- •Глава 2. Минимизация днф
- •2.1. Введение
- •2.2. Геометрическая интерпретация
- •2.2.1. Интервалы и их свойства
- •2.2.2. Допустимые и максимальные интервалы
- •Свойства максимального интервала:
- •2.3. Методы построения сокращенных днф
- •2.3.1. Метод Квайна–МакКласки
- •2.3.1.1. Представление конъюнкций троичными векторами
- •2.3.1.2. Алгоритм Квайна–МакКласки
- •2.3.1.3. Таблица Квайна и ее покрытия
- •2.3.1.4. Построение всех безызбыточных покрытий
- •Алгоритм
- •2.3.2. Метод Блейка
- •2.4. Получение безызбыточных (тупиковых) днф
- •2.5. Ядро днф
- •2.6. Минимизация частичных булевых функций
- •2.7. Матричное представление булевых функций
- •2.8. Контрольные вопросы к главе 2
2.5. Ядро днф
Определение. Ядром ДНФ D называется совокупность H всех таких конъюнкций:
H = ,
для каждой из которых выполняется условие
.
Иными словами, конъюнкция входит в ядро H ДНФ D, если она не поглощается совокупностью других конъюнкций ДНФ D.
В рассмотренном выше примере конъюнкции , , входят в ядро, остальные – нет.
Будем иметь в виду, если ДНФ является безызбыточной (тупиковой), то каждая ее конъюнкция входит в ядро.
ДНФ, сопоставляемая безызбыточному покрытию функции f( ,…, ), называется безызбыточной или тупиковой.
Теорема 2.7. Конъюнкция k из ДНФ D входит в пересечение тупиковых ДНФ, если и только если она входит в ядро этой ДНФ.
Доказательство. Достаточность. Пусть k входит в ядро. Покажем, что она содержится в пересечении тупиковых ДНФ. Допустим противное, то есть k не содержится в пересечении тупиковых ДНФ. Это значит, что она была исключена при построении одной из тупиковых ДНФ. Однако тогда , то есть не принадлежит ядру ДНФ. Пришли к противоречию.
Необходимость. Пусть k входит в пересечение тупиковых ДНФ. Покажем, что она принадлежит ядру ДНФ. Допустим противное: k не принадлежит ядру. Тогда для нее выполняется условие , то есть k может быть удалена при построении некоторой тупиковой ДНФ. Значит, k не принадлежит пересечению тупиковых ДНФ. Пришли к противоречию. Ч.Т.Д.
КАДР
Будем иметь в виду, что для некоторых функций совершенная ДНФ совпадает с сокращенной и, следовательно, совершенная ДНФ является минимальной и кратчайшей одновременно. Речь идет о совершенной ДНФ, конъюнкции которой попарно ортогональны по двум и более переменным. Такие ДНФ встречаются на практике, представляя, например, кодовые слова равновесных кодов, кодов Бергера и т.д.
Сокращенная ДНФ монотонной функции совпадает со своим ядром и, значит, является минимальной и кратчайшей ДНФ одновременно. Это утверждается в нижеследующей теореме.
Функция называется монотонной, если для любых двух наборов и таких, что , имеет место неравенство f () f ().
Теорема 2.8. Сокращенная ДНФ монотонной функции не содержит отрицаний переменных и является ее единственной минимальной (кратчайшей) ДНФ.
Доказательство. Докажем сначала первую часть утверждения. Рассмотрим простую импликанту k функции f( ,…, ) ранга r и представим ее в виде . Простая импликанта, так же как и функция, обращается в единицу на всяком наборе α значений переменных ,…, , удовлетворяющем условию: = … = = 1, = … = = 0. В силу монотонности функция f( ,…, ) обращается в единицу на всяком наборе , удовлетворяющем условию = … = = 1. Последнее означает, что конъюнкция является импликантой функции f( ,…, ). Тогда конъюнкция k не является простой импликантой этой функции. Пришли к противоречию, следовательно, допущение о наличии отрицаний переменных в простых импликантах сокращенной ДНФ монотонной функции f( ,…, ) не верно.
Итак, на основании только что доказанного произвольная простая импликанта k ранга r монотонной функции f( ,…, ) представляется в виде . Покажем, что она не может быть исключена из сокращенной ДНФ функции. Рассмотрим набор α значений переменных ,…, такой, что в нем = … = = 1, = … = = 0. Покажем, что на этом наборе только конъюнкция k обращается в единицу. Допустим, что найдется другая простая импликанта , которая обращается в единицу на этом наборе. По доказанному ранее не содержит отрицаний переменных. Следовательно, поглощает k, то есть k не является простой импликантой. Пришли к противоречию. Делаем заключение: k является единственной простой импликантой, обращающейся в единицу на наборе α, значит, k нельзя исключить из сокращенной ДНФ. В силу произвольного выбора k ни одну из простых импликант нельзя исключить из сокращенной ДНФ функции f( ,…, ). Значит, сокращенная ДНФ является минимальной (кратчайшей) ДНФ монотонной функции. Ч.Т.Д.
КАДР