Question

1. Consider the following hypotheses:

Answer 1

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.