Matematyka dyskretna 2002 01 Oznaczenia

Matematyka Dyskretna

Andrzej Szepietowski

25 czerwca 2002 roku

Rozdział 1

Oznaczenia

W tym rozdziale przedstawimy podstawowe oznacznia.

oznacza kwantyfikator ogólny "dla ka˙zdego".

oznacza kwantyfikator szczegółowy

"istnieje".

1.1

Sumy

Maj¸ac dany sko ´nczony ci¸ag

,...

, sum¸e jego elementów zapisujemy jako

Niezbyt formalnie mo˙zemy to zapisa´c

Jako przykład zastosujmy symbol sumy do zapisu wzoru na sum˛e ci¸agu arytmetycznego).

(1.1)

oraz wzoru na sum˛e ci¸agu geometrycznego).

%$'&

(

,+ .-

(1.2)

(wzór (1.2) jest słuszny dla ka˙zdego

&21

)

B¸edziemy te˙z u˙zywa´c zapisu typu

476

98:9;.9<:=6

Rozdział 1. Oznaczenia

W tym przypadku zbiór indeksów okre´slony jest za pomoc¸a warunku pod znakiem sumy.
Warunek okre´slaj¸acy indeksy, po których nale˙zy sumowa´c mo˙ze by´c bardziej skompliko-
wany, na przykład

;

Stosowa´c b¸edziemy tak˙ze zapis

oznaczaj¸acy sum¸e tych elementów

, których indeksy nale˙z¸a do sko ´nczonego zbioru

indeksów

. Na przykład, je˙zeli

///

, to

8:<

Mo˙zemy te˙z sumowa´c ci ˛

agi, których elementy zale˙z ˛

a od dwóch indeksów,

!"#

$ &%#

Za pomoc ˛

a podwójnej sumy mo˙zemy na przykład przedstawi ´c uogólnione prawo roz-

dzielno´sci mno˙zenia wzgl˛edem dodawania:

()

4+*

-,.

()

40/21

&%4

(1.3)

a tak˙ze wzór na podnoszenie sumy do kwadratu:

()

40*

-5

4+*

(1.4)

1.2

Iloczyny

Aby zapisa´c iloczyn elementów ci¸agu

,...

, stosujemy zapis

Znów niezbyt formalnie mo˙zemy to zapisa´c jako

1.3. Zbiory

1.3

Zbiory

oznacza zbiór pusty, który nie zawiera ˙zadnych elementów.

oznacza zbiór liczb naturalnych

oznacza zbiór liczb całkowitych.

oznacza zbiór liczb wymiernych.

oznacza zbiór liczb rzeczywistych.

oznacza, ˙ze elment

nale˙zy do zbioru

, ˙ze elment

nie nale˙zy do

zbioru

. Najprostszy sposób zdefiniowania zbioru polega na wypisaniu jego elementów

w nawiasach klamrowych. Na przykład zbiór

zawiera elementy 1,2,3. Inny spo-

sób definiowania zbioru polega na podaniu własno´sci, któr¸a spełniaj¸a elementy zbioru.
Na przykład

oznacza zbiór liczb naturalnych wi¸ekszych od 3 i

mniejszych od 7.

oznacza moc zbioru

, czyli liczb¸e jego elementów.

oznacza sum¸e zbiorów, czyli zbiór, który zawiera elementy, które nale˙z ˛

a do

lub

A zatem suma

zawiera wszystkie elementy zbioru

i wszystkie elementy zbioru

oznacza iloczyn lub przekrój zbiorów, czyli zbiór, który zawiera te elementy,

które nale˙z¸a do obu zbiorów naraz.

oznacza ró˙znic¸e zbiorów, czyli zbiór, który zawiera te elementy, które nale˙z¸a

i nie nale˙z¸a do

Przykład 1.1 Dla

mamy:

oznacza, ˙ze zbior

zawiera si¸e w zbiorze

, to znaczy wszystkie elementy zbioru

nale˙z¸a do zbioru

Dwa zbiory s¸a równe je˙zeli zawieraj¸a te same elementy, lub inaczej

wtedy i tylko

wtedy gdy

Jak wida´c kolejno´s´c elementów w zapisie zbioru nie ma znaczenia. I tak na przykład

. Taki zbiór dwuelementowy nazywamy czasami par¸a nieuporz¸adkowan¸a.

W poni˙zszym lemacie zebrano podstawowe własno´sci operacji sumy i iloczynu zbio-

rów.

Rozdział 1. Oznaczenia

Lemat 1.2

(przemienno´s´c sumy).

(przemienno´s´c iloczynu).

(ł¸aczno´s´c sumy).

(ł¸aczno´s´c iloczynu).

(rozdzielno´s´c sumy wzgl¸edem iloczynu).

(rozdzielno´s´c iloczynu wzgl¸edem sumy).

1.4

Ró˙znica symetryczna zbiorów

oznacza ró˙znic¸e symetryczn¸a zbiorów, która zawiera elementy nale˙z¸ace tylko do

jednego z dwóch zbiorów:

Przykład 1.3

W poni˙zszym lemacie zebrano podstawowe własno´sci ró˙znicy symetrycznej zbiorów.

Lemat 1.4

(przemienno´s´c).

(ł¸aczno´s´c).

(rozdzielno´s´c wzgl¸edem iloczynu).

Je˙zeli

, to

Dowód:

Udowodnimy, tylko dwie to˙zsamo´sci, dowód pozostałych pozostawiamy czytelnikowi

jako ´cwiczenie.

Aby pokaza´c, ˙ze ró˙znica symetryczna jest ł ˛

aczna wystarczy zauwa˙zy ´c, ˙ze zbiór

lub

zawiera te elementy, które nale˙z¸a do nieparzystej liczby zbiorów,

czyli te, które nale˙z¸a tylko do

, plus te, które nale˙z¸a tylko do

, plus te, które nale˙z¸a

tylko do

, plus te, które nale˙z¸a do przekroju

Udowodnimy teraz ostatni ˛

a implikacj˛e. Je˙zeli

, to

1.5. Iloczyn kartezja ´nski

Twierdzenie 1.5 Ró˙znica symetryczna

zbiorów:

zawiera elementy, które nale˙z¸a do nieparzystej liczby spo´sród zbiorów

Dowód przez indukcj¸e ze wzgl¸edu na

. Twierdzenie jest oczywiste dla

lub

. Załó˙zmy teraz, ˙ze jest ono prawdziwe dla

i rozpatrzmy:

Zbiór ten zawiera te elementy, które nale˙z¸a do

i nie nale˙z¸a do

oraz te, które nie nale˙z¸a do

i nale˙z¸a do

. W pierwszym przypad-

ku s¸a to elementy, które nie nale˙z¸a do

i na mocy zało˙zenia indukcyjnego nale˙z¸a

do jakiej´s nieparzystej liczby zbiorów spo´sród

. W drugim przypadku s¸a to

elementy, które nale˙z¸a do

, a tak˙ze do pewnej parzystej liczby zbiorów spo´sród

. Razem mamy wszystkie elementy nale˙z¸ace do nieparzystej liczby zbiorów

spo´sród

1.5

Iloczyn kartezja ´nski

Para uporz¸adkowana jest to dwuelementowy ci ˛

. Mamy

wtedy i

tylko wtedy gdy

oraz

. Dopuszczalne jest tak˙ze

oznacza iloczyn kartezja´nski zbiorów

. Jest to zbiór wszystkich uporz¸adkowanych

par

, w których

. Inaczej

Przykład 1.6 Dla

mamy

Mo˙zna łatwo wykaza´c, ˙ze

1.6

Rodzina zbiorów

Czasami b˛edziemy mieli do czynienia ze zbiorem, którego elementami s ˛

a zbiory. Przez

lub

b˛edziemy oznacza´c zbiór wszystkich podzbiorów zbioru

Przykład 1.7 Dla

Rozdział 1. Oznaczenia

Zbiór zbiorów nazywamy czasami rodzin¸a zbiorów. Na przykład

;

jest rodzin¸a zawieraj¸ac¸a cztery zbiory

;

, s¸a to elementy zbioru

. Mo˙zemy

te˙z zapisa´c

Mo˙zemy sumowa´c zbiory z rodziny. Suma

zawiera te elementy, które nale˙z¸a do którego´s ze zbiorów

, ... ,

, czyli

Inaczej mo˙zemy to zapisa´c:

B¸edziemy te˙z u˙zywa´c zapisu

na oznaczenie sumy wszystkich zbiorów

, których indeksy nale˙z¸a do zbioru

. Zacho-

dzi wtedy

Zbiór indeksów sumowania mo˙ze by´c okre´slony za pomoc¸a warunku.

-5

;

Mo˙zemy te˙z bra´c przekroje zbiorów z rodziny. Przekrój

zawiera te elementy, które nale˙z¸a do wszystkich zbiorów

, ... ,

, czyli

Inaczej mo˙zemy to zapisa´c:

1.7. Słowa

B¸edziemy te˙z u˙zywa´c zapisu

na oznaczenie przekroju wszystich zbiorów

, których indeksy nale˙z¸a do zbioru

. Za-

chodzi wtedy

Zbiór indeksów przekroju mo˙ze by´c okre´slony za pomoc¸a warunku.

57 "5

;

Przykład 1.8 We´zmy rodzin¸e zło˙zon¸a z trzech zbiorów

///

Przykład 1.9 Niech

////

b¸edzie zbiorem indeksów. Dla ka˙z-

dego

okre´slamy zbór

. Mamy:

////

-5

1.7

Słowa

Słowa s ˛

a to ci ˛

agi liter lub symboli z jakiego´s sko´nczonego zbioru

. Zbiór

nazywamy

wtedy alfabetem. Zbiór wszystkich słów nad alfabetem

oznaczamy przez

W´sród słów wyró˙zniamy słowo puste

, które nie zawiera ˙zadnych liter.

Przykład 1.10 Na przykład, je˙zeli

, to

zawiera słowo puste

, dwa słowa

jednoliterowe

, cztery słowa dwuliterowe

, osiem słów trzyliterowych

, i tak dalej.

Długo´s´c słowa

jest to liczba jego liter, b˛edziemy j ˛

a oznacza´c przez

. Dłu-

go´s´c słowa pustego

. Zbiór wszystkich słów długo´sci

nad alfabetem

oznacza-

my przez

Dla słów mo˙zemy okre´sli´c operacj˛e konkatenacji, lub składania słów. Konkatenacja lub
zło˙zenie dwóch słów

, oznaczana przez

, jest to sklejenie słów

. Do słowa

dopisujemy na ko ´ncu słowo

. Dla dowolnego słowa

zachodzi

Rozdział 1. Oznaczenia

Przykład 1.11 Konkatenacja słów

to sówo

Słowo

jest prefiksem lub przedrostkiem słowa

, je˙zeli istnieje takie słowo

, ˙ze

. Podobnie, słowo

jest sufiksem lub przyrostkiem słowa

, je˙zeli istnieje takie

słowo

, ˙ze

Przykład 1.12 Na przykład

jest prefiksem słowa

, a słowo

jest sufiksem

słowa

. Słowo puste jest prefixem i sufiksem dowolnego słowa

. Ka˙zde słowo

jest swoim własnym prefiksem i sufiksem.

Zwykle alfabet jest zbiorem uporz ˛

adkowanym, lub mówi ˛

ac inaczej mamy pewn ˛

a ko-

lejno´s´c liter w alfabecie. Na przykład w zbiorze

litera

stoi przed

. Mo˙zemy

te˙z wtedy uporz ˛

adkowa´c zbiór słów nad alfabetem

Jeden porz ˛

adek nazywa si˛e porz ˛

adkiem leksykograficznym. Jest to porz ˛

adek słów w

słownikach. Aby porówna´c dwa słowa

, szukamy pierwszej pozycji, na której te

dwa słowa si˛e ró˙zni ˛

a. Słowo, które ma na tej pozycji wcze´sniejsz ˛

a liter˛e, jest wcze´sniejsze

w porz ˛

adku leksykograficznym. Je˙zeli takiej pozycji nie ma, to albo

, albo jedno

ze słów jest prefiksem drugiego, wtedy wcze´sniejszy w porz ˛

adku leksykograficznym jest

prefiks.

Przykład 1.13 W porz ˛

adku leksykograficznym słowo

jest wcze´sniejsze od słowa

a to jest wcze´sniejsze od

Porz ˛

adek leksykograficzny jest wygodny, je˙zeli zbiór słów jest sko ´nczony. Zauwa˙zmy, ˙ze

w zbiorze wszystkich słów

niesko´nczenie wiele słów (wszystkie słowa zło˙zone

tylko z litery

) poprzedza słowo

. Dlatego czasami stosuje si˛e inny porz ˛

adek, tak zwany

porz ˛

adek kanoniczny.

Słowo

poprzedza słowo

w porz ˛

adku kanonicznym, je˙zeli:

albo

poprzedza

w porz ˛

adku leksykograficznym.

Przykład 1.14 Pocz ˛

atkowe słowa zbioru

uporz ˛

adkowane według porz ˛

adku kano-

nicznego to:

1.8

Zaokr¸aglenia

Wprowad´zmy dwa oznaczenia na zaokr¸aglenie liczby rzeczywistej. Dla dowolnej liczby
rzeczywistej

oznacza zaokr¸aglenie

w gór¸e do najbli˙zszej liczby całkowitej.

oznacza zaokr¸aglenie

w dół do najbli˙zszej liczby całkowitej.

Zaokr ˛

aglenie

nazywamy sufitem z

, a zaokr ˛

aglenie

nazywamy podłog ˛

a z

1.9. Przedrostki

Przykład 1.15

1.9

Przedrostki

W przypadku bardzo du˙zych lub bardzo małych warto´sci u˙zywa si¸e czasami jednostek
miar b¸ed¸acych wielokrotno´sciami lub podwielokrotno´sciami podstawowych jednostek.
Takie jednostki wyra˙za si¸e przez dodanie do nazwy jednostki odpowiedniego przedrostka,
a do oznaczenia tej jednostki dodaje si¸e oznaczenie przedrostka. W nast¸epuj¸acej tabeli
zebrano te przedrostki.

Przedrostek

Oznaczenie

Wielokrotno´s´c

exa

peta

tera

giga

mega

kilo

hekto

deka

Przedrostek

Oznaczenie

Podwielokrotno´s´c

decy

centy

mili

mikro

nano

piko

femto

atto

Przykładami tak utworzonych jednostek s¸a: centymetr (cm), milimetr (mm), hehtopa-

skal, hektolitr, kilogram (kg), kilowat (kW). Do mierzenia pr¸edko´sci (zegara) procesora
u˙zywa si¸e megahertzów. Jeden megahertz (MHz) to jednostka cz¸esto´sci równa miliono-
wi impulsów na sekund¸e. Kilobajtów, megabajtów i gigabajtów u˙zywa si¸e do mierzenia
liczby komórek pami¸eci. Cz¸esto przyjmuje si¸e, ˙ze kilobajt ma

bajtów, megabajt

bajtów, a gigabajt

bajtów.

1.10

Notacja asymptotyczna

W analizie jakiego´s algorytmu (programu) wa˙zne jest oszacowanie jego czasu działania.
Jako przykład we´zmy algorytm sortowania b ˛

abelkowego, który ustawia elementy ci ˛

agu

wej´sciowego w porz ˛

adku niemalej ˛

acym.

Rozdział 1. Oznaczenia

Algorytm sortowania b ˛

abelkowego.

Aby posortowa´c ci ˛

ag długo´sci :

(1) wykonujemy co nast˛epuje

razy:

(1a) wskazujemy na pierwszy element,

(1b) wykonujemy co nast˛epuje

razy:

porównujemy wskazany element z elementem nast˛epnym,

je˙zeli porównane elementy s ˛

a w niewła´sciwej kolejno´sci, to zamieniamy je

miejscami,

wskazujemy na nast˛epny element.

W poni˙zszej tabeli zilustrowano zastosowanie algorytmu dla ci ˛

agu

Kolejne wiersze przedstawiaj ˛

a ci ˛

ag po kolejnych porównaniach. Element aktualnie wska-

zany jest zaznaczony daszkiem.

Poprawno´s´c powy˙zszego algorytmu wynika z faktu, ˙ze po pierwszym wykonaniu ze-

wn˛etrznej p˛etli (1) najwi˛ekszy element ci ˛

agu znajdzie si˛e na ko ´ncu, po drugim wykonaniu

p˛etli drugi najwi˛ekszy element ci ˛

agu znajdzie si˛e na przedostatniej pozycji, i tak dalej. Po

ka˙zdym kolejnym wykonaniu p˛etli (1) kolejny najwi˛ekszy element znajdzie swoj ˛

a wła-

´sciw ˛

a pozycj˛e.

Czas działania algorytmu zale˙zy od

— liczby elementów w ci ˛

agu. P˛etla zewn˛etrzna

(1) jest wykowywana

razy. W ka˙zdej iteracji p˛etli zewn˛etrznej p˛etla wewn˛etrzna (1b)

równie˙z jest wykonywana

razy. W ka˙zdym kolejnym wykonaniu p˛etli wewn˛etrznej

algorytm wykonuje kilka kroków. Tak wi˛ec, aby posortowa ´c ci ˛

ag długo´sci

algorytm w

sumie wykonuje

kroków, gdzie

jest pewn ˛

a stał ˛

Czas pracy powy˙zszego algorytmu został oszacowany z dokładno´sci ˛

a do stałej. Jest

to powszechna praktyka i b˛edziemy tak post˛epowa´c w tej ksi ˛

a˙zce.

Do szacowania czasu pracy algorytmu (jego zło˙zono´sci czasowej) i do porównywania

algorytmów pod wzgl˛edem czasu działania b˛edziemy u˙zywa ´c notacji asymptotycznej.

Niech

b˛ed ˛

a dwiema funkcjami okre´slonymi na zbiorze liczb naturalnych o war-

to´sciach w zbiorze dodatnich liczb rzeczywistych

Wtedy:

1.10. Notacja asymptotyczna

, je˙zeli istnieje dodatnia stała

taka, ˙ze

dla prawie wszystkich

, to znaczy istnieje

, takie, ˙ze

dla

ka˙zdego

. W takim przypadku mówimy, ˙ze funkcja

jest O du˙ze od

, je˙zeli

. W takim przypadku mówimy, ˙ze funk-

cja

jest o małe od

, je˙zeli istnieje dodatnia stała

taka, ˙ze

dla

prawie wszystkich

. W takim przypadku mówimy, ˙ze funkcja

jest Omega

du˙ze od

, je˙zeli istniej ˛

a dwie dodatnie stałe

takie, ˙ze

dla prawie wszystkich

. W takim przypadku mówimy, ˙ze

funkcja

jest Theta du˙ze od

Je˙zeli

, to mówimy, ˙ze funkcja

ogranicza z góry funkcj˛e

dokładno´sci ˛

a do stałej), albo, ˙ze rz ˛

ad funkcji

jest nie wi˛ekszy od rz˛edu funkcji

Przykład 1.16

Czas działania algorytmu sortowania b ˛

abelkowego jest

B˛edziemy dopuszcza´c notacj˛e asymptotyczn ˛

a tak˙ze wobec funkcji, które s ˛

a dodatnie

dla prawie wszystkich liczb naturalnych. Na przykład

Je˙zeli

, to mówimy, ˙ze

jest ni˙zszego rz˛edu ni˙z

Przykład 1.17

Je˙zeli

, to

s ˛

a tego samego rz˛edu, czyli

oraz

Przykład 1.18

Rozdział 1. Oznaczenia

Nast˛epuj ˛

acy lemat jest bardzo u˙zyteczny przy szacowaniu asymptotycznym. Jego do-

wód zostawiamy jako ´cwiczenie.

Lemat 1.19 Je˙zeli granica

istnieje i jest wła´sciwa (nie jest równa

), to

Wniosek 1.20 Je˙zeli

, to

Nast˛epuj ˛

acy przykład pokazuje, ˙ze oszacowanie asymptotyczne mo˙ze by ´c zawodne.

Przykład 1.21 We´zmy dwie funkcje

oraz

. Mamy

, ale

dla wszystkich

, czyli dla wszystkich liczb mniejszych

od liczby atomów w naszej galaktyce (porównaj podrozdział du˙ze liczby w rozdziale o
arytmetyce).

Z drugiej jednak strony oszacowanie asymptotyczne wystarczy do naszych celów i

jest łatwiejsze do uzyskania.

Przykład 1.22 Rozwa˙zmy trzy algorytmy: pierwszy działaj ˛

acy w czasie

drugi w czasie

i trzeci w czasie

. Funkcje te okre´slaj ˛

a czas

działania na pewnym konkretnym komputerze. Niech

oznazczaj ˛

a długo´sci

wej´s´c, dla których algorytmy daj ˛

a odpowied´z w ci ˛

agu jednej sekundy, to znaczy

#:(

Przypu´s´cmy teraz, ˙ze mamy 1000 razy szybszy komputer i pytamy jakie wej´scia teraz

mog ˛

a by´c policzone przez te algorytmy w ci ˛

agu jednej sekundy.

Dla pierwszego algorytmu działaj ˛

acego w czasie liniowym mo˙zemy teraz oblicza´c

1000 razy dłu˙zsze dane wej´sciowe, poniewa˙z

. Dla drugie-

go algorytmu działaj ˛

acego w czasie sze´sciennym mo˙zemy teraz oblicza´c 10 razy dłu˙zsze

dane wej´sciowe, poniewa˙z

. Dla trzeciego algorytmu działaj ˛

cego w czasie wykładniczym mo˙zemy teraz oblicza´c tylko dane wej´sciowe o 10 dłu˙zsze,
poniewa˙z

1.11

Zadania

1. Oblicz

dla

2. Oblicz

3. Oblicz

;

4. Niech

. Oblicz

5. Niech

b¸edzie zbiorem indeksów. Dla ka˙zdego

okre´slamy

zbór

. Oblicz

oraz

;

1.11. Zadania

6. Niech

. Wypisz elementy

oraz

7. Niech

b¸edzie zbiorem indeksów. Dla ka˙zdego

okre´slamy

zbór

oraz

dzieli

. Oblicz

oraz

8. Uporz ˛

adkuj nast˛epuj ˛

acy zbiór słów [Fragment wiersza Ptasie radio Juliana Tu-

wima] według porz ˛

adku leksykograficznego i kanonicznego: słowik, wróbel, kos,

jaskółka, kogut, dzi˛ecioł, gil, kukułka, szczygieł, sowa, kruk, czubatka, drozd, siko-
ra i dzierlatka, kaczka, g ˛

aska, jemiołuszka, dudek, trznadel, po´smieciuszka, wilga,

zi˛eba, bocian, szpak.

9. Udowodnij wzór (1.1) na sum˛e ci ˛

agu arytmetycznego.

10. Udowodnij wzór (1.2) na sum˛e ci ˛

agu geometrycznego.

11. Udowodnij wzór (1.3).

12. Udowodnij wzór (1.4).

13. Udowodnij lemat 1.19,

14. Udowodnij zale˙zno´sci z przykładów 1.16, 1.17, 1.18,