경로로서의 형식적 증명
형식적 증명 체계는 공리 모음 & 추론 규칙을 정의합니다. 모든 정리 증명 프로그램은 이 체계를 탐색 문제로 탐색합니다: 주어진 전제에서 시작하여 추론 규칙을 적용하여 새로운 명제를 생성하고, 목표에 도달할 때까지 계속합니다.
이를 방향 그래프로 나타내면:
노드: 형식 체계의 잘 형성된 명제.
간선: 추론 규칙의 단일 적용 (modus ponens, SAS 합동, 등).
증명: 주어진 전제에서 원하는 결론으로의 방향 경로.
증명 길이: 경로의 추론 단계 수.
정리의 가장 짧은 증명은 이 그래프에서 전제 노드 & 결론 노드 사이의 가장 짧은 경로에 해당합니다.
기하학 정리 증명 프로그램은 다음과 같이 이 그래프를 탐색했습니다: (1) 규칙의 직접 적용; (2) 막히면 보조 구성을 도입 (탐색에 새로운 노드 추가). 프로그램은 보조 구성을 완전히 피함으로써 자기합동 증명을 찾았습니다 — 고전적 접근이 놓친 더 짧은 경로가 존재했습니다.
증명 길이 & 증명 탐색
증명 탐색은 게임 트리 탐색과 동일한 지수 성장을 직면합니다. 각 노드에서의 분기 계수는 적용 가능한 추론 규칙의 수와 같습니다. 증명 깊이는 정리 복잡성에 따라 증가합니다.
정리 증명 프로그램은 게임의 알파-베타 가지치기와 유사한 증명 공간을 가지치기하기 위해 휴리스틱을 사용했습니다.
점, 직선 & 쌍대성
기하학 프로그램의 이등변삼각형 정리에 대한 자기합동 증명은 고전적 유클리드 증명에 나타나지 않는 관점을 사용합니다. 통찰력: 삼각형 ABC를 두 번째로 구성된 삼각형과 비교하는 대신 ABC를 밑변 꼭짓점이 바뀐 자신과 비교합니다 — 대응 A↔A, B↔C, C↔B.
이것은 기하학적 대칭 논증입니다: 이등변삼각형은 꼭짓점으로부터의 높이를 기준으로 한 반사에 대해 대칭입니다. 프로그램은 반사를 명시적으로 구성하지 않았습니다; 대응을 추상화로 사용했습니다.
이것 뒤의 일반 원리는 사영 쌍대성입니다: 사영 평면에서 점 & 직선에 대한 모든 정리는 '점'과 '직선'이라는 단어를 전체적으로 바꿈으로써 얻어진 쌍대 정리를 가집니다.
쌍대성 사전:
- 점 ↔ 직선
- 점이 직선 위에 있음 ↔ 직선이 점을 통과함
- 두 점은 유일한 직선을 결정함 ↔ 두 직선은 유일한 점을 결정함
- 일직선상의 점들 ↔ 한 점에서 만나는 직선들
점에 관한 정리의 단일 증명은 자동으로 직선에 관한 쌍대 정리의 증명을 산출합니다 — 그리고 그 반대도 마찬가지입니다. 두 증명은 동일한 구조, 동일한 길이, & 동일한 추론 단계를 가집니다. 쌍대 관점을 찾는 것은 종종 원래 것의 더 간단한 증명을 드러냅니다.
쌍대성 적용
데자르그 정리: 두 삼각형이 한 점에서 관점을 이루면 (대응 꼭짓점을 통과하는 세 직선이 모두 한 점에서 만남), 그들은 한 직선에서 관점을 이룹니다 (대응 변의 세 교점이 모두 한 직선 위에 있음).
이 정리는 자기 쌍대입니다: 점과 직선을 바꾸면 정확히 같은 정리 명제를 얻습니다.
샘플링 속도 & 주파수 공간
벨 연구소의 컴퓨터 음악 시스템은 하나의 수학 정리 위에 세워졌습니다: 나이키스트-섀넌 샘플링 정리.
명제: 최대 주파수 f_max를 가진 대역제한 신호는 최소 초당 2 × f_max 샘플의 속도로 취한 샘플에서 완벽하게 재구성될 수 있습니다.
기하학적 해석: 대역제한 신호는 모든 연속 함수 공간의 유한 차원 부분공간에 있습니다. 2f_max 속도로 샘플링하면 그 부분공간의 점을 유일하게 식별할 수 있는 충분한 좌표를 제공합니다.
에일리어싱: 샘플링 실패의 기하학
나이키스트 속도 이하에서, f_max 위의 주파수는 에일리어스됩니다 — 샘플링된 신호에서 더 낮은 주파수로 나타납니다. 두 개의 서로 다른 신호는 샘플링 후 구분 불가능해집니다. 기하학적으로: 샘플링 연산자는 신호 공간을 더 낮은 차원의 공간으로 투영하여 서로 다른 신호가 충돌하게 합니다.
디지털 오디오 (CD 품질)의 경우: f_max = 22,050 Hz (인간 청각 한계 20,000 Hz보다 약간 높음), 샘플링 속도 = 초당 44,100 샘플. 전화의 경우: f_max = 4,000 Hz, 샘플링 속도 = 초당 8,000 샘플.
나이키스트 속도 계산
나이키스트 정리는 정보 손실을 피하기 위해 필요한 최소 샘플링 속도를 결정합니다.
증명 공간 & 신호 공간: 공유된 기하학
경로로서의 증명과 나이키스트 샘플링 정리는 공통의 기하학적 구조를 공유합니다: 둘 다 복잡한 것의 최소 표현을 찾는 것을 포함합니다.
증명 최소화: 전제에서 결론까지의 증명 그래프를 통해 가장 짧은 경로 (가장 적은 추론 단계)를 찾습니다. 자기합동 증명은 대칭성을 이용하여 경로 길이를 최소화했습니다.
신호 샘플링: 대역제한 신호의 모든 정보를 보존하는 최소 샘플 수 (최저 샘플링 속도)를 찾습니다. 나이키스트 정리는 대역폭 제한을 이용하여 표현을 최소화합니다.
두 문제 모두 최소 표현 결과를 가능하게 하는 구조를 가진 공간에 있습니다. 그 구조가 무너질 때 둘 다 실패합니다: 공리 공간이 잘 조직되지 않을 때 증명이 더 길어집니다; 신호가 대역제한되지 않을 때 에일리어싱이 발생합니다.