\(\displaystyle{ \neg \left[ \bigvee\limits_{x: \alpha \left( x\right) } \beta \left( x\right) \right] \Leftrightarrow \bigwedge\limits_{x: \alpha \left( x\right) } \neg \beta \left( x\right);}\)
tzn. nie istnieje element \(\displaystyle{ x}\) spełniający \(\displaystyle{ \alpha \left( x\right)}\), dla którego zachodziłoby \(\displaystyle{ \beta \left( x\right)}\), to to oznacza, że każdy element \(\displaystyle{ x}\) spełniający \(\displaystyle{ \alpha \left( x\right)}\) nie spełnia \(\displaystyle{ \beta \left( x\right)}\). Przez pewną symetrię, zauważyłem, że te dwa zdania są równoważne temu, że każdy element \(\displaystyle{ x}\) spełniający \(\displaystyle{ \beta \left( x\right)}\) nie spełnia \(\displaystyle{ \alpha \left( x\right)}\), co wczoraj udowodniłem. Np. zdanie w zbiorze liczbach naturalnych: nie istnieje liczba parzysta będąca liczbą nieparzystą jest równoważne temu, że każda liczba nieparzysta nie jest liczbą parzystą. Przedstawię teraz dowód tego ciekawego faktu:
Niech \(\displaystyle{ \alpha \left( x\right) ;\beta \left( x\right)}\) będą formułami tej samej zmiennej \(\displaystyle{ x}\). Wykażemy, że:
\(\displaystyle{ \neg \left[ \bigvee\limits_{x: \alpha \left( x\right) } \beta \left( x\right) \right] \Leftrightarrow \bigwedge\limits_{x: \beta \left( x\right) } \left[ \neg \alpha \left( x\right) \right].}\)
DOWÓD TEGO FAKTU:
Mamy, z definicji kwantyfikatorów o ograniczonym zakresie:
\(\displaystyle{ \neg \left[ \bigvee\limits_{x: \alpha \left( x\right) } \beta \left( x\right) \right] \Leftrightarrow \neg \left[ \bigvee\limits_{x} \left( \alpha \left( x\right) \wedge \beta \left( x\right) \right) \right] \Leftrightarrow \bigwedge\limits_{x} \neg \left( \alpha \left( x\right) \wedge \beta \left( x\right) \right) \Leftrightarrow \bigwedge\limits_{x} \neg \left( \beta \left( x\right) \wedge \alpha \left( x\right) \right) \Leftrightarrow \bigwedge\limits_{x} \left[ \ \left( \neg \beta \left( x\right) \right) \vee \left( \neg \alpha \left( x\right) \right) \ \right] \Leftrightarrow \\ \stackrel{\left( A \Rightarrow B\right) \Leftrightarrow \left( \neg A\right) \vee B }{\Leftrightarrow} \bigwedge\limits_{x} \left[ \ \beta \left( x\right) \rightarrow \left( \neg \alpha \left( x\right) \right) \ \right] \Leftrightarrow \bigwedge\limits_{x: \beta \left( x\right) } \left[ \neg \alpha \left( x\right) \right];}\)
co w myśl reguły przechodniości równoważności dowodzi naszego prawa.\(\displaystyle{ \square}\)
Zauważmy, że nie ma (niestety, a już próbowałem to dowodzić, a tu wskazałem kontrprzykład) analogicznego prawa odnośnie zaprzeczania formuł z kwantyfikatorem ogólnym o ograniczonym zakresie, tzn. nie zachodzi prawo:
\(\displaystyle{ \neg \left[ \bigwedge\limits_{x: \alpha \left( x\right) } \beta \left( x\right) \right] \Leftrightarrow \bigvee\limits_{x: \beta \left( x\right) } \neg \left( \alpha \left( x\right) \right);
}\)
Aby podać kontrprzykład to:
Niech uniwersum będzie \(\displaystyle{ U=\NN}\) zbiorem liczb naturalnych, i rozważmy dwie formuły:
\(\displaystyle{ \alpha \left( x\right)\equiv x \neq x;}\)
\(\displaystyle{ \beta \left( x\right)\equiv x \hbox{ jest liczbą parzystą}.}\)
Ponieważ dla każdej liczby naturalnej \(\displaystyle{ x}\) fałszem jest \(\displaystyle{ x \neq x}\), więc zdanie \(\displaystyle{ \bigwedge\limits_{x: \alpha \left( x\right) } \beta \left( x\right) }\) jest formalnie prawdziwe, a więc jego zaprzeczenie będzie fałszywe, a ponieważ istnieje liczba parzysta równa samej sobie( np. \(\displaystyle{ x=2}\)), to zdanie \(\displaystyle{ \bigvee\limits_{x: \beta \left( x\right) } \left[ \neg \alpha \left( x\right) \right]}\) jest prawdziwe. A zatem, podana równoważność nie zachodzi.
Wiemy, że równość pozwala zdefiniować kwantyfikator jednostkowy typu istnieje dokładnie jedno \(\displaystyle{ x}\), takie, że: \(\displaystyle{ \alpha \left( x\right)}\). Jako ciekawostkę podam, że można zdefiniować pozostałe kwantyfikatory ilościowe (dla dowolnych skończonych ilości \(\displaystyle{ n=2,3,\ldots}\)):
(1): \(\displaystyle{ \bigvee\limits_{x} ^{n} \alpha \left( x\right)\equiv \hbox{ Istnieje dokładnie } n \hbox{ elementów }x, \hbox{ takich, że } \alpha \left( x\right) ;}\)
(2): \(\displaystyle{ \bigvee\limits_{x} ^{n \uparrow } \alpha \left( x\right)\equiv \hbox{ Istnieje co najmniej } n \hbox{ elementów }x, \hbox{ takich, że } \alpha \left( x\right) ;}\)
(3): \(\displaystyle{ \bigvee\limits_{x} ^{n \downarrow } \alpha \left( x\right)\equiv \hbox{ Istnieje co najwyżej } n \hbox{ elementów }x, \hbox{ takich, że } \alpha \left( x\right) ;}\)
Aby to uzasadnić, zacznijmy najpierw od podpunktu (2):
i niech najpierw \(\displaystyle{ n=2}\), wtedy zdanie mówiące, że istnieje co najmniej dwa elementy \(\displaystyle{ x}\), że \(\displaystyle{ \alpha \left( x\right),}\) definiujemy jako:
\(\displaystyle{ \bigvee\limits_{a: \alpha \left( a\right) }\bigvee\limits_{b: \alpha \left( b\right) } a \neq b. }\)
Czyli istnieje element \(\displaystyle{ a}\) taki, że \(\displaystyle{ \alpha \left( a\right)}\), i istnieje element \(\displaystyle{ b}\), taki, że \(\displaystyle{ \alpha \left( b\right)}\), i \(\displaystyle{ a}\) jest różne od \(\displaystyle{ b}\).
Dalej, zdanie mówiące, że istnieją co najmniej trzy elementy \(\displaystyle{ x}\), takie, że \(\displaystyle{ \alpha \left( x\right),}\) definiujemy jako:
\(\displaystyle{ \bigvee\limits_{a: \alpha \left( a\right) }\bigvee\limits_{b: \alpha \left( b\right) } \bigvee\limits_{c: \alpha \left( c\right) } \left( a \neq b \wedge c \neq a \wedge c \neq b\right) . }\)
Dalej, zdanie mówiące, że istnieją co najmniej cztery elementy \(\displaystyle{ x}\) takie, że: \(\displaystyle{ \alpha \left( x\right)}\), definiujemy jako:
\(\displaystyle{ \bigvee\limits_{a: \alpha \left( a\right) }\bigvee\limits_{b: \alpha \left( b\right) } \bigvee\limits_{c: \alpha \left( c\right) }\bigvee\limits_{d: \alpha \left( d\right) } \left( a \neq b \wedge c \neq a \wedge c \neq b \wedge d \neq a \wedge d \neq b \wedge d \neq c\right) . }\)
Itd. ...
Zajmijmy się teraz podpunktem (3):
Zdanie mówiące, że istnieje co najwyżej \(\displaystyle{ n}\) elementów \(\displaystyle{ x}\), takich, że \(\displaystyle{ \alpha \left( x\right)}\) definiujemy jako zdanie mówiące, że nie istnieje \(\displaystyle{ \left( n+1\right)}\) elementów \(\displaystyle{ x,}\) takich, że \(\displaystyle{ \alpha \left( x\right)}\), tzn.:
\(\displaystyle{ \bigvee\limits_{x} ^{n \downarrow } \alpha \left( x\right)\equiv \neg \left[ \bigvee\limits_{x} ^{(n+1)\uparrow } \alpha \left( x\right)\right].}\)
Jeśli bowiem mamy co najwyżej \(\displaystyle{ n}\) elementów, to nie da się z nich wybrać \(\displaystyle{ \left( n+1\right)}\) różnych elementów; jeśli zaś mamy więcej niż \(\displaystyle{ n}\) elementów, to jest wśród nich \(\displaystyle{ (n+1)}\) różnych elementów.
No i podpunkt (1) mówiący, że istnieje dokładnie \(\displaystyle{ n}\) elementów, takich, że \(\displaystyle{ \alpha \left( x\right)}\) definiujemy jako koniunkcję zdania mówiącego, że istnieje co najmniej \(\displaystyle{ n}\) elementów \(\displaystyle{ x,}\) takich, że \(\displaystyle{ \alpha \left( x\right),}\) i zdania mówiącego, że istnieje co najwyżej \(\displaystyle{ n}\) elementów \(\displaystyle{ x}\), takich, że \(\displaystyle{ \alpha \left( x\right).\square}\)
