álgebras booleanas

Introducción Las álgebras booleanas, estudiadas por primera vez en detalle por George Boole , constituyen un área de las matemáticas que ha pasado a ocupar un lugar prominente con el advenimiento de la computadora digital. Son usadas ampliamente en el diseño de circuitos de distribución y computadoras, y sus aplicaciones van en aumento en muchas otras áreas. En el nivel de lógica digital de una computadora, lo que comúnmente se llama hardware, y que está formado por los componentes electrónicos de la máquina, se trabaja con diferencias de tensión, las cuales generan funciones que son calculadas por los circuitos que forman el nivel. Éstas funciones, en la etapa de diseña del hardware, son interpretadas como funciones de boole. En el presente trabajo se intenta dar una definición de lo que es un álgebra de boole; se tratan las funciones booleanas, haciendo una correlación con las fórmulas proposicionales. Asimismo, se plantean dos formas canónicas de las funciones booleanas, que son útiles para varios propósitos, tales como el de determinar si dos expresiones representan o no la misma función. Pero para otros propósitos son a menudo engorrosas, por tener más operaciones que las necesarias. Particularmente, cuando estamos construyendo los circuitos electrónicos con que implementar funciones booleanas, el problema de determinar una expresión mínima para una función es a menudo crucial. No resultan de la misma eficiencia en dinero y tiempo, principalmente, dos funciones las cuales calculan lo mismo pero donde una tiene menos variables y lo hace en menor tiempo. Como solución a este problema, se plantea un método de simplificación, que hace uso de unos diagramas especiales llamados mapas o diagramas de Karnaugh, y el cual tiene la limitación de poder trabajar adecuadamente sólo con pocas variables. Se realizan estas presentaciones con el fin de demostrar la afinidad existente entre el álgebra de boole y la lógica proposicional, y con el objeto de cimentar el procedimiento de simplificación presentado en la lógica de proposiciones. 2. Reseña Histórica A mediados del siglo XIX, George Boole (1815-1864), en sus libros: "The Mathematical Analysis of Logic" (1847) y "An Investigation of te Laws of Thought" (1854), desarrolló la idea de 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, estas proposiciones pueden ser representadas mediante símbolos y la teoría que permite trabajar con estos símbolos, sus entradas (variables) y sus salidas (respuestas) es la Lógica Simbólica desarrollada por él. Dicha lógica simbólica cuenta con operaciones lógicas que siguen el comportamiento de reglas algebraicas. Por ello, al conjunto de reglas de la Lógica Simbólica se le denomina ÁLGEBRA DE BOOLE. A mediados del siglo XX el álgebra Booleana resultó de una gran importancia práctica, importancia que se ha ido incrementando hasta nuestros días, en el manejo de información digital (por eso hablamos de Lógica Digital). Gracias a ella, Shannon (1930) pudo formular su teoría de la codificación y John Von Neumann pudo enunciar el modelo de arquitectura que define la estructura interna de los ordenadores desde la primera generación. 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 (bits), por lo cual el Álgebra booleana se puede entender cómo el Álgebra del Sistema Binario. 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. Evidentemente los resultados de las correspondientes operaciones también serán binarios. Todas las operaciones (representadas por símbolos determinados) pueden ser materializadas 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. Ejemplos de dichos estados son: Abierto/Cerrado (interruptor), Encendida/Apagada (bombilla), Cargado/Descargado (condensador) , Nivel Lógico 0/Nivel lógico 1 (salida lógica de un circuito semiconductor), etcétera. Los dispositivos con los cuales se implementan las funciones lógicas son llamados puertas (o compuertas) y, habitualmente, son dispositivos electrónicos basados en transistores. Estos dispositivos, y otros que veremos a lo largo de esta unidad, son los que permiten el diseño, y la ulterior implementación, de los circuitos de cualquier ordenador moderno, así como de muchos de los elementos físicos que permiten la existencia de las telecomunicaciones modernas, el control de máquinas, etcétera. De hecho, pensando en los ordenadores como una jerarquía de niveles, la base o nivel inferior sería ocupada por la lógica digital (en el nivel más alto del ordenador encontraríamos los actuales lenguajes de programación de alto nivel). En esta unidad se representan las puertas lógicas elementales, algunas puertas complejas y algunos ejemplos de circuitos digitales simples, así como algunas cuestiones de notación. Por otra parte se plantean actividades de trabajo, muchas de las cuales implican una respuesta escrita en vuestro cuaderno de trabajo. El deseo del autor es que os resulte sencillo y ameno adentraros en el mundo de la lógica digital y despertaros la curiosidad, tanto por ella, como por la matemática que subyace en ella. 3. Álgebra Booleana El álgebra booleana es un sistema matemático deductivo centrado en los valores cero y uno (falso y verdadero). Un operador binario " º " definido en éste juego de valores acepta un par de entradas y produce un solo valor booleano, por ejemplo, el operador booleano AND acepta dos entradas booleanas y produce una sola salida booleana. Para cualquier sistema algebraico existen una serie de postulados iniciales, de aquí se pueden deducir reglas adicionales, teoremas y otras propiedades del sistema, el álgebra booleana a menudo emplea los siguientes postulados: • Cerrado. El sistema booleano se considera cerrado con respecto a un operador binario si para cada par de valores booleanos se produce un solo resultado booleano. • Conmutativo. Se dice que un operador binario " º " es conmutativo si A º B = B º A para todos los posibles valores de A y B. • Asociativo. Se dice que un operador binario " º " es asociativo si (A º B) º C = A º (B º C) para todos los valores booleanos A, B, y C. • Distributivo. Dos operadores binarios " º " y " % " son distributivos si A º (B % C) = (A º B) % (A º C) para todos los valores booleanos A, B, y C. • Identidad. Un valor booleano I se dice que es un elemento de identidad con respecto a un operador binario " º " si A º I = A. • Inverso. Un valor booleano I es un elemento inverso con respecto a un operador booleano " º " si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de A. Para nuestros propósitos basaremos el álgebra booleana en el siguiente juego de operadores y valores: - Los dos posibles valores en el sistema booleano son cero y uno, a menudo llamaremos a éstos valores respectivamente como falso y verdadero. - El símbolo • representa la operación lógica AND. Cuando se utilicen nombres de variables de una sola letra se eliminará el símbolo •, por lo tanto AB representa la operación lógica AND entre las variables A y B, a esto también le llamamos el producto entre A y B. - El símbolo "+" representa la operación lógica OR, decimos que A+B es la operación lógica OR entre A y B, también llamada la suma de A y B. - El complemento lógico, negación ó NOT es un operador unitario, en éste texto utilizaremos el símbolo " ' " para denotar la negación lógica, por ejemplo, A' denota la operación lógica NOT de A. - Si varios operadores diferentes aparecen en una sola expresión booleana, el resultado de la expresión depende de la procedencia de los operadores, la cual es de mayor a menor, paréntesis, operador lógico NOT, operador lógico AND y operador lógico OR. Tanto el operador lógico AND como el OR son asociativos por la izquierda. Si dos operadores con la misma procedencia están adyacentes, entonces se evalúan de izquierda a derecha. El operador lógico NOT es asociativo por la derecha. Utilizaremos además los siguientes postulados: • P1 El álgebra booleana es cerrada bajo las operaciones AND, OR y NOT • P2 El elemento de identidad con respecto a • es uno y con respecto a + es cero. No existe elemento de identidad para el operador NOT • P3 Los operadores • y + son conmutativos. • P4 • y + son distributivos uno con respecto al otro, esto es, A• (B+C) = (A•B)+(A•C) y A+ (B•C) = (A+B) •(A+C). • P5 Para cada valor A existe un valor A' tal que A•A' = 0 y A+A' = 1. Éste valor es el complemento lógico de A. • P6 • y + son ambos asociativos, ésto es, (AB) C = A (BC) y (A+B)+C = A+ (B+C). Es posible probar todos los teoremas del álgebra booleana utilizando éstos postulados, además es buena idea familiarizarse con algunos de los teoremas más importantes de los cuales podemos mencionar los siguientes: • Teorema 1: A + A = A • Teorema 2: A • A = A • Teorema 3: A + 0 = A • Teorema 4: A • 1 = A • Teorema 5: A • 0 = 0 • Teorema 6: A + 1 = 1 • Teorema 7: (A + B)' = A' • B' • Teorema 8: (A • B)' = A' + B' • Teorema 9: A + A • B = A • Teorema 10: A • (A + B) = A • Teorema 11: A + A'B = A + B • Teorema 12: A' • (A + B') = A'B' • Teorema 13: AB + AB' = A • Teorema 14: (A' + B') • (A' + B) = A' • Teorema 15: A + A' = 1 • Teorema 16: A • A' = 0 Los teoremas siete y ocho son conocidos como Teoremas de DeMorgan en honor al matemático que los descubrió. Características: Un álgebra de Boole es un conjunto en el que destacan las siguientes características: 1- Se han definido dos funciones binarias (que necesitan dos parámetros) que llamaremos aditiva (que representaremos por x + y) y multiplicativa (que representaremos por xy) y una función monaria (de un solo parámetro) que representaremos por x'. 2- Se han definido dos elementos (que designaremos por 0 y 1) Y 3- Tiene las siguientes propiedades: • Conmutativa respecto a la primera función: x + y = y + x Conmutativa respecto a la segunda función: xy = yx Asociativa respecto a la primera función: (x + y) + z = x + (y +z) Asociativa respecto a la segunda función: (xy)z = x(yz) Distributiva respecto a la primera función: (x +y)z = xz + yz Distributiva respecto a la segunda función: (xy) + z = (x + z)( y + z) Identidad respecto a la primera función: x + 0 = x Identidad respecto a la segunda función: x1 = x Complemento respecto a la primera función: x + x' = 1 Complemento respecto a la segunda función: xx' = 0 Propiedades Del Álgebra De Boole 1. Idempotente respecto a la primera función: x + x = x Idempotente respecto a la segunda función: x x = x Maximalidad del 1: x + 1 = 1 Minimalidad del 0: x0 = 0 Involución: x'' = x Inmersión respecto a la primera función: x + (xy) = x Inmersión respecto a la segunda función: x(x + y) = x Ley de Morgan respecto a la primera función: (x + y)' = x'y' Ley de Morgan respecto a la segunda función: (xy)' = x' + y' Función Booleana Una función booleana es una aplicación de A x A x A x....A en A, siendo A un conjunto cuyos elementos son 0 y 1 y tiene estructura de álgebra de Boole. Supongamos que cuatro amigos deciden ir al cine si lo quiere la mayoría. Cada uno puede votar si o no. Representemos el voto de cada uno por xi. La función devolverá sí (1) cuando el numero de votos afirmativos sea 3 y en caso contrario devolverá 0. Si x1 vota 1, x2 vota 0, x3 vota 0 y x4 vota 1 la función booleana devolverá 0. Producto mínimo (es el número posible de casos) es un producto en el que aparecen todas las variables o sus negaciones. El número posible de casos es 2n. Siguiendo con el ejemplo anterior. Asignamos las letras A, B, C y D a los amigos. Los posibles casos son: Votos Resultado ABCD 1111 1 1110 1 1101 1 1100 0 1011 1 1010 0 1001 0 1000 0 0111 1 0110 0 0101 0 0100 0 0011 0 0010 0 0001 0 0000 0 Las funciones booleanas se pueden representar como la suma de productos mínimos (minterms) iguales a 1. En nuestro ejemplo la función booleana será: f(A, B, C, D) = ABCD + ABCD' + ABC'D + AB'CD + A'BCD Diagramas De Karnaugh Los diagramas de Karnaugh se utilizan para simplificar las funciones booleanas. Se construye una tabla con las variables y sus valores posibles y se agrupan los 1 adyacentes, siempre que el número de 1 sea potencia de 2. En esta página tienes un programa para minimización de funciones booleanas mediante mapas de Karnaugh 4. Álgebra Booleana y circuitos electrónicos La relación que existe entre la lógica booleana y los sistemas de cómputo es fuerte, de hecho se da una relación uno a uno entre las funciones booleanas y los circuitos electrónicos de compuertas digitales. Para cada función booleana es posible diseñar un circuito electrónico y viceversa, como las funciones booleanas solo requieren de los operadores AND, OR y NOT podemos construir nuestros circuitos utilizando exclusivamente éstos operadores utilizando las compuertas lógicas homónimas Un hecho interesante es que es posible implementar cualquier circuito electrónico utilizando una sola compuerta, ésta es la compuerta NAND Para probar que podemos construir cualquier función booleana utilizando sólo compuertas NAND, necesitamos demostrar cómo construir un inversor (NOT), una compuerta AND y una compuerta OR a partir de una compuerta NAND, ya que como se dijo, es posible implementar cualquier función booleana utilizando sólo los operadores booleanos AND, OR y NOT. Para construir un inversor simplemente conectamos juntas las dos entradas de una compuerta NAND. Una vez que tenemos un inversor, construir una compuerta AND es fácil, sólo invertimos la salida de una compuerta NAND, después de todo, NOT ( NOT (A AND B)) es equivalente a A AND B. Por supuesto, se requieren dos compuertas NAND para construir una sola compuerta AND, nadie ha dicho que los circuitos implementados sólo utilizando compuertas NAND sean lo óptimo, solo se ha dicho que es posible hacerlo. La otra compuerta que necesitamos sintetizar es la compuerta lógica OR, ésto es sencillo si utilizamos los teoremas de DeMorgan, que en síntesis se logra en tres pasos, primero se reemplazan todos los "•" por "+" después se invierte cada literal y por último se niega la totalidad de la expresión: A OR B A AND B.......................Primer paso para aplicar el teorema de DeMorgan A' AND B'.....................Segundo paso para aplicar el teorema de DeMorgan (A' AND B')'..................Tercer paso para aplicar el teorema de DeMorgan (A' AND B')' = A' NAND B'.....Definición de OR utilizando NAND Si se tiene la necesidad de construir diferentes compuertas de la manera descrita, bien hay dos buenas razones, la primera es que las compuertas NAND son las más económicas y en segundo lugar es preferible construir circuitos complejos utilizando los mismos bloques básicos. Observe que es posible construir cualquier circuito lógico utilizando sólo compuertas de tipo NOR (NOR = NOT(A OR B)). La correspondencia entre la lógica NAND y la NOR es ortogonal entre la correspondencia de sus formas canónicas. Mientras que la lógica NOR es útil en muchos circuitos, la mayoría de los diseñadores utilizan lógica NAND. 5. Circuitos Combinacionales Un circuito combinacional es un sistema que contiene operaciones booleanas básicas (AND, OR, NOT), algunas entradas y un juego de salidas, como cada salida corresponde a una función lógica individual, un circuito combinacional a menudo implementa varias funciones booleanas diferentes, es muy importante recordar éste echo, cada salida representa una función booleana diferente. Un ejemplo común de un circuito combinacional es el decodificador de siete segmentos, se trata de un circuito que acepta cuatro entradas y determina cuál de los siete segmentos se deben iluminar para representar la respectiva entrada, de acuerdo con lo dicho en el párrafo anterior, se deben implementar siete funciones de salida diferentes, una para cada segmento. Las cuatro entradas para cada una de éstas funciones booleanas son los cuatro bits de un número binario en el rango de 0 a 9. Sea D el bit de alto orden de éste número y A el bit de bajo orden, cada función lógica debe producir un uno (para el segmento encendido) para una entrada dada si tal segmento en particular debe ser iluminado, por ejemplo, el segmento e debe iluminarse para los valores 0000 0010, 0110 y 1000. En la siguiente tabla se puede ver qué segmentos deben iluminarse de acuerdo al valor de entrada, tenga en cuenta que sólo se están representando valores en el rango de 0 a 9, los decodificadores para las pantallas de siete segmentos comerciales tienen capacidad para desplegar valores adicionales que corresponden a las letras A a la F para representaciones hexadecimales, sin embargo la mecánica para iluminar los respectivos segmentos es similar a la aquí representada para los valores numéricos. 0 a b c d e f 1 b c 2 a b d e g 3 a b c d g 4 b c f g 5 a c d f g 6 c d e f g 7 a b c 8 a b c d e f g 9 a b c f g Los circuitos combinacionales son la base de muchos componentes en un sistema de cómputo básico, se puede construir circuitos para sumar, restar, comparar, multiplicar, dividir y muchas otras aplicaciones más. Circuitos Secuenciales Un problema con la lógica secuencial es su falta de "memoria". En teoría, todas las funciones de salida en un circuito combinacional dependen del estado actual de los valores de entrada, cualquier cambio en los valores de entrada se refleja (después de un intervalo de tiempo llamado retardo de propagación) en las salidas. Desafortunadamente las computadoras requieren de la habilidad para "recordar" el resultado de cálculos pasados. Éste es el dominio de la lógica secuencial. Una celda de memoria es un circuito electrónico que recuerda un valor de entrada después que dicho valor ha desaparecido. La unidad de memoria más básica es el flip-flop Set/Reset. Aunque recordar un bit sencillo es importante, la mayoría de los sistemas de cómputo requieren recordar un grupo de bits, ésto se logra combinando varios flip-flop en paralelo, una conexión de éste tipo recibe el nombre de registro. A partir de aquí es posible implementar diferentes circuitos como registros de corrimiento y contadores, éstos últimos también los conocemos como circuitos de reloj. Con los elementos mencionados es posible construir un microprocesador completo. 6. Relación entre la lógica combinacional y secuencial con la programación En ésta lección hemos dado una repasada muy básica a los elementos que forman la base de los modernos sistemas de cómputo, en la sección dedicada al diseño electrónico estudiaremos a profundidad los conceptos aquí presentados, pero para aquellos que están más interesados en el aspecto programático podemos decir que con los elementos vistos en ésta lección es posible implementar máquinas de estado, sin embargo la moraleja de ésta lección es muy importante: cualquier algoritmo que podamos implementar en software, lo podemos a su vez implementar directamente en hardware. Ésto sugiere que la lógica booleana es la base computacional en los modernos sistemas de cómputo actuales. Cualquier programa que Usted escriba, independientemente del lenguaje que utilice, sea éste de alto ó bajo nivel, se puede especificar como una secuencia de ecuaciones booleanas. Un hecho igualmente interesante es el punto de vista opuesto, es posible implementar cualquier función de hardware directamente en software, en la actualidad ésta es la función principal del lenguaje ensamblador y otros con capacidad de trabajar directamente en hardware, como el C y el C++. Las consecuencias de éste fenómeno apenas se están explotando, se infiere la existencia de un futuro muy prometedor para el profesional de la programación, especialmente aquellos dedicados a los sistemas incrustados (embedded systems), los microcontroladores y los profesionales dedicados a la Programación Orientada a Objetos. Para tener éxito en éstos campos de la investigación es fundamental comprender las funciones booleanas y la manera de implementarlas en software. Aún y cuando Usted no desee trabajar en hardware, es importante conocer las funciones booleanas ya que muchos lenguajes de alto nivel procesan expresiones booleanas, como es el caso de los enunciados if-then ó los bucles while. 7. Los Teoremas Básicos Del Algebra Booleana Los Teoremas Básicos del álgebra Booleana son: TEOREMA 1 Ley Distributiva A (B+C) = AB+AC A B C B+C AB AC AB+AC A (B+C) 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 TEOREMA 2 A+A = A AA = A A A A+A 0 0 0 1 1 1 A A AA 0 0 0 1 1 1 TEOREMA 3 Redundancia A+AB = A A B AB X 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 A (A+B) = A A B A+B X 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 TEOREMA 4 0+A = A Equivalente a una compuerta OR con una de sus terminales conectada a tierra A B=0 X 0 0 0 1 0 1 1A = A Equivalente a una compuerta AND con una de sus terminales conectada a 1 A B=1 X 0 1 0 1 1 1 1+A = 1 A B=1 X 0 1 1 1 1 1 0A = 0 A B=0 X 0 0 0 1 0 0 8. Bibliografía • Matemática discreta Kolmant • http://es.software.yahoo.com/fot/ftxt/karmap.html • http://www.terra.es/personal/jftjft/ algebra/boole/algboole.htm • http://www.terra.es/personal/jftjft/algebra/ boole/introduccion.htm • http://es.dir.yahoo.com/ciencia_y_tecnologia/ matematicas/algebra/algebra_de_boole/ • http://es.dir.yahoo.com/ciencia_y_tecnologia/ matematicas/algebra/algebra_de_boole • http://www.conocimientosweb.net/portal/directorio • http://www.zabalnet.com/intro/cursos/03_algebra.htm • http://www.inf.ufsc.br/ine5365/algboole.html ÁLGEBRA DE BOOLE. El álgebra de Boole se llama así debido a George Boole, quien la desarrolló a mediados del siglo XIX. El álgebra de Boole denominada también álgebra de la lógica, permite prescindir de la intuición y simplificar deductivamente afirmaciones lógicas que son todavía más complejos. El objetivo principal de este tema es llegar a manejar los postulados y teoremas del álgebra de Boole como herramienta básica en el análisis y síntesis de circuitos digitales. DEFINICIONES 1. Se establecen los conceptos fundamentales (símbolos o términos no definidos). 2. Se define un conjunto de postulados que forman la base del álgebra. 3. Se constituyen los teoremas fundamentales del álgebra a partir de los postulados. A su vez, las exigencias y condiciones que deben reunir los postulados son: 1. Los postulados deben ser coherentes o consistentes para que una álgebra definida pueda desarrollarse por deducciones lógicas. En caso contrario, el sistema resulta contradictorio. 2. Los postulados deben ser independientes; es decir irreductibles recíprocamente (libre de reducciones) 3. Los postulados deben ser tan simples en su enunciado como sea posible; es decir, no separables en dos o más partes. 1.2 POSTULADOS. P.1. Existe un conjunto M de elementos sujetos a una relación de equivalencia denotada por el signo = que satisfacen el principio se sustitución. P.2.a. Para toda (A, B) en M, A + B es una operación binaria (suma lógica) denotada por el signo +, tal que: (A + B) está en M Es decir, el conjunto M es cerrado a esta operación. P.2.b. Para toda (A, B) en M, A . B es una operación binaria (producto lógico) denotada por el signo ., tal que: (A . B) está en M Es decir, el conjunto M es cerrado a esta operación. P.3.a. Existe un elemento 0 en M, tal que: A + 0 = A para toda A en M. P.3.b. Existe un elemento 1 en M, tal que: A . 1 = A para toda A en M. P.4.a. Para toda (A, B) en M: A + B = B + A Se satisface la propiedad conmutativa P.4.b. Para toda (A, B) en M: A . B = B . A Se satisface la propiedad conmutativa P.5.a. Para toda (A, B, C) en M: A + (B . C) = (A + B) . (A + C) Ley distributiva de la suma sobre el producto P.5.b. Para toda (A, B, C) en M: A . (B + C) = (A . B) + (A . C) Ley distributiva del producto sobre la suma P.6.a. Para todo elemento A en M, existe un elemento A', tal que: A + A' = 1 P.6.b. Para todo elemento A en M, existe un elemento A', tal que: A . A' = 0 P.7. Existen por lo menos (A, B) en M, tal que: A es diferente de B Se habrá observado cierta similitud entre estos postulados y los del álgebra ordinaria. Nótese sin embargo, que la primera ley distributiva P.5.a. no es válida en el álgebra ordinaria y que tampoco existe ningún elemento A' en dicha álgebra. También se notará que los postulados se presentaron por pares. Una observación más detenida, muestra que existe una dualidad entre los símbolos + y. Lo mismo que entre los dígitos 1 y 0. Si el símbolo + se sustituye por . y . por +, así como todos los UNOS se sustituyen por CEROS y los CEROS por UNOS, en cualquiera de los postulados de cada par, el resultado es el otro postulado. A causa de esta dualidad fundamental, cada teorema que se presenta tendrá su dual que se obtendrá efectuando la sustitución mencionada; por tanto, la demostración de un teorema implica la validez de su teorema dual. 1.3 TEOREMAS FUNDAMENTALES. A continuación se presentan los teoremas principales del álgebra de Boole, los cuales son la base del trabajo subsecuente. Es posible demostrar dichos teoremas por cualquiera de los siguientes métodos: 1. Algebraicamente (empleando postulados y teoremas ya demostrados). 2. Gráficamente (por medio de los diagramas de Venn). 3. Por inducción perfecta (empleando tablas de verdad). Aquí se empleará el método algebraico pues se considera la mejor manera de iniciarse en esta álgebra, además de que sólo se demostrarán los teoremas primales, pero aplicando las reglas de dualidad mencionadas anteriormente, se podrá obtener la parte dual. T.1. Teoremas sobre la UNICIDAD. 1.a. El elemento 0 es único. 1.b. El elemento 1 es único. Demostración de 1.a. Por contradicción, supóngase que 0 y 01 son neutros aditivos, por lo que deben satisfacer al postulado P.3.a, es decir: A + 0 = A y A1 + 01 = A1 Si A1 = 0 y A = 01 y como 0 es neutro, por suposición, entonces: 01 + 0 = 0 (1) Además como 01 es neutro, por suposición, entonces: 0 + 01 = 0 (2) De (1) y (2) se tiene: 01 = 0 con lo que se demuestra el teorema. T.2. Teoremas sobre la EQUIPOTENCIA. 2.a. A + A = A 2.b. A . A = A Demostración de 2.a. A + A = (A + A) . 1 (P.3.b.) A + A = (A + A) . (A + A') (P.6.a.) A + A = A + (A . A') (P.5.a) A + A = A + 0 (P.6.b.) A + A = A (P.3.a.) T.3. 3.a. A + 1 = 1 3.b. A . 0 = 0 Demostración de 3.a. A + 1 = 1 . (A + 1) (P.3.b.) A + 1 = (A + A') . (A + 1) (P.6.a) A + 1 = A + (A' . 1) (P.5.a) A + 1 = A + A' (P.3.b.) A + 1 = 1 (P.6.a.) T.4. Teoremas de ABSORCIÓN. 4.a. A + (A . B) = A 4.b. A . (A + B) = A Demostración de 4.a. A + (A . B) = (A . 1) + (A . B) (P.3.b.) A + (A . B) = A . (1 + B) (P.5.b.) A + (A . B) = A . 1 (T.3.a.) A + (A . B) = A (P.3.b.) T.5. El elemento A' es único. Demostración Por contradicción, supóngase que existen dos elementos distintos A'1 y A'2, tales que satisfacen los postulados P.6.a. y P.6.b., es decir: A + A'1 = 1 y A + A'2 = 1 A . A'1 = 0 y A . A'2 = 0 Entonces: A'2 = 1 . A'2 (P.3.b) A'2 = (A + A'1) . A'2 (por suposición) A'2 = (A . A'2 ) + (A'1 . A'2) (P.5.b.) A'2 = 0 + (A'1 . A'2) (por suposición) A'2 = (A . A'1) + (A'1 . A'2) (por suposición) A'2 = (A + A'2) . A'1 (P.5.b) A'2 = 1 . A'1 (por suposición) A'2 = A'1 (P.3.b.) T.6. Para toda A en M, A = A'' Demostración Sea A'' = X, por tanto: A' + X = 1 y A' , X = 0 (P.6.) Pero: A' + A = 1 y A' . A = 0 (P.6.) Así que tanto X como A' satisfacen el postulado P.6. como el complemento de A, por tanto: X = A, es decir, A'' = A T.7. Teoremas de ABSORCIÓN 7.a. A . [(A + B) + C] = [(A + B) + C] . A = A 7.b. A + [(A . B) . C] = [(A . B) . C] = A Demostración de 7.a. A . [(A + B) + C] = A . (A + B) + (A . C) (P.5.b.) A . [(A + B) + C] = (A . A) + (A . B) + (A . C) (P.5.b.) A . [(A + B) + C] = A + (A . B) + (A . C) (T.2.) A . [(A + B) + C] = A . (1 + B + C) (P.5.b.) A . [(A + B) + C] = A . 1 (T.3.) A . [(A + B) + C] = A (P.3.b.) T.8. Teoremas sobre la ASOCIACIÓN. 8.a. A + (B + C) = (A + B) + C 8.b. A . (B . C) = (A . B) . C Demostración de 8.a. Sea: Z = [(A + B) + C] . [A + (B + C)] Z = {A . [(A + B) + C]} + {(B + C) . [(A + B) + C]} (P.5.b.) Z = A + {(B + C) . [(A + B) + C]} (T.7.) Z = A + {B . [(A + B) + C] + C . [(A + B) + C]} (P.5.b.) Z = A + {B + C . [(A + B) + C]} (T.7.) Z = A + (B + C) (T.7.) (1) Como: Z = [(A + B) + C] . [A + (B + C)] Z = {(A + B) . [A + (B + C)]} + {C . [A + (B + C)]} (P.5.b.) Z = {(A + B) . [A + (B + C)]} + C (T.7.) Z = {A . [A + (B + C)] + B . [A + (B + C)]} + C (P.5.b.) Z = {A . [A + (B + C)] + B} + C (T.7.) Z = (A + B) + C (T.7.) (2) Por consiguiente, de (1) y (2) y por transitividad: Z = A + (B + C) = (A + B) + C = A + B + C T.9. Teoremas sobre la COMPLEMENTACIÓN. 9.a. A + (A' . B) = A + B 9.b. A . (A' + B) = A . B Demostración de 9.a. A + (A' . B) = (A + A') . (A + B) (P.5.a.) A + (A' . B) = 1 . (A + B) (P.6.a.) A + (A' . B) = A + B (P.3.b.) T.10. Teoremas de DeMORGAN. 10. a. (A + B)'' = A' . B' 10.b. (A . B)' = A' + B' Demostración de 10.a. Primera parte: (A + B) + (A' . B') = [(A + B) + A'] . [(A + B) + B'] (P.5.a.) (A + B) + (A' . B') = [A' + (A + B)] . [(A + B) + B'] (P.4.a.) (A + B) + (A' . B') = [(A' + A) + B] . [A + (B + B')] (T.8.) (A + B) + (A' . B') = (1 + B) . (A + 1) (P.6.a.) (A + B) + (A' . B') = 1 . 1 (T.3.a.) (A + B) + (A' . B') = 1 (T.2.b.) (1) Segunda parte: (A + B) . (A' . B') = (A' . B') . (A + B) (P.4.b.) (A + B) . (A' . B') = (A' . B' . A) + (A' . B' . B) (P.5.b.) (A + B) . (A' . B') = 0 + 0 (P.6.b.) (A + B) . (A' . B') = 0 (T.2.a.) (2) Por tanto, de (1) y (2) se concluye que: (A + B)' = A' . B' T.11. 11.a. (A . B) + (A' . C) + (B . C) = (A . B) + (A' . C) 11.b. (A + B) . (A' + C) . (B + C) = (A + B) . (A' + C) Demostración de 11.a. (A . B) + (A' . C) + (B . C) = (A . B . 1) + (A' . 1 . C) + (1 . B . C) = (P.3.b.) = [A . B . (C + C')] + [A' . (B + B') . C] + [(A + A') . B . C ] = (P.6.b.) = (A B C) + (A B C') + ( A' B C) + (A' B' C) + (A B C) + (A' B C) = (P.5.b.) = (A B C) + (A B C') + ( A' B C) + (A' B' C) = (T.2.) = [A . B . (C + C')] + [A' . C . (B + B')] = (P.5.a.) = (A . B . 1) + (A' . C . 1) (P.6.a.) (A . B) + (A' . C) + (B . C) = (A . B) + (A' . C) (P.3.b.) T.12. 12.a. (A . B) + (A . B' . C) = (A . B) + (A . C) 12.b. (A + B) . (A + B' + C) = (A + B) . (A + C) Demostración de 12.a. (A . B) + (A . B' . C) = A . [B + (B' . C)] (P.5.b.) (A . B) + (A . B' . C) = A . [(B + B') . (B + C)] = A . (B + C) (T.9.a.) (A . B) + (A . B' . C) = (A . B) + (A . C) (P.5.b.) T.13. 13.a. (A . B) + (A . B') = A 13.b. (A + B) . (A + B') = A Demostración de 13.a. (A . B) + (A . B') = A . (B + B') (P.5.b.) (A . B) + (A . B') = A . 1 (P.6.b.) (A . B) + (A . B') = A Para fácil referencia, los teoremas se resumen en la siguiente tabla: TEOREMA PRIMAL TEOREMA DUAL T.1.a. 0 es único T.2.a A + A = A T.3.a. A + 1 = A T.4.a. A + (A . B) = A T.5. A' es único T.6. A = A'' T.7.a. A . [(A + B) + C] = [(A + B) + C] . A = A T.8.a. A + (B + C) = (A + B) + C T.9.a. A + (A' . B) = A + B T.10.a. (A + B)' = A' . B' T.11.a. (A . B) + (A' . C) + (B . C) = (A . B) + (A' .C ) T.12.a. (A . B) + (A . B' . C) = (A . B) + (A . C) T.13.a. (A . B) + (A . B') = A T.1.b. 1 es único T.2.b. A . A = A T.3.b. A . 0 = 0 T.4.b. A . (A + B) = A No tiene No tiene T.7.b. A + [(A . B) . C] = [(A . B) . C] + A = A T.8.b. A . (B . C) = (A . B) . C T.9.b. A . (A' + B) = A . B T.10.b. (A . B)' = A' + B' T.11.b. (A + B)(A' + C)(B + C) = (A + B)(A' + C) T.12.b. (A + B)(A + B' + C) = (A + B) (A + C) T.13.b. (A + B) . (A + B') = A 1.4 COMPUERTAS LÓGICAS Un computador digital, como su nombre lo indica, es un sistema digital que realiza diversas operaciones de cómputo. La palabra Digital implica que la información que se representa en el computador por medio de variables que toman un número limitado de valoresViscretos o cuantizados. Estos valores son procesados íntemamente por componentes que pueden mantener un número limitado de estados discretos. Los dígitos decimales por ejemplo, proporcionan 10 valores discretos ( 0 .. 9 ). Como sabemos en la práctica, los computadores funcionan más confiablemente si sólo utilizan dos estados equiprobables. Debido al hecho que los componentes electrónicos atienden a dos estados ( encendido / apagado ) y que la lógica humana tiende a ser binaria ( esto es, cierto o falsa, si o no ) se utiliza el sistema binario y se dice que son binarias. Los computadores digitales utilizan el sistema de números binarios, que tiene dos dígitos 0 y 1. Un dígito binario se denomina un bit. ' La infonnación está representada en los computadores digitales en grupos de bits. Utilizando diversas técnicas de codificación los grupos de bits pueden hacerse que representen no solamente números binarios sino también otros símbolos discretos cualesquiera, tales como dígitos decimales o letras de alfabeto. Utilizando arreglos binarios y diversas técnicas de codificación, los dígitos binarios o grupos de bits pueden utilizarse para desarrollar conjuntos completos de instrucciones para realizar diversos tipos de cálculos. La información binaria se representa en un sistema digital por cantidades físicas denominadas señales, Las señales eléctricas tales como voltajes existen a través del sistema digital en cualquiera de dos valores reconocibles y representan un a variable binaria igual a 1 o 0. Por ejemplo, un sistema digital particular puede emplear una señal de 3 [volts 1 para representar el binario "I" y 0.5 [volts 1 para el binario "0". La siguiente ilustración muestra un ejemplo de una señal binaria. Como se muestra en la figura, cada valor binario tiene una desviación aceptable del valor nominal. La región íntermedia entre las dos regiones permitidas se cruza solamente durante la transición de estado. Los terminales de entrada de un circuito digital aceptan señales binarias dentro de las tolerancias permitidas y los circuitos responden en los terminales de salida con señales binarias que caen dentro de las tolerancias permitidas. La lógica binaria tiene que ver con variables binarias y con operaciones que toman un sentido lógico. Es utilizada para escribir, en forma algebraica o tabular. La manipulación y. procesamiento de información binaria. La manipulación de información binaria se hace por circuitos lógico que se denominan Compuertas. Las compuertas son bloques del hardware que producen señales del binario 1 ó 0 cuando se satisfacen los requisitos de entrada lógica. Las diversas compuertas lógicas se encuentran comúnmente en sistemas de computadores digitales. Cada compuerta tiene un símbolo gráfico diferente y su operación puede describirse por medio de una función algebraica. Las relaciones entrada - salida de las variables binarias para cada compuerta pueden representarse en forma tabular en una tabla de verdad. A continuación se detallan los nombres, símbolos, gráficos, funciones algebraicas, y tablas de verdad de ocho compuertas. Compuerta AND: Cada compuerta tiene una o dos variables de entrada designadas por A y B y una salida binaria designada por x. La compuerta AND produce la unión lógica AND: esto es: la salida es 1 si la entrada A y la entrada B están ambas en el binario 1: de otra manera, la salida es 0. Estas condiciones también son especificadas en la tabla de verdad para la compuerta AND. La tabla muestra que la salida x es 1 solamente cuando ambas entradas A y B están en 1 . El símbolo de operación algebraico de la función AND es el mismo que el símbolo de la multiplicación de la aritmética ordinaria (*). Podemos utilizar o un punto entre las variables o concatenar las variables sin ningún símbolo de operación entre ellas. Las compuertas AND pueden tener más de dos entradas y por definición, la salida es 1 si cualquier entrada es 1. Compuerta OR: La compuerta OR produce la función OR inclusiva, esto es, la salida es 1 si la entrada A o la entrada B o ambas entradas son 1; de otra manera, la salida es 0. El símbolo algebraico de la función OR (+), similar a la operación de aritmética de suma. Las compuertas OR pueden tener más de dos entradas y por definición la salida es 1 si cualquier entrada es 1. Compuerta NOT (Inversor): El circuito inversor invierte el sentido lógico de una señal binaria. Produce el NOT,. o función complemento. El símbolo algebraico utilizado para el complemento es una barra sobra el símbolo de la variable binaria. Si la variable binaria posee un valor 0, la compuerta NOT cambia su estado al valor 1 y viceversa. El círculo pequeño en la salida de un símbolo gráfico de un inversor designa un complemento lógico. Es decir cambia los valores binarios 1 a 0 y viceversa. Compuerta Separador: Un símbolo triángulo por sí mismo designa un circuito separador no produce ninguna función lógica particular puesto que el valor binario de la salida es el mismo de la entrada. Este circuito se utiliza simplemente para amplificación de la señal. Por ejemplo, un separador que utiliza i volt para el binario 1 producirá una salida de 3 volt cuando la entrada es 3 volt. Sin embargo, la corriente suministrada en la entrada es mucho más pequeña que la corriente producida en la salida. De ésta manera, un separador puede excitar muchas otras compuertas que requieren una cantidad mayor de corriente que de otra manera no se encontraría en la pequeña cantidad de corriente aplicada a la entrada del separador. Compuerta NAND: Es el complemento de la función AND, como se indica por el símbolo gráfico que consiste en un símbolo gráfico AND seguido por un pequeño círculo. La designación NAND se deriva de la abreviación NOT - AND. Una designación más adecuada habría sido AND invertido puesto que Es la función AND la que se ha invertido. Compuerta NOR: La compuerta NOR es el complemento de la compuerta OR y utiliza un símbolo gráfico OR seguido de un círculo pequeño. Tanto las compuertas NAND como la NOR pueden tener más de dos entradas, y la salida es siempre el complemento de las funciones AND u OR, respectivamente. Compuerta OR exclusivo (XOR): La compuerta OR exclusiva tiene un símbolo gráfico similar a la compuerta OR excepto por una línea adicional curva en el lado de la entrada. La salida de esta compuerta es 1 si cada entrada es 1 pero excluye la combinación cuando las dos entradas son 1. La función OR exclusivo tiene su propio símbolo gráfico o puede expresarse en términos de operaciones complementarias AND, OR . Compuerta NOR exclusivo (XOR): El NOR exclusivo como se indica por el círculo pequeño en el símbolo gráfico. La salida de ésta compuerta es 1 solamente si ambas entradas son tienen el mismo valor binario. Nosotros nos referiremos a la función NOR exclusivo como la función de equivalencia. Puesto que las funciones OR exclusivo y funciones de equivalencia no son siempre el complemento la una de la otra. Un nombre más adecuado para la operación OR exclusivo sería la de una función impar; esto es, la salida es 1 si un número impar de entrada es 1. Así en una función OR (impar) exclusiva de tres entradas, la salida es 1 si solamente la entrada es 1 o si todas las entradas son 1. La función de equivalencia es una función par; esto es, su salida es 1 si un número par de entradas es 0. Para un función de equivalencia de tres entradas, la salida es 1 si ninauna de las entradas son 0 ( todas las entradas son 1 ) o si dos de las entradas son 0 ( una entrada es 1 Una investigación cuidadosa revelará que el OR exclusivo y las funciones de equivalencia son el complemento la una de la otra cuando las compuertas tienen un número par de entradas, pero las dos funciones son iguales cuando el número de entradas es impar. Estas dos compuertas están comúnmente disponibles con dos entradas y solamente en forma rara se encuentran con tres o más entradas. Retornemos el teorema De Morgan: El teorema De Morgan es muy importante al tratar compuertas NOR y NAND. Expresa que una compuerta NOR que realiza la función (x + y)' es equivalente a la expresión función xy' . Similarmente, una función NAND puede ser expresada bien sea por (xy)' o por x' + y' por esta razón, las compuertas NOR y NAND tienen dos símbolos gráficos distintos como se muestra en la figura: En vez de representar una cornpuerta NOR por el símbolo gráfico OR seguido por un círculo, nosotros podemos representarla por un símbolo gráfico AND precedido por círculos en todas las entrada. El inversor AND para la compuerta NOR proviene M teorema De Morgan y de la convención de que los círculos pequeños denotan complementación. Similarmente la compuertaNAND también posee dos símbolos gráficos. Para ver cómo se utiliza la manipulación del álgebra Booleana para simplificar circuitos digitales considere el diagrama lógico de la siguiente figura. La salida de la primera compuerta NAND es, por el teorema De Morgan, (AB)' = A' + B' . La salida del circuito es la operación NAND de este término y B' . X = [( A' + B ) * B' ] ' Utilizando el teorema De Morgan dos veces, obtenemos: X = (A' + B)' + B = AB' + B Note que el teorema De Morgan ha sido aplicado tres veces ( para demostrar su utilización ) pero podría ser aplicado solamente una vez de la siguiente manera: X = [ ( AB' )*B']' = AB' + B La expresión para x puede simplificarse por aplicación de las relaciones mencionadas anteriormente X = AB'+ B = B + AB' = ( B + A) ( B + B') = (B+A)* 1 = B + A = A + B El resultado final produce una función OR y puede ser implementado con una sola compuerta OR como se muestra en la figura parte (b). Uno Puede demostrar que dos circuitos producen relaciones binarias idénticas Entrada - Salida simplemente obteniendo la tabla de verdad para cada uno de ellos.