Page 16 - Chapter 2

• Two Structures with similar properties (Theorem 1)

Structure 1 (logic operations) (propositions, ∧, V, ~)

Structure 2 (sets operations) (sets, U, ∩ , - )

• Theorem 1

Commutative properties

p ∨ q ≡ q ∨p, p∧ q ≡ q ∧ p

Associative Properties

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

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

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

Idempotent Properties p ∨ p ≡ p , p∧ p ≡ p

Properties of Negation ~(~p) ≡ p

~(p ∨ q) ≡ (~p) ∧ (~q)

~(p ∧ q) ≡ (~p) ∨ (~q) De Morgan’s laws

• Theorem 2 (p ⇒ q) ≡ ((~p) ∨ q)

(p ⇒ q) ≡ (~q ⇒ ~p)

(p  q) ≡ ((p ⇒ q) ∧ (q ⇒ p))

~(p ⇒ q) ≡ (p ∧ ~q)

~(p  q) ≡ ((p ∧ ~q) ∨ (q ∧ ~p)