人工智能 谓词演算

重庆交通大学计算机与信息学院验证性实验报告班级：计软专业 13 级 1 班学号： 631306050123姓名：黄嘉城实验项目名称：谓词演算实验项目性质：验证性实验实验所属课程：人工智能实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国实验完成时间： 2016 年 6 月 10 日一、实验目的理解和掌握谓词演算二、实验内容及要求在一个空房间中，机器人将A桌子上的盒子搬移到B桌子上，用选定的编程语言编写程序，演示谓词演算过程。

三、实验设备及软件visual studio四、设计方案㈠题目机器人搬盒子㈡设计的主要思路设在房内c处有一个机器人，在a及b处各有一张桌子，a桌上有一个盒子。

为了让机器人从c处出发把盒子从a处拿到b处的桌上，然后再回到c处，需要制订相应的行动规划。

现在用一阶谓词逻辑来描述机器人的行动过程。

㈢主要功能实现机器人搬盒子移动五、主要代码#include "stdio.h"//定义初始状态char state[10][20]={"AT(robot,c)","EMPTY(robot)","ON(box,a)","TABLE(a)","TABLE(b)"};//定义目标状态char end_state[5][20]={"AT(robot,c)","EMPTY(robot)", "ON(box,b)","TABLE(a)","TABLE(b)"};int state_num=5;int number;//记录某字符串在总数据库中的位置bool IsInState(char *S1) /*判断字符串（状态）是否在总数据库中*/ {int i,j;bool flag;//printf("S1:%s\n state[0]: %s state[1]: %s\n",S1,state[0],state[1]);//printf("%d\n",state_num);for(i=0;i<state_num;i++){j=0;flag=true;while(S1[j]!='\0'){if(S1[j]!=state[i][j]){flag=false;break;}j++;}if(flag && state[i][j]=='\0'){//printf("%d\n",i);number=i;return true;}}return false;}void Delete(int k)/*删除总数据库中的第k个状态（字符串）*/ {if(k>=state_num){printf("The appointed state is not in the state set!");return;}int i,j;for(i=k;i<state_num;i++){for(j=0;*(state[i+1]+j)!='\0';j++)state[i][j]=state[i+1][j];state[i][j]='\0';}state_num--;}void Insert(char *S)/*将状态（字符串S）插入到总数据库中*/ {if(state_num>=10){printf("The state space is overwrited!");return;}int j;for(j=0;S[j]!='\0';j++)state[state_num][j]=S[j];state[state_num][j]='\0';state_num++;}bool GoTo(char x,char y){char S1[20]="AT(robot,x)",S2[20]="AT(robot,x)";//printf("%s,%s\n",S1,S2);S1[9]=x; S2[9]=y;//printf("%s,%s\n",S1,S2);if(IsInState(S1)){Delete(number);Insert(S2);return true;}else{printf("Cannot go from %c to %c\n",x,y);return false;}}bool PickUp(char x){charS[5][20]={"ON(box,x)","TABLE(x)","AT(robot,x)","EMPTY(robot)","HOLDS(robot,box)"};S[0][7]=x;S[1][6]=x;S[2][9]=x;if(IsInState(S[1]) && IsInState(S[2])){if(IsInState(S[0]))Delete(number);else{printf("Cannot pickup %c",x);return false;}if(IsInState(S[3]))Delete(number);else{printf("Cannot pickup %c",x);return false;}Insert(S[4]);return true;}{printf("Cannot pickup %c",x);return false;}}bool SetDown(char x){charS[5][20]={"AT(robot,x)","TABLE(x)","HOLDS(robot,box)","EMPTY(robot)","ON(box,x)"};S[0][9]=x;S[1][6]=x;S[4][7]=x;if(IsInState(S[0]) && IsInState(S[1])){if(IsInState(S[2]))Delete(number);else{printf("Cannot set down %c",x);return false;}Insert(S[3]); Insert(S[4]);return true;}return false;}void ShowState(char s[10][20],int num){int i;printf(" ");for(i=0;i<num;i++)printf("%s ",s[i]);printf("\n");}void main(){printf("the process as follows:\n\nThe start state:\n");ShowState(state,state_num);printf("(1) Go from c To a:\n");if(!GoTo('c','a'))return;ShowState(state,state_num);printf("(2) PickUp a:\n");if(!PickUp('a'))return;ShowState(state,state_num);printf("(3) Go from a To b:\n");if(!GoTo('a','b'))return;ShowState(state,state_num);printf("(4) SetDown b:\n");if(!SetDown('b'))return;ShowState(state,state_num);printf("(5) Go from b To c:\n");if(!GoTo('b','c'))return;ShowState(state,state_num);}六、测试结果及说明实验很成功七、实验体会让我了解到人工智能的先进化，开阔我的眼界通过，本次实验，让我更加了解启发式搜索算法的原理，见识了其广泛的应用；同时加强了本人阅读程序能力和编程能力，以及如何将理论问题解决实际应用的能力。

《人工智能》课后答案第一章课后习题1、对N＝5、k≤3时，求解传教士和野人问题的产生式系统各组成部分进行描述（给出综合数据库、规则集合的形式化描述，给出初始状态和目标条件的描述），并画出状态空间图。

2、对量水问题给出产生式系统描述，并画出状态空间图。

有两个无刻度标志的水壶，分别可装5升和2升的水。

设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。

已知5升壶为满壶，2升壶为空壶，问如何通过倒水或灌水操作，使能在2升的壶中量出一升的水来。

3、对梵塔问题给出产生式系统描述，并讨论N为任意时状态空间的规模。

相传古代某处一庙宇中，有三根立柱，柱子上可套放直径不等的N个圆盘，开始时所有圆盘都放在第一根柱子上，且小盘处在大盘之上，即从下向上直径是递减的。

和尚们的任务是把所有圆盘一次一个地搬到另一个柱子上去（不许暂搁地上等），且小盘只许在大盘之上。

问和尚们如何搬法最后能完成将所有的盘子都移到第三根柱子上（其余两根柱子，有一根可作过渡盘子使用）。

求N＝2时，求解该问题的产生式系统描述，给出其状态空间图。

讨论N为任意时，状态空间的规模。

4、对猴子摘香蕉问题，给出产生式系统描述。

一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到处走动，推移箱子，攀登箱子等）。

设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为a，箱子位置为b，香蕉位置为c），如何行动可摘取到香蕉。

5、对三枚钱币问题给出产生式系统描述及状态空间图。

设有三枚钱币，其排列处在"正、正、反"状态，现允许每次可翻动其中任意一个钱币，问只许操作三次的情况下，如何翻动钱币使其变成"正、正、正"或"反、反、反"状态。

6、说明怎样才能用一个产生式系统把十进制数转换为二进制数，并通过转换141.125这个数为二进制数，阐明其运行过程。

人工智能作业题1 － 1 什么是人工智能？试从学科和能力两方面加以说明。

1 － 4 现在人工智能有哪些学派？它们的任知观是什么？1 － 6 人工智能的主要研究和应用领域是什么？其中，哪些是新的研究热点？2 － 6 用谓词演算公式表示下列英文句子 ( 多用而不是省用不同谓词和项。

例如不要用单一的谓词字母来表示每个句子 ) 。

A computer system is intelligent if it can perform a task which,if performed by a human, requires intelligence.2 － 7 把下列语句表示成语义网络描述：(1) All man are mortal.(2) Every cloud has a silver liming.(3) All branch managers of DEC participate in a profit-sharing plan.2 － 9 试构造一个描述你的寝室或办公室的框架系统。

补充题：1 、张某被盗，公安局派出五个侦察员去调查。

研究案情时，侦察员 A 说“赵与钱中至少有一人作案”；侦察员 B 说“钱与孙中至少有一人作案”；侦察员C 说“孙与李中至少有一人作案”；侦察员 D 说“赵与孙中至少有一人与此案无关”；侦察员 E 说“钱与李中至少有一人与此案无关”。

如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。

3 －4 如何通过消解反演求取问题的答案？3 － 11 规则演绎系统和产生式系统有哪几种推理方式？各自的特点为何？3 － 6 下列语句是一些几何定理，把这些语句表示为基于规则的几何证明系统的产生式规则：(1) 两个全等三角形的各对应角相等。

(2) 两个全等三角形的各对应边相等。

3 － 17把下列句子变换成子句形式：4 － 1 计算智能的含义是什么？它涉及哪些研究分支？4 － 6 构作一个神经网络，用于计算含有两个输入的 XOP 函数。

人工智能概论中英文术语对照表动作action专家系统Expert system人工智能语言AI language祖先过滤形策略ancestry-filtered form strategy与节点AND node与或图AND/OR graph与或树AND/OR tree回答语句answer statement人工智能artificial intelligence,AI原子公式atomic formula自动定理证明automatic theorem provingB规则B-rule倒退值backed-up value回溯backtracking盲目搜索，无信息搜索blind search宽度优先搜索breadth-first search子句clause组合爆炸combinatorial explosion冲突解决conflict resolution合取式conjunct合取conjunction合取范式conjunctive normal form连词，连接词connective一致解图consistant solution graph控制策略control strategy费用cost演绎deduction深度优先搜索depth-first search推导表，引导图derivation graph差别difference有向图directed graph析取式disjunct析取disjunction谓词演算辖域domain in predicate calculus论域，文字域domain of discourse搜索算法的效率efficiency of search algorithm空子句empty clause等价equivalence估计费用estimated cost估值函数evaluation function存在量词existential quantifier扩展节点expending node节点的扩展expansion of nodeF规则F-rule事实fact一阶谓词演算first order predicate calculus 博弈game图graph图表示法graph notation图搜索graph search图搜索控制策略graph-search control strategy 启发函数heuristic function启发信息heuristic information启发搜索heuristic search蕴涵，蕴涵式implication推理inference智能intelligence解释器interpreter知识knowledge知识获取knowledge acquisition全局数据库Global database知识库knowledge base知识工程knowledge engineering学习learning启发式搜索Heuristic search线形输入形策略linear-input form strategy文字literal逻辑logic逻辑连词logic connective逻辑推理logic reasoning匹配match模式匹配match pattern母式matrix最一般合一者most general unifierNP完全问题NP-complete problem算符、算子、操作符operator最优解树optimal solution tree有序搜索ordered search谓词predicate谓词演算predicate calculus谓词逻辑predicate logic前缀prefix本原问题primitive problem问题归约problem-reduction问题求解problem solving产生式production产生式规则production rule量词quantifier推理reasoning正向推理forward reasoning逆向推理backward reasoning推理机reasoning machine归约reduction反演refutation反演树refutation tree归结resolution归结原理resolution principle归结反演resolution refutation归结式resolvent可满足性satisfiability模式识别Pattern recognition量词辖域scope of quantifier搜索search, searching搜索算法searching algorithm搜索图searching graph搜索策略searching strategy搜索树searching tree句子sentence解图solution graph解树solution tree可解节点solvable node可解标示过程solvable labeling procedure 状态state状态空间state space代换例substitution instance代换substitution重言式tautology项term定理证明theorem-proving不确定性uncertainty合一unifier最一般合一most general unifier全称量词universal quantifier不可满足集unsatisfiable set不可解标示过程unsolvable-labeling procedure 不可解节点unsolvable node永真式validity合适公式、合式公式well-formed formula (wff)谓词演算公式wffs of predicate calculus人工神经网络artificial neural network遗传算法genetic algorithm机器学习machine learning。

人工智能作业题1 － 1 什么是人工智能？试从学科和能力两方面加以说明。

1 － 4 现在人工智能有哪些学派？它们的任知观是什么？1 － 6 人工智能的主要研究和应用领域是什么？其中，哪些是新的研究热点？2 － 6 用谓词演算公式表示下列英文句子 ( 多用而不是省用不同谓词和项。

例如不要用单一的谓词字母来表示每个句子 ) 。

A computer system is intelligent if it can perform a task which,if performed by a human, requires intelligence.2 － 7 把下列语句表示成语义网络描述：(1) All man are mortal.(2) Every cloud has a silver liming.(3) All branch managers of DEC participate in a profit-sharing plan.2 － 9 试构造一个描述你的寝室或办公室的框架系统。

补充题：1 、张某被盗，公安局派出五个侦察员去调查。

研究案情时，侦察员 A 说“赵与钱中至少有一人作案”；侦察员 B 说“钱与孙中至少有一人作案”；侦察员 C 说“孙与李中至少有一人作案”；侦察员 D 说“赵与孙中至少有一人与此案无关”；侦察员 E 说“钱与李中至少有一人与此案无关”。

如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。

3 －4 如何通过消解反演求取问题的答案？3 － 11 规则演绎系统和产生式系统有哪几种推理方式？各自的特点为何？3 － 6 下列语句是一些几何定理，把这些语句表示为基于规则的几何证明系统的产生式规则：(1) 两个全等三角形的各对应角相等。

(2) 两个全等三角形的各对应边相等。

3 － 17 把下列句子变换成子句形式：4 － 1 计算智能的含义是什么？它涉及哪些研究分支？4 － 6 构作一个神经网络，用于计算含有两个输入的 XOP 函数。