Формальные доказательства как пути
Система формального доказательства определяет набор аксиом и правил вывода. Каждая программа доказательства теорем навигирует в этой системе как задача поиска: начиная с данных посылок, применяйте правила вывода для генерирования новых утверждений, пока не достигнете цели.
Представьте это как ориентированный граф:
Узлы: корректно сформированные утверждения в формальной системе.
Дуги: одиночные применения правил вывода (модус поненс, SAS-конгруэнтность и т.д.).
Доказательство: ориентированный путь от данных посылок к желаемому выводу.
Длина доказательства: количество шагов вывода в пути.
Кратчайшее доказательство теоремы соответствует кратчайшему пути между узлом посылки и узлом выводов в этом графе.
Программа доказательства геометрических теорем исследовала этот граф: (1) прямым применением правил; (2) если застряла, введением вспомогательных конструкций (которые добавляют новые узлы в поиск). Программа нашла доказательство самоконгруэнтности, полностью избежав вспомогательной конструкции — существовал более короткий путь, который классический подход пропустил.
Длина доказательства и поиск доказательства
Поиск доказательства сталкивается с тем же экспоненциальным ростом, что и поиск в дереве игры. Коэффициент ветвления в каждом узле равен количеству применимых правил вывода. Глубина доказательства растет со сложностью теоремы.
Программа доказательства теорем использовала эвристики для обрезки пространства доказательства, аналогично альфа-бета отсечению в играх.
Точки, линии и двойственность
Доказательство самоконгруэнтности теоремы о равнобедренном треугольнике, полученное программой геометрии, использует перспективу, которая не появляется в классических евклидовых доказательствах. Ключевая идея: вместо сравнения треугольника ABC со вторым сконструированным треугольником, сравните ABC с самим собой, поменяв местами вершины основания — соответствие A↔A, B↔C, C↔B.
Это аргумент геометрической симметрии: равнобедренный треугольник симметричен относительно отражения через высоту, проведённую из вершины. Программа не конструировала отражение явно; она использовала соответствие как абстракцию.
Общий принцип за этим — проективная двойственность: в проективной плоскости каждая теорема о точках и линиях имеет двойственную теорему, полученную заменой слов 'точка' и 'линия' везде.
Словарь двойственности:
- Точка ↔ Линия
- Точка лежит на линии ↔ Линия проходит через точку
- Две точки определяют уникальную линию ↔ Две линии определяют уникальную точку
- Коллинеарные точки ↔ Конкурентные линии
Одно доказательство теоремы о точках автоматически даёт доказательство двойственной теоремы о линиях — и наоборот. Оба доказательства имеют одинаковую структуру, одинаковую длину и одинаковые шаги вывода. Нахождение двойственной перспективы часто раскрывает более простое доказательство оригинальной теоремы.
Применение двойственности
Теорема Дезарга: Если два треугольника находятся в перспективе из точки (три линии, проходящие через соответствующие вершины, все пересекаются в одной точке), то они находятся в перспективе из линии (три пересечения соответствующих сторон все лежат на одной линии).
Эта теорема самодвойственна: замена точек и линий даёт ровно то же утверждение теоремы.
Частота дискретизации и пространство частот
Компьютерная система музыки в Bell Labs была основана на одной математической теореме: теорема дискретизации Найквиста-Шеннона.
Утверждение: сигнал с ограниченной полосой пропускания с максимальной частотой f_max может быть идеально восстановлен из выборок, взятых с частотой не менее 2 × f_max выборок в секунду.
Геометрическое толкование: сигнал с ограниченной полосой пропускания живёт в конечномерном подпространстве пространства всех непрерывных функций. Дискретизация с частотой 2f_max обеспечивает достаточно координат для уникальной идентификации точки в этом подпространстве.
Наложение спектров: геометрия отказа дискретизации
Ниже частоты Найквиста, частоты выше f_max создают наложение спектров — они появляются как более низкие частоты в дискретизированном сигнале. Два различных сигнала становятся неразличимыми после дискретизации. Геометрически: оператор дискретизации проектирует пространство сигналов в пространство меньшей размерности, вызывая столкновение различных сигналов.
Для цифрового аудио (качество компакт-диска): f_max = 22 050 Гц (немного выше предела слуха человека 20 000 Гц), частота дискретизации = 44 100 выборок/секунду. Для телефонии: f_max = 4 000 Гц, частота дискретизации = 8 000 выборок/секунду.
Расчёты частоты Найквиста
Теорема Найквиста определяет минимальную частоту дискретизации, необходимую для предотвращения потери информации.
Пространство доказательств и пространство сигналов: общая геометрия
Доказательство как путь и теорема дискретизации Найквиста имеют общую геометрическую структуру: оба включают поиск минимального представления чего-то сложного.
Минимизация доказательства: найти кратчайший путь (наименьшее количество шагов вывода) через граф доказательства от посылок к выводу. Доказательство самоконгруэнтности минимизировало длину пути, используя симметрию.
Дискретизация сигнала: найти минимальное количество выборок (самую низкую частоту дискретизации), которое сохраняет всю информацию в сигнале с ограниченной полосой пропускания. Теорема Найквиста минимизирует представление, используя ограничения полосы пропускания.
Обе задачи живут в пространствах со структурой, которая позволяет получить результаты минимального представления. Обе терпят неудачу, когда эта структура нарушается: доказательства становятся длиннее, когда пространство аксиом плохо организовано; наложение спектров возникает, когда сигнал не имеет ограниченной полосы пропускания.