Forma normal algebraica

Forma normal algebraica, estrechamente relacionada con el polinomio de Zhegalkin (Q4370006)

En álgebra booleana , la forma normal algebraica ( ANF ), la forma normal de suma anular ( RSNF o RNF ), la forma normal de Zhegalkin o la expansión de Reed-Muller es una forma de escribir fórmulas lógicas proposicionales en una de tres subformas:

• Toda la fórmula es puramente verdadera o falsa:

  ${\displaystyle 1}$

  ${\displaystyle 0}$

• Una o más variables se combinan en un término mediante AND ( ), luego uno o más términos se combinan mediante XOR ( ) en ANF. No se permiten negaciones : ${\displaystyle \land }$ ${\displaystyle \oplus }$

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

• La subforma anterior con un término puramente verdadero:

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

Las fórmulas escritas en ANF también se conocen como polinomios de Zhegalkin y expresiones de Reed-Muller de polaridad positiva (o paridad) (PPRM). ^[1]

Usos comunes

ANF ​​es una forma canónica , lo que significa que dos fórmulas lógicamente equivalentes se convertirán en la misma ANF, lo que muestra fácilmente si dos fórmulas son equivalentes para la demostración automatizada de teoremas . A diferencia de otras formas normales, se puede representar como una lista simple de listas de nombres de variables; las formas normales conjuntivas y disyuntivas también requieren registrar si cada variable se niega o no. La forma normal de negación no es adecuada para determinar la equivalencia, ya que en las formas normales de negación, la equivalencia no implica igualdad: a ∨ ¬a no se reduce a lo mismo que 1, aunque sean lógicamente equivalentes.

Poner una fórmula en ANF también facilita la identificación de funciones lineales (utilizadas, por ejemplo, en registros de desplazamiento de retroalimentación lineal ): una función lineal es aquella que es una suma de literales individuales. Las propiedades de los registros de desplazamiento de retroalimentación no lineal también se pueden deducir de ciertas propiedades de la función de retroalimentación en ANF.

Realizar operaciones dentro de la forma normal algebraica.

Existen formas sencillas de realizar operaciones booleanas estándar en entradas ANF para obtener resultados ANF.

XOR (disyunción lógica exclusiva) se realiza directamente:

( 1 ⊕ x ) ⊕ ( 1 ⊕ x ⊕ y )

1 ⊕ x ⊕ 1 ⊕ x ⊕ y

1 ⊕ 1 ⊕ x ⊕ x ⊕ y

y

NOT (negación lógica) es XORing 1: ^[2]

¬ (1 ⊕ x ⊕ y)

1 ⊕ (1 ⊕ x ⊕ y)

1 ⊕ 1 ⊕ x ⊕ y

x ⊕ y

AND (conjunción lógica) se distribuye algebraicamente ^[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

OR (disyunción lógica) usa 1 ⊕ (1 ⊕ a)(1 ⊕ b) ^[4] (más fácil cuando ambos operandos tienen términos puramente verdaderos) o a ⊕ b ⊕ ab ^[5] (más fácil en caso contrario):

( 1 ⊕ x ) + ( 1 ⊕ x ⊕ y )

1 ⊕ (1 ⊕ 1 ⊕ x )(1 ⊕ 1 ⊕ x ⊕ y )

1⊕x(x⊕y)

1 ⊕ x ⊕ xy

Conversión a forma normal algebraica

Cada variable en una fórmula ya está en ANF puro, por lo que solo es necesario realizar las operaciones booleanas de la fórmula como se muestra arriba para obtener la fórmula completa en ANF. Por ejemplo:

x + (y ⋅ ¬z)

x + (y(1 ⊕ z))

x + (y ⊕ yz)

x ⊕ (y ⊕ yz) ⊕ x(y ⊕ yz)

x ⊕ y ⊕ xy ⊕ yz ⊕ xyz

Representación formal

ANF ​​a veces se describe de manera equivalente:

donde se describe completamente . ${\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}}$ ${\displaystyle f}$

Derivar recursivamente funciones booleanas multiargumentos

Sólo hay cuatro funciones con un argumento:

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

Para representar una función con múltiples argumentos se puede utilizar la siguiente igualdad:

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

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

En efecto,

• si entonces y así ${\displaystyle x_{1}=0}$ ${\displaystyle x_{1}h=0}$ ${\displaystyle f(0,\ldots )=f(0,\ldots )}$
• si entonces y así ${\displaystyle x_{1}=1}$ ${\displaystyle x_{1}h=h}$ ${\displaystyle f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )}$

Dado que ambos y tienen menos argumentos, se deduce que usando este proceso de forma recursiva terminaremos con funciones con una variable. Por ejemplo, construyamos ANF de (lógico o): ${\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 y ${\displaystyle f(0,y)=0\lor y=y}$ ${\displaystyle f(1,y)=1\lor y=1}$
• resulta que ${\displaystyle f(x,y)=y\oplus x(y\oplus 1)}$
• por distribución, obtenemos el ANF final: ${\displaystyle f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy}$

Ver también

• Expansión de Reed-Muller
• Forma normal de Zhegalkin
• función booleana
• gráfico lógico
• polinomio de Zhegalkin
• Negación forma normal
• Forma normal conjuntiva
• Forma normal disyuntiva
• mapa de karnaugh
• anillo booleano

Referencias

1. Steinbach, Bernd [en alemán] ; Posthoff, cristiano (2009). "Prefacio". Funciones y ecuaciones lógicas: ejemplos y ejercicios (1ª ed.). Springer Science + Business Media BV pág. xv. ISBN 978-1-4020-9594-8. LCCN  2008941076.
2. Demostración de NO equivalencia de WolframAlpha: ¬a = 1 ⊕ a
3. Demostración de equivalencia AND de WolframAlpha: (a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd
4. De las leyes de De Morgan
5. Demostración de equivalencia OR de WolframAlpha: a + b = a ⊕ b ⊕ ab

Otras lecturas

• Wegener, Ingo (1987). La complejidad de las funciones booleanas. Wiley-Teubner . pag. 6.ISBN​ 3-519-02107-2.
• "Presentación" (PDF) (en alemán). Universidad de Duisburgo-Essen . Archivado (PDF) desde el original el 20 de abril de 2017 . Consultado el 19 de abril de 2017 .
• Maxfield, Clive "Max" (29 de noviembre de 2006). "Lógica de Reed-Muller". Lógica 101 . EETimes . Parte 3. Archivado desde el original el 19 de abril de 2017 . Consultado el 19 de abril de 2017 .