|
|
| (Nie pokazano 51 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>
| | |
| | | zbiór <math>S</math> ma element największy, o ile <math>S</math> jest niepusty |
| :4. <math>\times^2(y,+^2(x,-^1(2)))</math>
| | |
| | | zbiór <math>S</math> ma element najmniejszy, o ile <math>S</math> jest niepusty |
| 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
| | </quiz> |
| | |
| :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
| |
| | |
| # <math>\forall_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \forall_x \phi \Rightarrow
| |
| \psi</math>
| |
| | |
| # <math>\exists_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \exists_x \phi \wedge \psi</math>
| |
| | |
| i czytamy
| |
| | |
| # "dla każdego <math>x</math> które spełnia <math>\phi</math> spełnione jest
| |
| <math>\psi</math>"
| |
| | |
| # istnieje <math>x</math> spełniające <math>\phi</math> które spełnia <math>\psi</math>
| |
| | |
| Zgodnie z tą konwencją formułę [[##eq:wprowadzenieFLPrzykład|Uzupelnic eq:wprowadzenieFLPrzykład|]],
| |
| możemy zapisać następująco
| |
| | |
| <center><math>
| |
| | |
| \forall_{n:p(n)} q(n) \vee r(n).
| |
| </math></center>
| |
| | |
| Podobnie formułę [[##eq:wprowadzenieFLPrzykładE|Uzupelnic eq:wprowadzenieFLPrzykładE|]] zapiszemy jako
| |
| | |
| <center><math>
| |
| | |
| \exists_{n:p(n)}\neg q(n)
| |
| </math></center>
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| Wyeliminuj wszystkie skróty z napisu
| |
| | |
| <center><math>
| |
| | |
| \exists_{x:\phi} \psi
| |
| </math></center> | |
| | |
| {hint}{1}
| |
| ; Hint .
| |
| : eliminacja kwantyfikatora ograniczonego:
| |
| | |
| <center><math>
| |
| | |
| \exists_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv}
| |
| \exists_x \phi \wedge \psi
| |
| </math></center>
| |
| | |
| {hint}{1}
| |
| ; Hint .
| |
| : eliminacja kwantyfikatora egzystencjalnego
| |
| | |
| <center><math>
| |
| | |
| \exists_x \phi \wedge \psi \stackrel{\textrm{def}}{\equiv}
| |
| \neg \forall_x \neg(\phi \wedge \psi)
| |
| </math></center>
| |
| | |
| ; Solution.
| |
| : 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>
| |
| | |
| }}
| |
| | |
| ===Zmienne wolne i związane===
| |
| | |
| Jeśli <math>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>x</math> i nie jest poprzedzony
| |
| bezpośrednio kwantyfikatorem, nazywamy wystąpieniem zmiennej <math>x</math>.
| |
| Wystąpienia dzielimy na "wolne" i "związanie".
| |
| Wystąpienie jest związane jeśli znajduje się ,,pod działaniem"
| |
| jakiegoś kwantyfikatora.
| |
| | |
| Rodzaj wystąpienia zmiennej w formule określamy zgodnie z
| |
| poniższymi regułami:
| |
| | |
| # Jeśli <math>\gamma</math> jest formułą atomową to wszystkie wystąpienia zmiennych w napisie <math>\gamma</math> są
| |
| "'wolne"'.
| |
| | |
| # 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>.
| |
| | |
| # Jeśli formuła jest postaci <math>\forall_x \phi</math> to
| |
| wszystkie wystąpienia zmiennej <math>x</math> w <math>\forall_x \phi</math> są
| |
| "'związane"'.
| |
| | |
| ład
| |
| Rozważamy język z przykładu [[##ex:predykaty|Uzupelnic ex:predykaty|]]
| |
| | |
| # w formule
| |
| <math>y\times(x+(-3))=x</math> wszystkie wystąpienia zmiennych są wolne.
| |
| Zmienna <math>x</math> ma dwa wystąpienia a zmienna <math>y</math> jedno.
| |
| | |
| # w formule <math>\forall_x y\times(x+(-3))=x</math> wszystkie wystąpienia zmiennej <math>y</math> są
| |
| wolne, i wszystkie wystąpienia zmiennej <math>x</math> są związane
| |
| (nadal są tylko dwa wystąpienia <math>x</math> ponieważ zgodnie z
| |
| definicją nie liczymy symbolu <math>x</math> w <math>\forall_x</math>)
| |
| | |
| # w formule <math>\forall_x \exists_y y\times(x+(-3))=x</math>
| |
| wszystkie wystąpienia zmiennych <math>x</math> oraz <math>y</math> są związane
| |
| | |
| # w formule <math>x=2 \Rightarrow \exists_x x=2</math> zmienna <math>x</math> ma
| |
| jedno wystąpienie wolne (pierwsze) i jedno związane
| |
| (drugie).
| |
| | |
| # w formule <math>\forall_x (x=2 \Rightarrow \exists_x x=2)</math> obydwa wystąpienia zmiennej <math>x</math>
| |
| są związane.
| |
| | |
| ład
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| W podanych poniżej formułach podkreśl wszystkie wolne
| |
| wystąpienia zmiennych.
| |
| | |
| # <math>p(z) \Rightarrow \exists_z p(z)</math>
| |
| | |
| # <math>\forall_y ((\exists_z q(y,z)) \Rightarrow q(y,z))</math>
| |
| | |
| # <math>q(x,y) \Rightarrow \forall_x (q(x,y)\Rightarrow (\forall_y q(x,y)))</math>
| |
| | |
| # <math>\forall_x \exists_y q(x,y) \Rightarrow \exists_x \forall_y q(x,y)</math>
| |
| | |
| # <math>(\exists_z p(z)) \Rightarrow (\forall_z q(z,z) \vee \exists_x q(z,x))</math>
| |
| | |
| ; Solution.
| |
| :
| |
| | |
| :# <math>p(z) \Rightarrow \exists_z p(\underline{z})</math>
| |
| | |
| :# <math>\forall_y ((\exists_z q(y,z)) \Rightarrow q(y,\underline{z}))</math>
| |
| | |
| :# <math>q(\underline{x},\underline{y}) \Rightarrow \forall_x (q(x,\underline{y})\Rightarrow (\forall_y q(x,y)))</math>
| |
| | |
| :# <math>\forall_x \exists_y q(x,y) \Rightarrow \exists_x \forall_y q(x,y)</math>
| |
| | |
| :# <math>(\exists_z p(z)) \Rightarrow (\forall_z q(z,z) \vee \exists_x q(\underline{z},x))</math>
| |
| | |
| }}
| |
| | |
| Formułę <math>\phi</math> nazywamy "domkniętą" jeśli żadna zmienna nie ma
| |
| wolnych wystąpień w <math>\phi</math>.
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| Które z formuł z ćwiczenia [[##ex:wolneWystapienia|Uzupelnic ex:wolneWystapienia|]] są
| |
| domknięte?
| |
| {hint}{1}
| |
| ; Hint .
| |
| :
| |
| ; Solution.
| |
| : Jedynie formuła <math>\forall_x \exists_y q(x,y) \Rightarrow \exists_x \forall_y
| |
| q(x,y)</math> jest formułą domkniętą.
| |
| }}
| |
| | |
| ===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.
| |
| | |
| Schematy aksjomatów rachunku predykatów
| |
| | |
| # (Aksjomaty logiki zdaniowej) Każda formuła pasująca do któregokolwiek z poniższych
| |
| schematów jest tautologią
| |
| | |
| ## <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
| |
| | |
| ## <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
| |
| (\phi \Rightarrow \nu) \right)</math>
| |
| | |
| ## <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
| |
| \psi) \Rightarrow \phi</math>
| |
| | |
| # (Aksjomaty dotyczące kwantyfikatora)
| |
| | |
| ## 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)
| |
| | |
| ## Dla dowolnej formuły <math>\phi</math> oraz zmiennej <math>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>
| |
| | |
| ## 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
| |
| Modus Ponens(Wykład2).
| |
| | |
| Twierdzeniem rachunku predykatów nazywamy dowolną formułę którą
| |
| da się dowieść z aksjomatów rachunku predykatów.
| |
| | |
| ład
| |
| np. <math>p(t) \Rightarrow \exists_x p(x)</math>.
| |
| ład
| |
| | |
| ==Modele==
| |
| | |
| Dotychczas wprowadziliśmy rachunek predykatów aksjomatycznie. Zaletą
| |
| takiego definiowania jest niewielka ilość potrzebnych pojęć. Z
| |
| drugiej strony jednak dowody z aksjomatów są żmudne i nie sprzyjają
| |
| budowaniu intuicji. W przypadku rachunku zdań widzieliśmy, że ten
| |
| sam zbiór formuł można równoważnie zdefiniować za pomocą matrycy
| |
| Boolowskiej matryca boolowska(Wykład2). Niestety w przypadku rachunku
| |
| predykatów nie istnieje taka skończona struktura, która pozwalałaby
| |
| nam stwierdzać czy formuła jest twierdzeniem. Zobaczymy jednak, że
| |
| pewne struktury warto rozważać. Mówiąc o modelach będziemy musieli
| |
| użyć naiwnej teorii zbiorów opisanej w pierwszym rozdziale.
| |
| Decydujemy się na to nadużycie w celu zdobycia dobrych intuicji i
| |
| sprawności w posługiwaniu się kwantyfikatorami.
| |
| | |
| ład
| |
| 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>x</math> jest
| |
| silnie mniejsza od liczby <math>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>x</math> jest
| |
| silnie mniejsza od liczby <math>y</math>. Wtedy zdanie to powinniśmy uznać
| |
| prawdziwe. Istotnie, dla każdej liczby całkowitej <math>x</math> możemy
| |
| dobrać liczbę <math>y</math> (na przykład równą <math>x-1</math>) która jest od niej
| |
| silnie mniejsza.
| |
| | |
| ; Sytuacja 2
| |
| : 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>x</math> jest
| |
| równa liczbie <math>y</math>. Wtedy zdanie to powinniśmy uznać
| |
| prawdziwe (do każdej liczby <math>x</math> możemy dobrać liczbę <math>y</math> tak aby była równa <math>x</math>).
| |
| | |
| ład
| |
| | |
| 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.
| |
| | |
| [Model]
| |
| | |
| Modelem języka rachunku predykatów nazywamy <math>M=(D,I)</math>, gdzie:
| |
| | |
| # <math>D</math> - jest niepustym zbiorem (dziedziną).
| |
| | |
| # <math>I</math> - jest interpretacją symboli języka taką, że:
| |
| | |
| ## dla symboli stałych: <math>I(c)\in D</math> (symbole stałych
| |
| są interpretowane jako elementy dziedziny)
| |
| | |
| ## dla symboli funkcyjnych: <math>I(f):D^k\rightarrow D</math>, gdzie k jest ilością
| |
| argumentów f (symbole funkcyjne są interpretowane jako
| |
| funkcje z potęgi dziedziny w dziedzinę)
| |
| | |
| ## dla symboli predykatów: <math>I(p):D^k\rightarrow {0,1}</math>, gdzie <math>k</math> jest ilością
| |
| argumentów <math>p</math> (symbole predykatywne są interpretowane
| |
| jako funkcje przekształcające ciągi elementów z
| |
| dziedziny w prawdę lub fałsz)
| |
| | |
| 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
| |
| 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.
| |
| [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
| |
| | |
| # jeśli term <math>t</math> jest zmienną, <math>\hat{\sigma}(t) =
| |
| \sigma(t)</math>
| |
| | |
| # jeśli term <math>t</math> jest stałą, to <math>\hat{\sigma}(t)=I(t)</math> (stałe
| |
| wartościujemy zgodnie z interpretacją w modelu)
| |
| | |
| # jeśli term <math>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>f</math> na wartościach poddtermów. Funkcję
| |
| wartościującą termy będziemy często oznaczali tym samym
| |
| symbolem co wartościowanie zmiennych.
| |
| | |
| ład
| |
| | |
| 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>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
| |
| | |
| # term <math>x+y</math> będzie wartościowany na 5
| |
| | |
| # term <math>s(x)</math> będzie wartościowany na 3
| |
| | |
| # term <math>o</math> będzie wartościowany na 0 (zgodnie z
| |
| interpretacją stałych)
| |
| | |
| # term <math>s(o) \times s(z)</math> będzie wartościowany na 6
| |
| | |
| ład
| |
| | |
| [Waluacja formuł]
| |
| Zdefiniujemy teraz prawdziwość formuł w ustalonym modelu
| |
| <math>M=(D,I)</math> przy ustalonym wartościowaniu zmiennych <math>\sigma</math>.
| |
| | |
| # 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>p</math> (czyli <math>I(p)</math>)
| |
| na elementach dziedziny odpowiadających termom <math>t_0,
| |
| \dots, t_n</math> jest prawdą.
| |
| | |
| # Jeśli formuła jest postaci <math>A\Rightarrow B</math>, to
| |
| jest ona prawdziwa wtedy i tylko wtedy, gdy formuła <math>A</math>
| |
| jest wartościowana na fałsz lub formuła <math>B</math> jest
| |
| wartościowana na prawdę (zgodnie z tabelą dla implikacji
| |
| [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]])
| |
| | |
| # Jeśli formuła jest postaci <math>\neg A</math> to jest ona
| |
| prawdziwa wtedy i tylko wtedy gdy formuła <math>A</math> jest
| |
| wartościowana na fałsz (zgodnie z tabelą dla negacji
| |
| [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]])
| |
| | |
| # Jeśli formuła jest postaci <math>\forall_x \; A</math>, to
| |
| jest ona prawdziwa jeśli prawdziwe jest <math>A</math> i dla
| |
| każdego wartościowania zmiennych różniącego się od
| |
| <math>\sigma</math> co najwyżej interpretacją symbolu <math>x</math> prawdziwe
| |
| jest <math>A</math>.
| |
| | |
| # 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>x</math> taka, że przy tej ocenie prawdziwe
| |
| jest <math>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>x</math> w
| |
| formule <math>A</math> prawdziwa jest formuła <math>A</math> (uwaga! podstawiamy jedynie w
| |
| miejsca wolnych wystąpień <math>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>x</math> w formule <math>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 [[##ex:existsInterpretacja|Uzupelnic ex:existsInterpretacja|]] pokażemy, że zdefiniowana
| |
| powyżej waluacja formuł z kwantyfikatorem egzystencjalnym jest
| |
| zgodna z waluacją zdefiniowanego wcześniej skrótu.
| |
| | |
| ład
| |
| 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 [[##ex:arytmetykaModel|Uzupelnic ex:arytmetykaModel|]] 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>y</math> na 3
| |
| formuła <math>x<y \vee x=y</math> nie będzie prawdziwa).
| |
| ład
| |
| | |
| Istnieją jednak formuły które są prawdziwe w modelu z przykładu
| |
| [[##ex:arytmetykaModel|Uzupelnic ex:arytmetykaModel|]] niezależnie od oceny zmiennych. Przykładem
| |
| może być
| |
| | |
| <center><math>
| |
| | |
| \forall_y (x<y+x \vee y=o).
| |
| </math></center>
| |
| | |
| 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>p</math>). Jeśli w tym modelu nie jest prawdziwa formuła
| |
| <math>(\forall_x p(x))</math> to cała implikacja [[##eq:FOLtaut|Uzupelnic eq:FOLtaut|]] jest
| |
| prawdziwa a więc wszystkie te modele są modelami formuły
| |
| [[##eq:FOLtaut|Uzupelnic eq:FOLtaut|]]. 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>x</math> uczyni predykat oznaczony
| |
| przez <math>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>x</math> czyni predykat
| |
| odpowiadający <math>p</math> prawdziwym. Ponieważ dziedzina modelu <math>M</math> zgodnie
| |
| z definicją [[##defn:model|Uzupelnic defn:model|]] 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>x</math>, to
| |
| rzeczywiście istnieje taki element dziedziny, który podstawiony w
| |
| miejsce <math>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
| |
| [[##eq:FOLtaut|Uzupelnic eq:FOLtaut|]] jest prawdziwa w <math>M</math>. Pokazaliśmy więc, że formuła
| |
| [[##eq:FOLtaut|Uzupelnic eq:FOLtaut|]] jest prawdziwa w każdym modelu.
| |
| | |
| Formułę rachunku predykatów nazywamy "tautologią" rachunku
| |
| predykatów jeśli jest prawdziwa w każdym odpowiednim dla niej modelu .
| |
| | |
| Podobnie jak klasycznym rachunku zdań, w rachunku predykatów również
| |
| tautologie okazują się tym samym co twierdzenia. Mówi o tym następujące
| |
| klasyczne twierdzenie udowodnione przez Kurt G{o}del.
| |
| | |
| {{twierdzenie|[Uzupelnij]||
| |
| [Kurt G{o}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.
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| Rozważmy model <math>M</math>, którego dziedziną będą liczby naturalne, oraz w
| |
| którym jest jeden predykat binarny oznaczony symbolem <math>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)
| |
| | |
| # <math>x</math> jest równe <math>y</math>
| |
| | |
| # <math>x</math> jest zerem
| |
| | |
| # <math>x</math> jest jedynką
| |
| | |
| # <math>x</math> jest liczbą pierwszą
| |
| | |
| # <math>x</math> jest kwadratem pewnej liczby pierwszej
| |
| | |
| # <math>x</math> jest iloczynem dwóch różnych liczb pierwszych
| |
| | |
| # <math>x</math> jest iloczynem dwóch liczb pierwszych
| |
| | |
| # <math>x</math> jest potęgą liczby pierwszej
| |
| | |
| # dla każdych dwóch liczb istnieje ich największy wspólny dzielnik
| |
| | |
| # dla każdych dwóch liczb istnieje ich najmniejsza wspólna
| |
| wielokrotność
| |
| | |
| # liczby <math>x</math> i <math>y</math> są względnie pierwsze
| |
| | |
| {hint}{1}
| |
| ; Hint .
| |
| :
| |
| | |
| :# wstarczy aby się dzieliły nawzajem
| |
| | |
| :# każda liczba dzieli zero
| |
| | |
| :# jedynka dzieli wszystkie liczby
| |
| | |
| :# jest podzielna tylko przez siebie i przez jeden (uwaga, 1
| |
| nie jest pierwsza)
| |
| | |
| :# ma dokładnie 3 różne dzielniki
| |
| | |
| :# ma dokładnie 4 różne dzielniki
| |
| | |
| :# jest kwadratem lub iloczynem dwóch różnych liczb pierwszych
| |
| | |
| :# każde dwa dzielniki różne od 1 mają wspólny dzielnik różny od 1
| |
| | |
| :# każda liczba która dzieli obie liczby dzieli też ich
| |
| największy wspólny dzielnik
| |
| | |
| :# każda liczba która jest podzielna przez obie liczby jest
| |
| też podzielna przez ich najmniejszą wspólną wielokrotność
| |
| | |
| :# ich największym wspólnym dzielnikiem jest 1
| |
| | |
| ; Solution.
| |
| : Dla każdej z poniższych formuł w nawiasie zapisujemy skórty
| |
| których będziemy używać dla tych formuł.
| |
| | |
| :# <math>\forall_z (p(z,x) \Leftrightarrow p(z,y)</math> (skrót <math>x=y</math>)
| |
| | |
| :# <math>\forall_z p(z,x)</math> (skrót <math>x=1</math>)
| |
| | |
| :# <math>\forall_z p(x,z)</math> (skrót <math>x=0</math>)
| |
| | |
| :# <math>(\neg x=1) \wedge \forall_z [p(z,x) \Rightarrow (z=1 \vee z=x)]</math>
| |
| (skrót <math>Prim(x)</math>).
| |
| | |
| :# <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>).
| |
| | |
| :# <math>x</math> jest iloczynem dwóch różnych liczb pierwszych (skrót
| |
| <math>pq(x)</math>.
| |
| | |
| :# <math>pKq(x) \vee pq(x)</math>
| |
| | |
| :# <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>
| |
| | |
| :# <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>
| |
| | |
| :# <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>
| |
| | |
| :# <math>\forall_z ((p(z,x) \wedge p(z,y))\Rightarrow (z=1))</math>
| |
| | |
| }}
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| 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>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)
| |
| | |
| # <math>x</math> jest równe <math>y</math>
| |
| | |
| # <math>x</math> jest nadzbiorem <math>y</math>
| |
| | |
| # <math>x</math> jest punktem
| |
| | |
| # <math>x</math> jest odcinkiem
| |
| | |
| # <math>x</math> jest okręgiem
| |
| | |
| # <math>x</math> jest równoległe do <math>y</math>
| |
| | |
| # <math>x</math> i <math>y</math> mają dokładenie jeden punkt wspólny
| |
| | |
| # okręgi <math>x</math> i <math>y</math> są do siebie styczne
| |
| | |
| # okręgi <math>x</math> i <math>y</math> są do siebie wewnętrznie styczne i okrąg <math>x</math> jest okręgiem wewnętrznym
| |
| | |
| # okręgi <math>x</math> i <math>y</math> są do siebie zewnętrzenie styczne
| |
| | |
| # punkt <math>x</math> jest końcem odcinka <math>y</math>
| |
| | |
| # odcinek <math>x</math> jest styczny do okręgu <math>y</math>
| |
| | |
| # okręgi <math>x</math> i <math>y</math> mają taką samą średnicę
| |
| | |
| # okrąg <math>x</math> ma średnicę mniejszą niż okrąg <math>y</math>
| |
| | |
| # odcinek <math>x</math> jest krótszy od odcinka <math>y</math>
| |
| | |
| # odcinek <math>x</math> jest średnicą okręgu <math>y</math>
| |
| | |
| # <math>x</math> jest prostopadłe do <math>y</math>
| |
| | |
| # odcinki <math>x,y,z,w</math> tworzą kwadrat
| |
| | |
| {hint}{1}
| |
| ; Hint .
| |
| :
| |
| | |
| :# jeśli <math>x</math> jest różne od <math>y</math> to istnieje punkt który należy
| |
| do jednego obiektu i nie należy do drugiego
| |
| | |
| :# każdy punkt wspólny jakiegoś obiektu z podzbiorem jest też
| |
| punktem wspólnym z nadzbiorem
| |
| | |
| :# punkt ma z każdym obiektem co najwyżej jeden punkt wspólny
| |
| (okrąg i odcinek może mieć więcej)
| |
| | |
| :# tylko punkt i odcinek mogą mieć istotne nadzbiory, punkty
| |
| możemy wykluczyć korzystając z formuły w poprzednim punkcie
| |
| | |
| :# 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ę
| |
| | |
| :# każde dwa ich wspólne punkty muszą być równe
| |
| | |
| :# okręgi są styczne jeśli mają dokładnie jeden punkt wspólny
| |
| | |
| :# jeśli okrąg <math>x</math> jest wewnętrzny to każdy odcinek, który ma
| |
| przynajmniej jeden punkt wspólny z <math>x</math> da się przedłużyć tak,
| |
| aby przecinał (miał punkt wspólny) z <math>y</math>
| |
| | |
| :# okręgi muszą być styczne i żaden z nich nie może być wewnętrzny
| |
| | |
| :# istnieje okrąg przechodzący przez <math>x</math> taki że każdy okrąg
| |
| styczny do niego w <math>x</math> jeśli jest zewnętrzny to ma dokładnie jeden punkt
| |
| wspólny z <math>y</math> a jeśli jest wewnętrzny to dwa
| |
| | |
| :# każde przedłużenie odcinka <math>x</math> dokładnie jeden punkt
| |
| wpólny z <math>y</math>
| |
| | |
| :# istnieją dwa równoległe odcinki styczne do obu okręgów
| |
| które nie mają punktów wspólnych
| |
| | |
| :# 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>x</math> i przecina okrąg <math>y</math>
| |
| w dwóch różnych punktach
| |
| | |
| :# najmniejszy okrąg którego cięciwą jest <math>x</math> ma mniejszą średnicę niż
| |
| najmniejszy okrąg którego cięciwą jest <math>y</math>
| |
| | |
| :# najmniejszy okrąg którego cięciwą jest <math>x</math> ma taką samą
| |
| średnicę jak <math>y</math> i <math>x</math> jest cięciwą <math>y</math>
| |
| | |
| :# istnieje okrąg, który jest styczny do pewnego przedłużenia
| |
| <math>y</math> taki, że <math>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>y</math>
| |
| | |
| :# odcinki mają być równej długości, prostopadłe, różne i
| |
| mają się odpowiednio stykać końcami (uwaga na kolejność)
| |
| | |
| }}
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| 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|[Uzupelnij]||
| |
| | |
| Dla każdej z poniższych formuł znajdź model w którym jest
| |
| prawdziwa oraz model w którym jest fałszywa
| |
| | |
| # <math>\forall_x \forall_y p(x,y) \Rightarrow p(y,x)</math>
| |
| | |
| # <math>(\forall_x \exists_y p(x,y)) \Rightarrow \exists_y \forall_x p(x,y)</math>
| |
| | |
| # <math>(\forall_x (p(x)\vee q(x))) \Rightarrow (\forall_x(p(x)) \vee \forall_x q(x))</math>
| |
| | |
| # <math>\forall_y [(\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(z)]</math>
| |
| | |
| # <math>\forall_x \forall_y(p(x,y) \Rightarrow \exists_z (p(x,z)\wedge
| |
| p(z,y))</math>
| |
| | |
| # ...
| |
| | |
| ; Solution.
| |
| : Poniższe przykłady to tylko jedne z wielu możliwych rozwiązań.
| |
| | |
| :#
| |
| | |
| :## Formuła jest prawdziwa w zbiorze trójkątów, jeśli <math>p</math> jest interpretowany jako
| |
| podobieństwo trójkątów.
| |
| | |
| :## 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>x</math> jest krótszy od odcinka oznaczonego przez <math>y</math>.
| |
| | |
| :#
| |
| | |
| :## Formuła jest prawdziwa w liczbach naturalnych,
| |
| jeśli <math>p</math> jest interpretowane jako słaba mniejszość (czyli
| |
| <math>p(x,y)</math> jest prawdą jeśli <math>x</math> jest mniejsze lub równe
| |
| <math>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.
| |
| | |
| :## Formuła jest fałszywa w liczbach całkowitych,
| |
| jeśli <math>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>
| |
| | |
| :#
| |
| | |
| :## 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>x</math> jest liczbą
| |
| złożoną, a <math>q(x)</math> jest prawdziwe gdy <math>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.
| |
| | |
| :## 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>x</math> jest liczbą
| |
| parzystą, a <math>q(x)</math> jest prawdziwe gdy <math>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.
| |
| | |
| :#
| |
| <math>(\forall_y [\forall_x (p(x) \Rightarrow q(x)) \wedge q(y)) \Rightarrow p(y)]</math>
| |
| | |
| :## 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>x</math> jest mniejsze od 1000, a <math>p(y)</math>
| |
| jest prawdziwe gdy <math>y</math> jest parzyste.
| |
| | |
| :## Formuła jest fałszywa w zbiorze czworokątów, gdzie
| |
| <math>p(x)</math> jest prawdą jeśli <math>x</math> jest kwadratem, a <math>q(x)</math>
| |
| jest prawdą gdy <math>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>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>y</math>.
| |
| | |
| :#
| |
| | |
| :## Formuła jest prawdziwa w liczbach wymiernych gdzie
| |
| <math>p(x,y)</math> jest prawdziwe wtedy i tylko wtedy gdy <math>x</math> jest
| |
| silnie mniejsze od <math>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>).
| |
| | |
| :## 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>x</math> będziemy wartościować na 0, a
| |
| <math>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.
| |
| | |
| }}
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| Udowodnij, że w dowolnym ustalonym modelu <math>M</math> prawdziwe są
| |
| następujące formuły
| |
| | |
| # <math>\forall_x p(x) \Rightarrow (p(c))</math>
| |
| | |
| # <math>p(c) \Rightarrow \forall_x p(c)</math>
| |
| | |
| # <math>\forall_x(p(x) \Rightarrow q(x)) \Rightarrow ((\forall_x p(x))\Rightarrow(\forall_x q(x)))</math>
| |
| | |
| # <math>\exists_x p(x) \Leftrightarrow \neg \forall_x \neg p(x)</math>
| |
| | |
| # <math>\neg \forall_x p(x) \Leftrightarrow \exists_x \neg p(x)</math>
| |
| | |
| # <math>\forall_x r(x, f(x)) \Rightarrow \forall_x \exists_y r(x,y)</math>
| |
| | |
| ; Solution.
| |
| : }}
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| Rozważmy formułę
| |
| | |
| <center><math>
| |
| | |
| \forall_x (\neg g(x,x) \Leftrightarrow g(b,x))
| |
| </math></center>
| |
| | |
| (golibroda <math>b</math> goli wszystkich tych i tylko tych, którzy nie golą się sami).
| |
| Udowodnij, że nie istnieje model dla powyższej formuły.
| |
| | |
| ; Solution.
| |
| : (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>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>x</math> przypisuje ten sam
| |
| obiekt co stałej <math>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>.
| |
| }}
| |
| | |
| {amsplain}
| |
