Matemáticas discretas (apoyo de clase)

Matem´aticas discretas (apoyo de clase) Dr. Miguel Mata [email protected] FIME-UANL 2 de septiembre de 2016 ´Indice general Introducci´ on

0 downloads 29 Views 548KB Size

Story Transcript

Matem´aticas discretas (apoyo de clase) Dr. Miguel Mata [email protected] FIME-UANL 2 de septiembre de 2016

´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.6. Cuantificadores . . . . . . . . . . . . . . 1.6.1. Negaci´on . . . . . . . . . . . . . . 1.6.2. Cuantificadores anidados . . . . .

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

1 2 2 2 3 3 3 4 4 4 4 5 6 8 8 9 9 10 11 12 13 13 14

2. Conjuntos 2.1. Relaci´on de pertenencia . . . . . . . . . . . . . . . . . . . . . . .

15 15

i

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

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

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

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

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

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

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

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

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

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

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

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

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

Matem´aticas discretas (M. Mata)

ii

2.2. 2.3. 2.4. 2.5. 2.6.

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 . . 4.2.4. Matriz sim´etrica . . . . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

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

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

. . . . . . . . . .

. . . . . . . . . .

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

16 16 17 18 18 18 18 18 19 20 20 21 22

. . . . . . . . . .

23 23 24 25 25 26 26 26 27 27 27

. . . . . . . . . .

28 28 28 28 29 29 30 31 31 31 32

Matem´aticas discretas (M. Mata)

iii

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: 2016.09.02)

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

. . . . . .

. . . . . . .

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

. . . . . .

. . . . . . .

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

. . . . . .

. . . . . . .

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

. . . . . .

. . . . . . .

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

. . . . . .

. . . . . . .

32 33

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

34 34 34 35 36 36 37 38 38 38 39 40 41 42 43 44 44

. . . . . .

46 46 46 47 47 48 49

. . . . . . .

51 51 51 51 52 53 53 55

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 . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

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

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

55 56 57 57 59 59 59 60 60 60 61 61 61 62

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:

v

Matem´aticas discretas (M. Mata)

vi

L´ogica 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: 2016.09.02)

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: 2016.09.02)

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 conlusi´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. 1  2.

2. 1 3. x2

1 ¡ 0.

4. Las violetas son azules. 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: 2 q: 2

3.

r: x2 r: x2

4.

s: Las rosas son rojas, s: Las rosas no son rojas.

2  4, 2  4. 1 ¡ 0, 1 ¤ 0.

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

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: 2016.09.02)

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, F, F,

J, 1. 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: 2016.09.02)

Matem´aticas discretas (M. Mata)

5

Ejemplo 1.6. Calcular la tabla de verdad de pp _ q q ^ 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

pp _ q q  A 1 1 1 1 1 1 0 0

r

B 0 1 0 1 0 1 0 1

A^B 0 1 0 1 0 1 0 0

Ejercicio 1.7. Calcular la tabla de verdad de 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

r 0 1 0 1 0 1 0 1

pq _ rq  A rp ^ As  B 1 1 0 1 1 1 0 1

1 1 0 1 0 0 0 0

p_B 1 1 1 1 0 0 0 0

Ejercicio 1.8. Calcular la tabla de verdad dep ^ 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

p q ^ rq  A pq ^ rq  B rA _ B s  C 0 0 1 0 0 0 1 0

0 1 0 0 0 1 0 0

0 1 1 0 0 1 1 0

p^C 0 1 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. 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).

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

Matem´aticas discretas (M. Mata)

6 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: r

p

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 ^ q q _ 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

pp ^ qq  A pp ^ rq  B pq ^ rq  C 1 1 0 0 0 0 0 0

1 0 1 0 0 0 0 0

1 0 0 0 1 0 0 0

A_B_C 1 1 1 0 1 0 0 0

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

Matem´aticas discretas (M. Mata)

7

p

p

q

q

r

r

1

1

1

q

r 0

r

1

0

0

q r

0

1

p p ^ q ^ r q _ pp ^ q q _ pq ^ r q p p ^ q ^ rq  A pp ^ qq  B pq ^ rq  C

0

Ejemplo 1.12. 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

0 0 0 0 0 0 0 1

1 1 0 0 0 0 0 0

1 0 0 0 1 0 0 0

p

p

q

q

r 1

r 1

0

q

r 0

1

0

0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

1

1

pq _ rq  A rp ^ As  B 1 1 0 1 1 1 0 1

q r

r

Ejercicio 1.13. p _ rp ^ pq _ rqs. p 1 1 1 1 0 0 0 0

A_B_C 1 1 0 0 1 0 0 1

1 1 0 1 0 0 0 0

p_B 1 1 1 1 0 0 0 0

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

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

pq ^ rq  A r p _ As  B p q _ rq  C rp ^ C s  D 0 1 0 0 0 1 0 0

0 1 0 0 1 1 1 1

1 0 1 1 1 0 1 1

1 0 1 1 0 0 0 0

B_D 1 1 1 1 1 1 1 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: 2016.09.02)

Matem´aticas discretas (M. Mata)

9

Ejercicio 1.15. Verifique que: rp Ñ pq ^ rqs ^ r p 1 1 1 1 0 0 0 0

1.4.2.

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

pq ^ rq  A rp Ñ As  B 1 0 0 0 1 0 0 0

ñ p B^ rC

1 0 0 0 1 1 1 1

C

0 0 0 0 0 1 0 1

Ñ

p

1 1 1 1 1 1 1 1

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:

pA Ñ B q ô pA ^

Bq

Ejercicio 1.17. Verifique que: pA Ø B q ô rpA Ñ B q ^ pB

1.4.3.

Ñ Aqs

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: 2016.09.02)

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 _ q q _ r p ^ pq ^ rq ô pp ^ q q ^ r p _ pq ^ rq ô pp _ q q ^ pp _ rq p ^ pq _ rq ô pp ^ q q _ 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 _ q q ^ p 2. 3.

ô p^q p _ pp ^ q q ô p pp _ qq _ p p ^ qq ô

1.4.4.

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.

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

Matem´aticas discretas (M. Mata)

11

3. Conversa: No pienso, entonces no existo. 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 Ñ q q ^ pq

Ñ pq

Contrapuesta Euivalencia 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 la proposici´on pP1 ^ P2 ^    ^ Pn q Ñ Q es una tautolog´ıa. 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 ^ r q

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 calmente de la forma

$ Q tambi´en suele denotarse verti-

P1 P2 .. . Pn Q

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

Matem´aticas discretas (M. Mata)

1.5.1.

12

Reglas de inferencia

Existen modelos de argumentos ya establecidos. Son llamados reglas de inferencia:

Modus ponendo ponens:

AÑB A B

Modus tollendo tollens:

AÑB B A

Modus tollendo ponens:

A_B B A

Simplificaci´ on:

A^B A

Conjunci´ on:

A B A^B

Adici´ on:

A 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, por medio de las reglas de inferencia, que los siguientes argumentos son v´alidos: 1.

p Ñ ps _ tq,

p

$ s_t

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

Matem´aticas discretas (M. Mata)

13

Ñ s, s ^ p $ r q Ñ s, p _ q, r ^ p $ s _ t p _ q, r Ñ q, s ^ r, t Ñ p $ pt ^ r q p _ q, t ^ p, q Ñ s $ s Ñ m m Ñ n, q _ m, p Ñ n, p _ r, q $ r A, A $ B (regla de contradicci´on)

2. r 3. 4. 5. 6. 7.

1.6.

Cuantificadores

Cuantificador universal: Empleamos el s´ımbolo @, el cual se lee para todo: @x, ppxq. Cuantificador existencial: Empleamos el s´ımbolo D, el cual se lee existe:

Dx, ppxq.

Ejemplo 1.27. .

1. Todos los n´ umeros racionales son n´ umeros reales: @x P Q, x P R. 2. Existen n´ umeros reales que no son racionales: Dx P R, x R Q.

?

3. ¿Es cierto que @n P N, n R Q?

1.6.1.

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, ppxqs ô Dx, ppxq. rDx, ppxqs ô @x, ppxq. Ejemplo 1.28. . 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? R= No es cierto, pues existe el 9 que no es primo. ¡Material en construcci´on! (versi´on: 2016.09.02)

Matem´aticas discretas (M. Mata)

14

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

1.6.2.

Cuantificadores anidados

Son de la forma:

@x, @y, P px, yq. @x, Dy, P px, yq. Dx, @y, P px, yq. Dx, Dy, P px, yq. Ejemplo 1.29. . 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. 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.

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

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.

 ta´rbol, ave, zapato, chancletau C  t1, 3, 5, 7, 9u C  tn P N | n es un n´ umero d´ıgito imparu D  tn P Z | n es un n´ umero d´ıgitou D  t0, 1, 2, . . . , 9u E  t11, 12, 13, . . . u E  tn P N | n ¡ 10u F  tx P R | x2  3x 2  0u F  t1, 2u

2. B 3. 4. 5. 6. 7. 8. 9. 10.

2.1.

(forma expl´ıcita) (forma descriptiva)

(forma expl´ıcita abreviada)

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.

15

Matem´aticas discretas (M. Mata)

2.2.

16

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 elemento de A pertenecen a B. Tambi´en, si A „ B, se dice que B contiene a A y se escribe B … A. Observaci´ on 2.3. Si A entonces: @x P A, x P B.

„ B, entonces: x P A ñ x P B. Tambi´en, si A „ 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.4. Sean A  tn P Z | n es paru y B  tn P Z | n es m´ ultiplo de cuatrou. Demuestre que B „ A. (Recuerde que n es m´ ultiplo de k si existe m P Z tal que n  km). Ejercicio 2.5. Sean A  tn P N | 1 13, n es primou. ¿A „ B o B „ A?

  n   14, n es imparu y B  tn P N | n ¤

Definici´ on 2.6. 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. Definici´ on 2.7. 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.8. 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.9. . 1. En geometr´ıa, U es el plano. 2. En estudios poblacionales, U es toda la gente del mundo.

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

Matem´aticas discretas (M. Mata)

17

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.10. . 1. A  tn P Z | n2 2.

 16, n es imparu  ∅. B  tx P R | x2 1  0u  ∅.

3. Sea C el conjunto de personas de m´as de 140 a˜ nos. ¿C

 ∅?

Ejercicio 2.11. 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.12. . 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.13. . 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: 2016.09.02)

Matem´aticas discretas (M. Mata)

2.5.

18

Conjunto potencia

Ejercicio 2.14. Sea S

 ta, b, cu, escribir todos sus posibles subconjuntos.

Definici´ on 2.15. El conjunto de todos los posible subconjuntos de un conjunto A es llamado conjunto potencia de A, y se denota por P pAq. Ejemplo 2.16. Sea A  ta, b, cu, entonces P pAq  t∅, tau, tbu, tcu, ta, bu, ta, cu, tb, cu, Au. Ejercicio 2.17. Si A es un conjunto finito con n elementos, ¿cu´antos elementos tiene el conjunto P pAq? Ejercicio 2.18. Calcular P p∅q. Observe que t∅u  ∅.

2.6. 2.6.1.

Operaciones con conjuntos Uni´ on

Definici´ on 2.19. 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: AYB

2.6.2.

 tx | x P A _ x P B u.

Intersecci´ on

Definici´ on 2.20. 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: AXB

2.6.3.

 tx | x P A ^ x P B u.

Diferencia

Definici´ on 2.21. 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 B u.

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

Matem´aticas discretas (M. Mata)

2.6.4.

19

Complemento

Definici´ on 2.22. El complemento de un conjunto A, expresado por Ac , es el conjunto de todos los elementos que no pertenecen a A:

 tx | x P U ^ x R Au. Ejercicio 2.23. 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. C zA 7. AzC 8. B zpA Y C q Ac

Ejemplo 2.24. Demostrar (por las definiciones) que: 1. pA X B qc 2.

 Ac Y B c B zA  B X Ac

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

Matem´aticas discretas (M. Mata)

2.6.5. 1 2 3 4 5 6 7 8 9

20

Propiedades de los conjuntos AYAA AXAA AYB BYA AXB BXA A Y pB Y C q  pA Y B q Y C A X pB X C q  pA X B q X C A Y pB X C q  pA Y B q X pA Y C q A X pB Y C q  pA X B q Y pA X C q pA Y B qc  Ac X B c pA X B qc  Ac Y B c pAcqc  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.25. Demostrar, por medio de las propiedades, que: 1. pAzB qc 2. 3. 4.

 Ac Y B. A Y pA X B q  A. pAzB q X B  ∅. A X pB zC q  pA X B qzpA X C q.

2.6.6.

Propiedades de las cardinalidades

1. |∅|  0. 2. Si A „ B, entonces |A| ¤ |B|. 3. |A Y B|  |A|

|B|  |A X B|.

4. |A Y B| ¥ m´axt|A|, |B|u. 5. |A X B| ¤ m´ınt|A|, |B|u. ¡Material en construcci´on! (versi´on: 2016.09.02)

Matem´aticas discretas (M. Mata)

21

Ejercicio 2.26. Demostrar por medio de las propiedades que: 1. Si A  B, entonces |A|  |B|. 2. Si A X B 3. 4.

 ∅, entonces |A Y B|  |A| |A| |Ac |  |U |. |AzB|  |A|  |A X B|.

2.7.

|B|.

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.27. Representar mediante el diagrama de Venn las siguientes condiciones: 1. A y B no se intesectan 2. A „ B Ejemplo 2.28. 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.29. Verificar mediante un diagrama de Venn: A „ B

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

ñ A X B  A.

Matem´aticas discretas (M. Mata)

2.7.1.

22

Conteo mediante diagramas de Venn

Ejemplo 2.30. 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.31. 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: 2016.09.02)

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.

 t0, 1u. Sea Σ  N.

4. Sea B 5.

Ejercicio 3.4. Investigar sobre los siguientes alfabetos: 1. ASCII. 2. ISO 8859-1 (Lat´ın 1). 3. UTF-8. 23

Matem´aticas discretas (M. Mata)

3.2.

24

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 y 01.

 t0, 1u, las siguientes son posibles cadenas sobre B: 10010, 001, 10

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:

 aabcad β  015 08 1

1. β 2.

3. λ ¡Material en construcci´on! (versi´on: 2016.09.02)

Matem´aticas discretas (M. Mata)

3.2.1.

25

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 βα.

 0110, escribir λγ y γλ. Sean ε  x10 z 9 y 13 y δ  y 8 x7 , escribir εδ y δε.

2. Sea γ 3.

Ejercicio 3.17. . 1. Si α P A y β 2.

P B , ¿a qu´e conjunto pertenece αβ? 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.

 x10z9y13, ¿cu´ales de las siguientes son una subcadena de β? α1  x2 y 3 . α2  x10 z 10 . α3  zy.

2. Dado β a) b) c)

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: 2016.09.02)

Matem´aticas discretas (M. Mata)

3.2.3.

26

Potencia de una cadena

Definici´ on 3.23. Dados β β reiterada n veces:

P A y n P N, se define β n como la concatenaci´on de βn

 βββ β . loooomoooon n veces

Notaci´ on 3.24. Por convenci´on, suele definirse β 0

 λ.

Ejercicio 3.25. Sea β una cadena, demuestre las siguientes:

 β n m. |β n |  n|β|. |β n m |  |β n |

1. β n β m 2. 3.

3.2.4.

|β m |.

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

3.3.

 β R αR .

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: 2016.09.02)

Matem´aticas discretas (M. Mata)

3.3.1.

27

Operaciones entre lenguajes

Dado que los lenguajes son conjuntos, todas las operaciones de conjuntos pueden aplicarse a ellos. Ejemplo 3.33. 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

3.3.2.

 ΣzA. Concatenaci´ on de lenguajes

Definici´ on 3.34. Dados dos lenguajes A y B, la concatenaci´on de A con B, denotada por AB, se define como AB

 tαβ | α P A, β P B u

. Observaci´ on 3.35. Observe que, en general, AB

3.3.3.

 BA.

Reflexi´ on de un lenguaje

Definici´ on 3.36. Dado L un lenguaje, la reflexi´on de L, denotada por LR , se define como LR  tβ R | β P Lu . Ejercicio 3.37. Sean A y B dos lenjguajes sobre Σ, decir si las siguientes afirmaciones son verdaderas: 1. pAB qR 2. 3. 4.

 B R AR . pA Y B qR  AR Y B R . pA X B qR  AR X B R . pAR qR  A. ¡Material en construcci´on! (versi´on: 2016.09.02)

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: AB

 tpa, bq | a P A ^ b P B u. 28

Matem´aticas discretas (M. Mata)

29

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 pA  B q X pB  Aq.

4.1.3.

 t2, 3, 4u,

escribir explicitamente el conjunto

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, . . . , anq | a1 P A1, a2 P A2, . . . , an P Anu donde a cada elemento pa1 , a2 , . . . , an q se le llama n-upla ordenada. De igual manera, dado A un conjunto, An

4.1.4.

 tpa1, a2, . . . , anq | a1, a2, . . . , an P Au.

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: 2016.09.02)

Matem´aticas discretas (M. Mata)

30

Ejemplo 4.8. . 1. T pp _ q q  tp1, 1q, p1, 0q, p0, 1qu. 2. T ppp Ñ q q ^ pq

Ñ rqq  tp1, 1, 1q, p0, 1, 1q, p0, 0, 1q, p0, 0, 0qu.

Ejercicio 4.9. . 1. T pp Ø q q. 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 2. 3. 4.

_ Qq  T pP q Y T pQq. T pP ^ Qq  T pP q X T pQq. T p P q  T pP qc . 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 a  21  ..  .

a12 a22 .. .



 

a13 a23 .. .

a1n 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

donde, por ejemplo, a21



?

A



2 y a13

?1 2  5.

3 0

5 2

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 Fmn . ¡Material en construcci´on! (versi´on: 2016.09.02)

Matem´aticas discretas (M. Mata)

4.2.1.

31

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, 

a11

a12 a22 .. .

a  21  ..  .

a13 a23 .. .

am1 am2 am3

 

...



t

a1n a2n   ..  . amn

Observaci´ on 4.16. Observe que pAt qt

4.2.2.



a11 a21 a  12 a22   a13 a23  .. ..  . . a1n a2n



  

am1 am2   am3   ..  .

...



amn

 A.

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 las siguientes son matrices diagonales: 

5 0 A 0 0 

3  C 0 0

0 8 0

0 3 0 0

0 0 2 0





6 0  0 1

0 0 B  0 0 0 0



0 0 0 0 2 0

D





π 0

?0



0 0 1

3

E





4

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. ¡Material en construcci´on! (versi´on: 2016.09.02)

Matem´aticas discretas (M. Mata)

32

Ejemplo 4.22. La matriz identidad 3  3: 



1 0 0 I3  0 1 0 0 0 1

4.2.4.

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



8 0 3  1 2 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 una matrices triangulares inferior y superior, respectivamente: 

3 4 A 5 9

0 7 0 3

0 0 1 2



0 0  B 0 6



1 0  0 0

4 2 0 0

5 3 1 0



8 0  2 6

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

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

Matem´aticas discretas (M. Mata)

4.2.6.

33

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: 2016.09.02)

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 2. 3.

 t1, 2, 3u y R  tpa, 2q, pa, 3q, pb, 3qu Sean A  t1, 2, 3, 4u, B  t3, 4, 5, 6, 7, 8u y R  tpa, bq P A  B | b  2au. 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 pb, 1q R R denotan b R{ 1 y se lee ((b no est´a en relaci´on con 1)) o ((b no se relaciona 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 graficamente en un sistema de coordenadas cartesiano o por medio de un grafo.

34

Matem´aticas discretas (M. Mata)

35

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 representaci´on gr´afica.

5.1.2.

 t1, 2, 3, 4, 5u y R  tpa, bq P A2 | a ¤ bu. Hacer su

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 A  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: 2016.09.02)

Matem´aticas discretas (M. Mata)

5.1.3.

36

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 b   2au. Encontrar Dom R y Ran R.

 t3, 4, 5, 6, 7, 8u y R  tpa, bq P A  B |

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 R1 , es una relaci´on de B a A que se define como sigue: R1

 tpb, aq | pa, bq P Ru.

Ejemplo 5.14. .

1. R  tp1, 2q, p1, 3q, p2, 3qu. R1  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 R1  tpb, aq | b es m´as bajo que au. 3. Sea R  tpp, q q pq  2q{3u.

P Q2 | q  3p

2u, entonces R1

 tpq, pq P Q2 | p 

Ejercicio 5.15. Sea R  tp1, 2q, p1, 3q, p2, 1q, p2, 3qu: ¡Material en construcci´on! (versi´on: 2016.09.02)

Matem´aticas discretas (M. Mata)

37

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

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 a  b, entonces pb, aq R R.

PRy

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: 2016.09.02)

Matem´aticas discretas (M. Mata)

5.2.1.

38

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 pxq el conjunto de los polinomios de grado menor o igual a n. Sean ppxq y q pxq dos polinomios en Pn pxq y sea R la relaci´on que se define mediante la regla ((ppxq R q pxq si y s´olo si ppxq y q pxq 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 el valor de a m´odulo n como el residuo que queda al dividir a entre n. Suponiendo que el residuo de dividir a entre n es r, se denota a m´od n  r. 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 m´od n. 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 disjuntos.

X Xj  ∅ se llaman

 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

Ejemplo 5.26. Sea X

partici´on de X?:

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

Matem´aticas discretas (M. Mata) 1. 2. 3. 4.

39

tr0, 21 s, r 12 , 1su tr0, 21 q, r 12 , 1su tr0, 21 s, p 12 , 1su 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, 2q, p2, 1q, 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: 2016.09.02)

Matem´aticas discretas (M. Mata)

40

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

A ÝÑ B. f

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 2.

 ta, b, cu. Sea f  tp1, aq, p2, cq, p3, cqu. Sean A  Z y B  N. Sea f pz q  z 2 1.

Ejercicio 5.40. Diga si las siguientes son funciones: 1. Sean A  ta, b, c, d, eu y B 2. 3. 4. 5. 6.

 A. Sea f  tpa, bq, pb, cq, pc, dq, pe, aqu. Sean A  ta, b, c, d, eu y B  A. Sea f  tpa, eq, pb, eq, pc, eq, pd, eq, pe, equ. Sean A  ta, b, c, d, eu y B  A. Sea f  tpa, bq, pb, cq, pc, dq, pb, eq, pe, aqu. Sean A  Z y B  N. Sea f pz q  z 3 3. Sean A  Z y B  N. Sea f pz q  z 4 . Sean A  Z y B  t0, 1u. Sea f definida como: f pz q  0 si z es par y f pz q  1 si z es impar.

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

Matem´aticas discretas (M. Mata)

41

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. Observaci´ on 5.42. Si f es una funci´on, entonces Dom f riamente Ran f  B (aunque forzosamente Ran f „ B).

 A, pero no necesa-

Observaci´ on 5.43. Dos funciones f y g, son iguales si y s´olo si f paq  g paq para todo a P A. ¿Cu´ando dos funciones son distintas? Ejercicio 5.44. Sean f pxq  x y g pxq 

?

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 g pxq  rxs. 1. ¿Son f pxq y g pxq funciones? 2. ¿Son f pxq y g pxq iguales? Observaci´ on 5.46. En la mayor´ıa de las implementaciones computacionales se define la funci´on de truncamiento como Truncpxq 

# txu rxs

si x ¥ 0, si x   0,

y la funci´on de redondeo como Roundpxq 

5.3.1.

#

Truncpx 0.5q si x ¥ 0, Truncpx  0.5q si x   0.

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).

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

Matem´aticas discretas (M. Mata)

42

Definici´ on 5.47. 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. Ejemplo 5.48. Graficar las siguientes funciones: 1. Sean A  ta, b, c, d, eu y B 2. 3.

 A. Sea f  tpa, bq, pb, cq, pc, dq, pd, cq, pe, aqu. Sean A  Z y B  Z. Sea f pz q  2z  1. Sean A  Z y B  N. Sea f pz q  z 2 1.

e d c

5

10

4

9

3

8

2

7

1

3 2 1

b a

6

0

1

2

5

3

1

4

2

3

3

2

4

a

b

c

d

1

5

e

3 2 1

0

1

2

3

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

Observaci´ on 5.49. 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 g pf paqq, el cual es un elemento de C, ya que C es el contradominio de g. Definici´ on 5.50. 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  g pf paqq. f A

g B

C

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

Matem´aticas discretas (M. Mata)

43

Ejemplo 5.51. Sean A  ta, b, cu, B  t1, 2, 3u y C  tx, y, z u. Sean f : A Ñ B y g : B Ñ C las siguientes: f  tpa, 2q, pb, 3q, pc, 2qu y g  tp1, xq, p2, z q, p3, xqu. ¿Son f y g funciones? ¿Qui´en es g  f ? Ejemplo 5.52. Sean f : R Ñ R y g : R Ñ R definidas como sigue: f pxq g pxq  x 3. ¿Son f y g funciones? ¿Qui´en es g  f ? ¿Qui´en es f  g? Observaci´ on 5.53. Se debe tener cuidado de no confundir g  f con f el ejemplo 1 ni siquiera existe f  g).

5.3.3.

 x2 y

 g. (En

Funciones inyectivas y sobreyectivas

Definici´ on 5.54. 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.55. 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

Definici´ on 5.56. Se dice que una funci´on f : A inyectiva y sobreyectiva.

Ran f

 B.

Ñ B es biyectiva si y s´olo si es

Ejercicio 5.57. Decir si las siguientes funciones son inyectivas, sobreyectivas, biyectivas o ninguna: 1. Sea A  ta, b, c, d, eu y f : A Ñ A, f 2. f : Z Ñ Z,

 tpa, bq, pb, cq, pc, dq, pd, cq, pe, aqu.

f pz q  2z  1

3. f : R Ñ R0 , 4. f : R Ñ R,

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

Ejercicio 5.58. Demostrar las siguientes afirmaciones: 1. La composici´on de dos funciones inyectivas es inyectiva. 2. La composici´on de dos funciones sobreyectivas es sobreyectiva.

 g es inyectiva, entonces g es inyectiva. Si f  g es sobreyectiva, entonces f es sobreyectiva.

3. Si f 4.

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

Matem´aticas discretas (M. Mata)

5.3.4.

44

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.59. 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. Ejemplo 5.60. 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.61. Para que f 1 sea una funci´on, es necesario que f sea biyectiva. Ejercicio 5.62. Sea f : Q biyectiva?, ¿cu´al su inversa? Ejercicio 5.63. Dada f

Ñ

Q dada por f pxq

4

c

3

b

2

a

1 2

 2. ¿Es funci´on?, ¿es

f 1

5

d

1

3x

 tp1, bq, p2, dq, p3, eq, p4, aq, p5, cqu, graficar f y f 1.

f

e



3

4

5

a

b

c

d

e

Observaci´ on 5.64. 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.65. 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.

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

Matem´aticas discretas (M. Mata)

45

Observaci´ on 5.66. Dada f : A Ñ B cualquier funci´on, entonces: IB  f Observaci´ on 5.67. Si f : A funci´on inversa, entonces: f 1  f

 f  I  f. A

Ñ B es una funci´on biyectiva y f 1 : B Ñ A su

 f 1  I . Observaci´ on 5.68. Si f es biyectiva, pf 1 q1  f . Observaci´ on 5.69. Si |A|  n, entonces la representaci´on matricial de la funci´on I

A

y

f

B

identidad IA es la matriz identidad In .

Observaci´ on 5.70. 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: 2016.09.02)

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 n1 , 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  p1qn 3. p2, 4, 6, 8, . . . q 

4.

n2 n 2

6.1.1.



P

n N

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. 46

Matem´aticas discretas (M. Mata)

47

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 ,

 1

2.

pp ¥ 1q

P

n n N

 nn 1 S  p2, 4, 6, 8, . . . q sn  p1qn

3. sn 4. 5.



6.



n n2 2



8

7. pn2  2n qn1

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 es una subsucesi´on de S.

 ps2, s4, s6, . . . q

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: 2016.09.02)

Matem´aticas discretas (M. Mata)

48

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. .

 n  fn1. Dado a ¡ 0, ga p0q  1 y ga pnq  a  ga pn  1q. F0  0, F1  1 y Fn  Fn1 Fn2 .

1. f0 2. 3.

1

6.3.

y fn

Notaci´ on Sigma

Una suma de 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 ¸



a2k1

k 1

Ejercicio 6.16. Calcular el resultado de las siguientes sumas:

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

Matem´aticas discretas (M. Mata)

1.

5 ¸

49

3i



i 2

2.

4 ¸



pj

1q2

j 1 5 ¸

3.



p2k  1q

k 1

4.

888 ¸



p1qi

i 1

5.

n ¸

1



i 1

Teorema 6.17. Sean pan q y pbn q dos sucesiones y c una constante, entonces las siguientes propiedades se cumplen: 1.

n ¸

c ai



c

i 1

2.

n ¸



n ¸



pai

bi q 

i 1

3.

n ¸



i 1

6.4.

ai

i 1 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 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.

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

Matem´aticas discretas (M. Mata)

50

Paso base: Demostrar que existe un n´ umero inicial k0 para el cual se cumple la propiedad deseada. Ejemplo 6.18. Considere la siguiente sucesi´on. Sea Sn Demuestre que, para todo n P N se cumple que: Sn

1

2

3

 npn2 1q .

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

n ¸

i2



 npn

i 1

1qp2n 6

1q

2. n! ¥ 2n ¿cu´al es la base? 3. 4.

5.

@n P N se cumple que 5n  1 es divisible por 4. n ¸ rn 1  1 ri  r1 i0 n ¸



p2k  1q  n2

k 1

6. 7.

@n P N se cumple que n3  n es divisible por 3. n ¸ npn 1qpn 2q k pk 1q  3



k 1

8.

n ¸



i3

i 1

9.

n ¸



i 1

i4

2 2  n pn4 1q

 npn

1qp2n

1qp3n2 30

10. Si h ¡ 1, entonces p1

hqn

3n  1q

¥1

nh (desigualdad de Bernoulli).

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



n.

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)). 51

Matem´aticas discretas (M. Mata)

52

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, n!  Teorema 7.9. Prn

#

1 si n  0, 1  2  . . .  n si n P N.

 npn  1qpn  2q    pn  r

1q 

n!

pn  rq!

Ejercicio 7.10. Calcular P47 . Ejercicio 7.11. Demostrar que Pnn

7.2.1.

 n!.

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: 2016.09.02)

Matem´aticas discretas (M. Mata)

7.3.

53

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 C pn, rq, n Cr o Cn,r . n

Teorema 7.17. Crn

 Pr!r  r!pnn! rq!

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

7.4.

 Cnn1  n.

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: 2016.09.02)

Matem´aticas discretas (M. Mata)

54 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

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 ¡Material en construcci´on! (versi´on: 2016.09.02)

Matem´aticas discretas (M. Mata)

55

(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 r

Observaci´ on 7.24.



n r

 Crn

Ejemplo 7.25. Demostrar que

7.5.1.

 r!pnn! rq!



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: 2016.09.02)

Matem´aticas discretas (M. Mata)

56

1 1 1

1 1 1

7

3 4

5 6

1



2

1 1



1 3



1

6

4

10 10



1



5

15 20 15

1



6

1

21 35 35 21

7



6 0

7 1

6 1

5 1



7 2

1 0











7 0

1

5 0

4 0

3 0

2 0

2 1





3 1

4 1



0 0

5 2

6 2

7 3





4 2

6 3



1 1

3 2

 











2 2

4 3

5 3

5 4

6 4

7 4









3 3



7 5

4 4



6 5



5 5





6 6

7 6



7 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 coeficientes bino1. miales observe que el k-´esimo elemento de la n-´esima fila es nk 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 r

Teorema 7.26.

7.5.2.







n1 . r

n1 r1

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 . Teorema 7.27. pa

bq

n



n ¸





r 0

Ejemplo 7.28. Desarrollar pa

pa

bq6

 a6

6a5 b

n nr r a b. r bq6 . 15a4 b2

20a3 b3

15a2 b4

6ab5

b6 .

Ejercicio 7.29. Desarrollar p2x  3y q5 . Ejemplo 7.30. Demostrar que Ejercicio 7.31. Demostrar que





n 0



n 0

n 1





n 1



n 2



n 2





n n

 2n.

    p1qn



n n

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

 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, E q 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, E q 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. 57

Matem´aticas discretas (M. Mata)

58

Un grafo no dirigido si el conjunto E est´a formado por parejas no ordenadas de elementos de V , es decir, E „ ttu, v u | 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 t3, 3u, t3, 4u, t4, 5uuq:

 pt1, 2, 3, 4, 5u, tt1, 2u, t2, 4u, t2, 5u,

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, v q 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, v q 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, v q y pv, wq est´an en el grafo, ¿entonces pu, wq tambi´en pertenece al grafo?

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

Matem´aticas discretas (M. Mata)

8.2.

Definiciones b´ asicas

8.2.1.

Incidencia y adyacencia

59

Definici´ on 8.8. Dado un arco a  pu, v q, 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, v q es llamado bucle. Una arista de la forma tv, v u 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. Ejemplo 8.14. Poner un par de ejemplos. . . Definici´ on 8.15. 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. Observaci´ on 8.16. Toda cadena (o camino) elemental es simple. Definici´ on 8.17. Un ciclo es una cadena que inicia y termina en el mismo v´ertice.

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

Matem´aticas discretas (M. Mata)

60

Definici´ on 8.18. En un grafo dirigido, un circuito es un camino que inicia y termina en el mismo v´ertice. Definici´ on 8.19. Todo circuito es un ciclo. Ejemplo 8.20. Poner un par de ejemplos. . . 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: 2016.09.02)

Matem´aticas discretas (M. Mata)

8.3.3.

61

´ 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, E q es bipartito si existe una partici´on de V , tV1, V2u, 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.

8.4.

Predecesores, sucesores y grados

Definici´ on 8.37. El conjunto de v´ertices predecesores de un v´ertice v se define por Γ pv q  tu | pu, v q P E u.

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

Matem´aticas discretas (M. Mata)

62

Definici´ on 8.38. El conjunto de v´ertices sucesores de un v´ertice v se define por Γ pv q  t w

| pv, wq P E u.

Definici´ on 8.39. El grado entrante de v se define por g  pv q  |Γ pv q|. El grado saliente de v se define por g pv q  |Γ pv q|. El grado de v se define por g pv q  g  pv q g pv q. Observaci´ on 8.40. En el c´alculo del grado, un bucle se cuenta dos veces.

8.5.

Representaciones matriciales

Definici´ on 8.41. La matriz de incidencia de un grafo G  pV, E q, con |V | y |E|  m es una matriz n  m tal que cada elemento eij est´a dado por:

n

$ ' & 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.42. La suma de cada columna de la matriz de incidencia es cero. Definici´ on 8.43. La matriz de adyacencia de un grafo G  pV, E q, con |V |  n es una matriz n  n tal que cada elemento aij est´a dado por: aij



#

1 si el arco pi, j q P E, 0 si el arco pi, j q R E.

Observaci´ on 8.44. La suma de cada fila de la matriz de adyacencia es g

 t1, 2, 3, 4, 5u y E  tp1, 2q, p2, 5q, p3, 2q, p3, 4q, p5, 1q, p5, 4qu: Graficar G  pV, E q.

Ejemplo 8.45. Dados V 1.

piq.

2. Escribir la matriz de incidencia. 3. Escribir la matriz de adyacencia.

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

Get in touch

Social

© Copyright 2013 - 2024 MYDOKUMENT.COM - All rights reserved.