一、选择题（10小题，共10分） 6、产生式系统的推理不包括（） A）正向推理B）逆向推理C）双向推理D）简单推理 8、在公式中?y?xp(x,y))，存在量词是在全称量词的辖域内，我们允许所存在的x可能 依赖于y值。令这种依赖关系明显地由函数所定义，它把每个y值映射到存在的那个x。 这种函数叫做（） A) 依赖函数B) Skolem函数 C) 决定函数D) 多元函数 9、子句~P∨Q和P经过消解以后，得到（） A) P B) ~P C) Q D) P∨Q 10、如果问题存在最优解，则下面几种搜索算法中，（）必然可以得到该最优解。 A)宽度（广度）优先搜索B) 深度优先搜索 C) 有界深度优先搜索D) 启发式搜索 二、填空题（10个空，共10分） 1、化成子句形式为：~。 2、假言推理（A→B）∧A?B，假言三段论（A→B）∧（B→C）? A -> C. 3、在启发式搜索当中，通常用启发函数来表示启发性信息。 5、状态空间法三要点分别是：状态和算符，状态空间方法。 6. 鲁宾逊提出了⑦归结原理使机器定理证明成为可能。 7. 宽度优先搜索与深度优先搜索方法的一个致命的缺点是当问题比较复杂是可能会发 生组合爆炸。 8、产生式系统是由___综合数据库知识库___和_推理机________三部分组成的. 9、谓词公式G是不可满足的，当且仅当对所有的解释G都为假。 10、谓词公式与其子句集的关系是包含。 11、利用归结原理证明定理时，若得到的归结式为空集，则结论成立。 12、若C1=┐P∨Q，C2=P∨┐Q，则C1和C2的归结式R（C1，C2）= ┐P∨P或┐Q ∨Q。 13、在框架和语义网络两种知识表示方法中，框架适合于表示结构性强的知识，而 语义网络则适合表示一些复杂的关系和联系的知识。 三、简答题（4小题，共40分） 1．什么是A*算法的可纳性？(4分) 答：在搜索图存在从初始状态节点到目标状态节点解答路径的情况下，若一个搜索法总能找到最短（代价最小）的解答路径，则称算法具有可采纳性。 2．在一般图搜索算法中，当对某一个节点n进行扩展时，n的后继节点可分为三类，请举例说明对这三类节点的不同的处理方法。(8分)
人工智能习题
1、将下列谓词公式化成子句集 ?x?y(?z(P(z) ∧Q(x,z))→R(x,y,f(a))) ?x?y(??z(P(z) ∧Q(x,z)) ∨R(x,y,f(a))) ?x?y(?z(P(z) ∨Q(x,z)) ∨R(x,y,f(a))) ?y(?z(P(z) ∨Q(b,z)) ∨R(b,y,f(a))) ?y((P(g(y)) ∨Q(b,g(y))) ∨R(b,y,f(a))) 结果为：{P(g(y)) ∨Q(b,g(y)) ∨R(b,y,f(a))} 2、可信度推理的推理方法 带有阈值限度的不确定性推理； 加权的不确定性推理； 前提条件中带有可信度因子的不确定性推理。 3、现在人工智能有哪些学派？它们的任知观是什么？ 答：人工智能的学派及其认知观如下：符号主义认为人工智能起源于数理逻辑；连接主义认为人工智能起源于仿生学，特别是对人脑模型的研究；行为主义认为人工智能源于控制论。 4.什么叫人工智能？它的研究主要包含哪些内容？ 人工智能:是一门研究如何用人工的方法去模拟和实现人类智能的科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器。 该领域的的研究包括机器人、语言识别、图像识别、自然语言处理、自动程序设计、定理的证明、组合调度和专家系统等。 5.命题逻辑的归结法与谓词逻辑的归结法的不同之处是什么？请举例说明。 答：谓词逻辑比命题逻辑更复杂，由于谓词逻辑中的变量受到量词的约束，在归结之前需要对变量进行重命名即变量标准化，而在命题逻辑中的归结则不需要。 6、什么是推理？它有哪些分类方法？ 答：
谓词演算的 推理理论
在谓词逻辑中，除了命题逻辑中的推理规则继续有效外，还有以下四条规则。设前提Г= {A 1,A 2,…,A k }. 1. 全称指定规则（全称量词消去规则）US ： 例1 取个体域为实数域，F(x, y): x>y, P(x)=(?y) F(x,y), 则(?x)P(x) ?P(z)=(?y) F(z,y). 而不能(?x) P(x) ?P(y)=(?y) F(y,y). 其中x,y 是个体变项符号，c 为任意的个体常量. 或 (?x ) P (x ) ∴ P (y ) (?x) P (x ) ∴ P (c )
2 . 全称推广规则（全称量词引入规则） UG： P(x) ∴ (?x)P(x) 其中x是个体变项符号，且不在前提的任何公式中 自由出现. 3. 存在指定规则（存在量词消去规则） ES： (?x)P(x) ∴ P(c) 1)c是使P(x)为真的特定的个体常量，不是任意的. 2)c不在前提中或者先前推导公式中出现或自由出现， 换句话说，此c是在该推导之前从未使用过的.
4. 存在推广规则（存在量词引入规则) EG： P(c) ∴ ( x)P(x) 其中x是个体变项符号, c是个体常项符号.
谓词逻辑的推理理论由下列要素构成. 1. 等价公式 2. 蕴含式 3. 推理规则： (1) 前提引入规则 (2) 结论引入规则 (3) CP推理规则 (4)归谬论 (5) US规则 (6) UG规则 (7) ES规则 (8) EG规则
1)在推导的过程中，可以引用命题演算中的规则P、规则T、 规则CP . 2)为了在推导过程中消去量词，可以引用规则US和规则ES来 消去量词. 3)当所要求的结论可能被定量时，此时可引用规则UG和规则 EG将其量词加入. 4)证明时可采用如命题演算中的直接证明方法和间接证明方法. 5)在推导过程中，对消去量词的公式或公式中没含量词的子公 式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式. 6)在推导过程中，对含有量词的公式可以引用谓词中的基本等 价公式和基本蕴涵公式.
谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，， =，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧? ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧?? （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321 {，，=D 。求下列各式的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ，?? （4）)(y x yP x ，?? （5）)(y x yP x ， ?? （6）)(y x xP y ， ?? 解：
第二章 2.8设有如下语句，请用相应的谓词公式分别把他们表示出来： (1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。 解：定义谓词 P(x)：x是人 L(x,y)：x喜欢y 其中，y的个体域是{梅花，菊花}。 将知识用谓词表示为： (?x )(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花)) (2)有人每天下午都去打篮球。 解：定义谓词 P(x)：x是人 B(x)：x打篮球 A(y)：y是下午 将知识用谓词表示为： (?x )(?y) (A(y)→B(x)∧P(x)) (3)新型计算机速度又快，存储容量又大。 解：定义谓词 NC(x)：x是新型计算机 F(x)：x速度快 B(x)：x容量大 将知识用谓词表示为： (?x) (NC(x)→F(x)∧B(x)) (4)不是每个计算机系的学生都喜欢在计算机上编程序。 解：定义谓词 S(x)：x是计算机系学生 L(x, pragramming)：x喜欢编程序 U(x,computer)：x使用计算机 将知识用谓词表示为： ?(?x) (S(x)→L(x, pragramming)∧U(x,computer)) (5)凡是喜欢编程序的人都喜欢计算机。 解：定义谓词 P(x)：x是人 L(x, y)：x喜欢y 将知识用谓词表示为： (?x) (P(x)∧L(x,pragramming)→L(x, computer)) 2.10用谓词表示法求解农夫、狼、山羊、白菜问题。农夫、狼、山羊、白菜全部放在一条河的左岸，现在要把他们全部送到河的右岸去，农夫有一条船，过河时，除农夫外船上至多能载狼、山羊、白菜中的一种。狼要吃山羊，山羊要吃白菜，除非农夫在那里。似规划出一个确
2.5 谓词演算的推理理论 1．推理定律 谓词演算中也存在一些基本的等价与蕴含关系，参见表2-2。我们以此作为推理的基础，即推理定律。 表2-2 序号 等价或蕴含关系 含义 E27 E28 ┐?xA(x)??x┐A(x) ┐?xA(x)??x┐A(x) 量词否定等值式 E29 E30?x(A(x)∧B(x))??xA(x)∧?xB(x) ?x(A(x)∨B(x))??xA(x)∨?xB(x) 量词分配等值式（量词分配律） E31 E32 E33 E34 E35 E36 E37 E38 E39 E40 E41 E42 E43?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(A(x)→B(x))??xA(x)→?xB(x) ?x(A(x)→B)??xA(x)→B ?xA(x)→B??x(A(x)→B) A→?xB(x)??x(A→B(x)) A→?xB(x)??x(A→B(x)) 量词作用域的扩张与收缩 I21 I22?xA(x)∨?xB(x)??x(A(x)∨B(x)) ?x(A(x)∧B(x))??xA(x)∧?xB(x) I23 ?xA(x)→?xB(x)??x(A(x)→B(x)) 表2-2中的I、E序号是接着表1-5和1-8排列的，表明它们都是谓词逻辑的推理定律。E31~E34与E35~E38只是A和B的顺序不同。 2．量词的消除与产生规则 谓词推理可以看作是对命题推理的扩充。除了原来的P规则（前提引入）、T规则（命题等价和蕴含）及反证法、CP规则外，为什么还需引入新的推理规则呢？ 命题逻辑中只有一种命题，但谓词逻辑中有2种，即量词量化的命题和谓词填式命题。如果仅由表2-2的推理定律就可推证，并不需要引入新的规则，但这种情况十分罕见，也失去了谓词逻辑本身的意义。为此，要引入如下4个规则完成量词量化命题与谓词填式之间的转换，其中的A(x)表示任意的谓词。 (1) 全称指定（消去）规则US（Ubiquity Specification，或记为?-）
§2.2 谓词公式及其解释 习题2.2 1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。 （1）))()((y x Q x P x ，→? （2）)()(y x yQ y x xP ，，?→? （3）)())()((z y x xR z y Q y x P y x ，，，，?∨∧?? 解 （1）x ?中的x 是指导变元；量词x ?的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。 （2）x ?中的x ，y ?中的y 都是指导变元；x ?的辖域是)(y x P ，，y ?的辖域是)(y x Q ，；)(y x P ，中的x 是x ?的约束变元，y 是自由变元； )(y x Q ，中的x 是自由变元，y 是y ?的约束变元。 （3）x ?中的x ，y ?中的y 以及x ?中的x 都是指导变元；x ?的辖域是))()((z y Q y x P y ，，∧?，y ?的辖域是)()(z y Q y x P ，，∧，x ?的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元， )(z y x R ，，中的x 为约束变元，y ，z 是自由变元。 2. 设个体域}21 {，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。 （1）))()((x Q x P x →? （2）))()((x Q x P x ∧? 解（1）解释1I ：个体域}21 {，=D ，0:)(,0:)(>>x x Q x x P 。 （2）解释2I ：个体域}21 {，=D ，2:)(,0:)(>>x x Q x x P 。 3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。 （1）)))()(()((y x R y Q y x P x ，∧?→? （2）)),()()((y x R y Q x P y x →∧?? 解 （1）成真解释：个体域D ＝{1,2,3},0:)(
实验三化为子句集的九步法实验 一、实验目的 理解和掌握消解原理，熟悉谓词公式化为子句集的九个步骤，理解消解推理规则，能把任意谓词公式转换成子句集。 二、实验原理 消解是可用于一定的子句公式的重要推理规则，任一谓词演算公式可以化成一个子句集。通过九步法消解可以从这两个父辈子句推导出一个新子句。 九步法消解包括消去蕴涵符号、减否定符辖域、对变量标准化、消去存在量词、化为前束型、化为合取范式、消去全程量词、消去合取符、更换变量名，依次变换即可得到子句集。具体为： （1）消去连接词“→”和“?” P→Q?﹁P∨QP?Q?(P∧Q)∨(﹁P∧﹁Q) （2）将否定符号“﹁”移到仅靠谓词的位置 ﹁(﹁P)?P ﹁(P∧Q)?﹁P∨﹁Q ﹁(P∨Q)?﹁P∧﹁Q ﹁(?x)P(x)?(?x)﹁P(x) ﹁(?x)P(x)?(?x)﹁P(x) (?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))?(?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)(?y)(?z)(﹁P(x,y)∨(Q(x,z)∧﹁R(x,z))) （5）消去存在量词 (?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x)))) （6）化为Skolem标准形P∨(Q∧R)?(P∨Q)∧(P∨R) (?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))) （7）消去全称量词 (?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))) （8）消去合取词 ﹁P(x,f(x))∨Q(x,g(x)) ﹁P(x,f(x))∨﹁R(x,g(x)) （9）更换变量名称 ﹁P(x,f(x))∨Q(x,g(x)) ﹁P(y,f(y))∨﹁R(y,g(y)) 三、实验内容 （1）可以采用自己熟悉的C#、C++、JA V A等任一种语言编写出Windows应用程序，演示子句消解推理演示程序。 （2）界面中可以通过实例按钮，由程序指定具体的实例，给出原始谓词公式； （3）设计九个步骤的按钮，每按一步按钮，给出这一步消解的结果； （4）该程序主要帮助初学者学习、掌握九步法谓词公式化为子句集的过程。 四、实验要求 （1）提交实验报告，以word文档形式“学号+姓名”命名； （2）报告中要有程序源代码； （3）有程序运行结果截图； （4）报告提交到：ftp://192.168.129.253/xstjzy/任建平/人工智能 五．实验截图
3.8 判断下列公式是否为可合一，若可合一，则求出其最一般合一。 (1) P(a, b), P(x, y) (2) P(f(x), b), P(y, z) (3) P(f(x), y), P(y, f(b)) (4) P(f(y), y, x), P(x, f(a), f(b)) (5) P(x, y), P(y, x) 解：(1) 可合一，其最一般和一为：σ={a/x, b/y}。 (2) 可合一，其最一般和一为：σ={y/f(x), b/z}。 (3) 可合一，其最一般和一为：σ={ f(b)/y, b/x}。 (4) 不可合一。 (5) 可合一，其最一般和一为：σ={ y/x}。 3.11 把下列谓词公式化成子句集： (1)(?x)(?y)(P(x, y)∧Q(x, y)) (2)(?x)(?y)(P(x, y)→Q(x, y)) (3)(?x)(?y)(P(x, y)∨(Q(x, y)→R(x, y))) (4)(?x) (?y) (?z)(P(x, y)→Q(x, y)∨R(x, z)) 解：(1) 由于(?x)(?y)(P(x, y)∧Q(x, y))已经是Skolem标准型，且P(x, y)∧Q(x, y)已经是合取范式，所以可直接消去全称量词、合取词，得 { P(x, y), Q(x, y)} 再进行变元换名得子句集： S={ P(x, y), Q(u, v)} (2) 对谓词公式(?x)(?y)(P(x, y)→Q(x, y))，先消去连接词“→”得： (?x)(?y)(?P(x, y)∨Q(x, y)) 此公式已为Skolem标准型。 再消去全称量词得子句集： S={?P(x, y)∨Q(x, y)} (3) 对谓词公式(?x)(?y)(P(x, y)∨(Q(x, y)→R(x, y)))，先消去连接词“→”得： (?x)(?y)(P(x, y)∨(?Q(x, y)∨R(x, y))) 此公式已为前束范式。 再消去存在量词，即用Skolem函数f(x)替换y得： (?x)(P(x, f(x))∨?Q(x, f(x))∨R(x, f(x))) 此公式已为Skolem标准型。 最后消去全称量词得子句集： S={P(x, f(x))∨?Q(x, f(x))∨R(x, f(x))} (4) 对谓词(?x) (?y) (?z)(P(x, y)→Q(x, y)∨R(x, z))，先消去连接词“→”得： (?x) (?y) (?z)(?P(x, y)∨Q(x, y)∨R(x, z)) 再消去存在量词，即用Skolem函数f(x)替换y得： (?x) (?y) (?P(x, y)∨Q(x, y)∨R(x, f(x,y))) 此公式已为Skolem标准型。 最后消去全称量词得子句集： S={?P(x, y)∨Q(x, y)∨R(x, f(x,y))}
1 ．设有下列语句，请用相应的谓词公式把它们表示出来： （1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。答：定义谓词： MAN（X）：X是人， LIKE（X，Y）：X喜欢Y ((?X)(MAN(X)∧LIKE(X, 梅花)) ∧ ((?Y)(MAN(Y)∧LIKE(Y,菊花))∧ ((?Z)(MAN(Z)∧(LIKE(Z,梅花) ∧LIKE(Z,菊花)) （2）他每天下午都去打篮球。 答：定义谓词：TIME(X):X是下午 PLAY(X,Y):X去打Y （?X）TIME(X) PLAY(他,篮球) （3）并不是每一个人都喜欢吃臭豆腐。 定义谓词：MAN（X）：X是人 LIKE（X，Y）：X喜欢吃Y ┐（（?X）MAN（X） LIKE（X，CHOUDOUFU）） 2 ．请对下列命题分别写出它的语义网络： （1）钱老师从 6 月至 8 月给会计班讲《市场经济学》课程。 （2）张三是大发电脑公司的经理，他 35 岁，住在飞天胡同 68 号。
（3）甲队与乙队进行蓝球比赛，最后以 89 ： 102 的比分结束。 3. 框架表示法 一般来讲，教师的工作态度是认真的，但行为举止有些随便，自动化系教师一般来讲性格内向，喜欢操作计算机。方园是自动化系教师，他性格内向，但工作不刻苦。试用框架写出上述知识，并求出方圆的兴趣和举止？ 答： 框架名：<教师> 继承：<职业> 态度：认真 举止：随便 框架名：<自动化系教师> 继承：<教师> 性格：内向 兴趣：操作计算机框架名：<方园> 继承：<自动化系教师> 性格：内向 态度：不刻苦 兴趣：操作计算机 举止：随便 4. 剧本表示法 作为一个电影观众，请你编写一个去电影院看电影的剧本。
一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y))) 一. 利用代换实例判断下列公式的类型 (1) (?xA(x)→?xA(x))→(??yB(y)∨?yB(y)) (2) ?(?xF(x)→?xB(x))∧?xB(x) 二. 利用等值演算, 求证?x?y(P(x)→Q(y))??xP(x)→?yQ(y) 三. 利用等值演算, 求证??x?y(F(x) ∧(G(y) →H(x,y))) ??x?y((F(x) →G(y))∧( F(x) →? H(x,y)))
第２章 附加题 请写出用一阶谓词逻辑表示法表示知识的步骤。 步骤：（1）定义谓词及个体，确定每个谓词及个体的确切含义；（2）根据所要表达的事物或概念，为每个谓词中的变元赋予特定的值；（3）根据所要表达的知识的语义用适当的联接符号将各个谓词联接起来，形成谓词公式。 什么是子句？什么是子句集？请写出谓词公式子句集的步骤。 解：子句就是由一些文字组成的析取式。由子句构成的集合称为子句集。 步骤：（1）消去谓词公式中的蕴涵和双条件符号，以(A(B代替A(B，以(A(B)(((A((B)替换A(B。（2）减少不定符号的辖域，使不定符号最多只作用到一个谓词上。 （3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。（4）消去存在量词。 （5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。 （6）母式化为合取范式，建立起与其对应的子句集。 2-2 用谓词表示法求解修道士和野人问题。在河的北岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但要受到以下条件限制： (1) 修道士和野人都会划船，但船一次只能装运两个人。 (2) 在任何岸边，野人数不能超过修道士，否则修道士会被野人吃掉。 假定野人愿意服从任何一种过河安排，请规划出一种确保修道士安全的过河方案。要求写出所用谓词的定义、功能及变量的个体域。 解：（1）定义谓词 先定义修道士和野人人数关系的谓词： G(x,y,S)：在状态S下x大于y GE(x,y,S)：在状态S下x大于或等于y 其中，x,y分别代表修道士人数和野人数，他们的个体域均为{0,1,2,3}。 再定义船所在岸的谓词和修道士不在该岸上的谓词： Boat(z,S)：状态S下船在z岸 EZ(x,S)：状态S下x等于0，即修道士不在该岸上 其中，z的个体域是{L,R}，L表示左岸，R表示右岸。 再定义安全性谓词： Safety(z,x,y,S)≡(G(x,0,S)∧GE(x,y,S))∨(EZ(x,S)) 其中，z,x,y的含义同上。该谓词的含义是：状态S下，在z岸，保证修道士安全，当且仅当修道士不在该岸上，或者修道士在该岸上，但人数超过野人数。该谓词同时也描述了相应的状态。 再定义描述过河方案的谓词： L-R(x, x1, y, y1,S)：x1个修道士和y1个野人渡船从河的左岸到河的右岸 条件：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S) 动作：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(R,S’) R-L (x, x1, y, y1,S)：x2个修道士和y2个野人渡船从河的左岸到河的右岸 条件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S) 动作：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(L,S’) (2) 过河方案 Safety(L,3,3,S0)∧Safety(R,0,0,S0)∧Boat(L,S0)
第二节 谓词公式的分类与解释 为了给出谓词公式的定义，先给出项和原子公式的定义。 定义2.1 项： （1） 个体常项和个体变项是项； （2） 设),...,,(21n x x x ?是任意的n 元函数，n t t t ,...,,21是项，则),...,,(21n t t t ?是项； （3） 有限地使用（1），（2）形成的符号串是项。 定义2.2 设),...,,(21n x x x R 是任意的n 元谓词，n t t t ,...,,21是项，则称),...,,(21n t t t R 是原子公式。 定义2.3合式公式： （1） 原子公式是合式公式； （2） 若A 是合式公式，则)(A ?也是合式公式； （3） 若B A ,是合式公式，则)(),(),(),(B A B A B A B A ?→∨∧也是合式公式； （4） 若A 是合式公式，则(),()xA xA ??也是合式公式。其中x 为任意的个体变项； （5） 有限次地应用（1）～（4）形成的字符串是合式公式。 这样定义的合式公式又称作谓词公式，简称公式。合式公式的最外层括号可以省去。 定义2.4 （1） 在公式xA ?和xA ?中，A 是相应量词的辖域，x 称为指导变量。 （2） 在公式xA ?和xA ?中，x 的所有出现都是约束出现的，不是约束出现的变项称 为自由出现的。 例如：在公式))),,()((),((z y x L y G y y x F x ∧?→?中，?的辖域为 ))),,()((),((z y x L y G y y x F ∧?→ ?的辖域为 )),,()((z y x L y G ∧ x ?中的x 和y ?中的y 都是指导变量。x 的出现都是约束的，),(y x F 中的y 是自由出现的，)(y G 与),,(z y x L 中的y 是约束出现的，z 的出现是自由的。 一般情况下，在一个谓词公式A 中，除了可能含若干个个体常项，函数常项，谓词常 项外，还可能含个体变项，函数变项，谓词变项等。用下面定义对公式进行解释。 定义2.5 一个解释I 由下面4个部分构成： （1） 非空的个体域D ； （2） D 上一部分特定的元素； （3） D 上一些特定的函数；
人工智能复习参考（2012工程硕士） 第1部分绪论 什么是人工智能？试从学科和能力两方面加以说明。 答：从学科方面定义：人工智能是计算机科学中涉及研究、涉及应用智能机器的一个分支。它的近期主要目标在于研究用机器来模范和执行人脑的某些智力功能，并开发相关理论和技术。从能力方面定义：人工智能是智能机器所执行的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。 在人工智能的发展过程中，有哪些思想和思潮起了重要作用？ 答：1)数理逻辑和关于计算本质的新思想, 提供了形式推理概念与即将发明的计算机之间的联系。 2)1956年第一次人工智能研讨会召开, 标志着人工智能学科的诞生. 3)控制论思想把神经系统的工作原理与信息理论、控制理论、逻辑以及计算联系起来。影响了许多早期人工智能工作者，成为他们的指导思想。 4)计算机的发明发展, 5)专家系统和知识工程 6)机器学习、计算智能、人工神经网络和行为主义研究, 推动人工智能研究的进一步发展。 为什么能够用机器（计算机）模仿人的智能？ 答：物理符号系统的假设：任何一个系统，如果它能够表现出智能，那么它就必定能执行输入符号、输出符号、存储符号、复制符号、建立符号结构、条件性迁移6种功能。反之，任何系统如果具有这6种功能，那么它就能够表现出智能(人类所具有的智能)。 物理符号系统的假设伴随有3个推论。 推论一: 既然人具有智能，那么他(她)就一定是个物理符号系统。 推论二: 既然计算机是一个物理符号系统，它就一定能够表现出智能。 推论三: 既然人是一个物理符号系统，计算机也是一个物理符号系统，那么我们就能够用计算机来模拟人的活动。 人工智能的主要研究内容和应用领域是什么？其中，哪些是新的研究热点？ 答：研究和应用领域：问题求解(下棋程序)，逻辑推理与定理证明(四色定理证明)，自然语言理解，自动程序设计，专家系统，机器学习，神经网络，机器人学(星际探索机器人)，模式识别(手写识别，汽车牌照识别，指纹识别)，机器视觉(机器装配，卫星图像处理)，智能控制，智能检索，智能调度与指挥(汽车运输高度，列车编组指挥)，系统与语言工具 新的研究热点：概率图模型（隐马尔可夫模型、贝叶斯网络）、统计学习理论(SLT) & 支持向量机(SVM)、数据挖掘与知识发现(超市市场商品数据分析)，人工生命 人工智能的发展对人类有哪些方面的影响？试结合自己了解的情况和理解，从经济、社会和文化等方面加以说明？1、人工智能对经济的影响：人工智能系统的开发和应用，已为人类创造出可观的经济效益，专家系统就是一个例子。随着计算机系统价格的继续下降，人工智能技术必将得到更大的推广，产生更大的经济效益。 2、人工智能对社会的影响：劳务就业问题；社会结构变化；思维方式与观念的变化；心理上的威胁；技术失控的危险。 3、人工智能对文化的影响：改善人类知识；改善人类语言；改善文化生活。 试评述人工智能的未来发展。 答：我认为主要有以下两个发展方向：1、计算机能直接而人类大脑实现人机交流。借助以上技术，人类可以用思维控制自己想看到的，想听到的，使媒体技术中的感官媒体更真实化，对虚拟的事物不仅可以看见听见，更可以摸得，闻得着。同时电脑可以进一步辅助人类做出一定的判断，储存大量信息，甚至可以以身体为媒介，执行电脑程序，是人类更快的学会各种技巧，掌握更多知识。同时，提高了生物验证的渠道，比如利用DNA染色体作为密码的载体，相信是很难伪造的。2、电脑拥有机器思维：机器学会人类的思维方式，帮助人更好的思考问题。 第2部分知识表示 什么是知识？知识的要素有哪些？知识的表示方法有哪些？ 答：Feigenbaum：知识是经过削减、塑造、解释和转换的信息。简单地说，知识是经过加工的信息。Bernstein：知识是由特定领域的描述、关系和过程组成的。Hayes-Roth：知识是事实、信念和启发式规则。从知识库的观点看，知识是某领域中所涉及的各有关方面的一种符号表示。 知识的要素有：事实：有关问题环境的一些事物的知识，常以“…是…”的形式出现。规则：有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果…那么…”形式出现。控制：有关问题的求解步骤、技巧性
第三章思考题 3.1 什么是推理、正向推理、逆向推理、混合推理？试列出常引用的几种推理方式并列出每种推理方式的特点。 答：1）推理是指从已知事实出发，运用已掌握的知识，推导出其中蕴含的事实性结论或归纳出某些新的结论的过程。 2）正向推理是一种从已知事实出发、正向使用推理规则的推理方式，它是一种数据（或证据）驱动的推理方式，又称前项链推理或自底向上推理。 3）反向推理是一种以某个假设目标为出发点，反向运用推理规则的推理方式，它是一种目标驱动的推理方式，又称反向链推理或自顶向下推理。 4）混合推理是把正向推理和反向推理结合起来所进行的推理。 常引用的推理方式有演绎推理、归纳推理和默认推理。 演绎推理是从全称判断推倒出单称判断的过程，即有一般性只是推导出适合于某一具体情况的结论。是一种从一般到个别的推理。 归纳推理是从足够的事例中归纳出一半般结论的推理过程，是一种从个别到一般的推理。 默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理。 3.2 什么是冲突？在产生式系统中解决冲突的策略有哪些？ 答：1）已知事实与知识库中的多个知识匹配成功称发生了冲突。 2）解决冲突的策略有1）按针对性排序2）按已知事实的新鲜性排序3）按匹配度排序4）按条件个数排序5）按上下文限制排序6）按冗余限制排序7）根据领域问题的特点排序。 3.3 什么是子句？什么是子句集？请写出求谓词公式子句集的步骤。 答：1）任何原子谓词公式及其否定的析取式为子句。 2）由子句构成的集合称为子句集。 求谓词公式子句集的步骤：1）消去谓词公式中的“→”和“?”符号，2）把否定符号移到靠紧谓词的位置上，3）变量标准化，4）消去存在量词，5）化为前束型，6）化为Skolem标准型，7）略去全称量词，8）子句变量标准化。 3.4 谓词公式与它的子句集等价吗？在什么情况下它们才会等价？ 答：1）谓词公式与它的子句集不是总等价的。 2)在谓词公式不可满足的情况下是等价的。 3.5 为什么要引入Herbrand理论？什么是H域？如何求子句集的H 域？ 答：1）引入Herbrand理论能够构造一个特殊域，判定子句在域上的解释，从而判定该自居的不可满足性，从而可以判定子句集的不可满足性，继而判定谓词公式的不可满足性。 2）H域也称海伦伯域。满足以下条件： ①令H0是S中所有个体常量的集合。若S中不包含个体常量，则令H0={a}。其中a为任意指定的一个个体常量。
第二章谓词逻辑 练习一 1、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题： （1）?x(P(x)∨Q(x))∧R （R为命题常元） （2）?x(P(x)∧Q(x))∧?xS(x)→T(x) （3）?x(P(x)→?y(B(x,y)∧Q(y))∨T(y)) （4）P(x)→(?y?x(P(x)∧B(x,y))→P(x)) 解（1）全称量词?，辖域P(x)∨Q(x)，其中x为约束变元，?x(P(x)∨Q(x))∧R是命题。 （2）全称量词?，辖域P(x)∨Q(x)，其中x为约束变元。 存在量词?，辖域S(x) ，其中x为约束变元。 T(x)中x为自由变元。?x(P(x)∧Q(x))∧?xS(x)→T(x)不是命题。 （3）全称量词?，辖域P(x)→?y(B(x,y)∧Q(y))∨T(y)，其中x为约束变元，T(y)中y为自由变元。存在量词?，辖域B(x,y)∧Q(y)，其中y为约束变元。?x(P(x)→?y(B(x,y)∧Q(y))∨T(y))是命题。 （4）全称量词?，辖域?x(P(x)∧B(x,y))，其中y为约束变元。 存在量词?，辖域P(x)∧B(x,y)，其中x为约束变元。 不在量词辖域中的P(x)中的x为自由变元。P(x)→(?y?x(P(x)∧B(x,y))→P(x)) 不是命题。 2、对个体域{0，1}判定下列公式的真值, E(x)表示“x是偶数”： （1）?x(E(x)→┐x=1) （2）?x(E(x)∧┐x=1) （3）?x(E(x)∧x=1) （4）?x(E(x)→x=1) 再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。
排列组合公式/排列组合计算公式 2008-07-08 13:30 公式P是指排列，从N个元素取R个进行排列。 公式C是指组合，从N个元素取R个，不进行排列。 N-元素的总个数 R参与选择的元素个数 ！-阶乘，如9！＝9*8*7*6*5*4*3*2*1 从N倒数r个，表达式应该为n*（n-1)*(n-2)..(n-r+1); 因为从n到（n-r+1)个数为n－（n-r+1)＝r 举例： Q1:有从1到9共计9个号码球，请问，可以组成多少个三位数？ A1: 123和213是两个不同的排列数。即对排列顺序有要求的，既属于“排列P”计算范畴。 上问题中，任何一个号码只能用一次，显然不会出现988,997之类的组合，我们可以这么看，百位数有9种可能，十位数则应该有9-1种可能，个位数则应该只有9-1-1种可能，最终共有9*8*7个三位数。计算公式＝P（3，9)＝9*8*7,(从9倒数3个的乘积） Q2: 有从1到9共计9个号码球，请问，如果三个一组，代表“三国联盟”，可以组合成多少个“三国联盟”？ A2: 213组合和312组合，代表同一个组合，只要有三个号码球在一起即可。即不要求顺序的，属于“组合C”计算范畴。 上问题中，将所有的包括排列数的个数去除掉属于重复的个数即为最终组合数C(3,9)=9*8*7/3*2*1 排列、组合的概念和公式典型例题分析 例1设有3名学生和4个课外小组．（1）每名学生都只参加一个课外小组；（2）每
名学生都只参加一个课外小组，而且每个小组至多有一名学生参加．各有多少种不同方法？ 解（1）由于每名学生都可以参加4个课外小组中的任何一个，而不限制每个课外小组的人数，因此共有种不同方法． （2）由于每名学生都只参加一个课外小组，而且每个小组至多有一名学生参加，因此共有种不同方法． 点评由于要让3名学生逐个选择课外小组，故两问都用乘法原理进行计算． 例2 排成一行，其中不排第一，不排第二，不排第三，不排第四的不同排法共有多少种？ 解依题意，符合要求的排法可分为第一个排、、中的某一个，共3类，每一类中不同排法可采用画“树图”的方式逐一排出： ∴ 符合题意的不同排法共有9种． 点评按照分“类”的思路，本题应用了加法原理．为把握不同排法的规律，“树图”是一种具有直观形象的有效做法，也是解决计数问题的一种数学模型． 例３判断下列问题是排列问题还是组合问题？并计算出结果． （1）高三年级学生会有11人：①每两人互通一封信，共通了多少封信？②每两人互握了一次手，共握了多少次手？ （2）高二年级数学课外小组共10人：①从中选一名正组长和一名副组长，共有多少种不同的选法？②从中选2名参加省数学竞赛，有多少种不同的选法？ （3）有2，3，5，7，11，13，17，19八个质数：①从中任取两个数求它们的商可以有多少种不同的商？②从中任取两个求它的积，可以得到多少个不同的积？ （4）有8盆花：①从中选出2盆分别给甲乙两人每人一盆，有多少种不同的选法？②从中选出2盆放在教室有多少种不同的选法？ 分析（1）①由于每人互通一封信，甲给乙的信与乙给甲的信是不同的两封信，所以与顺序有关是排列；②由于每两人互握一次手，甲与乙握手，乙与甲握手是同一次握手，与顺序无关，所以是组合问题．其他类似分析． （1）①是排列问题，共用了封信；②是组合问题，共需握手（次）． （2）①是排列问题，共有（种）不同的选法；②是组合问题，共有种不同的选法． （3）①是排列问题，共有种不同的商；②是组合问题，共有种不同的积． （4）①是排列问题，共有种不同的选法；②是组合问题，共有种不同的选法． 例４证明． 证明左式