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