Show that $F$ is a Tautology using equivalence transformations

60 Views Asked by At

I want to show that

$((\lnot \forall v_0 Q v_0 \land \forall v_0 (\lnot Q v_0 \to P v_0)\land \forall v_0(Qv_0 \leftrightarrow \lnot Rv_0)) \to \exists v_0(Rv_0 \land P v_0))$

is a tautology using equivalence transformations. Now, I have tried so many different approaches with different rules, but I never got the formula simplified to such extent that it was obvious that it is a tautology, so I thought I might miss a crucial point and simple equivalence transformations are not enough. Maybe someone can lead me to the right idea.

1

There are 1 best solutions below

3
On BEST ANSWER

\begin{align}&\lnot \forall x Q x \land \forall x (\lnot Q x \to P x)\land \forall x(Qx \leftrightarrow \lnot Rx)\\\equiv &\lnot \forall x Q x \land \forall x (Q x \lor P x)\land \forall x\Big((\lnot Qx\lor \lnot Rx) \land (Qx \lor Rx)\Big)\\\equiv &\lnot \forall x Q x \land \forall x \Big( (Q x \lor P x)\land (\lnot Qx\lor \lnot Rx) \land (Qx \lor Rx)\Big)\\\equiv &\lnot \forall x Q x \land \forall x \Big( \big(Q x \lor (P x \land Rx)\big)\land (\lnot Qx\lor \lnot Rx) \Big)\\\equiv &\lnot\forall x Q x \land \forall x \Big( Q x \lor (P x \land Rx)\Big)\land \forall x (\lnot Qx\lor \lnot Rx) \\\models &\exists x \lnot Q x \land \forall x \Big( Q x \lor (P x \land Rx)\Big)\\\models &\exists x(Rx \land P x)\end{align}

P.S. I believe that the given sentence's validity cannot be shown using just equivalence transformations.