Алгебраическая нормальная форма

Алгебраическая нормальная форма (АНФ) для логической функции — это упрощённый полином Жегалкина, построенный для данной функции.

При этом таблицы истинности для логической функции и её АНФ совпадают.

Обозначения

n — число аргументов функции;

(x₁, x₂, …, x_n) — набор аргументов функции;

f(x₁ ,x₂, …, x_n) — логическая функция;

f_АНФ(x₁, x₂, …, x_n) — АНФ логической функции.

Формула

$f_{\text{АНФ}}(x_{1},\ldots ,x_{n})=a_{0}\oplus a_{1}x_{1}\oplus \ldots \oplus a_{n}x_{n}\oplus a_{12}x_{1}x_{2}\oplus \ldots \oplus a_{n-1,n}x_{n-1}x_{n}\oplus \ldots \oplus a_{1\ldots n}x_{1}\ldots x_{n}\Leftrightarrow$

$\Leftrightarrow f_{\text{АНФ}}(x_{1},\ldots ,x_{n})=a_{0}\oplus \sum \limits _{1\leqslant i_{1}<\ldots <i_{k}\leqslant n}a_{i_{1}\ldots i_{k}}x_{i_{1}}\ldots x_{i_{k}}\Leftrightarrow$

$\Leftrightarrow f_{\text{АНФ}}(x_{1},\ldots ,x_{n})=a_{0}\oplus \sum \limits _{1\leqslant i_{1}<\ldots <i_{k}\leqslant n}a_{i_{1}\ldots i_{k}}\prod \limits _{j=1}^{k}x_{i_{j}}$

• Заметим, что коэффициенты a_i1…ik принимают значения из множества {0; 1}, причём если коэффициент равен нулю, то соответствующее слагаемое должно быть опущено.

Методы построения АНФ

• метод эквивалентных преобразований;
• метод неопределённых коэффициентов.

Метод эквивалентных преобразований

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

Метод неопределённых коэффициентов

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

Другие формы:

• совершенная дизъюнктивная нормальная форма;
• совершенная конъюнктивная нормальная форма;
• минимальная дизъюнктивная нормальная форма;
• минимальная конъюнктивная нормальная форма);
• алгебраическая нормальная форма.