mate discretas 6ta edicion

Johnsonbough 21x27

5/20/05

10:35 PM

Page 1

Esta edición, igual que las anteriores, incluye temas como algoritmos, combinatoria, conjuntos, funciones e inducción matemática. También toma en cuenta la comprensión y construcción de pruebas y, en general, el reforzamiento matemático.

Johnsonbaugh

Este libro se diseñó para un curso de introducción a las matemáticas discretas. Laexposición
es clara y adecuada, además de que contiene abundantes ejercicios.

MATEMÁTICAS
DISCRETAS

CAMBIOS DE LA SEXTA EDICIÓN

La obra tiene como apoyo el sitio Web:
www.pearsoneducacion.net/johnsonbaugh

Visítenos en:
www.pearsoneducacion.net

MATEMÁTICAS DISCRETAS

• El primer capítulo de lógica y demostraciones se amplió en forma considerable. Se
agregaron ejemplos de lógica enlenguajes de programación.
• Ahora se presentan varios ejemplos de algoritmos antes de llegar a la
notación de O mayúscula.
• Un nuevo capítulo de introducción a la teoría de números. Este capítulo incluye resultados clásicos (como la divisibilidad, la infinitud de
los primos, el teorema fundamental de la aritmética), así como los
algoritmos de teoría de números.
• Nueva sección desugerencias para resolver problemas.
• Nuevas secciones de solución de problemas para funciones y teoría de números.
• El estilo del seudocódigo se ha actualizado del
tipo Pascal al tipo Java.
• El número de ejemplos resueltos aumentó
a cerca de 600 y el número de ejercicios
aumentó a 4000.

Sexta edición

Sexta
edición

Richard Johnsonbaugh

LISTA DE SÍMBOLOS
LÓGICA
p∨q
p∧q
¬p
p→qp↔q
P≡Q
∀
∃
\

p o q; p. 2
p y q; p. 2
no p; p. 5
si p, entonces q; p. 8
p si y sólo si q; p. 12
P y Q son lógicamente equivalentes; p. 12
para todo; p. 19
existe; p. 22
por lo tanto; p. 43

NOTACIÓN DE CONJUNTOS
{x1,…, xn}
{x|p(x)}
x∈X
x X
X=Y
|X|
∅
X⊆Y
X⊂Y
P(X)
X∪Y

conjunto que consta de los elementos x1,…, xn; p. 76
conjunto de los elementos x que satisfacen lapropiedad p(x); p. 77
x es un elemento de X; p. 77
x no es un elemento de X; p. 77
igualdad de conjuntos (X y Y tienen los mismos elementos); p. 77
número de elementos en X; p. 77
conjunto vacío; p. 77
X es un subconjunto de Y; p. 77
X es un subconjunto propio de Y; p. 79
conjunto potencia de X (todos los subconjuntos de X); p. 79
X unión Y (todos los elementos en X o Y); p. 80

n

Xiunión de X1,…, Xn (todos los elementos que pertenecen al menos a un conjunto de X1,…, Xn); p. 83

Xi

unión de X1, X2,… (todos los elementos que pertenecen al menos a uno de X1, X2,…); p. 83

i=1
∞
i=1

∪S
X∩Y

unión de S (todos los elementos que pertenecen al menos a un conjunto en S); p. 83
X intersección Y (todos los elementos en X y Y); p. 80

n

Xi

intersección de X1,…, Xn(todos los elementos que pertenecen a todos los conjuntos X1, X2,…, Xn); p. 83

Xi

intersección de X1, X2,… (todos los elementos que pertenecen a todos los conjuntos X1, X2,…); p. 83

i=1
∞
i=1

∩S
X−Y
ෆ
X
(x, y)
(x1,…, xn)
X×Y

intersección de S (todos los elementos que pertenecen a todos los conjuntos de S); p. 83
diferencia de conjuntos (todos los elementos en X pero no enY); p. 80
complemento de X (todos los elementos que no están en X); p. 80
par ordenado; p. 83
n-eada; p. 84
producto cartesiano de X y Y [pares (x, y) con x en X y y en Y]; p. 83

RELACIONES
xRy
[x]
R−1
R2 R1
x y

(x, y) está en R (x está relacionada con y mediante la relación R); p. 117
clase de equivalencia que contiene a x; p. 127
relación inversa [todo (x, y) que está en R]; p.122
composición de relaciones; p. 122
x R y; p. 121

FUNCIONES
f (x)
f: X → Y
f g
f −1
f (n) = O(g(n))
f (n) = (g(n))
f (n) = (g(n))

valor asignado a x; p. 88
función de X a Y; p. 87
composición de f y g; p. 97
función inversa [todo (y, x) con (x, y) que está en f ]; p. 96
|f (n)| ≤ C|g(n)| para n suficientemente grande; p. 158
c|g(n)| ≤ |f (n)| para n suficientemente...