4.論理による知識表現

2.論理表現の基礎知識
命題論理(Propositional Calculus)
と
述語論理(Predicate Calculus)
2.1 命題論理 (Propositional Calculus)
基本単位:意味のある言明→命題
↓
(通常、自然言語の1文に相当)
命題が真か偽かのみ
に言及する
命題自身を更に分析
することはしない。
真理値
真 : True
T
1
偽 : False
F
0
命題に関する演算
反対命題
~P : Pではない
(例)
P
: 徳川綱吉は戌年生ま
れである。
~P : 徳川綱吉は戌年生ま
れでない。
真理値表
P
~P
0
1
1
0
複合命題
連結詞によって複数の命題をつなぐ
P∩Q P かつ Q
P∪Q
P または Q
P→Q P ならば Q
P≡Q P と Q は等価
P
P
if
P
and Q
or Q
P then Q
equal Q
(P→Q かつ Q→P)
P/Q
P さもなくば Q
P exclusive Or Q
表記法のバラエティ
•
•
•
•
∩,∧,&
∪,∨,|
⊃,→
≡,=
• /,∨
連言,論理積, And,かつ
選言,論理和, Or,または
含意,Implies,ならば
等価,同値,
Equivalence,のときだけ
排他的論理和,
Exclusive Or, さもなくば
自然言語の連結詞の不確かさ
そして、および、または、ならびに、もしくは…
そして ∩ →
および ∩ ∪ (ならびに)
または ∪ / (もしくは)
不確かさの例
{この家は、駅に近く、そして日当りが良い}
∩の意味
{太郎は悪戯をした。そして母親に叱られた}
∩ではなく、→
{法律および政令には全て主任の国務大臣が署名する}
法律 ∪ 政令には、全て主任の国務大臣が署名する
{明日、雨天または強風ならば、花見中止}
雨天であり、強風のとき、花見は中止
{優勝者には、車1台または賞金200万円が贈られる}
車1台かつ賞金200万円が贈られることはない
複合命題の真理値表
P
1
1
0
0
Q
1
0
1
0
P∩Q
1
0
0
0
P∪Q
1
1
1
0
P→Q
1
0
1
1
P
1
1
0
0
Q
1
0
1
0
~P
0
0
1
1
~P∪Q
1
0
1
1
P→Q
1
0
1
1
P≡Q
1
0
0
1
P/Q
0
1
1
0
比較
P→Q≡~P∪Q
演習
任意の演算のうち適当な2種類で他を定義でき
ることを真理値表で確かめよ。
(ヒント:以下は~と∩で他演算を定義している式の展開である)
A∪B : ~(~A∩~B)
A≡B : (A→B)∩(B→A)
シェファー(Sheffer)の棒(↑)
P↑Q≡~(P∩Q)
~P
P∩Q
P∪Q
P→Q
P≡Q
P/Q
:
:
:
:
:
:
P↑P
(P↑Q)↑(P↑Q)
(P↑P)↑(Q↑Q)
P↑(Q↑Q)
(P↑Q)↑{ (P↑P)↑(Q↑Q)}
{P↑(Q↑Q)}↑{Q↑(P↑P)}
シェファー(Sheffer)の棒(↓)
P↓Q≡~(P∩Q)
~P
P∩Q
P∪Q
P→Q
P≡Q
P/Q
:
:
:
:
:
:
P↓P
(P↓P)↓(Q↓Q)
(P↓Q)↓(P↓Q)
{(P↓P)↓Q}↓{(P↓P)↓Q)}
{P↓(Q↓Q)}↓{Q↓(P↓P)}
(P↓Q)↓{ (P↓P)↓(Q↓Q)}
演習
① シェファーの2つの棒(↓,↑)での∩と∪、
および≡と/の演算を比較せよ。
② 適当なひとつの演算を選び、真理値表で確
認せよ。
命題論理とブール代数との対比
U :全体集合
A,B,CがUの部分集合であるとき
許される
U
許されない
U
A
A
命題論理とブール代数との考え方の違い
命題論理 ブール代数
基本単位 命題
演算
集合
T
全体集合U
F
空集合Φ
(なし)
部分集合
∩(連言)
∩(共通部分集合)
∪(選言)
∪(合併集合)
~(否定) ~(補集合)
→(含意) ⊂(部分集合)
A∪B
A
~A
A
A∩B
B
A
B
A⊂B
A
(A → B と A ⊂ B
の関係について注
意)
B
論理型知識での推論規則
(式の変形で行われる)
変形方法:書き換え規則
(基本)
(交換律)
(分配律:連結詞が異なる)
0 ∩ P
≡ 0
P ∩ Q ≡
Q ∩ P
0 ∪ P
≡ P
P ∪ Q ≡
Q ∪ P
1 ∩ P
≡ P
(結合律:連結詞が同じ)
1 ∪ P
≡ 1
P ∩ (Q ∩ R)
P ∩ ~P ≡ 0
P ∪ ~P ≡ 1
~(~P)
≡ P
(巾等律)
P ∩ P
≡ P
P ∪ P
≡ P
≡
(P ∩ Q) ∩ R
P ∩ (Q ∩ R)
≡
(P ∩ Q) ∩ R
P ∩ (Q ∪ R)
≡
(P ∩ Q) ∪ (P ∩ R)
P ∪ (Q ∩ R)
≡
(P ∪ Q) ∩ (P ∪ R)
(ド・モルガンの補助定理)
P ∩ (~P ∩ Q)
≡
0
P ∪ (~P ∩ Q)
≡
1
(吸収律)
(ド・モルガンの定理)
P ∩ (P ∪ Q)
~(P ∪ Q) ≡
(~P) ∩ (~Q)
~(P ∩ Q) ≡
(~P) ∪ (~Q)
≡
P ∪ (P ∩ Q)
ド・モルガンの定理を真理値表で確認
P
1
1
0
0
Q ~P ~Q
1
0
0
0
0
1
1
1
0
0
1
1
P∩Q
1
0
0
0
~(P∩Q)
0
1
1
1
(~P)∪(~Q)
0
1
1
1
[演習]
真理値表により、~(P∪Q)と(~P)∩(~Q)が等価であることを
確認せよ。
式の書き換え例
(例1)
~(P∪Q)→(~P)∩(~Q)
~(~(P∪Q))∪((~P)∩(~Q))
(P∪Q)∪((~P)∩(~Q))
分配律から
((P∪Q)∪(~P))∩((P∪Q)∪(~Q))
((~P∪P)∪Q)∩(P∪(Q∪~Q))
↓
↓
1
1
(1∪Q) ∩ (P∪1)
1 ∩ 1 ≡ 1
(例2)
~(P∩Q)→(~P)∪(~Q)
~(~(P∩Q))∪((~P)∪(~Q))
(P∩Q)∪((~P)∪(~Q))
結合律から
((P∩Q)∪(~P))∪(~Q)
((~P∪P)∩Q)∩(~Q))
↓
1
(1∩Q) ∩ (~Q)
Q ∩ ~Q ≡ 1
2.2 論理型知識の内容と利用の概要
• 知識の格納
知識の妥当性、矛盾のなさ
• 推論
既に格納されている知識を利用して他の
結論を導く。
結論の評価 = 根拠となる主張の適切さ + 導出の適切さ
根拠となる主張の適切さ
= 命題そのもの
知識ベースの内容
導出の適切さ
= 推論の実行
推論エンジンの機能
根拠となる主張の適切さ
(1)意味規定
①辞書的規定
: 一般に認められている意味規定
②一時的規定
: 与えられた状況に限定した一時的な意味規定
③提案的規定
: 辞書的規定に替わる一般的意味規定の提案
(2)事実認識
①個別的主張
: 個々の事実を示す主張
②一般的主張
: 一般的な事柄に対する主張
A:一般化に関する主張
B:法則の主張
C:存在の主張
(3)価値評価
: 価値・規範を共有している相手との間での価値・規範の評価
①良悪・善悪評価
②選択的評価
根拠の例
(1)意味規定
①辞書的規定
: 海藻は海の植物である。
②一時的規定
: ここでは、ソフトウェア科学は自然科学に含めないこととする。
③提案的規定
: 「善悪」とは、結局社会に受け入れられる行為であるかどうかで
ある。
(2)事実認識
①個別的主張
: 「Prologの技芸」の著作者はShapiroである。
②一般的主張
A:一般化の主張
: 関西の人は、納豆嫌いである。
B:法則の主張
: 酒を呑んで山に入ると、やぶ蚊に刺される。
C:存在の主張
: この山のどこかに、大鷲が棲んでいるはずだ。
(3)価値評価
①良悪・善悪評価
: このワインはとても美味しい。
②行動の選択的評価 : 夏休みには、ぜひ海に行くべきだ。
根拠の確認
(1)意味規定
①辞書的規定
: 一般的に認められている意味かどうかを確認
②一時的規定
: その状況の中で、規定に従った結果、矛盾が生じないかを検証
③提案的規定
: 提案を受け入れるか拒否するか意思決定することが必要
(2)事実認識
①個別的主張
: 事実であるかどうかを確認
②一般的主張
A:一般化の主張
: 厳密には全てを調査する。統計的に傾向を調べて一般化が妥
当かどうかを調べる。
B:法則の主張
: 反復現象に対する調査や因果関係の調査が必要
C:存在の主張
: 事実の調査や、目撃か単なる伝聞か等の情報源の妥当性を確
認。
(3)価値評価
: 価値・規範の基準が共有されていることが必要。相手が異なる
価値・規範を持っていたとしても否定はできない。評価が独断的
であることを示したり、他の評価が客観的であることを示すこと
等の手続きが必要。
導出の適切さ
① 意味に関わるもの→演繹
言語規則に正しく従っているかどうかによる。誤解や規
則違反を犯したとき誤謬が生じる。
② 事実に関わるもの→推測
ある事実に基づいて、事実から含意されないような他
の事実の成立を結論する。
A:背景法則に基づく推測
B:仮説形成による推測
C:帰納法による推測
導出の例
演繹
●蛙は哺乳類ではない。何故なら卵を産むからね。
●彼は、今日は自宅かアルバイト先にいると言ってたけど、自宅にいな
いから、きっとアルバイト先だと思う。
●近頃の学生はまじめだ。従って今度の新入生もまじめである。
推測
●彼は昨夜徹夜で勉強していた。だから、きっと疲れているに違いない。
●彼は二日酔いだそうだ。彼は、いつも近くのスナックに通っているから、
昨夜はいつものスナックで飲んだのだろう。
●今まで3回も見合いをして全て断られた。だから今度の見合いもどう
せ駄目だろう。
導出=推論
よく使われる三段論法(ModusPonens)
風が吹く
砂ほこりが立つ
盲人が多くなる
三味線が売れる
猫が殺される
ねずみが増える
桶をかじる
→
→
→
→
→
→
→
砂ほこりがたつ
盲人が多くなる
三味線が売れる
猫が殺される
ねずみが増える
桶をかじる
桶屋が儲かる
∴風が吹く
→
桶屋が儲かる
三段論法とは
P∩(P→Q)→Q
真理値表
P
Q
P→Q
P∩(P→Q)
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
0
P∩(P→Q)→Q
1
1
1
1
論理における推論(その1)
①連言
ゆえに
②簡約
ゆえに
③簡約
ゆえに
④付加
ゆえに
⑤付加
ゆえに
⑥後件の簡約
ゆえに
⑦前件の簡約
ゆえに
今日は雨が降る
今日は寒い
今日は雨が降り、寒い
東京は日本の首都で人口1千万以上である
東京は日本の首都である
A君は技術者を志望してK大学を受験するか
または歯医者志望してS大学を受験する
A君はK大学を受験するかS大学を受験する
A君は胃がんである
A君は胃がんか胃潰瘍である
A君は数学が得意でない
A君は数学と物理学両方ともに得意ということはない
僕はA大学に入学すれば
油絵を続けると共に数学を勉強する
僕はA大学に入学すれば、数学を勉強する
明日雨が降るか、大雨が吹くなら登山は中止する
明日雨が降れば、登山は中止する
P
Q
∴P∩Q
P∩Q
∴P
(P∩Q)∪
(R∩S)
∴Q∪S
P
∴P∪Q
~P
∴~(P∩Q)
P→Q∩R
∴P→Q
(P∪Q)→R
∴P→R
論理における推論(その2)
⑧肯定式
(単純三段論法)
ゆえに
⑨否定式
三角形ABCでAB=ACならば、角B=角Cである
三角形ABCでAB=ACである
三角形ABCで角B=角Cである
Sさんがおじさんなら、Sさんは男である。
Sさんは男ではない
ゆえに
Sさんは、おじさんではない。
⑩選言三段論法 A君は大学院に進むか、就職する
A君は大学院に進まない
ゆえに
A君は就職する
⑪条件三段論法 風が吹けば盲人が増える
盲人が増えれば三味線が売れる
ゆえに
風が吹けば三味線が売れる
⑫選言・三段論法 A君は大学院に進むか、就職する
A君は大学院に進むなら、S大学大学院に進む
ゆえに
A君はS大学大学院に進むか、就職する
⑬ジレンマ
重盛は父の命令に従うなら不忠である
重盛は父の命令に従わないなら親不孝である
ゆえに
重盛は不忠であるか、親不孝である
P→Q
P
∴Q
P→Q
~Q
∴~P
P∪Q
~P
∴Q
P→Q
Q→R
∴P→R
P∪Q
P→R
∴R∪Q
P→Q
~P→R
∴Q∪R
演習:以下の導出を演繹と推測に区別せよ
①ツルは天然記念物である。だから、むやみに捕獲したら罰せられる。
②今まで馬券を買って当たったことがない。だから買ってもどうせはず
れるさ。
③ジョーカを君が持ってるはずないさ。だって、僕の手元にあるもの。
④彼女、マスクをかけていたけど、スギ花粉症かな。
⑤ペンギンは哺乳類ではない。なぜならペンギンは鳥類だからさ。
⑥昨夜、彼は得意先の接待だったから、今朝は疲れているに違いない。
⑦コンピュータ室の鍵は鈴木君か木村君が持ってるけど、鈴木君は今
日いないから、木村君に借りてくれ。
⑧今までに付き合った男は、みんなずるかった。だから男はみんなずる
いものよ。
⑨どんな男だってずるいものよ。だから君もずるいに決まってるわ。
推測ということ
①背景法則に基づく推測(背景法則が確からしいものでなければならない)
(例)彼は昨日遅くまで呑んでいた。だから、きっと二日酔いだろう。
(背景法則)遅くまで呑んでいれば、二日酔いになるはずだ。
②仮説形成(証拠となる事実が説明できるか、他の有力な仮説がないか)
(例)彼をよくパチンコ屋で見かけるけど、パチンコが好きなのかな。
仮説:彼はパチンコが好きだ
→ 説明項
仮説形成 ↑
↓ 説明
証拠:彼をよくパチンコ屋で見かける ← 被説明項
③帰納法(サンプルの適切さが必要
(例)今まで付き合った男は、みんなずるかった。だから今度の彼もずるい
だろう。
(個別の事例を証拠として、一般的主張を結論) ⇔ 演繹
仮説形成での補助前提と消去条件
①補助前提
証拠
補助前提
仮説
②消去条件
:Aのシャツに血痕があった。
:被害者は刺されていた。
:Aは犯人である。
仮説
仮説形成↑
証拠+補助前提
仮説+補助前提
↓説明
証拠
証拠
補助前提
消去条件
仮説
:Aのシャツに血痕があった。
:被害者は刺されていた。
:血痕は被害者の血液型と異なる。
:Aは犯人ではない。
仮説
仮説形成 ↑
証拠+補助前提+消去条件
2.3 述語論理による推論
第1階述語論理(First-order Predicate calculus)
命題論理
述語論理
P1:つばめは鳥である。
鳥(つばめ)
P2:すずめは鳥である。
鳥(すずめ)
P3:こまどりは鳥である。
鳥(こまどり)
述語記号
:鳥
定数記号
:つばめ、すずめ、こまどり
素命題
:鳥(つばめ)、鳥(すずめ)、鳥(こまどり)
集合の定義域 :{つばめ,すずめ,こまどり}
全称記号
:∀x { 鳥(x) → 死ぬ(x) }
: xは変数
存在記号
:∃x { 鳥(x) → 飛ぶ(x) }
関数記号
:Friendly(Child(x), Neighbor(y))
Child, Neighbor を関数記号と呼ぶ
(例1)
•
•
•
•
全てのリンゴは赤い
リンゴはサクランボより大きい
花崗岩は白っぽい
厠橋変電所の地盤は沖積シルトである
:
:
:
:
•
•
•
全ての人間は動物である
全ての女性は人間である
本みかげは花崗岩である
: ∀x 人間(x)→動物(x)
: ∀x 女性(x)→動物(x)
: ∀x 本みかげ(x)→花崗岩(x)
•
•
•
美しい女性もいる
冬眠する哺乳動物もいる
地盤凍結して凍結土層を形成することがある
: ∃x 女性(x)→美しい(x)
: ∃x 哺乳動物(x)→冬眠(x)
: ∃x 地盤凍結→凍結土層形成(x)
赤い(リンゴ)
大きい(リンゴ,サクランボ)
白っぽい(花崗岩)
地盤(厠橋変電所,沖積シルト)
(例2)
全ての ………………………………………………………………… である
個体(x)に対して xが本みかげ
ならば xは花崗岩
∀ x
本みかげ(x)
→
花崗岩(x)
ある …………………………………………………………………… ことがある
個体(x)に対して xが地盤凍結する
ならば xは凍結土層を形成
∃ x
地盤凍結(x)
→
凍結土層形成(x)
節形式の必要性
推論規則
∀x Φ(x)のとき
任意の個体Aに対して
Φ(A)とすることができる
(例)
∀x 人間(x)→動物(x)
個体“淳子”に対して
人間(淳子)→動物(淳子)
とすることができる
節(Clause)形式
• リテラル(Literal) :素命題または素命題の否定
• 節(Clause)
:リテラルまたはリテラルの選言
(例) P(x)∪~Q(x,f(x))∪R(x,y)
• 節形式の命題 :
(例) (∀x1)(∀x2)……( ∀xn )[ C1∩C2∩……Cn ]
• 否定形式
:
(例) ~{(∀x)P(x)}≡ (∃x)~P(x)
~{(∃x)P(x)}≡ (∀x)~P(x)
{全ての鳥(x)が飛べる}わけではない≡飛べない鳥(x)が存在する
{冬眠する犬(x)が存在する}わけがない≡全ての犬(x)は冬眠しない
任意の式の節形式への変換
①P→Qを~P∪Qに、A≡Bを(~A∪B)∩(~B∪A)に変換。
②変数の標準化
(例)(∀x)[~P(x)∪(∃x)Q(x)]における∀x と x の x は別の変数を表している
ので、例えば(∀x)[~P(x)∪(∃y)Q(y)]とする。
③否定の範囲を縮小
(例)~(∀x)[P∩~(Q∩R)]を(∃x)[~P∪(Q∩R)]とする。
④存在記号を除去
(例)(∀x)(∃y)P(x,y)は、いかなるxに対しても、xが決まればP(x,y)を満足す
る y が存在するという意味であるため、 yはxの関数とみなすことができる。
従って(∀x)P(x,f(x))と書き直す。
⑤全称記号を前に出す
(例)(∀x)[P(x)∪(∀y)~Q(y)]を、 (∀x) (∀y) [P(x)∪~Q(y)]とする。
⑥連言標準形に変換
(例)(A∩B)∪(B∩C)は、(A∪B)∩(B∪C)∩ B ∩(A∪C)、
すなわち(A∪B)∩(B∪C)∩(A∪C)とする
演習
• 次の命題を節形式に直せ
(∀x)(∃y)P(x,y)∩(∀y)(∀z)[P(a,y)→~Q(y,z)]
→(∀u)(∃w)Q(u,w)
①~((∀x)(∃y)P(x,y)∩(∀y)(∀z)[~P(a,y)∪~Q(y,z)])∪(∀u)(∃w)Q(u,w)
②~(∀x)(∃y)P(x,y)∪~(∀y)(∀z)[~P(a,y)∪~Q(y,z)]∪(∀u)(∃w)Q(u,w)
③(∃x)(∀y)~P(x,y)∪(∃y)(∃z){~[~P(a,y)∪~Q(y,z)]}∪(∀u)(∃w)Q(u,w)
④(∃x)(∀y)~P(x,y)∪(∃y)(∃z)[P(a,y)∩Q(y,z)]}∪(∀u)(∃w)Q(u,w)
⑤~P(b,y)∪[P(a,c)∩Q(c,f(c))]}∪Q(u,g(u))
⑥[~P(b,y)∪P(a,c)∪Q(u,g(u))]∩[ ~P(b,y)∪Q(c,f(c))]}∪Q(u,g(u))]
一階述語論理
(Lower Predicate Calculus)
• 変数の出現を述語の引数にしか認めない
述語変数を認める(例∀p p(A))ものを2階述語論理、n階の述
語論理を許す論理をn+1階述語論理と呼ぶ。
• 関数の考え方
引数に対して「関数」を適用させ、結果を返す。
人間(父(淳子))
→ 動物(父(淳子))
関数 父(淳子) の結果が貞夫である場合
人間(貞夫)
→ 動物(貞夫)
• 等価の述語(個体間の関係での等価)
全ての述語に対して
P(X) ≡
P(Y)
f(X)
≡
f(Y)
のときに限り
X=Y とみなす。
色々な論理
•
•
•
•
•
•
•
命題論理と述語論理
古典論理と直感主義理論(P∪~Pは必ずしもそうではない)
様相論理(Modal Logic : 可能性や必然性を示す論理記号を導入)
非単調論理(Non-monotonic Logic : 不完全な情報に対応)
時相論理(Temporal Logic : 時間の経過の表現)
多ソート論理(Many Sorted Logic : 述語論理に概念間の階層構造)
多層論理(Many Layered Logic : 多ソート論理に巾集合の概念を導入)
巾集合 : ある集合の全ての部分集合の集合
(例)全ての点の集合の巾集合は線分の集合
• 多値論理(真偽の2値に未知を加えて3値にしたもの、0から1の間
の任意の値をとるファジー論理)