Matematyka dyskretna wykład

Wstęp do matematyki

dyskretnej

Wstęp do matematyki

dyskretnej

Beata Fałda

Lech Gruszecki

Lublin 2010

Spis treści

Wstęp

Logika i teoria zbiorów

1.1

Wprowadzenie do klasycznego rachunku zdań

. . . . .

1.2

Formalne ujęcie rachunku zdań

. . . . . . . . . . . . .

1.3

Elementy wielowartościowych rachunków zdań . . . . .

1.4

Klasyczny rachunek kwantyfikatorowy . . . . . . . . . .

1.5

Zbiory i ich własności . . . . . . . . . . . . . . . . . . .

Relacje i funkcje

2.1

Podstawowe własności relacji . . . . . . . . . . . . . . .

2.2

Relacje pomiędzy elementami zbiorów skończonych

. .

2.3

Relacje równoważności . . . . . . . . . . . . . . . . . .

2.4

Relacje porządku . . . . . . . . . . . . . . . . . . . . .

2.5

Funkcje i ich własności . . . . . . . . . . . . . . . . . .

Zbiór liczb naturalnych i indukcja

3.1

Zbiór liczb naturalnych. Definiowanie przez indukcję . .

3.2

Funkcje rekurencyjne . . . . . . . . . . . . . . . . . . .

3.3

Zastosowanie rekurencji: automaty skończone
i ich języki . . . . . . . . . . . . . . . . . . . . . . . . .

Spis treści

Kraty. Algebry Boole’a i funkcje booleowskie

4.1

Kraty i ich własności . . . . . . . . . . . . . . . . . . .

4.2

Algebry Boole’a . . . . . . . . . . . . . . . . . . . . . .

4.3

Formuły i funkcje booleowskie . . . . . . . . . . . . . .

Zbiory skończone i metody zliczania elementów tych
zbiorów

5.1

Nieformalne wprowadzenie do metod
kombinatorycznych . . . . . . . . . . . . . . . . . . . .

5.2

Formalne ujęcie podstaw kombinatoryki

. . . . . . . . 102

5.3

Współczynniki dwumianowe i wielomianowe . . . . . . 111

5.4

Zasada włączeń i wyłączeń . . . . . . . . . . . . . . . . 116

5.5

Zasada szufladkowa Dirichleta . . . . . . . . . . . . . . 121

Podziały i permutacje. Liczby Stirlinga i Bella

125

6.1

Liczenie podziałów . . . . . . . . . . . . . . . . . . . . 125

6.2

Rozkłady liczb

. . . . . . . . . . . . . . . . . . . . . . 128

6.3

Permutacje

. . . . . . . . . . . . . . . . . . . . . . . . 131

6.4

Liczby specjalne . . . . . . . . . . . . . . . . . . . . . . 136

Główne pojęcia teorii grafów

141

7.1

Nieformalne wprowadzenie do teorii grafów . . . . . . . 141

7.2

Podstawowe definicje teorii grafów . . . . . . . . . . . . 150

7.3

Spójność grafów . . . . . . . . . . . . . . . . . . . . . . 163

Poruszanie się po grafach

167

8.1

Grafy Eulera

. . . . . . . . . . . . . . . . . . . . . . . 167

8.2

Grafy Hamiltona . . . . . . . . . . . . . . . . . . . . . 172

8.3

Grafy z wagami . . . . . . . . . . . . . . . . . . . . . . 176

Drzewa i digrafy

183

9.1

Podstawowe pojęcia teorii drzew . . . . . . . . . . . . . 183

9.2

Drzewa rozpinające grafy . . . . . . . . . . . . . . . . . 188

9.3

Digrafy . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

10 Zliczanie grafów. Kilka wybranych problemów

201

Spis literatury

211

Wstęp

Matematyka dyskretna stosunkowo niedawno znalazła swoje miej-

sce wśród innych przedmiotów matematycznych, które wykładane są
na studiach matematycznych i informatycznych. Obejmuje ona zarów-
no pewne elementy tradycyjnych działów matematyki, jak np. logika,
algebra czy kombinatoryka, jak też w jej skład zaliczane są zagadnie-
nia z teorii grafów oraz teorii automatów. Niewątpliwie kluczową rolę
w powstaniu tej, w istocie, nowej dziedziny matematyki odegrał rozwój
technik komputerowych. Matematyka dyskretna jest traktowana coraz
częściej jako jeden z matematycznych fundamentów nauk informatycz-
nych. W polu jej zainteresowania znajdują się przede wszystkim zbiory
skończone i przeliczalne, w przeciwieństwie np. do analizy matematycz-
nej, w której podstawową rolę odgrywają zbiory liczb rzeczywistych
i zespolonych, a więc nieprzeliczalne.

Książka, którą oddajemy do rąk Czytelnika, zawiera wybór za-

gadnień poruszanych w ramach kursu matematyki dyskretnej. Wśród
nich są tematy z zakresu podstaw matematyki dotyczące logiki, teorii
zbiorów, relacji i funkcji. W dalszej kolejności wprowadzony jest zbiór
liczb naturalnych, a także omówione są problemy związane z definio-
waniem przez rekurencję; jako zastosowanie tej problematyki zapre-
zentowane zostały zagadnienia z dziedziny teorii automatów. Kolejne
rozdziały poświęcone są metodom zliczania elementów zbiorów skoń-
czonych. Zostały w nich omówione podstawowe wzory kombinatorycz-

Wstęp

ne, zasada włączeń i wyłączeń oraz zasada szufladkowania Dirichleta.
Książka kończy się przedstawieniem wybranych elementów z teorii gra-
fów; przedstawione są definicje i twierdzenia dotyczące grafów Eulera,
Hamiltona, grafów z wagami, digrafów oraz drzew. Ostatni rozdział
zawiera kilka wybranych zagadnień dotyczących zliczania grafów.

Mamy nadzieję, że duża ilość przykładów zamieszczonych w książce

przyczyni się do lepszego zrozumienia treści teoretycznych.

Autorzy

Logika i teoria zbiorów

1.1

Wprowadzenie do klasycznego
rachunku zdań

Zgodnie z zasadami klasycznej logiki dwuwartościowej, zdaniami

w sensie logicznym są te zdania orzekające, o których możemy powie-
dzieć, że są prawdziwe lub fałszywe. W dalszym ciągu zdania w sensie
logicznym oznaczać będziemy przy użyciu symboli

p, q, r, s, t, ...,

nazywanych także zmiennymi zdaniowymi .

Prawdę i fałsz oznaczać będziemy, jak to jest powszechnie przyjęte,

za pomocą znaków

1 i 0.

Prawdziwość zdania, powiedzmy zdania p, zapisywać będziemy na-

stępująco

w(p) =

Jeśli natomiast zdanie p jest fałszywe, to stosować będziemy zapis

w(p) =

Logika i teoria zbiorów

Funkcję w przyporządkowującą zmiennym zdaniowym liczby

0 i 1

nazywać będziemy wartościowaniem.

Zmienne zdaniowe możemy łączyć przy zastosowaniu spójników

zdaniowych, nazywanych też funktorami zdaniotwórczymi .

Najczęściej stosowanymi spójnikami są

∼

nieprawda, że

∧

∨

lub

⇒

jeżeli, to

⇔

wtedy i tylko wtedy, gdy

Noszą one odpowiednio nazwę: negacji , koniunkcji , alternatywy,

implikacji i równoważności (ekwiwalencji). Ich znaczenie w obrębie
klasycznego rachunku zdań nawiązuje do znaczenia odpowiadających
im wyrażeń (w drugiej kolumnie) języka naturalnego. Oczywiście, ję-
zyk potoczny obciążony jest, trudną do pozbycia się, wieloznacznością,
w związku z czym znaczenie spójników logicznych należy uznać jedynie
za pewną idealizację stworzoną na potrzeby logiki formalnej i matema-
tyki.

Sposób rozumienia spójników logicznych ilustrują poniższe tabele

w(p)

w(∼ p)

w(p)

w(q)

w(p ∧ q)

w(p ∨ q)

w(p ⇒ q)

w(p ⇔ q)

Tak więc, zdanie ∼ p jest prawdziwe tylko wtedy, gdy zdanie p jest

fałszywe. Zdanie p ∧ q jest prawdziwe wtedy i tylko wtedy, gdy obydwa
zdania p i q są prawdziwe. Alternatywa p ∨ q jest zdaniem prawdziwym
tyko wtedy, gdy co najmniej jedno ze zdań p oraz q jest prawdzie.
Z kolei implikacja p ⇒ q jest prawdziwa, gdy jej poprzednik p jest

Wprowadzenie do klasycznego rachunku zdań

zdaniem fałszywym lub gdy następnik q jest zdaniem prawdziwym.
Równoważność p ⇔ q jest prawdziwa, gdy oba zdania p oraz q są
zarazem prawdziwe lub fałszywe.

W dalszym ciągu wszystkie poprawnie zbudowane wyrażenia kla-

sycznego rachunku zdań, złożone ze zmiennych zdaniowych, spójników
i ewentualnie nawiasów, nazywać będziemy formułami klasycznego ra-
chunku zdań (w skrócie: k.r.z.).

A zatem formułami k.r.z. są na przykład

[(p ∨ q) ∧ r] ⇒ q

(1.1)

czy

[∼ p ∧ (q ⇒ p)] ∨ p.

(1.2)

Formułami k.r.z. nie są natomiast

p ⇒,

(( p,

∧∨ ⇒ p.

Aby uniknąć nadmiernej ilości nawiasów, przyjmiemy umowę, zgo-

dnie z którą najsilniej wiążącym jest znak negacji, następnie znak ko-
niunkcji, a w dalszej kolejności znak alternatywy, który wiąże silniej
od symboli implikacji i równoważności.

Na podstawie powyższej umowy formuły (1.1) i (1.2) możemy za-

pisać odpowiednio w postaci

(p ∨ q) ∧ r ⇒ q

∼ p ∧ (q ⇒ p) ∨ p.

Wśród formuł k.r.z. wyróżniamy te, które niezależnie od funkcji

wartościowania w, są zawsze prawdziwe. Nazywamy je tautologiami
k.r.z. Formuły, które są zawsze fałszywe nazywamy kontrtautologiami,
pozostałe zaś formuły określamy jako kontyngentne.

Szczególne znaczenie mają tautologie. Aby sprawdzić, czy formuła

jest tautologią, stosujemy znaną ze szkoły metodę tabelkową.

Dla przykładu, by sprawdzić czy formuła

f := (p ⇒ q) ⇒ (p ∧ q ⇒ q)

jest tautologią, konstruujemy tabelę

Logika i teoria zbiorów

w(p)

w(q)

w(p ⇒ q)

w(p ∧ q)

w(p ∧ q ⇒ q)

w(f )

Ponieważ ostatnia kolumna tabeli zawiera tylko jedności, więc for-

muła f jest tautologią.

Korzystając z metody tabelkowej, można dowieść szeregu ważnych

tautologii. Oto niektóre z nich:

◦

(p ⇒ q) ⇒ [(r ⇒ p) ⇒ (r ⇒ q)]

(prawo sylogizmu

hipotetycznego)

◦

[p ⇒ (q ⇒ r)] ⇒ [q ⇒ (p ⇒ r)]

(prawo komutacji)

◦

[p ⇒ (p ⇒ q)] ⇒ (p ⇒ q)

(prawo skracania)

◦

(p ⇒ q) ⇒ (∼ q ⇒∼ p)

(prawo transpozycji)

◦

p ⇒ (∼ p ⇒ q)

(prawo Dunsa Szkota)

◦

(p ⇒∼ p) ⇒∼ p

(prawo Claviusa)

◦

[p ⇒ (q ⇒ r)] ⇒ (p ∧ q ⇒ r)

(prawo importacji)

◦

(p ∧ q ⇒ r) ⇒ [p ⇒ (q ⇒ r)]

(prawo eksportacji)

◦

∼ (p ∧ ∼ p)

(prawo sprzeczności)

◦

p ∨ ∼ p

(prawo wyłączonego środka)

◦

∼∼ p ⇔ p

(prawo podwójnego przeczenia)

◦

p ∧ q ⇔ q ∧ p

(prawo przemienności koniunkcji)

◦

p ∨ q ⇔ q ∨ p

(prawo przemienności alternatywy)

◦

(p ⇔ q) ⇔ (q ⇔ p)

(prawo przemienności

równoważności)

◦

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

(prawo łączności koniunkcji)

◦

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

(prawo łączności alternatywy)

Wprowadzenie do klasycznego rachunku zdań

◦

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

(prawo rozdzielności

alternatywy względem koniunkcji)

◦

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

(prawo rozdzielności

koniunkcji względem alternatywy)

◦

∼ (p ∧ q) ⇔

(∼ p ∨ ∼ q)

∼ (p ∨ q) ⇔

(∼ p ∧ ∼ q)

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











(prawa De Morgana)

◦

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

(prawo obustronnej

negacji równoważności)

Przy wykazywaniu, że formuła jest tautologią można niekiedy po-

służyć się metodą skróconą. Zgodnie z nią, zakłada się, że dla pewnego
wartościowania w wartość formuły jest równa zeru. Jeśli założenie to
prowadzi do sprzeczności, to stąd wynika, że badana formuła jest tau-
tologią; w przeciwnym przypadku nią nie jest.

Dla przykładu, wykażemy metodą skróconą, że formuła

(p ⇒ q) ⇒ [(r ⇒ p) ⇒ (r ⇒ q)]

jest tautologią.

Dowód przeprowadzimy, numerując kolejne kroki rozumowania,

począwszy od założenia, że dla pewnego wartościowania formuła jest
fałszywa.

◦

w ((p ⇒ q) ⇒ [(r ⇒ p) ⇒ (r ⇒ q)]) =

(założenie)

◦

w(p ⇒ q) =

(wynika z 1

◦

)

◦

w((r ⇒ p) ⇒ (r ⇒ q)) =

(wynika z 1

◦

)

◦

w(r ⇒ p) =

(wynika z 3

◦

)

◦

w(r ⇒ q) =

(wynika z 3

◦

)

◦

w(r) =

(wynika z 5

◦

)

◦

w(q) =

(wynika z 5

◦

)

◦

w(p) =

(wynika z 2

◦

i 7

◦

)

◦

w(p) =

(wynika z 4

◦

i 6

◦

)

Logika i teoria zbiorów

Otrzymaliśmy zatem sprzeczność. Skąd wynika, że założenie 1

◦

jest

nieprawdziwe, czyli że badana formuła jest tautologią.

Zauważmy, że niektóre ze spójników logicznych mogą być wyrażo-

ne przy zastosowaniu spójników pozostałych. Na przykład, posługując
się negacją i implikacją, można zdefiniować koniunkcję, alternatywę
i równoważność:

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

p ∨ q ⇔ (∼ p ⇒ q),

p ⇔ q ⇔ (∼ ((p ⇒ q) ⇒∼ (q ⇒ p))).

Jak nietrudno zauważyć, istnieją 2

= 4 różne spójniki (funktory)

jednoargumentowe i 2

= 16 różnych spójników dwuargumentowych.

Wśród tych ostatnich warto wymienić alternatywę wykluczającą

Y (⊕),

dysjunkcję Sheffera / oraz funktor binegacji czyli jednoczesnego zaprze-
czenia, oznaczmy go tu symbolem

Z. Znaczenie wymienionych funkto-

rów może być określone za pomocą tabelek, można je także zdefiniować
przy zastosowaniu funktorów wprowadzonych wcześniej.

I tak, alternatywę wykluczającą można określić za pomocą tabelki

w(p)

w(q)

w(p Y q)

Nietrudno zauważyć, że

p Y q ⇔ (∼ (p ⇔ q)).

Dysjunkcję Sheffera określa tabelka

w(p)

w(q)

w(p/q)

Wprowadzenie do klasycznego rachunku zdań

A zatem

p/q ⇔ ∼ (p ∧ q).

Z kolei funktorowi binegacji odpowiada tabelka

w(p)

w(q)

w(p Z q)

Stąd

p Z q ⇔ ∼ (p ∨ q).

Funktor Sheffera oraz funktor binegacji mają szczególną własność:

jako jedyne - każdy z osobna - mogą być wykorzystane do zdefiniowania
pozostałych funktorów dwuargumentowych oraz negacji.

Rzeczywiście

∼ p ⇔ (p/p).

Z kolei

p ∨ q ⇔ [(p/p)/(q/q)].

Korzystając z jednego z praw De Morgana, które stwierdza, że

p ∧ q ⇔ ∼ (∼ p ∨ ∼ q), można wykazać, iż

p ∧ q ⇔

(p/p)

(q/q)

i .

. h

(p/p)

(q/q)

Jeżeli weźmiemy pod uwagę równoważność

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

to zdanie warunkowe możemy, przy zastosowaniu symbolu Sheffera,
wyrazić następująco

(p ⇒ q) ⇔

(p/p)

(q/q)

Definicję równoważności oraz pozostałych spójników dwuargumen-

towych (tzn.

Y oraz Z) pozostawiamy Czytelnikowi.

W podobny sposób możliwe jest zdefiniowanie, przy zastosowaniu

symbolu binegacji

Z, wszystkich spójników dwuargumentowych oraz

negacji.

Logika i teoria zbiorów

1.2

Formalne ujęcie rachunku zdań

Zaczniemy od definicji alfabetu klasycznego rachunku zdań

(por. na przykład [13, s. 34-42]).

Definicja 1.1 Przez alfabet k.r.z. rozumiemy zbiór

A = V ∪ S ∪ P,

gdzie

V = {p

, p

, ..., p

, ...}

jest zbiorem zmiennych zdaniowych,

S = {∼, ∧, ∨, ⇒, ⇔}

jest zbiorem zmiennych logicznych, natomiast

P = {(, ), [, ]}

jest zbiorem symboli pomocniczych, czyli nawiasów.

Uwaga. Zamiast zmiennych p

, p

, ... będziemy, dla uczynienia

zapisu bardziej czytelnym, pisać: p, q, r, s, ...

W dalszym ciągu zdefiniujemy pojęcie formuły k.r.z.

Definicja 1.2 Formułami k.r.z. są:

a) dowolna zmienna zdaniowa,

b) jeśli f

i f

są formułami k.r.z., to formułami k.r.z. są również

(i jedynie) formuły:

(i) ∼ (f

(ii) (f

) ∧ (f

(iii) (f

) ∨ (f

(iv) (f

) ⇒ (f

(v) (f

) ⇔ (f

Zbiór wszystkich formuł k.r.z. oznaczać będziemy symbolem F .

Formalne ujęcie rachunku zdań

Definicja 1.3 Wartościowaniem nazywamy dowolną funkcję

w : V → {

0, 1}.

Definicja 1.4 Dowolną funkcję

w : F → {

0, 1}

nazywamy interpretacją k.r.z.

Twierdzenie 1.1 Dowolne wartościowanie w można rozszerzyć jed-
noznacznie ze zbioru V na zbiór F , tak by było interpretacją.

Dowód. Załóżmy, że f

i f

są formułami, natomiast w jest wartościo-

waniem; w można rozszerzyć zgodnie z zależnościami

w(∼ f

) =

w. i t.w.g.

w(f

) =

w(f

∧ f

) =

w. i t.w.g.

w(f

) = w(f

) =

w(f

∨ f

) =

w. i t.w.g.

w(f

) =

1 lub w(f

) =

w(f

⇒ f

) =

1 w. i t.w.g. w(f

) =

0 lub w(f

) =

w(f

⇔ f

) =

1 w. i t.w.g. w(f

) = w(f

)

Definicja 1.5 W zbiorze {

0, 1} zdefiniujmy funkcję

¬ : {

0, 1} → {0, 1},

przy czym ¬(

0) = 1, ¬(1) = 0. Funkcję tę nazywać będziemy dopełnie-

niem lub negacją.

Niech ponadto

∩ : {

0, 1} × {0, 1} → {0, 1}

oraz

∪ : {

0, 1} × {0, 1} → {0, 1},

gdzie

∩(a, b) = min{a, b}

oraz

∪ (a, b) = max{a, b}.

Funkcje te nazywać będziemy iloczynem i suma booleowską.

Logika i teoria zbiorów

Uwaga. Zamiast pisać ¬(a), ∩(a, b), ∪(a, b), będziemy pisać ¬a, a ∩ b,
a ∪ b, gdzie a, b ∈ {

0, 1}.

Uwaga. Przy zastosowaniu powyższych funkcji można zdefiniować
funkcje

a → b

oraz

a ↔ b

jako równe odpowiednio wyrażeniom (¬a)∪b oraz ((¬a)∩(¬b))∪(a∩b).

W dalszym ciągu zakładać będziemy, by uniknąć stosowania nad-

miernej ilości nawiasów, że symbol ¬ wiąże silniej niż symbol ∩, a ten
z kolei wiąże silniej niż symbol ∪; jeszcze słabiej wiążą symbole ⇒
oraz ⇔.

Twierdzenie 1.2 Dla dowolnych formuł f

i f

zachodzą równości

¬w(f

) = w(∼ f

w(f

) ∩ w(f

) = w(f

∧ f

w(f

) ∪ w(f

) = w(f

∨ f

w(f

) → w(f

) = w(f

⇒ f

w(f

) ↔ w(f

) = w(f

⇔ f

Definicja 1.6 Formuły f , takie że dla dowolnej interpretacji w za-
chodzą równości w(f ) =

1, nazywamy tautologiami. Jeśli natomiast

dla dowolnej interpretacji w mają miejsce równości w(f ) =

0, to for-

muły takie nazywamy kontrtautologiami. Jeśli dla pewnej interpretacji
w

, w

(f ) =

1, a dla innej interpretacji w

, w

(f ) =

0, to formułę f

nazywamy kontyngentą.

Przedstawimy teraz równoważne, w stosunku do metody tabelko-

wej (wykorzystującej pojęcie interpretacji), podejście do k.r.z. Jest to
podejście aksjomatyczne.

Polega ono na wyróżnieniu pewnej liczby tautologii, w oparciu

o które, za pomocą odpowiednich i zarazem ściśle określonych metod
wnioskowania, wyprowadza się wszystkie pozostałe tautologie (i tylko
te tautologie).

Istnieje wiele równoważnych systemów aksjomatycznych k.r.z. Ja-

ko jeden z nich przedstawimy system pochodzący od Davida Hilberta
i Paula Bernaysa (por. [1, s. 42-65]).

Formalne ujęcie rachunku zdań

Aksjomaty klasycznego rachunku zdań

A.1

◦

p ⇒ (q ⇒ p)

(prawo poprzednika)

A.2

◦

[p ⇒ (q ⇒ r)] ⇒ [(p ⇒ q) ⇒ (p ⇒ r)] (prawo Fregego)

A.3

◦

(p ⇒ q) ⇒ (∼ q ⇒∼ p)

(prawo transpozycji)

A.4

◦

∼∼ p ⇒ p

(prawo podwójnego przeczenia)

A.5

◦

p ⇒∼∼ p

(odwrotne prawo podwójnego przeczenia)

A.6

◦

p ∧ q ⇒ p

(prawo symplifikacji)

A.7

◦

p ∧ q ⇒ q

(drugie prawo symplifikacji)

A.8

◦

(p ⇒ q) ⇒ [(p ⇒ r) ⇒ (p ⇒ q ∧ r)]

(prawo mnożenia

następników)

A.9

◦

p ⇒ p ∨ q

(prawo addycji)

A.10

◦

q ⇒ p ∨ q

(drugie prawo addycji)

A.11

◦

(p ⇒ r) ⇒ [(q ⇒ r) ⇒ (p ∨ q ⇒ r)] (prawo dodawania

poprzedników)

A.12

◦

(p ⇔ q) ⇒ (q ⇒ p)

(aksjomaty

A.13

◦

(p ⇔ q) ⇒ (q ⇒ p)

równoważności)

A.14

◦

(p ⇒ q) ⇒ [(q ⇒ p) ⇒ (p ⇔ q)]

Wszystkie tautologie k.r.z. wynikają z powyższych aksjomatów po-

przez użycie dwóch reguł wnioskowania.

Pierwszą z nich jest reguła odrywania (modus ponens), która od

prawdziwych formuł f

oraz f

⇒ f

prowadzi do formuły f

. Regułę

tę zapisujemy symbolicznie w postaci

, f

⇒ f

(1.3)

Logika i teoria zbiorów

gdzie nad kreską wniosku umieszczone zostały symbole przesłanek,
a poniżej kreski symbol wniosku.

Drugą regułą jest reguła podstawiania, która od tautologii f

, gdzie

występuje zmienna p

, prowadzi do formuły f

(g, p

). Ta zaś powstaje

z f

poprzez zastąpienie p

przez dowolną formułę g. Regułę tę zapi-

sujemy następująco

(g, p

)

(1.4)

Zastosujmy powyższe reguły do wyprowadzenia z aksjomatów pew-

nej tezy.

Przykład. Wykazać, że tautologią rachunku zdań jest formuła

p ⇒ p.

Dowód przedstawimy w postaci ciągu formuł.

◦

[p ⇒ (q ⇒ r)] ⇒ [(p ⇒ q) ⇒ (p ⇒ r)]

(A.2

◦

)

◦

[p ⇒ (q ⇒ p)] ⇒ [(p ⇒ q) ⇒ (p ⇒ p)]

(reguła (1.4): w 1

◦

podstawiamy p zamiast r)

◦

p ⇒ (q ⇒ p)

(A.1

◦

)

◦

(p ⇒ q) ⇒ (p ⇒ p) (reguła (1.3) zastosowana do 2

◦

i 3

◦

)

◦

(p ⇒ (q ⇒ p)) ⇒ (p ⇒ p)

(reguła (1.4): w 4

◦

podstawiamy q ⇒ p zamiast q)

◦

p ⇒ p

(reguła (1.3) zastosowana do 5

◦

i 3

◦

)

Powyższy przykład wskazuje na to, jak należy rozumieć pojęcie

dowodu w k.r.z.

Definicja 1.7 Dowodem formuły f w oparciu o aksjomaty A.1

◦

- A.14

◦

nazywamy skończony ciąg formuł

...p

o tej własności, że p

= f , p

jest aksjomatem k.r.z., natomiast każda

Elementy wielowartościowych rachunków zdań

z pozostałych formuł jest, albo aksjomatem albo wynika z wcześniej-
szych formuł za pomocą reguły odrywania lub reguły podstawiania.

Można wykazać, że zbiór wszystkich tautologii k.r.z. pokrywa się

ze zbiorem wszystkich formuł, które mogą być wyprowadzone z aksjo-
matów k.r.z. w oparciu o reguły odrywania i podstawiania. Wynik ten
nosi nazwę twierdzenia o pełności k.r.z.

1.3

Elementy wielowartościowych
rachunków zdań

W przypadku wielowartościowych rachunków zdań (w.r.z.) przyj-

mujemy, że formuły logiczne budowane są tak jak dla k.r.z., tzn. złożone
są ze zmiennych zdaniowych, spójników i symboli pomocniczych. Ina-
czej jednak określamy funkcję wartościowania. Zakładamy mianowicie,
że

w : F → {

1, ..., M},

gdzie

M 2 jest liczbą naturalną. Przyjmujemy przy tym, że dla pew-

nej liczby naturalnej 1 ¬

S < M, wartości logiczne 1, ..., S są wyróżnio-

ne, natomiast wartości logiczne

S+1, ..., M nie są wyróżnione. Wartości

wyróżnione stanowią odpowiednik liczby

1 w logice dwuwartościowej.

Można zatem uznać, że wartości te wyznaczają stopień prawdziwości
zdania, przy czym im większa jest wartość wyróżniona, tym mniejszy
stopień prawdziwości zdania.

Z kolei wartości

S+1, ..., M, stanowią odpowiednik liczby 0 w logice

dwuwartościowej i wskazują na stopień fałszywości zdania. Im wartość
ta jest wyższa, tym zdanie uznaje się za, w większym stopniu, fałszywe.

J. Łukasiewicz i A. Tarski zaproponowali, aby funktory negacji, ko-

niunkcji, alternatywy i implikacji funkcjonujące w obrębie logiki wie-
lowartościowej określić przez analogię z logiką klasyczną w sposób na-
stępujący:

w(∼ p) =

M − w(p) + 1,

w(p ∧ q) = max{w(p), w(q)},

w(p ∨ q) = min{w(p), w(q)},

w(p ⇒ q) = max{

1, w(q) − w(p) + 1}.

Logika i teoria zbiorów

W szczególności, gdy zbiór wartości logicznych składa się z trzech

elementów:

1, 2, 3, otrzymuje się tzw. logikę trójwartościową Łuka-

siewicza. Liczba

1 symbolizuje prawdę, liczba 3 - fałsz, natomiast 2

wskazuje na możliwość (tę wartość logiczną mają zdania odnoszące się
do zjawisk niekoniecznie zachodzących w przyszłości).

Tak więc, w tym przypadku tabele wartości logicznych przedsta-

wiają się następująco:

w(p)

w(∼ p)

w(p)

w(q)

w(p ∧ q)

w(p ∨ q)

w(p ⇒ q)

Równoważność w logice wielowartościowej określamy tak samo jak

w logice dwuwartościowej.

Zauważmy, że funktor negacji Łukasiewicza i Tarskiego jest jedynie

w pewnym stopniu analogiczny do funktora negacji w logice dwuwar-
tościowej. Rzeczywiście, można wykazać, że zachodzą równoważności

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

oraz

∼∼ p ⇔ p.

Jednak, na ogół, funktor ten nie ma następującej własności:

zdanie p jest prawdziwe (w jakimś stopniu) wtedy i tylko
wtedy, gdy zdanie ∼ p jest fałszywe (w jakimś stopniu).

Elementy wielowartościowych rachunków zdań

Powyższą własność ma natomiast, jak się okazuje, negacja określo-

na w poniższy sposób

−p

def

⇐⇒ i

S+1

(p) ∨ i

S+2

(p) ∨ ... ∨ i

(p),

gdzie w(i

(p)) jest wartością wyróżnioną wtedy i tylko wtedy, gdy

w(p) = k, k =

1, 2, ..., M.

W dalszym ciągu będziemy przyjmować, że nowy funktor negacji

wiąże silniej niż wszystkie funktory dwuargumentowe.

Zauważmy przy okazji, że wartość logiczna wyrażenia

(p) ∨ i

(p) ∨ ... ∨ i

(p)

należy zawsze do zbioru {

1, 2, ..., S}, a tym samym powyższą formułę

należy uznać za analogon prawa wyłączonego środka w logice dwuwar-
tościowej

p∨ ∼ p.

Przyjrzyjmy się bliżej funktorowi implikacji wprowadzonemu przez

Łukasiewicza i Tarskiego. Zauważmy, na przykład, że gdy zbiór war-
tości logicznych jest równy {

1, 2, 3, 4}, a zbiór wartości wyróżnionych

jest równy {

1, 2}, to w przypadku formuł p oraz q, takich że

w(p) =

2 oraz w(q) = 3,

zachodzi równość

w(p ⇒ q) = max{

1, 3 − 2 + 1} = 2.

A zatem formuły p i p ⇒ q uznajemy za (w pewnym stopniu) prawdzi-
we, natomiast formuła q jest (w pewnym stopniu) fałszywa. W przy-
padku logik wielowartościowych nie zachodzi więc reguła odrywania.

Można jednakże zdefiniować nowy funktor implikacji

p ⊃ q

def

⇐⇒ (−p ∨ q),

dla którego zachodzi reguła odrywania.

Logika i teoria zbiorów

1.4

Klasyczny rachunek
kwantyfikatorowy

Klasyczny rachunek zdań jest teorią zbyt wąską, aby opisać więk-

szość, ważnych z punktu widzenia matematyki, rozumowań. Rozważmy
dla przykładu następujące dwa wyrażenia:

(a) wartość funkcji sinus dla dowolnego argumentu jest mniejsza bądź

równa jedności,

(b) dowolna liczba jest sumą dwóch liczb.

Stosując symbole „

” i „

” zamiast wyrażeń „dla każdego” oraz

„istnieje takie, że”, powyższe wyrażenia możemy zapisać następująco:

(a)

sin x ¬ 1,

(b)

x = y + z.

Symbole „

” i „

” nazywamy odpowiednio kwantyfikatorem uni-

wersalnym (ogólnym, dużym) i egzystencjalnym (szczegółowym, ma-
łym). Nie tylko upraszczają one zapis wyrażeń matematycznych, ale
także umożliwiają wprowadzenie nowych obiektów do rachunku logicz-
nego. Są nimi zmienne nazwowe (np. x, y, z), stałe (np. 1), symbole
funkcji (np. sin, +), symbole relacji (np. ¬) oraz wyrażenia, takie jak

sin x ¬ 1

oraz

x = y + z,

które, po podstawieniu w miejsce zmiennych nazwowych wartości licz-
bowych, stają się zdaniami prawdziwymi lub fałszywymi. Wyrażenia
te nazywamy funkcjami zdaniowymi lub predykatami. Funkcje zdanio-
we jednej, dwóch lub trzech zmiennych oznaczamy symbolami P (x),
P (x, y), P (x, y, z), Q(x), Q(x, y), Q(x, y, z) itp.

Nie będziemy tutaj wchodzili w dość skomplikowane szczegóły

techniczne, jednak trzeba pamiętać, że klasyczny rachunek kwanty-
fikatorowy (k.r.k.) może być oparty na równie ścisłych podstawach

Klasyczny rachunek kwantyfikatorowy

jak k.r.z. Przedstawimy tu jedynie aksjomatykę k.r.k. wraz z regułami
wnioskowania.

Aksjomaty k.r.k. budujemy w oparciu o formuły A.1

◦

-A.14

◦

k.r.z.,

do których dodajemy dwa aksjomaty dotyczące własności kwantyfika-
torów:

A.15

◦

P (x) ⇒ P (y)

A.16

◦

P (y) ⇒

P (x),

gdzie y jest zmienną nazwową, którą w formule P można podstawić za
zmienną x.

Reguły wnioskowania możemy wzbogacić o dwie nowe reguły:

P ⇒ Q(x)

P ⇒

Q(x)

(1.5)

oraz

P (x) ⇒ Q

(1.6)

gdzie zakłada się, że

- w pierwszym przypadku - w poprzedniku implikacji nie występuje

zmienna x, natomiast

- w przypadku drugim - zmienna x nie występuje w następniku

implikacji.

Pierwsza z powyższych reguł nazywa się regułą dołączania kwan-

tyfikatora uniwersalnego w następniku implikacji, a drugą nazywa się
regułą dołączania kwantyfikatora egzystencjalnego w poprzedniku impli-
kacji.

W jaki sposób możemy zatem korzystać z powyższych aksjomatów

i reguł wnioskowania? Rozważmy w tym celu poniższy przykład.

Przykład. Wykazać, że formuła

P (x) ⇒

P (x)

jest twierdzeniem k.r.k.

Logika i teoria zbiorów

Korzystamy z tautologii

(p ⇒ q) ⇒ [(q ⇒ r) ⇒ (p ⇒ r)],

którą można wyprowadzić w sposób formalny z aksjomatów k.r.z., ale
też można dla jej wykazania zastosować metodę tabelkową.

Następnie podstawiamy odpowiednio formuły

P (x),

P (y),

P (x)

w miejsce p, q i r. Zakładamy przy tym, że zmienna y może być pod-
stawiona zamiast x.

Otrzymujemy zatem formułę

P (x) ⇒ P (y)

⇒

P (y) ⇒

P (x)

⇒

P (x) ⇒

P (x)

Wykorzystując dwukrotnie regułę odrywania oraz aksjomaty A.15

◦

i A.16

◦

, widzimy, że

P (x) ⇒

P (x).

Oto kilka innych formuł k.r.k.

◦

∼

P (x) ⇔

∼ P (x)

∼

P (x) ⇔

∼ P (x)











(prawa De Morgana),

◦

(P (x) ⇒ Q(x)) ⇒

P (x) ⇒

Q(x)

◦

(P (x) ⇒ Q(x)) ⇒

P (x) ⇒

Q(x)

◦

(P (x) ⇔ Q(x)) ⇒

(P (x) ⇒ Q(x)) ∧

(Q(x) ⇒ P (x)),

◦

(P (x) ∧ Q(x)) ⇔

P (x) ∧

Q(x),

Klasyczny rachunek kwantyfikatorowy

◦

(P (x) ∨ Q(x)) ⇔

P (x) ∨

Q(x),

◦

P (x, y) ⇔

P (x, y),

◦

P (x, y) ⇔

P (x, y),

◦

P (x, y) ⇒

P (x, y).

Uwaga. Przedstawienie formalnych dowodów powyższych formuł mo-
że łączyć się z dużymi trudnościami. Niekiedy jednak możemy zastoso-
wać metodę uproszczoną, sprowadzającą się do użycia tabelki. Prawa
rachunku kwantyfikatorowego powinny być prawdziwe w każdej dzie-
dzinie, a w szczególności, gdy X = {x

, x

}. Przyjmijmy p

= P (x

= Q(x

), i = 1, 2. Wtedy np. formuła

(P (x) ⇒ Q(x)) ⇒

P (x) ⇒

Q(x)

sprowadza się do formuły k.r.z.

[(p

⇒ q

) ∧ (p

⇒ q

)] ⇒ (p

∧ p

⇒ q

∧ q

która, jak to można sprawdzić przy zastosowaniu metody tabelkowej,
jest tautologią.

Powyższa metoda nie jest wprawdzie w pełni ścisła, ma jednak

duże znaczenie heurystyczne i może w wielu przypadkach okazać się
bardzo użyteczna.

Ważną rolę odgrywają tzw. kwantyfikatory o zasięgu ograniczonym.

Są to wyrażenia postaci:

(a) dla każdego x spełniającego warunek P (x) zachodzi Q(x),

(b) istnieje x spełniające warunek P (x), dla którego zachodzi Q(x).

Wyrażenia te zapisujemy następująco

P (x)

Q(x)

oraz

P (x)

Q(x),

Logika i teoria zbiorów

które rozumiemy jako skróty wyrażeń

(P (x) ⇒ Q(x))

(P (x) ∧ Q(x)).

Przykład. Kwantyfikatorami o zasięgu ograniczonym są na przykład
wyrażenia

x<0

−x > 0

oraz

x∈

= 2.

W drugim przypadku mamy do czynienia z funkcją zdaniową x ∈

którą odczytujemy: liczba x jest elementem zbioru liczb rzeczywistych.

Własnościami relacji „∈”, jak również własnościami zbiorów,

w tym także zbiorów liczbowych, zajmiemy się w następnym podroz-
dziale.

1.5

Zbiory i ich własności

Pojęcie zbioru oraz pojęcie należenia do zbioru są pojęciami pier-

wotnymi. Ich sposób użycia regulują aksjomaty teorii mnogości, któ-
rych przytaczać tu nie będziemy. Przypomnimy jedynie podstawowe
definicje, oznaczenia i własności.

Każdy zbiór jest jednoznacznie określony przez swoje elementy.

Tak więc, jeśli x

, x

, ..., x

, ... są wszystkimi elementami zbioru A, to

piszemy

A = {x

, x

, ..., x

, ...}.

Jeśli każdy element zbioru B jest elementem zbioru A, to piszemy

B ⊂ A,

a relację ⊂ nazywamy relacją zawierania się albo relacją inkluzji. Zbiór
B nazywamy podzbiorem zbioru A. Gdy każdy element zbioru B jest
elementem zbioru A i odwrotnie: każdy element zbioru A jest elemen-
tem zbioru B, czyli jeśli B ⊂ A i A ⊂ B, to zbiory A oraz B uznaje
się za równe, co zapisuje się w postaci

A = B.

Zbiory i ich własności

Zbiór, który nie ma żadnego elementu nazywamy zbiorem pustym

i oznaczmy symbolem ∅. Jeśli dla elementów zbioru A określona jest
funkcja zdaniowa P , to podzbiór zbioru A złożony z tych elementów
x zbioru A, dla których P (x) jest zdaniem prawdziwym, oznacza się
symbolem

{x ∈ A : P (x)}.

Przez sumę i iloczyn zbiorów A i B rozumieć będziemy odpowiednio
następujące zbiory

A ∪ B = {x : x ∈ A ∨ x ∈ B}

oraz

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

W przypadku, gdy dana jest rodzina zbiorów A

, i ∈ I, gdzie I jest

zbiorem indeksów, to sumę i iloczyn zbiorów należących do tej rodziny
oznaczmy następująco

[

i∈I

= {x :

i∈I

x ∈ A

i∈I

= {x :

i∈I

x ∈ A

Gdy I = {1, 2, ..., n} lub gdy I = {1, 2, 3, ...}, to zamiast

i∈I

piszemy

[

i=1

lub

∞

[

i=1

Podobnie postępujemy w przypadku iloczynu zbiorów. Różnicą

zbiorów A oraz B nazywamy zbiór

A \ B = {x ∈ A : x /

∈ B}.

Symbol x /

∈ B jest skrótem zapisu ∼ x ∈ B.

Z kolei przez różnicę symetryczną zbiorów A i B rozumiemy zbiór

A ÷ B = {x ∈ A ∪ B : x /

∈ A ∩ B}.

Logika i teoria zbiorów

W przypadku, gdy rozważać będziemy podzbiory A, B, ... pewnego

ustalonego zbioru X, wygodnie jest wprowadzić jeszcze jedną operację
na zbiorach, a mianowicie dopełnienie

= X \ A.

Rachunek zbiorów obejmuje szereg praw, które mogą zostać dowie-

dzione w oparciu o odpowiednie tautologie k.r.z. Oto niektóre z tych
praw:

◦

A ∪ A = A ,

A ∩ A = A,

◦

A ∪ B = B ∪ A ,

A ∩ B = B ∩ A,

◦

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

◦

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

◦

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

◦

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

◦

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

◦

(A ∩ B)

= A

∪ B

(A ∪ B)

= A

∩ B







(prawa De Morgana),

◦

)

= A,

◦

A ÷ B = B ÷ A,

◦

A ÷ (B ÷ C) = (A ÷ B) ÷ C,

◦

A ⊂ B ⇒ A ∪ C ⊂ B ∪ C,

◦

A ⊂ B ⇒ A ∩ C ⊂ B ∩ C,

◦

A ∪ B = B ∩ A ⇒ A = B.

Praw rachunku zbiorów dowodzimy, jak to już było wspomniane,

posługując się k.r.z.

Zbiory i ich własności

Przykład. Dowieść, że dla dowolnych zbiorów A, B, C

A \ (B ∪ C) = (A \ B) ∩ (A \ C).

Niech x ∈ A \ (B ∪ C). Otrzymujemy ciąg równoważności

x ∈ A \ (B ∪ C) ⇔ (x ∈ A ∧ ∼ x ∈ B ∪ C) ⇔

⇔ (x ∈ A ∧ ∼ (x ∈ B ∨ x ∈ C)) ⇔

⇔ (x ∈ A ∧ ∼ x ∈ B ∧ ∼ x ∈ C) ⇔

⇔ (x ∈ A ∧ x ∈ A ∧ ∼ x ∈ B ∧ ∼ x ∈ C) ⇔

⇔ (x ∈ A ∧ ∼ x ∈ B ∧ x ∈ A ∧ ∼ x ∈ C) ⇔

⇔ (x ∈ A \ B ∧ x ∈ A \ C) ⇔

⇔ x ∈ (A \ B) ∩ (A \ C).

W powyższych przekształceniach skorzystaliśmy z definicji sumy,

iloczynu i różnicy zbiorów, a także z tautologii k.r.z.:

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

p ⇔ p ∧ p

p ∧ q ⇔ q ∧ p

p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r.

Rozważmy teraz nieco bardziej skomplikowany problem.

Przykład. Jakie relacje pomiędzy zbiorami A, B, C muszą zachodzić,
aby

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

Zauważmy, że powyższa równość zachodzi, gdy

x ∈ (A ∩ B) ∪ (A ∩ C) ⇔ x ∈ B ∪ C,

czyli, gdy

(x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) ⇔ x ∈ B ∨ x ∈ C.

Logika i teoria zbiorów

Zastosujmy do powyższej formuły metodę tabelkową. Wprowadź-

my oznaczenia p = x ∈ A, q = x ∈ B, r = x ∈ C. Formułę

(p ∧ q) ∨ (p ∧ r) ⇔ q ∨ r

oznaczmy symbolem f .

(p ∧ q) ∨ (p ∧ r)

q ∨ r

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Gdyby równość (A ∩ B) ∪ (A ∩ C) = B ∪ C była prawdziwa dla

wszystkich zbiorów, to w ostatniej kolumnie znajdowałyby się wyłącz-
nie jedności. Jak widać, mamy kłopot z drugim, trzecim i czwartym
wierszem tabeli. Aby wspomniana równość zachodziła, należy zanego-
wać warunek

x /

∈ A ∧ (x ∈ B ∨ x ∈ C) .

Wobec tego

∼ (x /

∈ A ∧ (x ∈ B ∨ x ∈ C)) ⇔ x ∈ A ∨ ∼ (x ∈ B ∨ x ∈ C) ⇔

⇔ (x ∈ B ∪ C ⇒ x ∈ A).

Zauważmy, że skorzystaliśmy tu z tautologii

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

oraz

∼ p ∨ q ⇔ (p ⇒ q).

A zatem otrzymujemy poszukiwany warunek w postaci

B ∪ C ⊂ A.

Zbiory i ich własności

Wprowadzimy teraz nowe ważne pojęcie. Parą uporządkowaną

o poprzedniku x i następniku y nazywamy zbiór

(x, y) = {x, {x, y}}.

Z kolei, n-tką uporządkowaną nazywamy zbiór

, x

, ..., x

) = ((x

, x

, ..., x

n−1

), x

n  3.

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

A × B = {(x, y) : x ∈ A ∧ y ∈ B}.

Podobnie, iloczynem kartezjańskim zbiorów A

, A

, ..., A

nazy-

wamy zbiór

× A

× ... × A

= {(x

, x

, ..., x

) : x

∈ A

, i = 1, 2, ..., n}.

W przypadku, gdy A

= A

= ... = A

= A, n  2, iloczyn

kartezjański A

× A

× ... × A

oznaczamy symbolem A

Iloczyn kartezjański ma szereg ważnych własności. Zauważmy naj-

pierw, że na ogół

A × B 6= B × A

oraz

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

jakkolwiek w ostatnim przypadku oba zbiory, formalnie różne, utożsa-
miamy ze sobą.

Ponadto, można wykazać, że

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

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

A × (B \ C) = (A × B) \ (A × C)

(A × B) ∪ (C × D) ⊂ (A ∪ B) × (B ∪ D)

Kolejnym ważnym pojęciem, które wprowadzimy w tym podroz-

dziale, jest pojęcie tzw. zbioru potęgowego. Jeśli dany jest zbiór A, to
zbiorem potęgowym tego zbioru nazywamy zbiór

P(A) = {B : B ⊂ A}.

Logika i teoria zbiorów

Innymi słowy, P(A) (stosujemy też oznaczenie 2

) jest zbiorem

zawierającym wszystkie podzbiory A i tylko te podzbiory.

Szczególna nazwa zbioru P(A) bierze się stąd, że, o czym będzie

jeszcze mowa w jednym z następnych rozdziałów, w przypadku, gdy A
ma dokładnie n elementów, to jego zbiór potęgowy ma 2

elementów.

Na zakończenie tego rozdziału przypomnijmy oznaczenia dla zbio-

rów liczbowych. Zbiór liczb naturalnych 0, 1, 2, ... będziemy oznaczać
symbolem

N. Zbiór liczb całkowitych będzie oznaczany literą Z, a zbio-

ry liczb wymiernych i rzeczywistych będą oznaczane odpowiednio sym-
bolami

Q i R.

Relacje i funkcje

2.1

Podstawowe własności relacji

Definicja 2.1 Niech dane będą zbiory niepuste A

, A

, ..., A

n  2. Relacją n-członową w iloczynie kartezjańskim A

× A

× ... × A

nazywamy dowolny podzbiór ρ tego iloczynu.

W przypadku, gdy A

= A

= ... = A

= A, relację ρ ⊂ A

nazywamy relacją w zbiorze A.

Przykład. Niech dana będzie relacja ρ ⊂

, przy czym

, x

) ∈ ρ ⇔ x

< x

Relację tę możemy określić jako relację „leżenia między”. Ma ona

szereg interesujących własności. Na przykład,

jeśli

, x

) ∈ ρ,

+ a, x

+ a) ∈ ρ.

Podobnie,

jeśli

, x

) ∈ ρ,

, x

) ∈ ρ,

, x

) ∈ ρ.

Relacje i funkcje

W dalszym ciągu zajmować się będziemy relacjami dwuczłonowymi

albo, inaczej mówiąc, binarnymi. Zakładać dalej będziemy, że rozwa-
żane zbiory są niepuste.

Umowa notacyjna. Zamiast pisać (x

, x

) ∈ ρ będziemy na ogół uży-

wać oznaczenia x

ρx

Definicja 2.2 Niech ρ ⊂ A

× A

. Zbiory

D(ρ) = {x

∈ A

∈A

ρx

}

oraz

R(ρ) = {x

∈ A

∈A

ρx

}

nazywamy odpowiednio dziedziną i przeciwdziedziną tej relacji. Zbiór
D(ρ) ∪ R(ρ) nazywamy polem relacji.

Definicja 2.3 Relacją odwrotną do relacji ρ ⊂ A

× A

nazywamy

relację

−1

= {(x

, x

) : x

ρx

Definicja 2.4 Niech dane będą dwie relacje ρ

⊂ A

× A

oraz ρ

⊂

× A

. Iloczynem względnym (inaczej: superpozycją, złożeniem) tych

relacji nazywamy relację

◦ ρ

= {(x

, x

) :

∈A

∧ x

Twierdzenie 2.1 Niech ρ

⊂ A

× A

, ρ

⊂ A

× A

, ρ

⊂ A

× A

Wtedy

◦ (ρ

◦ ρ

) = (ρ

◦ ρ

) ◦ ρ

Dowód. Załóżmy, że xρ

◦ (ρ

◦ ρ

)y. Istnieje z takie, że xρ

◦ ρ

z oraz

zρ

y. Wynika stąd, że istnieje t o tej własności, że xρ

t i tρ

z. Z po-

wyższych zależności otrzymujemy tρ

◦ ρ

y, a zatem x(ρ

◦ ρ

) ◦ ρ

Dowód implikacji w drugą stronę jest analogiczny.

Podstawowe własności relacji

Twierdzenie 2.2 Dla dowolnych relacji ρ

⊂ A

× A

i ρ

⊂ A

× A

zachodzi równość

(ρ

◦ ρ

)

−1

= ρ

−1
1

◦ ρ

−1
2

Dowód. Niech x(ρ

◦ ρ

)

−1

y wtedy yρ

◦ ρ

x oraz istnieje z, takie że

yρ

z i zρ

x. Stąd wynika, że xρ

−1
2

z i zρ

−1
1

y, czyli xρ

−1
1

◦ ρ

−1
2

y. Dowód

implikacji odwrotnej jest podobny.

Definicja 2.5 Niech ρ ⊂ A

× A

oraz B

⊂ A

, i = 1, 2. Relacje

ρ B

= ρ ∩ (B

× A

)

oraz

ρ B

= ρ ∩ (A

× B

)

nazywamy obcięciami relacji ρ do zbiorów odpowiednio B

i B

Podobnie

ρ ↑ B

× B

nazywamy obustronnym obcięciem relacji ρ do B

× B

Definicja 2.6 Załóżmy, że ρ ⊂ A

oraz B ⊂ A. Relację

= {(x, x) : x ∈ B}

nazywamy relacją identycznościową w zbiorze B.

Twierdzenie 2.3 Jeżeli ρ ⊂ A

× A

oraz B

⊂ A

, i = 1, 2, to

ρ B

= ρ ◦ I

ρ B

= I

◦ ρ.

Dowód jest oczywisty.

Zajmiemy się dokładniej własnościami relacji ρ ⊂ A × A.

Definicja 2.7 Relację ρ ⊂ A × A nazywamy:

(a) zwrotną, jeśli

x∈A

xρx,

Relacje i funkcje

(b) przeciwzwrotną, jeśli

x∈A

∼ (xρx),

x∈A

y∈A

(xρy ⇒ yρx),

(d) przeciwsymetryczną, jeśli

x∈A

y∈A

(xρy ⇒∼ (yρx)),

(e) słabo antysymetryczną, jeśli

x∈A

y∈A

(xρy ∧ yρx ⇒ y = x),

(f) przechodnią, jeśli

x∈A

y∈A

z∈A

(xρy ∧ yρz ⇒ xρz),

(g) spójną, jeśli

x∈A

y∈A

(xρy ∨ yρz ∨ x = y).

Przykład. Zbadamy własności następujących relacji:

i) ρ ⊂

∧

xρy ⇔ xy > 0,

ii) ρ ⊂

∧

nρm ⇔ |n − m| = 2.

Zajmiemy się najpierw relacją i). Relacja ta nie jest zwrotna, bo na

przykład nie jest prawdą, że 0ρ0. Nie jest też przeciwzwrotna, gdyż nie
jest prawdą, że dla dowolnego x ∈

R, x

¬ 0. Rozważana relacja jest

oczywiście symetryczna i nie jest przeciwsymetryczna. Nie jest słabo
antysymetryczna, bo z tego, że xy > 0 nie wynika, że x = y. Relacja
jest przechodnia, ponieważ jeśli xy > 0 i yz > 0, to xy

z > 0, skąd

wynika, że xz > 0. Relacja nie jest spójna, bo np. liczby 1 i −2 nie są
ze sobą w relacji oraz 1 6= −2.

Relacje pomiędzy elementami zbiorów skończonych

Zbadajmy relację ii). Relacja ta nie jest zwrotna, bo |n−n| = 0 6= 2.

Jest ona natomiast przeciwzwrotna. Ponadto, relacja ta jest syme-
tryczna, ponieważ |n − m| = |m − n|. Nie jest przeciwsymetrycz-
na. Czy jest słabo asymetryczna? Odpowiedź jest negatywna, gdyż
np. 3ρ5 ∧ 5ρ3, ale 3 6= 5. Zauważmy jednocześnie, że chociaż 3ρ5 ∧ 5ρ7,
to nie jest prawdą, że 3ρ7, a zatem relacja nie jest przechodnia. Relacja
nie jest też spójna, ponieważ np. 1 nie jest w relacji ρ z 2 (i vice versa),
a ponadto 1 6= 2.

Twierdzenie 2.4 Relacja ρ ⊂ A

jest symetryczna wtedy i tylko wte-

dy, gdy

ρ ⊂ ρ

−1

Dowód. Załóżmy, że relacja ρ jest symetryczna. Wynika stąd, że jeśli
xρy, to yρx, a zatem xρ

−1

y, czyli ρ ⊂ ρ

−1

Jeśli natomiast ρ ⊂ ρ

−1

, to z tego, iż xρy wynika, że xρ

−1

y, czyli

yρx.

Twierdzenie 2.5 Relacja ρ ⊂ A

jest przechodnia wtedy i tylko wtedy,

gdy

ρ ◦ ρ ⊂ ρ.

Dowód. Załóżmy najpierw, że relacja ρ jest przechodnia. Niech xρ◦ρy.
Istnieje wtedy z, takie że xρz i zρy. Zatem xρy, czyli ρ ◦ ρ ⊂ ρ.

Niech ρ ◦ ρ ⊂ ρ i załóżmy, że xρy i yρz. Wtedy xρ ◦ ρz, a stąd

wynika, że xρz.

2.2

Relacje pomiędzy elementami
zbiorów skończonych

Zajmiemy się teraz bardziej szczegółowo relacjami zachodzącymi

pomiędzy elementami zbiorów skończonych. Przedstawiamy te relacje
często za pomocą odpowiednich diagramów.

Relacje i funkcje

Przykład. Rozważmy relację ρ pomiędzy elementami zbiorów

A = {α, β, γ, δ}

B = { , 4, }

określoną następująco

ρ = {(α, ), (β, 4), (γ, ), (δ, )}.

Za pomocą diagramu możemy ją zilustrować w poniższy sposób.

Relację odwrotną do powyższej przedstawiamy za pomocą diagra-

Jeśli ponadto dana jest relacja

τ = {( , a), ( , b), ( , c), (4, b)}

zawarta w iloczynie kartezjańskim B ×C, gdzie C = {a, b, c}, to relację
τ ◦ ρ przedstawiamy graficznie w formie kolejnego diagramu.

Relacje pomiędzy elementami zbiorów skończonych

czyli

Tak więc

τ ◦ ρ = {(α, a), (α, b), (α, c), (β, b), (γ, a), (γ, b), (γ, c)}.

W przypadku, gdy relacja zachodzi pomiędzy elementami tego

samego zbioru, również przedstawimy ją za pomocą odpowiedniego
diagramu.

Przykład. Rozważmy relację ρ ⊂ A

, gdzie A = {x, y, z, t} taką, że

ρ = {(x, x), (x, y), (x, u), (y, z), (y, t), (y, u), (z, y), (z, t), (t, t)}.

Relacje i funkcje

Odpowiada jej diagram

Definicja 2.8 Niech dana będzie relacja ρ ⊂ A × B, gdzie

A = {x

, x

, ..., x

B = {y

, y

, ..., y

Macierz R = [r

]

n×m

, gdzie

(

1, jeśli

ρy

0, jeśli ∼ (x

ρy

)

nazywamy macierzą tej relacji.

Twierdzenie 2.6 ([15, s. 668]) Niech dane będą dwie relacje ρ ⊂
A × B i τ ⊂ B × C, gdzie A = {x

, x

, ..., x

}, B = {y

, y

, ..., y

}, zaś

C = {z

, z

, ..., z

}. Wtedy relacji τ ◦ ρ odpowiada macierz S = [s

]

n×k

której współczynniki są równe

[

j=1

∩ t

gdzie R = [r

]

n×m

oraz T = [t

]

m×k

są macierzami odpowiednio relacji

ρ i τ , natomiast symbole ∪ oraz ∩ oznaczają, jak poprzednio, maksi-
mum i minimum.

Dowód twierdzenia jest oczywisty. Pozostawiamy go Czytelnikowi

jako ćwiczenie.

Przykład. Niech dane będą relacje

ρ = {(0, x), (0, y), (1, z), (2, y), (3, z)}

Relacje równoważności

oraz

τ = {(x, a), (y, a), (y, b), (z, b)},

takie że

ρ ⊂ {0, 1, 2, 3} × {x, y, z}

τ ⊂ {x, y, z} × {a, b}.

Odpowiadają im macierze

R =

0
1
2
3

x y z








1 1 0
0 0 1
0 1 0
0 0 1








T =

x
y

a b






1 0
1 1
0 1






Zauważmy, że

τ ◦ ρ = {(0, a), (0, b), (1, b), (2, a), (2, b), (3, b)}.

Odpowiada jej macierz S = R × T .

S =

0
1
2
3

a b








1 1
0 1
1 1
0 1








2.3

Relacje równoważności

Definicja 2.9 Relację ρ ⊂ A

nazywamy relacją równoważności jeśli

jest ona zwrotna, symetryczna i przechodnia.

Przykład. Relacjami równoważności są:

(i) ρ ⊂

taka, że ρ = {(x, x) : x ∈

R},

(ii) σ ⊂

taka, że xσy ⇔ x

= y

Relacje i funkcje

(iii) τ ⊂

taka, że nτ m ⇔ 4|(n − m), gdzie symbol k|l rozumiemy

jako: liczba k dzieli liczbę l,

(iv) ξ ⊂

taka, że (k

, l

)ξ(k

, l

) ⇔ k

− l

= k

− l

To, że relacje ρ i σ są relacjami równoważności nie wymaga komen-

tarza. Przyjrzyjmy się relacji τ .

Jest ona zwrotna, bo n − n = 0 dzieli się przez 4. Jest także syme-

tryczna, gdyż jeśli n − m dzieli się przez 4, to także m − n dzieli się
przez 4. Jest też relacją przechodnią, ponieważ, jeśli n − m oraz m − k
dzielą się przez 4, to n − k = n − m + m − k również dzieli się przez 4.

Relacja ξ jest oczywiście zwrotna i symetryczna. Jest też przechod-

nia, ponieważ, jeśli k

−l

= k

−l

i k

−l

= k

−l

, to k

−l

= k

−l

Definicja 2.10 Niech ρ ⊂ A

będzie relacją równoważności. Zbiór

[x]

= {y ∈ A : xρy}

nazywamy klasą abstrakcji elementu x dla relacji ρ.

Zbiór wszystkich klas abstrakcji tej relacji nazywamy zbiorem ilo-

razowym i oznaczamy symbolem A/ρ.

Przykład. Dla relacji równoważności ρ, σ, τ , ξ z poprzedniego przy-
kładu klasami abstrakcji są

(i) [x]

= {x}, x ∈

(ii) [x]

= {−x, x}, x ∈

(iii) [0]

= {4k : k ∈

Z},

[1]

= {4k + 1 : k ∈

Z},

[2]

= {4k + 2 : k ∈

Z},

[3]

= {4k + 3 : k ∈

Z},

(iv) [(k, l)]

= {(r + k − l, r) : r ∈

N}, k, l ∈ N.

Dla klasy [x]

element x nazywamy jej reprezentantem. Jeśli xρy,

to oczywiście [x]

= [y]

. Na przykład dla relacji τ , jak wyżej, [0]

[2]

= [−4]

, itd.

Relacje równoważności

Twierdzenie 2.7 Niech ρ ⊂ A

będzie relacją równoważności. Wtedy

(i) [x]

6= ∅ dla dowolnego x ∈ A,

(ii) [x]

= [y]

lub [x]

∩ [y]

= ∅ dla dowolnych x i y należących do

(iii) każdy element x zbioru A należy do pewnej klasy abstrakcji rela-

cji ρ.

Dowód twierdzenia jest oczywisty.

Definicja 2.11 Podziałem zbioru A 6= ∅ nazywamy rodzinę zbiorów
A

, i ∈ I, gdzie A

6= ∅ dla dowolnego i ∈ I, a ponadto A

∩ A

= ∅ dla

i 6= j, i, j ∈ I, oraz

[

i∈I

= A.

Uwaga. Z ostatniego twierdzenia i definicji wynika, że relacja równo-
ważności ρ ⊂ A

dokonuje podziału zbioru niepustego A.

Twierdzenie 2.8 Niech dany będzie podział A

, i ∈ I, zbioru A 6= ∅.

Istnieje relacja równoważności ρ ⊂ A

, która prowadzi do tego podziału.

Dowód. Nietrudno zauważyć, że relacja ρ jest określona następująco

xρy ⇔

i∈I

(x ∈ A

∧ y ∈ A

Uwaga. Ostatnie dwa twierdzenia łączące relację równoważności po-
między elementami danego zbioru z podziałem tego zbioru noszą nazwę
zasady abstrakcji.

Relacje i funkcje

2.4

Relacje porządku

Definicja 2.12 Relację ρ ⊂ A

nazywamy relacją częściowego porząd-

ku (lub, po prostu, porządku), jeśli jest ona zwrotna, słabo antysyme-
tryczna i przechodnia.

Umowa notacyjna. Relację częściowego porządku oznaczać będziemy
zazwyczaj symbolem .

Przykład. Poniższe relacje są relacjami częściowego porządku.

(i) Relacja  ⊂

taka, że

x y ⇔ x ¬ y.

(ii) Relacja  ⊂

2
+

taka, że

n m ⇔ n|m,

gdzie

N \ {0}.

(iii) Niech A będzie zbiorem. Rozważmy relację ⊂ P(A)

taką, że

U V ⇔ U ⊂ V.

Definicja 2.13 Jeżeli ⊂ A

jest relacją częściowego porządku, to

x ≺ y

def

⇐⇒ (x y ∧ x 6= y),

x, y ∈ A.

W dalszym ciągu, jeśli x y, będziemy pisać, że element x jest

mniejszy lub równy od elementu y, a element y jest większy lub równy
od x. Jeśli natomiast x ≺ y, będziemy pisać, że x jest mniejszy od y,
a y jest większy od x.

Definicja 2.14 Załóżmy, że ⊂ A

i niech x

∈ A

⊂ A. Wtedy, jeśli

x∈A

 x ⇒ x = x

to x

nazywamy elementem maksymalnym w zbiorze A

Jeżeli natomiast

x∈A

(x x

⇒ x = x

to x

nazywamy elementem minimalnym w zbiorze A

Relacje porządku

Definicja 2.15 Niech ⊂ A

i załóżmy, że x

∈ A

⊂ A. Jeżeli

x∈A

x x

to x

nazywamy elementem największym w zbiorze A

lub maksimum

zbioru A

i oznaczamy symbolem max A

Jeżeli

x∈A

 x,

to x

nazywamy elementem najmniejszym w zbiorze A

albo minimum

i oznaczamy symbolem min A

Definicja 2.16 Ograniczeniem górnym zbioru A

⊂ A nazywamy każ-

dy element x

∈ A, taki że

x∈A

x x

Ograniczeniem dolnym zbioru A

nazywamy x

, który spełnia wa-

runek

x∈A

 x.

Definicja 2.17 Kresem górnym albo supremum zbioru A

⊂ A nazy-

wamy najmniejsze z ograniczeń górnych tego zbioru. Kres górny zbioru
A

oznaczmy symbolem sup A

Podobnie, kresem dolnym albo infimum zbioru A

nazywamy naj-

większe z ograniczeń dolnych tego zbioru. Kres dolny zbioru A

ozna-

czamy symbolem inf A

Uwaga. Zdefiniowane wyżej elementy nazywamy elementami wyróż-
nionymi.

Przykład. Rozważmy zbiór

∗

∪ {

: n ∈

} z relacją częścio-

wego porządku

m k ⇔

∈

∗

k, m ∈

∗

Relacje i funkcje

Weźmy pod uwagę następujące podzbiory tego zbioru

= {

: n ∈

} ∪ {2n : n ∈

= {

1
3

, 1, 3, 9},

= {

1
4

1
3

, 1, 4, 7, 9},

= {p ∈

: p jest liczbą pierwszą}.

Tutaj zbiór B

nie ma elementów wyróżnionych. W przypadku

zbioru B

, max B

= sup B

= 9 oraz min B

= inf B

1
3

. Zbiór B

ma dwa elementy minimalne

1
4

1
3

, a także trzy elementy maksymalne

4, 7, 9. Nie ma oczywiście ani elementu największego, ani elementu
najmniejszego. Każdy element zbioru B

jest zarówno elementem mi-

nimalnym jak i maksymalnym.

Uwaga. Można wykazać, że dowolny zbiór ma co najwyżej jeden ele-
ment największy, najmniejszy oraz co najwyżej jeden kres górny i dol-
ny. Ponadto jeśli element największy (podobnie: najmniejszy) istnieje,
to jest on również kresem górnym zbioru i jedynym jego elementem
maksymalnym (odpowiednio: kresem dolnym i jedynym elementem mi-
nimalnym).

Definicja 2.18 Relację częściowego porządku, która jest spójna nazy-
wać będziemy relacją porządku liniowego.

Przykład. Relacjami liniowego porządku są

(i) relacja ¬ w zbiorze liczb rzeczywistych

(ii) relacja podzielności w zbiorze {2

: n ∈

N}.

Do przedstawiania graficznego zbiorów częściowo uporządkowa-

nych wykorzystywane są tzw. diagramy Hassego. Składają się one
z punktów płaszczyzny, nazywanych wierzchołkami, i łączących je linii
(odcinków lub łuków).

Wierzchołki odpowiadają elementom zbioru, przy czym elementom

wcześniejszym, w sensie relacjami , odpowiadają wierzchołki położo-
ne niżej. Ponadto dwa wierzchołki połączone są linią wtedy i tylko wte-
dy, gdy pomiędzy odpowiadającymi im elementami zbioru, powiedzmy

Relacje porządku

x i y, zachodzi relacja, a także nie istnieje z, takie że x z y lub
y z x, z 6= x, y.

Przykład

(i) Rozważmy zbiór A = {2, 3, 5, 6, 7, 8, 11, 15, 16, 30, 35, 105}, w któ-

rym dana jest relacja podzielności. Odpowiedni diagram Hassego
ma postać

105

(ii) Weźmy pod uwagę zbiór P({0, 1}) uporządkowany przez relację

inkluzji. Odpowiada mu diagram Hassego

{0, 1}

{0}

{1}

{∅}

(iii) Zajmijmy się zagadnieniem nieco bardziej skomplikowanym. Za-

stanówmy się, na ile sposobów można wprowadzić relację częścio-
wego porządku w zbiorze czteroelementowym {1, 2, 3, 4}. Okazu-
je się, że sposobów takich jest aż 249. Nie sposób przedstawić
wszystkie odpowiadające im diagramy Hassego. Poniżej prezen-
tujemy szesnaście diagramów, w oparciu o które łatwo otrzymać
diagramy pozostałe.

Relacje i funkcje

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

Funkcje i ich własności

(l)

(m)

(n)

(o)

(p)

2.5

Funkcje i ich własności

Przyjmijmy na wstępie założenie, które uczynione zostało wcze-

śniej, gdy definiowane było pojęcie relacji. Podobnie jak poprzednio,
zakładać będziemy, że zbiory rozważane w tym podrozdziale są niepu-
ste.

Definicja 2.19 Relację f ⊂ A × B nazywamy funkcją odwzorowującą
zbiór A w zbiór B, jeśli

(i)

x∈A

y∈B

xf y,

(ii)

x∈A

∈B

(xf y

∧ xf y

⇒ y

= y

Relacje i funkcje

Umowa notacyjna. W dalszym ciągu zamiast pisać xf y, będziemy
używać zapisu y = f (x). Element x nazywamy argumentem funkcji
f , zaś y - jej wartością dla tego argumentu. Funkcję zapisywać też
będziemy następująco f : A → B.

Przykład

(i) Relacja f

= {(x, y) ∈

: y = x

} jest funkcją odwzorowującą

zbiór

R w R.

(ii) Relacja f

= {(x, y) ∈ [0; ∞) ×

R : x = y

} nie jest funkcją, bo

na przykład 1f

−1 oraz 1f

Definicja 2.20 Zbiory D(f ) i R(f ) nazywamy odpowiednio dziedziną
i przeciwdziedziną funkcji f .

Definicja 2.21 Niech dana będzie funkcja f : A → B oraz zbiory
A

⊂ A i B

⊂ B. Zbiory

f (A

) = {y ∈ B :

x∈A

y = f (x)}

−1

) = {x ∈ A :

y∈B

f (x) = y}

nazywamy odpowiednio obrazem zbioru A

poprzez funkcję f oraz prze-

ciwobrazem zbioru B

poprzez f .

Twierdzenie 2.9 Niech dana będzie funkcja f : A → B. Wtedy dla
A

, A

⊂ A:

(i) f (A

∪ A

) = f (A

) ∪ f (A

(ii) f (A

∩ A

) ⊂ f (A

) ∩ f (A

(iii) f (A

) \ f (A

) ⊂ f (A

\ A

Dowód

(i) Jeśli y ∈ f (A

∪ A

), to istnieje x ∈ A

∪ A

o takiej własności,

że y = f (x). Zatem y ∈ f (A

) lub y ∈ f (A

), czyli y ∈ f (A

) ∪

f (A

). Dowód implikacji odwrotnej jest podobny.

Funkcje i ich własności

(ii) Jeżeli y ∈ f (A

∩ A

), to istnieje x takie, że x ∈ A

i x ∈ A

oraz

y = f (x). Tak więc y ∈ f (A

) ∩ f (A

(iii) Załóżmy, że y ∈ f (A

) \ f (A

). Stąd wynika, że istnieje x ∈ A

takie, że y ∈ f (A

), x /

∈ A

, bo y /

∈ f (A

). Zatem x ∈ A

\ A

czyli y ∈ f (A

\ A

Uwaga. W punktach (ii) i (iii) powyższego twierdzenia inkluzja nie
może być zastąpiona równością. Świadczy o tym przykład funkcji
f :

R → R, takiej że f(x) = x

oraz A

= [−1, 0], A

= [0, 1].

Mamy zatem

f (A

∩ A

) = f ({0}) = {0} 6= f (A

) ∩ f (A

) = [0, 1]

oraz

f (A

) \ f (A

) = ∅ 6= f (A

\ A

) = f ([−1, 0)) = (0, 1].

Twierdzenie 2.10 Niech f : A → B oraz B

, B

⊂ B. Wtedy

(i) f

−1

∪ B

) = f

−1

) ∪ f

−1

(ii) f

−1

∩ B

) = f

−1

) ∩ f

−1

(iii) f

−1

\ B

) = f

−1

) \ f

−1

Dowód powyższego twierdzenia pozostawiamy Czytelnikowi.

Definicja 2.22 Niech dane będą dwie funkcje

: A → B

: B → C.

Ich złożeniem albo superpozycją nazywamy relację f

◦ f

Przykład. Niech funkcja f

: [−1, 1] →

R będzie dana zależnością

(x) =

(

dla x ∈ [−1, 0],

x + 2 dla x ∈ (0, 1]

oraz niech dana będzie funkcja f

: [1, 3] → [1, 3] taka, że

(x) =

(

dla x ∈ [1, 2]

2x + 2 dla x ∈ (2, 3].

Relacje i funkcje

Wtedy

◦ f

(x) = f

(x)) =







dla x ∈ f

−1

([1, 2])

(x) + 2

dla x ∈ f

−1

((2, 3])







dla x ∈ [−1, 0]

(x) + 2

dla x ∈ (0, 1]







dla x ∈ [−1, 0]

2(x + 2) + 2

dla x ∈ (0, 1]







dla x ∈ [−1, 0]

2x + 6

dla x ∈ (0, 1].

Definicja 2.23 Wykresem funkcji f : A → B nazywa się zbiór

= {(x, f (x)) : x ∈ A}.

Definicja 2.24 Funkcję f : A → B nazywa się

(a) iniekcją (albo funkcją różnowartościową), jeśli

∈A

6= x

⇒ f (x

) 6= f (x

)),

(b) suriekcją (funkcją na cały zbiór B), jeśli

y∈B

x∈A

y = f (x),

zem iniekcją i suriekcją.

Umowa notacyjna. W dalszym ciągu, gdy f : A → B jest suriekcją,
będziemy pisać, że odwzorowuje ona zbiór A na zbiór B.

Funkcje i ich własności

Definicja 2.25 Zbiór wszystkich funkcji odwzorowujących zbiór A
w zbiór B oznaczany będzie symbolem B

Zbiory wszystkich iniekcji, suriekcji i bijekcji ze zbioru A w zbiór B

będą oznaczane odpowiednio symbolami ini (B

), sur (B

) oraz bij (B

Definicja 2.26 Funkcją odwrotną do funkcji f nazywamy relację f

−1

jeśli jest ona funkcją.

Przykład

(i) Rozważmy funkcję f :

R → R daną zależnością

f (x) = min{x − 1, 1}.

−1

Funkcja ta nie jest iniekcją, bo np. f (2) = f (3) = 1. Nie jest też
suriekcją, gdyż f (x) ¬ 1 dla dowolnego x ∈

R. A zatem nie jest

bijekcją.

−1

Relacja f

−1

nie jest funkcją, ponieważ 1f

−1

2 i 1f

−1

3, a jest to

sprzeczne z warunkiem (ii) definicji funkcji.

Relacje i funkcje

(ii) Weźmy pod uwagę funkcję f :

→

, taką że

f (x

, x

) = (x

+ x

, x

− x

Po pierwsze, zauważmy, że f jest suriekcją. Rzeczywiście, dla
dowolnych y

, y

∈

R, układ równań

+ x

= y

− x

= y

ma rozwiązanie

1
2

+ y

1
2

− y

)

Rozwiązanie to jest jednoznaczne, a więc f jest iniekcją. Funkcja
ta jest bijekcją. Funkcja f

−1

→

dana jest zależnością

−1

, y

) =

+ y

− y

)

Definicja 2.27 Niech dana będzie funkcja f : A → B oraz niech A

⊂

A. Obcięciem funkcji f do zbioru A

nazywamy funkcję f

Przykład

(i) Niech dana będzie funkcja f z punktu (i) poprzedniego przykła-

du. Funkcja f

(−∞, 2] jest iniekcją.

(ii) Funkcja sin :

R → R nie jest oczywiście ani iniekcją ani suriekcją.

Jednak funkcja sin

[−

] przekształca w sposób wzajemnie -

jednoznaczny przedział [−

] na przedział [−1, 1]. Umożliwia

to zdefiniowanie funkcji odwrotnej arcsin : [−1, 1] → [−

−1

−

arcsin

Zbiór liczb naturalnych i indukcja

3.1

Zbiór liczb naturalnych.
Definiowanie przez indukcję

Zbiór liczb naturalnych można wprowadzić w bardzo różnorodny

sposób. Można go na przykład zdefiniować jako pewien podzbiór zbioru
liczb rzeczywistych. Możliwe jest też zdefiniowanie zbioru liczb natu-
ralnych na drodze aksjomatycznej. Właśnie tak uczynimy, posługując
się aksjomatami przedstawionymi przez Giuseppe’a Peana.

Definicja 3.1 Zbiorem liczb naturalnych nazywamy zbiór

N, na któ-

rym określona jest funkcja następnika

s :

N → N,

spełniająca następujące aksjomaty

◦

0 ∈

◦

n∈

∼ (s(n) = 0),

Zbiór liczb naturalnych i indukcja

◦

n∈

m∈

(s(n) = m ∧

k∈

(s(n) = k ⇒ k = m)),

◦

n∈

m∈

k∈

(s(n) = s(m) = k ⇒ n = m),

◦

(zasada indukcji zupełnej)

A⊂

((0 ∈ A ∧

n∈

(n ∈ A ⇒ s(n) ∈ A)) ⇒ A =

Przedstawimy kluczowe twierdzenie pozwalające na definiowanie

funkcji spełniającej pewien warunek początkowy oraz zależność rekur-
sywną.

Twierdzenie 3.1 (o definiowaniu przez indukcję) Załóżmy, że A
jest dowolnym zbiorem niepustym. Jeśli ϕ :

N → A oraz ψ : N × N

A → A są dowolnymi funkcjami, to istnieje dokładnie jedna funkcja
f :

N × N

→ A o tej własności, że dla dowolnych liczb naturalnych

, m

, ..., m

, n zachodzą warunki

f (0, m

, m

, ..., m

) = ϕ(m

, m

, ..., m

)

(3.1)

f (s(n), m

, m

, ..., m

) = ψ(n, m

, m

, ..., m

, f (n, m

, m

, ..., m

)).

(3.2)

Dowód twierdzenia pomijamy.
Pierwszy z powyższych warunków nazywamy początkowym, a dru-

gi rekursywnym. Przedstawiony w twierdzeniu schemat definiowania
funkcji nazywamy schematem rekursji prostej.

Wniosek. Jeżeli A jest dowolnym zbiorem niepustym, zaś ϕ :

N → A

i ψ :

N × N × A → A są dowolnymi funkcjami, to istnieje dokładnie

jedna funkcja f :

N × N → A, taka że dla dowolnych liczb naturalnych

m i n

f (0, m) = ϕ(m)

(3.3)

oraz

f (s(n), m) = ψ(n, m, f (n, m)).

(3.4)

Zbiór liczb naturalnych. Definiowanie przez indukcję

Niekiedy korzysta się ze schematu definiowania przez indukcję

w jeszcze prostszej postaci.

Wniosek. Załóżmy, że A jest dowolnym niepustym zbiorem. Niech
a ∈ A i niech dana będzie funkcja γ : A → A. Wtedy istnieje dokładnie
jedna funkcja f :

N → A, taka że

f (0) = a

(3.5)

f (s(n)) = γ(f (n)).

(3.6)

Korzystając z pierwszego z wniosków, można w zbiorze liczb natu-

ralnych zdefiniować działania dodawania i mnożenia.

Twierdzenie 3.2 Istnieje funkcja + :

N × N → N o tej własności, że

dla dowolnych m, n ∈

+(0, m) = m,

+(s(n), m) = s(+(n, m)).

Funkcja ta jest wyznaczona jednoznacznie.

Dowód. Należy zastosować pierwszy z wniosków do funkcji ψ :

N ×

N × N → N określonej zależnością

ψ(j, k, l) = s(l).

Istnieje dokładnie jedna funkcja + :

N × N → N, taka że

+(0, m) = ϕ(m) = m

+(s(n), m) = ψ(n, m, +(n, m)) = s(+(n, m))

dla dowolnych n, m ∈

N. Dowód jest zakończony.

Umowa notacyjna. W dalszym ciągu zamiast pisać +(n, m), będzie-
my pisać n + m. Ponadto, zamiast symbolu s(n), będziemy pisać n + 1.
Liczbę n + m nazywać będziemy sumą liczb n oraz m.

Zbiór liczb naturalnych i indukcja

Twierdzenie 3.3 Dla dowolnych k, n, m ∈

(i) k + n = n + k,

(ii) k + (n + m) = (k + n) + m.

Dowód twierdzenia pozostawiamy Czytelnikowi.
Również w sposób indukcyjny można zdefiniować mnożenie liczb

naturalnych.

Twierdzenie 3.4 Istnieje dokładnie jedna funkcja · :

N × N → N,

taka że

·(0, m) = 0,

·(n + 1, m) = ·(n, m) + m.

Prosty dowód tego twierdzenia pomijamy.

Umowa notacyjna. W dalszym ciągu zamiast pisać ·(m, n) będziemy
pisać m · n lub mn. Liczbę mn nazywamy iloczynem liczb m i n.

Iloczyn ma własności analogiczne jak dodawanie.

Twierdzenie 3.5 Dla dowolnych liczb k, m, n ∈

(i) km = mk,

(ii) (km)n = k(mn).

Ponadto zachodzi

Twierdzenie 3.6 Dla dowolnych k, m, n ∈

k(m + n) = (km) + (kn).

Powyższa równość to oczywiście prawo rozdzielności mnożenia

względem dodawania. Przy założeniu, że mnożenie ma priorytet w sto-
sunku do dodawania, nawiasy po prawej stronie równości mogą być
pominięte.

Zbiór liczb naturalnych. Definiowanie przez indukcję

Przykład

(i) Jedną z najczęściej definiowanych indukcyjnie funkcji jest silnia,

czyli funkcja ! :

N → N, taka że

!(0) = 1

oraz

!(n + 1) = (n + 1)!(n).

Jej istnienie, a także to, że taka funkcja jest jedna, wynika z wa-
runków (3.3) i (3.4).
Rzeczywiście, jeżeli przyjmiemy

ϕ(n) = 1,

n ∈

oraz

ψ(j, k, l) = (j + 1)l,

to istnieje funkcja f , taka że

f (0, m) = 1

f (n + 1, m) = (n + 1)f (n, m),

n, m ∈

Przyjmijmy

!(n) = f (n, 0).

Z powyższej definicji wynika, że

!(0) = f (0, 0) = 1

oraz

!(n + 1) = f (n + 1, 0) = (n + 1) · f (n.0) = (n + 1)·!(n).

W dalszym ciągu, zamiast pisać !(n), będziemy stosowali trady-
cyjny zapis n!.

Zbiór liczb naturalnych i indukcja

(ii) Niech k

∈

N. Istnieje dokładnie jedna funkcja h : N → N, taka

że

h(0) = 1

oraz

h(n + 1) = k

· h(n).

Korzystamy tu z warunków (3.5) i (3.6), przyjmując a = k

oraz

γ(n) = k

· n.

Funkcję h nazywamy wykładniczą i stosujemy zapis

h(n) = k

3.2

Funkcje rekurencyjne

W poprzednim podrozdziale został przedstawiony pewien ważny

sposób definiowania nowych funkcji - za pomocą indukcji albo, inaczej
mówiąc, w oparciu o schemat tzw. rekursji prostej.

Obok tej metody, wykorzystuje się jeszcze kilka innych sposobów

definiowania funkcji [10, s. 342n]. Skoncentrujemy uwagę na trzech,
szczególnie istotnych sposobach definiowania.

Niekiedy przy definiowaniu funkcji bierze się pod uwagę różne przy-

padki, w każdym z nich określając funkcję inną zależnością.

Przykład. Rozważmy funkcje

(i)

f (n) =

(

dla n < 10,

dla n  10

(ii)

g(n, m) =

(

n − m dla n > m,
0

dla n ¬ m

W ostatnim przypadku stosuje się oznaczenie

g(n, m) = n ˙

−m.

Funkcje rekurencyjne

Zauważmy, że w ogólnym przypadku tego rodzaju definicje mają

postać

f (n

, n

, ..., n

) =

(

ϕ(n

, n

, ..., n

), jeśli (n

, n

, ..., n

) ∈ ρ,

ψ(n

, n

, ..., n

), jeśli (n

, n

, ..., n

) /

∈ ρ,

gdzie ϕ :

→

N, ψ : N

→

N, natomiast ρ jest dowolną relacją

r-członową w zbiorze

Inny ważny sposób definiowania opiera się na pojęciu superpozycji

funkcji.

Przykład. Niech dane będą funkcje

f (n, m, k) = n + m + k + 1,

n, m, k ∈

oraz

g(l) = 1,

l ∈

Wtedy w wyniku superpozycji otrzymujemy między innymi funkcje

f (g(l), m, k) = m + k + 2,

f (n, g(l), k) = n + k + 2,

f (n, m, g(l)) = n + m + 2

oraz

g(f (n, m, k)) = 1,

n, m, k, l ∈

Przyjmujemy też, że wynikiem superpozycji są funkcje otrzymane w wy-
niku przyrównania niektórych argumentów.

Przykład. Rozważmy funkcje, których wartości dane są zależnościami

f (n, m, k) = n + m

+ k

oraz

g(l) = l,

n, m, k, l ∈

Wtedy, na przykład,

f (g(l), g(l), k) = l

+ l + k

Zbiór liczb naturalnych i indukcja

oraz

f (g(l), g(l), g(l)) = l

+ 2l.

W pierwszym przypadku przyrównaliśmy do siebie pierwsze dwa

parametry, w drugim - wszystkie trzy. Ponieważ symbole n, m, k, l
są jedynie tzw. zmiennymi bieżącymi, funkcje nie ulegną zmianie, gdy
zastąpimy je innymi parametrami. W przypadku pierwszej funkcji mo-
żemy, co wydaje się dość naturalne, przyjąć zamiast l zmienną n (lub
m). Wtedy wartości funkcji piszemy następująco

f (g(n), g(n), k) = n

+ n + k.

Podobnie można postąpić w przypadku drugiej funkcji, pisząc

f (g(n), g(n), g(n)) = n

+ 2n.

Jeszcze jeden sposób definiowania funkcji opiera się na zastosowa-

niu operacji minimum do pewnej relacji ρ ⊂

r+1

. Mianowicie, okre-

ślamy

(µm)[(n

, n

, ..., n

, m) ∈ ρ]

jako najmniejszą liczbę naturalną m, dla której zachodzi relacja ρ lub
0, jeśli liczba taka nie istnieje.

Przykład. Rozważmy relację ρ ⊂

, taką że

nρm ⇔ n · m > 10.

Wtedy

(µm)[n · m > 10] = Ent

+ 1,

n ∈

gdzie Ent(x) oznacza największą liczbę całkowitą, która jest mniejsza
lub równa od x, x ∈

R, oraz

(µ0)[0 · m > 10] = 0.

Otrzymujemy w ten sposób funkcję, której wartości wyrażają się

zależnością

f (n) =

(

dla n = 0,

Ent

+ 1 dla n  1.

Funkcje rekurencyjne

Definicja 3.2 Funkcję f :

→

N określoną zależnością

f (n

, n

, ..., n

) = (µm)[(n

, n

, ..., n

, m) ∈ ρ]

nazywamy zdefiniowaną za pomocą operacji minimum efektywnego, je-
żeli dla dowolnych n

, n

, ..., n

∈

N istnieje m, takie że

, n

, ..., n

, m) ∈ ρ.

Przykład

(i) Funkcja z poprzedniego przykładu nie została zdefiniowana za

pomocą minimum efektywnego, bo dla n = 0 nie istnieje m ∈

o tej własności, że 0ρm.

(ii) Funkcja określona za pomocą operacji

n 7−→ (µm)[m + n > 10]

jest zdefiniowana w sposób efektywny, gdyż w tym przypadku

n 7−→

(

11 − n dla n ¬ 10,
0

dla n > 10

i jak łatwo widać dla dowolnej liczby n ∈

N istnieje m ∈ N, takie

że nρm.

W matematyce jest rzeczą istotną, jakimi metodami dowodzenia

się posługujemy. Czy dowodząc jakieś twierdzenie, wykazujemy jedy-
nie istnienie postulowanego obiektu matematycznego, czy też konstru-
ujemy go w skończonej liczbie kroków przy zastosowaniu uchwytnych
intuicyjnie elementarnych operacji. Jakie operacje uznajemy za elemen-
tarne (czyli, jak je nazywamy - proste), a jakie metody za efektywne,
ukazują poniższe definicje.

Definicja 3.3 Funkcję f : A →

N, gdzie A jest pewnym właściwym

podzbiorem

(tzn. A 6=

) nazywamy funkcją częściową.

Funkcję f :

→

N nazywamy funkcją całkowitą.

Definicja 3.4 Funkcjami prostymi są funkcje całkowite, określone na-
stępującymi zależnościami:

Zbiór liczb naturalnych i indukcja

(i) o(n) = 0,

(ii) s(n) = n + 1,

(iii) I

, n

, ..., n

) = n

1 ¬ k ¬ r.

Definicja 3.5 Funkcję f : A →

N, A ⊂ N

, nazywamy:

a) pierwotnie rekurencyjną, jeśli może być uzyskana z funkcji pro-

stych za pomocą superpozycji i rekursji prostej,

b) częściowo rekurencyjną, jeśli powstaje z funkcji prostych za po-

mocą superpozycji, rekursji prostej i minimum efektywnego,

c) ogólnie rekurencyjną (obliczalną), jeśli jest całkowitą funkcją czę-

ściowo rekurencyjną.

Przykład

(i) Rozważmy funkcję określoną zależnością

f (n) = n + k,

n ∈

gdzie k ∈

jest ustaloną liczbą. Ponieważ

f = s ◦ s ◦ ... ◦ s

}

k razy

więc f jest funkcją całkowitą pierwotnie rekurencyjną. Jest też
oczywiście funkcją ogólnie rekurencyjną.

(ii) Z kolei funkcja dwóch zmiennych dana zależnością

f (n, m) = m

może zostać zdefiniowana indukcyjnie czyli w oparciu o schemat
rekursji prostej, bowiem

f (0, m) = 1,

(ϕ(m) = 1)

f (n + 1, m) = f (n, m) · m,

(ψ(j, k, l) = k · l).

Wykorzystujemy tu umowę, zgodnie z którą 0

= 1. Zatem funk-

cja ta jest pierwotnie rekurencyjną funkcją całkowitą.

Zastosowanie rekurencji ...

Definicja 3.6 Jeżeli ρ ⊂

jest relacją r-członową, to funkcję

, n

, ..., n

) =

(

1 jeśli (n

, n

, ..., n

) ∈ ρ,

0 jeśli (n

, n

, ..., n

) /

∈ ρ

nazywa się funkcją charakterystyczną tej relacji.

Definicja 3.7 Jeśli A ⊂

, to funkcją charakterystyczną tego zbioru

nazywa się funkcję

, n

, ..., n

) =

(

1 jeśli (n

, n

, ..., n

) ∈ A,

0 jeśli (n

, n

, ..., n

) /

∈ A.

Powyższe definicje pozwalają na przeniesienie pojęcia rekurencji

na zbiory i relacje.

Definicja 3.8 Zbiór lub relację nazywać będziemy rekurencyjnymi, je-
śli odpowiadające im funkcje charakterystyczne są pierwotnie rekuren-
cyjne. Podobnie, zbiór lub relację nazywać będziemy ogólnie rekuren-
cyjnymi, jeśli odpowiadające im funkcje charakterystyczne są ogólnie
rekurencyjne.

Przykład. Nietrudno sprawdzić, że poniższe relacje są rekurencyjne:

(i) relacja identycznościowa I

⊂

N × N, taka że

m ⇔ n = m,

(ii) relacja ρ ⊂

o tej własności, że

(n, m, k) ∈ ρ ⇔ n + m = k.

Rekurencyjne są też oczywiście zbiory odpowiadające tym rela-

cjom.

3.3

Zastosowanie rekurencji: automaty
skończone i ich języki

Na wstępie tego podrozdziału przedstawimy dwie definicje.

Zbiór liczb naturalnych i indukcja

Definicja 3.9 Zbiorem przeliczalnym nazywamy każdy zbiór A, dla
którego istnieje bijekcja f :

N → A.

Nietrudno wykazać, że zbiorami przeliczalnymi są na przykład:

zbiór wszystkich naturalnych liczb parzystych

par

, zbiór wszystkich

liczb całkowitych

Z, a także zbiór wszystkich liczb wymiernych Q.

Definicja 3.10 Zbiór A nazywamy skończonym, jeśli dla pewnego n ∈
N istnieje bijekcja

f : {0, 1, ..., n} → A.

Rozróżnienie pomiędzy, z jednej strony, zbiorami przeliczalnymi

i skończonymi, a z drugiej strony - zbiorami nieskończonymi nieprzeli-
czalnymi (takimi jak

R) jest niezwykle ważne w matematyce dyskret-

nej. W jednym z kolejnych rozdziałów zajmiemy się dokładniej wła-
snościami zbiorów skończonych, w szczególności metodami zliczania
ich elementów.

Możemy przejść do zasadniczego tematu tego podrozdziału.

Definicja 3.11 Alfabetem języka automatu skończonego nazywamy
skończony zbiór symboli

= {α

, α

, ..., α

r ∈

Słowem języka takiego automatu nazywamy dowolny skończony ciąg

symboli (być może powtarzających się) pochodzących z alfabetu

Słowo, które nie zawiera ani jednego symbolu nazywać będziemy

pustym; będzie ono oznaczane symbolem λ.

Konkatenacją dwóch słów w

= α

...α

oraz w

= α

...α

nazywamy słowo

= α

...α

Definicja 3.12 Językiem formalnym nad alfabetem

nazywamy zbiór

∗

wszystkich słów, włącznie ze słowem pustym, utworzonych z symboli

tego alfabetu.

Zastosowanie rekurencji ...

Przykład

(i) Jeżeli

= {a, b, c}, to

∗

= {λ, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb,

cc, aaa, ...}. Konkatenacją słów abc i cc jest słowo abccc, ale także
słowo ccabc.

(ii) Niech

= {0, 1}. Wtedy

∗

= {λ, 0, 1, 00, 01, 10, 11, 000, ...}.

Konkatenacjami słów 010 i 101 są słowa 010101 oraz 101010.

Definicja 3.13 Długością słowa w ∈

∗

nazywamy liczbę |w| symboli

alfabetu tworzących to słowo.

Definicja 3.14 Przedrostkiem słowa w nazywa się dowolne słowo σ,
takie że istnieje słowo τ , iż

w = στ.

Przyrostkiem słowa w nazywa się dowolne słowo τ o tej własności,

że istnieje słowo σ, takie że zachodzi powyższa równość.

Definicja 3.15 ([11, s. 30]) Automatem skończonym nazywać będzie-
my strukturę

A = (Q,

, δ, q

, E),

gdzie Q = {q

, q

, ..., q

} jest zbiorem stanów automatu A,

jest al-

fabetem wejściowym automatu, q

jest stanem początkowym, a E ⊂ Q

zbiorem stanów końcowych tego automatu, natomiast

δ : Q ×

→ Q

jest tzw. funkcją przejścia, która stanom automatu oraz symbolom al-
fabetu przyporządkowuje stany automatu.

Działanie automatu skończonego możemy zilustrować następująco:

· · α β γ · · · ·

sterowanie

(i)

· · α β γ · · · ·

δ(q, β)

sterowanie

(ii)

Zbiór liczb naturalnych i indukcja

Automat znajdujący się w stanie q czyta z taśmy symbol alfabetu

β, a następnie głowica przesuwa się o jedno miejsce w prawo i zarazem
automat przechodzi do stanu δ(q, β).

W przypadku, gdy głowica urządzenia przesunęła się na prawy

koniec taśmy, mówimy, że automat A zaakceptował całe słowo zapisane
na taśmie.

Przykład. Rozważmy automat skończony przedstawiony następują-
cym diagramem

start

end

Stanem początkowym tego automatu jest q

, a stanem końcowym q

Symbolom alfabetu 0 i 1 oraz stanom odpowiadają przejścia zaznaczo-
ne łukami skierowanymi. Słowami akceptującymi, tzn. przeprowadza-
jącymi automat ze stanu początkowego q

w stan końcowy q

, są na

przykład

00, 0100, 010100, 1, 011, 01011.

Do tej pory pisaliśmy o pojedynczych symbolach alfabetu, których

odczytywanie przeprowadza automat z jednego stanu w drugi (może
być on stanem wyjściowym). Znacznie wygodniej jest jednak rozważać
całe słowa. W związku z tym należy zdefiniować nową funkcję

: Q ×

∗

→ Q,

która stanom i słowom języka przyporządkowuje stany automatu. Funk-
cję tę definiujemy indukcyjnie, korzystając z nieco zmodyfikowanej za-
sady indukcji, którą łatwo można otrzymać w oparciu o znane już
metody definiowania przez indukcję.

Zastosowanie rekurencji ...

Definicja 3.16 Funkcję δ

definiujemy następująco:

(q, λ) = q

(q, wα) = δ(δ

(q, w), α).

Przykład. Dla automatu z poprzedniego przykładu

, 01010) = q

, 100) = q

Definicja 3.17 Załóżmy, że A ⊂

∗

. Wtedy zbiory A

definiujemy

indukcyjnie następująco:

def

= {λ},

def

= AA

r−1

r  1.

Ponadto przyjmujemy

∗

def

∞

[

r=0

def

∞

[

r=1

∗

nazywamy domknięciem Kleenego zbioru A, natomiast A

nazywa-

my domknięciem dodatnim tego zbioru.

Zbiory słów wygodnie jest reprezentować za pomocą tzw. wyrażeń

regularnych. Ich ścisłe określenie zawiera poniższa definicja.

Definicja 3.18 Niech

będzie alfabetem pewnego języka automatu

skończonego. Wyrażeniami regularnymi tego języka są:

(i) ∅ - odpowiadające zbiorowi pustemu,

(ii) λ - odpowiadające zbiorowi {λ},

(iii) α - odpowiadające zbiorowi {α}, gdzie α ∈

Zbiór liczb naturalnych i indukcja

(iv) jeśli w i σ są wyrażeniami regularnymi odpowiadającymi odpo-

wiednio zbiorom A i B, A, B ⊂

∗

, to wσ, w + σ i w

∗

są wyra-

żeniami regularnymi odpowiadającymi zbiorom AB, A ∪ B, A

∗

Umowa notacyjna. W dalszym ciągu będziemy przyjmować, że sym-
bol ∗ wiąże silniej niż konkatenacja, a ta z kolei wiąże silniej niż sym-
bol +.

Przykład Niech dany będzie alfabet

= {0, 1}. Wtedy

(i) wyrażenie 101 reprezentuje zbiór {101},

(ii) wyrażenie 0 + 1 reprezentuje zbiór {0, 1},

(iii) wyrażenie 0

∗

+ 1

∗

reprezentuje zbiór {λ, 0, 1, 00, 11, ...},

(iv) wyrażenie (0 + 1)

∗

reprezentuje zbiór

∗

(v) wyrażenie 11(0 + 1)

∗∗

000 reprezentuje zbiór wszystkich słów za-

czynających się od co najmniej dwóch jedynek a kończących się
co najmniej trzema zerami.

Twierdzenie 3.7 ([11, s. 66]) Dla dowolnych wyrażeń regularnych
w, σ, τ zachodzą zależności

(i) w + σ = σ + w,

(ii) w + (σ + τ ) = (w + σ) + τ ,

(iii) w(στ ) = (wσ)τ ,

(iv) w(σ + τ ) = wσ + wτ ,

(σ + τ )w = σw + τ w,

(v) (w

∗

)

∗

= w

∗

(vi) (w

∗

)

∗

= (w + σ)

∗

(vii) ∅

∗

= λ,

(viii) (w + λ)

∗

= w

∗

Łatwy dowód powyższego twierdzenia pozostawiamy Czytelnikowi.

Definicja 3.19 Niech dany będzie automat skończony A. Językiem ak-
ceptowalnym przez ten automat nazywamy zbiór

L(A) = {w ∈

∗

q∈E

, w) = q}.

Zastosowanie rekurencji ...

Przykład. Rozważmy jeszcze raz ten sam, co poprzednio, automat
trzystanowy. Nietrudno zauważyć, że słowa akceptowalne przez ten
automat są postaci

w00

lub

w1,

gdzie w jest albo zbiorem pustym, albo jest postaci

01, 0101, 010101, itd.

Zatem L(A) jest reprezentowany przez wyrażenie regularne

(01)

∗

(00 + 1).

Czy każdy język

∗

jest akceptowalny przez pewien automat skończo-

ny? Jak się okazuje, nie. Można dowieść (dowód jest dość skomplikowa-
ny), że język jest akceptowalny przez automat skończony wtedy i tylko
wtedy, gdy język ten jest reprezentowany przez wyrażenie regularne.

Kraty. Algebry Boole’a

i funkcje booleowskie

4.1

Kraty i ich własności

Definicja 4.1 Niepusty zbiór K z relacją częściowego porządku ⊂
K

nazywamy kratą, jeśli dla dowolnych elementów x, y ∈ K

sup{x, y} ∈ K

inf{x, y} ∈ K.

Kratę będziemy zapisywać przy pomocy symbolu (K, ).

Twierdzenie 4.1 Niech x

, x

, ..., x

będą elementami kraty (K, ).

Wtedy

sup{x

, x

, ..., x

} = sup{sup{x

, x

, ..., x

r−1

}, x

}

oraz

inf{x

, x

, ..., x

} = inf{inf{x

, x

, ..., x

r−1

}, x

Dowód. Wykażemy pierwszą z powyższych równości. Dowód drugiej
jest analogiczny.

Kraty. Algebry Boole’a i funkcje booleowskie

Oznaczmy

a = sup{x

, x

, ..., x

}

b = sup{sup{x

, x

, ..., x

r−1

}, x

Oczywiście x

 a, x

 a, ..., x

 a. Stąd wynika, że

sup{x

, x

, ..., x

r−1

} a.

Zatem b a (wykorzystaliśmy tu definicję supremum jako najmniej-
szego z ograniczeń górnych).

Z drugiej strony, b jest ograniczeniem górnym zbioru {x

, x

, ...,

r−1

}, więc x

 b, x

 b, ..., x

r−1

 b. Także x

 b.

Zatem b jest ograniczeniem górnym zbioru {x

, x

, ..., x

}. Dlatego

a b. Ostatecznie a = b.

Umowa notacyjna. Będziemy stosować oznaczenia

x ∪ y = sup{x, y}

oraz

x ∩ y = inf{x, y}.

Z powyższymi symbolami zetknęliśmy się już w rozdziale 1, rozwa-

żając działania w zbiorze {

0, 1}. Zastosowanie tych samych oznaczeń

jest nieprzypadkowe, ponieważ zbiór {

0, 1} z działaniami ∪ oraz ∩ jest

szczególnie ważnym przykładem kraty.

Przykład. Obok zbioru {

0, 1} z działaniami ∪ oraz ∩, kratami są

także na przykład:

(i) zbiór P(A) wszystkich podzbiorów zbioru niepustego A z relacją

częściowego porządku

X Y ⇔ X ⊂ Y.

W tym przypadku

sup{X, Y } = X ∪ Y

inf{X, Y } = X ∩ Y,

(ii) dowolny zbiór liniowo uporządkowany,

Kraty i ich własności

(iii) zbiór P = {

0, x

, x

1} z relacją częściowego porządku przed-

stawioną poniższym diagramem

Krata ta nazywana jest pentagonem.

(iv) zbiór D = {

0, x

, x

1} z relacją częściowego porządku przed-

stawioną diagramem

Krata ta nazywana jest diamentem.

(v) zbiór B = {2

· 3

: n, k ∈

Z} z relacją podzielności,

(vi)

z relacją podzielności.

Twierdzenie 4.2 Niech x, y, z będą elementami kraty (K, ). Wtedy

(i) x ∪ y = y ∪ x,

(ii) x ∩ y = y ∩ x,

(iii) x ∪ (y ∪ z) = (x ∪ y) ∪ z,

(iv) x ∩ (y ∩ z) = (x ∩ y) ∩ z,

(v) x ∩ (y ∪ z) = (x ∩ y) ∪ (x ∩ z),

(vi) x ∪ (y ∩ z) = (x ∪ y) ∩ (x ∪ z).

Kraty. Algebry Boole’a i funkcje booleowskie

Dowód wynika natychmiast z definicji działań ∪ i ∩ oraz z po-

przedniego twierdzenia.

Wniosek. (prawa idempotentności) Dla dowolnego elementu x kraty
(K, )

(i) x ∪ x = x,

(ii) x ∩ x = x.

Twierdzenie 4.3 Dla dowolnych elementów x, y kraty (K, ) poniż-
sze trzy warunki są sobie równoważne

(i) x y,

(ii) x ∪ y = y,

(iii) x ∩ y = x.

Dowód. Implikacje (i)⇒(ii) oraz (i)⇒(iii) są natychmiastowe. Jeżeli
x ∪ y = y, to x y, a zatem także x ∩ y = x.

Twierdzenie 4.4 Dla dowolnych elementów x, y kraty (K, ) zacho-
dzą tzw. prawa pochłaniania

(i) x ∩ (x ∪ y) = x,

(ii) x ∪ (x ∩ y) = x.

Dowód

(i) Na mocy definicji kresu dolnego

x ∩ (x ∪ y)  x.

Z drugiej strony x x oraz x x∪y. Zatem x jest ograniczeniem
dolnym zbioru

{x, x ∪ y}.

Jednak x ∩ (x ∪ y) jest największym ograniczeniem dolnym tego
zbioru. Dlatego

x x ∩ (x ∪ y).

Ostatecznie otrzymujemy tezę.

Kraty i ich własności

Dowód równości (ii) jest analogiczny.

Definicja 4.2 Kratę (K, ), która ma element najmniejszy

0 i ele-

ment największy

1 nazywamy kratą z zerem i jednością.

Przykład

(i) Zbiór

B = {0, 1} z działaniami ∪ i ∩ jest kratą z zerem i jedno-

ścią.

(ii) Zbiór P(A) wszystkich podzbiorów niepustego zbioru A z relacją

inkluzji jest kratą z zerem i jednością. Dla tej kraty

0 = ∅ oraz

1 = A.

(iii) Zbiór {2, 4, 6, 10, 12, 20, 30, 60} z relacją podzielności jest kratą

z zerem i jednością. Zerem tej kraty jest liczba 2, jednością jest
liczba 60.

(iv) Każda krata skończona jest kratą z zerem i jednością.

Twierdzenie 4.5 Dla dowolnego elementu x kraty (K, ) z zerem
i jednością

(i) 0  x  1,

(ii)

0 ∩ x = 0, 0 ∪ x = x,

(iii)

1 ∩ x = x, 1 ∪ x = 1.

Dowód twierdzenia jest oczywisty.

Na zakończenie tego podrozdziału przedstawimy jeszcze jedno waż-

ne pojęcie.

Definicja 4.3 Niech dane będą dwie kraty (K

, 

) oraz (K

, 

Funkcję f : K

→ K

, taką że dla dowolnych x, y ∈ K

x 

y ⇒ f (x)

f (y)

nazywamy homomorfizmem krat. Jeśli f jest bijekcją, to f nazywamy
izomorfizmem krat.

Kraty. Algebry Boole’a i funkcje booleowskie

Przykład. Rozważmy rodzinę zbiorów {∅, {0}, {1}, {2}, {0, 1, 2}} upo-
rządkowaną przez relację zawierania się oraz zbiór liczb {2, 4, 6, 8, 24}
z relacją podzielności. Oba zbiory sa izomorficznymi kratami. Odpo-
wiadają im podobne diagramy.

{1}

{1, 2, 3}

{0}

{2}

∅

Izomorfizm f : {∅, {0}, {1}, {2}, {0, 1, 2}} → {2, 4, 6, 8, 24} ma po-

stać

f (∅) = 2,

f ({0}) = 4,

f ({1}) = 6,

f ({2}) = 8,

f ({0, 1, 2}) = 24.

Nietrudno zauważyć, że homomorfizm krat ma następujące wła-

sności.

Twierdzenie 4.6 Załóżmy, że f : K

→ K

jest homomorfizmem krat

, 

) i (K

, 

). Wtedy

f (x ∪

y) = f (x) ∪

f (y)

f (x ∩

y) = f (x) ∩

f (y),

gdzie x, y ∈ K

. Ponadto, obrazem homomorficznym zera i jedności

kraty K

są odpowiednio zero i jedność kraty K

Algebry Boole’a

4.2

Algebry Boole’a

Algebry Boole’a należą do najważniejszych struktur matematycz-

nych. Z przykładami algebr Boole’a spotkaliśmy się już w rozdziale 1
tej książki, jakkolwiek sam termin: algebra Boole’a nie został wtedy
użyty. Przedstawimy definicję tego ważnego pojęcia.

Definicja 4.4 ([3, s. 342]) Algebrą Boole’a nazywamy strukturę (B,
∪, ∩, −,

0, 1}, gdzie B jest zbiorem, do którego należą 0 i 1, ∪ oraz ∩

są działaniami dwuargumentowymi nazywanymi dodawaniem i mnoże-
niem booleowskim

∪ : B × B → B,

∩ : B × B → B,

natomiast − jest działaniem jednoargumentowym nazywanym dopeł-
nieniem

− : B → B,

przy czym dla dowolnych x, y, z ∈ B spełnione są równości

(i)

x ∪ y = y ∪ x,

(prawa przemienności)

(ii)

x ∩ y = y ∩ x,

(iii)

x ∪ (y ∪ z) = (x ∪ y) ∪ z,

(prawa łączności)

(iv)

x ∩ (y ∩ z) = (x ∩ y) ∩ z,

(v)

x ∩ (x ∪ y) = x,

(prawa pochłaniania)

(vi)

x ∪ (x ∩ y) = x,

(vii)

x ∩ (y ∪ z) = (x ∩ y) ∪ (x ∩ z),

(prawa rozdzielności)

(viii)

x ∪ (y ∩ z) = (x ∪ y) ∩ (x ∪ z),

(ix)

x ∪ (−x) =

(prawa dopełnienia)

(x)

x ∩ (−x) =

Kraty. Algebry Boole’a i funkcje booleowskie

Umowa. W dalszym ciągu tego rozdziału będziemy zakładać, że sym-
bol − wiąże silniej niż symbol ∩, a ten z kolei wiąże silniej niż ∪.

Uwaga. Nietrudno zauważyć (por. np. [3, s. 34]), że krata (K, )
z zerem i jednością oraz działaniami ∪ i ∩, zdefiniowanymi tak jak
w poprzednim podrozdziale, jest algebrą Boole’a, o ile spełniony jest
warunek

x∈K

y∈K

(x ∪ y =

1 ∧ x ∩ y = 0).

Przykład

(i) Algebrą Boole’a jest rozważany już zbiór

B = {0, 1} z działania-

x ∪ y = max{x, y}

x ∩ y = min{x, y}

oraz

−x =

1 − x.

(ii) Zbiór

z działaniami

, x

, ..., x

) ∪ (y

, y

, ..., y

) =

= (max{x

, y

}, max{x

, y

}, ..., max{x

, y

})

oraz

, x

, ..., x

) ∩ (y

, y

, ..., y

) =

= (min{x

, y

}, min{x

, y

}, ..., min{x

, y

})

−(x

, x

, ..., x

) = (1 − x

, 1 − x

, ..., 1 − x

)

jest także algebrą Boole’a.

(iii) Zbiór P(A), gdzie A jest zbiorem niepustym, z działaniami sumy

mnogościowej, iloczynu mnogościowego oraz dopełnienia, jest al-
gebrą Boole’a. Zerem tej algebry jest zbiór pusty, a jednością jest
zbiór A.

Algebry Boole’a

(iv) Dla dowolnej liczby naturalnej n > 1 zbiór Div(n) wszystkich

jej naturalnych dzielników (wraz z samą liczbą n) jest algebrą
Boole’a z działaniami (por. [15, s. 601])

k ∪ l = N W W (k, l),

k ∩ l = N W D(k, l)

−k =

gdzie, przypomnijmy, N W W (k, l) oznacza najmniejszą wspólną
wielokrotność liczb k i l, zaś N W D(k, l) oznacza najmniejszy
wspólny dzielnik tych liczb, jeśli w rozkładzie liczby n na liczby
pierwsze, te ostatnie występują w pierwszej potędze.
Tak jest np. dla n = 210 = 2

· 3

· 5

· 7

. Ale już dla n = 60 =

· 3

· 5

Div(60) nie jest algebrą Boole’a, bo 2 ∪ −2 = 2 ∪ 30 =

30 6= 60; należy bowiem pamiętać, że jeśli Div(n) jest algebrą
Boole’a, to jej jednością jest liczba n, a zerem liczba 1.

Twierdzenie 4.7 Dla dowolnych elementów x, y algebry Boole’a (B, ∪,
∩, −,

0, 1) zachodzą zależności

(i) x ∪ x = x,

(ii) x ∩ x = x,

(iii) x ∪

0 = x,

(iv) x ∩

1 = x,

(v) x ∪ y = y ⇔ x ∩ y = x.

Dowód. (i) Na podstawie prawa pochłaniania (vi)

x ∪ (x ∩ (x ∪ x)) = x.

Zarazem, na podstawie (v), x ∩ (x ∪ x) = x. Tak więc, x ∪ x = x.

Dowód (ii) jest analogiczny. Z kolei (iii) jest konsekwencją zależ-

ności

x ∪

0 = x ∪ (x ∩ −x) = x,

Kraty. Algebry Boole’a i funkcje booleowskie

która wynika także z prawa pochłaniania (vi). Dowód (iv) jest podob-
ny. Dowód zależności (v) pozostawiamy Czytelnikowi jako nietrudne
ćwiczenie.

Każda algebra Boole’a jest zbiorem częściowo uporządkowanym

poprzez odpowiednio zdefiniowaną relację.

Definicja 4.5 Dla dowolnych elementów x, y algebry Boole’a (B, ∪, ∩,
−,

0, 1) definiujemy relację następująco

x y ⇔ x ∪ y = y.

Twierdzenie 4.8 Relacja określona powyższą zależnością jest rela-
cją częściowego porządku w algebrze (B, ∪, ∩, −,

0, 1).

Dowód. Relacja jest zwrotna, bo x ∪ x = x.

Relacja ta jest także słabo antysymetryczna, ponieważ jeśli x ∪ y =

y oraz y ∪ x = x, to oczywiście, biorąc pod uwagę przemienność sumy
booleowskiej, otrzymujemy x = y.

Relacja jest przechodnia. Rzeczywiście, załóżmy, że x y i y 

z. Oznacza to, że x ∪ y = y i y ∪ z = z. Zatem

x ∪ z = x ∪ (y ∪ z) = (x ∪ y) ∪ z = y ∪ z = z,

czyli x z.

Twierdzenie 4.9 Dla dowolnych elementów x, y algebry Boole’a za-
chodzą prawa De Morgana

−(x ∪ y) = −x ∩ −y

−(x ∩ y) = −x ∪ −y.

Dowód. Zauważmy, że

(x ∪ y) ∪ (−x ∩ −y) = ((x ∪ y) ∪ −x) ∩ ((x ∪ y) ∪ −y) =

= ((x ∪ −x) ∪ y) ∩ ((y ∪ −y) ∪ x) =

1 ∩ 1 = 1.

Algebry Boole’a

Analogicznie możemy wykazać, że

(x ∪ y) ∩ (−x ∩ −y) = (x ∩ (−x ∩ −y)) ∪ (y ∩ (−x ∩ −y)) =

= ((x ∩ −x) ∩ −y) ∪ ((y ∩ −y) ∩ −x) =
=

0 ∪ 0 = 0.

Z powyższych zależności wynika, iż

−(x ∪ y) = −(x ∪ y) ∪

0 = −(x ∪ y) ∪ ((x ∪ y) ∩ (−x ∩ −y)) =

= [−(x ∪ y) ∪ (x ∪ y)] ∩ [−(x ∪ y) ∪ (−x ∩ −y)] =

1 ∩ [−(x ∪ y) ∪ (−x ∩ −y)] =

= [(x ∪ y) ∪ (−x ∩ −y)] ∩ [−(x ∪ y) ∪ (−x ∩ −y)] =

= (−x ∩ −y) ∩ [(x ∪ y) ∪ −(x ∪ y)] = (−x ∩ −y) ∩

1 =

= −x ∩ −y.

Dowód równości −(x ∩ y) = −x ∪ −y przebiega podobnie.

Definicja 4.6 Atomem w algebrze Boole’a (B, ∪, ∩, −,

0, 1) nazywa-

my dowolny element x 6=

0, mający tę własność, że jeśli x = y ∪ z, to

y = x lub z = x.

Przykład

(i) Niech B = P(

N) z działaniami sumy mnogościowej i dopełnienia.

Atomami w tej algebrze Boole’a są zbiory jednoelementowe {n},
gdzie n ∈

(ii) Atomami w algebrze Boole’a

są elementy

(1, 0, 0, ..., 0, 0),
(0, 1, 0, ..., 0, 0),

. . . . . . . . . . . . . . .

(0, 0, 0, ..., 1, 0),
(0, 0, 0, ..., 0, 1).

Jest ich oczywiście n.

Kraty. Algebry Boole’a i funkcje booleowskie

(iii) W algebrze Boole’a Div(n), gdzie n = p

· p

· ... · p

, przy czym

, i = 1, 2, ..., r, są różnymi liczbami pierwszymi, atomami są

właśnie wszystkie wymienione liczby pierwsze.

Zachodzi ważne twierdzenie.

Twierdzenie 4.10 Załóżmy, że B jest skończoną algebrą Boole’a. Wte-
dy istnieje zbiór

U = {u

, u

, ..., u

}

zawierający wszystkie atomy algebry B, takie że dowolny niezerowy ele-
ment x algebry B jest skończoną sumą elementów zbioru U

x = u

∪ u

∪ ... ∪ u

Powyższe przedstawienie jest jednoznaczne z dokładnością do kolejności
składników.

Dowód. Po pierwsze, należy zauważyć, że nie istnieje element y ∈ B,
taki że

0 ≺ y ≺ u

, i = 1, 2, ..., n.

W dalszym ciągu załóżmy, że element x algebry B nie jest sumą

atomów. Oznacza to, że

x = y ∪ z,

gdzie

0 ≺ y ≺ x, 0 ≺ z ≺ x, oraz co najmniej jeden z elementów y i z

nie jest sumą atomów. Powyższe rozumowanie możemy powtórzyć dla
tego elementu y lub z, który nie jest sumą atomów. W konsekwencji
otrzymujemy ciąg malejący

x x

 x

 ...

elementów algebry niebędących sumami atomów. Jednak, ponieważ
zbiór B jest skończony, więc w powyższym ciągu powinien istnieć ele-
ment najmniejszy. Element ten jest atomem; z drugiej strony, wobec
założenia dotyczącego x, nie jest on atomem. Otrzymaliśmy sprzecz-
ność.

Wykażemy jednoznaczność przedstawienia x w postaci sumy ato-

mów. Załóżmy, że

x = y

∪ y

∪ ... ∪ y

Algebry Boole’a

oraz

x = z

∪ z

∪ ... ∪ z

gdzie y

, y

, ..., y

, z

, ..., z

są atomami.

Wtedy

x = x ∩ x = (y

∩ z

) ∪ (y

∩ z

) ∪ ... ∪ (y

∩ z

) ∪ (y

∩ z

) ∪ ... ∪ (y

∩ z

Zauważmy, że

∩ z

0 lub y

= z

i = 1, 2, ..., p,

l = 1, 2, ..., q.

W przeciwnym przypadku y

, i = 1, 2, ..., p oraz z

, l = 1, 2, ..., q,

nie byłyby atomami. W ten sposób twierdzenie zostało dowiedzione.

Definicja 4.7 Dwie algebry Boole’a

, ∪

, ∩

, −

)

oraz

, ∪

, ∩

, −

)

nazywamy homomorficznymi, jeśli istnieje funkcja f : B

→ B

, taka

że

f (x ∪

y) = f (x) ∪

f (y),

f (x ∩

y) = f (x) ∩

f (y),

f (−

x) = −

f (x)

dla dowolnych x, y ∈ B

. Wtedy f nazywamy homomorfizmem. Jeśli

f jest bijekcją, to algebry nazywamy izomorficznymi, a f nazywamy
izomorfizmem.

Przykład. Algebry Boole’a Div(n), gdzie n = p

...p

jest iloczynem

różnych liczb pierwszych, oraz P ({1, 2, ..., r}) są izomorficzne. Izomor-
fizm f : Div(n) → P ({1, 2, ..., r}) jest postaci

f (p

...p

) = {k ∈ {1, 2, ..., r} : i

= 1},

gdzie i

, i

, ..., i

= 0, 1.

Kraty. Algebry Boole’a i funkcje booleowskie

4.3

Formuły i funkcje booleowskie

Zaczniemy od indukcyjnej definicji standardowych formuł boole-

owskich zawierających jedynie znaki ∪, ∩ oraz −.

Definicja 4.8 Standardowymi formułami booleowskimi są

(i) zmienne x

, x

, ..., x

, ...,

(ii) stałe

0, 1,

(iii) jeśli w

i w

są standardowymi formułami booleowskimi, to są

nimi także (w

∪ w

), (w

∩ w

) oraz −w

Umowa notacyjna. Jak poprzednio przyjmiemy, że znak − wiąże
silniej niż ∩, a ten silniej niż ∪. W dalszym ciągu znak ∩ często będzie
pomijany.

W praktyce często zamiast używać symboli x

, x

, ..., x

, stosuje

się znaki x, y, x, t, ....

Definicja 4.9 Zbiór wszystkich standardowych formuł booleowskich
będziemy oznaczać symbolem

W, a zbiór wszystkich formuł booleowskich

n-zmiennych oznaczać będziemy symbolem

W(n), n  2.

Przykład. Wyrażeniami booleowskimi są na przykład

x ∩ y ∪ z ∩ (−x) ∩ (−t)

oraz

(xyz ∪ (−x)(−y)z)xy.

Pierwsze z tych wyrażeń jest formułą, która zależy od czterech zmien-
nych, a drugie - od trzech zmiennych. Można jednak spojrzeć na te
wyrażenia jako na zależne od większej liczby zmiennych, które jednak
explicite nie występują.

Definicja 4.10 Dwie formuły tej samej liczby zmiennych nazywamy
równoważnymi, jeśli dla dowolnego układu zer i jedności przyjmują one
zawsze te same wartości.

Formuły i funkcje booleowskie

Przykład

(i) Wyrażenia

= (xy ∪ xy(−z))z

oraz

= xyz

są sobie równoważne ponieważ z(−z) =

(ii) Także równoważne są wyrażenia

= −((−x

)(−x

)...(−x

))

oraz

= x

∪ x

∪ ... ∪ x

Równoważność formuł może być wykazana poprzez zastosowanie

odpowiednich przekształceń formuł booleowskich. Można także zasto-
sować, znaną z logiki, metodę tabelkową.

Przykład. Wykażemy, stosując metodę tabelkową, równoważność wy-
rażeń w

i w

z punktu (i) poprzedniego przykładu.

xy(−z)

xy ∪ xy(−z)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 1

Definicja 4.11 O wyrażeniu w ∈

W(n) będziemy mówić, że ma postać

normalną sumacyjno-iloczynową, jeżeli jest sumą booleowską tzw. ilo-
czynów minimalnych, tzn. wyrażeń postaci

∗
1

∗
2

...x

∗
n

gdzie x

∗
i

= x

lub x

∗
i

= −x

dla i = 1, 2, ..., n.

Kraty. Algebry Boole’a i funkcje booleowskie

Przykład

(i) Wyrażenie

w = xy(−z) ∪ (−x)(−y)x ∪ (−x)yz

ma postać normalną sumacyjno-iloczynową przy przyjęciu zało-
żenia, że w ∈

W(3). Gdyby w ∈ W(4) i czwartą zmienną było t,

należałoby wyrażenie w poddać przekształceniom

w = w ∩

1 = w ∩ (t ∪ −t) = [xy(−z) ∪ (−x)(−y)z ∪ (−x)yz]∩

∩(t ∪ −t) = xy(−z)t ∪ (−x)(−y)zt ∪ (−x)yzt∪

∪xy(−z)(−t) ∪ (−x)(−y)z(−t) ∪ (−x)yz(−t).

(ii) Wyrażenie w ∈

W(3)

w = xy ∪ z

nie ma żądanej postaci. Należy je poddać następującym prze-
kształceniom

xy ∪ z = xy(z ∪ −z) ∪ z(x ∪ −x)(y ∪ −y) = xyz ∪ xy(−z)∪

∪xyz ∪ x(−y)z ∪ (−x)yz ∪ (−x)(−y)z =

= xyz ∪ xy(−z) ∪ x(−y)z ∪ (−x)yz ∪ (−x)(−y)z.

Jak widać, każde wyrażenie booleowskie jest związane z pewną

funkcją, która układom zer i jedności przyporządkowuje zero lub jeden.

Definicja 4.12 Funkcją booleowską n-argumentową nazywamy każdą
funkcję

f :

→

Uwaga. Równoważne sobie formuły booleowskie tej samej liczby argu-
mentów generują tę samą funkcję booleowską. Opisując jej działanie,
można posłużyć się jednym z tychże wyrażeń lub tabelą.

Przykład. Weźmy pod uwagę funkcję booleowską f :

→

B, która

dana jest tabelką

Formuły i funkcje booleowskie

f (x, y, z)

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Nietrudno zauważyć, że wartości funkcji opisuje wyrażenie

(−x)y(−z) ∪ x(−y)(−z) ∪ x(−y)z,

będące sumą iloczynów minimalnych odpowiadających tym wierszom
powyższej tabelki, dla których f (x, y, z) =

Wartości funkcji booleowskich mogą być też określane przy użyciu

znaków różnych od ∪, ∩ czy −.

Przykład

(i) Niech dana będzie funkcja f :

→

B określona wzorem

f (x, y, z) = x + y + z,

gdzie znak + oznacza dodawanie modulo dwa. Funkcji tej odpo-
wiada tabela.

x + y + z

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Biorąc pod uwagę iloczyny minimalne, dla których x + y + z =

otrzymujemy

x + y + z = (−x)(−y)z ∪ (−x)y(−z) ∪ x(−y)(−z) ∪ xyz.

Kraty. Algebry Boole’a i funkcje booleowskie

(ii) W rozdziale 1 tej książki rozpatrywana była funkcja

→:

→

dana tabelką

x → y

0 0

0 1

1 0

1 1

Oczywiście

x → y = (−x)(−y) ∪ (−x)y ∪ xy.

Nietrudno zauważyć, że

x → y = −x ∪ y

oraz

x → y = −(x ∩ −y).

(iii) Weźmy pod uwagę funkcję

| :

→

określoną tabelką

x|y

0 0

0 1

1 0

1 1

Funkcja ta odpowiada logicznemu funktorowi nazywanemu „kre-
ską” Scheffera i może być nazwana funkcją Scheffera.
Zachodzą równości

x|y = (−x)(−y) ∪ (−x)y ∪ x(−y)

oraz

x|y = −(x ∩ y)

x|y = −x ∪ −y.

Formuły i funkcje booleowskie

Jak zatem widać, obok standardowych symboli booleowskich, ta-

kich jak ∪, ∩, −, można też użyć innych symboli, na przykład +, →
czy |. Przy zastosowaniu znaków ∪, ∩, − można zdefiniować wszyst-
kie inne funkcje booleowskie. Powstaje pytanie: jakie układy symboli,
czy ogólniej, funkcji booleowskich wystarczą do zdefiniowania funkcji
pozostałych.

W dalszej części tego podrozdziału przedstawimy twierdzenie, któ-

re odpowiada na to pytanie. Wypowiedź twierdzenia poprzedzimy kil-
koma definicjami (por. [12, s. 18-31]).

Definicja 4.13 Funkcję f

∗

→

B nazywamy dualną do funkcji

f :

→

B, jeżeli

∗

, x

, ..., x

) = −f (−x

, −x

, ..., −x

Przykład

(i) Funkcją dualną do x 7→ x jest ta sama funkcja.

(ii) Funkcja (x

, x

) 7→ x

∩ x

jest dualna do funkcji (x

, x

) 7→

∪ x

i vice versa, funkcja druga jest dualna do pierwszej.

Twierdzenie 4.11 Dla dowolnej funkcji f :

→

∗

)

∗

= f.

Dowód twierdzenia jest oczywisty.

Definicja 4.14 Dla dowolnego zbioru F skończenie argumentowych
funkcji booleowskich domknięciem [F ] nazywamy zbiór wszystkich funk-
cji otrzymanych z funkcji należących do F za pomocą operacji super-
pozycji.

Jak łatwo widać, zachodzą zależności

Twierdzenie 4.12 Dla dowolnego zbioru F funkcji booleowskich

(i) F ⊂ [F ],

(ii) [[F ]] = [F ],

Kraty. Algebry Boole’a i funkcje booleowskie

(iii) jeśli F

⊂ F

, to [F

] ⊂ [F

Definicja 4.15 Zbiór funkcji booleowskich F nazywać będziemy do-
mkniętym funkcyjnie, jeśli

[F ] = F.

Definicja 4.16 Zbiór wszystkich funkcji booleowskich f skończenie ar-
gumentowych, dla których

f (

0, 0, ..., 0) = 0

oznaczać będziemy symbolem T

Symbolem T

oznaczać będziemy skończenie argumentowe funkcje

booleowskie, dla których

f (

1, 1, ..., 1) = 1.

Symbolem S oznaczane będą skończenie argumentowe funkcje bo-

oleowskie spełniające zależności

∗

= f,

tzn. funkcje samodualne.

Symbolem M oznaczać będziemy skończenie argumentowe funkcje

booleowskie monotoniczne, tzn. takie, dla których

f (x

, x

, ..., x

) ¬ f (y

, y

, ..., y

jeśli x

¬ y

, i = 1, 2, ..., n, n ∈

Symbolem L oznaczać będziemy skończenie argumentowe funkcje

booleowskie liniowe, tzn. funkcje otrzymane za pomocą operacji super-
pozycji z funkcji stałych

0, 1 oraz funkcji x 7→ x, x 7→ −x, (x

, x

) 7→

+ x

Wszystkie funkcje ze zbiorów T

, T

, S, M i L są funkcyjnie do-

mknięte, a ponadto zachodzi następujące

Twierdzenie 4.13 Niech dany będzie zbiór F skończenie argumen-
towych funkcji booleowskich. Każda skończenie argumentowa funkcja
booleowska może być przedstawiona jako superpozycja funkcji ze zbioru
F wtedy i tylko wtedy, gdy F nie jest zawarty w żadnym ze zbiorów T

, S, M , L.

Formuły i funkcje booleowskie

Uwaga. Powyższe twierdzenie nazywane jest niekiedy twierdzeniem
o funkcyjnej zupełności, a zbiór F spełniający założenia tego twierdze-
nia nazywany jest funkcyjnie zupełnym.

Przykład. Funkcyjnie zupełnymi są zbiory

(i) {∪, ∩, −},

(ii) {∪, −},

(iii) {→, −},

(iv) {|},

(v) {

0, 1, ∩, (x, y, z) 7→ x + y + z} (por. [12, s. 31]).

Zbiory skończone i metody zliczania

elementów tych zbiorów

5.1

Wprowadzenie do metod kombinato-
rycznych

Kombinatoryka to dział matematyki, który zajmuje się zlicza-

niem liczby elementów zbiorów skończonych. Według ujęcia tradycyj-
nego, mamy do czynienia z losowaniem elementów z pewnego zbioru
n-elementowego P = {x

, x

, ..., x

}, nazywanego niekiedy populacją,

do multizbioru k-elementowego A = {x

, x

, ..., x

}, gdzie x

∈ P ,

j = 1, 2, ..., k, nazywanego próbą.

Odnotujmy, że przez multizbiór rozumiemy „zbiór”, którego ele-

menty mogą się powtarzać. Ścisłej definicji pojęcia multizbioru nie bę-
dziemy tutaj wprowadzać, mimo że nie jest ona skomplikowana, a opie-
ra się na „zwykłym” pojęciu zbioru.

Pytanie, na które odpowiada kombinatoryka, brzmi: ile multizbio-

rów k-elementowych A można otrzymać, nakładając przy tym pewne
założenia na strukturę owych zbiorów? W przypadku zliczania multi-
zbiorów A bierzemy pod uwagę przede wszystkim dwie kwestie:

Zbiory skończone i metody zliczania ...

a) czy elementy multizbioru A powtarzają się (inaczej mówiąc, czy

losowanie elementów ze zbioru P do multizbioru A odbywa się
ze zwracaniem, czy też bez zwracania);

b) czy A jest liniowo uporządkowany, czy nie.

Definicja 5.1 Każdy multizbiór A, który jest liniowo uporządkowany
nazywamy wariacją z n elementów po k elementów.

Multizbiór A, w którym nie jest określona relacja porządku, nazy-

wamy kombinacją z n elementów po k elementów.

Definicja 5.2 Wariacje lub kombinacje otrzymane w wyniku losowa-
nia bezzwrotnego, tzn. takie, których elementy się nie powtarzają, nazy-
wamy wariacjami, lub odpowiednio kombinacjami, bez powtórzeń.
W przeciwnym przypadku, mówimy o wariacjach lub kombinacjach
z powtórzeniami.

Definicja 5.3 Liczbę wariacji bez powtórzeń z n elementów po k ele-
mentów oznaczamy symbolem V

Liczbę wariacji z powtórzeniami z n elementów po k elementów

oznaczamy symbolem V

k
n

Z kolei liczbę kombinacji bez powtórzeń z n elementów po k ele-

mentów oznaczamy symbolem C

Liczbę kombinacji z powtórzeniami z n elementów po k elementów

oznaczamy symbolem

k
n

W ramach kursu matematyki obowiązującego w szkole średniej wy-

kazuje się (my to uczynimy w sposób ścisły w następnym podrozdziale),
że

(n − k)!

k
n

= n

k
n

n + k − 1

Wprowadzenie do metod kombinatorycznych

gdzie przyjmujemy

k!(n − k)!

Ostatnie wyrażenie to tzw. symbol Newtona; w rzeczywistości sym-

bol ten pochodzi od Leonarda Eulera.

Szczególnym rodzajem wariacji są permutacje.

Definicja 5.4 Permutacją n-elementową bez powtórzeń nazywamy wa-
riacje bez powtórzeń z n elementów po n elementów.

Definicja 5.5 Liczbę permutacji n-elementowych bez powtórzeń ozna-
czamy symbolem P

Z powyższych definicji wynika natychmiast, że

= V

= n!

Definicja 5.6 Permutacją n-elementową, w której jeden element wy-
stępuje n

razy, drugi element n

razy, ..., k-ty element n

razy, gdzie

+ n

+ ... + n

¬ n, a pozostałe elementy nie powtarzają się, nazy-

wamy wariacją z powtórzeniami o powyższych własnościach.

Definicja 5.7 Liczbę n-elementowych permutacji zdefiniowanych wy-
żej oznaczamy symbolem

,...,n

Nietrudno wykazać, że

,...,n

!...n

Rzeczywiście, jeśli jeden z elementów powtarza się n

razy, to permu-

tując ze sobą n

egzemplarzy tego samego elementu, otrzymujemy n

permutacji nie różniących się między sobą. Podobnie jest w przypad-
ku pozostałych powtarzających się elementów. Tak więc, aby uzyskać
P

,...,n

, należy P

podzielić przez n

!, n

!, itd.

100

Zbiory skończone i metody zliczania ...

Przykład

(i) Winda, w której znajduje się pięciu pasażerów, może się zatrzy-

mać na 10-u kondygnacjach. Na ile sposobów może wysiąść tych
pięciu pasażerów?
Każdemu z pasażerów możemy przyporządkować numer kondy-
gnacji, na której wysiada. Tworzymy w ten sposób ciągi pię-
cioelementowe, w których występują liczby 1, 2, 3, 4, 5, 6, 7,
8, 9, 10. Ponieważ pasażerowie mogą wysiadać na tych samych
piętrach, więc liczby wyrażające numery kondygnacji mogą się
powtarzać w pięcioelementowym ciągu. Poszukiwana przez nas
liczba sposobów opuszczenia windy przez pasażerów jest równa
liczbie wariacji z powtórzeniami ze zbioru 10-elementowego po 5,
tzn.

L = V

5
10

= 10

(ii) Prostokąt podzielono na mniejsze prostokąty czterema poziomy-

mi i sześcioma pionowymi prostymi poprowadzonymi w równych
odległościach. Iloma sposobami można dojść od jednego wierz-
chołka prostokąta do przeciwległego mu, posuwając się tak, aby
suma odcinków przebytych była równa sumie dwóch przyległych
boków prostokąta?

Rozpatrujemy wszystkie możliwe drogi z A do C, których dłu-
gość jest równa sumie długości dwóch przyległych boków pro-
stokąta (np. AB i AD). Każda droga może być jednoznacznie
reprezentowana przez ciąg kresek poziomych i pionowych. Droga
zaznaczona na rysunku jest reprezentowana przez układ

|| − | − − − || − −−

Wprowadzenie do metod kombinatorycznych

101

Każda droga jest ciągiem 12-u kresek, w tym 5-u pionowych
i 7-u poziomych. Oczywiście, kolejności kresek mogą być dowol-
ne. Mamy zatem do czynienia w tym przypadku z permutacją
z powtórzeniami 12-u elementów, z których jeden powtarza się
5 razy, a drugi 7 razy.

L = P

5,7

12!

5! · 7!

(iii) Na płaszczyźnie danych jest 12 punktów, z których dokładnie 6

leży na jednej prostej; z pozostałych żadne 3 nie leżą na jednej
prostej i żadne 2 z tych pozostałych i żadne z tych 6 nie leżą
na jednej prostej. Należy znaleźć liczbę trójkątów, jakie można
otrzymać, łącząc punkty po 3?
Każdy trójkąt jest wyznaczony przez swoje wierzchołki, przy
czym obojętne jest w jakiej kolejności te wierzchołki są wymie-
niane. Wierzchołki, rzecz jasna, nie mogą się powtarzać.
Trójkąty otrzymujemy na trzy sposoby:

a) łączymy dowolny z 6 punktów leżących na prostej z dowolnie

wybranymi 2 punktami spośród 6 pozostałych punktów,

b) łączymy dowolny z 6 punktów spośród tych, które nie leżą

na prostej, z 2 dowolnie wybranymi ze zbioru 6 punktów
leżących na prostej,

c) spośród 6 punktów nieleżących na prostej wybieramy 3.

Zatem liczba trójkątów jest równa

6 · C

+ 6 · C

+ C

(iv) Ile jest parzystych liczb trzycyfrowych, w których cyfry nie po-

wtarzają się (zakładamy, że zero nie występuje na początku)?
Najpierw bierzemy pod uwagę wszystkie możliwości utworzenia
„liczb” trzycyfrowych parzystych, w których cyfry nie powtarzają
się i zero może występować na początku. „Liczb” takich jest

5 · V

= 5 · 9 · 8 = 360.

Istotnie: cyfr, które zapisane na końcu liczby „sprawiają”, że jest
ona parzysta, mamy pięć: 0, 2, 4, 6, 8.

102

Zbiory skończone i metody zliczania ...

Jeśli wybierzemy jedną z tych pięciu cyfr, pozostanie nam 9 cyfr.
Z tych dziewięciu wybieramy następnie dwie różne cyfry na V

sposobów. Stosujemy wariacje, ponieważ porządek rozmieszcze-
nia cyfr jest ważny.

W następnym kroku musimy od 360 odjąć ilość tych „liczb”,
w których zero występuje na początku. Tych „liczb” jest 4 · V

Ostatecznie liczb spełniających warunki zadania mamy

5 · V

− 4 · V

= 360 − 32 = 328.

(v) W kwiaciarni jest pięć gatunków róż: białe, czerwone, różowe,

żółte i pomarańczowe. Ile bukietów złożonych z pięciu róż można
utworzyć, przyjmując, że w bukiecie kolory kwiatów mogą się
powtarzać?
Bukiet jest zbiorem nieuporządkowanym. Mamy tu zatem do
czynienia z kombinacjami z powtórzeniami złożonymi z pięciu
elementów, które wylosowane zostały w sposób zwrotny ze zbio-
ru pięcioelementowego. Dlatego liczba wszystkich bukietów jest
równa

5
5

5 + 5 − 1

5!4!

6 · 7 · 8 · 9

1 · 2 · 3 · 4

= 2 · 7 · 9 = 126.

5.2

Formalne ujęcie podstaw
kombinatoryki

W poprzednim rozdziale podana została definicja zbioru skoń-

czonego. Zdefiniujemy teraz pojęcie liczebności albo, inaczej mówiąc,
liczby elementów takiego zbioru.

Formalne ujęcie podstaw kombinatoryki

103

Definicja 5.8 Niech A będzie zbiorem skończonym i niepustym oraz
niech

f : A → {1, 2, ..., n}

będzie bijekcją przekształcającą A na zbiór pierwszych n liczb natural-
nych dodatnich. Wtedy liczbę n nazywamy liczebnością zbioru A i pi-
szemy

n = card (A).

Jeśli A = ∅, to przyjmujemy card (A) = 0.

Twierdzenie 5.1 Dla dowolnych rozłącznych zbiorów skończonych A
i B zachodzi równość

card (A ∪ B) = card (A) + card (B).

Dowód. Niech f

: A → {1, 2, ..., n} oraz f

: B → {1, 2, ..., m} będą

bijekcjami. Wtedy bijekcją jest odwzorowanie g : A ∪ B → {1, 2, ...,
n + m}, takie że

g(x) =

(

(x)

dla x ∈ A,

(x) + n dla x ∈ B.

Wniosek. Dla dowolnych, skończonych, parami rozłącznych zbiorów

, A

, ..., A

card (A

∪ A

∪ .... ∪ A

) = card (A

) + card (A

) + ... + card (A

Dowód wniosku jest natychmiastowy. Należy wykorzystać tezę

poprzedniego twierdzenia i indukcję.

Uwaga. Powyższy wniosek nazywany jest niekiedy podstawową albo
fundamentalną zasadą zliczania.

Twierdzenie 5.2 Dla dowolnych skończonych zbiorów A i B zachodzi
równość

card (A × B) = card (A) · card (B).

Dowód. Niech A = {x

, x

, ..., x

} i B = {y

, y

, ..., y

}. Oczywiście

card (A) = n, card (B) = m. W celu wykazania tezy twierdzenia za-
stosujemy indukcję względem m.

104

Zbiory skończone i metody zliczania ...

Dla m = 1

A × B = {(x

, y

), (x

, y

), ..., (x

, y

)}

oraz

card (A × B) = n = n · 1 = card (A) · card (B).

Załóżmy, że teza twierdzenia zachodzi dla pewnego m. Wtedy dla

zbioru m + 1-elementowego B = {y

, y

, ..., y

m+1

} zachodzi równość

A × B = A × B

∪ A × B

gdzie B

= {y

, y

, ..., y

}, B

= {y

m+1

}. Ponieważ zbiory A × B

i A × B

są rozłączne, więc w oparciu o podstawową zasadę zliczania

card (A × B) = card (A × B

) + card (A × B

) = n · m + n =

= n(m + 1) = card (A) · card (B).

Jeśli jeden ze zbiorów A lub B jest pusty, teza twierdzenia także za-
chodzi.

Twierdzenie 5.3 Dla dowolnych zbiorów skończonych A

, A

, ..., A

ma miejsce równość

card (A

× A

× ... × A

) = card (A

) · card (A

) · ... · card (A

Łatwy dowód tego twierdzenia (należy posłużyć się indukcją) po-

zostawiamy Czytelnikowi.

Twierdzenie 5.4 Dla dowolnego skończonego zbioru A

card (P(A)) = 2

card (A)

Dowód. Jeśli A = ∅, to

card (P(A)) = 1 = 2

= 2

card (A)

Jeżeli A = {x

}, to

P(A) = {∅, A},

Formalne ujęcie podstaw kombinatoryki

105

czyli

card (P(A)) = 2 = 2

= 2

card (A)

Załóżmy, że teza twierdzenia zachodzi dla dowolnego zbioru n-ele-

mentowego. Niech A = {x

, x

, ..., x

, x

n+1

}. Wtedy

P(A) = P({x

, x

, ..., x

}) ∪ B,

gdzie B jest rodziną podzbiorów zbioru A, taką że

B ∈ B ⇔ B = A

∪ {x

n+1

} ∧ A

∈ P({x

, x

, ..., x

}).

Obie rodziny zbiorów: P({x

, x

, ..., x

}) i B mają tyle samo elemen-

tów, a mianowicie 2

. Ostatecznie

card (P(A)) = 2

+ 2

= 2

n+1

Twierdzenie zostało udowodnione.

W dalszej kolejności podamy kilka twierdzeń odnoszących się do

zbiorów funkcji (por. [9, s. 40n]). Przypomnijmy, że w jednym z wcze-
śniejszych

rozdziałów

wprowadziliśmy

oznaczenia

ini(B

sur(B

) oraz bij(B

) dla zbiorów wszystkich funkcji odwzorowują-

cych A w B, wszystkich iniekcji ze zbioru A w zbiór B, wszystkich
suriekcji ze zbioru A na B oraz wszystkich bijekcji ze zbioru A na
zbiór B. W tym podrozdziale obliczymy card (B

), card (ini(B

)),

card (bij(B

)) dla zbiorów skończonych A oraz B. Rachunki dotyczące

card (sur(B

)) są bardziej skomplikowane i zostaną wykonane w na-

stępnym podrozdziale.

Twierdzenie 5.5 Dla dowolnych niepustych i skończonych zbiorów A
i B zachodzi równość

card (B

) = card (B)

card (A)

Dowód. Wykorzystamy indukcję względem liczby elementów zbioru
A. Niech A = {x

} oraz B = {y

, y

, ..., y

}. Wtedy istnieje dokładnie

m funkcji odwzorowujących A w B, czyli równość zawarta w tezie
twierdzenia jest spełniona.

106

Zbiory skończone i metody zliczania ...

Załóżmy, że równość ta zachodzi dla dowolnego n-elementowego

zbioru i przyjmijmy, że A = {x

, x

, ..., x

n+1

}. Wtedy

A = A

∪ {x

n+1

gdzie A

= {x

, x

, ..., x

Każdej funkcji należącej do B

odpowiada m funkcji odwzorowu-

jących {x

n+1

} w B. Zatem

card (B

) = card (B

) · card (B) = card (B)

card (A

)

· card (B) =

= card (B)

card (A

)+1

= card (B)

card (A)

Twierdzenie zostało wykazane.

Twierdzenie 5.6 Niech A i B będą niepustymi zbiorami skończony-
mi, takimi że card (A) ¬ card (B). Wtedy

card (ini(B

)) =

card (B)!

(card (B) − card (A))!

Dowód. Zastosujemy indukcję względem liczby elementów zbioru B.
Jeżeli card (B) = 1, to card (A) = 1 i równość zawarta w tezie twier-
dzenia zachodzi.

Załóżmy, że jest ona prawdziwa dla dowolnego n-elementowego

zbioru B i dla dowolnego zbioru A o liczbie elementów nie większej
niż n.

Przyjmijmy, że B = {y

, y

, ..., y

n+1

}. Załóżmy też, że A = {x

, x

..., x

}, gdzie k ¬ n + 1. W takim przypadku

ini(B

) =

n+1

[

i=1

gdzie

= {f ∈ ini(B

) : f (x

) = y

i = 1, 2, ..., k + 1.

Oczywiście

∩ C

= ∅,

jeśli

i 6= j.

Formalne ujęcie podstaw kombinatoryki

107

W przypadku, gdy A = {x

} zachodzi równość

card

ini(B

)

= n + 1 =

(n + 1)!

card (B)!

(card (B) − card (A))!

Przyjmijmy, że card (A) 2.

Zauważmy, że każdy ze zbiorów C

zawiera jako swoje elemen-

ty funkcje, którym w sposób wzajemnie jednoznaczny odpowiadają
wszystkie iniekcje ze zbioru {x

, x

, ..., x

k−1

} w zbiór {y

, y

, ..., y

n+1

} \

}. Takich iniekcji jest

(n − k + 1)!

a zatem, korzystając z podstawowej zasady zliczania, otrzymujemy

card (ini(B

)) = (n + 1)

(n − k + 1)!

card (B)!

(card (B) − card (A))!

co kończy dowód twierdzenia.

Ostatnie dwa twierdzenia są przydatne do zliczania wariacji z po-

wtórzeniami i wariacji bez powtórzeń. Zauważmy bowiem, że każdy
wybór uporządkowany z populacji P dla próby A można zinterpreto-
wać jako funkcję

f : {1, 2, ..., k} → {x

, x

, ..., x

gdzie {x

, x

, ..., x

} = P , natomiast A = {f (i) : i = 1, 2, ..., k}.

Dlatego też liczbę wariacji z powtórzeniami ze zbioru n-elementowego

(tutaj: P ) po k elementów wyznaczamy poprzez zliczenie wszystkich
funkcji f określonych powyższą zależnością. Wzór

k
n

= n

jest więc konsekwencją zależności

card (B

) = card (B)

card (A)

108

Zbiory skończone i metody zliczania ...

Podobnie, rozważając wariacje bez powtórzeń, odwołujemy się do

iniekcji ze zbioru {1, 2, ..., k} w zbiór P (zakładamy, że k ¬ n. A zatem
wzór

(n − k)!

wynika z zależności

card

ini(B

)

card (B)!

(card (B) − card (A))!

Jak widać, pojęcie wariacji w prosty i elegancki sposób można spro-

wadzić do pojęcia funkcji o odpowiednich własnościach. W jaki sposób
poradzić sobie z pojęciem kombinacji? Należy „utożsamić” ze sobą
funkcje przyjmujące te same wartości (wraz z ewentualnymi krotno-
ściami), jednak niekoniecznie w tej samej „kolejności”. Bardziej ściśle
można to ująć w poniższy sposób.

W zbiorze wszystkich funkcji odwzorowujących {1, 2, ..., k} w {x

, ..., x

} wprowadzamy relację ε następująco

f εg ⇔ f (i) = g(σ(i))

dla i = 1, 2, ..., k oraz pewnej permutacji σ : {1, 2, ..., k} → {1, 2, ..., k}
(por. [9, s. 52]).

Twierdzenie 5.7 Relacja ε jest relacją równoważności.

Dowód. Relacja ta jest zwrotna, bowiem dla permutacji ι(i) = i,
i = 1, 2, ..., k, zachodzi równość

f (i) = f (ι(i)).

Relacja ta jest symetryczna, gdyż jeśli

f (i) = g(σ(i)),

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

g(i) = f (σ

−1

(i)),

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

Relacja ε jest przechodnia, bo jeśli

f (i) = g(σ(i))

oraz

g(i) = h(τ (i)),

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

Formalne ujęcie podstaw kombinatoryki

109

f (i) = h(τ (σ(i))),

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

Tak więc, zliczając - dla ustalenia uwagi - kombinacje bez powtó-

rzeń, zliczamy faktycznie klasy abstrakcji relacji ε, czyli elementy zbio-
ru ilorazowego ini(P

{1,2,...,k}

)/ε lub, jeśli zastosujemy uprzednią sym-

bolikę, ini(B

)/ε.

Twierdzenie 5.8 Niech dany będzie zbiór funkcji B

, gdzie card (A)

= card (B). Wtedy zbiór ini(B

)/ε ma

card (B)

card (A)!(card (B) − card (A))!

Dowód. Dowód twierdzenia jest natychmiastowy, a wynika stąd, iż
każda klasa abstrakcji ma card (A)! elementów.

Z powyższego twierdzenia otrzymujemy znany wzór na liczbę kom-

binacji bez powtórzeń

k!(n − k)!

gdzie n jest liczebnością populacji, a k jest liczebnością próby.

Wniosek. Niech dany będzie dowolny zbiór n-elementowy. Zbiór ten
ma

k!(n − k)!

podzbiorów k-elementowych, gdzie k ¬ n.

Powyższy wynik ma pewne ważne zastosowanie.

Definicja 5.9 Załóżmy, że A i B są niepustymi zbiorami uporządko-
wanymi liniowo. Funkcję f : A → B nazywamy rosnącą (malejącą),
jeśli

∈A

≺ x

⇒ f (x

) ≺ f (x

110

Zbiory skończone i metody zliczania ...





∈A

≺ x

⇒ f (x

)  f (x

)





gdzie tym samym symbolem oznaczone zostały relacje liniowego po-
rządku w zbiorach A i B.

Podobnie, f nazywamy nierosnącą (niemalejącą), jeśli

∈A

≺ x

⇒ f (x

)  f (x





∈A

≺ x

⇒ f (x

)  f (x

)





Jeśli funkcja f jest rosnąca lub malejąca, ewentualnie nierosnąca

lub niemalejąca, nazywamy ją monotoniczną.

Definicja 5.10 Niech A oraz B będą skończonymi zbiorami niepusty-
mi. Wtedy

(i) symbolem inc(B

) oznaczmy zbiór wszystkich funkcji rosnących

z A do B,

(ii) symbolem dec(B

) oznaczamy zbiór wszystkich funkcji maleją-

cych z A do B,

(iii) symbolem ninc(B

) oznaczamy zbiór wszystkich funkcji niero-

snących z A do B,

(iv) symbolem ndec(B

) oznaczamy zbiór wszystkich funkcji niema-

lejących z A do B,

(v) symbolem mon(B

) oznaczamy zbiór wszystkich funkcji monoto-

nicznych odwzorowujących A w B.

Twierdzenie 5.9 Liczba funkcji rosnących, odwzorowujących niepu-
sty skończony liniowo uporządkowany zbiór A w niepusty skończony
liniowo uporządkowany zbiór B, jest równa

card (inc(B

)) =

card (B)!

card (A)!(card (B) − card (A))!

Współczynniki dwumianowe i wielomianowe

111

Dowód. Powyższa równość wynika stąd, że funkcja rosnąca jest jedno-
znacznie określona poprzez wybór card (A)-elementowych podzbiorów
zbioru card (B)-elementowego.

Obliczenie card (dec(B

)) przebiega analogicznie.

Nieco trudniej obliczyć card (B

/ε). Odpowiedni rezultat zawarty

jest w poniższym twierdzeniu, które podajemy bez dowodu.

Twierdzenie 5.10 Dla dowolnych skończonych zbiorów niepustych A
i B oraz dla relacji ε określonej jak wyżej, zachodzi równość

card (B

/ε) =

(card (B) + card (A) − 1)!

card (A)!(card (B) − 1)!

Powyższa zależność pozwala na otrzymanie wzoru na liczbę kom-

binacji z powtórzeniami z n elementów po k elementów

k
n

(n + k − 1)!

k!(n − 1)!

Podobnie jak kombinacje bez powtórzeń służą do zliczania funkcji

rosnących, kombinacje z powtórzeniami są wykorzystywane do zlicza-
nia funkcji niemalejących.

Twierdzenie 5.11 Jeśli A i B są niepustymi zbiorami skończonymi
liniowo uporządkowanymi, to

card (ndec(B

)) =

(card (B) + card (A) − 1)!

card (A)!(card (B) − 1)!

Analogicznie obliczamy card (ninc(B

)).

5.3

Współczynniki dwumianowe
i wielomianowe

Zacznijmy od definicji

Definicja 5.11 Niech k, n ∈

N. Współczynnikiem dwumianowym na-

zywamy liczbę

112

Zbiory skończone i metody zliczania ...

k!(n − k)!

gdy

n k,

oraz

= 0,

gdy

n < k.

Uwaga. Z powyższego określenia wynika, że C

n
k

oraz

k
n

n+k−1

Twierdzenie 5.12 Dla dowolnych n, k ∈

N, k ¬ n, zachodzą równo-

ści

(i)

n
k

n−k

(ii)

n
k

k+1

n+1
k+1

Prosty dowód pozostawiamy Czytelnikowi.

Twierdzenie 5.13 Dla dowolnych x, y ∈

R i n ∈ N

(x + y)

n−1

y + ... +

Dowód Stosujemy indukcję względem n. Dla n = 1

(x + y)

x +

a zatem równość zachodzi. Załóżmy, że jest ona spełniona dla n ∈

Wtedy

(x + y)

n+1

= (x + y)

(x + y) =

n−1

y + ... +

n
n

·(x + y) =

n+1

y + ... +

n
n

y +

n−1

+ ... +

n
n

n+1

= x

n+1

y +

n−1

+... +

n
k

k−1

n−k+1

+ ... + y

n+1

y + ... +

n+1

n+1−k

+... +

n+1
n+1

n+1

Współczynniki dwumianowe i wielomianowe

113

Wykorzystaliśmy tu zależność

k − 1

n + 1

będącą konsekwencją punktu (ii) poprzedniego twierdzenia.

W ten sposób dowód jest zakończony.

Wzór zawarty w tezie twierdzenia nazywany jest wzorem dwumia-

nowym Newtona.

Wniosek. Dla n ∈

N zachodzi równość

+ ... +

= 2

Dowód. Powyższa równość jest konsekwencją poprzedniego twierdze-
nia z x = y = 1.

Uwaga. Ostatnią zależność kombinatoryczną można zinterpretować
następująco: liczby

n
k

są równe liczbom podzbiorów k-elementowych

zbioru n-elementowego. Oznacza to, że dowolny zbiór n-elementowy
ma 2

podzbiorów. W związku z tym, staje się bardziej zrozumiałe

użycie nazwy „zbiór potęgowy” dla zbioru złożonego ze wszystkich
podzbiorów danego zbioru.

Wniosek. Dla n ∈

N ma miejsce równość

−

+ ... + (−1)

= 0.

Dowód. Powyższa równość wynika z ostatniego twierdzenia, w którym
należy przyjąć x = 1, y = −1.

Obok powyższych równości można dowieść także, stosując różno-

rodne metody kombinatoryczne i analityczne, wiele innych tożsamości.

114

Zbiory skończone i metody zliczania ...

Przykład

(i) Wykazać równość (por. [5, s. 28-29])

n + l

k − 1

+ ... +

k − n

gdzie n ¬ k ¬ l.
Wykorzystamy równości dwumianowe

(1 + x)

x + ... +

(1 + x)

x + ... +

Mamy

(1 + x)

n+l

x + ... +

n
n

x + +... +

l
l

Współczynniki przy x

po lewej i prawej stronie powyższej rów-

ności są sobie równe. W ten sposób uzyskujemy żądaną równość.

(ii) Wykazać, że

n−1

m−1

n−2

m−2

n−m

m−n

(x + y)

gdzie n, m ∈

N, n m.

W celu dowiedzenia powyższej równości zauważmy, że

n−i

m−i

i!(n−i)!

(n−i)!

(m−i)!(n−m)!

m!(n−m)!

i!(m−i)!

i = 0, 1, ..., m.

W związku z tym lewa strona równości, którą należy wykazać,
jest równa

! "

m−1

+ ... +

(x + y)

Współczynniki dwumianowe i wielomianowe

115

Przy okazji zauważmy, że dowodzona równość może być zapisana
z użyciem symbolu

w bardziej zwartej postaci

i=0

n − i

m − i

m−i

(x + y)

(iii) Dowiedziemy, iż

i−1

i = n · 2

n−1

Skorzystamy ze wzoru dwumianowego Newtona, zapisanego
w postaci równości

i=0

n−i

= (x + y)

Różniczkując powyższą tożsamość względem x, otrzymujemy

i=1

i−1

n−i

= n(x + y)

n−1

Podstawiając x = y = 1, otrzymujemy żądaną równość.

Pożytecznym uogólnieniem współczynników dwumianowych są

tzw. współczynniki wielomianowe.

Definicja 5.12 Dla dowolnych n, i

, i

, ..., i

∈

N, takich że k 2 oraz

+...+i

= n, współczynnik wielomianowy definiujemy następująco

...i

!...i

Uwaga. Z powyższej definicji wynika, że

...i

= P

,...,i

Innymi słowy, współczynnik wielomianowy jest równy liczbie uporząd-
kowanych wyborów mających tę własność, że jeden element występuje
i

razy, drugi i

razy, ..., k-ty i

razy.

116

Zbiory skończone i metody zliczania ...

Z drugiej strony

...i

n − i

...

n − i

− i

− ... − i

k−1

a zatem współczynnik wielomianowy jest też równy liczbie takich wy-
borów, iż i

elementów zostaje zaliczonych do pierwszego zbioru, i

drugiego zbioru, itd.

Twierdzenie 5.14 Zachodzi równość

+ x

+ ... + x

)

+...+i

...i

...x

gdzie n ∈

Dowód twierdzenia jest podobny do dowodu wzoru Newtna.

Twierdzenie 5.15 Dla n ∈

N oraz i

, i

, ..., i

, takich że i

+ i

+ ... +

= n, zachodzi równość

...i

n − 1

...i

− 1...i

Powyższa równość jest uogólnieniem równości

n − 1

i − 1

n − 1

Dowód twierdzenia jest nieskomplikowany, lecz rachunkowy; z tego

względu pomijamy go.

5.4

Zasada włączeń i wyłączeń

Podstawową rolę w kombinatoryce odgrywa tzw. zasada włączeń

i wyłączeń. Pozwala ona w szczególnym przypadku na obliczenie
card (A ∪ B), jeśli znamy card (A), card (B) i card (A ∩ B). Miano-
wicie

card (A ∪ B) = card (A) + card (B) − card (A ∩ B).

Zasada włączeń i wyłączeń

117

W przypadku, gdy dane są trzy zbiory skończone A, B i C, zasada

ta przyjmuje postać równości

card (A ∪ B ∪ C) = card (A) + card (B) + card (C)−

−card (A ∩ B) − card (B ∩ C) − card (A ∩ C)+

+card (A ∩ B ∩ C).

W ogólności zasada włączeń i wyłączeń przedstawia się następują-

co:

Twierdzenie 5.16 Niech dane będą zbiory skończone A

, A

, ..., A

Wtedy

card

i=1

card (A

) −

1¬i<j¬n

card (A

∩ A

1¬i<j<k¬n

card (A

∩ A

+... + (−1)

n+1

card (A

∩ A

∩ ... ∩ A

)

118

Zbiory skończone i metody zliczania ...

Dowód. Zastosujemy indukcję względem n. Dla n = 2

card (A

∪ A

) = card (A

\ (A

∩ A

)) + card (A

\ (A

∩ A

))+

+card (A

∩ A

) = card (A

) − card (A

∩ A

+card (A

) − card (A

∩ A

) + card (A

∩ A

) =

card (A

) + card (A

) − card (A

∩ A

Przy przekształceniach wykorzystaliśmy podstawową zasadę zlicza-

nia, bo zbiory A

\ (A

∩ A

), A

\ (A

∩ A

) oraz A

∩ A

są parami

rozłączne. Ponadto A

∩ A

⊂ A

i A

∩ A

⊂ A

, więc

card (A

\ (A

∩ A

)) = card (A

) − card (A

∩ A

i = 1, 2.

Załóżmy, że teza twierdzenia zachodzi dla n ∈

N. Wtedy

card

n+1

i=1

= card

i=1

+ card (A

n+1

) − card

n+1

∩

i=1

card (A

) −

1¬i<j¬n

card (A

∩ A

+... + (−1)

n+1

card (A

∩ A

∩ ... ∩ A

+card (A

n+1

) −

i=1

card (A

∩ A

n+1

)−

−

1¬i<j¬n

card (A

∩ A

n+1

) + ...+

+(−1)

n+1

card (A

∩ A

∩ ... ∩ A

n+1

)

n+1

i=1

card (A

) −

1¬i<j¬n+1

card (A

∩ A

) + ...+

+(−1)

n+1

card (A

∩ A

∩ ... ∩ A

n+1

Dowód twierdzenia jest zakończony.

Przykład. W pewnej klasie jest 35 uczniów. Dziesięciu z nich uczy
się języka angielskiego, dwudziestu - języka niemieckiego, piętnastu -

Zasada włączeń i wyłączeń

119

języka francuskiego, ośmiu uczy się angielskiego i niemieckiego, dzie-
więciu - angielskiego i francuskiego, a dziewiętnastu uczy się wszystkich
tych trzech języków. Wiedząc, że każdy z uczniów uczy się co najmniej
jednego języka, należy obliczyć ilu uczniów uczy się niemieckiego i fran-
cuskiego.

W celu rozwiązania zadania wprowadzimy oznaczenia:

A - zbiór uczniów uczących się języka angielskiego,

N - zbiór uczniów uczących się języka niemieckiego,

F - zbiór uczniów uczących się języka francuskiego.

Wtedy card (A)

10, card (N )

20, card (F )

15,

card (A ∩ N ) = 8, card (A ∩ F ) = 9, card (A ∩ N ∩ F ) = 19, a także
card (A ∪ N ∪ F ) = 35.

Zasada włączeń i wyłączeń prowadzi do zależności

card (A ∩ N ∩ F ) = card (A) + card (N ) + card (F )−

−card (A ∩ N ) − card (A ∩ F )−

−card (N ∩ F ) + card (A ∩ N ∩ F ),

czyli

35 = 10 + 20 + 15 − 8 − 9 − card (N ∩ F ) + 19.

Zatem

card (N ∩ F ) = 12.

Z zasady włączeń i wyłączeń wynika poniższe twierdzenie

Twierdzenie 5.17 Niech A

, A

, ..., A

, B będą zbiorami skończony-

mi. Jeżeli A

⊂ B, i = 1, 2, ..., n, to

card

i=1

(B \ A

)

= card (B) −

i=1

card (A

) +

1¬i<j¬n

card (A

∩

∩A

) + ... + (−1)

card (A

∩ A

∩ ... ∩ A

120

Zbiory skończone i metody zliczania ...

W jaki sposób korzysta się z tego twierdzenia, pokazuje następu-

jący przykład.

Przykład. Rozważmy, ile spośród pierwszych 2000 liczb naturalnych
dodatnich nie jest podzielnych ani przez 5, ani przez 7, ani przez 11,
ani też przez 13.

Najpierw wprowadźmy oznaczenia:

B = {1, 2, ..., 2000}

- zbiór liczb należących do B, które nie są podzielne przez 5,

- zbiór liczb należących do B, które nie są podzielne przez 7,

- zbiór liczb należących do B, które nie są podzielne przez 11,

- zbiór liczb należących do B, które nie są podzielne przez 13.

Zauważmy, że

card (A

) = Ent

2000

= 400,

card (A

) = Ent

2000

= 285,

card (A

) = Ent

2000

= 181,

card (A

) = Ent

2000

= 153,

card (A

∩ A

) = Ent

2000

= 57,

card (A

∩ A

) = Ent

2000

= 36,

card (A

∩ A

) = Ent

2000

= 30,

card (A

∩ A

) = Ent

2000

= 25,

card (A

∩ A

) = Ent

2000

= 21,

card (A

∩ A

) = Ent

2000

143

= 13.

Podobnie

card (A

∩ A

) = 5,

card (A

∩ A

) = 4,

card (A

∩ A

) = 2,

card (A

∩ A

) = 1,

card (A

∩ A

) = 0.

Zasada szufladkowa Dirichleta

121

Zbiorem liczb, które nie są podzielne przez 5, 7, 11, 13 jest zbiór

i=1

(B \ A

). Zatem

card

i=1

(B \ A

)

= card (B) −

i=1

card (A

1¬i<j¬4

card (A

∩ A

)−

−

1¬i<j<k¬4

card (A

∩ A

+card (A

∩ A

czyli

card

i=1

(B \ A

)

= 2000 − (400 + 285 + 181 + 153) + (57 + 36+

+30 + 25 + 21 + 13) − (5 + 4 + 2 + 1) + 0 =

= 2000 − 1019 + 182 − 12 = 1151.

Z zasady włączeń i wyłączeń będziemy korzystać w następnym roz-

dziale przy rozwiązywaniu bardziej skomplikowanych problemów kom-
binatorycznych.

5.5

Zasada szufladkowa Dirichleta

Zasada Dirichleta w najbardziej znanej postaci stwierdza, że:

jeżeli w n szufladach rozmieszcza się więcej niż n przedmio-
tów, to istnieje co najmniej jedna szuflada, w której znaj-
duje się więcej niż jeden przedmiot.

Zasadzie tej można nadać bardziej ścisłą postać, formułując twier-

dzenie:

Twierdzenie 5.18 Niech A będzie zbiorem skończonym. Jeżeli zbiory
A

, i = 1, 2, ..., k, stanowią podział A, przy czym card (A) > k, to

istnieje i

∈ {1, 2, ..., k}, takie że card (A

) > 1.

122

Zbiory skończone i metody zliczania ...

Dowód twierdzenia, jako oczywisty, pomijamy. Ostatni wynik moż-

na uogólnić; zachodzi mianowicie

Twierdzenie 5.19 Jeśli A jest zbiorem skończonym, a zbiory A

i = 1, 2, ..., k, stanowią jego podział, taki że dla pewnej liczby p ∈

card (A) > p · k,

to istnieje i

∈ {1, 2, ..., k} o tej własności, że

card (A

) > p.

Dowód. Gdyby card (A

) ¬ p dla dowolnego i = 1, 2, ..., k, to otrzy-

mujemy card (A) ¬ p · k, co jest sprzeczne z założeniem.

Podziały zbioru są niejednokrotnie generowane przez funkcje

(por. [15, s. 315]). W związku z tym ma miejsce następujący wnio-
sek.

Wniosek. Załóżmy, że dana jest funkcja f : A → B, gdzie A i B są
zbiorami skończonymi, takimi że

card (A) > p · card (B),

gdzie p ∈

. Wtedy istnieje y ∈ B o tej własności, że

card (f

−1

({y})) > p.

Dowód. Teza wynika z poprzedniego twierdzenia i faktu, iż zbiory
f

−1

({y

}) stanowią podział zbioru A dla pewnego zbioru y

, y

, ..., y

k ¬ card (B), elementów B.

Przykład

(i) Zauważmy, że wśród dowolnych stu kolejnych liczb całkowitych

możemy wybrać kilka (w szczególnym przypadku jedną) kolej-
nych liczb w taki sposób, że ich suma dzieli się przez 5000.

Zasada szufladkowa Dirichleta

123

Niech rozważanymi liczbami będą x

, x

, ..., x

100

. Istnieje 100 jed-

noskładnikowych sum tych elementów, 99 dwuskładnikowych
x

+ x

, x

+ x

, ..., x

+ x

100

, 98 trzyskładnikowych x

+ x

, x

+ x

, ..., x

+ x

100

, itd; na końcu bierzemy pod

uwagę jedną sumę złożoną ze 100 składników x

+ x

+ ... + x

100

W rezultacie, wszystkich sum jest

1 + 2 + ... + 99 + 100 =

· 100 · 101 = 5050.

Ponieważ przy dzieleniu przez 5000 można otrzymać wiele rów-
nych reszt, więc z powyższych rachunków wynika, że przynaj-
mniej jedna z sum dzieli się przez tę liczbę.

(ii) Wykażemy, że gdy dane jest 10 dowolnych dwucyfrowych liczb

naturalnych, można spośród nich wybrać co najmniej dwa pod-
zbiory rozłączne, takie że sumy ich elementów są sobie równe.
Istotnie, można utworzyć ogółem 2

− 1 = 1023 podzbiorów

niepustych zawierających liczby z danego zbioru. Zarazem naj-
mniejsza z sum wynosi 10, a największa jest równa 90 + 91 +
92 + ... + 99 < 1000. Stąd wynika, że istnieją przynajmniej dwa
podzbiory o tej samej sumie elementów. Jeżeli zbiory te nie są
rozłączne, należy z nich usunąć elementy wspólne; sumy pozo-
staną sobie równe.

(iii) Wykażemy, że dla dowolnej liczby n ∈

istnieje liczba zapisana

(w systemie dziesiętnym) przy użyciu jedynie cyfr 0 i 1, która jest
podzielna przez n.
Liczb, które mogą być zapisane tylko przy użyciu cyfry 1 jest do-
wolnie wiele. Wśród nich są: 1, 11, 111, ..., 111...1 = 10

+ 10

n−1

... + 1. Tych ostatnich liczb jest n + 1, a zatem, zgodnie z zasadą
Dirichleta, są wśród nich co najmniej dwie liczby dające tę samą
resztę przy dzieleniu przez n. Jeśli nie jest to reszta równa zero,
to różnica tych liczb, zapisana jedynie przy użyciu cyfr 0 i 1, jest
podzielna przez n.

(iv) Niech dany będzie sześciokąt. Łączymy ze sobą wszystkie jego

wierzchołki, używając jedynie dwóch kolorów: niebieskiego i czer-
wonego do narysowania odpowiednich odcinków. Można wyka-
zać, że wśród narysowanych trójkątów przynajmniej jeden ma
wszystkie boki tego samego koloru.

124

Zbiory skończone i metody zliczania ...

Ustalmy jeden z wierzchołków, powiedzmy x

. Wychodzi z nie-

go 5 krawędzi, z których co najmniej trzy muszą być jednego
koloru. Niech będą to na rysunku odcinki x

, x

oraz x

Jeśli tym samym kolorem co wymienione odcinki, narysujemy
jeden z odcinków: x

, x

lub x

, to uzyskamy trójkąt o bo-

kach w jednym kolorze (będzie to jeden z trójkątów: 4x

, 4x

W przeciwnym przypadku wierzchołki x

, x

i x

zostaną połą-

czone drugim kolorem, a więc otrzymamy trójkąt 4x

o bo-

kach tego samego koloru.

Podziały i permutacje.

Liczby Stirlinga i Bella

6.1

Liczenie podziałów

W tym podrozdziale powrócimy do pojęcia podziału zbioru na

podzbiory.

Definicja 6.1 Niech dany będzie skończony i niepusty zbiór A. Jego
podziałem nazywamy rodzinę zbiorów A

, A

, ..., A

, k ¬ card (A), nie-

pustych, parami rozłącznych i takich, że

[

i=1

= A.

Rozwiązując pewnego typu zadania, obliczamy liczbę podziałów

tego zbioru na podzbiory o określonych liczebnościach.

Przykład. Rozwiążmy dwa podobne zadania.

(i) Dziewięciu pasażerów wsiada do tramwaju złożonego z trzech

wagonów. Na ile sposobów mogą to uczynić, jeśli do pierwszego

126

Podziały i permutacje. Liczby Stirlinga i Bella

wagonu ma wsiąść dwóch pasażerów, do drugiego - trzech, a do
trzeciego - czterech pasażerów.
W tym przypadku żądamy, aby to do pierwszego wagonu, a nie
drugiego czy trzeciego, wsiadło dwóch pasażerów; podobnie jest
w przypadku następnych wagonów. Mamy tu więc do czynienia
z podziałami na trzy zbiory o określonej liczebności. Ich liczba
jest równa

2,3,4

2! · 3! · 4!

(ii) Zmodyfikujemy poprzednie zadanie. Tym razem chcemy, aby do

jednego z wagonów (niekoniecznie pierwszego) wsiadło dwóch pa-
sażerów, do innego - trzech, a do pozostałych wagonów - czterech.
W tym przypadku rozwiązaniem jest liczba

· P

2,3,4

3! · 9!

2! · 3! · 4!

Definicja 6.2 Symbolem P art

k;i

,...,i

(A) oznaczać będziemy liczbę

podziałów zbioru A, card (A) k, na k podzbiorów o liczebnościach
i

, ..., i

Stwierdzenie. Zachodzi równość

P art

k;i

,...,i

(A) =

card (A)!

!...i

Przedstawimy teraz niezwykle ważny wynik, mający znaczenie sa-

moistne, ale też przydatny w dalszych rozważaniach dotyczących liczby
podziałów.

Twierdzenie 6.1 Niech A i B będą zbiorami skończonymi i niepusty-
mi. Wtedy

card

sur(B

)

card (B)

i=0

(−1)

card (B)

(card (B) − i)

card (A)

Dowód twierdzenia jest dość żmudny. Można go znaleźć np. w książ-

ce Flachsmeyera [9, s. 80-81].

Z powyższego twierdzenia wynika ważny wniosek. Najpierw poda-

my jednak następującą definicję

Liczenie podziałów

127

Definicja 6.3 Symbolem P art

(A) oznaczać będziemy liczbę podzia-

łów zbioru A, card (A) ¬ k, na k podzbiorów niepustych.

Wniosek. Dla zbioru skończonego i niepustego zachodzi równość

P art

(A) =

i=0

(−1)

(k − 1)

card (A)

Przykład. Znajdziemy wszystkie podziały nieuporządkowane zbioru
czteroelementowego A = {a, b, c, d}.

Istnieje tylko jeden podział złożony z jednego zbioru

{{a, b, c, d}}.

Podziałów złożonych z dwóch zbiorów jest siedem. Są to

{{a, b, c}, {d}}, {{a, c, d}, {b}}, {{b, c, d}, {a}}, {{a, b, d}, {c}}

oraz

{{a, b}, {c, d}}, {{a, c}, {b, d}}, {{a, d}, {b, c}}.

Podziałów złożonych z trzech zbiorów jest sześć

{{a, b}, {c}, {d}}, {{a, c}, {b}, {d}}, {{a, d}, {b}, {c}},

{{b, c}, {a}, {d}}, {{b, d}, {a}, {c}}, {{c, d}, {a}, {b}}.

Mamy ponadto jeden podział na cztery zbiory

{{a}, {b}, {c}, {d}}.

Zauważmy, że otrzymane wyniki są zgodne z ostatnim wnioskiem.

Rzeczywiście,w tym przypadku card (A) = 4 i odpowiednie liczby wy-
znaczające ilość podziałów tego zbioru na jeden, dwa i trzy podzbiory
są równe

(−1)

1
0

(1 − 0)

+ (−1)

1
1

(1 − 1)

= 1,

(−1)

2
0

(2 − 0)

+ (−1)

2
1

(2 − 1)

+ (−1)

2
2

(2 − 2)

1
2

(16 − 2) = 7,

(−1)

3
0

(3 − 0)

+ (−1)

3
1

(3 − 1)

+ (−1)

3
2

(3 − 2)

+ 0

1
6

(81 − 3 · 16 + 3) = 6.

128

Podziały i permutacje. Liczby Stirlinga i Bella

Wyznaczenie ostatniej liczby - odpowiadającej podziałowi zbioru A na
cztery podzbiory, pozostawiamy Czytelnikowi.

6.2

Rozkłady liczb

Rozważmy najpierw następujący problem.

Przykład. Ile rozwiązań w liczbach naturalnych dodatnich ma rów-
nanie

+ x

= 6,

jeśli odróżniamy od siebie wszystkie sumy różniące się kolejnością skład-
ników?

Najpierw wypiszemy wszystkie rozwiązania.

1 + 1 + 4 = 6, 1 + 2 + 3 = 6, 3 + 2 + 1 = 6, 2 + 3 + 1 = 6,
1 + 4 + 1 = 6, 1 + 3 + 2 = 6, 2 + 2 + 2 = 6, 2 + 1 + 3 = 6,
4 + 1 + 1 = 6, 3 + 1 + 2 = 6.

Jak widać, jest ich dziesięć. Czy jednak na pewno nie zapomnieliśmy
o jakimś rozwiązaniu? Okazuje się, że nie, a upewnia nas o tym nastę-
pujące rozumowanie (por. [5, s. 48]).

Zauważmy, że każdemu z powyższych rozwiązań odpowiada wybór

dwóch znaków + w poniższej sumie

1 + 1 + 1 + 1 + 1 + 1 = 6.

Znaków tych jest pięć, a więc liczba możliwych wyników jest równa

= 10.

Twierdzenie 6.2 Liczba rozwiązań równania

+ x

+ ... + x

= n,

k ¬ n,

będących liczbami naturalnymi dodatnimi, wynosi

n − 1

k − 1

jeśli za różne uznaje się rozwiązania odpowiadające różnej kolejności
składników.

Rozkłady liczb

129

Dowód. Można przeprowadzić dowód tego twierdzenia, opierając się
na ujęciu mnogościowym pojęć kombinatorycznych, stosując przy tym
zasadę indukcji zupełnej względem n. Znacznie łatwiej jest jednak prze-
prowadzić dowód kombinatoryczny przypominający rozumowanie z po-
przedniego przykładu.

Mianowicie, liczba rozwiązań równania jest równa liczbie sposobów

wyboru k − 1 znaków + w poniższej równości

1 + 1 + ... + 1 = n.

W wielu przypadkach interesują nas rozkłady liczb dopuszczające

rozwiązania zerowe.

Przykład. Ile rozwiązań w liczbach naturalnych, przy założeniu, że
odróżniamy rozwiązania różniące się kolejnością składników, ma rów-
nanie

+ x

= 8 ?

Aby rozwiązać ten problem, wypiszemy osiem jedynek, a następnie,

w dowolny sposób, dopiszemy 4 − 1 = 3 znaki +.

W ten sposób można otrzymać na przykład napisy

111 + 1 + 11 + 11

lub

11 + + 111 + 111,

lub też

+ + + 11111111.

Napisy te odpowiadają rozwiązaniom

3 + 1 + 2 + 2 = 8,

2 + 0 + 3 + 3 = 8

oraz

0 + 0 + 0 + 8 = 8.

130

Podziały i permutacje. Liczby Stirlinga i Bella

Ostatecznie, możliwych wyborów, i zatem rozwiązań, jest

8,3

8+3

11!

8!3!

Powyższy przykład jest szczególnym przypadkiem problemu, który

opisuje następujące twierdzenie

Twierdzenie 6.3 Dowolne równanie

+ x

+ ... + x

= n,

k ¬ n,

ma dokładnie

n + k − 1

k − 1

różnych rozwiązań w liczbach naturalnych przy, takim jak poprzednio,
założeniu, że rozwiązania różniące się kolejnością składników są różne.

Dowód. Tezę twierdzenia można wykazać za pomocą rozumowania po-
dobnego do tego, które zostało zastosowane w poprzednim przykładzie.
Dowód przeprowadzimy jednak inną metodą. Podstawiamy

= x

+ 1,

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

Wtedy równanie przyjmuje postać

+ y

+ ... + y

= n + k.

Ponieważ szukamy rozwiązań dodatnich, więc możemy zastosować po-
przednie twierdzenie, co natychmiast prowadzi do liczby

n+k−1

k−1

Stosując odpowiednie podstawienia, możemy badać liczbę rozwią-

zań równań liniowych o bardziej skomplikowanych postaciach.

Przykład. Ile rozwiązań w liczbach naturalnych ma równanie

2x + y = 15,

gdzie x  1, y  1?

Permutacje

131

Zastosujemy podstawienie: u = 2x − 1. Oczywiście u  1. Zatem

poszukujemy wszystkich rozwiązań równania

u + x = 14,

gdzie u, x  1, a ponadto u jest liczbą nieparzystą.

Takich rozwiązań jest siedem.

1 + 13 = 14, 3 + 11 = 14, 5 + 9 = 14,

7 + 7 = 14,

9 + 5 = 14,

11 + 3 = 14, 13 + 1 = 14.

Odpowiada im siedem rozwiązań równania wyjściowego

2 · 1 + 13 = 15, 2 · 2 + 11 = 15, 2 · 3 + 9 = 15, 2 · 4 + 7 = 15,
2 · 5 + 5 = 15,

2 · 6 + 3 = 15,

2 · 7 + 1 = 15.

6.3

Permutacje

Definicja 6.4 Permutacją n-elementową (bez powtórzeń) nazywać bę-
dziemy każdą bijekcję

σ : {1, 2, ..., n} → {1, 2, ..., n}.

Umowa notacyjna. W dalszym ciągu permutacje będziemy oznaczać
przy pomocy liter greckich σ, τ , ω. Zamiast pisać σ : {1, 2, ..., n} →
{1, 2, ..., n} będziemy też pisać

σ =

...

σ(1) σ(2) ... σ(n)

Superpozycję permutacji, która jest oczywiście też permutacją, na-

zywamy niejednokrotnie iloczynem permutacji. Zamiast pisać σ ◦ τ pi-
sze się na ogół στ . Permutację odwrotną do σ oznacza się, tak jak
w przypadku funkcji, symbolem σ

−1

Przykład. Dane są permutacje zbioru 6-elementowego

τ =

1 2 3 4 5 6
2 4 1 3 6 5

132

Podziały i permutacje. Liczby Stirlinga i Bella

σ =

1 2 3 4 5 6
1 3 6 5 4 2

Wtedy

1 7−→ τ (1) = 2 7−→

σ(2) = 3

2 7−→ τ (2) = 4 7−→

σ(4) = 5

3 7−→ τ (3) = 1 7−→

σ(1) = 1

4 7−→ τ (4) = 3 7−→

σ(3) = 6

5 7−→ τ (5) = 6 7−→

σ(6) = 2

6 7−→ τ (6) = 5 7−→ σ(5) = 4,

czyli

στ =

1 2 3 4 5 6
3 5 1 6 2 4

Ponadto

−1

2 4 1 3 6 5
1 2 3 4 5 6

1 2 3 4 5 6
3 1 4 2 6 5

Podobnie można obliczyć σ

−1

Definicja 6.5 Zbiór wszystkich permutacji zbioru n-elementowego
{1, 2, ..., n} oznaczmy symbolem S

Twierdzenie 6.4 Dla dowolnego n ∈

card (S

) = n!.

Dowód. Powyższa równość jest oczywistą konsekwencją tego, że per-
mutacje bez powtórzeń są wariacjami bez powtórzeń z n elementów po
n elementów. Dlatego ich liczba jest równa P

= V

= n!.

Definicja 6.6 Permutację σ ∈ S

nazywamy cykliczną, albo po prostu

cyklem, jeżeli istnieje ciąg liczb 1 ¬ i

< i

< ... < i

¬ n, takich że

σ(i

) = i

, σ(i

) = i

, ..., σ(i

k−1

) = i

, σ(i

) = i

a ponadto σ(i) = i dla i ∈ {1, 2, ..., n} \ {i

, i

, ..., i

Liczbę k nazywamy długością cyklu. Cykl długości dwa nazywamy

transpozycją.

Permutacje

133

Umowa notacyjna. Cykl σ ∈ S

zapisywać będziemy w postaci jed-

nowierszowej

, i

, ..., i

Zakładać będziemy przy tym, że powyższy zapis jest równoważny za-
pisom

, i

, ..., i

, i

), (i

, i

, ..., i

, i

), itd.

Zachodzi ważne twierdzenie, które podajemy bez dowodu.

Twierdzenie 6.5 Dowolna permutacja jest iloczynem skończonej ilo-
ści cykli.

Przykład. Rozważmy permutację σ ∈ S

σ =

1 2 3 4 5 6

8 9 10 11 12

5 1 6 2 4 3 10 7 8

12 11

Wtedy

σ = (1, 5, 4, 2)(3, 6)(7, 10, 9, 8)(11, 12).

Ponieważ

(1, 5, 4, 2) = (1, 2)(1, 4)(1, 5)

oraz

(7, 10, 9, 8) = (7, 8)(7, 9)(7, 10),

więc także

σ = (1, 2)(1, 4)(1, 5)(3, 6)(7, 8)(7, 9)(7, 10)(11, 12).

Jak widać, permutację można przedstawić w postaci iloczynu cykli

na różne sposoby.

Definicja 6.7 Liczbę i ∈ {1, 2, ..., n} nazywamy punktem stałym per-
mutacji σ ∈ S

, jeśli σ(i) = i.

Definicja 6.8 Permutację σ ∈ S

nazywamy nieporządkiem, jeżeli

σ(i) 6= i dla każdego i ∈ {1, 2, ..., n}.

134

Podziały i permutacje. Liczby Stirlinga i Bella

Umowa notacyjna. Liczbę wszystkich nieporządków należących do
S

oznaczamy symbolem D(n).

Twierdzenie 6.6 Dla dowolnego n ∈

zachodzi równość

D(n) =

i=0

(−1)

(n − i)!.

Dowód. Zastosujemy zasadę włączeń i wyłączeń. Dla i = 1, 2, ..., n
oznaczmy symbolami A

zbiory, które mają dokładnie jeden punkt sta-

ły, a mianowicie i. Oczywiście zbiór

i=1

zawiera, jako elementy, te

permutacje, które mają co najmniej jeden punkt stały. Ponieważ

card (A

) = (n − 1)!,

i = 1, 2, ..., n,

card (A

∩ A

) = (n − 2)!,

1 ¬ i < j ¬ n,

card (A

∩ A

) = (n − 3)!,

1 ¬ i < j < k ¬ n,

itd.,

więc

card

i=1

(n − 1)! −

(n − 2)! +

(n − 3)! − ...+

+(−1)

n+1

n
n

Tak więc

card

i=1

= n! −

(n − 1)! +

(n − 2)! + ...+

+(−1)

n
n

i=0

(−1)

(n − i)! .

Proste przekształcenia prowadzą do jeszcze jednego wzoru pozwa-

lającego na obliczanie D(n).

Wniosek. Dla n ∈

ma miejsce równość

D(n) = n!

1 −

− ... +

(−1)

Permutacje

135

Często rozwiązywanym problemem w teorii permutacji jest zagad-

nienie liczby rozkładów permutacji na określoną ilość cykli. Rozwią-
zanie tego problemu zostanie przedstawione w następnym rozdziale.
W tym miejscu przedstawimy jedynie pewien przykład.

Przykład. Ile jest permutacji dwu-, trzy- i czteroelementowych, które
są iloczynami dwóch cykli?

Łatwo zauważyć, że jest tylko jedna taka permutacja dwuelemen-

towa

(1)(2) =

1 2
1 2

i trzy permutacje należące do S

(1)(2, 3) =

1 2 3
1 3 2

, (1, 2)(3) =

1 2 3
2 3 1

(1, 3)(2) =

1 2 3
3 2 1

Permutacji należących do S

, o tej własności, jest już 11.

(1, 2, 3)(4) =

1 2 3 4
2 3 1 4

, (1, 2, 4)(3) =

1 2 3 4
2 4 3 1

(1, 3, 4)(2) =

1 2 3 4
3 2 4 1

, (1, 3, 2)(4) =

1 2 3 4
3 1 2 4

(1, 4, 2)(3) =

1 2 3 4
4 1 3 2

, (1, 4, 3)(2) =

1 2 3 4
4 2 1 3

(1, 2)(3, 4) =

1 2 3 4
2 1 4 3

, (1, 3)(2, 4) =

1 2 3 4
3 4 1 2

(1, 4)(2, 3) =

1 2 3 4
4 3 2 1

, (2, 3, 4)(1) =

1 2 3 4
1 3 4 2

(2, 4, 3)(1) =

1 2 3 4
1 4 2 3

136

Podziały i permutacje. Liczby Stirlinga i Bella

6.4

Liczby specjalne

W kombinatoryce ważną rolę odgrywają pewne funkcje, jak n 7→

n! czy (n, k) 7→

n
k

, oraz ich wartości. Właśnie te wartości tworzą

ciągi liczb o szczególnym znaczeniu, pozwalające na rozwiązanie wielu
istotnych problemów.

Wartości funkcji kombinatorycznych znajdują się w odpowiednich

tablicach. Dla przykładu, tablica dla pierwszych jedenastu wartości
funkcji silnia przedstawia się następująco

120

720

5040

40320

362880

3628800

Także współczynniki dwumianowe

n
k

mogą być umieszczane w ta-

beli. Oto taka właśnie tabela dla 0 ¬ k ¬ n ¬ 10.

126

120

210

252

210

120

Jak dobrze wiadomo, współczynniki dwumianowe mogą być przed-

stawione w postaci tzw. trójkąta Pascala.

Liczby specjalne

137

126

120

210

252

210

120

Liczby w kolejnych wierszach są sumami liczb z wiersza wcześniej-

szego, sąsiadujących „od góry” z danymi liczbami. Zależność ta wynika
z udowodnionej w poprzednim rozdziale własności

n − 1

k − 1

n − 1

Kolejnym ważnym pojęciem kombinatorycznym są tzw. liczby Stir-

linga. Są dwa rodzaje takich liczb: liczby Stirlinga podzbiorowe (dru-
giego rodzaju) i liczby Stirlinga cykliczne (pierwszego rodzaju).

Definicja 6.9 Liczbami podzbiorowymi Stirlinga nazywamy liczby

(

)

i=0

(−1)

(k − i)

Innymi słowy, liczby podzbiorowe Stirlinga

n
k

są równe ilościom

podziałów zbioru n-elementowego na k podzbiorów.

Nietrudno jest dowieść, że liczby te, podobnie jak współczynniki

dwumianowe, spełniają pewną zależność rekurencyjną.

Twierdzenie 6.7 Dla n, k ∈

N, 1 ¬ k ¬ n, zachodzą równości

(

)

= 1

138

Podziały i permutacje. Liczby Stirlinga i Bella

(

)

= k

(

n − 1

)

(

n − 1

k − 1

)

Liczby podzbiorowe Stirlinga można zaprezentować w postaci ta-

blicy.

0 1

9 10

0 1

301

350

140

0 1 127

966

1701

1050

266

0 1 255 3025

7770

6951

2646

462

0 1 511 9330 34105 42525 22827 5880 750 45

Zauważmy, że pierwsza kolumna powyższej tablicy zawiera liczby

. Dołączenie takich liczb jest wygodne ze względów czysto rachun-

kowych. Jednak interpretację kombinatoryczną jako liczby podziałów
zbioru n-elementowego na k, k > 0, podzbiorów, mają jedynie liczby

n
k

, k > 0.

Definicja 6.10 Niech n ∈

. Liczbami Bella nazywamy liczby

(

)

(

)

+ ... +

(

)

Liczby Bella są zatem równe ilości wszystkich możliwych podziałów

zbioru n-elementowego.

Przykład. Na ile sposobów można przedstawić zbiór 5-elementowy
w postaci sum zbiorów niepustych?

Liczby specjalne

139

Liczba takich podziałów jest równa

(

)

(

)

(

)

(

)

(

)

= 1 + 15 + 25 + 10 + 1 = 52

Definicja 6.11 Cyklicznymi liczbami Stirlinga nazywamy liczby

n
k

k, n ∈

N, k ¬ n, które wyrażają liczbę permutacji należących do S

które można przedstawić w postaci iloczynu k cykli.

Twierdzenie 6.8 Dla dowolnych k, n ∈

N, 1 ¬ k ¬ n, zachodzą

równości

= 0

= (n − 1)

n − 1

n − k

Liczby cykliczne Stirlinga także mogą być umieszczone w odpo-

wiedniej tablicy.

8 9

120

274

255

720

1764

1624

735

175

5040

13068

13132

6769

1960

322

0 40320 109584 118124 67284 22449 4536 546 36 1

Przykład. Znajdź wszystkie permutacje należące do S

, które są ilo-

czynami dwóch cykli.

140

Podziały i permutacje. Liczby Stirlinga i Bella

Oto one

(1)(2, 3, 4), (1)(3, 2, 4), (2)(1, 3, 4), (2)(3, 1, 4),
(3)(1, 2, 4), (3)(2, 1, 4), (4)(1, 2, 3), (4)(2, 1, 3),
(1, 2)(3, 4), (1, 3)(2, 4), (1, 4)(2, 3).

Jak widać, jest ich 11, co zgadza się z teorią, bowiem

= 11.

Odnotujemy jeszcze jeden ważny, a zarazem prosty, związek.

Twierdzenie 6.9 Dla dowolnej liczby n ∈

+ ... +

= n! .

Główne pojęcia teorii grafów

7.1

Nieformalne wprowadzenie do teorii
grafów

Pojęcie grafu wydaje się intuicyjnie łatwo uchwytne. Graf two-

rzą dwa zbiory: wierzchołków V i krawędzi E (są to zbiory skończo-
ne, jeśli graf jest skończony; w przeciwnym przypadku - przynajmniej
zbiór V jest nieskończony). Użycie takich terminów jak „wierzchołek”
i „krawędź” sugeruje, że grafy posiadają (dotyczy to zwłaszcza gra-
fów skończonych) interpretację geometryczną. By się o tym przekonać,
przyjrzyjmy się następującym przykładom.

142

Główne pojęcia teorii grafów

Przykład

(i) Rozważmy następujący graf

W tym przypadku V = {v

, v

}, zaś E = {e

, e

}. Jak widać, nie każde dwa wierzchołki połączone są

krawędziami. Ponadto jeden z wierzchołków, a mianowicie v

, nie jest

połączony krawędzią z żadnym innym wierzchołkiem. Gdybyśmy kra-
wędziom przypisali liczby, na przykład tak jak na poniższym rysunku
to otrzymalibyśmy tzw. graf z wagami.

Nieformalne wprowadzenie do teorii grafów

143

Tego rodzaju grafy mają wiele zastosowań, między innymi służą

do przedstawiania odległości - rozumianych jako długości dróg pomię-
dzy wybranymi miejscowościami. Interpretując w ten sposób powyższy
graf, zauważamy na przykład, że droga z v

do v

liczy 30 km, a z v

do v

- 47 km. Zarazem widzimy, że v

i v

nie są połączone bezpośred-

nio. By dostać się z v

do v

, należy po drodze „odwiedzić” v

lub v

otrzymując drogi o długości odpowiednio 65 km i 106 km. Zauważmy,
że z v

nie można dostać się do pozostałych wierzchołków, co jest od-

zwierciedleniem tego, iż pomiędzy tą miejscowością a pozostałymi nie
ma połączeń drogowych (np. v

znajduje się na wyspie albo w innym

niedostępnym terenie).

(ii) Graf przedstawiony poniższym rysunkiem pokazuje w jaki sposób

połączone są ze sobą za pomocą mostów różne części pewnego
miasta położonego w ujściu do morza dwóch rzek (rysunek na
stronie następnej).

Krawędzie, takie jak e

i e

oraz e

i e

łączące te same wierzchołki

nazywane są wielokrotnymi, a graf zawierający takie krawędzie na-
zywany jest multigrafem, w przeciwieństwie do tzw. grafów prostych,
niemających krawędzi wielokrotnych. Przy okazji zauważmy, że krawę-
dzie mogą być przedstawione nie tylko za pomocą odcinków, ale także
łuków.

144

Główne pojęcia teorii grafów

(iii) Niech dany będzie graf

Ilustruje on relację podzielności w zbiorze {2, 3, 5, 6, 9, 15}. Jest to

relacja częściowego porządku, a więc między innymi - zwrotna. Oznacza
to, że każda z liczb rozważanego zbioru jest połączona sama ze sobą.
Tego rodzaju krawędzie nazywane są pętlami.

Nieformalne wprowadzenie do teorii grafów

145

(iv) Weźmy teraz pod uwagę następujący graf

Odpowiada on schematowi losowania kuli koloru białego, czerwo-

nego i zielonego z jednej z dwóch urn: u

i u

. Losowanie to prze-

biega w sposób następujący: z prawdopodobieństwem p

wybieramy

i-tą urnę, i = 1, 2. Temu wyborowi odpowiada przejście z wierzchoł-
ka s (start) do jednego z wierzchołków u

i u

. Przy tym oczywiście

+ p

= 1. Następnie z wybranej urny losujemy jedną kulę: białą,

czerwoną lub zieloną. Jeżeli losujemy z urny u

, to odpowiednie praw-

dopodobieństwa są równe: q

, q

i q

, gdzie q

+ q

= 1. Jeżeli

natomiast losujemy z urny u

, to czynimy to z prawdopodobieństwami

równymi odpowiednio q

, q

i q

, gdzie q

+ q

= 1.

Powyższy graf należy do szczególnego rodzaju grafów nazywanych

drzewami. Wierzchołek s nazywamy korzeniem. Takie grafy będą oma-
wiane w następnym rozdziale.

(v) Teoria grafów ma zastosowanie w rozważaniach dotyczących au-

tomatów skończonych (por. podrozdział 3.3).

146

Główne pojęcia teorii grafów

Oto graf ilustrujący działanie automatu skończonego o stanach q

, q

, z których q

jest stanem początkowym, a q

stanem ak-

ceptującym. Automat odczytuje słowa napisane na taśmie przy użyciu
znaków alfabetu

= {0, 1}.

W tym przypadku ważna jest kolejność uzyskiwanych stanów. Dla-

tego krawędzie zostały zaopatrzone w strzałki. Tego rodzaju grafy na-
zywane są grafami skierowanymi albo digrafami. Również one, podob-
nie jak drzewa, będą jednym z tematów następnego rozdziału. Od-
notujmy, że drzewa w niektórych ujęciach teorii grafów zaliczane są
właśnie do grafów skierowanych.

Powyższy przykład ukazuje, jak wiele zastosowań ma teoria grafów.

W istocie, nie ma chyba dziedziny matematyki, która nie miałaby pew-
nych związków z tą teorią. Zanim przejdziemy do następnego podroz-
działu, w którym przedstawione zostaną ścisłe definicje podstawowych
pojęć teorii grafów, zwróćmy uwagę na dwie kwestie.

Po pierwsze, zauważmy, że graf jest pojęciem abstrakcyjnym, a ry-

sunki przedstawiające grafy mają swoiste własności geometryczne, któ-
re niosą ze sobą pewną dodatkową informację, nie odzwierciedlającą
relacji zachodzących w grafie.

Przykład. Poniższe dwa rysunki przedstawiają faktycznie ten sam
graf. Na rysunku pierwszym krawędzie e

i e

przecinają się w punkcie

niebędącym wierzchołkiem, a na rysunku drugim nie mają punktów
wspólnych.

Przykład ten stanowi zatem ostrzeżenie, aby nie traktować teorii

grafów jako działu geometrii. Grafy, jak to zobaczymy w następnym

Nieformalne wprowadzenie do teorii grafów

147

podrozdziale, są funkcjami, a rysunki je przedstawiające, czyli wykresy,
mogą mieć własności akcydentalne, które trzeba odróżnić od własności
istotnych.

Kolejna kwestia, którą należy poruszyć, dotyczy oznakowania wierz-

chołków i krawędzi grafu. Bardzo często przedstawiając grafy, kiedy to
nie prowadzi do nieporozumień, pomijamy oznaczenia wierzchołków
i krawędzi. Takie grafy nazywamy nieoznakowanymi, w przeciwień-
stwie do grafów oznakowanych. Jednak rozróżnienie pomiędzy oboma
rodzajami grafów staje się istotne, gdy zliczamy grafy.

Przykład

(i) Istnieje jeden graf oznakowany o trzech wierzchołkach.

Istnieje też jeden graf nieoznakowany.

(ii) Dla grafu nieoznakowanego

148

Główne pojęcia teorii grafów

istnieje 4!/4 = 6 grafów oznakowanych, powiedzmy o wierzchoł-
kach 1, 2, 3, 4. Oto one (symbole dla krawędzi pomijamy):

Zauważmy, że na przykład rysunki

przedstawiają ten sam graf. Podobnie jest w pozostałych przy-
padkach. Z tego względu rozważanych grafów oznakowanych jest
6 a nie 24 = 4!.

Nieformalne wprowadzenie do teorii grafów

149

Zliczanie powyższych grafów jest w gruncie rzeczy wersją

znanego zadania kombinatorycznego: na ile sposobów można po-
sadzić przy okrągłym stole n osób (w tym wypadku cztery osoby),
jeśli istotne jest to, kto z kim sąsiaduje, a nie jak położone jest
miejsce siedzenia każdej osoby w stosunku do otoczenia?

Gdyby przy rozmieszczaniu gości przy stole brać pod uwagę

ich położenie w stosunku do otoczenia, należałoby rozważać, np.
następujące grafy, gdzie o

, i = 1, 2, 3, 4, ..., symbolizują otoczenie

(można też rozważać grafy nieco prostsze).

σ(2)

σ(1)

σ(4)

σ(3)

Takich grafów, przy założeniu, że wierzchołki o

nie permutują

się, jest 4! = 24.

(iii) Weźmy pod uwagę graf nieoznakowany o 6 wierzchołkach, w któ-

rych każdy wierzchołek jest połączony z każdym innym jedną
krawędzią.

Nietrudno zauważyć, ze grafowi temu odpowiada jeden graf ozna-
kowany przy użyciu symboli 1, 2, 3, 4, 5, 6.

150

Główne pojęcia teorii grafów

7.2

Podstawowe definicje teorii grafów

W podrozdziale tym oraz w podrozdziałach następnych rozważać

będziemy grafy nieskierowne. Nazywać je będziemy po prostu grafami.
Będziemy dopuszczać istnienie krawędzi wielokrotnych, pętli i pętli
wielokrotnych.

Definicja 7.1 Dla dowolnego niepustego zbioru V symbolem P

(V )

oznaczamy zbiór wszystkich podzbiorów zbioru V , które mają co najwy-
żej dwa elementy, za wyjątkiem zbioru pustego, tzn.

(V ) = {{v, w} : v, w ∈ V }.

Uwaga. Z powyższej definicji wynika, że gdy v = w, otrzymuje się
zbiór jednoelementowy.

Definicja 7.2 Niech dane będą dwa niepuste i rozłączne zbiory V oraz
E. Grafem o zbiorze wierzchołków V i zbiorze krawędzi E nazywamy
odwzorowanie

Γ : E → P

(V )

przyporządkowujące każdej krawędzi dwa (lub jeden) wierzchołki.

Jeżeli dla e ∈ E, u ∈ Γ(e), to wierzchołek u nazywamy końcem e

lub mówimy, że e jest incydentna z u.

Jeśli card (Γ(e)) = 1, to e nazywamy pętlą.
Jeżeli dla dwóch różnych krawędzi e i f

Γ(e) = Γ(f ),

to e i f nazywamy krawędziami wielokrotnymi.

Definicja 7.3 Jeżeli funkcja Γ : E → P

(V ) jest iniekcją, to graf

nazywamy prostym. W przeciwnym przypadku graf nazywamy multi-
grafem.

Uwaga. Graf prosty nie ma krawędzi wielokrotnych w przeciwieństwie
do multigrafu, który takie krawędzie posiada.

Definicja 7.4 Wierzchołek v ∈ V nazywamy izolowanym, jeśli

v /

∈ Γ(E) =

[

e∈E

Γ(e).

Podstawowe definicje teorii grafów

151

Definicja 7.5 Jeśli dla dowolnych wierzchołków u, v ∈ V , card (V ) =
n  2, takich że u 6= v, zachodzi zależność

card (Γ

−1

({u, v})) = 1,

to graf nazywamy pełnym i oznaczamy go symbolem K

Przykład. Grafami pełnymi są poniższe grafy nieoznakowane

Grafy pełne to te, których dowolne dwa różne wierzchołki połączone
są dokładnie jedną krawędzią.

Definicja 7.6 Graf Γ : E → P

(V ) nazywamy k-dzielnym, jeżeli

V = V

∪ V

∪ ... ∪ V

gdzie

∩ V

= ∅

dla

1 ¬ i < j ¬ k,

oraz

e∈E

1¬i<j¬k

(Γ(e) ∩ V

6= ∅ ∧ Γ(e) ∩ V

= ∅) .

152

Główne pojęcia teorii grafów

Innymi słowy, w grafie k-dzielnym każda krawędź łączy wierzchołki

należące do dwóch różnych zbiorów V

oraz V

, i, j = 1, 2, ..., k.

Przykład

(i) Wśród grafów k-dzielnych szczególną rolę odgrywają grafy dwu-

dzielne, czyli takie, dla których V = U ∪ W , V 6= ∅ 6= W ,
U ∩ W = ∅, i każda krawędź grafu łączy wierzchołek u

∈ U

z wierzchołkiem w

∈ W . Oto kilka przykładów takich grafów.

(a)

(b)

Podstawowe definicje teorii grafów

153

(c)

(d)

(ii) A oto przykład dwóch grafów trójdzielnych.

(a)

(b)

Definicja 7.7 Pełnym grafem k-dzielnym nazywamy taki graf, że
V = V

∪ V

∪ ... ∪ V

, zbiory V

, i = 1, 2, ..., k, są parami rozłącz-

ne i niepuste oraz każdy wierzchołek v

∈ V

jest połączony krawędzią

z każdym wierzchołkiem v

∈ V

, i 6= j, a ponadto wierzchołki należące

do dowolnego ze zbiorów V

, i = 1, 2, ..., k, nie są połączone ze sobą.

Jeżeli zachodzą równości card (V

) = r

, i = 1, 2, ..., k, to pełny graf

k-dzielny oznaczamy symbolem K

,...,r

Przykład

(i) Graf

jest grafem typu K

4,2

154

Główne pojęcia teorii grafów

(ii) Graf

jest grafem typu K

5,1

Definicja 7.8 Stopniem deg(v) wierzchołka v ∈ V grafu Γ : E →
P

(V ) nazywamy liczbę

card {e ∈ E : v ∈ Γ(e) ∧ card Γ(e) = 2}+

+ 2 card {e ∈ E : v ∈ Γ(e) ∧ card Γ(e) = 1}.

Powyższa definicja wydaje się skomplikowana, jednak jej sens jest

prosty. Stopień to liczba krawędzi dwuwierzchołkowych incydentnych
z danym wierzchołkiem, powiększona o podwojoną liczbę pętli wycho-
dzących (i wchodzących do wierzchołka).

Przykład. Rozważamy graf

Wtedy

deg(v

) = 2,

deg(v

) = 7, deg(v

) = 8, deg(v

) = 4,

deg(v

) = 4, deg(v

) = 9, deg(v

) = 2, deg(v

) = 0.

Podstawowe definicje teorii grafów

155

Definicja 7.9 Minimalnym i maksymalnym stopniem wierzchołka gra-
fu Γ : E → P

(V ) nazywamy odpowiednio liczby

δ(Γ) = min{deg(v) : v ∈ V }

oraz

∆(Γ) = max{deg(v) : v ∈ V }.

Definicja 7.10 Graf Γ : E → P

(V ) nazywamy regularnym stopnia

k ∈

N, jeżeli

δ(Γ) = ∆(Γ) = k.

Przykład. Grafami regularnymi są tzw. grafy platońskie odpowiada-
jące pięciu prawidłowym wielościanom (por. [16, s. 31]).

czworościan

sześcian

ośmiościan

dwunastościan

156

Główne pojęcia teorii grafów

dwudziestościan

Definicja 7.11 Dla grafu Γ : E → P

(V ) symbolami d

(Γ), d

(Γ), ...,

(Γ), ... oznaczamy liczby wierzchołków grafu mające stopień odpo-

wiednio: zero, jeden, ..., k, itd. A zatem

(Γ) = card ({v ∈ V : deg(v) = k}),

k ∈

Twierdzenie 7.1 Dla grafu Γ : E → P

(V ) zachodzi równość

∆(Γ)

k=0

k d

(Γ) = 2 card (E).

Dowód twierdzenia jest oczywisty, ponieważ licząc stopnie wierz-

chołków, liczymy dwukrotnie krawędzie dwuwierzchołkowe, a każda pę-
tla zwiększa stopień wierzchołka o dwa.

Przykład. Powyższy wynik pozwala na stwierdzenie, czy istnieje graf,
któremu odpowiada zadany ciąg liczb d

(Γ), d

(Γ), .... Dla przykładu,

łatwo zauważyć, że nie istnieje graf o dwóch wierzchołkach izolowanych,
jednym wierzchołku stopnia pierwszego, dwóch wierzchołkach stopnia
drugiego i dwóch wierzchołkach stopnia trzeciego, gdyż

2 · 0 + 1 · 1 + 2 · 2 + 2 · 3 = 11,

a ta liczba nie jest podzielna przez 2.

Podstawowe definicje teorii grafów

157

Definicja 7.12 Drogą w grafie Γ : E → P

(V ), mającą długość k ∈

nazywamy ciąg krawędzi e

...e

o tej własności, że kolejne krawędzie

posiadają wspólne wierzchołki, tzn.

1¬i¬k−1

Γ(e

) ∩ Γ(e

i+1

) 6= ∅.

Uwaga. Droga e

...e

może być też zapisana jako ciąg wierzchołków

...v

k+1

, gdzie Γ(e

) = {v

, v

i+1

}, i = 1, 2, ..., k. Jednak ciąg wierz-

chołków nie określa jednoznacznie drogi w przypadku multigrafu.

Przykład. Niech dany będzie następujący multigraf:

Wtedy droga acdf może być zapisana jako v

. Zwróćmy

uwagę na to, że ostatni zapis odpowiada także drogom acef , abdf ,
abef .

Definicja 7.13 Drogę e

...e

nazywamy zamkniętą, jeżeli odpowiada

jej ciąg wierzchołków v

...v

Definicja 7.14 Drogę e

...e

nazywamy prostą, jeżeli e

6= e

dla

i, j = 1, 2, ...k, i 6= j.

Definicja 7.15 Prostą drogę zamkniętą e

...e

= v

...v

nazy-

wamy cyklem, jeżeli v

6= v

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

158

Główne pojęcia teorii grafów

Przykład. Rozważamy graf

Wtedy e

, e

są przykładami dróg.

Z kolei drogi e

, e

czy e

są przykładami dróg zamknię-

tych. Przy okazji zauważmy, że niekiedy samo wypisanie symboli kra-
wędzi może być niejednoznaczne. Dla przykładu, są dwie drogi za-
mknięte opisane symbolami e

, a mianowicie drogi v

oraz v

Jak zatem widać, niekiedy wygodniej jest posłużyć się ciągiem wierz-
chołków.

Drogami prostymi zamkniętymi są na przykład: e

, e

= v

Pierwsze trzy z powyższych dróg są przy tym cyklami, w przeci-

wieństwie do ostatniej drogi prostej.

Informację na temat tego, w jaki sposób połączone są ze sobą wierz-

chołki grafu zawiera tzw. macierz sąsiedztwa. Oto jej definicja:

Definicja 7.16 Macierzą sąsiedztwa grafu Γ : E → P

(V ) o n wierz-

chołkach v

, v

, ..., v

nazywamy macierz S mającą tę własność, że jej

dowolny wyraz s

jest równy liczbie krawędzi łączących wierzchołek v

z wierzchołkiem v

, gdzie i, j = 1, 2, ..., n.

Stwierdzenie. Dla dowolnego grafu Γ : E → P

(V )

S = S

gdzie po prawej stronie znaku równości występuje macierz transpono-
wana macierzy S.

Podstawowe definicje teorii grafów

159

Przykład. Niech dany będzie graf

Odpowiada mu macierz sąsiedztwa

S =



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

0 0 0 0 0 0 0
0 0 0 2 0 0 0
0 0 1 0 1 0 0
0 2 0 0 1 2 0
0 0 1 1 0 0 1
0 0 0 2 0 0 0
0 0 0 0 1 0 0



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

Macierz sąsiedztwa pozwala na znalezienie liczby dróg długości m,

m ∈

, łączących dowolne dwa wierzchołki grafu. Zachodzi mianowi-

cie twierdzenie

Twierdzenie 7.2 Jeżeli S jest macierzą sąsiedztwa grafu Γ : E →
P

(V ), gdzie card (V ) = n, to liczba dróg długości m, m ∈

, łą-

czących dowolny wierzchołek v

z dowolnym wierzchołkiem v

, i, k =

1, 2, ..., n, jest równa s

(m)
ik

, gdzie ten ostatni symbol oznacza wyraz ma-

cierzy S

znajdujący się w i-tym wierszu i k-tej kolumnie tej macierzy.

Dowód. Przeprowadzimy indukcję względem m ∈

. Dla m = 1

równość jest oczywista. Załóżmy, że jest ona także prawdziwa dla
m ∈

Z wierzchołka v

do wierzchołka v

, i, k = 1, 2, ..., n, można przejść

wzdłuż m+1 krawędzi na jeden ze sposobów zilustrowanych poniższym
diagramem.

160

Główne pojęcia teorii grafów

(m)
i1

(m)
i2

(m)
ij

(m)
in

Tak więc, po przejściu m krawędzi możemy dojść do wierzchołka

na s

(m)
i1

sposobów, do wierzchołka v

na s

(m)
i2

sposobów, itd. Z kolei

z wierzchołka v

do wierzchołka v

prowadzi s

krawędzi, z wierzchołka

do v

prowadzi s

krawędzi itd.

Ostatecznie wszystkich dróg długości m + 1 od v

do v

jest

(m)
ik

j=1

(m)
ij

co kończy dowód twierdzenia.

Przykład. Weźmy pod uwagę ten sam graf, co w poprzednim przy-
kładzie. Obliczmy S

. Aby to uczynić, najpierw obliczamy S



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

0 0 0 0 0 0 0
0 4 0 0 2 4 0
0 0 2 1 1 0 1
0 0 1 9 0 0 1
0 2 1 0 3 2 0
0 4 0 0 2 4 0
0 0 1 1 0 0 1



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

Podstawowe definicje teorii grafów

161

Następnie obliczamy S



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

2 18

0 18 1

11 18 0

4 11

2 18



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

Zauważmy na przykład, że zgodnie z powyższą macierzą, dróg dłu-

gości 3, wiodących z v

do v

jest 11. Wypiszmy te drogi:

, e

Kolejnym ważnym pojęciem, które należy wprowadzić, jest pojęcie

podgrafu.

Definicja 7.17 Niech dany będzie graf Γ : E → P

(V ). Podgrafem

tego grafu nazywamy dowolny graf Γ

: E

→ P

), taki że E

⊂ E,

⊂ V oraz

e∈E

(e) = Γ(e).

Inaczej mówiąc, podgraf danego grafu to graf, który powstaje z da-

nego grafu przez ewentualne usunięcie kilku krawędzi lub wierzchołków.

Przykład. Podgrafami grafu rozważanego w ostatnich dwóch przykła-
dach są na przykład grafy (pomijamy dla uproszczenia symbole kra-
wędzi).

(i)

(ii)

(iii)

162

Główne pojęcia teorii grafów

Natomiast podgrafami nie są poniższe diagramy,

(iv)

(v)

które powstały odpowiednio poprzez usunięcie z grafu wyjściowego
wierzchołków v

, v

- w przypadku (v) - wierzchołków v

, v

oraz krawędzi e

, e

Szczególnie ważnym pojęciem w teorii grafów jest pojęcie izomor-

fizmu grafów, pozwalające na nieodróżnianie grafów (i ich rysunków),
które mają te same własności.

Definicja 7.18 Dwa grafy Γ

: E

→ P

) i Γ

: E

→ P

)

nazywamy izomorficznymi, jeżeli istnieją bijekcje ϕ : E

→ E

i ψ :

→ V

, takie że

e∈E

u,w∈V

(e) = {u, w} ⇔ Γ

(ϕ(e)) = {ψ(u), ψ(w)}.

Uwaga. Sens powyższej definicji jest następujący. Grafy są izomor-
ficzne wtedy i tylko wtedy, gdy odpowiadającym sobie krawędziom
odpowiadają również incydentne z nimi pary wierzchołków. Powyższa
definicja może być znacznie uproszczona, gdy rozważa się grafy proste,
ponieważ w tym przypadku każda krawędź e grafu może być utoż-
samiona z incydentnymi z nią wierzchołkami u i w (w szczególnym
przypadku, gdy e jest pętlą, u = w), tzn. e = {u, w}.

W dalszym ciągu, jeśli wierzchołki u i w mają powyższą własność,

tzn. {u, w} ∈ E, czyli są wierzchołkami sąsiednimi, zapisywać to bę-
dziemy w postaci u ∼ w.

Tego samego symbolu ∼ używać będziemy dla zaznaczenia, że

wierzchołki sąsiadują ze sobą, bez względu na to jaki graf rozważa-
my.

Spójność grafów

163

Tak więc zachodzi wniosek

Wniosek. Grafy proste Γ

: E

→ P

) i Γ

: E

→ P

) są

izomorficzne, jeżeli istnieje bijekcja ψ : V

→ V

oraz

u,w∈V

u ∼ w ⇔ ψ(u) ∼ ψ(w).

Przykład.

(i) Dwa poniższe grafy proste są w oczywisty sposób izomorficzne.

(ii) Z kolei następujące grafy nie są izomorficzne, mimo iż mają tyle

samo wierzchołków odpowiednich stopni oraz taką samą ilość kra-
wędzi. Jednak drugi z grafów ma cykl długości osiem: wqrspvtuw,
podczas gdy graf pierwszy takiego cyklu nie posiada.

7.3

Spójność grafów

Definicja 7.19 Graf niepusty Γ : E → P

(V ) nazywać będziemy spój-

nym, jeżeli dowolne dwa jego wierzchołki mogą być połączone drogą.
W przeciwnym wypadku graf nazywać będziemy niespójnym.

164

Główne pojęcia teorii grafów

Definicja 7.20 Składową niespójnego grafu Γ : E → P

(V ) nazywać

będziemy każdy maksymalny spójny podgraf tego grafu, tzn. taki podgraf,
który po dołączeniu kolejnego wierzchołka grafu Γ, wraz z incydentnymi
z nim krawędziami przestaje być spójny.

Przykład. Graf

jest niespójny. Składa się z trzech składowych.

Definicja 7.21 Niech dany będzie graf Γ : E → P

(V ).

Zbiór E

⊂ E, taki ze graf Γ po usunięciu krawędzi należących do

E przestaje być grafem spójnym, nazywać będziemy zbiorem rozspaja-
jącym.

Zbiór V

⊂ V o tej własności, że usunięcie z grafu Γ wierzchołków

należących do V

wraz z incydentnymi z nimi krawędziami powoduje,

że Γ przestaje być grafem spójnym, nazywać będziemy zbiorem rozdzie-
lającym.

Rozcięciami nazywać będziemy zarówno zbiory rozspajające, jak

i rozcinające, takie że ich podzbiory właściwe nie są odpowiednio zbio-
rami rozspajającymi lub rozcinającymi.

Liczby λ(Γ) = card (E

) oraz k(Γ) = card (V

), gdzie E

oraz V

są

rozcięciami o najmniejszych liczbach elementów, nazywamy odpowied-
nio spójnością krawędziową i spójnością wierzchołkową.

Twierdzenie 7.3 ([16, s. 43]) Załóżmy, że Γ : E → P

(V ) jest gra-

fem prostym mającym n składników. Wtedy

card (V ) − n ¬ card (E) ¬

(card (V ) − n)(card (V ) − n + 1).

Dowód twierdzenia jest nieskomplikowany. Wykorzystuje on induk-

cję w stosunku do liczby krawędzi grafu.

Spójność grafów

165

Z powyższego twierdzenia wynika natomiast następujące

Twierdzenie 7.4 Jeżeli dla grafu prostego Γ : E → P

(V ) zachodzi

nierówność

card (E) >

(card (V ) − 1)(card (V ) − 2),

to graf ten jest spójny.

Zauważmy, że zachodzi następujący wynik

Twierdzenie 7.5 ([8, s.12]) Jeżeli graf Γ : E → P

(V ) ma więcej

niż jeden wierzchołek, to

k(Γ) ¬ λ(Γ) ¬ δ(Γ).

Dowód. Dowiedziemy najpierw nierówności k(Γ) ¬ λ(Γ).

Niech E

będzie dowolnym minimalnym zbiorem krawędzi, takim

że graf Γ

: E \ E

→ P

(V ) jest niespójny. Należy wykazać, że

k(Γ) ¬ card (E

). Jeżeli graf Γ ma wierzchołek, który nie jest incy-

dentny z żadną z krawędzi ze zbioru E

, to jeżeli Γ

jest składową Γ

zawierającą v, to wierzchołki Γ

incydentne z krawędziami z E

od-

dzielają v od grafu, który powstaje z Γ poprzez usunięcie składowej
Γ

. Jednak takich wierzchołków jest co najwyżej card (E

), ponieważ

żadna krawędź z E

nie ma obu wierzchołków należących do zbioru Γ

A zatem k(Γ) ¬ card (E

Z kolei załóżmy, że dowolny wierzchołek G jest incydentny z jakąś

krawędzią należącą do E

. Niech v będzie dowolnym takim wierzchoł-

kiem, a Γ

będzie składową Γ

zawierającą v. Wtedy wierzchołki u

sąsiadujące z v, takie że {u, v} /

∈ E

należą do Γ

i są incydentne

z różnymi krawędziami z E

. Stąd wynika, że deg(v) ¬ card (E

). Po-

nieważ zbiór U wszystkich wierzchołków sąsiadujących z v oddziela v
od pozostałych wierzchołków grafu Γ, więc k(Γ) ¬ card (E

), chyba że

nie ma innych wierzchołków, czyli {v} ∪ U = V . Jednak v jest wierz-
chołkiem dowolnym, więc możemy przyjąć, że Γ jest grafem pełnym,
skąd wynika, że k(Γ) = λ(Γ) = card (V ) − 1.

166

Główne pojęcia teorii grafów

Nierówność druga zawarta w tezie twierdzenia wynika stąd, że

wszystkie krawędzie incydentne z ustalonym wierzchołkiem rozspajają
graf Γ.

Przykład. Dla grafu C

mamy oczywiście k(C

) = λ(C

) = 2.

Poruszanie się po grafach

8.1

Grafy Eulera

Teoria grafów Eulera bierze swój początek od tak zwanego proble-

mu mostów królewieckich, który został postawiony i rozwiązany w ro-
ku 1736 przez szwajcarskiego matematyka Leonarda Eulera. Problem
ten sprowadza się do odpowiedzi na następujące pytanie: czy można
przejść przez wszystkie mosty Królewca dokładnie jeden raz i powrócić
do punktu wyjścia?

Schematyczny plan Królewca (K¨

onigsbergu)

168

Poruszanie się po grafach

Rozwiązując powyższe zadanie, Euler odwołał się do grafu, w któ-

rym wierzchołki reprezentują obszary lądu stałego (l

i l

) oraz wy-

spy (w

i w

), natomiast mosty są przedstawione za pomocą krawędzi.

Tak więc, problem został sprowadzony do takiego przebycia poniższe-
go grafu, aby każda krawędź została odwiedzona jednokrotnie i aby
wierzchołek końcowy był równy wierzchołkowi początkowemu.

Euler zauważył, że droga o tych własnościach nie istnieje. Podał

też wynik bardziej ogólny, który przedstawiony zostanie poniżej.

Sformułowanie tego wyniku poprzedzimy definicjami.

Definicja 8.1 Drogą Eulera w grafie nazywać będziemy drogę prostą
w tym grafie, która zawiera wszystkie krawędzie danego grafu.

Definicja 8.2 Cyklem Eulera nazywać będziemy zamkniętą drogę Eu-
lera.

Definicja 8.3 Graf nazywać będziemy grafem Eulera albo grafem eu-
lerowskim, jeśli istnieje w nim cykl Eulera. Graf, który ma drogę Eu-
lera, ale nie ma cyklu Eulera nazywamy semi-eulerowskim lub pół-
eulerowskim.

Twierdzenie 8.1 (Eulera) Niech dany będzie graf spójny. Jest on
grafem eulerowskim wtedy i tylko wtedy, gdy wszystkie jego wierzchołki
są stopnia parzystego.

Dowód. W dalszym ciągu załóżmy, że card (V ) 2, gdyż w przeciw-
nym przypadku twierdzenie staje się trywialne. Załóżmy dalej, że naj-
krótsza droga prosta w danym grafie jest postaci e

...e

= v

...v

k+1

gdzie k ¬ card (E). Wykażemy, że v

= v

k+1

oraz że card (E) = k.

Grafy Eulera

169

Po pierwsze, zauważmy, że mogą zachodzić równości v

= v

k+1

dla

i = 2, ..., k. Jeśli tak jest istotnie, to wierzchołek v

k+1

ma stopień nie-

parzysty w grafie Γ

utworzonym z wierzchołków v

, v

, ..., v

k+1

oraz

krawędzi e

, e

, ..., e

. Rzeczywiście, każde „przejście” przez ten wierz-

chołek oznacza „wykreślenie” z drogi e

...e

dwóch krawędzi. Ponad-

to droga kończy się krawędzią e

, która dochodzi do wierzchołka v

k+1

= v

l+1

Zatem w grafie Γ

wierzchołek ten ma stopień nieparzysty. Ponie-

waż jednak wszystkie wierzchołki danego grafu, na mocy założenia,
są stopnia parzystego, więc z wierzchołka v

k+1

wychodzi jeszcze jedna

krawędź. Jeśli v

k+1

6= v

, to dołączenie tej krawędzi do danej drogi

prostej powoduje wydłużenie jej do k + 1 krawędzi. Jest to sprzeczne
z tym, co przyjęliśmy, a mianowicie, że droga e

...e

jest najdłuższą

drogą prostą w grafie. Dlatego v

= v

k+1

Oczywiście, do każdej drogi prostej należeć muszą wszystkie wierz-

chołki grafu. Gdyby tak nie było, to łącząc (a jest to możliwe na mocy
założenia spójności grafu) wierzchołek v

nienależący do Γ

, ale sąsia-

dujący z jednym z wierzchołków tego grafu, z tymże wierzchołkiem,
otrzymaliśmy drogę prostą dłuższą od danej.

W podobny sposób można uzasadnić to, że wszystkie krawędzie

grafu muszą należeć do drogi e

...e

Załóżmy, że graf jest eulerowski. Wtedy „przejście” przez każdy

wierzchołek cyklu Eulera powoduje zmniejszenie stopnia tego wierz-
chołka o 2. W przypadku wierzchołka pierwszego - i zarazem ostatnie-
go - w cyklu, krawędzi wychodzącej odpowiada krawędź dochodząca.
Zatem stopień każdego wierzchołka grafu jest liczbą parzystą.

170

Poruszanie się po grafach

Uwaga. W dowodzie drugiej implikacji nie korzystaliśmy z założenia
spójności grafu.

Uwaga. Rozwiązując zagadnienie mostów królewieckich, można odwo-
łać się także do grafu prostego, a mianowicie grafu, w którym zarówno
mosty jak i obszary lądowe są reprezentowane przez wierzchołki.

Przykład ten pokazuje, że w wielu przypadkach zamiast multigra-

fów wystarczy posłużyć się grafami prostymi.

Wniosek. Niech dany będzie graf spójny. Graf ten jest semi-eulerowski
wtedy i tylko wtedy, gdy wszystkie wierzchołki grafu, poza dwoma,
które mają stopień nieparzysty, są stopnia parzystego.

Dowód. Teza twierdzenia jest konsekwencją tego, że jeśli dwa wierz-
chołki stopnia nieparzystego w danym grafie połączymy krawędzią, to
uzyskamy graf mający cykl Eulera, którego wszystkie wierzchołki są
stopnia parzystego.

Powyższe twierdzenie oraz wniosek nie podają niestety metody

konstruowania cyklu lub drogi Eulera, jeżeli takie istnieją. W tym sen-
sie wyniki te są niekonstruktywne. Metoda konstrukcji odpowiedniej
drogi lub cyklu Eulera zawarta jest w tzw. algorytmie Fleury’ego, któ-
ry zostanie podany bez dowodu (por. [15, s. 346-350]).

Grafy Eulera

171

Algorytm Fleury’ego

◦

Jeśli graf ma wierzchołek stopnia nieparzystego, należy wybrać w
dowolny sposób taki wierzchołek. Jeżeli graf nie ma wierzchołków
stopnia nieparzystego, to wybieramy dowolny wierzchołek tego
grafu. Wybrany wierzchołek oznaczamy symbolem u.

◦

Jeżeli z wierzchołka u nie wychodzi żadna krawędź, to należy
zatrzymać algorytm.

◦

Jeżeli z u wychodzi jedna krawędź e = uv, to należy usunąć
e ze zbioru krawędzi E grafu i zarazem usunąć u ze zbioru V
wierzchołków tego grafu. Następnie należy przejść do punktu 5

◦

Jeżeli z u wychodzą co najmniej dwie krawędzie, to należy wybrać
taką krawędź e = uv, aby graf po jej usunięciu pozostał spójny.
Krawędź tę usuwamy ze zbioru E krawędzi.

◦

Należy dopisać e do ciągu krawędzi tworzących drogę lub cykl
Eulera. Podobnie należy dopisać v do ciągu wierzchołków opisu-
jących tę drogę.

◦

Należy zastąpić wierzchołek u przez wierzchołek v i przejść do
punktu 2

◦

Przykład. Zastosujmy algorytm Fleury’ego do grafu

Zauważmy najpierw, że jedynie dwa wierzchołki w grafie, v

i v

są stopnia nieparzystego. Tak więc graf jest semi-eulerowski. Zgodnie

172

Poruszanie się po grafach

z algorytmem Fleury’ego wybieramy jako początek drogi Eulera jeden
z wierzchołków stopnia nieparzystego, powiedzmy v

. Następnie wybie-

ramy jedną z trzech krawędzi wychodzących z tego wierzchołka, np. e

Usuwamy tę krawędź ze zbioru E i przechodzimy do wierzchołka v

Z wierzchołka v

wychodzi już tylko jedna krawędź - e

. Dopisujemy

ją do ciągu krawędzi tworzącego drogę Eulera, podobnie wierzchołek
v

dopisujemy do ciągu wierzchołków. Przechodzimy do v

. Kontynu-

ując powyższe rozumowanie, możemy otrzymać np. następującą drogę
Eulera

= e

Nie jest to oczywiście jedyna droga Eulera w tym grafie.

8.2

Grafy Hamiltona

Obok dróg i cykli Eulera rozpatruje się też tzw. drogi i cykle

Hamiltona przechodzące przez każdy wierzchołek grafu dokładnie jeden
raz.

Definicja 8.4 Drogą Hamiltona w grafie nazywamy taką drogę, która
przez każdy wierzchołek przechodzi dokładnie raz.

Definicja 8.5 Cyklem Hamiltona w grafie nazywamy drogę Hamilto-
na, która jest zamknięta, tzn. ostatni wierzchołek cyklu Hamiltona jest
równy wierzchołkowi początkowemu.

Definicja 8.6 Graf, który ma cykl Hamiltona nazywać będziemy gra-
fem Hamiltona albo grafem hamiltonowskim.

Graf, który ma drogę Hamiltona, ale nie ma cyklu Hamiltona, na-

zywać będziemy grafem semi-hamiltonowskim albo pół-hamiltonowskim.

Teoria grafów hamiltonowskich i semi-hamiltonowskich jest znacz-

nie bardziej skomplikowana niż teoria grafów eulerowskich i semi-eule-
rowskich. W szczególności, jak dotąd, nieznane jest twierdzenie, które
zawierałoby warunki konieczne i wystarczające na to, by graf skoń-
czony i spójny miał cykl lub drogę Hamiltona. Dlatego ograniczy-
my się do przedstawienia kilku twierdzeń podających jedynie warunki

Grafy Hamiltona

173

dostateczne, aby graf był hamiltonowski, a następnie przedstawimy
warunek konieczny, który muszą spełnić grafy hamiltonowskie i semi-
hamiltonowskie dwudzielne.

Twierdzenie 8.2 (Orego) Jeżeli dla grafu prostego Γ : E → P

(V ),

takiego że card (V ) 3, zachodzą nierówności

deg(u) + deg(v) card (V )

dla dowolnych dwóch wierzchołków u i v niesąsiadujących ze sobą, to
Γ jest grafem hamiltonowskim.

Dowód. Załóżmy, że dla grafu Γ spełnione są powyższe nierówności
lecz graf nie ma cyklu Hamiltona. Wtedy, dodając do Γ odpowiednią
ilość krawędzi, możemy otrzymać graf Γ

, który jest już grafem hamil-

tonowskim. Usuwając z Γ

jedną krawędź, uzyskujemy z kolei graf Γ

który ma drogę Hamiltona, ale nie ma cyklu Hamiltona. Przyjmijmy,
że wspomnianą drogą Hamiltona jest ciąg

...u

k−1

k = card (V ).

Wierzchołki u

i u

nie są połączone krawędzią, gdyż gdyby tak

było, otrzymalibyśmy cykl Hamiltona. A zatem w Γ

deg(u

) + deg(u

) card (V ),

ponieważ dodanie krawędzi do grafu Γ zachowuje nierówności zawarte
w założeniu twierdzenia. Z powyższej nierówności wynika, że istnie-
ją takie wierzchołki u

oraz u

i−1

, że u

sąsiaduje z wierzchołkiem u

natomiast u

i−1

sąsiaduje z wierzchołkiem u

i−1

Jednak w takim przypadku otrzymujemy cykl Hamiltona

i+1

...u

i−1

i−2

...u

co jest sprzeczne z założeniem, że graf nie jest hamiltonowski.

174

Poruszanie się po grafach

Z powyższego twierdzenia wynika natomiast

Twierdzenie 8.3 (Diraca) Niech dany będzie graf prosty Γ : E →
P

(V ), taki że card (V ) 3. Jeżeli dla dowolnego wierzchołka u tego

grafu zachodzi nierówność

deg(u)

card (V ),

to graf jest hamiltonowski.

Zachodzi również twierdzenie, które w przypadku grafów dwudziel-

nych podaje warunki konieczne na to, by graf był hamiltonowski lub
semi-hamiltonowski; zob. [15, s. 379].

Twierdzenie 8.4 Niech dany będzie graf dwudzielny Γ : E → P

(V ),

gdzie U i W tworzą podział jego wierzchołków. Wtedy, jeśli graf jest
hamiltonowski, to card (U ) = card (W ). Jeśli natomiast graf jest semi-
hamiltonowski, to |card (U ) − card (W )| = 1.

Przykład

(i) Każdy graf pełny K

, n  1, jest grafem hamiltonowskim.

(ii) Graf ośmiościanu jest także grafem Hamiltona.

Cykl Hamiltona tworzy np. ciąg wierzchołków u

Grafy Hamiltona

175

(iii) Z kolei graf

jest dwudzielny. Zbiory

U = {u

, u

}

W = {w

, w

}

stanowią podział zbioru wierzchołków, taki że

card (U ) − card (W ) = 1.

Jest to więc graf semi-hamiltonowski. Znalezienie odpowiedniej
drogi Hamiltona jest bardzo proste.

(iv) Rozważmy graf nieoznakowany.

Jest to, jak nietrudno zauważyć, graf dwudzielny.

176

Poruszanie się po grafach

Rzeczywiście, jeśli wierzchołki należące do obu zbiorów tworzą-
cych podział V = U ∪ W oznaczymy odpowiednio kropkami pu-
stymi i pełnymi, to otrzymamy graf

W tym przypadku card (U ) = 13, card (W ) = 11, a zatem graf
nie jest ani hamiltonowski ani semi-hamiltonowski.

8.3

Grafy z wagami

Definicja 8.7 Graf Γ : E → P

(V ) nazywać będziemy grafem z waga-

mi, jeśli istnieje funkcja w : E →

R przypisująca każdej krawędzi e jej

wagę w(e).

Uwaga. Wagi krawędzi reprezentują zazwyczaj takie wielkości jak:
odległość, czas lub koszt, a zatem zazwyczaj przyjmujemy, że zachodzi
w(e) > 0.

W dalszym ciągu będziemy rozpatrywać grafy o wagach dodatnich.

W przypadku, gdy wierzchołki nie są połączone krawędzią, będziemy
przyjmować, że owej „wirtualnej” krawędzi odpowiada waga równa ze-
ro.

Definicja 8.8 Niech dany będzie graf postaci Γ : E → P

(V ), gdzie

card (V ) = k  2. Macierz

H = [h

]

k×k

= [h(u

, u

)]

k×k

gdzie h

jest wagą odpowiedniej krawędzi łączącej wierzchołki u

oraz u

lub h

= 0, jeżeli taka krawędź nie istnieje, nazywać będziemy macierzą

wag grafu Γ.

Grafy z wagami

177

Definicja 8.9 Długością albo wagą drogi d = e

...e

nazywać będzie-

my liczbę

w(d) =

i=1

w(e

Szczególnie ważnym zagadnieniem teorii grafów z wagami jest pro-

blem polegający na znalezieniu drogi łączącej dwa dowolne wierzchołki
grafu, której waga jest najmniejsza. Problem ten rozwiązuje tzw. algo-
rytm Dijkstry, który przedstawiony jest poniżej. Dla ustalenia uwagi
załóżmy, że chcemy znaleźć drogę o najmniejszej wadze z wierzchołka
u do wierzchołka w (por. [7, s. 178]).

Algorytm Dijkstry

◦

Przyjmijmy

l(v) =

(

jeśli v = u,

∞ jeśli v 6= u.

Równość l(u) = 0 będziemy traktować jako ustaloną. Wielkości
l(v), v 6= u, są zmienne. Podstawiamy p = u.

◦

Dla wszystkich wierzchołków v połączonych z p krawędzią, dla
których wielkości l(v) są zmienne, należy dokonać podstawienia

l(v) := min{l(v), l(p) + h(p, v)}.

◦

Wśród tych wierzchołków, którym odpowiadają wielkości zmien-
ne, należy znaleźć najmniejszą, tzn.

l(v) = min{l(v)}.

◦

Należy przyjąć, że l(v) jest wielkością ustaloną i podstawić p = v.

◦

Jeżeli p = w, to l(p) jest wagą najkrótszej drogi z u do w. Należy
zatrzymać algorytm. Jeżeli p 6= w, należy przejść do punktu 2

◦

Dowód poprawności algorytmu. Dowód ma charakter indukcyjny.
Oczywiście, gdy u = w to l(w) = 0 daje rzeczywiście wagę najkrótszej
drogi z u do w.

Załóżmy, że po wykonaniu pewnej liczby kroków algorytmu wielko-

ści l(v) są ustalone dla wierzchołków v należących do pewnego zbioru

178

Poruszanie się po grafach

oraz są nieustalone dla wierzchołków ze zbioru V

. Po wykonaniu

kroku 2

◦

, w trakcie każdej iteracji wielkości l(v), v ∈ V

, są równe naj-

krótszym drogom z wierzchołka u do wierzchołków v, które przechodzą
jedynie przez wierzchołki należące do V

Załóżmy, że najkrótsza droga z u do v przechodzi przez co naj-

mniej jeden wierzchołek ze zbioru V

. Niech v

będzie pierwszym takim

wierzchołkiem. Ponadto, h

0, więc droga z v

do v (będąca częścią

wspomnianej najkrótszej drogi) ma nieujemną wagę a. Dodatkowo

l(v

) < l(v) − a < l(v).

Jest to sprzeczne z założeniem, że l(v) jest najmniejszą zmienną wiel-
kością. A zatem najkrótsza droga z u do v przechodzi tylko przez wierz-
chołki za zbioru V

. Wielkość l(v) jest jej wagą.

Zauważmy, że przy każdej iteracji do zbioru V

(na początku wy-

korzystywania algorytmu V

= {u}) dodajemy kolejne wierzchołki. Po

skończonej liczbie kroków w ∈ V

, czyli l(w) jest wagą najkrótszej drogi

z u do w.

Przykład. Niech dany będzie graf z wagami.

Grafy z wagami

179

Należy znaleźć, korzystając z algorytmu Dijkstry, najkrótszą drogę

(drogę o najmniejszej wadze) z wierzchołka u

do wierzchołka u

Wypiszemy najpierw macierz wag H = [h(u

, u

)]

10×10

odpowiada-

jącą temu grafowi.



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



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

Przejdźmy do wykonania algorytmu.

◦

l(u

) = 0 (wielkość ustalona), l(u

) = ∞ dla i = 2, 3, ..., 10,

p = u

Iteracja pierwsza.

◦

Z wierzchołkiem p sąsiadują wierzchołki u

, u

l(u

) = min{∞, 0 + 1} = 1,

l(u

) = min{∞, 0 + 3} = 3,

l(u

) = min{∞, 0 + 2} = 2.

◦

Obliczamy

min{1, 3, 2, ∞, ..., ∞} = 1.

Wartość ta odpowiada wierzchołkowi u

◦

l(u

) = 1 (wielkość ustalona).

p = u

◦

Nie wszystkie wierzchołki u

mają ustalone wielkości l(u

). Należy

przejść do kroku 2

◦

180

Poruszanie się po grafach

Iteracja druga

◦

Z wierzchołkiem p sąsiadują wierzchołki u

i u

, dla których l(u

)

i l(u

) są zmienne. Obliczamy

l(u

) = min{∞, 1 + 3} = 4,

l(u

) = min{∞, 1 + 5} = 6.

◦

Obliczamy

min{3, 2, 4, 6, ∞} = 2.

Wartość ta odpowiada wierzchołkowi u

◦

l(u

) = 2 (wielkość ustalona).

p = u

◦

Nie wszystkie wierzchołki u

mają ustalone wielkości l(u

). Należy

przejść do kroku 2

◦

Iteracja trzecia

◦

Z wierzchołkiem p sąsiadują wierzchołki u

i u

o nieustalonych

wartościach l(u

) i l(u

). Obliczamy

l(u

) = min{∞, 2 + 2} = 4,

l(u

) = min{∞, 2 + 7} = 9.

◦

Obliczamy

min{3, 4, 6, 9, ∞} = 3.

Wartość ta odpowiada wierzchołkowi u

◦

l(u

) = 3 (wielkość ustalona).

p = u

◦

Ponieważ nie wszystkie wielkości l(u

) są ustalone, należy przejść

do kroku 2

◦

Iteracja czwarta

◦

Z wierzchołkiem p sąsiadują wierzchołki u

, u

i u

o nieustalo-

nych l(u

), l(u

) i l(u

). Obliczamy

l(u

) = min{4, 3 + 1} = 4,

l(u

) = min{4, 3 + 1} = 4,

l(u

) = min{9, 3 + 5} = 8.

Grafy z wagami

181

◦

Obliczamy

min{4, 8, 6, ∞} = 4.

Wartość ta odpowiada wierzchołkom u

i u

◦

l(u

) = l(u

) = 4 (wielkość ustalona).

p = u

◦

Ponieważ nie wszystkie wielkości l(u

) są ustalone, należy przejść

do kroku 2

◦

Kontynuując algorytm, przypisujemy określoną wartość l(u

) każde-

mu wierzchołkowi grafu, w szczególności wierzchołkowi u

. Nietrudno

zauważyć, że

l(u

) = 7.

Jest to właśnie poszukiwana długość najkrótszej drogi łączącej u

z u

Drzewa i digrafy

9.1

Podstawowe pojęcia teorii drzew

Definicja 9.1 Graf niezawierający cykli nazywać będziemy acyklicz-
nym.

Definicja 9.2 Skończony graf acykliczny i spójny nazywać będziemy
drzewem.

Przykład. Oto kilka grafów będących drzewami:

(i)

(ii)

184

Drzewa i digrafy

(iii)

(iv)

(v)

Uwaga. Drzewa nie mają oczywiście ani pętli ani krawędzi wielokrot-
nych, ponieważ w przeciwnym przypadku zawierałyby cykle. Odnotuj-
my też jeszcze jedną prostą własność drzew: dowolne dwa wierzchołki
drzewa można połączyć jedną i tylko jedną drogą prostą - gdyby było
inaczej nie byłyby grafami acyklicznymi.

Umowa notacyjna. W dalszym ciągu drzewa oznaczać będziemy za
pomocą symbolu T (ang. tree).

Twierdzenie 9.1 Drzewo T : E → P

(V ) ma card (V ) − 1 krawędzi,

gdzie zakładamy, że card (V ) 1.

Dowód. Skorzystamy z zasady indukcji matematycznej. Dla card (V ) =
1 teza jest oczywista. Zakładamy, że twierdzenie jest prawdziwe dla
card (V ) = n.

Niech T będzie drzewem o n + 1 wierzchołkach. Usuwając jeden

wierzchołek pierwszego stopnia (w każdym drzewie takie wierzchołki
istnieją) i incydentną z nim krawędź, otrzymujemy drzewo T

o n wierz-

chołkach, które, na mocy założenia, ma n − 1 krawędzi. Stąd wynika,
że drzewo T ma n krawędzi.

Podstawowe pojęcia teorii drzew

185

Definicja 9.3 Skończony graf acykliczny nazywamy lasem.

Uwaga. Z powyższej definicji wynika, że każde drzewo jest lasem. Po-
nadto lasem jest graf niespójny, którego składowe są drzewami.

Przykład. Lasem jest np. graf

Definicja 9.4 Wyróżniony wierzchołek u drzewa T nazywać będzie-
my korzeniem, a samo drzewo będziemy w takim przypadku oznaczać
symbolem T

Uwaga. Wybór korzenia drzewa jest w zasadzie umowny. Każdy wierz-
chołek drzewa może zostać uznany za korzeń.

Przykład. Drzewo T

może być przedstawione także następująco

186

Drzewa i digrafy

Definicja 9.5 Każdy wierzchołek drzewa mający stopień 1 i niebędący
korzeniem nazywać będziemy liściem albo węzłem końcowym.

Definicja 9.6 Każdy wierzchołek drzewa niebędący ani liściem, ani
korzeniem nazywać będziemy węzłem wewnętrznym albo węzłem gałęzi.

Definicja 9.7 Jeśli wierzchołek u, sąsiadujący z wierzchołkiem v, znaj-
duje się na jedynej drodze od korzenia do v, to nazywać go będziemy
rodzicem v; v nazywać będziemy dzieckiem u.

Definicja 9.8 Jeśli wierzchołek u znajduje się na jedynej drodze z ko-
rzenia do v, to v nazywać będziemy potomkiem wierzchołka u.

Definicja 9.9 Liczbę dzieci wierzchołka nazywać będziemy jego stop-
niem wyjściowym.

Definicja 9.10 Drzewem o k  2 rozgałęzieniach nazywać będziemy
takie drzewo, w którym każdy wierzchołek ma stopień wyjściowy mniej-
szy bądź równy k.

Gdy k = 2, drzewo to nazywać będziemy drzewem binarnym.
Drzewo o k rozgałęzieniach (binarne dla k = 2) nazywać będziemy

regularnym, jeśli stopień wyjściowy każdego wierzchołka niebędącego
liściem jest równy k.

Podstawowe pojęcia teorii drzew

187

Definicja 9.11 Wysokością drzewa T

nazywać będziemy długość naj-

dłuższej drogi z u do jednego z liści.

Definicja 9.12 Niech dane będzie drzewo T

i wierzchołek v tego drze-

wa (v może być równy u). Poddrzewem drzewa T

o wierzchołku v

nazywać będziemy drzewo utworzone z wierzchołka v i jego wszystkich
potomków.

Przykład. Dla drzewa T

poddrzewami są na przykład drzewa

Definicja 9.13 Nazwy wierzchołków drzewa określać będziemy jako
etykiety.

Uwaga. Do etykietowania wierzchołków drzewa wygodnie jest posłu-
żyć się pewnym alfabetem Σ tak, aby nazwy wierzchołków tworzyły
zbiór liniowo uporządkowany.

Przykład. Rozważmy drzewo regularne o trzech rozgałęzieniach i za-
etykietujmy jego wierzchołki, korzystając ze słów z alfabetu Σ = {0, 1, 2}.

188

Drzewa i digrafy

001

000

002

011

010

012

021

020

022 .......................................

9.2

Drzewa rozpinające grafy

Definicja 9.14 Niech dany będzie skończony graf spójny Γ : E →
P

(V ). Drzewem rozpinającym (albo inaczej: spinającym) tego gra-

fu nazywać będziemy każde drzewo, którego zbiorem wierzchołków jest
zbiór V , a zbiorem krawędzi - podzbiór zbioru E.

Przykład. Niech dany będzie graf

Jego drzewami rozpinającymi są między innymi drzewa

Drzewa rozpinające grafy

189

Uwaga. Dla dowolnego grafu spójnego drzewo rozpinające może być
skonstruowane na dwa sposoby.

Pierwszy polega na usuwaniu tych krawędzi grafu, które wchodzą

w skład cykli.

190

Drzewa i digrafy

Drugi opiera się na następującej procedurze. Wybieramy dowolny

wierzchołek grafu. Łączymy ten wierzchołek z wierzchołkami z nim są-
siadującymi. Wszystkie wierzchołki otrzymanego zbioru wierzchołków
łączymy z sąsiadującymi z nimi wierzchołkami nienależącymi do tego
zbioru. Procedurę tę kontynuujemy aż do uzyskania drzewa, którego
zbiór wierzchołków jest równy zbiorowi wierzchołków danego grafu.

Zauważmy jednakże, że dla grafów niespójnych możemy w analo-

giczny sposób budować lasy rozpinające (albo inaczej: spinające), któ-
rych składowe są drzewami rozpinającymi składowych danych grafów.

W dalszym ciągu zajmiemy się zagadnieniem znalezienia drzew

rozpinających, dla których sumy wag ich krawędzi są możliwie naj-
mniejsze.

Definicja 9.15 Niech T : E → P

(V ) będzie drzewem z wagami. Licz-

bę

w(T ) =

e∈E

w(e)

nazywać będziemy wagą tego drzewa.

Definicja 9.16 Minimalnym drzewem rozpinającym grafu nazywać bę-
dziemy każde drzewo rozpinające tego grafu, którego waga jest nie więk-
sza od wag innych grafów rozpinających tego grafu.

Istnieje kilka algorytmów pozwalających na budowę minimalnego

drzewa rozpinającego. Najbardziej znane z nich to algorytmy Kruskala
i Prima (zob. [7, s. 160].

Oto pierwszy z nich.

Algorytm Kruskala

◦

Należy zacząć od grafu T , którego wierzchołkami są wszystkie
wierzchołki danego grafu Γ, lecz który nie ma ani jednej krawędzi.

◦

Należy uporządkować krawędzie grafu Γ w ciąg nierosnący

w(e

) ¬ w(e

) ¬ ... ¬ w(e

k = card (E).

◦

Podstawiamy i := 0.

Drzewa rozpinające grafy

191

◦

Podstawiamy i := i + 1 i dołączamy krawędź e

do grafu T , jeśli

T ∪ {e

} jest acykliczny; w przeciwnym przypadku nie dołączamy

do T .

◦

Jeśli i = k, to należy zatrzymać algorytm. W przeciwnym przy-
padku należy przejść do kroku 4

◦

Dowód poprawności algorytmu. Zauważmy, po pierwsze, że pod-
czas każdej iteracji algorytmu graf T zawiera się w pewnym rozpina-
jącym drzewie minimalnym grafu Γ. Rzeczywiście, na początku wyko-
nywania algorytmu T jest grafem zbudowanym z wierzchołków grafu
Γ, ale nie mającym żadnych krawędzi. Zatem T jest podgrafem mini-
malnego drzewa rozpinającego T

min

Załóżmy, że po wykonaniu n, 1 ¬ n < k, iteracji T jest podgrafem

min

. Należy pokazać, że po kolejnej iteracji T jest także podgrafem

pewnego rozpinającego drzewa minimalnego.

W dalszym ciągu symbolem T ∪ {e} oznaczać będziemy rozsze-

rzenie funkcji T na zbiór zawierający krawędź e. Jeśli T ∪ {e

n+1

} jest

grafem cyklicznym, to krawędź e

nie jest dołączona do T , a więc T

jest nadal podgrafem T

min

. Jeśli natomiast T ∪ {e

n+1

} jest grafem acy-

klicznym, to należy znaleźć minimalne drzewo rozpinające T

, którego

podgrafem jest T ∪ {e

n+1

}. Jeżeli e

n+1

należy do T

min

, to oczywiście

= T

min

. Załóżmy więc, że e

n+1

nie jest krawędzią T

min

. Stąd wynika,

że T

min

∪ {e

n+1

} jest grafem cyklicznym, a e

n+1

wchodzi w skład pew-

nego cyklu. Jednak T ∪ {e

n+1

} jest grafem acyklicznym, a stąd wynika,

że do wspomnianego cyklu należy pewna krawędź a drzewa T

min

, która

nie należy do T . Jeśli zdefiniujemy T

jako (T

min

∪ {e

n+1

}) \ {a}, to

graf ten jest spójny, ma card (V ) wierzchołków i card (V ) − 1 krawę-
dzi. A zatem jest drzewem spinającym grafu Γ i ponadto T ∪ {e

n+1

}

jest jego podgrafem. Oczywiście graf T ∪ {a} jest acykliczny. Zarazem
w(e

n+1

) ¬ w(a), ponieważ a 6= e

, i = 1, 2, ..., n + 1. Tak więc

w(T

) = w(T

min

) + w(e

n+1

) − w(a) ¬ w(T

min

co oznacza, że T

jest minimalnym drzewem rozpinającym grafu Γ.

Wystarczy wykazać jeszcze, że graf T , po zakończeniu algorytmu,

jest spójny. Wybierzmy w dowolny sposób dwa wierzchołki v

oraz v

tego grafu. Łączy je pewna droga w grafie Γ, ponieważ ten graf jest

192

Drzewa i digrafy

spójny. Gdyby pewna krawędź, powiedzmy a, należąca do tej drogi, nie
należała do grafu T , to graf T ∪ {a} zawierałby cykl, w którego skład
wchodziłaby właśnie ta krawędź. Wystarczyłoby zastąpić w rozważanej
drodze krawędź a przez pozostałe krawędzie cyklu, by otrzymać drogę
z v

do v

, całkowicie zawierającą się w T .

W jaki sposób działa algorytm Kruskala pokażemy na następują-

cym przykładzie.

Przykład. Znajdziemy minimalne drzewo rozpinające dla grafu Γ.

◦

Zaczynamy od grafu T zawierającego wszystkie wierzchołki Γ
i nie mającego żadnych krawędzi.

◦

Tworzymy uporządkowany ciąg w(e

) ¬ w(e

) ¬ ... ¬ w(e

)

(możemy to zrobić na kilka sposobów, ponieważ wśród krawędzi
są takie, którym odpowiadają te same wagi). Sposób oznaczenia
krawędzi grafu Γ przedstawia rysunek.

Drzewa rozpinające grafy

193

◦

Podstawiamy i := 0.

◦

Podstawiamy i := 1; dołączamy e

do T , tzn. przyjmujemy T :=

T ∪ {e

}, bo T ∪ {e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 2; T := T ∪ {e

}, bo T ∪ {e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 3; T := T ∪ {e

}, bo T ∪ {e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 4; T := T ∪ {e

}, bo T ∪ {e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 5; T := T ∪ {e

}, bo T ∪ {e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 6; T := T ∪ {e

}, bo T ∪ {e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 7; T := T ∪ {e

}, bo T ∪ {e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

194

Drzewa i digrafy

◦

Podstawiamy i := 8; T := T (nie dołączmy e

do T ), bo T ∪ {e

}

jest cykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 9; T := T , bo T ∪ {e

} jest cykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 10; T := T , bo T ∪ {e

} jest cykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 11; T := T ∪{e

}, bo T ∪{e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 12; T := T ∪{e

}, bo T ∪{e

} jest acykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 13; T := T , bo T ∪ {e

} jest cykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 14; T := T , bo T ∪ {e

} jest cykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 15; T := T , bo T ∪ {e

} jest cykliczny.

◦

Ponieważ i 6= 16, więc przechodzimy do kroku 4

◦

Podstawiamy i := 16; T := T , bo T ∪ {e

} jest cykliczny.

◦

Ponieważ i = 16, więc zatrzymujemy algorytm.

Zauważmy, że otrzymaliśmy następujące minimalne drzewo rozpi-

nające T .

Drzewa rozpinające grafy

195

Łatwo sprawdzić, że w(T ) = 1 + 1 + 1 + 2 + 2 + 2 + 2 + 4 + 5 = 20.

Obok algorytmu Kruskala często stosowany jest algorytm Prima,

który to algorytm znajduje minimalne drzewo rozpinające grafu bez
sortowania krawędzi pod względem wielkości ich wag. Oto ten algo-
rytm.

Algorytm Prima

◦

Niech V

:= {v

}, E

:= ∅ (T jest minimalnym drzewem roz-

pinającym grafu Γ, v

jest dowolnym wierzchołkiem grafu Γ, V

jest zbiorem wierzchołków T , E

jest zbiorem krawędzi T ).

◦

Dla dowolnego wierzchołka v

∈ V

należy znaleźć wierzchołek

∈ V

, taki że

h(v

, w

) = min{h(v

, w

) : w

∈ V

} = a

jeżeli w

istnieje; w przeciwnym przypadku wierzchołkowi v

przy-

pisujemy parę (0, ∞).

◦

Należy wybrać wierzchołek v

, taki że

= min{a

: v

∈ V

Podstawiamy V

:= V

∪ {v

}, E

:= E

∪ {(v

, w

)}.

Jeżeli card (V

) = card (V ), to należy zatrzymać algorytm.

Jeżeli card (V

) 6= card (V ) to należy przejść do kroku 4

◦

196

Drzewa i digrafy

◦

Dla dowolnego v

∈ V

, sąsiadującego z

, należy dokonać zmian

współczynników w przypisanej temu wierzchołkowi parze upo-
rządkowanej.
Jeżeli a

> h(v

, v

), to a

:= h(v

, v

), w

:= v

i przechodzimy

do kroku 3

◦

Jeżeli a

¬ h(v

, v

), to przechodzimy do kroku 3

◦

Zachęcamy Czytelnika do zastosowania algorytmu Prima do grafu

Γ rozważanego w ramach ostatniego przykładu. Dowód poprawności
algorytmu pomijamy. Zauważmy tylko, że z przebiegu algorytmu wy-
nika nie tylko to, że otrzymany graf jest acykliczny, lecz także że jest
spójny.

Wspomniane tutaj zagadnienie znajdowania minimalnego drzewa

rozpinającego dla grafu ma związek z tzw. problemem komiwojaże-
ra. Problem ten polega na znalezieniu dla grafu prostego i spójnego
z wagami cyklu Hamiltona o możliwie najmniejszej wadze.

Przykład. Rozważmy następujące zagadnienie. Komiwojażer ma od-
wiedzić łącznie 7 miejscowości w taki sposób, by na końcu powrócić do
miejscowości, od której rozpoczyna spoją pracę. Diagram odległości
pomiędzy tymi miejscowościami przedstawia graf.

Drzewa rozpinające grafy

197

Jest to graf hamiltonowski. Spróbujmy oszacować wagi cykli Hamil-

tona w tym grafie od dołu, znajdując odpowiednie minimalne drzewo
rozpinające.

Takim drzewem jest na przykład drzewo T o wadze w(T ) = 7.

Powiedzmy, że ciąg f

...f

jest cyklem Hamiltona o najmniejszej

wadze. Wtedy f

...f

jest drzewem rozpinającym rozważanego grafu

i zachodzi nierówność

w(f

) + w(f

) + ... + w(f

) 7.

Zatem dla cyklu Hamiltona

w(f

...f

) 7 + w(f

Krawędź f

może być wybrana jako krawędź o możliwie najmniej-

szej wadze. Zachodzi zatem oszacowanie

w(f

...f

) 7 + 1 = 8.

Wynika stąd, że w danym grafie cykle Hamiltona będą miały wagę

nie mniejszą niż 8.

Pozostawiamy Czytelnikowi znalezienie cyklu o mniejszej wadze.

198

Drzewa i digrafy

9.3

Digrafy

Definicja digrafu, albo inaczej grafu skierowanego, różni się tym

od definicji grafu (nieskierowanego), że funkcja Γ przyporządkowuje
każdej krawędzi e nie zbiór {v, w} wierzchołków incydentnych z tą
krawędzią, lecz parę uporządkowaną (v, w). To, że wierzchołek v jest
pierwszym elementem pary, a w drugim elementem oznacza właśnie,
że krawędź e jest skierowana od v do w.

Dokładniej definicja ta przedstawia się następująco:

Definicja 9.17 Digrafem lub grafem skierowanym nazywać będziemy
funkcję Γ : E → V × V , gdzie V i E są dwoma rozłącznymi zbiorami
niepustymi.

Jeżeli Γ(e) = (v, w), to wierzchołek v nazywamy początkiem, zaś

wierzchołek w - końcem krawędzi e.

Definicja 9.18 Drogą w digrafie Γ nazywamy każdy ciąg e

...e

kra-

wędzi tego grafu taki, że koniec i-tej krawędzi jest początkiem i + 1-
krawędzi, gdzie i = 1, 2, ..., k − 1.

Długością drogi nazywamy liczbę krawędzi tej drogi.
Drogę e

...e

nazywamy zamkniętą, jeżeli koniec k-tej krawędzi

jest początkiem krawędzi pierwszej.

Drogę zamkniętą nazywamy cyklem, jeżeli wszystkie wierzchołki tej

drogi, oprócz pierwszego i ostatniego, które są sobie równe, różnią się
między sobą.

Również relację sąsiedztwa w przypadku digrafu rozumie się nieco

inaczej niż w przypadku grafów nieskierowanych.

Definicja 9.19 Mówimy, że wierzchołek u jest sąsiedni w stosunku do
v jeżeli istnieje krawędź od u do v.

W przypadku digrafów mogą także istnieć krawędzie skierowane

wielokrotne i pętle. Takie grafy nazywamy multigrafami skierowanymi.
W przeciwnym przypadku mówimy o digrafach lub grafach skierowa-
nych prostych.

Digrafy

199

Definicja 9.20 Dla dowolnego wierzchołka v grafu Γ : E → V × V
liczbę krawędzi, których końcem jest ten wierzchołek, nazywamy stop-
niem wejściowym v. Liczbę tę oznaczamy symbolem indeg (v).

Liczbę krawędzi, których początkiem jest v nazywamy stopniem wyj-

ściowym tego wierzchołka i oznaczamy symbolem outdeg (v).

Uwaga. Rzecz jasna, zachodzi równość

indeg (v) + outdeg (v) = deg(v).

Uwaga. Warto zwrócić uwagę na to, że drzewa są w istocie digrafami,

w szczególności, gdy określony jest korzeń tych grafów. W takim przy-
padku, wierzchołek będący rodzicem można traktować jako początek
krawędzi, a wierzchołek będący dzieckiem - jako koniec.

Dla grafów skierowanych zachodzą w wielu przypadkach twierdze-

nia analogiczne do tych, które dotyczą grafów nieskierowanych. Na
przykład zachodzi (por. [15, s. 484])

Twierdzenie 9.2 (Eulera) Niech dany będzie digraf skierowany Γ :
E → V × V . Jeśli graf ten jest spójny, jako graf nieskierowany, to
istnieje w nim droga zamknięta, do której należą wszystkie krawędzie Γ
wtedy i tylko wtedy, gdy dla dowolnego wierzchołka v tego grafu zachodzi
równość

indeg (v) = outdeg (v).

Przykład. Digrafem o powyższej własności jest na przykład poniższy
digraf

200

Drzewa i digrafy

Nietrudno w nim wskazać drogę zamkniętą.

Definicja 9.21 Digraf skończony i spójny (jako graf ) mający zamknię-
tą drogę przechodzącą przez wszystkie krawędzie, nazywać będziemy di-
grafem eulerowskim.

Istnieją też twierdzenia dla digrafów, w których rozpatruje się cykle

Hamiltona.

Definicja 9.22 Digraf nazywamy hamiltonowskim, jeśli istnieje w nim
droga zamknięta, przechodząca przez każdy wierzchołek oprócz pierw-
szego, który jest równy ostatniemu, dokładnie jeden raz.

Zachodzi twierdzenie, którego dowód jest raczej skomplikowany

(por. [16, s. 142] i [4]), będące uogólnieniem twierdzenia Diraca.

Twierdzenie 9.3 Załóżmy, że Γ : E → V × V jest digrafem mającym
tę własność, że dowolne dwa jego wierzchołki mogą być połączone drogą.
Wtedy, jeśli dla dowolnego wierzchołka v tego grafu

indeg (v)

card (V )

outdeg (v)

card (V ),

to digraf jest hamiltonowski.

Definicja 9.23 Wierzchołek v digrafu Γ, dla którego indeg (v) = 0,
nazywać będziemy źródłem tego digrafu.

Jeżeli natomiast outdeg (v) = 0 to v nazywać będziemy ujściem

digrafu Γ.

Dla digrafów z wagami można podać algorytmy, tak jak ma to miej-

sce w przypadku grafów nieskierowanych, pozwalające znaleźć długości
najkrótszych dróg z dowolnego wierzchołka do dowolnego innego wierz-
chołka - przy założeniu, że taka droga istnieje. W szczególności, można
zastosować w tym przypadku algorytm Dijkstry, pamiętając jednocze-
śnie, że w przypadku digrafów zmienia się rozumienie sąsiedztwa.

Zliczanie grafów.

Kilka wybranych problemów

Zliczanie grafów mających określone własności jest na ogół za-

daniem bardzo skomplikowanym. Jedynie w niektórych przypadkach
uzyskujemy proste wzory. W niniejszym rozdziale przedstawimy kilka
stosunkowo elementarnych, choć dość istotnych, problemów, których
rozwiązanie nie wymaga odwołania się do zaawansowanych technik
i złożonych rozważań.

◦

Rozważmy najpierw następujący problem: ile jest grafów ozna-
kowanych prostych o n wierzchołkach?

Aby odpowiedzieć na to pytanie, załóżmy, że v

, v

, ..., v

są wierz-

chołkami grafu. Rozważmy następnie wszystkie ciągi postaci

, d

, ..., d

, d

, ..., d

, d

, ..., d

, d

, ..., d

n−1,n

gdzie liczby d

, i, j ∈ {1, 2, ..., n}, i < j, są równe albo zero, jeśli wierz-

chołki v

oraz v

są połączone krawędziami, albo jeden - w przeciwnym

przypadku.

Zauważmy, że powyższy ciąg określa w sposób jednoznaczny graf

prosty o wierzchołkach v

, v

, ..., v

. Liczba elementów tego ciągu jest,

202

Zliczanie grafów. Kilka wybranych problemów

jak nietrudno zauważyć, równa

. A zatem, wszystkich takich cią-

gów i wszystkich grafów o danej własności jest tyle, ile wynosi liczba
wszystkich wariacji z powtórzeniami ze zbioru 2-elementowego po

elementów, czyli

(

)

= 2(

◦

Powyższe zadanie można nieco zmodyfikować, a mianowicie moż-
na zapytać np., ile jest grafów oznakowanych o n wierzchołkach,
bez krawędzi wielokrotnych, mogących jednak mieć pętle jedno-
krotne?

Zadanie to rozwiązuje się analogicznie do zadania poprzedniego.

Wystarczy dołączyć do ciągu liczb d

, i < j, także liczby d

, i =

1, 2, ..., n, które są równe jeden, gdy odpowiednie pętle istnieją, i zero
w przeciwnym przypadku. Tak więc wszystkich grafów o rozważanych
własnościach jest

)

= 2

n(n+1)

◦

Zastanówmy się nad następującym zagadnieniem: ile jest grafów
oznakowanych prostych o n wierzchołkach i k ¬

krawędziach?

Nietrudno zauważyć, że w tym przypadku liczba odpowiednich gra-

fów jest równa

◦

W tym punkcie zajmiemy się zagadnieniem bardziej skompliko-
wanym. Odpowiemy na pytanie o liczbę wszystkich oznakowa-
nych drzew o n wierzchołkach.

Zachodzi mianowicie następujące ([16, s. 69-72])

Twierdzenie 10.1 (Cayleya) Liczba różnych drzew oznakowanych
o n wierzchołkach jest równa

n−2

Zliczanie grafów. Kilka wybranych problemów

203

Dowód. Liczbę wszystkich drzew oznakowanych o n wierzchołkach
oznaczmy symbolem L

. Zachodzi równość

= L

(1) + L

(2) + ... + L

(n − 1),

gdzie L

(i), 1 ¬ i ¬ n − 1, oznacza liczbę drzew o n wierzchołkach,

takich że dany wierzchołek u ma stopień i.

Naszym celem jest obliczenie L

(i), a następnie L

Załóżmy, że T jest drzewem oznakowanym o n wierzchołkach, ta-

kich że deg(u) = m − 1 (na poniższym rysunku deg(u) = 4).

Poprzez usunięcie jednej z krawędzi drzewa T , która nie jest in-

cydentna z u, otrzymujemy dwa poddrzewa drzewa T . Powiedzmy, że
usuwamy krawędź lf . Wtedy l należy do poddrzewa zawierającego u,
w przeciwieństwie do wierzchołka f , który należy do drugiego poddrze-
wa. Jeżeli połączymy wierzchołek f z wierzchołkiem u, to otrzymamy
drzewo T

, dla którego deg(u) = m.

204

Zliczanie grafów. Kilka wybranych problemów

W dalszym ciągu obliczymy liczbę wszystkich par (T, T

Drzewo T może być utworzone L

sposobami. Z kolei drzewo T

powstaje z T na n − 1 − (m − 1) sposobów, gdyż wyznaczone jest ono
jednoznacznie poprzez usuniętą krawędź (w naszym przypadku lf ).
Z tego też względu liczba wszystkich par (T, T

) jest równa

(m − 1) · (n − m).

Załóżmy z kolei, że T

jest drzewem oznakowanym o n wierzchoł-

kach i takim, że dla dowolnego ustalonego wierzchołka u zachodzi
deg(u) = m. Jeżeli usunie się wierzchołek u wraz z incydentnymi z nim
krawędziami, otrzyma się m drzew T

, T

, ..., T

. Wybierzmy w dowol-

ny sposób jedną z m krawędzi łączących u z którymś z sąsiadujących
z nim wierzchołków należącym do jednego z wymienionych poddrzew,
powiedzmy poddrzewa T

. Jeśli następnie ów wierzchołek połączymy

z dowolnie wybranym wierzchołkiem należącym do któregoś z pozo-
stałych drzew, to otrzymamy drzewo T (w przypadku rozpatrywanego
już grafu T

możemy usunąć krawędź uf , łącząc f z l, i tym samym

„powrócić” do grafu T ; możemy także usunąć inną krawędź, np. ug,
i połączyć, jak to jest przedstawione niżej, g z o).

Zliczanie grafów. Kilka wybranych problemów

205

Stosując wyżej opisaną procedurę, znowu otrzymujemy pary (T, T

Drzewo T

może być wybrane na L

(m)
n

sposobów. Z kolei wierzchołek

drzewa T

sąsiadujący z u może być połączony z pozostałymi wierz-

chołkami innych poddrzew na n − 1 − n

sposobów. Ponieważ

+ n

+ ... + n

+ 1 = n,

więc wszystkich par (T, T

) jest

(m)[n − 1 − n

+ n − 1 − n

+ ... + n − 1 − n

] = L

(m)(n − 1)(m − 1).

A zatem zachodzi równość

(m)(n − 1)(m − 1) = L

(m − 1)(n − m).

Zauważmy, że L

(n − 1) = 1.

n−1

206

Zliczanie grafów. Kilka wybranych problemów

Stąd i z zależności rekurencyjnej wynika, że

(n − 2) = L

(n − 1) · (n − 1) · (n − 2),

(n − 3) =

1
2

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

1
2

(n − 1) · (n − 1)

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

itd.

Nietrudno stwierdzić, że

(m) =

n − 2

m − 1

(n − 1)

n−m−1

Stąd wynika, że

n−2

(n − 1)

n−2

(n − 1)

n−3

+ ...+

n−2
n−2

(n − 1)

= [(n − 1) + 1]

n−2

= n

n−2

co kończy dowód twierdzenia.

Wyniki zawarte w tym rozdziale zilustrujemy następującym przy-

kładem.

Przykład

(i) Wiadomo, że wszystkich grafów prostych o trzech wierzchołkach,

powiedzmy v

, v

, jest

3
2

) = 8.

Oto one

(1)

(2)

(3)

Zliczanie grafów. Kilka wybranych problemów

207

(4)

(5)

(6)

(7)

(8)

(ii) Grafów prostych oznakowanych o czterech wierzchołkach i pięciu

krawędziach jest

4
2

= 6.

(1)

(2)

(3)

(4)

(5)

(6)

208

Zliczanie grafów. Kilka wybranych problemów

(iii) Różnych drzew oznakowanych o czterech wierzchołkach, zgodnie

z twierdzeniem Cayleya, jest

4−2

= 16.

Są to drzewa

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

Zliczanie grafów. Kilka wybranych problemów

209

(13)

(14)

(15)

(16)

Spis literatury

[1] T. Batóg, Podstawy logiki, Wydawnictwo Naukowe UA, Poznań

2003.

[2] N. Biggs, Discrete Mathematics, Oxford 1993.

[3] A. Błaszczyk, S. Turek, Teoria mnogości, Wydawnictwo Nauko-

we PWN, Warszawa 2007.

[4] J. A. Bondy, U. S. R. Murty, Graph theory with applications,

Elsevier, 1976.

[5] R. C. Bose, B. Manvel, Introduction to Combinatorial Theory,

John Wiley & Sons, New York etc. 1984.

[6] V. Bryant, Aspekty kombinatoryki, Wydawnictwo Naukowo-

Techniczne, Warszawa 2007.

[7] N. Christofides, Graph Theory. An Algorithmic Approach, Aca-

demic Press, New York etc. 1975.

[8] R. Diestel, Graph Theory, Springer-Verlag, Heidelberg, New York

2005.

[9] J. Flachsmeyer, Kombinatoryka. Podstawowy wykład w ujęciu

mnogościowym, Wydawnictwo Naukowe PWN, Warszawa 1977.

[10] A. Grzegorczyk, Zarys logiki matematycznej, Wydawnictwo Na-

ukowe PWN, Warszawa 1981.

212

Spis literatury

[11] J. E. Hopcroft, J. D. Ullman, Wprowadzenie do teorii automa-

tów, języków i obliczeń, Wydawnictwo Naukowe PWN, Warszawa
2003.

[12] S. W. Jabłoński, Wstęp do matematyki dyskretnej, Wydawnictwo

Naukowe PWN, Warszawa 1991.

[13] M. Omyła, Zarys logiki, Wydawnictwa Szkolne i Pedagogiczne,

Warszawa 1995.

[14] N. Rescher, Many-valued Logic, McGraw-Hill, Inc, New York etc.

1969.

[15] K. A. Ross, Ch. R. B. Wright, Matematyka dyskretna, Wydaw-

nictwo Naukowe PWN, Warszawa 2000.

[16] R. J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Na-

ukowe PWN, Warszawa 2000.

Wyszukiwarka

Podobne podstrony:
Matematyka dyskretna pytania, matematyka dyskretna wyklady
Bobiński G Matematyka dyskretna Wykład
Matematyka Dyskretna wykład
MATEMATYKA DYSKRETNA2014(WYKŁADY)
Wykład z dnia 10.05.2008, Zajęcia, II semestr 2008, Matematyka dyskretna i logika
Matematyka dyskretna md wyklad 3
Matematyka dyskretna, md wyklad 2
Matematyka dyskretna, md wyklad 2b
Z Wykład 29.03.2008, Zajęcia, II semestr 2008, Matematyka dyskretna i logika
Matematyka dyskretna md wyklad 1
Matematyka dyskretna md wyklad 2b
Wykład 1, 1 STUDIA - Informatyka Politechnika Koszalińska, Labki, Matematyka Dyskretna i logika, MD,
Matematyka dyskretna md wyklad Nieznany
Z Wykład 27.04.2008, Zajęcia, II semestr 2008, Matematyka dyskretna i logika
matdyskr3, 2 Semestr, Matematyka dyskretna, matematyka dyskretna 2009, wyklady
matematyka dyskretna w 2 id 283 Nieznany

więcej podobnych podstron