02-离散谓词逻辑-1.4-1.5

1、第二章 谓词逻辑,2020年8月5日星期三,第四节 公式解释与类型,第四节 公式解释与类型 一、公式解释 一般情况下，谓词公式中包含：个体常元、个体变元、函数变元、谓词变元等。 对各种变元用指定的特殊常元去代替就构成了一个公式的解释。 在给定的解释下，可以对多个公式进行解释,2020年8月5日星期三,公式解释,定义：一个解释I由下面4部分组成 非空个体域DI DI中特定元素：a, b, DI上的特定的函数：f, g, DI上的特定的谓词：P, Q, ,2020年8月5日星期三,公式解释,在一个具体的解释中，个体常元、函数、谓词的数量一般是有限的，并且其解释一旦确定下来就不再改变，只是个体变元的

2、值在个体域DI内变化，量词符 和 仅作用于DI中的元素,2020年8月5日星期三,公式解释,例2.5 有给定的解释I： DI 3, 6 DI中特定的元素：a=3 DI中特定函数：f(x) : f(3)=6, f(6)=3 DI中特定谓词：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) =T R(3,6)=R(6,3) =F,2020年8月5日星期三,公式解释,求下列公式的真值： (x) ( P(x)Q(x, a) ) 解：在解释I下：公式 (P(3) Q(3, 3) (P(6) Q(6, 3)

3、( F T ) ( T T ) F,DI = 3, 6 a = 3 f(x) : f(3)=6, f(6)=3 P(x) : P(3)=F, P(6)=T Q(x,y) : Q(i, j)=T (i, j=3,6) R(x, y) : R(3,3)=R(6,6) =T R(3,6)=R(6,3) =F,2020年8月5日星期三,公式解释,(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) T,DI = 3, 6 a = 3 f(x) :

4、f(3)=6, f(6)=3 P(x) : P(3)=F, P(6)=T Q(x,y) : Q(i, j)=T (i, j=3,6) R(x, y) : R(3,3)=R(6,6) =T R(3,6)=R(6,3) =F,2020年8月5日星期三,公式解释,(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) T,DI = 3, 6 a = 3 f(x) : f(3)=6, f(6)=3 P(x) : P(3)=F, P(6)=T Q(x,y) :

5、Q(i, j)=T (i, j=3,6) R(x, y) : R(3,3)=R(6,6) =T R(3,6)=R(6,3) =F,2020年8月5日星期三,公式解释,例2.6 有给定的解释I： DI 整数集合 DI中特定的元素：a=0 DI中特定函数：f(x,y) : x+y, g(x, y)=xy DI中特定谓词：E(x, y) : x=y, B(x,y) : x y 求下列公式哪个为真，哪个为假？,2020年8月5日星期三,公式解释,(x) E ( g(x, a), x ) 解：在解释I下：公式 (x) E ( g (x, 0), x ) (x) (x0 = x ) (x) ( 0 = x

6、 ) F,a=0 f(x,y) : x+y, g(x, y)=xy E(x, y) : x=y, B(x,y) : x y,2020年8月5日星期三,公式解释,(x) (y) (E ( f (x, a), y ) E( f (y, a), x ) 解：在解释I下：公式 (x) (y)( (x+0=y) (y+0=x) ) (x) (y)( (x=y) (y=x) ) T,a=0 f(x,y) : x+y, g(x, y)=xy E(x, y) : x=y, B(x,y) : x y,2020年8月5日星期三,公式解释,(x) (y) (z) E ( f (x, y), z ) 解：在解释I下：

7、公式 (x) (y) (z) (x+y=z) T E ( f (x, y), g (x,y) ) 解：公式 (x+y=xy ) 真值不确定，不是命题,a=0 f(x,y) : x+y, g(x, y)=xy E(x, y) : x=y, B(x,y) : x y,2020年8月5日星期三,公式解释,(x) (y) B ( x, y ) 解：在解释I下：公式 (x) (y) ( x y ) T (x) (y) B ( x, y ) 解：在解释I下：公式 (x) (y) ( x y ) F,a=0 f(x,y) : x+y, g(x, y)=xy E(x, y) : x=y, B(x,y) : x

8、 y,2020年8月5日星期三,公式类型,二、公式类型 定义： 若一个公式在任何解释下都是真的称该公式为逻辑有效式，也叫作永真式或重言式 若一个公式在任何解释下都是假的称该公式为矛盾式，也叫作永假式 若一个公式至少存在一个解释使其为真称该公式为可满足式,2020年8月5日星期三,公式类型,前面介绍的代入规则，不仅局限于自由变元，对公式中的命题变元和谓词变元均可实施代入。原则是不能改变原公式的约束关系,2020年8月5日星期三,公式类型,谓词变元和命题变元的代入规则： 在一个公式A中，一个n元谓词P (x1, x2, , xn)可以用至少含有n个自由变元的公式B (y1, y2, , yn ,

9、yn+1, , yn+r) (r 0)代入，其中y1, y2, , yn是分别对应于x1, x2, , xn的任意选定的n个自由变元，且对P的所有出现处处代入 B中的其他r个自由变元不允许在原公式A中约束出现 P中的个体变元也不允许在B中约束出现,2020年8月5日星期三,公式类型,例2.7 对于公式A: (y)(P(x) Q(y)中的谓词变元P(x)用B: (x) (R(x) S(y, z) 代入 P(x)中的个体变元x在B中约束出现，因此需要将B中的约束变元x改名为u： (u) (R(u) S(y, z) B中的自由变元y在公式A中为约束出现，因此要将A中的约束变元y改名为v： (v)(P

10、(x) Q(v) 将P(x)用 (u) (R(u) S(y, z) 代入，得到： (v)(u) (R(u) S(y, z) Q(v),2020年8月5日星期三,公式类型,若原公式为重言式，则实施代入后仍为重言式 若原公式为非永真式，则实施代入后可能发生改变 例： 公式 (x)(P(x) P(x)为永真式，将P(x)用Q(y)代入后得到(x)(Q(y) Q(y)仍为永真式 公式 (x)(P(x) Q(y)为非永真式，将P(x)用Q(y)代入后得到(x)(Q(y) Q(y)为永真式,2020年8月5日星期三,公式类型,例2.8 判断下列公式是否为重言式 (x)P(x) (x) P(x) 解：设I为

11、任意解释，个体域为DI，若存在a DI ，使P(a)为假，则公式的前件(x)P(x)为假，则公式为真 否则，对于x DI ，都有P(a)为真，即公式的前件(x)P(x)为真，且后件(x) P(x)为真，则公式为真。 因此该公式是重言式,2020年8月5日星期三,公式类型,(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) ) 因此该公式是重言式,2020年8月5日星期三,公式类型,(x) (y) P(x, y) (x)(y)P(x, y) 解：

12、设解释I为： 个体域DI是自然数集合 P(x, y) : x=y， 则公式的前件为真，后件为假，因此该公式不是重言式,(x) (y)意译成：“无论选定 什么样的x的值，都可以确定一 个y的值，能使” 例：个体域是鞋 (x) (y)（x和y能配成双）： 对于客体域中的每一只鞋x，存 在一只鞋y，x和y能够配成双。 (y)(x) ？,2020年8月5日星期三,第五节 等价式与蕴涵式,第五节 等价式与蕴涵式 一、等价式 定义：设A和B是任意两个公式，若A B是永真式，则称A与B是等价的，记做A B，称A B为等价式 Ls中列出的基本等价式都是Lp中的等价式 设(A)是含有A出现的公式， (B)是用公

13、式B替换了若干A的结果，若A B，则(A) (B),2020年8月5日星期三,等价式,Lp的基本等价式 (x) A A(x) A A其中A是不含自由变元x的谓词公式 量词否定等价式 (x)A (x) (x) A (x) (x)A (x) (x) A (x),2020年8月5日星期三,等价式,例2.9： (x) (y) (z)P(x, y, z) (x) (y) (z)P(x, y, z) (x) (y) (z)P(x, y, z) (x) (y) (z) P(x, y, z),2020年8月5日星期三,等价式,量词辖域的扩大与缩小（B是不含自由变元x的谓词）(x)(A (x) B) (x)A

14、(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,2020年8月5日星期三,等价式,量词辖域的扩大与缩小（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) B,2020年8月5日星期三,等价式,量词辖域的扩大与缩小（B是不含自由变元x的谓词）同理可证： (x)(

15、A (x) B) (x)A (x) B(x)(B A (x) B (x)A (x)(x)(B A (x) B (x)A (x),2020年8月5日星期三,等价式,量词辖域的扩大与缩小（小结） (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) B) (x)A (x) B (x)(A (x) B) (x)A (x) B (x)(A (x) B) (x)A (x) B (x)(B A (x) B (x)A (x)(x)(B A (x) B (x)A (x),2020年8月5日星期三,等价式,例

16、2.11 求证 (x)(y)(A(x)B(y)(x)A(x)(y)B (y) 证明：左式 (x) (A(x) (y) B(y) (x) A(x) (y) B(y),(x)(B A (x) B (x)A (x),(x)(A (x) B) (x)A (x) B,2020年8月5日星期三,等价式,量词的分配等价式(x)(A (x)B (x) (x)A (x)(x)B (x)(x)(A (x)B (x) (x)A (x)(x)B (x) 证明：由(x)(A(x)B(x)(x)A(x)(x)B(x) 可知：(x)(A(x)B(x)(x)A(x)(x)B(x) 左边(x)(A(x)B(x) (x)(A (

17、x)B (x) 右边(x)A(x)(x)B(x) (x)A(x)(x)B(x),全称量词(x)对于析取不服从分配率,设： A (x)：x是偶整数 B (x)：x是奇整数 考察两公式是否等价 (x)(A (x) B (x) (x)A (x) (x)B (x),对于每一个x，有A(x)为真并且B（x）同时为真； 对于每一个x，有A(x)为真，并且对于每一个x ，B（x）为真,2020年8月5日星期三,等价式,例2.10 求证：(x)(A(x)B(x)(x)A(x)(x)B(x) 证明：左式 (x)( A(x) B(x) (x) A(x) (x) B(x) (x)A(x) (x) B(x) (x)A

18、(x) (x)B(x),思考：是否 (x)(A(x)B(x) (x)A(x)(x)B(x) ？,O,2020年8月5日星期三,等价式,多重量词等价式(x) (y) A (x, y) (y) (x) A (x, y) (x) (y) A (x, y) (y) (x) A (x, y),2020年8月5日星期三,蕴涵式,二、蕴涵式 Ls 中列出的基本蕴涵式都是Lp中的蕴涵式 使用代入规则得到的蕴涵式也是Lp中的蕴涵式 例如：P (P Q) Q 则用(x)A (x)代入P，用B(x, y)代入Q，得到： (x)A(x)(x)A(x) B(x, y) B(x, y),2020年8月5日星期三,蕴涵式,

19、Lp的基本蕴涵式 (x)A (x) A (y)(x)A (x) A (x) A (y) (x)A (x)A (x) (x)A (x) (x)A (x) (x)A (x) (x) (y) A (x, y) (x) A (x, x)(x)A (x, x) (x) (y) A (x, y),2020年8月5日星期三,蕴涵式,(x)(A (x) B (x) (x)A (x) (x)B (x) 证明：设论域为自然数，A (x) ：x是奇数， B (x) ：x是偶数，则左边为假而右边为真，因此左右两边不等价。 若存在一个x使A (x) B (x)为真，则必定存在一个x使A (x) 为真且使B (x)为真，即当左边为真时，右边必定为真，因此蕴涵式成立,2020年8月5日星期三,