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łę
W formule tej symbole i odczytujemy jako ``dla ka\
dego'' i ``istnieje''. Symbole i
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 oznaczają
konkretne funkcje zdaniowe, gdzie wspólnym zakresem zmiennych jest jakaś przestrzeń , formuła
równie\
oznacza funkcję zdaniową zmiennej o zakresie . Jeśli na przykład poprzedzimy ją
kwantyfikatorem (wią\
ącym zmienną ), 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 odnosi się do formuły
nie zaś tylko do jej części . Podobnie kwantyfikator odnosi się do formuły
nie zaś do jej części . 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
Wtedy obie zmienne w pozostałyby niezwiązane (inaczej: wolne).
Gdy w formule za symbole i podstawimy konkretne funkcje zdaniowe, stanie się ona sama
(zło\
oną) funkcją zdaniową. Na przykład, niech oznacza funkcję zdaniową (tzn: ``
dzieli ''), zaś oznacza funkcję zdaniową . Wówczas staje się funkcją
zdaniową:
którą dla uproszczenia będziemy teraz oznaczali przez , gdy\
w tej funkcji zdaniowej występuje
jako zmienna wolna. To wolne wystąpienie zmiennej w formule zaznaczyliśmy kropką, pozostałe
wystąpienia zmiennej w tej formule sa związane przez kwantyfikatory. Zakres zmienności zmiennej w
tej funkcji zdaniowej to . Sprawdz
my dla przykładu, czy formuła jest prawdziwa dla , tzn.
czy jest zdaniem prawdziwym. Jest to zdanie następujące:
(Powstało ono z przez podstawienie liczby za ka\
de wolne wystąpienie zmiennej .) Zdanie to
mówi, \
e
dla ka\
dej liczby naturalnej , jeśli dzieli , to .
Nie jest to prawda, gdy\
np. liczba dzieli oraz dla formuła jest
fałszywa.
Mo\
na sprawdzić, \
e dla ka\
dego , zdanie jest fałszywe, czyli .
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
Ogólniej, jeśli jest tautologią rachunku zdań, to formuła
jest tautologią rachunku kwantyfikatorów, gdzie symbole
oznaczają teraz funkcje zdaniowe zmiennej .
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 i (o wspólnym zakresie zmiennej ) są
równowa\
ne, gdy mają ten sam wykres. Innymi słowy, gdy oznacza wspólny zakres zmiennej w tych
funkcjach, znaczy to, \
e
(2) Mówimy, \
e dwie formuły domknięte i są równowa\
ne, gdy formuła jest tautologią.
Podobnie definiujemy równowa\
ność funkcji zdaniowych większej liczby zmiennych.
Uwaga 7..3 Dwie funkcje zdaniowe i są równowa\
ne wtedy i tylko wtedy, gdy zdanie
jest prawdziwe.
Dowód. Niech oznacza zdanie
i są równowa\
ne.
zaś zdanie
Zdanie jest prawdziwe.
By udowodnić równowa\
ność obu zdań korzystamy z faktu, \
e zdanie jest równowa\
ne koniunkcji
dwóch implikacji i . Wystarczy więc udowodnić ka\
dą z tych implikacji.
. Wystarczy udowodnić zdanie zakładając, \
e jest prawdziwe. Załó\
my, \
e jest prawdziwe,
to znaczy funkcje zdaniowe i są równowa\
ne. Znaczy to, \
e
. Oznaczmy przez ten zbiór. Dlatego dla ka\
dego mamy, \
e
zdania i mają tę samą wartość logiczną (a mianowicie są oba fałszywe, gdy i oba
prawdziwe, gdy ). Dlatego dla ka\
dego zdanie jest prawdziwe. Oznacza to, \
e
prawdziwe jest zdanie , czyli .
. Tu dowód pozostawiamy jako ćwiczenie.
Podamy teraz przykłady prostych tautologii rachunku kwantyfikatorów. Wiele z nich ma postać
równowa\
ności.
1.
(prawa de Morgana rachunku kwantyfikatorów)
2. (przemienność du\
ych kwantyfikatorów)
3. (przemienność małych kwantyfikatorów)
4.
5. (rozdzielność względem )
6. (rozdzielność względem )
7.
8.
9.
Przed dowodem zauwa\
my, \
e intuicyjnie formuły te istotnie zawsze oznaczają zdania prawdziwe.
Dowód. Udowodnimy niektóre punkty. (1) Udowodnimy, \
e jest tautologią. W
tym celu rozwa\
my dowolną konkretną funkcję zdaniową . Wystarczy pokazać, \
e zdania
i są równowa\
ne. Niech
Zatem i są rozłączne (prawo sprzeczności) i w sumie dają cały zbiór (prawo wyłączonego
środka). Korzystając z definicji kwantyfikatorów dostajemy ciąg zdań równowa\
nych
który świadczy o \
ądanej równowa\
ności.
(2) Obie strony równowa\
ności mówią, \
e , dlatego są
równowa\
ne.
(4) Podobnie jak w punkcie (1) interpretujemy najpierw jako funkcję zdaniową na jakiejś
(dowolnej) przestrzeni . Mamy pokazać, \
e przy tej interpretacji zdanie
jest prawdziwe.
Niech oznacza wykres funkcji zdaniowej . Zatem oznacza dokładnie, \
e
jeśli pewne cięcie pionowe zbioru jest całym , to ka\
de cięcie poziome zbioru jest
niepuste.
By to udowodnić, załó\
my, \
e oraz . Znaczy to, \
e ka\
da para postaci , gdzie
, nale\
y do . Wobec tego dla ka\
dego mamy , gdy\
, więc .
W tym miejscu zwróćmy uwage, \
e implikacja odwrotna do (4)
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 i . Mamy pokazać, \
e zdania
są równowa\
ne. W tym celu oznaczmy przez wykres funkcji zdaniowej , zaś przez wykres
funkcji zdaniowej . Wówczas zbiór jest wykresem funkcji zdaniowej . Dlatego
mamy następujący ciąg zdań równowa\
nych.
co kończy dowód.
Dowody pozostałych punktów jedną z powy\
szych metod pozostawiamy jako ćwiczenie.
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 piszemy i podobnie dla .
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 prawdziwa jest równość .
Oczywiście równość nie jest zdaniem, w tym przypadku jednak domyślnie rozumie się, \
e
chodzi tu o prawdziwość zdania , 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
oznacza zbiór mę\
czyzn, zaś zbiór kobiet. Na zbiorach tym rozwa\
amy relację bycia synem, tzn.
fakt, \
e mę\
czyzna i kobieta są w relacji oznacza dokładnie, \
e jest synem . Zwróćmy
uwagę, \
e relacja jest w pełni opisana przez zbiór
(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 i nazywamy dowolny podzbiór produktu kartezjańskiego
. W tym przypadku fakt, \
e elementy i są w relacji zapisujemy na dowolny z
poni\
szych sposobów.
1. (sposób teoriomnogościowy)
2.
3.
Zwróćmy uwagę, \
e ka\
dy ze sposobów 1-3 z definicji 7.4 jest symbolicznym sposobem zapisu funkcji
zdaniowej `` i są w relacji '', gdzie zakres to , zaś zakres to . Relacja , jako podzbiór
produktu , 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 relacja -argumentowa na zbiorach to
dowolny podzbiór produktu kartezjańskiego . Dla relację nazywamy te\

relacją unarną. W przypadku, gdy
mówimy, \
e jest to relacja -argumentowa na zbiorze . Funkcję zdaniową `` są w relacji ''
w przypadku zapisujemy w sposób 2. z definicji 7.4, w przypadku zapisujemy ją w sposób 1.
lub 2. Jeśli nie określamy jawnie liczby argumentów relacji (tzn. jej arności), to w domyśle zakładamy,
\
e jest to relacja binarna.
W przypadku relacji binarnej na zbiorach i definiujemy dziedzinę i obraz relacji jako zbiory
Zauwa\
my, \
e wtedy , czyli jest te\
relacją na zbiorach i .
Widzimy te\
, \
e w istocie to rzut na pierwszą oś, a to rzut na drugą oś7.1.
Definiujemy te\
relację odwrotną do relacji wzorem
Mamy zatem dla wszystkich . jest więc relacją na zbiorach i .
Gdy jest relacją na zbiorze oraz jest podzbiorem , to definiujemy ograniczenie (obcięcie)
relacji do zbioru wzorem
W przypadku relacji na zbiorach skończonych wygodnie jest przedstawiać ją graficznie w postaci
diagramu. Strzałka od do oznacza .
Poni\
ej zamieszczamy przykład diagramu relacji na zbiorze .
Przykłady. 1. Relacja pusta jest -argumentowa dla wszystkich .
2. Relacja porządku na zbiorze liczb rzeczywistych.
3. Relacja równoległości na zbiorze prostych na płaszczyz
nie.
4. Relacja podzielności na zbiorze liczb naturalnych
.
5. Relacja inkluzji na zbiorze potęgowym dla ustalonego zbioru .
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
W tym przypadku przyjmujemy i definiujemy (sugerujemy narysowanie
diagramu relacji ). Wtedy zdanie jest prawdziwe, zaś
jest fałszywe. Zatem implikacja
jest fałszywa, co pokazuje, \
e nie jest
tautologią rachunku kwantyfikatorów.
Rozwa\
a się ró\
ne własności relacji na zbiorze .
Definicja 7..5 Załó\
my, \
e jest relacją na zbiorze .
1. jest zwrotna .
2. jest przechodnia (tranzytywna) .
3. jest symetryczna .
4. jest antysymetryczna .
5. jest spójna .
Jako ćwiczenie pozostawiamy stwierdzenie, jak przy pomocy diagramu relacji rozpoznać powy\
sze
własności.
W powy\
szych przykładach relacji, relacja pusta jest przechodnia, symetryczna, antysymetryczna, lecz
nie jest zwrotna ani spójna (na niepustym zbiorze ).
Relacja na zbiorze jest zwrotna, przechodnia, antysymetryczna i spójna.
Relacja równoległości na zbiorze prostych na płaszczyz
nie jest zwrotna, symetryczna i przechodnia,
lecz nie jest antysymetryczna ani spójna.
Relacja podzielności na zbiorze jest zwrotna, przechodnia, antysymetryczna, lecz nie jest symetryczna
ani spójna.
Relacja inkluzji na zbiorze jest zwrotna, przechodnia, antysymetryczna, lecz nie jest spójna ani
symetryczna (gdy 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.