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

В булевой алгебре , тем алгебраической нормальной формой ( АНФ ), кольцо сумма нормальной формы ( RSNF или RNF ), Жегалкина нормальной форме , или расширения Рида-Мюллера представляет собой способ записи логических формул в одном из трех подформ:

Вся формула истинна или ложна:

1

0
Одна или несколько переменных объединяются вместе в терм, затем один или несколько терминов объединяются вместе в ANF. Нет НОТы не допускаются:
а ⊕ б ⊕ аб ⊕ абв

или в стандартных пропозициональных логических символах:

{\ Displaystyle а \ вибар б \ вибар \ влево (а \ клин б \ вправо) \ вибар \ влево (а \ клин б \ клин с \ вправо)}

Предыдущая подформа с чисто правдивым термином:
1 ⊕ a ⊕ b ⊕ ab ⊕ abc

Формулы, записанные в ANF, также известны как многочлены Жегалкина ( русский язык : полиномы Жегалкина ) и выражения Рида – Маллера с положительной полярностью (или четностью) (PPRM).

Общее использование

ANF - это нормальная форма , что означает, что две эквивалентные формулы преобразуются в одну и ту же ANF, что легко показывает, эквивалентны ли две формулы для автоматического доказательства теорем . В отличие от других нормальных форм, он может быть представлен как простой список списков имен переменных. Конъюнктивные и дизъюнктивные нормальные формы также требуют записи, отрицается ли каждая переменная. Нормальная форма отрицания не подходит для этой цели, поскольку в ней не используется равенство в качестве отношения эквивалентности: a ∨ ¬a не сводится к тому же самому, что и 1, даже если они равны.

Ввод формулы в ANF также упрощает идентификацию линейных функций (используемых, например, в регистрах сдвига с линейной обратной связью ): линейная функция - это функция, которая представляет собой сумму отдельных литералов. Свойства регистров сдвига с нелинейной обратной связью также можно вывести из определенных свойств функции обратной связи в ANF.

Выполнение операций в алгебраической нормальной форме

Есть простые способы выполнения стандартных логических операций над входами ANF, чтобы получить результаты ANF.

XOR (логическая исключающая дизъюнкция) выполняется напрямую:

( 1 ⊕ x ) ⊕ ( 1 ⊕ x ⊕ y )

1 ⊕ x ⊕ 1 ⊕ x ⊕ y

1 ⊕ 1 ⊕ x ⊕ x ⊕ y

у

НЕ (логическое отрицание) - это XORing 1:

¬ (1 ⊕ x ⊕ y)

1 ⊕ (1 ⊕ x ⊕ y)

1 ⊕ 1 ⊕ x ⊕ y

х ⊕ у

И (логическое соединение) распределяется алгебраически

( 1 ⊕ x ) (1 ⊕ x ⊕ y)

1 (1 ⊕ x ⊕ y) ⊕ x (1 ⊕ x ⊕ y)

(1 ⊕ x ⊕ y) ⊕ (x ⊕ x ⊕ xy)

1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy

1 ⊕ x ⊕ y ⊕ xy

ИЛИ (логическая дизъюнкция) использует либо 1 ⊕ (1 ⊕ a) (1 ⊕ b) (проще, когда оба операнда имеют чисто истинные термины), либо a ⊕ b ⊕ ab (проще в противном случае):

( 1 ⊕ x ) + ( 1 ⊕ x ⊕ y )

1 ⊕ (1 ⊕ 1 ⊕ x ) (1 ⊕ 1 ⊕ x ⊕ y )

1 ⊕ х (х ⊕ у)

1 ⊕ х ⊕ ху

Преобразование в алгебраическую нормальную форму

Каждая переменная в формуле уже находится в чистом ANF, поэтому вам нужно только выполнить логические операции формулы, как показано выше, чтобы получить всю формулу в ANF. Например:

х + (у ¬z)

х + (у (1 г))

х + (у ⊕ yz)

х ⊕ (y ⊕ yz) ⊕ x (y ⊕ yz)

x ⊕ y ⊕ xy ⊕ yz ⊕ xyz

Формальное представительство

ANF иногда описывают аналогичным образом:

${\ Displaystyle f (x_ {1}, x_ {2}, \ ldots, x_ {n}) = \!}$	${\ displaystyle a_ {0} \ oplus \!}$
	${\ displaystyle a_ {1} x_ {1} \ oplus a_ {2} x_ {2} \ oplus \ cdots \ oplus a_ {n} x_ {n} \ oplus \!}$
	${\ displaystyle a_ {1,2} x_ {1} x_ {2} \ oplus \ cdots \ oplus a_ {n-1, n} x_ {n-1} x_ {n} \ oplus \!}$
	${\ Displaystyle \ cdots \ oplus \!}$
	${\ displaystyle a_ {1,2, \ ldots, n} x_ {1} x_ {2} \ ldots x_ {n} \!}$

где полностью описано .

{\ displaystyle a_ {0}, a_ {1}, \ ldots, a_ {1,2, \ ldots, n} \ in \ {0,1 \} ^ {*}}

{\ displaystyle f}

Рекурсивное получение логических функций с несколькими аргументами

Всего четыре функции с одним аргументом:

${\ displaystyle f (x) = 0}$
${\ displaystyle f (x) = 1}$
${\ Displaystyle е (х) = х}$
${\ displaystyle f (x) = 1 \ oplus x}$

Для представления функции с несколькими аргументами можно использовать следующее равенство:

{\ displaystyle f (x_ {1}, x_ {2}, \ ldots, x_ {n}) = g (x_ {2}, \ ldots, x_ {n}) \ oplus x_ {1} h (x_ {2 }, \ ldots, x_ {n})}

, куда

${\ displaystyle g (x_ {2}, \ ldots, x_ {n}) = f (0, x_ {2}, \ ldots, x_ {n})}$
${\ displaystyle h (x_ {2}, \ ldots, x_ {n}) = f (0, x_ {2}, \ ldots, x_ {n}) \ oplus f (1, x_ {2}, \ ldots, x_ {n})}$

Действительно,

если тогда и так ${\ displaystyle x_ {1} = 0}$ ${\ displaystyle x_ {1} h = 0}$ ${\ Displaystyle е (0, \ ldots) = е (0, \ ldots)}$
если тогда и так ${\ displaystyle x_ {1} = 1}$ ${\ displaystyle x_ {1} h = h}$ ${\ Displaystyle е (1, \ ldots) = е (0, \ ldots) \ oplus f (0, \ ldots) \ oplus f (1, \ ldots)}$

Поскольку у обоих и меньше аргументов, из этого следует, что, используя этот процесс рекурсивно, мы закончим с функциями с одной переменной. Например, построим ANF из (логического или): ${\ displaystyle g}$ ${\ displaystyle h}$ ${\ displaystyle f}$ ${\ Displaystyle е (х, у) = х \ лор у}$

${\ Displaystyle f (x, y) = f (0, y) \ oplus x (f (0, y) \ oplus f (1, y))}$
с тех пор и ${\ Displaystyle f (0, y) = 0 \ lor y = y}$ ${\ Displaystyle f (1, y) = 1 \ lor y = 1}$
следует, что ${\ Displaystyle е (х, у) = у \ oplus х (у \ oplus 1)}$
по распределению получаем окончательный ANF: ${\ displaystyle f (x, y) = y \ oplus xy \ oplus x = x \ oplus y \ oplus xy}$