skrypt_okl_full.pdf

Publikacja współfinansowana przez Unię Europejską w ramach Europejskiego Funduszu Społecznego

SKRYPT Z MATEMATYKI DYSKRETNEJ

Matematyka dyskretna

dla studentów

kierunku

Informatyka

Hanna Furmańczyk

Karol Horodecki

Paweł Żyliński

Publikacja współfinansowana przez Unię Europejską w ramach Europejskiego Funduszu Społecznego

SKRYPT Z MATEMATYKI DYSKRETNEJ

Hanna Furmańczyk, Karol Horodecki

Paweł Żyliński

Matematyka dyskretna

dla studentów

kierunku

Informatyka

Dziękujemy wszystkim Studentom, których cenne sugestie i spostrzeżenia

pozwoliły nam na ulepszenie zawartości skryptu i wyeliminowanie błędów.

Dziękujemy także Autorom, z których materiałów skorzystaliśmy, a na

przestrzeni tych kilku lat zdążyliśmy już o tym zapomnieć.

Wydawnictwo Uniwersytetu Gdańskiego

Gdańsk 2010

Publikacja współfinansowana przez Unię Europejską w ramach Europejskiego Funduszu Społecznego

Skład komputerowy (LaTeX): Paweł Żyliński

ISBN 978-83-7326-708-4

Recenzent:

Projekt okładki i strony tytułowej: Anna Białk – Bielińska

Wydawnictwo Uniwersytetu Gdańskiego, ul. Armii Krajowej 119/121.

81-824 Sopot, tel./fax (058) 523-11-37

Uniwersytet Gdański

Wydział Matematyki, Fizyki i Informatyki

Instytut Informatyki

80-952 Gdańsk, ul. Wita Stwosza 57

Zestaw zadań nr 1

Oznaczenia, pojęcia wstępne

Symbol sumy, j, k∈

Z, j≤k:

x i = x j + x j+1 ++ x k .

i=j

i=1 2 i .

Przykład 1.1. Oblicz

i=1 2 i

= 2 1 + 2 2 + 2 3 + 2 4 + 2 5

Rozwiązanie.

= 2 + 4 + 8 + 16 + 32 = 62.

♯

Symbol iloczynu, j, k∈

Z, j≤k:

x i = x j x j+1 . . .x k .

i=j

Przykład 1.2. Oblicz

i=1 i.

Rozwiązanie.

i=1 i = 1234 = 4! = 24.

♯

i=1 (i2 i ) dla n = 0, 1, 2, 3, 4.

Zadanie 1.3. Oblicz

Zadanie 1.4. Oblicz

i=1 (i + 1).

i=1 (2i + 1).

Zadanie 1.6. Sprawdzić prawdziwość poniższych równań dla podanych wartości zmiennych,

obliczając wartość lewej i prawej strony.

Zadanie 1.5. Oblicz

i=1 i =

(1+n)n

dla n = 3 i n = 6,

k=0 (3k−2) = (2n + 1)(3n−2) dla n = 2 i n = 3,

3 n+1 −1

i=0,i∈P 3 i

dla n = 3 i n = 4, gdzie P – zbiór liczb parzystych,

1≤i≤5 i 2

= (5!) 2

i∈T 2i = 32, gdzie T ={0, 1, 4}.

Działania na zbiorach A oraz B:

a) suma:

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

b) iloczyn (przekrój):

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

c) różnica:

A\B ={x : x∈A i x ∈B}

d) różnica symetryczna:

A⊕B = (A\B)∪(B\A)

e) iloczyn kartezjański (produkt):

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

Dla ustalonego zbioru U (uniwersum, przestrzeń), dopełnieniem zbioru A, A⊆U nazywamy zbiór

U−A i oznaczamy przez A.

Przykład 1.7. Dla A ={1, 2, 3}oraz B ={2, 4}wyznacz: A∪B, A∩B, A\B, B\A, A⊕B,

A×B oraz B×A.

Rozwiązanie.

A∪B ={1, 2, 3, 4}, A∩B ={2}, A\B ={1, 3},

B\A ={4}, A⊕B ={1, 3, 4},

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

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

♯

Przykład 1.8. Dla A ={1, 2, 3}oraz uniwersum U ={1, 2, 3, 4, 5, 6, 7}wyznacz A.

Rozwiązanie. A ={4, 5, 6, 7}.

♯

Zadanie 1.9. Niech A ={1, 2, 3, 4, 5}, B ={1, 3, 5, 7}, C ={4, 5, 6, 7, 8}oraz U = N. Wyznacz:

a) A∪B∪C,

b) A∩B∩C,

c) A\B,

d) A∩(B\C),

e) A⊕B,

f) A⊕B⊕C,

g) A∩B,

h) A∩B.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: