Файл: Дискретная мат-ка_УП.pdf

Министерство образования и науки Российской Федерации 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ 

УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) 

Кафедра комплексной информационной безопасности 

электронно-вычислительных систем (КИБЭВС) 

Е.М. Давыдова, Р.В. Мещеряков 

ДИСКРЕТНАЯ МАТЕМАТИКА 

Учебное пособие 

2004 

 
 
 
 
 
 
 
 
 
Корректор: Осипова Е.А. 

Давыдова Е.М., Мещеряков Р.В. 
Дискретная  математика:  Учебное  пособие. 

− Томск: Томский меж-

вузовский центр дистанционного образования, 2004. 

− 181 с. 

                                                                © Давыдова Е.М., Мещеряков Р.В., 2004 
                                                                © Томский межвузовский центр 

     дистанционного образования,       2004

3

СОДЕРЖАНИЕ

Введение................................................................................................5 
1 ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ .........................................6 

1.1 Операции над множествами.......................................................9 
1.2 Диаграммы Эйлера-Венна ....................................................... 10 
1.3 Понятие алгебры....................................................................... 12 
1.4 Упражнения............................................................................... 15 

2 ОТНОШЕНИЯ................................................................................ 21 

2.1 Операции над отношениями ................................................... 24 
2.2 Свойства бинарных отношений.............................................. 26 
2.3 Задачи и упражнения ............................................................... 31 

3 НЕЧЕТКИЕ   МНОЖЕСТВА ....................................................... 33 

3.1 Операции над нечеткими множествами ................................ 34 
3.2 Задачи и упражнения ............................................................... 37 

4 K-ЗНАЧНАЯ ЛОГИКА ................................................................. 39 

4.1 Элементарные функции k-значных логик                                               

и соотношение между ними.................................................... 39 

4.2 Разложение функций k-значных логик в первую                                      

и вторую формы ....................................................................... 42 

4.3 Замкнутые классы и полнота в k-значных логиках.............. 42 
4.4 Задачи и упражнения ............................................................... 44 

5 ЛОГИКА ВЫСКАЗЫВАНИЙ ...................................................... 47 

5.1 Тождества в алгебре высказываний ....................................... 51 
5.2 Булевы формулы....................................................................... 52 
5.3 Интерпретации.......................................................................... 53 

6 БУЛЕВЫ ФУНКЦИИ.................................................................... 56 

6.1 Способы задания булевой функции ....................................... 57 
6.2 Равносильные преобразования формул ................................. 60 
6.3 Нормальные формулы. Совершенные нормальные                    

формулы .................................................................................... 61 

6.4 Разложение Шеннона. Декомпозиция булевых функций.... 63 
6.5 Представление булевой функции картами                                          

Карно (Вейча) ........................................................................... 65 

6.6 Минимизация булевых функций ............................................ 68 
6.7 Классы булевых функций........................................................ 74 

7 КОМБИНАТОРИКА ..................................................................... 77 
8 КОДИРОВАНИЕ ........................................................................... 84 

4

8.1 Алфавитное кодирование ........................................................ 86 
8.2 Кодирование с минимальной избыточностью ...................... 89 
8.3 Помехоустойчивое кодирование ............................................ 97 
8.4 Сжатие данных ....................................................................... 102 
8.5 Шифрование............................................................................ 107 
8.6 Криптография ......................................................................... 107 
8.7 Цифровая подпись.................................................................. 113 

9 ГРАФЫ.......................................................................................... 116 

9.1 Определение графа................................................................. 116 
9.2 Задание графов ....................................................................... 118 
9.3 Связность графа...................................................................... 126 
9.4 Эйлеровы и гамильтоновы графы ........................................ 131 
9.5 Деревья .................................................................................... 133 
9.6 Понятие метрики графа ......................................................... 135 
9.7 Цикломатическое число, раскраска...................................... 137 
9.8 Изоморфизм графов ............................................................... 140 
9.9 Орграфы................................................................................... 142 
9.10 Сети Петри ............................................................................ 145 

Контрольная работа №1 (варианты заданий) .............................. 152 
Множества ....................................................................................... 152 
Графы ............................................................................................... 159 
Контрольная работа №2 ................................................................. 169 
Список литературы ......................................................................... 181 

5

ВВЕДЕНИЕ

Настоящее  учебное  пособие  преследует  несколько  целей,  а 

именно: 

-  ознакомить  учащегося  с  широким  кругом  понятий  дис-

кретной математики; 

-  позволить  овладеть  методами  дискретной  математики, 

наиболее употребительными при решении практических задач; 

-  предоставит  к  изучению  ряд  алгоритмов  для  решения  ти-

повых задач; 

- сформировать абстрактное мышление, без которого невоз-

можно решение проблем информатизации. 

Дискретная  математика  зародилась  в  глубокой  древности  и 

включает  в  себя  многие  разделы  математики,  такие  как  теория 
множеств,  математическая логика, теория чисел, алгебра, теория 
графов и сетей и т.д. Наиболее интенсивно дискретная математи-
ка стала развиваться с появлением ЭВМ. 

Пособие предназначено для студентов специальностей 2205 

(проектирование и технология ЭВС) и 0755 (комплексная инфор-
мационная безопасность автоматизированных систем).