<<
>>

2.2.2. Минимизация нормальных форм

Выше было сказано, что произвольная булева функция может быть представлена формулой в дизъюнктивной и конъюнктивной нормальной форме. Равносильными преобразованиями можно получить формулу, содержащую меньшее, чем исходная, число переменных.

Определение. Минимальной ДНФ (МДНФ) функции f(x1, x2, …, xn) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими ДНФ, реализующими функцию f.

Минимальную ДНФ данной формулы можно найти, перебрав конечное число равносильных ей ДНФ и выбрав среди них ту, которая содержит минимальное число переменных. Однако при большом числе переменных такой перебор практически невыполним. Существуют эффективные способы нахождения минимальной ДНФ. Рассмотрим два из них.

Каждый из рассмотренных ниже методов состоит из двух этапов:

· построение сокращенной ДНФ;

· построение матрицы покрытий. Построение МДНФ.

Определение. Если для всякого набора а = (а1, а2, …, an) значений переменных условие g(a) = 1 влечет f(a) = 1, то функция g называется частью функции f (или функция f накрывает функцию g). Если при этом для некоторого набора с = (с1, с2, …, сn)функция g(c)=1, то говорят, что функция g накрывает единицу функции f на наборе с (или что g накрывает конституенту единицы функции f).

Конституента единицы функции f есть часть функции f, накрывающая единственную единицу функции f.

Определение. Элементарная конъюнкция К называется импликантом функции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1.

Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f.

Всякий импликант функции f есть часть функции f.

Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.

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

Утверждение. Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

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

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

Еще по теме 2.2.2. Минимизация нормальных форм:

  1. ФОРМЫ И ГРАНИЦЫ ТЕНЕВОЙ ИНСТИТУЦИОНАЛИЗАЦИИ ЧЕЛОВЕКА
  2. ФОРМА СЛОВА И ЧАСТИ РЕЧИ В РУССКОМ ЯЗЫКЕ [ПЕЧАТАЕТСЯ ВПЕРВЫЕ. НАПИСАНО В 1943 г.]
  3. ФОРМЫ СРАВНИТЕЛЬНОЙ СТЕПЕНИ (КОМПАРАТИВ)
  4. § 151. Формы винительного падежа одушевленных и неодушевленных существительных
  5. СПОСОБЫ ЗАДАНИЯ И ФОРМЫ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ
  6. 1.4. ПОСТРОЕНИЕ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ* СВОБОДНОЙ ОТ СОСТЯЗАНИЙ
  7. Псевдолюбовь и ее формы
  8. Псевдолюбовь и ее формы
  9. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  10. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  11. §1.6. Дизъюнктивные нормальные формы
  12. Дизъюнктивные нормальные формы
  13. Конъюнктивные нормальные формы
  14. 2.1.4. Нормальные формы
  15. 2.1.5.Совершенные нормальные формы
  16. 2.2.2. Минимизация нормальных форм
  17. 2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм
  18. 2.2.2.4. Алгоритм минимизации функций в классе ДНФ
  19. 2.2 Дизъюнктивные нормальные формы.
  20. 1.7. Формы представления высказываний