9.0: Introducción

Hemos visto muchas vistas bonitas en nuestro fresco paseo a paso ligero. Hemos visto la simple elegancia de los conjuntos y las relaciones, la precisión del razonamiento probabilístico, la estructura recursiva de los árboles, la naturaleza explosiva de la combinatoria y mucho más. Ninguna de estas cosas nos ha sondeado hasta las profundidades, pero hemos apreciado su belleza y hemos tomado nota de dónde se encontraban a lo largo de nuestro camino abrasado. Recordarás esta caminata cuando te encuentres con tales conceptos una y otra vez en futuros cursos de informática y matemáticas, y en tu carrera más allá de lo académico.

Ahora tenemos una parada más que hacer antes de regresar al comienzo del sendero, y eso trata de la noción de prueba. Como hemos estudiado estas diversas entidades matemáticas, he señalado algunas de sus propiedades. Un árbol libre tiene un vértice más que un borde, por ejemplo. La cardinalidad de la unión de dos conjuntos es al menos tan grande como cada una de sus uniones individuales. Si volteas todos los bits y agregas uno en un esquema de complemento de dos y luego vuelves a realizar esa operación de voltear y agregar, volverás al número original. Pero con algunas excepciones, no hemos probado ninguna de estas cosas. Yo las acabo de decir, y tú las has tomado por fe.

Para establecer una verdad confiable, por supuesto, los matemáticos profesionales no están satisfechos con afirmaciones infundadas. Deben estar convencidos de que las afirmaciones que hacemos realmente se mantienen, y probablemente así, en todas las circunstancias. Lo que buscan es una prueba de un reclamo: una secuencia irrefutable de pasos lógicos que lleva ineludiblemente de nuestras premisas a nuestra conclusión. Hay varias formas de construir una prueba convincente, y en este capítulo se destacarán algunas de ellas.

La mayoría de los autores de textos matemáticos discretos, por cierto, entretejen el concepto de prueba a lo largo de todo el libro. Estoy tomando una salida radical al aplazar esta idea fundamental hasta el final. ¿Por qué hice esta elección? Un par de razones. Primero, como dije al principio, mi público objetivo para este libro son los futuros practicantes, no los investigadores teóricos. Creo que la mayoría de los informáticos en ejercicio necesitan fluidez con las herramientas de las matemáticas discretas, no la capacidad de idear nuevos teoremas fundamentales sobre ellas. Sobre todo necesitamos usar, no para probar. La segunda razón es que he encontrado que intercalar pruebas a lo largo de la presentación a menudo distrae al lector de los conceptos en cuestión, ya que el enfoque cambia ligeramente del concepto que se está discutiendo (la función, la gráfica dirigida, qué tienes) a la prueba sobre el concepto. Cuando la prueba misma toma el centro de atención, obliga al tema real a compartir el centro de atención. Y con material técnico como este, necesitamos toda la luz que podamos obtener.