Metody dowodzenia twierdzeń
Metoda dowodu  nie wprost jest oparta na tautologii
(p Ò! q) Ô! (<" q Ò!<" p).
Metoda dowodu  przez sprzeczność jest oparta na tautologii
(p Ò! q) Ô!<" (p'" <" q).
1
Metoda indukcji matematycznej
Przykład. Obliczyć 1 + 3 + 5 + . . . + (2n - 1), gdzie n jest liczbą
naturalnÄ….
Dyskusja. Wprowadz
my oznaczenie:
Sn = 1 + 3 + 5 + . . . + (2n - 1).
Mamy: S1 = 1, S2 = 1 + 3 = 4, S3 = 1 + 3 + 5 = 9, S4 = 16,
S5 = 25, S6 = 36.
Widzimy, że powinno być Sn = n2. Czy można to jakoś uzasad-
nić?
2
Trzeba się przyjrzeć, w jaki sposób otrzymujemy kolejne Sn. Na
przykład, jeśli mamy już obliczone
S6 = 1 + 3 + 5 + 7 + 9 + 11 = 36,
to
S7 = 1 + 3 + 5 + 7 + 9 + 11 + 13
nie będziemy liczyli od początku, tylko wykorzystamy zależność
S7 = S6 + 13 = 36 + 13 = 49.
Podobnie
S8 = S7 + 15 = 49 + 15 = 64
i tak dalej. Zwróćmy uwagę na to, co należy dodać do Sn, żeby
otrzymać Sn+1. Jeśli Sn = n2, to
Sn+1 = Sn + (2 · (n + 1) - 1) = n2 + 2n + 1 = (n + 1)2.
3
Zadanie. Dowieść, że dla dowolnej liczby naturalnej n 1
n · (n + 1) · (n + 2)
1 · 2 + 2 · 3 + 3 · 4 + . . . + n · (n + 1) = .
3
RozwiÄ…zanie.
I. Baza indukcji.
Dla n = 1 równość jest oczywista:
1 · 2 · 3
1 · 2 = .
3
II. Krok indukcyjny.
Niech k będzie dowolną liczbą naturalną. Załóżmy, że dana w
zadaniu równość zachodzi dla n = k:
k · (k + 1) · (k + 2)
1 · 2 + . . . + k · (k + 1) = .
3
4
Wówczas dla n = k + 1 mamy:
k · (k + 1) · (k + 2)
1·2+. . .+k·(k+1)+(k+1)·(k+2) = +(k+1)·(k+2) =
3
k (k + 1) · (k + 2) · (k + 3)
= (k + 1) · (k + 2) · ( + 1) = ,
3 3
czyli dla n = k + 1 równość jest spełniona.
Na mocy zasady indukcji matematycznej równość
n · (n + 1) · (n + 2)
1 · 2 + 2 · 3 + . . . + n · (n + 1) =
3
zachodzi dla dowolnego naturalnego n.
5
Zadanie. Dowieść, że dla dowolnego n e" 0 liczba 22n+1 + 3n + 7
jest podzielna przez 9.
Zasada indukcji:
(T (0) '" "n"N (T (n) Ò! T (n + 1))) Ò! "n"N T (n)
(T (1) '" "n"N1 (T (n) Ò! T (n + 1))) Ò! "n"N1 T (n)
6
Dowieść, że dowolną liczbę naturalną większą od 1 można przed-
stawić w postaci iloczynu liczb pierwszych. (Jeśli n jest liczbą
pierwszą, to iloczyn ten składa się tylko z jednego czynnika.)
RozwiÄ…zanie.
Liczba n = 2 jest liczbÄ… pierwszÄ…, czyli iloczynem jednej liczby
pierwszej  samej siebie.
Niech n będzie dowolną liczbą naturalną większą od 2. Załóżmy,
że każdą liczbę naturalną mniejszą od n można przedstawić w
postaci iloczynu liczb pierwszych. Pokażemy, że n też można
przedstawić w postaci iloczynu liczb pierwszych.
7
Jeśli n jest liczbą pierwszą, to teza dla n zachodzi. Jeśli n jest licz-
bą złożoną, to można ją przedstawić w postaci iloczynu dwóch
liczb od niej mniejszych: n = k · l, k, l < n. Na mocy zaÅ‚ożenia
zarówno k, jak i l, jest iloczynem liczb pierwszych: k = p1 · . . . · pi,
l = q1 · . . . · qj, zatem n = k · l też, oczywiÅ›cie można tak przedsta-
wić: n = p1·. . .·pi·q1·. . .·qj, co koÅ„czy dowód kroku indukcyjnego.
Schemat powyższego dowodu:
I) Baza: T (2).
II) Krok: T (2) '" . . . '" T (n - 1) Ò! T (n) dla każdego n > 2.
8
Sposoby określania zbiorów
1) Zbiór wszystkich elementów postaci f(t), gdzie t przebiega
zbiór T :
{f(t); t " T }.
2) Zbiór wszystkich elementów x zbioru X spełniających warunek
Õ(x):
{x " X : Õ(x)}.
3) Zbiór skończony możemy określić przez wypisanie jego ele-
mentów, np.
{n " N1 : n | 6} = {1, 2, 3, 6}.
9
" Zbiór liczb parzystych możemy określić na dwa sposoby:
{2k; k " Z} = {n " Z : 2 | n}.
" Prostą o równaniu y = ax + b możemy określić jako zbiór
punktów o współrzędnych (x, ax + b), gdzie x " R:
{(x, ax + b); x " R}
lub jako zbiór tych punktów o współrzędnych (x, y), które
spełniają warunek y = ax + b:
{(x, y) " R2 : y = ax + b}.
10
Ważny przykład zbiorów stanowią przedziały osi liczbowej.
(a, b)={x " R : x > a '" x < b},
[a, b)={x " R : x a '" x < b},
(-", a)={x " R : x < a}.
11
Rozważmy dowolne dwa zbiory A i B.
Suma A *" B składa się z wszystkich elementów, które należą do
zbioru A lub do zbioru B:
(x " A *" B) Ô! (x " A (" x " B).
Część wspólna (przekrój) A )" B składa się z wszystkich elemen-
tów, które należą jednocześnie do zbioru A i do zbioru B:
(x " A )" B) Ô! (x " A '" x " B).
Różnica A \ B składa się z wszystkich elementów, które należą
do zbioru A, ale nie należą do zbioru B:
(x " A \ B) Ô! (x " A '" x "B).
OczywiÅ›cie (x "A) Ô!<" (x " A).
12
Różnica symetryczna A ÷ B skÅ‚ada siÄ™ z wszystkich elementów,
które należą do zbioru A, a nie należą do B, oraz tych, które
należą do B, a nie należą do A:
(x " A ÷ B) Ô! (x " A x " B).
Zauważmy, że A ÷ B = (A \ B) *" (B \ A).
13
Przykłady:
[0, 2) *" [1, 3) = [0, 3), [0, 2) )" [1, 3) = [1, 2),
[0, 2) \ [1, 3) = [0, 1), [0, 2) *" {2} = [0, 2],
(-1, +") )" (-", 1) = (-1, 1),
[-1, 1] \ {-1, 1} = (-1, 1),
[-1, 1] \ {0} = [-1, 0) *" (0, 1].
Inny przykład:
{n " N1 : n | 12} )" {n " N1 : n | 18} = {n " N1 : n | 6}.
14
Własności działań na zbiorach
Dla dowolnych zbiorów A, B i C zachodzą następujące równości:
1) (A *" B) )" C = (A )" C) *" (B )" C),
2) (A )" B) *" C = (A *" C) )" (B *" C),
3) (A *" B) \ C = (A \ C) *" (B \ C),
4) (A )" B) \ C = (A \ C) )" (B \ C),
15
5) (A \ B) )" C = (A )" C) \ B,
6) (A \ B) *" C = (A *" C) \ (B \ C),
7) (A \ B) \ C = A \ (B *" C),
8) A \ (B \ C) = (A \ B) *" (A )" C).
Takich równości można dowodzić dwiema metodami  rachunku
zdań (bardziej formalna) i diagramów Venne a (bardziej obrazo-
wa).
16
Inkluzja zbiorów
Mówimy, że zbiór A jest zawarty w zbiorze B, co zapisujemy
A ‚" B, jeÅ›li wszystkie elementy zbioru A należą do zbioru B,
czyli dla dowolnego elementu x prawdziwe jest zdanie
(x " A) Ò! (x " B).
Przykłady:
{0} ‚" [0, 1) ‚" (-1, 1) ‚" [-1, 1] ‚" (-", 1],
N1 ‚" N ‚" Z ‚" Q ‚" R.
17
Własności:
1) Jeżeli A ‚" B i B ‚" A, to A = B.
2) Jeżeli A ‚" B i B ‚" C, to A ‚" C.
3) Jeżeli A ‚" C i B ‚" C, to A *" B ‚" C.
4) Jeżeli A ‚" B i A ‚" C, to A ‚" B )" C.
Zadanie. Wykaż, że dla dowolnych zbiorów A, B i C zachodzą
następujące równoważności:
A ‚" B Ô! A )" B = A Ô! A *" B = B.
18
Zbiór pusty to zbiór posiadający 0 elementów, oznaczamy go
symbolem ".
Zbiór pusty jest zawarty w każdym zbiorze:
" ‚" A.
Jest tylko jeden zbiór pusty:
("1 ‚" "2) '" ("2 ‚" "1) Ò! ("1 = "2).
19
Algebra podzbiorów danego zbioru
Przez X oznaczmy dowolny zbiór. Zbiór podzbiorów zbioru X
oznaczamy symbolem 2X, na przykład:
jeśli X = {a, b}, to 2X = {", {a}, {b}, {a, b}},
jeśli X = {1, 2, 3}, to
2X = {", {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Twierdzenie. Jeśli zbiór X ma n elementów, to zbiór 2X ma
2n elementów.
Jeśli mamy ustalony zbiór X i rozważamy tylko jego podzbiory,
to zbiór X nazywamy przestrzenią lub uniwersum.
20
Dopełnieniem zbioru A (w przestrzeni X) nazywamy zbiór A =
X \ A. Dla każdego elementu x " X prawdziwe jest zdanie
x " A Ô!<" (x " A).
Zachodzą następujące zależności:
A )" A = ", A *" A = X, (A ) = A,
" = X, X = ".
21
Odnotujmy prawa de Morgana dla zbiorów:
(A *" B) = A )" B , (A )" B) = A *" B .
Podobne zależności zachodzą dla większej liczby zbiorów, na
przykład:
(A *" B *" C) = A )" B )" C ,
(A )" B )" C )" D) = A *" B *" C *" D .
22