Álgebra de Booleana.Teoremas y Postulados

Álgebra de Booleana.

El algebra de boole es toda clase o conjunto de elementos que pueden tomar dos valores perfectamente diferenciados, que designaremos por 0 y 1 y que están relacionados por dos operaciones binarias denominadas suma (+) y producto (.) (La operación producto se indica generalmente mediante la ausencia de símbolo entre dos variables lógicos).

4.1 Teoremas y Postulados.

TEOREMAS

La manera de demostrar los teoremas siguientes se puede basar en ideas intuitivas producto de la familiaridad con algún álgebra booleana en particular, (en diagramas de Venn, o bien, en circuitos con switches o en tablas de verdad) con la única condición de que se respete al pie de la letra los 6 postulados fundamentales. En estas notas sólo se usan razonamientos basados en los seis postulados. el hecho de que cada postulado tiene dos incisos los cuales son duales uno del otro.

O Principio de Dualidad. Si una expresión booleana es verdadera, su expresión dual también lo es.

O Expresiones duales. Dos expresiones se dicen duales una de la otra, si una se puede obtener de la otracambiando las operaciones ( + ) por (.) y viceversa y cambiando los O's por 1 's y viceversa.

Teorema 1. Multiplicación por cero

a) A.0 = 0

b) A+1 = 1

Explicación:

A.0 = A.0 + 0 0 es el neutro de la suma

= A.0 + A.A el producto de una variable por su complemento da 0

= A.(0 + A) distributividad

= A.(A) una variable más el neutro no se altera

= 0 una variable por su complemento da 0

Teorema 2. Absorción

a) A + AB = A

b) A(A + B) = A

F De aquí en adelante, de acuerdo al principio de dualidad demostrar sólo un inciso de los siguientes teoremas y automáticamente el inciso dual quedará demostrado.

Explicación:

A + AB = A.1 + AB 1 es el neutro del producto

= A(1 + B) distributividad

= A(1) Teorema 1

= A es el neutro del producto

Este teorema se puede usar en diversos casos de simplificación, basta con usar identificar en una suma, una expresión que se repite primero en forma aislada y luego multiplicando a otra expresión.

Teorema 3. Cancelación

a) A + AB = A + B

b) A(A + B) = A B

Explicación:

A + AB = (A+A)(A+B) distributividad

= 1.(A+B) la suma de una variable con su complemento es 1

= A+B 1 es el neutro del Producto

Este teorema se puede usar en la simplificación de expresiones cuando encontramos una expresión sumada Con su complemento multiplicado por otra expresión (o el dual).

Teorema 4. Cancelación

a) AB + AB = B

b) (A+B)(A+B)=B

Explicación:

AB + AB = (A+A )B distributividad

= 1.B la suma de una variable con su complemento es 1

= B 1 es el neutro del producto

Para usar este resultado hay que identificar dos términos que tienen un factor común y el término que no es común en una de ellas es el complemento del de la otra.

Teorema 5. Idempotencia

a) A.A = A

b\ A+A= A

La demostración del inciso (b) de este teorema es inmediata del teorema de absorción, ya que A + A =

A+ A.1.

Este teorema implica que cuando existen términos semejantes en una expresión, basta con escribir uno de ellos, o bien, que un término puede "desdoblarse" tantas veces como se quiera. Obsérvese que también esto implica que An = A para cualquier número n entero positivo.

Teorema 6. Consenso

a) AB + AC + BC = AB + AC

b) (A+B)(A+C)(B+C) = (A+B)( A+C)

Explicación:

AB +AC + BC = AB +AC + BC(A +A) A+A es el neutro de la multiplicación

= AB +AC +ABC +ABC distributividad

= (AB +ABC) + AC +ABC) conmutatividad y asociatividad

= AB + AC absorción

La clave para usar este teorema es encontrar dos términos que contengan una expresión en uno afirmada y en otro negada, anotar los términos con los que están multiplicando uno y otro y buscar otro elemento que sea la multiplicación de estos últimos dos, éste último elemento es el que se puede eliminar.

Teorema 7. Teorema de De Morgan

a) AB = A+B

b) A+B = AB

El teorema de De Morgan se puede generalizar al caso de más de dos variables booleanas, por ejemplo, para 3 variables, tenemos que A+B+C = (A+B )C = ABC, en forma similar, A.B.C = (A.B )+C = A+B+C , y así sucesivamente para más de tres variables.

Teorema 8. Involución

a) A=A

Teorema 9. Complementos de los neutros

a) 0 = 1, b) 1 = 0

Postulados

1.- La suma lógica de una variable a y 1 es siempre 1. f (a + 1) = 1

2.- La suma lógica de un 0 y una variable a, siempre da el valor de la variable a. f (a + 0) = a

3.- La suma lógica de una variable consigo misma, siempre da en la salida el mismo valor de la variable. f (a + a) = a

4.- La suma lógica de una variable y la inversa de ésta siempre da en la salida 1, ya que al menos uno de ellos vale 1. f (a + not a) = 1

5.- La multiplicación lógica de una variable a y un 1 siempre da como resultado el valor de la variable a. f (a · 1) = a

6.- La multiplicación lógica de un cero y una variable a, da en la salida un 0. f (a · 0) = 0

7.- La multiplicación lógica de una variable a consigo misma, da como resultado el valor de la variable a. f (a · a) = a

8.- La multiplicación lógica de una variable a por la inversa de ésta, dará a la salida siempre 0. f (a · not a) = 0

4.2 Optimización de expresiones booleanas.

Las expresiones booleanas se usan para determinar si un conjunto de una o más condiciones es verdadero o falso, y el resultado de su evaluación es un valor de verdad. Los operandos de una expresión booleana pueden ser cualquiera de los siguientes:

• Expresiones relacionales: que comparan dos valores y determinan si existe o no una cierta relación entre ellos (ver más adelante), tal como mfn<10;
• Funciones booleanas: tal como p(v24), que regresa un valor de verdad (estos se explican bajo "Funciones booleanas").

Las expresiones relacionales permiten determinar si una relación dada se verifica entre dos valores. La forma general de una expresión relacional es:

 Expresión-1 operador-de-relación expresión-2

 Donde:

• expresión-1 es una expresión numérica o de cadena
• operador-de-relación es uno de los siguientes:

•  = Igual
• <> No igual (diferente de)
• < Menor que
• <= Menor o igual que
• > Mayor que
• >= Mayor o igual que
• : Contiene (puede ser usado sólo en expresiones de cadena)

• expresión-2 es una expresión del mismo tipo que expresión-1, o sea, expresión-1 y expresión-2 deben ser ambas expresiones numéricas o ambas expresiones de cadena.

Los operadores de relación = <> < <= > >= tienen su significado convencional cuando se aplican a expresiones numéricas (dentro de los límites de precisión de los valores numéricos definidos bajo "Expresiones numéricas"). Cuando se comparan expresiones de cadena, se aplican las siguientes reglas:

• Excepto por el operador ":" (contiene), las cadenas se comparan exactamente en la forma en que ocurren, o sea, las letras mayúsculas y minúsculas se comparan de acuerdo con el código ASCII que les corresponde (p.ej. A será considerada menor que a);
• Dos expresiones de cadena no son consideradas iguales, a menos que tengan la misma longitud. Si dos expresiones generan cadenas de diferente longitud que son idénticas, carácter por carácter, hasta el total de la longitud de la más corta, entonces, la más corta será considerada menor que la más larga.

El operador: (contiene), busca una cadena de caracteres (definida por expresión-2) en otra cadena (definida por expresión-1). Si el segundo operando existe en cualquier parte del segundo operando, el resultado es Verdadero (TRUE). Este operador es insensible al hecho de que los caracteres se hallen en mayúsculas o minúsculas: por lo que las letras minúsculas se consideran iguales a su letra mayúscula correspondiente. Por ejemplo, el resultado de:

...