Provas Formais como Caminhos
Um sistema de prova formal define um conjunto de axiomas & regras de inferência. Todo programa de comprovação de teoremas navega este sistema como um problema de busca: começando nas premissas dadas, aplicar regras de inferência para gerar novas afirmações, até atingir o objetivo.
Represente isto como um grafo direcionado:
Nós: afirmações bem-formadas no sistema formal.
Arestas: aplicações únicas 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ó de premissa & o nó de conclusão neste grafo.
O programa de comprovação de teoremas geométricos explorou este grafo por: (1) aplicação direta de regras; (2) se preso, introduzindo construções auxiliares (que adicionam novos nós à busca). O programa encontrou a prova de autocongruência evitando inteiramente a construção auxiliar — um caminho mais curto existia que a abordagem clássica não havia visto.
Comprimento de Prova & Busca de Prova
A busca de prova enfrenta o mesmo crescimento exponencial que a busca em árvore de jogo. O fator de ramificação em cada nó é igual ao número de regras de inferência aplicáveis. A profundidade de prova cresce com a complexidade do teorema.
O programa de comprovação de teoremas usou heurísticas para podar o espaço de prova, análogo à poda alfa-beta em jogos.
Pontos, Linhas & Dualidade
A prova de autocongruência do programa do teorema do triângulo isósceles usa uma perspectiva que não aparece em provas euclidianas clássicas. A intuição: em vez de comparar o triângulo ABC a um segundo triângulo construído, compare ABC a si mesmo com os vértices da 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 através da altitude do ápice. O programa não construiu a reflexão explicitamente; usou a correspondência como uma abstração.
O princípio geral por trás disto é dualidade projetiva: no plano projetivo, todo teorema sobre pontos & linhas tem um teorema dual obtido trocando as palavras 'ponto' e 'linha' em todo lugar.
Dicionário de dualidade:
- Ponto ↔ Linha
- Ponto está em linha ↔ Linha passa por ponto
- Dois pontos determinam uma linha única ↔ Duas linhas determinam um ponto único
- Pontos colineares ↔ Linhas concorrentes
Uma prova única de um teorema sobre pontos automaticamente produz uma prova do teorema dual sobre linhas — e vice-versa. As duas provas têm a mesma estrutura, o mesmo comprimento, & 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 estão em perspectiva a partir de um ponto (as três linhas através de vértices correspondentes se encontram em um ponto), então estão em perspectiva a partir de uma linha (as três intersecções de lados correspondentes todas estão em uma linha).
Este teorema é auto-dual: trocar pontos e linhas dá exatamente a mesma afirmação de teorema.
Taxa de Amostragem & Espaço de Frequência
O sistema de música de computador nos Bell Labs descansava em um teorema matemático: o teorema de amostragem Nyquist-Shannon.
Afirmação: um sinal com banda limitada com frequência máxima f_max pode ser perfeitamente reconstruído a partir de amostras coletadas a uma taxa de pelo menos 2 × f_max amostras por segundo.
A interpretação geométrica: um sinal com banda limitada vive em um subespaço de dimensão finita do espaço de todas as funções contínuas. Amostragem na taxa 2f_max fornece coordenadas suficientes para identificar unicamente um ponto naquele subespaço.
Aliasing: A Geometria da Falha de Amostragem
Abaixo da taxa Nyquist, frequências acima de f_max sofrem aliasing — elas aparecem como frequências mais baixas no sinal amostrado. Dois sinais distintos se tornam indistinguíveis após amostragem. Geometricamente: o operador de amostragem projeta o espaço de sinal em um espaço de menor dimensão, causando sinais diferentes colidirem.
Para áudio digital (qualidade CD): f_max = 22.050 Hz (ligeiramente acima do limite de audição humana de 20.000 Hz), taxa de amostragem = 44.100 amostras/segundo. Para telefone: f_max = 4.000 Hz, taxa de amostragem = 8.000 amostras/segundo.
Cálculos da Taxa Nyquist
O teorema Nyquist determina a taxa mínima de amostragem necessária para evitar perda de informação.
Espaço de Prova & Espaço de Sinal: Geometria Compartilhada
A prova-como-caminho & o teorema de amostragem Nyquist compartilham uma estrutura geométrica comum: ambos envolvem encontrar a representação mínima de algo complexo.
Minimização de prova: encontre o caminho mais curto (menos passos de inferência) através do grafo de prova das premissas para a conclusão. A prova de autocongruência minimizou o comprimento do caminho explorando simetria.
Amostragem de sinal: encontre o número mínimo de amostras (taxa de amostragem mais baixa) que preserva toda informação em um sinal com banda limitada. O teorema 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 aquela estrutura se quebra: provas ficam mais longas quando o espaço de axiomas é mal organizado; aliasing ocorre quando o sinal não tem banda limitada.