조건부 증명
Conditional proof| 변환 규칙 |
|---|
| 명제 미적분학 |
| 추론 규칙 |
| 교체규칙 |
| 술어 논리학 |
| 추론 규칙 |
 |
조건부 증명이란 조건부 주장을 하는 형식을 취하고, 조건부의 선행은 필연적으로 결과로 이어진다는 것을 증명하는 증거다.
개요
조건부 입증의 전제조건을 조건부 증명 가정(CPA)이라고 한다. 따라서, 조건부 증명의 목적은 CPA가 사실이라면, 원하는 결론이 반드시 뒤따른다는 것을 입증하는 것이다. 조건부 증명의 타당성은 CPA가 사실일 것을 요구하지 않는다. 다만 그것이 사실이라면 결과가 나올 것이다.
조건부 증거는 수학에서 매우 중요하다. 조건부 증거는 입증되지 않은 몇 가지 추측을 연관시켜 존재하기 때문에 하나의 추측에 대한 증거가 다른 여러 가지 추측의 타당성을 즉시 암시할 수 있다. 독립적으로 증명하는 것보다 다른 명제에서 따르는 명제의 진리를 보여주는 것이 훨씬 더 쉬울 수 있다.
조건부 입증의 유명한 네트워크는 복잡성 이론의 NP-완전 등급이다. 흥미로운 과업(NP-완전 문제 목록 참조)이 많고, 이들 중 하나에 대해 다항식 해결책이 존재하는지 여부는 알 수 없지만, 일부에 대해 그러한 해결책이 존재한다면 그 해결책이 모두 존재한다고 알려져 있다. 이와 유사하게, 리만 가설은 이미 입증된 많은 결과를 가지고 있다.
상징논리학
상징논리의 조건부 증명의 예로서, 아래의 처음 두 전제로부터 A → C (A, 그 다음 C)를 증명하고 싶다고 가정해 보자.
| 1. | A → B | ("A이면 B") |
| 2. | B → C | ("B이면 C") |
| 3. | A | (조건부 입증 가정, "공급 A가 참") |
| 4. | B | (1호선과 3호선에서 이어지는 모드스 폰; "만약 A가 B, 따라서 B") |
| 5. | C | (2행과 4행에서 따라, 모드스 폰; "만약 B가 C, 따라서 C") |
| 6. | A → C | (3~5행, 조건부 증빙; "A이면 C") |
참고 항목
참조
- Robert L. Causey, Logic, set, and recurration, Jones and Barlett, 2006.
- Dov M. Gabbay, Franz Guenthner (edds), 철학적 논리 핸드북, 제8권, Springer, 2002.
