Capítulo X: Aplicaciones de la teoría de conjuntos.

 

 

11.1. ÁLGEBRA DE CONJUNTOS.

 

Definiciones

Dado un conjunto A={a, b, c, d}, la relación de pertenencia se representa por a Î A.

Se llama cardinal del conjunto, y se representa car(A), al número de elementos que contiene.

Se llama conjunto vacío, y se representa por Æ, al conjunto que no contiene ningún elemento. No desespere, estamos de acuerdo en que si no contiene ningún elemento, no es un conjunto, sin embargo su definición como tal es muy útil.

Se llama universo o conjunto universal, y se suele representar por H, al conjunto formado por todos los elementos que se están considerando.

Dado un conjunto A, se llama complementario del mismo, y se representa por Ac, al conjunto formado por los elementos del universo que no son de A.

Dos conjuntos son iguales si están formados por los mismos elementos.

Se dice que B es subconjunto de A, y se representa B Ì A, si todos los elementos de B pertenecen a A. Se dice también que B está incluido en A.

Dados dos conjuntos A y B, se llama unión de ambos, y se representa A È B, al conjunto formado por los elementos que pertenecen a A o a B.

Ejemplo 1: A={a, b, c, d} B={c, d, e, h}

A È B = {a, b, c, d, e, h}

Ejemplo 2: C={personas obesas} D={personas hipertensas}

C È D = {personas obesas o hipertensas}

Se llama intersección y se representa A Ç B, al conjunto formado por los elementos que pertenecen a A y a B.

Ejemplo 3: para los conjuntos anteriores

A Ç B = {c, d} C Ç D = {hipertensos y obesos}

Si dos conjuntos no tienen elementos comunes, se llaman disjuntos y su intersección es el conjunto vacío. Si, para el ejemplo 2, en el universo que se está considerando no hay nadie que sea hipertenso y obeso C Ç D = Æ

Al conjunto formado por todos los subconjuntos de un conjunto dado se le denomina conjunto de las partes del conjunto o álgebra y se representa por P(A)

Ejemplo: A = {1, 2, 3}

P(A) = {Æ , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

Propiedades

10.1.1. Propiedades de la inclusión

i) A Ì A

ii) Æ Ì A

iii) A Ì B Þ B Ë A ; sólo si A = B

iv) A Ì B y B Ì D ==> A Ì D

 

10.1.2. Propiedades de la unión e intersección
 

i) Identidad

A È Æ = A

A ÇH = A

ii) Idempotencia

A È A = A

A Ç A = A

iii) Commutatividad

A È B = B È A

A Ç B = B Ç A 

iv) Asociatividad

(A È B) È D = A È (B È D)

(A ÇB) Ç D = A Ç (B Ç D)

v) Distributividad

(A È B) Ç D= (A ÇD) È (B Ç D)

(AÇB)È D = (A È D) Ç (B È D)

vi) Absorción

A È (A Ç B) = A

A Ç (A È B) = A

vii) Complementaridad

 

A È Ac = H

A Ç Ac = Æ

 

Nota: A todo conjunto en el que se hayan definido dos operaciones que tengan estas propiedades, se le denomina Álgebra de Bolee.

Función de conjunto: toda regla que de un modo perfectamente determinado haga corresponder un número real a cada elemento del conjunto. Se representa por   f: A ® Â

el número x que le corresponde al elemento a, se representa por x=f(a)

Se denomina imagen de la función al conjunto de números que están en correspondencia con algún elemento, a través de la función.

 

im f = { x ÎÂ; a Î A , f(a)=x }

 

10.2. ÁLGEBRA BOOLEANA.

 

A mediados del siglo pasado George Boole desarrolló una teoría matemática completamente distinta a la que entonces se conocía y cuya expansión ha sido tan rápida que en la actualidad se aplica a la resolución y análisis de la mayoría de las operaciones industriales complejas. Igualmente ha pasado a ser parte importante en el equipo físico y en la programación de las modernos computadoras.

Para la resolución de problemas, el álgebra de Boole establece una serie de postulados y operaciones lógicas, que son implementadas por elementos físicos de tipo mecánico, eléctrico, neumático o electrónico.

Todos los elementos que contempla el álgebra de Boole (constantes y variables) sólo admiten dos estados, es decir, se comportan como magnitudes digitales bivalentes. Además, dichos estados tienen un carácter opuesto. Así, por ejemplo, a una lámpara corriente(tubo fluorescente) el álgebra de Boole sólo la considera en uno de los dos estados posibles y opuestos: encendida o apagada. No se admiten estados intermedios. A uno de los dos estados posibles (lámpara encendida), se le denomina de diversas formas tales como: Verdadero, Estado Alto, Nivel Lógico 1, etc... Al otro estado (lámpara apagada), se le referencia con palabras opuestas tales como; Falso, Estado Bajo, Nivel Lógico 0, etc.

Todos los elementos tratados por el álgebra de Boole se contemplan con la posibilidad de aceptar dos estados. Así, un interruptor puede estar "abierto" o "cerrado", un diodo "conduciendo" o "bloqueado", un transistor "saturado" o "bloqueado" .

La posibilidad de que todos los elementos admitan dos estados en este "Tipo de Álgebra" ha llevado a llamarla "álgebra binaria". La denominación de "álgebra lógica" se debe al carácter intuitivo y lógico que tienen los razonamientos que en ella se aplican.

En el álgebra de Boole, las variables y constantes binarias de entrada y salida se suelen expresar con las letras del alfabeto. Además, sus operaciones se expresan con signos muy similares a los empleados en las operaciones matemáticas clásicas, como la suma y la multiplicación. De esta forma se pueden manejar ecuaciones lógicas ligando las variables y constantes de entrada mediante ciertas operaciones para expresar el valor de las variables de salida del sistema.

En la implementación de las ecuaciones lógicas que resuelven los procesos en los que se aplica el álgebra de Boole, se utilizan diversas operaciones o funciones lógicas entre las que se citan las tres fundamentales:

 

Función AND o Producto Lógico

Función OR o Suma Lógica

Función NOT o Negación Lógica

 

10.2.1. Función Lógica AND. Puerta AND

Cuando varias variables lógicas, de tipo binario, se combinan mediante la operación lógica AND, producen una variable de salida, que sólo toma el nivel lógico 1 o estado alto o verdadero, si todas ellas tienen dicho nivel o estado.

La operación lógica AND también recibe el nombre de producto lógico porque se representa mediante un punto, igual que la operación convencional de multiplicación. Asimismo, recibe la

denominación de operación Y en castellano, pues con dicha letra se expresa la relación que debe existir entre las variables de entrada para que sea "verdadera" la salida. Por ejemplo, si se dispone de dos variables lógicas A y B, para que el resultado de combinarlas mediante la función AND genere un resultado X verdadero, se dice que A "y" B deben ser verdaderas o tener un nivel lógico 1.

La expresión simbólica de dicha ecuación en el álgebra de Boole es la siguiente:

 

Ecuación lógica de la función AND para dos variables de entrada

 

X = A · B

Para representar una ecuación lógica de forma clara y completa se usa un gráfico denominado Tabla de Verdad, que consiste en una tabla cuyas columnas de la parte izquierda representan todas las combinaciones posibles que pueden tomar las variables de entrada. En la columna derecha se indica el valor que toman las salidas para cada combinación de las entradas. En el caso de la ecuación X=A·B, existen dos entradas (A, B) y un sola salida (X). El número de combinaciones diferentes, N, que se pueden realizar con a variables binarias viene expresado por la fórmula N = 2ª , que en el ejemplo citado, dará lugar a N = 2 x2 = 4 combinaciones posibles. En consecuencia, la tabla de verdad dispondrá de 4 combinaciones diferentes para las dos entradas y, para cada una de ellas, (en la columna de la derecha) se expresará el valor que toma la salida tal como se expresa a continuación:

 

 

 

Tabla de verdad que describe la ecuación lógica X=A.B

 

VALOR EN LA PARTE A

VALOR EN LA PARTE B

VALOR OBTENIDO EN LA

SALIDA

0

0

0

0

1

0

1

0

0

1

1

1

 

 

 

10.2.2. Función Lógica OR ó Puerta OR

 

Cuando distintas variables lógicas se combinan mediante la función OR, el resultado toma el estado ALTO si alguna de ellas tiene dicho estado.

La operación OR es menos exigente que la AND por que sólo exige que alguna de las variables de entrada valga 1, para que la salida tome ese nivel. A la función OR también se le denomina Suma Lógica ya que se representa con el símbolo suma (+). En castellano recibe el nombre de operación O, puesto que la salida vale sólo 1 solo si presenta dicho valor la entrada A "o" la B. La ecuación que representa la función OR de dos variables de entrada es la siguiente:

 

10.2.3. Ecuación lógica de la función OR para dos variables de entrada

 

X= A + B

A continuación se representa la tabla de verdad que representa a la ecuación anterior.

 

Tabla de verdad que describe la ecuación lógica X = A + B

 

VALOR EN LA PARTE A

VALOR EN LA PARTE B

VALOR OBTENIDO EN LA

SALIDA

0

0

0

0

1

1

1

0

1

1

1

1

 

 

10.3. FUNCIÓN LÓGICA NOT. PUERTA NOT O INVERSOR

 

Se trata de una operación que sólo maneja una variable de entrada y otra de salida. La salida toma el estado opuesto o inverso del que tiene la entrada. Por este motivo, también se la Función Inversión o negación. En castellano recibe el nombre de operación NO.

La siguiente figura muestra la ecuación lógica de la función NOT, su tabla de verdad y el símbolo usado para la representación de la puerta NOT.

 

Tabla de Verdad de la Puerta Inversora NOT

 

Entrada

Salida

0

1

1

0

 

ejecución de una doble inversión mediante dos puertas NOT equivale a una afirmación, es decir, a obtener en la salida el mismo valor que el que tiene la variable de entrada.

 

10.4. OTRAS PUERTAS LÓGICAS...

 

10.4.1. PUERTA LÓGICA NAND

La Puerta NAND produce la función inversa de la AND, o sea, la negación del producto lógico de las variables de entrada. Actúa como una puerta AND seguida por un NOT. En la siguiente figura se muestra el símbolo de la puerta NAND y, a continuación su tabla de verdad.

 

 

 

VALOR EN LA PARTE A

VALOR EN LA PARTE B

VALOR OBTENIDO EN LA

SALIDA

0

0

1

0

1

1

1

0

1

1

1

0

 

De análisis de la tabla de verdad de una puerta NAND se deduce que su salida es siempre vale 1, excepto cuando todas sus entradas toman el valor lógico 1.

 

10.4.2. PUERTA LÓGICA NOR

 

Esta Puerta produce la función inversa de la puerta OR, es decir, la negación de la suma lógica de las variables de entrada. Su comportamiento es equivalente al de la puerta OR seguida de una NOT. En la siguiente figura se muestra el símbolo lógico y la tabla de verdad para una puerta NOR de dos entradas.

 

VALOR EN LA PARTE A

VALOR EN LA PARTE B

VALOR OBTENIDO EN LA

SALIDA

0

0

1

0

1

0

1

0

0

1

1

0

 

De la tabla de Verdad de una función NOR se desprende que su salida siempre tiene nivel lógico bajo, excepto cuando todas sus entradas tienen nivel bajo, en cuyo caso la salida vale 1. Se dice que NOR "es un detector de entradas a 0", porque sólo en esa situación saca un 1. La NAND es un "detector de entradas a 1" por que solo dicha combinación produce en su salida un 0.

 

 

10.5. EXPRESIONES LÓGICAS BOOLEANAS Y TABLAS PARA REPRESENTARLAS

 

El álgebra Booleana difiere de la álgebra decimal en que las constantes y las variables usadas en el álgebra Booleana sólo pueden tomar dos posibles valores, ya sea un cero lógico, o bien un uno lógico, o sea una variable Booleana puede tomar valores de cero o de uno, siendo así, que las variables Booleanas no representan números en realidad, sólo representan el estado de una variable de voltaje, o bien lo que se conoce como su nivel lógico, en la lógica digital se emplean otros términos que son sinónimos de 0 y 1, como se mencionan en la tabla siguiente.

 

0 Lógico

1 Lógico

Falso

Verdadero

desactivado

Activado

Bajo

alto

No

si

Interruptor abierto

Interruptor cerrado

 

La forma de manejar la lógica binaria es por medio de expresiones matemáticas; estas expresiones se denominan Booleanas. El álgebra Booleana es como cualquier otro sistema matemático deductivo.

El álgebra Booleana se aprovecha para expresar y simular los efectos que los diversos circuitos digitales ejercen sobre las entradas lógicas, y para manipular variables lógicas con el objeto de determinar el mejor método de ejecución de cierta función.

Ya que sólo puede haber dos valores, el álgebra Booleana es relativamente fácil de manejar, comparándola con el álgebra ordinaria. En el álgebra Booleana, no hay fracciones, números negativos, raíces cuadradas, raíces cúbicas, logaritmos, números imaginarios ni nada de esas operaciones que empleamos en el álgebra decimal

 

10.6. ÁLGEBRA BOOLEANA DE DOS VALORES


 

X

Y

X+Y

X.Y

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

10.6.1. TABLAS DE VERDAD

 

Muchos circuitos lógicos tienen más de una entrada y sólo una salida, una tabla de verdad muestra la forma en que la salida del circuito lógico responde a las diversas combinaciones de niveles lógicos en las entradas.

En cada tabla de verdad, las combinaciones posibles de niveles lógicos 0 y 1 para las entradas se listan en el lado izquierdo, y el nivel lógico resultante para la salida se lista a la derecha.

El número de combinaciones de entrada será igual a 2 a la N para una tabla de verdad de N entradas.