资源描述：
《基于谓词逻辑的机器》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章基于谓词逻辑的机器推理5.1一阶谓词逻辑5.2归结演绎推理5.3应用归结原理求取问题答案5.4归结策略5.5归结反演程序举例5.6Horn子句归结与逻辑程序5.7非归结演绎推理5.1一阶谓词逻辑5.1.1谓词、函数、量词设a1,a2,…,an表示个体对象,A表示它们的属性、状态或关系,则表达式A(a1,a2,…,an)在谓词逻辑中就表示一个(原子)命题。例如,(1)素数(2),就表示命题“2是个素数”。(2)好朋友(张三,李四),就表示命题“张三和李四是好朋友”。P(x1,x2,…,xn)一般地,表达式在谓词逻辑中
2、称为n元谓词。其中P是谓词符号，也称谓词，代表一个确定的特征或关系(名)。x1,x2,…,xn称为谓词的参量或者项，一般表示个体。个体变元的变化范围称为个体域（或论述域），包揽一切事物的集合称为全总个体域。为了表达个体之间的对应关系，我们引入通常数学中函数的概念和记法。例如我们用father(x)表示x的父亲，用sum(x,y)表示数x和y之和，一般地，我们用如下形式：f(x1,x2,…,xn)表示个体变元x1,x2,…,xn所对应的个体y，并称之为n元个体函数，简称函数（或函词、函词命名式）。其中f是函数符号，有了函数的概念
3、和记法，谓词的表达能力就更强了。例如，我们用Doctor(father(Li))表示“小李的父亲是医生”，用E(sq(x),y))表示“x的平方等于y”。以后我们约定用大写英文字母作为谓词符号,用小写字母f,g,h等表示函数符号,用小写字母x,y,z等作为个体变元符号,用小写字母a,b,c等作为个体常元符号。我们把“所有”、“一切”、“任一”、“全体”、“凡是”等词统称为全称量词,记为x;把“存在”、“有些”、“至少有一个”、“有的”等词统称为存在量词,记为x。其中M(x)表示“x是人”,N(x)表示“x有名字”,该式可读作“
4、对于任意的x,如果x是人,则x有名字”。这里的个体域取为全总个体域。如果把个体域取为人类集合,则该命题就可以表示为同理,我们可以把命题“存在不是偶数的整数”表示为其中G(x)表示“x是整数”,E(x)表示“x是偶数”。此式可读作“存在x,x是整数并且x不是偶数”。不同的个体变元,可能有不同的个体域。为了方便和统一起见,我们用谓词表示命题时,一般总取全总个体域,然后再采取使用限定谓词的办法来指出每个个体变元的个体域。具体来讲,有下面两条：(1)对全称量词,把限定谓词作为蕴含式之前件加入,即x(P(x)→…)。(2)对存在量词,
5、把限定量词作为一个合取项加入,即x(P(x)∧…)。这里的P(x)就是限定谓词。我们再举几个例子。例5.1不存在最大的整数,我们可以把它翻译为或例5.2对于所有的自然数,均有x+y>x例5.3某些人对某些食物过敏5.1.2谓词公式定义1(1)个体常元和个体变元都是项。(2)设f是n元函数符号,若t1,t2,…,tn是项,则f(t1,t2,…,tn)是项。(3)只有有限次使用(1),(2)得到的符号串才是项。定义2设P为n元谓词符号，t1,t2,…,tn为项，则P(t1,t2,…,tn)称为原子谓词公式，简称原子公式或者
6、原子。从原子谓词公式出发，通过命题联结词和量词，可以组成复合谓词公式。下面我们给出谓词公式的严格定义，即谓词公式的生成规则。定义3(1)原子公式是谓词公式。(2)若A,B是谓词公式，则A,A∧B,A∨B,A→B,AB,xA,xA也是谓词公式。(3)只有有限步应用(1)，(2)生成的公式才是谓词公式。由项的定义，当t1,t2,…,tn全为个体常元时，所得的原子谓词公式就是原子命题公式（命题符号）。所以，全体命题公式也都是谓词公式。谓词公式亦称为谓词逻辑中的合适（式）公式，记为Wff。紧接于量词之后被量词作用(即说明)的谓词公式称
7、为该量词的辖域。例如：(1)xP(x)。(2)x(H(x)→G(x,y))。(3)xA(x)∧B(x)。其中(1)中的P(x)为x的辖域,(2)中的H(x)→G(x,y)为x的辖域,(3)中的A(x)为x的辖域,但B(x)并非x的辖域。量词后的变元如x,y中的x,y称为量词的指导变元(或作用变元),而在一个量词的辖域中与该量词的指导变元相同的变元称为约束变元,其他变元(如果有的话)称为自由变元,例如(2)中的x为约束变元,而y为自由变元,(3)中A(x)中的x为约束变元,但B(x)中的x为自由变元。例如(3)
8、,一个变元在一个公式中既可约束出现,又可自由出现,但为了避免混淆,通常通过改名规则,使得一个公式中一个变元仅以一种形式出现。约束变元的改名规则如下：(1)对需改名的变元,应同时更改该变元在量词及其辖域中的所有出现。(2)新变元符号必须是量词辖域内原先没有的,最好是公式中也
