En el álgebra de Boole , la forma algebraica normales ( ANF ), suma anillo de forma normal ( RSNF o RNF ), forma normal Zhegalkin , o expansión Reed-Muller es una forma de escribir fórmulas lógicas en una de tres subformularios:
- La fórmula completa es puramente verdadera o falsa:
- 1
- 0
- Una o más variables se unen mediante AND en un término, luego uno o más términos se combinan con XOR en ANF. No se permiten NOT :
- a ⊕ b ⊕ ab ⊕ abc
- o en símbolos lógicos proposicionales estándar:
- El subformulario anterior con un término puramente verdadero:
- 1 ⊕ a ⊕ b ⊕ ab ⊕ abc
Las fórmulas escritas en ANF también se conocen como polinomios de Zhegalkin (en ruso : полиномы Жегалкина ) y expresiones de Reed-Muller de polaridad positiva (o paridad) (PPRM). [1]
Usos comunes
ANF es una forma normal , lo que significa que dos fórmulas equivalentes se convertirán en el mismo ANF, mostrando 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 lista simple de listas de nombres de variables. Las formas normales conjuntivas y disyuntivas también requieren registrar si cada variable está negada o no. La forma normal de negación no es adecuada para ese propósito, ya que no usa la igualdad como su relación de equivalencia: a ∨ ¬a no se reduce a lo mismo que 1, aunque sean iguales.
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 una que es una suma de literales simples. 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.
Realización de operaciones dentro de la forma normal algebraica
Hay formas sencillas de realizar las 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
Y (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 necesita 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
A veces, ANF se describe de manera equivalente:
- dónde describe completamente .
Derivación recursiva de funciones booleanas con múltiples argumentos
Solo hay cuatro funciones con un argumento:
Para representar una función con múltiples argumentos, se puede usar la siguiente igualdad:
- , dónde
En efecto,
- Si luego y entonces
- Si luego y entonces
Ya que ambos y tener menos argumentos que se deduce que usando este proceso de forma recursiva terminaremos con funciones con una variable. Por ejemplo, construyamos ANF de (lógico o):
- desde y
- resulta que
- por distribución, obtenemos el ANF final:
Ver también
Referencias
- ^ Steinbach, Bernd ; 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. LCCN 2008941076 .
- ^ Demostración de WolframAlpha NOT-equivalencia: ¬a = 1 ⊕ a
- ^ Demostración de WolframAlpha AND-equivalencia: (a ⊕ b) (c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd
- ^ A partir de las leyes de De Morgan
- ^ 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 Duisburg-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 Reed-Muller" . Lógica 101 . EETimes . Part 3. Archivado desde el original el 19 de abril de 2017 . Consultado el 19 de abril de 2017 .