English· Español· Deutsch· Nederlands· Français· 日本語· ქართული· 繁體中文· 简体中文· Português· Русский· العربية· हिन्दी· Italiano· 한국어· Polski· Svenska· Türkçe· Українська· Tiếng Việt· Bahasa Indonesia

un

게스트
1 / ?
수업 목록으로

경로로서의 형식적 증명

형식적 증명 체계는 공리 모음 & 추론 규칙을 정의합니다. 모든 정리 증명 프로그램은 이 체계를 탐색 문제로 탐색합니다: 주어진 전제에서 시작하여 추론 규칙을 적용하여 새로운 명제를 생성하고, 목표에 도달할 때까지 계속합니다.

이를 방향 그래프로 나타내면:

노드: 형식 체계의 잘 형성된 명제.

간선: 추론 규칙의 단일 적용 (modus ponens, SAS 합동, 등).

증명: 주어진 전제에서 원하는 결론으로의 방향 경로.

증명 길이: 경로의 추론 단계 수.

정리의 가장 짧은 증명은 이 그래프에서 전제 노드 & 결론 노드 사이의 가장 짧은 경로에 해당합니다.

공리 공간의 경로로서의 증명

기하학 정리 증명 프로그램은 다음과 같이 이 그래프를 탐색했습니다: (1) 규칙의 직접 적용; (2) 막히면 보조 구성을 도입 (탐색에 새로운 노드 추가). 프로그램은 보조 구성을 완전히 피함으로써 자기합동 증명을 찾았습니다 — 고전적 접근이 놓친 더 짧은 경로가 존재했습니다.

증명 길이 & 증명 탐색

증명 탐색은 게임 트리 탐색과 동일한 지수 성장을 직면합니다. 각 노드에서의 분기 계수는 적용 가능한 추론 규칙의 수와 같습니다. 증명 깊이는 정리 복잡성에 따라 증가합니다.

정리 증명 프로그램은 게임의 알파-베타 가지치기와 유사한 증명 공간을 가지치기하기 위해 휴리스틱을 사용했습니다.

형식 기하학 체계가 각 단계마다 12개의 적용 가능한 추론 규칙을 가지고 있다고 가정하고 증명을 찾고 있습니다. 이등변삼각형 정리의 고전적 증명은 3 단계가 필요합니다 (주어짐 → 구성 → SAS → 결론). 프로그램의 증명은 2 단계가 필요합니다 (주어짐 → 자기합동 → 결론). 증명을 찾기 전에 탐색이 최악의 경우에 탐색해야 하는 각 길이의 경로 수를 계산하세요. 2단계 탐색 공간은 3단계 공간에 비해 얼마나 더 작습니까?

점, 직선 & 쌍대성

기하학 프로그램의 이등변삼각형 정리에 대한 자기합동 증명은 고전적 유클리드 증명에 나타나지 않는 관점을 사용합니다. 통찰력: 삼각형 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 샘플.

나이키스트 속도 계산

나이키스트 정리는 정보 손실을 피하기 위해 필요한 최소 샘플링 속도를 결정합니다.

음성인터넷 시스템은 8,000 Hz까지 음성을 재현해야 합니다. 필요한 최소 샘플링 속도는 무엇입니까? 그 다음: 이 샘플링 속도에서 16비트 샘플 (65,536 양자화 레벨)로 5분의 오디오를 저장하려면 몇 바이트가 필요합니까? 모든 계산을 표시하세요.

증명 공간 & 신호 공간: 공유된 기하학

경로로서의 증명과 나이키스트 샘플링 정리는 공통의 기하학적 구조를 공유합니다: 둘 다 복잡한 것의 최소 표현을 찾는 것을 포함합니다.

증명 최소화: 전제에서 결론까지의 증명 그래프를 통해 가장 짧은 경로 (가장 적은 추론 단계)를 찾습니다. 자기합동 증명은 대칭성을 이용하여 경로 길이를 최소화했습니다.

신호 샘플링: 대역제한 신호의 모든 정보를 보존하는 최소 샘플 수 (최저 샘플링 속도)를 찾습니다. 나이키스트 정리는 대역폭 제한을 이용하여 표현을 최소화합니다.

두 문제 모두 최소 표현 결과를 가능하게 하는 구조를 가진 공간에 있습니다. 그 구조가 무너질 때 둘 다 실패합니다: 공리 공간이 잘 조직되지 않을 때 증명이 더 길어집니다; 신호가 대역제한되지 않을 때 에일리어싱이 발생합니다.

증명 최소화와 신호 샘플링은 모두 최소 표현을 달성하기 위해 구조적 속성을 이용합니다. 증명의 경우 구조는 증명 그래프의 연결성입니다. 신호의 경우 구조는 대역제한성입니다. 기저 구조적 속성 때문에 최소 표현 결과가 존재하는 다른 도메인을 하나 식별하세요. 구조, 표현, 최소 결과가 무엇이라고 말하는지 이름을 지으세요.