GATE DA 2024 Set 1 — Question 29
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MSQ+1 / -0MediumLogical ConnectivesPropositional LogicArtificial IntelligenceLogical Equivalence
Artificial Intelligence → Propositional Logic → Logical Connectives
Last updated
Question
Let and be two propositions. Which of the following statements is a tautology /are tautologies?
Correct answer
(B) (x ∧ ¬ y) ⇒ (¬ x ⇒ y); (C) (¬ x ∧ y) ⇒ (¬ x ⇒ y); (D) (x ∧ ¬ y) ⇒ (y ⇒ x)
Solution
A statement is a tautology if it is true for all possible truth values of its variables.(A)
Consider the case where is False and is True.
LHS:
RHS:
Overall: . Not a tautology.(B)
LHS is True only when .
In this case, RHS is .
Since the implication is True when the antecedent is True (and trivially True otherwise), this is a tautology.(C)
LHS is True only when .
In this case, RHS is .
This is a tautology.(D)
LHS is True only when .
In this case, RHS is .
This is a tautology.Therefore, options (B), (C), and (D) are correct.
Consider the case where is False and is True.
LHS:
RHS:
Overall: . Not a tautology.(B)
LHS is True only when .
In this case, RHS is .
Since the implication is True when the antecedent is True (and trivially True otherwise), this is a tautology.(C)
LHS is True only when .
In this case, RHS is .
This is a tautology.(D)
LHS is True only when .
In this case, RHS is .
This is a tautology.Therefore, options (B), (C), and (D) are correct.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE DA question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Propositional Logic
2026 Set 1 Q13Which of the following algorithms is NOT an example of uninformed search?2026 Set 1 Q14Which of the following statements is NOT true? (The names of the predicates are intuitive.)2026 Set 1 Q23In the following table, the
Task column lists a few tasks related to machine learning. The…2026 Set 1 Q24Sentence is said to entail Sentence if whenever is TRUE, also must hold TRUE. Which…2026 Set 1 Q30Consider the game tree for a two-player turn-taking minimax game as shown in the figure. The value…