vicerrectorado acadÉmico  · web viewen conclusión toda toda función booleana esta implícita...

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

UNIDAD 6: INTRODUCCIÓN A LOS CIRCUITOS LÓGICOS

6.1 Elementos del Algebra de BooleEl álgebra de Boole consiste en una serie de leyes y propiedades que

permiten el análisis y el diseño de sistemas, circuitos, redes y dispositivos, cuyo funcionamiento se basa en las reglas de la Lógica y el Sistema Binario.

Los elementos fundamentales del Algebra de Boole son:a. Viables Lógicas o Boolenas: Son variables que solo pueden tomar

como valores el 0 y el 1. Se representan por letras ejemplo: W, X, Y, Z o A, B, C, Db. Valores Lógicos o Booleanos: Conformados por el 1 y el 0 Lógicos.c. Operadores: son los elementos que permiten modificar los valores de las

expresiones en función de las variables y de los valores lógicos. Los operadores fundamentales son:

Complemento: se basa en la regla lógica de la negación, se conoce como el operador lógico NOT. Se representa por:

__ ___

0 = 1 y 1 = 0 también se puede expresar: 0’ = 1 y 1’ = 0Suma Booleana: se basa en el operador lógico de disyunción, se conoce

como operador lógico OR. Se representa por:0 + 0 = 0 0 + 1 = 1 1 + 1 = 1

Producto Booleano: se basa en el operador lógico de conjunción, se conoce como operador lógico AND y se representa por:

0 . 0 = 0 0 . 1 = 0 1 . 1 = 1Suma Booleana Excluyente: se basa en el operador lógico de disyunción

excluyente, se conoce como el operador XOR. Se representa por:0 0 = 0 0 1 = 1 1 1 = 0

Suma Booleana Complementada: es la combinación del operador OR y el NOT, se conoce con el nombre de NOR. Se representa por: __________

X + Y o X|XProducto Booleano Complementado: es la combinación del operador

AND y el NOT, se conoce con el nombre de NAND. Se representa por: __________

X . Y o X↓X

Ejemplo: Calcular el valor de la siguiente expresión Booleana. ________

(1.0) + (0+1) = 0 + 0 = 0

6.2 Expresiones y Funciones BoolenasUna función transforma los elementos de un conjunto A en otro conjunto B.

Se denota por A → B o también por F(A) =B, donde “A” es el conjunto de partida o Dominio y “B” es el conjunto de llegada o Rango, donde están las imágenes de los elementos de A. Para cada elemento del Dominio corresponderá un elemento del Rango.

Modulo Instruccional Estructuras Discretas. Teoría y Práctica 1

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

Gráficamente la relación de transformación de elementos de una función se puede apreciar en el siguiente esquema:

Una función booleana es aquella cuyo dominio es formado por n-tuplas de elementos binarios (cadenas de bits), donde a cada elemento del conjunto de n-tuplas le corresponde una imagen en el conjunto de rangos formado por los elementos el conjunto del binario (0,1).

Ejemplo:

Una variable booleana es aquella que permite representar los valores que pueden tomar los elementos de las funciones, se representan por letras mayúsculas. A continuación se muestra la forma de expresar las funciones booleanas:F (X, Y) = Función booleana de 2 bits.F (X, Y, Z) = Función booleana de 3 bits.F (W, X, Y, Z) = Función booleana de 4 bits.

EjemploRepresentar en una tabla de verdad las siguientes funciones booleanas:

a) F (X, Y) = XY’b) F (X, Y, Z) = XY + Z’

Solución caso a:X Y F (X, Y) = XY’0 0 0 F (0,0) = 0.0’ = 0.1 = 00 1 0 F (0,1) = 0.1’ = 0.0 = 01 0 1 F (1,0) = 1.0’ = 1.1 = 11 1 0 F (1,1) = 1.1’ = 1.0 = 0

Modulo Instruccional Estructuras Discretas. Teoría y Práctica

Función A → BDominio Rango

f (a) 1f (b) 2f (c) 3

abc

123

A B

Función Bn → BDominio Rangof (0,1) 0f (0,0) 0f (1,1) 1

(0,1)(0,0)(1,1)

0

1

Bn B

2

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

Solución caso b:

X Y Z F (X, Y) = XY + Z’0 0 0 1 F (0,0,0) = 0.0 + 0’ = 10 0 1 0 F (0,0,1) = 0.0 + 1’ = 00 1 0 1 F (0,1,0) = 0.1 + 0’ = 10 1 1 0 F (0,1,1) = 0.1 + 1’ = 01 0 0 1 F (1,0,0) = 1.0 + 0’ = 11 0 1 0 F (1,0,1) = 1.0 + 1’ = 01 1 0 1 F (1,1,0) = 1.1 + 0’ = 11 1 1 1 F (1,1,1) = 1.1 + 1’ = 1

Una expresión booleana es la forma mas general de una función, esta formada por operadores, variables booleanas y adicionalmente valores (0,1).Ejemplo:

F1 = XY’+Z Función (Operadores y variables)E1 = XY’+1 Expresión (Operadores, variables y valores.

En conclusión toda toda función booleana esta implícita en una expresión booleana.

6.3 Propiedades del Algebra de Boole

Se utilizan para simplificar expresiones o para determinar equivalencias de expresiones booleanas. Las más comunes son:

Nombre Identidad IdentidadDoble complemento X’’ = X

Idempotencia X + X = X X . X = XElemento neutro X + 0 = X X . 1 = X

Acotación X + 1 = 1 X . 0 = 0Conmutativa X + Y = Y + X X . Y = Y . XAsociativa X + (Y + Z) = (X + Y) + Z X (Y Z) = (X Y) ZDistributiva X + YZ = (X + Y) (X + Z) X (Y + Z) = XY + XZDe Morgan (XY)’ = X’ + Y’ (X+Y)’ = X’.Y’Absorción X + XY = X X (X+Y) = X

Inverso X + X’= 1 XX’= 0

Ejemplo: Aplicando las propiedades del Algebra de Boole, demostrar que X(X+Y) = X

Modulo Instruccional Estructuras Discretas. Teoría y Práctica 3

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

Aplicando distributiva: XX + XY = XAplicando idempotencia: X + XY = XAplicando distributiva: X(1 + Y) = XAplicando acotación: X.1 = XAplicando elemento neutro: X = X

6.4 Representación de funciones booleanasLas funciones se pueden representar a través de suma de productos

llamados miniterminos. Los miniterminos se conforman por un producto de n literales, los literales son variables booleanas que pueden estar o no complementadas. La siguiente función esta conformada por la suma de tres miniterminos, los primeros dos miniterminos tienen 3 literales y el tercero tiene 2 literales:

F (X, Y, Z) = XYZ’ + XY’Z’ + X’Y

Para la representación de funciones booleanas se pueden presentar dos casos:

a) Dados los valores de una función en una tabla de verdad, obtener una expresión que la represente. En este caso a partir de la tabla se busca una expresión de miniterminos para cada combinación donde la función esta definida, es decir, donde vale 1. Si la variable vale 1 en la combinación esta queda tal cual en el minitermino, si la variable vale 0, esta debe ser complementada en le minitermino.

b) Dada la función a través de una expresión booleana, obtener una tabla de valores que la represente. Se sustituyen las combinaciones de valores de las variables y para cada caso se obtiene el resultado. Con estos valores se construye la tabla de verdad.

Ejemplo:Dada la siguiente tabla de valores para las funciones F (X, Y, Z) y G(X, Y), obtener unas expresiones en suma de productos que representen a cada función.

X Y Z F (X, Y, Z) G (X, Y, Z)0 0 0 0 00 0 1 0 00 1 0 0 10 1 1 0 01 0 0 0 01 0 1 1 01 1 0 0 11 1 1 0 0

Modulo Instruccional Estructuras Discretas. Teoría y Práctica 4

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

Solución:

La función F (X, Y, Z) será: F = XY’ZLa función G (X, Y, Z) será: G = X’YZ’ + XYZ’

Estas son las combinaciones para las cuales las funciones F y G están definidas (valen 1), para el resto de los casos las funciones no están definidas (valen 0)

EjemploHallar la expresión en suma de productos de la función F (X, Y, Z) = (X + Y)Z’Solución:Se construye la tabla de valores en base a la expresión dada

X Y Z X + Y (X + Y)Z’0 0 0 0 00 0 1 0 00 1 0 1 10 1 1 1 01 0 0 1 11 0 1 1 01 1 0 1 11 1 1 1 0

De la tabla la función en suma de productos será: F = X’YZ’ + XY’Z’ + XYZ’

6.5 Compuertas LógicasSon elementos básicos de circuitos, de naturaleza eléctrica o electrónica,

que permiten la implementación de las operaciones lógicas, basándose en las reglas del Algebra de Boole. Se aplican para el diseño de los circuitos lógicos y constituyen la base electrónica para el hardware de los computadores. Los tipos de compuertas fundamentales son: NOT (1 entrada), OR, AND y XOR (2 a “n” entradas). A través de combinaciones se obtienen la NAND, NOR y XNOR .

a. Compuerta NOT

Modulo Instruccional Estructuras Discretas. Teoría y Práctica

X X’0 11 0

X X’

5

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

b. Compuerta OR

c. Compuerta AND

d. Compuerta XOR

e. Compuerta NOREs una combinación de una compuerta OR con una NOT a la salida.

f. Compuerta NAND

Modulo Instruccional Estructuras Discretas. Teoría y Práctica

X Y X + Y0 0 00 1 11 0 11 1 1

X

Y X + Y

X Y X . Y0 0 00 1 01 0 01 1 1

X

Y X . Y

X Y X Y0 0 00 1 11 0 11 1 0

X

Y X Y

X Y (XY)’0 0 10 1 01 0 01 1 0

X

Y

(X + Y)’

6

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

g. Compuerta XNOR

6.6 Circuitos LógicosSon arreglos de combinaciones de compuertas lógicas diseñados para

realizar funciones específicas. Operan con niveles de voltaje alto (+5V) para representar el valor 1 y niveles de voltaje bajo (0V) para representar el valor 0.

Ejemplo:Construir un circuito lógico que produzca las siguientes salidas:a) XY + X’Yb) (X + Y) X’c) X’ (Y + Z’)’d) (X + Y + Z) (XYZ)’

Modulo Instruccional Estructuras Discretas. Teoría y Práctica

X Y (XY)’0 0 10 1 11 0 11 1 0

X

Y

(X . Y)’

X Y X Y0 0 10 1 01 0 01 1 1

X

Y (X Y)’

7

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

Ejemplo:Diseñar dos circuitos lógicos para modelar una instalación eléctrica de iluminación, de manera que al accionar cualquier interruptor, la luz se encienda si esta apagada y se apague si esta encendida. En el primer caso el sistema es de dos interruptores y en el segundo de 3 interruptores.

Solución al caso de los 2 interruptores:a) Se asignan los valores lógicos a las condiciones de los interruptores y las lámparas.F(X,Y) = 1 Luz encendida X=Y=1 Interruptor cerradoF(X,Y) = 0 Luz apagada X=Y=0 Interruptor abiertob) Se establece la tabla de valores según el enunciado.

X Y F0 0 10 1 01 0 01 1 1

Modulo Instruccional Estructuras Discretas. Teoría y Práctica 8

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

c) Se establece la expresión booleana en suma de productosF = XY + (XY)’

d) Se dibuja el circuito lógico respectivo para la expresión booleana

Solución al caso de los 3 interruptores:Tabla de valores y función booleana

F (X, Y, Z) = XYZ + XY’Z’ + X’YZ’ + X’Y’Z

El circuito de la expresión es:

Modulo Instruccional Estructuras Discretas. Teoría y Práctica

X Y Z F1 1 1 11 1 0 01 0 0 11 0 1 00 1 0 10 1 1 00 0 1 10 0 0 0

9

FACULTAD DE INGENIERIAESCUELA DE COMPUTACION ESTRUCTURAS DISCRETAS

6.7 Ejercicios Propuestos de la Unidad 7:

1.- Sean las funciones, F (x, y, z) = XYZ + XYZ y G (x, y, z) = Z (XZ + XZ), dos funciones booleanas. Si la función H (x, y, z) = F G. Hallar la tabla de valores de la función H(x, y, z).

2.- Diseñar el circuito lógico basado en compuertas lógicas, que produzca la salida indicada en la siguiente función: ____________ ______ ____ ___ ___ _____________

F (X, Y, Z) = ((X Y Z) (X + Y + Z)) + ( X Y)

3.- Diseñar un circuito lógico de 3 entradas, basado en compuertas lógicas que cumpla con la siguiente función: se enciende una lámpara indicadora si dos de las tres entradas están en “1”. Una segunda lámpara se enciende cuando todos los suiches están cerrados o todos están abiertos. La lámpara se apaga en el resto de los casos.

4.- Obtener la función booleana de la salida F (x, y, z). Por otra parte, determinar el valor de la salida en cada compuerta, si las entradas son x=y=1 y z=0

F (x, y, z)

5.- Diseñar un circuito lógico para comparar 2 enteros X e Y, codificados a 2 Bits, de manera que determine las condiciones X > Y, Y>X y X = Y.

6.- Diseñar un circuito que sume dos enteros codificados a dos Bits.

7.- Dadas las siguientes funciones, encontrar un circuito basado en compuertas NAND y otro basado en compuertas NOR, para cada función:

F = (X+Y) (X+Z) G = (XY) + (XZ)

Modulo Instruccional Estructuras Discretas. Teoría y Práctica

x

x

x

y

y

y

z

z

z

10