Provas Formais como Caminhos
Um sistema de provas formais define um conjunto de axiomas e regras de inferência. Cada programa de demonstração de teoremas navega neste sistema como um problema de busca: começando nas premissas dadas, aplique as regras de inferência para gerar novas declarações, até chegar ao objetivo.
Represente isso como um gráfico direcionado:
Nós: declarações bem-formuladas no sistema formal.
Arestas: aplicações singulares de regras de inferência (modus ponens, congruência SAS, etc.).
Prova: um caminho direcionado das premissas dadas para a conclusão desejada.
Comprimento da prova: número de passos de inferência no caminho.
A prova mais curta de um teorema corresponde ao caminho mais curto entre o nó da premissa e o nó da conclusão neste gráfico.
O programa de provas geométricas explorou este gráfico por: (1) aplicação direta das regras; (2) se ficar preso, introduzir construções auxiliares (o que adiciona novos nós à busca). O programa encontrou a prova de autocongruência evitando completamente a construção auxiliar — um caminho mais curto existia que a abordagem clássica perdeu.
Comprimento da Prova e Busca de Prova
A busca de provas enfrenta o mesmo crescimento exponencial que a busca de árvores de jogo. O fator de ramificação em cada nó é igual ao número de regras de inferência aplicáveis. A profundidade da prova cresce com a complexidade do teorema.
O programa de provas geométricas usou heurísticas para podar o espaço de provas, semelhante à prúnia alfa-beta nos jogos.
Pontos, Linhas & Dualidade
A prova de autocongruência do programa de geometria da teoria do triângulo isósceles usa uma perspectiva que não aparece nas provas clássicas euclidianas. A insígnia: em vez de comparar o triângulo ABC com um segundo triângulo construído, compare ABC consigo mesmo com as vértices base trocados - a correspondência A↔A, B↔C, C↔B.
Esta é uma argumentação de simetria geométrica: o triângulo isósceles é simétrico sob reflexão sobre o altitude do ápice. O programa não construiu a reflexão explicitamente; usou a correspondência como uma abstração.
A princípio geral por trás disso é a dualidade projética: na placa projética, todo teorema sobre pontos e linhas tem um teorema dual obtido trocando as palavras 'ponto' e 'linha' em toda parte.
Dicionário de dualidade:
- Ponto ↔ Linha
- Ponto está em linha ↔ Linha passa por ponto
- Dois pontos determinam uma linha única ↔ Dois linhas determinam um ponto único
- Pontos colineares ↔ Linhas concorrentes
Uma única prova de um teorema sobre pontos automaticamente fornece uma prova do teorema dual sobre linhas - e vice-versa. As duas provas têm a mesma estrutura, a mesma extensão e os mesmos passos de inferência. Encontrar a perspectiva dual frequentemente revela uma prova mais simples do original.
Aplicando Dualidade
Teorema de Desargues: Se dois triângulos são em perspectiva de um ponto (as três linhas que passam por vértices correspondentes se encontram em um único ponto), então eles são em perspectiva de uma linha (as três interseções de lados correspondentes se encontram em uma única linha).
Este teorema é autodual: trocando pontos e linhas dá exatamente a mesma declaração do teorema.
Taxa de Amostragem & Espaço de Frequência
O sistema de música para computador nos Laboratórios Bell repousava em um teorema matemático: o teorema de amostragem de Nyquist-Shannon.
Declaração: uma sinalização limitada por banda com frequência máxima f_max pode ser reconstruída perfeitamente a partir de amostras coletadas em uma taxa de pelo menos 2 × f_max amostras por segundo.
A interpretação geométrica: uma sinalização limitada por banda vive em um subespaço de dimensão finita do espaço de todas as funções contínuas. Amostragem em uma taxa de 2f_max fornece suficientes coordenadas para identificar únicamente um ponto nesse subespaço.
Aliasing: A Geometria do Falha de Amostragem
Abaixo da taxa de Nyquist, frequências acima de f_max se repetem - aparecem como frequências mais baixas na sinal amostrado. Dois sinais distintos se tornam indistinguíveis após a amostragem. Geometricamente: o operador de amostragem projeta o espaço de sinais em um espaço de dimensão inferior, fazendo diferentes sinais colidir.
Para áudio digital (qualidade CD): f_max = 22.050 Hz (ligeiramente acima do limite de audição humano de 20.000 Hz), taxa de amostragem = 44.100 amostras por segundo. Para telefone: f_max = 4.000 Hz, taxa de amostragem = 8.000 amostras por segundo.
Cálculos da Taxa de Nyquist
O teorema de Nyquist determina a taxa de amostragem mínima necessária para evitar a perda de informação.
Prova do Espaço & Espaço de Sinal: Geometria Compartilhada
A prova como caminho e o teorema de amostragem de Nyquist compartilham uma estrutura geométrica comum: ambos envolvem encontrar a representação mínima de algo complexo.
Minimização de provas: encontre o caminho mais curto (menos passos de inferência) pelo gráfico de provas das premissas à conclusão. O caminho minimizado da prova de autocongruência reduziu a extensão explorando simetria.
Amostragem de sinal: encontre o número mínimo de amostras (taxa de amostragem mais baixa) que preserva toda a informação em um sinal limitado por banda. O teorema de Nyquist minimiza a representação explorando limites de banda.
Ambos os problemas vivem em espaços com estrutura que permite resultados de representação mínima. Ambos falham quando essa estrutura se rompe: provas ficam mais longas quando o espaço de axiomas está mal organizado; aliasing ocorre quando o sinal não é limitado por banda.