4ta semana: funsion booleana...

Si se hace un análisis comparativo del cálculo proposicional y la teoría de conjuntos, con sus conectivos lógicos y las operaciones unión, intersección y complemento respectivamente, se observa un comportamiento idéntico.
EL álgebra booleana provee operaciones y reglas para trabajar con el conjunto de {0, 1}. 0 ® F y 1® V.
Las 3 operaciones del álgebra booleana son complemento, suma y producto booleano.
El complemento es definido por ¬0 = 1 y ¬1 = 0. La suma es definido por +, or 1 + 1 = 1, 1 + 0 = 1, 0 + 1=1, 0 + 0 = 0. El producto es definido por •, and 1 • 1 = 1, 1 • 0 = 0, 0 • 1 = 1, 0 • 0 = 0. Precedencia son ¬, • , +.
Ejemplo : Encuentre el valor de 1 • 0 + ¬(0 + 1).
EXPRESIONES BOOLEANAS
Definición : Una expresión booleana es una sucesión de símbolos que incluye 0,1, algunas variables x, y, z y las operaciones booleanas + , •. Para ser más precisos definamos una expresión boolena en n variables x1, x2..., xn recursivamente como:

• Los símbolos 0 y 1 y x1, x2,..., xn son expresiones booleanas en x1, x2,... xn.
• Si E1 y E2 son expresiones booleanas en x1, x2,... xn también lo son E1 + E2; E1 E2 y ¬E1.

Ejemplo : Las siguientes son cuatro expresiones booleanas en las tres variables x, y, z:

• (x + y)•(x + z)
• ¬x•z + ¬x•y + ¬z.

Es obvio que las expresiones del lado izquierdo involucran las tres variables. Las expresiones booleanas 0 y 1 pueden verse como expresiones en cualquier número de variables.
FUNCIONES BOOLEANAS
Definición : La función booleanas F(x,y) con valores 1 donde x = 1 e y = 0 y el valor 0 para todas las otras elecciones x e y. Las funciones booleanas pueden ser representadas usando expresiones con variables y operaciones booleanas.

x	y	F(x, y)
1	1	0
1	0	1
0	1	0
0	0	0

Cada expresión booleana representa una función. El valor de la función es obtenido sustituyendo 0 y 1 por los valores de las variables en la expresión.

x	y	z	x•y	¬x	F(x, y,z) =x•y +¬z
1	1	1	1	0	1
1	1	0	1	1	1
1	0	1	0	0	0
1	0	0	0	1	1
0	1	1	0	0	0
0	1	0	0	1	1
0	0	1	0	0	0
0	0	0	0	1	1

Las funciones booleanas F y G de n variables son iguales si y solo si F(b1, b2, ..., bn) = G(b1, b2, ..., bn). Dos funciones diferentes que tienen los mismos valores de verdad en su tabla son llamadas equivalentes. El complemento de una función booleana F es la función ¬F, donde ¬F(x1, x2, ..., xn) = ¬(F(x1, x2, ..., xn).
La suma booleana F + G y el producto FG es definido por (F + G)(x1, x2, ..., xn) = F(x1, x2, ..., xn) + G(x1, x2, ..., xn) y (FG)(x1, x2, ...,xn) = F(x1, x2, ...,xn) G(x1, x2, ...,xn).
IDENTIDADES EN ÁLGEBRA BOOLEANAS

Equivalencia Lógica
X º ØØX	Doble negación
X • X º X	Idempotencia
X + X º X	Idempotencia
X + (Y + Z) º (X + Y) + Z	Ley asociativa
X • (Y • Z) º (X • Y) • Z	Ley asociativa
(X + Y) º (Y + X)	Ley conmutativa
(X • Y) º (Y • X)	Ley conmutativa
X + (Y • Z) º (X + Y) • (X + Z)	Ley distributiva
X • (Y + Z) º (X • Y) + (X • Z)	Ley distributiva
Ø (X + Y) º ØX • ØY	Ley de De Morgan
Ø (X • Y) º ØX + ØY	Ley de De Morgan
X + 0 º X	Ley de identidad
X • 1 º X	Ley de identidad
X + 1 º 1	Ley de dominación
X • 0 º 0	Ley de dominación
X + (X • Y) º X	Ley de cobertura
X • (X + Y) º X	Ley de cobertura
Ø X • X º 0	Ley de contradicción
ØX + X º 1	Ley de contradicción

Principio de la dualidad : Toda proposición o identidad algebraica sigue siendo válida, si todas las operaciones (+) y (•) y los elementos identidad 0 y 1 son intercambiados. Si una proposición o una expresión algebraica se obtiene de otra por una sola aplicación del principio de la dualidad, la segunda se llamará la dual de la primera y recíprocamente.
Ejemplo

• Se tiene que a + a•b entonces por el principio de la dualidad se puede concluir que a•(a + b).
• Se tiene que x•(x+y) entonces por el principio de la dualidad se puede concluir que a = x +(x•y).

Representación de Funciones Booleanas
Los más importante del algebra booleana es :

• Dados los valores de una función booleana, podemos encontrar una expresión booleana que representa esta función. Las funciones booleanas pueden ser representadas por sumas, productos y complemento booleana de variables (•, +, ¬).

Expansión de Suma de Productos
Ejemplo : Encontrar una expansión booleana que represente las funciones F(x, y, z) y G(x, y, z), las cuales son :

x	y	z	F	G
1	1	1	0	0
1	1	0	0	1
1	0	1	1	0
1	0	0	0	0
0	1	1	0	0
0	1	0	0	1
0	0	1	0	0
0	0	0	0	0

Solución : el producto booleano de F = x¬yz y G= xy¬z + ¬xy¬z.
Definición : Un literal es una variable booleana o su complemento.
Un mintérmino de las variables booleanas x1, x2, ..., xn es un producto booleano y1• y2, ...yn donde yi = xi o yi = ¬xi, un mintérmino es un producto de n literales, con un literal para cada variable.
Forma normal disyuntiva : Una expresión booleana está en forma normal disyuntiva con n variables x1, x2,... xn, si la expresión es una suma de términos del tipo E1(x1) • E2( x2) • ... • En(xn), donde Ei(xi) = xi o ¬xi para i = 1, 2,..., n, y ningún par de términos son idénticos.
Toda expresión booleana que no contiene constantes es igual a una función en forma normal disyuntiva.
Ejemplo.

• Escribir ¬(x•¬y + x•z) + ¬x en F.N.D
• Escribir (x + y)•¬z en F.N.D, luego generar la tabla y encontrar la suma de productos en expansión.
• Encuentre y simplifique la expresión booleana especificada por la siguiente tabla.

  x	y	z	x+y	¬z	(x+y)¬z
  1	1	1	1	0	0
  1	1	0	1	1	1
  1	0	1	1	0	0
  1	0	0	1	1	1
  0	1	1	1	0	0
  0	1	0	1	1	1
  0	0	1	0	0	0
  0	0	0	0	1	0

• Exprese cada una de las siguientes funciones en F.N.D con el menor número posible de variables.
  • (u + v + w)(uv + u’w)’
  • (x + y)(x + y’)( x’ + z’)
  • xyz + (x + y)(x + z)
• Encuentre el complemento de las siguientes funciones: x’z + xz’ xy + x’y + x’y’
• Simplifique las siguientes expresiones usando teoremas del álgebra booleana.
  • xy + (x + y)z’ + y
  • x + y + (x’ + y + z)’
  • yz + wx + z + wz(xy + wz)
  • xyz + x’yz + x’y’z’ + x’y’z + xy’z + xy’z’.