Question

Prove the validity using laws of propositional logic and rules of inference:

∀x(P(x) → (Q(x) ∧ S(x)))

∃x(P(x) ∧ R(x))

− − − − − − − − − − − − −

∴ ∃x(R(x) ∧ S(x))

Answer 1

given

∀x(P(x) → (Q(x) ∧ S(x)))

∃x(P(x) ∧ R(x))

Step	Reason
1. ∃x(P(x) ∧ R(x))	Hypothesis
2. P(a) ^ R(a)	Existencial instantiation from (1)
3. P(a)	Simplification from (2)
4. ∀x(P(x) → (Q(x) ∧ S(x)))	Hypothesis
5. P(a) -> (Q(a) ^ S(a))	Universal instantiation from (4)
6. (Q(a) ^ S(a))	Modus ponens from (3) and (5)
7. R(a)	Simplification from (2)
8. R(a) ^ Q(a) ^ S(a)	Conjunction from (6) and (7)
9. ∃x(R(x) ∧ S(x))	Existential generalization from(8)