Tema 8# Expresiones de conmutación

        Un símbolo x es una variable booleana si representa a cualquier elemento de un conjunto B sobre el que se ha definido un Algebra de Boole. Una función booleana o de conmutación es una expresión algebraica de variables booleanas con las operaciones +, * y complemento

Literal: 

        Es toda ocurrencia de una variable, ya sea complementada o sin complementar, en una expresión de conmutación.

Por ejemplo: En la expresión de conmutación:

A · B + C · A + D + B · 1

A, B, C y D son Variables.

A, B, C, A, D y B son Literales.

1 es una Constante.

Dual:

        Esta expresión se obtiene, intercambiando las operaciones AND por OR (y viceversa), e intercambiando las constantes 0 por 1 y 1 por 0 en la expresión de conmutación.

Por ejemplo: Para la expresión de conmutación:

(A · B) + (C · D) + 0

La Expresión Dual es:

(A + B) · (C + D) · 1

Tema 7# Teoremas y postulados del Álgebra Boole

Postulados       

  

            Un álgebra de Boole es toda clase o conjunto de elementos que pueden tomar dos valores perfectamente diferenciados, que designaremos por 0 y 1 y que están relacionados por dos operaciones binarias denominadas suma (+) y producto (.) (la operación producto se indica en general simplemente mediante la ausencia de símbolo entre dos variables) lógicos que cumplen los siguientes postulados:

 

a) Ambas operaciones son conmutativas, es decir, si a y b son elementos del álgebra, se verifica:

 

a + b = b + a                    a . b = b . a

 

b) Dentro del álgebra existen dos elementos neutros, el 0 y el 1, que cumplen la propiedad de identidad con respecto a cada una de dichas operaciones:

 

0 + a = a                         1 . a = a

 

c) Cada operación es distributiva con respecto a la otra:

 

a . (b + c) = a . b + a . c                       a + (b . c) = (a + b) . (a + c)

 

d) Para cada elemento, a, del álgebra existe un elemento denominado, ā  , tal que:

 

a + ā = 1                          a . ā = 0

 

    Este postulado define realmente una nueva operación fundamental que es la inversión o complementación de una variable. La variable ā se encuentra siempre en un estado binario contrario al de a.

 

    La primera ecuación expresa la imposibilidad de que a y ā tomen el valor lógico cero al mismo tiempo y la segunda ecuación indica que nunca pueden tener el valor lógico uno al mismo tiempo.

 

    De lo explicado anteriormente se deduce que el álgebra de Boole es un ente matemático. En realidad, son físicamente varios los conjuntos que poseen dos operaciones binarias que cumplen los postulados desarrollados. Ejemplos de estos conjuntos son el álgebra de las proposiciones formales y el álgebra de la conmutación formad también por elementos que pueden tomar dos estados perfectamente diferenciados.

 

    Los primeros circuitos de conmutación o lógicos utilizados han sido los contactos, y aunque poco a poco han sido desplazados por los circuitos electrónicos, pueden ser empleados para memorizar más fácilmente las leyes del álgebra de Boole antes expresadas y los teoremas que desarrollaremos seguidamente.

 

    La operación suma se asimila a la conexión en paralelo de contactos y la operación producto a la conexión en serie. El inverso de un contacto es otro cuyo estado es siempre opuesto del primero, es decir está cerrado cuando aquel está abierto y viceversa. El elemento 0 es un contacto que está siempre abierto y el elemento 1 un contacto que está siempre cerrado. Además se considera una función de transmisión entre los dos terminales de un circuito de contactos, que toma el valor 1, cuando existe un camino para la circulación de corriente entre ellos (cortocircuito) y el valor 0 al no existir dicho camino (Circuito abierto).

Teoremas

 

        Basándose en los postulados anteriores se deducen los teoremas que expondremos seguidamente. Su demostración se puede realizar algebraicamente mediante la llamada tabla de verdad. La tabla de verdad de una expresión algebraica binaria representa los valores que dicha expresión puede tomar para cada combinación, de estados de las variables que forman parte de la misma. Dos expresiones algebraicas que tienen la misma tabla de verdad son equivalentes.

Teorema 1: 

        Cada identidad deducida de los anteriores postulados del álgebra de Boole permanece válida si la operación + y . y los elementos 0 y 1 se intercambian entre si.

        Este principio, llamado de dualidad, se deduce inmediatamente de la simetría de los cuatro postulados con respecto a ambas operaciones y ambos elementos neutros.

Teorema 2: 

        Para cada elemento a de un álgebra de Boole se verifica:

                             a + 1 = 1                          a . 0 = 0

Teorema 3:

        Para cada elemento a de un álgebra de Boole se verifica:

                            a + a = a                          a . a = a

Teorema 4: 

        Para cada par de elementos de un álgebra de Boole a y b, se verifica:

 

                           a +ab = a                         a . (a + b) = a

        Esta ley se llama de absorción.

Teorema 5: 

        En álgebra de Boole, las operaciones suma y producto son asociativas:

 

                           a + (b + c) = (a + b) + c = a + b + c

                          a . (b . c) = ( a . b) . c = a . b . c 

Teorema 6: 

        Para todo elemento ā de un álgebra de Boole se verifica:

                                                 ā = a

       Estas igualdades se llaman leyes de De Morgan

Tema 6# Reglas del Álgebra de Boole

1- A + 0 = A

2- A + 1 = 1

3- A x 0 = 0

4- A x 1 = A

5- A + A = A

6- A + ̄ A = 1

7- A x A = A

8- A x ̄ A = 0

9- ̄ ̄ A = A

10- A + AB = A

A + AB = AA + AB = A (1 + B) Sacar factor común A

(ley distributiva)

= A ·1 Regla 2: (1 + B) = 1

= A Regla 4: A ·1 = A

11- A + ̄ AB = A + B

A+ ̄ AB = (A + AB)+ ̄ AB Regla 10: A = A + AB

= A + (A + ̄ A) B Sacar factor común

= A + 1 ·B Regla 6: A + ̄ A= 1

= A + B Regla 4: A ·1 = A

12- (A + B) (A + C) = A + BC

(A + B)(A + C) = AA + AC + AB + BC   Ley distributiva

= A + AC + AB + BC          Regla 7: AA = A

= A + BC                Regla 10: A + AB = A (x2 veces)

Tema #5 Simplificación de funciones Booleanas

         Al usar los teoremas y leyes booleanas, podemos simplificar las expresiones booleanas, mediante las cuales podemos reducir el número requerido de compuertas lógicas a implementar. Podemos simplificar la función Boolean utilizando dos métodos:

• El Método de Mapa Karnaugh. 

        Un mapa de Karnaugh (también conocido como tabla de Karnaugh o diagrama de Veitch, abreviado como Mapa-K o Mapa-KV) es un diagrama utilizado para la simplificación de funciones algebraicas Booleanas. El mapa de Karnaugh fue inventado en 1953 por Maurice Karnaugh, un físico y matemático de los laboratorios Bell.

    Los mapas de Karnaugh reducen la necesidad de hacer cálculos extensos para la simplificación de expresiones booleanas, aprovechando la capacidad del cerebro humano para el reconocimiento de patrones y otras formas de expresión analítica, permitiendo así identificar y eliminar condiciones muy inmensas.

        El mapa de Karnaugh consiste en una representación bidimensional de la tabla de verdad de la función a simplificar. 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. Las variables de la expresión son ordenadas en función de su peso y siguiendo el código Gray, de manera que sólo una de las variables varía entre celdas adyacentes. La transferencia de los términos de la tabla de verdad al mapa de Karnaugh se realiza de forma directa, albergando un 0 ó un 1, dependiendo del valor que toma la función en cada fila. Las tablas de Karnaugh se pueden fácilmente realizar a mano con funciones de hasta 6 variables, para funciones de mayor cantidad de variables es más eficiente el uso de software especializado.

           Al calcular el numero de renglones y columnas debemos tomar en cuenta:

        Normalmente suele representarse como un mapa cuadrado (número de renglones = número de columnas) cuando el número de variables es par (2, 4, 6, 8... etc) y cuando el número de variables es impar el número de renglones igual a la mitad del número de columnas; siguiendo la siguientes fórmulas:

          Cuando el número de variables es par:

                                 

          Cuando el número de variables es impar:

                                                  

                                                   

Ejemplo:

          Dada la siguiente función algebraica booleana representada como el sumatorio de sus minitérminos, y con las variables Booleanas A, B, C, D, la función se puede representar con dos notaciones distintas:

                               

Tabla de Verdad

        Las variables de entrada pueden combinarse de 16 formas diferentes, por lo que el mapa de Karnaugh tendrá 16 celdas, distribuidas en una cuadrícula de 4 × 4. La razón por la cual en las tablas de 4 variables (por ejemplo) hay una transición de una columna rotulada como "01" a otra "11" (en vez de "10" que sería el próximo valor binario) se debe a que es un requisito en la construcción del mapa que en cada nueva columna (de izquierda a derecha) sólo varíe una variable a la vez. Entonces, al "01" le sigue el "11", de tal forma que sólo varía el primer bit, cosa que no ocurriría si se pasará del "01" al "10" (porque cambiarían ambos bits a la vez).

• El Método Algebraico. 

      Para la simplificación por este método no sólo bastará con conocer todas las propiedades y teoremas del álgebra de Boole, además se debe desarrollar una cierta habilidad lógico-matemática que se adquiere fundamentalmente con la experiencia.

            Como ejemplo se simplificará la siguiente función:

                    F = A’C’ + ABC + BC’ + A’B’C + A’BC

            Observando cada uno de los sumando podemos ver que hay factores comunes en los sumandos 2º con 5º y 4º con 5º que conllevan simplificación:

                   F = A’C’ + BC’ + BC(A + A’) + A’C(B + B’)

            Note que el término 5º se ha tomado dos veces, de acuerdo con la propiedad que dice que A + A = A. Aplicando las propiedades del álgebra de Boole (A + A' = 1 y A . 1 = A), queda

                   F = A’C’ + BC’ + BC + A’C

               Repitiendo nuevamente el proceso,

                    F = A’( C’ + C) + B( C’ + C) = A’ + B

            No siempre las funciones son tan fáciles de simplificar como la anterior. El método algebraico, por lo general, no resulta cómodo para los no expertos, a los cuales, una vez simplificada una ecuación le pueden quedar serias dudas de haber conseguido la máxima simplificación.

• Numérico de Quine-McCluskey

        El algoritmo Quine-McCluskey permite la simplificación de funciones lógicas de cualquier número de variables y es el que se utiliza para diseñar aplicaciones informáticas en las que se necesite obtener funciones simplificadas.

              A continuación se indican los pasos a seguir en este método a partir de un ejemplo.

            Se expresa la función a simplificar en su forma canónica de suma de productos.

            Sea la siguiente función a simplificar:

               

            Se forma una tabla con el valor decimal de la combinación, el estado de las variables y el índice (número de unos que contiene el estado de las variables).

        Se agrupan las combinaciones cuyos estados difieren en una sola variable, sustituyéndola por un guion bajo (_). Las combinaciones utilizadas se marcan con un aspa (X). Hay que fijarse en las combinaciones cuya diferencia entre sus respectivos índices es la unidad.

            Se repite el proceso anterior las veces que sean necesarias y se van eliminando estados idénticos.

           

           Se forma una tabla con las combinaciones finales y las no agrupadas. Se toman como filas las combinaciones finales y las no agrupadas y como columnas los valores decimales de dichas combinaciones. Cada celda que contenga el valor decimal de una combinación se marca con un aspa. A continuación nos fijamos en aquellas columnas con una sola aspa; sus combinaciones serán esenciales. Finalmente se toman aquellas combinaciones de los valores decimales no seleccionados, teniendo precaución de no tomar aquellas combinaciones cuyos valores decimales hayan sido ya tomados en otras combinaciones. La función simplificada final viene dada por las combinaciones esenciales y estas últimas.

Tema 4# Leyes y identidades del Álgebra Boole

        El álgebra de Boole son las matemáticas de los sistemas digitales, esta siguen una serie de leyes y reglas, ademas de dos teoremas para poder realizar sus operaciones.

Leyes conmutativas

• Ley conmutativa de la suma:  

        Esta ley nos dice que:

        Establece que no importa el orden en que se apliquen las variables de la operación OR, ya que la suma representa dicha operación.

      Esta nos dice que si a la entrada tenemos las variables A y B en la salida tendremos A+B, eso equivaldría a que si esta al contrario, es decir, si al entrar tenemos B y A en la salida tendremos B+A, lo que nos quiere decir que tanto A+B como B+A representan la misma operación y esta no se vera alterada, por lo que es lo mismo colocar uno como el otro.

• Ley conmutativa de la multiplicación:

        Esta ley nos dice:

        

        Con esto establece que el orden de las variables en las que se aplique la operación de multiplicación o operación AND, no es importante.

        Esta nos dice que si en la entrada tenemos las variables A y B en la salida tendremos A*B, que esto es equivalente a el caso contrario, es decir, si tenemos en la entrada las variables B y A en la salida resultara B*A, por lo que una es equivalente a la otra y no poseerá ninguna alteración la operación.

Leyes asociativas

• Ley asociativa de la suma:

        Esta ley nos dice:

 

        Básicamente nos dice que A mas la agrupación de B+C es exactamente igual a agrupar las variables A+B sumándole C, lo que nos da a entender que es equivalente sumar de una forma a la otra, no importa como asocies los términos en la suma da lo mismo.

        Esta ley establece que la operación OR o la suma a mas de dos variables el resultado es el mismo independientemente en la forma en la que se agrupen los términos.

      En esta representación observamos dos compuertas OR, en la primera esta en la entrada B y C en la salida de estas tenemos B+C este resultado se introduce a la otra compuerta OR junto a la variable A como datos de entra por lo que de salida tendremos A+(B+C), por lo que todo esto es igual o equivalente a realizar las mismas acciones con A+B y C para que nos de en la salida (A+B)+C, con esta ley se demuestra que ambas operaciones son lo mismo.

• Ley asociativa de la multiplicación:

          Esta ley nos dice:

          Nos dice que A por la agrupación de B*C que se multiplica ya de por si entre si misma sera igual a multiplicar primero A*B para luego hacer lo mismo con C, no hay ninguna diferencia entre ambos procedimientos.

        Esta ley establece que la operación AND o la multiplicación se hace a mas de dos variables el resultado es el mismo, independientemente en la forma en la que se agrupen los elementos.

        En esta representación observamos dos compuertas AND, en la primera esta en la entrada B y C en la salida de estas tenemos B*C este resultado se introduce a la otra compuerta AND junto a la variable A como datos de entra por lo que de salida tendremos A*(B*C), por lo que todo esto es igual o equivalente a realizar las mismas acciones con A*B y C para que nos de en la salida (A*B)*C, con esta ley se demuestra que ambas operaciones son lo mismo.(Recordar que en las representaciones las letras unidas son multiplicación no es necesario colocar el símbolo).

Ley distributiva

        Esta ley nos dice:

            Nos dice que A multiplicado por la suma de B+C va a ser igual a suma de A*B y A*C, ya que hay que recordar que el elemento que esta fuera de la agrupación se multiplica por cada uno de los términos que estén dentro del paréntesis.

           Esta ley establece que al aplicar la operación OR o suma a dos o mas variables luego aplicar la operación AND o multiplicación al resultado, es lo mismo o es equivalente a aplicar únicamente la operación AND a cada uno de los sumandos, es muy importante recalcar esto ya que como se esta hablando de sistemas digitales mientras menos puertas lógicas se requieran sera mas eficiente.

            Aquí tomaremos en cuenta que ambos circuitos son equivalentes, analizando el primero se requerirá una puerta OR y una AND, ya que B y C se generaran una salida B+C que se introducirá como dato de entrada en la multiplicación al igual que A que sera quien multiplique este elemento resultante de la puerta anterior, lo que sera equivalente a el lado de la igualdad, es decir, que tenemos una suma de dos multiplicaciones por lo que se requerirán tres puertas lógicas donde tanto A y B como A y C son datos de entrada que proporcionaran una salida A*B y A*C respectivamente que servirán como datos de entrada en la puerta OR donde se sumaran. Aquí pudimos observa que aunque saldrán con el mismo resultado lo  mas conveniente es usar la que requiera menores puertas lógicas para seguir correctamente el álgebra de Boole.

Identidades Útiles

Tema 3# NOT, AND y OR

Leyes Fundamentales

Puertas lógicas

            Una puerta lógica, o compuerta lógica, es un dispositivo electrónico con una función booleana u otras funciones como sumar o restar, incluyen o excluyen según sus propiedades lógicas. 

NOT (Inversor lógico):  

            La puerta lógica NOT realiza la función booleana de inversión o negación de una variable lógica. Una variable lógica (A) a la cual se le aplica la negación se pronuncia como "no A" o "A negada".

            Su tabla de verdad es la siguiente: 

            Donde en este sistema la única salida posible es el inverso del valor es decir, si es 1 la entrada su salida sera 0 y viceversa.

            Su simbología es la siguiente:

            En todo caso la entrada es por la izquierda, la primera tiene forma de rectángulo y es mas usada a procedimientos donde se relacione a la polaridad y el triangulo es la representación mas común, el pequeño circulo es la negación.

AND (Multiplicación lógica):  

        La puerta lógica AND realiza la función booleana de producto lógico. Así, el producto lógico de las variables A y B se indica como AB, y se lee A y B o simplemente A por B.

          Su tabla de a verdad es la siguiente:

      Esta tabla es sencilla de comprender ya que como la misma puerta lo dice es un multiplicador lógico, luego de que se buscan todas las probabilidades únicamente hay que realizar el procedimiento de multiplicación para que nos de lo que esta en la tabla. Observamos que todo numero que se multiplico por 0 da 0, y el único que dio uno fue 1 x 1 que algebraicamente es el resultado correcto. Podemos definir la puerta AND como aquella que proporciona a su salida un 0 lógico si al menos una de sus entradas está a 0.

           Su simbología es la siguiente:

       En este caso puede tener dos entradas o mas pero siempre sera una salida, por la izquierda están las entradas seguido de una figura que es una especie de mezcla entre cuadrado y circulo para finalizar en la salida que es por la derecha que sera el producto lógico de la operación.

OR (Suma lógica):

         La puerta lógica OR , realiza la operación de suma lógica. Puede poseer dos entradas o mas y es una puerta básica que es la base de todas las funciones.

          Su tabla de la verdad es la siguiente:

        Donde se le llama suma lógica porque es lo que se implementa, podemos decir que 0 + 0 es 0, 0 + 1 es 1, 1 + 0 es 1 y 1 + 1 diríamos por una operación que seria dos pero por las reglas del álgebra de Boole el resultado es 1. Podemos definir la puerta OR como aquella que proporciona a su salida un 1 lógico si al menos una de sus entradas está a 1.

        Su simbología es la siguiente:

        Pueden existir de dos o mas entradas que se introducen por la izquierda, se puede visualizar un triangulo de puntas alargadas y del lado derecho estará la salida que por supuesto es la suma lógica.

Tema 2# Historia del Álgebra Boole

        A mediados del siglo XIX, George Boole, 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 fines del siglo XIX, los científicos Jevons, Schroder y Huntington utilizaron este concepto para términos modernizados. Y en el año de 1936, MHStone demostró que el álgebra de Boole es 'isomorfo' para los conjuntos (un área funcional en matemáticas).

        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.

        La síntesis lógica de las herramientas modernas de automatización electrónica se representa de manera eficiente mediante el uso de funciones booleanas conocidas como "Diagramas de decisión binarios".

        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.