Tautologia rachunku predykatów

[Sylakenth]

Witam, nigdzie nie mogłem znaleźć dobrej odpowiedzi na podany problem. Bardzo bym prosił o sprawdzenie mojego toku rozumowania.
Zad. Sprawdzić czy formuła jest tautologią
\(\displaystyle{ \exists x(Q(x) \Rightarrow P(x)) \Rightarrow \forall x(P(x) \Rightarrow \exists xQ(x))}\)

Aby formuła była fałszywa to pierwsza część implikacji musi być prawdziwa a druga fałszywa. Aby druga część była fałszywa to musi zajść: \(\displaystyle{ \forall x P(x)}\) i \(\displaystyle{ \forall x \neg Q(x)}\) i z tego wynika, że całe zdanie jest fałszywe. Można przyjąć \(\displaystyle{ Q(x) \Leftrightarrow x \neq x}\) a \(\displaystyle{ P(x) \Leftrightarrow x=x}\)

[Valki]

Aby formuła była fałszywa to pierwsza część implikacji musi być prawdziwa a druga fałszywa. Aby druga część była fałszywa to musi zajść: \(\displaystyle{ \forall x P(x)}\) i \(\displaystyle{ \forall x \neg Q(x)}\)

Zgadza się. Jeśli \(\displaystyle{ \forall x P(x)}\) i \(\displaystyle{ \forall x \neg Q(x)}\), to \(\displaystyle{ \forall x \left( Q(x) \Rightarrow P(x)\right)}\), z czego wynika, że \(\displaystyle{ \exists x \left( Q(x) \Rightarrow P(x)\right)}\), czyli lewa strona implikacji jest prawdziwa, a prawa fałszywa. Formuła byłaby tautologią, gdyby z założenia o fałszywości prawej strony implikacji wynikała fałszywość lewej - wtedy cała implikacja nie mogłaby być fałszywa.

EDYCJA Powyższy akapit należy czytać od "lewa strona implikacji...", wcześniejsza jego część była pisana przy przeoczeniu kwantyfikatora [patrz post niżej], sorry, późno było.

[norwimaj]

Aby druga część była fałszywa to musi zajść: \(\displaystyle{ \forall x P(x)}\) i \(\displaystyle{ \forall x \neg Q(x)}\)

Niezupełnie. Fałszywość następnika oznacza tyle, że \(\displaystyle{ \exists x \neg(P(x) \Rightarrow \exists xQ(x))}\), czyli przed \(\displaystyle{ P(x)}\) masz zły kwantyfikator.

Można przyjąć \(\displaystyle{ Q(x) \Leftrightarrow x \neq x}\) a \(\displaystyle{ P(x) \Leftrightarrow x=x}\)

To jest wystarczające uzasadnienie, a jak do niego dochodziłeś, tego nie musisz w rozwiązaniu pisać.