《离散数学课件》谓词逻辑2

1、1,上节课内容,谓词公式的符号化 谓词演算的合式公式 自由出现和约束出现 约束变元的换名规则 自由变元的代入规则,2,第3讲 永真性和可满足性,谓词公式的赋值 可满足性 代换实例 等价式,3/66,3.4.1 真假性,四个因素 (1) 个体域 (2) 自由变元 (3) 谓词变元 (4) 命题变元,xA(x) A(y) P,4/66,(1) 个体域,例 设A(e)表示e为偶数，考察 xA(x),当个体域I为1,2,3时，公式的值为假； 当个体域I为2,4,6时，公式的值为真。,5/66,(2) 自由变元,例 设A(e)表示e为偶数，考察 A(y),当y取1时，其值为F； 当y取2时，其值为T。,

2、6/66,(3) 谓词变元,例 个体域I=2，4. 考察 xA(x),当A(e)表示e为偶数时，xA(x)=T； 当A(e)表示e为奇数时，xA(x)=F；,7/66,(4) 命题变元,例 个体域I=2，4，A(e)表示e为偶数. 考察 xA(x)P,当P=T 时，公式的值为真； 当P=F 时，公式的值为假。,8/66,谓词演算公式,设为任何一个谓词演算公式， 其中自由变元为x1，x2，xn； 谓词变元为X1，X2，Xm； 命题变元为P1，P2，Pk。 此时可表示为： (x1，xn；X1，Xm；P1，Pk),9/66,谓词演算公式的解释, 设个体域I解释为常个体域I0； 自由变元x1，xn解释

3、为： I0中的个体a1，an； 谓词变元X1，Xm解释为： I0上的谓词A1，Am； 命题变元P1，Pk解释为： P10，Pk0， 其中Pi0=T或F(i=1，2，k)。,10/66,成真解释、成假解释,给定公式一个解释： (I0；a1，an；A1，Am；P10，Pk0) 公式在该解释下的值记为： (a，A，P0)= (a1,an；A1,Am；P10,Pk0) 若(a，A，P0)=T，则称(I0；a；A；P0)为成真解释； 若(a，A，P0)=F，则称(I0；a；A；P0)为成假解释。,11/66,含有量词的谓词演算公式,设个体域I中所有实体变元为a1，a2，an，则有： x(x)=(a1)(

4、a2)(an) x(x)=(a1)(a2)(an),12/66,含有量词的谓词演算公式的真假性,x(x)为真 个体域I中的每一个个体均使得取为真 x(x)为真 个体域I中有一个个体使得取为真,13,例 求(x)（P(x)Q(x)）的真值， 其中(x)：x等于1；(x)：x等于2； 且个体域1,2。,解：(x)(P(x)Q(x) (P(1)Q(1)(P(2)Q(2) ()() ,代换实例(续),例2 给定解释I 如下: (a) 个体域 D=N (b) (c) (d) 谓词 说明下列公式在 I 下的涵义,并讨论真值 (1) xF(g(x,a),x),x(2x=x) 假命题,(2) xy(F(f(x

5、,a),y)F(f(y,a),x),xy(x+2=yy+2=x) 假命题,例1(续),(3) xyzF(f(x,y),z),15,两点说明: 5个小题都是闭式,在I下全是命题 (3)与(5)说明，量词顺序不能随意改变,(5) xyzF(f(y,z),x),xyz (y+z=x) 假命题,(4) xF(f(x,x),g(x,x),x(2x=x2) 真命题,xyz (x+y=z) 真命题,个体域 D=N； ； ；,16/66,例3(p41)已知 xy(X(x，y)Y(z)Z(x，y) 试求公式在解释 (I；z；X(e1，e2)，Y(e)，Z(e1，e2) =(1，2，3；1；e1e2；e为偶数；e

6、1e2) 之下的值。,解：将解释代入公式得： 原式 = xy(xy 1为偶数)xy) = xy(T) =T,17/66,例3(p41)已知 xy(X(x，y)Y(z)Z(x，y) 试求公式在解释 (I；z；X(e1，e2)，Y(e)，Z(e1，e2) =(1，2，3；2；e1e2；e为偶数；e1e2) 之下的值。,解：将解释代入公式得： 原式 = xy(xy 2为偶数)xy) = xy(xyxy),18/66,解(续) 原式 = xy(xyxy),当x=1时, 考察y的作用域(1y1y) 当y=1时，(11)(11)=TT=T 当y=2时，(12)(12)=FT=T 当y=3时，(13)(13

7、)=FT=T 当x=2时，考察y的作用域(2y2y) 当y=1时，(21)(21)=TF=F 当y=2时，(22)(22)=TT=T 当y=3时，(23)(23)=FT=T,19/66,解(续2) 原式 = xy(xyxy),当x=3时, 考察y的作用域(3y3y) 当y=1、2时，(3y)(3y)=TF=F 当y=3时，(33)(33)=TT=T,所以，得到： 原式 =(TTT) (F*) (F *) =TF* =F,20/66,永真、永假,定义2：给定一个谓词演算公式，其个体域为I，对于I中的任意一个解释, (1)若均取为真， 则称公式在I上为永真的； (2)若均取为假， 则称公式在I上为

8、永假的， 也称为公式在I上不可满足的。,21/66,例 讨论公式类型 xF(x) xF(x),证明 设E为任意一个解释，其个体域为I， 1、若对于任意的xI,F(x)均为真, 则xF(x)与xF(x)都为真， 从而该公式也为真。 2、若存在x0I, 使得F(x0)为假， 则xF(x)为假，从而该公式为真。 故在解释E下该公式为真。 由于E的任意性，所以该公式是永真式。,22/66,可满足、非永真,定义3：给定一个谓词演算公式，其个体域为I, (1)如果在个体域I上存在一个成真解释, 则称公式在I上为可满足公式； (2)如果在个体域I上存在一个成假解释， 则称公式在I上为非永真公式。,23/66

9、,考察 xF(x) xF(x)=T?,可满足式,24/66,定理1 (p42),如果I，J是个具有相同个数的个体域(个体本身可不相同)，则任意一个公式， 若在I中永真当且仅当其在J中永真； 若在I中可满足当且仅当其在J中可满足。,注：有限域上一个公式的永真性和可满足性依赖于个体域中个体的数目，与个体的内容无关。,25/66,K 域,定义：把个体域1，2，3，k称为K域， 即由k个个体组成的个体域。 当k=1时，就称为1域，依此类推。,定理2：如果一公式在k域上永真， 则其在h(hk)域上永真。,定理3：如果一公式在h域上可满足， 则其在k(kh)域上可满足。,26/66,定理(补充) 如下公式

10、在k域上永真： x(A(x)B(x)(xA(x)xB(x),证明：在k域 I=1，2， ，k上，,原式= (A(1)B(1)(A(2)B(2) (A(k)B(k) ) (A(1)A(2)A(k) (B(1)B(2)B(k) = T 所以原式在k域上永真。,代换实例（补充）,定义 设A0是含命题变项p1, p2, ,pn的命题公式， A1,A2,An是n个谓词公式，用Ai处处代替A0中的pi (1in) ，所得公式A称为A0的代换实例. 例如: F(x)G(x), xF(x)yG(y) 等都是pq的换实例， x(F(x)G(x) 等不是 pq 的代换实例.,27,定理 重言式的代换实例都是永真式

11、，矛盾式的代 换实例都是矛盾式.,28/66,例 判断下列公式的类型:,(1) xF(x)(xyG(x，y)xF(x) (2) (xF(x)yG(y)yG(y),p(qp) (pq)q,重言式 矛盾式,29/66,3.4.2 同真假性、等价式,定义1：设有两公式和, 如果对于个体域 I 上任何解释，公式 和均取得相同的真假值， 则称和在 I 上同真假。 如果和在每一个非空个体域上均同真假，则称和同真假。,在任何解释I和I中的任意赋值下的两个谓词公式和，若对和中的变项作同样的赋值，所得命题的真值都相同，则称谓词公式和在I上是等价的，记作：（A=B）。,30/66,（1）关于否定的等价公式,x(x

12、)= x(x) x(x)= x(x),例如，设P(x)表示“x今天来校上课”，则P(x)表示“x今天没来校上课”。那麽， 对第一个式子,“不是所有的人今天都来上课(x)P(x) ”与“有(存在)一些人今天没来上课(x)P(x)”在意义上是相同的。 对第二个式子,“今天没有(不存在)来上课的人(x)P(x) ”与“所有的人今天都没来上课(x)P(x)”在意义上是相同的。,31/66,设个体域I中所有实体变元为a1，a2，an，则有： x(x)=(a1)(a2)(an) =(a1)(a2)(an) =x(x) x(x)=(a1)(a2)(an) =(a1)(a2)(an) =x(x),32/66,

13、（2）量词作用域的收缩与扩张,设公式中不含有自由的x，则: x(x) )= x(x) x(x) )= x(x) x(x) )= x(x) x(x) )= x(x) ,析取式/合取式的量词作用域中的闭式可分离出来,33/66,量词作用域的收缩与扩张(续),设公式中不含有自由的x，则下面的公式成立: x(x) )= ( x(x) ) x( (x) = (x(x) x(x) )= (x(x) ) x(x)= (x(x),蕴含式的量词作用域中的闭式前件可分离出来,34/66,例1 试判断下面两公式是否等价 x(x) 和 x (x),解： x(x) =x( (x) = x (x) = x (x) 所以两

14、公式等价。,35/66,例2 (p42) 试判断下面两公式是否等价 x(x) 和 x(x),解： x(x) = (x(x) = (x(x) = x(x) ) = x(x) ) x(x) 所以两公式不等价。,36/66,（3）量词分配等值式,x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x),注意：对无分配律，对无分配律,例如，“联欢会上所有的人既唱歌又跳舞”和“联欢会上所有的人唱歌且所有的人跳舞”的意义相同。 例如，“联欢会上有人唱歌或跳舞”和“联欢会上有人唱歌，或有人跳舞”的意义相同。,37,证：(x)(P(x)Q(x) (x)(P(x)Q(x) (x)P(x

15、)(x)Q(x) (x)P(x)(x)Q(x) (x)P(x)(x)Q(x),例1 证明(x)（P(x)Q(x)） (x)P(x)(x)Q(x),38,证： 左式(x)(y)(P(x)Q(y) (x)(y)( P(x)Q(y) (x)(P(x)(y)Q(y) (x) P(x)(y)Q(y) (x)P(x)(y)Q(y) (x)P(x)(y)Q(y),例2 证明：(x)(y)(P(x)Q(y) (x)P(x)(y)Q(y),等价式与基本等价式,基本等值式: 命题逻辑中16组基本等值式的代换实例 如，xF(x)yG(y) xF(x)yG(y) (xF(x)yG(y) xF(x)yG(y) 等 消去

16、量词等值式 设D=a1,a2,an xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an),39,定义 若AB为逻辑有效式（永真），则称A 与B是等值（等价）的， 记作 AB，并称AB为等值式（等价式）.,量词辖域收缩与扩张等值式 设A(x)是含x自由出现的公式，B中不含x的出现 关于全称量词的： x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x),40,关于存在量词的: x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x),量词分配等值

17、式 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) 注意：对无分配律，对无分配律,41,小结,谓词公式的赋值 可满足性 代换实例 等价式,第4讲 范式（4.3）,前束范式 SKOLEM标准形,42,43/66,3.4.3 范式,定义：如果一谓词演算公式中的一切量词均在公式的最前面(量词前不含否定词)且其作用域一直延伸到公式的末端，则称公式为前束形公式。 前束形公式的一般形式为： Q1x1Q2x2QnxnM(x1，x2，xn) 其中，Qi为或，M称为公式的母式且其中不含有量词。,44/66,例如，xy(F(x)(G(y)H(x,y) x(F(x)G(x) 是前

18、束范式, 而 x(F(x)y(G(y)H(x,y) x(F(x)G(x) 不是前束范式,45/66,定理,任意一个谓词演算公式均有一前束范式与之等价。,求前束范式的一般步骤:,（1）消去除 、之外的联结词； （2）将否定符 移到量词符后； （3）换名使各变元不同名； （4）扩大辖域使所有量词处在最前面。,注：公式的前束范式不惟一,例1 求下列公式的前束范式 (1) x(M(x)F(x) 解 x(M(x)F(x) x(M(x)F(x) （量词否定等值式） x(M(x)F(x) 两步结果都是前束范式，说明前束范式不惟一.,46,例(续),(2) xF(x)xG(x) 解 xF(x)xG(x) xF

19、(x)xG(x) （量词否定等值式） x(F(x)G(x) （量词分配等值式） 另有一种形式 xF(x)xG(x) xF(x)xG(x) xF(x)yG(y) ( 代替规则 ) xy(F(x)G(y) ( 量词辖域扩张 ) 两种形式是等值的,47,例(续),(3) xF(x)xG(x) 解 xF(x)xG(x) xF(x)xG(x) x(F(x)G(x) （为什么？） 或 xy(F(x)G(y) （为什么？） xF(x)xG(x) xF(x)yG(y),48,49,(4) xF(x)y(G(x,y)H(y) 解 xF(x)y(G(x,y)H(y) zF(z)y(G(x,y)H(y) （换名规则

20、） zy(F(z)(G(x,y)H(y) （为什么？） 或 xF(x)y(G(z,y)H(y) （代替规则） xy(F(x)(G(z,y)H(y),50,(x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u) 解：原式 (x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u) (x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u) (x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u) (x)(y)(z)(u)(P(x,z)P(y,z) Q(x,y,u), (x)(y)(z)(u)(P(x,z)P(y,z)Q(x,y,u),例2 将谓词公式化为前束

21、范式：,51,(x)(y)A(x,y) (x)(y)(B(x,y)(y)(A(y,x)B(x,y) 解：原式 (x)(y)A(x,y) (x)(y)(B(x,y)(y)(A(y,x)B(x,y) ) (x)(y)A(x,y) (u)(r)(B(u,r)(z)(A(z,u)B(u,z) ) (x)(y)(u)(r)(z) (A(x,y)(B(u,r)(A(z,u)B(u,z) ),例3 将谓词公式化为前束范式：,例(续),练习 x(F(x,y)y(G(x,y)H(x,z) 解 用换名规则, 也可用代替规则, 这里用代替规则 x(F(x,y)y(G(x,y)H(x,z) x(F(x,u)y(G(x

22、,y)H(x,z) xy(F(x,u)G(x,y)H(x,z) 注意：x与y不能颠倒,52,如果给定解释I：个体域为实数集，F(x,y)：xy。 则 xyF（x，y）为真， 而y xF（x，y） 意为“存在着最小实数”，是假命题.,53/66,二、SKOLEM标准形,定义：仅含有全称量词的前束范式称为SKOLEM标准形。,定理：任一谓词演算公式，均可以化成相应的SKOLEM标准形, 且为不可满足的当且仅当其SKOLEM标准形是不可满足的。,54/66,SKOLEM标准形的求解算法,(1)先求谓词演算公式的前束范式； (2)按如下方法消去存在量词 若存在量词x前无全称量词，则引入SKOLEM常量a，代替公式中受x约束的变元，消去存在量词； 若存在量词x前有n个全称量词，则引入n元SKOLEM函数f，代替公式中受x约束的变元，消去存在量词； (3)从左至右重复上述过程，直至公式中不含有存在量词。,55/66,例4 (p46)求公式的SKOLEM标准形,x(X(x)(yY(x，y)xZ(x),解：先把公式化为前束范式 原式=x(X(x)(yY(x，y)xZ(x) =x(X(x)(yY(x，y)xZ(x) =x(X(x)(yY(x，y)uZ(u) =xyu(X(x)(Y(