[文学]第2章 基于谓词逻辑的机器by toby.ppt

第2章 基于谓词逻辑的机器推理 2.1 一阶谓词逻辑 2.2 归结演绎推理 2.3 应用归结原理求取问题答案 2.4 归结策略 2.5 Horn子句归结与逻辑程序 2.1 一阶谓词逻辑 2.1.1 谓词、函数、量词 设a1, a2, …, an表示个体对象，A表示它们的属性、状态或关系，则表达式A(a1, a2, …, an)在谓词逻辑中就表示一个(原子)命题。例如， 1. 素数(2)，就表示命题“2是个素数”。 2. 好朋友(张三，李四)，就表示命题“张三和李四是好朋友”。 一般地，表达式 P(x1, x2, …, xn) 在谓词逻辑中称为n元谓词。其中P是谓词符号，也称谓词，代表一个确定的特征或关系(名)。x1, x2, …, xn称为谓词的参量或者项，一般表示个体。 个体变元的变化范围称为个体域（或论述域），包揽一切事物的集合称为全总个体域。为了表达个体之间的对应关系，我们引入通常数学中函数的概念和记法。 例如我们用father(x)表示x的父亲，用sum(x, y)表示数x和y之和，一般地，我们用如下形式： f(x1, x2, …, xn) 表示个体变元x1, x2, …, xn所对应的个体y，并称之为n元个体函数，简称函数（或函词、函词命名式）。其中f是函数符号，有了函数的概念和记法，谓词的表达能力就更强了。 ? ? 例如，我们用Doctor(father(Li))表示“小李的父亲是医生”，用E(sq(x), y))表示“x的平方等于y”。 以后我们约定用大写英文字母作为谓词符号，用小写字母f,g,h等表示函数符号，用小写字母x,y,z等作为个体变元符号，用小写字母a,b,c等作为个体常元符号。 我们把“所有”、“一切”、“任一”、“全体”、“凡是”等词统称为全称量词，记为 x；把“存在”、“有些”、“至少有一个”、“有的”等词统称为存在量词，记 为 x。 引入量词后，谓词的表达能力就大大扩充了，例如命题“凡是人都有名字”，就可以表示为 x (M(x)→N(x)) 其中M(x)表示“x是人”，N(x)表示“x有名字”，该式可读作“对于任意的x，如果x是人，则x有名字”。这里的个体域取为全总个体域。如果把个体域取为人类集合，则该命题就可以表示为 x N (x) 同理，我们可以把命题“存在不是偶数的整数”表示为 x (G(x)∧乛E(x)) 其中G(x)表示“x是整数”，E(x)表示“x是偶数”。此式可读作“存在x，x是整数并且x不是偶数”。 5种联结词的定义: (1)乛:否定, 乛Q表示否定Q真值的命题,即”非Q” (2) ∧:合取,P∧Q表示”P与Q” (3) ∨:析取,P∨Q表示”P或Q” (4) →:条件(蕴含),P→Q表示”如果P,那么Q” :双条件(等值),P Q表示”P当且仅当Q” 运算优先次序:乛, ∧, ∨, →, 不同的个体变元，可能有不同的个体域。为了方便和统一起见，我们用谓词表示命题时，一般总取全总个体域，然后再采取使用限定谓词的办法来指出每个个体变元的个体域。具体来讲，有下面两条： (1)对全称量词，把限定谓词作为蕴含式之前件加入，即 x(P(x)→…)。 ? (2)对存在量词，把限定量词作为一个合取项加入，即 x(P(x)∧…)。这里的P(x)就是限定谓词。 我们再举几个例子。 例2.1 不存在最大的整数，我们可以把它翻译为 乛 x (G(x)∧ y(G(y)→D(x,y)) 或 x (G(x)→ y(G(y)∧D(y,x)) 例2.2 对于所有的自然数，均有x+yx x y(N(x)∧N(y)→S(x, y, x)) 例2.3 某些人对某些食物过敏 x y(M(x)∧F(y)∧G(x, y)) 2.1.2 谓词公式