algebra booleana

Download Algebra Booleana

Post on 09-Jul-2015

447 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

ALGEBRA BOOLEANAlgebra de Boole El lgebra booleana es la teora matemtica que se aplica en la lgica combinatoria. Las variables booleanas son smbolos utilizados para representar magnitudes lgicas y pueden tener slo dos valores posibles: 1 (valor alto) 0 (valor bajo). El lgebra booleana proporciona las operaciones y reglas para trabajar con el conjunto {0,1}. Los conmutadores elctricos y pticos pueden ser estudiados usando este conjunto y las reglas del lgebra booleana. Las 3 operaciones booleanas mas usadas son: Complemento (denotado con una barra superior) es definido como: 0 = 1y 1= 0

Suma (denotada por + o por OR) es definida como: 1+1=1, 1+0=1, 0+1=1 y 0+0=0 Producto (denotado por . o por AND) es definido como: 1.1=1, 1.0=0, 0.1=0 y 0.0=01 Matemticas Discretas

ALGEBRA BOOLEANALas reglas de precedencia son: complemento, AND y OR. Es claro que el complemento y la suma y producto bolanos corresponden a los operadores lgicos , y respectivamente donde 0 corresponde a falso (F) y 1 corresponde a verdadero (V).1.0 + (0 + 1) Ej: Evaluar Sol: Utilizando las definiciones de complemento, la suma booleana y el producto booleano se tiene que:1.0 + (0 + 1) = 0 + 1 =0+0 =0

2

Matemticas Discretas

ALGEBRA BOOLEANAExpresiones booleanas y Funciones Booleanas Sea B={0,1}. Entonces Bn={(x1, x2,...xn) xiB para 1 i n} es el conjunto de todas las tuplas posibles de 0s y 1s. La variable x es llamada una variable booleana si ella asume valores solo de B (0 y 1). Una funcin de Bn en B es llamada una funcin booleana de grado n. Ej: La funcin F(x,y)= es una funcin de grado 2 con los siguientes valoresx 1 1 0 0 y 1 0 1 0 F(x,y) 0 1 0 0

La funcin F ( x, y ) = x y es una funcin de grado 2, con F(0,0)=0, F(1,0)=1, F(0,1)=0 y F(1,1)=0

3

Matemticas Discretas

ALGEBRA BOOLEANAEj: Calcular los valores de la funcin booleana F(x,y,z)=xy+z 1=(Z+Z)x 1 1 1 1 0 0 0 0 y 1 1 0 0 1 1 0 0 z 1 0 1 0 1 0 1 0 xy 1 1 0 0 0 0 0 0 z 0 1 0 1 0 1 0 1 F(x,y,z)=xy+z 1 1 0 1 0 1 0 1

xyz Xyz XYZ

XYZ XYZ

XY+Z=XYZ+XYZ+XYZ+XYZ

4

Matemticas Discretas

ALGEBRA BOOLEANAUna funcin booleana de grado dos es una funcin de un conjunto de cuatro elementos, a saber, todos los pares de elementos de B={0,1}, en B, un conjunto con dos elementos. Por tanto hay 16 funciones booleanas diferentes de grado 2.x 1 1 0 0 y F1 F2 1 1 1 0 1 1 1 1 1 0 1 0 F3 1 1 0 1 F4 1 1 0 0 F5 1 0 1 1 F6 1 0 1 0 F7 1 0 0 1 F8 1 0 0 0 F9 0 1 1 1 F10 F11 F12 F13 F14 F15 F16 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0

La cantidad de funciones booleanas de grado n son: Por ejemplo:

2

2n

F6 = xy + x y

5

Matemticas Discretas

ALGEBRA BOOLEANAPropiedades de un lgebra de BooleIdentidades booleanas Identidad __x=x x+x=x x.x =x x+0=x x.1 =x x+1=1 x.0 =0 x+y=y+x x.y =y.x x + (y + z) = (y + x) + z x . (y . z) = (y . x) . z x + (y . z) = (x + y) . (x + z) x . (y + z) = (x . y) + (x . z) x. y = x + y x + y = x. y x + x.y = x x . (x + y) = x x + x =1 x.x = 06

Nombre Doble complemento Idempotencia Identidad Dominacin Conmutativa Asociativa Distributiva De morgans Absorcin Propiedad unidad Propiedad ceroMatemticas Discretas

ALGEBRA BOOLEANAEj: Demostrar que se cumple la propiedad distributiva x(y+z)=xy+xzx 1 1 1 1 0 0 0 0 y 1 1 0 0 1 1 0 0 z 1 0 1 0 1 0 1 0 y+z 1 1 1 0 1 1 1 0 xy 1 1 0 0 0 0 0 0 xz 1 0 1 0 0 0 0 0 x(y+z) xy+xz 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0

Ej: Probar la ley de absorcin x(x+y)= x usando las otras identidades. Sol: x.(x+y) = (x+0).(x+y) (identidad suma booleana ) = x + (0.y) (distrib. suma booleana s/ el prod. booleano) = x + (y.0) (conmutativa producto booleano) =x+0 (dominacin producto booleano) =x (identidad suma booleana).

7

Matemticas Discretas

ALGEBRA BOOLEANAEj: Simplificar F=F = A BC + A BC F = A B(C + C) F = AB

F = (A + B)(A + B) F = A A + A B + AB + BB F = A B + ABF = [(A + C)(B + D)] F = ( A + C) + ( B + D ) F = AC + BD

F = (X + Z)( Z + WY) + (VZ + W X)(Y + Z)

8

Matemticas Discretas

EJERCICIOS Simplificar:

Calculas los valores de las siguientes funciones booleanas:

Realizar los ejercicios del Libro de Rosen: Problemas Complementarios 1 y 2. Tema: lgebra Boole. Pgina: 653.

ALGEBRA BOOLEANADualidad Es una expresin booleana que se obtiene intercambiando entre s la suma y el producto booleanos, as como los ceros y unos. Ej: Calcular el dual de x(Y+0) = x+(Y . 1) X . 1 +(Y + z) = (X + 0) . (Y+z)

El dual de una funcin booleana F representado por una expresin booleana es la funcin representeada por el dual de dicha expresin. Se denota por Fd. Una igualdad entre funciones booleanas sigue siendo vlida cuando se toman duales a ambos lados de la igualdad (Principio de la dualidad), el cual es muy til para la obtencin de nuevas propiedades

9

Matemticas Discretas

ALGEBRA BOOLEANARepresentacin de Funciones Booleanas A partir de los valores de una funcin booleana, se va a obtener una expresin booleana que represente a dicha funcin (Suma de Productos), utilizando los tres operadores booleanos (+ . ) Determinar el mnimo conjunto de operadores para representar dichas funciones. Desarrollo en suma de productos Toda funcin booleana se puede representar mediante una suma booleana de productos booleanos de variables y variables complementadas.

10

Matemticas Discretas

ALGEBRA BOOLEANAEj: Para cada una de las funciones F(x,y,z) y G(x,y,z), calcular una expresin booleana que la represente.x 1 1 1 1 0 0 0 0 y 1 1 0 0 1 1 0 0 z 1 0 1 0 1 0 1 0 F 0 0 1 0 0 0 0 0 G 0 1 0 0 0 1 0 0

Sol: Para representar a F se necesita una expresin que valga 1 cuando x=1,y=0 y z=1. Esa expresin sera: x y z Para representar a G, se necesita una expresin que valga 1 cuando x=1,y=1,z=0 o cuando x=0,y=1, y z=0. La expresin quedara: xy z + x y z

11

Matemticas Discretas

ALGEBRA BOOLEANAMiniterm Un literal es una variable booleana o su complemento. Un minterm de las variables booleanas x1,x2,...xn es un producto booleano y1,y2,...yn, donde yi=xi o yi=Xi. Por ello, un minterm es un producto de n literales, con un literal por cada variable. Un minitrmino vale 1 para una y slo una combinacin de sus variables Los minterms en una suma booleana corresponde a las combinaciones para las cuales la funcin tiene el valor 1. La suma de minterms que representa esta funcin es llamada la expansin en suma de productos o la forma normal disyuntiva de la funcin booleana. Del ejemplo anterior:

G = xy z + x y z

12

Matemticas Discretas

ALGEBRA BOOLEANAEj: Hallar la FND de la funcin F(x,y,z) = (x+y)Z Sol: Existen dos maneras. La primera desarrollar y simplicar el producto utilizando las propiedades del algebra booleana F(x,y,z) = (x+y)Z = xZ + yZ Distributiva = x1Z +1yZ Identidad = x(y+Y)Z+(x+X)yZ Inverso = xyZ+xYZ+xyZ+XyZ Distributiva = xyZ+xYZ+XyZ Idempotencia La segunda consiste en calcular los valores de F para todos los valores posibles de las variables x,y,z. x y z x +y Z (x +y )Z1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0

F(x,y,z)= (x+y)Z F(x,y,z)= xyZ+xYZ+XyZ

13

Matemticas Discretas

ALGEBRA BOOLEANACompletitud Funcional Es claro que cada funcin booleana puede ser expresada como una suma de minterminos, es decir puede ser representada usando los operadores del conjunto {+ , . , } por lo cual podemos decir que este es funcionalmente completo. Es claro tambin que podemos eliminar todas las sumas booleanas aplicando las leyes de morgan, pues, x+y= X Y es decir las funciones pueden ser representadas usando los operadores del conjunto {+ , . , } por lo cual podemos decir que este conjunto tambin funcionalmente completo. Igualmente podemos eliminar todas los productos booleanos aplicando las leyes de morgan, pues xy= X+Y , es decir las funciones pueden ser representadas usando los operadores del conjunto {+, } por lo cual podemos decir que este conjunto tambin es funcionalmente completo.

14

Matemticas Discretas

ALGEBRA BOOLEANASi se definen los operadores NAND () y NOR () cuyas tablas las cuales son definidos como: Operador Definicin NAND 11 = 0 10 = 1 01 = 1 00 = 1 NOR 11 = 0 10 = 0 01 = 0 00 = 1 Ambos operadores son funcionalmente completos.X =X|X XY = (X | Y) | (X | Y) X + Y = (X | X) | (Y | Y)X=XX XY = (X X) (Y Y) X + Y = (X Y) (X Y)15 Matemticas Discretas

ALGEBRA BOOLEANAOperador NAND Definicin 11 = 0 10 = 1 01 = 1 00 = 1 11 = 0 10 = 0 01 = 0 00 = 1

NOR

X =X|X XY = (X | Y) | (X | Y) X + Y = (X | X) | (Y | Y)X 1 1 0 0 Y 1 0 1 0 X|X Y|Y X|Y 0 0 1 1 0 1 0 1 0 1 1 1 XY X+Y (X|Y)|(X|Y) (X|X)|(Y|Y) 1 1 0 1 0 1 0 0

X=XX XY = (X X) (Y Y) X + Y = (X Y) (X Y)X 1 1 0 016

Y 1 0 1 0

XX YY XY 0 0 1 1 0 1 0 1 0 0 0 1

XY X+Y (XX)(YY)(XY)(XY) 1 1 0 1 0 1 0 0Matemticas Discretas

ALGEBRA BOOLEANAPuertas Lgicas El Igebra de Boole se utiliza para modelar los circuitos de dispositivos electrnicos. Cada entrada y salida de estos dispositivos se puede ver como un elemento del conjunto (O, I ). Un computador, u otro dispositivo elctrico, se compone de un cierto nmero de circuitos. Cada circuito se puede disear utilizando las reglas del Igebra de Boole estudiadas. Los elementos bsicos de los circuitos se llaman puertas Igicas. Cada tipo de puerta implemen-ta una operacin booleana Circuitos Combinacionales Producen una salida que depende solamente de la entrada y no del estado actual del circuito. (No tienen memoria). Se van a utilizar la puertas lgicas y la reglas del algebra de boole para disear circuitos.17 Matemticas Discretas

ALGEBRA BOOLEANAPuerta Not - Inversor

Tiene como entrada el valor de una variable booleana y produce como salida el complemento de dicho valor Puert