Matematicas Discretas

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 resulta muy 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 esfuerzo para su presentación, pertenece a nuestro

bagaje cultural común:

N = f1; 2; 3; 4; 5:::g:

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 cantidad

nita de cifras o con un período) como por ejemplo el número

p

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 de

discreto (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 2

N tal que 1 < n < 2. Lo mismo ocurre entre el dos y el tres o entre

dos cualesquiera nú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á por ejemplo 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

1+10¡107 (verdaderamente cercano

...