178k views
1 vote
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.

1 Answer

0 votes

Answer:

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.

User Rajan Goswami
by
7.8k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.