人工智能学科体系

人工智能学科体系内容摘要：

1. 个体常项和变项是项 2. 若 φ(x1,x2,… ,xn)是任意的 n元函数，x1,x2,… ,xn是项，则 φ(x1,x2,… ,xn)是项 3. 只有有限次地使用 1， 2生成的符号才是项 a,b,x,y, f(x,y), f(x,g(a,b,z)) 2020/11/17 50 合式公式（谓词公式）  原子公式 定义 13：设 R(x1,x2,..,xn)是任意的 n元谓词，t1,t2,… ,tn为项，则 R(t1,t2,… ,tn)称为原子公式  合式公式，定义 14： 1. 原子公式是合式公式 2. 如果 A是合式公式，则（ 172。 A）为合式公式 3. 如果 A,B是合式公式，则（ A∧ B） ,（ A∨ B） , （ A→ B） , （ A B）也是合式公式 4. 如果 A是合式公式，则 xA， xA也是合式公式 5. 只有有限次地应用 1－ 4组成的符号串才是合式公式（谓词公式） 2020/11/17 51 指导变项、辖域  定义 15：在合式公式 xA和 xA中，称 x为指导变项 ，称 A为相应量词的 辖域。 在辖域中，x的所有出现称为 约束出现 （即 x受相应量词指导变项的约束）， A中不是约束出现的其它变项称为 自由出现。  通常用 A(x)表示 x是自由出现的任意公式  例子  x(F(x)→ yH(x,y))  xF(x)∧ G(x,y)  x y(R(x,y)∨ L(y,z))∧ xH(x,y) 2020/11/17 52 闭式  定义 16：设 A为任一公式，若 A中无自由出现的个体变项，则称 A是 封闭的合式公式 ，简称 闭式。  例子： 2020/11/17 53 换名规则和代替规则  为了避免出现某个变项既是自由出现的又是约束出现的，使用以下 2种办法 换名规则 ：将量词辖域种出现的某个约束出现的个体变项及对应的指导变项，改成另外一个辖域中未曾出现过的个体变项符号，公式其它部分不变 xF(x)∧ G(x,y) zF(z)∧ G(x,y) 代替规则 ：对某个自由出现的个体变项用与原公式中的所有个体变项符号不同的变项符号来代替，且处处代替 xF(x)∧ G(x,y) xF(x)∧ G(z,y) 2020/11/17 54 公式的解释  公式的解释 ：一阶谓词公式中含有：个体常项，个体变项（自由出现或约束出现的），函数变项，谓词变项等。 对各种变项指定特殊的常项来代替，就构成公式的一个解释。  解释，定义 17 一个解释 I由下面的 4个部分构成 1. 非空个体域 D 2. D上的一部分特定的元素 3. D上的一些特定的函数 4. D上的一些特定的谓词 2020/11/17 55 解释的例子  解释  DI={2,3}  DI上的特定元素  函数： f(2)=3,f(3)=2  谓词： F(2)=0。 f(3)=1 G(x,y)为 G(i,j)=1, i,j=2,3。 L(x,y)为 L(2,2)=L(3,3)=1 L(3,2)=L(2,3)=0。  2020/11/17 56 公式的解释 2020/11/17 57 公式的性质  定义 18 设 A为一个公式 (谓词公式 ) 若 A在它的任何解释下取值均为真，则称 A为逻辑有效式 或 永真式 若 A在它的任何解释下取值均为假，则称 A为矛盾式 或 永假式 若 A至少存在一组解释是成真赋值，则称 A为可满足式 2020/11/17 58 代换实例  定义 19：设 A0是含命题变项 p1,p2,… ,pn的命题公式， A1,A2,… ,An是 n个谓词公式，用Ai(i=1… n)处处代替 pi，所得到的公式称为 A0的 代换实例  例子 命题公式： p∨ q A1 xF(x) A2 G(x,y) 代换实例： ( xF(x))∨ G(x,y) 2020/11/17 59 代换实例的一个结论  命题公式的重言式的代换实例在谓词逻辑中，仍然是重言式；  命题公式的矛盾式的代换实例在谓词逻辑中，仍然是矛盾式；  例子： 2020/11/17 60 一阶逻辑等值式  定义 20：设 A,B是一阶逻辑中的任意 2公式，若A B是逻辑有效式，则称 A与 B是 等值 的，记做 A B，称 A B为 等值式  命题逻辑中的 24条等值式的代换实例也是逻辑等值式 2020/11/17 61 谓词逻辑中的逻辑等值式 1  定理 1：量词否定等值式 2020/11/17 62 谓词逻辑中的逻辑等值式 2  定理 2：量词的 辖域收缩 和 扩张 等值式 2020/11/17 63 谓词逻辑中的逻辑等值式 3  定理 3： 量词分配 等值式 2020/11/17 64 谓词逻辑中的逻辑等值式 4  定理 4 量词的性质相同，可以交换位置 量词的性质不同，不可交换位置 2020/11/17 65 前束范式  定义 21：设 A为一谓词公式，如果 A具有如下形式： Q1x1Q2x2… QkxkB 则称 A是 前束范式。 其中每一个 Qi为 或 B为不含量词的谓词公式（ 母式 ） 例如： x y(F(x,y)→ G(x,y)) 前束范式 x(F(x)→ y(G(y)→ H(x))) 非前束范式 2020/11/17 66 前束范式例题  求下列公式的前束范式 2020/11/17 67 谓词公式的合取范式和子句集  对任一公式 量词辖域扩张和收缩定理，得到 前束范式 对于母式，等值演算得到 合取范式 合取项的集合，构成了该公式的 子句集 S  前束范式  母式 原子：谓词 文字：谓词或谓词的否定 子句：文字的析取 合取范式：子句的合取 子句集：合取范式的集合形式，元素之间的关系为合取关系 2020/11/17 68  一阶谓词逻辑  语法和语义： 谓词逻辑的基本组成、谓词符号、常量符号、变量符号、函数符号、项的递归定义、原子、谓词演算语言的语义  连词和量词： 合适公式、连词、合取、析取、蕴含、否定、等价、命题演算、全称量词、存在量词、约束变量、自由变量、句子、一阶谓词演算 表示方法 — 逻辑表示法 2020/11/17 69  谓词逻辑的基本组成 ：谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。  谓词符号 ：表示个体所具有的性质，或者若干个体之间的关系的符号。 习惯用大写字母 P， Q， R或 GREATER， LOVE表示。  常量符号 ：用来表示论域内的物体或实体，它可以是实际的物体和人，也可以是概念或具有名字的任何事情。 一般用英文字母表中前几个带下标或不带下标的小写字母表示。 如 a， b， ... ， a1，b2， c3， ...。 2020/11/17 70  变量符号 ：不必明确涉及是哪一个实体。 习惯上用带下标或不带下标的小写字母表示。 如 x，y， ... ， x1， y2，。  函数符号 ：表示论域内的函数。 习惯用小写字母 f，g， h表示。 2020/11/17 71 例如，要表示“机器人（ ROBOT）在 1号房间（ ROOM1）内”，简单的原子公式如下： INROOM（ ROBOT， r1） 式中， INROOM为谓词符号， ROBOT和 r1为常量符号。 又如，要表示“李（ LI）的母亲与他的父亲结婚”， 原子公式如下： MARRIED[father（ LI）， mother（ LI） ] 式中，函数符号 mother、 father分别用来表示某人与他（她的）母亲、父亲之间的 映射。 2020/11/17 72  谓词演算语言的语义 ：。