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

http://creative.gettyimages.com/source/Search/30','30','64','

Á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


)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)


)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:


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:


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 +


Modelo de Conmutación:

Con B = {1, 0}

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

Operaciones Binarias, equivalentes a

, respectivamente

Operación Unaria, equivalente a


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


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


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:


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)


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


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


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


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:


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?


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


¿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



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



zwxy 00 01 11 10

00 1 1

01 1 1 1

11 1

10 1 1 1

ywx

zy

x

y

w

z



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


• 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)


• 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


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


• 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.


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



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: , ,


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.


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.


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



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,


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


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


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

algebra de boole patricia guerrero

Documents