Diskret

  • 10 янв. 2013 г.
  • 23944 Слова
Министерство образования Российской Федерации ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра автоматизированных систем управления (АСУ)

Е.Н. Сафьянова

ДИСКРЕТНАЯ МАТЕМАТИКА
Часть 1

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

2000

Сафьянова Е.Н. Дискретная математика. Часть 1: Учебное пособие. − Томск: Томский межвузовский центр дистанционного образования, 2000. − 106 с.Учебное пособие рассмотрено и рекомендовано к изданию методическим семинаром кафедры автоматизированных систем управления ТУСУР 17 мая 1999 г.

© Сафьянова Е.Н., 2000 © Томский межвузовский центр дистанционного образования, 2000

3

СОДЕРЖАНИЕ
ВВЕДЕНИЕ............................................................................................. 5 1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ ...................... 61.1 Основные определения ................................................................ 6 1.2 Операции над множествами ....................................................... 8 1.3 Отношения на множествах ....................................................... 12 1.4 Экстремальные элементы множеств ...................................... 16 1.5 Отображения множеств............................................................. 16 1.6 Задачи и упражнения ................................................................. 17 2 ОСНОВЫ ТЕОРИИ ГРАФОВ ....................................................... 20 2.1 Основные определения .............................................................. 21 2.1.1 Общие понятия ..................................................................... 21 2.1.2Ориентированные и неориентированные графы ............... 22 2.1.3 Цепи, циклы, пути и контуры графов................................. 23 2.1.4 Конечный и бесконечный графы ........................................ 25 2.1.5 Частичные графы, подграфы, частичные подграфы ......... 25 2.1.6 Связность в графах............................................................... 27 2.1.7 Изоморфизм. Плоскиеграфы.............................................. 29 2.2 Отношения на множествах и графы ....................................... 30 2.3 Матрицы смежности и инциденций графа ............................ 33 2.4 Операции над графами.............................................................. 35 2.5 Степени графов ........................................................................... 42 2.5.1 Степенинеориентированных графов ................................. 42 2.5.2 Степени ориентированных графов ..................................... 44 2.6 Характеристики расстояний в графах ................................... 45 2.7 Определение путей и кратчайших путейв графах ............... 47 2.7.1 Алгоритм определения пути в графе .................................. 47 2.7.2 Алгоритм определения кратчайших путей вграфе........... 49 2.8 Обход графа ................................................................................. 53 2.8.1 Эйлеровы цепи, циклы, пути, контуры............................... 53

4 2.8.2 Гамильтоновы цепи, циклы, пути, контуры....................... 58 2.9 Характеристики графов ............................................................ 59 2.10 Задачи и упражнения............................................................... 60 3. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ............................. 62 3.1 Алгебра высказываний ............................................................. 62 3.2 Булевы функции ......................................................................... 66 3.3 Совершенные дизъюнктивная и конъюнктивная нормальные формы.................................................................... 69 3.4 Полнота системы булевых функций....................................... 71 3.5 Минимизация дизъюнктивных нормальных форм ............. 77 3.5.1 Основные определения ........................................................ 77 3.5.2 Этапы минимизации ДНФ................................................... 78 3.5.3 Минимизация ДНФ...
tracking img