Temat18 Dowodzenie

[ Pobierz całość w formacie PDF ]
18. DOWODZENIE II: REGUŁA
∀
WPR
18.1. Wprowadzenie
Wpr polega na tym, że z jednej strony musimy ją dołączyć do systemu, a z drugiej
strony jest to reguła, która zachowuje prawdziwość przesłanek tylko w ściśle określonych warunkach i
musi być w związku z tym obwarowana pewnymi ograniczeniami. Gdyby ograniczeń takich nie było
można byłoby dokonywać następujących inferencji:
∀
Ia
Dziedzina: ludzie
a
:= _________________________ [wpisz swoje imię i nazwisko]
Ix
:=
x
jest inteligentny
∀
x Ix
Rozumowanie to jest ewidentnie nieprawidłowe – zaczynamy od prawdziwych przesłanek a kończymy
na fałszywym wniosku. Kontrprzykładów dla tezy, że rozumowania tego kształtu są prawidłowe można
byłoby mnożyć:
Otylia Jędrzejczak zdobyła złoty medal olimpijski w pływaniu.
Zatem, wszyscy zdobyli złoty medal olimpijski w pływaniu.
Jolanta Kwaśniewska jest kobietą.
Zatem, wszyscy są kobietami.
Okazuje się jednak, że reguła wprowadzania generalizatora pełni ważną rolę w dowodach – pod
warunkiem m.in. że stosuje się ją do tzw. indywiduów arbitralnych, tj. indywiduów, które występują
tylko wewnątrz dowodu i które pozwalają nam na rozebranie zdań w najbardziej wyczerpujący sposób.
18.2. Cele
zrozumienie potrzeby wprowadzenia restrykcji dla reguły
∀
Wpr
opanowanie graficznej interpretacji restrykcji dla reguły
∀
Wpr
umiejętność stosowania reguły
∀
Wpr
18.3. O regule
∀
Wpr i o indywiduach arbitralnych
Rozważmy następujące rozumowanie:
Wszystkie małpy tworzą rodziny lub stada.
Wszystkie makaki są małpami.
Żadne makaki nie tworzą rodzin.
Wszystkiemakakiżyją w stadach.
Wnioskowanie to jest prawidłowe. Przyjrzyjmy się logicznej strukturze tych zdań:
© Katarzyna Paprzycka
18-1
Samouczek logiki zdań i kwantyfikatorów
(wersja wstępna)
Wszelkie prawa zastrzeżone
Uwagi proszę kierować na adres:
Katarzyna.Paprzycka@swps.edu.pl
Kłopot z regułą
(1)
Dla każdego
x
, jeżeli
x
jest małpą, to albo
x
jest członkiem rodziny, albo
x
jest
członkiem stada.
Dla każdego
x
, jeżeli
x
jest makakiem, to
x
jest małpą.
Dla każdego
x
jeżeli
x
jest makakiem, to nieprawda, że
x
jest członkiem rodziny.
(2)
(3)
Dla każdego
x
, jeżeli
x
jest makakiem, to
x
jest członkiem stada.
Weźmy pod uwagę dowolnego makakę. Na mocy (2) jest on z pewnością małpą. Na mocy (1) musi on
być albo członkiem rodziny albo członkiem stada. Na mocy (3) nie jest on członkiem rodziny. A zatem
ponieważ musi on być albo członkiem rodziny albo stada, a nie może być członkiem rodziny, więc
musi on być członkiem stada. Ponieważ rozważaliśmy dowolnego, arbitralnie wybranego, makakę,
więc nasz wniosek będzie się stosować do wszystkich makak.
We wnioskowaniu tym odwołaliśmy się do dowolnego, arbitralnie wybranego makaki. W rzeczy
samej, zastosowanie reguły
∀
Wpr będzie wymagało odwołania się do indywiduów arbitralnych.
18.3.1. Indywidua arbitralne
Powyższe wnioskowanie odwołuje się do indywiduum arbitralnego, postulowanego tylko na potrzeby
danego dowodu. Znaczy to w szczególności, że indywidua arbitralne nie mogą występować ani w
przesłankach pierwotnych ani we wniosku dowodu – mogą być postulowane tylko wewnątrz dowodu.
Aby podkreślić specjalny charakter reguły
∀
Wpr (a jak zobaczymy w następnym rozdziale również
Elim) oraz indywiduów, które są przez tę regułę zakładane, będziemy odwołując się do
indywiduów arbitralnych stosować odrębne symbole:
ⓐ
,
ⓑ
,
ⓒ
, ….
Aby uniknąć pomyłek przyjmiemy konwencję, że wprowadzamy do dowodu tylko takie indywidua
arbitralne, których nazwy nie pomylą się z nazwami występujących w dowodzie indywiduów. Jeżeli
np. w dowodzie mowa jest o indywiduum
a
, to nie wprowadzimy indywiduum arbitralnego
ⓐ
, lecz
indywiduum
ⓑ
.
Każde zastosowanie reguły wymagającej postulowanie indywiduów arbitralnych wymaga
zapostulowania nowego indywiduum arbitralnego. Jeżeli w dowodzie zastosowaliśmy już regułę
∃
Wpr
jednokrotnie, co wymagało zapostulowania indywiduum arbitralnego
ⓐ
, to w kolejnym zastosowaniu
reguły
∀
Elim, jak zobaczymy w następnym temacie), trzeba będzie
wprowadzić
inne
indywiduum arbitralne
ⓑ
(o ile nie występuje nigdzie w dowodzie indywiduum
b
).
Jeżeli reguła
∀
Wpr (a również reguły
∃
Wpr stosowana jest trzykrotnie, to do dowodu trzeba wprowadzić trzy
różne
indywidua
arbitralne. Jeżeli trzeba raz zastosować regułę
∀
∀
Wpr a następnie regułę
Elim, to do dowodu trzeba
wprowadzić dwa różne indywidua arbitralne.
Indywidua arbitralne zachowują się zupełnie normalnie – tj. tak samo jak pozostałe indywidua – jeżeli
chodzi o reguły
∀
Elim i
∃
Wpr oraz wszystkie reguły systemu ZD. Jeżeli dane jest dowolna
generalizacja np.:
(1)
∀
x
(
Px
→
(
Qx
→
Nx
))
to wolno zastosować regułę
∀
Elim podstawiając nazwę indywiduum arbitralnego za zmienną
x
.
(2)
P
ⓐ
→
(
Q
ⓐ
→
N
ⓐ
)
∀
Elim (1)
Podobnie jeżeli dane jest pewne zdanie indywiduowe traktujące o indywiduum arbitralnym – takie jak
(2) – to wolno zastosować regułę
∃
Wpr:
(3)
∃
x
(
Px
→
(
Qx
→
Nx
))
∃
Wpr (2)
Podsumujmy to, co powiedzieliśmy do tej pory o indywiduach arbitralnych:
•
Indywidua arbitralne są indywiduami teoretycznymi, postulowanymi na potrzeby dowodu
•
Ani przesłanki pierwotne, ani wniosek dowodu nie mogą zawierać nazwy jakiegokolwiek
indywiduum arbitralnego.
•
Każde zastosowanie zarówno reguły
∀
Wpr jak i reguły
Elim wymusza wprowadzenie do
dowodu nowego indywiduum arbitralnego.
•
Nazwa wprowadzanego do dowodu indywiduum arbitralnego musi różnić się od nazw
wszystkich indywiduów występujących w dowodzie – zarówno w przesłankach, jak i we
wniosku.
Katarzyna Paprzycka,
Samouczek
(wersja wstępna): Temat 18.
Dowodzenie
18-2
reguły
∃
∃
•
Reguła
Wpr stosują się bez zastrzeżeń również do indywiduów
arbitralnych; zdania o indywiduach arbitralnych zachowują się jak zdania indywiduowe
względem reguł system ZD.
∀
Elim oraz reguła
∃
18.3.2. Zakluczone indywidua arbitralne i ich komnaty
Aby ułatwić zadanie pamiętania o rozmaitych ograniczeniach, które ciążą na indywiduach arbitralnych
wprowadzimy dla nich specjalne graficzne »komnaty«
1
, w których indywidua te będą »zakluczone«.
Każde indywiduum ma swoją komnatę i żeby o tym pamiętać oznaczymy każdą komnatę nazwą tego
indywiduum w prawym górnym rogu.
ⓐ
Komnaty są swego rodzaju subderywacjami. Ogólną zasadą jest jednak to, że zakluczone w komnacie
indywiduum nie może się nigdy wydostać poza komnatę:
Zasada zakluczenia
Tylko zdania znajdujące się w komnacie dla indywiduum
ⓐ
mogą zawierać nazwę ‘
ⓐ
’.
Następujące zastosowanie reguły
∀
Elim będzie więc nieuprawnione, gdyż gwałci zasadę zakluczenia:
∀
x Bx
ⓐ
ⓐ
Elim do indywiduum arbitralnego
ⓐ
wolno wykonać, ale tylko
wewnątrz komnaty, w której
ⓐ
jest zakluczone.
Komnaty – podobnie jak subderywacje – mogą być w sobie zagnieżdżone.
∀
4.
∀
x Bx
W tym wypadku mamy do czynienia z sytuacją, gdzie
komnata dla indywiduum
ⓐ
»gości« komnatę dla
indywiduum
ⓑ
oraz dla indywiduum
ⓒ
. Żadne
indywiduum arbitralne nie może opuścić komnaty, w
której jest zakluczone – jednakże indywiduum
arbitralne (np. indywiduum
ⓐ)
goszczące inne
indywiduum arbitralne (np. indywiduum
ⓑ)
może
wchodzić do komnat goszczonego indywiduum.
Zatem indywiduum
ⓐ
może pojawiać się zarówno w
komnacie dla indywiduum
ⓑ
jak i w komnacie dla
indywiduum
ⓒ
.
ⓐ
ⓑ
B
ⓐ
∀
Elim 4
B
ⓑ
∀
Elim 4
B
ⓐ
∀
Elim 4
ⓒ
B
ⓐ
∀
Elim 4
B
ⓒ
∀
Elim 4
B
ⓐ
∀
Elim 4
1
Zostały one wprowadzone w systemie Kennetha Mandersa.
Katarzyna Paprzycka,
Samouczek
(wersja wstępna): Temat 18.
Dowodzenie
18-3
Krok ten, tj. zastosowanie reguły
Komnaty nie mogą się jednakże przecinać:
ⓐ
ⓒ
Podobnie sprawy się mają z subderywacjami. Subderywacje mogą występować wewnątrz komnat, oraz
komnaty mogą występować wewnątrz subderywacji, ale nie mogą się nawzajem przecinać.
ⓐ
ⓐ
Komnaty nie mogą też zawierać ani założeń pierwotnych dowodu (choć mogą zawierać założenia
wtórne poszczególnych subderywacji), ani wniosku ostatecznego dowodu.
Zasada wnętrza
Wniosek oraz założenia pierwotne dowodu muszą znajdować się poza jakąkolwiek
komnatą.
18.3.3. Reguła R oraz komnaty
Komnata dla reguły
∀
Wpr nie jest oparta na żadnych założeniach dodatkowych (w przeciwieństwie do
Elim, jak zobaczymy), dlatego regułę R można stosować do zdań znajdujących
się w komnacie skonstruowanej dla reguły
∃
Wpr pod warunkiem, że nie gwałci się zasady zakluczenia
oraz przestrzega innych ograniczeń reguły R.
∀
ⓐ
3 B
ⓐ
5
ⓐ
x
Bx
7
∃
5
∃
x
Bx
x
Bx
10 B
ⓐ
∀
9
∃
x
Bx
R5
R3
11
∃
x
Bx
R5
x
Bx R7
∀
Katarzyna Paprzycka,
Samouczek
(wersja wstępna): Temat 18.
Dowodzenie
18-4
komnaty dla reguły
12
18.4. Reguła
∀
Wpr (Reguła dołączania generalizatora)
Jeżeli w dowodzie macierzystym można skonstruować komnatę dla arbitralnego
indywiduum
ⓐ
oraz wyprowadzić w jej ostatnim wierszu zdanie indywiduowe
Φ
∀
x
Φ
.
∀
:
ⓐ
i
j
Φ
[
ⓐ
/x
]
¾
∀
x
Φ
∀
Wpr
i-j
nie może zawierać już indywiduum arbitralnego
ⓐ
– byłoby to
pogwałceniem zasady zakluczenia. Jak pamiętamy, w uzasadnieniach zdań wyprowadzanych za
pomocą reguł wymagających wprowadzenia subderywacji zawsze odwoływaliśmy się do całej
subderywacji. Podobnie jest w wypadku reguły
∀
x
Φ
Wpr, gdzie powołujemy się na ciąg wierszy
począwszy od pierwszego wiersza w komnacie do wiersza ostatniego.
∀
Wpr
Reguła wprowadzania generalizacji jest regułą konstrukcyjną. Zawsze, gdy chcemy wprowadzić
generalizację musimy najpierw skonstruować komnatę, a reguła
∀
Wpr – łącznie z ogólnymi zasadami
dotyczącymi indywiduów arbitralnych (por. §18.3) –
ściśle determinuje
, po pierwsze, jakie
indywiduum musi być zakluczone w tej komnacie, a po drugie, jakie musi być ostatnie zdanie w tej
komnacie (zawsze: instancja generalizacji, którą chcemy wyprowadzić, dla zakluczonego w tej
komnacie indywiduum).
∀
Ćwiczenia na stosowanie reguły
∀
Wpr
Wpr, aby
wyprowadzić pewną generalizację. Aby to zrobić trzeba skonstruować komnatę (została już
skonstruowana). Podaj jakie zdanie można wyprowadzić poza komnatą w wierszu 9.
Wpr.I.a.
W każdym z poniższych „szkieletów dowodowych” trzeba zastosować regułę
∀
(a)
(b)
∀
:
ⓐ
∀
:
ⓐ
5
5
8
A
ⓐ
8
~A
ⓐ
9
∀
x
Ax
∀
Wpr 5-8
9
∀
x
~
Ax
∀
Wpr 5-8
(c)
(d)
∀
:
ⓐ
∀
:
ⓐ
5
5
8
B
ⓐ
→
A
ⓐ
8
~B
ⓐ
∨
(
A
ⓐ
→
B
ⓐ
)
9
∀
x
(
Bx
→
Ax
)
∀
Wpr 5-8
9
∀
x
(
~Bx
∨
(
Ax
→
Bx
))
∀
Wpr 5-8
Katarzyna Paprzycka,
Samouczek
(wersja wstępna): Temat 18.
Dowodzenie
18-5
[
ⓐ
/x
],
to wolno zamknąć komnatę, a do dowodu macierzystego dołączyć wiersz, gdzie
(swobodnie) występuje generalizacja
Oczywiście generalizacja
Konstruowanie komnat dla Reguły
∀
[ Pobierz całość w formacie PDF ]