Let p and q be two propositions. Consider the following two formulae in propositional logic:S1: (NOT p AND (p OR q)) --> qS2: q --> (NOT p AND (p OR q))Which one of the following choices is correct?

Correct Answer: (B) S1 is a tautology but S2 is not.Concept -- Propositional Logic Tautologies: Simplify S1: The antecedent NOT p AND (p OR q). By distribution: (NOT p AND p) OR (NOT p AND q) = FALSE OR (NOT p AND q) = NOT p AND q. So S1 becomes (NOT p AND q) --> q. Whenever the antecedent (NOT p AND q) is true, q must be true (it is a conjunct). So S1 is always true -- it is a tautology.Check S2: q --> (NOT p AND (p OR q)). Take p = TRUE, q = TRUE. Then NOT p = FALSE, (p OR q) = TRUE, NOT p AND (p OR q) = FALSE. So S2 becomes TRUE --> FALSE = FALSE. Since S2 is false for some truth assignment, it is not a tautology.

GATE-CS is a competitive examination conducted in India. This question is from the 2021 GATE-CS Discrete Mathematics paper.

How can I prepare for GATE-CS Discrete Mathematics?

To prepare for GATE-CS Discrete Mathematics, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2021 question covers Propositional and First-Order Logic topic.

What is the difficulty level of this question?

This GATE-CS 2021 Discrete Mathematics question has a medium difficulty level and is marked as an important question.

Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

GATE-CS Discrete Mathematics 2021 - Let p and q be two...

For two different persons x and y, the predicate M(x, y) denotes that x knows y. Consider the follow…

MEDIUM2026GATE-CSDiscrete Mathematics

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the stat…

HARD2025GATE-CSDiscrete Mathematics

Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following st…

MEDIUM2025GATE-CSDiscrete Mathematics

Let p and q be the following propositions: p: Fail grade can be given. q: Student scores more than 5…

EASY2024GATE-CSDiscrete Mathematics

Geetha has a conjecture: for all x, P(x) implies there exists y such that Q(x,y). Which of the follo…

HARD2023GATE-CSDiscrete Mathematics

Choose the correct choice(s) regarding the following propositional logic assertion S:S: ((P implies …

HARD2021GATE-CSDiscrete Mathematics

Let p and q be two propositions. Consider the following two formulae in propositional logic:S1: (NOT p AND (p OR q)) --> qS2: q --> (NOT p AND (p OR q))Which one of the following choices is correct?

Master GATE-CS with Our Test Series

More Questions from Propositional and First-Order Logic

Frequently Asked Questions

Let p and q be two propositions. Consider the following two formulae in propositional logic:S1: (NOT p AND (p OR q)) --> qS2: q --> (NOT p AND (p OR q))Which one of the following choices is correct?

Master GATE-CS with Our Test Series

More Questions from Propositional and First-Order Logic

Frequently Asked Questions