Capítulo 13: ALGEBRA BOOLEANA

13.1 Introducción

George Boole fue un lógico y matemático británico. Escribió los libros: “The Mathematical Analysis of Logic” (1847) y “An Investigation of the Laws of Thought” (1854). Desarrolló la lógica Simbólica mediante la cual las proposiciones pueden ser representadas mediante símbolos y la teoría que permite trabajar con estos símbolos, sus entradas (variables o proposiciones) y sus salidas (respuestas). Dicha lógica cuenta con operaciones lógicas que siguen el comportamiento de reglas algebraicas. Consideró que las proposiciones lógicas podían ser tratadas mediante herramientas matemáticas. Las proposiciones lógicas (asertos, frases o predicados de la lógica clásica) son aquellas que únicamente pueden tomar valores Verdadero/Falso, o preguntas cuyas únicas respuestas posibles sean Sí/No. Según Boole, al conjunto de reglas de la Lógica Simbólica se le denomina Álgebra Booleana. Todas las variables y constantes del Álgebra Booleana, admiten sólo uno de dos valores en sus entradas y salidas: Sí/No, 0/1 o Verdadero/Falso. Estos valores bivalentes y opuestos pueden ser representados por números binarios de un dígito denominado bit, por lo cual el Álgebra Booleana se puede entender cómo el Álgebra del Sistema Binario.
Todas las operaciones pueden representarse mediante elementos físicos de diferentes tipos: mecánicos, eléctricos, neumáticos o electrónicos que admiten entradas binarias o lógicas y que devuelven una respuesta (salida) también binaria o lógica. Sus estados pueden ser: Abierto/Cerrado, en el casi de interruptores, Encendida/Apagada si se refiere a una bombilla, Cargado/Descargado, si se tratase de un condensador, Nivel Lógico 0/Nivel lógico 1, para producir una salida lógica de un circuito semiconductor, entre otras.
Un día en 1864 George Boole recorrió dos millas de su residencia a la universidad, bajo una lluvia torrencial para dar una conferencia que llevó a cabo con sus ropas mojadas. Como resultado, adquirió un fuerte resfriado que afectó sus pulmones y así terminó su carrera a la edad de 49 años. Parece ser que negligentemente su esposa Mary (nieta de Sir George Everest), creía que su remedio podría ser la causa. En efecto, ella puso a Boole en su cama y le arrojó cubos de agua, lo cual aceleró más su enfermedad.

El trabajo de Boole ha llegado a ser como un paso fundamental en la revolución de los computadores hoy en día. El álgebra Booleana tiene una amplia aplicación en el switch telefónico y en el diseño de computadores modernos.
A mediados del siglo XX el Álgebra Booleana se utilizó en el manejo de información digital llamada Lógica Digital. En efecto, Shannon (1930) la pudo formular en su teoría de la codificación y John Von Neumann la pudo enunciar en el modelo de arquitectura que define la estructura interna de los ordenadores desde la primera generación.
Claude Elwood Shannon (1916–2001) ingeniero eléctrico y matemático. Nacido el 30 de abril de 1916, Míchigan-USA. Reconocido como “el padre de la teoría de la información”. Falleció el 24 de febrero del año 2001, a la edad de 84 años, después de una larga lucha en contra la enfermedad de Alzheimer. Aplico el álgebra booleana a los circuitos con relés . “A Symbolic Analysis of Relay and Switchin Circuits” Trans. AIEE 1938.
El desarrollo de este capítulo tiene como finalidad iniciar a sus lectores en la comprensión de las funciones lógicas de un circuito digital como una aplicación tecnológica de la lógica de proposiciones. No se desarrollarán sistemas complejos, pero si se realizarán las operaciones básicas de un sistema digital combinatorio.

Se estudiarán aspectos básicos de un circuito digital tales como:
. La descripción simbólica de la lógica digital que mantiene sus bases en el álgebra booleana y otras técnicas matemáticas similares.

. Una introducción a los componentes electrónicos básicos de la lógica digital como lo son las compuertas lógicas.

13.2 Circuitos eléctricos simples o conmutados
13.2.1 Noción de circuito eléctrico simple

Los circuitos eléctricos simples son circuitos conmutados (figura 13.1) con interruptores que están conformados por una conexión de una fuente de voltaje (V), un interruptor o suiche (S) y una bombilla o lámpara (LAMP). La función de este sistema eléctrico consiste en cerrar o abrir el interruptor para que se encienda o se apague la lámpara, respectivamente.

Al cerrar o poner el interruptor en estado lógico1 “1”, se produce el encendido de la lámpara, a esta acción se asignará “1”; al abrir o poner el interruptor en estado en lógico “0”, se produce el apagado de la lámpara, a cuya acción se asignará el estado lógico “0” (vea tabla 13.1).

13.2.2 Tipos de circuitos conmutados

Los circuitos conmutados según la distribución de sus interruptores se pueden clasificar así:
. Circuitos conmutados en serie. Son aquellos circuitos cuyos interruptores van de manera consecutiva (figura 13.2).

. Circuitos conmutados en paralelo. Son aquellos circuitos cuyos interruptores van distribuidos en diferentes filas (figura 13.3).

13.2.3 Funciones lógicas de circuitos conmutados

Una tabla de verdad contiene valores obtenidos de las posibles combinaciones de los valores de los interruptores o pulsadores (o simplemente entradas) también se denomina función lógica.

Según la distribución de los interruptores o pulsadores en el circuito en serie corresponde a la función lógica denominada función AND y equivale al encendido o apagado de la lámpara.

Ahora, la distribución de los interruptores o pulsadores en el circuito en paralelo se produce la o función OR y corresponde al encendido o apagado de la lámpara.

Función lógica de un circuito conmutado en serie. Un circuito conmutado en serie (figura 13.2) tiene como función, dar encendido a la lámpara, si los interruptores están cerrados o apagarla, si se abre algún interruptor o pulsador. La función lógica de este circuito corresponde a la compuerta AND (tabla 13.2).

Función lógica de un circuito conmutado en paralelo. Un circuito conmutado en paralelo (figura 13.3) tiene como función darle encendido a la lámpara, siempre que alguno de los interruptores esté cerrado o de apagarla cuando se abren todos los interruptores o pulsadores. La función lógica de este circuito corresponde a la compuerta OR (tabla 13.3).

Nota: Las funciones lógicas de circuitos conmutados toman valores similares a los de las tablas de verdad de la lógica de proposiciones, solo que en vez de escribir verdadero escriba 1 y en vez de falso escriba 0.
Ejercicio 13.1: Construya la tabla de las funciones lógicas correspondientes a cada uno de los circuitos figuras 13.4a, 13.4b y 13.4c
Función

13.4 Compuertas lógicas
13.4.1 Concepto de compuerta lógica

Una compuerta lógica es un dispositivo físico conformado por elementos eléctricos o electrónicos que realizan una función lógica, cuyo resultado puede hallarse de acuerdo a los distintos valores de las variables de entrada.
Las compuertas lógicas básicas son: AND, OR, NOT (o inversor) y las compuertas negadas o invertidas de éstas, NAND, NOR, YES o BUFFER. Otro tipo de compuerta es XOR y su negación XNOR (o comparadora).
En este texto, las entradas de las compuertas se denotarán con letras minúsculas del alfabeto como w, x, y, z; de manera similar se tomará la salida con la letra mayúscula Q. Cada entrada toma los valores lógicos 0 ó 1 e igualmente, en la salida se produce 0 ó 1. Con los valores que toman las entradas y el respectivo resultado de la salida se construyen las tablas de verdad correspondientes a una función lógica.

13.4.2 Función lógica de las compuertas

Se denomina función lógica a una tabla de verdad de una compuerta o circuito digital. Una función lógica es el resultado obtenido de las posibles combinaciones de los valores de las entradas de un conjunto de compuertas lógicas.
Función lógica NOT o Inversor (vea figura 13.5). Esta compuerta se utiliza para cambiar el valor de la entrada. En efecto, la salida se obtiene cambiando el valor de la entrada así: cambia 0 por 1 y 1 por 0. La tabla de verdad de esta función lógica esta representada en la tabla 13.4.

Función lógica de AND (vea figura 13.6). Esta compuerta es equivalente a la conjunción vista en lógica de proposiciones y, en efecto, su salida toma el valor 1 si todas las entradas tienen 1 y toma el valor 0 si alguna de las entradas es 0. La tabla de verdad de esta función lógica esta representada en la tabla 13.5.

Función lógica de OR (vea figura 13.7). Esta compuerta es equivalente a la disyunción vista en lógica de proposiciones y, en efecto, su salida es 1, si alguna entrada es 1 y toma el valor 0 si todas las entradas son 0. La tabla de verdad de esta función lógica esta representada en la tabla 13.6.

Función lógica de NAND (vea tabla 13.8). Esta compuerta corresponde a la negación de la compuerta AND; por lo tanto, su función lógica tendría los valores contrarios de la AND. Intuitivamente, se dice que la salida es 1 si alguna entrada es 0 y es 0 si todas las entradas son 1. La tabla de verdad de esta función lógica esta representada en la tabla 13.7.

Función lógica de NOR (vea figura 13.9). Esta compuerta corresponde a la negación de la compuerta OR; por lo tanto, su función lógica tendría los valores contrarios de la OR. Su función lógica se representa en la tabla 13.8. Se puede concluir que la salida es 0, si al menos una entrada es 1 y es 1 si todas las entradas son 0. La tabla de verdad de esta función lógica esta representada en la tabla 13.8.

Función lógica de XOR (vea figura 13.10). La compuerta XOR también se denomina compuerta OR-exclusiva. Su función lógica se representa en la tabla 13.9. Se puede concluir que si las entradas toman valores contrarios la salida es 1 y si son iguales su salida es 0. La tabla de verdad de esta función lógica esta representada en la tabla 13.9.

Función lógica de XNOR (figura 13.12). La compuerta XNOR también denominada en otros textos como XE. Esta compuerta se utiliza para comparar. Su función lógica se representa en la tabla 12.10, de la cual se puede concluir que la salida es 1 si las entradas son iguales y 0 si las entradas toman valores contrarios.

Ejercicio 13.2: Utilizando las compuertas AND, OR, NAND o NOR dibuje el circuito correspondiente a la compuertas XOR y XNOR.

12.4 Circuitos digitales

Se denomina circuito digital a la interconexión formada por dos o más compuertas lógicas que producen una función lógica. Es decir, es la combinación de varias compuertas lógicas; por eso también le llaman circuitos lógicos combinacionales. Para dibujarlo se utilizan líneas que corresponden a los alambres conductores eléctricos; la conexión de estos alambres se diferenciará del cruce de los cables porque llevarán un punto en dicho enlace (vea figura 13.12).

13.5 Función lógica de un circuito digital

Función lógica de un circuito digital está formada por las posibles combinaciones de valores de las entradas de la compuerta principal, consignando así la salida final. Las salidas parciales de las diferentes compuertas lógicas conformarán las entradas de las compuertas de un nivel superior.
Se recomienda marcar las salidas parciales de cada compuerta con Qi (i=1, 2, 3, …). Los valores obtenidos para cada Qi servirán como entrada para cada compuerta de nivel superior; luego se evalúa cada compuerta según la función lógica de cada una; siguiendo la secuencia del circuito se continúa hasta obtener el resultado final.

Ejemplo 13.1: Determine la función lógica del circuito de la figura 13.12. Pongamos los Qi en la salida de cada compuerta como en la figura 13.13 que da como resultado la tabla 13.12.

Nota: Un circuito lógico como la siguiente:

Ejercicio 13.3: Determine la función lógica de cada uno de los circuitos digitales de las figuras 13.14a hasta 13.14d:

13.7 Concepto de álgebra booleana

El nombre de álgebra booleana se dio en memoria a su descubridor George Boole. Mucho antes que Shannon, E. V. Huntington en 1904 ya había establecido la definición de “álgebra booleana” como un sistema axiomático consistente, completo e independiente que comprende un conjunto B con mínimo dos elementos digamos w, x, y, z (entradas), Q (salidas); dos operaciones binarias (suma +, producto •); una operación unitaria (negación ‾) y que cumplen los siguientes axiomas:
. Modulativa: x+0=0+x=x x.1=1.x=x
. Conmutativa: x+y=y+x x.y=y.x
. Distributiva: x.(y+z)=x.y+x.z x+(y.z)=(x+y).(x+z)
. Complemento:

Mediante el álgebra booleana se puede diseñar un circuito digital y simplificarlo hasta expresarlo como la mínima expresión booleana que por tanto contendría el menor número de compuertas lógicas posible al momento de implementarle físicamente, utilizando las entradas del circuito como variables y las cantidades 0 y 1 como sus únicos valores posibles para dichas entradas booleanas.

13.8 Elementos del álgebra booleana

Los siguientes elementos se utilizan para escribir expresiones booleanas que representan simbólicamente un circuito digital. Cada expresión lógica tiene su respectiva función lógica. Los elementos del álgebra booleana son:

Símbolos numéricos. Se representan por 0 y 1; corresponden a los posibles estados de una compuerta lógica (en la entrada o salida). Es 0, cuando el nivel de voltaje es bajo (0 a 0.8V) equivalente a desactivado (interruptor abierto) en lógica positiva y es 1, si el nivel de voltaje es alto (2,5 a 5V) equivalente a activado (interruptor cerrado) en lógica positiva.
Constantes. Es una señal de entrada o salida que no cambia (siempre 0 ó 1).
Variables. Es una señal que cambia con el tiempo, denominadas entradas y salidas; representadas por las letras minúsculas o mayúsculas del alfabeto respectivamente, así: las entradas por w, x, y, z; la salida por Q.
Signos de agrupación. Se utilizan paréntesis izquierdo “(“ y paréntesis derecho “)”.

Símbolo relacional. Como único símbolo relacional se utiliza el signo “=”.

13.9 Expresiones booleanas

Al igual que en álgebra tradicional, también se trabaja con letras del alfabeto para denominar variables y formar ecuaciones para obtener el resultado de ciertas operaciones mediante una ecuación o expresión booleana. Efectivamente, los resultados de las correspondientes operaciones también serán binarios.
Ejemplo 13.2: las siguientes expresiones son booleanas con x, y, z entradas y Q la salida

13.10 Trascripción de circuito digital a expresión booleana

Para transcribir un circuito digital a una expresión booleana escriba la expresión correspondiente a cada compuerta del circuito comenzando siempre por las entradas de las más independientes hasta escribir la operación de la compuerta principal.
Ejemplo 12.3: Escriba la expresión booleana correspondiente a cada uno de los circuitos de las figuras 13.15 y 13.16. La expresión lógica de la figura 13.15 se podría obtener así: determine las salidas parciales: Q1=x+y, Q2=x.y, Q4=x.y, Q5=x+y

13.11 Trascripción de expresión booleana a circuito digital

Para transcribir una expresión booleana a circuito digital se comienzan a dibujar las compuertas correspondientes a las operaciones indicadas más interna, siguiendo de manera lógica a dicha expresión.

Ejercicio 13.4:

1. Dibuje el circuito digital correspondiente a cada una de las siguientes expresiones booleanas utilizando el mínimo de compuertas posible (sin simplificar la expresión):

2. Escriba la expresión lógica de cada uno de los circuitos dados en las figuras 13.18a hasta 13.18d:

13.12 Velocidad y Retraso de Propagación

La velocidad en la que opera un circuito digital corresponde a la rapidez con que puede completar una tarea. Las limitaciones en velocidad surgen principalmente de dos fuentes:

1. El número de compuertas que una señal encuentra desde el punto de entrada al circuito y hasta la salida (que se conoce como camino lógico)

2. El retraso encontrado por una señal en transitar por una compuerta el cual no solamente proviene del tiempo que requieren los transistores en cambiar de estado, sino también del tiempo que requiere la capacitancia de las compuertas en cargarse y descargarse. Un retraso de propagación es un retardo que existe en una aplicación desde las entradas hasta obtener la salida de un dispositivo o compuerta lógica. Por ejemplo, en las compuertas de tipo NAND y NOR los retrasos de propagación son de 10 ns (nanosegundos, 1 ns=10–9 segundos).

13.13 Postulados del álgebra booleana

Según la enciclopedia Lexis, “un postulado es una proposición cuya verdad se admite sin pruebas y que es necesaria para servir de base en posteriores razonamientos”. En efecto, el álgebra booleana sugiere los siguientes postulados:

a) 0+0= 0

b) 0.0 = 0

c) 0+1= 1

d) 0.1 = 0

e) 1+0= 1

f) 1.0 = 0

g) 1+1= 1

h) 1.1 = 1

i) 0= 1

j) 1 = 0

13.14 Leyes del álgebra booleana

Partiendo de la premisa que el álgebra booleana se utiliza para verificar la consistencia de las funciones lógicas de circuitos integrados o chips, se puede asegurar que las leyes de esta álgebra son una herramienta fundamental que se utiliza para simplificar expresiones booleanas complejas y por ende, para simplificar circuitos digitales. Las leyes del álgebra booleana son las mismas utilizadas en el álgebra proposicional, con la diferencia que sus valores constantes ya no serán V y F sino 1 y 0 (vea tabla 13.13).

12.12 Simplificación de expresiones booleanas

Las leyes y los postulados booleanos permiten obtener de una expresión compleja otras expresiones idénticas más simples (generalmente con menos variables); igualmente se obtendrá su correspondiente circuito digital con menos compuertas lo cual permite que los retardos de propagación sean menores debido a que los bits tienen que pasar por el conjunto de compuertas y de tal manera pasaría por menos de las compuertas de las que pasaría originalmente. Esto es muy conveniente no solamente por el aspecto económico en la construcción de un sistema electrónico digital complejo (por ejemplo, un computador), sino además por la velocidad en el transporte de los bits.
El método de simplificar expresiones booleanas será el mismo que se ha utilizado para hacer una demostración; es decir, se pone una columna con las expresiones obtenidas y otra con la justificación (ley o postulado que se utilizó) de cada paso dado hasta alcanzar la mínima expresión.

Nótese que el circuito original (figura 13.19) tiene 7 compuertas: 3 NOT, 1 AND, 1 NAND y 2 OR.; en cambio el circuito resultante (figura 10.19b) quedó con solamente una compuerta (1 NAND), lo cual solo produciría el retraso de propagación que técnicamente igual al que haya programado el fabricante al pasar por cada compuerta.

Ejercicio 13.6
1) Simplifique cada una de las siguientes compuertas, justificando cada paso realizado; dibuje ambos circuitos y determine la cantidad de compuertas que se ahorra.

13.13 Formas útiles de expresiones booleanas

Las expresiones booleanas en aplicaciones tecnológicas pueden se representadas por dos formas especiales que muy útiles, son ellas: la forma normal disyuntiva (FND o expresada en minterms) y la forma normal conjuntiva (FNC o expresada en maxterms).
La cantidad de términos de estas formas depende de la cantidad de variables que se van a utilizar y se expresa 2n con n= cantidad de variables. Es decir, si n=2, la FND o FNC constará de 4 posibles combinaciones de términos producto o suma respectivamente y si es de 3 variables será de 8 posibles combinaciones de términos.

13.13.1 Forma normal disyuntiva

Es aquella expresión booleana formada como una suma de productos que involucra todas las variables con o sin negación; es decir, cada término que la compone está escrito como un producto de sus variables. Cada producto se denomina término minimal o miniterm. La expresión se denomina función polinomial minterms o minimales y denota f(x) para expresiones de una entrada, f(x,y) para expresiones de dos entradas o f(x,y,z) para expresiones de tres entradas y así sucesivamente. Por ejemplo, la función

Dada una expresión booleana escrita en sumas de productos incompleta, para obtener una FND se procede por simple inspección así:
. Aplique la ley de D’Morgan para quitar los complementos que estén indicados hasta que aparezcan solamente aplicados a las variables individuales.

.Aplique la ley distributiva del producto sobre la suma; de tal manera la expresión puede quedar reducida a un polinomio.

.Aplique ley de idempotencia para reducir los términos semejantes (o repetidos) y otras leyes reconocidas para simplificar.

13.13.2 Forma normal conjuntiva

Es aquella expresión booleana formada como un producto de sumas que involucra todas las variables con o sin negación; es decir, cada término que la compone está escrito como una suma de sus variables. Cada suma se denomina término maximal o maxiterm. La expresión se denomina función polinomial maxiterms o maximales. Por

Dada una expresión escrita de manera libre, a partir de ella se puede obtener la forma normal conjuntiva y esta puede usarse para hallar su complemento (vea ejemplo 12.7).
Dada una expresión booleana escrita en productos incompletos de sumas, para obtener una FNC se procede así:
. Aplique la ley de D’Morgan para quitar los complementos que estén indicados hasta que aparezcan solamente aplicados a las variables individuales.

. Aplique la ley distributiva de la suma sobre el producto (factorización).

.Aplique ley de idempotencia para reducir los términos semejantes (o repetidos).

Observe el primer apóstrofe (complemento) aplica la ley de D’Morgan y el segundo halla el complemento, es decir, busca los términos que faltan para completar la FNC.
Dada una función lógica f(x,y,z) en una tabla de valores para representarla en FNC (maxterms) tome de la tabla los 0 y en FND (minterms) tome los 1.

12.14 Simplificación de expresiones booleanas con compuertas NAND o NOR

Las diferentes empresas fabricantes de circuitos integrados y chips buscan la eficiencia de sus construcciones fabricándolas en serie y de manera automatizada; para tal fin, por consideraciones constructivas, utilizan solo compuertas NAND o NOR, es decir, diseñan los circuitos digitales con únicamente compuertas NAND o NOR, respectivamente.

Con el fin de lograr tales técnicas obtenga primero la expresión óptima; luego, utilice la ley de involución, y por último, aplique la ley de D’Morgan, si es necesario.

13.15 Mapas de Karnaugh

El mapa de Karnaugh fue inventado en 1950 por Maurice Karnaugh, un físico y matemático estadounidense. Se Graduó en la universidad de Yale en el 1952, es actualmente gobernador emérito del ICCC (International Council for Computer Communication). Ha trabajado como investigador en los Laboratorios Bell desde 1952 a 1966 y en el centro de investigación de IBM de 1966 a 1993. Así mismo, ha impartido de informática en el Politécnico de Nueva York de 1980 a 1999, y desde 1975 es miembro del IEEE (Institute of Electrical and Electronics Engineers), por sus aportaciones sobre la utilización de métodos numéricos en las telecomunicaciones.
Los mapas K aprovechan la capacidad del cerebro humano de trabajar mejor con patrones que con ecuaciones y otras formas de expresión analítica. Externamente, un mapa de Karnaugh consiste de una serie de cuadrados, cada uno de los cuales representa una línea de la tabla de verdad. Puesto que la tabla de verdad de una función de N variables posee 2N filas, el mapa K correspondiente debe poseer también 2N cuadrados. Cada cuadrado alberga un 0 ó un 1, dependiendo del valor que toma la función en cada fila. Las tablas de Karnaugh se pueden utilizar para funciones de hasta 6 variables.
Estos mapas han sido creados con el fin de obtener expresiones lógicas más simples y por ende circuitos digitales más simples y más económicos, que producen menos retardos de propagación y por lo tanto, serán de menor tamaño.

13.15.1 Concepto de mapas de Karnaugh

Hasta el momento se pueden simplificar expresiones booleanas utilizando las leyes del álgebra booleana, pero existe una herramienta importante que permite simplificar expresiones complejas escritas en FND o FNC denominada “mapa de Karnaugh”.

Dichos mapas se utilizan para simplificar expresiones escritas en estas formas sin tener que recurrir a las leyes del álgebra booleana.
Un mapa de Karnaugh es un arreglo rectangular o cuadrado de celdas adyacentes (comparten un mismo termino) con los cuales se representa de manera gráfica una expresión booleana escrita en FND o en FNC. En síntesis es una tabla de verdad en la que se escribe 1 en la intersección de la fila y la columna para indicar que el término formado por las variables de esa fila y esa columna, existe, o se escribe 0, si ese término no existe.
Los mapas se clasifican según el número de variables que representan así:

. Mapas de Karnaugh de 2 variables (Tabla 13.14a)

. Mapas de Karnaugh de e 3 variables (Tabla 13.14b)

. Mapas de Karnaugh de e 4 variables (Tabla 13.14c)

En términos prácticos, los mapas de Karnaugh son útiles hasta no más de seis variables caso tal que usa 2 mapas de 4 variables. Para un número mayor de variables, se acude a otras técnicas de simplificación como el método de Quine McCluskey.
Observe, el orden de las negaciones de las variables es estricto, mas no el nombre de las variables, es decir, el resultado no cambia si donde se escribió x se haya escrito y y viceversa, pero sin afectar el orden de las negaciones en cada mapa.

13.15.2 Adyacencias en los mapas de Karnaugh

Se dice que dos celdas están adyacentes si dichas celdas estás contiguas, mas no de manera diagonal; es decir, si sus direcciones respectivas difieren en un solo dígito. Las adyacencias de 1 se agrupan en potencias de 2 así: de a dos, de a cuatro, de a ocho y de a dieciséis 1 contiguos. También hay adyacencias cuando los 1 están ubicados en los extremos opuestos de las filas o columnas o que comparten las esquinas.
Los mapas de Karnaugh permiten representar expresiones de máximo 6 variables con los cuales se hacen simplificación de variables así:

Ejercicio 13.7: Escriba las expresiones booleanas correspondientes a cada uno de los mapas de Karnaugh dados en el ejemplo 13.9.

12.15.3 Simplificación de expresiones booleanas mediante mapas de Karnaugh

En la simplificación con mapas de Karnaugh debe considerarse no realizar muchas agrupaciones, porque a mayor cantidad de agrupaciones mayor cantidad de términos. Por lo tanto, optimizar los circuitos es obtener la menor cantidad de términos con la menor cantidad de variables y en efecto, debe realizar la menor cantidad posible de agrupaciones en el mapa, pero abarcando el máximo de adyacencias posibles.
La optimización de los circuitos es muy importante desde el punto de vista técnico y económico debido a que se mejora la velocidad de respuesta, se disipa menor potencia, se disminuyen los costos (menos compuertas), entre otros conceptos.

Ejemplo 13.10: Determine la expresión resultante de la utilización de los mapas de Karnaugh del ejemplo 13.9.
El mapa de la Tabla 13.15a representa a una expresión con 8 términos; tiene una adyacencia de 8 unos que en efecto simplificará 3 variables. La expresión resultante es:

El mapa de la Tabla 13.15b representa a una expresión con 4 términos; tiene una adyacencia de 4 unos que en efecto simplificará 2 variables. La expresión resultante es: .

El mapa de la Tabla 13.15c representa a una expresión con 4 términos; tiene una adyacencia de 4 unos que en efecto simplificará 2 variables. La expresión resultante es:

El mapa de la Tabla 13.15d representa a una expresión con 4 términos; tiene una adyacencia de 4 unos que en efecto simplificará 2 variables. La expresión resultante es:

El mapa de la Tabla 13.15e representa a una expresión con 8 términos; tiene tres adyacencias repartidas en dos de 4 unos, una de dos unos y un termino que no se simplifica. En efecto simplificará las variables así:

El mapa de la Tabla 13.15f representa a una expresión con 8 términos, pero ninguno se simplifica, porque no tiene adyacencias.

Redúzcala a una expresión óptima. Dibuje el circuito digital óptimo con compuertas básicas. Dibújelo también utilizando solamente compuertas NAND de dos entradas y determine la cantidad de retrasos de propagación del circuito si se sabe que cada compuerta produce un retardo de 10 ns.

12.16 Mapas de Karnaugh con términos irrelevantes (condiciones no importa)

Un término irrelevante en una expresión booleana es el resultado de la combinación de valores lógicos de variables no requeridas para la solución de un problema específico. Estos términos se simbolizan en el mapa en vez de 0 ó de 1 por “x”. Dichos símbolos pueden utilizarse para conformar adyacencias con las cuales se ayuda a realizar simplificaciones importantes. En el argot de la electrónica estos términos producen condiciones que se denominan “don’t care” o “no importa”.

Ejemplo 13.12: Dado el siguiente mapa (Tabla 13.17) con términos irrelevantes marcados con “x”, obtenga la expresión simplificada resultante
La expresión correspondiente

12.17 Aplicaciones de circuitos digitales

Existe gran variedad de aplicaciones de los circuitos digitales, más aún cuando en la actualidad en casi todas las situaciones del quehacer humano, el hombre quisiera controlar y automatizar desde aparatos para el oficio doméstico, máquinas y herramientas de trabajo hasta un sistema de cómputo.
Con la implementación de funciones booleanas y la construcción de circuitos digitales se han diseñado los denominados circuitos integrados que son construidos con gran cantidad y variedad de compuertas lógicas que se distribuyen y utilizan según la necesidad. En el mercado se encuentran esos componentes electrónicos con su respectivo manual que le permiten al diseñador electrónico construir el circuito, ya sea de automatismo o de control. A continuación veremos algunos ejemplos de la cotidianidad, útiles desde el punto de vista técnico y de la economía.

Ejemplo 13.13: Dada la función lógica de la Tabla 13.18 diseñe el circuito digital para 2 entradas (x, y) y 4 salidas (Q3, Q2, Q1, Q0), teniendo en cuenta que 0: low y 1: high que utilice solamente compuertas lógicas simples.

Llevemos la función lógica de cada Qi a un mapa de Karnaugh para obtener un resultado simplificado. En efecto, en las tablas 13.19a a 13.19d.

Ahora el dibujo del circuito con compuertas básicas se ve en la figura 12.23
Ejemplo 13.14: Con el fin de controlar el nivel de agua de una represa se instalan en ella 4 sensores w, x, y, z con los cuales se controlarán: dos compuertas C1 (auxiliar) y C2 (principal) y una alarma, según la figura 13.24, bajo las siguientes condiciones:
. Si el agua está en el cuarto nivel (N4) se activará el cuarto sensor (z); e abrirán ambas compuertas C1 y

. C2; además, se activará una alarma (A) que indicará posible desbordamiento de la represa.

. Si está por debajo de N4 (entre N3 y N4), entonces se activará el sensor y; abrirán las compuertas 1 (C1) y 2 (C2).

. Si está por debajo de N3 (entre N2 y N3), entonces se activará el sensor x; se abrirá la compuerta 2 (C2), únicamente.

. Si está por debajo de N2 (entre N1 y N2), entonces se activará el sensor w; se abrirá la compuerta 1 (C1), únicamente.

. Si está por debajo de N1 (N0), no se activará ningún sensor; ninguna compuerta se abrirá.

Diseñe el circuito digital que realice el control para esas compuertas. En efecto, construyamos primero la tabla de verdad correspondiente a los sensores; en efecto, vea la tabla 13.20
La función booleana para las compuertas depende de los sensores y se puede ver la taba 13.21. Los términos irrelevantes se dan porque no es posible que se activen los sensores de los niveles superiores sin activarse los de los inferiores.
Ahora, construyamos los mapas de Karnaugh y el circuito digital y la alarma (A).
En las tablas 13.2a, 13.22b, 13.22c, respectivamente están las tablas para las compuertas C1, C2 y la alarma A.

AUTOEVALUACIÓN

1. En los problemas 1.1 hasta 1.5 escoja la opción correcta:

A) Si 1 y 2 son correctas

B) Si 2 y 3 son correctas

C) Si 3 y 4 son correctas

D) Si 2 y 4 son correctas

E) Si 1 y 3 son correctas

3.1 El circuito óptimo de la tabla 13.26 es:

A) una XNOR B) una AND C) una XOR D) una NOR E) una NAND

3.2 El circuito óptimo de la tabla 13.27 es:

A) una XNOR B) una AND C) una XOR D) una NOR E) una NAND

3.3 El circuito óptimo de la tabla 13.28 es:

A) una XNOR B) una AND C) una XOR D) una NOR E) una NAND

TALLER 13

1. Dada la función lógica de la tabla 13.29 diseñe un circuito digital con seis entradas (A0, A1, A2, A3, C1, C0) y una salidas (Q), teniendo en cuenta que 0: low y 1: high que utilice solamente compuertas lógicas.
   
   
   2. Dada la función lógica de la tabla 13.30 diseñe un circuito digital con cuatro entradas (D ,C, B, A) y una salidas (Q1, Q2), teniendo en cuenta que 0: low y 1: high que utilice solamente compuertas lógicas.
   3. Determine la expresión booleana óptima del ejemplo13.12 utilizando la técnica NOR y dibuje su circuito correspondiente.
   4. Simplifique las expresiones booleanas dadas desde 4.1 hasta 4.6, utilizando mapas de karnaugh y leyes del álgebra booleana. Conviértalas en expresiones óptimas. Dibuje el circuito digital óptimo con compuertas básicas. Dibújelo también utilizando solamente compuertas NAND y compuertas NOR de dos entradas. Determine la cantidad de retrasos de propagación del circuito dado que en cada compuerta produce un retardo de 10 ns.

5. Diseñe un circuito digital que controle una lámpara desde 3 interruptores puestos en diferentes sitios.
6. La dirección de seguridad de un edificio ha dispuesto de tres tanques en la azotea del edificio para controlar un incendio, en cualquier momento. Los tanques 1 y 2 deben abastecer simultáneamente para sostener el flujo de agua y para que sea mantenido, el tanque 3 debe abastecer. En ningún momento el tanque 3 deberá funcionar cuando lo hagan los tanques 1 y 2. Diseñe un circuito digital que controle esa situación.
7. El río Rioabajo cruza la zona urbana del municipio Rioabajo; dicho río tiene como afluentes dos caudalosas quebradas que precisamente le llegan poco antes de cruzar la zona urbana. El gobierno de este municipio ha dispuesto una casa central con dos alarmas (amarilla y roja) para que den aviso dependiendo de los niveles alcanzados por ese río. Para tal fin, los técnicos han colocado unos sensores que se activan al tener contacto con el nivel de agua. Las señales pueden ser:

(0,0): es Normal; en tal caso, no se activarán las alarmas.

(0,1): es un estado irrelevante, porque no es posible que se active la alarma roja sin activarse la amarilla.

(1,0): se activa la alarma amarilla (alerta).

(1,1): se activa la alarma roja (la población ubicada en las riveras del río debe subir hacia las laderas del municipio).
Diseñe el circuito digital que active a dichas alarmas correctamente en un momento dado.
8. El propietario de electrónicas NORNAND & Cia. ha pedido a sus técnicos diseñar un chip para activar y desactivar una alarma a partir de tres interruptores. La alarma se activa según los siguientes casos:

. El primero (x) esté cerrado y los otros dos (y, z) estén abiertos.

. El primero y el segundo (x, y) estén cerrados y el tercero (z) esté abierto.

. Los tres interruptores estén cerrados.

9. El propietario de electrónicas NORNAND & Cia. ha pedido a sus técnicos diseñar un chip para poner en funcionamiento una alarma a partir de tres interruptores. La alarma se activa cerrando simultáneamente dos interruptores; en los demás casos quedará desactivada. Para tal fin, los técnicos se ponen en esta tarea y presentan las siguientes funciones booleanas:

¿Ambas funciones son correctas para las exigencias del propietario? Analícelas. Si ambas funciones son correctas, técnicamente ¿cuál recomienda? ¿Por qué?
10. Se quiere diseñar un dispositivo con tres interruptores (x, y, z): uno para control de alarma de un vehículo, otro para asegurar las puertas y un tercero para activar el mecanismo del elevavidrios. El sistema funciona así:

.Si se cierra el primer interruptor (x) se activa la alarma.

. Si se cierra el segundo interruptor (y) se activan los seguros de las puertas.

.Si se cierran simultáneamente los dos primeros interruptores (x, y), el sistema no funcionará (ni alarma ni elevavidrios ni los seguros).

. Si se cierra el tercer interruptor (z) se activa el elevavidrios (cerrando los vidrios si están abiertos).

Diseñe el circuito digital óptimo adecuado técnicamente para el sistema planteado.

12. Seleccione la respuesta correcta según los siguientes casos, que dé respuestas a las situaciones planteadas en los numerales 12.1 a 12.3:

A) Si la afirmación y la razón son VERDADERAS y la razón es una explicación CORRECTA de la afirmación

B) Si la afirmación y la razón son VERDADERAS, pero la razón NO es una explicación CORRECTA de la afirmación

C) Si la afirmación es VERDADERA, pero la razón es una proposición FALSA D) Si la afirmación es FALSA, pero la razón es una proposición VERDADERA E) Si tanto la afirmación como la razón son proposiciones FALSAS

Los mapas de Karnaugh se usan como herramienta para simplificar expresiones booleanas expresadas en las formas FNC o FND o circuitos digitales complejos, simplificándolos de manera óptima sin la utilización de leyes del álgebra booleana PORQUE los mapas de Karnaugh permiten expresar circuitos digitales con menor valor económico, que producen menos retardos y son más confiables. Respuesta: ___

16. Los circuitos lógicos combinacionales de la figura 13.28 tienen su equivalencia con las compuertas básicas. Determine a cuál compuerta corresponde cada una.