Содержание

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего

Профессионального образования

«ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

УТВЕРЖДАЮ:

Директор ИДО

_____________А.Ф.Федоров

"" _________2007 г.

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

Методическое пособие

Для студентов специальности 220301 – Автоматизация технологических процессов и производств (в нефтегазовой отрасли) Института дистанционного образования

Томск 2007

УДК 681.3.06:51

ББК 32.973-018

Методическое пособие для студентов специальности 220301 – Автоматизация технологических процессов и производств (в нефтегазовой отрасли) Института дистанционного образования. – Томск: Изд–во ТПУ, 2007. – 108 с.

Составитель: А. В. Воронин

Рецензент – к.т.н., доцент В. Н. Шкляр.

Методическое пособие рассмотрено и рекомендовано к изданию методическим семинаром кафедры интегрированных компьютерных систем управления 20 марта 2007 г.

Заведующий кафедрой ИКСУ А. М. Малышенко

Одобрено учебно–методической комиссией АВТФ

Председатель учебно–методической комиссии

Рейзлин

Содержание

Введение Глава 1 Множества и отношения 1.1 Множества 1.1.1 Основные определения теории множеств 1.1.2 Способы задания множеств 1.1.3 Диаграммы Эйлера–Венна 1.1.4 Операции над множествами. 1.1.5 Свойства булевых операций над множествами 1.2 Отношения 1.2.1 Способы задания бинарных отношений 1.2.2 Свойства бинарных отношений 1.2.3 Эквивалентность и порядок 1.2.4 Операции над бинарными отношениями 1.2.5 Функциональные отношения 1.2.6 Функции и отображения 1.2.7 Операции Глава 2 Математическая логика 2.1 Логические операции 2.1.1 Основные определения математической логики 2.1.2 Таблицы истинности 2.1.3 Основные логические операции 2.1.4 Функционально полные системы (базисы) 2.1.5 Совершенная дизъюнктивная нормальная форма 2.1.6 Основные эквивалентные соотношения в булевой алгебре 2.1.7 Переход от ДНФ к СДНФ методом расщепления 2.2 Формы представления булевых функций 2.2.1 Геометрическое представление булевых функций 2.2.2 Интервальное представление булевых функций 2.3 Синтез логических схем 2.4 Минимизация дизъюнктивных номальных форм 2.4.1 Приведение к дизъюнктивной нормальной форме 2.4.2 Геометрическая интерпретация задачи минимизации ДНФ 2.4.3 Допустимые конъюнкции 2.4.4 Сокращенная ДНФ. 2.4.5 Построение сокращенной ДНФ 2.4.6 Тупиковые ДНФ 2.5 Логика предикатов 2.5.1 Основные понятия логики предикатов 2.5.2 Кванторы 2.5.3 Выполнимость и истинность 2.5.4 Префиксная нормальная форма Глава 3 Графы и сети 3.1 Графы 3.1.1 Основные определения теории графов 3.1.2 Способы задания графов 3.1.3 Операции над частями графа 3.1.4 Маршруты, пути, цепи, циклы 3.1.5 Эйлеровы циклы и цепи 3.1.6 Гамильтонов цикл. Взвешенные графы 3.1.7 Граф–дерево и граф–лес 3.1.8 Связность. Цикломатическое число графа 3.1.9 Двудольные (четные) графы 3.1.10 Планарность графов 3.2 Сети 3.2.1 Потоки в сетях 3.2.2 Расчет максимального потока в сети Глава 4 Автоматы, языки, элементы кодирования 4.1 Автоматы 4.1.2 Реализация крнечных автоматов 4.1.3 Автоматы – распознаватели 4.2 Элементы кодирования 4.2.1 Формулировка задачи кодирования 4.2.2.Алфавитное (побуквенное) кодирование 4.2.3 Кодирование с минимальной избыточностью 4.2.4 Алгоритм квазиоптимального кодирования Фано 4.2.5 Алгоритм оптимального кодирования Хаффмена 4.2.6 Помехоустойчивое кодирование 4.2.7 Сжатие данных Список литературы