Dr Andrzej Kmiecik
Zakład Logiki i Epistemologii
Instytut Filozofii i Socjologii UKW
w Bydgoszczy
ul. Ogińskiego 16
Wykład 7
Klasyczny rachunek zdań (2)
Istnieją dwie metody budowania klasycznego rachunku zdań: metoda aksjomatyczna i metoda
założeniowa. O metodzie aksjomatycznej będzie mowa póz
niej.
Systemy założeniowe są bliższe potocznym intuicjom pod tym względem, że dowody
przeprowadzone na ich gruncie nie różnią się prawie od dowodów matematycznych i
rozumowań w innych naukach.
Z tego powodu systemy założeniowe noszą nazwę dedukcji naturalnej
Pierwsze systemy założeniowe ukazały się w latach 1934 i 1935. Twórcami ich byli
Jaśkowski i Gentzen. System tu prezentowany różni się od nich kilkoma szczegółami. Został
opracowany przez Jerzego Słupeckiego wespół z Ludwikiem Borkowskim.
Ujęcie założeniowe
Zob. Jerzy Słupecki, Ludwik Borkowski: Elementy logiki matematycznej i teorii mnogości,
PWN, Warszawa 1984, s. 7-20.
Implikacja. Wynikanie logiczne. Wnioskowanie. Reguła dowodzenia.
Najpierw rozróżnimy język i metajęzyk
język metajęzyk
-----------------------------------------------------------------
|
p, q, r | "p", "q" (nazwa jednostkowa
| wyrażenia)
|
;p'"q | "p'"q"
|
pq | Õ, È, Õ ,..., Õ
1 n
| są to zmienne metajęzykowe
|
| % Õ a" È %
|
| jest to wynik pisania Õ i potem nazwa równoważnoÅ›ci,
| i potem È; cudzysłów kÄ…towy wprowadza nazw
| funktora
1) Implikacja
1
pq , jeżeli p to q,
jest wyrażeniem języka logiki
2) Wynikanie logiczne
Def. (Ajdukiewicz)
Z wyrażeÅ„ Õ ,..., Õ wynika logicznie wyrażenie Õ wtedy i tylko wtedy, gdy
1 n
implikacja
% Õ '" ... '" Õ Õ %
1 n
jest podstawieniem prawa logiki
Ex. a) Warszawa jest identyczna ze stolicÄ… Polski
b) Stolica Polski jest identyczna z WarszawÄ…
Pytanie
Czy z a) wynika b) ?
Odp.:
Wynika, gdyż x = y y = x
Õ '" ... '" Õ - racja
1 n
Õ - nastÄ™pstwo
3) Wnioskowanie (rozumowanie)
Wnioskowanie jest procesem myślowym, w którym na podstawie uznania
pewnych zdań, zwanych jego przesłankami, dochodzimy do uznania innego
zdania, zwanego wnioskiem, połączonego z przesłankami związkiem
uprawniającym do uznania wniosku na podstawie przesłanek.
Ze względu na rodzaj związku zachodzącego między przesłankami a wnioskiem
odróżnia się różne rodzaje wnioskowania.
LogikÄ™ interesuje tylko wnioskowanie dedukcyjne.
Określenie
Wnioskowanie dedukcyjne to takie wnioskowanie, w którym związek wynika
logicznie z przesłanek.
Znane sÄ… niededukcyjne sposoby wnioskowania.
2
BÅ‚Ä…d formalny we wnioskowaniu
Jeśli we wnioskowaniu traktowanym jako dedukcyjne wniosek nie wynika
logicznie z przesłanek, to mówimy o błędzie formalnym we wnioskowaniu.
Logika nie zajmuje siÄ™ wnioskowaniem jako
- czynnością
- procesem myślowym
ale rezultatem wnioskowania jako czynności myślowej.
Dla logiki ważne są przesłanki i wniosek, ich układ, a nie proces myślowy.
Logika nie zajmuje siÄ™ nawet konkretnym wnioskowaniem, ale formalnymi
schematami wnioskowań, pod które może podpadać wnioskowanie konkretne.
Def.
Formalne schematy rozumowania to takie schematy, gdzie przesłanki i wniosek
są formami zdaniowymi, zbudowanymi wyłącznie ze stałych logicznych i
zmiennych.
Znane są różne formalne schematy wnioskowania. Wśród nich znajdują się
schematy zawodne i niezawodne (logiczne).
Def.
Logiczny schemat wnioskowania to taki schemat, który jest zapisany wyłącznie
za pomocą stałych i zmiennych, w którym wniosek logicznie wynika z
przesłanek.
Ex. p q
p
--------
q
Z powyższej definicji wynika następujący wniosek: schemat wnioskowania
Õ
1
:
: (S)
Õ
n
-------
Õ
jest schematem logicznym wtedy i tylko wtedy, gdy implikacja
Õ '" ... '" Õ Õ (P)
1 n
jest prawem logiki.
3
Tę odpowiedniość trzeba tak rozumieć, że schemat S jest schematem logicznym
wtedy i tylko , gdy wyrażenie o postaci P, zapisane za pomocą stałych
logicznych i zmiennych jest prawem logiki.
Prawa logiki są gwarantem niezawodności odpowiednich schematów
implikacyjnych.
Reguły logiczne
W logice oprócz praw logicznych i schematów logicznych formułuje się reguły
wnioskowania
Charakterystyka reguły wnioskowania.
Ogólnie, są one zdaniami głoszącymi, że z pewnych wyrażeń zdaniowych
można wyprowadzić inne wyrażenia zdaniowe.
Ex. RO  reguła odrywania, formułowana w metajęyku
Z implikacji i jej poprzednika można wyprowadzić następnik
Reguły wnioskowania zapisuje się w postaci schematów reguł zwanych
schematami metasystemowymi (są to skrócone zapisy reguł)
Ex. ÕÈ
Õ
-------
È
W systemach logiki formalnej będziemy posługiwać się wyłącznie schematami
reguł dedukcyjnych (=logicznych), tzn. schematami reguł, w których wniosek
wynika logicznie z przesłanek.
Uwaga 1.
Reguły wnioskowania są zdaniami języka metasystemu. Głoszą one coś zawsze
o wyrażeniach zdaniowych pewnej postaci i posługują się nazwami tych
wyrażeń. Mogą one głosić, że określone schematy formalne są niezawodne.
Uwaga 2.
W prawach logiki i schematach logicznych używa się pewnych wyrażeń nic o
nich nie mówiąc.
Ex. p
4
 q
-----
p'"q
Zmienne "p" i "q" są zmiennymi zdaniowymi, za które można podstawiać
wyrażenia zdaniowe.
Uwaga 3.
Prawa logiki mogą być przesłankami lun wnioskami rozumowań.
Język założeniowego systemu rachunku zdań
1) stałe rachunku zdań: ~, '", (", , a"
2) zmienne zdaniowe: p, q, r, s, ..., p , ...
1
3) znaki pomocnicze: nawiasy (,)
Umowa
W ciÄ…gu symboli
~, '", (", , a"
każdy symbol występujący wcześniej wiąże silniej od wszystkich symboli
występujących po nim.
Definicja indukcyjna wyrażenia zdaniowego 1
Wyrażeniami zdaniowymi rachunku zdań są zmienne zdaniowe oraz wyrażenia
złożone utworzone z nich przy pomocy funktorów rachunku zdań
Precyzyjnie ujmuje się to przy pomocy definicji, złożonej z trzech warunków:
I Õ jest wyrażeniem zdaniowym 1-go rzÄ™du rachunku zdaÅ„ wttw, gdy Õ jest
zmiennÄ… zdaniowÄ…
II Õ jest wyrażeniem zdaniowym k-go rzÄ™du rachunku zdaÅ„ wttw, gdy
istnieje takie wyrażenie rachunku zdaÅ„ Õ , Õ , rzÄ™dów mniejszych niż k, że
1 2
jest
Õ = ~Õ
1
lub
Õ = Õ '" Õ
1 1 2
lub
Õ = Õ (" Õ
1 1 2
lub
Õ = Õ Õ
1 1 2
1
Jerzy Słupecki, Ludwik Borkowski: Elementy logiki matematycznej i teorii mnogości, PWN, Warszawa
1984, s. 8.
5
lub
Õ = Õ a" Õ
1 1 2
III Õ jest wyrażeniem rachunku zdaÅ„ wttw, gdy istnieje taka liczba n " N, że
Õ jest wyrażeniem rachunku zdaÅ„ n-tego rzÄ™du.
Wyrażeniami zdaniowymi rachunku zdań są zmienne zdaniowe i wyrażenia z
nich utworzone za pomocą funktorów rachunku zdań.
System założeniowy rachunku zdań 2
Pojęcie prawa logiki jest wyrażeniem semantycznym.
Pojęcie tezy jest wyrażeniem syntaktycznym.
Dowody założeniowe były stosowane od dawna w logice i w matematyce.
Posługiwał się nimi już Arystoteles dowodząc trybów sylogistycznych.
Jednak dopiero niedawno sformułowano reguły dla tych dowodów
Założeniowy system rachunku zdań jest oparty na regułach określających
sposób budowy dowodów wyrażeń.
Wśród tych reguł odróżniamy:
1) reguły pierwotne dołączania nowych wierszy do dowodu.
2) reguły tworzenia dowodów założeniowych
Ad1)
Reguły należą do metasystemu
RO: ÕÈ prawidÅ‚owo:% ÕÈ %
Õ % Õ %
------- ------------
È % È %
DK: Õ
È
------
Õ '"È
OK: Õ '"È Õ '"È
------- -------
2
Elementy logiki matematycznej i teorii mnogości, s. 17.
6
 Õ È
albo w postaci jednego schematu
Õ '"È
-------
Õ
È
Ogólnie, reguła o schemacie
Õ
1
:
:
Õ
n
---
È
1
:
:
È
k
stwierdza, że jeżeli do dowodu należą wyrażenia Õ ... , Õ , to do dowodu wolno
1, n
doÅ‚Ä…czyć każde z wyrażeÅ„ È , ... , È .
1 k
DA: Õ È
------- --------
Õ (" È Õ (" È
OA: Õ (" È Õ (" È (reguÅ‚a wtórna 3)
~Õ ~È
------- --------
È Õ
Obie reguły mówią, że do dowodu wolno dołączyć jeden człon alternatywy, o ile
do dowodu należy ta alternatywa i negacja innego jej członu.
DE: Õ È
È Õ
3
Elementy logiki matematycznej i teorii mnogości, s. 24.
7
---------
Õ a" È
OE: Õ a" È Õ a" È
-------- --------
Õ È È Õ
Ad2) Reguły tworzenia dowodów założeniowych
Założeniowy dowód wprost wyrażenia
(I) Õ (Õ [Õ ... {Õ Õ }...])
1 2 2 n-1 n
1. W n-1 wierszach dowodu wypisujemy kolejno wyrażenia od Õ do Õ jako
1 n-1
założenia dowodu twierdzenia.
2. a) Do dowodu jako nowe wiersze nożna dołączyć twierdzenia poprzednio
udowodnione.
b) Do dowodu jako nowe wiersze można dołączyć wyrażenia uzyskane w
oparciu o wiersze poprzednie za pomocą pierwotnych reguł dołączania nowych
wierszy do dowodu: RO, DK, OK, DA, OA, DE, OE.
3. Założeniowy dowód wprost jest zakończony kiedy w ostatnim wierszu
dowodu pojawi siÄ™ wyrażenie Õ .
n
Zakończenie dowodu zaznaczamy w ten sposób, że ostatniego wiersza nie
numerujemy.
Ex. (p q) [(q r) (p r)]
Dowód
1. p q z.
2. q r z.
3. p z.
4. q RO: 1,3
r RO: 2,4
Dowód założeniowy nie wprost wyrażenia (I)
1. a) tak jak w z.d.w: w n-1 wierszach dowodu wypisujemy kolejno
wyrażenia od Õ do Õ jako zaÅ‚ożenia dowodu twierdzenia.
1 n-1
b) w pierwszym wierszu dowodu piszemy, że ~Õ jako zaÅ‚ożenie dowodu
n
nie wprost.
8
2. tak w z.d.w.:
a) do dowodu jako nowe wiersze nożna dołączyć twierdzenia poprzednio
udowodnione.
b) do dowodu jako nowe wiersze można dołączyć wyrażenia uzyskane w
oparciu o wiersze poprzednie za pomocą pierwotnych reguł dołączania nowych
wierszy do dowodu: RO, DK, OK, DA, OA, DE, OE.
3. Dowód jest zakończonym jeśli występują w nim dwa wiersze sprzeczne
Zakończenie dowodu zaznaczamy w ten sposób, że ostatniego wiersza nie
numerujemy i piszemy "sprz." (jako skrót od "sprzeczność"), podając po prawej
stronie numeru dwóch wierszy sprzecznych.
Ex. (~p q) (~q p)
Dowód
1. ~p q z.
2. ~q z.
3. ~p z.d.n.
4. q RO: 1,3
sprz. 2,4
Założenia twierdzenia i założenia dowodu nie wprost będziemy nazywać
założeniami dowodu.
Jeśli dowodzone twierdzenie nie jest implikacją, to założeniem z.d.n. będzie
negacja dowodzonego twierdzenia.
Każdy dowód założeniowy wprost wyrażenia (I) daje się przekształcić w dowód
założeniowy nie wprost tego wyrażenia. Ale nie odwrótnie. Stąd mówimy, że
reguła tworzenia z.d.n jest pierwotna.
Wśród reguł dowodzenia i dołączania nowych wierszy do dowodu istnieją
reguły pierwotne i wtórne. Reguł pierwotnych się nie dowodzi. Reguły wtórne
mają na celu skrócenie dowodu. Dowodzi się ich na podstawie reguł
pierwotnych i na podstawie twierdzeń uzyskanych za pomocą reguł
pierwotnych.
Powyżej przedstawione reguły były sformułowane przez średniowiecznych
logików.
9
Wnioski 4
Reguły wtórne opuszczania i dołączania negacji
Tw. (a) (b)
~~p p p ~~p
Dowód Dowód
1. ~~p z. 1. p z.
2. ~p zdn. 2. ~(~~p) zdn.
sprz.: 1, 2 3. ~p ON: 2
sprz.: 1, 3
Reguła opuszczania negacji ON, wtórna ze względu na twierdzenie (a)
~~Õ
-----
Õ
Reguła dołączania negacji DK, wtórna ze względu na tw. (b)
Õ
------
~~Õ
Ex. ((p q) '" ~q) ~p
Dowód (1)
1. (p q) '" ~q z.
2. ~~p zdn.
3. p ON: 2
4. p q OK: 1
5. ~q OK: 1
6. q RO: 4, 3
sprz.: 5, 6
Dowód (2)
1. (p q) '" ~q z.
2. ~~p zdn.
3. ~~p p teza
4. p RO: 3, 2
5. p q OK: 1
4
Elementy logiki matematycznej i teorii mnogości, s. 17.
10
6. ~q OK: 1
7. q RO: 5, 4
sprz.: 6, 7
Stąd mamy regułę modus tollens
Õ È
~È
--------
~Õ
Na każdej tezie rachunku zdań o postaci implikacji, można oprzeć pewną regułę
wtórną
Uzasadnienie
Niech T będzie tezą rachunku zdań o postaci implikacji, tzn.
(I) Õ (Õ [Õ ... {Õ Õ }...]), n e" 2
1 2 2 n-1 n
reguła o schemacie
Õ
1
Õ
2
:
:
Õ
n-1
-------
Õ
n
jest wówczas regułą wtórna. Jeśli w dowodzie występuje każde z wyrażeń
Õ , Õ , ... ,Õ , to na podstawie metatezy, odpowiadajÄ…cej tezie T przez (n-1)
1 2 n-1
krotne zastosowanie reguÅ‚y odrywania otrzymujemy w dowodzie wyrażenie Õ .
n
Innym przykładem jest reguła sylogizmu hipotetycznego.
Reguła R dołączania nowych wierszy do dowodu jest wtórna wttw, gdy ilekroć
1
È jest uzyskane z wyrażeÅ„ Õ , ... , Õ za pomocÄ… reguÅ‚ R , tylekroć È daje siÄ™
1 n 1
uzyskać z wyrażeÅ„ Õ , ... , Õ za pomocÄ… reguÅ‚ pierwotnych i tez systemu.
1 n
Przy wypisywaniu założeń twierdzenia, można każde założenie będące
koniunkcją rozbić na poszczególne jej składniki, wypisując te składniki jako
osobne założenia.
11
Założenia dowodu nie wprost można wypisać bądz
dołączając znak negacji do
ostatniego następnika, bądz
skreślając znak negacji, jeśli ten następnik zaczyna
siÄ™ od znaku negacji.
Õ : ~~p a" p (skrajny przypadek implikacji)
n
Dowód
1. ~~p p teza
2. p ~~p teza
~~p a" p DE: 1, 2
Wniosek 1
Przyjmując w opisie dowodu założeniowego wprost, że n=1, otrzymujemy jako
przypadek szczególny zwykły dowód wprost. Każdy woersz takie dowodu jest
tezÄ… systemu.
Wniosek 2.
Jeżeli wyrażenie ma postać Õ a" È, to dla udowodnienia tego wyrażenia
wystarczy udowodnić implikację i implikację odwrotną, gdyż z obu tych
implikacji otrzymujemy równoważność wyjściową za pomocą reguły DE.
Ex. ~(p '" ~p), n=1
Dowód
1. p '" ~p zdn.
2. p OK: 1
3. ~p OK: 2
sprz.: 2, 3
Wniosek
Przyjmując w opisie zdn., że n=1 otrzymujemy jako szczególny przypadek
zwykły dowód nie wprost.
W dowodzie takim przyjmujemy negację lub wyrażenie sprzeczne do
dowodzonego twierdzenia, jako złożenie dowdou nie wprost i wyprowadzamy
stÄ…d dwa wiersze sprzeczne.
Podsumowanie
Wniosek 1
Jeżeli mamy założeniowy dowód wprost, to możemy zawsze otrzymać
założeniowy dowód nie wprost tego wyrażenia. Odwrotnie tak nie musi być.
Reguła tworzenia założeniowego dowodu wprost jest wtórna ze względu na
regułę tworzenia założeniowego dowodu nie wprost.
Wniosek 2
12
W badaniach nad logicznymi systemami dedukcyjnymi wprowadza się pojęcie
pozytywnego rachunku zdań. Tezami takiego rachunku zdań są wszystkie tylko
te wyrażenia rachunku zdań zapisane za pomocą znaków: '", (", , a", które to
wyrażenia dają się udowodnić za pomocą założeniowego dowodu wprost.
Znane jest też pojęcie pozytywnego implikacyjnego rachunku zdań.
Przybliżona charakterystyka tezy założeniowego rachunku zdań: każde
wyrażenie zdaniowe rachunku zdań, dla którego istnieje założeniowy dowód nie
wprost.
Ex.
W poniższym przykładzie zakładamy, że wszystkie liczby są całkowite.
Tw.
Jeżeli liczby całkowite x, y są podzielne przez a, to liczba x " b + y " b jest
1 2
podzielna przez a.
np. x=4, y=6, a=2, b =5, b =7
1 2
wtedy
4 " 5 + 6 " 7
dzieli siÄ™ przez 2.
Zauważmy, że dowodzone twierdzenie ma strukturę p q
Dowód wprost
x, y, a, b , b " Z z.
1 2
1. x, y sÄ… podzielne przez a z.
symbolicznie zapisujemy to: x|2, y|2
2. definicja podzielności
x jest podzielne przez y wttw, gdy istnieje taka liczba całkowita m, że
x = m " y
3. Skoro x, y są podzielne, to na mocy powyższej definicji istnieją liczby
całkowite m , m , takie, że
1 2
x = m " a
1
y = m " a
2
Ten wiersz dowodu wynika z wiersza 1 oraz 2.
4. Obie strony możemy pomnożyć przez tę samą liczbę. Zatem z wiersza 3
wynika, że
x " b = m " a " b
1 1 1
13
y " b = m " a " b
2 2 2
Widzimy, że prawe strony są podzielne przez a.
Mnożenie jest scharakteryzowane przez odpowiedni aksjomat arytmetyki
5. Obie równości możemy dodać parami. Zatem z wiersza 4 wynika, że
x " b + y " b = (m " b + m " b ) " a
1 2 1 1 2 2
na podstawie definicji podzielności i w. 5 uzyskujemy wniosek, że skoro obie
liczby są równe i ta po prawej stronie jest podzielna przez a, zatem i ta po lewej
też musi być podzielna przez a.
x " b + y " b jest podzielne przez a
1 2
Ex. Zakładamy, że zmienne przebiegają zbiór liczb całkowitych. Zakładany
też, że n jest liczbą pierwszą.
Liczba pierwsza to taka liczba, która dzieli się tylko przez 1 i przez samą siebie.
Tw.
Jeżeli n dzieli a " a, to n dzieli a.
twierdzenie ma strukturÄ™: p p
Dowód (nie wprost)
1. n dzieli a " a z.
2. n nie dzieli a zdn.
3. Jeżeli n dzieli a " b, i n nie dzieli a, to n dzieli b twierdzenie arytmetyki
4. Jeżeli n dzieli a " a, i n nie dzieli a, to n dzieli a 3, podstawienie
twierdzenia; struktura tw. (p '" q) r
5. (n dzieli a " a) '" (n nie dzieli a) DK: 1, 2
6. n dzieli a RO: 4, 5
sprzeczność 6, 2
14