Matematyka dyskretna

Oznaczenia

Andrzej Szepietowski

W tym rozdziale przedstawimy podstawowe oznacznia.
∀ oznacza kwantyfikator og´olny ”dla ka˙zdego”. ∃ oznacza kwantyfikator szczeg´o lowy

”istnieje”.

1

Sumy i iloczyny

Maj¸ac dany sko´

nczony ci¸ag a

1

, a

2

,... a

k

, sum¸e jego element´ow zapisujemy jako

k

X

i=1

a

i

Niezbyt formalnie mo˙zemy zapisa´c

k

X

i=1

a

i

= a

1

+ a

2

+ · · · + a

k

.

Na przyk lad

k

X

i=1

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

(k + 1)k

2

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

k

X

i=0

x

i

= 1 + x + x

2

+ · · · + x

k

=

x

k+1

− 1

x − 1

(suma ci¸agu geometrycznego). B¸edziemy te˙z u˙zywa´c zapisu typu

X

1≤i≤6

a

i

= a

1

+ a

2

+ a

3

+ a

4

+ a

5

+ a

6

.

W tym przypadku zbi´or indeks´ow okre´slony jest za pomoc¸a warunku pod znakiem sumy.
Warunek okre´slaj¸acy indeksy, po kt´orych nale˙zy sumowa´c mo˙ze by´c bardziej skomplikowany,
na przyk lad

X

1≤i≤6

i

parzyste

a

i

= a

2

+ a

4

+ a

6

.

1

Stosowa´c b¸edziemy tak˙ze zapis

X

i∈I

a

i

oznaczaj¸acy sum¸e tych element´ow a

i

, kt´orych indeksy nale˙z¸a do sko´

nczonego zbioru indeks´ow

I. Na przyk lad, je˙zeli I = {1, 3, 5, 7}, to

X

i∈I

a

i

= a

1

+ a

3

+ a

5

+ a

7

.

Aby zapisa´c iloczyn element´ow ci¸agu a

1

, a

2

,... a

k

, stosujemy zapis

k

Y

i=1

a

i

.

Zn´ow niezbyt formalnie mo˙zemy to zapisa´c jako

k

Y

i=1

a

i

= a

1

· a

2

· · · · · a

k

.

2

Zbiory

∅ oznacza zbi´or pusty, kt´ory nie zawiera ˙zadnych element´ow. IN oznacza zbi´or liczb natu-
ralnych IN = {0, 1, 2, 3, . . .}

a ∈ A oznacza, ˙ze elment a nale˙zy do zbioru A, a /

∈ A, ˙ze elment a nie nale˙zy do zbioru A.

Najprostszy spos´ob zdefiniowania zbioru polega na wypisaniu jego element´ow w nawiasach
klamrowych. Na przyk lad zbi´or {1, 2, 3} zawiera elementy 1,2,3. Inny spos´ob definiowania
zbioru polega na podaniu w lasno´sci, kt´or¸a spe lniaj¸a elementy zbioru. Na przyk lad {x | x ∈
IN, 3 < x < 7} oznacza zbi´or liczb naturalnych wi¸ekszych od 3 i mniejszych od 7.

|A| oznacza moc zbioru lub inaczej liczb¸e element´ow tego zbioru.

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

|∅| = 0.

A ∪ B oznacza sum¸e zbior´ow, czyli zbi´or, kt´ory 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´oj zbior´ow, czyli zbi´or, kt´ory zawiera te elementy, kt´ore
nale˙z¸a do obu zbior´ow naraz.

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

A − B oznacza r´o˙znic¸e, czyli zbi´or, kt´ory zawiera te elementy, kt´ore nale˙z¸a do A i nie nale˙z¸a
do B.

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

2

A ⊕ B oznacza r´o˙znic¸e symetryczn¸a, kt´ora zawiera elementy nale˙z¸ace tylko do jednego z
dw´och zbior´ow. A ⊕ B = (A − B) ∪ (B − A).

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

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

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

Dwa zbiory s¸a r´owne je˙zeli 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´c kolejno´s´c element´ow 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´s´c elemnet´ow jest istotna w parze uporz¸adkowanej, kt´or¸a oznaczamy przez (x, y).

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

A×B oznacza iloczyn kartezja´

nski zbior´ow A i B. Jest to zbi´or wszystkich uporz¸adkowanych

par (a, b), w kt´orych 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´c oczywiste, ˙ze

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

3

Rodzina zbior´

ow

Zbi´or zbior´ow nazywamy czasami rodzin¸a zbior´ow. Na przyk lad A = {A

1

, A

2

, A

3

, A

4

} jest

rodzin¸a zawieraj¸ac¸a cztery zbiory A

1

, A

2

, A

3

i A

4

, s¸a to elementy zbioru A. Mo˙zemy te˙z

zapisa´c A = {A

i

| 1 ≤ i ≤ 4}.

Mo˙zemy sumowa´c zbiory z rodziny. Suma

k

[

i=1

A

i

zawiera te elementy, kt´ore nale˙z¸a do kt´orego´s ze zbior´ow A

1

, A

2

, ... ,A

k

, czyli

k

[

i=1

A

i

= {x | ∃

i

1 ≤ i ≤ k; x ∈ A

i

}.

3

Inaczej mo˙zemy to zapisa´c:

k

[

i=1

A

i

= A

1

∪ A

2

∪ . . . ∪ A

k

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

[

i∈I

A

i

na oznaczenie sumy wszystkich zbior´ow A

i

, kt´orych indeksy nale˙z¸a do zbioru I. Zachodzi

wtedy

[

i∈I

A

i

= {x | ∃

i∈I

x ∈ A

i

}.

Zbi´or indeks´ow sumowania mo˙ze by´c okre´slony za pomoc¸a warunku.

[

1<i<6

A

i

= A

2

∪ A

3

∪ A

4

∪ A

5

.

Mo˙zemy te˙z bra´c przekroje zbior´ow z rodziny. Przekr´oj

k

\

i=1

A

i

zawiera te elementy, kt´ore nale˙z¸a do wszystkich zbior´ow A

1

, A

2

, ... ,A

k

, czyli

k

\

i=1

A

i

= {x | ∀

i

1 ≤ i ≤ k; x ∈ A

i

}.

Inaczej mo˙zemy to zapisa´c:

k

\

i=1

A

i

= A

1

∩ A

2

∩ . . . ∩ A

k

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

\

i∈I

A

i

na oznaczenie przekroju wszystich zbior´ow A

i

, kt´orych indeksy nale˙z¸a do zbioru I. Zachodzi

wtedy

\

i∈I

A

i

= {x | ∀

i∈I

x ∈ A

i

}.

Zbi´or indeks´ow przekroju mo˙ze by´c okre´slony za pomoc¸a warunku.

\

1<i<6

A

i

= A

2

∩ A

3

∩ A

4

∩ A

5

.

Przyk lad 1.

We´zmy rodzin¸e z lo˙zon¸a z trzech zbior´ow A

1

= {4, 6, 8}, A

2

= {4, 5, 6},

A

3

= {4, 5, 8, 9},

3

[

i=1

A

i

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

3

\

i=1

A

i

= {4}

4

Przyk lad 2.

Niech I = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} b¸edzie zbiorem indeks´ow. Dla ka˙zdego

i ∈ I okre´slamy zb´or A

i

= {x ∈ N | 1 ≤ x ≤ i}. Mamy

[

i∈I

A

i

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

\

i∈I

A

i

= {1}

[

1<i<7

A

i

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

\

1<i<7

A

i

= {1, 2}

4

Zaokr¸

aglenia

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

Dla dowolnej liczby

rzeczywistej x

dxe

oznacza zaokr¸aglenie x w g´or¸e do najbli˙zszej liczby ca lkowitej. Na przyk lad:

d4e = 4,

d4.3e = 5,

d−4e = −4,

d−4.3e = −4.

Przez

bxc

b¸edziemy oznacza´c zaokr¸aglenie x w d´o l do najbli˙zszej liczby ca lkowitej. Na przyk lad:

b4c = 4,

b4.3c = 4,

b−4c = −4,

b−4.3c = −5.

5