Informatyka MIMUW

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

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$.