Rachunek kwantyfikatorów

W rachunku zdań tworzyliśmy formuły zdaniowe, które mogły oznaczać różne zdania w zależności od interpretacji zmiennych zdaniowych wchodzących w ich skład. W rachunku kwantyfikatorów przy pomocy symboli oznaczających funkcje zdaniowe, symbolu równości $=$, kwantyfikatorów, spójników logicznych, zmiennych i nawiasów tworzymy wyrażenia oznaczające nowe funkcje zdaniowe lub zdania (w zależności od tego, czy wszystkie zmienne w tych wyrażeniach są związane, czy nie). Wyrażenia takie nazywamy formułami rachunku kwantyfikatorów, lub krótko formułami. Przykładowo rozważmy formułę

$$(*)\ \ \forall x(\varphi(x,y)\Rightarrow\exists y(\psi(x,y)\land\neg\varphi(x,y))).$$

W formule tej symbole $\forall$ i $\exists$ odczytujemy jako ``dla każdego'' i ``istnieje''. Symbole $\varphi(x,y)$ i $\psi(x,y)$ mogą być tu interpretowane jako konkretne funkcje zdaniowe na wiele sposobów. Wyjątek czynimy dla symbolu równości $=$, który zawsze interpretujemy jak prawdziwą równość. Gdy $\varphi,\psi$ oznaczają konkretne funkcje zdaniowe, gdzie wspólnym zakresem zmiennych $x,y$ jest jakaś przestrzeń $X$, formuła $(*)$ również oznacza funkcję zdaniową zmiennej $y$ o zakresie $X$. Jeśli na przykład poprzedzimy ją kwantyfikatorem $\exists y$ (wiążącym zmienną $y$), stanie się ona zdaniem. Dlatego formuły, w których wszystkie zmienne są związane przez kwantyfikatory, nazywamy formułami domkniętymi lub (niezbyt poprawnie) zdaniami.

W formule $(*)$ kwantyfikator $\forall x$ odnosi się do formuły

$$\varphi(x,y)\Rightarrow\exists y(\psi(x,y)\land\neg\varphi(x,y)),$$

nie zaś tylko do jej części $\varphi(x,y)$. Podobnie kwantyfikator $\exists y$ odnosi się do formuły

$$\psi(x,y)\land\neg\varphi(x,y),$$

nie zaś do jej części $\psi(x,y)$. Dlatego w obu przypadkach formuły te dodatkowo ograniczyliśmy nawiasami. Gdyby tych nawiasów nie było, formułę $(*)$ domyślnie należałoby odczytywać jako

$$(\forall x\varphi(x,y))\Rightarrow(\exists y\psi(x,y))\land\neg\varphi(x,y).$$

Wtedy obie zmienne w $\neg\varphi(x,y)$ pozostałyby niezwiązane (inaczej: wolne).

Gdy w formule $(*)$ za symbole $\varphi$ i $\psi$ podstawimy konkretne funkcje zdaniowe, stanie się ona sama (złożoną) funkcją zdaniową. Na przykład, niech $\varphi(x,y)$ oznacza funkcję zdaniową $x\mid y,x,y\in\mathbb{N}$ (tzn: ``$x$ dzieli $y$''), zaś $\psi(x,y)$ oznacza funkcję zdaniową $y\mid x,x,y\in\mathbb{N}$. Wówczas $(*)$ staje się funkcją zdaniową:

$$(\forall x\in\mathbb{N})(x\mid \dot{y}\Rightarrow(\exists y\in\mathbb{N})(y\mid x\land\neg x\mid y)),$$

którą dla uproszczenia będziemy teraz oznaczali przez $\chi(y)$, gdyż w tej funkcji zdaniowej $y$ występuje jako zmienna wolna. To wolne wystąpienie zmiennej $y$ w formule $\chi(y)$ zaznaczyliśmy kropką, pozostałe wystąpienia zmiennej $y$ w tej formule sa związane przez kwantyfikatory. Zakres zmienności zmiennej $y$ w tej funkcji zdaniowej to $\mathbb{N}$. Sprawdźmy dla przykładu, czy formuła $\chi(y)$ jest prawdziwa dla $y=1$, tzn. czy $\chi(1)$ jest zdaniem prawdziwym. Jest to zdanie następujące:

$$(\forall x\in\mathbb{N})(x\mid 1\Rightarrow(\exists y\in\mathbb{N})(y\mid x\land\neg x\mid y)).$$

(Powstało ono z $\chi(y)$ przez podstawienie liczby $1$ za każde wolne wystąpienie zmiennej $y$.) Zdanie to mówi, że

dla każdej liczby naturalnej $x$, jeśli $x$ dzieli $1$, to $(\exists y\in\mathbb{N})(y\mid x\land \neg x\mid y)$.

Nie jest to prawda, gdyż np. liczba $x=1$ dzieli $1$ oraz dla $x=1$ formuła $(\exists y\in\mathbb{N})(y\mid x\land \neg x\mid y)$ jest fałszywa.

Można sprawdzić, że dla każdego $n\in\mathbb{N}$, zdanie $\chi(n)$ jest fałszywe, czyli $(\forall y\in\mathbb{N})\neg\chi(y)$.

Definicja 7..1   Formułę domkniętą nazywamy tautologią (rachunku kwantyfikatorów), gdy jest zdaniem prawdziwym przy dowolnym rozumieniu występujących w niej symboli funkcji zdaniowych.

Przykładem tautologii jest formuła

$$\forall x(\varphi(x)\lor\neg\varphi(x)).$$

Ogólniej, jeśli $\alpha(p,q,r)$ jest tautologią rachunku zdań, to formuła
$\forall x\alpha(p(x),q(x),r(x))$ jest tautologią rachunku kwantyfikatorów, gdzie symbole $p(x),q(x),r(x)$ oznaczają teraz funkcje zdaniowe zmiennej $x$.

Podobnie jak w rachunku zdań, wiele tautologii rachunku kwantyfikatorów ma postać równoważności. Pozwalają one przekształcać w sposób równoważny zdania tak, by uzyskać jak najprostszą formę.

Definicja 7..2 (1)   Mówimy, że dwie funkcje zdaniowe $\alpha(x)$ i $\beta(x)$ (o wspólnym zakresie zmiennej $x$) są równoważne, gdy mają ten sam wykres. Innymi słowy, gdy $X$ oznacza wspólny zakres zmiennej $x$ w tych funkcjach, znaczy to, że

$$\{x\in X:\alpha(x)\}=\{x\in X:\beta(x)\}.$$

(2) Mówimy, że dwie formuły domknięte $\alpha$ i $\beta$ są równoważne, gdy formuła $\alpha\Leftrightarrow\beta$ jest tautologią.

Podobnie definiujemy równoważność funkcji zdaniowych większej liczby zmiennych.

Uwaga 7..3   Dwie funkcje zdaniowe $\alpha(x)$ i $\beta(x),x\in X$ są równoważne wtedy i tylko wtedy, gdy zdanie $\forall x(\alpha(x)\Leftrightarrow\beta(x))$ jest prawdziwe.

Dowód. Niech $p$ oznacza zdanie

$\alpha(x)$ i $\beta(x)$ są równoważne.

zaś $q$ zdanie

Zdanie $\forall x(\alpha(x)\Leftrightarrow\beta(x))$ jest prawdziwe.

By udowodnić równoważność obu zdań korzystamy z faktu, że zdanie $p\Leftrightarrow q$ jest równoważne koniunkcji dwóch implikacji $p\Rightarrow q$ i $q\Rightarrow p$. Wystarczy więc udowodnić każdą z tych implikacji.

$p\Rightarrow q$. Wystarczy udowodnić zdanie $q$ zakładając, że $p$ jest prawdziwe. Załóżmy, że $p$ jest prawdziwe, to znaczy funkcje zdaniowe $\alpha(x)$ i $\beta(x)$ są równoważne. Znaczy to, że $\{x\in X:\alpha(x)\}=\{x\in X:\beta(x)\}$. Oznaczmy przez $Y$ ten zbiór. Dlatego dla każdego $a\in X$ mamy, że zdania $\alpha(a)$ i $\beta(a)$ mają tę samą wartość logiczną (a mianowicie są oba fałszywe, gdy $a\not\in Y$ i oba prawdziwe, gdy $a\in Y$). Dlatego dla każdego $a\in X$ zdanie $\alpha(a)\Leftrightarrow\beta(a)$ jest prawdziwe. Oznacza to, że prawdziwe jest zdanie $\forall x(\alpha(x)\Leftrightarrow\beta(x))$, czyli $q$.

$q\Rightarrow p$. Tu dowód pozostawiamy jako ćwiczenie. $\Box$

Podamy teraz przykłady prostych tautologii rachunku kwantyfikatorów. Wiele z nich ma postać równoważności.

1. $\neg\forall x\varphi(x)\Leftrightarrow\exists x\neg\varphi(x)\ ,\ \neg\exists x\varphi(x)\Leftrightarrow\forall x\neg\varphi(x)$
   (prawa de Morgana rachunku kwantyfikatorów)
2. $\forall x\forall y\varphi(x,y)\Leftrightarrow\forall y\forall x\varphi(x,y)$ (przemienność dużych kwantyfikatorów)
3. $\exists x\exists y\varphi(x,y)\Leftrightarrow\exists y\exists x\varphi(x,y)$ (przemienność małych kwantyfikatorów)
4. $\exists x\forall y\varphi(x,y)\Rightarrow\forall y\exists x\varphi(x,y)$
5. $\forall x(\varphi(x)\land\psi(x))\Leftrightarrow\forall x\varphi(x)\land\forall x\psi(x)$ (rozdzielność $\forall$ względem $\land$)
6. $\exists x(\varphi(x)\lor\psi(x))\Leftrightarrow\exists x\varphi(x)\lor\exists x\psi(x)$ (rozdzielność $\exists$ względem $\lor$)
7. $\exists x(\varphi(x)\land\psi(x))\Rightarrow\exists x\varphi(x)\land\exists x\psi(x)$
8. $\forall x\varphi(x)\lor\forall x\psi(x)\Rightarrow\forall x(\varphi(x)\lor\psi(x))$
9. $\forall x(\varphi(x)\Rightarrow\psi(x))\Rightarrow(\exists x\varphi(x)\Rightarrow\exists x\psi(x))$

Przed dowodem zauważmy, że intuicyjnie formuły te istotnie zawsze oznaczają zdania prawdziwe.
Dowód. Udowodnimy niektóre punkty. (1) Udowodnimy, że $\neg\forall x\varphi(x)\Leftrightarrow\exists x\neg\varphi(x)$ jest tautologią. W tym celu rozważmy dowolną konkretną funkcję zdaniową $\varphi(x),x\in X$. Wystarczy pokazać, że zdania $\neg(\forall x\in X)\varphi(x)$ i $(\exists x\in X)\neg\varphi(x)$ są równoważne. Niech

$$A=\{x\in X:\varphi(x)\}\mbox{\ \ i\ \ }B=\{x\in X:\neg\varphi(x)\}.$$

Zatem $A$ i $B$ są rozłączne (prawo sprzeczności) i w sumie dają cały zbiór $X$ (prawo wyłączonego środka). Korzystając z definicji kwantyfikatorów dostajemy ciąg zdań równoważnych

$$\neg(\forall x\in X)\varphi(x)$$

$$\Updownarrow$$

$$A\neq X$$

$$\Updownarrow$$

$$B\neq\emptyset$$

$$\Updownarrow$$

$$(\exists x\in X)\neg\varphi(x),$$

który świadczy o żądanej równoważności.

(2) Obie strony równoważności mówią, że $\{\langle x,y\rangle\in X\times X:\varphi(x,y)\}=X\times X$, dlatego są równoważne.

(4) Podobnie jak w punkcie (1) interpretujemy najpierw $\varphi(x,y)$ jako funkcję zdaniową na jakiejś (dowolnej) przestrzeni $X$. Mamy pokazać, że przy tej interpretacji zdanie

$$(**)\ \ (\exists x\in X)(\forall y\in X)\varphi(x,y)\Rightarrow(\forall y\in X)(\exists x\in X)\varphi(x,y)$$

jest prawdziwe.

Niech $A\subseteq X\times X$ oznacza wykres funkcji zdaniowej $\varphi(x,y)$. Zatem $(**)$ oznacza dokładnie, że

jeśli pewne cięcie pionowe zbioru $A$ jest całym $X$, to każde cięcie poziome zbioru $A$ jest niepuste.

By to udowodnić, załóżmy, że $a\in X$ oraz $A_a=X$. Znaczy to, że każda para postaci $\langle a,y\rangle$, gdzie $y\in X$, należy do $A$. Wobec tego dla każdego $b\in X$ mamy $A^b\neq\emptyset$, gdyż $\langle a,b\rangle\in A$, więc $a\in A^b$.

W tym miejscu zwróćmy uwage, że implikacja odwrotna do (4)

$$\forall y\exists x\varphi(x,y)\Rightarrow\exists x\forall y\varphi(x,y)$$

nie jest tautologią. Świadczy o tym przykład o dudku z rozdziału 5. Podobnie implikacje odwrotne do (7),(8),(9) nie są tautologiami.

(5) Jak wyżej, rozważamy funkcje zdaniowe $\varphi(x)$ i $\psi(x),x\in X$. Mamy pokazać, że zdania

$$(\forall x\in X)(\varphi(x)\land \psi(x))\mbox{\ i\ }(\forall x\in X)\varphi(x)\land(\forall x\in X)\psi(x)$$

są równoważne. W tym celu oznaczmy przez $A$ wykres funkcji zdaniowej $\varphi(x)$, zaś przez $B$ wykres funkcji zdaniowej $\psi(x)$. Wówczas zbiór $A\cap B$ jest wykresem funkcji zdaniowej $\varphi(x)\land\psi(x)$. Dlatego mamy następujący ciąg zdań równoważnych.

$$(\forall x\in X)(\varphi(x)\land \psi(x))$$

$$\Updownarrow$$

$$A\cap B=X$$

$$\Updownarrow$$

$$A=X\land B=X$$

$$\Updownarrow$$

$$(\forall x\in X)\varphi(x)\land(\forall x\in X)\psi(x),$$

co kończy dowód.

Dowody pozostałych punktów jedną z powyższych metod pozostawiamy jako ćwiczenie. $\Box$

Należy tu zaznaczyć, że chociaż dowody, że powyższe formuły są tautologiami, są dość łatwe, ogólnie nie istnieje algorytm (tzn. przepis) sprawdzania, czy dana formuła jest tautologią. Jak pamiętamy, algorytm taki istnieje w przypadku tautologii rachunku zdań (tabelka).

Z uwagi na przemienność kwantyfikatorów stosujemy konwencję łączenia sąsiednich dużych i sąsiednich małych kwantyfikatorów, tzn. zamiast $\forall x\forall y\varphi(x,y)$ piszemy $(\forall x,y)\varphi(x,y)$ i podobnie dla $\exists$.

Warto tu wspomnieć o tym, że niekiedy w matematyce traktuje się duży kwantyfikator jako kwantyfikator domyślny. Jest tak na przykład w zdaniach typu:

W przestrzeni ${\mathbb{R}}^2$ prawdziwa jest równość $x+y=y+x$.

Oczywiście równość $x+y=y+x$ nie jest zdaniem, w tym przypadku jednak domyślnie rozumie się, że chodzi tu o prawdziwość zdania $(\forall x,y)x+y=y+x$, duży kwantyfikator jest tu domyślny. W niniejszym wykładzie ze względów dydaktycznych będziemy jednak unikać tej konwencji.

Aby uzasadnić, że formuła nie jest tautologią, trzeba podać przykład (tzn. interpretację tej formuły jako konkretnego zdania), w którym jest ona zdaniem fałszywym. W tym celu potrzebujemy dużo przykładów funkcji zdaniowych. Dostarczają ich nam relacje.

Relacje. Relacja oznacza określony związek między obiektami jakiegoś typu. Przykładowo niech $M$ oznacza zbiór mężczyzn, zaś $K$ zbiór kobiet. Na zbiorach tym rozważamy relację $R$ bycia synem, tzn. fakt, że mężczyzna $X$ i kobieta $Y$ są w relacji $R$ oznacza dokładnie, że $X$ jest synem $Y$. Zwróćmy uwagę, że relacja $R$ jest w pełni opisana przez zbiór

$$\{\langle X,Y\rangle\in M\times K: X\mbox{ jest w relacji }R\mbox{ z }Y\}$$

(podobnie jak spójnik logiczny jest w pełni określony przez tabelkę wartości logicznych). W przypadku spójników logicznych definiowaliśmy również abstrakcyjne spójniki, nie mające odpowiednika w języku potocznym, poprzez właśnie zadanie tabelki wartości. Podobnie możemy postąpić w przypadku relacji.

Definicja 7..4   Relacją R na zbiorach $X$ i $Y$ nazywamy dowolny podzbiór produktu kartezjańskiego $X\times Y$. W tym przypadku fakt, że elementy $x\in X$ i $y\in Y$ są w relacji zapisujemy na dowolny z poniższych sposobów.

1. $\langle x,y\rangle\in R$ (sposób teoriomnogościowy)
2. $R(x,y)$
3. $x\ R\ y$

Zwróćmy uwagę, że każdy ze sposobów 1-3 z definicji 7.4 jest symbolicznym sposobem zapisu funkcji zdaniowej ``$x$ i $y$ są w relacji $R$'', gdzie zakres $x$ to $X$, zaś zakres $y$ to $Y$. Relacja $R$, jako podzbiór produktu $X\times Y$, jest natomiast wykresem tej funkcji zdaniowej. W ten sposób dostajemy mnóstwo przykładów funkcji zdaniowych.

W definicji 7.4 wprowadziliśmy pojęcie relacji dwuargumentowej (binarnej). Rozważa się również relacje o innej liczbie argumentów. Mianowicie, dla $k\geq 1$ relacja $k$-argumentowa na zbiorach $X_1,\dots,X_k$ to dowolny podzbiór $R$ produktu kartezjańskiego $X_1\times\dots\times X_k$. Dla $k=1$ relację $R$ nazywamy też relacją unarną. W przypadku, gdy

$$X_1=\dots=X_k=X,$$

mówimy, że jest to relacja $k$-argumentowa na zbiorze $X$. Funkcję zdaniową ``$x_1,\dots,x_k$ są w relacji $R$'' w przypadku $k=1$ zapisujemy w sposób 2. z definicji 7.4, w przypadku $k>2$ zapisujemy ją w sposób 1. lub 2. Jeśli nie określamy jawnie liczby argumentów relacji $R$ (tzn. jej arności), to w domyśle zakładamy, że jest to relacja binarna.

W przypadku relacji binarnej $R$ na zbiorach $X$ i $Y$ definiujemy dziedzinę i obraz relacji $R$ jako zbiory

$$Dom(R)=\{x\in X:(\exists y\in Y) R(x,y)\}\mbox{\ i\ }Rng(R)=\{y\in Y:(\exists x\in X)R(x,y)\}.$$

Zauważmy, że wtedy $R\subseteq Dom(R)\times Rng(R)$, czyli $R$ jest też relacją na zbiorach $Dom(R)$ i $Rng(R)$. Widzimy też, że w istocie $Dom(R)$ to rzut $R$ na pierwszą oś, a $Rng(R)$ to rzut $R$ na drugą oś^7.1.

Definiujemy też relację odwrotną $R^{-1}$ do relacji $R$ wzorem

$$R^{-1}=\{\langle y,x\rangle:R(x,y)\}.$$

Mamy zatem dla wszystkich $x,y,\ R(x,y)\Leftrightarrow R^{-1}(y,x)$. $R^{-1}$ jest więc relacją na zbiorach $Y$ i $X$.

Gdy $R$ jest relacją na zbiorze $X$ oraz $Y$ jest podzbiorem $X$, to definiujemy ograniczenie (obcięcie) relacji $R$ do zbioru $Y$ wzorem

$$R\vert _Y=R\cap (Y\times Y).$$

W przypadku relacji $R$ na zbiorach skończonych $X,Y$ wygodnie jest przedstawiać ją graficznie w postaci diagramu. Strzałka od $a$ do $b$ oznacza $R(a,b)$.

Poniżej zamieszczamy przykład diagramu relacji na zbiorze $X=\{a,b,c\}$.

Przykłady. 1. Relacja pusta $R=\emptyset$ jest $k$-argumentowa dla wszystkich $k\geq 1$.

2. Relacja porządku $x\leq y$ na zbiorze liczb rzeczywistych.

3. Relacja równoległości $l_1\parallel l_2$ na zbiorze prostych $L$ na płaszczyźnie.

4. Relacja podzielności $n\mid m$ na zbiorze liczb naturalnych
${\bf N}=\{0,1,2,3,\dots\}$.

5. Relacja inkluzji $\subseteq$ na zbiorze potęgowym ${\cal P}(X)$ dla ustalonego zbioru $X$.

Jak już wspomnieliśmy, relacji można używać do definiowania funkcji zdaniowych wskazujących, że pewne formuły nie są tautologiami. Przykładowo zrobimy to dla formuły

$$(\dagger)\ \ \forall x\exists y\varphi(x,y)\Rightarrow\exists y\forall x\varphi(x,y).$$

W tym przypadku przyjmujemy $X=\{0,1\}$ i definiujemy $R=\{\langle 0,1\rangle,\langle 1,0\rangle\}$ (sugerujemy narysowanie diagramu relacji $R$). Wtedy zdanie $(\forall x\in X)(\exists y\in X)R(x,y)$ jest prawdziwe, zaś $(\exists y\in X)(\forall x\in X)R(x,y)$ jest fałszywe. Zatem implikacja $(\forall x\in X)(\exists y\in X)R(x,y)\Rightarrow (\exists y\in X)(\forall x\in X)R(x,y)$ jest fałszywa, co pokazuje, że $(\dagger)$ nie jest tautologią rachunku kwantyfikatorów.

Rozważa się różne własności relacji $R$ na zbiorze $X$.

Definicja 7..5   Załóżmy, że $R$ jest relacją na zbiorze $X$.

1. $R$ jest zwrotna $\Leftrightarrow (\forall x\in X)( xRx)$.
2. $R$ jest przechodnia (tranzytywna) $\Leftrightarrow\\ (\forall x,y,z\in X)(xRy\land yRz\Rightarrow xRz)$.
3. $R$ jest symetryczna $\Leftrightarrow(\forall x,y\in X)(xRy\Rightarrow yRx)$.
4. $R$ jest antysymetryczna $\Leftrightarrow(\forall x,y\in X)(xRy\land yRx\Rightarrow x=y)$.
5. $R$ jest spójna $\Leftrightarrow (\forall x,y\in X)(xRy\lor yRx)$.

Jako ćwiczenie pozostawiamy stwierdzenie, jak przy pomocy diagramu relacji $R$ rozpoznać powyższe własności.

W powyższych przykładach relacji, relacja pusta $\emptyset$ jest przechodnia, symetryczna, antysymetryczna, lecz nie jest zwrotna ani spójna (na niepustym zbiorze $X$).

Relacja $\leq$ na zbiorze $\mathbb{R}$ jest zwrotna, przechodnia, antysymetryczna i spójna.

Relacja równoległości na zbiorze prostych na płaszczyźnie $L$ jest zwrotna, symetryczna i przechodnia, lecz nie jest antysymetryczna ani spójna.

Relacja podzielności na zbiorze $\mathbb{N}$ jest zwrotna, przechodnia, antysymetryczna, lecz nie jest symetryczna ani spójna.

Relacja inkluzji na zbiorze ${\cal P}(X)$ jest zwrotna, przechodnia, antysymetryczna, lecz nie jest spójna ani symetryczna (gdy $X$ ma więcej niż jeden element).

W następnych dwóch rozdziałach poznamy najważniejsze rodzaje relacji: relacje porządkujące i relacje równoważności.