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

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

• Вся формула является чисто истинной или ложной:
  • $1$
  • $0$
• Одна или несколько переменных объединяются в термин с помощью AND ( $\land$), затем один или несколько членов объединяются с помощью XOR ( $\oplus$) вместе в ANF. Отрицания не допускаются:
  $$a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)$$
• Предыдущая подформа с чисто истинным термином:
  $$1\oplus a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)$$

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

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

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

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

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

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

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

( 1 ⊕ Икс ) ⊕ ( 1 ⊕ Икс ⊕ у )

1 ⊕ х ⊕ 1 ⊕ х ⊕ у

1 ⊕ 1 ⊕ х ⊕ х ⊕ у

и

НЕ (логическое отрицание) — это операция XOR 1:

¬ (1 ⊕ х ⊕ у)

1 ⊕ (1 ⊕ х ⊕ у)

1 ⊕ 1 ⊕ х ⊕ у

х ⊕ у

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

( 1 ⊕ Икс ) (1 ⊕ Икс ⊕ у)

1 (1 ⊕ х ⊕ у) ⊕ х (1 ⊕ х ⊕ у)

(1 ⊕ х ⊕ у) ⊕ (х ⊕ х ⊕ ху)

1 ⊕ х ⊕ х ⊕ х ⊕ у ⊕ ху

1 ⊕ х ⊕ у ⊕ ху

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

( 1 ⊕ Икс ) + ( 1 ⊕ Икс ⊕ у )

1 ⊕ (1 ⊕ 1 ⊕ Икс )(1 ⊕ 1 ⊕ Икс ⊕ у )

1 ⊕ х(х ⊕ у)

1 ⊕ х ⊕ ху

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

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

х + (у ⋅ ¬z)

х + (у(1 ⊕ z))

х + (у ⊕ уз)

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

Икс ⊕ у ⊕ ху ⊕ yz ⊕ xyz

Официальное представление

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

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

где $a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}$ полностью описывает $f$.

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

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

• $f(x)=0$
• $f(x)=1$
• $f(x)=x$
• $f(x)=1\oplus x$

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

$f(x_{1},x_{2},\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})\oplus x_{1}h(x_{2},\ldots ,x_{n})$, где

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

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

• если $x_{1}=0$ затем $x_{1}h=0$ и так $f(0,\ldots )=f(0,\ldots )$
• если $x_{1}=1$ затем $x_{1}h=h$ и так $f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )$

Поскольку оба $g$ и $h$ иметь меньше аргументов, чем $f$ следовательно, используя этот процесс рекурсивно, мы закончим с функциями с одной переменной. Например, построим АНФ из $f(x,y)=x\lor y$ (логическое или):

• $f(x,y)=f(0,y)\oplus x(f(0,y)\oplus f(1,y))$
• с $f(0,y)=0\lor y=y$ и $f(1,y)=1\lor y=1$
• отсюда следует, что $f(x,y)=y\oplus x(y\oplus 1)$
• по распределению получаем итоговый АНФ: $f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy$

См. также

• Расширение Рида – Мюллера
• Жегалкин нормальная форма
• Булева функция
• Логический график
• Полином Жегалкина
• Нормальная форма отрицания
• Конъюнктивная нормальная форма
• Дизъюнктивная нормальная форма
• Карта Карно
• Булево кольцо

Дальнейшее чтение

• Вегенер, Инго (1987). Сложность булевых функций . Вили-Тойбнер . п. 6. ISBN  3-519-02107-2 .
• «Презентация» (PDF) (на немецком языке). Университет Дуйсбург-Эссен . Архивировано (PDF) из оригинала 20 апреля 2017 г. Проверено 19 апреля 2017 г.
• Максфилд, Клайв «Макс» (29 ноября 2006 г.). «Логика Рида-Мюллера» . Логика 101 . ЭТаймс . Часть 3. Архивировано из оригинала 19 апреля 2017 г. Проверено 19 апреля 2017 г.