Задать вопрос юристу

2.2.2.3. Построение всех тупиковых ДНФ

Определение. Тупиковой ДНФ (ТДНФ) функции f называется такая ДНФ ее простых импликант, из которых нельзя выбросить ни одного импликанта, не изменив функции f.

Теорема. Всякая минимальная ДНФ некоторой функции является ее тупиковой ДНФ.

Для получения МДНФ функции f необходимо построить все ТДНФ функции f и выбрать те из них, которые содержат минимальное число букв.

Алгоритм построения всех тупиковых ДНФ.

Пусть f(x1, x2, …, xn) есть булева функция.

Шаг 1. Построим СДНФ функции f и пусть P1, P2, …,Pn есть ее конституенты (единицы).

Шаг 2. Построим сокращенную ДНФ функции f и пусть К1, К2, …, Кm – ее простые импликанты.

Шаг 3. Построим матрицу покрытий простых импликант функции f ее коституентами единицы (табл. 34), полагая, что

Таблица 34

N P1 P2 Pj Pn
K1 a11 a12 a1j a1n
K2 a21 a22 a2j a2n
Ki ai1 ai2 aij ain
Km am1 am2 amj amn

Шаг 4. Для каждого столбца j (1 £ j £ n)найдем множество Ej всех тех номеров i строк, для которых aij=1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …, m и с операциями конъюнкции и дизъюнкции.

Шаг 5. В выражении А раскроем скобки приведя выражение А к равносильному выражению , где перечислены все конъюнкции элементы ei1, ei2, …, ein которой взяты из скобок 1, 2, …, n соответственно в выражении А.

Шаг 6. В выражении В проведем все операции удаления дублирующих членов и все операции поглощения. В результате получим равносильное выражение С, представляющее собой дизъюнкцию элементарных конъюнкций.

Пример 38.

Построить все минимальные ДНФ для функции f=1111010010101111.

Решение.

Сокращенная ДНФ для данной функции имеет вид

Строим матрицу покрытий (табл. 35).

Таблица 35

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - - + + + +
2 0 0 - - + + + +
3 - 0 - 0 + + + +
4 1 - - 0 + + + +
5 0 - 0 1 + +
6 - 1 0 1 + +

Пошагово будем выбирать слагаемые, которые войдут в минимальную ДНФ. Если слагаемое нами выбрано, то мы помечаем конституенты единицы функции f, которые будут покрыты (по строке). При этом автоматически исключаем из рассмотрения конституенты единицы, которые уже покрыты, но относятся к другим слагаемым сокращенной ДНФ.

Шаг 1. Выбираем слагаемое 1 (табл. 36):

Таблица 36

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - - + + + +
2 0 0 - - + + + +
3 - 0 - 0 + + + +
4 1 - - 0 + + + +
5 0 - 0 1 + +
6 - 1 0 1 + +

Шаг 2. Выбираем слагаемое 2 (табл. 37):

Таблица 37

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - - + + + +
2 0 0 - - + + + +
3 - 0 - 0 + + + +
4 1 - - 0 + + + +
5 0 - 0 1 + +
6 - 1 0 1 + +

Шаг 3.

Выбираем слагаемое 4 (табл. 38):

Таблица 38

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - - + + + +
2 0 0 - - + + + +
3 - 0 - 0 + + + +
4 1 - - 0 + + + +
5 0 - 0 1 + +
6 - 1 0 1 + +

Шаг 4. Выбираем слагаемое 5 (табл. 39):

Таблица 39

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - - + + + +
2 0 0 - - + + + +
3 - 0 - 0 + + + +
4 1 - - 0 + + + +
5 0 - 0 1 + +
6 - 1 0 1 + +

Поскольку все конституенты единицы покрыты, то одна из ТДНФ имеет вид

Поскольку выбор включаемых слагаемых произволен, то функция может иметь несколько ТДНФ. Для рассматриваемой функции существует еще несколько ТДНФ:

Все найденные ТДНФ являются минимальными ДНФ.

Пример 39.

Построить одну из МДНФ функции f=11100101.

Решение.

Сокращенная ДНФ для данной функции имеет вид

Строим матрицу покрытий (табл. 40):

Таблица 40

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 010 101 111
1 0 0 - + +
2 0 - 0 + +
3 1 - 1 + +
4 - 0 1 + +

Шаг 1. Выбираем слагаемое 3 (табл. 41):

Таблица 41

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 010 101 111
1 0 0 - + +
2 0 - 0 + +
3 1 - 1 + +
4 - 0 1 + +

Шаг 2. Выбираем слагаемое 2 (табл. 42):

Таблица 42

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 010 101 111
1 0 0 - + +
2 0 - 0 + +
3 1 - 1 + +
4 - 0 1 + +

Шаг 3. Выбираем слагаемое 1(табл. 43):

Таблица 43

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 010 101 111
1 0 0 - + +
2 0 - 0 + +
3 1 - 1 + +
4 - 0 1 + +

В результате получаем МДНФ:

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 2.2.2.3. Построение всех тупиковых ДНФ:

  1. 2.2.2.1. Алгоритм Куайна построения сокращенной ДНФ
  2. 2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм
  3. Минимизация ДНФ
  4. Алгоритм получения тупиковой д. н. ф.
  5. 2.2.2.4. Алгоритм минимизации функций в классе ДНФ
  6. 1.1.5 Остаточная нефть в тупиковых порах и микронеоднородных зонах
  7. ТУПИКОВАЯ ВОЙНА
  8. Заявлялось о ликвидации всех сословных привилегий, всех личных и поземельных платежей и
  9. Виновные подвергались лишению всех прав состояния и смертной казни (статья 263), лишению всех прав
  10. § 8. Продажа предприятия (ст. 559-566) 129. Допускается ли отчуждение всех (или практически всех) активов лица, используемых для ведения предпринимательской деятельности, в иных формах, нежели продажа предприятия?
  11. А5. Синтаксические нормы (нормы согласования, управления, построение предложений с однородными членами, построение сложноподчиненных предложений).
  12. 1.4. ПОСТРОЕНИЕ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ* СВОБОДНОЙ ОТ СОСТЯЗАНИЙ
  13. 5. Сомневайтесь во всех источниках
  14. Как учить всех?
  15. ОБОГНАТЬ ВСЕХ
  16. 8. О принципе всех этих функций
  17. Четыре импульса всех холонов
  18. Страхование «от всех рисков»
  19. Визер: с позиции всех
  20. Пролог (для всех)