COMPUTATIONAL LOGIC-Homework 3 Solved

Let S be a binary predicate symbol, P and Q unary predicate symbols.

(1)   Find a natural deduction proof to show

∃x∃y(S(x,y) ∨ S(y,x)) ` ∃x∃yS(x,y).

(2)   Find a natural deduction proof to show

∀x∀y∀z(S(x,y)∧S(y,z) =⇒ S(x,z)),∀x¬S(x,x) ` ∀x∀y(S(x,y) =⇒ ¬S(y,x)).

(3)   Find a natural deduction proof to show

∃x∃y(S(x,y) ∨ S(y,x)),¬∃xS(x,x) ` ∃x∃y¬(x = y).

(4)   Show that there is no natural deduction proof for ∀x(P(x) ∨ Q(x)) ` ∀xP(x) ∨ ∀xQ(x).

(5)   Semantically show

∀x¬φ |= ¬∃xφ.

1