Let a(x, y), b(x, y,) and c(x, y) be three statements with variables x and y…
2004
Let a(x, y), b(x, y,) and c(x, y) be three statements with variables x and y chosen from some universe. Consider the following statement:
(∃x)(∀y)[(a(x, y) ∧ b(x, y)) ∧ ¬c(x, y)] Which one of the following is its equivalent?
- A.
(∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)]
- B.
(∃x)(∀y)[(a(x, y) ∨ b(x, y)) ∧¬ c(x, y)]
- C.
¬ (∀x)(∃y)[(a(x, y) ∧ b(x, y)) → c(x, y)]
- D.
¬ (∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)]
Attempted by 55 students.
Show answer & explanation
Correct answer: C
Answer: ¬(∀x)(∃y)[(a(x, y) ∧ b(x, y)) → c(x, y)].
Reason: Transform the original formula step by step.
Start with: ∃x ∀y [(a(x,y) ∧ b(x,y)) ∧ ¬c(x,y)].
Use the quantifier equivalence ∃x ∀y P(x,y) ≡ ¬∀x ∃y ¬P(x,y). Applying it with P = (a ∧ b) ∧ ¬c gives: ¬(∀x)(∃y) ¬[(a(x,y) ∧ b(x,y)) ∧ ¬c(x,y)].
Simplify the inner negation: ¬[(a ∧ b) ∧ ¬c] = ¬(a ∧ b) ∨ c, and ¬(a ∧ b) ∨ c is logically equivalent to (a ∧ b) → c.
Therefore the original formula is equivalent to: ¬(∀x)(∃y)[(a(x,y) ∧ b(x,y)) → c(x,y)].