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. Wprowadźmy oznaczenie:

S

n

= 1 + 3 + 5 + . . . + (2n − 1).

Mamy: S

1

= 1, S

2

= 1 + 3 = 4, S

3

= 1 + 3 + 5 = 9, S

4

= 16,

S

5

= 25, S

6

= 36.

Widzimy, że powinno być S

n

= n

2

. Czy można to jakoś uzasad-

nić?

2

Trzeba się przyjrzeć, w jaki sposób otrzymujemy kolejne S

n

. Na

przykład, jeśli mamy już obliczone

S

6

= 1 + 3 + 5 + 7 + 9 + 11 = 36,

to

S

7

= 1 + 3 + 5 + 7 + 9 + 11 + 13

nie będziemy liczyli od początku, tylko wykorzystamy zależność

S

7

= S

6

+ 13 = 36 + 13 = 49.

Podobnie

S

8

= S

7

+ 15 = 49 + 15 = 64

i tak dalej. Zwróćmy uwagę na to, co należy dodać do S

n

, żeby

otrzymać S

n+1

. Jeśli S

n

= n

2

, to

S

n+1

= S

n

+ (2

· (n + 1) − 1) = n

2

+ 2n + 1 = (n + 1)

2

.

3

Zadanie. Dowieść, że dla dowolnej liczby naturalnej n > 1

1

· 2 + 2 · 3 + 3 · 4 + . . . + n · (n + 1) =

n · (n + 1) · (n + 2)

3

.

Rozwiązanie.

I. Baza indukcji.

Dla n = 1 równość jest oczywista:

1

· 2 =

1

· 2 · 3

3

.

II. Krok indukcyjny.

Niech k będzie dowolną liczbą naturalną. Załóżmy, że dana w

zadaniu równość zachodzi dla n = k:

1

· 2 + . . . + k · (k + 1) =

k · (k + 1) · (k + 2)

3

.

4

Wówczas dla n = k + 1 mamy:

1

·2+. . .+k·(k+1)+(k+1)·(k+2) =

k · (k + 1) · (k + 2)

3

+(k+1)·(k+2) =

= (k + 1) · (k + 2) · (

k

3

+ 1) =

(k + 1) · (k + 2) · (k + 3)

3

,

czyli dla n = k + 1 równość jest spełniona.

Na mocy zasady indukcji matematycznej równość

1

· 2 + 2 · 3 + . . . + n · (n + 1) =

n · (n + 1) · (n + 2)

3

zachodzi dla dowolnego naturalnego n.

5

Zadanie. Dowieść, że dla dowolnego n ≥ 0 liczba 2

2n+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∈N

1

(T (n) ⇒ T (n + 1))) ⇒ ∀

n∈N

1

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 = p

1

· . . . · p

i

,

l = q

1

· . . . · q

j

, zatem n = k · l też, oczywiście można tak przedsta-

wić: n = p

1

·. . .·p

i

·q

1

·. . .·q

j

, 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 ∈ N

1

: 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) ∈ R

2

: 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 ∧ x6∈B).

Oczywiście (x6∈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 Y 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 ∈ N

1

: n | 12} ∩ {n ∈ N

1

: n | 18} = {n ∈ N

1

: 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],

N

1

⊂ 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 2

X

, na przykład:

jeśli X = {a, b}, to 2

X

=

{∅, {a}, {b}, {a, b}},

jeśli X = {1, 2, 3}, to

2

X

=

{∅, {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 2

X

ma

2

n

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

0

=

X \ A. Dla każdego elementu x ∈ X prawdziwe jest zdanie

x ∈ A

0

⇔∼ (x ∈ A).

Zachodzą następujące zależności:

A ∩ A

0

= ∅, A ∪ A

0

= X,

(A

0

)

0

= A,

∅

0

= X,

X

0

= ∅.

21

Odnotujmy prawa de Morgana dla zbiorów:

(A ∪ B)

0

= A

0

∩ B

0

,

(A ∩ B)

0

= A

0

∪ B

0

.

Podobne zależności zachodzą dla większej liczby zbiorów, na

przykład:

(A ∪ B ∪ C)

0

= A

0

∩ B

0

∩ C

0

,

(A ∩ B ∩ C ∩ D)

0

= A

0

∪ B

0

∪ C

0

∪ D

0

.

22