- •Содержание:
- •Диаграммы Венна.
- •Операции над множествами.
- •Свойства теоретико-множественных операций.
- •Представление множеств в эвм
- •Реализация операций над подмножествами заданного универсума в эвм.
- •Многоместные отношения. Композиция отношений. Степень и ядро отношений.
- •Свойства отношений.
- •Представление отношений в эвм.
- •Минимальные элементы. Теорема о существовании минимального элемента.
- •Алгоритм топологической сортировки
- •Операции над бинарными отношениями.
- •Тема 4. Замыкание отношений. Транзитивное замыкание, рефлексивное замыкание. Алгоритм Уоршалла вычисления транзитивного замыкания. Замыкание отношений.
- •Транзитивное замыкание отношений
- •Рефлексивное замыкание отношений
- •Алгоритм Уоршалла.
- •Представление функций в эвм.
- •Операции
- •Свойства бинарных операций:
- •Способы задания операций.
- •Тема 6. Алгебраическая система. Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр. Алгебраическая система
- •Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр.
- •Основные характеристики нечетких множеств
- •Примеры нечетких множеств
- •Операции над нечеткими множествами
- •Графическое представление операций
- •Тема 8. Алгебраические операции над нечеткими множествами.
- •Тема 9. Основное определение графов. Смежность. Изоморфизм графов. Элементы графов. Подграфы. Валентность. Теорема Эйлера. Основное определение.
- •Смежность.
- •Изоморфизм графов.
- •Элементы графов. Подграфы. Валентность.
- •Теорема Эйлера.
- •Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети. Маршруты в графах. Цепи. Циклы.
- •Расстояние между вершинами.
- •Связность.
- •Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети.
- •Тема 11. Матрица смежности, матрица инцидентности. Операции над графами. Представление графов в эвм. Матрица смежности. Матрица инцедентности.
- •Операции над графами: Объединение графов.
- •Пересечение графов
- •Композиция графов
- •Декартово произведение графов.
- •Операция произведения графов.
- •Представление графов в эвм
- •V k1 k2
- •Теорема Форда - Фалкерсона. Алгоритм нахождения максимального потока.
- •Тема 14. Кратчайшие пути. Алгоритм Флойда. Алгоритм Дейкстры.
- •Кратчайшие пути
- •Рёбра отрицательного веса
- •Представление кратчайших путей в алгоритме
- •Алгоритм Флойда
- •Алгори́тм Де́йкстры
- •Сложность алгоритма
- •Ориентированные, упорядоченные и бинарные деревья
- •Представление в эвм свободных, ориентированных и упорядоченных деревьев.
- •Тема 16. Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья. Минимальный каркас. Схема алгоритма построения минимального каркаса.
- •Применение деревьев в программировании. Ассоциативная память. Выровненные деревья. Сбалансированные деревья.
- •Минимальный каркас. Схема алгоритма построения минимальных каркасов.
- •Тема 17. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. Раскраска графов. Хроматическое число. Планарные графы. Укладка графов. Алгоритм раскрашивания.
- •21. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака.
- •Раскраска графов. Хроматическое число. Планарность. Укладка графов. Алгоритмы раскрашивания.
- •F1(X) – нулевая функция.
- •Дизъюнктивная нормальная форма.
- •Конъюнктивная нормальная форма.
- •Тема 19. Неполностью определенные (частные) пф. Минимизация пф и неполностью определенных пф. Понятие минимизации булевых функций.
- •Метод неопределённых коэффициентов.
- •Метод карт Карно
- •Метод Петрика
- •Теорема Поста
- •Тема 22. Законы алгебры логики в офпс и их следствия. Правило выполнения совместных логических действий, правило склеивания, правило поглощения, правило развертывания.
- •Тема 23. Задача анализа и синтеза логических схем
- •Тема 24. Элементы теории алгоритмов. Цели и задачи теории алгоритмов. Формализация понятия алгоритмов: определение Колмогорова, определение Маркова
Дизъюнктивная нормальная форма.
Элементарной конъюнкцией называется такая формула A, которая является конъюнкцией, возможно одночленной, переменных и их отрицаний. Говорят, что формулаAнаходится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией, возможно одночленной, элементарных конъюнкций. ДНФ:A = x1·x2x1· .
Теоремао приведении формулы к ДНФ.AB, находящаяся в ДНФ, чтоAB.B называется ДНФА.
Доказательство:В качестве доказательства приводят алгоритм построения ДНФ формулыА.
1.С помощью основных равносильностей, которые позволяют устранить операции импликации и эквивалентности, строят. При этомА1не содержит операций импликации и эквивалентности.
Основные равносильности:
1);
2);
3);
4);
5);
6);
7);
8)
2.ОтА1переходят кА2, в которой отрицание только перед переменной1)A1A
2)
Полученная А2равносильнаАи состоит из многочисленных конъюнкций и дизъюнкций. КА2применяют формулу дистрибутивности конъюнкции относительно дизъюнкции. ПолучимА3, находящуюся в дизъюнктивной нормальной форме.
Рассмотрим конъюнкцию х1σ, х2σ2, ... , хnσn (1).
Конъюнкция (1) называется конституентной единицей.
Теорема. f(х1,х2,…,хn) может быть представлена в виде дизъюнкций конституент 1. На любом набореf(х1,х2,…,хn)=1 будет равна 1 и только одна конституента. Дизъюнкция конституент равна 1, если 1 равна хотя бы 1 конституента.
Пример
-
х1
х2
х3
f1(х1, х2, х3)
f2(х1, х2, х3)
0
0
0
1
0
0
0
1
0
0
0
1
0
0
1
0
1
1
1
1
1
0
0
0
0
1
0
1
1
1
1
1
0
1
0
1
1
1
0
1
f1(х1, х2, х3)=131x2x3x1 x3 x1x23.
f2(х1, х2, х3)=1 x231x2x3x1 x3 x1x2х3.
Всякую конъюнкцию переменных функций функций, взятых с отрицанием, называют элементарной дизъюнкцией. Дизъюнкцию элементарных конъюнкций называют дизъюнктивной элементарной формой.
Конъюнктивная нормальная форма.
Аназывается элементарной дизъюнкцией, если она состоит из переменных и их отрицаний, связанных операцией дизъюнкции. Говорят, чтоАнаходится в КНФ, если она представляет собой конъюнкцию, возможно одночленную, элементарных дизъюнкций. КНФ:A=x1& (x2) & (x1).
Теоремао приведении к КНФ.ABA, находящаяся в КНФ.B называется КНФА.
Доказательство: Аналогично теореме 1. Применяют обобщенные законы Де Моргана, чтобы привести операции отрицания к переменным. Применяют формулы дистрибутивности дизъюнкции относительно конъюнкции.A3Aи находится в КНФ.
Найдем КНФ для функций:
-
х1
х2
х3
f1(х1, х2, х3)
f2(х1, х2, х3)
0
0
0
1
0
0
0
1
0
0
0
1
0
0
1
0
1
1
1
1
1
0
0
0
0
1
0
1
1
1
1
1
0
1
0
1
1
1
0
1
f1(х1, х2, х3)= (х1х23 )( х1x3 )(1 х2x3 )(1 3 )
f2(х1, х2, х3)= (х1х2 x3)( х1x3 )(1 х2x3 )(1 x3)