Difficulty: Introductory–Intermediate | Prerequisites: Basic understanding of logical connectives (AND, OR, NOT, implication).
Propositional calculus is the foundation of logical reasoning in computer science and artificial intelligence. Before you can build inference engines, write formal proofs, or understand how an AI agent reasons, you need fluency in the identities that govern how logical expressions can be rewritten. These identities are to logic what algebraic identities (like a + b = b + a) are to arithmetic. If you are behind, make sure you understand truth tables and the five basic connectives (¬, ∧, ∨, →, ↔) before working through this material.
Every logical identity here can be proved by building a truth table and confirming that both sides produce the same output for every possible input. The core laws (De Morgan's, commutativity, associativity, distributivity) let you rewrite any propositional formula into equivalent forms, which is essential for simplification, normal-form conversion, and automated reasoning.
Propositional calculus
The branch of logic that deals with propositions (statements that are either true or false) and the connectives that combine them. Think of it as the algebra of true/false values.
Logical equivalence (≡)
Two expressions are logically equivalent when they produce the same truth value for every possible assignment of their variables. In simple terms, they always agree, no matter what.
Contradiction
A formula that is false under every possible assignment. The classic example is P ∧ ¬P. Think of it as a statement that defeats itself.
Identity element
A value that, when combined with a variable under a given operation, returns the variable unchanged. FALSE is the identity for OR; TRUE is the identity for AND.
Negation (¬)
Flips a truth value: true becomes false, false becomes true. Sometimes written as NOT or ~.
Conjunction (∧)
Logical AND. True only when both operands are true.
Disjunction (∨)
Logical OR. True when at least one operand is true.
Implication (→)
"If P then Q." False only when P is true and Q is false. In simple terms, a promise is only broken when the condition holds but the result does not.
A proposition ANDed with its own negation is always false. There is no assignment of P that makes both P and ¬P true at the same time.
When P = T, ¬P = F, so P ∧ ¬P = F
When P = F, ¬P = T, so P ∧ ¬P = F
This identity is the formal basis for proof by contradiction.
ORing anything with FALSE leaves it unchanged, because FALSE contributes nothing.
When P = T, P ∨ F = T
When P = F, P ∨ F = F
Negating a negation returns you to the original value. Two "nots" cancel out.
When P = T, ¬P = F, ¬(¬P) = T
When P = F, ¬P = T, ¬(¬P) = F
An implication can always be rewritten as "either the premise is false, or the conclusion is true." This equivalence is heavily used when converting formulas to conjunctive or disjunctive normal form.
The only row where P → Q is false is P = T, Q = F. ¬P ∨ Q also gives F only on that row.
An implication is logically equivalent to its contrapositive. "If it rains, the ground is wet" is the same as "if the ground is not wet, it did not rain." The converse (Q → P) and inverse (¬P → ¬Q) are not equivalent to the original.
Truth table confirms both sides produce T, F, T, T across the four input rows.
These two laws describe how negation distributes over conjunction and disjunction. They are among the most frequently used identities in logic, circuit design, and programming.
De Morgan's Law 1: ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Negating a disjunction is the same as conjoining the negations. "It is not the case that P or Q" means "P is false and Q is false."
The only row where ¬(P ∨ Q) is true is P = F, Q = F, which matches ¬P ∧ ¬Q.
De Morgan's Law 2: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
Negating a conjunction is the same as disjoining the negations. "It is not the case that both P and Q" means "at least one of them is false."
The only row where ¬(P ∧ Q) is false is P = T, Q = T, which matches ¬P ∨ ¬Q.
A useful mnemonic: negation flips the connective (∧ becomes ∨, and vice versa) and negates each operand.
Commutative Law for AND: P ∧ Q ≡ Q ∧ P
The order of operands does not matter for conjunction. Confirmed by truth table: all four rows match.
Commutative Law for OR: P ∨ Q ≡ Q ∨ P
The order of operands does not matter for disjunction. Same confirmation method.
Note: implication is not commutative. P → Q is not the same as Q → P.
Associative Law for AND: (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
Grouping does not matter when all connectives are AND. Proved with all eight rows of a three-variable truth table.
Associative Law for OR: (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
Grouping does not matter when all connectives are OR. Same eight-row confirmation.
These laws justify writing P ∧ Q ∧ R without parentheses, since the result is the same regardless of grouping.
Distributive Law 1 (OR over AND): P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
OR distributes over AND, just as multiplication distributes over addition in arithmetic. Confirmed across all eight rows.
Distributive Law 2 (AND over OR): P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
AND distributes over OR. This is the dual of Law 1. Also confirmed across all eight rows.
These are critical for converting between conjunctive normal form (CNF) and disjunctive normal form (DNF).
Summary of all identities at a glance:
P ∧ ¬P ≡ FALSE (contradiction)
P ∨ FALSE ≡ P (identity for OR)
¬(¬P) ≡ P (double negation)
P → Q ≡ ¬P ∨ Q (implication elimination)
P → Q ≡ ¬Q → ¬P (contrapositive)
¬(P ∨ Q) ≡ ¬P ∧ ¬Q (De Morgan 1)
¬(P ∧ Q) ≡ ¬P ∨ ¬Q (De Morgan 2)
P ∧ Q ≡ Q ∧ P (commutativity of AND)
P ∨ Q ≡ Q ∨ P (commutativity of OR)
(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R) (associativity of AND)
(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R) (associativity of OR)
P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) (distribution of OR over AND)
P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) (distribution of AND over OR)
These identities are not just exam material. Digital circuit designers use De Morgan's laws to convert between NAND and NOR gate implementations. Software engineers apply them when simplifying complex conditional expressions (for instance, rewriting !(a && b) as !a || !b). In AI, resolution-based theorem provers depend on converting formulas to CNF, which requires distributive and De Morgan's laws at every step.
Students often assume the converse of an implication (Q → P) is equivalent to the original (P → Q). It is not. Only the contrapositive (¬Q → ¬P) is equivalent.
De Morgan's laws are sometimes misapplied by flipping the connective without negating the operands, or negating the operands without flipping the connective. Both steps are required.
Students sometimes think implication is commutative because AND and OR are. Implication has a direction: "if P then Q" is fundamentally different from "if Q then P."
Confusing the identity element: FALSE is the identity for OR (P ∨ FALSE = P), while TRUE is the identity for AND (P ∧ TRUE = P). Mixing these up produces wrong simplifications.
⚠️ Truth table construction is a standard exam question format. Be comfortable building tables with up to three variables (eight rows).
⚠️ You will almost certainly be asked to prove at least one equivalence using truth tables and at least one using algebraic manipulation with identities.
⚠️ De Morgan's laws and the implication-to-disjunction equivalence (P → Q ≡ ¬P ∨ Q) appear in nearly every propositional logic exam.
⚠️ Know the difference between equivalence (≡, same truth values everywhere) and implication (→, one-directional).
True or false: P ∨ ¬P ≡ TRUE.
Fill in the blank: ¬(P ∧ Q) ≡ ______.
True or false: The converse of P → Q is logically equivalent to P → Q.
Fill in the blank: P → Q can be rewritten as ¬P ____ Q.
True or false: (P ∨ Q) ∨ R and P ∨ (Q ∨ R) always have the same truth value.
Answers: 1. True (tautology, the complement of the contradiction law). 2. ¬P ∨ ¬Q (De Morgan's Law 2). 3. False (the contrapositive is equivalent, not the converse). 4. ∨ (disjunction). 5. True (associative law for OR).
Q: Prove using a truth table that P ∧ ¬P ≡ FALSE.
A: Construct a two-row table. When P = T, ¬P = F, so P ∧ ¬P = F. When P = F, ¬P = T, so P ∧ ¬P = F. Both rows yield F, which matches FALSE in every row. Therefore the equivalence holds.
Q: State De Morgan's Law 1 and give a real-world example.
A: ¬(P ∨ Q) ≡ ¬P ∧ ¬Q. Example: "It is not the case that it is raining or snowing" is the same as "It is not raining and it is not snowing."
Q: Why is implication elimination (P → Q ≡ ¬P ∨ Q) useful in automated reasoning?
A: It removes the implication connective entirely, allowing the formula to be expressed using only ¬, ∧, and ∨. This is a required step when converting to conjunctive normal form (CNF), which is the input format for resolution-based theorem provers.
Q: How many rows does a truth table need for an expression with three variables?
A: 2³ = 8 rows, one for each combination of truth values.
Q: Write the contrapositive of "If it is a square, then it has four sides."
A: "If it does not have four sides, then it is not a square." Both statements are logically equivalent.
These identities connect directly to normal forms (CNF and DNF), which are central to resolution in AI. They also underpin Boolean algebra used in digital logic design and set theory (where De Morgan's laws have exact analogues with union, intersection, and complement). If you go on to study first-order logic, the same structural laws reappear with quantifiers added.
propositional logic, propositional calculus, truth tables, logical equivalence, De Morgan's laws, De Morgan's theorem, commutativity, associativity, distributivity, contrapositive, implication elimination, double negation, contradiction, tautology, Boolean algebra, logical identities, CNF, DNF, conjunctive normal form, disjunctive normal form, negation, conjunction, disjunction, material conditional, logic laws, AI logic, discrete mathematics, proof by truth table