人工智能：第八章 自动规划
第八章自动规划
教学内容：介绍自动规划的基本概念和各种规划系统。
教学重点：机器人规划的作用与任务、积木世界的规划系统、具有学习能力的规划系统、基于专家系统的规划机理。
教学难点：具有学习能力的规划系统。
教学方法：课堂教学为主，注意结合例子来说明抽象概念。
教学要求：本章为选修内容，掌握机器人规划的作用与任务，并一般了解有哪几种规划方法。
8.1机器人规划的作用与任务
教学内容：引入规划的概念，说明问题分解途径，然后讨论自动规划系统的任务。
教学重点：机器人规划的作用。
教学方法：课堂教学。
教学要求：掌握机器人规划的作用与任务。
8.1.1规划的作用与问题分解途径
1、规划的概念及作用
规划的概念：规划是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。
规划的作用：规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。
2、问题分解途径及方法
把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。
第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。
第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。
3、域的预测和规划的修正
举例：以工作日计划来形象地说明规划的作用。
8.1.2机器人规划系统的任务与方法
在规划系统中，必须具有执行下列各项任务的方法：
(1)根据最有效的启发信息，选择应用于下一步的最好规则。
(2)应用所选取的规则来计算由于应用该规则而生成的新状态。
(3)对所求得的解答进行检验。
(4)检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。
(5)检验殆正确的解答，并应用具体的技术使之完全正确。
下面讨论能够执行上述5项任务的方法。
1、选择和应用规则
在选择合适的应用规则时最广泛采用的技术是：首先要查出期望目标状态与现有状态之间的差别集合，然后辨别出那些与减少这些差别有关的规则。
2、检验解答与空端
当规划系统找到一个能够把初始问题状态变换为目标状态的操作符序列时，此系统就成功地求得问题的一个解答。
如果搜索过程是从初始状态正向推理的，那么可以删去任何导致某种状态的路径，从这种状态出发是无法达到目标状态的。
如果搜索过程是从目标状态逆向推理的，那么当确信无法达到初始状态，或者搜索过程进展甚微时，可以终止该路径的搜索。
3、修正殆正确解
一个求解殆可分解问题的办法是：当执行与所提出的解答相对应的操作符序列时，检查求得的状态，并把它与期望目标加以比较。
修正一个殆正确的解答的较好办法是注意有关出错的知识，然后加以直接修正。
8.2积木世界的机器人规划
教学内容：寻求某个机器人的动作序列(可能包括路径等)。
教学重点：机器人问题求解。
教学难点：用F规则求解机器人规划序列。
教学方法：课堂教学。
教学要求：了解问题求解的目标与一般过程、掌握积木世界的机器人规划方法。
8.2.1积木世界的机器人问题
机器人问题既比较简单，又很直观。在机器人问题的典型表示中，机器人能够执行一套动作。
在这个例子中机器人能够执行的动作举例如下：
unstack(a,b)：把堆放在积木b上的积木a拾起。在进行这个动作之前，要求机器人的手为空手，而且积木a的顶上是空的。
stack(a,b)：把积木a堆放在积木b上。动作之前要求机械手必须已抓住积木a，而且积木b顶上必须是空的。
pickup(a)：从桌面上拾起积木a，并抓住它不放。在动作之前要求机械手为空手，而且积木a顶上没有任何东西。
putdown(a)：把积木a放置到桌面上。要求动作之前机械手已抓住积木a。
采用状态描述作为数据库的产生式系统是一种最简单的问题求解系统。机器人问题的状态描述和目标描述均可用谓词逻辑公式构成。为了指定机器人所执行的操作和执行操作的结果，需要应用下列谓词：
ON(a,b)：积木a在积木b之上。
ONTABLE(a)：积木a在桌面上。
CLEAR(a)：积木a顶上没有任何东西。
HOLDING(a)：机械手正抓住积木a。
HANDEMPTY：机械手为空手。
举例：积木世界由一些有标记的立方形积木，互相堆迭在一起构成；机器人有个可移动的机械手，它可以抓起积木块并移动积木从一处至另一处。
提问：请同学就图8.1积木世界的机器人问题应用谓词公式的合取来表示为：ON(B，C)∧ON(A，B)。
8.2.2用F规则求解规划序列
采用F规则表示机器人的动作，这是一个叫做STRIPS规划系统的规则，它由3部分组成。
第一部分是先决条件。为了使F规则能够应用到状态描述中去。
第二部分是一个叫做删除表的谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。
第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。
8.3STRIPS规划系统
教学内容：STRIPS规划系统的机理，规划的目标与实现方法。
教学重点：STRIPS系统的组成
教学难点：对STRIPS规划过程的描述
教学方法：课堂教学
教学要求：掌握STRIPS机器人规划系统的组成，了解规划过程的描述
8.3.1STRIPS系统的组成
整个STRIPS系统的组成如下：
(1)世界模型。为一阶谓词演算公式。
(2)操作符(F规则)。包括先决条件、删除表和添加表。
(3)操作方法。应用状态空间表示和中间-结局分析。
例如：状态：(M，G)，包括初始状态、中间状态和目标状态。
初始状态：(M0，(G0))
目标状态：得到一个世界模型，其中不遗留任何未满足的目标。
8.3.2STRIPS系统规划过程
每个STRIPS问题的解答为某个实现目标的操作符序列，即达到目标的规划。下面举例说明STRIPS统规划的求解过程。
例1 考虑STRIPS系统一个比较简单的情况，即要求机器人到邻室去取回一个箱子。机器人的初始状态和目标状态的世界模型示于图8.4。设有两个操作符，即gothru和pushthru(“走过”和“推过”)，分别描述于下：
OP1：gothru(d,r1,r2)；
机器人通过房间r1和房间r2之间的d，即机器人从房间r1走过门d而进入房间r2。先决条件：INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；机器人在房间r1内，而且门d连接r1和r2两个房间。
删除表：INROOM(ROBOT，S)；对于任何S值。
添加表：INROOM(ROBOT，r2)。
OP2：pushthru(b,d,r1,r2)
机器人把物体b从房间r1经过门d推到房间r2。
先决条件：INROOM(b,r1)∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,r2)删除表：INROOM(ROBOT，S)，INROOM(b，S);对于任何S。
添加表：INROOM(ROBOT，r2),INROOM(b,r2)。
8.4具有学习能力的规划系统
教学内容：介绍一个叫做PULP-Ⅰ(PurdueUniversityLearningProgram)的具有学习能力的机器人规划系统的结构和操作方式，了解规划系统的模型和规划方法。
教学重点：系统的结构与操作方式。
教学难点：规划系统的学习方法。
教学方法：课堂教学。
教学要求：了解具有学习能力的机器人规划系统的规划方法及其与一般规划系统的异同
8.4.1PULP-Ⅰ系统的结构与操作方式
1、PULP-Ⅰ系统的结构
字典、模型和过程是系统的内存部分，它们集中了所有信息。“字典”是英语词汇的集合，它的每个词汇都保持在LISP的特性表上。“模型”部分包括模型世界内物体现有状态的事实。
模型的信息不是固定不变的，它可能随着环境而改变。此外，无论什么时候应用某个操作符，此模型就被适时修正。“过程”集中了予先准备好的过程知识。这种过程知识是一个表式结构，包含一个指令序列。每个指令可能是一个任务语句，这些语句与该任务的过程、局部定义的物体或某个操作符有关。
2、PULP-Ⅰ系统的操作方式
PULP-Ⅰ系统具有两种操作方式，即学习方式和规划方式。
在学习方式下，输入至系统的知识是由操作人员或者所谓“教师”提供的。系统首先把给出的过程知识分解为一个子过程的集合，本原过程知识被分解为几个知识块，每块为一知识包。然后，由任务分析程序进行试验，这个程序对知识包进行分析，并通过一个语义匹配程序求得其提取表示。
当某个命令句子送入系统时，PULP-Ⅰ就进入规划方式。此规划系统的主要作用是形成一个能够把现有世界变换为满足给定命令的世界状态的规划。所生成的规划由一些本原操作符的有序排列组成。当求得一个成功的规划之后，对世界模型进行修正，而且系统输出规划时间和规划细节，以满足输入命令。
8.4.2PULP-Ⅰ的世界模型和规划结果
提问：请同学比较具有学习能力的机器人规划系统与一般规划系统的异同，并总结前者的特点。
8.5分层规划
教学内容：通过ABSTRIPS系统了解针对困难问题的分层规划方法。
教学方法：课堂教学。
教学重点：本规划机理及实例。
教学难点：规划实例分析。
教学要求：本节作为选讲内容，只要求一般了解相关内容。
8.5.1长度优先搜索
探索规划时首先只考虑一层的细节，然后再注意规划中比这一层低一层的细节，所以把它叫做长度优先搜索。
8.5.2NOAH规划系统
1、应用最小约束策略
一个寻找非线性规划而不必考虑操作符序列的所有排列的方法是把最少约束策略应用来选择操作符执行次序的问题。
问题求解系统NOAH采用一种网络结构来记录它所选取的操作符之间所需要的排序。它也分层进行操作运算，即首先建立起规划的抽象轮廓，然后在后续的各步中，填入越来越多的细节。
2、检验准则
准则法已被应用于各种规划生成系统。对于早期的系统，如HACKER系统，准则只用于舍弃不满足的规划。在NOAH系统中，准则被用来提出推定的方法以便修正所产生的规划。
第一个涉及的准则是归结矛盾准则。
第二个准则叫做消除多余先决条件准则，包括除去对子目标的多余说明。
可以把分层规划和最少约定策略十分直接地结合起来，以求得非线性规划而不产生一个庞大的搜索树。
8.6基于专家系统的机器人规划
内容与作用：本节将结合作者对机器人规划专家系统的研究，介绍基于专家系统的机器人规划。
教学重点：基于专家系统的系统结构和规划机理。
教学难点：基于专家系统的规划机理。
教学方法：课堂教学。
教学要求：了解基于专家系统的机器人规划系统的结构和实现方法。
8.6.1系统结构和规划机理
1、系统结构及规划机理
(1) 知识库：用于存储某些特定领域的专家知识和经验，包括机器人工作环境的世界模型、状态、物体描述等事实和可行操作或规则等。
(2)控制策略：包含综合机理，确定系统应当应用什么规则以及采取什么方式去寻找该规则。
(3)推理机：用于记忆所采用的规则和控制策略及推理策略。
(4)知识获取：首先获取某特定域的专家知识。然后用程序设计语言把这些知识变换为计算机程序。最后把它们存入知识库待用。
(5) 解释与说明：通过用户接口，在专家系统与用户之间进行对话，从而使用户能够输入数据、提出问题、知道推理结果以及了解推理过程等。
2、任务级机器人规划三要素
(1)建立模型。
(2)任务说明。
(3)程序综合。
8.6.2ROPES机器人规划系统
作业：根据简化框图8.18，举例说明应用专家系统的机器人规划系统。
8.7小结
本章在说明了机器人规划的作用和任务后，主要讨论了几种机器人规划的方法：
(1)规划演绎法。用F规则求解规划序列。
(2)逻辑演算和通用搜索法。STRIPS和ABSTRIPS系统即属此法。
(3)具有学习能力的规划系统。如PULP-Ⅰ系统，它采用类比技术和语义网络表示。
(4)分层规划方法。如NOAH规划系统，它特别适用于非线性规划。
(5)基于专家系统的规划。如ROPES规划系统，它具有更快的规划速度、更强的规划能力和更大的适应性
from:http://netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/jiaoan/chapter8.htm
人工智能：第二章 知识表示方法
第二章知识表示方法
教学内容：本章讨论知识表示的各种方法，是人工智能课程三大内容（知识表示、知识推理、知识应用）之一，也是学习人工智能其他内容的基础。
教学重点：状态空间法、问题归约法、谓词逻辑法、语义网络法。
教学难点：状态描述与状态空间图示、问题归约机制、置换与合一。
教学方法：课堂教学为主，同时结合《离散数学》等已学的内容实时提问、收集学生学习情况，充分利用网络课程中的多媒体素材来表示抽象概念。
教学要求：重点掌握用状态空间法、问题归约法、谓词演算法、语义网络法来描述问题；解决问题；掌握几种主要方法之间的差别；并对其它几种表示方法有一般了解。
2.1状态空间法
教学内容：本节是通过状态空间法来求解问题，它是以状态和算符(operator)为基础来表示和求解问题的。
教学重点：问题的状态描述，操作符。
教学难点：选择一个好的状态描述与状态空间表示方案。
教学方法：以课堂教学为主；充分利用网络课程中的多媒体素材来阐述抽象概念。
教学要求：重点掌握对某个问题的状态空间描述，学会组织状态空间图，用搜索图来求解问题。
2.1.1问题状态描述
1、状态（State）的基本概念
状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：
Q=［q0,q1,…,qn］T(2.1)
式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如
Qk=［q０k,q1k,…，qnk］T(2.2)
算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。
问题的状态空间(statespace)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。
提问：1.列举已经学习过的“状态”概念，并比较之。2.列举算符。
举例：列举几个日常生活中状态与算符的例子，如：棋局。
讨论：每走一步后，棋局都变化了，以此来理解问题的状态空间。
2、状态空间的表示法
对一个问题的状态描述，必须确定3件事：
(1)该状态描述方式，特别是初始状态描述；
(2)操作符集合及其对状态描述的作用；
(3)目标状态描述的特性。
举例：讲解初始状态、算符、中间状态与目标状态之间的关系；讲解三数码难题的状态变化过程。
2.1.2状态图示法
图的基本概念
图由节点(不一定是有限的节点)的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做有向图(directedgraph)。
某个节点序列(ni1,ni2,…,nik)当j=2，3，…，k时，如果对于每一个ni，j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。
代价(cost)是给各弧线指定数值以表示加在相应算符上的代价。
图的显式说明是指各节点及其具有代价的弧线由一张表明确给出。
图的隐式说明是指各节点及其具有代价的弧线不能由一张表明确给出。
提问：举已经学习过的“有向图”、“路径”及“代价”等的概念。
举例：针对三数码难题的状态变化过程讲解图的几个基本概念。
2.1.3状态空间表示举例
1、产生式系统
一个产生式系统由下列3部分组成：
一个总数据库(globaldatabase)，它含有与具体任务有关的信息。
一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。
一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。
2、状态空间表示举例
猴子与香蕉的问题
状态空间表示用四元组（W，x，y，z）其中：W-猴子的水平位置；x－当猴子在箱子顶上时取x=1；否则取x=0；Y－箱子的水平位置；z-当猴子摘到香蕉时取z=1；否则取z=0。
算符
(1)goto(U)猴子走到水平位置U；
(2)pushbox(V)猴子把箱子推到水平位置V；
(3)climbbox猴子爬上箱顶；
(4)grasp猴子摘到香蕉。
求解过程令初始状态为(a,0,b,0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U，0，b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图，如图所示。从图不难看出，把该初始状态变换为目标状态的操作序列为：
｛goto(b),pushbox(c),climbbox,grasp｝
举例：针对多媒体上的猴子与香蕉问题的状态空间图，讲解问题的状态空间表示和产生式规则的应用。
2.2问题归约法
教学内容：知识表示的归约法，即已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题的方法。
教学重点：问题归约的基本思想，问题描述，问题变换的操作符，与或图表示。
教学难点：如何把初始问题变换为子问题，与或图表示方法。
教学方法：课堂教学为主，充分利用网络课程中的相关多媒体素材来表示抽象概念。
教学要求：通过梵塔难题重点掌握问题归约法的机理和问题归约描述方法。学会用与或图表示归约问题。
2.2.1问题归约描述
1、问题归约法的概念
已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。
该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。
2、问题归约法的组成部分
（1）一个初始问题描述；
（2）一套把问题变换为子问题的操作符；
（3）一套本原问题描述。
3、示例：梵塔难题
问题有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。
归约过程
（1）移动圆盘A和B至柱子2的双圆盘难题；
（2）移动圆盘C至柱子3的单圆盘难题；
（3）移动圆盘A和B至柱子3的双圆盘难题。
由上可以看出简化了难题每一个都比原始难题容易，所以问题都会变成易解的本原问题。
讲述：梵塔问题的来源。
提问：一圆盘问题要走几步？两圆盘问题要走几步？三个、四个．．．等？
4、归约描述
问题归约方法是应用算符来把问题描述变换为子问题描述。
可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问题［（111）→(122)］，［(122)→(322)］以及［(322)→(333)］规定了最后解答路径将要通过的脚踏石状态(122)和(322)。
问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。
2.2.2与或图表示
1、与或图的概念
用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。
例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示。
举例：含有与图与或图的混合图。
提问：对于一个与或图如何引入附加节点，使得后继问题的每个集合能够聚集在它们各自的父辈节点之下。
2、与或图的有关术语
父节点是一个初始问题或是可分解为子问题的问题节点；
子节点是一个初始问题或是子问题分解的子问题节点；
或节点只要解决某个问题就可解决其父辈问题的节点集合；
与节点只有解决所有子问题，才能解决其父辈问题的节点集合；
弧线是父辈节点指向子节点的圆弧连线；
终叶节点是对应于原问题的本原节点。
举例：对于一个与或图。
提问：指出图中的父节点、子节点、或节点、与节点、弧线和终叶节点。
3、与或图的有关定义
可解节点与或图中一个可解节点的一般定义可以归纳如下：
(1)终叶节点是可解节点(因为它们与本原问题相关连)。
(2)如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。
(3)如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。
举例：对于一个与或图。
提问：指出图中的终叶节点、可解节点、不可解节点。
不可解节点不可解节点的一般定义归纳于下：
(1)没有后裔的非终叶节点为不可解节点。
(2)如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。
(3)如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。
举例：对于三圆盘梵塔难题根据构图规则画出其归约图。
提问：指出图中的终叶节点、可解节点、不可解节点。
课后作业：教材第二章习题2－2与2－5
4、与或图构图规则
(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。
(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。
(3) 对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。
(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。
(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。
2.3谓词逻辑法
教学内容：本节主要讲述问题的谓词逻辑表示的基本方法。
教学重点：谓词逻辑、谓词公式、谓词演算、置换与合一。
教学难点：如何选择谓词，问题的谓词逻辑表示及运算。
教学方法：课堂教学为主，充分利用网络课程中的示例程序。
教学要求：重点掌握谓词逻辑表示的语言与方法，掌握谓词公式的性质及谓词演算，学会谓词公式的置换与合一，运用谓词推理来解决问题。
2.3.1谓词演算
1、语法和语义
谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。
原子公式是由若干谓词符号和项组成，只有当其对应的语句在定义域内为真时，才具有值T(真)；而当其对应的语句在定义域内为假时，该原子公式才具有值F(假)。
2、连词和量词
连词有∧(与)、∨(或)，全称量词(x)，存在量词(x)。
原子公式是谓词演算的基本积木块，运用连词能够组合多个原子公式以构成比较复杂的合适公式。
3、几个有关定义
用连词∧把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合适公式。
用连词∨把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。由一些合适公式所构成的任一析取也是一个合适公式。
用连词→连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项，右式叫做后项。如果前项和后项都是合适公式，那么蕴涵也是合适公式。
前面具有符号～的公式叫做否定。一个合适公式的否定也是合适公式。
量化一个合适公式中的某个变量所得到的表达式也是合适公式。如果一个合适公式中某个变量是经过量化的，就把这个变量叫做约束变量，否则就叫它为自由变量。在合适公式中，感兴趣的主要是所有变量都是受约束的。这样的合适公式叫做句子。
2.3.2谓词公式
1、谓词合适公式的定义
在谓词演算中合适公式的递归定义如下：
(1)原子谓词公式是合适公式。
(2)若A为合适公式，则～A也是一个合适公式。
(3)若A和B都是合适公式，则(A∧B)，(A∨B)，(A=>B)和(A←→B)也都是合适公式。
(4)若A是合适公式，x为A中的自由变元，则(x)A和(x)A都是合适公式。
(5)只有按上述规则(1)至(4)求得的那些公式，才是合适公式。
举例：试把下列命题表示为谓词公式：任何整数或者为正或者为负。
提问：指出此例题谓词公式中的量词、连词及蕴涵符号。
2、合适公式的性质
(1)否定之否定
～(～P)等价于P
(2)P∨Q等价于～P→Q
(3)狄·摩根定律
～(P∨Q)等价于～P∧～Q
～(P∧Q)等价于～P∨～Q
(4)分配律
P∧(Q∨R)等价于(P∧Q)∨(P∧R)
P∨(Q∧R)等价于(P∨Q)∧(P∨R)
(5)交换律
P∧Q等价于Q∧P
P∨Q等价于Q∨P
(6)结合律
(P∧Q)∧R等价于P∧(Q∧R)
(P∨Q)∨R等价于P∨(Q∨R)
(7)逆否律
P→Q等价于～Q→～P
此外，还可建立下列等价关系：
(8)～(x)P(x)等价于(x)［～P(x)］
～(x)P(x)等价于(x)［～P(x)］
(9)(x)［P(x)∧Q(x)］等价于
(x)P(x)∧(x)Q(x)
(x)［P(x)∨Q(x)］等价于
(x)P(x)∨(x)Q(x)
(10)(x)P(x)等价于(y)P(y)
(x)P(x)等价于(y)P(y)
证明：否定之否定，～(～P)等价于P。
2.3.3置换与合一
1、置换
假元推理，就是由合适公式W1和W1→W2产生合适公式W2的运算。
全称化推理，是由合适公式(x)W(x)产生合适公式W(A)，其中A为任意常量符号。
一个表达式的置换就是在该表达式中用置换项置换变量。
一般说来，置换是可结合的，但置换是不可交换的。
2、合一
寻找项对变量的置换，以使两表达式一致，叫做合一(unification)。如果一个置换s作用于表达式集｛Ei｝的每个元素，则用｛Ei｝s来表示置换例的集。称表达式集｛Ei｝是可合一的。如果存在一个置换s使得：E1s=E2s=E3s=…那么称此s为｛Ei｝的合一者，因为s的作用是使集合｛Ei｝成为单一形式。
举例：表达式P［x,f(y),B］的一个置换为s1=｛z/x,w/y｝，则：P［x,f(y),B］s1=P［z,f(w),B］
2.4语义网络法
教学内容：本节主要讲述知识的语义网络表示法。
教学重点：语义网络表示的词法、结构、过程、语义。
教学难点：如何选择节点和弧线来构成语义网络。
教学方法：课堂教学。
教学要求：重点掌握语义网络的结构，掌握二元语义网络表示方法，了解语义网络的特点。
2.4.1二元语义网络的表示
１、语义网络的基本概念语义网络是知识的一种结构化图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。
语义网络表示由下列4个相关部分组成：
(1)词法部分决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。
(2)结构部分叙述符号排列的约束条件，指定各弧线连接的节点对。
(3)过程部分说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。
(4)语义部分确定与描述相关的(联想)意义的方法即确定有关节点的排列及其占有物和对应弧线。
语义网络具有下列特点：
(1)能把实体的结构、属性与实体间的因果关系显式地和简明地表达出来，与实体相关的事实、特征和关系可以通过相应的节点弧线推导出来。
(2)由于与概念相关的属性和联系被组织在一个相应的节点中，因而使概念易于受访和学习。
(3)表现问题更加直观，更易于理解，适于知识工程师与领域专家沟通。
(4)语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定，因而得到的推理不能保证像谓词逻辑法那样有效。
(5)节点间的联系可能是线状、树状或网状的，甚至是递归状的结构，使相应的知识存储和检索可能需要比较复杂的过程。
2、二元语义网络的表示用两个节点和一条弧线可以表示一个简单的事实，对于表示占有关系的语义网络，是通过允许节点既可以表示一个物体或一组物体，也可以表示情况和动作。每一情况节点可以有一组向外的弧(事例弧)，称为事例框，用以说明与该事例有关的各种变量。
在选择节点时，首先要弄清节点是用于表示基本的物体或概念的，或是用于多种目的的。否则，如果语义网络只被用来表示一个特定的物体或概念，那么当有更多的实例时就需要更多的语义网络。
选择语义基元就是试图用一组基元来表示知识。这些基元描述基本知识，并以图解表示的形式相互联系。
举例：用二元语义网络表示：小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。
2.4.2多元语义网络的表示语义网络是一种网络结构。节点之间以链相连。从本质上讲，接点之间的连接是二元关系。语义网络从本质上来说，只能表示二元关系，如果所要表示的事实是多元关系，则把这个多元关系转化成一组二元关系的组合，或二元关系的合取。具体来说，多元关系R(X1，X2，…，Xn)总可以转换成R1(X11，X12)∧R2(X21，X22)∧…∧Rn(Xn1,Xn2)。要在语义网络中进行这种转换需要引入附加节点。
举例：用”Limingisaman”的语义网络和谓词逻辑表示说明谓词逻辑与语义网络的等效性。
2.4.3连词和量化的表示
可以用语义网络表示谓词逻辑法中的各种连词及量化。
1.合取多元关系可以被转换成一组二元关系的合取，从而可以用语义网络的形式表示出来。
2.析取在语义网络中，为与合取关系相区别，在析取关系的连接上加注析取界限，并标记DIS。
3.否定采用～ISA和～PARTOF关系或标注NEG界限来表示否定。
4.蕴涵在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。
5.量化存在量化在语义网络中可直接用ISA链来表示。而全称量化就要用分割方法来表示。
2.5其他方法教学内容：简介知识表示的其他三种表示方法，即框架表示法、剧本表示法和过程表示法，阐述了三种表示法的原理和应用范围。
教学重点：各方法的基本原理及基本结构。
教学难点：各方法的推理过程。
教学方法：课堂教学为主。适当提问，加深学生对概念的理解。
教学要求：初步了解三种方法的基本原理。
2.5.1框架
1、框架的构成
框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可以拥有若干个值。一个框架的一般结构如下：〈框架名〉
〈槽1〉〈侧面11〉〈值111〉…
〈侧面12〉〈值121〉…
…
〈槽2〉〈侧面21〉〈值211〉…
…
…
〈槽n〉〈侧面n1〉〈值n11〉…
…
〈侧面nm〉〈值nm1〉…
较简单的情景是用框架来表示诸如人和房子等事物。例如，一个人可以用其职业、身高和体重等项描述，因而可以用这些项目组成框架的槽。当描述一个具体的人时，再用这些项目的具体值填入到相应的槽中。表2.2给出的是描述John的框架。
表2.2简单框架示例
JOHN
Isa
:
PERSON
Profession
:
PROGRAMMER
Height
:
1.8m
Weight
:
79kg
框架是一种通用的知识表达形式，对于如何运用框架系统还没有一种统一的形式，常常由各种问题的不同需要来决定。
2、框架的推理
如前所述，框架是一种复杂结构的语义网络。因此语义网络推理中的匹配和特性继承在框架系统中也可以实行。除此以外，由于框架用于描述具有固定格式的事物、动作和事件，因此可以在新的情况下，推论出未被观察到的事实。框架用以下几种途径来帮助实现这一点：
(1)框架包含它所描述的情况或物体的多方面的信息。(2)框架包含物体必须具有的属性。在填充框架的各个槽时，要用到这些属性。(3)框架描述它们所代表的概念的典型事例。用一个框架来具体体现一个特定情况的过程，经常不是很顺利的。但当这个过程碰到障碍时，经常不必放弃原来的努力去从头开始，而是有很多办法可想的：
(1)选择和当前情况相对应的当前的框架片断，并把这个框架片断和候补框架相匹配。选择最佳匹配。
(2)尽管当前的框架和要描述的情况之间有不相匹配的地方，但是仍然可以继续应用这个框架。
(3)查询框架之间专门保存的链，以提出应朝哪个方向进行试探的建议。
(4)沿着框架系统排列的层次结构向上移动(即从狗框架→哺乳动物框架→动物框架)，直到找到一个足够通用，并不与已有事实矛盾的框架。
2.5.2剧本
剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列，就像剧本中的事件序列一样，故称为“剧本”或脚本。
一个剧本一般由以下各部分组成：
(1)开场条件给出在剧本中描述的事件发生的前提条件。
(2)角色用来表示在剧本所描述的事件中可能出现的有关人物的一些槽。
(3)道具这是用来表示在剧本所描述的事件中可能出现的有关物体的一些槽。
(4)场景描述事件发生的真实顺序，可以由多个场景组成，每个场景又可以是其它的剧本。
(5)结果给出在剧本所描述的事件发生以后通常所产生的结果。
例子：以餐厅剧本为例说明剧本各个部分的组成。
根据剧本的重要性，可以有二种准备剧本的方法。
(1)对于不属于事件核心部分的剧本，只需设置指向该剧本的指针即可，以便当它成为核心时启用。
(2)对于符合事件核心部分的剧本，则应使用在当前事件中涉及到的具体对象和人物去填写剧本的槽。剧本的前提、道具、角色和事件等常能起到启用剧本的指示器的作用。
一旦剧本被启用，则可以应用它来进行推理。其中最重要的是运用剧本可以预测没有明显提及的事件的发生。
剧本结构，比起框架这样的一些通用结构来，要呆板得多，知识表达的范围也很窄，因此不适用于表达各种知识，但对于表达预先构思好的特定知识，如理解故事情节等，是非常有效的。
2.5.3过程
语义网络、框架和剧本等知识表示方法，均是对知识和事实的一种静止的表达方法，是知识的一种显式表达形式。而对于如何使用这些知识，则通过控制策略来决定。
和知识的陈述式表示相对应的是知识的过程式表示。所谓过程式表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程。它所给出的是事物的一些客观规律，表达的是如何求解问题。知识的描述形式就是程序，所有信息均隐含在程序之中。从程序求解问题的效率上来说，过程式表达要比陈述式表达高得多。但因其知识均隐含在程序中，因而难于添加新知识和扩充功能，适用范围较窄。
2.6小结
知识表示方法很多，本章介绍了其中的7种，有图示法和公式法，结构化方法，陈述式表示和过程式表示等。
状态空间法是一种基于解答空间的问题表示和求解方法，它是以状态和操作符为基础的。在利用状态空间图表示时，从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。由于状态空间法需要扩展过多的节点，容易出现“组合爆炸”，因而只适用于表示比较简单的问题。
问题归约法从目标(要解决的问题)出发，逆向推理，通过一系列变换把初始问题变换为子问题集合和子子问题集合，直至最后归约为一个平凡的本原问题集合。这些本原问题的解可以直接得到从而解决了初始问题，用与或图来有效地说明问题归约法的求解途径。问题归约法能够比状态空间法更有效地表示问题。状态空间法是问题归约法的一种特例。在问题归约法的与或图中，包含有与节点和或节点，而在状态空间法中只含有或节点。
谓词逻辑法采用谓词合适公式和一阶谓词演算把要解决的问题变为一个有待证明的问题，然后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导出的，从而证明这个新语句也是正确的。谓词逻辑是一种形式语言，能够把数学中的逻辑论证符号化。谓词逻辑法常与其它表示方法混合使用，灵活方便，可以表示比较复杂的问题。
语义网络是一种结构化表示方法，它由节点和弧线或链线组成。节点用于表示物体、概念和状态，弧线用于表示节点间的关系。语义网络的解答是一个经过推理和匹配而得到的具有明确结果的新的语义网络。语义网络可用于表示多元关系，扩展后可以表示更复杂的问题。
框架是一种结构化表示方法。框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。大多数实用系统必须同时使用许多框架，并可把它们联成一个框架系统。框架表示已获广泛应用，然而并非所有问题都可以用框架表示。
剧本是框架的一种特殊形式，它使用一组槽来描述事件的发生序列。剧本表示特别适用于描述顺序性动作或事件，但使用不如框架灵活，因此应用范围也不如框架那么广泛。
过程是一种知识的过程式表示，它将某一有关问题领域知识同这些使用方法一起，隐式地表示为一个问题求解过程。过程表示用程序来描述问题，具有很高的问题求解效率。由于知识隐含在程序中难以操作，所以适用范围较窄。
在表示和求解比较复杂的问题时，采用单一的知识表示方法是远远不够的。往往必须采用多种方法混合表示。例如，综合采用框架、语义网络、谓词逻辑的过程表示方法(两种以上)，可使所研究的问题获得更有效的解决。
此外，在选择知识表示方法时，还要考虑所使用的程序设计语言所提供的功能和特点，以便能够更好地描述这些表示方法。
from：http://netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/jiaoan/chapter2.htm
上海教师资格证面试：《人工智能》教案
原标题：上海教师资格证面试：《人工智能》教案本文由上海中公教师考试网整合，更多上海教师招聘信息关注微信号：shjsksw,或者加上海教师招聘学习群①126052361
一、教学目标
【知识与技能】知道什么是人工智能，并能够举出具体的例子。
【过程与方法】在人工智能的应用体验中，感受其应用前景的广阔。
【情感态度与价值观】通过对人工智能技术的了解，建立对该技术的兴趣，并辨证的认识到人工智能技术对生活的影响。
二、教学重难点
【重点】什么是人工智能及其应用
【难点】辨证的看待人工智能技术
三、教学方法
【教法】体验感悟法、案例分析法、视频陶冶法
【学法】参与法、自主学习法、讨论法
四、教学过程
(一)导入
首先询问学生是否玩过五子棋、蜘蛛纸牌等单机游戏，然后引出人工智能这个概念。通过从学生的生活实际入手，更能激发学生的兴趣，也容易激发学生的学习欲望。然后进一步展示轰动全球的“人机大战”事件，引出本节课的课题——人工智能。
(二)新授
1.请学生自行归纳概括人工智能的定义。
2.在人机对弈的事件的基础上解释其运行的根本原理。
3.展示人工智能技术在生活当中的应用，感受人工智能技术，并请学生举出人工智能表现的案例。
4.呈现赵薇老公豪宅被卖的案例，说明人工智能存在的局限性。并请学生思考并讨论，人工智能的不断发展和大量使用，对人类的生活有什么样的影响。学生受前面案例的影响会举出许多的积极影响，对消极影响关注可能不够。因此可以进一步呈现一些反面案例，激发学生的思考能力。如，电影——变形金刚。
(三)巩固提高
给出现代人在生活中对手机过度的依赖的漫画，请同学思考应该如何应对。假如未来的人工智能技术非常强大，人们的生活又会怎么样呢?
展开全文(四)小结作业
1.带领学生用集体总结的方式，回顾人工智能的定义及应用。
2.查找关于人工智能的资料，再次思考人工智能对于人类的意义。
五、板书设计
六、教学反思
《人工智能》并不是我们常见的操作课，同时也不是理论性很强的课程。而且对于高中生而言，人工智能在生活中并不少见，影视作品中有常常出现。所以，这节课的课程目标绝不是单纯的认识人工智能技术。因此，结合课程标准中的课程理念，可知这节课的内容更偏向于给学生树立正确的信息技术使用观念。故而，课程内容设定为什么是人工智能及其应用及辨证的看待人工智能技术。在教学方法上，改变传统的教师讲授为主的方式，从引导学生从生活实例入手来初步认识这一技术，这样做的目的是让学生觉得“人工智能”就在身边，这样可以引导学生注意观察生活，并树立科学技术是为大众服务的理念。然后引出“更深的蓝”，进一步让学生感受人工智能的进步之处，并且通过这个案例向学生讲清楚人工智能的运行原理是在机器根据实际情况在多种备用方案中做出恰当的选择。再去了解人工智能技术的应用，可以让学生清楚的感知这一技术在生活当中的广泛应用。但是，在这一阶段结束之后，学生对人工智能会过度崇拜。而高中阶段也是学生形成辨证思维的时期，所以用赵薇老公豪宅被盗的案例，引发学生对这一技术的思考。整个课程当中，老师充当的是一个引导者的角色，很多事实是由学生自己讲出来的，老师只是加以点拨。并且呈现的内容结合了生活实际、科学运用、影视作品等多方面的内容，有助于吸引学生的注意力，提升学生的学习兴趣。
信息技术学科的知识来源于生活，运用于生活，它在学生的未来生活中几乎是难以舍弃的一部分。所以，教师要注重价值观的正确引导，并且引导的方式不是灌输，而是学生的自我发现、自我思考和评判。
更多上海教师资格证考试备考资料关注：返回搜狐，查看更多
责任编辑：