Editado porVernica Gruenberg Stern

Apuntes de

MAT021 - Complementos vs. 1 sem. 2014

Prefacio

Estimados alumnos:

Este texto ha sido desarrollado especialmente para ustedes, y es el resultado del aporte de muchoscolegas del Departamento de Matemtica de la Universidad Tcnica Federico Santa Mara, quea lo largo del tiempo han dictado este curso. Las diferentes secciones incorporan, adems de lospropios, apuntes de profesores tanto de Casa Central como del Campus Santiago, especialmen-te Nelson Cifuentes, Pedro Gajardo, Vctor Gonzlez y Erwin Hernndez. En esta versin, losapuntes que hemos tomado de ellos han sido editados por quien suscribe, para enfatizar aquellosaspectos que nos parecen relevantes y unificar notacin y enfoque. Adems, la estructura del apun-te incorpora no solo los contenidos que se espera conozcan en profundidad, sino que tambin unagran cantidad de ejercicios resueltos y propuestos, que esperamos resuelvan con entusiasmo, pa-ra lograr mejores aprendizajes. Hemos optado tambin por incluir muchas demostraciones de losteoremas que revisarn en clases. No es el objetivo que todas stas sean vistas en clases. Ms bien,esperamos que los alumnos interesados, tengan la posibilidad de profundizar en la aprehensin delos conceptos involucrados, y de comprender cmo se realiza la construccin del conocimiento ma-temtico. Esperamos que esta segunda versin, an preliminar, les sea de utilidad, y que cualquiererror que an persista y encuentren (por cierto, involuntario), nos sea informado al mail indicadoabajo. Hemos incorporado varias de las correcciones que nos han hecho llegar, y agradecemos latarea silenciosa y meticulosa de quienes as lo han hecho.

Una concepcin equivocada respecto a la forma de enfrentar un curso en la Universidad, proba-blemente producto de su experiencia previa, es que piensan que el estudio debe enfocarse solo a laresolucin de problemas tipo y que no se debiera revisar los conceptos . Deben tener presenteque queremos que resuelvan todos los problemas, no slo un cierto tipo. Para lograr ese nivelde dominio, los estudiantes deben comprender los conceptos y deben desarrollar la habilidad desaber cuando y cmo aplicarlos en situaciones diversas. Otro error es pretender concentrar el estu-dio un par de das antes de cada certamen. Las habilidades y competencias que sern evaluadas,en general requieren tiempo de construccin y de maduracin, por lo que les recomendamos fuer-temente estudiar clase a clase, desarrollando los ejercicios planteados en los apuntes y tambin enlas guas de ejercicios.

I

PREFACIO Vernica Gruenberg Stern

Es importante que tengan presente que, aunque hemos intentado incluir todo el material peda-ggico relevante, este apunte no reemplaza las clases. Nada se compara a la interaccin que seproduce en el aula, tanto con sus profesores como con sus compaeros. La discusin de los con-ceptos y la contrastacin de diversos puntos de vista fortalece la comprensin de los mismos. Pero,para argumentar adecuadamente y lograr un buen aprendizaje de los conceptos e ideas que con-sidera este curso, es fundamental que asistan a clases, participen activamente en ella, estudien demanera metdica, ojal estructurando un horario de estudio diario, preparndose siempre para suprxima clase y que planteen a sus profesores cualquier duda que les surja.

Cordialmente,

Vernica Gruenberg SternDepartamento de Matemtica

Universidad Tcnica Federico Santa Mara

veronica.gruenberg@usm.cl

II

ndice general

Prefacio I

ndice general III

1. Nociones bsicas de Lgica y Conjuntos 11.1. Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Conectivos Lgicos y Tablas de Verdad . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3. lgebra de Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4. Nociones Bsicas de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5. lgebra de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.6. Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.7. Conjunto Potencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251.8. Producto Cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.9. Cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291.10. Ejercicios Miscelneos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331.11. Ejercicios de Controles y Certmenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2. Nociones Bsicas de Relaciones 392.1. Relaciones de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.2. Relaciones de Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.3. Ejercicios de Controles y Certmenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3. Nmeros Naturales 493.1. Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493.2. Induccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.3. Sumas y Productos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.3.1. Notacin: Sumatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613.3.2. Notacin: Productoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.4. Progresiones Aritmticas y Geomtricas . . . . . . . . . . . . . . . . . . . . . . . . . . 703.5. Teorema del Binomio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

III

NDICE GENERAL

3.6. Ejercicios de Controles y Certmenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4. Trigonometra 81

4.1. Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.2. Funciones Trigonomtricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.3. Identidades Fundamentales en el tringulo . . . . . . . . . . . . . . . . . . . . . . . . 87

4.3.1. Suma y resta de ngulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

4.4. Identidades Trigonomtricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.5. Resolucin de Tringulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.6. Grficas de las Funciones Trigonomtricas . . . . . . . . . . . . . . . . . . . . . . . . . 96

4.6.1. Funciones sinusoidales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4.7. Funciones Trigonomtricas Inversas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.8. Ecuaciones Trigonomtricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4.8.1. Ecuaciones de la forma a senx+ b cosx = c . . . . . . . . . . . . . . . . . . . . 102

4.9. Ejercicios de Controles y Certmenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4.10. Propiedades trigonomtricas bsicas (resumen) . . . . . . . . . . . . . . . . . . . . . . 107

5. Funciones Exponencial y Logaritmo 109

5.1. Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

5.2. Funcin Exponencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

5.3. Funcin Logaritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.3.1. Bases 10 y e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.3.2. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5.4. Ejercicios de Controles y Certmenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

6. Geometra Analtica 117

6.1. Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6.2. Distancia entre dos Puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.2.1. Divisin Interior de un trazo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.3. La Recta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

6.3.1. Distancia de un punto a una recta . . . . . . . . . . . . . . . . . . . . . . . . . 125

6.4. Secciones Cnicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

6.4.1. La Circunferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

6.4.2. La Elipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

6.4.3. La Parbola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

6.4.4. La Hiprbola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

6.5. Ejemplos y Ejercicios de Lugares Geomtricos . . . . . . . . . . . . . . . . . . . . . . 132

6.6. Ejercicios de Controles y Certmenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

IV

NDICE GENERAL

7. Nmeros Complejos y Polinomios 1397.1. Nmeros Complejos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

7.1.1. Operaciones con nmeros complejos . . . . . . . . . . . . . . . . . . . . . . . . 1407.1.2. Conjugado y Mdulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1417.1.3. Forma Polar de un Nmero Complejo . . . . . . . . . . . . . . . . . . . . . . . 1437.1.4. Teorema de de Moivre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1457.1.5. Races n-simas de un nmero complejo . . . . . . . . . . . . . . . . . . . . . 1467.1.6. Forma Exponencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

7.2. Polinomios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1507.2.1. Estructura algebraica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1527.2.2. Races . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1537.2.3. Funciones Polinomiales y Racionales . . . . . . . . . . . . . . . . . . . . . . . 1557.2.4. Algoritmo de la Divisin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1557.2.5. Divisin Sinttica (Regla de Ruffini) . . . . . . . . . . . . . . . . . . . . . . . . 1567.2.6. Polinomios Irreductibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1617.2.7. Descomposicin en Fracciones Parciales . . . . . . . . . . . . . . . . . . . . . . 161

7.3. Ejercicios de Controles y Certmenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

V

NDICE GENERAL

VI

Captulo 1

Nociones bsicas de Lgica y Conjuntos

1.1. Introduccin

La lgica matemtica es el estudio del lenguaje utilizado en matemtica. Lo que distingue ala matemtica de otras ciencias, es el uso de demostraciones en lugar de observaciones. Demostrarun teorema significa lograr deducir usando reglas, a partir de un pequeo nmero de axiomas, elresultado que se desea. Estos axiomas traducen al lenguaje matemtico las propiedades ms evi-dentes de los objetos que interesan, y la sucesin de silogismos por medio de los que se pasa delos axiomas (o ms prcticamente, de teoremas ya establecidos) a una aseveracin dada, constituyeuna demostracin del teorema.

Los axiomas debern referirse a objetos tan bsicos, que no requieran de una definicin especialy que sin embargo sean comprensibles y aceptables para cualquiera. Estos objetos bsicos se deno-minan en lgica conceptos primitivos. Los conceptos primitivos que manejaremos en esta seccinson tres: proposicin (aseveracin), el valor lgico V y el valor lgico F . En lugar de estos valoreslgicos, podramos utilizar las palabras verdadero y falso. Sin embargo, stas tienen sentidodependiendo del contexto que se est considerando. Por ejemplo, en la geometra euclidiana, laafirmacin: por cada punto fuera de una recta pasa una nica recta paralela a ella es verdadera,pero sto no es as en la geometra hiperblica.

Las proposiciones que consideraremos debern satisfacer la llamada ley del tercero excludo,que afirma que cada proposicin debe tener un slo valor lgico (V o F ). Este hecho determina quenuestra lgica matemtica sea binaria. Notemos que este principio, que a priori podra parecertrivial, no lo es tanto, ya que nuestro lenguaje habitual nos permite construir proposiciones (afir-maciones) que pueden tomar ambos valores de verdad. Considere, por ejemplo, la afirmacin

Yo siempre miento.

Si estoy diciendo la verdad, entonces miento en mi afirmacin. Es decir, sta es falsa. Si lo que digoes falso, entonces lo que afirmo es verdadero.

Es fundamental por tanto, conocer las principales leyes de la lgica matemtica, que regulan lacorreccin de los argumentos matemticos. Desarrollaremos aqu los conceptos de verdad, equi-valencia, consecuencia lgica y algunas aplicaciones al razonamiento matemtico.

1

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

Teniendo presentes las consideraciones anteriores, iniciamos la formalizacin de estas ideas.

DEFINICIN 1.1.1 Una proposicin es una expresin, aseveracin o sentencia de la cual se puedeafirmar inequvocamente que es verdadera (V) o falsa (F). Denotaremos las proposiciones median-te letras minsculas p, q, r etc.

EJEMPLOS: Cules de las siguientes expresiones son proposiciones?

1. 8 es menor que 3.

2. Compra 3 panes.

3. El dgito 218 de la expansin decimal de pi es un nmero par.

4. La silla tiene 5 patas.

5. Aprobar este curso?

6. x+ 3 = 7

7. Qu bonito!

8. Existe un nico nmero natural que tiene por inverso multiplicativo otro nmero natural.

9. 2+5

Antes de seguir adelante, queremos ilustrar el uso del principio del tercero excluido en unasdemostraciones. Para ello, consideremos las siguientes proposiciones.

PROPOSICIN 1.1.1 Si a2 es un nmero par, entonces a es un nmero par.

Demostracin:Sabiendo que a2 es par, queremos demostrar que a tambin es un nmero par. Por el principio

del tercero excluido, la afirmacin a es par puede tomar slo uno de los valores de verdad V oF .

Supongamos que es F . Luego a debe ser impar, por lo que existe un nmero ` N tal quea = 2`+ 1. Por lo tanto:

a2 = (2`+ 1)2 = 4`2 + 4`+ 1 = 2(2`2 + 2`) + 1

de donde se concluye que a2 es un nmero impar, que obviamente contradice la hiptesis.Por lo tanto, la suposicin de que a es impar toma el valor de verdad F . As, por el principio

del tercero excluido, no hay otra posibilidad excepto que la proposicin a es par sea V .

2

Vernica Gruenberg Stern 1.1. INTRODUCCIN

PROPOSICIN 1.1.2

2 no es un nmero racional.

Demostracin:

Supongamos que la afirmacin

2 no es un nmero racional es F . Por lo tanto,

2 es unnmero racional. Esto significa que existen nmeros enteros a, b 6= 0 sin divisores en comn, talque

2 = ab . Luego, elevando esta igualdad al cuadrado, tenemos que: 2 =

a2

b2, de donde

a2 = 2b2, es decir que a2 es un nmero par. Por la proposicin anterior, esto significa que a espar, o sea, hay un nmero c Z tal que a = 2c. Reemplazando este valor de a en la igualdadanterior, obtenemos (2c)2 = 2b2, es decir, 4c2 = 2b2, de donde b2 = 2c2. Luego b2 es par ypor lo tanto b tambin es un nmero par.

Tenemos entonces que tanto a como b son nmeros pares, es decir, tanto a como b son divisiblespor 2. Pero, al suponer que

2 es un nmero racional es V , elegimos a y b sin divisores en co-

mn. Luego, por el principio del tercero excluido, necesariamente

2 no es un nmero racionales V .

Usualmente en las demostraciones no se hace referencia al principio del tercero excluido en for-ma explcita, como hemos hecho en ambas demostraciones. Simplemente se observa que, debidoa que la falsedad de la afirmacin lleva a concluir la falsedad de alguna hiptesis, y esto ltimo nopuede ser, entonces la proposicin ha de ser verdadera. Esto se hace notar escribiendo contradiccin(con alguna hiptesis) en el lugar en que ello acaece. Ilustremos esto en la siguiente

PROPOSICIN 1.1.3 En la geometra euclidiana se tiene que: dos rectas L1 y L2 perpendiculares aotra recta L3, son paralelas entre s. (Considere conocido que la suma de los ngulos interiores deun tringulo es igual a 180).

Demostracin:

Supongamos que L1 y L2 no son paralelas entre s. Por lo tanto, las rectas L1, L2 y L3 formanun tringulo.

Pero, si L1 y L3 son perpendiculares entre s, entonces el ngulo que ellas forman es de 90.Anlogamente para L2 y L3, es decir, al ngulo formado por L2 y L3 es de 90.

Luego, al ngulo formado por L1, L2 slo puede ser 0, debido a que la suma de los ngulosde un tringulo es de 180. Esto contradice el supuesto de que L1, L2 y L3 forman un tringulo.Luego queda probada la afirmacin.

Note que el argumento se basa fuertemente en que la suma de los ngulos interiores de untringulo es 180. Si hubiese una geometra en la cual esta suma fuese mayor que 180, el razona-miento fallara. . . y dicha geometra existe!

3

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

1.2. Conectivos Lgicos y Tablas de Verdad

Estudiaremos a continuacin la forma de construir nuevas proposiciones a partir de una, dos oms proposiciones dadas, para formar una nueva. Esto se har definiendo algunas operaciones queconsistirn en modificar o combinar mediante ciertos conectivos lgicos las proposiciones bsicas.Entenderemos por conectivos lgicos a ciertos smbolos que nos permitirn relacionar dos o msproposiciones de modo tal que se genere una nueva.

DEFINICIN 1.2.1 Sean p y q dos proposiciones lgicas, entonces se definen los siguientes conecti-vos lgicos y sus correspondientes valores de verdad:

Conjuncin Disyuncin Implicacin Equivalencia Negacin Disyuncincondicional bicondicional exclusiva

p y q; p o q p implica q; p si y solo si q; no p solo p o solo qtanto p como p si p entonces q p equivale a q

p q p q p q p q p q p p Y q

V V V V V V F FV F F V F F F VF V F V V F V VF F F F V V V F

OBSERVACIN: En algunos textos se utiliza la notacin p o p para la negacin de p.

DEFINICIN 1.2.2 Sern proposiciones simples aquellas que no incluyen conectivos lgicos. Sernproposiciones compuestas aquellas que los incluyen.

EJEMPLO 1.2.1 Considere las siguientes proposiciones simples

p : 5 es mayor que 7

q : 4 es divisible por 2

Escriba en palabras las proposiciones p q, p q y (p q) q. Cules son sus valores deverdad?

DEFINICIN 1.2.3 Si p, q, r, s, etc. son smbolos que no denotan proposiciones especficas, llamare-mos forma proposicional a cualquier expresin finita que se pueda construir con tales smbolos ylos conectivos lgicos.

4

Vernica Gruenberg Stern 1.2. CONECTIVOS LGICOS Y TABLAS DE VERDAD

OBSERVACIN: Toda forma proposicional tiene asociada una tabla de verdad.

Es decir, con estas operaciones podemos formar formas proposicionales de compleja estructura,como por ejemplo:

1. (p q) r.

2. [s {(p q) r}] q.

en donde los parntesis tienen un objetivo obvio. Cabe hacer notar que en este punto estamosfrente al problema de contar. En 1, tenemos tres proposiciones bsicas p, q, r. Al construir la tablade verdad correspondiente a (p q) r, cuntas posibles alternativas tiene para combinar losvalores de verdad de p, q, r? Y en 2? Si tuviera n proposiciones, cuntas filas tendra su tabla deverdad?

EJEMPLOS: Construya la tabla de verdad de las formas proposicionales:

1. (p q) (p q)

2. (p q) r.

3. [(p q) (q r)] (p r)

DEFINICIN 1.2.4 Las formas proposicionales se pueden clasificar de la siguiente manera:

1. Tautologa si obtiene el valor lgico V (verdadero) para cualquier sustitucin (de valor deverdad) de las proposiciones que la componen.

2. Contradiccin si obtienen el valor lgico F (falso) para cualquier sustitucin (de valor deverdad) de las proposiciones que la componen.

3. Contingencia si no es tautologa ni contradiccin.

DEFINICIN 1.2.5 Dos proposiciones p y q (simples o compuestas) son lgicamente equivalentessi el bicondicional entre ambas es una tautologa. En tal caso, denotamos el bicondicional por y escribiremos p q.

EJEMPLOS: Demuestre las siguientes equivalencias:

1. p q [(p q) F ]

2. [p q r] [(p r) (q r)]

3. [p q r] [(p r) (q r)]

5

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

OBSERVACIN: Es importante tener presente que las proposiciones pueden ser afirmaciones demuy diversos mbitos, entre ellas expresiones matemticas.

DEFINICIN 1.2.6 Se dice que una proposicin p implica lgicamente a una proposicin q si p qes una tautologa.

DEFINICIN 1.2.7 Sean p1, p2, . . . , pn, q proposiciones. Diremos que q es una consecuencia lgicade las premisas p1, p2, . . . , pn si p1 p2 pn implica lgicamente a q.

EJEMPLO 1.2.2 Muestre que (p (p q)) q es una tautologa, y que por lo tanto, q es una con-secuencia lgica de las premisas p y (p q).

p

p q premisas

q conclusin

Solucin: Construimos la tabla de verdad

p q (p q) (p (p q)) (p (p q)) qV V V V VV F F F VF V V F VF F V F V

de donde obtenemos que (p (p q)) q es una tautologa.

6

Vernica Gruenberg Stern 1.3. LGEBRA DE PROPOSICIONES

1.3. lgebra de Proposiciones

PROPOSICIN 1.3.1 Sean p, q y r proposiciones lgicas, entonces se tienen las siguientes:

Nombre Propiedad

Identidad p V p , p F F , p V V , p F p

Idempotencia p p p , p p p

Involucin (p) p

Complemento p p F , p p V

Conmutatividad p q q p , p q q p

Asociatividad p (q r) (p q) r , p (q r) (p q) r

Distributividad p (q r) (p q) (p r) , p (q r) (p q) (p r)

Leyes de Morgan (p q) p q , (p q) p q

Transitividad [(p q) (q r)] (p r)

Absorcin [p (p q)] p , [p (p q)] p

Dejamos como ejercicio la demostracin, mediante el uso de tablas de verdad, de estas propie-dades.

7

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

PROPOSICIN 1.3.2 Sean p y q proposiciones lgicas; entonces, se cumplen las siguientes:

1. (p q) (p q)

2. (p q) (q p)

3. (p q) [(p q) F ]

Demostracin:

Haremos las correspondientes tablas de verdad:

1.p q p p q p q (p q) (p q)V V F V V VV F F F F VF V V V V VF F V V V V

2.p q p q p q q p (p q) (q p)V V F F V V VV F F V F F VF V V F V V VF F V V V V V

3.p q q p q p q p q F (p q) [(p q) F ]V V F V F V VV F V F V F VF V F V F V VF F V V F V V

OBSERVACIN: Las dos ltimas tautologas reflejan fuertemente el principio del tercero excluido,y por ello son muy usadas en las demostraciones de proposiciones o teoremas. Usar la equivalen-cia q p para demostrar una afirmacin p q, se llama mtodo de la contrarecproca dedemostracin, y utilizar la equivalencia [(p q) F ] se conoce como mtodo de reduccin alabsurdo.

8

Vernica Gruenberg Stern 1.3. LGEBRA DE PROPOSICIONES

EJEMPLOS:

1. Usando propiedades, determine el valor de verdad de la proposicin

[(p q) (p r)] = [q (p r)]

sabiendo que p (q r) es falsa.Solucin: Como p (q r) es falsa, necesariamente el valor de verdad de p es V y elvalor de verdad de q r es F. Luego, tanto q como r son F. Luego, p q es F y p r es F.As, [(p q) (p r)] toma el valor F y por lo tanto la proposicin propuesta es V.

2. Para qu valores de x R la proposicin x < 0 = x2 < 0 es verdadera?Solucin: Como x R, existen tres posibilidades:

a) Si x > 0, entonces x < 0 es F la proposicin es V.b) Si x = 0, entonces x < 0 es F la proposicin es V.c) Si x < 0, entonces x < 0 es V. Como x2 < 0 es F, se tiene que la proposicin es F.

Luego, la proposicin es verdadera para todos los valores x 0.

No queremos dejar pasar la oportunidad de mostrar cmo se pueden usar las tautologas ante-riores en razonamientos de la vida diaria, y tambin cmo ellas permiten desnudar ciertas falacias.Consideremos los siguientes

EJEMPLOS:

1. (Lewis Carroll) Pruebe que el siguiente razonamiento es vlido:

a) Todas las cartas fechadas en esta habitacin estn escritas sobre papel azul.

b) Ninguna est escrita con tinta negra, excepto aquellas escritas en tercera persona.

c) No he archivado ninguna de las que puedo leer.

d) Ninguna de las que estn escritas en una hoja estn sin fecha.

e) Todas las que no estn eliminadas estn en tinta negra.

f ) Todas las escritas por Prez empiezan con Estimado seor.

g) Todas las escritas en papel azul estn archivadas.

h) Ninguna de las que estn escritas en ms de una hoja estn eliminadas.

i) Ninguna de las que empiezan con Estimado Seor estn escritas en tercera persona.

No puedo leer ninguna de las cartas de Prez.

9

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

Solucin: Consideremos las proposiciones

p : la carta est fechadaq : la carta est escrita en papel azulr : la carta est escrita con tinta negras : la carta est escrita en tercera personat : la carta est archivadau : puede leer la cartav : la carta est escrita en una hojaw: la carta est eliminadax : la carta est escrita por Prezy : la carta empieza con Estimado Seor

Simblicamente el razonamiento anterior se expresa:

a) p qb) s rc) u t ( (t u))d) v pe) w rf ) x yg) q th) v w ( (w v))i) y s

x u

Basta ahora poner las premisas en el orden adecuado:

f) i) b) e) h) d) a) g) c)

y entonces la conjuncin de las premisas queda:

(x y) (y s) (s r) (r w) (w v) (v p) (p q) (q t) (t u)

de donde, aplicando sucesivamente la transitividad, obtenemos x u.

10

Vernica Gruenberg Stern 1.3. LGEBRA DE PROPOSICIONES

2. Demuestre que el siguiente razonamiento constituye una falacia:

Si el Sr. Ramrez es honesto y capaz, entonces tendr un puesto importante en su empresa.

El Sr. Ramrez es el subgerente de su empresa.

Por lo tanto, el Sr. Ramrez es honesto y capaz.

Solucin: Smbolicamente, este razonamiento tiene la forma: ((p q) q) pEscribiendo la correspondiente tabla de verdad se ve de inmediato que el argumento no esvlido, pero, si se dice rpidamente y con energa suena bastante convincente.

EJERCICIOS:

1. Simplifique utilizando propiedades.

a) [p (q r)] (p q)b) (p q) [(p r) (q r)]

c) [p (p q)] pd) [p (p q)] q

2. Si [(p q) (r t)] es una proposicin falsa, determine el valor de verdad de(r t) (q r).

3. Sean u y v nmeros enteros, y considere las siguientes proposiciones:

p : u > 0, q : v < 0, r : u2 > 0, s : v2 > 0

Exprese las siguientes proposiciones en el lenguaje natural, y determine su valor de verdad,sabiendo que las cuatro proposiciones son verdaderas:

a) p pb) p rc) q s

d) s qe) p rf ) r s

g) r ph) s pi) r p

4. Considere las proposiciones:

p : dos es par, q : dos es impar, r : tres es par, s : tres es impar

Exprese simblicamente:

a) Si dos no es par entonces tres es par y dos es impar.

b) No slo dos no es par sino que tampoco es impar.

c) Si tres no es impar entonces dos no es par.

d) Dos es par si y solamente si dos no es impar.

11

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

5. En los siguientes, determine la validez de los razonamientos:

a) Siempre que llueve hay humedad; hoy llovi. Luego, hay humedad

b) Los burros tienen orejas; X tiene orejas. Luego, X es burro.

c) Siempre hay pollo o pato; hoy no hubo pollo. Luego, hoy hubo pato.

d) Si voy a Acapulco es que fui de vacaciones; no fui a Acapulco. Luego, no fui de vacacio-nes.

e) Si las chicas son risueas, entonces son populares entre los chicos.

Las chicas serias no son populares entre los chicos.

Las chicas intelectuales son serias.

Por lo tanto, las chicas risueas no son intelectuales.

f ) Si estudio, entonces no reprobar este curso.

Si no twiteo muy seguido, entonces estudiar.

Reprob este curso.

Por lo tanto, twiti muy seguido.

6. Escriba simblicamente la afirmacin: Si repruebo MAT021, entonces no estudi y me deprimo.Luego, niegue la afirmacin y traduzca al lenguaje usual dicha negacin.

7. Demuestre las siguientes afirmaciones:

a) Si a y b son pares, entonces a2 + b2 es divisible por 4.

b) Si a y b son impares, entonces a2 + b2 es par pero no es divisible por 4.

c) Si un nmero natural no es par entonces no es mltiplo 10.

d) Si a y b son enteros positivos tales que a b = 100 entonces a 10 o b 10.e) Si el producto de dos enteros par, entonces al menos uno de ellos es par.

8. Identifique en cada una de las siguientes afirmaciones la hiptesis y la tesis, y luego demues-tre o refute cada una:

a) Si la suma de dos nmeros naturales es divisible por 7, entonces cada sumando es divi-sible por 7.

b) Si dos nmeros naturales son divisibles por 7, su suma es divisible por 7.

12

Vernica Gruenberg Stern 1.4. NOCIONES BSICAS DE CONJUNTOS

1.4. Nociones Bsicas de Conjuntos

El concepto de conjunto es una de las ideas ms importantes de la matemtica del siglo XX,aunque aparentemente no hay nada especialmente geomtrico o cuantitativo en este concepto quepudiera indicarnos que es algo intrnsicamente matemtico. Sin embargo, esta sencilla nocin hainfluido todos los aspectos de esta ciencia, empezando con el trabajo del matemtico alemn GeorgCantor (18451918), quien fue un pionero en este tema.

El concepto de conjunto es un concepto primitivo, pero puede ser considerado como una colec-cin de elementos u objetos. Estos elementos pueden tener o no tener caractersticas en comn. Unade las peculiaridades que ms diferencia a los conjuntos que se tratan en matemtica de los deotras reas es el uso de notacin simblica. Denotaremos a los conjuntos por letras maysculas. Siun objeto a se encuentra en un conjunto A, diremos que a es un elemento de A o que a pertenece a A,y escribiremos a A. Si a no est en A o no pertenece a A, escribiremos a / A.

Es claro entonces que un conjunto estar completamente determinado (o definido), cuandodispongamos de algn medio para decidir si un objeto cualquiera est o no en l. Esto puedehacerse de varias formas (notar que siempre usaremos un parntesis de llave para agrupar a loselementos de un conjunto):

1. Listndolos todos. Por ejemplo:A = {u, v, w}Esta forma de definir un conjunto se llama definicin por extensin.

2. Listando algunos elementos representativos.B = {1, 2, 3, 4, 5, . . . }Esta forma de definir un conjunto no es matemticamente rigurosa pues puede llevar a equ-vocos; sin embargo, es bastante utilizada precisamente cuando el contexto es claro.

3. Dado un conjunto de referencia U cualquiera, al que llamaremos universo de referencia, pode-mos definir un conjuntoC como aquel formado por los elementos de U que satisfacen algunapropiedad. Por ejemplo, si U = N = B del ejemplo anterior, podemos definir:

a) C = {x N : x es un nmero primo}b) D = {x N : x es un nmero par}

Esta forma de definir un conjunto se llama definicin por comprensin.

La pregunta que surge de manera natural es cmo decidir cundo dos conjuntos son iguales.

13

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

Para ello, consideremos los siguientes ejemplos:

A = {x Z : x2 = x} y B = {0, 1}A = {0, 1, 5, 8} y B = {5, 1, 8, 0}A = {a, b, c} y B = {a, b, c, a, b, c, a, b}

Por simple inspeccin, pareciera claro que en cada caso los elementos deA yB son los mismos,no importando:

por qu va se definen

el orden en que los elementos sean dados

la cantidad de veces en que los elementos se repitan.

Por ello, diremos que dos conjuntos A y B son iguales cuando tienen exactamente los mismoselementos. As, en cada caso del ejemplo anterior tenemos que A = B. Dicho de otra forma, A = Bsignifica que si x A, entonces se tiene que x B y, recprocamente, si x B entonces tambinx A.

Pero bien podra suceder que slo una de las dos aserciones anteriores se satisfaga. Diremos eneste caso que un conjunto A est contenido en (o es subconjunto de) un conjunto B si, y slo si, cadaelemento x A satisface que x B. Denotaremos esta relacin por A B. Si un conjunto A noest contenido en un conjunto B, escribimos A * B.

Ms formalmente:

DEFINICIN 1.4.1 Sean A,B conjuntos. Diremos que :

1. A es subconjunto de B, y escribimos A B si y slo six A x B, para todo elemento x A.

2. A = B si y slo si (A B B A). Lo anterior tambin se puede expresar como:

x A x B

3. A est propiamente contenido en B si, y slo si, A B, pero A 6= B. A veces se escribe A Ben este caso.

DEFINICIN 1.4.2 Sea U un universo referencial, y sea A U . Llamaremos conjunto vaco, de-notado por , al conjunto que no tiene elementos.

A pesar de su obvia trivialidad, este ltimo conjunto tiene varias propiedades interesantes,cuyas demostraciones nos permitirn introducirnos ms de lleno al mundo del razonamiento ma-temtico.

14

Vernica Gruenberg Stern 1.4. NOCIONES BSICAS DE CONJUNTOS

PROPOSICIN 1.4.1 El conjunto vaco es subconjunto de cualquier conjunto.

Demostracin: Sea A un conjunto cualquiera. Entonces, o bien A, o bien * A.Si A, entonces tenemos lo que queramos probar.Luego, supongamos que * A. Esto significa que debe existir un elemento x con x / A. Pero no tiene elementos por lo que tal x no puede existir. Por tanto, nuestra suposicin de que * Aes imposible de donde A.

La demostracin anterior puede parecer un tanto extraa cuando se mira por primera vez, pe-ro es un tpico ejemplo del razonamiento involucrado para probar que el conjunto vaco satisfacealguna propiedad. Como no tiene elementos, no hay en l ninguno que refute la propiedad, dedonde satisface dicha propiedad vacamente!

ILUSTRACIN: Pruebe que los elementos de son negros.Demostracin:

Si todos los elementos de son negros, entonces no hay nada que probar. Supongamos entoncesque no todos los elementos de son negros. Esto quiere decir que hay un elemento x que noes negro. Pero no tiene elementos, por lo que tal x no puede existir. Por tanto, el supuesto de quehay un elemento que no es negro es imposible, de donde todos los elementos de son negros!

Claramente, de manera anloga, puede probarse que los elementos de son de cualquier color!

Notar que hablamos insistentemente de el conjunto vaco. Esto se justifica en lo siguiente:

COROLARIO 1.4.1 El conjunto vaco es nico.

Demostracin:Supongamos que el conjunto vaco no es nico, es decir, al menos hay dos conjuntos vacos.

Sean y estos dos conjuntos vacos. Queremos probar que = . Por la proposicin 1.4.1, como es vaco entonces , y como es vaco, entonces . Luego = .

15

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

1.5. lgebra de Conjuntos

En esta seccin especificaremos algunas operaciones de la teora de conjuntos que permitenconstruir nuevos conjuntos a partir de otros ya conocidos.

DEFINICIN 1.5.1 Sean A y B subconjuntos de un universo referencial U . Definimos:la unin de A y B (denotado por A B) como el conjunto formado por todos los elementosde A y todos los elementos de B. Es decir,

A B = {x U / x A x B}

la interseccin de A y B (denotado por A B) como el conjunto formado por todos los ele-mentos que estn en A y en B. Es decir,

A B = {x U / x A x B}

la diferencia deA yB (denotado porAB) como el conjunto formado por todos los elementosque estn en A y no en B. Es decir,

AB = {x A / x / B}

el complemento de A, denotado por Ac, al conjunto formado por todos los elementos de U queno estn en A. Es decir,

Ac = U A = {x U / x / A}

OBSERVACIN: Podemos notar de inmediato que

AB = A Bc.

c = U

Uc = Adems, A y B se dicen disjuntos si A B = .

EJEMPLOS:

1. Sean A = {a, b, c}, B = {b, c} y C = {d}. Entonces

A B = {a, b, c}, A B = {b}, AB = {a} y A C =

2. Considere los conjuntos: A = {x R/ 5 |x|}, B = {x R / x2 + 6 = 7x},C = {x R / 7 x 3}, D = y E = R. Determine:B C, A C, A B, B C, A E, B E, D A y A C.

16

Vernica Gruenberg Stern 1.5. LGEBRA DE CONJUNTOS

PROPOSICIN 1.5.1 Sean A,B y C conjuntos en un universo de referencia U . Entonces se cumple:

1. A B Bc Ac.

2. A B = A B = A A B = B.

3. A B B C = A C

4. A B A A B

Demostracin:

1. Debemos probar que

A B Bc AcEn efecto: sea x Bc. Luego: x 6 B

ABx 6 A x Ac

Bc Ac A BEn efecto: sea x A. Luego: x 6 Ac

BcAcx 6 Bc x B

2. Debemos probar que

A B = A B = AEn efecto:A B A x A B x A x B x AA B A x A

ABx B x A B

A B = A B = BEn efecto:A B B x A B x A x B

ABx B

A B B x B x A B

3. Sea x A. Como A B, se tiene que x B. Como B C, se tiene que x C.

4. Debemos probar:

A B AA A B

que dejamos como ejercicio.

17

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

OBSERVACIN: Notamos que existe una estrecha relacin entre la notacin de la lgica y la de lateora de conjuntos. En la siguiente tabla se ilustran las analogas que se pueden establecer entrelos smbolos (operaciones) utilizados en lgica y en conjuntos.

Lgica V F p (Proposicin) pConjuntos U A (Conjunto) = Ac

PROPIEDADES 1.5.1 Sean A,B y C conjuntos. Se tienen las siguientes propiedades:

Nombre Propiedad

Identidad A U = A , A = , A U = U , A = A

Idempotencia A A = A , A A = A

Involucin (Ac)c = A

Complemento A Ac = , A Ac = U

Conmutatividad A B = B A , A B = B A

Asociatividad A (B C) = (A B) C , A (B C) = (A B) C

Distributividad A (B C) = (A B) (A C) , A (B C) = (A B) (A C)

Leyes de de Morgan (A B)c = Ac Bc , (A B)c = Ac Bc

18

Vernica Gruenberg Stern 1.5. LGEBRA DE CONJUNTOS

EJEMPLOS:

1. Mostrar que (A C) (B C) = (A B) C.

Dem. (A C) (B C) = (A Cc) (B Cc) = (A B) Cc = (A B) C

2. Mostrar que (A C) (B C) = (AB) C.Dem. (A C) (B C) = (A Cc) (B Cc)c = (A Cc) (Bc C) =

= [(A Cc) Bc] [(A Cc) C)] = [(A Cc) Bc] = (AB) C

3. Una embotelladora fabrica tres bebidas gaseosas. Se sabe que hay personas que toman slouna de ellas, otras que toman slo dos de ellas y otras que toman indistintamente cualquierade las tres. Construya un modelo conjuntista que permita describir esta situacin.

Solucin: Sean

A = {personas que toman la bebida 1}B = {personas que toman la bebida 2}C = {personas que toman la bebida 3}

Es claro entonces que podemos considerar como universo de referencia a aquellas personas queson consumidores de la embotelladora, lo cual en trminos de los conjuntos recin definidosqueda:

U = A B C = {consumidores de la embotelladora}

Las personas que beben indistintamente cualquiera de los tres productos, son las que estnen los 3 conjuntos simultneamente, es decir:

R1 = A B C = {personas que toman las 3 bebidas}

Las personas que beben slo las bebidas 1 y 2, estn en los conjuntos A y B pero no en C.Luego

R2 = (A B) C = {personas que toman slo bebidas 1 y 2}Anlogamente

R3 = (A C)B = {personas que toman slo bebidas 1 y 3}R4 = (B C)A = {personas que toman slo bebidas 2 y 3}

19

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

EJERCICIOS:

1. Describa los siguientes conjuntos por extensin:

a) A = {X {1, 2, 3} : X {4, 5, 6} {1, 3, 4, 5, 6}}b) B = {C {, {}} : C {} = {}}

2. Simplifique utilizando propiedades:

a) [A (A B)c] [B (B Cc)]c Bcb) [A (AB)] Bc) [(A Bc) (ABc)]c Ac

3. Demuestre:

a) B A A (B C) = Ab) (A B) (A B) = (B A) (AB)c) [A B A B = ] A =

Las operaciones que hemos definido entre conjuntos pueden representarse mediante los llama-dos diagramas de Venn, en que los conjuntos se representan por regiones. En la figura, A y B serepresentan por los crculos izquierdo y derecho respectivamente, y la zona pintada correspondea la operacin que se indica:

A B A B

Ac B A

20

Vernica Gruenberg Stern 1.6. CUANTIFICADORES

1.6. Cuantificadores

Ampliaremos ahora las posibilidades de generar proposiciones, introduciendo primeramenteel concepto de funcin proposicional.

DEFINICIN 1.6.1 Sea U el conjunto universo en un contexto dado. Entendemos por funcin propo-sicional a una aseveracin o expresin que contiene una o ms variables, con la propiedad siguiente:al reemplazar la(s) variable(s) por elementos especficos pertenecientes a U , se obtiene una propo-sicin.

EJEMPLOS:

1. Sea U = {Los seres humanos}. Entonces, p (x) = x es jugador de ftbol es una funcinproposicional. Note que: p (Alexis Snchez) es una proposicin verdadera, perop (Nicols Mass) es una proposicin falsa.

2. Sea U = R. Entonces, p (x) = |x| 5 es una funcin proposicional. Note que p (6) esverdadera y p (3) es falsa.

3. Sea U = Z. Entonces p(x) : x2 1 = 0 es una funcin proposicional. Note que la definimosutilizando : para evitar confusiones con el signo igual en la proposicin.

4. Sea U = {rectas en el plano}. Entonces q(x, y) : x y es una funcin proposicional.

Notar que tambin se obtienen proposiciones si en lugar de reemplazar la(s) variable(s) por al-gn objeto especfico del universo referencial, se cuantifica el nmero de elementos del universoque satisfacen la propiedad. Por ejemplo:

(1) Existe un x en el universo con la propiedad x2 1 = 0.

(2) Todos los x en el universo tienen la propiedad x2 1 = 0.

Si nuestro universo son los nmeros enteros, (1) es V y (2) es F . Los smbolos usados paracuantificar son:

: Cuantificador existencial, que se lee existe un o existe al menos un. : Cuantificador universal, que se lee todos los o para todo o para cada.

As, las proposiciones anteriores se escriben simblicamente:

(1) x U : x2 1 = 0

(2) x U : x2 1 = 0

21

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

Adems, cuantificamos el hecho de que uno y slo un elemento del universo, satisfaga unapropiedad, con el cuantificador existencial acompaado de un signo de exclamacin: ! , que se leeexiste un nico.

Para ver cmo cuantificar en el caso en que se tengan 2 o ms variables, volvamos al ejemplo 4.anterior en que consideramos el universo como las rectas de un plano, y la funcin proposicional

q(x, y) : x es perpendicular a y

Como q(x, y) contiene dos variables, es necesario anteponer dos cuantificadores. Por ejemplo:

(1) (x U)( y U) : q(x, y) Existe un par de rectas en U que son perpendi-culares.

(2) (x U)( y U) : q(x, y) Existe una recta que es perpendicular a cual-quier otra.

(3) (x U)( y U) : q(x, y) Para cada recta en U , existe al menos una quees perpendicular a ella.

(4) (x U)( y U) : q(x, y) Las rectas en U son perpendiculares entre s.

Notamos de inmediato que (1) y (3) son V , en cambio (2) y (4) son F . Queremos resaltar eneste punto la diferencia existente entre (2) y (3), de donde podemos concluir de inmediato que loscuantificadores de distinto tipo no pueden ser intercambiados entre s, o, no conmutan.

Hemos vista ya que dada un proposicin, la negacin de sta define una nueva proposicincuyo valor de verdad es el contrario a la proposicin bsica. La pregunta obvia ahora es: cmonegar una proposicin que est escrita en trminos de cuantificadores?

Observemos que negar la existencia de un objeto con determinada propiedad p significa aceptarque ningn objeto posee dicha propiedad, o que, todos los objetos no poseen la propiedad. Portanto:

x U : p(x) x U : p(x)

Por ejemplo, si

U : alumnos de MAT021p(x) : x es rubio,

entonces x U : p(x) se traduce como hay un alumno de MAT021 que es rubio. La negacinde este hecho es que ningn alumno de MAT021 es rubio, o, de otro modo, todos los alumnosson no rubios.

22

Vernica Gruenberg Stern 1.6. CUANTIFICADORES

Al revs, negar que todos los objetos de un universo satisfacen cierta propiedad, equivale aaceptar que a lo menos uno de ellos no la satisface, es decir:

x U : p(x) x U : p(x)En el ejemplo anterior: x U : p(x) dice que todos los alumnos de MAT021 son rubios.Negar esto, es aseverar que hay un alumno de MAT021 que no es rubio.

Para negar la existencia de un nico elemento que satisface una propiedad p, se debe ser cui-dadoso: deber considerarse la negacin tanto de la existencia como de la unicidad, es decir:

(!x U) : p(x) [(x U), p(x)] [(x, y U , x 6= y) : p(x) p(y)]

En el ejemplo anterior: !x U : p(x) dice que hay slo un alumno de MAT021 que es rubio.Negar esto, es aseverar que ningn alumno de MAT021 es rubio o bien que al menos dosalumnos de MAT021 son rubios.

Podemos resumir las observaciones anteriores de la siguiente manera:

Negacin de Cuantificadores

(x U), p(x) (x U), p(x).

(x U), p(x) (x U), p(x).

(!x U), p(x) [(x U), p(x)] [(x, y U), x 6= y : p(x) p(y)]

OBSERVACIN: La negacin de proposiciones con 2 o ms variables, se obtiene de manera similar;por ejemplo:

(x U)( y U) : q(x, y) (x U)(y U) : q(x, y)En sntesis, para negar una proposicin cuantificada (sin unicidad), se debe cambiar el cuanti-

ficador y negar la funcin proposicional.

23

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

EJERCICIOS:

1. Dadas las siguientes funciones proposicionales

p(x) : 2x 10 20q(x) : |x| < 40

a) Determine explcitamente los conjuntos

A = {x R / p(x) q(x) es Verdadero }B = {x R / p(x) q(x) es Falso }

b) Encuentre AB.

2. Sea A = {1, 2, 3}. Determine el valor de verdad de:

a) x A y A : x+ y = 3b) x A y A : x+ y = 3c) x A y A : x+ y = 3d) x A y A : x+ y Ae) x A : x+ 1 6 Af ) x A : x+ 1 6 A

3. Sea A = {1, 2, 3}. Determine el valor de verdad de

(x A) (y A) (x+ y A x y 1)

y negar la proposicin.

4. Para las siguientes definiciones obtenga su negacin

a) Un conjunto A R se dice acotado si: (M R+)(x A) : |x| Mb) Una funcin f : R R se dice continua en x0 si:

> 0 > 0 x R : 0 < |x x0| < |f(x) f(x0)| <

5. Demuestre que A U : A = .

24

Vernica Gruenberg Stern 1.7. CONJUNTO POTENCIA

1.7. Conjunto Potencia

Un conjunto nuevo interesante que puede construirse a partir de un conjunto A dado, esel llamado conjunto potencia de A, que denotaremos por P(A). Este conjunto ser aquel formadopor todos los subconjuntos del conjunto A. Se llama a veces tambin conjunto de las partes de A.Formalmente,

DEFINICIN 1.7.1 Sea A U un conjunto. Se define el conjunto potencia de A, denotado porP(A), como el conjunto cuyos elementos son todos los subconjuntos de A. Es decir,

P(A) = {B U / B A}

OBSERVACIN:

Notar que P(A) es un conjunto cuyos elementos son a su vez conjuntos.

El conjunto potencia de un conjunto A siempre es no vaco puesto que tiene el subconjuntoA y como elementos. Es decir: P(A) 6= .

EJEMPLOS:

1. Si A = {a}, entonces P(A) = {, {a}}

2. Si A = {a, b}, entonces P(A) = {, {a}, {b}, {a, b}}

3. Si A = {a, b, c}, encuentre P(A).

4. Determine P() y P(P()). En este caso se debe tener cuidado, distinguiendo conjuntode elemento, y respetar la consecuente notacin:

P() = {} y P(P()) = {, {}}

TEOREMA 1.7.1 Sean A,B U . Entonces:

1. A B P(A) P(B).

2. P(A B) = P(A) P(B).

3. P(A) P(B) P(A B).

25

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

Demostracin:

1. Sea X P(A). Queremos probar que X P(B). Como X P(A), por definicin se tieneX A. Como A B, lo anterior implica que X B de donde X P(B).

2. Aqu debemos probar una igualdad de conjuntos, es decir debemos mostrar que:

a) P(A B) P(A) P(B) yb) P(A) P(B) P(A B)

Veamos primeramente a). Sea X P(A B). Como antes, por definicin esto quiere decirque X A B. Luego, X A y X B, de donde X P(A) y X P(B), es decirX P(A) P(B).Veamos ahora b). Sea X P(A) P(B). Luego, X P(A) y X P(B), de donde X A yX B y entonces X P(A B).

3. Dejamos la demostracin de la inclusin como ejercicio. Para darse cuenta de que en generalP(A B) 6 P(A) P(B) basta tomar A = {a} y B = {b}.

EJERCICIOS:

1. Sean A,B,D U , donde U es el universo de referencia. Si Ac B = , determine:

a) [(A B)A]c

b) P(B A) P(D)

2. Qu relacin existe entre los conjuntos P(U A) y P(U) P(A)?

3. Sea B A. Se defineF = {X P(A) : B X = }

Probar que:

a) X F Y P(A) : X Y Fb) X P(B) : X A = A A = B

26

Vernica Gruenberg Stern 1.8. PRODUCTO CARTESIANO

1.8. Producto Cartesiano

Observe que los conjuntos {a, b} y {b, a} son iguales ya que ambos contienen los mismos ele-mentos. Para poder distinguir el orden de los elementos, se introduce el concepto de par ordenado:

DEFINICIN 1.8.1 Dados dos elementos a A, b B, el par ordenado (a, b) se define como elconjunto

(a, b) = {{a}, {a, b}}

Entonces se tiene la siguiente:

PROPIEDADES 1.8.1 Sean a1, a2 A, b1, b2 B. Entonces

(a1, b1) = (a2, b2) si y solo si a1 = a2 b1 = b2

OBSERVACIN: Para demostrar esta proposicin, y por ende comprender de mejor manera la defi-nicin de par ordenado, sugerimos probar:

{a} = {b, c} a = b = c

{{a}, {a, b}} = {{c}, {c, d}} (a = c) (b = d).Ayuda: considerar separadamente los casos a = b y a 6= b.

Se define a continuacin el producto cartesiano entre dos conjuntos:

DEFINICIN 1.8.2 Sean A,B U . Se define el producto cartesiano de A y B, denotado por AB,como el conjunto:

AB = {(x, y) / x A y B}

OBSERVACIN:

Observar que AB 6= B A.

Claramente, R2 = RR.

Es claro que la definicin de par ordenado se puede extender a tro ordenado y, en general, auna n-upla ordenada.

EJEMPLOS:

1. Si A = {1, 2, 3} y B = {a, b}, entonces AB = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)} .

27

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

2. Se arroja un dado azul y a continuacin se arroja un dado rojo. Explicitar un modelo mate-mtico donde se puedan representar los resultados posibles.

Solucin: Si denotamos por Da los posibles resultados del dado azul y por Dr los posiblesresultados del dado rojo, entonces Da = Dr = {1, 2, 3, 4, 5, 6}. As, un conjunto mediante elque se puede representar los resultados es el producto cartesiano Da Dr.

3. ZZ representa un reticulado de puntos en el plano cartesiano.

4. Si S1 = {(x, y) R2 : x2+y2 = 1} y A = [0, 1], entonces S1A representa un cilindrode altura 1 unidad.

EJERCICIOS:

1. Considere los siguientes subconjuntos de R: A = [0, 1], B ={1n , n N

}, C = [1, 1],

D = {0, 1,1}. Dibuje, en el plano cartesiano, los siguientes conjuntos: AD,AB, A C, AR, D R, B B, B C. Puede dibujar en R3 : A C D?

2. Representar grficamente el subconjunto de R2 que es solucin del sistema de inecuaciones

x+ y 1x+ y 1x y 1x y 1

y relacionarlo con |x|+ |y| 1.

TEOREMA 1.8.1 Sean A,B,C,D U . Entonces se cumple:

1. AB = A = B =

2. A (B C) = (AB) (A C)

3. A (B C) = (AB) (A C)

4. A C B D = AB C D

Demostracin: Demostraremos la primera propiedad, dejando las dems como ejercicio.Probemos, en primer lugar, que si A = B = entonces A B = . Supongamos, para ello,

que A B 6= , es decir, neguemos la tesis. Luego, existe (a, b) A B, lo que, por definicin delproducto cartesiano significa que a A, b B, de donde A 6= , B 6= .

28

Vernica Gruenberg Stern 1.9. CARDINALIDAD

Recprocamente, si A 6= y B 6= , entonces existen a A y b B, y por lo tanto, existe(a, b) AB, de donde AB 6= .

Adems de las demostraciones formales, sugerimos que, mediante dibujos de subconjuntosadecuados del plano, verifique las afirmaciones anteriores.

EJERCICIOS:

1. Determine condiciones para que (AB) (B A) 6= .

2. Determine, justificadamente, si es vlida la siguiente afirmacin:

(AB)c = (Ac Bc) (Ac B) (ABc)

1.9. Cardinalidad

DEFINICIN 1.9.1 Llamaremos cardinalidad de un conjunto A (denotado por |A| #A), al nmerode elementos que lo forman. Si no existe un nmero natural que corresponda al nmero de ele-mentos de un conjunto A, diremos que el conjunto tiene infinitos elementos, o que A es infinito. Encaso contrario, diremos que A es finito.

En otras palabras, diremos que A es finito si se puede escribir de la forma

A = {x1, x2, x3, . . . xn}

donde x1, x2, . . . son sus elementos. En caso contrario, se dice que A es infinito.

EJEMPLOS:

1. Si A = , entonces |A| = 0.

2. Si A = {a, b, c}, entonces |A| = 3.

3. Si A = {x N : x 32}, entonces |A| = 33.

4. Si A = Z, entonces A es infinito.

5. En una encuesta realizada a los estudiantes de la USM, se encontr que 77 alumnos esta-ban estudiando ingls, 44 francs y 13 estudiaban ambos idiomas. Cuntos alumnos de losencuestados estudiaban al menos uno de estos idiomas extranjeros?

29

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

Solucin:Notamos que un alumno que estudia ambos idiomas, est siendo contado en los 3 grupos.

Luego, la suma 77 + 44 considera a tales alumnos 2 veces, por lo que debemos corregir este errorrestando la cantidad de alumnos que estudian ambos idiomas, o sea, 13.

Luego 77+4413 = 108 es el nmero de alumnos que estudian al menos un idioma extranjero.Podemos clarificar esta argumentacin del siguiente modo:

Sea

A = {estudiantes de ingls}B = {estudiantes de francs}

Buscamos |A B|.Pero |A B| = 13. Como |A| = 77, hay 77 13 = 64 que estudian slo ingls y como |B| = 44,

hay 44 13 = 31 que estudian slo francs.Por lo tanto: |A B| = (77 13) + (44 13) + 13 = 77 + 44 13.

El razonamiento que hemos utilizado se aplica a dos conjuntos finitos cualesquiera y tenemos

PROPOSICIN 1.9.1 Sean A,B U tales que |A|, |B|

Vernica Gruenberg Stern 1.9. CARDINALIDAD

EJEMPLOS:

1. Sea U = {n N : 1 n 200}. Sea C el conjunto de nmeros de U que no son divisibles nipor 2 ni por 3. Determine |C|.Solucin:

Obviamente, resulta aburridsimo contar los elementos de C = {1, 5, 7, 11, . . . , 199}. Paraevitar esto, sea A = {2, 4, 6, . . . , 200} el conjunto de los nmeros pares de U y B ={3, 6, 9, . . . , 198} el conjunto de los nmeros de U que son divisibles por 3.Es claro que |A| = 100, y como 198 = 3 66, entonces |B| = 66. Adems,A B = {6, 12, 18, . . . , 198} y como 198 = 6 33, vemos que |A B| = 33.Concluimos entonces que:

|C| = |(A B)c| = |U | |A B|= |U | (|A|+ |B| |A B|)= |U | |A| |B|+ |A B|= 200 100 66 + 33= 67

2. Una encuesta entre 100 estudiantes arroj los siguientes resultados:

41 alumnos toman clases de lgebra29 alumnos toman clases de Clculo26 alumnos toman clases de Fsica15 alumnos toman clases de lgebra y Clculo

8 alumnos toman clases de Clculo y Fsica19 alumnos toman clases de lgebra y Fsica

5 alumnos toman las tres asignaturas

Determine el nmero de estudiantes entre los 100 encuestados que no estn tomando ningu-na de esas asignaturas Cuntos toman slo una?

Solucin:

Es ms conveniente en este caso utilizar la informacin dada en el orden inverso en que fuedada, y de paso mostraremos una aplicacin de los diagramas de Venn.

31

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

Cinco alumnos toman las 3 asignaturas, luego el nmerocinco debe ir en la regin correspondiente a la interseccinde los 3 ramos. 19 alumnos toman lgebra y Fsica, perocomo 5 toman los 3 ramos, restan 14 que toman slo lge-bra y Fsica. As ubicamos el nmero 14 en la correspon-diente regin. Prosiguiendo con este proceso, llegamos fi-nalmente a completar la figura.

As, 100 (12 + 10 + 5 + 14 + 11 + 3 + 4) = 100 59 = 41 alumnos no asisten a ningn cursode estos, y 12 + 11 + 4 = 27 alumnos estn tomando exactamente una de estas asignaturas.

La siguiente proposicin relaciona la cardinalidad del conjunto potencia de un conjunto finitoA con la del conjunto mismo.

PROPOSICIN 1.9.2 Si |A| = n

Vernica Gruenberg Stern 1.10. EJERCICIOS MISCELNEOS

EJERCICIOS:

1. Sea A = {z Z : |z| > 3} calcular |P (Ac)|.

2. Si A = {1, 2, 3} y B = {a, b} calcular |P (A P (AB))|

3. Cuntos nmeros hay entre 100 y 1000 para los cuales cada dgito es impar?Cuntos destos estn entre 100 y 500?

4. Se realiz una encuesta a 160 Sansanos de primer ao respecto a la lectura de libros de cien-cias: Matemtica (M ), Fsica (F ) y Qumica (Q), obteniendo los siguientes resultados: 65 leenM , 70 leen F , 73 leen Q, 30 leen M y F , 109 leen F o Q, 106 leen M o Q, 105 leen M o F yfinalmente 40 no leen (no porque no sepan leer, sino porque no tienen inters).

Determine:

a) Nmero de Sansanos que leen los 3 libros.

b) Nmero de Sansanos que lee 1 solo libro.

c) Nmero de Sansanos que leen libros de Matemtica o Fsica, pero no ambas.

d) Nmero de Sansanos que leen libros de Fsica y Qumica.

5. Sean A,B,C U . Determine |A B C|.

1.10. Ejercicios Miscelneos

1. Demuestre las siguientes proposiciones:

a)

3 no es un nmero racional.

b) No existen nmeros primos a, b, c tal que a3 + b3 = c3.

c) Pruebe que no existen n,m N : 1n

+1

m=

7

17

2. Determine en cada caso si son iguales o diferentes los siguientes conjuntos A y B:

a) A = {2k 1 : k Z}, B = {2k + 1 : k Z}b) A = {x Z : x = 2n+ 1}, B = {x Z : x = 4n 1}c) A = {4n+ 1 : n Z}, B = {2n+ 3 : n Z, n es par}d) A = {3n+ 1 : n Z}, B = {3n 2 : n Z}e) A = {4n+ 1 : n Z}, B = {2n : n es un entero impar}

33

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

3. Sean A0 = {3n : n Z}, A1 = {3n + 1 : n Z}, A2 = {3n + 2 : n Z}.Pruebe que estos conjuntos son disjuntos dos a dos, es decir, si i 6= j entonces Ai Aj = .Qu puede decir de A0 A1 A2?

4. Sean

A = {x N |x es impar x 11}B = {x N | (k N : x = 3k) (x 12)}C = {x N |x 12}

Expresar cada uno de los conjuntos siguientes en trminos de uniones, intersecciones, com-plementos y diferencias de A, B, C:

a) El conjunto de los nmeros pares del 2 al 12

b) El conjunto de los elementos de C que al dividirlos por 3 dejan resto 2.

c) El conjunto {3, 9}.d) El conjunto {2, 3, 4, 6, 8, 9, 10, 12}.

5. D un ejemplo de un universo referencial U y dos subconjuntos A y B tales que

U (A B) 6= (U A) (U B)

6. D ejemplos de conjuntos A,B,C tales que (A B) C 6= A (B C).

7. Demostrar que A,B,C U :

a) C \ (B \A) = (C \Ac) (C \B) b) A \ (A \B) = B \ (B \A)

8. Si A,B U , use propiedades de las operaciones de conjuntos para simplificar

A ((AB) B) (Ac B)c

9. Sean A,B U . Demuestre:

a) A B A Bc = b) A B = A B A = Bc) A B = U Ac Bd) A = B (A Bc) (Ac B) = e) (AB) (B A) = (A B) (A B)

34

Vernica Gruenberg Stern 1.10. EJERCICIOS MISCELNEOS

10. Demuestre o refute cada una de las siguientes:

a) A B = C B = A = Cb) A B = C B = A = Cc) (A B) \ (A C) = (A B) \ C

11. Se define A B = Ac Bc. Demuestre o refute:

a) A A = Ac

b) (A A) (B B) = A Bc) (A B) (A B) = A Bd) A (B C) = (A B) C

12. En una encuesta sobre 2 artculos A y B, se sabe que

el 50 % de los encuestados prefiere A

el 60 % de los encuestados no prefiere B

el 80 % de los encuestados prefiere A o B

a) Qu porcentaje de los encuestados prefiere A y B?

b) Qu porcentaje de los encuestados prefiere solo uno de ellos?

13. De un total de 120 personas sobre una encuesta de 3 productos A,B y C, se sabe:

a 60 les gusta A a 27 les gusta A y B a 11 les gusta solo C

a 63 les gusta B a 31 les gusta B y C

a 58 les gusta C a 21 les gusta A y C

a) A cuntos no les gusta ninguno de los productos?

b) A cuntos les gusta solo 2 productos?

c) A cuntos les gusta solo los productos B y C?

14. Dados A = {1, 0,2,12} y B = {2, 2, 1}. Determine el valor de verdad de :

a) (x A)(y B)(xy + 1 < 0 x2 y2 = 0)b) (x A)(y B)(xy + 1 < 0 x2 y2 = 0)c) (x B)(y A)(xy 0 (x+ y) Ad) (y B)(x A)((x y) A (x+ y) / B)

35

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

15. Sea A = {1, 2, 3, 4, 5, 6}. Escriba simblicamente las siguientes afirmaciones en A, y determi-ne su valor de verdad:

a) Hay un elemento que es mayor que los restantes.

b) Hay un nico elemento cuyo cuadrado es 4.

c) Dado cualquier elemento, siempre es posible encontrar uno que es menor o igual quel.

d) Hay un elemento cuyo cuadrado es igual a si mismo.

e) Dado un elemento cualquiera, siempre sexiste otro que lo divide.

f ) Hay un elemento, distinto de 1, que al multiplicarlo con cualquier otro el resultado esmenor que 10.

16. En R, determine el valor de verdad de las siguientes afirmaciones, y luego niguelas:

a) x y : (x+ y = 1 x = y)b) x y : [x+ y es par (x es par ) (y es par )]c) x y : (x < y x2 > y)

17. Sean A y B conjuntos en U . Definimos la diferencia simtrica entre A y B como

AB = (AB) (B A)

Si A = {1, 3, 4} y B = {1, 5}, determine

a) AB b) P(A)P(B)

Si ahora A,B y C son conjuntos arbitrarios, demuestre que:

a) AB = BA

b) A(BC) = (AB)C

c) A = Ad) AA = e) AB = C AC = B

f ) AB = AC = B = C

g) |AB|

h) |(AB)C|

i) A (BC) = (A B)(A C)

Determine:

a) |AB| b) |(AB)C|

36

Vernica Gruenberg Stern 1.11. EJERCICIOS DE CONTROLES Y CERTMENES

1.11. Ejercicios de Controles y Certmenes

1. a) Sin hacer uso de tablas de verdad, determine el valor de verdad de

(p q) ((p r) (q r)).

b) Si A,B U , usando propiedades de las operaciones de conjuntos, simplificar al mxi-mo

A ((AB) B) (Ac B)c .

2. Sean A,B conjuntos en U . Demuestre que: B [(Bc A)c (A B)c] = B A

3. Determine, justificadamente, si las siguientes son V o F.

a) (x R) (y R {0} ) :(x < y x

y< 1

)b){x R : |x||1 x| > 1

}= {x R : |x| > |1 x|}

4. En U = N, considere las siguientes funciones proposicionales:

p(n) = n2 + n es par

q(n) = 5n+ 8 = 23

Determine el valor de verdad de p(5) q(4) n N : q(n)

5. Sean A = {1,1, 2}, B = {0,1, 1}. Determine, justificadamente, el valor de verdad de

x A y B : x y 6 B = x2 y2 < 1

6. Demuestre o refute (justificando adecuadamente) las siguientes:

a) A B = C B = A = Cb) A B = C B = A = Cc) (A B) (A C) = (A B) C

7. Sean A = {x N : x < 8} y B = {x Z : x2 < 18}. Determine la cardinalidad de AB.

8. Sean A,B,C U . Suponga que |AB| = 12, B C = {(5, 1), (2, 1), (1, 1)}Determine: (i) P(B C) (ii) |P(A)|

9. Use propiedades para determinar el valor lgico de

[(p q) (r s)] [(p r) (q s)]

37

CAPTULO 1. NOCIONES BSICAS DE LGICA Y CONJUNTOS Vernica Gruenberg Stern

10. Use propiedades para determinar el valor de verdad de la expresin

[(p q r) (p q)] (p r)

11. Sean A = {2, 4, 6}, B = {1, 3,2} C = {2, 3}. Determine, justificadamente, el valor deverdad de

(x A) (y B) (z C) : x+ y z 2

38

Captulo 2

Nociones Bsicas de Relaciones

DEFINICIN 2.0.1 Sean A,B conjuntos. Una relacinR de A en B es un sunconjunto de AB. Esdecir,R AB o, equivalentemente,R P(AB). De esta forma los elementos de una relacinson pares ordenados.

OBSERVACIN:

Si (x, y) R tambin se escribe xRy

Se denota por R : A B a una relacin R de A en B. En tal caso, se puede escribir,equivalentemente, y = R(x) para (x, y) R.

Si (x, y) R entonces diremos que x est relacionado con y o y es la imagen de x por Ro x es la preimagen de y porR.

Si A = B escribimosR A2.

EJEMPLOS:

1. R = AB es siempre una relacin de A en B.

2. R = es siempre una relacin de A en B.

3. Sea A = {1, 2, 3, 4}. Determine el subconjunto de AA determinado por la relacin

xRy x+ y > 3

Solucin:

R = {(1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)}

4. El conjunto R ={(x, y) RR : x2 + y2 = 9} es una relacin de R en R. Geomtrica-mente, se puede representar como una circunferencia centrada de radio 3.

39

CAPTULO 2. NOCIONES BSICAS DE RELACIONES Vernica Gruenberg Stern

5. El conjuntoR = {(x, y) RR : x < y} es una relacin deR enR.Notar que (1, 2) R pero(2, 1) 6 R.

6. Si A = {1, 2, 3} y B = {a, b} entonces A B = {(1, a) , (1, b) , (2, a) , (2, b) , (3, a) , (3, b)} sonejemplos de relaciones de A en B:

a) R1 = {(1, a) , (1, b)}b) R2 = {(1, a) , (2, a) , (3, a)}c) R3 = {(1, b)}d) Cuntas relaciones se pueden obtener?

OBSERVACIN:

1. De la definicin, es claro que el nmero de relaciones posibles de A en B es menor o igual alnmero de subconjuntos de AB.

2. Adems, si A es un conjunto, siempre es posible construir las siguientes relaciones:

a) AAb) La diagonal de AA, denotada por , con = {(x, y) AA : y = x}c) AA, la relacin vaca.

EJERCICIOS:

1. En un grupo A de 5 colegas, se define la siguiente relacinR:

a est relacionado con b a y b son amigos.

Determine explcitamenteen qu consiste la relacin AA, y la relacinR.

2. Explicite grficamente en R2 las siguientes relaciones en R:

a) xRy x+ y = 1b) xRy x2 + y2 = 1c) xRy x2 + y2 < 1

DEFINICIN 2.0.2 Dada una relacinR de A en B se definen los siguientes conjuntos:

1. Dominio de la relacinR: Dom(R) = {x A / (x, y) R para algn y B}.Notemos que en clculo se defini: Dom(f) = {x R : y R tal que y = f(x)} R

40

Vernica Gruenberg Stern

2. Recorrido de la relacinR: Rec(R) = {y B / (x, y) R para algn x A}.Notemos que en clculo se defini: Rec(f) = {y R : x R tal que f(x) = y} R

EJEMPLOS:

1. Determinar dominio y recorrido de las relaciones de {1, 2, 3} en {a, b} :

a) R1 = {(1, a) , (2, a) , (3, a)}b) R2 = {(1, b) , (1, a)}

2. Determinar el dominio de la relacin de R en R

R = {(x, y) RR : x2 + y2 = 1}

DEFINICIN 2.0.3 SiR AB es una relacin, se define la relacin inversaR1 por

R1 = {(y, x) B A : (x, y) R} B A

(R1 es una relacin de B en A).

EJEMPLO 2.0.1 SiR = {(x, y) RR : x+ 4y = 1} entonces

R1 = {(y, x) RR : (x, y) R}= {(y, x) RR : x+ 4y = 1}= {(x, y) RR : 4x+ y = 1}

DEFINICIN 2.0.4 Sean R1 : A B y R2 : B C relaciones. Se define la relacin compuestaR2 R1 : A C como el conjunto

R2 R1 = {(a, c) A C : b B, (a, b) R1 (b, c) R2}

EJEMPLO 2.0.2 SiR = {(2, 5) , (3, 4) , (6, 2) , (3, 0) , (2, 7)} y S = {(4, 8) , (5, 3) , (0, 9) , (2, 2) , (7, 4) , (5, 10)}entonces

R S = {(5, 4) , (5, 0) , (2, 5) , (2, 7)}

S R = {(2, 3) , (2, 10) , (3, 8) , (6, 2) , (3, 9) , (2, 4)}

note en particular queR S 6= S R

41

CAPTULO 2. NOCIONES BSICAS DE RELACIONES Vernica Gruenberg Stern

2.1. Relaciones de Equivalencia

DEFINICIN 2.1.1 Sea R A2. Diremos que una relacin R en A es una relacin de equivalenciasi cumple con las siguientes propiedades:

Propiedad Condicin

Reflexividad (a A) ((a, a) R)

Simetra (a, b) R (b, a) R

Transitividad (a, b) R (b, c) R (a, c) R

EJEMPLOS:

1. Si A = { alumnos del curso MAT021 }, y se define la relacin

aRb a y b tienen la misma edad

es fcil verificar queR es una relacin de equivalencia.

2. Si A 6= , entonces AA es una relacin de equivalencia.

3. Si A = {1, 2, 3} yR = {(1, 2) , (2, 1) , (2, 2) , (1, 1)} entoncesR es una relacin de A en A.R essimtrica, transitiva pero no es reflexiva por lo tanto no es una relacin de equivalencia.

4. SiR = {(x, y) RR : x y} entoncesR es reflexiva, transitiva pero no es simtrica.

EJERCICIOS:

1. Es verdad que si una relacin es simtrica y transitiva entonces es reflexiva?

2. Sea R una relacin de R2 en R2 definida por (x, y)R (a, b) x2 a2 = y3 b3. Es R unarelacin de equivalencia?

3. Sea n Z+ fijo. Mostrar que R = {(x, y) ZZ : x y es divisible por n} es una relacinde equivalencia en Z.

42

Vernica Gruenberg Stern 2.1. RELACIONES DE EQUIVALENCIA

4. En R, se define la relacin

xRy k Z : x y = 2kpi

Demuestre queR es una relacin de equivalencia.

5. En ZZ, se define la relacin

(p, q)R(p, q) pq = pq

Demuestre queR es una relacin de equivalencia.

6. Sea A R, A 6= , y sea f : A R una funcin. Se define la relacinR en A mediante

uRv f(u) = f(v)

Demuestre que esta relacin es de equivalencia en A.

Considere f(x) =

{x+ 4 si x < 1x2 2x si x 1

a) Determine la cardinalidad de [2].

b) Determine [1].

c) Hallar el valor de verdad de: !x R : #[x] = 2.

DEFINICIN 2.1.2 Sea R una relacin de equivalencia de A. Para cada a A, se define la clase deequivalencia del elemento a por

[a] = {b A / aRb}

Es decir, la clase de equivalencia de a es el subconjunto deA formado por todos los elementos deA que estn relacionados con a. Cualquier elemento b A relacionado con a, se llama representantede la clase [a]. As, en el ejemplo 1., si un estudiante a tiene 19 aos, la clase de a consiste en todoslos alumnos de MAT021 que tienen 19 aos.

Es claro que una clase determina un subconjunto no vaco, que no se intercepta con la clase de-terminada por otro elemento que no est relacionado con el primero. En el mismo ejemplo anterior,si suponemos que las edades extremas de los alumnos del curso son 17 y 21 aos, la relacin deequivalencia prouce 5 clases de equivalencia C1, C2, C3, C4 y C5, donde C1 consiste en los alumnosque tienen 17 aos, C2 consiste en los alumnos que tienen 18 aos, etc. Esto motiva las siguientesdos definiciones.

43

CAPTULO 2. NOCIONES BSICAS DE RELACIONES Vernica Gruenberg Stern

DEFINICIN 2.1.3 Si R es una relacin de equivalencia de A llamaremos conjunto cociente de AporR al conjunto

A/R = {[a] : a A}es decir es el conjunto de todas las clases de equivalencia.

DEFINICIN 2.1.4 Sea A un conjunto. Una particin de A es una familia de subconjuntos Ci, i Ide A, tal que:

Ci Cj = , si i 6= jiI

Ci = A

Luego, en el ejemplo, el conjunto A queda particionado en 5 clases de equivalencia disjuntas,cuya unin es A.

Con lo visto hasta ahora es claro que se satisfacen las siguientes

PROPIEDADES 2.1.1 SiR es una relacin de equivalencia de A, A 6= , entonces

1. a A, [a] 6=

2. a [a]

3. (x, y) R [x] = [y]

EJEMPLOS:

1. Sea A = {a, b, c} y seaR la relacin en A2 dada por

R = {(a, a) , (b, b) , (c, c) , (b, c) , (c, b)}

entoncesR es una relacin de equivalencia. Adems: [a] = {a} y [b] = {b, c} = [c].Se sigue que

A/R = {{a} , {b, c}} = {[a] , [b]}

2. En Z (Z {0}) considere la relacin

(x, y)R(u, v) xv = uy

Es claro que:

R es reflexiva, pues xy = yxR es simtrica, pues (x, y)R(u, v) xv = yu uy = vx (u, v)R(x, y)

44

Vernica Gruenberg Stern 2.2. RELACIONES DE ORDEN

R es transitiva, pues si (x, y)R(u, v) (u, v)R(s, t) entonces xv = yu ut = vs.Multiplicando la segunda igualdad por y(6= 0), obtenemos yut = yvs. Reemplazamosyu por xv, obteniendo xvt = yvs. Simplificamos por v(6= 0) y se tiene que (x, y)R(s, t).

Luego, la relacin es de equivalencia. Para determinar (Z (Z {0}))/R, notamos quexv = yu es lo mismo que xy =

uv , y, v 6= 0. Luego, el conjunto cuociente no es otra cosa que

Q, el conjunto de los nmeros racionales.

EJERCICIOS:

1. Mostrar que R = {(x, y) ZZ : x y es divisible por 2} es una relacin de equivalenciaen Z. Encontrar las clases de equivalencia y el conjunto cociente.

2. Mostrar que R = {(x, y) ZZ : x y es divisible por 3} es una relacin de equivalenciaen Z. Encontrar las clases de equivalencia y el conjunto cociente.

2.2. Relaciones de Orden

DEFINICIN 2.2.1 Sea R A2. Diremos que una relacin R en A es una relacin de orden sicumple con las siguientes propiedades:

Propiedad Condicin

Reflexividad (a A) ((a, a) R)

Antisimetra (a, b) R (b, a) R a = b

Transitividad (a, b) R (b, c) R (a, c) R

EJEMPLOS:

1. En R, considere la relacin xRy x y. Claramente,R es una relacin de orden.

2. Sea A un conjunto, y consideremos el conjunto potencia, P(A). En l, definimos la relacinXRY X Y . Claramente,R es una relacin de orden.

3. Sea A = N. Definamos la relacin R = {(x, y) A2 : x divide a y}; entonces R es unarelacin de orden.

45

CAPTULO 2. NOCIONES BSICAS DE RELACIONES Vernica Gruenberg Stern

OBSERVACIN: Notamos que en el ejemplo 1 es posible comparar todos los elementos de R. Noocurre lo mismo en el ejemplo 2. Considere, por ejemplo, A = {1, 2, 3, 4}. Los subconjuntosX = {1, 2} e Y = {3, 4} no se pueden comparar, en el sentido que ninguno de ellos est contenidoen el otro.

Si en un conjunto A se tiene una relacin de orden R, diremos que el par (A,R) es un con-junto parcialmente ordenado, o ms laxamente, que A es parcialmente ordenado porR.As, en los tres ejemplos anteriores, los conjuntos respectivos son parcialmente ordenados.Si adems se satisface la propiedad que todos los elementos pueden ser comparados entre smediante la relacin de orden, se dice que el par (A,R) es un conjunto totalmente ordenado.Ms precisamente,

Sea (A,R) un conjunto parcialmente ordenado. Diremos que es totalmente ordenado si cadapar de elementos en A son comparables, es decir, si x, y A : xRy yRx.

EJERCICIOS:

1. En R2 considere la relacin (a, b)R(c, d) b = d.

a) Demuestre que es una realcin de equivalencia.

b) (3, 1) [(0, 1)]?c) Describa la clase de (0, 1).

2. Sea A un conjunto. En P(A), se definen las relaciones

XR1Y X Y = y XR2Y X Y 6=

Estudie la reflexividad, simetra y transitividad de estas relaciones.

3. Sea A = {(x, y) R2 : y 0}. Defina en A la relacinRmediante

(x1, y1)R(x2, y2) x1 = x2 y1 y2

Pruebe que (A,R) es parcialmente ordenado.

46

Vernica Gruenberg Stern 2.3. EJERCICIOS DE CONTROLES Y CERTMENES

2.3. Ejercicios de Controles y Certmenes

1. Sea A = {1, 2, 3} y R una relacin en A, dada por

R = { (1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2) }

Determine siR es refleja, simtrica y/o transitiva.

2. En R2 considere la relacin siguiente: (a, b) R (c, d) b = d.

a) Demuestre que es una relacin de equivalencia.

b) (3, 1) [(0, 1)]?c) Describa la clase de (0, 1).

3.

47

CAPTULO 2. NOCIONES BSICAS DE RELACIONES Vernica Gruenberg Stern

48

Captulo 3

Nmeros Naturales

3.1. Introduccin

Segn el matemtico Leopold Kronecker,1 nacido en Polonia, Dios nos regal los nmerosnaturales y el resto es obra del hombre. Sin embargo, el matemtico italiano Giuseppe Peano,2

uno de los fundadores de la lgica matemtica y la teora de conjuntos, axiomatiz la construccinde los nmeros naturales en los llamados postulados de Peano para los nmeros naturales. No es elobjetivo de este curso profundizar en los fundamentos de la matemtica, pero es importante tenerpresente en todo momento cmo se ha construdo la matemtica que conocemos. Adoptaremosaqu un enfoque un poco menos formal.

DEFINICIN 3.1.1 Llamaremos I al conjunto de todos los subconjuntos M de R tal que:

1 M

x M x+ 1 M

OBSERVACIN:

1. A los elementos de I se les llama conjuntos inductivos.

2. Notar que I 6= pues R I .

DEFINICIN 3.1.2 Definimos el conjunto de los nmeros naturales como la interseccin de todoslos subconjuntos inductivos de R, es decir:

N =MI

M

Esto significa queN R es el conjunto inductivo ms pequeo.118231891218581932

49

CAPTULO 3. NMEROS NATURALES Vernica Gruenberg Stern

Veamos queMI

M efectivamente es un conjunto inductivo:

1 M M I 1 MI

M 1 N

Sea n MI

M n M M I .

Como cada M es inductivo, se tiene que n+ 1 M M I n+ 1 MI

M

3.2. Induccin

La induccin matemtica es un mtodo de demostracin usada, tpicamente, para probar queuna determinada propiedad se cumple para todos los nmeros naturales. Formalmente:

TEOREMA 3.2.1 Sea P (n) una funcin proposicional asociada a cada n N. Si

1. P (1) es verdadera.

2. n N : P (n) P (n+ 1) es verdadera.

entonces, es verdadero que n N : P (n).

Demostracin: SeaM el conjunto de los nmeros naturales en los que P (n) es verdadera. Tene-mos que:

1 M por la hiptesis 1.

n M n+ 1 M por la hiptesis 2.

Luego: M = N. Es decir, P (n) es verdadero n N.

Lo que el teorema dice es que, si queremos probar que una determinada propiedad se satisfacepara todos los nmeros naturales, bastar probar que se cumple para el primero (1 en este caso,pero podramos considerar igualmente a 0) y que, si la propiedad se satisface para algn nmeronatural, tambin se satisface para el siguiente. Entonces, como se cumple para n = 1, se cumplirpara n = 2 (que es el siguiente); como se cumple para n = 2, se cumplir para n = 3 (que es elsiguiente); y as sucesivamente.

50

Vernica Gruenberg Stern 3.2. INDUCCIN

EJEMPLOS:

1. Demuestre que 1 + 2 + 3 + + n = n(n+ 1)2

n N.

Dem.: En este caso: p(n) : 1 + 2 + 3 + + n = n(n+ 1)2

. Luego:

p(1) : 1 =1 2

2lo cual es verdadero. p(1) es V.

Supondremos que p(n) es verdadero, y probaremos que p(n+ 1) es verdadero, donde :

p(n+ 1) : 1 + 2 + 3 + + n+ (n+ 1) = (n+ 1)(n+ 2)2

Notemos que:

1 + 2 + 3 + + n+ (n+ 1) =(

1 + 2 + 3 + + n)

+ (n+ 1)

=n(n+ 1)

2+ (n+ 1)

=(n+ 1)(n+ 2)

2

es decir, p(n) p(n + 1) es verdadera, que es exactamente lo que queramos probar.Luego,

1 + 2 + 3 + + n = n(n+ 1)2

n N.

OBSERVACIN: Cuenta la leyenda que al matemtico alemn Karl Friederich Gauss, 3 suprofesor en la escuela primaria le dio como castigo sumar los nmeros del 1 al 100, cosa quel realiz en menos de 1 minuto. Se cuenta que el procedimiento que us fue el siguiente:

1 + 2 + 3 + 4 + + 99 + 100100 + 99 + 98 + + 2 + 1101 + 101 + 101 + 101 + + 101

Es decir, al sumar dos veces los nmeros del 1 al 100, se obtiene 100 veces 101, de donde lasuma pedida es

100 1012

. Claramente, este procedimiento se puede extender a una cantidadarbitraria de nmeros naturales, y a otras formas de progresiones numricas, que veremosmuy pronto.

31777-1855

51

CAPTULO 3. NMEROS NATURALES Vernica Gruenberg Stern

2. Demuestre que 1 + 3 + 5 + + (2n 1) = n2 n N.Dem.: En este caso: p(n) : 1 + 3 + 5 + + (2n 1) = n2. Luego:

p(1) : 1 = 12 lo cual es verdadero. p(1) es V.

Supondremos que p(n) es verdadero, y probaremos que p(n+ 1) es verdadero, donde :

p(n+ 1) : 1 + 3 + 5 + + (2n 1) + (2n+ 1) = (n+ 1)2

Notemos que:

1 + 3 + 5 + + (2n 1) + (2n+ 1) =(

1 + 3 + 5 + + (2n 1))

+ (2n+ 1)

= n2 + (2n+ 1)

= (n+ 1)2

es decir, p(n) p(n + 1) es verdadera, que es exactamente lo que queramos probar.Luego,

1 + 3 + 5 + + (2n 1) = n2 n N

3. Demostrar que n2 + n es siempre divisible por 2, si n es un nmero natural.

Dem.: En este caso: p(n) : n2 + n = 2k, para algn k N. Luego:

p(1) : 12 + 1 = 2 = 2 1, es decir, k = 1. Luego, p(1) es verdadero.Supondremos que p(n) es verdadero, y probaremos que p(n+ 1) es verdadero, donde :

p(n+ 1) : ` N : (n+ 1)2 + n+ 1 = 2`

Notemos que:

(n+ 1)2 + n+ 1 = n2 + n+ 2n+ 2

= 2k + 2(n+ 1)

= 2(k + n+ 1)

= 2` donde ` = k + n+ 1

es decir, p(n) p(n+1) es verdadera, que es exactamente lo que queramos probar. Luego,

n N : n2 + n es siempre divisible por 2

OBSERVACIN: Otra forma de demostrar este resultado es notar que

n2 + n = n(n+ 1)

52

Vernica Gruenberg Stern 3.2. INDUCCIN

es decir, la expresin es simplemente el producto de dos nmeros consecutivos, por lo quenecesariamente uno de ellos es par. O, utilizando el mismo razonamiento pero aplicado alproceso inductivo, notamos que

(n+ 1)2 + n+ 1 = (n+ 1)(n+ 1 + 1) = (n+ 1)(n+ 2)

que es producto de dos nmeros consecutivos.

4. Demostrar que n N : 2n+ 1 3n

Dem.: En este caso: p(n) : 2n+ 1 3n

p(1) : 2 1 + 1 = 3 3. Luego, p(1) es verdadero.Supondremos que p(n) es verdadero, y probaremos que p(n+ 1) es verdadero, donde :

p(n+ 1) : 2(n+ 1) + 1 3n+1

Como p(n) es verdadero, sto significa que

2n+ 1 3n

Multiplicando por 3:

6n+ 3 3n+1 y claramente 2n+ 3 6n+ 3 3n+1

es decir, p(n) p(n+ 1) es verdadera. Luego

n N : 2n+ 1 3n

OBSERVACIN:

1. A pesar de su nombre, la induccin es un mtodo deductivo de demostracin.

2. Es importante ser cuidadosos en la demostracin por induccin de ciertas afirmaciones. Mu-chas veces se verifican algunos casos iniciales y se asume que el resultado es correcto, sin hacerla demostracin completa. Esto induce a errores, de lo que ya Leonhard Euler 4 (matemticosuizo) se dio cuenta y encontr el siguiente ejemplo:

Determine el valor de verdad de la proposicin n N : n2 + n+ 41 es un nmero primo.Hacemos una tabla con los primeros clculos:

n : 1 2 3 4 5 6 7 8 n2 + n+ 41 : 43 47 53 61 71 83 97 113

41707-1783

53

CAPTULO 3. NMEROS NATURALES Vernica Gruenberg Stern

Notamos que todos los valores que calculamos para el polinomio cuadrtico son nmerosprimos... la tentacin de afirmar que la proposicin es verdadera es grande. Sin embargo,p(41) : 412 + 41 + 41 = 41 (41 + 1 + 1) = 41 43, es decir, p(41) no es un nmero primo.Luego, la afirmacin es falsa.

Este ejemplo muestra claramente que no basta con verificar muchos casos particulares paravalidar una afirmacin general.

3. Por otra parte, la verificacin del caso inicial (P (1) en los casos que hemos visto hasta aqu) esfundamental. Considere la afirmacin

1 + 3 + 5 + 7 + + (2n 1) = 3 + n2 para n N

Demuestre que si la afirmacin es vlida para algn n N, entonces tambin lo es paran+ 1.

Es verdadera la afirmacin n N?

Solucin:

Sea p(n) : 1 + 3 + 5 + 7 + + (2n 1) = 3 + n2. Por lo tanto,p(n+ 1) : 1 + 3 + 5 + 7 + + (2n 1) + (2n+ 1) = 3 + (n+ 1)2.Veamos ahora que p(n) p(n+ 1) es verdadera:1 + 3 + 5 + 7 + + (2n 1) + (2n + 1) = 3 + n2 + (2n + 1) = 3 + (n + 1)2, comoqueramos probar.

Claramente, la afirmacin es falsa, incluso para el caso n = 1 : 1 6= 3 + 12 = 4.En realidad, ya probamos por induccin que la suma de los primeros "n" nmerosimpares es igual a n2.

El Principio de Induccin es til para tratar proposiciones que involucran a todos los nmerosnaturales. Sin embargo, sucede a veces que interesa probar alguna propiedad que se satisface apartir de un nmero k N, y no para todos los anteriores. En este caso, podemos usar el Principiode Induccin Matemtica Extendida.

TEOREMA 3.2.2 SeaP (n) una funcin proposicional asociada a cada nmero natural n, y sea k N.Si P (k) es verdadera y si n k : P (n) P (n + 1) es verdadera, entonces P (n) es verdaderan k, n N.

54

Vernica Gruenberg Stern 3.2. INDUCCIN

EJEMPLOS:

1. Determine todos los n N : 1 2 3 n > 2n

Solucin: Estudiamos algunos casos particulares:

n = 1 : 1 > 2 Falson = 2 : 1 2 > 22 Falson = 3 : 1 2 3 > 23 Falson = 4 : 1 2 3 4 > 24 Verdaderon = 5 : 1 2 3 4 5 > 25 Verdadero

Luego, aparentemente la afirmacin es vlida n 4. Verifiquemos que sto es as:

Ya vimos que es vlida para n = 4.

Veamos que si p(n) : 1 2 3 n > 2n es verdadera para algn n 4, entoncesp(n+ 1) : 1 2 3 n (n+ 1) > 2n+1 tambin lo es. En efecto:

1 2 3 n (n+ 1) >Hip. Inductiva

2n(n+ 1) >n+1>2

2n 2 = 2n+1

Luego, n 4, n N : 1 2 3 n > 2n.

2. Determine si el producto de 3 nmeros consecutivos es siempre divisible por 6.

Solucin: Debemos determinar el valor de verdad de:

n N ` N : n (n+ 1) (n+ 2) = 6`n = 1 : 1 2 3 = 6, que es divisible por 6.Supongamos que p(n) : n (n+ 1) (n+ 2) = 6`, para algn ` N.Probemos que p(n+ 1) : (n+ 1) (n+ 2) (n+ 3) = 6`, para algn ` N tambin loes. Notemos que:

(n+ 1) (n+ 2) (n+ 3) = n (n+ 1) (n+ 2) + 3 (n+ 1) (n+ 2)= 6`+ 3 (n+ 1) (n+ 2)= 6`+ 6k,

((n+ 1)(n+ 2)

)divisible por 2

= 6`1

Luego, el producto de 3 nmeros consecutivos es siempre divisible por 6.

3. Determine si la suma de 3 nmeros consecutivos es siempre divisible por 6.

Solucin: Debemos determinar el valor de verdad de:

n N ` N : n+ (n+ 1) + (n+ 2) = 6`

55

CAPTULO 3. NMEROS NATURALES Vernica Gruenberg Stern

n = 1 : 1 + 2 + 3 = 6, que es divisible por 6.

Supongamos que p(n) : n+ (n+ 1) + (n+ 2) = 6`, para algn ` N.Debemos probar que p(n+ 1) : (n+ 1) + (n+ 2) + (n+ 3) = 6`, para algn ` N.Pero:

(n+ 1) + (n+ 2) + (n+ 3) = n+ (n+ 1) + (n+ 2) + 3 = 6`+ 3, que claramente no esdivisible por 6. Luego, p(n) verdadero no implica que p(n+ 1) sea verdadera.

Por lo tanto, la suma de 3 enteros consecutivos no es necesariamente divisible por 6.

Notemos que que n + (n + 1) + (n + 2) = 3(n + 1), de donde para que esta expresin seadivisible por 6, necesariamente el factor (n + 1) debe ser un nmero impar para cualquiern N, lo que es falso.

4. Sea f0(x) =x

x+ 1, fn+1(x) = (f0 fn)(x). Encuentre una expresin para fn(x), n N.

(Stewart, Conceptos y Contextos).

Solucin: Determinamos algunos casos particulares:

f1(x) = (f0 f0)(x) = f0(

x

x+ 1

)=

xx+1xx+1 + 1

=x

2x+ 1

f2(x) = (f0 f1)(x) = = f0(

x

2x+ 1

)=

x2x+1x

2x+1 + 1=

x

3x+ 1

Luego, conjeturamos que fn(x) =x

(n+ 1)x+ 1, n N. Probemos que la conjetura

es correcta:

El caso n = 1 fue probado arriba.

Supongamos que p(n) : fn(x) =x

(n+ 1)x+ 1es verdadero. Veamos que

p(n+ 1) : fn+1(x) =x

(n+ 2)x+ 1es verdadero.

Notamos que:

fn+1(x) = (f0 fn)(x)= f0

(x

(n+ 1)x+ 1

)=

x(n+1)x+1x

(n+1)x+1 + 1=

x

(n+ 2)x+ 1

56

Vernica Gruenberg Stern 3.2. INDUCCIN

5. Una triangulacin de un polgono es la descomposicin del rea del polgono en tringulos,de modo que los vrtices sean los mismos del polgono, o se agregan al interior del mismopara servir de vrtices de tringulos. Denotemos por v: nmero de vrtices, `: nmero delados y c: nmero de caras de una triangulacin dada. Demuestre que en una triangulacinde un polgono, siempre se tiene que v `+ c = 1.Dem.: Si se considera 1 tringulo, ste tiene 3 vrtices, 3 lados y 1 cara, de donde

P (1) : v `+ c = 3 3 + 1 = 1

es verdadera.

Supongamos ahora que P (n) es verdadera, es decir, que dada una triangulacin Tn formadapor n tringulos, vn `n + cn = 1. Queremos probar que P (n + 1) es verdadera, es decir,que la frmula anterior se cumple en una triangulacin de n+1 tringulos. Si Tn+1 es una taltriangulacin, al borrar un tringulo adecuado (de tal modo de que la malla que queda ansea una triangulacin), quedar una triangulacin Tn por n tringulos, en donde podemosaplicar nuestra hiptesis de induccin, i.e., en ella se cumple que vn `n + cn = 1. Hay 3formas en que puede borrarse un tringulo de tal modo que la malla resultante an seauna triangulacin:

a) Quitar 1 vrtice, 2 lados y 1 cara.

b) Quitar 2 vrtices, 3 lados y 1 cara.

c) Quitar 1 lado y 1 cara.

Si pensamos que Tn+1 consta de Tn ms cada uno de los casos anterior