Page 31 - 人工智慧導論_試閱_課本PDF

第2章 知識及知識表示

2-4.2 謂詞邏輯公式

ίፗ൚ᜌ፨ʕϞəவ఻ࡈਿ͉฿ׂܝఱ̙࿴ிፗ൚ᜌ፨ʮόf

定義 2.1cࡡɿʮό
Ǻண P ݊ፗ൚ୌdt ,t ,n,t މධdۆ P(t ,t ,n,t ) ݊ࡡɿʮόf
1
1
2
n
2
n
ǻண R ݊նᕚdۆ R ݊ࡡɿʮόf
定義 2.2cፗ൚ᜌ፨Υόʮό€͵̙ᔊ၈ፗ൚ᜌ፨ʮόאʮό
Ǻࡡɿʮό݊ʮόf
ǻν A,B ݊ʮόdۆ (¬A)d(A∨B)d(A∧B)d(A→B)d(A↔B) ݊ʮόf
Ǽν A މʮόdx މࡈ᜗ᜊᅰdۆ (∀xA)d(∃xA) މʮόf

ǽʮό͟˲ස͟ϞࠢϣԴ͜ǺeǻeǼϾ੻f
ʮόʕǻeǼஈה̈ତֹܼ̙ٙܲɓ֛ٙ˙ج޲ଫdШඎ൚ٙᒍਹʕස̈ତɓ

ࡈࡡɿʮόࣛՉᒍਹֹܼ̙ٙ޲ଫdщۆʔঐ޲f

例 2.4 ഹΤٙԭԢ౶εᅃɧݬሞٙ৿ணj˜ɭɛ̀ϥdᘽࣸזֵ݊ɛd݂˼

̀ϥ™f
解 ண H(x) ڌͪ x ݊ɛdP(x) ڌͪ x ̀ϥda ڌͪᘽࣸזֵdۆ̙ਗ਼ԭԢ౶εᅃ
ٙɧݬሞᄳϓމፗ൚ᜌ፨ʮόj

∀x(H(x) ÷ P(x)) ÷ (H(a) ÷ P(a))

例 2.5 ࿁הϞІ್ᅰ xdy ̀Ϟ x+y≥xf
例 2. 5 对所有自然数 x,y 必有 x+y≥x。
ڌͪ x މІ್ᅰdϤ̙ࣛ˸ਗ਼Ⴇ̩ᄳϓj
解 解 设 F(x,y,z)表示 x+y≥z,N(X)表示 x 为自然数,此时可以将语句写成:
例 2. 5 对所有自然数 x,y 必有 x+y≥x。
∀x∀y(N(x) ∧ N(y) → F(x,y,x))
解 设 F(x,y,z)表示 x+y≥z,N(X)表示 x 为自然数,此时可以将语句写成:
∀x∀y(N(x) ∧ N(y) → F(x,y,x))
2. 4. 3 谓词逻辑公式的解释
2-4.3 謂詞邏輯公式的解釋
2. 4. 3 谓词逻辑公式的解释
在谓词逻辑中,公式是一个符号串,必须给以具体的解释。 所谓解释就是给公式
ίፗ൚ᜌ፨ʕdʮό݊ɓࡈୌ໮Еd̀඲ഗ˸Ո᜗ٙ༆ᙑfהፗ༆ᙑఱ݊ഗʮ
中的个体变量指定一个具体的个体域 D,个体常量指定个体域中的一个具体个体,对 n
όʕٙࡈ᜗ᜊᅰܸ֛ɓࡈՈ᜗ٙࡈ᜗ਹ Ddࡈ᜗੬ඎܸ֛ࡈ᜗ਹʕٙɓࡈՈ᜗ࡈ᜗d
在谓词逻辑中,公式是一个符号串,必须给以具体的解释。 所谓解释就是给公式
元函数 f 指定一个具体的从 D 到 D 的映射,对命题 R 指定一个 E = {F,T}中的值,对
n
n
࿁ n ʩՌᅰ f ܸ֛ɓࡈՈ᜗ٙ੽ D Ց D ݈࢛ٙd࿁նᕚ R ܸ֛ɓࡈ E={F,T} ʕٙ࠽d
中的个体变量指定一个具体的个体域 D,个体常量指定个体域中的一个具体个体,对 n
m
m
m 元谓词 P 指定一个具体的从 D 到{F,T}的映射。
n
࿁ m ʩፗ൚ P ܸ֛ɓࡈՈ᜗ٙ੽ D Ց {F,T} ݈࢛ٙf 指定一个 E = {F,T}中的值,对
元函数 f 指定一个具体的从 D 到 D 的映射,对命题 R
一个公式经解释后才有具体的意义,即可确定其真假。
m
ɓࡈʮό຾༆ᙑܝʑϞՈ᜗ٙจ່dу̙ᆽ֛Չॆ৿f
m 元谓词 P 指定一个具体的从 D 到{F,T}的映射。
例 2. 6 用下面的公式定义一个半群:
一个公式经解释后才有具体的意义,即可确定其真假。
例 2.6 ͜ɨࠦٙʮό່֛ɓࡈ໊̒j
x y z((x°y)°z = x°(y°z))
例 2. 6 用下面的公式定义一个半群:
对这个公式可以给出一个解释:
x y z((x°y)°z = x°(y°z))
①个体域 D:整数。
对这个公式可以给出一个解释:
②二元函数°:整数的加运算。
①个体域 D:整数。
③二元谓词 = :整数的相等性关系。 31
②二元函数°:整数的加运算。
在此解释下公式为真,亦即是说:(I,+)是半群。
③二元谓词 = :整数的相等性关系。
在此解释下公式为真,亦即是说:(I,+)是半群。
2. 4. 4 谓词逻辑永真公式
2. 4. 4 谓词逻辑永真公式
公式一经给出解释就成为确定的了,此时即能分辨其真假。 以此为基础就能研究
公式一经给出解释就成为确定的了,此时即能分辨其真假。 以此为基础就能研究
公式的永真性问题。
定义 2. 3 公式 A 如至少在一种解释下有一个赋值使其为真,则称 A 是可满足的。
公式的永真性问题。
定义 2. 4 公式 A 在所有解释下的所有赋值均使其为真,则称 A 是永真,或称 A 为
定义 2. 3 公式 A 如至少在一种解释下有一个赋值使其为真,则称 A 是可满足的。
永真公式。 定义 2. 4 公式 A 在所有解释下的所有赋值均使其为真,则称 A 是永真,或称 A 为
定义 2. 5 公式 A 在所有解释下的所有赋值均使其为假,则称 A 为永假,或称 A 为
永真公式。
永假公式。 定义 2. 5 公式 A 在所有解释下的所有赋值均使其为假,则称 A 为永假,或称 A 为
接下来讨论谓词逻辑中的永真公式。 在谓词逻辑中常用的永真公式有以下
永假公式。
22 个。 接下来讨论谓词逻辑中的永真公式。 在谓词逻辑中常用的永真公式有以下
设 P,Q,R 是公式,则必有:
22 个。

① ┐┐P→P。
设 P,Q,R 是公式,则必有:

② P∧Q→Q∧P。
① ┐┐P→P。
③ P∨Q→Q∨P。
② P∧Q→Q∧P。
④ ┐(P∧Q)→┐P∨┐Q。
③ P∨Q→Q∨P。
⑤ ┐(P∨Q)→┐P∧┐Q。
④ ┐(P∧Q)→┐P∨┐Q。
⑥ P∧T→P。
⑤ ┐(P∨Q)→┐P∧┐Q。
⑦ P∨F→P。
⑥ P∧T→P。
⑧ P∧P→P。
⑦ P∨F→P。
⑧ P∧P→P。
2 9

2 9