1.2. Reguły tworzenia dowodu
8 stycznia 2011
Wprowadzimy obecnie pewną terminologię, z której będziemy korzystać przy formułowaniu reguł tworzenia dowodów założeniowych. Wyrażenia F1, F2, …, Fn-1 występujące w wyrażeniu:
(F) F1 → {F2 → [F3 → … → (Fn-1 → Fn) … ]}
nazywać będziemy poprzednikami Fn.
Dlaczego F1, F2, …, Fn-1 są poprzednikami Fn. Z budowy wyrażenia F można wnioskować, że równoważnym mu wyrażeniem jest F’ o postaci:
(F’) (F1 ˄ F2 ˄ … ˄ Fn-1) → Fn
W tym wyrażeniu Fn jest wyraźnie następnikiem i wnioskiem swoich poprzedników. Jeżeli F przedstawimy w postaci normalnej, to ma ono postać:
~ F1 ˅ ~ F2 ˅ … ˅ ~ Fn ˅ Fn ,
a postacią normalną wyrażenia F’ jest
~ F1 ˅ ~ F2 ˅ … ˅ ~ Fn-1 ˅ Fn,
czyli obie formy są równoważne.
Na przykład elementy zbioru:
{p → q, q → r, p}
są poprzednikami wyrażenia
(p → q) → [(q → r) → (p → r)].
Jeżeli F1, F2, …, Fi są kolejnymi poprzednikami wyrażenia (F), to pozostałą część wyrażenia (F), a mianowicie wyrażenie:
Fi+1 → [… → (Fn-1 → Fn)],
będziemy nazywać następnikiem wyrażenia F odpowiadającym tym poprzednikom.
Na przykład w wyrażeniu:
(p → q) → [(q → r) → (p → r)]
poniższe
[(q → r) → (p → r)]
jest następnikiem odpowiadającym poprzednikowi (p → q), wyrażenie (p → r) jest następnikiem odpowiadającym poprzednikom (p → q) i (q → r), wyrażenie r jest następnikiem odpowiadającym poprzedni-kom: (p → q), (q → r), p.
Założeniowy dowód reguły stwierdzającej niezawodność danego schematu logicznego zaczynamy od wypisania założeń dowodu, którymi są przesłanki tego schematu oraz poprzedniki wniosku. Z tych założeń wyprowadzamy nowe wiersze według reguł dołączania nowych wierszy do dowodu (pierwotnych) lub uprzednio udowodnionych.
Możemy też do dowodu dołączyć jako nowe wiersze twierdzenia uprzednio udowodnione. Jest to opis założeniowego dowodu wprost (z.d.w.). Z.d.w. jest zakończony, gdy otrzymamy następnik wniosku odpowiadający tym poprzednikom wniosku, które są założeniami dowodu.
Przykładem jest dowód reguły sylogizmu warunkowego
p → q
q → r
p → r
W tym schemacie (p → q) i (q → r) są przesłankami, a (p → q), (q → r) i p stanowią poprzedniki wniosku r.
Dowód.
(1.) p → q
(2.) q → r {założenia}
(3.) p
(4.) q (RO: 1, 3)
r (RO: 2, 4).
Uwaga. W dowodzie ostatniego wiersza nie numerujemy, zaznaczając w ten sposób, że dowód jest zakończony.
Założeniowy dowód twierdzenia zaczynamy od wypisania założeń twierdzenia, którymi są jego poprzedniki. Do dowodu dołączamy nowe wiersze według reguł dołączania nowych wierszy do dowodu (pierwotnych lub uprzednio udowodnionych) lub twierdzenia uprzednio udowodnione. Opisane wyżej postępowanie nazywamy założeniowym dowodem wprost. Dowód taki jest zakończony, gdy otrzymamy następnik tego twierdzenia odpowiadający tym jego poprzednikom, które występują jako założenia w dowodzie tego twierdzenia.
Założeniowy dowód wprost prawa (p → q) → [(q → r)→(p → r) pokrywa się z podanym powyżej dowodem reguły sylogizmu warunkowego.
Założeniowy dowód wprost jakiegoś twierdzenia odróżniamy od zwykłego dowodu wprost.
Zwykły dowód wprost jakiegoś twierdzenia rozpoczynamy od twierdzeń uprzednio udowodnionych. Z tych twierdzeń za pomocą reguł dołączenia nowych wierszy do dowodu wyprowadzamy – jako twierdzenie z nich wynikające – dowodzone twierdzenie.
W zwykłym dowodzie wprost każdy wiersz dowodu jest twierdzeniem (tezą), natomiast wiersze założeniowego dowodu, w szczególności założenia dowodu, nie muszą i często nie są tezami.
Przykładem zwykłego dowodu wprost będzie dowód prawa:
(p ˄ q) ≡ q ˄ p
Dowód. 1.) (p ˄ q) → (q ˄ p) {T 1}
2.) (q ˄ p) → (p ˄ q) {T 2}
(p ˄ q) ≡ (q ˄ p) {DE: 1, 2}
Wiersze 1.) i 2.) są tutaj twierdzeniami uprzednio udowodnionymi.
Założeniowy dowód nie wprost reguły stwierdzającej niezawodność danego schematu logicznego rozpoczynamy od wypisania założeń dowodu. Są nimi przesłanki tego schematu oraz poprzedniki wniosku. Wyrażenie sprzeczne z odpowiadającym mu następnikiem tego wniosku wypisujemy jako założenie dowodu nie wprost (z.d.n.). Przez wyrażenie sprzeczne rozumiemy tu jakieś wyrażenie F i jego negację ~ F. Wyrażenie dowodu nie wprost wypisujemy więc bądź poprzedzając dany następnik znakiem negacji bądź skreślając początkowy znak negacji w następniku o postaci ~ F. Do dowodu dołączamy nowe wiersze. Według reguł dołączania nowych wierszy do dowodu (pierwotnych lub uprzednio udowodnionych) lub twierdzenia uprzednio udowodnione. Założeniowy dowód nie wprost jest zakończony, gdy otrzymamy w nim dwa wiersze sprzeczne.
Tak samo zbudowany jest założeniowy dowód nie wprost jakiegoś twierdzenia, z tą jedynie różnicą, że założeniami dowodu są poprzedniki tego twierdzenia.
Przykłady założeniowych dowodów nie wprost:
~ p → q
~ q → p
Dowód. (1.) ~ p → q {zał.}
(2.) ~ q
(3.) ~ p {z.d.n}
(4.) q {RO: 1, 3}
Sprzeczność {2, 4}
p → q
~ q → ~ p
Dowód. (1.) ~ p → q {zał.}
(2.) ~ q
(3.) p {z.d.n}
(4.) q {RO: 1, 3}
Sprzeczność {2, 4}
Założenie dowodu nie wprost „p” powstaje tutaj z następnika wniosku „~ p” przez skreślenie w nim znaku negacji.
Uwaga. Przy zapisywaniu dowodów będziemy używać skrótów zał. zamiast „założenie”, z.d.n. zamiast „założenie dowodu nie wprost”, sprz. zamiast „sprzeczność”.
Zwykły dowód nie wprost jakiegoś twierdzenia tym tylko różni się od założeniowego dowodu nie wprost, że nie występują w nim założenia, a tylko założenie dowodu nie wprost. Założeniem dowodu nie wprost jest w takim dowodzie wyrażenie sprzeczne z dowodzonym twierdzeniem.
Oto przykład zwykłego dowodu nie wprost:
~ [(p → q) ˄ (p ˄ ~ q)]
Dowód. (1.) (p → q) ˄ (p ˄ ~ q) {z.d.n}
(2.) (p → q) { OK.:1}
(3.) (p ˄ ~ q)
(4.) p {OK.: 3}
(5.) ~ q
(6.) q {RO: 2, 4}
Sprz. {5, 6}
Zakończenie założeniowego lub zwykłego dowodu nie wprost zaznaczamy pisząc na końcu „sprz.” i podając po prawej stronie numery dwóch wierszy sprzecznych.
Uwaga. Każdy założeniowy dowód wprost reguły lub twierdzenia można przekształcić na założeniowy dowód nie wprost, wypisując po założeniach wyrażenie sprzeczne z następnikiem wniosku lub następnikiem dowodzonego twierdzenia (odpowiadającym tym poprzednikom, które są założeniami tego dowodu) jako założenie dowodu nie wprost.
Podobnie każdy zwykły dowód wprost można przekształcić na zwykły dowód nie wprost umieszczając na początku dowodu wyrażenie sprzeczne z dowodzonym twierdzeniem, jako założenie dowodu nie wprost.