Matemática discreta

MATEMATICA DISCRETA
Versi´n preliminar o

Departamento de Matem´tica a Universidad Nacional del Sur

Material elaborado por
• • • •

Estela Bianco Aldo V. Figallo Claudia Sanza Alicia N. Ziliani
Bah´ Blanca 2004 ıa

´ Indice General
1 Introducci´n informal a la l´gica matem´tica o o a 1.1 El lenguaje coloquial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Ellenguaje simb´lico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 1 1 9

1.3 Tautolog´ contradicciones y contingencias . . . . . . . . . . . . . . . . . . . . 17 ıas, 1.4 Equivalencia sem´ntica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 a 1.5 Conjunto adecuado de conectivas . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.6 Formasargumentativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.7 Consecuencias sem´nticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 a 1.8 Formas proposicionales normales . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.9 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2 Conjuntos 36

2.1 Introducci´n . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 o 2.2 El conjunto vac´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 ıo 2.3 Descripci´n gr´fica de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 o a 2.4 Subconjuntos de un conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.5 El conjunto de las partes de un conjunto .. . . . . . . . . . . . . . . . . . . . . 43 2.6 Operaciones con conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.7 Diagramas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.8 Propiedades de las operaciones conjuntistas . . . . . . . . . . . . . . . . . . . . 49 2.9 Principio de inclusi´n y exclusi´n . . . . . . . . . . . . . . . . . .. . . . . . . . 49 o o 2.10 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3 Relaciones y funciones 56

3.1 Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2 Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 Relaciones n−arias . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 61 3.4 Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.5 Producto directo de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.6 Conjuntos coordinables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 81

i

4 Multigrafos y multidigrafos

92

4.1 Multigrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.2 Arboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.3 Arboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.4 Multidigrafos . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 111 4.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5 Relaciones binarias especiales 124

5.1 Relaciones binarias entre los elementos de un conjunto . . . . . . . . . . . . . . 124 5.2 Digrafos y relaciones binarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.3 P −clausura de una relaci´nbinaria . . . . . . . . . . . . . . . . . . . . . . . . . 127 o 5.4 Clausuras: reflexiva, sim´trica, transitiva . . . . . . . . . . . . . . . . . . . . . . 131 e 5.5 Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.6 Relaci´n de equivalencia asociada a una funci´n . . . . . . . . . . . . . . . . . . 133 o o 5.7 Relaci´n de equivalencia asociada a una...