Алгебраическая нормальная форма, тесно связанная с полиномом Жегалкина (Q4370006)
В булевой алгебре алгебраическая нормальная форма ( ANF ), нормальная форма кольцевой суммы ( RSNF или RNF ), нормальная форма Жегалкина или расширение Рида–Мюллера — это способ записи формул пропозициональной логики в одной из трех подформ:
- Вся формула является чисто истинной или ложной:
![{\displaystyle 1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Одна или несколько переменных объединяются в термин с помощью AND ( ), затем один или несколько терминов объединяются с помощью XOR ( ) вместе в ANF. Отрицания не допускаются:
![{\displaystyle \земля }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \oplus }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ Displaystyle а \ oplus b \ oplus \ влево (а \ земля b \ вправо) \ oplus \ влево (а \ земля b \ земля с \ вправо)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Предыдущая подформа с чисто истинным термином:
![{\displaystyle 1\oplus a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Формулы, написанные в 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\}^{*}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle е}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Рекурсивный вывод булевых функций с несколькими аргументами
Существует всего четыре функции с одним аргументом:
![{\ displaystyle f (x) = 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f(x)=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle f (x) = x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f(x)=1\oplus x}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Чтобы представить функцию с несколькими аргументами, можно использовать следующее равенство:
, где![{\displaystyle g(x_{2},\ldots,x_{n})=f(0,x_{2},\ldots,x_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(x_{2},\ldots,x_{n})=f(0,x_{2},\ldots,x_{n})\oplus f(1,x_{2},\ldots, x_{n})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Действительно,
- если тогда и так
![{\displaystyle x_{1}=0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{1}h=0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle f (0, \ ldots) = f (0, \ ldots)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- если тогда и так
![{\displaystyle x_{1}=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x_{1}h = h}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle f (1, \ ldots) = f (0, \ ldots) \ oplus f (0, \ ldots) \ oplus f (1, \ ldots)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Поскольку оба и имеют меньше аргументов, чем следует, рекурсивно используя этот процесс, мы закончим с функциями с одной переменной. Например, давайте построим ANF из (логического или):![{\displaystyle г}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle ч}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle е}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f(x,y)=x\lor y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle f (x, y) = f (0, y) \ oplus x (f (0, y) \ oplus f (1, y))}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- с тех пор и
![{\displaystyle f(0,y)=0\lor y=y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f(1,y)=1\lor y=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- следует, что
![{\ displaystyle f (x, y) = y \ oplus x (y \ oplus 1)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- по распределению получаем итоговый АНФ:
![{\displaystyle f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Смотрите также
Викискладе есть медиафайлы, связанные с алгебраической нормальной формой .
Рекомендации
- ^ Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (2009). "Предисловие". Логические функции и уравнения - примеры и упражнения (1-е изд.). Springer Science + Business Media BV с. хв. ISBN 978-1-4020-9594-8. LCCN 2008941076.
- ^ Демонстрация НЕ-эквивалентности WolframAlpha: ¬a = 1 ⊕ a
- ^ Демонстрация И-эквивалентности WolframAlpha: (a ⊕ b) (c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd
- ^ Из законов Де Моргана
- ^ Демонстрация ИЛИ-эквивалентности 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 г.