Logical Equivalences

What Are Logical Equivalences?

Two compound propositions are logically equivalent if they have the same truth value for every possible combination of truth values of their variables. We write P ≡ Q to indicate logical equivalence.

Important Equivalence Laws

Identity Laws:     p ∧ T ≡ p       p ∨ F ≡ p
Domination Laws:   p ∨ T ≡ T       p ∧ F ≡ F
Idempotent Laws:   p ∨ p ≡ p       p ∧ p ≡ p
Double Negation:   ¬(¬p) ≡ p

Commutative:  p ∨ q ≡ q ∨ p     p ∧ q ≡ q ∧ p
Associative:  (p∨q)∨r ≡ p∨(q∨r)  (p∧q)∧r ≡ p∧(q∧r)
Distributive: p∨(q∧r) ≡ (p∨q)∧(p∨r)
              p∧(q∨r) ≡ (p∧q)∨(p∧r)

De Morgan's Laws

De Morgan's Laws are among the most useful equivalences in logic and computer science:

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

In plain English: the negation of "A and B" is "not A or not B", and the negation of "A or B" is "not A and not B".

Contrapositive and Converse

Conditional:    p → q
Contrapositive: ¬q → ¬p    (equivalent to p → q)
Converse:       q → p       (NOT equivalent)
Inverse:        ¬p → ¬q     (NOT equivalent)