Which formula is NOT equivalent to x( y\, z\,)?

$\forall x(\exists z(\neg\beta)\to\forall y(\alpha))$

$\forall x(\forall z(\beta)\to\exists y(\neg\alpha))$

$\forall x(\forall y(\alpha)\to\exists z(\neg\beta))$

$\forall x(\exists y(\neg\alpha)\to\exists z(\neg\beta))$

GATE 2013 CS (CS1) – Question 57

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · MTA

Which formula is NOT equivalent to $\neg\exists x(\forall y\,\alpha\land\forall z\,\beta)$?

$\forall x(\exists z(\neg\beta)\to\forall y(\alpha))$
$\forall x(\forall z(\beta)\to\exists y(\neg\alpha))$
$\forall x(\forall y(\alpha)\to\exists z(\neg\beta))$
$\forall x(\exists y(\neg\alpha)\to\exists z(\neg\beta))$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: MTA

Explanation

The final official key gives marks to all. Pushing the outer negation inward gives ∀x(∃y¬α ∨ ∃z¬β), equivalent to implications in B and C under the usual variable conditions. Write P=∀yα and Q=∀zβ. A simplifies to P∨Q and D to P∨¬Q, neither generally equal to ¬P∨¬Q. Thus both A and D can fail equivalence, leaving more than one exclusion. Preserve universal credit.

More Discrete Mathematics: Propositional and First Order Logic questions

GATE 2011 CS (CS1) Q40 – For positive integers x,y,z, define P(x)=(x=1) y[( z(x=yz))((y=x)(y=1))]. Which is…
GATE 2010 CS (CS1) Q40 – Let F(x,y,t) mean that x can fool y at time t. What does x\, y\, t\, F(x,y,t) express?
GATE 2015 CS (CS2) Q11 – S1: If a candidate is known to be corrupt, he will not be elected. S2: If a candidate is…
GATE 2015 CS (CS2) Q63 – Which first-order formula is logically valid?
GATE 2015 CS (CS3) Q26 – A room contains truth-tellers and liars. An unknown person tosses a fair coin unseen and…
GATE 2021 CS (CS2) Q25 – For S:((P Q) R)((P Q)(Q R)), choose the correct statements.

All Discrete Mathematics: Propositional and First Order Logic questions →