Podstawy Systemów Dyskretnych

Wybrane elementy teorii mnogo´sci: zbiory, działania na zbiorach, iloczyn

kartezja ´nski, multizbiory

opracował Grzegorz Łabiak

Instytut In˙zynierii Elektrycznej

Uniwersytet Zielonogórski

29 wrze´snia 2015

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

1 / 25

Plan wykładu

1

Literatura

2

Okre´slanie zbiorów

3

Porównywanie zbiorów, sporz ˛

adzanie dowodów

4

Suma, iloczyn, prawa algebry zbiorów

5

Dopełnienie, ró˙znica symetryczna, pozostałe prawa rachunku zbiorów

6

Iloczyn kartezja ´nski, zbiory pot ˛egowe

7

Moc zbioru

8

Multizbiory

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

2 / 25

Literatura podstawowa

Wojciech Guzicki, Piotr Zakrzewski

Wykłady ze wst ˛epu do matematyki. Wprowadzenie do teorii mnogo´sci

Wydawnictwo Naukowe PWN, Warszawa, 2012

Wiktor Marek, Janusz Onyszkiewicz

Elementy logiki i teorii mnogo´sci w zadaniach

Wydawnictwo Naukowe PWN, Warszawa, 2006

Helena Rasiowa

Wst ˛ep do matematyki współczesnej

Wydawnictwo Naukowe PWN, Warszawa, 2013

Kenneth A. Ross, Charles R.B. Wright

Matematyka dyskretna

Wydawnictwo Naukowe PWN, Warszawa, 1999

Andrew D. Ker

Discrete Mathematics. 16 Lectures, Michaelmas Term 2010

Oxford University Computing Laboratory, Oxford, 2010

http://www.cs.ox.ac.uk/andrew.ker/docs/discretemaths-lecture-notes-mt2010.pdf

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

3 / 25

Poj˛ecie zbioru

Potocznie poprzez

zbiór

(ang. set) rozumie si ˛e kolekcj ˛e (zbiorowo´s´c)

obiektów, w której kolejno´s´c nie ma znaczenia oraz obiekty w tej kolekcji
si ˛e nie powtarzaj ˛

a

Podanie formalnej definicji jest zło˙zonym zadaniem, a nawet mówi si ˛e, ˙ze
zbiór jest poj ˛eciem pierwotnym, które si ˛e nie definiuj ˛e

Formalnie zbiorami (czyli nauk ˛

a o zbiorach) zajmuje si ˛e

Aksjomatyczna

Teoria Mnogo´sci

(ang. axiomatic set theory), która sama w sobie jest

obszerna i zło˙zona

Definicja (Zbiór)

Zbiór

jest nieuporz ˛

adkowan ˛

a kolekcj ˛

a unikalnych obiektów. Gdy x jest

w zbiorze A mówimy, ˙ze x

jest elementem (jego członkiem) zbioru A

i zapisujemy to x ∈ A. Gdy x nie jest elementem zbioru A zapisujemy to x 6∈ A

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

4 / 25

Okre´slanie zbiorów (1/3)

Poniewa˙z dwa zbiory s ˛

a równe (co si ˛e zapisuje A = B), je˙zeli maj ˛

a takie

same elementy, to zbiór mo˙zna okre´sli´c jego elementami

Mo˙zna to zrobi´c poprzez jawne wymienienie jego elementów, np.:

A = {1, 2, 3}

co oznacza, ˙ze zbiór A posiada liczby 1, 2 i 3

Mo˙zemy powiedzie´c, ˙ze 1 ∈ A, i ˙ze 4 6∈ A

Definiuj ˛

ac zbiór poprzez jawne podanie jego elementów posługujemy si ˛e

nawiasami klamrowymi

: „{” i „}”

Poniewa˙z w zbiorze nie ma ani kolejno´sci elementów ani elementów
powtarzaj ˛

acych si ˛e, definicja zbioru

{3, 2, 1, 2}

jest równowa˙zna zbiorowi A (kolejno´s´c i powtórzenia elementów widzimy
jedynie w

zapisie definicji

zbioru!)

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

5 / 25

Okre´slanie zbiorów (2/3)

Zbiory mog ˛

a posiada´c niesko ´nczon ˛

a liczb ˛e elementów i oczywi´scie nie

trzeba ich wszystkich wymienia´c

Gdy

wiadomo o co chodzi

mo˙zna posłu˙zy´c si ˛e skrótem, np. zbiór

{1, 3, 5, 7, . . .}

definiuje wszystkie liczby naturalne nieparzyste

Inny sposób to okre´slenie zbioru tzw.

konstruktorem zbioru

(ang. set

comprehension, set-builder, set abstraction), np.:

{x | pewien warunek nało˙zony na x}

jest to zbiór tych elementów, które spełniaj ˛

a

pewien warunek

Przykład:

{x | x ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9} i jest podzielne przez 4}

definiuje, de facto, zbiór {4, 8}

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

6 / 25

Okre´slanie zbiorów (3/3)

Czasami symbol „|” zast ˛epowany jest „:” (dwukropkiem), a czyta si ˛e to
„

takie, ˙ze

”

Definiuj ˛

ac konstruktor mo˙zna spotyka´c dwa skrócone zapisy. Ma to

miejsce w przypadku gdy:

1

warunek zawiera przynale˙zno´s´c do zbioru – wówczas ta cz ˛e´s´c warunku
umieszczana jest przed kresk ˛

a, np.:

E = {n ∈ N | n/2 ∈ N}

zbiór E jest zbiorem liczb całkowitych parzystych

2

chodzi o te warto´sci jakiej´s funkcji, dla których argumenty spełniaj ˛

a pewien

warunek – wówczas funkcja umieszczana jest przed kresk ˛

a, np.:

E = {2m | m ∈ N}

jest to alternatywna definicja wcze´sniejszego zbioru E

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

7 / 25

Uwagi na temat oznacze´n literowych

W teorii mnogo´sci stosuje si ˛e pewne umowne konwencje literowe, które
w ró˙znych ksi ˛

a˙zkach mog ˛

a by´c jednak odmienne

Zasadniczo

nie ma rozró˙znienia

mi ˛edzy

elementem

zbioru a

zbiorem

,

gdy˙z mo˙zliwe jest, ˙ze jeden zbiór jest

elementem

innego

zbioru

, np.:

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

jest zbiorem, którego elementami s ˛

a {1, 2} i {2, 3}, z których ka˙zdy jest

zbiorem liczb
Raczej zaleca si ˛e unikania konstrukcji, gdzie zbiór jest elementem
samego siebie
Zazwyczaj

małe litery

alfabetu rzymskiego, jak np. x i y , oznaczaj ˛

a

elementy

zbioru, a

wielkie litery

, jak np. A i B, oznaczaj ˛

a

zbiory

Do oznaczania zbiorów, których elementami s ˛

a inne zbiory (tzw.

rodziny

zbiorów

), u˙zywa si ˛e

wielkich liter kaligrafowanych

, np. A i B

Przedstawiona konwencja nie mo˙ze obejmowa´c wszystkich przypadków,
bo jak np. oznaczy´c zbiór

{1, {1}}

którego pierwszym elementem jest liczba 1, a drugim zbiór {1}, albo jak
nazwa´c zbiór zbiorów zbiorów. . .

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

8 / 25

Wybrane zbiory standardowe

Definicja (Przykłady standardowych zbiorów)

(i)

∅ = {}

zbiór pusty

(ang. empty set)

(ii)

N = {0, 1, 2, . . .}

liczby naturalne

(

całkowite nieujemne

, z zerem)

(iii)

N

+

= {

1, 2, . . .}

całkowite dodatnie

(bez zera)

(iv)

Z = {. . . , −2, −1, 0, 1, 2, . . .}

całkowite

(ang. integers)

(v)

Z

n

= {

0, 1, 2, . . . , n − 1}

całkowite modulo n

(dla n = {2, 3, 4, . . .}

(vi)

Q = {

n

d

| n ∈ Z i d ∈ N

+

}

liczby wymierne

(ang. rational num.)

(vii)

R

liczby rzeczywiste

(ang. real num.)

Zamiast N

+

(całkowite dodatnie) mo˙zna pisa´c Z

+

Niektórzy u˙zywaj ˛

a N na oznaczenie dodatnich całkowitych bez zera (tu

N

+

), a symbolu N

0

na oznaczenie naturalnych z zerem (tu N)

Czasami do oznaczenia całkowitych dodatnich (tu N

+

) stosowane jest P,

które równie˙z mo˙ze by´c stosowane do liczb pierwszych
Istnieje rozró˙znienie mi ˛edzy {} a {{}}. Pierwsze ({}) jest zbiorem pustym
bez elementów, drugie ({{}}) jest zbiorem z jednym elementem (zbiorem)

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

9 / 25

Porównywanie zbiorów

Zbiory mo˙zna porównywa´c

Definicja

1

Gdy dwa zbiory A i B maj ˛

a dokładnie takie same elementy, wówczas

mo˙zna to zapisa´c nast ˛epuj ˛

aco: A = B

2

Gdy wszystkie elementy A s ˛

a równie˙z elementami B mówimy, ˙ze A jest

podzbiorem

(ang. subset) B, co zapisujemy A ⊆ B. Alternatywnie

mo˙zemy stwierdzi´c, ˙ze A jest

zawarte

(ang. included) w B lub B jest

nadzbiorem

(ang. superset) A, co zapisuje si ˛e B ⊇ A

3

Gdy A ⊆ B i A 6= B mówimy, ˙ze A jest

podzbiorem wła´sciwym

(ang.

proper subset) B, co si ˛e zapisuje A ⊂ B lub B ⊃ A. (Wszystkie elementy
A nale˙z ˛

a do B, ale pewne elementy B nie nale˙z ˛

a do A)

Uwaga. Czasami dla zapisania, ˙ze A jest podzbiorem B stosuje si ˛e zapis
A ⊂ B, a dla oznaczenia podzbiorów wła´sciwych zapisy A ( B lub A $ B
Przykład: {2, 3} ⊂ {1, 2, 3}, N

+

⊂ N ⊂ Z, oraz dla dowolnego zbioru A

∅ ⊆ A i A ⊆ A

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

10 / 25

Sporz ˛

adzanie dowodów

Co to jest dowód? Nie ma jednoznacznej odpowiedzi, ale generalnie
chodzi o ustalenie prawdy, w czym ma pomaga´c logika

W matematyce dowody dotycz ˛

a ustalenia prawdziwo´sci zda ´n w postaci:

Je˙zeli (

pewna hipoteza

)

to (

wniosek

)

Czym jest dowód?

Dowód

jest

sekwencj ˛

a stwierdze ´n

, która rozpoczyna

si ˛e od hipotezy i ko ´nczy si ˛e wnioskiem, a ka˙zdy krok w tej sekwencji

logicznie

musi

wynika

z kroków poprzednich (jest konsekwencj ˛

a logiczn ˛

a)

Pokazane definicje mówi ˛

a jak ˛

a konstrukcj ˛e mog ˛

a przyj ˛

a´c dowody

dotycz ˛

ace zbiorów, i tak:

Je˙zeli chcemy dowie´s´c stwierdzenia „Je˙zeli (pewna hipoteza) to A ⊆ B”, to

zakładamy prawdziwo´s´c hipotezy

dla dowolnego x ∈ A i

wykazujemy

, ˙ze

wówczas x ∈ B
Je˙zeli chcemy dowie´s´c stwierdzenia „Je˙zeli (pewna hipoteza) to A = B”,
wówczas dowodzimy dwu stwierdze ´n, ˙ze zarówno 1) A ⊆ B, jak i 2) A ⊇ B.
Ten typ dowodu zwany jest

dowodem przez podwójne zawieranie

Czasami dwie połowy dowodu przez podwójne zawieranie mog ˛

a by´c

przeprowadzone w jednym kroku

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

11 / 25

Podstawowe działania na zbiorach

Definicja (Suma, iloczyn i rozł ˛

aczno´s´c zbiorów)

1

Sum ˛

a

(ang. union) zbiorów A i B, zapisywan ˛

a jako A ∪ B, jest zbiór,

którego elementy s ˛

a elementami zbioru A lub B (lub te˙z obu zbiorów):

A ∪ B = {x | x ∈ A lub x ∈ B}

2

Iloczynem

(ang. intersection) zbiorów A i B, zapisywanym jako A ∩ B, jest

zbiór, którego elementy nale˙z ˛

a zarówno do A jak i do B:

A ∩ B = {x | x ∈ A i x ∈ B}

3

Dwa zbiory A i B s ˛

a

rozł ˛

aczne

(ang. disjoint), je˙zeli A ∩ B = ∅

Przykład dla A = {0, 1, 2, 3} i E = {n ∈ N | n jest parzyste}:

A ∪ E = {0, 1, 2, 3, 4, 6, 8, . . .}
A ∩ E = {0, 2}

Je˙zeli O = {n ∈ N | n jest nieparzyste} to:

E ∪ O = N
E ∩ O = ∅ – zbiory s ˛

a rozł ˛

aczne

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

12 / 25

Prawa algebry zbiorów

Istnieje wiele równo´sci z operatorami ∪ i ∩, które s ˛

a prawdziwe dla wszystkich

zbiorów. Tego rodzaju równo´sci nazywane s ˛

a

prawami algebry zbiorów

Prawa rachunku (algebry) zbiorów

Prawa

idempotentno´sci

(ang. idempotence) dla ∪ i ∩:

A ∪ A = A

A ∩ A = A

Prawa

przemienno´sci

(ang. commutative):

A ∪ B = B ∪ A

A ∩ B = B ∩ A

Prawa

ł ˛

aczno´sci

(ang. asscoiative):

(

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

(

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

Prawo

rozdzielno´sci

(ang. distributive) sumy i iloczynu:

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

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

Prawa

zera

i

jedynki

:

A ∪ ∅ = A

A ∩ ∅ = ∅

Powy˙zsze prawa (s ˛

a symetryczne!) mo˙zna zestawi´c z prawami rachunku

arytmetycznego, zast ˛epuj ˛

ac operatory ∪ przez +, ∩ przez ∗ i ∅ przez 0.

Pytanie ciekawostka: które z praw nie jest prawdziwe w analogii do
rachunku arytmetycznego?

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

13 / 25

Uogólnienie praw ł ˛

aczno´sci dla kolekcji zbiorów (1/2)

Wnioski płyn ˛

ace z praw

ł ˛

aczno´sci

(zarówno dla ∪ jak i ∩) s ˛

a szczególnie

praktyczne, gdy˙z dzi ˛eki tym prawom w zło˙zonych wyra˙zeniach, jak np.
A ∪ B ∪ C, nie ma znaczenia jak posłu˙zymy si ˛e nawiasami, np. (A ∪ B) ∪ C
czy A ∪ (B ∪ C), wynik b ˛edzie taki sam, gdy˙z kolejno´s´c działania operatorów
na tym samym poziomie nawiasowania dla wyniku cało´sci nie ma znaczenia

Definicja (Suma i iloczyn rodziny zbiorów)

Suma rodziny zbiorów

A

1

,

A

2

,

A

2

, . . . ,

A

n

jest zbiorem, którego elementy

nale˙z ˛

a do

któregokolwiek

zbioru A

i

z rodziny:

n

[

i=1

A

i

= {

x | x ∈ A

i

dla pewnego i}

Iloczyn rodziny zbiorów

A

1

,

A

2

,

A

2

, . . . ,

A

n

jest zbiorem, którego elementy

nale˙z ˛

a do

ka˙zdego

zbioru A

i

z rodziny:

n

\

i=1

A

i

= {

x | x ∈ A

i

dla ka˙zdego i}

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

14 / 25

Uogólnienie praw ł ˛

aczno´sci na rodziny zbiorów (2/2)

Poj ˛ecie uogólnionej sumy (iloczynu) zbiorów obejmuje równie˙z

niesko ´nczon ˛

a rodzin ˛e zbiorów

∞

[

i=1

A

i

∞

\

i=1

A

i

Na mocy praw

przemienno´sci

i

idempotentno´sci

nie ma znaczenia ani

kolejno´s´c zbiorów A

i

w działaniach, ani powtórzenia zbiorów

Dzi ˛eki powy˙zszemu, sum ˛e i iloczyn zbiorów mo˙zna uogólni´c na

indeksowan ˛

a rodzin ˛e zbiorów

{A

i

| i ∈ I} (dla

zbioru indeksuj ˛

acego

I):

[

i∈I

A

i

\

i∈I

A

i

Przykładowo dla zbioru M

i

= {

i, 2i, 3i, . . .} (wszystkie krotno´sci i) mamy:

a)

T

4
i=1

M

i

= {

1, 2, 3, . . .}∩{2, 4, 6, 8, . . .}∩{3, 6, 9, 12, . . .}∩{4, 8, 12, 16, . . .} =

= {

12, 24, 36, 48, . . .} = M

12

b)

S

4
i=1

M

i

= N

+

c)

S

4
i=2

M

i

= {

2, 3, 4, 6, 8, 9, 10, 12, 14, 15, . . .}

d)

ale:

T

i∈N

+

M

i

= ∅

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

15 / 25

Ró˙znica i ró˙znica symetryczna zbiorów

Inne operacje na zbiorach dotycz ˛

ace ró˙znicy zbiorów

Definicja (Ró˙znica zbiorów)

Ró˙znica zbiorów

A i B (

dopełnienie wzgl ˛edne

zbioru B w zbiorze A, ang.

relative complement), zapisywanie jako A \ B, s ˛

a to te elementy zbioru A,

które nie nale˙z ˛

a do B:

A \ B = {x | x ∈ A i x 6∈ B}

Ró˙znica symetryczna

(ang. symmetric difference) zbiorów A i B, zapisywana

jako A ⊕ B (lub A∆B), jest to zbiór tych elementów, które nale˙z ˛

a do jednego

zbioru i nie nale˙z ˛

a do obu zbiorów A i B:

A ⊕ B = {x | (x ∈ A and x 6∈ B) lub (x ∈ B i x 6∈ A)}

Przykład. Niech A = {1, 3, 4} i B = {3, 5, 7}, wówczas:

a)

A ∪ B = {1, 3, 4, 5, 7}

b)

A ∩ B = {3}

c)

A \ B = {1, 4}

d)

A ⊕ B = {1, 4, 5, 7}

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

16 / 25

Prawa ró˙znicy zbiorów, uniwersum

Istnieje wiele praw rachunku zbiorów dotycz ˛

acych ∪, ∩, \, i ⊕. Oto niektóre:

Prawa rachunku (algebry) zbiorów

Prawa

skracania

(ang. cancellation):

A \ A = ∅

A \ ∅ = A

Prawo

inwolucji

(ang. involution):

A \ (A \ B) = A ∩ B

Prawa

de Morgana

:

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

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

Prawa

rozdzielno´sci prawostronnej

(ang. right-distributive):

(

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

(

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

Istnieje pewien szczególnie po˙zyteczny przypadek dopełnienia
wzgl ˛ednego zbioru
Je´sli w obszarze pewnego problemu, wszystkie zbiory, które mog ˛

a nas

interesowa´c, s ˛

a podzbiorami jakiego´s zbioru U , to taki zbiór U nazywa si ˛e

uniwersum

(ang. universe)

Np. zajmuj ˛

ac si ˛e liczbami naturalnymi dodatnimi uniwersum jest U = N

+

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

17 / 25

Dopełnienie zbioru

Definicja (Dopełnienie zbioru A)

Je˙zeli zbiór A ⊆ U , to ró˙znic ˛e U \ A oznaczamy symbolem A i nazywamy j ˛

a

jego

dopełnieniem

(absolutnym, ang. absolut complement). Elementami

dopełniania A s ˛

a te elementy uniwersum U , które do zbioru A nie nale˙z ˛

a:

A = {x | x 6∈ A}

Na oznaczenie dopełnienia mo˙zna spotka´c inne symbole: A

0

, A

c

Korzystaj ˛

ac z praw dla ró˙znicy zbiorów (dopełnienia wzgl ˛ednego) mo˙zna

wyprowadzi´c prawa dla dopełnienia (absolutnego):

Prawa rachunku (algebry) zbiorów dla dopełnienia

Prawo

podwójnego dopełnienia

(inwolucji):

A = A

Prawo

de Morgana

:

A ∪ B = A ∩ B

A ∩ B = A ∪ B

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

18 / 25

Iloczyn kartezja´nski (1/3)

Przedstawione dotychczas działania na zbiorach cechowały si ˛e tym, ˙ze
tworzyły nowe zbiory ale z tych elementów, które ju˙z nale˙zały wcze´sniej
do zbiorów
Elementy nowych zbiorów nie były modyfikowane, co najwy˙zej były
dodawane b ˛

ad´z usuwane z wyniku

Dwa nowe działania –

iloczyn kartezja ´nski

(ang. cartesian product) i

zbiór

pot ˛egowy

(ang. power set) – tworz ˛

a nowe elementy: pary i zbiory

Definicja (Para uporz ˛

adkowana, iloczyn kartezja ´nski)

Symbolu

(

x , y )

u˙zywamy na oznaczenie

pary uporz ˛

adkowanej

(ang.

ordered pair) składaj ˛

acej si ˛e z x i y

Pary s ˛

a

równe

, (x , y ) = (x

0

,

y

0

)

, wtedy i tylko wtedy, gdy x = x

0

i y = y

0

Je˙zeli A i B s ˛

a zbiorami, to

iloczynem kartezja ´nskim

zbiorów A i B,

oznaczanym jako A × B, jest zbiór takich par, gdzie pierwszy element
nale˙zy do A, a drugi do B w ka˙zdej mo˙zliwej kombinacji:

A × B = {(x , y ) | x ∈ A i y ∈ B}

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

19 / 25

Iloczyn kartezja´nski (2/3)

Mimo, ˙ze para uporz ˛

adkowana nie jest zbiorem, to u˙zywamy słowa

element

i mówimy, ˙ze x jest pierwszym elementem pary, a y drugim.

Słowo składnik równie˙z mo˙ze by´c stosowane
Aktualnie przyjmowana definicja teoriomnogo´sciowa pary
uporz ˛

adkowanej – wg Kazimierza Kuratowskiego (1921 r.):

(

x , y )

K

= {{

x }, {x , y }}

Przykład iloczynu kartezja ´nskiego dla A = {1, 3, 5} i B = {2, 4, 6}:

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

Iloczyn kartezja ´nskie równie˙z podlega prawom algebry. Najistotniejsze
s ˛

a prawa rozdzielno´sci:

Prawa rozdzielno´sci iloczynu kartezja ´nskiego

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

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

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

20 / 25

Iloczyn kartezja´nski (3/3)

Poj ˛ecie pary uporz ˛

adkowanej mo˙ze by´c rozszerzone do

trójek

, czy nawet

krotek

(ang. n-tuples) w ogólno´sci (x

1

,

x

2

, . . . ,

x

n

). Wówczas iloczyn

kartezja ´nski rozci ˛

aga si ˛e na iloczyny sko ´nczone:

×

n
i=1

=

A

i

Mnogi iloczyn kartezja ´nski ró˙zni si ˛e od działa ´n sumy i iloczynu zbiorów:

1)

jest działaniem sko ´nczonym – działaj ˛

acym na sko ´nczonej liczbie

argumentów

2)

nie jest działaniem ł ˛

acznym, gdy˙z A × (B × C) zawiera elementy o postaci

(

a, (b, c)), a (A × B) × C elementy o postaci ((a, b), c) – cho´c podobne, to

jednak ró˙zne

3)

nie jest działaniem przemiennym, poniewa˙z pary iloczynu A × B s ˛

a

odwróconymi parami iloczynu B × A

Mo˙zna stosowa´c zapisy uproszczone: A

2

dla A × A, A

3

dla A × A × A, itd.

W informatyce iloczyn kartezja ´nski pozwala w zgrabny sposób poł ˛

aczy´c

wiele obserwacji w jedn ˛

a obserwacj ˛e, np.:

działanie programu

obejmuje

dwa liczniki

(których warto´sci s ˛

a dodatnie) i

akumulator

(z warto´sciami

całkowitymi). Wówczas

stan

programu, w dowolnym momencie czasu,

mo˙ze reprezentowa´c element iloczynu N

0

× N

0

× Z

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

21 / 25

Zbiór pot˛egowy

Definicja (Zbiór pot ˛egowy)

Je˙zeli A jest zbiorem, wówczas

zbiorem pot ˛egowym

zbioru A, zapisywanym

jako P(A) lub 2

A

, jest zbiór

wszystkich podzbiorów

zbioru A:

P(A) = {B | B ⊆ A}

Zbiory pot ˛egowe „szybko” staj ˛

a si ˛e du˙ze i zło˙zone (wzgl ˛edem mocy

zbioru A)

Na przykład: P(∅) = {∅}, P(P(∅)) = {∅, {∅}},
P(P(P(∅))) = {∅, {∅}, {{∅}}, {∅, {∅}}}, . . .

W ogólno´sci zbiór pot ˛egowy P({1, 2, . . . , n}) składa si ˛e z 2

n

podzbiorów,

z których ka˙zdy z elementów 1, 2, . . . , n jest zawarty b ˛

ad´z wył ˛

aczony

z ka˙zdej mo˙zliwej (których jest 2

n

) kombinacji podzbioru

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

22 / 25

Moc zbioru

Definicja (Moc zbioru)

Własno´s´c zbioru A okre´slaj ˛

aca jego liczebno´s´c, zwana jest jego

moc ˛

a

(ang.

cardinality) i jest zapisywana #A lub |A| (a tak˙ze n(A), card (A), A)

Liczby okre´slaj ˛

ace moc zbioru zwane s ˛

a

liczbami kardynalnymi

(ang.

cardinal numbers) i dla zbiorów sko ´nczonych s ˛

a to liczby N (naturalne)

Moc zbioru sko ´nczonego jest po prostu liczb ˛

a jego elementów, np.:

|∅| = 0, |{1, 2, 4, 8, 16}| = 5

Matematyka dyskretna zasadniczo bardziej zajmuje si ˛e liczeniem mocy
zbiorów sko ´nczonych ni˙z niesko ´nczonych

Poj ˛ecie mocy zbiorów mo˙ze by´c rozci ˛

agni ˛ete na

zbiory niesko ´nczone

,

gdzie moce ró˙znych zbiorów niesko ´nczonych mog ˛

a by´c ró˙zne, tzn. jeden

zbiór niesko ´nczony mo˙ze by´c „wi ˛ekszy” od drugiego

Przykładem zbioru nieko ´nczonego jest zbiór liczb naturalnych N, którego
liczb ˛e kardynaln ˛

a odpowiadaj ˛

ac ˛

a jego mocy oznacza si ˛e hebrajsk ˛

a liter ˛

a

alef z indeksem 0:

ℵ

0

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

23 / 25

Multizbiory (wielozbiory) – informacje wprowadzaj ˛

ace

W informatyce cz ˛esto przydatne s ˛

a nieuporz ˛

adkowane kolekcje obiektów,

gdzie dopuszczone s ˛

a powtórzenia

Struktury takie nazywane s ˛

a

multizbiorami

(ang. bags, pol. torby)

Multizbiory mo˙zna przedstawia´c tak jak zwykłe zbiory, np. {1,2,3,3}, lub
mo˙zna stosowa´c nawiasy-„torby”:

H1, 2, 3, 3I

W systemie L

A

TEXnawiasy „

H” i „I” uzyskuje si ˛

e poleceniami \Lbags

i \Rbags (a tak˙ze \lbags i \rbags) z pakietu stmaryrd

Np. w multizbiorze

H1, 2, 3, 3I

element 1 i 2 wyst ˛epuj ˛

a raz, element 3 dwa razy. Jest on równowa˙zny

multizbiorowi

H3, 1, 2, 3I, a nie jest H1, 2, 3I

Multizbiorów nie mo˙zna okre´sli´c przez prost ˛

a przynale˙zno´s´c elementu,

gdy˙z istotna jest równie˙z

ilo´s´c wyst ˛

apie ´n

elementu w multizbiorze

Prostym sposobem definiowania multizbioru jest posłu˙zenie si ˛e

funkcj ˛

a

zliczaj ˛

ac ˛

a

ilo´s´c wyst ˛

apie ´n ka˙zdego elementu

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

24 / 25

Multizbiory – podstawowe operacje na multizbiorach

Wi ˛ekszo´s´c operacji na zbiorach mo˙ze by´c zdefiniowana w odniesieniu do
multizbiorów:

suma

dodaje liczb ˛e wyst ˛

apie ´n ka˙zdego elementu, np.:

H1, 2, 3, 3I ∪ H2, 3, 4I = H1, 2, 2, 3, 3, 3, 4I

iloczyn

zwraca minimaln ˛

a ilo´s´c wyst ˛

apie ´n ka˙zdego z elementów, np.:

H1, 2, 3, 3I ∩ H2, 3, 4I = H2, 3I

ró˙znica

odejmuje wyst ˛

apienia elementów (bez elementów ujemnych), np.:

H1, 2, 3, 3I \ H2, 3, 4I = H1, 3I

Pewne prawa rachunku zbiorów równie˙z zachodz ˛

a dla multizbiorów:

przykładowo zachodz ˛

a:

przemienno´s´c i ł ˛

aczno´s´c dla sumy i iloczynu

nie zachodzi idempotentno´s´c, gdy˙z np.

H1I ∪ H1I = H1, 1I

a nie

H1I

nie s ˛

a prawdziwe niektóre prawa rozdzielno´sci, np.:

H1I ∩ (H1I ∪ H1I) = H1I

a nie

H1, 1I

Multizbiory rzadko s ˛

a wzmiankowane w literaturze matematycznej, ale s ˛

a

przydatne w informatyce, zwłaszcza w odniesieniu do teorii baz danych

opracował Grzegorz Łabiak (IIE)

Podstawy Systemów Dyskretnych

29 wrze´snia 2015

25 / 25