Demostraciones formales como caminos
Un sistema de demostraciones formales define un conjunto de axiomas e reglas de inferencia. Cada programa de demostración de teoremas navega por este sistema como un problema de búsqueda: comenzando en las premisas dadas, aplicar reglas de inferencia para generar nuevas declaraciones, hasta llegar al objetivo.
Represente esto como un gráfico dirigido:
Nodos: declaraciones bien formadas en el sistema formal.
Aristas: aplicaciones singulares de reglas de inferencia (modus ponens, congruencia SAS, etc.).
Demostración: un camino dirigido de las premisas dadas a la conclusión deseada.
Longitud de la demostración: número de pasos de inferencia en el camino.
La demostración más corta de un teorema corresponde al camino más corto entre el nodo de la premisa y el nodo de la conclusión en este gráfico.
El programa de demostración geométrica exploró este gráfico al: (1) aplicación directa de reglas; (2) si se quedaba atascado, introducir construcciones auxiliares (lo que agrega nuevos nodos al buscador). El programa encontró la demostración de autocongruencia evitando completamente la construcción auxiliar - un camino más corto existía que el enfoque clásico se perdió.
Longitud de la demostración y búsqueda de demostraciones
La búsqueda de demostraciones enfrenta el mismo crecimiento exponencial que la búsqueda de árboles de juego. El factor de ramificación en cada nodo es igual al número de reglas de inferencia aplicables. La profundidad de la demostración crece con la complejidad del teorema.
El programa de demostración de teoremas utilizó heurísticas para podar el espacio de demostraciones, similar a la poda alpha-beta en los juegos.
Puntos, Líneas & Dualidad
La prueba de autocongruencia del programa de geometría de la proposición del teorema de los triángulos isósceles utiliza una perspectiva que no aparece en las pruebas euclíneas clásicas. La intuición: en lugar de comparar el triángulo ABC con un segundo triángulo construido, compare ABC consigo mismo con los vértices de la base intercambiados — la correspondencia A↔A, B↔C, C↔B.
Este es un argumento de simetría geométrica: el triángulo isósceles es simétrico con respecto a la reflexión a lo largo de la altura desde la cúspide. El programa no construyó la reflexión explícitamente; utilizó la correspondencia como una abstracción.
La idea general detrás de esto es la dualidad proyectiva: en el plano proyectivo, cada teorema sobre puntos y líneas tiene un teorema dual obtenido al intercambiar las palabras 'punto' y 'línea' en todo el texto.
Diccionario de dualidad:
- Punto ↔ Línea
- Punto que pertenece a la línea ↔ Línea que pasa por el punto
- Dos puntos determinan una línea única ↔ Dos líneas determinan un punto único
- Puntos colineales ↔ Líneas concurrentes
Una sola prueba de un teorema sobre puntos automáticamente produce una prueba del teorema dual sobre líneas — y viceversa. Las dos pruebas tienen la misma estructura, la misma longitud y los mismos pasos de inferencia. Encontrar la perspectiva dual a menudo revela una prueba más simple del original.
Aplicando la Dualidad
Teorema de Desargues: Si dos triángulos están en perspectiva desde un punto (las tres líneas que pasan por vértices correspondientes se encuentran en un solo punto), entonces están en perspectiva desde una línea (los tres puntos de intersección de los lados correspondientes se encuentran en una sola línea).
Este teorema es autodual: intercambiar puntos y líneas da exactamente la misma declaración del teorema.
Tasa de Muestreo y Espacio de Frecuencias
El sistema de música para computadoras en Bell Labs se basaba en uno teorema matemático: el teorema de muestreo de Nyquist-Shannon.
Declaración: una señal limitada por banda con una frecuencia máxima f_max se puede reconstruir perfectamente a partir de muestras tomadas a una tasa de al menos 2 × f_max muestras por segundo.
La interpretación geométrica: una señal limitada por banda vive en un subespacio de dimensiones finitas del espacio de todas las funciones continuas. Muestrear a una tasa de 2f_max proporciona suficientes coordenadas para identificar de forma única un punto en ese subespacio.
Aliasing: La Geometría del Fallo del Muestreo
Por debajo de la tasa de Nyquist, las frecuencias por encima de f_max se aliasan - aparecen como frecuencias más bajas en la señal muestreada. Dos señales distintas se vuelven indistinguibles después de la muestreación. Geométricamente: el operador de muestreo proyecta el espacio de señales en un espacio de menor dimensión, causando que diferentes señales colisionen.
Para audio digital (calidad de CD): f_max = 22,050 Hz (ligeramente por encima del límite de audición humano de 20,000 Hz), tasa de muestreo = 44,100 muestras por segundo. Para teléfono: f_max = 4,000 Hz, tasa de muestreo = 8,000 muestras por segundo.
Cálculos de la tasa de Nyquist
El teorema de Nyquist determina la tasa de muestreo mínima necesaria para evitar la pérdida de información.
Demostración Espacio de Prueba y Espacio de Señal: Geometría Compartida
La prueba como camino y el teorema de muestreo de Nyquist comparten una estructura geométrica común: ambos implican encontrar la representación mínima de algo complejo.
Minimización de pruebas: encontrar el camino más corto (pocos pasos de inferencia) a través del gráfico de pruebas desde las premisas hasta la conclusión. El camino minimizado de la prueba de autocongruencia redujo la longitud al explotar la simetría.
Muestreo de señal: encontrar el número mínimo de muestras (tasa de muestreo más baja) que preserva toda la información en una señal limitada por ancho de banda. El teorema de Nyquist minimiza la representación al explotar los límites de ancho de banda.
Ambos problemas viven en espacios con estructura que permite resultados de representación mínima. Ambos fallan cuando esa estructura se rompe: las pruebas se vuelven más largas cuando el espacio de axiomas está mal organizado; la aliasing ocurre cuando la señal no está limitada por ancho de banda.