Curso Matemáticas Discretas

INTRODUCCIÓN A LA TEORÍA DE CONJUNTOS
EL CONCEPTO DE CONJUNTO ES FUNDAMENTAL EN MATEMÁTICA , incluso más que la operación

de contar, pues se puede encontrar implícita o explícitamente, en todas las ramas de las
matemáticas puras y aplicadas. En su forma explícita, los principios y terminología de los
conjuntos se utilizan para construir proposiciones matemáticas más claras y precisas y para
explicar conceptos abstractos como él.
DEFINICIONES
Sabemos que la palabra conjunto implica la idea de una colección de objetos que se caracterizan
en algo común.
En matemática tiene el mismo significado, sólo que a estos objetos se les llama elementos o
miembros del conjunto.
La noción simple de una colección o conjunto de objetos es fundamental en la estructura básica de

las matemáticas y fue George Cantor, en los años 1870 quien primero llamó la atención de los
matemáticos a este respecto.
No puede darse una definición satisfactoria de un conjunto en términos de conceptos simples, por
lo tanto, la palabra " CONJUNTO " debe aceptarse lógicamente como un TÉRMINO NO DEFINIDO .
El concepto de conjunto es simplemente intuitivo.
NOTACIÓN
Usualmente los conjuntos se representan con una letra mayúscula:
A, B, C, D, E,…
Llamaremos elemento, a cada uno de los objetos que forman parte de un conjunto, estos
elementos poseen características muy particulares y propias de su individualidad, tienen
cualidades que nos permiten diferenciarlos, y cada uno de ellos es único, no habiendo elementos
duplicados o repetidos. Los representaremos con una letra minúscula, los elementos de un
conjunto se escriben entre llaves y separados por comas:
a, b, c, d, e, f, ….
De esta manera, si A es un conjunto, y a, b, c, d, e todos sus elementos, es común escribir:
A = {a, b, c, d, e}
para definir a tal conjunto .

RELACIÓN DE PERTENENCIA
Se denomina relación de pertenencia en teoría de conjuntos a la relación que se da entre en un
elemento y un conjunto (y no a la inversa).
Así por ejemplo si el conjunto V = {a, e, i, o, u} o sea el conjunto V está formado por las letras
vocales del idioma español, entonces podemos afirmar que cualquiera de esas vocales es un
elemento del conjunto V.
En otras palabras, tenemos que:
a pertenece a V , e pertenece a V y así sucesivamente con cada uno de los elementos del conjunto.
Tal relación se representa simbólicamente de la siguiente manera:
Volviendo al conjunto anterior, también podemos afirmar que:
Y se representa simbólicamente de la siguiente manera:
DETERMINACIÓN DE UN CONJUNTO
Hay dos formas de determinar conjuntos.
POR EXTENSIÓN
Se dice que un conjunto es determinado por EXTENSIÓN (o enumeración), cuando se da una lista
que comprende a todos los elementos del conjunto y sólo a ellos.
Ejemplos:
A={a, e, i, o, u} entonces 𝑎𝑎 ∈ 𝐴𝐴, 𝑜𝑜 ∈ 𝐴𝐴 pero 𝑣𝑣 ∉ 𝐴𝐴
B={0, 2, 4, 6, 8}
C = { m, a, t, e, i, c, s } En un conjunto determinado por extensión no se repite un mismo elemento y

contiene cada una de las letras de la palabra matemáticas.
POR COMPRENSIÓN
Se dice que un conjunto es determinado por COMPRENSIÓN, cuando se enuncia una propiedad
que la cumpla en todos los elementos del conjunto y tal que es válida sólo a ellos.
Ejemplos:
A = {x/x es una letra vocal}
B = {x/x es un número positivo par menor que 10}, entonces 2 ∈ 𝐵𝐵 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 5 ∉ 𝐵𝐵
C = {x/x es una letra de la palabra matemáticas}
Vamos a mostrar un cuadro comparativo de determinación de conjuntos
Por extensión
A = { a, e, i, o, u }
B = { 0, 2, 4, 6, 8 }
C = { c, o, n, j, u, t, s }
D = { 1, 3, 5, 7, 9 }
E = { b, c, d, f, g, h, j, . . ., x, y, z}
Por comprensión
A = { x/x es una vocal }
B = { x/x es un número positivo par menor que 10 }
C = { x/x es una letra de la palabra conjuntos }
D = { x/x es un número positivo impar menor que 10 }
E = { x/x es una consonante del alfabeto español}
DIAGRAMAS DE VENN
Los diagramas de Venn tienen el nombre de su creador, John Venn,

matemático y filósofo británico. Venn introdujo el sistema de
representación que hoy conocemos en julio de 1880 con la
publicación de su trabajo titulado « De la representación mecánica
y diagramática de proposiciones y razonamientos» en el
Philosophical Magazine and Journal of Science , adentrándose de
esta manera en el mundo de la lógica formal. El método de Venn
superaba en claridad y sencillez a los sistemas de representación
anteriores, convirtiéndose con el tiempo en un nuevo estándar. Venn fue el primero en formalizar
su uso y en ofrecer un mecanismo de generalización para los mismos.
Posteriormente desarrolló su nuevo método en su libro Lógica simbólica, publicado en 1881 con el
fin de interpretar y ampliar nociones del Álgebra de Boole en el campo de la lógica formal. Su libro
se convirtió en una excelente plataforma de ejemplo para el nuevo sistema de representación.
Siguió usándolo en su siguiente libro sobre lógica (Los principios de la lógica empírica, publicado
en 1889), con lo que los diagramas de Venn se constituyen a partir de entonces como un recurso
de representación de relaciones lógicas.
En un Diagrama de Venn cada conjunto se representa mediante un óvalo, círculo o rectángulo. Al

superponer dos o más de las anteriores figuras geométricas, el área en que confluyen indica la
existencia de un subconjunto que tiene características que son comunes a ellas; en el área
restante, propia de cada figura, se ubican los elementos que pertenecen únicamente a esta. En un
diagrama de Venn de dos conjuntos tiene tres áreas claramente diferenciadas: A, B y [A y B].
CONJUNTOS FINITOS
Un conjunto es finito si consta de cierto número de elementos distintos, es decir si al contar los
diferentes elementos del conjunto el proceso de contar termina. En caso contrario, el conjunto es
infinito.
Ejemplos:
M = {x / x es un alumno matriculado en el curso Matemática Discreta} Conjunto finito
N = {0, 1, 2, 3, 4, 5, 6, 7, 8, ... } Conjunto infinito
P = {x / x es un país miembro de la Organización de Naciones Unidas} Conjunto finito
V = {3, 6, 9, 12, 15, 18, 21, 24, 27, ... } Conjunto infinito
IGUALDAD DE CONJUNTOS
Se dice que 2 conjuntos A y B son iguales cuando ambos tienen los mismos elementos, es decir si
cada elemento de A pertenece a B y si cada elemento que pertenece a B pertenece también a A. La
igualdad se denota A = B.
En la igualdad, el orden de los elementos de cada conjunto no importa.
Ejemplos:
A = {1, 2, 3, 4} B = {3, 4, 1, 2} A= B
C = {1, 2, 3, 3, 4, 1} D = {1, 2, 2, 3, 3, 4,} C= D
E = {x/x es una vocal de la palabra mundo} F = {u, o} E = F
CONJUNTO VACÍO
Es un conjunto que no posee elementos. Suele llamársele conjunto nulo, y se le denota por el
símbolo ø o { }
Ejemplos:
A= { x/x es número natural menor que 0 } A = { } A = Ø
B = { x / x es un mes que tiene 33 días} B = { } B = Ø
C = { x / x = 8 y x es impar } C = { } C = Ø
D = { x / x es un día terrestre de 90 horas } D = { } D = Ø
CONJUNTO UNITARIO
Es todo conjunto que está formado por un sólo y único elemento.
Ejemplos:
A = {5}
B = {x/x es un número par entre 6 y 10} = {8}
C = {x/x es la capital de Costa Rica} = {San José}
D = {x / 2x = 6} = {3}
CONJUNTO UNIVERSAL
Es el conjunto que contiene a todos los elementos del discurso, dicho de otra manera, es el
conjunto referencias de todos los elementos que estemos manejando. Es un término relativo. Se le
denota por la letra U.
Ejemplos:
Sean los conjuntos:
P={x/x es un número primo par}
X={0, 2, 4, 6, 8, 10}
I={x/x es un número positivo impar menor que 11}
Existe otro conjunto que incluye a los conjuntos P, X, I. Es
U = {x/x es un número positivo menor o igual que 10}
Gráficamente se representa por un rectángulo tal como se observa a continuación.

CARDINALIDAD DE UN CONJUNTO
La cardinalidad de un conjunto es un concepto que se refiere al número de elementos que tiene

dicho conjunto. En el diagrama anterior la cardinalidad de U es 10 y se representa así:
N(U)=10 o #(U)=10
SUBCONJUNTOS
Decimos que un conjunto A es subconjunto de otro B, si cada elemento de A lo es de B. En este caso

escribimos . Si A no es un subconjunto de B, se escribe
En términos simbólicos esto suele ser expresado de la siguiente forma:
Que leemos A está contenido en B si y solo si cada elemento de A, es elemento de B.
Ejemplos:
1. Se tiene que
Por otra parte, si denota el conjunto de los números racionales, entonces
2. Sean A = {1, 2, 3, 4, 5, 6}, B = {2, 4, 5} y C = {1, 2, 3, 4, 5}.
Entonces,
3. Si A es un conjunto cualquiera,
Es decir, todo conjunto es un subconjunto de sí mismo.

CONJUNTO DE CONJUNTOS
Es un conjunto cuyos elementos son todos conjuntos.
Ejemplo:
F = {{}, {a}, {a, b}, {a,b,c}}
Solamente en este caso es válido decir que {a} es un elemento de F, o sea
Pero no es correcto indicar que , ya que en este caso particular
CONJUNTO POTENCIA
El conjunto potencia de un conjunto M está formado por la familia de todos los subconjuntos del
conjunto M se le llama Conjunto Potencia de M. Se le denota como 2M
Ejemplos:
a) M = { 1, 2 } El conjunto M tiene 2 elementos, la cardinalidad de M es 2.
2M = { {1}, {2}, {1, 2}, ø} entonces M tiene 22 = 4 subconjuntos
b) M = { 1, 2, 3 } El conjunto M tiene cardinalidad 3.
2M = { {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, ø} entonces M tiene 23 = 8 subconjuntos
Si un conjunto M es finito con "n" elementos, entonces su cardinalidad es “n” y el conjunto

potencia 2M tendrá 2n elementos que corresponde al número de subconjuntos de M.
EJERCICIOS:
1. Sea A = {1, 2, 4, 6, a, b, c, d}. Escriba en cada caso una V si la proposición es verdadera y una
F si es falsa.
2. Sea . Identifique cada uno de los siguientes casos como verdadero o

falso.
3. En cada parte, escriba un conjunto por extensión con las letras de cada palabra.
a. condecoraciones b. pacifismo c. fundamentalismo
4. En cada caso, forme un conjunto listando sus elementos
a. El conjunto de todos los enteros positivos que son menores que diez
b.
5. En cada caso, escriba el conjunto por comprensión
a. {2, 4, 6, 8, 10}
b. {a, e, o}
c. {1, 8, 27, 64, 125}
d. {-2, -1, 0, 1, 2}
6. Sea A={1, 2, 3, 4, 5}. Marque con una X sobre la letra que antecede a cada conjunto si es
igual a A.
a. {4, 1, 2, 3, 5}
b. {2, 3, 4}
c. {1, 2, 3, 4, 5, 6}
d.
e.
f.
7. ¿Cuáles de los siguientes conjuntos son vacíos?
a.
b.
c.
d.
8. Haga una lista de todos los subconjuntos de {a, b}
9. Haga una lista de todos los subconjuntos de {java, c++, c}
10. Utilice el diagrama de Venn adjuntos para identificar si la proposición es verdadera o falsa.
a. ( )
b. ( )
c. ( )
d. ( )
e. ( )
f. ( )
g. ( )
OPERACIONES CON CONJUNTOS
UNIÓN DE CONJUNTOS
Se llama UNIÓN de dos conjuntos A y B al conjunto formado por los elementos de A o de B, es

decir:
Ejemplo: Sean A = {a, b, c, d, e, f} y B={b, d, r, s}
Entonces está formado por todos los elementos que pertenecen a A o a B.
Luego,
INTERSECCIÓN DE CONJUNTOS
Se llama INTERSECCIÓN de dos conjuntos A y B al conjunto formado por objetos que son
elementos de A y de B, es decir:
En la imagen la intersección es la parte obscura de la misma.
Ejemplo:
Sean A = {a, b, c, e, f}, B = {b, e, f, r, s} y C = {a, t, u, v}.
Encuentre:
Como la intersección está formada por los elementos comunes de ambos conjuntos, se tiene que:
Cuando dos conjuntos no tienen elementos en común como B y C en el ejemplo anterior, se
denominan Conjuntos disjuntos.
DIFERENCIA DE CONJUNTOS
Dados dos conjuntos A y B, se llama DIFERENCIA al conjunto
Luego A-B se llama complemento de B con respecto a A
A–B
En el diagrama de Venn A-B está representado por la zona rayada.
Ejemplo:
Sean A = {a, b, c} y B = {b, c, d, e}. Entonces:
A – B = {a} y B – A = {d, e}.
Asimismo, se llama DIFERENCIA SIMÉTRICA entre A y B al conjunto
En el diagrama de Venn la diferencia simétrica está representada por las regiones menos oscuras.
(Lo que no tienen en común).
Ejemplo: Sean A = {a, b, c, d} y B = {a, c, e, f, g}. Entonces
COMPLEMENTO DE UN CONJUNTO
Si un conjunto A es subconjunto de otro conjunto universal U, al conjunto A ' formado por todos
los elementos de U, pero no de A, se llama complemento de A con respecto a U. Simbólicamente se
expresa:
Ejemplos:
a) Sean U = {m, a, r, t, e } y A = {a, e }
Su complemento de A es: A' = {m, t, r}
b) Sean U = {letras de la palabra aritmética} y A = { e, i, a }
Determinado por extensión tenemos
U = {a, r, i, t, m, e, c} A = { e, i, a } Su complemento es: A' = {r, t, m, c}
En forma gráfica:
PROPIEDADES DE LAS OPERACIONES BOOLEANAS
Las llamadas OPERACIONES BOOLEANAS (unión e intersección) verifican las siguientes

propiedades
Estas propiedades hacen que partes de U con las operaciones unión e intersección tenga una
estructura de álgebra de Boole.
Además de éstas, se verifican también las siguientes propiedades:
PROBLEMAS CON OPERACIONES CON CONJUNTOS

Mediante diagramas de Venn y las definiciones y aplicación de las distintas operaciones con
conjuntos se pueden resolver problemas, que nos preparan en el campo de la lógica formal.
Ejemplo: A una fiesta llegaron 150 personas, de las cuales 75 cantan, 85 bailan, 20 no cantan ni
bailan. ¿Cuántas personas cantan y bailan?
Solución: La pregunta lleva implícita una conectiva lógica y, que es parte importante de la
definición formal de la operación intersección. Por lo tanto, podemos representar el problema de
la siguiente manera:
R./ El número de personas que cantan y bailan es igual a 30.

EJERCICIOS:
1. Sean U={a, b, c, d, e, f, g, h, k} A={a, b, c, g} B={d, e, f, g} C={a, c, f} D={f, h, k}.

Escriba por extensión
a. b. c.
d. e. f.
g. h. i.
j. k. l.
m. n. o.
p. q. r.
s. t. u.
v. w. x.
2. Sean U={1, 2, 3, 4, 5, 6, 7, 8, 9} A={1, 2, 4, 6, 8} B={2, 4, 5, 9}

D={7, 8} . Escriba por extensión
a. b. c.
d. e. f.
g. h. i.
j. k. l.
m. n. o.
p. q. r.
s. t. u.
3. De acuerdo al diagrama: Identifique los siguientes casos como verdaderos o falsos
a. b.
c. d.
e. f.
g. h.
4. En una encuesta realizada a 150 personas sobre sus preferencias de tres productos
A, B y C, se encontró el siguiente resultado:
a. 82 consumen el producto A
b. 54 consumen el producto B
c. 50 sólo consumen el producto A
d. 30 sólo consumen el producto B
e. El número de personas que consumen sólo B y C es la mitad de las personas que
consumen sólo A y C
f. El número de personas que consumen sólo A y B es el triple de las personas que
consumen los tres productos
g. El número de personas que no consumen los productos mencionados son tantos
como los que consumen sólo C
Determinar
a. El número de personas que consumen sólo dos de los productos

b. El número de personas que no consumen A, B ni C
c. El número de personas que por lo menos consumen uno de los productos
CONJUNTO PRODUCTO Y PARTICIONES
CONJUNTO PRODUCTO
Un par ordenado (a, b) es un listado de los objetos a y b en un orden prescrito, donde aparece en
primer término y b, en segundo. En consecuencia, un par ordenado simplemente es una secuencia
de longitud 2. A partir del análisis anterior de las secuencias, se desprende que los pares
ordenados (a1, b1) y (a2, b2) son iguales sí y solamente sí a1 = a2 y b1 = b2.
Si A y B son dos conjuntos no vacíos, se define el conjunto producto o producto cartesiano A x B

como el conjunto de todos los pares ordenados (a, b) con a que pertenece a A y b que pertenece a
B. Así,
Ejemplo 1. Sean A = {1, 2, 3} y B = {a, b}
Entonces
A x B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
Observe que los elementos de A x B pueden ser dispuestos en forma tabular conveniente como se
muestra a continuación.
B
a b
A
1 (1, a) (1, b)
2 (2, a) (2, b)
3 (3, a) (3, b)
Ejemplo 2. Si A y B son como en el ejemplo 1, entonces
B x A = {(a, 1), (b, 1), (a, 2), (b, 2), (a, 3), (b, 3)}
De los ejemplos anteriores se ve que A x B no siempre es igual a B x A
Teorema 1. Para dos conjuntos finitos no vacíos cualesquiera A y B, se tiene que ,

donde se lee La cardinalidad de X.
Ejemplo 3. Una compañía de aseguradora clasifica a sus potenciales clientes de acuerdo con los
siguientes criterios:
Género: masculino (m); femenino (f)
Máximo nivel educativo: técnico (t); trabajador especializado (e); profesional (p); investigador (i)
Sean G = {m, f} y E = {t, e, p, i}. Entonces G x E contendrá todas las categorías de personas en que
se clasifica la población para ese mercado. Determinar G x E.
G x E = {(m,t), (f,t), (m,e), (f,e), (m,p), (f,p), (m,i), (f,i)}
Ejemplo 4. Una compañía de programación proporciona las tres características siguientes para
cada programa que se vende:
Lenguaje: C++ (p), C# (s), .NET (n)
Memoria: 4 Gb (4), 8 Gb (8), 16 GB (16)
Sistema Operativo: Linux (l), Windows (w)
Luego L = {p, s, n}, M = {4, 8, 16}, S = {l, w}
El producto L x M x S contiene todas las categorías que describen un programa en esa compañía y
hay 3 x 3 x 2 o sea 18 categorías en este esquema de clasificación. Determinar L x M x S
LxMxS={(p,4,l), (p,4,w), (p,8,l), (p,8,w), (p,16,l), (p,16,w), (s,4,l), (s,4,w), (s,8,l), (s,8,w), (s,16,l),
(s,16,w), (n,4,l), (n,4,w), (n,8,l), (n,8,w), (n,16,l), (n,16,w)}
PARTICIONES
Una partición o conjunto cociente de un conjunto no vacío P es una colección de subconjuntos no

vacíos de P tales que:
1. Cada elemento de P pertenece a uno de los conjuntos en Pi.
2. Si P1 y P2 son elementos distintos de P, entonces
Los conjuntos que hay en P se llaman bloques o celdas de la

partición. La siguiente figura muestra una Partición
P = {P1, P2, P3, P4, P5, P6, P7}
Consideremos los siguientes subconjuntos de A:
A1= {a, b, c, d}, A2= {a, c, e, f, g, h}, A3= {a, c, e, g}, A4= {b, d}, A5= {f, h}
{A1, A2} no es una partición ya que . Luego {A1, A5} es una partición de A en vista de que
no tienen elementos comunes.
¿Qué sucede con la colección {A3, A4, A5}.
Ejemplo: Sean:
Z = conjunto de todos los enteros,
A1= conjunto de todos los enteros pares, y
A2= conjunto de todos los enteros impares.
Entonces {A1, A2} es una partición de Z.
EJERCICIOS:
1. En cada parte, encuentre x o y de manera que el enunciado sea verdadero.

a. (x+2, 3) = (4, 3)
b. (1, 3y) = (x, 9)
c. (3x+1, 2) = (10, 2)
d. (c++, java)=(x, y)
2. En cada parte, encuentre x o y de manera que el enunciado sea verdadero.

a. (4x, 5) = (16, y)
b. (3x – 3, 3y – 1) = (5, 5)
c. (x , 25) = (49,y)
3. Sean A = {a, b, c} y B = {3, 5, 7}. Haga una lista de los elementos en:
a. A x B
b. B x A
c. A x A
d. B x B
4. Sean A = {Salas, Pérez} y B = {presidente, vicepresidente, secretario, tesorero}. Dé cada

uno de los tres casos siguientes:
1. A x B
2. B x A
3. A x A
5. Un fabricante de automóviles hace tipos diferentes de chasis (o armazón del auto) y tres
tipos de motores:
Tipo de armazón: sedán (s), coupé (c), vagón (v)
Tipo de motor: gasolina (g), diesel (d), híbrido (h)
Elabore una lista de todos los modelos posibles de autos.
6. Si A = {a, b, c}, B = {1, 2}, y C = {#, *}, escriba el conjunto A x B x C

7. Si A = {a/a es un número entero positivo} y B = {1, 2, 3}. Haga un esquema de cada uno de
los siguientes casos en el plano cartesiano.
a. A x B
b. B x A
8. Si A = {a / a es un número racional y -1 a 5} y B = {b / b es un racional y 1 b 5}, haga un

esquema de los siguientes casos en el plano cartesiano.
a. A x B
b. B x A
9. Sean A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} y

A1 = {1, 2, 3, 4} A2={5, 6, 7} A3={4, 5, 7, 9}
A4 = {4, 8, 10} A5={8, 9, 10} A6={1, 2, 3, 6, 8, 10}
¿Cuáles de las siguientes son particiones de A?
a. {A1 , A2, A5}

b. {A1, A3 , A5}
c. {A3, A6}
d. {A2, A3 , A4 }
10. Si P1 es el conjunto de los enteros positivos y P2 el conjunto de todos los enteros negativos,
¿es {P1, P2 } una partición de .
11. Si B = {0, 3, 6, 9, ….} escriba una partición de B que contenga:
a. Dos subconjuntos infinitos
b. Tres subconjuntos infinitos
SUCESIONES
Algunos conjuntos importantes se originan en relación con las sucesiones. Una sucesión es
simplemente una lista de objetos ordenados: Un primer elemento, un segundo elemento, un tercer
elemento, y así sucesivamente. Dicha lista puede finalizar después de n pasos, donde ,o
puede continuar indefinidamente. En el primer caso se dice que la sucesión es finita, y en el
segundo caso, la sucesión es infinita. Los elementos pueden ser todos diferentes o algunos estarán
repetidos.
Ejemplos:
a) 1, 0, 0, 1, 0, 0, 1, 1, 1 es una sucesión finita

b) 3, 8, 13, 18, 23,… es una sucesión infinita
c) 1, 4, 9, 16, 25, … es una sucesión infinita y corresponde a la lista de los
cuadrados de los números naturales
Puede ocurrir que la secuencia de términos de una sucesión no quede claramente definida por los
primeros términos que la conforman y también es útil conocer una forma corta de especificar una
sucesión. Existen dos clases de fórmulas para determinar una sucesión. En el ejemplo b) una
descripción natural de la sucesión consiste en indicar que los términos consecutivos se forman su-
mando 5 al término anterior. Si empleamos un subíndice para indicar la posición de cada término
de una sucesión, puede describirse dicha sucesión de la siguiente manera:
Una fórmula como la anterior, que se refiere al término anterior, para definir el siguiente término,
se llama recursiva o recurrente. Toda fórmula recursiva debe tener un punto de partida.
La descripción de la sucesión del ejemplo c) sería: . A las fórmulas de este tipo se

les llama explícitas, porque indican exactamente qué valor tiene cualquier término en particular.
Ejemplos:
d) La fórmula recursiva define la sucesión finita: 5, 10, 20, 40, 80, 160.
e) La sucesión infinita 3, 7, 11, 15, 19, 23, … puede definirse por la fórmula recursiva
f) La fórmula explícita describe la sucesión infinita:
-4, 16, -64, 256, …
g) La sucesión finita: 87, 82, 77, 72, 67 puede definirse por la fórmula explícita,
CONJUNTO CORRESPONDIENTE A UNA SUCESIÓN
Está constituido por todos los elementos distintos de la sucesión. En una sucesión el orden de los
elementos es importante, sin embargo, el orden en que se enlisten los elementos en el conjunto
carece de significado.
Ejemplos:
a) El conjunto correspondiente a los elementos del ejemplo c) es {1, 4, 9, 16, 25, …}
b) El conjunto correspondiente a los elementos del ejemplo a) es {0, 1}
REPRESENTACIÓN EN COMPUTADORA DE CONJUNTOS Y SUBCONJUNTOS
Si A es un subconjunto de un conjunto universal U, la función característica fA de A se define como

sigue:
Para representar un conjunto en una computadora, debe disponerse los elementos del conjunto en
una sucesión. Cuando un conjunto universal U es finito y A es subconjunto de U, entonces la
función característica asigna un 1 a los elementos que pertenecen a A y 0 a los que no pertenecen a
A. Así f A puede ser representada por una sucesión de ceros y unos de longitud n.
Ejemplo:
Sea . Entonces
EJERCICIOS:
1. En cada caso escriba el conjunto correspondiente a la sucesión.
a. 2, 1, 2, 1, 2, 1, 2, 1
b. 0, 2, 4, 6, 8, 10, …
c. aabbccddee…zz
d. abbcccdddd
2. En cada caso, escriba los cuatro primeros términos (comience con n=1) de la sucesión
cuyo término general se da.
a.
b.
c.
d.
3. En los ejercicios, escriba una fórmula para el término de orden n de la sucesión.

Identifique su fórmula como recursiva o explícita.
a. 1, 3, 5, 7, …
b. 0, 3, 8, 15, 24, 35, …
c. 1, -1, 1, -1, 1, -1, …
d. 0, 2, 0, 2, 0, 2, …
e. 1, 4, 7, 10, 13, 16
f.
4. Escriba una fórmula explícita para la sucesión 2, 5, 8, 11, 14, 17, …

5. Escriba una fórmula recursiva para la sucesión 2, 5, 8, 11, 14, 17, …
6. Sean U = {Fortran, Pascal, Ada, Cobol, Lisp, Basic, C++, Forth}, B = { C++, Basic, Ada}, C
= {Pascal, Ada, Lisp, C++}, D = { Fortran, Pascal, Ada, Basic, Forth}, y E = { Pascal, Ada,
Cobol, Lisp, C++}. En cada uno de los siguientes casos, represente el conjunto dado por
un arreglo de ceros y unos.
a.
b.
c.
d.
7. Sea U = {b, d, e, g, h, k, m, n}, B = {b}, C = {d, g, m, n}, y D = {d, k, n}
a. Represente fB , fC, fD
b. Represente como arreglos binarios
UNIDAD II - LÓGICA
CONECTIVAS
Al realizar razonamientos empleamos sentencias que están conectadas entre sí por conectivas
lingüísticas. La lógica proposicional se ocupa del estudio de las conectivas lingüísticas entre
proposiciones. Una proposición es una sentencia que puede ser verdadera, circunstancia que
indicaremos asociándola el valor de verdad V , o falsa, en cuyo caso le asociaremos el valor de
verdad F . Nuestro principal interés en relación con la lógica proposicional es dejar establecido el
papel que juegan las conectivas lingüísticas y sus conectivos lógicos asociados en relación con los
conceptos de verdad y demostración.
Las conectivas lingüísticas permiten construir proposiciones compuestas a partir de otras más
simples. Así, si los símbolos p y q representan proposiciones genéricas, las conectivas lingüísticas
más empleadas son las que aparecen en la siguiente tabla:
NEGACIÓN
El significado de la conectiva lógica negación, reside en que la proposición ¬p es verdadera en el

caso de que p sea falsa y recíprocamente que ¬p es falsa cuando p es verdadera. Recogemos el
significado del conectivo ¬ en la siguiente tabla de verdad:
Del mismo modo podemos recoger el significado del resto de las conectivas.
CONJUNCIÓN
La sentencia es verdadera sólo cuando p y q son verdaderas simultáneamente. La tabla de

verdad correspondiente a esta conectiva será, pues:
DISYUNCIÓN
La sentencia , que se lee p ó q; debe entenderse en su acepción más amplia, es decir, p ó q o

ambos; con lo que será verdadera en el caso de que p sea verdadera, q sea verdadera o
ambas sean verdaderas simultáneamente:
IMPLICACIÓN
Para establecer el significado de la sentencia , que se lee si p entonces q o también p implica

q; debemos tener presente que en lenguaje natural la sentencia p implica q encierra una relación
de causalidad, causalidad que no siempre aparece al utilizar este conectivo en el ámbito formal. Se
pretende que el valor V o F de la sentencia dependa por completo de los valores de verdad
de p y q, con independencia de que exista o no alguna relación de causalidad con sentido entre p y
q. En lenguaje matemático, p implica q quiere decir que, si p es verdadera, necesariamente q es
verdadera, o lo que es lo mismo, que es imposible que q sea falsa y p verdadera: Esto es, si el valor
de verdad de p es V y el de q es F, el valor de verdad de es F; para el resto de posibles
valores de p y q la sentencia será verdadera. Considérese el ejemplo siguiente:
Sea la proposición: Si quemo madera, hay humo en el ambiente, que representaremos por .
Entendemos que esta sentencia es verdadera, puesto que en nuestra experiencia no encontramos
una situación en la que una madera esté ardiendo y no produzca humo. Sin embargo, la sentencia
es verdadera independientemente de que se tenga madera a mano y no haya humo en el ambiente,
de que no estemos quemando madera y haya humo debido a que estamos quemando papel, o
incluso de que efectivamente estemos quemando madera y se esté llenando el ambiente de humo.
En otras palabras sigue siendo verdadera aun en el caso en el que p sea falsa (no estemos
quemando madera) y q sea falsa (no hay humo en el ambiente), p sea falsa y q sea verdadera o
incluso que p sea verdadera y q sea verdadera. El significado de este conectivo lógico queda pues
del siguiente modo:
Es importante destacar que de la tabla anterior se sigue que para demostrar que la sentencia
es verdadera, basta con estudiar el caso en el que p es verdadera, puesto que, si p es falsa, la
sentencia es verdadera.
A las sentencias p y q las denominaremos, respectivamente, antecedente y consecuente de la

proposición
La sentencia es denominada sentencia recíproca de la sentencia ; y la sentencia:

sentencia contrarrecíproca de la sentencia
EQUIVALENCIA
La proposición , que se lee p si y solo si q, o también p equivale a q es verdadera cuando p

y q tienen el mismo valor de verdad, es decir:
ara representar proposiciones emplearemos los símbolos p, q, r... o, lo que es lo mismo,

emplearemos los símbolos p, q, r... como variables proposicionales.
FORMA DE UNA PROPOSICIÓN
Uno de los descubrimientos más sorprendentes con el que nos encontramos al estudiar lógica
consiste en que la validez de una deducción depende exclusivamente de la forma que ésta tenga, y
no del posible significado de las proposiciones que en ella intervienen.
Las proposiciones trabajo o no trabajo y estoy sentado o no estoy sentado tienen la misma forma
: La tabla de verdad de esta forma proposicional es:
Es decir, cualquier proposición que tenga la forma será verdadera independientemente

del valor de verdad que tenga p: La forma de las proposiciones va a estar determinada por la
disposición de los conectivos ; por lo que vamos a introducir la definición
de forma proposicional para estudiar aquellas propiedades que únicamente dependen de la
manera en la que están colocados dichos conectivos lógicos:
Definición: Llamaremos forma proposicional a cualquier expresión formada por:
a) variables proposicionales tales como p; q, r;…
b) los conectivos lógicos
c) los paréntesis (,)
Y construida utilizando las siguientes reglas:
1. Cualquier variable proposicional es una forma proposicional
2. Si A y B son formas proposicionales, entonces también lo son
En la práctica se suelen suprimir los paréntesis en aquellos casos en los que al hacerlo no se
produce ambigüedad. Señalar también que, como veremos luego, la regla 2 puede ser simplificada
prescindiendo de algunos de los conectivos.
Ejemplo: La expresión
No es una forma proposicional (por ejemplo, porque comienza por un conectivo binario )
mientras que la expresión
Sí lo es porque sigue las reglas de su construcción.
Obsérvese que última forma proposicional puede ser representada sin ambigüedad suprimiendo
paréntesis por
Cada forma proposicional tiene asociada una tabla de verdad, que recoge los distintos valores de
verdad de la forma al asignar valores V y F a las distintas variables involucradas. La tabla de
verdad asociada a una forma proposicional se puede construir sistemáticamente a partir del
procedimiento empleado para construir dicha forma proposicional:
Ejemplo: Construcción de la tabla de verdad de la forma proposicional
Lo primero es determinar los pasos seguidos en su construcción. Obsérvese que según las reglas
de construcción de formas proposicionales siempre se tiene un último conectivo que va separando
la parte de la derecha y la de la izquierda que son proposiciones más simples (con menos
conectivos):
En segundo lugar, se construye la primera fila de la tabla teniendo en cuenta dichos pasos:
En tercer lugar, establecemos todas las posibles situaciones de verdad o falsedad de las primeras
variables del enunciado que intervienen:
Finalmente se van rellenando el resto de las columnas teniendo en cuenta por una parte el
significado de los conectivos lógicos y por otra, que cada vez que aparece una
nueva variable proposicional es preciso comparar las situaciones de verdad o falsedad obtenidas
con los dos posibles valores de verdad de la nueva variable proposicional:
EJERCICIOS
Construir las tablas de verdad de las siguientes formas proposicionales:
1.
2.
3.
4.
5.
TAUTOLOGÍAS Y RAZONAMIENTOS VÁLIDOS
Definición. Una forma proposicional es una tautología si toma el valor V cualquiera que sea la
forma en que asignemos los valores V ó F a las variables proposicionales que en ella intervienen.
Una forma proposicional es una contradicción si toma el valor F cualquiera que sea la forma en
que asignemos los valores V ó F a las variables proposicionales que en ella intervienen.
Ejemplo. Es una tautología según se sigue de su tabla de verdad:
EJERCICIOS
Probar que las siguientes formas proposicionales son tautologías:
REGLAS DE INFERENCIA
Los argumentos basados en tautologías representan métodos de razonamiento universalmente

correctos. Su validez depende solamente de la forma de las proposiciones que intervienen y no de
los valores de verdad de las variables que contienen. A esos argumentos se les llama reglas de
inferencia. Las reglas de inferencia permiten relacionar dos o más tautologías o hipótesis en una
demostración. En una demostración no solamente hay tautologías e hipótesis, también existen
reglas de inferencia que permiten obtener nuevas líneas válidas, a continuación, se cita una lista
de las principales reglas de inferencia que se pueden aplicar en una demostración.
MODUS PONENDO PONENS (PP)
“Si llueve, entonces las calles se mojan” (premisa)

p “Llueve” (premisa)
q “Luego, las calles se mojan” (conclusión)
El condicional o implicación es aquella operación que establece entre dos enunciados una relación
de causa-efecto. La regla ‘ponendo ponens ’ significa, “afirmando afirmo ” y en un condicional
establece, que si el antecedente (primer término, en este caso p) se afirma, necesariamente se
afirma el consecuente (segundo término, en este caso q).
MODUS TOLLENDO TOLLENS (TT)
‘Tollendo tollens’ significa “negando, niego”, y se refiere a una propiedad inversa de los
condicionales, a los que nos referíamos en primer lugar.
“Si llueve, entonces las calles se mojan” (premisa)

“Las calles no se mojan” (premisa)
“Luego, no llueve” (conclusión)
Si de un condicional, aparece como premisa el consecuente negado (el efecto), eso nos conduce a
negar el antecedente (la causa), puesto que, si un efecto no se da, su causa no ha podido darse.
Esto nos permite formular una regla combinada de las ambas anteriores, consecuencia ambas de
una misma propiedad de la implicación; la regla ponendo ponens sólo nos permite afirmar si está
afirmado el antecedente (el primer término de la implicación), y la regla tollendo tollens sólo nos
permite negar a partir del consecuente (segundo término de la implicación); ambas consecuencias
se derivan de que la implicación es una flecha que apunta en un único sentido, lo que hace que sólo
se pueda afirmar a partir del antecedente y negar sólo a partir del consecuente.
DOBLE NEGACIÓN (DN)
El esquema representa, “p doblemente negada equivale a p”. Siguiendo el esquema de una

inferencia por pasos, la representaríamos así:
¬¬p “No ocurre que Ana no es una estudiante”

p “Ana es una estudiante”
La regla ‘doble negación’, simplemente establece que, si un enunciado está doblemente negado,
equivaldría al enunciado afirmado.
ADJUNCIÓN Y SIMPLIFICACIÓN
Adjunción (A): Si disponemos de dos enunciados afirmados como dos premisas separadas,
mediante la adjunción, podemos unirlos en una sola premisa utilizando el operador (conjunción).
p “Juan es cocinero”
q “Pedro es policía ”
“Juan es cocinero y Pedro es policía”
Simplificación (S): obviamente, es la operación inversa. Si disponemos de un enunciado formado

por dos miembros unidos por una conjunción, podemos hacer de los dos miembros dos
enunciados afirmados por separado.
“Tengo una manzana y tengo una pera”

p “Tengo una manzana”
q “Tengo una pera”
MODUS TOLLENDO PONENS (TP)
La disyunción, que se simboliza con el operador , representa una elección entre dos enunciados.
Ahora bien, en esa elección, forma parte de las posibilidades escoger ambos enunciados, es decir,
la verdad de ambos enunciados no es incompatible, si bien, ambos no pueden ser falsos.
A partir de lo anterior, se deduce la siguiente regla, denominada tollendo ponens (negando

afirmo): si uno de los miembros de una disyunción es negado, el otro miembro queda
automáticamente afirmado, ya que uno de los términos de la elección ha sido descartado.
“He ido al cine o me he ido de compras”

“No he ido de compras”
p “Por tanto, he ido al cine”
LEY DE LA ADICIÓN (LA)
Dado un enunciado cualquiera, es posible expresarlo como una elección (disyunción) acompañado
por cualquier otro enunciado.
a “He comprado manzanas”

b “He comprado peras”
“He comprado manzanas o he comprado peras”
SILOGISMO HIPOTÉTICO (SH)
Dados dos implicaciones, de las cuales, el antecedente de la una sea el consecuente de la otra (el
mismo enunciado), podemos construir una nueva implicación cuyo antecedente sea el de aquella
implicación cuya consecuencia sea el antecedente de la otra implicación, y cuyo consecuente sea el
de ésta última, cuyo antecedente era consecuencia del primero.
Expresado de otro modo, si una causa se sigue una consecuencia, y esta consecuencia es a su vez
causa de una segunda consecuencia, se puede decir que esa primera causa es causa de esa segunda
consecuencia, del mismo modo que, si una bola de billar roja golpea a otra bola blanca que a su vez
golpea a una bola negra, la bola roja es causa del movimiento de la bola negra. Expresado en forma
de inferencia lógica:
“Si la bola roja golpea a la bola blanca, la bola blanca se mueve”

“Si la bola blanca golpea a la bola negra, la bola negra se mueve”
“Si la bola roja golpea a la bola blanca, la bola negra se mueve”
SILOGISMO DISYUNTIVO (DS)
Dadas tres premisas, dos de ellas implicaciones, y la tercera una disyunción cuyos miembros sean
los antecedentes de los condicionales, podemos concluir en una nueva premisa en forma de
disyunción, cuyos miembros serían los consecuentes de las dos implicaciones. Lógicamente, si
planteamos una elección entre dos causas, podemos plantear una elección igualmente entre sus
dos posibles efectos, que es el sentido de esta regla.
“Si llueve, entonces las calles se mojan”

“Si la tierra tiembla, los edificios se caen”
“Llueve o la tierra tiembla”
“Las calles se mojan o los edificios se caen”
SIMPLIFICACIÓN DISYUNTIVA (SD)
Si disponemos de dos premisas que corresponden a dos implicaciones con el mismo consecuente,
y sus antecedentes se corresponden con los dos miembros de una disyunción, podemos concluir
con el consecuente de ambas implicaciones.
“Helado de fresa o helado de vainilla”

“Si tomas helado de fresa, entonces repites”
“Si tomas helado de vainilla, entonces repites”
r Luego, repites
LEY CONMUTATIVA
Esta ley, no es válida para la implicación, pero sí para conjunción y para la disyunción. Una
conjunción es afirmar que se dan dos cosas a la vez, de modo que el orden de sus elementos no
cambia este hecho. Igualmente, una disyunción es presentar una elección entre dos cosas, sin
importar en qué orden se presente esta elección. Así pues,
“«p y q» equivale a «q y p»”

“«p ó q» equivale a «q ó p»”
LEYES DE MORGAN (DM)
Esta ley permite transformar una disyunción en una conjunción, y viceversa, es decir, una
conjunción en una disyunción. Cuando se pasa de una a otra, se cambian los valores de afirmación
y negación de los términos de la disyunción/conjunción, así como de la propia operación en
conjunto, como podemos observar aquí:
Ejemplos:
REGLA DEL MODUS PONENDO PONENS
Es una regla de inferencia que permite demostrar q a partir de yp
PREMISA 1) Si Pedro está en el partido de Fútbol, entonces Pedro está en el

estadio.
PREMISA 2) Pedro está en el partido de Fútbol.
CONCLUSIÓN: Pedro Está en el estadio.
Simbólicamente tenemos lo siguiente:
p: Pedro está en el partido de fútbol
q: Pedro está en el estadio
Entonces:
PREMISA 1)
PREMISA 2)
CONCLUSIÓN:
Esta regla permite pasar de dos premisas a la conclusión, se dice que la conclusión es una
consecuencia lógica de las premisas, es decir siempre que las premisas son ciertas, la conclusión es
también verdadera.
Cuando el MODUS PONENDO PONENS o cualquier otra regla se aplica para sacar una conclusión
de dos o más proposiciones, el orden de las proposiciones es indiferente.
La abreviatura para esta regla es MP.
DOBLE NEGACIÓN.
Es una regla que permite pasar de una premisa única a la conclusión. Un ejemplo simple es el de
una negación de la negación que se denomina << Doble negación >>.
Sea la proposición:
No ocurre que Ana no es un estudiante.
De donde se puede sacar la conclusión: Ana es estudiante.
La regla también actúa en sentido contrario. Por ejemplo: de la proposición se puede concluir la
negación de su negación:
Juan toma el autobús para ir a la escuela.
No ocurre que Juan no toma el autobús para ir a la escuela
La abreviatura para esta regla es DN .
MODUS TOLLENDO TOLLENS
La regla de Inferencia que se aplica también a las proposiciones condicionales, pero en este caso,
negando (tollendo) el consecuente, se puede negar (tollens) el antecedente de la condicional.
La deducción siguiente es un ejemplo del uso de esta regla:
PREMISA 1) Si tiene luz propia, entonces el astro es una estrella .

PREMISA 2) El astro no es una estrella.
CONCLUSIÓN: Por lo tanto, no tiene luz propia.
Simbolizando:
p : Tiene luz propia

q : El astro es una estrella.
PREMISA 1)
PREMISA 2)
CONCLUSIÓN:
Cuando se trata de proposiciones moleculares puede usarse el paréntesis para mayor claridad. La
abreviatura para esta regla es TT .
Regla de ADJUNCION Y SIMPLIFICACIÓN.
Se suponen dadas dos proposiciones como premisas. La primera es
Jorge es adulto
La segunda es:
María es adolescente.
Si ambas proposiciones son verdaderas, entonces se podrían juntar en una proposición molecular
utilizando el término de enlace « y » y se tendría una proposición verdadera que se leería:
Jorge es adulto y María es adolescente.
La regla que permite pasar de las dos premisas a la conclusión se denomina regla de ADJUNCION.
La abreviatura para esta regla es A.
De manera simbólica se puede ilustrar la regla así :
PREMISA 1)
PREMISA 2)
CONCLUSIÓN 1)
CONCLUSIÓN 2)
El orden de las premisas es indiferente.
Ahora veamos la REGLA DE SIMPLIFICACIÓN
Si se tiene una premisa que dice:
El cumpleaños de María es el lunes y el mío es el sábado.
De esta premisa se pueden concluir:

El cumpleaños de María es el lunes.
La otra conclusión:
El mío es el sábado.
Si la premisa es cierta, cada una de las conclusiones es también cierta.
Esta regla se abrevia por S.
En forma simbólica la regla de simplificación es:
De la premisa
Se concluye: p
O se concluye: q
En una demostración no solamente hay tautologías e hipótesis, también existen reglas de
inferencia que permiten obtener nuevas líneas válidas, esta es la parte en donde la mayoría de
alumnos tienen problemas y en donde no sabe que regla aplicar para resolver un determinado
problema.
Nota: Una demostración formal en la lógica se fundamenta y desarrolla estrictamente utilizando

únicamente las reglas de validez enunciadas en el numeral anterior). Con base en ellas puede de-
mostrarse que las implicaciones implícitas en cada una de las reglas de inferencia son teoremas.
Como un objetivo práctico a lograr es abreviar los procesos demostrativos, se introducen las
reglas de inferencia; éstas, conjuntamente con las reglas de validez permiten ampliar y facilitar la
obtención de los resultados válidos en esta teoría.
EJERCICIOS
En cada uno de los problemas siguientes, tradúzcase a la forma simbólica y empleando las reglas
de inferencia y de validez, establézcase para cada argumento si es o no válido.
1. Si llueve, entonces iré al cine. Llueve. Luego, iré al cine.

2. Si llueve, entonces iré al cine. No llueve. Luego, no iré al cine.
3. Si me caigo de la bicicleta, me golpeo. Estoy golpeado; luego, me caí de la bicicleta.
4. Si voy al colegio pasaré por la biblioteca. Si paso por la biblioteca consultaré el diccionario de
sinónimos. Voy al colegio; luego, consulté el diccionario de sinónimos.
5. Si los precios son bajos, entonces los salarios son bajos. Los precios son bajos o no hay
control de precios. Si no hay control de precios, entonces hay inflación. No hay inflación; por
tanto, los salarios son bajos.
6. La lógica es fácil o les gusta a los estudiantes. Si las matemáticas son difíciles entonces la
lógica no es fácil. Por tanto, si a los estudiantes no les gusta la lógica, las matemáticas no son
difíciles.
7. Si trabajo, entonces no estudio. Estudio o repruebo el curso de matemáticas. Aprobé el curso
de matemáticas; luego, trabajo.
8. Si el entero 35 244 es divisible entre 396, entonces el entero 35 244 es divisible entre 66. Si
el entero 35 244 es divisible entre 66, entonces el entero 35 244 es divisible entre 3.
INDUCCIÓN MATEMÁTICA
G. Peano (1858 –1932) propuso cinco propiedades fundamentales que caracterizan a los números
naturales, Axiomas de Peano. Una de ellas conocida como el Principio de Inducción Matemática es
actualmente una herramienta de uso práctico y teórico principalmente para matemáticos y
personas que trabajan en Ciencias Computacionales.
El principio lo enunciaremos para los enteros positivos N+, pero bien se puede ampliar a los
números naturales o a cualquier subconjunto de los enteros mayores o iguales a un entero fijo.
PRINCIPIO DE INDUCCIÓN MATEMÁTICA
Si S en un conjunto de enteros positivos tal que
entonces S contiene todos los enteros positivos.
En un principio de Inducción Matemática son muy importantes los nombres asociados y en la

literatura técnica, como es costumbre, no se presenta con detalle los pasos, por lo que resulta
indispensable conocer la nomenclatura.
Nomenclatura de Inducción Matemática.
(B) se llama Caso Base o caso inicial
(I) se llama Paso de Inducción
se llama Hipótesis de Inducción
Y como ya se mencionó todo junto se llama Principio de Inducción Matemática.
Es importante que el alumno comprenda y memorice cada uno de estos conceptos y su

participación directa en la propiedad.
Esencialmente lo que enuncia el principio de inducción matemática es, si logramos establecer que
el primer entero positivo cumple, una propiedad, y si partiendo de que un entero arbitrario
también la cumple, se puede comprobar que el entero siguiente también tiene la propiedad
entonces concluimos que todos los enteros positivos tienen la propiedad indicada.
Por lo que otra forma de enunciar el Principio de Inducción Matemática es:
Si F(n) es una proposición abierta que involucra enteros y se tiene:

(B) F(1) es verdadera; o sea, se que cumple para n=1
(I) ; Si se cumple para n = k entonces también se cumple para n=k+1.
Concluimos que la proposición es verdadera para todos los enteros positivos.
El Principio de Inducción Matemática se utiliza para demostrar propiedades, formulas, validarlas y

probar que son verdaderas, usualmente en el conjunto de los números enteros positivos. Muchas
propiedades que incluyen la definición de factorial se pueden probar por Inducción Matemática,
como el Teorema del Binomio de Newton, el Triángulo de Pascal y algunas propiedades de
combinatoria que involucran combinaciones y permutaciones. Otra forma de utilizarla es para
proporcionar definiciones y formalizar conceptos.
ALGORITMO. Para demostrar una igualdad F(n) algebraica válida que involucra enteros donde la
parte izquierda es una suma cuyo término n-ésimo es una fórmula de n.
[Fórmula] Escribir la fórmula en función de n, sea F(n).
[Caso Base] Probar la fórmula para n=1, F(1).
[Meta] Escribir la fórmula para n=k+1, F(k+1).
[Paso de Inducción]
[Hipótesis de Inducción] Escribir la fórmula para n=k.
[Llegar a la Meta] Sumar a ambos lados el último término de la parte izquierda de la [Meta], o sea
la igualdad para n=k+1.
Aplicar propiedades algebraicas al lado derecho hasta llegar al lado derecho de la [Meta], o sea la
igualdad para n=k+1.
Nota: Cabe aclarar que la única dificultad se puede presentar en el manejo algebraico de las
expresiones en la segunda parte del Paso de Inducción y que depende muchas veces de la
complejidad de la expresión y de la habilidad algebraica de quien realiza la prueba.
Nota: La meta la marcamos con rojo para indicar que no es un paso válido en la demostración, sino
más bien una guía de a dónde queremos llegar y para tener una mejor idea de lo que estamos
demostrando.
En los ejemplos que se vean se debe considerar expresiones que se puedan resolver con la
preparación de los estudiantes a los que va dirigido.
Ejemplos: Demuestre por inducción matemática, que para todos los valores de:
Solución:
Paso Base: Demostrar que se cumple para n = 1
, la cual es verdadera.
Paso de inducción. Si P(k) es verdadera, entonces también lo será para P(k+1)
Demostrar para k+1
b) Demostrar por inducción que la expresión es divisible por
Proceso:
Para n=1:
es divisible por . Se verifica.
Sea cierta la proposición para n=k:
Veamos entonces que también será cierta para n=k+1:
En efecto:
El primer sumando es divisible por a+1 por hipótesis, y el segundo lo es porque contiene a (a+1)
como factor.
Por consiguiente, es divisible por (a+1), para todo n>0
d)
e)
EJERCICIOS:
Demuestre por inducción matemática en cada caso:
1.
2.
3.
4.
5.
6.
7.
8.
UNIDAD III – CONTEO
COMBINATORIA
Breve reseña histórica
El surgimiento y desarrollo de la combinatoria ha sido paralelo al desarrollo de otras ramas de las

matemáticas, tales como el álgebra, teoría de los números, y probabilidad. Desde tiempos muy
remotos ha habido problemas de combinatoria que han llamado la atención de los matemáticos.
por ejemplo, el problema de los cuadrados mágicos que son arreglos de números con la propiedad
de que la suma de los elementos de cualquier columna, renglón o diagonal es el mismo número,
aparece en un viejo libro chino fechado 2200 a. C. Los cuadrados mágicos de orden 3 fueron
estudiados con fines místicos. Los coeficientes binomiales, que son los coeficientes enteros de la
expansión de (a + b) fueron conocidos en el siglo XII. El triángulo de Pascal que es un arreglo
triangular de los coeficientes binomiales fue desarrollado en el siglo XIII.
Se puede considerar que en el Occidente la combinatoria surge en el siglo XVII con los trabajos de
Blaise Pascal y de Pierre Fermat sobre la teoría de juegos de azar. Estos trabajos, que formaron los
fundamentos de la teoría de la probabilidad, contenían asimismo los principios para determinar el
número de combinaciones de elementos de un conjunto finito, y así se estableció la tradicional
conexión entre combinatoria y probabilidad.
El término "combinatoria" tal y como lo usamos actualmente fue introducido por Wilhem Leibniz
en su Dissertatio de Arte Combinatoria. De gran importancia para la consolidación de la
combinatoria fue el artículo de Ars Conjectandi (el arte de conjeturar por J. Bernoulli; este trabajo
estaba dedicado a establecer las nociones básicas de probabilidad. Para esto fue necesario
introducir también un buen número de nociones básicas de combinatoria pues se usaron
fuertemente como aplicaciones al cálculo de probabilidades. Se puede decir que con los trabajos
de Leibniz y Bernoulli se inicia el establecimiento de la combinatoria como una nueva e
independiente rama de las matemáticas.
El matemático suizo Leonard Euler fue quien desarrolló a principios del siglo XVIII una auténtica
escuela de matemática combinatoria. En sus artículos sobre la partición y descomposición de en-
teros positivos en sumandos, estableció las bases de uno de los métodos fundamentales para el
cálculo de configuraciones combinatorias, que es el método de las funciones generadoras.
También se le considera el padre de la teoría de gráficas por el planteamiento y solución del
problema de los "Puentes de Königsberg" usando por primera vez conceptos y métodos de teoría
de gráficas. Los primeros problemas de teoría de gráficas surgieron de la búsqueda de solución a
algunos problemas cotidianos y también en el planteamiento de algunos acertijos matemáticos
tales como el problema de los Puentes de Königsberg, el arreglo de reinas en un tablero de ajedrez
con alguna restricción, problemas de transporte, el problema del agente viajero, etcétera.
El problema de los cuatro colores formulado a mediados del siglo XIX (cuatro colores son
suficientes para colorear las regiones de un mapa de tal manera que regiones con frontera tengan
asignados distinto color) pasó de ser un mero acertijo matemático a ser fuente de importantes
problemas y resultados en teoría de gráficas de interés tanto teórico como en aplicaciones. Este ha
sido uno de los problemas teóricos más desafiantes en la historia de la combinatoria debido a la
simplicidad de su planteamiento.
En Inglaterra a finales de siglo XIX Arthur Cayley (motivado por el problema de calcular el número
de isómeros de hidrocarburos saturados) hizo importantes contribuciones a la teoría de
enumeración de gráficas. Por este tiempo el matemático George Boole usó métodos de
combinatoria en conexión con el desarrollo de la lógica simbólica y con las ideas y métodos que
Henri Poincaré desarrolló en relación con problemas de topología. Uno de los factores más
importantes que han contribuido al gran desarrollo que ha tenido la combinatoria desde 1920 es
la teoría de gráficas, la importancia de esta disciplina estriba en el hecho de que las gráficas
pueden servir como modelos abstractos para modelar una gran variedad de relaciones entre
objetos de un conjunto. Sus aplicaciones se extienden a campos tan diversos como la investigación
de operaciones, química, mecánica estadística, física teórica y problemas socio-económicos. La
teoría de redes de transporte se puede ver como un capítulo de la teoría de las gráficas.
INTRODUCCIÓN A LA COMBINATORIA
A menudo se presenta la necesidad de calcular el número de maneras distintas en que un suceso

se presenta o puede ser realizado. Otras veces es importante determinar la probabilidad de
ocurrencia de un evento específico. En ambos casos se apela al sentido común, o se establecen
métodos que permitan sistematizar tales cálculos. Con frecuencia el sentido común ayuda a
entender por qué se eligió un procedimiento dado, mientras que la formalización del cálculo las
vías para encontrar las soluciones apropiadas.
Iniciaremos nuestro estudio de teoría combinatoria enunciando los principios aditivo y

multiplicativo de conteo.
Principio aditivo de conteo: Sean A y B dos sucesos que no pueden ocurrir simultáneamente. Si A
ocurre de a maneras distintas y B ocurre de b maneras distintas, el número de maneras en el cual
puede ocurrir A o B es A +B
Principio multiplicativo de conteo: Si un suceso puede ocurrir en a maneras e, independiente-

mente, un segundo suceso puede ocurrir en b maneras, entonces el número de maneras en que
ambos, A y B, pueden ocurrir AB.
A este principio también se le denomina principio fundamental de conteo.
Ejemplo: Se tienen 6 banderas de señalización, dos rojas, dos verdes y dos azules. ¿Cuántas seña-
les distintas pueden hacerse con una o dos banderas a la vez?
Solución: Si denotamos las banderas rojas, verdes y azules por R, V y A, respectivamente, vemos
que con una bandera a la vez se pueden hacer 3 señales distintas:
R,V,A
Con dos banderas a la vez se puede hacer las siguientes señales (sacando, por ejemplo, una
primera y después la otra) es decir
RR, RV. RA, VR, VV, VA, AR, AV, AA
Entonces, si se utilizan dos banderas, se pueden hacer 9 señales distintas. Luego, con una o dos
banderas se podrán realizar 3+9= 12 señales diferentes. Observa que, como se establece en la
definición, se trata de dos sucesos A y B descritos como:
A: Se hacen señales con una sola bandera
B: Se hacen señales con dos banderas.
Y que ambos no pueden ocurrir simultáneamente, ya que si se decide hacer señales con una
bandera se descarta la segunda alternativa y viceversa
Ejemplo: En una liga de 28 equipos. ¿Cuántas quinielas de futbol distintas se pueden hacer?
Tenemos en cuenta que en cada partido puede haber 3 resultados(Gana A, Empate, Gana B): 1, x,
2, que hay 14 partidos y que los resultados de cada uno son independientes de los demás, por
tanto, tendremos
Ejemplo: ¿Cuántos resultados distintos puede haber en un sorteo de la lotería en el que se deben
elegir 6 números de 49 (del 1 al 49) sin repetición de número?
En una bolsa tenemos 49 bolas numeradas del 1 al 49. El primer número lo escojo entre 49
posibles números, el segundo número lo escojo entre 48 (pues las bolas, una vez extraídas no se
devuelven a la bolsa), el tercero entre 47, y así sucesivamente, por lo tanto, en principio habría
49*48*47*46*45*44= 10.068.347.520
Esta sería la solución si el orden de extracción de las bolas, se tuviese en cuenta, pero no es así. El
número que hemos sacado en la primera extracción podría haber salido en la segunda, tercera,
cuarta, quinta o sexta extracción (en total 6), por lo tanto, habrá que dividir por 6. El número que
hemos sacado en la segunda extracción, podría haber salido en la tercera, cuarta, quinta o sexta
extracción, (en total 5), habrá que dividir entre 5 y así seguiríamos razonando hasta la última ex-
tracción.
Por ello habrá que dividir por 6*5*4*3*2*1 el número anterior para obtener la solución.
10.068.347.520/720=13.983.816
Ejemplo: ¿Cuántas quinielas distintas se pueden hacer si creemos que el resultado de 4 partidos
será un 1, el de 5 partidos puede ser un 1 o una x, y los 6 partidos restantes puede darse
cualquiera de los tres signos?
Los cuatro resultados 'fijos' los podemos elegir entre un signo, los 5 'dobles' entre dos y los 6 'tri-
ples' entre 3, por lo tanto, la solución sería:
Hasta ahora, los ejemplos realizados los hemos realizado mediante conteo, nuestro objetivo es
formalizar y obtener expresiones matemáticas que nos den los resultados buscados.
PERMUTACIONES
PERMUTACIONES SIN REPETICIÓN:

Las permutaciones sin repetición de n elementos se definen como las distintas formas de ordenar
todos esos elementos distintos, por lo que la única diferencia entre ellas es el orden de colocación
de sus elementos.
El número de estas permutaciones será:
PERMUTACIONES CON REPETICIÓN:

Llamamos permutaciones con repetición de n elementos tomados de a en a , de b en b , de c en c ,
etc., cuando en los n elementos existen elementos repetidos (un elemento aparece a veces, otro b
veces, otro c veces, etc.) verificándose que a+b+c+...=n.
El número de estas permutaciones será:
Teniendo en cuenta que
Ejemplos
a) ¿Cuántos números de 5 cifras distintas se pueden formar con los dígitos 1,2,3,4,5?
b) ¿Cuántos números de 4 cifras se pueden formar con los dígitos 0,1,2,3?

Hemos restado P3 para descontar los números que empiezan por cero, ya que estos no son de
cuatro cifras.
c) ¿Cuántos números de 6 cifras se pueden formar si en ellos siempre hay 1’s, 2 ’s y 3 ’s?
VARIACIONES
Definición: Las variaciones sin repetición de n elementos tomados de r en r se definen como las
distintas agrupaciones formadas con r elementos distintos, eligiéndolos de entre los n elementos
de que disponemos, considerando una variación distinta a otra tanto si difieren en algún elemento
como si están situados en distinto orden.
El número de variaciones que se pueden construir se puede calcular mediante la fórmula
Definición: Las variaciones con repetición de n elementos tomados de r en r se definen como las
distintas agrupaciones formadas con r elementos que pueden repetirse, eligiéndolos de entre los n
elementos de que disponemos, considerando una variación distinta a otra tanto si difieren en
algún elemento como si están situados en distinto orden.
El número de variaciones que se pueden construir se puede calcular mediante la fórmula:
Ejemplos
a) ¿Cuántos números de tres cifras distintas se pueden formar con los dígitos 1,2,3,….,9?
Se trata de variaciones sin repetición, ya que las cifras de cada número deben ser distintas.
b) Con las letras del alfabeto español (27 letras) a)¿Cuántas palabras (con o sin sentido) de 6
letras distintas pueden formarse?- b)¿Cuántas empiezan por vocal?
Se trata de variaciones con repetición

a.
b.
COMBINACIONES
Definición: Las combinaciones sin repetición de n elementos tomados de r en r se definen como las
distintas agrupaciones formadas con r elementos distintos, eligiéndolos de entre los n elementos
de que disponemos, considerando una variación distinta a otra sólo si difieren en algún elemento,
(No influye el orden de colocación de sus elementos).
El número de combinaciones que se pueden construir se puede calcular mediante la fórmula:
Definición: Las combinaciones con repetición de n elementos tomados de r en r se definen como

las distintas agrupaciones formadas con r elementos que pueden repetirse, eligiéndolos de entre
los n elementos de que disponemos, considerando una variación distinta a otra sólo si difieren en
algún elemento, (No influye el orden de colocación de sus elementos).
El número de combinaciones que se pueden construir se puede calcular mediante la fórmula:
Ejemplos
a) Como respuesta a un anuncio de trabajo se presentan 12 personas para cubrir tres plazas de
administrativo ¿Cuántos grupos diferentes de personas se pueden seleccionar?
Debemos elegir grupos de 3 de entre los 12 , no influye el orden
b) ¿Cuántos triángulos distintos se pueden formar con 8 puntos en el plano si tres de ellos nunca
están alineados?
Para que dos triángulos sean distintos se tienen que diferenciar al menos en un vértice y el orden
en que tomamos los vértices no influye
c) ¿Cuántos conjuntos de tres letras existen elegidas entre a, b, c, d, e, f, g si en cada conjunto puede
haber más de una letra igual?
Tenemos en cuenta que el conjunto a, b, c coincide con el conjunto b, c, a y que los elementos se
pueden repetir, es decir a, a, b es un conjunto de tres letras, luego
¿CÓMO LAS DIFERENCIAMOS?

EJERCICIOS
1. Supongamos que hay ocho diferentes lugares de capacitación administrativa para asignar a
ocho empleados en el programa preliminar de capacitación administrativa de una empresa. ¿De
cuántas maneras diferentes pueden ser asignados los ocho individuos a los ocho lugares distintos?
2. En referencia a la situación descrita en el ejercicio 1, supongamos que sólo se dispone de seis

diferentes lugares para los ocho candidatos. ¿De cuántas maneras diferentes pueden asignar- se
los seis lugares distintos a seis de los ocho individuos?
3. En referencia a la situación descrita en el ejercicio 2, supongamos que seis de los lugares

disponibles pueden considerarse comparables y en realidad iguales para efectos prácticos. ¿De
cuántas maneras pueden elegirse seis de los ocho candidatos para ocupar los seis lugares?
4. Un grupo de proyecto de dos ingenieros y tres técnicos debe formarse a partir de un grupo
departamental que incluye a cinco ingenieros y nueve técnicos. ¿Cuántos diferentes grupos de
proyecto pueden formarse con los catorce empleados disponibles?
5. Una clave de acceso a un banco consta de dos letras de alfabeto seguidas por dos dígitos.
¿Cuántas claves diferentes hay?
6. ¿Cuántas permutaciones hay de cada uno de los siguientes conjuntos, sin permitir repetición?
a. {r, s, t, u} r=2
b. {1, 2, 3, 4, 5} r = 3
c. {a, b, 1, 2, 3, c} r = 3
7. Para cada conjunto A, encuentre el número de permutaciones de A tomando r elementos a la

vez, pudiendo repetir elementos.
a. A = {1, 2, 3, 4, 5, 6, 7}, r = 3
b. A = {a, b, c, d, e, f}, r = 2
c. A = {x/x es un número entero y x <16}, r = 4
8. ¿De cuántas maneras 6 hombres y 6 mujeres pueden sentarse en línea si:
a. Cualquier persona puede sentarse en seguida de cualquier otra.
b. Los hombres y las mujeres deben ocupar asientos alternos.
9. Encuentre el número de permutaciones de la palabra BOUGHT con y sin repetición de términos.
10. ¿De cuántas maneras puede seleccionarse un comité de tres miembros de facultad y dos de
estudiantes, tomándolos de siete miembros de facultad y ocho estudiantes?
11. ¿De cuántas formas se puede elegir un comité de 3 personas de un grupo de 20? ¿Y de cuán- tas
si uno debe ser el presidente, otro el vicepresidente y otro el secretario?
12. ¿Cuántos números distintos de 5 cifras se pueden formar con las cifras 1,2,3,5,7,8,9?
13. En una reunión hay tres chicas y siete chicos ¿Cuántos grupos de 5 personas pueden formar-
se? ¿Cuántos si en cada grupo debe haber 2 y solo dos chicas?
14. ¿Cuántos números de cuatro cifras pueden formarse con dos cifras pares (no entra el cero) y
dos impares?
UNIDAD IV - RELACIONES Y DÍGRAFOS
RELACIONES
Una relación R de A en B es cualquier subconjunto de A x B. Si , entonces se dice que “x

está relacionado con y” y se escribe x R y o R(x, y).
La notación infija x R y es muy común en matemática, por ejemplo, para decir que 3 y 5 están
vinculados por la relación “menor que” se escribe 3 < 5. La notación prefija R(x, y ) a veces se usa
sin paréntesis, como R xy .
Si A = B entonces en lugar de “relación de A en A” simplemente se dice “relación en A”.
El conjunto de todas las relaciones de A en B es el conjunto P(A x B ).
Ejemplo 1. Sea F = {Ana, Berta, Carlos, Diana, Ernesto} una familia en la cual Ana es la madre de
Berta, Berta es la madre de Carlos y Diana, y Diana es la madre de Ernesto.
Entonces M = {(Ana, Berta), (Berta, Carlos), (Berta, Diana), (Diana, Ernesto)} es una relación de F
en F que corresponde al concepto intuitivo de la relación “es madre de”.
Ejemplo 2. Sean A y B conjuntos de números reales. Se define la siguiente relación R (de igualdad)
de A a B:
a R b si y solo sí a = b
Ejemplo 3. Sea A = {1, 2, 3, 4, 5}
Defina la siguiente relación R (menor que) en A:
Entonces:
R = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}
Ejemplo 4. el conjunto de todos los enteros positivos. Muestre un ejemplo y un

contraejemplo de la siguiente relación R en A:
pero
Ejemplo 5. Una línea aérea da servicio a cinco ciudades c1, c2, c 3, c4 y c5. La tabla muestra el costo
en dólares del viaje de ci a cj. En consecuencia, el viaje de c1 a c3 es de $100, mientras que el costo
del viaje de c4 a c2 es de $200.
A
C1 C2 C3 C4 C5
De
C1 140 100 150 200
C2 190 200 160 220
C3 110 180 190 250
C4 190 200 120 150
C5 200 100 200 150
Defina la siguiente relación entre el conjunto de ciudades A: ci R cj si y sólo sí el costo de ir de ci a cj
es menor o igual a $180. Determine R.
R = {(c1,c2),(c1 ,c3),(c1,c4),(c2,c4),(c3,c1),(c3 ,c2),(c4 ,c3),(c4 ,c5),(c5,c2),(c5,c4)}
CONJUNTOS QUE SURGEN DE LAS RELACIONES
Sea , una relación de A a B. Se va a definir ahora varios conjuntos importantes y útiles

relacionados con R.
El dominio de R, denotado Dom(R), es el conjunto de todos los elementos de A que están

relacionados con algún elemento de B. En otras palabras, Dom(R), un subconjunto de A, es el
conjunto de todos los primeros elementos de los pares que forman R. De modo similar, se define el
rango de R, designado por Ran(R), como el conjunto de todos los elementos de B que están
relacionados con algún elemento de A.
Los elementos de A que no están en Dom(R) no están involucrados en la relación R de manera

alguna. Esto es cierto también para los elementos de B que no están en el rango de R.
Ejemplo 6. Si R es la relación definida en A = {1, 2, 3} y B = {r, s} t.q. su relación es
R = {(1,r),(2,s),(3,r)}
Entonces el Dom(R) = A y Ran(R) = B.
Ejemplo 7. Sea A = {1, 2, 3, 4, 5} Definida por la siguiente relación R (menor que) en A:

.
Entonces el Dom(R) = {1, 2, 3, 4} y Ran(R) {2, 3, 4, 5}
Teorema 1. Sea R la relación de A a B, y sean A1 y A2 subconjuntos de A. Entonces:

Teorema 2. Sean R y S relaciones de A a B. Si R(a) = S(a) para todas las a de A, entonces R = S.
LA MATRIZ DE UNA RELACIÓN
Es posible representar una relación entre dos conjuntos finitos como una matriz de la siguiente
manera. Si A = {a 1, a 2, … , a m } y B = {b1, b 2, … , b n} son conjuntos finitos que contienen m y n
elementos respectivamente, y R es una relación de A a B, se representa R por la matriz m x n MR
[mij ], la cual se define por
La matriz MR se llama matriz de R. A menudo MR proporciona una manera fácil de verificar si R

tiene una propiedad dada.
Ejemplo 8. Sea R la relación definida en A = {1, 2, 3} y B = {r, s} t.q. su relación es
R = {(1,r),(2,s),(3,r)}
Entonces la matriz de R es:
A la inversa, dados los conjuntos A y B con , una matriz m x n cuyas entradas

son ceros y unos, determina una relación.
Ejemplo 9. Considere la matriz
Como M es 3 x 4, entonces A={a1, a2,a3} y B={b1,b2,b3,b4}
Entonces .
En consecuencia,
DÍGRAFOS
Si A es un conjunto finito y R es una aplicación sobre A, también se puede representar R

gráficamente como sigue. Se traza un círculo para cada elemento de A y se marca el círculo con el
elemento correspondiente de A. A estos círculos se los llama vértices. Se traza a continuación una
flecha, a la flecha se le llama lado o arco, del vértice ai al vértice aj si y solamente sí ai R aj. La
representación gráfica resultante de R se llama gráfica dirigida o dígrafo de R.
Ejemplo 10. Sean
A = {1, 2, 3, 4}
B = {(1,1), (1,2), (2,1), (2,2),(2,3),(2,4),(3,4),(4,1)}
Entonces el dígrafo de R es el siguiente:
Ejemplo 11. Encuentre la relación determinada por el siguiente dígrafo.
Un concepto importante para las relaciones es el que inspira la

forma visual de los dígrafos. Si R es una relación sobre un conjunto
Ay , entonces el grado interno de a (relativo a R) es el
número . El grado externo de a es el número
.
Esto significa en términos del dígrafo de R, que el grado interno

de un vértice es el número de arcos que terminan en el vértice y el grado externo de un vértice es
el número de arcos que salen del vértice.
Ejemplo 12 . Considere el dígrafo del ejemplo 9. Determinar los grados internos y externos de cada
vértice.
Vértice Grado interno Grado externo

1 3 2
2 2 4
3 1 1
4 2 1
Ejemplo 13. Sea A = {a, b, c, d} y sea R la relación sobre A que tiene la matriz
Construya el dígrafo de R, y haga una tabla de los grados internos y grados externos de todos los
vértices.
Vértice Grado interno Grado externo

a 2 1
b 3 1
c 1 3
d 1 2
Ejemplo 14. Sea A = {1, 4, 5}, y sea R la relación que da el dígrafo siguiente.
Encuentre MR y R.
R = {(1,4), (1,5), (4,1), (4,4), (5,4),(5,5)}

EJERCICIOS:
En los ejercicios 1 al 9, determine el dominio, rango, matriz y cuando A=B, el dígrafo de la
relación R.
1. A={a, b, c, d}, B={1, 2, 3}, R={(a, 1), (a, 2), (b, 1), (c, 2), (d, 1)}
2. A={I, C, D, G, Z}, B={750C, PS60, 450SV, 433S, 525SX, 466V, 486SL}
R={(I, 750C), (D, 466V), (C, 450SV), (G, PS60)}
3. A={1, 2, 3, 4}, B={1, 4, 6, 8, 9}; aRb si y sólo si b = a2.
4. A={1, 2, 3, 4, 8}=B; aRb si y sólo si a=b
5. A={1, 2, 3, 4, 8}=B; aRb si y sólo si a|b
6. A={1, 2, 3, 4, 6}=B; aRb si y sólo si a es múltiplo de b
7. A={1, 2, 3, 4, 5}=B; aRb si y sólo si
8. A={1, 3, 5, 7, 9}, B={2, 4, 6, 8}; aRb si y sólo si b<a
9. A={1, 2, 3, 4, 8}=B; aRb si y sólo si
10. Sea , los enteros positivos, y R la relación definida por aRb si y sólo si existe una k en
de modo que a=bk (k depende de a y b). ¿Cuáles de los siguientes pares ordenados pertenecen
a R?
a. (4, 16) b. (1, 7) c. (8, 2) d. (3, 3) e. (2, 8) f. (2, 32)
En los ejercicios 11 y 12, escriba la relación R definida en A y su dígrafo.
11. Sea A = {1, 2, 3, 4} y
12. Sea A ={a, b, c, d, e} y
En los ejercicios 13 y 14, escriba la relación determinada por el dígrafo y su matriz.

13.
14.
15. Para los dígrafos de los ejercicios 13 y 14 proporcione las tablas de grados internos y externos
para cada vértice.
TRAYECTORIAS EN RELACIONES Y DÍGRAFOS
Supóngase que R es una relación sobre un conjunto A. Una trayectoria de longitud n en R de a a b

es una secuencia finita , que comienza con a y termina con b, tal que:
Debe observarse que una trayectoria de longitud n involucra n+1 elementos de A, aunque no
necesariamente distintos.
Ejemplo. Considere el dígrafo de la siguiente figura.
Entonces:
π1: 1, 2, 5, 4, 3 es una trayectoria de longitud 4 del vértice 1 al

vértice 3.
π2: 1, 2,5,1 es una trayectoria de longitud 3 del vértice 1 al vértice

1.
π3: 2, 2 es una trayectoria de longitud 1 del vértice 2 al vértice 2.

Una trayectoria que inicia y termina en el mismo vértice se llama ciclo. En el ejemplo anterior, π2 y
π3 son ciclos de longitud 3 y 1 respectivamente. Es claro que una trayectoria de longitud 1 se
identifica como un par ordenado (x, y) que pertenece a R.
Se define una relación Rn sobre A como sigue: significa que hay una trayectoria de longitud n
de x a y en R. También puede definirse una relación sobre A , suponiendo que
signifique que hay una trayectoria en R de x a y. La longitud de esa trayectoria dependerá, en
general, de x y y . A la relación se le llama relación de conectividad de R.
Ejemplo: Sea A = {1, 2, 3, 4, 5, 6}. Sea R la relación cuyo dígrafo aparece a continuación.
1 R2 2 puesto que 1 R 2 y 2 R 2
Ejemplo: Sean A = {a, b, c, d, e} y R = {(a, a), (a, b), (b, c), (c, e), (c, d), (d, e)}
Determinar:
El siguiente es el dígrafo de R.
Luego:
(a) a R2 a puesto que a R a y a R a
a R2 b puesto que a R a y a R b
a R2 c puesto que a R b y b R c
b R2 e puesto que b R c y c R e
b R2 d puesto que b R c y c R d
c R2 e puesto que c R d y d R e
(b) Para calcular , se necesitan todos los pares ordenados de vértices para los cuales haya una
trayectoria de cualquier longitud del primer vértice al segundo.
EJERCICIOS:
Para los ejercicios 1 al 8 utilice el dígrafo que aparece a la derecha.
1. a. Haga una lista de todas las trayectorias de longitud 1.
b. Haga una lista de todas las trayectorias de longitud 2,
que inicien en el vértice 2.
c. Haga una lista de todas las trayectorias de longitud 2.
2. a. Haga una lista de todas las trayectorias de longitud 3,
que inicien en el vértice 3.
b. Haga una lista de todas las trayectorias de longitud 3.
3. Encuentre un ciclo que comience en el vértice 2.
5. Trace el dígrafo de R2 .
6. Determine
7. Determine
8. Determine
Para los ejercicios 9 al 19, sea R la relación cuyo dígrafo aparece a la derecha.
9. Haga una lista de todas las trayectorias de longitud 1.
10. Haga una lista de todas las trayectorias de longitud 2 que inicien en el vértice c.
11. Encuentre todas las trayectorias de longitud 2.
12. Haga una lista de todas las trayectorias de longitud 3 que inicien el vértice a.
13. Determine todas las trayectorias de longitud 3.
14. Encuentre un ciclo que comience en el vértice c.
15. Encuentre un ciclo que comience ene vértice d.
16. Dibuje el dígrafo de R2
17. Determine
18. Determine
19. Determine
En los ejercicios 20 al 26, utilice el dígrafo de la figura de la derecha.
20. Determine todas las trayectorias de longitud 3.
22. Encuentre un ciclo que comience ene vértice 7.
23. Dibuje el dígrafo de R2
24. Determine
25. Determine
26. Determine
REPRESENTACIÓN EN COMPUTADORA DE RELACIONES Y DÍGRAFOS
El método directo para almacenar elementos de datos es colocarlos en una lista o

arreglo lineal. Esto equivale a poner elementos de datos consecutivos en lugares de
almacenamiento con numeración consecutiva en la memoria de la computadora. La
siguiente figura ilustra dicho método para cinco elementos.
El problema principal que se tiene con este método es que no se puede insertar
nuevos datos entre los datos existentes sin tener que mover un número que podría
ser muy grande de elementos.
Un método alternativo para representar esa secuencia de datos es por medio de

una lista enlazada, que se muestra esquemáticamente en la
siguiente figura. Se imagina que tales celdas tienen espacio para
dos elementos de información. El primero puede ser de datos
(números o símbolos), y el segundo elemento es un apuntador
(puntero), es decir un número que dice (señala) la localización de
la siguiente celda. En consecuencia, las celdas pueden estar
dispuestas en sucesión, pero los datos no necesariamente están en
sucesión.
En la práctica el concepto de lista enlazada por punteros, se puede

poner a funcionar utilizando dos arreglos enlazados, un arreglo de
datos A y un arreglo de apuntadores P, como se muestra a
continuación. Obsérvese que una vez que se ha tenido acceso a los
datos de la posición A[i], el número de la posición P[i], da o señala,
el índice de A que contiene el siguiente elemento de datos.
Ejemplo:
Considere la relación cuyo dígrafo aparece a continuación
Si se desea almacenar el dígrafo en forma de lista enlazada de manera que el orden lógico coincida
con la numeración de sus lados, se puede usar el siguiente esquema.
INICIO TAIL HEAD NEXT

2 1 3 9
2 3 10
2 1 4
3 5 8
5 4 1
3 4 3
3 6 0
6 1 7
1 6 6
1 2 5
El esquema anterior nos permite seguir el rastro del proceso, sin embargo, el mismo presenta
desventajas importantes. En muchos algoritmos, es eficiente localizar un vértice, y luego comenzar
de inmediato a investigar los lados que comienzan o terminan en ese vértice. En general esto no es
posible con el esquema anterior, por lo que se proporciona una modificación al mismo. Usaremos
un arreglo denominado VERT que tiene una posición para cada vértice en el dígrafo. Para cada
vértice I, se deben arreglar los apuntadores de SIGUE de manera que enlacen todos los lados que
salgan de I, que inicie en el lado al que señale VERT[I]. En cada caso el último de esos lados
apuntará a cero. En este modelo Los arreglos COLA y CABEZA contienen realmente varias listas
enlazadas de lados, una lista para cada vértice.
VERT POS[i] TAIL HEAD NEXT
1 2 2 3 7
2 1 1 2 4
3 6 5 4 0
4 0 1 3 5
5 3 1 6 0
6 9 3 4 8
2 1 0
3 5 10
6 1 0
3 6 0
EJERCICIOS
1. Sea A = {1, 2, 3, 4} y sea R = {(1,1), (1,2), (1,3), (2,3), (2,4), (3,1), (3,4), (4,2)} una relación
sobre A. Calcule la Matriz MR que de la representación de R y los valores de los arreglos VERT,
TAIL, HEAD y NEXT que describan R como una lista enlazada. Enlazar en orden creciente.
2. Sea A = {1, 2, 3, 4} y sea R la relación cuyo dígrafo aparece

al lado. Describa los arreglos VERT, TAIL, HEAD y NEXT que
describan R como una lista enlazada, de manera que los lados
que salen de cada vértice sean alcanzados en la lista en orden
creciente.
3. Sea A = {1, 2, 3, 4, 5, 6, 7} y sea R la relación cuyo dígrafo

aparece al lado. Describa los arreglos VERT, TAIL, HEAD y
NEXT que describan R como una lista enlazada, de manera
que los lados que salen de cada vértice sean alcanzados en la
lista en orden decreciente.
4. Considere los siguientes arreglos
VERT = [1, 2, 3, 4]
TAIL = [1, 2, 2, 4, 4, 3, 4, 1]
HEAD = [2, 2, 3, 3, 4, 4, 1, 3]
NEXT = [8, 3, 0, 5, 7, 0, 0, 0]
Los cuales describen una relación R en el conjunto A = {1, 2, 3, 4}. Dibuje el dígrafo de R y la matriz
MR .
5. Considere los siguientes arreglos
VERT = [1, 2, 3, 4, 5]
TAIL = [1, 1, 2, 3, 3, 3, 4, 5, 5]
HEAD = [2, 4, 3, 4, 1, 5, 1, 1, 2]
NEXT = [2, 0, 0, 6, 0, 5, 0, 0, 8]
Los cuales describen una relación R en el conjunto A = {1, 2, 3, 4, 5}. Dibuje el dígrafo de R y la
matriz MR.
UNIDAD V - FUNCIONES
Una función f del conjunto X al conjunto Y es una relación del conjunto Y. A los elementos del con-
junto X se les llamará entradas de f, y a los elementos del conjunto Y se les llamará salidas de f. La
notación f : X→ Y significará que f es una función del conjunto X al conjunto Y. Al conjunto X se le
llamará el dominio de f , mientras que al conjunto Y se le llamará codominio de f . Para que f sea
considerada una función debe satisfacer dos axiomas:
Para un x∊X, el único elemento y de Y que cumple (x,y)∊f, se le simbolizará por f(x) y se le llamará
imagen de f en x o también valor de f en x.
El conjunto de todos los elementos de Y que son valores de algún elemento de X se le llamará el
rango de f:
Para un y∊Y puede o no existir algún elemento x∊X tal que f(x)=y, al conjunto de todos los
posibles x’s que cumplan esto se les llamará imagen inversa de y.
Considérese la función:
• Dominio de f = {a, b, c}
• Codominio de f = {1, 2, 3, 4}
• f(a) = 1, f(b) = 2, f(c) = 1
• Rango de f = {1, 2}
• Imagen inversa de 1 = {a, c}
• Imagen inversa de 2 = {b}
• Imagen inversa de 3 = {}
• Pares que forman f = {(a,1), (b,2), (c,1)}
FUNCIONES ESPECIALES EN CIENCIAS DE LA COMPUTACIÓN
FUNCIÓN MÓDULO
Sea m un número entero positivo. Para cada número entero n el módulo m de n es el residuo
positivo de la división entera de n entre m:
Ejemplos:
FUNCIÓN PISO
Para cada número real x el piso de x es el mayor entero que es menor o igual a x, corresponde esta
función al redondeo al número entero menor más próximo: Se representa
Ejemplos:
FUNCIÓN TECHO
Para cada número real x el techo x es el menor entero que es mayor o igual a x, redondeo al
número entero mayor más próximo: Se representa
Ejemplos:
FUNCIONES HASH
Sirven para garantizar la integridad de los textos. El código ASCII asigna un número a cada letra o
signo de puntuación:
Es una clave simétrica estándar internacional. La utilizan, por ejemplo, todos los computadores.
Podemos substituir cada letra de un texto por su código ASCII:
Podemos utilizar los códigos ASCII de un texto para hacer cualquier cálculo:
Aquí, cada tres caracteres, con sus códigos ASCII, se opera (1º-2º)*3º . La suma de los resultados
es una función HASH que identifica perfectamente el texto.
Cualquier modificación en el texto provoca un cambio en el valor de la función HASH.

Por ejemplo, al substituir “rincón” por “ rincon ” sin acento, el valor HASH ha pasado de -11.399 a
3.121 .
Ejemplo:
Ana envía un mensaje a Benito. Al final del mensaje le añade el valor HASH del texto según una
función en la que se han puesto previamente de acuerdo.
Benito recibe el mensaje y calcula el valor HASH. Si coincide con el que ha dicho Ana puede estar
seguro de que el mensaje no ha sido modificado.
Los textos enviados electrónicamente pueden deformarse, bien por la intervención de terceras
personas, o bien por errores en la transmisión. Las funciones HASH sirven para garantizar la
integridad de los textos.
EJERCICIOS
1. Sea f la función mod 10. Calcule:
a. f(417) b. f(38) c. f(253)
2. Sea f la función mod 7. Calcule:
a. f(81) b. f(316) c. f(1057)
3. Calcule cada uno de los siguientes:
a. ⌊2,78⌋ b. ⌊−2,78⌋ c. ⌊28⌋ d. ⌊−17,8⌋ e. ⌊21,48⌋
4. Calcule cada uno de los siguientes:
a. ⌈3,34⌉ b. ⌈−3,34⌉ c. ⌈34⌉ d. ⌈−13,4⌉ e. ⌈31,4⌉
5. Utilice la función de hash h, la cual toma los primeros tres dígitos del número de cuenta como un
número y los últimos cuatro dígitos como otro número, los suma y luego aplica la función mod 59.
Determine a cuál lista debe agregarse las siguientes cuentas:
a. 3759273 b. 7149021 c. 5167249 d. 6751238 e. 3344543

6. Determine en cuál lista habrá que buscar para encontrar la cuenta de los siguientes clientes, si
se definió una función hash tal que se toman los cuatro primeros dígitos como un número y se
suman al número formado por los últimos tres dígitos y luego se les aplica la función mod de los
últimos dos dígitos.
a. 2561384 b. 6082376 c. 4984620 d. 9127655 e. 8712120

Curso Matemáticas Discretas

Cargado por

Copyright:

Formatos disponibles

Curso Matemáticas Discretas

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Curso Matemáticas Discretas

Cargado por

Copyright:

Formatos disponibles

INTRODUCCIÓN A LA TEORÍA DE CONJUNTOS

EL CONCEPTO DE CONJUNTO ES FUNDAMENTAL EN MATEMÁTICA , incluso más que la operación

La noción simple de una colección o conjunto de objetos es fundamental en la estructura básica de

De esta manera, si A es un conjunto, y a, b, c, d, e todos sus elementos, es común escribir:

para definir a tal conjunto .

En otras palabras, tenemos que:

Tal relación se representa simbólicamente de la siguiente manera:

Volviendo al conjunto anterior, también podemos afirmar que:

Y se representa simbólicamente de la siguiente manera:

Hay dos formas de determinar conjuntos.

A={a, e, i, o, u} entonces 𝑎𝑎 ∈ 𝐴𝐴, 𝑜𝑜 ∈ 𝐴𝐴 pero 𝑣𝑣 ∉ 𝐴𝐴

C = { m, a, t, e, i, c, s } En un conjunto determinado por extensión no se repite un mismo elemento y

A = {x/x es una letra vocal}

B = {x/x es un número positivo par menor que 10}, entonces 2 ∈ 𝐵𝐵 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 5 ∉ 𝐵𝐵

C = {x/x es una letra de la palabra matemáticas}

Vamos a mostrar un cuadro comparativo de determinación de conjuntos

A = { x/x es una vocal }

B = { x/x es un número positivo par menor que 10 }

C = { x/x es una letra de la palabra conjuntos }

D = { x/x es un número positivo impar menor que 10 }

E = { x/x es una consonante del alfabeto español}

Los diagramas de Venn tienen el nombre de su creador, John Venn,

En un Diagrama de Venn cada conjunto se representa mediante un óvalo, círculo o rectángulo. Al

M = {x / x es un alumno matriculado en el curso Matemática Discreta} Conjunto finito

N = {0, 1, 2, 3, 4, 5, 6, 7, 8, ... } Conjunto infinito

P = {x / x es un país miembro de la Organización de Naciones Unidas} Conjunto finito

En la igualdad, el orden de los elementos de cada conjunto no importa.

C = {1, 2, 3, 3, 4, 1} D = {1, 2, 2, 3, 3, 4,} C= D

E = {x/x es una vocal de la palabra mundo} F = {u, o} E = F

A= { x/x es número natural menor que 0 } A = { } A = Ø

B = { x / x es un mes que tiene 33 días} B = { } B = Ø

D = { x / x es un día terrestre de 90 horas } D = { } D = Ø

Es todo conjunto que está formado por un sólo y único elemento.

B = {x/x es un número par entre 6 y 10} = {8}

C = {x/x es la capital de Costa Rica} = {San José}

Sean los conjuntos:

P={x/x es un número primo par}

I={x/x es un número positivo impar menor que 11}

Existe otro conjunto que incluye a los conjuntos P, X, I. Es

U = {x/x es un número positivo menor o igual que 10}

Gráficamente se representa por un rectángulo tal como se observa a continuación.

La cardinalidad de un conjunto es un concepto que se refiere al número de elementos que tiene

Decimos que un conjunto A es subconjunto de otro B, si cada elemento de A lo es de B. En este caso

En términos simbólicos esto suele ser expresado de la siguiente forma:

Que leemos A está contenido en B si y solo si cada elemento de A, es elemento de B.

Por otra parte, si denota el conjunto de los números racionales, entonces

2. Sean A = {1, 2, 3, 4, 5, 6}, B = {2, 4, 5} y C = {1, 2, 3, 4, 5}.

Es decir, todo conjunto es un subconjunto de sí mismo.

Es un conjunto cuyos elementos son todos conjuntos.

F = {{}, {a}, {a, b}, {a,b,c}}

Solamente en este caso es válido decir que {a} es un elemento de F, o sea

Pero no es correcto indicar que , ya que en este caso particular

a) M = { 1, 2 } El conjunto M tiene 2 elementos, la cardinalidad de M es 2.

2M = { {1}, {2}, {1, 2}, ø} entonces M tiene 22 = 4 subconjuntos

b) M = { 1, 2, 3 } El conjunto M tiene cardinalidad 3.

Si un conjunto M es finito con "n" elementos, entonces su cardinalidad es “n” y el conjunto

2. Sea . Identifique cada uno de los siguientes casos como verdadero o

Se llama UNIÓN de dos conjuntos A y B al conjunto formado por los elementos de A o de B, es

Ejemplo: Sean A = {a, b, c, d, e, f} y B={b, d, r, s}

Entonces está formado por todos los elementos que pertenecen a A o a B.