ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

形式論理と自然演繹の紹介

論理学の勉強で自然演繹を学んだので、とうとうご紹介したいと思います。

論理学といえば自然演繹、自然演繹といえば論理学ですね。
いや、そんなにでもないか…。


自然演繹を紹介するとは言っても正直なところ、健全性や完全性の証明とかそんな深入りして紹介するのは大規模過ぎて難しいので、
さらっと規則を紹介したり、具体例を示したり、で済まそうと思いますが。

あと、述語論理での扱いも入れたかったのですが、面倒なのと、固有変数条件あたり熱弁して空回りするクソ解説を生産しそうなので、命題論理にとどめておきました。


自然演繹は論理学の形式的証明の方法のひとつで、自然演繹の他には、
ヒルベルト式と呼ばれる矢印だらけの気色の悪い、仕組みは単純だけど使うのが難しいものとか、

シークエント計算という、これはまだ勉強中なのでコメントしづらいんですが、シークエントというものに対してゴニョゴニョしていくものなどがあります。

ちなみに、自然演繹とシークエント計算は、同じゲンツェンという人が発明したそうです。


さて、今回の記事は前編と後編ではなく、ひとつの記事で完結しますが、執筆には2日間かけています。

続きを読む

tag: 数学 論理学 構文論 論理式 証明 命題論理 直観主義 自然演繹 形式 勉強

命題論理の意味論まとめ (後編)

昨日は命題論理について勉強したことのまとめとして、記事「命題論理の意味論まとめ (前編)」を書きましたが、

今回はより話が本格的になってくる後編を書いてまいります。


なお前編で、集合{ T, F }の要素としてのT, Fと、論理式の構成要素としてのT, Fは別物だということに注意しなければならないと触れましたが、

今回はそれを区別するために、論理式の構成要素として使うのはT, Fなんですが、
命題論理で使う集合の{ T, F }のほうは{ 1, 0 }に改めます。

もちろん1が真で0が偽なので、そのように読みかえてください。



前編で言った∨, ∧, ¬の三種類の演算があれば、実は残りの→, ↔は代用可能であるということの、理由については言及しませんでしたが、

まずa→bは、aならばbであり、aでなければあらゆる場合に真ということでしたからaかつb、またはaでないのどちらかで、(a∧b)∨¬aといえます。

つまり代用可能です。

しかしよく考えれば、(a∧b)¬aは満たす条件が排他的ですが、わざわざ排他的にする必要もありません。

つまり、aがなんであれbが真ならばこの演算は真であって、ようするにb∨¬aというふうに、よりスリム化できます。


今、日本語でグダグダと説明しましたが、もちろん厳密にそれを言うためには、前編で触れたように表を用いて確認します。

ただ、今の話のように、演算子の日本語としてのイメージを捉えたうえでわかることというのを考えて、最後に表で確認するという方法は悪くないですね。


まあこの先、それでどんどん法則が増えていって、ほとんど法則とかで同値変形していく感じになって、今後は日本語を使うことなんてほぼないですが…。


なお、a↔bについては、aならばbだしbならばa、ということになるので、これも日本語的に考えて(a→b)∧(b→a)となります。

二つの演算は前述のようにで代用できるので、それをで結んでいるだけなので、結局も三つの演算で代用できることになりますね。

続きを読む

tag: 数学 論理学 法則 標準形 論理式 命題 命題論理 意味論

命題論理の意味論まとめ (前編)

記事「集合と写像の勉強まとめ」なんかも書きましたが、
昨年末から論理学の勉強を継続的にしていて、京都大学の教授の方のサイトをずっと見ています。

そういえばこの前、このサイトが書籍化されたらしい本を見かけました。


今回、命題論理、とくに意味論について書かれてある部分を、ようやく読破しましたので、そのまとめとしてお書きしようと思います。


そういえば昔も論理学について放送大学で学んで、記事「記号論理学という学問を知ってみたが」を書いたことがありました。

あのときは今回の命題論理よりハイグレードな述語論理だったんですが、数学的で厳密な定義はおいといて実用的な論理学をやるみたいなものでしたので、

今回は厳密な部分をとばさずに再挑戦しているみたいな感じですね。

記事の書き方も、あの記事ではトップダウン的な説明でしたが、今回はボトムアップ的であると思います。


ところで、意味論とか構文論ってどういうことなのかイマイチ入ってこないのですが、“命題論理の意味論”なのか“意味論の命題論理”なのか、どっちなんでしょうか。

一応、“命題論理の意味論”と書いてあったので、そういうことにしておきますが…。


あと、記事「集合と写像の勉強まとめ」と続編記事「続・集合と写像の勉強まとめ ~ブール代数も~」、
で書いた数学の知識は正直ほとんど使わなかったと思うのですが、最初の根源的な定義をするところで少しその知識がいりますね。


少なくとも演算というのが何なのか理解する必要がありますし、演算というのがなんのか理解するには写像についての理解、ひいては集合とは何か…

数学は少しずつ積み上げる学問なので、学校で嫌われるんですね。


今回、ひとつの記事に収めるつもりだったのですが、すごく基本的な話をしただけで無駄に長くしてしまったので、これを前編として次回、後編を書こうと思います。

お楽しみにしていてください。

続きを読む

tag: 数学 論理学 演算 論理式 命題 命題論理 集合 意味論

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。