W tej części wykładu omówimy metodę badania prawdziwości formuł zwaną "nie wprost". Metoda ta polega na przyjęciu hipotezy odwrotnej do tej, którą chcemy udowodnić, i wydedukowaniu stąd, albo zaprzeczenia jednego z założeń, albo zaprzeczenia dowodzonej tezy. Dowody oparte o tę zasadę noszą nazwę apagogicznych, a inaczej mówi się o nich, że są to dowody przez sprowadzanie do niedorzeczności. W podanych niżej przykładach dowody będą oparte na tej zasadzie.

Przykład 7.5.1

Rozważmy formułę (( α ∧ β ) → γ ) → ( α → ( β → γ )), zwaną prawem eksportacji.

Chcemy udowodnić, że jest to prawo rachunku zdań, czyli że niezależnie od wartości zdań składowych całe wyrażenie ma zawsze wartość 1.

Przypuśćmy, że tak nie jest, tzn. przypuśćmy, że są takie wartości zdań składowych, że w((( α ∧ β ) → γ ) → ( α → ( β → γ ))) = 0. Ponieważ implikacja tylko w jednym przypadku ma wartość 0 zatem musiałoby być

1. w((( α ∧ β ) → γ )) = 1 oraz

2. w( α → ( β → γ )) = 0

Ponownie, korzystamy z własności implikacji i z (2) otrzymując

3. w( α )=1
4. w( β → γ )= 0

Z (4), wynika że w( β ) = 1 oraz w( γ )= 0.

Stąd na mocy (3) mamy w( α ∧ β ) =1 , a zatem w(( α ∧ β ) → γ )=0, co jest sprzeczne z (1).

Zatem nasze przypuszczenie początkowe nie było prawdziwe, czyli zawsze musi być w((( α ∧ β ) → γ ) → ( α → ( β → γ ))) = 1. ♦

Schemat postępowania jaki zastosowaliśmy w przykładzie 7.5.1, polegał na tym, że z przypuszczenia fałszywości zdania dowodzonego wywnioskowaliśmy własność (1), a w chwilę później, jej zaprzeczenie. Ponieważ w żadnej interpretacji nie może być równocześnie prawdziwe zdanie i jego zaprzeczenie więc nie istnieje interpretacja, w której prawo eksportacji jest fałszywe.

Uproszczony zapis rozumowania "nie wprost" zastosowanego do prawa eksportacji omawianego w przykładzie 7.5.1 przedstawiliśmy na rysunku 7.5.1. Kolejne linie poziome oddzielają kolejne kroki rozumowania. W wyniku pierwszych czterech kroków uzyskaliśmy informację o wartościach formuł α, β i γ. Te pierwsze etapy rozumowania charakteryzują się tym, że przechodzimy "w głąb" formuły. W piątym kroku zebraliśmy uzyskane informacje i wpisaliśmy je w odpowiednie miejsca w poprzedniku rozważanej formuły. Teraz rozpoczyna się proces odwrotny: od wartości prostych formuł do wartości formuł złożonych. Doprowadza to do kroku 7, w którym dostrzegamy sprzeczność uzyskanych informacji: w tej samej kolumnie pionowej mamy równocześnie 0 i 1.

Rys. 7.5.1 Przykład rozumowania "nie wprost".

Ten sam schemat postępowania "nie wprost" zastosujemy też w następnych przykładach.

Przykład 7.5.2

Jeżeli funkcja g : Y → X jest funkcją odwrotną do funkcji f: X → Y, to obie funkcje f i g są różnowartościowe. Przypominam, że funkcję g: Y → X nazywamy odwrotną do funkcji f : X → Y, jeśli Y = f(X) i X = g(Y) oraz g(f(x)) = x dla wszystkich x ∈ X.

Przypuśćmy, że f nie jest funkcją różnowartościową. Niech x₁ ≠ x₂ oraz f(x₁)=f(x₂). Ponieważ g jest funkcją, to dla równych argumentów przyjmuje takie same wartości, czyli g(f(x₁)) = g(f(x₂)). Stąd, na mocy definicji funkcji odwrotnej, mamy x₁= g(f(x₁)) = g(f(x₂)) = x₂, co jest sprzeczne z wcześniej przyjętym założeniem, że x₁ ≠ x₂.

Gdyby g nie była funkcją różnowartościową, zatem musiałyby istnieć w zbiorze Y dwa różne elementy y₁, y₂, takie że g(y₁) = g(y₂). Wówczas mamy

(*)      f (g(y₁)) = f(g(y₂)).

Ponieważ g jest funkcją odwrotną do f, zatem Y = f(X), czyli y₁, y₂ ∈ f(X). Stąd istnieją takie elementy x₁, x₂ w X, że f(x₁) = y₁ oraz f(x₂) = y₂. Wstawiając do równości (*) otrzymujemy

f(g(f(x₁)) ) = f(g(f(x₂)) ). Korzystając z własności funkcji odwrotnej mamy f(x₁) = f(x₂), a zatem y₁ = y₂. Sprzeczność. Zatem, jeśli tylko y₁ ≠ y₂, to g(y₁) ≠ g(y₂). Czyli funkcja g też jest różnowartościowa. ♦

Przykład 7.5.3

W tym przykładzie udowodnimy, że √ 2 jest liczbą niewymierną. Chcemy pokazać, że jeśli x² = 2, to x nie może być liczbą wymierną. Przypuśćmy przeciwnie, że

1. x² = 2 oraz
2. x jest liczbą wymierną.

Na mocy (2) x = n/m dla pewnych liczb całkowitych n, m, gdzie m ≠ 0. Możemy założyć, że n i m nie mają wspólnych dzielników innych niż 1( bo w przeciwnym przypadku wystarczy podzielić n i m przez ich największy wspólny dzielnik).

Mamy n²/m² = 2, czyli n² = 2m². Wynika stąd, że n² jest liczbą parzystą. W konsekwencji n też musi być liczbą parzystą (bo gdyby n było nieparzyste, np. n=2k+1,to n²= 4k²+ 4k+1 byłoby też liczbą nieparzystą). Niech n = 2k . Wtedy mamy n² = 4k² = 2m². Stąd 2k² = m², tzn. m też jest liczbą parzystą. Sprzeczność z założeniem, że n i m nie mają wspólnych dzielników. Zatem √ 2 jest liczbą niewymierną. ♦

Powyższy przykład dowodu apagogicznego (dowodu nie wprost) polegał na sprowadzeniu do sprzeczności.

Do dowodów apagogicznych zaliczają się też dowody oparte o prawa transpozycji: zamiast dowodzić implikacji ( α → β), dowodzi się zdania przeciwstawnego ( ¬ β → ¬ α).

Zadanie 7.5.1 Udowodnij, że formuła ((( α → β) → α) → α) jest tautologią rachunku zdań. Zastosuj w dowodzie metodę sprowadzania do niedorzeczności.

Rozwiązanie. Gdyby wartością formuły było 0, to w( α) = 0 oraz w(( α → β) → α)=1. Wstawiając jednak w miejsce α w formule (( α → β) → α) wartość 0, otrzymamy niezależnie od wartości β, w( α → β)= 1 oraz w(( α → β) → α)= 0, co jest sprzeczne z wcześniej otrzymanym wnioskiem.