Propositional Logic in AI

Table of Content:

Content Highlight:

Propositional logic is a foundational component of artificial intelligence, representing knowledge through true/false propositions. It uses logical connectives like AND, OR, and NOT to create complex statements. However, it has limitations, such as its inability to represent quantifiers or describe properties, which restrict its ability to handle complex reasoning tasks.

Propositional logic in Artificial intelligence

Propositional Logic (PL) is a foundational component of Artificial Intelligence, offering a systematic approach to representing knowledge. In PL, statements are expressed as propositions, each of which can be either true or false. This logical framework provides a means to model the world by breaking down complex concepts into simpler, binary components. By manipulating these propositions according to defined rules, AI systems can infer new knowledge, make decisions, and solve problems in a structured and rigorous manner.

Let's say we have two propositions:

  • p: "It is raining."
  • q: "The streets are wet."

We can express the relationship between these two propositions using a logical connective:

pq: "If it is raining, then the streets are wet."

In this example, p and q are propositions that can be either true or false. The logical connective → represents implication, indicating that if p is true, then q must also be true. This simple example demonstrates how Propositional Logic can be used to represent relationships between different statements, which is crucial in AI for reasoning and decision-making.

Following are some basic facts about propositional logic:

  • Boolean Logic: Propositional logic, also known as Boolean logic, operates on the values 0 and 1, representing false and true, respectively.
  • Symbolic Variables: In propositional logic, symbolic variables (e.g., A, B, C, P, Q, R) are used to represent propositions.
  • True or False: Propositions in propositional logic can only be true or false, but not both simultaneously.
  • Components: Propositional logic consists of propositions, logical connectives (also known as operators), and objects, relations, or functions.
  • Logical Connectives: These are operators that connect propositions, forming complex statements. Examples include AND, OR, NOT, IMPLIES, etc.
  • Basic Elements: Propositions and connectives are the fundamental elements of propositional logic.
  • Tautology: A proposition formula that is always true is called a tautology, or a valid sentence.
  • Contradiction: A proposition formula that is always false is called a contradiction.
  • Statements vs. Propositions: Statements like questions, commands, or opinions are not propositions (e.g., "Where is Rohini", "How are you", "What is your name").

Syntax of propositional logic:

The syntax of propositional logic defines the allowable sentences for the knowledge representation.

There are two types of Propositions:

  1. Atomic Propositions
  2. Compound propositions

Atomic Proposition: Atomic propositions are the simple propositions. It consists of a single proposition symbol. These are the sentences which must be either true or false.

Example:

  • 2+2 is 4, it is an atomic proposition as it is a true fact.
  • "The Sun is cold" is also a proposition as it is a false fact.

Compound proposition: Compound propositions are constructed by combining simpler or atomic propositions, using parenthesis and logical connectives.

Example:

  • "It is raining today, and street is wet."
  • "Ankit is a doctor, and his clinic is in Mumbai."

These connectives are also called logical operators.

The propositions and connectives are the basic elements of the propositional logic.

Connectives can be said as a logical operator which connects two sentences.

A proposition formula which is always true is called tautology, and it is also called a valid sentence. A proposition formula which is always false is called Contradiction.

A proposition formula which has both true and false values is called Statements which are questions, commands, or opinions are not propositions such as "Where is Rohini", "How are you", "What is your name", are not propositions.

Logical connectives are used to connect two simpler propositions or represent a sentence logically. We can create compound propositions with the help of logical connectives. There are mainly five connectives, which are given as follows:

  • Negation: A sentence such as ¬ P is called the negation of P. A literal can be either a positive literal or a negative literal.
  • Conjunction: A sentence which has ∧ connective such as, P ∧ Q is called a conjunction. Example: Rohan is intelligent and hardworking. It can be written as, P= Rohan is intelligent, Q= Rohan is hardworking. → P∧ Q.
  • Disjunction: A sentence which has ∨ connective, such as P ∨ Q is called disjunction, where P and Q are the propositions. Example: "Ritika is a doctor or Engineer", Here P= Ritika is Doctor. Q= Ritika is Doctor, so we can write it as P ∨ Q.
  • Implication: A sentence such as P → Q is called an implication. Implications are also known as if-then rules. It can be represented as If it is raining, then the street is wet. Let P= It is raining, and Q= Street is wet, so it is represented as P → Q.
  • Biconditional: A sentence such as P⇔ Q is a biconditional sentence, example If I am breathing, then I am alive P= I am breathing, Q= I am alive, it can be represented as P ⇔ Q.

These connectives are also called logical operators.

Following is the summarized table for Propositional Logic Connectives:

Connective Symbol Technical Term Word Example
Conjunction AND P ∧ Q
V Disjunction OR P V Q
Implication Implies P → Q
Biconditional If and only If P ⇔ Q
¬ or ~ Negation Not ¬P or ¬Q

Truth Table:

In propositional logic, understanding the truth values of propositions in all possible scenarios is crucial. We can combine these propositions using logical connectives, and represent the resulting combinations in a tabular format known as a Truth table. Here are the truth tables for all logical connectives:

Negation (¬):

P ¬P
true false
false true

Conjunction (∧):

P Q P ∧ Q
true true true
true false false
false true false
false false false

Disjunction (∨):

P Q P V Q
true true true
true false true
false true true
false false false

Implication (→):

P Q P → Q
true true true
true false false
false true true
false false true

Biconditional (↔):

P Q P ⇔ Q
true true true
true false false
false true false
false false true

Truth table with three propositions:

You can build a proposition composing three propositions P, Q, and R. The truth table is made up of 8Xn Tuples as we have taken three proposition symbols.

P Q R ¬R P V Q P V Q → ¬R
true true true false true false
true true false true true true
true false true false true false
true false false true true true
false true true false true false
false true false true true true
false false true false true true
false false false true true true

Precedence of connectives:

Propositional connectors or logical operators, like arithmetic operators, have a precedence order. When evaluating a propositional problem, this order should be followed. The following is a list of the operator precedence order:

Precedence Operators
First Precedence Parenthesis
Second Precedence Negation
Third Precedence Conjunction(AND)
Forth Precedence Disjunction(OR)
Fifth Precedence Implication
Sixth Precedence Biconditional

Note: Use parenthesis to make sure of the correct interpretations for a better understanding. For example: ¬R∨ Q, It can be interpreted as (¬R) ∨ Q.

Logical equivalence:

One of the characteristics of propositional logic is logical equivalence. If and only if the truth table's columns are equal, two assertions are said to be logically comparable. Let's take two propositions P and Q, so for logical equivalence, we can write it as P⇔Q. In below truth table we can see that column for ¬P ∨ Q and P→Q, are identical hence P is Equivalent to P

P Q ¬P ¬P V Q P → Q
T T F T T
T F F F F
F T T T T
F F T T T

Properties of Operators:

  • Commutativity:
    • P ∧ Q= Q ∧ P, or
    • P ∨ Q = Q ∨ P.
  • Associativity:
    • (P ∧ Q) ∧ R = P ∧ (Q ∧ R),
    • (P ∨ Q) ∨ R= P ∨ (Q ∨ R).
  • Identity element:
    • P ∧ True = P,
    • P ∨ True= True.
  • Distributive:
    • P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
    • P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
  • DE Morgan's Law:
    • ¬(P ∧ Q) = (¬P) ∨ (¬Q),
    • ¬(P ∨ Q) = (¬ P) ∧ (¬Q).
  • Double-negation elimination:
    • ¬(¬P) = P.

Limitations of Propositional logic:

Propositional logic, while powerful for certain tasks, has its limitations when it comes to representing certain types of statements and relationships. Some of the key limitations include:

  1. Inability to Represent Quantifiers: Propositional logic cannot represent quantifiers like "all," "some," or "none." For example, it cannot directly express statements like "All the girls are intelligent" or "Some apples are sweet."
  2. Limited Expressive Power: Propositional logic has limited expressive power compared to higher-order logics. It cannot capture the nuances of complex relationships or infer higher-level concepts.
  3. Lack of Description for Properties: In propositional logic, it is challenging to describe statements in terms of their properties or logical relationships. The logic is more focused on the truth values of propositions rather than the properties they represent.

While propositional logic is valuable for certain types of reasoning, its limitations make it unsuitable for representing more complex concepts and relationships found in natural language and more advanced forms of reasoning.