1

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.

kklaw
  • 301
  • 1
  • 9

1 Answers1

0

\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.

ryang
  • 38,879
  • 14
  • 81
  • 179
  • could you explain me the step from line 5 to 6? – kklaw Jan 05 '22 at 19:51
  • I meant, why do we have $\vDash$ suddenly? – kklaw Jan 05 '22 at 20:05
  • 1
    @kklaw Line 5 logically entails, but isn't logically equivalent to, Line 6. Similarly, Lines 6 to 7. Lines 1 to 7 means that $\Big[\lnot \forall x Q x \land \forall x (\lnot Q x \to P x)\land \forall x(Qx \leftrightarrow \lnot Rx)\Big]\to\Big[\exists x(Rx \land P x)\Big]$ is a validity (first-order tautology). – ryang Jan 05 '22 at 20:40