Klasyczny Rachunek Zdań
Semantyka KRZ cd.
1
Tautologie KRZ są wykorzystywane jako
• zasady formalnie poprawnych wnioskowań w tym sensie, że na każdej z nich można oprzeć pewną niezawodną regułę wnioskowania;
• źródło pewnych dodatkowych przesłanek w przeprowadzanych dowodach twierdzeń.
Wnioskowaniem nazywamy jakąkolwiek skończoną – co najmniej dwuwyrazową – sekwencję zdań, z których ostatnie jest wnioskiem, a wcześniejsze są przesłankami. Wnioskowanie nazywamy formalnie poprawnym lub dedukcyjnym wtw jego schematem jest niezawodna reguła wnioskowania, czyli taka, która od przesłanek prawdziwych prowadzi zawsze do prawdziwego wniosku. Ogólnie mówiąc, przez regułę wnioskowania rozumie się instrukcję stwierdzającą z jakiego rodzaju zdań jako przesłanek, jakie zdanie można otrzymać jako wniosek. Przy tym instrukcja ta podaje na ogół tylko strukturę owych zdań, nie wnikając w ich treść.
2
DEF. 9 (Reguła wnioskowania). Regułą (schematem) wnioskowania wyrażoną w języku KRZ
nazywamy dowolny skończony, co najmniej dwuwyrazowy ciąg formuł języka KRZ
〈 A 1, ..., An, B〉.
Ostatnią formułę nazywamy schematem wniosku, a formuły wcześniejsze schematami przesłanek.
Przykłady: Dla większej przejrzystości regułom wnioskowania nadaje się postać ułamków.
p ≡ ~ q
p → ~ q
p ∧ q
( p → q ∧
)
( q → r)
~ p ≡ q
q
,
,
,
.
p
p → q
( p ≡ ~ q) ∧ (~ p ≡ q)
~ p
Dwie pierwsze reguły można potraktować jako szczególne przypadki reguły o schemacie: A ∧ B . Powstają one z tego schematu w wyniku wstawienia za (metazmienne) A i B pewnych A
konkretnych formuł języka KRZ. Owe schematy reguł też będziemy nazywać regułami. ■
3
Semantyka KRZ
DEF. 10 (Niezawodna reguła wnioskowania).
A , ..., A
Reguła wnioskowania
1
n jest niezawodna (na gruncie KRZ) wtw dla każdego B
wartościowania v,
jeżeli v( A 1) = 1 i … i v( An) = 1, to również v( B) = 1.
W przeciwnym przypadku jest ona zawodna.
A , ..., A
Innymi słowy: Reguła wnioskowania 1
n jest niezawodna wtw nie istnieje wartościowanie
B
v, przy którym wszystkie jej przesłanki A 1, …, An uzyskują wartość 1, a wniosek B uzyskuje wartość 0. W przypadku, gdy takie wartościowanie istnieje – jest ona zawodna.
Dygresja: Reguły niezawodne (a więc i logika) dają więc gwarancję przechodzenia od prawdy do prawdy i tylko taką gwarancję (!). ■
4
Semantyka KRZ
Połączymy teraz pojęcie niezawodnej reguły wnioskowania z pojęciami tautologii i konsekwencji semantycznej (tj. wynikania logicznego).
Twierdzenie 4.
A , ..., A
Reguła wnioskowania 1
n jest niezawodna na gruncie KRZ wtw implikacja
B
A 1 ∧ … ∧ An → B
jest tautologią KRZ.
5
Semantyka KRZ
A , ..., A
Dowód. (→) Załóżmy, że reguła 1
n jest niezawodna oraz – dla dowodu nie wprost – że
B
( A 1 ∧ … ∧ An → B) ∉ Trz.
Wtedy istnieje wartościowanie v takie, że v( A 1 ∧ … ∧ An → B) = 0 (na mocy DEF. 7). Stąd A , ..., A
wnosimy, że v( A
1
n
1) = 1 i … i v( An) = 1, a v( B) = 0. To oznacza, że reguła jest
B
zawodna, wbrew założeniu.
A , ..., A
(←) Załóżmy, że ( A
1
n
1 ∧ … ∧ An → B) ∈ Trz oraz – dla dowodu nie wprost – że reguła
B
jest zawodna.
Wtedy istnieje wartościowanie v takie, że v( A 1) = 1 i … i v( An) = 1, a v( B) = 0 (na mocy DEF.
10). Wówczas zachodzi też równość: v( A 1 ∧ … ∧ An → B) = 0, czyli ( A 1 ∧ … ∧ An → B) ∉ Trz, wbrew założeniu. ■
6
Semantyka KRZ
Twierdzenie 5.
A , ..., A
Reguła wnioskowania 1
n jest niezawodna na gruncie KRZ wtw implikacja
B
A 1 → { A 2 → [ A 3 → (… → ( An → B) …)]}
jest tautologią KRZ.
Dowód tego twierdzenia przebiega analogicznie do dowodu twierdzenia poprzedniego.
Dygresja. A 1 → [ A 2 → (... → ( An → B)…)] to schemat implikacji wstępującej. Kolejne jego przypadki są następujące:
B
np. ( p → q) ∨ (~ p → ~ q) A 1 → B
np. ~( p ∧ q) → ~ p ∨ ~ q
A 1 → ( A 2 → B)
np. p → ( q → p ∧ q)
A 1 → ( A 2 → ( A 3 → B))
np. ( p → q) → (( p → r) → ( p → q ∧ r))
■
A 1 A 2 A 3 B
7
Semantyka KRZ
Przykłady:
Reguła
Prawo
p → q, p
( p → q) ∧ p → q
modus ponendo ponens
q
p → q, ~ q
( p → q) ∧ ~ q → ~ p
modus tollendo tollens
~ p
p ∧ q
( p ∧ q) → p
pr. symplifikacji
p
p → q, q → r
( p → q) ∧ ( q → r) → ( p → r) p → r
pr. sylogizmu hipotetycznego
p, ~ p
p → (~ p → q)
pr. przepełnienia
■
q
8
Semantyka KRZ
Wnioskiem z twierdzeń 3 i 4 jest twierdzenie następujące:
A , ..., A
Twierdzenie 6. Reguła wnioskowania 1
n jest niezawodna na gruncie KRZ wtw wniosek
B
B jest konsekwencją semantyczną przesłanek A 1, …, An.
Znaczy to, że stwierdzenia:
•
A , ..., A
reguła 1
n jest niezawodna,
B
• implikacja A 1 ∧ … ∧ An → B jest tautologią,
• B wynika logicznie z A 1, …, An
są równoważne.
9
Semantyka KRZ
Dygresja. Dedukcją nazywa się wnioskowanie oparte na jakieś regule niezawodnej, czyli takie, w którym wniosek wynika logicznie z przesłanek. Rozważmy wnioskowanie występujące w tzw. paradoksie wszechmocy (kieruje nim pytanie: Czy Bóg jest wszechmocny?).
Ponieważ:
P1. Bóg jest wszechmocny wtw może uczynić każdą rzecz.
P2. Bóg może stworzyć kamień tak ciężki, że nie może go podnieść bądź nie może stworzyć takiego kamienia.
P3. Jeżeli Bóg może stworzyć kamień tak ciężki, że nie może go podnieść, to nie może uczynić każdej rzeczy (bo nie może podnieść kamienia, o którym mowa).
P4. Jeżeli Bóg nie może stworzyć kamienia tak ciężkiego, że nie może go podnieść, to nie może uczynić każdej rzeczy (bo nie może stworzyć owego kamienia).
A zatem,
Bóg nie jest wszechmocny.
10
Semantyka KRZ
O dedukcyjnym charakterze tego wnioskowania przekonujemy się wykazując, że jest ono oparte na regule niezawodnej, a mianowicie:
p ≡ q, r ∨ ~ r, r → ~ q, ~ r → ~ q
.
~ p
Niezawodność tej reguły potwierdza tautologiczność implikacji:
( p ≡ q) ∧ ( r ∨ ~ r) ∧ ( r → ~ q) ∧ (~ r → ~ q) → ~ p
■
Ćwiczenie. Soryt (łańcusznik) średniowiecznych żaków:
Kto pije, ten śpi. Kto śpi, ten nie grzeszy. Kto nie grzeszy, jest święty.
Zatem, kto pije, jest święty.
(Łac.)
Qui bibit, dormit; qui dormit, non peccat; qui non peccat, sanctus est.
Ergo: qui bibit, sanctus est.
Czy podane wnioskowanie jest dedukcją? ■
11