第二章命题逻辑的等值推演精选文档.ppt

第二章命题逻辑的等值推演本讲稿第一页，共二十七页2.1 等值式等值式一、复习一、复习 p q仅在仅在p与与q均为均为0时结果才为时结果才为0，其他为，其他为1。p q仅在仅在p与与q均为均为1时结果才有时结果才有1，其他为，其他为0。pq仅在仅在p为为1、q为为0才为才为0，其他为，其他为1。pq仅在仅在p与与q等值等值时才时才1，其他为，其他为1。用真值表证明了用真值表证明了 pq与与 p q的真值表完全一样，即这两者等的真值表完全一样，即这两者等值，根据双条件的定义，值，根据双条件的定义，(pq)(p q)为永为永真或重言式。真或重言式。pq(pq)(qp)(p q)(p q)本讲稿第二页，共二十七页二、等值式定义二、等值式定义 公式公式A、B，如果其真值表完全一样，或者，如果其真值表完全一样，或者AB为永真式，为永真式，则称则称A与与B等值，记为等值，记为AB 如：如：pq p q pq(pq)(qp)(p q)(p q)三、判断方法三、判断方法 判断真值表是否一样判断真值表是否一样 判断判断AB是否为永真。是否为永真。例如：例如：p与与p (p q)与与 pp，这是德摩律，这是德摩律 (p q)与与 pp 与与 互反互反 本讲稿第三页，共二十七页 pq p q pq(pq)(qp)(p q)(p q)pp (p q)pp 德摩律德摩律 (p q)pp 与与 对偶对偶 pp p p p p(q r)(p q)(p r)分配律分配律 p(q r)(p q)(p r)对偶式对偶式 p(p q)p 吸收律吸收律(多吃少多吃少)p(p q)p p p 1，p p 0 (pq)(pq)双条件相同为真双条件相同为真 (pq)(pq)p 归谬律归谬律本讲稿第四页，共二十七页如：如：pq p q pq(pq)(qp)(p q)(p q)pp (p q)pp 德摩律德摩律 (p q)pp 与与 对偶对偶 pp p p p p(q r)(p q)(p r)分配律分配律 p(q r)(p q)(p r)对偶式对偶式 p(p q)p 吸收律吸收律(多吃少多吃少)p(p q)p p p 1，p p 0 (pq)(qp)(pq)(pq)p 归谬律归谬律将以上公式中命题变元将以上公式中命题变元p/q，换成公式，换成公式A/B，一样成立！，一样成立！AB A B本讲稿第五页，共二十七页 pq p q 可推出可推出 AB A B 尽管尽管A/B可能很复杂，但是公式值也只有可能很复杂，但是公式值也只有0、1二二种种可能，公式可能，公式A/B的组合只有的组合只有0/0,0/1,1/0,1/1四种，四种，即只要证明：即只要证明：00 与与 0 0 相等相等 01 与与 0 1 相等相等 10 与与 1 0 相等相等 11 与与 1 1 相等相等 这与证明这与证明pq p q的过程完全一样，的过程完全一样，即即变元变元 p/q的值只有的值只有0、1,变元变元p/q的组合只有的组合只有0/0,0/1,1/0与与1/1四种组合，即证明各组合下各值四种组合，即证明各组合下各值相等。相等。本讲稿第六页，共二十七页 pq p q 可推出可推出 AB A B 这种将变元换成公式的方法，称为这种将变元换成公式的方法，称为“置换规则置换规则”，推而广知：，推而广知：已知已知A B，(A)是含公式是含公式A的命题公式，将的命题公式，将(A)中中A全部换成公式全部换成公式B，则，则(A)(B)如：如：pq p q，(pq)=(pq)p，这里这里A=pq，B=p q，(A)=(pq)=(pq)p，(B)=(p q)=(p q)p，故，故(pq)p (p q)p 部分等值置换部分等值置换后公式仍后公式仍等值等值！可用于等值演算！可用于等值演算本讲稿第七页，共二十七页 因为因为pq p q 故故 (pq)p (p q)p 部分等值置换部分等值置换后公式仍后公式仍等值等值！可用于等值演算！可用于等值演算(pq)r(p q)r (因因(pq)(p q)(p q)r (因因(p q)r(p q)r)(pq)r(德摩律德摩律)(pq)r (双重否定律双重否定律)(p r)(q r)(双重否定律双重否定律)本讲稿第八页，共二十七页证：证：(p q)r (pr)(qr)尽量转换尽量转换证：证：(pq)pq 先演算后判断公式类型先演算后判断公式类型 (p(p q)r应用题：应用题：甲：王不是苏州人，是上海人甲：王不是苏州人，是上海人 乙：王不是上海人，是苏州人乙：王不是上海人，是苏州人 丙：王不是上海人，也不是杭州人丙：王不是上海人，也不是杭州人 王说：一人全对，一人对一半，一人全不对！王说：一人全对，一人对一半，一人全不对！解：解：p:王是苏州人王是苏州人,q是上海人是上海人，r王是杭州人王是杭州人。甲甲:p q 乙：乙：p q 丙：丙：q r 王说的话译成公式为，据此判断王说的话译成公式为，据此判断p,q,r的值。的值。本讲稿第九页，共二十七页一、复习一、复习 p q仅在仅在p与与q均为均为0时结果才为时结果才为0，其他为，其他为1。p q仅在仅在p与与q均为均为1时结果才有时结果才有1，其他为，其他为0。pq仅在仅在p为为1、q为为0才为才为0，其他为，其他为1。pq仅在仅在p与与q等值等值时才时才1，其他为，其他为1。用真值表证明了用真值表证明了 pq与与 p q的真值表完全一样，即这两者等的真值表完全一样，即这两者等值，根据双条件的定义，值，根据双条件的定义，(pq)(p q)为永为永真或重言式。真或重言式。pq(pq)(qp)(p q)(p q)本讲稿第十页，共二十七页2.2 析取范式与合取范式析取范式与合取范式 文字文字：命题变项：命题变项(变元变元)及其否定称为文字及其否定称为文字.如如:p,q,r,p,q,r 简单析取式简单析取式:仅由有限个仅由有限个文字文字构成的析取式构成的析取式.如如:p q,p q,pq,p q,p q r 简单合取式简单合取式:仅由有限个仅由有限个文字文字构成的合取式构成的合取式.如如:p q,p q,pq,pq,p q r定理定理2.1：简单：简单析取析取式与简单式与简单合取式合取式 (1)一个简单析取式一个简单析取式Ai是重言式当且仅当同时含是重言式当且仅当同时含有某个命题变元及其否定式，如有某个命题变元及其否定式，如Ai=p p (2)一个简单合取式一个简单合取式Ai是矛盾式当且仅当同时含是矛盾式当且仅当同时含有某个命题变元及其否定式，如有某个命题变元及其否定式，如Ai=p p 本讲稿第十一页，共二十七页2.2 析取范式与合取范式析取范式与合取范式定义定义2.3：由有限个：由有限个简单合取简单合取式的式的析取析取构成的构成的命命题公式题公式称为称为析取范式析取范式。总体是总体是析取析取式式，每对括号内是，每对括号内是合取合取式式 A=(p q)(p r)定义定义2.3：由有限个：由有限个简单析取简单析取式的式的合取合取构成的构成的命命题公式题公式称为称为合取范式合取范式。总体是总体是合取合取式式，每对括号内是，每对括号内是析析取式取式 A=(p q)(p r)本讲稿第十二页，共二十七页2.2 析取范式与合取范式析取范式与合取范式 总体是总体是析取析取式式，每对括号内是，每对括号内是合取合取式式 A=(p q)(p r)析取范式析取范式 总体是总体是合取合取式式，每对括号内是，每对括号内是析析取式取式 A=(p q)(p r)合取范式合取范式定理定理2.2：析取范析取范式与式与合取范式合取范式 (1)一个一个析取范式析取范式A是矛盾式是矛盾式当且仅当当且仅当每个简单每个简单合取式是矛盾式。合取式是矛盾式。A=(p q)(p r)(2)一个一个合取范式合取范式A是重言式是重言式当且仅当当且仅当每个简单每个简单析取式是重言式。析取式是重言式。A=(p q)(p r)本讲稿第十三页，共二十七页2.2 析取范式与合取范式析取范式与合取范式 A=(p q)(p r)析取范式析取范式 A=(p q)(p r)合取范式合取范式建立范式的基本步骤建立范式的基本步骤：(1)转换条件式转换条件式 ABA B (2)转换双条式转换双条式AB(A B)(AB)(A B)(AB)(3)否定到底否定到底 A,(A B),(A B)(4)取消公因式取消公因式 A(B C),A(B C).本讲稿第十四页，共二十七页2.2 析取范式与合取范式析取范式与合取范式 (1)转换条件式转换条件式 ABA B (2)转换双条式转换双条式AB(A B)(AB)(A B)(AB)(3)否定到底否定到底 A,(A B),(A B)(4)取消公因式取消公因式 A(B C),A(B C).如如合取式范式合取式范式：(pq)r(p q)r(p q)r)(p q)r)(pq)r)(p q)r)(p r)(q r)(p qr)本讲稿第十五页，共二十七页2.2 析取范式与合取范式析取范式与合取范式 (1)转换条件式转换条件式 ABA B (2)转换双条式转换双条式AB(A B)(AB)(A B)(AB)(3)否定到底否定到底 A,(A B),(A B)(4)取消公因式取消公因式 A(B C),A(B C).如如析取式范式析取式范式：(pq)r(p q)r(p q)r)(p q)r)(p r)(q r)(pq r)本讲稿第十六页，共二十七页2.2 析取范式与合取范式析取范式与合取范式定义定义2.4：在含有：在含有n个变元的个变元的简单合取式简单合取式中中,每个每个命题变元或其否定命题变元或其否定仅出现仅出现一次一次,且各变元按其字且各变元按其字母顺序出现母顺序出现,则该简单合取式为则该简单合取式为(极极)小项小项。如：如：p q r,pq r,p qr,p q r (pq)r(p r)(q r)(pq r)非小非小项项定义定义2.4：在含有：在含有n个变元的个变元的简单析取式简单析取式中中,每个每个命题变元或其否定命题变元或其否定仅出现仅出现一次一次,且各变元按其字且各变元按其字母顺序出现母顺序出现,则该简单析取式为则该简单析取式为(极极)大项大项。如：如：p q r,pq r,p qr,p q r (pq)r(p r)(q r)(p qr)非大非大项项本讲稿第十七页，共二十七页2.2 析取范式与合取范式析取范式与合取范式小项的取值情况：小项的取值情况：对小项仅有一个对小项仅有一个成真的成真的赋值赋值如：如：p q r为为111,记为记为m111或或m7.pq r为为101,记为记为m101或或m5.p qr为为110,记为记为m110或或m6.p q r为为011,记为记为m011或或m3.大项的取值情况大项的取值情况：对小项仅有一个：对小项仅有一个成假成假的赋值。的赋值。如：如：p q r为为000,记为记为M000或或M0.pq r为为010,记为记为M010或或M2.p qr为为001,记为记为M001或或M1.p q r为为011,记为记为M011或或M3.本讲稿第十八页，共二十七页2.2 析取范式与合取范式析取范式与合取范式定义定义2.5：一个析取范式中，如果所有：一个析取范式中，如果所有简单合取式简单合取式均为均为(极极)小项，小项，则称则称为主析取范式为主析取范式。(pq)r(p r)(q r)(pq r)(p 1 r)(1 q r)(pq r)(p(qq)r)(pp)q r)(pq r)(p q r)(p q r)(p q r)(p q r)(pqr)m011 m001 m111 m011 m100.本讲稿第十九页，共二十七页2.2 析取范式与合取范式析取范式与合取范式定义定义2.5：一个析取范式中，如果所有：一个析取范式中，如果所有简单合取式简单合取式均为均为(极极)小项，小项，则称则称为主析取范式为主析取范式。(pq)r(p r)(q r)(pq r)(p 1 r)(1 q r)(pq r)(p(qq)r)(pp)q r)(pq r)(p q r)(p q r)(p q r)(p q r)(pqr)m011 m001 m111 m011 m100.m011 m001 m111 m100.本讲稿第二十页，共二十七页2.2 析取范式与合取范式析取范式与合取范式定义定义2.5：一个合取范式中，如果所有：一个合取范式中，如果所有简单析取式简单析取式均为均为(极极)大项，大项，则称为主合取范式。则称为主合取范式。(pq)r(p r)(q r)(p qr)(p 0 r)(0q r)(p qr)(p(qq)r)(pp)q r)(p qr)(p q r)(p q r)(pq r)(pq r)(p qr)M000 M010 M110 M101.成假赋值来编号成假赋值来编号m011 m001 m111 m100.编号互补编号互补本讲稿第二十一页，共二十七页2.2 析取范式与合取范式析取范式与合取范式主范式的获取方法主范式的获取方法：先转换析取式或合取式，再：先转换析取式或合取式，再 对于对于主析取主析取(小项的析取小项的析取)式，如果其中的简单式，如果其中的简单合取式没有出现某个变元，则合取式没有出现某个变元，则合取合取1.如：如：(pq)r(p r)(q r)(pq r)(p 1 r)(1 q r)(pq r)对于对于主合取范式主合取范式(大项的合取大项的合取)，如果所有，如果所有简单简单析取式析取式没有出现某个变元，则没有出现某个变元，则析取析取0。如：。如：(pq)r(p r)(q r)(p qr)(p 0 r)(0q r)(p qr)本讲稿第二十二页，共二十七页2.2 析取范式与合取范式析取范式与合取范式主范式的获取方法主范式的获取方法：1、先转换、先转换析取式析取式或或合取式合取式，再，再合取合取1或或析取析取0。2、先建立、先建立真值表真值表，取出所有取出所有成真赋值成真赋值对应的小项，析取所有小项对应的小项，析取所有小项得主析取范式。得主析取范式。取出所取出所有成假赋值有成假赋值对应的大项，合取所有大项对应的大项，合取所有大项得主合取范式。得主合取范式。如：如：(pq)r 本讲稿第二十三页，共二十七页2.2 析取范式与合取范式析取范式与合取范式主范式的获取方法主范式的获取方法：1、先转换、先转换析取式析取式或或合取式合取式，再，再合取合取1或或析取析取0。2、先建立、先建立真值表真值表，成真赋值成真赋值之小项析取，之小项析取，成假赋值成假赋值的大项的大项合取。合取。如：如：(pq)r主范式的应用主范式的应用：(1)若若A去则去则B去去(2)若若B去则去则C不能去不能去 (3)若若C不去则不去则A或或B可去。可去。解：解：(pq)(qr)(r(p q)用方法用方法1或方法或方法2建立主析取范式，再进一步处理。建立主析取范式，再进一步处理。本讲稿第二十四页，共二十七页2.3 联结词的完备集联结词的完备集 第一章介绍了生成公式的第一章介绍了生成公式的4条规则，对于条规则，对于n个变个变元的所有可能公式中，只要使用我们所学的元的所有可能公式中，只要使用我们所学的5个个联结词联结词()及园括号及园括号()，足以表示所有这，足以表示所有这些公式，这称为联结词的完备性。些公式，这称为联结词的完备性。其实只要其实只要与园括号与园括号()足够了，足够了，本讲稿第二十五页，共二十七页2.4 可满足性问题与消解法可满足性问题与消解法 公式的可满足性是指，是否存在一种赋值情况，公式的可满足性是指，是否存在一种赋值情况，使得该公式的值为真。使得该公式的值为真。可以先得到一个公式的主析取或主合取范式，可以先得到一个公式的主析取或主合取范式，然后判断公式的类型。然后判断公式的类型。当一个公式比较复杂时，该问题的求解比较麻当一个公式比较复杂时，该问题的求解比较麻烦，因此烦，因此Ribson找到了一种好方法。找到了一种好方法。本讲稿第二十六页，共二十七页2.3 联结词的完备集联结词的完备集 第一章介绍了生成公式的第一章介绍了生成公式的4条规则，对于条规则，对于n个变元的所有可能公式中，只要使用我们所学的个变元的所有可能公式中，只要使用我们所学的5个个联结词联结词()及园括号及园括号()，足以表示所有这些公式，这称为联结，足以表示所有这些公式，这称为联结 对于主析取对于主析取(小项的析取小项的析取)式，如果其中的简单合取式没有出现某个变元，则加合取式，如果其中的简单合取式没有出现某个变元，则加合取1.如：如：(pq)r(p r)(q r)(pq r)(p 1 r)(1 q r)(pq r)对于主合取范式对于主合取范式(大项的合取大项的合取)，如果所有，如果所有简单析取式简单析取式没有出现某个变元，则析取没有出现某个变元，则析取0。如：。如：(pq)r(p r)(q r)(p qr)(p 0 r)(0q r)(p qr)(p(qq)r)(pp)q r)(p qr)(p q r)(p q r)(pq r)(pq r)(p qr)本讲稿第二十七页，共二十七页