Algebra de Boole PDF

Preview

Summary

Unidad 7...

Description

Universidad Nacional de Salta – Facultad de Ciencias Exactas Licenciatura en Análisis de Sistemas – Técnico Universitario en Programación ELEMENTOS DE PROGRAMACIÓN Año 2020 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

UNIDAD 7 - PRIMERA PARTE ÁLGEBRA DE BOOLE Contenidos de la Primera Parte: Álgebra de Boole en el conjunto {0,1} y las operaciones de suma y producto lógico. Propiedades. INTRODUCCIÓN George Boole (1.815-1.864), fue el creador de un sistema algebraico para el estudio sistemático de la lógica, que hoy en día se usa en campos tales como las técnicas digitales, el Álgebra de Conjuntos y la Teoría de las Probabilidades. En los últimos cien años hay pocas obras de matemática que hayan tenido mayor impacto. El Álgebra de Boole constituye una formalización apropiada para representar información digital, y proporciona un modelo matemático para determinar la respuesta de los circuitos lógicos, independientemente del tipo de dispositivo que constituyen sus correspondientes circuitos físicos. Entre las aplicaciones de esta álgebra pueden contarse: formulación algebraica de los requerimientos que debe cumplir un circuito lógico, análisis y síntesis de los circuitos combinacionales, comparación de distintas realizaciones circuitales, minimización del número de cables y dispositivos de los circuitos, codificación de información digital. Conceptos previos Sea una operación genérica a la que denotaremos con el siguiente símbolo: Θ. Ejemplos de operación son la suma, resta, radicación, entre muchas otras. Sea un conjunto genérico al que denotaremos con: M. Ejemplos de conjuntos son los Naturales, Enteros, Reales etc. Definición de operación cerrada en un conjunto: se dice que una operación genérica binaria Θ es cerrada, en un conjunto M, si es una regla que asigna a cada par ordenado (a, b) de elementos de M un elemento único c = a Θ b, tal que c ∈ M. Es decir, una operación binaria es cerrada en un conjunto M, si para todo par de elementos que pertenece a M, el resultado de la operación, también pertenece a M. Por ejemplo, la operación resta es una operación cerrada, en el conjunto de los números enteros, porque restando cualquier pareja de números enteros, el resultado es también un entero. Contrariamente, la resta no es cerrada en el conjunto de los naturales, porque hay restas cuyo resultado no es un número natural, o sea, el resultado no se mantiene dentro del conjunto M. Ejemplo: 3 – 8 = -5 que no pertenece al conjunto de los naturales. Para el desarrollo del Álgebra de Boole, el conjunto de nuestro interés es el formado por los dos elementos 0 y 1, que son los usados por la computadora para registrar datos y programas. Respecto a las operaciones, interesan la suma y el producto, pero no como las conocemos en nuestra álgebra tradicional, donde 5+9=14 y 3*7=21, sino como operaciones lógicas entre ceros y unos.

Universidad Nacional de Salta – Facultad de Ciencias Exactas Licenciatura en Análisis de Sistemas – Técnico Universitario en Programación ELEMENTOS DE PROGRAMACIÓN Año 2020 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

ÁLGEBRA de BOOLE para el conjunto B = {0,1} y las operaciones + y . Definición de Álgebra de Boole Sea el conjunto B = {0,1} y las siguientes dos operaciones, ambas cerradas en B:  

la reunión o suma lógica, que denotaremos con el símbolo + y la intersección o producto lógico, que denotaremos con el símbolo .

Las operaciones lógicas están definidas por las siguientes tablas: + 0 1 0 0 1 1 1 1

. 0 1

0 1 0 0 0 1

Decimos que la estructura (B, +, .) es un Álgebra de Boole si y solo si ∀ a, b, c ∈ B, se verifican cuatro postulados: Antes de presentar cada postulado, debe entenderse la expresión “ ∀ a, b, c ∈ B”.  El símbolo matemático ∀, significa para todo.  Las variables a, b y c pueden tomar solamente uno de los dos valores que son elementos del conjunto B.  sea, la expresión indica que, cualesquiera sean los valores que tomen a, b y c, mientras que sean un 0 ó un 1, determinada afirmación será verdadera. Así, por ejemplo, los valores de a, b y c podrían ser a= 0, b= 0 y c= 1 o a= 1, b= 0 y c= 0. Es importante resaltar que “para todo” establece que bajo todas las combinaciones posibles de ceros y unos que puedan ocurrir con los valores de a, b y c, la afirmación seguirá siendo verdadera. Importante; aunque las operaciones suma y producto son lógicas, de ahora en adelante se omitirá la palabra “lógica” entendiendo que, en contexto del Álgebra de Boole, las operaciones son siempre lógicas. Ahora sí, retomamos la definición de Álgebra de Boole, que no estará completa hasta tanto no se presenten los cuatro postulados: Postulado 1: Las operaciones + y . son conmutativas. ∀ a, b ∈ B: (a + b = b + a) ∧ (a.b = b.a)

Universidad Nacional de Salta – Facultad de Ciencias Exactas Licenciatura en Análisis de Sistemas – Técnico Universitario en Programación ELEMENTOS DE PROGRAMACIÓN Año 2020 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Aclaración: el símbolo ∧ significa Y. El postulado afirma que la suma es conmutativa y (∧) el producto es conmutativo. Postulado 2: Cada operación tiene un elemento neutro. ∀ a ∈ B; ∃ 0,1∈ ∈ B, llamados elementos neutros de las operaciones + y . respectivamente, tal que: (a + 0 = a) ∧ (a.1 = a) Es decir, sumar 0 a cualquier valor de la variable a es hacer algo neutro que no modifica el valor de a. Se dice que 0 es el neutro de la suma lógica. Análogamente, multiplicar 1 a cualquier valor de la variable a es hacer algo neutro que no modifica el valor de a. Se dice que 1 es el neutro del producto lógico. Postulado 3: Cada operación es distributiva con respecto a la otra. ∀ a, b, c ∈ B: a + (b.c) = (a + b) . (a + c) ∧ a . (b + c) = (a.b) + (a.c) Postulado 4: Cada elemento de B posee su correspondiente complemento. ∀ a ∈ B, ∃ 𝐚 ∈ B, llamado complemento de a, tal que: (a +

𝐚

 = 0) = 1) ∧ (a . 𝐚

Resumiendo, una estructura algebraica llamada Álgebra de Boole y denotada como (B, +, .) requiere de un conjunto no vacío, dos operaciones cerradas en dicho conjunto y el cumplimiento de los 4 postulados señalados. Un mejor entendimiento de estos cuatro postulados, se logra por observación de las tablas de las operaciones o realizando nuevas tablas lógicas, como se explica a continuación. Postulado 1: Es evidente, con una sola observación de las tablas que definen las operaciones de + y . nos permite verificar si la siguiente preposición es Verdadera/Falsa: ∀ a, b ∈ B: (a + b = b + a) ^ (a.b = b.a) Por ejemplo, si a y b valen 0 y 1 respectivamente: 

0 + 1 = 1 + 0 y ambas sumas conducen al resultado 1



0 . 1 = 1 . 0 y ambos productos conducen al resultado 0 Recordemos que se presentó sólo un ejemplo. La afirmación del postulado es válida para todo valor que pudieran tomar a y b. Se deja al lector completar las otras tres combinaciones de ceros y unos que completarían todas las combinaciones posibles para los valores de a y b.

Postulado 2: De las tablas que definen las operaciones se observa: ∃ 0, 1 ∈ B llamados elementos neutros de las operaciones + y . respectivamente, tal que: ∀ a ∈ B: (a + 0 = a) ^ (a . 1 = a)

Universidad Nacional de Salta – Facultad de Ciencias Exactas Licenciatura en Análisis de Sistemas – Técnico Universitario en Programación ELEMENTOS DE PROGRAMACIÓN Año 2020 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

El símbolo matemático ∃ significa “existe”, esto quiere decir que al menos hay uno Este postulado se puede comprobar también mediante el uso de tablas lógicas. La tabla lógica considera los distintos valores de la variable a, y define para esos valores (una vez 0 y otra vez 1), el resultado de la operación, según la tabla de operación correspondiente. Se usa una columna para analizar el resultado de la suma y otra para el producto.

Valores que puede tomar a

a

a+0 0 1

a .1

Valores que toma a.1

En esta tabla podemos ver que a puede tomar el valor 0 o el valor 1 Cuando a toma 0, a + 0 vale 0 y a .1 vale 0, también Cuando a toma 1, a + 0 vale 1 y a .1 vale 1, también Entonces, a + 0 coincide con el valor de a; lo mismo ocurre con a .1; por lo tanto, se verifica el postulado 2. El cero es el neutro de la suma y el uno es el neutro del producto. Postulado 3: La Ley Distributiva del producto respecto de la suma, se define como: ∀ a, b, c ∈ B: a . (b + c) = (a.b) + (a.c) La Ley distributiva de la suma respecto del producto, se define como: ∀ a, b, c ∈ B: a + (b . c) = (a + b).(a + c) La validez de la Ley Distributiva del producto respecto de la suma, puede comprobarse utilizando una Tabla lógica. En este caso, la tabla lógica depende de tres variables, a, b, y c. Cada variable puede tomar el valor 0 o 1. Entonces, la tabla tiene 8 filas, correspondiente a las 8 posibles combinaciones de las tres variables. Utilizando las tablas de operaciones de suma y de producto, en cada columna de la tabla vamos construyendo los resultados parciales necesarios para llegar a los valores que toman las dos expresiones a izquierda y derecha del signo = 

expresión a.(b + c) (a la izquierda del =) y



expresión (a.b) + (a.c) (a la derecha del =)

Una recomendación al armar una tabla lógica es colocar las variables en orden y sus valores de ceros y unos en combinaciones crecientes, desde la primera combinación, que es las tres variables con valor 0 (debe notarse que 000 puede

Universidad Nacional de Salta – Facultad de Ciencias Exactas Licenciatura en Análisis de Sistemas – Técnico Universitario en Programación ELEMENTOS DE PROGRAMACIÓN Año 2020 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

verse como una combinación binaria cuyo equivalente en decimal es el 0, o sea, el menor valor posible de todas las combinaciones). Seguidamente se establece una nueva fila de la tabla con la siguiente combinación, después de 000, esto es, 001, o sea, a y b valen cero, c vale 1. Se continúa hasta la última combinación en la que las tres variables valen 1 (nuevamente, 111 es la combinación binaria cuyo equivalente es el 7 decimal, o sea, el mayor valor posible de todas las combinaciones). a b c b+c 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

a.( b + c ) 0 0 0 0 0 1 1 1

a.b 0 0 0 0 0 0 1 1

a.c 0 0 0 0 0 1 0 1

(a.b )+(a.c ) 0 0 0 0 0 1 1 1

Se observa que para toda combinación de entrada, las dos expresiones: a.(b + c) y (a.b) + (a.c) arrojan el mismo valor. En forma análoga se comprueba la validez de la Ley distributiva de la suma lógica respecto del producto lógico. Es importante advertir que la propiedad distributiva de la suma con respecto al producto, es una propiedad que no está presente en nuestra álgebra tradicional. Examinemos el siguiente ejemplo: 3 + 5 * 4, cuyo resultado 23 se obtiene sumando 3 + 20, debido a que el producto 5 * 4 tiene prioridad con respecto a la suma y esa prioridad establece que se hace primeramente el producto y posteriormente la suma. Si en esta álgebra tradicional existiera la propiedad distributiva de la suma con respecto al producto, sería legal efectuar 3 + 5 * 4 = (3 + 5) * (3 + 4) lo que conduce a 8 * 7 = 56. Claramente, esta no es la forma de operar porque la propiedad distributiva de la suma con respecto al producto, como dijimos, no existe en el álgebra tradicional. En el Álgebra de Boole esta propiedad es válida (dejamos al lector construir la tabla lógica para verificarlo) y dicha validez es la que permite asegurar que en el Álgebra de Boole ninguna de las dos operaciones, suma y producto, son una prioritaria sobre la otra. Postulado 4: Cada elemento de B, posee su correspondiente complemento. Entonces: ∀ a ∈ B, ∃ a ∈ B, llamado complemento de a, tal que (a + a = 1) ∧ (a.a = 0)

Universidad Nacional de Salta – Facultad de Ciencias Exactas Licenciatura en Análisis de Sistemas – Técnico Universitario en Programación ELEMENTOS DE PROGRAMACIÓN Año 2020 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Para demostrar este postulado, plantearemos un estudio de casos. Caben las siguientes posibilidades: Primer caso (suponemos que el complemento de 0 es 0 y el complemento de 1 es 0):  =0) Si (0 =0) ^ (1 Tendríamos que: ( 0 + 0 = 0 + 0 = 0 ), lo que no verifica el postulado 4 que exige 0 + 0 = 1. Segundo caso (suponemos que el complemento de 0 es 1 y el complemento de 1 es 1):  =1) Si (0 =1) ^ (1 Tendríamos que: ( 0 + 0 = 0 + 1 = 1 ) lo cual verifica el postulado 4, pero ( 1 . 1 = 1 . 1 = 1 ) no verifica el postulado 4 que exige 1 . 1 = 0. Tercer caso (suponemos que el complemento de 0 es 0 y el complemento de 1 es 1):  =1) Si (0 =0) ^ (1 Tendríamos que: (0 + 0 = 0 + 0 = 0), lo que no verifica el postulado que exige 0 + 0 = 1. Cuarto caso (suponemos que el complemento de 0 es 1 y el complemento de 1 es 0):  = 0) Si (0 = 1) ^ (1 Tendríamos que: (0+0 = 0+1= 1) verifica y (1.1 = 1.0 = 0), también verifica el postulado 4. Concluimos entonces que este cuarto caso, es el que verifica al postulado 4 y permite establecer como complementos a la siguiente combinación los siguientes: 

el complemento de 0 es 1 y



el complemento de 1 es 0

Como vimos, se verificaron cada uno de los cuatro postulados. En consecuencia: ( { 0 , 1 } , + , . ) es un Álgebra de Boole. Propiedades Antes de enunciar las propiedades, vamos a establecer las siguientes convenciones de notación, cuya finalidad es simplificar la notación y hacerla más comprensible: 1. Si entre dos elementos no hubiere ningún símbolo de operación, se supondrá que existe un producto lógico, por lo tanto: a . b pude escribirse ab 2. Como ninguna de las operaciones, + y

. es prioritaria una con respecto a la

otra, toda expresión debe resolverse de izquierda a derecha. Por ejemplo, para resolver a + bc en el Álgebra de Boole, debe efectuarse primero la suma entre a y b, posteriormente, ese resultado se multiplica con c. Esto no nos resulta familiar dado que estamos acostumbrados a operar teniendo en cuenta la prioridad del producto con respecto a la suma. Si se hubiese deseado efectuar primero el producto de b por c, se debería haber indicado esta prioridad mediante

Universidad Nacional de Salta – Facultad de Ciencias Exactas Licenciatura en Análisis de Sistemas – Técnico Universitario en Programación ELEMENTOS DE PROGRAMACIÓN Año 2020 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

el uso de paréntesis, es decir: a + (bc). Sin embargo, por razones de practicidad, adoptaremos la convención de omitir el paréntesis cuando se desea priorizar el producto. Reservaremos el uso del paréntesis sólo para cuando la operación a efectuar prioritariamente sea la suma lógica. Ejemplos: 

Cuando se expresa: a + bc, se resolverá primero el producto lógico b por c y a ese resultado se le sumará a.



Cuando se expresa: (a + b) c, se resolverá primero la suma lógica de a con b y a ese resultado se lo multiplicará por c.

Habiendo ya demostrado que la estructura ( {0, 1} , + , . ) es un Álgebra de Boole, enunciaremos los teoremas. Cada teorema es una propiedad de esta álgebra que nos facilita operar algebraicamente:

1)

Principio de Dualidad. Tesis: Dada una identidad deducible de los postulados de un álgebra booleana, por lo tanto válida, se obtiene otra identidad igualmente válida reemplazando en la primera la operación + por la operación . y viceversa, y el elemento neutro 0 por el elemento neutro 1 y viceversa. La demostración de este teorema se obtiene de inmediato observando la simetría de los postulados con respecto a las dos operaciones y a los dos elementos neutros. Si una proposición o una expresión algebraica se obtiene de otra por la sola aplicación del principio de dualidad, la segunda se llama dual de la primera. En este caso, es claro que la primera es también dual de la segunda.

2)

Ley de Idempotencia para la operación +: ∀ a ∈ B: a + a = a

3)

Ley de Idempotencia para la operación .: ∀ a ∈ B: a.a = a

4)

Ley de Absorción para la operación +: ∀ a ∈ B: a + 1 = 1

5)

Ley de Absorción para la operación .: ∀ a ∈ B: a.0 = 0

6)

Una Ley de Redundancia para la operación +: ∀ a ∈ B: a + a.b = a

7)

Una Ley de Redundancia para la operación .: ∀ a ∈ B: a.(a + b) = a

8)

Vale la Ley de unicidad del complemento. ∀ a ∈ B: a es único

9)

Ley de Involución: a = a

10) Ley asociativa: ∀ a, b, c ∈ B: (a + (b + c) = (a + b) + c) ^ (a.(b.c) = (a.b).c) 11) Primera ley de Morgan: ∀ a, b ∈ B: a + b = a . b 12) Segunda ley de Morgan: ∀ a, b ∈ B: a. b = a + b  = 0) 13) Ley de Complementación de elementos neutros: (0 = 1) ^ (1

14) Una Ley de Redundancia para la operación + : ∀ a, b ∈ B: a + a . b = a + b. 15) Una Ley de Redundancia para la operación . : ∀ a,b ∈ B: a . ( a + b ) = a.b

Universidad Nacional de Salta – Facultad de Ciencias Exactas Licenciatura en Análisis de Sistemas – Técnico Universitario en Programación ELEMENTOS DE PROGRAMACIÓN Año 2020 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------

La operación disyunción o suma binaria Aparte de las operaciones suma lógica y producto lógico, llamadas operaciones primitivas, se define, como operación secundaria o derivada de las primitivas, la operación disyunción o suma binaria, que se simboliza con ⊕, del siguiente modo: ∀ a, b ∈ B: a ⊕ b = a . b + a . b conforme a la definición anterior, la operación tiene la siguiente tabla: ⊕ 0 1

0 0 1

1 1 0

LOGIGRAMAS O CIRCUITOS LÓGICOS Un circuito lógico es un esquema gráfico que representa la relación entre las variables booleanas intervinientes. Tal como lo hemos señalado en nuestra introducción, el Álgebra de Boole proporciona un modelo matemático para determinar la respuesta de los circuitos lógicos, independientemente del tipo de dispositivo que constituyen dichos circuitos. A lo largo de la historia de la Informática, la tecnología ha ido implementando los circuitos con diferentes elementos físicos, pero todos ellos poseen en común, una determinada funcionalidad que siempre obedece a la finalidad lógica que debe implementarse. Nuestro objetivo es entonces ver de qué manera lógica podemos diseñar circuitos lógicos que simbolicen a aquellos circuitos físicos que deberán representar operaciones. Además de diseñarlos, es importante entender la lógica de circuitos ya diseñados, como los clásicos de una computadora, sumadores semi-sumadores y otros que son objeto de estudio en profundidad en el área de la arquitectura de la computadora. Supongamos el caso más sencillo: un circuito eléctrico en donde se produce una entrada de corriente (T0), con un interruptor (x) al medio. Se desea saber si se produce salida de la corriente que entró (T1). Supongamos también que vamos a asignar x = 0 si el interruptor se encuentra abierto, o sea, si impide el paso de la corriente y x = 1 en...