[INT 1358]: Discrete Mathematics I
1.3 Propositional Equivalences
Tautologies, Contradictions, and Contingencies
• A tautology is a compound proposition which is always true.
• A contradiction is a compound proposition which is always false.
• A contingency is a compound proposition which is neither a tautology nor a contradiction.
Logical Equivalences
Identity Name
p∧T≡p
Identity Laws
p∨F≡p
p∨T≡T
Domination laws
p∧F≡F
p∨p≡p
Idempotent laws
p∧p≡p
¬(¬p) ≡ p Double negation law
p∨q ≡q∨p
Commutative laws
p∧q ≡q∧p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
¬(p ∧ q) ≡ ¬p ∨ ¬q
De Morgan’s laws
¬(p ∨ q) ≡ ¬p ∧ ¬q
p ∨ (p ∧ q) ≡ p
Absorption laws
p ∧ (p ∨ q) ≡ p
p ∨ ¬p ≡ T
Negation laws
p ∧ ¬p ≡ F
Logical Equivlances Involving Condi-
tional Statements
p → q ≡ ¬p ∨ q
Logical Equivalences Involving Bicondi-
p → q ≡ ¬q → ¬p
tional Statements
p ∨ q ≡ ¬p → q
p ↔ q ≡ (p → q) ∧ (q → p)
p ∧ q ≡ ¬(p → ¬q)
p ↔ q ≡ ¬p ↔ ¬q
¬(p → q) ≡ q ∧ ¬q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
¬(p ↔ q) ≡ p ↔ ¬q
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
1
[INT 1358]: Discrete Mathematics I
Constructing New Logical Equivalences
We can construct new logical equivalences by applying known logically equivalent statements to
show that A ≡ B.
Recall that two propositions p and q are logically equivalent if and only if p ↔ q is a tautology
(a.k.a. their truth tables match). However, for very long or complex propositions, it might be less
work to do a proof of logical equivalence.
Goal: Get both sides to be the same.
Strategy:
• Apply rules from the list of Logical Equivalences to manipulate one side of the proposition
• Apply one rule per line
• Keep applying rules until we arrive at our goal
1.3 pg. 34 # 7
Use De Morgan’s laws to find the negation of each of the following statements.
a) Jan is rich and happy.
p = “Jan is rich”
q = “Jan is happy”
p∧q
¬(p ∧ q) ≡ ¬p ∨ ¬q
“Jan is not rich, or not happy.”
b) Mei walks or takes the bus to class.
p = “Mei walks to class”
q = Mei takes the bus to class.”
p∨q
¬(p ∨ q) ≡ ¬p ∧ ¬q
“Mei does not walk to class, and Mei does not take the bus to class.”
1.3 pg. 35 # 11
Show that each conditional statement is a tautology without using truth tables
b p → (p ∨ q)
p → (p ∨ q)
≡ ¬p ∨ (p ∨ q) Law of Implication
≡ (¬p ∨ p) ∨ q Associative Law
≡T∨q Negation Law
≡T Domination law
2
[INT 1358]: Discrete Mathematics I
d (p ∧ q) → (p → q)
(p ∧ q) → (p → q)
≡ ¬(p ∧ q) ∨ (p → q) Law of Implication
≡ ¬(p ∧ q) ∨ (¬p ∨ q) Law of Implication
≡ (¬p ∨ ¬q) ∨ (¬p ∨ q) De Morgan’s Law
≡ (¬p) ∨ (¬q ∨ (¬p ∨ q)) Associative Law
≡ (¬p) ∨ ((¬p ∨ q) ∨ ¬q) Commutative Law
≡ (¬p) ∨ (¬p ∨ (q ∨ ¬q)) Associative Law
≡ (¬p) ∨ (¬p ∨ T) Negation Law
≡ (¬p) ∨ (T) Domination Law
≡T Domination Law
f ¬(p → q) → ¬q
¬(p → q) → ¬q
≡ ¬¬(p → q) ∨ ¬q Law of Implication
≡ (p → q) ∨ ¬q Double Negation
≡ (¬p ∨ q) ∨ ¬q Law of Implication
≡ ¬p ∨ (q ∨ ¬q) Associative Law
≡ ¬p ∨ T Negation Law
≡T Domination Law
1.3 pg. 35 # 15
Determine whether (¬q ∧ (p → q)) → ¬p) is a tautology.
p q ¬p ¬q p→q ¬q ∧ (p → q)) (¬q ∧ (p ∧ q)) → ¬p
T T F F T F T
T F F T F F T
F T T F T F T
F F T T T T T
1.3 pg. 35 # 17
Show that ¬(p ↔ q) and p ↔ ¬q are logically equivalent.
p q ¬q p↔q ¬(p ↔ q) p ↔ ¬q
T T F T F F
T F T F T T
F T F F T T
F F T T F F
