Libro Digital Mate para Computación 1 PDF

Preview

Summary

Libro matematica para computacion usado en 3 cuatrimestre 2021...

Description

MATEMÁTICAS

PARA COMPUTACIÓN

I

MATEMÁTICAS

PARA COMPUTACIÓN

Seymour Lipschutz, Ph. D. Temple University

Marc Lars Lipson, Ph. D. University of Virginia

Revisión técnica María de Lourdes Quezada Batalla Departamento de Ciencias Básicas Instituto Tecnológico y de Estudios Superiores de Monterrey Campus Estado de México

I

Managing Director Latam: Fernando Valenzuela Product Director Latam: María Clara Andrade Portfolio Manager: Marcela Rocha Martínez Coordinadora Custom Publishing: Celina Orozco Correa Traducción: Hugo Villagómez Velázquez Diseño y formación de portada: Cícero

MATEMÁTICAS PARA COMPUTACIÓN I Todos los derechos reservados. Esta publicación no puede ser reproducida, ni parcial ni totalmente, ni registrada en/o transmitida por un sistema de recuperación de información, en ninguna forma ni formato, por ningún medio, sea mecánico, fotocopiado, electrónico, magnético, electroóptico o cualquier otro, sin el permiso previo y por escrito de la editorial.

DERECHOS RESERVADOS © 2017, respecto a la primera edición por: McGRAW-HILL INTERAMERICANA EDITORES, S.A. de C.V. Prolongación Paseo de la Reforma 1015 Torre A, Piso 16 Col. Desarrollo Santa Fe Delegación Álvaro Obregón C.P. 01376, México, D.F. Miembro de la Cámara Nacional de la Industria Editorial Mexicana Reg. No. 736

ISBN: 978-1-4562-5626-5

Adaptado de: Seymour Lipschutz y Marc Lars Lipson, Matemáticas discretas. Tercera edición (Capítulos 1-7) © 2009. Derechos reservados por McGRAW-HILL INTERAMERICANA EDITORES, S.A. de C.V. ISBN: 978-970-10-7236-3 Copyright © 2007, 1997, 1976 de la edición en inglés Discrete Mathematics, by Seymour Lipschutz and Marc Lipson, published by The McGraw-Hill Companies, Inc. All rights reserved

02/17

0123456789

2345689017

Impreso en México

Printed in Mexico

ACERCA DE LOS AUTORES

SEYMOUR LIPSCHUTZ da clases en la Facultad de Matemáticas de la Universidad Temple y antes enseñó en el Instituto Politécnico de Brooklin. Se doctoró en 1960 en el Instituto Courant de Ciencias Matemáticas de la Universidad de Nueva York. Es uno de los más prolíficos autores de la serie Schaum’s Outlines, y también es autor de Probability; Finite Mathematics, 2a. edición; Linear Algebra, 3a. edición; Beginning Linear Algebra; Set Theory; y Essential Computer Mathematics. MARC LARS LIPSON da clases en la Universidad de Virginia y antes enseñó en la Facultad de la Universidad de Georgia. Se doctoró en finanzas en 1994 en la Universidad de Michigan. También es coautor de Linear Algebra, 3a. edición y 2000 Solved Problems in Discrete Mathematics con Seymour Lipschutz.

V

PRÓLOGO

Las matemáticas discretas, el estudio de los sistemas finitos, han adquirido cada vez más importancia en la medida en que ha avanzado la era de las computadoras. Básicamente, la computadora digital es una estructura finita, y muchas de sus propiedades pueden comprenderse e interpretarse en el marco de referencia de los sistemas matemáticos finitos. Este libro, al presentar el material esencial, cumple los requisitos de un curso formal de matemáticas discretas, o como complemento de cualquier texto actual. Los tres primeros capítulos cubren el material normal sobre conjuntos, relaciones y funciones y algoritmos. Luego, siguen capítulos sobre lógica, conteo y probabilidad. El capítulo sobre funciones y algoritmos incluye un análisis de cardinalidad y conjuntos numerables, y complejidad. Se recalca que los capítulos han sido escritos de modo que sea posible modificar su orden sin dificultad ni pérdida de continuidad. Cada capítulo empieza con un planteamiento claro de las definiciones, principios y teoremas pertinentes, con material ilustrativo y de otros materiales descriptivos. Después, se plantean conjuntos de problemas resueltos y complementarios. Los problemas resueltos sirven para ilustrar y ampliar el material, y también incluye demostraciones de teoremas. Los problemas complementarios proporcionan una revisión completa del material del capítulo. Se ha incluido más material, el cual puede cubrirse en la mayor parte de los primeros cursos. Lo anterior se ha hecho con la intención de que el libro sea más flexible, a fin de ofrecer un libro de referencia más útil, y para estimular un mayor interés en los temas presentados. SEYMOUR LIPSCHUTZ MARC LARS LIPSON

VII

CONTENIDO

CAPÍTULO 1

Teoría de conjuntos

CAPÍTULO 2

Relaciones

23

CAPÍTULO 3

Funciones y algoritmos

43

1.1 Introducción 1.2 Conjuntos, elementos y subconjuntos 1.3 Diagramas de Venn 1.4 Operaciones con conjuntos 1.5 Álgebra de conjuntos, dualidad 1.6 Conjuntos finitos y principio de conteo 1.7 Clases de conjuntos, conjuntos potencia y particiones 1.8 Inducción matemática Problemas resueltos Problemas suplementarios

2.1 Introducción 2.2 Producto de conjuntos 2.3 Relaciones 2.4 Representación gráfica de las relaciones 2.5 Composición de relaciones 2.6 Tipos de relaciones 2.7 Propiedades de cerradura 2.8 Relaciones de equivalencia 2.9 Relaciones de orden parcial 2.10 Relaciones n-arias Problemas resueltos Problemas suplementarios

3.1 3.2 3.3 3.4 3.5 3.6

Introducción Funciones Funciones uno a uno, sobre e invertibles Funciones matemáticas, funciones exponencial y logarítmica Sucesiones, clases indexadas de conjuntos Funciones definidas en forma recursiva

1

1 1 3 4 7 8 10 12 12 18

23 23 24 25 27 28 30 31 33 33 34 40

43 43 46 47 50 52

IX

X

CONTENIDO

CAPÍTULO 4

CAPÍTULO 5

CAPÍTULO 6

3.7 Cardinalidad 3.8 Algoritmos y funciones 3.9 Complejidad de los algoritmos Problemas resueltos Problemas suplementarios

55 56 57 60 66

Lógica y cálculo de proposiciones

70

4.1 Introducción 4.2 Proposiciones y declaraciones compuestas 4.3 Operaciones lógicas básicas 4.4 Proposiciones y tablas de verdad 4.5 Tautologías y contradicciones 4.6 Equivalencia lógica 4.7 Álgebra de proposiciones 4.8 Proposiciones condicionales y bicondicionales 4.9 Argumentos 4.10 Funciones proposicionales, cuantificadores 4.11 Negación de proposiciones cuantificadas Problemas resueltos Problemas suplementarios

70 70 71 72 74 74 75 75 76 77 79 82 86

Técnicas de conteo

88

5.1 Introducción 5.2 Principios básicos de conteo 5.3 Funciones matemáticas 5.4 Permutaciones 5.5 Combinaciones 5.6 El principio del palomar 5.7 El principio de inclusión-exclusión 5.8 Diagramas de árbol Problemas resueltos Problemas suplementarios

88 88 89 91 93 94 95 95 96 103

Técnicas de conteo avanzadas, recurrencia 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9

Introducción Combinaciones con repeticiones Particiones ordenadas y no ordenadas Otra aplicación del principio de inclusión-exclusión Otra aplicación del principio del palomar Relaciones recursivas, o de recurrencia Relaciones recursivas, o de recurrencia, lineales con coeficientes constantes Solución de relaciones de recurrencia lineales homogéneas de segundo orden Solución de relaciones de recurrencia lineales homogéneas generales

107 107 107 108 108 110 111 113 114 116

CONTENIDO XI

Problemas resueltos Problemas suplementarios

CAPÍTULO 7

Probabilidad 7.1 Introducción 7.2 Espacio muestral y eventos 7.3 Espacios de probabilidad finitos 7.4 Probabilidad condicional 7.5 Eventos independientes 7.6 Ensayos independientes repetidos, distribución binomial 7.7 Variables aleatorias 7.8 Desigualdad de Chebyshev, ley de los grandes números Problemas resueltos Problemas suplementarios

118 121

123 123 123 126 127 129 130 132 135 136 149

conjuntos Teoría de

1

CAPÍTULO

1.1

INTRODUCCIÓN

El concepto de conjunto aparece en todas las matemáticas. Por ello es que conviene iniciar este capítulo con la notación y la terminología básicas de la teoría de conjuntos, las cuales se utilizan en todo el texto; el capítulo termina con la definición formal, y ejemplos, de la inducción matemática.

1.2 CONJUNTOS, ELEMENTOS Y SUBCONJUNTOS Un conjunto es una colección bien definida de objetos, que se denominan elementos o miembros del conjunto. Las letras mayúsculas A, B, X, Y, . . . , denotan conjuntos y las minúsculas a, b, x, y, . . . , denotan elementos de conjuntos. Algunos sinónimos de “conjunto” son “clase”, “colección” y “familia”. La pertenencia a un conjunto se denota: a ∈ S denota que a pertenece al conjunto S. a, b ∈ S denota que a y b pertenecen al conjunto S. Aquí ∈ es el símbolo para indicar “es un elementos de” y ∈ significa “no es un elemento de”.

Especificación de conjuntos Hay dos formas para especificar un conjunto particular. Una forma, de ser posible, consiste en enumerar sus elementos separados por comas y escritos entre llaves { }. La segunda es escribir las propiedades que caracterizan a los elementos del conjunto. Dos ejemplos de lo anterior son: A = {1, 3, 5, 7, 9}

y B = {x | x es un entero par, x > 0}

Es decir, A consta de los elementos 1, 3, 5, 7, 9. El segundo conjunto se lee: B es el conjunto de x tal que x es un entero par y x es mayor que 0, denota el conjunto B, cuyos elementos son los enteros pares positivos. Observe que para denotar un miembro del conjunto se usa una letra, casi siempre x; la recta vertical | se lee “tal que” y la coma “y”. EJEMPLO 1.1 a) El conjunto A anterior también se escribe como A = {x | x es un entero positivo impar, x < 10}. b) Aunque no es posible listar todos los elementos del conjunto B anterior, a este conjunto se le especifica como B = {2, 4, 6, . . .} donde se supone que todo mundo lo entiende. Observe que 8 ∈ B, pero 3 ∈ B.

1

2 CAPÍTULO 1 T EORÍA

DE CONJUNTOS

c) Sean E = {x | x2 − 3x + 2 = 0}, F = {2, 1} y G = {1, 2, 2, 1}. Entonces E = F = G. Aquí es preciso señalar que un conjunto no depende de la forma en que se muestren sus elementos. Un conjunto es el mismo aun si sus elementos se repiten o están en desorden. Incluso si es posible enumerar los elementos de un conjunto, hacerlo tal vez no sea práctico. Es por esto que los elementos de un conjunto se enumeran sólo si son pocos; en caso contrario, un conjunto se describe con la indicación de la propiedad que caracteriza a sus elementos.

Subconjuntos Suponga que todo elemento de un conjunto A también es un elemento de un conjunto B; es decir, si a ∈ A implica que a ∈ B. Entonces se dice que A es un subconjunto de B. También se dice que A está contenido en B o que B contiene a A. Esta relación se escribe A⊆B o B⊇A Dos conjuntos son iguales si ambos tienen los mismos elementos o, equivalentemente, si cada uno está contenido en el otro. Es decir: A  B si y sólo si A ⊆ B y B ⊆ A Si A no es un subconjunto de B —porque al menos un elemento de A no pertenece a B— se escribe A ⊆ B. EJEMPLO 1.2

Considere los conjuntos: A  {1, 3, 4, 7, 8, 9}, B  {1, 2, 3, 4, 5},

C  {1, 3}.

Entonces C ⊆ A y C ⊆ B, ya que 1 y 3, los elementos de C, también son miembros de A y B. Pero B ⊆ A, puesto que algunos elementos de B, por ejemplo, 2 y 5, no pertenecen a A. En forma semejante, A ⊆ B.

Propiedad 1: En matemáticas es una práctica común cruzar un símbolo con una línea vertical “|” o una diagonal “/” para indicar el significado opuesto o negativo del símbolo. Propiedad 2: La declaración A ⊆ B no excluye la posibilidad de que A  B. De hecho, para todo conjunto A se tiene A ⊆ A, ya que todo elemento de A pertenece a A. No obstante, si A ⊆ B y A = B, entonces se dice que A es un subconjunto propio de B (lo que algunas veces se escribe A ⊂ B). Propiedad 3: Suponga que todo elemento de un conjunto A pertenece a un conjunto B y que todo elemento de B pertenece a un conjunto C. Entonces resulta evidente que todo elemento de A también pertenece a C. En otras palabras, si A ⊆ B y B ⊆ C, entonces A ⊆ C. Las propiedades anteriores llevan al siguiente teorema: Teorema 1.1: Sean A, B y C tres conjuntos cualesquiera. Entonces: i) A ⊆ A ii) Si A ⊆ B y B ⊆ A, entonces A = B iii) Si A ⊆ B y A ⊆ B, entonces A ⊆ B

Símbolos especiales En el texto aparecen muy a menudo algunos conjuntos, para los que se usan símbolos especiales. Algunos de estos símbolos son: N = conjunto de números naturales o enteros positivos: 1, 2, 3, . . . Z = conjunto de todos los enteros: . . . , −2, −1, 0, 1, 2, . . . Q = conjunto de números racionales R = conjunto de números reales C = conjunto de números complejos Observe que N ⊆ Z ⊆ Q ⊆ R ⊆ C.

1.3 DIAGRAMAS

DE

VENN

3

Conjunto universo y conjunto vacío Todos los conjuntos que se estudian en cualquier aplicación de la teoría de conjuntos pertenecen a un gran conjunto fijo denominado universo, que se denota por U a menos que se establezca o implique otra cosa. Dados un conjunto universo U y una propiedad P, en U puede no haber elementos que tengan la propiedad P. Por ejemplo, el siguiente conjunto no tiene elementos: S = {x | x es un entero positivo, x2 = 3} Un conjunto que no tiene elementos se denomina conjunto vacío o conjunto nulo y se denota por ∅ Sólo hay un conjunto vacío. Es decir, si S y T son vacíos, entonces S = T, ya que tienen exactamente los mismos elementos, a saber, ninguno. El conjunto vacío ∅ también se considera como un subconjunto de cualquier otro conjunto. Así, el planteamiento formal de este sencillo resultado es: Teorema 1.2: Para cualquier conjunto A, se tiene ∅ ⊆ A ⊆ U.

Conjuntos ajenos o disjuntos Dos conjuntos A y B son ajenos o disjuntos, si no tienen elementos en común. Por ejemplo, suponga A  {1, 2},

B  {4, 5, 6}

y C  {5, 6, 7, 8}.

Entonces A y B son ajenos, y A y C son ajenos. Pero B y C no son ajenos porque B y C tienen elementos en común, 5 y 6. Observe que si A y B son ajenos, entonces ninguno es un subconjunto del otro (a menos que uno sea el conjunto vacío).

1.3

DIAGRAMAS DE VENN

Un diagrama de Venn es un gráfico donde los conjuntos se representan con regiones encerradas en un plano. Aquí el conjunto universo U es el interior de un rectángulo y los otros conjuntos se representan por círculos dentro del rectángulo. Si A ⊆ B, entonces el círculo que representa a A está dentro del círculo que representa a B, como se muestra en la figura 1-1a). Si A y B son ajenos, entonces el círculo que representa a A está separado del círculo que representa a B, como se muestra en la figura 1-1b).

U B

A

a) A ⊆ B

U

U

B

A

b ) A y B son ajenos

Figura 1-1

B

A

c)

4 CAPÍTULO 1 T EORÍA

DE CONJUNTOS

No obstante, si A y B son dos conjuntos arbitrarios, es posible que algunos elementos estén en A pero no en B, que otros estén en B pero no en A, que algunos estén tanto en A como en B, y que otros no estén ni en A ni en B; por tanto, en general A y B se representan como en la figura 1-1c).

Argumentos y diagramas de Venn Muchas declaraciones verbales son, en esencia, sobre conjuntos y, en consecuencia, se les puede describir mediante diagramas de Venn; por tanto, éstos sirven para determinar si un argumento es válido o no. EJEMPLO 1.3 Demuestre que el siguiente argumento (una adaptación de un libro de lógica de Lewis Carroll, autor de Alicia en el país de las maravillas) es válido: S1: Todos mis objetos de estaño son cazos. S2: Encuentro muy útiles todos tus regalos. S3: Ninguno de mis cazos es útil. S3: Tus regalos no son de estaño. Las declaraciones S1, S2 y S3, arriba de la línea horizontal, son los supuestos o las hipótesis y la declaración S, abajo de la línea horizontal, es la conclusión. El argumento es válido si la conclusión S se obtiene en forma lógica a partir de las hipótesis S1, S2 y S3. Si S1 son todos los objetos de estaño que contiene el conjunto de los cazos, entonces S3, el conjunto de los cazos, y el conjunto de los objetos útiles son ajenos. Además, por S2, el conjunto de “tus regalos” es un subconjunto del conjunto de los objetos útiles. En consecuencia, es posible dibujar el diagrama de Venn que se muestra en la figura 1-2. Resulta evidente que la conclusión es válida por el diagrama de Venn, porque el conjunto “tus regalos” es ajeno al conjunto de los objetos de estaño.

objetos de estaño

tus regalos

cazos

objetos útiles

Figura 1-2

1.4 OPERACIONES CON CONJUNTOS En esta sección se presentan varias operaciones con conjuntos, como son las operaciones básicas de unión, intersección y complemento.

Unión e intersección La unión de dos conjuntos A y B, que se denota por A ∪ B, es el conjunto de todos los elementos que pertenecen a A o a B; es decir, A ∪ B = {x | x ∈ A o x ∈ B} Aquí “o” se usa en el sentido incluyente de y/o. La figura 1-3a) es un diagrama de Venn en el que A ∪ B está sombreada. La intersección de dos conjuntos A y B, que se denota por A ∩ B , es el conjunto de los elementos que pertenecen tanto a A como a B; es decir, A ∩ B = {x | x ∈ A y x ∈ B} La figura 1-3b) es un diagrama de Venn en el que A ∩ B está sombreada.

1.4 OPERACIONES

A

B

A

a ) A ∪ B está sombreada

CON CONJUNTOS

5

B

b ) A ∩ B está sombreada

Figura 1-3

Recuerde que los conjuntos A y B son disjuntos o ajenos si no tienen elementos en común o, al aplicar la definición de intersección, si A ∩ B = M, el conjunto vacío. Suponga que S=A∪B y A∩B=∅ Entonces S se denomina unión disjunta, o ajena, de A y B.

EJEMPLO 1.4 a) Sean A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 7}, C = {2, 3, 8, 9}. Entonces A ∪ B = {1, 2, 3, 4, 5, 6, 7}, A ∩ B = {3, 4},

A ∪ C = {1, 2, 3, 4, 8, 9}, A ∩ C = {2, 3},

B ∪ C = {2, 3, 4, 5, 6, 7, 8, 9}, B ∩ C = {3}.

b) Sean U el conjunto de estudiantes en una universidad, M el conjunto de estudiantes varones y F el conjunto de estudiantes mujeres. U es la unión disjunta de M y F; es decir, U=M∪F

y M∩F=∅

Esto se debe a que cualquier estudiante en U está en M o en F, y resulta evidente que ningún estudiante pertenece tanto a M como a F; es decir, M y F son disjuntos. Es necesario observar las siguientes propiedades de la unión y la intersección.

Propiedad 1: Todo elemento x en A ∩ B pertenece tanto a A como a B; así, x pertenece a A y x pertenece a B. Entonces, A ∩ B es un subconjunto de A y de B; a saber, A∩B⊆A y

A∩B⊆B

Propiedad 2: Un elemento x pertenece a la unión A ∪ B si x pertenece a A o x pertenece a B; así, cualquier elemento en A pertenece a A ∪ B, y cualquier elemento en B pertenece a A ∪ B. Es decir, A⊆A∪B y B⊆A∪B El planteamiento formal de los resultados anteriores es: Teorema 1.3: Para dos conjuntos A y B arbitrarios, se tiene: i) A ∩ B ⊆ A ⊆ A ∪ B y ii) A ∩ B ⊆ B ⊆ A ∪ B. La operación de inclusión de conjuntos se relaciona estrechamente con las operaciones de unión e intersección, como se muestra en el siguiente teorema. Teorema 1.4: Las siguientes expresiones son equivalentes: A ⊆ B,

A ∩ B = A,

A ∪ B = B.

Este teorema se demuestra en el problema 1.8. Otras condiciones equivalentes también se proporcionan en el problema 1.31.

6 CAPÍTULO 1 T EORÍA

DE CONJUNTOS

a ) Ac está sombreado

b ) A\B está sombreada

c) A ⊕ B está sombreada

Figura 1.4

Complementos, diferencias y diferencias simétricas Recuerde que todos...