Формальні докази як шляхи
Формальна система доказів визначає набір аксіом та правил висновування. Кожна програма доведення теорем навігує цією системою як задачею пошуку: починаючи з даних передумов, застосовуйте правила висновування для генерування нових тверджень, поки не досягнете мети.
Представте це як спрямований граф:
Вузли: добре сформовані твердження у формальній системі.
Ребра: окремі застосування правил висновування (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 Гц (трохи вище межі людського слуху 20,000 Гц), частота дискретизації = 44,100 зразків/секунду. Для телефону: f_max = 4,000 Гц, частота дискретизації = 8,000 зразків/секунду.
Розрахунки частоти Найквіста
Теорема Найквіста визначає мінімальну частоту дискретизації, необхідну для запобігання втраті інформації.
Простір доказів та простір сигналів: спільна геометрія
Доказ-як-шлях та теорема дискретизації Найквіста мають спільну геометричну структуру: обидва включають знаходження мінімального представлення чогось складного.
Мінімізація доказу: знайдіть найкоротший шлях (найменше кроків висновування) через граф доказів від передумов до висновку. Доказ самоконгруентності мінімізував довжину шляху, використовуючи симетрію.
Дискретизація сигналу: знайдіть мінімальну кількість зразків (найнижчу частоту дискретизації), що зберігає всю інформацію в сигналі з обмеженою смугою частот. Теорема Найквіста мінімізує представлення, використовуючи обмеження пропускної здатності.
Обидві задачі живуть у просторах зі структурою, яка дозволяє результати мінімального представлення. Обидві не вдаються, коли ця структура розпадається: докази стають довшими, коли простір аксіом погано організований; накладання частот відбувається, коли сигнал не має обмеженої смуги частот.