Matematyka dyskretna

WYKŁADY I ĆWICZENIA

Z MATEMATYKI DYSKRETNEJ

Informatyka WEiI PL

rok akad. 2012/2013

Małgorzata Murat

Rozdział 1

Elementy logiki matematycznej.

Logika jest dyscypliną naukową mającą bardzo długą historię. Jej początki sięgają Chin i starożyt-
nej Grecji. Pojawiła się w związku z rozwinięciem zdolności do konstruowania abstrakcyjnych pojęć
oraz prowadzenia rozumowań o charakterze systematycznym. Na przełomie XIX i XX wieku wraz z
dążeniem do dogłębnego zbadania podstaw matematyki jako samodzielna dziedzina powstała logika
matematyczna. Koncentruje się ona na analizowaniu zasad rozumowania oraz pojęć z nim związanych
z wykorzystaniem sformalizowanych oraz uściślonych metod i narzędzi matematyki. Nazwa logika ma-
tematyczna została użyta po raz pierwszy przez włoskiego matematyka Giuseppe Peano. Korzenie
logiki matematycznej tkwią w badaniach Gottfrieda Leibniza, ale jej burzliwy rozwój zaczął się w
pierwszej połowie XIX wieku w wyniku prac George’a Boole’a i Augusta De Morgana.

Dla informatyka znajomość logiki matematycznej może być ważna z następujących powodów:

1. Logika jest podstawą wszystkich języków programowania.

2. Systemy logiczne są odpowiednikami baz danych.

3. Logika dostarcza metod weryfikacji programów komputerowych.

4. Logika uczy myśleć jasno i precyzyjnie, dzięki czemu uczy szybciej rozwiązywać problemy i pisać

programy komputerowe.

5. Dzięki znajomości podstaw logiki lepiej można komunikować się z innymi, w szczególności można

szybciej porozumieć się z klientem lub pracodawcą i to bez niedomówień i niejasności.

1.1.

Rachunek zdań i tautologie.

Rachunek zdań jest działem logiki matematycznej, który zajmuje się badaniem związków między
zdaniami lub funkcjami zdaniowymi.

Definicja 1.1.1

Zdaniem nazywamy w logice wypowiedź orzekającą, której można przypisać jedną

z dwóch ocen: prawdę lub fałsz.

Prawdę i fałsz nazywamy wartościami logicznymi zdania.
Prawdę oznaczamy cyfrą 1, a fałsz cyfrą 0.

Na przykład zdanie: ”Jeśli dziś jest sobota, to jutro będzie niedziela” jest prawdziwe, a zdanie:

”2 jest liczbą nieparzystą” jest fałszywe. Natomiast ocena prawdziwości zdania: ”Matematyka jest
łatwa” zależy już od subiektywnego odczucia osoby je wypowiadającej. W dalszym ciągu będą nas
interesowały zdania pierwszego rodzaju. Wartość logiczną zdania będziemy oznaczać przez w(p). Jeśli
zdanie p jest fałszywe, to będziemy pisać w(p) = 0, a jeśli zdanie p jest prawdziwe, to w(p) = 1.

Z danych zdań możemy przy pomocy słów ”nie”, ”i”, ”lub”, ”jeśli ..., to ...”, ”wtedy i tylko wtedy,

gdy ...”, zwanych funktorami zdaniotwórczymi, tworzyć nowe zdania.

Funktory zdaniotwórcze oznaczamy w następujący sposób

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

”nie”

∼

funktor negacji

”lub”

∨

funktor alternatywy

”i”

∧

funktor koniunkcji

”jeśli ... to ...”

⇒

funktor implikacji

”wtedy i tylko wtedy, gdy ... ”

⇔

funktor równoważności

Przy pomocy wymienionych funktorów definiujemy następujące zdania.

Definicja 1.1.2

Negacją zdania p nazywamy zdanie oznaczane symbolem ∼ p, które jest prawdziwe,

gdy zdanie p jest fałszywe i jest fałszywe, gdy p jest prawdziwe.

Definicja 1.1.3

Alternatywą dwóch zdań p i q nazywamy zdanie oznaczane symbolem p ∨ q, które

jest fałszywe jeśli oba zdania p i q są fałszywe, a w pozostałych przypadkach jest prawdziwe.

Definicja 1.1.4

Koniunkcją dwóch zdań p i q nazywamy zdanie oznaczane symbolem p ∧ q, które

jest prawdziwe jeśli oba zdania p i q są prawdziwe, a w pozostałych przypadkach jest fałszywe.

Definicja 1.1.5

Implikacją dwóch zdań p i q nazywamy zdanie oznaczane symbolem p ⇒ q, które

jest fałszywe jeśli zdanie p jest prawdziwe, a zdanie q jest fałszywe, a w pozostałych przypadkach jest
prawdziwe. Zdanie p nazywamy poprzednikiem implikacji, a zdanie q następnikiem.

Definicja 1.1.6

Równoważnością dwóch zdań p i q nazywamy zdanie oznaczane symbolem p ⇔ q,

które jest prawdziwe jeśli oba zdania p i q mają tą samą wartość logiczną, a w pozostałych przypadkach
jest fałszywe.

Przy pomocy funktorów zdaniotwórczych, nawiasów i zdań logicznych możemy tworzyć zdania złożone.
Tablicę podającą wartości logiczne zdania złożonego w zależności od wartości zdań składowych nazywa
się matrycą logiczną. Na mocy przyjętych oznaczeń definicje funktorów możemy zapisać przy użyciu
następującej matrycy logicznej

w(p)

w(q)

w(∼ p)

w(p ∧ q)

w(p ∨ q)

w(p ⇒ q)

w(p ⇔ q)

Definicja 1.1.7

Zdanie złożone prawdziwe bez względu na wartości logiczne występujących w nim

zdań składowych nazywamy tautologią i oznaczamy T .

Zdanie złożone fałszywe bez względu na wartości logiczne występujących w nim zdań nazywamy

zdaniem sprzecznym i oznaczamy F .

Wprost z definicji wynika, że

∼ T ⇔ F

∼ F ⇔ T.

Zadania

Zadanie 1.1.1

Wykorzystując matrycę logiczną udowodnić następujcie prawa rachunku zdań

prawo podwójnego przeczenia

∼ (∼ p) ⇔ p,

(1.1)

prawa przemienności

(p ∧ q) ⇔ (q ∧ p),

(p ∨ q) ⇔ (q ∨ p),

(1.2)

prawa łączności

[(p ∧ q) ∧ r] ⇔ [p ∧ (q ∧ r)],

[(p ∨ q) ∨ r] ⇔ [p ∨ (q ∨ r)],

(1.3)

1.1. RACHUNEK ZDAŃ I TAUTOLOGIE.

prawo rozdzielności alternatywy względem koniunkcji

[r ∨ (p ∧ q)] ⇔ [(r ∨ p) ∧ (r ∨ q)],

(1.4)

prawo rozdzielności koniunkcji względem alternatywy

[r ∧ (p ∨ q)] ⇔ [(r ∧ p) ∨ (r ∧ q)],

(1.5)

f )

prawa identyczności

(p ∧ T ) ⇔ p,

(p ∧ F ) ⇔ F,

(p ∨ T ) ⇔ T,

(p ∨ F ) ⇔ p,

(1.6)

prawa idempotentności

(p ∧ p) ⇔ p,

(p ∨ p) ⇔ p,

(1.7)

prawa wyłączonego środka

(p∧ ∼ p) ⇔ F,

(p∨ ∼ p) ⇔ T,

(1.8)

prawa de Morgana

∼ (p ∧ q) ⇔ (∼ p∨ ∼ q),

∼ (p ∨ q) ⇔ (∼ p∧ ∼ q),

(1.9)

prawo przechodniości implikacji (prawo sylogizmu)

(p ⇒ q) ∧ (q ⇒ r)

⇒ (p ⇒ r),

(1.10)

prawo przechodniości równoważności

(p ⇔ q) ∧ (q ⇔ r)

⇒(p ⇔ r),

(1.11)

zaprzeczenie implikacji

∼ (p ⇒ q) ⇔ p∧ ∼ q

(1.12)

ł)

prawo kontrapozycji

(p ⇒ q) ⇔ (∼ q ⇒∼ p),

(1.13)

określenie implikacji za pomocą alternatywy i negacji

(p ⇒ q) ⇔ (∼ p ∨ q),

(1.14)

określenie implikacji za pomocą koniunkcji i negacji

(p ⇒ q) ⇔∼ (p∧ ∼ q),

(1.15)

określenie równoważności za pomocą alternatywy, koniunkcji i negacji

(p ⇔ q) ⇔

(∼ p∨q) ∧ (∼ q∨p)

(1.16)

określenie równoważności za pomocą koniunkcji i negacji

(p ⇔ q) ⇔

∼ (p∧ ∼ q)∧ ∼ (q∧ ∼ p)

(1.17)

określenie równoważności za pomocą koniunkcji i implikacji

(p ⇔ q) ⇔

(p ⇒ q) ∧ (q ⇒ p)

(1.18)

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

reductio ad absurdum

(p ⇒ q) ⇔ [(p∧ ∼ q) ⇒ f ],

(1.19)

Zadanie 1.1.2

Wśród niżej podanych zdań wskazać tautologie i zdania sprzeczne.

p ⇒ q ⇒ p

∼ p ⇒ q

⇒ p,

p ∨ q

⇔

∼ p ⇒ q

p ∧ q

⇔ p ⇒∼ q

(p ∧ q) ∨ q

⇒ (q ∨ p),

f )

(p ∨ q) ∧ p

⇒ (q ∧ p),

(p∧ ∼ q) ⇔ (∼ p ∨ q),

(p ⇒ q) ∨ (p ⇒ r)

⇒ (q ∨ r),

p ⇒ q ⇒ r

⇒

p ⇒ q

⇒ p ⇒ r

Zadanie 1.1.3

Sprawdzić, czy dla implikacji i równoważności dwóch zdań zachodzą prawa przemien-

ności i łączności.

Zadanie 1.1.4

Sprawdzić, czy zachodzi prawo rozdzielności implikacji względem

koniunkcji,

alternatywy.

Czy zachodzą prawa rozdzielności

koniunkcji,

alternatywy

względem implikacji?

Zadanie 1.1.5

Alternatywą wykluczającą dwóch zdań p i q nazywamy zdanie oznaczane symbo-

lem pXORq, które jest fałszywe jeśli oba zdania p i q mają tą samą wartość logiczną, a w pozostałych
przypadkach jest prawdziwe.

Pokazać, że negacją alternatywy wykluczającej jest równoważność.

Jaka jest wartość logiczna zdania pXORp, dla dowolnego zdania p?

Czy dla alternatywy wykluczającej zachodzą prawa przemienności, łączności, rozdzielności wzglę-
dem koniunkcji i alternatywy? Odpowiedź uzasadnij.

Określ alternatywę wykluczającą za pomocą negacji, koniunkcji i alternatywy.

Zadanie 1.1.6

Funktor zwany kreską Sheffera zdefiniowano następująco: p | q

⇔ ∼ p ∨ ∼ q.

Sporządź matrycę logiczną dla kreski Sheffera.

Jaka jest wartość logiczna zdania p |∼ p, dla dowolnego zdania p?

Czy dla kreski Sheffera zachodzi prawo rozdzielności względem koniunkcji? Odpowiedź uzasadnij.

Określ alternatywę za pomocą kreski Sheffera.

1.2. FUNKCJE ZDANIOWE I KWANTYFIKATORY

Określ kreskę Sheffera za pomocą koniunkcji.

Zadanie 1.1.7

Funktor zwany strzałką Peirce’a zdefiniowano następująco: p ⊥ q

⇔ ∼ p ∧ ∼ q.

Sporządź matrycę logiczną dla strzałki Peirce’a.

Jaka jest wartość logiczna zdania ∼ p ⊥ p, dla dowolnego zdania p?

Czy dla strzałki Peirce’a zachodzi prawo rozdzielności względem alternatywy? Odpowiedź uza-
sadnij.

Określ koniunkcję za pomocą strzałki Peirce’a.

Określ strzałkę Peirce’a za pomocą alternatywy.

1.2.

Funkcje zdaniowe i kwantyfikatory

Definicja 1.2.1

Funkcją zdaniową ϕ(x) jednej zmiennej nazywamy wyrażenie zawierające zmienną

x, które staje się zdaniem logicznym, gdy na miejsce x podstawimy element ze zbioru X.

Zbiór elementów x ∈ X, dla których ϕ(x) jest zdaniem logicznym nazywamy zakresem zmien-

ności lub dziedziną funkcji zdaniowej i oznaczamy D

lub D.

Przykład 1.2.2

Funkcja zdaniowa ”x jest liczbą parzystą”, ze zmienną x określoną na zbiorze liczb

naturalnych, dla x = 2 jest zdaniem prawdziwym, a dla x = 13 jest zdaniem fałszywym.

Przykład 1.2.3

Każde równanie oraz każda nierówność jest funkcją zdaniową.

Jeśli dla a ∈ D

zdanie ϕ(a) jest prawdziwe, to mówimy, że a spełnia funkcję zdaniową.

Definicja 1.2.4

Zbiór wszystkich a ∈ D

, które spełniają funkcję zdaniową nazywamy wykresem

funkcji zdaniowej i oznaczamy symbolem S(ϕ), tj.

S(ϕ) = {x ∈ D

: w(ϕ(x)) = 1}.

Definicja 1.2.5

Funkcję zdaniową nazywamy tożsamościową, jeżeli spełnia ją każdy element z jej

dziedziny, natomiast nazywamy ją sprzeczną, jeżeli nie spełnia jej żaden element z dziedziny.

Definicja 1.2.6

Dwie funkcje zdaniowe nazywamy równoważnymi, gdy mają wspólną dziedzinę i

gdy każdy element, który spełnia jedną z nich, spełnia także drugą i na odwrót.

Innymi słowy dwie funkcje zdaniowe ϕ(x) i ψ(x) o wspólnej dziedzinie X są równoważne, jeżeli mają
taki sam wykres, tzn. S(ϕ) = S(ψ).

Wyrażenie ”dla każdego x...” oznaczamy

i nazywamy kwantyfikatorem ogólnym, natomiast

wyrażenie ”istnieje takie x, że ...” oznaczamy

i nazywamy kwantyfikatorem szczegółowym.

Jeżeli dla każdego x ∈ D funkcja zdaniowa ϕ(x) o dziedzinie D jest zdaniem prawdziwym, to fakt

ten zapisujemy w następujący sposób

x∈D

ϕ(x)

i odczytujemy: ”dla każdego x jest ϕ(x)”.

Jeżeli w dziedzinie D istnieje co najmniej jeden element x, dla którego funkcja zdaniowa ϕ(x) jest

zdaniem prawdziwym, to piszemy

x∈D

ϕ(x)

i odczytujemy: ”istnieje taki x, że ϕ(x)”.

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

Kwantyfikator ogólny można uważać za uogólniony symbol koniunkcji, a kwantyfikator szczegółowy

za uogólniony symbol alternatywy. Ten fakt zauważymy łatwo, gdy A = {x

, x

, . . . , x

}. Wtedy

x∈A

ϕ(x) ⇔

ϕ(x

) ∧ ϕ(x

) ∧ · · · ∧ ϕ(x

)

x∈A

ϕ(x) ⇔

ϕ(x

) ∨ ϕ(x

) ∨ · · · ∨ ϕ(x

)

Wyrażenie następujące po kwantyfikatorze, objęte tym kwantyfikatorem, nazywa się zasięgiem kwan-
tyfikatora, zbiór A nazywa się zakresem kwantyfikatora.

Definicja 1.2.7

Funkcją zdaniową n zmiennych ϕ(x

, . . . , x

) nazywamy wyrażenie zawierające

zmienne x

, . . . , x

, które staje się zdaniem logicznym, gdy na miejsce każdej zmiennej x

, . . . , x

podstawimy elementy ze zbioru X.

Wykresem funkcji zdaniowej dwóch zmiennych ϕ(x, y) jest zbiór postaci

S(ϕ) = {(x, y) ∈ D

: w(ϕ(x, y)) = 1}.

W analogiczny sposób definiuje się wykres funkcji zdaniowej n zmiennych.

Dla funkcji zdaniowych wielu zmiennych możemy wprowadzić pojęcie zmiennych związanych i

zmiennych wolnych. Zmienna występująca pod znakiem kwantyfikatora nazywa się zmienną zwią-
zaną danym kwantyfikatorem. Natomiast zmienna, która nie jest związana żadnym kwantyfikatorem,
nazywa się zmienną wolną. Mianowicie w zdaniu

,...,x

ϕ(x

, . . . , x

, x

k+1

, . . . , x

)

zmienne x

, . . . , x

są związane, a zmienne x

k+1

, . . . , x

są wolne.

Niech p będzie zdaniem lub funkcją zdaniową, w której zmienna x jest zmienną wolną i niech ϕ(x)
będzie funkcja zdaniową.

Niech ϕ i ψ będą dwiema funkcjami zdaniowymi o tej samej dziedzinie D i niech A, B ⊆ D. Niech p
będzie dowolnym zdaniem logicznym.

PRAWA RACHUNKU KWANTYFIKATORÓW

x∈D

p ∧ ϕ(x)

⇔

p ∧

x∈D

ϕ(x)

(1.20)

x∈D

p ∨ ϕ(x)

⇔

p ∨

x∈D

ϕ(x)

(1.21)

x∈D

p ∨ ϕ(x)

⇔

p ∨

x∈D

ϕ(x)

(1.22)

x∈D

p ∧ ϕ(x)

⇔

p ∧

x∈D

ϕ(x)

(1.23)

x∈A

ϕ(x) ⇒

x∈A

ϕ(x),

(1.24)

x∈A

[ϕ(x) ∨ ψ(x)] ⇐⇒

x∈A

ϕ(x) ∨

x∈A

ψ(x),

(1.25)

x∈A

[ϕ(x) ∧ ψ(x)] =⇒

x∈A

ϕ(x) ∧

x∈A

ψ(x),

(1.26)

x∈A

[ϕ(x) ∧ ψ(x)] ⇐⇒

x∈A

ϕ(x) ∧

x∈A

ψ(x),

(1.27)

1.2. FUNKCJE ZDANIOWE I KWANTYFIKATORY

x∈A

[ϕ(x) ∨ ψ(x)] ⇐=

x∈A

ϕ(x) ∨

x∈A

ψ(x),

(1.28)

prawa de Morgana dla kwantyfikatorów

∼

x∈A

ϕ(x)

⇐⇒

x∈A

∼ ϕ(x)

(1.29)

∼

x∈A

ϕ(x)

⇐⇒

x∈A

∼ ϕ(x)

(1.30)

prawa przemienności kwantyfikatora ogólnego

x∈A

y∈B

ϕ(x, y) ⇐⇒

y∈B

x∈A

ϕ(x, y)

(1.31)

prawa przemienności kwantyfikatora szczegółowego

x∈A

y∈B

ϕ(x, y) ⇐⇒

y∈B

x∈A

ϕ(x, y)

(1.32)

przeniesienie kwantyfikatora egzystencjalnego za ogólny

x∈A

y∈B

ϕ(x, y) =⇒

y∈B

x∈A

ϕ(x, y)

(1.33)

Przykład 1.2.8

Rozważmy dwa zdania

p =

x∈R

x  0 ∧ x < 0

q =

x∈R

x  0 ∧

x∈R

x < 0.

Z własności zbioru R wynika, że w(p) = 0 oraz w(q) = 1. Implikacja q ⇒ p jest fałszywa. Zatem

przykład pokazuje, że implikacja (1.26) nie zachodzi w drugą stronę.

Przykład 1.2.9

Rozważmy dwa zdania

p =

x∈R

x  0 ∨ x < 0

q =

x∈R

x  0 ∨

x∈R

x < 0.

W tym przypadku w(p) = 1 oraz w(q) = 0. Prowadząc rozumowanie jak w przykładzie 1.2.8

stwierdzamy, że implikacja (1.28) w druga stronę nie zachodzi.

Przykład 1.2.10

Niech ϕ(x, y) ≡ [x > y] i x, y ∈ R. Wtedy zdanie

x > y jest zdaniem prawdzi-

wym, gdyż dla każdej liczby rzeczywistej y można zawsze wskazać liczbę x od niej większą. Natomiast
zdanie

x > y jest zdaniem fałszywym, gdyż nie istnieje liczba x większa od dowolnej liczby rze-

czywistej y. Zatem implikacja

ϕ(x, y) ⇒

ϕ(x, y) jest zdaniem fałszywym. Oznacza to, że

prawo przemienności kwantyfikatora ogólnego i szczegółowego w ogólności nie zachodzi.

Zadania

Zadanie 1.2.1

Za pomocą kwantyfikatorów zapisać następujące zdania

Równanie x

− x − 2 = 0 ma dodatni pierwiastek.

Istnieje liczba m, od której nie jest mniejszy kwadrat dowolnej liczby.

Każda liczba ma nieujemną wartość bezwzględną.

Funkcja sinus przyjmuje tylko wartości w przedziale h−1, 1i.

Każda liczba rzeczywista ma liczbę przeciwną.

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

Zadanie 1.2.2

Wyznaczyć dziedzinę i wykres funkcji zdaniowych

ϕ(x) =

− x

− 2 > 0

ϕ(x) =

|x + 1| + |x − 1| x

f )

ϕ(x) =

√

+ 2x + 1 +

√

− 6x + 9 < 2

ϕ(x) =

cos x −

< 1

ϕ(x) =

sin x −

√

3 cos x > 1

ϕ(x) =

3x−1

¬ 3

ϕ(x) =

log

(x + 1) − log

(x − 1) > log

1
3

Zadanie 1.2.3

Wyznaczyć dziedzinę funkcji zdaniowej, a następnie w układzie XOY naszkicuj jej

wykres

ϕ(x, y) =

(x + y > 1) ∧ (3x − 2y ¬ 6)

ϕ(x, y) =

(x + y > 1) ∨ (3x − 2y ¬ 6)

ϕ(x, y) =

+ y

< 4) ∧ (y ¬ x

− 2)

ϕ(x, y) =

− 2x + y

+ 6y 1

ϕ(x, y) =

|x + 1| + |y − 1| < 0

f )

ϕ(x, y) =

log y − log x > 1

Zadanie 1.2.4

Określić wartość logiczną zdań i zbudować ich zaprzeczenie

x∈R

sin 2x = 2 sin x cos x,

x∈R

√

= −x,

x∈R

| x | 0,

x∈R

y∈R

y > x,

x∈R

y∈R

y > x,

f )

x∈R

cos 2x = cos

x − sin

x∈R

a∈R

+ 4a +

> 0,

x∈R

> 0 ∧ sin

> cos

x∈R

+ 2x + 1 = 0 ∧ x < 0

a∈R

x∈R

(a + 1)x

+ (2a − 1)x + a < 0,

a∈h0,2i

x∈R

cos 2x =

− 4a + 1

− 1

x∈N

a∈R

− 2a + log x > 0,

ł)

a∈N

b∈Z

(x + 1)

+ bx

+ 2x

+ ax + 1),

x∈N

b∈R

−b

+ bx + x < 0.

Zadanie 1.2.5

Podać wartość logiczną zdania w zależności od wartości parametru p





x∈R

sin x ¬ p





⇒

cos

√





x∈R

cos x p





⇒





x∈R

|x| < 0









x∈R

− 2x + log

√

p > 0





⇒

sin





x∈R

− x +

p−3

> 0





⇒

√





x∈R

+ 3x +

p+1

> 0





⇒

ctg

√

1.3. PODSTAWOWE TECHNIKI DOWODZENIA TWIERDZEŃ.

f )





x∈R

−x

+ 4x + log

1
2

p < 0





∨





x∈R

+ x + 1 < 0





x∈R

−x

+ 2x + sin 2p ¬ 0 ∧ x

+ 2x + 3 > 0

1.3.

Podstawowe techniki dowodzenia twierdzeń.

Własności pojęć matematycznych oraz związki między nimi podaje się w twierdzeniach. Same zaś
pojęcia oraz ich nazwy określa się w definicjach w oparciu o pojęcia wcześniej zdefiniowane lub tak
zwane pojęcia pierwotne, których się nie definiuje tylko przyjmuje jako powszechnie znane (w geometrii
jest to np. punkt, w rachunku prawdopodobieństwa-zdarzenie elementarne). Każde twierdzenie uważa
się za prawdziwe jeśli zostało dowiedzione. Dowodząc dane twierdzenie wykorzystuje się twierdzenia
wcześniej udowodnione oraz aksjomaty, czyli twierdzenia, które uważa się za oczywiste i przyjmuje się
je bez dowodu. Znajomość dowodu ułatwia posługiwanie się twierdzeniem oraz pozwala na poznanie
wzajemnych powiązań miedzy pojęciami matematycznymi. Twierdzenia mają zwykle postać implikacji
p ⇒ q. Poprzednik implikacji p nazywa się założeniem, a następnik q nazywa się tezą. Jeśli nawet
jakieś twierdzenie nie jest zapisane w postaci implikacji, to można je przeformułować w taki sposób,
aby było zapisane w postaci implikacji, np. twierdzenie: Iloczyn dwóch liczb parzystych jest liczbą
parzystą można sformułować jako:

Twierdzenie 1.3.1

Jeśli dwie liczby x i y są parzyste, to ich iloczyn xy jest liczbą parzystą.

W twierdzeniu 1.3.1 założeniem jest: ”liczby x i y są parzyste”, a tezą: ”iloczyn xy jest parzysty”.

W matematyce spotyka się również twierdzenia, które mają postać równoważności p ⇔ q. Na mocy

prawa rachunku zdań (1.18) wykazanie prawdziwości twierdzenia p ⇔ q najczęściej sprowadza się do
udowodnienia dwóch implikacji p ⇒ q i q ⇒ p.

Formułując twierdzenie przyjmujemy, że poprzednik jest zdaniem prawdziwym. Jak wiemy im-

plikacja będzie wówczas prawdziwa, gdy prawdziwy będzie następnik. W sytuacji, gdy poprzednik
jest fałszywy, implikacja będzie prawdziwa bez względu na wartość logiczną następnika, ale takiego
przypadku nie rozpatrujemy wykazując prawdziwość twierdzenia. Dowody twierdzeń matematycznych
polegają na uznaniu pewnych zdań za konsekwencję logiczną innych, przy wykorzystaniu reguł wnio-
skowania i praw logicznych. Reguły wnioskowania podaje się w postaci następujących schematów:
zdania będące przesłankami przedzielone przecinkami oznaczającymi koniunkcję, piszemy nad kreską,
a wnioski - pod kreską. Jeżeli przesłanki są prawdziwe, to wnioski również są prawdziwe. Poniżej
wymieniamy najczęściej wykorzystywane reguły wnioskowania.

PODSTAWOWE REGUŁY WNIOSKOWANIA

reguła odrywania

p, (p ⇒ q)

(1.34)

modus tollens

∼ q, p ⇒ q

∼ p

(1.35)

reguła sylogizmu warunkowego

(p ⇒ q), (q ⇒ r)

p ⇒ r

dowód przez sprowadzenie do sprzeczności

∼ p ⇒ (q ∧ ∼ q)

(1.36)

(p ∧ ∼ q) ⇒∼ p

p ⇒ q

(1.37)

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

Dowodząc twierdzenie opieramy się o reguły wnioskowania oraz tautologie rachunku zdań. Najczę-

ściej stosuje się następujące metody dowodzenia.

1. Dowód wprost.

Metoda ta polega na wykazaniu, że z prawdziwości założenia wynika prawdzi-

wość tezy. Korzystamy tu z reguły odrywania (1.34), która mówi, że jeśli założenie p i implikację
p ⇒ q uznamy za prawdziwe, to tezę q możemy uznać za prawdziwą.

Przykład 1.3.2

Wykorzystując metodę dowodu wprost udowodnimy twierdzenie 1.3.1. Naj-

pierw przypomnijmy, że liczba x jest parzysta, gdy dzieli się przez 2, tj. gdy istnieje liczba
całkowita k taka, że x = 2k. Niech p oznacza zdanie: ”Liczby x i y są parzyste”, a q - ”Iloczyn
xy jest liczbą parzystą”. Załóżmy, że liczby x i y są parzyste, tzn. zdanie p jest zdaniem praw-
dziwym. Wtedy istnieją liczby całkowite k i l takie, że x = 2k i y = 2l. Wykażemy, że zdanie q
też jest zdaniem prawdziwym. Mamy

xy = (2k)(2l) = 4kl,

co oznacza, że liczba xy jest podzielna przez 2, a więc jest parzysta. Pokazaliśmy więc, że w(p) = 1
i w(p ⇒ q) = 1. Stosując regułę odrywania wnosimy, że w(q) = 1.

2. Dowód nie wprost.

Dowód nie wprost opiera się o prawo kontrapozycji. Zakładamy, że zdanie

p jest prawdziwe i dowodzimy wprost, że zdanie ∼ q ⇒∼ p też jest prawdziwe. Następnie
korzystamy z prawa kontrapozycji otrzymując prawdziwość implikacji p ⇒ q. Korzystając z
reguły odrywania dowodzimy prawdziwości zdania q.

Przykład 1.3.3

Wykorzystując metodę dowodu nie wprost wykażemy, że jeżeli iloczyn dwóch

liczb x i y jest liczbą parzystą, to x jest liczbą parzystą lub y jest liczbą parzystą. Przypomnijmy,
że liczba x jest nieparzysta jeśli istnieje liczba całkowita k taka, że x = 2k + 1.

Niech p oznacza zdanie: ”Iloczyn xy jest liczbą parzystą”, q - ”x jest liczbą parzystą lub y
jest liczbą parzystą”. Załóżmy, że zdanie ∼ q jest zdaniem prawdziwym tzn., że x jest liczbą
nieparzystą i y jest liczbą nieparzystą (skorzystaliśmy z praw de Morgana). Istnieją więc liczby
całkowite k i l takie, że x = 2k + 1 i y = 2l + 1. Tym samym mamy

xy = (2k + 1)(2l + 1) = 2(2kl + k + l) + 1.

Oznacza to, że iloczyn xy jest nieparzysty, czyli zdanie ∼ p jest prawdziwe (bo p jest fałszywe).
Otrzymaliśmy więc, że implikacja ∼ q ⇒∼ p jest zdaniem prawdziwym. Zatem z prawa kon-
trapozycji wynika, że implikacja p ⇒ q jest prawdziwa. Stosując regułę odrywania wnioskujemy
prawdziwość zdania q.

3. Dowód przez sprowadzenie do sprzeczności.

Metoda ta polega na zaprzeczeniu twierdzenia,

które mamy udowodnić. Opieramy się o regułę (1.36), która mówi, że jeżeli z założenia, że
twierdzenie jest fałszywe wynika sprzeczność, to tym samym twierdzenie uznajemy za prawdziwe.
Jeśli w regule (1.36) za zdanie p przyjmiemy p ⇒ q, a za q zdanie r, to otrzymamy następującą
regułę wnioskowania

(p∧ ∼ q) ⇒ (r∧ ∼ r)

p ⇒ q

(1.38)

W tym przypadku zakładamy, że zdanie p∧ ∼ q jest prawdziwe i wnioskujemy stąd sprzeczność,
tym samym uznajemy prawdziwość implikacji p ⇒ q.

Zauważmy, że podstawiając w regule (1.38) za zdanie r zdanie ∼ p otrzymamy ∼ p ∧ p, które
jest zdaniem sprzecznym. Ponieważ (∼ p ∧ p) ⇒∼ p, to wykorzystując prawo przechodniości
implikacji otrzymamy regułę wnioskowania

(p∧ ∼ q) ⇒∼ p

p ⇒ q

W tym przypadku zakładając, że zdanie p∧ ∼ q jest prawdziwe wnioskujemy, że zdanie p jest
fałszywe i tym samym uznajemy, że implikacja p ⇒ q jest prawdziwa.

1.3. PODSTAWOWE TECHNIKI DOWODZENIA TWIERDZEŃ.

Przykład 1.3.4

Działanie metody dowodu przez sprowadzenie do sprzeczności zilustrujemy

dowodząc, że

√

2 jest liczbą niewymierną. W tym celu oznaczmy przez p zdanie: ”a =

√

2”, a

przez q - ”a jest liczbą niewymierną”. Udowodnimy, że zachodzi twierdzenie p ⇒ q. Załóżmy, że
zdanie p∧ ∼ q jest zdaniem prawdziwym, tzn. że a =

√

2 i a jest liczbą wymierną. Przypomnijmy,

że liczba jest wymierna jeśli można ją przedstawić w postaci nieskracalnego ułamka

x
y

, wtedy x

jest liczbą nieparzystą lub y jest liczbą nieparzystą. Mamy więc

√

2 =

x
y

, a stąd

√

2y = x. Po

podniesieniu do kwadratu stronami otrzymamy

= x

(1.39)

co oznacza, że x

jest liczbą parzystą. Z przykładu 1.3.3 wynika, że x jest liczbą parzystą,

czyli istnieje liczba całkowita k taka, że x = 2k. Wstawiając do równania (1.39) otrzymujemy

= 4k

, czyli

= 2k

, co oznacza, że liczba y jest parzysta, tym samym dochodzimy do

sprzeczności ze stwierdzeniem, że jedna z liczb x lub y jest liczbą nieparzystą. Zatem zakładając,
że zdanie p∧ ∼ q jest prawdziwe doszliśmy do sprzeczności r∧ ∼ r, gdzie r oznacza zdanie: ”x jest
liczbą nieparzystą lub y jest liczbą nieparzystą”, bowiem pokazaliśmy, że x jest liczbą parzystą
i y jest liczbą parzystą. Stosując regułę (1.38) dostajemy, ze implikacja p ⇒ q jest prawdziwa.
Zatem z reguły odrywania wynika, że

√

2 jest liczbą niewymierną.

W dowodach pewnych twierdzeń można korzystać z więcej niż jednej metody dowodowej. Wynika
to z przechodniości implikacji. W takiej sytuacji należy kilkakrotnie zastosować regułę odrywania.

WARUNEK KONIECZNY I DOSTATECZNY

Jeżeli ze zdania p wynika zdanie q (p ⇒ q), to mówimy, że
p jest warunkiem dostatecznym (wystarczającym) dla q,
natomiast q jest warunkiem koniecznym dla p.

Przykład 1.3.5

Podzielność liczby n przez 4 jest warunkiem dostatecznym podzielności liczby n

przez 2.

4|n ⇒ 2|n

Podzielność liczby n przez 4 nie jest warunkiem koniecznym podzielności liczby n przez 2, o czym
świadczy przykład liczby 6, która jest podzielna przez 2, ale nie jest podzielna przez 4.

Jeżeli warunek konieczny jest jednocześnie warunkiem dostatecznym, to mówimy, że jest to wa-

runek konieczny i dostateczny.

Przykład 1.3.6

Podzielność liczby n przez 2 i przez 5 jest warunkiem koniecznym i dostatecznym

podzielności liczby n przez 10.

2|n ∧ 5|n

⇔ 10|n

Chcąc udowodnić twierdzenie, które dotyczy liczb naturalnych zwykle stosujemy

zasadę indukcji

matematycznej.

Twierdzenie 1.3.7

Jeżeli ciąg twierdzeń dotyczących liczb naturalnych T (n

), T (n

+ 1), . . . spełnia

warunki:

twierdzenie T (n

) jest prawdziwe;

dla dowolnej liczby naturalnej n n

z prawdziwości twierdzenia T(n) wynika prawdziwość

twierdzenia T (n + 1),

to dla każdej liczby naturalnej n n

twierdzenie T(n) jest prawdziwe.

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

Przykład 1.3.8

Najstarszy znany dowód indukcyjny podał w 1575 roku Francesco Maurolico. Udo-

wodnił on, że suma n pierwszych liczb nieparzystych równa jest n

. Dowód ten przedstawimy poniżej,

mianowicie udowodnimy, że

n∈N

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

(1.40)

I krok indukcyjny:
Oczywiście dla n = 1 lewa trona równości (1.40) równa jest 1, a prawa 1

= 1. Zatem twierdzenie jest

prawdziwe dla n = 1.

II krok indukcyjny:
Następnie zakładamy, że twierdzenie jest prawdziwe dla liczby naturalnej n tj. zakładamy, że

Założenie: 1 + 3 + 5 + · · · + (2n − 1) = n

i dowodzimy prawdziwości twierdzenia dla liczby naturalnej n + 1

Teza: 1 + 3 + 5 + · · · + (2n + 1) = (n + 1)

Dowód może przebiegać w następujący sposób:

Dowód:

1 + 3 + 5 + · · · + (2n − 1) + (2n + 1)

zał .

= n

+ 2n + 1 = (n + 1)

Uwaga 1.3.9

Gottfried Wilhelm Leibniz udowodnił, że dla dowolnej liczby całkowitej dodatniej n,

− n jest podzielne przez 3; n

− n jest podzielne przez 5 oraz, że n

− n jest podzielne przez 7. Czy

to oznacza, że można ten wynik uogólnić bez dowodu? Okazuje sie, że nie. Sam Leibniz zauważył, że
2

− 2 = 510 i nie jest podzielne przez 9. Pokazuje to, że uogólnienie jest uprawomocnione tylko

na podstawie dowodu.

Przykład 1.3.10

Wykorzystując zasadę indukcji matematycznej udowodnimy, że dla dowolnego

n ∈ N liczba n

− n jest podzielna przez 7.

I krok indukcyjny:
Dla n = 1 wyrażenie n

− n przyjmuje wartość 0, co jest oczywiście podzielne przez 7.

II krok indukcyjny:
Założenie:

k∈Z

− n = 7k

Teza:

l∈Z

(n + 1)

− (n + 1) = 7l

Dowód: Celem dowodu będzie wskazanie liczby całkowitej l występującej w tezie. Korzystając ze
wzoru na dwumian Newtona otrzymujemy

(n + 1)

− (n + 1) = n

+ 7n

+ 21n

+ 35n

+ 21n

+ 7n + 1 − n − 1.

Z założenia indukcyjnego wynika, że n

= 7k + n. Wykorzystując ten fakt dostajemy

− n = 7k + n + 7n

+ 21n

+ 35n

+ 21n

+ 7n − n = 7(k + n

+ 3n

+ 5n

+ 3n

+ n).

Ponieważ n jest liczbą naturalną, a k jest liczbą całkowitą, to k + n

+ 3n

+ 5n

+ 3n

+ n jest

liczbą całkowitą i możemy przyjąć, że szukane l = k + n

+ 3n

+ 5n

+ 3n

+ n.

Zadanie 1.3.1

Czy warunek p :”liczba naturalna n jest podzielna przez 3” jest warunkiem koniecz-

nym, dostatecznym czy też koniecznym i dostatecznym dla zadania q, jeśli

1.3. PODSTAWOWE TECHNIKI DOWODZENIA TWIERDZEŃ.

q: ”n jest podzielna przez 6”,

q: ”n jest większa od 2”,

q: ”suma cyfr rozwinięcia dziesiętnego liczby n jest podzielna przez 3”.

Zadanie 1.3.2

Wykorzystując zasadę indukcji matematycznej udowodnij, że dla dowolnego n ∈ N

liczba n

− n jest podzielna przez 3,

liczba n

− n jest podzielna przez 5,

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

1 + 5 + 9 + · · · + (4n − 3) = n(2n − 1),

1 + 2 + 4 + · · · + 2

= 2

n+1

− 1,

+ 2

+ · · · + n

1
6

n(n + 1)(2n + 1),

f )

+ 2

+ · · · + n

n(n+1)

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

1
3

n(n + 1)(n + 2),

1 · 4

4 · 7

+ · · · +

(3n − 2)(3n + 1)

3n + 1

1 · 2

2 · 2

+ · · · +

n(n + 1)

n + 1

liczba n

+ 2n jest podzielna przez 3,

liczba 10

− (−1)

jest podzielna przez 11,

liczba 9 · 31

+ 1 jest podzielna przez 10,

ł)

liczba 4

+ 15n − 1 jest podzielna przez 9,

liczba 2

n+2

+ 3

2n+1

jest podzielna przez 7,

liczba 2

5n+1

+ 4

5n+1

− 6 jest podzielna przez 31,

liczba 9

3n+1

− 3

3n+1

− 6 jest podzielna przez 13,

1 · 3 · 5 . . . (2n − 1)

2 · 4 · 6 . . . 2n

√

2n + 1

n! 2

n−1

x>−1

(1 + x)

1 + nx, (nierówność Bernoulli’ego

 n

, (n  4).

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

ROZWIĄZANIA I ODPOWIEDZI

1.1.2

Tautologie: a, c, e, i; zdania sprzeczne: d, g. Pozostałe zdania nie są ani tautologiami, ani zdaniami
sprzecznymi.

1.1.3

Prawo przemienności i łączności zachodzi tylko dla równoważności, co można sprawdzić za po-
mocą matrycy logicznej. Dla implikacji mamy tylko

(p ⇒ q) ⇒ r

⇒

p ⇒ (q ⇒ r)

1.1.4

Zachodzi prawo rozdzielności implikacji względem koniunkcji oraz względem alternatywy, ale
tylko z ”lewej strony”, tzn.

p ⇒ (q ∧ r)

⇔

(p ⇒ q) ∧ (p ⇒ r)

p ⇒ (q ∨ r)

⇔

(p ⇒

q) ∨ (p ⇒ r)

. Natomiast z ”prawej strony” mamy tylko implikację w jedna stronę mianowicie:

(p ⇒ r) ∧ (q ⇒ r)

⇒

(p ∧ q) ⇒ r

oraz

(p ∨ q) ⇒ r

⇒

(p ⇒ r) ∨ (q ⇒ r)

1.1.5 a)

Wykorzystać matrycę logiczną.

w(p XOR p) = 0

Zachodzą tylko prawa przemienności

i łączności.

p XOR q ⇔

(p∧ ∼ q) ∨ (q∧ ∼ p)

1.1.6 b)

w(p |∼ p) = 1

Wykorzystując matrycę logiczną można pokazać, że kreska Sheffera nie jest

rozdzielna względem koniunkcji, ale jest rozdzielna względem alternatywy.

(p ∨ q) ⇔ (∼ p |∼ q)

(p | q) ⇔∼ (p ∧ q)

1.1.7 b)

w(∼ p ⊥ p) = 0

Wykorzystując matrycę logiczna można pokazać, że strzałka Peirce’a nie

jest rozdzielna ani względem koniunkcji, ani względem alternatywy.

(p ∧ q) ⇔ (∼ p ⊥∼ q)

(p ⊥ q) ⇔∼ (p ∨ q)

1.2.1 a)

x>0

− x − 2 = 0 (wiadomo, że tym pierwiastkiem jest 2)

1.2.1 b)

mıR

y∈R

 m (oczywiście m = 0)

1.2.1 b)

x∈R

|x|  0

1.2.1 c)

x∈R

| sin x| ¬ 1

1.2.1 d)

x∈R

y∈R

y = −x

1.2.2 a)

= R, S(ϕ) = (−∞, −

√

2) ∪ (

√

2, ∞)

1.2.2 b)

= R, S(ϕ) = h−2, 2i

1.2.2 c)

= R, S(ϕ) =

x ∈ R : −

π + 2kπ < x <

π + 2kπ, k ∈ Z

1.2.2 d)

= R, S(ϕ) =

1.2.2 e)

= R r {0}, S(ϕ) =

1 −

√

, 0

∪

1 +

√

1.2.2 f)

= R, S(ϕ) = ∅

1.2.2 g)

= R, S(ϕ) =

x ∈ R :

+ 2kπ < x <

π + 2kπ, k ∈ Z

1.2.2 h)

= (1, ∞), S(ϕ) = (2, ∞)

1.2.4 a)

Prawdziwe. Jest to znany wzór trygonometryczny zwany wzorem na sinus kąta podwojonego.

x∈R

sin 2x 6= 2 sin x cos x.

1.3. PODSTAWOWE TECHNIKI DOWODZENIA TWIERDZEŃ.

1.2.4 b)

Prawdziwe. Np. x = 0.

x∈R

√

6= −x.

1.2.4 c)

Prawdziwe.

x∈R

|x| < 0.

1.2.4 d)

Fałszywe. Zdanie to oznacza, że istnieje liczba mniejsza od każdej liczby rzeczywistej.

x∈R

y∈R

y ¬ x.

1.2.4 d)

Prawdziwe. Zdanie to oznacza, że dla każdej liczby rzeczywistej istnieje liczba od niej większa.

x∈R

y∈R

y ¬ x.

1.2.4 f)

Prawdziwe -wzór na cosinus kata podwojonego.

x∈R

cos 2x 6= cos

x − sin

1.2.4 g)

Chcąc sprawdzić wartość logiczną podanego zdania musimy odpowiedzieć na pytanie: Dla ja-

kiej wartości parametru x funkcja kwadratowa a

+ 4a +

zmiennej a, przyjmuje tylko

wartości dodatnie. Ponieważ współczynnik stojący przy a

jest dodatni wystarczy, aby wyróż-

nik tej funkcji był ujemny. Mamy więc do rozwiązania następującą nierówność wykładniczą

16 − 4

< 0. Zbiór rozwiązań tej nierówności jest przedziałem (−∞, −2). Zatem zdanie jest

prawdziwe.

x∈R

a∈R

+ 4a +

¬ 0.

1.2.4 h)

Najpierw skorzystamy z prawa (1.20) otrzymując koniunkcje dwóch zdań. Pierwsze z tych zdań
jest zdaniem prawdziwym, bowiem funkcja wykładnicza przyjmuje tylko wartości dodatnie. Dru-
gie zdanie oczywiście jest zdaniem prawdziwym. Zatem podane zdanie jest koniunkcją dwóch

zdań prawdziwych, a więc jest zdaniem prawdziwym.

x∈R

¬ 0 ∨ sin

¬ cos

1.2.4 i)

Prawdziwe. Np. x = −1.

x∈R

+ 2x + 1 6= 0 ∨ x  0

1.2.4 j)

Problem jest podobny do zadania 1.2.4g). W tym przypadku funkcja kwadratowa zmiennej x ma
przyjmować tylko wartości ujemne, a więc należy założyć, że a+1 < 0 i ∆ = (2a−1)

−4a(a+1) =

−8a + 1 < 0. Zatem mamy a < −1 i a >

. Oznacza to, że a ∈ ∅, czyli że zdanie jest fałszywe.

a∈R

x∈R

(a + 1)x

+ (2a − 1)x + a  0

1.2.4 k)

Aby zbadać wartość logiczną podanego zdania załóżmy, że jest ono prawdziwe i spróbujmy zna-
leźć a i x spełniające podane równanie. Ponieważ zbiorem wartości funkcji cosinus jest przedział

h−1, 1i, to podana równość będzie miała rozwiązanie jeśli

− 4a + 1

− 1

¬ 1, a ma to miejsce

dla a ∈ h0,

i ∪ {2}. Zatem widzimy, że możliwe jest znalezienie x ∈ R i a ∈ h0, 2i takich,

aby cos 2x =

− 4a + 1

− 1

, na przykład a = 2 i x = π. Oznacza, to że zdanie jest prawdziwe.

a∈h0,2i

x∈R

cos 2x 6=

− 4a + 1

− 1

1.2.4 l)

Problem jest podobny do zadania 1.2.4g). W tym przypadku funkcja kwadratowa zmiennej
a ma przyjmować tylko wartości dodatnie, a więc należy założyć, że ∆ = 4 − 4 log x < 0.
Rozwiązaniem tej nierówności logarytmicznej jest x > 10. Zatem zdanie jest prawdziwe, bo
istnieje liczba naturalna x, np. równa 11 taka, że a

− 2a + log x > 0 dla wszystkich a ∈ R.

x∈N

a∈R

− 2a + log x ¬ 0

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

1.2.4 ł)

W tym przypadku należy sprawdzić, czy istnieją parametry a ∈ N i b ∈ Z, dla których wielomian
W (x) = x

+ bx

+ 2x

+ ax + 1 jest podzielny przez wielomian (x + 1)

. Ponieważ wielomian

(x + 1)

ma podwójny pierwiastek x = −1, to należy rozwiązać układ równań

(

W (−1) = 0

(−1) = 0

z niewiadomymi a i b, tj.

(

−a − b + 4 = 0

a + 3b − 8 = 0

. Rozwiązaniem tego układu jest a = 2, b = 2.

Oznacza to, że zdanie jest prawdziwe.

a∈N

b∈Z

∼

(x + 1)

+ bx

+ 2x

+ ax + 1)

1.2.4 m)

Problem jest podobny do zadania 1.2.4g). W tym przypadku funkcja kwadratowa zmiennej b
ma przyjmować tylko wartości ujemne, a więc wystarczy założyć, że ∆ = x

− 4(−1)x < 0.

Rozwiązaniem tej nierówności jest przedział (−4, 0). Ale szukamy parametru x ∈ N. Zatem
nasze zdanie jest fałszywe.

x∈N

b∈R

−b

+ bx + x  0

1.2.5 a)

dla p < 1 zdanie prawdziwe, dla p  1 zdanie fałszywe,

1.2.5 b)

dla p ¬ −1 zdanie prawdziwe, dla p > −1 zdanie fałszywe,

1.2.5 c)

dla p 

zdanie prawdziwe, dla 0 < p <

zdanie fałszywe, (dla p ¬ 0 podane wyrażenie nie

jest zdaniem logicznym, bo wówczas nie istnieje log

√

p),

1.2.5 d)

dla p  5 zdanie prawdziwe, dla

p < 5

zdanie fałszywe,

1.2.5 e)

dla p −3 zdanie prawdziwe, dla p < −3 zdanie fałszywe,

1.2.5 f)

dla

p > 16

zdanie prawdziwe, dla

0 < p ¬ 16

zdanie fałszywe,

1.2.5 g)

Aby określić wartość logiczną podanego zdania musimy najpierw skorzystać z prawa (1.27). Wów-
czas otrzymane zdanie jest koniunkcją dwóch zdań. Drugie z tych zdań jest oczywiście zdaniem
prawdziwym, natomiast wartość logiczna zdania pierwszego zależy od wartości parametru p. W

tym przypadku żądamy, aby ∆ = 4 + 4 sin 2p ¬ 0. Ostatecznie otrzymujemy, że dla p =

π + kπ,

k ∈ Z zdanie jest prawdziwe, a dla p ∈ R r {p =

π + kπ, k ∈ Z} zdanie jest fałszywe.

1.3.1 a)

q jest warunkiem dostatecznym dla p, bo każda liczba podzielna przez 6 jest na pewno podzielna
przez 3

1.3.1 b)

q jest warunkiem koniecznym dla p, bo jak liczba jest podzielna przez 3, to jest oczywiście
większa od 2

1.3.1 c)

q jest znaną zasadą podzielności przez 3, zatem jest warunkiem koniecznym i dostatecznym dla
p

1.3.2 ł)

I krok indukcyjny: Dla n = 1 mamy 4 + 15 − 1 = 18 = 2 · 9.

II krok indukcyjny:

Założenie:

k∈Z

+ 15n − 1 = 9k

Teza:

l∈Z

n+1

+ 15(n + 1) − 1 = 9l

Dowód: Zauważmy, że z założenia indukcyjnego mamy 4

= 9k − 15n + 1. Wobec tego

n+1

+ 15(n + 1) − 1 = 4(9k − 15n + 1) + 15n + 14 = 36k − 45n + 18

= 9(4k − 5n + 2).

To kończy dowód, bo l = 9(4k − 5n + 2) ∈ Z dla dowolnego n ∈ N.

1.3. PODSTAWOWE TECHNIKI DOWODZENIA TWIERDZEŃ.

1.3.2 m)

I krok indukcyjny: Dla n = 1 mamy 2

n+2

+ 3

2n+1

= 35 co jest podzielne przez 7.

II krok indukcyjny:

Założenie:

k∈Z

n+2

+ 3

2n+1

= 7k

Teza:

l∈Z

n+3

+ 3

2n+3

= 7l

Dowód: Zauważmy, że z założenia indukcyjnego mamy 3

2n+1

= 7k − 2

n+2

. Wobec tego

n+3

+ 3

2n+3

= 2

n+3

+ 3

2n+1 zał .

= 2

n+3

+ 9(7k − 2

n+2

)

= 2

n+3

+ 63k − 92

n+2

= −72

n+2

+ 63k == 7(9k − 2

n+2

) = 7l.

To kończy dowód, bo l = 9k − 2

n+2

∈ Z dla dowolnego n ∈ N.

1.3.2 p)

I krok indukcyjny: Dla n = 1 lewa strona nierówności równa jest

, a prawa

√

. Ponieważ

2 >

√

3, więc dla n = 1 podana nierówność zachodzi.

II krok indukcyjny:

Założenie:

1 · 3 · 5 . . . (2n − 1)

2 · 4 · 6 . . . 2n

√

2n + 1

Teza:

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

2 · 4 · 6 . . . (2n + 2)

√

2n + 3

Dowód:

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

2 · 4 · 6 . . . (2n + 2)

1 · 3 · 5 . . . (2n − 1)

2 · 4 · 6 . . . 2n

2n + 1

2n + 2

zał .

√

2n + 1

2n + 2

√

2n + 1

2n + 2

√

2n + 3

√

2n + 3

√

+ 8n + 3

(2n + 2)

√

2n + 3

1 −

(2n + 2)

√

2n + 3

√

2n + 3

1.3.2 q)

I krok indukcyjny: Dla n = 1 obie strony nierówności są równe 1, a więc jest ona spełniona.

II krok indukcyjny:

Założenie: n! 2

n−1

Teza: (n + 1)! 2

Dowód: (n + 1)! = n!(n + 1)

zał .

n−1

(n + 1) 2

n−1

· 2 2

, bo oczywiście

n∈N

n + 1 2.

1.3.2 r)

Załóżmy, że x ∈ (−1, ∞).

I krok indukcyjny: Dla n = 1 mamy 1 + x  1 + x, ponieważ

x∈R

(1.41)

II krok indukcyjny:

Założenie:

n>1

(1 + x)

1 + nx

Teza:

n>1

(1 + x)

n+1

1 + (n + 1)x

ROZDZIAŁ 1. ELEMENTY LOGIKI MATEMATYCZNEJ.

Dowód: Mnożąc obie strony nierówności z założenia indukcyjnego przez dodatnie wyrażenie
1 + x otrzymujemy

(1 + x)

n+1

> (1 + nx)(1 + x) = 1 + x + nx + nx

= 1 + (n + 1)x + nx

(1.41)

1 + (n + 1)x.

Rozdział 2

Zbiory, relacje i funkcje.

2.1.

Zbiory.

Pojęcie zbioru jest jednym z podstawowych pojęć matematyki. Własnościami zbiorów, bez wnikania
w istotę elementów, z których się one składają, zajmuje się teoria mnogości. Teoria ta została stwo-
rzona przez genialnego matematyka niemieckiego Georga Cantora (1845-1918). Metody stosowane w
początkowym okresie rozwoju teorii mnogości oparte były na intuicyjnym (nieformalnym) traktowa-
niu zbiorów (dlatego też nazywa się ją naiwną), co wkrótce doprowadziło do powstania tak zwanych
antynomii

. Jako odpowiedź na paradoksy powstające w teorii naiwnej powstała aksjomatyczna teoria

mnogości. Istnieje wiele różnych aksjomatyzacji teorii mnogości, ale najbardziej rozpowszechniona jest
aksjomatyka Zermelo-Fraenkla

W niniejszym podręczniku prezentowana jest tylko naiwna teoria mnogości. Zatem pojęcie zbioru i

należenia do zbioru przyjmujemy jako pierwotne. Ponadto będziemy zakładali, że wszystkie rozważane
zbiory są utworzone z elementów pewnego zbioru X, który nazywać będziemy przestrzenią. Zbiory
będziemy oznaczali dużymi literami alfabetu łacińskiego, a ich elementy - małymi. Ponadto zbiory
będziemy definiować następująco

albo wymieniając elementy należące do zbioru, np. A = {2, 4, 8, 16, 32, 64, . . . } ,

albo podając regułę wyznaczania elementów zbioru, np. A = {2

: n ∈ N} .

Uwaga 2.1.1

Powtórzenie jakiegoś elementu w opisie zbioru oraz kolejność w jakiej wymieniane są

elementy nie ma wpływu na definicję samego zbioru, oznacza to, między innymi, że opisy {a, b}, {b, a},
{a, a, b} definiują ten sam zbiór, którego elementami są a i b.

Jeżeli element a należy do zbioru A, to będziemy pisać a ∈ A. Jeśli element a nie należy do
zbioru A, to będziemy pisać a 6∈ A.

Definicja 2.1.2

Zbiór, który posiada tylko jeden element nazywamy zbiorem jednoelementowym.

Zbiór, do którego żaden element nie należy nazywamy zbiorem pustym i oznaczamy ∅.

Niech A i B będą dowolnymi zbiorami.

Definicja 2.1.3

Mówimy, że zbiór A jest równy zbiorowi B i piszemy A = B, jeśli każdy element

zbioru A jest elementem zbioru B i każdy element zbioru B jest elementem zbioru A, co oznacza, że

A = B ⇐⇒

x∈A

x ∈ B ∧

x∈B

x ∈ A

Z praw de Morgana wynika, że zbiór A jest różny od zbioru B jeśli istnieje element należący do zbioru
A, który nie należy do zbioru B lub istnieje element należący do zbioru B, który nie należy do zbioru
A, tzn.

A 6= B ⇔

x∈A

x 6∈ B ∨

x∈B

x 6∈ A

Antynomia oznacza sprzeczność między zdaniami, z których każde wydaje się dobrze uzasadnione, lub też sprzeczność

w obrębie jednego zdania.

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

Zauważmy, że zbiór A jest równy zbiorowi B, jeśli

x∈X

x ∈ A ⇔ x ∈ B

Przykład 2.1.4

Niech A = ∅ i B = {∅}. Oczywiście zbiory A i B nie są równe. Zbiór A nie zawiera

żadnego elementu, natomiast zbiór B zawiera jeden element, którym jest zbiór pusty.

Definicja 2.1.5

Mówimy, że zbiór A zawiera się w zbiorze B i piszemy A ⊆ B, jeśli

x∈X

x ∈ A ⇒ x ∈ B

Zbiór A nazywamy podzbiorem zbioru B, a zbiór B nadzbiorem zbioru A.

Jeśli A ⊆ B i A 6= B, to będziemy pisać A ⊂ B.

Definicja 2.1.6

Zbiór A nazywamy podzbiorem właściwym zbioru B, jeśli A ⊂ B.

Definicja 2.1.7

Dopełnieniem zbioru A (do przestrzeni X) nazywamy zbiór A zawierający wszyst-

kie elementy przestrzeni X nienależące do zbioru A, tzn.

A = {x ∈ X : x 6∈ A}.

Z definicji 2.1.7 wynika, że

x∈X

x ∈ A ⇔∼ x ∈ A

Przykład 2.1.8

Dopełnieniem zbioru liczb ujemnych do zbioru liczb rzeczywistych jest zbiór liczb

nieujemnych.

Dopełnieniem zbioru liczb wymiernych do zbioru liczb rzeczywistych jest zbiór liczb niewymier-

nych.

Definicja 2.1.9

Sumą zbiorów A i B nazywamy zbiór złożony ze wszystkich elementów, które należą

do zbioru A lub do zbioru B tj.

A ∪ B = {a : a ∈ A ∨ a ∈ B}.

Z definicji 2.1.9 wynika, że

a∈X

a ∈ A ∪ B

⇔

a ∈ A

∨ a ∈ B

Z praw rachunku zdań wynika, że

A ∪ X = X,

A ∪ A = A,

A ∪ A

= X,

A ∪ ∅ = A.

(2.1)

Definicja 2.1.10

Iloczynem zbiorów A i B nazywamy zbiór złożony z elementów, które jednocześnie

należą do zbioru A i do zbioru B, tj.

A ∩ B = {a : a ∈ A ∧ a ∈ B}.

Z definicji 2.1.10 mamy

a∈X

a ∈ A ∩ B

⇔

a ∈ A

∧ a ∈ B

Z praw rachunku zdań wynika, że

A ∩ X = A,

A ∩ A = A,

A ∩ A

= ∅,

A ∩ ∅ = ∅.

(2.2)

Definicja 2.1.11

Różnicą zbiorów A i B nazywamy zbiór złożony z tych elementów, które należą

do zbioru A i nie należą do zbioru B, tj.

A r B = {a : a ∈ A ∧ a /

∈ B},

2.1. ZBIORY.

Z definicji 2.1.11 wynika, że

a∈X

a ∈ A r B

⇔

a ∈ A

∧ ∼ a ∈ B

Korzystając z pojęcia dopełnienia zbioru możemy wyrazić różnicę zbiorów za pomocą iloczynu

A r B = A ∩ B.

(2.3)

Uwaga 2.1.12

Każde działanie w rachunku zbiorów ma swój odpowiednik w rachunku zdań i na od-

wrót. Na przykład sumie zbiorów odpowiada alternatywa, a iloczynowi zbiorów odpowiada koniunkcja.
Oznacza to, że możemy wykorzystać prawa rachunku zdań do dowodzenia praw rachunku zbiorów.

Definicja 2.1.13

Zbiory A i B nazywamy rozłącznymi, jeżeli nie mają wspólnego elementu, tzn.

A ∩ B = ∅.

Niech A

, A

, . . . , A

, . . . będą podzbiorami przestrzeni X. Będziemy używać następującej symboliki

∪ A

∪ · · · ∪ A

∪ · · · =

∞

[

i=1

∩ A

∩ · · · ∩ A

∩ · · · =

∞

i=1

Zadanie 2.1.1

Wykorzystując definicje sumy, iloczynu i różnicy zbiorów oraz prawa rachunku zdań

udowodnić następujące prawa rachunku zbiorów.

prawa de Morgana

(A ∪ B) = A ∩ B,

(A ∩ B) = A ∪ B,

(2.4)

przemienność sumy

A ∪ B = B ∪ A,

(2.5)

przemienność iloczynu

A ∩ B = B ∩ A,

(2.6)

łączność sumy

(A ∪ B) ∪ C = A ∪ (B ∪ C),

(2.7)

łączność iloczynu

(A ∩ B) ∩ C = A ∩ (B ∩ C),

(2.8)

f )

rozdzielność sumy względem iloczynu

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),

(2.9)

rozdzielność iloczynu względem sumy

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C),

(2.10)

prawa de Morgana dla różnicy zbiorów

A r (B ∩ C) = (A r B) ∪ (A r C),

(2.11)

A r (B ∪ C) = (A r B) ∩ (A r C),

(2.12)

A = (A ∩ B) ∪ (A r B),

A ⊆ B

⇒

(A ∪ B = B) ∧ (A ∩ B = A) ∧ (A r B = ∅)

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

Zadanie 2.1.2

Wykorzystując definicję inkluzji oraz własności implikacji udowodnić następujące pra-

wa inkluzji.

(A ⊆ B) ⇔ (B ⊆ A)

(2.13)

(A ∩ B) ⊆ A ⊆ (A ∪ B)

(2.14)

(A ⊆ B) ∧ (B ⊆ C)

⇒ (A ⊆ C),

(2.15)

(A ⊆ B) ∧ (C ⊆ D)

⇒

(A ∩ C) ⊆ (B ∩ D)

(2.16)

(A ⊆ B) ∧ (C ⊆ D)

⇒

(A ∪ C) ⊆ (B ∪ D)

Definicja 2.1.14

Parą uporządkowaną nazywamy zbiór dwuelementowy z ustalonym porządkiem

elementów, element określony jako pierwszy nazywamy poprzednikiem, a element określony jako
drugi - następnikiem. Parę uporządkowaną o poprzedniku a i następniku b oznaczamy symbolem
(a, b). Pary (a, b) i (c, d) są równe, gdy a = c i b = d.

Bardziej formalną definicję podał w 1921 roku Kuratowski

Definicja 2.1.15

Zbiór {{a}, {a, b}} oznaczamy przez (a, b) i nazywamy uporządkowaną parą o

poprzedniku a i następniku b.

Zauważmy, że gdy a 6= b, to (a, b) 6= (b, a) ponieważ {{a}, {a, b}} 6= {{b}, {a, b}}.

Definicja 2.1.16

Iloczynem kartezjańskim zbiorów A i B nazywamy zbiór uporządkowanych

par (a, b) takich, że a ∈ A i b ∈ B. tj.

A × B = {(a, b) : a ∈ A ∧ b ∈ B}.

Zadanie 2.1.3

Wykorzystując definicję iloczynu kartezjańskiego i prawa rachunku zdań udowodnić

następujące własności iloczynu kartezjańskiego.

A × B = ∅

⇐⇒

(A = ∅ ∧ B = ∅),

(2.17)

A ⊆ B ∧ C ⊆ D ⇒

(A × C) ⊆ (B × D)

(2.18)

rozdzielność iloczynu kartezjańskiego względem sumy zbiorów

A × (B ∪ C) = (A × B) ∪ (A × C),

(A ∪ B) × C = (A × C) ∪ (B × C),

(2.19)

rozdzielność iloczynu kartezjańskiego względem iloczynu zbiorów

A × (B ∩ C) = (A × B) ∩ (A × C),

(A ∩ B) × C = (A × C) ∩ (B × C),

(2.20)

rozdzielność iloczynu kartezjańskiego względem różnicy zbiorów

A × (B r C) = (A × B) r (A × C),

(A r B) × C) = (A × C) r (B × C),

(2.21)

(A × B) ∩ (C × D) = (A ∩ C) × (B ∩ D),

(2.22)

Uwaga 2.1.17

Oczywiście (A×B)∪(C ×D) 6= (A∪C)×(B∪D). Ponadto dla iloczynu kartezjańskiego

nie zachodzi prawo de Morgana. Natomiast mamy (A × X) = A × X.

Przykład 2.1.18

Pokażemy, że prawo rozdzielności sumy względem iloczynu kartezjańskiego nie za-

chodzi.

Niech A = {a} i B = C = ∅. Oczywiście z definicji iloczynu kartezjańskiego wynika, że B × C = ∅.

Zatem A ∪ (B × C) = A. Z drugiej strony mamy A ∪ B = A ∪ C = A. Wobec tego

(A ∪ B) × (A ∪ C) = {a} × {a} =

(x, y) : x ∈ {a} ∧ y ∈ {a}

= {(a, a)}.

Ale z definicji Kuratowskiego pary uporządkowanej mamy

(a, a) =

{a}, {a, a}

{a}, {a}

{a}

2.1. ZBIORY.

Ostatecznie (A ∪ B) × (A ∪ C) =

}. Ponieważ elementem zbioru {a} jest a, a elementem zbioru

{a}

jest zbiór jednoelementowy {a}, to {a} 6=

{a}

. Widzimy, więc że

A ∪ (B × C) 6= (A ∪ B) × (A ∪ C).

Przykład 2.1.19

Również nie zachodzi prawo rozdzielności iloczynu zbiorów względem iloczynu kar-

tezjańskiego Niech teraz A = B = C = {a}. Wtedy B × C =

{a}

. Wobec tego

A ∩ (B × C) = {a} ∩

{a}

= ∅.

Z drugiej strony mamy A ∩ B = A ∩ C = A. Zatem

(A ∩ B) × (A ∩ C) = {a} × {a} =

{a}

6= ∅,

co oznacza, że w ogólności

A ∩ (B × C) 6= (A ∩ B) × (A ∩ C).

W naturalny sposób można rozszerzyć definicję iloczynu kartezjańskiego na dowolną skończoną

liczbę zbiorów X

, X

, . . . , X

. Mianowicie iloczyn kartezjański zbiorów X

, X

, . . . , X

określamy

w sposób rekurencyjny

× X

= (X

× X

) × X

× X

× · · · × X

n−1

× X

= (X

× X

× · · · × X

n−1

) × X

Elementy zbioru X

× X

× · · · × X

n−1

× X

nazywamy n-tką uporządkowaną.

Zadania

Zadanie 2.1.4

Udowodnij podane równości

(A r B) ∩ B = ∅,

(A r B)

= A

∪ (A ∩ B),

A r B = A r (A ∩ B),

(A r B) ∩ C = (A ∩ C) r B,

(A ∩ B) ∪ (A

∩ B) = B,

f )

(A r B) ∪ (B r A) = (A ∪ B) ∩ (A ∩ B)

Zadanie 2.1.5

Podaj interpretację geometryczną następujących zbiorów

N × {1},

R ×

−

3π

R × h−1, ∞),

h−1, 2) × {−1, 0, 1},

{2, 3} × {

√

2, e, π}

∩

{

√

2, e, π} × {2, 3}

f )

h−1, 2i × h−2, 1i

∩

h−2, 1i × h−1, 2i

h−1, 2i × h−2, 1i

∪

h−2, 1i × h−1, 2i

{x ∈ R : |x + 2| < 3} × {x ∈ R : |x − 2| < 3},

{x ∈ R : x

+ x  6} × N,

h0, 1i × h0, 1i × h0, 1i,

{(x, y) ∈ R

: x

+ (y − 1)

¬ 4} × h−1, 1i,

h0, 2i × {(x, y) ∈ R

: (x − 1)

+ y

¬ 4}.

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

Zadanie 2.1.6

Znaleźć A ∩ B, A ∪ B, A r B, B r A, jeśli

A = {x : |x| + |1 − x| < 3}, B =

(

x :

+ 1

< 1

)

A = {x : 3

< 2 · 3

+ 3}, B = {x : log

4 < 8},

A = {(x, y) : x

+ (y − 1)

< 4}, B = {(x, y) : |x| + |y − 1| < 2},

A = {(x, y) : 4x + 3y ¬ 12}, B = {(x, y) : |y| ¬ 2},

A = {(x, y) : |x − y| ¬ 2}, B = {(x, y) : |y − 2| ¬ 1},

f )

A = {(x, y) : |x + y| ¬ 1}, B = {(x, y) : |x − 3| ¬ 1},

A = {(x, y) : x

− y

0}, B = {(x, y) : (x − 1)

+ y

¬ 1},

A = {(x, y) : x

+ y

¬ 1}, B = {(x, y) : x

+ y

¬ 9}.

ROZWIĄZANIA I ODPOWIEDZI

2.1.5 b)

dwie proste równoległe do osi OX o równaniach y = −

, y =

3π

;

półpłaszczyzna leżąca nad

prostą y = −1 łącznie z tą prostą;

zbiór pusty;

sześcian o wierzchołkach (0, 0, 0), (1, 0, 0),

(1, 1, 0), (0, 1, 0), (0, 0, 1), (1, 0, 1), (0, 1, 1), (1, 1, 1);

walec, którego podstawą jest koło o środku

(1, 0) i promieniu długości 2, leżący w płaszczyźnie Y OZ i wysokości równej 2.

2.1.6 a)

A = (−1, 2), B = (−∞, 0), A ∩ B = (−1, 0), A ∪ B = (−∞, 2), A rB = h0, 2), B rA = (−∞, −1i

2.1.6 b)

A = (−∞, 1), B = (0, 1) ∪ (

√

2, +∞), A ∩ B = (0, 1), A ∪ B = (−∞, 1) ∪ (

√

2, +∞),

A r B = (−∞, 0i, B r A = (

√

2, +∞)

2.2. RELACJE.

2.2.

Relacje.

Pojęcie iloczynu kartezjańskiego odgrywa ważną rolę w opisywaniu związków między elementami
dwóch zbiorów. Związki te bada się przez zdefiniowanie tak zwanej relacji binarnej, dwuargumen-
towej lub dwuczłonowej w iloczynie kartezjańskim.

Definicja 2.2.1

Relacją dwuargumentową w iloczynie kartezjańskim zbiorów A i B nazywamy

dowolny podzbiór zbioru A × B.

Jeśli A = B, to mówimy o relacji w zbiorze A.

Niech R ⊂ A × B będzie relacją dwuargumentową. Będziemy pisać aRb jeśli para (a, b) należy do

podzbioru R. Mówimy wówczas, że elementy a i b są ze sobą w relacji R.

Zbiór ∅ jako podzbiór zbioru A × B jest relacją, którą nazywamy relacją pustą. Relacja pusta

nie zachodzi między żadnymi dwoma elementami.

Relacje jako podzbiory iloczynu kartezjańskiego, a więc zbiory, można dodawać, odejmować i mno-

żyć w sensie teorii mnogości.

Definicja 2.2.2

Dziedziną relacji R nazywamy zbiór wszystkich poprzedników par należących do

D(R) = {a ∈ A : (a, b) ∈ R} = {a ∈ A : aRb}.

Przeciwdziedziną relacji R nazywamy zbiór wszystkich następników par należących do R,

D (R) = {b ∈ B : (a, b) ∈ R} = {b ∈ B : aRb}.

Definicja 2.2.3

Wykresem relacji R ⊂ A × B w kartezjańskim układzie współrzędnych nazywamy

zbiór punktów (a, b), których współrzędne są w relacji R, tj.

W(R) = {(a, b) : aRb}.

Niech R ⊆ X × Y będzie relacją i niech A ⊆ X, B ⊆ Y .

Definicja 2.2.4

Obrazem zbioru A wyznaczonym przez relację R nazywamy zbiór postaci

R(A) = {y ∈ Y :

x∈A

xRy}.

Przeciwobrazem zbioru B wyznaczonym przez relację R nazywamy zbiór postaci

−1

(B) = {x ∈ X :

y∈B

xRy}.

Definicja 2.2.5

Relacją odwrotną do relacji R ⊂ A × B nazywamy relację R

−1

⊂ B × A określoną

wzorem

−1

= {(b, a) ∈ B × A : aRb}.

Definicja 2.2.6

Niech R ⊆ A × B i S ⊆ C × D. Złożeniem relacji R z relacją S nazywamy relację

R ◦ S ⊆ A × D zdefiniowaną wzorem

R ◦ S = {(a, d) ∈ A × D :

b∈B∩C

(aRb ∧ bSd)}.

Twierdzenie 2.2.7

Niech R ⊆ A × B, S ⊆ C × D i T ⊆ E × F będą dowolnymi relacjami. Wtedy

(R ◦ S) ◦ T = R ◦ (S ◦ T ),

(R ◦ S)

−1

= S

−1

◦ R

−1

Definicja 2.2.8

Relację dwuargumentową R w zbiorze X nazywamy

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

(a)

zwrotną, jeśli

x∈X

xRx,

(b)

przeciwzwrotną, jeśli

x∈X

∼ (xRx),

(c)

symetryczną, jeśli

x,y∈X

xRy ⇒ yRx

(d)

przeciwsymetryczną, jeśli

x,y∈X

xRy ⇒∼ (yRx)

(e)

antysymetryczną, jeśli

x,y∈X

xRy ∧ yRx

⇒ x = y

(f )

przechodnią, jeśli

x,y,z∈X

xRy ∧ yRz

⇒ xRz

(g)

spójną, jeśli

x,y∈X

xRy ∨ yRx

Definicja 2.2.9

Jeśli relacja R ⊂ X × X jest zwrotna, przechodnia i symetryczna, to nazywamy ją

relacją równoważności w zbiorze X.

Definicja 2.2.10

Zbiór wszystkich elementów y ∈ X będących w relacji równoważności ≈⊂ X × X

z elementem x ∈ X nazywamy klasą abstrakcji lub klasą równoważności elementu x, tj.

[x] = {y ∈ X : y ≈ x}.

Zbiór wszystkich klas równoważności relacji ≈ w zbiorze X nazywamy zbiorem ilorazowym i ozna-
czamy X

≈

Twierdzenie 2.2.11 (Zasada abstrakcji)

Dowolna relacja równoważności ≈ w zbiorze X 6= ∅ wyznacza podział tego zbioru na rozłączne i
niepuste podzbiory, klasy abstrakcji, w taki sposób, że dwa elementy x, y zbioru X należą do tego
samego podzbioru wtedy i tylko wtedy, gdy x ≈ y.

Definicja 2.2.12

Jeśli relacja R ⊂ X ×X jest zwrotna, przechodnia i antysymetryczna, to nazywamy

ją relacją porządkującą zbiór X, a parę (X, R) nazywamy zbiorem częściowo uporządkowa-
nym.
Jeśli relacja porządkująca jest spójna, to parę (X, R) nazywamy zbiorem liniowo uporządkowa-
nym.

Jeśli ≺ jest relacją porządku i x ≺ y, to mówimy, że x poprzedza y i y następuje po x. Jeśli

x ≺ y lub y ≺ x, to mówimy, że elementy x i y są porównywalne. Oczywiście jeśli ≺ jest relacją
porządku częściowego, to nie każde dwa elementy są porównywalne.

Niech (X, ≺) będzie zbiorem częściowo uporządkowanym.

Definicja 2.2.13

Element x

∈ X nazywamy maksymalnym, jeśli nie poprzedza on żadnego ele-

mentu w zbiorze X, czyli nie istnieje element x ∈ X r {x

} taki, że x

≺ x, tj.

∼

x∈X

x 6= x

∧ x

≺ x

Element x

∈ X nazywamy minimalnym, jeśli nie poprzedza go żaden element w zbiorze X, czyli

nie istnieje element x ∈ X r {x

} taki, że x ≺ x

, tj.

∼

x∈X

x 6= x

∧ x ≺ x

2.2. RELACJE.

Element x

∈ X nazywamy największym jeśli

x∈X

x ≺ x

Element x

∈ X nazywamy najmniejszym jeśli

x∈X

≺ x.

W zbiorze uporządkowanym może istnieć jeden lub więcej elementów maksymalnych lub minimalnych,
jak również zbiór uporządkowany może nie posiadać takich elementów.

Niech A ⊂ X będzie podzbiorem zbioru częściowo uporządkowanego (X, ≺).

Definicja 2.2.14

Element x

∈ X nazywamy ograniczeniem dolnym zbioru A w zbiorze X, jeśli

dla każdego x ∈ A zachodzi zależność x

≺ x. Element x

∈ X nazywamy ograniczeniem górnym

zbioru A w zbiorze X, jeśli dla każdego x ∈ A zachodzi zależność x ≺ x

Zbiór ograniczeń dolnych zbioru A oznaczamy A

, a zbiór ograniczeń górnych A

Definicja 2.2.15

Jeśli zbiór ograniczeń dolnych A

ma element największy, to nazywamy, go kresem

dolnym zbioru A i oznaczamy inf A.
Jeśli zbiór ograniczeń górnych A

ma element najmniejszy, to nazywamy, go kresem górnym zbioru

A i oznaczamy sup A.

Kresy zbioru nie muszą być jego elementami.

Jeśli x

= sup A i x

∈ A, to piszemy x

= max A oraz jeśli x

= inf A i x

∈ A, to piszemy

= min A.

Elementy największy, najmniejszy, minimalny, maksymalny, ograniczenie górne, dolne i kresy na-

zywa się elementami wyróżnionymi.

Twierdzenie 2.2.16

Niech (X, ≺) będzie zbiorem częściowo uporządkowanym i niech A ⊆ X. Wtedy

W zbiorze A istnieje co najwyżej jeden element największy i co najwyżej jeden element najmniej-
szy.

Zbiór A ma co najwyżej jeden kres dolny i co najwyżej jeden kres górny.

Jeśli a ∈ A jest elementem największym w zbiorze A, to jest on

(a)

jedynym elementem maksymalnym w zbiorze A,

(b)

kresem górnym zbioru A.

Jeśli a ∈ A jest elementem najmniejszym w zbiorze A, to jest on

(a)

jedynym elementem minimalnym w zbiorze A,

(b)

kresem dolnym zbioru A.

Jeśli w zbiorze A istnieje dokładnie jeden element maksymalny, to jest on też elementem naj-
większym w A.

Jeśli w zbiorze A istnieje dokładnie jeden element minimalny, to jest on też elementem najmniej-
szym w A.

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

Oczywiście może się zdarzyć, że w zbiorze A tylko niektóre z elementów wyróżnionych. Jeśli w zbiorze
X istnieje ograniczenie dolne zbioru A, to mówimy, że zbiór A jest ograniczony z dołu, a jeśli
istnieje ograniczenie górne, to że jest on ograniczony z góry.

W zbiorze pustym nie ma elementów minimalnych i maksymalnych (tym samym nie ma elementu

najmniejszego i największego). Natomiast każdy element zbioru X jest zarówno ograniczeniem górnym
i dolnym podzbioru pustego zbioru X. Zatem, gdy X 6= ∅, zbiór pusty jest zbiorem ograniczonym z
góry i z dołu.

Czasami wygodnie jest przedstawić relację porządku częściowego w zbiorze skończonym w sposób

graficzny za pomocą diagramu Hassego. Diagram ten rysuje sie na płaszczyźnie R

w następujący

sposób:

• Elementy zbioru X przedstawia się za pomocą punktów,

• Jeśli x ≺ y, to punkt odpowiadający elementowi y jest powyżej punktu przypisanemu elementowi

• Łączymy odcinkiem punkt x z punktem y, jeśli x ≺ y oraz nie istnieje z ∈ X, taki że x ≺ z ≺ y.

Przykład 2.2.17

W zbiorze X = {1, 2, 3, 4, 5, 6, 7, 8} rozważmy relację % zdefiniowaną w następujący

sposób

x%y ⇔ y jest dzielnikiem x.

Relację tę jako podzbiór iloczynu kartezjańskiego X × X możemy zapisać w postaci

{(1, 1), (2, 1), (2, 2), (3, 1), (3, 3), (4, 1), (4, 2), (4, 4), (5, 1), (5, 5),

(6, 1), (6, 2), (6, 3), (6, 6), (7, 1), (7, 7), (8, 1), (8, 2), (8, 4), (8, 8)}

Zauważmy, że relacja % ma następujące własności

1) jest zwrotna, gdyż każda liczba jest swoim własnym dzielnikiem,

2) jest antysymetryczna, bowiem jeśli dowolne x, y ∈ X spełniają poprzednik implikacji występu-

jącej po kwantyfikatorze ogólnym w definicji 2.2.8(e), to

k∈Z

x = k · y, ∧

l∈Z

y = l · x.

Stąd mamy, że x = k · (l · x). A to oznacza, że k · l = 1. Ale k, l ∈ Z, więc k i l muszą być równe
1. Zatem x = y.

3) jest przechodnia, bowiem jeśli x, y, z ∈ X spełniają poprzednik implikacji z definicji 2.2.8(f), to

k∈Z

x = k · y, ∧

l∈Z

y = l · z.

Stąd x = k · (l · z). Zatem z łączności mnożenia wynika, że z jest dzielnikiem x.

Tym samym pokazaliśmy, że relacja % jest relacją porządku częściowego w zbiorze X. Ponieważ 5 i 3
nie są ze sobą w relacji, to % nie jest relacją porządku liniowego. Poniższy diagram ilustruje relację %.

2.2. RELACJE.

Zauważmy, że elementem maksymalnym w zbiorze X, uporządkowanym przez relację %, jest 1.

Istotnie jest to element, dla którego w zbiorze X nie istnieje element, który jest różny od 1 i z którym
1 byłby w relacji (który by następował po 1, bo w zbiorze X nie ma dzielników 1 różnych od 1).
Ponieważ w X istnieje tylko jeden element maksymalny, to w myśl twierdzenia 2.2.16 jest on również
elementem największym. Zauważmy również, że w zbiorze X nie ma elementów różnych od 5, z którymi
element 5 byłyby w relacji (które poprzedzałby 5, bo 5 nie jest dzielnikiem żadnego elementu, różnego
od 5, zbioru X) . Oznacza to, że jest to element minimalny w zbiorze X. Ta sama sytuacja zachodzi
dla elementów 6, 7 i 8. Oznacza to, że w zbiorze X istnieją cztery elementy minimalne: 5, 6, 7 i 8
oraz, że zbiór X nie posiada elementu najmniejszego (nie ma elementu, który byłby w relacji % ze
wszystkimi elementami zbioru X; który byłby dzielnikiem każdego elementu zbioru X).

Na koniec rozważmy zbiór X jako podzbiór zbioru liczb naturalnych uporządkowanego tą samą

relacją % i wyznaczmy jego kresy. Kresem górnym jest oczywiście 1, bo jest to element największy
(porównaj twierdzenie 2.2.16). Aby wyznaczyć kres dolny wyznaczymy zbiór ograniczeń dolnych zbioru
X. Mamy X

= {1680, 3360, 5040, . . . }. Zatem inf X = 1680, bo jest to element największy zbioru

(1680 jest dzielnikiem wszystkich elementów zbioru X

, tzn. wszystkie elementy x

są w relacji z

1680). Oczywiście w tym przypadku wystarczyło wyznaczyć najmniejszą wspólną wielokrotność liczb
5, 6, 7, 8.

Uwaga 2.2.18

Uzasadniając, że relacja jest antysymetryczna braliśmy pod uwagę tylko elementy,

które spełniały poprzednik implikacji z definicji 2.2.8(e) mimo, iż występuje ona po kwantyfikatorze
ogólnym. Mogliśmy tak zrobić gdyż dla elementów, które poprzednika tej implikacji nie spełniają
jest ona prawdziwa z definicji 1.1.5 (jeśli poprzednik jest fałszywy, to implikacja jest prawdziwa bez
względu na wartość logiczną następnika).

Czasami relację przedstawia się za pomocą macierzy o elementach postaci

(

i nie jest w relacji z j

i jest w relacji z j.

Przykład 2.2.19

Wróćmy do przykładu 2.2.17. Niech pierwsza kolumna (i tym samym pierwszy

wiersz) macierzy odpowiada elementowi 1, druga - 2, trzecia 3, i.t.d. Mamy więc

































Zadanie 2.2.1

Dla podanych relacji wyznaczyć dziedzinę, przeciwdziedzinę, wykres i relację odwrot-

ną. Zbadać jakie własności mają podane relacje i ich relacje odwrotne.

R ⊆ X

, X = {x ∈ Z : 0 < |x| ¬ 4}, xRy ⇔ xy > 0,

R ⊆ N

, xRy ⇔ y = x + 1,

R ⊆ N

, xRy ⇔ y < 2x,

R ⊆ N

, xRy ⇔ y < x

R ⊆ N

, xRy ⇔ xy = 10,

f )

R ⊆ N

, xRy ⇔ |x| < |y|,

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

R ⊆ R

, xRy ⇔ x ¬ |y|,

R ⊆ N

, xRy ⇔ |x − y| = 1,

R ⊆ R

, xRy ⇔ |x + y| = 1,

R ⊆ Z

, xRy ⇔ 3

(x + y),

R ⊆ Z

, xRy ⇔ 2

(x − y),

R ⊆ R

× R

, (x

, y

)R(x

, y

) ⇔ x

= x

ł)

R ⊆ R

× R

, (x

, y

)R(x

, y

) ⇔ x

+ y

= x

+ y

Zadanie 2.2.2

W zbiorze X = {0, 1, 2, 3, 4} określone są relacje:

R = {(0, 1); (0, 2); (0, 3); (0, 4); (1, 2); (1, 3); (1, 4), (2, 3); (2, 4); (3, 4)}
S = {(0, 0); (1, 1); (2, 2); (3, 3); (4, 4); (1, 0); (1, 2); (1, 3); (1, 4); (2, 0); (2, 4); (3, 0); (4, 0)}.
Zbadać własności relacji R, S, R ∪ S, R ∩ S, R r S, S r R.

Zadanie 2.2.3

W zbiorze X = {1, 2, 3, 4, 5, 6} określone są relacje

xRy ⇔ x

xSy ⇔ y = x

Zbadać własności relacji R, S, R ∪ S, R ∩ S, R r S, S r R.

Zadanie 2.2.4

Jaka jest geometryczna interpretacja w prostokątnym układzie współrzędnych po-

szczególnych własności relacji.

Zadanie 2.2.5

Jeśli dwie liczby całkowite m i n mają te same reszty z dzielenia przez liczbę naturalną

p to mówimy, że są one przystające modulo p i piszemy m ≡

y. Liczbę p nazywamy modulnikiem.

Udowodnić, że liczby m i n są przystające modulo p wtedy i tylko wtedy, gdy różnica m − n jest
podzielna przez p, a następnie pokazać, że ≡

jest relacją równoważności. Wyznaczyć klasy abstrakcji

tej relacji.

Zadanie 2.2.6

W zbiorze potęgowym zbioru X = {1, 2, 3, 4} określono relację R wzorem

ARB ⇔ N (A) = N (B),

gdzie N (A) oznacza liczbę elementów w zbiorze A. Pokazać, że R jest relacją równoważności. Wyzna-
czyć klasy abstrakcji elementów {4}, {1, 2}, {2, 4, 3}.

Zadanie 2.2.7

W zbiorze R r {0} × R określono relację (a, b)R(c, d) ⇔ ac > 0. Pokazać, że R jest

relacją równoważności i wyznaczyć jej klasy abstrakcji.

Zadanie 2.2.8

W zbiorze N

określono relację (a, b)R(c, d) ⇔ a − b = c − d. Pokazać, że R jest relacją

równoważności i wyznaczyć klasę abstrakcji elementu (1, 1).

Zadanie 2.2.9

W zbiorze Z × Z r {0} określono relację (a, b)R(c, d) ⇔

. Pokazać, że R jest

relacją równoważności i wyznaczyć klasę abstrakcji elementu (1, 1).

Zadanie 2.2.10

Niech R i S będą relacjami równoważności odpowiednio na zbiorze X i Y . Niech

T ⊆ X × Y będzie relacją określoną następująco

, y

)T (x

, y

) ⇔ x

∧ y

Czy S jest relacja równoważności?

2.2. RELACJE.

Zadanie 2.2.11

Niech % będzie relacją zwrotną i przechodnią. Udowodnić, że relacja R zdefiniowana

wzorem xRy ⇔ x%y ∧ y%x jest relacją równoważności.

Zadanie 2.2.12

W zbiorze potęgowym zbioru X = {1, 2, 3} określono relację inkluzji. Pokazać, że

jest to relacja porządku. Czy jest to porządek liniowy? Wskazać elementy wyróżnione.

Zadanie 2.2.13

Wskazać elementy wyróżnione w zbiorze A = {2, 3, 4, 5, . . . , 11, 12} uporządkowanym

przez relację podzielności.

Zadanie 2.2.14

W zbiorze X = {1, 2, 3, 4, 5, 6, 7} zdefiniowano relację wzorem

x%y ⇔ 2

(x − y).

Pokazać, że jest to relacja równoważności. Wyznaczyć wszystkie klasy abstrakcji.

Zadanie 2.2.15

W zbiorze R

określono relację % w następujący sposób

(x, y)%(z, t) ⇔ x ¬ z ∧ y ¬ t.

(a)

Pokazać, że % jest relacją porządku.

(b)

Znaleźć elementy wyróżnione zbiorów

A = {(x, y) : x

+ y

¬ 1}, B = {(x, y) : |x| + |y| ¬ 1}.

Zadanie 2.2.16

Niech R i S będą relacjami porządku odpowiednio na zbiorach X i Y . Czy relacja T

zdefiniowana wzorem (x

, y

)T (x

, y

) ⇔ x

∧ y

też jest relacją porządku na zbiorze X × Y ?

Zadanie 2.2.17

Wyznaczyć kresy zbioru A ⊆ X, gdzie X jest zbiorem uporządkowanym przez relację

podzielności.

A = {12, 15}, X = {1, 4, 5, 12, 15, 16, 20}

A = {1, 5}, X = {1, 4, 5, 12, 15, 16, 20}

A = {18, 21, 36}, X = {3x : x ∈ N}

A = {3, 6, 12}, X = {3k : k ∈ N}

A = {7, 9, 11, 19, 23}, X = {2k − 1 : k ∈ N}

Zadanie 2.2.18

W zbiorze R

określamy relację porządku wzorem

, y

)R(x

, y

) ⇐⇒ x

¬ x

∧ y

¬ y

Wyznaczyć elementy wyróżnione oraz kresy zbiorów

A = {(1, 1), (1, 2), (2, 1), (3, 1), (3, 2)},

B = {(−1, 1), (0, −1), (1, 2), (3, 2), (2, 3)}.

Zadanie 2.2.19

W zbiorze N

określamy relację porządku wzorem

, y

)R(x

, y

) ⇐⇒ x

¬ x

∧ y

Wyznaczyć elementy wyróżnione oraz kresy zbiorów

A = {(2, 1), (1, 3), (1, 4), (1, 6)},

B = {(1, 2), (2, 1), (1, 4), (3, 2), (3, 8)}.

Zadanie 2.2.20

W zbiorze Z

określamy relację porządku wzorem

, y

)R(x

, y

) ⇐⇒ x

¬ x

∧ y

 y

Wyznaczyć elementy wyróżnione oraz kresy zbiorów

A = {(2, 1), (1, 4), (1, 6)},

B = {(1, 2), (2, 4), (1, 4), (3, 2)},

C = {(1, 2), (2, 1), (1, 4), (3, 8)}.

Zadanie 2.2.21

W zbiorze R

określamy relację porządku wzorem

, y

)R(x

, y

) ⇐⇒ x

∧ y

 y

Wyznaczyć elementy wyróżnione oraz kresy zbiorów

A = {(1, 2), (2, 1), (3, 1), (3, 2)},

B = {(1, 2), (3, 2), (3, 8)},

C = {(1, 2), (2, 1), (1, 4), (3, 2)}.

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

2.3.

Funkcje.

Niech X i Y będą dowolnymi zbiorami

Definicja 2.3.1

Funkcją odwzorowując ą zbiór X w zbiór Y nazywamy relację f ⊆ X × Y

spełniającą warunek: dla każdego każdego elementu x ∈ X istnieje dokładnie jeden element y ∈ Y ,
taki że x f y.

Jeśli x f y, to będziemy również pisać y = f (x). Dziedzinę funkcji f nazywa się również zbiorem
argumentów, a jej elementy x - argumentami. Przeciwdziedzinę funkcji f nazywa się również
zbiorem wartości funkcji, a jej elementy y - wartościami funkcji f . Dziedzinę funkcji oznaczać
będziemy przez D

, a przeciwdziedzinę przez

. Zauważmy, że jeśli X jest dziedziną funkcji f , to

przeciwdziedzina jest zbiorem postaci

= {y : y = f (x) ∧ x ∈ X}.

Warunek z definicji 2.3.1 można zastąpić dwoma następującymi warunkami:

x∈X

y∈Y

x f y,

x∈X

∈Y

(x f y

∧ x f y

) ⇒ y

= y

Podzbiór f iloczynu kartezjańskiego nie jest funkcją w dwóch przypadkach:

jeśli ma element nie będący parą uporządkowaną,

jeśli należą do niego co najmniej dwie pary uporządkowane o tym samym poprzedniku i różnych
następnikach.

Oczywiście zbiór pusty też jest funkcją, którą nazywa się funkcją pustą.

Definicja 2.3.2

Dwie funkcje f : A → Y i g : B → Y nazywamy równymi jeśli spełniają następujące

warunki

(i) A = B, (dziedziny funkcji są równe)

(ii)

x∈A

f (x) = g(x).(wartości funkcji odpowiadające tym samym argumentom są równe)

Definicja 2.3.3

Zawężeniem (obcięciem) funkcji f : X → Y do zbioru Z ⊆ X nazywamy funkcję

oznaczaną przez f

i spełniającą warunki

: Z → Y,

x∈Z

(x) = f (x)

Definicja 2.3.4

Rozszerzeniem funkcji g : B → Y do zbioru Z takiego, że B ⊆ Z nazywamy

każdą funkcję f : Z → Y , taką że

x∈B

f (x) = g(x).

Zauważmy, że rozszerzenie funkcji nie jest jednoznaczne. Jeśli rozważmy dwie funkcje f

: Z → Y i

: Z → Y takie, że

x∈ZrB

(x) 6= f

(x)

oraz

x∈B

(x) = g(x) ∧ f

(x) = g(x)

to obie te funkcje f

i f

możemy potraktować jako dwa różne rozszerzenia funkcji g do zbioru Z.

2.3. FUNKCJE.

PRZYKŁADY FUNKCJI

Funkcję I : X → X, I(x) = x nazywamy funkcją identycznościową na zbiorze X (identycz-
nością na X).

Niech X będzie dowolnym zbiorem. Dla dowolnego podzbioru A ⊆ X funkcję χ

: X → {0, 1}

określoną wzorem

(x) =

(

jeśli x ∈ A,

jeśli x /

∈ A

nazywamy funkcją charakterystyczną zbioru A

Funkcję, której dziedzina jest zbiorem liczb naturalnych nazywa się ciągiem. W szczególności
jeśli przeciwdziedzina jest zbiorem liczbowym ciąg nazywamy ciągiem liczbowym.

Funkcję określoną wzorem

sgn(x) =











−1,

x < 0

x = 0

x > 0.

nazywamy funkcją signum.

−1

Rysunek 2.1. f (x) = sng(x).

Funkcję zmiennej rzeczywistej, która przyjmuje wartość 1, gdy argument jest liczbą wymierną i
wartość 0, gdy argument jest liczbą niewymierną nazywamy funkcją Dirichleta

D(x) =

(

x /

∈ Q

x ∈ Q.

(2.23)

Funkcję całkowitoliczbową b · c : R → Z, która każdej liczbie rzeczywistej x przyporządkowuje
największą liczbę całkowitą nie większą od x nazywamy funkcją podłoga

bxc = max{k ∈ Z : k ¬ x}.

Funkcję całkowitoliczbową d · e : R → Z, która każdej liczbie rzeczywistej x przyporządkowuje
najmniejszą liczbę całkowitą nie mniejszą od x nazywamy funkcją sufit

dxe = min{k ∈ Z : k x}.

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

−3 −2 −1

−3

−2

−1

(a) f (x) = dxe

−

−3 −2 −1

−3

−2

−1

(b) f (x) = bxc

Rysunek 2.2. Wykresy funkcji sufit i podłoga.

Podstawowe własności funkcji podłogi i sufitu

x − 1 < bxc ¬ x ¬ dxe < x + 1,

b−xc = −dxe,

d−xe = −bxc,

bx + nc = bxc + n, n ∈ N,

dx + ne = dxe + n, n ∈ N.

Zadanie 2.3.1

Znaleźć liczbę całkowitą x spełniającą równanie

3x − 2

2x − 1

2x − 5

3x − 4

x − 1

11x − 2

x − 2

x − 4

2x − 1

x − 1

2x − 5

x − 3

f )

2x + 1

= x − 1,

x − 1

x + 1

3x + 1

= 2x − 1,

2x + 1

3x − 1

x + 1

x + 2

Definicja 2.3.5

Obrazem zbioru A przez funkcję f nazywamy zbiór wszystkich wartości f (x) dla

x ∈ A, tj.

f (A) = {y ∈ Y : y = f (x) ∧ x ∈ A}.

Niech A, B będą podzbiorami dziedziny funkcji f : X → Y .

2.3. FUNKCJE.

WŁASNOŚCI OBRAZU

f (∅) = ∅,

f (A) ⊆ Y ,

(A) = f (A) ∩ Z, Z ⊆ X,

A ⊆ B ⇒ f (A) ⊆ f (B),

f (A

∪ A

) = f (A

) ∪ f (A

f (A

∩ A

) ⊆ f (A

) ∩ f (A

f (A

− A

) ⊇ f (A

) − f (A

Definicja 2.3.6

Przeciwobrazem zbioru B przez funkcję f nazywamy zbiór wszystkich wartości x

takich, że f (x) ∈ B, tj.

−1

(B) = {x ∈ X : y = f (x) ∧ y ∈ B}.

Niech A, B będą podzbiorami przeciwdziedziny funkcji f : X → Y .

WŁASNOŚCI PRZECIWOBRAZU

−1

(∅) = ∅

−1

(B) ⊆ X,

−1

(A) = f

−1

(A) ∩ Z, Z ⊆ Y ,

A ⊆ B ⇒ f

−1

(A) ⊆ f

−1

(B),

−1

(A ∪ B) = f

−1

(A) ∪ f

−1

(B),

−1

(A ∩ B) = f

−1

(A) ∩ f

−1

(B),

−1

(A r B) = f

−1

(A) r f

−1

(B),

Definicja 2.3.7

Funkcję f : X → Y nazywamy

różnowartościową

, jeśli dla różnych argumentów

przyjmuje różne wartości, tzn.

∈X

6= x

⇒ f (x

) 6= f (x

)

Zauważmy, że z prawa kontrapozycji wynika, że jeśli funkcja jest różnowartościowa, to

∈X

f (x

) = f (x

) ⇒ x

= x

Definicja 2.3.8

Mówimy, że funkcja f : X → Y przekształca zbiór X na zbiór Y , jeśli Y = f (X).

Zadanie 2.3.2

Wyznaczyć obraz zbioru A przez funkcję f , jeśli

A = {2, 4, 6}, f (x) = x + (−1)

;

A = {1, 3, 5, 7}, f (x) = x + (−1)

;

A = h−2, 3), f (x) = −|3 − x|;

A = (−2, 5i, f (x) = −|3 − x|;

A = (0,

), f (x) = sin 3x;

A = h0, 2i, f (x) = |x − 1|;

f )

A = h−2, 3i, f (x) = −x

+ 4x − 1;

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

A = (0,

1
2

), f (x) =

(

x + 3,

dla x ¬

1
2

−2x + 2,

dla x >

1
2

;

A = h0,

1
2

i, f (x) =

+ 2 arc sin x;

Zadanie 2.3.3

Wyznaczyć przeciwobraz zbioru B przez funkcję f , jeśli

B = (−2, 4i, f (x) = x

− x − 2;

B = h2, 4) ∪ (

1
2

, 1), f (x) =

1
2

;

B = h2, 4) ∪ (

1
2

, 1), f (x) = 2

;

B = (−∞, 3i ∪ {0}, f (x) = −|3 − x|;

B = (−1, 0i, f (x) = sin 3x;

f )

B = f ((0, 2)), f (x) = |x − 1|;

B = f ((1, 2)), f (x) = x

+ 2x;

B = (0, 1) ∪ {2}, f (x) =

(

x + 3,

dla x ¬

1
2

−2x + 2,

dla x >

1
2

;

A = (0,

), f (x) =

+ 2 arc sin x;

Zadanie 2.3.4

Dana jest funkcja y = f (x), D

= h−5, ∞),

= h−2, ∞). f jest malejąca w przedzia-

le (−5, 1i i rosnąca w h1, ∞). Wyznaczyć obraz zbioru A = h0, 2i oraz przeciwobraz zbioru B = h−3, 3i.

2.4.

Zbiory przeliczalne i nieprzeliczalne.

Definicja 2.4.1

Mówimy, że zbiór A jest równoliczny ze zbiorem B i piszemy A ∼ B wtedy i tylko

wtedy, gdy istnieje funkcja f : A → B różnowartościowa przekształcająca zbiór A na zbiór B.

Przykład 2.4.2

Dwa przedziały domknięte ha, bi i hc, di są równoliczne. Wystarczy rozważyć funkcję

f : R → R określoną wzorem

f (x) =

d − c

b − a

x +

bc − ad

b − a

Przykład 2.4.3

Funkcja

f (x) =











1 + x

x ∈ (−1, 0i

1 − x

x ∈ (0, 1)

odwzorowuje przedział (−1, 1) na zbiór liczb rzeczywistych R oznacza to, że (−1, 1) ∼ R.

Jeśli A i B są zbiorami równolicznymi, to mówimy, że mają tę samą moc. Liczbę elementów zbio-
ru A, czyli moc zbioru A będziemy oznaczać |A|. Dla zbiorów skończonych jest to całkowita liczba
nieujemna. Przypadek zbiorów nieskończonych nie będzie omawiany w tym skrypcie. Pojęcia mocy
zbioru będziemy używać tylko dla porównywania liczby elementów dwóch zbiorów.

Definicja 2.4.4

Zbiór A nazywamy skończonym jeśli

A = ∅ i wtedy |A| = 0,

A ∼ {1, 2, 3, . . . , n} i wtedy |A| = n.

Zbiór, który nie jest skończony nazywa się nieskończonym.

2.4. ZBIORY PRZELICZALNE I NIEPRZELICZALNE.

Twierdzenie 2.4.5

Dla dowolnych zbiorów A, B i C zachodzą następujące zależności.

|A| = |A|,

|A| = |B| ⇒ |B| = |A|,

|A| = |B| ∧ |B| = |C|

⇒ |A| = |C|.

Powyższe twierdzenie orzeka, że równoliczność zbiorów jest relacją równoważności na zbiorze potęgo-
wym przestrzeni X.

Zauważmy, że zbiór skończony nie jest równoliczny z żadnym ze swoich podzbiorów właściwych.

Natomiast zbiór nieskończony jest równoliczny z pewnym swoim podzbiorem właściwym.

Przykład 2.4.6

Zbiór liczb naturalnych jest równoliczny ze zbiorem liczb nieparzystych lub ze zbio-

rem liczb podzielnych przez trzy. Istotnie w obu tych przypadkach możemy znaleźć różnowartościową
funkcję odwzorowującą zbiór liczb naturalnych na jeden z wymienionych zbiorów. W przypadku zbioru
liczb nieparzystych taką funkcją jest f (x) = 2x + 1, x ∈ N, zaś w przypadku zbioru liczb podzielnych
przez trzy, taką funkcja jest f (x) = 3x, x ∈ N.

Z powyższego przykładu wynika, że zbiór liczb naturalnych jest nieskończony.

Definicja 2.4.7

Zbiór Z nazywamy zbiorem przeliczalnym jeśli jest on skończony lub równoliczny

ze zbiorem liczb naturalnych.

Niepusty zbiór jest przeliczalny wtedy i tylko wtedy, gdy jego elementy można ustawić w ciąg skończony
lub nieskończony.

Definicja 2.4.8

Niepusty zbiór Z, który nie jest przeliczalny nazywamy zbiorem nieprzeliczalnym.

Przykład 2.4.9

Zbiór liczb rzeczywistych i zbiór liczb niewymiernych są zbiorami nieprzeliczalnymi.

Przykład 2.4.10

Zbiór liczb wymiernych jest zbiorem przeliczalnym. Aby ten fakt udowodnić wy-

starczy liczby wymierne umieścić w tablicy, a następnie ustawić je w ciąg w kolejności wskazanej przez
strzałki

1
1

1
2

→

1
3

1
4

→

1
5

1
6

→

1
7

· · ·

↓

2
1

2
2

2
3

2
4

2
5

2
6

2
7

· · ·

3
1

3
2

3
3

3
4

3
5

3
6

3
7

· · ·

↓

4
1

4
2

4
3

4
4

4
5

4
6

4
7

· · ·

5
1

5
2

5
3

5
4

5
5

5
6

5
7

· · ·

↓

6
1

6
2

6
3

6
4

6
5

6
6

6
7

· · ·

Przykład 2.4.11

Zbiór liczb całkowitych jest również zbiorem przeliczalnym, gdyż elementy tego

zbioru można ustawić w następujący ciąg

0, 1, −1, 2, −2, 3, −3, . . . .

Jeśli zbiory A i B są przeliczalne, to A ∪ B i A × B też są przeliczalne.

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

2.5.

Zbiory skończone

Zbiory skończone zostały zdefiniowane w poprzednim paragrafie. W tym paragrafie omówimy kilka ich
własności.

Stwierdzenie 2.5.1

Jeśli A ⊆ B i A, B są skończone, to |A| ¬ |B|.

Twierdzenie 2.5.2

Jeśli zbiory A i B są rozłączne i skończone, to | A ∪ B |=| A | + | B | .

Twierdzenie 2.5.3 Prawo różnicy.

Dla dowolnych zbiorów skończonych A i B mamy | A − B |=| A | − | A ∩ B | .

Twierdzenie 2.5.4 Prawo sumy.

Dla dowolnych zbiorów skończonych A i B mamy | A ∪ B |=| A | + | B | − | A ∩ B | .

Ćwiczenie 2.5.5

Ile liczb naturalnych mniejszych od 1000 dzieli się przez 3 lub 5?

Twierdzenie 2.5.6 Prawo iloczynu.

Dla dowolnych zbiorów skończonych A

, A

, . . . , A

mamy

| A

× A

× · · · × A

|=| A

| · | A

| · · · · · | A

Ogólniej, załóżmy, że mamy zbiór ciągów (s

, s

, . . . , s

) długości n o następującej strukturze. Jest

możliwości wyboru pierwszego elementu s

. Dla każdego ustalonego s

jest n

różnych możliwości

wyboru drugiego elementu s

, dla ustalonych s

i s

mamy n

możliwości wyboru s

, itd. Dla danego

j mając s

, s

, . . . , s

j−1

możemy wybrać s

na n

różnych sposobów. Wtedy zbiór ciągów o wyżej

opisanej strukturze składa się z n

· n

. . . n

elementów.

Niech dany będzie pewien zbiór Z.

Definicja 2.5.7

Zbiorem potęgowym zbioru Z nazywamy zbiór wszystkich podzbiorów zbioru Z

i oznaczamy P(Z).

Definicja 2.5.8

Alfabetem nazywamy skończony niepusty zbiór Σ, którego elementami są symbole,

nazywane literami.

Słowem długości n alfabetu Σ nazywamy dowolny n-elementowy ciąg liter tego alfabetu. Słowo,

które nie zawiera żadnej litery alfabetu Σ (ciąg pusty) nazywa się słowem pustym i oznacza ε.

Definicja 2.5.9

Językiem Σ

∗

nad alfabetem Σ nazywamy zbiór wszystkich słów zbudowanych z

liter tego alfabetu.

Przykład 2.5.10

Jeśli Σ = {0, 1}, to

∗

= {ε, 0, 1, 00, 11, 01, 10, 000, 001, 010, 100,

110, 011, 101, 111, . . . }.

Przykład 2.5.11

Zbiór A tych słów, które zaczynają się od litery 1 jest zbiorem rozwinięć dwójko-

wych liczb całkowitych dodatnich, tj.

A = {1, 10, 11, 100, 101, 110, 111, . . . }

Ćwiczenie 2.5.12

Niech dany będzie alfabet Σ = {a, b, c, d, e}. Obliczyć liczbę słów w języku Σ

∗

o długości 3 w przypadku,

gdy litery w słowie mogą się powtarzać oraz gdy słowo nie może składać się z tych samych liter.

Niech S = {1, 2, . . . , n}.

2.5. ZBIORY SKOŃCZONE

Twierdzenie 2.5.13 Zasada włączeń i wyłączeń.

Dla dowolnych zbiorów skończonych A

, A

, . . . , A

mamy

[

i=1

| =

I∈P(S)

(−1)

|I|+1

i∈I

Zadanie 2.5.1

Wypisać elementy zbioru P(S), gdy

a) S = {∅, a},

b) S = {a, b, c},

c) S = {{a, b}, b}.

Zadanie 2.5.2

Wypisać pięć elementów zbioru Σ

∗

, gdy

a) Σ = {a},

b) Σ = {a, b, c},

c) Σ = {ab, b}.

Zadanie 2.5.3

Ile liczb naturalnych mniejszych od 1000 dzieli się przez 3, 5 lub 7?

Zadanie 2.5.4

Wśród 100 studentów 50 uczy się francuskiego, 40 angielskiego, a 20 obu tych języków.

Ilu studentów nie uczy się ani angielskiego, ani francuskiego?

Zadanie 2.5.5

W trzydziestoosobowej grupie studenckiej dwudziestu studentów uczy się angielskie-

go, 14 niemieckiego, a 10 francuskiego. Jeśli żaden z nich nie uczy się wszystkich trzech języków, a 8
nie uczy się ani jednego, to ilu studentów tej grupy uczy się niemieckiego i francuskiego?

Zadanie 2.5.6

Wśród 200 studentów pierwszego roku informatyki po 80 studentów zapisało się na

dodatkowe wykłady z analizy, algebry i matematyki dyskretnej. Co więcej, na każde dwa z tych
wykładów zapisało się po 30 studentów, a na wszystkie trzy 15 studentów. Ilu studentów zapisało się
tylko na matematykę dyskretną?

Zadanie 2.5.7

Na pierwszym roku informatyki jest 140 studentów. Część z nich zapisała się na brydża

i tenis stołowy, przy czym na brydża zapisało się dwa razy więcej studentów niż na tenisa. Studentów,
którzy nie wybrali się na żaden z tych sportów jest o 35 więcej niż tych co chodzą na oba kursy.
Ponadto 65 studentów uczęszcza na co najmniej jeden kurs. Ilu studentów chodzi na brydża, a ilu na
tenis stołowy?

Zadanie 2.5.8

Ile liczb naturalnych nie większych niż 1000 nie dzieli się ani przez 3, ani przez 7, ani

przez 11?

Zadanie 2.5.9

Wśród 200 osób, 150 uprawia pływanie lub jazdę na rowerze, lub i jedno, i drugie.

Jeśli 85 osób uprawia tylko pływanie, a 60 pływanie i jazdę na rowerze, to ile uprawia tylko jazdę na
rowerze?

Zadanie 2.5.10

W grupie 60 osób, 34 zna język niemiecki, a 30 francuski. Ponadto francuski i nie-

miecki zna 15 osób, niemiecki i angielski 12, a angielski i francuski 14. Ile osób zna język angielski
jeżeli każda z osób zna co najmniej jeden język, a wszystkie trzy języki zna 5 osób?

Zadanie 2.5.11

W pewnej stuosobowej grupie czterdzieści osób było w Paryżu, pięćdziesiąt w Lon-

dynie i pięćdziesiąt w Rzymie. Ponadto dziesięć osób było w Paryżu i Londynie, piętnaście w Rzymie
i Paryżu, a dwadzieścia w Londynie i Rzymie. Ile osób z tej grupy odwiedziło wszystkie wymienione
trzy miasta, jeśli wiadomo, że każda osoba odwiedziła co najmniej jedno z miast.

Zadanie 2.5.12

40-osobowej

grupie

hazardzistów,

osób

gra

nałogowo

pokera,

21 osób - w ruletkę, a 6 - w ruletkę i pokera. Ile osób w tej grupie nie gra nałogowo, ani w poke-
ra, ani w ruletkę?

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

Zadanie 2.5.13

W 38-osobowej grupie muzyków, 20 osób gra na saksofonie, 21 osób gra na forte-

pianie, zaś 11 osób gra na obu tych instrumentach. Ilu muzyków nie gra ani na fortepianie, ani na
saksofonie?

Zadanie 2.5.14

Wśród 150 studentów pierwszego roku informatyki zaliczenie z algebry uzyskało tyle

samo osób co z logiki, a z logiki tyle samo osób co z matematyki dyskretnej. Ponadto 45 osób uzyskało
zaliczenie z algebry i logiki, 34 osoby z logiki i matematyki dyskretnej oraz 38 osób z matematyki
dyskretnej i z algebry. Ilu studentów ma zaliczenie z matematyki dyskretnej jeżeli wiadomo, że każdy
student uzyskał zaliczenie z co najmniej jednego przedmiotu.

Zadanie 2.5.15

W pewnej stuosobowej grupie czterdzieści osób było w Paryżu, pięćdziesiąt w Lon-

dynie i trzydzieści w Rzymie. Ponadto dziesięć osób było w Paryżu i Londynie, piętnaście w Rzymie
i Paryżu, a dwadzieścia w Londynie i Rzymie. Ile osób z tej grupy odwiedziło wszystkie wymienione
trzy miasta, jeśli wiadomo, że każda osoba odwiedziła co najmniej jedno z miast.

Zadanie 2.5.16

Wśród 150 studentów pierwszego roku informatyki po sześćdziesięciu studentów za-

pisało się na lektorat z języka angielskiego, niemieckiego oraz francuskiego. Co więcej na każde dwa z
tych lektoratów zapisało się po dwudziestu studentów, a na wszystkie trzy - dziesięciu. Ilu studentów
zapisało się tylko na język francuski?

ROZWIĄZANIA I ODPOWIEDZI

2.2.4

Jeśli w prostokątnym układzie prostokątnym zaznaczymy elementy należące do relacji R, to
otrzymany zbiór R w zależności od własności relacji będzie miał następujące własności

relacja

geometryczna własność zbioru

zwrotna

prosta y = x jest zawarta w zbiorze R

przeciwzwrotna

prosta y = x nie ma punktów wspólnych ze zbiorem R

symetryczna

zbiór R jest symetryczny względem prostej y = x

przeciwsymetryczna

zbiór R nie ma punktów symetrycznych względem prostej y = x

antysymetryczna

jedynymi punktami symetrycznymi względem prostej y = x są punkty
leżące na tej prostej

spójna

suma mnogościowa zbioru R, prostej y = x i figury symetrycznej
do zbioru R względem y = x jest całą płaszczyzną

przechodnia

dowolny prostokąt o bokach równoległych do osi układu, którego jeden
wierzchołek leży na prostej y = x i dwa sąsiednie wierzchołki należą ,
do zbioru R ma czwarty wierzchołek w zbiorze R

2.2.6

{4}

{1}, {2}, {3}, {4}

{1, 2}

{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}

{2, 4, 3}

{1, 2, 3}, {1, 3, 4}, {1, 2, 4}, {2, 3, 4}

2.2.7

jeśli c > 0, to [(c, d)] = {(a, b) : a > 0}, jeśli c < 0, to c > 0, to [(c, d)] = {(a, b) : a < 0}

2.2.8

[(1, 1)] = {(a, a) : a ∈ N}

2.2.9

[(1, 1)] = {(a, a) : a ∈ Z r {0}},

2.2.10

TAK

2.2.12

Tak, element największy: {1, 2, 3}, element najmniejszy: ∅

2.2.13

elementy maksymalne: 7, 8, 9, 10, 11, 12, elementy minimalne: 3, 2, 5, 7, 11

2.2.14

elementy maksymalne: 7 i 6, elementy minimalne: 1, 2

2.2.16

TAK

2.5. ZBIORY SKOŃCZONE

2.2.17 (a)

sup A-brak, inf A = 1;

(b)

sup A = 5, inf A = 1;

(c)

sup A = 252, inf A = 3;

(d)

sup A = 12,

inf A = 3;

(e)

sup A = 302841, inf A = 1

2.2.18

element najmniejszy w zbiorze A: (1, 1), element największy w zbiorze A: (3, 2), sup A = (3, 2),
inf A = (1, 1), elementy minimalne w zbiorze B: (−1, 1), (0, −1), elementy maksymalne w zbiorze
B: (3, 2), (2, 3), sup B = (3, 3), inf B = (−1, −1),

2.2.19

elementy minimalne w zbiorze A: (1, 3), (1, 4), (2, 1) elementy maksymalne w zbiorze A: (1, 6),
(2, 1), (4, 1), sup A = (2, 12), inf A = (1, 1), elementy minimalne w zbiorze B: (1, 2), (2, 1),
element największy w zbiorze B: (3, 8), sup B = (3, 8), inf B = (1, 1)

2.3.1 a)

x = 3,

x = 0,

x ∈ ∅,

x ∈ {−3, −1, 1},

f )

x ∈ {−1, 1, 3, 5, 7},

x = −1,

x = 1,

x = 1 ∨ x = 3,

x ∈ ∅,

x = 1

2.5.3

542

2.5.4

2.5.5

2.5.8

520

2.5.9

2.5.10

2.5.11

2.5.12

2.5.13

ROZDZIAŁ 2. ZBIORY, RELACJE I FUNKCJE.

Rozdział 3

Kombinatoryka.

3.1.

Podstawowe pojęcia kombinatoryczne.

Niech dany będzie n elementowy zbiór A i liczba naturalna k ¬ n.

Definicja 3.1.1

k-elementową wariacją bez powtórzeń ze zbioru n-elementowego A nazy-

wamy każdy uporządkowany zbiór utworzony z k różnych elementów zbioru A.

Twierdzenie 3.1.2

Istnieje

(n−k)!

różnych k-elementowych wariacji bez powtórzeń ze zbioru n ele-

mentowego.

Definicja 3.1.3

k-elementową wariacją z powtórzeniami ze zbioru n elementowego A nazy-

wamy każdy uporządkowany zbiór utworzony z k różnych lub nie różniących się między sobą elementów
zbioru A.

Twierdzenie 3.1.4

Istnieje n

różnych k-elementowych wariacji z powtórzeniami ze zbioru n ele-

mentowego.

Definicja 3.1.5

n-elementową wariację bez powtórzeń ze zbioru n elementowego nazywa-

my permutacją bez powtórzeń zbioru n-elementowego.

Twierdzenie 3.1.6

Istnieje n! różnych permutacji bez powtórzeń zbioru n-elementowego.

Definicja 3.1.7

Zbiór złożony z n elementów uporządkowanych, wśród których pewne elementy po-

wtarzają się odpowiednio k

, k

, . . . , k

razy, gdzie k

+ k

+ · · · + k

= n, nazywamy permutacją z

powtórzeniami.

Twierdzenie 3.1.8

Istnieje

!...k

różnych permutacji z powtórzeniami.

Definicja 3.1.9

k-elementową kombinacją bez powtórzeń ze zbioru n elementowego A na-

zywamy każdy podzbiór utworzony z k różnych elementów zbioru A.

Twierdzenie 3.1.10

Istnieje

n
k

różnych k-elementowych kombinacji bez powtórzeń ze zbioru n ele-

mentowego.

Definicja 3.1.11

k-elementową kombinacją z powtórzeniami ze zbioru n elementowego A

nazywamy podzbiór utworzony z k różnych lub nie różniących się między sobą elementów zbioru A.

Twierdzenie 3.1.12

Istnieje

n+k−1

n−1

różnych k-elementowych kombinacji z powtórzeniami ze zbioru

n elementowego.

Twierdzenie 3.1.13 Zasada rozmieszczania przedmiotów w pudełkach.

k identycznych przedmiotów można rozmieścić w n rozróżnialnych pudełkach na

n+k−1

n−1

sposobów.

ROZDZIAŁ 3.

KOMBINATORYKA.

Twierdzenie 3.1.14

Liczba sposobów wyboru k przedmiotów n rozróżnialnych typów, przy założeniu,

że dopuszczalne są powtórzenia równa jest

n+k−1

n−1

Niech dane będą skończone zbiory A i B oraz funkcja f : A → B.

Twierdzenie 3.1.15 Lemat o zliczaniu.

Jeśli wszystkie zbiory postaci f

−1

(b) = {a ∈ A : f (a) = b} dla wszystkich b ∈ B mają tyle samo

elementów, | f

−1

(b) |= r, to

| B |=

| A |

Definicja 3.1.16

Podziałem uporządkowanym zbioru S nazywamy ciąg (A

, A

, . . . , A

), któ-

rego elementy są parami rozłącznymi podzbiorami zbioru S takimi, że A

∪ A

∪ · · · ∪ A

= S. Ważna

jest tu tylko kolejność w jakiej występują zbiory A

Twierdzenie 3.1.17

Jeśli dany zbiór A ma n elementów i n

+ n

+ · · · + n

= n, to istnieje

n − n

− n

· · · · ·

n − n

− · · · − n

k−1

! · n

! · · · · · n

podziałów uporządkowanych (A

, A

, . . . , A

) zbioru A takich, że | A

|= n

dla i = 1, 2, . . . , k.

Zadanie 3.1.1

W pudełku znajdują się trzy kule o numerach 1, 2, 3.

Losujemy kolejno 3 kule i tworzymy z ich numerów liczby trzycyfrowe w kolejności losowania.
Ile liczb można utworzyć w ten sposób ?

Do pudełka wkładamy obie ręce i jednocześnie wyjmujemy dwie kule. Ile jest możliwych takich
losowań?

Z pudełka losujemy kolejno dwie kule i z ich numerów tworzymy liczby dwucyfrowe. Ile można
utworzyć takich liczb?

Z pudełka losujemy kulę zapisujemy jej numer i wkładamy ją z powrotem do pudełka. Następnie
losujemy drugą kulę i zapisujemy jej numer. Ile można w ten sposób utworzyć liczb dwucyfro-
wych?

Zadanie 3.1.2

Ile różnych wyników można otrzymać przy rzucaniu dwoma kostkami, jeśli

kostki są rozróżnialne;

kostki są nierozróżnialne;

rozróżniamy wyniki w zależności od sumy wyrzuconych oczek.

Zadanie 3.1.3

Na ile sposobów można rozmieścić trzy przedmioty w dwóch pudełkach, jeżeli

przedmioty i pudełka są rozróżnialne;

przedmioty są rozróżnialne, a pudełka są nierozróżnialne;

pudełka są rozróżnialne, a przedmioty nierozróżnialne;

przedmioty i pudełka są nierozróżnialne.

Narysuj możliwe przypadki.

Zadanie 3.1.4

Na ile sposobów można rozmieścić dwa przedmioty w trzech pudełkach, jeżeli

przedmioty i pudełka są rozróżnialne;

3.1. PODSTAWOWE POJĘCIA KOMBINATORYCZNE.

przedmioty są rozróżnialne, a pudełka są nierozróżnialne;

pudełka są rozróżnialne, a przedmioty nierozróżnialne;

przedmioty i pudełka są nierozróżnialne.

Narysuj możliwe przypadki.

Zadanie 3.1.5

Urna zawiera n kul ponumerowanych liczbami 1, 2, . . . , n. Wyjmujemy kolejno po

jednej kuli zapisując jej numer. Otrzymany rezultat nazywamy próbką o liczebności k z n elementów.
Jeśli po każdym ciągnieniu zwracamy wyciągniętą kulę, to mówimy, że próbka jest ze zwracaniem, jeśli
nie, to bez zwracania. Jeśli kolejność zapisywanych numerów kul ma znaczenie, to mówimy, że próbka
jest uporządkowana, w przeciwnym razie nieuporządkowana. Obliczyć ilość wszystkich rozróżnialnych
próbek

nieuporządkowanych bez zwracania,

nieuporządkowanych ze zwracaniem,

uporządkowanych bez zwracania,

uporządkowanych ze zwracaniem,

uporządkowanych bez zwracania, gdy k = n.

Zadanie 3.1.6

Rozmieszczono k kul w n szufladach, przy czym k ¬ n. Obliczyć ilość możliwych

sposobów rozmieszczania, jeśli

kule są nierozróżnialne, a szuflady są rozróżnialne i każda z szuflad może zawierać co najwyżej
jedną kulę,

kule są nierozróżnialne, a szuflady są rozróżnialne i nie ma ograniczenia na liczbę kul, które mogą
być w szufladach,

kule i szuflady są rozróżnialne i nie ma ograniczenia na liczbę kul, które mogą być w szufladach,

kule i szuflady są rozróżnialne i każda z szuflad może zawierać co najwyżej jedną kulę.

Zadanie 3.1.7

W pudełku mamy sześć kul, przy czym dwie są oznaczone numerem 1, jedna jest

oznaczona numerem 2 i trzy są oznaczone numerem 3. Losujemy kolejno sześć kul bez zwracania i
notujemy ich numery w kolejności losowania. Ile różnych liczb możemy otrzymać w ten sposób?

Zadanie 3.1.8

W n różnych komórkach rozmieszczono k rozróżnialnych cząstek b

, b

, . . . , b

, przy

czym k ¬ n oraz każda komórka może zawierać nie więcej niż jedną cząstkę. Obliczyć liczbę wszystkich
sposobów rozmieszczania, przy których:

w komórce a

znajduje się cząstka b

;

w komórkach a

i a

znajdują się odpowiednio cząstki b

i b

;

w komórkach a

i a

znajdują się cząstki b

i b

Zadanie 3.1.9

Ile istnieje różnych rozmieszczeń n ponumerowanych kul w n ponumerowanych pu-

dełkach, jeśli

żadne pudełko nie jest puste;

co najmniej jedno pudełko jest puste;

dokładnie jedno pudełko jest puste.

ROZDZIAŁ 3.

KOMBINATORYKA.

Zadanie 3.1.10

Podczas zawodów lekkoatletycznych w biegu na 100 m startowało k zawodników. Ile

było możliwych wyników ukończenia biegu jeżeli:

wszyscy zawodnicy ukończyli bieg;

jeden z zawodników nie ukończył biegu i jego nazwisko jest nieznane;

jeden z zawodników nie ukończył biegu i jego nazwisko jest znane.

Zakładamy, że zawodnicy nie dzielą miejsc ex aequo.

Zadanie 3.1.11

W biegu na 100 m uczestniczyło ośmiu zawodników. Ile jest możliwych wyników

ukończenia biegu, jeżeli sędziowie punktują tylko sześć pierwszych miejsc i zawodnicy nie dzielą miejsc
ex aequo.

Zadanie 3.1.12

Iloma sposobami można posadzić na pięciu krzesłach:

pięć osób;

trzy osoby.

Zadanie 3.1.13

Na parterze dziesięciopiętrowego budynku do windy wsiadło siedem osób. Na ile

sposobów osoby te mogą opuścić windę. Czy ilość możliwych opuszczeń windy ulegnie zmianie, jeśli
założymy, że każda osoba wysiada na innym piętrze?

Zadanie 3.1.14

W pudełku znajduje się siedem kul ponumerowanych od 1 do 7. Losujemy trzy

kule bez zwracania i notujemy ich numery. Ile jest możliwych wyników losowania, w których suma
wylosowanych numerów jest liczbą

nieparzystą;

parzystą?

Zadanie 3.1.15

W szufladzie znajduje się 20 śrub w tym 3 wadliwe. Losujemy bez zwracania pięć

śrub. Ile istnieje sposobów wylosowania jednej śruby wadliwej?

Zadanie 3.1.16

Problem sekwencjonowania RNA polega na odtworzeniu sekwencji nukleotydów, w

badanym łańcuchu. Załóżmy, że interesuje nas struktura fragmentu łańcucha RNA, o którym wiemy,
że składa sie on z dziesięciu nukleotydów. Wiemy ponadto, że w łańcuchu występuje czterokrotnie
adenina, trzykrotnie guanina, dwukrotnie cytozyna i raz uracyl. Dodatkowo wiemy, że na początku
łańcucha znajduje się guanina. Ile jest wszystkich różnych łańcuchów RNA? Odpowiedź uzasadnij.

Zadanie 3.1.17

Na ile sposobów można wybrać dziesięć monet mając nieograniczony zapas groszy

oraz pięcio-, dziesięcio- i pięćdziesięciogroszówek?

Zadanie 3.1.18

Dwanaście identycznych listów ma zostać wrzuconych do czterech różnych skrzynek

pocztowych.

Na ile sposobów można to zrobić?

Ile jest możliwych sposobów, jeśli do każdej ze skrzynek muszą trafić co najmniej dwa listy?

Zadanie 3.1.19

Na ile sposobów można rozmieścić 14 przedmiotów w 3 pudełkach tak, aby w jednym

z pudełek znalazło się co najmniej 8 przedmiotów?

Zadanie 3.1.20

Na ile sposobów można rozmieścić 14 przedmiotów w 3 pudełkach, tak aby w żadnym

z pudełek nie znalazło się więcej niż 7 przedmiotów.

Zadanie 3.1.21

Na ile sposobów można wybrać 10 piłek spośród nieograniczonej liczby piłek czer-

wonych, niebieskich i zielonych, jeśli chcemy otrzymać

3.2. ZASADA SZUFLADKOWA DIRICHLETA

co najmniej 6 zielonych piłek?

co najwyżej 5 zielonych piłek?

Zadanie 3.1.22

Na ile sposobów można rozmieścić k kul w n ponumerowanych pudełkach jeśli k < n

oraz

kule są różnokolorowe,

wszystkie kule są białe.

Zadanie 3.1.23

Rozmieszczamy n przedmiotów w k pudełkach w taki sposób, że w każdym pudełku

może znaleźć się co najwyżej jeden przedmiot. Na ile sposobów można dokonać takiego rozmieszczenia
jeśli

pudełka i przedmioty są rozróżnialne,

pudełka i przedmioty są nierozróżnialne,

pudełka są nierozróżnialne, a przedmioty są rozróżnialne,

pudełka są rozróżnialne, a przedmioty są nierozróżnialne.

Zadanie 3.1.24

Rozmieszczamy k przedmiotów w n pudełkach w dowolny sposób. Na ile sposobów

można dokonać takiego rozmieszczenia jeśli

pudełka i przedmioty są rozróżnialne,

pudełka i przedmioty są nierozróżnialne,

pudełka są nierozróżnialne, a przedmioty są rozróżnialne,

pudełka są rozróżnialne, a przedmioty są nierozróżnialne.

3.2.

Zasada szufladkowa Dirichleta

Twierdzenie 3.2.1 Zasada szufladkowa Dirichleta.

Jeśli zbiór n-elementowy podzielimy na k rozłącznych podzbiorów, to wśród tych podzbiorów istnieje
zbiór zawierający co najmniej

n
k

elementów oraz zbiór zawierający co najwyżej

n
k

elementów.

Dowód.

(nie wprost) Załóżmy, że każdy z podzbiorów ma mniej niż

n
k

elementów, czyli że ma co

najwyżej

n
k

− 1 elementów. Zatem

n = |S| = |A

| + |A

| + . . . |A

| ¬

− 1

k = k

− k.

Stąd

+ 1,

co jest sprzeczne z własnościami funkcji sufit (dxe < x + 1).

Załóżmy, teraz, że każdy podzbiór ma więcej niż

n
k

elementów, czyli że ma co najmniej

n
k

+ 1

elementów. Wtedy

n = |S| 

+ 1

Stąd

− 1,

co przeczy jednej z własności funkcji podłoga (bxc > x − 1).

ROZDZIAŁ 3.

KOMBINATORYKA.

Zadanie 3.2.1

Worek zawiera 50 szklanych kulek w czterech różnych kolorach. Uzasadnić, że jest w

nim co najmniej 13 kulek tego samego koloru. Ponadto wyjaśnić że jeśli jest w worku dokładnie 8
czerwonych kulek, to co najmniej 14 kulek musi być tego samego koloru.

Zadanie 3.2.2

Przypuśćmy, że 73 kule rozmieszczono w 8 szufladach.

Wykazać, że jedna z szuflad zawiera co najmniej 10 kul.

Wykazać, że jeśli dwie szuflady są puste, to jakaś szuflada zawiera co najmniej 13 kul.

Zadanie 3.2.3

83 jabłka zostały umieszczone w 9 skrzynkach. Wykazać, że

jedna ze skrzynek zawiera co najmniej 10 jabłek,

jeśli 2 skrzynki są puste, to któraś skrzynka zawiera co najmniej 12 jabłek.

Zadanie 3.2.4

W turnieju piłkarskim, w którym docelowo każda drużyna ma zagrać z każdą inną,

bierze udział n zespołów. Wykorzystując zasadę szufladkowa Dirichleta, uzasadnić, że w dowolnym
momencie trwania turnieju znajdą się dwie drużyny, które rozegrały do tego momentu tę samą liczbę
meczów.

Zadanie 3.2.5

Grupa 100 studentów zaliczyła sesję składająca się z trzech egzaminów, w których

możliwymi ocenami były 5.0, 4.5, 4.0, 3.5, 3.0. Wykazać wykorzystując zasadę szufladkową Dirichleta,
że co najmniej siedmiu studentów zaliczyło sesję z jednakowym wynikiem.

3.3.

Permutacja, cykle

Permutację zbioru n elementowego S możemy zdefiniować jako wzajemnie jednoznaczną funkcję π
zbioru S na siebie, π : S → S. Na przykład jeśli S = {a, b, c, d, e, f }, to jedną z permutacji tego zbioru
jest taka funkcja, że

π(a) = e,

π(b) = a,

π(c) = f,

π(d) = c,

π(e) = d,

π(f ) = b,

co możemy zapisać w postaci

(3.1)

Oto przykład innej permutacji

(3.2)

Jeśli w zbiorze S ustalimy kolejność elementów, to dowolną permutację tego zbioru możemy iden-

tyfikować z ciągiem. Zatem permutację (3.1) można zapisać w postaci (e, a, f, c, d, b), a permutację
(3.2) w postaci (b, a, f, e, c, d).

Definicja 3.3.1

Cyklem nazywamy każdą permutację postaci:

· · ·

k−1

k+1

k+2

· · ·

k+1

k+2

· · ·

Zazwyczaj, gdy operujemy na cyklach opuszczamy część:

k+1

k+2

· · ·

k+1

k+2

· · ·

gdyż nie wnosi ona

nic nowego.
Zapis cyklu możemy jeszcze uprościć. Wystarczy zauważyć że dolny wiersz naszego symbolu oznacza-
jącego cykl można jednoznacznie odtworzyć z górnego. Zatem uproszczony symbol ma postać:

· · ·

k−1

· · ·

= [a

, a

, · · · , a

k−1

, a

Można udowodnić, że każdą permutację można przedstawić jako złożenie pewnej liczby cykli.

3.4. LICZBY STIRLINGA

Przykład 3.3.2

Niech S = {1, 2, 3, 4, 5}. Rozważmy permutację (2, 6, 5, 3, 4). Zauważmy, że tę per-

mutację możemy rozłożyć na dwa cykle

(2,

6, 5, 3, 4) = [2, 1][6, 5, 3, 4].

Zadanie 3.3.1

Każdą z poniższych permutacji przedstaw w postaci cyklu lub układu cykli rozłącz-

nych

3.4.

Liczby Stirlinga

Definicja 3.4.1

Liczbę sposobów podziału n-elementowej permutacji na k cykli oznaczamy

n
k

nazywamy liczbami Stirlinga pierwszego rodzaju.

Podział permutacji na cykle można interpretować jako podział zbioru n-elementowego na podzbiory,
którym nadano ”orientację cykliczną”. Zatem liczby Stirlinga pierwszego rodzaju równe są liczbie
rozmieszczenia n elementów w k cyklach.

Oczywiście mamy

= 0,

n > 0;

n
n

= 1,

n  0;

= (n − 1)!,

n > 0.

Przykład 3.4.2

Niech S = {1, 2, 3, 4}. Istnieje 11 różnych sposobów na utworzenie dwóch cykli ze

zbioru S:

[1, 2, 3][4],

[1, 2, 4][3],

[1, 3, 4][2],

[2, 3, 4][1],

[1, 3, 2][4],

[1, 4, 2][3],

[1, 4, 3][2],

[2, 4, 3][1]

[1, 2][3, 4],

[1, 3][2, 4],

[1, 4][2, 3]

Zauważmy, że liczby Stirlinga pierwszego rodzaju spełniają następującą zależność

n
k

n − 1
k − 1

+ (n − 1)

n − 1

Istotnie rozmieszczając n elementów w k cyklach możemy

albo n − 1 elementów podzielić na k − 1 cykli na

n − 1
k − 1

sposobów i n-ty element umieścić w

jednoelementowym cyklu

albo n elementów podzielić na k cykli na

n − 1

sposobów i n-ty element umieścić w jednym z

tych cykli na n − 1 sposobów.

Trójkąt Stirlinga dla cykli

ROZDZIAŁ 3.

KOMBINATORYKA.

0
0

1
0

1
1

2
0

2
1

2
2

3
0

3
1

3
2

3
3

4
0

4
1

4
2

4
3

4
4

5
0

5
1

5
2

5
3

5
4

5
5

6
0

6
1

6
2

6
3

6
4

6
5

6
6

Rozwiązany trójkąt Stirlinga dla cykli

120

274

225

Definicja 3.4.3

Niech dany będzie pewien zbiór n elementowy S. Liczbę sposobów podziału zbioru n

elementowego na k niepustych podzbiorów oznaczamy

(

n
k

)

i nazywamy liczbami Stirlinga drugiego

rodzaju.

Zauważmy, że liczby Stirlinga drugiego rodzaju spełniają następującą zależność

(

n
k

)

(

n − 1
k − 1

)

+ k

(

n − 1

)

Istotnie dzieląc zbiór S złożony z n elementów na k niepustych podzbiorów możemy

albo podzielić zbiór (n−1)-elementowy na k −1 podzbiorów na

(

n − 1
k − 1

)

sposobów i n-ty element

umieścić w zbiorze jednoelementowym ,

albo podzielić n − 1 elementów na k podzbiorów na

(

n − 1

)

sposobów i n-ty element umieścić

w jednym z tych podzbiorów na k sposobów.

Ponadto zauważmy, że

(

)

= 0,

n > 0;

(

n
n

)

= 1,

n  0.

Trójkąt Stirlinga dla podzbiorów

3.4. LICZBY STIRLINGA

(

0
0

)

(

1
0

)

(

1
1

)

(

2
0

)

(

2
1

)

(

2
2

)

(

3
0

)

(

3
1

)

(

3
2

)

(

3
3

)

(

4
0

)

(

4
1

)

(

4
2

)

(

4
3

)

(

4
4

)

(

5
0

)

(

5
1

)

(

5
2

)

(

5
3

)

(

5
4

)

(

5
5

)

(

6
0

)

(

6
1

)

(

6
2

)

(

6
3

)

(

6
4

)

(

6
5

)

(

6
6

)

Rozwiązany trójkąt Stirlinga dla podzbiorów

Zadanie 3.4.1

Udowodnić, że

(

)

= 2

n−1

− 1,

(

n − 1

)

n − 1

n(n − 1)

n + 1
n − 1

n + 1

+ 6

n + 1

(

n − 2

)

n + 1

+ 2

Zadanie 3.4.2

Oblicz

(

3
2

)

(

5
3

)

(

6
2

)

3
1

5
3

6
4

Zadanie 3.4.3

Dany jest zbiór ośmioelementowy. Oblicz na ile sposobów zbiór ten można podzielić

dwa niepuste podzbiory,

dwa niepuste cykle,

siedem niepustych podzbiorów,

siedem niepustych cykli.

Zadanie 3.4.4

Na przyjęcie urodzinowe zaproszono k dzieci i przygotowano n różnych ciastek. Na

ile sposobów można te ciastka rozdzielić między dzieci tak, aby każde dziecko dostało przynajmniej
jedno ciastko? Podaj dokładną odpowiedź dla k = 4 i n = 8.

ROZDZIAŁ 3.

KOMBINATORYKA.

Zadanie 3.4.5

Dysponujemy komputerem mającym sześć rozróżnialnych procesorów. Chcemy roz-

dzielić pomiędzy nie wykonanie 11 różnych procesów, z których każdy od początku do końca działa na
jednym przydzielonym procesorze. Na ile sposobów możemy rozdzielić procesy pomiędzy procesory,
zakładając, że chcemy by każdy z procesorów wykorzystany był chociaż raz?

Zadanie 3.4.6

Ile jest możliwości rozdzielenia 8 nagród rzeczowych pomiędzy 5 pracowników firmy

tak, by każdy z nich otrzymał jakąś nagrodę?

Zadanie 3.4.7

Mamy do dyspozycji m ponumerowanych procesorów i n różnych programów, przy

czym n m. Każdy z programów może być wykonany na dowolnym procesorze. Na ile sposobów
można przydzielić wszystkie programy tym procesorom, aby każdy procesor otrzymał co najmniej
jeden program.

Zadania

ROZWIĄZANIA I ODPOWIEDZI

3.1.1 a)

3.1.2 a)

36,

21,

3.1.3 a)

3.1.4 a)

3.1.5 a)

n
k

n+k−1

(n−k)!

3.1.6 a)

n
k

n+k−1

(n−k)!

3.1.7

3.1.8 a)

(n−1)!
(n−k)!

(n−2)!
(n−k)!

2(n−2)!

(n−k)!

3.1.9 a)

n!,

− n!,

1
2

n(n − 1)n!

3.1.10 a)

k!,

(k − 1)!

3.1.11

20160

3.1.12 a)

120,

3.1.13

10000000, 604800

3.1.14 a)

16,

3.1.15

7140

3.1.17

286

3.1.18 a)

455,

3.1.19

3.1.20

3.4.4

(

n
k

)

3.4.5

(

)

3.4.6

(

8
5

)

Rozdział 4

Rekurencja.

Definicja 4.0.4

Mówimy, że ciąg jest zdefiniowany rekurencyjnie, jeśli

(P) Określony jest pewien skończony zbiór wyrazów tego ciągu.

(R) Kolejne wyrazy ciągu są definiowane za pomocą wcześniej wyznaczonych wyrazów tego ciągu.

Warunek (P) nazywamy warunkiem początkowym, a warunek (R) nazywamy warunkiem re-
kurencyjnym.

Przykład 4.0.5

Definicja silni jest definicją rekurencyjną, istotnie

(P) 0! = 1,

(R) n! = (n − 1)! · n, n ∈ N.

Przykład 4.0.6

Niech a

oznacza liczbę permutacji zbioru {1, 2, . . . , n}. Oczywiście a

= 1, bo ist-

nieje tylko jedna permutacja zbioru {1}. Ponadto dla dowolnego n  1 mamy a

= n · a

n−1

. Z drugiej

strony wiadomo, że a

= n!.

Zajmować będziemy się problemem rozwiązywania zależności rekurencyjnych. Dokładniej sposobami
wyznaczania ogólnego wyrazu ciągu spełniającego pewną zależność rekurencyjną.

Rozwiązanie rekurencji bez uwzględnienia warunków początkowych nazywamy rozwiązaniem

ogólnym. Jeśli wykorzystamy warunki początkowe, to otrzymane rozwiązanie nazywać będziemy
rozwiązaniem szczególnym.

4.1.

Liniowe zależności rekurencyjne

Niech r ∈ N i w

dla i = 1, 2, . . . , r będą pewnymi stałymi rzeczywistymi.

Definicja 4.1.1

Równanie rekurencyjne postaci

= w

n−1

+ w

n−2

+ · · · + w

n−r

+ f (n),

n r,

nazywamy niejednorodnym liniowym równaniem rekurencyjnym.

Jeśli

n∈N

f (n) = 0, to równanie

nazywamy jednorodnym liniowym równaniem rekurencyjnym.

Zauważmy, że każdy ciąg stały o wyrazach równych 0 spełnia jednorodne liniowe równanie rekuren-
cyjne. Rozwiązanie takie nazywamy trywialnym. Każde rozwiązanie różne od trywialnego nazywa
się nietrywialnym.

Twierdzenie 4.1.2

Jeżeli ciągi o wyrazach a

i a

spełniają jednorodne liniowe równanie rekuren-

cyjne, to ciągi o wyrazach c

+ c

, gdzie c

i c

są dowolnymi stałymi, też spełniają jednorodne

liniowe równanie rekurencyjne.

ROZDZIAŁ 4. REKURENCJA.

Definicja 4.1.3

Równanie z niewiadomą x

− w

r−1

− w

r−2

− · · · − w

r−1

x − w

= 0

nazywa się równaniem charakterystycznym jednorodnego liniowego równania rekurencyjnego.

Twierdzenie 4.1.4

Ciąg o wyrazach s

= α

jest nietrywialnym rozwiązaniem jednorodnego linio-

wego równania rekurencyjnego wtedy i tylko wtedy, gdy α jest pierwiastkiem jego równania charakte-
rystycznego.

Twierdzenie 4.1.5

Ciąg o wyrazach s

= n

jest nietrywialnym rozwiązaniem jednorodnego li-

niowego równania rekurencyjnego dla i = 1, 2, . . . , k − 1 wtedy i tylko wtedy, gdy α jest k-krotnym
pierwiastkiem równania charakterystycznego.

Wniosek 4.1.6

Jeśli α

, α

, . . . , α

są różnymi pierwiastkami równania charakterystycznego, to jed-

norodne liniowe równanie rekurencyjne ma rozwiązanie ogólne postaci

= C

n
1

+ C

n
2

+ · · · + C

n
r

Wniosek 4.1.7

Jeżeli

− w

r−1

− w

r−2

− · · · − w

r−1

x − w

= (x − α

)

(x − α

)

· · · · · (x − α

)

gdzie

1¬i¬k

1, m

+ m

+ · · · + m

= r (tzn. α

jest m

-krotnym pierwiastkiem równania charak-

terystycznego), to jednorodne liniowe równanie rekurencyjne ma rozwiązanie ogólne postaci

= (C

+ C

n + C

+ · · · + C

−1

)α

n
1

+ (D

+ D

n + D

+ · · · + D

−1

)α

n
2

+ . . .

+ (Z

+ Z

n + Z

+ · · · + Z

−1

)α

n
k

Przykład 4.1.8

Załóżmy, że wchodzimy po schodach zbudowanych z n stopni i że w każdym kroku

możemy pokonać jeden albo dwa stopnie. Wtedy jeśli a

oznacza liczbę sposobów wejścia po tych

schodach, to dla n > 2 a

= a

n−1

+ a

n−2

oraz a

= 1 i a

= 2. Można pokazać, że taką rekurencję

spełnia ciąg o wyrazie ogólnym

√

1 +

√

n+1

−

√

1 −

√

n+1

Kolejne wyrazy tego ciągu: 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .

Ciąg o wyrazach F

spełniających zależność rekurencyjną z powyższego przykładu z pierwszym wy-

razem F

= 1 nazywa się ciągiem Fibonacciego, a jego elementy liczbami Fibonacciego.

Twierdzenie 4.1.9

Jeżeli ciąg o wyrazach a

jest rozwiązaniem ogólnym jednorodnego równania re-

kurencyjnego i ciąg o wyrazach a

jest rozwiązaniem szczególnym niejednorodnego równania rekuren-

cyjnego, to ciąg o wyrazach a

= a

+ a

jest rozwiązaniem ogólnym równania niejednorodnego.

Równanie niejednorodne rozwiązuje się w dwóch etapach.

Etap I.

Poszukujemy rozwiązania ogólnego a

jednorodnego liniowego równania rekurencyjnego.

Etap II.

Poszukujemy rozwiązania szczególnego a

niejednorodnego liniowego równania rekurencyjnego.

Najczęściej stosuje się tzw, metodę przewidywań

jeżeli f (n) jest wielomianem stopnia n i rozwiązanie ogólne nie jest wielomianem, to rozwiązanie
szczególne jest wielomianem tego samego stopnia co f (n),

4.1. LINIOWE ZALEŻNOŚCI REKURENCYJNE

jeżeli f (n) jest wielomianem stopnia n i rozwiązanie ogólne jest wielomianem stopnia k, to
rozwiązanie szczególne ma postać

s
n

= n

k+1

+ A

k−1

+ · · · + A

jeżeli f (n) jest funkcją wykładniczą postaci f (n) = Cβ

i β nie jest pierwiastkiem równania

charakterystycznego, to rozwiązanie szczególne jest postaci a

= Aβ

jeżeli f (n) jest funkcją wykładniczą postaci f (n) = Cβ

i β jest k-krotnym pierwiastkiem

równania charakterystycznego, to rozwiązanie szczególne jest postaci a

= An

Stałe A

, A

, . . . , A

i A występujące w rozwiązaniach szczególnych należy wyznaczyć wykorzystując

fakt, że mamy otrzymać rozwiązanie równania niejednorodnego.

Jeżeli funkcja f (n) jest sumą funkcji rozważanych powyżej, to przewidywanie rozwiązanie jest

sumą przewidywanych rozwiązań odpowiadających tym funkcjom.

4.1.1.

Rozwiązywanie rekurencji z wykorzystaniem czynnika sumacyjnego

Wiadomo, że jeśli S

k=0

= a

+ a

+ · · · + a

, to S

= S

n−1

+ a

i S

= a

. Zatem suma n pierw-

szych wyrazów ciągu {a

} spełnia niejednorodne liniowe równanie rekurencyjne. W szczególności, gdy

= α + βn rozwiązanie ogólne jest postaci S

= a

+ αn +

n(n + 1). Widzimy więc, że moż-

na znajdować sumy wyrazów ciągu przy pomocy rekurencji. Można również rozwiązywać rekurencje
wykorzystując sumy

Przykład 4.1.10

Dana jest rekurencja

(

= 0,

= 2T

n−1

+ 1,

n > 0.

Dzieląc przez 2

stronami i podstawiając S

= 2

−n

otrzymamy rekurencję dla ciągu S

k=1

−k

Jeśli potrafimy obliczyć wartość tej sumy, to również potrafimy wyznaczyć wzór na wyrazy ciągu T

Rozważmy teraz sytuację bardziej ogólną. Niech ciąg {t

} spełnia rekurencję

= b

n−1

+ c

gdzie {a

}, {b

}, {c

} są danymi ciągami takimi, że

6= 0.

Aby wyznaczyć postać jawną ciągu {t

} mnożymy rekurencję obustronnie przez czynnik sumacyjny

dobrany tak, aby s

= s

n−1

. Wówczas otrzymujemy

k=1

Kładąc r

= s

dostajemy niejednorodne liniowe równanie rekurencyjne postaci

= r

n−1

+ c

którego rozwiązaniem jest ciąg o wyrazach

= s

k=1

Wracając do podstawienia mamy

k=1

Wystarczy więc wyznaczyć ciąg sumacyjny s

aby otrzymać ostateczne rozwiązanie.

Tego typu postępowanie ilustruje poniższy przykład.

ROZDZIAŁ 4. REKURENCJA.

Przykład 4.1.11

W analizie sortowania szybkiego (quicksort), najważniejszej metodzie sortowania

pamięci wewnętrznej, średnia liczba porównań t

wykonywanych dla m losowych elementów spełnia

rekurencję

= 0,

= m + 1 +

m−1

k=0

m > 0.

Wyznaczyć postać jawną liczby porównań.

Odpowiedź: t

= 2(n + 1)H

− 2n, gdzie elementy ciągu H

k=1

1
k

nazywa się liczbami harmonicz-

nymi.

Zadania

Zadanie 4.1.1

Dla ciągów {a(n)} danych poniższymi relacjami rekurencyjnymi obliczyć wyrazy a(2),

a(9), a(73)

(a)

a(1) = 1, a(n) = 2a(b

c);

(b)

a(1) = 1, a(n) = 2a(b

c) + n.

Zadanie 4.1.2

Niech Σ = {a, b}, A

będzie zbiorem słów słownika Σ

∗

niezawierających kolejnych

liter a, a s

- liczbą słów długości n, w których nie występują kolejno dwie litery a, tzn. nie zawierają

ciągu aa. Wyznaczyć wzór rekurencyjny na s

Zadanie 4.1.3

Niech Σ = {a, b, c}, A

będzie zbiorem słów słownika Σ

∗

, w których występuje pa-

rzysta liczba liter a, a s

- liczbą słów długości n ze zbioru A

. Wyznaczyć wzór rekurencyjny na

Zadanie 4.1.4

Niech {a

} będzie ciągiem liczb rzeczywistych. Podaj definicję rekurencyjną ciągu

i=1

, n  1.

Zadanie 4.1.5

Niech {A

} będzie ciągiem podzbiorów pewnego niepustego zbioru S. Podaj definicje

rekurencyjne ciągów S

i=1

, T

i=1

, n  1.

Zadanie 4.1.6

Podaj definicję rekurencyjną rodziny zbiorów {x ∈ N : x ¬ n}, n  1.

Zadanie 4.1.7

Podaj wzór jawny na s

gdy

(a)

= 2, s

= −1, s

= −s

n−1

+ 6s

n−2

, n  2;

(b)

= 1, s

= 4, s

= −2s

n−1

+ 3s

n−2

, n  2;

(c)

= 1, s

= 8, s

= 4s

n−1

− 4s

n−2

, n > 1;

(d)

= 0, s

= 5, s

= −2s

n−1

− s

n−2

− 2s

n−3

, n  3;

(e)

= 2, a

= 3, a

= −9a

n−2

− 6a

n−1

, n > 1;

(f )

= 5, a

= 16, a

= 4a

n−1

−4a

n−2

+ 4

, n > 1;

(g)

= 0, a

= 1, a

= −3a

n−1

+ 4a

n−3

, n > 2;

(h)

= 1, a

= 0, a

= 3, a

= 3a

n−1

− 4a

n−3

,n  3;

(i)

= 3, a

5
2

n−1

− a

n−2

, n  2;

(j)

= 0, a

= 8, a

= −16, a

= −2a

n−1

+ 4a

n−2

+ 8a

n−3

, n  3;

4.1. LINIOWE ZALEŻNOŚCI REKURENCYJNE

(k)

= 1, a

= 8, a

= 12, a

= 2a

n−1

+ 4a

n−2

− 8a

n−3

, n > 2;

(l)

= 10, a

= 4, a

= 5a

n−1

+ 6a

n−2

− 10n − 13, n > 1;

(ł)

= 0, a

5
6

1
6

n−1

1
6

n−2

, n  2.

Zadanie 4.1.8

Znaleźć rozwiązanie ogólne równania rekurencyjnego

(a)

= 3a

n−1

− 2a

n−2

+ 2

(b)

= 3a

n−1

− 3a

n−2

+ a

n−3

(c)

= 3a

n−2

+ 2a

n−3

Zadanie 4.1.9

Wiadomo, że wielomian charakterystyczny jednorodnej rekurencji liniowej ma dwa

pierwiastki jednokrotne równe 2 i −2. Podać postać tej rekurencji oraz jej rozwiązanie przy warunkach
początkowych a

= 0, a

= 8.

Zadanie 4.1.10

Wiadomo, że wielomian charakterystyczny jednorodnej rekurencji liniowej ma dwa

pierwiastki jednokrotne równe 2 i −2 oraz jeden pierwiastek dwukrotny równy −1. Podać postać tej
rekurencji oraz jej rozwiązanie przy warunkach początkowych a

= 2, a

= 1, a

= 6 i a

= 3.

Zadanie 4.1.11

Wiadomo, że wielomian charakterystyczny jednorodnej rekurencji liniowej ma trzy-

krotny pierwiastek równy 2. Podać postać tej rekurencji oraz jej rozwiązanie przy warunkach począt-
kowych a

= 0, a

= 8.

Zadanie 4.1.12

Mówimy, że rozwiązujący pewien problem student jest na n-tym etapie jeżeli do

rozwiązania problemu pozostaje mu n kroków (n  1). Na każdym etapie ma on 5 możliwości postę-
powania. Dwie z nich prowadzą go z n-tego do (n − 1)-go etapu, a pozostałe 3 z n-tego do (n − 2)-go
etapu. Niech a

oznacza liczbę sposobów rozwiązania problemu zaczynając od n-tego etapu. Przyjmu-

jąc , że problem na pierwszym etapie można rozwiązać na 5 sposobów, a na drugim na 13, wyznaczyć
liczbę sposobów rozwiązania problemu w ogólnej sytuacji czyli na n-tym etapie.

Zadanie 4.1.13

Kod Morse’a zbudowany jest ze skończonych ciągów kropek i kresek, które odpo-

wiadają znakom alfanumerycznym. Długością kodu dla ustalonego znaku nazywa się liczbę całkowitą
otrzymaną przez zsumowanie wag poszczególnych elementów kodu, gdzie kropka ma wagę 1, a kreska
ma wagę 2. Niech a

oznacza liczbę kodów Morse’a długości n. Udowodnić, że liczba takich kodów

długości n tworzy ciąg Fibonacciego i na tej podstawie wyznaczyć a

Zadanie 4.1.14

Niech a

oznacza liczbę n elementowych ciągów o elementach ze zbioru {0, 1, 2},

takich, że żadne dwie po sobie następujące jedynki ani żadne dwie następujące po sobie dwójki nie są
dozwolone. Wyznaczyć wzór na a

Zadanie 4.1.15

Przy pomocy czynnika sumacyjnego rozwiązać rekurencję

(a)

(

= 4,

1
2

= nT

n−1

1
2

n!,

n  1,

(b)

(

= 1,

1
2

= nt

n−1

1
2

n > 1,

(c)

(

= 3,

= nt

n−1

+ 2n!,

n  1,

(d)











= 7,

= T

n−1

(n − 1)!

n  1,

(e)

(

= 5,

= nt

n−1

+ 3n!,

n  1,

(f )











= 0,

= 5t

n−1

[(n − 1)!]

n > 1.

ROZDZIAŁ 4. REKURENCJA.

Odpowiedzi i wskazówki do zadań

4.1.2

Zobacz przykład 4 ze strony 232 w książce Rossa i Wrighta ”Matematyka dyskretna”.

4.1.3

Zobacz przykład 5 ze strony 232 w książce Rossa i Wrighta ”Matematyka dyskretna”.

4.1.7 d)

= (−2)

−

1−2i

−1+2i

(−i)

, gdzie i

= −1,

4.1.12

1
2

n+1

1
2

(−1)

n+1

4.1.14

1
2

(1 +

√

n+1

1
2

(1 −

√

n+1

Rozdział 5

Teoria grafów

5.1.

Podstawowe pojęcia

Definicja 5.1.1

Grafem nazywamy trójkę G = (V, E, Ψ), gdzie V jest skończonym zbiorem obiektów

zwanych wierzchołkami, E jest skończonym zbiorem obiektów zwanych krawędziami, natomiast
funkcja incydencji Ψ określa sposób przyporządkowania krawędzi wierzchołkom.

Ze względu na sposób przyporządkowania krawędzi wierzchołkom grafy dzielimy na:

nieskierowane, jeśli Ψ : E → P(V ) oraz

e∈E

0 <| Ψ(e) |¬ 2,

skierowane (digrafy), jeśli Ψ : E → V × V .

Zauważmy, że zbiór krawędzi grafu nieskierowanego tworzą dwu- lub jedno-elementowe podzbiory
zbioru wierzchołków, natomiast zbiór krawędzi grafu skierowanego tworzą uporządkowane pary wierz-
chołków.

Krawędzie grafu skierowanego nazywa się również łukami.

Definicja 5.1.2

Rysunkiem grafu lub diagramem

nazywamy wykres składający się z punk-

tów odpowiadających elementom zbioru V oraz odcinków (graf nieskierowany) lub strzałek (graf
skierowany) odpowiadających elementom zbioru E takich, że jeśli Ψ(e) = {v, w} lub odpowiednio
Ψ(e) = (v, w), to punkty v i w są połączone odcinkiem bądź strzałką.

Definicja 5.1.3

Graf (V

, E

, Ψ

) nazywamy podgrafem grafu (V, E, Ψ) jeśli

⊆ V , E

⊆ E,

∈E

) = Ψ(e

Jeśli nie istnieje krawędź incydentna do wierzchołka v, to taki wierzchołek nazywa się izolowa-
nym.

Jeśli Ψ(e

) = Ψ(e

), to e

i e

nazywamy krawędziami równoległymi.

Jeśli | Ψ(e) |= 1, tzn. Ψ(e) = {v} lub odpowiednio Ψ(e) = (v, v), to e nazywamy pętlą.

Jeśli graf nie ma pętli i krawędzi równoległych, to nazywamy go grafem prostym.

Jeśli v ∈ Ψ(e), to krawędź e nazywa się incydentną do wierzchołka v.

Każda krawędź może być incydentna do jednego lub dwóch wierzchołków.

Jeśli Ψ(e) = {v, w} lub odpowiednio Ψ(e) = (v, w), to wierzchołki v i w nazywamy sąsiednimi,
a o krawędzi e mówimy, że łączy wierzchołki v i w.

Jeśli Ψ(e) = (u, v), to u nazywa się początkiem krawędzi e, a v jej końcem i mówi się, że krawędź
e wychodzi z wierzchołka u i wchodzi do wierzchołka v.

ROZDZIAŁ 5. TEORIA GRAFÓW

Liczbę d(v) krawędzi incydentnych z wierzchołkiem v nazywa się stopniem wierzchołka v,
przy czym pętle zlicza się dwukrotnie.

Ciąg liczb wierzchołków kolejnych stopni jest to ciąg, w którym n-ty element równy jest
liczbie wierzchołków grafu stopnia n.

Stopień wierzchołka izolowanego wynosi zero.

Jeśli d(v) = 1, to wierzchołek v nazywamy liściem.

Przykład 5.1.4

Przykłady grafów:

Graf prosty = graf, który nie zawiera pętli i krawędzi równoległych.

Graf zerowy = graf, którego zbiór wierzchołków jest pusty.

Graf pusty = graf, którego zbiór krawędzi jest pusty, oznaczamy go N

, gdzie m =| V |; każdy

wierzchołek w grafie pustym jest izolowany.

Graf pełny o m wierzchołkach = graf prosty, w którym każde dwa różne wierzchołki są
sąsiednie, oznaczamy go K

Graf regularny stopnia r = graf, w którym każdy wierzchołek ma stopień równy r. Grafy
regularne stopnia 3 nazywa się grafami kubicznymi.

Grafy platońskie = grafy regularne utworzone z wierzchołków i krawędzi pięciu wielościanów
foremnych: czworościanu, sześcianu, ośmiościanu, dwunastościanu i dwudziestościanu.

Graf dwudzielny = graf, w którym zbiór wierzchołków można podzielić na dwa rozłączne pod-
zbiory V

i V

w taki sposób, że każda krawędź grafu łączy dowolny wierzchołek zbioru V

dowolnym wierzchołkiem zbioru V

. Jeśli każdy wierzchołek zbioru V

jest połączony krawędzią

z każdym wierzchołkiem zbioru V

i graf jest prosty, to nazywamy go grafem pełnym dwu-

dzielnym.

Obwód = graf spójny, regularny stopnia dwa, oznaczamy go C

Graf krawędziowy L(G) grafu prostego G = graf, którego wierzchołkom odpowiadają wzajemnie
jednoznacznie krawędzie grafu G, a dwa wierzchołki grafu L(G) są incydentne wtedy i tylko wtedy,
gdy odpowiednie krawędzie grafu G są sąsiednie.

Koło = graf, który powstaje z obwodu C

n−1

przez dołożenie jednego wierzchołka sąsiedniego do

wszystkich wierzchołków obwodu C

n−1

, oznaczamy go W

Graf Petersena = graf regularny stopnia 3 o dziesięciu wierzchołkach, przedstawiony na ry-
sunku 5.1(a).

Pryzmatoid = graf regularny stopnia 4 o ośmiu wierzchołkach, przedstawiony na rysunku
5.1(b).

Niech e będzie krawędzią, a v wierzchołkiem grafu G. Wprowadźmy oznaczenia.

G − e

=graf otrzymany z grafu G po usunięcie krawędzi e bez wierzchołków do niej incydentnych

G − v

=graf otrzymany z grafu G przez usunięcie wierzchołka v razem z krawędziami do niego incy-
dentnymi

G \ e

=graf otrzymany w wyniku ściągnięcia krawędzi e, tj. przez usuniecie e i utożsamienie jej koń-
ców v i w w taki sposób, że otrzymany wierzchołek jest incydentny z krawędziami, które były
incydentne z v i w z wyjątkiem usuniętej krawędzi e

5.2. REPREZENTACJE MACIERZOWE GRAFÓW

(a) Graf Petersena

(b) Pryzmatoid

Rysunek 5.1.

5.2.

Reprezentacje macierzowe grafów

Niech G będzie grafem nieskierowanym o n wierzchołkach i m krawędziach.

Definicja 5.2.1

Macierz I(G) = [a

] o n wierszach i m kolumnach zdefiniowaną następująco

(

jeśli j-ta krawędź jest incydentna do i-tego wierzchołka

w przeciwnym przypadku,

nazywamy macierzą incydencji grafu G.

Własności macierzy incydencji

W macierzy incydencji grafu nieskierowanego poszczególne wiersze odpowiadają wierzchołkom
grafu, a kolumny - krawędziom.

Każda kolumna macierzy incydencji grafu prostego zawiera dokładnie dwie jedynki.

Kolumna odpowiadająca pętli zawiera jedną jedynkę.

W grafie bez pętli liczba jedynek w każdym wierszu równa się stopniowi odpowiadającego mu
wierzchołka.

Wiersz samych zer reprezentuje wierzchołek izolowany.

Krawędzie równoległe tworzą identyczne kolumny.

Definicja 5.2.2

Macierz kwadratową S(G) = [a

] o n wierszach zdefiniowaną następująco

= liczba krawędzi łączących wierzchołek v

z wierzchołkiem v

nazywamy macierzą sąsiedztwa grafu G.

Własności macierzy sąsiedztwa

Wiersze i kolumny macierzy sąsiedztwa odpowiadają wierzchołkom grafu.

Macierz sąsiedztwa jest kwadratową macierzą symetryczną.

Suma elementów w każdym wierszu i każdej kolumnie równa jest stopniowi odpowiedniego wierz-
chołka.

Jeśli w grafie nie występują pętle, to na przekątnej są zera.

Jeśli graf jest grafem prostym, to elementami macierzy sąsiedztwa są zera i jedynki.

ROZDZIAŁ 5. TEORIA GRAFÓW

5.3.

Drogi w grafie

Drogą w grafie nazywamy skończony ciąg następujących po sobie wierzchołków i krawędzi ta-
kich, że każda krawędź jest incydentna do wierzchołka poprzedzającego ją i następującego po
niej

. . . v

n−1

Czasami dla uproszczenia podaje sie tylko ciąg wierzchołków lub tylko ciąg krawędzi.

Długością drogi nazywamy liczbę krawędzi jakie w niej występują.

Drogą zamkniętą nazywamy drogę, która zaczyna się i kończy w tym samym wierzchołku.

Drogą prostą nazywamy drogę, w której każda krawędź grafu pojawia się co najwyżej raz. (W
drodze prostej wszystkie krawędzie są różne)

Ścieżka to droga nie zamknięta, w której każdy wierzchołek grafu pojawia co najwyżej raz. (W
ścieżce wszystkie wierzchołki są różne).

Każda ścieżka jest droga prostą.

Cykl to zamknięta ścieżka. W szczególności każda pętla jest cyklem długości jeden, a dwie
krawędzie równoległe są cyklem długości dwa.

Graf, w którym nie występuje żaden cykl nazywamy grafem acyklicznym.

Lemat o uściskach dłoni

Suma stopni wierzchołków grafu jest dwa razy większa od liczby krawędzi, tzn.

v∈V

d(v) = 2 · |E|.

Wniosek 5.3.1

Liczba wierzchołków stopnia nieparzystego jest w dowolnym grafie liczbą parzystą.

Twierdzenie 5.3.2

Niech d

oznacza liczbę wierzchołków stopnia k. Wtedy

+ 2d

+ 3d

+ · · · = 2|E|.

5.4.

Grafy izomorficzne

Definicja 5.4.1

Dwa grafy G

= (V

, E

, Ψ

) i G

= (V

, E

, Ψ

) nazywamy izomorficznymi jeśli

istnieje wzajemnie jednoznaczne różnowartościowe odwzorowanie f : V

→ V

takie, że

u,v∈V

(u, v) ∈ E

⇔ Ψ

(f (u), f (v)) ∈ E

Własności grafów izomorficznych

Grafy G i G

są izomorficzne wtedy i tylko wtedy, gdy macierze I(G) i I(G

) różnią się kolejnością

wierszy lub kolumn.

Grafy izomorficzne mają tyle samo wierzchołków i krawędzi.

Grafy izomorficzne mają tyle samo pętli i dróg prostych tej samej długości.

Grafy izomorficzne mają takie same ciągi liczb wierzchołków kolejnych stopni.

5.5. GRAFY SPÓJNE

5.5.

Grafy spójne

Definicja 5.5.1

Graf nieskierowany nazywamy spójnym, jeśli dla każdej pary jego wierzchołków

istnieje droga łącząca te wierzchołki.

Dowolny graf można rozbić na rozłączne podgrafy spójne zwane składowymi. Oczywiście graf spójny
ma tylko jedną składową.

Twierdzenie 5.5.2

Niech G = (V, E, Ψ) będzie grafem prostym o n wierzchołkach. Jeśli G ma k

składowych, to liczba jego krawędzi spełnia nierówność

n − k ¬ |E| ¬

(n − k)(n − k + 1)

Wniosek 5.5.3

Dowolny graf prosty o n wierzchołkach i więcej niż

1
2

(n − 1)(n − 2) krawędziach jest

spójny.

Definicja 5.5.4

Zbiorem rozspajającym dowolnego grafu G nazywamy podzbiór zbioru E złożony

z tych krawędzi, których usunięcie zwiększa liczbę składowych.

Definicja 5.5.5

Rozcięciem dowolnego grafu G nazywamy taki zbiór rozspajający, którego żaden

podzbiór właściwy nie jest rozspajający.

Definicja 5.5.6

Zbiorem rozdzielającym dowolnego grafu G nazywamy zbiór wierzchołków których

usunięcie zwiększa liczbę składowych grafu.

Niech teraz G = (V, E, Ψ) będzie grafem spójnym.

Definicja 5.5.7

Spójnością krawędziową λ(G) nazywamy najmniejszą liczbę krawędzi, których

usunięcie powoduje, że graf G jest niespójny.
Mówimy, że graf jest k-spójny krawędziowo, gdy λ(G)  k.

Definicja 5.5.8

Spójnością wierzchołkową µ(G) nazywamy najmniejszą liczbę wierzchołków, któ-

rych usunięcie czyni graf G niespójnym.
Mówimy, że graf jest k-spójny wierzchołkowo, gdy µ(G)  k.

Zadania

Zadanie 5.5.1

Narysuj graf o pięciu wierzchołkach i ośmiu krawędziach, który jest

prosty,

nie jest prosty, ale nie ma pętli,

nie jest prosty, ale nie ma krawędzi równoległych.

Zadanie 5.5.2

Narysuj grafy pełne o 3, 4, 5 wierzchołkach i podaj ich macierze incydencji i sąsiedz-

twa.

Zadanie 5.5.3

Narysuj graf pełny dwudzielny o pięciu wierzchołkach, w którym jeden ze zbiorów

wierzchołków zawiera tylko dwa wierzchołki. Podaj macierze sąsiedztwa i incydencji tego grafu.

Zadanie 5.5.4

Narysować wszystkie nieizomorficzne grafy o czterech wierzchołkach i trzech krawę-

dziach, a następnie skonstruować macierze incydencji i sąsiedztwa dla każdego grafu.

Zadanie 5.5.5

Pokazać, że graf na rysunku 5.2 jest izomorficzny z grafem Petersena, a następnie

podać macierz sąsiedztwa i incydencji tych grafów.

ROZDZIAŁ 5. TEORIA GRAFÓW

Rysunek 5.2.

Zadanie 5.5.6

Podać macierz sąsiedztwa, macierz incydencji oraz ciąg liczb kolejnych stopni wierz-

chołków grafów o diagramach

Zadanie 5.5.7

Dane są macierze sąsiedztwa

































































































Narysować grafy o podanych macierzach sąsiedztwa, a następnie wyznaczyć stopnie każdego z wierz-
chołków. Wskazać drogi długości 3 i ścieżki długości 5. Czy istnieją cykle w tych grafach?

Zadanie 5.5.8

Dane są macierze incydencji

5.5. GRAFY SPÓJNE





































































Narysować grafy o podanych macierzach incydencji, a następnie wyznaczyć stopnie każdego z wierz-
chołków. Wskazać drogi długości 5 i ścieżki długości 3. Czy istnieją cykle w tych grafach?

Zadanie 5.5.9

Dane są trzy grafy

(a) Wskaż grafy izomorficzne. Odpowiedź uzasadnij.

(b) Wypisz macierze sąsiedztwa i incydencji grafów G

, G

i G

(c) Który z podanych grafów jest acykliczny, a który jest prosty? Odpowiedź uzasadnij.

Zadanie 5.5.10

Niech G będzie grafem prostym o n wierzchołkach i m krawędziach. Niech v będzie

wierzchołkiem grafu G stopnia k, k ¬ m i niech e będzie krawędzią grafu G. Ile wierzchołków i krawędzi
mają grafy G

powstały przez usunięcie z grafu G krawędzi e i graf G

powstały przez usunięcie z grafu

G wierzchołka v?

Zadanie 5.5.11

Niech dany będzie nieskierowany spójny graf G. Okazało się, że po usunięciu jednej

krawędzi e z grafu G graf pozostał nadal spójny. Co można powiedzieć o krawędzi e. Odpowiedź
uzasadnij.

Zadanie 5.5.12

Zbuduj graf mający zbiór wierzchołków {0, 1}

, w którym wierzchołki u, v są połą-

czone krawędzią, jeśli różnią się na 3 współrzędnych. Wskaż cykle w tym grafie.

Zadanie 5.5.13

Zbuduj graf mający zbiór wierzchołków {0, 1}

, w którym wierzchołki u, v są połą-

czone krawędzią, jeśli różnią się na dwóch lub trzech współrzędnych. Wskaż cykle w tym grafie.

Zadanie 5.5.14

Graf o 21 krawędziach ma 6 wierzchołków stopnia zerowego, 7-stopnia pierwszego,

3-stopnia drugiego i 7-stopnia trzeciego, a pozostałe wierzchołki są stopnia czwartego. Ile wierzchołków
ma ten graf?

Zadanie 5.5.15

Narysuj graf o podanej funkcji incydencji, a następnie wypisz jego macierz incydencji

i sąsiedztwa.

ROZDZIAŁ 5. TEORIA GRAFÓW

Ψ(e

) = {a, b},

Ψ(e

) = {a, c},

Ψ(e

) = {b, a},

Ψ(e

) = {a, b},

Ψ(e

) = {b, c},

Ψ(e

) = {c, c},

Ψ(e

) = {d, d},

Ψ(e

} = {d, b},

Ψ(e

) = {d, d}

Ψ(e

) = {x, y},

Ψ(e

) = {x, y},

Ψ(e

) = {w, x},

Ψ(e

) = {w, y},

Ψ(e

) = {y, z},

Ψ(e

) = {y, z},

Ψ(e

) = {w, z}

Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

Ψ(e

) = {v

, v

}

Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

Ψ(e

) = {a, b},

Ψ(e

) = {b, c},

Ψ(e

) = {c, d},

Ψ(e

) = {d, f },

Ψ(e

) = {f, a},

Ψ(e

) = {b, d},

Ψ(e

) = {d, a},

Ψ(e

) = {d, d}

f )

Ψ(e

) = {a, b},

Ψ(e

) = {b, c},

Ψ(e

) = {c, d},

Ψ(e

) = {d, e},

Ψ(e

)) = {e, f },

Ψ(e

) = {f, a},

Ψ(e

) = {f, b},

Ψ(e

) = {b, d},

Ψ(e

) = {d, f },

Ψ(e

) = {e, a}

Ψ(e

) = {a, c},

Ψ(e

) = {c, e}

Zadanie 5.5.16

Które z następujących ciągów są ciągami liczb wierzchołków kolejnych stopni grafu?

W każdym przypadku albo narysuj graf i wypisz jego macierz sąsiedztwa i incydencji albo wyjaśnij
dlaczego taki graf nie istnieje

(a) (1, 1, 0, 3, 1, 0, 0, . . . ),

(b) (4, 1, 0, 3, 1, 0, 0, . . . ),

(c) (0, 1, 0, 2, 1, 0, 0, . . . ),

(d) (0, 0, 2, 2, 1, 0, 0, . . . ),

(e) (0, 0, 1, 2, 1, 0, 0, . . . ),

(f ) (0, 1, 0, 1, 1, 1, 0, 0, . . . ),

(g) (0, 0, 0, 4, 0, 0, . . . ),

(h) (0, 0, 0, 0, 5, 0, 0, . . . ).

Zadanie 5.5.17

Udowodnić, że dla dowolnego grafu G

2|E(G)| − |V (G)| = −d

+ d

+ 2d

+ 3d

+ · · · + (k − 1)d

+ . . . ,

gdzie d

oznacza liczbę wierzchołków stopnia k.

Zadanie 5.5.18

Dany jest spójny i prosty graf G, który ma tylko wierzchołki drugiego i czwartego

stopnia w jednakowej ilości. Ponadto liczba krawędzi tego grafu równa jest kwadratowi liczby wierz-
chołków stopnia drugiego. Obliczyć ile wierzchołków ma ten graf.

5.6.

Droga Hamiltona

Definicja 5.6.1

Drogę prostą przechodzącą przez każdy wierzchołek grafu dokładnie raz nazywamy

drogą Hamiltona.
Drogę zamkniętą przechodzącą przez każdy wierzchołek grafu dokładnie raz, za wyjątkiem wierzchołka
początkowego i końcowego, nazywamy cyklem Hamiltona.
Graf, w którym istnieje cykl Hamiltona nazywa się grafem Hamiltona.

Twierdzenie 5.6.2 Orego

Jeśli

1. graf G jest prosty,

2. | V (G) |= n  3,

3. dla każdej pary wierzchołków v i w niepołączonych krawędzią d(v) + d(w)  n,

to graf G jest grafem Hamiltona.

Twierdzenie 5.6.3 Diraca

Jeśli

5.7. DROGA EULERA

1. graf G jest prosty,

2. | V (G) |= n  3,

v∈V (G)

d(v)

to graf G jest grafem Hamiltona.

Twierdzenie 5.6.4 o krawędziach

Jeśli graf prosty o n wierzchołkach ma co najmniej

1
2

(n − 1)(n − 2) + 2 krawędzi, to jest grafem Hamiltona.

Kod Graya

Definicja 5.6.5

Kodem Graya długości n nazywa się ciąg wszystkich 2

różnych ciągów cyfr

dwójkowych, ustawionych w taki sposób, że dwa kolejne ciągi różnią się dokładnie jedną cyfrą oraz
ostatni ciąg różni się dokładnie jedną cyfrą od pierwszego ciągu.

Przykład 5.6.6

00, 01, 11, 10 jest kodem Graya długości 2.

Kod Graya długości n można interpretować jako graf Hamiltona, w którym zbiór wierzchołków jest
zbiorem {0, 1}

wszystkich ciągów cyfr dwójkowych długości n, a krawędzie istnieją między wierzchoł-

kami różniącymi się dokładnie jedną cyfrą.

5.7.

Droga Eulera

Definicja 5.7.1

Drogę prostą przechodzącą przez każdą krawędź grafu dokładnie raz nazywamy dro-

gą Eulera.
Drogę zamkniętą przechodzącą przez każdą krawędź grafu dokładnie raz nazywamy cyklem Eulera.
Graf, w którym istnieje cykl Eulera nazywa się grafem Eulera.

Twierdzenie 5.7.2

Graf Eulera ma wszystkie wierzchołki stopnia parzystego.

Twierdzenie 5.7.3

Graf mający drogę Eulera ma albo dwa wierzchołki stopnia nieparzystego, albo

nie ma w ogóle wierzchołków stopnia nieparzystego.

Twierdzenie 5.7.4 Eulera

Skończony graf spójny, w którym każdy wierzchołek ma stopień parzysty ma cykl Eulera.

Wniosek 5.7.5

Skończony graf spójny, w którym istnieją dokładnie dwa wierzchołki stopnia niepa-

rzystego, ma drogę Eulera.

Algorytm Fleury’ego

Krok 1: Jeśli w grafie istnieje wierzchołek stopnia nieparzystego, to zmiennej v nadajemy nazwę jedne-

go (dowolnego) z tych wierzchołków, w przeciwnym przypadku zmiennej v nadajemy nazwę
dowolnego z wierzchołków rozważanego grafu.

Krok 2: Kładziemy V S := v oraz ES := ε.

Krok 3: Jeśli v jest wierzchołkiem izolowanym, to zatrzymujemy się.

Krok 4: Jeśli pozostała dokładnie jedna krawędź incydentna z wierzchołkiem v, to nadajemy zmiennej

e nazwę tej krawędzi, a zmiennej w nazwę drugiego wierzchołka incydentnego z krawędzią e i
usuwamy krawędź e za zbioru E(G) oraz wierzchołek v ze zbioru V (G),

w przeciwnym przypadku nadajemy zmiennej e nazwę jednej z tych krawędzi incydentnych
z wierzchołkiem v, której usunięcie z grafu nie spowoduje niespójności otrzymanego grafu, a
zmiennej w nazwę drugiego wierzchołka incydentnego z krawędzią e i usuwamy krawędź e ze
zbioru E(G).

ROZDZIAŁ 5. TEORIA GRAFÓW

Krok 5: Dołączamy wierzchołek w do ciągu V S, a krawędź e do ciągu ES, zastępujemy wierzchołek v

wierzchołkiem w i przechodzimy do kroku 3.

Poprawność algorytmu Fleury’ego dowodzi się w oparciu o następujące twierdzenie.

Twierdzenie 5.7.6

Niech e będzie krawędzią grafu spójnego G. Następujące warunki są równoważne:

(a)

graf G − e jest spójny,

(b)

e jest krawędzią w pewnym cyklu w grafie G,

(c)

e jest krawędzią w pewnej zamkniętej drodze w grafie G,

Poprawność algorytmu Fleury’ego

Musimy pokazać, że:

algorytm zakończy działanie,

II.

podczas wykonywania algorytmu nie wystąpi błąd,

III.

po zakończeniu działania algorytmu droga ES zawiera wszystkie krawędzie grafu.

I. Każdy przebieg pętli z kroku 3 do kroku 5 powoduje usunięcie jednej krawędzi z grafu. Zatem

żadna z krawędzi nie wystąpi więcej niż raz. Ponieważ graf jest skończony, to algorytm zakończy
się lub może wystąpić błąd.

II. Błąd może nastąpić w kroku 4, gdzie nie mamy pewności, że istnieje taka krawędź, którą można

usunąć bez utraty spójności. Pokażemy, że jest to możliwe.

Niech G

będzie grafem otrzymanym z grafu G w trakcie działania algorytmu. Niech v

będzie

wierzchołkiem wybranym w kroku 1, a v

wierzchołkiem grafu G

, z kroku 4. Chcemy pokazać,

że możemy wybrać jedną z krawędzi incydentnych do v

bez utraty spójności grafu. Możliwe są

przypadki:

1. G

ma dwa wierzchołki stopnia nieparzystego, z których jednym jest v

, a drugim v

2. v

= v

i G

nie ma wierzchołków stopnia nieparzystego.

Ad. 1. Z wniosku 5.7.5 wynika, że w G

istnieje droga Eulera prowadząca z v

do v

, bo są one

stopnia nieparzystego. Za każdym razem, gdy ta droga powraca do v

tworzy ona zamknię-

ta drogę prostą zawierającą dwie krawędzie incydentne do v

. Zatem wszystkie krawędzie

wychodzące z v

należą do pewnych zamkniętych dróg prostych w grafie G

, za wyjątkiem

być może krawędzi, którą ta droga wychodzi z wierzchołka v

po raz ostatni.

Ad. 2. Z twierdzenia Eulera 5.7.4 wynika, że w grafie G

istnieje cykl Eulera i wówczas podobnie

jak w punkcie 1 możemy pokazać, że każda krawędź incydentna do v

jest krawędzią pewnej

zamkniętej drogi prostej.

Z twierdzenia 5.7.6 wynika więc, że po usunięciu dowolnej krawędzi incydentnej do wierzchołka
v

graf G

pozostanie nadal spójny.

III. Pokażemy, że na końcu algorytmu nie pozostaną żadne krawędzie.

Na początku graf jest spójny, w kroku 4 wykazaliśmy, że też jest spójny. W kroku 3 również
jest spójny, bo usuwamy krawędź z incydentnym do niej wierzchołkiem. Zatem cały czas graf
jest spójny. Działanie kończymy, gdy nie ma krawędzi wychodzącej z v

i w G

nie ma żadnego

wierzchołka. Zatem G

nie ma krawędzi i droga ES zawiera wszystkie krawędzie grafu G.

5.7. DROGA EULERA

Zadania

Zadanie 5.7.1

Dla grafów z zadań 5.5.2, 5.5.5, 5.5.6, 5.5.7, 5.5.8, 5.5.9, 5.5.13, 5.5.15 wyznaczyć

spójność krawędziową i wierzchołkową.

Zadanie 5.7.2

Znaleźć spójność wierzchołkową i spójność krawędziową następujących grafów

(a)

obwodu o n wierzchołkach,

(b)

grafu Petersena,

(c)

koła o n wierzchołkach.

Zadanie 5.7.3

Dla grafów z zadań 5.5.2, 5.5.5, 5.5.6, 5.5.7, 5.5.8, 5.5.9, 5.5.13, 5.5.15 sprawdzić, czy

spełnione są założenia twierdzenia

(a)

Orego,

(b)

Diraca,

(c)

o krawędziach (5.6.4).

Zadanie 5.7.4

Dla grafów z zadań 5.5.2, 5.5.5, 5.5.6, 5.5.7, 5.5.8, 5.5.9, 5.5.13, 5.5.15 wyznaczyć, o

ile istnieje drogę

(a)

Hamiltona.

(b)

Eulera.

Zadanie 5.7.5

Czy jest możliwe, aby biedronka poruszająca się wzdłuż krawędzi sześcianu przeszła

każdą krawędź dokładnie raz? Odpowiedź uzasadnij.

Zadanie 5.7.6

Czy jest możliwe, aby mrówka poruszająca się wzdłuż krawędzi czworościanu przeszła

każdą krawędź dokładnie raz? Odpowiedź uzasadnij.

Zadanie 5.7.7

Które grafy pełne mają cykle Eulera? Odpowiedź uzasadnij.

Zadanie 5.7.8

Które grafy pełne mają cykle Hamiltona? Odpowiedź uzasadnij.

Zadanie 5.7.9

Dla jakich n koło W

jest grafem Eulera?

Zadanie 5.7.10

Dla n  4 niech P

będzie grafem powstałym z grafu pełnego K

n−1

przez dodanie

jednego wierzchołka w środku jakiejś krawędzi grafu K

n−1

. Uzasadnij, że P

jest grafem Hamiltona.

Zadanie 5.7.11

Dany jest graf zwany grafem Gr¨

otzscha

(a)

Sprawdzić, czy w grafie istnieje droga Eu-
lera i w przypadku odpowiedzi pozytyw-
nej wyznaczyć tę drogę wykorzystując al-
gorytm Fleury’ego.

(b)

Sprawdzić, czy w grafie spełnione są zało-
żenia twierdzenia, Diraca, Orego i o kra-
wędziach.

(c)

Wyznaczyć drogę Hamiltona, o ile istnieje.

ROZDZIAŁ 5. TEORIA GRAFÓW

Zadanie 5.7.12

Dany jest graf G o macierzy sąsiedztwa





























(a)

Sprawdzić, czy spełnione są założenia twierdzenia Di-
raca i Orego.

(b)

Wykorzystując algorytm Fleury’ego wyznaczyć drogę
Eulera.

5.8.

Drzewa

Definicja 5.8.1

Drzewem nazywamy graf spójny i acykliczny.

Graf, którego każda składowa jest drzewem nazywamy lasem.

Twierdzenie 5.8.2

Niech G będzie grafem prostym mającym więcej niż jeden wierzchołek. Następu-

jące warunki są równoważne:

(a)

G jest drzewem,

(b)

każde dwa różne wierzchołki są połączone dokładnie jedną drogą prostą,

(c)

G jest spójny, a po usunięciu dowolnej krawędzi przestaje być spójny,

(d)

G jest acykliczny, a po dodaniu jednej krawędzi przestaje być acykliczny.

Twierdzenie 5.8.3

Drzewo skończone, mające co najmniej jedną krawędź, ma co najmniej dwa liście.

Twierdzenie 5.8.4

Drzewo mające n wierzchołków ma dokładnie n − 1 krawędzi.

Twierdzenie 5.8.5

Niech G będzie grafem prostym o n wierzchołkach. Wtedy następujące warunki

są równoważne:

(a)

G jest drzewem,

(b)

G jest grafem acyklicznym mającym n − 1 krawędzi,

(c)

G jest spójnym mającym n − 1 krawędzi.

Definicja 5.8.6

Maksymalny podgraf spójnego grafu G nazywamy drzewem spinającym lub den-

drytem.
Każdą krawędź drzewa spinającego T nazywamy gałęzią.
Krawędź grafu G, która nie jest gałęzią drzewa spinającego T nazywamy cięciwą względem drzewa
spinającego T

Twierdzenie 5.8.7

Jeśli graf spójny ma n wierzchołków i m krawędzi, to każde jego drzewo spinające

ma n − 1 gałęzi i m − n + 1 cięciw.

Twierdzenie 5.8.8

Każdy skończony graf spójny ma co najmniej jedno drzewo spinające.

Algorytm wyznaczania dendrytu

DANE: dowolny wierzchołek v skończonego grafu G
WYNIKI: zbiór krawędzi E drzewa spinającego składowej grafu G zawierającej wierzchołek v
Zmienna pomocnicza: ciąg V odwiedzanych wierzchołków, ostatecznie V = V (G)

• V := {v}, E := ε

5.8. DRZEWA

• Dopóki istnieją krawędzie w grafie G łączące wierzchołki zbioru V z wierzchołkami nie należą-

cymi do V ,

wykonuj wybierz taką krawędź {u, w} łączącą u ∈ V z wierzchołkiem w /

∈ V ,

dołącz w do V i {u, w} do E.

Twierdzenie 5.8.9

Niech G będzie grafem prostym o n wierzchołkach. Wtedy następujące warunki

są równoważne:

(a)

G jest drzewem,

(b)

G jest grafem acyklicznym mającym n − 1 krawędzi,

(c)

G jest spójnym mającym n − 1 krawędzi.

Definicja 5.8.10

Drzewo, którego wierzchołkami są dodatnie liczby całkowite nazywamy drzewem

oznakowanym.

Dla danego drzewa oznakowanego T tworzymy dwa ciągi: ciąg liczb P

= (a

, a

, . . . , a

n−2

) zwany

kodem Pr¨

ufera oraz ciąg drzew T

, T

, . . . , T

n−1

spełniające warunki:

(1)

= T ,

(2)

dla każdego i ∈ {1, 2, . . . , n − 2} liczba a

jest wierzchołkiem drzewa T

sąsiednim do wierzchołka

tego drzewa, który jest wierzchołkiem stopnia pierwszego o najmniejszej wartości,

(3)

drzewo T

i+1

powstaje z drzewa T

przez usunięcie wierzchołka b

oraz krawędzi łączącej ten

wierzchołek z wierzchołkiem a

Algorytm wyznaczania drzewa o danym kodzie Pr¨

ufera

DANE: n, P

= (a

, a

, . . . , a

n−2

)

WYNIKI: drzewo o danym kodzie Pr¨

ufera

Kładziemy V

= {1, 2, . . . , n}, A

= (a

, a

, . . . , a

n−2

)

Dla kolejnych wartości i = 1, 2, . . . , n − 2 wykonujemy następujące czynności:

2.1.

kładziemy b

równe najmniejszemu elementowi zbioru V

, który nie jest elementem ciągu

2.2.

łączymy wierzchołki a

oraz b

2.3.

kładziemy V

i+1

= V

− {b

} oraz usuwamy element a

z ciągu A

łączymy ze sobą pozostałe wierzchołki tworzące zbiór V

n−1

Twierdzenie 5.8.11 Cayleya

Istnieje n

n−2

różnych drzew oznakowanych mających n wierzchołków.

Wniosek 5.8.12

Graf pełny o n wierzchołkach ma n

n−2

drzew spinających.

Definicja 5.8.13

Drzewo, w którym wyróżniono jeden z wierzchołków nazywamy drzewem z wy-

różnionym korzeniem, a ten wyróżniony wierzchołek nazywa się korzeniem.
Drzewo z wyróżnionym korzeniem, w którym oprócz korzenia i liści pozostałe wierzchołki mają stopień
równy trzy nazywa się drzewem przeszukiwań binarnych.

Drzewo z wyróżnionym korzeniem jako graf skierowany ma następujące własności:

ROZDZIAŁ 5. TEORIA GRAFÓW

liście są wierzchołkami nie będącymi początkiem żadnej krawędzi,

korzeń jest wierzchołkiem nie będącym końcem żadnej krawędzi,

jeśli (v, w) jest krawędzią, to v nazywamy rodzicem lub przodkiem, a w nazywamy dzieckiem
lub potomkiem,

każdy wierzchołek poza korzeniem ma jednego rodzica,

każdy rodzic może mieć kilkoro dzieci, a w drzewie przeszukiwań binarnych co najwyżej dwoje.

Definicja 5.8.14

Numer poziomu wierzchołka - długość drogi prostej od korzenia do wierzchołka.

Wysokość drzewa - największy numer poziomu wierzchołka.

Rodzaje drzew z wyróżnionym korzeniem

Drzewo o m rozgałęzieniach - drzewo, w którym każdy rodzic, ma co najwyżej m dzieci.
Pełne drzewo o m rozgałęzieniach - wszystkie liście mają ten sam numer poziomu.
Drzewo binarne - pełne drzewo o dwóch rozgałęzieniach.

Definicja 5.8.15

Drzewo z wyróżnionym korzeniem, w którym każdemu liściowi przyporządkowano

liczbę rzeczywistą zwaną wagą nazywa się drzewem z wagami.
Wagą drzewa o n liściach nazywa się liczbę daną wzorem

W (T ) =

i=1

gdzie w

oznacza wagę i-tego liścia, a l

-numer jego poziomu.

Algorytm Huffmana

DANE: t  2, (w

, w

, . . . , w

) niemalejący ciąg liczb nieujemnych

WYNIKI: optymalne drzewo binarne T (w

, . . . , w

)

Jeżeli t = 2, to optymalnym drzewem binarnym jest drzewo z dwoma liśćmi o wagach w

i w

w przeciwnym razie wykonujemy następujące kroki:

tworzymy ciąg (w

, w

, . . . , w

) i porządkujemy go niemalejąco, otrzymując ciąg (u

, u

, . . . , u

t−1

wykonujemy algorytm Huffmana H(t − 1, u

, u

, . . . , u

t−1

III

przekształcamy drzewo T (u

, . . . , u

t−1

) w drzewo T (w

, . . . , w

), zastępując w T (u

, . . . , u

t−1

)

liść o wadze w

+ w

poddrzewem mającym dwa liście o wagach w

i w

Wychodzimy z algorytmu H(t, w

, . . . , w

)

Definicja 5.8.16

Kodem prefiksowym nazywamy kod, w którym żadne słowo kodowe nie jest

początkiem (prefiksem) żadnego innego słowa kodowego.

Kod prefiksowy można otrzymać poprzez konstrukcję drzewa binarnego spełniającego warunki:

krawędzie łączące dowolnego rodzica z jego dziećmi mają etykiety 0 oraz 1,

każdy liść o numerze poziomu n ma etykietę b

. . . b

, która jest ciągiem etykiet kolejnych

krawędzi w drodze od korzenia do tego liścia.

5.8. DRZEWA

Zadania

Zadanie 5.8.1

Pewne drzewo ma dwa wierzchołki stopnia 4, jeden wierzchołek stopnia 3 i jeden

wierzchołek stopnia 2. Jeśli pozostałe wierzchołki są stopnia 1, to ile wierzchołków jest w tym grafie?
Narysuj to drzewo.

Zadanie 5.8.2

Pewne drzewo ma dwa wierzchołki stopnia 5, trzy wierzchołki stopnia 3, dwa wierz-

chołki stopnia 2 i resztę wierzchołków stopnia 1. Oblicz ile wierzchołków jest w tym grafie?

Zadanie 5.8.3

Wiadomo, że pewien graf G, który jest acykliczny i spójny, ma trzy wierzchołki stopnia

siódmego, pięć wierzchołków stopnia drugiego, czterdzieści jeden wierzchołków stopnia pierwszego i
resztę wierzchołków stopnia ósmego. Ile wierzchołków ma ten graf?

Zadanie 5.8.4

Wyznacz liczbę dendrytów w grafie o podanej macierzy sąsiedztwa, a następnie na-

rysuj diagram każdego z dendrytów

(a)



















(b)



















Zadanie 5.8.5

Dany jest graf o funkcji incydencji Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

Ψ(e

) = {v

, v

}, Ψ(e

) = {v

, v

}. Wyznaczyć liczbę dendrytów w tym grafie, a następnie naszkicować

diagramy wszystkich tych dendrytów.

Zadanie 5.8.6

Narysować diagramy oraz wyznaczyć macierze sąsiedztwa i incydencji drzew oznako-

wanych o następujących kodach Pr¨

ufera

(a)

(3, 3, 3, 3, 9, 3, 3, 3),

(d)

(1, 1, 1, 1, 1, 1, 1, 9),

(b)

(9, 1, 1, 1, 1, 1, 1, 1),

(e)

(1, 2, 3, 4),

(c)

(1, 3, 5, 7, 9, 7, 5, 1),

Zadanie 5.8.7

Dane jest drzewo T o kodzie Pr¨

ufera (1, 1, 2, 2, 2, 1).

(a)

Zbudować graf T o podanym kodzie.

(b)

Zbudować nowy graf G z drzewa T łącząc krawędzią, każdego liścia z niesąsiednim wierzchołkiem
najwyższego stopnia.

(c)

Zbadać, czy w grafie G istnieje droga Eulera i w przypadku odpowiedzi pozytywnej wykorzystując
algorytm Fleury’ego wyznaczyć tę drogę.

(d)

Sprawdzić, czy spełnione są wszystkie założenia twierdzenia Orego i Diraca, a następnie wyzna-
czyć, o ile istnieje, drogę Hamiltona w grafie G.

Zadanie 5.8.8

Dany jest graf G o macierzy sąsiedztwa



















Wierzchołki tego grafu oznaczono liczbami naturalnymi w następujący sposób: wierzchołkowi odpo-
wiadającemu pierwszemu wierszowi macierzy nadano numer 3, drugiemu-2, trzeciemu-1, czwartemu-5,
piątemu-4.

(a)

Wyznaczyć liczbę dendrytów w grafie G, a następnie narysować diagram każdego z dendrytów.

(b)

Podać kody Pr¨

ufera wszystkich dendrytów.

ROZDZIAŁ 5. TEORIA GRAFÓW

Zadanie 5.8.9

Obliczyć ile rodziców i ile liści ma pełne drzewo regularne o m rozgałęzieniach i

wysokości h.

Zadanie 5.8.10

Obliczyć ile wierzchołków i ile liści ma pełne drzewo binarne o wysokości h.

Zadanie 5.8.11

Udowodnić, że jeśli t jest liczbą liści, a p liczbą rodziców w drzewie pełnym o m

rozgałęzieniach, to t = (m − 1)p + 1 niezależnie od wysokości drzewa.

Zadanie 5.8.12

Zbudować optymalne drzewo binarne dla następujących zbiorów wag i obliczyć wagi

tych drzew.

(a)

(1, 3, 4, 6, 9, 13),

(b)

(2, 4, 5, 8, 13, 15, 18, 25),

(c)

(1, 1, , 2, 3, 5, 8, 13, 21, 34).

Zadanie 5.8.13

Wyznaczyć optymalny kod prefiksowy dla tekstu

• MATEMATYKA DYSKRETNA

• KOD PREFIKSOWY

• ALGORYTM HUFFMANA

• KOBYŁA MA MAŁY BOK

• MOŻE JEŻ ŁŻE JEŻOM

• KOD PR ¨

UFERA

• WIELOMIAN CHROMATYCZNY

• RELACJA REKURENCYJNA