記号論理学

１．命題論理学

１．１命題論理とブール代数

　　命題とは，真（ True, T ）か偽（ False, F ）の値をとり，その両方を同時に値とはし得ないような言明文をいいます．例えば，

P ：雪は白い

Q ：太陽は西から昇る

などの言明文は命題となります．しかし，

R ：袋井は浜松に近い

などは，命題とはいえません．

　　一つの命題を真又は偽の値を取る変数（上に述べた例における P や Q ）とみなせば，それらを演算記号（命題論理においては，論理結合子，または，論理記号と呼ぶ）によって結合されたもの（論理式）も命題になります．一般に，命題としてそれ以上分解できない命題を原始式（原始論理式，基本命題，素命題，原始命題）と呼びます．これに対し，原始式を次のような論理結合子（論理記号）によって組み合わせて構成される命題を複合命題といいます．

～：否定

∨ ： 論理和　　G ∨ H　（ G，または，H ）

∧ ： 論理積　　G ∧ H　（ G，かつ，H ）

⇒ ：含意　　　G ⇒ H = ～G ∨ H　（もし G ならば H ）

⇔ ：同値　　　G ⇔ H = ( G ⇒ H ) ∧ ( H ⇒ G )

　　例えば，

P ：雪は白い

Q ：雪は冷たい

とすれば，P や Q は原始式，「 P ∧ Q 」は複合命題となり，複合命題の意味は，「雪は白く，かつ，雪は冷たい」となります．

　　実は，命題論理は，以下に示すような対応関係を取ると，零元 0 と単位元 1 だけからなる集合 B₂ = { 0, 1 } の上に定義されたブール代数 ( B₂ ; ＋, ・, (　) ) と同型，つまり，代数的構造が全く同じになります．

L = { False, True } = { F, T } ⇔ B₂ = { 0, 1 }

∨ （論理和） ⇔ ＋

∧ （論理積） ⇔ ・

～（否定） ⇔ (　)

　　従って，命題論理 ( L ; ∨, ∧, ～ )は，ブール代数 B₂ の定義で述べた以下に示す基本的性質をそのまま所有します．

［命題論理の基本的性質］　以下において，P，Q，R は命題であり，その取り得る値は L = { F, T } の元である．
[束の条件]

(1) 結合律
P ∨ ( Q ∨ R ) = ( P ∨ Q ) ∨ R

P ∧ ( Q ∧ R ) = ( P ∧ Q ) ∧ R

(2) 交換律
P ∨ Q = Q ∨ P

P ∧ Q = Q ∧ P

(3) 吸収律
P ∧ ( P ∨ Q ) = P

P ∨ ( P ∧ Q ) = P: P ∨ ( Q ∨ R ) = ( P ∨ Q ) ∨ R; P ∧ ( Q ∧ R ) = ( P ∧ Q ) ∧ R; P ∨ Q = Q ∨ P; P ∧ Q = Q ∧ P; P ∧ ( P ∨ Q ) = P; P ∨ ( P ∧ Q ) = P
[分配束の条件]

(4) 分配律
P ∧ ( Q ∨ R ) = ( P ∧ Q ) ∨ ( P ∧ R )

P ∨ ( Q ∧ R ) = ( P ∨ Q ) ∧ ( P ∨ R ): P ∧ ( Q ∨ R ) = ( P ∧ Q ) ∨ ( P ∧ R ); P ∨ ( Q ∧ R ) = ( P ∨ Q ) ∧ ( P ∨ R )
[ False ( F ) と True ( T ) ]

(5) False ( F ) と True ( T ) の性質
P ∨ F = P，　P ∧ F = F

P ∨ T = T，　P ∧ T = P: P ∨ F = P，　P ∧ F = F; P ∨ T = T，　P ∧ T = P
[可補束の条件]

(6) 否定の性質
P ∨ ～P = T　　排中律

P ∧ ～P = F　　矛盾律: P ∨ ～P = T　　排中律; P ∧ ～P = F　　矛盾律

　　命題論理においても，ブール代数と同様，任意の性質は，∨ と ∧，及び，F と T を入れ替えても成立します．また，上に述べた基本的性質から，以下に示すような性質を導くことができます．

二重否定律　　～～P = P
ベキ等律
P ∨ P = P

P ∧ P = P
ド・モルガン律
～ ( P ∨ Q ) = ～P ∧ ～Q

～ ( P ∧ Q ) = ～P ∨ ～Q
否定の吸収
P ∨ ( ～P ∧ Q ) = P ∨ Q

P ∧ ( ～P ∨ Q ) = P ∧ Q
対偶　　P ⇒ Q = ～Q ⇒ ～P

　　以下に，命題論理における真理値表を示しておきます．

P	Q	～P	～Q	P ∨ Q	P ∧ Q	P ⇒ Q	P ⇔ Q
F	F	T	T	F	F	T	T
F	T	T	F	T	F	T	F
T	F	F	T	T	F	F	F
T	T	F	F	T	T	T	T

　　最後に，論理式の形式的な定義を示しておきます．

［定義］　論理式（整合論理式）

(1) 原子式は論理式である

(2) G が論理式であれば，～G も論理式である

(3) G，H が論理式であれば，G ∨ H，G ∧ H，G ⇒ H，G ⇔ H も論理式である

(4) すべての論理式は上の規則から生成される

１．２論理式の解釈

［定義］　解釈
　　論理式 G が与えられ，A₁，A₂，・・・，A_n を論理式 G 中の原始式とする．このとき，G の解釈 I とは，A₁，A₂，・・・，A_n に同時に T または F とはならないように，T か F のいずれかを割り当てたものをいう．従って，論理式 G が n 個の異なった原始式によって構成されている場合は，2ⁿ 個の解釈が存在する．

　　もし，G がある解釈 I の下で T になれば，またそのときに限って，G はその解釈 I の下で真であるといいます．さもなければ，G はその解釈 I の下で偽であるといいます．例えば，論理式，

P ⇒ Q

は，解釈，I₁ = { T, F } （ P に T，Q に F を割り当てる）の下で偽，解釈，I₂ = { F, T } （ P に F，Q に T を割り当てる）の下で真になります．

［定義］　恒真と恒偽
　　ある論理式がすべての解釈のもとで真であるならば，またその時に限って，その論理式は恒真であるという．それが恒真でないとき，またその時に限って，非恒真という．また，恒真な論理式を恒真式（トートロジー）という．
　　同様に，ある論理式がすべての解釈のもとで偽であるならば，またその時に限って，その論理式は恒偽（充足不可能）であるという．それが恒偽でないとき，またその時に限って，非恒偽（充足可能）という．また，恒偽である式を恒偽式（矛盾）という．

　　以上の定義より，以下のようなことがいえます．

論理式の否定が恒偽 ⇔ 論理式が恒真
論理式の否定が恒真 ⇔ 論理式が恒偽
偽となる解釈が少なくとも 1 つ存在 ⇔ 論理式が非恒真
真となる解釈が少なくとも 1 つ存在 ⇔ 論理式が非恒偽
論理式が恒真であれば，その論理式は非恒偽（逆は成立しない）
論理式が恒偽であれば，その論理式は非恒真（逆は成立しない）

　　たとえば，以下に示す真理値表からも明らかなように，( P ⇒ Q ) ∧ ( P ∧ ～Q ) は恒偽式になります．

P	Q	P ⇒ Q	～Q	P ∧ ～Q	( P ⇒ Q ) ∧ ( P ∧ ～Q )
F	F	T	T	F	F
F	T	T	F	F	F
T	F	F	T	T	F
T	T	T	F	F	F

１．３論理式の標準形

［定義］　論理積標準形と論理和標準形
　　論理式 F が，: F = F₁ ∧ F₂ ∧ ・・・ ∧ F_n
の形で表現でき，かつ，各 F_i がリテラル（原始式又はその否定）の論理和であるとき，またそのときに限って，この形を論理積標準形（連言標準形）という．
　　論理式 F が，: F = F₁ ∨ F₂ ∨ ・・・ ∨ F_n
の形で表現でき，かつ，各 F_i がリテラルの論理積であるとき，またそのときに限って，この形を論理和標準形（選言標準形）という．

　　例えば，

F = ( P ∨ ～Q ∨ R ) ∧ ( ～P ∨ Q )

F = ( ～P ∧ Q ) ∨ ( P ∧ ～Q ∧ ～R )

は，各々，論理積標準形及び論理和標準形の例です．一般の論理式を論理積標準形や論理和標準形に変形するには，以下のようにして行います．

⇒，及び，⇔ を除去
否定記号を，二重否定やド・モルガン律を使用して原始式の直前に移動
分配律等を利用して変形

１．４論理的帰結と推論

　　推論とは，事実及び事実間の関係を記述した規則を使用して，知識として明示されていない事実を引き出すことです．例えば，

三郎の父は次郎である．

次郎の父は太郎である．

父の父は祖父である．

といった事実から，「三郎の祖父は太郎である」といった事実を引き出すことが推論です．推論には，様々な方法が存在しますが，ここでは演繹推論について検討します．

［定義］　論理的帰結
　　論理式 F₁，F₂，・・・，F_n と論理式 G が与えられた時，もし，F₁ ∧ F₂ ∧ ・・・ ∧ F_n が真となるすべての解釈 I のもとで，G もまた真となるとき，またその時に限って，G を F₁，F₂，・・・，F_n の論理的帰結と呼ぶ．このとき F₁，F₂，・・・，F_n を G の公理（仮定，前提），G を定理と呼ぶ．また，G は論理式 F₁，F₂，・・・，F_n から演繹可能であるともいい，: F₁，F₂，・・・，F_n |- G
とかく．

　　実際に命題論理において推論を実行するためには，次の定理が重要です（証明は省略します）．

［定理］　演繹定理
　　論理式 F₁，F₂，・・・，F_n と G が与えられたとき，G が F₁，F₂，・・・，F_n の論理的帰結であることと，論理式 F₁ ∧ F₂ ∧ ・・・ ∧ F_n ⇒ G が恒真であることとは同値である．
　　論理式 F₁，F₂，・・・，F_n と G が与えられたとき，G が F₁，F₂，・・・，F_n の論理的帰結であることと，論理式 F₁ ∧ F₂ ∧ ・・・ ∧ F_n ∧ ～G が恒偽であることとは同値である．

　　我々が日常行っている推論方法には，否定式，肯定式，三段論法などが存在します．以下に示すように，これらの推論方法を命題論理によって記述することができます．

否定式

　　P ⇒ Q という事実と～Q という事実から，～P という事実を導き出す推論方法です．例えば，P，Q を，

P ：人間である

Q ：生物である

のような命題としたとき，

P ⇒ Q　　人間であれば生物である

～Q　　生物でない

から，

～P　　人間でない

を演繹（推論）することになります．

　　ここでは，日常行っているこの推論方法が正しいか否かを調べてみます．この推論方法が正しいことを証明するには，～P が，P ⇒ Q，～Q の論理的帰結であること，つまり，

P ⇒ Q，～Q |- ～P

であることを示せばよいことになります．最初に，論理的帰結の定義に基づいて考えてみます．そこで，関連する項目に対する真理値表を作成すると，以下のようになります．明らかに，( P ⇒ Q ) ∧ ～Q が真となるすべての解釈 I （この例の場合は，P が F，Q が F の場合だけ）のもとで，～P もまた真となっていますので，～P は，P ⇒ Q，～Q の論理的帰結であるといえます．

P	Q	P ⇒ Q	～Q	( P ⇒ Q ) ∧ ～Q	～P
F	F	T	T	T	T
F	T	T	F	F	T
T	F	F	T	F	F
T	T	T	F	F	F

　　次に，演繹定理を使用して証明してみます．つまり，

( ( P ⇒ Q ) ∧ ～Q ) ⇒ ～P

が恒真であることをいえばよいわけです．その方法としては 2 つあります．一つは真理値表を利用する方法であり，他の一つは論理式の変形による方法です．まず，真理値表を作成すると下に示すようになり，恒真であることは明らかです．

P	Q	P ⇒ Q	～Q	P ⇒ Q ∧ ～Q	～P	( ( P ⇒ Q ) ∧ ～Q ) ⇒ ～P
F	F	T	T	T	T	T
F	T	T	F	F	T	T
T	F	F	T	F	F	T
T	T	T	F	F	F	T

　　次に，論理式を変形し，( ( P ⇒ Q ) ∧ ～Q ) ⇒ ～P が恒真であることを証明してみます．

( ( P ⇒ Q ) ∧ ～Q ) ⇒ ～P

　　　= ～( ( P ⇒ Q ) ∧ ～Q ) ∨ ～P

　　　= ～( ( ～P ∨ Q ) ∧ ～Q ) ∨ ～P

　　　= ～( ( ～P ∧ ～Q ) ∨ ( Q ∧ ～Q ) ) ∨ ～P

　　　= ～( ( ～P ∧ ～Q ) ∨ F ) ∨ ～P

　　　= ～( ～P ∧ ～Q ) ∨ ～P

　　　= P ∨ Q ∨ ～P

　　　= T ∨ Q

　　　= T

　　同様に，( P ⇒ Q ) ∧ ～Q ∧ ～～P の恒偽性によっても証明可能です．

( P ⇒ Q ) ∧ ～Q ∧ ～～P

　　　= ( P ⇒ Q ) ∧ ～Q ∧ P

　　　= ( ～P ∨ Q ) ∧ ～Q ∧ P

　　　= ( ( ～P ∧ ～Q ) ∨ ( Q ∧ ～Q ) ) ∧ P

　　　= ( ( ～P ∧ ～Q ) ∨ F ) ∧ P

　　　= ～P ∧ ～Q ∧ P

　　　= F ∧ ～Q

　　　= F

肯定式

　　P ⇒ Q という事実と P という事実から，Q という事実を導き出す推論方法です．例えば，P，Q を，

P ：晴天である
Q ：遠足にいく

のような命題としたとき，

P ⇒ Q　　晴天であれば遠足にいく
P　　晴天である

から，

Q　　遠足にいく

を演繹（推論）することになります．
三段論法

　　P ⇒ Q という事実と Q ⇒ R という事実から，P ⇒ R という事実を導き出す推論方法です．例えば，P，Q，R を，

P ：人間である
Q ：生物である
R ：死ぬべき存在である

のような命題としたとき，

P ⇒ Q　　人間であれば生物である
Q ⇒ R　　生物であれば死ぬ

から，

P ⇒ R　　人間であれば死ぬ

を演繹（推論）することになります．

２．述語論理学

２．１述語論理

　　例えば，次に示すような 2 つの事実，

P ：すべての人間は死すべき存在である

Q ：太郎は人間である

から，

R ：太郎は死すべき存在である

を，命題論理の範囲で推論可能でしょうか．つまり，R が P，Q の論理的帰結であることを証明できるでしょうか．これを証明するためには，例えば，

P ∧ Q ⇒ R

が恒真であることを証明する必要があります．しかしながら，これは不可能です．明らかに正しい推論であるにもかかわらず，なぜそれを証明することが不可能なのでしょうか．その大きな原因は，「命題論理では，個々の命題の内部構造を取り扱えない」点にあります．例えば，

x は 3 より大きい

といった言明文は，x の値によって真偽が変化します．従って，言明文の内部に立ち入った処理が必要になります．例えば，先の例では，「すべての」という部分を解釈する必要があります．それを可能にするのがこれから述べる述語論理です．まず，次に示す述語論理における論理式の例に基づきながら，基本的な用語の定義を行っていきます．

GREATER ( x, 3, )　　x は 3 より大きい

GREATER ( plus ( x, 1 ), x )　　x + 1 は x より大きい

LOVE( mother ( Taro ), Taro )　　Taro の母は Taro を愛している

［定義］　定数記号，変数記号，関数記号，及び，述語記号: 定数記号 ：事物の名前（ Taro，3 ）; 変数記号 ：小文字で示す（ x ）; 関数記号 ：小文字で示す（ mother，plus ）．特に，n 個の引き数を持つ関数記号を n-変数関数記号という; 述語記号 ：大文字で示す（ GREATER，LOVE ）．述語は，定数のリストを T （ True ）または F （ False ）へ写像する写像である．特に，n 個の引き数を持つ述語記号を n-変数述語記号という．

　　次に，項について定義し，続いて，述語論理における原始式の定義を行います．

［定義］　項

(1) 定数は項である

(2) 変数は項である

(3) f が n-変数関数記号，t₁，･･･，t_n が項であれば，f ( t₁，･･･，t_n ) は項である

(4) すべての項は上の規則によって生成される

［定義］　原始式: 　　P を n-変数述語記号，t₁，･･･，t_n を項とすると，P ( t₁，･･･，t_n ) は原子式である．また，原子式あるいは原子式の否定をリテラルという．

　　述語論理においても，命題論理と同様，原始式を次のような論理結合子によって組み合わせて新たな論理式を構成することが可能です．

～：否定

∨ ： 論理和　　G ∨ H　（ G，または，H ）

∧ ： 論理積　　G ∧ H　（ G，かつ，H ）

⇒ ：含意　　　G ⇒ H = ～G ∨ H　（もし G ならば H ）

⇔ ：同値　　　G ⇔ H = ( G ⇒ H ) ∧ ( H ⇒ G )

さらに，述語論理においては，以下に示すような限定記号を使用することができます．

∀ ： 全称記号　　　すべての～について

∃ ： 存在記号　　　ある～が存在して

　　例えば，

Q ( x ) ： x は有理数である

R ( x ) ： x は実数である

P ( x ) ： x は素数である

LESS ( x, y ) ： x は y より小さい

としたとき，以下のように使用します．

すべての x に対して，x が有理数であれば，x は実数である
(∀x) ( Q ( x ) ⇒ R ( x ) )
素数であるような数が存在する
(∃x) P ( x )
すべての数 x に対して x < y であるような数 y が存在する
(∀x) (∃y) LESS ( x, y )

　　論理式中の変数の出現は，その出現が限定記号の出現範囲内であるか，あるいは，限定記号と共に使われているならば，その出現は束縛されているといい，その変数を束縛変数といいます．逆に，束縛されていなければ，その出現は自由であるといい，その変数を自由変数といいます．

　　一般に，限定記号は，変数に対してだけでなく，例えば，

すべての x に対し，ある述語 G が存在する　　　(∀x) (∃G) G ( x )

などのように，述語に対しても使用可能です．しかしながら，このような論理体系（高階述語論理）に対しては完全な演繹体系が確立していません．そこで，以下においては，変数だけに対して限定記号を利用できる第 1 階述語論理だけを取り扱っていきます．以上説明した点に基づき，最後に，第 1 階述語論理における論理式に対する形式的な定義を与えておきます．

［定義］　整合論理式（論理式）

(1) 原子式は論理式である

(2) F，G が論理式であれば，～F，F ∧ G，F ∨ G，F ⇒ G，F ⇔ G も論理式である

(3) F が論理式で，かつ，x が F 中の自由変数であれば，(∀x) F，(∃x) F も論理式である

(4) すべての論理式は上の規則から生成される

　　原始式，及び，論理式の定義より，引数のない述語，又は，すべての引数が定数である述語は，命題論理の論理式に一致します．従って，述語論理は，命題論理を含んだ拡張であるといえます．

２．２論理式の解釈

　　第 1 階述語論理における解釈は，以下に示すように，限定記号などの存在のため，命題論理の場合よりかなり面倒なものになります．

［定義］　論理式の解釈
第 1 階述語論理における論理式 F の（ D 上での）解釈は，空でない定義域 D と，F 中の定数，関数記号，述語記号の各々に対する値の割り当てからなる．ここで，値の割り当ては次のようにして行う． (1) 各定数に対して D の要素を割り当てる (2) 各 n-変数関数記号に対して Dⁿ から D への写像を割り当てる．ただし，Dⁿ = { ( x₁，･･･，x_n ) ｜ x_i ∈ D } とする (3) 各 n-変数述語記号に対して Dⁿ から { T, F } への写像を割り当てる
定義域 D 上の論理式の解釈において，論理式の真理値は，次の規則に従って，T あるいは F に決定される． (1) (∀x) G は，G の真理値が D のすべての要素 x について T であれば，T となる．さもなければ，F となる． (2) (∃x) G は，G の真理値が D の少なくとも 1 つの要素 x について T であれば，T となる．さもなければ，F となる．

　　例えば，解釈 I，

定義域： D = { 1, 2 }

P への割り当て　　P( 1 )：T，　P( 2 )：F

のもとで，

(∀x) P( x )，及び，(∃x) ～P( x )

の真理値を決定すると以下のようになります．

P ( x ) は，D のすべての要素に対しては T でないので，解釈 I のもとで，(∀x) P ( x ) は F となる
～P ( 2 ) が T となるので，解釈 I のもとで，(∃x) ～P( x ) は T となる

　　論理式の解釈に基づき，命題論理の場合と同様，恒真，恒偽，論理的帰結などの概念を定義することができます．

［定義］　恒偽と恒真
　　G が T となる解釈 I が存在するならば，またその時に限り，論理式 G は非恒偽（充足可能）であるという．また，解釈 I のもとで G が T となるとき，I を G のモデルと呼び，I は G を充足するという．また，G を充足する解釈が存在しないならば，またその時に限り，論理式 G は恒偽（充足不可能）であるという．
　　G のすべての解釈が G を充足するならば，またその時に限り，論理式 G は恒真であるという．

［定義］　論理的帰結
　　すべての解釈 I について，F₁ ∧ F₂ ∧ ・・・ ∧ F_n が I のもとで真であれば，G もまた I のもとで真となるとき，またその時に限り，論理式 G を F₁，F₂，・・・，F_n の論理的帰結であるという．

　　ここで，述語論理の最初に挙げた例を第 1 階述語論理で表現し，推論結果の正当性を示してみます．2 つの述語，

MAN ( x ) ： x は人間である

MORTAL ( x ) ：　x は死すべき存在である

を定義することによって，各記述は以下に示すような論理式によって表現することができます．

P ： (∀x) ( MAN ( x ) ⇒ MORTAL ( x ) )　　　すべての人間は死すべき存在である

Q ： MAN ( 太郎 )　　　太郎は人間である

R ： MORTAL ( 太郎 )　　　太郎は死すべき存在である

　　従って，R が P，Q の論理的帰結であること，つまり，P ∧ Q が真であるすべての解釈に対して，R が真になることを証明すればよいわけです．まず，P ∧ Q がある解釈 I において真であったとします．このとき，論理積の定義より，解釈 I のもとで P 及び Q も真でなければなりません．

　　P は，その定義より，すべての x に対して真であるため，当然，太郎に対しても真，つまり，

MAN ( 太郎 ) ⇒ MORTAL ( 太郎 )

　　　= ～MAN ( 太郎 ) ∨ MORTAL ( 太郎 )

が真である必要があります．この式において，Q が真であるため，～MAN ( 太郎 ) は偽となります．従って，MORTAL ( 太郎 )，つまり，R は，解釈 I のもとで真となる必要があります．

２．３論理式の標準形

　　推論を行う場合，論理的帰結の定義に基づいて行えば可能なわけですが，一般的には，かなり面倒な作業となります．命題論理においては，演繹定理を利用しましたが，述語論理においては，後に述べる導出原理がよく利用されます．導出原理を利用するに当たり，論理式を適切な標準形に変換しておく必要がありますので，ここでは，標準形について述べます．

２．３．１冠頭標準形

［定義］　冠頭標準形
　　第 1 階述語論理式 F は，もし論理式が: (Q₁) ･･･ (Q_n) ( M )
の形をしているならば，またそのときに限って，冠頭標準形であるという．ただし，(Q_i) は，(∀x_i) または (∃x_i) を表し，また，M は限定記号を含まない論理式である．このとき，(Q₁) ･･･ (Q_n) を前置部，また，M を母式という．

　　一般の論理式を冠頭標準形に変形するためには，論理式に対する以下に示すような性質を利用します．

［述語論理の性質］

(1) 交換律
P ∨ Q = Q ∨ P

P ∧ Q = Q ∧ P

(2) 否定の性質
P ∨ ～P = T　　排中律

P ∧ ～P = F　　矛盾律

～～P = P

(3) 真偽の性質
P ∨ F = P，　P ∧ F = F

P ∨ T = T，　P ∧ T = P

(4) 結合律
P ∨ ( Q ∨ R ) = ( P ∨ Q ) ∨ R

P ∧ ( Q ∧ R ) = ( P ∧ Q ) ∧ R

(5) ベキ等律
P ∨ P = P

P ∧ P = P

(6) 分配律
P ∧ ( Q ∨ R ) = ( P ∧ Q ) ∨ ( P ∧ R )

P ∨ ( Q ∧ R ) = ( P ∨ Q ) ∧ ( P ∨ R )

(7) ド・モルガン律
～ ( P ∨ Q ) = ～P ∧ ～Q

～ ( P ∧ Q ) = ～P ∨ ～Q

(8) 否定記号の移動
～( (∀x) F ( x ) ) = (∃x) ( ～F ( x ) )

～( (∃x) F ( x ) ) = (∀x) ( ～F ( x ) )

(9) 限定記号の移動
(Qx) F ( x ) ∨ G = (Qx) ( F ( x ) ∨ G )

(Qx) F ( x ) ∧ G = (Qx) ( F ( x ) ∧ G )

(10) 限定記号に対する分配律
(∀x) F ( x ) ∧ (∀x) H ( x ) = (∀x) ( F ( x ) ∧ H ( x ) )

(∃x) F ( x ) ∨ (∃x) H ( x ) = (∃x) ( F ( x ) ∨ H ( x ) )

(11) 変数の置き換え
(Q₁x) F ( x ) ∨ (Q₂x) H ( x ) = (Q₁x) (Q₂z) ( F ( x ) ∨ H ( z ) )

(Q₃x) F ( x ) ∧ (Q₄x) H ( x ) = (Q₃x) (Q₄z) ( F ( x ) ∧ H ( z ) ): P ∨ Q = Q ∨ P; P ∧ Q = Q ∧ P; P ∨ ～P = T　　排中律; P ∧ ～P = F　　矛盾律; ～～P = P; P ∨ F = P，　P ∧ F = F; P ∨ T = T，　P ∧ T = P; P ∨ ( Q ∨ R ) = ( P ∨ Q ) ∨ R; P ∧ ( Q ∧ R ) = ( P ∧ Q ) ∧ R; P ∨ P = P; P ∧ P = P; P ∧ ( Q ∨ R ) = ( P ∧ Q ) ∨ ( P ∧ R ); P ∨ ( Q ∧ R ) = ( P ∨ Q ) ∧ ( P ∨ R ); ～ ( P ∨ Q ) = ～P ∧ ～Q; ～ ( P ∧ Q ) = ～P ∨ ～Q; ～( (∀x) F ( x ) ) = (∃x) ( ～F ( x ) ); ～( (∃x) F ( x ) ) = (∀x) ( ～F ( x ) ); (Qx) F ( x ) ∨ G = (Qx) ( F ( x ) ∨ G ); (Qx) F ( x ) ∧ G = (Qx) ( F ( x ) ∧ G ); (∀x) F ( x ) ∧ (∀x) H ( x ) = (∀x) ( F ( x ) ∧ H ( x ) ); (∃x) F ( x ) ∨ (∃x) H ( x ) = (∃x) ( F ( x ) ∨ H ( x ) ); (Q₁x) F ( x ) ∨ (Q₂x) H ( x ) = (Q₁x) (Q₂z) ( F ( x ) ∨ H ( z ) ); (Q₃x) F ( x ) ∧ (Q₄x) H ( x ) = (Q₃x) (Q₄z) ( F ( x ) ∧ H ( z ) )

　　性質の最後に述べた変数の置き換えがなぜ必要なのでしょうか．それは，以下に示すような限定記号の分配律が成立しないからです．

(∀x) F ( x ) ∨ (∀x) H ( x ) ≠ (∀x) ( F ( x ) ∨ H ( x ) )　　(1)

(∃x) F ( x ) ∧ (∃x) H ( x ) ≠ (∃x) ( F ( x ) ∧ H ( x ) )　　(2)

　　(1) 式の右辺は，すべての x に対して，F ( x )，または，H ( x ) が真になることを意味しています．しかし，左辺は，必ずしもすべての x に対して，F ( x )，または，H ( x ) が真にならなくても真になります．また，(2) 式の右辺は，ある x に対し，常に，F ( x ) = H ( x ) = T ですが，左辺は，F ( x ) = T となる x と，H ( x ) = T となる x が異なっても構いません．そこで，F ( x ) にはない変数 z を選び，

(∀x) F ( x ) ∨ (∀x) H ( x ) = (∀x) F ( x ) ∨ (∀z) H ( z )

　　　 = (∀x) (∀z) ( F ( x ) ∨ H ( z ) )

(∃x) F ( x ) ∧ (∃x) H ( x ) = (∃x) F ( x ) ∧ (∃z) H ( x )

　　　 = (∃x) (∃z) ( F ( x ) ∧ H ( x ) )

のような変形を行う必要が出てきます．

　　上に述べた性質を利用し，冠頭標準形に変換する手続きをまとめると以下のようになります．

［冠頭標準形への変換手続き］

(1) 論理結合子 ⇔，⇒ を消去

(2) 否定記号を原子式の直前まで移動する（性質 (7) と (8) ）

(3) 必要な箇所の変数名の変更

(4) 限定記号の移動（性質 (9) ～ (11) ）

　　以下に，冠頭標準形への変換例を示します．

(∀x) P ( x ) ⇒ (∃x) Q ( x )

　　　 = ～( (∀x) P ( x ) ) ∨ (∃x) Q ( x )

　　　 = (∃x) ( ～P ( x ) ) ∨ (∃x) Q ( x )

　　　 = (∃x) ( ～P ( x ) ∨ Q ( x ) )

２．３．２節形式

［定義］　節形式
　　節とは，リテラルの論理和（選言）である．また，r 個のリテラルからなる節を r-リテラル節と呼ぶ．特に，1-リテラル節を単位節と呼び，リテラルを一つも含まない節を空節（ □，nil ）と呼ぶ．空節は，解釈によって真となるリテラルを含まないので，常に偽であるような節である．
　　第 1 階述語論理式 F は，もし論理式が: (∀x₁) ･･･ (∀x_n) ( C₁ ∧ ･･･ ∧ Ｃ_m )
の形をしているならば，またそのときに限って，節形式（スコーレム標準形，標準形）であるという．ただし，C_i は節を表し，これらの節の集合 S = { C₁，･･･，C_m } を節集合と呼ぶ．

　　一般に，論理式は，節形式に変換可能です．その変換方法は以下に示すとおりです．

［節形式への変換方法］

(1) 冠頭標準形に変換

(2) 母式を論理積標準形に変換

(3) 恒偽性を変えること無く，以下に示す方法によって，存在記号を除去（存在記号を Q_r とする）

Q_r より左に全称記号がないなら，母式に現れない新しい定数 c をとり，母式中のすべての x_r を c で置き換え，Q_rx_r を消去する．

Q_s1，･･･，Q_sm が Q_r より左にある全称記号であるときには，母式ですでに使用されている関数記号以外の新しい m-変数関数記号 f をとり，母式に現れるすべての x_r を f ( x_s1，･･･，x_sm ) で置き換え，Q_rx_r を消去する．例えば，(∀x) (∃y) P ( x, y ) は，いかなる x に対しても，もし x が決まれば P ( x, y ) を満足する y が存在することを意味している．従って，y は x の関数とみなすことができる．このように，存在記号を消去するために使用される定数や関数を，スコーレム関数という．

　　例として，

(∀x) (∃y) (∃z) ( ( ～P ( x, y ) ∧ Q ( x, z ) ) ∨ R ( x, y, z ) )

を節形式に変換してみます．まず，母式を論理積標準形に変換します．

　　 = (∀x) (∃y) (∃z) ( ( ～P ( x, y ) ∨ R ( x, y, z ) ) ∧ ( Q ( x, z ) ) ∨ R ( x, y, z ) ) )

次に，存在記号を消去するために，y，z を f ( x )，g ( x ) に置き換えます．節集合は，下線を引いた 2 つの節から構成されることになります．

　　 = (∀x) ( ( ～P ( x, f ( x ) ) ∨ R ( x, f ( x ), g ( x ) ) ) ∧ ( Q ( x, g ( x ) ) ) ∨ R ( x, f ( x ), g ( x ) ) ) )

２．４導出原理

［定義］　導出原理
　　任意の 2 つの節 C₁，C₂ に対して，もし C₁ のリテラル L₁ が C₂ のリテラル L₂ と相補対（原始式とその否定の対）になっているならば，C₁ および C₂ からそれぞれ L₁ および L₂ を消去し，残った節の論理和を作る．この新たに作られた節を C₁ と C₂ からの導出形という．

　　例えば，

C₁ = ～P ∨ Q ∨ R，　C₂ = ～Q ∨ S

の導出形は以下のようになります．

～P ∨ R ∨ S

［定理］　2 つの節 C₁ および C₂ が与えられたとき，C₁ と C₂ とからの導出形 C は，C₁，C₂ の論理的帰結になっている．

［定理］　論理式 P の節形式を表す節集合を S とすると，P が恒偽であることと，集合 S が恒偽であることとは同値である．

　　導出原理と上の 2 つの定理を利用して，演繹定理と似たような方法によって推論（定理の証明）を行うことができます．その具体的な方法は以下に示すとおりです．

［導出原理による定理の証明］

(1) 公理の集合 F をすべて，節形式に変換する（ S ：節集合とする）．

(2) 定理 P の否定を作り，それを節形式に変換する．その結果を，ⅰ で得られた節集合 S に加える．定理を否定したものと，公理とは同時に成り立たない．従って，定理の否定と公理を合わせたものからは矛盾が導かれるはずである．

(3) 矛盾が発見されるか，または，先に進まなくなるまで以下の操作を繰り返す．

任意の二つの節を選び親節とする．

親節から導出形を導き出す．

もし，導出形が空節であれば，証明されたことになる．さもなければ，得られた導出形を節集合 S に加え，a に戻る．

　　先に，相補対を見つけ，導出形を求める例を示しましたが，一般に，述語論理においては，変数が存在するためそのままでは相補対が存在しない場合が多くあります．例えば，2 つの節，

C₁ ： P ( x ) ∨ Q ( x )

C₂ ：～P ( f ( x ) ) ∨ R ( x )

の間には，このままでは，相補対は存在しません．そこで，変数に対して代入という操作を行い（各節には，全称記号が付加されているため可能），相補対を作り出していきます．この例の場合，C₁ の x に f ( a )，C₂ の x に a を代入すると，以下のようになり，導出形を求めることができます．

C₁' ： P ( f ( a ) ) ∨ Q ( f ( a ) )

C₂' ：～P ( f ( a ) ) ∨ R ( a )

導出形 C₃ ： Q ( f ( a ) ) ∨ R ( a )

　　一般に，代入を行う方法は一意ではありません．例えば，C₁ の x に f ( x ) を代入することによっても，以下に示すように，導出形を求めることができます．

C₁" ： P ( f ( x ) ) ∨ Q ( f ( x ) )

C₂ ：～P ( f ( x ) ) ∨ R ( x )

導出形 C₃ ： Q ( f ( x ) ) ∨ R ( x )

　　次に，いくつかの例を導出原理を利用して証明してみます．まず最初に，命題論理で行った否定式による推論の正しさを導出原理を使用して証明してみます．否定式は，P，Q を，

P ：人間である

Q ：生物である

のような命題としたとき，公理，

P ⇒ Q　　人間であれば生物である

～Q　　生物でない

から，定理，

～P　　人間でない

を導こうとするものです．この場合，公理の集合を節形式に変換し，かつ，定理の否定をその節集合に加えると，節集合 S は以下に示す 3 つの節から構成されます．

(1) P ⇒ Q = ～P ∨ Q
(2) ～Q
(3) P　　　定理の否定

　　この結果，以下のようにして導出形が得られ，最終的に空節となり，証明が完了します．以前述べた証明方法に比較して，非常に簡単になっていることが分かるかと思います．

(4) Q　　　(1) と (3)
(5) nil　　　(2) と (4)

　　次に，述語論理の最初に挙げた例を，導出原理によって証明してみます．この例では，2 つの述語，

MAN ( x ) ： x は人間である

MORTAL ( x ) ：　x は死すべき存在である

を定義し，公理，

(∀x) ( MAN ( x ) ⇒ MORTAL ( x ) )　　　すべての人間は死すべき存在である

MAN ( 太郎 )　　　太郎は人間である

の下で，定理，

MORTAL ( 太郎 )　　　太郎は死すべき存在である

を証明することになります．先の例と同様に，公理の集合を節形式に変換し，かつ，定理の否定をその節集合に加えると，節集合 S は以下に示す 3 つの節から構成されます．

(1) ～MAN ( x ) ∨ MORTAL ( x )
(2) MAN ( 太郎 )
(3) ～MORTAL ( 太郎 )　　　定理の否定

　　この結果，以下のようにして導出形が得られ，最終的に空節となり，証明が完了します．

(4) MORTAL ( 太郎 )　　　(1) と (2) （ x に太郎を代入)
(5) nil　　　(3) と (4)