To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
Spanish Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Forma normal algebraica

De Wikipedia, la enciclopedia libre

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

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

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

(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 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

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

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

on describe completamente .

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

Solo hay cuatro funciones con un argumento:

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

, on

En efecto,

  • si , entonces y por tanto
  • si , entonces y por tanto

Como tanto como tienen menos argumento que , 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 (disyunción lógica):

  • como que i
  • se sigue que
  • por distribución, obtenemos la FNA final:

Referencias

Véase también

Enlaces externos

Esta página se editó por última vez el 8 ago 2019 a las 08:41.
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.