命题逻辑等值演算 讲稿.ppt

命题逻辑等值演算 第一页，讲稿共四十二页哦基本要求：1.深刻理解等值式的概念。深刻理解等值式的概念。2.牢牢记记24个个基基本本等等值值式式，这这是是等等值值演演算算的的基基础础；能能熟熟练练地地应应用用它它们们进进行行等等值演算。值演算。3.了解简单析取式、简单合取式、析取范式、合取范式的概念。了解简单析取式、简单合取式、析取范式、合取范式的概念。4.深深刻刻理理解解极极小小项项及及极极大大项项的的定定义义及及它它们们的的名名称称，及及名名称称下下角角标标与与成成真真赋赋值值的的关系。关系。5.熟练掌求公式的主析取范式的方法。熟练掌求公式的主析取范式的方法。6.熟练掌握由公式的主析取范式求公式的主合取范式的方法。熟练掌握由公式的主析取范式求公式的主合取范式的方法。7.会用公式的主析取范式（主合取范式）求公式的成真赋值、成假赋值。会用公式的主析取范式（主合取范式）求公式的成真赋值、成假赋值。8.会将公式等值地化为任何联结词完备集中的公式。会将公式等值地化为任何联结词完备集中的公式。第二页，讲稿共四十二页哦某公司派小李或小张去上海出差，若派小李去，则小赵要加某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？派遣的？解：解：复合命题（公式）复合命题（公式）例题例题(p(pq q)(p(pr r)(q(qs s)r rA=A=第三页，讲稿共四十二页哦(p(pqq)(p(pr r)(q(qs s)r rA=A=p qrsp q pr qs r(pq)(pr)(qs)r0 000011100 001011100 010011000 011011000 100110100 101111110 110110000 111111001 000101101 001101101 010111001 011111001 100100101 101101101 110110001 11111100麻烦！麻烦！计算量大！计算量大！方法很多：方法很多：真值表法真值表法 等值演算法等值演算法第四页，讲稿共四十二页哦2.1 等值式1.例子 看下面三个公式的真值表 P Q PQ PQ QP 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 从真值表可以看出，不论对P、Q作何指 派，都使得PQ、PQ和QP的真值相同，表明它们之间彼此等价等价。第五页，讲稿共四十二页哦2.定义：A、B是含有命题变元P1,P2,Pn的命题公式，如不论对P1,P2,Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价，记作AB。显然 PQPQQP3.重要的等价公式 双重否定律 AA 幂等律 AAA AAA 交换律 ABBA ABBA 结合律 A(BC)(AB)C A(BC)(AB)C 第六页，讲稿共四十二页哦(6)德摩根律德摩根律(AB)A B(AB)A B(7)吸收律吸收律A(AB)AA(AB)A(8)零律零律A11A00(9)同一律同一律A0AA1A(10)排中律排中律A A1(11)矛盾律矛盾律A A0分配律分配律A(BC)(AB)(AC)A(BC)(AB)(AC)(对对的分配律的分配律)互补律互补律(对对的分配律的分配律)第七页，讲稿共四十二页哦(13)等价等值式等价等值式AB(AB)(BA)AB(AB)(A B)AB(AB)(A B)(14)假言易位假言易位ABBA(15)等价否定等值式等价否定等值式ABA B(16)归谬论归谬论(AB)(AB)A(12)蕴含等值式蕴含等值式ABAB第八页，讲稿共四十二页哦4.等价公式的证明方法方法1：用列真值表。（不再举例）方法2：用公式的等价变换.(用置换定律)置换定律:A是一个命题公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，则AB。应用置换定律以及前面列出的等价公式可以对给定公式进行等价变换。等值演算等值演算：由已知等值式推演出新的等值式的过程。：由已知等值式推演出新的等值式的过程。第九页，讲稿共四十二页哦例题1.用等值演算法证明下面等值式：(1)(pq)(pq)(pq)(2)q(pr)(pq)r证明：证明：(1)从左边开始演算 (pq)(pq)(pq)(pq)(双重否定律)(pq)(pq)(德摩根律)(pq)(pq)(德摩根律)(pp)(pq)(qp)(qq)(分配律)(pq)(qp)(同一律)(p q)(q p)(蕴含等值式)(pq)(等价等值式)11第十页，讲稿共四十二页哦例题1.用等值演算法证明下面等值式：(2)q(pr)(pq)r证明：证明：(2)从右边开始演算 (pq)r(pq)r (蕴含等值式)pqr (德摩根律)q(pr)(交换律)q(pr)(蕴含等值式)q(pr)(蕴含等值式)第十一页，讲稿共四十二页哦例题2.用等值演算法判断下列公式的类型：(1)(pq)(pq)(2)p(pqr)(3)(pq)q)r解：解：(1)(pq)(pq)(pq)(pq)(蕴含等值式)(pq)(pq)(德摩根定律)(pq)(pq)(双重否定律)p(qq)(分配律)p1 (排中律)p (同一律)因为因为p是可满足式，故式是可满足式，故式(1)为可满足式为可满足式第十二页，讲稿共四十二页哦例题2.用等值演算法判断下列公式的类型：(2)p(pqr)解：解：(2)p(pqr)p(pqr)(蕴含等值式)(pp)(qr)(分配律)1(qr)(排中律)1 (零律)因为因为1是重言式，故式是重言式，故式(2)为重言式为重言式第十三页，讲稿共四十二页哦例题2.用等值演算法判断下列公式的类型：(3)(pq)q)r解：解：(3)(pq)q)r (pq)q)r (蕴含等值式)p(q q)r (德摩根律、结合律)p0r (矛盾律)0 (零律)因为因为p是矛盾式，故式是矛盾式，故式(3)为矛盾式为矛盾式第十四页，讲稿共四十二页哦某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？派小张去，小王也得去。小赵没加班。问公司是如何派遣的？(p(pq q)(p(pr r)(q(qs s)r rA=A=例题例题.用等值演算法解决实际问题用等值演算法解决实际问题p p：派小李去上海出差：派小李去上海出差q q：派小张去上海出差：派小张去上海出差r r：小赵要加班：小赵要加班s s：小王也去上海出差：小王也去上海出差 (pq)(pr)(qs)r (德摩根律)(pq)(pr)r (qs)(交换律)(pq)(pr)(qs)(分配律、矛盾律)(ppr)(qpr)(qs)(分配律)(qpr)(qs)(矛盾律)(qprs)(分配律、矛盾律)结论：派遣方案为：派小张和小王去上海出差，只有结论：派遣方案为：派小张和小王去上海出差，只有这一种方案这一种方案第十五页，讲稿共四十二页哦2.2.范式 范式就是命题公式形式的规范形式。这里约定在范式中 只含有联结词只含有联结词、和和。一.析取范式与合取范式1.合取式与析取式合取式与析取式 合取式合取式：是用“”联结命题变元或变元的否定构成的式子。如 P、P、PQ、PQR 析取式析取式：是用“”联结命题变元或变元的否定构成的式子。如 P、P、PQ、PQR注注:PPPPPPP是合是合(析析)取式取式.第十六页，讲稿共四十二页哦2.析取范式析取范式 公式A如果写成如下形式：A1A2.An (n1)其中每个Ai(i=1,2.n)是合取式，称之为A的析取范式析取范式。3.合取范式合取范式 公式A如果写成如下形式：A1A2.An (n1)其中每个Ai(i=1,2.n)是析取式，称之为A的合取范式合取范式。例如，PQ 的析取范式与合取范式：PQ(PQ)(PQ)-析取范式 PQ(PQ)(PQ)-合取范式第十七页，讲稿共四十二页哦4.析取范式与合取范式的写法析取范式与合取范式的写法先用相应的公式去掉先用相应的公式去掉和和。蕴含等值式蕴含等值式PQPQ等价等值式等价等值式PQ(PQ)(P Q)PQ(PQ)(QP)PQ(PQ)(P Q)用公式的否定公式或德摩根律将用公式的否定公式或德摩根律将 后移到命题变元之前。后移到命题变元之前。A(P1,P2,Pn)A*(P1,P2,Pn)(PQ)P Q(PQ)P Q用分配律、幂等律等公式进行整理，使之成为所要求的形用分配律、幂等律等公式进行整理，使之成为所要求的形式。式。(对偶式对偶式)第十八页，讲稿共四十二页哦例如求(PQ)R的析取范式与合取范式(PQ)R (PQ)(PQ)R(PQ)(PQ)R -析取范式(PQ)R(PQ)(PQ)R(PQ)(PQ)R(PQR)(PQR)-合取范式第十九页，讲稿共四十二页哦二.主析取范式与主合取范式 一个公式的析取范式与合取范式的形式是不唯一的。下面定义形式唯一的主析取范式与主合取范式。主析取范式主析取范式 1.极小项极小项 定义：在一个有n个命题变元的合取式中，每个变元必出现且仅出现一次，称这个合取式是个极小极小项项。例如，有两个变元的极极小项：PQ、PQ、PQ、PQ第二十页，讲稿共四十二页哦 极小项的性质极小项的性质m3m2m1m0PQPQP Q PQ P Q00FFFFFT01FTFFTF10TFFTFF11TTTFFFa).有有n个变元，则有个变元，则有2n个极小项。个极小项。b).每一组指派有且只有一个极小项为每一组指派有且只有一个极小项为T。为了记忆方便，可将各组指派对应的为为了记忆方便，可将各组指派对应的为T的极小项的极小项分别记作分别记作m0,m1,m2,m2n-1上例中上例中m0 P Qm1 PQm2P Qm3PQ第二十一页，讲稿共四十二页哦2.主析取范式定义 析取范式 A1A2.An,其中每个Ai(i=1,2.n)都是极极小项，称之为主析取范式主析取范式。3.主析取范式的写法 方法：列真值表 列出给定公式的真值表。找出真值表中每个“T”对应的极极小项。(如何根据一组指派写对应的为“T”的项：如果变元P被指派为T，P在极极小项中以P形式出现；如变元P被指派为F,P在极极小项中以P形式出现(因要保证该极极小项为T)。用“”联结上述极极小项，即可。第二十二页，讲稿共四十二页哦例如求 PQ和PQ的主析取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ m0m1m3 (PQ)(PQ)(PQ)PQm0m3 (PQ)(PQ)思考题:永真式的主析取范式是什么样？第二十三页，讲稿共四十二页哦方法方法：用公式的等价变换：用公式的等价变换先写出给定公式的析取范式先写出给定公式的析取范式A1A2.An。为使每个为使每个Ai都变成极小项，对缺少变元的都变成极小项，对缺少变元的Ai补全变补全变元，元，比如缺变元比如缺变元R，就用，就用联结永真式联结永真式(R R)形式形式补补R。用分配律等公式加以整理用分配律等公式加以整理。PQPQ(P(Q Q)(P P)Q)(PQ)(P Q)(PQ)(PQ)(PQ)(P Q)(PQ)第二十四页，讲稿共四十二页哦主主合取范式合取范式1.极大项极大项定义定义:在有n个命题变元的析取式中，每个变元必出现且仅出现一次,称之为极大项极大项。例如，有两个变元的极极大项及其真值表：M0 M1 M2 M3 P Q PQ PQ PQ PQ F F F T T T F T T F T T T F T T F T T T T T T F第二十五页，讲稿共四十二页哦极大项的性质极大项的性质 a).有n个变元，则有2n个极极大项。b).每一组指派有且只有一个极极大项为F。为了记忆方便，可将各组指派对应的为F的极极大项分别记作M0,M1,M2,M2n-1。上例中 M0 PQ M1 PQ M2 PQ M3 PQ 第二十六页，讲稿共四十二页哦极大项与极小项之间的关系极大项与极小项之间的关系 定理定理2.3：第二十七页，讲稿共四十二页哦2.主合取范式定义主合取范式定义 合取范式 A1A2.An,其中每个Ai(i=1,2.n)都是极大项，称之为主合取范式主合取范式。3.主合取范式的写法主合取范式的写法 方法：列真值表 列出给定公式的真值表。找出真值表中每个“F”对应的极极大项。如何根据一组指派写对应的为“F”的极极大项：如果变元P被指派为F，P在极极大项中以P形式出现；如变元P被指派为T，P在极极大项中以 P形式出现(确保该极极大项为F)。用“”联结上述大项，即可。第二十八页，讲稿共四十二页哦例如求 PQ和PQ的主合取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ M2 PQ PQ M1M2 (PQ)(PQ)第二十九页，讲稿共四十二页哦方法：用公式的等价变换先写出给定公式的合取范式 A1A2.An。为使每个Ai变成极极大项，对缺少变元的析取式Ai补全变元，比如缺变元R，就用联结永假式(RR)形式补R。用分配律等公式加以整理。第三十页，讲稿共四十二页哦例如，求(PQ)R的主合取范式(PQ)R(PQ)R(PQ)R(PR)(QR)(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)第三十一页，讲稿共四十二页哦三三.主主范式的应用范式的应用1.应用主析取范式解决实际问题应用主析取范式解决实际问题某公司派小李或小张去上海出差，若派小李去，则小赵要某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？何派遣的？A(pq)(pr)(qs)r (pq)(pr)(qs)r (p p)(p s)(q p)(qs)(q r)(r r)00(p s)(q p)(qs)(q r)(ps q r)00(ps q r)m9第三十二页，讲稿共四十二页哦应用应用2 用主析取范式或主合取范式判断两个命题公式是否等值用主析取范式或主合取范式判断两个命题公式是否等值(1)设设A=(pq)(pqr)，B=(p(qr)(q(pr)解：求解：求A与与B的主析取范式的主析取范式 A=(pq)(pqr)(pq r)(pqr)(pqr)(pqr)(pqr)(pqr)m6m7m3m3m6m7B=(p(qr)(q(pr)(pq)(ppr)(qrq)(qrpr)(pqr)(pqr)(pqr)(pqr)(pqr)m3m6m7m7m6m3m3m6m7由于由于A与与B有相同的主析取范式，所以有相同的主析取范式，所以A B第三十三页，讲稿共四十二页哦解：求解：求A与与B的主合取范式的主合取范式 A=(pq)(pqr)(pp)(pq)(p r)(qp)(q p)(q r)(pq)(p r)(qp)(q p)(qr)(pq)(p r)(pq)(qr)(pqr)(pqr)(pqr)(pqr)(pq r)(pq r)(pqr)(pqr)应用应用2 用主析取范式或主合取范式判断两个命题公式是否等用主析取范式或主合取范式判断两个命题公式是否等值值(1)设设A=(pq)(pqr)，B=(p(qr)(q(pr)M1M0M2M5M4M0M1M2M4M5M0M1M2M4M5第三十四页，讲稿共四十二页哦B=(p(qr)(q(pr)(pq)(pr)(qp)(qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)解：求解：求A与与B的主合取范式的主合取范式 A=(pq)(pqr)应用应用2 用主析取范式或主合取范式判断两个命题公式是否等值用主析取范式或主合取范式判断两个命题公式是否等值(1)设设A=(pq)(pqr)，B=(p(qr)(q(pr)M1M0M2M5M4M0M1M2M4M5M0M1M2M4M5由于由于A与与B有相同的主合取范式，所以有相同的主合取范式，所以A B第三十五页，讲稿共四十二页哦说明：A=(pq)(pqr)m3m6m7M0M1M2M4M5没出现在主析取范式中的极小项为没出现在主析取范式中的极小项为m0,m1,m2,m4,m5.没出现在主合取范式中的极大项为没出现在主合取范式中的极大项为M3,M6,M7.所以由公式的主析取范式可以得到主合取范式所以由公式的主析取范式可以得到主合取范式也可由公式的主合取范式确定主析取范式也可由公式的主合取范式确定主析取范式在演算中，若求主合取范式方便，则可先求主合取范式，然后再写出在演算中，若求主合取范式方便，则可先求主合取范式，然后再写出主析取范式，这样比直接求主析取范式方便；主析取范式，这样比直接求主析取范式方便；若求主析取范式方便，则可先求主析取范式，然后再写出主合取范式，若求主析取范式方便，则可先求主析取范式，然后再写出主合取范式，这样比直接求主合取范式方便；这样比直接求主合取范式方便；第三十六页，讲稿共四十二页哦应用应用3.判断命题公式的类型判断命题公式的类型设公式A中含n个命题变项，容易看出(1)A 为重言式当且仅当 A 的主析取范式含全部2n个极小项。(2)A 为矛盾式当且仅当 A 的主析取范式不含任何极小项。此时，记 A 的主析取范式为0.(3)A 为可满足式当且仅当 A 的主析取范式中至少含有一个极小项。例题：例题：用公式的主析取范式判断公式的类型：第三十七页，讲稿共四十二页哦应用应用4.求命题公式的成真和成假赋值求命题公式的成真和成假赋值如在上例(3)中，000，001，011，101,111是成真赋值，010,100，110是成假赋值。第三十八页，讲稿共四十二页哦四、主析取范式与主合取范式的相互转化四、主析取范式与主合取范式的相互转化1.由公式的主析取范式求主合取范式由公式的主析取范式求主合取范式步骤：步骤：例题：例题：第三十九页，讲稿共四十二页哦2.重言式与矛盾式的主析取范式与主合取范式重言式与矛盾式的主析取范式与主合取范式 矛盾式无成真赋值，因而矛盾式的主合取范式含2n（n为公式中命题变项个数）个极大项，而重言式无成假赋值，因而主合取式不含任何极大项。将重言式的主合取式记为1，至于可满足式，它的主合取范式中极大项的个数一定小于2n第四十页，讲稿共四十二页哦注注：AB当且仅当当且仅当A与与B有相同的真值表，又当且仅当有相同的真值表，又当且仅当A与与B有有相同的主析取范式（主合取范式）。因而可以这样说，真值表相同的主析取范式（主合取范式）。因而可以这样说，真值表与主析取范式（主合取范式）是描述命题公式标准形的两种不与主析取范式（主合取范式）是描述命题公式标准形的两种不同的等价形式，因而两者是可以相互确定的，即由同的等价形式，因而两者是可以相互确定的，即由A的主析取的主析取（主合取）范式，立即可确定（主合取）范式，立即可确定A的真值表，反之，由的真值表，反之，由A的真值的真值表可以立刻确定表可以立刻确定A的主析取（主合取）范式。的主析取（主合取）范式。第四十一页，讲稿共四十二页哦本节要掌握：析取范式、合取范式、主析取范式、主合取范式的写法，范式的应用。作业：习题二（P39）1,3(2),4(3),5(2),8(2),11(3),12,13,14 15(1),16(2),23,25,30第四十二页，讲稿共四十二页哦