《离散数学课件第二章(第2讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第二章(第2讲).ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式1、谓词公式的等价谓词公式的等价定义定义A A，B B为二个谓词公式，为二个谓词公式，E E为它们共同个体域，若对为它们共同个体域，若对A A和和B B的任一组变元进行赋值，使得的任一组变元进行赋值，使得A A和和B B的值相同，则称的值相同，则称A A和和B B在个体域在个体域E E上是互为等价的，记为上是互为等价的，记为A AB B EB或 A定义定义给定谓词公式给定谓词公式A A，E E是是A A的个体域。若给的个体域。若给A A中中客体变元指派客体变元指派E E中的每一个客体所得命题的值均为真，中的每一个客体所得命题的值均为真，则称则
2、称A A在在E E中是永真的。若中是永真的。若E E为任意域则称为任意域则称A A是永真的。是永真的。2 2、谓词公式的分类、谓词公式的分类定义定义给定谓词公式给定谓词公式A，E是是A的个体域。若给的个体域。若给A中客中客体变元指派体变元指派E中的每一个客体所得命题的值均为假，中的每一个客体所得命题的值均为假，则称则称A在在E中是永假的。若中是永假的。若E为任意域则称为任意域则称A是永假的。是永假的。定义定义给定谓词公式给定谓词公式A，E是是A的个体域。若给的个体域。若给A中客中客体变元指派体变元指派E中每一个客体，在中每一个客体，在E中存在一些客体，使中存在一些客体，使得指派后的真值为真，则
3、得指派后的真值为真，则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
4、)(x)x(x)x(x)x(x)4.含有量词的一般谓词公式的等价公式和永真蕴含式含有量词的一般谓词公式的等价公式和永真蕴含式5.含有量词的特殊的谓词公式的等价式和永真蕴含式含有量词的特殊的谓词公式的等价式和永真蕴含式(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)
5、xP(x)量化命题与非量化命题的的否定形式量化命题与非量化命题的的否定形式例：例：否定下列命题：否定下列命题：(a)上海是一个小城镇上海是一个小城镇 A(s)(b)每一个自然数都是偶数每一个自然数都是偶数 x(N(x)E(x)上述二命题的否定为：上述二命题的否定为：(a)上海不是一个小城镇上海不是一个小城镇 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)结论：对于非量化命题的否定只需将动词否定，而对于量化
6、命结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定，其方题的否定不但对动词进行否定而且对量词同时进行否定，其方法是：法是：x的否定变为的否定变为 x，x的否定变为的否定变为 x。量词转换律的推广应用量词转换律的推广应用:x yP(x,y,z)x yP(x,y,z)解释：解释：x yP(x,y,z)x yP(x,y,z)x yP(x,y,z)(3)量词辖域的扩张及其收缩律量词辖域的扩张及其收缩律 xA(x)P 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为不含有变元为不含
7、有变元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)A xB(x)x(AB(x)A x B(x)x(AB(x)注：注：A,B为不含有变元为不含有变元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)(
8、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,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)含有多个量词的含有多个量词的谓词公式的等价式谓词公式
9、的等价式 在含有多个量词的谓词公式中在含有多个量词的谓词公式中,相同量词间的次序相同量词间的次序是可以任意调动的，是可以任意调动的，不会影响命题的真值。不会影响命题的真值。x yP(x,y)y xP(x,y)x yP(x,y)y xP(x,y)不同量词间的次序则不能随意调动。所以不同量词间的次序则不能随意调动。所以若谓词公式中若谓词公式中出现多个不同量词，则按照出现多个不同量词，则按照从左到右从左到右的次序读出，不能的次序读出，不能颠倒次序。颠倒次序。例：例：y x(xy-2)表示表示:任何任何y均存在均存在x，使得，使得xy-2。例：设例：设A(x,y)表示表示x和和y同姓，个体域同姓，个体
10、域x是甲组的人，个体域是甲组的人，个体域y是乙组的人。则：是乙组的人。则：x yA(x,y)表示对于甲组所有的人，乙组都有人和他同姓。表示对于甲组所有的人，乙组都有人和他同姓。y x A(x,y)表示存在一个乙组的人，甲组所有的人和他同姓。表示存在一个乙组的人，甲组所有的人和他同姓。注：量词出现的次序直接关系到命题的含义。注：量词出现的次序直接关系到命题的含义。例：设个体域是例：设个体域是整数集整数集，则下列命题的真值为真的是，则下列命题的真值为真的是:A y x(xy=1)B x y(xy0)C x y(xy=y2)(C )5 前束范式前束范式定义定义一个公式，如果量词一个公式，如果量词均非
11、否定均非否定地位于全式的地位于全式的开头，它们的作用域延伸到整个公式的末尾，则称开头，它们的作用域延伸到整个公式的末尾，则称此公式为前束范式。此公式为前束范式。例：例：x y z(Q(x,y)R(z)(前束范式前束范式)x(x)(x)(不是前束范式不是前束范式)x(x)(x)(不是前束范式不是前束范式)定理定理 任何一个谓词公式都存在和它等价的前束范式。任何一个谓词公式都存在和它等价的前束范式。如何将谓词公式转换为前束范式如何将谓词公式转换为前束范式转换方法：转换方法：利用量词转换把利用量词转换把深入到原子谓词公式前深入到原子谓词公式前 利用量词辖域的扩张收缩定律利用量词辖域的扩张收缩定律,把量词移到全式的最把量词移到全式的最前面，这样一定可得到等价的前束范式。前面，这样一定可得到等价的前束范式。利用约束变元的改名规则例：将例：将 xP(x)R(x)转换为前束范式转换为前束范式 xP(x)R(x)yP(y)R(x)y(P(y)R(x)例：把例：把 xP(x)xQ(x)变成前束范式。变成前束范式。xP(x)xQ(x)xP(x)xQ(x)xP(x)xQ(x)x(P(x)Q(x)