GATE CSE 2015 Set 2 | Question: 55

Question

Which one of the following  well-formed formulae is a tautology?
 

• A. $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$
• B. $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$
• C. $[ \forall x \, \exists y \, \left( P(x,y) \, \rightarrow \, R(x, y) \right)] \, \leftrightarrow [ \forall x \, \exists y \left(\neg P(x, y) \, \lor R(x, y) \right)]$
• D. $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$

Comments

Ignoring the variables, $(R \rightarrow S) \rightarrow S$ cannot be a tautology.

So, even if we use quantifiers and variables, it cannot be a tautology.

---

[deleted]

---

@strawberry-jam I too believe that cause (R->S) -> S

LHS can be ~R + S ->S 

if R = False and S = False

then ~R +S will be True  → S will be false.

 

Answer 1

The correct option is C

[∀x∃y(P(x,y)→R(x,y))]↔[∀x∃y(⇁P(x,y)∨R(x,y))]

Since P→R≡⇁P∨R. and the quantifiers on both the sides are same (∀x∃y).

Option (c) is clearly a tautology.