Page 17 - Chapter 2

• Theorem 3

~(∀xP(x)) ≡ ∃x~P(x)

~(∃xP(x)) ≡ ∀x(~P(x))

∃x(P(x) ⇒ Q(x)) ≡ ∀xP(x) ⇒ ∃xQ(x)

∃x(P(x) ∨ Q(x)) ≡ ∃xP(x) ∨ ∃xQ(x)

∀x(P(x) ∧ Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x)

∀xP(x) ∨ ∀xQ(x) ⇒ ∀x(P(x) ∨ Q(x)) is a tautology

∃x(P(x) ∧ Q(x)) ⇒ ∃xP(x) ∧ ∃xQ(x) is a tautology

• Theorem 4 : Each of the following is a tautology

(p ∧ q) ⇒ p , (p ∧ q) ⇒ q

p ⇒ (p ∨ q) , q ⇒ (p ∨ q)

~p ⇒ (p ⇒ q) , ~(p ⇒ q) ⇒ p

(p ∧ (p ⇒ q)) ⇒ q , (~p ∧ (p ∨ q)) ⇒ q

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

((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r)

• Properties of Quantifiers ∃ and ∀

(a) ∃ x (P(x) V Q(x)) ≡ ∃x P(x) V ∃x (Q(x))

(b) ∀ x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∀x Q(x)