tautologia - kwantyfikatory

[mc_piter]

Witam, ostatnio na dyskretnej robiliśmy takie zadanie(chodzi chyba o zbadanie czy zdanie jest tautologią):

\(\displaystyle{ (\forall_{y}
\exists_{x}
: p(x,y))
\Rightarrow
(\exists_{x}
\forall_{y}
:p(x,y))}\)
Zakładamy więc , że nieprawda,
wtedy:
\(\displaystyle{ \forall_{y}
\exists_{x=x_{y}}: p(x_{y},y)=1}\)

\(\displaystyle{ \forall_{x}
\exists_{y=y_x}: p(x,y_{x})=0}\)

(1)

Z tego otrzymał dla pierwszego:
\(\displaystyle{ y=x , p(y,y)=1}\)
dla drugiego
\(\displaystyle{ y=x+2, p(x,x+2)=0}\)

i z tego na koncu nasz szanowny cwiczeniowiec otrzymał

\(\displaystyle{ p(x,y)= \left\{\begin{array}{l}1 , x=y\\0, y=x+2\\0, dla\ innych\ x,y \end{array}\right.}\)
i otóż teraz mam prośbę do Was:
czy mógłby ktoś mi wytłumaczyć co się dzieje w tym zadaniu od momentu oznaczonego (1)? jak szanowny cwiczeniowiec znalazł wartości dla których p(x) jest fałszywa / prawdziwa.
z góry dzięki!

[Jan Kraszewski]

Mogę domyślać się fragmentarycznych wniosków, ale jak dla mnie całość nie ma większego sensu.

JK

[mc_piter]

Po chwili namysłu nasunęła mi się pewna myśl ( poprawcie mnie jak co) .
\(\displaystyle{ \forall_{y} \exists_{x =x_y}: p(x_{y},y)=1

\forall_{x} \exists_{y=y_x}: p(x,y_{x})=0}\)

czyli istnieje tylko 1 prawdziwa funkcja dla tych warunków jeżeli określimy Universum jako N. Dla każdego y należącego do kodziedziny istnieje x należący do dziedziny co spełnia tylko funkcja y=x (spełnia również 2 podpunkt) I wydaje mi się iż jest to kontrprzykład i zdanie to jest tautologią.

[Jan Kraszewski]

Przykro mi, ale to też nie ma sensu.

A tak na marginesie - to zdanie jest tautologią.

JK

[mc_piter]

a tak, racja dzięki . mój błąd.

[Jan Kraszewski]

To niestety niewiele poprawia.

Dla każdego y należącego do kodziedziny istnieje x należący do dziedziny co spełnia tylko funkcja y=x .

A skąd ten wniosek? Przecież po pierwsze nic nie wiesz o formule \(\displaystyle{ p}\), a po drugie tam są inne kwantyfikatory.

Gdybyś chciał koniecznie rozumować nie wprost, to pierwszy warunek zapewnia istnienie \(\displaystyle{ y_0}\) takiego, że zdanie \(\displaystyle{ p(x,y_0)}\) dla każdego \(\displaystyle{ x}\). Ponieważ drugi warunek zapewnia istnienie takiego \(\displaystyle{ x_0}\), że zdanie \(\displaystyle{ p(x_0,y)}\) jest fałszywe dla każdego \(\displaystyle{ y}\), więc w szczególności fałszywe jest zdanie \(\displaystyle{ p(x_0,y_0)}\). Ale to stoi w sprzeczności z pierwszym spostrzeżeniem.

JK

[mc_piter]

tak.... pomieszałem wszystko. Pomyłka wynikła iż myślałem ze te 2 kwantyfikatory to to samo....

\(\displaystyle{ \vee \\ \forall}\)

sorry....

[Jan Kraszewski]

No fakt, namieszałeś.

Tyle, że teraz musisz pokazać, że to zdanie nie jest tautologią (bo nie jest), czyli wskazać konkretną formułę \(\displaystyle{ p(x,y)}\), dla której to zdanie nie jest prawdziwe. A niczego takiego w Twoim rozumowaniu nie widzę (tzn. nie widzę tej formuły).

JK