《02-离散谓词逻辑-1.4-1.5》由会员分享，可在线阅读，更多相关《02-离散谓词逻辑-1.4-1.5（39页珍藏版）》请在金锄头文库上搜索。
1、第二章 谓词逻辑第四节 公式解释与类型第四节 公式解释与类型一、公式解释v一般情况下，谓词公式中包含：个体常元、个体变元、函数变元、谓词变元个体常元、个体变元、函数变元、谓词变元等。v对各种变元用指定的特殊常元去代替就构成了一个公式的解释公式的解释。v在给定的解释下，可以对多个公式进行解释公式解释v定义：一个解释I由下面4部分组成非空个体域DIDI中特定元素特定元素：a, b, DI上的特定的函数特定的函数：f, g, DI上的特定的谓词特定的谓词：P, Q, 公式解释v在一个具体的解释中，个体常元、函数、谓词的数量一般是有限的，并且其解释一旦确定下来就不再改变，只是个体变元的值在个体域DI内
2、变化，量词符 和 仅作用于DI中的元素公式解释例2.5 有给定的解释I：DI 3, 6DI中特定的元素：a=3DI中特定函数：f(x) : f(3)=6, f(6)=3DI中特定谓词：P(x) : P(3)=F, P(6)=TQ(x,y) : Q(i, j)=T (i, j=3,6)R(x, y) : R(3,3)=R(6,6) =TR(3,6)=R(6,3) =F 公式解释求下列公式的真值：(x) ( P(x)Q(x, a) )解：在解释I下：公式 (P(3) Q(3, 3) (P(6) Q(6, 3) ( F T ) ( T T ) FDI = 3, 6a = 3f(x) : f(3)=6
3、, f(6)=3P(x) : P(3)=F, P(6)=TQ(x,y) : Q(i, j)=T (i, j=3,6)R(x, y) : R(3,3)=R(6,6) =TR(3,6)=R(6,3) =F 公式解释(x)( P(f(x) Q(x, f(x) )解：在解释I下： 公式 (P(f(3)Q(3,f(3) (P(f(6)Q(6, f(6) (P(6)Q(3, 6) (P(3)Q(6, 3) (TT) (FT) TDI = 3, 6a = 3f(x) : f(3)=6, f(6)=3P(x) : P(3)=F, P(6)=TQ(x,y) : Q(i, j)=T (i, j=3,6)R(x,
4、y) : R(3,3)=R(6,6) =TR(3,6)=R(6,3) =F 公式解释(x)(y) R (x, y)解：在解释I下： 公式 (x)(R (x, 3) R (x, 6) (R (3, 3) R (3, 6) (R (6, 3) R (6, 6) (T F) (F T) TDI = 3, 6a = 3f(x) : f(3)=6, f(6)=3P(x) : P(3)=F, P(6)=TQ(x,y) : Q(i, j)=T (i, j=3,6)R(x, y) : R(3,3)=R(6,6) =TR(3,6)=R(6,3) =F 公式解释例2.6 有给定的解释I：DI 整数集合DI中特定的
5、元素：a=0DI中特定函数：f(x,y) : x+y, g(x, y)=xyDI中特定谓词：E(x, y) : x=y, B(x,y) : x y求下列公式哪个为真，哪个为假？ 公式解释(x) E ( g(x, a), x )解：在解释I下：公式 (x) E ( g (x, 0), x ) (x) (x0 = x ) (x) ( 0 = x ) Fa=0f(x,y) : x+y, g(x, y)=xyE(x, y) : x=y, B(x,y) : x y公式解释(x) (y) (E ( f (x, a), y ) E( f (y, a), x )解：在解释I下：公式 (x) (y)( (x+0
6、=y) (y+0=x) ) (x) (y)( (x=y) (y=x) ) Ta=0f(x,y) : x+y, g(x, y)=xyE(x, y) : x=y, B(x,y) : x y公式解释(x) (y) (z) E ( f (x, y), z )解：在解释I下：公式 (x) (y) (z) (x+y=z) TE ( f (x, y), g (x,y) )解：公式 (x+y=xy )真值不确定，不是命题a=0f(x,y) : x+y, g(x, y)=xyE(x, y) : x=y, B(x,y) : x y公式解释(x) (y) B ( x, y )解：在解释I下：公式 (x) (y) (
7、 x y ) T(x) (y) B ( x, y )解：在解释I下：公式 (x) (y) ( x y ) Fa=0f(x,y) : x+y, g(x, y)=xyE(x, y) : x=y, B(x,y) : x y公式类型二、公式类型v定义：若一个公式在任何解释下都是真的称该公式为逻辑有效式，也叫作永真式永真式或重言式重言式若一个公式在任何解释下都是假的称该公式为矛盾式矛盾式，也叫作永假式永假式若一个公式至少存在一个解释使其为真称该公式为可满足式可满足式公式类型v前面介绍的代入规则代入规则，不仅局限于自由变元，对公式中的命题变元命题变元和谓词变元谓词变元均可实施代入。原则是不能改变原公式的约
8、束关系不能改变原公式的约束关系公式类型vv谓词变元和命题变元的代入规则谓词变元和命题变元的代入规则：在一个公式A中，一个n元谓词P (x1, x2, , xn)可以用至少含有n个自由变元的公式B (y1, y2, , yn , yn+1, , yn+r) (r 0)代入，其中y1, y2, , yn是分别对应于x1, x2, , xn的任意选定的n个自由变元，且对P的所有出现处处代入B中的其他r个自由变元不允许在原公式A中约束出现P中的个体变元也不允许在B中约束出现公式类型例2.7 对于公式A: (y)(P(x) Q(y)中的谓词变元P(x)用B: (x) (R(x) S(y, z) 代入P(
9、x)中的个体变元x在B中约束出现，因此需要将B中的约束变元x改名为u： (u) (R(u) S(y, z)B中的自由变元y在公式A中为约束出现，因此要将A中的约束变元y改名为v： (v)(P(x) Q(v)将P(x)用 (u) (R(u) S(y, z) 代入，得到：(v)(u) (R(u) S(y, z) Q(v)公式类型v若原公式为重言式，则实施代入后仍为重言式v若原公式为非永真式，则实施代入后可能发生改变例：公式 (x)(P(x) P(x)为永真式，将P(x)用Q(y)代入后得到(x)(Q(y) Q(y)仍为永真式公式 (x)(P(x) Q(y)为非永真式，将P(x)用Q(y)代入后得到
10、(x)(Q(y) Q(y)为永真式公式类型例2.8 判断下列公式是否为重言式 (x)P(x) (x) P(x)解：设I为任意解释，个体域为DI，若存在a DI ，使P(a)为假，则公式的前件(x)P(x)为假，则公式为真否则，对于x DI ，都有P(a)为真，即公式的前件(x)P(x)为真，且后件(x) P(x)为真，则公式为真。因此该公式是重言式公式类型 (x)P(x) ( (x)P(x) (y) Q(y) )解：因为P PQ 是重言式，因此将(x)P(x)代入P，将(y) Q(y)代入Q，得到公式(x)P(x) ( (x)P(x) (y) Q(y) )因此该公式是重言式公式类型 (x) (
11、y) P(x, y) (x)(y)P(x, y)解：设解释I为：个体域DI是自然数集合P(x, y) : x=y，则公式的前件为真，后件为假，因此该公式不是重言式(x) (y)意译成：“无论选定什么样的x的值，都可以确定一个y的值，能使”例：个体域是鞋(x) (y)（x和y能配成双）：对于客体域中的每一只鞋x，存在一只鞋y，x和y能够配成双。(y)(x) ？第五节 等价式与蕴涵式第五节 等价式与蕴涵式一、等价式v定义：设A和B是任意两个公式，若A B是永真式，则称A与B是等价的，记做A B，称A B为等价式Ls中列出的基本等价式都是Lp中的等价式设(A)是含有A出现的公式， (B)是用公式B替
12、换了若干A的结果，若A B，则(A) (B)等价式vLp的基本等价式 ( ( x) A x) A A A( ( x) A x) A A A其中A是不含自由变元x的谓词公式量词否定等价式 ( ( x)A (x) x)A (x) ( ( x) x) A (x) A (x) ( ( x)A (x) x)A (x) ( ( x) x) A (x) A (x)等价式例2.9： ( ( x) (x) ( y) (y) ( z)P(x, y, z)z)P(x, y, z) (x) (y) (z)P(x, y, z) (x) (y) (z)P(x, y, z) ( ( x) (x) ( y) (y) ( z)
13、 z) P(x, y, z) P(x, y, z)等价式量词辖域的扩大与缩小（B是不含自由变元x的谓词）(x)(A (x) B) (x)A (x) B 证明：当B为假时，两边都为假；当B为真时，两边都等价于(x)A (x)。同理可证：(x)(A (x) B) (x)A (x) B(x)(A (x) B) (x)A (x) B(x)(A (x) B) (x)A (x) B等价式量词辖域的扩大与缩小（B是不含自由变元x的谓词）(x)(A (x) B) (x)A (x) B 证明： (x)(A (x) B) (x)( A (x) B) (x) A (x) B (x)A (x) B (x)A (x)
14、B等价式量词辖域的扩大与缩小（B是不含自由变元x的谓词）同理可证：(x)(A (x) B) (x)A (x) B(x)(B A (x) B (x)A (x)(x)(B A (x) B (x)A (x)等价式量词辖域的扩大与缩小（小结） ( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B ( ( x)(A (x) x)(A
