- •Дискретная математика
- •Воронеж 2012
- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия и определения теории множеств
- •1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
- •1.3. Мощность множества
- •1.4. Взаимно однозначное соответствие между множествами
- •1.5. Счетные и несчетные множества
- •Задачи и упражнения
- •2. Элементы теории отношений
- •2.1. Бинарные отношения. Свойства отношений
- •2.2. Отношение эквивалентности и разбиения
- •2.3. Отношения порядка. Диаграмма Хассе
- •Задачи и упражнения
- •3. Функции, отображения и операции
- •4. Элементы теории графов
- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Алгебра логики
- •5.1. Операции над высказываниями
- •5.2. Правила записи сложных формул
- •5.3. Таблицы истинности
- •5.4. Равносильность формул
- •5.5. Дизъюнктивные и конъюнктивные нормальные формы
- •5.5.1. Аналитический способ приведения к сднф
- •5.5.2. Табличный способ приведения к сднф
- •5.5.3. Табличный способ приведения к скнф
- •5.7. Геометрическое представление булевых функций
- •5.7.1. Геометрический метод минимизации булевой функции
- •Задачи и упражнения
- •6. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
5.7. Геометрическое представление булевых функций
Обозначим через множество всех наборов , состоящих из чисел ноль и единица. Множество называется п-мерным кубом, а набор - вершинами куба.
Пусть - фиксированный набор чисел из 0 и 1. Множество всех вершин куба Е таких, что , ,…, , 1<i <i <…<i , называется (п-r)-мерной гранью. Очевидно, что (n-r)-мерная грань является (n-r)-подкубом куба Е .
Например, в трехмерном кубе Е3 наборы (0, 0, 1) и (0, 0, 0) образуют одномерную ( n=3, r=2) грань ( ребро), а наборы (1, 0, 0), (1, 0, 1), (1, 1, 0), (1,1, 1) - двухмерную грань.
Пусть f( ) — произвольная булева функция. Ей сопоставляется в соответствие подмножество вершин куба Е , таких что тогда и только тогда, когда f =l. Очевидно, что по подмножеству исходная функция f( ) восстанавливается однозначно. Таким образом, геометрический способ задания булевой функции заключается в задании множества вершин п-мерного куба Е , в которых данная функция истинна.
Пример. Пусть функция f( ) задана таблицей истинности. Составить для нее множество .
x |
y |
z |
f( ) |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Очевидно, что
Nf={(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0)(1,1,1)}. Множество можно изобразить следующим образом. Рассмотреть вершины трехмерного куба (или просто куба), каждой вершине поставить в соответствие набор из нулей и единиц. Для этого одну из вершин поместить в начало декартовой системы координат, при этом три вершины должны оказаться на координатных осях. Считая, что ребро куба равно единице, каждой вершине поставим в соответствие набор из нулей и единиц, соответствующий координатам вершины в декартовой системе. Для наглядного изображения геометрического представления булевой функции выделяют вершины куба, в которой функция принимает значение 1. На рис. 5.1 изображено геометрическое представление рассмотренной булевой функции.
Z
(0,0,1)
(0,1,1)
(1,0,1)
(1,1,1)
(0,0,0)
(1,0,0) (0,1,0 )
Y
X (1,1,0)
Рис. 5.1. Геометрическое представление булевой функции
Для любой булевой функции существует ее представление в СДНФ. Причем в алгоритме построения СДНФ используются только те наборы значений, при которых функция равна единице. Это позволяет проинтерпретировать геометрическое представление функции следующим образом. Рассмотрим, например, ребро куба, представленное вершинами (1,0,0) и (1,0,1), им соответствуют элементарные конъюнкции и . Ребру (одномерному подкубу) соответствует формула .
Аналогично можно получить формулы, описывающие грани (двумерные подкубы). Например, описанию грани куба, представленной вершинами (1,0,0), (1,0,1), (1,1,0) и (1,1,1), соответствует формула . Описанию грани куба, представленной вершинами (0,0,0), (0,0,1), (0,1,0) и (0,1,1), соответствует формула .
Замечание. Для функций, зависящих от четырёх и более переменных, геометрическое представление применяется очень редко, т.к. трудно построить наглядную модель n - мерного куба при n>3.
Перейдем теперь к геометрической постановке задачи минимизации булевых функций.