Cn(X) – zbiór wszystkich konsekwencji inferencyjnych zbioru formuł X.
Intuicyjnie utożsamia się stwierdzenia:
Zdanie B jest wnioskiem ze zdania A (i ew. pewnych dodatkowych przesłanek)
oraz
Twierdzeniem jest zdanie: Jeżeli A, to B.
To intuicyjnie ma podstawę w następującym twierdzeniu:
Twierdzenie 8. (o dedukcji wprost) Dla dowolnego X oraz formuł A i B zachodzi następująca zależność:
Jeżeli B e Cn(X u {A}), to (A → B) e Cn(X).
Specjalna metoda dowodzenia:
Twierdzenie to dowodzi się przez tzw. indukcję względem długości dowodu:
Za pomocą dowodu indukcyjnego można wykazać, że twierdzenie jest prawdziwe w nieskończenie wielu przypadkach, sprawdzając je bezpośrednio tylko w jednym przypadku.
Dowód indukcyjny jest dwuczęściowy
· krok wyjściowy – dowodzi się, że dana prawidłowość p zachodzi dla pierwszego, najprostszego przypadku
· krok indukcyjny – dowodzi się, że jeżeli prawidłowość p zachodzi dla k-przypadku, to zachodzi również dla k+1 przypadku.
· Wniosek: stwierdza się, że rozważana prawidłowość p zachodzi dla w ogóle wszystkich przypadków.
Metaforycznie: nieskończenie wiele przypadków, można wyobrazić sobie jako nieskończony szereg kostek domina, aby udowodnić każdy przypadek, trzeba znaleźć sposób aby przewrócić wszystkie kostki domina [pojedynczo było by bezsensu, bo jest ich nieskończenie wiele]; dowód indukcyjny wykorzystuje efekt domina, jeśli jest odpowiednio skonstruowany: jeśli przewróci się pierwszą, ta przewróci następną i w nieskończoność. Metoda indukcyjna pozwala przewrócić wszystkie kostki, o ile przewróci się pierwszą z nich a wszystkie będą starannie ułozone.
Jeżeli twierdzenie jest prawdziwe dla liczby n>=0, to jest również prawdziwe dla n+1.
1. Rozważane twierdzenie jest prawdziwe dla najmniejszej liczby naturalnej – 0
2. Skoro twierdzenie jest prawdziwe dla liczby 0, to jest prawdziwe dla 1, a skoro dla 1, to dla 2 itd.
Dowód
Założenie: B e Cn(X u {A}).
Z założenia wnosimy, że istnieje co najmniej jeden dowód formuły B w oparciu o zbiór X u {A} (na gruncie KRZ). Niech tym dowodem będzie ciąg formuł:
D1, D2, …, Dn
Oczywiście Dn = B. Wykażmy, że dla każdego i =< n zachodzi wzór:
((*) - będzie się powtarzał) (A → Di) e Cn(X)
(1) Krok wyjściowy:
Pokażmy, to najpierw dla i = 1.
Skoro D1 jest pierwszym wyrazem dowodu, więc na pewno D1 e Arz u X u {A}. Trzeba więc rozróżnić trzy przypadki w zależności od tego czy D1 e Arz, czy D1 e X, czy D1 e {A}
Przypadek 1: Gdy D1 e Arz, to:
1.1 . D1 e Cn(X).Ponadto:
1.2 . D1 → (A → D1) e Arzw rezultacie:
1.3 . D1 → (A → D1) e Cn(X)
Z 1,1 i 1.3 na mocy syntaktycznego twierdzenia o odrywaniu wniosimy, że
1.4. (A->D1) e Cn(X)
a to dowodzi wzoru (*) dla tego przypadku.
Przypadek 2: Analogicznie do przypadku 1! na mocy twierdzenie o zwrotności.
Przypadek 3: Gdy D1 e {A}. Wtedy D1 = A oraz (A → D1) = (A → A). Ponadto
[O – zbiór pusty]
3.1 (A->A) e Dn(O).
a stąd
3.2 (A → A) e Cn(X), bo O _c X
czyli
3.3 (A → D1) e Cn(X), bo D1 = A.
A to dowodzi wzoru (*) dla tego przypadku.
Założenie indukcyjne:
Twierdzenie o dedukcji zachodzi dla wszystkich indeksow i < k gdzie 1 < k =< n.
Krok indukcyjny: Pokażemy, że wzór (*) jest słuszny dla i=k, czyli że (A → Dk) e Cn(X).
Z uwagi na definicję dowodu rozważamy trzy przypadki:
Przypadek 1: gdy Dk e Arz u X u {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 D1,..., 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) e Cn(X)
2.2) A → (Dj → Dk) e Cn(X), bo Di – (Dj → Dk).
Z drugiej strony:
2.3) [A → (Dj → Dk)] → [(A → Dj) → (A → Dk)] e Arz.
2.4) [A → (Dj → Dk)] → [(A → Dj) → (A → Dk)] e Cn(X)
Stąd oraz (2.2) na mocy syntaktycznego twierdzenia o odrywaniu:
2.5) (A → Dj) → (A → Dk) e Cn(X)ponieważ także j<k więc zgodnie z założeniem indukcyjnym:
2.6) (A → Dj) e Cn(X)
Stosując znów syntaktyczne twierdzenie o odrywaniu do (2.5) i (2.6) otrzymujemy
2.7) (A → Dk) e 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) e Cn(X)
a także wobec faktu, że Dn = B
(A → B) e Cn(X)
Dygresja: powyższe twierdzenie formuułuje się w postacji równoważności [jako, że da się ono odwrócić]:
B e Cn(X u {A}) wtw (A → B) e Cn(X)
Dla dowodu zależności (←) zakładamy, że (A → B) e Cn(X)
Musimy pokazać, że B e Cn(X u {A}).
Wobec monotoniczności operacji Cn mamy też:
(1) (A → B) e Cn(X u {A}) [bo X _c X u {A}]z drugiej strony:
(2) A e Cn(X u {A}) [wobec zwrotności operacji Cn]
Stosując syntaktyczne twierdzenie o odrywaniu, otrzymujemy:
(3) B e Cn(X u {A}),co kończy dowód.
Wniosek: Dla dowolnych formuł A1, A2, …, An oraz B zachodzi następująca zaleznośc:
Jeżeli B e Cn({A1, A2,..., An}, to A1 → [A2 → (… → (An → B)...)] e Cn(O) [O zbiór pusty]
Przykład:
T11.
p → ((p → q) → q).
A1 → (A2 → B)
Zgodnie z twierdzeniem o dedukcji wprost:
p → ((p → q) → q) e Cn(O)
o ile:
q e Cn({p, p → q}).
1. p [zał.]
2. p → q [zał.]
3. q [RO: 1,2]
Przykład 2:
T12. Sylogizm hipotetyczny:
(p → q) → ((q → r) → (p → r)).
A1 → (A2 → (A3 → B))
(p → q) → ((q → r) → (p → r)) e Cn(O).
r e Cn({p → q, q → r, p}).
1. p → q zał.
2. q → r zał
3. p zał.
4. q RO: 1,3
5. r RO: 1,4
...
jelonka72