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

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

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

УТВЕРЖДАЮ

Зав. кафедрой АСУ

профессор д-р техн. наук

_______________А.М. Кориков

«_____»______________1999 г.

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

Методическое пособие по дисциплине

«Дискретная математика»

для студентов специальностей 071900

«Информационные системы в экономике» и 22040

«Программное обеспечение вычислительной техники

и автоматизированных систем»

Конспект лекций, часть 1

Разработчик

канд. техн. наук, доцент

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

Методическое пособие рассмотрено и рекомендовано к изданию методическим семинаром кафедры автоматизированных систем управления ТУСУР 17 мая 1999 г.

Зав. кафедрой АСУ

проф. д-р техн. наук А.М.Кориков

© Е.Н. Сафьянова, 1999 г.

© ТУСУР, каф. АСУ, 1999 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................................................... 5

1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ....................................... 6

1.1 Основные определения...................................................................................... 6

1.2 Операции над множествами............................................................................ 7

1.3 Отношения на множествах............................................................................ 11

1.4 Экстремальные элементы множеств.......................................................... 14

1.5 Отображения множеств................................................................................... 14

1.6 Задачи и упражнения....................................................................................... 16

2 ОСНОВЫ ТЕОРИИ ГРАФОВ........................................... 18

2.1 Основные определения.................................................................................... 19

2.1.1 Общие понятия.............................................................................................. 19

2.1.2 Ориентированные и неориентированные графы................................ 20

2.1.3 Цепи, циклы, пути и контуры графов...................................................... 21

2.1.4 Конечный и бесконечный графы............................................................. 22

2.1.5 Частичные графы, подграфы, частичные подграфы.......................... 22

2.1.6 Связность в графах...................................................................................... 24

2.1.7 Изоморфизм. Плоские графы..................................................................... 25

2.2 Отношения на множествах и графы........................................................... 26

2.3 Матрицы смежности и инциденций графа.............................................. 29

2.4 Операции над графами................................................................................... 30

2.5 Степени графов................................................................................................... 36

2.5.1 Степени неориентированных графов..................................................... 36

2.5.2 Степени ориентированных графов......................................................... 37

2.6 Характеристики расстояний в графах...................................................... 38

2.7 Определение путей и кратчайших путей в графах............................... 40

2.7.1 Алгоритм определения пути в графе...................................................... 40

2.7.2 Алгоритм определения кратчайших путей в графе............................ 41

2.8 Обход графа......................................................................................................... 45

2.8.1 Эйлеровы цепи, циклы, пути, контуры................................................... 45

2.8.2 Гамильтоновы цепи, циклы, пути, контуры.......................................... 49

2.9 Характеристики графов.................................................................................. 50

2.10 Задачи и упражнения..................................................................................... 51

3. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ.................... 52

3.1 Алгебра высказываний................................................................................... 52

3.2 Булевы функции................................................................................................ 56

3.3 Совершенные дизъюнктивная и конъюнктивная нормальные формы 58

3.4 Полнота системы булевых функций.......................................................... 60

3.5 Минимизация дизъюнктивных нормальных форм............................. 65

3.5.1 Основные определения............................................................................... 65

3.5.2 Этапы минимизации ДНФ......................................................................... 66

3.5.3 Минимизация ДНФ методом Квайна..................................................... 69

3.6 Автоматные описания..................................................................................... 72

3.7 Синтез комбинационных схем..................................................................... 76

3.8 Логика предикатов........................................................................................... 79

3.8.1 Предикаты и операции квантирования.................................................. 79

3.8.2 Равносильные формулы логики предикатов........................................ 81

3.9 Задачи и упражнения....................................................................................... 83

Список литературы....................................................... 84

ВВЕДЕНИЕ

Для создания и эксплуатации сложных автоматизированных систем обработки информации и их компонент в области экономики, математи-ческого и программного обеспечения вычислительной техники, сетей передачи данных и многих других сферах деятельности человека необходимо знание дискретной математики.

Дискретная математика – часть математики, которая зародилась в глубокой древности. Как говорит само название, главной ее особенностью является дискретность, т.е. антипод непрерывности. В ней отсутствует понятие предельного перехода, присущее классической, «непрерывной» математике. Дискретная математика занимается изучением дискретных структур, которые возникают как внутри математики, так и в ее приложениях.

Цель дисциплины «Дискретная математика» - знакомство с основными разделами зтой науки: теорией множеств, математической логикой, теорией графов, теорией алгоритмов, комбинаторным анализом как аппаратом для построения моделей дискретных систем.

Дискретная математика является обязательной дисциплиной цикла «Математические и общие естественнонаучные дисциплины». Знания и навыки, полученные при ее изучении, используются в дисциплинах: «Информатика», «Программирование», «Структуры и алгоритмы обработки данных в ЭВМ», «Базы данных» и т.д.

Настоящее пособие представляет собой курс лекций, читаемый в Томском государственном университете систем управления и радиоэлектроники студентам специальностей «Программное обеспечение вычислительной техники и автоматизированных систем» и «Информационные системы в экономике».

Пособие рассчитано на изучение в течение двух семестров и в соответствии с этим разбито на две части.

В первой части излагаются основы теории множеств, теории графов, элементы алгебры высказываний, теории булевых функций и логики предикатов.

Вторая часть посвящена изложению основ построения формальных теорий, знакомству с основными разделами теории алгоритмов: аппаратом рекурсивных функций, машинами Тьюринга, нормальными алгоритмами Маркова. Завершает вторую часть раздел, дающий представление о задачах и основных построениях комбинаторного анализа.

В конце каждого раздела приведены задачи и упражнения, которые необходимо выполнить для закрепления теоретического материала.