中文数学 Wiki
Advertisement

反證法,又稱歸謬法,是一種證明某命題為真的方法,藉由假設原本敘述是錯的,再從中推出當原本的敘述是錯的時會出現矛盾,以證明原有的命題為真。

像例如說「若X則Y」,若要證明此命題為真時,可假設此命題不成立,Y為偽,並藉由各種合理的步驟,從X為真但Y為偽的狀況下,一步步地推演出「在Y為偽的狀況下,X為真的狀況」會出現自相矛盾的結果,藉此間接證明原「若X則Y」的命題為真。「若X則Y」和「若非Y則非X」兩者同時成立和不成立,反證法即很多程度上藉由否定使「若X則Y」或「若非Y則非X」不成立的狀況,來證明「若X則Y」或「若非Y則非X」其中之一成立。

反證法基於排中律無矛盾律,是一種非構造性、間接的證明的方法,因為它往往並未從正面給出使定理成立的具體元素,因此直覺主義邏輯的支持者不使用它。

實例[]

命題:「質數有無限多個」

證明:假設「質數有無限多個」是錯的,也就是說,「質數僅有有限多個」是對的。那麼就可以假設所有的質數分別為,然後將所有的質數相乘加一,可得,但顯然這個數不可為除盡,因此要不就是一個質數,要不就存在一個質數可除盡,但不管怎樣,顯然在之外,都有別的質數存在,此與先前的假設矛盾,因此「質數僅有有限多個」是錯的(無矛盾律),進而「質數有無限多個」是對的(排中律)。

參見[]

  • 非構造性證明
  • 排中律
  • 直覺主義邏輯
  • 構造性證明
Advertisement