- •Дискретная математика
- •Воронеж 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.1. Геометрический метод минимизации булевой функции
Рассмотрим элементарную конъюнкцию ранга r (т.е. содержащую r пропозициональных переменных).
K(X ,...,Xr)=X ... Х ,
где =0,1 ; Х = , . Очевидно, что множество N , соответствующее конъюнкции К, есть (3-r)- мерная грань. Число r называется рангом этой грани.
Пример. Конъюнкциям
K ( )=
К ( )=
К ( )= ,
соответствуют грани, имеющие ранги 2, 2, и 1. Первые две грани являются одномерной гранью (ребром), а третья - двумерной гранью.
Отметим очевидные свойства введенного соответствия между булевой функцией f и подмножеством .
Если f( ) = g( ) h( ), то
1) , ;
2)Nf = Ng Nh.
В частности, если f( ) обладает ДНФ, т. е.
f( )= , то и , т.е. ДНФ функции f соответствует покрытие множества N гранями Nk , ., Nks
Пусть r, - ранг грани Nki (он равен рангу конъюнкции k ) Число r, определенное формулой
называется рангом покрытия. Тогда задача о минимизации булевой функции принимает следующую геометрическую постановку: для данного множества найти такое покрытие гранями, принадлежащими , , чтобы его ранг был наименьшим.
Приведем также определения сокращенной и тупиковой ДНФ с геометрической точки зрения.
Грань , содержащаяс в , называется максимальной относительно , если не существует грани , такой, что
1) ;
2) размерность грани больше размерности грани Nk .
Конъюнкция К, соответствующая максимальной грани , называется простой импликантой функции f.
ДНФ, являющаяся дизъюнкцией всех простых импликант функции f, называется сокращенной ДНФ.
Покрытие множества , состоящее из максимальных относительно
граней, называется неприводимым, если совокупность граней, получающаяся из исходной путем выбрасывания любой грани, не будет покрытием .
ДНФ, соответствующая неприводимому покрытию множества , называется тупиковой в геометрическом смысле.
Теорема 5.7.1. Понятия тупиковой ДНФ и тупиковой ДНФ в геометрическом смысле эквивалентны.
Алгоритм минимизации функций, зависящих от трех переменных, состоит в следующих четырех шагах:
1. Нанести множество N , на трехмерный куб. Использовать или табличное задание функции, отметив вершины, в которых f( ) = 1, или СДНФ функции и тогда каждому слагаемому СДНФ поставить в соответствие вершину.
2. Если отмеченными окажутся все вершины куба, то данная функция тождественно истинна.
. Если отмечены все вершины какой-либо грани, то для построения минимальной формы заменить все четыре вершины одной переменной - названием грани.
. Если отменены вершины какого-либо ребра то в минимизированной форме им соответствует конъюнкция - название ребра.
Чтобы получить минимизированную форму, надо выбирать ребра, покрывающие вершины так, чтобы меньшим числом ребер покрыть все отмеченные вершины.
5. Если существует вершина, которая не образует ребро ни с какой другой вершиной, то в минимизированной форме ей соответствует конъюнкция - название вершины.
Пример. Минимизировать булеву функцию f(0,1,1)=f(1,0,0)=f(1,0,1)=0 геометрическим методом.
Так как функция задана перечислением наборов, на которых функция принимает значение 0, то на остальных она принимает эначение 1, т.е.
f(0,0,0)=f(0,0,1)=f(0,1,0)=f(1,1,0)= f(1,1,1)=1.
На рис. 5.2 изображено геометрическое представление данной булевой функции с указанием наборов и соответствующих им элементарных конъюнкций.
; ; ;
.
Из геометрического представления булевой функции следует, что осуществить покрытие вершин можно не единственным образом, поэтому существует для данной булевой функции две различные минимизированные формы и .
Замечание. При n=3 геометрический метод минимизации булевых функций аналогичен минимизации с помощью прямоугольной таблицы, называемой минимизирующей картой (картой Карно) [4].