Wstęp
Matematyka dyskretna to część matematyki zajmująca się strukturami dyskretnymi.
Słowo „dyskretny” należy tu rozumieć w znaczeniu „nieciągły”, „oddzielony od siebie”
(w języku angielskim mamy słowo discrete, w odróżnieniu od discreet oznaczającego coś,
co nie rzuca się w oczy lub ma pozostać w tajemnicy). W bardziej restrykcyjnym znaczeniu
termin „dyskretny” rozumie się również jako „skończony”, co wskazuje, że obiektem
zainteresowania matematyki dyskretnej będą struktury i procesy skończone. W ten sposób
matematyka dyskretna różni się zasadniczo od analizy matematycznej, teorii równań
różniczkowych czy topologii, zainteresowanych głównie pojęciami ciągłymi i obiektami
nieskończonymi.
Konkretniej, matematyka dyskretna opiera swoje podstawy na logice, teorii zbiorów
i teorii liczb, a główny działy wchodzące w jej zakres to kombinatoryka i teoria grafów.
Stosuje się ją w takich obszarach z pogranicza matematyki i informatyki jak: algorytmika,
kryptografia, teoria kodowania czy teoria obliczeń. Matematyka dyskretna jest
niezbędna dla zrozumienia teoretycznych podstaw informatyki. Dogłębne zrozumienie zagadnień
matematyki dyskretnej pozwala na sprawne rozwiązywanie złożonych problemów
informatycznych i tworzenie efektywnych algorytmów.
Podręcznik ten ma na celu przybliżenie najważniejszych pojęć matematyki dyskretnej
wszystkim zainteresowanym tą dziedziną, w szczególności studentom pierwszego roku
studiów licencjackich kierunku informatyka. Poznając podstawy matematyki dyskretnej,
student rozwija umiejętności rozwiązywania problemów, które mają zastosowanie w różnych
praktycznych scenariuszach.
Materiał do skryptu „Matematyka dyskretna dla studentów kierunku informatyka” jest
tak dobrany, aby porządkował wiedzę z tej dziedziny nabytą w szkole średniej i uzupełniał
ją o tematy niezbędne do studiowania informatyki na dalszych etapach kształcenia.
Niniejszy skrypt obejmuje podstawy logiki (rozdział 1), elementy teorii liczb (rozdział 2)
oraz wstęp do kombinatoryki (rozdział 3). Każdy rozdział jest uzupełniony o zestaw zadań,
do większości których dostarczone są także odpowiedzi. Całość uzupełniona jest
o przykładowe pytania egzaminacyjne (rozdział 4).
5
Spis treści
Oznaczenia 4
Wstęp 5
1. Elementy logiki 6
1.1. Podstawy rachunku zdań . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2. Podstawy rachunku kwantyfikatorów . . . . . . . . . . . . . . . . . . . . . 10
1.3. Elementy teorii zbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4. Elementy teorii relacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5. Notacja dla sum i iloczynów . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6. Indukcja matematyczna . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7. Funkcje całkowitoliczbowe . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.9. Odpowiedzi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2. Elementy teorii liczb 37
2.1. Podzielność liczb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2. Liczby pierwsze i złożone . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3. Największy wspólny dzielnik i najmniejsza wspólna wielokrotność . . . . . 41
2.4. Algorytm Euklidesa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.5. Liczby względnie pierwsze . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.6. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.7. Odpowiedzi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3. Elementy kombinatoryki 53
3.1. Silnia i symbol Newtona . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2. Wariacje, permutacje i kombinacje . . . . . . . . . . . . . . . . . . . . . . 56
3.3. Prawo mnożenia i prawo dodawania . . . . . . . . . . . . . . . . . . . . . 59
3.4. Problemy różne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5. Zasada włączania i wyłączania oraz zasada szufladkowa Dirichleta . . . . 64
3.6. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.7. Odpowiedzi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4. Przykładowe pytania egzaminacyjne 88
Literatura 92
3
Za darmo