秋季学期书面作业讲解

人工智能ArtificialIntelligence(AI)许建华xujianhua@南京师范大学计算机学院2013年秋季考试安排：时间：2013年12月31日周二下午1:30-3:30地点：J2-5012013年秋季学期书面作业讲解状态空间法书面作业题：15243678初始状态12345678目标状态利用宽度优先、深度优先（深度限制为4）、有序搜索算法（启发函数定义为数码不在位的个数）找出上述八数码问题从初始状态到目标状态的操作符序列？15243678123415243678124536781524367815247368521436781526437812453678124536781543267815243867152473681524736852143678152643784125367812345678154326781524386715273468152476835214367854213678152637481526437841253678412653781234567812345867宽度优先1524367812341524367812453678152436781524736812453678124536781543267815243867152473681524736812345678154326781524386715273468152476831234567812345867深度优先1547268315247683521734681527346815243867152486371543267813542678右边后产生书面作业：假设当前的棋局为OX请用极大极小过程为MAX找出一个好棋？OXXOXOXXOXXXOXXOOXXOOXXOXOXOXOXOXO111221OOXXOXXOOXXOOXXOOXXO00001OOXX10OOXXOOXXOOXX1121OXOXXOXOXOOX00001XOXO1XOXOXOXOXOXO001存在的问题：中间层的值不是倒推计算出来的某些棋局的值计算有误消解原理部分的书面作业1、求公式集W={P(f(x),y),P(f(y),a)}的最一般的合一者（一致置换）第一步：k=0,公式集F0=W,置换σ0=ε（空）,分歧集D0={x,y}置换为{y/x}σ1=σ0{y/x}={y/x}F1=F0{y/x}={P(f(y),y),P(f(y),a)}k=k+1=1解：{P(f(x),y),P(f(y),a)}第二步：F1中含有两个表达式，继续分歧集D1={a,y}，置换为{a/y}σ2=σ1{a/y}={a/x,a/y}F2=F1{a/y}={P(f(a),a)}k=2{P(f(y),y),P(f(y),a)}第三步：F2中只有一个表达式，结束所求的最一般的一致置换或最一般的合一者为：σ2={a/x,a/y}主要问题：合成运算有误，错误答案：{y/x,a/y}还是两个公式2、求谓词公式～{(∀x){P(x)→{(∀y)[P(y)→P(f(x,y))]∧(∀y)[Q(x,y)→P(y)]}}}的子句集

注：所有粗箭头仅表示配对的括号或者操作的符号分析公式的配对括号和量词的辖域～{(∀x){P(x)→

{(∀y)[P(y)→P(f(x,y))]∧(∀y)[Q(x,y)→P(y)]}}

}（消去蕴涵）=～{(∀x){[～P(x)]∨

{(∀y)[～P(y)∨P(f(x,y))]∧(∀y)[～Q(x,y)∨P(y)]}}}

（非直接作用到谓词符号）=(∃x){P(x)∧

～{(∀y)[～P(y)∨P(f(x,y))]∧(∀y)[～Q(x,y)∨P(y)]}}=(∃x){P(x)∧

{

～{(∀y)[～P(y)∨P(f(x,y))]}∨

～{

(∀y)[～Q(x,y)∨P(y)]}}}=(∃x){P(x)∧

{(∃y)[P(y)∧～P(f(x,y))]∨(∃y)[Q(x,y)∧～P(y)]}}

（改名）=(∃x){P(x)∧{(∃y)[P(y)∧～P(f(x,y))]∨(∃z)[Q(x,z)∧～P(z)]}}（消去存在量词）=P(a)∧{[P(b)∧～P(f(a,b))]∨[Q(a,c)∧～P(c)]}用常量a,b,c代替变量x,y,z（利用分配律）P∨(Q∧R)=(P∨Q)∧(P∨R)=P(a)∧{{[P(b)∧～P(f(a,b))]∨Q(a,c)}∧

{[P(b)∧～P(f(a,b))]∨～P(c)}}=P(a)∧{{[P(b)∨Q(a,c)]∧[～P(f(a,b))∨Q(a,c)]}∧{[P(b)∨～P(c)]∧[～P(f(a,b))∨～P(c)]}}再用一次分配律=P(a)∧{[P(b)∧～P(f(a,b))]∨[Q(a,c)∧～P(c)]}（结合律）＝P(a)∧[P(b)∨Q(a,c)]∧[～P(f(a,b))∨Q(a,c)]∧[P(b)∨～P(c)]∧[～P(f(a,b))∨～P(c)]子句集：{P(a),P(b)∨Q(a,c),～P(f(a,b))∨Q(a,c),P(b)∨～P(c),～P(f(a,b))∨～P(c)}这里a,b,c都是常量，不需要改名主要错误：没有按照步骤常量改名3、设子句集为：S={～P(x)∨Q(x),P(f(a)),～Q(f(z))}请求出它的一个反演

解法1：①～P(x)∨Q(x)②P(f(a))③～Q(f(z))可以消解的子集④

c1=①,c’1=Q(x);c2=②,c’2=φ

用合一算法求{P(x),P(f(a))}的mug，得β={f(a)/x}

归结式或消解式为c=(c’1β∨c’2β)=Q(f(a))①～P(x)∨Q(x)②P(f(a))错误写法：{x/f(a)}⑤c1=③,c’1=φ;c2=④,c’2=φ用合一算法求{Q(f(z)),Q(f(a))}的mgu，得β={a/z}

归结式或消解式为c=φ

③～Q(f(z))④Q(f(a))①～P(x)∨Q(x)②P(f(a))③～Q(f(z))④

Q(f(a))①②mgu={f(a)/x}⑤

φ

③④mgu={a/z}解法2：④c1=①,c1’=～P(x)；c2=③,c’2=φ

合一算法得mgu:β={f(z)/x}消解式为～

P(f(z))⑤c1=②,c’1=φ,c2=④,c’2=φ合一算法得mgu:β={a/z}归结式或消解式为c=φ①～P(x)∨Q(x)③～Q(f(z))②P(f(a))④～P(f(z))①～P(x)∨Q(x)②P(f(a))③～Q(f(z))④

～P(f(z))①③mgu={f(z)/x}⑤

φ②④mgu={a/z}4、设前提条件为F1:(∀x){P(x)→(∀y)[Q(y)→～L(x,y)]}F2:(∃x){P(x)∧(∀y)[R(y)→L(x,y)]}试用消解原理证明下列结论成立：G:(∀x)[R(x)→～Q(x)]证明：

F1的前束合取范式与子句集：(∀x){P(x)→(∀y)[Q(y)→～L(x,y)]}＝(∀x){～P(x)∨(∀y)[～Q(y)∨～L(x,y)]}＝(∀x)(∀y){～P(x)∨～Q(y)∨～L(x,y)}子句集：～P(x)∨～Q(y)∨～L(x,y)错误：取“非”。F2的前束合取范式与子句集：(∃x){P(x)∧(∀y)[R(y)→L(x,y)]}＝(∃x){P(x)∧(∀y)[～R(y)∨L(x,y)]}＝P(a)∧(∀y)[～R(y)∨L(a,y)]＝(∀y){P(a)∧[～R(y)∨L(a,y)]}子句集：{P(a),～R(y)∨L(a,y)}错误：取非结论取非的前束合取范式与子句集：～G＝～{(∀x)[R(x)→～Q(x)]}＝～{(∀x)[～R(x)∨～Q(x)]}＝(∃x)[R(x)∧Q(x)]＝R(b)∧Q(b)子句集为：{R(b),Q(b)}错误：与前面相同的常量符号完整的子句集为：{～P(x)∨～Q(y)∨～L(x,y)P(a)～R(z)∨L(a,z)（改名）R(b)Q(b)}反演过程：(1)～P(x)∨～Q(y)∨～L(x,y)(2)P(a)(3)～R(z)∨L(a,z)(4)R(b)(5)

Q(b)(6)～Q(y)∨～L(a,y)(1)(2)mgu={a/x}(7)～L(a,b)(5)(6)mgu={b/y}(8)L(a,b)(3)(4)mgu={b/z}(9)Φ(7)(8)mgu=Φ

5、编写Prolog程序，并上机调试通过：①已知三个前提F1:：王(Wang)先生是小李(Li)的老师F2：小李与小张(Zhang)是同班同学F3：如果x与y是同班同学，则x的老师就是y的老师。问题：小张的老师是谁？

domainspredicatesteacher(symbol,symbol)classmate(symbol,symbol)clausesclassmate(li,zh