Basic First Order Logic Question

141 Views Asked by At

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

(A) $\forall x\exists yR(x,y)\iff\exists y\forall xR(x,y)$

(B) $[(\forall x\exists y(p(x,y)\Rightarrow R(x,y))]\Rightarrow [\forall x\exists y(\lnot p(x,y) \lor R(x,y))]$

(C) $\forall x\forall yp(x,y)\Rightarrow \forall y\forall xp(y,x)$

The answer is B, but can't we do these type of questions in an efficient way so as to save time in exam like some truth table method or something else.

1

There are 1 best solutions below

2
On BEST ANSWER

You can probably save time if you turn these logic statements into a concrete example. So for $A$, something like letting $x$ be shirts, $y$ be pants and $R(x,y)$ means the combination of $x$ and $y$ looks $\textbf{R}$eally good. Then we can think of $A$ as comparing the two statements:

For every shirt there exists a pair of pants that look really good.

There exists a pair of pants that can be paired with any shirt to look really good.

These statements convey different ideas. The first statement tells us that we can find a pair of pants to go with any shirt. The second statement tells us that there is a magical pair of pants that looks good with every possible shirt. This isn't rigorous obviously, but it is this kind of reasoning that you could use on an exam to deduce that $A$ is not a tautology.

For $B$, it's a matter of using the tautology $X \implies Y \equiv \neg X \vee Y $. So seeing that $B$ is a tautology comes from plugging in $\neg p(x,y)\vee R(x,y)$ in place of the logically equivalent $p(x,y)\implies R(x,y)$.

For $C$, see if you can create two statements like I did for $A$ to convince yourself that it is/isn't a tautology.