Download - Algebra Booleana

Transcript
Page 1: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 1/40Matemáticas Discretas1

Álgebra de Boole

El álgebra booleana es la teoría matemática que se aplica en la lógicacombinatoria. Las variables booleanas son símbolos utilizados para

representar magnitudes lógicas y pueden tener sólo 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 eléctricos y ópticos pueden serestudiados usando este conjunto y las reglas del álgebra booleana. Las 3operaciones booleanas mas usadas son:

Complemento (denotado con una barra superior) es definido como:

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=0

01 10 == y

ALGEBRA BOOLEANA

Page 2: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 2/40Matemáticas Discretas2

Las reglas de precedencia son: complemento, AND y OR.

Es claro que el complemento y la suma y producto boléanos correspondena los operadores lógicos ¬, ∨ y ∧ respectivamente donde 0 corresponde a

falso (F) y 1 corresponde a verdadero (V).

Ej: EvaluarSol: Utilizando las definiciones de complemento, la suma booleana y el

producto booleano se tiene que:

)10(0.1 ++

00 

10)10(0.1

=+=+=++

ALGEBRA BOOLEANA

Page 3: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 3/40

Matemáticas Discretas3

Expresiones booleanas y Funciones Booleanas

Sea B={0,1}. Entonces Bn={(x1, x2,...xn)⏐ xi∈B para 1≤ i ≤ n} es el conjuntode todas las tuplas posibles de 0’s y 1’s. La variable x es llamada una

variable booleana si ella asume valores solo de B (0 y 1). Una función deBn en B es llamada una función booleana de grado n.

Ej: La función F(x,y)= es una función de grado 2 con los siguientes valores

La función es una función de grado 2, con F(0,0)=0, F(1,0)=1,F(0,1)=0 y F(1,1)=0

x y F(x,y)1 1 0

1 0 1

0 1 0

0 0 0

 y x y xF  =),(

ALGEBRA BOOLEANA

Page 4: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 4/40

Matemáticas Discretas4

Ej: Calcular los valores de la función booleana F(x,y,z)=xy+z1=(Z+Z’)

x y z xy z F(x,y,z)=xy+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

ALGEBRA BOOLEANA

xyz

Xyz´

XY’Z’

X’YZ’

X’Y’Z’

XY+ZY+Z’=XYZ+XYZYZ+XYZ´+XYXY’Z’+XX’Y’Z’

Page 5: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 5/40

Matemáticas Discretas5

Una función booleana de grado dos es una función de un conjunto decuatro elementos, a saber, todos los pares de elementos de B={0,1}, en B,un conjunto con dos elementos. Por tanto hay 16 funciones booleanasdiferentes de grado 2.

La cantidad de funciones booleanas de grado n son:

Por ejemplo:

x y F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16

1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0

1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0

0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0

0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

n22

 y x xyF  +=6

ALGEBRA BOOLEANA

Page 6: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 6/40

Matemáticas Discretas6

Propiedades de un Álgebra de BooleIdentidades booleanas 

Identidad Nombre

__

 x x =  

Doble complemento

x + x = x

x . x = x

Idempotencia

x + 0 = x

x . 1 = x

Identidad

x + 1 = 1

x . 0 = 0

Dominación

x + y = y + x

x . y = y . x

Conmutativa

x + (y + z) = (y + x) + z

x . (y . z) = (y . x) . z

Asociativa

x + (y . z) = (x + y) . (x + z)

x . (y + z) = (x . y) + (x . z)

Distributiva

 y x y x +=.  

 y x y x .=+  

De morgan’s

x + x.y = x

x . (x + y) = x

Absorción

1=+ x x   Propiedad unidad

Propiedad cero0. = x x

ALGEBRA BOOLEANA

Page 7: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 7/40

Matemáticas Discretas7

Ej: Demostrar que se cumple la propiedad distributiva x(y+z)=xy+xz

Ej: Probar la ley de absorción 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 (dominación producto booleano)= x (identidad suma booleana).

x y z y+z xy xz x(y+z) xy+xz

1 1 1 1 1 1 1 1

1 1 0 1 1 0 1 1

1 0 1 1 0 1 1 11 0 0 0 0 0 0 0

0 1 1 1 0 0 0 0

0 1 0 1 0 0 0 0

0 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0

ALGEBRA BOOLEANA

Page 8: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 8/40

Matemáticas Discretas8

Ej: Simplificar F=

BAF

)C(CBAF

 CBACBAF

=

+=+=

ABBAF

BBABBAAAF

)BB)·(AA(F

+=+++=

++=

DBCAF

)DB()CA(F

)]DC)·(BA[(F

+=

+++=

++=

)ZY)(XW(VZ)WYZ)(Z(XF +++++=

ALGEBRA BOOLEANA

Page 9: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 9/40

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. Página: 653.

Page 10: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 10/40

Matemáticas Discretas9

DualidadEs una expresión booleana que se obtiene intercambiando entre sí lasuma 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 función booleana F representado por una expresiónbooleana es la función representeada por el dual de dicha expresión. Sedenota por Fd. Una igualdad entre funciones booleanas sigue siendo válidacuando se toman duales a ambos lados de la igualdad (Principio de ladualidad), el cual es muy útil para la obtención de nuevas propiedades

ALGEBRA BOOLEANA

Page 11: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 11/40

Matemáticas Discretas10

Representación de Funciones Booleanas

A partir de los valores de una función booleana, se va a obtener unaexpresión booleana que represente a dicha función (Suma de Productos),

utilizando los tres operadores booleanos (+ . )

Determinar el mínimo conjunto de operadores para representar dichasfunciones.

Desarrollo en suma de productos

Toda función booleana se puede representar mediante una suma booleanade productos booleanos de variables y variables complementadas.

ALGEBRA BOOLEANA

Page 12: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 12/40

Matemáticas Discretas11

Ej: Para cada una de las funciones F(x,y,z) y G(x,y,z), calcular unaexpresión booleana que la represente.

Sol: Para representar a F se necesita una expresión que valga 1 cuandox=1,y=0 y z=1. Esa expresión sería:

Para representar a G, se necesita una expresión que valga 1 cuandox=1,y=1,z=0 o cuando x=0,y=1, y z=0. La expresión quedaría:

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

 z y x

 z y x z xy +

ALGEBRA BOOLEANA

Page 13: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 13/40

Matemáticas Discretas12

Miniterm

Un literal es una variable booleana o su complemento. Un minterm de lasvariables 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 unliteral por cada variable.

Un minitérmino vale 1 para una y sólo una combinación de sus variables

Los minterms en una suma booleana corresponde a las combinacionespara las cuales la función tiene el valor 1. La suma de minterms querepresenta esta función es llamada la expansión en suma de productos ola forma normal disyuntiva de la función booleana.

Del ejemplo anterior:  z y x z xyG +=

ALGEBRA BOOLEANA

Page 14: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 14/40

Matemáticas Discretas13

Ej: Hallar la FND de la función F(x,y,z) = (x+y)Z

Sol: Existen dos maneras. La primera desarrollar y simplicar el productoutilizando las propiedades del algebra booleanaF(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 valoresposibles de las variables x,y,z.

F(x,y,z)= (x+y)Z

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

x y z x+y Z (x+y)Z

1 1 1 1 0 0

1 1 0 1 1 11 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

ALGEBRA BOOLEANA

Page 15: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 15/40

Matemáticas Discretas14

Completitud Funcional

Es claro que cada función booleana puede ser expresada como una sumade minterminos, es decir puede ser representada usando los operadores

del conjunto {+ , . , } por lo cual podemos decir que este esfuncionalmente completo.

Es claro también que podemos eliminar todas las sumas booleanasaplicando las leyes de morgan, pues, x+y= X Y es decir las funcionespueden ser representadas usando los operadores del conjunto {+ , . , }por lo cual podemos decir que este conjunto también funcionalmentecompleto.

Igualmente podemos eliminar todas los productos booleanos aplicandolas leyes de morgan, pues xy= X+Y , es decir las funciones pueden serrepresentadas usando los operadores del conjunto {+, } por lo cualpodemos decir que este conjunto también es funcionalmente completo.

ALGEBRA BOOLEANA

Page 16: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 16/40

Matemáticas Discretas15

Si se definen los operadores NAND (⏐) y NOR (↓) cuyas tablas las cualesson definidos como:

Ambos operadores son funcionalmente completos.

ALGEBRA BOOLEANA

Operador Definición

1⏐1 = 0

1⏐0 = 10⏐1 = 1

0⏐0 = 1

1↓1 = 0

1↓0 = 00↓1 = 0

0↓0 = 1

NAND

NOR

 Y)(YX)(XYX

 Y)(XY)(XXY

XXX

|||=+|||=

|=

Y) X(Y) (XYX

Y) Y(X) (XXY

XXX

↓↓↓=+

↓↓↓=

↓=

Page 17: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 17/40

Matemáticas Discretas16

ALGEBRA BOOLEANA

Operador Definición

1⏐1 = 0

1⏐0 = 1

0⏐1 = 1

0⏐0 = 1

1↓1 = 0

1↓0 = 0

0↓1 = 0

0↓0 = 1

NAND

NOR

 Y)(YX)(XYX

 Y)(XY)(XXY

XXX

|||=+|||=

|=

Y) X(Y) (XYX

Y) Y(X) (XXY

XXX

↓↓↓=+

↓↓↓=

↓=

X Y X|X Y|Y X|Y XY X+Y

(X|Y)|(X|Y) (X|X)|(Y|Y)

1 1 0 0 0 1 1

1 0 0 1 1 0 1

0 1 1 0 1 0 1

0 0 1 1 1 0 0

X Y X↓X Y↓ Y X↓  Y XY X+Y

(X↓X)↓(Y↓ Y)(X↓ Y)↓(X↓ Y)

1 1 0 0 0 1 1

1 0 0 1 0 0 1

0 1 1 0 0 0 1

0 0 1 1 1 0 0

Page 18: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 18/40

Matemáticas Discretas17

Puertas Lógicas

El áIgebra de Boole se utiliza para modelar los circuitos de dispositivoselectrónicos. Cada entrada y salida de estos dispositivos se puede ver

como un elemento del conjunto (O, I ). Un computador, u otro dispositivoeléctrico, se compone de un cierto número de circuitos. Cada circuito sepuede diseñar utilizando las reglas del áIgebra de Boole estudiadas.

Los elementos básicos de los circuitos se llaman puertas Iógicas. Cadatipo de puerta implemen-ta una operación booleana

Circuitos Combinacionales

Producen una salida que depende solamente de la entrada y no del estadoactual del circuito. (No tienen memoria).

Se van a utilizar la puertas lógicas y la reglas del algebra de boole para

diseñar circuitos.

ALGEBRA BOOLEANA

Page 19: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 19/40

Matemáticas Discretas18

Puerta Not - Inversor

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

Puerta OR

Las entradas de esta puerta son los valores de dos o más variablesbooleanas. La salida es la suma booleana de estos valores.

Puerta AND

Las entradas de esta puerta son los valores de dos o más variablesbooleanas. La salida es el producto booleano de estos valores

ALGEBRA BOOLEANA

Page 20: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 20/40

Matemáticas Discretas19

Combinaciones de Puertas

Los circuitos combinacionales se pueden construir utilizando unacombinación de los tres tipos puertas NOT, OR y AND.

Al construir combinaciones de circuitos puede ocurrir que varias puertastengan entradas comunes. Esto da lugar a dos formas de representacióngráfica de los circuitos.

•Indicar separadamente las entradas para cada puerta

ALGEBRA BOOLEANA

Page 21: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 21/40

Matemáticas Discretas20

•Utilizar ramificaciones para indicar todas las puertas que compartenuna misma entrada.

La salida de una puerta se puede emplear como entrada de una o máspuertas

ALGEBRA BOOLEANA

Page 22: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 22/40

Matemáticas Discretas21

Ejemplos

ALGEBRA BOOLEANA

 y y x ).( +

)( y x

)()( x z xy ++

Page 23: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 23/40

Matemáticas Discretas22

Ejemplos:

ALGEBRA BOOLEANA

 x y x )( +

))(( z y x z y x ++

)(

 z

 y x +

Page 24: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 24/40

Matemáticas Discretas23

Ejemplo de CircuitosUn comité formado por tres personas toma las decisiones en unaorganización. Para ello, cada individuo vota sí o no a cada propuestafomulada. Una propuesta prospera si recibe al menos dos de los tres

votos. Diseña un circuito que determine cuándo prospera una propuesta.

Solución: Representamos con la variable x el voto del primer individuo: x= 1 indica que vota sí y x=0 el caso contrario. Con y=1 que el segundoindividuo vota si y con y = O que vota no; por úItimo, denotaremos con z

= 1 que el tercer individuo vota sí y con z = O que vota no. En esascondiciones, debemos diseñar un circuito que produzca un 1 a partir delas variables x, y y z cuando dos o más de estas variables valgan 1.

Una representación de la función booleana que produce esta salidaes xy + xz + yz

ALGEBRA BOOLEANA

Page 25: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 25/40

Matemáticas Discretas24

Ejemplo de CircuitosAlgunas veces las instalaciones eléctricas se controlan mediante más deun interruptor. Los circuitos tienen que ser diseñados de modo que alaccionar cualquier interruptor de la instalación la luz se encienda si está

apagada y se apague si está encendida. Diseñar un circuito que modeleesta situación para el caso de dos interruptores.

Solución: Definimos x = 1 si el primer interruptor está cerrado y x = O siestá abierto, y definimos y = 1 si el segundo interruptor está cerrado e y

= O si está abierto. Sea F(x, y) = 1 si la luz está encendida y F(x, y) = O siestá apagada. Podemos decidir arbitrariamente que la luz está encendidasi ambos interuptores están cerrados, esto es, F(1, 1) = 1.

Esto determina los restantes valores de F. Cuando uno de losinterruptores se abre, la luz se apaga, luego F(1,0)=F(0,1)=0. Si ambosestán abiertos, la luz se enciende. Por tanto F(0,0)=1.

ALGEBRA BOOLEANA

A GEBRA BOO EANA

Page 26: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 26/40

Matemáticas Discretas25

La tabla muestra los valores de la función, tomando como entrada losestados de los interruptores.

Se observa que

Y el circuito quedaría

ALGEBRA BOOLEANA

x y F(x,y)

1 1 1

1 0 0

0 1 00 0 1

 y x xy y xF  +=),(

ALGEBRA BOOLEANA

Page 27: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 27/40

Matemáticas Discretas26

Otras Puertas: NAND, NOR, EXOR.

La mayoría de circuitos electrónicos se implementan utilizandocompuertas NAND, y NOR.

Para ello se tiene en cuenta la representación de las operaciones básicas(negación, suma y producto) booleanas, utilizando sólo un tipo decompuerta (Diapositiva 16), y las leyes de morgan.

Investigar.

ALGEBRA BOOLEANA

ALGEBRA BOOLEANA

Page 28: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 28/40

Matemáticas Discretas27

Minimización de circuitos

La eficiencia de un circuito combinacional depende del número de puertasque tenga y de la disposición de éstas. El proceso de diseñar un circuito

combinacional comienza con la tabla que especifica las salidas para cadacombinación de valores de entrada. Para obtener un conjunto de puertasIógicas que implemente este circuito siempre podemos usar la formanormal disyuntiva del circuito. Sin embargo, la forma normal disyuntivapuede tener muchos más sumandos de los necesarios. Se pueden

combinar entre sí dos sumandos de una forma normal disyuntiva quedifieren en una sola variable de manera que en un sumando aparezcadicha variable y en el otro sumando lo haga su complementario.

Por ejemplo, consideremos el circuito que tiene salida 1 si, y sólo si, bienx = y = z = 1 o bien x = z = 1 e y = O. La forma normal disyuntiva deeste circuito es

ALGEBRA BOOLEANA

 z y x xyz +

ALGEBRA BOOLEANA

Page 29: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 29/40

Matemáticas Discretas28

Los dos sumandos de este desarrollo difieren en exactamente unavariable, a saber, y. Estos sumandos se pueden combinar del modosiguiente:

Por tanto, xz es una expresión booleana con menos operadores que

representa igualmente al circuito

ALGEBRA BOOLEANA

 xz xz

 xz y y z y x xyz

==

+=+

 ).(1 

))((

ALGEBRA BOOLEANA

Page 30: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 30/40

Matemáticas Discretas29

Diagramas de Karnaugh ó K-DiagramaPara reducir el número de términos de una expresión booleana querepresenta a un circuito hace falta encontrar términos que se puedancombinar entre si. La idea es buscar que las funciones booleanas

dependan de relativamente pocas variables.

En la forma normal disyuntiva de una función de dos variables x, y haycuatro posibles minitérminos. Un K-diagrama para una función booleanade dos variables consta de cuatro celdas. Se coloca un 1 en la celda que

representa a un minitérmino si este minitérmino aparece en el desarrollode la función.

Se dice que dos celdas son adyacentes si los minitérminos querepresentan difieren en exactamente un literal. Por ejemplo, la celda querepresenta a es adyacente a las celdas que representan a y a

ALGEBRA BOOLEANA

 xy y x y x

ALGEBRA BOOLEANA

Page 31: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 31/40

Matemáticas Discretas30

Ejemplo:

Calcular los siguientes K Diagramas.

Solución: Se coloca un 1 en una celda si el minitérmino representado poresa celda es un sumando de la FND.

ALGEBRA BOOLEANA

 y x xy +

 y x y x y x ++

 y x y x +

Siempre que haya unos en dos celdas adyacentes del

K-diagrama, los minitérminos representados por estasceldas se pueden combinar entre sí dando lugar a untérmino que depende sólo de una de las vanables.

Están adyacentes y pueden combinarse

para producir , ya que

 y x y x y

 y y y x x y x y x =+=+ )(

ALGEBRA BOOLEANA

Page 32: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 32/40

Matemáticas Discretas31

Solución: Simplificando la FND, utilizando agrupamiento (2 variables)

ALGEBRA BOOLEANA

 y x xy +

 y x y x y x ++

 y x y x +

 y

 y x y x +

 y x +

ALGEBRA BOOLEANA

Page 33: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 33/40

Matemáticas Discretas32

K-Diagrama de 3 Variables

Un K-diagrama de tres variables es un rectángulo dividido en ocho celdas.

• Dos celdas son adyacentes si los minitérminos que representan difierenexactamente en un literal

• Este diagrama puede verse como un cilindro, donde dos celdas tienen un ladocomún si, y solo si, son adyacentes

• Los bloques 2x2 y 1x4 se pueden representar con una variable• El bloque de 4x2 representa un término sin literales, es decir la funcion 1.• Los bloques de dos celdas adyacentes representan parejas de minitérminos que

se pueden combinar dando lugar a un producto de dos literales.

ALGEBRA BOOLEANA

ALGEBRA BOOLEANA

Page 34: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 34/40

Matemáticas Discretas33

ALGEBRA BOOLEANA

ALGEBRA BOOLEANA

Page 35: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 35/40

Matemáticas Discretas34

ALGEBRA BOOLEANA

 yz x z y z x ++ z x y +

 z y x ++  y x z y z x ++

 z y x yz x z y x z xy +++ z y x yz x z y x z y x z y x ++++

 z y x z y x yz x z y x z y x z xy xyz ++++++ z y x z y x z y x z xy +++

ALGEBRA BOOLEANA

Page 36: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 36/40

Matemáticas Discretas35

ALGEBRA BOOLEANA

 z y xw y xw y xw zwxwyz ++++

 z y z x y xw ++

 xw z y xw ++

ALGEBRA BOOLEANA

Page 37: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 37/40

Matemáticas Discretas36

Método de Quine-McCluskey

Método alternativo al de Karnaugh, el cual tiene dos inconvenientes:•Se vuelve dificil de utilizar cuando son más de 4 variables•Es un método que usa la inspección visual para su ejecución

La idea es utilizar un método para simplificar desarrollos en sumas deproductos que puede automatizarse, y que pueda utilizarse par acualquiernúmero de variables

Consta de 2 partes

•La primera determina que términos son candidatos a ser incluídos en un

desarrollo mínimo como una suma booleana de productos booleanos

•La segunda determina cuales de esos términos se utilizan finalmente

ALGEBRA BOOLEANA

ALGEBRA BOOLEANA

Page 38: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 38/40

Matemáticas Discretas37

Metodologia:1) Expresar cada minitérmino en formato binario.

2) Agrupar las cadenas según el número de unos que tengan.

3) Combinar todas las cadenas que difieran en uno de los literales,cambiando el literal que difiere por un -, y dejando el resto de la cadenaigual, y agregar la nueva cadena a un segundo grupo, sobre el cual seharán futuras combinaciones. Iterar hasta que no se consigan nuevascombinaciones, en ambos grupos

4) Conformar un conjunto minimal de productos (candidatos), conaquellos que no se utilizaron para conformar nuevos productos conmenos literales, y con aquellos que resultaron de la combinación de

términos originales

5) Conformar el grupo que represente la función booleana, tomandoprimero los términos candidatos escenciales (aquellos que son los únicosque recubren un minitérmino), y luego rechazando los redundantes (es

decir aquellos cuya cobertura ya no aplica),

ALGEBRA BOOLEANA

ALGEBRA BOOLEANA

Page 39: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 39/40

Matemáticas Discretas38

Ejemplo: Obtener una expresión minimal equivalente a:

Solución:

Respuesta:

 z y x z y x yz x z y x xyz ++++

Paso 1 Paso 2

Minitérmino Cadena de

Bits

Número de

Bits

Término Cadena Término Cadena

1 x y z 111 3 (1,2) x z 1-1 (1,2,3,4) z --1

2 x Yz 101 2 (1,3) y z -11

3 Xy z 011 2 (2,4) Yz -01

4 XYz 001 1 (3,4) Xz 0-1

5 XZZ 000 0 (4,5) XY 00-

x y z x Yz Xy z XYz XYZ

z X X X X

XY X X

 y x z +

ALGEBRA BOOLEANA

Page 40: Algebra Booleana

5/10/2018 Algebra Booleana - slidepdf.com

http://slidepdf.com/reader/full/algebra-booleana-559e001ba0a35 40/40

Matemáticas Discretas39

Ejemplo: Obtener una expresión minimal equivalente a:

Solución:

Respuesta:  o   yz x zwy zw y xw zwy zw ++++

 z y xw yz xw z y xw xyzw z y xw yz xw zwxy ++++++

w x y Z w Xy z Wx y z w Xy Z Wx Yz WXy z WXYz

Wz X X X X

w y Z X X

w Xy X X

Xy z X X

Paso 1 Paso 2

Minitérmino Cadena de

Bits

Número de

Unos

Término Cadena Término Cadena

1 w x y Z 1110 3 (1,4) w y Z 1-10 (3,5,6,7) Wz 0--1

2 w Xy z 1011 3 (2,4) w Xy 101-

3 Wx y z 0111 3 (2,6) Xy z -011

4 w Xy Z 1010 2 (3,5) Wx z 01-1

5 Wx Yz 0101 2 (3,6) Wy z 0-116 WXy z 0011 2 (5,7) WYz 0-01

7 WXYz 0001 1 (6,7) WXz 00-1


Top Related