Question

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

• A. $\forall x\exists yR(x,y)\leftrightarrow \exists y\forall xR(x,y)$
• B. $\left(\forall x[\exists yR(x,y)\to S(x,y)]\right)\to \forall x\exists yS(x,y)$
• C. $\left[\forall x\exists y(P(x,y)\to R(x,y))\right]\leftrightarrow \left[\forall x\exists y(\rightharpoondown P(x,y)\vee R(x,y))\right]$
• D. $\forall x\forall yP(x,y)\to \forall x\forall yP(y,x)$

Answer 1

The correct option is C

$\left[\forall x\exists y(P(x,y)\to R(x,y))\right]\leftrightarrow \left[\forall x\exists y(\rightharpoondown P(x,y)\vee R(x,y))\right]$

Since $P\to R\equiv \rightharpoondown P\vee R$. and the quantifiers on both the sides are same $\left(\forall x\exists y\right)$.

Option (c) is clearly a tautology.