ユーリの使った背理法のロジック
数学ガール/フェルマーの最終定理の10.3.2「風景から問題を見出す」(p299)でユーリが問題10-1を解いてみせています。そのとき使ったロジックについて考えてみました。
定理
命題\(P, Q, R\)に対して\((\lnot P \land Q) \Rightarrow R\)と\((\lnot P \land Q) \Rightarrow \lnot R\)がどちらも真ならば、\(Q \Rightarrow P\)は真である。
証明
命題\(A,B,C\)に対して
\[(A\Rightarrow B) \land (A \Rightarrow C) \equiv A \Rightarrow (B \land C)\]
だから
\[ ((\lnot P \land Q) \Rightarrow R) \land (\lnot P \land Q) \Rightarrow \lnot Q) \equiv
(\lnot P \land Q) \Rightarrow (R \land \lnot R)
\]
である。また、命題と対偶命題も論理的同値、つまり論理式で書けば
\[ A \Rightarrow B \equiv \lnot B \Rightarrow \lnot A\]
なので
\[
\begin{align*}
(\lnot P \land Q) \Rightarrow (R \land \lnot R)
&\equiv \lnot (R \land \lnot R) \Rightarrow \lnot (\lnot P \land Q)\\
&\equiv (\lnot R \lor R) \Rightarrow (P \lor \lnot Q)
\end{align*}
\]
である。最後の変形にはド・モルガンの法則を使った。\(\lnot R \lor R\)は常に真であることと、
\(\lnot Q \lor P \equiv Q \Rightarrow P\)を使うと
\[
(\lnot R \lor R) \Rightarrow (P \lor \lnot Q)\equiv Q \Rightarrow P
\]
である。従って
\[
((\lnot P \land Q) \Rightarrow R) \land (\lnot P \land Q) \Rightarrow \lnot Q)
\equiv Q \Rightarrow P
\]
が成り立つ。これが示したいことだった。
応用
- FLT(4)が成り立つ
- フェルマーの最終定理が成り立たず、FLT(4)が成り立つならば、ある3以上の素数pに対してFLT(p)が成り立たない
- すべての楕円曲線は、モジュラーである
- ある3以上の素数pに対してFLT(p)が成り立たないとすれば、フライ曲線は存在する
- フライ曲線は、楕円曲線である
- フライ曲線は、モジュラーではない
以上のことが成り立つとすると、フェルマーの最終定理は成り立つ。このことを証明しなさい。
命題の翻訳
まず列挙された定理を論理記号に翻訳する。
- F:フェルマーの最終定理が成り立つ
- Ln:FLT(n)が成り立つ
- T:ある3以上の素数pに対してFLT(p)が成り立たない
- Px:xは楕円曲線である
- Qx:xはモジュラーである
- Rx:xはフライ曲線である
という記号を使うと、上の定理は次のように書ける。
- \(A_{1} = L4\)
- \(A_{2} = \lnot F \land L4 \Rightarrow T\)
- \(A_{3} = \forall x(Px \Rightarrow Qx)\)
- \(A_{4} = T \Rightarrow \exists x Rx\)
- \(A_{5} = \forall x(Rx \Rightarrow Px)\)
- \(A_{6} = \forall x(Rx \Rightarrow \lnot Qx)\)
証明
\(A = A_{1} \land A_{2} \land A_{3} \land A_{4} \land A_{5} \land A_{6}\)とし、\(B\)をある命題とする。上の背理法を使えば\(\lnot F \land A \Rightarrow B\)かつ\(\lnot F \land \Rightarrow \lnot B\)を導けば、\(A \Rightarrow F\)が成り立つ。
i)\(\lnot F \land A \Rightarrow B\)
\(\lnot F\)とすると、\(\lnot F \land L4\)が成り立つので、これと\(\lnot F \land L4 \Rightarrow T\)から\(T\)は真になる。\(T\)と\(T \Rightarrow \exists x Rx\)から、\(Rx\)を真にする\(x\)がある。これを\(\alpha\)と呼ぶことにする。\(R\alpha\)と\(\forall x(Rx \Rightarrow Px)\)から\(P\alpha\)は真である。\(P\alpha , \forall x(Px \Rightarrow Qx)\)から\(Q\alpha\)。従って
\[\lnot F \land A \Rightarrow Q\alpha \]
が成り立つ。
ii)\(\lnot F \land A \Rightarrow \lnot B\)
また、\(R_{\alpha},~~\forall x(Rx \Rightarrow \lnot Qx)\)から\(\lnot Q\alpha\)。従って
\[\lnot F \land A \Rightarrow \lnot Q\alpha\]
である。
(i),(ii)より、\(A \Rightarrow F\)が真になることが証明された。
参考図書
数学: 物理を学び楽しむために
2章に集合と論理について扱っています。物理学を専攻にする人には、一番薦めやすいです。もちろん、他の人にもオススメです。
だれでも証明が書ける
数学の証明に使う論理や、証明の書き方について書かれています。
論理学をつくる
タイトルの通り論理学をつくっていきますが、論理学の標準的な教科書でもあると思います。練習問題には映画ネタが多くて面白いかもしれません。ただし、数学で使うような論理学を軽く超えていきます。