1105140233

14

ROZDZIALI. RACHUNEK ZDAŃ

Twierdzenie 1.5 Następujące dwa zdania są równoważne

1.

2.    rodzina zdań ipi,..., ip_n, jest sprzeczna, czyli nie istnieje waluacja it taka,

że n(<pi) = ... = n(p_n) = n(~np) = 1

Dowód. (1) —» (2). Załóżmy, że {y?i,... ,(p_n} \= ip. Rozważmy dowolną waluację 7r. Jeśli dla wszystkich i = 1,.. . n mamy n(<pi) = 1, to z założenia wynika, że 7r(^) = t a więc ir(-np) = 0.

(2) —> (1). Załóżmy, że 7r jest taką waluacją, że Tt(<pi) = ... 7r(</?_n) = 1. Wtedy 7r(—>-0) = 0, więc ir(ip) = 1.    □

Dowody Wprost

Najprostsze dowody twierdzeń, zwane dowodami wprost, polegają na wywnioskowaniu tezy twierdzenia z jego założeń.

Przykład 1.4 Rozważmy dowód następującego prostego twierdzenia o liczbach naturalnych:

“jeśli liczby nim są parzyste, to ich suma n + m jest parzysta

(czyli: “suma dwóch liczb parzystych jest parzysta”). Założenie tego twierdzenie jest koniunkcją dwóch zdań: “n jest liczbą parzystą” oraz “m jest liczbą parzystą”. Załóżmy zatem, że oba te zdania są prawdziwe. Istnieją wtedy liczby a oraz b takie, że n — 2a oraz m = 2b. Lecz wtedy n + m = 2a + 2b = 2 (a + b), zatem teza jest prawdziwa.

Jest to typowy przykład rozumowanie “wprost.

Dowody Nie Wprost

Dowody nie wprost polegają na wykorzystaniu reguły

Zaczynają się one od założenia, że teza jest fałszywa i pokazaniu, że z tego wynika fałszywość założenia.

Przykład 1.5 Wykażemy prawdziwość następującego zdania o liczbach rzeczywistych:

“jeśli średnia arytmetyczna liczb x, y jest większa od 1, to co najmniej jedna z tych liczb jest większa od 1 ”.

Twierdzenie to możemy zapisać następująco:

(^±i^>i)^_((a;^>i)^v(_!/^>i)).

Załóżmy, że teza twierdzenia jest fałszywa, czyli, że prawdziwe jest zdanie ~<((x > 1) V (y > 1)). Z prawa de Morgana wynika, że prawdziwa jest wówczas koniunkcją (-i(a: > 1)) A (-i(y > 1)), czyli, że prawdziwe jest zdanie (x < 1) A (y < 1). Lecz wtedy x + y < 2, zatem < 1. Pokazaliśmy więc, że zaprzeczenie tezy implikuje zaprzeczenie założenia. Zatem twierdzenie zostało udowodnione.