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) \)

Rozwiązanie

termy: \( x,y,s(x),s(y) \)

formuły atomowe: \( s(x)=s(y),x=y \)

termy: \( x,s(x),0 \)

formuły atomowe: \( s(x)=0 \)

termy: \( x,0,y,s(y) \)

formuły atomowe: \( x=0, s(y)=x \)

termy: \( x,0,x+0 \)

formuły atomowe: \( x+0=x \)

termy: \( x,y,s(y),x+y,s(x+y) \)

formuły atomowe: \( 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 \)

Podpowiedź 1

eliminacja kwantyfikatora ograniczonego:

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

Podpowiedź 2

eliminacja kwantyfikatora egzystencjalnego

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

Rozwiązanie

Pozostało jedynie wyeliminować \( \wedge \)

\( \neg \forall_x \neg(\phi \wedge \psi) \stackrel{\textrm{def}}{\equiv} \neg \forall_x \neg(\neg(\phi \Rightarrow \neg \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)) \)

Rozwiązanie

1. \( p(z) \Rightarrow \exists_z p(\underline{z}) \)

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

3. \( q(\underline{x},\underline{y}) \Rightarrow \forall_x (q(x,\underline{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(\underline{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?

Rozwiązanie

Jedynie formuła \( \forall_x \exists_y q(x,y) \Rightarrow \exists_x \forall_y q(x,y) \) jest formułą domkniętą.

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 \).