|
|
| (Nie pokazano 40 wersji utworzonych przez 4 użytkowników) |
| Linia 1: |
Linia 1: |
| ==Wprowadzenie==
| | --- przykładowo jak zrobić pierwsze pytanie z pierwszego modułu --- |
|
| |
|
| Na początku rozdziału o logice zdaniowej rozważaliśmy zdanie
| | <quiz type="exclusive"> |
| | Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które |
| | spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności, |
| | dziedzin i kodziedzin morfizmów. |
| | <wrongoption>Prawda</wrongoption> |
| | <rightoption>Fałsz</rightoption> |
| | </quiz> |
| | --------------------------------------------------------------------- |
|
| |
|
| <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>
| |
|
| |
|
| Opisaliśmy je wtedy formułą
| | <quiz> |
| | Zaznacz zdania prawdziwe dotyczące podłogi i sufitu: |
| | |
| | |
| | <option><math>n\geq 2^{\left\lceil \log_2 n \right\rceil}</math>,</option> |
| | |
| | <option><math>n\leq 2^{\left\lceil \log_2 n \right\rceil}</math>,</option> |
| | |
| | <option><math>\left\lceil \log_2 \left\lceil n/2 \right\rceil \right\rceil=\left\lceil \log_2 \left( n/2 \right) \right\rceil</math>,</option> |
| | |
| | <option><math>\left\lfloor \log_2 \left\lceil n/2 \right\rceil \right\rfloor=\left\lfloor \log_2 \left( n/2 \right) \right\rfloor</math>.</option> |
| | </quiz> |
|
| |
|
| <center><math>
| |
|
| |
|
| p \Rightarrow (q \vee r).
| | <quiz> |
| </math></center> | | Dowolny niepusty podzbiór <math>S\subseteq \mathbb{N}</math> zbioru liczb naturalnych |
| | |
| | |
| | ma w sobie liczbę największą |
| | |
| | ma w sobie liczbę najmniejszą |
| | |
| | ma w sobie liczbę największą oraz liczbę najmniejszą |
| | |
| | ma w sobie liczbę najmniejszą ale nigdy nie ma największej |
| | </quiz> |
|
| |
|
| w której <math>p,q,r</math> odpowiadały odpowiednio zdaniom
| |
|
| |
|
| :1. <math>\textnormal{n}</math> jest liczbą pierwszą,<br/>
| | <quiz> |
| :2. <math>\textnormal{n}</math> jest liczbą nieparzystą,<br/>
| | Zbiór <math>S\subseteq\mathbb{N}</math> jest taki, że jeśli <math>s\in S</math> to <math>s+1\in S</math> . |
| :3. <math>\textnormal{n}</math> jest równe '''2'''.<br/>
| | Jeśli <math>9\in S</math> , to: |
|
| |
|
| 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>\textnormal{p}</math> aby podkreślić fakt że prawdziwość <math>\textnormal{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ć
| | <math>S=\mathbb{N}</math> |
|
| |
|
| <center><math> | | <math>S=\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math> |
|
| |
|
| p(n) \Rightarrow (q(n) \vee r(n)).
| | <math>S\subseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math> |
| </math></center> | |
|
| |
|
| | <math>S\supseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math> |
| | </quiz> |
|
| |
|
| Zwróćmy uwagę jednak, że trudno ocenić prawdziwość zdania <math>\textnormal{p}</math> dopóki
| |
| nie podstawimy w miejsce <math>\textnormal{n}</math> jakiejś konkretnej liczby. Z drugiej
| |
| strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce <math>\textnormal{n}</math>
| |
| 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'''.
| | <quiz> |
| | Zbiór <math>S\subseteq\mathbb{N}</math> jest taki, że jeśli <math>a,b\in S</math> , |
| | to <math>a+b\in S</math> oraz <math>a+b+1\not\in S</math> . |
| | Jeśli <math>0,2 \in S</math> , to: |
|
| |
|
| Aby móc formalnie zapisywać zdania takie jak powyższe wprowadzimy
| | <math>S=\mathbb{N}</math> |
| kwantyfikator <math>\forall</math> który będzie oznaczał ,,dla każdego" oraz
| |
| <math>\exists</math> który będzie oznaczał ,,istnieje". Każde wystąpienie
| |
| kwantyfikatora będzie dotyczyło pewnej zmiennej. W naszym
| |
| przykładzie napiszemy
| |
|
| |
|
| <center><math> | | zbiór <math>S</math> zawiera wszystkie liczby naturalne, które są parzyste |
|
| |
|
| \forall_n p(n) \Rightarrow (q(n) \vee r(n)).
| | zbiór <math>S</math> jest zawarty w zbiorze liczb naturalnych, które są parzyste |
| </math></center> | |
|
| |
|
| Możemy teraz powiedzieć, że powyższa formuła jest prawdziwa w
| | zbiór <math>S</math> jest zbiorem wszystkich liczb naturalnych, które są parzyste |
| zbiorze liczb naturalnych, gdzie <math>p(n),q(n),r(n)</math> będą oznaczać
| | </quiz> |
| odpowiednio <math>\textnormal{n}</math> jest liczbą pierwszą, <math>\textnormal{n}</math> jest liczbą nieparzystą, <math>\textnormal{n}</math> jest równe '''2'''.
| |
|
| |
|
| Przy tej samej interpretacji <math>p(n),q(n)</math> moglibyśmy wyrazić zdanie
| |
|
| |
|
| <center>Istnieje parzysta liczba pierwsza.</center> | | <quiz> |
| | Ostatnią cyfrą liczby <math>3^{3^n}</math> jest: |
|
| |
|
| jako
| | zawsze <math>3</math> |
|
| |
|
| <center><math> | | zawsze <math>3</math> lub <math>7</math> |
|
| |
|
| \exists_n p(n) \wedge \neg q(n)
| | zawsze <math>7</math> |
| </math></center> | |
|
| |
|
| ==Język rachunku predykatów==
| | jakakolwiek z cyfr <math>0,1,2,3,4,5,6,7,8,9</math> |
| | </quiz> |
|
| |
|
| Podobnie jak dla rachunku zdań zaczniemy od zdefiniowania języka rachunku predykatów.
| |
|
| |
|
| {{definicja|2.1|| | | <quiz> |
| Alfabet języka rachunku predykatów składa się z:
| | Jeśli <math>Z \subseteq \mathbb{N}</math> jest jakimś zbiorem liczb naturalnych, |
| | który wraz z każdym początkowym fragmentem zbioru <math>\mathbb{N}</math> |
| | postaci <math>\left\lbrace 0,\ldots,k-1 \right\rbrace</math> zawiera również kolejną liczbę <math>k</math>, to wtedy |
|
| |
|
| :1. symboli stałych (a,b,c,)
| | zbiór <math>Z</math> zawiera wszystkie liczby naturalne poza skończonym podzbiorem |
|
| |
|
| :2. symboli zmiennych (x,y,z,)
| | zbiór <math>Z</math> zawiera wszystkie liczby naturalne |
|
| |
|
| :3. symboli funkcji <math>(f^1, f^2, f^3, \dots ,g^1,g^2,g^3, \dots ,h^1, h^2, h^3,
| | zbiór <math>Z</math> zawiera nieskończenie wiele liczb naturalnych |
| \dots)</math>
| |
|
| |
|
| :4. symboli predykatów <math>(p^1, p^2, p^3, \dots ,q^1,q^2,q^3, \dots ,r^1, r^2, r^3,
| | zbiór <math>Z</math> jest pusty |
| \dots)</math>
| | </quiz> |
|
| |
|
| :5. spójników logicznych: <math>\Rightarrow,\neg</math>
| |
|
| |
|
| :6. kwantyfikatorów: <math>\forall,\exists</math>
| | <quiz> |
| | Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, że nikt z nikim się nie lubił. Jeden z nich, aby naprawić relacje, wymyślił, że jeżeli wszyscy znajdujący się wewnątrz klasy będą pogodzeni, to nie powinno być problemu, aby któryś stojący na zewnątrz klasy wszedł do środka i pogodził się ze wszystkimi, będącymi w klasie. Drugi z nich zauważył jednak, że nic z tego nie wyjdzie, bo w środku nikogo nie ma. Czy klasa jest w stanie się pogodzić? |
|
| |
|
| :7. nawiasów i przecinków (niekonieczne)
| | klasa na pewno się nie pogodzi |
|
| |
|
| 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.
| | klasa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia |
| }}
| |
|
| |
|
| Zwykle będą nam wystarczały symbole wymienione w nawiasach. Zanim przystąpimy do konstrukcji formuł zdefiniujemy tzw. termy.
| | jeżeli w klasie byłaby już jedna osoba, to reszta klasy miałaby szansę się pogodzić |
|
| |
|
| {{definicja|2.2 [Termy]||
| | jeżeli w klasie byłyby już co najmniej dwie osoby, |
| | przy czym osoby w klasie byłyby ze sobą pogodzone, |
| | to reszta klasy miałaby szansę się pogodzić |
| | </quiz> |
|
| |
|
| :1. każdy symbol stałej jest termem
| |
|
| |
| :2. każdy symbol zmiennej jest termem
| |
|
| |
| :3. jeśli <math>t_1,..,t_n</math> są termami, a <math>\alpha^n</math> jest symbolem funkcyjnym, to <math>\alpha^n(t_1,..,t_n)</math> jest termem
| |
|
| |
| :4. nic innego nie jest termem
| |
| }}
| |
| {{przyklad|2.3||
| |
| | | |
| Jeśli rozważymy język, w którym '''1''','''2''','''3''' są symbolami stałych, <math>{x,y}</math> są symbolami zmiennych a <math>+^2,\times^2,-^1,s^1</math> są symbolami funkcji to poniższe napisy będą termami
| | <quiz> |
| | | Jeśli <math>S\subseteq\mathbb{N}</math> , to: |
| :1. <math>+^2(1,x)</math>
| | |
| | | zbiór <math>S</math> ma element największy |
| :2. <math>-^1(3)</math>
| | |
| | | zbiór <math>S</math> ma element najmniejszy |
| :3. <math>s^1(-^1(3))</math>
| |
| | |
| :4. <math>\times^2(y,+^2(x,-^1(2)))</math>
| |
| | |
| 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. <math>1+x</math>
| |
| | |
| :2. <math>-3</math>
| |
| | |
| :3. <math>s(-3)</math>
| |
| | |
| :4. <math>y\times(x+(-3))</math>
| |
| | |
| }}
| |
| | |
| 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 <math>t_1,..,t_n</math> są termami, a <math>\beta^n</math> jest symbolem predykatu, to <math>\beta^n(t_1,..,t_n)</math> jest formułą atomową. | |
| }}
| |
| {{przyklad|2.5||
| |
| | |
| Kontynuując przykład dotyczący termów przyjmijmy dodatkowo, że w rozważanym języku <math>p^3, q^1, =^2</math> są symbolami predykatów wtedy formułami atomowymi będą
| |
| | |
| :1. <math>p^3(1+x,-3,y\times(x+(-3)))</math>
| |
| | |
| :2. <math>q^1(1)</math>
| |
| | |
| :3. <math>=^2(y\times(x+(-3)),2)</math>
| |
| | |
| Stosując analogiczną konwencję jak dla termów powyższe formuły atomowe zapiszemy jako
| |
| | |
| :1. <math>p(1+x,-3,y\times(x+(-3)))</math>
| |
| | |
| :2. <math>q(1)</math>
| |
| | |
| :3. <math>y\times(x+(-3))=2</math>
| |
| | |
| }} | |
| | |
| 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.
| |
| | |
| '''Uwaga 2.6''' 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
| |
| powyższy napis powinniśmy przeczytać jako
| |
| | |
| <center><math>y\times(x+(-3))</math> jest równe temu, że '''1''' jest liczbą
| |
| nieparzystą.</center>
| |
| | |
| 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 <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. | |
| | |
| :3. Jeśli <math>\textnormal{A}</math> jest formułą i <math>\textnormal{x}</math> jest zmienną, to <math>\forall_x A</math> jest formułą.
| |
| | |
| :4. Nic innego nie jest formułą.
| |
| }}
| |
| Przyjmujemy analogiczną konwencję dotyczącą nawiasowania jak dla rachunku zdań.
| |
| | |
| {{przyklad|2.8||
| |
| | |
| W oznaczeniach z poprzednich przykładów poniższe napisy nie są formułami rachunku predykatów
| |
| | |
| :* <math>x+1</math>
| |
| | |
| :* <math>(x=1) \Rightarrow 2</math>
| |
| | |
| :* <math>\forall_x (x+y)</math>
| |
| | |
| :* <math>\forall_x (\neg x)</math>
| |
| | |
| Poniższe napisy są formułami rachunku predykatów
| |
| | |
| :* <math>x=1</math>
| |
| | |
| :* <math>x=1 \Rightarrow x=2</math>
| |
| | |
| :* <math>\forall_x q(x+y)</math>
| |
| | |
| :* <math>\forall_x \neg (x=0)</math>
| |
| | |
| :* <math>\forall_x \forall_z \neg (x=0)</math>
| |
| | |
| :* <math>\forall_x \forall_y \neg (x=y)</math>
| |
| | |
| }}
| |
| | |
| {{cwiczenie|2.1||
| |
| | |
| Z poniższych formuł wypisz wszytkie termy i formuły atomowe
| |
| | |
| :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>
| |
| | |
| <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">
| |
| | |
| :1.
| |
| ::* termy: <math>x,y,s(x),s(y)</math>
| |
| | |
| ::* formuły atomowe: <math>s(x)=s(y),x=y</math>
| |
| | |
| :2.
| |
| | |
| ::* termy: <math>x,s(x),0</math>
| |
| | |
| ::* formuły atomowe: <math>s(x)=0</math>
| |
| | |
| :3.
| |
| | |
| ::* termy: <math>x,0,y,s(y)</math>
| |
| | |
| ::* formuły atomowe: <math>x=0, s(y)=x</math>
| |
| | |
| :4.
| |
| | |
| ::* termy: <math>x,0,x+0</math>
| |
| | |
| ::* formuły atomowe: <math>x+0=x</math>
| |
| | |
| :5
| |
| | |
| ::* termy: <math>x,y,s(y),x+y,s(x+y)</math>
| |
| | |
| ::* formuły atomowe: <math>x+s(y)=s(x+y)</math>
| |
| </div></div>
| |
| }}
| |
| | |
| | |
| Często będziemy używać dodatkowych spójników <math>\wedge, \vee, \Leftrightarrow</math>.
| |
| Ponieważ wszystkie dadzą się zdefiniować przy pomocy <math>\Rightarrow</math> i
| |
| <math>\neg</math> 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. <math>\phi \vee \psi \stackrel{\textrm{def}}{\equiv} \phi \Rightarrow (\phi \Rightarrow \psi)</math> (może jakoś inaczej?)
| |
| | |
| :2. <math>\phi \wedge \psi \stackrel{\textrm{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>
| |
| | |
| ===Kwantyfikator egzystencjaly===
| |
| | |
| Wprowadzimy jeszcze jeden bardzo ważny skrót - kwantyfikator
| |
| egzystencjalny, oznaczamy go przez <math>\exists</math> i definiujemy w
| |
| następujący sposób
| |
| | |
| <center><math>
| |
| | |
| \exists_x \phi \stackrel{\textrm{def}}{\equiv} \neg (\forall_x \neg \phi)
| |
| </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>
| |
| 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
| |
| | |
| <center><math>
| |
| | |
| \exists_n [p(n) \wedge \neg q(n)]
| |
| </math></center>
| |
| | |
| powinniśmy rozumieć jako
| |
| | |
| <center><math>
| |
| | |
| \neg \forall_n \neg (p(n) \wedge \neg q(n)).
| |
| </math></center>
| |
| | |
| ===Kwantyfikatory ograniczone===
| |
| | |
| 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>
| |
| | |
| :2. <math>\exists_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \exists_x \phi \wedge \psi</math>
| |
| | |
| i czytamy
| |
| | |
| :1. dla każdego <math>\textnormal{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>
| |
| | |
| Zgodnie z tą konwencją formułę 1.1 możemy zapisać następująco
| |
| | |
| | |
| <center><math>
| |
| | |
| \forall_{n:p(n)} q(n) \vee r(n).
| |
| </math></center>
| |
| | |
| | |
| Podobnie formułę '''??''' zapiszemy jako
| |
| | |
| <center><math>
| |
| | |
| \exists_{n:p(n)}\neg q(n)
| |
| </math></center>
| |
| | |
| | |
| {{cwiczenie|2.2||
| |
| | |
| Wyeliminuj wszystkie skróty z napisu
| |
| | |
| <center><math>
| |
| | |
| \exists_{x:\phi} \psi
| |
| </math></center>
| |
| | |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź 1 </span><div class="mw-collapsible-content" style="display:none">
| |
| | |
| : eliminacja kwantyfikatora ograniczonego:
| |
| | |
| <center><math>
| |
| | |
| \exists_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv}
| |
| \exists_x \phi \wedge \psi
| |
| </math></center>
| |
| </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">Podpowiedź 2 </span><div class="mw-collapsible-content" style="display:none">
| |
| | |
| : eliminacja kwantyfikatora egzystencjalnego
| |
| | |
| <center><math>
| |
| | |
| \exists_x \phi \wedge \psi \stackrel{\textrm{def}}{\equiv}
| |
| \neg \forall_x \neg(\phi \wedge \psi)
| |
| </math></center>
| |
| </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">
| |
| : Pozostało jedynie wyeliminować <math>\wedge</math>
| |
| | |
| <center><math>
| |
| | |
| \neg \forall_x \neg(\phi \wedge \psi) \stackrel{\textrm{def}}{\equiv}
| |
| \neg \forall_x \neg(\neg(\phi \Rightarrow \neg \psi))
| |
| </math></center>
| |
| </div></div>
| |
| }}
| |
| | |
| ===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.
| |
| | |
| {{definicja|2.9||
| |
| Rodzaj wystąpienia zmiennej w formule określamy zgodnie z poniższymi regułami:
| |
| | |
| :1. Jeśli <math>{\gamma}</math> jest formułą atomową to wszystkie wystąpienia zmiennych w napisie <math>{\gamma}</math> są '''wolne'''.
| |
| | |
| :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'''.
| |
| }}
| |
| | |
| {{przyklad|2.10||
| |
| Rozważamy język z przykładu 2.5
| |
| | |
| :1. w formule <math>y\times(x+(-3))=x</math> wszystkie wystąpienia zmiennych są wolne. Zmienna <math>\textnormal{x}</math> ma dwa wystąpienia a zmienna <math>\textnormal{y}</math> jedno.
| |
| | |
| :2. w formule <math>\forall_x y\times(x+(-3))=x</math> wszystkie wystąpienia zmiennej <math>\textnormal{y}</math> są wolne, i wszystkie wystąpienia zmiennej <math>\textnormal{x}</math> są związane (nadal są tylko dwa wystąpienia <math>\textnormal{x}</math> ponieważ zgodnie z definicją nie liczymy symbolu <math>\textnormal{x}</math> w <math>\forall_x</math>)
| |
| | |
| :3. w formule <math>\forall_x \exists_y y\times(x+(-3))=x</math> wszystkie wystąpienia zmiennych <math>\textnormal{x}</math> oraz <math>\textnormal{y}</math> są związane
| |
| | |
| :4. w formule <math>x=2 \Rightarrow \exists_x x=2</math> zmienna <math>\textnormal{x}</math> ma jedno wystąpienie wolne (pierwsze) i jedno związane (drugie).
| |
| | |
| :5. w formule <math>\forall_x (x=2 \Rightarrow \exists_x x=2)</math> obydwa wystąpienia zmiennej <math>\textnormal{x}</math> są związane.
| |
| }}
| |
| | |
| {{cwiczenie|2.3||
| |
| | |
| W podanych poniżej formułach podkreśl wszystkie wolne wystąpienia zmiennych.
| |
| | |
| :1. <math>p(z) \Rightarrow \exists_z p(z)</math>
| |
| | |
| :2. <math>\forall_y ((\exists_z q(y,z)) \Rightarrow q(y,z))</math>
| |
| | |
| :3. <math>q(x,y) \Rightarrow \forall_x (q(x,y)\Rightarrow (\forall_y q(x,y)))</math>
| |
| | |
| :4. <math>\forall_x \exists_y q(x,y) \Rightarrow \exists_x \forall_y q(x,y)</math>
| |
| | |
| :5. <math>(\exists_z p(z)) \Rightarrow (\forall_z q(z,z) \vee \exists_x q(z,x))</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">
| |
| | |
| :1. <math>p(z) \Rightarrow \exists_z p(\underline{z})</math>
| |
| | |
| :2. <math>\forall_y ((\exists_z q(y,z)) \Rightarrow q(y,\underline{z}))</math>
| |
| | |
| :3. <math>q(\underline{x},\underline{y}) \Rightarrow \forall_x (q(x,\underline{y})\Rightarrow (\forall_y q(x,y)))</math>
| |
| | |
| :4. <math>\forall_x \exists_y q(x,y) \Rightarrow \exists_x \forall_y q(x,y)</math>
| |
| | |
| :5. <math>(\exists_z p(z)) \Rightarrow (\forall_z q(z,z) \vee \exists_x q(\underline{z},x))</math>
| |
| </div></div>
| |
| | |
| {{definicja|2.11||
| |
| Formułę <math>{\phi}</math> nazywamy domkniętą jeśli żadna zmienna nie ma
| |
| wolnych wystąpień w <math>{\phi}</math>.
| |
| }}
| |
| {{cwiczenie|2.4||
| |
| | |
| Które z formuł z ćwiczenia 2.3 są domknięte?
| |
| }}
| |
| '''Hint 1.'''
| |
| | |
| <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">
| |
| : Jedynie formuła <math>\forall_x \exists_y q(x,y) \Rightarrow \exists_x \forall_y q(x,y)</math> jest formułą domkniętą.
| |
| </div></div>
| |
| | |
| ===Podstawienia===
| |
| | |
| ==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 <math>\forall</math>
| |
| oraz jego interakcji z implikacją. Przypomnijmy, że kwantyfikator
| |
| <math>\exists</math> 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) <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>
| |
| | |
| ::(c) <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi</math>
| |
| | |
| :2. (Aksjomaty dotyczące kwantyfikatora)
| |
| | |
| ::(a) Dla dowolnej formuły <math>{\phi}</math> oraz termu <math>\textnormal{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>
| |
| | |
| ::(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>
| |
| }}
| |
| 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 Modus Ponens <u>'''Modus Ponens (Wykład2)'''</u>.
| |
| | |
| {{definicja|3.2||
| |
| Twierdzeniem rachunku predykatów nazywamy dowolną formułę którą da się dowieść z aksjomatów rachunku predykatów.
| |
| }}
| |
| {{przyklad|3.3||
| |
| | | |
| np. <math>p(t) \Rightarrow \exists_x p(x)</math>.
| | zbiór <math>S</math> ma element największy, o ile <math>S</math> jest niepusty |
| }}
| |
| | |
| ==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 <u>'''matryca boolowska(Wykład2)'''</u>. 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.
| |
| | |
| {{przyklad|4.1||
| |
| | |
| Rozważmy następujące zdanie
| |
| | |
| <center><math>
| |
| | |
| \forall_x \exists_y x \prec y
| |
| </math></center> | |
| | |
| | |
| '''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.
| |
| | |
| '''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.
| |
| | |
| '''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>).
| |
| | |
| }}
| |
| | |
| 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 <math>N, Z, N</math>)
| |
| oraz jak interpretujemy symbole funkcyjne i predykatywne (w naszym
| |
| przykładzie występował jedynie symbol predykatywny <math>\prec</math> 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 <math>M=(D,I)</math>, gdzie:
| |
| | |
| :1. <math>D</math> - jest niepustym zbiorem (dziedziną).
| |
| | |
| :2. <math>\textnormal{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)
| |
| | |
| ::(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ę)
| |
| | |
| ::(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)
| |
| }}
| |
| {{definicja|4.3||
| |
| | |
| Mówimy, że model <math>M</math> jest ''odpowiedni'' dla formuły <math>{\phi}</math> jeśli są
| |
| w nim zdefiniowane interpretacje wszystkich symboli stałych funkcji oraz predykatów występujących w formule <math>{\phi}</math>.
| |
| }}
| |
| Zanim ustalimy co to znaczy że formuła jest prawdziwa w modelu zdefiniujemy tzw. wartościowanie zmiennych
| |
| | |
| {{definicja|4.4||
| |
| | |
| 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.
| |
| | |
| {{definicja|4.5 [Wartościowanie termów]||
| |
| | |
| Przy ustalonym modelu <math>M=(D,I)</math> wartościowanie zmiennych <math>\sigma</math>
| |
| 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>
| |
| | |
| :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)
| |
| | |
| :3. jeśli term <math>\textnormal{t}</math> jest postaci <math>f(t_0,..,t_n)</math>, to
| |
| | |
| <center><math>
| |
| | |
| \hat{\sigma}(f(t_0,..,t_n))= I(f)(\hat{\sigma}(t_0),..,\hat{\sigma}(t_n))
| |
| </math></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.
| |
| }}
| |
| | |
| {{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
| |
| 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
| |
| | |
| :1. term <math>{x+y}</math> będzie wartościowany na '''5'''
| |
| | |
| :2. term <math>s(x)</math> będzie wartościowany na '''3'''
| |
| | |
| :3. term <math>o</math> będzie wartościowany na '''0''' (zgodnie z interpretacją stałych)
| |
| | |
| :4 term <math>s(o) \times s(z)</math> będzie wartościowany na '''6'''
| |
| }}
| |
| | | |
| {{definicja|4.7 [Waluacja formuł]||
| | zbiór <math>S</math> ma element najmniejszy, o ile <math>S</math> jest niepusty |
| | | </quiz> |
| 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ą.
| |
| | |
| :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 '''??''')
| |
| | |
| :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 '''??''')
| |
| | |
| :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>.
| |
| | |
| :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>.
| |
| }}
| |
| 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.
| |
| | |
| {{przyklad|4.8||
| |
| | |
| Możemy teraz powiedzieć, że formuła
| |
| | |
| <center><math>
| |
| | |
| \forall_y (x<y \vee x=y)
| |
| </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).
| |
| }}
| |
| | |
| 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ć
| |
| | |
| <center><math>
| |
| | |
| \forall_y (x<y+x \vee y=o).
| |
| </math></center>
| |
| | |
| {{definicja|4.9||
| |
| | |
| Formuła <math>{\phi}</math> jest prawdziwa w modelu <math>M</math> jeśli jest prawdziwa w tym modelu przy każdej ocenie zmiennych. Mówimy wtedy, że model <math>M</math> jest '''modelem formuły''' <math>{\phi}</math>.
| |
| }}
| |
| Ciekawe, że istnieją również formuły które są prawdziwe we wszystkich modelach. Rozważmy formułę
| |
| | |
| <center><math>
| |
| | |
| (\forall_x p(x)) \Rightarrow (\exists_x p(x)).
| |
| </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
| |
| 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.
| |
| | |
| {{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 <u>'''Kurt Godel'''</u>.
| |
| | |
| {{twierdzenie|4.11 [Kurt Godel]||
| |
| | |
| Formuła rachunku predykatów jest tautologią rachunku predykatów wtedy i tylko wtedy gdy jest twierdzeniem rachunku predykatów.
| |
| }}
| |
| | |
| Dowód powyższego twierdzenia jest przedstawiony na wykładzie <u>'''Logika dla informatyków.'''</u>
| |
| 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||
| |
| | |
| 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)
| |
| | |
| :1. <math>\textnormal{x}</math> jest równe <math>\textnormal{y}</math>
| |
| | |
| :2. <math>\textnormal{x}</math> jest zerem
| |
| | |
| :3. <math>\textnormal{x}</math> jest jedynką
| |
| | |
| :4. <math>\textnormal{x}</math> jest liczbą pierwszą
| |
| | |
| :5. <math>\textnormal{x}</math> jest kwadratem pewnej liczby pierwszej
| |
| | |
| :6. <math>\textnormal{x}</math> jest iloczynem dwóch różnych liczb pierwszych
| |
| | |
| :7. <math>\textnormal{x}</math> jest iloczynem dwóch liczb pierwszych
| |
| | |
| :8. <math>\textnormal{x}</math> 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 <math>\textnormal{x}</math> i <math>\textnormal{y}</math> są względnie pierwsze
| |
| }}
| |
| | |
| <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. wstarczy aby się dzieliły nawzajem
| |
| | |
| :2. każda liczba dzieli zero
| |
| | |
| :3. jedynka dzieli wszystkie liczby
| |
| | |
| :4. jest podzielna tylko przez siebie i przez jeden (uwaga, '''1''' nie jest pierwsza)
| |
| | |
| :5. ma dokładnie '''3''' różne dzielniki
| |
| | |
| :6. ma dokładnie '''4''' różne dzielniki
| |
| | |
| :7. jest kwadratem lub iloczynem dwóch różnych liczb pierwszych
| |
| | |
| :8. każde dwa dzielniki różne od '''1''' mają wspólny dzielnik różny od '''1'''
| |
| | |
| :9. każda liczba która dzieli obie liczby dzieli też ich największy wspólny dzielnik
| |
| | |
| :10. każda liczba która jest podzielna przez obie liczby jest też podzielna przez ich najmniejszą wspólną wielokrotność
| |
| | |
| :11. ich największym wspólnym dzielnikiem jest '''1'''
| |
| </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">
| |
| | |
| : Dla każdej z poniższych formuł w nawiasie zapisujemy skórty których będziemy używać dla tych formuł.
| |
| | |
| :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>
| |
| </div></div>
| |
| | |
| {{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)
| |
| | |
| :1. <math>\textnormal{x}</math> jest równe <math>\textnormal{y}</math>
| |
| | |
| :2. <math>\textnormal{x}</math> jest nadzbiorem <math>\textnormal{y}</math>
| |
| | |
| :3. <math>\textnormal{x}</math> jest punktem
| |
| | |
| :4. <math>\textnormal{x}</math> jest odcinkiem
| |
| | |
| :5. <math>\textnormal{x}</math> jest okręgiem
| |
| | |
| :6. <math>\textnormal{x}</math> jest równoległe do <math>\textnormal{y}</math>
| |
| | |
| :7. <math>\textnormal{x}</math> i <math>\textnormal{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
| |
| | |
| :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
| |
| | |
| :10. okręgi <math>\textnormal{x}</math> i <math>\textnormal{y}</math> są do siebie zewnętrzenie styczne
| |
| | |
| :11. punkt <math>\textnormal{x}</math> jest końcem odcinka <math>\textnormal{y}</math>
| |
| | |
| :12. odcinek <math>\textnormal{x}</math> jest styczny do okręgu <math>\textnormal{y}</math>
| |
| | |
| :13. okręgi <math>\textnormal{x}</math> i <math>\textnormal{y}</math> mają taką samą średnicę
| |
| | |
| :14. okrąg <math>\textnormal{x}</math> ma średnicę mniejszą niż okrąg <math>\textnormal{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">
| |
| | |
| :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
| |
| | |
| :2. każdy punkt wspólny jakiegoś obiektu z podzbiorem jest też punktem wspólnym z nadzbiorem
| |
| | |
| :3. punkt ma z każdym obiektem co najwyżej jeden punkt wspólny (okrąg i odcinek może mieć więcej)
| |
| | |
| :4. tylko punkt i odcinek mogą mieć istotne nadzbiory, punkty możemy wykluczyć korzystając z formuły w poprzednim punkcie
| |
| | |
| :5. jeśli coś nie jest punktem ani odcinkiem to jest okręgiem
| |
| | |
| :6. odcinki są równoległe jeśli dowolne ich przedłużenia nie przecinają się
| |
| | |
| :7. każde dwa ich wspólne punkty muszą być równe
| |
| | |
| :8. okręgi są styczne jeśli mają dokładnie jeden punkt wspólny
| |
| | |
| :9. jeśli okrąg <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>
| |
| | |
| :10. okręgi muszą być styczne i żaden z nich nie może być wewnętrzny
| |
| | |
| :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
| |
| | |
| :12. każde przedłużenie odcinka <math>\textnormal{x}</math> dokładnie jeden punkt wpólny z <math>\textnormal{y}</math>
| |
| | |
| :13. istnieją dwa równoległe odcinki styczne do obu okręgów które nie mają punktów wspólnych
| |
| | |
| :14. istnieję dwa równoległe odcinki które nie mają punktów wspólnych z których pierwszy jest styczny do obu okręgów a drugi jest styczny do <math>\textnormal{x}</math> i przecina okrąg <math>\textnormal{y}</math> w dwóch różnych punktach
| |
| | |
| :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>
| |
| | |
| :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>
| |
| | |
| :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>
| |
| | |
| :18. odcinki mają być równej długości, prostopadłe, różne i mają się odpowiednio stykać końcami (uwaga na kolejność)
| |
| </div></div>
| |
| | |
| {{cwiczenie|4.3||
| |
| | |
| Napisz formuły które mówią:
| |
| | |
| :* każdy odcinek ma dokładnie dwa końce
| |
| | |
| :* dla każdego okręgu wszystkie jego średnice przecinają się w dokładnie jednym punkcie
| |
| | |
| :* dla dowolnego odcinka istnieje dłuższy odcinek, który go zawiera
| |
| | |
| :* dla dowolnych trzech punktów niewspółliniowych istnieje okrąg który przechodzi przez wszystkie trzy punkty
| |
| | |
| :* istnieją dwa okręgi, które przecinają się w dokładnie '''5''' punktach.
| |
| | |
| ; Solution.
| |
| }}
| |
| | |
| {{cwiczenie|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. <math>\forall_x \forall_y p(x,y) \Rightarrow p(y,x)</math>
| |
| | |
| :2. <math>(\forall_x \exists_y p(x,y)) \Rightarrow \exists_y \forall_x p(x,y)</math>
| |
| | |
| :3. <math>(\forall_x (p(x)\vee q(x))) \Rightarrow (\forall_x(p(x)) \vee \forall_x q(x))</math>
| |
| | |
| :4. <math>\forall_y [(\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(z)]</math>
| |
| | |
| :5. <math>\forall_x \forall_y(p(x,y) \Rightarrow \exists_z (p(x,z)\wedge p(z,y))</math>
| |
| | |
| :6. ...
| |
| }}
| |
| | |
| <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">
| |
| | |
| Poniższe przykłady to tylko jedne z wielu możliwych rozwiązań.
| |
| | |
| :1.
| |
| | |
| ::(a) Formuła jest prawdziwa w zbiorze trójkątów, jeśli <math>\textnormal{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>.
| |
| | |
| :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.
| |
| | |
| ::(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>
| |
| | |
| :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.
| |
| | |
| ::(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.
| |
| | |
| :4.
| |
| ::<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.
| |
| | |
| ::(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>.
| |
| | |
| :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>).
| |
| | |
| ::(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
| |
| p(z,y))</math> bo pomiędzy liczbami '''0''' a '''1''' nie ma żadnej liczby naturalnej.
| |
| | |
| </div></div>
| |
| | |
| {{cwiczenie|4.5||
| |
| | |
| Udowodnij, że w dowolnym ustalonym modelu <math>M</math> prawdziwe są następujące formuły
| |
| | |
| :1. <math>\forall_x p(x) \Rightarrow (p(c))</math>
| |
| | |
| :2. <math>p(c) \Rightarrow \forall_x p(c)</math>
| |
| | |
| :3. <math>\forall_x(p(x) \Rightarrow q(x)) \Rightarrow ((\forall_x p(x))\Rightarrow(\forall_x q x)))</math>
| |
| | |
| :4. <math>\exists_x p(x) \Leftrightarrow \neg \forall_x \neg p(x)</math>
| |
| | |
| :5. <math>\neg \forall_x p(x) \Leftrightarrow \exists_x \neg p(x)</math>
| |
| | |
| :6. <math>\forall_x r(x, f(x)) \Rightarrow \forall_x \exists_y r(x,y)</math>
| |
| | |
| ; Solution.
| |
| }}
| |
| | |
| {{cwiczenie|4.6||
| |
| | |
| Rozważmy formułę
| |
| | |
| <center><math>
| |
| | |
| \forall_x (\neg g(x,x) \Leftrightarrow g(b,x))
| |
| </math></center>
| |
| | |
| (golibroda <math>\textnormal{b}</math> goli wszystkich tych i tylko tych, którzy nie golą się sami).
| |
| Udowodnij, że nie istnieje model dla powyższej formuły.
| |
| }}
| |
| <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">
| |
| | |
| :(Idea dowodu: kto w goli golibrodę?) Dla dowodu nie wprost przypuśćmy, że istnieje model <math>M</math> w którym ta formuła jest prawdziwa. Skoro tak to dla dowolnego wartościowania zmiennej <math>\textnormal{x}</math> prawdziwa jest formuła
| |
| | |
| <center><math>
| |
| | |
| (\neg g(x,x) \Leftrightarrow g(b,x)).
| |
| </math></center>
| |
| | |
| :W szczególności dla wartościowania które <math>\textnormal{x}</math> przypisuje ten sam obiekt co stałej <math>\textnormal{b}</math> powyższa formuła ma tę samą wartość co
| |
| | |
| <center><math>
| |
| | |
| (\neg g(b,b) \Leftrightarrow g(b,b)).
| |
| </math></center>
| |
| | |
| :a taka formuła nigdy nie jest spełniona. Wobec tego formuła z zadania jest nieprawdziwa w <math>M</math>.
| |
| </div></div>
| |
