Сокращённая ДНФ и способы её построения

Сокращённая ДНФ функции f — дизъюнкция всех простых импликант этой функции. Геометрически она соответствует покрытию \(N_f\) всеми максимальными по включению гранями, лежащими в \(N_f\). Поэтому сокращённая ДНФ определяется самой функцией однозначно с точностью до порядка конъюнктов и не содержит поглощений.1

Её можно строить геометрически по максимальным граням, по карте Карно для небольшого числа переменных, алгебраически из КНФ после раскрытия скобок и удаления поглощений или методом Блейка через последовательные обобщённые склеивания.1

Что важно запомнить
  • Сокращённая ДНФ содержит все простые импликанты функции.
  • Геометрически это все максимальные грани, содержащиеся в \(N_f\).
  • Сокращённая ДНФ не обязательно минимальна или кратчайша.
  • Основные способы построения: максимальные грани/карта Карно, преобразование КНФ, метод Блейка с обобщённым склеиванием.1

Определение и геометрический смысл

После нахождения всех простых импликант K1,…,Ks их дизъюнкция K1∨…∨Ks называется сокращённой ДНФ функции f. Поскольку простые импликанты соответствуют всем максимальным граням множества \(N_f\), сокращённая ДНФ представляет полное покрытие \(N_f\) этими максимальными гранями.1

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

Геометрический способ

Если функция задана таблицей, можно отметить её единичные вершины в \(B^n\) и найти все максимальные грани, целиком лежащие в \(N_f\). Каждой такой грани соответствует простая импликанта. Для небольшого числа переменных эту процедуру удобно выполнять с помощью карты Карно, где максимальные прямоугольные группы соседних единиц соответствуют максимальным граням.1

Построение из КНФ

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

Метод Блейка

Из произвольной ДНФ сокращённую форму можно получить последовательными обобщёнными склеиваниями. Если в ДНФ есть члены \(x_iK\)' и \(\neg x_iK\)'', к ним добавляют K'K'', после чего выполняют приведение подобных и поглощения. Процесс продолжают, пока ДНФ без поглощений не перестанет иметь строгие расширения. Теорема 3.2 курса утверждает, что именно тогда она сокращённая.1

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

Пример простыми словами

Для функции большинства трёх переменных f=1, когда хотя бы две переменные равны 1, максимальными гранями являются x1x2, x1x3 и x2x3. Поэтому сокращённая ДНФ имеет вид x1x2 ∨ x1x3 ∨ x2x3. Удалить литерал из любого из этих конъюнктов нельзя: соответствующая грань вышла бы за множество единиц функции.

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

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 1, §3, теоремы 3.1–3.2, МГУ, факультет ВМК