Forma normal algebraica

De Viquipèdia
Dreceres ràpides: navegació, cerca

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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 ⊕ x1 ⊕ 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]

(1x)(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[modifica | modifica el codi]

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[modifica | modifica el codi]

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

f(x_1, x_2, \ldots, x_n) = \! a_0 \oplus \!
a_1x_1 \oplus a_2x_2 \oplus \cdots \oplus a_nx_n \oplus \!
a_{1,2}x_1x_2 \oplus \cdots \oplus a_{n-1,n}x_{n-1}x_n \oplus \!
\cdots \oplus \!
a_{1,2,\ldots,n}x_1x_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[modifica | modifica el codi]

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 x y \oplus x = x \oplus y \oplus x y

Referències[modifica | modifica el codi]

  1. WolframAlpha Demostració de l'equivalència de NOT: ¬a = 1 ⊕ a
  2. WolframAlpha Demostració de l'equivalència d'AND: (a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd
  3. De les lleis de De Morgan
  4. WolframAlpha Demostració de l'equivalència OR: a + b = a ⊕ b ⊕ ab

Vegeu també[modifica | modifica el codi]