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

Алгебраическая нормальная форма, тесно связанная с полиномом Жегалкина (Q4370006)

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

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

  ${\displaystyle 1}$

  ${\displaystyle 0}$

• Одна или несколько переменных объединяются в термин с помощью AND ( ), затем один или несколько терминов объединяются с помощью XOR ( ) вместе в ANF. Отрицания не допускаются: ${\displaystyle \land }$ ${\displaystyle \oplus }$

${\displaystyle a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}$

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

${\displaystyle 1\oplus a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}$

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

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

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

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

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

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

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

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

1 ⊕ х ⊕ 1 ⊕ х ⊕ у

1 ⊕ 1 ⊕ х ⊕ х ⊕ у

й

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

¬ (1 ⊕ х ⊕ у)

1 ⊕ (1 ⊕ х ⊕ у)

1 ⊕ 1 ⊕ х ⊕ у

х ⊕ у

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

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

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

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

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

1 ⊕ х ⊕ у ⊕ ху

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

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

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

1 ⊕ х(х ⊕ у)

1 ⊕ х ⊕ ху

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

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

х + (у ⋅ ¬z)

х + (у(1 ⊕ z))

х + (у ⊕ уз)

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (2009). "Предисловие". Логические функции и уравнения - примеры и упражнения (1-е изд.). Springer Science + Business Media BV с. хв. ISBN 978-1-4020-9594-8. LCCN  2008941076.
2. Демонстрация НЕ-эквивалентности WolframAlpha: ¬a = 1 ⊕ a
3. Демонстрация И-эквивалентности WolframAlpha: (a ⊕ b) (c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd
4. Из законов Де Моргана
5. Демонстрация ИЛИ-эквивалентности WolframAlpha: a + b = a ⊕ b ⊕ ab

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

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