Elementy metalogiki rachunku zdań
cd.
1
Twierdzenie o dedukcji wprost dla KRZ
Intuicyjnie utożsamia się stwierdzenia:
Zdanie B jest wnioskiem ze zdania A (i ewentualnie pewnych dodatkowych przesłanek) oraz
Twierdzeniem jest zdanie: Jeżeli A, to B.
To intuicyjne utożsamienie ma podstawę w następującym twierdzeniu:
Twierdzenie 8 (O dedukcji wprost). Dla dowolnego zbioru X oraz formuł A i B zachodzi następująca zależność:
Jeżeli B ∈ Cn( X ∪ { A}), to ( A → B) ∈ Cn( X).
2
Twierdzenie o dedukcji wprost dla KRZ
Dygresja o dowodzie indukcyjnym. Dowód indukcyjny to zasadniczo proces dwuczęściowy:
Krok wyjściowy: Najpierw dowodzi się, że dana prawidłowość P zachodzi dla pierwszego przypadku-elementu danego zbioru X.
Krok indukcyjny: Następnie dowodzi się, że jeżeli prawidłowość P zachodzi dla k-tego przypadku-elementu zbioru X, to zachodzi ona również dla bezpośrednio po nim następującego ( k + 1)-ego przypadku. Zdanie stwierdzające, że „Prawidłowość P zachodzi dla k-tego przypadku=elementu zbioru X” nazywa się założeniem indukcyjnym.
Wniosek: Prawidłowość P zachodzi dla wszystkich przypadków-elementów zbioru X.
3
Twierdzenie o dedukcji wprost dla KRZ
Dowód.
Założenie: B ∈ Cn( X ∪ { A}).
Z założenia wnosimy, że istnieje co najmniej jeden dowód formuły B w oparciu o zbiór X ∪ { A}
(na gruncie KRZ). Niech tym dowodem będzie ciąg formuł:
D 1, D 2, ..., Dn.
Oczywiście, Dn = B. Wykażemy, że dla każdego i ≤ n zachodzi wzór: (*)
( A→ Di) ∈ Cn( X).
4
Twierdzenie o dedukcji wprost dla KRZ
Krok wyjściowy. Pokażemy to najpierw dla i = 1.
Skoro D 1 jest pierwszym wyrazem dowodu, więc na pewno D 1 ∈ Arz ∪ X ∪ { A}. Trzeba więc rozróżnić trzy przypadki w zależności od tego, czy D 1 ∈ Arz, czy D 1 ∈ X, czy D 1 ∈ { A}.
Przypadek 1: gdy D 1 ∈ Arz, to
(1.1)
D 1 ∈ Cn( X).
Ponadto,
(1.2)
D →
1
( A → D 1) ∈ Arz
i w rezultacie
(1.3)
D →
1
( A → D 1) ∈ Cn( X).
Z (1.1) i (1.3) na mocy syntaktycznego twierdzenia o odrywaniu wnosimy, że
(1.4)
( A → D 1) ∈ Cn( X),
a to dowodzi wzoru (*) dla tego przypadku.
5
Twierdzenie o dedukcji wprost dla KRZ
Przypadek 2: gdy D 1 ∈ X, rozumujemy analogicznie jak w przypadku pierwszym.
Przypadek 3: gdy D 1 ∈ { A}. Wtedy D 1 = A oraz ( A→ D 1) = ( A→ A). Ponadto, (3.1)
( A → A) ∈ Cn(∅),
a stąd
(3.2)
( A → A) ∈ Cn( X), bo ∅ ⊆ X
czyli
(3.3)
( A → D 1) ∈ Cn( X), bo D 1 = A.
A to dowodzi wzoru (*) dla tego przypadku.
Założenie indukcyjne.
Twierdzenie o dedukcji zachodzi dla wszystkich indeksów i < k, gdzie 1 < k ≤ n.
Krok indukcyjny. Pokażemy, że wzór (*) jest słuszny dla i = k, czyli że ( A → Dk) ∈ Cn( X).
Z uwagi na definicję dowodu rozważamy trzy przypadki:
6
Twierdzenie o dedukcji wprost dla KRZ
Przypadek 1: gdy Dk ∈ Arz ∪ X ∪ { A}. Rozumujemy tak samo jak w kroku wyjściowym.
Przypadek 2: gdy formuła Dk jest bezpośrednią konsekwencją na mocy RO pewnych dwu formuł
poprzedzających ją w dowodzie D 1, ..., Dn. Istnieją wtedy i, j < k takie, że Di = ( Dj → Dk).
Ponieważ i < k, więc na mocy założenia indukcyjnego:
(2.1) ( A → Di) ∈ Cn( X),
(2.2)
A → ( D →
j
Dk) ∈ Cn( X),
bo Di = ( Dj → Dk).
Z drugiej strony:
(2.3)
[ A → ( D →
j
Dk)] → [( A → Dj ) → ( A → Dk)] ∈ Arz,
i w rezultacie:
(2.4)
[ A → ( D →
j
Dk)] → [( A → Dj ) → ( A → Dk)] ∈ Cn( X).
Stąd oraz (2.2) na mocy syntaktycznego twierdzenia o odrywaniu:
(2.5)
( A → Dj ) → ( A → Dk) ∈ Cn( X).
7
Twierdzenie o dedukcji wprost dla KRZ
Ponieważ także j < k, więc zgodnie z założeniem indukcyjnym:
(2.6)
( A → Dj ) ∈ Cn( X).
Stosując znów syntaktyczne twierdzenie o odrywaniu do (2.5) i (2.6) otrzymujemy:
(2.7) ( A → Dk) ∈ Cn( X).
W ten sposób krok indukcyjny dowodu został zakończony.
Wzór (*) jest w szczególności słuszny dla i = n, czyli
( A → Dn) ∈ Cn( X),
a także wobec faktu, że Dn = B:
( A → B) ∈ Cn( X). ■
8
Twierdzenie o dedukcji wprost dla KRZ
Dygresja: Często powyższe twierdzenie formułuje się w postaci równoważności:
B ∈ Cn( X ∪ { A}) wtw ( A → B) ∈ Cn( X).
Dla dowodu zależności (←) zakładamy, że ( A → B) ∈ Cn( X).
Musimy pokazać, że B ∈ Cn( X ∪ { A}).
Wobec monotoniczności operacji Cn mamy też:
(1)
( A → B) ∈ Cn( X ∪ { A}) (bo X ⊆ X ∪ { A}).
Z drugiej strony:
(2)
A ∈ Cn( X ∪ { A})
(wobec zwrotności operacji Cn).
Stosując syntaktyczne twierdzenie o odrywaniu otrzymujemy:
(3)
B ∈ Cn( X ∪ { A}),
co kończy dowód. ■
9
Twierdzenie o dedukcji wprost dla KRZ
Wniosek: Dla dowolnych formuł A 1, A 2, ..., An oraz B zachodzi następująca zależność: Jeżeli B ∈ Cn({ A 1, A 2, ..., An}), to A 1 → [ A 2 → (... → ( An → B)…)] ∈ Cn(∅).
Dygresja. Przypomnijmy, A 1 → [ A 2 → (... → ( An → B)…)] to schemat implikacji wstępującej.
Przykłady:
T11.
p → (( p → q) → q).
Zgodnie z twierdzeniem o dedukcji wprost:
p → (( p → q) → q) ∈ Cn(∅),
o ile:
q ∈ Cn({ p, p → q}).
1. p
zał.
2. p → q
zał.
3. q
1, 2, RO. ■
10
Twierdzenie o dedukcji nie wprost dla KRZ
T12.
( p → q) → (( q → r) → ( p → r)).
Zgodnie z twierdzeniem o dedukcji wprost:
( p → q) → (( q → r) → ( p → r)) ∈ Cn(∅),
o ile:
r ∈ Cn({ p → q, q → r, p}).
1. p → q
zał.
2. q → r
zał.
3. p
zał.
4. q
1, 3; RO
5. r
2, 4; RO. ■
11
Twierdzenie o dedukcji nie wprost dla KRZ
Twierdzenie 9 (O dedukcji nie wprost dla KRZ – słabe). Dla dowolnego zbioru X i dowolnej formuły A zachodzi następująca zależność:
Jeżeli istnieje formuła C taka, że C, ~ C ∈ Cn( X ∪ { A}), to (~ A) ∈ Cn( X).
Dowód. Załóżmy, że C, ~ C ∈ Cn( X ∪ { A}), dla pewnej formuły C.
Korzystając z twierdzenia o dedukcji wprost dostajemy:
(1) ( A → C) ∈ Cn( X),
(2) ( A → ~ C) ∈ Cn( X).
Równocześnie:
(3) ( A → C) → (( A → ~ C) → ~ A) ∈ Cn( X) (bo jest to prawo KRZ).
Stosując dwukrotnie syntaktyczne twierdzenie o odrywaniu z uwagi na (1) i (2) dostajemy: (4) (~ A) ∈ Cn( X),
co kończy dowód. ■
12
Twierdzenie o dedukcji nie wprost dla KRZ
Dygresja: Często powyższe twierdzenie formułuje się w postaci równoważności:
(~ A) ∈ Cn( X) wtw istnieje formuła C taka, że C, ~ C ∈ Cn( X ∪ { A}).
Dla dowodu zależności (←) zakładamy, że (~ A) ∈ Cn( X).
Musimy pokazać, że istnieje formuła C taka, że C, ~ C ∈ Cn( X ∪ { A}).
Wobec monotoniczności operacji Cn mamy też:
(1)
(~ A) ∈ Cn( X ∪ { A}), bo X ⊆ X ∪ { A}
Z drugiej strony:
(2)
A ∈ Cn( X ∪ { A}) (wobec zwrotności operacji Cn).
Znaleźliśmy więc parę formuł wzajemnie sprzecznych będących konsekwencjami zbioru X ∪ { A}, mianowicie A i ~ A, co kończy dowód. ■
13
Twierdzenie o dedukcji nie wprost dla KRZ
Wniosek: Dla dowolnych formuł A 1, A 2, ..., An oraz B zachodzi następująca zależność: Jeżeli istnieje formuła C taka, że C, ~ C ∈ Cn({ A 1, A 2, ..., An, B}), to A 1 → [ A 2 → (... → ( An → ~ B)…)] ∈ Cn(∅).
Przykład:
T13.
( p → q) → (~ q → ~ p)
Zgodnie z twierdzeniem o dedukcji nie wprost: ( p → q) → (~ q → ~ p) ∈ Cn(∅),
o ile istnieje para formuł wzajemnie sprzecznych C, ~ C taka, że
C, ~ C ∈ Cn({ p → q, ~ q, p}).
1. p → q
zał.
2. ~ q
zał.
3. p
zał. d. n.
4. q
1, 3, RO; sprzeczność: 2 i 4. ■
14
Twierdzenie o dedukcji nie wprost dla KRZ
Twierdzenie 10. (O dedukcji nie wprost dla KRZ – mocne). Dla dowolnego zbioru X i dowolnej formuły A zachodzi następująca zależność:
Jeżeli istnieje formuła C taka, że C, ~ C ∈ Cn( X ∪ {~ A}), to A ∈ Cn( X).
Szkic dowodu: Załóżmy, że istnieje formuła C taka, że C, ~ C ∈ Cn( X ∪ {~ A}). Wykażemy, że A ∈ Cn( X). Na mocy twierdzenia poprzedniego, otrzymujemy: (~~ A) ∈ Cn( X). Wykorzystując prawo podwójnej negacji i syntaktyczne twierdzenie o odrywaniu pokazujemy, że A ∈ Cn( X), co kończy dowód. ■
Dygresja: Również to twierdzenie często formułuje się w postaci równoważności:
A ∈ Cn( X) wtw istnieje formuła C taka, że C, ~ C ∈ Cn( X ∪ {~ A}).
Wniosek: Dla dowolnych formuł A 1, A 2, ..., An oraz B zachodzi następująca zależność: Jeżeli istnieje formuła C taka, że C, ~ C ∈ Cn({ A 1, A 2, ..., An, ~ B}), to A 1 → [ A 2 → (... → ( An → B)…)] ∈ Cn(∅).
15
Twierdzenie o dedukcji nie wprost dla KRZ
Przykład:
T14.
( p → q) → ((~ p → q) → q)
Zgodnie z twierdzeniem o dedukcji nie wprost: ( p → q) → ((~ p → q) → q) ∈ Cn(∅),
o ile istnieje para formuł wzajemnie sprzecznych C, ~ C taka, że
C, ~ C ∈ Cn({ p → q, ~ p → q, ~ q)}).
1. p → q
zał.
2. ~ p → q
zał.
3. ~ q
zał. d. n.
4. ( p → q) → (~ q → ~ p) T12
5. ~ q → ~ p
1, 4, RO
6. ~ p
3, 5, RO
7. q
2, 6, RO; sprzeczność: 3 i 7. ■
16