Which one of the following well-formed formulae in predicate calculus is NOT…
2016
Which one of the following well-formed formulae in predicate calculus is NOT valid?
- A.
\((∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x¬p(x) ∨ ∀x q(x))\) - B.
\((∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x))\) - C.
\(∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))\) - D.
\(∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))\)
Attempted by 65 students.
Show answer & explanation
Correct answer: D
Key point: the formula ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x)) is not valid.
Counterexample:
Domain = {a, b}.
Set p true only for a (p(a) true, p(b) false) and q true only for b (q(a) false, q(b) true).
Then for each x in the domain p(x) ∨ q(x) holds, so ∀x (p(x) ∨ q(x)) is true.
But neither ∀x p(x) nor ∀x q(x) holds, so (∀x p(x) ∨ ∀x q(x)) is false. Therefore the implication fails in this model.
Conclusion: The distributive-style move from a universal quantifier over a disjunction to a disjunction of universals is not generally valid; the given formula is not valid.
A video solution is available for this question — log in and enroll to watch it.