Let S be a binary predicate symbol, P and Q unary predicate symbols.
- Find a natural deduction proof to show
∃x∃y(S(x,y) ∨ S(y,x)) ` ∃x∃yS(x,y).
- 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)).
- Find a natural deduction proof to show
∃x∃y(S(x,y) ∨ S(y,x)),¬∃xS(x,x) ` ∃x∃y¬(x = y).
- Show that there is no natural deduction proof for ∀x(P(x) ∨ Q(x)) ` ∀xP(x) ∨ ∀xQ(x).
- Semantically show
∀x¬φ |= ¬∃xφ.
1
