소모에 의한 증명

Proof by exhaustion
이 기사는 수학적 증명의 종류에 관한 것이다.한계를 계산하는 방법은 소모 방법을 참조하십시오.
"Brute force method"는 여기서 리다이렉트됩니다.다른 분야에서도 유사한 이름의 방법은 Brute force(동음이의)를 참조하십시오.
"사례별 증명"은 여기서 리다이렉트됩니다.명제 논리의 개념은 분리 제거를 참조하십시오.

소진에 의한 증명, 사례별 증명, 사례별 증명, 완전 유도 또는 폭력적 방법이라고도 하는 수학적인 증명 방법으로서, 증명될 진술이 한정된 수의 사례 또는 동등한 사례 집합으로 분할되고, 각 유형의 사례를 [1]확인하여 문제가 되는 명제가 유지되는지 여부를 확인하는 것이다.이것은 직접적인 증거 방법이다.소모에 의한 증명은 일반적으로 다음 두 단계로 구성됩니다.

  1. 일련의 케이스가 완전하다는 증거, 즉 증명해야 할 진술의 각 인스턴스가 (적어도) 케이스 중 하나의 조건과 일치한다는 증거.
  2. 각 사건의 증거입니다.

디지털 컴퓨터의 보급으로 소모 방법의 사용 편의성이 크게 향상되었습니다(예: 1976년 4색 정리에 대한 최초의 컴퓨터 지원 증명). 그러나 이러한 접근법은 수학적 우아함에 기반하여도 도전할 수 있습니다.전문가 시스템을 사용하여 자신에게 제기된 많은 질문에 대한 답을 얻을 수 있습니다.이론적으로 소진법에 의한 증명은 케이스 수가 유한할 때마다 사용할 수 있다.그러나 대부분의 수학 집합은 무한하기 때문에 이 방법은 일반적인 수학 [2]결과를 도출하는 데 거의 사용되지 않습니다.

Curry-Howard 동형사상에서는 소모에 의한 증명과 사례 분석은 ML 스타일의 패턴 [citation needed]매칭과 관련이 있습니다.

예

완전 입방체일 경우 정수는 9의 배수, 9의 배수보다 1 많거나 [3]9의 배수보다 1 작아야 한다는 것을 증명하기 위해 소진 증명을 사용할 수 있습니다.

실증:
각 완전 입방체는 일부 정수 n의 세제곱입니다. 여기서 n은 3의 배수, 3의 배수보다 1 많거나 3의 배수보다 1 작습니다.이 세 가지 케이스는 모두 다음과 같습니다.

  • 사례 1: n = 3p이면 n3 = 27p로3 9의 배수입니다.
  • 사례 2: n = 3p + 1이면 n3 = 27p3 + 27p2 + 9p + 1로, 9의 배수보다 1 많다.예를 들어, n = 4이면 n3 = 64 = 9×7 + 1이다.
  • 사례 3: n = 3p - 1이면 n3 = 27p3 - 27p2 + 9p - 1로, 이는 9의 배수보다 1 적다.예를 들어, n = 5이면3 n = 125 = 9×14 - 1. Q.E.D.

우아함

수학자들은 고상하지 않은 것으로 여겨지는 많은 사례들로 인해 지쳐서 증명되는 것을 피하는 것을 선호한다.이러한 증거들이 얼마나 고상하지 않은지에 대한 예시는 모든 현대 하계 올림픽이 4로 나눌 수 있는 해에 개최된다는 다음 증거들을 살펴보는 것이다.

증명: 제1회 근대 하계 올림픽은 1896년에 개최되었고, 그 후 4년마다 개최되었다(제1차 세계 대전과 제2차 세계 대전으로 인해 개최되지 않은 2020년 도쿄 올림픽은 COVID-19 대유행으로 인해 2021년으로 연기되었다).1896 = 474 × 4는 4로 나누어지기 때문에, 다음 올림픽은 474 × 4 = (474 + 1) × 4가 될 것이다(이것은 수학 귀납에 의한 증명이다).따라서 그 진술은 증명되었다.

하계 올림픽이 열린 매년 목록을 작성하고, 각각을 4로 나눌 수 있는지 확인함으로써, 그 진술은 또한 지치는 것으로도 입증될 수 있다.2016년 하계올림픽 총 28건, 28건으로 지친 증거다.

기품이 떨어지는 것 외에도, 탈진 증명은 새로운 하계 올림픽이 열릴 때마다 여분의 케이스가 필요할 것이다.이것은 미래로 무한히 그 진술을 증명하는 수학적 귀납에 의한 증명과 대조되어야 한다.

건수

기진맥진하여 증빙할 수 있는 건수에는 상한이 없습니다.경우에 따라서는 두세 가지 경우가 있습니다.때로는 수천, 심지어 수백만 명이 있을 수도 있다.예를 들어, 체스 게임 퍼즐을 엄격하게 푸는 것은 그 문제의 게임 트리에서 매우 많은 가능한 위치를 고려하는 것을 포함할 수 있다.

사색정리의 첫 번째 증명은 1834건의 [4]경우에 의한 소진 증명이었다.이 증거는 대부분의 사건들이 수작업이 아닌 컴퓨터 프로그램으로 확인되었기 때문에 논란이 되었다.오늘날 4색 정리의 가장 짧은 증명은 여전히 600개 이상의 경우를 가지고 있다.

일반적으로 전체 증명에서 오류가 발생할 확률은 사례의 수에 따라 증가합니다.사례가 많은 증명은 그 정리가 단지 우연에 의해 참일 뿐, 어떤 근본적인 원리나 연관성 때문이 아니라는 인상을 남긴다.유도에 의한 증명(수학 귀납)과 같은 다른 유형의 증명은 더 우아한 것으로 간주된다.그러나, 다음과 같은 다른 증명 방법이 발견되지 않은 몇 가지 중요한 이론이 있다.

「 」를 참조해 주세요.

메모들

  1. ^ 를 클릭합니다Reid, D. A; Knipping, C (2010), Proof in Mathematics Education: Research, Learning, and Teaching, Sense Publishers, p. 133, ISBN 978-9460912443.
  2. ^ S., Epp, Susanna (2011-01-01). Discrete mathematics with applications. Brooks/Cole. ISBN 978-0495391326. OCLC 970542319.
  3. ^ Glaister, Elizabeth; Glaister, Paul (September 2017). "Mathematical argument, language and proof — AS/A Level 2017" (PDF). Mathematical Association. Retrieved October 25, 2019.
  4. ^ Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), "Every Planar Map is Four Colorable. II. Reducibility", Illinois Journal of Mathematics, 21 (3): 504, doi:10.1215/ijm/1256049012, MR 0543793, Of the 1834 configurations in 𝓤