农夫过河问题状态空间表示
-
逻辑学教授的
3
个得意门生
ABC
，前一晚在酒吧喝多了，结果第二天
3
人集体迟到。教授
说：
“
作
为对你们迟到的惩罚，你们
3
人必须比其他同学多做一道作业，
完成了这道作业才
可以离开教室。
”
这
道附加的作业是一道帽子题，教授给每人戴了顶帽子，帽子不是红色就
是白色，不是白色
就是红色。每人都能看见其他
2
人帽子的颜色，却不能看见自己
帽子的
颜色。每人都看到其他
2
人帽子
的颜色后，每思考
5
分钟为一轮，谁猜出自己帽子的颜色
了就可以说出来并离开。教授还说：
“
你们<
/p>
3
人中至少有
1
人戴了红色帽子。
”
第一轮下来，<
/p>
A
说：
“
我没猜
出来。
”B
说
“
我也没猜出来
”C
说：
“
我也猜不出。
”
第二轮下来，还是没人能猜出自己帽子的颜色。
第三轮，
3
人都猜出了自己帽子的颜色。
问：
ABC
三人头顶都
是什么颜色的帽子？然后用谓词逻辑写出推理过程。
最一般合一及归结反演相关
已知
w={P(f(x,g(A,y)),z),
P(f(x,z),z)
，求
MGU
令
δ
0
=ε<
/p>
，
w
0
=w
，因
w
中含有两个表达式，因此
δ
0
不是最一般合一
<
/p>
差异集
D
0
={
g(A,y)/z}
δ
1
=δ
0
ºD
0
={g(A,y)/z}
w
1
={P(f(x,g(A,y)),g(A,y)),
P(f(x,g(A,y)),g(A,y))
w
1
中仅含有一个表达式，所以
δ
< br>1
就是最一般合一。
证明
G
是否是
F1
、<
/p>
F2
的逻辑结论。
F1:(
∀
x)(P(x)→(Q(x)
< br>∧
R(x)))
F2:(
∃
x)(P(x)
∧
S(x))
G: (
∃
x)(S(x)
∧
R(x))
F1: ¬P(x)
∨
(Q(x
)
∧
R(x))
⇒
(¬P(x)
∨
Q(x))
∧
(¬P(x)
∨
R(x))
F2:
P(x)
∧
S(x)
¬G: ¬(
∃
x)(S(x)
∧
R(x))
⇒
(
∀
x)(¬(S(x)
∧
R(x)))
⇒
¬S(x)
∨
¬R(x)
子句集：
1
¬P(x)
∨
Q(x)
2
¬P(x)
∨
R(x)
3 P(x)
4
S(x)
5
¬S(x)
∨
¬R(x)
其中
2
与
3
规约，
4
与
5
归结，其结果再归结得到空子句，证明
G
是
F1
与
F2
的结论。<
/p>
农夫过河问题
(1)
农夫每次只能带一样东西过河
(2)
如果没有农夫看管，狼吃羊，羊吃菜
要求：
设计一个过河方案，使
得农夫、狼、羊、菜都能过河，画出相应的状态空间图。
四元
组
S
表示状态，即
S
< br>＝
(
农夫，狼，羊，菜
)
用
0
表示在左岸，
1
表示在右岸
初始
< br>S=(0
，
0
，
0
，
0)
目标
G=(1
，
1
，
1
，
1)