Matemáticas Discretas · Matemáticas

Técnicas de demostración

Construye demostraciones por método directo, por contrarrecíproco, por contradicción y por inducción matemática.

Técnicas de demostración

Diagrama de matematicas discretas: grafo con nodos conectados, puertas logicas y diagramas de Venn.
Temas centrales de matematicas discretas: logica, conjuntos, grafos y conteo.

Mapa conceptual



Por qué demostrar Mil ejemplos que cumplen una propiedad no la demuestran; un solo contraejemplo la destruye. Una demostración es un argumento que garantiza la verdad para TODOS los casos. Es justo lo que un algoritmo necesita: no «funciona a menudo», sino «funciona siempre».


1) Método directo


Supones la hipótesis y, encadenando definiciones y resultados previos, llegas a la conclusión. Ejemplo: «la suma de dos enteros pares es par». Sean 2m y 2n; su suma es 2m + 2n = 2(m + n), que es 2 por un entero, o sea par. Fin (QED).


2) Contrarrecíproco


Para probar «si P entonces Q», es equivalente probar «si no Q entonces no P». Cuando negar Q te da más información útil que asumir P, este método brilla. Ejemplo: «si n² es par, entonces n es par». Contrarrecíproco: «si n es impar, n² es impar», que es fácil de verificar.


3) Reducción al absurdo (contradicción)


Supones la negación de lo que quieres probar y derivas una contradicción lógica. El clásico: √2 es irracional. Supón que es a/b irreducible; acabas concluyendo que a y b son ambos pares, contradicciendo que fuera irreducible. Luego la suposición era falsa.


4) Inducción matemática


Para probar una propiedad P(n) para todo entero n ≥ 1, dos pasos: (base) P(1) es cierta, y (paso inductivo) si P(k) es cierta entonces P(k+1) lo es. Como fichas de dominó: tiras la primera, y cada ficha tira a la siguiente.


La inducción como dominó
  1.  — Base
  2.  — Hipótesis inductiva
  3.  — Paso inductivo
  4.  — Conclusión


Nunca faltes la base El error mortal de la inducción es olvidar el paso base: sin la primera ficha, el domino nunca empieza aunque cada ficha sí empuje a la siguiente. Una hipótesis inductiva sin base demuestra cualquier absurdo.


En una demostración por inducción de «1 + 2 + … + n = n(n+1)/2», el paso inductivo consiste en…


Comprobar una proposición para cien valores concretos constituye una demostración.


Une cada técnica con la pista que la hace elegirla.


Errores en demostraciones



Ejemplo resuelto por inducción


  1. Prueba que 1 + 2 + … + n = n(n+1)/2 para todo n ≥ 1.
  2. Base: n = 1. Izquierda = 1; derecha = 1·2/2 = 1. ✓
  3. Hipótesis inductiva: supuesto para k: 1 + … + k = k(k+1)/2.
  4. Paso: 1 + … + k + (k+1) = k(k+1)/2 + (k+1).
  5. Factoriza (k+1): (k+1)(k/2 + 1) = (k+1)(k+2)/2, que es la fórmula para k+1. ✓


¿Por qué le importa esto a un científico de datos? La corrección de algoritmos recursivos y iterativos se prueba por inducción: la «invariante de bucle» es literalmente una hipótesis inductiva. Y la complejidad de un algoritmo divide-y-vencerás (merge sort) se resuelve con recurrencias que se verifican por inducción.


El arsenal de demostrar
directo
de hipótesis a conclusión
contrarrecíproco
prueba ¬Q ⟹ ¬P
contradicción
supón ¬P y cae un absurdo
inducción
base + paso k→k+1
paso base
la primera ficha del dominó
contraejemplo
refuta un «todo»
QED
quedó demostrada


Técnicas de demostración (repaso formal)
Métodos directo, indirecto e inducción con ejemplos detallados.




Elige la propiedad «2 + 4 + 6 + … + 2n = n(n + 1)» y demuéstrala completa por inducción: escribe explícitamente el paso base, la hipótesis inductiva y el paso inductivo. Señala en qué línea usaste la hipótesis.


MIT OCW 6.042J
Matematicas para Ciencias de la Computacion (MIT OpenCourseWare).