Intro to Logic I - Extra Exercises Sheet 06

Logic I: Extra Exercises Sheet 06 [email protected]

6 More proofs with quantifiers For each of the following, prove if valid or give a counter example if not. 1.

6.

F(a) ∧ ¬F(b) ¬∀x∀y(x = y)

2.

∀xF(x) ∧ ∀xG(x) 7.

∀x(F(x) → G(x))

8. ∀x(F(x) → G(x))

∃x(F(x) ∧ G(x)) ∃xF(x) ∧ ∃xG(x)

∀xF(x) → ∃xG(x)

9.

∃x(F(x) ∨ G(x)) ∃xF(x) ∨ ∃xG(x)

4. 10.

¬∃x¬F(x) ↔ ∀xF(x) 5.

∀x(F(x) ∨ G(x)) ∀xF(x) ∨ ∀xG(x)

∀xF(x) → ∀xG(x) 3.

∀x(F(x) ∧ G(x))

∀x(S(x) → C(x)) ∃x¬C(x) → ∃xS(x)

∀x∀y((R(x) ∧ A(x, y)) → R(y)) ∀x∀y∀z((A(x, y) ∧ A(y, z)) → A(x, z)) ∀x∀y(A(x, y) → x ̸= y) R(a) ∃x(A(a, x))

∃xC(x)

∃x∃y(x ̸= y ∧ R(x) ∧ R(y))

1