4. Técnicas de demostración matemática

4.1 Introducción

En matemática no alcanza con que una afirmación parezca verdadera ni con que funcione para algunos ejemplos. Una demostración es una cadena de razonamientos que establece que una proposición es verdadera a partir de definiciones, axiomas, hipótesis y resultados ya demostrados.

En programación ocurre algo parecido. Ejecutar un algoritmo con diez casos de prueba aporta evidencia, pero no garantiza su corrección para todos los casos válidos. Una demostración de corrección explica por qué el resultado se cumple siempre que se respeten las condiciones de entrada.

4.2 Proposiciones

Una proposición es un enunciado al que podemos asignar exactamente uno de dos valores: verdadero o falso. No depende de quién lo lea ni de una opinión personal.

Una expresión con variables se convierte en proposición cuando fijamos sus valores o usamos cuantificadores. Por ejemplo, «para todo entero x, x + 2 > x» sí es una proposición verdadera.

4.3 Definiciones, lemas, teoremas y corolarios

Las demostraciones se construyen sobre un vocabulario preciso. Cada tipo de enunciado cumple un papel diferente.

Una definición no se demuestra: se adopta para usar el término de manera consistente. En cambio, un teorema requiere una prueba que derive su conclusión de información aceptada.

4.4 Hipótesis y conclusión

Muchas afirmaciones matemáticas tienen la forma «si P, entonces Q», escrita P → Q. P es la hipótesis o antecedente, y Q es la conclusión o consecuente.

La demostración debe partir de la hipótesis, no de lo que queremos probar. Este orden evita razonamientos circulares y obliga a indicar qué propiedades se usan en cada paso.

4.5 Implicación, recíproca y bicondicional

La implicación P → Q no significa necesariamente que Q → P. La afirmación Q → P se llama recíproca. Cuando ambas son verdaderas, escribimos P ↔ Q y decimos «P si y solo si Q».

En especificaciones de software, confundir una condición suficiente con una necesaria puede introducir errores. Por ejemplo, una contraseña larga puede ser una condición útil para seguridad, pero no garantiza por sí sola que sea segura.

4.6 Cuantificadores

Los cuantificadores indican para cuántos elementos vale una afirmación. El cuantificador universal ∀ se lee «para todo» y el existencial ∃ se lee «existe al menos un».

El orden de los cuantificadores es importante. «Para todo usuario existe una contraseña» no significa lo mismo que «existe una contraseña para todo usuario». La primera permite una contraseña distinta para cada persona; la segunda exige una única contraseña común.

4.7 Ejemplos no son demostraciones

Probar algunos casos puede ayudar a descubrir una conjetura, pero no establece una afirmación universal. Si queremos demostrar que una propiedad vale para todos los enteros, no podemos revisar uno por uno porque hay infinitos.

Por ejemplo, los primeros valores de n² + n son pares:

La demostración general es más corta y fuerte: n² + n = n(n + 1). Dos enteros consecutivos siempre incluyen uno par, así que el producto es par. La prueba no depende de revisar valores concretos.

4.8 Contraejemplos

Para refutar una afirmación universal basta encontrar un único caso válido en el que falle. Ese caso se llama contraejemplo. Es una herramienta muy eficiente para detectar conclusiones apresuradas.

function esPrimo(n) {
  if (n < 2) return false;

  for (let divisor = 2; divisor * divisor <= n; divisor++) {
    if (n % divisor === 0) return false;
  }

  return true;
}

console.log(`¿2 es primo? ${esPrimo(2)}`); // true
console.log(`¿2 es impar? ${2 % 2 !== 0}`); // false

Un contraejemplo debe respetar todas las condiciones de la afirmación. Si el enunciado habla de enteros positivos, un número negativo no sirve para refutarlo.

4.9 Estructura de una demostración

Una prueba clara permite a otra persona verificar cada paso. Aunque su forma varía según el método, suele seguir una estructura ordenada.

1. Indicar qué se quiere demostrar y cuáles son las hipótesis.
2. Usar definiciones con precisión.
3. Aplicar reglas lógicas o resultados ya establecidos.
4. Justificar los pasos que no son evidentes.
5. Conectar el resultado obtenido con la conclusión exacta.

Una demostración no debe ocultar el paso decisivo detrás de frases como «es evidente» o «se ve fácilmente». Si un paso es esencial para llegar a la conclusión, debe explicarse.

4.10 Técnicas principales

La técnica adecuada depende de la forma de la afirmación y de las propiedades disponibles. En los próximos temas estudiaremos cada método con mayor detalle.

4.11 Demostración directa: una vista previa

Una demostración directa comienza con la hipótesis y aplica definiciones hasta alcanzar la conclusión. Para demostrar que «la suma de dos enteros pares es par», tomamos dos enteros pares a y b.

La prueba funciona porque usa la definición de número par. En el tema siguiente desarrollaremos este método y aprenderemos a identificar el punto de partida correcto.

4.12 Demostración por contraposición

Las proposiciones P → Q y ¬Q → ¬P son lógicamente equivalentes. Por eso, para demostrar una implicación, a veces resulta más sencillo demostrar su contraposición.

No debemos confundir contraposición con recíproca. La recíproca intercambia P y Q; la contraposición niega ambas y cambia el orden.

4.13 Demostración por contradicción

En una demostración por contradicción suponemos que la afirmación que queremos demostrar es falsa. Si esa suposición conduce a una imposibilidad lógica, concluimos que la afirmación inicial debe ser verdadera.

Por ejemplo, para demostrar que no existe un entero mayor que todos los enteros, podríamos suponer que existe uno llamado M. Pero M + 1 también es un entero y es mayor que M, lo que contradice la suposición.

4.14 Inducción matemática

La inducción se utiliza para demostrar afirmaciones sobre todos los números naturales. Se parece a una fila infinita de fichas de dominó: debemos derribar la primera y demostrar que, si una cae, empuja a la siguiente.

Este método será especialmente importante para justificar recurrencias, bucles, estructuras recursivas y fórmulas que dependen del tamaño de una entrada.

4.15 Demostraciones y corrección de programas

Un programa puede especificarse mediante una precondición y una postcondición. La precondición describe qué debe ser cierto antes de ejecutar el algoritmo; la postcondición describe qué garantiza al terminar.

Para demostrar corrección de un ciclo se usa normalmente un invariante: una propiedad que es verdadera antes de empezar el ciclo, se conserva en cada iteración y permite concluir la postcondición al finalizar.

4.16 Ejemplo: comprobar una propiedad con código

El código puede explorar ejemplos y detectar errores, aunque no reemplaza una demostración general. La siguiente función verifica para varios valores que la suma de dos pares es par.

function esPar(n) {
  return n % 2 === 0;
}

function verificarSumaDePares(limite) {
  for (let a = 0; a <= limite; a += 2) {
    for (let b = 0; b <= limite; b += 2) {
      if (!esPar(a + b)) return false;
    }
  }

  return true;
}

console.log(verificarSumaDePares(20)); // true

El resultado respalda nuestra intuición para los casos revisados. La demostración directa de la sección 4.11 es la que establece la propiedad para todos los enteros pares, incluso los que el programa no evaluó.

4.17 Errores frecuentes al demostrar

• Usar ejemplos particulares como si demostraran una afirmación universal.
• Suponer la conclusión dentro de la prueba sin justificarla.
• Confundir la recíproca de una implicación con su contraposición.
• Omitir las condiciones de dominio, como que una variable sea entera o positiva.
• Usar una definición de manera imprecisa.
• Concluir más de lo que permiten las hipótesis.

4.18 Qué debes recordar de este tema

• Una demostración establece una afirmación mediante pasos lógicos válidos, no mediante ejemplos aislados.
• Las definiciones fijan significados; los teoremas y lemas deben demostrarse.
• Una implicación tiene hipótesis y conclusión; su recíproca no siempre es verdadera.
• Los cuantificadores indican si una afirmación vale para todos los elementos o si basta con alguno.
• Un contraejemplo basta para refutar una afirmación universal.
• Las técnicas principales son demostración directa, contraposición, contradicción, inducción y división en casos.
• Las pruebas de corrección de programas utilizan especificaciones e invariantes.

4.19 Conclusión

Demostrar es explicar con precisión por qué una conclusión se sigue de unas condiciones. Esta habilidad ayuda a leer especificaciones, diseñar algoritmos confiables y detectar errores de razonamiento antes de que se conviertan en errores de software.

En el próximo tema estudiaremos la demostración directa, el método más natural para derivar una conclusión a partir de una hipótesis.