next up previous
Next: 7. Rachunek kwantyfikatorów Up: Wstęp do matematyki Previous: 5. Produkty kartezjańskie

6. Kwantyfikatory

Kwantyfikatory to określenia ilościowe dotyczące liczby obiektów jakiegoś typu. Na przykład niech $X$ oznacza zbiór Polaków, zaś $\varphi(x),x\in X$ funkcję zdaniową ``$x$ jest praworęczny''. Rozważmy zdanie:
$(*)$
Każdy Polak jest praworęczny.
Możemy to zdanie przepisać w sposób częściowo symboliczny:
Dla każdego $x\in X$, $x$ jest praworęczny.
W rachunku zdań zastępowaliśmy spójniki języka potocznego przez pewne symbole. W rachunku kwantyfikatorów zwrot ``dla każdego '' zapisujemy symbolicznie w postaci $\forall$. Zdanie $(*)$ możemy więc zapisać w postaci

\begin{displaymath}(**)  (\forall x\in X)\varphi(x).\end{displaymath}

Zdanie to jest równoważne temu, że wykres funkcji zdaniowej $\varphi(x)$ to cały zbiór $X$, tzn.

\begin{displaymath}\{x\in X:\varphi(x)\}=X.\end{displaymath}

Zdanie $(**)$ możemy odczytywać na wiele równoważnych sposobów:
  1. Dla każdego $x\in X$, $\varphi(x)$ .
  2. Dla dowolnego $x\in X$, $\varphi(x)$.
  3. Dla wszystkich $x\in X$, $\varphi(x)$.
  4. Wszystkie $x\in X$ mają własność $\varphi(x)$.
  5. Każdy $x\in X$ spełnia $\varphi(x)$.
  6. $\varphi(x)$ dla wszystkich $x\in X$.

Symbol $\forall$ nazywamy dużym kwantyfikatorem (lub kwantyfikatorem ogólnym, uniwersalnym)6.1. Ogólnie, dla dowolnej funkcji zdaniowej $\varphi(x),x\in X$ zapis $(**)$ odczytujemy na dowolny z powyższych sposobów. Oznacza on zawsze, że $\{x\in X:\varphi(x)\}=X$.

Rozważmy teraz zdanie

$(\dagger)$
Pewien Polak jest praworęczny.
Oznaczając znów przez $X$ zbiór Polaków i używając $\varphi(x)$ na oznaczenie funkcji zdaniowej ``$x$ jest praworęczny'' możemy zdanie to zapisać w postaci
Istnieje $x\in X$ taki, że $\varphi(x)$.
Zwrot ``istnieje'' zapisujemy symbolicznie w postaci $\exists$. Zatem zdanie $(\dagger)$ możemy zapisać symbolicznie jako

\begin{displaymath}(\ddagger)  (\exists x\in X)\varphi(x).\end{displaymath}

Zdanie to jest równoważne temu, że wykres funkcji zdaniowej $\varphi(x)$ jest niepusty, tzn.

\begin{displaymath}\{x\in X:\varphi(x)\}\neq\emptyset.\end{displaymath}

Zdanie $(\ddagger)$ możemy odczytywać na wiele równoważnych sposobów:
  1. Istnieje $x\in X$ takie, że $\varphi(x)$.
  2. Dla pewnego $x\in X$ mamy $\varphi(x)$.
  3. Jakieś $x\in X$ spełnia $\varphi(x)$.
  4. $\varphi(x)$ dla pewnego $x\in X$.

Symbol $\exists$ nazywamy małym kwantyfikatorem (lub kwantyfikatorem egzystencjalnym)6.2. Ogólnie, dla dowolnej funkcji zdaniowej $\varphi(x),x\in X$ zapis $(\ddagger)$ odczytujemy na dowolny z powyższych sposobów. Oznacza on zawsze, że $\{x\in X:\varphi(x)\}\neq\emptyset$.

Zbiór $X$ w wyrażeniach $(**)$ i $(\ddagger)$ nazywamy zakresem kwantyfikatora. Gdy jest on znany z kontekstu, można pomijać fragment ``$\in X$'' w $(**)$ i $(\ddagger)$, pisząc odpowiednio

\begin{displaymath}\forall x \varphi(x)\mbox{  i  }\exists x \varphi(x).\end{displaymath}

Używając kwantyfikatorów wiele matematycznych zdań możemy zapisać w przejrzystej formie. Na przykład zdanie

\begin{displaymath}\exists x(x^2+x-1=0)\end{displaymath}

mówi, że ``równanie $x^2+x-1=0$ ma rozwiązanie''. Fakt, że $A$ zawiera się w $B$, możemy zapisać w postaci

\begin{displaymath}\forall x(x\in A\Rightarrow x\in B),\end{displaymath}

zaś to, że zbiory $A$ i $B$ nie są rozłączne, znaczy, że

\begin{displaymath}\exists x(x\in A\land x\in B).\end{displaymath}

W przypadku kwantyfikowania po zbiorze skończonym mały kwantyfikator możemy zastąpić przez kilkukrotną alternatywę, zaś duży kwantyfikator przez kilkukrotną koniunkcję. Załóżmy mianowicie, że rozważamy funkcję zdaniową $\varphi(x),x\in X$, gdzie $X=\{a_1,\dots,a_n\}$ jest zbiorem skończonym. Wówczas zdanie $\exists x\varphi(x)$ jest równoważne

\begin{displaymath}\varphi(a_1)\lor\varphi(a_2)\lor\dots\lor\varphi(a_n),\end{displaymath}

zaś zdanie $\forall x\varphi(x)$ jest równoważne

\begin{displaymath}\varphi(a_1)\land\varphi(a_2)\land\dots\land\varphi(a_n).\end{displaymath}

W matematyce używa się też często tak zwanych kwantyfikatorów ograniczonych (inaczej: zrelatywizowanych).

Przykład 1. Zdanie ``Jeśli liczba rzeczywista $x$ jest $\geq
5$, to $x^2\geq 5x$'' w formie symbolicznej ma postać

\begin{displaymath}\forall x(x\geq 5\Rightarrow x^2\geq 5x),\end{displaymath}

gdzie zakres kwantyfikatora to zbiór liczb rzeczywistych. Możemy je jednak również wyrazić mówiąc: ``Dla każdej liczby rzeczywistej $x$ większej lub równej $5$ mamy $x^2\geq 5x$'', co w formie symbolicznej ma postać:

\begin{displaymath}(\forall x\geq 5)(x^2\geq 5x).\end{displaymath}

W wyrażeniu tym zakres kwantyfikatora jest ograniczony do liczb rzeczywistych $\geq
5$, dlatego nazywamy go tu kwantyfikatorem ograniczonym (zrelatywizowanym).

Podobnie dla funkcji zdaniowej $\varphi(x),x\in X$ i zbioru $A\subseteq X$ zdanie

\begin{displaymath}\forall x(x\in A\Rightarrow\varphi(x))\end{displaymath}

czytamy ``Dla każdego $x$, jeśli $x\in A$, to $\varphi(x)$''. Jest ono równoważne temu, że $\{x\in A:\varphi(x)\}=A$. Zatem równoważnie możemy wyrazić to zdanie mówiąc: ``Dla każdego $x\in A$ mamy $\varphi(x)$''. W formie symbolicznej zdanie to ma postać

\begin{displaymath}(\forall x\in A)\varphi(x),\end{displaymath}

zakres kwantyfikatora został tu ograniczony do zbioru $A$.

Przykład 2. Rozważmy zdanie ``Istnieje liczba rzeczywista $x$ taka, że $x<5$ i $x^2>3x$''. Symbolicznie zdanie to ma postać

\begin{displaymath}\exists x(x<5\land x^2>3x).\end{displaymath}

Możemy jednak wysłowić je mówiąc: ``Istnieje liczba $x$ mniejsza od $5$, taka że $x^2>3x$''. Symbolicznie zapisujemy to w postaci:

\begin{displaymath}(\exists x<5)(x^2>3x).\end{displaymath}

Znów zakres kwantyfikatora, ktory początkowo był równy $\mathbb{R}$, został tu ograniczony do liczb rzeczywistych $<5$.

Podobnie, gdy mamy funkcję zdaniową $\varphi(x),x\in X$ i $A\subseteq X$, zdanie

\begin{displaymath}\exists x(x\in A\land \varphi(x))\end{displaymath}

jest równoważne temu, że $\{x\in A:\varphi(x)\}\neq\emptyset$. Możemy więc zapisać je w formie

\begin{displaymath}(\exists x\in A)\varphi(x).\end{displaymath}

Zakres kwantyfikatora, który początkowo był równy $X$, jest tu ograniczony do zbioru $A$.

Warto podkreślić, że relatywizacja dużego kwantyfikatora odpowiada ``schowaniu'' poprzednika implikacji, zaś relatywizacja małego kwantyfikatora odpowiada ``schowaniu'' pierwszego członu koniunkcji, i tylko w takich przypadkach mogą być one dokonane. Formalnie rzecz biorąc, każda z form zapisu (zrelatywizowana lub nie) jest równie dobra, wybór formy jest więc kwestią smaku. W miarę potrzeby można przechodzić od jednej formy zapisu do drugiej. Kwantyfikatory ograniczone zazwyczaj ujmujemy w nawiasy.

Jako kolejny przykład zauważmy, że w zrelatywizowanej formie zdanie $\forall
x(x\in A\Rightarrow x\in B)$ ma postać $(\forall x\in A)(x\in B)$. Podobnie zdanie $\exists x(x\in A\land x\in B)$ w postaci zrelatywizowanej można zapisać na dwa sposoby: $(\exists x\in
A)(x\in B)$ i $(\exists x\in B)(x\in A)$. (W obu tych przykładach zakładamy, że zbiory $A$ i $B$ są podzbiorami jednej przestrzeni $X$, która jest zakresem kwantyfikatorów w postaci niezrelatywizowanej.)

Możemy również kwantyfikować funkcje zdaniowe większej liczby zmiennych. Rozważmy funkcję zdaniową $\varphi(x,y),x\in X,y\in Y$. Wówczas możemy utworzyć nowe funkcje zdaniowe:

``dla każdego $x\in X, \varphi(x,y)$'' oraz ``istnieje $x\in X$ takie, że $\varphi(x,y)$''.
W formie symbolicznej zapisujemy je następująco:

\begin{displaymath}(\dagger\dagger)   (\forall x\in X)\varphi(x,y)\mbox{ oraz\
}(\exists x\in X)\varphi(x,y).\end{displaymath}

Są to funkcje zdaniowe zmiennej $y$ o zakresie $Y$. Zmienna $x$ została tu ``związana'' przez kwantyfikatory $\forall x$ i $\exists
x$. Gdy zakres kwantyfikatorów jest znany z kontekstu, możemy pomijać fragment ``$\in X$'' w $(\dagger\dagger)$, pisząc $\forall x\varphi(x,y)$ i $\exists
x\varphi(x,y)$.

Niech $A\subseteq X\times Y$ będzie wykresem funkcji zdaniowej $\varphi(x,y),x\in X,y\in Y$. Widzimy, że

\begin{displaymath}\pi_X[A]=\{x\in X:(\exists y\in Y)\langle x,y\rangle\in A\}=\{x\in
X:(\exists y\in Y)\varphi(x,y)\},\end{displaymath}


\begin{displaymath}\pi_Y[A]=\{y\in Y:(\exists x\in X)\langle x,y\rangle\in A\}=\{y\in
Y:(\exists x\in X)\varphi(x,y)\}.\end{displaymath}

Dla dowolnych $a\in X,b\in Y$ mamy też


\begin{displaymath}(\forall y\in Y)\varphi(a,y)\Leftrightarrow A_a=Y,   (\exists y\in
Y)\varphi(a,y)\Leftrightarrow A_a\neq\emptyset,\end{displaymath}


\begin{displaymath}(\forall x\in X)\varphi(x,b)\Leftrightarrow A^b=X,   (\exists
x\in X)\varphi(x,b)\Leftrightarrow A^b\neq\emptyset.\end{displaymath}

Przy pomocy cięć pionowych zbioru $A$ możemy więc zinterpretować zdania typu $(\forall x\in X)(\exists y\in
Y)\varphi(x,y)$.

\begin{displaymath}(\forall x\in X)(\forall y\in Y)\varphi(x,y)\Leftrightarrow\mbox{
każde cięcie pionowe zbioru $A$ jest całym $Y$.}\end{displaymath}


\begin{displaymath}(\forall x\in X)(\exists y\in Y)\varphi(x,y)\Leftrightarrow\mbox{
każde cięcie pionowe zbioru $A$ jest niepuste.}\end{displaymath}


\begin{displaymath}(\exists x\in X)(\forall y\in Y)\varphi(x,y)\Leftrightarrow\mbox{
pewne cięcie pionowe zbioru $A$ jest całym $Y$.}\end{displaymath}


\begin{displaymath}(\exists x\in X)(\exists y\in Y)\varphi(x,y)\Leftrightarrow\mbox{
pewne cięcie pionowe zbioru $A$ jest niepuste.}\end{displaymath}

Podobnie przy pomocy cięć poziomych zbioru $A$ interpretujemy zdania

\begin{displaymath}(\forall y\in Y)(\forall x\in X)\varphi(x,y), (\forall y\in
Y)(\exists x\in X)\varphi(x,y),\end{displaymath}


\begin{displaymath}(\exists y\in Y)(\forall x\in X)\varphi(x,y), (\exists y\in
Y)(\exists x\in X)\varphi(x,y).\end{displaymath}

Rozważymy teraz kilka przykładów z języka potocznego. Niestety, zarówno w języku potocznym, jak i w matematyce, by sformalizować zdanie przy pomocy kwantyfikatorów, trzeba je często najpierw przeformułować.

Przykład 1. Sformalizujemy zdanie: ``Każdy kij ma przynajmniej dwa końce''. Niech mianowicie $X$ oznacza zbiór kijów, $Y$ zbiór końców, zaś $\varphi(x,y),x\in X,y\in Y,$ funkcję zdaniową: ``$y$ jest końcem $x$''. Nasze zdanie możemy wysłowić mówiąc:

Dla każdego kija $x$ istnieją końce $y,z$ takie, że $y$ jest końcem $x$ i $z$ jest końcem $x$ i $y\neq z$.
Symbolicznie nasze zdanie ma postać:

\begin{displaymath}(\forall x\in X)(\exists y\in Y)(\exists z\in
Y)(\varphi(x,y)\land\varphi(x,z)\land y\neq z).\end{displaymath}

Zapis $y\neq z$ jest skrótem dla $\neg(y=z)$.

Przykład 2. Sformalizujemy zdanie: ``Każdy dudek ma swój czubek''. Niech $X$ oznacza zbiór dudków, $Y$ zbiór czubków, zaś $\varphi(x,y),x\in X,y\in Y,$ funkcję zdaniową: ``$x$ ma $y$''. Nasze zdanie możemy przeformułować następująco:

Dla każdego dudka $x$ istnieje czubek $y$ taki, że $x$ ma $y$.
W formie symbolicznej nasze zdanie ma postać

\begin{displaymath}(\forall x\in X)(\exists y\in Y)\varphi(x,y).\end{displaymath}

W tym miejscu zwróćmy uwagę, że zdanie z kwantyfikatorami w zmienionej kolejności:

\begin{displaymath}(\exists y\in Y)(\forall x\in X)\varphi(x,y)\end{displaymath}

odczytujemy jako:
Istnieje taki czubek, że każdy dudek go ma.
co jest jawnym fałszem. Widzimy więc, że ogólnie zdania

\begin{displaymath}\forall x\exists y\varphi(x,y)\mbox{  i  }\exists y\forall
x\varphi(x,y)\end{displaymath}

nie są równoważne, to znaczy kwantyfikatory $\forall$ i $\exists$ nie są przemienne.

Przykład 3. Sformalizujemy zdanie: ``Nie wszystko złoto, co się świeci''. Niech $X$ oznacza zbiór rzeczy, $\varphi(x),x\in X$, funkcję zdaniową ``$x$ jest złote'', zaś $\psi(x),x\in X$ funkcję zdaniową ``$x$ się świeci''. Nasze zdanie możemy przeformułować w postaci: ``Nieprawda, że każda rzecz $x$, która się świeci, jest złota.'', czy też inaczej: ``Nieprawda, że dla każdej rzeczy $x$, jeśli $x$ się świeci, to $x$ jest złota.'' Zatem nasze zdanie ma postać symboliczną:

\begin{displaymath}\neg\forall x(\psi(x)\Rightarrow\varphi(x)).\end{displaymath}

Formalizacja zdań matematycznych przy pomocy spójników logicznych i kwantyfikatorów nie jest celem samym w sobie. Warto ją stosować, gdy rozjaśnia znaczenie matematycznego zdania lub upraszcza jego zapis. Gdy jednak zdanie jest wystarczająco jasne w potocznym języku matematycznym, nie należy ulegać manierze zastępowania w nim zwyczajnych słów (takich jak ``i'', ''lub'', ``dla każdego'') przez sztuczne znaczki ( $\land,\lor,\forall$).


next up previous
Next: 7. Rachunek kwantyfikatorów Up: Wstęp do matematyki Previous: 5. Produkty kartezjańskie
Ludomir Newelski 2005-09-22