Propositional logic and equivalences
Propositional logic studies Boolean statements, their connectives and algebraic laws so you can simplify logical formulas, prove equivalences and convert formulas to normal forms used in design, verification and algorithms.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Propositional logic is the foundation for reasoning about digital circuits, program conditions, correctness proofs and SAT solvers. Engineers use logical equivalences to simplify conditions in code, to minimise logic in circuits and to transform formulas into normal forms required by automated tools.
Key ideas
Start from first principles and define every term before use.
- proposition: a declarative sentence that is either true (T) or false (F), but not both. Example: "It is raining" (if we can assign a truth value).
- logical connective: an operation that builds new propositions from one or more propositions. Main connectives below.
- negation (¬p): the proposition "not p"; it is true exactly when p is false.
- conjunction (p ∧ q): the proposition "p and q"; true exactly when both p and q are true.
- disjunction (p ∨ q): the proposition "p or q" (inclusive); true when at least one of p or q is true.
- implication / material implication (p → q): the proposition "if p then q"; defined as false only when p is true and q is false, otherwise true.
- biconditional (p ↔ q): the proposition "p if and only if q"; true when p and q have the same truth value.
- literal: either a proposition p or its negation ¬p.
- clause: a disjunction of literals (used in CNF). In DNF, the analogous building block is called a term (a conjunction of literals).
- tautology: a formula that is true for every assignment of truth values to its propositional variables.
- contradiction: a formula that is false for every assignment.
- contingency: a formula that is neither a tautology nor a contradiction; its truth depends on the assignment.
- logical equivalence (φ ≡ ψ): two formulas φ and ψ are logically equivalent if they have the same truth value for every assignment of truth values to their variables.
- satisfiable: a formula is satisfiable if there exists at least one assignment that makes it true.
- conjunctive normal form (CNF): a conjunction of clauses where each clause is a disjunction of literals (useful for SAT solvers). In digital logic this corresponds to Product of Sums (POS); a clause mentioning every variable is a maxterm.
- disjunctive normal form (DNF): a disjunction of terms where each term is a conjunction of literals. In digital logic this corresponds to Sum of Products (SOP); a term mentioning every variable is a minterm.
Exact algebraic laws (assume p, q, r are arbitrary propositions). These are standard and can be proved by truth table or algebraic steps.
Identity laws:
- p ∧ T ≡ p
- p ∨ F ≡ p
Domination laws:
- p ∨ T ≡ T
- p ∧ F ≡ F
Idempotent laws:
- p ∨ p ≡ p
- p ∧ p ≡ p
Negation laws:
- p ∨ ¬p ≡ T (law of excluded middle)
- p ∧ ¬p ≡ F (contradiction)
Double negation:
- ¬(¬p) ≡ p
Commutative laws:
- p ∨ q ≡ q ∨ p
- p ∧ q ≡ q ∧ p
Associative laws:
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
- (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributive laws:
- p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
- p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Absorption laws:
- p ∨ (p ∧ q) ≡ p
- p ∧ (p ∨ q) ≡ p
De Morgan's laws (exact form):
- ¬(p ∧ q) ≡ ¬p ∨ ¬q
- ¬(p ∨ q) ≡ ¬p ∧ ¬q
Implication and biconditional equivalences:
- p → q ≡ ¬p ∨ q (material implication)
- p ↔ q ≡ (p → q) ∧ (q → p) ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
- Contrapositive: p → q ≡ ¬q → ¬p
Exportation (useful in proofs):
- (p ∧ q) → r ≡ p → (q → r)
Typical derivations universities ask for (outline):
- Prove p → q ≡ ¬p ∨ q by truth table: draw a 4-row table with columns p, q, p→q, ¬p∨q and show identical column values.
- Use De Morgan to push negation inward: convert ¬(p ∨ (q ∧ r)) step by step to ¬p ∧ (¬q ∨ ¬r) (show intermediate steps and cite De Morgan; distributivity is not needed here).
- Prove distributive law p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) by truth table or by algebraic manipulation using known laws.
What to draw in answers: for any truth-table proof draw a table with columns for each basic variable (p, q, r...), intermediate subformulas in the simplification order, and the final formula; label the rows with all combinations of truth assignments in standard order: T T ... , T F ..., F T ..., F F .... For n variables there are 2^n rows.
Formulas
¬(¬p) ≡ p — ¬p means logical negation of p; no SI unit; applies to any proposition p.
p ∧ q — conjunction of p and q; true when both p and q are true.
p ∨ q — disjunction (inclusive) of p and q; true when at least one is true.
p → q ≡ ¬p ∨ q — material implication; useful to eliminate → when converting to CNF/DNF.
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) — biconditional expansion.
¬(p ∧ q) ≡ ¬p ∨ ¬q — De Morgan (first form).
¬(p ∨ q) ≡ ¬p ∧ ¬q — De Morgan (second form).
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) — distributive law (∨ over ∧).
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) — distributive law (∧ over ∨).
CNF: conjunction of clauses; DNF: disjunction of terms.
(Each symbol: p, q, r are propositions; ≡ means logical equivalence; no physical units apply. Operator precedence (highest to lowest): ¬, ∧, ∨, →, ↔.)
Worked examples
Example 1 — show (p → q) ∧ (p → r) ≡ p → (q ∧ r).
- Start with left side: (p → q) ∧ (p → r).
- Replace each implication using p → q ≡ ¬p ∨ q: (¬p ∨ q) ∧ (¬p ∨ r).
- Factor ¬p using distributive law in reverse: ≡ ¬p ∨ (q ∧ r). (This follows from distributivity: (¬p ∨ q) ∧ (¬p ∨ r) ≡ ¬p ∨ (q ∧ r).)
- Replace back: ¬p ∨ (q ∧ r) ≡ p → (q ∧ r). Result: therefore (p → q) ∧ (p → r) ≡ p → (q ∧ r). Bold final: equivalent.
Example 2 — convert ¬(p ∨ (q ∧ ¬r)) to CNF.
- Start: ¬(p ∨ (q ∧ ¬r)).
- Apply De Morgan: ≡ ¬p ∧ ¬(q ∧ ¬r).
- Apply De Morgan again inside: ≡ ¬p ∧ (¬q ∨ r).
- Now this is already a conjunction of clauses: (¬p) ∧ (¬q ∨ r) — this is CNF (two clauses). Final: (¬p) ∧ (¬q ∨ r).
Example 3 — truth-table proof of p → q ≡ ¬p ∨ q. Draw and fill table: Columns: p | q | p → q | ¬p | ¬p ∨ q Rows: TT, TF, FT, FF. Calculate each column and show p→q column equals ¬p∨q column for all rows; conclude equivalence. (When writing answer in exam: draw 4-row table, compute each intermediate column, tick equality.)
Common mistakes
- Not listing all intermediate columns in a truth table; skipping columns leads to algebra mistakes.
- Confusing exclusive OR with inclusive OR (if a problem uses XOR, write it as (p ∨ q) ∧ ¬(p ∧ q) or explicitly state XOR).
- Missing the step to push negation inward using De Morgan before applying distributivity for CNF conversion.
- Treating implication as logical causation rather than the material implication truth table.
For your exam
Types of questions you will get:
- Definitions and short notes: define proposition, tautology, contradiction, logical equivalence; a full answer gives definition, a short example and significance.
- Derivations: prove a law by truth table (show full table with intermediate columns) or show algebraic equivalence using listed laws (cite each law when used).
- Conversions: convert a formula to CNF or DNF — full marks require step-by-step: (1) eliminate → and ↔, (2) push negation inward with De Morgan, (3) use distributive laws to reach CNF/DNF, (4) show final clauses/terms.
- Simplification: use algebraic laws to simplify an expression — show each applied law and intermediate formula.
- Small proofs: show two formulas are equivalent by truth table or by sequence of equivalence transformations, each justified.
What a full-marks answer includes: clear definitions, a correctly labelled truth table when required, each transformation with a cited law (for example: apply De Morgan, then distributivity), and the final simplified formula or conclusion. When converting to CNF/DNF show the three canonical steps listed above.
Quick check
- State De Morgan's two laws.
- Convert p → q to an expression without →.
- Is (p ∨ q) ∧ (p ∨ ¬q) equivalent to p ∨ (q ∧ ¬q)? Simplify.
Answers: 1) ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q. 2) p → q ≡ ¬p ∨ q. 3) (p ∨ q) ∧ (p ∨ ¬q) ≡ p ∨ (q ∧ ¬q) ≡ p ∨ F ≡ p; so yes, equivalent to p.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?