Which of the following is the negation of [∀ x, α → (∃y, β → (∀ u, ∃v, y))]
2008
Which of the following is the negation of [∀ x, α → (∃y, β → (∀ u, ∃v, y))]
- A.
[∃ x, α → (∀y, β → (∃u, ∀ v, y))]
- B.
[∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))]
- C.
[∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))]
- D.
[∃ x, α ʌ (∀y, β ʌ (∃u, ∀ v, ¬y))]
Attempted by 66 students.
Show answer & explanation
Correct answer: D
Negation of the formula ∀x (α → (∃y (β → (∀u ∃v y)))):
Step 1: Move the outer negation inside the universal: ¬∀x φ ≡ ∃x ¬φ. So we get ∃x ¬(α → ∃y (β → ∀u ∃v y)).
Step 2: Negate the implication using ¬(P → Q) ≡ P ∧ ¬Q: ¬(α → ...) ≡ α ∧ ¬(∃y (β → ∀u ∃v y)).
Step 3: Move negation through the existential: ¬∃y ψ ≡ ∀y ¬ψ. This yields α ∧ ∀y ¬(β → ∀u ∃v y).
Step 4: Negate the inner implication: ¬(β → ψ) ≡ β ∧ ¬ψ. So we have α ∧ ∀y (β ∧ ¬(∀u ∃v y)).
Step 5: Move negation through ∀ and ∃: ¬∀u ∃v y ≡ ∃u ¬∃v y ≡ ∃u ∀v ¬y. Substitute to get α ∧ ∀y (β ∧ ∃u ∀v ¬y).
Final negation: ∃x (α ∧ ∀y (β ∧ ∃u ∀v ¬y))
This matches the formula written as [∃ x, α ʌ (∀y, β ʌ (∃u, ∀ v, ¬y))].