Foundations of Computing Cheatsheet

Cheat Sheet
ALGEBRAIC LAWS OF LOGIC SET IDENTITIES

a ∧b ≡b∧a A∩B =B∩A
Commutative
a ∨b ≡ b ∨a A∪B = B ∪A
(a ∧ b) ∧ c ≡ a ∧ (b ∧ c) (A ∩ B ) ∩ C = A ∩ (B ∩ C )
Associative
(a ∨ b) ∨ c ≡ a ∨ (b ∨ c) (A ∪ B ) ∪ C = A ∪ (B ∪ C )
a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c) A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
Distributive
a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C )
¬(a ∧ b) ≡ ¬a ∨ ¬b (A ∩ B )c = A c ∪ B c
De Morgan’s Law
¬(a ∨ b) ≡ ¬a ∧ ¬b (A ∪ B )c = A c ∩ B c
Double negation ¬ ¬a ≡ a
Double complement (A c )c = A

a ∧T ≡ a A ∩𝒰= A
Identity
a ∨F ≡ a A∪∅= A
a ∧ ¬a ≡ F
Negation
a ∨ ¬a ≡ T
A ∩ Ac = ∅
Complement
A ∪ Ac = 𝒰
a ∧a ≡a A∩A=A
Idempotence
a ∨a ≡ a A∪A =A
a∧F ≡F A ∩∅=∅
Universal bound
a ∨T ≡T A∪𝒰=𝒰
a ∨ (a ∧ b) ≡ a A ∪ (A ∩ B ) = A
Absorption
a ∧ (a ∨ b) ≡ a A ∩ (A ∪ B ) = A
Negation of T ¬T ≡ F
Negation of F ¬F ≡ T
Complement of 𝒰 𝒰c = ∅
Complement of ∅ ∅c = 𝒰

Translation ⇒ a ⇒ b ≡ ¬a ∨ b
Translation ⇔ a ⇔ b ≡ (a ⇒ b) ∧ (b ⇒ a)
Set difference A\ B = A ∩ B c


Rules of inference
Modus Ponens Modus Tollens Elimination Conjunction Transitivity
a ⇒b a ⇒b a ∨b a a ⇒b
a ¬b ¬b b b ⇒c
∴ b ∴ ¬a ∴ a ∴ a∧b ∴ a ⇒c

Specialization Generalization Contradiction Contradiction

a∧b a b ⇒F a
∴ a ∴ a ∨b ∴ ¬b b ⇒ ¬a
∴ ¬b
Case distinction Case distinction
a ⇒c a ⇒c
b ⇒c b ⇒c
p ⇒a ∨b a ∨b
∴ p ⇒c ∴ c