Answer:
See deductions below
Step-by-step explanation:
1)
a) p(y)∧q(y) for some y (Existencial instantiation to H1)
b) q(y) for some y (Simplification of a))
c) q(y) → r(y) for all y (Universal instatiation to H2)
d) r(y) for some y (Modus Ponens using b and c)
e) p(y) for some y (Simplification of a)
f) p(y)∧r(y) for some y (Conjunction of d) and e))
g) ∃x (p(x) ∧ r(x)) (Existencial generalization of f)
2)
a) ¬C(x) → ¬A(x) for all x (Universal instatiation of H1)
b) A(x) for some x (Existencial instatiation of H3)
c) ¬(¬C(x)) for some x (Modus Tollens using a and b)
d) C(x) for some x (Double negation of c)
e) A(x) → ∀y B(y) for all x (Universal instantiation of H2)
f) ∀y B(y) (Modus ponens using b and e)
g) B(y) for all y (Universal instantiation of f)
h) B(x)∧C(x) for some x (Conjunction of g and d, selecting y=x on g)
i) ∃x (B(x) ∧ C(x)) (Existencial generalization of h)
3) We will prove that this formula leads to a contradiction.
a) ∀y (P (x, y) ↔ ¬P (y, y)) for some x (Existencial instatiation of hypothesis)
b) P (x, y) ↔ ¬P (y, y) for some x, and for all y (Universal instantiation of a)
c) P (x, x) ↔ ¬P (x, x) (Take y=x in b)
But c) is a contradiction (for example, using truth tables). Hence the formula is not satisfiable.
