逻辑蕴涵式精选文档.ppt

《逻辑蕴涵式精选文档.ppt》由会员分享，可在线阅读，更多相关《逻辑蕴涵式精选文档.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、逻辑蕴涵式本讲稿第一页，共三十六页2023/1/292对蕴涵式性质的证明蕴涵性质正确性的证明蕴涵性质正确性的证明,以以简化真值表法简化真值表法较为简单较为简单证证P PQ Q当且仅当要证当且仅当要证PQPQ是永真式是永真式如果不发生第二行的情况如果不发生第二行的情况,即即 当当前件取真时后件必取真前件取真时后件必取真，也可，也可 以是以是后件取假时前件必为假，后件取假时前件必为假，条条 件命题公式必为永真式件命题公式必为永真式 运用运用的的证明法称证明法称简化真值表法简化真值表法P QP QP PQQT TT TT FT FF TF TF F F F T TF FT TT T本讲稿第二页，共三

2、十六页2023/1/293运用简化真值表法证明蕴涵式例例1.1.证明：证明：P(PP(PQ)Q)Q.Q.证明：证明：方法方法.考虑考虑P(PP(PQ)Q)Q.Q.假定前件假定前件P(PP(PQ)Q)取真值为真取真值为真,则则P P和和P PQ Q都取真值真都取真值真,因而后件因而后件Q Q也也只能取真值真只能取真值真只能取真值真只能取真值真 P(PP(PQ)Q)Q Q是永真式是永真式,从而从而P(PP(PQ)Q)Q.Q.方法方法.考虑考虑P(PQ)Q,设设后件后件Q取值假取值假,则则P可取真值可取真值T或真值或真值F.显然显然,不论不论P取真值假取真值假,还是取真值真还是取真值真,前件前件P(

3、PQ)都取真值都取真值F,即即P(PQ)Q是永真式是永真式从而从而P(PQ)Q.试用证明的试用证明的另一种形式另一种形式(在具体证明时选二者之一在具体证明时选二者之一)?本讲稿第三页，共三十六页2023/1/294重言式与蕴涵式的关系定理：定理：设设A A和和B B是任意两个命题公式是任意两个命题公式 则则A A=B B的的充要条件充要条件充要条件充要条件是是A AB B且且B BA.A.证明：证明：p必要性：必要性：若若A A=B B，则则A AB B是永真式是永真式 而而A AB B(A(AB)(BB)(BA),A),故故A AB B和和 B BA A 皆为永真式皆为永真式,即即A AB,

4、BB,BA.A.充分性：充分性：若若A AB B且且B BA A，则则A AB B和和B BA A均为永真式均为永真式,由于由于(A(AB)(BB)(BA)A)A AB B，所以，所以A AB B为永为永 真式，即真式，即A A=B.B.本讲稿第四页，共三十六页2023/1/295基本蕴涵式以下各式是常用的蕴涵式以下各式是常用的蕴涵式,称为称为基本蕴涵式基本蕴涵式，可以用真值表法、，可以用真值表法、简化的真值表法一一证明简化的真值表法一一证明.(1)(1)化简式：化简式：PQPQP P，PQPQQ Q；(2)(2)附加式：附加式：P PPQPQ，Q QPQPQ；(3)(3)假言推论：假言推论：

5、P(PP(PQ)Q)Q Q；(4)(4)拒取式：拒取式：Q(PQ(PQ)Q)P P；(5)(5)析取三段论：析取三段论：P(PP(PQ)Q)Q Q；(6)(6)假言三段论：假言三段论：(P(PQ)(QQ)(QR)R)P PR R；(7)(7)双条件三段论：双条件三段论：(P PQ)(QQ)(QR)R)P PR R；在命题逻辑推理中与在命题逻辑推理中与基本等值式基本等值式一样重要的还有一样重要的还有基本蕴涵式基本蕴涵式本讲稿第五页，共三十六页2023/1/296基本蕴涵式 (8)(8)二难推论二难推论(析取构造二难析取构造二难)：(P PR)(QR)(QS)(PQ)S)(PQ)RSRS；(9)(

6、9)合成式：合成式：P,QP,QPQ.PQ.有时也使用下面蕴涵式有时也使用下面蕴涵式：化简式变形化简式变形：(P PQ)Q)P P，(P PQ)Q)Q Q；附加式变形附加式变形：P PP PQ Q，Q QP PQ Q；合取构造二难合取构造二难:(P(PR)(QR)(QS)(PQ)S)(PQ)RSRS；前后件同附加前后件同附加：P PQ Q(PR)(PR)(QR).(QR).本讲稿第六页，共三十六页2023/1/297基本蕴涵式举例 1)1)假言推理：饮食自倍假言推理：饮食自倍,肠胃乃伤；贾母吃多了，所以她伤了肠肠胃乃伤；贾母吃多了，所以她伤了肠胃。胃。(P(PP(PQ)Q)Q Q)2)2)拒取

7、式：拒取式：伊索寓言伊索寓言卜人卜人 卜人摆摊街边，其邻居冲冲卜人摆摊街边，其邻居冲冲赶来告知赶来告知“你家你家,门被撬门被撬”。摊边一人说：。摊边一人说：“既然你能预既然你能预卜未知，怎么就没有算出自家被盗？卜未知，怎么就没有算出自家被盗？”(Q(PQ(PQ)Q)P P)3)3)必要条件假言推理：纪晓岚必要条件假言推理：纪晓岚微草堂笔记微草堂笔记伊犁无井，皆伊犁无井，皆汲于河。一佐领曰：戈壁积沙无水，故草木不生。今城中汲于河。一佐领曰：戈壁积沙无水，故草木不生。今城中多老树，苟其下无水，树安得活？乃拔木就根下掘井，果多老树，苟其下无水，树安得活？乃拔木就根下掘井，果皆得泉。皆得泉。(Q(Q(

8、P PQ)Q)P P：只有有水，草木才能活；老只有有水，草木才能活；老树能活，所以有水树能活，所以有水。)本讲稿第七页，共三十六页2023/1/298 4)析取三段论：析取三段论：韩非子韩非子“郑人买履郑人买履”郑人去集市买鞋郑人去集市买鞋,却忘了却忘了带在家里量好的尺寸带在家里量好的尺寸,赶忙返家去拿赶忙返家去拿,当他再回集市当他再回集市,集市已散。集市已散。有人问有人问“汝弗以脚试汝弗以脚试?”答答“吾宁信绳勿信脚。吾宁信绳勿信脚。”(P(PP(PQ)Q)Q Q)5)5)二难推论：二难推论：战国策战国策秦策秦策秦宣太后爱魏丑夫秦宣太后爱魏丑夫,太后病将死太后病将死,出令曰：为我葬出令曰：为

9、我葬,必以魏子为殉！魏子患之必以魏子为殉！魏子患之,庸芮为魏子说太后曰：庸芮为魏子说太后曰：以死者为有知乎？太后曰：无知也！以死者为有知乎？太后曰：无知也！曰：若太后之神灵曰：若太后之神灵,明知死者明知死者之无知矣之无知矣,何为以生之所爱何为以生之所爱,葬于无知之死人哉！若死者有知葬于无知之死人哉！若死者有知,先先王积怒之日久矣王积怒之日久矣,太后极过不赡太后极过不赡,何暇及私魏丑夫乎何暇及私魏丑夫乎?太后曰：太后曰：善。乃止。善。乃止。(PQ)(P(PQ)(PR)(QR)(QS)S)RSRS )基本蕴涵式举例本讲稿第八页，共三十六页2023/1/299 10.6 范 式用真值表的方法可以解决

10、命题公式的判定问题用真值表的方法可以解决命题公式的判定问题当公式中命题变元的数目较大时当公式中命题变元的数目较大时,真值表方法就显得很烦琐真值表方法就显得很烦琐命题公式的判定问题需要研究新的方法命题公式的判定问题需要研究新的方法1.1.合取式合取式&析取式析取式定义：定义：称仅由称仅由命题变元命题变元及其及其否定否定构成的合取式命题公式为构成的合取式命题公式为 简单合取式简单合取式（短语）（短语）（短语）（短语）称仅由命题变元及其否定构成的析取式命题公式为称仅由命题变元及其否定构成的析取式命题公式为 简单析取式简单析取式（子句）（子句）（子句）（子句）本讲稿第九页，共三十六页2023/1/29

11、10简单合取式与简单析取式p公式公式P,P,Q,PQQ,PQ和和PQPPQP等都是简单合取式等都是简单合取式 称称P,QP,Q和和P P为相应的简单合取式的合取项为相应的简单合取式的合取项p公式公式P,P,Q,PQ,Q,PQ,PQPPQP等都是简单析取式等都是简单析取式 称称P,QP,Q和和P P为相应简单析取式的析取项为相应简单析取式的析取项.注意：注意：一个命题变元或其否定一个命题变元或其否定既可以是简单合取式既可以是简单合取式,也是简单也是简单析取式析取式。如例中。如例中P,Q等。等。本讲稿第十页，共三十六页2023/1/2911续定理：定理：简单合取式为永假式的充要条件是公式中含有互否

12、文字简单合取式为永假式的充要条件是公式中含有互否文字 简单析取式为永真式的充要条件是公式中含有互否文字简单析取式为永真式的充要条件是公式中含有互否文字证明证明：(充分性充分性)对于任一命题变元对于任一命题变元P,PP,PP P在在简单合取式简单合取式中出中出 现现,它必是永假式；它必是永假式；(必要性必要性)假设某一假设某一简单合取式简单合取式是永假式是永假式,但它不含互否但它不含互否 文字。当为所有命题变员指派真值文字。当为所有命题变员指派真值T,T,而所有带而所有带 否定词的命题变元指派真值否定词的命题变元指派真值F F时时,即为该短语的即为该短语的 成真指派成真指派,这与永假矛盾这与永假

13、矛盾 简单析取式同理可证简单析取式同理可证本讲稿第十一页，共三十六页2023/1/2912简单合取式与简单析取式例例1 短语短语PQPPQP是永假式是永假式 短语短语PQPQPRPR不是永假式是可满足式不是永假式是可满足式:P/F,Q/T,R/TP/F,Q/T,R/T时成真时成真 子句子句PQPPQP是永真式是永真式 子句子句PQPQPRPR不是永真式但是可满足不是永真式但是可满足式式:P/T,Q/F,R/F:P/T,Q/F,R/F时成假时成假.本讲稿第十二页，共三十六页2023/1/2913析取范式与合取范式定义定义一个命题公式一个命题公式A A称为析取范式称为析取范式,当且仅当当且仅当A

14、A可表示可表示 为简单合取式的析取为简单合取式的析取(短语的析取式短语的析取式),),即即 A A A A1 1AA2 2AAn n，式中，式中A Ai i为简单合取式为简单合取式(短短 语语),i=1,2,),i=1,2,n,n；一个命题公式一个命题公式A A称为合取范式称为合取范式,当且仅当当且仅当A A可表示可表示 为简单析取式的合取为简单析取式的合取(子句的合取式子句的合取式),),即即A A A A1 1AA2 2 A Am m，式中，式中A Aj j为简单析取式为简单析取式(子子 句句),j=1,2,),j=1,2,m.,m.例例2 2 用真值表可证用真值表可证(PQ)(QR)(R

15、P)(PQ)(QR)(RP)(G G)(PQ)(PPQ)(PR)(R)(QR)QR)(P(PQ)(Q)(PR)(QPR)(QR)R)同一命题公式同一命题公式G有着两个形式不同的合取范式有着两个形式不同的合取范式例例3 用真值表可证用真值表可证(P(Q R)(P Q R)(H)(P Q)(P R)(Q R)(P Q)(P R)(Q R)同一命题公式同一命题公式H有着两个形式不同的析取范式有着两个形式不同的析取范式本讲稿第十三页，共三十六页2023/1/2914析取范式与合取范式定理：定理：对于任何一命题公式对于任何一命题公式G,G,都存在与其逻辑等值的析都存在与其逻辑等值的析 取范式和合取范式取

16、范式和合取范式证明：证明：构造性证明：构造性证明：将将G G等值化归到逻辑联词组等值化归到逻辑联词组 ,上；上；使用反演律将否定词使用反演律将否定词深入到命题变元之前；深入到命题变元之前；适当运用结合律适当运用结合律,分配律等基本等值式将分配律等基本等值式将G G化化 为析取范式或合取范式为析取范式或合取范式本讲稿第十四页，共三十六页2023/1/2915析取范式与合取范式例例4(P(P(QR)QR)(PQR)(PQR)=(=(PP(QR)(PQR)(QR)(PQR)(等值化归等值化归)=(=(PPQQR)(PQR)(R)(PQR)(否定深入否定深入)合取范式合取范式 =(P P)(Q P)(

17、R P)(P Q)(Q Q)(R Q)(P R)(Q R)(R R)(分配律分配律)-短语的析取式即短语的析取式即析取范式析取范式；=(P Q)(P R)(P Q)(Q R)(P R)(Q R),(矛盾律矛盾律,壹律壹律,交换律交换律)。本讲稿第十五页，共三十六页2023/1/2916范式的应用对命题公式进行判定：对命题公式进行判定：定理定理 命题公式命题公式A A为永假式的充要条件是为永假式的充要条件是A A的析取范式的析取范式 中每个中每个短语短语短语短语都至少包含一对互否文字都至少包含一对互否文字 命题公式命题公式A A为永真式的充要条件是为永真式的充要条件是A A的合取范式的合取范式

18、中每个中每个子句子句子句子句都至少包含一对互否文字都至少包含一对互否文字4.范式的不唯一性范式的不唯一性 前述例前述例2与例与例3的的G与与H式分别有两个相异的合取范式式分别有两个相异的合取范式 和析取范式和析取范式本讲稿第十六页，共三十六页2023/1/2917范式的应用例例5 5 命题公式命题公式(P(PQQP)(PP)(PRR)RR)命题公式命题公式(PPQP)(PQRQP)(PQRQ)Q)例例6 6 (P (PQ)Q)P P (PQ)PPQ)P (P(P Q)PQ)P P(P(两个不同形式的析取范式两个不同形式的析取范式)P(P(QP)QP)P(P(两个不同形式的合取范式两个不同形式的

19、合取范式).).范式可以解决公式判定问题范式可以解决公式判定问题,但范式的不唯一但范式的不唯一 性仍不能令人满意性仍不能令人满意,唯一性问题由主范式解决唯一性问题由主范式解决永假式永假式永真式永真式本讲稿第十七页，共三十六页2023/1/2918 主析取范式1.1.主析取范式主析取范式 布尔小项的概念布尔小项的概念定义定义 在含有在含有n n个命题变元的个命题变元的简单合取式简单合取式简单合取式简单合取式中中,若每个命题若每个命题 变元及其否定二者之一都出现一次且仅出现一次变元及其否定二者之一都出现一次且仅出现一次,则称该简单合取式为布尔小项则称该简单合取式为布尔小项,或布尔积或布尔积p n

20、n个命题变元共有布尔小项个命题变元共有布尔小项2 2n n个个例例7.7.试三个命题变元试三个命题变元(P(P，Q Q，R)R)的布尔小项？的布尔小项？PQR PQR PQR PQR PQPQPQPQ R R R R P P P P QR PQR PQR PQR P QQQQ R R R R PQ R PQ R PQ R PQ R PQPQPQPQ R R R R PPPP QR QR QR QR PPPP QQQQ R R R R 其编码分别是其编码分别是(变元编变元编1,变元的否定编变元的否定编0):111,110,101,100,011,010,001,000(共共2 23个个).本讲稿

21、第十八页，共三十六页2023/1/2919布尔小项规定规定命题变元按字典序排列命题变元按字典序排列,命题命题变元对应变元对应1 1,命题命题变元的否定对应变元的否定对应0 0即得布尔小项的二进制编码即得布尔小项的二进制编码.显然显然n n个命题变元的布尔小项个命题变元的布尔小项有有2 2n n个个,它们与它们与n n长二进制数一一对应长二进制数一一对应.一般布尔小项记为一般布尔小项记为m mi i,其下标其下标i i是由相应二进制数转换的十进制数。二进制码的布尔小是由相应二进制数转换的十进制数。二进制码的布尔小项与其真值表的取值有如下对应性质：项与其真值表的取值有如下对应性质：本讲稿第十九页，

22、共三十六页2023/1/2920布尔小项的性质 布尔小项的性质布尔小项的性质 1)1)不同布尔小项值不同不同布尔小项值不同,即各布尔小项的真值表各即各布尔小项的真值表各 不相同不相同 2)2)相异布尔小项的合取式是永假式相异布尔小项的合取式是永假式 即即 m mi immj jF F，ijij；3)3)全部布尔小项的析取式是永真式全部布尔小项的析取式是永真式 即即 m m1 1mm2 2mmk kT,k=2T,k=2n n；4)4)每个布尔小项都只有一个成真指派每个布尔小项都只有一个成真指派,且其成真指且其成真指 派与其二进制编码一致派与其二进制编码一致本讲稿第二十页，共三十六页2023/1/

23、2921主析取范式 主析取范式的定义及其唯一存在定理主析取范式的定义及其唯一存在定理定义：定义：在给定公式的析取范式中在给定公式的析取范式中,若其短语都是布尔小项若其短语都是布尔小项,则称该范式为主析取范式则称该范式为主析取范式定理定理 任意任意n n个命题变元的可满足命题公式个命题变元的可满足命题公式A A都唯一存在与其都唯一存在与其 逻辑等值的逻辑等值的主主主主析取范式；不可满足公式析取范式；不可满足公式(永假式永假式)的主的主 析取范式是空式析取范式是空式证明证明 首先求出首先求出A A的真值表，在的真值表，在A A的真值表中的真值表中,对应对应A A取真值取真值1 1的行取的行取布尔小

24、项布尔小项,使其二进制脚标与该行的真值指派一致使其二进制脚标与该行的真值指派一致.所有这些所有这些小项的析取式小项的析取式,即为即为A A的主析取范式的主析取范式.显然显然A A的主析取范式与的主析取范式与A A逻辑等值且唯一逻辑等值且唯一,而永假式的主析取范式是空式而永假式的主析取范式是空式本讲稿第二十一页，共三十六页2023/1/2922求主析取范式的真值表法例例8 8 用真值表法求用真值表法求(P(Q(P(QR)R)(PQR)(PQR)的主析的主析取范式取范式解：解：设设G G(P(Q(P(QR)R)(PQR),(PQR),则：则：G=(G=(P P Q Q R R)(P)(P QQ R

25、)(PQR)R)(PQR)m m000000mm100100mm111 111=.本讲稿第二十二页，共三十六页2023/1/2923求主析取范式的等值演算法 求命题公式的主析取范式除了求命题公式的主析取范式除了真值表方法真值表方法外外,还有还有等值演等值演算法算法,具体步骤是：具体步骤是：1)1)将给定公式将给定公式A A等值化归为析取范式；等值化归为析取范式；2)2)删除析取范式中所有永假短语删除析取范式中所有永假短语(壹律壹律)；3)3)由等幂律实现短语中文字的无重出现；由等幂律实现短语中文字的无重出现；4)4)用同一律补进短语中或缺的命题变元用同一律补进短语中或缺的命题变元,通过分配律使

26、成布通过分配律使成布尔小项的析取式尔小项的析取式,按字典序对布尔小项短语排序并用按字典序对布尔小项短语排序并用等幂律使之无重等幂律使之无重,最后步的结果即为最后步的结果即为A A的主析取范式的主析取范式 本讲稿第二十三页，共三十六页2023/1/2924求主析取范式的等值演算法例例9 用用等值推演法等值推演法求求(P(QR)(P Q R)的主析的主析 取范式。取范式。解：解：(P(QR)(P Q R)(P(Q R)(Q R)(P P Q Q R R)(P Q R)(P Q R)(P P Q Q R R)(P P Q Q R R)(P Q R)(P Q R)m000 m100 m111 (分配律

27、分配律,排序整理排序整理)0,4,7 .(联词化归联词化归,否定深入否定深入)本讲稿第二十四页，共三十六页2023/1/2925求主析取范式的等值演算法例例1010 用用等值推演法等值推演法求求P(QR)P(QR)的的主析取范式。主析取范式。解：解：P(P(QRQR)(P(P Q)Q)(PR)(PR)(P(P Q Q(R(R R)R)(P(P(Q(Q Q)Q)R)(R)(补缺补缺)(P(P QR)QR)(P(P QQ R)R)(PQR)(P(PQR)(P QR)QR)(P(P QQ R)R)(P(P QR)QR)(PQR)(PQR)m m100100mm101101mm1111114,5,74

28、,5,7.(.(交换交换,等幂等幂,整理次序整理次序)本讲稿第二十五页，共三十六页2023/1/2926主合取范式2.2.主合取范式主合取范式 布尔大项的概念布尔大项的概念定义：定义：在含有在含有n n个命题变元的简单析取式中个命题变元的简单析取式中,若每个命题变元及其若每个命题变元及其否定二者之一都出现一次且仅出现一次否定二者之一都出现一次且仅出现一次,则称该简单析取式为则称该简单析取式为布尔大项布尔大项.显显n n个命题变元共有布尔大项个命题变元共有布尔大项2 2 2 2n n n n个个.例例11.11.试给出试给出三个命题变元三个命题变元(P,Q,R)(P,Q,R)的布尔大项？的布尔大

29、项？PP QQ R R；PP QRQR；PQPQ R R；PQRPQR；PP QQ R R；PP QRQR；PQ PQ R R；PQR.PQR.其编码分别是：其编码分别是：111,110,101,100,011,010,001和和000(变元编变元编0,变元的否定编变元的否定编1,与小项相反与小项相反)本讲稿第二十六页，共三十六页2023/1/2927布尔大项本讲稿第二十七页，共三十六页2023/1/2928布尔大项的性质 布尔大项的性质布尔大项的性质 1)1)不同布尔大项值不同不同布尔大项值不同,即各布尔大项的真值表各即各布尔大项的真值表各 不相同；不相同；2)2)相异布尔大项的析取式是永真

30、式，即相异布尔大项的析取式是永真式，即 M Mi iMMj jT T，ijij；3)3)全部布尔大项的合取式是永假式，即全部布尔大项的合取式是永假式，即 M M1 1MM2 2MMk kF F,k=2,k=2n n；4)4)每个布尔大项都只有一个成假指派每个布尔大项都只有一个成假指派,且成假指派且成假指派 与其二进制编码一致与其二进制编码一致本讲稿第二十八页，共三十六页2023/1/2929 主合取范式 主合取范式的定义及其唯一存在定理主合取范式的定义及其唯一存在定理定义定义 在给定公式的在给定公式的合取范式合取范式合取范式合取范式中中,若其字句若其字句都都都都是布尔大项是布尔大项,则称该范式

31、为主合取范式。则称该范式为主合取范式。定理定理 任意任意 n n个命题变元的个命题变元的非永真命题非永真命题非永真命题非永真命题公式公式A A都唯一存在与其逻辑等都唯一存在与其逻辑等值的主合取范式值的主合取范式 永真命题公式的主合取范式是空式永真命题公式的主合取范式是空式证明证明 首先求出首先求出A A的真值表的真值表,在在A A的真值表中的真值表中,对应对应A A取真值取真值0 0的行的行取布尔大项取布尔大项,使其二进制脚标与该行的真值指派一致使其二进制脚标与该行的真值指派一致.所有这些所有这些大项的合取式大项的合取式,即为即为A A的主合取范式的主合取范式.显然显然A A的主合取范式与的主

32、合取范式与A A逻逻辑等值且唯一辑等值且唯一,而永真式的主合取范式是空式而永真式的主合取范式是空式本讲稿第二十九页，共三十六页2023/1/2930求主合取范式的真值表法例例12 12 用真值表法求用真值表法求(P(Q(P(Q(P(Q(P(QR)R)R)R)(PQR)(PQR)(PQR)(PQR)的主的主合取范式合取范式解：解：设设G G(P(Q(P(QR)R)(PQR)(PQR)G=(P Q R)(P Q R)(P Q R)(P Q R)(P Q R)=1,2,3,5,6.本讲稿第三十页，共三十六页2023/1/2931例例13 13 用用等值推演法等值推演法求求(P(Q(P(QR)R)(P

33、QR)(PQR)的主合取范式的主合取范式解：解：(P(P(Q(Q(Q(QR)R)R)R)(PQR)(PQR)(PQR)(PQR)(P )(P )(P(P P P)(P P Q QR)(R)(P PQQ R R)(P(P Q Q)(Q QRR Q Q)()(Q QQQ R R)(P(P R R)(Q QRR R R)(Q)(Q R R R R)(P P P P Q Q Q QR)(R)(R)(R)(P P P PQQQQ R R R R)(P(P Q Q)(Q QR)(PR)(P R R)(Q)(Q R R)(P P P P Q Q Q QR)(R)(R)(R)(P P P PQQQQ R R

34、R R)(P(P QQ(R(R(R(R R)R)R)R)()(P(P(P(P P)P)P)P)Q QR)R)(P (P(Q(Q(Q(Q Q Q Q Q)R)R)(P(P(P(P P)P)P)P)QQ R)R)(PP QR)(QR)(PQPQ R)R)(P (P QR)(PQR)(P QQ R)(PQR)(PQ R)R)1,2,3,5,6 1,2,3,5,6.(.(分配分配)(Q Q R)R)(Q(Q R)R)(P P Q Q R)R)补补 缺缺本讲稿第三十一页，共三十六页2023/1/2932主析取范式与主合取范式3.3.主析取范式与主合取范式之间的关系主析取范式与主合取范式之间的关系主析取范

35、式和主合取范式是分别由布尔小项和布尔大项所组成主析取范式和主合取范式是分别由布尔小项和布尔大项所组成布尔小项和布尔大项之间有关系布尔小项和布尔大项之间有关系:m m m mi i i i M M M Mi i i i，i=1,2,i=1,2,2,2n n 主析取范式与主合取范式之间的关系还是主析取范式与主合取范式之间的关系还是相互补充相互补充的关系。的关系。即在给定命题公式的真值表中即在给定命题公式的真值表中,若其主析取范式由若其主析取范式由k k k k个布尔小项个布尔小项构成，则其主合取范式由构成，则其主合取范式由2 2 2 2n n n n-k-k-k-k个布尔大项构成个布尔大项构成.由

36、于编码方法统一于真值指派由于编码方法统一于真值指派,而且而且m mi i M Mi i,这就给我们提供了这就给我们提供了主主合取范式合取范式可以通过可以通过主析取范式的否定式主析取范式的否定式求取的方法求取的方法本讲稿第三十二页，共三十六页2023/1/2933主析取范式与主合取范式p设命题公式设命题公式A A中含有中含有n n个命题变元个命题变元,且且A A的主析取范式中含有的主析取范式中含有k k k k个布尔小项个布尔小项,则则 A A A A的主析取范式将含有另外的主析取范式将含有另外2 2 2 2n n n n-k-k-k-k个布尔个布尔小项小项p写出写出 A A的主析取范式的主析取

37、范式,简记为简记为 A AG,G,于是再从于是再从A A(A)A)G G便得便得A A的的主合取范式主合取范式.显然显然,G G恰由一一恰由一一否定否定全部未出全部未出现在现在A A中之中之布尔小项布尔小项(恰成为恰成为A A的的全部布尔大项全部布尔大项)的合取所构的合取所构成成p从从A A的主析取范式求其主合取范式的步骤：的主析取范式求其主合取范式的步骤：1)1)确定确定A A的主析取范式中未出现的布尔小项；的主析取范式中未出现的布尔小项；2)2)求出与求出与1)1)中小项的下标相同的布尔大项；中小项的下标相同的布尔大项；3)3)将将2)2)中大项做合取，即为中大项做合取，即为A A的主合取

38、范式的主合取范式.本讲稿第三十三页，共三十六页2023/1/2934主析取范式与主合取范式例例1414由由(P(Q(P(QR)R)(PQR)(PQR)的主析取范式求它的主合的主析取范式求它的主合取范式取范式从命题公式从命题公式A的主合取范式求的主合取范式求A的主析取范式其方法是相同的的主析取范式其方法是相同的本讲稿第三十四页，共三十六页2023/1/2935主范式的应用 判定问题判定问题 1)1)A AT T当且仅当当且仅当A A的主析取范式尽含全部的主析取范式尽含全部2 2n n个布尔小项个布尔小项(或当且或当且仅当仅当A A的主合取范式是空式的主合取范式是空式)；2)2)A AF F当且仅

39、当当且仅当A A的主合取范式尽含全部的主合取范式尽含全部2 2n n个布尔大项个布尔大项(或当或当且仅当且仅当A A的主析取范式是空式的主析取范式是空式)；3)3)A A既不与既不与T T也不与也不与F F等值则等值则A A为一般可满足式为一般可满足式.证明逻辑等值公式证明逻辑等值公式证明依据：证明依据：任一命题公式的主范式是唯一的，所以任一命题公式的主范式是唯一的，所以有相同主范有相同主范式的命题公式逻辑等值式的命题公式逻辑等值.本讲稿第三十五页，共三十六页2023/1/2936主范式的应用例例1515 用主范式方法证用主范式方法证PQPQ与与 PQPQ逻辑等值。逻辑等值。解解1 1：PQPQ PQPQ 具有相同的主合取范式，逻辑等值具有相同的主合取范式，逻辑等值.解解2 2：PQPQ的主析取范式是：的主析取范式是：(PP Q)Q)(PQ)PQ)(PQ)PQ)(m(m0000,m,m0101,m,m1111)PQ(MPQ(M1010)的主析取范式相同的主析取范式相同 逻辑等值逻辑等值本讲稿第三十六页，共三十六页