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
m (Zastępowanie tekstu - "\textnormal" na "\text")
 
(Nie pokazano 13 wersji utworzonych przez 2 użytkowników)
Linia 3: Linia 3:
 
Na początku rozdziału o logice zdaniowej rozważaliśmy zdanie
 
Na początku rozdziału o logice zdaniowej rozważaliśmy zdanie
  
<center>Jeśli <math>\textnormal{n}</math> jest liczbą pierwszą to <math>\textnormal{n}</math> jest liczbą nieparzystą lub <math>\textnormal{n}</math> jest równe '''2'''.</center>
+
<center>Jeśli <math>\text{n}</math> jest liczbą pierwszą to <math>\text{n}</math> jest liczbą nieparzystą lub <math>\text{n}</math> jest równe '''2'''.</center>
  
 
Opisaliśmy je wtedy formułą
 
Opisaliśmy je wtedy formułą
Linia 14: Linia 14:
 
w której <math>p,q,r</math> odpowiadały odpowiednio zdaniom
 
w której <math>p,q,r</math> odpowiadały odpowiednio zdaniom
  
:1. <math>\textnormal{n}</math> jest liczbą pierwszą,<br/>
+
:1. <math>\text{n}</math> jest liczbą pierwszą,<br/>
:2. <math>\textnormal{n}</math> jest liczbą nieparzystą,<br/>
+
:2. <math>\text{n}</math> jest liczbą nieparzystą,<br/>
:3. <math>\textnormal{n}</math> jest równe '''2'''.<br/>
+
:3. <math>\text{n}</math> jest równe '''2'''.<br/>
  
Podstawiając zamiast zdania  <math>\textnormal{n}</math> ''jest liczbą pierwszą'' zmienną zdaniową <math>\textnormal{p}</math> ukrywamy jednak część informacji. Zdanie to mówi przecież o pewnej liczbie <math>\textnormal{n}</math>, co więcej zdania <math>{p,q}</math> i <math>\textnormal{r}</math> dotyczą tej samej liczby <math>\textnormal{n}</math>. Zapiszmy więc <math>p(n)</math> zamiast <math>{p}</math> aby podkreślić fakt że prawdziwość <math>{p}</math> zależy od tego jaką konkretną wartość przypiszemy zmiennej <math>\textnormal{n}</math>. Zdanie <math>p(n)</math> będzie prawdziwe jeśli za <math>\textnormal{n}</math> podstawimy jakąś liczbę pierwszą i fałszywe w przeciwnym przypadku. Zgodnie z tą konwencją nasze zdanie przyjmie postać
+
Podstawiając zamiast zdania  <math>\text{n}</math> ''jest liczbą pierwszą'' zmienną zdaniową <math>\text{p}</math> ukrywamy jednak część informacji. Zdanie to mówi przecież o pewnej liczbie <math>\text{n}</math>, co więcej zdania <math>{p,q}</math> i <math>\text{r}</math> dotyczą tej samej liczby <math>\text{n}</math>. Zapiszmy więc <math>p(n)</math> zamiast <math>{p}</math> aby podkreślić fakt że prawdziwość <math>{p}</math> zależy od tego jaką konkretną wartość przypiszemy zmiennej <math>\text{n}</math>. Zdanie <math>p(n)</math> będzie prawdziwe jeśli za <math>\text{n}</math> podstawimy jakąś liczbę pierwszą i fałszywe w przeciwnym przypadku. Zgodnie z tą konwencją nasze zdanie przyjmie postać
  
 
<center><math>
 
<center><math>
Linia 25: Linia 25:
 
</math></center>
 
</math></center>
  
Zwróćmy uwagę jednak, że trudno ocenić prawdziwość zdania <math>\textnormal{p}</math> dopóki
+
Zwróćmy uwagę jednak, że trudno ocenić prawdziwość zdania <math>\text{p}</math> dopóki
nie podstawimy w miejsce <math>\textnormal{n}</math> jakiejś konkretnej liczby. Z drugiej
+
nie podstawimy w miejsce <math>\text{n}</math> jakiejś konkretnej liczby. Z drugiej
strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce <math>\textnormal{n}</math>
+
strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce <math>\text{n}</math>
 
zdanie będzie prawdziwe. Możemy więc przeformułować je jako
 
zdanie będzie prawdziwe. Możemy więc przeformułować je jako
  
Dla każdej liczby naturalnej <math>\textnormal{n}</math>, jeśli <math>\textnormal{n}</math> jest liczbą pierwszą to <math>\textnormal{n}</math> jest liczbą nieparzystą lub <math>\textnormal{n}</math> jest równe '''2'''.
+
Dla każdej liczby naturalnej <math>\text{n}</math>, jeśli <math>\text{n}</math> jest liczbą pierwszą to <math>\text{n}</math> jest liczbą nieparzystą lub <math>\text{n}</math> jest równe '''2'''.
  
 
Aby móc formalnie zapisywać zdania takie jak powyższe wprowadzimy
 
Aby móc formalnie zapisywać zdania takie jak powyższe wprowadzimy
Linia 45: Linia 45:
 
Możemy teraz powiedzieć, że powyższa formuła jest prawdziwa  w
 
Możemy teraz powiedzieć, że powyższa formuła jest prawdziwa  w
 
zbiorze liczb naturalnych, gdzie <math>p(n),q(n),r(n)</math> będą oznaczać
 
zbiorze liczb naturalnych, gdzie <math>p(n),q(n),r(n)</math> będą oznaczać
odpowiednio <math>\textnormal{n}</math> jest liczbą pierwszą, <math>\textnormal{n}</math> jest liczbą nieparzystą, <math>\textnormal{n}</math> jest równe '''2'''.
+
odpowiednio <math>\text{n}</math> jest liczbą pierwszą, <math>\text{n}</math> jest liczbą nieparzystą, <math>\text{n}</math> jest równe '''2'''.
  
 
Przy tej samej interpretacji <math>p(n),q(n)</math> moglibyśmy wyrazić zdanie
 
Przy tej samej interpretacji <math>p(n),q(n)</math> moglibyśmy wyrazić zdanie
Linia 146: Linia 146:
  
 
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
 
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 <math>p(n)</math>, który przyjmuje wartość prawdy jeśli <math>n</math> jest liczbą pierwszą i fałszu w przeciwnym przypadku. Podobnie możemy mówić o binarnym predykacie równości (zwyczajowo oznaczanym przez <math>=</math>). Dla argumentów <math>{x,y}</math> przyjmuje on wartość prawdy wtedy kiedy <math>\textnormal{x}</math> jest tą samą liczbą co <math>\textnormal{y}</math> i fałszu w przeciwnym przypadku. Formuły atomowe będą opisywały proste zdania typu <math>\textnormal{x}</math> jest liczbą pierwszą, <math>\textnormal{x}</math> dzieli <math>\textnormal{y}</math>, <math>\textnormal{x}</math> jest równe <math>\textnormal{y}</math>. Innymi słowy sprowadzają sie do stwierdzania czy dany zestaw argumentów ma pewną własność opisywaną predykatem.
+
pierwszości <math>p(n)</math>, który przyjmuje wartość prawdy jeśli <math>n</math> jest liczbą pierwszą i fałszu w przeciwnym przypadku. Podobnie możemy mówić o binarnym predykacie równości (zwyczajowo oznaczanym przez <math>=</math>). Dla argumentów <math>{x,y}</math> przyjmuje on wartość prawdy wtedy kiedy <math>\text{x}</math> jest tą samą liczbą co <math>\text{y}</math> i fałszu w przeciwnym przypadku. Formuły atomowe będą opisywały proste zdania typu <math>\text{x}</math> jest liczbą pierwszą, <math>\text{x}</math> dzieli <math>\text{y}</math>, <math>\text{x}</math> jest równe <math>\text{y}</math>. Innymi słowy sprowadzają sie do stwierdzania czy dany zestaw argumentów ma pewną własność opisywaną predykatem.
  
 
{{uwaga|2.6.||
 
{{uwaga|2.6.||
  
 
W oznaczeniach z poprzednich przykładów, napis <math>y\times(x+(-3))=q(1)</math> nie jest formułą atomową ani
 
W oznaczeniach z poprzednich przykładów, napis <math>y\times(x+(-3))=q(1)</math> nie jest formułą atomową ani
termem. Gdyby predykat <math>\textnormal{q}</math> oznaczał np. bycie liczbą nieparzystą to
+
termem. Gdyby predykat <math>\text{q}</math> oznaczał np. bycie liczbą nieparzystą to
 
powyższy napis powinniśmy przeczytać jako
 
powyższy napis powinniśmy przeczytać jako
  
Linia 168: Linia 168:
 
:1. Formuły atomowe są formułami.
 
:1. Formuły atomowe są formułami.
  
:2. Jeśli <math>\textnormal{A}</math> i <math>B</math> są formułami, to <math>(A \Rightarrow B)</math> oraz <math>\neg A</math> są formułami.
+
:2. Jeśli <math>\text{A}</math> i <math>B</math> są formułami, to <math>(A \Rightarrow B)</math> oraz <math>\neg A</math> są formułami.
  
:3. Jeśli <math>\textnormal{A}</math> jest formułą i <math>\textnormal{x}</math> jest zmienną, to <math>\forall_x A</math> jest formułą.
+
:3. Jeśli <math>\text{A}</math> jest formułą i <math>\text{x}</math> jest zmienną, to <math>\forall_x A</math> jest formułą.
  
 
:4. Nic innego nie jest formułą.
 
:4. Nic innego nie jest formułą.
Linia 254: Linia 254:
 
będziemy traktować jako  skróty. Ustalmy poniższe definicje
 
będziemy traktować jako  skróty. Ustalmy poniższe definicje
  
:1. <math>\phi \vee \psi \stackrel{\textrm{def}}{\equiv} \neg \phi \Rightarrow \psi</math>  
+
:1. <math>\phi \vee \psi \stackrel{\text{def}}{\equiv} \neg \phi \Rightarrow \psi</math>  
  
:2. <math>\phi \wedge \psi \stackrel{\textrm{def}}{\equiv} \neg ( \phi \Rightarrow \neg \psi)</math>
+
:2. <math>\phi \wedge \psi \stackrel{\text{def}}{\equiv} \neg ( \phi \Rightarrow \neg \psi)</math>
  
:3. <math>\phi \Leftrightarrow \psi \stackrel{\textrm{def}}{\equiv} (\phi \Rightarrow \psi) \wedge (\psi \Rightarrow \phi)</math>
+
:3. <math>\phi \Leftrightarrow \psi \stackrel{\text{def}}{\equiv} (\phi \Rightarrow \psi) \wedge (\psi \Rightarrow \phi)</math>
  
 
===Kwantyfikator egzystencjalny===
 
===Kwantyfikator egzystencjalny===
Linia 268: Linia 268:
 
<center><math>
 
<center><math>
  
\exists_x \phi \stackrel{\textrm{def}}{\equiv} \neg (\forall_x \neg \phi)
+
\exists_x \phi \stackrel{\text{def}}{\equiv} \neg (\forall_x \neg \phi)
 
</math></center>
 
</math></center>
  
Nieformalnie kwantyfikator egzystencjalny mówi o tym, że istnieje jakiś obiekt, który podstawiony w miejsce <math>\textnormal{x}</math> uczyni formułę <math>{\phi}</math>
+
Nieformalnie kwantyfikator egzystencjalny mówi o tym, że istnieje jakiś obiekt, który podstawiony w miejsce <math>\text{x}</math> uczyni formułę <math>{\phi}</math>
prawdziwą. Zdefiniowaliśmy go poprzez równoważne stwierdzenie które mówi że nieprawdą jest, że każdy obiekt podstawiony w miejsce <math>\textnormal{x}</math> falsyfikuje <math>{\phi}</math>. Zgodnie z powyższą konwencją formułę ze wstępu
+
prawdziwą. Zdefiniowaliśmy go poprzez równoważne stwierdzenie które mówi że nieprawdą jest, że każdy obiekt podstawiony w miejsce <math>\text{x}</math> falsyfikuje <math>{\phi}</math>. Zgodnie z powyższą konwencją formułę ze wstępu
  
 
<center><math>
 
<center><math>
Linia 290: Linia 290:
 
Kwantyfikatory ograniczone są skrótami które definujemy następująco
 
Kwantyfikatory ograniczone są skrótami które definujemy następująco
  
:1. <math>\forall_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \forall_x \phi \Rightarrow \psi</math>
+
:1. <math>\forall_{x:\phi} \psi \stackrel{\text{def}}{\equiv} \forall_x \phi \Rightarrow \psi</math>
  
:2. <math>\exists_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \exists_x \phi \wedge \psi</math>
+
:2. <math>\exists_{x:\phi} \psi \stackrel{\text{def}}{\equiv} \exists_x \phi \wedge \psi</math>
  
 
i czytamy
 
i czytamy
  
:1. dla każdego <math>\textnormal{x}</math> które spełnia <math>{\phi}</math> spełnione jest <math>{\psi}</math>
+
:1. dla każdego <math>\text{x}</math> które spełnia <math>{\phi}</math> spełnione jest <math>{\psi}</math>
  
:2. istnieje <math>\textnormal{x}</math> spełniające <math>{\phi}</math> które spełnia <math>{\psi}</math>
+
:2. istnieje <math>\text{x}</math> spełniające <math>{\phi}</math> które spełnia <math>{\psi}</math>
  
 
Zgodnie z tą konwencją formułę 1.1 możemy zapisać następująco
 
Zgodnie z tą konwencją formułę 1.1 możemy zapisać następująco
Linia 329: Linia 329:
 
<center><math>
 
<center><math>
  
\exists_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv}
+
\exists_{x:\phi} \psi \stackrel{\text{def}}{\equiv}
 
\exists_x \phi \wedge \psi
 
\exists_x \phi \wedge \psi
 
</math></center>
 
</math></center>
Linia 340: Linia 340:
 
<center><math>
 
<center><math>
  
\exists_x \phi \wedge \psi \stackrel{\textrm{def}}{\equiv}
+
\exists_x \phi \wedge \psi \stackrel{\text{def}}{\equiv}
 
\neg \forall_x \neg(\phi \wedge \psi)
 
\neg \forall_x \neg(\phi \wedge \psi)
 
</math></center>
 
</math></center>
Linia 350: Linia 350:
 
<center><math>
 
<center><math>
  
\neg \forall_x \neg(\phi \wedge \psi) \stackrel{\textrm{def}}{\equiv}
+
\neg \forall_x \neg(\phi \wedge \psi) \stackrel{\text{def}}{\equiv}
 
\neg \forall_x \neg(\neg(\phi \Rightarrow \neg \psi))
 
\neg \forall_x \neg(\neg(\phi \Rightarrow \neg \psi))
 
</math></center>
 
</math></center>
Linia 357: Linia 357:
 
===Zmienne wolne i związane===
 
===Zmienne wolne i związane===
  
Jeśli <math>\textnormal{x}</math> jest zmienną, a <math>{\phi}</math> jest formułą to każda pozycję w napisie <math>{\phi}</math> na której występuje symbol <math>\textnormal{x}</math> i nie jest poprzedzony bezpośrednio kwantyfikatorem, nazywamy wystąpieniem zmiennej <math>\textnormal{x}</math>. Wystąpienia dzielimy na ''wolne'' i ''związanie''. Wystąpienie jest związane jeśli znajduje się ,,pod działaniem" jakiegoś kwantyfikatora.
+
Jeśli <math>\text{x}</math> jest zmienną, a <math>{\phi}</math> jest formułą to każda pozycję w napisie <math>{\phi}</math> na której występuje symbol <math>\text{x}</math> i nie jest poprzedzony bezpośrednio kwantyfikatorem, nazywamy wystąpieniem zmiennej <math>\text{x}</math>. 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.||
 
{{definicja|2.9.||
Linia 367: Linia 367:
 
:2. Jeśli formuła jest postaci <math>\phi \Rightarrow \psi</math> lub <math>\neg \phi</math> to wystąpienia zmiennych pozostają takie same jak wystąpienia w w <math>{\phi}</math> oraz <math>{\psi}</math>.
 
:2. Jeśli formuła jest postaci <math>\phi \Rightarrow \psi</math> lub <math>\neg \phi</math> to wystąpienia zmiennych pozostają takie same jak wystąpienia w w <math>{\phi}</math> oraz <math>{\psi}</math>.
  
:3. Jeśli formuła jest postaci <math>\forall_x \phi</math> to wszystkie wystąpienia zmiennej <math>\textnormal{x}</math> w <math>\forall_x \phi</math> są '''związane''', a wystąpienia innych zmiennych pozostają takie jak w <math>\phi</math>.
+
:3. Jeśli formuła jest postaci <math>\forall_x \phi</math> to wszystkie wystąpienia zmiennej <math>\text{x}</math> w <math>\forall_x \phi</math> są '''związane''', a wystąpienia innych zmiennych pozostają takie jak w <math>\phi</math>.
 
}}
 
}}
  
Linia 429: Linia 429:
 
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 <math>\displaystyle \forall_x x+y >x</math>, wstawiając w miejsce <math>\displaystyle y</math> stałą <math>\displaystyle 1</math>, otrzymamy <math>\displaystyle \forall_x x+1 >x</math>.
 
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 <math>\displaystyle \forall_x x+y >x</math>, wstawiając w miejsce <math>\displaystyle y</math> stałą <math>\displaystyle 1</math>, otrzymamy <math>\displaystyle \forall_x x+1 >x</math>.
  
{{definicja|2.10.||Przez <math> [x \leftarrow t]\phi</math> będziemy oznaczać formułę powstałą przez zastąpienie wszystkich '''wolnych''' wystąpień zmiennej <math>\displaystyle x</math> w formule <math>\displaystyle \phi</math> termem <math>\displaystyle t</math>. Pisząc <math>[x \leftarrow t]\phi</math> zakładamy również, że w formule <math>\displaystyle \phi</math> żadna ze zmiennych występujących w termie <math>\displaystyle t</math> nie występuje w <math>\displaystyle \phi</math>.
+
{{definicja|2.10.||Przez <math> [x \leftarrow t]\phi</math> będziemy oznaczać formułę powstałą przez zastąpienie wszystkich '''wolnych''' wystąpień zmiennej <math>\displaystyle x</math> w formule <math>\displaystyle \phi</math> termem <math>\displaystyle t</math>. Pisząc <math>[x \leftarrow t]\phi</math> zakładamy również, że w formule <math>\displaystyle \phi</math> żadna ze zmiennych występujących w termie <math>\displaystyle t</math> nie ma związanych wystąpień w <math>\displaystyle \phi</math>.
 
}}
 
}}
  
Linia 448: Linia 448:
 
::(a) <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
 
::(a) <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
  
::(b) <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \nu) \right)</math>
+
::(b) <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \psi) \right)</math>
  
 
::(c) <math>(\neg \phi \Rightarrow \psi) \Rightarrow ((\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi)</math>
 
::(c) <math>(\neg \phi \Rightarrow \psi) \Rightarrow ((\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi)</math>
Linia 456: Linia 456:
 
::(a) Dla dowolnej formuły <math>\phi</math> oraz termu <math>t</math> następująca formuła jest aksjomatem <math>\forall_x \phi \Rightarrow (\phi [x \leftarrow t])</math> (uwaga na podstawienie)
 
::(a) Dla dowolnej formuły <math>\phi</math> oraz termu <math>t</math> następująca formuła jest aksjomatem <math>\forall_x \phi \Rightarrow (\phi [x \leftarrow t])</math> (uwaga na podstawienie)
  
::(b) Dla dowolnej formuły <math>\phi</math> oraz zmiennej <math>\textnormal{x}</math>, która nie ma wolnych wystąpień w <math>\phi</math> następująca formuła jest aksjomatem <math>\phi \Rightarrow \forall_x \phi</math>
+
::(b) Dla dowolnej formuły <math>\phi</math> oraz zmiennej <math>\text{x}</math>, która nie ma wolnych wystąpień w <math>\phi</math> następująca formuła jest aksjomatem <math>\phi \Rightarrow \forall_x \phi</math>
  
 
::(c) Dla dowolnych formuł <math>{\phi}</math> i <math>{\psi}</math> aksjomatem jest formuła <math>\forall_x(\phi \Rightarrow \psi) \Rightarrow ((\forall_x \phi)\Rightarrow(\forall_x \psi))</math>
 
::(c) Dla dowolnych formuł <math>{\phi}</math> i <math>{\psi}</math> aksjomatem jest formuła <math>\forall_x(\phi \Rightarrow \psi) \Rightarrow ((\forall_x \phi)\Rightarrow(\forall_x \psi))</math>
 +
 +
Poza tym do aksjomatów dorzucamy również wszystkie generalizacje formuł pasujących do powyższych schematów. Generalizacja formuły jest to ta sama formuła poprzedzona blokiem kwantyfikatorów ogólnych - dla dowolej formuły <math> \phi</math> oraz dowolnych zmiennych <math>x_1,\dots,x_k</math> formuła <math> \forall_{x_1} \dots \forall_{x_k} \phi </math> jest generalizacją <math> \phi </math>.
 
}}
 
}}
 
Podobnie jak w rachunku zdań dowodem formuły <math>{\phi}</math> nazwiemy ciąg formuł <math>\phi_0, \dots, \phi_n</math> taki, że <math>\phi_n</math> jest tym samym napisem co <math>{\phi}</math> a każda formuła <math>\phi_i</math> dla <math>i<n</math> jest aksjomatem rachunku predykatów lub powstaje z dwóch formuł występujących wcześniej w dowodzie poprzez zastosowanie reguły [[Logika i teoria mnogości/Wykład 2: Rachunek zdań|Modus Ponens z Wykładu 2]].
 
Podobnie jak w rachunku zdań dowodem formuły <math>{\phi}</math> nazwiemy ciąg formuł <math>\phi_0, \dots, \phi_n</math> taki, że <math>\phi_n</math> jest tym samym napisem co <math>{\phi}</math> a każda formuła <math>\phi_i</math> dla <math>i<n</math> jest aksjomatem rachunku predykatów lub powstaje z dwóch formuł występujących wcześniej w dowodzie poprzez zastosowanie reguły [[Logika i teoria mnogości/Wykład 2: Rachunek zdań|Modus Ponens z Wykładu 2]].
Linia 493: Linia 495:
 
Ostatnia formuła to dokładnie <math>\displaystyle \exists_x p(x)</math> po rozpisaniu skrótu <math>\displaystyle \exists</math>.
 
Ostatnia formuła to dokładnie <math>\displaystyle \exists_x p(x)</math> po rozpisaniu skrótu <math>\displaystyle \exists</math>.
 
}}
 
}}
 +
 +
 +
===Przykład teorii w rachunku predykatów===
 +
W oparciu o logikę predykatów możemy budować nowe teorie, dokładając inne, tzw. pozalogiczne aksjomaty. W językach wielu teorii pojawia się symbol predykatywny <math>=^2</math>, mający symbolizować równość. Ponieważ zwykle wymagamy aby te same własności były spełnione dla <math>=^2</math>, zostały wyodrębnione specjalne aksjomaty dla równości. Aksjomaty, te to wszystkie formuły oraz ich generalizacje odpowiadające poniższym schematom:
 +
 +
:1. <math> t=t</math>, dla każdego termu <math>t</math>
 +
 +
 +
:2. <math>  ( t_1=t_1' \wedge \ldots \wedge t_k= t_k' ) \Rightarrow f(t_1,\ldots,t_k) = f(t_1', \ldots,t_k') </math>, dla dowolnego symbolu funkcyjnego <math>f</math>, oraz dowolnych termów <math> t_1,\ldots,t_k, t_1', \ldots, t_k'</math>, gdzie <math>k</math> jest ilością argumentów symbolu <math> f</math>
 +
 +
 +
:3. <math>  ( t_1=t_1' \wedge \ldots \wedge t_k= t_k' ) \Rightarrow ( p(t_1,\ldots,t_k) \Rightarrow p(t_1', \ldots,t_k') ) </math>, dla dowolnego symbolu predykatywnego  <math>p</math>, oraz dowolnych termów <math> t_1,\ldots,t_k, t_1', \ldots, t_k'</math>, gdzie <math>k</math> jest ilością argumentów symbolu <math> p</math>
 +
 +
 +
Rozważmy język, w którym mamy jeden binarny symbol predykatywny <math>=^2</math>, jeden symbol stałej <math>0</math> oraz symbole funkcyjne <math> s^1, +^2, \times^2</math>. Zgodnie z przyjętą konwencją termy i formuły będziemy zapisywać infixowo. Do aksjomatów logicznych, oraz aksjomatów dla równości, dokładamy następujące aksjomaty:
 +
 +
:1. <math>\forall_x \forall_y (s(x)=s(y) \Rightarrow x=y)</math>
 +
 +
:2. <math>\forall_x \neg s(x)=0 </math>
 +
 +
:3. <math>\forall_x (\neg (x=0) \Rightarrow (\exists_y s(y)=x))</math>
 +
 +
:4. <math>\forall_x x+0=x</math>
 +
 +
:5. <math>\forall_x \forall_y x+s(y)=s(x+y)</math>
 +
 +
:6.  <math>\forall_x x\times 0= 0</math>
 +
 +
:7.  <math>\forall_x \forall_y x\times s(y)=x \times y+y</math>
 +
 +
Teorią Q nazwiemy wszystkie formuły w ustalonym języku które da się udowodnić z aksjomatów logiki predykatów z dołączonymi aksjomatami równości oraz 1-7. Nietrudno się przekonać, że wszystkie twierdzenia teorii Q są prawdziwe w liczbach naturalnych, przy naturalnej interpretacji występujących symboli (<math> s(x)</math> interpretujemy jako <math>x+1</math>). W następnym wykładzie (patrz [[Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach|Wykład 4]]) przedstawiamy aksjomatyczną teorię w rachunku predykatów nazywaną teorią mnogości ZFC.
  
 
==Modele==
 
==Modele==
Linia 500: Linia 533:
 
drugiej strony jednak dowody z aksjomatów są żmudne i nie sprzyjają
 
drugiej strony jednak dowody z aksjomatów są żmudne i nie sprzyjają
 
budowaniu intuicji. W przypadku rachunku zdań widzieliśmy, że ten
 
budowaniu intuicji. W przypadku rachunku zdań widzieliśmy, że ten
sam zbiór formuł można równoważnie zdefiniować za pomocą [[Logika i teoria mnogości/Wykład 2: Rachunek zdań|matrycy Boolowskiej z Wykładu 2]]. Niestety w przypadku rachunku
+
sam zbiór formuł można równoważnie zdefiniować za pomocą [[Logika i teoria mnogości/Wykład 2: Rachunek zdań|matrycy Boolowskiej z Wykładu 2]] . Niestety w przypadku rachunku
 
predykatów nie istnieje taka skończona struktura, która pozwalałaby
 
predykatów nie istnieje taka skończona struktura, która pozwalałaby
 
nam stwierdzać czy formuła jest twierdzeniem. Zobaczymy jednak, że
 
nam stwierdzać czy formuła jest twierdzeniem. Zobaczymy jednak, że
Linia 519: Linia 552:
  
 
'''Sytuacja 1.'''  
 
'''Sytuacja 1.'''  
:Przypuśćmy, że to zdanie mówi o liczbach naturalnych, a <math>x \prec y</math> jest prawdą wtedy i tylko wtedy gdy liczba <math>\textnormal{x}</math> jest silnie  mniejsza od liczby <math>\textnormal{y}</math>. Wtedy zdanie to powinniśmy uznać za nieprawdziwe, gdyż dla liczby '''0''' nie istnieje silnie mniejsza liczba naturalna.
+
:Przypuśćmy, że to zdanie mówi o liczbach naturalnych, a <math>x \prec y</math> jest prawdą wtedy i tylko wtedy gdy liczba <math>\text{x}</math> jest silnie  mniejsza od liczby <math>\text{y}</math>. Wtedy zdanie to powinniśmy uznać za nieprawdziwe, gdyż dla liczby '''0''' nie istnieje silnie mniejsza liczba naturalna.
  
 
'''Sytuacja 2.'''  
 
'''Sytuacja 2.'''  
:Przypuśćmy, że to zdanie mówi o liczbach całkowitych, a <math>x \prec y</math> jest prawdą wtedy i tylko wtedy gdy liczba <math>\textnormal{x}</math> jest silnie  mniejsza od liczby <math>\textnormal{y}</math>. Wtedy zdanie to powinniśmy uznać prawdziwe. Istotnie, dla każdej liczby całkowitej <math>\textnormal{x}</math> możemy dobrać liczbę <math>\textnormal{y}</math> (na przykład równą <math>x-1</math>) która jest od niej silnie mniejsza.
+
:Przypuśćmy, że to zdanie mówi o liczbach całkowitych, a <math>x \prec y</math> jest prawdą wtedy i tylko wtedy gdy liczba <math>\text{x}</math> jest silnie  mniejsza od liczby <math>\text{y}</math>. Wtedy zdanie to powinniśmy uznać prawdziwe. Istotnie, dla każdej liczby całkowitej <math>\text{x}</math> możemy dobrać liczbę <math>\text{y}</math> (na przykład równą <math>x-1</math>) która jest od niej silnie mniejsza.
  
 
'''Sytuacja 3.'''  
 
'''Sytuacja 3.'''  
:Przypuśćmy, że to zdanie mówi o liczbach naturalnych, a <math>x \prec y</math> jest prawdą wtedy i tylko wtedy gdy liczba <math>\textnormal{x}</math> jest równa liczbie <math>\textnormal{y}</math>. Wtedy zdanie to powinniśmy uznać prawdziwe (do każdej liczby <math>\textnormal{x}</math> możemy dobrać liczbę <math>\textnormal{y}</math> tak aby była równa <math>\textnormal{x}</math>).
+
:Przypuśćmy, że to zdanie mówi o liczbach naturalnych, a <math>x \prec y</math> jest prawdą wtedy i tylko wtedy gdy liczba <math>\text{x}</math> jest równa liczbie <math>\text{y}</math>. Wtedy zdanie to powinniśmy uznać prawdziwe (do każdej liczby <math>\text{x}</math> możemy dobrać liczbę <math>\text{y}</math> tak aby była równa <math>\text{x}</math>).
  
 
}}
 
}}
Linia 545: Linia 578:
 
:1. <math>D</math> - jest niepustym zbiorem (dziedziną).
 
:1. <math>D</math> - jest niepustym zbiorem (dziedziną).
  
:2. <math>\textnormal{I}</math> - jest interpretacją symboli języka taką, że:
+
:2. <math>\text{I}</math> - jest interpretacją symboli języka taką, że:
  
 
::(a) dla symboli stałych: <math>I(c)\in D</math> (symbole stałych są interpretowane jako elementy dziedziny)
 
::(a) dla symboli stałych: <math>I(c)\in D</math> (symbole stałych są interpretowane jako elementy dziedziny)
  
::(b) dla symboli funkcyjnych: <math>I(f):D^k\rightarrow D</math>, gdzie <math>\textnormal{k}</math> jest ilością argumentów <math>\textnormal{f}</math> (symbole funkcyjne są interpretowane jako funkcje z potęgi dziedziny w dziedzinę)
+
::(b) dla symboli funkcyjnych: <math>I(f):D^k\rightarrow D</math>, gdzie <math>\text{k}</math> jest ilością argumentów <math>\text{f}</math> (symbole funkcyjne są interpretowane jako funkcje z potęgi dziedziny w dziedzinę)
  
::(c) dla symboli predykatów: <math>I(p):D^k\rightarrow {0,1}</math>, gdzie <math>k</math> jest ilością argumentów <math>\textnormal{p}</math> (symbole predykatywne są interpretowane jako funkcje przekształcające ciągi elementów z dziedziny w prawdę lub fałsz)
+
::(c) dla symboli predykatów: <math>I(p):D^k\rightarrow {0,1}</math>, gdzie <math>k</math> jest ilością argumentów <math>\text{p}</math> (symbole predykatywne są interpretowane jako funkcje przekształcające ciągi elementów z dziedziny w prawdę lub fałsz)
 
}}
 
}}
 
{{definicja|4.3.||
 
{{definicja|4.3.||
Linia 564: Linia 597:
 
Wartościowanie zmiennych modelu <math>M=(D,I)</math> to funkcja która zmiennym przypisuje wartości dziedziny.
 
Wartościowanie zmiennych modelu <math>M=(D,I)</math> 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.
+
Jeśli ustalimy już wartościowanie zmiennych w modelu to możemy też mówić o wartościach przyjmowanych przez termy.
  
 
{{definicja|4.5. [Wartościowanie termów]||
 
{{definicja|4.5. [Wartościowanie termów]||
Linia 571: Linia 604:
 
możemy rozszerzyć na wszytekie termy. Oznaczymy je przez <math>\hat{\sigma}</math>. Rozszerzenie definiujemy w następujący sposób
 
możemy rozszerzyć na wszytekie termy. Oznaczymy je przez <math>\hat{\sigma}</math>. Rozszerzenie definiujemy w następujący sposób
  
:1. jeśli term <math>\textnormal{t}</math> jest zmienną, <math>\hat{\sigma}(t) = \sigma(t)</math>
+
:1. jeśli term <math>\text{t}</math> jest zmienną, <math>\hat{\sigma}(t) = \sigma(t)</math>
  
:2. jeśli term <math>\textnormal{t}</math> jest stałą, to <math>\hat{\sigma}(t)=I(t)</math> (stałe wartościujemy zgodnie z interpretacją w modelu)
+
:2. jeśli term <math>\text{t}</math> jest stałą, to <math>\hat{\sigma}(t)=I(t)</math> (stałe wartościujemy zgodnie z interpretacją w modelu)
  
:3. jeśli term <math>\textnormal{t}</math> jest postaci <math>f(t_0,..,t_n)</math>, to
+
:3. jeśli term <math>\text{t}</math> jest postaci <math>f(t_0,..,t_n)</math>, to
  
 
<center>
 
<center>
Linia 581: Linia 614:
 
</center>
 
</center>
  
::czyli aby poznać wartość termu najpierw obliczamy wartości poddtermów a potem obliczamy wartość funkcji odpowiadającej w modelu <math>M</math> symbolowi <math>\textnormal{f}</math> na wartościach poddtermów. Funkcję wartościującą termy będziemy często oznaczali tym samym symbolem co wartościowanie zmiennych.
+
::czyli aby poznać wartość termu najpierw obliczamy wartości poddtermów a potem obliczamy wartość funkcji odpowiadającej w modelu <math>M</math> symbolowi <math>\text{f}</math> na wartościach poddtermów. Funkcję wartościującą termy będziemy często oznaczali tym samym symbolem co wartościowanie zmiennych.
 
}}
 
}}
  
 +
<span id="przyklad_4_6">
 
{{przyklad|4.6.||  
 
{{przyklad|4.6.||  
  
Przypuśćmy, że w rozważanym języku symbol <math>o</math> jest symbolem stałej, symbole <math>s,+,\times</math> są symbolami funkcji, symbole <math><,=</math> są symbolami predykatów, <math>{x,y,z}</math> są zmiennymi. Ustalmy model w którym dziedziną jest zbiór liczb naturalnych, a symbole są interpretowane zgodnie z ich zwyczajowym znaczeniem (<math>\textnormal{s}</math>  będziemy interpretować jako jednoargumentową funkcję która każdej liczbie przypisuje
+
Przypuśćmy, że w rozważanym języku symbol <math>o</math> jest symbolem stałej, symbole <math>s,+,\times</math> są symbolami funkcji, symbole <math><,=</math> są symbolami predykatów, <math>{x,y,z}</math> są zmiennymi. Ustalmy model w którym dziedziną jest zbiór liczb naturalnych, a symbole są interpretowane zgodnie z ich zwyczajowym znaczeniem (<math>\text{s}</math>  będziemy interpretować jako jednoargumentową funkcję która każdej liczbie przypisuje
 
liczbę większą o jeden, <math>o</math> interpretujemy jako '''0'''). Jeśli ustalimy ocenę zmiennych tak, że <math>\sigma(x)=2, \sigma(y)=3, \sigma(z)=5</math> to
 
liczbę większą o jeden, <math>o</math> interpretujemy jako '''0'''). Jeśli ustalimy ocenę zmiennych tak, że <math>\sigma(x)=2, \sigma(y)=3, \sigma(z)=5</math> to
  
Linia 596: Linia 630:
  
 
:4 term <math>s(o) \times s(z)</math> będzie wartościowany na '''6'''
 
:4 term <math>s(o) \times s(z)</math> będzie wartościowany na '''6'''
}}
+
}}</span>
+
 
 
{{definicja|4.7. [Waluacja formuł]||
 
{{definicja|4.7. [Waluacja formuł]||
  
 
Zdefiniujemy teraz prawdziwość formuł w ustalonym modelu <math>M=(D,I)</math> przy ustalonym wartościowaniu zmiennych <math>{\sigma}</math>.
 
Zdefiniujemy teraz prawdziwość formuł w ustalonym modelu <math>M=(D,I)</math> przy ustalonym wartościowaniu zmiennych <math>{\sigma}</math>.
  
:1. Jeśli formuła jest postaci <math>p(t_0,..,t_n)</math> (czyli jest formułą atomową), to jest ona prawdziwa wtedy i tylko wtedy jeśli wartością predykatu odpowiadającego w modelu <math>M</math> symbolowi <math>\textnormal{p}</math> (czyli <math>I(p)</math>) na elementach dziedziny odpowiadających termom <math>t_0, \dots, t_n</math> jest prawdą.
+
:1. Jeśli formuła jest postaci <math>p(t_0,..,t_n)</math> (czyli jest formułą atomową), to jest ona prawdziwa wtedy i tylko wtedy jeśli wartością predykatu odpowiadającego w modelu <math>M</math> symbolowi <math>\text{p}</math> (czyli <math>I(p)</math>) na elementach dziedziny odpowiadających termom <math>t_0, \dots, t_n</math> jest prawdą.
  
:2. Jeśli formuła jest postaci <math>A\Rightarrow B</math>, to jest ona prawdziwa wtedy i tylko wtedy, gdy formuła <math>\textnormal{A}</math> jest wartościowana na fałsz lub formuła <math>B</math> jest wartościowana na prawdę (zgodnie z tabelą dla implikacji '''??''')
+
:2. Jeśli formuła jest postaci <math>A\Rightarrow B</math>, to jest ona prawdziwa wtedy i tylko wtedy, gdy formuła <math>\text{A}</math> jest wartościowana na fałsz lub formuła <math>B</math> jest wartościowana na prawdę (zgodnie z tabelą dla implikacji)
  
:3. Jeśli formuła jest postaci <math>\neg A</math> to jest ona prawdziwa wtedy i tylko wtedy gdy formuła <math>\textnormal{A}</math> jest wartościowana na fałsz (zgodnie z tabelą dla negacji '''??''')
+
:3. Jeśli formuła jest postaci <math>\neg A</math> to jest ona prawdziwa wtedy i tylko wtedy gdy formuła <math>\text{A}</math> jest wartościowana na fałsz (zgodnie z tabelą dla negacji)
  
:4. Jeśli formuła jest postaci <math>\forall_x \; A</math>, to jest ona prawdziwa jeśli prawdziwe jest <math>\textnormal{A}</math> i dla każdego wartościowania zmiennych różniącego się od <math>{\sigma}</math> co najwyżej interpretacją symbolu <math>\textnormal{x}</math> prawdziwe jest <math>\textnormal{A}</math>.
+
:4. Jeśli formuła jest postaci <math>\forall_x \; A</math>, to jest ona prawdziwa jeśli prawdziwe jest <math>\text{A}</math> i dla każdego wartościowania zmiennych różniącego się od <math>{\sigma}</math> co najwyżej interpretacją symbolu <math>\text{x}</math> prawdziwe jest <math>\text{A}</math>.
  
:5. Jeśli formuła jest postaci <math>\exists_x \; A</math>, to jest ona prawdziwa jeśli istnieje ocena zmiennych różniąca się od <math>{\sigma}</math> co najwyżej interpretacją symbolu <math>\textnormal{x}</math> taka, że przy tej ocenie prawdziwe jest <math>\textnormal{A}</math>.
+
:5. Jeśli formuła jest postaci <math>\exists_x \; A</math>, to jest ona prawdziwa jeśli istnieje ocena zmiennych różniąca się od <math>{\sigma}</math> co najwyżej interpretacją symbolu <math>\text{x}</math> taka, że przy tej ocenie prawdziwe jest <math>\text{A}</math>.
 
}}
 
}}
Interpretacje kwantyfikatorów, jest w gruncie rzeczy bardzo intuicyjna. Formuła <math>\forall_x A</math> jest prawdziwa wtedy i tylko wtedy gdy dla każdego elementu dziedziny ,,podstawionego" w miejsce <math>\textnormal{x}</math> w formule <math>\textnormal{A}</math> prawdziwa jest formuła <math>\textnormal{A}</math> (uwaga! podstawiamy jedynie w miejsca wolnych wystąpień <math>\textnormal{x}</math>). Analogicznie formuła <math>\exists_x A</math> jest prawdziwa wtedy i tylko wtedy gdy istnieje taki element dziedziny, który  ,,podstawiony" w miejsce <math>\textnormal{x}</math> w formule <math>\textnormal{A}</math> uczyni ją prawdziwa. Dotąd rozważaliśmy kwantyfikator <math>\exists</math> 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.
+
Interpretacje kwantyfikatorów, jest w gruncie rzeczy bardzo intuicyjna. Formuła <math>\forall_x A</math> jest prawdziwa wtedy i tylko wtedy gdy dla każdego elementu dziedziny ,,podstawionego" w miejsce <math>\text{x}</math> w formule <math>\text{A}</math> prawdziwa jest formuła <math>\text{A}</math> (uwaga! podstawiamy jedynie w miejsca wolnych wystąpień <math>\text{x}</math>). Analogicznie formuła <math>\exists_x A</math> jest prawdziwa wtedy i tylko wtedy gdy istnieje taki element dziedziny, który  ,,podstawiony" w miejsce <math>\text{x}</math> w formule <math>\text{A}</math> uczyni ją prawdziwa. Dotąd rozważaliśmy kwantyfikator <math>\exists</math> 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.
  
 
{{przyklad|4.8.||
 
{{przyklad|4.8.||
Linia 623: Linia 657:
 
</math></center>
 
</math></center>
  
jest prawdziwa w modelu z przykładu 4.6 przy ocenie zmiennych <math>\sigma_1</math> takiej, że <math>\sigma_1(x)=0</math>, oraz że jest fałszywa w tym samym modelu dla przy ocenie zmiennej <math>\sigma_2</math> takiej, że <math>\sigma_2(x)=7</math> (bo na przykład wartościując <math>\textnormal{y}</math> na '''3''' formuła <math>x<y \vee x=y</math> nie będzie prawdziwa).
+
jest prawdziwa w modelu z [[#przyklad_4_6|Przykładu 4.6]] przy ocenie zmiennych <math>\sigma_1</math> takiej, że <math>\sigma_1(x)=0</math>, oraz że jest fałszywa w tym samym modelu dla przy ocenie zmiennej <math>\sigma_2</math> takiej, że <math>\sigma_2(x)=7</math> (bo na przykład wartościując <math>\text{y}</math> na '''3''' formuła <math>x<y \vee x=y</math> 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ć
+
Istnieją jednak formuły które są prawdziwe w modelu z [[#przyklad_4_6|Przykładu 4.6]] niezależnie od oceny zmiennych. Przykładem może być
  
 
<center><math>
 
<center><math>
Linia 644: Linia 678:
 
</math></center>
 
</math></center>
  
Rozważmy dowolny model <math>M</math> odpowiedni dla powyższej formuły (odpowiedni to znaczy taki który ustala interpretację symbolu predykatywnego <math>\textnormal{p}</math>). Jeśli w tym modelu nie jest prawdziwa formuła <math>(\forall_x p(x))</math> to cała implikacja 4.1 jest
+
Rozważmy dowolny model <math>M</math> odpowiedni dla powyższej formuły (odpowiedni to znaczy taki który ustala interpretację wszystkich symboli stałychm, funkcji i predykatów występujących w formule, w tym przypadku symbolu predykatywnego <math>\text{p}</math>). Jeśli w tym modelu nie jest prawdziwa formuła <math>(\forall_x p(x))</math> 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 <math>(\forall_x p(x))</math>. Weźmy dowolny taki model i oznaczmy go przez <math>M</math>. Aby pokazać, że <math>(\exists_x p(x))</math> jest prawdziwe w <math>M</math> wystarczy wskazać że istnieje w dziedzinie taka wartość, że podstawiona w miejsce <math>\textnormal{x}</math> uczyni predykat oznaczony przez <math>\textnormal{p}</math> prawdziwym. Formuła <math>(\forall_x p(x))</math> jest prawdziwa w <math>M</math> więc każda wartość podstawiona pod <math>\textnormal{x}</math> czyni predykat odpowiadający <math>\textnormal{p}</math> prawdziwym. Ponieważ dziedzina modelu <math>M</math> 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 <math>{p(x)}</math> jest prawdziwy niezależnie od tego co podstawimy w miejsce <math>\textnormal{x}</math>, to rzeczywiście istnieje taki element dziedziny, który podstawiony w miejsce <math>\textnormal{x}</math> uczyni formułę <math>{p(x)}</math> prawdziwą. A więc formuła <math>\exists_x p(x)</math> również jest prawdziwa. Wobec tego cała implikacja 4.1 jest prawdziwa w <math>M</math>. Pokazaliśmy więc, że formuła 4.1 jest prawdziwa w każdym modelu.
+
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 <math>(\forall_x p(x))</math>. Weźmy dowolny taki model i oznaczmy go przez <math>M</math>. Aby pokazać, że <math>(\exists_x p(x))</math> jest prawdziwe w <math>M</math> wystarczy wskazać że istnieje w dziedzinie taka wartość, że podstawiona w miejsce <math>\text{x}</math> uczyni predykat oznaczony przez <math>\text{p}</math> prawdziwym. Formuła <math>(\forall_x p(x))</math> jest prawdziwa w <math>M</math> więc każda wartość podstawiona pod <math>\text{x}</math> czyni predykat odpowiadający <math>\text{p}</math> prawdziwym. Ponieważ dziedzina modelu <math>M</math> 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 <math>{p(x)}</math> jest prawdziwy niezależnie od tego co podstawimy w miejsce <math>\text{x}</math>, to rzeczywiście istnieje taki element dziedziny, który podstawiony w miejsce <math>\text{x}</math> uczyni formułę <math>{p(x)}</math> prawdziwą. A więc formuła <math>\exists_x p(x)</math> również jest prawdziwa. Wobec tego cała implikacja 4.1 jest prawdziwa w <math>M</math>. Pokazaliśmy więc, że formuła 4.1 jest prawdziwa w każdym modelu.
  
 
{{definicja|4.10.||
 
{{definicja|4.10.||
Linia 658: Linia 692:
 
}}
 
}}
  
Dowód powyższego twierdzenia jest przedstawiony na wykładzie <u>'''Logika dla informatyków.'''</u>
+
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.
 
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.
  
 
{{cwiczenie|4.1||
 
{{cwiczenie|4.1||
  
Rozważmy model <math>M</math>, którego dziedziną będą liczby naturalne, oraz w którym jest jeden predykat binarny oznaczony symbolem <math>\textnormal{p}</math>, który przyjmuje wartość prawdy jeśli pierwszy z jego argumentów dzieli drugi. Napisz formuły które w modelu <math>M</math> są równowążne następującym zdaniom (w kolejnych formułach można wykorzystywać skróty dla formuł zdefiniowanych wcześniej)
+
Rozważmy model <math>M</math>, którego dziedziną będą liczby naturalne, oraz w którym jest jeden predykat binarny oznaczony symbolem <math>\text{p}</math>, który przyjmuje wartość prawdy jeśli pierwszy z jego argumentów dzieli drugi. Napisz formuły które w modelu <math>M</math> są równowążne następującym zdaniom (w kolejnych formułach można wykorzystywać skróty dla formuł zdefiniowanych wcześniej)
  
:1. <math>\textnormal{x}</math> jest równe <math>\textnormal{y}</math>
+
:1. <math>\text{x}</math> jest równe <math>\text{y}</math>
  
:2. <math>\textnormal{x}</math> jest zerem
+
:2. <math>\text{x}</math> jest zerem
  
:3. <math>\textnormal{x}</math> jest jedynką
+
:3. <math>\text{x}</math> jest jedynką
  
:4. <math>\textnormal{x}</math> jest liczbą pierwszą
+
:4. <math>\text{x}</math> jest liczbą pierwszą
  
:5. <math>\textnormal{x}</math> jest kwadratem pewnej liczby pierwszej
+
:5. <math>\text{x}</math> jest kwadratem pewnej liczby pierwszej
  
:6. <math>\textnormal{x}</math> jest iloczynem dwóch różnych liczb pierwszych
+
:6. <math>\text{x}</math> jest iloczynem dwóch różnych liczb pierwszych
  
:7. <math>\textnormal{x}</math> jest iloczynem dwóch liczb pierwszych
+
:7. <math>\text{x}</math> jest iloczynem dwóch liczb pierwszych
  
:8. <math>\textnormal{x}</math> jest potęgą liczby pierwszej
+
:8. <math>\text{x}</math> jest potęgą liczby pierwszej
  
 
:9. dla każdych dwóch liczb istnieje ich największy wspólny dzielnik
 
:9. dla każdych dwóch liczb istnieje ich największy wspólny dzielnik
Linia 685: Linia 719:
 
:10. dla każdych dwóch liczb istnieje ich najmniejsza wspólna wielokrotność
 
:10. dla każdych dwóch liczb istnieje ich najmniejsza wspólna wielokrotność
  
:11 liczby <math>\textnormal{x}</math> i <math>\textnormal{y}</math> są względnie pierwsze
+
:11 liczby <math>\text{x}</math> i <math>\text{y}</math> są względnie pierwsze
 
}}
 
}}
  
Linia 696: Linia 730:
 
:3. jedynka dzieli wszystkie liczby
 
:3. jedynka dzieli wszystkie liczby
  
:4. jest podzielna tylko przez siebie i przez jeden (uwaga, '''1''' nie jest pierwsza)
+
:4. jest podzielna tylko przez siebie i przez jeden (uwaga!, '''1''' nie jest pierwsza)
  
 
:5. ma dokładnie '''3''' różne dzielniki
 
:5. ma dokładnie '''3''' różne dzielniki
  
:6. ma dokładnie '''4''' różne dzielniki
+
:6. ma dokładnie '''2''' różne dzielniki, które są różne od '''x''' i od '''1'''
  
 
:7. jest kwadratem lub iloczynem dwóch różnych liczb pierwszych
 
:7. jest kwadratem lub iloczynem dwóch różnych liczb pierwszych
Linia 715: Linia 749:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
  
: Dla każdej z poniższych formuł w nawiasie zapisujemy skórty których będziemy używać dla tych formuł.
+
: ''Uwaga: przekonwertowane latex2mediawiki; prawdopodobnie trzeba wprowadzi� poprawki''
 
 
:1. <math>\forall_z (p(z,x) \Leftrightarrow p(z,y)</math> (skrót <math>x=y</math>)
 
 
 
:2. <math>\forall_z p(z,x)</math> (skrót <math>x=1</math>)
 
 
 
:3. <math>\forall_z p(x,z)</math> (skrót <math>{x=0}</math>)
 
 
 
:4. <math>(\neg x=1) \wedge \forall_z [p(z,x) \Rightarrow (z=1 \vee z=x)]</math> (skrót <math>Prim(x))</math>.
 
 
 
:5. <math>\forall_z \forall_y (p(z,x) \wedge p(y,x) \wedge (\neg z=1) \wedge (\neg z=x) \wedge (\neg y=1) \wedge (\neg z=x)) \Rightarrow (z=y)</math> (skrót <math>pKw(x))</math>.
 
 
 
:6. <math>\textnormal{x}</math> jest iloczynem dwóch różnych liczb pierwszych (skrót <math>pq(x)</math>.
 
 
 
:7. <math>pKq(x) \vee pq(x)</math>
 
 
 
:8. <math>\forall_{y:\neg(y=1)} \forall_{z:\neg(z=1)} (p(y,x) \wedge p(z,x)) \Rightarrow (\exists_{v:\neg(z=1)} (p(v,y) \wedge p(v,z))</math>
 
 
 
:9. <math>\forall_x \forall_y \exists_z (p(z,x) \wedge p(z,y) \wedge(\forall_v (p(v,x) \wedge p(v,y) \Rightarrow p(v,z)) ))</math>
 
 
 
:10 <math>\forall_x \forall_y \exists_z (p(x,z) \wedge p(y,z) \wedge(\forall_v (p(x,v) \wedge p(y,v) \Rightarrow p(z,v)) ))</math>
 
  
:11. <math>\forall_z ((p(z,x) \wedge p(z,y))\Rightarrow (z=1))</math>
+
:Dla każdej z poniższych formuł w nawiasie zapisujemy skróty których będziemy używać dla tych formuł.
 +
:# <math>\displaystyle p(x,y) \wedge p(y,z)</math>  (skrót <math>\displaystyle x=y</math>),
 +
:# <math>\displaystyle \forall_z p(z,x)</math> (skrót <math>\displaystyle x=0</math>),
 +
:# <math>\displaystyle \forall_z p(x,z)</math> (skrót <math>\displaystyle x=1</math>),
 +
:# <math>\displaystyle \neg (x=1) \wedge \forall_z [p(z,x) \Rightarrow (z=1 \vee z=x)]</math> (skrót <math>\displaystyle Prim(x)</math>),
 +
:# <math>\displaystyle \forall_z \forall_y ((p(z,x) \wedge p(y,x) \wedge (\neg z=1) \wedge (\neg z=x) \wedge (\neg y=1) \wedge (\neg y=x)) \Rightarrow
 +
    (z=y))</math> (skrót <math>\displaystyle \phi_5(x)</math>),
 +
:# <math>\displaystyle \exists_z \exists_y [ p(z,x) \wedge p(y,x) \wedge \neg(z=x) \wedge \neg(z=1) \wedge \neg(y=1) \wedge\neg (y=x) \wedge \neg(y=z)\wedge </math><math> (\forall_v (p(v,x) \Rightarrow ((v=1) \vee (v=x) \vee (v=y) \vee (v=z)))]</math>(skrót <math>\displaystyle \phi_6(x)</math>),
 +
:# <math>\displaystyle \phi_5(x) \vee \phi_6(x)</math>,
 +
:# <math>\displaystyle \forall_{y:\neg(y=1)} \forall_{z:\neg(z=1)} [(p(y,x) \wedge p(z,x)) \Rightarrow (\exists_{v:\neg(z=1)} (p(v,y) \wedge p(v,z)))]</math>,
 +
:# <math>\displaystyle \forall_x \forall_y \exists_z (p(z,x) \wedge p(z,y) \wedge(\forall_v (p(v,x) \wedge p(v,y) \Rightarrow p(v,z)) ))</math>,
 +
:# <math>\displaystyle \forall_x \forall_y \exists_z (p(x,z) \wedge p(y,z) \wedge(\forall_v (p(x,v) \wedge p(y,v) \Rightarrow p(z,v)) ))</math>,
 +
:# <math>\displaystyle \forall_z ((p(z,x) \wedge p(z,y))\Rightarrow (z=1))</math>.
 
</div></div>
 
</div></div>
  
 
{{cwiczenie|4.2||
 
{{cwiczenie|4.2||
  
Rozważmy model <math>M</math>, którego dziedziną będą wszytkie punkty, odcinki i okręgi płaszyczny, oraz w którym jest jeden predykat binarny oznaczony symbolem <math>\textnormal{p}</math>, który przyjmuje wartość prawdy jeśli jego argumenty mają przynajmniej jeden punkt wspólny. Napisz formuły które w modelu <math>M</math> są równowążne następującym zdaniom (w kolejnych formułach można wykorzystywać skróty dla formuł zdefiniowanych wcześniej)
+
Rozważmy model <math>M</math>, którego dziedziną będą wszytkie punkty, odcinki i okręgi płaszyczny, oraz w którym jest jeden predykat binarny oznaczony symbolem <math>\text{p}</math>, który przyjmuje wartość prawdy jeśli jego argumenty mają przynajmniej jeden punkt wspólny. Napisz formuły które w modelu <math>M</math> są równowążne następującym zdaniom (w kolejnych formułach można wykorzystywać skróty dla formuł zdefiniowanych wcześniej)
  
:1. <math>\textnormal{x}</math> jest równe <math>\textnormal{y}</math>
+
:1. <math>\text{x}</math> jest równe <math>\text{y}</math>
  
:2. <math>\textnormal{x}</math> jest nadzbiorem <math>\textnormal{y}</math>
+
:2. <math>\text{x}</math> jest nadzbiorem <math>\text{y}</math>
  
:3. <math>\textnormal{x}</math> jest punktem
+
:3. <math>\text{x}</math> jest punktem
  
:4. <math>\textnormal{x}</math> jest odcinkiem
+
:4. <math>\text{x}</math> jest odcinkiem
  
:5. <math>\textnormal{x}</math> jest okręgiem
+
:5. <math>\text{x}</math> jest okręgiem
  
:6. <math>\textnormal{x}</math> jest równoległe do <math>\textnormal{y}</math>
+
:6. <math>\text{x}</math> jest równoległe do <math>\text{y}</math>
  
:7. <math>\textnormal{x}</math> i <math>\textnormal{y}</math> mają dokładenie jeden punkt wspólny
+
:7. <math>\text{x}</math> i <math>\text{y}</math> mają dokładenie jeden punkt wspólny
  
:8. okręgi <math>\textnormal{x}</math> i <math>\textnormal{y}</math> są do siebie styczne
+
:8. okręgi <math>\text{x}</math> i <math>\text{y}</math> są do siebie styczne
  
:9. okręgi <math>\textnormal{x}</math> i <math>\textnormal{y}</math> są do siebie wewnętrznie styczne i okrąg <math>\textnormal{x}</math> jest okręgiem wewnętrznym
+
:9. okręgi <math>\text{x}</math> i <math>\text{y}</math> są do siebie wewnętrznie styczne i okrąg <math>\text{x}</math> jest okręgiem wewnętrznym
  
:10. okręgi <math>\textnormal{x}</math> i <math>\textnormal{y}</math> są do siebie zewnętrzenie styczne
+
:10. okręgi <math>\text{x}</math> i <math>\text{y}</math> są do siebie zewnętrzenie styczne
  
:11. punkt <math>\textnormal{x}</math> jest końcem odcinka <math>\textnormal{y}</math>
+
:11. punkt <math>\text{x}</math> jest końcem odcinka <math>\text{y}</math>
  
:12. odcinek <math>\textnormal{x}</math> jest styczny do okręgu <math>\textnormal{y}</math>
+
:12. odcinek <math>\text{x}</math> jest styczny do okręgu <math>\text{y}</math>
  
:13. okręgi <math>\textnormal{x}</math> i <math>\textnormal{y}</math> mają taką samą średnicę
+
:13. okręgi <math>\text{x}</math> i <math>\text{y}</math> mają taką samą średnicę
  
:14. okrąg <math>\textnormal{x}</math> ma średnicę mniejszą niż okrąg <math>\textnormal{y}</math>
+
:14. okrąg <math>\text{x}</math> ma średnicę mniejszą niż okrąg <math>\text{y}</math>
 
 
:15. odcinek <math>\textnormal{x}</math> jest krótszy od odcinka <math>\textnormal{y}</math>
 
 
 
:16. odcinek <math>\textnormal{x}</math> jest średnicą okręgu <math>\textnormal{y}</math>
 
 
 
:17. <math>\textnormal{x}</math> jest prostopadłe do <math>\textnormal{y}</math>
 
 
 
:18. odcinki <math>{x,y,z,w}</math> tworzą kwadrat
 
 
}}
 
}}
  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">
  
:1. jeśli <math>\textnormal{x}</math> jest różne od <math>\textnormal{y}</math> to istnieje punkt który należy do jednego obiektu i nie należy do drugiego
+
:# jeśli <math>\displaystyle x</math> jest różne od <math>\displaystyle y</math>, to istnieje punkt, który należy do jednego obiektu i nie należy do drugiego, czyli są równe wtedy i tylko wtedy, gdy mają punkty wspólne dokładnie z tymi samymi elementami,
 
+
:# każdy punkt wspólny jakiegoś obiektu z podzbiorem jest też punktem wspólnym z nadzbiorem,
:2. każdy punkt wspólny jakiegoś obiektu z podzbiorem jest też punktem wspólnym z nadzbiorem
+
:# każde dwa obiekty, które mają punkt wspólny z punktem, mają też punkt wspólny z sobą,
 
+
:# tylko punkt i odcinek mogą mieć istotne nadzbiory, punkty możemy wykluczyć korzystając z formuły w poprzednim punkcie,
:3. punkt ma z każdym obiektem co najwyżej jeden punkt wspólny (okrąg i odcinek może mieć więcej)
+
:# jeśli coś nie jest punktem ani odcinkiem, to jest okręgiem,
 
+
:# odcinki są równoległe, jeśli dowolne ich przedłużenia nie przecinają się lub jeśli mają wspólne przedłużenie,
:4. tylko punkt i odcinek mogą mieć istotne nadzbiory, punkty możemy wykluczyć korzystając z formuły w poprzednim punkcie
+
:# każde dwa ich wspólne punkty muszą być równe,
 
+
:# okręgi są styczne, jeśli mają dokładnie jeden punkt wspólny,
:5. jeśli coś nie jest punktem ani odcinkiem to jest okręgiem  
+
:# jeśli okrąg <math>\displaystyle x</math> jest wewnętrzny, to każdy odcinek, który ma   przynajmniej jeden punkt wspólny z <math>\displaystyle x</math> da się przedłużyć tak, aby przecinał (miał punkt wspólny) z <math>\displaystyle y</math>,
 
+
:# okręgi muszą być styczne i żaden z nich nie może być wewnętrzny,
:6. odcinki są równoległe jeśli dowolne ich przedłużenia nie przecinają się
+
:# istnieje okrąg przechodzący przez <math>\displaystyle x</math> taki, że każdy okrąg styczny do niego w <math>\displaystyle x</math>, jeśli jest zewnętrzny, to ma dokładnie jeden punkt wspólny z <math>\displaystyle y</math>, a jeśli jest wewnętrzny to dwa,
 
+
:# każde przedłużenie odcinka <math>\displaystyle x</math> ma dokładnie jeden punkt wspólny z <math>\displaystyle y</math>,
:7. każde dwa ich wspólne punkty muszą być równe
+
:# istnieją dwa równoległe odcinki styczne do obu okręgów, które nie mają punktów wspólnych,
 
+
:# Możliwe są dwa przypadki:
:8. okręgi są styczne jeśli mają dokładnie jeden punkt wspólny
+
:## 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 <math>\displaystyle x</math> i przecina okrąg <math>\displaystyle y</math> w dwóch różnych punktach,
 
+
:## okrąg <math>\displaystyle x</math> jest wewnątrz okręgu <math>\displaystyle y</math>, czyli nie mają punktów wspólnych i żaden odcinek styczny do <math>\displaystyle y</math> nie przecina <math>\displaystyle x</math>.
:9. jeśli okrąg <math>\textnormal{x}</math> jest wewnętrzny to każdy odcinek, który ma przynajmniej jeden punkt wspólny z <math>\textnormal{x}</math> da się przedłużyć tak, aby przecinał (miał punkt wspólny) z <math>\textnormal{y}</math>
+
</div></div>
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
:10. okręgi muszą być styczne i żaden z nich nie może być wewnętrzny
+
Dla każdej z poniższych formuł w nawiasie zapisujemy skróty, których będziemy używać dla tych formuł.
 
+
# <math>\displaystyle \forall_z p(x,z) \Leftrightarrow p(y,z)</math> (skrót <math>\displaystyle x=y</math>),
:11. istnieje okrąg przechodzący przez <math>\textnormal{x}</math> taki że każdy okrąg styczny do niego w <math>\textnormal{x}</math> jeśli jest zewnętrzny to ma dokładnie jeden punkt wspólny z <math>\textnormal{y}</math> a jeśli jest wewnętrzny to dwa
+
# <math>\displaystyle \forall_z p(y,z) \Rightarrow p(x,z)</math> (skrót <math>\displaystyle x \supset y</math>),
 
+
# <math>\displaystyle \forall_y \forall_z [(p(x,y) \wedge p(x,z)) \Rightarrow p(y,z)]</math> (skrót <math>\displaystyle pkt(x)</math>),
:12. każde przedłużenie odcinka <math>\textnormal{x}</math> dokładnie jeden punkt wpólny z <math>\textnormal{y}</math>
+
# <math>\displaystyle \neg pkt(x) \wedge \exists_y (y \supset x \wedge \exists_z (\neg p(x,z) \wedge p(y,z))</math> (skrót <math>\displaystyle odc(x)</math>),
 
+
# <math>\displaystyle \neg pkt(x) \wedge \neg odc(x)</math> (skrót <math>\displaystyle okr(x)</math>),
:13. istnieją dwa równoległe odcinki styczne do obu okręgów które nie mają punktów wspólnych
+
# <math>\displaystyle odc(x)\wedge odc(y) \wedge [(\exists_z (z \supset x \wedge z \supset y)) \vee(\forall_a \forall_b ( (a \supset x\wedge b \supset y)\Rightarrow \neg p(a,b)))]</math> (skrót <math>\displaystyle \phi_6(x,y)</math>),
 
+
# <math>\displaystyle p(x,y) \wedge \forall_a \forall_b ([pkt(a) \wedge pkt(b)\wedge p(x,a) \wedge p(y,a) \wedge p(x,b) \wedge p(y,b)]\Rightarrow (a=b))</math> (skrót <math>\displaystyle \phi_7(x,y)</math>),
: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 <math>\textnormal{x}</math> i przecina okrąg <math>\textnormal{y}</math> w dwóch różnych punktach
+
# <math>\displaystyle okr(x) \wedge okr(y) \wedge \phi_7(x,y)</math> (skrót <math>\displaystyle \phi_8(x,y)</math>),
 
+
# <math>\displaystyle \phi_8(x,y) \wedge \forall_{a: odc(a) \wedge p(a,x)} \exists_b (b\supset a \wedge p(b,y))</math> (skrót <math>\displaystyle \phi_9(x,y)</math>),
:15. najmniejszy okrąg którego cięciwą jest <math>\textnormal{x}</math> ma mniejszą średnicę niż najmniejszy okrąg którego cięciwą jest <math>\textnormal{y}</math>
+
# <math>\displaystyle \phi_8(x,y) \wedge \neg \phi_9(x,y) \wedge \neg \phi_9(y,x)</math> (skrót <math>\displaystyle \phi_{10}(x,y)</math>),
 
+
# <math>\displaystyle pkt(x) \wedge odc(y) \wedge \exists_{a:okr(a) \wedge p(a,x)} \forall_{b:okr(b)\wedge p(b,x) \wedge \phi_8(a,b)} [(\phi_9(a,b) \Rightarrow \neg \phi_7(a,b))\wedge(\phi_{10}(a,b) \Rightarrow \phi_7(a,b))]</math> (skrót <math>\displaystyle \phi_{11}(x,y)</math>),
:16. najmniejszy okrąg którego cięciwą jest <math>\textnormal{x}</math> ma taką samą średnicę jak <math>\textnormal{y}</math> i <math>\textnormal{x}</math> jest cięciwą <math>\textnormal{y}</math>
+
# <math>\displaystyle odc(x) \wedge okr(y) \wedge \forall_z (z \supset x \Rightarrow \phi_7(y,z))</math> (skrót <math>\displaystyle \phi_{12}(x,y)</math>),
 
+
# <math>\displaystyle okr(x) \wedge okr(y) \wedge \exists_{a:odc(a)\wedge \phi_{12}(a,x) \wedge \phi_{12} (a,y)}    \exists_{b:odc(b)\wedge \phi_{12}(b,x) \wedge \phi_{12} (b,y)}( \neg p(a,b) \wedge\phi_6(a,b)),</math>
:17. istnieje okrąg, który jest styczny do pewnego przedłużenia <math>\textnormal{y}</math> taki, że <math>\textnormal{x}</math> jest równoległy do średnicy okręgu której jeden z końców znajduje się w punkcie styczności z <math>\textnormal{y}</math>
+
#<math>\displaystyle \begin{align} okr(x) \wedge okr(y) &\wedge \\
 
+
            &[(\exists_{a:odc(a)\wedge \phi_{12}(a,x) \wedge \phi_{12} (a,y)}      \exists_{b:odc(b)\wedge \phi_{12}(b,x) \wedge p(b,y) \wedge \neg \phi_7(b,y)} (\neg p(a,b) \wedge \phi_6(a,b)))\\
:18. odcinki mają być równej długości, prostopadłe, różne i mają się odpowiednio stykać końcami (uwaga na kolejność)
+
            \vee& \\
 +
            &(\forall_{a:odc(a) \wedge \phi_{12}(a,y)}\neg p(a,x))].
 +
        \end{align}</math>
 
</div></div>
 
</div></div>
 
 
{{cwiczenie|4.3||
 
{{cwiczenie|4.3||
  
Linia 834: Linia 853:
 
:* istnieją dwa okręgi, które przecinają się w dokładnie '''5''' punktach.
 
:* istnieją dwa okręgi, które przecinają się w dokładnie '''5''' punktach.
 
}}
 
}}
 
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 +
:# <math>\displaystyle \forall_{x:odc(x)} \exists_{k_1:pkt(k_1)} \exists_{k_2:pkt(k_2)} \neg(k_1=k_2) \wedge \phi_{11}(a,k_1) \wedge \phi_{11}(a,k_2) \wedge \forall_{k_3:pkt(k_3)} (\Phi_{11}(k_3,a)\Rightarrow (k_3=k_1 \vee k_3=k_2)) </math>
 +
:# <math>\displaystyle \forall_{x:odc(x)} \exists_{y:odc(y)} y \supset x</math>
 +
:# <math>\displaystyle \forall_{x:pkt(x)} \forall_{y:pkt(y)} \forall_{z:pkt(z)}[
 +
            [\neg\exists_{a:odc(a)} (p(a,x)\wedge p(a,y) \wedge p(a,z))]
 +
            \Rightarrow \exists_{b:okr(b)}( p(b,x)\wedge p(b,y) \wedge p(b,z))]</math>
 +
:# <math>\displaystyle \exists_{a:okr(a)} \exists_{b:okr(b)} \exists_{x_1:pkt(x_1)} \exists_{x_2:pkt(x_2)} \exists_{x_3:p(x_3)} (p(a,x_1) \wedge p(a,x_2) \wedge p(a,x_3) \wedge p(b,x_1) \wedge p(b,x_2) \wedge p(b,x_3) \wedge \forall_{x_4:pkt(x_4)} ((p(a,x_4) \wedge p(b,x_4))\Rightarrow (x_4=x_1 \vee x_4=x_2 \vee x_4=x_3)))</math>
 +
</div></div>
 
{{cwiczenie|4.4||
 
{{cwiczenie|4.4||
  
Linia 848: Linia 874:
  
 
:5. <math>\forall_x \forall_y(p(x,y) \Rightarrow \exists_z (p(x,z)\wedge p(z,y))</math>
 
:5. <math>\forall_x \forall_y(p(x,y) \Rightarrow \exists_z (p(x,z)\wedge p(z,y))</math>
 
:6. ...
 
 
}}
 
}}
  
Linia 858: Linia 882:
 
:1.   
 
:1.   
  
::(a) Formuła jest prawdziwa w zbiorze trójkątów, jeśli <math>\textnormal{p}</math> jest interpretowany jako podobieństwo trójkątów.
+
::(a) Formuła jest prawdziwa w zbiorze trójkątów, jeśli <math>\text{p}</math> jest interpretowany jako podobieństwo trójkątów.
  
::(b) Formuła jest fałszywa w zbiorze odcinków, jeśli <math>p(x,y)</math> jest prawdziwy wtedy i tylko wtedy gdy odcinek oznaczony przez <math>\textnormal{x}</math> jest krótszy od odcinka oznaczonego przez <math>\textnormal{y}</math>.
+
::(b) Formuła jest fałszywa w zbiorze odcinków, jeśli <math>p(x,y)</math> jest prawdziwy wtedy i tylko wtedy gdy odcinek oznaczony przez <math>\text{x}</math> jest krótszy od odcinka oznaczonego przez <math>\text{y}</math>.
  
 
:2.   
 
:2.   
  
::(a) Formuła jest prawdziwa w liczbach naturalnych, jeśli <math>\textnormal{p}</math> jest interpretowane jako słaba mniejszość (czyli <math>p(x,y)</math> jest prawdą jeśli <math>\textnormal{x}</math> jest mniejsze lub równe <math>\textnormal{y}</math>). 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.
+
::(a) Formuła jest prawdziwa w liczbach naturalnych, jeśli <math>\text{p}</math> jest interpretowane jako słaba mniejszość (czyli <math>p(x,y)</math> jest prawdą jeśli <math>\text{x}</math> jest mniejsze lub równe <math>\text{y}</math>). 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 <math>\textnormal{p}</math> 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. <math>(\forall_x \exists_y p(x,y)) \Rightarrow \exists_y \forall_x p(x,y)</math>
+
::(b) Formuła jest fałszywa w liczbach całkowitych, jeśli <math>\text{p}</math> 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. <math>(\forall_x \exists_y p(x,y)) \Rightarrow \exists_y \forall_x p(x,y)</math>
  
 
:3.   
 
:3.   
  
::(a) Formuła jest prawdziwa w zbiorze liczb naturalnych przy następującej interpretacji symboli predykatywncych jeśli <math>{p(x)}</math> jest prawdziwe gdy <math>\textnormal{x}</math> jest liczbą złożoną, a <math>{q(x)}</math> jest prawdziwe gdy <math>\textnormal{x}</math> 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.
+
::(a) Formuła jest prawdziwa w zbiorze liczb naturalnych przy następującej interpretacji symboli predykatywncych jeśli <math>{p(x)}</math> jest prawdziwe gdy <math>\text{x}</math> jest liczbą złożoną, a <math>{q(x)}</math> jest prawdziwe gdy <math>\text{x}</math> 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 <math>{p(x)}</math> jest prawdziwe gdy <math>\textnormal{x}</math> jest liczbą parzystą, a <math>{q(x)}</math> jest prawdziwe gdy <math>\textnormal{x}</math> 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.
+
::(b) Formuła jest prawdziwa w zbiorze liczb naturalnych przy następującej interpretacji symboli predykatywncych jeśli <math>{p(x)}</math> jest prawdziwe gdy <math>\text{x}</math> jest liczbą parzystą, a <math>{q(x)}</math> jest prawdziwe gdy <math>\text{x}</math> 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.   
 
:4.   
 
::<math>(\forall_y [\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(y)]</math>
 
::<math>(\forall_y [\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(y)]</math>
  
::(a) Formuła jest prawdziwa a dowolnym modelu w którym <math>p(y)</math> jest zawsze prawdą. Na przykład w zbiorze liczb naturalnych podzielnych przez '''10''', gdzie <math>{q(x)}</math> prawdziwa, gdy <math>\textnormal{x}</math> jest mniejsze od '''1000''', a <math>p(y)</math> jest prawdziwe gdy <math>\textnormal{y}</math> jest parzyste.
+
::(a) Formuła jest prawdziwa a dowolnym modelu w którym <math>p(y)</math> jest zawsze prawdą. Na przykład w zbiorze liczb naturalnych podzielnych przez '''10''', gdzie <math>{q(x)}</math> prawdziwa, gdy <math>\text{x}</math> jest mniejsze od '''1000''', a <math>p(y)</math> jest prawdziwe gdy <math>\text{y}</math> jest parzyste.
  
::(b) Formuła jest fałszywa w zbiorze czworokątów, gdzie <math>{p(x)}</math> jest prawdą jeśli <math>\textnormal{x}</math> jest kwadratem, a <math>{q(x)}</math> jest prawdą gdy <math>\textnormal{x}</math> jest prostokątem. Wtedy, prawdziwa jest formuła <math>\forall_x (p(x) \Rightarrow q(x))</math> (każdy kwadrat jest prostokątem). Jeśli więc w roli <math>\textnormal{y}</math> w formule <math>(\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(y)]</math> wystąpi prostokąt to poprzednik implikacji będzie prawdziwy, a następnik nie. Nie jest więc prawdą, ze formuła <math>\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(y)</math> jest prawdziwa dla każdego <math>\textnormal{y}</math>.
+
::(b) Formuła jest fałszywa w zbiorze czworokątów, gdzie <math>{p(x)}</math> jest prawdą jeśli <math>\text{x}</math> jest kwadratem, a <math>{q(x)}</math> jest prawdą gdy <math>\text{x}</math> jest prostokątem. Wtedy, prawdziwa jest formuła <math>\forall_x (p(x) \Rightarrow q(x))</math> (każdy kwadrat jest prostokątem). Jeśli więc w roli <math>\text{y}</math> w formule <math>(\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(y)]</math> wystąpi prostokąt to poprzednik implikacji będzie prawdziwy, a następnik nie. Nie jest więc prawdą, ze formuła <math>\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(y)</math> jest prawdziwa dla każdego <math>\text{y}</math>.
  
 
:5.   
 
:5.   
  
::(a) Formuła jest prawdziwa w liczbach wymiernych gdzie <math>p(x,y)</math> jest prawdziwe wtedy i tylko wtedy gdy <math>\textnormal{x}</math> jest silnie mniejsze od <math>\textnormal{y}</math>. Wtedy rzeczywiście dla dowolnych dwóch liczb wymiernych <math>{x,y}</math> takich, że <math>{x<y}</math> istnieje trzecia liczba która znajduje się pomiędzy nimi (np. <math>\frac{x+y}{2}</math>).
+
::(a) Formuła jest prawdziwa w liczbach wymiernych gdzie <math>p(x,y)</math> jest prawdziwe wtedy i tylko wtedy gdy <math>\text{x}</math> jest silnie mniejsze od <math>\text{y}</math>. Wtedy rzeczywiście dla dowolnych dwóch liczb wymiernych <math>{x,y}</math> takich, że <math>{x<y}</math> istnieje trzecia liczba która znajduje się pomiędzy nimi (np. <math>\frac{x+y}{2}</math>).
  
::(b) Formuła jest fałszywa w zbiorze liczb naturalnych w którym <math>p(x,y)</math> interpretujemy jako silną mniejszość. Na przykład dla jeśli <math>\textnormal{x}</math> będziemy wartościować na '''0''', a <math>\textnormal{y}</math> na '''1''' to prawdą będzie <math>p(x,y)</math> (poprzednik implikacji) ale nie będzie prawdą <math>\exists_z (p(x,z)\wedge
+
::(b) Formuła jest fałszywa w zbiorze liczb naturalnych w którym <math>p(x,y)</math> interpretujemy jako silną mniejszość. Na przykład dla jeśli <math>\text{x}</math> będziemy wartościować na '''0''', a <math>\text{y}</math> na '''1''' to prawdą będzie <math>p(x,y)</math> (poprzednik implikacji) ale nie będzie prawdą <math>\exists_z (p(x,z)\wedge
 
p(z,y))</math> bo pomiędzy liczbami '''0''' a '''1''' nie ma żadnej liczby naturalnej.
 
p(z,y))</math> bo pomiędzy liczbami '''0''' a '''1''' nie ma żadnej liczby naturalnej.
  
Linia 906: Linia 930:
 
:6. <math>\forall_x r(x, f(x)) \Rightarrow \forall_x \exists_y r(x,y)</math>
 
:6. <math>\forall_x r(x, f(x)) \Rightarrow \forall_x \exists_y r(x,y)</math>
 
}}
 
}}
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 +
# Weźmy dowolny model <math>\displaystyle M</math> który jest odpowiedni dla badanej formuły. Jeśli w tym modelu nie jest prawdziwa formuła <math>\displaystyle \forall_x p(x)</math> to cała implikacja jest prawdziwa. Przypuśćmy więc, że w modelu <math>\displaystyle M</math> jest prawdziwa formuła <math>\displaystyle \forall_x p(x)</math>. Oznacza to, że dla dowolnego wartościowania <math>\displaystyle v</math> zmiennej <math>\displaystyle x</math> prawdziwa jest formuła <math>\displaystyle \forall_x p(x)</math>. Czyli <math>\displaystyle p(x)</math> jest prawdziwa dla dowolnego wartościowania różniącego się od <math>\displaystyle v</math> jedynie interpretacją symbolu <math>\displaystyle x</math>. W szczególności <math>\displaystyle p(x)</math> jest prawdziwe dla wartościowania, które zmiennej <math>\displaystyle x</math> przypisuje wartość odpowiadającą interpretacji stałej <math>\displaystyle c</math>. Wynika stąd że w <math>\displaystyle M</math> prawdziwa jest formuła <math>\displaystyle p(c)</math>,  a więc również cała implikacja jest prawdziwa.
 +
# Weźmy dowolny model <math>\displaystyle M</math> który jest odpowiedni dla badanej formuły. Jeśli w tym modelu nie jest prawdziwa formuła <math>\displaystyle p(c)</math> to cała implikacja jest prawdziwa. Przypuśćmy więc, że w modelu <math>\displaystyle M</math> jest prawdziwa formuła <math>\displaystyle p(c)</math>. Aby pokazać, że <math>\displaystyle \forall_x p(c)</math> wystarczy pokazać, że przy dowolnym wartościowaniu <math>\displaystyle v</math> prawdziwa jest formuła <math>\displaystyle p(c)</math>. Oczywiście jest to prawdą, gdyż prawdziwość formuły <math>\displaystyle p(c)</math> nie zależy od wartościowania (<math>\displaystyle c</math> jest stałą). Wobec tego cała implikacja jest prawdziwa w modelu <math>\displaystyle M</math>.
 +
# Weźmy dowolny model <math>\displaystyle M</math> który jest odpowiedni dla badanej formuły. Jeśli w tym modelu nie jest prawdziwa któraś z formuł  <math>\displaystyle \forall_x(p(x) \Rightarrow q(x)),(\forall_x p(x)) </math> to cała implikacja jest prawdziwa. Przypuśćmy więc, że w modelu <math>\displaystyle M</math> obie formuły są prawdziwe. Pokażemy, że prawdziwa jest formuła <math>\displaystyle \forall_x q(x)</math>. Wystarczy więc pokazać, że <math>\displaystyle q(x)</math> jest prawdą dla dowolnego wartościowania. Niech <math>\displaystyle v</math> będzie dowolnym wartościowaniem. Z przesłanek implikacji otrzymujemy, że dla wartościowania <math>\displaystyle v</math> prawdziwe są formuły <math>\displaystyle p(x) \Rightarrow q(x)</math> oraz <math>\displaystyle p(x)</math>. Z własności implikacji wynika, że w takim przypadku konieczne jest aby <math>\displaystyle q(x)</math> było wartościowane na prawdę. Wobec dowolności wyboru wartościowania otrzymujemy prawdziwość <math>\displaystyle \forall_x q(x)</math> w modelu <math>\displaystyle M</math>.
 +
# Przypuśćmy, że formuła  <math>\displaystyle \neg \forall_x \neg p(x)</math>  jest prawdziwa w <math>\displaystyle M</math>. Jest to równoważne faktowi, że istnieje wartościowanie <math>\displaystyle v</math>, dla którego nie jest prawdą <math>\displaystyle \forall_x \neg p(x)</math>, czyli że nie dla wszystkich wartościowań <math>\displaystyle v'</math> różniących się od <math>\displaystyle v</math> jedynie na <math>\displaystyle x</math>, formuła <math>\displaystyle \neg p(x)</math> jest prawdziwa. Czyli dla pewnego wartościowania <math>\displaystyle v'</math> formuła <math>\displaystyle \neg p(x)</math> musi być fałszywa. Oznacza to że dla wartościowania <math>\displaystyle v'</math> prawdziwa jest formuła <math>\displaystyle p(x)</math>. Ponieważ jedyną zmienną występującą w <math>\displaystyle p(x)</math> jest <math>\displaystyle x</math> to ostatnie zdanie jest równoważne stwierdzeniu że  formuła <math>\displaystyle \exists_x p(x)</math> jest prawdziwa w modelu <math>\displaystyle M</math>.
 +
# Dowód analogiczny do poprzedniego punktu.
 +
# Weźmy dowolny model <math>\displaystyle M</math> który jest odpowiedni dla badanej formuły. Jeśli w tym modelu nie jest prawdziwa formuła <math>\displaystyle \forall_x r(x, f(x))</math> to cała implikacja jest prawdziwa. Przypuśćmy więc, że w modelu <math>\displaystyle M</math> jest prawdziwa formuła <math>\displaystyle \forall_x r(x, f(x))</math>. Pokażemy, że w <math>\displaystyle M</math> jest prawdziwa formuła <math>\displaystyle \forall_x \exists_y r(x,y)</math>. Weźmy dowolne wartościowanie <math>\displaystyle v</math>, pokażemy że przy tym wartościowaniu prawdziwa jest formuła <math>\displaystyle \forall_x \exists_y r(x,y)</math>. Oznacza to, że dla dowolnego wartościowania <math>\displaystyle v'</math> różniącego się od <math>\displaystyle v</math> jedynie wartością zmiennej <math>\displaystyle x</math> trzeba pokazać że prawdziwa jest formuła <math>\displaystyle \exists_y r(x,y)</math>. Weźmy dowolne takie wartościowanie <math>\displaystyle v'</math>. Aby pokazać prawdziwość  <math>\displaystyle \exists_y r(x,y)</math> skonstruujemy wartościowanie <math>\displaystyle v''</math> różniące sie od <math>\displaystyle v'</math> jedynie wartością zmiennej <math>\displaystyle y</math>, dla którego prawdziwa jest formuła <math>\displaystyle r(x,y)</math>. Ponieważ w <math>\displaystyle M</math> jest prawdziwa formuła <math>\displaystyle \forall_x r(x,f(x))</math> to w szczególności dla wartościowania <math>\displaystyle v'</math> prawdziwa jest <math>\displaystyle r(x,f(x))</math>. Wobec tego ustalmy wartościowanie <math>\displaystyle v''</math> tak aby było zgodne z <math>\displaystyle v'</math> poza zmienną <math>\displaystyle y</math> na której przyjmuje tę samą wartość co term <math>\displaystyle f(x)</math> w wartościowaniu <math>\displaystyle v'</math>. Wtedy <math>\displaystyle r(x,y)</math> jest prawdą przy wartośiowaniu <math>\displaystyle v''</math> a zatem przy wartościowaniu <math>\displaystyle v'</math> prawdą jest formuła <math>\displaystyle \exists_y r(x,y)</math>. Wobec dowolności wyboru <math>\displaystyle v'</math> i <math>\displaystyle v</math> prawdą jest, że w modelu <math>\displaystyle M</math> spełniona jest formuła <math>\displaystyle \forall_x \exists_y r(x,y)</math>, a więc również cała implikacja
 +
 +
<center><math>\displaystyle \forall_x r(x, f(x)) \Rightarrow \forall_x \exists_y r(x,y)
 +
</math></center>
  
 +
 +
</div></div>
 
{{cwiczenie|4.6||
 
{{cwiczenie|4.6||
  

Aktualna wersja na dzień 15:26, 10 cze 2020

Wprowadzenie

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

Jeśli jest liczbą pierwszą to jest liczbą nieparzystą lub jest równe 2.

Opisaliśmy je wtedy formułą

w której odpowiadały odpowiednio zdaniom

1. jest liczbą pierwszą,
2. jest liczbą nieparzystą,
3. jest równe 2.

Podstawiając zamiast zdania jest liczbą pierwszą zmienną zdaniową ukrywamy jednak część informacji. Zdanie to mówi przecież o pewnej liczbie , co więcej zdania i dotyczą tej samej liczby . Zapiszmy więc zamiast aby podkreślić fakt że prawdziwość zależy od tego jaką konkretną wartość przypiszemy zmiennej . Zdanie będzie prawdziwe jeśli za 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 dopóki nie podstawimy w miejsce jakiejś konkretnej liczby. Z drugiej strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce zdanie będzie prawdziwe. Możemy więc przeformułować je jako

Dla każdej liczby naturalnej , jeśli jest liczbą pierwszą to jest liczbą nieparzystą lub 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 jest liczbą pierwszą, jest liczbą nieparzystą, 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 jest tą samą liczbą co i fałszu w przeciwnym przypadku. Formuły atomowe będą opisywały proste zdania typu jest liczbą pierwszą, dzieli , jest równe . 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 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 i są formułami, to oraz są formułami.
3. Jeśli jest formułą i 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 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 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 które spełnia spełnione jest
2. istnieje 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 jest zmienną, a jest formułą to każda pozycję w napisie na której występuje symbol i nie jest poprzedzony bezpośrednio kwantyfikatorem, nazywamy wystąpieniem zmiennej . 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 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 ma związanych wystąpień 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 , która nie ma wolnych wystąpień w następująca formuła jest aksjomatem
(c) Dla dowolnych formuł i aksjomatem jest formuła

Poza tym do aksjomatów dorzucamy również wszystkie generalizacje formuł pasujących do powyższych schematów. Generalizacja formuły jest to ta sama formuła poprzedzona blokiem kwantyfikatorów ogólnych - dla dowolej formuły oraz dowolnych zmiennych formuła jest generalizacją .

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 .


Przykład teorii w rachunku predykatów

W oparciu o logikę predykatów możemy budować nowe teorie, dokładając inne, tzw. pozalogiczne aksjomaty. W językach wielu teorii pojawia się symbol predykatywny , mający symbolizować równość. Ponieważ zwykle wymagamy aby te same własności były spełnione dla , zostały wyodrębnione specjalne aksjomaty dla równości. Aksjomaty, te to wszystkie formuły oraz ich generalizacje odpowiadające poniższym schematom:

1. , dla każdego termu


2. , dla dowolnego symbolu funkcyjnego , oraz dowolnych termów , gdzie jest ilością argumentów symbolu


3. , dla dowolnego symbolu predykatywnego , oraz dowolnych termów , gdzie jest ilością argumentów symbolu


Rozważmy język, w którym mamy jeden binarny symbol predykatywny , jeden symbol stałej oraz symbole funkcyjne . Zgodnie z przyjętą konwencją termy i formuły będziemy zapisywać infixowo. Do aksjomatów logicznych, oraz aksjomatów dla równości, dokładamy następujące aksjomaty:

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

Teorią Q nazwiemy wszystkie formuły w ustalonym języku które da się udowodnić z aksjomatów logiki predykatów z dołączonymi aksjomatami równości oraz 1-7. Nietrudno się przekonać, że wszystkie twierdzenia teorii Q są prawdziwe w liczbach naturalnych, przy naturalnej interpretacji występujących symboli ( interpretujemy jako ). W następnym wykładzie (patrz Wykład 4) przedstawiamy aksjomatyczną teorię w rachunku predykatów nazywaną teorią mnogości ZFC.

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 jest silnie mniejsza od liczby . 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 jest silnie mniejsza od liczby . Wtedy zdanie to powinniśmy uznać prawdziwe. Istotnie, dla każdej liczby całkowitej możemy dobrać liczbę (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 jest równa liczbie . Wtedy zdanie to powinniśmy uznać prawdziwe (do każdej liczby możemy dobrać liczbę tak aby była równa ).

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. - 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 jest ilością argumentów (symbole funkcyjne są interpretowane jako funkcje z potęgi dziedziny w dziedzinę)
(c) dla symboli predykatów: , gdzie jest ilością argumentów (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ż wartościowanie zmiennych w modelu to możemy też mówić o wartościach przyjmowanych przez termy.

Definicja 4.5. [Wartościowanie termów]

Przy ustalonym modelu wartościowanie zmiennych możemy rozszerzyć na wszytekie termy. Oznaczymy je przez . Rozszerzenie definiujemy w następujący sposób

1. jeśli term jest zmienną,
2. jeśli term jest stałą, to (stałe wartościujemy zgodnie z interpretacją w modelu)
3. jeśli term jest postaci , to

czyli aby poznać wartość termu najpierw obliczamy wartości poddtermów a potem obliczamy wartość funkcji odpowiadającej w modelu symbolowi 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 ( 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 (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 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 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 i dla każdego wartościowania zmiennych różniącego się od co najwyżej interpretacją symbolu prawdziwe jest .
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 taka, że przy tej ocenie prawdziwe jest .

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 w formule prawdziwa jest formuła (uwaga! podstawiamy jedynie w miejsca wolnych wystąpień ). Analogicznie formuła jest prawdziwa wtedy i tylko wtedy gdy istnieje taki element dziedziny, który ,,podstawiony" w miejsce w formule 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 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ę wszystkich symboli stałychm, funkcji i predykatów występujących w formule, w tym przypadku symbolu predykatywnego ). 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 uczyni predykat oznaczony przez prawdziwym. Formuła jest prawdziwa w więc każda wartość podstawiona pod czyni predykat odpowiadający 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 , to rzeczywiście istnieje taki element dziedziny, który podstawiony w miejsce 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 , 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. jest równe
2. jest zerem
3. jest jedynką
4. jest liczbą pierwszą
5. jest kwadratem pewnej liczby pierwszej
6. jest iloczynem dwóch różnych liczb pierwszych
7. jest iloczynem dwóch liczb pierwszych
8. 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 i 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 , 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. jest równe
2. jest nadzbiorem
3. jest punktem
4. jest odcinkiem
5. jest okręgiem
6. jest równoległe do
7. i mają dokładenie jeden punkt wspólny
8. okręgi i są do siebie styczne
9. okręgi i są do siebie wewnętrznie styczne i okrąg jest okręgiem wewnętrznym
10. okręgi i są do siebie zewnętrzenie styczne
11. punkt jest końcem odcinka
12. odcinek jest styczny do okręgu
13. okręgi i mają taką samą średnicę
14. okrąg ma średnicę mniejszą niż okrąg
Podpowiedź
Rozwiązanie

Ć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.
Rozwiązanie

Ć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.
Rozwiązanie

Ćwiczenie 4.5

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

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

Ć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