农夫过河问题状态空间表示.pdf

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