产生式及一阶谓词.ppt

第四讲 基于逻辑的问题求解方法 逻辑表示法 用数理逻辑表示知识 经典逻辑（标准逻辑） 非经典逻辑 一阶谓词是一种形式语言，可以表示和推理客观世界的属性和关系。 第一节 一阶谓词逻辑基础 命题 取值为真或假(表示是否成立)的句子 谓词 带有变量(参数)的命题 谓词 p (x1，x2，…，xn) 一元谓词 谓词与一个个体的属性 blue ( desk ) 多元谓词 谓词与多个个体间的关系 TEACHER(x, y) 一阶谓词 xi 为常量、变元或函数 高阶谓词 xi 本身为一阶谓词 一、谓词逻辑的符号体系 连接词 量词 二、谓词逻辑的知识表示 1 形式化的领域 2 非形式化的领域 三、谓词演算公式 第二节 逻辑推理 一、等价式 二、自然演绎推理 例 设已知如下事实： (1) 只要是需要编程序的课，王程都喜欢。 (2) 所有的程序设计语言课都是需要编程序的课 (3) C是一门程序设计语言课。 求证：王程喜欢C这门课。 证明：首先定义谓词 program (X) X是需要编程序的课。 like (X,Y) X喜欢Y。 language (X) X 是—门程序设计语言课。 把已知事实及待求解问题用谓词公式表示如下： program (X) ?like ( wang, X)、 (?X)( language (X)? program (X))、language (C) 应用推理规则进行推理： 全称例化 language (Y)? program (Y) 假言推理 language (C), language (Y)? program (Y) ? program (C) 假言推理 program (C), program (X)? like ( wang, X) ? like ( wang, C) 王程喜欢C这门课。 二、归结(消解)原理简介 归结式 ? 自动归结证明的过程： WFF化为子句的基本步骤 例 已知每个使用Internet的人都想从网络获得信息，证明如网络没有信息就不会有人使用Internet。 条件：W= (?x)[ (?y)(U(x, y)∧I(y))→(?u)(F(u)∧E(x, u))] 变换为子句集。 归结策略 例 等腰三角形ABC，AD为底边的高，试证明BD=CD. 问题求解 问题求解（续） 前束范式 设F为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，而它们的辖域为整个公式，则称F为前束范式。 F(x, y, w)=(?w) (?x) (?y) (P(x) ?Q(y, w)? R(x,w)) 任一谓词公式均可化为与其对应的前束范式，其化简方法将在后面子句集的化简中讨论。 Skolem范式 前束范式中所有的存在量词都在全称量词之前的谓词公式形式。 1 置换 2 合一 WFF的基本等价式及推理规则（续）： 12 量词消去及引入规则： 全称量词消去规则：(?x)P(x) ≡ P(y) 它说明：如果个体域的所有元素具有性质P，则个体域中的任一个元素具有性质P。 全称量词引入规则：P(y) ≡ (?x)P(x) 存在量词消去规则： (?y) (?x)P(x, y) ≡ (?y) P(g(x), y) 引入函数g(y)表示x ，称为SKOLEM 函数。注意，这里的函数g应是原WFF中没有的符号。 不含任何连接词的谓词公式是原子公式； 原子公式及其否定为文字； 一些文字的析取式(或项)为子句； 一些子句的集合为子句集。 用特定的项(常量、变量或函数符号) v 替代公式中的某变量t，对公式进行置换后得到的新公式称为公式的实例(instance)。 只能用项v置换变量t，且必须置换公式中出现的一切 t，置换记为 s = v /t。 P(x, f(y)) s={z/x, w/y} P ∥s= P(z, f(w)) 任一被替代的变量不能出现在置换公式中。 s=(g(x)/x) ? 置换不唯一 置换是可结合的，即 (L∥s1) ∥ s2 = L∥ (sl