Минимизация ДНФ

Определение. Элементарная конъюнкция u называется импликантой булевой функции F , если .

Например, элементарная конъюнкция является импликантой функции .

Определение. Если никакая собственная часть импликанты u (т.е. ) булевой функции F не является импликантой F, то u называется простой импликантой (т.е. если удаление из u хотя бы одного литерала нарушает условие , то u – простая импликанта).

Например, – простая импликанта булевой функции , а импликанта не является простой для этой функции , так как (собственная часть импликанты ) является импликантой функции F .

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

Например, – СкДНФ булевой функции . Отметим, что СкДНФ является единственной для конкретной булевой функции F .

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

Например, – КрДНФ этой же булевой функции F .

Вообще говоря, для заданной булевой функции F существу­ет несколько различных по числу вхождений литералов КрДНФ.

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

Отметим, что для заданной булевой функции F существует, вообще говоря, несколько МДНФ, отличающихся друг от друга чис­лом слагаемых.

Более того, МДНФ не всегда совпадает с КрДНФ булевой функции n переменных F . Хотя для начальных значе­ний n ( n = 2 или n = 3 ) МДНФ всегда совпадает с КрДНФ). Например, является КрДНФ и МДНФ рассматриваемой функции F.

Задача минимизации булевой функции в классе ДНФ формулируется следующим образом: тре­буется для булевой функции n переменных F построить ДНФ с минимально возможным числом слагаемых (КрДНФ) или с мини­мально возможным числом вхождений литералов (МДНФ).

Причем, если раньше (при синтезе контактных схем) основное внимание уделялось построению МДНФ, то в настоящее время (при синтезе логических схем на элементах И,ИЛИ,НЕ, И-НЕ и др.) требуется построение КрДНФ.

Также отметим, что задача минимизации булевых функций n переменных F в классе ДНФ является чрезвычайно громоз­дкой и ее трудоемкость с ростом n возрастает по экспонен­циальному закону.

К настоящему времени разработано около 200 различных ме­тодов минимизации булевых функций в классе ДНФ, наиболее из­вестными среди которых являются метод Квайна - Мак-класки, метод Блейк-Порецкого, метод Нельсона, метод неопределенных коэффициентов и др.

Пример. Составить по таблице истинности СДНФ булевой функции и минимизировать ее, применяя законы склеивания.

Решение

0 0 0 1 1 1
0 0 1 0 1 1
0 1 0 1 1 1
0 1 1 1 1 1
1 0 0 1 0 0
1 0 1 0 0 1
1 1 0 1 0 0
1 1 1 1 0 0

СДНФ будет иметь вид .

Минимизируем ее, применяя законы склеивания. Подчеркнем конъюнкции, которые можно склеить. Очевидно, что это можно сделать различными способами, например:

,

,

,

.

Выберем один из возможных вариантов склеивания, например: и минимизируем ДНФ:

.

Замечание. При минимизации ДНФ достаточно часто (но не всегда!) удается получить лучшие результаты, если «нарастить» данную ДНФ, используя свойство идемпотентности дизъюнкции: .

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

.

Пример. Составить СДНФ булевой функции, заданной вектором значений таблицы истинности w(F)=(10010010), и минимизировать ее, применяя законы склеивания.

Решение. Так как вектор значений заданной булевой функции имеет 8=23 разрядов, следовательно, булевой функции соответствует следующая таблица истинности:

F
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

СДНФ будет иметь вид: .

К сожалению, минимизировать ее, применяя законы склеивания, невозможно.

<< | >>
Источник: БУЛЕВЫ ФУНКЦИИ. Лекция. 2016

Еще по теме Минимизация ДНФ:

  1. 3.5. Минимизация издержек при выборе и использовании факторов производства
  2. 3.2.2 Минимизация ресурсных требований к программной реализации
  3. 2.2.3. Сравнение МСП, RBF и СНРБ-сетей.
  4. 1.4. Функции страхования
  5. 1. Стратегия минимизации издержек
  6. 12.2. Качество менеджмента
  7. Минимизация целевой функции на основе адаптивных алгоритмов
  8. Глава 4. БЕЗРАБОТИЦА В ЭКОНОМИКЕ РОССИИ: ПРИЧИНЫ, ОСОБЕННОСТИ И ПУТИ МИНИМИЗАЦИИ
  9. § 8. Пути минимизации безработицы
  10. ФОРМИРОВАНИЕ НАЛОГОВОЙ ПОЛИТИКИ ПРЕДПРИЯТИЯ
  11. Экономическая сущность и классификация капитала предприятия.
  12. Управление привлечением товарного коммерческого кредита
  13. Минимизация сети
  14. И.В. Чикенева, Е.Е. Лутовина. Аварийно -спасательные работы как минимизация экологических рисков: учебное пособие / авт.-сост. И. В. Чикенева, Е.Е. Лутовина. Мин-во образования и науки РФ, Оренбург. гос. пед. ун-т. — Оренбург,2016.-143с., 2016
  15. 5.2.3. Метод минимизации..