Logika i teoria mnogości/Wykład 3: Rachunek predykatów, przykład teorii w rachunku predykatów: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 465: Linia 465:
 
Twierdzeniem rachunku predykatów nazywamy dowolną formułę którą da się dowieść z aksjomatów rachunku predykatów.
 
Twierdzeniem rachunku predykatów nazywamy dowolną formułę którą da się dowieść z aksjomatów rachunku predykatów.
 
}}
 
}}
{{przyklad|3.3.||
+
{{przyklad|3.3.|| Formalne dowody twierdzeń rachunku predykatów są zwykle skomplikowane. Dlatego w rozważanym przykładzie poczynimy kilka uproszczeń. Będziemy się zajmować formułą
 +
<center><math>\displaystyle p(t) \Rightarrow \exists_x p(x).
 +
</math></center>
 +
 
 +
Zamiast dowodzić dokładnie powyższą formułę, dowiedziemy podobny fakt, a mianowicie, że jeśli dołączymy do zbioru aksjomatów formułę <math>\displaystyle p(t)</math>, to będziemy w stanie udowodnić <math>\displaystyle \exists_x p(x)</math>. Twierdzenie o dedukcji, które można znaleźć w wykładzie [[Logika dla informatyków]], mówi, że te podejścia są równoważne.
 +
 
 +
W poniższym dowodzie pominiemy również dowód formuły <math>\displaystyle \neg \neg \forall_x \neg p(x) \Rightarrow  \forall_x \neg p(x)</math>. Formuła ta pasuje do schematu <math>\displaystyle \neg \neg \phi \Rightarrow \phi</math>. Łatwo więc sprawdzić, że formuła <math>\displaystyle \neg \neg \phi \Rightarrow \phi</math> jest tautologią klasycznego rachunku zdań, a więc -- w myśl twierdzenia Posta (patrz [[Logika i teoria mnogości/Wykład 2: Rachunek zdań#twierdzenie_4_4|Wykład 2, Twierdzenie 4.4]]) -- ma dowód. Po zastąpieniu w tym dowodzie zmiennej <math>\displaystyle \phi</math> formułą <math>\displaystyle \forall_x \neg p(x)</math>, otrzymamy dowód formuły <math>\displaystyle \neg \neg \forall_x \neg p(x) \Rightarrow  \forall_x \neg p(x)</math>.
 +
 
 +
Przestawiamy uproszczony dowód formuły <math>\displaystyle p(t) \Rightarrow \exists_x p(x)</math>:
 +
# <math>\displaystyle \neg \neg \forall_x \neg p(x) \Rightarrow  \forall_x \neg p(x)</math> (patrz komentarz powyżej)
 +
# <math>\displaystyle (\forall_x \neg p(x)) \Rightarrow \neg p(t)</math> (aksjomat 2a)
 +
# <math>\displaystyle [(\forall_x \neg p(x)) \Rightarrow \neg p(t)] \Rightarrow ([\neg \neg \forall_x \neg p(x)] \Rightarrow  [(\forall_x \neg p(x)) \Rightarrow \neg p(t)])</math> (aksjomat 1a)
 +
# <math>\displaystyle [\neg \neg \forall_x \neg p(x)] \Rightarrow  [(\forall_x \neg p(x)) \Rightarrow \neg p(t)]</math> (MP z 2 i 3)
 +
# <math>\displaystyle ([\neg \neg \forall_x \neg p(x)] \Rightarrow  [(\forall_x \neg p(x)) \Rightarrow \neg p(t)])
 +
            \Rightarrow [(\neg \neg \forall_x \neg p(x) \Rightarrow  \forall_x \neg p(x)) \Rightarrow
 +
            [(\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)]]</math> (aksjomat 1b)
 +
# <math>\displaystyle (\neg \neg \forall_x \neg p(x) \Rightarrow  \forall_x \neg p(x)) \Rightarrow
 +
            [(\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)]</math> (MP z 4 i 5)
 +
# <math>\displaystyle (\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)</math> (MP z 6 i 1)
 +
# <math>\displaystyle p(t) \Rightarrow ([\neg \neg \forall_x \neg p(x)]\Rightarrow p(t))</math> (aksjomat 1a)
 +
# <math>\displaystyle p(t)</math> (dołączyliśmy tę formułę jako aksjomat)
 +
# <math>\displaystyle [\neg \neg \forall_x \neg p(x)]\Rightarrow p(t)</math> (MP z 8 i 9)
 +
# <math>\displaystyle ([\neg \neg \forall_x \neg p(x)]\Rightarrow p(t)) \Rightarrow [((\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)) \Rightarrow \neg \forall_x \neg p(x)]</math> (aksjomat 1c)
 +
# <math>\displaystyle (\neg \neg \forall_x \neg p(x))\Rightarrow \neg p(t)) \Rightarrow \neg \forall_x \neg p(x)</math> (MP z 10 i 11)
 +
# <math>\displaystyle \neg \forall_x \neg p(x)</math> (MP z 7 i 12)
 
   
 
   
np. <math>p(t) \Rightarrow \exists_x p(x)</math>.
+
Ostatnia formuła to dokładnie <math>\displaystyle \exists_x p(x)</math> po rozpisaniu skrótu <math>\displaystyle \exists</math>.
 
}}
 
}}
  

Wersja z 18:46, 25 wrz 2006

Wprowadzenie

Na początku rozdziału o logice zdaniowej rozważaliśmy zdanie

Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą pierwszą to Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą nieparzystą lub Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest równe 2.

Opisaliśmy je wtedy formułą

w której odpowiadały odpowiednio zdaniom

1. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą pierwszą,
2. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą nieparzystą,
3. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest równe 2.

Podstawiając zamiast zdania Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą pierwszą zmienną zdaniową Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} ukrywamy jednak część informacji. Zdanie to mówi przecież o pewnej liczbie Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} , co więcej zdania i Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{r}} dotyczą tej samej liczby Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} . Zapiszmy więc zamiast aby podkreślić fakt że prawdziwość zależy od tego jaką konkretną wartość przypiszemy zmiennej Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} . Zdanie będzie prawdziwe jeśli za Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} podstawimy jakąś liczbę pierwszą i fałszywe w przeciwnym przypadku. Zgodnie z tą konwencją nasze zdanie przyjmie postać

Zwróćmy uwagę jednak, że trudno ocenić prawdziwość zdania Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} dopóki nie podstawimy w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jakiejś konkretnej liczby. Z drugiej strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} zdanie będzie prawdziwe. Możemy więc przeformułować je jako

Dla każdej liczby naturalnej Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} , jeśli Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą pierwszą to Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą nieparzystą lub Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest równe 2.

Aby móc formalnie zapisywać zdania takie jak powyższe wprowadzimy kwantyfikator który będzie oznaczał ,,dla każdego" oraz który będzie oznaczał ,,istnieje". Każde wystąpienie kwantyfikatora będzie dotyczyło pewnej zmiennej. W naszym przykładzie napiszemy

Możemy teraz powiedzieć, że powyższa formuła jest prawdziwa w zbiorze liczb naturalnych, gdzie będą oznaczać odpowiednio Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą pierwszą, Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest liczbą nieparzystą, Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{n}} jest równe 2.

Przy tej samej interpretacji moglibyśmy wyrazić zdanie

Istnieje parzysta liczba pierwsza.

jako

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
4. symboli predykatów
5. spójników logicznych:
6. kwantyfikatorów:
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 są termami, a jest symbolem funkcyjnym, to 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, są symbolami zmiennych a są symbolami funkcji to poniższe napisy będą termami

1.
2.
3.
4.

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.
2.
3.
4.

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 są termami, a jest symbolem predykatu, to jest formułą atomową.

Przykład 2.5.

Kontynuując przykład dotyczący termów przyjmijmy dodatkowo, że w rozważanym języku są symbolami predykatów wtedy formułami atomowymi będą

1.
2.
3.

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

1.
2.
3.

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 , który przyjmuje wartość prawdy jeśli 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 przyjmuje on wartość prawdy wtedy kiedy Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest tą samą liczbą co Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} i fałszu w przeciwnym przypadku. Formuły atomowe będą opisywały proste zdania typu Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest liczbą pierwszą, Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} dzieli Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} , Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest równe Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{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 nie jest formułą atomową ani termem. Gdyby predykat Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{q}} oznaczał np. bycie liczbą nieparzystą to powyższy napis powinniśmy przeczytać jako

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 Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} i są formułami, to oraz są formułami.
3. Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} jest formułą i Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest zmienną, to 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

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

Ćwiczenie 2.1

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

1.
2.
3.
4.
5.
Rozwiązanie

Często będziemy używać dodatkowych spójników . Ponieważ wszystkie dadzą się zdefiniować przy pomocy i 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.
2.
3.

Kwantyfikator egzystencjalny

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

Nieformalnie kwantyfikator egzystencjalny mówi o tym, że istnieje jakiś obiekt, który podstawiony w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} uczyni formułę prawdziwą. Zdefiniowaliśmy go poprzez równoważne stwierdzenie które mówi że nieprawdą jest, że każdy obiekt podstawiony w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} falsyfikuje . Zgodnie z powyższą konwencją formułę ze wstępu

powinniśmy rozumieć jako

Kwantyfikatory ograniczone

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

1.
2.

i czytamy

1. dla każdego Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} które spełnia spełnione jest
2. istnieje Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} spełniające które spełnia

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

Podobnie formułę 1.2 zapiszemy jako

Ćwiczenie 2.2

Wyeliminuj wszystkie skróty z napisu

Podpowiedź 1
Podpowiedź 2
Rozwiązanie

Zmienne wolne i związane

Jeśli Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest zmienną, a jest formułą to każda pozycję w napisie na której występuje symbol Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} i nie jest poprzedzony bezpośrednio kwantyfikatorem, nazywamy wystąpieniem zmiennej Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{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 jest formułą atomową to wszystkie wystąpienia zmiennych w napisie wolne.
2. Jeśli formuła jest postaci lub to wystąpienia zmiennych pozostają takie same jak wystąpienia w w oraz .
3. Jeśli formuła jest postaci to wszystkie wystąpienia zmiennej Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} w związane, a wystąpienia innych zmiennych pozostają takie jak w .

Przykład 2.10.

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

1. w formule wszystkie wystąpienia zmiennych są wolne. Zmienna ma dwa wystąpienia a zmienna jedno.
2. w formule wszystkie wystąpienia zmiennej są wolne, i wszystkie wystąpienia zmiennej są związane     (nadal są tylko dwa wystąpienia ponieważ zgodnie z definicją nie liczymy symbolu w )
3. w formule wszystkie wystąpienia zmiennych oraz są związane
4. w formule zmienna ma jedno wystąpienie wolne (pierwsze) i jedno związane (drugie).
5. w formule obydwa wystąpienia zmiennej są związane.

Ćwiczenie 2.3

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

1.
2.
3.
4.
5.
Rozwiązanie

Definicja 2.11.

Formułę nazywamy domkniętą jeśli żadna zmienna nie ma wolnych wystąpień w .

Ćwiczenie 2.4

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

Rozwiązanie

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 , wstawiając w miejsce stałą , otrzymamy .

Definicja 2.10.

Przez będziemy oznaczać formułę powstałą przez zastąpienie wszystkich wolnych wystąpień zmiennej w formule termem . Pisząc zakładamy również, że w formule żadna ze zmiennych występujących w termie nie występuje w .

Aksjomatyka Rachunku Predykatów

Rachunek predykatów podobnie jak klasyczny rachunek zdań może być wprowadzony aksjomatycznie. Pierwsza grupa aksjomatów to aksjomaty klasycznego rachunku zdań. Druga dotyczy kwantyfikatora oraz jego interakcji z implikacją. Przypomnijmy, że kwantyfikator traktujemy jako pewien skrót zapisu.

Definicja 3.1.

Schematy aksjomatów rachunku predykatów

1. (Aksjomaty logiki zdaniowej) Każda formuła pasująca do któregokolwiek z poniższych schematów jest tautologią
(a)
(b)
(c)
2. (Aksjomaty dotyczące kwantyfikatora)
(a) Dla dowolnej formuły oraz termu następująca formuła jest aksjomatem (uwaga na podstawienie)
(b) Dla dowolnej formuły oraz zmiennej Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} , która nie ma wolnych wystąpień w następująca formuła jest aksjomatem
(c) Dla dowolnych formuł i aksjomatem jest formuła

Podobnie jak w rachunku zdań dowodem formuły nazwiemy ciąg formuł taki, że jest tym samym napisem co a każda formuła dla jest aksjomatem rachunku predykatów lub powstaje z dwóch formuł występujących wcześniej w dowodzie poprzez zastosowanie reguły Modus Ponens z Wykładu 2.

Definicja 3.2.

Twierdzeniem rachunku predykatów nazywamy dowolną formułę którą da się dowieść z aksjomatów rachunku predykatów.

Przykład 3.3.

Formalne dowody twierdzeń rachunku predykatów są zwykle skomplikowane. Dlatego w rozważanym przykładzie poczynimy kilka uproszczeń. Będziemy się zajmować formułą

Zamiast dowodzić dokładnie powyższą formułę, dowiedziemy podobny fakt, a mianowicie, że jeśli dołączymy do zbioru aksjomatów formułę , to będziemy w stanie udowodnić . Twierdzenie o dedukcji, które można znaleźć w wykładzie Logika dla informatyków, mówi, że te podejścia są równoważne.

W poniższym dowodzie pominiemy również dowód formuły . Formuła ta pasuje do schematu . Łatwo więc sprawdzić, że formuła jest tautologią klasycznego rachunku zdań, a więc -- w myśl twierdzenia Posta (patrz Wykład 2, Twierdzenie 4.4) -- ma dowód. Po zastąpieniu w tym dowodzie zmiennej formułą , otrzymamy dowód formuły .

Przestawiamy uproszczony dowód formuły :

  1. (patrz komentarz powyżej)
  2. (aksjomat 2a)
  3. (aksjomat 1a)
  4. (MP z 2 i 3)
  5. (aksjomat 1b)
  6. (MP z 4 i 5)
  7. (MP z 6 i 1)
  8. (aksjomat 1a)
  9. (dołączyliśmy tę formułę jako aksjomat)
  10. (MP z 8 i 9)
  11. (aksjomat 1c)
  12. (MP z 10 i 11)
  13. (MP z 7 i 12)

Ostatnia formuła to dokładnie po rozpisaniu skrótu .

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


Sytuacja 1.

Przypuśćmy, że to zdanie mówi o liczbach naturalnych, a jest prawdą wtedy i tylko wtedy gdy liczba Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest silnie mniejsza od liczby Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{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 jest prawdą wtedy i tylko wtedy gdy liczba Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest silnie mniejsza od liczby Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} . Wtedy zdanie to powinniśmy uznać prawdziwe. Istotnie, dla każdej liczby całkowitej Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} możemy dobrać liczbę Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} (na przykład równą ) która jest od niej silnie mniejsza.

Sytuacja 3.

Przypuśćmy, że to zdanie mówi o liczbach naturalnych, a jest prawdą wtedy i tylko wtedy gdy liczba Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest równa liczbie Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} . Wtedy zdanie to powinniśmy uznać prawdziwe (do każdej liczby Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} możemy dobrać liczbę Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} tak aby była równa Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{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 ) oraz jak interpretujemy symbole funkcyjne i predykatywne (w naszym przykładzie występował jedynie symbol predykatywny 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 , gdzie:

1. - jest niepustym zbiorem (dziedziną).
2. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{I}} - jest interpretacją symboli języka taką, że:
(a) dla symboli stałych: (symbole stałych są interpretowane jako elementy dziedziny)
(b) dla symboli funkcyjnych: , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{k}} jest ilością argumentów Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{f}} (symbole funkcyjne są interpretowane jako funkcje z potęgi dziedziny w dziedzinę)
(c) dla symboli predykatów: , gdzie jest ilością argumentów Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{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 jest odpowiedni dla formuły jeśli są w nim zdefiniowane interpretacje wszystkich symboli stałych funkcji oraz predykatów występujących w formule .

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

Definicja 4.4.

Wartościowanie zmiennych modelu to funkcja która zmiennym przypisuje wartości dziedziny.

Jeśli ustalimy już ocenę 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 wartościowanie zmiennych możemy rozszerzyć na wszytekie termy. Oznaczymy je przez . Rozszerzenie definiujemy w następujący sposób

1. jeśli term Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{t}} jest zmienną,
2. jeśli term Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{t}} jest stałą, to (stałe wartościujemy zgodnie z interpretacją w modelu)
3. jeśli term Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{t}} jest postaci , to

czyli aby poznać wartość termu najpierw obliczamy wartości poddtermów a potem obliczamy wartość funkcji odpowiadającej w modelu symbolowi Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{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 jest symbolem stałej, symbole są symbolami funkcji, symbole są symbolami predykatów, są zmiennymi. Ustalmy model w którym dziedziną jest zbiór liczb naturalnych, a symbole są interpretowane zgodnie z ich zwyczajowym znaczeniem (Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{s}} będziemy interpretować jako jednoargumentową funkcję która każdej liczbie przypisuje liczbę większą o jeden, interpretujemy jako 0). Jeśli ustalimy ocenę zmiennych tak, że to

1. term będzie wartościowany na 5
2. term będzie wartościowany na 3
3. term będzie wartościowany na 0 (zgodnie z interpretacją stałych)
4 term będzie wartościowany na 6

Definicja 4.7. [Waluacja formuł]

Zdefiniujemy teraz prawdziwość formuł w ustalonym modelu przy ustalonym wartościowaniu zmiennych .

1. Jeśli formuła jest postaci (czyli jest formułą atomową), to jest ona prawdziwa wtedy i tylko wtedy jeśli wartością predykatu odpowiadającego w modelu symbolowi Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} (czyli ) na elementach dziedziny odpowiadających termom jest prawdą.
2. Jeśli formuła jest postaci , to jest ona prawdziwa wtedy i tylko wtedy, gdy formuła Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} jest wartościowana na fałsz lub formuła jest wartościowana na prawdę (zgodnie z tabelą dla implikacji ??)
3. Jeśli formuła jest postaci to jest ona prawdziwa wtedy i tylko wtedy gdy formuła Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} jest wartościowana na fałsz (zgodnie z tabelą dla negacji ??)
4. Jeśli formuła jest postaci , to jest ona prawdziwa jeśli prawdziwe jest Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} i dla każdego wartościowania zmiennych różniącego się od co najwyżej interpretacją symbolu Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} prawdziwe jest Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} .
5. Jeśli formuła jest postaci , to jest ona prawdziwa jeśli istnieje ocena zmiennych różniąca się od co najwyżej interpretacją symbolu Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} taka, że przy tej ocenie prawdziwe jest Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} .

Interpretacje kwantyfikatorów, jest w gruncie rzeczy bardzo intuicyjna. Formuła jest prawdziwa wtedy i tylko wtedy gdy dla każdego elementu dziedziny ,,podstawionego" w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} w formule Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} prawdziwa jest formuła Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} (uwaga! podstawiamy jedynie w miejsca wolnych wystąpień Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} ). Analogicznie formuła jest prawdziwa wtedy i tylko wtedy gdy istnieje taki element dziedziny, który ,,podstawiony" w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} w formule Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{A}} uczyni ją prawdziwa. Dotąd rozważaliśmy kwantyfikator 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

jest prawdziwa w modelu z przykładu 4.6 przy ocenie zmiennych takiej, że , oraz że jest fałszywa w tym samym modelu dla przy ocenie zmiennej takiej, że (bo na przykład wartościując Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} na 3 formuła 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ć

Definicja 4.9.

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

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

Rozważmy dowolny model odpowiedni dla powyższej formuły (odpowiedni to znaczy taki który ustala interpretację symbolu predykatywnego Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} ). Jeśli w tym modelu nie jest prawdziwa formuła 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 . Weźmy dowolny taki model i oznaczmy go przez . Aby pokazać, że jest prawdziwe w wystarczy wskazać że istnieje w dziedzinie taka wartość, że podstawiona w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} uczyni predykat oznaczony przez Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} prawdziwym. Formuła jest prawdziwa w więc każda wartość podstawiona pod Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} czyni predykat odpowiadający Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} prawdziwym. Ponieważ dziedzina modelu 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 jest prawdziwy niezależnie od tego co podstawimy w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} , to rzeczywiście istnieje taki element dziedziny, który podstawiony w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} uczyni formułę prawdziwą. A więc formuła również jest prawdziwa. Wobec tego cała implikacja 4.1 jest prawdziwa w . 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.

Kurt Goedel (1906-1978)
Zobacz biografię

Twierdzenie 4.11. [Kurt Gödel]

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 , którego dziedziną będą liczby naturalne, oraz w którym jest jeden predykat binarny oznaczony symbolem Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{p}} , który przyjmuje wartość prawdy jeśli pierwszy z jego argumentów dzieli drugi. Napisz formuły które w modelu są równowążne następującym zdaniom (w kolejnych formułach można wykorzystywać skróty dla formuł zdefiniowanych wcześniej)

1. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest równe Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
2. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest zerem
3. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest jedynką
4. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest liczbą pierwszą
5. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest kwadratem pewnej liczby pierwszej
6. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest iloczynem dwóch różnych liczb pierwszych
7. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest iloczynem dwóch liczb pierwszych
8. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{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 Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} są względnie pierwsze
Podpowiedź
Rozwiązanie

Ćwiczenie 4.2

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

1. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest równe Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
2. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest nadzbiorem Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
3. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest punktem
4. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest odcinkiem
5. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest okręgiem
6. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest równoległe do Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
7. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} mają dokładenie jeden punkt wspólny
8. okręgi Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} są do siebie styczne
9. okręgi Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} są do siebie wewnętrznie styczne i okrąg Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest okręgiem wewnętrznym
10. okręgi Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} są do siebie zewnętrzenie styczne
11. punkt Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest końcem odcinka Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
12. odcinek Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest styczny do okręgu Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
13. okręgi Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}} mają taką samą średnicę
14. okrąg Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} ma średnicę mniejszą niż okrąg Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
15. odcinek Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest krótszy od odcinka Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
16. odcinek Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest średnicą okręgu Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
17. Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{x}} jest prostopadłe do Parser nie mógł rozpoznać (nieznana funkcja „\textnormal”): {\displaystyle \textnormal{y}}
18. odcinki tworzą kwadrat
Podpowiedź

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

Ćwiczenie 4.4

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

1.
2.
3.
4.
5.
6. ...
Rozwiązanie

Ćwiczenie 4.5

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

1.
2.
3.
4.
5.
6.

Ćwiczenie 4.6

Rozważmy formułę

(golibroda goli wszystkich tych i tylko tych, którzy nie golą się sami). Udowodnij, że nie istnieje model dla powyższej formuły.

Rozwiązanie