Forma normal algebraica

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

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

• La fórmula completa 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 ( ) juntos 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)}$$
• El subformulario 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 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 automática de teoremas . A diferencia de otras formas normales, se puede representar como una simple lista 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.

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

Realizar operaciones dentro de la forma normal algebraica

Hay formas sencillas de realizar las operaciones booleanas estándar en las 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

NO (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) utiliza 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 de 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 convertir 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}$

Derivación recursiva de funciones booleanas multiargumento

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 asi ${\displaystyle x_{1}=0}$ ${\displaystyle x_{1}h=0}$ ${\displaystyle f(0,\ldots )=f(0,\ldots )}$
• si entonces y asi ${\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 tanto y tienen menos argumentos, se deduce que, utilizando este proceso de forma recursiva, terminaremos con funciones con una variable. Por ejemplo, construyamos ANF de (o lógico): ${\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}$

Véase también

• Expansión de Reed-Muller
• Forma normal de Zhegalkin
• Función booleana
• Gráfico lógico
• Polinomio de Zhegalkin
• Forma normal de negación
• Forma normal conjuntiva
• Forma normal disyuntiva
• Mapa de Karnaugh
• Anillo booleano

Referencias

1. Steinbach, Bernd [en alemán] ; Posthoff, Christian (2009). "Prefacio". Funciones y ecuaciones lógicas: ejemplos y ejercicios (1.ª ed.). Springer Science + Business Media BV p. xv. ISBN 978-1-4020-9594-8. Número de serie 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

Lectura adicional

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