Matematicas discretas

MATEMÁTICA DISCRETA
APUNTES ESCET 2003

2

Introducción
La introducción de las notas de un curso de Matemática Discreta para estudiantes de Informática debe comenzar tratando de responder la pregunta de qué es la Matemática discreta. La primera respuesta obvia es señalar que la matemática discreta es la parte de la matemática que estudia los objetos discretos. Esta respuesta no resultamuy satisfactoria pues seguimos sin conocer el signicado del calicativo discreto. No resulta fácil, sin recurrir a deniciones formales que en este contexto resultarían muy oscuras, dar una denición de lo que es ser discreto, así que vamos a utilizar algunos ejemplos familiares para el lector. Comenzamos con los números naturales, un objeto que, aunque matemáticamente precisa de cierto esfuerzopara su presentación, pertenece a nuestro bagaje cultural común: N = {1, 2, 3, 4, 5...}. Todos entendemos lo que es tener 5 sillas o que en clase haya 80 alumnos. Cuando los representamos solemos usar una semirrecta colocando a la derecha los números mayores:

1 •

2 •

3 •

4 •

... ...

Una vez que tenemos los números naturales, recurramos a un objeto matemático un poco más complejo,los números reales positivos R+ . De nuevo éste es un conjunto conocido que contiene al conjunto de los números naturales, N ⊂ R+ , y es estrictamente más grande. Ahora contiene al cero, a las fracciónes y también a esos números especiales que no son fracciones (es decir que no se pueden escribir mediante un número decimal con una canti√ dad nita de cifras o con un período) como por ejemplo elnúmero 2 o el número e. 3

4 También solemos representar a los números reales positivos mediante una semirrecta donde cada uno de sus puntos es un número real y hacia la derecha quedan ordenados de menor a mayor:

0

1

2

3

4

...

Miremos con detenimiento un conjunto y otro. Hay cuantiosas diferencias entre ellos pero aquí vamos a centrarnos en las que establecen los conceptos dediscreto (que se aplica a los números naturales) y de continuo (a los números reales). Los números naturales son discretos, es decir, se disponen en la semirrecta que los representa separados entre sí. Del uno al dos hay un salto de una unidad. No hay ningún número natural entre ellos, es decir, no existe n ∈ N tal que 1 < n < 2. Lo mismo ocurre entre el dos y el tres o entre dos cualesquieranúmeros naturales consecutivos. Los conjuntos nitos o los números enteros Z (unión de los naturales el 0 y los negativos) tienen de igual manera esta propiedad. Sin embargo, los números reales son muy distintos. Están todos pegados, no quedan huecos entre ellos, la recta que los representa está completamente punteada. Entre el uno y el dos no hay agujeros, siempre hay números entre ellos; está porejemplo el 1.5 en medio. Entre el 1 y el 1.5 está por ejemplo el 1.2. Y entre el 1 y un número muy cercano a 1, pongamos por ejemplo el 7 1+10−10 (verdaderamente cercano ya que la distancia es cero coma un millón 8 de ceros y luego un uno), hay números por medio, por ejemplo el 1 + 10−10 . Valga esta aproximación a la noción de ser continuo: completamente pegados entre sí, sin espacios que losseparan. De la formalización de este concepto es de donde parte la idea de límite y por tanto los conceptos de continuidad de funciones, derivada, integral y, en n, todos los que se estudiarán en el curso de Bases de Matemáticas. Con esta noción intuitiva acerca de qué es la matemática discreta la lista de contenidos del curso nos aclara un poco más:

• Lógica • Algoritmos • Aritmética y Aritméticamodular

5

• Combinatoria • Grafos • Relaciones
Esto es, formalizar, diseñar procesos nitos para resolver problemas, analizar las propiedades fundamentales de los números enteros, contar, enumerar, relacionar conjuntos nitos, representar estas relaciones,... Una vez que hemos respondido (de forma intuitiva) a la pregunta sobre el concepto de matemática discreta se trata de responder...