GATE 2016 CS (CS2) – Question 37

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

Which predicate-calculus formula is NOT valid?

$(\forall x\,p(x)\Rightarrow\forall x\,q(x))\Rightarrow(\exists x\,\neg p(x)\lor\forall x\,q(x))$
$(\exists x\,p(x)\lor\exists x\,q(x))\Rightarrow\exists x(p(x)\lor q(x))$
$\exists x(p(x)\land q(x))\Rightarrow(\exists x\,p(x)\land\exists x\,q(x))$
$\forall x(p(x)\lor q(x))\Rightarrow(\forall x\,p(x)\lor\forall x\,q(x))$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\forall x(p(x)\lor q(x))\Rightarrow(\forall x\,p(x)\lor\forall x\,q(x))$

Explanation

Universal quantification does not distribute over disjunction. On domain {a,b}, let p hold only at a and q only at b. Then p(x)∨q(x) holds everywhere, but neither predicate holds everywhere. Thus D fails. A uses $\neg\forall p=\exists\neg p$; B and C follow from existential witnesses.

More Discrete Mathematics: Propositional and First Order Logic questions

GATE 2017 CS (CS2) Q21 – Let p,q,r mean “It is raining”, “It is cold”, “It is pleasant”. Represent: “It is not…
GATE 2012 CS (CS1) Q11 – I₁: If it rains, the cricket match will not be played; the match was played; infer no…
GATE 2012 CS (CS1) Q23 – Translate “Some real numbers are rational” into logic.
GATE 2013 CS (CS1) Q37 – With F(x)=“x is my friend” and P(x)=“x is perfect”, translate “None of my friends are…
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?

All Discrete Mathematics: Propositional and First Order Logic questions →