6.Сокращенная днф.

Познакомимся с сопутствующими понятиями.

Максимальная грань: N_k называется максимальной гранью, если не существует N_k’ такая, что:

1. N_k N_f N_k’ ;

2. размерность грани N_k’ больше размерности N_k .

Пример:

для каждой конъюнкции найдем грани и выявим максимальные:

N_k1 ={(000), (100)}- одномерная, максимальная,

N_k2 ={(100), (101)}- одномерная, является подмножеством N_k3, или, покрывается гранью N_k3, поэтому не является максимальной.

N_k3 ={(100), (110), (101), (111)}- двухмерная, максимальная.

Конъюнкции, соответствующие максимальным граням, называются простыми импликантами.

В нашем примере простыми импликантами будут К₁ и К₃.

ДНФ, являющаяся дизъюнкцией всех простых импликант функции f, называется сокращенной ДНФ.

Алгоритм построения сокращенной ДНФ:

1. составить какую-либо КНФ функции (можно СКНФ);

2. раскрыть скобки;

3. удалить нулевые члены, поглащаемые и дублирующие, т.е. К₁К₂VK₁ K₁, K₁VK₁ K₁.

Полученная ДНФ состоит только из простых импликант и является сокращенной.

Пример: Для функции построить сокращенную ДНФ.

Путем равносильных преобразований составим какую-либо КНФ и, выполняя пункты 2 и 3 алгоритма, получим сокращенную ДНФ:

Найдем грани конъюнкций:

N_k1 = {(000), (010)}- одномерная, максимальная,

N_k2 = {(100), (101)}- одномерная, максимальная,

N_k3 = {(000), (100)}- одномерная, максимальная.

Соответствующий рисунок:

7.Тупиковая днф. Днф Квайна.

Построение сокращенной ДНФ является первым шагом в процессе получения минимальной ДНФ. Следующий шаг минимизации – это построение, так называемых, тупиковых ДНФ.

Дадим определение тупиковой ДНФ:

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

ДНФ, которая соответствует неприводимому покрытию, называется тупиковой ДНФ.

Минимальная ДНФ содержится среди тупиковых.

Тупиковые ДНФ получаются путем выбрасывания из сокращенной ДНФ некоторых простых импликант.

Существуют алгоритмы, при помощи которых получаются единственные для данной функции тупиковые ДНФ. К таким тупиковым ДНФ относится ДНФ Квайна.

Введем сопутствующие понятия.

Ядровая грань: максимальная грань называется ядровой, если ей принадлежит вершина, принадлежащая покрытию N_f только этой грани и не принадлежащая никакой другой максимальной грани.

Множество всех ядровых граней покрытия N_f , называется ядром N_f .

Теперь познакомимся с определением ДНФ Квайна:

ДНФ, которую получают путем выбрасывания всех простых импликант, соответствующих максимальным граням, которые покрываются ядром, называется ДНФ Квайна.

Алгоритм построения ДНФ Квайна:

1. получить сокращенную ДНФ;

2. найти ядровые грани;

3. удалить импликанты, покрываемые ядром.

Полученная ДНФ, является ДНФ Квайна.

В предыдущем примере N_k3 – не является ядровой гранью, т.к. каждая вершина принадлежит другим граням. Тогда сокращенную ДНФ можно еще раз минимизировать, выбросив конъюнкцию , получим ДНФ Квайна : .

Оставшиеся грани N_k1 и N_k2 покрывают N_f . Продемонстрируем это на рисунке:

Отметим справедливость следующего утверждения:

Для любой не тождественно ложной функции существует единственная ДНФ Квайна.

Задачи для самостоятельного решения.

1. Минимизировать функцию, принимающую значение 1, если большинство переменных равны 1, методом минимизирующих карт.

2. Для формулы составить множество N_f и изобразить его вершинами куба. Минимизировать методом Карно. Составить сокращенную ДНФ. Определить ядровые грани. Составить ДНФ Квайна.

3. Графически представлено нольмерное покрытие множества N_f . Составить СДНФ и СКНФ. Составить покрытие ядровыми гранями и записать соответствующую ДНФ Квайна. По данному рисунку составить карту Карно и минимизировать функцию. Сравнить результаты.

4. Дана функция f(00101110). Составить множество N_f и изобразить его графически.

5. Для функции из задания 4 составить СКНФ и сокращенную ДНФ. Изобразить сокращенную ДНФ. Найти ядровые грани и построить ДНФ Квайна.

6. Функция представлена картой Карно. Построить минимальную ДНФ с помощью этой карты.

c

d

0 b	1	1	0
0	0	1	1
0 а	0	1	1
0	1	1	0

7. Дана функция от четырех переменных f(2,3,6,7,11,13,14,15)=1. Минимизировать ее методом Квайна и методом Карно.

Контрольные вопросы

1. Определение минимальной ДНФ.

2. Что собой представляет минимизирующая карта?

3. Сформулировать утверждение, которое используется в методе минимизирующих карт.

4. Алгоритм построения минимальной ДНФ с помощью минимизирующей карты.

5. Этапы минимизации СДНФ при применении метода Квайна.

6. Что представляет собой карта Карно?

7. Сколько ячеек можно включать в контуры и почему?

8. Что представляет собой единичный n-мерный куб?

9. Какие наборы входят в множество N_f ?

10. Что называется (n-r)- мерной гранью? Как определяется ранг конъюнкции и ранг ДНФ?

11. Задача минимизации в геометрической форме.

12. Какая грань называется максимальной? Что такое простая импликанта? Какая ДНФ называется сокращенной?

13. Методика построения сокращенной ДНФ.

14. Какое покрытие называется неприводимым? Какие ДНФ называются тупиковыми?

15. Алгоритм построения ДНФ Квайна.