Rachunek kwantyfikatorów

[peterek]

Cześć, mam sprawdzić czy następujące zdanie jest tautologią.

\(\displaystyle{ \forall x \exists y \varphi(x,y) \Leftarrow \exists y \forall x \varphi(x,y)}\)

Z góry dzięki za pomoc.

[Piotr Rutkowski]

Tak jest tautologią. Jeśli \(\displaystyle{ (\exists_{y}\forall_{x} \ \varphi(x,y)=1) \Rightarrow (\forall_{x} \ \varphi(x,y_{1})=1) \Rightarrow (\forall_{x}\exists_{y} \ \varphi(x,y)=1)}\)

[peterek]

Mam pytanie, czy da się to jakoś dokładniej pokazać? Generalnie nie wiem co tutaj zaszło (skąd ten \(\displaystyle{ y_1}\)).

[Jan Kraszewski]

Chodzi o to, że zakładasz prawdziwość \(\displaystyle{ \exists y \forall x \varphi(x,y)}\). Oznacza to, że istnieje \(\displaystyle{ y_1}\), dla którego prawdziwe jest zdanie \(\displaystyle{ \forall x \varphi(x,y_1)}\). Ale wtedy dla każdego \(\displaystyle{ x}\) istnieje \(\displaystyle{ y}\) takie, że zachodzi \(\displaystyle{ \varphi(x,y)}\) - jest to za każdym razem wskazane \(\displaystyle{ y_1}\). Oznacza to, że prawdziwe jest zdanie \(\displaystyle{ \forall x \exists y \varphi(x,y)}\), a to chciałeś uzasadnić.

JK

[peterek]

Dziękuję bardzo

[max89]

Witam,
O ile dobrze wyczytałem to powyższy przykład tautologii pochodzi z prawa przemienności dla kwantyfikatorów tego samego rodzaju, ale nie jest tautologią gdy odwrócimy implikację. Starałem się dla takiego przypadku znaleźć jakiś kontrprzykład lecz niestety nic mi nie przychodzi do głowy. Zatem mam pytanie czy można to jakoś, w łatwy sposób objaśnić?

[nne]

\(\displaystyle{ \varphi(x,y) =:}\) czytelnik \(\displaystyle{ x}\) książki uważa zdanie \(\displaystyle{ y}\) tej książki za trywialne.

\(\displaystyle{ \{x_1, x_2\}}\) to jest przykładowy zbiór czytelników, a to \(\displaystyle{ \{y_1, y_2\}}\) przykładowy zbiór zdań w tej książce.

Załóżmy, że czytelnik \(\displaystyle{ x_1}\) uważa \(\displaystyle{ y_1}\) za trywialne. Czytelnik \(\displaystyle{ x_2}\) uważa \(\displaystyle{ y_2}\) za trywialne. Wtedy zdanie \(\displaystyle{ \forall x \exists y \varphi(x,y)}\) jest prawdziwe. Natomiast zdanie \(\displaystyle{ \exists y \forall x \varphi(x,y)}\) już nie jest prawdziwe, bo nie istnieje jedno takie zdanie, które będzie trywialne dla dwóch czytelników.

[Msciwoj]

Dobry kontrprzykład to definicja Cauchy'ego ciągłości i ciągłości jednostajnej na całym przedziale otwartym. Wtedy dochodzą jeszcze dwa kwantyfikatory, ale one są w tych samych miejscach, więc można się nimi nie przejmować.

I wtedy z ciągłości jednostajnej wynika ciągłość, a z ciągłości nie wynika ciągłość jednostajna.

[yorgin]

A może prościej takie zdanie?

\(\displaystyle{ \forall\ x\in \NN\ \ \exists \ y\in \NN \ \ y>x}\)

Wszak po co brać skomplikowane definicje?

[max89]

Wielkie dzięki, już powoli to rozumiem. Idąc tym samym tropem myślenia zrobiłem własny kontrprzykład:

\(\displaystyle{ \varphi(x,y)=:}\) pracownik x dostaje premię y (obojętnie jaka, w zależności jak na nią zapracował)

\(\displaystyle{ \{x_1,x_2\}}\) - przykładowy zbiór pracowników, a \(\displaystyle{ \{y_1,y_2\}}\) - przykładowy zbiór premii.

Zakładając, że pracownik \(\displaystyle{ x_1}\) otrzymuje premie \(\displaystyle{ y_1}\) oraz że pracownik \(\displaystyle{ x_2}\) otrzymuje premie \(\displaystyle{ y_2}\). Wtedy pierwsze zdanie jest prawdziwe, a drugie już nie ponieważ nie istnieje jedna taka premia, którą otrzyma dwóch pracowników. (Złamałoby to zasadę logiki oraz zasadę dobrych manier pracodawcy ).

Czy taki kontrprzykład jest poprawny?