Temat07

[ Pobierz całość w formacie PDF ]
7. DOWODZENIE I: REGUŁY
∧
WPR,
∧
ELIM,
→
ELIM
7.1. Cele i wprowadzenie
Umiejętność zastosowania reguł ∧Wpr, ∧Elim, →Elim
Umiejętność przeprowadzania prostych dowodów z użyciem reguł ∧Wpr, ∧Elim, →Elim
Żaden z tematów w podstawowym kursie logiki nie jest ani tak trudny jak dowodzenie, ani tak
użyteczny jak dowodzenie w systemie dedukcji naturalnej. Jednocześnie – jak w żadnym dotąd
temacie – są Państwo zdani wyłącznie na
Samouczek
, a przede wszystkim na ćwiczenia w nim zawarte.
Muszą Państwo wykonać je
wszystkie
, w dodatku muszą je Państwo wykonywać w momencie, w
którym są podane. Nie wolno Państwu pofolgować przyzwyczajeniom z czytania innych rozdziałów –
najpierw przeczytać całość i ją myślowo ogarnąć a potem przejść jeszcze raz. Po pierwsze się Państwo
zanudzą czytając całość, a po drugie wyda się Państwu to takie proste, że sięgną Państwo po
Samouczek
tuż przed egzaminem, po to tylko by egzamin oblać po skąpanej zimnym potem,
nieprzespanej nocy. Do dowodzenia należy podchodzić z pogodą duchą, wiarą w swoje siły – ale
jednocześnie i moje ostrzeżenia – oraz zapałem do systematycznej pracy. Należy ćwiczyć trochę
codziennie.
Na umiejętność dowodzenia składają się dwie umiejętności:
(a) umiejętność stosowania formalnych reguł wnioskowania
(b) umiejętność myślenia strategicznego
Paradoksalnie źródłem trudności w nauczeniu się dowodzenia jest to co – wydawać by się mogło –
najprostsze, a mianowicie umiejętność stosowania reguł inferencji. Komputery z łatwością bezbłędnie
stosują reguły inferencji, a z dowodzeniem mają kłopoty, bo trudniej nauczyć je myślenia
strategicznego. Ludzie natomiast świetnie sobie radzą z myśleniem strategicznym, trudno się jest im
natomiast zmobilizować do sztywnego stosowania reguł wnioskowania. Gdyby nie ta trudność, to
jestem głęboko przekonana, że można byłoby systemy dowodzenia w dedukcji naturalnej sprzedawać
tak, jak sprzedaje się gry strategiczne!
Jednym z zadań
Samouczka
jest pomóc Państwu w opanowaniu głównie tej pierwszej umiejętności.
Dla każdej wprowadzanej reguły inferencji będą musieli Państwo wykonać ćwiczenia, które pozwolą
Państwu wykształcić sobie „mentalny schemat” takiej reguły. Bez wykształcenia takiego schematu nie
nauczą się Państwo dowodzić. Aby umieć przeprowadzać dowody trzeba dosłownie widzieć struktury
logiczne i ich legalne (tj. dozwolone przez reguły) przekształcenia.
7.2. Dowodzenie jako uporządkowane rozumowanie
Dowodzenie nie jest niczym innym niż rozumowaniem, a dowód jest zapisem kolejnych kroków
myślowych.
Przykład 1
Jeżeli Ania zda logikę, to jej chłopak Tomek zaprosi ją albo do greckiej albo do francuskiej
restauracji. Tomek zapowiedział, że nie zaprosi jej do francuskiej restauracji, jeśli będzie
oglądała dużo TV. Ania zda logikę – jeśli będzie dobrze przygotowana, a będzie dobrze
przygotowana – jeśli będzie się dużo uczyć. Ania dużo się uczyła, ale też oglądała dużo TV.
Czy Tomek zaprosi Anię do restauracji? A jeśli tak, to do której? – Oczywiście, do greckiej. Jak do tej
odpowiedzi dochodzimy można zrekonstruować w formie „dowodopodobnej”:
© Katarzyna Paprzycka
7-1
Samouczek logiki zdań
(wersja wstępna)
Wszelkie prawa zastrzeżone
Uwagi proszę kierować na adres:
Katarzyna.Paprzycka@swps.edu.pl
(1)
Jeżeli Ania zda logikę, to jej chłopak Tomek zaprosi ją albo do greckiej albo do
francuskiej restauracji.
(Zał.)
(3)
Ania zda logikę – jeśli będzie dobrze przygotowana, a będzie dobrze
przygotowana – jeśli będzie się dużo uczyć. (Zał.)
(4)
Ania dużo się uczyła, ale też oglądała dużo TV. (Zał.)
(5)
Ania zda logikę. (3), (4)
(6)
Tomek zaprosi Anię albo do greckiej albo do francuskiej restauracji. (1), (5)
(7)
Tomek nie zaprosi Ani do restauracji francuskiej. (2), (4)
(8)
Tomek zaprosi Anię do restauracji greckiej. (6), (7)
‘(Zał.)’ jest skrótem od ‘Założenie’ i zaznacza te zdania, które są nam dane, które – przyjmujemy – są
prawdziwe. W powyższej historyjce dane są nam cztery założenia, z którym potem kolejno wyciągamy
wnioski (tzw. wnioski pośrednie: kroki (5)-(7)) aż do wniosku ostatecznego (8).
Przykład 2
Ujęcie rozumowania w formę „dowodopodobną” nie tylko pomaga je zrekonstruować i unaocznić, lecz
czasem pomaga nam w samym rozumowaniu. Dzieje się tak często wówczas, gdy mamy do czynienia
z tekstem powikłanym, a w szczególności niezbyt logicznie ułożonym, jak np. ten:
Tomek nie jest zainteresowany Beatą; Staś natomiast bardzo chciałby się z nią umówić. Beata
umówi się ze Stasiem albo wtedy, gdy zostanie przewodniczącym samorządu, albo gdy się
okaże, że Robert nie jest nią zainteresowany. Staś zostanie przewodniczącym samorządu, jeśli
albo Cecylia nie umówi się z nim, albo Paweł nie zostanie wybrany do samorządu. Cecylia nie
umówi się ze Stasiem, chyba że Beata zaprosi ją na imprezę. Jeśli Tomek nie jest
zainteresowany Beatą, to Beata nie zaprosi ani jego ani Cecylii na imprezę.
Czy Beata umówi się ze Stasiem? Zrekonstruujmy:
(1)
Tomek nie jest zainteresowany Beatą; Staś natomiast bardzo chciałby się z nią
umówić.
(Zał.)
(2)
Beata umówi się ze Stasiem albo wtedy, gdy zostanie przewodniczącym
samorządu, albo gdy się okaże, że Robert nie jest nią zainteresowany.
(Zał.)
(3)
Staś zostanie przewodniczącym samorządu, jeśli albo Cecylia nie umówi się z
nim, albo Paweł nie zostanie wybrany do samorządu.
(Zał.)
(4)
Cecylia nie umówi się ze Stasiem, chyba że Beata zaprosi ją na imprezę.
(Zał.)
(5)
Jeśli Tomek nie jest zainteresowany Beatą, to Beata nie zaprosi ani jego ani
Cecylii na imprezę.
(Zał.)
(6)
_________________________________________________________________
____
(7)
_________________________________________________________________
____
(8)
_________________________________________________________________
____
(9)
_________________________________________________________________
____
(10)
_________________________________________________________________
____
(11)
_________________________________________________________________
____
Proszę spróbować samodzielnie wyprowadzić wniosek, nie zapominając o „uzasadnieniach”, tj. o
zaznaczeniu, z którego wiersza Państwo korzystali. Odpowiedzi znajdą Państwo w
Rozwiązaniach.
Każdy krok rozumowania w dowodzie jest albo założeniem, albo jest
uzasadniony
jako wniosek
wynikający z wcześniejszych kroków w dowodzie. Różnica między powyższymi strukturami
„dowodopodobnymi” a dowodami formalnymi polega na tym, że w dowodach formalnych ściśle
określa się, które kroki są dozwolone za pomocą tzw.
reguł wnioskowania
lub
inferencji
. Reguły te są
regułami logicznie prawidłowego wnioskowania – ich zastosowanie gwarantuje, że nigdy nie
wyprowadzimy fałszywego wniosku z prawdziwych przesłanek. Cała trudność w dowodzeniu polega
na tym, aby się wdrożyć w konsekwentne stosowanie tych reguł.
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 7. Dowodzenie I
7-2
(2)
Tomek nie zaprosi Ani do francuskiej restauracji, jeśli Ania oglądała dużo TV.
(Zał.)
7.3. System dedukcji naturalnej SD (Bergman, Moore, Nelson, 1998)
7.3.1. Dowód w systemie SD
Dowód w systemie SD może wyglądać np. jak na Rys. 1:
Rys. 1.
System SD stosuje graficzny zapis dowodzenia, który bardzo ułatwia stosowanie tzw. konstrukcyjnych
reguł inferencji, które poznamy później. Na razie zapis graficzny sprowadza się do dwóch elementów:
linii dowodowej
, która jest pionową kreską zaznaczającą tok rozumowania składający się na
dany dowód – ważne jest to, aby zarówno przesłanki (założenia pierwotne, wiersze 1-4 na
Rys. 1), jak i wniosek (ostatni wiersz dowodu, wiersz 9 na Rys. 1) znajdowały się przy tej
samej linii dowodu;
linii założeń
, która jest poziomą kreską odgradzającą założenia od wniosków z nich
wyciąganych.
Zapis dowodu składa się z ciągu następujących po sobie, kolejno numerowanych wierszy. W każdym
wierszu występują trzy elementy: kolejny numer, zdanie wyprowadzane w danym kroku, oraz
uzasadnienie tego zdania.
Dowodem
w systemie SD jest skończony ciąg zdań (logiki zdań), w którym każde zdanie jest
albo założeniem (pierwotnym lub dodatkowym) albo jest uzasadnione przez jedną z reguł
systemu SD.
Zdanie α
można udowodnić
w systemie SD w oparciu o założenia β
1
, β
2
, …, β
k
, zawsze i
tylko wtedy, gdy w systemie SD istnieje dowód o założeniach pierwotnych β
1
, β
2
, …, β
k
, a α
występuje w zasięgu tych założeń (tj. przy głównej linii dowodowej).
O innych niż główna liniach dowodowych mówić będziemy w Temacie 9. Na razie do czynienia mamy
tylko z „głównymi” liniami dowodowymi.
7.3.2. Pierwotne reguły inferencyjne systemu SD
W systemie SD występuje jedenaście reguł inferencji – po dwie reguły dla każdego spójnika
logicznego (reguły wprowadzania i eliminacji) oraz reguła powtarzania R:
•Reguły dla koniunkcji: ∧Wpr, ∧Elim
•Reguły dla implikacji: → Wpr, →Elim
•Reguły dla równoważności: ≡Wpr, ≡Elim
•Reguły dla alternatywy: ∨Wpr, ∨Elim
•Reguły dla negacji:
~Wpr, ~Elim
•Reguła reiteracji:
R
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 7. Dowodzenie I
7-3
7.4. Reguła
∧
Elim (Reguła opuszczania koniunkcji, Symplifikacja)
Jeżeli we wcześniejszym wierszu dowodu występuje (swobodnie) koniunkcja
p
∧
r
,
to wolno do dowodu dołączyć wiersz, gdzie (swobodnie) występuje jeden z członów
tej koniunkcji.
i
.
p
∧
r
i
.
p
∧
r
¾
p
∧Elim
i
¾
r
∧Elim
i
Intuicje
Reguła ∧Elim jest jedną z najbardziej intuicyjnych reguł. O jej intuicyjności można się przekonać
przyglądając się np. jej zastosowaniu w języku naturalnym. Proszę ocenić, czy poniższe rozumowania
są prawidłowe:
Alicja jest piękna, ale i wredna.
Alicja jest wredna.
Zarówno teoria Freuda jak i teoria Junga jest fałszywa.
Teoria Freuda jest fałszywa.
Oczywiście oba rozumowania są logicznie prawidłowe. To nie znaczy – przypominam – że wniosek
jest prawdziwy, lecz tylko, że wniosek nie może być fałszywy, jeżeli przesłanki są prawdziwe. Oba są
też przykładami zastosowania reguły ∧Elim. Proszę zwrócić uwagę, że pierwsze rozumowanie – o
Alicji – jest przykładem zastosowania drugiej wersji ∧Elim (tej z prawej strony ramki), a drugie
rozumowanie – o Freudzie – jest przykładem zastosowania pierwszej wersji reguły ∧Elim.
Można w prosty sposób wykazać prawidłowość rozumowania opartego na regule ∧Elim odwołując się
do naszej wiedzy na temat wartości logicznych koniunkcji. Jeżeli wiemy, że koniunkcja jest
prawdziwa, to wiemy również, że dowolny jej człon jest prawdziwy.
Stosowanie reguły
∧
Elim
Regułę ∧Elim można zastosować do koniunkcji zawsze i tylko na
dwa sposoby
– można wyprowadzić
albo jej pierwszy człon, albo jej drugi człon, np:
1.
A ∧ (B ∧ C)
Zał.
2. A
∧Elim 1
3. B ∧ C ∧Elim 1
Nie wolno natomiast wyprowadzić„podczłonów”, tj. członów członów. Z powyższej koniunkcji
nie
wolno
wyciągnąć następujących wniosków:
1. A ∧ (B ∧ C)
Zał.
2. B
∧Elim 1
3. C
∧ Elim 1
∧Elim pozwala nam na wyprowadzenie członu danej koniunkcji, ale A ∧ (B ∧ C) ma tylko dwa człony:
A oraz (B ∧ C) – ani B ani C nie są zatem członami koniunkcji A ∧ (B ∧ C). Oczywiście zdania B i C
są członami drugiego członu tej koniunkcji. Zdania te możemy zatem wyprowadzić lecz tylko przez
podwójne zastosowanie ∧Elim:
1.
A ∧ (B ∧ C)
Zał.
2.
B ∧ C ∧Elim 1
3. B
∧Elim 2
4. C ∧Elim 2
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 7. Dowodzenie I
7-4
Należy zwrócić uwagę, że kroki 3 i 4 są wynikiem zastosowania reguły ∧Elim do wiersza 2, a nie do
wiersza 1.
7.5. Reguła
∧
Wpr (Reguła wprowadzania koniunkcji, Koniunkcja)
Jeżeli w pewnym wcześniejszym wierszu dowodu występuje (swobodnie) zdanie
p
oraz w innym wcześniejszym wierszu dowodu występuje (swobodnie) zdanie
r
, to
wolno do dowodu dołączyć wiersz, gdzie (swobodnie) występuje ich koniunkcja
p
∧
r
.
i
.
p
i
.
p
j. r
¾
p
∧
r
∧Wpr
i, j
j. r
¾
r
∧
p
∧Wpr
j, i
Intuicje
Reguła ∧Wpr jest również niezwykle intuicyjna – jeżeli wiemy, że dwa zdania są prawdziwe, to wiemy
również, że ich koniunkcja jest prawdziwa. O jej intuicyjności można się przekonać przyglądając się
np. jej zastosowaniu w języku naturalnym:
Ala dostała kota.
Ala dostała psa.
Ala dostała psa i kota.
Jeśli jutro będzie padać deszcz, to pójdę do kina.
Jeśli jutro będzie padać śnieg, to pójdę na sanki.
Jeśli jutro będzie padać deszcz, to pójdę do kina, a jeśli będzie padać śnieg, to pójdę na sanki.
Reguła ∧Wpr z pewnością zachowuje prawdziwość przesłanek: jeżeli obie przesłanki są prawdziwe, to
ich koniunkcja
musi
być prawdziwa.
Stosowanie reguły
∧
Wpr
Regułę ∧Wpr można zastosować do każdych dwóch swobodnie stojących zdań – zawsze i tylko na
dwa
sposoby
:
1.
A ∧ B
Zał.
2.
C
Zał.
3. (A ∧ B) ∧ C ∧Wpr 1, 2
4.
C ∧ (A ∧ B) ∧Wpr 2, 1
Nie wolno reguły ∧Wpr stosować do członów zdań:
1. A ∧ B Zał.
2.
C
Zał.
3.
B ∧ C ∧Wpr 1,2
4.
C ∧ A ∧Wpr 2,1
Uwaga! Można – choć nie jest to niezbędne – stosować konwencję rejestrowania kolejności dołączania
członów koniunkcji przez odpowiednie zapisanie w uzasadnieniu danego kroku numerów wierszy, na
których znajdują się te człony. Według tej konwencji wyrażenie kształtu ‘∧Wpr 2, 1’ znaczy tyle, co
‘Reguła ∧Wpr uzasadnia dołączenie koniunkcji, której pierwszym członem jest zdanie z wiersza 2, a
drugim członem zdanie z wiersza 1’.
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 7. Dowodzenie I
7-5
[ Pobierz całość w formacie PDF ]