書記が数学やるだけ#789 自然演繹の規則-2

前回に続き自然演繹の証明に慣れていく。

問題

今回は否定・矛盾・二重否定・背理法に加え，述語論理の全称と存在を加えている。

説明

否定の導入はP仮定した上で矛盾が生じればPでないこと，否定の除去はPでありPでないことから矛盾が生じることを示している。

矛盾について，前提が矛盾していればどんな命題でも真であることが言える。

二重否定は，一見当たり前のことに思えるが，直観主義など排中律を認めない立場では採用できない。

背理法は証明ではお馴染みのもので，Pの否定を仮定すると矛盾が生じることからPであることを結論づける。否定の導入とよく似ているが，背理法の成立には排中律や二重否定の除去が必要という点で異なる。

続いて述語論理について，大筋は命題論理と同じであり，全称と存在を加えることとなる。

解答

ここでは矛盾と否定の除去を用いている。

対偶の証明について，ここは否定の導入と否定の除去を用いて，仮定にない否定を消していく。

ド・モルガンの法則の一つをここで証明しておく，これは否定の総合問題と言える。

二重否定を示すために，背理法を用いる。

述語論理について，文字の置き換えに注意が必要。

述語論理に否定を組み合わせたパターン。

ここでは背理法を用いることで仮定を引き出している。

本記事のもくじはこちら：