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
