Forma normal algébrica - Algebraic normal form
Na álgebra booleana , a forma normal algébrica ( ANF ), forma normal de soma de anéis ( RSNF ou RNF ), forma normal de Zhegalkin ou expansão de Reed-Muller é uma maneira de escrever fórmulas lógicas em uma das três subformas:
- Toda a fórmula é puramente verdadeira ou falsa:
- 1
- 0
- Uma ou mais variáveis são combinadas com AND em um termo, então um ou mais termos são XORed juntos em ANF. Não são permitidos NOTs :
- a ⊕ b ⊕ ab ⊕ abc
- ou em símbolos lógicos proposicionais padrão:
- O subformulário anterior com um termo puramente verdadeiro:
- 1 ⊕ a ⊕ b ⊕ ab ⊕ abc
As fórmulas escritas em ANF também são conhecidas como polinômios de Zhegalkin ( russo : полиномы Жегалкина ) e expressões de Reed-Muller de polaridade positiva (ou paridade) (PPRM).
Usos comuns
ANF é uma forma normal , o que significa que duas fórmulas equivalentes serão convertidas para o mesmo ANF, mostrando facilmente se duas fórmulas são equivalentes para a prova automatizada de teoremas . Ao contrário de outras formas normais, pode ser representado como uma lista simples de listas de nomes de variáveis. As formas normais conjuntivas e disjuntivas também requerem registro se cada variável é negada ou não. A forma normal de negação não é adequada para esse fim, pois não usa a igualdade como sua relação de equivalência: a ∨ ¬a não se reduz a 1, embora sejam iguais.
Colocar uma fórmula em ANF também torna mais fácil identificar funções lineares (usadas, por exemplo, em registradores de deslocamento de feedback linear ): uma função linear é aquela que é uma soma de literais únicos. Propriedades de registradores de deslocamento de feedback não linear também podem ser deduzidas de certas propriedades da função de feedback em ANF.
Execução de operações dentro da forma normal algébrica
Existem maneiras simples de realizar as operações booleanas padrão em entradas ANF para obter resultados ANF.
XOR (disjunção lógica exclusiva) é realizada diretamente:
- ( 1 ⊕ x ) ⊕ ( 1 ⊕ x ⊕ y )
- 1 ⊕ x ⊕ 1 ⊕ x ⊕ y
- 1 ⊕ 1 ⊕ x ⊕ x ⊕ y
- y
NÃO (negação lógica) é XORing 1:
- ¬ (1 ⊕ x ⊕ y)
- 1 ⊕ (1 ⊕ x ⊕ y)
- 1 ⊕ 1 ⊕ x ⊕ y
- x ⊕ y
AND (conjunção lógica) é distribuído algebricamente
- ( 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
OR (disjunção lógica) usa 1 ⊕ (1 ⊕ a) (1 ⊕ b) (mais fácil quando ambos os operandos têm termos puramente verdadeiros) ou a ⊕ b ⊕ ab (mais fácil caso contrário):
- ( 1 ⊕ x ) + ( 1 ⊕ x ⊕ y )
- 1 ⊕ (1 ⊕ 1 ⊕ x ) (1 ⊕ 1 ⊕ x ⊕ y )
- 1 ⊕ x (x ⊕ y)
- 1 ⊕ x ⊕ xy
Converter para a forma normal algébrica
Cada variável em uma fórmula já está em ANF puro, portanto, você só precisa realizar as operações booleanas da fórmula, conforme mostrado acima, para obter a fórmula inteira em ANF. Por exemplo:
- x + (y ⋅ ¬z)
- x + (y (1 ⊕ z))
- x + (y ⊕ yz)
- x ⊕ (y ⊕ yz) ⊕ x (y ⊕ yz)
- x ⊕ y ⊕ xy ⊕ yz ⊕ xyz
Representação formal
ANF às vezes é descrito de forma equivalente:
- onde descreve totalmente .
Derivando recursivamente funções booleanas de vários instrumentos
Existem apenas quatro funções com um argumento:
Para representar uma função com vários argumentos, pode-se usar a seguinte igualdade:
-
, Onde
De fato,
- se então e assim
- se então e assim
Como ambos e têm menos argumentos do que segue que, usando este processo recursivamente, terminaremos com funções com uma variável. Por exemplo, vamos construir ANF de (lógico ou):
- desde e
- segue que
- por distribuição, obtemos o ANF final:
Veja também
- Expansão Reed-Muller
- Forma normal de Zhegalkin
- Função booleana
- Gráfico lógico
- Polinômio de Zhegalkin
- Forma normal de negação
- Forma normal conjuntiva
- Forma normal disjuntiva
- Mapa de Karnaugh
- Anel booleano
Referências
Leitura adicional
- Wegener, Ingo (1987). A complexidade das funções booleanas . Wiley-Teubner . p. 6. ISBN 3-519-02107-2.
- "Apresentação" (PDF) (em alemão). Universidade de Duisburg-Essen . Arquivado (PDF) do original em 20-04-2017 . Recuperado em 19-04-2017 .
- Maxfield, Clive "Max" (2006-11-29). "Lógica Reed-Muller" . Logic 101 . EETimes . Parte 3. Arquivado do original em 19-04-2017 . Recuperado em 19-04-2017 .