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:

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

• 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:

${\ 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} \!}$

onde descreve totalmente .${\ displaystyle a_ {0}, a_ {1}, \ ldots, a_ {1,2, \ ldots, n} \ in \ {0,1 \} ^ {*}}$${\ displaystyle f}$

Derivando recursivamente funções booleanas de vários instrumentos

Existem apenas quatro funções com um argumento:

• ${\ displaystyle f (x) = 0}$
• ${\ displaystyle f (x) = 1}$
• ${\ displaystyle f (x) = x}$
• ${\ displaystyle f (x) = 1 \ oplus x}$

Para representar uma função com vários argumentos, pode-se usar a seguinte igualdade:

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

• ${\ 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})}$

De fato,

• se então e assim${\ displaystyle x_ {1} = 0}$${\ displaystyle x_ {1} h = 0}$${\ displaystyle f (0, \ ldots) = f (0, \ ldots)}$
• se então e assim${\ displaystyle x_ {1} = 1}$${\ displaystyle x_ {1} h = h}$${\ displaystyle f (1, \ ldots) = f (0, \ ldots) \ oplus f (0, \ ldots) \ oplus f (1, \ ldots)}$

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): ${\ 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))}$
• desde e${\ displaystyle f (0, y) = 0 \ lor y = y}$${\ displaystyle f (1, y) = 1 \ lor y = 1}$
• segue que ${\ displaystyle f (x, y) = y \ oplus x (y \ oplus 1)}$
• por distribuição, obtemos o ANF final: ${\ displaystyle f (x, y) = y \ oplus xy \ oplus x = x \ oplus y \ oplus xy}$

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 .