SEMANA 2 (Compuertas Lógicas y Álgebra Booleana) (COMPLETO)

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 57

Sistemas digitales y periféricos

Compuertas lógicas y álgebra Booleana

Dr. Carlos Raúl Montaño Espinosa


Matrícula 019851149

Open class
Semana 2
120
4
5
3
Descarga la app Edutel
Utiliza la APP para tus actividades de la semana, en:

•Actividades: Participen en el foro.


•Exámenes: Realicen examen de la semana.
•Puntos extra: Autocalificables
Es compatible con Android y iOS.

https://play.google.com/store/apps/details?id=com.do
naumorgen.utel&hl=es_419&gl=US
Recomendaciones iniciales.

 En caso de tener algún problema de audio, favor de salir y volver a


iniciar la sesión.
 Verificar que sus altavoces estén encendidos.
 En caso de tener alguna pregunta favor de hacerla en el espacio
respectivo.
 Esta es una clase participativa, por lo que todos debemos aportar
conocimiento.
 Para hacer válidos tus puntos extras deberás entregar contestadas
las preguntas que se harán a lo largo de la clase. Las respuestas se
deberán enviar, en formato UTEL, al apartado de puntos extra con
los siguientes datos de la clase: Semana, hora, tema, nombre del
profesor que impartió la open class y materia.
Objetivos generales

 Detallar las compuertas lógicas y algunos de los teoremas


fundamentales con el uso de la lógica booleana.
 Optimización de circuitos lógicos de dos niveles.
Compuertas lógicas
Los circuitos digitales son componentes de hardware que manipulan información binaria.
Los circuitos se realizan con transistores e interconexiones en complejos dispositivos de
semiconductores llamados circuitos integrados. A cada circuito básico se le denomina
compuerta lógica.

La lógica binaria trabaja con variables binarias, que pueden tomar dos valores discretos, y
con las operaciones lógicas matemáticas aplicadas a esas variables

Una tabla de verdad para una operación es una tabla de combinaciones de las variables
binarias que muestran la relación entre los valores que toman las variables y los valores del
resultado de la operación.

1
Compuertas lógicas en tablas de verdad

7408 7400

7432 7402

7404 7486

74266
• AND. Esta operación está representada por un punto o por la ausencia de un operador.
• OR. Esta operación se representa por el símbolo «más».
• NOT. Esta operación está representada por una barra encima de la variable.
• XOR: Se puede utilizar para detectar señales que son distintas.
• XNOR: Se puede utilizar para detectar señales que son iguales
Los símbolos alternativos para el · de la AND y el + de la OR, son los símbolos ∧ y ∨, respectivamente, que representan
operaciones conjuntivas y disyuntivas en cálculos proposicionales.
Lógica Booleana
Para describir las propiedades operacionales de los circuitos digitales es necesario
introducir una notación matemática que especifica la operación de cada puerta y que
puede ser usada para analizar y diseñar circuitos. Este sistema de lógica binaria es una clase
de sistema matemático que se denomina Álgebra de Boole. Es un álgebra que trata con
variables binarias y operaciones lógicas.

Las variables se indican con las letras del alfabeto y las operaciones básicas son AND, OR y
NOT. Una expresión booleana es una expresión algebraica formada por variables binarias,
las constantes 0 y 1, los símbolos de operación lógicos y paréntesis.

Una función booleana con única salida se tabula a partir de cada combinación posible de
valores 0 y 1 entre las variables de la función al valor 0 o 1. Una función booleana con
salida múltiple se tabula a partir de cada combinación posible de valores 0 y 1 entre las
variables de la función a combinaciones de 0 y 1 entre las salidas de la función.
Lógica Booleana
Ejemplo 1.
Considera una ecuación booleana que representa a la función 𝐹 𝑋, 𝑌, 𝑍 = 𝑋 + 𝑌𝑍
A las dos partes de la expresión, 𝑋 y 𝑌𝑍 , se les llaman términos de la expresión de F.

Una ecuación booleana se evalúa determinando el valor binario de la expresión para


todas las combinaciones posibles de valores para las variables. Una tabla de verdad para
una función es una lista de todas las combinaciones de 1 y 0 que se pueden asignar a las
variables binarias y una lista que indica el valor de la función para cada combinación
binaria.

El número de filas en una tabla de verdad es 2𝑛 , donde


n es el número de variables de la función. Las
combinaciones binarias para la tabla de verdad son los
números binarios de n-bit que corresponden a la cuenta
en decimal de 0 a 2𝑛 -1.
Transformación de una expresión algebraica en un diagrama de circuito
En los diagramas lógicos de los circuitos, las variables de la función F se toman como
entradas del circuito y la variable binaria F se toma como salida del circuito. Si el circuito
tiene una única salida, F es una función de salida única. Si el circuito tiene múltiples salidas,
la función F es una función de salida múltiple que requiere de múltiples ecuaciones para
representar sus salidas.

A los circuitos lógicos de este tipo se les llama circuitos


lógicos combinacionales, porque las variables están
“combinadas” por las operaciones lógicas.

OR
AND
Identidades básicas del álgebra de Boole
=
+

Propiedades duales

Teorema de DeMorgan para


n variables
Construcción de circuitos básicos con Circuit Maker

Circuit-Maker es un software de simulación de circuitos electrónicos que nos facilita


el diseño de circuitos tanto digitales como analógicos lo que nos ahorra tiempo y
dinero en la elaboración de los mismos. Circuit-Maker es muy practico y sencillo de
utilizar, cuenta con un menú en su interfaz muy amigable y de fácil acceso a las
distintas opciones requeridas para el circuito que estamos elaborando.

Construye el circuito lógico, utilizando Circuit Maker, para la siguiente expresión


booleana y diagrama de bloque:

Entradas Salidas

A
𝐹 = 𝐴𝐵 + 𝐴𝐵 F

B
Latch D
sincronizado
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
𝐹 = 𝐴𝐵 + 𝐴𝐵
Construcción de circuitos básicos con Circuit Maker
HEXA A B 𝑨 𝑩 𝑨𝑩 𝑨𝑩 𝑨𝑩 F=𝐴𝐵 + 𝐴𝐵
0 0 0 1 1 1 0 1 1
𝐹 = 𝐴𝐵 + 𝐴𝐵 1 0 1 1 0 0 1 0 0
2 1 0 0 1 0 0 1 1
3 1 1 0 0 0 0 1 1
Gamificación con BooleanTT sobre BlueStack

Una aplicación, para celular, ligera pero potente para:


● Simplificar / Minimizar Expresiones
● Resolver el mapa de Karnaugh
● Simular circuitos lógicos
● Generar circuitos lógicos
● Cálculos del sistema numérico
● Generar tablas de la verdad
● Aprender básico sobre álgebra booleana.
Simplificación de circuitos digitales
El Álgebra de Boole es un instrumento muy útil para simplificar circuitos digitales

𝑎) 𝐹 𝑋, 𝑌, 𝑍 = 𝑋𝑌𝑍 + 𝑋𝑌 𝑍 + 𝑋𝑍

Hagamos una simplificación de la expresión para F aplicando algunas de las identidades

La expresión se reduce a sólo dos términos

𝑏) 𝐹 𝑋, 𝑌, 𝑍 = 𝑋𝑌 + 𝑋𝑍
Simplificación de circuitos digitales
Ambas expresiones tienen la misma tabla de verdad, por lo tanto son equivalentes.
X Y Z 𝑿 𝒁 𝑿YZ 𝑿Y𝒁 XZ 𝒂 𝑭 = 𝑿YZ+𝑿Y𝒁+XZ 𝑿Y 𝒃 𝑭 = 𝑿Y+XZ
0 0 0 1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0
0 1 0 1 1 0 1 0 1 1 1
0 1 1 1 0 1 0 0 1 1 1
1 0 0 0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 1 1 0 1
1 1 0 0 1 0 0 0 0 0 0
1 1 1 0 0 0 0 1 1 0 1

Ejemplo 2.
𝑋 + 𝑌 𝑋 + 𝑌 = 𝑋𝑋 + 𝑋 𝑌 + 𝑋𝑌 + 𝑌 𝑌 = 𝑋 + 𝑋𝑌 + 𝑋𝑌 + 0 = 𝑋 + 𝑋 𝑌 + 𝑌 = 𝑋 + 𝑋 = 𝑋

Observación: 𝑋𝑋 = 𝑋, 𝑋 𝑋 = 0, 𝑋1 = 𝑋 𝑦 𝑌 + 𝑌 = 1
Simplificación de circuitos digitales
Ejemplo 3.

𝑋 𝑋 + 𝑋 = 𝑋𝑋 + 𝑋𝑋 = X + 0 = X

𝑋 𝑋 + 𝑌 = 𝑋 𝑋 + 𝑋𝑌 = 0 + XY = XY

Observación: 𝑋𝑋 = 𝑋, 𝑋 𝑋 = 0,

El principio de dualidad del Álgebra de Boole expresa que una ecuación booleana
permanece válida si tomamos el dual de la expresión en ambos lados del signo de igualdad.

ECUACIÓN BOOLEANA ECUACIÓN DUAL

1. X + XY = X 1 + 𝑌 = 𝑋 4. X 𝑋 + 𝑌 = X + XY = 𝑋
2. 𝑋𝑌 + 𝑋𝑌 = 𝑋 𝑌 + 𝑌 = 𝑋 5. 𝑋 + 𝑌 𝑋 + 𝑌 = 𝑋 + 𝑌𝑌 = 𝑋
3. 𝑋 + 𝑋𝑌 = 𝑋 + 𝑋 𝑋 + 𝑌 = 𝑋 + 𝑌 6. 𝑋 𝑋 + 𝑌 = 𝑋𝑋 + 𝑋𝑌 = 𝑋𝑌
Teorema de consenso
𝑋𝑌 + 𝑋𝑍 + 𝑌𝑍 = 𝑋𝑌 + 𝑋𝑍

El teorema muestra que el tercer término, YZ, es redundante y se puede eliminar. Nota que
se asocian Y y Z con X y 𝑋 en los primeros dos términos y que aparecen juntos en el término
eliminado.

Demostración

El dual del teorema de consenso es

𝑋+𝑌 𝑋+𝑍 𝑌+𝑍 = 𝑋+𝑌 𝑋+𝑍


Simplificación de circuitos digitales. Teorema de Consenso
Ejemplo 5.

Observa que 𝐴𝐴 = 0y 0+AC=AC. El término redundante eliminado por el teorema de


consenso es BC.

Dado un par de términos en donde aparece una variable en uno de ellos y su


complemento en el otro, el término de consenso se obtiene al multiplicar los dos
términos originales, eliminando de ellos la variable seleccionada y su complemento.
Complemento de una función
La representación complementaria de una función F, 𝐹, se obtiene de un intercambio de 1
por 0 y 0 por 1 en los valores de F en la tabla de verdad. La forma generalizada de este
teorema expresa que se obtiene el complemento de una expresión mediante el intercambio
de las operaciones AND y OR y complementando cada variable y cada constante.

Ejemplo 6
Encuentre el complemento de la función siguiente
𝐹 = 𝑋𝑌𝑍 + 𝑋𝑌𝑍

Aplicando el Teorema de DeMorgan tantas veces como sea necesario, obtenemos el


complemento según lo siguiente:

𝐹 = 𝑋𝑌 𝑍 + 𝑋 𝑌𝑍 = 𝑋𝑌 𝑍 𝑋 𝑌𝑍 = 𝑋 + 𝑌 + 𝑍 𝑋 + 𝑌 + 𝑍
Complemento de una función
Un método más simple para derivar el complemento de una función es calcular el dual de
la ecuación de la función y complementar cada literal.
Ejemplo 7

Encuentre el complemento de la función anterior calculando los duales de su ecuación y


complementando cada literal.

𝐹 = 𝑋𝑌 𝑍 + 𝑋 𝑌𝑍 = 𝑋𝑌 𝑍 + 𝑋𝑌𝑍

El dual de la ecuación anterior es

𝐹 = 𝑋𝑌𝑍 + 𝑋𝑌𝑍

Complementando cada literal, se tiene

𝐹= 𝑋+𝑌+𝑍 𝑋+𝑌+𝑍
Formas canónicas. Mintérminos
La forma canónica contiene términos producto y términos suma. Un ejemplo de un
término producto es 𝑋𝑌 𝑍 y un ejemplo de un término suma es 𝑋 + 𝑌 + 𝑍.
A un término producto donde todas las variables aparecen exactamente una vez, sean
complementadas o no complementadas, se le llama mintérmino. El símbolo para un
mintérmino es 𝑚𝑗 , donde j denota el equivalente decimal de una combinación binaria
para la que el minitérmino tiene el valor 1.

Hay 2𝑛 diferentes mintérminos para n variables.


Los cuatro mintérminos para las dos variables X e Y son y 𝑋 𝑌, 𝑋𝑌, 𝑋𝑌 y XY.
Formas canónicas. Maxtérminos
A un término suma que contiene todas las variables de forma complementada o no
complementada se le llama maxtérmino. El símbolo para un maxtérmino es Mj, donde j
denota el equivalente decimal de una combinación binaria para la que el maxtérmino
tiene el valor 0.

Hay 2𝑛 diferentes maxtérminos para n variables.

Un mintérmino es una función, no igual a 0, que tiene el menor número de 1s en su


tabla de verdad; un maxtérmino es una función, no igual a 1, que tiene el mayor número
de 1s en su tabla de verdad.
Expresar una función booleana como producto de maxitérminos
La función F = 𝑋𝑌 𝑍 + 𝑋𝑌 𝑍 + 𝑋 𝑌𝑍 + 𝑋𝑌𝑍 = 𝑚0 + 𝑚2 + 𝑚5 + 𝑚7
Esto se puede abreviar más enumerando solamente los subíndices decimales de los
mintérminos:
F 𝑋, 𝑌, 𝑍 = 𝑚 0,2,5,7

El símbolo Σ significa la suma lógica (OR booleana) de los mintérminos


El complemento de la función F es F = 𝑋𝑌𝑍 + 𝑋𝑌𝑍 + 𝑋 𝑌𝑍 + 𝑋𝑌𝑍 = 𝑚1 + 𝑚3 + 𝑚4 + 𝑚6
de forma abreviada
𝐹 𝑋, 𝑌, 𝑍 = 𝑀 1,3,4,6

Para demostrarlo, tomamos el complemento de para obtener F:

F = 𝑚1 + 𝑚3 + 𝑚4 + 𝑚6 = 𝑚1 ∙ 𝑚3 ∙ 𝑚4 ∙ 𝑚6 = 𝑀1 ∙ 𝑀3 ∙ 𝑀4 ∙ 𝑀6 (ya que 𝑚𝑗 = 𝑀𝑗 )

F = 𝑋+𝑌+𝑍 𝑋+𝑌+𝑍 𝑋+𝑌+𝑍 𝑋+𝑌+𝑍

F 𝑋, 𝑌, 𝑍 = 𝑀 1,3,4,6
Conversión de una función booleana como suma de mintérminos
Una función que no tiene la forma de suma de mintérminos puede convertirse a esta
forma mediante la tabla de verdad, mientras que la tabla de verdad especifica los
mintérminos de la función. Es una expresión algebraica canónica que se obtiene
directamente de una tabla de verdad.
Ejemplo 8
Sea E = 𝑌 + 𝑋𝑌 la cual no tiene forma de suma de mintérminos, porque cada término no
contiene todas los tres variables X, Y, y Z.
De la tabla, obtenemos los mintérminos de la función: Tabla de verdad de la
función E
E 𝑋, 𝑌, 𝑍 = 𝑚 0,1,2,4,5

𝐸 𝑋, 𝑌, 𝑍 = 𝑀 3,6,7

El número total de mintérminos en E y 𝐸 es igual a


ocho, ya que la función tiene tres variables las cuales
producen un total de ocho mintérminos.

¿Cuántos minterminos habrá para 4 variables y por qué?

Habrá 16 mintérminos. Por que hay 𝟐𝒏 minitérminos para n variables


Circuito de dos niveles
Si se ha obtenido una vez la suma de minitérminos de la tabla de verdad, el siguiente paso
es intentar simplificar la expresión para ver si es posible reducir el número de productos y
el número de literales en los términos. El resultado es una suma de productos.

Ejemplo 9
Sea F = 𝑌 + 𝑋𝑌 𝑍 + 𝑋𝑌 la cual es una función booleana expresada como suma de productos.

Las puertas AND seguidas por la puerta OR


forman una configuración de circuito al que se le
denomina implementación de dos niveles o
circuito de dos niveles.

¿Qué se debería agregar al diagrama si las variables fuesen no negadas?


Conversión a forma canónica
Si una expresión no está en la forma de suma de productos, se puede convertir a una forma
canónica mediante las leyes distributivas.
Ejemplo 10

Sea F = 𝐴𝐵 + 𝐶(𝐷 + 𝐸) la cual es una función booleana expresada como suma de


productos.

F = 𝐴𝐵 + 𝐶(𝐷 + 𝐸)

La expresión puede convertirse en una suma de productos aplicando la ley distributiva.

F = 𝐴𝐵 + 𝐶 𝐷 + 𝐸 = 𝐴𝐵 + 𝐶𝐷 + 𝐶𝐸
Formas canónicas. Producto de sumas
Esta forma se obtiene formando un producto lógico de sumas. Cada término de la suma
lógica puede tener cualquier número de literales diferentes.

Ejemplo 11

Sea F = 𝑋(𝑌 + 𝑍)(𝑋 + 𝑌 + 𝑍) Como en el caso de la suma de productos, este tipo de


expresión canónica está formada por una estructura de dos niveles de compuertas.

F = 𝑋(𝑌 + 𝑍)(𝑋 + 𝑌 + 𝑍)
Ejercicios propuestos
Criterios de costo por literal
El costo por literal, se refiere al número de veces que aparecen las literales en una
expresión booleana que corresponde exactamente al diagrama lógico.

En la primera ecuación aparecen cinco literales y seis en la segunda, de esta forma, la


primera ecuación es la más simple en términos de coste por literal. Empero no
representa correctamente la complejidad del circuito en todos los casos.
Criterios de costo por entrada de compuerta
El costo por entrada de compuerta, se refiere el número de entradas a las puertas en la
implementación que corresponde exactamente a la ecuación o las ecuaciones dadas.

Para las ecuaciones de suma de productos o producto de sumas, se puede averiguar


encontrando la suma de
(1) todas las apariciones de los literales,
(2) el número de términos excluyendo términos que solamente consisten en un único literal,
y, opcionalmente,
(3) el número de diferentes literales complementados.

Las respectivas sumas de las entradas de las puertas son:

Literales = 4 Literales = 4
Compuertas = 7 Compuertas = 7
Inversores = 3 Inversores = 4
Total = 14 Total = 15

¿Por qué?
Mapas de Karnaugh o mapas-k
El método de Mapa de Karnaugh, o mapa-K, se trata de un diagrama hecho con cuadrados,
donde cada cuadrado representa un mintérmino de la función. Puesto que cualquier función
booleana se puede expresar como suma de mintérminos, una función booleana puede ser
reconocida gráficamente en el mapa por aquellos cuadrados cuyos mintérminos se incluyen
en la función.

El mapa presenta un diagrama visual de todos los caminos posibles para expresar una
función en forma canónica.

El mapa de dos variables consiste en cuatro


cuadrados, uno por cada mintérmino,
Simplificación de una función lógica
Dada un mapa de Karnaugh correspondiente a una función lógica expresada en DNF,
el procedimiento para su simplificación es el siguiente:
1. Se agrupan las celdas con valor ‘1’ de la tabla teniendo en cuenta las siguientes
reglas:
2. Un grupo está formado por un número variable de celdas con valor ‘1’.
3. El número de celdas con valor ‘1’ dentro de un grupo debe ser potencia de dos: 1,
2, 4, 8, 16.
4. A efectos de la formación de grupos se debe considerar la tabla como toroidal, pues
los extremos de la tabla son adyacentes: el extremo derecho es adyacente al
izquierdo, y el inferior al superior.
Simplificación de una función lógica
5. Todas las celdas con valor ‘1’ deben pertenecer al menos a un grupo.
6. Una celda con valor ‘1’ puede pertenecer a varios grupos distintos.
7. El número de grupos debe ser mínimo.
8. Cuanto mayor sea el tamaño del grupo, mayor será la simplificación, tanto en
número de términos como en número de literales por cada término.
9. No es necesario que todos los grupos tengan el mismo tamaño.
10. Por último, puede darse el caso de que la función contenga alguna interpretación ‘x’
que no sea posible (por ejemplo, por representar parte de un sistema físico con
combinaciones de entradas que son físicamente imposibles). A las celdas
correspondientes a esas interpretaciones se les asigna un valor ‘x’. Dichas celdas
no tienen por qué pertenecer a ningún grupo, pero pueden emplearse para
agrandar grupos ya existentes.
Mapas de dos variables
Una función de dos variables puede ser representada en un mapa marcando los
cuadrados que corresponden a los mintérminos de la función.

Ejemplo 12

F= 𝑚3 = 𝑋𝑌

G = 𝑚1 + 𝑚2 + 𝑚3 = 𝑋𝑌 + 𝑋𝑌 + 𝑋𝑌 = 𝑋 + 𝑌

La expresión optimizada X|Y se determina del área de dos cuadrados para la variable X en
la segunda fila y del área de dos cuadrados para Y en la segunda columna. Juntas, estas
dos áreas incluyen los tres cuadrados pertenecientes a X o Y.

Justificación algebraica:
Mapas de tres variables
Hay ocho minitérminos para tres variables binarias. Por eso, un mapa de tres variables
tiene ocho cuadrados,

Ejemplo 13

Simplificación de la función booleana


Pregunta de investigación
1.- Con ayuda del software logisim (https://www.rollapp.com/app/logisim) ¿cómo se
podrían generar los circuitos lógicos para las siguientes expresiones algebraicas?.
a.- 𝐹 𝑋, 𝑌, 𝑍 = 𝑋 𝑌 + 𝑍 b.- 𝐹 𝑋, 𝑌, 𝑍 = 𝑋(𝑌 + 𝑍)
2.-¿Cómo se podría demostrar, por medio de tablas de verdad, la validez de las siguientes
identidades
a) Teorema de DeMorgan para tres variables: 𝑋𝑌𝑍 = 𝑋 + 𝑌 + 𝑍
b) La segunda ley distributiva: 𝑋 + 𝑌𝑍 = (𝑋 + 𝑌)(𝑋 + 𝑍)
Realizar tu autocalificable de la
semana 1 desde la app EDutel

https://1drv.ms/f/s!AsiTCY_FPh97lyvx_4tU7nGBbbFP

Dr. Carlos Raúl Montaño Espinosa


Matrícula 019851149

También podría gustarte