Expresiones Booleanas

Expresiones Booleanas

Esta pagina va a ser modificada por Angelica Vargas Ramirez e Hiram Diaz Camarena

ALGEBRA BOOLEANA

DEFINICION: El Algebra Boolena es un sistema cerrado formado por un conjunto P de dos o más elementos que pueden tomar dos valores perfectamente diferenciados (0 - 1, V - F, Abierto - Cerrado, etc.) y dos operaciones binarias: suma (+) o función OR y producto (*) o función AND, y que cumplen los siguientes axiomas o postulados:

a) Conmutatividad. “A Î P y “ B Î P se cumple que A + B = B + A A * B = B * A

b) Asociatividad “A, B y C Î P se cumple que (A + B) + C = A + (B + C) = (A + C) + B (A * B) * C = A * (B * C) = (A * C) * B

c) Distributividad “ A, B y C Î P se cumple que A + (B * C) = (A + B) * (A + C)+ A * (B + C) = (A * B) + (A * C)

d) Elemento Idéntico 0 es el elemento idéntico de la suma A + 0 = A 1 es el elemento idéntico del producto A * 1 = A

e) Complemento o inverso “ A Î P , $ �� Î P tal que �� + A = 1 y���� * A = 0 Esta función se conoce como función NOT. De aquí se concluye que 0 = 1 y 1 = 0 Algunas definiciones interesantes: Variable: Símbolos que pueden tomar los valores 0 o 1 en cualquier instante de tiempo. Constante: Símbolo que toma sólo un valor 0 o 1 para todo instante de tiempo. Expresión booleana o expresión de conmutación: combinación de un número finito de variables y constantes por medio de las operaciones suma y producto

Ejemplo: f (a, b, c, d) = a + b*c + d *a*(b + c)

TEOREMAS DEL ALGEBRA DE BOOLEANA

Teorema 1: Cada identidad deducida de los postulados anteriores permanece válida si las Operaciones suma (+) y producto (*) y los elementos 0 y 1 se intercambian entre sí. Este es el principio de dualidad y se deduce de la simetría de los cuatro postulados con respecto a ambas operaciones y a ambos elementos neutros.

Teorema 2: Para cada elemento A se cumple que A + 1 = 1 y su dual A * 0 = 0

Demostración: 1=a+ a postulado e) = a + a 0 1 postulado d) = (a + a) 0 (a + 1) postulado c) = 1 0 (a + 1) postulado d) 1 = a + 1 postulado c)

Teorema 3: Para cada elemento A del Algebra de Boole se verifica que A + A = A Y su dual A * A = A

Demostración:a = a + 0 postulado d) = a + a 0 a postulado e) = (a + a ) 0 (a + a ) postulado c) = (a + a ) postulado e)

Teorema 4: Para cada par de elementos A y B del Algebra de Boole, se cumple que: A + A * B = A y su dual A * (A + B) = A

‘’‘Este teorema se conoce como Ley de Absorción. Demostración:’‘’ a = 1 * a postulado d) = (1 + b) * a teorema 2) = (1 * a) + (a * b) postulado c) = a + (a * b) postulado d)

Otra forma de demostrar es usando las tablas de verdad: a b a*b a + a*b 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 Son iguales

Teorema 5: Para todo elemento A, se verifica que a = a

Teorema 6: Leyes de De Morgan. a) a + b + c + d + … = a * b * c * d * … b) a * b * c * d * … = a + b + c + d + …

Este teorema define dos nuevas funciones lógicas: NOR (NO-OR) y NAND (NO-AND) Con estos teoremas podemos definir los valores numéricos de las operaciones booleanas OR AND N O T 0 + 0 = 0 0 * 0 = 0 0 = 1 0 + 1 = 1 0 * 1 = 0 1 = 0 1 + 0 = 1 1 * 0 = 0 0 = 0 1 + 1 = 1 1 * 1 = 1 1 = 1

FUNCIONES LOGICAS O FUNCIONES DE CONMUTACION:

Definiciones previas:

Una función del Algebra de Booleana es una variable binaria cuyo valor depende de una expresión Algebraica en la que se relacionan entre sí las variables binarias por medio de las operaciones básicas. Representación: f = f(a, b, c)

La tabla de verdad de una función lógica es una forma de representación de la misma, en la que se indica el valor 1 o 0 que toma la función para cada una de las posibles combinaciones de las variables de la función. Se llama término canónico de una función lógica a todo producto o suma en la cual aparecen todas las variables en su forma directa o inversa. A la suma canónica se le llama maxterm y al producto canónico se le llama minterm Ejemplo: Sea la tabla de verdad de una función de tres variables: Decimal a b c f(a, b, c) Este 1 se obtiene como 0 0 0 0 0 1 0 0 1 1 a * b * c 2 0 1 0 0 3 0 1 1 1 a * b * c 4 1 0 0 1 a * b * c 5 1 0 1 0 6 1 1 0 1 a * b * c 7 1 1 1 1 a * b * c

Para obtener la función lógica que representa esta tabla de verdad, podemos elegir trabajar con aquellas combinaciones en que f(a, b, c) = 1 o con aquellas combinaciones en que f(a, b, c) = 0. En el caso de las combinaciones correspondientes a los decimales 1, 3, 4, 6 y 7, la función toma el valor 1 (Combinaciones que se denominan minterm). Se forma el producto canónico asignando al estado 1 la variable directa y al estado 0 la variable inversa. En nuestro ejemplo, para el minterm 0 0 1 tenemos 0 0 1 estado 1 variable directa c estado 0 variable inversa b estado 0 variable inversa a Por lo tanto 0 0 1 a b c En nuestro ejemplo, la función toma el valor 1 para cinco de las ocho posibles combinaciones, luego debemos considerar las cinco situaciones en las que f(a, b, c) = 1. f(a, b, c) = a b c + a b c + a b c + a b c + a b c A esta forma de representar la función se le denomina suma de productos, y como todos los términos involucrados en la función son canónicos, entonces la función toma el nombre de función canónica suma de productos (función canónica OR de AND)Si asignamos a cada combinación binaria de entrada el número decimal equivalente, podemos obtener la expresión abreviada de la función: f(a, b, c) = å3 (1, 3, 4, 6, 7) Por otro lado, si buscamos representar la función por medio de las combinaciones en las que f(a, b, c) = 0, debemos considerar a las variables cuyo valor es cero en su forma directa y si el valor de la variable es 1 en su forma inversa, con lo cual formamos la suma canónica. De esta forma, en nuestro ejemplo A b c 0 1 0 a + b + c Y para la función misma F (a, b, c) = ( a + b + c ) * ( a + b + c ) * ( a + b + c ) En su forma abreviada es: f(a, b, c) =Õ3 (0, 2, 5) A esta representación se le llama función canónica producto de sumas (función canónica AND de OR) Simplificación de funciones. Para simplificar funciones, se usan los teoremas del Algebra de Boole y las leyes de De Morgan. Ejemplo: Reducir la función: f(a, b, c) = ac + bc + a b Solución: f(a, b, c) = ac + bc + a b = ac + bc (a + a ) + a b postulado d) = ac + abc + a b c + a b postulado c) = ac (1 + b) + a b (c + 1) postulado c) = ac + a b teorema 2) Ejemplo: Reducir: f(a, b, c) = a + b + c + abc teorema de Morgan = a b c + abc postulado e) = 1 Transformación de funciones a formas canónicas.

Primer método: Se agrega a cada término no canónico, la(s) variable(s) que falta(n), en forma directa o complementada. Caso 1) usando mintermino f(a, b, c) = a b + a b c = a b (c + c ) + a b c = a b c + a b c + a b c = n 3 ( 5 , 6 , 7 ) Caso 2) usando maxtermino f(a, b, c) = a b + a b c = a ( b + b c ) 1 = a * ( b + b ) * ( b + c ) = a * ( b + c ) = a + ( b b ) + ( c c ) * ( a a ) + ( b + c ) = [ ( a + b ) ( a + b ) + ( c c ) ] * [ ( a + b + c ) ( a + b + c ) ] = [ ( a + b ) ( a + b ) + c ] [ ( a + b ) ( a + b ) + c ] [ ( a + b + c ) ( a + b + c ) ] = ( a + b + c ) ( a + b + c ) ( a + b + c ) ( a + b + c ) ( a + b + c ) ( a + b + c ) = ( a + b + c ) ( a + b + c ) ( a + b + c ) ( a + b + c ) ( a + b + c ) = m 3 ( 0 , 1 , 2 , 3 , 4 )

Una función expresada en forma canónica suma de productos (OR de AND) permite visualizar rápidamente los “1” de la función.

Una función expresada en forma canónica producto de sumas (AND de OR) permite visualizar rápidamente los “0” de la función.

Segundo método: Usando las tablas de verdad. a b c f(a, b, c) 0 0 0 0 0 0 1 0 0 1 0 0 f(a, b, c) = m 3 ( 0, 1, 2, 3, 4) 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 f(a, b, c) = n 3 ( 5, 6, 7) 1 1 1 1 (:include urlhttp://docs.google.Presentation Editor??id=dc2mr285_13hd5nkvcq

 http://docs.google.com/Presentation?id=dc2mr285_13hd5nkvcq

Mis sitios nuevos:
Emprendedores
Politica de Privacidad