Home › Previous year questions › GATE 2021 CS (CS1) › Question 17GATE 2021 CS (CS1) – Question 17 Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 1 mark · Multiple choice
Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic. $S_1$: $(\neg p \wedge (p \vee q)) \rightarrow q$ $S_2$: $q \rightarrow (\neg p \wedge (p \vee q))$ Which one of the following choices is correct?
Both $S_1$ and $S_2$ are tautologies. $S_1$ is a tautology but $S_2$ is not a tautology. $S_1$ is not a tautology but $S_2$ is a tautology. Neither $S_1$ nor $S_2$ is a tautology. Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (B) $S_1$ is a tautology but $S_2$ is not a tautology.
Explanation $\neg p \wedge (p\vee q) \equiv \neg p \wedge q$, which implies $q$, so $S_1$ is a tautology. $S_2$ fails when $p=q=1$.
More Discrete Mathematics: Propositional and First Order Logic questions GATE 2020 CS Q49 – Which one of the following predicate formulae is NOT logically valid? Note that W is a… 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… All Discrete Mathematics: Propositional and First Order Logic questions →