Matematyka dyskretna

Oznaczenia

Andrzej Szepietowski

W tym rozdziale przedstawimy podstawowe oznacznia.

∀ oznacza kwantyfikator ogólny ”dla każdego”. ∃ oznacza kwantyfikator szczegó lowy

”istnieje”.

1

Sumy i iloczyny

Maj¸ac dany skończony ci¸ag a1, a2,... ak, sum¸e jego elementów zapisujemy jako k

X ai

i=1

Niezbyt formalnie możemy zapisać

k

X ai = a1 + a2 + ··· + ak.

i=1

Na przyk lad

k

X

(k + 1)k

i = 1 + 2 + · · · + k =

2

i=1

(suma ci¸agu arytmetycznego). Podobnie dla każdego x 6= 1 mamy

k

X

xk+1 − 1

xi = 1 + x + x2 + · · · + xk =

x − 1

i=0

(suma ci¸agu geometrycznego). B¸edziemy też używać zapisu typu

X ai = a1 + a2 + a3 + a4 + a5 + a6.

1≤i≤6

W tym przypadku zbiór indeksów określony jest za pomoc¸a warunku pod znakiem sumy.

Warunek określaj¸acy indeksy, po których należy sumować może być bardziej skomplikowany, na przyk lad

X ai = a2 + a4 + a6.

1≤i≤6

i parzyste

1

Stosować b¸edziemy także zapis

X ai

i∈I

oznaczaj¸acy sum¸e tych elementów ai, których indeksy należ¸a do skończonego zbioru indeksów I. Na przyk lad, jeżeli I = {1, 3, 5, 7}, to

X ai = a1 + a3 + a5 + a7.

i∈I

Aby zapisać iloczyn elementów ci¸agu a1, a2,... ak, stosujemy zapis k

Y ai.

i=1

Znów niezbyt formalnie możemy to zapisać jako

k

Y ai = a1 · a2 · ··· · ak.

i=1

2

Zbiory

∅ oznacza zbiór pusty, który nie zawiera żadnych elementów. IN oznacza zbiór liczb naturalnych IN = {0, 1, 2, 3, . . .}

a ∈ A oznacza, że elment a należy do zbioru A, a /

∈ A, że elment a nie należy do zbioru A.

Najprostszy sposób zdefiniowania zbioru polega na wypisaniu jego elementów w nawiasach klamrowych. Na przyk lad zbiór {1, 2, 3} zawiera elementy 1,2,3. Inny sposób definiowania zbioru polega na podaniu w lasności, któr¸a spe lniaj¸a elementy zbioru. Na przyk lad {x | x ∈

IN, 3 < x < 7} oznacza zbiór liczb naturalnych wi¸ekszych od 3 i mniejszych od 7.

|A| oznacza moc zbioru lub inaczej liczb¸e elementów tego zbioru.

|{3, 6, 9}| = 3,

|∅| = 0.

A ∪ B oznacza sum¸e zbiorów, czyli zbiór, który zawiera wszystkie elementy zbioru A i wszystkie elementy zbioru B.

{1, 2, 4} ∪ {1, 4, 6} = {1, 2, 4, 6}.

A ∩ B oznacza iloczyn lub przekrój zbiorów, czyli zbiór, który zawiera te elementy, które należ¸a do obu zbiorów naraz.

{1, 2, 4} ∩ {1, 4, 6} = {1, 4}.

A − B oznacza różnic¸e, czyli zbiór, który zawiera te elementy, które należ¸a do A i nie należ¸a do B.

{1, 2, 4} − {1, 4, 6} = {2}.

2

A ⊕ B oznacza różnic¸e symetryczn¸a, która zawiera elementy należ¸ace tylko do jednego z dwóch zbiorów. A ⊕ B = (A − B) ∪ (B − A).

{1, 2, 4} ⊕ {1, 4, 6} = {2, 6}.

A ⊆ B oznacza, że zbior A zawiera si¸e w zbiorze B, to znaczy wszystkie elementy zbioru A należ¸a do zbioru B.

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

Dwa zbiory s¸a równe jeżeli zawieraj¸a te same elementy, lub inaczej A = B wtedy i tylko wtedy gdy A ⊆ B i B ⊆ A.

{1, 4, 2, 3} = {4, 1, 3, 2}.

Jak widać kolejność elementów w zapisie zbioru nie ma znaczenia. I tak na przyk lad {1, 2} =

{2, 1}. Taki zbior dwuelementowy nazywamy czasami par¸a nieuporz¸adkowan¸a.

Kolejność elemnetów jest istotna w parze uporz¸adkowanej, któr¸a oznaczamy przez (x, y).

Mamy (x, y) = (u, v) wtedy i tylko wtedy gdy x = u oraz y = v. Dopuszczalne jest także x = y. Para uporz¸adkowana jest ci¸agiem dwuelementowym.

A×B oznacza iloczyn kartezjański zbiorów A i B. Jest to zbiór wszystkich uporz¸adkowanych par (a, b), w których a ∈ A i b ∈ B. Inaczej

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

Dla A = {1, 3, 5} i B = {3, 4} mamy

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

Powinno być oczywiste, że

|A × B| = |A| · |B|.

3

Rodzina zbiorów

Zbiór zbiorów nazywamy czasami rodzin¸a zbiorów. Na przyk lad A = {A1, A2, A3, A4} jest rodzin¸a zawieraj¸ac¸a cztery zbiory A1, A2, A3 i A4, s¸a to elementy zbioru A. Możemy też zapisać A = {Ai | 1 ≤ i ≤ 4}.

Możemy sumować zbiory z rodziny. Suma

k

[ Ai

i=1

zawiera te elementy, które należ¸a do któregoś ze zbiorów A1, A2, ... ,Ak, czyli k

[ Ai = {x | ∃i 1 ≤ i ≤ k; x ∈ Ai}.

i=1

3

Inaczej możemy to zapisać:

k

[ Ai = A1 ∪ A2 ∪ ... ∪ Ak

i=1

B¸edziemy też używać zapisu

[ Ai

i∈I

na oznaczenie sumy wszystkich zbiorów Ai, których indeksy należ¸a do zbioru I. Zachodzi wtedy

[ Ai = {x | ∃i∈I x ∈ Ai}.

i∈I

Zbiór indeksów sumowania może być określony za pomoc¸a warunku.

[ Ai = A2 ∪ A3 ∪ A4 ∪ A5.

1<i<6

Możemy też brać przekroje zbiorów z rodziny. Przekrój

k

\ Ai

i=1

zawiera te elementy, które należ¸a do wszystkich zbiorów A1, A2, ... ,Ak, czyli k

\ Ai = {x | ∀i 1 ≤ i ≤ k; x ∈ Ai}.

i=1

Inaczej możemy to zapisać:

k

\ Ai = A1 ∩ A2 ∩ ... ∩ Ak

i=1

B¸edziemy też używać zapisu

\ Ai

i∈I

na oznaczenie przekroju wszystich zbiorów Ai, których indeksy należ¸a do zbioru I. Zachodzi wtedy

\ Ai = {x | ∀i∈I x ∈ Ai}.

i∈I

Zbiór indeksów przekroju może być określony za pomoc¸a warunku.

\ Ai = A2 ∩ A3 ∩ A4 ∩ A5.

1<i<6

Przyk lad 1.

Weźmy rodzin¸e z lożon¸a z trzech zbiorów A1 = {4, 6, 8}, A2 = {4, 5, 6}, A3 = {4, 5, 8, 9},

3

[

3

\

Ai = {4, 5, 6, 8, 9}

Ai = {4}

i=1

i=1

4

Przyk lad 2. Niech I = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} b¸edzie zbiorem indeksów. Dla każdego i ∈ I określamy zbór Ai = {x ∈ N | 1 ≤ x ≤ i}. Mamy

[

\

Ai = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Ai = {1}

i∈I

i∈I

[

\

Ai = {1, 2, 3, 4, 5, 6}

Ai = {1, 2}

1<i<7

1<i<7

4

Zaokr¸

aglenia

Wprowadźmy dwa oznaczenia na zaokr¸aglenie liczby rzeczywistej.

Dla dowolnej liczby

rzeczywistej x

dxe

oznacza zaokr¸aglenie x w gór¸e do najbliższej liczby ca lkowitej. Na przyk lad: d4e = 4,

d4.3e = 5,

d−4e = −4,

d−4.3e = −4.

Przez

bxc

b¸edziemy oznaczać zaokr¸aglenie x w dó l do najbliższej liczby ca lkowitej. Na przyk lad: b4c = 4,

b4.3c = 4,

b−4c = −4,

b−4.3c = −5.

5