Basics of Propositional Logic

Propositions

A proposition is a declarative statement that can be either true (T) or false (F), but not both. Examples include:

• "It is Sunday."

• "The Sun rises from the West." (False proposition)

• "3 + 3 = 7." (False proposition)

• "5 is a prime number." (True proposition)

Propositional logic is based on symbolic variables representing logical statements, typically denoted as A, B, C, P, Q, R, etc.

Syntax of Propositional Logic

The syntax of propositional logic defines the allowable sentences for knowledge representation. There are two types of propositions:

• Atomic Propositions Atomic propositions are simple propositions consisting of a single proposition symbol. These are sentences that must be either true or false.

  Examples:

  • "2 + 2 = 4" 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 Propositions Compound propositions are constructed by combining simpler or atomic propositions using parentheses and logical connectives. Examples:

  • "It is raining today, and the street is wet."

  • "Ankit is a doctor, and his clinic is in Mumbai."

Logical Connectives

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 (¬P) – A sentence such as ¬P is called the negation of P. A literal can be either a positive literal or a negative literal.

• Conjunction (P ∧ Q) – A sentence that has the ∧ 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

  • Representation: P∧ Q

• Disjunction (P ∨ Q) – A sentence that has the ∨ connective, such as P ∨ Q, is called disjunction, where P and Q are the propositions.

  Example: "Ritika is a doctor or an engineer."

  • P = Ritika is a doctor

  • Q = Ritika is an engineer

  • Representation: P ∨ Q

• Implication (P → Q) – A sentence such as P → Q is called an implication. Implications are also known as if-then rules.

  Example: "If it is raining, then the street is wet."

  • P = It is raining

  • Q = The street is wet

  • Representation: P → Q

• Biconditional (P ⇔ Q) – 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

  • Representation: P ⇔ Q

Summarized Table for Propositional Logic Connectives

Logical Connective	Symbol	Meaning	Example
Negation	¬P	The opposite of P	¬(It is raining) = It is not raining
Conjunction	P ∧ Q	Both P and Q must be true	It is raining ∧ It is cold
Disjunction	P ∨ Q	At least one of P or Q must be true	It is raining ∨ It is cold
Implication	P → Q	If P is true, then Q must also be true	If it rains → The street is wet
Biconditional	P ⇔ Q	P is true if and only if Q is true	I am breathing ⇔ I am alive

Truth Tables for All Logical Connectives

Negation (¬P)

P	¬P
True	False
False	True

Conjunction (P ∧ Q)

P	Q	P ∧ Q
True	True	True
True	False	False
False	True	False
False	False	False

Disjunction (P ∨ Q)

P	Q	P ∨ Q
True	True	True
True	False	True
False	True	True
False	False	False

Implication (P → Q)

P	Q	P → Q
True	True	True
True	False	False
False	True	True
False	False	True

Biconditional (P ⇔ Q)

P	Q	P ⇔ Q
True	True	True
True	False	False
False	True	False
False	False	True

Truth Table with Three Propositions

We can build a proposition composing three propositions P, Q, and R. This truth table consists of 8 rows (2³ combinations of truth values).

P	Q	R	P ∧ (Q ∨ R)
True	True	True	True
True	True	False	True
True	False	True	True
True	False	False	False
False	True	True	False
False	True	False	False
False	False	True	False
False	False	False	False

Precedence of Connectives

Like arithmetic operators, logical connectives have a precedence order that should be followed while evaluating a propositional statement:

1. Parenthesis (Highest precedence)

2. Negation (¬)

3. Conjunction (∧)

4. Disjunction (∨)

5. Implication (→)

6. Biconditional (↔) (Lowest precedence)

For better clarity, parentheses should be used to ensure the correct interpretation of statements.

Logical Equivalence and Properties of Operators

Logical equivalence is a property where two propositions yield the same truth values across all possible scenarios. If two propositions A and B are logically equivalent, they are written as A ⇔ B.

Some essential properties of propositional logic include:

• Commutativity: P ∧ Q = Q ∧ P, P ∨ Q = Q ∨ P

• Associativity: (P ∧ Q) ∧ R = P ∧ (Q ∧ R)

• Identity element: P ∧ True = P, P ∨ True = True

• Distributivity: P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R)

• De Morgan’s Laws: ¬(P ∧ Q) = ¬P ∨ ¬Q, ¬(P ∨ Q) = ¬P ∧ ¬Q

• Double Negation: ¬(¬P) = P

Conclusion

Propositional logic provides a structured way to represent and process information in AI. Its ability to model real-world scenarios using logical statements makes it a valuable tool for reasoning, decision-making, and automation. While simple, propositional logic forms the foundation for more advanced logical systems used in AI and machine learning, enabling more sophisticated forms of knowledge representation and reasoning.