すごブロ

「好き」をブチ抜く

本、映画、科学、哲学、心理、すごい人の考え方、など。

数理論理学入門に最適 【はじめての数理論理学】証明の具体例が豊富でありがたい

はじめての数理論理学 証明を作りながら学ぶ記号論理の考え方

 

今回紹介したい本がこちら。画像クリックでAmazonへ飛べます!

 

 

論理とは何かを追求する人が行き着くところが「論理学」。

 

しかし、なかなかとっつきやすい入門書がない。

 

今回の本は、高校生でも読めるかなり親切な本だ。興味がある人がまず手に取ってみるのにいい本だと思う。

 

 

 

 

 

 

 

序章 数理論理学とは

 

論理的に物事を考える時、人はどのような方法を使っているのか?

 

この問いに、数学的に応えようとする。

 

とくに、主張推論に、数理論理学は注目する。そこで役立つのが、記号で表すということ。

 

そうすれば、「証明」そのものを対象にできるのだ。これによって、「どんな証明のよっても、Aという命題を示すことはできない」などの主張を議論できるようになる。数学においては、とても大事なことに見えないだろうか??(一方、日常生活とはだいぶ離れてしまう??笑)

 

 

 

 

 

1 論理式

 

推論の例は次だ。

 

4の倍数である整数は、みな偶数だ。

8は4の倍数である。 

よって、8は偶数だ。

 

推論に現れる主張を記号化する。主張が正しいかどうかや、何を証明すべきかを分析しやすくなる。

 

 

 

 

 

2 証明法

この本の親切なところが、この2証である。

 

普通の数理論理学の教科書のように、いきなり「自然演繹」という形式的なものを見せられても意味がなかなかわからない。その自然演繹がどのように役立つか、なぜ必要か、ということを実感しにくいのだ。

 

なぜならば、そもそも「数学の証明」というものの全体像と具体例をまだまだつかめていないからだ。高校でやる証明といえば、数学的帰納法背理法などだけだ。これでは、具体的すぎて、数学の証明とは何かという視点を持ちにくい。それでは、わざわざ証明そのものを記号で表すということの意味も気づきにくい。

 

この数学における推論こそ、証明である。そして、数理論理学が対象にするのは、人間の推論行為だ。それならば、数理論理学の中心こそ、「証明」をどう扱うか、である。

 

証明を扱うには?

 

証明に使われる「推論そのもの」を記号で表わそう!!

 

という流れである。

 

もう一度繰り返すが、だからこそ、元々の数学の証明とは何か、という具体例を知っておくとイメージがしやすい。この部分をこの本は助けてくれる!!!

 

以下のように具体的な数学の証明を紹介してくれる。どんどんイメージがしやすくなる。

 

・含意の証明

・同値の証明

・全称と存在の証明

・論理法則の利用と反証

 

 

 

 

 

 

3 自然演繹 記号を使って証明を表す

 

いよいよ、「自然演繹」の説明に入る。自然演繹とは、人間が普段使う推論に近い。だから、数理論理学入門に最適だと思う。

 

推論を記号によって表現するため、「推論規則」を定義する。その推論規則を繰り返し使うことで、証明全体を構成する。

 

自然演繹(しぜんえんえき、: Natural deduction)は、「自然な」ものとしての論理的推論の形式的モデルを提供する証明理論の手法であり、哲学的論理学の用語である。

自然演繹 - Wikipedia

 

推論規則を具体的に見たい人は、wikiのリンクに飛んでみてほしい。

 

自然演繹による証明図は次のようなものだ。推論規則を繰り返し使うことによって、証明が構成される。

 

f:id:asc_meta:20190429172133j:plain

引用 https://slidesplayer.net/slide/11581795/

 

 

 

 

 

 

自然演繹って証明に十分な体系なの?

 

 

主張や推論を記号で表現してきた。それらをより厳密に分析したい。

 

 記号を形式と内容に分けて考える!!!!

 

構文論・・・議論の対象をどんなで表すのか

意味論・・・論理式の内容について考え、「正しい論理式とは何か」という疑問に答える。つまり、記号をどう解釈するか。

 

 

 

構文論の意義

証明が適切に組み立てられているかは、論理式や証明が表す内容とは無関係に、証明の形式だけで決まる。パズルのようなものだが、どんな記号操作が許されるのか、明確に決めておく必要がある。

 

こうした構文論の議論が整備されて、証明可能性という概念が定義できる。

 

証明可能性

論理式Aが自然演繹により証明可能であるとは、Aが結論であって、それが依存する仮定が一つもない導出を作れること

 

 

 

意味論の意義

「単なるパズルの操作ではなくて、論理的な推論の基本原理を抑えている」これを確かめたい。だから、意味論を考える必要がある。

 

健全・・・証明できる論理式がどれも正しい

完全・・・正しい論理式がどれも証明できる

 

健全で完全であるならば、その証明体系は十分な証明能力を持っていることになる。

 

恒真性・・・恒に正しい論理式は、記号をどう解釈しても真になる

 

 

 

構文論と意味論をつなぐ

 

・Aが自然演繹で証明可能ならばAが恒真 健全性

・Aが恒真ならばAが自然演繹で証明可能 完全性

 

 

自然演繹では、論理式の証明可能性(構文論)と恒真性(意味論)が一致する。

 

 

数学的に厳密に考えていくには、記号を導入する必要がある。そして、記号化された証明の性質を厳密に考えるために、構文論と意味論が必要になる。この流れを、すこしは感じてもらえただろうか?

 

 

こうした自然演繹についての結果を、さらに知りたい人には次の本がおすすめだ。教科書的で、じっくり読む必要はある。

 

 

 

 

 

 

ゲーデル不完全性定理

 

数学における証明体系のある限界を示した重要な定理だ。名前だけは知っている人も多いと思う。次の記事にまとめているので、興味がある人は是非読んでみてほしい。

 

interaction.hatenadiary.jp

 

 

 

 

 

関連記事

 

interaction.hatenadiary.jp

interaction.hatenadiary.jp

interaction.hatenadiary.jp