PROPOSITIONAL EQUIVALENCES

Important Logical Equivalences. The logical equivalences below are important
equivalences that should be memorized.
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
Law:
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)
De Morgan’s Laws: ¬(p ∧ q) ⇔ ¬p ∨ ¬q
¬(p ∨ q) ⇔ ¬p ∧ ¬q
Absorption Laws: p ∧ (p ∨ q) ⇔ p
p ∨ (p ∧ q) ⇔ p
2. PROPOSITIONAL EQUIVALENCES 38
Implication Law: (p → q) ⇔ (¬p ∨ q)
Contrapositive Law: (p → q) ⇔ (¬q → ¬p)
Tautology: p ∨ ¬p ⇔ T
Contradiction: p ∧ ¬p ⇔ F
Equivalence: (p → q) ∧ (q → p) ⇔ (p ↔ q)

Simplifying Propositions.

Use the logical equivalences above to show that ¬(p ∨ ¬(p ∧ q))
is a contradiction.
Solution.
¬(p ∨ ¬(p ∧ q))
⇔ ¬p ∧ ¬(¬(p ∧ q)) De Morgan’s Law
⇔ ¬p ∧ (p ∧ q) Double Negation Law
⇔ (¬p ∧ p) ∧ q Associative Law
⇔ F ∧ q Contradiction
⇔ F Domination Law and Commutative Law

Author: Team onlinestudy.guru

Leave a Reply

Your email address will not be published. Required fields are marked *