Forma normal algebraica

En Àlgebra booleana, la forma normal algebraica (FNA) és una manera d'expressar fòrmules llògiques en una dels següents tres subformas:

La fòrmula sancera és purament verdadera o falsa:
1

0
Una o més variables estan unides per mig de conjunció llògica per a formar un terme. Un o més térmens estan units per mig de disjunció exclusiva en FNA. No es permeten negacions llògiques:
a ⊕ b ⊕ ab ⊕ abc
pot escriure l'expressió anterior en un terme purament verdader adicional:
1 ⊕ a ⊕ b ⊕ ab ⊕ abc

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

Usos

La forma normal algebraica (FNA) és una forma canònica, lo que significa que dos fòrmules equivalents es poden transformar en la mateixa FNA, lo que permet comprovar si dos fòrmules són equivalents. Açò és particularment útil en sistemes de demostració automàtica de teoremes. Al contrari que atres formes normals, la FNA es pot representar com una llista senzilla de llistes de noms de variables. Les formes normals conjuntiva i disyuntiva també requerixen determinar si cada variable està negada o no. La forma normal negativa no servix per a este propòsit, ya que no usa l'igualtat com una relació d'equivalència: "a ∨ ¬A" no es reduïx a "1", encara que són expressions equivalents.

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