1105140234

15

ROZDZIALI. RACHUNEK ZDAŃ

Dowody przez sprowadzenie do sprzeczności

Dowody przez sprowadzenie do sprzeczności są pewną odmianą dowodów nie wprost. Korzystają one z następującej reguły dowodzenia:

{(ifi a-4) -> x} 1= ip ->

Reguła ta jest poprawna, gdyż

{(<p A -i-0)    -L) = ^_l(<p A -i-0) V JL = -i(<£ A —>-0) = -«£> V 0 =    ^ -0.

Przykład 1.6 Zanalizujemy dobrze z pewnością znany czytelnikowi dowód niewy-mierności liczby \/2, czy// dowód zdania

„jeśli x² = 2 to x jest liczbą niewymierną

Zakładamy w nim, że

„x² = 2 i x jest liczbą wymierną”

i przedstawiamy liczbę x w postaci ułamka x = ^ takiego, ze NWD(n,m) = 1, gdzie NDW(n,m) oznacza największy wspólny dzielnik liczb n i m. Po podniesieniu obu stron do kwadratu otrzymujemy równość 2 = którą przekształcamy do postaci 2m² = n². Z otrzymanej równości wynika, że n jest liczbą parzystą, możemy ją więc przestawić w postaci n = 2k. Po podstawieniu otrzymujemy równość 2m² = (2k)², czyli 2m² = 4k². Z równości tej wynika, że m² = 2k², z czego wnioskujemy, że m jest liczbą parzystą. Zatem NWD(n, m) > 1.

Z założeń „x² = 2 i x jest liczbą wymierną” wywnioskowaliśmy, że „istnieją liczby n i m takie, że NWD(n, m) = 1 i NWD(n, m) > 1 Założenie „x² = 2 i x jest liczbą wymierną ” prowadzi więc do sprzeczności.

Dowody Przez Rozważenie Przypadków

Do dowodów niektórych twierdzeń skorzystać możemy z następującej postaci reguły rezolucji

{p -> 9,    -> 9} h ?•

Przykład 1.7 Pokażemy, że dla dowolnej liczb rzeczywistej x prawdziwa jest nierówność

x < |x|.

Jeśli x > D, to \x\ = x < x. Jeśli x < 0, to x < 0 < |rr|. Pokazaliśmy więc, że (x > 0 —> x < |x||) A (^-i(a: > 0) —> x < |x|),

co kończy dowód.

Przykład 1.8 Pokażemy, że dla dowolnych liczb rzeczywistych x oraz y prawdziwa jest nierówność

\x + y\ < |*| + \y\-