Test GR: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Nie podano opisu zmian
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
==``Naiwna'' teoria mnogości==
==Wprowadzenie==


wyszczególnionych w preambule
Logika zdaniowa jest językiem, który pozwala opisywać zależności
Teoria zbiorów, zwana również teorią mnogości, została stworzona
pomiędzy zdaniami. Przykładem może być zdanie:
około połowy XIX wieku, przez niemieckiego matematyka '''Georg Cantor'''.
Teoria  mnogości to gałąź matematyki zajmująca się zbiorami --
kolekcja obiektów. Skończone zbiory można definiować wypisując
kolejno wszystkie ich elementy. '''Georg Cantor''' był pierwszą osobą która
podjęła się przeniesienia na ścisły grunt matematyczny pojęcia
zbioru nieskończonego. Według '''Georg Cantor''' zbiór może być dowolną
kolekcją obiektów zwanych elementami. Według tego podejścia zbiór
jest pojęciem podstawowym i niedefiniowalnym. Niestety podejście
do teorii zbiorów w ten sposób rodzi paradoksy i dlatego teoria
mnogości prezentowana w ten sposób jest często nazywana ``naiwną''
teorią mnogości.


Teoria matematyczna nie może dopuszczać istnienia paradoksów i
Jeśli n jest liczbą pierwszą to n jest liczbą nieparzystą lub n jest
dlatego na początku XX wieku zmieniono podejście do teorii
równe 2.
mnogości. Zaproponowana przez '''Ernst Zermelo''' i uzupełniony przez
'''Adolf Abraham Halevi Fraenkel''' system aksjomatów wyklucza paradoksy które spowodowały
że naiwna teoria zbiorów musiała zostać porzucona. Aksjomaty te
nakładają pewne ograniczenia na konstrukcje zaproponowane przez
'''Georg Cantor'''. W większości przypadków jednak intuicje związanej z
naiwna teorią mnogości sprawdzają się również w aksjomatycznej
teorii zbiorów. Zaprezentowane poniżej, skrótowe przedstawienie
"naiwnej teorii mnogości" ma na celu wyrobienie intuicji
niezbędnych przy dalszej pracy formalną wersją tych teorii.
Aksjomatyczna teoria zbiorów zostanie przedstawiona w '''Wykład
4.'''


W podejściu zaproponowanym przez '''Georg Cantor''' zbiory skończone można
W powyższym zdaniu spójniki "'jeśli"' [..] "'to"',
łatwo wskazywać poprzez wyliczenie ich elementów. Definiowanie
"'lub"' mówią o związkach które zachodzą pomiędzy zdaniami:
zbiorów nieskończonych wymaga bardziej rozwiniętego języka,
niemniej jednak, według '''Georg Cantor''', każda kolekcja obiektów jest
zbiorem. Podstawowym symbolem używanym przy definiowaniu i
opisywaniu zbiorów jest


oznaczający, że dany byt jest ''elementem'' pewnego zbioru.
# "n jest liczbą pierwszą,"
Napis


"Kraków""zbiór wszystkich miast Polski"
# "n jest liczbą nieparzystą,"


ilustruje zastosowanie tego symbolu.
# "n jest równe 2."


Aby zdefiniować zbiór należy określić definitywny sposób na
Oznaczmy powyższe zdania przez <math>p,q,r</math> (w takiej właśnie
rozpoznawania czy dany byt jest elementem zbioru, czy nie.
kolejności). Używając symboli, które zwyczajowo odpowiadają
Najczęściej używanym symbolem przy definiowaniu zbioru są nawiasy
potocznemu rozumieniu spójników <math>\textbf{jeśli} [..] \textbf{to},
klamrowe. Definicja skończonego zbioru może być bardzo łatwa.
\textbf{lub}</math> oraz powyższych oznaczeń otrzymamy formułę
Zbiór


2,3,Kraków
<center><math>


posiada trzy elementy. Liczba <math>2</math> jest elementem tego zbioru
p \Rightarrow (q \vee r).
<math>2\in\{2,3,\mbox{Kraków}\}</math>, ale również
</math></center>
<math>\mbox{Kraków}\in\{2,3,\mbox{Kraków}\}</math>.


Dwa zbiory są sobie równe&nbsp;(takie same) jeśli posiadają dokładnie
Jeśli powyższą formułę uznamy za prawdziwą to może nam ona posłużyć
te same elementy. Jedynymi elementami zbioru <math>\{2,3\}</math> są liczby
do otrzymania nowych wniosków. Na przykład jeśli o jakiejś liczbie n
naturalne <math>2</math> i <math>3</math> -- ten sam fakt jest prawdziwy dla zbioru
będziemy wiedzieć, że jest liczbą pierwszą oraz, że nie jest
<math>\{2,2,3\}</math>, a więc
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:


2,3 <nowiki>=</nowiki> 2,3,3.
# <math> p \Rightarrow (q \vee r) </math>,


Podobnie <math>\{2,3\}=\{3,2\}</math> i
# <math>p </math>,


2,3<nowiki>=</nowiki>"zbiór liczb naturalnych ściśle pomiędzy <math>1</math> a
# <math> \neg q </math> (przez <math>\neg</math> oznaczamy negację)
<math>4</math>".


W definicji zbioru nie ma znaczenia kolejność w jakiej wymienione
to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) zdań
są jego elementy, ani krotność w jakiej dany element pojawia się w
powinniśmy uznać za prawdziwe zdanie <math>r</math>, czyli "n jest równe
zbiorze.
2". Powyższy schemat wnioskowania można również opisać formułą


Zbiory można definiować na wiele sposobów. Najprostszym sposobem
<center><math>
zdefiniowani zbioru jest wyliczenie jego elementów. Strategia ta
zawodzi jednak w odniesieniu do zbiorów nieskończonych -- nie
jesteśmy w stanie wypisać wszystkich liczb naturalnych. Zgodnie z
postulatami '''Georg Cantor''' możemy przyjąć że istnieje zbiór wszystkich
liczb naturalnych. Czasami, na określenie zbiorów nieskończonych
używamy nieformalnego zapisu -- zbiór wszystkich liczb naturalnych
może być zapisany jako


0,1,2,3,4,....
\left((p \Rightarrow (q \vee r)) \wedge p \wedge (\neg q)\right) \Rightarrow
q.
</math></center>


W podejściu zaproponowanym przez '''Georg Cantor''' równoważna definicja tego
W powyższej formule spójnik symbol <math>\wedge</math> odpowiada spójnikowi
zbioru brzmi
"'i"' (oraz).


``zbiór wszystkich liczb naturalnych''
Dzięki rachunkowi zdań możemy precyzyjnie opisywać schematy
wnioskowania i zdania złożone oraz oceniać ich prawdziwość.


Bardzo często tworzymy zbiory składające się z obiektów
==Język logiki zdaniowej==
spełniających daną własność. Zbiór liczb parzystych możemy
zdefiniować w sposób następujący


x|<math>x</math> jest liczbą parzystą.
Zaczniemy od definicji języka logiki zdaniowej. Składa się on z
formuł zdefiniowanych następująco:
{formuła logiki zdaniowej}


Bardziej ogólnie
# zmienna zdaniowa jest formułą (zmienne zdaniowy oznaczamy
zwykle literami alfabetu rzymskiego np. <math>p,q,r</math>)


x|warunek
# 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ą)


W skład powyżej zdefiniowanego zbioru wchodzą te elementy, które
# jeśli <math>\phi</math> jest formułą to <math>\neg \phi</math> jest formułą
spełniają warunek występujący po znaku <math>\,|\,</math>. Żeby
(spójnik <math>\neg</math> nazywamy negacją)
zakwalifikować element do powyższego zbioru wstawiamy go w miejsce
<math>x</math> w warunku występującym po <math>\,|\,</math> i sprawdzamy czy jest on
prawdziwy. Żeby pokazać, że


2x|<math>x</math> jest liczbą parzystą.
# nic innego nie jest formułą.


musimy dowieść, że warunek ``<math>2</math> jest liczbą parzystą'' jest
Powyższa definicja mówi, że formułami nazywamy te napisy które dają
prawdziwy.
się skonstruować ze zmiennych zdaniowych przy pomocy spójników
<math>\Rightarrow</math> oraz <math>\neg</math>.


Pomiędzy zbiorem liczb parzystych a zbiorem wszystkich liczb
Zgodnie z powyższą definicją nie jest formułą napis <math>p\Rightarrow q</math>,
naturalnych występuje oczywista zależność. Każda liczba parzysta
gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy
jest liczbą naturalną, co, ujęte w języku zbiorów oznacza że każdy
napisać <math>(p\Rightarrow q)</math> możemy przyjąć że nie będzie konieczne
element zbioru liczb parzystych jest elementem zbioru liczb
pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić.
naturalnych. Zbiór liczb parzystych jest ''podzbiorem''
zbioru liczb naturalnych&nbsp;(a zbiór liczb naturalnych
''nadzbiorem'' zbioru liczb parzystych). Zapisujemy to w
następujący sposób


x|<math>x</math> jest liczbą parzystą"zbiór
ład
liczb naturalnych".
Poniższe napisy nie są formułami


Ogólniej, jeśli każdy element zbioru <math>A</math> jest elementem zbioru <math>B</math>
* <math>p \Rightarrow \Rightarrow q</math>
mówimy że zbiór <math>A</math> jest podzbiorem zbioru <math>B</math> i piszemy


A B.
* <math>\neg \neg \neg</math>


W takim przypadku mówimy, że pomiędzy zbiorami <math>A</math> i <math>B</math> zachodzi
* "ten napis na pewno nie jest formułą"
inkluzja.


W szczególności, dla dowolnego zbioru <math>A</math> zachodzi <math>A\subseteq A</math>.
* <math>(p \Rightarrow \neg q))</math>
Wspomnieliśmy wcześniej, że dwa zbiory są sobie równe wtedy i
tylko wtedy kiedy posiadają dokładnie takie same elementy. Fakt
ten możemy zapisać formalnie w następujący sposób


A <nowiki>=</nowiki> B  wtedy i tylko wtedy, kiedy  A B i
Poniższe napisy są formułami
B A.


Często zależy nam na określeniu znaczącym, że jeden zbiór jest
* <math>(p \Rightarrow (r \Rightarrow q))</math>
podzbiorem drugiego i że zbiory te nie są sobie równe. Używamy
wtedy symbolu <math>\varsubsetneq</math> w następujący sposób


A B  wtedy i tylko wtedy, kiedy  (
* <math>\neg \neg \neg q</math>
A B i nieprawda, że  A<nowiki>=</nowiki>B).


Dla każdej pary zbiorów poniżej określ czy są sobie równe, oraz
* <math>(p \Rightarrow \neg q)</math>
czy jeden z nich jest nadzbiorem drugiego
[#]
<math>\{2,3\}</math>, <math>\{x\,|\,\mbox{</math>x<math> dzieli liczbę </math>6<math>}\}</math>


<math>\mbox{"zbiór liczb naturalnych"}</math>, <math>\{x\,|\,\mbox{</math>2<math> dzieli </math>x^2<math>}\}</math>
ład
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
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>p</math>. Ile można skonstruować rożnych
formuł o rozmiarze 3?
 
; Solution.
: Oznaczmy przez <math>f_n</math> liczbę formuł o rozmiarze <math>n</math> (czyli liczbę
formuł w których jest <math>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ść:
 
<center><math>
 
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
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>p</math>. Mamy więc następujący wzór dla <math>f_2</math>
 
<center><math>
 
f_2= 1 \cdot f_1 + f_1 \cdot 1 +f_1 = 3 \cdot f_1
</math></center>
 
Z dwóch ostatnich wzorów otrzymujemy
 
<center><math>
 
f_3= 3 \cdot f_1 + (f_1)^2= 6+4 = 10
</math></center>
 
Skoro jest ich niewiele to możemy wszystkie wypisać
 
:# <math>\neg \neg \neg p</math>
 
:# <math>\neg \neg (p \Rightarrow p)</math>
 
:# <math>\neg (p \Rightarrow \neg p)</math>
 
:# <math>\neg (p \Rightarrow (p\Rightarrow p))</math>
 
:# <math>\neg (\neg p \Rightarrow  p)</math>
 
:# <math>\neg ((p\Rightarrow p) \Rightarrow  p)</math>
 
:# <math> (\neg p)\Rightarrow  (\neg p)</math>
 
:# <math> (\neg p)\Rightarrow  (p \Rightarrow p)</math>
 
:# <math> (p \Rightarrow p) \Rightarrow  (\neg p)</math>
 
:# <math> (p \Rightarrow p)\Rightarrow  (p \Rightarrow p)</math>
 
{Koniec æwiczenia {section}.{cwicz}}
 
Język logiki zdaniowej można równoważnie zdefiniować nie
używając nawiasów za pomocą Odwrotnej Notacji Polskiej
Odwrotna Notacja Polska.
 
==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:
Aksjomaty klasycznego rachunku zdań.
 
# <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>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
\psi) \Rightarrow \phi</math>
 
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
formuły.
 
===Reguła dowodzenia===
 
Przyglądnijmy się teraz jak posługujemy się implikacją we
wniskowaniu. W przykładzie z początku wykładu implikacja odpowiadała
konstrukcji językowej:
 
"'jeśli"' <math>\phi</math> "'to"' <math>\psi</math>.
 
W takim przypadku jeśli akceptujemy powyższą implikacjię jako zdanie
prawdziwe oraz jeśli zdanie <math>\phi</math> jako prawdziwe to powinniśmy
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
 
<center><math>
 
\frac{\phi \Rightarrow \psi, \phi}{\psi}.
</math></center>
 
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.
 
Ciąg formuł <math>\phi_0, \dots ,\phi_n</math> jest dowodem formuły <math>\psi</math>
wtedy i tylko wtedy, gdy:
 
# <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>.
 
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
<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 \Rightarrow \phi_i</math>.
 
Formułę nazywamy "twierdzeniem klasycznego rachunku zdań"
jeśli istnieje jej dowód  z aksjomatów klasycznego rachunku
zdań [[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]].
 
===Przykład===
 
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
[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]]. 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.
 
# <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 \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 \phi)</math> 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
[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]] 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 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 <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
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.
 
Dwuelementową matrycą boolowską nazywamy zbiór dwuelementowy
<math>\mathbb{B}=\{0,1\}</math> w którym 1 jest wyróżnioną wartością prawdy, wraz z
dwoma funkcjami odpowiadającymi za interpretacje spójników
<math>\Rightarrow</math> oraz <math>\neg</math> zdefiniowanymi następująco
 
<center><math>
 
\begintabular {|c|c c|}\hline
& 0 & 1 \\\hline
0 & 1 & 1 \\
1 & 0 & 1 \\\hline
\endtabular  \hspace{1cm}
\begintabular {|c|c|}\hline
</math>p<math> & </math> p<math> \\\hline
0 & 1  \\
1 & 0  \\\hline
\endtabular
</math></center>
 
Wartościowaniem nazywamy funkcję która przypisuje zmiennym
zdaniowym elementy zbioru <math>\mathbb{B}</math>. Wartościowanie zmiennych
można rozszerzyć na wartościowanie formuł interpretując spójniki
<math>\Rightarrow</math> oraz <math>\neg</math> jako funkcje zgodnie z tabelami
[[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]].
 
ład
 
Niech <math>v</math> będzie wartościowaniem zmiennych takim, że <math>v(p)=0,
v(q)=1, v(r)=0</math>. Wtedy
 
* 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>\neg p \Rightarrow r</math> jest wartościowana na  0 (czyli <math>v(\neg p \Rightarrow r)=0</math>)
 
ład
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Przy wartościowaniu <math>v</math> z przykładu [[##eg:wartosciowania|Uzupelnic eg:wartosciowania|]] jakie
wartości przyjmują następujące formuły
 
# <math>p \Rightarrow (q \Rightarrow r)</math>
 
# <math>p \Rightarrow (p \Rightarrow q)</math>
 
# <math>\neg \neg q \Rightarrow p</math>
 
# <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
 
; Solution.
: 
 
:# <math>v(p \Rightarrow (q \Rightarrow r))=1</math>
 
:# <math>v(p \Rightarrow (p \Rightarrow q))=1</math>
 
:# <math>v(\neg \neg q \Rightarrow p)=0</math>
 
:# <math>v((\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q))=0</math>
 
{Koniec æwiczenia {section}.{cwicz}}
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
# Podaj przykład wartościowania zmiennych tak aby poniższe formuły
były wartościowane na 0
 
## <math>p \Rightarrow (q \Rightarrow r)</math>
 
## <math>(\neg p \Rightarrow q)</math>
 
## <math>(p\Rightarrow q) \Rightarrow q</math>
 
# Podaj przykład wartościowania zmiennych tak aby poniższe formuły
były wartościowane na 1
 
## <math>\neg (p \Rightarrow q)</math>
 
## <math>\neg (\neg p \Rightarrow  \neg q)</math>
 
## <math>(\neg q\Rightarrow q) \Rightarrow (q \Rightarrow \neg q)</math>
 
; Solution.
: Wartościowania będziemy oznaczać przez <math>v</math>
 
:# 
 
:## <math>v(p)=1, v(q)=1, v(r)=0</math>
 
:## <math>v(p)=0,v(q)=0</math>
 
:## <math>v(p)=0,v(q)=0</math>
 
:# 
 
:## <math>v(p)=1,v(q)=0</math>
 
:## <math>v(p)=0,v(q)=1)</math>
 
:## <math>v(q)=1</math>
 
{Koniec æwiczenia {section}.{cwicz}}
 
===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. <math>p \Rightarrow p</math>).
Takie formuły będziemy nazywać "'tautologiami"'.
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Sprawdź czy poniższe formuły są tautologiami
 
# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>
 
# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
(\phi \Rightarrow \nu) \right)</math>
 
# <math>(\neg \phi \Rightarrow \psi) \Rightarrow (\neg \phi \Rightarrow \neg
\psi) \Rightarrow \phi</math>
 
# <math>((\phi \Rightarrow q) \Rightarrow p) \Rightarrow p</math>
 
{hint}{1}
; Hint .
: Spróbuj poszukać wartościowań dla których formuła przyjmuje
wartość 0
 
{hint}{1}
; Hint .
: Można też sprawdzić wszystkie możliwości wartościowań.
 
; Solution.
: 
 
{Koniec æwiczenia {section}.{cwicz}}
 
Nie przez przypadek pierwsze trzy formuły z poprzedniego zadania
odpowiadają aksjomatom klasycznego rachunku zdań
[[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]]. Okazuje się że istnieje ścisły związek
pomiędzy tautologiami a twierdzeniami klasycznego rachunku zdań. Mówi o tym ważny wynik Emil Post.
 
{{twierdzenie|[Uzupelnij]||
{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ń).
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Udowodnij że każde twierdzenie klasycznego rachunku zdań jest tautologią.
 
{hint}{1}
; Hint .
: Pokazaliśmy już w zadaniu
[[##zad:aksjomatyTatuologie|Uzupelnic zad:aksjomatyTatuologie|]], że aksjomaty są tautologiami.
Zacznij od pokazania, że zastosowanie reguły MP  do tautologii daje
tautologię.
{hint}{1}
; Hint .
: Udowodnij, twierdznie przez indukcję ze względu na długość
dowodu.
 
; Solution.
: 
 
{Koniec æwiczenia {section}.{cwicz}}
 
===Inne spójniki===
 
Do tej pory jedynymi rozważanymi spójnikami była implikacja i
negacja. W analogiczny sposób do [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]]
możemy wprowadzać kolejne spójniki. Często używane spójniki to
koniunkcja (spójnik "'i"') oznaczana przez <math>\wedge</math> oraz
alternatywa (spójnik "'lub"') oznaczana przez <math>\vee</math>, które
będziemy interpretować w następujący sposób:
 
<center><math>  
 
\begintabular {|c|c c|}\hline
& 0 & 1 \\\hline
0 & 0 & 0 \\
1 & 0 & 1 \\\hline
\endtabular  \hspace{1cm}
\begintabular {|c|c c|}\hline
& 0 & 1 \\\hline
0 & 0 & 1 \\
1 & 1 & 1 \\\hline
\endtabular
</math></center>
 
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ą
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
wartościowana na 1.
 
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>.
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Udowodnij, że następujące formuły są równoważne
 
# <math>\phi \vee \psi \equiv \neg \phi \Rightarrow \psi </math>
 
# <math>\phi \wedge \psi \equiv \neg (\phi \Rightarrow \neg \psi)</math>


<math>\{x\,|\, x^2 =1\}</math>, <math>\{x\,|\, x^3=1\}</math>
[:]
; Solution.
; Solution.
:[:]Rozwiązanie:
:
[#]
 
Zarówno <math>2</math>, jak i <math>3</math> dzielą <math>6</math>, a więc
:# Lewa strona jest fałszywa jedynie gdy <math>\phi</math> oraz
<math>\{2,3\}\subseteq\{x\,|\,\mbox{</math>x<math> dzieli liczbę </math>6<math>}\}</math>. Liczba <math>6</math>
<math>\psi</math> są wartościowane na 0. Prawa strona jest fałszywa
jest elementem lewego zbioru, a nie jest elementem prawego i dlatego
wtedy i tylko wtedy kiedy <math>\neg \phi</math> jest wartościowane na
zbiory te są od siebie różne. Odpowiedzią jest
1 oraz <math>\psi</math> jest wartościowane na 0 (to jedyna możliwość
<math>\{2,3\}\varsubsetneq\{x\,|\,\mbox{</math>x<math> dzieli liczbę </math>6<math>}\}</math>.
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.
 
:# 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
możliwości wartościowań i porównanie wyników.


Do zbioru liczb naturalnych należy <math>3</math>, które nie należy do zbioru
{Koniec æwiczenia {section}.{cwicz}}
<math>\{x\,|\,\mbox{</math>2<math> dzieli </math>x^2<math>}\}</math>&nbsp;(ponieważ <math>2</math> nie dzieli <math>9=3^2</math>).
Równocześnie do prawego zbioru należy liczba <math>-2</math> która nie jest liczbą
naturalną. Żaden z wymienionych tu zbiorów nie jest podzbiorem drugiego.


Lewy zbiór to, oczywiście zbiór <math>\{-1,1\}</math>, a prawy to
Z powyższego zadania wynika, że każdą formułę w której występują
jednoelementowy zbiór <math>\{1\}</math>. W tym przypadku odpowiedzią jest
spójniki <math>\wedge</math> lub <math>\vee</math> można zastąpić równoważną formułą w
<math>\{x\,|\, x^2 =1\}\varsupsetneq\{x\,|\, x^3=1\}</math>.
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
skrótami w zapisywaniu formuł.


Najczęstszymi operacjami wykonywanymi na zbiorach są operacje
Aby się oswoić z własnościami spójników prześledzimy szereg ich
''sumy'',''przecięcia'' i ''różnicy''. Sumą dwóch
praw.
zbiorów <math>A</math> i <math>B</math> jest zbiór oznaczony przez <math>A\cup B</math> w skład
którego wchodzą wszystkie element zbioru <math>A</math>, wszystkie elementy
zbioru <math>B</math> i żadne elementy spoza tych zbiorów.


A B <nowiki>=</nowiki> x| x A  lub  x B
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}


{obra}{1}{{Obrazek {section}.{obra}}}standardowy obrazek ilustrujący unię zbiorów Podobnie
Udowodnij następujące równoważności
definiujemy przecięcie zbiorów


A B <nowiki>=</nowiki> x| x A  i  x B
# <math>\neg \neg p \equiv p</math>


{obra}{1}{{Obrazek {section}.{obra}}}standardowy obrazek ilustrujący przecięcie zbiorów oraz
# <math>p\Rightarrow q \equiv \neg p \vee q</math>
różnicę zbiorów


A B <nowiki>=</nowiki> x| x A i  x B.
# <math>p \Rightarrow (q \Rightarrow r) \equiv (p \wedge q) \Rightarrow r</math>


{obra}{1}{{Obrazek {section}.{obra}}}standardowy obrazek ilustrujący różnicę zbiorów
# <math>\neg( p \wedge q) \equiv \neg p \vee \neg q</math>


Dla następujących par zbiorów ustal zawieranie, lub równość
# <math>\neg( p \vee q) \equiv \neg p \wedge \neg q</math>
[#]
 
<math>A=\mbox{"zbiór liczb naturalnych"}\setminus\{x\,|\, \mbox{liczba nieparzysta, większa niż 2 dzieli </math>x<math>}\}</math> i drugi zbiór <math>B=\{2^n\,|\,\mbox{gdzie </math>n<math> jest liczbą naturalną}\}</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 \Rightarrow q) \Rightarrow (\neg p \Rightarrow \neg q)</math>


<math>A=\{x\,|\, \mbox{liczba 2 dzieli </math>x<math>}\}\cup\{x\,|\, \mbox{liczba 3 dzieli </math>x<math>}\}</math> i zbiór
<math>B=\{x\,|\, \mbox{liczba 6 dzieli </math>x<math>}\}</math>.
[:]
; Solution.
; Solution.
:[:]Rozwiązanie:
: Przedstwiamy przykładowe dowody kilku pierwszych równoważności.
[#]
 
Każda liczba postaci <math>2^n</math> jest liczbą naturalną
:# Jeśli <math>p</math> jest wartościowane na 1, to zgodnie z tabelą dla negacji [[##eq:tabeleInterpretacjiKRZ|Uzupelnic eq:tabeleInterpretacjiKRZ|]]
niepodzielną przez żadną liczbę nieparzystą większą niż
<math>\neg p</math> jest wartościowane na 0 i <math>\neg \neg p</math> jest wartościowane na 1. Jeśli <math>p</math> jest wartościowane
<math>2</math>, a więc <math>B\subseteq A</math>. Każda liczba naturalna, która
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ą
nie dzieli się przez żadną liczbę nieparzystą posiada tylko
te same wartości dla każdego wartościowania więc są równoważne.
jeden dzielnik pierwszy <math>2</math>. W związku z tym każda z liczb
 
w <math>A</math> występuje również w <math>B</math>. W związku z tym <math>A=B</math>.
:# Jedyną możliwością aby lewa strona była fałszywa jest
aby <math>p</math> było wartościowane na 1, a <math>q</math> na 0. Prawa
stona jest fałszywa jedynie gdy <math>\neg p</math> oraz <math>q</math> są wartościowane
na 0. Czyli prawa strona jest fałszywa jedynie
gdy <math>p</math> jest wartościowane na 1 i <math>q</math> na 0. Formuły są więc
równoważne.


Każda liczba która jest podzielna przez <math>6</math> dzieli się
:# Analogicznie do poprzedniego punktu łatwo się
również przez <math>2</math> co dowodzi, że <math>B\subseteq A</math>. Zawieranie w
przekonać, że jedynym wartościowaniem które falsyfikuje lewą
drugą stronę nie zachodzi ponieważ liczba <math>9\in A</math> i <math>9\notin
stronę jest takie które wartościuje <math>p</math> i <math>q</math> na 1 oraz <math>r</math>
B</math>.
na 0. Tą samą własność ma formuła po prawej stronie, więc
formuły są równoważne.


Dla dowolnego zbioru <math>A</math> zachodzi <math>A\cup A = A</math> i <math>A\cap A = A</math>.
:# Przykład rozwiązania przez rozważenie wszystkich
Zbiór który otrzymujemy jako wynik operacji <math>A\setminus A</math> jest
możliwości
''zbiorem pustym''. Na mocy definicji różnicy zbiorów
elementami zbioru <math>A\setminus A</math> są wyłącznie te elementy <math>A</math>,
które nie należą do <math>A</math>. Takie elementy nie istnieją -- żaden
element ze zbioru <math>A</math> nie należy do <math>A\setminus A</math> i żaden element
spoza <math>A</math> nie należy do tego zbioru. Zbiór pusty jest oznaczany
przez <math>\emptyset</math>. Odejmowanie zbiorów od samych siebie nie jest
jedynym sposobem na otrzymanie zbioru pustego.


1,2,2006"zbiór liczb naturalnych"<nowiki>=</nowiki>"zbiór
<center><math>
psów""zbiór wszystkich zwierząt"


Zbiór po lewej stronie nierówności jest równy zbiorowi po prawej
\begintabular {|c|c|c|c|c|c|c|}\hline
stronie nierówności. Każdy element zbioru po prawej stronie jest
</math>p<math> & </math>q<math> & </math>p q<math> & </math> (p q)<math>& </math> p<math> & </math> q<math>&  </math>  p  q<math>\\\hline
również elementem zbioru po lewej stronie nierówności i vice versa
0 & 0 & 0 & 1 & 1 & 1 & 1\\
dlatego, że żaden z tych zbiorów nie posiada elementów.
0 & 1 & 0 & 1 & 1 & 0 & 1\\
1 & 0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 1 & 0 & 0 & 0 & 0\\\hline
\endtabular  \hspace{1cm}
</math></center>


Niestety, podejście zaproponowane przez '''Georg Cantor''' i uściślone przez
W pierwszych dwóch kolumnach są zapisane wartościowania
'''Friedrich Frege''' posiada błędy. Jedną z pierwszych osób które zwróciły uwagę
zmiennych <math>p</math> i <math>q</math> a w pozostałych odpowiadające im wartościowania
na niedociągnięcia tej teorii jest '''Bertrandt Russell'''. Zgodnie z zasadami
formuł zbudowanych z tych zmiennych. Ponieważ kolumna 4 i 7
zaproponowanymi przez '''Georg Cantor''' można zdefiniować dowolny zbiór.
są identyczne to formuły z zadania są równoważne.
Zdefiniujmy więc zbiór


Z <nowiki>=</nowiki> A| A A.
:# W równoważności z poprzedniego punktu, podstawiąjąc za <math>p</math>
formułę <math>\neg p</math> oraz za <math>q</math> formułę <math>\neg q</math> otrzymamy
równoważność


Zbiór <math>Z</math> składa się ze zbiorów, które nie są swoimi własnymi
<center><math>
elementami. Paradoks zaproponowany przez '''Bertrandt Russell''' polega na tym,
że pytanie czy <math>Z</math> jest swoim własnym elementem prowadzi do
sprzeczności. Jeśli <math>Z\in Z</math> to, zgodnie z definicją zboru <math>Z</math>
otrzymujemy <math>Z\notin Z</math> co jest sprzecznością z założeniem. Jeśli
<math>Z\notin Z</math>, to <math>Z</math> spełnia warunek na przynależność do <math>Z</math> i w
związku z tym <math>Z\in Z</math> co jest kolejną sprzecznością. Definicja
zbioru zaproponowana przez '''Georg Cantor''' prowadzi do powstania
logicznych paradoksów. Okazuje się że pytanie co jest zbiorem jest
trudniejsze niż wydawało się matematykom końca XIX wieku.


W dalszej części wykładu przedstawimy właściwe podejście do teorii
\neg( \neg p \wedge \neg q) \equiv \neg \neg p \vee \neg \neg
mnogości. Podejście to jest oparte o część logiki zwaną rachunkiem
q.
predykatów. Podejście to zostało zaproponowane przez '''Ernst Zermelo''' na
</math></center>
początku XX wieku i ma na celu dostarczenie spójnej teorii zbiorów
o mocy podobnej to naiwnej teorii, przy równoczesnym uniknięciu
paradoksów. Aksjomatyczna teoria mocy definiuje bardzo dokładnie
które kolekcje obiektów są zbiorami. W szczególności paradoks
zaproponowany przez '''Bertrandt Russell''' nie pojawia się w aksjomatycznej
teorii zbiorów, ponieważ zbiór zdefiniowany powyżej jako <math>Z</math> w
niej nie istnieje.


=="Naiwna" indukcja==
Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony
otrzymujemy


Zasada indukcji matematycznej jest o prawie trzysta lat starsza
<center><math>
niż teoria mnogości. Pierwszy dowód indukcyjny pojawił się w pracy
'''Francesco Maurolico''' w 1575 roku. W pracy tej autor wykazał, że suma <math>n</math>
pierwszych liczb nieparzystych równa się <math>n^2</math>.


Aby zastosować zasadę indukcji matematycznej należy wykazać dwa
\neg( \neg p \wedge \neg q) \equiv  p \vee    q.
fakty:
</math></center>
[*]
hipoteza jest prawdziwa dla <math>n=1</math>;


jeśli hipoteza jest prawdziwa dla <math>n</math> to jest również prawdziwa dla
Negując tą równoważność obustronnie otrzymamy
<math>n+1</math>.
Drugi z powyższych punktów musi być prawdą dla wszystkich <math>n\geq
1</math>. Jeśli oba fakty są prawdą to hipoteza jest prawdziwa dla
wszystkich liczb naturalnych większych od <math>1</math>. Rozumowanie które
stoi za tym wnioskiem wygląda następująco:
[#]
hipoteza jest prawdziwa dla <math>n=1</math> na podstawie podstawy indukcji,


hipoteza jest prawdziwa dla <math>n=2</math>, ponieważ jest prawdziwa dla <math>1</math>
<center><math>
i po zastosowaniu kroku indukcyjnego również dla <math>2</math>,


hipoteza jest prawdziwa dla <math>n=3</math>; w poprzednim punkcie pokazaliśmy,
\neg \neg( \neg p \wedge \neg q) \equiv\neg(  p \vee    q).
że jest prawdziwa dla <math>2</math> i na podstawie kroku indukcyjnego jest również
</math></center>
prawdziwa <math>3</math>


i tak dalej.
Stosując równoważność z pierwszego punktu do lewej strony
Zasadę indukcji matematycznej można porównać do domina. Aby mieć
otrzymamy szukaną równoważność.
pewność że przewrócone zostaną wszystkie klocki wystarczy wykazać,
że przewrócony zostanie pierwszy klocek i że każdy klocek pociąga
za sobą następny. {obra}{1}{{Obrazek {section}.{obra}}}nieskończone domino ponumerowanych
liczbami naturalnymi klocków w trakcie przewracania


Dowód indukcyjny przedstawiony przez '''Francesco Maurolico''' pokazuje, że suma
{Koniec æwiczenia {section}.{cwicz}}
pierwszych <math>n</math> liczb nieparzystych jest równa <math>n^2</math>.
[*]
Jeśli <math>n=1</math> to pierwsza liczba nieparzysta <math>1</math> jest równa <math>1^2</math>.


Jeśli hipoteza jest prawdą dla <math>n</math>, to znaczy że suma pierwszych <math>n</math>
{cwicz}{1}
liczb nieparzystych równa się <math>n^2</math>. Bardziej formalnie 
{hint}{0}
1+3++(2n-1) <nowiki>=</nowiki> n^2.
{Æwiczenie {section}.{cwicz}}


tak więc suma pierwszych <math>n+1</math> liczb nieparzystych
Sprawdź które z następujących formuł są tautologiami
<math>1+3+\dotsb+(2n-1)+(2(n+1)-1)</math>, przy użyciu założenia powyżej może
być zapisana jako


1+3++(2n-1)+(2(n+1)-1) <nowiki>=</nowiki> n^2 +(2(n+1)-1)<nowiki>=</nowiki> n^2+2n+1<nowiki>=</nowiki>
# <math>( (p \vee r)\wedge( q \vee \neg r) )\Rightarrow (p \vee q)</math>
{(n+1)}^2.


Krok indukcyjny został dowiedziony.
# <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 q) \Rightarrow ( (p \wedge r)\vee( q \wedge \neg r)
)</math>


Wykaż, że suma pierwszych <math>n</math> liczb naturalnych jest równa
<math>\frac{1}{2}n(n+1)</math>. [:]
; Solution.
; Solution.
:[:]Aby udowodnić wzór na sumę <math>n</math>
:
pierwszych liczb naturalnych posłużymy się indukcją.
 
[*]
:# Spróbujmy znaleźć wartościowanie które falsyfikuje tą
Dla <math>n=1</math> mamy <math>\frac{1}{2}\cdot 1\cdot 2 = 1</math>.
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>p</math> jak i <math>q</math> są
fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji,
czyli formułą
 
<center><math>
 
(p \vee r)\wedge( q \vee \neg r).
</math></center>
 
Jeśli teraz ustalimy <math>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ą.
 
:# Formuła nie jest tautologią. Wystarczy wartościować <math>p</math> i
<math>r</math> na prawdę i <math>q</math> na fałsz.
 
:# Formuła nie jest tautologią. Wystarczy wartościować <math>p</math> i
<math>r</math> na prawdę i <math>q</math> na fałsz.
 
:# Przykład rozwiązania przez rozważenie wszystkich
możliwości
 
<center><math>
 
\begintabular {|c|c|c|c|c|c|c|c|}\hline
</math>p<math> & </math>q<math> & </math>r<math> &</math>(p  q)<math> &</math> (p  r)<math>&</math> ( q  r)<math>
&</math> (p  r)( q  r)<math>& </math>(p  q)  ( (p  r)( q  r))<math>\\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 & 0& 1 \\
0 & 1 & 0 & 0 & 0 & 1 & 1& 1 \\
0 & 1 & 1 & 0 & 0 & 0 & 0& 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0& 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1& 1 \\
1 & 1 & 0 & 1 & 0 & 1 & 1& 1 \\
1 & 1 & 1 & 1 & 1 & 0 & 1& 1 \\\hline
\endtabular  \hspace{1cm}
</math></center>
 
W kolumnie odpowiadającej badanej formule są same 1, więc
jest ona tautologią.
 
{Koniec æwiczenia {section}.{cwicz}}
 
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.
 
W poniższej tabeli przedstawiamy wszystkie spójniki binarne.


Zakładamy, że wzór jest prawdziwy dla <math>n</math>. W związku z tym do sumy
<center><math>


1+2++n+(n+1) <nowiki>=</nowiki>
\begintabular {|c|c|c|c|c|c||c|}\hline
Numer & </math>p<nowiki>=</nowiki>0<math> &</math> p<nowiki>=</nowiki>0<math> &</math> p<nowiki>=</nowiki>1<math> &</math> p<nowiki>=</nowiki>1<math> && \\
funkcji& </math>q<nowiki>=</nowiki>0<math> & </math>q<nowiki>=</nowiki>1<math> & </math>q<nowiki>=</nowiki>0<math> & </math>q<nowiki>=</nowiki>1<math> && \\ \hline
0 & 0 & 0 & 0 & 0 && </math>F<math>\\
1 & 0 & 0 & 0 & 1 && \\
2 & 0 & 0 & 1 & 0 && </math>(p  q)<math>\\
3 & 0 & 0 & 1 & 1 && </math>p<math> \\
4 & 0 & 1 & 0 & 0 && </math> (q p)<math> \\
5 & 0 & 1 & 0 & 1 && </math>q<math> \\
6 & 0 & 1 & 1 & 0 && </math>XOR<math> \\
7 & 0 & 1 & 1 & 1 &&  \\
8 & 1 & 0 & 0 & 0 && </math>NOR<math> \\
9 & 1 & 0 & 0 & 1 &&  \\
10& 1 & 0 & 1 & 0 && </math> q<math> \\
11& 1 & 0 & 1 & 1 && </math> q  p<math> \\
12& 1 & 1 & 0 & 0 && </math>  p <math>\\
13& 1 & 1 & 0 & 1 && </math> p  q <math>\\
14& 1 & 1 & 1 & 0 && </math> NAND<math> \\
15& 1 & 1 & 1 & 1 && </math>T <math>\\\hline
\endtabular  \hspace{1cm}
</math></center>


stosujemy założenie indukcyjne
Spójnik binarny <math>\circ</math> będziemy nazywać "przemiennym" jeśli zachodzi
następująca równoważność


(1+2++n ) +(n+1) <nowiki>=</nowiki> {1}{2}n(n+1) + (n+1) <nowiki>=</nowiki>
<center><math>  


i po paru prostych przekształceniach otrzymujemy
p \circ q \equiv q \circ p
</math></center>


<nowiki>=</nowiki> {1}{2}n(n+1) +{1}{2}2(n+1) <nowiki>=</nowiki> {1}{2}(n+1)(n+2)
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}


co dowodzi kroku indukcyjnego.
Sprawdź następujące równoważności
Na zasadzie indukcji matematycznej dowiedliśmy wzór na sumę <math>n</math>
 
pierwszych liczb naturalnych.
# <math>x NAND y \equiv \neg (x \wedge y)</math>
 
# <math>x NOR y \equiv \neg (x \vee y)</math>
 
# <math>x XOR y \equiv \neg (x \Leftrightarrow y)</math>


Wykaż, że suma kwadratów pierwszych <math>n</math> liczb
naturalnych jest równa <math>\frac{1}{6}n(n+1)(2n+1)</math>. [:]
; Solution.
; Solution.
:[:]Aby
:
wykazać prawdziwość wzoru powyżej postępujemy jak
w poprzednim zadaniu.
[*]
Dla <math>n=1</math> mamy <math>\frac{1}{6}\cdot 1\cdot 2\cdot 3 = 1</math> co dowodzi
podstawy indukcji.


Zakładamy że wzór jest prawdziwy dla <math>n</math> to jest, że
{Koniec æwiczenia {section}.{cwicz}}


1^2+2^2++n^2 <nowiki>=</nowiki> {1}{6}n(n+1)(2n+1).
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}


Korzystając z tego faktu przekształcamy
Ile spójników binarnych jest przemiennych? Wypisz je wszystkie.


1^2+2^2++n^2 + {(n+1)}^2<nowiki>=</nowiki> {1}{6}n(n+1)(2n+1) +
{hint}{1}
{(n+1)}^2 <nowiki>=</nowiki>
; Hint .
: Wygodnie jest reprezentować spójniki binarne w tabeli
kwadratowej. Na przykład alternatywę
zdefiniowaliśmy jako


i dalej do
<center><math>


{1}{6}(n+1)(n(2n+1)+6(n+1))<nowiki>=</nowiki>{1}{6}(n+1)(2n^2+7n+6)<nowiki>=</nowiki>
\begintabular {|c|c c|}\hline
{1}{6}(n+1)(n+2)(2(n+1)+1)
& 0 & 1 \\\hline
0 & 0 & 1 \\
1 & 1 & 1 \\\hline
\endtabular .
</math></center>


co dowodzi kroku indukcyjnego.
Jaką własność musi posiadać tabela aby spójnik definiowany przez nią był
Podobnie jak w poprzednim przykładzie zasada indukcji
przemienny?
matematycznej gwarantuje, że wzór jest prawdziwy dla wszystkich
liczb naturalnych.


Wykaż, że dla <math>n\geq 1</math> zachodzi <math>4|3^{2n-1}+1</math>. [:]
; Solution.
; Solution.
:[:]Jak
: Dla przemienności spójnika <math>\circ</math> istotne jest aby <math> 1\circ 0 =  0 \circ 1</math>. Dla pozostałych
poprzednio stosujemy zasadę indukcji matematycznej.
przypadków wartościowań równoważnośc [[##eq:przemienność|Uzupelnic eq:przemienność|]]
[*]
jest zawsze spełniona. Każdy spójnik binarny możemy
Dla <math>n=1</math> mamy <math>3^{2n-1} + 1 = 3^1 +1 = 4</math> jest podzielne przez <math>4</math>.
zdefiniować za pomocą tabelki kwadratowej, np. alternatywę
zdefiniowaliśmy jako
 
<center><math>
 
\begintabular {|c|c c|}\hline
& 0 & 1 \\\hline
0 & 0 & 1 \\
1 & 1 & 1 \\\hline
\endtabular .
</math></center>
 
Warunek przemienności oznacza, że wartość w polu o
współrzędnych <math>(0,1)</math> jest równa wartości w polu o
współrzędnych <math>(1,0)</math>. Takich tabel jest 8, więc mamy 8
spójników przemiennych. Nietrudno je teraz odnaleźć w tabeli
[[##defn:spójniki|Uzupelnic defn:spójniki|]]. Są to
 
:# <math>F</math>
 
:# <math>\wedge</math>
 
:# <math>XOR</math>
 
:# <math>\vee</math>
 
:# <math>NOR</math>
 
:# <math>\Leftrightarrow</math>
 
:# <math>NAND</math>


Zakładamy że podzielność zachodzi dla <math>n</math>.
:# <math>T</math>
Pokażemy że <math>3^{2(n+1)-1}+1</math> jest podzielne przez <math>4</math>. Przekształcamy


3^{2(n+1)-1}+1 <nowiki>=</nowiki> 3^{2n-1+2} + 1 <nowiki>=</nowiki> 9 3^{2n-1} + 1<nowiki>=</nowiki>
{Koniec æwiczenia {section}.{cwicz}}


wprowadzamy sztuczny czynnik
Spójnik binarny <math>\circ</math> będziemy nazywać "łącznym" jeśli zachodzi
następująca równoważność


<nowiki>=</nowiki>9 (3^{2n-1} +1 -1) + 1 <nowiki>=</nowiki> 9 (3^{2n-1} +1 -1) + 1 <nowiki>=</nowiki>
<center><math>  
9 (3^{2n-1} +1) -9 + 1 <nowiki>=</nowiki> 9 (3^{2n-1} +1) -8.


Zarówno <math>(3^{2n+1} +1)</math>&nbsp;(na mocy założenia indukcyjnego) jak i <math>8</math>
p \circ (q \circ r) \equiv    (p \circ q) \circ r.
są podzielne przez <math>4</math>, a wiec ich różnica również. W ten sposób
</math></center>
udowodniliśmy krok indukcyjny.


Często bardzo niepraktyczne jest używanie indukcji w jej
Jeśli spójnik <math>\circ</math> jest łączny to dowolne dwie formuły, które są zbudowane
podstawowej formie. Używa się wtedy indukcji, która w pierwszym
jedynie ze spójników <math>\circ</math> są równoważne jeśli występuje w nich tyle samo spójników.
kroku nie zaczyna się od <math>n=1</math>, ale <math>n=0</math>, <math>n=2</math> lub dowolnej
Dlatego dla łącznych spójników binarnych pomija się często nawiasy.
innej liczby naturalnej. W takim przypadku drugi krok indukcyjny
nie musi działać dla wszystkich <math>n</math> a wystarczy by działał dla <math>n</math>
większych lub równych od liczby którą wybraliśmy w pierwszym
kroku. Końcowy dowód indukcyjny pokaże, że dana hipoteza nie jest
prawdziwa dla wszystkich liczb naturalnych, a jedynie dla liczb
większych od tej wybranej na pierwszy krok indukcyjny.


Jako przykład pokażemy, że <math>n!>2^n</math>. Po pierwsze nierówność ta nie
{cwicz}{1}
zachodzi dla <math>1,2,3</math>, więc nie można rozpocząć kroku indukcyjnego
{hint}{0}
od <math>n=1</math>. Indukcja będzie wyglądać następująco.
{Æwiczenie {section}.{cwicz}}
[*]
Hipoteza jest prawdą dla <math>n=4</math>, ponieważ <math>4!=24>16=2^4</math>.


Jeśli hipoteza jest prawdą dla <math>n</math> i jeśli <math>n\geq 4</math> to
Udowodnij, że następujące spójniki są łączne


(n+1)!<nowiki>=</nowiki> n! (n+1)>2^n(n+1)>2^{n+1}
# <math>\vee</math>
 
# <math>\wedge</math>
 
# <math>\Leftrightarrow</math>
 
# <math>XOR</math>


gdzie pierwsza nierówność pochodzi z założenia indukcyjnego, a
druga z faktu, że dowodzimy krok indukcyjny dla liczb większych
niż <math>4</math>.
W tym ćwiczeniu dowodzimy wariant nierówności Bernoulliego. Dla dowolnego <math>x</math> takiego, że <math>x> -1</math> i <math>x\neq 0</math> i dla dowolnego <math>n\geq 2</math> zachodzi <math>{(1+x)}^n> 1+nx</math>.
[:]
; Solution.
; Solution.
:[:]Rozwiązanie:
:
[*]
 
Nierówność ostra nie jest prawdą dla <math>n=0</math>, ani dla
:# Formuła <math>(p \vee q) \vee r</math> jest fałszywa jedynie
<math>n=1</math>. Krok indukcyjny zaczniemy od <math>2</math>. Wtedy
wtedy gdy <math>p</math>,<math>q</math> i <math>r</math> są wartościowane na fałsz. Tak
<math>{(1+x)}^2=1+2x+x^2>1+2x</math>, gdzie ostatnia nierówność bierze
samo jest dla formuły <math>p \vee( q \vee r )</math> więc są one
się z faktu, że <math>x\neq 0</math>.
równoważne.
 
:# Formuła <math>(p \wedge q) \wedge r</math> jest prawdziwa jedynie
wtedy gdy <math>p</math>,<math>q</math> i <math>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.
 
:# Zbadamy równoważność formuł <math>(p \Leftrightarrow q) \Leftrightarrow r</math>
i <math> p \Leftrightarrow(q \Leftrightarrow r)</math> za pomocą tabeli
 
<center><math>
 
\begintabular {|c|c|c|c|c|c|c|}\hline
</math>p<math> &</math> q<math> &</math> r <math>&</math>(p  q)<math> & </math>(p  q)  r<math>& </math>(q  r )<math>&</math> p (q  r)<math>\\\hline
0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
\endtabular  \hspace{1cm}
</math></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.
 
:# ...


Zakładamy teraz, że nierówność jest prawdziwa dla <math>n</math>, czyli, że dla dowolnego <math>x</math> takiego, że <math>0\neq x> -1</math> mamy
{Koniec æwiczenia {section}.{cwicz}}


{(1+x)}^n> 1+nx.
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>.
ład
W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego


Przekształcając nierówność dla <math>n+1</math> otrzymujemy
<center><math>


{(1+x)}^{(n+1)}<nowiki>=</nowiki>{(1+x)}^n(1+x)>(1+nx)(1+x)<nowiki>=</nowiki>1+(n+1)x +x^2
\begintabular {|c c c|c||}\hline
1+(n+1)x,
</math>p<math> & </math>q<math> & </math>r<math> &</math>(p, q,r)<math> \\\hline
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 \\\hline
\endtabular  \hspace{1cm}
</math></center>


gdzie otrzymujemy ostrą nierówność dzięki założeniu indukcyjnemu i
ład
faktowi, że <math>x\neq -1</math>. W ten sposób krok indukcyjny został
udowodniony.


'''Liczby Fibonacciego''' zdefiniowane są następująco
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}


f_1<nowiki>=</nowiki>1, f_2<nowiki>=</nowiki>1 oraz  f_i<nowiki>=</nowiki>f_{i-2}+f_{i-1}  dla  i>3.
Udowodnij, że różnych spójników <math>k</math>-argumentowych jest dokładnie
<math>2^{2^k}</math>.


Udowodnij, że dla dowolnego <math>n\geq 2</math> liczby <math>f_n</math> i <math>f_{n-1}</math> są
względnie pierwsze. [:]
; Solution.
; Solution.
:[:]Dowód przez indukcję matematyczną
:
[*]
 
Twierdzenie jest prawdą dla <math>n=2</math> ponieważ <math>f_2</math> i <math>f_1</math> są
{Koniec æwiczenia {section}.{cwicz}}
względnie pierwsze.
 
==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
<math>\mathbb{B}</math>. Na przykład formuła <math>p \Rightarrow (q\Rightarrow r)</math> wyznacza funkcję
<math>f_{p \Rightarrow (q\Rightarrow r)}</math> opisaną poniższą tabelą
 
<center><math>
 
\begintabular {|c|c|c|c|}\hline
p & q & r & </math>f_{p  (q r)}<math> \\\hline
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 \\\hline
\endtabular
</math></center>
 
Mówimy, wtedy że formuła <math>\phi</math> definuje funkcję <math>f_{\phi}</math>.
 
Skończony zbiór funkcji boolowskich <math>\Gamma</math> 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 <math>\Gamma</math>.
 
{{twierdzenie|[Uzupelnij]||
 
Zbiór <math>\{\wedge, \vee, \neg\}</math> jest funkcjonalnie pełny.
}}
 
{{dowod|[Uzupelnij]||
 
}}
 
{{twierdzenie|[Uzupelnij]||
 
Zbiory <math>\{\wedge,  \neg\}</math>, <math>\{\vee,  \neg\}</math> są funkcjonalnie pełne.
}}
 
{{dowod|[Uzupelnij]||
 
}}


Zakładamy że twierdzenie jest prawdą dla <math>n</math>. Rozpatrzmy wspólny
Udowodnij, że zbiór <math>\{\Rightarrow, \neg\}</math> jest funkcjonalnie
dzielnik liczb <math>f_{n+1}</math> i <math>f_n</math> i oznaczmy go przez <math>k</math>. Jeśli <math>k</math>
pełny.
dzieli <math>f_{n+1}</math> i równocześnie <math>f_n</math> to <math>k | f_{n+1}-f_n</math>. Korzystając z
definicji liczb Fibbonaciego otrzymujemy
<math>f_{n+1}-f_n=f_n+f_{n-1}-f_n=f_{n-1}</math>.
W związku z czym <math>k</math> jest wspólnym dzielnikiem liczb <math>f_n</math> i <math>f_{n-1}</math>,
więc na mocy założenia indukcyjnego mówiącego, że liczby te są względnie
pierwsze, jest równy <math>1</math>. Pokazaliśmy,
że każdy wspólny dzielnik <math>f_{n+1}</math> i <math>f_n</math> jest równy <math>1</math>, a więc liczby
te są względnie pierwsze. Krok indukcyjny został pokazany.


Kolejnym uogólnieniem zasady indukcji matematycznej jest indukcja,
{{twierdzenie|[Uzupelnij]||
w której w drugi kroku indukcyjnym zakładamy, że hipoteza jest
prawdą dla wszystkich liczb mniejszych niż <math>n</math> i dowodzimy, że
jest również prawdziwa dla <math>n+1</math>.


Jako przykład udowodnimy, że każda liczba naturalna większa niż
Zbiór <math>\{NOR\}</math> jest funkcjonalnie pełny.
<math>2</math> jest produktem jednej, lub więcej liczb pierwszych.
}}
[*]
Hipoteza jest prawdą dla <math>n=2</math> ponieważ <math>2</math> jest liczbą pierwszą.


Zakładamy że hipoteza jest prawdziwa dla liczb od <math>2</math> do
Udowodnij, że zbiór <math>\{NAND\}</math> jest funkcjonalnie pełny.
<math>n</math>. Weźmy liczbę <math>n+1</math>, jeśli <math>n+1</math> jest liczbą pierwszą, to
hipoteza jest udowodniona. Jeśli <math>n+1</math> nie jest liczbą
pierwszą, to <math>n+1=k\cdot l</math> gdzie <math>2\leq k,l\leq n</math>. Założenie
indukcyjne gwarantuje, że 
k<nowiki>=</nowiki>p_1 p_2 p_i i l<nowiki>=</nowiki>q_1
q_2 q_j


gdzie <math>p_1,\dotsc,p_i,q_1,\dotsc,q_j</math> są liczbami pierwszymi. W
{cwicz}{1}
związku z tym
{hint}{0}
{Æwiczenie {section}.{cwicz}}


n+1<nowiki>=</nowiki>p_1 p_2 p_i q_1
Zdefiniuj alternatywę przy pomocy samej implikacji.
q_2 q_j


i krok indukcyjny jest udowodniony.
Udowodnij, że każda liczba naturalna większa niż
<math>1</math> może być przedstawiona jako suma liczb Fibonacciego tak, że
żadna liczba nie występuje w tej sumie więcej niż raz. [:]
; Solution.
; Solution.
:[:]Przedstawimy dowód przez indukcję.
: Łatwo sprawdzić że formuła <math>p \Rightarrow (p \Rightarrow q)</math> jest równoważna
[*]
formule <math>p\vee q</math>.
Dla <math>n=1</math> mamy <math>f_2=1</math>.


Zakładamy że każda liczba mniejsza lub równa <math>n</math> może być
{Koniec æwiczenia {section}.{cwicz}}
przedstawiona w sposób opisany powyżej. Jeśli liczba <math>n+1</math> jest
liczbą Fibonacciego to krok indukcyjny jest już dowiedziony, jeśli
nie to znajdujemy największą liczbę Fibonacciego mniejszą od <math>n+1</math>
-- oznaczmy tą liczbę <math>f_k</math>. Liczba <math>n+1-f_k</math> jest mniejsza niż
<math>n</math> więc, na mocy założenia indukcyjnego, posiada reprezentację
jako suma liczb Fibonacciego


n+1-f_k<nowiki>=</nowiki>f_{l_0}++f_{l_i}
Jakie funkcje binarne da się zdefiniować przy pomocy samej
implikacji?


tak, że każda z liczb w tej reprezentacji występuje co najwyżej
{cwicz}{1}
raz. Oczywiście
{hint}{0}
{Æwiczenie {section}.{cwicz}}


n+1 <nowiki>=</nowiki> f_k+f_{l_0}++f_{l_i}
Udowodnij, że poniższe zbiory nie są funkcjonalnie pełne


i pozostaje wykazać, że <math>f_k</math> nie występuje pośród liczb
# <math>\{\wedge\}</math>
<math>f_{l_0},\dotsc,f_{l_i}</math>. Skoro <math>f_k</math> było największą liczbą
Fibonacciego mniejszą niż <math>n+1</math> to <math>f_{k+1}>n+1</math> a więc
<math>f_{k-1}=f_{k+1}-f_k>n+1-f_k</math>. W związku z tym liczby
<math>f_{l_0},\dotsc,f_{l_i}</math> są silnie mniejsze niż <math>f_{k-1}</math> i żadna
z nich nie może być równa <math>f_k</math>. W ten sposób krok indukcyjny
został dowiedziony.


Znajdź błąd w poniższym dowodzie indukcyjnym. Dowodzimy
# <math>\{\vee\}</math>
indukcyjnie twierdzenia, że wszystkie liczby są parzyste.
 
[*]
# <math>\{\Leftrightarrow\}</math>
Twierdzenie jest prawdą dla <math>n=0</math> ponieważ <math>0</math> jest liczbą parzystą.
 
# <math>\{XOR\}</math>


Zakładamy, że twierdzenie jest prawdą dla wszystkich liczb
mniejszych lub równych <math>n</math>. Liczba <math>n+1</math> jest niewątpliwie sumą
dwóch liczb silnie mniejszych od siebie <math>n+1=k+l</math>. Liczby <math>k</math> i
<math>l</math>, na podstawie założenia indukcyjnego, są parzyste, zatem ich
suma równa <math>n+1</math> jest parzysta. Krok indukcyjny został
dowiedziony.
Na zasadzie indukcji matematycznej wszystkie liczby są parzyste.
[:]
; Solution.
; Solution.
:[:]Dowód indukcyjny jest niepoprawny. Krok indukcyjny nie
:
działa dla wszystkich <math>n</math> większych lub równych od <math>0</math> -- które
 
jest podstawą indukcji. Jeśli <math>n=0</math>, to <math>n+1=1</math> i nie jesteśmy w
:# Oznaczmy zbiór formuł w których jedynym spójnikiem jest <math>\wedge</math> przez
stanie rozbić liczby <math>1</math> na sumę dwóch liczb istotnie mniejszych
<math>F_\wedge</math>. Udowodnimy, że każda formuła z <math>F_\wedge</math> przyjmuje zawsze wartość 1, jeśli jej zmienne są
od niej samej.
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>x</math>, gdzie
<math>x</math> jest zmienną. Wobec tego przy wartościowaniu zmiennych na 1 formuła <math>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>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>n</math> to z założenia indukcyjnego
otrzymujemy, że dla naszego wartościowania obie przyjmują
wartość 1. Wobec tego zgodnie z tabelą
[[##eq:tabeleInterpretacjiKRZANDOR|Uzupelnic eq:tabeleInterpretacjiKRZANDOR|]] 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>n</math> ma postulowaną własność.


W trójwymiarowej przestrzeni znajduje się <math>n</math> punktów. Ilość
Wiemy już że każda <math>F_\wedge</math> przyjmuje zawsze wartość 1, jeśli jej zmienne są
punktów w rzutowaniu na płaszczyznę <math>O_x, O_y</math> oznaczamy przez
wartościowane na 1. Wobec tego niemożliwe jest zdefiniowanie
<math>n_{xy}</math>. Podobnie ilość punktów w rzutowaniu na <math>O_x, O_z</math> przez
np. spójnika <math>F</math> gdyż definująca go formuła musiałby
<math>n_{xz}</math> i ilość punktów w rzutowaniu na <math>O_y, O_z</math> przez
przyjąć wartość 0 na takim wartościowaniu.
<math>n_{yz}</math>. Wykaż, że dla dowolnego rozkładu punktów w przestrzeni
zachodzi nierówność


n^2 n_{xy}n_{xz}n_{yz}.
:# Dowód analogiczny do poprzedniego.


[:]{hint}{1}
{Koniec æwiczenia {section}.{cwicz}}
; Hint .
 
:[:]Użyj nierówności pomiędzy średnią geometryczną, a
{cwicz}{1}
średnią arytmetyczną
{hint}{0}
{Æwiczenie {section}.{cwicz}}


{1}{2}(a+b) {ab}.
Czy funkcje binarne zdefiniowane za pomocą formuł zawierającyh jedynie przemienne spójniki muszą być przemienne?


{hint}{1}
{hint}{1}
; Hint .
; Hint .
:[:]Podziel punkty na dwie grupy płaszczyzną równoległą do
: Przyjrzyj się formułom zbudowanym z <math>\Leftrightarrow</math>
którejś z płaszczyzn <math>O_x, O_y</math>, <math>O_x, O_z</math> lub <math>O_y, O_z</math>.  
 
{Koniec æwiczenia {section}.{cwicz}}
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
(z wykładu prof. P.M.Idziaka)
Niech <math>F_n</math> oznacza ilość boolowskich funkcji <math>n</math> argumetnowych,
a <math>P_n</math> ilość boolowskich funkcji <math>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>
 
\lim_{n \rightarrow \infty} \frac{P_n}{F_n}
</math></center>
 
; Solution.
: 
 
{Koniec æwiczenia {section}.{cwicz}}
 
==Postacie normalne==
 
"Literałem" nazywamy formułę która jest zmienną zdaniową lub
negacją zmiennej zdaniowej.
 
Zauważmy, że formuła konstruowana w dowodzie twierdzenia
[[##thm:AndOrNegFP|Uzupelnic thm:AndOrNegFP|]] 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>
 
(p \wedge q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q).
</math></center>
 
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>
 
\phi_1\vee \dots \vee \phi_n
</math></center>
 
oraz każda z formuł <math>\phi_i</math> jest koniunkcją literałów, czyli jest postaci
 
<center><math>
 
l_1^i \wedge \dots \wedge l_k^i
</math></center>
 
dla pewnych literałów <math>l_1^i, \dots,l_k^i</math>
 
{{twierdzenie|[Uzupelnij]||
 
Dla każedej formuły istnieje równoważna formuła w DNF.
}}
 
{{dowod|[Uzupelnij]||
 
Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia
[[##thm:AndOrNegFP|Uzupelnic thm:AndOrNegFP|]].
}}
 
Formuła jest w koniunktywnej postaci normalnej (CNF) jeśli jest koniunkcją formuł które są
alternatywami literałów.
 
{{twierdzenie|[Uzupelnij]||
 
Dla każdej formuły istnieje równoważna formuła w CNF.
}}
 
{{dowod|[Uzupelnij]||
 
}}
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Jak sprawdzić, czy formuła w CNF jest tautologią?
 
; Solution.
: Niech rozważaną formułą będzie
 
<center><math>
 
\phi_1\wedge \dots \wedge \phi_n
</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).
 
{Koniec æwiczenia {section}.{cwicz}}
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w
CNF
 
# <math>p \Leftrightarrow q</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 \wedge q) \vee (r \wedge s)</math>
 
; Solution.
; Solution.
:[:]Dowiedziemy nierówność przy użyciu indukcji.
:
[*]
 
Jeśli <math>n=1</math> to <math>n_{xy}=n_{xz}=n_{yz}=1</math> i nierówność jest prawdziwa.
{Koniec æwiczenia {section}.{cwicz}}
 
===Spełnialność===
 
Spośród wszystkich formuł wyróżnimy też zbiór formuł spełnialnych.
 
Formuła jest spełnialna jeśli istenieje takie wartościowanie
które wartościuje tą formułę na 1.


Zakładamy, że nierówność jest prawdziwa dla wszystkich liczb
Formuły spełnialne są w ścisłym związku z tautologiami.
naturalnych&nbsp;(dla dowolnego układu punktów) mniejszych niż <math>n+1</math>.
Rozpoczynamy z dowolnym układem <math>n+1</math> punktów w przestrzeni.
Ponieważ <math>n+1>1</math> wiemy, że istnieje płaszczyzna równoległa do
którejś z płaszczyzn <math>O_x, O_y</math>, <math>O_x, O_z</math> lub <math>O_y, O_z</math> i
dzieląca <math>n+1</math> punktów na dwie niepuste części posiadające
odpowiednio <math>n'</math> i <math>n''</math> punktów. Ponieważ nasz układ jest bardzo
symetryczny możemy założyć że nasza płaszczyzna jest równoległa do
płaszczyzny <math>O_x, O_y</math>. Stosując założenie indukcyjne do każdej z
części otrzymujemy


{n'}^2  n'_{xy}n'_{xz}n'_{yz}
{{twierdzenie|[Uzupelnij]||


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


{n''}^2  n''_{xy}n''_{xz}n''_{yz}.
{{dowod|[Uzupelnij]||
 
Przypuśćmy, że formuła <math>\phi</math> jest tautologią. Wtedy dla każdego wartościowania <math>v</math> mamy
<math>v(\phi)=1</math>. Stąd otrzymujemy że dla każdego wartościowania <math>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.
 
Przypuśćmy, że formuła <math>\neg \phi</math> nie jest spełnialna, czyli nie istnieje wartościowanie <math>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ą.
}}


Co więcej, pomiędzy projekcjami zachodzą następujące zależności
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}


n'_{xz}+n''_{xz}<nowiki>=</nowiki>n_{xz} oraz  n'_{yz}+n''_{yz}<nowiki>=</nowiki>n_{yz}.
Sprawdź spełnialność następujących formuł


Dla płaszczyzny <math>O_x, O_y</math> nie posiadamy podziału na część punktów
# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee \neg p)</math>
należących do <math>n'</math> i <math>n''</math> i możemy jedynie wnioskować, że


n'_{xy} n_{xy} oraz n''_{xy} n_{xy}.
# <math>(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee p)</math>


Zaczynamy przekształcenia mające udowodnić pożądaną nierówność
; Solution.
: 


n^2& <nowiki>=</nowiki>{(n'+n'')}^2<nowiki>=</nowiki>{(n')}^2+2n'n'' + {(n'')}^2 {(n')}^2+2{{(n')}^2}{{(n'')}^2} + {(n'')}^2 <br>
{Koniec æwiczenia {section}.{cwicz}}
&  n'_{xy}n'_{xz}n'_{yz} +2{n'_{xy}n'_{xz}n'_{yz}}{n''_{xy}n''_{xz}n''_{yz}}+n''_{xy}n''_{xz}n''_{yz} <br>
&  n_{xy}n'_{xz}n'_{yz} +2{n_{xy}n'_{xz}n'_{yz}n_{xy}n''_{xz}n''_{yz}}+n_{xy}n''_{xz}n''_{yz}  <br>
&  n_{xy}(n'_{xz}n'_{yz}
+2{n'_{xz}n'_{yz}n''_{xz}n''_{yz}}+n''_{xz}n''_{yz}
)


używając założenia indukcyjnego i nierówności pomiędzy projekcjami
==Logika intuicjonistyczna==
na płaszczyznę <math>O_x, O_y</math>. Kontynuujemy używając nierówności
pomiędzy średnią algebraiczną i geometryczną


n^2 &  n_{xy}(n'_{xz}n'_{yz} +2{n'_{xz}n''_{xz}n'_{yz}n''_{yz}}+n''_{xz}n''_{yz})  <br>
Niektórzy logicy mają wątpliwości co do tego czy powinniśmy
&  n_{xy}(n'_{xz}n'_{yz} +2{1}{2}(n'_{xz}n''_{xz} +n'_{yz}n''_{yz})+n''_{xz}n''_{yz}) <nowiki>=</nowiki> <br>
przyjmować schemat dowodu nie wprost jako aksjomat. Poddanie w wątpliwość tego
& <nowiki>=</nowiki> n_{xy}(n'_{xz}n'_{yz} +n'_{xz}n''_{xz}
aksjomatu doprowadziło do powstnia tzw. logiki intuicjonistycznej. Ważnym
+n'_{yz}n''_{yz}+n''_{xz}n''_{yz}) <nowiki>=</nowiki> n_{xy}(n'_{xz} +
powodem zajmowania się logiką intuicjonistyczną są jej zadziwiające
n''_{xz})(n'_{yz}+n''_{yz})
związki z teorią obliczeń (izomorfizm Curry-Howard).


W ostatnim kroku wystarczy wykorzystać zależności pomiędzy
Implikacyjny fragment logiki intuicjonistycznej, który będziemy
projekcjami na pozostałe dwie współrzędne i
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.
Aksjomaty <math>I_\Rightarrow</math>


n^2 n_{xy}(n'_{xz} + n''_{xz})(n'_{yz}+n''_{yz})<nowiki>=</nowiki>
# <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math> (formuła ta jest nazywana
n_{xy}n_{xz}n_{yz}.
aksjomatem K)


Krok indukcyjny został dowiedziony.
# <math>(\phi \Rightarrow (\nu \Rightarrow \psi) \Rightarrow \left((\phi \Rightarrow \nu) \Rightarrow
Na podstawie zasady indukcji matematycznej twierdzenie jest
(\phi \Rightarrow \nu) \right)</math> (formuła ta jest nazywana
prawdziwe.
aksjomatem S)


{obra}{1}{{Obrazek {section}.{obra}}}Obrazek do powyższego ćwiczenia według załączonego skanu
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
[[##defn:AksjomatyIntImp|Uzupelnic defn:AksjomatyIntImp|]]. 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.


Zasada indukcji matematycznej jest bardzo potężnym narzędziem.
{{twierdzenie|[Uzupelnij]||
Intuicyjnie wydaje się jasne, że dowody przeprowadzone przy jej
pomocy są poprawne. Niemniej jednak, żeby uzasadnić poprawność
samej zasady należy sięgnąć do teorii mnogości i definicji zbioru
liczb naturalnych. Wiemy już, że "naiwna teoria mnogości" nie daje
nam poprawnych zbiorów na których można oprzeć ścisłe rozumowanie.
W dalszej części wykładu wyprowadzimy zasadę indukcji
matematycznej w oparciu o aksjomaty i aksjomatycznie zdefiniowany
zbiór liczb naturalnych. Takie podejście gwarantuje nam poprawność
rozumowania -- podejście naiwne zapewnia intuicje niezbędne do
budowania poprawnych teorii.
=="Naiwne" dowody niewprost==


Częstą metodą dowodzenia twierdzeń matematycznych jest dowodzenie
Każde twierdzenie logiki intuicjonistycznej
niewprost. Dowód niewprost polega na założeniu zaprzeczenia
jest twierdzeniem klasycznego rachunku zdań.
twierdzenia, które chcemy udowodnić i doprowadzeniu do
}}
sprzeczności. Wykazujemy, że jeśli twierdzenie nasze jest
nieprawdziwe, jesteśmy w stanie udowodnić jakąś tezę, która jest w
sposób oczywisty fałszywa.


Jednym z najbardziej znanych dowodów niewprost jest dowód
{{dowod|[Uzupelnij]||
istnienia nieskończenie wielu liczb pierwszych. Dowód ten został
zaproponowany przez '''Euclid of Alexandria''' a my prezentujemy go w wersji podanej
przez Ernst'a Kummera.


{{twierdzenie|[Uzupelnij]||
Każdy dowód twierdzenia logiki inuicjonistycznej jest równocześnie dowodem
Istnieje nieskończenie wiele liczb pierwszych.
twierdzenia klasycznego rachunku zdań.
}}
}}


{{dowod|[Uzupelnij]||
Implikacja w drugą stronę nie zachodzi. Istnieją formuły zbudowane
Załóżmy że istnieje jedynie skończenie wiele liczb pierwszych
jedynie przy pomocy <math>\Rightarrow</math>, które nie należą do <math>I_\Rightarrow</math> pomimo
<math>p_0,\dotsc,p_n</math>. Zdefiniujmy liczbę
że są twierdzeniami klasycznego rachunku zdań. Przykładem takiej formuły jest prawo
Pierce'a:
 
<center><math>
 
((p \Rightarrow q) \Rightarrow p ) \Rightarrow p
</math></center>
 
W zadaniu [[##zad:aksjomatyTatuologie|Uzupelnic zad:aksjomatyTatuologie|]] pokazaliśmy, że formuła ta jest w istocie tautologią
więc w myśl twierdzenia Posta [[##thm:zupełnośćPost|Uzupelnic thm:zupełnośćPost|]] również
twierdeniem klasycznego rachunku zdań.
 
W poniższych zadaniach wykażemy poniższe twierdzenie


k <nowiki>=</nowiki> p_0 p_1 p_n
{{twierdzenie|[Uzupelnij]||


i rozważmy <math>k+1</math>. Liczba <math>k+1</math> posiada dzielnik pierwszy, a
Prawo Pierce'a nie jest twierdzeniem intuicjonizmu.
ponieważ jedynymi pierwszymi liczbami są liczby <math>p_0,\dotsc,p_n</math>
wnioskujemy, że <math>p_i</math> dzieli <math>k+1</math> dla pewnego <math>i</math>. Liczba <math>p_i</math>
dzieli również <math>k</math>, a więc <math>p_i</math> dzieli <math>(k+1)-k=1</math> co jest
sprzecznością.
}}
}}


Wykaż, że nie istnieje największa liczba naturalna.
Zauważmy, że oznacza to również że każdy dowód prawa Pierce'a w
[:]
logice klasycznej korzysta z aksjomatu 3 [[##defn:AksjomatyKRZ|Uzupelnic defn:AksjomatyKRZ|]], a więc wymaga
używania spójnika <math>\neg</math>.
 
Aby udowodnić twierdzenie [[##thm:PrawoPiercea|Uzupelnic thm:PrawoPiercea|]] zdefiniujemy
jeszcze jedną logikę którą nazwiemy <math>I_3</math>. Podobnie do
[[##defn:matrycaBool|Uzupelnic defn:matrycaBool|]] zdefiniujemy matrycę tym razem 3-elementową.
 
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
 
<center><math>
 
\begintabular {|c|c c c|}\hline
& 0 & 1 & 2\\\hline
0 & 2 & 2 & 2\\
1 & 0 & 2 & 2\\
2 & 0 & 1 & 2\\\hline
\endtabular  \hspace{1cm}
</math></center>
 
W przypadku rozważanej matrycy <math>\mathbb{M}_3</math> wartościowanie będzie
funkcją przypisującą zmiennym zdaniowym elementy zbioru <math>M_3</math>.
Podobnie jak dla logiki klasycznej wartościowanie zmiennych
rozszzerzamy na wartościowanie formuł zgodnie z tabelą
[[##eq:tabeleInterpretacjiInt3|Uzupelnic eq:tabeleInterpretacjiInt3|]].
 
ład
Dla wartościowania <math>v</math> takiego, że <math>v(p)=2, v(q)=1, v(r)=0</math>
formuła
 
<center><math>
 
(p \Rightarrow q) \Rightarrow r
</math></center>
 
przyjmuje wartość 0.
ład
 
Tautologią logiki <math>I_3</math> będziemy nazywać każdą formułę
implikacyjną,
która przy każdym wartościowaniu zmiennych w <math>M_3</math> przyjmuje
wartość 2.
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Udowodnij, że aksjomaty S i K są tautologiami <math>I_3</math>.
 
; Solution.
: 
 
{Koniec æwiczenia {section}.{cwicz}}
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
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>.
 
; Solution.
: 
 
{Koniec æwiczenia {section}.{cwicz}}
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Udowodnij, że każde twierdzenie logiki <math>I_\Rightarrow</math> jest
tautologią <math>I_3</math>.
 
{hint}{1}
; Hint .
: Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu.
Pomocne będą poprzednie zadania.
 
; Solution.
; Solution.
:[:]Załóżmy, niewprost, że istnieje największa liczba
:
naturalna i oznaczmy ją przez <math>n</math>. Niewątpliwie <math>n+1</math> jest liczbą
 
naturalną większą od <math>n</math>, co jest sprzecznością z naszym
{Koniec æwiczenia {section}.{cwicz}}
założeniem.
 
{cwicz}{1}
{hint}{0}
{Æwiczenie {section}.{cwicz}}
 
Sprawdź, czy prawo Pierce'a jest tautologią <math>I_3</math>.
{hint}{1}
; Hint .
: Nie jest.


Wykaż, że <math>\sqrt{2}</math> jest liczbą niewymierną. [:]
; Solution.
; Solution.
:[:]Załóżmy,
: Dla wartościowania <math>v</math> takiego, że <math>v(p)=1</math> i <math>v(q)=0</math> kolejne
niewprost, że <math>\sqrt{2}</math> jest liczbą wymierną, czyli, że istnieją
fomruły przyjmują następujace wartości
dwie naturalne, względnie pierwsze liczby <math>k</math> i <math>l</math> takie, że
 
<math>\sqrt{2}=k/l</math>. Przekształcając ostatnie wyrażenie otrzymujemy
:# <math>v(p\Rightarrow q) =0</math>
<math>k^2=2l^2</math>. Skoro <math>2</math> dzieli lewą stronę równości dzieli też i
 
prawą, a ponieważ dwa jest liczbą pierwszą wnioskujemy, że <math>2</math>
:# <math>v((p\Rightarrow q)\Rightarrow p) =2</math>
dzieli <math>k</math>. Jeśli <math>2</math> dzieli <math>k</math> to <math>4</math> dzieli <math>k^2</math> i na
 
podstawie równości <math>4</math> dzieli <math>2l^2</math>. Wnioskujemy stąd, że <math>2</math>
:# <math>v(((p\Rightarrow q)\Rightarrow p)\Rightarrow p) =1</math>
dzieli <math>l^2</math> i, na podstawie pierwszości liczby <math>2</math>, że <math>2</math> dzieli
 
<math>l</math>. Udowodniliśmy, że <math>2</math> dzieli zarówno <math>k</math> jak i <math>l</math>, co jest
Wobec tego prawo Pierce'a nie jest tautologią <math>I_3</math> gdyż
sprzecznością z założeniem, że liczby te są względnie pierwsze.
wyróżnioną wartością prawdy <math>I_3</math> w jest 2.
 
{Koniec æwiczenia {section}.{cwicz}}
 
Podsumujmy wyniki powyższych zadań. Wskazaliśmy logikę <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ż
twierdzeniem <math>I_\Rightarrow</math>.
 
UWAGA! W dalszej części będziemy się posługiwać wyłącznie
"'logiką klasyczną"'.
{amsplain}
 


Ścisłe uzasadnienie poprawności dowodów niewprost leży na gruncie
logiki, której poświęcony jest następny wykład.




Wersja z 20:51, 2 sie 2006

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ą,"
  1. "n jest liczbą nieparzystą,"
  1. "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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textbf{jeśli} [..] \textbf{to}, \textbf{lub}} oraz powyższych oznaczeń otrzymamy formułę

p⇒(q∨r).

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⇒(q∨r),
  1. p,
  1. ¬q (przez ¬ oznaczamy negację)

to zgodnie z klasycznym rachunkiem (może lepiej z intuicją?) 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⇒(q∨r))∧p∧(¬q))⇒q.

W powyższej formule spójnik 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: {formuła logiki zdaniowej}

  1. zmienna zdaniowa jest formułą (zmienne zdaniowy oznaczamy

zwykle literami alfabetu rzymskiego np. p,q,r)

  1. jeśli ϕ oraz ψ są formułami to (ϕ⇒ψ) jest formułą (spójnik ⇒ nazywamy implikacją)
  1. jeśli ϕ jest formułą to ¬ϕ jest formułą

(spójnik ¬ nazywamy negacją)

  1. 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 ¬.

Zgodnie z powyższą definicją nie jest formułą napis p⇒q, gdyż brakuje w nim nawiasów. Pomimo, iż poprawnie powinniśmy napisać (p⇒q) możemy przyjąć że nie będzie konieczne pisanie nawiasów, jeśli nawiasy można jednoznacznie uzupełnić.

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

  • p⇒⇒q
  • ¬¬¬
  • "ten napis na pewno nie jest formułą"
  • (p⇒¬q))

Poniższe napisy są formułami

  • (p⇒(r⇒q))
  • ¬¬¬q
  • (p⇒¬q)

ład

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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 (p⇒q) 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?

Solution.
Oznaczmy przez fn liczbę formuł o rozmiarze n (czyli liczbę

formuł w których jest n spójników). Interesuje nas f3. Każda formuła o rozmiarze 3 powstaje albo z dwóch formuł o rozmiarach 1 poprzez połączenie ich spójnikiem ⇒ albo z jednej formuły o rozmiarze 2 poprzez dodanie do niej spójnika ¬. Co więcej każda taka formuła powstaje tylko w jeden sposób. Wynika stąd następująca zależność:

f3=f2+(f1)2

Wiemy, że są tylko dwie formuły o rozmiarze 1, są to ¬p oraz p⇒p. Stąd mamy f1=2. 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ą ⇒, albo jest zbudowana z formuły o rozmiarze 1 za pomocą negacji. Zauważmy też, że istnieje formuła o rozmiarze 0, jest to p. Mamy więc następujący wzór dla f2

f2=1⋅f1+f1⋅1+f1=3⋅f1

Z dwóch ostatnich wzorów otrzymujemy

f3=3⋅f1+(f1)2=6+4=10

Skoro jest ich niewiele to możemy wszystkie wypisać

  1. ¬¬¬p
  1. ¬¬(p⇒p)
  1. ¬(p⇒¬p)
  1. ¬(p⇒(p⇒p))
  1. ¬(¬p⇒p)
  1. ¬((p⇒p)⇒p)
  1. (¬p)⇒(¬p)
  1. (¬p)⇒(p⇒p)
  1. (p⇒p)⇒(¬p)
  1. (p⇒p)⇒(p⇒p)

{Koniec æwiczenia {section}.{cwicz}}

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

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: Aksjomaty klasycznego rachunku zdań.

  1. (ϕ⇒(ψ⇒ϕ)) (formuła ta jest nazywana

aksjomatem K)

  1. (ϕ⇒(ν⇒ψ)⇒((ϕ⇒ν)⇒(ϕ⇒ν)) (formuła ta jest nazywana

aksjomatem S)

  1. (¬ϕ⇒ψ)⇒(¬ϕ⇒¬ψ)⇒ϕ

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

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

  1. ϕn jest formułą ψ
  1. dla każdego i≤n 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.

Formułę nazywamy "twierdzeniem klasycznego rachunku zdań" jeśli istnieje jej dowód z aksjomatów klasycznego rachunku zdań Uzupelnic defn:AksjomatyKRZ|.

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 Uzupelnic defn:AksjomatyKRZ|. 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
  1. ϕ⇒[(q⇒ϕ)⇒ϕ] aksjomat zgodny ze

schematem K

  1. (ϕ⇒(q⇒ϕ))⇒(ϕ⇒ϕ) z modus ponens z

formuł 1 i 2.

  1. ϕ⇒[q⇒ϕ] aksjomat zgodny ze schematem

K

  1. (ϕ⇒ϕ) 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 Uzupelnic defn:AksjomatyKRZ| 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 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.

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

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 1 & 1 \\ 1 & 0 & 1 \\\hline \endtabular \hspace{1cm} \begintabular {|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 1 \\ 1 & 0 \\\hline \endtabular }

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 Uzupelnic eq:tabeleInterpretacjiKRZ|.

ład

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

  • formuła q⇒p jest wartościowana na

0 (będziemy to zapisywać jako v(q⇒p)=0),

  • formuła r⇒(q⇒p) jest wartościowana na 1 (czyli v(r⇒(q⇒p))=1)
  • formuła ¬p⇒r jest wartościowana na 0 (czyli v(¬p⇒r)=0)

ład

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

Przy wartościowaniu v z przykładu Uzupelnic eg:wartosciowania| jakie wartości przyjmują następujące formuły

  1. p⇒(q⇒r)
  1. p⇒(p⇒q)
  1. ¬¬q⇒p
  1. (¬q⇒q)⇒(q⇒¬q)
Solution.
  1. v(p⇒(q⇒r))=1
  1. v(p⇒(p⇒q))=1
  1. v(¬¬q⇒p)=0
  1. v((¬q⇒q)⇒(q⇒¬q))=0

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

były wartościowane na 0

    1. p⇒(q⇒r)
    1. (¬p⇒q)
    1. (p⇒q)⇒q
  1. Podaj przykład wartościowania zmiennych tak aby poniższe formuły

były wartościowane na 1

    1. ¬(p⇒q)
    1. ¬(¬p⇒¬q)
    1. (¬q⇒q)⇒(q⇒¬q)
Solution.
Wartościowania będziemy oznaczać przez v
    1. v(p)=1,v(q)=1,v(r)=0
    1. v(p)=0,v(q)=0
    1. v(p)=0,v(q)=0
    1. v(p)=1,v(q)=0
    1. v(p)=0,v(q)=1)
    1. v(q)=1

{Koniec æwiczenia {section}.{cwicz}}

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. p⇒p). Takie formuły będziemy nazywać "'tautologiami"'.

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. (ϕ⇒(ψ⇒ϕ))
  1. (ϕ⇒(ν⇒ψ)⇒((ϕ⇒ν)⇒(ϕ⇒ν))
  1. (¬ϕ⇒ψ)⇒(¬ϕ⇒¬ψ)⇒ϕ
  1. ((ϕ⇒q)⇒p)⇒p

{hint}{1}

Hint .
Spróbuj poszukać wartościowań dla których formuła przyjmuje

wartość 0

{hint}{1}

Hint .
Można też sprawdzić wszystkie możliwości wartościowań.
Solution.

{Koniec æwiczenia {section}.{cwicz}}

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

Twierdzenie [Uzupelnij]

{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ń).

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

{hint}{1}

Hint .
Pokazaliśmy już w zadaniu

Uzupelnic zad:aksjomatyTatuologie|, że aksjomaty są tautologiami. Zacznij od pokazania, że zastosowanie reguły MP do tautologii daje tautologię. {hint}{1}

Hint .
Udowodnij, twierdznie przez indukcję ze względu na długość

dowodu.

Solution.

{Koniec æwiczenia {section}.{cwicz}}

Inne spójniki

Do tej pory jedynymi rozważanymi spójnikami była implikacja i negacja. W analogiczny sposób do Uzupelnic eq:tabeleInterpretacjiKRZ| 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:

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 0 \\ 1 & 0 & 1 \\\hline \endtabular \hspace{1cm} \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular }

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.

Formuły ϕ oraz ψ są "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 ψ.

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. ϕ∨ψ≡¬ϕ⇒ψ
  1. ϕ∧ψ≡¬(ϕ⇒¬ψ)
Solution.
  1. Lewa strona jest fałszywa jedynie gdy ϕ oraz

ψ są wartościowane na 0. Prawa strona jest fałszywa wtedy i tylko wtedy kiedy ¬ϕ jest wartościowane na 1 oraz ψ 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 ϕ oraz ψ są wartościowane na 0, a więc jest równoważna lewej.

  1. Lewa strona jest prawdziwa jedynie gdy ϕ oraz

ψ są wartościowane na 1. Prawa strona jest prawdziwa wtedy i tylko wtedy kiedy ¬(ϕ⇒¬ψ) jest wartościowane na 1, więc wtedy gdy (ϕ⇒¬ψ) jest wartościowane na 0. To z kolei zdarzyć się może jedynie gdy ϕ jest wartościowane na 1 i ¬ψ na 0, a więc wtedy gdy zarówno ϕ jak i ψ są wartościowane na 1. Wobec tego obie formuły są równoważne.

Równie dobrym rozwiązaniem jest sprawdzenie wszystkich możliwości wartościowań i porównanie wyników.

{Koniec æwiczenia {section}.{cwicz}}

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.

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. ¬¬p≡p
  1. p⇒q≡¬p∨q
  1. p⇒(q⇒r)≡(p∧q)⇒r
  1. ¬(p∧q)≡¬p∨¬q
  1. ¬(p∨q)≡¬p∧¬q
  1. p∧(q∨r)≡(p∧q)∨(p∧r)
  1. p∨(q∧r)≡(p∨q)∧(p∨r)
  1. (p⇒q)⇒(¬p⇒¬q)
Solution.
Przedstwiamy przykładowe dowody kilku pierwszych równoważności.
  1. Jeśli p jest wartościowane na 1, to zgodnie z tabelą dla negacji Uzupelnic eq:tabeleInterpretacjiKRZ|

¬p jest wartościowane na 0 i ¬¬p jest wartościowane na 1. Jeśli p jest wartościowane na 0 to ¬p jest wartościowane na 1 i ¬¬p jest wartościowane na 0. Formuły przyjmują te same wartości dla każdego wartościowania więc są równoważne.

  1. Jedyną możliwością aby lewa strona była fałszywa jest

aby p było wartościowane na 1, a q na 0. Prawa stona jest fałszywa jedynie gdy ¬p oraz q są wartościowane na 0. Czyli prawa strona jest fałszywa jedynie gdy p jest wartościowane na 1 i q na 0. Formuły są więc równoważne.

  1. Analogicznie do poprzedniego punktu łatwo się

przekonać, że jedynym wartościowaniem które falsyfikuje lewą stronę jest takie które wartościuje p i q na 1 oraz r na 0. Tą samą własność ma formuła po prawej stronie, więc formuły są równoważne.

  1. Przykład rozwiązania przez rozważenie wszystkich

możliwości

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } p qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } p qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 & 0 & 0\\\hline \endtabular \hspace{1cm} }

W pierwszych dwóch kolumnach są zapisane wartościowania zmiennych p i q 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.

  1. W równoważności z poprzedniego punktu, podstawiąjąc za p

formułę ¬p oraz za q formułę ¬q otrzymamy równoważność

¬(¬p∧¬q)≡¬¬p∨¬¬q.

Stosując dwukrotnie równoważność z pierwszego punktu do prawej strony otrzymujemy

¬(¬p∧¬q)≡p∨q.

Negując tą równoważność obustronnie otrzymamy

¬¬(¬p∧¬q)≡¬(p∨q).

Stosując równoważność z pierwszego punktu do lewej strony otrzymamy szukaną równoważność.

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. ((p∨r)∧(q∨¬r))⇒(p∨q)
  1. (p∨q)⇒((p∨r)∧(q∨¬r))
  1. ((p∧r)∨(q∧¬r))⇒(p∧q)
  1. (p∧q)⇒((p∧r)∨(q∧¬r))
Solution.
  1. Spróbujmy znaleźć wartościowanie które falsyfikuje tą

formułę. Skoro implikacja ma być fałszywa to formuła (p∨q) (czyli następnik) musi być fałszywa. Tak jest tylko wtedy kiedy zarówno p jak i q są fałszywe. Zobaczmy co się wtedy dzieje z poprzednikim implikacji, czyli formułą

(p∨r)∧(q∨¬r).

Jeśli teraz ustalimy r na fałsz to (p∨q) będzie fałszywe a jeśli ustalimy r na prawdę to (q∨¬r) 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ą.

  1. Formuła nie jest tautologią. Wystarczy wartościować p i

r na prawdę i q na fałsz.

  1. Formuła nie jest tautologią. Wystarczy wartościować p i

r na prawdę i q na fałsz.

  1. Przykład rozwiązania przez rozważenie wszystkich

możliwości

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } rParser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} ( q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p r)( q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q) ( (p r)( q r))Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0& 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1& 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0& 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0& 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1& 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1& 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 1& 1 \\\hline \endtabular \hspace{1cm} }

W kolumnie odpowiadającej badanej formule są same 1, więc jest ona tautologią.

{Koniec æwiczenia {section}.{cwicz}}

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.

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

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c||c|}\hline Numer & } p=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle && \\ funkcji& } q=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } q=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle && \\ \hline 0 & 0 & 0 & 0 & 0 && } FParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 1 & 0 & 0 & 0 & 1 && \\ 2 & 0 & 0 & 1 & 0 && } (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 3 & 0 & 0 & 1 & 1 && } pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 4 & 0 & 1 & 0 & 0 && } (q p)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 5 & 0 & 1 & 0 & 1 && } qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 6 & 0 & 1 & 1 & 0 && } XORParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 7 & 0 & 1 & 1 & 1 && \\ 8 & 1 & 0 & 0 & 0 && } NORParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 9 & 1 & 0 & 0 & 1 && \\ 10& 1 & 0 & 1 & 0 && } qParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 11& 1 & 0 & 1 & 1 && } q pParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 12& 1 & 1 & 0 & 0 && } p Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 13& 1 & 1 & 0 & 1 && } p q Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 14& 1 & 1 & 1 & 0 && } NANDParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ 15& 1 & 1 & 1 & 1 && } T Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline \endtabular \hspace{1cm} }

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

p∘q≡q∘p

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. xNANDy≡¬(x∧y)
  1. xNORy≡¬(x∨y)
  1. xXORy≡¬(x⇔y)
Solution.

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

{hint}{1}

Hint .
Wygodnie jest reprezentować spójniki binarne w tabeli

kwadratowej. Na przykład alternatywę zdefiniowaliśmy jako

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular . }

Jaką własność musi posiadać tabela aby spójnik definiowany przez nią był przemienny?

Solution.
Dla przemienności spójnika ∘ istotne jest aby 1∘0=0∘1. Dla pozostałych

przypadków wartościowań równoważnośc Uzupelnic eq:przemienność| jest zawsze spełniona. Każdy spójnik binarny możemy zdefiniować za pomocą tabelki kwadratowej, np. alternatywę zdefiniowaliśmy jako

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c|}\hline & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 1 \\\hline \endtabular . }

Warunek przemienności oznacza, że wartość w polu o współrzędnych (0,1) jest równa wartości w polu o współrzędnych (1,0). Takich tabel jest 8, więc mamy 8 spójników przemiennych. Nietrudno je teraz odnaleźć w tabeli Uzupelnic defn:spójniki|. Są to

  1. F
  1. ∧
  1. XOR
  1. ∨
  1. NOR
  1. ⇔
  1. NAND
  1. T

{Koniec æwiczenia {section}.{cwicz}}

Spójnik binarny ∘ będziemy nazywać "łącznym" jeśli zachodzi następująca równoważność

p∘(q∘r)≡(p∘q)∘r.

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.

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. ∨
  1. ∧
  1. ⇔
  1. XOR
Solution.
  1. Formuła (p∨q)∨r jest fałszywa jedynie

wtedy gdy p,q i r są wartościowane na fałsz. Tak samo jest dla formuły p∨(q∨r) więc są one równoważne.

  1. Formuła (p∧q)∧r jest prawdziwa jedynie

wtedy gdy p,q i r są wartościowane na prawdę. Tak samo jest dla formuły p∧(q∧r) więc są one równoważne.

  1. Zbadamy równoważność formuł (p⇔q)⇔r

i p⇔(q⇔r) za pomocą tabeli

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|c|c|c|}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle &} qParser nie mógł rozpoznać (błąd składni): {\displaystyle &} r Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p q)Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } (p q) rParser nie mógł rozpoznać (błąd składni): {\displaystyle & } (q r )Parser nie mógł rozpoznać (błąd składni): {\displaystyle &} p (q r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline \endtabular \hspace{1cm} }

Kolumna 4 i 6 są identyczne więc odpowiadające im formuły są równoważne. Spójnik ⇔ jest więc łączny.

  1. ...

{Koniec æwiczenia {section}.{cwicz}}

Możemy również rozważać spójniki 3 i więcej argumentowe. Spójnik k-argumetowy powinien odpowiadać funkcji 𝔹k→𝔹. ład W poniższej tabeli przedstawiamy przykład spójnika trójargumentowego

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c c c|c||}\hline } pParser nie mógł rozpoznać (błąd składni): {\displaystyle & } qParser nie mógł rozpoznać (błąd składni): {\displaystyle & } rParser nie mógł rozpoznać (błąd składni): {\displaystyle &} (p, q,r)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 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 \\\hline \endtabular \hspace{1cm} }

ład

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

Udowodnij, że różnych spójników k-argumentowych jest dokładnie 22k.

Solution.

{Koniec æwiczenia {section}.{cwicz}}

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⇒(q⇒r) wyznacza funkcję fp⇒(q⇒r) opisaną poniższą tabelą

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c|c|c|}\hline p & q & r & } f_{p (q r)}Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\\hline 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 \\\hline \endtabular }

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

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 [Uzupelnij]

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

Dowód [Uzupelnij]

Twierdzenie [Uzupelnij]

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

Dowód [Uzupelnij]

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

Twierdzenie [Uzupelnij]

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

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

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

Zdefiniuj alternatywę przy pomocy samej implikacji.

Solution.
Łatwo sprawdzić że formuła p⇒(p⇒q) jest równoważna

formule p∨q.

{Koniec æwiczenia {section}.{cwicz}}

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

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. {∧}
  1. {∨}
  1. {⇔}
  1. {XOR}
Solution.
  1. Oznaczmy zbiór formuł w których jedynym spójnikiem jest ∧ przez

F∧. Udowodnimy, że każda formuła z F∧ przyjmuje zawsze wartość 1, jeśli jej zmienne są wartościowane na 1. Rozmiarem formuły będziemy nazywać liczbę wystąpień spójnika ∧ w formule. Dowód będzie indukcyjny ze względu na rozmiar formuły.

Baza indukcji: Każda formuła z F∧ o rozmiarze 0 jest postaci x, gdzie x jest zmienną. Wobec tego przy wartościowaniu zmiennych na 1 formuła x też jest wartościowana na 1. A więc każda formuła o rozmiarze 0 ma postulowaną własność.

Krok indukcyjny: Ustalmy dowolne n>0 i przyjmijmy, że wszystkie formuły o mniejszym rozmiarze mają postulowaną własność. Niech ν będzie dowolną formułą z F∧ o rozmiarze n. Skoro n>1 to ν musi być postaci ϕ∧ψ. Rozważmy wartościowanie które wszyskim zmiennym przypisuje wartość 1. Ponieważ rozmiary ϕ oraz ψ są silnie mniejsze od n to z założenia indukcyjnego otrzymujemy, że dla naszego wartościowania obie przyjmują wartość 1. Wobec tego zgodnie z tabelą Uzupelnic eq:tabeleInterpretacjiKRZANDOR| cała formuła ϕ∧ψ też przyjmuje wartość 1. Dowiedliśmy więc, że każda formuła o rozmiarze n ma postulowaną własność.

Wiemy już że każda F∧ przyjmuje zawsze wartość 1, jeśli jej zmienne są wartościowane na 1. Wobec tego niemożliwe jest zdefiniowanie np. spójnika F gdyż definująca go formuła musiałby przyjąć wartość 0 na takim wartościowaniu.

  1. Dowód analogiczny do poprzedniego.

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

{hint}{1}

Hint .
Przyjrzyj się formułom zbudowanym z ⇔

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

(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ść

limn→∞PnFn
Solution.

{Koniec æwiczenia {section}.{cwicz}}

Postacie normalne

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

Zauważmy, że formuła konstruowana w dowodzie twierdzenia Uzupelnic thm:AndOrNegFP| jest w pewnej standartowej postaci - formuła jest alternatywą formuł które są koniunkcjami literałów. Przypomnijmy, że dla p⇒q zbudujemy formułę

(p∧q)∨(¬p∧q)∨(¬p∧¬q).

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

l1i∧…∧lki

dla pewnych literałów l1i,…,lki

Twierdzenie [Uzupelnij]

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

Dowód [Uzupelnij]

Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia Uzupelnic thm:AndOrNegFP|.

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

Twierdzenie [Uzupelnij]

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

Dowód [Uzupelnij]

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

Solution.
Niech rozważaną formułą będzie
ϕ1∧…∧ϕn

Aby była tautologią konieczne jest aby każda z formuł ϕi była tautologią. Ponieważ każda z formuł ϕi jest alternatywą literałów to jest tautologią jedynie wtedy jeśli istnieje taki literał który występuje w ϕi zarówno pozytywnie (czyli jako zmienna) jak i negatywnie (czyli jako zanegowana zmienna).

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. p⇔q
  1. p⇒(q⇒p)
  1. (p⇒q)⇒p
  1. (p∨a∨b)∧(¬q∨¬a)∧(r∨¬b∨¬c)∧(c∨p))
  1. (p∧q)∨(r∧s)
Solution.

{Koniec æwiczenia {section}.{cwicz}}

Spełnialność

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

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 [Uzupelnij]

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

Dowód [Uzupelnij]

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 mamyv(¬ϕ)=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ą.

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

  1. (¬p∨q)∧(¬q∨¬r)∧(¬q∨¬p)
  1. (¬p∨q)∧(¬q∨¬r)∧(¬q∨p)
Solution.

{Koniec æwiczenia {section}.{cwicz}}

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 związki z teorią obliczeń (izomorfizm Curry-Howard).

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. Aksjomaty I⇒

  1. (ϕ⇒(ψ⇒ϕ)) (formuła ta jest nazywana

aksjomatem K)

  1. (ϕ⇒(ν⇒ψ)⇒((ϕ⇒ν)⇒(ϕ⇒ν)) (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 Uzupelnic defn:AksjomatyIntImp|. 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 [Uzupelnij]

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

Dowód [Uzupelnij]

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:

((p⇒q)⇒p)⇒p

W zadaniu Uzupelnic zad:aksjomatyTatuologie| pokazaliśmy, że formuła ta jest w istocie tautologią więc w myśl twierdzenia Posta Uzupelnic thm:zupełnośćPost| również twierdeniem klasycznego rachunku zdań.

W poniższych zadaniach wykażemy poniższe twierdzenie

Twierdzenie [Uzupelnij]

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 Uzupelnic defn:AksjomatyKRZ|, a więc wymaga używania spójnika ¬.

Aby udowodnić twierdzenie Uzupelnic thm:PrawoPiercea| zdefiniujemy jeszcze jedną logikę którą nazwiemy I3. Podobnie do Uzupelnic defn:matrycaBool| zdefiniujemy matrycę tym razem 3-elementową.

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

Parser nie mógł rozpoznać (nieznana funkcja „\begintabular”): {\displaystyle \begintabular {|c|c c c|}\hline & 0 & 1 & 2\\\hline 0 & 2 & 2 & 2\\ 1 & 0 & 2 & 2\\ 2 & 0 & 1 & 2\\\hline \endtabular \hspace{1cm} }

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ą Uzupelnic eq:tabeleInterpretacjiInt3|.

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

(p⇒q)⇒r

przyjmuje wartość 0. ład

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

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

Solution.

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

Solution.

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

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

{hint}{1}

Hint .
Przeprowadź rozumowanie indukcyjne ze względu na długość dowodu.

Pomocne będą poprzednie zadania.

Solution.

{Koniec æwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Æwiczenie {section}.{cwicz}}

Sprawdź, czy prawo Pierce'a jest tautologią I3. {hint}{1}

Hint .
Nie jest.
Solution.
Dla wartościowania v takiego, że v(p)=1 i v(q)=0 kolejne

fomruły przyjmują następujace wartości

  1. v(p⇒q)=0
  1. v((p⇒q)⇒p)=2
  1. v(((p⇒q)⇒p)⇒p)=1

Wobec tego prawo Pierce'a nie jest tautologią I3 gdyż wyróżnioną wartością prawdy I3 w jest 2.

{Koniec æwiczenia {section}.{cwicz}}

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ą"'. {amsplain}






Ćwiczenie

-


Złożoność czasowa Złożoność pamięciowa
Maszyna dodająca f(0)=1
f(1)=3
f(n)=n+3;n≥2		 f(0)=2
f(1)=3
f(n)=n+1;n≥2
Maszyna rozpoznająca ww← f(n)=6+8+…+(n+3)+2;n=2k+1
f(n)=5+7+…+(n+3)+1;n=2k		 f(n)=n+1
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR&oldid=8703”