Forma normal algebraica

En àlgebra booleana, la forma normal algebraica (FNA) és una manera d'expressar fórmules lògiques en una de les següents tres subformes:

• La fórmula sencera és purament certa o falsa:

  1

  0

• Una o més variables estan unides mitjançant conjunció lògica per formar un terme. Un o més termes estan units mitjançant disjunció exclusiva en FNA. No es permeten negacions lògiques:

  a ⊕ b ⊕ ab ⊕ abc

• Podem escriure l'expressió anterior amb un terme purament cert addicional:

  1 ⊕ a ⊕ b ⊕ ab ⊕ abc

Les fórmules escrites en FNA també es coneixen com a polinomis de Zhegalkin ((rus) полиномы Жегалкина) i com a expressions de Reed-Muller de polaritat (o paritat) positiva.

Usos

La forma normal algebraica (FNA) és una forma canònica, la qual cosa significa que dues fórmules equivalents es poden transformar en la mateixa FNA, i això permet comprovar si dues fórmules són equivalents. Això és particularment útil en sistemes de demostració automàtica de teoremes. Al contrari que altres formes normals, la FNA es pot representar com una llista senzilla de llistes de noms de variables. Les formes normals conjuntiva i disjuntiva també requereixen determinar si cada variable està negada o no. La forma normal negativa no serveix per a aquest propòsit, ja que no usa la igualtat com a relació d'equivalència: "a ∨ ¬a" no es redueix a "1", encara que són expressions equivalents.

Si s'expressa una fórmula en forma normal algebraica, llavors és fàcil identificar funcions lineals (emprades, per exemple, en registres de desplaçament amb retroalimentació lineal (linear feedback shift registers): una funció lineal és aquella que és suma de literals simples. Es poden deduir les propietats dels registres de desplaçament a partir de certes propietats de la funció de retroalimentació en FNA.

Operacions en forma normal algebraica

Existeixen formes directes per tal de transformar les operacions booleanes estàndard sobre fórmules en FNA per tal d'obtenir resultats en FNA.

La disjunció logical exclusiva (XOR) es realitza directament:

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

1 ⊕ x ⊕ 1 ⊕ x ⊕ y

1 ⊕ 1 ⊕ x ⊕ x ⊕ y

y

La negació lògica (NOT) és el mateix que aplicar un XOR amb 1:

¬(1 ⊕ x ⊕ y)

1 ⊕(1 ⊕ x ⊕ y)

1 ⊕ 1 ⊕ x ⊕ y

x ⊕ y

La conjunció lògica (AND) es transforma mitjançant la propietat distributiva

(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 disjunció lògica (OR) usa o bé 1 ⊕ (1 ⊕ a)(1 ⊕ b) (més senzill quan els dos operands tenen termes purs certs), o bé a ⊕ b ⊕ ab

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

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

1 ⊕ x(x ⊕ y)

1 ⊕ x ⊕ xy

Conversió a forma normal algebraica

Tota variable en una fórmula està en FNA pura, de tal manera que només és necessari transformar les operacions booleanes de la fórmula com hem vist abans per tal d'obtenir la fórmula completa en FNA. Per exemple:

x + (y · ¬z)

x + (y(1 ⊕ z))

x + (y ⊕ yz)

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

x ⊕ y ⊕ xy ⊕ yz ⊕ xyz

Representació formal

De vegades, la forma normal algebraica es descriu en una forma equivalent:

$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\}^{*}$ descriu completament $f$.

Derivació recursiva de funcions booleanes amb més d'un argument

Només hi ha quatre funcions amb un argument:

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

Per tal de representar una funció amb múltiples arguments, hom pot utilitzar la següent igualtat:

$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 efecte,

• si $x_{1}=0$, llavors $x_{1}h=0$ i per tant $f(0,\ldots )=f(0,\ldots )$
• si $x_{1}=1$, llavors $x_{1}h=h$ i per tant $f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )$

Com que tant $g$ com $h$ tenen menys argument que $f$, d'aquí se segueix que podem emprar aquest procés de forma recursiva, i acabarem amb funcions d'una sola variable. Per exemple, construïm ara la FNA de $f(x,y)=x\lor y$ (disjunció lògica):

• $f(x,y)=f(0,y)\oplus x(f(0,y)\oplus f(1,y))$
• com que $f(0,y)=0\lor y=y$ i $f(1,y)=1\lor y=1$
• se segueix que $f(x,y)=y\oplus x(y\oplus 1)$
• per distribució, obtenim la FNA final: $f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy$

Vegeu també

• Funció booleana
• Graf lògic
• Polinomi de Zhegalkin
• Forma normal negativa
• Forma normal conjuntiva
• Forma normal disjuntiva