Question

Prove the formula that:

Answer 1

Step-by-step explanation:

Given: [∀x(L(x) → A(x))] →

[∀x(L(x) ∧ ∃y(L(y) ∧ H(x, y)) → ∃y(A(y) ∧ H(x, y)))]

To prove, we shall follow a proof by contradiction. We shall include the negation of the conclusion for

arguments. Since with just premise, deriving the conclusion is not possible, we have chosen this proof

technique.

Consider ∀x(L(x) → A(x)) ∧ ¬[∀x(L(x) ∧ ∃y(L(y) ∧ H(x, y)) → ∃y(A(y) ∧ H(x, y)))]

We need to show that the above expression is unsatisfiable (False).

¬[∀x(L(x) ∧ ∃y(L(y) ∧ H(x, y)) → ∃y(A(y) ∧ H(x, y)))]

∃x¬((L(x) ∧ ∃y(L(y) ∧ H(x, y))) → ∃y(A(y) ∧ H(x, y)))

∃x((L(x) ∧ ∃y(L(y) ∧ H(x, y))) ∧ ¬(∃y(A(y) ∧ H(x, y))))

E.I with respect to x,

(L(a) ∧ ∃y(L(y) ∧ H(a, y))) ∧ ¬(∃y(A(y) ∧ H(a, y))), for some a

(L(a) ∧ ∃y(L(y) ∧ H(a, y))) ∧ (∀y(¬A(y) ∧ ¬H(a, y)))

E.I with respect to y,

(L(a) ∧ (L(b) ∧ H(a, b))) ∧ (∀y(¬A(y) ∧ ¬H(a, y))), for some b

U.I with respect to y,

(L(a) ∧ (L(b) ∧ H(a, b)) ∧ (¬A(b) ∧ ¬H(a, b))), for any b

Since P ∧ Q is P, drop L(a) from the above expression.

(L(b) ∧ H(a, b)) ∧ (¬A(b) ∧ ¬H(a, b))), for any b

Apply distribution

(L(b) ∧ H(a, b) ∧ ¬A(b)) ∨ (L(b) ∧ H(a, b) ∧ ¬H(a, b))

Note: P ∧ ¬P is false. P ∧ f alse is P. Therefore, the above expression is simplified to

(L(b) ∧ H(a, b) ∧ ¬A(b))

U.I of ∀x(L(x) → A(x)) gives L(b) → A(b). The contrapositive of this is ¬A(b) → ¬L(b). Replace

¬A(b) in the above expression with ¬L(b). Thus, we get,

(L(b) ∧ H(a, b) ∧ ¬L(b)), this is again false.

This shows that our assumption that the conclusion is false is wrong. Therefore, the conclusion follows

from the premise.

15