Home › Previous year questions › GATE 2020 CS › Question 49GATE 2020 CS – Question 49 Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple choice
Which one of the following predicate formulae is NOT logically valid?
Note that $W$ is a predicate formula without any free occurrence of $x$.
$\forall x(p(x)\vee W)\equiv\forall x\,p(x)\vee W$ $\exists x(p(x)\wedge W)\equiv\exists x\,p(x)\wedge W$ $\forall x(p(x)\to W)\equiv\forall x\,p(x)\to W$ $\exists x(p(x)\to W)\equiv\forall x\,p(x)\to W$ Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (C) $\forall x(p(x)\to W)\equiv\forall x\,p(x)\to W$
Explanation Since $W$ has no free $x$, $\forall x(p\to W)\equiv\forall x\neg p\vee W$, which is not equivalent to $\forall x\,p\to W\equiv\exists x\neg p\vee W$. Options A, B and D are valid equivalences.
More Discrete Mathematics: Propositional and First Order Logic questions GATE 2019 CS Q45 – Consider the first order predicate formula : x[( z\ z x((z=x)(z=1))) w\,(w>x)( z\ z… GATE 2018 CS Q38 – Consider the first-order logic sentence s\, t\, u\, v\, w\, x\, y\ (s,t,u,v,w,x,y) where… GATE 2015 CS (CS1) Q19 – Which one of the following is NOT equivalent to p q? GATE 2016 CS (CS1) Q11 – Let p, q, r, s represent the following propositions. p: x \8, 9, 10, 11, 12\ q: x is a… GATE 2017 CS (CS1) Q11 – The statement ( p) ( q) is logically equivalent to which of the statements below? I. p q… GATE 2017 CS (CS1) Q12 – Consider the first-order logic sentence F: x( y R(x, y)). Assuming non-empty logical… All Discrete Mathematics: Propositional and First Order Logic questions →