Sprawdź czy podane wyrażenie jest tautologią (kwantyfikatory)

[ColumbusTheBox]

Witam.
Mam takie zadanie ażeby sprawdzić czy wyrażenie jest tautologią.
Mój znajomy rozwiązał to w ten sposób, jednak nie jestem pewien czy jest to zrobione prawidłowo, mianowicie samemu wyszło mi coś innego.
Dlatego chciałbym prosić o weryfikację tego rozwiązania.

\(\displaystyle{ [ \forall x (p(x)) \implies \forall x (q(x)) ] \implies [ \forall x(p(x) \implies q(x))]}\)

"dowód nie wprost przez kontrapozycję"

Niech \(\displaystyle{ \forall x(p(x) \implies q(x))}\) jest fałszywe
Wtedy \(\displaystyle{ \exists x \neg (p(x) \implies q(x))}\)
Czyli jest \(\displaystyle{ \exists x (p(x) \wedge \neg q(x))}\)

Czyli jest taki x, że p(x) prawdziwe i q(x) nieprawdziwe.
Zatem \(\displaystyle{ \forall x (p(x)) \implies \forall x (q(x)) }\) nie jest prawdziwe

Czyli całość jest tautologią.

[a4karo]

Czyli jest taki x, że p(x) prawdziwe i q(x) nieprawdziwe.
Zatem \(\displaystyle{ \forall x (p(x)) \implies \forall x (q(x)) }\) nie jest prawdziwe

Czyli całość jest tautologią.

To za mało, żeby wyciągnąć taki wniosek.

[Jan Kraszewski]

Czyli jest taki x, że p(x) prawdziwe i q(x) nieprawdziwe.
Zatem \(\displaystyle{ \forall x (p(x)) \implies \forall x (q(x)) }\) nie jest prawdziwe

Niby dlaczego?

To za mało, żeby wyciągnąć taki wniosek.

Tym bardziej, że to nie jest tautologia.

JK

[ColumbusTheBox]

Też mi coś nie pasuje tutaj.
Dowód przez kontrapozycję wygląda tak:
\(\displaystyle{
(p \implies q) \Leftrightarrow (\neg q \implies \neg p)
}\)

Zatem wychodzi coś takiego:

\(\displaystyle{
\exists x (p(x) \wedge \neg q(x)) \implies \neg [ \forall x (p(x)) \implies \forall x (q(x))]
}\)

Po przekształceniu:

\(\displaystyle{
\exists x (p(x) \wedge \neg q(x)) \implies [ \forall x (p(x)) \wedge \exists x \neg (q(x))]
}\)

Czyli mamy tak:
istnieje jakiś 'x', który jednocześnie ma właściwość 'p' i nie ma właściwości 'q'
=>
każdy x ma właściwość 'p' i jednocześnie istnieje x, który nie ma właściwości 'q'

To co widać na przekształceniu nie ma chyba za bardzo sensu, sam fakt istnienia jakiegoś x który ma właściwość 'p' i nie ma właściwości 'q' nie implikuje przecież, że każdy x ma właściwość 'p', czy dobrze rozumuję?

Dodano po 16 minutach 26 sekundach:
EDIT:

Tym bardziej, że to nie jest tautologia.

JK

O proszę, czyli chyba dobrze myślałem, a próbowałem już z 2/3 godziny dojść do tego dlaczego wyszła mu (znajomemu) ta tautologia. Tym bardziej, że jego rozwiązanie potwierdził student starszego roku...

W każdym razie chciałbym jeszcze zapytać czy mój kontrprzykład jest prawidłowy?
\(\displaystyle{
x \in \NN\\
p(x) = x > 5\\
q(x) = x < 5}\)

\(\displaystyle{
[( \forall x \in \NN (x > 5) \implies \forall x \in \NN (x<5)] \implies \forall x \in \NN (x > 5 \implies x < 5)
}\)

W skrócie (jeżeli dobrze myślę) poprzednik będzie wyglądał tak [0 => 0] czyli będzie miał wartość PRAWDA.
Następnik z kolei będzie miał wartość FAŁSZ, gdyż chociaż by dla x = 6, implikacja
\(\displaystyle{
\forall x \in \NN (x > 5 \implies x < 5)
}\)
przyjmuje wartość fałsz, więc nie zachodzi dla każdego x.

Postać całego wyrażenia przyjmie formę [1 => 0] czyli jego wartością jest FAŁSZ.
Zatem całość nie jest tautologią.

[Jan Kraszewski]

W każdym razie chciałbym jeszcze zapytać czy mój kontrprzykład jest prawidłowy?

Tak.

JK

[ColumbusTheBox]

Dziękuję bardzo za całą pomoc.