Forma normal algebraica

En Álgebra booleana, la forma normal algebraica (FNA) es una manera de expresar fórmulas lógicas en una de les siguientes tres subformas:

La fórmula entera es puramente verdadera o falsa:
1

0
Una o más variables están unidas mediante conjunción lógica para formar un término. Uno o más términos están unidos mediante disyunción exclusiva en FNA. No se permiten negaciones lógicas:
a ⊕ b ⊕ ab ⊕ abc
puede escribir la expresión anterior con un término puramente verdadero adicional:
1 ⊕ a ⊕ b ⊕ ab ⊕ abc

Las fórmulas escritas en FNA también se conocen como polinomios de Zhegalkin ((en ruso) полиномы Жегалкина) y como expresiones de Reed-Muller de polaridad (o paridad) positiva.

Usos[editar]

La forma normal algebraica (FNA) es una forma canónica, lo que significa que dos fórmulas equivalentes se pueden transformar en la misma FNA, lo que permite comprobar si dos fórmulas son equivalentes. Esto es particularmente útil en sistemas de demostración automática de teoremas. Al contrario que otras formas normales, la FNA se puede representar como una lista sencilla de listas de nombres de variables. Las formas normales conjuntiva y disyuntiva también requieren determinar si cada variable está negada o no. La forma normal negativa no sirve para este propósito, ya que no usa la igualdad como una relación de equivalencia: "a ∨ ¬A" no se reduce a "1", aunque son expresiones equivalentes.

Si se expresa una fórmula en forma normal algebraica, entonces es fácil identificar funciones lineales (utilizadas, por ejemplo, en registros de desplazamiento con retroalimentación lineal (linear feedback shift registers): una función lineal es aquella que es suma de literales simples. Se pueden deducir las propiedades de los registros de desplazamiento a partir de ciertas propiedades de la función de retroalimentación en FNA.

Operaciones en forma normal algebraica[editar]

Existen formas directas para transformar las operaciones booleanas estándares sobre fórmulas en FNA para obtener resultados en FNA.

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

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

1 ⊕ x ⊕ 1 ⊕ x ⊕ y

1 ⊕ 1 ⊕ x ⊕ x ⊕ y

y

La negación lógica (NOT) es el mismo que aplicar un XOR con 1:^[1]

¬(1 ⊕ x ⊕ y)

1 ⊕(1 ⊕ x ⊕ y)

1 ⊕ 1 ⊕ x ⊕ y

x ⊕ y

La conjunción lógica (AND) se transforma mediante la propiedad distributiva^[2]

(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

La disyunción lógica (OR) usa o bien 1 ⊕ (1 ⊕ a)(1 ⊕ b)^[3] (más sencillo cuando los dos operandos tienen términos puros verdaderos), o bien a ⊕ b ⊕ ab^[4]

(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[editar]

Toda variable en una fórmula está en FNA pura, de tal modo que solo es necesario transformar las operaciones booleanas de la fórmula como hemos visto antes para obtener la fórmula completa en FNA. 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[editar]

A veces, la forma normal algebraica se describe en una forma equivalente:

$f(x_{1},x_{2},\ldots ,x_{n})=\!$	$a_{0}\oplus \!$
	$a_{1}x_{1}\oplus a_{2}x_{2}\oplus \cdots \oplus a_{n}x_{n}\oplus \!$
	$a_{1,2}x_{1}x_{2}\oplus \cdots \oplus a_{n-1,n}x_{n-1}x_{n}\oplus \!$
	$\cdots \oplus \!$
	$a_{1,2,\ldots ,n}x_{1}x_{2}\ldots x_{n}\!$

on

a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}

describe completamente

f

.

Derivación recursiva de funciones booleanas con más de un argumento[editar]

Solo hay cuatro funciones con un argumento:

$f(x)=0$
$f(x)=1$
$f(x)=x$
$f(x)=1\oplus x$

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

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

, on

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

En efecto,

si $x_{1}=0$ , entonces $x_{1}h=0$ y por tanto $f(0,\ldots )=f(0,\ldots )$
si $x_{1}=1$ , entonces $x_{1}h=h$ y por tanto $f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )$

Como tanto $g$ como $h$ tienen menos argumento que $f$ , de ahí se sigue que podemos emplear este proceso de forma recursiva, y acabaremos con funciones de una sola variable. Por ejemplo, construimos ahora la FNA de $f(x,y)=x\lor y$ (disyunción lógica):

$f(x,y)=f(0,y)\oplus x(f(0,y)\oplus f(1,y))$
como que $f(0,y)=0\lor y=y$ i $f(1,y)=1\lor y=1$
se sigue que $f(x,y)=y\oplus x(y\oplus 1)$
por distribución, obtenemos la FNA final: $f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy$