Question

1. Consider the following hypotheses:

H1 : ∃x (p(x) ∧ q(x)) H2 : ∀x (q(x) → r(x))
Use rules of inference to prove that the following conclusion follows from these hypotheses:
C : ∃x (p(x) ∧ r(x))
Clearly label the inference rules used at every step of your proof.

2. Consider the following hypotheses:
H1 : ∀x (¬C(x) → ¬A(x)) H2 : ∀x (A(x) → ∀y B(y)) H3 : ∃x A(x)
Use rules of inference to prove that the following conclusion follows from these hypotheses:
C : ∃x (B(x) ∧ C(x))
Clearly label the inference rules used at every step of your proof.

3. Consider the following predicate quantified formula:
∃x ∀y (P (x, y) ↔ ¬P (y, y))
Prove the unsatisfiability of this formula using rules of inference.

Answer 1

See deductions below

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.