teorías de los conjuntos y circuitos lógicos_lectura_m4

Módulo 4

Unidad 4 y 5

Teorías de los Conjuntos y

Circuitos Lógicos

Materia: Lógica Simbólica

Profesor: Marcelo Smrekar

Lógica Simbólica – Marcelo Smrekar | 2

1. Introducción.

Escribió en cierta ocasión Bertrand Russell «…se supone que uno

sabe ya que todos los hombres son mortales y que Sócrates es un

hombre; y de ahí uno deduce lo que jamás había sospechado, a

saber, que Sócrates es mortal… Así que si tiene usted la intención de

dedicarse a la lógica, he aquí un buen consejo en el que nunca

insistiré bastante: no estudie la lógica tradicional... » El cambio

crucial a la lógica moderna se produjo en 1847 y se debió a George

Boole (1815-1864), hombre modesto y autodidacta, hijo de un

humilde zapatero inglés, publicó The Mathematical Analysis of

Logic. Este y otros trabajos fueron motivo de su nombramiento

como profesor de matemáticas (pese a carecer de títulos

universitarios) del Queens College (hoy University College) de Cork,

en Irlanda…

Javier Borge Holthoefer. Álgebra de Boole: del Silogismo Aristotélico a los Circuitos Integrados – En http://serbal.pntic.mec.es/~cmunoz11/boole.pdf

(Última Visita: marzo de 2011)

Pocas veces sucesos que parecen insignificantes en su época tiene tantas

consecuencias como el trabajo de George Boole. Bien lo ilustra Javier Borge

Holthoefer en su tratado “del silogismo Aristotélico a los circuitos

integrados” con un ejemplo. Expresa Holthoefer: Ocurre a veces que la

importancia de un acontecimiento histórico se mide no tanto por la difusión

de que éste gozó, como por las consecuencias que trajo consigo. Así, hoy

sabemos que la guerra entre Francia y Alemania a finales del siglo XIX fue

deliberadamente provocada por el canciller prusiano Bismarck: falsificó

intencionadamente el despacho del embajador Ems, dándole un carácter

ofensivo, agresivo, hacia la opinión pública francesa para provocar una

reacción de furor en ésta a la vez que la guerra. Tenemos, pues, un

acontecimiento relativamente insignificante (manipulación de un informe)

que desemboca en una guerra, que a su vez da como resultado la unificación

de Alemania”.1

El ejemplo de Bismarck resulta especialmente interesante porque

raramente encontramos en la Historia de la Lógica algo que pueda

compararse; es decir, raramente un logro en Lógica (parecido al ejemplo de

Bismarck en cuanto a difusión se refiere) tiene un impacto de magnitud

similar a la que tuvo en la Historia (general) contemporánea el surgimiento

1 Javier Borge Holthoefer. Álgebra de Boole: del Silogismo Aristotélico a los Circuitos

Integrados – En http://serbal.pntic.mec.es/~cmunoz11/boole.pdf (Última Visita: marzo de 2011)


del Estado Alemán. ¿Cuál podría ser ese logro? A mi entender, el Álgebra de

Boole.

Fundamentemos un poco este razonamiento. De lo manifestado más

arriba se desprende que cualquier hallazgo en Lógica es insignificante. Que

nadie se alborote: con ello quiere decirse que tales hallazgos pasan tan

inadvertidos (o más) para la gran mayoría, como la falsificación del

despacho de Ems por parte de Bismarck. La falta de atención a los logros en

Lógica ocurre incluso en los círculos más próximos a ella: buena parte de

los filósofos de la ciencia del siglo XX (a excepción de Lakatos) han

elaborado sus epistemologías respectivas tomando como referente principal

a la física. Así sucedió con el Círculo de Viena, con Popper, con la

Concepción Heredada y con Kuhn. Para muchos de estos filósofos parecería

a veces que las Matemáticas, la Lógica y, en general, las ciencias formales

caen fuera del saber científico, por no satisfacer los sucesivos criterios de

demarcación que dichos autores han ido proponiendo, o, en otros casos, por

no ser las Matemáticas un saber empírico.

Para completar el paralelismo Bismarck - Boole queda solamente

mostrar la huella que ha dejado la obra del último. Esto no es muy

complicado: basta que observemos el mecanismo que rige un semáforo o el

funcionamiento de un sistema informático para damos cuenta que el

Álgebra de Boole juega un papel nada despreciable no ya en el ámbito

específico de la Lógica, sino en la civilización tal y como la conocemos.

Hasta aquí he hablado únicamente de la proyección "hacia adelante" del

trabajo de Boole, dejando a un lado sus raíces históricas (nada surge de la

nada, Parménides dixit). De las aportaciones de Boole relacionadas con el

Cálculo Proposicional nos ocuparemos en temas posteriores

En cuanto al alcance y estructura de este estudio, hay que decir que es

meramente divulgativo. Esta lectura está dedicada primero a resaltar

aspectos básicos de la Teoría de Conjuntos y del Cálculo Proposicional, para

luego ver en qué sentido Boole colaboró en su interrelación, desarrollo o

profundización; asimismo, se intenta poner en contacto esta Teoría y este

Cálculo con su despliegue práctico, que desemboca en los dispositivos

lógicos bajo la forma de un Álgebra de Boole (sección 4). La sección 3 se

limita a la enunciación de los teoremas y postulados del Álgebra de Boole,

con algunas apreciaciones históricas. Por último, añadimos un Anexo en el

que se utilizan las representaciones diagramáticas de Venn para comprobar

(que no demostrar) la validez de las leyes del Álgebra de Conjuntos.

Fruto de todo esto, la lectura tiene una considerable envergadura. Por

esta razón, se debe afrontar su estudio de un modo selectivo. Si uno está

interesado, por ejemplo, en la Electrónica o la informática, y quiere conocer

los fundamentos históricos y teóricos del Álgebra de Boole, deberá

profundizar en temas posteriores, dando menos valor a la última parte. Por

el contrario, si uno está familiarizado con la Lógica y su Historia, desde las

humanidades, quizá le llamen más la atención los aspectos prácticos en que

han desembocado los trabajos de Boole.


Por último, se ha procurado que esta lectura goce de cierta consistencia.

El hilo conductor al que debe agradecerse tal consistencia no es otro que

Kneale, y su obra “El desarrollo de la lógica”. En esta obra se encuentran

todos los aspectos aquí tratados, además de otros (como las relaciones entre

Boole y el cálculo de probabilidades). Esta tarea ha consistido en

seleccionar y ampliar aquellos aspectos que son más relevantes y han sido

más fructíferos para el surgimiento de nuestra actual "era informática".

4. Teoría de conjuntos y

Álgebra de Boole.

Tanto el Cálculo Proposicional que abreviaremos (CP) y estudiamos

hasta aquí como la Teoría de Conjuntos que abreviaremos (TC) pueden

pensarse ambos como instancias de un sistema algébrico denominado

Álgebra de Boole y que definiremos en esta lectura.

Para ilustrar los nexos que los unen, intercalaremos explicaciones

acerca de uno (CP), a pesar de haber sido definidos ya y de la otra (TC), que

iremos definiendo a medida que avance la lectura.

4.1. Conjuntos: Definición, notación.

Comencemos ahora por la Teoría de Conjuntos. El concepto de conjunto

surge de manera natural en muchas situaciones de la vida: películas de

guerra, novela rosa, pescaderías... Si llevamos a cabo un sencillo proceso de

abstracción, veremos que podemos definir un conjunto de dos modos

distintos:

» Por extensión: enumeración simple de sus elementos.

» Por comprensión: definir una propiedad no ambigua y determinada.

Veamos un ejemplo:

Supongamos un conjunto que comprende los componentes del grupo

musical “The Beatles". Definiríamos tal conjunto por extensión de la

siguiente manera:

S= {Paul McCartney. John Lennon, George Harrison, Ringo Starr}

Definido por comprensión, el conjunto quedaría así:

S={x / x pertenezca al grupo musical “The Beatles"}


4.2. Conjuntos especiales, subconjuntos.

Al definir un conjunto L no sólo se determinan sus elementos, sino

también los que no lo son. Sin embargo, esto puede acarrear algún

problema. Por ejemplo, pensemos en el conjunto de los números enteros, al

que denotaremos con la letra Z. Si hacemos caso de lo dicho hasta ahora, Z

no define sólo el conjunto de los números enteros: define también un

conjunto Z', al que definimos como "todo aquello que no es un número

entero". Hasta aquí, todo parece correcto: el conjunto Z' contiene, por

ejemplo, el número “e”. la raíz cuadrada de 2. ... pero también incluye los

templos hindúes a orillas del Ganges. o las Zapaterías del barrio gótico de

Barcelona. Para evitar complicaciones, resulta más adecuado restringir los

elementos considerados a un conjunto menor. En nuestro caso, servirá el

conjunto de los números reales (R). Con el fin de obtener esta restricción

postulamos un conjunto universal E que definimos como el conjunto de

todos los elementos que consideramos. El complementario de un conjunto

es entonces el complementario respecto de este conjunto universal. La

interpretación de este conjunto universal por parte de Boole le llevó a

identificar tal conjunto con el valor "1" pero nosotros lo denotaremos con U

de Universal o también con Ω .

Queda por determinar qué es un conjunto vacío. En general, la

intersección de dos conjuntos sería siempre un conjunto, excepto cuando

no tienen elementos comunes. Este caso especial se elimina postulando un

conjunto vacío. La interpretación de este conjunto vacío por parte de Boole

le llevó a identificar tal conjunto con el valor “0” pero nosotros lo

denotaremos como Φ o también con dos llaves que no contienen nada {}.

Esta asignación de valores 1-0 a los conjuntos Ω y Φ tiene importantes

consecuencias no sólo en el ámbito de la Lógica Formal sino también en

ámbitos que aquí no tratamos, como la teoría de la probabilidad (diremos

sólo que cualquier valor de probabilidad se encuentra entre 0 y 1).

Para mostrar algunas de estas consecuencias, consideremos el modo de

Boole de asignar valores de verdad a las proposiciones: hoy día expresamos

la certeza de un enunciado asignándole el valor “1” (o también como lo

hacíamos con una V), y su falsedad con el valor “0”. Pues bien, en

Bochénski leemos:

“Si nos limitamos a la consideración de una sentencia dada x. dejando

de lado toda otra consideración, se podrán imaginar sólo dos casos, a saber

primero, que la sentencia sea verdadera. y la segunda, que sea falsa. Como

estos casos componen el universo de la sentencia, y el primero se representa

por el símbolo x, el segundo se representará por el símbolo (1-x)”


4.3 Operaciones con conjuntos.

Relaciones. Relación entre conjuntos y

clases.

Habíamos definido una proposición como un aserto que puede ser

cierto o falso, pero no ambas cosas a la vez. Tales proposiciones, como

dijimos, pueden ser simples ("Los gatos comen pescado") o compuestas

("Los gatos comen pescado y los perros comen carne"). Como es sabido, las

proposiciones simples se unen mediante conectivos. De ellos, cuatro son los

más importantes:

CONJUNCIÓN y ^

DISYUNCIÓN o v

CONDICIONAL Si... entonces =>

BICONDICIONAL Si y sólo si <=>

Además de estos conectivos, en el lenguaje coloquial se usa a menudo la

negación:

NEGACIÓN no

Por supuesto, en el lenguaje coloquial (natural) usamos un número más

amplio de conectivos, tales como "a menos que", "pero'... Ante esto,

podríamos establecer notaciones distintas para cada una de ellas. Por otro

lado, parece (es) más conveniente intentar reducir (sin distorsión de su uso

común) tales conectivos a los cuatro establecidos. Considérese este ejemplo:

“El café es agradable, a menos que se le añada azúcar" (simbólicamente,

p a menos que q).

El significado de la oración es que si añadimos azúcar, el café no es

agradable: es decir "El Café es agradable si no añadimos azúcar o bien 'Si no

añadimos azúcar, entonces el Café es agradable*. O lo que es lo mismo: “q

=> p”, con lo cual hemos logrado nuestro objetivo.

Unión e intersección:

Aquí comenzamos a percibir el modo en que Boole unifica el CP y la TC.

Unión e intersección son las dos operaciones básicas en el Álgebra de

Conjuntos.

La unión entre dos conjuntos L y W se define como el conjunto formado

por todos los elementos de L junto con todos los elementos de W y la

denotaremos como L U W


La intersección entre dos conjuntos L y W se define como el conjunto

que comprende sólo aquellos elementos que L y W tienen en común y la

denotaremos como L W

Lo cierto es que tanto la unión como la intersección quedan mucho más

claras a través de una ilustración:

El sombreado representa L W en el caso de la intersección (primer

caso) y en el caso de la unión (segundo caso) el sombreado representa L U

W

Si bien ya Leibniz, en el siglo XVII, entrevió la existencia de una cierta

analogía entre la intersección y la unión, por una parte, y el producto y la

suma de números, por otra, fueron las aportaciones de Boole las que

clarificaron tales relaciones, ampliándolas además a los conectivos lógicos ^

(conjunción) y v (disyunción) de la Lógica Formal. De este modo, la

intersección de conjuntos se expresa también con esta simbología:

/A B x x A x B

Y la unión de conjuntos se expresa como:

/A B x x A x B ,

Cerrando de esta manera la relación entre la intersección y la

conjunción por un lado y la unión de conjuntos y la disyunción de

proposiciones por el otro. De este modo, diremos que un x está en la

intersección de los conjuntos A y B si la proposición “x está en A y x está en

B” es verdadera, es decir p^q. Por otro lado diremos que un elemento x está

en la unión de A y B si la proposición “x está en A o x está en B” es

verdadera, es decir pvq.

Leyes de conjuntos y del cálculo proposicional.

Para convencernos del enunciado general arriba expuesto, según el cual

el CP y la TC pueden reducirse a un Álgebra de Boole, veamos una tabla

comparativa que contemple las leyes del álgebra de conjuntos y del cálculo

proposicional (para darnos cuenta de que tratan, en esencia, de lo mismo):

Intersección de dos conjuntos Unión de dos conjuntos


CONJUNTOS CÁLCULO PROPOSICIONAL

Leyes conmutativas para la

intersección y la unión

Ley conmutativa

A B = B A p ^ q q ^ p

A U B = B U A p v q q v p

Ley asociativa para la intersección Ley asociativa para la conjunción

A (B C) = (A B) C p ^ (q ^ r) (p ^ q) ^ r

Ley asociativa para la unión Ley asociativa para la disyunción

A U (B U C) = (A U B) U C p v (q v r) (p v q) v r

Ley distributiva de la intersección

respecto de la Unión

Ley distributiva de la conjunción

respecto de la disyunción

A (B U C) = (A B) U (A C) p ^ (q v r) (p ^ q) v (p ^ r)

Ley distributiva de la unión respecto

de la Intersección

Ley distributiva de la disyunción

respecto de la conjunción

A U (B C) = (A U B) (A U C) p v (q ^ r) (p v q) ^ (p v r)

Ley idempotente Ley idempotente

A U A = A A A = A p v p p p ^ p p

Ley de complementación Leyes de negación (complementación)

A U A’ = Ω A A’ = Φ |p v ¬p| =1 (V) |p ^ ¬p| = 0 (F)

Leyes de absorción Leyes de absorción

A U (A B) = A A (A U B)=A pv(p^q) p p^(pvq) p

Leyes De Morgan Leyes de De Morgan

(AUC)’ = A’ B’ (AC)’ = A’ U B’ ¬(pvq) ¬p^¬q ¬(p^q)

¬pv¬q

Leyes con Ω y Φ (Ω’ = Φ) Leyes con 0 y 1 (¬10)

Φ U A = A Ω A = A 0 v pp 1^p p

Ω U A = Ω Φ A = Φ 1 v p0 0^p 0


4.4. Álgebra de Boole: Definición,

propiedades.

En el tema anterior hemos visto que las aportaciones de Boole jugaron

un papel primordial para alcanzar la unificación del CP y la TC. Pero el

trabajo de Boole no llegó sólo hasta ahí, agregó también un motivo más

para que se buscaran estructuras abstractas dentro de los universos de

manera que cuando un universo en particular se podía estructurar de

alguna manera automáticamente pasaba a cumplir en particular con las

leyes que la estructura tenía en general. A estas estructuras se le brindó el

nombre de estructuras algebraicas y el espacio vectorial (que se verá en otra

materia) es un ejemplo. Otra de las estructuras importantes es la estructura

de Álgebra y es la que motiva esta lectura. En esta oportunidad nos

limitaremos a presentar el cuerpo del Álgebra de Boole tal y como él lo

concibió.

Supongamos entonces que podemos relacionar elementos de un

universo a través de una operación. Por ejemplo los números reales con la

suma, los conjuntos con el complemento o las proposiciones con la

disyunción. Para ello, es necesario antes distinguir entre "operaciones

binarias" y "operaciones unitarias", aunque hayamos intuido

implícitamente con anterioridad a qué se refieren estos conceptos:

Operaciones binarias

Una operación binaria $ en un conjunto A es una operación tal que si a

y b son elementos del conjunto A entonces también lo es a$b.

Por ejemplo, en Aritmética, ¿es la división una operación binaria?

Puede serlo o no, depende del conjunto que consideremos como universal.

Si el conjunto considerado es el de los reales R entonces la división es una

operación binaria. Si, por el contrario, el conjunto a considerar es el de los

enteros Z entonces la división no resulta ser una operación binaria puesto

que por ejemplo 5/2 no es un entero.

Operaciones unitarias

Una operación unitaria ~ sobre un conjunto A es una operación tal que

si a es un elemento de A también lo es ~a.

Volvamos a la Aritmética para elaborar un ejemplo, ¿es la operación

"tomar el opuesto de" (-) una operación unitaria? Si consideramos tal

operación sobre el conjunto de los Naturales N, entonces (-) no es una

operación unitaria. Si, por el contario, la consideramos sobre todos los

números enteros Z, entonces (-) sí cumple con el requisito para ser

operación unitaria.

Definición de Álgebra de Boole.


Un Álgebra conmutativa o Álgebra de Boole (A,$,&) es un Conjunto A no

vacío tal que existen dos operaciones binarias entre sus elementos ($ y &)

de forma que satisfacen las siguientes cinco propiedades (axiomas):

1. $ y & son asociativas en A

Es decir que para todo elemento x, y o z de A se tiene que:

( x $ y ) $ z = x $ ( y $ z )

( x & y ) & z = x & ( y & z )

2. $ y & son conmutativas en A

Es decir que para todo par de elementos x, y de A se tiene que:

x $ y = y $ x

x & y = y & x

3. Existe un elemento identidad para $ y uno para & en A

Es decir que para todo elemento x de A se tiene que existe 0,

elemento neutro de $, tal que:

x $ 0 = 0 $ x = x

y para todo elemento x de A se tiene que existe 1, elemento neutro de

&, tal que:

x & 1 = 1 & x = x

4. Existe un elemento opuesto para $ y uno para & en A

Es decir que para todo elemento x de A se tiene que existe x’ tal que:

x $ x’ = x’ $ x = 0

x & x’ = x’ & x = 1

5. $ y & cumplen la ley distributiva de una respecto de la otra en A

x $ (y & z) = (x$ y) & (x $ z)

x & (y $ z) = (x & y) $ (x & z)

Propiedades del Álgebra de Boole.


A partir de esos axiomas se pueden demostrar una serie de postulados o

teoremas que se incorporan a las leyes enunciadas. Por ejemplo:

1. En todo Álgebra de Boole se cumple que (leyes de absorción)

x $ 1 = 1

x & 0 = 0

2. En todo Álgebra de Boole se cumple que (leyes de idempotencia)

x $ x = x

x & x = x

3. En todo Álgebra de Boole se cumple que (ley involutiva)

(x’)’ = x

4. En todo Álgebra de Boole se cumple que (leyes de absorción)

x $ (x & y) = x

x & (x $ y )= x

5. En todo Álgebra de Boole se cumplen las leyes de De Morgan:

(x & y)’ = x’ $ y’

(x $ y )’= x’ & y’

Es importante notar que dado un conjunto universal Ω entonces todos

los subconjuntos de Ω forman un Álgebra de Boole. Veamos:

Tomemos C=(Ω, U, ). Como Ω y el conjunto vacío Φ son subconjuntos

de Ω luego se ve que C cumple con todos los axiomas presentados puesto

que haciendo Ω como el elemento neutro de la intersección y Φ el elemento

neutro de la unión tenemos:

1. Leyes conmutativas para la intersección y la unión


A B = B A

A U B = B U A

2. Ley asociativa para la intersección y para la unión

A (B C) = (A B) C

A U (B U C) = (A U B) U C

3. Existencia de neutros

Φ U A = A Ω A = A

4. Existencia de inversos

A U A’ = Ω A A’ = Φ

5. Leyes distributivas

A (B U C) = (A B) U (A C)

A U (B C) = (A U B) (A U C)

Luego, los conjuntos de un universal forman un Álgebra de Boole ya que

cumplen con todos los requisitos. Se prueba, además, que las proposiciones

forman también un álgebra, si se acotan a un determinado referencial.

Por lo tanto, podemos concluir que tanto los conjuntos como las

proposiciones cumplen con todas las leyes del Álgebra de Boole, que por

otra parte, son demostrables a través de los axiomas de las operaciones

solamente.

Es importante notar que todos los teoremas que mencionamos del

Álgebra han sido listados de a pares, uno para una operación y otro para

otra. Una parte puede obtenerse a partir de la otra mediante el intercambio

de los elementos unitarios (0 y 1) y los operadores binarios ($ y &). Esto se

conoce como el Principio de dualidad, gracias al cual cualquier apartado de

los postulados puede obtenerse a partir del otro sin más que intercambiar

los operadores binarios y los elementos unitarios.

4.5 Expresiones Booleanas. Funciones

Booleanas. Tablas de verdad para

clases.

Un ejemplo importante de Álgebra de Boole es el Álgebra bivalente (T,

OR, AND), esto es un conjunto universal T con sólo dos elementos, 0 y 1 de

manera que:


NOT 1=0

NOT 0=1

1 AND 0=0

1 OR 0=1

Las funciones Booleanas son aquellas funciones proposicionales donde el

argumento es una variable que puede tomar valores sólo en el universo

{0,1} y su tabla de verdad es la tabla de verdad usual. De este ejemplo en

particular hablaremos en el próximo tema.

Estos axiomas con los que se definió un Álgebra de Boole se conocen

como los postulados de Huntington. Otros grupos de axiomas conocidos en

el ámbito de las Matemáticas son los de Birkhoff y Mac Lane pero terminan

definiendo lo mismo, es decir, los conjuntos de axiomas son equivalentes.

5. Circuitos lógicos.

5.1. Introducción a los circuitos lógicos.

Debido a que las computadoras trabajan con información binaria, esto

es, dado un determinado lugar, ese lugar puede estar cargado

eléctricamente o no, eso lo podemos medir con 1 si está cargado o 0 si no, o

lo podemos medir con V si está cargado o F si no. De todas formas, la

herramienta matemática adecuada para el análisis y diseño de su

funcionamiento es el Álgebra de Boole en su forma bivalente. Aunque fue

desarrollada inicialmente para el estudio de la Lógica, viene muy bien con

sus aplicaciones. Ha sido a partir de 1938, fecha en que C.E. Shanon publicó

su obra “Análisis simbólico de circuitos con relés”, estableciendo los

primeros conceptos de la actual Teoría de la Conmutación, cuando se ha

producido un aumento considerable en el número de trabajos de aplicación

del Álgebra de Boole a los computadores digitales. Hoy en día, esta

herramienta resulta fundamental para el desarrollo de los computadores ya

que, con su ayuda, el análisis y síntesis de combinaciones complejas de

circuitos lógicos puede realizarse con rapidez y eficacia.

5.2. Circuitos lógicos simples

(compuertas lógicas).

Para que el Álgebra de Boole se torne realmente útil de cara a la

electrónica y la computación, ésta debe plantearse como un álgebra

bivalente. No hay acuerdo acerca de si tal Álgebra "nació" bivalente, o el ser

bivalente es una restricción añadida para facilitar su aplicación. A este

respecto, Kneale y Bochénski mantienen opiniones contrapuestas.


En cualquier caso, este álgebra bivalente aplicada tiene las mismas

tablas de verdad del CP expuestas anteriormente, cambiándoles sólo la

nomenclatura: donde decíamos "disyunción" (v), ahora decimos OR: donde

decíamos "conjunción" (^), decimos AND; donde decíamos "negación" (¬)

ahora decimos INVERSOR o NOT. Veamos de nuevo la tabla con el

vocabulario renovado:

Variables Funciones proposicionales

x y x + y x . y

(operación OR) (operación AND)

1 1 0 1

1 0 1 0

0 1 1 0

0 0 1 0

x"

(operación NOT)

x x'

1 0

0 1

Por supuesto, existen otros operadores además de éstos pero todos se

pueden expresar a través de los mismos. Véase la siguiente tabla con todos

los operadores y su símbolo más extendido (de este modo nos avanzamos

un poco al contenido de la siguiente sección, dedicado íntegramente a la

aplicación del Álgebra de Boole dentro de la electrónica):


Funciones Booleanas.

La aplicación más directa de las puertas lógicas es la combinación entre

dos o más de ellas para formar circuitos lógicos que responden a funciones

booleanas (Funciones proposicionales sobre el universo {0,1}). Una función

lógica hace que una o más salidas tengan un determinado valor para un

valor determinado de las entradas.

Tales funciones o fórmulas (puesto que tienen variables que a priori son

incógnitas) consisten en un número finito de constantes (0. 1) y variables

conectados por los operadores (+). (•) y (¬) de forma que (+) y (•) no

pueden estar adyacentes nunca. Cada expresión de n-variables describe una

única función.

Se pueden tomar como ejemplos las funciones de la tabla de la página

anterior, correspondientes a los distintos operadores lógicos.

Por supuesto, dos fórmulas pueden ser equivalentes. Dos expresiones

Booleanas A y B se dicen equivalentes (A=B) si ellas describen la misma

función Booleana.

Ejemplo (recordar que las constantes pueden valer 0 ó 1): Sea F =

a((a+b).c') y G = (a+b).(a+b'+c')


a b c a+b (a+b).c’ a+b'+c’ F G

1 1 1 1 0 1 1 1

1 1 0 1 1 1 1 1

1 0 1 1 0 1 1 1

1 0 0 1 1 1 1 1

0 1 1 1 0 0 0 0

0 1 0 1 1 1 1 1

0 0 1 0 0 1 0 0

0 0 0 0 0 1 0 0

Luego, F y G son equivalentes porque tienen la misma tabla de verdad.

5.3 Circuitos combinatorios.

Propiedades. Equivalencia con la LP.

Representación.

Implementación de Funciones Booleanas.

Para el diseño de circuitos digitales sólo cabe hacer la precisión del

siguiente convenio:

- Presencia de tensión: 1

- Ausencia de tensión: 0

Con este criterio, podemos proceder a la implementación de funciones.

Es decir que dado un circuito podemos a través de las posibles entradas y

las salidas correspondientes encontrar la fórmula que el circuito determina.

Veamos con un ejemplo:

Supongamos que tenemos el siguiente circuito:

1

2

5

3 4

F


Aquí vemos que de acuerdo a las entradas A, B y C tendremos la salida

F. Procederemos a escribir la tabla de verdad correspondiente.

Veamos que si A se junta con B y C en 1 (donde hay un and) y que A se

junta con B’ y C’ en el otro AND de 2 (debido a que 3 y 4 son NOT) por

último los resultados se juntan en un OR (denominado 5 en este ejemplo).

Por lo tanto, en la primera fila de la tabla correspondiente, dado que A, B y

C valen 1 entonces el primer AND le llegan tres unos y por lo tanto éste vale

1. Al segundo AND le llegan un uno correspondiente a A y dos ceros

correspondientes a B y C, luego pasa 0 (porque es un AND) y a 5 le llega un

uno y un cero, luego pasa 1 y el resultado de la primera fila es 1. Para la

segunda fila por ejemplo, al primer AND le llegan dos unos (A y B) y un

cero (C) y al segundo AND le llegan también dos unos (de A y C’ ahora) y un

cero (B’). Luego pasan dos ceros y 5 vale cero. De esta manera completamos

la tabla.

Tendremos que la tabla del circuito se hace 1 sólo para dos

combinaciones de valores de las entradas:

A B C F

1 1 1 1

1 1 0 0

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 0

0 0 1 0

0 0 0 0

Entonces, dado un sistema cualquiera compuesto de x entradas (3 en

este caso) y una Salida (F, la función a implementar) podemos utilizar dos

tipos de procedimientos (formas canónicas de las fórmulas Booleanas) para

recuperar la fórmula del sistema. A saber:

Procedimiento minterms: obtendremos la suma de

productos de las variables "entrada" cuyas combinaciones


hacen 1 a la función. Convenio a aplicar "0* para variables

negadas, "1" para variables sin negar.

Ecuación maxterms: obtendremos el producto de las sumas

de las variables "entrada" cuyas combinaciones hacen 0 a la

función. Convenio a aplicar. 1 para variables negadas: "0* para

variables sin negar.

Lo que se logra con estas ecuaciones es la expresión correspondiente a

una tabla de verdad dada. Tal expresión es, además, simplificable

algebraicamente mediante los postulados y teoremas enunciados más

arriba (aunque la simplificación se obtiene casi siempre por métodos

tabulares -por el simple motivo de que es más fácil- como veremos en el

apartado siguiente). Por ejemplo, intentemos obtener la ecuación de la

tabla de verdad correspondiente al ejemplo anterior:

Con el método minterms, tenemos sólo dos unos para F en la tabla de

verdad que corresponden a las combinaciones 1,1,1 y 1,0,0 de las entradas.

Luego, para la combinación uno tomamos A.B.C porque las tres valen uno y

para la segunda tomamos A.B’.C’ porque para B y C tenemos el valor cero.

Recordando que minterms es “suma de productos” luego sumamos los

términos y nos queda que:

F= A.B.C+ A.B’.C’

Con el método maxterms, tenemos seis ceros para F en la tabla de

verdad que corresponden a todas las combinaciones salvo 1,1,1 y 1,0,0 de las

entradas. Hacemos exactamente al revés, si A tiene un 1 tomamos A’, si

tiene un cero tomamos A. Luego para la combinación dos tomamos

(A’+B’+C), para la tres tomamos (A’+B+C’), la cuatro no la ponemos y

tomamos las últimas cuatros como:

(A+B’+C’)

(A+B’+C)

(A+B+C’)

(A+B+C)

Y recordando que maxterms es “producto de sumas” luego multiplicamos

los términos y nos queda que:

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

Tal expresión es, además, simplificable algebraicamente mediante los

postulados y teoremas enunciados más arriba (aunque la simplificación se

obtiene casi siempre por métodos tabulares -por el simple motivo de que es

más fácil- como veremos en el apartado siguiente). De todas maneras

tomémonos el trabajo de tratar de llegar a la expresión obtenida con


mintems a partir de la obtenida con maxterms para comprobar que son

equivalentes. Considerando que A’A’=A’ y que por ejemplo BB’=0 tenemos

que el producto de los dos primeros paréntesis, aplicando distributiva es:

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

Reordenando y considerando que A+0=A esto es igual a:

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

Que es igual a:

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

Y recordando que B +B’=1 tenemos que:

A’+A’1 +A’1+B’C’+BC=

De donde, ya que A.1=A y A+A=A:

A’+A’+A’+B’C’+BC= A’+B’C’+BC

El producto de los dos primeros paréntesis lo podemos reducir a:

A’+B’C’+BC

De la misma manera el producto de dos paréntesis 4 y 5 queda

(A+AB+AC’+AB’+0+B’C’+AC+BC+0)=

Que es lo mismo que

A+B’C’+BC

De una manera similar a lo anterior. Por último el producto de los

paréntesis que quedan (3 y 6) se puede expresar como:

(A+AB+AC+AB’+0+B’C+AC’+BC’+0)=

Que es igual a:

A+B’C+BC’

Entonces F termina siendo el producto de las tres expresiones que hemos

derivado

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

Y haciendo el producto de los dos primeros paréntesis tenemos:

(A’A+A’B’C’+A’BC+AB’C’+B’C’B’C’+B’C’BC+ABC+BCB’C’+BCBC)

Que, reordenando y agrupando, es lo mismo que:

A’A+(A’B’C’+AB’C’)+(B’C’B’C’+B’C’BC)+(ABC+A’BC) +(BCB’C’+BCBC)


Idéntico a:

0+B’C’+B’C’+BC+BC

Que queda:

(B’C’+BC)

Luego F es:

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

Entonces,

F=AB’C’+ABC+BB’C+BB’C’+BC’C+B’C’C=

Y por último, puesto que BB’=0 y 0C=0, tenemos

F=AB’C’+ABC+0+0+0+0

Y llegamos a:

F=AB’C’+ABC

Que es lo mismo que habíamos obtenido por minterms.

Métodos tabulares de simplificación de ecuaciones.

Como vimos, simplificar funciones puede llegar a ser bastante

complicado. El recurso de las tablas para la simplificación de ecuaciones

booleanas es, como ya se ha dicho, de mayor simplicidad. Nos limitaremos

a explicar aquí someramente el método conocido como "mapas de

Kamaugh". Estos mapas se pueden utilizar para simplificar funciones de

dos a seis Variables aunque habitualmente sólo se los emplee para

funciones de dos a cinco Variables. Existen otros métodos como el

Algoritmo Quine–McCluskey que es un método de simplificación de

funciones booleanas desarrollado por Willard Van Orman Quine y Edward

J. McCluskey. Es funcionalmente idéntico a la utilización del mapa de

Karnaugh, pero su forma tabular lo hace más eficiente para su

implementación en lenguajes computacionales, y provee un método

determinístico de conseguir la mínima expresión de una función booleana.

De todas maneras, el primero sirve como ejemplo y es más sencillo de

comprender.

Para hacer honor a la verdad, el método gráfico de Kamaugh

desarrollado en The Map Method for Synthesis of Combinatorial Logic

Circuito (AIEE. vd. 72. 195a) se basa en otro método debido a E. W. Veitch

publicado en A Chart Method for Simpfifying Truth Functionc (ACM. 1952)

pero es autocontenido y por lo tanto sólo nos referiremos a ése. Esta técnica

se convirtió rápidamente en la herramienta más potente entre los

diseñadores de computadores y expertos en lógica digital durante la década

de los 50.

http://es.wikipedia.org/wiki/Willard_Van_Orman_Quine

http://es.wikipedia.org/wiki/Edward_J._McCluskey



http://es.wikipedia.org/wiki/Mapa_de_Karnaugh




Entrando en materia, los mapas están constituidos por una cuadrícula

en forma de encasillado cuyo número de Casillas depende del número de

Variables que tenga la función a simplificar. Cada una de las casillas que

forman el mapa puede representar términos tanto minterms como

maxterms. Veamos un ejemplo de mapa con tres variables en términos de

maxterms siguiendo la tabla del ejemplo anterior:

Como la tabla tenía 8 filas (dos al cubo puesto que hay tres variables) el

mapa tendrá 8 casillas con los resultados de los valores de F así en la

primera fila están todos los posibles valores de AB y en la primera columna

todos los posibles valores de C, en el cuerpo de la tabla están todos los

valores de F correspondientes.

El principio de simplificación de los mapas se basa en una de las leyes

del Álgebra de Boole:

a . b + a . b' = a

Como podemos observar en la tabla todas las Casillas contiguas se

caracterizan por diferenciarse sólo en una Variable que se encuentra negada

en una de ellas y sin negar en la otra. Tal característica, propia de todos los

mapas de Kamaugh permite aplicar la ley anterior.

Para proceder a la simplificación, debemos fijamos sólo en las casillas

que contienen "1" (si simplificaremos por minterms), o en las que contienen

"0" (si simplificaremos por maxterms).

Ejemplo con minterms (de unicrom.com): Se tiene la siguiente tabla de

verdad para tres variables.

Se desarrolla la función lógica basada en ella (primera forma canónica).

Ver que en la fórmula se incluyen solamente las variables (A, B, C) cuando F

es igual a "1".

Si A en la tabla de verdad es "0" se pone A, si B = "1" se pone B, Si C =

"0" se pone C, etc.

F = A B C + A B C + A BC + A B C + A B C + A B C


Una vez obtenida la función lógica, se implementa el mapa de

Karnaugh.

Este mapa tiene 8 casillas que corresponden a 2n, donde n = 3 (número

de variables (A, B, C))

La primera fila corresponde a A = 0

La segunda fila corresponde a A = 1

La primera columna corresponde a BC = 00 (B=0 y C=0)

La segunda columna corresponde a BC = 01 (B=0 y C=1)

La tercera columna corresponde a BC = 11 (B=1 y C=1)

La cuarta columna corresponde a BC = 10 (B=1 y C=0)

En el mapa de Karnaugh se han puesto "1" en las casillas que

corresponden a los valores de F = "1" en la tabla de verdad.

Tomar en cuenta la numeración de las filas de la tabla de verdad y la

numeración de las casillas en el mapa de Karnaugh.

Para proceder con la simplificación, se crean grupos de "1"s que tengan

1, 2, 4, 8, 16, etc. (sólo potencias de 2).

Los "1"s deben estar adyacentes (no en diagonal) y mientras más "1"s

tenga el grupo, mejor.

La función mejor simplificada es aquella que tiene el menor número de

grupos con el mayor número de "1"s en cada grupo

Se ve del gráfico que hay dos grupos cada uno de cuatro "1"s, (se

permite compartir casillas entre los grupos).

La nueva expresión de la función boolena simplificada se deduce del

mapa de Karnaugh.

- Para el primer grupo (rojo): la simplificación da B (los "1"s de la

tercera y cuarta columna) corresponden a B sin negar) porque

como el grupo abarca a A negado y sin negar (dos filas) se


simplifica y C negado y sin negar (dos columnas) también se

simplifica. Luego queda sólo B.

- Para el segundo grupo (azul): la simplificación da A (los "1"s

están en la fila inferior que corresponde a A sin negar) Aquí A

está sin negar y los otros dos están negados y sin negar, luego, se

simplifican.

Entonces, como el maxterms es la suma de productos y los términos que

nos quedaron fueron A y B solamente tenemos que el resultado es F = B + A

ó por supuesto su equivalente F = A + B

Otro Ejemplo de la misma fuente:

Una tabla de verdad como la que sigue da la siguiente función booleana:

F = ABC + AB C + A B C + A B C

Se ve claramente que la función es un reflejo del contenido de la tabla

de verdad cuando F = "1"

Con esta ecuación se crea el mapa de Karnaugh y se escogen los

grupos. Se lograron hacer 3 grupos de dos "1"s cada uno.

Se puede ver que no es posible hacer grupos de 3, porque 3 no es

potencia de 2. Se observa que hay una casilla que es compartida por los tres

grupos.

Grupo en azul: tenemos AB con C negado y sin negar, luego

quitamos C

Grupo en marrón: tenemos AC con B negado y sin negar, luego

quitamos B


Grupo en verde: tenemos BC con A negado y sin negar, luego

quitamos A

La función simplificada es:

F = AB + A C + B C

Veamos ahora nuestro ejemplo con maxterms. Recordemos que la tabla

de verdad era:

A B C F

1 1 1 1

1 1 0 0

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 0

0 0 1 0

0 0 0 0

Con lo que nos quedaría el siguiente mapa:

AB en la fila de arriba, C en la columna de la izquierda

00 01 11 10

0 0 0 0 1

1 0 0 1 0

Ahora trabajamos con los ceros y aquí podemos hacer tres grupos:

El cuadrado de las primeras cuatro casillas correspondientes a B y C

negadas y sin negar, con lo que nos queda A’ y como estamos con maxterms

tomamos A

00 01 11 10

0 0 0 0 1

1 0 0 1 0


También tenemos el rectángulo de las casillas coloreadas en amarillo.

Con A negada y sin negar, con lo que nos queda B y C’ como estamos con

maxterms tomamos B’ y C, es decir (B’+C)

00 01 11 10

0 0 0 0 1

1 0 0 1 0

También tenemos el rectángulo de las casillas coloreadas en rojo ya que

podemos juntar las esquinas. Con A negada y sin negar, con lo que nos

queda B’ y C como estamos con maxterms tomamos B y C’, es decir (B+C’)

00 01 11 10

0 0 0 0 1

1 0 0 1 0

Luego dado que maxterms es producto de sumas tenemos:

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

Que si hacemos distributiva nos queda

F=AB’B+AB’C’+ACB+ACC’=0+ AB’C’+ACB+0

Entonces

F= AB’C’+ACB

Que es la misma expresión que habíamos deducido.


ANEXO I:

Conjuntos: Comprobaciones gráficas

(Diagramas de Venn)

Ley asociativa para la intersección:

X (Y Z) = (X Y) Z

Diagramas:

Ley asociativa para la unión:

X U (Y U Z) = (X U Y) U Z

Mediante diagramas:

El sombreado representa Y U Z El sombreado representa X U (Y U Z)


El sombreado representa X U Y El sombreado representa (X U Y) U Z

Ley distributiva de la intersección respecto a la unión:

X (Y U Z) = (X Y) U (X Z)

Ley distributiva de la unión respecto a la intersección:

X U (Y Z) = (X U Y) (X U Z>

Esquema:

Al usar los diagramas de Venn hemos remarcado que ayudan a

comprobar la validez de las leyes. Por sí mismos, los diagramas de Venn no

constituyen una demostración definitiva, aunque sugieren el método a

seguir. Nos abstendremos de llevar a cabo tales demostraciones,

considerando como suficientes los diagramas reproducidos.


ANEXO II:

Un ejemplo de Lógica aplicada:

decodificador 7 segmentos.

A lo largo del trabajo hemos repetido la idea de la enorme importancia

que tiene para nuestra sociedad el Álgebra de Boole aplicada. Son grandes

palabras, y por ello pueden sonar exageradas.

Incluimos este Anexo para mostrar que no hay tal exageración. Todos

tenemos en casa un despertador digital o un video, cuyos dígitos se

caracterizan por estar formados a partir de segmentos, tal como muestra la

figura:

Como vemos, cada segmento tiene asignada una letra minúscula y el

conjunto se conoce como "decodificador de 7 segmentos".

Algo tan simple a primera vista lleva tras de sí todo un dispositivo lógico

de cierta envergadura. Para no complicamos, vamos a diseñar solamente el

dispositivo que "enciende" el segmento "a”.

Para comenzar, hemos de determinar cuántas "variables entrada"

necesitamos para indicarle a “a” que se encienda o no en todos los números

posibles. Como los números posibles son 10 y para cada número

necesitamos que “a” reciba la orden de encenderse o no debemos construir

una función en cuya tabla de verdad haya por lo menos 10 filas. Si tenemos

cierta práctica con las tablas de verdad, sabemos que el número de filas

viene determinado por 2n .donde n es el número de variables de entrada.

Por lo tanto la función deberá tener como mínimo 4 variables de entrada

(pues es la primera potencia de 2 que sobrepasa el valor “10" es 4 y el valor

es 16). Efectuado esto, construimos la tabla teniendo presente que F debe

valer 1 cuándo debe encenderse el segmento "a": es decir en 0. 2. 3. 5. 6. 7. 8

y 9. La tabla queda del siguiente modo:


Decimal X1 X2 X3 X4 F

0 0 0 0 0 1

1 0 0 0 1 0

2 0 0 1 0 1

3 0 0 1 1 1

4 0 1 0 0 0

5 0 1 0 1 1

6 0 1 1 0 1

7 0 1 1 1 1

8 1 0 0 0 1

9 1 0 0 1 1

10 1 0 1 0 ¿?

11 1 0 1 1 ¿?

12 1 1 0 0 ¿?

1a 1 1 0 1 ¿?

14 1 1 1 0 ¿?

15 1 1 1 1 ¿?

Los valores indicados con "¿?" tanto de la tabla como del

correspondiente mapa de Kamaugh indican "estados indiferentes” ya que

son órdenes que como 10 a 15 nunca se mostrará en el display de 7

elementos, entonces son órdenes que nunca se darán, por lo tanto da lo

mismo qué ordenes sean. Podemos suponer que son todos unos, para

simplificar:

00 01 11 10

00 1 0 1 1

01 0 1 1 1

1 1 1 1 1 1

10 1 1 1 1


A partir del mapa obtendremos la función booleana del segmento "a" ya

simplificada, X1 X2 en la fila de arriba X3 X4 en la primera columna

(Conviene maxterms ¿sabe Ud. porqué?). Nos queda la función:

F= X1+X3+(X2 X4)+ (X’2 X’4)

Para acabar aquí ofrecemos el esquema de la función que hemos

obtenido:

Cuando se den las condiciones exigidas por la tabla de verdad, se

iluminará el LED (Light Emission Diode) correspondiente al segmento *a".

Como vemos, se trata un tema harto complejo: para lograr la formación

de un dígito entero, tendríamos que conocer las tablas, mapas y esquemas

del resto de segmentos, y relacionarlos de modo que actuasen

coordinadamente. Por no hablar, si pretendiésemos hacer que contara, al

modo de un reloj... Valga esto como muestra de que sólo una herramienta

potente y (relativamente) simple ha podido propiciar la revolución digital

de finales de siglo XX.


Bibliografía Lectura 4

Arnold, R. "Logic and Boolean Álgebra'. Prentice-Hall, New York, 1962.

Bochénski, I. "Historia de la Lógica formal". Editorial Gredos, Madrid, 1967.

Breuer, S. "Introduction to the theory of sets". Prentice-Hall, New York, 1958.

Cuesta, L. "Electrónica digital". Editorial McGraw-Hill, Madrid, 1992.

Freudenthal, G. "The language of Logic". Elsevier, London, 1966.

Goodstein, D. "Boolean algebra". Pergamon, Oxford, 196a.

Hoernes, G. "Introducción al algebra de Boole y a los dispositivos lógicos".

Edítohal Paraninfo, Madrid, 1972.

Kneale, W. y M. "El desarrollo de la lógica". Editorial Tecnos, Madrid, 1972.

Shin, S. "The logical status of diagrams". Cambndge University Press, Cambridge,

1994.

Stall, T. "Sets, logic and axiomatic theohes". Freeman, New York, 1961.

Vega, L. "Una guía de historia de la lógica". Uned, Madhd, 1996.

Whitesitt, J. "Boolean algebra and its applications". Addison Wesley, Reading

(Mass.), 1961.

www.uesiglo21.edu.ar

teorías de los conjuntos y circuitos lógicos_lectura_m4

Documents