7. Dedukcja naturalna
Załóżmy, że ktoś rozumuje w sposób następujący:
(1) Logika jest trudna lub niewielu studentów ją lubi,
(2) Jeżeli matematyka jest łatwa, to logika nie jest trudna.
Zatem: Jeżeli wielu studentów lubi logikę, to matematyka nie jest łatwa.
Jest to rozumowanie poprawne. I chociaż na pierwszy rzut oka może to być
niewidoczne, wniosek wynika tu logicznie z przesłanek. Jak moglibyśmy się o
tym przekonać? Korzystając z tego, co już wiemy, należałoby wykazać, że im-
plikację, której poprzednikiem jest koniunkcja przesłanek, a następnikiem wnio-
sek, można otrzymać przez podstawianie z jakiejś tautologii rachunku zdań.
Wymagałoby to zrekonstruowania schematu powyższego rozumowania i spraw-
dzenia, czy odpowiadająca mu formuła jest tautologią. Moglibyśmy posłużyć się
w tym celu metodą zerojedynkową. Byłoby to oczywiście dość uciążliwe. Przyj-
rzyjmy się zatem metodzie, którą zastosowałby tu matematyk. Powiedziałby on,
że należy po prostu udowodnić wniosek na podstawie przesłanek i zabrałby się
do tego następująco:
Załóżmy, że wielu studentów lubi logikę. Z założenia tego, na mocy prze-
słanki (1) wynika, że logika jest trudna. Z tego zaś, że logika jest trudna, na
mocy przesłanki (2) wynika, że matematyka nie jest łatwa, co kończy dowód.
Nasz matematyk będzie utrzymywał, że w ten sposób udowodnił wniosek na
podstawie jego przesłanek, a to, co zostało w ten sposób udowodnione, na pew-
no z nich wynika logicznie. Pewność tę opiera na tym, iż każdy krok, który tu
wykonał, był wnioskowaniem niezawodnym opartym na prawach logiki, czyli
dedukcjÄ….
W zastosowanej tu procedurze istotne jest to, że wniosek miał postać impli-
kacji. Pozwoliło to posłużyć się metodą dowodu założeniowego wprost. Meto-
da ta pozwala dołączyć do przesłanek poprzednik implikacji jako tzw. założenie
dowodu i zająć się dowodzeniem samego jej następnika. Dowodzenie to składa-
ło się z dwóch kroków. Aby uzyskać wgląd w ich strukturę i strukturę całego
dowodu, posłużymy się literowymi skrótami zdań i logicznymi symbolami
spójników. Wprowadz
my skróty:
L  zamiast  Logika jest trudna
S  zamiast  Wielu studentów lubi logikę
M  zamiast  Matematyka jest Å‚atwa
(Zauważmy, że w analizowanym tu rozumowaniu, występują również nega-
cje tych zdań.). Dowód, jaki przeprowadził nasz matematyk, możemy teraz
przedstawić następująco:
(1) L(" ŹS (przesłanka)
(2) M Ò! ŹL (przesÅ‚anka)
(3) S (założenie dowodu)
(4) L (otrzymane z (1) i (3))
1
(5) ŹM (otrzymane z (2) i (4))
Przechodząc od (1) i (3) do (4) oraz od (2) i (4) do (5) matematyk skorzystał
tu z reguł odpowiadających tautologiom logicznym. Są to tautologie:
(p (" Źq) '" q Ò! p oraz (p Ò! Źq)'"q Ò! Źp.1
Odpowiadające im niezawodne schematy wnioskowań to:
p Ò! Źq
p (" Źq
q
q
oraz
p Źp
Schematy takie są wygodnym zapisem reguł będących tu regułami dołą-
czania nowych wierszy do dowodu. Jak widać, dołączając wiersze nowe
(czyli te, które nie są ani przesłankami, ani założeniami dowodu) wymaga
się, aby one wynikały logicznie z wcześniejszych. Tym, czego się w naszym
przykładzie dowodu założeniowego dowodzi, nie jest oczywiście żaden z
wierszy dowodu, lecz implikacja S Ò! ŹM, której poprzednikiem jest zaÅ‚oże-
nie dowodu, a następnikiem ostatni wiersz dowodu. Wykazanie, że taka im-
plikacja wynika logicznie z przesłanek jest zadaniem dość skomplikowanym,
wymaga bowiem powoływania się na pewne twierdzenia metalogiczne mó-
wiące o własnościach relacji wynikania logicznego.2
Zamiast założeniowego dowodu wprost, nasz matematyk mógł tu posłu-
żyć się metodą dowodu założeniowego niewprost, polegającą na tym, że
oprócz poprzednika dowodzonej implikacji przyjąłby również jako założenie
negację jej następnika. Dowód przedstawiałby się wówczas następująco:
(1) L(" ŹS (przesłanka)
(2) M Ò! ŹL (przesÅ‚anka)
(3) S (założenie dowodu)
(4) Ź(ŹM) (założenie dowodu niewprost)
(5) M (otrzymane z (4))
(6) ŹL (otrzymane z (2) i (4)
(7) ŹS (otrzymane z (1) i (6)
(sprzeczność: (3) i (7))
Dowód ten kończy się, jak widać stwierdzeniem, że uzyskano dwa wier-
sze, z których jeden zaprzecza drugiemu. Jest to  tak, jak poprzednio  do-
wód implikacji S Ò! ŹM 3, a reguÅ‚y, z których korzystaliÅ›my w nim sÄ… prostsze i
bardziej uniwersalne. Przechodząc od (4) do (5) skorzystano z reguły pomijania
podwójnej negacji
1
O tym, że są to tautologie można przekonać się za pomocą metody zerojedynkowej.
2
W szczególności na tzw. twierdzenie o dedukcji mówiące, że jeśli zdanie q wynika ze zbioru zdań X z doda-
nym zdaniem p, to z samego zbioru X wynika implikacja p Ò! q.
3
Aby wykazać, że dowiedziona w ten sposób implikacja wynika z przesłanek należałoby powołać się na meta-
logiczną zasadę głoszącą, że: jeżeli ze zbioru zdań X powiększonego o zdania p i Źq wynikają dwa zdania
sprzeczne, to z samego zbioru X wynika implikacja p Ò! q.
2
Ź(Źp)
p
bÄ™dÄ…cej odpowiednikiem prostej tautologii Ź(Źp) Ò! p, natomiast w dwóch po-
zostałych krokach  z reguły
p Ò! q
p
q
odpowiadajÄ…cej tautologii (p Ò! q)'"p Ò!q. ReguÅ‚a ta zwana reguÅ‚Ä… odrywania
lub modus ponendo ponens obowiązuje również w aksjomatycznym ujęciu ra-
chunku zdań. Obie przedstawione tu w postaci schematów wnioskowania reguły
można wyrazić słowami:
Jeżeli wierszem dowodu jest zdanie poprzedzone podwójną negacją, to ja-
ko kolejny wiersz dowodu można zapisać samo to zdanie.
Jeżeli wierszami dowodu są implikacja i jej poprzednik, to można jako ko-
lejny wiersz zapisać jej następnik.
Zdanie, które usiłujemy dowieść na podstawie pewnych przesłanek nie
zawsze ma postać implikacji lub zdania logicznie jej równoważnego. Wówczas
dowód założeniowy nie ma zastosowania i musimy posłużyć się zwykłym do-
wodem wprost lub zwykłym dowodem niewprost. Ten pierwszy polega na
wyprowadzeniu wniosku z przesłanek za pomocą niezawodnych reguł w skoń-
czonej liczbie kroków. Często wymaga to użycia dość skomplikowanych reguł
lub dopisywania do dowodu pewnych prawd logicznych, czyli zdań uzyska-
nych z tautologii przez podstawianie. Aby tego uniknąć posługujemy się zwy-
kłym dowodem niewprost, w którym jako założenie przyjmujemy całe zdanie,
które zamierzamy udowodnić.
Taką strategię warto zastosować do rozumowania następującego:
(1) Marianna jest przekonana, że Michał nie nadaje się na męża.
(2) Jeżeli postępowanie Marianny jest zawsze zgodne z jej przekonania-
mi, to jeśli jest ona przekonana, że Michał nie nadaje się na męża, to nie
poślubi Michała.
(3) Marianna poślubiła Michała.
Zatem: Postępowanie Marianny nie zawsze jest zgodne z jej przekonaniami.
Zastosujemy tu skróty:
M  zamiast  Marianna jest przekonana, że Michał nie nadaje się na męża .
Z  zamiast  Postępowanie Marianny jest zawsze zgodne z jej przekonaniami .
P  zamiast  Marianna poślubi (względnie: poślubiła) Michała.
Dowód wniosku na podstawie przyjętych tu przesłanek przestawia się na-
stępująco:
(1) M (przesłanka)
(2) Z Ò! (M Ò! ŹP) (przesÅ‚anka)
3
(3) P (przesłanka)
(4) Ź (ŹZ) (założenie dowodu niewprost)
(5) Z (z (4) przez pominięcie podwójnej negacji)
(6) (M Ò! ŹP) (z (2) i (5)  reguÅ‚a odrywania)
(7) ŹP (z (6) i (1)  reguła odrywania)
(sprzeczność: (3) i (7)).
Przedstawione tu metody dowodzenia sÄ… spontanicznie stosowane przez
matematyków przy dowodzeniu twierdzeń matematycznych i z tej racji określa-
ne są mianem dedukcji naturalnej. Ale  jak pokazują nasze przykłady 
mogą być zastosowane do zdań mówiących o czymkolwiek, pod warunkiem, że
w sposób umożliwiający odtworzenie ich formy logicznej.
Każdy dowód wymaga posłużenia się regułami dołączania nowych wier-
szy. Im większym zasobem reguł dysponujemy, tym bardziej dowód bywa krót-
szy. Jednakże logicy starają się wskazać jakiś minimalny zestaw reguł, który
byłby zarazem wystarczający do przeprowadzenia dowolnego dowodu, jaki jest
możliwy na gruncie rachunku zdań. Wyróżniają zatem pewne reguły odpowia-
dające możliwie oczywistym tautologiom jako tzw. reguły pierwotne. Jest
wśród nich znana nam już reguła odrywania
p Ò! q
p
RO
q
a ponadto reguły:
p
DN (dołączania negacji)
Ź(Źp)
p '" q p '" q
OK (opuszczania koniunkcji)
p q
p
q
DK (dołączania koniunkcji)
p '" q
p (" q p (" q
Źp Źq
OA (opuszczania alternatywy)
q p
p q
DA (dołączania alternatywy)
p (" q p (" q
p Ô! q p Ô! q
OR (opuszczania równoważności)
p Ò! q q Ò! p
4
p Ò! q
q Ò! p
DR (dołączania równoważności).
p Ô! q
Z reguł tych można korzystać nie tylko przy dowodzeniu zdań o dowolnie
zróżnicowanej treści (jak w powyższych przykładach), lecz również dowodząc
tautologii rachunku zdań. Akceptując metodę tworzenia dowodów założenio-
wych, nie musimy wówczas przyjmować żadnych aksjomatów. Można zatem
powiedzieć, że  paradoksalnie  konstruujemy system aksjomatyczny ra-
chunku zdań bez aksjomatów.
Dla przykÅ‚adu, udowodnijmy dwie proste implikacje: p Ò! Ź(Źp) oraz
odwrotnÄ… Ź(Źp) Ò! p. DowodzÄ…c pierwszej posÅ‚użymy siÄ™ dowodem zaÅ‚oże-
niowym wprost.
(1) p (założenie)
(1) Ź(Źp).
Dowodząc drugiej zastosujemy dowód założeniowy niewprost.
(1) Ź(Źp) (założenie)
(2) Źp (założenie dowodu niewprost)
(sprzeczność: (1), (2)).
Dowodząc tautologii mających postać implikacji możemy do naszego re-
pertuaru środków dowodowych wprowadzić dodatkowe reguły wtórne. W ten
oto sposób uzyskaliśmy dwie użyteczne reguły:
p
DN (dołączania negacji)
Ź(Źp)
Ź(Źp)
ON (opuszczania negacji).
p
Z reguł tych możemy korzystać w dowodach kolejnych tautologii, na przykład
dowodząc prawa sprzeczności Ź(p '" Źp). Zastosujemy tu zwykły dowód nie-
wprost.
(1) Ź(Ź(p '" Źp)) (założenie dowodu niewprost)
(2) p '" Źp (ON, (1))
(3) p (OK, (2)
(4) Źp (OK, (2)
(sprzeczność: (3), (4)).
Kiedy dowodzimy implikacji, której następnik jest również implikacją itd.
to również poprzedniki tych kolejnych implikacji przyjmujemy jako założenia
dowodu. Tak właśnie postępujemy dowodząc tautologii zwanej prawem sylogi-
zmu hipotetycznego (p Ò! q) Ò!((q Ò! r) Ò! (p Ò!r)).
(1) p Ò! q (zaÅ‚ożenie)
(2) q Ò! r (zaÅ‚ożenie)
(3) p (założenie)
(4) q (RO, (1), (3))
(5) r (RO, (2), (4)).
5
Zamiast dowodzić tautologii mających postać implikacji możemy dowo-
dzić bezpośrednio odpowiadających im reguł. Na przykład tautologii
(p Ò!q) '"Źq Ò! Źp
p Ò! q
Źq
zwanej modus tollendo tollens odpowiada reguła . Jest to schemat
Źp
wnioskowania, w którym wyrażenia (p Ò!q) oraz Źq odpowiadajÄ… przeslan-
kom. Tak też je trakujemy w dowodzie.
(1) p Ò!q (przesÅ‚anka)
(2) Źq (przesłanka)
(3) Ź (Źq) (założenie dowodu niewprost)
(4) q (ON, (3))
(sprzeczność: (2), (4)).
Dedukcja naturalna jest prostym sposobem ujawniania związków wynika-
nia logicznego między zdaniami, natomiast wymaga pewnej inwencji w kwestii
wyboru metody dowodzenia i reguł dołączania nowych wierszy. Oczywiście,
ilekroć jest to możliwe, posługujemy się dowodem założeniowym. Dowód nie-
wprost jest z reguły łatwiejszy do przeprowadzenia. W praktyce  w miarę po-
trzeby  można jako kolejne wiersze dowodu dopisywać znane nam tautologie
lub odpowiadające im prawdy logiczne. Istnieją również inne metody uprasz-
czania dowodów, które nie zostały tu omówione.
Pamiętajmy jednakże, iż nie każdy dowód daje się przeprowadzić za pomocą
narzędzi, jakich dostarcza rachunek zdań. Kiedy wynikanie logiczne zależy od
struktury wewnętrznej zdań, która nie sprowadza się do negowania i łączenia
spójnikami, musimy odwołać się do mniej elementarnego działu logiki klasycz-
nej zwanego rachunkiem kwantyfikatorów.
.
6