Temat11

[ Pobierz całość w formacie PDF ]
11. DOWODZENIE V:
WYNIKANIE LOGICZNE I RÓWNOWAŻNOŚĆ LOGICZNA
11.1. Cele i wprowadzenie
Eksplikacja pojęć wynikania logicznego i równoważności logicznej w systemie SD
Umiejętność wykazywania zachodzenia relacji wynikania logicznego i równoważności
logicznej za pomocą dowodów
11.2. Wynikanie logiczne
O wniosku wyprowadzanym z założeń pierwotnych często mówiliśmy, że wniosek ten wynika z tych
założeń. Istotnie tak eksplikuje się pojęcie wynikania logicznego w systemie SD.
Zdanie
p
wynika logicznie (w systemie SD) ze zbioru zdań {
q
1
,
q
2
, …,
q
k
} zawsze i tylko
wtedy, gdy istnieje w systemie SD dowód, że
p
na podstawie zbioru założeń pierwotnych
{
q
1
,
q
2
, …,
q
k
}.
Niech wyrażenie ‘Γ
⊢
p
’ znaczy tyle, co ‘istnieje w systemie SD dowód, że p na podstawie zbioru
założeń pierwotnych Γ’. Mamy wtedy:
Zdanie
p
wynika logicznie (w systemie SD) ze zbioru zdań {
q
1
,
q
2
, …,
q
k
} zawsze i tylko
wtedy, gdy {
q
1
,
q
2
, …,
q
k
}
⊢
p
.
Możemy na tej podstawie zrozumieć też, że prawidłowość logiczna wnioskowania polega na tym, iż
wniosek wynika logicznie z przesłanek:
Wnioskowanie jest logicznie prawidłowe (w systemie SD) zawsze i tylko wtedy, gdy
gdy istnieje w systemie SD dowód wniosku na podstawie zbioru przesłanek.
11.3. Zdania równoważne logicznie
Dwa zdania są równoważne logicznie zawsze i tylko wtedy, gdy jedno logicznie wynika z drugiego:
Zdanie
p
jest logicznie równoważne (w systemie SD) zdaniu
q
zawsze i tylko wtedy, gdy
{
q
}
⊢
p
oraz {
p
}
⊢
q
.
Zdanie
p
jest logicznie równoważne (w systemie SD) zdaniu
q
zawsze i tylko wtedy, gdy istnieje w
systemie SD dowód, że
p
na podstawie zbioru założeń pierwotnych {
q
}, oraz gdy istnieje w systemie
SD dowód, że
q
na podstawie zbioru założeń pierwotnych {
p
}.
Przypomnijmy sobie równoważności logiczne, które byliśmy w stanie wyczuć już intuicyjnie, a z
których korzystaliśmy w Temacie dotyczącym symbolizacji. Mamy teraz możliwość uzasadnić nasze
intuicje.
© Katarzyna Paprzycka
11-1
Samouczek logiki zdań
(wersja wstępna)
Wszelkie prawa zastrzeżone
Uwagi proszę kierować na adres:
Katarzyna.Paprzycka@swps.edu.pl
11.3.1. Prawa de Morgana I: ‘ani
p
, ani
r
’
Jak pamiętamy uznaliśmy za logicznie równoważne również zdania:
(1) Nie jest prawdziwa ani teoria Watsona, ani teoria Skinnera.
(2) Nieprawda, że albo teoria Watsona albo teoria Skinner jest prawdziwa.
Zdaniom tym odpowiadają logicznie równoważne formuły logiki zdań:
[1] ~W ∧ ~S
[2] ~(W ∨ S)
S
: Teoria
S
kinnera jest prawdziwa
W
: Teoria
W
atsona jest prawdziwa
Możemy teraz udowodnić, że nasze intuicje nas nie zawodziły, konstruując: (a) dowód, że ~(W ∨ S) na
podstawie założenia, że ~W ∧ ~S oraz (b) dowód, że ~W ∧ ~S na podstawie założenia, że ~(W ∨ S).
Pierwszy z tych dowodów jest prostszy.
Wskazówki:
Przykład 1. Dowód (a)
1.
~W ∧ ~S
Zał.
2.
W ∨ S
Zał. (~Wpr)
3. ~W
∧Elim 1
4. S MTP 2, 3
5. ~S
∧Elim 1
W subderywacji należy wyprowadzić bezpośred-
nią sprzeczność, może to być albo para zdań ~W i
W, albo para zdań ~S i S. Spróbujmy
wyprowadzić sprzeczność S i ~S. Drugi element,
~S, jest łatwo dostępny. Skąd wziąć S?
Oczywiście z drugiej przesłanki. Aby
wyprowadzić S, trzeba najpierw otrzymać negację
pierwszego członu alternatywy znajdującej się w
wierszu 2, czyli trzeba najpierw otrzymać zdanie
~W. W prosty sposób otrzymamy je z wiersza 1.
6.
~(W ∨ S)
~Wpr 2–4, 2–5
Pełen dowód podany jest w
Rozwiązaniach
Wskazówki:
Przykład 2. Dowód (b)
1.
~(W ∨ S)
Zał.
2. W Zał. (~Wpr)
3. W ∨ S ∨Wpr 2
4.
~(W ∨ S)
R 1
Wniosek jest koniunkcją i możemy w tym
wypadku zastosować narzucającą się strategię
zastosowania reguły ∧Wpr. Musimy jednak
uzyskać oba człony ~W oraz ~S. Obydwa te
człony uzyskamy stosując regułę ~Wpr.
5. ~W
∧Wpr 2–3, 2–4
Pełen dowód podany jest w
Rozwiązaniach
5. ~W
∧Wpr 2–3, 2–4
5. ~W
∧Wpr 2–3, 2–4
6. S Zał. (~Wpr)
7.
W ∨ S ∨Wpr 6
8.
~(W ∨ S)
R 1
9. ~S
∧Wpr 6–7, 6–8
10.
~W ∧ ~S
∧Wpr 5, 9
Dowody te stanowią uzasadnienie naszych intuicji dotyczących zdań (1) i (2).
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 11. Dowodzenie V
11-2
11.3.2. Prawa de Morgana II: ‘nie zarówno
p
i
r
’
Jak pamiętamy uznaliśmy za logicznie równoważne zdania:
(1) Teoria Freuda i teoria Junga nie mogą być obie prawdziwe.
(2) Albo teoria Freuda albo teoria Junga jest fałszywa.
Zdaniom tym odpowiadają logicznie równoważne formuły logiki zdań:
[1] ~(F ∧ J)
[2] ~F ∨ ~J
F
: Teoria
F
reuda jest prawdziwa
J
: Teoria
J
unga jest prawdziwa
Możemy teraz udowodnić, że nasze intuicje nas nie zawodziły, konstruując: (a) dowód, że ~(F ∧ J) na
podstawie założenia, że ~F ∨ ~J oraz (b) dowód, że ~F ∨ ~J na podstawie założenia, że ~(F ∧ J).
Pierwszy z tych dowodów jest prostszy.
Wskazówki:
Przykład 3. Dowód (a)
1.
~F ∨ ~J
Zał.
2.
F ∧ J
Zał. (~Wpr)
3. ~F Zał. (~Wpr)
4. F
∧Elim 2
5. ~F
R 3
W subderywacji należy wyprowadzić bezpośred-
nią sprzeczność, może to być albo para zdań ~F i
F, albo para zdań ~J i J. Spróbujmy wyprowadzić
sprzeczność J i ~J. Pierwszy element, J, jest łatwo
dostępny. Skąd wziąć ~J? Oczywiście z pierwszej
przesłanki. Aby wyprowadzić ~J, trzeba najpierw
otrzymać negację pierwszego członu alternatywy,
czyli trzeba najpierw otrzymać zdanie ~~F.
Jedynym sposobem na otrzymanie ~~F jest za
pomocą reguły ~Wpr. Trzeba więc skonstruować
jeszcze jedną subderywację (wnuczkę) i w niej już
łatwo da się znaleźć bezpośrednia sprzeczność.
6. ~~F
~Wpr 3–4, 3–5
7. ~J
MTP 1, 6
8. J
∧Elim 2
6. ~~F
~Wpr 3–4, 3–5
7. ~J
MTP 1, 6
8. J
∧Elim 2
Pełen dowód podany jest w
Rozwiązaniach
~(F ∧ J)
~Wpr 2–7, 2–8
Wskazówki:
Przykład 4. Dowód (b)
1.
~(F ∧ J)
Zał.
2.
~(~F ∨ ~J)
Zał. (~Elim)
3. ~F Zał. (~Elim)
4.
~F ∨ ~J ∨Wpr 3
5.
~(~F ∨ ~J)
R 2
W subderywacji należy wyprowadzić bezpośred-
nią sprzeczność. Może to być albo para zdań:
~(F ∧ J) i F ∧ J, albo ~(~F ∨ ~J) i ~F ∨ ~J.
Gdyby to miała być ta druga para wówczas
musielibyśmy wyprowadzić najpierw ~F; jednak
wyprowadzenie ~F (za pomocą reguły ~Wpr)
nastręczałoby kłopotów (zastanów się jakich).
Spróbujmy zatem dążyć do otrzymania pierwszej
pary zdań bezpośrednio sprzecznych. ~(F ∧ J) już
mamy. Musimy zdobyć F ∧ J stosując regułę
∧Wpr. Musimy zatem zdobyć swobodnie stojące
zdanie F, oraz swobodnie stojące zdanie J. W
obydwu wypadkach pozostaje nam tylko ostatnia
deska ratunku w postaci reguły ~Elim. Jak
skonstruujecie odpowiednie subderywacje, to para
zdań bezpośrednio sprzecznych będzie już w
zasięgu dwóch reguł.
6. F
~Elim 3–4, 3–5
7. ~J Zał. (~Elim)
8.
~F ∨ ~J ∨Wpr 7
9.
~(~F ∨ ~J)
R 2
10. J ~Elim 7–8, 7–9
11.
F ∧ J ∧Wpr 6, 10
12.
~(F ∧ J)
Pełen dowód podany jest w
Rozwiązaniach
R 1
13.
~F ∨ ~J
~Elim 2–11, 2–12
Dowody te stanowią uzasadnienie naszych intuicji dotyczących zdań (1) i (2).
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 11. Dowodzenie V
11-3
11.3.3. ‘
p
chyba, że
r
’
Rozważając zdanie:
(1) Rozwiodę się, chyba że się zmienisz.
R
: Rozwiodę się
Z
: Zmienisz się
doszliśmy do wniosku, że można je sparafrazować na dwa logicznie równoważne sposoby:
(2) Jeżeli się nie zmienisz, to się rozwiodę, czyli: ~Z → R
(3) Albo się zmienisz, albo się rozwiodę, czyli: Z ∨ R
Możemy teraz udowodnić, że nasze intuicje nas nie zawodziły, konstruując: (a) dowód, że ~Z → R na
podstawie założenia, że Z ∨ R oraz (b) dowód, że Z ∨ R na podstawie założenia, że ~Z → R. Pierwszy
z dowodów jest bardzo prosty i nie wymaga komentarza. Drugi dowód jest trudniejszy, jeżeli ma być
przeprowadzany tylko w oparciu o reguły pierwotne. Staje się prostszy jeżeli opiera się na regule
podstawiania DeMorgana (DeM), która pozwala zdanie postaci ‘~(
p
∨
q
)’ zastąpić zdaniem postaci ‘~
p
∧ ~
q
’ zastosowanej w kroku 3:
Przykład 5. Dowód (a)
1.
Z ∨ R
Zał.
2. ~Z
Zał. (→Wpr)
3. R MTP 1, 2
4.
~Z → R →Wpr 2–3
Przykład 6. Dowód (b)
(z regułą DeM)
1.
~Z → R
Zał.
2.
~(Z ∨ R)
Zał. (~Elim)
3.
~Z ∧ ~R
DeM 2
4. ~Z
∧Elim 3
5. R
→Elim 1, 4
6. ~R
∧Elim 3
7.0
Z ∨ R
~Elim 2–5, 2–6
Rozwiązania
zawierają zarówno Dowód (b) z użyciem reguły DeM jak i ten dowód przeprowadzony
wyłącznie za pomocą reguł pierwotnych.
Ponownie obydwa dowody stanowią uzasadnienie dla naszych językowych intuicji. Jednocześnie
możliwość wykazania tych równoważności pokazuje, że w systemie dedukcji naturalnej ujęte są
głębokie prawidła rządzące myślą, które zakodowane są w naszym języku. Niesamowite jest zarówno
to, że je intuicyjnie wyczuwamy, jak i to że teraz jesteśmy w stanie lepiej zrozumieć źródła tych
zależności.
11.3.4. ‘
r
tylko jeśli
p
’
Rozważając zdanie:
(1) Wygrasz na loterii tylko jeśli kupisz bilet.
B
: Kupisz bilet
W
: Wygrasz na loterii
doszliśmy do wniosku, że można je sparafrazować na dwa logicznie równoważne sposoby:
(2) Jeżeli wygrasz na loterii, to [znaczy, że] musiałeś kupić bilet; czyli: W → B
(3) Jeżeli nie kupisz biletu, to nie wygrasz na loterii; czyli: ~B → ~W
Możemy teraz udowodnić, że nasze intuicje nas nie zawodziły, konstruując: (a) dowód, że ~B → ~W
na podstawie założenia, że W → B oraz (b) dowód, że W → B na podstawie założenia, że ~B → ~W.
Obydwa dowody są w miarę proste – pełne dowody znajdują się w
Rozwiązaniach
.
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 11. Dowodzenie V
11-4
Przykład 7. Dowód (a)
1.
W → B
Zał.
2. ~B
Zał. (→Wpr)
3. W Zał. (~Wpr)
4. B →Elim 1, 3
5. ~B
R 2
Przykład 8. Dowód (b)
1.
~B → ~W
Zał.
2. W
Zał. (→Wpr)
3. ~B Zał. (~Elim)
4. ~W →Elim 1, 3
5. W
R 2
6. ~W
~Wpr 3–4, 3–5
6. B
~Elim 3–4, 3–5
7.
~B → ~W
→Wpr 2–6
7.
W → B
→Wpr 2–6
Dowiedź, że następującymi pary zdań są logicznie równoważne:
(a) A
~~A
(b)
A
∧
A
A
(c) A
∨
A
A
(d)
A
→
(B
→
C)
(A
∧
B)
→
C
(e)
A
→
B
~A
∨
B
(f)
~(A
→
B)
A
∧
~B
(g) ~(~A
∨
B)
A
∧
~B
(h)
~(~A
∧
B)
A
∨
~B
Katarzyna Paprzycka,
Samouczek logiki zdań
(wersja wstępna): Temat 11. Dowodzenie V
11-5
[ Pobierz całość w formacie PDF ]