論理学の孤独な散歩道

散歩者の独り言―「孤独な」というのは「ロンリー」という意味ですか。ルソーの自叙伝のタイトルを踏まえている?
説明が少ないのは、まあ、自分の頭を使えということですね、ロンリーですからね。
論理学で使う記号はパソコンで出しにくいが、Windowsなら、「きごう」と入力すると、ずらずらと多くの記号が出るので、使うものを辞書に登録しておけばよいでしょう。
でも、出ない記号も少なくない。
(断定記号(「┠」「|-」みたいなやつ)は矢印(→と⇒)で代用。)


命題論理
(真理関数の理論)

命題論理は、命題(文)を単位として、その論理的関係を分析する。
命題(proposition)とは、真か偽かのどちらか(真理値)を決定しうる文をいう。
否定子と接続詞を含まない単文を、要素命題と呼ぶ。要素命題が組み合わさって複合命題ができる。
要素命題の値が決まれば、全体の値が一意的に決まる複合命題を、真理関数(truth function)と呼ぶ。
(一つの命題だけからなる真理関数(=一項真理関数)は、肯定と否定の二つ、
二つの命題からなる真理関数(=二項真理関数)は、全部で24=16個あるが、よく使われるのは、下のいくつか。三項以上の真理関数は、必要がない。)
例題1 命題ではない文の例を一つ挙げなさい。
例題2 真理関数ではない複合命題の例を三つ挙げなさい。

論理記号
否定 「Aでない (not)」 ¬A
連言 「AかつB (and)」  A∧B
選言 「AまたはB (or)」 A∨B
条件 「AならばB (if)」 A⊃B (「含意」とも呼ばれる。A implies B)
同値 「AとBは同値(Aならば、またその時に限って、B (iff = if and only if))」 A≡B
    A≡B は (A⊃B)∧(B⊃A) または (A∧B)∨(¬A∧¬B)
    A⊃B は ¬A∨B  または ¬(A∧¬B) と書き換えられる。
例題3-1 両否定(「AでもBでもない」 A|B)だけを用いて、否定と連言を定義しなさい。
例題3-2 条件記号(⊃)だけを用いて、選言(∨)を定義しなさい。
→例題の回答   

真理表

真を1、偽を0で表わすと、真理関数の真理値は次のようになる。

A ¬A
1 0
0 1
A B A∧B A∨B A⊃B A≡B
1 1 1 1 1
1 0 0 1 0
0 1 0 1 1
0 0 0 0 1
これらのうち、∨の1行目、⊃の3/4行目が、通常の日本語の用語法と較べると、若干の問題があるかもしれない。
「または」に関しては、「太田が犯人か、または田中が犯人だ」と言うとき、通常は太田か田中の単独犯であり、
太田が犯人かつ田中が犯人(共犯?)の場合は含まない。
しかしそれは事柄(内容)から来るものであり、「または」という言葉そのものの問題ではない。
例えば、(x-1)(x-4)=0 ゆえに x=1 または x=4 というとき、x=1 かつ x=4 ということはあり得ない。
しかし、(x-1)(y-4)=0 ゆえに x=1 または y=4 というとき、x=1 かつ y=4 ということは可能である。
だから「または」という言葉そのものの意味としては、AかつBの場合を含んでいると考えてもいいだろう。
論理学では、A∧Bを含む「または」を非排反的選言と呼び、A∧Bを含まない「または」を排反的選言と呼ぶ。
とちらを選ぶのも自由だが、一般的には、日常の用語法に近く、「かつ」と双対(dual)の関係にある、非排反的選言が使われているということだ。
条件の「ならば」に関しては、もっと大きな問題がある。
前件が偽のときに全体の真理値を真とするのは正しいのだろうか?
これは自分で考えてもらおう。

例題4-0 「ならば」で前件が偽のとき真理値が真になるのはなぜなのか、答えなさい。
例題4-1 上の真理表の同値(A≡B)の欄を埋めなさい。
例題4-2 次の真理表を埋めなさい。

A B A⊃B (A⊃B)⊃A ((A⊃B)⊃A)⊃A
1 1
1 0
0 1
0 0

最低覚えておくべき論理法則(トートロジー)
同一律 A⊃A
矛盾律 ¬(A∧¬A)
二重否定 ¬¬A≡A
ド・モルガン ¬(A∧B)≡¬A∨¬B
        ¬(A∨B)≡¬A∧¬B
結合法則 A∧(B∨C)≡(A∧B)∨(A∧C)
       A∨(B∧C)≡(A∨B)∧(A∨C)
対偶法則(第一) (A⊃B)⊃(¬B⊃¬A)
      (第二) (¬A⊃¬B)⊃(B⊃A)
添加法則 A⊃(B⊃A)
排中律 A∨¬A
MP(Modus Ponens 前件肯定式) A∧(A⊃B)⊃B
これら以外では、
A∧0≡0 A∧1≡A
A∨1≡1 A∨0≡0 など。ただし、0は恒偽命題、1は恒真命題。 

トートロジーの判別(意味論的タブロー
1)与えられた式を、偽になると仮定し、否定記号をつける。
2)以下のルールに従って外側から要素命題にまで分析する。
 (枝分かれするものは、どちらか一方が真であればよい。枝分かれする式の分析は後回しにする方が効率がよい。)

 A⊃B
 /\
¬A  B

 A∧B
  |
  A
  B

  A∨B
  /\
 A    B

A≡B
(下記)
¬(A⊃B)
   |
   A
  ¬B

¬(A∧B)
  /\
 ¬A ¬B

¬(A∨B)
   |
  ¬A
  ¬B
¬¬A
  |
  A
¬(A≡B)
(下記)

3)矛盾(同じ枝のリストにAと¬A)が生じたら、Xをつけて分析を止める。
4)全ての枝で、Xがついたら、元の式は偽になることはないので、トートロジー。
 先端にまで行って矛盾が生じない枝が一つでもあれば、偽になりうるので、トートロジーではない。
 (その枝の先端に○をつけて、他の枝の分析を止めてよい。)
例題5 同値(A≡B と ¬(A≡B))の分析のルールを自分で考えよ。

ラッセル=ヒルベルトの公理系R
原始記号 ¬, ∨, p, q, r, …, (, )
論理式 p, q, r, …は式
     AとBが式のとき、¬(A), (A)⊃(B) は式
 (派生記号の定義 A∧B=df¬(¬A∨¬B), A⊃B=df¬A∨B, A≡B=df(A⊃B)∧(B⊃A)
公理1 p∨p⊃p
公理2 p⊃p∨q
公理3 p∨q⊃q∨p
公理4 (p⊃q)⊃(r∨p⊃r∨q)
推論規則1(代入規則) 一式中の命題変項はすべて他の式で置き換えてもよい(ただし、代入は一斉に行う)。
推論規則2(分離規則=MP) AとBを任意の式とすると、A と A⊃B から B を得ることができる。
例題6a この公理系によって、定理A⊃A を証明しなさい。

ウカシェヴィツの公理系L
原始記号 ¬, ⊃
論理式 AとBが式のとき、¬A, A⊃B は式
 (派生記号の定義 A∨B=df¬A⊃B, A∧B=df¬(A⊃¬B))
公理1 A⊃(B⊃A)
公理2 (A⊃(B⊃C))⊃((A⊃B)⊃(A⊃C))
公理3 (¬A⊃¬B)⊃(B⊃A)
推論規則1 A と A⊃B から B を得る。(MP)
(文字A, B,…などは形を表わしており、この形をしたものは全て公理だから、代入規則は要らない。)
例題6b この公理系によって、定理A⊃A を証明しなさい。

演繹定理
A→B ⇔ →A⊃B
Aを仮定してBが成り立つなら、仮定なしにA⊃Bが成り立つ。およびその逆。
(一般的に書くと、A1,…,An-1,An→B ⇔ A1,…,An-1→An⊃B )
コメント この定理の意味が理解できたら、あなたの論理学の知識は、なかなかのものだと思う。
→演繹定理の証明

自然演繹(NK)による証明
Aを仮定してBなら、Aを消去して、A⊃B (演繹定理)
AとA⊃Bから、B (MP)
AとBから、A∧B
A∧Bから、A  および、A∧Bから、B
Aから、A∨B  および、Bから、A∨B
Aを仮定してC、かつBを仮定してCならば、AとBを消去して新たにA∨Bを仮定して、C
 (言い換えれば、A⊃CかつB⊃Cならば、A∨B⊃C)
Aと¬Aから、人(矛盾)
Aを仮定して人(矛盾)なら、Aを消去して、¬A (背理法)
人(矛盾)から、D(任意の命題)
¬¬Aから、A

NKの証明図
上の推理規則を図にすると(上が記号を入れる規則、下が取る規則。「…」は途中省略の意味)

A

 B 
A⊃B
A B
A∧B
 A   B 
A∨B A∨B
A


¬A
A A⊃B
B
A∧B A∧B
A   B
    A B
    
A∨B C C      C  
A ¬A

D
¬¬A
  A

証明図において一番上に来る(上に横線がない)のは全て仮定。
(仮定が途中で消去されていなければ証明ではない。
だからNKでは演繹定理か背理法を用いないと証明にはならない。)
横線は上の式が下の式に変形されるという論理関係(推論規則の適用)を表わす。
一番下に来るのが証明されるべき定理。
例えば、定理 A∧(B∨C)⊃(A∧B)∨(A∧C) の証明図は、次のようになる。
(三つの仮定のうち、BとCは4行目で、A∧(B∨C)は6行目で、消去されている。)

      A∧(B∨C)     A∧(B∨C)
           A  B         A  C
A∧(B∨C)    A∧B         A∧C    
  B∨C  (A∧B)∨(A∧C) (A∧B)∨(A∧C)
             (A∧B)∨(A∧C)      
         A∧(B∨C)⊃(A∧B)∨(A∧C)

例題7−1 (A⊃(B⊃C))⊃((A⊃B)⊃(A⊃C)) を証明しなさい。
例題7−2 (¬A⊃¬B)⊃(B⊃A) を証明しなさい。
例題7−3 A∨(B∧C)⊃(A∨B)∧(A∨C) を証明しなさい。
例題7−4 A∨¬A を証明しなさい。(いきなりは無理?)
例題7−5 ((A⊃B)⊃A)⊃A を証明しなさい。(パースの法則)
→例題の回答

公理系の性質
公理系には、
公理中心の公理系(上記の、ラッセル=ヒルベルトの公理系R、ルカシェヴィッツの公理系Lなど)と、
公理を用いない推論規則中心の公理系(ゲンツェンのNKやLKなどの自然演繹やタブロー)とがある。
どちらにしても、次の三つの内、1)無矛盾性と 2)完全性は公理系には必須の性質である。
1)無矛盾性
ある式Aとその否定形¬Aが、その公理系で同時に定理として導かれることはない。
(もしこの条件が上の公理系で満たされないとすると、→A⊃(¬A⊃B)だから、これに(仮定により)→Aと→¬Aを加え、推論規則1(MP)を二度適用して、→Bが得られる。
Bは任意の式だから、その公理系では全ての式が定理として証明できるということになる。それでは公理系が存在する意味がない。)
2)完全性
「定理であれば、妥当式(恒真式)である(→Aならば⇒A)」ことを「健全性(soundness)」、
「妥当式であれば定理である(⇒Aならば→A)」ことを狭い意味での「完全性(completeness)」といい、
両者を併せて強い意味での「完全性」という。
(命題論理の範囲でなら、
この公理系の定理は全てトートロジーであり(健全性)、
トートロジーであれば、すべてこの公理系で証明できる(完全性)、ということ。)
3)独立性
どの公理も他の公理から導出されない。
(上のラッセル=ヒルベルトの公理系もルカシェヴィッツの公理系も、この三つの条件を満たしているから、
公理の一つを取り除けば、トートロジーだけどその公理系では証明できない式が出て来てしまい、不完全な公理系になる。)
例題8 上の公理系の無矛盾性と完全性を証明せよ。(無理?)


述語論理
(量化の理論)

命題を主語(=個体)と述語(=性質や関係)に分析し、その妥当する範囲(=量化)を限定する。
一般には、大文字で述語を、小文字で主語を(x,y,z などで個体変項を、a,b,c などで個体定項を)表わし、
述語を先にして、Fa、Rxy などと書く。(「aはFである。」「xはyに対してRである。」)

量化記号
全称記号 ∀ 「すべての〜について(for all 〜)」
存在記号 ∃ 「〜が(少なくとも一つ)存在する(for some〜)」
量記号のついた個体変項を「束縛変項(bound variable)」、
量記号のついていない個体変項を「自由変項(free variable)」と呼ぶ。
(注意 量化記号は否定記号と同じ結合力を持つから、∀xFx⊃Gx という論理式では、∀xは最初のFxだけにかかかっており、文字は同じでも後のGxとは無関係である。
Gxにまで作用域を及ぼすためには、∀x(Fx⊃Gx) と書く必要がある。この括弧は絶対に省略できない。)

例題9 次の文を記号化しなさい。
1)中居正広は歌手であるが歌は下手である。
2)歌が下手なものは歌手ではない。
3)歌が下手な歌手というものが存在する!
4)中居より歌が下手な歌手は存在しない。
5)中居より歌が下手ならば、そんな奴は歌手ではない。
一部の解答
中居正広をa、歌手であるという性質をK、歌が下手であるという性質をHとすると、
1)Ka∧Ha
2)∀x(Hx⊃¬Kx)
3)∃x(Kx∧Hx)
「AはBである」という形の日本語でも、意味を考えると、「全て」の場合は ∀x(Ax⊃Bx)、「存在する」の場合は ∃x(Ax∧Bx) となることが多い。
4)と5)は、xはyより歌が下手だという関係をPxyとして記号化する。(残りの解答は→例題の回答

最低覚えておくべき論理法則(恒真式)
ド・モルガン ¬∀xFx≡∃x¬Fx
         ¬∃xFx≡∀x¬Fx
全称例化 ∀xFx⊃Fx
存在汎化 Fx⊃∃xFx
交換法則 ∀x∀yRxy≡∀y∀xRxy
       ∃x∃yRxy≡∃y∃xRxy
       ∃x∀yRxy⊃∀y∃xRxy
因みに、全称汎化(Fx⊃∀xFx)と存在例化(∃xFx⊃Fx)を使う際には変項条件がつきます(省略)。

述語論理のモデル理論
<D, V>
領域D(Domain)
付値関数V
(省略)

恒真式の判別(タブロー

∀xFx

Fx
∃xFx

Fα
¬∀xFx

∃x¬Fx

¬Fα
¬∃xFx

∀x¬Fx

¬Fx

ただし、αは不確定名(まだ表れていない新しい変項を代入)
自由変項のxには、上で現われている全ての自由変項を代入する(一つでも矛盾が生じたら×)。
(その他の注意点は、存在記号から先に外すということと、多重量化では外から先に外すということだろうか。)

ウカシェヴィツの公理体系L
原始記号 ¬, ⊃, ∀
論理式 AとBが式のとき、¬A, A⊃B は式
 Fx、∀xFx は式
 (派生記号の定義 ∃xFx=df¬∀x¬Fx)

公理4 ∀x(A⊃Fx)⊃(A⊃Fx)
推論規則2 Fx から ∀xFx を得る。

自然演繹(NK)による証明

 Fa 
∀xFx
   (注1)
 Fa 
∃xFx
∀xFx
Fa
   
    Fa
    
∃xFx A
  A
    (注2)

注1)自由変項a はFa の依存する(=Fa より上にある)いかなる仮定にも含まれていない。
注2)自由変項a は、Fxにも、Aにも、またFa の依存する(=Fa より上にある)いかなる仮定にも含まれていない。

述語論理の無矛盾性
ウカシェヴィッツの公理系Lを用いて、この公理系に現れる全ての式について、∃を定義にしたがって∀に書き換えておく。
その上で、この公理系Lの全ての式から、∀と固体記号(アルファベットの小文字)を消去し、このLを「∀抜き」した公理系をL*とする。
すると公理4は、(A⊃F)⊃(A⊃F)となるが、これは(A⊃A)という形のトートロジーである。
また推論規則2も、「FからFを得る」というトートロジーになる。
さて、いま、公理系Lが矛盾する(つまりLでAと¬Aが証明される)と仮定する。
するとLを∀抜きした公理系L*も矛盾する(つまりL*でもAと¬Aが証明される)ことになる。
ところがL*は命題論理の公理系に、公理4(A⊃F)⊃(A⊃F)と推論規則2「FからFを得る」を付け加えたものであるから、
公理系L*が矛盾するということは、命題論理の公理系が矛盾するということである。
しかし命題論理の公理系が無矛盾であることは既に証明されている。
したがって述語論理の公理系Lは無矛盾である。


非古典論理

二値原理(真か偽か、必ずどちらかの値をとる)に基づく論理を古典論理と呼び、そうでない論理を非古典論理と呼ぶ。
直観主義論理多値論理、厳密含意、様相論理などがその代表である。

様相論理
「必然である」「偶然である」「可能(不可能)である」といった論理の関係を様相と呼ぶ。
「義務である」「許されている」「禁じられている」という義務の論理関係を扱う義務論理(deontic logic)、
「信じている」「知っている」といった信念や知識の関係を扱う(一般的に言えば)内包論理(intensional logic)、
「〜だった」「〜であろう」といった時間の論理関係を扱う時制論理(tense logic)、
「必然的に帰結する(含意する)」といった厳密条件=含意(strict conditional=implication)なども、
同様の仕方で扱いうるので、広い意味での様相論理(modal logic)の一部である。

様相記号
必然 □A 「Aは必然である(必然的にAである)」(necessarily; it is necessarily the case that A.)
可能 ◇A 「Aは可能である」(possibly; it is possibly the case that A.))
  ◇A≡¬□¬A
  □A≡¬◇¬A
 偶然▽は、次のように定義できる。▽A=df◇A∧◇¬A

(命題論理の)公理系
K(クリプキKripkeによる体系)―最も基礎的な(弱い)体系(命題論理の公理系Pに次の公理と推論規則を加える)
 分配公理 □(A⊃B)⊃(□A⊃□B)
 必然化規則 Aが定理なら、□Aも定理である(A→□A)
T(Mとも呼ばれる、ゲーデルによる体系)―Kに次の公理を加えた体系
 必然性の公理 □A⊃A
B(ブロウエルBrouwer体系)―Tに次の公理を加えた体系
 A⊃□◇A
S4(ルイスによる体系)―Tに次の公理を加えた体系
 □A⊃□□A
S5(ルイスによる体系)―Tに次の公理を加えた体系
 ◇A⊃□◇A
様相論理の公理系は無数にあるが、Kは弱すぎて、□A⊃A のような妥当な式さえ扱うことができない。
その意味では、Tが様相の基礎的な体系である。
しかし、OA 「Aは義務である」(道徳的な必然性)とか、BA 「Aを信じている」(認識の必然性)といった関係の論理を扱う場合には、
(「Aは義務である」や「Aを信じている」から「Aは事実である」が導かれてはいけないので)、
Tでは強すぎる。よって
D―Kに公理 □A⊃◇A を加えた体系
を用いる。

Tの定理としては、
A⊃◇A
◇(A∨B)≡◇A∨◇B
◇(A∧B)⊃◇A∧◇B
などがある。(述語論理の恒真式と形が似ていることに注意。)
さらに、BとS4とS5では、多重様相が扱われる。
(Sという名はルイスの著書"Surveys of Symbolic Logic"から)
S5の定理としては、
□□A≡□A (これはS4の定理)
□◇A≡◇A
◇□A≡□A
◇◇A≡◇A (これもS4の定理)
などがある。
(従って、□や◇が複数重なっている多重様相は、最後の様相記号より前のものは省略できる―ということが分かる。)

これらの関係を図にすると、次のようになる。
      S4
K←T<   >S5
      B
(うまく書けないが、右から左にすべて矢印(=証明可能)が付いていると読んでほしい。つまり、S5からS4やBが導けるし、S4やBからTが導ける。)

例題10a
S5の体系でS4の公理(□A⊃□□A)が導けることを証明しなさい。
例題10b
S4とBの公理からS5の公理が導けることを証明しなさい。
例題11
述語論理の無矛盾性の証明を参考にして、Tの無矛盾性を証明しなさい。

(→例題の回答)

可能世界意味論
「必然である」というのは、どういう意味なのか、キリスト教的な世界観(例えば、トマス=アクィナス『神学大全』)で考えてみる。
万物の創造主である神は全能であると言われる。「奇跡」という仕方で物理法則に反する事実を生じさせることもできる。
死者が生き返ること(生物学的な必然)も、水が下から上に流れること(物理学的な必然)も、可能だと考えられる。
しかし、その神でも、論理法則や数学上の法則に矛盾した行動をとることは、神の概念に矛盾するから、不可能だとされる。
(また、これは異論があるだろうが、一度起こった事実を取り消すこともできないとされる。
例えば、死者を甦らせることができたとしても、その人が死んだという事実を変えることはできないのだから。A⊃□A ?)
であるから、(Aを「2+3=5」(真)と置けば□Aは真であるが、)Aを「カラスは黒い」(いちおう、真)と置いたとき、□Aは偽である。(だから真理関数ではない。)
我々は矛盾なく白いカラスが存在する世界を考えることができる。そういう世界を神が創造したことは可能である。
必然的命題とは、単にこの世界だけではなく、他の全ての可能な世界において真であるような命題をいう。

いま、世界を「w」で表わし、命題Pが世界wで成り立つことを「Pw」と書くことにすると、
□P≡∀wPw
◇P≡∃wPw
これらの間には、
∀wPw≡¬∃w¬Pw
∃wPw≡¬∀w¬Pw
という関係が成立する(可能世界の量化)。

到達可能性(accessibility)の関係R(クリプキ・モデル)
いま、世界 w1から世界 w2が想像可能であるとき、
(言い換えれば、世界w2で事実(真)であることが世界w1で可能であるとき)、これを
「w1からw2へ到達可能である」といい、
w1Rw2
と書く。
このRには、反射性(ρ)、対称性(σ)、推移性(τ)、拡張性(η)といった関係が考えられる。
反射性 w1Rw1 (w1からw1へ到達可能である)
対称性 w1Rw2ならば、w2Rw1 (w1からw2へ到達可能ならば、 w2からw1へも到達可能である)
推移性 w1Rw2であり、w2Rw3であるならば、w1Rw3 (w1からw2へ到達可能であり、w2からw3へ到達可能ならば、w1からw3へ直接到達可能である)
Rが反射的である場合、Tに対応する。
(必然性の公理□A⊃Aは、A⊃◇Aと書き換えられるが、これはw1でAが真のときw1から到達可能な一つの世界でAが真であることを意味するから、w1が自分自身であるw1に到達可能であればよい。)
Rが(反射的で)対称的である場合、Bに対応する。
(A⊃□◇Aは、Aであるとき(つまりw1においてAが真であるとき)、w1から到達可能な全ての世界w2において◇Aである、つまりそこ(w2)から到達可能な少なくとも一つの世界が存在するということを意味している。これはw2からw1へ到達可能だということに他ならない。)
Rが(反射的で)推移的である場合、S4に対応する。
(□A⊃□□Aは、◇◇A⊃◇Aと書き換えられる。この左辺◇◇Aは、w1から到達可能なある世界w2において◇Aが成り立つこと、即ちw2から到達可能なある世界w3においてAが成り立つことを意味している。このとき右辺◇Aは、w1から到達可能なある世界においてAが真であることを意味する。Aが真であるのはw3であるから、これはw1からw3へ直接到達可能であることを、つまり推移的関係を意味している。)
Rが(反射的で)対称的かつ推移的(=ユークリッド的)である場合、S5に対応する。
(◇A⊃□◇Aは、w1から到達可能な一つの世界w2でAが成り立つならば、w1から到達可能な全ての世界w3で◇Aが成り立つ、つまりw2へ到達可能であるということを意味しているから、w1からw2とw3に到達可能ならw2からw3にも到達可能であるという、ユークリッド的な関係を意味している。)

拡張性 全てのw1に対してw1Rw2であるようなw2が存在する。
Rが拡張的である場合、Dに対応する。(反射的であれば拡張的であるから、DはTに含まれる。)

クリプキ・モデルとタブロー
<W, R, V>
W:対象世界w1, w2,…,wn の集合
R:Wの要素に対して定義される二項関係(=到達関係)
V:付値関数
 V(¬A, w)=1 であるのは、V(A, w)=0 の時に限る。それ以外は、V(¬A, w)=0
 V(A∧B, w)=1 であるのは、V(A, w)=1 かつ V(B, w)=1 の時に限る。それ以外は、V(A∧B, w)=0
 V(A∨B, w)=1 であるのは、V(A, w)=1 または V(B, w)=1 の時に限る。それ以外は、V(A∨B, w)=0
 V(A⊃B, w)=1 であるのは、V(A, w)=0 または V(B, w)=1 の時に限る。それ以外は、V(A⊃B, w)=0
 V(□A, w)=1 であるのは、wから到達可能なWの全ての世界でV(A, w)=1 の時に限る。それ以外は、V(□A, w)=0
 V(◇A, w)=1 であるのは、wから到達可能なWのある世界wnでV(A, wn)=1 の時に限る。それ以外は、V(◇A, w)=0

様相命題の恒真式の判別は、その式がいかなる可能な世界においても偽にならないことを示せばよい。
□P≡∀wPw
と置き換えて考えれば、述語論理と同じやり方で判別することができることが分かる。

□P
  |
(∀wPw)

Pw
◇P

(∃wPw)

Pα
¬□P

(¬∀wPw)

(∃w¬Pw)

¬Pα
¬◇P

(¬∃wPw)

(∀w¬Pw)

¬Pw

ただし、αはある特定の可能世界を表わす不確定名だから、新しい変項を代入し、分析はこちらから先に行う。
任意の可能世界を表わす自由変項のwには、上で現われている全ての到達可能な自由変項を代入する。

述語論理において主語となる個体には、それらの間には順序関係が存在しないから、全ての自由変項を代入すればよいが、
様相論理における可能世界の間には、それぞれの公理系に応じて別々の到達関係が存在するから、
T、D、B、S4 などに関しては、それらの到達関係を明記しておく必要がある。
そこで上の図に、次の到達関係を付け加える。

反射性(ρ) 対称性(σ) 推移性(τ) ユークリッド(σ&τ) 拡張性(η)
T B S4 S5 D


aRa
aRb
|
bRa
aRb
bRc

aRc
aRb
aRc

bRc
(全ての自由変項)


aRα

αは新しい文字(数字)。
一応書いておいたが、S5 では既出の全ての自由変項(世界)が到達されえるから、到達関係の表記は必要ない。
タブローも次のように表記する。
(P a は、世界aにおいてPが成り立つことを意味する。
aには、w0, w1…等と表記してもよいが、簡略化するために単に、0,1…等の数字を入れる。)

 □P a
aRb

P b
◇P a

aRα
P α
¬□P a

◇¬P a
|
aRα
¬P α
¬◇P a

□¬P a
aRb
|
¬P b

出発点(根;ルート)は、¬A 0 (世界 w0 において A は成立しない)。
同じ枝に P a と ¬P a が生じたら矛盾だから、×をつける。全ての枝に×がつけば、与式(A)は恒真式である。

例1-4

S5における □□A⊃□A S4における □A⊃□□A Bにおける □A⊃□□A Kにおける □(A⊃B)⊃(□A⊃□B)
¬(□□A⊃□A) 0
|
□□A 0
¬□A 0
0R0

◇¬A 0
|
0R1
¬A 1
1R0
1R1
|
□A 1
|
A 1
×
¬(□A⊃□□A) 0
|
□A 0
¬□□A 0
0R0

◇◇¬A 0
|
0R1
◇¬A 1
1R1

1R2
¬A 2
2R2
0R2
|
A 2
×
¬(□A⊃□□A) 0
|
□A 0
¬□□A 0
0R0

◇◇¬A 0
|
0R1
◇¬A 1
1R0
1R1

1R2
¬A 2
2R1
2R2
|
A 0
A 1
 ¬(□(A⊃B)⊃(□A⊃□B)) 0
          |
      □(A⊃B) 0
     ¬(□A⊃□B) 0
          |
         □A 0
        ¬□B 0
          |
        ◇¬B 0
          |
         0R1
         ¬B 1
          |
          A 1
          |
        A⊃B 1
        /\
      ¬A 1  B 1
       ×   ×

S4では推移性があるので□A 0と0R2からA 2が導かれ矛盾が生じる(ゆえに□A⊃□□は恒真)だが、
BではA 2が導かれず矛盾が生じない(ゆえに□A⊃□□は恒真ではない)。
よってBでは、W={ w0, w1, w2 }, w0Rw0, w0Rw1, w1Rw0, w1Rw1, w1Rw2, w2Rw1, w2Rw2, V(A, w0)=V(A, w1)=1, V(A, w2)=0
というモデルにおいて、w0 から到達できる全ての世界(w0, w1)でAは真だから、□Aは真だが、
w0 から到達できる全ての世界(w0, w1)から到達できる全ての世界(w0, w1, w2)でAは真ではない(w2でAは偽)から、□□Aは偽。
したがって、このモデルにおいて、□A⊃□□A はBで恒真ではないことが示せる。


不完全性定理

第一不完全性定理
(自然数論を含む形式的な公理系)Pにおいて、その肯定形も否定形も証明できないような式Aが存在する。
第二不完全性定理
(自然数論を含む公理系)Pが無矛盾なら、Pの無矛盾性はPにおいて証明不可能である。

2006年に岩波文庫で翻訳が出ました(大半はやや専門的な解説で、ゲーゲルの原論文は、48頁しかありません)。
ゲーデル『不完全性定理』 林 普/八杉満里子 訳・解説 岩波文庫
以前は、広瀬健・横田一正『ゲーデルの世界』(海鳴社)しかありませんでした。
付録として完全性定理と不完全性定理の両方を収録しています。それを理解できるようになるための解説が本文です。
翻訳は岩波の方が優れていますが、一般の人には、こちらの方を勧めたいような気がします。
ゲーデルではその他に、好田訳『ゲーデル 未刊哲学論考』(青土社)がありますが、訳が酷くて読めません。
その一部は、高橋昌一郎『ゲーデルの哲学』(講談社現代新書)でも詳しく紹介されていますから、
ゲーデルによる神の存在証明とか、興味がある人は、こちらを読むべきでしょう。


参考文献
論理学の一般的なテキストとしては、

野矢茂樹『論理学』(東京大学出版会)
清水義男『記号論理学』(東京大学出版会)
辺りが手に入りやすいスタンダードなものだろう。
野矢『論理学』は、初心者が必ず疑問に思うような個所を丁寧に説明しているし、
ボケ(無門)とツッコミ(道元)の役割がはっきりした対話体の記述も読みやすい。
自然演繹の証明(ゲンツェンのNK)に関しては、
前原昭二『記号論理入門』(日本評論社)
がNKを採用した定評のあるロングセラーである。

様相論理に関しては、

ヒューズ/クレスウェル『様相論理入門』(恒星社厚生閣)
が定評のある概説書だったが、現在は品切れ(絶版?)。
定評がある(あった)とは言っても、現在の視点から見ると古くなっているし、
新版(→A New Introduction to Modal Logic)の翻訳が待ち望まれている。
入手しやすいものでは、やや哲学的ではあるが、

三浦俊彦『可能世界の哲学』(NHKブックス)
飯田隆『言語哲学大全V 意味と様相(下)』(勁草書房)
非古典論理全般については、
東条敏『言語・知識・信念の論理』(オーム社)
赤松世紀・宮本定明『ソフトコンピューティングのロジック』(行学社

あるいは、命題論理限定で、英語だが、

Graham Priest, An Introduction to Non-Classical Logic, 2001, Cambridge U.P.


→例題の回答

→演繹定理
→完全性の定理
→直観主義論理
→時間論理
→多値論理

→修辞学ゼミ

→村の広場に帰る