86

Министерство общего и профессионального образования российской федерации

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

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

УТВЕРЖДАЮ

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

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

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

«_____»______________1999 г.

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

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

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

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

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

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

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

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

Разработчик

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

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

1999

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

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

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

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

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

СОДЕРЖАНИЕ

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

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

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

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

СОДЕРЖАНИЕ 2

ВВЕДЕНИЕ 6

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

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

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

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

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

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

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 Частичные графы, подграфы, частичные подграфы 23

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

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

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

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

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

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

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

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

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

2.7 Определение путей и кратчайших путей 42

в графах 42

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

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

2.8 Обход графа 48

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

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

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

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

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

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

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

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

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

Эта таблица весьма полезна при выявлении полных систем булевых функций. В ней заполнены только две первых строки. Оставшуюся часть таблицы заполните самостоятельно. 67

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

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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