Matematicas Discretas tomo 1

ELEMENTOS DE LOGICA´
Y TEORIA DE CONJUNTOS´
Dra. Patricia Kisbye
Dr. Alejandro L. Tiraboschi

3
INTRODUCCION´
Estas notas han sido elaboradas con el objetivo de ofrecer al ingresante a las carreras de la FaMAF un curso introductorio a la lo´gica elemental y teor´ıa de conjuntos. Los temas abarcados son, a grandes rasgos, nociones ba´sicas de conjuntos, operaciones entre conjuntos yproducto cartesiano; proposiciones, conectivos lo´gicos y cuantificadores. Gran parte de los contenidos y ejercicios han sido extra´ıdos de los primeros cap´ıtulos de nuestras notas Elementos de Logica y´ Computacion´ , Trabajos de Informa´tica, No. 1/99.
Cada cap´ıtulo contiene un desarrollo teo´rico, variados ejemplos y una completa lista de ejercicios de aplicacio´n.
Alejandro Tiraboschi
PatriciaKisbye

Indice general´
Cap´ıtulo 1. TEOR´IA BASICA DE CONJUNTOS´ 7
1. Conjuntos y pertenencia 7
2. Subconjuntos 9
3. Ejercicios 15
Cap´ıtulo 2. OPERACIONES ENTRE CONJUNTOS 19
1. La unio´n de conjuntos 19
2. La interseccio´n 20
3. Complemento de un conjunto 21
4. Diferencia 22
5. Ejercicios 24
Cap´ıtulo 3. PRODUCTO CARTESIANO 27
1. Pares ordenados y producto cartesiano 27
2.Representacio´n en ejes cartesianos 28
3. Ejercicios 31
Cap´ıtulo 4. LOGICA´ 35
1. Proposiciones 35
2. Conectivos lo´gicos 36
3. Negacio´n 36
4. Conjuncio´n 37
5. Disyuncio´n 38
6. Los conectivos y las operaciones entre conjuntos 39
7. Propiedades de la conjuncio´n y la disyuncio´n 39
8. Ejercicios 40
Cap´ıtulo 5. CUANTIFICADORES 43
1. Funciones proposicionales 43
2. Cuantificadores 44
3.Negacio´n de cuantificadores 45
4. Ejercicios 46
5
INDICE GENERAL
Cap´ıtulo 6. OTROS CONECTIVOS 47
1. Condicional o implicacio´n 47
2. Bicondicional o doble implicacio´n 48
3. Argumentos y demostraciones 49
4. Combinacio´n de proposiciones con conectivos lo´gicos 50
5. Ejercicios 51
CAP´ıTULO 1
TEORIA B´ ASICA DE CONJUNTOS´
Cualquier coleccio´n de objetos o individuos se denominaconjunto. En el contexto de la matema´tica, el te´rmino conjunto no tiene una definicio´n sino que es un concepto primitivo. Ejemplos de conjuntos son el conjunto de los nu´meros naturales, de los televisores de la ciudad de Co´rdoba y de los peces en los oce´anos. Nuestro objetivo sera´ estudiar aquellos conjuntos que esta´n relacionados con el campo de la matema´tica, especialmente los conjuntosnume´ricos. La teor´ıa de conjuntos es fundamental en matema´tica y de suma importancia en informa´tica, donde encuentra aplicaciones en a´reas tales como inteligencia artificial, bases de datos y lenguajes de programacio´n.
1. Conjuntos y pertenencia
Un conjunto esta´ integrado por objetos y los objetos que integran el conjunto se llaman elementos de ese conjunto. Ejemplos de conjuntos son lossiguientes:
El conjunto de los nu´meros enteros.
El conjunto de los nu´meros naturales mayores que 5 y menores que 9.
El conjunto formado por los estudiantes de primer an˜o de la Fa.M.A.F.
El conjunto formado por un punto P en el plano y las rectas que pasan por e´l.
Un conjunto sin elementos se denomina conjunto vac´ıo.
En general usaremos letras mayu´sculas para designar a los conjuntos yletras minu´sculas para designar a sus elementos. Si a es un elemento de un conjunto A se escribe a ∈ A y se lee a pertenece a A o a es un elemento de A. Si a no es un elemento del conjunto A se escribe a 6∈ A y se lee a no pertenece a A o a no es elemento de A. Los s´ımbolos N, Z, Q y R servira´n para denotar a los siguientes conjuntos:
N: el conjunto de los nu´meros naturales.
Z: el conjunto delos nu´meros enteros.
Q: el conjunto de los nu´meros racionales.
R: el conjunto de los nu´meros reales.
Definir un conjunto es describir de una manera precisa, sin ambigu¨edades, cua´les son los elementos de dicho conjunto. Existen distintas maneras de definir un conjunto. La forma ma´s
7
1. TEOR
simple, pero que no siempre es posible, es por extension´ , es decir listando todos los...