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

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

Обозначения

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

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

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

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

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

P(x₁,x₂,…,x_n) – полином Жегалкина.

Общий вид

Полином Жегалкина имеет следующий вид:

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

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

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

Эквивалентные преобразования

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

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

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

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

• Совершенная дизъюнктивная нормальная форма (СДНФ);
• Совершенная конъюнктивная нормальная форма (СКНФ);
• Минимальная дизъюнктивная нормальная форма (МДНФ);
• Минимальная конъюнктивная нормальная форма (МКНФ);
• Алгебраическая нормальная форма (АНФ).

Ссылки

• Википедия.
• Участник:Logic-samara