Дизъюнктивные нормальные формы: представление ФАЛ, совершенная ДНФ и критерий единственности

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

Совершенная ДНФ строится по всем единичным наборам функции: каждому \(\alpha \in N_f\) соответствует конъюнкция ранга n, в которой для \(\alpha_i=1\) берут \(x_i\), а для \(\alpha_i=0\) — \(\neg x_i\). Совершенная ДНФ определена однозначно, однако она является единственной вообще ДНФ функции на переменных X(n) только тогда, когда в \(N_f\) нет соседних наборов.1

Что важно запомнить
  • ДНФ — дизъюнкция элементарных конъюнкций.
  • Совершенная ДНФ содержит по одному минтерму для каждой единицы функции.
  • Геометрически произвольная ДНФ покрывает \(N_f\) гранями, а совершенная ДНФ — отдельными вершинами.
  • Критерий единственности: совершенная ДНФ является единственной ДНФ на X(n) тогда и только тогда, когда в \(N_f\) нет соседних вершин.1

Дизъюнктивная нормальная форма

Литералом называют переменную \(x_i\) или её отрицание \(\neg x_i\). Элементарная конъюнкция — конъюнкция литералов различных переменных. Дизъюнктивная нормальная форма является дизъюнкцией различных элементарных конъюнкций. Если \(A=K_1\vee\cdots\vee K_s\) реализует f, то соответствующие грани \(N_{K_{1}},\ldots,N_{K_s}\) образуют покрытие множества единиц \(N_f\).1

Совершенная ДНФ

В совершенной ДНФ каждый конъюнкт содержит все рассматриваемые переменные и поэтому имеет ранг n. Для каждого набора \(\alpha =(\alpha_{1},\ldots,\alpha_n)\), на котором \(f(\alpha)=1\), строят один минтерм: \(x_i\) включают без отрицания при \(\alpha_i=1\) и с отрицанием при \(\alpha_i=0\) — \(\neg x_i\). Дизъюнкция всех этих минтермов и есть совершенная ДНФ. Таким образом, она является прямой алгебраической записью таблицы истинности.1

Геометрически каждый минтерм соответствует грани размерности 0, то есть одной вершине. Поэтому совершенная ДНФ покрывает \(N_f\) вершинами по отдельности. Обычная ДНФ может объединять соседние единичные вершины в грани большей размерности и тем самым использовать конъюнкции меньшего ранга.

Критерий единственности

Совершенная ДНФ функции f на переменных X(n) является единственной ДНФ этой функции тогда и только тогда, когда в \(N_f\) нет соседних наборов. Если две единичные вершины соседние, их можно объединить в ребро куба. Этому ребру соответствует элементарная конъюнкция ранга \(n-1\), поэтому возникает другая ДНФ. Если соседних единиц нет, ни одной грани положительной размерности внутри \(N_f\) построить нельзя, и иного покрытия элементарными конъюнкциями не возникает.1

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

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

Для функции XOR двух переменных множество единиц равно {(0,1),(1,0)}. Эти две вершины находятся на расстоянии Хэмминга 2 и не являются соседними. Поэтому совершенная ДНФ \(\neg x_{1}\cdot x_{2} \vee x_{1}\cdot \neg x_{2}\) является не только совершенной, но и единственной ДНФ этой функции на переменных \(x_{1},x_{2}\).

Частые ошибки
  • Считать, что любая функция имеет только одну ДНФ. Однозначна совершенная ДНФ, но другие эквивалентные ДНФ обычно существуют.
  • Путать критерий единственности ДНФ с единственностью совершенной ДНФ.
  • Забывать, что критерий формулируется для фиксированного множества переменных X(n).

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

Источники

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