Propositional Equivalences (KR 1.3)
Tautologies & Contradictions
Tautology: a proposition that is always true
ex) p V ¬p
Contradiction: a propisiton that is always false
ex) p ^ ¬p
Logically Equivalent
Two propositions p and q are logically equivalent if p↔q is a tautology
- We write this as p⇔q or as p≡q where p and q are compound propositions.
- Propositions p and q are equivalent iff the columns in a truth table giving their truth values agree
De Morgan’s Laws
First Law: ¬(p^q) ≡ ¬pV¬q
Second Law: ¬(pVq) ≡ ¬p ^ ¬q
- visual representation of de morgan’s law
Key Logical Equivalences
- Identity Laws:
- Domination Laws:
- Idempotent Laws:
- Double Negation Law:
- Negation Laws:
- Commutative Laws:
- Associative Laws: