人工智能技术实验指导书

实用文档人工智能技术实验指导书目录前言………………………….1实验一刺激响应Agent实验…………….2实验二能计划的Agent实验（一）………4实验三能计划的Agent实验（二）………6实验四双Agent博弈实验（一）…………7实验五双Agent博弈实验（二）…………9实验六谓词逻辑与归结原理实验（一）…………………11实验七谓词逻辑与归结原理实验（二）…………………13实验八学习Agent实验…………………15前言人工智能技术实验是为了结合研究生人工智能理论课程的学习而开设的一门实践教学课程，要求学生通过本课程的学习巩固并进一步深入理解理论学习所介绍的人工智能的基本原理与方法，掌握人工智能一些主要技术的实现方法，提高人工智能程序的设计和使用程序设计语言实际编程的能力。学习本课程要求学生掌握程序设计基本知识和至少一种程序设计语言，学过人工智能原理。 本实验指导书中共有八个实验，涵盖了人工智能的一些基本技术，包括能对周围环境进行探测并做出响应的刺激响应Agent实验；能在解空间中进行搜索，寻找问题求解方法的能计划的Agent实验；能够在游戏中与对手较量的双Agent博弈实验；能够进行逻辑推理的谓词逻辑与归结原理实验；能够进行学习和优化的学习Agent实验等。其中，实验三、实验五、实验七相对于实验二、实验四、实验六要复杂一些，可供学生根据自己的基础和程序设计能力选做。实验指导书对每个实验首先提出了实验目的和要求，主要指出通过实验所要掌握的人工智能的基本技术；然后简单介绍与该实验相关的人工智能技术的基本知识，以便读者回忆和复习人工智能原理的有关内容，为完成实验做好准备；最后给出了实验内容和进行方式，具体给出实际的应用环境和要解决的问题以及对程序功能的要求。实验一刺激响应Agent实验实验目的与要求目的：掌握产生式系统的结构和设计方法，了解刺激响应Agent的工作原理。要求：设计生活在一个二维网格世界中的“人工蚂蚁”的模拟程序。基本知识刺激响应（stimulus-response）Agent指的是没有内部状态而只是对所感知到的环境刺激给出简单反应的机器。刺激响应Agent是具有传感器和效应器、处于某一环境中的实体。它通过传感器感知环境，通过效应器作用于环境。这种Agent能够对环境主动进行监视，并能做出必要的反应。刺激响应Agent最典型的应用是机器人，特别是Brookes类型的机器昆虫。实验内容与进行方式“人工蚂蚁”生活在一个二维网格世界中，它能沿已作标记的单元所组成的连续“信息素踪迹”(宽为一个单元)的运动。这个蚂蚁占一个单元，它可以面向东、南、西、北。它能做五个动作：前移一个单元(m)；在同一单元中向左转(l)；在同一单元中向右转(r)；设置状态位元“开”(on)；设置状态位元“关”(off)。蚂蚁感知它的正前方(即其面朝的方向)是否有信息素踪迹且其状态位元是否为“开”，若状态位元为“开”表示该单元已经走过（设状态位元起初为“关”）。如图一中黑色的单元组成了信息素踪迹，红色的圆形表示人工蚂蚁。描述可以控制这样一个跟踪以上路线的蚂蚁的一个产生式系统。设这个蚂蚁最初位于一个可感知的信息素踪迹单元中，面向东方（请记住，产生式系统由一个有序的条件—动作规则集合组成；所执行的动作与首先满足的那个条件相应。每个规则的动作部分可以有一个以上的动作）。确保蚂蚁不会折反自己走过的路线。写一个模拟人工蚂蚁行为的算法，并编制程序，分别对图中的三只蚂蚁，给出运行的结果。北س图一人工蚂蚁的网格世界附：蚁群算法简介20世纪90年代初意大利学者Dorigo，Maniezzo提出的第一个“蚁群算法（antcolonyalgorithm）”是依照蚂蚁觅食原理，设计的一个群体智能的算法。其原理如下。据研究当蚂蚁找到食物并将它搬回来时，就会在其经过的路径上留下一种“外激素”，其他蚂蚁嗅到这个激素的“味道”，就沿该路奋勇向前，觅食而去。不但如此而且还会沿着最短的路径奔向食物。下面我们分析一下蚂蚁是如何找到通向食物的最短路径的呢？设一群蚂蚁（随机地）从蚁巢O向四面八方去觅食，当某只蚂蚁在A点觅到食物时，一般就沿原路回巢，同时在归途上留下外激素，外激素随着向四周散发其浓度会不断下降。若有两只蚂蚁分别沿路径OBA和路径OA找到食物，且沿原路返回（见图一）设OA比OBA短，当第一只蚂蚁回到O点时，第二只蚂蚁（沿OBA的蚂蚁）才回到C点。于是OA路上有两次外激素的遗留物（去一次、回来一次），而在OC路是只有去一次的外激素遗留物，故OA的外激素浓度比OC上大。据研究蚂蚁一般会沿外激素浓度大的路径上前BCOA图二蚂蚁觅食路径示意图行，于是后面的蚂蚁会渐渐地沿由O到A的最短程到达A点（指所有已求到的路径中的最短者）。以上就是蚂蚁能以最短路径找到食物的原因。根据这个原理可以设计出求最短路径的蚁群算法。下面以求通过n个城市的最短回路为例。设有n个城市，在t时刻在第i个城市上有蚂蚁ai(t)个，共有m个蚂蚁。设在t时刻在连接第i,j两城市间的道路留下的外激素量为bij(t)。规定每个蚂蚁在未完成一个回路时,不重复走已走过的城市。则第k个蚂蚁从i城市到j城市的概率Pijk=bPijk=l允许到达的城市bil(t)其中外激素量bij(t)有许多不同的定义,如可定义为：b(t)=e-ct，c>0；或定义为：bij(t+1)=dbij(t)+dij(t)，其中dij(t)=k=1..m(e/Lk)ijk(t)，d、e为正常量，Lk是第k个蚂蚁求得的回路长度，若第t轮第k只蚂蚁经过边(i,j)则ijk(t)=1，否则ijk(t)=0。这样每只蚂蚁经过n次迁移后就得到一条回路,其长度记为Lk.若满足要求,则停止。不然，利用(1)式重新计算各边的外激素浓度,进行第二轮的搜索。借助蚂蚁的启迪，不但可以开发出求最短程的算法，还可以开发出其它的算法，下面再举一、二。据说蚂蚁很爱卫生，对其窩内经常进行大扫除，将垃圾堆在一起，然后拉到窩外。根据蚂蚁的上述行为，人们以蚂蚁为师设计分类算法：一群蚂蚁随机出发，遇到垃圾，就将其拉走（拉的方向也是随机的），拉垃圾时，若遇到某一堆垃圾时，就放下。放下垃圾后，再次进行拉垃圾行为。当然还要加了一些限制，才能达到人们所希望的结果。另外，蚂蚁同心协进行搬运食物，是我们见得最多的蚂蚁行为，有人以此为蓝本设计出几个机器人共同推盒子的算法。借助蚂蚁分工合作的特点（蚁皇管生男育女、工蚁管干活、兵蚁管保卫）的启迪，人们设计了求解任务分配问题的蚂蚁算法，并应用于工厂中汽车喷漆问题。工人分成小组，各组只喷一种颜色，只有当某小组任务特别紧张时，才分配另一小组前去帮助。通过这种设计后工厂各车间改变颜色的次数更少，从而提高了整体的生产率。实验二能计划的Agent实验（一）实验目的与要求目的：熟悉状态空间的基本搜索方法，比较盲目搜索算法、A算法和A*算法。要求：编制一个15数码难题解题程序。基本知识状态图实际上是一类问题的抽象表示。事实上，有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。因此，研究状态图搜索具有普遍意义。状态图中的状态是表示问题求解过程中每一步问题状况的数据结构，包括由问题已知的前提、初始条件的原始描述所构成的初始状态，问题解决时应该到达的目标状态以及问题求解过程中由初始状态可能到达的中间状态。状态图中的边为操作，操作是把一种状态变成另一种状态的运算。在状态空间中进行搜索，以找到一条从初始状态到达目标状态的（最佳）路径的方法称为状态空间法。产生式系统由三部分组成：产生式规则库、推理机和动态数据库。产生式规则库亦称产生式规则集，由领域规则组成，在机器中以某种动态数据结构进行组织。推理机亦称控制执行机构，它是一个程序模块，负责产生式规则的前提条件测试或匹配，规则的调度与选取，规则体的解释和执行。即推理机实施推理，并对推理进行控制，它也就是规则的解释程序。产生式系统运行时，除了需要规则库以外，还需要有初始事实(或数据)和目标条件。目标条件是系统正常结束的条件，也是系统的求解目标。产生式系统启动后，推理机就开始推理，按所给的目标进行问题求解。一个实际的产生式系统，其目标条件一般不会只经一步推理就可满足，往往要经过多步推理才能满足或者证明问题无解。可以看出，图搜索与产生式系统实际是一回事。要说差别的话，图搜索技术描述了问题求解的方法，而产生式系统则给出了实施这种方法的一种计算机程序系统的结构模式。这样，问题求解、图搜索和产生式系统三者的关系是：问题求解是目的，图搜索是方法，产生式系统是形式。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索和启发式（heuristic）搜索两大类。盲目搜索按搜索树生成方式可分为广度优先和深度优先两种搜索方式。这两种方式也是最基本的树式搜索策略，其他搜索策略都是建立在它们的基础之上的。广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进，直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。启发式搜索就是利用启发性信息进行制导的搜索。穷举搜索法从理论上讲，似乎可以解决任何状态空间的搜索问题，但实践表明，穷举搜索只能解决一些状态空间很小的简单问题，而对于那些大状态空间问题，穷举搜索就不能胜任了。因为大空间问题，往往会导致“组合爆炸”。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息一般可以(1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。(2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。(3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。在启发式搜索中，通常用所谓启发函数来表示启发性信息。启发函数是用来估计搜索树上节点与目标节点接近程度的一种函数，通常记为h(x)。启发函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：一个节点到目标节点的某种距离或差异的度量；一个节点处在最佳路径上的概率；或者根据经验的主观打分等等。启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。下面介绍两种典型的启发式图搜索的A算法和A*算法。利用启发函数h(x)制导的启发式搜索，实际是一种深度优先的搜索策略。虽然它是很高效的，但也可能误入歧途。所以，为了更稳妥一些，人们把启发函数扩充为估价函数。估价函数的一般形式为f(x)＝g(x)＋h(x)其中g(x)为从初始节点S0到节点x已经付出的代价，h(x)是启发函数。即估价函数f(x)是从初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值之总和。A算法是基于估价函数f(x)的一种加权状态图启发式搜索算法。如果对上述A算法再限制其估价函数中的启发函数h(x)满足：对所有的节点x均有h(x)≤h*(x)其中h*(x)是从节点x到目标节点的最小代价(若有多个目标节点则为其中最小的一个)，则它就称为A*算法。实验内容与进行方式数码问题常被用来演示如何在状态空间中生成动作序列。一个典型的例子是15数码问题，它由放在一个4×4的棋盘中的15个数码构成，棋盘中的一个单元是空的，它的周边单元中的数码可以移到该单元中。此问题的任务是找到一个数码移动序列使初始的无序数码转变为一些特殊的排列。8数码问题是一个简化版本，在一个3×3的棋盘中有8个数码。假定该问题的目标是把数码从开始状态移动到目标状态，如图8-1所示。在这个问题中，一个明显的问题状态描述是一个3×3的方阵，方阵的每个单元中包含1～8之间的数字或一个代表空格的符号。目标状态是图8-1中右边的方阵。状态间的转变就是把一个数码移到空的单元中。一般地讲，在构造一个问题的状态空间时我们有一些代表性的选择。在8数码问题中，我们可以想像有8×4个不同的移动，它们是：1上移、1下移、1左移、1右移、2上移、...，等等（当然在一个给定的状态中，并不是所有的这些移动都是可能的）。一个更精练的选择只有4个移动，即：空格左移、空格上移、空格右移和空格下移。一个给定的开始状态和一组可能的移动隐式地定义了从开始状态可到达的状态空间图。在8数码表示的状态空间中节点数是9！=362880个（8数码状态空间刚好可以分成两个独立的图；一个图中的状态不能从另一个图中的状态到达）。图三8数码问题的开始和目标状态 请分别给出用盲目搜索算法、A算法和A*算法解决15数码难题的算法，并编制程序对于任意输入的初始棋局和目标棋局，求出解决的步骤。并通过具体的例子比较三种算法的性能。注意：给的例子是8数码难题，要求解决的是15数码难题。实验三能计划的Agent实验（二）实验目的与要求目的：进一步掌握启发式搜索的方法，学习分析问题获得启发信息的方法。要求：完成Caesar密码破解程序。基本知识启发式搜索就是利用启发性信息进行制导的搜索。穷举搜索法从理论上讲，似乎可以解决任何状态空间的搜索问题，但实践表明，穷举搜索只能解决一些状态空间很小的简单问题，而对于那些大状态空间问题，穷举搜索就不能胜任了。因为大空间问题，往往会导致“组合爆炸”。启发性信息就是有利于尽快找到问题之解的信息。正确地选择启发函数对搜索结果起着决定的作用：使用不能识别某些节点真实价值的启发函数会得到非最佳解，而使用一个过多地估计了全部节点希望的启发函数又会扩展过多的节点。如用f(x)=g(x)，就得到宽度优先的搜索过程。好的启发函数依赖于对问题本身的认识——知识。因为启发信息与要求解的实际问题相关，启发函数要根据对问题的了解和相关知识来设计，使得搜索过程可以在启发信息制导下向着求解目标进行，大大提高搜索效率。实验内容与进行方式Caesar密码是一种简单的基于字母表循环置换的加密方案，即字母表中的第i个字母用字母表中的第（i+n）个字母替换，其中n为偏移量。例如，在偏移量为4的Caesar密码系统中，“Caesar”会被加密为“Geiwev”。要求给出一种用于破解Caesar密码的启发函数，并设计出破解程序完成破解Caesar密码的实验。另一种在Caesar密码基础上加以改进的简单的置换加密方案是每一个字母以某种任意的一对一映射方式用另外一个字母替换。请给出用于破解这种密码的一个启发函数，设计出破解程序。说明：此实验中搜索的目标节点不是显式的，需要设置一定的判别条件。实验四双Agent博弈实验（一）实验目的与要求目的：掌握敌对搜索的基本方法。要求：完成二维网格中的机器人“追捕”程序。基本知识诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。其中最简单的一种称为“二人零和、全信息、非偶然”博弈。所谓“二人零和、全信息、非偶然”博弈是指：(1)对垒的A，B双方轮流采取行动，博弈的结果只有三种情况：A方胜，B方败；B方胜，A方败；双方战成平局。(2)在对垒过程中，任何一方都了解当前的格局及过去的历史。(3)任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自己最为有利而对对方最为不利的对策，不存在“碰运气”的偶然因素。即双方都是很理智地决定自己的行动。在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。这样，如果站在某一方（如A方，即在A要取胜的意义下），把上述博弈过程用图表示出来，则得到的是一棵“与或树”。描述博弈过程的与或树称为博弈树，它有如下特点：(1)博弈的初始格局是初始节点。(2)在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流地扩展节点。(3)所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。在二人博弈问题中，为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案，就需要对当前的情况以及将要发生的情况进行分析，从中选出最优的走步。最常使用的分析方法是极小极大分析法。其基本思想是：(1)设博弈的双方中一方为A，另一方为B。然后为其中的一方(例如A)寻找一个最优行动方案。(2)为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较。(3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。(4)当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”（MAX）节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”（MIN）节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。(5)如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。图4—18给出了计算倒推值的示例。上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值。这样做的缺点是效率较低。于是,人们又在极小极大分析法的基础上,提出了α—β剪枝技术。具体的剪枝方法如下：(1)对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β,则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。(2)对于一个“或”节点MAX，若能估计出其倒推值的下确界α,并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β,即α≥β,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为β剪枝。实验内容与进行方式以图三中的网格为例，两个机器人，分别命名为“black”和“white”。它们可以向其所在的行或列中的相邻一格交替地移动（比如说，white先移动），而且轮到其中一个时，它必须移动。假设white的目标是与black在同一格，而black的目标是避免发生这种情况。white就可建立一棵搜索树，在交替的级别上，black可能的行动也被考虑进去。请为white编写一个追捕black的程序，试试用键盘控制black时，white移动的情况。再为black编写一个逃避white追捕的程序，看看在某种初始局面下，计算机自动运行追捕过程的情况。对每个程序，给出算法描述，并给出能说明两个机器人移动过程的运行结果。图四在网格环境中的两个机器人实验五双Agent博弈实验（二）实验目的与要求目的：掌握带有机会因素的博弈搜索方法。要求：编写西洋双陆棋博弈程序。基本知识在实际生活中存在许多不可预测的外部事件迫使我们陷入未预见到的情境中。一些游戏含有某种随机的因素如掷骰子来反映这种不可预测性。这样使我们更接近实际，因此值得研究这种不可预测性是如何影响决策过程的。西洋双陆棋是典型的机会与技巧相结合的游戏。轮到的一方游戏者首先掷骰子来决定他可以采用的合法的走步集合。在下图所示的西洋双陆棋棋局中，白方掷了6-5，所以有5种可能的走步：(5-10,5-11),(5-11,19-24),(5-10,10-16),(5-11,11-16),(5-10,19-25)。012345678910111225242322212019181716151413图五一个典型的西洋双陆棋棋局尽管白方知道自己的合法走步，但他并不知道黑方掷骰子将会掷出什么样的结果来，从而也不知道什么将是黑方的合法走步。这意味着白方不可能构造完整的博弈树。西洋双陆棋的博弈树除了极大极小节点还必须包括机会节点。在图六中，圆形的节点为机会节点。从每个机会节点引出的分支表示掷骰子的可能性，每个分支上标明掷出的点数和其出现的概率。掷两个骰子共有36种结果，每种结果都有相同的可能性；但是，因为6-5和5-6的效果是一样的，所以实际上只有21种不同的结果。两个骰子点数相同的情况有6种(1-1至6-6)，每种出现的机会为1/36，其他15种不同的组合出现的机会各为1/18。下一步是分析怎样做出正确的决策。显然，我们希望选择导致最好棋局的走步。但是，每一个可能的棋局不再具有确定的极小极大值（在确定性博弈中该值是最好下法所到达的叶节点的估价值）。取而代之，我们只能计算一个平均值或期望值，这里平均值是在可能出现的所有掷骰子的结果上计算得到的。MAXBBDICE1/366,61/186,51/181,21/366,61/186,51/181,21/361,1MINCCDICE1/366,61/186,51/181/366,61/186,51/181,21/361,1MAXTERMINAL2-11-11图六西洋双陆棋的博弈树计算节点的期望值是简单的。对于端节点，像确定性博弈一样我们使用估价函数计算。在搜索树向上一层，我们遇到一个机会节点。在图六中机会节点是圆圈；我们看一下标记为C的节点。设di是一种可能的掷骰子的点数，P(di)是掷得该点数的机会或概率。对每一次投掷，我们计算MIN最好走步的棋局估价值，然后求所有估价值的加权和，每个估价值的权为掷得该点数的概率。如果用S(C,di)表示在棋局C下掷得概率为p(di)的点数di其中，utility(s)为棋局s的估价值。这就给出了在棋局C下采取最好的走步所得到棋局的期望估价值。再向上一层为MIN节点（图中为倒三角形），因为我们已经计算了所有机会节点的估价值，现在可用极小极大值公式得到MIN节点的估计值。进一步我们向上移动到机会节点B，在此可以采用与期望最大值类似的公式计算其期望极小值。 这一过程可以沿着博弈树向上反复应用，除了已经知道掷得点数的最顶层。所以，为了计算最好的走步，我们只要把确定的博弈树中的极小极大值换成期望极小极大值就行了。实验内容与进行方式 西洋双陆棋类似于飞行棋。开始时双方各自的15枚棋分别从棋盘外（相当于图五中标示的0和25的位置）进入棋盘，游戏的目标是将自己所有的棋通过棋盘走一遍再移出棋盘。白棋从0开始顺时针方向移向25，黑棋从25逆时针方向移向0。每次可移动两个棋，移动的步数由掷两枚骰子决定。如果一个位置上已经有对方的两个或更多的棋，则本方的棋不能移到该位置。如果自己的棋移动到的位置恰好有对方的一个棋，则可将对方的棋吃掉，被吃掉的棋要从头开始走。在图五所示的棋局，白方掷了6和5，可以选择将两个在第5格的白棋分别走5步和6步，即走到第10格和第11格，记作(5-10,5-11)。另外4种合法的走步是(5-11,19-24),(5-10,10-16),(5-11,11-16),(5-10,19-25)。根据上面的介绍，设计一种对西洋双陆棋棋局的估价函数，并实现相应的人机对弈的下棋程序。其中掷骰子的结果可用随机数产生，棋盘可以画得简单一些。实验六谓词逻辑与归结原理实验（一）实验目的与要求目的：掌握基于一阶逻辑的知识表达方法，熟悉消解原理在问题求解中的应用。要求：编写逻辑电路功能诊断与推理程序。基本知识设a1,a2,…,an表示个体对象，A表示它们的属性、状态或关系，则表达式A(a1,a2,…,an)在谓词逻辑中就表示一个(原子)命题。例如，(1)素数(2)，就表示命题“2是个素数”。(2)好朋友（张三，李四），就表示命题“张三和李四是好朋友”。一般地，表达式P(x1,x2,…,xn)在谓词逻辑中称为n元谓词。其中P是谓词符号，也称谓词，代表一个确定的特征或关系(名)。x1,x2,…,xn称为谓词的参量或者项，一般表示个体。个体变元的变化范围称为个体域（或论述域），包揽一切事物的集合称为全总个体域。为了表达个体之间的对应关系，我们引入通常数学中函数的概念和记法。例如我们用father(x)表示x的父亲，用sum(x,y)表示数x和y之和。一般地，我们用f(x1,x2,…,xn)表示个体变元x1,x2,…,xn所对应的个体y，并称之为n元个体函数，简称函数（或函词、函词命名式）。其中f是函数符号，有了函数的概念和记法，谓词的表达能力就更强了。例如，我们用Doctor(father(Li))表示“小李的父亲是医生”，用E(sq(x),y))表示“x的平方等于y”。约定用大写英文字母作为谓词符号，用小写字母f,g,h等表示函数符号，用小写字母x,y,z等作为个体变元符号，用小写字母a,b,c等作为个体常元符号。我们把“所有”、“一切”、“任一”、“全体”、“凡是”等词统称为全称量词，记为x;把“存在”、“有些”、“至少有一个”、“有的”等词统称为存在量词，记为x。引入量词后，谓词的表达能力就大大扩充了，例如命题“凡是人都有名字”，就可以表示为"x(M(x)→N(x))，其中M(x)表示“x是人”，N(x)表示“x有名字”，该式可读作“对于任意的x，如果x是人，则x有名字”。这里的个体域取为全总个体域。如果把个体域取为人类集合，则该命题就可以表示为"xN(x)。同理，我们可以把命题“存在不是偶数的整数”表示为$x(G(x)∧E(x))，其中G(x)表示“x是整数”，E(x)表示“x是偶数”。此式可读作“存在x，x是整数并且x不是偶数”。不同的个体变元，可能有不同的个体域。为了方便和统一起见，我们用谓词表示命题时，一般总取全总个体域，然后再采取使用限定谓词的办法来指出每个个体变元的个体域。具体来讲，有下面两条：(1)对全称量词，把限定谓词作为蕴含式之前件加入，即"x(P(x)→…)。(2)对存在量词，把限定量词作为一个合取项加入，即$x(P(x)∧…)。这里的P(x)就是限定谓词。再举几个例子：1、不存在最大的整数，我们可以把它翻译为$x(G(x)∧"y(G(y)→D(x,y))或"x(G(x)→$y(G(y)∧D(y,x))。2、对于所有的自然数均有x+y>x，"x"y(N(x)∧N(y)→S(x,y,x))。3、某些人对某些食物过敏，$x$y(M(x)∧F(y)∧G(x,y))。谓词公式：(1)个体常元和个体变元都是项。(2)设f是n元函数符号，若t1,t2,…,tn是项，则f(t1,t2,…,tn)是项。(3)只有有限次使用(1)，(2)得到的符号串才是项。(4)设P为n元谓词符号，t1,t2,…,tn为项，则P(t1,t2,…,tn)称为原子谓词公式，简称原子公式或者原子。(5)原子公式是谓词公式。(6)若A,B是谓词公式，则A,A∧B,A∨B,A→B,AB,$xA,"xA也是谓词公式。(7)只有有限步应用(5)，(6)生成的公式才是谓词公式。由项的定义，当t1,t2,…,tn全为个体常元时，所得的原子谓词公式就是原子命题公式（命题符号）。所以，全体命题公式也都是谓词公式。谓词公式亦称为谓词逻辑中的合适（式）公式，记为Wff。子句集：原子谓词公式及其否定称为文字，若干个文字的一个析取式称为一个子句，由r个文字组成的子句叫r—文字子句，1—文字子句叫单元子句，不含任何文字的子句称为空子句，记为或NIL。例如P∨Q∨R，P(x,y)∨Q(x)都是子句对一个谓词公式G，通过以下步骤所得的子句集合S，称为G的子句集。(1)消去蕴含词→和等值词。可使用逻辑等价式:①A→BA∨B②AB(A∨B)∧(B∨A)(2)缩小否定词的作用范围，直到其仅作用于原子公式。可使用逻辑等价式:①(A)A②(A∧B)A∨B③(A∨B)A∧B④"xP(x)Û$xP(x)⑤$xP(x)Û"xP(x)(3)适当改名，使量词间不含同名指导变元和约束变元。(4)消去存在量词。消去存在量词时，同时还要进行变元替换。变元替换分两种情况：①若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元，这样的函数称为Skolem函数；②若该存在量词不在任何全称量词的辖域内，则用一个常量符号代替该存在量词辖域中的相应约束变元，这样的常量符号称为Skolem常量。(5)消去所有全称量词。(6)化公式为合取范式。可使用逻辑等价式:①A∨(B∧C)Û(A∨B)∧(A∨C)②(A∧B)∨CÛ(A∨C)∧(B∨C)(7)适当改名，使子句间无同名变元。(8)消去合取词∧，以子句为元素组成一个集合S。例：求下面谓词公式的子句集"x{"yP(x,y)→"y［Q(x,y)→R(x,y)］}解由步(1)得"x{"yP(x,y)∨"y［ØQ(x,y)∨R(x,y)］}由步(2)得"x{$yØP(x,y)∨"y［ØQ(x,y)∧R(x,y)］}由步(3)得"x{$yØP(x,y)∨"z［ØQ(x,z)∧R(x,z)］}由步(4)得"x{ØP(x,f(x))∨［ØQ(x,g(x))∧R(x,g(x))］}由步(5)得P(x,f(x))∨［ØQ(x,g(x))∧R(x,g(x))］由步(6)得［P(x,f(x))∨ØQ(x,g(x))］∧［P(x,f(x))∨R(x,g(x))］由步(7)得［P(x,f(x))∨Q(x,g(x))］∧［P(y,f(y))∨R(y,g(y))］由步(8)得{P(x,f(x))∨Q(x,g(x)),P(y,f(y))∨R(y,g(y))}或P(x,f(x))∨Q(x,g(x))P(y,f(y))∨R(y,g(y))为原谓词公式的子句集。命题逻辑中的归结原理（亦称为消解原理）设L为一个文字，则称L与ØL为互补文字。设C1,C2是命题逻辑中的两个子句，C1中有文字L1，C2中有文字L2，且L1与L2互补，从C1,C2中分别删除L1,L2，再将剩余部分析取起来，记构成的新子句为C12，则称C12为C1,C2的归结式(或消解式)，C1,C2称为其归结式的亲本子句，L1,L2称为消解基。归结式是其亲本子句的逻辑结果。例：设C1=ØP∨Q∨R,C2=ØQ∨S,于是C1,C2的归结式为ØP∨R∨S若先把诸前提条件化为子句形式，再把结论R的非也化为子句，由所有子句得到子句集S，然后对该子句集施行归结，若最后推出了空子句，所以子句集S不可满足，从而R是题设前提的逻辑结果。实验内容与进行方式下面的逻辑电路有4条线，W1，W2，W3和W4。它有一个“与门”A和一个“反相器”B。输入线W1和W2或者是“on”或者不是“on”。若与门A运行“OK”，则当且仅当W1和W2都是“on”时W3才是“on”。如果反相器B运行“OK”，则当且仅当W3不是“on”时W4才是“on”。1)使用形如OK(A)、ON(W1)的表达式描述所定义的电路功能。2)使用描述电路功能的公式，假定所有的元件都是运行正确的，并且W1和W2是“on”，用归结法证明W4不是“on”。3)再次使用描述电路功能的公式，给定W1和W2是“on”，且W4也是“on”，用归结法证明或者与门或者反相器不是运行正确的。 试描述一个算法并编制程序完成对上述逻辑电路故障的诊断。实验七谓词逻辑与归结原理实验（二）实验目的与要求目的：掌握从归结过程中提取答案的问题求解方法。要求：编写个人理财顾问程序。基本知识由上一个实验可知，若先把诸前提条件化为子句形式，再把结论R的非也化为子句，由所有子句得到子句集S，然后对该子句集施行归结，若最后推出了空子句，则子句集S不可满足，从而R是题设前提的逻辑结果。在很多问题中，我们不仅要证明存在满足某个谓词的对象，还要推出究竟是哪个对象满足该谓词，这样能推出具体满足所说结论的对象的证明称为推定证明。而在归结反演过程中，我们可以跟踪变量替换过程，当证明结论成立时，即归结得到空子句时，替代表示结论的谓词中的变量的对象即是我们想要得到的满足结论的具体对象，这样就可以从归结反演中提取问题的具体答案。实验内容与进行方式个人理财顾问的作用是帮助客户决定是将资金存入银行储蓄账户还是投资到股票市场。有些投资者可能希望将他们的资金分别投放在这两个方面。根据个人的收入和当前已经存储的金额，理财顾问按照以下准则向个人投资者提出投资建议：1、储蓄不够的个人不论他们的收入多少总是应将增加储蓄额放在优先的地位。2、已有足够储蓄并且有足够收入的人应考虑股票市场具有一定风险但收益较大的投资。3、已经有足够储蓄而收入较低的人可考虑将他们多余的收入分开投放在储蓄和股票两方面，以增加储蓄的保障同时力图通过股票增加收入。储蓄和收入是否足够由个人要供养的人数来决定。我们的规则是对每个要供养的人至少要有银行存款5000元。而足够的收入必须是每年至少15000元以及对每个要供养的人附加额外的4000元的稳定收入。为自动实现上述机制，我们将其用谓词演算公式表示。首要任务是确定必须考虑的主要因素，即足够的储蓄和收入。我们分别用谓词Savings_account和Income。它们两者都是一元谓词，其参数可以是Adequate或Inadequate。于是它们的值可能是Savings_account(Adequate).Savings_account(Inadequate).Income(Adequate).Income(Inadequate).结论用一元谓词Investment表示，其参数可能的值为Stocks，Savings或Combination（表示将资金分开投放）。采用以上谓词，不同的投资方案可用蕴含式表示。第一条规则，具有不充分储蓄的人应当将增加储蓄放在第一位，被表示为Savings_account(Inadequate)→Investment(Savings).类似地，其余两种可能的投资方案表示为Savings_account(Adequate)∧Income(Adequate)→Investment(Stocks).Savings_account(Adequate)∧Income(Inadequate)→Investment(Combination).下面顾问必须确定储蓄和收入是否充足。这也可用蕴含式来实现。需要用函数完成算术运算。定义函数minsavings来确定最小的充足的储蓄量。minsavings有一个参数即所供养的人数，返回5000与人数的乘积。利用minsavings，储蓄的充足性由规则"xAmount_saved(x)∧$y(Dependents(y)∧Greater(x,minsavings(y)))→Savings_account(Adequate)"xAmount_saved(x)∧$y(Dependents(y)∧Greater(x,minsavings(y)))→Savings_account(Inadequate)决定。其中minsavings(x)=5000×x。在此定义中，Amount_saved(x)和Dependents(y)表示投资者当前储蓄量和他所供养的人数；Greater(x,y)是一个数是否大于另一个数的标准的算术检测，在此没有进一步定义。类似地，函数minincome定义为minincome(x)=15000+(4000×x)，它被用来在给定供养人数时计算足够收入最低值。投资者当前的收入用谓词Earnings表示。因为足够的收入必须既稳定又超过最低值，Earnings有两个参数：第一个参数是收入数，第二个为Steady或Unsteady。对于理财顾问所需要的其他规则为"xEarnings(x,Steady)∧$y(Dependents(y)∧Greater(x,minincome(y)))→Income(Adequate)"xEarnings(x,Steady)∧$y(Dependents(y)∧Greater(x,minincome(y)))→Income(Inadequate)"xEarnings(x,Unsteady)→Income(Inadequate)在理财顾问咨询时，目标是发现一种投资方式，这可以用谓词表达式$xInvestment(x)来表示，其中目标变量x是我们要发现的投资方式。从目标出发，有三条规则可以推出投资方式。在使用归结法推理时，即可将目标取反化成子句与三条规则化成的子句分别进行归结，若最后能得到空子句，则推出结论是成立的结论。但是要知道最后是根据哪条规则推出结论，才能确定投资方式x的值，所以要跟踪归结时变量替换的过程。这也就是从归结反演提取答案的过程。要求根据上面的描述，编制一个程序，首先让用户输入年收入数、是否稳定，所供养的人数以及已有的储蓄。然后给出投资方式的建议。实验八学习Agent实验实验目的与要求目的：掌握遗传算法的基本原理，学习根据实际问题确定染色体编码方法及设计适应度函数，从而实现用遗传算法求解优化问题。要求：编写用遗传算法求解背包问题的程序。基本知识遗传算法(GeneticAlgorithm)是一种优化算法。它是人们从生物的有性繁殖、遗传变异和按优胜劣汰法则进化的自然现象中得到启发，而设计出来的，因此称为遗传算法。我们知道，自然选择的原则是优胜劣汰、适者生存，有性繁殖则可以使基因不断地进行混合和重组。遗传算法以生物细胞中的染色体作为生物个体，并设置了三个作用于染色体的操作：复制、交叉（亦称交换或杂交）和变异（亦称突变），它们被称为遗传操作或遗传算子。此外，还要定义染色体的适应度，即对环境的适应程度。适应度也就是表征一个染色体优劣的测度。在此基础上，遗传算法的步骤就是对一个染色体集合中的染色体，重复做：①三种遗传操作；②计算适应度；③按适应度大小进行取舍，直至达到预定目标。三种遗传操作：1、复制：产生一个与字符串S相同的字符串；2、交叉：取字符串S1和S2，互相交换其中的某些字符，得到两个新的字符串S’1和S’2；3、变异：改变字符串S中的某一个字符，得到一个新的字符串S′。例如，设字符串S1=10101001，S2=10010011，那么，(1)对S1进行复制操作，得新串10101001；(2)对S1和S2进行交叉操作，如交换两个字符串的后4位，则得S’1=10100011，S’2=10011001；(3)对S1进行变异操作，如把第三位的1改为0，则得新串10001001。基本遗传算法：1、随机产生一个个体集合A={S1,S2,:,Sn}，将A作为一个初始种群，并在其上定义一个适应度函数f(x)；2、计算A中每个个体的适应度函数值；3、若满足停止条件，取A中适应度最大的个体作为所求结果，算法结束。4、以一定的概率选择A中若干适应度高的个体S1,S2,…,Sk(k<n)，进行复制操作，并删去A中适应度低的个体，这样得到集合A’(注：被复制个体和复制个体同时存在于A’中)；5、以一定的概率选取A’中的若干个体对，进行交叉操作，得到集合A″；6、以一定的概率选取A″中的若干个体，进行变异操作，得到集合Anew；7、将Anew作为新一代种群，用Anew代替A，转步2。遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，解决困难的问题。遗传算法的适应性强，除需知适应度函数外，几乎不需要其它的先验知识。遗传算法长于全局搜索，它不受搜索空间的限制性假设的约束，不要求连续性，能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。实验内容与进行方式编制用遗传算法求解下面的背包问题的程序：有十件物品，其重量与价值如下