2013第四章_谓词逻辑.ppt

* * * * * * * * 第13次课 11月11日 * 上次课程回顾 合一算法 谓词逻辑的归结 * Herbrand定理 Herbrand定理是归结原理的理论基础。 Jacques Herbrand ： (1908.2.12—1931.7.27) 法国数学家, 生于法国巴黎, 死于一次登山事故. Herbrand定理的提出者。 Herbrand定理是归结原理的理论基础，归结原理的正确性是通过Herbrand定理证明的。 * 预备知识 谓词逻辑合式公式的真值： 1）原子公式的值要么为T, 要么为F. 2）若A,B为合式公式, 那么?A, A?B, A?B, A?B, A?B的值由真值表决定. 3) 如果在解释I下,A对X的所有赋值都是 T，那么?XA的值是T，否则为F。 4）如果在解释中存在一个赋值使A的值是T， 那么?XA的值是T，否则为F。 简单的说: 对谓词公式中的各种变量指定特定的常量去代替, 就构成了谓词的解释. * 举例 例： 给定解释I如下: 论域 D={2,3}; 函数f(x)为f(2)=3,f(3)=2； 谓词p(x)为p(2)=0，p(3)=1； q(x,y)为q(i,j)=1, i, j=2,3 r(x,y)为r(2,2)=r(3,3)=1, r(2,3)=r(3,2)=0 求（1）在解释I下，?x(p(f(x))?q(x,f(x)))的 真值。 （2）在解释I下，?x?y r(x,y)的真值。 (3) 在解释I下， ?x?y r(x,y)的真值。 * 模型 对于公式F，公式集S和解释I： （1）若在I下，F为真，则I是F的一个模型。 （2）若在I下，S中各公式均为真，则I是S的 一个模型。 （3）如果S有模型，则称S是可满足的。 （4）如果S无模型，则称S是不可满足的。 （5）如果S的任一模型都是F的模型,则称F是 S的逻辑推论,记为 S|= F. 公式F永真：对于F的所有解释，F都为真。 公式F永假：对于F的所有解释，F都为假。 S={ F1, F2, F3 } * Herbrand定理思想 为了证明一个谓词公式A永真, 需要证明其反命题?A永假. 所谓“永假”就是不存在模型,即在所有可能的解释中, ?A均取假值. 由于量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限的, 不可数的，要找到所有的解释是不可能的。 Herbrand定理的基本思想是简化讨论域，建立一个比较简单的，特殊的论域（Herbrand域），使得只要在此论域上，原谓词公式是不可满足的，即保证不可满足的性质不变。 * Herbrand域和D域的关系如图： D 域 H 域 * Herbrand域 定义1：设S是一个子句集，U0是S中子句所含的全体常量集。若S中子句皆不含常量，则任择一常量a, 并令 U0 ={a}, 对i?1, 令 Ui = Ui-1?{fn(t1,?,tn)| n?1,fn是S中出现的所有函数符号的集合函数; t1,?,tn?Ui-1} Us= ?i?0 Ui 则称Ui为S的i阶常量集, Us称为S的Herbrand论域. Us的元素称为基项. * 举例 例1：令S={p(X),q(Y)?r(Z)}，求：H-域 解 在题目中设有常量a U0={a} U1=U0={a} ?? Us=U0?U1?U3?={ a } 例2: 令S={p(a),q(X)??r(f(X))}，求：H-域 解 在题目中有一个常量a，U0={a}， U1=U0?{f(a)}={a, f(a)} U2=={a, f(a)， f(f(a))}， ?? Us=U0?U1?U3?= {a, f(a)， f(f(a)), ? } * 举例（续） 例3: 令S={p(a),q(b)?r(f(X))} 求：H-域 解 U0={a,b}， U1={a,b,f(a),f(b)} U2={a,b,f(a),f(b),f(f(a)),f(f(b))} ?? Us={a,b,f(a),f(b),f(f(a)),f(f(b)),?} * 练习 1，设子句集 S={p(X),q(Y,f(Z,b)),r(a)},求H-域. * Herbrand基 为研究子句集S的不可满足性，讨论H域上S中各谓词的真值。 Herbrand基是公式S中出现的谓词取H域的元素值组成的