从x处走到y处。
条件:
SITE(Monkey,x)
动作:
删除SITE(Monkey,x);增加SITE(Monkey,y)
(2)pushbox(x,y):
将箱子从x处推到y处。
条件:
SITE(Monkey,x)∧SITE(Box,x)∧~ONBOX(Monkey)
动作:
删除SITE(Monkey,x),SITE(Box,x);增加SITE(Monkey,y),SITE(Box,y)
(3)climbbox:
爬到箱子顶上。
条件:
~ONBOX(Monkey)
动作:
删除~ONBOX(Monkey);增加ONBOX(Monkey)
(4)grasp:
摘下香蕉。
条件:
~HOLDS(Monkey)∧ONBOX(Monkey)∧SITE(Monkey,b)
动作:
删除~HOLDS(Monkey);增加HOLDS(Monkey)
在执行某一操作前,先检查当前状态是否满足其前提条件。
若满足,则执行该操作。
否则,检查另一操作的条件是否被满足。
检查的方法就是当前的状态中是否蕴含了操作所要求的条件。
在定义了操作谓词后,就可以给出从初始状态到目标状态的求解过
程。
在求解过程中,当进行条件检查时,要进行适当的变量代换。
SITE(Monkey,a)
SITE(Box,c)
~ONBOX(Monkey)
~HOLDS(Monkey)
⇓goto(x,y),用a代x,用c代y
SITE(Monkey,c)
SITE(Box,c)
~ONBOX(Monkey)
~HOLDS(Monkey)
⇓pushbox(x,y),用c代x,用b代y
SITE(Monkey,b)
SITE(Box,b)
~ONBOX(Monkey)
~HOLDS(Monkey)
⇓climbbox
SITE(Monkey,b)
SITE(Box,b)
ONBOX(Monkey)
~HOLDS(Monkey)
⇓grasp
SITE(Monkey,b)
SITE(Box,b)
ONBOX(Monkey)
HOLDS(Monkey)
2.16.用语义网络表示下列知识:
(1)所有的鸽子都是鸟;
(2)所有的鸽子都有翅膀;
(3)信鸽是一种鸽子,它有翅膀。
解:
本题涉及对象有信鸽、鸽子和鸟。
鸽子和信鸽的属性是有翅膀。
鸽子和鸟是ISA关系,信鸽和鸽子是AKO关系。
根据分析得到本题的语义网络如下:
2.17.请对下列命题分别写出它的语义网络:
(1)每个学生都有多本书。
解:
根据题意可得本题的语义网络如下:
(2)孙老师从2月至7月给计算机应用专业讲《网络技术》课程。
解:
根据题意可得本题的语义网络如下:
(3)雪地上留下一串串脚印,有的大,有的小,有的深,有的浅。
解:
根据题意可得本题的语义网络如下:
(4)王丽萍是天发电脑公司的经理,她35岁,住在南内环街68号。
解:
根据题意可得本题的语义网络如下:
2.18.请把下列命题用一个语义网络表示出来:
(1)猪和羊都是动物;
(2)猪和羊都是偶蹄动物和哺乳动物;
(3)野猪是猪,但生长在森林中;
(4)山羊是羊,且头上长着角;
(5)绵羊是一种羊,它能生产羊毛。
解:
本题涉及对象有猪、羊、动物、野猪、山羊和绵羊。
猪和羊的属性是偶蹄和哺乳。
野猪的属性是生长在森林中。
山羊的属性是头上长着角。
绵羊的属性是产羊毛。
根据对象之间的关系得到本题的语义网络如下:
2.27有一农夫带一条狼,一只羊和一框青菜与从河的左岸乘船倒右岸,但受到下列条件的限制:
(1)船太小,农夫每次只能带一样东西过河;
(2)如果没有农夫看管,则狼要吃羊,羊要吃菜。
请设计一个过河方案,使得农夫、浪、羊都能不受损失的过河,画出相应的状态空间图。
题示:
(1)用四元组(农夫,狼,羊,菜)表示状态,其中每个元素都为0或1,用0表示在左岸,用1表示在右岸。
(2)把每次过河的一种安排作为一种操作,每次过河都必须有农夫,因为只有他可以划船。
解:
第一步,定义问题的描述形式
用四元组S=(f,w,s,v)表示问题状态,其中,f,w,s和v分别表示农夫,狼,羊和青菜是否在左岸,它们都可以取1或0,取1表示在左岸,取0表示在右岸。
第二步,用所定义的问题状态表示方式,把所有可能的问题状态表示出来,包括问题的初始状态和目标状态。
由于状态变量有4个,每个状态变量都有2种取值,因此有以下16种可能的状态:
S0=(1,1,1,1),S1=(1,1,1,0),S2=(1,1,0,1),S3=(1,1,0,0)
S4=(1,0,1,1),S5=(1,0,1,0),S6=(1,0,0,1),S7=(1,0,0,0)
S8=(0,1,1,1),S9=(0,1,1,0),S10=(0,1,0,1),S11=(0,1,0,0)
S12=(0,0,1,1),S13=(0,0,1,0),S14=(0,0,0,1),S15=(0,0,0,0)
其中,状态S3,S6,S7,S8,S9,S12是不合法状态,S0和S15分别是初始状态和目标状态。
第三步,定义操作,即用于状态变换的算符组F
由于每次过河船上都必须有农夫,且除农夫外船上只能载狼,羊和菜中的一种,故算符定义如下:
L(i)表示农夫从左岸将第i样东西送到右岸(i=1表示狼,i=2表示羊,i=3表示菜,i=0表示船上除农夫外不载任何东西)。
由于农夫必须在船上,故对农夫的表示省略。
R(i)表示农夫从右岸将第i样东西带到左岸(i=1表示狼,i=2表示羊,i=3表示菜,i=0表示船上除农夫外不载任何东西)。
同样,对农夫的表示省略。
这样,所定义的算符组F可以有以下8种算符:
L(0),L
(1),L
(2),L(3)
R(0),R
(1),R
(2),R(3)
第四步,根据上述定义的状态和操作进行求解。
该问题求解过程的状态空间图如下:
L
(2)
(0,1,0,1)
(1,1,0,1)
(0,0,1,0)
(1,0,1,0)
(0,0,0,0)
3.5什么是谓词公式?
什么是谓词公式的解释?
设D={1,2},试给出谓词公式(∃x)(∀y)(P(x,y)→Q(x,y))的所有解释,并且对每一种解释指出该谓词公式的真值。
解:
谓词公式是按照下述五个规则由原子公式、连接词、量词及圆括号所组成的字符串。
(1)原子谓词公式是合式公式。
(2)若A是合式公式,则~A也是合式公式。
(3)若A和B都是合式公式,则A∧B、A∨B、A→B、A↔B也都是合式公式。
(4)若A是合式公式,x是任一个体变元,则(∀x)A和(∃x)A也都是合式公式。
(5)只有按
(1)−(4)所得的公式才是合式公式。
谓词公式的解释:
设D为谓词公式P的个体域,若对P中的个体常量、函数和谓词按照如下规定赋值:
(1)为每个个体常量指派D中的一个元素;
(2)为每个n元函数指派一个从Dn到D的映射,其中Dn={(x1,x2,…,xn)|x1,x2,…,xn∈D}(3)为每个n元谓词指派一个从Dn到{F,T}的映射;则这些指派称为公式P在D上的解释。
下面给出本题的所有解释:
1.对谓词指派的真值为:
P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,Q(1,1)=T,Q(1,2)=F,Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
2.对谓词指派的真值为:
P(1,1)=T,P(1,2)=F,P(2,1)=F,P(2,2)=T,Q(1,1)=T,Q(1,2)=F,Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为F。
所以在此解释下,本题谓词公式的真值为T。
3.对谓词指派的真值为:
P(1,1)=F,P(1,2)=T,P(2,1)=T,P(2,2)=F,Q(1,1)=T,Q(1,2)=F,Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为F;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
4.对谓词指派的真值为:
P(1,1)=F,P(1,2)=T,P(2,1)=F,P(2,2)=T,Q(1,1)=T,Q(1,2)=F,Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为F;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为F。
所以在此解释下,本题谓词公式的真值为F。
5.对谓词指派的真值为:
P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,Q(1,1)=T,Q(1,2)=F,Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为F,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
6.对谓词指派的真值为:
P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,Q(1,1)=F,Q(1,2)=T,Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)→Q(1,1)为F,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
7.对谓词指派的真值为:
P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,Q(1,1)=F,Q(1,2)=T,Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)→Q(1,1)为F,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为F,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为F。
8.对谓词指派的真值为:
P(1,1)=T,P(1,2)=F,P(2,1)=F,P(2,2)=T,Q(1,1)=T,Q(1,2)=F,Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
9.对谓词指派的真值为:
P(1,1)=T,P(1,2)=F,P(2,1)=F,P(2,2)=T,Q(1,1)=F,Q(1,2)=T,Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)→Q(1,1)为F,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为F。
所以在此解释下,本题谓词公式的真值为F。
10.对谓词指派的真值为:
P(1,1)=T,P(1,2)=F,P(2,1)=F,P(2,2)=T,Q(1,1)=F,Q(1,2)=T,Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)→Q(1,1)为F,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
11.对谓词指派的真值为:
P(1,1)=F,P(1,2)=T,P(2,1)=T,P(2,2)=F,Q(1,1)=T,Q(1,2)=F,Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为F;x=2时,P(2,1)→Q(2,1)为F,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为F。
12.对谓词指派的真值为:
P(1,1)=F,P(1,2)=T,P(2,1)=T,P(2,2)=F,Q(1,1)=F,Q(1,2)=T,Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
13.对谓词指派的真值为:
P(1,1)=F,P(1,2)=T,P(2,1)=T,P(2,2)=F,Q(1,1)=F,Q(1,2)=T,Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为F,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
14.对谓词指派的真值为:
P(1,1)=F,P(1,2)=T,P(2,1)=F,P(2,2)=T,Q(1,1)=T,Q(1,2)=F,Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为F;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
15.对谓词指派的真值为:
P(1,1)=F,P(1,2)=T,P(2,1)=F,P(2,2)=T,Q(1,1)=F,Q(1,2)=T,Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为F。
所以在此解释下,本题谓词公式的真值为F。
16.对谓词指派的真值为:
P(1,1)=F,P(1,2)=T,P(2,1)=F,P(2,2)=T,Q(1,1)=F,Q(1,2)=T,Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)→Q(1,1)为T,P(1,2)→Q(1,2)为T;x=2时,P(2,1)→Q(2,1)为T,P(2,2)→Q(2,2)为T。
所以在此解释下,本题谓词公式的真值为T。
3.9判断以下公式对是否可合一;若可合一,则求出最一般的合一。
(1)P(a,b), P(x,y)
解:
依据算法:
(1)令W={P(a,b),P(x,y)}。
(2)令σ0=ε,W0=W。
(3)W0未合一。
(4)从左到右找不一致集,得D0={a,x}。
(5)取x0=x,t0=a,则
σ1=σ0⋅{t0/x0}=σ0⋅{a/x}={a/x}
W1=W0σ1={P(a,b),P(a,y)}
(3’)W1未合一。
(4’)从左到右找不一致集,得D1={b,y}。
(5’)取x1=y,t1=b,则
σ2=σ1⋅{t1/x1}=σ1⋅{b/y}={a/x}⋅{b/y}={a/x,b/y}
W2=W1σ2={P(a,b),P(a,b)}
(3’’)W2已合一,因为其中包含相同的表达式,这时σ2={a/x,b/y}即为所求的mgu。
(2)P(f(z)),b), P(y,x)
解:
依据算法:
(1)令W={P(f(z),b),P(y,x)}。
(2)令σ0=ε,W0=W。
(3)W0未合一。
(4)从左到右找不一致集,得D0={f(z),y}。
(5)取x0=y,t0=f(z),则
σ1=σ0⋅{t0/x0}=σ0⋅{f(z)/y}={f(z)/y}
W1=W0σ1={P(f(z),b),P(f(z),x)}
(3’)W1未合一。
(4’)从左到右找不一致集,得D1={b,x}。
(5’)取x1=x,t1=b,则
σ2=σ1⋅{t1/x1}=σ1⋅{b/x}={f(z)/y}⋅{b/x}={f(z)/y,b/x}
W2=W1σ2={P(f(z),b),P(f(z),b)}
(3’’)W2已合一,因为其中包含相同的表达式,这时σ2={f(z)/y,b/x}即为所求的mgu。
(3)P(f(x),y), P(y,f(a))
解:
依据算法:
(1)令W={P(f(x),y),P(y,f(a))}。
(2)令σ0=ε,W0=W。
(3)W0未合一。
(4)从左到右找不一致集,得D0={f(x),y}。
(5)取x0=y,t0=f(x),则
σ1=σ0⋅{t0/x0}=σ0⋅{f(x)/y}={f(x)/y}
W1=W0σ1={P(f(x),f(x)),P(f(x),f(a))}
(3’)W1未合一。
(4’)从左到右找不一致集,得D1={y,f(a)}。
(5’)取x1=y,t1=f(a),则
σ2=σ1⋅{t1/x1}=σ1⋅{f(a)/y}={f(x)/y}⋅{f(a)/y}={f(x)/y}
W2=W1σ2={P(f(x),f(x)),P(f(x),f(a))}
(6)算法终止,W的mgu不存在。
(4)P(f(y),y,x), P(x,f(a),f(b))
解:
依据算法:
(1)令W={P(f(y),y,x),P(x,f(a),f(b))}。
(2)令σ0=ε,W0=W。
(3)W0未合一。
(4)从左到右找不一致集,得D0={f(y),x}。
(5)取x0=x,t0=f(y),则
σ1=σ0⋅{t0/x0}=σ0⋅{f(y)/x}={f(y)/x}
W1=W0σ1={P(f(y),y,f(y)),P(f(y),f(a),f(b))}
(3’)W1未合一。
(4’)从左到右找不一致集,得D1={y,f(a)}。
(5’)取x1=y,t1=f(a),则
σ2=σ1⋅{t1/x1}=σ1⋅{f(a)/y}={f(y)/x}⋅{f(a)/y}={f(f(a))/x,f(a)/y}
W2=W1σ2={P(f(f(a)),f(a),f(f(a))),P(f(f(a)),f(a),f(b))}
(6)算法终止,W的mgu不存在。
(5)P(x,y), P(y,x)
解:
依据算法:
(1)令W={P(x,y),P(y,x)}。
(2)令σ0=ε,W0=W。
(3)W0未合一。
(4)从左到右找不一致集,得D0={x,y}。
(5)取x0=x,t0=y,则
σ1=σ0⋅{t0/x0}=σ0⋅{y/x}={y/x}
W1=W0σ1={P(y,y),P(y,y)}
(3’)W2已合一,因为其中包含相同的表达式,这时σ1={y/x}即为所求的mgu。
3.13把下列谓词公式分别化为相应的子句集:
(1)(∀z)(∀y)(P(z,y)∧Q(z,y))
解:
所求子句集为S={P(z,y),(z,y)}
(2)(∀x)(∀y)(P(x,y)→Q(x,y))
解:
原式⇒(∀x)(∀y)(~P(x,y)∨Q(x,y))
所求子句集为S={~P(x,y)∨Q(x,y)}
(3)(∀x)(∃y)(P(x,y)∨(Q(x,y)→R(x,y)))
解:
原式⇒(∀x)(∃y)(P(x,y)∨(~Q(x,y)∨R(x,y)))
⇒(∀x)(P(x,f(x))∨(~Q(x,f(x))∨R(x,f(x))))
所求子句集为S={P(x,f(x))∨(~Q(x,f(x))∨R(x,f(x)))}
(4)(∀x)(∀y)(∃z)(P(x,y)→Q(x,y)∨R(x,z))
解:
原式⇒(∀x)(∀y)(∃z)(~P(x,y)∨Q(x,y)∨R(x,z))
⇒(∀x)(∀y)(~P(x,y)∨Q(x,y)∨R(x,f(x,y)))
所求子句集为S={~P(x,y)∨Q(x,y)∨R(x,f(x,y))}
(5)(∃x)(∃y)(∀z)(∃u)(∀v)(∃w)(P(x,y,z,u,v,w)∧(Q(x,y,z,u,v,w)∨~R(x,z,w)))
解:
原式⇒(∃x)(∃y)(∀z)(∃u)(∀v)(P(x,y,z,u,v,f(z,v))∧(Q(x,y,z,u,v,f(z,v))∨~R(x,z,f(z,v))))
⇒(∃x)(∃y)(∀z)(∀v)(P(x,y,z,f(z),v,f(z,v))∧(Q(x,y,z,f(z),v,f(z,v))∨~R(x,z,f(z,v))))
⇒(∀z)(∀v)(P(a,b,z,f(z),v,f(z,v))∧(Q(a,b,z,f(z),v,f(z,v))∨~R(a,b,f(z,v))))
所求子句集为S={P(a,b,z,f(z),v,f(z,v)),Q(a,b,z,f(z),v,f(z,v))∨~R(a,b,f(z,v))}
3.14判断下列子句集中哪些是不可满足的:
(1)S={~P∨Q,~Q,P,~P}
解:
使用归结推理:
(1)~P∨Q
(2)~Q(3)P(4)~P
(3)与(4)归结得到NIL,因此S是不可满足的。
(2)S={P∨Q,~P∨Q,P∨~Q,~P∨~Q}
解:
使用归结推理:
(1)P∨Q
(2)~P∨Q(3)P∨~Q(4)~P∨~Q
(1)与
(2)归结得(5)Q
(3)与(5)归结得(6)P
(4)与(6)归结得(7)~Q
(5)与(7)归结得NIL,因此S是不可满足的。
(3)S={P(y)∨Q(y),~P(f(x))∨R(a)}
解:
使用归结推理:
设C1=P(y)∨Q(y),C2=~P(f(x))∨R(a),选L1=P(y),L2=~P(f(x)),则
L1与L2的mgu是σ={f(x)/y},C1与C2的二元归结式C12=Q(f(x))∨R(a),因此S是可满足的。
(4)S={~P(x)∨Q(x),~P(y)∨R(y),P(a),S(a),~S(z)∨~R(z)}
解:
使用归结推理:
(1)~P(x)∨Q(x)
(2)~P(y)∨R(y)(3)P(a)(4)S(a)(5)~S(z)∨~R(z)
(2)与(3)归结得到(6)R(a)
(4)与(5)归结得到(7)~R(a)
(6)与(7)归结得到NIL,因