T.S.U. en Informatica

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.1 El lenguaje coloquial . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . .

1

1.2 El lenguaje simb´lico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
o

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 Formas argumentativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.7 Consecuencias sem´nticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
a
1.8 Formas proposicionales normales

. . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.9 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2Conjuntos

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.9Principio 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.7Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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´n binaria . . . . . . . . . . . . . . . . . . . . . . . . . 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...