2018/10/06

【読書メモ】スマリヤン 記号論理学

スマリヤン 記号論理学 一般化と記号化 丸善出版』
本書を手にした理由は、久しぶりに論理学でもと書店を散策していたさいのこと、偶然手に取って中をパラリパラリと捲ってみたところ、前半部の論理パズル群がちょっと面白ろかったため。
そこで購入してざっと読み進めて見れば、後半部(特に第七章)以降がむしろ本書の主要コンテンツであり、記号論理学の入門本として体を成したものであること納得。

本書はトレーニングの書としての構成上の配慮からか(?)、用語定義や文脈展開はやや散在的で却って捕捉し難い箇所もあるが、全貌を俯瞰してみれば、紹介されている命題論理の根本的な着想はさして厄介なものではない。
『我々の前に、任意の命題ρがあるとして、これ自体では真(T)か偽(F)か判別出来ないとする。しかしここで、この命題ρを成す内訳としての(いわば変数としての)命題 k1,k2,k3 ... までを我々が観察可能であるならば、それらひとつひとつの真(T)か偽(F)と論理上の結合を見極め、命題ρそのものの「真/偽さらには恒真式」が分かる…』

本書の最重要な主題は、おそらくは恒真式(tautology)であろう、あらゆる命題を断片そして全体として恒真式で表現するにあたり、「論理結合子に応じた真/偽判定」で充足しうるとして、それでは「タブロー法表現」では? ─ このあたり、今般ここに読書メモとして(僕のような)初学者とくに学生諸君に紹介してみたいと思い立った。
※ なお、「1階述語論理」まででひとまず閉じられている本書は実は2分冊のうちの1冊にすぎず、もう1冊は同著者がヨリ理数的(技術的)に論旨を深化させた『数理論理学』と銘打って発行されている由である。

では、以僕なりに要約した簡易な読書メモを以下ざっと記す


<第7章: 任意の命題論理を成す主要な論理結合子と、命題の真/偽 

「否定(negation) "~p"」 …或る命題"p"の逆(反対)
これに則った真(T)偽(F)の組み合わせは;
p = T ならば "~p" = F
p = F ならば "~p" = T

「論理積(conjunction) "p∧q"」 …或る命題pおよびqがともに成り立つ
これから成る命題の真(T)偽(F)組み合わせと全体は;
p = T で q = T ならば "p∧q" = T
p = T で q = F ならば "p∧q" = F
p = F で q = T ならば "p∧q" = F
p = F で q = F ならば "p∧q" = F

「論理和(disjunction) "pq"」 …或る命題"p"および"q"のどちらかが成り立つ
これから成る命題の真(T)偽(F)組み合わせと全体は;
p = T で q = T ならば "pq" = T
p = T で q = F ならば "pq" = T
p = F で q = T ならば "pq" = T
p = F で q = F ならば "pq" = F

「含意(implication) "p⇒q"」 …或る命題"p"が成り立つならば命題"q"も成り立つ
これから成る命題の真(T)偽(F)組み合わせと全体は;
p = T で q = T ならば "p⇒q" = T
p = T で q = F ならば "p⇒q" = F
p = F で q = T ならば "p⇒q" = T  (qが真ならば全体としても真)
p = F で q = F ならば "p⇒q" = T  (pが偽ならばqも偽、という含意は全体としては真)

「同値(biconditional) "p≣q"」 …或る命題"p"が成り立つときにかぎり命題"q"も成り立つ
これから成る命題の真(T)偽(F)組み合わせと全体は;
p = T で q = T ならば "p≣q" = T
p = T で q = F ならば "pq" = F
p = F で q = T ならば "pq" = F  
p = F で q = F ならば "pq" = T

・論理式表現と真/偽判定
たとえば、或る命題Xが観察出来るとする。
この命題Xを成す「変数としての命題pと命題q」が (p≣(q⋀p)⇒(~p⇒q)) という論理式で表現されているとする。
この論理式にて変数命題p,qにそれぞれ真(T)偽(F)を充ててみると、2の2乗つまり4通りのケースがある。
ここでは、変数命題pが偽(F)でqが真(T)の場合のみ「命題Xとしては」偽(F)となる、つまり成立しないことがわかる。

同様に、今度は命題Yが観察できるとして、この命題Yを成す変数としての命題p,q,rが (p⋀q)≣(~p⇒r) という論理式で記されるとする。
上と同様、変数命題p,q,rにそれぞれ真(T)偽(F)を充ててみると、2の3乗つまり8通りのケースがある。
ここではp,q,r がそれぞれ T,T,T か T,T,F か F,T,F か F,F,F の場合に「命題Yとしては」真(T)となる、つまり成立することがわかる。
(※ この命題の真偽判定方法論は、たしか別著者による『パズルの国のアリス』における或る難問の解答案としても紹介されていたと記憶する。)

・恒真式
或る命題Zが観察出来るとする。
これを成す変数命題が、論理式として (p⇒q)≣(~q⇒~p) と記されているとしよう。
これで、p,qそれぞれに真(T)偽(F)を充ててみると…なんと、どのケースでもこの「命題Zとしては」必ず真(T)となってしまう(成立する)。
この論理式をとくに恒真式(tautology)と称す。
恒真式の例としては;
((p⇒q)⋀(q⇒r))⇒(p⇒r) …いわゆる三段論法の例
((~p⇒q)⋀(~p⇒~q))⇒p …いわゆる背理法の例、"~p"が偽(F)であることを導く
((p⋁q)⋀(p⇒r)⋀(q⇒r))⇒r …"p⋁q"が真であるときの場合分けによる証明

========================

<第8章以降: 正直者と嘘つきの命題論理>
ここから、本書の第1章など巻頭部における論理問題を、「あらためて命題論理で表現し分析」する。

<巻頭問題1.3の例>
或る島に、複数の住人A1とA2が居り、それぞれ、「正直な騎士」か、あるいは「嘘つきの悪漢」、どちらかである。
ここで、住人A1が「A1とA2はどちらも嘘つきの悪漢だ」と主張したとすると、A1とA2のどちらが正直な騎士だろうか?

まず、このA1ないしA2による何らかの言を、すべて命題ρとしよう。
また、A1が正直な騎士であるという命題論理を k1≣ρ と表現し、これが嘘である場合の命題論理を ~k1≣ρと表現する。
一方で、A2が正直な騎士であるという命題論理を k2≣ρ と表現し、これが嘘である場合の命題論理を ~k2≣ρとする。
すると、本問での住人A1による言つまり命題ρは、k1≣(~k1⋀~k2) という論理式で表現出来る。

さぁそこで、上で挙げたような真(T)/偽(F)を論理式に充当していこう。
k1が真(T)でK2が真(T)ならば、論理式k1≣(~k1⋀~k2)としては偽(F)になる、よって命題ρとして成立しない、と検証が出来、同様に、k1が真(T)でk2が偽(F)ならば命題ρは真(T)かどうか、さらに、k1が偽(F)でk2が真(T)ならばどうか…と検証を続けていく。
すると、k1が偽(F)でk2が真(T)のケースのみ命題ρとして真(T)となる、つまり成立することが分かる。
よって、k1の台詞を吐いたA1が嘘つきの悪漢であり、(ここでは何も言っていない)A2こそが正直な騎士である。

以上にて、命題ρの成立ケースのみを恒真式として表現すれば (k1≣(~k1⋀~k2))⇒(~k1⋀k2) となる。

巻頭問題1.4 についても、同様にアプローチしていく。
住人A1が 「A1とA2のうち少なくとも1人は嘘つきの悪漢だ」と言ったとしよう。
これも命題ρとし、変数命題をk1,k2として論理式 (k1≣(~k1⋁~k2)として、それぞれに真(T)/偽(F)を充当して検討すれば、k1が真(T)でありk2が偽(F)のときのみに命題ρとして真(T)になることがわかる。
このときのみの命題ρを恒真式で表現すれば(k1≣(~k1⋁~k2)⇒(~k1⋀k2)

巻頭問題1.5 では、住人A1が「自分はA2と同じ種類の人間だ」と言う。
やはりこれも命題ρとして、内訳の変数命題による論理式を記すと、k1≣(k1≣k2)となり、それぞれに真(T)/偽(F)を充てて検証してみれば、k1が真(T)であろうが偽(F)であろうがK2は真(T)となることがわかる。
このときのみの命題ρをまとめて恒真式で表せば k1≣(k1≣k2)⇒k2

(以上に抽出した設問と命題化と真(T)偽(F)充当による解説が、本書では続々とふんだんに呈されていくので、トレーニング素材として面白い。)

なお、あらゆる論理命題から恒真式を導く論理が、本書の随所に注記されているネルソン・グッドマンの定理である。

=================================

<第11章: タブロー法による恒真式の証明、など>

或る命題Xが、複数の変数命題とそれらによる論理式から成っているとする。
タブロー法は、それら変数命題と論理式の全体に一括して真(T)/偽(F)を充当するのみならず、変数命題そのものをさらに真(T)/偽(F)に応じつつ論理分解していく
この論理分解のプロセスにては、ひとつの変数命題が論理和(または)から成っているならばさらに細かく命題を分岐させ、またそれが論理積(かつ)から成っているならば直接の帰結の命題に分け ─ こうして細かい命題に分割を続ける。
この徹底的な分解が完了したさいに、それら一つひとつの命題の間にて真(T)偽(F)の矛盾関係(共役関係)があるかないかを確認出来、仮に最初の命題Xそのものが真(T)でしかありえないと知れたら、これが恒真式であるともわかる。

(仔細は面倒なので引用省くが、本書p.87以降に実践的に記されている。)

同じ命題Xについても、変数命題と論理式の表し方によって、タブロー法による分割の仕方も変わり、ステップ数の少ない(効率的な)タブロー法分析も実現しうる。

※ 上に挙げたタブロー法はどこまで完全なのか、本書にてはp.100以降から、命題と論理の恒真性を証明するにあたって「正しい(correct)」か「完全(complete)」かを更に問い続けており、了察にあたっての難度が上がる ─ ような気がする。

======================

以上、あくまで本書のごく一部だが紹介してみた。

論理学については、量化問題や健全性問題はどうか、また電子素子との実装親和性はどうか、ソフトウェアプログラムとの相性はなどなど、巨大な拡張性について想像するだけでも圧倒されそうになる。
それでも、本書の主たるテーマである、論理の「峻別と単純化」のスキル探求は、法分野などでも有効な気はしている ─ ただし、知識の組み替えや着想の飛躍で出来ている分野(たとえば数学そのもの)においてはあまり有用でないこと、識者の多くが指摘するとおりであろう。

ともあれ、学生諸君などは僕の分まで(いや僕の見識など超越して)秋の夜長に大いに悩み、翌朝には颯爽と閃き、まあそんなふうに精進するがいいさ。