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

Материал из Циклопедии
Перейти к: навигация, поиск
АНФ01.JPG

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

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


Содержание

[править] Обозначения

Введём обозначения:

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

(x1, x2, …, xn) — набор аргументов функции;

f(x1 ,x2, …, xn) — логическая функция;

fАНФ(x1, x2, …, xn) — АНФ логической функции.

[править] Формула

[math]f_\text{АНФ}(x_1,\ldots,x_n)=a_0\oplus a_1x_1\oplus \ldots \oplus a_nx_n \oplus a_{12}x_1x_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[/math]
[math]\Leftrightarrow f_\text{АНФ}(x_1,\ldots,x_n)=a_0\oplus \sum\limits_{1 \leqslant i_1 \lt \ldots \lt i_k \leqslant n}a_{i_1\ldots i_k}x_{i_1}\ldots x_{i_k} \Leftrightarrow[/math]
[math]\Leftrightarrow f_\text{АНФ}(x_1,\ldots,x_n)=a_0\oplus \sum\limits_{1 \leqslant i_1 \lt \ldots \lt i_k \leqslant n}a_{i_1\ldots i_k}\prod\limits_{j=1}^kx_{i_j}[/math]
  • Заметим, что коэффициенты ai1…ik принимают значения из множества {0; 1}, причём если коэффициент равен нулю, то соответствующее слагаемое должно быть опущено.

[править] Методы построения АНФ

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

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

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

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

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

[править] Другие формы

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты