离散数学第二章(第2讲)课件

1、4 谓词演算的等价式与蕴含式1、谓词公式的等价定义A，B为二个谓词公式，E为它们共同个体域，若对A和B的任一组变元进行赋值，使得A和B的值相同，则称A和B在个体域E上是互为等价的，记为AB EB或 A定义给定谓词公式A，E是A的个体域。若给A中客体变元指派E中的每一个客体所得命题的值均为真，则称A在E中是永真的。若E为任意域则称A是永真的。2、谓词公式的分类定义给定谓词公式A，E是A的个体域。若给A中客体变元指派E中的每一个客体所得命题的值均为假，则称A在E中是永假的。若E为任意域则称A是永假的。定义给定谓词公式A，E是A的个体域。若给A中客体变元指派E中每一个客体，在E中存在一些客体，使得指

2、派后的真值为真，则A称是可满足的。3.不含量词的谓词公式的等价公式和永真蕴含式 只要用原子谓词公式去代替命题逻辑中等价公式和永真蕴含式中的原子命题变元，则可获得谓词演算中的等价公式和永真蕴含式。 命题逻辑 谓词逻辑 (x)(x)(x) (x)(x) (x) (x) . . . . (x)(x)(x) (x) (x) (x) . . . . 命题逻辑 谓词逻辑 x(x)(x) x P(x) Q(x)() (x) x(x) (x) x(x) x(x) x(x) (x) x(x) x(x) x(x) 4. 含有量词的一般谓词公式的等价公式和永真蕴含式5.含有量词的特殊的谓词公式的等价式和永真蕴含式(

3、1) 消去量词定律设个体域为：S= a1, a2 , , an ，则： xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an) (2) 量词转换律 xP(x) xP(x) xP(x) xP(x) 证明：xP(x) xP(x) 设个体域为： S= a1 , a2 , , an xP(x) ( P(a1) P(a2) P(an) ) P(a1) P(a2) P(an) xP(x)量化命题与非量化命题的的否定形式例： 否定下列命题： (a) 上海是一个小城镇 A(s) (b) 每一个自然数都是偶数 x( N(x)E(x) )上述二命题的否定为： (a) 上海不

4、是一个小城镇 A(s) (b) 有一些自然数不是偶数 x ( N(x) E(x) )其否定为：x( N(x)E(x) ) x( N(x)E(x) ) x( N(x)E(x) ) x ( N(x) E(x) )每一个自然数都是偶数 x( N(x)E(x) )结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定，其方法是： x的否定变为x ， x的否定变为x 。量词转换律的推广应用: xyP(x,y,z) xyP(x,y,z) 解释：xyP(x,y,z) x yP(x,y,z) xyP(x,y,z) (3) 量词辖域的扩张及其收缩律 xA(x) P

5、 x( A(x) P ) xA(x) P x( A(x) P ) xA(x) P x( A(x) P ) xA(x) P x( A(x) P )注：P为不含有变元x的任何谓词公式。证明： xA(x) P x(A(x) P)设个体域为： S = a1 , a2 , , an xA(x) P ( A(a1) A(a2) A(an) ) P ( A(a1) P ) ( A(a2)P ) ( A(an) P ) x( A(x) P ) 下面的等价公式也是成立的：xA(x)B x(A(x)B) xA(x)B x(A(x)B)AxB(x) x(AB (x)A x B(x) x(AB (x)注：A,B为不含

6、有变元x的任何谓词公式证明：xA(x)B x(A(x)B) xA(x)B xA(x) B x A(x) B x ( A(x) B ) x( A(x)B )(4) 量词分配律x( A(x) B(x) ) xA(x) xB(x)x ( A(x) B(x) ) xA(x) xB(x) x ( A(x) B(x) ) xA(x) xB(x) x ( A(x) B(x) ) xA(x) xB(x)xA(x) xB(x) x( A(x) B(x) ) xA(x) xB(x) x( A(x) B(x) )证明: x( A(x) B(x) ) xA(x) xB(x)设个体域为： S = a1 , a2 , ,

7、 an x( A(x)B(x) ) ( A(a1) B(a1) ) . ( A(an) B(an) ) ( A(a1) A(an) ) ( B(a1) B(an) ) xA(x) x B(x)(5) 量词的转换xP(x) xP(x)(6) 含有多个量词的谓词公式的等价式 在含有多个量词的谓词公式中, 相同量词间的次序是可以任意调动的，不会影响命题的真值。 xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y)不同量词间的次序则不能随意调动。所以若谓词公式中出现多个不同量词，则按照从左到右的次序读出，不能颠倒次序。 例： yx(xy-2)表示: 任何y均存在x，使得xy-2。 例

8、：设A(x,y)表示x和y同姓，个体域x是甲组的人，个体域y是乙组的人。则：xyA(x,y)表示对于甲组所有的人，乙组都有人和他同姓。yx A(x,y)表示存在一个乙组的人，甲组所有的人和他同姓。 注：量词出现的次序直接关系到命题的含义。例：设个体域是整数集，则下列命题的真值为真的是:A y x(xy=1) B x y (xy0)C x y (xy=y2)( C )5 前束范式定义一个公式，如果量词均非否定地位于全式的开头，它们的作用域延伸到整个公式的末尾，则称此公式为前束范式。例： xyz( Q(x,y) R(z) (前束范式) x(x)(x) (不是前束范式) x(x)(x) (不是前束范式) 定理 任何一个谓词公式都存在和它等价的前束范式。如何将谓词公式转换为前束范式转换方法： 利用量词转换把深入到原子谓词公式前 利用量词辖域的扩张收缩定律,把量词移到全式的最前面，这样一定可得到等价的前束范式。利用约束变元的改名