Logika i teoria mnogości/Wykład 2: Rachunek zdań: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Matiunreal (dyskusja | edycje)
m Zastępowanie tekstu – „,↵</math>” na „</math>,”
 
(Nie pokazano 31 wersji utworzonych przez 3 użytkowników)
Linia 5: Linia 5:




<center>Jeśli <math>\textnormal{n}</math> jest liczbą pierwszą to <math>\textnormal{n}</math> jest liczbą nieparzystą lub <math>\textnormal{n}</math> jest równe '''2'''.</center>
<center>Jeśli <math>\text{n}</math> jest liczbą pierwszą to <math>\text{n}</math> jest liczbą nieparzystą lub <math>\text{n}</math> jest równe '''2'''.</center>


W powyższym zdaniu spójniki '''jeśli [..] to, lub''' mówią o związkach które zachodzą pomiędzy zdaniami:
W powyższym zdaniu spójniki '''jeśli [..] to, lub''' mówią o związkach które zachodzą pomiędzy zdaniami:


# ''<math>\textnormal{n}</math> jest liczbą pierwszą,''
# ''<math>\text{n}</math> jest liczbą pierwszą,''
# ''<math>\textnormal{n}</math> jest liczbą nieparzystą,''
# ''<math>\text{n}</math> jest liczbą nieparzystą,''
# ''<math>\textnormal{n}</math> jest równe 2.''
# ''<math>\text{n}</math> jest równe 2.''


Oznaczmy powyższe zdania przez <math>p,q,r</math> (w takiej właśnie
Oznaczmy powyższe zdania przez <math>p,q,r</math> (w takiej właśnie
kolejności). Używając symboli, które zwyczajowo odpowiadają
kolejności). Używając symboli, które zwyczajowo odpowiadają
potocznemu rozumieniu spójników '''jeśli [..] to, lub''' oraz powyższych oznaczeń otrzymamy formułę
potocznemu rozumieniu spójników '''jeśli [..] to, lub''' oraz powyższych oznaczeń, otrzymamy formułę




<center><math>
<center><math>


p \Rightarrow (q \vee r).
p \Rightarrow (q \vee r)</math></center>
</math></center>




Jeśli powyższą formułę uznamy za prawdziwą to może nam ona posłużyć
Jeśli powyższą formułę uznamy za prawdziwą, to może nam ona posłużyć
do otrzymania nowych wniosków. Na przykład jeśli o jakiejś liczbie <math>\textnormal{n}</math> będziemy wiedzieć, że jest liczbą pierwszą oraz, że nie jest nieparzysta to klasyczny rachunek zdań pozwoli nam formalnie wywnioskować fakt że liczba <math>\textnormal{n}</math> jest równa '''2'''. Podsumowując, jeśli uznamy za prawdziwe następujące zdania:
do otrzymania nowych wniosków. Na przykład, jeśli o jakiejś liczbie <math>\text{n}</math> będziemy wiedzieć, że jest liczbą pierwszą oraz że nie jest nieparzysta, to klasyczny rachunek zdań pozwoli nam formalnie wywnioskować fakt, że liczba <math>\text{n}</math> jest równa '''2'''. Podsumowując, jeśli uznamy za prawdziwe następujące zdania:


# <math> p \Rightarrow (q \vee r) </math>,
# <math>p \Rightarrow (q \vee r)</math>,
# <math>p </math>,
# <math>p</math>,
# <math> \neg q </math> (przez <math>\neg</math> oznaczamy negację)
# <math>\neg q</math> (przez <math>\neg</math> oznaczamy negację)


to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) zdań
to zgodnie z klasycznym rachunkiem zdań
powinniśmy uznać za prawdziwe zdanie <math>\textnormal{r}</math>, czyli ''<math>\textnormal{n}</math> jest równe '''2'''''. Powyższy schemat wnioskowania można również opisać formułą
powinniśmy uznać za prawdziwe zdanie <math>\text{r}</math>, czyli ''<math>\text{n}</math> jest równe '''2'''''. Powyższy schemat wnioskowania można również opisać formułą




<center><math>
<center><math>


\left((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q)\right)\Rightarrow q.
\left((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q)\right)\Rightarrow q</math></center>
</math></center>




W powyższej formule spójnik symbol <math>\wedge</math> odpowiada spójnikowi <math>\textnormal{i}</math> (oraz).
W powyższej formule symbol <math>\wedge</math> odpowiada spójnikowi <math>\text{i}</math> (oraz).


Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy
Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy
Linia 53: Linia 51:
{{definicja|2.1 [Formuła logiki zdaniowej]||
{{definicja|2.1 [Formuła logiki zdaniowej]||


# ''zmienna zdaniowa jest formułą (zmienne zdaniowe oznaczamy zwykle literami alfabetu rzymskiego np. <math>p,q,r</math>)''
# ''zmienna zdaniowa jest formułą (zmienne zdaniowe oznaczamy zwykle literami alfabetu rzymskiego np. <math>p,q,r</math>)'',
# ''jeśli <math>{\phi}</math> oraz <math>{\psi}</math> są formułami to <math>(\phi \Rightarrow \psi)</math> jest formułą (spójnik <math>\Rightarrow</math> nazywamy implikacją)''
# ''jeśli <math>{\phi}</math> oraz <math>{\psi}</math> są formułami to <math>(\phi \Rightarrow \psi)</math> jest formułą (spójnik <math>\Rightarrow</math> nazywamy implikacją)'',
# ''jeśli <math>{\phi}</math> jest formułą to <math>\neg \phi</math> jest formułą (spójnik <math>\neg</math> nazywamy negacją)''
# ''jeśli <math>{\phi}</math> jest formułą to <math>\neg \phi</math> jest formułą (spójnik <math>\neg</math> nazywamy negacją)'',
# ''nic innego nie jest formułą.''
# ''nic innego nie jest formułą.''


Powyższa definicja mówi, że formułami nazywamy te napisy które dają
Powyższa definicja mówi, że formułami nazywamy te napisy, które dają
się skonstruować ze zmiennych zdaniowych przy pomocy spójników
się skonstruować ze zmiennych zdaniowych przy pomocy spójników
<math>\Rightarrow</math> oraz <math>\neg</math>.
<math>\Rightarrow</math> oraz <math>\neg</math>.
}}
}}


{{uwaga|2.2.|| Zgodnie z powyższą definicją nie jest formułą napis <math>p\Rightarrow q</math>, gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy napisać <math>(p\Rightarrow q)</math> możemy przyjąć że nie będzie konieczne pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić.
{{uwaga|2.2.|| Zgodnie z powyższą definicją nie jest formułą napis <math>p\Rightarrow q</math>, gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy napisać <math>(p\Rightarrow q)</math> możemy przyjąć że nie będzie konieczne pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić. Często przyjmuje się również prawostronne nawiasowanie dla implikacji, czyli formuła <math>p \Rightarrow q \Rightarrow r</math> jest domyślnie nawiasowana w następujący sposób <math>(p \Rightarrow (q \Rightarrow r))</math>.
}}
}}


{{przyklad|2.3 Poniższe napisy nie są formułami||
{{przyklad|2.3 Poniższe napisy nie są formułami||


* <math>p \Rightarrow \Rightarrow q</math>
* <math>p \Rightarrow \Rightarrow q</math>,


* <math>\neg \neg \neg</math>
* <math>\neg \neg \neg</math>,


* ten napis na pewno nie jest formułą
* ten napis na pewno nie jest formułą,


* <math>(p \Rightarrow \neg q))</math>
* <math>(p \Rightarrow \neg q))</math>.


''Poniższe napisy są formułami''
''Poniższe napisy są formułami''


* <math>(p \Rightarrow (r \Rightarrow q))</math>
* <math>(p \Rightarrow (r \Rightarrow q))</math>,


* <math>\neg \neg \neg q</math>
* <math>\neg \neg \neg q</math>,


* <math>(p \Rightarrow \neg q)</math>
* <math>(p \Rightarrow \neg q)</math>.
}}  
}}  


Linia 89: Linia 87:


Rozmiarem formuły nazwiemy ilość występujących w niej spójników.
Rozmiarem formuły nazwiemy ilość występujących w niej spójników.
Na przykład formuła <math>\neg \neg q</math> ma rozmiar '''2''', a formuła <math>(p\Rightarrow q)</math> ma rozmiar '''1'''. Przypuśćmy, że jedyną zmienną zdaniową jaką wolno nam użyć jest <math>\textnormal{p}</math>. Ile można skonstruować rożnych formuł o rozmiarze '''3'''?
Na przykład formuła <math>\neg \neg q</math> ma rozmiar '''2''', a formuła <math>(p\Rightarrow q)</math> ma rozmiar '''1'''. Przypuśćmy, że jedyną zmienną zdaniową jaką wolno nam użyć jest <math>\text{p}</math>. Ile można skonstruować rożnych formuł o rozmiarze '''3'''?
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  


Oznaczmy przez <math>f_n</math> liczbę formuł o rozmiarze <math>\textnormal{n}</math> (czyli liczbę formuł w których jest <math>\textnormal{n}</math> spójników). Interesuje nas <math>f_3</math>. Każda formuła o rozmiarze '''3''' powstaje albo z dwóch formuł o rozmiarach '''1''' poprzez połączenie ich spójnikiem <math>\Rightarrow</math> albo z jednej formuły o rozmiarze '''2''' poprzez dodanie do niej spójnika <math>\neg</math>. Co więcej każda taka formuła powstaje tylko w jeden sposób. Wynika stąd następująca zależność:
Oznaczmy przez <math>f_n</math> liczbę formuł o rozmiarze <math>\text{n}</math> (czyli liczbę formuł w których jest <math>\text{n}</math> spójników). Interesuje nas <math>f_3</math>. Każda formuła o rozmiarze '''3''' powstaje z dwóch formuł o rozmiarach '''1''' poprzez połączenie ich spójnikiem <math>\Rightarrow</math> lub dwóch formuł o rozmiarach odpowiednio '''0''' i '''2''' oraz '''2''' i '''0''',  lub z jednej formuły o rozmiarze '''2''' poprzez dodanie do niej spójnika <math>\neg</math>. Co więcej każda taka formuła powstaje tylko w jeden sposób. Wynika stąd następująca zależność:


<center><math>
<center><math>
 
f_3= (f_1)^2+ 2 f_2 +f_2</math></center>
f_3= f_2 + (f_1)^2
</math></center>


Wiemy, że są tylko dwie formuły o rozmiarze '''1''', są to <math>\neg p</math> oraz <math>p \Rightarrow p</math>. Stąd mamy <math>f_1=2</math>. Dla formuł o rozmiarze '''2''' możemy zauważyć podobną zależność. Każda taka formuła jest albo zbudowana z
Wiemy, że są tylko dwie formuły o rozmiarze '''1''', są to <math>\neg p</math> oraz <math>p \Rightarrow p</math>. Stąd mamy <math>f_1=2</math>. Dla formuł o rozmiarze '''2''' możemy zauważyć podobną zależność. Każda taka formuła jest albo zbudowana z
dwóch formuł z których jedna (niekoniecznie pierwsza) ma rozmiar '''1''' a druga '''0'''  za pomocą <math>\Rightarrow</math>, albo jest zbudowana z formuły o rozmiarze '''1''' za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze '''0''', jest to <math>\textnormal{p}</math>. Mamy więc następujący wzór dla <math>f_2</math>
dwóch formuł z których jedna (niekoniecznie pierwsza) ma rozmiar '''1''' a druga '''0'''  za pomocą <math>\Rightarrow</math>, albo jest zbudowana z formuły o rozmiarze '''1''' za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze '''0''', jest to <math>\text{p}</math>. Mamy więc następujący wzór dla <math>f_2</math>


<center><math>
<center><math>


f_2= 1 \cdot f_1 + f_1 \cdot 1 +f_1 = 3 \cdot f_1
f_2= 1 \cdot f_1 + f_1 \cdot 1 +f_1 = 3 \cdot f_1</math></center>
</math></center>


Z dwóch ostatnich wzorów otrzymujemy
Z dwóch ostatnich wzorów otrzymujemy
Linia 112: Linia 107:
<center><math>
<center><math>


f_3= 3 \cdot f_1 + (f_1)^2= 6+4 = 10
f_3= 9 \cdot f_1 + (f_1)^2= 18+4 = 22</math></center>
</math></center>


Skoro jest ich niewiele to możemy wszystkie wypisać
Skoro jest ich niewiele, to możemy wszystkie wypisać


:1. <math>\neg \neg \neg p</math>
:1. <math>\neg \neg \neg p</math>
Linia 127: Linia 121:
:5. <math>\neg (\neg p \Rightarrow  p)</math>
:5. <math>\neg (\neg p \Rightarrow  p)</math>


:6. <math>\neg ((p\Rightarrow p) \Rightarrow p)</math>
:6. <math>\neg ((p\Rightarrow p) \Rightarrow p)</math>


:7. <math> (\neg p)\Rightarrow (\neg p)</math>
:7. <math>p \Rightarrow (\neg \neg p)</math>


:8. <math> (\neg p)\Rightarrow  (p \Rightarrow p)</math>
:8. <math>p \Rightarrow (\neg (p \Rightarrow p))</math>


:9. <math> (p \Rightarrow p) \Rightarrow  (\neg p)</math>
:9. <math>p \Rightarrow (p \Rightarrow \neg p)</math>
 
:10. <math>p \Rightarrow (p \Rightarrow (p\Rightarrow p))</math>
 
:11. <math>p \Rightarrow (\neg p \Rightarrow p)</math>
 
:12. <math>p \Rightarrow ((p\Rightarrow p) \Rightarrow p)</math>
 
:13. <math>(\neg \neg p) \Rightarrow p</math>
 
:14. <math>(\neg (p \Rightarrow p))\Rightarrow p</math>
 
:15. <math>(p \Rightarrow \neg p) \Rightarrow p</math>
 
:16. <math>(p \Rightarrow (p\Rightarrow p)) \Rightarrow p</math>
 
:17. <math>(\neg p \Rightarrow  p) \Rightarrow p</math>
 
:18. <math>((p\Rightarrow p) \Rightarrow  p)\Rightarrow p</math>
 
:19. <math>(\neg p)\Rightarrow  (\neg p)</math>
 
:20. <math>(\neg p)\Rightarrow  (p \Rightarrow p)</math>
 
:21. <math>(p \Rightarrow p) \Rightarrow  (\neg p)</math>
 
:22. <math>(p \Rightarrow p)\Rightarrow  (p \Rightarrow p)</math>


:10. <math> (p \Rightarrow p)\Rightarrow  (p \Rightarrow p)</math>
</div></div>
</div></div>
}}


{{uwaga|2.4.|| Język logiki zdaniowej można równoważnie zdefiniować nie używając nawiasów za pomocą Odwrotnej Notacji Polskiej
 
<u>'''Odwrotna Notacja Polska.'''</u>
{{uwaga|2.4.|| Język logiki zdaniowej można równoważnie zdefiniować nie używając nawiasów za pomocą tzw. Odwrotnej Notacji Polskiej.
}}
}}


Linia 146: Linia 164:


Podobnie jak nie wszystkie zdania języka naturalnego mają sens, nie
Podobnie jak nie wszystkie zdania języka naturalnego mają sens, nie
wszystkie formuły opisują prawdziwe schematy wnioskowania, lub
wszystkie formuły opisują prawdziwe schematy wnioskowania lub
zdania które bylibyśmy skłonni uznać za prawdziwe. W tym rozdziale
zdania, które bylibyśmy skłonni uznać za prawdziwe. W tym rozdziale
skupimy się na tym które spośród wszystkich formuł zdaniowych
skupimy się na tym, które spośród wszystkich formuł zdaniowych
wyróżnić jako prawdziwe.
wyróżnić jako prawdziwe.


===Aksjomaty===
===Aksjomaty===


Wielu matematyków zgadza się dzisiaj co do tego że zdania pasujące
Wielu matematyków zgadza się dzisiaj co do tego, że zdania pasujące
do poniższych schematów powinny być uznane za prawdziwe:
do poniższych schematów powinny być uznane za prawdziwe:


{{definicja|3.1 Aksjomaty klasycznego rachunku zdań||
{{definicja|3.1 Aksjomaty klasycznego rachunku zdań||


# ''<math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana aksjomatem K)
# ''<math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana aksjomatem K),
# ''<math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana aksjomatem S)
# ''<math>(\phi \Rightarrow (\nu \Rightarrow \psi)) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \psi) \right)</math> (formuła ta jest nazywana aksjomatem S),
# ''<math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi</math>
# ''<math>(\neg \phi \Rightarrow \psi) \Rightarrow ((\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi)</math> (tzw. schemat dowodu niewprost)
}}
}}
Zdania pasujące do powyższych schematów to wszystkie zdania które
Zdania pasujące do powyższych schematów to wszystkie zdania, które
można otrzymać podstawiając w miejsce <math>\phi, \nu, \psi</math> dowolne
można otrzymać, podstawiając w miejsce <math>\phi, \nu, \psi</math> dowolne
formuły.
formuły.


===Reguła dowodzenia===
===Reguła dowodzenia===


Przyglądnijmy się teraz jak posługujemy się implikacją we
Przyglądnijmy się teraz jak posługujemy się implikacją we wnioskowaniu. W przykładzie z początku wykładu implikacja odpowiadała konstrukcji językowej:
wniskowaniu. W przykładzie z początku wykładu implikacja odpowiadała
konstrukcji językowej:


<center>'''jeśli''' <math>{\phi}</math> '''to''' <math>{\psi}</math>.</center>
<center>'''jeśli''' <math>{\phi}</math> '''to''' <math>{\psi}</math>.</center>


<span id="modus_ponens">
<span id="modus_ponens">
W takim przypadku jeśli akceptujemy powyższą implikacjię jako zdanie
W takim przypadku, jeśli akceptujemy powyższą implikacjię jako zdanie
prawdziwe oraz jeśli zdanie <math>{\phi}</math> jako prawdziwe to powinniśmy
prawdziwe oraz jeśli zdanie <math>{\phi}</math> jako prawdziwe, to powinniśmy
także zaakceptować <math>{\psi}</math>. Przedstawiony sposób wnioskowania nosi
także zaakceptować <math>{\psi}</math>. Przedstawiony sposób wnioskowania nosi
nazwę reguły ''Modus Ponens'' (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest skrótowo notowany w poniższy sposób</span>
nazwę reguły ''Modus Ponens'' (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest skrótowo notowany w poniższy sposób</span>


<center><math>
<center><math>
\frac{\phi \Rightarrow \psi, \phi} \psi}.
\frac{\phi \Rightarrow \psi, \phi} {\psi}</math></center>
</math></center>


Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów  o
Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów  o
ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby
ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby
precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych
precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych
aksjomatów definiujemy poniżej pojęcie dowodu.
aksjomatów, definiujemy poniżej pojęcie dowodu.


{{definicja|3.2||
{{definicja|3.2||
Linia 195: Linia 209:
''wtedy i tylko wtedy, gdy:''
''wtedy i tylko wtedy, gdy:''


# ''<math>\phi_n</math> jest formułą <math>{\psi}</math>''
# ''<math>\phi_n</math> jest formułą <math>{\psi}</math>'',
# ''dla każdego <math>i\leq n</math> formuła <math>\phi_i</math> jest aksjomatem lub istnieją <math>j,k <i</math> takie, że formuła <math>\phi_i</math> jest wynikiem zastosowania reguły modus ponens do formuł <math>\phi_j, \phi_k</math>.''
# ''dla każdego <math>i\leq n</math> formuła <math>\phi_i</math> jest aksjomatem lub istnieją <math>j,k <i</math> takie, że formuła <math>\phi_i</math> jest wynikiem zastosowania reguły modus ponens do formuł <math>\phi_j, \phi_k</math>.''
}}
}}
W drugim punkcie powyższej definicji jeśli formuła <math>\phi_i</math> nie jest
W drugim punkcie powyższej definicji, jeśli formuła <math>\phi_i</math> nie jest
aksjomatem (a więc powstaje przez zastosowanie MP) to formuły
aksjomatem (a więc powstaje przez zastosowanie MP), to formuły
<math>\phi_j,\phi_k</math> muszą pasować do przesłanek reguły MP, a więc
<math>\phi_j,\phi_k</math> muszą pasować do przesłanek reguły MP, a więc
<math>\phi_j</math> musi być postaci <math>\phi_k \Rightarrow \phi_i</math> lub <math>\phi_k</math> postaci
<math>\phi_j</math> musi być postaci <math>\phi_k \Rightarrow \phi_i</math> lub <math>\phi_k</math> postaci
Linia 214: Linia 228:


Zastanówmy się na formułą postaci <math>\phi \Rightarrow \phi</math>. Intuicja
Zastanówmy się na formułą postaci <math>\phi \Rightarrow \phi</math>. Intuicja
podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie pasuje ona jednak do żadnego ze schematów aksjomatów 3.1. Formuła ta jest jednak twierdzeniem klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby łatwiej dopasować formuły do schematów aksjomatów użyliśmy
podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie pasuje ona jednak do żadnego ze schematów aksjomatów 3.1. Formuła ta jest jednak twierdzeniem klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby łatwiej dopasować formuły do schematów aksjomatów, użyliśmy
nawiasów kwadratowych dla nawiasów, które pochodzą ze  schematów.
nawiasów kwadratowych dla nawiasów, które pochodzą ze  schematów.


# <math>[\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi)]\Rightarrow [[\phi \Rightarrow (q \Rightarrow \phi)] \Rightarrow [\phi \Rightarrow\phi]]</math> formuła ta jest aksjomatem zgodnym ze schematem S
# <math>[\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi)]\Rightarrow [[\phi \Rightarrow (q \Rightarrow \phi)] \Rightarrow [\phi \Rightarrow\phi]]</math> formuła ta jest aksjomatem zgodnym ze schematem S,
# <math>\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi]</math> aksjomat zgodny ze schematem K
# <math>\phi \Rightarrow [(q \Rightarrow \phi) \Rightarrow \phi]</math> aksjomat zgodny ze schematem K,
# <math>(\phi \Rightarrow (q \Rightarrow \phi)) \Rightarrow (\phi \Rightarrow \phi)</math> z modus ponens z formuł 1 i 2.
# <math>(\phi \Rightarrow (q \Rightarrow \phi)) \Rightarrow (\phi \Rightarrow \phi)</math> z modus ponens z formuł 1 i 2,
# <math>\phi \Rightarrow [q \Rightarrow \phi]</math> aksjomat zgodny ze schematem K
# <math>\phi \Rightarrow [q \Rightarrow \phi]</math> aksjomat zgodny ze schematem K,
# <math>(\phi \Rightarrow \phi)</math> z modus ponens z formuł '''3''' i '''4'''
# <math>(\phi \Rightarrow \phi)</math> z modus ponens z formuł '''3''' i '''4'''.


===Podsumowanie===
===Podsumowanie===


Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za
Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za
prawdziwe zdefiniowaliśmy wyróżniając pewne formuły jako aksjomaty 3.1 i dorzucając do nich wszystkie formuły, które dają się z nich wywnioskować przy pomocy reguły modus ponens.
prawdziwe, zdefiniowaliśmy, wyróżniając pewne formuły jako aksjomaty 3.1 i dorzucając do nich wszystkie formuły, które dają się z nich wywnioskować przy pomocy reguły Modus Ponens.
Warto zwrócić uwagę, że pomimo tego iż w doborze aksjomatów i reguł wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną, zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.
Warto zwrócić uwagę, że pomimo tego, iż w doborze aksjomatów i reguł wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną, zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.


{{Uwaga|3.4||
{{Uwaga|3.4||
Linia 235: Linia 249:
postaci <math>\phi \Rightarrow (\nu \Rightarrow \psi)</math> jako „jeśli prawdziwe jest
postaci <math>\phi \Rightarrow (\nu \Rightarrow \psi)</math> jako „jeśli prawdziwe jest
<math>{\phi}</math> i prawdziwe jest <math>\nu</math> to prawdziwe jest <math>{\psi}</math>”. W
<math>{\phi}</math> i prawdziwe jest <math>\nu</math> to prawdziwe jest <math>{\psi}</math>”. W
kolejnych rozdziałach przekonamy się że taka interpretacja jest uzasadniona.
kolejnych rozdziałach przekonamy się, że taka interpretacja jest uzasadniona.
}}
}}


Linia 276: Linia 290:
{| border="1" cellspacing="0" CELLPADDING="5"  
{| border="1" cellspacing="0" CELLPADDING="5"  


| <math>\textnormal{p}</math> || <math>\neg p</math>
| <math>\text{p}</math> || <math>\neg p</math>


|-
|-
Linia 295: Linia 309:
{{definicja|4.2||
{{definicja|4.2||


Wartościowaniem nazywamy funkcję która przypisuje zmiennym
Wartościowaniem nazywamy funkcję, która przypisuje zmiennym
zdaniowym elementy zbioru <math>\mathbb{B}</math>. Wartościowanie zmiennych
zdaniowym elementy zbioru <math>\mathbb{B}</math>. Wartościowanie zmiennych
można rozszerzyć na wartościowanie formuł interpretując spójniki
można rozszerzyć na wartościowanie formuł interpretując spójniki
Linia 306: Linia 320:
* formuła <math>q \Rightarrow p</math> jest wartościowana na '''0''' (będziemy to zapisywać jako <math>v(q \Rightarrow p)=0</math>),
* formuła <math>q \Rightarrow p</math> jest wartościowana na '''0''' (będziemy to zapisywać jako <math>v(q \Rightarrow p)=0</math>),


* formuła <math>r \Rightarrow (q \Rightarrow p)</math> jest wartościowana na '''1''' (czyli <math>v(r \Rightarrow (q \Rightarrow p))=1</math>)
* formuła <math>r \Rightarrow (q \Rightarrow p)</math> jest wartościowana na '''1''' (czyli <math>v(r \Rightarrow (q \Rightarrow p))=1</math>),


* formuła <math>\neg p \Rightarrow r</math> jest wartościowana na  '''0''' (czyli <math>v(\neg p \Rightarrow r)=0</math>)
* formuła <math>\neg p \Rightarrow r</math> jest wartościowana na  '''0''' (czyli <math>v(\neg p \Rightarrow r)=0</math>).


}}
}}
Linia 316: Linia 330:
Przy wartościowaniu <math>v</math> z przykładu 4.3 jakie wartości przyjmują następujące formuły
Przy wartościowaniu <math>v</math> z przykładu 4.3 jakie wartości przyjmują następujące formuły


# <math>p \Rightarrow (q \Rightarrow r)</math>
# <math>p \Rightarrow (q \Rightarrow r)</math>,
# <math>p \Rightarrow (p \Rightarrow q)</math>
# <math>p \Rightarrow (p \Rightarrow q)</math>,
# <math>\neg \neg q \Rightarrow p</math>
# <math>\neg \neg q \Rightarrow p</math>,
# <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
# <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</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">
<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">
:   
:   
Linia 332: Linia 346:
:4. <math>v((\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q))=0</math>
:4. <math>v((\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q))=0</math>
</div></div>
</div></div>
}}
 
</span>
</span>
<span id="cwiczenie_4_2">{{cwiczenie|4.2||
<span id="cwiczenie_4_2">{{cwiczenie|4.2||
Linia 344: Linia 358:
:(b) <math>\neg (\neg p \Rightarrow  \neg q)</math>
:(b) <math>\neg (\neg p \Rightarrow  \neg q)</math>
:(c) <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
:(c) <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</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">  
<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">  


Wartościowania będziemy oznaczać przez <math>\textnormal{v}</math>
Wartościowania będziemy oznaczać przez <math>\text{v}</math>


:1. (a) <math>v(p)=1, v(q)=1, v(r)=0</math>
:1. (a) <math>v(p)=1, v(q)=1, v(r)=0</math>
Linia 361: Linia 375:
: &nbsp;&nbsp;&nbsp;&nbsp;(c) <math>v(q)=1</math>
: &nbsp;&nbsp;&nbsp;&nbsp;(c) <math>v(q)=1</math>
</div></div>
</div></div>
}}</span>
</span>


===Twierdzenie o pełności===
===Twierdzenie o pełności===


Zauważmy, że istnieją formuły, które dla każdego wartościowania
Zauważmy, że istnieją formuły, które dla każdego wartościowania
zmiennych zdaniowych zawsze przyjmują wartość '''1''' (np. <math>p \Rightarrow p</math>).
zmiennych zdaniowych, zawsze przyjmują wartość '''1''' (np. <math>p \Rightarrow p</math>).
Takie formuły będziemy nazywać '''tautologiami'''.
Takie formuły będziemy nazywać '''tautologiami'''.


Linia 373: Linia 387:
Sprawdź czy poniższe formuły są tautologiami
Sprawdź czy poniższe formuły są tautologiami


# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
# <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>(\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>
# <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg \psi) \Rightarrow \phi</math>,
# <math>((\phi \Rightarrow q) \Rightarrow p) \Rightarrow p</math>
# <math>((\phi \Rightarrow q) \Rightarrow p) \Rightarrow p</math>.
 
}}
<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">  
<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">  


Spróbuj poszukać wartościowań dla których formuła przyjmuje wartość '''0'''
Spróbuj poszukać wartościowań, dla których formuła przyjmuje wartość '''0'''.
</div></div>
</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">  
<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">  
Linia 392: Linia 406:
<center>  
<center>  
{| border="1" cellspacing="0"
{| border="1" cellspacing="0"
! <math>\phi</math>!! <math>\psi</math>!! <math>\psi \Rightarrow \phi</math>!! <math>\displaystyle (\phi \Rightarrow (\psi \Rightarrow \phi))</math>!!
! <math>\phi</math>!! <math>\psi</math>!! <math>\psi \Rightarrow \phi</math>!! <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>!!
|-
|-
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
Linia 404: Linia 418:
</center>
</center>


: Ponieważ w kolumnie odpowiadającej formule <math>\displaystyle (\phi \Rightarrow (\psi \Rightarrow \phi))</math> są same 1 to formuła ta jest tautologią.
: Ponieważ w kolumnie odpowiadającej formule <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> są same 1 to formuła ta jest tautologią.
</div></div>
</div></div>
}}
 


Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania odpowiadają aksjomatom klasycznego rachunku zdań 3.1. Okazuje się że istnieje ścisły związek pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik [[Biografia Post, Emil Leon|Emila Posta]]
Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania odpowiadają aksjomatom klasycznego rachunku zdań 3.1. Okazuje się że istnieje ścisły związek pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik [[Biografia Post, Emil Leon|Emila Posta]]
Linia 412: Linia 426:
[[grafika:Post.jpg|thumb|right||Emil Leon Post (1897-1954)<br>[[Biografia Post|Zobacz biografię]]]]
[[grafika:Post.jpg|thumb|right||Emil Leon Post (1897-1954)<br>[[Biografia Post|Zobacz biografię]]]]


<span id="twierdzenie_4_4">
{{twierdzenie|4.4||
{{twierdzenie|4.4||
Post 1921 Formuła jest twierdzeniem klasycznego rachunku zdań wtedy i tylko wtedy kiedy jest tautologią.
Post 1921 Formuła jest twierdzeniem klasycznego rachunku zdań wtedy i tylko wtedy kiedy jest tautologią.


}}
}}
Dowód powyższego twierdzenia jest przedstawiony na wykładzie <u>'''Logika dla informatyków'''</u>
</span>
Dzięki powyższemu twierdzeniu możemy w miarę łatwo stwierdzać czy dana formuła jest twierdzeniem klasycznego rachunku zdań sprawdzając czy jest tautologią, co wymaga rozważenia jedynie skończonej (chociaż często niemałej) liczby wartościowań. Co więcej, mamy też możliwość dowodzenia, że jakaś formuła nie jest twierdzeniem klasycznego rachunku zdań. Uzasadnienie, że nie da się jakiejś formuły udowonić z aksjomatów poprzez stosowanie reguły MP wydaje się zadaniem trudnym, znacznie łatwiej jest poszukać wartościowania, które
Dowód powyższego twierdzenia jest przedstawiony na wykładzie [[Logika dla informatyków]]
Dzięki powyższemu twierdzeniu możemy w miarę łatwo stwierdzać, czy dana formuła jest twierdzeniem klasycznego rachunku zdań, sprawdzając, czy jest tautologią, co wymaga rozważenia jedynie skończonej (chociaż często niemałej) liczby wartościowań. Co więcej, mamy też możliwość dowodzenia, że jakaś formuła nie jest twierdzeniem klasycznego rachunku zdań. Uzasadnienie, że nie da się jakiejś formuły udowonić z aksjomatów poprzez stosowanie reguły MP wydaje się zadaniem trudnym, znacznie łatwiej jest poszukać wartościowania, które
wartościuje formułę na ''0'' (znowu wystarczy sprawdzić jedynie skończenie wiele wartościowań).
wartościuje formułę na ''0'' (znowu wystarczy sprawdzić jedynie skończenie wiele wartościowań).


Linia 423: Linia 439:


Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.
Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.
 
}}
<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">  
<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">  


Linia 434: Linia 450:


<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
: Zaczniemy od pokazania, że jeśli formuły <math>\displaystyle \phi \Rightarrow \psi</math> oraz <math>\displaystyle \phi</math> są tautologiami, to formuła <math>\displaystyle \psi</math> jest tautologią. Dla dowodu nie wprost przypuśćmy, że nie jest. Wtedy istnieje wartościowanie, które oznaczymy przez <math>\displaystyle v</math>, dla którego <math>\displaystyle v(\psi)=0</math>. Ponieważ  <math>\displaystyle \phi</math> jest tautologią, to <math>\displaystyle v(\phi)=1</math>. Ponieważ jednak <math>\displaystyle v(\psi)=0</math> oraz <math>\displaystyle v(\phi)=1</math>, to z [[#tabela_4_1|tabeli interpretacji 4.1]] dostajemy <math>\displaystyle v(\phi \Rightarrow \psi)=0</math>.  Jest to sprzeczne z faktem, że <math>\displaystyle \phi \Rightarrow \psi</math> jest tautologią.
: Zaczniemy od pokazania, że jeśli formuły <math>\phi \Rightarrow \psi</math> oraz <math>\phi</math> są tautologiami, to formuła <math>\psi</math> jest tautologią. Dla dowodu niewprost przypuśćmy, że nie jest. Wtedy istnieje wartościowanie, które oznaczymy przez <math>v</math>, dla którego <math>v(\psi)=0</math>. Ponieważ  <math>\phi</math> jest tautologią, to <math>v(\phi)=1</math>. Ponieważ jednak <math>v(\psi)=0</math> oraz <math>v(\phi)=1</math>, to z [[#tabela_4_1|tabeli interpretacji 4.1]] dostajemy <math>v(\phi \Rightarrow \psi)=0</math>.  Jest to sprzeczne z faktem, że <math>\phi \Rightarrow \psi</math> jest tautologią.


:Udowodnimy teraz indukcyjnie, że każda formuła, która ma dowód w klasycznym rachunku zdań, jest tautologią klasycznego rachunku zdań. Indukcję poprowadzimy ze względu na długość dowodu (długością dowodu nazywamy ilość formuł w ciągu będącym dowodem).
:Udowodnimy teraz indukcyjnie, że każda formuła, która ma dowód w klasycznym rachunku zdań, jest tautologią klasycznego rachunku zdań. Indukcję poprowadzimy ze względu na długość dowodu (długością dowodu nazywamy ilość formuł w ciągu będącym dowodem).


:# Baza indukcji. Jeśli formuła <math>\displaystyle \phi</math> ma dowód długości jeden, to musi być jednym z aksjomatów. W [[#cwiczenie_4_1|ćwiczeniu 4.1]] pokazaliśmy, że wszystkie aksjomaty są tautologiami, wobec czego <math>\displaystyle \phi</math> jest tautologią.
:# Baza indukcji. Jeśli formuła <math>\phi</math> ma dowód długości jeden, to musi być jednym z aksjomatów. W [[#cwiczenie_4_1|ćwiczeniu 4.1]] pokazaliśmy, że wszystkie aksjomaty są tautologiami, wobec czego <math>\phi</math> jest tautologią.
:# Krok indukcyjny. Weźmy dowolne <math>\displaystyle n\in N</math> takie, że <math>\displaystyle n>1</math> i przypuśćmy, że wszystkie formuły o dowodach silnie krótszych od <math>\displaystyle n</math> są tautologiami. Pokażemy, że wszystkie formuły o dowodach długości <math>\displaystyle n</math> są tautologiami. Weźmy dowolną formułę <math>\displaystyle \Phi</math> o dowodzie długości <math>\displaystyle n</math>, niech <math>\displaystyle \phi_1, \dots,\phi_{n-1},\phi_n=\Phi</math> będzie dowodem <math>\displaystyle \Phi</math>. Jeśli <math>\displaystyle \Phi</math> jest aksjomatem to z [[#cwiczenie_4_1|ćwiczenia 4.1]] wynika, że <math>\displaystyle \Phi</math> jest tautologią. W przeciwnym przypadku <math>\displaystyle \Phi</math> musiała powstać przez zastosowanie reguły MP do pewnych formuł <math>\displaystyle \phi_i, \phi_j</math>. Ponieważ <math>\displaystyle \phi_i</math> występuje w dowodzie formuły <math>\displaystyle \Phi</math> to ciąg formuł <math>\displaystyle \phi_1, \dots,\phi_i</math> jest dowodem formuły <math>\displaystyle \phi_i</math>. Ponieważ istnieje dowód formuły, <math>\displaystyle \phi_i</math> o długości silnie mniejszej od <math>\displaystyle n</math> to z założenia indukcyjnego formuła <math>\displaystyle \phi_i</math> jest tautologią. Analogiczne rozumowanie dla <math>\displaystyle \phi_j</math> pokazuje, że formuła <math>\displaystyle \phi_j</math> też jest tautologią. Wobec tego z faktu udowodnionego na początku tego ćwiczenia wynika, że również <math>\displaystyle \Phi</math> jest tautologią, jako formuła powstająca przez zastosowanie reguły MP do tautologii. Wobec dowolności wyboru <math>\displaystyle \Phi</math> otrzymujemy, że wszystkie formuły o dowodach długości <math>\displaystyle n</math> są tautologiami.
:# Krok indukcyjny. Weźmy dowolne <math>n\in N</math> takie, że <math>n>1</math> i przypuśćmy, że wszystkie formuły o dowodach silnie krótszych od <math>n</math> są tautologiami. Pokażemy, że wszystkie formuły o dowodach długości <math>n</math> są tautologiami. Weźmy dowolną formułę <math>\Phi</math> o dowodzie długości <math>n</math>, niech <math>\phi_1, \dots,\phi_{n-1},\phi_n=\Phi</math> będzie dowodem <math>\Phi</math>. Jeśli <math>\Phi</math> jest aksjomatem to z [[#cwiczenie_4_1|ćwiczenia 4.1]] wynika, że <math>\Phi</math> jest tautologią. W przeciwnym przypadku <math>\Phi</math> musiała powstać przez zastosowanie reguły MP do pewnych formuł <math>\phi_i, \phi_j</math>. Ponieważ <math>\phi_i</math> występuje w dowodzie formuły <math>\Phi</math> to ciąg formuł <math>\phi_1, \dots,\phi_i</math> jest dowodem formuły <math>\phi_i</math>. Ponieważ istnieje dowód formuły, <math>\phi_i</math> o długości silnie mniejszej od <math>n</math> to z założenia indukcyjnego formuła <math>\phi_i</math> jest tautologią. Analogiczne rozumowanie dla <math>\phi_j</math> pokazuje, że formuła <math>\phi_j</math> też jest tautologią. Wobec tego z faktu udowodnionego na początku tego ćwiczenia wynika, że również <math>\Phi</math> jest tautologią, jako formuła powstająca przez zastosowanie reguły MP do tautologii. Wobec dowolności wyboru <math>\Phi</math> otrzymujemy, że wszystkie formuły o dowodach długości <math>n</math> są tautologiami.
</div></div>
</div></div>


}}
 


===Inne spójniki===
===Inne spójniki===
Linia 489: Linia 505:


Zgodnie z intuicją koniunkcja <math>\phi \wedge\psi</math> jest wartościowana
Zgodnie z intuicją koniunkcja <math>\phi \wedge\psi</math> jest wartościowana
na '''1''' wtedy i tylko wtedy gdy zarówno <math>{\phi}</math> jak i <math>{\psi}</math> są
na '''1''' wtedy i tylko wtedy, gdy zarówno <math>{\phi}</math> jak i <math>{\psi}</math> są
wartościowane na '''1'''. Alternatywa <math>\phi \vee \psi</math> jest wartościowana
wartościowane na '''1'''. Alternatywa <math>\phi \vee \psi</math> jest wartościowana
na '''1''' jeśli przynajmniej jedna z formuł <math>\phi, \psi</math> jest
na '''1''', jeśli przynajmniej jedna z formuł <math>\phi, \psi</math> jest
wartościowana na '''1'''.
wartościowana na '''1'''.


Linia 497: Linia 513:


Formuły <math>{\phi}</math> oraz <math>{\psi}</math> są ''równoważne'' (oznaczamy ten fakt
Formuły <math>{\phi}</math> oraz <math>{\psi}</math> są ''równoważne'' (oznaczamy ten fakt
przez <math>\phi \equiv \psi</math> wtedy i tylko wtedy gdy dla każdego wartościowania formuła <math>{\phi}</math> przyjmuje tą samą wartość co formuła <math>{\psi}</math>.
przez <math>\phi \equiv \psi</math> wtedy i tylko wtedy, gdy dla każdego wartościowania formuła <math>{\phi}</math> przyjmuje tą samą wartość co formuła <math>{\psi}</math>.
}}
}}
{{cwiczenie|4.5||
{{cwiczenie|4.5||
Linia 503: Linia 519:
Udowodnij, że następujące formuły są równoważne
Udowodnij, że następujące formuły są równoważne


# <math>\phi \vee \psi \equiv \neg \phi \Rightarrow \psi </math>
# <math>\phi \vee \psi \equiv \neg \phi \Rightarrow \psi</math>
# <math>\phi \wedge \psi \equiv \neg (\phi \Rightarrow \neg \psi)</math>
# <math>\phi \wedge \psi \equiv \neg (\phi \Rightarrow \neg \psi)</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">   
<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. Lewa strona jest fałszywa jedynie gdy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''0'''. Prawa strona jest fałszywa wtedy i tylko wtedy kiedy <math>\neg \phi</math> jest wartościowane na '''1''' oraz <math>{\psi}</math> jest wartościowane na '''0''' (to jedyna możliwość aby implikacja była fałszywa). Wobec tego prawa strona jest fałszywa wtedy i tylko wtedy kiedy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''0''', a więc jest równoważna lewej.
:1. Lewa strona jest fałszywa jedynie, gdy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''0'''. Prawa strona jest fałszywa wtedy i tylko wtedy, kiedy <math>\neg \phi</math> jest wartościowane na '''1''' oraz <math>{\psi}</math> jest wartościowane na '''0''' (to jedyna możliwość aby implikacja była fałszywa). Wobec tego prawa strona jest fałszywa wtedy i tylko wtedy, kiedy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''0''', a więc jest równoważna lewej.


:2. Lewa strona jest prawdziwa jedynie gdy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''1'''. Prawa strona jest prawdziwa wtedy i tylko wtedy kiedy <math>\neg (\phi \Rightarrow \neg \psi)</math> jest wartościowane na '''1''', więc wtedy gdy <math>(\phi \Rightarrow \neg \psi)</math> jest wartościowane na '''0'''. To z kolei zdarzyć się może jedynie gdy <math>{\phi}</math> jest wartościowane na '''1''' i <math>\neg \psi</math> na '''0''', a więc wtedy gdy zarówno <math>{\phi}</math> jak i <math>{\psi}</math> są wartościowane na '''1'''. Wobec tego obie formuły są równoważne.
:2. Lewa strona jest prawdziwa jedynie, gdy <math>{\phi}</math> oraz <math>{\psi}</math> są wartościowane na '''1'''. Prawa strona jest prawdziwa wtedy i tylko wtedy, kiedy <math>\neg (\phi \Rightarrow \neg \psi)</math> jest wartościowane na '''1''', więc wtedy gdy <math>(\phi \Rightarrow \neg \psi)</math> jest wartościowane na '''0'''. To z kolei zdarzyć się może jedynie, gdy <math>{\phi}</math> jest wartościowane na '''1''' i <math>\neg \psi</math> na '''0''', a więc wtedy, gdy zarówno <math>{\phi}</math> jak i <math>{\psi}</math> są wartościowane na '''1'''. Wobec tego obie formuły są równoważne.


Równie dobrym rozwiązaniem jest sprawdzenie wszystkich
Równie dobrym rozwiązaniem jest sprawdzenie wszystkich
Linia 517: Linia 533:


Z powyższego zadania wynika, że każdą formułę w której występują
Z powyższego zadania wynika, że każdą formułę w której występują
spójniki <math>\wedge</math> lub <math>\vee</math> można zastąpić równoważną formułą w
spójniki <math>\wedge</math> lub <math>\vee</math> można zastąpić równoważną formułą, w
której jedynymi spójnikami są <math>\Rightarrow</math> oraz <math>\neg</math>. Tak naprawdę
której jedynymi spójnikami są <math>\Rightarrow</math> oraz <math>\neg</math>. Tak naprawdę
więc nowe spójniki nie wprowadzają nic nowego poza użytecznymi
więc nowe spójniki nie wprowadzają nic nowego poza użytecznymi skrótami w zapisywaniu formuł.
skrótami w zapisywaniu formuł.
Aby się oswoić z własnościami spójników, prześledzimy szereg ich
Aby się oswoić z własnościami spójników prześledzimy szereg ich
praw.
praw.


Linia 528: Linia 543:
Udowodnij następujące równoważności
Udowodnij następujące równoważności


# <math>\neg \neg p \equiv p</math>
# <math>\neg \neg p \equiv p</math>,
# <math>p\Rightarrow q \equiv \neg p \vee q</math>
# <math>p\Rightarrow q \equiv \neg p \vee q</math>,
# <math>p \Rightarrow (q \Rightarrow r) \equiv (p \wedge q) \Rightarrow r</math>
# <math>p \Rightarrow (q \Rightarrow r) \equiv (p \wedge q) \Rightarrow r</math>,
# <math>\neg( p \wedge q) \equiv \neg p \vee \neg q</math>
# <math>\neg( p \wedge q) \equiv \neg p \vee \neg q</math>,
# <math>\neg( p \vee q) \equiv \neg p \wedge \neg q</math>
# <math>\neg( p \vee q) \equiv \neg p \wedge \neg q</math>,
# <math>p \wedge (q \vee r) \equiv (p \wedge q) \vee (p\wedge r)</math>
# <math>p \wedge (q \vee r) \equiv (p \wedge q) \vee (p\wedge r)</math>,
# <math>p \vee (q \wedge r) \equiv (p \vee q) \wedge (p\vee r)</math>
# <math>p \vee (q \wedge r) \equiv (p \vee q) \wedge (p\vee r)</math>,
# <math>(p \Rightarrow q) \Rightarrow (\neg p \Rightarrow \neg q)</math>
# <math>(p \Rightarrow q) \Rightarrow (\neg p \Rightarrow \neg q)</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">  
<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">  
Linia 541: Linia 556:
Przedstawiamy przykładowe dowody kilku pierwszych równoważności.
Przedstawiamy przykładowe dowody kilku pierwszych równoważności.


:1. Jeśli <math>\textnormal{p}</math> jest wartościowane na '''1''', to zgodnie z tabelą dla negacji 4.1 <math>\neg p</math> jest wartościowane na '''0''' i <math>\neg \neg p</math> jest wartościowane na '''1'''. Jeśli <math>\textnormal{p}</math> jest wartościowane na '''0''' to <math>\neg p</math> jest wartościowane na '''1''' i <math>\neg \neg p</math> jest wartościowane na '''0'''. Formuły przyjmują te same wartości dla każdego wartościowania więc są równoważne.
:1. Jeśli <math>\text{p}</math> jest wartościowane na '''1''', to zgodnie z tabelą dla negacji 4.1 <math>\neg p</math> jest wartościowane na '''0''' i <math>\neg \neg p</math> jest wartościowane na '''1'''. Jeśli <math>\text{p}</math> jest wartościowane na '''0''' to, <math>\neg p</math> jest wartościowane na '''1''' i <math>\neg \neg p</math> jest wartościowane na '''0'''. Formuły przyjmują te same wartości dla każdego wartościowania, więc są równoważne.


:2. Jedyną możliwością aby lewa strona była fałszywa jest aby <math>\textnormal{p}</math> było wartościowane na '''1''', a <math>\textnormal{q}</math> na '''0'''. Prawa stona jest fałszywa jedynie gdy <math>\neg p</math> oraz <math>\textnormal{q}</math> są wartościowane na '''0'''. Czyli prawa strona jest fałszywa jedynie gdy <math>\textnormal{p}</math> jest wartościowane na '''1''' i <math>\textnormal{q}</math> na '''0'''. Formuły są więc równoważne.
:2. Jedyną możliwością, aby lewa strona była fałszywa jest, aby <math>\text{p}</math> było wartościowane na '''1''', a <math>\text{q}</math> na '''0'''. Prawa stona jest fałszywa jedynie, gdy <math>\neg p</math> oraz <math>\text{q}</math> są wartościowane na '''0'''. Czyli prawa strona jest fałszywa, jedynie gdy <math>\text{p}</math> jest wartościowane na '''1''' i <math>\text{q}</math> na '''0'''. Formuły są więc równoważne.


:3. Analogicznie do poprzedniego punktu łatwo się przekonać, że jedynym wartościowaniem które falsyfikuje lewą stronę jest takie które wartościuje <math>\textnormal{p}</math> i <math>\textnormal{q}</math> na '''1''' oraz <math>\textnormal{r}</math> na '''0'''. Tą samą własność ma formuła po prawej stronie, więc formuły są równoważne.
:3. Analogicznie do poprzedniego punktu łatwo się przekonać, że jedynym wartościowaniem, które falsyfikuje lewą stronę, jest takie, które wartościuje <math>\text{p}</math> i <math>\text{q}</math> na '''1''' oraz <math>\text{r}</math> na '''0'''. Tą samą własność ma formuła po prawej stronie, więc formuły są równoważne.


:4. Przykład rozwiązania przez rozważenie wszystkich możliwości
:4. Przykład rozwiązania przez rozważenie wszystkich możliwości
<center>
<center>
{| border="1"
{| border="1"
! <math>\textnormal{p}</math>!! <math>\textnormal{q}</math>!! <math>\textnormal{p} \wedge \textnormal{q}</math>!! <math>\neg( p \wedge q)</math>!! <math>\neg p</math>!! <math>\neg q</math>!! <math>\neg p \vee \neg q</math>
! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{p} \wedge \text{q}</math>!! <math>\neg( p \wedge q)</math>!! <math>\neg p</math>!! <math>\neg q</math>!! <math>\neg p \vee \neg q</math>
|-
|-
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 0|| 1|| 1|| 1|| 1
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 0|| 1|| 1|| 1|| 1
Linia 561: Linia 576:
|}
|}
</center>
</center>
:W pierwszych dwóch kolumnach są zapisane wartościowania zmiennych <math>\textnormal{p}</math> i <math>\textnormal{q}</math> a w pozostałych odpowiadające im wartościowania formuł zbudowanych z tych zmiennych. Ponieważ kolumna '''4''' i '''7''' są identyczne to formuły z zadania są równoważne.
:W pierwszych dwóch kolumnach są zapisane wartościowania zmiennych <math>\text{p}</math> i <math>\text{q}</math>, a w pozostałych odpowiadające im wartościowania formuł zbudowanych z tych zmiennych. Ponieważ kolumna '''4''' i '''7''' są identyczne to formuły z zadania są równoważne.


:5. W równoważności z poprzedniego punktu, podstawiąjąc za <math>\textnormal{p}</math> formułę <math>\neg p</math> oraz za <math>\textnormal{q}</math> formułę <math>\neg q</math> otrzymamy równoważność
:5. W równoważności z poprzedniego punktu, podstawiąjąc za <math>\text{p}</math> formułę <math>\neg p</math> oraz za <math>\text{q}</math> formułę <math>\neg q</math> otrzymamy równoważność


<center><math>
<center><math>


\neg( \neg p \wedge \neg q) \equiv \neg \neg p \vee \neg\neg q. </math></center>
\neg( \neg p \wedge \neg q) \equiv \neg \neg p \vee \neg\neg q</math></center>


:Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony otrzymujemy
:Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony otrzymujemy
Linia 573: Linia 588:
<center><math>
<center><math>


\neg( \neg p \wedge \neg q) \equiv  p \vee    q.
\neg( \neg p \wedge \neg q) \equiv  p \vee    q</math></center>
</math></center>


:Negując tą równoważność obustronnie otrzymamy
:Negując tą równoważność obustronnie otrzymamy
Linia 580: Linia 594:
<center><math>
<center><math>


\neg \neg( \neg p \wedge \neg q) \equiv\neg(  p \vee    q).
\neg \neg( \neg p \wedge \neg q) \equiv\neg(  p \vee    q)</math></center>
</math></center>


:Stosując równoważność z pierwszego punktu do lewej strony otrzymamy szukaną równoważność.
:Stosując równoważność z pierwszego punktu do lewej strony otrzymamy szukaną równoważność.
Linia 591: Linia 604:
Sprawdź które z następujących formuł są tautologiami
Sprawdź które z następujących formuł są tautologiami


# <math>( (p \vee r)\wedge( q \vee \neg r) )\Rightarrow (p \vee q)</math>
# <math>( (p \vee r)\wedge( q \vee \neg r) )\Rightarrow (p \vee q)</math>,
# <math>(p \vee q) \Rightarrow ( (p \vee r)\wedge( q \vee \neg r)) </math>
# <math>(p \vee q) \Rightarrow ( (p \vee r)\wedge( q \vee \neg r))</math>,
# <math>( (p \wedge r)\vee( q \wedge \neg r) )\Rightarrow(p \wedge q)</math>
# <math>( (p \wedge r)\vee( q \wedge \neg r) )\Rightarrow(p \wedge q)</math>,
# <math>(p \wedge q) \Rightarrow ( (p \wedge r)\vee( q \wedge \neg r))</math>
# <math>(p \wedge q) \Rightarrow ( (p \wedge r)\vee( q \wedge \neg r))</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">  
<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. Spróbujmy znaleźć wartościowanie które falsyfikuje tą formułę. Skoro implikacja ma być fałszywa to formuła <math>(p \vee q)</math> (czyli następnik) musi być fałszywa. Tak jest tylko wtedy kiedy zarówno <math>\textnormal{p}</math> jak i <math>\textnormal{q}</math> są fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji, czyli formułą
:1. Spróbujmy znaleźć wartościowanie, które falsyfikuje tą formułę. Skoro implikacja ma być fałszywa, to formuła <math>(p \vee q)</math> (czyli następnik) musi być fałszywa. Tak jest tylko wtedy, kiedy zarówno <math>\text{p}</math> jak i <math>\text{q}</math> są fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji, czyli formułą


<center><math>
<center><math>


(p \vee r)\wedge( q \vee \neg r).
(p \vee r)\wedge( q \vee \neg r)</math></center>
</math></center>


:Jeśli teraz ustalimy <math>\textnormal{r}</math> na fałsz to <math>(p \vee q)</math> będzie fałszywe a jeśli ustalimy <math>r</math> na prawdę to <math>( q \vee \neg r)</math> będzie fałszywe. W obu tych przypadkach cały poprzednik jest fałszywy. Wynika stąd, że nie da się dobrać takiego wartościowania że poprzednik jest prawdziwy, a następnik fałszywy więc rozważana formuła jest tautologą.
:Jeśli teraz ustalimy <math>\text{r}</math> na fałsz, to <math>(p \vee q)</math> będzie fałszywe, a jeśli ustalimy <math>r</math> na prawdę to <math>( q \vee \neg r)</math> będzie fałszywe. W obu tych przypadkach cały poprzednik jest fałszywy. Wynika stąd, że nie da się dobrać takiego wartościowania, że poprzednik jest prawdziwy, a następnik fałszywy więc, rozważana formuła jest tautologą.


:2 Formuła nie jest tautologią. Wystarczy wartościować <math>\textnormal{p}</math> i <math>\textnormal{r}</math> na prawdę i <math>\textnormal{q}</math> na fałsz.
:2 Formuła nie jest tautologią. Wystarczy wartościować <math>\text{p}</math> i <math>\text{r}</math> na prawdę i <math>\text{q}</math> na fałsz.


:3. Formuła nie jest tautologią. Wystarczy wartościować <math>\textnormal{p}</math> i <math>\textnormal{r}</math> na prawdę i <math>\textnormal{q}</math> na fałsz.
:3. Formuła nie jest tautologią. Wystarczy wartościować <math>\text{p}</math> i <math>\text{r}</math> na prawdę i <math>\text{q}</math> na fałsz.


:4. Przykład rozwiązania przez rozważenie wszystkich możliwości
:4. Przykład rozwiązania przez rozważenie wszystkich możliwości
<center>
<center>
{| border="1"
{| border="1"
! <math>\textnormal{p}</math>!! <math>\textnormal{q}</math>!! <math>\textnormal{r}</math>!!<math>(\textnormal{p} \wedge \textnormal{q})</math>!! <math>( p \wedge r)</math>!! <math>( q \wedge \neg r)</math>!! <math>(p \wedge r) \vee (q \wedge \neg r)</math>!! <math>(p \wedge q) \Rightarrow ((p \wedge r) \vee (q \wedge \neg r))</math>
! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>(\text{p} \wedge \text{q})</math>!! <math>( p \wedge r)</math>!! <math>( q \wedge \neg r)</math>!! <math>(p \wedge r) \vee (q \wedge \neg r)</math>!! <math>(p \wedge q) \Rightarrow ((p \wedge r) \vee (q \wedge \neg r))</math>
|-
|-
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 0|| 0|| 0|| 0|| 1
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 0|| 0|| 0|| 0|| 1
Linia 633: Linia 645:
|}
|}
</center>
</center>
:W kolumnie odpowiadającej badanej formule są same '''1''', więc jest ona tautologią.
:W kolumnie odpowiadającej badanej formule, są same '''1''', więc jest ona tautologią.
</div></div>
</div></div>




Binarne spójniki logiczne interpretowaliśmy jako funkcje z <math>\mathbb{B}\times \mathbb{B} \rightarrow \mathbb{B}</math>. Nie trudno przekonać się że takich funkcji jest dokładnie '''16'''. Dla każdej takiej funkcji możemy dodać spójnik, który będzie interpretowany dokładnie jako ta funkcja. W poniższej tabeli zamieszczamy wszystkie takie funkcje wraz ze
Binarne spójniki logiczne interpretowaliśmy jako funkcje z <math>\mathbb{B}\times \mathbb{B} \rightarrow \mathbb{B}</math>. Nie trudno przekonać się, że takich funkcji jest dokładnie '''16'''. Dla każdej takiej funkcji możemy dodać spójnik, który będzie interpretowany dokładnie jako ta funkcja. W poniższej tabeli zamieszczamy wszystkie takie funkcje wraz ze
zwyczajowymi oznaczeniami odpowiadających im spójników.  
zwyczajowymi oznaczeniami odpowiadających im spójników.  


Linia 653: Linia 665:
| 2|| 0|| 0|| 1|| 0|| &nbsp;|| <math>\neg (p \Rightarrow q)</math>
| 2|| 0|| 0|| 1|| 0|| &nbsp;|| <math>\neg (p \Rightarrow q)</math>
|-
|-
| 3|| 0|| 0|| 1|| 1|| &nbsp;|| <math>\textnormal{p}</math>
| 3|| 0|| 0|| 1|| 1|| &nbsp;|| <math>\text{p}</math>
|-
|-
| 4|| 0|| 1|| 0|| 0|| &nbsp;|| <math>\neg (q \Rightarrow p)</math>
| 4|| 0|| 1|| 0|| 0|| &nbsp;|| <math>\neg (q \Rightarrow p)</math>
|-
|-
| 5|| 0|| 1|| 0|| 1|| &nbsp;|| <math>\textnormal{q}</math>
| 5|| 0|| 1|| 0|| 1|| &nbsp;|| <math>\text{q}</math>
|-
|-
| 6|| 0|| 1|| 1|| 0|| &nbsp;|| <math>XOR</math>
| 6|| 0|| 1|| 1|| 0|| &nbsp;|| <math>XOR</math>
Linia 680: Linia 692:
|}
|}
</center>
</center>
Spójnik binarny <math>\circ</math> będziemy nazywać ''przemiennym'' jeśli zachodzi
Spójnik binarny <math>\circ</math> będziemy nazywać ''przemiennym'', jeśli zachodzi
następująca równoważność
następująca równoważność


Linia 688: Linia 700:




{{cwiczenie|4.8||
<span id="cwiczenie_4_8">{{cwiczenie|4.8||


Sprawdź następujące równoważności
Sprawdź następujące równoważności
Linia 699: Linia 711:
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
: Powyższe równoważności wynikają natychmiast z porównania odpowiednich wierszy w tabeli definicji spójników.
: Powyższe równoważności wynikają natychmiast z porównania odpowiednich wierszy w tabeli definicji spójników.
</div></div>
</div></div></span>


{{cwiczenie|4.9||
{{cwiczenie|4.9||


Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.
Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  


Linia 723: Linia 735:
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  


:Dla przemienności spójnika <math>\circ</math> istotne jest aby <math> 1\circ 0 =  0 \circ 1</math>. Dla pozostałych przypadków wartościowań równoważnośc 4.3 jest zawsze spełniona. Każdy spójnik binarny możemy zdefiniować za pomocą tabelki kwadratowej, np. alternatywę zdefiniowaliśmy jako
:Dla przemienności spójnika <math>\circ</math> istotne jest aby <math>1\circ 0 =  0 \circ 1</math>. Dla pozostałych przypadków wartościowań równoważnośc 4.3 jest zawsze spełniona. Każdy spójnik binarny możemy zdefiniować za pomocą tabelki kwadratowej, np. alternatywę zdefiniowaliśmy jako
<center>
<center>
{| border="1" cellspacing="0"
{| border="1" cellspacing="0"
Linia 753: Linia 765:


</div></div>
</div></div>
}}
 


:Spójnik binarny <math>\circ</math> będziemy nazywać ''łącznym'' jeśli zachodzi
:Spójnik binarny <math>\circ</math> będziemy nazywać ''łącznym'' jeśli zachodzi
Linia 762: Linia 774:


Jeśli spójnik <math>\circ</math> jest łączny to dowolne dwie formuły, które są zbudowane
Jeśli spójnik <math>\circ</math> jest łączny to dowolne dwie formuły, które są zbudowane
jedynie ze spójników <math>\circ</math> są równoważne jeśli występuje w nich tyle samo spójników. Dlatego dla łącznych spójników binarnych pomija się często nawiasy.
jedynie ze spójników <math>\circ</math> są równoważne, jeśli występuje w nich tyle samo spójników. Dlatego dla łącznych spójników binarnych pomija się często nawiasy.


{{cwiczenie|4.10||
{{cwiczenie|4.10||
Linia 772: Linia 784:
# <math>\Leftrightarrow</math>
# <math>\Leftrightarrow</math>
# <math>XOR</math>
# <math>XOR</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">  
<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. Formuła <math>(p \vee q) \vee r</math> jest fałszywa jedynie wtedy gdy <math>\textnormal{p}</math>,<math>\textnormal{q}</math> i <math>\textnormal{r}</math> są wartościowane na fałsz. Tak samo jest dla formuły <math>p \vee( q \vee r )</math> więc są one równoważne.
:1. Formuła <math>(p \vee q) \vee r</math> jest fałszywa jedynie wtedy, gdy <math>\text{p}</math>,<math>\text{q}</math> i <math>\text{r}</math> są wartościowane na fałsz. Tak samo jest dla formuły <math>p \vee( q \vee r )</math>, więc są one równoważne.


:2. Formuła <math>(p \wedge q) \wedge r</math> jest prawdziwa jedynie wtedy gdy <math>\textnormal{p}</math>,<math>\textnormal{q}</math> i <math>\textnormal{r}</math> są wartościowane na prawdę. Tak samo jest dla formuły <math>p \wedge( q \wedge r )</math> więc są one równoważne.
:2. Formuła <math>(p \wedge q) \wedge r</math> jest prawdziwa jedynie wtedy, gdy <math>\text{p}</math>,<math>\text{q}</math> i <math>\text{r}</math> są wartościowane na prawdę. Tak samo jest dla formuły <math>p \wedge( q \wedge r )</math>, więc są one równoważne.


:3. Zbadamy równoważność formuł <math>(p \Leftrightarrow q) \Leftrightarrow r</math> i <math> p \Leftrightarrow(q \Leftrightarrow r)</math> za pomocą tabeli
:3. Zbadamy równoważność formuł <math>(p \Leftrightarrow q) \Leftrightarrow r</math> i <math>p \Leftrightarrow(q \Leftrightarrow r)</math> za pomocą tabeli
<center>
<center>
{| border="1"
{| border="1"
! <math>\textnormal{p}</math>!! <math>\textnormal{q}</math>!! <math>\textnormal{r}</math>!!<math>(p \leftrightarrow q)</math>!! <math>(p \leftrightarrow q) \leftrightarrow r</math>!! <math>(q \leftrightarrow r)</math>!! <math>p \leftrightarrow (q \leftrightarrow r)</math>
! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>(p \leftrightarrow q)</math>!! <math>(p \leftrightarrow q) \leftrightarrow r</math>!! <math>(q \leftrightarrow r)</math>!! <math>p \leftrightarrow (q \leftrightarrow r)</math>
|-
|-
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 1|| 0|| 1|| 0
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 1|| 0|| 1|| 0
Linia 801: Linia 813:
|}
|}
</center>
</center>
:Kolumna '''4''' i '''6''' są identyczne więc odpowiadające im formuły są równoważne. Spójnik <math>\Leftrightarrow</math> jest więc łączny.
:Kolumna '''4''' i '''6''' są identyczne, więc odpowiadające im formuły są równoważne. Spójnik <math>\Leftrightarrow</math> jest więc łączny.
 
:4.W  [[#cwiczenie_4_8|ćwiczeniu 4.8]] pokazaliśmy, że <math>x XOR y \equiv \neg (x \Leftrightarrow y)</math>. Łatwo zauważyć, że
 
<center><math>\neg a \Leftrightarrow b \equiv \neg (a\Leftrightarrow b) \equiv a \Leftrightarrow \neg b</math></center>
 
:Wynika to z faktu, że każda z powyższych formuł jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jedna z zmiennych jest wartościowana na 1. Wobec tego mamy
 
<center><math>\begin{align} p XOR (q XOR r)\equiv \\
    \neg (p \Leftrightarrow \neg (q\Leftrightarrow r))\equiv \\
    \neg \neg (p \Leftrightarrow (q\Leftrightarrow r)) \equiv \\
    \neg \neg ((p \Leftrightarrow q)\Leftrightarrow r) \equiv \\
    \neg (\neg (p \Leftrightarrow q)\Leftrightarrow r) \equiv \\
      (p XOR q) XOR r.
\end{align}</math></center>


:4. ...
:Pokazaliśmy więc, że spójnik <math>XOR</math> jest łączny.
</div></div>
</div></div>
}}
 


Możemy również rozważać spójniki '''3''' i więcej argumentowe. Spójnik <math>k</math>-argumetowy powinien odpowiadać funkcji <math>\mathbb{B}^k \rightarrow \mathbb{B}</math>.
Możemy również rozważać spójniki '''3''' i więcej argumentowe. Spójnik <math>k</math>-argumetowy powinien odpowiadać funkcji <math>\mathbb{B}^k \rightarrow \mathbb{B}</math>.
Linia 815: Linia 841:
<center>
<center>
{| border="1"
{| border="1"
! <math>\textnormal{p}</math>!! <math>\textnormal{q}</math>!! <math>\textnormal{r}</math>!!<math>\circ (p, q, r)</math>
! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>\circ (p, q, r)</math>
|-
|-
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;
Linia 835: Linia 861:
</center>
</center>


{{cwiczenie|4.11||
{{uwaga|4.1||


Udowodnij, że różnych spójników <math>k</math>-argumentowych jest dokładnie
Różnych spójników <math>k</math>-argumentowych jest dokładnie
<math>2^{2^k}</math>.
<math>2^{2^k}</math>.
; Solution.
}}
}}


Linia 851: Linia 875:
<center>
<center>
{| border="1"
{| border="1"
! <math>\textnormal{p}</math>!! <math>\textnormal{q}</math>!! <math>\textnormal{r}</math>!!<math>f_{p \rightarrow _(q \rightarrow r)}</math>
! <math>\text{p}</math>!! <math>\text{q}</math>!! <math>\text{r}</math>!!<math>f_{p \rightarrow _(q \rightarrow r)}</math>
|-
|-
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 1
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| 1
Linia 883: Linia 907:


{{dowod|||
{{dowod|||
Dla dowolnej funkcji boolowskiej skonstruujemy formułę która ją definiuje. Niech <math>\displaystyle k\in \nNat</math> oraz <math>\displaystyle f:\mathbb{B}^k \rightarrow \; \mathbb{B}</math>. W definiowanej formule będziemy używać zmiennych <math>\displaystyle p_1, \dots,p_k</math>, a każdy element <math>\displaystyle (w_1,\ldots,w_k) \in \mathbb{B}^k</math> będzie odpowiadał wartościowaniu <math>\displaystyle v_w</math> takiemu, że <math>\displaystyle v(p_i)=w_i</math>.
Dla dowolnej funkcji boolowskiej skonstruujemy formułę która ją definiuje. Niech <math>k\in \mathbb{N}</math> oraz <math>f:\mathbb{B}^k \rightarrow \; \mathbb{B}</math>. W definiowanej formule będziemy używać zmiennych <math>p_1, \dots,p_k</math>, a każdy element <math>(w_1,\ldots,w_k) \in \mathbb{B}^k</math> będzie odpowiadał wartościowaniu <math>v_w</math> takiemu, że <math>v(p_i)=w_i</math>.


Niech <math>\displaystyle F</math> będzie zbiorem tych argumentów, dla których funkcja <math>\displaystyle f</math> przyjmuje wartość 1. Dla dowolnego elementu <math>\displaystyle x_i \in F</math> skonstruujemy formułę <math>\displaystyle \phi_i</math> w taki sposób, aby była spełniona tylko dla wartościowania odpowiadającego elementowi <math>\displaystyle x_i</math>. Niech <math>\displaystyle x_i= (w_1,\dots,w_k)</math>, wtedy formułę <math>\displaystyle \phi_i</math> definiujemy jako <math>\displaystyle l^i_1 \wedge l^i_2 \wedge \dots \wedge l^i_k</math> gdzie
Niech <math>F</math> będzie zbiorem tych argumentów, dla których funkcja <math>f</math> przyjmuje wartość 1. Dla dowolnego elementu <math>x_i \in F</math> skonstruujemy formułę <math>\phi_i</math> w taki sposób, aby była spełniona tylko dla wartościowania odpowiadającego elementowi <math>x_i</math>. Niech <math>x_i= (w_1,\dots,w_k)</math>, wtedy formułę <math>\phi_i</math> definiujemy jako <math>l^i_1 \wedge l^i_2 \wedge \dots \wedge l^i_k</math> gdzie


<center><math>\displaystyle l^i_j \begin{cases}
<center><math>l^i_j \begin{cases}
p_j, & \mbox{gdy } w_j = 1 \displaystyle ;\\
p_j, & \mbox{gdy } w_j = 1 ;\\
\neg p_j, & \mbox{gdy } w_j = 0 \displaystyle .\end{cases}</math></center>
\neg p_j, & \mbox{gdy } w_j = 0 .\end{cases}</math></center>


Łatwo sprawdzić, że formuła <math>\displaystyle \phi_i</math> jest spełniona tylko dla wartościowania odpowiadającego elementowi <math>\displaystyle x_i</math>.
Łatwo sprawdzić, że formuła <math>\phi_i</math> jest spełniona tylko dla wartościowania odpowiadającego elementowi <math>x_i</math>.


Postępując w ten sposób dla każdego elementu zbioru <math>\displaystyle F</math> otrzymamy formuły <math>\displaystyle \phi_1, \dots \phi_m</math>. Biorąc
Postępując w ten sposób dla każdego elementu zbioru <math>F</math> otrzymamy formuły <math>\phi_1, \dots \phi_m</math>. Biorąc


<center><math>\displaystyle \phi_1 \vee \dots \vee \phi_m
<center><math>\phi_1 \vee \dots \vee \phi_m
</math></center>
</math></center>


otrzymamy formułę która definiuje funkcję <math>\displaystyle f</math>, oznaczmy ją przez <math>\displaystyle \Phi</math>. Jeśli dla wartościowania <math>\displaystyle v</math> formuła <math>\displaystyle \Phi</math> jest spełniona to znaczy, że któraś z formuł <math>\displaystyle \phi_i</math> jest spełniona. Oznacza to że wartościowanie <math>\displaystyle v</math> odpowiada pewnemu elementowi <math>\displaystyle x_i</math> zbioru <math>\displaystyle F</math>, wobec tego funkcja <math>\displaystyle f(x_i)=1</math>  co jest zgodne z tym, że spełniona jest <math>\displaystyle \Phi</math>. W drugą stronę załóżmy że dla pewnego elementu <math>\displaystyle a\in \mathbb{B}^k </math> mamy <math>\displaystyle f(a)=1</math>. Wobec tego <math>\displaystyle a\in F</math>. Wtedy <math>\displaystyle a</math> odpowiada pewnej formule <math>\displaystyle \phi_i</math>, która jest spełniona dla wartościowania odpowiadającego <math>\displaystyle a</math>. Wobec tego również cała formuła <math>\displaystyle \Phi</math> jest spełniona dla tego wartościowania (bo jeden z elementów alternatywy jest spełniony). Wynika stąd, że formuła <math>\displaystyle \Phi</math> definiuje funkcję <math>\displaystyle f</math>. Na koniec zauważmy jeszcze że jedynymi spójnikami występującymi w formule <math>\displaystyle \Phi</math> są <math>\displaystyle \neg, \vee, \wedge</math>.
otrzymamy formułę która definiuje funkcję <math>f</math>, oznaczmy ją przez <math>\Phi</math>. Jeśli dla wartościowania <math>v</math> formuła <math>\Phi</math> jest spełniona to znaczy, że któraś z formuł <math>\phi_i</math> jest spełniona. Oznacza to że wartościowanie <math>v</math> odpowiada pewnemu elementowi <math>x_i</math> zbioru <math>F</math>, wobec tego funkcja <math>f(x_i)=1</math>  co jest zgodne z tym, że spełniona jest <math>\Phi</math>. W drugą stronę załóżmy że dla pewnego elementu <math>a\in \mathbb{B}^k</math> mamy <math>f(a)=1</math>. Wobec tego <math>a\in F</math>. Wtedy <math>a</math> odpowiada pewnej formule <math>\phi_i</math>, która jest spełniona dla wartościowania odpowiadającego <math>a</math>. Wobec tego również cała formuła <math>\Phi</math> jest spełniona dla tego wartościowania (bo jeden z elementów alternatywy jest spełniony). Wynika stąd, że formuła <math>\Phi</math> definiuje funkcję <math>f</math>. Na koniec zauważmy jeszcze że jedynymi spójnikami występującymi w formule <math>\Phi</math> są <math>\neg, \vee, \wedge</math>.
}}
}}


Linia 907: Linia 931:


{{dowod|||
{{dowod|||
Aby pokazać, że <math>\displaystyle \{\wedge,  \neg\}</math> jest funkcjonalnie pełny wystarczy pokazać, że przy pomocy spójników <math>\displaystyle \{\wedge,  \neg\}</math> da się zdefiniować <math>\displaystyle \vee</math>. Wtedy funkcjonalną pełność otrzymamy z [[#twierdzenie_5_2|twierdzenia 5.2]]. W [[#cwiczenie_4_2|ćwiczeniu 4.2]] pokazaliśmy, że
Aby pokazać, że <math>\{\wedge,  \neg\}</math> jest funkcjonalnie pełny wystarczy pokazać, że przy pomocy spójników <math>\{\wedge,  \neg\}</math> da się zdefiniować <math>\vee</math>. Wtedy funkcjonalną pełność otrzymamy z [[#twierdzenie_5_2|twierdzenia 5.2]]. W [[#cwiczenie_4_2|ćwiczeniu 4.2]] pokazaliśmy, że


<center><math>\displaystyle \neg (x \vee y) = \neg x \wedge \neg y.
<center><math>\neg (x \vee y) = \neg x \wedge \neg y</math></center>
</math></center>


Wobec tego
Wobec tego


<center><math>\displaystyle x \vee y =\neg(\neg x \wedge \neg y)
<center><math>x \vee y =\neg(\neg x \wedge \neg y)
</math></center>
</math></center>


a więc zdefiniowaliśmy <math>\displaystyle \vee</math> przy pomocy <math>\displaystyle \neg, \wedge</math>.
a więc zdefiniowaliśmy <math>\vee</math> przy pomocy <math>\neg, \wedge</math>.


Analogicznie aby pokazać funkcjonalną pełność zbioru <math>\displaystyle \{\vee,  \neg\}</math> zdefiniujemy <math>\displaystyle \wedge</math> przy pomocy spójników <math>\displaystyle \vee,  \neg</math>. Z [[#cwiczenie_4_2|ćwiczenia 4.2]] mamy
Analogicznie aby pokazać funkcjonalną pełność zbioru <math>\{\vee,  \neg\}</math> zdefiniujemy <math>\wedge</math> przy pomocy spójników <math>\vee,  \neg</math>. Z [[#cwiczenie_4_2|ćwiczenia 4.2]] mamy


<center><math>\displaystyle \neg(x \wedge y)= \neg x \vee \neg y
<center><math>\neg(x \wedge y)= \neg x \vee \neg y
</math></center>
</math></center>


a więc
a więc


<center><math>\displaystyle x \wedge y=\neg( \neg x \vee \neg y).
<center><math>x \wedge y=\neg( \neg x \vee \neg y)</math></center>
</math></center>


}}
}}
Linia 933: Linia 955:
{{cwiczenie|5.1||
{{cwiczenie|5.1||


Udowodnij, że zbiór <math>\displaystyle \{\Rightarrow,  \neg\}</math> jest funkcjonalnie pełny.
Udowodnij, że zbiór <math>\{\Rightarrow,  \neg\}</math> jest funkcjonalnie pełny.
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
W [[#cwiczenie_4_2|ćwiczeniu 4.2]] pokazaliśmy, że
W [[#cwiczenie_4_2|ćwiczeniu 4.2]] pokazaliśmy, że
      
      
<center><math>\displaystyle p\Rightarrow q \equiv \neg p \vee q,
<center><math>p\Rightarrow q \equiv \neg p \vee q,
    </math></center>
</math></center>


wobec tego
wobec tego
      
      
<center><math>\displaystyle (\neg  p)\Rightarrow q  \equiv \neg \vee q.
<center><math>(\neg  p)\Rightarrow q  \equiv \neg \vee q.
    </math></center>
</math></center>


Udało nam się więc zdefiniować alternatywę za pomocą dostępnych spójników, wobec czego zgodnie z [[#twierdzenie_5_3|twierdzeniem 5.3]] możemy również zdefiniować wszystkie inne funkcje boolowskie. Wynika stąd, że zbiór <math>\displaystyle \{\Rightarrow,  \neg\}</math> jest funkcjonalnie pełny.
Udało nam się więc zdefiniować alternatywę za pomocą dostępnych spójników, wobec czego zgodnie z [[#twierdzenie_5_3|twierdzeniem 5.3]] możemy również zdefiniować wszystkie inne funkcje boolowskie. Wynika stąd, że zbiór <math>\{\Rightarrow,  \neg\}</math> jest funkcjonalnie pełny.
</div></div>
</div></div>
}}
 


<span id="twierdzenie_5_4">{{twierdzenie|5.4||
<span id="twierdzenie_5_4">{{twierdzenie|5.4||
Linia 956: Linia 978:


{{dowod|||
{{dowod|||
Pokażemy, że przy pomocy <math>\displaystyle NOR</math> można zdefiniować <math>\displaystyle \neg</math> oraz <math>\displaystyle \vee</math>. Wtedy z twierdzenia [[#twierdzenie_5_3|twierdzenia 5.3]] otrzymamy tezę twierdzenia.
Pokażemy, że przy pomocy <math>NOR</math> można zdefiniować <math>\neg</math> oraz <math>\vee</math>. Wtedy z twierdzenia [[#twierdzenie_5_3|twierdzenia 5.3]] otrzymamy tezę twierdzenia.


Łatwo sprawdzić, że
Łatwo sprawdzić, że
      
      
<center><math>\displaystyle p NOR p \equiv \neg.
<center><math>p NOR p \equiv \neg</math></center>
</math></center>


Wiemy, że
Wiemy, że
      
      
<center><math>\displaystyle p NOR q \equiv \neg (p\vee q).
<center><math>p NOR q \equiv \neg (p\vee q)</math></center>
</math></center>


Wobec tego mamy również
Wobec tego mamy również
      
      
<center><math>\displaystyle \neg(p NOR q) \equiv p\vee q.
<center><math>\neg(p NOR q) \equiv p\vee q</math></center>
</math></center>


Możemy teraz wyrazić negację za pomocą <math>\displaystyle NOR</math>, otrzymamy wtedy
Możemy teraz wyrazić negację za pomocą <math>NOR</math>, otrzymamy wtedy
      
      
<center><math>\displaystyle (p NOR q) NOR (p NOR q) \equiv p\vee q.
<center><math>(p NOR q) NOR (p NOR q) \equiv p\vee q</math></center>
</math></center>
}}
}}


{{cwiczenie|5.2||
{{cwiczenie|5.2||
Udowodnij, że zbiór <math>\displaystyle \{NAND\}</math> jest funkcjonalnie pełny.
Udowodnij, że zbiór <math>\{NAND\}</math> jest funkcjonalnie pełny.
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
Analogicznie do dowodu w [[#twierdzenie_5_4|twierdzeniu 5.4]] pokażemy, że przy pomocy <math>\displaystyle NAND</math> można zdefiniować <math>\displaystyle \neg</math> oraz <math>\displaystyle \wedge</math>. Wtedy z [[#twierdzenie_5_3|twierdzenia 5.3]] otrzymamy, że zbiór <math>\displaystyle \{NAND\}</math> jest funkcjonalnie pełny.
Analogicznie do dowodu w [[#twierdzenie_5_4|twierdzeniu 5.4]] pokażemy, że przy pomocy <math>NAND</math> można zdefiniować <math>\neg</math> oraz <math>\wedge</math>. Wtedy z [[#twierdzenie_5_3|twierdzenia 5.3]] otrzymamy, że zbiór <math>\{NAND\}</math> jest funkcjonalnie pełny.


Z definicji spójnika <math>\displaystyle NAND</math> [[#definicja_4_6|4.6]] łatwo wynika, że
Z definicji spójnika <math>NAND</math> [[#definicja_4_6|4.6]] łatwo wynika, że
      
      
<center><math>\displaystyle p NAND p \equiv \neg p.
<center><math>p NAND p \equiv \neg p</math></center>
</math></center>


W [[#cwiczenie_4_2|ćwiczeniu 4.2]] pokazaliśmy, że
W [[#cwiczenie_4_2|ćwiczeniu 4.2]] pokazaliśmy, że
      
      
<center><math>\displaystyle p NAND q \equiv \neg (p \wedge q).
<center><math>p NAND q \equiv \neg (p \wedge q)</math></center>
</math></center>


Wobec tego
Wobec tego
      
      
<center><math>\displaystyle \neg p NAND q\equiv  p \wedge q.
<center><math>\neg p NAND q\equiv  p \wedge q</math></center>
</math></center>


i po zapisaniu <math>\displaystyle \neg</math> za pomocą <math>\displaystyle NAND</math> otrzymujemy
i po zapisaniu <math>\neg</math> za pomocą <math>NAND</math> otrzymujemy
      
      
<center><math>\displaystyle (p NAND q) NAND (p NAND q) \equiv p\wedge q
<center><math>(p NAND q) NAND (p NAND q) \equiv p\wedge q
</math></center>
</math></center>
</div></div>
</div></div>
}}
 


{{cwiczenie|5.3||
{{cwiczenie|5.3||


Zdefiniuj alternatywę przy pomocy samej implikacji.
Zdefiniuj alternatywę przy pomocy samej implikacji.
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  


Łatwo sprawdzić że formuła <math>p \Rightarrow (p \Rightarrow q)</math> jest równoważna formule <math>p\vee q</math>.
Łatwo sprawdzić, że formuła <math>(p \Rightarrow q) \Rightarrow q</math> jest równoważna formule <math>p\vee q</math>.
</div></div>
</div></div>
}}
}}
Linia 1019: Linia 1034:
{{cwiczenie|5.4||
{{cwiczenie|5.4||
Jakie funkcje binarne da się zdefiniować przy pomocy samej implikacji?
Jakie funkcje binarne da się zdefiniować przy pomocy samej implikacji?
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">     
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">     
Rozważmy po kolei najmniejsze formuły zbudowane z dwóch zmiennych <math>\displaystyle p</math> i <math>\displaystyle q</math>.
Rozważmy po kolei najmniejsze formuły zbudowane z dwóch zmiennych <math>p</math> i <math>q</math>.
Formuły <math>\displaystyle p</math> oraz <math>\displaystyle q</math> definiują funkcje binarne będące rzutowaniami, które oznaczymy przez <math>\displaystyle f_p</math> oraz <math>\displaystyle f_q</math>. Kolejne formuły to <math>\displaystyle p \Rightarrow p</math>, <math>\displaystyle q \Rightarrow q</math>, obydwie one są tautologiami, więc definiują  funkcję stale równą 1, którą oznaczymy przez  <math>\displaystyle f_T</math>. Kolejne <math>\displaystyle p\Rightarrow q</math> oraz <math>\displaystyle q\Rightarrow p</math> definiują funkcje które oznaczymy przez <math>\displaystyle f_{p \Rightarrow q}, f_{p\Rightarrow q}</math>. Wśród formuł o trzech spójnikach znajdziemy formuły opisujące funkcję <math>\displaystyle f_{p \vee q}</math>, zgodnie z poprzednim ćwiczeniem są to formuły <math>\displaystyle p \Rightarrow (p \Rightarrow q)</math> oraz <math>\displaystyle q \Rightarrow (q \Rightarrow p)</math>. Dociekliwi mogą sprawdzić, że każda z pozostałych formuł o trzech spójnikach definiuje którąś z funkcji opisanych wcześniej. Pokażemy teraz, że każda funkcja zdefiniowana przy pomocy implikacji jest którąś funkcji <math>\displaystyle f_p,f_q,f_T,f_{p \Rightarrow q},f_{q \Rightarrow p}, f_{p\vee q}</math>. Zbiór tych funkcji oznaczymy przez <math>\displaystyle F_\Rightarrow</math>. Pokażemy teraz, że przy pomocy implikacji można zdefiniować co najwyżej 7 różnych funkcji binarnych. Zaczniemy od prostej obserwacji, że każda formuła zbudowana jedynie z implikacji przyjmuje wartość 1, jeśli zmienne są wartościowane na 1. Pokażemy nawet więcej.
Formuły <math>p</math> oraz <math>q</math> definiują funkcje binarne będące rzutowaniami, które oznaczymy przez <math>f_p</math> oraz <math>f_q</math>. Kolejne formuły to <math>p \Rightarrow p</math>, <math>q \Rightarrow q</math>, obydwie one są tautologiami, więc definiują  funkcję stale równą 1, którą oznaczymy przez  <math>f_T</math>. Kolejne <math>p\Rightarrow q</math> oraz <math>q\Rightarrow p</math> definiują funkcje które oznaczymy przez <math>f_{p \Rightarrow q}, f_{p\Rightarrow q}</math>. Wśród formuł o trzech spójnikach znajdziemy formuły opisujące funkcję <math>f_{p \vee q}</math>, zgodnie z poprzednim ćwiczeniem są to formuły <math>(p \Rightarrow q) \Rightarrow q)</math> oraz <math>(q \Rightarrow p) \Rightarrow p)</math>. Dociekliwi mogą sprawdzić, że każda z pozostałych formuł o trzech spójnikach definiuje którąś z funkcji opisanych wcześniej. Pokażemy teraz, że każda funkcja zdefiniowana przy pomocy implikacji jest którąś funkcji <math>f_p,f_q,f_T,f_{p \Rightarrow q},f_{q \Rightarrow p}, f_{p\vee q}</math>. Zbiór tych funkcji oznaczymy przez <math>F_\Rightarrow</math>. Pokażemy teraz, że przy pomocy implikacji można zdefiniować co najwyżej 6 różnych funkcji binarnych. Zaczniemy od prostej obserwacji, że każda formuła zbudowana jedynie z implikacji przyjmuje wartość 1, jeśli zmienne są wartościowane na 1. Pokażemy nawet więcej.


Niech <math>\displaystyle \Phi</math> będzie dowolną formułą o zmiennych <math>\displaystyle p,q</math> zbudowaną jedynie przy pomocy spójnika <math>\displaystyle \Rightarrow</math>. Jeśli <math>\displaystyle p</math> jest ostatnią zmienną występującą w <math>\displaystyle \Phi</math> to każde wartościowanie które wartościuje <math>\displaystyle p</math> na 1 wartościuje również <math>\displaystyle \Phi</math> na 1. Przeprowadzimy dowód indukcyjny ze względu na ilość wystąpień spójnika <math>\displaystyle \Rightarrow</math>.
Niech <math>\Phi</math> będzie dowolną formułą o zmiennych <math>p,q</math> zbudowaną jedynie przy pomocy spójnika <math>\Rightarrow</math>. Jeśli <math>p</math> jest ostatnią zmienną występującą w <math>\Phi</math> to każde wartościowanie które wartościuje <math>p</math> na 1 wartościuje również <math>\Phi</math> na 1. Przeprowadzimy dowód indukcyjny ze względu na ilość wystąpień spójnika <math>\Rightarrow</math>.
# Baza indukcji. Jeśli <math>\displaystyle \Rightarrow</math> ma zero wystąpień to jedyną formułą w której ostatnią zmienną jest <math>\displaystyle p</math> jest formuła <math>\displaystyle p</math>. Badana własność jest oczywiście spełniona.
# Baza indukcji. Jeśli <math>\Rightarrow</math> ma zero wystąpień to jedyną formułą w której ostatnią zmienną jest <math>p</math> jest formuła <math>p</math>. Badana własność jest oczywiście spełniona.
# Krok indukcyjny. Niech <math>\displaystyle n\in \nNat</math> takie, że <math>\displaystyle n>0</math>. Przypuśćmy, że wszystkie formuły o mniejszej liczbie spójników od <math>\displaystyle n</math> mają żądaną własność. Weźmy dowolną formułę <math>\displaystyle \Phi</math> o <math>\displaystyle n</math> spójnikach, w której ostatnią występującą zmienną jest <math>\displaystyle p</math>. Ponieważ <math>\displaystyle n>0</math> to <math>\displaystyle \Phi</math> jest postaci <math>\displaystyle \phi \Rightarrow \psi</math>. Ponieważ <math>\displaystyle p</math> jest również ostatnią zmienną w <math>\displaystyle \psi</math> oraz w <math>\displaystyle \psi</math> jest mniej niż <math>\displaystyle n</math> spójników to z założenia indukcyjnego każde wartościowanie, które wartościuje <math>\displaystyle p</math> na 1, wartościuje również <math>\displaystyle \psi</math> na 1. Z [[#tabela_4_1|tabeli 4.1]] wynika, że również formuła <math>\displaystyle \phi \Rightarrow \psi</math> jest wtedy wartościowana na 1, a więc posiada badaną własność. Wobec dowolności wybory <math>\displaystyle \Phi</math> wszystkie formuły o <math>\displaystyle n</math> spójnikach posiadają badaną własność.
# Krok indukcyjny. Niech <math>n\in \mathbb{N}</math> takie, że <math>n>0</math>. Przypuśćmy, że wszystkie formuły o mniejszej liczbie spójników od <math>n</math> mają żądaną własność. Weźmy dowolną formułę <math>\Phi</math> o <math>n</math> spójnikach, w której ostatnią występującą zmienną jest <math>p</math>. Ponieważ <math>n>0</math> to <math>\Phi</math> jest postaci <math>\phi \Rightarrow \psi</math>. Ponieważ <math>p</math> jest również ostatnią zmienną w <math>\psi</math> oraz w <math>\psi</math> jest mniej niż <math>n</math> spójników to z założenia indukcyjnego każde wartościowanie, które wartościuje <math>p</math> na 1, wartościuje również <math>\psi</math> na 1. Z [[#tabela_4_1|tabeli 4.1]] wynika, że również formuła <math>\phi \Rightarrow \psi</math> jest wtedy wartościowana na 1, a więc posiada badaną własność. Wobec dowolności wybory <math>\Phi</math> wszystkie formuły o <math>n</math> spójnikach posiadają badaną własność.
   
   
Analogiczny dowód dla zmiennej <math>\displaystyle q</math> pomijamy. Wiemy teraz że jeśli formuła zbudowana jedynie z implikacji kończy się jakąś zmienną to wartościowania tej zmiennej na 1 wartościuje całą formułę na 1. Dla tabeli funkcji binarnej oznacza to, że ostatni wiersz lub ostatnia kolumna są stale równe 1. Nietrudno sprawdzić, że tabeli o takiej własności jest dokładnie 6. Wobec tego przy pomocy implikacji nie da się zdefiniować więcej niż 6 funkcji binarnych. Oznacza to, że funkcje <math>\displaystyle f_p,f_q,f_T,f_{p \Rightarrow q},f_{q \Rightarrow p}, f_{p\vee q}</math> są wszystkimi funkcjami binarnymi, które da się zdefiniować przy pomocy samej implikacji.
Analogiczny dowód dla zmiennej <math>q</math> pomijamy. Wiemy teraz że jeśli formuła zbudowana jedynie z implikacji kończy się jakąś zmienną to wartościowania tej zmiennej na 1 wartościuje całą formułę na 1. Dla tabeli funkcji binarnej oznacza to, że ostatni wiersz lub ostatnia kolumna są stale równe 1. Nietrudno sprawdzić, że tabeli o takiej własności jest dokładnie 6. Wobec tego przy pomocy implikacji nie da się zdefiniować więcej niż 6 funkcji binarnych. Oznacza to, że funkcje <math>f_p,f_q,f_T,f_{p \Rightarrow q},f_{q \Rightarrow p}, f_{p\vee q}</math> są wszystkimi funkcjami binarnymi, które da się zdefiniować przy pomocy samej implikacji.
</div></div>
</div></div>
}}


{{cwiczenie|5.5||
{{cwiczenie|5.5||
Linia 1040: Linia 1055:
# <math>\{\Leftrightarrow\}</math>
# <math>\{\Leftrightarrow\}</math>
# <math>\{XOR\}</math>
# <math>\{XOR\}</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">  
<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. Oznaczmy zbiór formuł w których jedynym spójnikiem jest <math>\wedge</math> przez <math>F_\wedge</math>. Udowodnimy, że każda formuła z <math>F_\wedge</math> przyjmuje zawsze wartość '''1''', jeśli jej zmienne są wartościowane na '''1'''. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika <math>\wedge</math> w formule. Dowód będzie indukcyjny ze względu na rozmiar formuły.
:1. Oznaczmy zbiór formuł w których jedynym spójnikiem jest <math>\wedge</math> przez <math>F_\wedge</math>. Udowodnimy, że każda formuła z <math>F_\wedge</math> przyjmuje zawsze wartość '''1''', jeśli jej zmienne są wartościowane na '''1'''. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika <math>\wedge</math> w formule. Dowód będzie indukcyjny ze względu na rozmiar formuły.
:Baza indukcji: Każda formuła z <math>F_\wedge</math> o rozmiarze '''0''' jest postaci <math>\textnormal{x}</math>, gdzie <math>\textnormal{x}</math> jest zmienną. Wobec tego przy wartościowaniu zmiennych na '''1''' formuła <math>\textnormal{x}</math> też jest wartościowana na '''1'''. A więc każda formuła o rozmiarze '''0''' ma postulowaną własność.
:Baza indukcji: Każda formuła z <math>F_\wedge</math> o rozmiarze '''0''' jest postaci <math>\text{x}</math>, gdzie <math>\text{x}</math> jest zmienną. Wobec tego przy wartościowaniu zmiennych na '''1''' formuła <math>\text{x}</math> też jest wartościowana na '''1'''. A więc każda formuła o rozmiarze '''0''' ma postulowaną własność.
:Krok indukcyjny: Ustalmy dowolne <math>n>0</math> i przyjmijmy, że wszystkie formuły o mniejszym rozmiarze mają postulowaną własność. Niech <math>\nu</math> będzie dowolną formułą z <math>F_\wedge</math> o rozmiarze <math>\textnormal{n}</math>. Skoro <math>n>1</math> to <math>\nu</math> musi być postaci <math>\phi\wedge \psi</math>. Rozważmy wartościowanie które wszyskim zmiennym przypisuje wartość '''1'''. Ponieważ rozmiary <math>{\phi}</math> oraz <math>{\psi}</math> są silnie mniejsze od <math>\textnormal{n}</math> to z założenia indukcyjnego otrzymujemy, że dla naszego wartościowania obie przyjmują wartość '''1'''. Wobec tego zgodnie z tabelą 4.2 cała formuła <math>\phi\wedge \psi</math> też przyjmuje wartość '''1'''. Dowiedliśmy więc, że każda formuła o rozmiarze <math>\textnormal{n}</math> ma postulowaną własność.
:Krok indukcyjny: Ustalmy dowolne <math>n>0</math> i przyjmijmy, że wszystkie formuły o mniejszym rozmiarze mają postulowaną własność. Niech <math>\nu</math> będzie dowolną formułą z <math>F_\wedge</math> o rozmiarze <math>\text{n}</math>. Skoro <math>n>1</math> to <math>\nu</math> musi być postaci <math>\phi\wedge \psi</math>. Rozważmy wartościowanie które wszyskim zmiennym przypisuje wartość '''1'''. Ponieważ rozmiary <math>{\phi}</math> oraz <math>{\psi}</math> są silnie mniejsze od <math>\text{n}</math> to z założenia indukcyjnego otrzymujemy, że dla naszego wartościowania obie przyjmują wartość '''1'''. Wobec tego zgodnie z tabelą 4.2 cała formuła <math>\phi\wedge \psi</math> też przyjmuje wartość '''1'''. Dowiedliśmy więc, że każda formuła o rozmiarze <math>\text{n}</math> ma postulowaną własność.
:Wiemy już że każda <math>F_\wedge</math> przyjmuje zawsze wartość '''1''', jeśli jej zmienne są wartościowane na '''1'''. Wobec tego niemożliwe jest zdefiniowanie np. spójnika <math>F</math> gdyż definująca go formuła musiałby przyjąć wartość '''0''' na takim wartościowaniu.
:Wiemy już że każda <math>F_\wedge</math> przyjmuje zawsze wartość '''1''', jeśli jej zmienne są wartościowane na '''1'''. Wobec tego niemożliwe jest zdefiniowanie np. spójnika <math>F</math> gdyż definująca go formuła musiałby przyjąć wartość '''0''' na takim wartościowaniu.


:2. Dowód analogiczny do poprzedniego.
:2. Dowód analogiczny do poprzedniego.
</div></div>
</div></div>
}}
 


{{cwiczenie|5.6||
{{cwiczenie|5.6||


Czy funkcje binarne zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki muszą być przemienne?
Czy funkcje binarne, zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki, muszą być przemienne?
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  
Przyjrzyj się formułom zbudowanym z <math>\Leftrightarrow</math>
Przyjrzyj się formułom zbudowanym z <math>\Leftrightarrow</math>
</div></div>
</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">
Spójnik <math>\Leftrightarrow</math> jest przemienny. Rozważmy formułę <math>x\Leftrightarrow  x \Leftrightarrow y</math>. Łatwo zauważyć, że definiuje ona funkcję <math>f(x,y)=y</math>, która nie jest przemienna.
</div></div>
 


{{cwiczenie|5.7||
{{cwiczenie|5.7||


(z wykładu prof. P.M.Idziaka) Niech <math>F_n</math> oznacza ilość boolowskich funkcji <math>\textnormal{n}</math> argumetnowych, a <math>P_n</math> ilość boolowskich funkcji <math>\textnormal{n}</math> argumentowych, takich że przy pomocy każdej z nich da się zdefiniować dowolną funkcję boolowską (czyli jeśli <math>\circ</math> jest takim spójnikiem to zbiór <math>\{\circ\}</math> jest funkcjonalnie pełny). Udowdnij istenienie poniższej granicy i wyznacz jej wartość
(z wykładu prof. P.M.Idziaka) Niech <math>F_n</math> oznacza ilość boolowskich funkcji <math>\text{n}</math> argumetnowych, a <math>P_n</math> ilość boolowskich funkcji <math>\text{n}</math> argumentowych, takich że przy pomocy każdej z nich da się zdefiniować dowolną funkcję boolowską (czyli jeśli <math>\circ</math> jest takim spójnikiem to zbiór <math>\{\circ\}</math> jest funkcjonalnie pełny). Udowdnij istenienie poniższej granicy i wyznacz jej wartość


<center><math>
<center><math>
Linia 1069: Linia 1087:
\lim_{n \rightarrow \infty} \frac{P_n}{F_n}
\lim_{n \rightarrow \infty} \frac{P_n}{F_n}
</math></center>
</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">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
: Ustalmy dowolne <math>\displaystyle n>1</math>. Niech <math>\displaystyle \circ</math> będzie spójnikiem <math>\displaystyle n</math> argumentowym takim, że zbiór <math>\displaystyle \{\circ\}</math> jest funkcjonalnie pełny. Zastanówmy się jaką funkcję unarną definiuje formuła <math>\displaystyle \circ(x, \dots, x)</math>. Funkcja ta nie może na samych 1 dawać wartości 1, gdyż wtedy każda formuła unarna poza formułą <math>\displaystyle x</math> zbudowana z <math>\displaystyle \circ</math> byłaby stale równa 1 (indukcyjny dowód pomijamy), a więc nie dałoby się zdefiniować <math>\displaystyle \neg</math> przyp pomocy <math>\displaystyle \circ</math>. Z tych samych przyczyn formuła <math>\displaystyle \circ(x, \dots, x)</math> na samych 0 nie może przyjmować wartości 0. Wynika stąd, że konieczne jest aby  
: Ustalmy dowolne <math>n>1</math>. Niech <math>\circ</math> będzie spójnikiem <math>n</math> argumentowym takim, że zbiór <math>\{\circ\}</math> jest funkcjonalnie pełny. Zastanówmy się jaką funkcję unarną definiuje formuła <math>\circ(x, \dots, x)</math>. Funkcja ta nie może na samych 1 dawać wartości 1, gdyż wtedy każda formuła unarna poza formułą <math>x</math> zbudowana z <math>\circ</math> byłaby stale równa 1 (indukcyjny dowód pomijamy), a więc nie dałoby się zdefiniować <math>\neg</math> przyp pomocy <math>\circ</math>. Z tych samych przyczyn formuła <math>\circ(x, \dots, x)</math> na samych 0 nie może przyjmować wartości 0. Wynika stąd, że konieczne jest aby  


<center><math>\displaystyle
<center><math>
     \circ(x, \dots ,x) \equiv \neg x. \quad \mbox{(5.1)}
     \circ(x, \dots ,x) \equiv \neg x. \quad \mbox{(5.1)}
</math></center>
</math></center>


: Łatwo zauważyć, że <math>\displaystyle n-argumentowych</math> spójników spełniających powyższą równoważność jest dokładnie <math>\displaystyle 2^{2^{n}-2}</math> (równoważność ta ustala wartość funkcji na dwóch wartościowaniach). Skoro wszystkie spójniki które są funkcjonalnie pełne mają powyższą własność to
: Łatwo zauważyć, że <math>n-argumentowych</math> spójników spełniających powyższą równoważność jest dokładnie <math>2^{2^{n}-2}</math> (równoważność ta ustala wartość funkcji na dwóch wartościowaniach). Skoro wszystkie spójniki które są funkcjonalnie pełne mają powyższą własność to


<center><math>\displaystyle P_n  \leq 2^{2^{n}-2}.
<center><math>P_n  \leq 2^{2^{n}-2}</math></center>
</math></center>


: Wynika stąd, że jeśli granica <math>\displaystyle \lim_{n \rightarrow \infty} \frac{P_n}{F_n}</math> istnieje to jest nie większa od <math>\displaystyle \frac{1}{4}</math>.
: Wynika stąd, że jeśli granica <math>\lim_{n \rightarrow \infty} \frac{P_n}{F_n}</math> istnieje to jest nie większa od <math>\frac{1}{4}</math>.


: Dla dowolnego <math>\displaystyle a\in \mathbb{B}</math> przez <math>\displaystyle \bar{a}</math> będziemy oznaczać element <math>\displaystyle 1-x</math> (czyli <math>\displaystyle \bar{0}=1</math> i <math>\displaystyle \bar{1}=0</math>). Notację tą w naturalny sposób rozszerzymy na elementy <math>\displaystyle \mathbb{B}^n</math>. Czyli dla <math>\displaystyle x=(x_1,\dots,x_n) \in \mathbb{B}^n</math> mamy <math>\displaystyle \bar{x}= \overline{(x_1,\dots,x_n)}= (\bar{x_1},\dots,\bar{x_n})</math>.
: Dla dowolnego <math>a\in \mathbb{B}</math> przez <math>\bar{a}</math> będziemy oznaczać element <math>1-x</math> (czyli <math>\bar{0}=1</math> i <math>\bar{1}=0</math>). Notację tą w naturalny sposób rozszerzymy na elementy <math>\mathbb{B}^n</math>. Czyli dla <math>x=(x_1,\dots,x_n) \in \mathbb{B}^n</math> mamy <math>\bar{x}= \overline{(x_1,\dots,x_n)}= (\bar{x_1},\dots,\bar{x_n})</math>.


: Pokażemy, że dowolny spójnik <math>\displaystyle n</math> argumentowy spełniający <math>\mbox{(5.1)}</math> pozwala zdefiniować wszystkie inne spójniki wtedy i tylko wtedy gdy istnieje <math>\displaystyle x\in \mathbb{B}^n</math> dla którego <math>\displaystyle \circ(\bar{x})= \circ(x)</math>. Niech <math>\displaystyle \circ</math> będzie spójnikiem <math>\displaystyle n</math> argumentowym spełniającym <math>\mbox{(5.1)}</math>.
: Pokażemy, że dowolny spójnik <math>n</math> argumentowy spełniający <math>\mbox{(5.1)}</math> pozwala zdefiniować wszystkie inne spójniki wtedy i tylko wtedy gdy istnieje <math>x\in \mathbb{B}^n</math> dla którego <math>\circ(\bar{x})= \circ(x)</math>. Niech <math>\circ</math> będzie spójnikiem <math>n</math> argumentowym spełniającym <math>\mbox{(5.1)}</math>.


: Zaczniemy od pokazania, że jeśli nie istnieje taki <math>\displaystyle x</math> to nie wszystkie funkcje da się zdefiniować przy pomocy <math>\displaystyle \circ</math>. W takim wypadku, dla każdego <math>\displaystyle x\in \mathbb{B}^n</math> mamy <math>\displaystyle \circ(\bar{x})= \overline{\circ(x)}</math>. Z ostatniej obserwacji wynika również, że dla dowolnej formuły <math>\displaystyle \phi</math> zbudowanej przy pomocy <math>\displaystyle \circ</math>, wartość <math>\displaystyle \phi</math> przy wartościowaniu odpowiadającym <math>\displaystyle x</math> jest równa wartości <math>\displaystyle \neg \phi</math> przy wartościowaniu odpowiadającym <math>\displaystyle \bar{x}</math> (prosty indukcyjny dowód tego faktu pomijamy). Oznacza to że zmiana wartościowania na "przeciwne" zmienia też wartość formuły na przeciwną. Wobec tego nie jest możliwe zdefiniowanie żadnej funkcji stałej przy pomocy <math>\displaystyle \circ</math>, a więc zbiór <math>\displaystyle \{\circ\}</math> nie jest funkcjonalnie pełny.
: Zaczniemy od pokazania, że jeśli nie istnieje taki <math>x</math> to nie wszystkie funkcje da się zdefiniować przy pomocy <math>\circ</math>. W takim wypadku, dla każdego <math>x\in \mathbb{B}^n</math> mamy <math>\circ(\bar{x})= \overline{\circ(x)}</math>. Z ostatniej obserwacji wynika również, że dla dowolnej formuły <math>\phi</math> zbudowanej przy pomocy <math>\circ</math>, wartość <math>\phi</math> przy wartościowaniu odpowiadającym <math>x</math> jest równa wartości <math>\neg \phi</math> przy wartościowaniu odpowiadającym <math>\bar{x}</math> (prosty indukcyjny dowód tego faktu pomijamy). Oznacza to że zmiana wartościowania na "przeciwne" zmienia też wartość formuły na przeciwną. Wobec tego nie jest możliwe zdefiniowanie żadnej funkcji stałej przy pomocy <math>\circ</math>, a więc zbiór <math>\{\circ\}</math> nie jest funkcjonalnie pełny.


: Pokażemy teraz, że jeśli istnieje przynajmniej jeden element <math>\displaystyle x\in \mathbb{B}^n</math> dla którego <math>\displaystyle \circ(x)=\circ(\bar{x})</math> to zbiór <math>\displaystyle \{\circ\}</math> jest funkcjonalnie pełny. Niech <math>\displaystyle x</math> będzie tym elementem. Zdefiniujemy formułę o dwóch zmiennych <math>\displaystyle p</math> oraz <math>\displaystyle q</math>. Nowa formuła będzie postaci
: Pokażemy teraz, że jeśli istnieje przynajmniej jeden element <math>x\in \mathbb{B}^n</math> dla którego <math>\circ(x)=\circ(\bar{x})</math> to zbiór <math>\{\circ\}</math> jest funkcjonalnie pełny. Niech <math>x</math> będzie tym elementem. Zdefiniujemy formułę o dwóch zmiennych <math>p</math> oraz <math>q</math>. Nowa formuła będzie postaci


<center><math>\displaystyle \phi=    \circ(v_1,\dots,v_n),
<center><math>\phi=    \circ(v_1,\dots,v_n)</math>,</center>
</math></center>


: gdzie <math>\displaystyle v_i</math> jest zmienną p jeśli <math>\displaystyle x_i</math> jest równe 1 i zmienną <math>\displaystyle q</math> w przeciwnym przypadku. Zobaczmy jaką funkcję binarną definiuje formuła <math>\displaystyle \phi</math>. Jeśli <math>\displaystyle p</math> oraz <math>\displaystyle q</math> są wartościowane na 0, to <math>\displaystyle \phi</math> jest wartościowane zgodnie z <math>\displaystyle \circ(0,\dots,0)</math> a więc na 1. Jeśli <math>\displaystyle p</math> oraz <math>\displaystyle q</math> są wartościowane na 1 <math>\displaystyle \phi</math> jest wartościowane zgodnie z <math>\displaystyle \circ(1,\dots,1)</math> a więc na 0. W pozostałych przypadkach wartościowanie odpowiada albo <math>\displaystyle x</math> albo <math>\displaystyle \bar{x}</math>, a funkcja <math>\displaystyle \phi</math> przyjmuje tą samą wartość, oznaczmy ją przez <math>\displaystyle c</math>. Podsumowując otrzymujemy
: gdzie <math>v_i</math> jest zmienną p jeśli <math>x_i</math> jest równe 1 i zmienną <math>q</math> w przeciwnym przypadku. Zobaczmy jaką funkcję binarną definiuje formuła <math>\phi</math>. Jeśli <math>p</math> oraz <math>q</math> są wartościowane na 0, to <math>\phi</math> jest wartościowane zgodnie z <math>\circ(0,\dots,0)</math> a więc na 1. Jeśli <math>p</math> oraz <math>q</math> są wartościowane na 1 <math>\phi</math> jest wartościowane zgodnie z <math>\circ(1,\dots,1)</math> a więc na 0. W pozostałych przypadkach wartościowanie odpowiada albo <math>x</math> albo <math>\bar{x}</math>, a funkcja <math>\phi</math> przyjmuje tą samą wartość, oznaczmy ją przez <math>c</math>. Podsumowując otrzymujemy


<center>
<center>
Linia 1101: Linia 1117:
! <math>\phi</math>!! 0!! 1!!
! <math>\phi</math>!! 0!! 1!!
|-
|-
| &nbsp;0&nbsp;|| &nbsp;1&nbsp;|| &nbsp;<math>\displaystyle c</math>&nbsp;
| &nbsp;0&nbsp;|| &nbsp;1&nbsp;|| &nbsp;<math>c</math>&nbsp;
|-
|-
| &nbsp;1&nbsp;|| &nbsp;<math>\displaystyle c</math>&nbsp;|| &nbsp;0&nbsp;
| &nbsp;1&nbsp;|| &nbsp;<math>c</math>&nbsp;|| &nbsp;0&nbsp;
|}
|}
</center>
</center>


: W zależności od wartości <math>\displaystyle c</math> formuła <math>\displaystyle \phi</math> definiuje funkcję <math>\displaystyle NAND</math> albo <math>\displaystyle NOR</math>. W obu tych przypadkach przy pomocy formuły <math>\displaystyle \phi</math> da się zdefiniować wszystkie funkcje boolowskie. Ponieważ <math>\displaystyle \circ</math> jest jedynym spójnikiem występującym w <math>\displaystyle \phi</math> to również zbiór <math>\displaystyle \{\circ\}</math> jest funkcjonalnie pełny.
: W zależności od wartości <math>c</math> formuła <math>\phi</math> definiuje funkcję <math>NAND</math> albo <math>NOR</math>. W obu tych przypadkach przy pomocy formuły <math>\phi</math> da się zdefiniować wszystkie funkcje boolowskie. Ponieważ <math>\circ</math> jest jedynym spójnikiem występującym w <math>\phi</math> to również zbiór <math>\{\circ\}</math> jest funkcjonalnie pełny.


: Po scharakteryzowaniu, które spójniki pozwalają zdefiniować wszystkie inne, pozostało jedynie oszacować ich liczbę. Wszystkich spójników <math>\displaystyle n</math> argumentowych  spełniających <math>\mbox{(5.1)}</math> jest <math>\displaystyle \frac{1}{4} \cdot 2^{2^n}</math>. Wszystkich spójników <math>\displaystyle n</math> argumentowych spełniających <math>\displaystyle \circ(\bar{x})= \overline{\circ(x)}</math> jest <math>\displaystyle 2^{2^{n-1}}</math> (z każdej pary przeciwnych wartościowań wybieramy jedno). Po odrzuceniu połowy funkcji które nie spełniają <math>\mbox{(5.1)}</math> otrzymujemy <math>\displaystyle \frac{1}{2} \cdot 2^{2^{n-1}}</math>. Wobec tego pozostaje dokładnie
: Po scharakteryzowaniu, które spójniki pozwalają zdefiniować wszystkie inne, pozostało jedynie oszacować ich liczbę. Wszystkich spójników <math>n</math> argumentowych  spełniających <math>\mbox{(5.1)}</math> jest <math>\frac{1}{4} \cdot 2^{2^n}</math>. Wszystkich spójników <math>n</math> argumentowych spełniających <math>\circ(\bar{x})= \overline{\circ(x)}</math> jest <math>2^{2^{n-1}}</math> (z każdej pary przeciwnych wartościowań wybieramy jedno). Po odrzuceniu połowy funkcji które nie spełniają <math>\mbox{(5.1)}</math> otrzymujemy <math>\frac{1}{2} \cdot 2^{2^{n-1}}</math>. Wobec tego pozostaje dokładnie


<center><math>\displaystyle \frac{1}{4} \cdot 2^{2^n} - \frac{1}{2} \cdot 2^{2^{n-1}}
<center><math>\frac{1}{4} \cdot 2^{2^n} - \frac{1}{2} \cdot 2^{2^{n-1}}
</math></center>
</math></center>


: funkcji które spełniają <math>\mbox{(5.1)}</math> oraz nie spełniają <math>\displaystyle \circ(\bar{x})= \overline{\circ(x)}</math>. Możemy teraz obliczyć granicę
: funkcji które spełniają <math>\mbox{(5.1)}</math> oraz nie spełniają <math>\circ(\bar{x})= \overline{\circ(x)}</math>. Możemy teraz obliczyć granicę


<center><math>\displaystyle \lim_{n \rightarrow \infty} \frac{    \frac{1}{4} \cdot 2^{2^n} - \frac{1}{2} \cdot 2^{2^{n-1}}}{2^{2^n}} = \lim_{n \rightarrow \infty} \frac{1}{4} (1- 2 \cdot \frac{1}{2^{2^{n-1}}})=\frac{1}{4}.
<center><math>\lim_{n \rightarrow \infty} \frac{    \frac{1}{4} \cdot 2^{2^n} - \frac{1}{2} \cdot 2^{2^{n-1}}}{2^{2^n}} = \lim_{n \rightarrow \infty} \frac{1}{4} (1- 2 \cdot \frac{1}{2^{2^{n-1}}})=\frac{1}{4}</math></center>
</math></center>
</div></div>
</div></div>
}}


==Postacie normalne==
==Postacie normalne==
Linia 1125: Linia 1139:
{{definicja|6.1||
{{definicja|6.1||


Literałem nazywamy formułę która jest zmienną zdaniową lub negacją zmiennej zdaniowej.
Literałem nazywamy formułę, która jest zmienną zdaniową lub negacją zmiennej zdaniowej.
}}
}}
Zauważmy, że formuła konstruowana w dowodzie twierdzenia 5.2 jest w pewnej standartowej postaci - formuła jest alternatywą formuł które są koniunkcjami literałów. Przypomnijmy, że dla <math>p \Rightarrow q</math> zbudujemy formułę
Zauważmy, że formuła konstruowana w dowodzie twierdzenia 5.2 jest w pewnej standartowej postaci - formuła jest alternatywą formuł, które są koniunkcjami literałów. Przypomnijmy, że dla <math>p \Rightarrow q</math> zbudujemy formułę


<center><math>
<center><math>


(p \wedge q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q).
(p \wedge q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q)</math></center>
</math></center>


{{definicja|6.2||
{{definicja|6.2||


Formuła jest w dyzjunktywnej postaci normalnej (DNF) jeśli jest alternatywą formuł które są koniunkcjami literałów. Czyli wtedy gdy jest postaci
Formuła jest w dyzjunktywnej postaci normalnej (DNF), jeśli jest alternatywą formuł które są koniunkcjami literałów. Czyli wtedy, gdy jest postaci


<center><math>
<center><math>
Linia 1152: Linia 1165:
dla pewnych literałów <math>l_l^i, \dots,l_k^i</math>
dla pewnych literałów <math>l_l^i, \dots,l_k^i</math>
}}
}}
<span id="twierdzenie_6_3">
{{twierdzenie|6.3||
{{twierdzenie|6.3||


Dla każedej formuły istnieje równoważna formuła w DNF.
Dla każdej formuły istnieje równoważna formuła w DNF.
}}
}}
 
</span>
{{dowod|||
{{dowod|||


Linia 1163: Linia 1177:
{{definicja|6.4||
{{definicja|6.4||


Formuła jest w koniunktywnej postaci normalnej (CNF) jeśli jest koniunkcją formuł które są
Formuła jest w koniunktywnej postaci normalnej (CNF), jeśli jest koniunkcją formuł które są
alternatywami literałów.
alternatywami literałów.
}}
}}
Linia 1172: Linia 1186:


{{dowod|||
{{dowod|||
Niech <math>\displaystyle \Phi</math> będzie dowolną formułą. Z twierdzenia ??[[##dnf|Uzupelnic dnf|]] wynika że dla formuły <math>\displaystyle \neg \Phi</math> istnieje dyzjunktywna postać normalna. Niech <math>\displaystyle \Psi</math> będzie taką formułą. Wtedy mamy
Niech <math>\Phi</math> będzie dowolną formułą. Z twierdzenia [[#twierdzenie_6_3|twierdzenia 6.3]] wynika, że dla formuły <math>\neg \Phi</math> istnieje dyzjunktywna postać normalna. Niech <math>\Psi</math> będzie taką formułą. Wtedy mamy


<center><math>\displaystyle \Phi \equiv \neg \Psi.
<center><math>\Phi \equiv \neg \Psi</math></center>
</math></center>


Stosując wielokrotnie prawa de'Morgana dla formuły <math>\displaystyle \neg \Psi</math> otrzymamy formułę w koniunktywnej postaci normalnej. Indukcyjny dowód tego faktu pomijamy.
Stosując wielokrotnie prawa de'Morgana dla formuły <math>\neg \Psi</math> otrzymamy formułę w koniunktywnej postaci normalnej. Indukcyjny dowód tego faktu pomijamy.
}}
}}


Linia 1183: Linia 1196:


Jak sprawdzić, czy formuła w CNF jest tautologią?
Jak sprawdzić, czy formuła w CNF jest tautologią?
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  


Linia 1193: Linia 1206:
</math></center>
</math></center>


:Aby była tautologią konieczne jest aby każda z formuł <math>\phi_i</math> była tautologią. Ponieważ każda z formuł <math>\phi_i</math> jest alternatywą literałów to jest tautologią jedynie wtedy jeśli istnieje taki literał który występuje w <math>\phi_i</math> zarówno pozytywnie (czyli jako zmienna) jak i negatywnie (czyli jako zanegowana zmienna).
:Aby była tautologią konieczne jest, aby każda z formuł <math>\phi_i</math> była tautologią. Ponieważ każda z formuł <math>\phi_i</math> jest alternatywą literałów to jest tautologią jedynie wtedy, gdy istnieje taki literał który występuje w <math>\phi_i</math> zarówno pozytywnie (czyli jako zmienna) jak i negatywnie (czyli jako zanegowana zmienna).
</div></div>
</div></div>
}}
 


{{cwiczenie|6.2||
{{cwiczenie|6.2||
Linia 1201: Linia 1214:
Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w CNF
Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w CNF


# <math>p \Leftrightarrow q</math>
# <math>p \Leftrightarrow q</math>,
# <math>p \Rightarrow (q \Rightarrow p)</math>
# <math>p \Rightarrow (q \Rightarrow p)</math>,
# <math>(p \Rightarrow q) \Rightarrow p</math>
# <math>(p \Rightarrow q) \Rightarrow p</math>,
# <math>(p \vee a \vee b) \wedge (\neg q \vee \neg a) \wedge(r \vee \neg b \vee \neg c) \wedge(c \vee p))</math>
# <math>(p \vee a \vee b) \wedge (\neg q \vee \neg a) \wedge(r \vee \neg b \vee \neg c) \wedge(c \vee p))</math>,
# <math>(p \wedge q) \vee (r \wedge s)</math>
# <math>(p \wedge q) \vee (r \wedge s)</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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
:# <math>\displaystyle \neg p \vee q</math>
:# <math>\neg p \vee q</math>
:# <math>\displaystyle \neg a \vee a</math>
:# <math>\neg a \vee a</math>
:# <math>\displaystyle p</math>
:# <math>p</math>
:# <math>\displaystyle (p\vee r) \wedge (p\vee s)\wedge (q \vee r) \wedge (q \vee s)</math>
:# <math>(p\vee r) \wedge (p\vee s)\wedge (q \vee r) \wedge (q \vee s)</math>
</div></div>
</div></div>


}}
 


===Spełnialność===
===Spełnialność===
Linia 1222: Linia 1235:
{{definicja|6.6||
{{definicja|6.6||


Formuła jest spełnialna jeśli istenieje takie wartościowanie które wartościuje tą formułę na '''1'''.
Formuła jest spełnialna, jeśli istenieje takie wartościowanie, które wartościuje tą formułę na '''1'''.


:Formuły spełnialne są w ścisłym związku z tautologiami.
:Formuły spełnialne są w ścisłym związku z tautologiami.
Linia 1228: Linia 1241:
{{twierdzenie|6.7||
{{twierdzenie|6.7||


Formuła <math>{\phi}</math> jest tautologią wtedy i tylko wtedy kiedy formuła <math>\neg \phi</math> nie jest spełnialna.
Formuła <math>{\phi}</math> jest tautologią wtedy i tylko wtedy, kiedy formuła <math>\neg \phi</math> nie jest spełnialna.
}}
}}


{{dowod|||
{{dowod|||


Przypuśćmy, że formuła <math>{\phi}</math> jest tautologią. Wtedy dla każdego wartościowania <math>\textnormal{v}</math> mamy <math>v(\phi)=1</math>. Stąd otrzymujemy że dla każdego wartościowania <math>\textnormal{v}</math> mamy <math>v(\neg \phi)=0</math>, a więc
Przypuśćmy, że formuła <math>{\phi}</math> jest tautologią. Wtedy dla każdego wartościowania <math>\text{v}</math> mamy <math>v(\phi)=1</math>. Stąd otrzymujemy, że dla każdego wartościowania <math>\text{v}</math> mamy <math>v(\neg \phi)=0</math>, a więc
nie istnieje wartościwanie, które spełnia <math>\neg \phi</math>, czyli formuła ta nie jest spełnialna.
nie istnieje wartościwanie, które spełnia <math>\neg \phi</math>, czyli formuła ta nie jest spełnialna.


Przypuśćmy, że formuła <math>\neg \phi</math> nie jest spełnialna, czyli nie istnieje wartościowanie <math>\textnormal{v}</math> takie, że <math>v(\neg \phi)=0</math>. Wynika stąd, że dla każdego wartościowania mamy <math>v(\phi)=1</math>, a więc <math>{\phi}</math> jest tautologią.
Przypuśćmy, że formuła <math>\neg \phi</math> nie jest spełnialna, czyli nie istnieje wartościowanie <math>\text{v}</math> takie, że <math>v(\neg \phi)=0</math>. Wynika stąd, że dla każdego wartościowania mamy <math>v(\phi)=1</math>, a więc <math>{\phi}</math> jest tautologią.
}}
}}


Linia 1245: Linia 1258:
# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee \neg p)</math>
# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee \neg p)</math>
# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee  p)</math>
# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee  p)</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">
<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">
:# Łatwo sprawdzić, że wartościowanie <math>\displaystyle v</math> takie, że <math>\displaystyle v(p)=0, v(q)=1, v(r)=1</math> spełnia pierwszą z formuł.
:# Łatwo sprawdzić, że wartościowanie <math>v</math> takie, że <math>v(p)=0, v(q)=1, v(r)=1</math> spełnia pierwszą z formuł.
:# Po zastąpieniu alternatyw implikacjami otrzymujemy
:# Po zastąpieniu alternatyw implikacjami otrzymujemy
<center><math>\displaystyle (\neg q \Rightarrow \neg  p)  \wedge (q \Rightarrow \neg r) \wedge (\neg p \Rightarrow q) \wedge (\neg r \Rightarrow \neg q).
<center><math>(\neg q \Rightarrow \neg  p)  \wedge (q \Rightarrow \neg r) \wedge (\neg p \Rightarrow q) \wedge (\neg r \Rightarrow \neg q)</math></center>  
</math></center>  
: Przypuśćmy teraz, że formuła ta jest spełnialna. Niech <math>v</math> będzie wartościowaniem spełniającym. Przypuśćmy, że <math>v(q)=0</math> wtedy ponieważ <math>v(\neg q \Rightarrow \neg  p)=1</math> to konieczne jest aby <math>v(p)=0</math>. Jednak wtedy ponieważ mamy <math>v(\neg p \Rightarrow q)=1</math>, to <math>v(q)=1</math>, a więc otrzymujemy sprzeczność. Przypuśćmy zatem, że <math>v(q)=1</math> wtedy ponieważ <math>v(q \Rightarrow \neg r)=1</math>, to <math>v(r)=0</math>. W takim przypadku jednak ponieważ <math>v(\neg r \Rightarrow \neg q)=0</math> otrzymujemy,  że <math>v(q)=0</math>, a więc znowu sprzeczność. Wynika stąd, że nie istnieje wartościowanie spełniające dla tej formuły.
: Przypuśćmy teraz że formuła ta jest spełnialna. Niech <math>\displaystyle v</math> będzie wartościowaniem spełniającym. Przypuśćmy, że <math>\displaystyle v(q)=0</math> wtedy ponieważ <math>\displaystyle v(\neg q \Rightarrow \neg  p)=1</math> to konieczne jest aby <math>\displaystyle v(p)=0</math>. Jednak wtedy ponieważ mamy <math>\displaystyle v(\neg p \Rightarrow q)=1</math> to <math>\displaystyle v(q)=1</math>, a więc otrzymujemy sprzeczność. Przypuśćmy zatem, że <math>\displaystyle v(q)=1</math> wtedy ponieważ <math>\displaystyle v(q \Rightarrow \neg r)=1</math> to <math>\displaystyle v(r)=0</math>. W takim przypadku jednak ponieważ <math>\displaystyle v(\neg r \Rightarrow \neg q)=0</math> otrzymujemy,  że <math>\displaystyle v(q)=0</math>, a więc znowu sprzeczność. Wynika stąd, że nie istnieje wartościowanie spełniające dla tej formuły.
</div></div>
</div></div>
}}


Formuły z powyższego zadania, poza tym że są w koniunktywnej postaci normalnej, to jeszcze występujące w nich klauzule mają dokładnie dwa literały. Problem spełnialności takich formuł jest nazywany w literaturze problemem 2SAT. Dla takich formuł  istnieją szybkie algorytmy pozwalające ocenić ich spełnialność. Dopuszczanie klauzul o długości 3, bardzo komplikuje problem. Do dziś nie wiadomo czy dla takich formuł istnieją szybkie algorytmy oceniające spełnialność. Więcej na ten temat można się dowiedzieć z wykładu '''<u>Teoria złożoności</u>'''.
 
Formuły z powyższego zadania, poza tym że są w koniunktywnej postaci normalnej, to jeszcze występujące w nich klauzule mają dokładnie dwa literały. Problem spełnialności takich formuł jest nazywany w literaturze problemem 2SAT. Dla takich formuł  istnieją szybkie algorytmy pozwalające ocenić ich spełnialność. Dopuszczanie klauzul o długości 3, bardzo komplikuje problem. Do dziś nie wiadomo czy dla takich formuł istnieją szybkie algorytmy oceniające spełnialność. Więcej na ten temat można się dowiedzieć z wykładu [[Złożoność obliczeniowa/Wykład 6: NP-zupełność jako narzędzie analizy problemu|Teoria złożoności]].


==Logika intuicjonistyczna==
==Logika intuicjonistyczna==


Niektórzy logicy mają wątpliwości co do tego czy powinniśmy przyjmować schemat dowodu nie wprost jako aksjomat. Poddanie w wątpliwość tego aksjomatu doprowadziło do powstnia tzw. logiki intuicjonistycznej. Ważnym powodem zajmowania się logiką intuicjonistyczną są jej zadziwiające
Niektórzy logicy mają wątpliwości co do tego, czy powinniśmy przyjmować schemat dowodu niewprost jako aksjomat. Poddanie w wątpliwość tego aksjomatu doprowadziło do powstnia tzw. logiki intuicjonistycznej. Ważnym powodem zajmowania się logiką intuicjonistyczną są jej zadziwiające
związki z teorią obliczeń (<u>'''izomorfizm Curry-Howard'''</u>).
związki z teorią obliczeń (patrz [[Logika dla informatyków| izomorfizm Curryego-Howarda]]).


Implikacyjny fragment logiki intuicjonistycznej, który będziemy oznaczać przez <math>I_\Rightarrow</math> to zbiór tych formuł które da się dowodnić przy pomocy reguły MP z aksjomatów S i K.
Implikacyjny fragment logiki intuicjonistycznej, który będziemy oznaczać przez <math>I_\Rightarrow</math> to zbiór tych formuł, które da się dowodnić przy pomocy reguły MP z aksjomatów S i K.


{{definicja|7.1||
{{definicja|7.1||
Linia 1268: Linia 1280:
Aksjomaty <math>I_\Rightarrow</math>
Aksjomaty <math>I_\Rightarrow</math>


# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana aksjomatem K)
# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana aksjomatem K),
# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana aksjomatem S)
# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow (\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana aksjomatem S).
}}
}}
W pełnej wersji logiki intucjonistycznej pojawiają się również aksjomaty dla spójników <math>\wedge, \vee</math> oraz <math>\neg</math>. Dla uproszczenia zajmiemy  się jedynie formułami w których jedynym spójnikiem jest implikacja. Dodatkowym argumentem uzasadniającym takie podejście jest fakt, że każde twierdzenie logiki intuicjonistycznej w którym jedynymi spójnikami są <math>\Rightarrow</math> da się udowodnić przy pomocy aksjomatów 7.1. Zobaczymy, że analogiczne twierdzenie nie jest prawdą dla logiki klasycznej. Logika intuicjonistyczna jest
W pełnej wersji logiki intucjonistycznej pojawiają się również aksjomaty dla spójników <math>\wedge, \vee</math> oraz <math>\neg</math>. Dla uproszczenia zajmiemy  się jedynie formułami, w których jedynym spójnikiem jest implikacja. Dodatkowym argumentem uzasadniającym takie podejście jest fakt, że każde twierdzenie logiki intuicjonistycznej, w którym jedynymi spójnikami są <math>\Rightarrow</math>, da się udowodnić przy pomocy aksjomatów 7.1. Zobaczymy, że analogiczne twierdzenie nie jest prawdą dla logiki klasycznej. Logika intuicjonistyczna jest
bardziej skomplikowana od logiki klasycznej. W szczególności nie istnieje skończona matryca za pomocą której moglibyśmy rozstrzygać czy dana formuła jest twierdzeniem logiki intuicjonistycznej.
bardziej skomplikowana od logiki klasycznej. W szczególności nie istnieje skończona matryca, za pomocą której moglibyśmy rozstrzygać czy dana formuła jest twierdzeniem logiki intuicjonistycznej.


{{twierdzenie|7.2||
{{twierdzenie|7.2||
Linia 1284: Linia 1296:
}}
}}


Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane jedynie przy pomocy <math>\Rightarrow</math>, które nie należą do <math>I_\Rightarrow</math> pomimo że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo Pierce'a:
Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane jedynie przy pomocy <math>\Rightarrow</math>, które nie należą do <math>I_\Rightarrow</math>, pomimo że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo Pierce'a:


<center><math>
<center><math>


((p \Rightarrow q) \Rightarrow p ) \Rightarrow p
((p \Rightarrow q) \Rightarrow p ) \Rightarrow p</math></center>
</math></center>


W zadaniu 4.1 pokazaliśmy, że formuła ta jest w istocie tautologią więc w myśl twierdzenia Posta 4.4 również twierdeniem klasycznego rachunku zdań.<br/>
W zadaniu 4.1 pokazaliśmy, że formuła ta jest w istocie tautologią więc w myśl twierdzenia Posta 4.4 również twierdeniem klasycznego rachunku zdań.<br/>
W poniższych zadaniach wykażemy poniższe twierdzenie
W poniższych zadaniach udowodnimy poniższe twierdzenie


{{twierdzenie|7.3||
{{twierdzenie|7.3||
Linia 1299: Linia 1310:
}}
}}


Zauważmy, że oznacza to również że każdy dowód prawa Pierce'a w logice klasycznej korzysta z aksjomatu 3 3.1, a więc wymaga używania spójnika <math>\neg</math>.<br/>
Zauważmy, że oznacza to również, że każdy dowód prawa Pierce'a w logice klasycznej korzysta z aksjomatu 3 3.1, a więc wymaga używania spójnika <math>\neg</math>.<br/>
Aby udowodnić twierdzenie 7.3 zdefiniujemy jeszcze jedną logikę którą nazwiemy <math>I_3</math>. Podobnie do 4.1 zdefiniujemy matrycę tym razem 3-elementową.
Aby udowodnić twierdzenie 7.3, zdefiniujemy jeszcze jedną logikę którą nazwiemy <math>I_3</math>. Podobnie do 4.1 zdefiniujemy matrycę tym razem 3-elementową.


{{definicja|7.4||
{{definicja|7.4||


Matrycą <math>\mathbb{M}_3</math> będziemy nazywać zbiór trójelementowy <math>M_3=\{0,1,2\}</math> w którym '''2''' jest wyróżnioną wartością prawdy, wraz z funkcją odpowiadają za interpretacje <math>\Rightarrow</math> zdefiniowaną następująco
Matrycą <math>\mathbb{M}_3</math> będziemy nazywać zbiór trójelementowy <math>M_3=\{0,1,2\}</math>, w którym '''2''' jest wyróżnioną wartością prawdy, wraz z funkcją odpowiadają za interpretacje <math>\Rightarrow</math> zdefiniowaną następująco
}}
}}
<span id="tabela_7_4"><center>
<span id="tabela_7_4"><center>
Linia 1337: Linia 1348:


Udowodnij, że aksjomaty S i K są tautologiami <math>I_3</math>.
Udowodnij, że aksjomaty S i K są tautologiami <math>I_3</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">
<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">
: Ćwiczenie jest elementarne, wystarczy sprawdzić wszystkie możliwości.
: Ćwiczenie jest elementarne, wystarczy sprawdzić wszystkie możliwości.
</div></div>
</div></div>
}}
 


{{cwiczenie|7.2||
{{cwiczenie|7.2||


Udowodnij, że jeśli formuła postaci <math>\phi \Rightarrow \psi</math> oraz formuła <math>{\phi}</math> są tautologiami <math>I_3</math> to formuła <math>{\psi}</math> jest tautologią <math>I_3</math>.
Udowodnij, że jeśli formuła postaci <math>\phi \Rightarrow \psi</math> oraz formuła <math>{\phi}</math> są tautologiami <math>I_3</math>, to formuła <math>{\psi}</math> jest tautologią <math>I_3</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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
: Weżmy dowolne wartościowanie <math>\displaystyle v</math> w <math>\displaystyle \mathbb{M}_3</math>. Ponieważ formuły <math>\displaystyle \phi \Rightarrow \psi</math> oraz <math>\displaystyle \phi</math> są tautologiami <math>\displaystyle I_3</math> to <math>\displaystyle v(\phi \Rightarrow \psi) = v(\phi) = 2</math>. Zobaczmy teraz jak może być wartościowana formuła <math>\displaystyle \psi</math>. Przypadek <math>\displaystyle v(\psi)=0</math> możemy wykluczyć, gdyż wtedy zgodnie z [[#tabela_7_4|tabelą interpretacji 7.4]] otrzymalibyśmy <math>\displaystyle v(\phi \Rightarrow \psi) = 0</math>. Podobnie, w przypadku <math>\displaystyle v(\psi)=1</math> otrzymalibyśmy <math>\displaystyle v(\phi \Rightarrow \psi) = 1</math>. Wobec tego pozostała jedynie możliwość <math>\displaystyle v(\psi)=2</math> i wtedy rzeczywiście <math>\displaystyle v(\phi \Rightarrow \psi) = 2</math>. Z dowolności wyboru <math>\displaystyle v</math> wynika, że <math>\displaystyle v(\psi)=2</math> dla dowolnego wartościowania, a więc <math>\displaystyle \psi</math> jest tautologią <math>\displaystyle I_3</math>.
: Weżmy dowolne wartościowanie <math>v</math> w <math>\mathbb{M}_3</math>. Ponieważ formuły <math>\phi \Rightarrow \psi</math> oraz <math>\phi</math> są tautologiami <math>I_3</math>, to <math>v(\phi \Rightarrow \psi) = v(\phi) = 2</math>. Zobaczmy teraz jak może być wartościowana formuła <math>\psi</math>. Przypadek <math>v(\psi)=0</math> możemy wykluczyć, gdyż wtedy zgodnie z [[#tabela_7_4|tabelą interpretacji 7.4]] otrzymalibyśmy <math>v(\phi \Rightarrow \psi) = 0</math>. Podobnie, w przypadku <math>v(\psi)=1</math> otrzymalibyśmy <math>v(\phi \Rightarrow \psi) = 1</math>. Wobec tego pozostała jedynie możliwość <math>v(\psi)=2</math> i wtedy rzeczywiście <math>v(\phi \Rightarrow \psi) = 2</math>. Z dowolności wyboru <math>v</math> wynika, że <math>v(\psi)=2</math> dla dowolnego wartościowania, a więc <math>\psi</math> jest tautologią <math>I_3</math>.
</div></div>
</div></div>
}}
 


{{cwiczenie|7.3||
{{cwiczenie|7.3||


Udowodnij, że każde twierdzenie logiki <math>I_\Rightarrow</math> jest tautologią <math>I_3</math>.
Udowodnij, że każde twierdzenie logiki <math>I_\Rightarrow</math> jest tautologią <math>I_3</math>.
 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  
: Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu. Pomocne będą poprzednie zadania.
: Przeprowadź rozumowanie indukcyjne, ze względu na długość dowodu. Pomocne będą poprzednie zadania.
</div></div>
</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">
<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">
: Rozwiązanie jest analogiczne do rozwiązania [[#cwiczenie_4_1|ćwiczenia 4.1]].
: Rozwiązanie jest analogiczne do rozwiązania [[#cwiczenie_4_1|ćwiczenia 4.1]].
</div></div>
</div></div>
}}
 


{{cwiczenie|7.4||
{{cwiczenie|7.4||


Sprawdź, czy prawo Pierce'a jest tautologią <math>I_3</math>.
Sprawdź, czy prawo Pierce'a jest tautologią <math>I_3</math>.
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Podpowiedź </span><div class="mw-collapsible-content" style="display:none">  
: Nie jest.
: Nie jest.
Linia 1379: Linia 1391:
:3. <math>v(((p\Rightarrow q)\Rightarrow p)\Rightarrow p) =1</math>
:3. <math>v(((p\Rightarrow q)\Rightarrow p)\Rightarrow p) =1</math>


:Wobec tego prawo Pierce'a nie jest tautologią <math>I_3</math> gdyż wyróżnioną wartością prawdy <math>I_3</math> w jest '''2'''. </div></div>
:Wobec tego prawo Pierce'a nie jest tautologią <math>I_3</math>, gdyż wyróżnioną wartością prawdy <math>I_3</math> w jest '''2'''. </div></div>
}}
 


Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę <math>I_3</math>
Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę <math>I_3</math>
taką, że każda twierdzenie intuicjonizmu jest tautologią <math>I_3</math>.
taką, że każda twierdzenie intuicjonizmu jest tautologią <math>I_3</math>.
Skoro prawo Pierce'a nie jest tautologią <math>I_3</math> to nie jest też
Skoro prawo Pierce'a nie jest tautologią <math>I_3</math>, to nie jest też
twierdzeniem <math>I_\Rightarrow</math>.
twierdzeniem <math>I_\Rightarrow</math>.


UWAGA! W dalszej części będziemy się posługiwać wyłącznie '''logiką klasyczną'''.
UWAGA! W dalszej części będziemy się posługiwać wyłącznie '''logiką klasyczną'''.

Aktualna wersja na dzień 21:47, 11 wrz 2023

Wprowadzenie

Logika zdaniowa jest językiem, który pozwala opisywać zależności pomiędzy zdaniami. Przykładem może być zdanie:


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

W powyższym zdaniu spójniki jeśli [..] to, lub mówią o związkach które zachodzą pomiędzy zdaniami:

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

Oznaczmy powyższe zdania przez p,q,r (w takiej właśnie kolejności). Używając symboli, które zwyczajowo odpowiadają potocznemu rozumieniu spójników jeśli [..] to, lub oraz powyższych oznaczeń, otrzymamy formułę


p(qr)


Jeśli powyższą formułę uznamy za prawdziwą, to może nam ona posłużyć do otrzymania nowych wniosków. Na przykład, jeśli o jakiejś liczbie n będziemy wiedzieć, że jest liczbą pierwszą oraz że nie jest nieparzysta, to klasyczny rachunek zdań pozwoli nam formalnie wywnioskować fakt, że liczba n jest równa 2. Podsumowując, jeśli uznamy za prawdziwe następujące zdania:

  1. p(qr),
  2. p,
  3. ¬q (przez ¬ oznaczamy negację)

to zgodnie z klasycznym rachunkiem zdań powinniśmy uznać za prawdziwe zdanie r, czyli n jest równe 2. Powyższy schemat wnioskowania można również opisać formułą


((p(qr))p(¬q))q


W powyższej formule symbol odpowiada spójnikowi i (oraz).

Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy wnioskowania i zdania złożone oraz oceniać ich prawdziwość.

Język logiki zdaniowej

Zaczniemy od definicji języka logiki zdaniowej. Składa się on z formuł zdefiniowanych następująco:

Definicja 2.1 [Formuła logiki zdaniowej]

  1. zmienna zdaniowa jest formułą (zmienne zdaniowe oznaczamy zwykle literami alfabetu rzymskiego np. p,q,r),
  2. jeśli ϕ oraz ψ są formułami to (ϕψ) jest formułą (spójnik nazywamy implikacją),
  3. jeśli ϕ jest formułą to ¬ϕ jest formułą (spójnik ¬ nazywamy negacją),
  4. nic innego nie jest formułą.

Powyższa definicja mówi, że formułami nazywamy te napisy, które dają się skonstruować ze zmiennych zdaniowych przy pomocy spójników oraz ¬.

Uwaga 2.2.
Zgodnie z powyższą definicją nie jest formułą napis pq, gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy napisać (pq) możemy przyjąć że nie będzie konieczne pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić. Często przyjmuje się również prawostronne nawiasowanie dla implikacji, czyli formuła pqr jest domyślnie nawiasowana w następujący sposób (p(qr)).

Przykład 2.3 Poniższe napisy nie są formułami

  • pq,
  • ¬¬¬,
  • ten napis na pewno nie jest formułą,
  • (p¬q)).

Poniższe napisy są formułami

  • (p(rq)),
  • ¬¬¬q,
  • (p¬q).


Ćwiczenie 2.1

Rozmiarem formuły nazwiemy ilość występujących w niej spójników. Na przykład formuła ¬¬q ma rozmiar 2, a formuła (pq) ma rozmiar 1. Przypuśćmy, że jedyną zmienną zdaniową jaką wolno nam użyć jest p. Ile można skonstruować rożnych formuł o rozmiarze 3?

Rozwiązanie


Uwaga 2.4.
Język logiki zdaniowej można równoważnie zdefiniować nie używając nawiasów za pomocą tzw. Odwrotnej Notacji Polskiej.

Aksjomatyka Klasycznego Rachunku Zdań

Podobnie jak nie wszystkie zdania języka naturalnego mają sens, nie wszystkie formuły opisują prawdziwe schematy wnioskowania lub zdania, które bylibyśmy skłonni uznać za prawdziwe. W tym rozdziale skupimy się na tym, które spośród wszystkich formuł zdaniowych wyróżnić jako prawdziwe.

Aksjomaty

Wielu matematyków zgadza się dzisiaj co do tego, że zdania pasujące do poniższych schematów powinny być uznane za prawdziwe:

Definicja 3.1 Aksjomaty klasycznego rachunku zdań

  1. (ϕ(ψϕ)) (formuła ta jest nazywana aksjomatem K),
  2. (ϕ(νψ))((ϕν)(ϕψ)) (formuła ta jest nazywana aksjomatem S),
  3. (¬ϕψ)((¬ϕ¬ψ)ϕ) (tzw. schemat dowodu niewprost)

Zdania pasujące do powyższych schematów to wszystkie zdania, które można otrzymać, podstawiając w miejsce ϕ,ν,ψ dowolne formuły.

Reguła dowodzenia

Przyglądnijmy się teraz jak posługujemy się implikacją we wnioskowaniu. W przykładzie z początku wykładu implikacja odpowiadała konstrukcji językowej:

jeśli ϕ to ψ.

W takim przypadku, jeśli akceptujemy powyższą implikacjię jako zdanie prawdziwe oraz jeśli zdanie ϕ jako prawdziwe, to powinniśmy także zaakceptować ψ. Przedstawiony sposób wnioskowania nosi nazwę reguły Modus Ponens (nazywana też regułą odrywania, często będziemy używać skrótu MP) i jest skrótowo notowany w poniższy sposób

ϕψ,ϕψ

Reguła modus ponens posłuży nam do uzupełniania zbioru aksjomatów o ich konsekwencje logiczne, które również uznamy za prawdziwe. Aby precyzyjnie zdefiniować zbiór wszystkich konsekwencji logicznych aksjomatów, definiujemy poniżej pojęcie dowodu.

Definicja 3.2

Ciąg formuł ϕ0,,ϕn jest dowodem formuły ψ wtedy i tylko wtedy, gdy:

  1. ϕn jest formułą ψ,
  2. dla każdego in formuła ϕi jest aksjomatem lub istnieją j,k<i takie, że formuła ϕi jest wynikiem zastosowania reguły modus ponens do formuł ϕj,ϕk.

W drugim punkcie powyższej definicji, jeśli formuła ϕi nie jest aksjomatem (a więc powstaje przez zastosowanie MP), to formuły ϕj,ϕk muszą pasować do przesłanek reguły MP, a więc ϕj musi być postaci ϕkϕi lub ϕk postaci ϕjϕi.

Definicja 3.3

Formułę nazywamy twierdzeniem klasycznego rachunku zdań jeśli istnieje jej dowód z aksjomatów klasycznego rachunku zdań 3.1

Przykład

Zastanówmy się na formułą postaci ϕϕ. Intuicja podpowiada, że taką formułę powinniśmy uznać za prawdziwą. Nie pasuje ona jednak do żadnego ze schematów aksjomatów 3.1. Formuła ta jest jednak twierdzeniem klasycznego rachunku zdań. Poniżej przedstawiamy jej dowód. Aby łatwiej dopasować formuły do schematów aksjomatów, użyliśmy nawiasów kwadratowych dla nawiasów, które pochodzą ze schematów.

  1. [ϕ[(qϕ)ϕ)][[ϕ(qϕ)][ϕϕ]] formuła ta jest aksjomatem zgodnym ze schematem S,
  2. ϕ[(qϕ)ϕ] aksjomat zgodny ze schematem K,
  3. (ϕ(qϕ))(ϕϕ) z modus ponens z formuł 1 i 2,
  4. ϕ[qϕ] aksjomat zgodny ze schematem K,
  5. (ϕϕ) z modus ponens z formuł 3 i 4.

Podsumowanie

Klasyczny rachunek zdań, czyli zbiór formuł które uznajemy za prawdziwe, zdefiniowaliśmy, wyróżniając pewne formuły jako aksjomaty 3.1 i dorzucając do nich wszystkie formuły, które dają się z nich wywnioskować przy pomocy reguły Modus Ponens. Warto zwrócić uwagę, że pomimo tego, iż w doborze aksjomatów i reguł wnioskowania kierowaliśmy się intuicyjnym pojęciem implikacji i konsekwencji, klasyczny rachunek zdań jest teorią syntaktyczną, zbiorem pewnych napisów o których znaczeniu nie musimy nic mówić.

Uwaga 3.4

Warto przyglądnąć się przyjętym aksjomatom i zastanowić się jakim zdaniom odpowiadają i czy rzeczywiście bylibyśmy skłonni uznać je za prawdziwe. Pomocne może być interpretowanie formuł postaci ϕ(νψ) jako „jeśli prawdziwe jest ϕ i prawdziwe jest ν to prawdziwe jest ψ”. W kolejnych rozdziałach przekonamy się, że taka interpretacja jest uzasadniona.

Matryca boolowska

W poprzednim rozdziale zdefiniowaliśmy klasyczny rachunek zdań jako teorię aksjomatyczną. Jeśli pozwolimy sobie na używanie skończonych zbiorów i funkcji, możemy równoważnie zdefiniować klasyczny rachunek zdań za pomocą tzw. matrycy boolowskiej.

Definicja 4.1

Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy 𝔹={0,1} w którym 1 jest wyróżnioną wartością prawdy, wraz z dwoma funkcjami odpowiadającymi za interpretacje spójników oraz ¬ zdefiniowanymi następująco

0 1
0 1 1
1 0 1
    
p ¬p
0 1
1 0

(4.1)

Definicja 4.2

Wartościowaniem nazywamy funkcję, która przypisuje zmiennym zdaniowym elementy zbioru 𝔹. Wartościowanie zmiennych można rozszerzyć na wartościowanie formuł interpretując spójniki oraz ¬ jako funkcje zgodnie z tabelami 4.1.

Przykład 4.3

Niech v będzie wartościowaniem zmiennych takim, że v(p)=0,v(q)=1,v(r)=0. Wtedy

  • formuła qp jest wartościowana na 0 (będziemy to zapisywać jako v(qp)=0),
  • formuła r(qp) jest wartościowana na 1 (czyli v(r(qp))=1),
  • formuła ¬pr jest wartościowana na 0 (czyli v(¬pr)=0).

Ćwiczenie 4.1

Przy wartościowaniu v z przykładu 4.3 jakie wartości przyjmują następujące formuły

  1. p(qr),
  2. p(pq),
  3. ¬¬qp,
  4. (¬qq)(q¬q).
Rozwiązanie

Ćwiczenie 4.2

     1. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były wartościowane na 0

(a) p(qr)
(b) (¬pq)
(c) (pq)q

     2. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były wartościowane na 1

(a) ¬(pq)
(b) ¬(¬p¬q)
(c) (¬qq)(q¬q)
Rozwiązanie

Twierdzenie o pełności

Zauważmy, że istnieją formuły, które dla każdego wartościowania zmiennych zdaniowych, zawsze przyjmują wartość 1 (np. pp). Takie formuły będziemy nazywać tautologiami.

Ćwiczenie 4.3

Sprawdź czy poniższe formuły są tautologiami

  1. (ϕ(ψϕ)),
  2. (ϕ(νψ)((ϕν(ϕν)),
  3. (¬ϕψ)(¬ϕ¬ψ)ϕ,
  4. ((ϕq)p)p.
Podpowiedź 1
Podpowiedź 2
Rozwiązanie


Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania odpowiadają aksjomatom klasycznego rachunku zdań 3.1. Okazuje się że istnieje ścisły związek pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik Emila Posta

Emil Leon Post (1897-1954)
Zobacz biografię

Twierdzenie 4.4

Post 1921 Formuła jest twierdzeniem klasycznego rachunku zdań wtedy i tylko wtedy kiedy jest tautologią.

Dowód powyższego twierdzenia jest przedstawiony na wykładzie Logika dla informatyków Dzięki powyższemu twierdzeniu możemy w miarę łatwo stwierdzać, czy dana formuła jest twierdzeniem klasycznego rachunku zdań, sprawdzając, czy jest tautologią, co wymaga rozważenia jedynie skończonej (chociaż często niemałej) liczby wartościowań. Co więcej, mamy też możliwość dowodzenia, że jakaś formuła nie jest twierdzeniem klasycznego rachunku zdań. Uzasadnienie, że nie da się jakiejś formuły udowonić z aksjomatów poprzez stosowanie reguły MP wydaje się zadaniem trudnym, znacznie łatwiej jest poszukać wartościowania, które wartościuje formułę na 0 (znowu wystarczy sprawdzić jedynie skończenie wiele wartościowań).

Ćwiczenie 4.4

Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.

Podpowiedź 1
Podpowiedź 2
Rozwiązanie


Inne spójniki

Do tej pory jedynymi rozważanymi spójnikami była implikacja i negacja. W analogiczny sposób do 4.1 możemy wprowadzać kolejne spójniki. Często używane spójniki to koniunkcja (spójnik i) oznaczana przez oraz alternatywa (spójnik lub) oznaczana przez , które będziemy interpretować w następujący sposób:

0 1
 0   0   0 
 1   0   1 
    
0 1
 0   0   1 
 1   1   1 

(4.2)


Zgodnie z intuicją koniunkcja ϕψ jest wartościowana na 1 wtedy i tylko wtedy, gdy zarówno ϕ jak i ψ są wartościowane na 1. Alternatywa ϕψ jest wartościowana na 1, jeśli przynajmniej jedna z formuł ϕ,ψ jest wartościowana na 1.

Definicja 4.5

Formuły ϕ oraz ψrównoważne (oznaczamy ten fakt przez ϕψ wtedy i tylko wtedy, gdy dla każdego wartościowania formuła ϕ przyjmuje tą samą wartość co formuła ψ.

Ćwiczenie 4.5

Udowodnij, że następujące formuły są równoważne

  1. ϕψ¬ϕψ
  2. ϕψ¬(ϕ¬ψ)
Rozwiązanie

Z powyższego zadania wynika, że każdą formułę w której występują spójniki lub można zastąpić równoważną formułą, w której jedynymi spójnikami są oraz ¬. Tak naprawdę więc nowe spójniki nie wprowadzają nic nowego poza użytecznymi skrótami w zapisywaniu formuł. Aby się oswoić z własnościami spójników, prześledzimy szereg ich praw.

Ćwiczenie 4.6

Udowodnij następujące równoważności

  1. ¬¬pp,
  2. pq¬pq,
  3. p(qr)(pq)r,
  4. ¬(pq)¬p¬q,
  5. ¬(pq)¬p¬q,
  6. p(qr)(pq)(pr),
  7. p(qr)(pq)(pr),
  8. (pq)(¬p¬q).
Rozwiązanie


Ćwiczenie 4.7

Sprawdź które z następujących formuł są tautologiami

  1. ((pr)(q¬r))(pq),
  2. (pq)((pr)(q¬r)),
  3. ((pr)(q¬r))(pq),
  4. (pq)((pr)(q¬r)).
Rozwiązanie


Binarne spójniki logiczne interpretowaliśmy jako funkcje z 𝔹×𝔹𝔹. Nie trudno przekonać się, że takich funkcji jest dokładnie 16. Dla każdej takiej funkcji możemy dodać spójnik, który będzie interpretowany dokładnie jako ta funkcja. W poniższej tabeli zamieszczamy wszystkie takie funkcje wraz ze zwyczajowymi oznaczeniami odpowiadających im spójników.

Definicja 4.6

W poniższej tabeli przedstawiamy wszystkie spójniki binarne.

Numer
funkcji
p=0
q=0
p=0
q=1
p=1
q=0
p=1
q=1
   
0 0 0 0 0   F
1 0 0 0 1  
2 0 0 1 0   ¬(pq)
3 0 0 1 1   p
4 0 1 0 0   ¬(qp)
5 0 1 0 1   q
6 0 1 1 0   XOR
7 0 1 1 1  
8 1 0 0 0   NOR
9 1 0 0 1  
10 1 0 1 0   ¬q
11 1 0 1 1   qp
12 1 1 0 0   ¬p
13 1 1 0 1   pq
14 1 1 1 0   NAND
15 1 1 1 1   T

Spójnik binarny będziemy nazywać przemiennym, jeśli zachodzi następująca równoważność

pqqp(4.3)


Ćwiczenie 4.8

Sprawdź następujące równoważności

  1. xNANDy¬(xy)
  2. xNORy¬(xy)
  3. xXORy¬(xy)
Rozwiązanie

Ćwiczenie 4.9

Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.

Podpowiedź
Rozwiązanie


Spójnik binarny będziemy nazywać łącznym jeśli zachodzi

następująca równoważność

p(qr)(pq)r.(4.4)

Jeśli spójnik jest łączny to dowolne dwie formuły, które są zbudowane jedynie ze spójników są równoważne, jeśli występuje w nich tyle samo spójników. Dlatego dla łącznych spójników binarnych pomija się często nawiasy.

Ćwiczenie 4.10

Udowodnij, że następujące spójniki są łączne

  1. XOR
Rozwiązanie


Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik k-argumetowy powinien odpowiadać funkcji 𝔹k𝔹.

Przykład 4.7

W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego

p q r (p,q,r)
 0   0   0   0 
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
Uwaga 4.1

Różnych spójników k-argumentowych jest dokładnie 22k.

Systemy funkcjonalnie pełne

Każda formuła odpowiada pewnej funkcji przekształcającej wartościowania zmiennych w niej występujących w element zbioru 𝔹. Na przykład formuła p(qr) wyznacza funkcję fp(qr) opisaną poniższą tabelą

p q r fp(qr)
 0   0   0  1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

Mówimy, wtedy że formuła ϕ definuje funkcję fϕ.

Definicja 5.1

Skończony zbiór funkcji boolowskich Γ nazywamy funkcjonalnie pełnym, jeśli każdą funkcję boolowską da się zdefiniować przy pomocy formuły zbudowanej wyłącznie ze spójników odpowiadających funkcjom ze zbioru Γ.

Twierdzenie 5.2

Zbiór {,,¬} jest funkcjonalnie pełny.

Dowód

Dla dowolnej funkcji boolowskiej skonstruujemy formułę która ją definiuje. Niech k oraz f:𝔹k𝔹. W definiowanej formule będziemy używać zmiennych p1,,pk, a każdy element (w1,,wk)𝔹k będzie odpowiadał wartościowaniu vw takiemu, że v(pi)=wi.

Niech F będzie zbiorem tych argumentów, dla których funkcja f przyjmuje wartość 1. Dla dowolnego elementu xiF skonstruujemy formułę ϕi w taki sposób, aby była spełniona tylko dla wartościowania odpowiadającego elementowi xi. Niech xi=(w1,,wk), wtedy formułę ϕi definiujemy jako l1il2ilki gdzie

lji{pj,gdy wj=1;¬pj,gdy wj=0.

Łatwo sprawdzić, że formuła ϕi jest spełniona tylko dla wartościowania odpowiadającego elementowi xi.

Postępując w ten sposób dla każdego elementu zbioru F otrzymamy formuły ϕ1,ϕm. Biorąc

ϕ1ϕm

otrzymamy formułę która definiuje funkcję f, oznaczmy ją przez Φ. Jeśli dla wartościowania v formuła Φ jest spełniona to znaczy, że któraś z formuł ϕi jest spełniona. Oznacza to że wartościowanie v odpowiada pewnemu elementowi xi zbioru F, wobec tego funkcja f(xi)=1 co jest zgodne z tym, że spełniona jest Φ. W drugą stronę załóżmy że dla pewnego elementu a𝔹k mamy f(a)=1. Wobec tego aF. Wtedy a odpowiada pewnej formule ϕi, która jest spełniona dla wartościowania odpowiadającego a. Wobec tego również cała formuła Φ jest spełniona dla tego wartościowania (bo jeden z elementów alternatywy jest spełniony). Wynika stąd, że formuła Φ definiuje funkcję f. Na koniec zauważmy jeszcze że jedynymi spójnikami występującymi w formule Φ¬,,.

Twierdzenie 5.3

Zbiory {,¬}, {,¬} są funkcjonalnie pełne.

Dowód

Aby pokazać, że {,¬} jest funkcjonalnie pełny wystarczy pokazać, że przy pomocy spójników {,¬} da się zdefiniować . Wtedy funkcjonalną pełność otrzymamy z twierdzenia 5.2. W ćwiczeniu 4.2 pokazaliśmy, że

¬(xy)=¬x¬y

Wobec tego

xy=¬(¬x¬y)

a więc zdefiniowaliśmy przy pomocy ¬,.

Analogicznie aby pokazać funkcjonalną pełność zbioru {,¬} zdefiniujemy przy pomocy spójników ,¬. Z ćwiczenia 4.2 mamy

¬(xy)=¬x¬y

a więc

xy=¬(¬x¬y)

Ćwiczenie 5.1

Udowodnij, że zbiór {,¬} jest funkcjonalnie pełny.

Rozwiązanie


Twierdzenie 5.4

Zbiór {NOR} jest funkcjonalnie pełny.

Dowód

Pokażemy, że przy pomocy NOR można zdefiniować ¬ oraz . Wtedy z twierdzenia twierdzenia 5.3 otrzymamy tezę twierdzenia.

Łatwo sprawdzić, że

pNORp¬

Wiemy, że

pNORq¬(pq)

Wobec tego mamy również

¬(pNORq)pq

Możemy teraz wyrazić negację za pomocą NOR, otrzymamy wtedy

(pNORq)NOR(pNORq)pq

Ćwiczenie 5.2

Udowodnij, że zbiór {NAND} jest funkcjonalnie pełny.

Rozwiązanie


Ćwiczenie 5.3

Zdefiniuj alternatywę przy pomocy samej implikacji.

Rozwiązanie

}}

Ćwiczenie 5.4

Jakie funkcje binarne da się zdefiniować przy pomocy samej implikacji?

Rozwiązanie


Ćwiczenie 5.5

Udowodnij, że poniższe zbiory nie są funkcjonalnie pełne

  1. {}
  2. {}
  3. {}
  4. {XOR}
Rozwiązanie


Ćwiczenie 5.6

Czy funkcje binarne, zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki, muszą być przemienne?

Podpowiedź
Rozwiązanie


Ćwiczenie 5.7

(z wykładu prof. P.M.Idziaka) Niech Fn oznacza ilość boolowskich funkcji n argumetnowych, a Pn ilość boolowskich funkcji n argumentowych, takich że przy pomocy każdej z nich da się zdefiniować dowolną funkcję boolowską (czyli jeśli jest takim spójnikiem to zbiór {} jest funkcjonalnie pełny). Udowdnij istenienie poniższej granicy i wyznacz jej wartość

limnPnFn
Rozwiązanie

Postacie normalne

Definicja 6.1

Literałem nazywamy formułę, która jest zmienną zdaniową lub negacją zmiennej zdaniowej.

Zauważmy, że formuła konstruowana w dowodzie twierdzenia 5.2 jest w pewnej standartowej postaci - formuła jest alternatywą formuł, które są koniunkcjami literałów. Przypomnijmy, że dla pq zbudujemy formułę

(pq)(¬pq)(¬p¬q)

Definicja 6.2

Formuła jest w dyzjunktywnej postaci normalnej (DNF), jeśli jest alternatywą formuł które są koniunkcjami literałów. Czyli wtedy, gdy jest postaci

ϕ1ϕn

oraz każda z formuł ϕi jest koniunkcją literałów, czyli jest postaci

llilki

dla pewnych literałów lli,,lki

Twierdzenie 6.3

Dla każdej formuły istnieje równoważna formuła w DNF.

Dowód

Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia 5.2.

Definicja 6.4

Formuła jest w koniunktywnej postaci normalnej (CNF), jeśli jest koniunkcją formuł które są alternatywami literałów.

Twierdzenie 6.5

Dla każdej formuły istnieje równoważna formuła w CNF.

Dowód

Niech Φ będzie dowolną formułą. Z twierdzenia twierdzenia 6.3 wynika, że dla formuły ¬Φ istnieje dyzjunktywna postać normalna. Niech Ψ będzie taką formułą. Wtedy mamy

Φ¬Ψ

Stosując wielokrotnie prawa de'Morgana dla formuły ¬Ψ otrzymamy formułę w koniunktywnej postaci normalnej. Indukcyjny dowód tego faktu pomijamy.

Ćwiczenie 6.1

Jak sprawdzić, czy formuła w CNF jest tautologią?

Rozwiązanie


Ćwiczenie 6.2

Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w CNF

  1. pq,
  2. p(qp),
  3. (pq)p,
  4. (pab)(¬q¬a)(r¬b¬c)(cp)),
  5. (pq)(rs).
Rozwiązanie


Spełnialność

Spośród wszystkich formuł wyróżnimy też zbiór formuł spełnialnych.

Definicja 6.6

Formuła jest spełnialna, jeśli istenieje takie wartościowanie, które wartościuje tą formułę na 1.

Formuły spełnialne są w ścisłym związku z tautologiami.

Twierdzenie 6.7

Formuła ϕ jest tautologią wtedy i tylko wtedy, kiedy formuła ¬ϕ nie jest spełnialna.

Dowód

Przypuśćmy, że formuła ϕ jest tautologią. Wtedy dla każdego wartościowania v mamy v(ϕ)=1. Stąd otrzymujemy, że dla każdego wartościowania v mamy v(¬ϕ)=0, a więc nie istnieje wartościwanie, które spełnia ¬ϕ, czyli formuła ta nie jest spełnialna.

Przypuśćmy, że formuła ¬ϕ nie jest spełnialna, czyli nie istnieje wartościowanie v takie, że v(¬ϕ)=0. Wynika stąd, że dla każdego wartościowania mamy v(ϕ)=1, a więc ϕ jest tautologią.

Ćwiczenie 6.3

Sprawdź spełnialność następujących formuł

  1. (¬pq)(¬q¬r)(¬q¬p)
  2. (¬pq)(¬q¬r)(¬qp)
Rozwiązanie


Formuły z powyższego zadania, poza tym że są w koniunktywnej postaci normalnej, to jeszcze występujące w nich klauzule mają dokładnie dwa literały. Problem spełnialności takich formuł jest nazywany w literaturze problemem 2SAT. Dla takich formuł istnieją szybkie algorytmy pozwalające ocenić ich spełnialność. Dopuszczanie klauzul o długości 3, bardzo komplikuje problem. Do dziś nie wiadomo czy dla takich formuł istnieją szybkie algorytmy oceniające spełnialność. Więcej na ten temat można się dowiedzieć z wykładu Teoria złożoności.

Logika intuicjonistyczna

Niektórzy logicy mają wątpliwości co do tego, czy powinniśmy przyjmować schemat dowodu niewprost jako aksjomat. Poddanie w wątpliwość tego aksjomatu doprowadziło do powstnia tzw. logiki intuicjonistycznej. Ważnym powodem zajmowania się logiką intuicjonistyczną są jej zadziwiające związki z teorią obliczeń (patrz izomorfizm Curryego-Howarda).

Implikacyjny fragment logiki intuicjonistycznej, który będziemy oznaczać przez I to zbiór tych formuł, które da się dowodnić przy pomocy reguły MP z aksjomatów S i K.

Definicja 7.1

Aksjomaty I

  1. (ϕ(ψϕ)) (formuła ta jest nazywana aksjomatem K),
  2. (ϕ(νψ)((ϕν)(ϕν)) (formuła ta jest nazywana aksjomatem S).

W pełnej wersji logiki intucjonistycznej pojawiają się również aksjomaty dla spójników , oraz ¬. Dla uproszczenia zajmiemy się jedynie formułami, w których jedynym spójnikiem jest implikacja. Dodatkowym argumentem uzasadniającym takie podejście jest fakt, że każde twierdzenie logiki intuicjonistycznej, w którym jedynymi spójnikami są , da się udowodnić przy pomocy aksjomatów 7.1. Zobaczymy, że analogiczne twierdzenie nie jest prawdą dla logiki klasycznej. Logika intuicjonistyczna jest bardziej skomplikowana od logiki klasycznej. W szczególności nie istnieje skończona matryca, za pomocą której moglibyśmy rozstrzygać czy dana formuła jest twierdzeniem logiki intuicjonistycznej.

Twierdzenie 7.2

Każde twierdzenie logiki intuicjonistycznej jest twierdzeniem klasycznego rachunku zdań.

Dowód

Każdy dowód twierdzenia logiki inuicjonistycznej jest równocześnie dowodem twierdzenia klasycznego rachunku zdań.

Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane jedynie przy pomocy , które nie należą do I, pomimo że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo Pierce'a:

((pq)p)p

W zadaniu 4.1 pokazaliśmy, że formuła ta jest w istocie tautologią więc w myśl twierdzenia Posta 4.4 również twierdeniem klasycznego rachunku zdań.
W poniższych zadaniach udowodnimy poniższe twierdzenie

Twierdzenie 7.3

Prawo Pierce'a nie jest twierdzeniem intuicjonizmu.

Zauważmy, że oznacza to również, że każdy dowód prawa Pierce'a w logice klasycznej korzysta z aksjomatu 3 3.1, a więc wymaga używania spójnika ¬.
Aby udowodnić twierdzenie 7.3, zdefiniujemy jeszcze jedną logikę którą nazwiemy I3. Podobnie do 4.1 zdefiniujemy matrycę tym razem 3-elementową.

Definicja 7.4

Matrycą 𝕄3 będziemy nazywać zbiór trójelementowy M3={0,1,2}, w którym 2 jest wyróżnioną wartością prawdy, wraz z funkcją odpowiadają za interpretacje zdefiniowaną następująco

0 1 2
 0   2   2   2 
 1   0   2   2 
 2   0   1   2 

W przypadku rozważanej matrycy 𝕄3 wartościowanie będzie funkcją przypisującą zmiennym zdaniowym elementy zbioru M3. Podobnie jak dla logiki klasycznej wartościowanie zmiennych rozszzerzamy na wartościowanie formuł zgodnie z tabelą 7.4.

Przykład 7.5

Dla wartościowania v takiego, że v(p)=2,v(q)=1,v(r)=0 formuła

(pq)r

przyjmuje wartość 0.

Definicja 7.6

Tautologią logiki I3 będziemy nazywać każdą formułę implikacyjną, która przy każdym wartościowaniu zmiennych w M3 przyjmuje wartość 2.

Ćwiczenie 7.1

Udowodnij, że aksjomaty S i K są tautologiami I3.

Rozwiązanie


Ćwiczenie 7.2

Udowodnij, że jeśli formuła postaci ϕψ oraz formuła ϕ są tautologiami I3, to formuła ψ jest tautologią I3.

Rozwiązanie


Ćwiczenie 7.3

Udowodnij, że każde twierdzenie logiki I jest tautologią I3.

Podpowiedź
Rozwiązanie


Ćwiczenie 7.4

Sprawdź, czy prawo Pierce'a jest tautologią I3.

Podpowiedź
Rozwiązanie


Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę I3 taką, że każda twierdzenie intuicjonizmu jest tautologią I3. Skoro prawo Pierce'a nie jest tautologią I3, to nie jest też twierdzeniem I.

UWAGA! W dalszej części będziemy się posługiwać wyłącznie logiką klasyczną.