Bản chứng Hình thức như Con đường
Một hệ thống bản chứng hình thức định nghĩa một tập các tiên đề và quy tắc suy luận. Mỗi chương trình chứng minh bài toán phải lướt qua hệ thống này như một vấn đề tìm kiếm: bắt đầu từ các tiền đề đã cho, áp dụng quy tắc suy luận để tạo ra các tuyên bố mới, cho đến khi đạt được kết quả.
Đại diện như một đồ thị có hướng:
Đỉnh: các tuyên bố hợp lệ trong hệ thống hình thức.
Kết: một ứng dụng đơn của quy tắc suy luận (modus ponens, SAS tương đồng, v.v.).
Bản chứng: một con đường có hướng từ các tiền đề đã cho đến kết quả mong muốn.
Độ dài bản chứng: số bước suy luận trong con đường.
Bản chứng ngắn nhất của một bài toán tương ứng với con đường ngắn nhất giữa đỉnh tiền đề và đỉnh kết quả trong đồ thị này.
Chương trình chứng minh hình học đã khám phá đồ thị này thông qua: (1) áp dụng trực tiếp các quy tắc; (2) nếu bị mắc kẹt, giới thiệu các công trình phụ trợ (điều này thêm các đỉnh mới vào tìm kiếm). Chương trình đã tìm thấy bản chứng tự tương đồng bằng cách tránh việc giới thiệu công trình phụ trợ - một con đường ngắn hơn đã được bỏ qua bởi phương pháp cổ điển.
Độ dài Bản chứng & Tìm kiếm Bản chứng
Tìm kiếm bản chứng phải đối mặt với sự tăng trưởng theo cấp số nhân giống như tìm kiếm cây trò chơi. Bánh xe lăn tại mỗi nút bằng số lượng quy tắc suy luận có thể áp dụng. Độ sâu bản chứng tăng với độ phức tạp của bài toán.
Chương trình chứng minh hình học đã sử dụng heuristics để loại bỏ không gian bản chứng, tương tự như alpha-beta pruning trong trò chơi.
Điểm, Đường & Duality
Cái nhìn của chứng minh tự tương đồng hình học chương trình về định lý tam giác đều sử dụng một quan điểm không xuất hiện trong các chứng minh Euclidean cổ điển. Nhận thức: thay vì so sánh tam giác ABC với một tam giác khác được xây dựng, hãy so sánh ABC với chính nó với hai đầu cơ sở được đảo ngược — sự tương ứng A↔A, B↔C, C↔B.
Này là một argument đối xứng hình học: tam giác đều là đối xứng dưới ánh xạ phản chiếu từ đỉnh cao nhất. Chương trình không xây dựng ánh xạ phản chiếu trực tiếp; nó sử dụng sự tương ứng như một trừu tượng.
Sự nguyên tắc chung đằng sau điều này là duality projective: trong mặt phẳng projective, mọi định lý về điểm & đường có một định lý đối xứng được lấy ra bằng cách thay thế từ 'điểm' thành 'đường' khắp mọi nơi.
Từ điển duality:
- Điểm ↔ Đường
- Điểm nằm trên đường ↔ Đường đi qua điểm
- Hai điểm xác định một đường duy nhất ↔ Hai đường xác định một điểm duy nhất
- Điểm thẳng hàng ↔ Đường song song
Một chứng minh duy nhất của một định lý về điểm tự động tạo ra một chứng minh của định lý đối xứng về đường - và ngược lại. Hai chứng minh có cùng cấu trúc, cùng độ dài và cùng các bước suy luận. Việc tìm hiểu quan điểm đối xứng thường tiết lộ một chứng minh đơn giản hơn của định lý gốc.
Áp dụng Duality
Định lý Desargues: Nếu hai tam giác nằm ở vị trí tương quan từ một điểm (các đường thẳng qua các đỉnh tương ứng đều hội tụ tại một điểm), thì chúng nằm ở vị trí tương quan từ một đường (các giao điểm của các cạnh tương ứng đều nằm trên một đường thẳng).
Định lý này là tự đối xứng: thay thế điểm và đường thẳng sẽ cho ta cùng một tuyên bố của định lý.
Tỷ lệ lấy mẫu & Không gian tần số
Hệ thống âm nhạc máy tính tại Bell Labs dựa trên một định lý toán học: định lý lấy mẫu Nyquist-Shannon.
Tuyên bố: một tín hiệu có giới hạn tần số f_max có thể được tái tạo hoàn hảo từ các mẫu lấy tại một tỷ lệ là ít nhất 2 × f_max mẫu mỗi giây.
Giải thích hình học: một tín hiệu có giới hạn tần số sống trong một không gian có chiều hữu hạn của không gian của tất cả các hàm liên tục. Lấy mẫu với tỷ lệ 2f_max cung cấp đủ tọa độ để xác định duy nhất một điểm trong không gian đó.
Giả tạo: Hình học của sự thất bại trong lấy mẫu
Dưới băng thông Nyquist, tần số trên f_max giả tạo - chúng xuất hiện dưới dạng tần số thấp hơn trong tín hiệu lấy mẫu. Hai tín hiệu khác biệt không thể phân biệt sau khi lấy mẫu. Hình học: operator lấy mẫu chiếu không gian tín hiệu vào không gian thấp hơn, làm cho các tín hiệu khác nhau va chạm.
Về âm thanh kỹ thuật số (chất lượng CD): f_max = 22,050 Hz (rất gần giới hạn nghe của con người là 20,000 Hz), tốc độ lấy mẫu = 44,100 mẫu/giây. Đối với điện thoại: f_max = 4,000 Hz, tốc độ lấy mẫu = 8,000 mẫu/giây.
Tính toán Tần số Nyquist
Thệ thức Nyquist quyết định tần số lấy mẫu tối thiểu cần tránh mất thông tin.
Bằng chứng Không gian & Không gian Tín hiệu: Hình học Chia sẻ
Đồ thị chứng minh và định lý lấy mẫu Nyquist chia sẻ một cấu trúc hình học chung: cả hai đều liên quan đến việc tìm biểu diễn tối thiểu của điều phức tạp.
Giảm thiểu chứng minh: tìm đường ngắn nhất (số bước suy luận ít nhất) qua đồ thị chứng minh từ tiền đề đến kết luận. Đồ thị chứng minh tự tương phản giảm thiểu bước đường bằng cách khai thác tính đối xứng.
Nhân mẫu tín hiệu: tìm số mẫu tối thiểu (tần số lấy mẫu thấp nhất) mà vẫn giữ tất cả thông tin trong một tín hiệu có dải tần giới hạn. Nguyên lý Nyquist giảm thiểu biểu diễn bằng cách khai thác giới hạn dải tần.
Cả hai vấn đề đều tồn tại trong không gian có cấu trúc cho phép kết quả giảm thiểu biểu diễn. Cả hai đều thất bại khi cấu trúc đó bị phá vỡ: chứng minh dài hơn khi không gian tiên đề không được tổ chức tốt; nhiễu xạ xảy ra khi tín hiệu không có dải tần giới hạn.