• Author / Uploaded
• David

Citation preview

Matem´ aticas discretas (material de apoyo de clase)

Dr. Miguel Mata P´ erez

[email protected] Facultad de Ingenier´ıa Mec´anica y El´ectrica Universidad Aut´onoma de Nuevo Le´on

Nuevo Le´on, M´exico 19 de abril de 2018

Matem´aticas discretas (M. Mata)

¡Material en construcci´on! (versi´on: 2018.04.19)

ii

´Indice general Introducci´ on

V

1. L´ ogica 1.1. Proposiciones . . . . . . . . . . . . . . . 1.2. Operadores l´ogicos . . . . . . . . . . . . 1.2.1. Negaci´on . . . . . . . . . . . . . . 1.2.2. Conjunci´on . . . . . . . . . . . . 1.2.3. Disyunci´on . . . . . . . . . . . . 1.2.4. Implicaci´on . . . . . . . . . . . . 1.2.5. Doble implicaci´on . . . . . . . . . 1.2.6. Precedencia . . . . . . . . . . . . 1.3. Representaciones . . . . . . . . . . . . . 1.3.1. Tablas de verdad . . . . . . . . . 1.3.2. Redes de decisi´on . . . . . . . . . 1.3.3. Diagrama de decisi´on binario . . 1.4. Tautolog´ıas . . . . . . . . . . . . . . . . 1.4.1. Implicaci´on tautol´ogica . . . . . . 1.4.2. Equivalencias . . . . . . . . . . . 1.4.3. Leyes del a´lgebra de proposiciones 1.4.4. M´as sobre la implicaci´on . . . . . 1.5. Argumentos . . . . . . . . . . . . . . . . 1.5.1. Reglas de inferencia . . . . . . . . 1.5.2. Demostraciones . . . . . . . . . . 1.6. Cuantificadores . . . . . . . . . . . . . . 1.6.1. Negaci´on . . . . . . . . . . . . . . 1.6.2. Cuantificadores anidados . . . . . 2. Conjuntos

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

1 2 2 2 3 3 3 4 4 4 4 5 6 8 8 9 9 10 11 11 13 13 15 15 17

i

Matem´aticas discretas (M. Mata)

ii

2.1. 2.2. 2.3. 2.4. 2.5. 2.6.

Relaci´on de pertenencia . . . . . . . . . . . Subconjuntos e igualdad . . . . . . . . . . . Conjunto universal y conjunto vac´ıo . . . . . Cardinalidad . . . . . . . . . . . . . . . . . Conjunto potencia . . . . . . . . . . . . . . Operaciones con conjuntos . . . . . . . . . . 2.6.1. Uni´on . . . . . . . . . . . . . . . . . 2.6.2. Intersecci´on . . . . . . . . . . . . . . 2.6.3. Diferencia . . . . . . . . . . . . . . . 2.6.4. Complemento . . . . . . . . . . . . . 2.6.5. Propiedades de los conjuntos . . . . . 2.6.6. Propiedades de las cardinalidades . . 2.7. Diagramas de Venn . . . . . . . . . . . . . . 2.7.1. Conteo mediante diagramas de Venn 3. Alfabetos, cadenas y lenguajes 3.1. Alfabetos . . . . . . . . . . . . . . . 3.2. Cadenas . . . . . . . . . . . . . . . . 3.2.1. Concatenaci´on . . . . . . . . . 3.2.2. Subcadenas, prefijos y sufijos 3.2.3. Potencia de una cadena . . . 3.2.4. Reflexi´on de una cadena . . . 3.3. Lenguajes . . . . . . . . . . . . . . . 3.3.1. Operaciones entre lenguajes . 3.3.2. Concatenaci´on de lenguajes . 3.3.3. Reflexi´on de un lenguaje . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

4. Producto cartesiano y matrices 4.1. Producto cartesiano . . . . . . . . . . . . . . . 4.1.1. Pares ordenados . . . . . . . . . . . . . 4.1.2. Conjunto producto . . . . . . . . . . . 4.1.3. Conjunto producto en general . . . . . 4.1.4. Conjuntos de verdad de proposiciones˚ 4.2. Matrices . . . . . . . . . . . . . . . . . . . . . 4.2.1. Matriz traspuesta . . . . . . . . . . . . 4.2.2. Matrices cuadradas . . . . . . . . . . . 4.2.3. Matriz diagonal y matriz identidad . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

¡Material en construcci´on! (versi´on: 2018.04.19)

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . .

17 18 18 19 20 20 20 20 20 21 22 23 23 24

. . . . . . . . . .

25 25 26 27 27 28 28 28 29 29 29

. . . . . . . . .

31 31 31 31 32 32 33 34 34 34

Matem´aticas discretas (M. Mata)

iii

4.2.4. Matriz sim´etrica . . . . . . . . . . . . . . . . . . . . . . . 4.2.5. Matrices triangulares . . . . . . . . . . . . . . . . . . . . . 4.2.6. Operaciones entre matrices* . . . . . . . . . . . . . . . . . 5. Relaciones y funciones 5.1. Relaciones . . . . . . . . . . . . . . . . . . . . . 5.1.1. Representaci´on gr´afica de una relaci´on . 5.1.2. Representaci´on matricial de una relaci´on 5.1.3. Dominio y rango de una relaci´on . . . . 5.1.4. Relaci´on inversa . . . . . . . . . . . . . . 5.2. Relaciones de equivalencia y relaciones de orden 5.2.1. Relaciones de orden . . . . . . . . . . . . 5.2.2. Relaciones de equivalencia . . . . . . . . 5.2.3. Particiones . . . . . . . . . . . . . . . . . 5.2.4. Relaciones de equivalencia y particiones 5.3. Funciones . . . . . . . . . . . . . . . . . . . . . 5.3.1. Gr´afica de una funci´on . . . . . . . . . . 5.3.2. Composici´on de funciones . . . . . . . . 5.3.3. Funciones inyectivas y sobreyectivas . . . 5.3.4. Funci´on inversa . . . . . . . . . . . . . . 5.3.5. Funci´on identidad . . . . . . . . . . . . . 6. Recursividad 6.1. Sucesiones . . . . . . . . . . . . . . . . . . 6.1.1. Sucesiones crecientes y decrecientes 6.1.2. Subsucesiones . . . . . . . . . . . . 6.2. Funciones recursivas . . . . . . . . . . . . 6.3. Notaci´on Sigma . . . . . . . . . . . . . . . 6.4. Inducci´on matem´atica . . . . . . . . . . . 7. Combinatoria 7.1. Conteo . . . . . . . . . . . . . . . . . . . 7.1.1. Principio fundamental del conteo 7.2. Permutaciones . . . . . . . . . . . . . . . 7.2.1. Permutaciones con repetici´on . . 7.3. Combinaciones . . . . . . . . . . . . . . 7.4. Diagramas de ´arbol . . . . . . . . . . . . 7.5. Coeficientes binomiales . . . . . . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

¡Material en construcci´on! (versi´on: 2018.04.19)

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . . . .

. . . . . . .

35 35 35

. . . . . . . . . . . . . . . .

36 36 36 37 38 38 39 40 40 40 41 42 43 44 45 45 46

. . . . . .

47 47 47 48 48 49 50

. . . . . . .

53 53 53 53 54 55 55 57

Matem´aticas discretas (M. Mata)

iv

7.5.1. Tri´angulo de Pascal . . . . . . . . . . . . . . . . . . . . . . 7.5.2. Teorema del binomio . . . . . . . . . . . . . . . . . . . . . 8. Teor´ıa de grafos 8.1. Grafos . . . . . . . . . . . . . . . . . . . . 8.2. Definiciones b´asicas . . . . . . . . . . . . . 8.2.1. Incidencia y adyacencia . . . . . . . 8.2.2. Cadenas, caminos, ciclos y circuitos 8.3. Algunos tipos de grafos . . . . . . . . . . . 8.3.1. Grafos completos . . . . . . . . . . 8.3.2. Grafos conexos . . . . . . . . . . . ´ 8.3.3. Arboles . . . . . . . . . . . . . . . 8.3.4. Grafos bipartitos . . . . . . . . . . 8.4. Predecesores, sucesores y grados . . . . . . 8.5. Representaciones matriciales . . . . . . . .

57 58

. . . . . . . . . . .

59 59 61 61 61 63 63 63 64 64 64 65

A. Conjuntos num´ ericos A.1. Breve resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66 66

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

¡Material en construcci´on! (versi´on: 2018.04.19)

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

Introducci´ on Respecto a estas notas Este material ha sido preparado como material de apoyo para la materia de ((Matem´aticas discretas)) que se imparte a nivel licenciatura en la Facultad de Ingenier´ıa Mec´anica y El´ectrica de la Universidad Aut´onoma de Nuevo Le´on. No es propiamente el material del curso, y su elaboraci´on est´a a´ un en construcci´on por lo que el infortunado lector podr´a encontrar que a´ un hay partes no desarrolladas, otras inacabadas e incluso otras a´ un ausentes. A´ un con lo anterior, el material se encontrar´a en desarrollo continuo y esperamos sinceramente que, eventualmente, sea de utilidad.

Competencias espec´ıficas De acuerdo al programa anal´ıtico de la materia, las competencias de la materia son: ((Modelar problemas por m´etodos anal´ıticos y/o computacionales, generando alternativas de soluci´on basadas en lenguaje matem´atico y computacional de tal manera que permite identificar el fundamento matem´atico que sustenta a la computadora. ))Implementar soluciones tecnol´ogicas a problemas de ingenier´ıa en software y hardware de tal forma que est´e basada en algoritmos matem´aticos y computacionales)).

Unidades tem´ aticas De acuerdo a la academia, este curso debe cubrir: L´ogica v

Matem´aticas discretas (M. Mata)

vi

Combinatoria Grafos Seg´ un los ejercicios del programa anal´ıtico, este curso debe cubrir: Tablas l´ogicas Inducci´on matem´atica Leyes, propiedades y operaciones con conjuntos Tipos de sucesiones Tipos cadenas y alfabetos Relaciones de recurrencia mediante gr´aficas y matriz de relaciones Representaci´on de funciones Seg´ un un miembro de la academia, el material se deber´ıa organizar de la siguiente manera: L´ ogica: representaci´on digital, expresiones booleanas, tablas de verdad, inferencia, ´arboles de decisi´on, circuitos. Combinatoria: inducci´on, sucesiones, funciones, conjuntos. Grafos y ´ arboles: recorridos, modelos, problemas y algoritmos fundamentales, optimizaci´on combinatoria. Otro miembro de la acad´emia propuso un orden distinto pero similar. En este material hemos hecho una fusi´on de todo lo anterior ordenado en una secuencia l´ogica de acuerdo al contenido.

Calificaci´ on De acuerdo a la academia, esta materia debe ser evaluada de la siguiente manera: Ex´ amenes: 40 %. Actividades: 50 %. Proyecto: 10 %.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

vii

Incidencia en los planes de estudio Seg´ un los programas vigentes, la materia de ((Matem´aticas discretas)) forma parte de los planes de estudio de las siguientes carreras: IAS (401): 2.o semestre. Materia obligatoria. IAS: 3.er semestre. Materia obligatoria. ITS: 3.er semestre. Materia obligatoria. IMTC (401): 5.o semestre. Materia optativa.

Bibliograf´ıa R. Johnsonbaugh. Matem´aticas discretas. 6.a edici´on. Editorial Pearson Educaci´on. M´exico, 2005. S. Lipschutz. Matem´aticas finitas. McGraw-Hill. M´exico, 1966. R. Grimaldi. Matem´aticas discretas y combinatoria. 3.a edici´on. Editorial Addison-Wesley Iberoamericana. Estados Unidos, 1997.

¡Material en construcci´on! (versi´on: 2018.04.19)

Cap´ıtulo 1 L´ ogica La ((l´ogica)) es una ciencia formal que estudia el ((razonamiento)) correcto. Suele ser confundida con el ((sentido com´ un)). Por ello, antes de comenzar, iniciemos con un peque˜ no examen de l´ogica. Responda a lo siguiente: 1. ¿Es verdadera la afirmaci´on ((algunos de los alumnos de este sal´on tienen menos de 80 a˜ nos))? 2. Si estudio, apruebo. No estudio. ¿Cu´al es la conclusi´on? 3. La afirmaci´on ((Madrid est´a en Espa˜ na o Londres est´a en Inglaterra)) ¿es verdadera o falsa? 4. ((Si dos rectas son paralelas no se intersectan e inversamente)), en este caso, ¿qu´e es ((inversamente))?, es decir, ¿cu´al es la afirmaci´on ((inversa))? 5. El siguiente, ¿es un razonamiento correcto? ((Si estudio aprendo m´as)), ((Estudio)) y ((No aprendo m´as)), por lo tanto ((Soy un genio)). 6. El padre dijo a su hijo, ((Si sacas buenas notas te compro una bicicleta)), el ni˜ no sac´o malas notas, cuando el padre las vio el hijo le pregunt´o, ((Pap´a, ¿me vas a comprar una bicicleta?)). ¿Hizo el ni˜ no una pregunta l´ogica? Las respuestas correctas son: 1. S´ı. 2. Se puede concluir cualquier cosa. 3. Verdadera. 4. Si dos rectas no se intersectan son paralelas. 5. S´ı. 6. S´ı. Si contest´o incorrectamente a m´as de una de las preguntas anteriores, no puede obviar este cap´ıtulo.

1

Matem´aticas discretas (M. Mata)

1.1.

2

Proposiciones

Una proposici´on es un enunciado que puede ser calificado como verdadero o falso. Ejemplo 1.1. Las siguientes son proposiciones simples: 1. Par´ıs est´a en Inglaterra. 2. 1 ` 1 “ 3. 3. x2 ` 1 ą 0. 4. Las violetas son azules. 5. Hoy es mi´ercoles. En cambio, expresiones como ((Hola, ¿qu´e hace?)), ((Cierra la puerta)) o ((¡Viva M´exico!)) no son proposiciones. Denotaremos las proposiciones simples con letras min´ usculas: p, q, r, . . .

1.2.

Operadores l´ ogicos

Las proposiciones simples pueden combinarse para formar proposiciones m´as complejas mediante algunos operadores l´ogicos. Las proposiciones compuestas las denotaremos, en ocasiones, con letras may´ usculas.

1.2.1.

Negaci´ on

Dada una proposici´on p la negaci´on de p es tambi´en una proposici´on. La denotaremos p y se lee ((no p)). Su valor de verdad ser´a el contrario al de p. Ejemplo 1.2. Algunos ejemplos de negaci´on: 1.

p: Par´ıs est´a en Inglaterra, p: Par´ıs no est´a en Inglaterra.

2.

q: 1 ` 1 “ 3, q: 1 ` 1 ‰ 3.

3.

r: x2 ` 1 ą 0, r: x2 ` 1 ď 0.

4.

s: Las rosas son rojas, s: Las rosas no son rojas. ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

1.2.2.

3

Conjunci´ on

Dadas dos proposiciones p y q la conjunci´on de p con q es tambi´en una proposici´on. La denotaremos p ^ q y se lee ((p y q)). Su valor de verdad ser´a verdadero s´olo cuando ambas proposiciones p y q sean verdaderas. Ejemplo 1.3. Algunos ejemplos de conjunci´on: 1. p: Par´ıs est´a en Inglaterra, q: Madrid est´a en Espa˜ na, p ^ q: Par´ıs est´a en Inglaterra y Madrid est´a en Espa˜ na. 2. p: |x| ą π, q: x2 ´ 16 ď 0, p ^ q: |x| ą π y x2 ´ 16 ď 0. 3. p : Las rosas son rojas, q: Las violetas son azules, p ^ q: Las rosas son rojas y las violetas son azules.

1.2.3.

Disyunci´ on

Dadas dos proposiciones p y q la disyunci´on de p con q es tambi´en una proposici´on. La denotaremos p _ q y se lee ((p o q)). Su valor de verdad ser´a falso s´olo cuando ambas proposiciones p y q sean falsas. Ejemplo 1.4. Algunos ejemplos de disyunci´on: 1. p: Par´ıs est´a en Inglaterra, q: Madrid est´a en Espa˜ na, p _ q: Par´ıs est´a en Inglaterra o Madrid est´a en Espa˜ na. 2. Sacas buenas calificaciones o no vas a la fiesta.

1.2.4.

Implicaci´ on

Dadas dos proposiciones p y q la implicaci´on de p con q es tambi´en una proposici´on. La denotaremos p Ñ q y se lee ((p implica q)) o ((si p entonces q)) (entre otras expresiones). Su valor de verdad ser´a falso s´olo cuando p sea verdadera pero q sea falsa. Ejemplo 1.5. Algunos ejemplos de implicaci´on: 1. p: Par´ıs est´a en Francia, q: Madrid est´a en Inglaterra, p Ñ q: Si Par´ıs est´a en Francia, Madrid est´a en Inglaterra. 2. Si x ă ´2 entonces x2 ą 4. 3. Si apruebas matem´aticas te compro una bicicleta. ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

1.2.5.

4

Doble implicaci´ on

Dadas dos proposiciones p y q la doble implicaci´on de p y q es tambi´en una proposici´on. La denotaremos p Ø q y se lee ((p si y s´olo si q)) o ((p siempre y cuando q)). Su valor de verdad ser´a verdadero s´olo cuando p y q tengan el mismo valor de verdad.

1.2.6.

Precedencia

Cuando se escriben sin par´entesis, los operadores se ejecutan con la siguiente precedencia: , ^, _, Ñ, Ø. De esta manera, la expresi´on p _ q ^ r _ s Ñ p _ s es equivalente a rp _ pq ^ p rqq _ ss Ñ rp _ p sqs.

1.3.

Representaciones

Los valores de verdad de las proposiciones se representan simb´olicamente de diversas maneras: Verdadero: Falso:

V, T, J, 1. F, F, K, 0.

En este curso, usaremos los valores binarios 1 y 0.

1.3.1.

Tablas de verdad

Las tablas de verdad de los operadores son como sigue: p q p^q p q p_q p q pÑq p p 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1

p 1 1 0 0

q pØq 1 1 0 0 1 0 0 1

Con estas tablas podemos calcular los valores de verdad de expresiones m´as complejas.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

5

Ejemplo 1.6. Calcular la tabla de verdad de pp _ qq ^ r. p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

A kj hkkik B kj hkkik p_q r A^B 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 0

Ejercicio 1.7. Calcular la tabla de verdad de rp ^ pq _ rqs _ p.

p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

A B kj hkkikkj hkkik r q_ r p^A B_p 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0

Ejercicio 1.8. Calcular la tabla de verdad de p ^ rp q ^ rq _ pq ^ rqs.

p 1 1 1 1 0 0 0 0

1.3.2.

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

C A B hkkikkj hkkikkj hkkikkj q^r q^ r A_B p^C 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0

Redes de decisi´ on

Existe una representaci´on de redes de los operadores binarios , _ y ^. Suele ser u ´til en la comprensi´on de circuitos o redes el´ectricas, y en diagramas de comunicaci´on y conmutadores. ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

6

Imaginemos que hay un emisor T0 y un receptor T1 . El flujo debe pasar por algunos puertos que pueden estar abiertos (valor de 1) o cerrados (valor de 0). p

T0

T1

En este caso, el flujo ser´a recibido en el receptor si p toma el valor de 1, y no ser´a recibido si toma el valor de 0. La red toma la siguiente forma para el disyuntivo p _ q: p T0

T1 q

La red toma la siguiente forma para el conjuntivo p ^ q: p

T0

q

T1

Ejemplo 1.9. Dibujar la red de decisi´on para rp ^ p r _ sqs _ rq ^ ts: p

r s

T0 q

T1

t

Ejercicio 1.10. Dibujar la red de decisi´on para rrp ^ pq _ rqs _ rpq _ sq ^ tss ^ s:

1.3.3.

Diagrama de decisi´ on binario

´ Arbol de decisi´on binario y diagrama (reducido) de decisi´on binario. Ejemplo 1.11. pp ^ qq _ pp ^ rq _ pq ^ rq p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

A kj hkkik B kj hkkik C kj hkkik p^q p^r q^r A_B_C 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

7

p

p

q

q

r 1

r 1

1

q

r 0

1

r 0

0

q r

0

1

0

Ejemplo 1.12. p p ^ q ^ rq _ pp ^ qq _ pq ^ rq p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

A B kj hkkik C kj hkkkkkkkikkkkkkkj hkkik p^ q^ r p^q q^r A_B_C 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1

p

p

q

q

r 1

r 1

0

q

r 0

1

r

r 0

0

1

1

Ejercicio 1.13. p _ rp ^ pq _ rqs.

p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

q

A B kj hkkikkj hkkik q_ r p^A p_B 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0

¡Material en construcci´on! (versi´on: 2018.04.19)

r 0

Matem´aticas discretas (M. Mata)

8

p

p

q

q

r 1

1.4.

r 1

1

r 1

0

r 0

0

0

1

0

Tautolog´ıas

Ejercicio 1.14. Calcular la tabla de verdad de la siguiente proposici´on: r p _ pq ^ rqs _ rp ^ p q _ rqs.

p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

A B C D kj hkkikkj hkkikkj hkkikkj hkkik q^ r p_A q_r p^C B_D 0 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1

Observamos que el valor de verdad de la expresi´on anterior es verdadero, sin importar los valores de verdad de p, q y r. Este tipo de expresiones, en las que su u ´nico valor posible es verdadero, son de particular inter´es en matem´aticas y se les llama tautolog´ıas.

1.4.1.

Implicaci´ on tautol´ ogica

Cuando una proposici´on es una implicaci´on y es una tautolog´ıa se llama implicaci´on tautol´ogica. Esta estructura es importante porque, si A Ñ B es una tautolog´ıa, entonces B es cierta si A lo es, sin importar los valores de verdad de las variables simples. Es decir, tenemos una estructura que es siempre v´alida para todas las variables. Cuando A implica tautol´ogicamente a B se escribe A ñ B.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

9

Ejercicio 1.15. Verifique que: rp Ñ pq ^ rqs ^ r ñ

p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

p

A kj hkkikkj B C hkkik hkkikkj q^r pÑA B^ r C Ñ 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1

p

El resultado es verdadero en todos los casos, por lo tanto s´ı es una implicaci´on tautol´ogica.

1.4.2.

Equivalencias

Cuando una proposici´on es una doble implicaci´on y es una tautolog´ıa se llama equivalencia. Esta estructura es importante porque, si A Ø B es una tautolog´ıa, entonces A tiene el mismo valor de verdad de B. Es decir, tenemos una estructura que es equivalente para todas las variables. Cuando A es equivalente a B se escribe A ô B. Ejercicio 1.16. Verifique que: A 1 1 0 0

pA Ñ Bq ô pA ^ Bq

B AÑB 1 1 0 0 1 1 0 1

pA Ñ Bq A ^ B 0 0 1 1 0 0 0 0

El resultado es el mismo en las dos columnas correspondientes (las dos u ´ltimas, en este caso), por lo tanto s´ı son equivalentes. Ejercicio 1.17. Verifique que: pA Ø Bq ô rpA Ñ Bq ^ pB Ñ Aqs

1.4.3.

Leyes del ´ algebra de proposiciones

Todas las siguientes son equivalencias tautol´ogicas, por lo cual pueden enunciarse como leyes.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

1 2 3 4 5 6 7 8 9

10

p_pôp p^pôp p_q ôq_p p^q ôq^p p _ pq _ rq ô pp _ qq _ r p ^ pq ^ rq ô pp ^ qq ^ r p _ pq ^ rq ô pp _ qq ^ pp _ rq p ^ pq _ rq ô pp ^ qq _ pp ^ rq pp _ qq ô p ^ q pp ^ qq ô p _ q p pq ô p p_ pô1 p^ pô0 p_0ôp p^1ôp p_1ô1 p^0ô0

Leyes idempotentes Leyes conmutativas Leyes asociativas Leyes distributivas Leyes de De Morgan Doble negaci´on Leyes de complementaci´on Leyes de identidad Leyes de dominaci´on

Ejercicio 1.18. Demostrar, mediante las leyes de las proposiciones, las siguientes equivalencias: 1. pp _ qq ^ p ô

p^q

2. p _ pp ^ qq ô p 3.

1.4.4.

pp _ qq _ p p ^ qq ô

p

M´ as sobre la implicaci´ on AÑB BÑA AÑ B BÑ A

Implicaci´on Inversa Conversa Contrapuesta

Ejemplo 1.19. Sean A : pienso, B : existo. 1. Implicaci´on: ((Pienso, luego existo)). 2. Inversa: Existo, entonces pienso. 3. Conversa: No pienso, entonces no existo. ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

11

4. Contrapuesta: No existo, entonces no pienso. Ejercicio 1.20. ((Si dos rectas son paralelas, no se intersectan, e inversamente)). En este caso, ¿qu´e es ((inversamente))? Algunas leyes m´as que involucran la implicaci´on: 10 11 12 13

1.5.

pÑqô qÑ p pÑq ô p_q pp Ñ qq ô p ^ q p Ø q ô pp Ñ qq ^ pq Ñ pq

Contrapuesta Equivalencia a la implicaci´on Negaci´on de la implicaci´on Doble implicaci´on

Argumentos

Definici´ on 1.21. Un argumento es la deducci´on de una conclusi´on Q a partir de un conjunto de premisas P1 , P2 ,. . . , Pn . Un argumento, denotado por P1 , P2 , . . . , Pn $ Q, es v´alido si la conclusi´on Q es verdadera cuando todas las premisas son verdaderas. Observaci´ on 1.22. El argumento P1 , P2 , . . . , Pn $ Q es v´alido si y s´olo si pP1 ^ P2 ^ ¨ ¨ ¨ ^ Pn q ñ Q. Ejemplo 1.23. Verificar si el siguiente es un argumento v´alido: ((Todos los hombres son mortales)), ((Homero es hombre)), por lo tanto, ((Homero es mortal)). Ejemplo 1.24. Verificar si el siguiente es un argumento v´alido: p _ q, r Ñ

q, s ^ r, t Ñ

p $

pt ^ rq

Una opci´on ser´ıa verificar mediante su tabla de verdad que: rpp _ qq ^ pr Ñ

qq ^ ps ^ rq ^ pt Ñ

pqs ñ

pt ^ rq

Afortunadamente hay una alternativa. Notaci´ on 1.25. El argumento P1 , P2 , . . . , Pn $ Q tambi´en suele denotarse verticalmente de la forma P1 P2 .. . Pn Q

1.5.1.

Reglas de inferencia

Existen modelos de argumentos ya establecidos. Son llamados reglas de inferencia. Las siguientes son algunas de las m´as u ´tiles:

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

12

Modus ponendo ponens:

AÑB A B

Simplificaci´ on:

A^B A

Modus tollendo tollens:

AÑB B A

Adici´ on:

A A_B

Modus tollendo ponens:

A_B B A

Conjunci´ on:

A B A^B

Silogismo hipot´ etico:

AÑB BÑC AÑC

Prueba por casos:

AÑC BÑC A_B C

Ejercicio 1.26. Demostrar mediante su tabla de verdad el modus ponendo ponens, es decir, que pA Ñ Bq ^ A ñ B. Soluci´on: A 1 1 0 0

B A Ñ B pA Ñ Bq ^ A rpA Ñ Bq ^ As Ñ B 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 1

Lo cual es una tautolog´ıa, por lo tanto el modus ponendo ponens es verdad. Ejercicio 1.27. Demostrar, por medio de las reglas de inferencia, que los siguientes argumentos son v´alidos: 1.

p Ñ ps _ tq,

p $ s_t

Equivalentemente:

Soluci´on:

P1 : p Ñ ps _ tq P2 : p Q: s_t

Q : s _ t por M. ponens de P2 en P1 .

2. r Ñ s,

s^p $

r

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

13

Equivalentemente:

Soluci´on:

P1 : r Ñ s P2 : s^p Q: r

C1 : Q:

3. q Ñ s,

s r

p _ q, r ^ p $ s _ t

Equivalentemente:

Soluci´on:

P1 : q Ñ s P2 : p_q P3 : r ^ p Q: s_t

C1 : C2 : C3 : Q:

4. p _ q, r Ñ

7. A,

1.5.2.

p q s s_t

q, s ^ r, t Ñ

5. p _ q, t ^ p, q Ñ 6. m Ñ n,

por simplificaci´on en P2 , por M. tollens de C1 en P1 .

por por por por

p $

simplificaci´on en P3 , ponendo tollens de C1 en P2 , m. ponens de C2 en P1 , adici´on a C3 . pt ^ rq

s $ sÑm

q _ m, p Ñ

n, p _ r, q $ r

A $ B (regla de contradicci´on)

Demostraciones

Una demostraci´on es un argumento deductivo para verificar una proposici´on matem´atica. Veamos dos ejemplos: Definici´ on 1.28. Un n´ umero entero a es par si y s´olo si existe un n´ umero entero m tal que a “ 2m. Un n´ umero entero a es impar si y s´olo si existe un n´ umero entero m tal que a “ 2m ` 1. Proposici´ on 1.29. La suma de dos n´ umeros pares es par. Proposici´ on 1.30. El producto de dos n´ umeros impares es impar.

1.6.

Cuantificadores

Expresiones del tipo ((todos los hombres son mortales)) o ((algunos alumnos de este sal´on tienen menos de 80 a˜ nos)) se pueden traducir en expresiones l´ogicas mediante la ayuda de los cuantificadores.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

14

Cuantificador universal: Cuando todos los elementos del conjunto de estudio satisfacen una propiedad determinada. Empleamos el s´ımbolo @, el cual se lee para todo: @x, P pxq. Lo anterior se puede leer como ((para todo x se cumple P pxq)), ((todos los x satisfacen P pxq)), entre otras expresiones similares. Cuantificador existencial: Cuando al menos un elemento del conjunto de estudio satisface una propiedad determinada. Empleamos el s´ımbolo D, el cual se lee existe: Dx : P pxq. Lo anterior se puede leer como ((existe x tal que P pxq)), ((hay alg´ un x que satisface P pxq)), entre otras expresiones similares. Ejemplo 1.31. Escribir en forma simb´olica los siguientes enunciados1 : 1. Todos los n´ umeros racionales son n´ umeros reales: @x P Q, x P R. 2. Existen n´ umeros racionales menores que 2: Dx P Q : x ă 2. 3. Todos los hombres son mortales: Definimos H el conjunto de hombres y M pxq la propiedad de que x es mortal. Entonces la afirmaci´on quedar´ıa: @x P H, M pxq. Ejercicio 1.32. Escribir en forma simb´olica, en forma de enunciado o responder, seg´ un corresponda: 1. Existen n´ umeros reales que no son racionales: Dx P R : x R Q. 2. El cuadrado de todos los n´ umeros reales es no negativo: @x P R, x2 ě 0. 3. @n P N, n ą 0: Todos los n´ umeros naturales son positivos. ? 4. Dx P Q : π ă x ă 10: Existe al menos un n´ umero racional entre Pi y ra´ız de diez. 5. A algunos mexicanos les gusta el f´ utbol: Definimos M el conjunto de mexicanos y F pxq la propiedad de que a x le gusta el f´ utbol. Entonces la afirmaci´on quedar´ıa: Dx P M : F pxq. 6. A ning´ un mexicano les gusta el f´ utbol: Siguiendo la notaci´on anterior: @x P M, F pxq. ? 7. ¿Es cierto que @n P N, n R Q? 1

Esta secci´ on da por hecho que el lector est´a familiarizado con los conjuntos num´ericos. Para un repaso r´ apido, se puede consultar la secci´on A.1 (p´ag. 66).

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

1.6.1.

15

Negaci´ on

La negaci´on de un cuantificador universal es uno existencial con la propiedad negada. De la misma forma, la negaci´on de un cuantificador existencial es uno universal con la propiedad negada: r@x, P pxqs ô Dx :

P pxq.

rDx : P pxqs ô @x, P pxq. Ejemplo 1.33. . 1. No es verdad que todos los n´ umeros naturales son pares: r@n P N, n es pars ô Dn P N : n no es par. 2. ¿Es cierto que @n P N con 1 ă n ă 14 y n impar, n es primo? No es cierto, pues existe el 9 que no es primo. 3. No a todos los mexicanos les gusta el f´ utbol. r@x P M, F pxqs ô Dx P M :

F pxq

es decir, existen mexicanos que no les gusta el f´ utbol. 4. ¿Cu´al es la negaci´on de la oraci´on ((si todos estudian, entonces nadie reprueba))? Todos estudian y alguien reprueba. 5. ¿Es cierto que a todas las personas de 140 a˜ nos les gustan los xoconostles? 6. Si S es el conjunto de estudiantes de este sal´on, ppxq es ((x repasa en casa)) y qpxq es ((x aprueba sus materias)), ¿qu´e significa @x P S, ppxq ^ qpxq? ¿Cu´al ser´ıa su negaci´on?

1.6.2.

Cuantificadores anidados

Son de la forma: @x, Dy : P px, yq. Dx : @y, P px, yq. Observaci´ on 1.34. Los cuantificadores @x, @y, P px, yq y Dx : Dy : P px, yq en realidad suelen denotarse como @x, y, P px, yq y Dx, y : P px, yq, respectivamente. Ejemplo 1.35. . 1. Todos los n´ umeros pares se pueden escribir de la forma 2m para alg´ un n´ umero entero m: @n par, Dm P Z : n “ 2m. ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata) 2. Todos aman a alguien: @x, Dy : x ama a y. 3. Existe un n´ umero natural que divide a todos los n´ umeros enteros: Dn P N : @z P Z, n divide a z. 4. @x P R, Da P Z : a ď x ă a ` 1. 5. @x P R, ε ą 0, Dq P Q : x ă q ă x ` ε.

¡Material en construcci´on! (versi´on: 2018.04.19)

16

Cap´ıtulo 2 Conjuntos Un conjunto es una colecci´on de objetos. Ejemplo 2.1. Las siguientes son descripciones de conjuntos. 1. El conjunto A de objetos en mi mochila, en este momento. 2. B “ t´arbol, ave, zapato, chancletau 3. C “ t1, 3, 5, 7, 9u

(forma expl´ıcita)

4. C “ tn P N | n es un n´ umero d´ıgito imparu

(forma descriptiva)

5. D “ tn P Z | n es un n´ umero d´ıgitou 6. D “ t0, 1, 2, . . . , 9u

(forma expl´ıcita abreviada)

7. E “ t11, 12, 13, . . . u 8. E “ tn P N | n ą 10u 9. F “ tx P R | x2 ´ 3x ` 2 “ 0u 10. F “ t1, 2u

2.1.

Relaci´ on de pertenencia

Sea A un conjunto y a un elemento de A, entonces se dice que ((a pertenece a A)) y se escribe a P A. Si b no pertenece a A escribimos b R A.

17

Matem´aticas discretas (M. Mata)

2.2.

18

Subconjuntos e igualdad

Definici´ on 2.2. Sean A y B dos conjuntos, se dice que A es un subconjunto de B, y se escribe A Ď B, si y s´olo si todos los elementos de A pertenecen a B. Tambi´en, si A Ď B, se dice que B contiene a A y se escribe B Ě A. Ejemplo 2.3. Sean A “ t7, 17u y B “ t1, 3, 5, . . . , 99u, entonces A Ď B. Ejercicio 2.4. Sean A “ t1, 2u y B “ tx P R | x2 ´ 3x ` 2 “ 0u, ¿A Ď B? Observaci´ on 2.5. Si A Ď B, entonces: x P A ñ x P B. Tambi´en, si A Ď B, entonces: @x P A, x P B. ¿Cu´al es la negaci´on de A Ď B? Se dice que A no es subconjunto de B, o que B no contiene a A, si existe a P A tal que a R B, y se escribe AĎB. { Ejemplo 2.6. Sean A “ tn P Z | n es paru y B “ tn P Z | n es m´ ultiplo de seisu. Demuestre que B Ď A. (Recuerde que n es m´ ultiplo de k si existe m P Z tal que n “ km). Ejercicio 2.7. Sean A “ tn P N | 1 ă n ă 14, n es imparu y B “ tn P N | n ď 13, n es primou. ¿A Ď B o B Ď A? Definici´ on 2.8. Sean A y B dos conjuntos, se dice que A es igual a B, y se escribe A “ B, si y s´olo si A Ď B y B Ď A. Ejercicio 2.9. Sean A “ tx P R | x4 ´ 2x3 ´ x2 ` 2x “ 0u y B “ tx P Z | ´1 ď x ď 2u, ¿A “ B? Definici´ on 2.10. En caso de que A Ď B pero A ‰ B, se dice que A es subconjunto propio de B y se escribe A Ă B. Notaci´ on 2.11. Algunos autores escriben simplemente A Ă B cuando A es subconjunto de B, pero deben escribir A Ł B cuando A es subconjunto propio de B.

2.3.

Conjunto universal y conjunto vac´ıo

No existe un conjunto que contenga a todos los objetos. En cualquier aplicaci´on de la teor´ıa de conjuntos, todos los posibles conjuntos a investigar se consideran subconjuntos de un conjunto dado. Llamamos a ese conjunto el conjunto universal. En nuestro estudio lo denotaremos por U . Ejemplo 2.12. . ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

19

1. En geometr´ıa, U es el plano. 2. En estudios poblacionales, U es toda la gente del mundo. Por otra parte, en ocasiones deberemos estudiar conjuntos que no tienen ning´ un elemento. Dicho conjunto es llamado conjunto vac´ıo y lo denotamos por ∅. Ejemplo 2.13. . 1. A “ tn P Z | n2 “ 16, n es imparu “ ∅. 2. B “ tx P R | x2 ` 1 “ 0u “ ∅. 3. Sea C el conjunto de personas de m´as de 140 a˜ nos. ¿C “ ∅? Ejercicio 2.14. Demuestre que, si A es un conjunto cualquiera, ∅ Ď A.

2.4.

Cardinalidad

Dado A un conjunto, se define la cardinalidad de A, y se denota |A|, como la cantidad de elementos que pertenecen a A. Ejemplo 2.15. . 1. Dado A “ ta, e, i, o, uu, |A| “ 5. 2. Dado B el conjunto de las letras del alfabeto espa˜ nol, ¿cu´anto vale |B|? 3. Dado C el conjunto de consonantes del alfabeto espa˜ nol, ¿cu´anto vale |C|? Ejercicio 2.16. . 1. Si S “ ∅, ¿cu´anto vale |S|? 2. ¿Cu´al es la cardinalidad de N? 3. Si A Ď B, ¿|A| ď |B|? 4. Si A Ă B, ¿|A| ă |B|?

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

2.5.

20

Conjunto potencia

Ejercicio 2.17. Sea S “ ta, b, cu, escribir todos sus posibles subconjuntos. Definici´ on 2.18. El conjunto de todos los posibles subconjuntos de un conjunto A es llamado conjunto potencia de A, y se denota por PpAq. Ejemplo 2.19. Sea S “ ta, b, cu, entonces PpSq “ t∅, tau, tbu, tcu, ta, bu, ta, cu, tb, cu, Su. Ejercicio 2.20. Si A es un conjunto finito con n elementos, ¿cu´antos elementos tiene el conjunto PpAq? Ejercicio 2.21. Escribir Pp∅q. Observe que t∅u ‰ ∅.

2.6. 2.6.1.

Operaciones con conjuntos Uni´ on

Definici´ on 2.22. La uni´on de dos conjuntos A y B, expresada por A Y B, es el conjunto de todos los elementos que pertenecen a A o a B: A Y B “ tx | x P A _ x P Bu.

2.6.2.

Intersecci´ on

Definici´ on 2.23. La intersecci´on de dos conjuntos A y B, expresada por A X B, es el conjunto de todos los elementos que pertenecen a A y a B: A X B “ tx | x P A ^ x P Bu.

2.6.3.

Diferencia

Definici´ on 2.24. La diferencia entre dos conjuntos A y B, expresada por AzB, es el conjunto de todos los elementos que pertenecen a A pero que no pertenecen a B: AzB “ tx | x P A ^ x R Bu.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

2.6.4.

21

Complemento

Definici´ on 2.25. El complemento de un conjunto A, expresado por Ac , es el conjunto de todos los elementos que no pertenecen a A: Ac “ tx | x P U ^ x R Au. Ejercicio 2.26. Sea U “ t0, 1, 2, 3, . . . , 13u. Calcular: 1. A “ tx P U | x es paru 2. B “ tx P U | x es m´ ultiplo de 3u 3. C “ tx P U | x es primou 4. Ac Y C 5. B c X C 6. CzA 7. AzC 8. BzpA Y Cq Ejemplo 2.27. Demostrar (por las definiciones) que: 1. pA X Bqc “ Ac Y B c Demostraci´on. pA X Bqc “ tx | x P U ^ x R A X Bu

por definici´on del complemento,

“ tx | x P U ^ px P A X Bqu

por notaci´on,

“ tx | x P U ^ px P A ^ x P Bqu

por definici´on de la intersecci´on,

“ tx | x P U ^ p x P A _ x P Bqu

por ley de De Morgan,

“ tx | x P U ^ px R A _ x R Bqu

por notaci´on,

“ tx | px P U ^ x R Aq _ px P U ^ x R Bqu por distributividad, “ tx | x P Ac _ x P B c u c

“A YB

c

por definici´on del complemento, por definici´on de la uni´on.

2. BzA “ B X Ac

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

22

Demostraci´on. BzA “ tx | x P B ^ x R Au “ tx | x P B ^ x P U ^ x R Au “ tx | x P B ^ x P Ac u “ B X Ac

2.6.5. 1 2 3 4 5 6 7 8 9

por definici´on de la diferencia, porque A Ď U y B Ď U , por definici´on del complemento, por definici´on de la intersecci´on.

Propiedades de los conjuntos AYA“A AXA“A AYB “BYA AXB “BXA A Y pB Y Cq “ pA Y Bq Y C A X pB X Cq “ pA X Bq X C A Y pB X Cq “ pA Y Bq X pA Y Cq A X pB Y Cq “ pA X Bq Y pA X Cq pA Y Bqc “ Ac X B c pA X Bqc “ Ac Y B c pAc qc “ A A Y Ac “ U A X Ac “ ∅ AY∅“A AXU “A AYU “U AX∅“∅

Leyes idempotentes Leyes conmutativas Leyes asociativas Leyes distributivas Leyes de De Morgan Ley de involuci´on Leyes de complementaci´on Leyes de identidad Leyes de dominaci´on

Ejercicio 2.28. Demostrar, por medio de las propiedades, que: 1. pAzBqc “ Ac Y B. 2. A Y pA X Bq “ A. 3. pAzBq X B “ ∅. 4. A X pBzCq “ pA X BqzpA X Cq.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

2.6.6.

23

Propiedades de las cardinalidades

1. |∅| “ 0. 2. Si A Ď B, entonces |A| ď |B|. 3. |A Y B| “ |A| ` |B| ´ |A X B|. Ejemplo 2.29. Demostrar por medio de las propiedades anteriores que: 1. Si A “ B, entonces |A| “ |B|. 2. Si A X B “ ∅, entonces |A Y B| “ |A| ` |B|. 3. |A Y B| ě m´axt|A|, |B|u. 4. |A Y B Y C| “ |A| ` |B| ` |C| ´ |A X B| ´ |A X C| ´ |B X C| ` |A X B X C|. Ejercicio 2.30. Demostrar por medio de las propiedades anteriores que: 1. |A X B| ď m´ınt|A|, |B|u. 2. |A| ` |Ac | “ |U |

(sugerencia: observe queA Y Ac “ U y A X Ac “ ∅).

3. |AzB| “ |A| ´ |A X B|.

2.7.

Diagramas de Venn

Propuestos por John Venn (1834-1923) para c´alculos l´ogicos, en la actualidad se emplean para representar gr´aficamente los conjuntos y sus relaciones. U A

B

Figura: Representaci´ on de dos conjuntos mediante un diagrama de Venn.

Ejemplo 2.31. Representar mediante el diagrama de Venn las siguientes condiciones: 1. A y B no se intersectan

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

24

2. A Ď B Ejemplo 2.32. Representar mediante el diagrama de Venn los siguientes conjuntos: 1. A Y B 2. A X B 3. Ac 4. Ac X B Ejercicio 2.33. Verificar mediante un diagrama de Venn: A Ď B ñ A X B “ A.

2.7.1.

Conteo mediante diagramas de Venn

Ejemplo 2.34. En una empresa trabajan 20 personas de las cuales 13 son casadas y 11 son profesionistas; de las profesionistas 5 no son casadas. ¿Cu´antas personas no son casadas ni profesionistas, y cu´antas son casadas y profesionistas? R = Dos y seis. Ejercicio 2.35. En una encuesta a 200 alumnos se encontr´o que 68 tienen excelente conducta, 138 son inteligentes, 160 son muy sociables, 120 son muy sociables e inteligentes, 20 tienen excelente conducta pero no son inteligentes, 13 tienen excelente conducta pero no son muy sociables, y 15 tienen excelente conducta, son muy sociables y no son inteligentes. Identificar en un diagrama de Venn.

¡Material en construcci´on! (versi´on: 2018.04.19)

Cap´ıtulo 3 Alfabetos, cadenas y lenguajes 3.1.

Alfabetos

Definici´ on 3.1. Un alfabeto es un conjunto finito no vac´ıo de elementos que llamaremos s´ımbolos. Notaci´ on 3.2. En teor´ıa de computaci´on se suele denotar con Σ a un alfabeto cualquiera. Ejemplo 3.3. Determinar si los siguientes son alfabetos: 1. Sea Σ el conjunto de letras, tanto may´ usculas como min´ usculas, del idioma espa˜ nol. 2. Sea Γ el conjunto de letras, tanto may´ usculas como min´ usculas, del idioma griego. 3. Sea A “ ta, b, c, du. 4. Sea B “ t0, 1u. 5. Sea Σ “ N. Ejercicio 3.4. Investigar sobre los siguientes alfabetos: 1. ASCII. 2. ISO 8859-1 (Lat´ın 1). 3. UTF-8. 25

Matem´aticas discretas (M. Mata)

3.2.

26

Cadenas

Definici´ on 3.5. Una cadena o palabra sobre un alfabeto A es una secuencia finita de elementos de A. Ejemplo 3.6. . 1. Sea A “ ta, b, c, du, las siguientes son tres posibles cadenas sobre A: babc, dcbbbbad y a. 2. Sea B “ t0, 1u, las siguientes son posibles cadenas sobre B: 10010, 001, 10 y 01. Observaci´ on 3.7. En las cadenas el orden de los s´ımbolos es importante, de tal manera que aab ‰ aba. Notaci´ on 3.8. Las repeticiones de un elemento se pueden denotar con un super´ındice. Por ejemplo, baaaccbbbd puede escribirse como ba3 c2 b3 d. Definici´ on 3.9. La cadena sin elementos se llama cadena nula y se denota por λ. Definici´ on 3.10. Sea A un alfabeto, se define A˚ como el conjunto de todas las posibles cadenas sobre A, incluyendo la cadena nula. Ejercicio 3.11. Responder lo siguiente: 1. Si A es un conjunto finito, ¿A˚ es finito? 2. Sea A “ tau, ¿cu´al es el conjunto A˚ ? Definici´ on 3.12. La longitud de una cadena β, denotada por |β|, es el n´ umero de s´ımbolos que conforman β. Ejercicio 3.13. Calcular la longitud de las siguientes cadenas: 1. β “ aabcad 2. β “ 015 08 1 3. λ ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

3.2.1.

27

Concatenaci´ on

Definici´ on 3.14. Sea A un alfabeto y sean α y β dos cadenas sobre A, la concatenaci´on de α con β es la cadena formada por α seguida de β, y se escribe αβ. Observaci´ on 3.15. Observe que la concatenaci´on de α con β tambi´en es una cadena sobre A. Ejercicio 3.16. . 1. Sean α “ aab y β “ acad, escribir αβ y βα. 2. Sea γ “ 0110, escribir λγ y γλ. 3. Sean ε “ x10 z 9 y 13 y δ “ y 8 x7 , escribir εδ y δε. Ejercicio 3.17. . 1. Si α P A˚ y β P B ˚ , ¿a qu´e conjunto pertenece αβ? 2. Si |α| “ n y |β| “ m, ¿cu´al es el valor de |αβ|?

3.2.2.

Subcadenas, prefijos y sufijos

Definici´ on 3.18. Se dice que una cadena α es una subcadena de la cadena β si y s´olo si existen dos cadenas γ y δ tales que β “ γαδ. Ejercicio 3.19. . 1. En los siguientes casos, decir si α es una subcadena β. a) α “ ab y β “ cabad. b) α “ 011 y β “ 001011. 2. Dado β “ x10 z 9 y 13 , ¿cu´ales de las siguientes son una subcadena de β? a) α1 “ x2 y 3 . b) α2 “ x10 z 10 . c) α3 “ zy. Ejercicio 3.20. Demostrar que toda cadena es subcadena de s´ı misma. Definici´ on 3.21. Se dice que una cadena α es un prefijo de la cadena β si y s´olo si existe una cadena δ tal que β “ αδ. Similarmente, se dice que una cadena α es un sufijo de la cadena β si y s´olo si existe una cadena γ tal que β “ γα. Ejercicio 3.22. Demostrar que los prefijos y sufijos son subcadenas. ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

3.2.3.

28

Potencia de una cadena

Definici´ on 3.23. Dados β P A˚ y n P N, se define β n como la concatenaci´on de β reiterada n veces: β n “ βββ ¨¨¨β . loooomoooon n veces

Notaci´ on 3.24. Por convenci´on, suele definirse β 0 “ λ. Ejercicio 3.25. Sea β una cadena, demuestre las siguientes: 1. β n β m “ β n`m . 2. |β n | “ n|β|. 3. |β n`m | “ |β n | ` |β m |.

3.2.4.

Reflexi´ on de una cadena

Definici´ on 3.26. La reflexi´on de una cadena β es la cadena formada por los mismos s´ımbolos dispuestos en orden inverso y se denota β R . Ejemplo 3.27. Sea β “ f ime, entonces β R “ emif . Notaci´ on 3.28. Algunos autores denotan la cadena inversa con β ´1 . Ejercicio 3.29. Demuestre que pαβqR “ β R αR .

3.3.

Lenguajes

Definici´ on 3.30. Un lenguaje L sobre un alfabeto Σ es un subconjunto de Σ˚ . Observaci´ on 3.31. Todo lenguaje L cumple que ∅ Ď L Ď Σ˚ , y puede ser finito o infinito. Ejemplo 3.32. Sean: Σ “ ta, b, c, . . . , z, ´a, ´e, ´ı, o´, u ´, u ¨u Σ˚ “ tλ, a, ´a´en ˜yz, r´otulo, . . . u L “ tβ P Σ˚ |β est´a en el diccionario de la RAEu ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

29

Ejemplo 3.33. Sea Σ los s´ımbolos del alfabeto cir´ılico y L el conjunto de palabras legales del idioma ruso. Ejemplo 3.34. Sea Σ el c´odigo ASCII y L el conjunto de palabras reservadas del lenguaje C (por ejemplo, main, int, if, else, while, for, return, etc´etera).

3.3.1.

Operaciones entre lenguajes

Dado que los lenguajes son conjuntos, todas las operaciones de conjuntos pueden aplicarse a ellos. Ejemplo 3.35. Sean A y B dos lenguajes sobre Σ, entonces los siguientes tambi´en son lenguajes: 1. A Y B. 2. A X B. 3. AzB. 4. Ac “ Σ˚ zA.

3.3.2.

Concatenaci´ on de lenguajes

Definici´ on 3.36. Dados dos lenguajes A y B, la concatenaci´on de A con B, denotada por AB, se define como AB “ tαβ | α P A, β P Bu . Observaci´ on 3.37. Observe que, en general, AB ‰ BA.

3.3.3.

Reflexi´ on de un lenguaje

Definici´ on 3.38. Dado L un lenguaje, la reflexi´on de L, denotada por LR , se define como LR “ tβ R | β P Lu . Ejercicio 3.39. Sean A y B dos lenguajes sobre Σ, decir si las siguientes afirmaciones son verdaderas: ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata) 1. pABqR “ B R AR . 2. pA Y BqR “ AR Y B R . 3. pA X BqR “ AR X B R . 4. pAR qR “ A.

¡Material en construcci´on! (versi´on: 2018.04.19)

30

Cap´ıtulo 4 Producto cartesiano y matrices 4.1. 4.1.1.

Producto cartesiano Pares ordenados

Un par ordenado o pareja ordenada es una asociaci´on de dos elementos a y b tales que el primer elemento es a y el segundo es b. El par ordenado se escribe pa, bq. Definici´ on 4.1. Formalmente, un par ordenado se define mediante el siguiente conjunto: pa, bq “ ttau, ta, buu. La definici´on anterior se debe a Kuratowski (1896-1980). Ejemplo 4.2. . 1. Observe que p2, 3q ‰ p3, 2q. 2. De hecho pa, bq “ pc, dq si y s´olo si a “ c y b “ d. 3. Ambos elementos del par ordenado puede ser el mismo: pa, aq.

4.1.2.

Conjunto producto

Definici´ on 4.3. Sean A y B dos conjuntos, el conjunto producto o producto cartesiano de A y B, denotado por A ˆ B, consta de todos los pares ordenados pa, bq tales que a es elemento de A y b es elemento de B, esto es: A ˆ B “ tpa, bq | a P A ^ b P Bu.

31

Matem´aticas discretas (M. Mata)

32

Notaci´ on 4.4. Al producto cartesiano de un conjunto A con s´ı mismo, es decir A ˆ A, lo denotamos tambi´en por A2 .

Ejercicio 4.5. . 1. Sean A “ ta, bu y B “ t1, 2, 3u, escribir expl´ıcitamente el conjunto A ˆ B. 2. Si un conjunto A tiene n elementos y un conjunto B tiene m elementos, ¿cu´antos elementos tiene A ˆ B? 3. Sean A “ t0, 1, 2, 3u y B “ t2, 3, 4u, escribir explicitamente el conjunto pA ˆ Bq X pB ˆ Aq.

4.1.3.

Conjunto producto en general

El concepto de producto cartesiano se puede generalizar: Sean A1 , A2 , . . . , An conjuntos, el producto cartesiano de ellos se define por A1 ˆ A2 ˆ ¨ ¨ ¨ ˆ An “ tpa1 , a2 , . . . , an q | a1 P A1 , a2 P A2 , . . . , an P An u donde a cada elemento pa1 , a2 , . . . , an q se le llama n-upla ordenada. De igual manera, dado A un conjunto, An “ tpa1 , a2 , . . . , an q | a1 , a2 , . . . , an P Au.

4.1.4.

Conjuntos de verdad de proposiciones˚

Supongamos que una proposici´on P tiene tres variables p, q y r, cada una de ellas toma un valor de verdad en el conjunto B “ t1, 0u, por lo cual cada posible combinaci´on de valores de verdad puede estar dada por una terna pb1 , b2 , b3 q P B 3 , donde b1 es el valor de verdad de p, b2 el valor de q y b3 el de r. Con lo anterior, todas las posibles combinaciones para evaluar P estar´ıan dadas por B 3 “ tp1, 1, 1q, p1, 1, 0q, p1, 0, 1q, p1, 0, 0q, p0, 1, 1q, p0, 1, 0q, p0, 0, 1q, p0, 0, 0qu. Observaci´ on 4.6. Recordemos que, seg´ un la notaci´on usada, el conjunto de valores de verdad tambi´en puede ser B “ tV, F u o B “ tJ, Ku.

Definici´ on 4.7. El conjunto de verdad de una proposici´on P que contiene n variables proposicionales, denotado por T pP q, est´a formado por aquellos elementos de B n para los cuales la proposici´on P es verdadera.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

33

Ejemplo 4.8. . 1. T pp _ qq “ tp1, 1q, p1, 0q, p0, 1qu. 2. T ppp Ñ qq ^ pq Ñ rqq “ tp1, 1, 1q, p0, 1, 1q, p0, 0, 1q, p0, 0, 0qu. Ejercicio 4.9. . 1. T pp Ø qq. 2. T p pq. 3. Es evidente que siempre T pP q Ď B n pero, ¿puede T pP q “ B n ? 4. ¿Existe la posibilidad de que T pP q “ ∅? Teorema 4.10. Sean P y Q proposiciones. Entonces: 1. T pP _ Qq “ T pP q Y T pQq. 2. T pP ^ Qq “ T pP q X T pQq. 3. T p P q “ T pP qc . 4. P ñ Q si y s´olo si T pP q Ď T pQq.

4.2.

Matrices

Definici´ on 4.11. Una matriz de m ˆ n es un arreglo rectangular de elementos de un conjunto (normalmente num´erico) de la forma ¨ ˛ a11 a12 a13 ¨ ¨ ¨ a1n ˚ a21 a22 a23 ¨ ¨ ¨ a2n ‹ ‹ ˚ ˚ .. .. .. .. ‹ . . ˝ . . . . . ‚ am1 am2 am3 ¨ ¨ ¨

amn

Notaci´ on 4.12. Una matriz m ˆ n, A, es usualmente denotada por paij q, donde cada aij es el elemento situado en la i-´esima fila y la j-´esima columna de A. Ejemplo 4.13. Considere la matriz 2 ˆ 3 ˆ ˙ 1 ´3 5 A“ ? 2 0 ´2 ? donde, por ejemplo, a21 “ 2 y a13 “ 5. Observaci´ on 4.14. Observe la estrecha relaci´on que hay entre una matriz y el producto cartesiano. De hecho, cuando cada uno de los elementos de la matriz m ˆ n, A, est´an en un conjunto F, se suele denotar A P Fmˆn . ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

4.2.1.

34

Matriz traspuesta

Definici´ on 4.15. La traspuesta de una matriz m ˆ n, A, denotada por At , es la matriz n ˆ m tal que el elemento aij de At es igual al elemento aji de A, es decir, ¨ ˛ ¨ ˛t a11 a21 ¨ ¨ ¨ am1 a11 a12 a13 ¨ ¨ ¨ a1n ˚ a12 a22 ¨ ¨ ¨ am2 ‹ ˚ ‹ ˚ a21 a22 a23 ¨ ¨ ¨ a2n ‹ ˚ ‹ ˚ a13 a23 ¨ ¨ ¨ am3 ‹ ˚ .. ‹ .. .. .. ‹ “ ˚ .. ˝ . . .. .. .. ‹ . . . ‚ ˚ . . ˝ . . . . ‚ am1 am2 am3 ¨ ¨ ¨ amn a1n a2n ¨ ¨ ¨ amn Observaci´ on 4.16. Observe que pAt qt “ A.

4.2.2.

Matrices cuadradas

Definici´ on 4.17. Una matriz se dice que es cuadrada si y s´olo si tiene la misma cantidad de filas que de columnas, es decir si es de dimensi´on n ˆ n.

4.2.3.

Matriz diagonal y matriz identidad

Definici´ on 4.18. Se define la diagonal principal de una matriz cuadrada a los elementos de la forma aii , es decir, a los elementos a11 , a22 , . . . , ann . Definici´ on 4.19. Una matriz cuadradad paij q se dice que es diagonal si y s´olo si los elementos que no pertenecen a la diagonal principal son cero, es decir, aij “ 0 si i ‰ j. Ejercicio 4.20. Cu´ales de ¨ 5 ˚0 A“˚ ˝0 0 ¨ 3 0 ˝ C “ 0 ´8 0 0

las siguientes son matrices diagonales: ˛ ¨ ˛ 0 0 6 0 0 0 ‹ 3 0 0‹ B “ ˝0 0 0 ‚ 0 ´2 0‚ 0 0 ´1 0 0 1 ˛ ˙ ˆ 0 0 ` ˘ π ?0 ‚ 0 0 E“ 4 D“ 3 0 ´2 0

Definici´ on 4.21. Se define la matriz identidad, y se denota In como la matriz diagonal n ˆ n cuyos elementos de la diagonal principal son todos 1. Ejemplo 4.22. La matriz identidad 3 ˆ 3: ¨ ˛ 1 0 0 I3 “ ˝0 1 0‚ 0 0 1 ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

4.2.4.

35

Matriz sim´ etrica

Definici´ on 4.23. Se dice que una matriz cuadrada paij q es sim´etrica si y s´olo si todos sus elementos cumplen que aij “ aji . Ejemplo 4.24. La siguiente es una matriz sim´etrica: ¨ ˛ 3 4 ´5 8 ˚ 4 1 0 3‹ ˚ ‹ ˝´5 0 ´1 2 ‚ 8 3 2 12 Observaci´ on 4.25. Una matriz A es sim´etrica si y s´olo si A “ At .

4.2.5.

Matrices triangulares

Se dice que una matriz cuadrada es triangular si todos sus elementos por encima o por debajo de la diagonal principal son cero. Definici´ on 4.26. Se dice que una matriz cuadrada paij q es triangular superior si y s´olo aij “ 0 para i ą j. Definici´ on 4.27. Se dice que una matriz cuadrada paij q es triangular inferior si y s´olo aij “ 0 para i ă j. Ejemplo 4.28. La siguientes son respectivamente: ¨ 3 0 0 ˚4 7 0 A“˚ ˝5 0 1 9 3 2

una matrices triangulares inferior y superior, ˛ ¨ 0 1 4 ˚0 2 0‹ ‹ B“˚ ˝0 0 0‚ 6 0 0

5 3 1 0

˛ 8 0‹ ‹ 2‚ 6

Observaci´ on 4.29. Si una matriz A es diagonal, entonces es triangular inferior y triangular superior. Observaci´ on 4.30. Si una matriz A es triangular superior (inferior), entonces t A es una matriz triangular inferior (superior).

4.2.6.

Operaciones entre matrices*

Las matrices se pueden sumar y multiplicar entre s´ı, bajo ciertas condiciones, se puede multiplicar una matriz por un escalar y se pueden transformar por medio de operaciones elementales, pero todas estas operaciones escapan al enfoque de ´ este material de estudio. Dicha teor´ıa puede leerse en cualquier texto de Algebra Lineal. ¡Material en construcci´on! (versi´on: 2018.04.19)

Cap´ıtulo 5 Relaciones y funciones 5.1.

Relaciones

Definici´ on 5.1. Sean A y B dos conjuntos, una relaci´on R definida del conjunto A al conjunto B es un subconjunto de A ˆ B. Ejemplo 5.2. . 1. Sean A “ ta, b, cu, B “ t1, 2, 3u y R “ tpa, 2q, pa, 3q, pb, 3qu 2. Sean A “ t1, 2, 3, 4u, B “ t3, 4, 5, 6, 7, 8u y R “ tpa, bq P A ˆ B | b “ 2au. 3. Sean A “ t1, 2, 3u y R “ tpa, bq P A2 | a ă bu. Cuando una relaci´on R est´a definida del conjunto A al conjunto A, es decir, cuando R Ď A2 , se dice simplemente que R est´a definida sobre A. Notaci´ on 5.3. Algunos autores usan la siguiente notaci´on: si pa, 2q P R denotan a R 2 y se lee ((a est´a en relaci´on con 2)) o ((a se relaciona con 2)); tambi´en, si { 1 y se lee ((b no est´a en relaci´on con 1)) o ((b no se relaciona pb, 1q R R denotan b R con 1)). Este es un abuso de notaci´on, puesto que entonces R es, al mismo tiempo, un subconjunto de A ˆ B y un operador binario entre los elementos de A y B, pero, salvo por el rigor, no suele haber oposici´on en su uso, puesto que no hay peligro de ambig¨ uedad.

5.1.1.

Representaci´ on gr´ afica de una relaci´ on

Una relaci´on puede representarse gr´aficamente en un sistema de coordenadas cartesiano o por medio de un grafo.

36

Matem´aticas discretas (M. Mata)

37

Ejemplo 5.4. Dados A “ t1, 2, 3u, B “ ta, b, cu y la relaci´on de A a B dada por R “ tp1, aq, p1, bq, p2, aq, p2, cq, p3, cqu. La representaci´on gr´afica de R, tanto en forma cartesiana como en forma de grafo, ser´ıa: c b a 1

2

3

1

a

2

b

3

c

Ejemplo 5.5. Dado A “ t1, 2, 3, 4u y la relaci´on definida sobre A definida por R “ tp1, 2q, p1, 4q, p3, 3q, p4, 1q, p4, 2qu. La representaci´on de R en un grafo se puede hacer replicando el conjunto A, resultando un ((gr´afico bipartito)) como el del caso anterior, pero tambi´en se puede usar el conjunto A una u ´nica vez, resultando un ((gr´afico dirigido)). 4 3

1

1

2

2

3

3

4

4

1

2

4

3

2 1 1

2

3

4

Ejercicio 5.6. Dados A “ t1, 2, 3, 4, 5u y R “ tpa, bq P A2 | a ď bu. Hacer su representaci´on gr´afica.

5.1.2.

Representaci´ on matricial de una relaci´ on

Dados A “ ta1 , a2 , . . . , am u y B “ tb1 , b2 , . . . , bn u dos conjuntos y R una relaci´on de A a B, entonces R se puede representar por una matriz m ˆ n, prij q, de tal manera que # 1 si pai , bj q P R, rij “ 0 si pai , bj q R R. Ejemplo 5.7. Dados A “ t1, 2, 3u, B “ ta, b, c, du y la relaci´on de A a B dada por R “ tp1, aq, p1, bq, p2, aq, p2, cq, p3, cq, p3, dqu. La representaci´on matricial de R es: ¨ ˛ 1 1 0 0 R “ ˝1 0 1 0‚ 0 0 1 1 Ejercicio 5.8. Dado A “ t1, 2, 3, 4u y la relaci´on definida sobre A definida por R “ tp1, 2q, p1, 4q, p3, 3q, p4, 1q, p4, 2qu. Encontrar la representaci´on matricial de R. ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

5.1.3.

38

Dominio y rango de una relaci´ on

Definici´ on 5.9. Dada una relaci´on R de A a B, el dominio y el rango de R est´an definidos por: Dom R :“ ta P A | Db P B, pa, bq P Ru, Ran R :“ tb P B | Da P A, pa, bq P Ru.

Ejemplo 5.10. Sean A “ t1, 2, 3, 4u, B “ t3, 4, 5, 6, 7, 8u y R “ tpa, bq P A ˆ B | b ă 2au. Encontrar Dom R y Ran R. Ejercicio 5.11. Si R es una relaci´on de A a B, diga si las siguientes afirmaciones son verdaderas o falsas: 1. Dom R “ A

4. Dom R Ă A

7. Ran R Ă B

2. Dom R Ď B

5. Ran R “ B

8. Ran R Ď B

3. Dom R Ď A

6. Ran R Ď A

9. Ran R Ď Dom R

Notaci´ on 5.12. Algunos autores dan otros nombres al rango de R, como contradominio, imagen o recorrido. Por la misma raz´on, al conjunto Ran R lo denotan de otra manera, por ejemplo Im R.

5.1.4.

Relaci´ on inversa

Definici´ on 5.13. Sea R una relaci´on de A a B, la inversa de R, representada por R´1 , es una relaci´on de B a A que se define como sigue: R´1 “ tpb, aq | pa, bq P Ru.

Ejemplo 5.14. . 1. R “ tp1, 2q, p1, 3q, p2, 3qu. R´1 “ tp2, 1q, p3, 1q, p3, 2qu. 2. Sea A el conjunto de alumnos del sal´on y R definida sobre A como sigue: R “ tpa, bq | a es m´as alto que bu, entonces R´1 “ tpb, aq | b es m´as bajo que au. 3. Sea R “ tpp, qq P Q2 | q “ 3p ` 2u, entonces R´1 “ tpq, pq P Q2 | p “ pq ´ 2q{3u. Ejercicio 5.15. Sea R “ tp1, 2q, p1, 3q, p2, 1q, p2, 3qu: ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

39

1. Expresar R´1 . 2. Hacer la representaci´on matricial de R y de R´1 . 3. ¿Es posible establecer alguna relaci´on entre las representaciones matriciales de R y de R´1 ?

5.2.

Relaciones de equivalencia y relaciones de orden

Definici´ on 5.16. Sea R una relaci´on sobre A: 1. Se dice que R es reflexiva si y s´olo si para todo a P A, pa, aq P R. 2. Se dice que R es transitiva si y s´olo si se cumple que, si pa, bq P R y pb, cq P R, entonces pa, cq P R. 3. Se dice que R es sim´etrica si y s´olo si se cumple que, si pa, bq P R, entonces pb, aq P R. 4. Se dice que R es antisim´etrica si y s´olo si se cumple que, si pa, bq P R y a ‰ b, entonces pb, aq R R. Ejercicio 5.17. Para cada una de las relaciones siguientes, diga si es reflexiva, transitiva, sim´etrica o antisim´etrica. 1. R “ tp1, 2q, p1, 3q, p2, 3qu. 2. R “ tpa, bq P Z | a ě bu. 3. Sea A el conjunto de alumnos del sal´on y R definida sobre A de tal forma que a R b si y s´olo si a es amigo de b. Ejercicio 5.18. Sea R una relaci´on sobre A. Decir si la representaci´on matricial de R tiene alguna caracter´ıstica en cada caso: 1. Si R es reflexiva. 2. Si R es transitiva. 3. Si R es sim´etrica. 4. Si R es antisim´etrica.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

5.2.1.

40

Relaciones de orden

Definici´ on 5.19. Sea R una relaci´on sobre A, se dice que R es una relaci´on de orden si y s´olo si R es reflexiva, transitiva y antisim´etrica. Ejemplo 5.20. Precisamente en los conjuntos num´ericos, las relaciones ((menor o igual)) (ď) y ((mayor o igual)) (ě) son relaciones de orden. Se llaman as´ı porque definen un orden (de menor a mayor o viceversa) entre los elementos del conjunto.

5.2.2.

Relaciones de equivalencia

Definici´ on 5.21. Sea R una relaci´on sobre A, se dice que R es una relaci´on de equivalencia si y s´olo si R es reflexiva, transitiva y sim´etrica. Ejemplo 5.22. Sea Pn rxs el conjunto de los polinomios de grado menor o igual a n. Sean ppxq y qpxq dos polinomios en Pn rxs y sea R la relaci´on que se define mediante la regla ((ppxq R qpxq si y s´olo si ppxq y qpxq tienen el mismo grado)). Entonces R es una relaci´on de equivalencia. Ejemplo 5.23. Sea n P N, para cada a P Z se define a m´odulo n como el valor r tal que a “ npkq ` r, con 0 ď r ă n y k P Z, y se denota a m´od n “ r. Observe que, en el caso de los n´ umeros positivos, r es el residuo que queda al dividir a entre n. Se dice que p es congruente a q m´odulo n, y se denota p ” q pm´od nq, si y s´olo si p ´ q m´od n “ 0. La relaci´on ((p R q si y s´olo si p ” q pm´od nq)) es una relaci´on de equivalencia.

5.2.3.

Particiones

Definici´ on 5.24. Una partici´on de un conjunto X es una divisi´on de los elementos de X de tal manera que cada elemento pertenece s´olo una parte de la divisi´on. Formalmente, tX1 , X2 , X3 , . . . , Xn u es una partici´on de X si y s´olo si X “ X1 Y X2 Y ¨ ¨ ¨ Y Xn y para cada par de conjuntos Xi y Xj (con i ‰ j) se cumple que Xi X Xj “ ∅. Nomenclaura 5.25. Dos conjuntos que cumplen que Xi X Xj “ ∅ se llaman disjuntos. Ejemplo 5.26. Sea X “ t1, 2, 3, 4, 5, 6u, la siguiente es una partici´on: tt1, 2, 4u, t3, 5u, t6uu. Ejemplo 5.27. Sea X el intervalo cerrado r0, 1s, ¿cu´ales de las siguientes es una partici´on de X?: ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

41

1. tr0, 21 s, r 12 , 1su 2. tr0, 21 q, r 12 , 1su 3. tr0, 21 s, p 12 , 1su 4. tr0, 21 q, p 12 , 1su

5.2.4.

Relaciones de equivalencia y particiones

Definici´ on 5.28. Sea R una relaci´on de equivalencia sobre A. Para un elemento a P A se define la clase de equivalencia de a, y se denota ras, como el conjunto de todos los elementos de A que se est´an relacionados con a, es decir: ras “ tx | pa, xq P Ru.

Ejemplo 5.29. Sea A “ t1, 2, 3, 4, 5, 6u y R “ tp1, 1q, p1, 2q, p1, 4q, p2, 1q, p2, 2q, p2, 4q, p3, 3q, p3, 5q, p4, 1q, p4, 2q, p4, 4q, p5, 3q, p5, 5q, p6, 6qu. ¿Es R una relaci´on de equivalencia? Ejercicio 5.30. En el ejemplo anterior calcular r1s, r2s, r3s, . . . , r6s. Observaci´ on 5.31. Las clases de equivalencia ras son subconjuntos de A. Teorema 5.32. Sea R una relaci´on de equivalencia sobre A. Entonces el conjunto S de las clases de equivalencia son una partici´on de A. Es decir: S “ tras | a P Au es una partici´on de A. Ejercicio 5.33. En el ejemplo anterior escribir S y verificar el teorema anterior. Ejemplo 5.34. Graficar, como un grafo dirigido, la relaci´on del ejemplo anterior.

1

2

3

4

6

5

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

42

Observaci´ on 5.35. El grafo obtenido de la relaci´on de equivalencia R est´a dividido en los subconjuntos de la partici´on definida por R y cada uno de esos subgrafos es completo. Ejercicio 5.36. . ¿Cu´antos arcos se conectan a cada nodo en cada parte del grafo? ¿Cu´antos arcos hay en total en cada parte del grafo? ¿Cu´al es su representaci´on matricial?

5.3.

Funciones

Definici´ on 5.37. Sean A y B dos conjuntos. Una funci´on de A en B es una relaci´on f tal que a cada elemento de A se le asigna uno y s´olo un elemento de B. Notaci´ on 5.38. Si f es una funci´on de A en B, la denotamos: f :AÑB

o tambi´en

f

A ÝÑ B.

Para cada elemento a P A, el elemento de B asignado a a se denota f paq. Ejemplo 5.39. . 1. Sean A “ t1, 2, 3u y B “ ta, b, cu.Sea f “ tp1, aq, p2, cq, p3, cqu. 2. Sean A “ Z y B “ N. Sea f pzq “ z 2 ` 1. Ejercicio 5.40. Diga si las siguientes son funciones: 1. Sean A “ ta, b, c, d, eu y B “ A. Sea f “ tpa, bq, pb, cq, pc, dq, pe, aqu. 2. Sean A “ ta, b, c, d, eu y B “ A. Sea f “ tpa, eq, pb, eq, pc, eq, pd, eq, pe, equ. 3. Sean A “ ta, b, c, d, eu y B “ A. Sea f “ tpa, bq, pb, cq, pc, dq, pb, eq, pe, aqu. 4. Sean A “ Z y B “ N. Sea f pzq “ z 3 ` 3. 5. Sean A “ Z y B “ N. Sea f pzq “ z 4 . 6. Sean A “ Z y B “ t0, 1u. Sea f definida como: f pzq “ 0 si z es par y f pzq “ 1 si z es impar. Observaci´ on 5.41. Dado que las funciones son un caso particular de las relaciones, todo lo que hemos estudiado de las relaciones es v´alido para las funciones.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

43

Observaci´ on 5.42. Si f es una funci´on, entonces Dom f “ A, pero no necesariamente Ran f “ B (aunque forzosamente Ran f Ď B). Observaci´ on 5.43. Dos funciones f y g, son iguales si y s´olo si f paq “ gpaq para todo a P A. ¿Cu´ando dos funciones son distintas? Ejercicio 5.44. Sean f pxq “ x y gpxq “

? x2 . ¿Son f y g iguales?

Ejercicio 5.45. Se define el piso de un n´ umero real x, denotado por txu, como el mayor n´ umero entero menor o igual a x. An´alogamente, se define el techo de un n´ umero real x, denotado por rxs, como el menor n´ umero entero mayor o igual a x. Sean f : R Ñ Z y g : R Ñ Z definidas por f pxq “ txu y gpxq “ rxs. 1. ¿Son f pxq y gpxq funciones? 2. ¿Son f pxq y gpxq iguales? Observaci´ on 5.46. En la mayor´ıa de las implementaciones computacionales se define la funci´on de truncamiento como # txu si x ě 0, Truncpxq “ rxs si x ă 0, y la funci´on de redondeo como # Truncpx ` 0.5q si x ě 0, Roundpxq “ Truncpx ´ 0.5q si x ă 0. Ejercicio 5.47. Calcular Roundp2.6q, Roundp´4.4q y Roundp´0.2q.

5.3.1.

Gr´ afica de una funci´ on

Dado que una funci´on es una relaci´on, la gr´afica de una funci´on es en realidad su representaci´on en producto cartesiano. Algunos autores dan la siguiente definici´on formal de gr´afica (que, en nuestro caso, coincide con la definici´on de funci´on). Definici´ on 5.48. Sea f : A Ñ B una funci´on, la gr´afica de f , denotada por Γpf q, es el subconjunto de A ˆ B definido por: Γpf q “ tpa, f paqq | a P Au. ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

44

Ejemplo 5.49. Graficar las siguientes funciones: 1. Sean A “ ta, b, c, d, eu y B “ A. Sea f “ tpa, bq, pb, cq, pc, dq, pd, cq, pe, aqu. 2. Sean A “ Z y B “ Z. Sea f pzq “ 2z ´ 1. 3. Sean A “ Z y B “ N. Sea f pzq “ z 2 ` 1. e d c

5

10

4

9

3

8

2

7

1 ´3

b

´2

a

6

´1 0

1

2

5

3

´1

4

´2

3

´3

2

´4

1

a

b

c

d

e

´5

´3

´2

´1

0

1

2

3

Gr´ aficas de los ejemplos 1, 2 y 3, respectivamente.

Observaci´ on 5.50. En la gr´afica de una funci´on cada recta vertical que pasa por un elemento del dominio intersecta con uno y s´olo un punto de la gr´afica.

5.3.2.

Composici´ on de funciones

Sean f : A Ñ B y g : B Ñ C dos funciones. Dado que para cada a P A, f paq es un elemento de B, y puesto que B es el dominio de g, entonces tiene sentido calcular gpf paqq, el cual es un elemento de C, ya que C es el contradominio de g. Definici´ on 5.51. Dadas f : A Ñ B y g : B Ñ C dos funciones, la funci´on compuesta de f con g, denotada por g ˝f es la funci´on de A en C tal que g ˝f paq “ gpf paqq. f A

g B

C

Ejemplo 5.52. Sean A “ ta, b, cu, B “ t1, 2, 3u y C “ tx, y, zu. Sean f : A Ñ B y g : B Ñ C las siguientes: f “ tpa, 2q, pb, 3q, pc, 2qu y g “ tp1, xq, p2, zq, p3, xqu. ¿Son f y g funciones? ¿Qui´en es g ˝ f ? Ejemplo 5.53. Sean f : R Ñ R y g : R Ñ R definidas como sigue: f pxq “ x2 y gpxq “ x ` 3. ¿Son f y g funciones? ¿Qui´en es g ˝ f ? ¿Qui´en es f ˝ g? Observaci´ on 5.54. Se debe tener cuidado de no confundir g ˝ f con f ˝ g. (En el ejemplo 1 ni siquiera existe f ˝ g). ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

5.3.3.

45

Funciones inyectivas y sobreyectivas

Definici´ on 5.55. Se dice que una funci´on f : A Ñ B es inyectiva si y s´olo si diferentes elementos del dominio tienen diferentes im´agenes, esto es: a ‰ b ñ f paq ‰ f pbq o equivalentemente f paq “ f pbq ñ a “ b. Definici´ on 5.56. Se dice que una funci´on f : A Ñ B es sobreyectiva si y s´olo si todo b P B es imagen de alg´ un a P A, esto es: @b P B, Da P A, f paq “ b

o equivalentemente

Ran f “ B.

Definici´ on 5.57. Se dice que una funci´on f : A Ñ B es biyectiva si y s´olo si es inyectiva y sobreyectiva. Ejercicio 5.58. Decir si las siguientes funciones son inyectivas, sobreyectivas, biyectivas o ninguna: 1. Sea A “ ta, b, c, d, eu y f : A Ñ A, f “ tpa, bq, pb, cq, pc, dq, pd, cq, pe, aqu. 2. f : Z Ñ Z,

f pzq “ 2z ´ 1

3. f : R Ñ R` 0, 4. f : R Ñ R,

f pxq “ x2 f pxq “ xp donde p es un n´ umero natural impar.

Ejercicio 5.59. Demostrar las siguientes afirmaciones: 1. La composici´on de dos funciones inyectivas es inyectiva. 2. La composici´on de dos funciones sobreyectivas es sobreyectiva. 3. Si f ˝ g es inyectiva, entonces g es inyectiva. 4. Si f ˝ g es sobreyectiva, entonces f es sobreyectiva.

5.3.4.

Funci´ on inversa

Dada una funci´on f , puesto que f es una relaci´on, la relaci´on inversa f ´1 definida antes siempre existe, pero ¿es siempre f ´1 una funci´on? Ejemplo 5.60. Dados A “ B “ ta, b, c, d, eu y f “ tpa, bq, pb, cq, pc, dq, pd, cq, pe, aqu, entonces f ´1 “ tpa, eq, pb, aq, pc, bq, pc, dq, pd, cqu no es una funci´on.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

46

Ejemplo 5.61. Dados A “ B “ ta, b, c, d, eu y f “ tpa, bq, pb, dq, pc, eq, pd, aq, pe, cqu, entonces f ´1 “ tpa, dq, pb, aq, pc, eq, pd, bq, pe, cqu s´ı es funci´on. Observaci´ on 5.62. Para que f ´1 sea una funci´on, es necesario que f sea biyectiva. Ejercicio 5.63. Sea f : Q Ñ Q dada por f pxq “ 3x ´ 2. ¿Es funci´on?, ¿es biyectiva?, ¿cu´al su inversa? Ejercicio 5.64. Dada f “ tp1, bq, p2, dq, p3, eq, p4, aq, p5, cqu, graficar f y f ´1 . f

e d

4

c

3

b

2

a

1 1

2

f ´1

5

3

4

5

a

b

c

d

e

Observaci´ on 5.65. Dada f una funci´on, la gr´afica de la funci´on inversa f ´1 es la gr´afica de f reflejada sobre un eje de 45˝ .

5.3.5.

Funci´ on identidad

Definici´ on 5.66. Dado A un conjunto, la funci´on IA : A Ñ A definida por IA paq “ a se llama funci´on identidad en A. Es decir, IA asigna cada elemento a s´ı mismo. Observaci´ on 5.67. Dada f : A Ñ B cualquier funci´on, entonces: IB ˝ f “ f ˝ IA “ f. Observaci´ on 5.68. Si f : A Ñ B es una funci´on biyectiva y f ´1 : B Ñ A su funci´on inversa, entonces: f ´1 ˝ f “ IA

y

f ˝ f ´1 “ IB .

Observaci´ on 5.69. Si f es biyectiva, pf ´1 q´1 “ f . Observaci´ on 5.70. Si |A| “ n, entonces la representaci´on matricial de la funci´on identidad IA es la matriz identidad In . Observaci´ on 5.71. Si f es una funci´on biyectiva y F es la representaci´on matricial de f , entonces la representaci´on matricial de f ´1 es F t .

¡Material en construcci´on! (versi´on: 2018.04.19)

Cap´ıtulo 6 Recursividad 6.1.

Sucesiones

Definici´ on 6.1. Una sucesi´on S es una funci´on f : N Ñ A. Si f pnq “ sn solemos denotar S “ ps1 , s2 , s3 , . . . q, S “ psn q8 n“1 , S “ psn qnPN o simplemente S “ psn q. Los elementos sn son llamados t´erminos de la sucesi´on. Notaci´ on 6.2. La mayor´ıa de los autores denotan las sucesiones por S “ tsn u. Nosotros las denotaremos con par´entesis como una n-upla y no con llaves como un conjunto, ya que el orden de los elementos es importante. Ejemplo 6.3. . # 1. f pnq “

n 2 n`1 2

si n es par, si n es impar.

2. f pnq “ p´1qn 3. p2, 4, 6, 8, . . . q ´ 2 ¯ 4. n 2`n nPN

6.1.1.

Sucesiones crecientes y decrecientes

Definici´ on 6.4. Sea S “ psn q una sucesi´on, entonces: Se dice que S es creciente si y s´olo si sk ă sk`1 para todo k P N. Se dice que S es decreciente si y s´olo si sk ą sk`1 para todo k P N. Se dice que S es no creciente si y s´olo si sk ě sk`1 para todo k P N. Se dice que S es no decreciente si y s´olo si sk ď sk`1 para todo k P N. 47

Matem´aticas discretas (M. Mata)

48

Nomenclaura 6.5. Una sucesi´on se dice mon´otona si es creciente, decreciente, no creciente o no decreciente. As´ı, por ejemplo, si una sucesi´on es creciente, tambi´en se dice que es mon´otona creciente. Ejemplo 6.6. Decir si las siguientes sucesiones son crecientes, decrecientes, no crecientes, no decrecientes o ninguna. 1. sn “ np , ` ˘ 2. n1 nPN 3. sn “

pp ě 1q

n´1 n

4. S “ p2, 4, 6, 8, . . . q 5. sn “ p´1qn ´ ¯ 2 6. n´n 2 8

7. pn2 ´ 2n qn“1

6.1.2.

Subsucesiones

Definici´ on 6.7. Sea psn q una sucesi´on y pnk q una sucesi´on de elementos de N tales que n1 ă n2 ă n3 ă ¨ ¨ ¨ . Entonces, la sucesi´on psnk q es llamada una subsucesi´on de psn q. Ejemplo 6.8. Sea S “ psn q una sucesi´on, la sucesi´on ps2n qnPN “ ps2 , s4 , s6 , . . . q es una subsucesi´on de S. Teorema 6.9. Toda sucesi´on de n´ umeros reales tiene una subsucesi´on mon´otona.

6.2.

Funciones recursivas

Ejercicio 6.10. En la biblioteca se cobran $ 5.00 por el pr´estamo de un libro que debe devolverse al d´ıa siguiente. Si un estudiante desea llevarse el libro por m´as tiempo, pagar´a una cantidad de $ 1.50 por cada d´ıa adicional. Sea cn el costo que el alumno debe pagar el d´ıa n por haber pedido prestado un libro. ¿Cu´anto se debe pagar por conservarlo un d´ıa m´as? cn`1 “ cn ` 1.5

con

c1 “ 5.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

49

Observaci´ on 6.11. La anterior es una f´ormula recursiva. En este caso es posible hallar una expresi´on alternativa que no dependa del valor anterior: cn “ 5 ` 1.5pn ´ 1q. Nomenclaura 6.12. Una funci´on recursiva es una funci´on f : N Ñ R tal que el valor de f pnq depende de un conjunto de valores anteriores, los cuales deben ser conocidos o pueden ser calculados. En t´erminos simples, una funci´on recursiva es aquella que se invoca a s´ı misma. Notaci´ on 6.13. Con frecuencia escribimos fn como equivalente de f pnq. Ejemplo 6.14. La siguientes son funciones expresadas en forma recursiva: 1. f0 “ 1

y fn “ n ¨ fn´1 .

2. Dado a ą 0, ga p0q “ 1 3. F0 “ 0, F1 “ 1 4. f p0q “ f p1q “ 1

6.3.

(Factorial)

y ga pnq “ a ¨ ga pn ´ 1q.

y Fn “ Fn´1 ` Fn´2 .

(Potencia) (Sucesi´on de Fibonacci)

y f pnq “ n ¨ f pn ´ 2q.

(Doble factorial)

Notaci´ on Sigma

Una suma de varios t´erminos se puede escribir en forma m´as compacta y m´as concisa mediante la notaci´on sigma: n ÿ

ai “ a1 ` a2 ` a3 ` ¨ ¨ ¨ ` an .

i“1

Ejercicio 6.15. Expresar las siguientes sumas en su notaci´on desarrollada: 1.

7 ÿ

bi

i“3

2.

4 ÿ

cj`1

j“1

3.

5 ÿ

a2k´1

k“1

Ejercicio 6.16. Calcular el resultado de las siguientes sumas: ¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

1.

5 ÿ

50

3i

i“2

2.

4 ÿ

pj ` 1q2

j“1 5 ÿ

3.

p2k ´ 1q

k“1

4.

888 ÿ

p´1qi

i“1

5.

n ÿ

1

i“1

Teorema 6.17. Las siguientes propiedades se satisfacen: 1.

n ÿ

c ai “ c

i“1

2.

n ÿ

pai ` bi q “

n ÿ i“1

6.4.

ai

i“1

i“1

3.

n ÿ

n ÿ

ai `

i“1

ai “

m ÿ i“1

ai `

n ÿ

bi

i“1 n ÿ

ai

i“m`1

Inducci´ on matem´ atica

La inducci´on matem´atica es un m´etodo que permite demostrar que cierta propiedad se cumple para todos los elementos de un conjunto infinito numerable. La idea fundamental se basa en que, si una propiedad P es v´alida para un n´ umero k0 P N y que si siempre que dicha propiedad sea verdadera para un n´ umero k tambi´en lo es para su sucesor k ` 1; entonces se puede asegurar que la propiedad P es v´alida para todos los n´ umeros naturales mayores o iguales que k0 . La demostraci´on por inducci´on matem´atica se basa, por tanto, en dos pasos: Paso inductivo (paso de la muerte): Suponiendo que la propiedad deseada es verdadera para un n´ umero k, demostrar que lo es para su sucesor k ` 1. Paso base: Demostrar que existe un n´ umero inicial k0 para el cual se cumple la propiedad deseada.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

51

Ejemplo 6.18. Demuestre que, para todo n P N se cumple que: n ÿ

i“

i“1

npn ` 1q . 2

Ejemplo 6.19. Demostrar por inducci´on las siguientes afirmaciones: 1.

n ÿ

i2 “

i“1

npn ` 1qp2n ` 1q 6

2. n! ě 2n ¿cu´al es la base? 3. @n P N se cumple que 5n ´ 1 es divisible por 4. n ÿ

rn`1 ´ 1 4. r “ r´1 i“0 i

Ejercicio 6.20. Demostrar por inducci´on las siguientes afirmaciones: 1.

n ÿ

p2k ´ 1q “ n2

k“1

2.

n ÿ

kpk ` 1q “

k“1

npn ` 1qpn ` 2q 3

3. n2 ą 2n ` 1, ¿cu´al es la base? 4. 2n ą n2 , ¿cu´al es la base? 5. @n P N se cumple que n3 ´ n es divisible por 3. 6.

n ÿ

i3 “

n2 pn ` 1q2 4

i4 “

npn ` 1qp2n ` 1qp3n2 ` 3n ´ 1q 30

i“1

7.

n ÿ i“1

8. @n P N se cumple que n3 ` 1 ě n2 ` n. 9. Si a ą ´1, entonces p1 ` aqn ě 1 ` na, para todo n P N (desigualdad de Bernoulli). 10. @n P N se cumple que 22n´1 ` 32n´1 es divisible por 5.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

52

Ejercicio 6.21. Se define el doble factorial de un n´ umero entero no negativo n mediante la siguiente f´ormula recursiva: # 1 n “ 0 o n “ 1, n!! “ n ¨ pn ´ 2q!! n ě 2. Demostrar por inducci´on que: 1. Si n es un n´ umero par de la forma 2m, entonces n!! “ 2m m! 2. Si n es un n´ umero impar de la forma 2m ´ 1, entonces n!! “

p2mq! 2m m!

Ejercicio 6.22. Sea M “ t1 ` k1 | k P Nu. Demostrar que cada n´ umero entero p P Z puede escribirse como producto de uno o m´as elementos de M, no necesariamente distintos.

¡Material en construcci´on! (versi´on: 2018.04.19)

Cap´ıtulo 7 Combinatoria 7.1.

Conteo

Ejemplo 7.1. Un estudiante tiene 6 playeras, 4 pantalones y 2 pares de tenis. ¿De cu´antas formas distintas puede combinar su ropa al vestir?

7.1.1.

Principio fundamental del conteo

Si un suceso puede ocurrir de n1 formas distintas, un segundo suceso puede ocurrir de n2 formas distintas, y as´ı sucesivemente hasta un k-´esimo evento que puede ocurrir de nk formas distintas, entonces el n´ umero de formas distintas en que los sucesos pueden ocurrir es n1 ˆ n2 ˆ ¨ ¨ ¨ ˆ nk . Ejercicio 7.2. Las placas de automovil contienen 3 letras seguidas de 4 n´ umeros. ¿Cu´antas placas diferentes pueden fabricarse? Ejercicio 7.3. Si se eligen en el sal´on un presidente, un secretario y un tesorero, ¿de cu´antas formas diferentes puede hacerse esta selecci´on?

7.2.

Permutaciones

Definici´ on 7.4. Sea A un conjunto de n elementos. Una ((permutaci´on de esos n elementos tomados de r a la vez)) (r ď n) es un arreglo de r elementos de A en un orden determinado. En otras palabras, una ((permutaci´on de n en r)) es un posible ordenamiento de r de los elementos de A. Nomenclaura 7.5. Cuando se permutan todos los elementos A se dice simplemente permutaci´on en vez de ((permutaci´on de n en n)). 53

Matem´aticas discretas (M. Mata)

54

Ejercicio 7.6. Sea A “ ta, b, c, du. 1. ¿Cu´antas son todas las posibles permutaciones de los elementos de A? Enliste algunos ejemplos. 2. ¿Cu´antas son todas las posibles permutaciones tomadas de 3 a la vez? Enliste algunos ejemplos. 3. ¿Cu´antas son todas las posibles permutaciones tomadas de 2 a la vez? Escriba algunos ejemplos. 4. ¿Cu´antas son todas las posibles permutaciones tomadas de 1 a la vez? Enliste algunos ejemplos. Notaci´ on 7.7. El n´ umero de permutaciones de n en r se representa por Prn . Otros autores tambi´en usan P pn, rq, n Pr o Pn,r . Definici´ on 7.8. Se define el factorial de un n´ umero n P N0 , y se denota n!, como 1 si n “ 0 y como el producto de todos los n´ umeros naturales menores o iguales a n para el resto de los casos. Es decir, # 1 si n “ 0, n! “ 1 ¨ 2 ¨ . . . ¨ n si n P N. Teorema 7.9. Prn “ npn ´ 1qpn ´ 2q ¨ ¨ ¨ pn ´ r ` 1q “

n! pn ´ rq!

Ejercicio 7.10. Calcular P47 . Ejercicio 7.11. Demostrar que Pnn “ n!.

7.2.1.

Permutaciones con repetici´ on

En ocasiones deseamos encontrar el n´ umero de permutaciones de objetos, algunos de los cuales son iguales. Teorema 7.12. El n´ umero de permutaciones de n objetos de los cuales n1 son iguales, n2 son iguales, . . . , nk son iguales (n “ n1 ` n2 ` ¨ ¨ ¨ ` nk ) es n! n1 !n2 ! ¨ ¨ ¨ nk ! Ejemplo 7.13. ¿Cu´antos cadenas distintas de longitud 7 pueden formarse con los elementos de la cadena cananea?

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

7.3.

55

Combinaciones

Definici´ on 7.14. Sea A un conjunto de n elementos. Una ((combinaci´on de esos n elementos tomados de r a la vez)) es cualquier selecci´on de r elementos de A sin importar el orden. En otras palabras, una ((combinaci´on de n en r)) es cualquier subconjunto de r elementos del conjunto A. Ejercicio 7.15. Sea A “ ta, b, c, du. 1. Enliste todas las posibles combinaciones tomadas de 3 a la vez. 2. Enliste todas las posibles combinaciones tomadas de 2 a la vez. 3. Enliste todas las posibles combinaciones tomadas de 1 a la vez. 4. Enliste todas las posibles combinaciones tomadas de 4 a la vez. Notaci´ on 7.16. El n´ umero de combinaciones de n en r se representa por Crn . Otros autores tambi´en usan Cpn, rq, n Cr o Cn,r . Teorema 7.17. Crn “

Prn n! “ r! r!pn ´ rq!

Ejemplo 7.18. . 1. ¿Cu´antos comit´es de 3 personas pueden hacerse de un grupo de 8? 2. ¿Cu´antas manos de p´oquer distintas pueden tomarse de la baraja inglesa? n “ n. Ejercicio 7.19. Demostrar que C1n “ Cn´1

7.4.

Diagramas de ´ arbol

Un diagrama de ´arbol es un recurso gr´afico que se puede emplear para enumerar todas las posibilidades l´ogicas de una secuencia finita de sucesos. Ejemplo 7.20. Un estudiante tiene 3 camisetas, 2 pantalones y 2 pares de tenis. ¿De cu´ales formas puede combinar su ropa al vestir? Denotemos por el conjunto C “ tc1 , c2 , c3 u las tres camisetas, por P “ tp1 , p2 u los dos pantalones y por T “ tt1 , t2 u los dos pares de tenis. Las posibles formas de combinar la ropa se ilustran en el siguiente diagrama:

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

56 t1

p1

t2 c1 t1

p2

t2 t1

p1

t2 c2

‚

t1

p2

t2 t1

p1

t2 c3 t1

p2

t2 Ejemplo 7.21. Marcos y Enrique van a jugar frontenis. El primero en ganar dos juegos seguidos o que gane un total de tres juegos ser´a el ganador del encuentro. El siguiente diagrama ilustra las posibles formas en que termine el encuentro: M M

M M

E

M E

E

E

M

M

‚

M E

M E

E

E E

¿Cu´antas formas distintas hay de terminar el encuentro? ¿Cu´al es el n´ umero m´ınimo de juegos que se requieren para terminar el encuentro?

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

57

¿Cu´al es el n´ umero m´aximo de juegos que se requieren para terminar el encuentro? Ejercicio 7.22. Un hombre jugar´a a la ruleta. El hombre inicia con un peso y en cada juego gana o pierde un peso. El hombre teminar´a de jugar si se queda sin dinero, cuando termine el quinto juego, o cuando tenga una ganacia de tres pesos (es decir, si acumula cuatro pesos). Realice un diagrama de ´arbol que represente todas las posibilidades. 4

4 3 2

3

2 2 1 0

1

2 4 3 2 1

2

0

2 1 0

7.5.

0

Coeficientes binomiales

Definici´ on 7.23. Se define el ((coeficiente binomial de n en r)) (con n y r n´ umeros naturales o cero tales que r ď n) como ˆ ˙ n! n “ r r!pn ´ rq!

Observaci´ on 7.24.

`n˘ r

“ Crn

Ejemplo 7.25. Demostrar que

7.5.1.

`n˘ r

“

`

n n´r

˘

Tri´ angulo de Pascal

El tri´angulo de Pascal es una disposici´on de n´ umeros ordenados en forma triangular, de tal manera que cada n´ umero interior tiene un n´ umero superior derecho y un n´ umero superior izquierdo, tales que dicho n´ umero es igual a la suma de sus n´ umeros superiores.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

58 `0 ˘

1 1 1 1 1 1 1 1

5 6

7

1 2

3 4

0

`1˘ `1˘ 0

1 3

6

0

4

2

0

5

2

3

0

6

1

2

3

4

`5˘ `5˘ `5˘ `5˘ `5˘ `5˘

1

21 35 35 21

1

`4˘ `4˘ `4˘ `4˘ `4˘

1

15 20 15

1

`3˘ `3˘ `3˘ `3˘

1

10 10

1

`2˘ `2˘ `2˘

0

1 7

1

2

3

4

5

`6˘ `6˘ `6˘ `6˘ `6˘ `6˘ `6˘ 0

1

2

3

4

5

6

`7˘ `7˘ `7˘ `7˘ `7˘ `7˘ `7˘ `7˘

1

0

1

2

3

4

5

6

7

Los n´ umeros del tri´angulo de Pascal est´an ´ıntimamente relacionados con los coeficientes binomiales, como se muestra en la figura, y con el teorema del binomio. Para establecer la relaci´on entre el tri´angulo de Pascal y los bino`n´1coeficientes ˘ miales observe que el k-´esimo elemento de la n-´esima fila es k´1 . As´ı, la propiedad de que cada elemento del tri´angulo es igual a la suma de los elementos superiores a ´el se puede demostrar en el siguiente teorema. ˆ ˙ ˆ ˙ ˆ ˙ n n´1 n´1 “ ` . Teorema 7.26. r r´1 r

7.5.2.

Teorema del binomio

El teorema del binomio, que puede demostrarse por inducci´on matem´atica, establece la expresi´on general para el desarrollo de pa ` bqn . n ˆ ˙ ÿ n n´r r n a b. Teorema 7.27. pa ` bq “ r r“0 Ejemplo 7.28. Desarrollar pa ` bq6 . pa ` bq6 “ a6 ` 6a5 b ` 15a4 b2 ` 20a3 b3 ` 15a2 b4 ` 6ab5 ` b6 . Ejercicio 7.29. Desarrollar p2x ´ 3yq5 . Ejemplo 7.30. Demostrar que

`n˘

Ejercicio 7.31. Demostrar que

`n˘

0

0

`

`n˘

´

`n˘

1

1

`

`n˘

`

`n˘

2

2

` ¨¨¨ `

`n˘ n

“ 2n .

´ ¨ ¨ ¨ ` p´1qn

`n˘ n

¡Material en construcci´on! (versi´on: 2018.04.19)

“ 0.

Cap´ıtulo 8 Teor´ıa de grafos Los grafos, tambi´en llamados gr´aficas, son herramientas muy u ´tiles en la comprensi´on, construcci´on y resoluci´on de modelos y m´etodos matem´aticos para la soluci´on de diversos problemas te´oricos y pr´acticos de diversas ´areas del conocimiento. La teor´ıa de grafos a´ un no es una disciplina uniformada, por lo que las definiciones y conceptos var´ıan de un autor a otro (ya sea en relaci´on al problema a resolver o la imaginaci´on del autor) en forma casi an´arquica. Las definiciones que se proporcionan en este cap´ıtulo han sido constituidas en forma m´as o menos generalizada.

8.1.

Grafos

Definici´ on 8.1. Un grafo G “ pV, Eq es una pareja ordenada constituida por un conjunto V de v´ertices o nodos y un conjunto E de parejas de elementos de V . Observaci´ on 8.2. La mayor´ıa de los autores suele definir a V como un conjunto finito y no vac´ıo. Por su parte, el conjunto E puede ser definido de parejas ordenadas o de parejas no ordenadas de elementos de V . Definici´ on 8.3. Se dice que un grafo G “ pV, Eq es: Un grafo dirigido si el conjunto E est´a formado por parejas ordenadas de elementos de V , es decir, E Ď V ˆ V . En este caso, los elementos de E son llamados arcos. 59

Matem´aticas discretas (M. Mata)

60

Un grafo no dirigido si el conjunto E est´a formado por parejas no ordenadas de elementos de V , es decir, E Ď ttu, vu | u, v P V u. En este caso, los elementos de E son llamados aristas. Un grafo mixto si el conjunto E contiene tanto arcos como aristas. Ejemplo 8.4. Sea G “ pt1, 2, 3, 4u, tp1, 2q, p2, 2q, p2, 4q, p3, 2q, p3, 4quq, el cual se puede representar gr´aficamente por: 1

2

4

3

Ejercicio 8.5. Representar gr´aficamente G “ pt1, 2, 3, 4, 5u, tt1, 2u, t2, 4u, t2, 5u, t3, 3u, t3, 4u, t4, 5uuq: 1

5

2

4

3

Ejemplo 8.6. Sea V el conjunto de pasajeros de cierto vuelo transatl´antico y E el conjunto de pares pu, vq de pasajeros tales que el pasajero u habla un idoma com´ un con v y u es m´as joven que v. Ejercicio 8.7. En el grafo del ejemplo anterior: 1. Si pu, vq est´a en el grafo, ¿es posible que pv, uq tambi´en est´e en el grafo? 2. Si existen pasajeros u, v y w tales que pu, vq y pv, wq est´an en el grafo, ¿entonces pu, wq tambi´en pertenece al grafo?

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

8.2.

Definiciones b´ asicas

8.2.1.

Incidencia y adyacencia

61

Definici´ on 8.8. Dado un arco a “ pu, vq, el v´ertice u es llamado v´ertice inicial de a y v es llamado v´ertice terminal de a; tambi´en u y v ser´an llamados v´ertices extremos de a. Definici´ on 8.9. Un v´ertice v y un arco a son incidentes si v es un v´ertice extremo de a. Definici´ on 8.10. Dos arcos son adyacentes si tienen un mismo v´ertice extremo. Dos v´ertices son adyacentes si existe un arco que los une. Definici´ on 8.11. Un arco de la forma pv, vq es llamado bucle. Una arista de la forma tv, vu es llamado lazo.

8.2.2.

Cadenas, caminos, ciclos y circuitos

Definici´ on 8.12. Una sucesi´on de aristas (o arcos) adyacentes que empieza en v y termina en w se llama una cadena de v a w. Definici´ on 8.13. En un grafo dirigido, un camino es una cadena tal que cada par de arcos adyacentes en la cadena, el v´ertice final de un arco es el v´ertice inicial del otro arco. Definici´ on 8.14. Un ciclo es una cadena que inicia y termina en el mismo v´ertice. Definici´ on 8.15. En un grafo dirigido, un circuito es un camino que inicia y termina en el mismo v´ertice. Observaci´ on 8.16. Todo circuito es un ciclo. Ejemplo 8.17. Considere el siguiente grafo:

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

62 1

2 3

4

Entonces, los siguientes son ejemplos de: 1

1

2

2

3

4

3

4

(a) una cadena,

(b) un camino,

1

1

2

2

3

4 (c) un ciclo,

3

4 (d) un circuito.

Definici´ on 8.18. Una cadena (o camino) simple es aquella que no pasa m´as de una vez por la misma arista (o arco). Una cadena (o camino) elemental es aquella que no pasa m´as de una vez por el mismo v´ertice. Ejercicio 8.19. ¿Puede existir una cadena que no sea simple pero que s´ı sea elemental? Observaci´ on 8.20. Toda cadena (o camino) elemental es simple.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

63

Definici´ on 8.21. Un camino euleriano (o cadena euleriana) es un camino (cadena) simple que pasa por todos los arcos (aristas). Un ciclo euleriano (o circuito euleriano) es un ciclo (circuito) simple que pasa por cada arista (arco). Definici´ on 8.22. Un camino hamiltoniano (o cadena hamiltoniana) es un camino (cadena) elemental que pasa por todos los v´ertices. Un ciclo hamiltoniano (o circuito hamiltoniano) es un ciclo (circuito) elemental que pasa por cada v´ertice.

8.3. 8.3.1.

Algunos tipos de grafos Grafos completos

Definici´ on 8.23. Un grafo es completo si para cada par de v´ertices distintos existe una arista (un arco) que los une. Observaci´ on 8.24. Un grafo completo no contiene bucles o lazos. Notaci´ on 8.25. El grafo completo de n v´ertices suele denotarse por Kn . Ejercicio 8.26. Hacer la representaci´on gr´afica de K6 . Teorema 8.27. El n´ umero de aristas (arcos) de Kn es igual a npn ´ 1q . 2

8.3.2.

Grafos conexos

Definici´ on 8.28. Un grafo es conexo si para cada par de v´ertices distintos existe una cadena que los une. Ejercicio 8.29. ¿Cu´al es la menor cantidad de aristas que contiene un grafo conexo de n v´ertices?

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

8.3.3.

64

´ Arboles

Definici´ on 8.30. Un ´arbol es un grafo conexo sin ciclos. Teorema 8.31. Sea G un grafo con n v´ertices, entonces las siguientes afirmaciones son equivalentes: G es un a´rbol. G tiene n ´ 1 arcos y es conexo. G tiene n ´ 1 arcos y no tiene ciclos. Definici´ on 8.32. Un bosque es un grafo en el cual cada componente conexa es un ´arbol.

8.3.4.

Grafos bipartitos

Definici´ on 8.33. Un grafo G “ pV, Eq es bipartito si existe una partici´on de V , tV1 , V2 u, tal que para todo pu, vq P E se cumple que u P V1 y v P V2 , o bien u P V2 y v P V1 . Observaci´ on 8.34. Recordemos que tV1 , V2 u es una partici´on de V si y s´olo si V “ V1 Y V2 y V1 X V2 “ ∅. Definici´ on 8.35. La cardinalidad de una cadena es el n´ umero de arcos que la componen. Teorema 8.36. Un grafo es bipartito si y s´olo si no contiene ciclos de cardinalidad impar. Corolario 8.37. Todos los ´arboles son bipartitos.

8.4.

Predecesores, sucesores y grados

Definici´ on 8.38. El conjunto de v´ertices predecesores de un v´ertice v se define por Γ´ pvq “ tu | pu, vq P Eu.

¡Material en construcci´on! (versi´on: 2018.04.19)

Matem´aticas discretas (M. Mata)

65

Definici´ on 8.39. El conjunto de v´ertices sucesores de un v´ertice v se define por Γ` pvq “ tw | pv, wq P Eu. Definici´ on 8.40. El grado entrante de v se define por g ´ pvq “ |Γ´ pvq|. El grado saliente de v se define por g ` pvq “ |Γ` pvq|. El grado de v se define por gpvq “ g ´ pvq ` g ` pvq. Observaci´ on 8.41. En el c´alculo del grado, un bucle se cuenta dos veces.

8.5.

Representaciones matriciales

Definici´ on 8.42. La matriz de incidencia de un grafo G “ pV, Eq, con |V | “ n y |E| “ m es una matriz n ˆ m tal que cada elemento eij est´a dado por: $ ’ &`1 si el v´ertice i es el v´ertice inicial del arco j, eij “ ´1 si el v´ertice i es el v´ertice terminal del arco j, ’ % 0 en otro caso. Observaci´ on 8.43. La suma de cada columna de la matriz de incidencia es cero. Definici´ on 8.44. La matriz de adyacencia de un grafo G “ pV, Eq, con |V | “ n es una matriz n ˆ n tal que cada elemento aij est´a dado por: # 1 si el arco pi, jq P E, aij “ 0 si el arco pi, jq R E. Observaci´ on 8.45. La suma de cada fila de la matriz de adyacencia es g ` piq. Ejemplo 8.46. Dados V “ t1, 2, 3, 4, 5u y E “ tp1, 2q, p2, 5q, p3, 2q, p3, 4q, p5, 1q, p5, 4qu: 1. Graficar G “ pV, Eq. 2. Escribir la matriz de adyacencia. 3. Verifique que en la matriz de adyacencia la suma por filas es g ` piq. ¿A qu´e es igual la suma por columnas? 4. Escribir la matriz de incidencia. 5. Verifique que en la matriz de incidencia la suma por columnas es cero. ¿A qu´e es igual la suma por filas?

¡Material en construcci´on! (versi´on: 2018.04.19)

Ap´ endice A Conjuntos num´ ericos A.1.

Breve resumen

El concepto de n´ umero ha sufrido un largo y complejo desarrollo hist´orico. Iniciaremos dando un breve resumen de los conjuntos num´ericos, los cuales se abordar´an un poco m´as a detalle en las siguientes secciones. N´ umeros naturales: Los m´as antiguos. Son los que se emplean para contar. N “ t1, 2, 3, . . . u N´ umeros enteros: A los n´ umeros naturales se a˜ nanden sus inversos aditivos (negativos) y el cero. Z “ t. . . , ´3, ´2, ´1, 0, 1, 2, 3, . . . u N´ umeros racionales: Conocidos tambi´en como fraccionales. Su expansi´on decimal es peri´odica. !a ˇ ) ˇ Q“ ˇ a, b P Z, b ‰ 0 b N´ umeros irracionales: Son n´ umeros de expansi´on decimal infinita no peri´odica. Para estos n´ umeros no existe forma de? escribirlos como cociente de dos enteros. Algunos ejemplos de estos n´ umeros son: 2, π, e, φ, sen 1˝ . N´ umeros reales: Son aquellos que contienen a todos los n´ umeros con cualquier tipo de expansi´on decimal. Son la uni´on de los n´ umeros racionales y los irracionales. R “ tA.A1 A2 A3 ¨ ¨ ¨ | A P Z, Ai P t0, 1, 2, . . . , 9uu

66

Matem´aticas discretas (M. Mata)

67

N´ umeros complejos: Una vez definida la unidad imaginaria i, son aquellos que se conforman de una parte real y una imaginaria. C “ ta ` b i | a, b P Ru Observaci´ on A.1. Los conjuntos N, Z y Q son conjuntos discretos. Los conjuntos R y C son conjuntos continuos.

¡Material en construcci´on! (versi´on: 2018.04.19)