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]
- ¬(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[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 disjunció lògica (OR) usa o bé 1 ⊕ (1 ⊕ a)(1 ⊕ b)[3] (més senzill quan els dos operands tenen termes purs certs), o bé 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ó 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:
- on descriu completament .
Derivació recursiva de funcions booleanes amb més d'un argument
Només hi ha quatre funcions amb un argument:
Per tal de representar una funció amb múltiples arguments, hom pot utilitzar la següent igualtat:
- , on
En efecte,
- si , llavors i per tant
- si , llavors i per tant
Com que tant com tenen menys argument que , 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 (disjunció lògica):
- com que i
- se segueix que
- per distribució, obtenim la FNA final:
