命题逻辑等值演算 .ppt

《命题逻辑等值演算 .ppt》由会员分享，可在线阅读，更多相关《命题逻辑等值演算 .ppt（42页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、命题逻辑等值演算 现在学习的是第1页，共42页基本要求：1.深刻理解等值式的概念。深刻理解等值式的概念。2.牢牢记记24个个基基本本等等值值式式，这这是是等等值值演演算算的的基基础础；能能熟熟练练地地应应用用它它们们进进行行等值演算。等值演算。3.了解简单析取式、简单合取式、析取范式、合取范式的概念。了解简单析取式、简单合取式、析取范式、合取范式的概念。4.深深刻刻理理解解极极小小项项及及极极大大项项的的定定义义及及它它们们的的名名称称，及及名名称称下下角角标标与与成成真真赋赋值的关系。值的关系。5.熟练掌求公式的主析取范式的方法。熟练掌求公式的主析取范式的方法。6.熟练掌握由公式的主析取范式

2、求公式的主合取范式的方法。熟练掌握由公式的主析取范式求公式的主合取范式的方法。7.会会用用公公式式的的主主析析取取范范式式（主主合合取取范范式式）求求公公式式的的成成真真赋赋值值、成成假假赋值。赋值。8.会将公式等值地化为任何联结词完备集中的公式。会将公式等值地化为任何联结词完备集中的公式。现在学习的是第2页，共42页某公司派小李或小张去上海出差，若派小李去，则小赵某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？司是如何派遣的？解：解：复合命题（公式）复合命题（公式）例题例题(p(p

3、q q)(p(pr r)(q(qs s)r rA=A=现在学习的是第3页，共42页(p(pqq)(p(pr r)(q(qs s)r rA=A=p qrsp q pr qs r(pq)(pr)(qs)r000001110000101110001001100001101100010011010010111111011011000011111100100010110100110110101011100101111100110010010110110110111011000111111100麻烦！麻烦！计算量大！计算量大！方法很多：方法很多：真值表法真值表法 等值演算法等值演算法现在学习的是第4页，共

4、42页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的真值相同，表明它们之间彼此等价等价。现在学习的是第5页，共42页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 现

5、在学习的是第6页，共42页(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)(对对的分配律的分配律)互补律互补律(对对的分配律的分配律)现在学习的是第7页，共42页(13)等价等值式等价等值式AB(AB)(BA)AB(AB)(A B)AB(AB)(A B)(14)假言易位假言易位ABBA(15)等价否定等值式等价否定等值式ABA B(16)归谬论归谬论(AB)(AB)A(12)蕴

6、含等值式蕴含等值式ABAB现在学习的是第8页，共42页4.等价公式的证明方法方法1：用列真值表。（不再举例）方法2：用公式的等价变换.(用置换定律)置换定律:A是一个命题公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，则AB。应用置换定律以及前面列出的等价公式可以对给定公式进行等价变换。等值演算等值演算：由已知等值式推演出新的等值式的过程。：由已知等值式推演出新的等值式的过程。现在学习的是第9页，共42页例题1.用等值演算法证明下面等值式：(1)(pq)(pq)(pq)(2)q(pr)(pq)r证明：证明：(1)从左边开始演算 (pq)(pq)(pq)(pq)(双重

7、否定律)(pq)(pq)(德摩根律)(pq)(pq)(德摩根律)(pp)(pq)(qp)(qq)(分配律)(pq)(qp)(同一律)(p q)(q p)(蕴含等值式)(pq)(等价等值式)11现在学习的是第10页，共42页例题1.用等值演算法证明下面等值式：(2)q(pr)(pq)r证明：证明：(2)从右边开始演算 (pq)r(pq)r (蕴含等值式)pqr (德摩根律)q(pr)(交换律)q(pr)(蕴含等值式)q(pr)(蕴含等值式)现在学习的是第11页，共42页例题2.用等值演算法判断下列公式的类型：(1)(pq)(pq)(2)p(pqr)(3)(pq)q)r解：解：(1)(pq)(pq

8、)(pq)(pq)(蕴含等值式)(pq)(pq)(德摩根定律)(pq)(pq)(双重否定律)p(qq)(分配律)p1 (排中律)p (同一律)因为因为p是可满足式，故式是可满足式，故式(1)为可满足式为可满足式现在学习的是第12页，共42页例题2.用等值演算法判断下列公式的类型：(2)p(pqr)解：解：(2)p(pqr)p(pqr)(蕴含等值式)(pp)(qr)(分配律)1(qr)(排中律)1 (零律)因为因为1是重言式，故式是重言式，故式(2)为重言式为重言式现在学习的是第13页，共42页例题2.用等值演算法判断下列公式的类型：(3)(pq)q)r解：解：(3)(pq)q)r (pq)q)

9、r (蕴含等值式)p(q q)r (德摩根律、结合律)p0r (矛盾律)0 (零律)因为因为p是矛盾式，故式是矛盾式，故式(3)为矛盾式为矛盾式现在学习的是第14页，共42页某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？去，小王也得去。小赵没加班。问公司是如何派遣的？(p(pq q)(p(pr r)(q(qs s)r rA=A=例题例题.用等值演算法解决实际问题用等值演算法解决实际问题p p：派小李去上海出差：派小李去上海出差q q：派小张去上海出差：派小张去上海出

10、差r r：小赵要加班：小赵要加班s s：小王也去上海出差：小王也去上海出差 (pq)(pr)(qs)r (德摩根律)(pq)(pr)r (qs)(交换律)(pq)(pr)(qs)(分配律、矛盾律)(ppr)(qpr)(qs)(分配律)(qpr)(qs)(矛盾律)(qprs)(分配律、矛盾律)结论：派遣方案为：派小张和小王去上海出差，只有结论：派遣方案为：派小张和小王去上海出差，只有这一种方案这一种方案现在学习的是第15页，共42页2.2.范式 范式就是命题公式形式的规范形式。这里约定在范式中 只含有联结词只含有联结词、和和。一.析取范式与合取范式1.合取式与析取式合取式与析取式 合取式合取式：

11、是用“”联结命题变元或变元的否定构成的式子。如 P、P、PQ、PQR 析取式析取式：是用“”联结命题变元或变元的否定构成的式子。如 P、P、PQ、PQR注注:PPPPPPP是合是合(析析)取式取式.现在学习的是第16页，共42页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)-合取范式

12、现在学习的是第17页，共42页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用分配律、幂等律等公式进行整理，使之成为所要求的形式。用分配律、幂等律等公式进行整理，使之成为所要求的形式。(对偶式对偶式)现在学习的是第18页，共42页例如求(PQ)R的析取范式与合取范式(

13、PQ)R (PQ)(PQ)R(PQ)(PQ)R -析取范式(PQ)R(PQ)(PQ)R(PQ)(PQ)R(PQR)(PQR)-合取范式现在学习的是第19页，共42页二.主析取范式与主合取范式 一个公式的析取范式与合取范式的形式是不唯一的。下面定义形式唯一的主析取范式与主合取范式。主析取范式主析取范式 1.极小项极小项 定义：在一个有n个命题变元的合取式中，每个变元必出现且仅出现一次，称这个合取式是个极小极小项项。例如，有两个变元的极极小项：PQ、PQ、PQ、PQ现在学习的是第20页，共42页 极小项的性质极小项的性质m3m2m1m0PQPQP Q PQ P Q00FFFFFT01FTFFTF1

14、0TFFTFF11TTTFFFa).有有n个变元，则有个变元，则有2n个极小项。个极小项。b).每一组指派有且只有一个极小项为每一组指派有且只有一个极小项为T。为了记忆方便，可将各组指派对应的为为了记忆方便，可将各组指派对应的为T的极小项的极小项分别记作分别记作m0,m1,m2,m2n-1上例中上例中m0 P Qm1 PQm2P Qm3PQ现在学习的是第21页，共42页2.主析取范式定义 析取范式 A1A2.An,其中每个Ai(i=1,2.n)都是极极小项，称之为主析取范式主析取范式。3.主析取范式的写法 方法：列真值表 列出给定公式的真值表。找出真值表中每个“T”对应的极极小项。(如何根据一

15、组指派写对应的为“T”的项：如果变元P被指派为T，P在极极小项中以P形式出现；如变元P被指派为F,P在极极小项中以P形式出现(因要保证该极极小项为T)。用“”联结上述极极小项，即可。现在学习的是第22页，共42页例如求 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)思考题:永真式的主析取范式是什么样？现在学习的是第23页，共42页方法方法：用公式的等价变换：用公式的等价变换先写出给定公式的析取范式先写出给定公式的析取范式A1A2.An。为使每个为使每个Ai都变

16、成极小项，对缺少变元的都变成极小项，对缺少变元的Ai补全变元，补全变元，比如缺变元比如缺变元R，就用，就用联结永真式联结永真式(R R)形式补形式补R。用分配律等公式加以整理用分配律等公式加以整理。PQPQ(P(Q Q)(P P)Q)(PQ)(P Q)(PQ)(PQ)(PQ)(P Q)(PQ)现在学习的是第24页，共42页主主合取范式合取范式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

17、T F T T T T T T F现在学习的是第25页，共42页极大项的性质极大项的性质 a).有n个变元，则有2n个极极大项。b).每一组指派有且只有一个极极大项为F。为了记忆方便，可将各组指派对应的为F的极极大项分别记作M0,M1,M2,M2n-1。上例中 M0 PQ M1 PQ M2 PQ M3 PQ 现在学习的是第26页，共42页极大项与极小项之间的关系极大项与极小项之间的关系 定理定理2.3：现在学习的是第27页，共42页2.主合取范式定义主合取范式定义 合取范式 A1A2.An,其中每个Ai(i=1,2.n)都是极大项，称之为主合取范式主合取范式。3.主合取范式的写法主合取范式的写

18、法 方法：列真值表 列出给定公式的真值表。找出真值表中每个“F”对应的极极大项。如何根据一组指派写对应的为“F”的极极大项：如果变元P被指派为F，P在极极大项中以P形式出现；如变元P被指派为T，P在极极大项中以 P形式出现(确保该极极大项为F)。用“”联结上述大项，即可。现在学习的是第28页，共42页例如求 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)现在学习的是第29页，共42页方法：用公式的等价变换先写出给定公式的合取范式 A1A2.An。为使每个Ai变成极极大项，对缺少变元的

19、析取式Ai补全变元，比如缺变元R，就用联结永假式(RR)形式补R。用分配律等公式加以整理。现在学习的是第30页，共42页例如，求(PQ)R的主合取范式(PQ)R(PQ)R(PQ)R(PR)(QR)(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)现在学习的是第31页，共42页三三.主主范式的应用范式的应用1.应用主析取范式解决实际问题应用主析取范式解决实际问题某公司派小李或小张去上海出差，若派小李去，则小赵要加班。某公司派小李或小张去上海出差，若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的若派小张去，小王也得去。小赵没加班。问公司是如何派遣

20、的？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现在学习的是第32页，共42页应用应用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

21、)(qrq)(qrpr)(pqr)(pqr)(pqr)(pqr)(pqr)m3m6m7m7m6m3m3m6m7由于由于A与与B有相同的主析取范式，所以有相同的主析取范式，所以A B现在学习的是第33页，共42页解：求解：求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 用主析取范式或主合取范式判断两个命题公式是否等值用主析取范式或主合取范式判断两个命题公式是否等

22、值(1)设设A=(pq)(pqr)，B=(p(qr)(q(pr)M1M0M2M5M4M0M1M2M4M5M0M1M2M4M5现在学习的是第34页，共42页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由于由于

23、A与与B有相同的主合取范式，所以有相同的主合取范式，所以A B现在学习的是第35页，共42页说明：A=(pq)(pqr)m3m6m7M0M1M2M4M5没出现在主析取范式中的极小项为没出现在主析取范式中的极小项为m0,m1,m2,m4,m5.没出现在主合取范式中的极大项为没出现在主合取范式中的极大项为M3,M6,M7.所以由公式的主析取范式可以得到主合取范式所以由公式的主析取范式可以得到主合取范式也可由公式的主合取范式确定主析取范式也可由公式的主合取范式确定主析取范式在演算中，若求主合取范式方便，则可先求主合取范式，然后再写出主在演算中，若求主合取范式方便，则可先求主合取范式，然后再写出主析取

24、范式，这样比直接求主析取范式方便；析取范式，这样比直接求主析取范式方便；若求主析取范式方便，则可先求主析取范式，然后再写出主合取范式，若求主析取范式方便，则可先求主析取范式，然后再写出主合取范式，这样比直接求主合取范式方便；这样比直接求主合取范式方便；现在学习的是第36页，共42页应用应用3.判断命题公式的类型判断命题公式的类型设公式A中含n个命题变项，容易看出(1)A 为重言式当且仅当 A 的主析取范式含全部2n个极小项。(2)A 为矛盾式当且仅当 A 的主析取范式不含任何极小项。此时，记 A 的主析取范式为0.(3)A 为可满足式当且仅当 A 的主析取范式中至少含有一个极小项。例题：例题：

25、用公式的主析取范式判断公式的类型：现在学习的是第37页，共42页应用应用4.求命题公式的成真和成假赋值求命题公式的成真和成假赋值如在上例(3)中，000，001，011，101,111是成真赋值，010,100，110是成假赋值。现在学习的是第38页，共42页四、主析取范式与主合取范式的相互转化四、主析取范式与主合取范式的相互转化1.由公式的主析取范式求主合取范式由公式的主析取范式求主合取范式步骤：步骤：例题：例题：现在学习的是第39页，共42页2.重言式与矛盾式的主析取范式与主合取范式重言式与矛盾式的主析取范式与主合取范式 矛盾式无成真赋值，因而矛盾式的主合取范式含2n（n为公式中命题变项个

26、数）个极大项，而重言式无成假赋值，因而主合取式不含任何极大项。将重言式的主合取式记为1，至于可满足式，它的主合取范式中极大项的个数一定小于2n现在学习的是第40页，共42页注注：AB当且仅当当且仅当A与与B有相同的真值表，又当且仅当有相同的真值表，又当且仅当A与与B有有相同的主析取范式（主合取范式）。因而可以这样说，真值表相同的主析取范式（主合取范式）。因而可以这样说，真值表与主析取范式（主合取范式）是描述命题公式标准形的两种不与主析取范式（主合取范式）是描述命题公式标准形的两种不同的等价形式，因而两者是可以相互确定的，即由同的等价形式，因而两者是可以相互确定的，即由A的主析取的主析取（主合取）范式，立即可确定（主合取）范式，立即可确定A的真值表，反之，由的真值表，反之，由A的真值的真值表可以立刻确定表可以立刻确定A的主析取（主合取）范式。的主析取（主合取）范式。现在学习的是第41页，共42页本节要掌握：析取范式、合取范式、主析取范式、主合取范式的写法，范式的应用。作业：习题二（P39）1,3(2),4(3),5(2),8(2),11(3),12,13,14 15(1),16(2),23,25,30现在学习的是第42页，共42页