融合原理 (Resolution Principle)

命題論理の融合原理


[定義] (融合節) 任意の二つの節 C₁ と C₂ に対して，C₁ がリテラル L を含み，C₂ がリテラル ¬L を含むとき， C₁ から L を除いたものと C₂ から ¬L を除いたも のを合わせて 融合節 (resolvent) を作るこ と．

具体例 C₁ = P ∨ Q ∨ R, C₂ = ¬Q ∨ S とすると， C₁ と C₂ の融合節は P ∨ R ∨ S である．

[定理] (融合原理と論理的帰結) 節C₁，C₂に対して，C を C₁ と C₂ の融合節とすると，C は C₁ と C₂ の 論理的帰結である．

証明

融合原理と充足不能性


C₁ も C₂ も単一節，つまり C₁ = L, C₂ = ¬L の場合，C₁ と C₂ の融合節は空節であり，与え られた節集合が充足不能(恒偽)であることを あらわす．

[定義] (演繹融合) 節集合 S に対して，次のような節の系列 C₁, C₂, ・・・, C_k を S からの C の演繹融合 (deductive resolution)という．

1. C_i は S に含まれる節であるか， C_i より前に 現れた節の融合節である．
   
2. C_k = C である．

C が空節(□で表記する)のとき，その演繹融合を S の反駁 (refutation) という．

(演習)

節集合 S = {(P ∨ Q ∨ ¬R), (P ∨ ¬Q), ¬P, R} について考え る．Sにはどのような演繹融合，もしくは反駁が存在するか?

(課題)

節集合 S = {( P ∨ R), (Q ∨ R), (¬P ∨ ¬Q ∨ R)} について考え る．Sにはどのような演繹融合，もしくは反駁が存在するか?

融合原理の完全性


融合原理は完全である．つまり，任意の充足不能な節集合に対して，有 限回のステップで空節を導くことができる．

[定理3] (充足可能性と論理的帰結)

G₁, ・・・, G_n と式 H が与えられ， G₁ ∧ ・・・ ∧ G_nが充足可能であるとき， H が G₁, ・・・, G_n の論理的帰結であるための必要 十分条件は，((G₁ ∧ ・・・ ∧ G_n) ∧ ¬H ) が恒偽 であることである．

---

(演習)

次の文章が与えられたとき，ユニコーン(unicorn: 一角獣)は架空(imaginary) の動物であることを証明できるだろうか?またユニコーンが魔法を使える (magical)ことを証明できるだろうか?さらに，角を持っていることを証明でき るだろうか? 以下の文を命題論理に翻訳し，これらを融合原理を用いて証明しなさい．

「ユニコーンが架空の動物であれば，それは不死である(immortal)．しかし， ユニコーンが架空の動物でなければ，死ぬべき(mortal)ものである．ユニコー ンが不死であるか，もしくは死ぬべきものであるならば，角を持っている (horned)．ユニコーンは角を持っていれば，魔法を使うことが出来る．」

...Return

• 講義の詳細