Matemáticas Para la computación PDF

Preview

Summary

Matemáticas Para iacomputación JOSÉ A. JIMÉNEZ MURILLO Apoyo«nía Alfaomega www.FreeLibros.me á Matemáticas Para ia computación www.FreeLibros.me Matemáticas para iacomputación JOSE ALFREDO JIMÉNEZ MURILLO www.FreeLibros.me Francisco Javier Rodríguez Cruz Datos catalográficos [email protected]...

Description

Matemáticas Para iacomputación JOSÉ A. JIMÉNEZ MURILLO

Alfaomega

www.FreeLibros.me

Apoyo«nía

á

Matemáticas Para ia computación

www.FreeLibros.me

Matemáticas para iacomputación JOSE ALFREDO JIMÉNEZ MURILLO

www.FreeLibros.me

Datos catalográficos

Francisco Javier Rodríguez Cruz

[email protected]

Jiménez, José A. Matemáticas para la Computación Primera Edición

G erente editorial Marcelo Grillo Giannetto

Alfaomega Grupo Editor, S.A. de C.V., M éxico

[email protected]

ISBN: 978-970-15-1401-6,

h

Formato: 21 x 24 cm

i •:

Páginas: 496

Matemáticas para la Computación José Alfredo Jiménez Murillo Derechos reservados © Alfaom ega Grupo Editor, S.A. de C. V., M éxico. Primera edición: Alfaom ega Grupo Editor, México, diciembre 2008 © 2009 Alfaomega Grupo Editor, S.A. de C.V. Pitágoras 1139, Col. Del Valle, 03100, M éxico D.F.

Q O é Miembro de la Cámara Nacional de la Industria Editorial Registro No. 2317

.

J 55

Pág. Web: http://www.alfaomega.com.mx E-mail: [email protected]

A é y

ISB N : 978-970-15-1401-6

M 35

3 i

i5 02.

Derechos reservados: Esta obra es propiedad intelectual de su autor y los derecroá^t pQ&TkM^iii«Mengua española han sido legalmente transferidos al editor. Prohibida su reproducción parcial o total por cualquier medio sin permiso por escrito del propietario de los derechos del copyright. Nota importante: La información contenida en esta obra tiene un fin exclusivamente didáctico y, por lo tanto, no está previsto su aprovechamiento a nivel profesional o industrial. Las indicaciones técnicas y programas incluidos, han sido elaborados con gran cuidado por el autor y reproducidos bajo estrictas normas de control. A LF A O M E G A GRUPO EDITOR, S.A. de C.V. no será jurídicamente responsable por: errores u omisiones; daños y perjuicios que se pudieran atribuir al uso de la información comprendida en este libro, ni por la utilización indebida que pudiera dársele. Edición autorizada para venta en todo el mundo. Impreso en México. Printed in México.

Empresas del grupo: México: Alfaomega Grupo Editor, S.A. de C.V. - Pitágoras 1139, Col. Del Valle, México. D.F. - C.P. 03100. Tel.: (52-55) 5089-7740 - Fax: (52-55) 5575-2420 / 2490. Sin costo: 01-800-020-4396 E-mail: [email protected]

C olom bia: Alfaomega Colombiana S.A. - Carrera 15 No. 64 A 29 - PBX (57-1) 2100122, Bogotá, Colombia, Fax: (57-1) 6068648 - E-mail: [email protected]

C hile: Alfaomega Grupo Editor, S.A. - General del Canto 370-Providencia, Santiago, Chile Tel.: (56-2) 235-4248 - Fax: (56-2) 235-5786 - E-mail: [email protected] A rgentina: Alfaomega Grupo Editor Argentino, S.A. - Paraguay 1307 P.B. “ 11” , Buenos Aires, Argentina, C.P. 1057-T e l.: (54-11)4811-7183 / 8352, E-mail: [email protected]

www.FreeLibros.me

311502

Contenido Contenido de la página Web de apoyo.......................................................

xi

Página Web de apoyo..................................................................................

xvii ,

Prefacio......................................................................................................

Capítulo I Sistemas numéricos

xix.

2

1.1

Introducción................................................................................................

4

1.2

Sistema decimal...........................................................................................

5

1.3

Sistemas binario, octal y hexadecimal.........................................................

6

1.3.1

Sistema binario........................ .....................................................

6

1.3.2

Sistema octal............ ......................................................................

8

1.3.3

Sistema hexadecimal.....................................................................

10

1.4

Generalización de las conversiones.............................................................

12

1.5

Operaciones básicas....................................................................................

13

1.5.1

Suma....... ?.....................................................................................

14

1.5.2

Resta...............................................................................................

16

1.5.3

Multiplicación.................................................................................

19

1.5.4

División..........................................................................................

21

1.6

Suma de dos cantidades en complemento a 2 .............................................

24

1.7

Aplicación de los sistemas numéricos.........................................................

30

1.8

Resumen.....................................................................................................

32

1.9

Problemas....................................................................................................

34

Capítulo II Métodos de conteo

40

2.1

Introducción.................................................................................................

42

2.2

Principios fundamentales del conteo............................................................

42

2.2.1

Principio fundamentaldel producto................................................

42

2.2.2

Principio fundamental de la adición...............................................

45

ALFAOM EGA

www.FreeLibros.me

ri

Contenido

#, i

u

2.3

Permutaciones........................................................................ ................... '

46

2.4

Combinaciones....................................................................... ...................

52

2.5

Aplicaciones en la computación.............................................. ...................

57

2.5.1

Binomio elevado a la potencia n ................................ ...................

57

2.5.2

Triángulo de Pascal................................................... ........... w .

60

2.5.3

Sort de la burbuja (bubble sort)................................. ....... .

61

2.6

Resumen................................................................................. ..................

62

2.7

Problemas............................................................................... ...................

64

C a p ítu lo

III

72

C o n ju n t o s

3.1

Introducción............................................................................ ...................

74

3.2

Concepto de conjunto.............................................................

74

3.3

Subconjuntos.......................................................................... ...................

78

3.4

Diagramas de Venn................................................................. ..................

79

3.5

Operaciones y leyes de conjuntos.......................................... ..................

80

3.5.1

Unión (A u B ) ............................................................. ...................

80

3.5.2

Intersección (A n B ).................................................. ...................

82

3.5.3

Ley distributiva......................................................... ...................

83

3.5.4

Complemento ( A ') ..................................................... ...................

84

3.5.5

Ley de Morgan........................................................... ...................

85

3.5.6

Diferencia (A - B )...................................................... ...................

87

3.5.7

Diferencia simétrica (A © B )...................................... ...................

87

3.6

Simplificación de expresiones usando leyes de conjuntos

...................

92

3.7

Relación entre teoría de conjuntos, lógica matemática y álgebra booleana.................................................................. ...................

97

3.8

Conjuntos finitos..................................................................... ...................

98

3.9

Aplicación de la teoría de conjuntos....................................... ............. .....

101

3.10 Resumen................................................................................. ...................

102

3.11

104

ALFAOMEGA

Problemas............................................................................... ...................

www.FreeLibros.me

C o n t e n id o

V il

C a p ít u lo IV Lógica matemática

114

4.1

Introducción..............................................................................................

116

4.2

Proposiciones.............................................................................................

117

4.3

4.2.1

Proposiciones compuestas.............................................................

117.

4.2.2

Proposición condicional (-^ )...........................................................

121

4.2.3

Proposición bicondicional ()........................................................

122

Tablas de verdad.......................................................................................

125

4.3.1

Tautología, contradicción y contingencia......................................

127

4.3.2

Contradicción.............................................. ...................................

129

4.3.3

Contingencia...................................................................................

130

4.4

Inferencia lógica........................................................................................

130

4.5

Equivalencia lógica.....................................................................................

133

4.6

Argumentos válidos y no válidos................................................................

137

4.6.1

Tipos de argumentos................................................... '................

141

Demostración formal.................................................................................

142

4.7

4.7.1

Demostración por el método directo...............................................

142

4.7.2

Demostración por contradicción....................................................

147

4.8

Predicados y sus valores de verdad...........................................................

150

4.9

Inducción matemática................................................................................

159

4.10

Aplicación de la lógica matemática...........................................................

163

4.11

Resumen...................................................................................................

165

4.12

Problemas.................................................................................................

168

Capítulo V Álgebra booleana

176

5.1

Introducción...............................................................................................

178

5.2

Expresiones booleanas................................................................................

178

5.3

Propiedades de las expresionesbooleanas...................................................

180

5.4

Optimización de expresiones booleanas....................................................

182

5.4.1 5.4.2

Simplificación de expresiones booleanas mediante teoremas del álgebra de Boole......................................................................

182

Simplificación de expresiones booleanas usando mapas de Karnaugh..................................................................................

185

www.FreeLibros.me

ALFAOMEGA

■I ■ V IH

C o n t e n id o

5.5

Compuertas lógicas.....................................................................................

197

5.6

Aplicaciones del álgebra booleana.............................................................

206

5.7

Resumen.....................................................................................................

209

5.8

Problemas...................................................................................................

210

•í*v.

Capítulo VI Relaciones

218 t

6.1

Introducción................................................................................................ .

220

6.2

Elementos de una relación..........................................................................

220

6.3

6.4

6.2.1

Producto cartesiano.......................................................................

222

6.2.2

Relación binaria.............................. ..............................................

223

6.2.3

Matriz de una relación...................................................................

224

6.2.4

Grafo de una relación.....................................................................

225

Tipos de relaciones......................................................................................

227

6.3.1

Relación reflexiva..........................................................................

228

6.3.2

Relación irreflexiva.........................................................................

228

6.3.3

Relación simétrica..........................................................................

229

6.3.4

Relación asimétrica........................................................................

229

6.3.5

Relación antisimétrica....................................................................

230

6.3.6

Relación transitiva..........................................................................

230

Relaciones de equivalencia, clases de equivalencia y particiones..............

235

6.4.1

Cerraduras.....................................................................................

239

6.5

Operaciones entre relaciones.......................................................................

242

6.6

Propiedades de las relaciones......................................................................

246

6.7

Aplicaciones de las relaciones.....................................................................

248

6.8

6.7.1

Una lista enlazada es una relación................................................

248

6.7.2

Las relaciones en las bases de datos..............................................

253

Funciones.....................................................................................................

257

6.8.1

Composición de funciones..............................................................

261

6.8.2

Tipos de funciones.........................................................................

262

6.8.3

Funciones invertibles...................................................,7................

265

Aplicación de las funciones.........................................................................

267

6.10 Resumen......................................................................................................

268

6.11 Problemas....................................................................................................

272

6.9

ALFAOMEGA

www.FreeLibros.me

C o n t e n id o

ÍX

Capítulo VII Grafos

284

7.1

Introducción.................................................................................................

286

7.2

Partes de un grafo........................................................................................

287

7.3

Tipos de grafos...........................................................................................

7.4

Representación matricial.............................................................................

292

7.5

Caminos y circuitos......................................................................................

294

7.6