§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:)(
4. 给定解释I 如下： 个体域R =D （这里R 为实数集合）。 个体常元0=a 。
二元函数y x y x f -=)(，。
二元谓词y x y x P =：，)(，y x y x Q <：，)(。
在解释I 下，下列公式的含义是什么？哪些成为命题哪些不成为？成为命题的其真值又如何？ （1）))()((y x P y x Q y x ，，?→?? （2）))())(((y x Q a y x f P y x ，，，→?? （3）)))(()((a y x f P y x Q y x ，，，?→??
（4）))())(((y x P a y x f Q y x ，，，→??
解（1）公式被解释成“)(y x y x y x ≠→
（2）公式被解释成“)0(y x y x y x <→=-??”，为假命题。
（3）公式被解释成“)0(≠-→
5. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。 （1）)()(x xP x P ?→ （2）)()(x P x xP →? （3）)()(x xP x P ?→
（4）)()(x P x xP →?
（5）))()((x P x P x ?→?
（6）)()(y x xP y y x yP x ，，??→?? （7）)()(x y yP x y x yP x ，，??→?? （8）)()(y x yP x y x yP x ，，??→??
（9）)()(y x xP y y x yP x ，，??→??
（10）))()((x y P y x P y x ，，→??
解（1）因为当存在某个x 使)(x P 取1时)(x xP ?一定取1，所以公式是为永真式。 （3）取解释1I ：个体域为自然数集合，0)(2
≥x x P ：。在1I 下公式的前件与后件均为真，所以公式为真，即不是永假式。取解释2I ：个体域仍为自然数集合，但)(x P 取为0>x 。在2I 下公式不成为命题，即不是永真式。综合知公式为可满足式。
（5）取解释1I ：个体域为自然数集合，0)(2
≥x x P ：。在1I 下，对任意的x ，)(x P 为真而)(x P ?为假，所以公式为假，即不是永真式。取解释2I ：个体域仍为自然数集合，但)(x P 取为02
不是永假式。综合知公式为可满足式。 （7）公式为永真式，用非形式化的反证法证明如下：若公式非永真，则存在一个解释，使得)(y x yP x ，??取1而)(x y yP x ，??取0。)(x y yP x ，??取0表明存在某对00,y x 使得)(00x y P ，取0，从而)(y x yP x ，??也应取0。这与前面说)(y x yP x ，??取1矛盾。故公式是永真式。 （9） 设I 为任意一个解释，个体域为D 。若)(y x yP x ，??取1，即存在D x ∈0， 使得)(0y x yP ，?为真，从而)(y x xP y ，??为真，故)()(y x xP y y x yP x ，，??→??为真。所以在解释I 下公式为真，由I 的任意性可知，公式为永真式。 （2）、（4）、（6）、（8）、（10）略。 6. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。 （1）))()(())()((y yQ x xP x Q x P x ?∧?→∧? （2）))()(())()((y yQ x xP x Q x P x ?∨?→∨? （3）)())()((y yQ y yQ x xP ?∧?→?? （4）))()(())()((x xQ y P x Q y P x ?→→→? （5）))()(())()((x xQ x P x Q x P x ?→→→? （6）)))()(()((x P y x yQ x P →?→?， （7）))()(()(y x P y x Q y x P ，，，→→ 解 略 7. 给出一个非闭式的永真式，给出一个非闭式的永假式，给出一个非闭式的可满足式。 解 略 一、选择题（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、什么是推理？它有哪些分类方法？ 答： 谓词逻辑习题 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.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. 剧本表示法 作为一个电影观众，请你编写一个去电影院看电影的剧本。 从而 ， , , , 有 . (20) 四、格林公式 平面曲线积分，当曲线C（A,B）的始点A与终点B重合时（即C是一条闭曲线），在力学、电学等有很多应用。因为第二型曲线积分与所沿平面闭曲线的曲线积分要规定闭曲线的正方向。按右手坐标系，当一个人沿着平面闭曲线环行时，闭曲线所围成的区域位于此人的左侧，规定这个方向是曲线的正方向，如图14.7，反之是负方向，如图14.8 沿闭曲线C的曲线积分，记为 规定其中曲线C 总是取正方向。格林公式给出了平面区域上的二重积分与沿着该区域边界的闭曲线的曲线积分之间的关系。 设D 是有向的x 型或y 型闭区域，即 ,如图14.9， 或 {(x,y)│φ1 (y )≤y≤φ2 (y ),a≤x≤b}，如图14.10. 这里的 ， 在[a,b]上是连续函数，φ1 (y)，φ2 (y)在[a,b]上是连续函数，D 的正负向 按上面的规定。 定理3（格林公式） 若函数P ,Q 及其偏导数，在有界闭区域D 上连续，则有 . (21) 其中是围成闭区域D 的边界封闭曲线，取正向。公式（21）称为格林公式 格林公式是两个等式组成的： 与 证明由于区域D形状不同，定理证明分三步进行。1）设D是x型闭区域（如图14.9）。 dx ]. (22) 由曲线积分的计算公式，按图14.9，有 ? ? ? ??+ + + = ) , ( ) , ( ) , ( ) , ( ) , ( ) , ( ) , ( ) , ( ) , ( H N N M M K K H dx y x P dx y x P dx y x P dx y x P dx y x P τ τ τ ττ , 其中 ? ?=b a K H dx x x P dx y x P)] ( , [ ) , ( 1 ) , ( ? τ ， ? ? ?-= = b a a b M K dx x x P dx x x P dx y x P)] ( , [ )] ( , [ ) , ( 2 2 ) , ( ? ? τ 因为线段KM与NH都平行于y轴，有 ) , ( ) , ( ) , ( ) , ( = =? ? H N M K dx y x P dx y x P τ τ . 于是， ? ? ?- = Γ b a b a dx x x P dx x x P dx y x P)] ( , [ )] ( , [ ) , ( 2 1 ? ? =dx x x P x x P b a )]} ( , [ )] ( , [ { 1 2 ? ?- -?。（23） 由（22）式与（23）式，有 ? ?? Γ = ? ? -dx y x P dxdy y P D ) , (（24） 若D又是y型闭区域（如图14.10）.同理可证 ? ?? Γ = ? ? dx y x Q dxdy y Q D ) , (，（25） 2）若闭区域D是一条光滑或逐段光滑的闭曲线Γ所围成，则先用几段光滑曲线将D 分成有限个既是x型又是y型闭区域，然后逐块按照1）的计算方法得格林公式，再逐块相加即得（21）式。其中在D内两个小区域有共同边界，则因正向取向恰好相反，他们的积分值正好互相抵消。 一. 利用代换实例判断下列公式的类型 (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))) 格林公式的推导 推导格林公式之前，首先要深入理解高斯-散度定律： v div dv Γ=?????F Fds (1) 其实就是一句话， 矢量的散度的体积积分=矢量的面积积分。简单来说可以这样理解：对比等式左右两端，左端的被积函数求了散度（就是微分运算）比右端低了一阶，因此左端的积分变量上就要比右端高一阶（由面元变为体元）。 详细说明如下： 注意P Q R =++F i j k 为矢量，散度算子div x y z ???=++???i j k 也是矢量，因此等式左端是两个矢量的标量积的体积积分。 而等式右端，面积微元()cos cos cos ds ds αβγ==++ds n i j k 也是矢量，因此等式右端实际上是两个矢量的标量积的面积积分。 这样将上式（1）展开，可以得到高斯-散度定理另一种形式： ()cos cos cos v P Q R dv P Q R ds x y z αβγΓ?????++=++ ?????? ????? (2) 注意，上述推导中矢量的处理（矢量都已加粗并上标箭头），不要混淆了。 明白了以上几点，再推导格林公式就很容易了： 令,,v v v P u Q u R u x y z ???===???代入（2）式： 左端： v v v P Q R u v u v u v dv u vdv dv x y z x x y y z z ?????????????++=?+++ ? ?????????????? ????????? 右端： ()cos cos cos cos cos cos P Q R ds v v v u ds x y z v u ds n αβγαβγΓΓΓ++???????=++?? ????? ????=??????? 最后一步逆用了方向导数的定义，方向恰为外法线方向： cos cos cos αβγ=++n i j k 稍微整理，即得格林第一公式： v v u u v u v u v v udv v ds dv n x x y y z z Γ??????????=-++ ?????????? ???????? (3) 第２章 附加题 请写出用一阶谓词逻辑表示法表示知识的步骤。 步骤：（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 上一些特定的函数； 在导出黎曼问题的弱解概念时，在欧拉方程两边同时乘以任意函数再积分转化为一等价的“弱”形式的方程时用到了二重积分的分部积分方法，其实就是格林公式。 一般意义下的分部积分公式： uv dx uv vu dx ''=- ?? 或udv uv vdv =-?? 证明： 分部积分实际上是把普通积分公式f dx f ' =?中的被积函数f 换成了两个函数的乘积，故可称之为一维情况下的分部积分； 把普通积分公式运用到二维情况，其实就得到了格林公式，格林公式实现了把面积分转换成了线积分（降次）。 格林公式： F dxdy Fdy x Ω ?Ω ?=??? ? F dxdy Fdx y Ω ?Ω ?=-??? ? 一般合并写为D L Q P dxdy Pdx Qdy x y ?? ??-= + ???????? 证明（以第一个公式为例）： 积分域为{ }(x,y)|a(y)x b(y),c y d Ω=≤≤≤≤，如图： 则： (y)(y) (y)(y) (x,y)((y),y)((y),y)d b c a d x b x a c d d c c F dxdy x F dxdy x F dy F b dy F a dy Fdy Ω ==?Ω ???= ?==-= ?? ?????? 类似地，把格林公式中的被积函数换成两个函数的乘积，则导出二维情况下 的分部积分。 二重积分的分部积分公式： ()g f f dxdy fg dy g dxdy x x Ω ?Ω Ω ??=-??????? ()g f f dxdy fg dx g dxdy y y Ω ?Ω Ω ??=--??????? 证明（以第一个公式为例）： 在F dxdy Fdy x Ω ?Ω ?=??? ? 中，把F 换为fg ，则： () ()fg dxdy fg dy x Ω ?Ω ?=??? ? ， 即()()g f f g dxdy fg dy x x Ω ?Ω ??+=????? 即()g f f dxdy fg dy g dxdy x x Ω ?Ω Ω ??=- ??????? 综上： 把普通积分公式中的被积函数换成两个函数的乘积，则导出了一维分部积分公式； 把格林公式中的被积函数换成两个函数的乘积，则导出了二维分部积分公式。 且两种分部积分公式在形式上是很相似的： uv dx uv vu dx ''=-??对比()g f f dxdy fg dy g dxdy x x Ω ?Ω Ω ??=-??????? 北航曾元圆 人工智能复习参考（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) 再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。西工大计算智能化试题(卷)
人工智能习题讲课讲稿
谓词逻辑习题及答案
人工智能第3版王万森部分习题答案
《应用离散数学》谓词公式及其解释
人工智能-化为子句集的九步法实验
第3章 参考答案
模式识别习题答案
格林公式
第七次作业(谓词公式类型及等值演算)
[0315]格林公式的推导
人工智能第4版部分课后答案
谓词公式的分类与解释
二重积分的分部积分公式与格林公式
人工智能考试提纲与答案
人工智能 第三章思考题
谓词逻辑练习及答案
相关主题
文本预览