Logical Equivalence & Laws

definitions
discrete-math
logic
propositional-logic

Two statement forms are logically equivalent (\(\equiv\)) if they have the same truth value for every combination of truth values of their variables — shown via a truth table, or by chaining the laws below. To show two forms are not equivalent (\(\not\equiv\)), exhibit one combination of truth values where they differ.

\(\equiv\) compares statements (like \(=\) compares numbers); it’s not a connective itself.

Laws of logical equivalence

Provided in the exam. These laws are printed on the MATH1061/MATH7861 Examination Formula Page, so they don’t need memorising — the marks are in choosing and applying them, and in naming the one you used at each step. The same page also carries the valid-argument-forms and the set identities.

Given statement variables \(p, q, r\), a tautology \(\mathbf{t}\), and a contradiction \(\mathbf{c}\):

Law Form 1 Form 2
Commutative \(p \land q \equiv q \land p\) \(p \lor q \equiv q \lor p\)
Associative \((p \land q) \land r \equiv p \land (q \land r)\) \((p \lor q) \lor r \equiv p \lor (q \lor r)\)
Distributive \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\) \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)
Identity \(p \land \mathbf{t} \equiv p\) \(p \lor \mathbf{c} \equiv p\)
Negation \(p \lor \sim p \equiv \mathbf{t}\) \(p \land \sim p \equiv \mathbf{c}\)
Double negative \(\sim(\sim p) \equiv p\)
Idempotent \(p \land p \equiv p\) \(p \lor p \equiv p\)
Universal bound \(p \lor \mathbf{t} \equiv \mathbf{t}\) \(p \land \mathbf{c} \equiv \mathbf{c}\)
De Morgan’s \(\sim(p \land q) \equiv \sim p \lor \sim q\) \(\sim(p \lor q) \equiv \sim p \land \sim q\)
Absorption \(p \lor (p \land q) \equiv p\) \(p \land (p \lor q) \equiv p\)
Negations of \(\mathbf{t}\)/\(\mathbf{c}\) \(\sim \mathbf{t} \equiv \mathbf{c}\) \(\sim \mathbf{c} \equiv \mathbf{t}\)

De Morgan’s Laws are especially important for negating “and”/“or” statements — e.g. the negation of “5 is divisible by 2 and 6 is divisible by 2” is “5 is not divisible by 2 or 6 is not divisible by 2”.

See also