Temat17 Dowodzenie Proste

[ Pobierz całość w formacie PDF ]
17. DOWODZENIE I: REGUŁY
∀
ELIM ORAZ
∃
WPR
17.1. Cele i wprowadzenie
zrozumienie potrzeby wprowadzenia logiki kwantyfikatorów
zastosowanie reguł
Wpr i
∀
Elim
17.1.1. Dlaczego warto uczyć się dowodzenia w logice kwantyfikatorów?
W przeciwieństwie do logiki zdań, w której symbolizacja zdań nie przysparza większych trudności,
umiejętność wyrażenia zdań języka naturalnego w logice kwantyfikatorów zakłada sporą wiedzę
logiczną. Warto jest opanować umiejętność dowodzenia w logice kwantyfikatorów, gdyż pozwala ona
nie tylko na badanie prawidłowości wnioskowań, ale również na swobodniejsze i pewniejsze
opanowanie symbolizacji. Okazuje się na przykład, że niby proste zdanie:
(1) Jeżeli ktoś w tym przedziale zapali papierosa, to wyrzucę go z pociągu.
daje się w logice kwantyfikatorów oddać w następujący sposób:
Dziedzina: ludzie
Rx: x
jest w tym przedziale
Zx: x
zapali papierosa
Wx:
wyrzucę
x
z pociągu
[1]
∀
x
((
Rx
∧
Zx
)
→
Wx
)
Może się to wydać w pierwszej chwili kontrintuicyjne, gdyż w zdaniu (1) zdaje się występować
partykularyzator, a nie generalizator. Niemniej jednak [1] oddaje jedyną dostępną w klasycznej logice
kwantyfikatorów symbolizację zdania (1). Dzieje się tak m.in. na mocy tego, że równoważne są sobie
schematy zdaniowe:
∃
x
Ax
→
Q
Q
)
gdzie
Q
jest po prostu pewnym zdaniem (w którym jednak nie występuje zmienna ‘
x
’). Można
oczywiście próbować wykuć wiele różnych równoważności i mieć nadzieję, po pierwsze, że wykucie
było skuteczne (nie przestawił się jakiś symbol), a po drugie, że wykute zostały wszystkie zależności
między schematami zdaniowymi, które będą przydatne w symbolizacji. Wydaje mi się jednak, że dużo
łatwiej jest poświęcić dwa tygodnie na opanowanie umiejętności dowodzenia w logice
kwantyfikatorów i w razie wątpliwości szkicować dowód.
Podobnie sprawa ma się w wypadku następującego zdania:
(2) Kobiety i mężczyźni powinni być równo traktowani w zakresie nawiązania i rozwiązania
stosunku pracy (…). (fragment § 1,
Kodeks Pracy
,
Art. 18
3a
)
którego symbolizacją jest nie zdanie:
x
(
Ax
→
∀
x
[(
Kx
∧
Mx
)
→
(
Nx
∧
Rx
)]
lecz zdanie:
[2]
∀
x
[(
Kx
∨
Mx
)
→
(
Nx
∧
Rx
)]
Warto zwrócić uwagę, że ‘i’ z wyrażenia ‘kobiety i mężczyźni’ jest interpretowane jako alternatywa, a
‘i’ z wyrażenia ‘nawiązywania i rozwiązywania stosunku pracy’ jako koniunkcja.
W przeciwieństwie do logiki zdań, w której metodę dowodzenia można zastąpić metodą
zerojedynkową do sprawdzania relacji logicznych między zdaniami, w wypadku logiki kwantyfikato-
rów nie ma odpowiednika metody zerojedynkowej. Jest to związane z tym po prostu, że kwantyfikatory
mogą przebiegać nieskończone dziedziny. Konsekwencją tego ograniczenia jest jednak to, że metoda
dowodzenia jest przydatną metodą sprawdzania zależności logicznych między zdaniami.
© Katarzyna Paprzycka
17-1
Samouczek logiki zdań
(wersja wstępna)
Wszelkie prawa zastrzeżone
Uwagi proszę kierować na adres:
Katarzyna.Paprzycka@swps.edu.pl
∃
∀
17.2. System KW
Elim. Tak się składa, że
reguła opuszczania generalizatora oraz reguła wprowadzania partykularyzatora są dużo prostsze niż
pozostałe dwie reguły. Od nich więc zaczniemy naszą podróż przez świat dowodzenia w logice
kwantyfikatorów.
∀
Wpr,
∀
Elim,
∃
Wpr,
∃
17.2.1. Reguły inferencyjne systemu ZD
Warto poświęcić parę słów jeszcze zastosowaniu reguł inferencji, które już znamy:
∧
Elim,
∧
Wpr,
Wpr, ~Elim, ~Wpr. Musimy pamiętać, że stosować się one
będą tylko i wyłącznie do zdań, w których głównym operatorem jest odpowiedni spójnik zdaniowy.
Zastanówcie się przez chwilę, do których z poniższych zdań wolno zastosować regułę
Elim,
∨
Wpr,
→
Elim,
→
Wpr,
≡
Elim,
≡
∧
Elim.
Wypiszcie pierwszy i drugi człon koniunkcji, który można uzyskać przez zastosowanie reguły
∧
Elim:
pierwszy człon
drugi człon
(1)
Aa
∧
Ba
Aa
Ba
(2)
∃
x
Ax
∧
Ba
∃
x
Ax
Ba
(3)
Aa
∧
∀
x
Bx
Aa
∀
x
Bx
(4)
∀
x
Ax
∧
∀
x
Bx
∀
x
Ax
∀
x
Bx
(5)
∀
x
(
Ax
∧
Bx
)
(6)
∃
x
(
Ax
∧
Bx
)
(7)
∀
x
(
Ax
∧
Bx
)
∧
x
(
Ax
∧
Bx
)
∀
x
(Ax
∧
Bx)
∃
x
(Ax
∧
Bx)
Elim można zastosować do powyższych zdań, wystarczy
odpowiedzieć na pytanie, czy spójnik koniunkcji jest spójnikiem głównym w tych zdaniach. Jest tak
oczywiście w przypadku zdania (1) – członami są tu zdania:
Aa
oraz
Ba
, a zatem obydwa mogą zostać
wyprowadzone za pomocą reguły
∧
∧
Elim. Jest tak również w przypadku (2), gdzie pierwszym członem
x
Ax
a drugim członem zdanie indywiduowe Ba. Analogicznie przedstawia się
sprawa w przypadku (3): pierwszym członem jest tym razem zdanie indywiduowe Aa a drugim –
generalizacja
∃
x
Bx
. W zdaniu (4) mamy ponownie do czynienia z koniunkcją – tym razem dwóch
generalizacji. W zdaniu (5) jednakże to generalizator jest funktorem głównym – ponieważ zdanie to nie
jest koniunkcją, więc nie można do niego zastosować reguły
∀
Elim. Oczywiście zdanie (5) jest
generalizacją pewnej koniunkcji, lecz aby się do tej koniunkcji »dostać« będziemy musieli wprowadzić
regułę pozwalającą na eliminację kwantyfikatorów. Podobnie jest w przypadku (6), gdzie tym razem
partykularyzator jest funktorem głównym. Natomiast zdanie (7) jest ponownie koniunkcją, której
członami są wewnętrznie złożone zdania skwantyfikowane.
∧
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 17.
Dowodzenie
17-2
W systemie KW obowiązywać będą wszystkie dotychczasowe reguły (pierwotne) systemu SD, które
jak pamiętamy stosują się do zdań. System KW będzie jednak uzupełniony o cztery reguły związane z
opuszczaniem i wprowadzaniem obu kwantyfikatorów:
∨
∃
Aby odpowiedzieć na pytanie, czy regułę
jest partykularyzacja
Rodzaje wyrażeń złożonych w logice kwantyfikatorów
Możemy teraz przedstawić pełniejszą klasyfikację zdań w logice kwantyfikatorów. Jest ona
wzbogacona o podziały na zdania złożone jednorodnie i niejednorodnie.
zdania
(zewnętrznie) proste
(zewnętrznie) złożone
jednorodne
niejednorodne
(zewnętrznie)
proste
indywiduowe
(atomowe)
(zewnętrznie)
proste
skwantyfikowane
(
∀
x
)
Wx
∨
Na
((
∃
x
)
Wx
∧
Na
)
∨
(
∃
x
)
Nx
Wa
Wc
Na
wewnętrznie
proste
wewnętrznie
złożone
(zewnętrznie)
złożone
indywiduowe
(zewnętrznie)
złożone
skwantyfikowane
Wa
∨
Na
(
∀
x
)
Wx
∨
(
∃
x
)
Nx
(
∀
x
)
Wx
~
Wa
(
Wa
~
(
∀
x
)
Wx
∨
Na
)
∧
~
Wc
(
∃
x
)(
Wx
∧
Nx
)
∨
(
∃
x
)~
Nx
(
∃
x
)
Wx
(
∀
x
)
Nx
jednorodne
niejednorodne
(
∀
x
) (
Wx
∨
Nx
)
(
∀
x
) (
Wx
∨
Na
)
(
∃
x
) ~
Wx
(
∀
x
) ((
Nx
∨
Wx
)
∧
Nx
)
Rys. 1.
Klasyfikacja typów zdań w logice kwantyfikatorów (por. tekst)
Reguły eliminacji spójników zdaniowych stosować się będą tylko i wyłącznie do zewnętrznie
złożonych zdań. Reguły eliminacji kwantyfikatorów natomiast stosować się będą tylko i wyłącznie do
zewnętrznie prostych zdań skwantyfikowanych.
Ćwiczenie 17.I.
Uzupełnij brakujące informacje.
(a)
(b)
1.
Ca
Zał.
1.
∀
x
Ax
Zał.
2.
Db
∧
Aa
Zał.
2.
~
∃
x
(
Bx
∧
Ax
)
Zał.
3.
Aa
∧
Elim 2
3.
∀
x
Ax
∧
~
∃
x
(
Bx
∧
Ax
)
∧
Wpr 1, 2
4.
Aa
∧
Ca
∧
Wpr 3, 1
4.
~
∃
x
(
Bx
∧
Ax
)
∧
∀
x
Ax
∧
Wpr 2, 1
(c)
(d)
1.
∀
x
Ax
∧
∃
x
Bx
Zał.
1.
∀
x
Ax
Zał.
2.
∀
x
(
Cx
∧
Dx
)
Zał.
2.
∃
x
Bx
Zał.
3.
∀
x
Ax
∧
Elim
1
3.
∀
x
Ax
∧
∃
x
Bx
∧
Wpr 1, 2
4.
∃
x
Bx
∧
Elim
1
4.
∃
x Bx
∧
(
∀
x Ax
∧
∃
x Bx
)
∧
Wpr 2, 3
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 17.
Dowodzenie
17-3
(e)
(f)
1.
∀
x
Ax
∧
∃
x
Bx
Zał.
1. ~
∀
x
Ax
∧
∃
x
Bx
Zał.
2.
∃
x
Bx
→
∀
x
Cx
Zał.
2.
∃
x
Bx
∨
∀
x
Ax
Zał.
3.
∃
x
Bx
∧
Elim 1
3.
~
∀
x
Ax
∧
Elim 1
4.
∀
x
Cx
→
Elim 2, 3
4.
∃
x
Bx
∨
Elim 2, 3
(g)
(h)
1.
(
∀
x Ax
∨
Ba
)
≡
∀
xCx
Zał.
1.
~
∀
x
Ax
∨
∃
x
Bx
Zał.
2.
Ba
Zał.
2.
~~
∀
x
Ax
Zał.
3.
∀
x
Ax
∨
Ba
∨
Wpr 2
3.
∃
x
Bx
∨
Elim 1, 2
4.
∀
x
Cx
≡
Elim 1, 3
4.
∃
x
Bx
∧
~~
∀
x
Ax
∧
Wpr 3, 2
Ćwiczenie 17.II.
Przeprowadź następujące dowody korzystając z reguł systemu ZD.
(a) Dowieść, że:
∀
(b) Dowieść, że:
x
Ax
→
(
∃
x
Bx
∧
∀
x
Cx
)
~
∀
x
Ax
1.
∀
x
Ax
→
∀
x
Cx
Zał.
1.
∀
x
Ax
→
∃
x
Bx
Zał.
2.
∀
x
Ax
→
∃
x
Bx
Zał.
2.
∀
x
Ax
→
~
∃
x
Bx
Zał.
4.
∨
Wpr 3
5.
∨
Wpr 1
5.
∨
Wpr 1
5.
∨
Wpr 1
6.
∧
Wpr 4,5
(c) Dowieść, że:
(
(d) Dowieść, że:
∃
x
Bx
→
∀
x
Cx
)
→
(
∀
x
Ax
→
∀
x
Cx
)
~~
∀
x
Cx
1.
∀
x
Ax
→
∃
x
Bx
Zał.
1.
(
∀
x
Cx
∧
∃
x
Bx
)
∧
∀
x
Ax
Zał.
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 17.
Dowodzenie
17-4
17.3. Reguła
∀
Elim (Reguła opuszczania generalizatora, Instancjacja)
Jeżeli we wcześniejszym wierszu dowodu występuje (swobodnie) generalizacja
∀
x
Φ
Φ
[
a/x
]*, dla dowolnego
a
.
i
.
∀
x
Φ
¾
Φ
[
a/x
]
∀
Elim
i
’ jest zmienną przebiegającą zbiór
wszystkich funkcji zdaniowych – zarówno prostych (np.
Ax
,
Bx
) jak i złożonych (np. ~
Ax
,
Ax
Φ
[
a/x
] wymaga pewnego komentarza. Otóż ‘
Φ
∨
Bx
).
[
a/x
]’ odczytujemy: rezultat podstawienia stałej indywiduowej
a
pod wszystkie
wystąpienia zmiennej
x
w funkcji zdaniowej
Φ
Φ
. Sens tych zapisów stanie się jaśniejszy, gdy
omówimy zastosowanie reguły
∀
Elim.
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:
∀
Wszyscy są wredni.
Alicja jest wredna.
Wszyscy pójdą albo do piekła, albo do nieba.
Aleksander Kwaśniewski pójdzie albo do piekła, albo do nieba.
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.
Stosowanie reguły
∀
Elim
Elim można stosować tylko do zewnętrznie prostych zdań skwantyfikowanych, których
głównym funktorem jest generalizator (bez względu na to, czy są to zdania wewnętrznie proste, czy
złożone.
∀
x
Px
Zał.
2.
Pa
∀
1.
∀
x
(
Px
∨
Qx
)
Zał.
∀
Elim 1
2.
Pa
∨
Qa
∀
Elim 1
3.
Pc
∀
Elim 1
3.
Pc
∨
Qc
∀
Elim 1
1.
∀
x
Px
∨
∀
Qx
Zał.
1.
∀
x
Px
∨
∀
Qx
Zał.
2.
Pa
∨
Qa
∀
Elim 1
2.
Pa
∨
∀
Qx
∀
Elim 1
3.
Pa
∨
Qa
∀
Elim 2
Pierwsze dwa zastosowania są uprawnione, trzecie i czwarte – nie. W trzecim i czwartym wypadku
zdanie nie jest w ogóle zdaniem ogólnym, lecz jest alternatywą. Ponieważ głównym funktorem zdania
drugiego jest generalizator, możemy zatem zastosować regułę
∀
Elim podstawiając nazwę
indywiduową
a
wszędzie tam, gdzie w złożonej funkcji zdaniowej
Px
∨
Qx
występuje zmienna
x
.
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 17.
Dowodzenie
17-5
, to wolno do dowodu dołączyć wiersz, gdzie (swobodnie) występuje zdanie
indywiduowe
* Zapis
Wyrażenie ‘
Intuicje
Reguła
Regułę
1.
[ Pobierz całość w formacie PDF ]