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

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

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

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

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

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

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

Часть 1 

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

2000 

 
 
 
 
 
 
 
 
 
 
 
 
Сафьянова Е.Н. 
Дискретная  математика.  Часть 1: Учебное  пособие. 

−  Томск: 

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

− 106 с. 

Учебное пособие рассмотрено и рекомендовано к изданию 

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

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

© Томский межвузовский центр 

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

3 

СОДЕРЖАНИЕ

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

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

1.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 Минимизация ДНФ методом Квайна ................................. 82 

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

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

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

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

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

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

МЕТОДИЧЕСКИЕ

УКАЗАНИЯ

ПО

КУРСУ

 «

ДИСКРЕТНАЯ

МАТЕМАТИКА

». 

Часть

 1 …………………………………………100 

Контрольная работа №1…………………………………………... 100 
Контрольная работа №2…………………………………………... 104 
Список литературы........................................................................... 106 

5 

ВВЕДЕНИЕ

Для  создания  и  эксплуатации  сложных  автоматизированных 

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

Дискретная  математика – часть  математики,  которая  зароди-

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

Цель дисциплины «Дискретная математика» 

− знакомство с ос-

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

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

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

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

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

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

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

 В  первой  части  излагаются  основы  теории  множеств,  теории 

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

Вторая  часть  посвящена  изложению  основ  построения  фор-

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