Laws of Logic and Theorems on Set Operations

Some definitions before studying the laws of logic

• Tautology: A compound statement that is always true regardless of its components is known as tautology.
  For example: 2 + 2 = 4 or 2 + 3 = 6.
• Contradiction: A compound statement that is always false regardless of its components is known as contradiction.
  For example: 2 + 2 = 4 and 2 + 3 = 6.
• Converse: Let p and q be two statements. Then, the converse of p ⇒ q is q ⇒ p.
  For example:
  Given statement: If a > 0, then a + 2 > 0.
  Converse: If a + 2 > 0, then a > 0.
• Inverse: Let p and q be two statements. Then, the inverse of p ⇒ q is ~p ⇒ ~q.
  For example:
  Given statement: If a > 0, then a + 2 > 0.
  Inverse: If a < 0, then a + 2 < 0.
• Contrapositive: Let p and q be two statements. Then, the contrapositive of p ⇒ q is ~q ⇒ ~p.
  For example:
  Given statement: If a > 0, then a + 2 > 0.
  Contrapositive: If a + 2 < 0, then a < 0.
• Logically Equivalent: Two statements S₁ and S₂ are said to be logically equivalent if both have the same truth values in the columns of the truth table. They are denoted by S₁ ≡ S₂
  For example:
  

  p	t	p ∨ t
  T	T	T
  F	T	T

  From the above table, t ≡ p ∨ t

Basic Laws of Logic

• Idempotent Laws:
  1. p ∧ p ≡ p
  2. p ∨ p ≡ p
• Commutative Laws:
  1. p ∧ q ≡ q ∧ p
  2. p ∨ q ≡ q ∨ p
• Associative Laws:
  1. p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r
  2. p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r
• Distributive Laws:
  1. p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
  2. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
• De Morgan's Laws:
  1. ~(p ∧ q) ≡ (~p ∨ ~q)
  2. ~(p ∨ q) ≡ (~p ∧ ~q)

Verification of the Laws of Logic

p ∧ p ≡ p (Idempotent Law)

p ∨ p ≡ p (Idempotent Law)

p ∧ q ≡ q ∧ p (Commutative Law)

p ∨ q ≡ q ∨ p (Commutative Law)

p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r (Associative Law)

p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r (Associative Law)

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)