1
Download introducción
Document related concepts
Transcript
FIA-2010-I
Matemáticas Discreta
I. SISTEMA NUMÉRICO BINARIO Y CÓDIGOS DE COMPUTADOR
Introducción
Los sistemas numéricos más antiguos son: Babilónico, Romano, Hindú, Árabe.
El sistema numérico hindú y árabe son los que han llegado hasta nuestros días; es lo que
conocemos como sistema numérico decimal (de base 10), siendo el de uso más
extendido en todo el mundo.
Debido al extendido uso del sistema decimal muchas personas desconocen la existencia
de otros sistemas numéricos como, por ejemplo, el binario (de base 2), el octal (de base
8) y el hexadecimal (de base 16), entre otros.
Con el surgimiento de los ordenadores o computadoras personales (PCs), los ingenieros
informáticos se vieron en la necesidad de adoptar un sistema numérico que le permitiera
a la máquina funcionar de forma fiable. Debido a que el sistema numérico decimal
resultaba complejo para crear un código apropiado, adoptaron el uso del sistema
numérico binario (de base 2), que emplea sólo dos dígitos: “0” y “1”.
Digito: Es un signo que representa una cantidad contable. Dependiendo del sistema de
numeración, serán los diferentes signos que se tenga para representar cualquier
cantidad.
Numero: Es la representación de una cantidad contable por medio de uno o más dígitos.
Sistemas de numeración
Un sistema de numeración es un conjunto de símbolos y reglas que se utilizan para
representar y operar con cantidades.
Los sistemas de numeración actuales son sistemas posicionales, en los que el valor que
representa cada símbolo o cifra, depende de su valor absoluto y de la posición relativa
que ocupa la cifra con respecto al resto.
Se entiende por base (b) de un sistema de numeración al número de símbolos que se
utilizan para la representación.
Ejemplo:
1
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
BASE
NUMÉRICA
DÍGITOS EMPLEADOS
Binaria(2)
0y1
2
Octal(8)
0, 1, 2, 3, 4, 5, 6 y 7
8
Decimal(10)
0, 1, 2, 3, 4, 5, 6, 7, 8 y 9
10
Hexadecimal(16) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E y F
CANTIDAD
TOTAL
16
Como se podrá observar, el dígito de mayor valor en el sistema numérico binario es el
1, en el octal el 7, en el decimal el 9 y en el hexadecimal la letra F, cuyo valor numérico
es igual a 15.
Sistema de numeración decimal
El sistema que cotidianamente utilizamos es el decimal, cuya base es el número 10
porque se emplean diez dígitos para representar cualquier cifra. Ellos son:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
En este sistema un número puede descomponerse en potencias de 10
Así, por ejemplo, el número 657 se puede descomponer de la siguiente manera:
657 = 600 + 50 + 7 = 6 100 + 5. 10 + 7 1
Al número 10 se le denomina base del sistema.
Es fácil deducir que un número N (10) = a b c d puede descomponer en
N(10) = a 103 + b 102 + c 101 + d 100
Por otra parte,
657,25 = 600 + 50 + 7 = 6 100 + 5 10 + 7 1 + 2 .1/10 + 5 .1/100
y, en general,
N(10) = ab n+1...d m. ef.z = a10n+ b 10n-1 + ... + d10° + e10 -1+f 10 -2+ ... + z.10-m
Esto es aplicable para cualquier sistema de numeración de base B.
2
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
SISTEMA BINARIO
El sistema binario o de numeración de base dos, fue introducido por Leibniz en el siglo
XVII, y se ha utilizado en las máquinas electrónicas porque se basa en dos estados (base
dos) estables el 0 y el 1 (apagado y encendido) que utiliza el hardware de las
computadoras
Este sistema de numeración utiliza solamente dos símbolos (0, 1); normalmente se le
denomina sistema de numeración en base 2 o binario natural.
A cada dígito binario se denomina BIT. (BIT: binary digit)
Bit
byte
Kilobyte
Megabyte
Gigabyte
bit
1
8
8,192
8,388,608
8,589,934,592
byte
8
1
1,024
1,048,576
1,073,741,824
Kilobyte
8,192
1,024
1
1,024
1,048,576
Megabyte 8,388,608
1,048,576
1,024
1
1,024
Gigabyte 8,589,934,592
1,073,741,824
1,048,576
1,024
1
Terabyte 8,796,093,022,208
1,099,511,627,776
1,073,741,824
1,048,576
1,024
Peta byte 9,007,199,254,740,990
1,125,899,906,842,620
1,099,511,627,776
1,073,741,824
1,048,576
Exabyte
1,152,921,504,606,850,000
1,125,899,906,842,620
1,099,511,627,776
1,073,741,824
9,223,372,036,854,780,000
Zettabyte 9,444,732,965,739,290,000,000 1,180,591,620,717,410,000,000 1,152,921,504,606,850,000 1,125,899,906,842,620 1,099,511,627,776
Un número en el sistema binario se divide en cifras con diferente peso: 1, 2, 4, 8, 16, 32,
64, 128,.... etc.
Ver el siguiente gráfico
1
0
1
0
23
22
21
20
Multiplicador
(0,1)
Potencia de 2
Peso 1
Peso 2
Peso 4
Peso 8
3
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Cada peso tiene asociado una potencia de 2. En el primer número (de derecha a
izquierda) la potencia de dos es 20, en el segundo número la potencia de dos es 21 y así
hasta el último número del lado izquierdo.
Entonces para formar el número 1010(2) a decimal:
1 x 23
=1x8=8
8
2
=0x4=0 +
0
1
1x2
=1x2=2 +
2
0 x 20
=0x1=0 +
equivalente
decimal ----- =
->
0
0x2
10
Los pesos fraccionarios son 1/2, 1/4, 1/8, etc., que corresponden a 2-1, 2-2, 2-3, etc.
La Tabla siguiente muestra algunos números pertenecientes a este código y su
correspondencia
Código
decimal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Código binario
natural
16 8 4 2 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
24 23 22 21 20
4
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejemplo 1:
Para transformar 110101(2), escriba el valor posición sobre cada bit, y luego sume
aquellas potencias que están ponderadas por 1:
26
25
24
23
22
21
20
64
32
16
8
4
2
1
1 1
0
1
0
1
26
25
24
23
22
21
20
64
32
16
8
4
2
1
0
1
1
0
1
0
1
32+16+4+1=53(10)
Ejemplo 2:
Convertir 101.1101(2) a su equivalente decimal
22
21
20
2-1
2-2
2-3
2-4
4
2
1
0.5
0.25
0.125
0.0625
1
1
0
1
1
0
1
4+1+0.5+0.25+0.0625= 5.8125
Ejercicios:
1. Convertir los siguientes números binarios al sistema decimal:
a.
b.
c.
d.
11100111
0.10101
11.0101
11111
5
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
128
64
32
16
8
4
2
1
1
1
1
0
0
1
1
1
1
a.
b.
c.
d.
1
1
1
1
1
1
0.5 0.25 0.125 0.0625 0.03125
1
0
1
0
0
1
0
1
1
128 + 64 + 32 + 4 + 2 + 1 =231(10)
0.5 + 0.125 + 0.03125 =0.65625(10)
2 + 1 + 0.025 + 0.0625 =3.3125(10)
16 + 8 + 4 + 1 = 31(10)
Conversión de decimal a binario
Seguidamente realizaremos la operación inversa, es decir, convertir un número
perteneciente al sistema numérico decimal (base 10) a un número binario (base 2). Por
ejemplo utilizamos primero el número 189 como dividendo y el 2, correspondiente a la
base numérica binaria del número que queremos hallar, como divisor. A continuación el
resultado o cociente obtenido de esa división (94 en este caso), lo dividimos de nuevo
por 2 y así, continuaremos haciendo sucesivamente con cada cociente que obtengamos,
hasta que ya sea imposible continuar dividiendo. Veamos el ejemplo:
Una vez terminada la operación, escribimos los números correspondientes a los residuos
de cada división en orden inverso, o sea, haciéndolo de abajo hacia arriba. De esa forma
obtendremos el número binario, cuyo valor equivale a 189, que en este caso será:
10111101(2)
6
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
Ejemplo: Convertir el número 428(10) en correspondiente binario.
Por tanto, 428(10) = 110101100(2)
Si el número decimal tiene parte fraccionaria, la parte entera se convierte de la misma
manera que se ha expuesto anteriormente y la parte fraccionaria se multiplica por 2; la
parte entera obtenida es la cifra más significativa del número. Si la parte fraccionaria
restante se vuelve a multiplicar por 2, la nueva parte entera será la siguiente cifra más
significativa, y así sucesivamente.
Ejemplo:
Convertir el número 327,625(10) en binario.
327,625(10) = 327(10) + 0,625(10)
La parte entera es 327 (10) que pasándola al binario, resulta
7
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Para obtener la parte fraccionaria se procede de la siguiente manera:
Por tanto, la parte fraccionaria será
0,625 (10) = 0,101 (2)
Entonces: 327,625 (10) = 101000111,101 (2)
Ejercicio:
Convertir 13.6875 (10) a sistema binario
23
22
21
20
2-1
2-2
2-3
2-4
8
4
2
1
0.5
0.25
0.125
0.0625
1
1
1
1
1
0
1
8 + 4 + 1 = 13
8
4
2
1
0.5
0.25
0.125
0.0625
1
0
1
1
1
0
0.5+0.125+0.0625= 0.6875
1
1
0
1
1
1
Luego: 13. 6875(10) =1101.1011(2)
8
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejercicios:
Convertir los siguientes números decimales al sistema binario
a)
b)
c)
d)
49
0.375
75.125
158
Reptas:
a) 110001
b) 0.011
c) 1001011.001
d) 10011110
Operaciones en el sistema binario
Introducción
La Unidad Aritmético Lógica, en el CPU del procesador, es capaz de realizar
operaciones aritméticas, con datos numéricos expresados en el sistema binario.
Naturalmente, esas operaciones incluyen la adición, la sustracción, el producto y la
división. Las operaciones se hacen del mismo modo que en el sistema decimal, pero
debido a la sencillez del sistema de numeración, pueden hacerse algunas
simplificaciones que facilitan mucho la realización de las operaciones.
Suma en Binario
Para aprender a sumar, con cinco o seis años de edad, tuviste que memorizar las 100
combinaciones posibles que pueden darse al sumar dos dígitos decimales. La tabla de
sumar, en binario, es mucho más sencilla que en decimal. Sólo hay que recordar cuatro
combinaciones posibles:
+
0
1
0
0
1
1
1
0+1
Las sumas 0 + 0, 0 + 1 y 1 + 0 son evidentes:
0+0=0
0+1=1
1+0=1
Pero la suma de 1+1, que sabemos que es 2 en el sistema decimal, debe escribirse en
binario con dos cifras (10) y, por tanto 1+1 es 0 y se arrastra una unidad, que se suma a
la posición siguiente a la izquierda. Veamos algunos ejemplos:
9
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
010 + 101 = 111(2) = 2(10) + 5(10) = 7(10)
001101 + 100101 = 110010(2)
13(10) + 37(10) = 50(10)
1011011 + 1011010 = 10110101(2)
91(10) + 90(10) = 18(10)
110111011 + 100111011 = 1011110110
443(10)
+ 315(10) = 758(10)
Ejercicio 1:
Realiza las siguientes sumas de números binarios:
111011 + 110
111110111 + 111001
10111 + 11011 + 10111
Sustracción en Binario
La técnica de la resta en binario es, nuevamente, igual que la misma operación en el
sistema decimal. Pero conviene repasar la operación de restar en decimal para
comprender la operación binaria, que es más sencilla. Los términos que intervienen en
la resta se llaman minuendo, sustraendo y diferencia.
-
0
1
0
0
1
1
1+1
0
Las restas 0 - 0, 1 - 0 y 1 - 1 son evidentes:
0–0=0
1–0=1
1–1=0
La resta 0 - 1 se resuelve, igual que en el sistema decimal, tomando una unidad prestada
de la posición siguiente: 10 - 1, es decir, 2(10) – 1(10)= 1. Esa unidad prestada debe
devolverse, sumándola, a la posición siguiente.
Veamos algunos ejemplos:
111 – 101 = 010
= 7(10) – 5(10) = 2(10)
10
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
10001 – 01010 = 00111
17(10) – 10(10) = 7(10)
11011001 – 10101011 = 00101110
217(10) – 171(10) = 46(10)
111101001 – 101101101 = 001111100 489(10) – 365(10) = 124(10)
Ejercicio 2:
Realiza las siguientes restas de números binarios y comprueba los resultados
convirtiéndolos al sistema decimal:
111011 - 110
111110111 - 111001
1010111 - 11011 – 10011
A pesar de lo sencillo que es el procedimiento de restar, es fácil confundirse. Tenemos
interiorizado el sistema decimal y hemos aprendido a restar mecánicamente, sin
detenernos a pensar en el significado del arrastre. Para simplificar las restas y reducir la
posibilidad de cometer errores hay varias soluciones:
1) Dividir los números largos en grupos.
En el siguiente ejemplo, vemos cómo se divide una resta larga en tres restas
cortas:
100110011101
010101110010
010000101011
1001
0101
0100
1001
0111
0010
1101
0010
1011
2) Calculando el complemento a dos del sustraendo
a. Complemento a dos
El complemento a dos de un número N, compuesto por n bits, se define como:
C2N = 2n – N
Veamos un ejemplo:
Tomemos el número N = 1011012, que tiene 6 bits, y calculemos su complemento a
dos:
N = 4510 n = 6 26 = 64 y, por tanto:
C2N = 64 – 45 = 19 = 0100112
11
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejercicio 3:
Calcula el complemento a dos de los siguientes números:
11001
10001011
110011010
b. . Complemento a uno
El complemento a uno de un número N, compuesto por n bits es, por definición, una
unidad menor que el complemento a dos, es decir:
C 1N = C2N - 1
y, por la misma razón:
C2N = C1N + 1
Calculemos el complemento a uno del mismo número del ejemplo anterior:
siendo N = 101101, y su complemento a dos C2N = 010011
C1N = C2N – 1 = 010011 – 000001 = 010010
C1N = 010010
Da la sensación de que al calcular el complemento a uno no es más que una forma
elegante de complicarse la vida, y que no va a ser más sencillo restar utilizando el
complemento a dos, porque el procedimiento para calcular el complemento a dos es más
difícil y laborioso que la propia resta. Pero es mucho más sencillo de lo que parece.
En realidad, el complemento a uno de un número binario es el número resultante de
invertir los UNOS y CEROS de dicho número. Por ejemplo si:
N = 110100101
obtenemos su complemento a uno invirtiendo ceros y unos, con lo que resulta:
C1N = 001011010
y su complemento a dos es:
C2N = C1N + 1 = 001011011
Veamos otro ejemplo de cálculo de complementos.
Sea:
N = 0110110101
12
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
El complemento a uno es:
C1N = 1001001010
y el complemento a dos es:
C2N = 1001001011
Restar en binario usando el complemento a dos
La resta binaria de dos números puede obtenerse sumando al minuendo el complemento
a dos del sustraendo.
Veamos algunos ejemplos:
Primer ejemplo
Hagamos la siguiente resta, 91 – 46 = 45, en binario:
1011011 – 0101110 = 0101101
Tiene alguna dificultad, cuando se acumulan los arrastres a la resta siguiente
Pero esta misma resta puede hacerse como una suma, utilizando el complemento a dos
del sustraendo:
1011011 + 1010010 = 0101101
En el resultado de la suma nos sobra un bit, que se desborda por la izquierda. Pero,
como el número resultante no puede ser más largo que el minuendo, el bit sobrante se
desprecia.
Segundo ejemplo:
Hagamos esta otra resta, 219 – 23 = 196, utilizando el complemento a dos:
21910=110110112,
2310=000101112
C23 = 11101001
El resultado de la resta será:
11011011 + 11101001 = 111000100
Y, despreciando el bit que se desborda por la izquierda, llegamos al resultado correcto:
110001002 = 19610
13
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejercicio:
Haz las siguientes restas binarias utilizando la técnica del complemento a dos.
Al terminar, comprueba los resultados haciendo la resta en el sistema decimal:
11010001101 – 1000111101
10110011101 - 1110101
Método práctico (Complemento a dos)
Cuando el mayor número es negativo:
Realizar las siguientes operaciones:
a.
93(10) = 1011101(2)
-38(10) = 100110(2)
Complemento a dos de: 100110
011010
1011101
0 011010
1 110111
b.
38
- 93
Se cambia
carried (+) = +55
Complemento a dos de: 1011101
es: 0100011
0100110
0100011
0 1001001
No carried (-), se vuelve a sacar complemento a 2 del resultado: - 0110111 = -55
Resolver:
a. 526-343
b. 343-526
14
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Multiplicación Binaria
La multiplicación en binario es más fácil que en cualquier otro sistema de numeración.
Como los factores de la multiplicación sólo pueden ser CEROS o UNOS, el producto
sólo puede ser CERO o UNO. En otras palabras, las tablas de multiplicar del cero y del
uno son muy fáciles de aprender:
x
0
1
0
0
0
1
0
1
En un ordenador, sin embargo, la operación de multiplicar se realiza mediante sumas
repetidas. Eso crea algunos problemas en la programación porque cada suma de dos
UNOS origina un arrastre, que se resuelven contando el número de UNOS y de arrastres
en cada columna. Si el número de UNOS es par, la suma es un CERO y si es impar, un
UNO. Luego, para determinar los arrastres a la posición superior, se cuentan las parejas
de UNOS.
Veamos, por ejemplo, una multiplicación:
15
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
Ejercicio:
Haz las siguientes multiplicaciones binarias. Al terminar, comprueba los
resultados haciendo las multiplicaciones en el sistema decimal:
a. 10110101000101 x 1011
b. 10100001111011 x 10011
División Binaria
Igual que en el producto, la división es muy fácil de realizar, porque no son posibles en
el cociente otras cifras que UNOS y CEROS.
Consideremos el siguiente ejemplo, 42 : 6 = 7, en binario:
Se intenta dividir el dividendo por el divisor, empezando por tomar en ambos el mismo
número de cifras (100 entre 110, en el ejemplo). Si no puede dividirse, se intenta la
división tomando un dígito más (1001 entre 100).
Si la división es posible, entonces, el divisor sólo podrá estar contenido una vez en el
dividendo, es decir, la primera cifra del cociente es un UNO. En ese caso, el resultado
de multiplicar el divisor por 1 es el propio divisor. Restamos las cifras del dividendo del
divisor y bajamos la cifra siguiente.
El procedimiento de división continúa del mismo modo que en el sistema decimal.
Ejercicio:
Haz las siguientes divisiones binarias. Al terminar, comprueba los resultados haciendo
las divisiones en el sistema decimal:
a. 10110101000101 : 1011
b. 10100001111011 : 10011
16
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
El Sistema Octal (base 8)
Representar un número en sistema binario puede ser bastante difícil de leer, así que se
creó el sistema octal. En el sistema Octal (base 8), sólo se utilizan 8 cifras
(0,1,2,3,4,5,6,7)
Este Sistema de numeración una vez que se llega a la cuenta 7 se pasa a 10, etc.
Cuenta hecha en octal: 0,1,2,3,4,5,6,7,10,11,12,13,14,15,16,17,20,21,..... se puede
observar que en este sistema numérico no existen los números: 8 y 9
Para pasar del un sistema binario al octal se utiliza el siguiente método:
- Se divide el número binario en grupos de 3 empezando por la derecha. Si al final
queda un grupo de 2 o 1 dígitos, se completa el grupo de 3 con ceros (0) al lado
izquierdo.
- Se convierte cada grupo en su equivalente en el Sistema octal y se reemplaza.
Ejemplo: 101101112 pasarlo a octal
Número en binario convertido a grupos de 3 010 110 111
2 6
7
Resultado: 101101112 = 2678
Equivalente en base 8
El Sistema Hexadecimal: (base 16)
El sistema hexadecimal, a diferencia del sistema decimal, necesita 16 cifras y/o letras
(0,1,2,3,4,5,6,7,8,9,A,B;C,D,E.F).Si se cuentan las letras y números anteriores se tienen
16.
Comparación de los números superiores a 9 en hexadecimal con su equivalente en
decimal.
A16 = 1010
B16 = 1110
C16 = 1210
D16 = 1310
E16 = 1410
F16 = 1510
Ver el siguiente gráfico
17
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Un número en el sistema hexadecimal se divide en cifras con diferente peso: 1, 16, 256,
4096, 65536,.... etc.
Entonces para formar el número AB516: (el número 2741 en hexadecimal)
= 10 x 256
= 2560
= 11 x 16
= 176
A x 162
B x 161
5 x 160
=5x1=5
equivalente
decimal ----->
2560
+
176
+
5
=
2741
Sistema Binario
Sistema Hexadecimal
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Relación entre el sistema binario y el hexadecimal
El Sistema hexadecimal es una abreviación del Sistema Binario.
Si a cada cifra de un número Hexadecimal se lo reemplaza por su equivalente en
binario, se habrá convertido el número en hexadecimal a número binario.
Ejemplo:
9B16 = 10012 10112.
Donde 92 = 10012 y B16 = 10112
18
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
Cuatro (4) cifras binarias se reemplazan por una (1) cifra hexadecimal. De esta manera
se puede convertir un número en base 16 a uno en base 2.
También se puede convertir un número binario en uno hexadecimal de la siguiente
manera.
Se separa el número binario en grupos de 4 dígitos empezando por la derecha. Si al final
queda un grupo de 3 dígitos o menos, se completa el grupo de 4 con ceros (0) al lado
izquierdo.
Se busca el equivalente en base 16 de cada uno de los grupos y se reemplaza
Nota: 9B16 = 9BH
La conversión de hexadecimal a binario simplemente sustituiremos cada carácter por su
equivalente en binario, por ejemplo:
69DE16= 0110 1001 1101 11102
19
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
EJERCICIOS PROPUESTOS
1. Pasar de binario a octal
a) 1110101012
Solución: 7258
b) 11011, 012
Solución: 33,28
2. Pasar de octal a binario
a) 20668
b) 142768
Solución: 0100001101102
Solución: 0011000101111102
3. Pasar de binario a hexadecimal
a) 1100010002
b) 100010,1102
Solución: 18816
Solución: 22,C
4. Para pasar de hexadecimal a binario
a) 86BF16
b) 2D5E16
Solución: 10000110101111112
Solución: 00101101010111102
5. Para pasar de octal a decimal
a) 1068
b) 7428
Solución: 7010
Solución: 482108
6. Pasar de decimal a octal:
a) 23610
Solución: 3548
b) 5274610
Solución: 1470128
20
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
SISTEMAS DE CODIFICACION
Introducción
Las computadoras no se comunican entre sí en español, inglés o francés. Tienen sus
propios lenguajes, que son más adecuados para la comunicación electrónica. En estos
lenguajes, los bits se combinan de acuerdo con un sistema de codificación para
representar letras (caracteres alfabéticos), números (caracteres numéricos) y caracteres
especiales (como *, $,+ y &).
Sistemas de Codificación Binaria
Los Sistemas de codificación establecen la secuencia de bits que son necesarios para
que la computadora pueda almacenar la información que es ingresada (previo al
procesamiento).
Observaciones:
1. Es importante entender la diferencia entre la conversión de un número decimal
en binario y la codificación en Sistema binario de un número decimal. En cada
caso el resultado final es una cadena de bits.
2. Los bits que se obtienen de la conversión son dígitos binarios.
3. Los bits que se obtienen de la codificación son combinaciones de unos y ceros
dispuestos de acuerdo con las reglas del código usado.
4. Es importante entender que una cadena de bits en una computadora representa a
veces un número binario y en otras ocasiones una cadena de bits representa otra
información, especificada por un código binario dado.
Sistemas de codificación decimales
Un sistema de codificación decimal es aquel que permite codificar el conjunto de
números decimales (Diez dígitos).
Para representar el conjunto de números decimales necesitamos al menos cuatro bits
(24=16). Es decir tenemos 16 posibles combinaciones, de las cuales seis se mantendrán
no asignadas.
Decimal codificado en binario BCD
El código que se utiliza mas comúnmente para representar los dígitos decimales es la
Asignación Binaria Directa y se conoce comúnmente como BCD Decimal Codificado
en Binario, según se representa en la siguiente tabla:
21
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Decimal Codificado en Binario (BCD)
Símbolo
decimal
0
1
2
3
4
5
6
7
8
9
Dígito
BCD
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
La tabla anterior muestra el código de cuatro bits para un dígito decimal. Un número
con “n” dígitos decimales requerirá 4n bits en BCD.
Por ejemplo el número decimal 396 se representa en BCD con 12 dígitos como 0011
1001 0110, donde cada grupo de cuatro bits es un dígito decimal.
Un número decimal en BCD es el mismo que su número binario equivalente solo
cuando el número esta entre 0 y 9. Un número BCD mayor que 10 se ve diferente de su
número binario equivalente aunque ambos contengan unos y ceros (1 y 0).
Además, las combinaciones binarias de la 1010 a la 1111 no se utilizan y no tienen
significado alguno en el código BCD.
Considérese el número decimal 185 y su valor correspondiente en BCD y en binario
(en forma directa):
(185)10 = (0001 1000 0101)BCD = (10111001)2
Ejercicios: Decodifique cada número, expresado en el código BCD.
a) 0111 0011 0000 1001
b) 0101 1000 0010
c) 0100 1010 0110
Solución:
a) 7309
b) 582
c) Como 10 no es un dígito debe haber un error en la codificación
Es importante entender que los números BCD son números decimales y no números
binarios, aunque se representen en bits.
22
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
Sistemas de codificación alfanuméricos
Muchas aplicaciones de las computadoras digitales requieren manejar datos no solo de
números, sino también de letras. Por ejemplo, aplicaciones que manejen los nombres del
personal de una determinada empresa.
Para representar los nombres y otra información pertinente, es necesario formular un
código binario para las letras del alfabeto. Además, el mismo código binario debe
representar numerales y caracteres especiales como “$” y “*“.
Existen diversos códigos alfanuméricos. Entre los más importantes podemos mencionar:
ASCII: Codificación Estándar Americana para el Intercambio de Información (Se
pronuncia “aski” y es usado en la mayoría de las computadoras)
EBCDIC: Codificación Extendida de Intercambio Codificado en Binario Decimal (Se
pronuncia “ib-si-dic” y es usa general en computadoras grandes IBM).
Código de caracteres ASCII
El American Standard Code for Information Interchange (ASCII, Código Estándar
Americano para el Intercambio de Información) es un código alfanumérico
universalmente aceptado, que se usa en la mayoría de las computadoras y otros equipos
electrónicos.
La mayor parte de los teclados de computadora se estandarizan de acuerdo con el
código ASCII, y cuando se pulsa una letra, un número o un comando de control, es el
código ASCII el que se introduce en la computadora.
El código ASCII dispone de 128 caracteres que se representan mediante un código
binario de 7 bits. El código ASCII puede considerarse como un código de 8 bits en el
que el MSB (bit de mayor significación) siempre es 0
Código ASCII extendido
Además de los 128 caracteres ASCII estándar, existen 128 caracteres adicionales.
Debido a la popularidad de las computadoras, estos caracteres especiales del código
ASCII extendido se usan también en otras aplicaciones distintas a las de las PC, por lo
que se ha convertido en un estándar oficial.
Los caracteres del código ASCII extendido se representan mediante una serie de
códigos de 8 bits que van, en hexadecimal, del 80 hasta FF.
El código ASCII extendido está formado por caracteres que pertenecen a las siguientes
categorías generales:
1. Caracteres alfabéticos no ingleses
2. Símbolos de moneda no ingleses
3. Letras griegas
23
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
4. Símbolos matemáticos
5. Caracteres para gráficos
6. Caracteres para gráficos de barras
7. Caracteres sombreados.
Tabla del conjunto de caracteres del código ASCII extendido, junto con sus
representaciones decimal y hexadecimal.
Caracteres no imprimibles
Nombre
Dec
Hex
Car.
Nulo
0
00
NUL
Inicio de cabecera
1
01
SOH
Inicio de texto
2
02
STX
Fin de texto
3
03
ETX
Fin de transmisión
4
04
EOT
enquiry
5
05
ENQ
acknowledge
6
06
ACK
Campanilla (beep)
7
07
BEL
backspace
8
08
BS
Tabulador
horizontal
9
09
HT
Salto de línea
10
0A
LF
Tabulador vertical
11
0B
VT
Salto de página
12
0C
FF
Retorno de carro
13
0D
CR
Shift fuera
14
0E
SO
Shift dentro
15
0F
SI
de
16
10
DLE
Control dispositivo 1
17
11
DC1
Control dispositivo 2
18
12
DC2
Control dispositivo 3
19
13
DC3
Control dispositivo 4
20
14
DC4
neg acknowledge
21
15
NAK
Sincronismo
22
16
SYN
Escape
datos
línea
24
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Fin
transmitido
bloque
23
17
ETB
Cancelar
24
18
CAN
Fin medio
25
19
EM
Sustituto
26
1A
SUB
Escape
27
1B
ESC
Separador archivos
28
1C
FS
Separador grupos
29
1D
GS
Separador registros
30
1E
RS
Carácteres imprimibles
Dec
Hex
Car.
Dec
Hex
Car.
Dec
Hex
Car.
32
20
Espacio
64
40
@
96
60
`
33
21
!
65
41
A
97
61
a
34
22
"
66
42
B
98
62
b
35
23
#
67
43
C
99
63
c
36
24
$
68
44
D
100
64
d
37
25
%
69
45
E
101
65
e
38
26
&
70
46
F
102
66
f
39
27
'
71
47
G
103
67
g
40
28
(
72
48
H
104
68
h
41
29
)
73
49
I
105
69
i
42
2A
*
74
4A
J
106
6A
j
43
2B
+
75
4B
K
107
6B
k
44
2C
,
76
4C
L
108
6C
l
45
2D
-
77
4D
M
109
6D
m
46
2E
.
78
4E
N
110
6E
n
47
2F
/
79
4F
O
111
6F
o
25
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
48
30
0
80
50
P
112
70
p
49
31
1
81
51
Q
113
71
q
50
32
2
82
52
R
114
72
r
51
33
3
83
53
S
115
73
s
52
34
4
84
54
T
116
74
t
53
35
5
85
55
U
117
75
u
54
36
6
86
56
V
118
76
v
55
37
7
87
57
W
119
77
w
56
38
8
88
58
X
120
78
x
57
39
9
89
59
Y
121
79
y
58
3A
:
90
5A
Z
122
7A
z
59
3B
;
91
5B
[
123
7B
{
60
3C
<
92
5C
\
124
7C
|
61
3D
=
93
5D
]
125
7D
}
62
3E
>
94
5E
^
126
7E
Otros códigos alfanuméricos
EBCDIC es un código binario que representa caracteres alfanuméricos, controles y
signos de puntuación. Cada carácter está compuesto por 8 bits = 1 byte, por eso
EBCDIC define un total de 256 caracteres.
EBCDIC tiene los mismos símbolos de caracteres que ASCII, pero la asignación de bits
para cada carácter es diferente. Como el nombre lo indica, el código binario de las letras
y los numerales son una extensión del código BCD. Esto significa que los primeros
cuatro bits y los últimos cuatro del código varían de 0000 a 1001, como en BCD.
Tiene su aplicación en las grandes computadoras.
26
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
27
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
Sistema de codificación “UNICODE”
UNICODE: 65,536 posibilidades
UNICODE, es un Sistema de Codificación de caracteres para los caracteres de todo el
mundo. Está diseñado para permitir a los Sistemas de las computadoras intercambiar
información textual sin ambigüedades porque cada carácter tiene una sola codificación
(caracteres a nivel mundial).
Un consorcio de compañías importantes de la industria de la computación, entre ellas
IBM, Microsoft y Sun Microsystems, esta patrocinando el desarrollo de UNICODE, un
sistema de codificación uniforme de 16 bits. Unicode permitirá a computadoras y
aplicaciones comunicarse entre si con mayor facilidad y se adaptara a la mayoría de los
idiomas de todo el mundo.
El código ASCII con sus 128 (2**7) caracteres, es suficiente para el idioma ingles, pero
se queda corto ante los requerimientos del japonés
Unicode, al igual que cualquier otro avance en la tecnología de cómputo, presenta
problemas de conversión. Por tener 16 bits, el código Unicode requiere más memoria
que las claves tradicionales de 8 bits. Una A en Unicode ocupa el doble de RAM y de
espacio en disco que una A en ASCII.
28
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
II. LÓGICA
Este tema se desarrollará con el enfoque formal algebraico y estará orientado a sustentar
teóricamente las aplicaciones de la lógica en la tecnología moderna.
La lógica es el sistema de comunicación entre las personas y los computadores.
El estudio de la lógica nos proporciona el empleo de un conjunto de conceptos y
procedimientos para analizar determinadas expresiones a través del razonamiento, de
modo que se obtengan otras más complejas, indicando la validez de cada una.
ÁLGEBRA DE PROPOSICIONES:
Enunciado: Es toda frase u oración que señala alguna idea. Puede cumplir las
siguientes funciones:
a. Directiva.- Su objeto es dar órdenes o hacer pedidos. Los enunciados pueden ser
Interrogativos, imperativos o exhortativos.
b. Expresiva.- Busca comunicar sentimientos, deseos o actitudes. Pueden ser
exclamativos o admirativos, desiderativos, informativos.
Proposición: Es aquel enunciado aseverativo (afirma algo) del cual se puede señalar si
es verdadero (V) o falso (F), pero no ambos a la vez, con respecto a una realidad.
A la verdad o falsedad de una proposición se llama valor de verdad
Ejemplos:
Señalar cuales de los enunciados son proposiciones:
1) 17 es divisible por 9
2) Un cuadrilátero es un rombo
3) 3 = 3
4) ¿Qué hora es?
5) Si un triángulo es equilátero, entonces, sus lados son iguales.
6) ¿Cuánto dinero tienes?
7) X + 5 = 13
8) Si x² + 1 = 17 entonces x = ± 4
9) (a – b) (a + b) = a² - b²
Clases de proposiciones:
Proposición simple: Llamada también atómica, monódica o monaria, es aquella que
está formada por un solo sujeto y un solo predicado.
Las proposiciones serán simbolizadas con letras minúsculas: p, q, r,…etc. Llamadas
variables proposicionales.
Ej.:
p: Un cuadrilátero es un rombo
29
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Proposición compuesta: También llamada molecular, es aquella constituida por
proposiciones simples ligadas entre sí por conjunciones gramaticales o afectadas del
adverbio de negación “no”. Su valor de verdad depende de los valores de verdad de las
proposiciones que la conforman.
Eje:
Cada vez que -4 es número natural además es un número imaginario, entonces es un
número entero.
Conectivas u operadores lógicos:
Llamadas también signos de enlace o ligadura, sirven para unir proposiciones sin
formar parte de ellas.
Eje: Cada vez que, además etc.
Operaciones lógicas: Aquellas que utilizan proposiciones para transformarlas en otras
usando las conectivas lógicas. De ellas resulta: la conjunción, la disyunción, la
condicional, la bicondicional y la negación.
a. Conjunción: Aquella que vincula dos proposiciones mediante la conectiva “y” o
algún equivalente (,) (;) (.) siempre que no haya otra expresión que esté señalando otro
correctivo.
También se puede utilizar otras palabras como: pero, además, incluso, sin embargo,
también, igualmente, no obstante, tanto como, etc.
Ejemplos:
1. Juan enseña, Óscar coordina, Blanca controla.
2. El log2 = 0.301030 y log4 = 2(0.301030)
3. Isabel barre el piso, sin embargo el dormitorio está limpio.
4. Elton llegó tarde a la universidad, igualmente llegó tarde a la casa.
5. El 10% de S/. 500 es S/.50, el 25% de S/. 1000 es S/. 250
6. Karla gusta de nadar, tanto como gusta de bailar.
7. Carlos es el coordinador de EEGG de Sta. Anita también lo es de EEGG de la
ciudad de Chiclayo.
TABLA DE VERDAD DE LA CONJUNCIÓN
p q
p q
VV
V
VF
F
FV
F
FF
F
30
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
b. Disyunción: Es aquella operación que vincula dos proposiciones mediante el
conectivo “o” esta operación puede ser:
•
Disyunción débil o inclusiva “o”
•
Disyunción fuerte o exclusiva o “pero no ambos”
Ejemplo:
1. Ó
3²+4²= 5²
ó
2.
3X2=6 ó
3²+4² = 5²
(disyunción fuerte)
2=2
(disyunción débil)
DISYUNCIÓN DÉBIL O INCLUSIVA
p q
p q
VV
V
VF
V
FV
V
FF
F
DISYUNCION FUERTE O EXCLUSIVA
p q
p q
VV
F
VF
V
FV
V
FF
F
c. Condicional: Es aquella operación que toma dos proposiciones, llamando a la
primera antecedente y a la segunda consecuente. Una condicional puede utilizar otras
palabras que unan las proposiciones es así que:
pq
1. Si Natividad se enfermó, dejó de ir a la universidad.
2. Carlos está fuera de Lima, por consiguiente Óscar reemplaza a Carlos.
Otras formas que toma la condicional: Si…entonces, cada vez que, de allí que, en
consecuencia, por lo tanto, en conclusión, luego etc.
En otros casos la condicional se da en orden inverso, como:
31
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
1. Natividad dejó de ir a la universidad cuando se enfermó.
Otras formas similares:
cada vez
si
dado que
CONSECUENTE
ANTECEDENTE
CONDICIONAL
p q
p q
VV
V
VF
F
FV
V
FF
V
Proposiciones condicionales: Las proposiciones condicionales pueden ser de cuatro
formas:
Proposición Directa
p
q
Proposición Reciproca
q
p
Proposición Inversa
~p
~q
Proposición Contra recíproca
~q
~p
Es aquella que vincula dos proposiciones con el término “ si
d. . Bicondicional
y sólo si” o expresiones equivalentes. También se utiliza:
cuando y sólo cuando
entonces y sólo entonces
32
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
BICONDICIONAL
p q
p q
VV
V
VF
F
FV
F
FF
V
e. Negación “~”: Afecta a una proposición cambiándole su verdad. Utiliza el adverbio
“no”.
TABLA DE VERDAD DE “~ “
p
~ p
V
F
F
V
La negación utiliza: Es falso que, no ocurre que, no es cierto que, etc.
Esquemas Moleculares: Es la combinación de variables proposicionales, operaciones
lógicas y signos de agrupación.
Es la expresión lógica utilizada en la representación de una proposición.
Ejemplo:
a. ( p q) (p q) r
b. ( q r ) ( q r ) ( p r) ( p r) (p r)
q
Los signos de agrupación (paréntesis, corchetas, llaves etc.), se utilizan para indicar el
conectivo de menor o mayor jerarquía. Además para darle un nombre al esquema
molecular. Así, el ejemplo a recibe el nombre de esquema conjuntivo y el b esquema
condicional.
33
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Evaluación de esquemas moleculares: Según los valores hallados en la tabla de
verdad de un esquema molecular, este puede ser: tautológico, contingente o
contradictorio.
a. Tautológico.- Cuando todos los valores encontrados son verdaderos.
b. Contingente.- Cuando existe por lo menos un valor verdadero y otro falso.
c. Contradictorio.- Cuando solo existe valores falsos.
Equivalencia e Implicación:
Consideramos dos esquemas moleculares A y B tal que A B es una tautología,
entonces decimos que A es lógicamente equivalente a B.
También se simboliza A B y se lee “A equivalente a B” o “B equivalente a A”
Consideramos dos esquemas moleculares A y B tal que A B es una tautología,
entonces decimos que “A implica a B”. B puede o no implicar a A.
Los términos “A es condición suficiente para B” se simboliza: “AB”
“ A es condición necesaria para B” se simboliza “B A”
Inferencia: es el paso de un conjunto de premisas a la conclusión, como la premisa y la
conclusión están constituidas por proposiciones, la inferencia es una estructura de
proposiciones, donde a partir de una o más proposiciones llamadas premisas se obtiene
otra llamada conclusión.
Formalmente podemos definir la inferencia como:
( p₁ p₂ p3 ….pn ) C
Donde “Pi” , 1 ≤ i ≤ n representarán cada una de las premisas
“” significa: luego, por lo tanto, etc. y “ C ” representa la conclusión
Ejemplo:
1. Ramón viajará al sur de Argentina o se quedará en Buenos Aires. Por lo tanto, si
Ramón viaja al sur de Argentina entonces no se quedará en Buenos Aires.
2.
Si todas las tierras son cultivadas entonces la reforma agraria dará buenos
resultados. Si la reforma agraria da buenos resultados entonces aumentará el
34
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
volumen de producción. En consecuencia, si todas las tierras son cultivadas
entonces aumentará el volumen de producción.
3. Si una persona es drogadicta entonces fuma marihuana. Esta persona fuma
marihuana. En consecuencia esta persona es drogadicta.
Verdad y validez: El concepto de verdad o falsedad se aplica sólo a proposiciones. Es
decir, sólo las proposiciones son verdaderas o falsas. En cambio el concepto de validez
sólo se aplica en inferencias ya que son relaciones entre proposiciones, en base a sus
conectivas. Puede ser válida o no válida.
Análisis de validez de Inferencias: Pasos a seguir:
a. Simbolización de las premisas, diferenciándose una de otra y después
simbolizaremos la conclusión.
b. Unir las premisas y conclusión de acuerdo al siguiente esquema inferencial:
p₁ Λ p₂Λ…. Λ p
C
c. Evaluar la forma de la inferencia mediante las tablas de verdad.
La inferencia es válida si la conjunción de premisas implica la conclusión, caso
contrario la inferencia no es válida.
Ejemplo:
1. Ramón viajará al sur de Argentina o se quedará en Buenos Aires. Por lo tanto si
Ramón viaja al sur de Argentina entonces no se quedará en Buenos Aires.
Análisis:
Asignemos variables a las proposiciones simples, simbolizaremos premisas y
conclusión
En efecto: p: Ramón viajará al sur de Argentina
q: Ramón se quedará en Buenos Aires.
Simbolizando premisa: p v q
Simbolizando conclusión: p
~q
Evaluaremos
35
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
p
q
(p v q)
(p
~q)
V
V
V
F
F
V
F
V
V
V
F
V
V
V
V
F
F
F
V
V
(1)
(3)
(2)
La fórmula no es una tautología
La inferencia no es válida
2. Si Renzo gana el concurso de poesía entonces obtendrá una beca. Renzo ganó el
concurso de poesía. Por lo tanto, Renzo obtendrá una beca.
Análisis:
Procedemos como en el ejemplo 1
En efecto: p: Renzo gana el concurso de poesía.
q: Renzo obtendrá una beca.
Simbolizamos las premisas: (p
q) Λ p
la conclusión : q
p
q) Λ p ]
q [ (p
q
V V
V
V
V
V
V
V F
F
F
V
V
F
F V
V
F
F
V
V
F F
V
F
F
V
F
La fórmula es una tautología.
La inferencia es válida.
Leyes Lógicas
Las Leyes lógicas las podemos dividir en tres:
a. Principios Lógicos
b. Equivalencias lógicas
c. Implicaciones lógicas
a. Principios Lógicos
Principio de Identidad:
Principio de no contradicción:
Principio del tercio excluido:
pp
( p p)
p p
ò
p p
36
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
b. Equivalencias
Leyes de idempotencia
a) p v p ≡ p
b) p Λ p ≡ p
Leyes asociativas
a) (p v q) v r ≡ p v (q v r)
b) (p Λ q) Λ r ≡ p Λ (q Λ r)
Leyes conmutativas
a) p v q ≡ q v p
b) p Λ q ≡ q Λ p
Leyes distributivas
a) p v (q Λ r) ≡ (p v q) Λ (p v r)
b) p Λ (q v r) ≡ (p Λ q) v (p Λ r)
Leyes de Morgan
a) ~(p v q) ≡ ~p Λ ~q
b) ~(p Λ q) ≡ ~p v ~q
Leyes de la absorción
a) p ( p q ) p
b) p ( p q) p q
c) p ( p q ) p
d) p ( p q ) p q
Leyes de identidad
a) p v F ≡ p
pΛV≡p
b) p v V ≡ V
pΛF≡F
Leyes del complemento
a) p v ~p ≡ V
b) ~(~p) ≡ p
p Λ ~p ≡ F
~V ≡ F
~F ≡ V
37
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
CONJUNTOS
INTRODUCCIÓN
Los conjuntos están relacionados con el proceso de contar y por lo tanto permiten
resolver preguntas que implican la noción de cantidad. Los conceptos geométricos y
aritméticos pueden ser formulados de una manera clara y concisa en términos de
conjuntos. Desde que se introdujo formalmente la teoría de conjuntos, se facilitó el
desarrollo de diversas ramas de la matemática como la geometría, la aritmética, el
análisis y la topología.
Las ideas de conjunto y elemento son ideas primitivas y se presentan en forma intuitiva.
Un conjunto es una colección de objetos o entidades distinguibles y bien definidas. Los
objetos (números, letras, puntos, etc.) que constituyen un conjunto se llaman miembros
o elementos del conjunto.
Para denotar los conjuntos se utilizan con frecuencia letras mayúsculas: A, B, C, ...; y
para denotar los elementos, letras minúsculas: a, b, c, ...: números, símbolos o variables
subindizadas.
Ejemplo 1
a) A = {1,3,5,7} significa que el conjunto A se compone de los primeros cuatro
números naturales impares.
b) B = {a,b,c} los elementos del conjunto B son las tres primeras letras del alfabeto.
c) C = {x | e es una vocal} la notación x | x se lee “x tal que x”, o sea que C es el
conjunto de los “x tal que x” es una vocal.
d) D = {x | x es un número natural par} el conjunto D consta de todos los números
naturales pares.
Observaciones
a) Para indicar que un determinado objeto es miembro o elemento de un conjunto
dado, se emplea el símbolo, de pertenencia. En el Ejemplo 1 se puede escribir: 5
A que se lee “5 pertenece a A”, también a B, u C, 6 D.
El símbolo se lee “no pertenece a” o “no es elemento de”. Observe que d C, 3
D.
b) En el Ejemplo 1 no surgen dudas acerca de si un miembro pertenece o no a cada uno
de los conjuntos dados. Son conjuntos bien definidos pues se puede afirmar de
manera inequívoca si un objeto dado es o no elemento de los conjuntos
38
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
considerados. En los casos a) y b) se ha dado la lista explícita de los elementos de
los conjuntos, y se dice que A y B se han determinado por extensión. En los casos
c) y d) se ha establecido una regla que permite decidir si un objeto es miembro o no
de los conjuntos, se dice que C y D se han determinado por comprensión.
c) Los conjuntos A, B y C son finitos. El Conjunto C también se puede determinar
por extensión. El conjunto D es infinito, no se puede determinar por extensión.
RELACIONES ENTRE CONJUNTOS
Subconjunto
Un conjunto A es subconjunto de un conjunto B, lo cual se escribe A B y se lee “A es
subconjunto de B”, si todo elemento de A es elemento de B. Es decir x A x B.
Ejemplo 2
a) A = {6,9,12} y B = {x | x es múltiplo de tres} A B.
b) G = {x | x es un número natural divisible por tres} y
H = {x | x es un número natural} G H se lee “G es un subconjunto de H”.
Observar que G H pero H G. (El símbolo se lee “no es subconjunto de”).
c) A = {a, m, p} y B = {p, a, m} A B.
Observaciones
a) En el Ejemplo 2, a) A B pero A B, en este caso se dice que A es subconjunto
propio de B.
b) En el mismo ejemplo, c) A B y B A ya que los conjuntos son iguales. Este caso
permite afirmar que todo conjunto es subconjunto de sí mismo A A.
Igualdad de conjuntos
Dos conjuntos A y B son iguales si todos los elementos de A pertenecen a B y todos los
elementos de B pertenecen a A. O sea
A=B ABB A
Ejemplo 3
El Conjunto C = {m, a, a, p, m} = {a, m, p} es igual a los conjuntos A y B del ordinal c)
del Ejemplo 2. Esto sugiere que no interesa el orden en que se enumeran los elementos
ni si éstos aparecen repetidos.
39
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
CONJUNTOS ESPECIALES
Conjunto vacío
Es el carece de elementos, se simboliza por {} o por . El conjunto cuyos miembros
son los hombres que viven actualmente con más de 500 años de edad es un ejemplo de
conjunto vacío.
Conjunto Universal
Cuando se habla o se piensa acerca de los conjuntos, es conveniente saber que los
miembros de un conjunto dado pertenecen a alguna “población” determinada. Por
ejemplo, si se habla de conjuntos de números es útil establecer una población general de
números denominada conjunto universal o conjunto de referencia, cuyos elementos son
los posibles candidatos para formar los conjuntos que intervienen en una discusión
determinada. El conjunto universal se denota U.
Si U = N, el conjunto de los números naturales,
A = {1, 2, 3, 4, 5}; B = {x | x es número primo}:
C = {x | x es un número natural par} A, B y C son subconjuntos propios de U.
Conjunto de partes
Dado un conjunto A, el conjunto de partes de A, denotado por P (A), es el conjunto
cuyos elementos son todos los subconjuntos de A.
En la lista de subconjuntos de A hay que tener en cuenta dos subconjuntos especiales: el
mismo A, ya que A A; y el conjunto vacío .
Ejemplo 4
Si A = {a, b, c}, entonces
P(A) = {{a}; {b}, {c}; {a, b}, {a, c}; {b, c}; {a, b, c}; }
Observaciones
a) Los conjuntos {a}, {b}, {c} son elementos (o miembros) de P(A). Tales conjuntos
constan de un solo elemento y se llaman conjuntos unitarios.
b) El conjunto A está conformado por 3 elementos, y el conjunto P(A) por 8 = 23. En
general, si un conjunto M posee n elementos, el conjunto P(M) constará de 2n
elementos.
40
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
c) Los elementos del conjunto P(A) son a su vez conjuntos. Un conjunto cuyos
elementos son conjuntos se les llama familia de conjuntos. P(A) es un ejemplo de
una familia de conjuntos.
Diagramas de Venn
Los diagramas de Venn o de Euler son una manera esquemática de representar los
conjuntos y los conceptos de la teoría de conjuntos. Constituyen un auxiliar didáctico
valioso para visualizar las relaciones de pertenencia, inclusión y las operaciones con
conjuntos. En la figura 1. se puede apreciar uno de esos diagramas.
U
A
B
C
Figura 1
En general, para representar el conjunto universal se usa cualquier región cerrada del
plano (con frecuencia un rectángulo), entendiendo que la región interior del rectángulo
representa al conjunto U. En el diagrama se han utilizado círculos para representar los
subconjuntos A, B y C de U.
En la figura 2 se han incluido los elementos de los conjuntos U, A, B, C y D.
U
A
C
4
6
D
2
B
1
8
9
3
5
7
Figura 2
41
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
La Figura 2 constituye una descripción gráfica del siguiente conjunto:
U = {1,2,3,4,5,6,7,8,9}
A = {1,2,3}; B = {1}; C = {8,9}, D = {8}
Por tanto, tenemos A U, B U, C U, B A y D C.
OPERACIONES CON CONJUNTOS
Así como los números se combinan mediante las operaciones de adición, sustracción y
multiplicación, los conjuntos se pueden combinar para obtener otros conjuntos con
ciertas operaciones.
Unión de conjuntos
La unión (o reunión) de dos conjuntos A y B, denotada por A B que se lee “A unión
B”) es el nuevo conjunto formado por los elementos que pertenecen a A o a B o a
ambos conjuntos.
Simbólicamente: A B = {x | x A x B}
En el diagrama de Venn, la región sombreada de la Figura 3 corresponde al conjunto A
B.
U
A
B
Figura 3
Ejemplo 5
A = {a,b,c,d}; B = {c,d,e,f} A B = {a,b,c,d,e,f}
42
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Intersección de conjuntos
La intersección de dos conjuntos A y B, denotada por A B (que se lee “A intersección
B”), es el nuevo conjunto formado por los elementos que pertenecen a A y a B, es decir,
por los elementos comunes a ambos conjuntos.
Simbólicamente:
A B = {x | x A x B}
En el diagrama de la Figura 4, la región sombreada corresponde al conjunto A B.
U
A
B
Figura 3
Con relación a los conjuntos del Ejemplo 5, A B = {c,d}. Observe que los elementos
c y d pertenecen simultáneamente a los conjuntos A y B.
Nota:
A B también se llama la suma lógica de los conjuntos A y B
A B se denomina también el producto lógico de los conjuntos A y B.
Dos conjuntos que no tienen elementos comunes se llaman disyuntos. En símbolos A y
B son disyuntos A B = .
U
U
A
A
B
B
Figura 5a
Figura 5b
En la Figura 5a se observa que A B = B porque B A.
43
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
En la figura 5b no hay región sombreada puesto que los conjuntos son disyuntos y por
tanto su intersección es vacía.
Diferencia de conjuntos
La diferencia de dos conjuntos A y B, denotada por A – B (que se lee “A menos B”), es
el conjunto formado por los elementos que pertenecen a A y no pertenecen a B.
Simbólicamente:
A – B = {x | x A x B}
En los diagramas de la Figura 6, la región sombreada corresponde al conjunto A – B.
U
U
U
A
A
B
B
A
B
Figura 6
Ejemplo 6
a) A = {a,b,c}; B = {c,d} A – B = {a,b}
b) A = {3,4,5,6}; B = {4,5} A – B = {3,6}
c) A = {1,2,3}; B = {6,7} A – B = {1,2,3}
Diferencia simétrica de conjuntos
La diferencia simétrica de dos conjuntos A y B, denotada por (que se lee “A
diferencia simétrica B”), es el conjunto formado por los elementos que pertenecen a A o
a B, pero no pertenecen simultáneamente a ambos conjuntos.
Simbólicamente:
A B = {x | x A x B x A B}
En el diagrama de la Figura 7 se muestra A B.
44
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
U
A
B
Figura 7
Observe que las regiones sombreadas a la izquierda y a la derecha corresponden
respectivamente a los conjuntos A – B y B – A, por esto también:
A B = {A – B} {B – A)
A B = {A B} – {B A)
Ejemplo 7
A = {1,2,3,4}; B = {4,5} A B = {1,2,3,5}
Complemento de un conjunto
El complemento de un conjunto A con respecto al conjunto U, denotado por A’, es el
conjunto constituido por los elementos de U que no pertenecen a A.
Simbólicamente:
A’ = {x | x U y x A}
Observe en la figura 8, que A’ = U – A
U
A
Figura 8
45
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejemplo 8
Sea U = N (el conjunto de los números naturales)
A = {x | x es un número natural par} A’ = {x | x es un número natural impar} = U –
A
NÚMERO DE ELEMENTOS DE UN CONJUNTO
Mediante la noción primitiva del apareamiento entre los elementos de un conjunto
cualquiera A y el conjunto N = {1,2,3,4,...} de los números naturales (o números para
contar) se puede establecer cuántos elementos tiene el conjunto A, cuando éste es finito.
Es decir, que al conjunto A se le puede asignar un número natural, denotado por n(A)
(que también se llama la cardinal de A) y que es igual al número de elementos de A.
Ejemplo 9
a) A = {x | x N y x es submúltiplo de 8} n(A) = 3
b) B = {x | x es un número primo divisible entre 3} n(B) = 1
Es fácil probar que, en general:
1. n(A B) = n(A) + n(B) – n(A B)
2. Cuando A y B son disyuntos, es decir, A B = entonces
n(A B) = n(A) + n(B)
3. Para tres conjuntos A, B y C:
n(A B C) = n(A) + n(B) + n(C) – n(A B) – n(A C) - n(B C) + n(A B C)
4. Cuando A y B, A y C y B y C son disyuntos:
n(A B C) = n(A) + n(B) + n(C)
46
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
PROPIEDADES DE LAS OPERACIONES ENTRE CONJUNTOS
5. Las siguientes cuatro propiedades son válidas para las operaciones de unión
e intersección:
a. Leyes de idempotencia
a.1. A A = A
a.2. A A = A
b. Leyes asociativas
b.1. (A B) C = A (B C)
b.2. (A B) C = A (B C)
c. Leyes conmutativas
c.1. A B = B A
c.2. A B = B A
d. Leyes distributivas
d.1. A (B C) = (A B) (A C)
d.2. A (B C) = (A B) (B C)
6. Relacionadas con los conjuntos universal y vacío.
e. Leyes de identidad
e.1. A U = U
e.2. A = A
AU=A
A=
7. Con respecto al complemento
f. Leyes del complemento
f.1. A A’ = U
f.2. (A’)’ = A
A A’ =
U’ =
’ = U
g. Leyes de D’Morgan
g.1. (A B)’ = A’ B’
g.2. (A B)’ = A’ B’
47
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Álgebra de conjuntos
Con base en la relación de orden A B y en las operaciones A B y A B se puede
formar un álgebra de conjuntos.
La relación de contenencia es una relación de orden ya que satisface las propiedades
reflexiva, antisimétrica y transitiva, así:
a) A A
b) Si A B B A entonces A = B
c) Si A B B C entonces A = C
Con base en la definición de A C, se tiene
a) A para todo conjunto A
b) A U
Es posible interpretar la parte a) como sigue:
Si la relación A fuera falsa, indicaría que debe al menos tener un elemento que
no esté en el conjunto A, lo cual resulta imposible porque vacío no tiene elementos y si
una proposición no es falsa entonces es verdadera.
La relación A B es equivalente a una de las dos relaciones A B = B o A B = A
Relación entre la lógica y los conjuntos
Todas las leyes del álgebra de conjuntos se apoyan en el análisis lógico de la relación A
B, de las operaciones binarias (de dos conjuntos) A B y B A; y de la operación
unitaria (sobre un conjunto A’) complemento de A. Con base en esto las leyes del
álgebra de conjuntos se pueden traducir al lenguaje lógico de la siguiente manera:
Sean las proposiciones:
p: ser un elemento del conjunto A
q: ser un elemento del conjunto B, entonces:
Conjuntos
Proposiciones
Se lee
AB
pq
Ser de A o de B
AB
pq
Ser de A y de B
A’
~p
No ser de A
48
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
(A B)’
A’ B’
~(p q)
~p ~q
No ser de A ni ser de B
(A B)’
A’ B’
~(p q)
~p ~q
No ser de A y B
AB
pq
AB =
pqF
Algunos elementos de A son elementos
A B’ =
de B
pqF
Ningún elemento de A es elemento
A=
p=F
Si es de A entonces es de B
de B
No hay elementos en A
Ejemplo 10
Demostrar que A – B = A B’ = B’ – A’
a) A – B = {x | x A x B}
= {x | x A x B’}
= A B’
=A–B
b) A – B = {x | x A x B}
= {x | x A’ x B’}
= {x | x B’ x A’}
= B’ A’
=A–B
Ejemplo 11
a) Demostrar la Ley de D’Morgan:
(A B)’ = A’ B’
= {x | x (A B )’}
= {x | x A B}
49
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
= {x | x A x B}
= {x | x A’ x B’}
= A’ B’
b) Demostrar:
A – (B C) = (A – B) (a – C)
= {x | x A x (B C)
= {x | x A (x B x C)}
= {x | x A x B) (x A x C)}
= {x | x (A – B) x (A – C)}
= {x | x (A – B) (A – C)}
= (A – B) (A – C)
FORMAS NORMALES
Las formas normales disyuntiva y conjuntiva corresponden en la teoría de conjuntos
a las formas unión e intersección. Esto se obtiene de manera similar al asignar los
valores F y V a las proposiciones “no ser elemento de” y “ser elemento de”
respectivamente. De la siguiente tabla se deducen las formas normales completas.
A B
Término Término
Intersección Unión
F F
A’ B’
AB
F V
A’ B
A B’
V F
A B’
A’ B
V V
A B
A’ B’
La forma normal completa de la unión se obtiene reuniendo los términos intersección
cuyo resultado es el conjunto universal (U):
(A’ B’) (A’ B) (A B’) (A B) = U
50
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
En el diagrama de Venn se ilustra la validez del anterior resultado.
U
A
B
A B’ A B A’ B
A’ B’
Figura 9
Note que el conjunto universal ha quedado particionado en cuatro regiones que son
conjuntos disyuntos.
La forma normal completa de la intersección se obtiene intersectando los términos
unión cuyo resultado es el conjunto vacío.
(A B) (A B’) (A’ B) (A’ B’) =
Ejemplo 12
Comprobar con los siguientes conjuntos las formas normales completas:
U = {x | x N x 15}
A =} x | x es impar}
B = {x | x es primo}
a) Forma normal unión
A = {1,3,5,7,9,11,13,15}
B = {2,3,5,7,11,13}
A’ = {2,4,6,8,10,12,14}
B’ = {1,4,6,8,9,10,12,14,15}
AB
A’ B
A B’
A’ B’
=
=
=
=
{3,5,7,11,13}
{2}
{1,9,15}
{4,6,8,10,12,14}
n(A B)
n(A’ B)
n(A B’)
n(A’ B’)
n(U)
=
=
=
=
=
5
1
3
6
15
(A B) (A B’) (A B) (A’ B’) = U
51
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
b) Forma normal de intersección
A’ B’ = {1,2,4,6,8,9,10,12,14,15}
A’ B = {2,3,4,5,6,7,8,10,11,12,13,14}
A B’ = {1,3,4,5,6,7,8,9,10,11,12,13,14,15}
A B = {1,2,3,5, 7, 9, 11, 15}
(A’ B’) (A’ B) = {2,4,6,8,10,12,14}
(A B’) (A B) = {1,3,5,7,9,11,13,15}
(A’ B’) (A’ B) ó (A B’) (A B) =
PRODUCTO CARTESIANO
Pares ordenados: intuitivamente un par ordenado (a,b) es un par de objetos en el cual
el orden en el que éstos se consideran debe ser: primero a y después b. Las letras ay b
se llaman la primera y la segunda componentes, respectivamente, de la pareja ordenada.
Dos pares ordenados (a,b) y (c,d) son iguales, si y solo si
a=cb=d
Producto cartesiano: dados dos conjuntos A y B, se llama producto cartesiano (o
conjunto producto) de A y B, al conjunto de todos los pares ordenados (a,b) de tal forma
que la primera componente a pertenece al conjunto A y la segunda componente b es
elemento del conjunto B. Este conjunto se denota por A B y se lee “A cruz B”.
Simbólicamente:
A B = {(a,b) | a A b B}
Ejemplo 13
a) Si A = {a,b,c}; B = {x,y}
A B = {(a,x), (a,y), (b,x), (b,y), (c,x), (c,y)}
Note que el conjunto contiene seis elementos (parejas)
b) Si A = {1,2,3}; B = {4,5,6}
A B = {(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)}
B A = {(4,1), (5,1), (6,1), (4,2), (5,2), (6,2), (4,3), (5,3), (6,3)}
Observe que cada conjunto tiene nueve elementos, y que A B B A.
52
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
En general, si n(A) = p y n(B) = q entonces,
N(A B) = n(B A) = pq
Además, el producto cartesiano no es conmutativo.
A B B A, a menos que A = B o que uno de los conjuntos sea vacío.
Si A y B son conjuntos finitos dicho producto puede ser representado en el plano
cartesiano colocando el conjunto A en el eje horizontal, y B en el eje vertical. A
cada par ordenado (a,b) le corresponde un punto del plano.
Por ejemplo, si A = {a1, a2, a3, a4} y B = {b1, b2, b3 } , el conjunto producto
consta de 12 elementos o parejas, y en su representación gráfica deben aparecer
12 puntos, que forman una red, así:
B
b3
b2
b1
a1
a2
a3
a3
A
Otra manera de representar el producto A B es mediante un diagrama de árbol.
Por ejemplo, si A = {1,2,3} y B = {a,b), la gráfica arborescente correspondiente a A
B, es:
a (1,a)
1
b (1,b)
a (2,a)
2
b (2,b)
a (3,a)
3
b (3,b)
53
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Conjuntos numéricos
En esta sección se presentan los conjuntos numéricos más importantes sin entrar a
operar con ellos. El interés fundamental es distinguir y determinar sus elementos, y
clasificarlos de acuerdo con la relación de inclusión.
Números naturales
Es la colección de objetos matemáticos representados por los símbolos 0,1,2,3,4,..., etc.,
llamados números para contar. El conjunto se suele representar con el símbolo N, es
decir:
N = {0,1,2,3,4,...}
Dos características esenciales son: el conjunto tiene un primer elemento, el 1, y cada
elemento tiene un sucesor.
Números enteros
Ampliando el conjunto de los naturales para incluir el cero y los negativos de los
naturales, se obtiene el conjunto de los enteros que se acostumbra denotar mediante el
símbolo Z, es decir:
Z = { ...,-3,-2,-1,0,1,2,3,...}
Números racionales
p
donde p y q son enteros, con q O. Se
q
representa mediante el símbolo Q, de tal forma que:
p
Q = { q Z q O}
q
Es el conjunto de los números de la forma
Observaciones:
a) Todo número entero es racional.
3
5
0
= -3, = 5, = 0 son números racionales enteros.
1
1
1
b) Si q no es divisor de p, los números
p
son racionales no enteros.
q
7 2
,
son números racionales no enteros.
3 5
54
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
c) Todo número racional es equivalente a un número que tiene una expansión decimal
que se repite periódicamente.
8
2.666...
periodo 6 (periódica pura)
3
12
3.000...
4
periodo 0 (periódica pura)
29
0.3222...
90
periodo 2 (periódica mixta)
Números irracionales
Es el conjunto de los números que no pueden ser expresados como el cociente de dos
enteros; se representa con el símbolo Q’. Entre los irracionales más conocidos están los
números y e. El primero es la razón de la longitud de la circunferencia al diámetro, y
el segundo es la base de los logaritmos naturales; sus valores aproximados son 3.141592
t 2.718281, respectivamente.
Los números irracionales se caracterizan por tener expansiones decimales infinitas no
periódicas. Otros números irracionales son: 2 , 3 , 5 , 3 2 , 3 7 , 3 9 , etc.
Números reales
Es el conjunto constituido por todos los números racionales e irracionales. Cada
número real puede ser representado como un punto en una recta, y recíprocamente cada
punto de la recta corresponde a un número real. A tal recta se le llama recta real. El
conjunto se simboliza por R, y de acuerdo con lo anterior:
R = Q Q’
De las definiciones anteriores se tiene que Q Q’ = , o sea que los conjuntos de los
racionales y los irracionales son disyuntos.
Números complejos
Es la colección de números de la forma a + bi, donde a y b son números relaes, e i es la
unidad imaginaria, que cumple con la propiedad i2 = -1. El conjunto se denota C.
Simbólicamente:
C = {a + bi | a,b R i2 = 1}
Observaciones
55
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
a) Todos los números reales son complejos. Cuando b = 0 se obtiene
A
Bi =a,2 + 0i = 2,
2 + 0i =
2 son números complejos reales.
b) Cuando a = 0, y b 0 los números de la forma bi se llaman imaginarios puros.
1
( )i, 8i son imaginarios puros.
3
Cada uno de los conjuntos de números considerados ha sido presentado en orden
creciente de “amplitud”, de tal modo que cada conjunto está totalmente incluido en
el siguiente, excepto el conjunto Q que no es subconjunto de Q’. De acuerdo con
esto es posible escribir:
NZQRC
Q’ R, Q Q’ =
Q Q’ = R
En el siguiente diagrama se puede apreciar la relación de inclusión. La flecha indica
que el conjunto de “abajo” está conectado en el de “arriba”.
C
C
Q
Q
C
C
El conjunto Z es la unión de tres subconjuntos disyuntos:
Z = {enteros negativos} {0} {enteros positivos}
RESUMEN
Un conjunto es una colección de objetos de cualquier naturaleza. Tales objetos se
llaman elementos del conjunto. Dos conjuntos especiales son el vacío y el
universal.
56
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Un conjunto cuyos elementos son a su vez conjuntos se llama familia de
conjuntos. Todo conjunto A de n elementos tiene 2n subconjuntos distintos. El
conjunto de todos los subconjuntos de un conjunto A, se llama conjunto de partes
de A, P(A).
Con los conjuntos se pueden realizar cuatro operaciones básicas: unión,
intersección, diferencia y diferencia simétrica.
Operación
Unión
Intersección
Diferencia
Diferencia Simétrica
Símbolo
Definición Simbólica
A B = {x | x A x B}
A B = {x | x A x B}
A b = {x | x A x B}
A b = {x | x A x B}
EJERCICIOS RESUELTOS
1. Sean A = {1}, B = {1,2}, C = {2,3,4}, D = {2,3}, E = {1,2,3,4}. Establecer la
verdad o la falsedad de las siguientes proposiciones.
a) D B
c) C D
b) C E
d) E A
Solución
a) Como 3 D y 3 B, entonces, D B es verdadera.
b) Todo elemento de C lo es de E, luego C E es verdadera.
c) C es un superconjunto de D, porque todos los elementos de D lo son de C; la
proposición es verdadera.
d) E es un superconjunto de A, puesto que el único elemento de A es elemento
de E, por tanto la afirmación es falsa.
2. Dado M = {a,b, {a,b}}. Establecer la verdad o falsedad de:
a) {a} M
c) {a,b} M
b) {a,(a)} M
d) {(a,b)} M
Solución
Los elementos de M son: a, b y el conjunto {a,b}; luego a) es falsa y c) es
verdadera.
El conjunto M tiene 23 = 8 subconjuntos, entre los cuales están: {a}, {(a,b)}; por
lo tanto b) y d) son verdaderas.
3. Si x = {1, {1}}; hallar todos los subconjuntos de x.
57
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Solución
Como x tiene dos elementos: 1 y {1}, entonces hay 22 = 4 subconjuntos distintos
que son: , {1}, {{1}}, {1,{1}}.
4. Si A = {a,b,c}: B = {c,d,e}; C = {b,c,e}; comprobar que:
a)
b)
c)
d)
(A C) A
(A B) (A B)
A (B C) = (A B) (A C)
Si el universo es U = a,b,c,d,e,f); (A B)’ = A’ B’
Solución
a) Como todos los elementos de A C = }b,c} también lo son de A,
entonces se verifica la proposición.
b) A B = {a,b,d,e} y A B = {a,b,c,d,e}. Todo elemento del primer
conjunto pertenece al segundo, por tanto se comprueba la afirmación.
c) El conjunto A (B C) = {a,b,c} {b,c,d,e} = {b,c} es igual al
conjunto (A B) (A C) = {c} {b,c} = {b,c}
d) (A B)’ = {f} y A’ B’ = {d,e,f} {a,b,f} = {f}
5. Sean A = {1,2,3,4,5}, B = {2,4,6}, C = {3,5,7} y U = {x|x es un número natural
menor o igual que 9}.
Hallar a)
A’ B’
b) A’ B’
c)
A–B
d) A B
e)
BC
Solución
a) Cómo A’ = {6,7,8,9} t B’ = {1,33,5,7,8,9}, entonces A’ B’ = {7,8,9}
b) A’ B’ = {1,3,5,6,7,8,9}
c) El conjunto consta de los elementos de A que no están en B: A – B =
{1,3,5}
d) Los elementos de la intersección son los comunes a ambos conjuntos: A
B = {2,4}
e) B C = . Los conjuntos no tienen elementos comunes, son disyuntos.
6. Para los conjuntos dados en el Ejercicio 5, hallar:
a) A B
b) B C
c) Comprobar que el número de elementos de A B y de B C, está dado
respectivamente por:
n(A B) = n(A) + n(B) – n(A B)
n(B C) = n(B) + n(C)
58
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Solución
a) La unión está constituida por los elementos de ambos conjuntos,
incluyendo elementos comunes y no comunes:
A B = {1,2,3,4,5,6}
b) B C = {2,3,4,5,6,7}
c) n(A B) = 6, n(A) = 5, n(B) = 3, n(A B) = 2 con lo cual n(A B)
=5+3–2=6
n(B C) = 6, n(B) = 3, n(C) = 3
Así n(B C) = 3 + 3 = 6. El resultado se debe a que la intersección
de B y C es vacía, es decir n(B C) = 0.
7. Hallar los conjuntos A y B, si:
A’ = {2,3,5,7}
B’ = {1,4,7} y U = {1,2,3,4,5,6,7,8}
Solución
Empleando las leyes de D’Morgan:
A’ B’ = {7} = (A B)’. O sea que 7 es el único elemento del conjunto
universal que no está ni en A ni en B, luego A B = {1,2,3,4,5,6,8}
A’ B’ = {1,2,3,4,5,7} = (A B)’
El complemento de este último conjunto:
(A B)’’ = A B = {6,8} es subconjunto de A y de B. Luego los elementos
de A son 6,8 más los de B’, exceptuando el 7. los elementos de B son 6,8 más
los de A’ excluyendo el 7. En consecuencia: A = {1,4,6,8} y B = {2,3,5,6,8}.
8. Cuando en cualquiera de las leyes del álgebra de conjuntos se intercambian los
símbolos y los símbolos U y , el resultado también es una ley que se
denomina la dual de la primera (son mutuamente duales).
Escribir el dual en cada caso:
a)
b)
c)
d)
(A ) (A U) = A
A=
(A B)’ = A’ B’
(A B) C = (A C) (B C)
Solución
a)
b)
c)
d)
(A U) (A ) = A
AU=U
(A B)’ = A’ B’
(A B) C = (A C) (B C)
59
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
9. Si en lugar de las notaciones X Y y X Y, se emplea X + Y y X.Y; y en vez
de U y se usa I y O, respectivamente, hallar el dual de:
a)
b)
c)
d)
X + X’ = 1
X.X’ = 0
X + X.Y = X
X +Y.Z = (X + Y).(X + Z)
Solución
a)
b)
c)
d)
X.X’ = 0
X + X’ = 1
X.(X + Y) = X
X.(Y + Z) = X.Y + X.Z
10. Cuando se ha demostrado un teorema sobre conjuntos, el dual del teorema se
puede demostrar utilizando el dual de cada paso de la primera demostración:
Demostrar:
a) (X.Y) + (X.Y’) = X
b) (X + Y).(X + Y’) = X
Solución
a) (X.Y) + (X.Y’) = X.(y + Y’) (Ley distributiva)
(X.Y) + (X.Y’) = X.1 (Ley del Complemento)
(X.Y) + (X.Y’) = X
b) (X + Y). (X + Y’) = X + (Y.Y’) (dual)
(X + Y). (X + Y’) = X + 0 (dual)
(X + Y). (X + Y’) = X (el teorema es el dual del anterior)
11. Dados n(U) = 60, n(A) = 26, n(B) = 24, n(C) = 8, n(A B) = 10, n(A C) = 0
y C B. Hallar:
a) n(A – B)
b) n(A B)’
c) n(A C)’
d) nA – (B C)’
Solución
En el siguiente diagrama de Venn se encuentra la información dada
U
A
B
16
10
C
8
6
60
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
20
a) El elemento de A que no está en B es 16: n(A – B) = 16
b) (A B)’ corresponde a los elementos fuera de la unión: n(A B)’ = 20
c) A C tiene 16 + 10 + 8 = 34 elementos, luego n(A C)’ = 60 – 34 = 26
elementos.
d) Como C es subconjunto de B, la unión B C es el mismo B; los elementos de A
– B’ son los que pertenecen a A y no a B. De los 26 = 16 + 10 elementos de A,
sólo hay 10 que cumplen las dos condiciones:
nA – (B C)’ = 10
12. Determinar los elementos de los conjuntos X y Y, sabiendo que el complemento
de X es {f,g,h}, X Y = {a,b,c,d,e,f,g} y X Y = {d,e}
Solución
En este caso el universo debe ser: U = {a,b,c,d,e,f,g,h} y hay un solo elemento
de éste que no está en la unión: h. Como X’ = {f,g,h}, el complemento de este
conjunto es:
X = {a,b,c,d,e} y Y = {d,e,f,g}
EJERCICIOS PROPUESTOS
1.
Sean a = {a,b}, B = {a,b,c}, C = {c{d{e), D = b,c} y E ) {a,b,c,d,e}, establecer la
verdad o falsedad de las siguientes proposiciones:
a) D B
b) C E
c) C D
d) E A
Respuesta:
a) Falso
c) Falso
2.
b) Verdadero
d) Falso
Dado M = {0,1,{0,1}}, establecer la verdad o falsedad de:
a) {1} M
b) {0,19 M
c) {0,1} M
d) {{0,1}} M
Respuesta:
Todas son verdaderas excepto a)
3.
Si X = {, {}}, establecer la verdad o falsedad de:
a) X
b) X
c) {} X
d) {} X
e) {{}} X
Respuesta:
Todas son verdaderas
61
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
4.
Hallar todos los subconjuntos de: M = {0, {{0}}
Respuesta:
Son cuatro: , {0}, {{{0}}} y el mismo M.
5.
Si A, B, C, D, E son conjuntos con 3,7,12,4 y 5 elementos respectivamente,
cuántos elementos tiene el conjunto de partes de M = {A,B,C,D,E}
Respuesta: 32
6.
Si U = {1,2,3,4,5,6,7,8}, A = {1,2,3,4}, B = {2,44,5,6}, C = {3,4,6,7}, comprobar
que:
a) (A C) A
b) (A B) (A B)
c) A (B C) = (A B) (A C)
d) (A B)’ = A’ B’
7.
Para los conjuntos del ejercicio 6, hallar:
a) A’ B’
b) (A B)’
c) A B
d) B C
e) (C A)’ B
f) (A C) (B C)
Respuesta:
a) {7,8}
c) {1,3}
e) (1,3,8}
8.
b) {7,8}
d) {4,6}
f) {2,7}
Hallar los conjuntos A y B, si:
A’ = {3,4,5}, B’ = {1,2,4} y U = {1,2,3,4,5,6,7}
Respuesta:
A = {1,2,6,7}
B = {3,5,6,7}
9.
Escribir el dual de:
a) (A ) (A U) = A
b) A U = U
c) (A B)’ = A’ B’
d) (A B) C = (A C) (B C)
Respuesta
a) (A U) (A ) = A
b) A =
c) (A B)’ = A’ B’
d) (A B) C = (A C) (B C)
62
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
10.
Hallar el dual de:
a) X.X´= 0
b) X + X´ = 1
c) X. (X + Y) = X
d) X.(Y + Z) = X.Y + X.Z
Respuesta
a) X + X´= 1
b) X.X´= 0
c) X + X.Y = X
d) X + Y.Z= (X + Y) + X + Z)
11.
Demostrar que:
a) (X. Y) + (X.Y´)= Y
b) ( X + Y). X´+ Y = Y
12.
Dados n(U)= 60, n(A) = 10, n(B)=20, n(C)=38, n(B C) = 8, n(A C) = 0 y A
B, hallar:
a) n(C B)
c) n(A C)’
b) n(B C)’
d) nC – (A B)’
Respuesta:
a) 30
b) 10 c) 12 d) 8
13.
Determinar los elementos de los conjuntos X y Y, sabiendo que el complemento
de Y es el conjunto {m,n,t}, X Y = {m,n,p,q,e} y X Y = {p,q}
Respuesta:
X = {m,n,p,q} y
Y = {p,q,r}
14. Sabiendo que U = {x| x es el número natural, menor que 11}, A’ = {x | x > 2}, A
B = {x | x2 6x + 9 = 0, A B = {1,2,3,4,6}, hallar los conjuntos A, B, A
By (A B)’
Respuesta:
A = {1,2,3}
B = {3,4,6}
A B = {1,2,4,6}
(A B)’ = {5,7,8,9,10}
15.
Determinar cuál de los conjuntos dados es vacío:
a) A = {a | a N a2 1 = 0}
b) B = {b | b R b2 2 = 0}
c) C = {c | c Q c2 9 = 0}
d) D = {d | d Q’ d2 3 = 0}
e) E = {e | e R e2 + 9 = 0}
Respuesta: Sólo es vacío el conjunto E.
63
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
16.
En un examen a 200 estudiantes relacionado con la habilidad para leer inglés,
francés y español se obtuvieron los siguientes resultados: 80 leen inglés, 105 leen
francés, 80 leen español, 55 leen español y francés, 55 leen inglés y no leen
francés, 60 leen ingles y no lee español, 15 leen inglés y español, pero no francés.
Cuántos de estos estudiantes a) leen los tres idiomas, b) cuántos leen únicamente
francés, c) cuántos no leen ninguno de los tres idiomas, y d) cuántos leen español
pero no inglés ni francés.
Respuesta:
a) 5
b) 30 c) 30 d) 10
17.
Dados dos conjuntos no disyuntos A y B, usar diagramas de Venn para mostrar
que:
a)
b)
c)
d)
18.
A (A B) = A
A (A B) = A
(A B)’ = A’ B’
(A B)’ = A’ B’
Si A B demuestra que:
a) A B = B
c) A B = A
19.
b) A B’ =
d) A’ B = U
Demostrar utilizando las leyes del álgebra de conjuntos:
a) ( A B ) = (A B’) (A’ B)
b) (A B )’ = (A B’) (A’ B)’
c) (A B )’ = (A’ B) (A’ B’)
20.
Dados tres conjuntos A, B, C demuestre utilizando las leyes del álgebra de
conjuntos las siguientes igualdades:
a)
b)
c)
d)
e)
f)
21.
(A B’) (A C) (A B) = A
(A B) (A’ B) = B
(A B’ C) (A’ B’ C’) = U
(A B’) (B C) (B C’) = A B
(A B) (A’ C) (B C) = (A B) (A’ B) (A’ C)
(A B) (A’ B’) = (A’ B) (A B’)
En cada uno de los diagramas de Venn identificar el área sombreada.
a)
A
B
C
Falcón/Nazario/Uribe
64
Matemáticas Discreta
FIA-2010-I
Respuesta: A B C’
b)
A
B
C
Respuesta: (A B C) (A’ B C’)
c)
A
B
C
Respuesta: A (A’ B C)
d)
A
B
C
Respuesta: (A’ B’ C’) (A B C)
e)
A
B
C
65
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Respuesta: (A B’ C’) (A’ B C’) (A’ B’ C’)
f)
A
B
C
22.
Respuesta: (A B C) (A B C’) (A B’ C) (A’ B C)
Simplificar utilizando las leyes:
a)
b)
c)
d)
e)
f)
A B’ A’ B’
(A B) (A B’) (A’ B) (A’ B’)
(A C’) (A B C) (A C)
(A B C) A’ B’ C’
(A B) (A’ B)
B (C’ B) B (A C)
Respuesta:
a)
b) U
e) B
f) B
c) A
g) A
d) U
ALGEBRA BOOLEANA
INTRODUCCIÓN
Las aplicaciones de la electrónica digital a los procesos de control y automatismo
industriales y a la computación, están fundamentadas teóricamente en el sistema
matemático denominado álgebra booleana.
Los círculos digitales o lógicos operan de un modo binario donde cada voltaje (señal) de
entrada o de salida es un cero (9) o un uno (1). Las designaciones 0 y 1 representan
intervalos predefinidos de voltaje. Esta característica de los circuitos lógicos permite
emplear el álgebra booleana en el análisis y diseño de sistemas digitales. En este
capítulo se estudiarán las compuertas lógicas, que son los circuitos lógicos
fundamentales cuyo funcionamiento puede describirse mediante el uso del álgebra
booleana. Las combinaciones de estas compuertas conforman circuitos lógicos cuyas
salidas son las respuestas deseadas para propósitos de automatismo y control.
66
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
VARIABLES Y CONSTANTES BOOLEANAS
Las variables y constantes del álgebra booleana sólo pueden tener dos valores posibles:
cero (0) y uno (1). Una variable booleana, denominada también variable lógica, puede,
en diferentes ocasiones, ser igual a 0 ó a 1. las variables booleanas se emplean para
representar el nivel de voltaje presente en los terminales de entrada y salida de un
circuito. A este nivel de voltaje también se llama El “nivel lógico” de la variable.
Cuando este nivel de voltaje es bajo (entre 0 y 0.8 voltios) se emplean los términos:
falso, desactivado, no, interruptor abierto (0). Cuando el nivel lógico es alto (por
ejemplo, entre 4 y 5 voltios) se usan las palabras: verdadero, activado, si, interruptor
cerrado (1).
El álgebra booleana se utiliza para describir los efectos que producen las entradas
lógicas sobre los diversos circuitos digitales (circuitos lógicos). También se usa para
manipular variables lógicas en la determinación del método de ejecución de una cierta
función de un circuito.
Las operaciones del álgebra booleana son:
Adición o suma lógica
También llamada operación OR, o simplemente OR. Corresponde a la disyunción de
proposiciones en lógica y a la unión de conjuntos; su símbolo es (+). El dispositivo
electrónico que ejecuta esta operación se denomina compuerta OR y su representación
es:
Multiplicación o producto lógico.
Llamada también operación AND o simplemente AND. Corresponde a la conjunción
de proposiciones en lógica y a la intersección de conjuntos; su símbolo es el punto (.).
El dispositivo electrónica que ejecuta esta operación se llama compuerta AND y su
representación es:
67
Falcón/Nazario/Uribe
FIA-2010-I
Matemáticas Discreta
Complementación o inversión lógica
Denominada también operación NOT, corresponde a la negación de una proposición en
lógica o a la operación de complementación en conjuntos. Se simboliza con apóstrofo
en la variable complementada. El dispositivo electrónico que ejecuta esta operación es
un inversor y su representación es:
68
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Lógica
Disyunción
Negación
Conjunción
pq
Conjuntos
Complemento
pq
Unión
~p
Intersección
AB
AB
Algebra
Inversor
Booleana
Suma
Producto
x+y
xy
x’
Compuertas
lógicas
OR
AND
NOT
A’
Tabla 4.1.
La tabla 4.1. muestra las correspondencias mencionadas. Las propiedades o leyes que
se cumplen para estas operaciones en lógica y en conjuntos son válidas también para las
correspondientes operaciones del álgebra booleana.
DEFINICIÓN DEL ÁLGEBRA BOOLEANA
Una definición del álgebra booleana como un sistema axiomático consistente, completo
e independiente fue dada por E.V. Huntington en 1904.
La definición formal es la siguiente:
Un álgebra booleana es un sistema matemático que comprende: un conjunto B, con al
menos dos elementos; dos operaciones binarias, la suma y el producto (+ y.), y una
operación unitaria, la complementación, definidas para todos los x, y, z elementos de B,
tales que se cumplen los siguientes axiomas:
P1: las operaciones suma y producto lógico son conmutativas:
x+y=y+x
xy = yx
Leyes conmutativas
P2: cada operación es distributiva respecto a la otra:
x + yz = (x + y)(x + z)
x(y + z) = xy + xz
Leyes distributivas
P3: existen elementos individuales 0 y 1, tales que:
69
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
x+0= x
x.1 = x
Leyes modulativas
P4: para todo x B existe el elemento x’ llamado el complemento de
x,
o la negación de x, tal que:
x + x’ = 1
x.x’ = 0
Leyes del complemento
Sobre la anterior definición caben las siguientes observaciones:
1. Tanto la lógica matemática como la teoría de conjuntos cumplen con la definición
de álgebra booleana por son sistemas axiomáticos similares.
2. La definición de álgebra booleana no hace mención del axioma de asociatividad de
las operaciones suma y producto lógico, porque éste no es independiente de los
cuatro postulados citados, sino que es deducible de ellos. La ley o propiedad
asociativa de las operaciones suma y producto lógico se escribe:
Para todo x, y, z elementos de B se verifica que:
x + (y + z) = (x + y) + z = x + y + z
x(yz) = (xy)z = xyz
3. En cada axioma de la definición aparecen dos expresiones. Cada una puede
obtenerse de la otra intercambiando + por . y 0 por 1. por esta razón se denominan
expresiones duales. Cada uno de los axiomas y teoremas del álgebra booleana tiene
la propiedad de tener su dual.
PROPIEDADES DEL ÁLGEBRA BOOLEANA
Otras propiedades o leyes del álgebra booleana empleadas en los procesos de
simplificación de expresiones booleanas o en la demostración de teoremas, son:
Ley de idempotencia:
x+x=x
x.x = x
x+1=1
x.0 = 0
x + xy = x
x(x + y) = x
(x’)’ = x
(0’)’ = 0
Ley de acotación:
Ley de absorción:
Ley de involución:
(1’)’ = 1
Ley de De Morgan:
(x + y)’ = x’.y’
(x.y)’ = x’ + y
La representación de algunos axiomas y teoremas del álgebra booleana se puede realizar
con compuertas lógicas como se demuestra en la tabla 4.2:
70
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Nombre
Ley
Modulativa
Ley dual
x+0= x
x.1 = x
x
x
x
0
x + x’ = 1
Complemento
x
Ley de idempotencia:
x.x’ = 0
1
x
0
x+x=x
x
Ley de acotación:
x.x = x
x
x
x
x+1=1
x.0 = 0
x
x
1
1
Ley de absorción:
x
1
0
0
x + xy = x
x(x + y) = x
x
x
x
x
y
y
(x’)’ = x
Ley de involución:
(0’)’ = 0
x
x
Ley de D’Morgan:
(x + y)’
x
Ley de D’Morgan:
x’.y’
(x + y)’ =
y
(x.y)’ =
x
y
(x.y)’
x
x
x
y
x’.y’
x’ + y’
=
x
y
x’ + y’
Tabla 4.2
71
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
RELACIÓN DE ORDEN EN UN ÁLGEBRA BOOLEANA
El conjunto B, con al menos dos elementos, debe ser parcialmente ordenado. Esto
quiere decir que sus elementos deben cumplir con las propiedades de la relación de
orden: reflexiva, antisimétrica y transitiva.
La relación de orden parcial (menor o igual) en un conjunto B, por ser parcialmente
ordenado, cumple las siguientes propiedades:
Para todo x, y,z elementos de B:
Reflexiva:
xx
Antisimétrica:
xyyxx=y
Transitiva:
xyyzxz
El conjunto potencia de B o de partes de B es un conjunto parcialmente ordenado que
cumple las condiciones de la definición de un álgebra booleana. En este caso el cero (0)
es el conjunto vacío y el uno (1) es el mismo conjunto B. La relación de orden es la
de inclusión de conjuntos.
Establecida la relación de orden parcial anterior, se puede enunciar:
Definición:
En un álgebra de Boole:
x y si y solo si x + y = y
Para indicar que el elemento y es mayor que x, se emplea el diagrama (línea dirigida de
x hacia y)
y
x
Así 0 1 porque 0 + 1 = 1
En un álgebra de Boole, las siguientes afirmaciones son equivalentes:
Si x y, entonces:
1.
2.
3.
4.
x+y=y
x.y’ = 0
x.y = x
x’ + y = 1
72
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
EXPRESIONES BOOLEANAS
Una expresión booleana (función booleana o función lógica) es un conjunto finito de
símbolos, cada uno representa una constante o una variable, combinados mediante las
operaciones de suma, producto o complementación. Por ejemplo, la expresión x + x’ =
1 representa la proposición de que esta función de la variable x es igual a la constante 1.
Funciones booleanas de dos variables
El número total de funciones lógicas que se pueden escribir con dos variables es 16. si
n es el número de variables lógicas, entonces el número total de funciones lógicas que
2n
se pueden escribir con n variables es 2 .
Para n = 3 (tres variables lógicas: x, y, z), el número de funciones lógicas distintas es de
256. para n = 2 (dos variables lógicas, x, y), las 16 funciones lógicas se denominan
Fi para i = 0...15.
En la tabla 4.3. se presentan las 16 funciones lógicas posibles que pueden ser generadas
con dos variables. Al frente de cada Fi aparece el número binario correspondiente al
subíndice i. Observar además la simetría entre cada par de funciones Fi y Fj, para i + j
= 15. Cuando esto se cumple las funciones Fi y Fj son complementarias, es decir, una
es negación de la otra. Así F0 y F15 son 0 y 1 respectivamente; F1 y F14 AND y
NAND; F13 y F2 la implicación directa y su negación; F11 y F4 la implicación contraria
y su negación; F6 y F9 XOR y XNOR, F7 y F8 OR y NOR. Las cuatro funciones
restantes corresponden a las variables y sus negaciones.
x 0 0 1 1
Función
Lógica
Expresión
Otra
Compuerta
Equivalente Expresión
y 0 1 0 1
F0 0 0 0 0
x’ ó yy’
0
0
F1 0 0 0 1
xy
(x’ + y’)’
AND
F2 0 0 1 0
xy’
(x’ + y)’
F3 0 0 1 1
x
x
F4 0 1 0 0
x’y
(x’ + y’)’
F5 0 1 0 1
y
y
F6 0 1 1 0
x’y + xy’
xy
F7 0 1 1 1
x+y
(x’y’)’
(x y)’
(y x)’
(x y)’
XOR
OR
73
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
F8 1 0 0 0
(x + y)’
x’y’
F9 1 0 0 1
x’y’ + xy
(x y)’
F10 1 0 1 0
y’
y’
F11 1 0 1 1
x + y’
(x’y)’
F12 1 1 0 0
x’
x’
F13 1 1 0 1
x’ + y
(xy’)’
F14 1 1 1 0
(xy)’
x’ + y’
NAND
1
1
F15 1 1 1 1 x + x’ ó y + y’
NOR
xy
XNOR
yx
xy
Tabla 4.3.: Funciones Lógicas de dos variables
Las expresiones booleanas pueden adoptar dos formas útiles para las aplicaciones
tecnológicas; tales expresiones están conformadas por una suma de productos o por un
producto de sumas denominadas, respectivamente, la forma normal disyuntiva y la
forma normal conjuntiva.
Forma normal disyuntiva
La función booleana adopta una forma normal disyuntiva si está escriba como una suma
de términos, en la cual cada término es un producto que involucra todas las n variables
con negación o sin ella. Cada término se llama término minimal o minterm y la función
se denomina función polinomial de términos minimales o minterms.
Ejemplos de tales funciones son: x + x’, xy’, xyz’ + x’yz + xyz’ en una, dos y tres
variables, respectivamente.
El proceso para llegar a la forma normal disyuntiva de una función booleana consiste en
aplicar las leyes de D’Morgan, hasta que los complementos aparezcan aplicados
solamente a variables individuales. Después, por la aplicación de la ley distributiva del
producto sobre la suma la función puede ser reducida a un polinomio. Si en algún
término falta una variable, por ejemplo w, entonces este término pede ser multiplicado
por x + x’ sin cambiar la función.
Ejemplo 1
Escribir la función f = (xy + yz’)’ +y’ en la forma normal disyuntiva
(xy + yz’)’ +y’ = (xy)’.(yz’)’ +y’
= (x’ + y’).(y’ + z) + y’
= (y’ + x’).(y’ + z) + y’
= y’ + x’z + y’
74
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
= y’ + x’z
= y’(x + x’) (z + z’) + x’z(y + y’)
= y’(xz + xz’ + x’z + x’z’) + x’yz + x’y’z
= xy’z + xy’z’ + x’y’z + x’y’z’ + x’yz + x’y’z
= xy’z + xyz’ + x’y’z + x’y’z’ + x’yz
Una función booleana puede ser expresada en forma normal disyuntiva en más de una
manera, mediante el cambio del número de variables; sin embargo, para un número
dado de variables la forma normal es única.
Por ejemplo, f = xy está en forma normal disyuntiva en x y en y pero si xy es
multiplicada por z + z’, entonces f = xyz + xyz’ está también en forma normal en las
variables, x, y, z.
En forma similar, g = x’yz + xyz + x’yz’ + xyz’ está en forma normal disyuntiva en x,
y, z, pero reduciéndola se llega a g = y, la cual está en forma normal en y.
La forma normal disyuntiva en n variables que tiene 2n términos se llama “forma
normal disyuntiva completa en n variables” y es idénticamente igual a la unidad. Por
ejemplo, para el caso de dos variables (n = 2) la forma normal disyuntiva se puede
obtener de la tabla:
x
0
0
1
1
y
0
1
0
1
f
x’y’
x’y
xy’
xy
x’y’ + x’y + xy’ + xy = 1
Cuyo valor es 1 porque
x’y’ + x’y + xy’ + xy = x’(y’ + y) + x(y’+y)
= x’1 + x1
= x’ + x
=1
Una función booleana f está completamente determinada por los valores que ella asuma
para cada una de las combinaciones de los valores asignados, 0 ó 1, a las respectivas
variables. Esto sugiere que una función booleana puede ser convenientemente
especificada mediante una tabla que represente las condiciones deseadas. En las
aplicaciones tecnológicas, particularmente en el diseño de circuitos lógicos, ésta es la
manera como se construyen las funciones booleanas. Si la tabla es dada, entonces la
función, en forma normal disyuntiva, puede ser escriba por inspección. Para cada
conjunto de condiciones que producen un 1 en la tabla, el término correspondiente es
incluido en la forma normal disyuntiva. La suma de estos tres términos da la función,
aunque no necesariamente en su forma más simple.
75
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejemplo 2
Encontrar y simplificar la función booleana f(x,y,z) especificada en la tabla 4.4.:
Fila
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f(x,y,z)
0
1
0
0
0
1
1
0
Tabla 4.4
La tabla 4.4. muestra el valor de f para cada una de las 23 = 8 posibles combinaciones de
valores de 0 y 1 para x,y,z. Las combinaciones representadas en las filas, 1, 5 y 6 de la
tabla tienen valor 1. así la forma normal disyuntiva de f contendrá tres términos:
F(x,y,z) = x’y’z + xy’z + xyz’
= y’z(x’ + x) + xyz’
= y’z.1 + xyz’
= y’z + xyz’
Una aplicación de lo anterior consiste en encontrar, por simple inspección, el
complemento de una función en forma normal disyuntiva. Dicho complemento
contendrá exactamente aquellos términos de la forma normal disyuntiva completa que
no aparecen en la función dada. El complemento de x’y’ + x’y es xy’ + xy.
El complemento de x’y’z’ + x’y’z + x’yz’ + x’yz + xy’z’ es xy’z + xyz’ + xyz
Forma normal conjuntiva
Una función booleana adopta la forma normal conjuntiva si está escriba como un
producto de términos, en el cual cada término es una suma que involucra todas las n
variables, con complementación o sin ella. Cada término se denomina término maximal
o maxterm.
El proceso para obtener la forma normal conjuntiva de una función booleana consiste en
aplicar las leyes de D’Morgan para quitar los complementos de los paréntesis. Después,
la función es factorizada y luego se introducen la(s) variable(s) que falta(n) en cada
factor, por ejemplo w, sumando un término de la forma w.w’ que no cambia la función.
El paso final es expandirla en factores y reducir aquellos que sean semejantes.
76
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejemplo 3
Escribir la función (xy + yz’)’ + y’ en la forma normal conjuntiva.
(xy + yz’)’ + y’ = (xy)’.(yz’)’ + y’
= (x + y’).(y’ + z) + y’
= y’ + (x’ + y’) + (y’ + z)
= (y’ + x’ + y’) (y’ + y’ + z)
= (x’ + y’) (y’ + z)
= (x’ + y’ + zz’). (xx’ + y’ + z)
= (x’ + y’ + z)(x’ ´y’ + z’) (x ´y’ + z) (x’ + y’ + z)
= (x’ + y’ + z).(x’ + y’ + z’) (x + y’ + z)
Una función booleana puede ser expresada en forma normal conjuntiva en más de una
manera, mediante el cambio del número de variables; sin embargo, para un número
dado de variables la forma normal es única. Por ejmplo, f = x + y está en forma normal
en x y en y, pero si a x + y se le suma z.z’ entonces f = x + y + zz’ ó f = (x + y + z) (x +
y + z’) está también en forma normal en las variables x, y, z. Por otra parte, g = (x’ + y
+ z) (x + y + z) (x’ + y + z’) está en forma normal conjuntiva en x.y.z pero
simplificándola se obtiene g = y que está en forma normal en y.
La forma normal conjuntiva en n variables que tiene 2n términos se llama la forma
normal conjuntiva completa en n variables y es igual a cero. Por ejemplo, para el
caso de dos variables (n 0 2) la forma normal conjuntiva completa se puede obtener de
la siguiente tabla, al tomar las variables complementadas.
x
0
0
1
1
y
0
1
0
1
f
x + y’
x+y
x’ + y’
x’ + y
(x + y) (x + y’) (x’ + y) (x’ + y’)
Porque
(x + y) (x + y’) (x’ + y) (x’ + y’)
= (x + yy’) (x’ + yy’)
= (x + 0) (x’ + 0=
= xx’
=0
77
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejemplo 4
Encontrar y simplificar la función booleana f(x,y,z) especificada en la tabla 4.5.
Fila
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f(x,y,z)
1
0
1
1
1
0
1
1
Tabla 4.5
Como sólo dos filas de la tabla, la 1 y la 5, tienen el valor cero, es más fácil escribir la
función en forma normal conjuntiva, así:
F(x,y,z) = (x + y + z’) . (x’ + y + z’)
= (y + z’ + x) . (y + z’ + x’)
= (y + z’ + xx’)
= y + z’ + 0
= y + z’
En los ejemplos de este tipo, la forma normal disyuntiva se usa si el número de unos (1)
es menor que el número de ceros (0) en la columna f, y la forma normal conjuntiva se
usa si el número de ceros (0) es menor que el número de unos (1).
Dos funciones, cada una expresada en la forma normal conjuntiva en n variables, son
iguales si tienen idénticos factores.
La forma normal conjuntiva puede usarse para hallar el complemento de funciones
escritas en esta forma. El complemento de una función escriba en forma normal
conjuntiva es una función cuyos factores son exactamente aquellos de la forma normal
conjuntiva completa, los cuales no aparecen en la función dada. Por ejemplo el
complemento
de
(x
´y’)
(x’
+
y’)
es
(x’ + y) (x + y).
Para cambiar una función de una forma normal a la otra se utiliza (f’)’ = f. El siguiente
ejemplo ilustra el método.
Ejemplo 5
Encontrar la forma normal conjuntiva para la función f = xyz + x’yz + xy’z’ + x’yz’
(f’)’
=
=
[(xyz + x’yz + xy’z’ + x’yz’)’]’
[(x’ + y’ + z´) (x + y’ + z’) (x’ + y + z) (x + y’ + z)]’
78
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
=
(x + y + z) (x’ + y + z’) (x + y + z’) (x’ + y’ + z)
El apóstrofo significa la complementación de toda la expresión entre paréntesis.
Después de negar doblemente la función, la primera negación se trata con la ayuda de
las leyes de D’Morgan; para la segunda negación (la del corchete) se construye el
complemento, es decir, se buscan los términos que allí faltan para totalizar la forma
normal conjuntiva completa.
Ejemplo 6
Hallar la forma normal conjuntiva para la función: f = xyz + xyz’ + xy’z + xy’z’ +
x’y’z’
(f’)’
= [(xyz + xyz’ + xy’z + xy’z’ + x’y’z’)’)’
= [(x’ + y’ + z´) .(x’ + y’ + z). (x’ + y + z’). (x’ + y + z).(x + y+ z)]’
= (x + y’ + z´) (x + y’ + z) (x + y + z)
79
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
SIMPLIFICACIÓN DE EXPRESIONES BOOLEANAS
Para simplificar expresiones booleanas, además de las leyes del álgebra lógica, se
emplea un método llamado mapas de Karnaugh o mapas K.
Estos son diagramas cuadrangulares o rectangulares que tienen 2n compartimentos o
casillas, donde n es el número de variables lógicas consideradas. Los diagramas asocian
a cada compartimiento una fila de tabla de verdad. El número binario que identifica
cada fila de la tabla de verdad se hace corresponder con las coordenadas binarias que
identifican cada casilla del mapa K. En estos mapas se puede trabajar con términos
minimales (miniterms) llenando los compartimentos correspondientes a los unos (1) que
aparezcan en la tabla de verdad de la función considerada, o con términos maximales
(maxiterms) con los ceros (0) de la tabla de verdad. El uso de minterms o de maxterms
depende de la forma elegida para la expresión: la forma normal disyuntiva o la forma
normal conjuntiva, respectivamente.
Mapa de Karnaugh para dos variables
Una expresión booleana con dos variables, es decir f(x,y), tiene una tabla de verdad con
cuatro filas, conteniendo cada una el valor de la función para cada combinación de
valores de verdad de las variables x, y. El mapa K correspondiente es una tabla de 2.2.
casillas como se muestra a continuación:
x’ = 0
x=1
y’ = 0
y=1
Si dos casillas contiguas (horizontal o verticalmente, no en diagonal) tienen unos (1), se
dice que forman una adyacencia. Por ejemplo, si en el mapa K sólo aparecen unos (1)
en el primer renglón, entonces la función booleana en forma normal disyuntiva es:
y' = 0
x' = 0
x=1
1
1
y=1
f(x,y) = x’y’ + xy’
= y’x’ + y’x
= y’(x’ + x)
= y’.1
= y’
80
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Note que al simplificar la expresión se anula la variable x porque x ´x’ = 1. Además
ambos unos (1) se encuentran en el primer renglón, es decir, se encuentran en el renglón
denominado y’, por lo tanto la expresión simplificada es:
f(x,y) = y’
Ejemplo 7
Simplificar la función booleana representada en la tabla:
x
y
f
0
0
0
0
1
1
1
0
1
1
1
1
El mapa K correspondiente a la tabla es:
x' = 0
x=1
y' = 0
1
y=1
1
1
Este mapa K tiene dos adyacencias, una en la segunda fila y la otra en la segunda
columna. La función sin simplificar es:
f(x,y) = x’y + xy’ + xy
Utilizando las adyacencias mencionadas se obtiene la función reducida:
f(x,y) = y + x
Observe que las adyacencias pueden sobreponerse y que los valores en una fila o una
columna pueden ser usados más de una vez. Además, una adyacencia de dos unos (1)
elimina una variable.
Mapas de Karnaugh para tres variables
El mapa K para tres variables es una tabla 2.4. como se presenta a continuación:
81
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
x’y’
00
x’y
01
xy’
10
xy
11
z’ = 0
z=1
Hay que observar que en el anterior mapa K para tres variables, la numeración binaria
se cambia de la segunda columna a la tercera, es decir, se pasa de 01 a 11, no a 10. la
única razón para esto es que es deseable que haya cambio en una sola variable y no en
ambas, como sucedería si al 01 le sigue 10. de esta forma pueden distinguirse seis
regiones.
Región de x
Región de x’
Región de y
Región de y’
Región de z
Región de z’
: columnas 3° y 4°
: columnas 1° y 2°
: columnas 2° y 3°
: columnas 1° y 4°
: fila 2°
: fila 1°
En este caso pueden ocurrir adyacencias de dos, cuatro u ocho unos (1). También se
considera las adyacencias entre la primera y la cuarta columna, tal como si el mapa K
fuera dibujado sobre un cilindro. Además, las adyacencias pueden estar en una sola fila
o formando un cuadrado. Los ejemplos siguientes ilustran lo anterior.
Ejemplo 8
Encontrar la expresión booleana simplificada cuyo mapa K es:
x'y'
00
x'y
01
xy
11
xy'
10
z' 0
1
1
z1
1
1
Al existir una adyacencia de cuatro unos (1), la función booleana de tres variables se
reduce a una sola. Observe que la adyacencia está en la primera y cuarta columna, es
decir, en la región de y’, por tanto, la función booleana simplificada será:
f(x,y,z) = y’
Para demostrar lo anterior, se escribe la función en forma normal disyuntiva, así:
f(x,y,z)
= x’y’z’ + x’y’z + xy’z’ + xy’z
= x’y’(z’ + z) + xy’(z’ + z)
= x’y’ + xy’
= y’(x’ + x)
= y’
82
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejemplo 9
Encontrar la expresión booleana simplificada cuyo mapa K es:
x'y'
00
x'y
01
xy
11
z' 0
1
1
z1
1
1
xy'
10
La adyacencia está en la segunda y tercera columna, es decir, en la región de y, por lo
que la función booleana simplificada será:
f(x,y,z) = y
Para demostrar lo anterior, se escribe la función en forma normal disyuntiva:
f(x,y,z)
= x’y’z’ + x’y’z + xy’z’ + xy’z
= x’y(z’ + z) + xy(z’ + z)
= x’y + xy
= y(x’ + x)
=y
Mapas de Karnaugh para cuatro variables
El mapa K para funciones booleanas de cuatro variables es una talba de 4.4. diseñada de
la siguiente forma:
x'y'
00
z'w'
00
z'w'
01
zw
11
zw'
10
x'y
01
xy
11
xy'
10
Como en el caso anterior, pueden distinguirse ocho regiones así:
Región de x
Región de x’
Región de y
Región de y’
Región de z
: columnas 3° y 4°
: columnas 1° y 2°
: columnas 2° y 3°
: columnas 1° y 4°
: fila 3° y 4°
83
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Región de z’ : fila 1° y 2°
Región de w : fila 2° y 3°
Región de w’ : fila 1° y 4°
Aquí pueden ocurrir adyacencias de dos, cuatro, ocho o diecisésis unos (1) que eliminan
una, dos, tres o cuatro variables, respectivamente. Se consideran adyacencias entre la
primera y cuarta columna y también entre la primera y cuarta fila como puede verse en
los ejemplos siguientes:
Ejemplo 10
Simplificar la función booleana cuyo mapa K asociado es:
x'y'
00
x'y
01
xy
11
z'w'
00
1
z'w'
01
1
1
zw
11
1
1
zw'
10
1
xy'
10
1
1
f(x,y,z,w) = x’y’z’w’ + xy’z’w’ + x’y’zw’ + xy’zw’ + x’yz’w + xyz’w + x’yzw + xyzw
= y’z’w’(x’ + x) + y’zw’(x’ + x) + yz’w(x’ + x) + yzw(x’ + x)
= y’z’w’ + y’zw’ + yz’w + yzw
= y’w’(z’ + z) + yw’(z’ + z)
= yw + y’w’
84
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Ejemplo 11
Simplificar la función booleana cuyo mapa K asociado es:
x'y'
00
x'y
01
xy
11
xy'
10
z'w'
00
1
1
z'w'
01
1
1
zw
11
1
1
zw'
10
1
1
f(x,y,z,w) = x’y’z’w’ + x’y’z’w + x’y’zw + x’y’zw’ + xy’z’w’ + xy’z’w + xy’zw +
xy’zw’
= x’y’z’(w’ + w) + x’y’z(w’ + w) + xy’z’(w’ + w) + xy’z(w’ + w)
= x’y’z’ + x’y’z + xy’z’ + xy’z
= x’y’(z’ + z) + xy’(z’ + z)
= x’y’ + xy’
= y’(x’ + x)
= y’
En los ejemplos anteriores la consideración de las adyacencias señaladas conducen
directamente a las expresiones simplificadas, observando las regiones del mapa K en las
que se encuentran estas adyacencias.
RESUMEN
Resumen de operaciones y compuertas
Lógica
Disyunción
pq
Conjuntos
Unión
AB
Conjunción
pq
Intersección
AB
Negación
~p
Complemento
A’
85
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Algebra
Suma Booleana
x+y
Producto
xy
Inversor
x’
AND
NOT
Compuertas lógicas
OR
Leyes
P1: Conmutativas:
P2: Distribuitiva
x+y=y+x
xy = yx
x + yz = (x + y)(x + z)
x(y + z) = xy + xz
P3: Modulativas
x.1 = x
x+0= x
P4: Complemento
x + x’ = 1
x.x’ = 0
T1: Asociativa
x + (y + z) = (x + y) + z
x.(yz) = (xy).z
T2: Idempotencia:
x+x=x
x.x = x
T3: Acotación:
x+1=1
x.0 = 0
T4: Absorción:
x + xy = x
x(x + y) = x
T5: Involución:
(x’)’ = x
T6: De Morgan:
(x.y)’ = x’ + y’
(x + y)’ = x’.y’
(0’)’ = 0
(1’)’ = 1
86
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
Expresiones Booleanas
Forma normal disyuntiva completa (n = 2)
x
y
f
0
0
x’y’
0
1
x’y
1
0
xy’
1
1
xy
f = x’y’ + x’y + xy’ + xy = 1
Forma normal conjuntiva completa (n = 2)
x
0
0
1
1
y
0
1
0
1
f
x + y’
x+y
x’ + y’
x’ + y
f = (x + y) (x + y’) (x’ + y) (x’ + y’) = 0
EJERCICIOS RESUELTOS
1. Escribir las siguientes funciones en forma normal disyuntiva (polinomial de
términos minimales o minterms):
a) (y + z’y).(y ´xz)
b) (xz + yz’)(xy + xz + y’z’)
Respuesta:
a) (y + z’y).(y ´xz) = y ´z’y.xz
= y + xy(z.z’)
= y + xy(0)
=y+0
=y
= y(x + x’) (z + z’)
= (xy + x’y)(z + z’)
= xxyz + xxyz’ + x’yz + x’yz’
Distributiva
Asociativa
Complemento
Acotación
Modulativa
Complemento
Distributiva
Distributiva
b) (xz + yz’)(xy + xz + y’z’) = (xz + yz’)[xz + (xy + y’z’)]
= xz + yz’.(xy + y’z’)
= xz + yz’.xy + yz’.y’z’
Asociativa
Distributiva
Distributiva
87
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
= xz + xyz’ + (y.y’)z’
Conmutativa
= xz + xxyz’ + (0)z’
Invertiva
= xz + xyz’
Acotación
= x(z + yz’)
Distributiva
= x(z + y) (z + z’)
Distributiva
= x(y + z)
Conmutativa
= xy + xz
Distributiva
= xy(z + z’) + xz (y + y’)
Complemento
= xyz + xyz’ + xyz + xy’z
Distributiva
= xyz + xyz’ + xy’z
Idempotencia
2. Escribir las siguientes expresiones en forma normal conjuntiva (términos maximales
o maxterms):
a) xz’ + y
b) (x + z)y’ + yz’
Respuesta:
a) xz’ + y = y + xz’
= (y + x).(y + z)
= (y + x + x.x’).(y + z’ + x.x’)
= (x + y + z)(x + y + z’)(y + z’ + x) (y + z’ + x’)
= (x + y + z)(x + y + z’) (x’ + y + z’)
Conmutativa
Distributiva
Complemento
Distributiva
Idempotencia
b) (x + z)y’ + yz’ = xy’ + y’z + yz’
Distributiva
= xy’ (z + z’)+ y’z (x + x’)+ yz’(x + x’)
Complemento
= xy’z + xy’z’ + xy’z + xyz’ + x’yz’
Distributiva
= xy’z + xy’z’ + x’y’z + xyz’ + x’yz’
Idempotencia
= [(x’ + y + z’)(x’ + y + z)(x + y + z’)(x’ + y’ + z)(x + y’ +z)]’
D’Morgan
= (x’ + y’ + z’)(x + y’ + z’)(x + y + z)
Complemento
3. Simplificar las siguientes expresiones booleanas:
a) xy’x’y’
c) xz’ + xyz + xz
Respuesta:
a) xy’x’y’ = (x.x’)(y’.y’)
= 0.y’
=0
b) xy + xy’ + x’y + x’y’
d) xyz + x’ + y’ + z’
Asociativa
Complemento
Acotación
88
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
b) xy + xy’ + x’y + x’y’ = 1 Forma normal disyuntiva completa en dos variables
c) xz’ + xyz + xz = xz’ + [xz + (xz)y)
= xz’ + xz
= x(z + z’) = x.(1)
=x
Asociativa
Absorción
Complemento
Modulativa
d) xyz + x’ + y’ + z’ = xyz + (x’ + y’ + z’)
= xyz + (xyz)’
=1
Asociativa
D’Morgan
Complemento
4. Simplificar las siguientes expresiones booleanas:
a) (xy + x’y + x’y’)’
c) x’z + y’z + xyzw’
e) (x’yz’)’.(xy’z’)’
b) (x + y’ + z)(xy.x’z)’
d) (xw + y’z’)(yz + yz’ + y’z)’
f) (xyz + yz + x’y)yz
Respuesta:
a) (xy + x’y + x’y’)’ = xy’
b) (x + y’ + z)(xy.x’z)’ = (x + y’ + z) [(x.x’)yz]’
= (x + y’ + z) [(0)yz]’
= (x + y’ + z) [0]’
= (x + y’ + z) 1
= (x + y’ + z)
Conmutativa
Complemento
Acotación
Complemento
Acotación
c) x’z + y’z + xyzw’
Distributiva
Doble negación
D’Morgan
D’Morgan
Distributiva
Complemento
D’Morgan
= z(x’ + y’ + xyw’)
= z[(x’ + y’ + xyw’)’]’
= z[x.y.(xyw’)’]’
= z[xy(x’ + y’ + w)]’
= z[xyx’ + xyy’ + xyw]’
= z[0.y + x.0 + xyw]’
= z(xyw)’
d) (xw + y’z’)(yz + yz’ + y’z)’ = (xw + y’z’).y’z’
= xwy’z’ + y’z’. y’z’
= xwy’z’ + y’z’
= (y’z’) + (y’z’)(xw)
= y’z’
Complemento
Distributiva
Idempotencia
Conmutativa
Absorción
e) (x’yz’)’.(xy’z’)’ = [(x’yz’) + (xy’z)’]’
= [(x + y’ + z)’ + (x’ + y + z)’]’
D’Morgan
D’Morgan
89
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
= [(x + y’ + z)’ + (x’ + y + z)’
= [(x + y’ + z) + (x’ + y + z)
= z + (x’ + y) (x + y)
= z + x’x + x’y’ + yx + yy’
= z + x’y’ + xy
f) (xyz + yz + x’y)yz = yz.y(xz + z + x)
= yz(z + x’)
= yz.z + yzx’
= yz + yzx’
= yz
D’Morgan
Doble complemento
Distributiva
Distributiva
Complemento
Distributiva
Absorción
Distributiva
Idempotencia
Absorción
5. Escribir cada una de las siguientes expresiones en forma normal disyuntiva en las
tres variables x, y, z.
a) x’ + y
b) x’z + xz’
c)(y + z) (y’ + z’)
d) x
Respuesta:
a) x’ + y = x’(y + y’) (z + z’) + y (x + x’)(z + z’)
Complemento
= (x’y + x’y’)(z + z’) + (xy + y’y)(z + z’)
Distributiva
= x’yz + x’yz’ + x’y’z + x’y’z’ + xyz + xyz’ + x’yz + x’yz’
Distributiva
= x’y’z’ + x’y’z + x’yz’ + x’yz + xyz’ + xyz
Idempotencia
b) x’z + xz’ = x’z(y + y’) + xz’(y + y’)
= x’yz + x’y’z + xyz’ + xy’z’
Complemento
Distributiva
c) (y + z) (y’ + z’) = {[(y + z).(y’ + z’)]’}’
= [(y + z)’ + (y’ + z’)]’
= (y’z’ + yz)’
= y’z(x + x’) + yz(x + x’)
= xy’z + x’y’z + xyz’ + x’yz’
Doble negación
Doble D’Morgan
Complemento
Complemento
Distributiva
d) x = x(y + y’)(z + z’)
= x[(y + y’).z + (y + y’)z’]
= x[(yz + y’z + yz’ + y’z
= xyz + xy’z + xyz’ + xy’z’
Complemento
Distributiva
Distributiva
Distributiva
90
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
6. Escribir las funciones, f1, f2, y f3 especificadas en la siguiente tabla en forma normal
disyuntiva y simplificarlas:
x
y
z
f1
f2
f3
0
0
0
0
1
1
0
0
1
0
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
0
0
0
1
0
1
0
1
0
1
1
1
1
0
1
0
0
1
1
1
1
0
1
Respuesta:
a) f1
= x’yz + x’yz + xyz’ + xyz
= x’y(z + z’) + xy(z + z’)
= x’y(1) + xy(1)
= x’y + xy
= y(x’ + x)
= y(1)
=y
b) f2
= x’y’z’ + x’y’z + xy’z’ + xy’z
= x’y’(z’ + z) + xy’(z’ + z)
= x’y’(1) + xy’(1)
= y’(x’ + x)
= y’(1)
= y’
c) f3
= x’y’z’ + x’yz’ + xy’z + xyz
= x’y’(y’ + y) + xz(y’ + y)
= x’z’(1) + xz’(1)
= x’z’ + xz
91
Falcón/Nazario/Uribe
Matemáticas Discreta
FIA-2010-I
7. Escribir una expresión booleana para la salida f(x,y,z) del siguiente circuito, además
determinar el valor de F para todas las posibles entradas y hacer una lista en una
tabla de verdad.
x
y
z
f
Respuesta: f(x,y,z) = (x’ + y’).’(yz)
x
y
z
x’
y’
x’ + y’
(x’ + y’)’
yz
f
0
0
0
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
1
0
1
0
1
0
0
0
0
1
1
1
0
1
0
1
0
1
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
0
0
0
1
0
0
1
1
1
0
0
0
1
1
1
92
Falcón/Nazario/Uribe
