Język rachunku predykatów

---

Podobnie jak dla rachunku zdań zaczniemy od zdefiniowania języka rachunku predykatów.
Definicja 2.1.
Alfabet języka rachunku predykatów składa się z:

1. symboli stałych (a,b,c,)

2. symboli zmiennych (x,y,z,)

3. symboli funkcji \( (f^1, f^2, f^3, \dots ,g^1,g^2,g^3, \dots ,h^1, h^2, h^3, \dots) \)

4. symboli predykatów \( (p^1, p^2, p^3, \dots ,q^1,q^2,q^3, \dots ,r^1, r^2, r^3, \dots) \)

5. spójników logicznych: \( \Rightarrow,\neg \)

6. kwantyfikatorów: \( \forall,\exists \)

7. nawiasów i przecinków (niekonieczne)

Przyjmujemy, że cztery pierwsze alfabety są nieskończone, w tym sensie że nigdy nam nie braknie ich symboli. Z każdym symbolem funkcyjnym oraz predykatywnym jest związana liczba (którą zapisujemy w indeksie górnym) która będzie oznaczała liczbę jego argumetów.
Zwykle będą nam wystarczały symbole wymienione w nawiasach. Zanim przystąpimy do konstrukcji formuł zdefiniujemy tzw. termy.
Definicja 2.2. [Termy]

1. każdy symbol stałej jest termem

2. każdy symbol zmiennej jest termem

3. jeśli \( t_1,..,t_n \) są termami, a \( \alpha^n \) jest symbolem funkcyjnym, to \( \alpha^n(t_1,..,t_n) \) jest termem

4. nic innego nie jest termem

Przykład 2.3.
Jeśli rozważymy język, w którym 1,2,3 są symbolami stałych, \( {x,y} \) są symbolami zmiennych a \( +^2,\times^2,-^1,s^1 \) są symbolami funkcji to poniższe napisy będą termami

1. \( +^2(1,x) \)

2. \( -^1(3) \)

3. \( s^1(-^1(3)) \)

4. \( \times^2(y,+^2(x,-^1(2))) \)

Dla uproszczenia zapisu będziemy często pomijać liczby opisujące ilość argumentów symbolu. Symbole binarne będziemy czasem zapisywać w notacji infiksowej. Zgodnie z tą konwencją powyższe termy możemy zapisać jako

1. \( 1+x \)

2. \( -3 \)

3. \( s(-3) \)

4. \( y\times(x+(-3)) \)

Kiedy będziemy mówić o modelach zobaczymy, że termy będą interpretowane jako elementy rozważanej dziedziny, np. jeśli tą dziedziną będą liczby naturalne to termy będą interpretowane jako liczby naturalne. Formuły rachunku predykatów zdefiniujemy w dwóch krokach. Zaczniemy od formuł atomowych.

Definicja 2.4. [Formuły atomowe]

Jeśli \( t_1,..,t_n \) są termami, a \( \beta^n \) jest symbolem predykatu, to \( \beta^n(t_1,..,t_n) \) jest formułą atomową.

Przykład 2.5.

Kontynuując przykład dotyczący termów przyjmijmy dodatkowo, że w rozważanym języku \( p^3, q^1, =^2 \) są symbolami predykatów wtedy formułami atomowymi będą

1. \( p^3(1+x,-3,y\times(x+(-3))) \)

2. \( q^1(1) \)

3. \( =^2(y\times(x+(-3)),2) \)

Stosując analogiczną konwencję jak dla termów powyższe formuły atomowe zapiszemy jako

1. \( p(1+x,-3,y\times(x+(-3))) \)

2. \( q(1) \)

3. \( y\times(x+(-3))=2 \)

Symbole predykatywne będą odpowiadały funkcjom, które elementom rozważanej dziedziny (lub parom, trójkom itd. elementów) przypisują wartość prawdy lub fałszu. Takie funkcje nazywamy predykatami. W przypadku liczb naturalnych możemy na przykład mówić o predykacie pierwszości \( p(n) \), który przyjmuje wartość prawdy jeśli \( n \) jest liczbą pierwszą i fałszu w przeciwnym przypadku. Podobnie możemy mówić o binarnym predykacie równości (zwyczajowo oznaczanym przez \( = \)). Dla argumentów \( {x,y} \) przyjmuje on wartość prawdy wtedy kiedy \( \mathrm{x} \) jest tą samą liczbą co \( \mathrm{y} \) i fałszu w przeciwnym przypadku. Formuły atomowe będą opisywały proste zdania typu \( \mathrm{x} \) jest liczbą pierwszą, \( \mathrm{x} \) dzieli \( \mathrm{y} \), \( \mathrm{x} \) jest równe \( \mathrm {y} \). Innymi słowy sprowadzają sie do stwierdzania czy dany zestaw argumentów ma pewną własność opisywaną predykatem.

Uwaga 2.6.

W oznaczeniach z poprzednich przykładów, napis \( y\times(x+(-3))=q(1) \) nie jest formułą atomową ani termem. Gdyby predykat \( \mathrm{q} \) oznaczał np. bycie liczbą nieparzystą to powyższy napis powinniśmy przeczytać jako

\( y\times(x+(-3)) \) jest równe temu, że 1 jest liczbą nieparzystą.

Nie wolno porównywać elementów dziedziny (opisywanych przez termy) z wartościami prawdy i fałszu.

Z formuł atomowych będziemy budować bardziej złożone formuły zgodnie z poniższą definicją

Definicja 2.7. [Formuły rachunku predykatów]

1. Formuły atomowe są formułami.

2. Jeśli \( \mathrm{A} \) i \( B \) są formułami, to \( (A \Rightarrow B) \) oraz \( \neg A \) są formułami.

3. Jeśli \( \mathrm {A} \) jest formułą i \(\mathrm {x} \) jest zmienną, to \( \forall_x A \) jest formułą.

4. Nic innego nie jest formułą.

Przyjmujemy analogiczną konwencję dotyczącą nawiasowania jak dla rachunku zdań.

Przykład 2.8.

W oznaczeniach z poprzednich przykładów poniższe napisy nie są formułami rachunku predykatów

• \( x+1 \)

• \( (x=1) \Rightarrow 2 \)

• \( \forall_x (x+y) \)

• \( \forall_x (\neg x) \)

Poniższe napisy są formułami rachunku predykatów

• \( x=1 \)

• \( x=1 \Rightarrow x=2 \)

• \( \forall_x q(x+y) \)

• \( \forall_x \neg (x=0) \)

• \( \forall_x \forall_z \neg (x=0) \)

• \( \forall_x \forall_y \neg (x=y) \)

Ćwiczenie 2.1

Z poniższych formuł wypisz wszytkie termy i formuły atomowe

1. \( \forall_x \forall_y (s(x)=s(y) \Rightarrow x=y) \)

2. \( \forall_x \neg s(x)=0 \)

3. \( \forall_x (\neg (x=0) \Rightarrow (\exists_y s(y)=x)) \)

4. \( \forall_x x+0=x \)

5. \( \forall_x \forall_y x+s(y)=s(x+y) \)

Często będziemy używać dodatkowych spójników \( \wedge, \vee, \Leftrightarrow \). Ponieważ wszystkie dadzą się zdefiniować przy pomocy \( \Rightarrow \) i \( \neg \) nie włączamy ich do języka, a napisy w których występują będziemy traktować jako skróty. Ustalmy poniższe definicje

1. \( \phi \vee \psi \stackrel{\textrm{def}}{\equiv} \neg \phi \Rightarrow \psi \)

2. \( \phi \wedge \psi \stackrel{\textrm{def}}{\equiv} \neg ( \phi \Rightarrow \neg \psi) \)

3. \( \phi \Leftrightarrow \psi \stackrel{\textrm{def}}{\equiv} (\phi \Rightarrow \psi) \wedge (\psi \Rightarrow \phi) \)

Kwantyfikator egzystencjalny

Wprowadzimy jeszcze jeden bardzo ważny skrót - kwantyfikator egzystencjalny, oznaczamy go przez \( \exists \) i definiujemy w następujący sposób

\( \exists_x \phi \stackrel{\textrm{def}}{\equiv} \neg (\forall_x \neg \phi) \)

Nieformalnie kwantyfikator egzystencjalny mówi o tym, że istnieje jakiś obiekt, który podstawiony w miejsce \( \mathrm{x} \) uczyni formułę \( {\phi} \) prawdziwą. Zdefiniowaliśmy go poprzez równoważne stwierdzenie które mówi że nieprawdą jest, że każdy obiekt podstawiony w miejsce \( \mathrm {x} \) falsyfikuje \( {\phi} \). Zgodnie z powyższą konwencją formułę ze wstępu

\( \exists_n [p(n) \wedge \neg q(n)] \)

powinniśmy rozumieć jako

\( \neg \forall_n \neg (p(n) \wedge \neg q(n)). \)

Kwantyfikatory ograniczone

Kwantyfikatory ograniczone są skrótami które definujemy następująco

1. \( \forall_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \forall_x \phi \Rightarrow \psi \)

2. \( \exists_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \exists_x \phi \wedge \psi \)

i czytamy

1. dla każdego \(\mathrm {x} \) które spełnia \( {\phi} \) spełnione jest \( {\psi} \)

2. istnieje \( \mathrm {x} \) spełniające \( {\phi} \) które spełnia \( {\psi} \)

Zgodnie z tą konwencją formułę 1.1 możemy zapisać następująco

\( \forall_{n:p(n)} q(n) \vee r(n). \)

Podobnie formułę 1.2 zapiszemy jako

\( \exists_{n:p(n)}\neg q(n) \)

Ćwiczenie 2.2

Wyeliminuj wszystkie skróty z napisu

\( \exists_{x:\phi} \psi \)

Zmienne wolne i związane

Jeśli \( \mathrm {x} \) jest zmienną, a \( {\phi} \) jest formułą to każda pozycję w napisie \( {\phi} \) na której występuje symbol \(\mathrm {x} \) i nie jest poprzedzony bezpośrednio kwantyfikatorem, nazywamy wystąpieniem zmiennej \( \mathrm {x} \). Wystąpienia dzielimy na wolne i związanie. Wystąpienie jest związane jeśli znajduje się ,,pod działaniem" jakiegoś kwantyfikatora.

Definicja 2.9.

Rodzaj wystąpienia zmiennej w formule określamy zgodnie z poniższymi regułami:

1. Jeśli \( {\gamma} \) jest formułą atomową to wszystkie wystąpienia zmiennych w napisie \( {\gamma} \) są wolne.

2. Jeśli formuła jest postaci \( \phi \Rightarrow \psi \) lub \( \neg \phi \) to wystąpienia zmiennych pozostają takie same jak wystąpienia w w \( {\phi} \) oraz \( {\psi} \).

3. Jeśli formuła jest postaci \( \forall_x \phi \) to wszystkie wystąpienia zmiennej \( \mathrm {x} \) w \( \forall_x \phi \) są związane, a wystąpienia innych zmiennych pozostają takie jak w \( \phi \).

Przykład 2.10.

Rozważamy język z przykładu 2.5 (patrz przykład 2.5.)

1. w formule \( y\times(x+(-3))=x \) wszystkie wystąpienia zmiennych są wolne. Zmienna \( x \) ma dwa wystąpienia a zmienna \( y \) jedno.

2. w formule \( \forall_x y\times(x+(-3))=x \) wszystkie wystąpienia zmiennej \( y \) są wolne, i wszystkie wystąpienia zmiennej \( x \) są związane     (nadal są tylko dwa wystąpienia \( x \) ponieważ zgodnie z definicją nie liczymy symbolu \( x \) w \( \forall_x \))

3. w formule \( \forall_x \exists_y y\times(x+(-3))=x \) wszystkie wystąpienia zmiennych \( x \) oraz \( y \) są związane

4. w formule \( x=2 \Rightarrow \exists_x x=2 \) zmienna \( x \) ma jedno wystąpienie wolne (pierwsze) i jedno związane (drugie).

5. w formule \( \forall_x (x=2 \Rightarrow \exists_x x=2) \) obydwa wystąpienia zmiennej \( x \) są związane.

Ćwiczenie2.3

W podanych poniżej formułach podkreśl wszystkie wolne wystąpienia zmiennych.

1. \( p(z) \Rightarrow \exists_z p(z) \)

2. \( \forall_y ((\exists_z q(y,z)) \Rightarrow q(y,z)) \)

3. \( q(x,y) \Rightarrow \forall_x (q(x,y)\Rightarrow (\forall_y q(x,y))) \)

4. \( \forall_x \exists_y q(x,y) \Rightarrow \exists_x \forall_y q(x,y) \)

5. \( (\exists_z p(z)) \Rightarrow (\forall_z q(z,z) \vee \exists_x q(z,x)) \)

Definicja 2.11.

Formułę \( {\phi} \) nazywamy domkniętą jeśli żadna zmienna nie ma wolnych wystąpień w \( {\phi} \).

Ćwiczenie 2.4

Które z formuł z ćwiczenia 2.3 są domknięte?

Podstawienia

Często będziemy w formułach zastępować wystąpienia zmiennych pewnymi termami. Częstym przykładem jest podstawienie w miejsce zmiennej pewnej stałej np. w formule \( \displaystyle \forall_x x+y >x \), wstawiając w miejsce \( \displaystyle y \) stałą \( \displaystyle 1 \), otrzymamy \( \displaystyle \forall_x x+1 >x \).

Definicja 2.10.

Przez \( [x arrow t]\phi \) będziemy oznaczać formułę powstałą przez zastąpienie wszystkich wolnych wystąpień zmiennej \( \displaystyle x \) w formule \( \displaystyle \phi \) termem \( \displaystyle t \). Pisząc \( [x arrow t]\phi \) zakładamy również, że w formule \( \displaystyle \phi \) żadna ze zmiennych występujących w termie \( \displaystyle t \) nie ma związanych wystąpień w \( \displaystyle \phi \).

Modele

---

Dotychczas wprowadziliśmy rachunek predykatów aksjomatycznie. Zaletą takiego definiowania jest niewielka ilość potrzebnych pojęć. Z drugiej strony jednak dowody z aksjomatów są żmudne i nie sprzyjają budowaniu intuicji. W przypadku rachunku zdań widzieliśmy, że ten sam zbiór formuł można równoważnie zdefiniować za pomocą matrycy Boolowskiej z Wykładu 2. Niestety w przypadku rachunku predykatów nie istnieje taka skończona struktura, która pozwalałaby nam stwierdzać czy formuła jest twierdzeniem. Zobaczymy jednak, że pewne struktury warto rozważać. Mówiąc o modelach będziemy musieli użyć naiwnej teorii zbiorów opisanej w pierwszym rozdziale. Decydujemy się na to nadużycie w celu zdobycia dobrych intuicji i sprawności w posługiwaniu się kwantyfikatorami.

Przykład 4.1.

Rozważmy następujące zdanie
\( \forall_x \exists_y x \prec y \)

Sytuacja 1.

Przypuśćmy, że to zdanie mówi o liczbach naturalnych, a \( x \prec y \) jest prawdą wtedy i tylko wtedy gdy liczba \( \mathrm {x} \) jest silnie mniejsza od liczby \( \mathrm {y} \). Wtedy zdanie to powinniśmy uznać za nieprawdziwe, gdyż dla liczby 0 nie istnieje silnie mniejsza liczba naturalna.

Sytuacja 2.

Przypuśćmy, że to zdanie mówi o liczbach całkowitych, a \( x \prec y \) jest prawdą wtedy i tylko wtedy gdy liczba \( \mathrm {x} \) jest silnie mniejsza od liczby \( \mathrm {y} \). Wtedy zdanie to powinniśmy uznać prawdziwe. Istotnie, dla każdej liczby całkowitej \( \mathrm {x} \) możemy dobrać liczbę \( \mathrm {y} \) (na przykład równą \( x-1 \)) która jest od niej silnie mniejsza.

Sytuacja 3.

Przypuśćmy, że to zdanie mówi o liczbach naturalnych, a \( x \prec y \) jest prawdą wtedy i tylko wtedy gdy liczba \(\mathrm {x} \) jest równa liczbie \( \mathrm {y} \). Wtedy zdanie to powinniśmy uznać prawdziwe (do każdej liczby \( \mathrm {x} \) możemy dobrać liczbę \( \mathrm {y} \) tak aby była równa \( \mathrm {x} \)).

Powyższe przykłady pokazują różne interpretacje tej samej formuły. Wydaje się również że prawdziwość zdania zmienia się w zależności od interpretacji. Aby mówić o interpretacji danej formuły powinniśmy powiedzieć w jakim zbiorze będziemy interpretować zmienne i stałe (w naszym przykładzie były to kolejno zbiory \( N, Z, N \)) oraz jak interpretujemy symbole funkcyjne i predykatywne (w naszym przykładzie występował jedynie symbol predykatywny \( \prec \) który był interpretowany kolejno jako silna mniejszość, silna mniejszość, równość). Poniżej definiujemy formalnie pojęcie modelu.

Definicja 4.2. [Model]

Modelem języka rachunku predykatów nazywamy \( M=(D,I) \), gdzie:

1. \( D \) - jest niepustym zbiorem (dziedziną).

2. \( \mathrm {I} \) - jest interpretacją symboli języka taką, że:

(a) dla symboli stałych: \( I(c)\in D \) (symbole stałych są interpretowane jako elementy dziedziny)

(b) dla symboli funkcyjnych: \( I(f):D^k \rightarrow D \), gdzie \( \mathrm {k} \) jest ilością argumentów \( \mathrm {f} \) (symbole funkcyjne są interpretowane jako funkcje z potęgi dziedziny w dziedzinę)

(c) dla symboli predykatów: \( I(p):D^k \rightarrow {0,1} \), gdzie \( k \) jest ilością argumentów \( \mathrm {p} \) (symbole predykatywne są interpretowane jako funkcje przekształcające ciągi elementów z dziedziny w prawdę lub fałsz)

Definicja 4.3.

Mówimy, że model \( M \) jest odpowiedni dla formuły \( {\phi} \) jeśli są w nim zdefiniowane interpretacje wszystkich symboli stałych funkcji oraz predykatów występujących w formule \( {\phi} \).

Zanim ustalimy co to znaczy że formuła jest prawdziwa w modelu zdefiniujemy tzw. wartościowanie zmiennych

Definicja 4.4.

Wartościowanie zmiennych modelu \( M=(D,I) \) to funkcja która zmiennym przypisuje wartości dziedziny.
Jeśli ustalimy już wartościowanie zmiennych w modelu to możemy też mówić o wartościach przyjmowanych przez termy.
Definicja 4.5. [Wartościowanie termów]

Przy ustalonym modelu \( M=(D,I) \) wartościowanie zmiennych \( \sigma \) możemy rozszerzyć na wszytekie termy. Oznaczymy je przez \( \hat{\sigma} \). Rozszerzenie definiujemy w następujący sposób

1. jeśli term \( \mathrm {t} \) jest zmienną, \( \hat{\sigma}(t) = \sigma(t) \)

2. jeśli term \( \mathrm {t} \) jest stałą, to \( \hat{\sigma}(t)=I(t) \) (stałe wartościujemy zgodnie z interpretacją w modelu)

3. jeśli term \( \mathrm {t} \) jest postaci \( f(t_0,..,t_n) \), to

\( \hat{\sigma}(f(t_0,..,t_n))= I(f)(\hat{\sigma}(t_0),..,\hat{\sigma}(t_n)) \)
czyli aby poznać wartość termu najpierw obliczamy wartości poddtermów a potem obliczamy wartość funkcji odpowiadającej w modelu \( M \) symbolowi \( \mathrm {f} \) na wartościach poddtermów. Funkcję wartościującą termy będziemy często oznaczali tym samym symbolem co wartościowanie zmiennych.

Przykład 4.6.

Przypuśćmy, że w rozważanym języku symbol \( o \) jest symbolem stałej, symbole \( s,+,\times \) są symbolami funkcji, symbole \( < ,= \) są symbolami predykatów, \( {x,y,z} \) są zmiennymi. Ustalmy model w którym dziedziną jest zbiór liczb naturalnych, a symbole są interpretowane zgodnie z ich zwyczajowym znaczeniem (\( \mathrm {s} \) będziemy interpretować jako jednoargumentową funkcję która każdej liczbie przypisuje liczbę większą o jeden, \( o \) interpretujemy jako 0). Jeśli ustalimy ocenę zmiennych tak, że \( \sigma(x)=2, \sigma(y)=3, \sigma(z)=5 \) to

1. term \( {x+y} \) będzie wartościowany na 5

2. term \( s(x) \) będzie wartościowany na 3

3. term \( o \) będzie wartościowany na 0 (zgodnie z interpretacją stałych)

4 term \( s(o) \times s(z) \) będzie wartościowany na 6

Definicja 4.7. [Waluacja formuł]

Zdefiniujemy teraz prawdziwość formuł w ustalonym modelu \( M=(D,I) \) przy ustalonym wartościowaniu zmiennych \( {\sigma} \).

1. Jeśli formuła jest postaci \( p(t_0,..,t_n) \) (czyli jest formułą atomową), to jest ona prawdziwa wtedy i tylko wtedy jeśli wartością predykatu odpowiadającego w modelu \( M \) symbolowi \( \mathrm {p} \) (czyli \( I(p) \)) na elementach dziedziny odpowiadających termom \( t_0, \dots, t_n \) jest prawdą.

2. Jeśli formuła jest postaci \( A\Rightarrow B \), to jest ona prawdziwa wtedy i tylko wtedy, gdy formuła \( \mathrm {A} \) jest wartościowana na fałsz lub formuła \( B \) jest wartościowana na prawdę (zgodnie z tabelą dla implikacji)

3. Jeśli formuła jest postaci \( \neg A \) to jest ona prawdziwa wtedy i tylko wtedy gdy formuła \( \mathrm {A} \) jest wartościowana na fałsz (zgodnie z tabelą dla negacji)

4. Jeśli formuła jest postaci \( \forall_x \; A \), to jest ona prawdziwa jeśli prawdziwe jest \( \mathrm {A} \) i dla każdego wartościowania zmiennych różniącego się od \( {\sigma} \) co najwyżej interpretacją symbolu \( \mathrm {x} \) prawdziwe jest \( \mathrm {A} \).

5. Jeśli formuła jest postaci \( \exists_x \; A \), to jest ona prawdziwa jeśli istnieje ocena zmiennych różniąca się od \( {\sigma} \) co najwyżej interpretacją symbolu \( \mathrm {x} \) taka, że przy tej ocenie prawdziwe jest \( \mathrm {A} \).

Interpretacje kwantyfikatorów, jest w gruncie rzeczy bardzo intuicyjna. Formuła \( \forall_x A \) jest prawdziwa wtedy i tylko wtedy gdy dla każdego elementu dziedziny ,,podstawionego" w miejsce \( \mathrm {x} \) w formule \( \mathrm {A} \) prawdziwa jest formuła \( \mathrm {A} \) (uwaga! podstawiamy jedynie w miejsca wolnych wystąpień \( \mathrm {x} \)). Analogicznie formuła \( \exists_x A \) jest prawdziwa wtedy i tylko wtedy gdy istnieje taki element dziedziny, który ,,podstawiony" w miejsce \( \mathrm {x} \) w formule \( \mathrm {A} \) uczyni ją prawdziwa. Dotąd rozważaliśmy kwantyfikator \( \exists \) jako skrót pewnego napisu, jednak ze względu na jego naturalną interpretacje zdecydowaliśmy się dodać go do definicji waluacji formuł. W ćwiczeniu 4 pokażemy, że zdefiniowana powyżej waluacja formuł z kwantyfikatorem egzystencjalnym jest zgodna z waluacją zdefiniowanego wcześniej skrótu.

Przykład 4.8.

Możemy teraz powiedzieć, że formuła

\( \forall_y (x < y \vee x=y) \)

jest prawdziwa w modelu z Przykładu 4.6 przy ocenie zmiennych \( \sigma_1 \) takiej, że \( \sigma_1(x)=0 \), oraz że jest fałszywa w tym samym modelu dla przy ocenie zmiennej \( \sigma_2 \) takiej, że \( \sigma_2(x)=7 \) (bo na przykład wartościując \( \mathrm {y} \) na 3 formuła \( x < y \vee x=y \) nie będzie prawdziwa).

Istnieją jednak formuły które są prawdziwe w modelu z Przykładu 4.6 niezależnie od oceny zmiennych. Przykładem może być
\( \forall_y (x < y+x \vee y=o). \)

Definicja 4.9.

Formuła \( {\phi} \) jest prawdziwa w modelu \( M \) jeśli jest prawdziwa w tym modelu przy każdej ocenie zmiennych. Mówimy wtedy, że model \( M \) jest modelem formuły \( {\phi} \).

Ciekawe, że istnieją również formuły które są prawdziwe we wszystkich modelach. Rozważmy formułę

\( (\forall_x p(x)) \Rightarrow (\exists_x p(x)). \quad \mbox{(4.1)} \)

Rozważmy dowolny model \( M \) odpowiedni dla powyższej formuły (odpowiedni to znaczy taki który ustala interpretację wszystkich symboli stałychm, funkcji i predykatów występujących w formule, w tym przypadku symbolu predykatywnego \( \mathrm {p} \)). Jeśli w tym modelu nie jest prawdziwa formuła \( (\forall_x p(x)) \) to cała implikacja 4.1 jest prawdziwa a więc wszystkie te modele są modelami formuły 4.1. Pozostają więc do rozważenia te modele w których prawdziwe jest \( (\forall_x p(x)) \). Weźmy dowolny taki model i oznaczmy go przez \( M \). Aby pokazać, że \( (\exists_x p(x)) \) jest prawdziwe w \( M \) wystarczy wskazać że istnieje w dziedzinie taka wartość, że podstawiona w miejsce \( \mathrm {x} \) uczyni predykat oznaczony przez \( \mathrm {p} \) prawdziwym. Formuła \( (\forall_x p(x)) \) jest prawdziwa w \( M \) więc każda wartość podstawiona pod \( \mathrm {x} \) czyni predykat odpowiadający \( \mathrm {p} \) prawdziwym. Ponieważ dziedzina modelu \( M \) zgodnie z definicją 4.2 nie może być pusta więc istnieje przynajmniej jeden element dziedziny. Ponieważ w dziedzinie istnieje przynajmiej jeden element, oraz że formuła \( {p(x)} \) jest prawdziwy niezależnie od tego co podstawimy w miejsce \( \mathrm {x} \), to rzeczywiście istnieje taki element dziedziny, który podstawiony w miejsce \( \mathrm {x} \) uczyni formułę \( {p(x)} \) prawdziwą. A więc formuła \( \exists_x p(x) \) również jest prawdziwa. Wobec tego cała implikacja 4.1 jest prawdziwa w \( M \). Pokazaliśmy więc, że formuła 4.1 jest prawdziwa w każdym modelu.

Definicja 4.10.

Formułę rachunku predykatów nazywamy tautologią rachunku predykatów jeśli jest prawdziwa w każdym odpowiednim dla niej modelu .

Podobnie jak klasycznym rachunku zdań, w rachunku predykatów również tautologie okazują się tym samym co twierdzenia. Mówi o tym następujące klasyczne twierdzenie udowodnione przez Kurta Gödela.

Formuła rachunku predykatów jest tautologią rachunku predykatów wtedy i tylko wtedy gdy jest twierdzeniem rachunku predykatów.

Dowód powyższego twierdzenia jest przedstawiony na wykładzie Logika dla informatyków. Zauważmy, że zgodnie z powyższym twierdzeniem aby udowodnić, że formuła nie jest twierdzeniem rachunku predykatów wystarczy wskazać model w którym nie jest prawdziwa.

Ćwiczenie 4.1

Rozważmy model \( M \), którego dziedziną będą liczby naturalne, oraz w którym jest jeden predykat binarny oznaczony symbolem \( \mathrm {p} \), który przyjmuje wartość prawdy jeśli pierwszy z jego argumentów dzieli drugi. Napisz formuły które w modelu \( M \) są równowążne następującym zdaniom (w kolejnych formułach można wykorzystywać skróty dla formuł zdefiniowanych wcześniej)

1. \( \mathrm {x} \) jest równe \( \mathrm {y} \)

2. \( \mathrm {x} \) jest zerem

3. \(\mathrm {x} \) jest jedynką

4. \( \mathrm {x} \) jest liczbą pierwszą

5. \( \mathrm {x} \) jest kwadratem pewnej liczby pierwszej

6. \( \mathrm {x} \) jest iloczynem dwóch różnych liczb pierwszych

7. \( \mathrm {x} \) jest iloczynem dwóch liczb pierwszych

8. \(\mathrm {x} \) jest potęgą liczby pierwszej

9. dla każdych dwóch liczb istnieje ich największy wspólny dzielnik

10. dla każdych dwóch liczb istnieje ich najmniejsza wspólna wielokrotność

11 liczby \( \mathrm {x} \) i \( \mathrm {y} \) są względnie pierwsze

Ćwiczenie 4.2

Rozważmy model \( M \), którego dziedziną będą wszytkie punkty, odcinki i okręgi płaszyczny, oraz w którym jest jeden predykat binarny oznaczony symbolem \( \mathrm {p} \), który przyjmuje wartość prawdy jeśli jego argumenty mają przynajmniej jeden punkt wspólny. Napisz formuły które w modelu \( M \) są równowążne następującym zdaniom (w kolejnych formułach można wykorzystywać skróty dla formuł zdefiniowanych wcześniej)

1. \( \mathrm {x} \) jest równe \( \mathrm {y} \)

2. \( \mathrm {x} \) jest nadzbiorem \( \mathrm {y} \)

3. \( \mathrm {x} \) jest punktem

4. \( \mathrm {x} \) jest odcinkiem

5. \( \mathrm {x} \) jest okręgiem

6. \( \mathrm {x} \) jest równoległe do \( \mathrm {y} \)

7. \( \mathrm {x} \) i \( \mathrm {y} \) mają dokładenie jeden punkt wspólny

8. okręgi \( \mathrm {x} \) i \( \mathrm {y} \) są do siebie styczne

9. okręgi \( \mathrm {x} \) i \( \mathrm {y} \) są do siebie wewnętrznie styczne i okrąg \( \mathrm {x} \) jest okręgiem wewnętrznym

10. okręgi \( \mathrm{x} \) i \( \mathrm {y} \) są do siebie zewnętrzenie styczne

11. punkt \(\mathrm {x} \) jest końcem odcinka \( \mathrm {y} \)

12. odcinek \(\mathrm {x} \) jest styczny do okręgu \( \mathrm {y} \)

13. okręgi \( \mathrm{x} \) i \( \mathrm {y} \) mają taką samą średnicę

14. okrąg \( \mathrm {x} \) ma średnicę mniejszą niż okrąg \( \mathrm {y} \)

Ćwiczenie 4.3

Napisz formuły które mówią:

• każdy odcinek ma dokładnie dwa końce

• dla każdego okręgu wszystkie jego średnice przecinają się w dokładnie jednym punkcie

• dla dowolnego odcinka istnieje dłuższy odcinek, który go zawiera

• dla dowolnych trzech punktów niewspółliniowych istnieje okrąg który przechodzi przez wszystkie trzy punkty

• istnieją dwa okręgi, które przecinają się w dokładnie 5 punktach.

Ćwiczenie4.4
Dla każdej z poniższych formuł znajdź model w którym jest prawdziwa oraz model w którym jest fałszywa

1. \( \forall_x \forall_y p(x,y) \Rightarrow p(y,x) \)

2. \( (\forall_x \exists_y p(x,y)) \Rightarrow \exists_y \forall_x p(x,y) \)

3. \( (\forall_x (p(x)\vee q(x))) \Rightarrow (\forall_x(p(x)) \vee \forall_x q(x)) \)

4. \( \forall_y [(\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(z)] \)

5. \( \forall_x \forall_y(p(x,y) \Rightarrow \exists_z (p(x,z)\wedge p(z,y)) \)

Ćwiczenie 4.5

Udowodnij, że w dowolnym ustalonym modelu \( M \) prawdziwe są następujące formuły

1. \( \forall_x p(x) \Rightarrow (p(c)) \)

2. \( p(c) \Rightarrow \forall_x p(c) \)

3. \( \forall_x(p(x) \Rightarrow q(x)) \Rightarrow ((\forall_x p(x))\Rightarrow(\forall_x q (x))) \)

4. \( \exists_x p(x) \Leftrightarrow \neg \forall_x \neg p(x) \)

5. \( \neg \forall_x p(x) \Leftrightarrow \exists_x \neg p(x) \)

6. \( \forall_x r(x, f(x)) \Rightarrow \forall_x \exists_y r(x,y) \)

Ćwiczenie 4.6

Rozważmy formułę \( \forall_x (\neg g(x,x) \Leftrightarrow g(b,x)) \) (golibroda \( b \) goli wszystkich tych i tylko tych, którzy nie golą się sami). Udowodnij, że nie istnieje model dla powyższej formuły.