algebra de boole patricia guerrero

Elementos Discretos

Álgebra de Boole

Álgebra de Boole

Patricia Guerrero

Contenido

• Reseña Histórica

• Definición del Álgebra de Boole

• Principio de Dualidad

• Propiedades del Álgebra de Boole

• Ejemplos

• Expresiones Booleanas

• Representación de Expresiones Booleanas

• Formas Canónicas: Mintérminos y Maxtérminos

• Simplificación: Mapas de Karnaugh

• Circuitos Lógicos

Álgebra de BooleReseña Histórica

• En 1854, desarrollo del Álgebra Booleana por el filósofo y matemático inglés George Boole

• En 1869, primera máquina que utilizaba el Álgebra Booleana. William Stanley Jevons.

Álgebra Boolena

Símbolos Algebraicos

Lógica= +

Sistema de Numeración Binario

Computadoras Electrónicas

Un Álgebra de Boole está definida por:

• Un conjunto no vacío K

• Un conjunto de operaciones que actúan sobre los elementos de K y que deben cumplir ciertas condiciones. Dos operaciones binarias {*, º} y una operación unaria {-}

Y se denota como:

Álgebra de BooleDefinición

)k,k-, ,º(K,*,K 21

¿Cuáles son las condiciones?

• Conjunto Cerrado: * y º son l.c.i

• Ley Conmutativa: * y º son conmutativos

• Ley Asociativa: * y º son asociativos

Álgebra de BooleDefinición

)k,k-, ,º(K,*,K 21x * y, x º y K

k1, k2 K

x * y = y * x

x º y = y º x

(x * y) * z = x * (y * z)

(x º y) º z = x º (y º z)

Álgebra de BooleDefinición

)k,k-, ,º(K,*,K 21x * (y º z) =, (x * y) º (x * z)

x º (y * z) =, (x º y) * (x º z)

x * k1 = x

x º k2 = x

a * ā = k2

a º ā = k1

¿Cuáles son las condiciones?

• Ley Distributiva: * y º son distributivas una respecto de la otra

• Elementos Neutros: k1 y k2

• Complementación: Todo a K, admite un ā

Álgebra de BoolePrincipio de Dualidad

Cualquier teorema deducible de los postulados del álgebra de Boole, puede transformarse en un segundo teorema o identidad válida sólo intercambiando * por º y k1 por k2, o viceversa

La demostración de un teorema implica la validez de su teorema dual

Ejemplos:

a * ā = k2 ------ dual ------ a º ā = k1

A = ------ dual ------ A U = UQ v Q ------ dual ------ Q f Q

)k,k-, ,º(K,*,K 21

Álgebra de BoolePropiedades

Para cualquier Álgebra de Boole se

cumplen las siguientes propiedades, con x, y K:

• Idempotencia x * x = x x º x = x

• Absorción x * (x º y) = x x º (x * y) = x

• Ley De Morgan (x * y) = x º y (x º y) = x * y

• Dominancia x * k2 = k2 x º k1 = k1

• Doble Complementación x = x

Idempotencia:x * x = xx * x = (x * x) º k2 (1) Elemento

Neutro = (x * x) º (x * x) (2) Complementación = x * (x º x) (3) Distributiva = x * k1 (4) Complementación

x * x = x (5) Elemento Neutro

Demostremos algunas propiedades:

Álgebra de BoolePropiedades

Es posible demostrar una propiedad del Álgebra de Boole, algebraicamente o utilizando tablas de verdad

Absorción:

x * (x º y) = xx * (x º y) = (x º 1) * (x º y) (1) Elemento

Neutro = x º (1 * y) (2) Distributiva

= x º 1 (3) Dominancia

x * (x º y) = x (4) Elemento Neutro

Demostremos algunas propiedades:

Álgebra de BoolePropiedades

Ejemplo: Sea S un conjunto cualquiera, entonces

es un Álgebra de Boole.

S),,,,(P(S), S c

Se cumplen las seis (6) condiciones:, : Son l.c.i. en P(S), S: Son elementos neutros de , respectivamente, : Son conmutativos y asociativos, : Son distributivos uno respecto del otroCada Si P(S) admite un Si, tal que Si Si = S y Si Si =

Álgebra de BooleEjemplos

Justificación:

+ no es distributivo respecto de *

No se cumple la complementación: x + (-x) = 0 1x * (-x) = -(x2) 0

Contraejemplo: La estructura

no es un Álgebra de Boole.

,0,1),*,(R, R Neutro del operador *

Neutro del operador +

Álgebra de BooleEjemplos

Modelo de Conmutación:

Con B = {1, 0}

1) 0, , , . , (B, B

Operaciones Binarias, equivalentes a

, respectivamente

Operación Unaria, equivalente a

Álgebra de BooleEjemplos

Modelo de Conmutación:

Con B = {1, 0}

1) 0, , , . , (B, B

1 y 0 representan las abstracciones activado y

desactivado, equivalentes a verdadero y falso, respectivamente

Álgebra de BooleEjemplos

ORAND

NOT

Una sucesión de variables (x1, x2, …, xn), constantes (1, 0) y operadores (+, .) conforman una Expresión

Booleana

Álgebra de BooleExpresiones Booleanas

Dos constantes

0 y 1

Tres variablesx1, x2 y x3

(x1 + x2) + (x3 . 0) + 1(x1 + x2) + (x3 . 0) + 1

Operadores+, .

Álgebra de BooleExpresiones Booleanas

Definición Formal:

Una Expresión de Boole o Polinomio de Boole en las variables {x1,x2,...,xn} se define de forma recursiva como:

1. x1, x2, ..., xn son expresiones booleanas2. 0, 1 son expresiones booleanas3. Si E1(x1,x2,...,xn), E2(x1,x2,...,xn) son expresiones booleanas, entonces:

E1 + E2E1 . E2

4. No existen expresiones de Boole que no puedan obtenerse por ññ 1, 2, o 3.

También son expresiones booleanas

Toda Expresión Booleana define una Función Booleana que hace corresponder a cada n-tupla de

Bn un valor de B

Álgebra de BooleFunciones Booleanas

Una función booleana de n variables es una aplicación f: Βn → Β tal que

1 f(x1, x2, ..., xn) = (x1, x2, ..., xn) Βn

0

Álgebra de BooleFunciones Booleanas

32414x,3x,2x,1x x.1)(x.xxE

1

110

0(1.1)1.0

x.1)(x.xxE 32414x,3x,2x,1x

Ejemplo:

Si asignamos valores a las variables (x1,x2,x3,x4) =

(1,1,0,0)

Representación de Expresiones Booleanas

Una función booleana de n variables puede representarse en una tabla de la forma:

Representación de Expresiones Booleanas

Ejemplo 1: Representar 3221321 x.xx.x)x,x,f(x

x1 x2 x3 f(x1,x2,x3)

0 0 0 0

0 0 1 0

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 01

10

1.10.0

01.10.f(0,1,0)

Representación de Expresiones Booleanas

x1 x2 x3 f(x1,x2,x3)

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

Cómo se puede obtener la expresión booleana de

f(x1,x2,x3)

Ejemplo 2: Dada la siguiente tabla de verdad obtener la expresión booleana asociada

Representación de Expresiones Booleanas

Ejemplo 2: Dada la siguiente tabla de verdad obtener la expresión booleana asociada, por suma de productos completa

x1 x2 x3 f(x1,x2,x3)

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

321 x..xx

321 x.x.x

321 .x.xx

321 .x.xx Productos Fundamental

es

Representación de Expresiones Booleanas

Ejemplo 2: Dada la siguiente tabla de verdad obtener la expresión booleana asociada, por producto de sumas completa

x1 x2 x3 f(x1,x2,x3)

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

321 xxx

321 xxx

321 xxx 321 xxx

Sumas Fundamental

es

Representación de Expresiones Booleanas

Ejemplo 2: Dada la siguiente tabla de verdad obtener la expresión booleana asociada x1 x2 x3 f(x1,x2,x3)

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

)xxx)(xxx)(xxx)(xx(x

xxxxxxxxxxxx

)x,x,f(x

321321321321

321321321321

321

Producto de Sumas Completa

Suma de Productos Completa

Formas CanónicasMintérminos - Maxtérminos

Dec x1 x2 x3 f(x1,x2,x3)Mintérmino

sMaxtérminos

0 0 0 0 1 m0 M0

1 0 0 1 0 m1 M1

2 0 1 0 1 m2 M2

3 0 1 1 1 m3 M3

4 1 0 0 0 m4 M4

5 1 0 1 0 m5 M5

6 1 1 0 0 m6 M6

7 1 1 1 1 m7 M7

321 xxx 321 x.x.x

321 xxx 321 .xx.x

321 x..xx

321 .x.xx

321 x.x.x

321 .xx.x

321 x..xx

321 .x.xx

321 xxx

321 xxx 321 xxx

321 xxx

321 xxx

321 xxx

Se observa queii Mm

Formas CanónicasMintérminos

321 x.x.xDec x1 x2 x3 f(x1,x2,x3)

Mintérminos

0 0 0 0 1 m0

1 0 0 1 0 m1

2 0 1 0 1 m2

3 0 1 1 1 m3

4 1 0 0 0 m4

5 1 0 1 0 m5

6 1 1 0 0 m6

7 1 1 1 1 m7

321 .xx.x

321 x..xx

321 .x.xx

321 x.x.x

321 .xx.x

321 x..xx

321 .x.xx

m321 (0,2,3,7) )x,x,f(x

321 x.x.x

Formas CanónicasMaxtérminos

Dec x1 x2 x3 f(x1,x2,x3) Maxtérminos

0 0 0 0 1 M0

1 0 0 1 0 M1

2 0 1 0 1 M2

3 0 1 1 1 M3

4 1 0 0 0 M4

5 1 0 1 0 M5

6 1 1 0 0 M6

7 1 1 1 1 M7

M321 (1,4,5,6) )x,x,f(x

321 xxx

321 xxx

321 xxx

321 xxx

321 xxx

321 xxx

321 xxx

321 xxx

ConversiónMintérminos - Maxtérminos

Procedimiento:

i. Intercambiar los símbolos y

ii. Listar los índices que faltan en la expresión booleana original

Ejemplo:

m321 (0,2,3,7) )x,x,f(x

M321 (1,4,5,6) )x,x,f(x

ConversiónMintérminos - Maxtérminos¿Qué sucede si complementamos?

m321 (0,2,3,7) )x,x,f(x

Dec x1 x2 x3 f(x1,x2,x3) f(x1,x2,x3) Min Max

0 0 0 0 1 0 m0 M0

1 0 0 1 0 1 m1 M1

2 0 1 0 1 0 m2 M2

3 0 1 1 1 0 m3 M3

4 1 0 0 0 1 m4 M4

5 1 0 1 0 1 m5 M5

6 1 1 0 0 1 m6 M6

7 1 1 1 1 0 m7 M7

ConversiónMintérminos - Maxtérminos¿Qué sucede si complementamos?

M

MMMM

mmmm

mmmm

)7,3,2,0(

...

...

(0,2,3,7) )x,x,f(x

7320

7320

7320

m321

Simplificación de Expresiones Booleanas

Mapas de Karnaugh: Método utilizado para simplificar funciones booleanas y así poder construir un circuito lógico más sencillo y más económico

Circuito Lógico: Es un dispositivo físico que maneja la información en forma de 1’s y 0’s, niveles alto y bajo, respectivamente. Su diseño sigue las leyes de la lógica proposicional. Se construye en base a elementos digitales llamados compuertas lógicas

Circuitos LógicosCompuertas

Compuerta AND: Compuerta OR:

Compuerta NOT:

Simplificación de Expresiones Booleanas

Mapa de dos variables:

yx 0 1

0 m0 m1

1 m2 m3

Mapa de tres variables:

yzx 00 01 11 10

0 m0 m1 m3 m2

1 m4 m5 m7 m6

¿Cómo construir un Mapa de Karnaugh?

Simplificación de Expresiones Booleanas

Mapa de cuatro variables:

zwxy 00 01 11 10

00 m0 m1 m3 m2

01 m4 m5 m7 m6

11 m12 m13 m15 m14

10 m8 m9 m11 m10

El orden de las combinaciones hace que los cuadros vecinos sean

adyacentesm0 es vecino de m1 son

adyacentes

m12 no es vecino de m15 no son adyacentes

Simplificación de Expresiones Booleanas

¿Cómo hacer la simplificación?

Paso 1: Seleccionar cuadros adyacentes de valor igual a 1.

El número de cuadros seleccionados debe ser potencia de 2. zw

xy 00 01 11 10

00 1 1

01 1 1 1

11 1

10 1 1 1

Son Adyacent

es

No son Adyacent

esSon

Adyacentes pero no son potencia de

2

Simplificación de Expresiones Booleanas

¿Cómo hacer la simplificación?

Paso 2: Generar el término asociado a cada grupo. Sólo aparecen las variables que no cambian su valor al pasar de un cuado al otro

zwxy 00 01 11 10

00 1 1

01 1 1 1

11 1

10 1 1 1

zxywx

zywxyz

wyx

Simplificación de Expresiones Booleanas

¿Cómo hacer la simplificación?

zwxy 00 01 11 10

00 1 1

01 1 1 1

11 1

10 1 1 1

ywx

zy

x

y

w

z

Simplificación de Expresiones Booleanas

¿Cómo hacer la simplificación?

Paso 3: Sumar todos los términos obtenidos en el Paso 2

wyxwxyzywxzyzx w)z,y,f(x,

zwxy 00 01 11 10

00 1 1

01 1 1 1

11 1

10 1 1 1

zxywx

zy

wxyz

wyx

SimplificaciónCircuitos Lógicos

Paso 4: Diseñar el circuito lógico asociado a la función booleana simplificada obtenida en el Paso 3

wyxwxyzywxzyzx

w)z,y,f(x,

• Programa para la captura de sistemas digitales

• Programa para la simplificación de Mapas de Karnaugh de 4 variables

• Otros: LogicAid, CircuitMaker, DesignWorks Professional con Simulador

Álgebra de Boole Circuitos Lógicos - Software

¡Gracias por su

atención!

¿Preguntas?

Para quienes no ansían sino ver,

hay luz bastante; más para quienes

tienen opuesta disposición, siempre hay

bastante oscuridad

Pascal

Álgebra de BooleReseña Histórica

• En 1854, desarrollo del Álgebra Booleana por el filósofo y matemático inglés George Boole

• En 1869, primera máquina que utilizaba el Álgebra Booleana. William Stanley Jevons.

Álgebra Boolena

Símbolos Algebraicos

Lógica= +

Sistema de Numeración Binario

Computadoras Electrónicas

Comienza así el álgebra de la lógica: Algebra Booleana Como método para resolver problemas lógicos usando

solamente los valores binarios 1 y 0, y tres operadores: AND (y), OR (o) y NOT (no)

Álgebra de BooleReseña Histórica

• El primer interés de George fueron los idiomas. A la edad de 12 años llegó a ser tan hábil en Latín que provocaba controversia

• Publico obras relacionadas con ecuaciones diferenciales, diferencias finitas y métodos generales en probabilidad

• No estudió para un grado académico, a la edad de 16 años fue profesor auxiliar de colegio. Sus primeras instrucciones en matemática fueron de su padre. Desde 1835, comenzó a estudiar matemáticas por si mismo, era un gran autodidacta

Álgebra de BooleDefinición

En definitiva,

Es un Estructura Algebraica (EA), que cumple ciertos postulados o condiciones especiales

)k,k-, ,º(K,*,K 21

es una EA, donde: K: Portador del Álgebra, K

fi: Operaciones l.c.i. definidas en K, i = 1,2,…,n

ki: Elementos Neutros, i = 1,2,…,n

)k,k,...,f,f(K,K 2,...121

Ejemplo 2: Sea P el conjunto de todas las proposiciones lógicas entonces,

es un Álgebra de Boole.

Se cumplen las seis (6) condiciones:, : Son l.c.i. en P(S)f, v: Son elementos neutros de , respectivamente, : Son conmutativos y asociativos, : Son distributivos uno respecto del otroCada p P admite un p, tal que p p v y p p f

v)f,,,,(P, P

Álgebra de BooleEjemplos

• Variable: Son símbolos que pueden tomar cualquier valor del conjunto B = {0,1}. Se representan con letras minúsculas

• Constante: Un elemento del conjunto B en la expresión. Las constantes pueden ser 0 ó 1.

• Literal: Ocurrencia de una variable o su complemento en una expresión.

Álgebra de BooleFunciones Booleanas

Una función booleana de n variables puede representarse en una tabla de la forma:

¿Cómo construir esta tabla?

• Una columna para cada variable

• Una columna para el resultado de la evaluación

• Generar todas las combinaciones de valores 0 y 1 para las variables

Representación de Expresiones Booleanas

Representación de Expresiones Booleanas

Todo función booleana puede determinarse a través de una expresión booleana llamada forma normal

Toda tabla de verdad contiene:Una f.n.d. completa Valuación final contiene al menos

un vUna f.n.c. completa Valuación final contiene al menos

un f

Es posible reproducir una expresión booleana utilizando suma de productos completa o el producto de sumas

completa

Formas CanónicasMintérminos - Maxtérminos

Maxtérmino: Factor normal formado por la suma de tantos literales como variables tenga la expresión booleana

Ejemplos: , ,321 xxx 321 xxx 321 xxx

321 x..xx 321 .x.xx321 .x.xx

Mintérmino: Factor normal formado por el producto de tantos literales como variables tenga la expresión booleana

Ejemplos: , ,

Circuitos LógicosCompuertas

Compuerta AND:

Con dos o más entradas, esta compuerta realiza la función booleana de la de la multiplicación (.). Su salida será un 1 cuando todas sus entradas estén en nivel alto. En cualquier otro caso, la salida será un 0.

Circuitos LógicosCompuertas

Compuerta OR:

Con dos o más entradas, esta compuerta realiza la función de la suma (+). Su salida será 1 cuando al menos una de sus entradas esté en estado alto. En cualquier otro caso, la salida será 0.

Circuitos LógicosCompuertas

Compuerta NOT:

Recibe una única entrada y presenta en su salida el valor opuesto del que recibe como entrada. En efecto, realiza la función booleana de la complementación.

Otras Compuertas: Resultan de la combinación de las compuertas AND, OR y NOT

NAND NOR

Circuitos LógicosCompuertas

Simplificación de Expresiones Booleanas

zyx zxy

zy z1.y z)yx(xzxyzyx

Dos términos son adyacentes si tienen las mismas variables con el mismo estado de complemento, a excepción de una de ellas.

Ejemplo: y son adyacentes

Los términos adyacentes se pueden simplificar fácilmente,

Simplificación de Expresiones Booleanas

zwxy 00 01 11 10

00 m0 m1 m3 m2

01 m4 m5 m7 m6

11 m12 m13 m15 m14

10 m8 m9 m11 m10

En el Mapa de Karnaugh también se presenta adyacencia entre la primera y última fila; así como

entre la primera y última columna

Son Adyacentes

Simplificación de Expresiones Booleanas

En el Mapa de Karnaugh también se presenta adyacencia entre la primera y última fila; así como

entre la primera y última columna

zwxy 00 01 11 10

00 m0 m1 m3 m2

01 m4 m5 m7 m6

11 m12 m13 m15 m14

10 m8 m9 m11 m10

Son Adyacentes

Simplificación de Expresiones Booleanas

zwxy 00 01 11 10

00 1 1

01 1 1 1

11 1

10 1 1 1

Son Adyacent

es

No son Adyacent

esSon

Adyacentes pero no son potencia de

2

Dos cuadros son adyacentes sólo si varia el valor de

una única variable al pasar de un cuadro al otro