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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Алгебраическая нормальная форма»  -  новости  · газеты  · книги  · ученый  · JSTOR ( июль 2013 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

  1

  0

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

  а ⊕ б ⊕ аб ⊕ абв

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

${\displaystyle a\veebar b\veebar \left(a\wedge b\right)\veebar \left(a\wedge b\wedge c\right)}$

• Предыдущая подформа с чисто правдивым термином:

  1 ⊕ a ⊕ b ⊕ ab ⊕ abc

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

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

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

y

НЕ (логическое отрицание) является XORing 1: ^[2]

¬ (1 ⊕ x ⊕ y)

1 ⊕ (1 ⊕ x ⊕ y)

1 ⊕ 1 ⊕ x ⊕ y

х ⊕ у

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

( 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) ^[4] (проще, когда оба операнда имеют чисто истинные члены), либо a ⊕ b ⊕ ab ^[5] (проще в противном случае):

( 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 f(x)=x}$
• ${\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 f(0,\ldots )=f(0,\ldots )}$
• если тогда и так${\displaystyle x_{1}=1}$${\displaystyle x_{1}h=h}$${\displaystyle f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )}$

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

• ${\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 f(x,y)=y\oplus x(y\oplus 1)}$
• по распределению получаем окончательный ANF: ${\displaystyle f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy}$

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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