Министерство образования Республики Беларусь

Белорусско-Российский Университет

КОНСПЕКТ

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Могилёв 2010

Содержание:

Тема 1. Основные понятия теории множеств. Способы задания множеств. Диаграммы Венна. Операции над множествами. Свойства теоретико-множественных операций. Представление множеств в ЭВМ. 5

Основные понятия теории множеств. Способы задания множеств 5

Диаграммы Венна. 5

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

Свойства теоретико-множественных операций. 7

Представление множеств в ЭВМ 7

Реализация операций над подмножествами заданного универсума в ЭВМ. 8

Тема 2. Упорядоченные пары. Прямое произведение множеств. Отношения. Многоместные отношения. Композиция отношений. Степень отношений. Ядро отношения. Свойства отношений. Представление отношений в ЭВМ. 9

Упорядоченные пары. Декартово (прямое) произведение множеств. Отношения. 9

Многоместные отношения. Композиция отношений. Степень и ядро отношений. 10

Свойства отношений. 10

Представление отношений в ЭВМ. 11

Тема 3. Специальные классы отношений. Отношение эквивалентности и разбиения. Отношения порядка. Минимальные элементы. Теорема о существовании минимального элемента. Алгоритм топологической сортировки. Операции над бинарными отношениями. 12

Специальные классы отношений. Отношение эквивалентности и разбиения. Отношения порядка. 12

Минимальные элементы. Теорема о существовании минимального элемента. 16

Алгоритм топологической сортировки 18

Операции над бинарными отношениями. 19

Тема 4. Замыкание отношений. Транзитивное замыкание, рефлексивное замыкание. Алгоритм Уоршалла вычисления транзитивного замыкания. 21

Замыкание отношений. 21

Транзитивное замыкание отношений 21

Рефлексивное замыкание отношений 22

Алгоритм Уоршалла. 22

Тема 5. Функции и отображения. Инъекция, сюръекция, биекция. Представление функций в ЭВМ. Операции. Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева и справа. Способы задания операций. Таблица Кэли. 24

Функции и отображения. Инъекция, сюръекция, биекция. 24

Представление функций в ЭВМ. 26

Операции 27

Свойства бинарных операций: 27

Способы задания операций. 28

Таблица Кэли 28

Тема 6. Алгебраическая система. Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр. 30

Алгебраическая система 30

Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр. 31

Тема 7. Нечеткие множества. Основные понятия и определения. Основные характеристики. Теоретико-множественные операции над нечеткими множествами. Графическое представление операций. 34

Нечеткие множества. Основные понятия и определения. 34

Основные характеристики нечетких множеств 35

Примеры нечетких множеств 35

Операции над нечеткими множествами 36

Графическое представление операций 37

Тема 8. Алгебраические операции над нечеткими множествами. 39

Тема 9. Основное определение графов. Смежность. Изоморфизм графов. Элементы графов. Подграфы. Валентность. Теорема Эйлера. 43

Основное определение. 43

Смежность. 43

Изоморфизм графов. 44

Элементы графов. Подграфы. Валентность. 45

Теорема Эйлера. 45

Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. 46

Маршруты в графах. Цепи. Циклы. 46

Расстояние между вершинами. 46

Связность. 47

Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. 47

Тема 11. Матрица смежности, матрица инцидентности. Операции над графами. Представление графов в ЭВМ. 49

Матрица смежности. Матрица инцедентности. 49

Операции над графами: 49

Объединение графов. 49

Пересечение графов 51

Композиция графов 53

Декартово произведение графов. 54

Операция произведения графов. 57

Представление графов в ЭВМ 59

Тема 12. Компоненты связности и объединение графов. Оценка числа ребер через число вершин и число компонентов связности. Вершинная и реберная связность. Мосты и блоки. 60

Объединение графов и компоненты связности. Оценка числа рёбер через число вершин и число компонентов связности. Вершинная и рёберная связность: мосты и блоки, меры связности. 60

Тема 13. Потоки в сетях. Определение потока. Разрезы. Пример сети с потоками. Теорема Форда и Фалкерсона. Алгоритм нахождения максимального потока. 62

Потоки в сетях. Примеры практических задач, определение потока, разрезы. 62

Теорема Форда - Фалкерсона. Алгоритм нахождения максимального потока. 65

Тема 14. Кратчайшие пути. Алгоритм Флойда. Алгоритм Дейкстры. 66

Кратчайшие пути 66

Рёбра отрицательного веса 67

Представление кратчайших путей в алгоритме 67

Алгоритм Флойда 68

Алгори́тм Де́йкстры 69

Пример 70

Сложность алгоритма 77

Тема 15. Свободные деревья. Основные свойства деревьев. Ориентированные, упорядоченные и бинарные деревья. Представление в ЭВМ свободных, ориентированных и упорядоченных деревьев. 79

Свободные деревья. Основные свойства деревьев. 79

Ориентированные, упорядоченные и бинарные деревья 80

Представление в ЭВМ свободных, ориентированных и упорядоченных деревьев. 81

Тема 16. Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья. Минимальный каркас. Схема алгоритма построения минимального каркаса. 82

Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья. 82

Минимальный каркас. Схема алгоритма построения минимальных каркасов. 84

Тема 17. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. Раскраска графов. Хроматическое число. Планарные графы. Укладка графов. Алгоритм раскрашивания. 86

21. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. 86

Раскраска графов. Хроматическое число. Планарность. Укладка графов. Алгоритмы раскрашивания. 87

Тема 18. Переключательные функции. Основные понятия и определения. Способы задания переключательных функций. Таблица истинности. Переключательные функции одного и двух аргументов. Специальные разложения ПФ. 89

Переключательные функции. Существенные и несущественные переменные. Булевы функции одной переменной. Булевы функции двух переменных. 89

f1(x) – нулевая функция. 90

Дизъюнктивная нормальная форма. 92

Конъюнктивная нормальная форма. 93

Тема 19. Неполностью определенные (частные) ПФ. Минимизация ПФ и неполностью определенных ПФ. 94

Понятие минимизации булевых функций. 94

Тема 20. Геометрическая интерпретация минимизации. Метод неопределенных коэффициентов. Метод карт Карно Метод Петрика для нахождения тупиковых ДНФ. 96

Геометрическая интерпретация минимизации функций алгебры логики. 96

Метод неопределённых коэффициентов. 96

Метод карт Карно 97

Метод Петрика 104

Тема 21. Пять классов переключательных функций: линейные переключательные функции; переключательные функции, сохраняющие нуль; переключательные функции, сохраняющие единицу; монотонные переключательные функции; самодвойственные переключательные функции. Теорема о функциональной полноте. Основная функционально полная система логических функций. Функционально полные системы логических функций. Примеры функционально полных базисов. 107

Теорема Поста 108

Тема 22. Законы алгебры логики в ОФПС и их следствия. Правило выполнения совместных логических действий, правило склеивания, правило поглощения, правило развертывания. 111

Тема 23. Задача анализа и синтеза логических схем 116

Тема 24. Элементы теории алгоритмов. Цели и задачи теории алгоритмов. Формализация понятия алгоритмов: определение Колмогорова, определение Маркова 118

Тема 1. Основные понятия теории множеств. Способы задания множеств. Диаграммы Венна. Операции над множествами. Свойства теоретико-множественных операций. Представление множеств в ЭВМ.

Основные понятия теории множеств. Способы задания множеств

Определение 1.1.Множество – это любая, определенная совокупность объектов. Объекты из которых составлено множество называют его элементами. Элементы множества различны и отличны друг от друга. Множества обозначают прописными буквами латинского алфавита, а их элементы – строчными. Например N, Z, Q, R – множества натуральных, целых, рациональных и действительных чисел.

N={1, 2, 3…}A={a₁,a₂,a₃…}

Если объект х является элементом множества М, то говорят, что хМ. Если х не является элементом множества М, то говорят, что хМ.

Одно множество равно другому, если выполняется условие: A=B|AB&BA

Множество не содержащее элементов называется пустым. Его обозначают Ø.

Обычно, в конкретных обсуждениях, элементы всех множеств берутся из некоторого одного достаточно широкого множества U (своего для каждого множества), которое называется универсальным множеством или универсумом. В общем случае множества могут быть конечными и бесконечными. Конечное множество – это такое множество, для которого существует натуральное число, равное количеству элементов множества, и называемое мощностью множества и обозначаемое |A|.

Чтобы задать множество нужно указать, какие элементы ему принадлежат. Это можно сделать различными способами:

1) перечислением элементов множества А={a₁,a₂,…,a_n|n=6} (перечислением можно задавать только конечное множество);

2)характеристическим предикатомM={x|P(x) }, где P(x) – предикат.

Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения, возвращаемое логическое значение. Если для данного элемента условие выполнено, т.е. P(x) = 1, то этот элемент принадлежит определяемому множеству, в противном случае – не принадлежит. Пример 1.1.:

M= {x|xN&x< 10}

P(x) = (11) = ( 11 & 11 < 10 ) = 0 11М

3)порождающей процедурой:M={x|x:=f}

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

Иначе говоря, порождающая процедура – последовательность действий, которые формируют некоторые объекты по заданному правилу.

Пример 1.2.: M = { x | x := from 1 to 9 generate x}