Test GR3

Wprowadzenie

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

Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą pierwszą to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą nieparzystą lub Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest równe 2.

Opisaliśmy je wtedy formułą

$p\Rightarrow (q\vee r).$

w której $p,q,r$ odpowiadały odpowiednio zdaniom

1. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą pierwszą,

2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą nieparzystą,

3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest równe 2.

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

$p(n)\Rightarrow (q(n)\vee r(n)).$

Zwróćmy uwagę jednak, że trudno ocenić prawdziwość zdania Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} dopóki nie podstawimy w miejsce Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jakiejś konkretnej liczby. Z drugiej strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce Parser nie mógł rozpoznać (błąd składni): {\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ć (błąd składni): {\displaystyle \textnormal{n}} , jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą pierwszą to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest liczbą nieparzystą lub Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{n}} jest równe 2.

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

${\mathrm{\forall }}_{n}p(n)\Rightarrow (q(n)\vee r(n)).$

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

Przy tej samej interpretacji $p(n),q(n)$ moglibyśmy wyrazić zdanie

Istnieje parzysta liczba pierwsza.

jako

${\mathrm{\exists }}_{n}p(n)\wedge \mathrm{\neg }q(n)$

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 ,\mathrm{\neg }$

6. kwantyfikatorów: $\mathrm{\forall },\mathrm{\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest tą samą liczbą co Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} i fałszu w przeciwnym przypadku. Formuły atomowe będą opisywały proste zdania typu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest liczbą pierwszą, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} dzieli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest równe Parser nie mógł rozpoznać (błąd składni): {\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 $y\times (x+(-3))=q(1)$ nie jest formułą atomową ani termem. Gdyby predykat Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{A}} i $B$ są formułami, to $(A\Rightarrow B)$ oraz $\mathrm{\neg }A$ są formułami.

3. Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{A}} jest formułą i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest zmienną, to ${\mathrm{\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$

• ${\mathrm{\forall }}_x(x+y)$

• ${\mathrm{\forall }}_x(\mathrm{\neg }x)$

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

• $x=1$

• $x=1\Rightarrow x=2$

• ${\mathrm{\forall }}_{x}q(x+y)$

• ${\mathrm{\forall }}_x\mathrm{\neg }(x=0)$

• ${\mathrm{\forall }}_x{\mathrm{\forall }}_z\mathrm{\neg }(x=0)$

• ${\mathrm{\forall }}_x{\mathrm{\forall }}_y\mathrm{\neg }(x=y)$

Ćwiczenie 2.1

{{{3}}}

Często będziemy używać dodatkowych spójników $\wedge ,\vee ,\iff$. Ponieważ wszystkie dadzą się zdefiniować przy pomocy $\Rightarrow$ i $\mathrm{\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. $\varphi \vee \psi \stackrel{\text{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }\varphi \Rightarrow (\varphi \Rightarrow \psi )$ (może jakoś inaczej?)

2. $\varphi \wedge \psi \stackrel{\text{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }\mathrm{\neg }(\varphi \Rightarrow \mathrm{\neg }\psi )$

3. $\varphi \iff \psi \stackrel{\text{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }(\varphi \Rightarrow \psi )\wedge (\psi \Rightarrow \varphi )$

Kwantyfikator egzystencjaly

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

${\mathrm{\exists }}_x\varphi \stackrel{\text{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }\mathrm{\neg }({\mathrm{\forall }}_x\mathrm{\neg }\varphi )$

Nieformalnie kwantyfikator egzystencjalny mówi o tym, że istnieje jakiś obiekt, który podstawiony w miejsce Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} uczyni formułę $\varphi$ 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ć (błąd składni): {\displaystyle \textnormal{x}} falsyfikuje $\varphi$. Zgodnie z powyższą konwencją formułę ze wstępu

${\mathrm{\exists }}_n[p(n)\wedge \mathrm{\neg }q(n)]$

powinniśmy rozumieć jako

$\mathrm{\neg }{\mathrm{\forall }}_n\mathrm{\neg }(p(n)\wedge \mathrm{\neg }q(n)).$

Kwantyfikatory ograniczone

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

1. ${\mathrm{\forall }}_{x:\varphi }\psi \stackrel{\text{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }{\mathrm{\forall }}_x\varphi \Rightarrow \psi$

2. ${\mathrm{\exists }}_{x:\varphi }\psi \stackrel{\text{<mrow data-mjx-texclass="ORD">def</mrow>}}{\equiv }{\mathrm{\exists }}_x\varphi \wedge \psi$

i czytamy

1. dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} które spełnia $\varphi$ spełnione jest $\psi$

2. istnieje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} spełniające $\varphi$ które spełnia $\psi$

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

${\mathrm{\forall }}_{n:p(n)}q(n)\vee r(n).$

Podobnie formułę ?? zapiszemy jako

${\mathrm{\exists }}_{n:p(n)}\mathrm{\neg }q(n)$

Ćwiczenie 2.2

{{{3}}}

Zmienne wolne i związane

Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest zmienną, a $\varphi$ jest formułą to każda pozycję w napisie $\varphi$ na której występuje symbol Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} i nie jest poprzedzony bezpośrednio kwantyfikatorem, nazywamy wystąpieniem zmiennej Parser nie mógł rozpoznać (błąd składni): {\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 $\gamma$ jest formułą atomową to wszystkie wystąpienia zmiennych w napisie $\gamma$ są wolne.

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

3. Jeśli formuła jest postaci ${\mathrm{\forall }}_x\varphi$ to wszystkie wystąpienia zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} w ${\mathrm{\forall }}_x\varphi$ są związane.

Przykład 2.10

Rozważamy język z przykładu 2.5

1. w formule $y\times (x+(-3))=x$ wszystkie wystąpienia zmiennych są wolne. Zmienna Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} ma dwa wystąpienia a zmienna Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} jedno.

2. w formule ${\mathrm{\forall }}_{x}y\times (x+(-3))=x$ wszystkie wystąpienia zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} są wolne, i wszystkie wystąpienia zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} są związane (nadal są tylko dwa wystąpienia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} ponieważ zgodnie z definicją nie liczymy symbolu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} w ${\mathrm{\forall }}_x$)

3. w formule ${\mathrm{\forall }}_x{\mathrm{\exists }}_{y}y\times (x+(-3))=x$ wszystkie wystąpienia zmiennych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} są związane

4. w formule $x=2\Rightarrow {\mathrm{\exists }}_{x}x=2$ zmienna Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} ma jedno wystąpienie wolne (pierwsze) i jedno związane (drugie).

5. w formule ${\mathrm{\forall }}_x(x=2\Rightarrow {\mathrm{\exists }}_{x}x=2)$ obydwa wystąpienia zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} są związane.

Ćwiczenie 2.3

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

1. $p(z)\Rightarrow {\mathrm{\exists }}_{z}p(z)$

2. ${\mathrm{\forall }}_y(({\mathrm{\exists }}_{z}q(y,z))\Rightarrow q(y,z))$

3. $q(x,y)\Rightarrow {\mathrm{\forall }}_x(q(x,y)\Rightarrow ({\mathrm{\forall }}_{y}q(x,y)))$

4. ${\mathrm{\forall }}_x{\mathrm{\exists }}_{y}q(x,y)\Rightarrow {\mathrm{\exists }}_x{\mathrm{\forall }}_{y}q(x,y)$

5. $({\mathrm{\exists }}_{z}p(z))\Rightarrow ({\mathrm{\forall }}_{z}q(z,z)\vee {\mathrm{\exists }}_{x}q(z,x))$

Rozwiązanie

1. $p(z)\Rightarrow {\mathrm{\exists }}_{z}p(\underset{\_}{z})$

2. ${\mathrm{\forall }}_y(({\mathrm{\exists }}_{z}q(y,z))\Rightarrow q(y,\underset{\_}{z}))$

3. $q(\underset{\_}{x},\underset{\_}{y})\Rightarrow {\mathrm{\forall }}_x(q(x,\underset{\_}{y})\Rightarrow ({\mathrm{\forall }}_{y}q(x,y)))$

4. ${\mathrm{\forall }}_x{\mathrm{\exists }}_{y}q(x,y)\Rightarrow {\mathrm{\exists }}_x{\mathrm{\forall }}_{y}q(x,y)$

5. $({\mathrm{\exists }}_{z}p(z))\Rightarrow ({\mathrm{\forall }}_{z}q(z,z)\vee {\mathrm{\exists }}_{x}q(\underset{\_}{z},x))$

Definicja 2.11

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

Ćwiczenie 2.4

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

Hint 1.

Rozwiązanie

Jedynie formuła ${\mathrm{\forall }}_x{\mathrm{\exists }}_{y}q(x,y)\Rightarrow {\mathrm{\exists }}_x{\mathrm{\forall }}_{y}q(x,y)$ jest formułą domkniętą.

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 $\mathrm{\forall }$ oraz jego interakcji z implikacją. Przypomnijmy, że kwantyfikator $\mathrm{\exists }$ 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) $(\varphi \Rightarrow (\psi \Rightarrow \varphi ))$

(b) $(\varphi \Rightarrow (\nu \Rightarrow \psi )\Rightarrow ((\varphi \Rightarrow \nu )\Rightarrow (\varphi \Rightarrow \nu ))$

(c) $(\mathrm{\neg }\varphi \Rightarrow \psi )\Rightarrow (\mathrm{\neg }\varphi \Rightarrow \mathrm{\neg }\psi )\Rightarrow \varphi$

2. (Aksjomaty dotyczące kwantyfikatora)

(a) Dla dowolnej formuły $\varphi$ oraz termu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{t}} następująca formuła jest aksjomatem ${\mathrm{\forall }}_x\varphi \Rightarrow (\varphi [x\leftarrow t])$ (uwaga na podstawienie)

(b) Dla dowolnej formuły $\varphi$ oraz zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} , która nie ma wolnych wystąpień w $\varphi$ następująca formuła jest aksjomatem $\varphi \Rightarrow {\mathrm{\forall }}_x\varphi$

(c) Dla dowolnych formuł $\varphi$ i $\psi$ aksjomatem jest formuła ${\mathrm{\forall }}_x(\varphi \Rightarrow \psi )\Rightarrow (({\mathrm{\forall }}_x\varphi )\Rightarrow ({\mathrm{\forall }}_x\psi ))$

Podobnie jak w rachunku zdań dowodem formuły $\varphi$ nazwiemy ciąg formuł ${\varphi }_0,\dots ,{\varphi }_n$ taki, że ${\varphi }_n$ jest tym samym napisem co $\varphi$ a każda formuła ${\varphi }_i$ dla $i<n$ jest aksjomatem rachunku predykatów lub powstaje z dwóch formuł występujących wcześniej w dowodzie poprzez zastosowanie reguły Modus Ponens Modus Ponens (Wykład2).

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

np. $p(t)\Rightarrow {\mathrm{\exists }}_{x}p(x)$.

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 matryca boolowska(Wykład2). 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

${\mathrm{\forall }}_x{\mathrm{\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest silnie mniejsza od liczby Parser nie mógł rozpoznać (błąd składni): {\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 $x\prec y$ jest prawdą wtedy i tylko wtedy gdy liczba Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest silnie mniejsza od liczby Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} . Wtedy zdanie to powinniśmy uznać prawdziwe. Istotnie, dla każdej liczby całkowitej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} możemy dobrać liczbę Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest równa liczbie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} . Wtedy zdanie to powinniśmy uznać prawdziwe (do każdej liczby Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} możemy dobrać liczbę Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} tak aby była równa Parser nie mógł rozpoznać (błąd składni): {\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 $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. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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\to D$, gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{k}} jest ilością argumentów Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{f}} (symbole funkcyjne są interpretowane jako funkcje z potęgi dziedziny w dziedzinę)

(c) dla symboli predykatów: $I(p):D^k\to 0,1$, gdzie $k$ jest ilością argumentów Parser nie mógł rozpoznać (błąd składni): {\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 $M$ jest odpowiedni dla formuły $\varphi$ jeśli są w nim zdefiniowane interpretacje wszystkich symboli stałych funkcji oraz predykatów występujących w formule $\varphi$.

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ż 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 $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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{t}} jest zmienną, $\hat{\sigma }(t)=\sigma (t)$

2. jeśli term Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{t}} jest stałą, to $\hat{\sigma }(t)=I(t)$ (stałe wartościujemy zgodnie z interpretacją w modelu)

3. jeśli term Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 Parser nie mógł rozpoznać (błąd składni): {\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 $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 (Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 $\mathrm{\neg }A$ to jest ona prawdziwa wtedy i tylko wtedy gdy formuła Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{A}} jest wartościowana na fałsz (zgodnie z tabelą dla negacji ??)

4. Jeśli formuła jest postaci ${\mathrm{\forall }}_{x}A$, to jest ona prawdziwa jeśli prawdziwe jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{A}} i dla każdego wartościowania zmiennych różniącego się od $\sigma$ co najwyżej interpretacją symbolu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} prawdziwe jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{A}} .

5. Jeśli formuła jest postaci ${\mathrm{\exists }}_{x}A$, to jest ona prawdziwa jeśli istnieje ocena zmiennych różniąca się od $\sigma$ co najwyżej interpretacją symbolu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} taka, że przy tej ocenie prawdziwe jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{A}} .

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

${\mathrm{\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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ć

${\mathrm{\forall }}_y(x<y+x\vee y=o).$

Definicja 4.9

Formuła $\varphi$ 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 $\varphi$.

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

$({\mathrm{\forall }}_{x}p(x))\Rightarrow ({\mathrm{\exists }}_{x}p(x)).$

Rozważmy dowolny model $M$ odpowiedni dla powyższej formuły (odpowiedni to znaczy taki który ustala interpretację symbolu predykatywnego Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} ). Jeśli w tym modelu nie jest prawdziwa formuła $({\mathrm{\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 $({\mathrm{\forall }}_{x}p(x))$. Weźmy dowolny taki model i oznaczmy go przez $M$. Aby pokazać, że $({\mathrm{\exists }}_{x}p(x))$ jest prawdziwe w $M$ wystarczy wskazać że istnieje w dziedzinie taka wartość, że podstawiona w miejsce Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} uczyni predykat oznaczony przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} prawdziwym. Formuła $({\mathrm{\forall }}_{x}p(x))$ jest prawdziwa w $M$ więc każda wartość podstawiona pod Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} czyni predykat odpowiadający Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} , to rzeczywiście istnieje taki element dziedziny, który podstawiony w miejsce Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} uczyni formułę $p(x)$ prawdziwą. A więc formuła ${\mathrm{\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 Kurt Godel.

Twierdzenie 4.11 [Kurt Godel]

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest równe Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest zerem

3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest jedynką

4. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest liczbą pierwszą

5. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest kwadratem pewnej liczby pierwszej

6. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest iloczynem dwóch różnych liczb pierwszych

7. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest iloczynem dwóch liczb pierwszych

8. Parser nie mógł rozpoznać (błąd składni): {\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ć (błąd składni): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} są względnie pierwsze

Podpowiedź

1. wstarczy aby się dzieliły nawzajem

2. każda liczba dzieli zero

3. jedynka dzieli wszystkie liczby

4. jest podzielna tylko przez siebie i przez jeden (uwaga, 1 nie jest pierwsza)

5. ma dokładnie 3 różne dzielniki

6. ma dokładnie 4 różne dzielniki

7. jest kwadratem lub iloczynem dwóch różnych liczb pierwszych

8. każde dwa dzielniki różne od 1 mają wspólny dzielnik różny od 1

9. każda liczba która dzieli obie liczby dzieli też ich największy wspólny dzielnik

10. każda liczba która jest podzielna przez obie liczby jest też podzielna przez ich najmniejszą wspólną wielokrotność

11. ich największym wspólnym dzielnikiem jest 1

Rozwiązanie

Dla każdej z poniższych formuł w nawiasie zapisujemy skórty których będziemy używać dla tych formuł.

1. ${\mathrm{\forall }}_z(p(z,x)\iff p(z,y)$ (skrót $x=y$)

2. ${\mathrm{\forall }}_{z}p(z,x)$ (skrót $x=1$)

3. ${\mathrm{\forall }}_{z}p(x,z)$ (skrót $x=0$)

4. $(\mathrm{\neg }x=1)\wedge {\mathrm{\forall }}_z[p(z,x)\Rightarrow (z=1\vee z=x)]$ (skrót $Prim(x)$).

5. ${\mathrm{\forall }}_z{\mathrm{\forall }}_y(p(z,x)\wedge p(y,x)\wedge (\mathrm{\neg }z=1)\wedge (\mathrm{\neg }z=x)\wedge (\mathrm{\neg }y=1)\wedge (\mathrm{\neg }z=x))\Rightarrow (z=y)$ (skrót $pKw(x)$).

6. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest iloczynem dwóch różnych liczb pierwszych (skrót $pq(x)$.

7. $pKq(x)\vee pq(x)$

8. ${\mathrm{\forall }}_{y:\mathrm{\neg }(y=1)}{\mathrm{\forall }}_{z:\mathrm{\neg }(z=1)}(p(y,x)\wedge p(z,x))\Rightarrow ({\mathrm{\exists }}_{v:\mathrm{\neg }(z=1)}(p(v,y)\wedge p(v,z))$

9. ${\mathrm{\forall }}_x{\mathrm{\forall }}_y{\mathrm{\exists }}_z(p(z,x)\wedge p(z,y)\wedge ({\mathrm{\forall }}_v(p(v,x)\wedge pv,y)\Rightarrow p(v,z))))$

10 ${\mathrm{\forall }}_x{\mathrm{\forall }}_y{\mathrm{\exists }}_z(p(x,z)\wedge p(y,z)\wedge ({\mathrm{\forall }}_v(p(x,v)\wedge py,v)\Rightarrow p(z,v))))$

11. ${\mathrm{\forall }}_z((p(z,x)\wedge p(z,y))\Rightarrow (z=1))$

Ć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 Parser nie mógł rozpoznać (błąd składni): {\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 $M$ 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ć (błąd składni): {\displaystyle \textnormal{x}} jest równe Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest nadzbiorem Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest punktem

4. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest odcinkiem

5. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest okręgiem

6. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest równoległe do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

7. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} mają dokładenie jeden punkt wspólny

8. okręgi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} są do siebie styczne

9. okręgi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} są do siebie wewnętrznie styczne i okrąg Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest okręgiem wewnętrznym

10. okręgi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} są do siebie zewnętrzenie styczne

11. punkt Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest końcem odcinka Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

12. odcinek Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest styczny do okręgu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

13. okręgi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} mają taką samą średnicę

14. okrąg Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} ma średnicę mniejszą niż okrąg Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

15. odcinek Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest krótszy od odcinka Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

16. odcinek Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest średnicą okręgu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

17. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest prostopadłe do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

18. odcinki $x,y,z,w$ tworzą kwadrat

Podpowiedź

1. jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest różne od Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} to istnieje punkt który należy do jednego obiektu i nie należy do drugiego

2. każdy punkt wspólny jakiegoś obiektu z podzbiorem jest też punktem wspólnym z nadzbiorem

3. punkt ma z każdym obiektem co najwyżej jeden punkt wspólny (okrąg i odcinek może mieć więcej)

4. tylko punkt i odcinek mogą mieć istotne nadzbiory, punkty możemy wykluczyć korzystając z formuły w poprzednim punkcie

5. jeśli coś nie jest punktem ani odcinkiem to jest okręgiem

6. odcinki są równoległe jeśli dowolne ich przedłużenia nie przecinają się

7. każde dwa ich wspólne punkty muszą być równe

8. okręgi są styczne jeśli mają dokładnie jeden punkt wspólny

9. jeśli okrąg Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest wewnętrzny to każdy odcinek, który ma przynajmniej jeden punkt wspólny z Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} da się przedłużyć tak, aby przecinał (miał punkt wspólny) z Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

10. okręgi muszą być styczne i żaden z nich nie może być wewnętrzny

11. istnieje okrąg przechodzący przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} taki że każdy okrąg styczny do niego w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jeśli jest zewnętrzny to ma dokładnie jeden punkt wspólny z Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} a jeśli jest wewnętrzny to dwa

12. każde przedłużenie odcinka Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} dokładnie jeden punkt wpólny z Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

13. istnieją dwa równoległe odcinki styczne do obu okręgów które nie mają punktów wspólnych

14. istnieję dwa równoległe odcinki które nie mają punktów wspólnych z których pierwszy jest styczny do obu okręgów a drugi jest styczny do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} i przecina okrąg Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} w dwóch różnych punktach

15. najmniejszy okrąg którego cięciwą jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} ma mniejszą średnicę niż najmniejszy okrąg którego cięciwą jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

16. najmniejszy okrąg którego cięciwą jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} ma taką samą średnicę jak Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest cięciwą Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

17. istnieje okrąg, który jest styczny do pewnego przedłużenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest równoległy do średnicy okręgu której jeden z końców znajduje się w punkcie styczności z Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}}

18. odcinki mają być równej długości, prostopadłe, różne i mają się odpowiednio stykać końcami (uwaga na kolejność)

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

Solution.

Ć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. ${\mathrm{\forall }}_x{\mathrm{\forall }}_{y}p(x,y)\Rightarrow p(y,x)$

2. $({\mathrm{\forall }}_x{\mathrm{\exists }}_{y}p(x,y))\Rightarrow {\mathrm{\exists }}_y{\mathrm{\forall }}_{x}p(x,y)$

3. $({\mathrm{\forall }}_x(p(x)\vee q(x)))\Rightarrow ({\mathrm{\forall }}_x(p(x))\vee {\mathrm{\forall }}_{x}q(x))$

4. ${\mathrm{\forall }}_y[({\mathrm{\forall }}_x(p(x)\Rightarrow q(x))\wedge q(y))\Rightarrow p(z)]$

5. ${\mathrm{\forall }}_x{\mathrm{\forall }}_y(p(x,y)\Rightarrow {\mathrm{\exists }}_z(p(x,z)\wedge p(z,y))$

6. ...

Rozwiązanie

Poniższe przykłady to tylko jedne z wielu możliwych rozwiązań.

1.

(a) Formuła jest prawdziwa w zbiorze trójkątów, jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} jest interpretowany jako podobieństwo trójkątów.

(b) Formuła jest fałszywa w zbiorze odcinków, jeśli $p(x,y)$ jest prawdziwy wtedy i tylko wtedy gdy odcinek oznaczony przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest krótszy od odcinka oznaczonego przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} .

2.

(a) Formuła jest prawdziwa w liczbach naturalnych, jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} jest interpretowane jako słaba mniejszość (czyli $p(x,y)$ jest prawdą jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest mniejsze lub równe Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} ). Wtedy rzeczywiście dla każdej liczby istnieje liczba słabo mniejsza (poprzednik implikacji jest prawdziwy) oraz istnieje liczba (zero) która jest słabo mniejsza od wszyskich innych (następnik prawdziwy). Cała implikacja jest więc prawdziwa.

(b) Formuła jest fałszywa w liczbach całkowitych, jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} jest interpretowane jako słaba mniejszość. Wtedy rzeczywiście dla każdej liczby istnieje liczba słabo mniejsza (poprzednik implikacji jest prawdziwy) ale nie istnieje najmniejsza liczba całkowita (następnik implikacji jest fałszywy). Cała implikacja jest więc fałszywa. $({\mathrm{\forall }}_x{\mathrm{\exists }}_{y}p(x,y))\Rightarrow {\mathrm{\exists }}_y{\mathrm{\forall }}_{x}p(x,y)$

3.

(a) Formuła jest prawdziwa w zbiorze liczb naturalnych przy następującej interpretacji symboli predykatywncych jeśli $p(x)$ jest prawdziwe gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest liczbą złożoną, a $q(x)$ jest prawdziwe gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest liczbą nieparzystą. Ponieważ istnieje liczba parzysta która jest liczbą pierwszą to poprzednik implikacji jest fałszywy więc cała implikacja jest prawdziwa.

(b) Formuła jest prawdziwa w zbiorze liczb naturalnych przy następującej interpretacji symboli predykatywncych jeśli $p(x)$ jest prawdziwe gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest liczbą parzystą, a $q(x)$ jest prawdziwe gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest liczbą nieparzystą. Każda liczba naturalna jest parzysta lub nieparzysta (poprzednik jest prawdziwe), ale nie prawda, że każda jest parzysta ani nie prawda że każda jest nieparzysta (następnik fałszywy). Cała implikacja jest więc fałszywa.

4.

$({\mathrm{\forall }}_y[{\mathrm{\forall }}_x(p(x)\Rightarrow q(x))\wedge q(y))\Rightarrow p(y)]$

(a) Formuła jest prawdziwa a dowolnym modelu w którym $p(y)$ jest zawsze prawdą. Na przykład w zbiorze liczb naturalnych podzielnych przez 10, gdzie $q(x)$ prawdziwa, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest mniejsze od 1000, a $p(y)$ jest prawdziwe gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} jest parzyste.

(b) Formuła jest fałszywa w zbiorze czworokątów, gdzie $p(x)$ jest prawdą jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest kwadratem, a $q(x)$ jest prawdą gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest prostokątem. Wtedy, prawdziwa jest formuła ${\mathrm{\forall }}_x(p(x)\Rightarrow q(x))$ (każdy kwadrat jest prostokątem). Jeśli więc w roli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} w formule $({\mathrm{\forall }}_x(p(x)\Rightarrow q(x))\wedge q(y))\Rightarrow p(y)]$ wystąpi prostokąt to poprzednik implikacji będzie prawdziwy, a następnik nie. Nie jest więc prawdą, ze formuła ${\mathrm{\forall }}_x(p(x)\Rightarrow q(x))\wedge q(y))\Rightarrow p(y)$ jest prawdziwa dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} .

5.

(a) Formuła jest prawdziwa w liczbach wymiernych gdzie $p(x,y)$ jest prawdziwe wtedy i tylko wtedy gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} jest silnie mniejsze od Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} . Wtedy rzeczywiście dla dowolnych dwóch liczb wymiernych $x,y$ takich, że $x<y$ istnieje trzecia liczba która znajduje się pomiędzy nimi (np. $\frac{x+y}{2}$).

(b) Formuła jest fałszywa w zbiorze liczb naturalnych w którym $p(x,y)$ interpretujemy jako silną mniejszość. Na przykład dla jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} będziemy wartościować na 0, a Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{y}} na 1 to prawdą będzie $p(x,y)$ (poprzednik implikacji) ale nie będzie prawdą ${\mathrm{\exists }}_z(p(x,z)\wedge p(z,y))$ bo pomiędzy liczbami 0 a 1 nie ma żadnej liczby naturalnej.

Ćwiczenie 4.5

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

1. ${\mathrm{\forall }}_{x}p(x)\Rightarrow (p(c))$

2. $p(c)\Rightarrow {\mathrm{\forall }}_{x}p(c)$

3. ${\mathrm{\forall }}_x(p(x)\Rightarrow q(x))\Rightarrow (({\mathrm{\forall }}_{x}p(x))\Rightarrow ({\mathrm{\forall }}_{x}qx)))$

4. ${\mathrm{\exists }}_{x}p(x)\iff \mathrm{\neg }{\mathrm{\forall }}_x\mathrm{\neg }p(x)$

5. $\mathrm{\neg }{\mathrm{\forall }}_{x}p(x)\iff {\mathrm{\exists }}_x\mathrm{\neg }p(x)$

6. ${\mathrm{\forall }}_{x}r(x,f(x))\Rightarrow {\mathrm{\forall }}_x{\mathrm{\exists }}_{y}r(x,y)$

Solution.

Ćwiczenie 4.6

Rozważmy formułę

${\mathrm{\forall }}_x(\mathrm{\neg }g(x,x)\iff g(b,x))$

(golibroda Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{b}} goli wszystkich tych i tylko tych, którzy nie golą się sami). Udowodnij, że nie istnieje model dla powyższej formuły.

Rozwiązanie

(Idea dowodu: kto w goli golibrodę?) Dla dowodu nie wprost przypuśćmy, że istnieje model $M$ w którym ta formuła jest prawdziwa. Skoro tak to dla dowolnego wartościowania zmiennej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} prawdziwa jest formuła

$(\mathrm{\neg }g(x,x)\iff g(b,x)).$

W szczególności dla wartościowania które Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{x}} przypisuje ten sam obiekt co stałej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{b}} powyższa formuła ma tę samą wartość co

$(\mathrm{\neg }g(b,b)\iff g(b,b)).$

a taka formuła nigdy nie jest spełniona. Wobec tego formuła z zadania jest nieprawdziwa w $M$.