LSSX-1-3.ppt

《LSSX-1-3.ppt》由会员分享，可在线阅读，更多相关《LSSX-1-3.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、联结词是否够用？每种联结词对应一种四个T或F的组合，总共可以有24=16种组合，似乎需要16种联结词才够用。事实上，我们定义的这九种就够用了。请看P27 表1-6.5最小联结词组最小联结词组o指可表示出其它所有指可表示出其它所有联结词的最小的最小联结词集合。如：集合。如：，都可构成都可构成最小最小联结词组。最小联结词组o例：写出例：写出P QP Q分分别用用，表示的等价式。表示的等价式。解：解：(1)(1)用用，表示的等价式表示的等价式 P Q P Q (P Q)(P Q)德德.摩根定理摩根定理(2)(2)用用 表示的等价式表示的等价式 P Q P Q (P Q)(P Q)德德.摩根定理摩根定

2、理 (P)P)(Q)Q)(P P P)P)(Q Q Q)Q)(3)(3)用用 表示的等价式表示的等价式 P Q P Q (P(P Q)Q)(P P Q)Q)(P P Q)Q)最小联结词组命命题：最小：最小联结词组应为，或或，亦可，亦可以以为 或或。证明：明：1）用）用这些些联结词组可以表示其它的可以表示其它的联结词。2）用）用，以及以及，不能表示其它的不能表示其它的联结词。最小联结词组 不能表示不能表示 ，因因为含有二元含有二元联结词的命的命题公式不能用公式不能用仅含含一元一元联结词的命的命题公式等价代公式等价代换。，或或，不能表示不能表示 因因为如果有如果有 P(P Q)若若对右右边所出所出

3、现的的变元都指派真元都指派真值为，由，由，定定义可知其真可知其真值必必为，而左，而左边的真的真值为，矛盾。矛盾。对偶与范式对偶与范式o命命题公式的最小公式的最小联结词组为,或或,，但，但实际上上为了使用方便，命了使用方便，命题公式常常同公式常常同时包含包含,。我。我们认为这样的公式的公式 与与 存在存在对偶偶规律。律。o定定义1-7、1 在在给定的命定的命题公式中公式中，将，将联结词 换成成 ，将，将 换成成 ，若有特殊，若有特殊变元元F和和T亦相互取代，亦相互取代，所得公式所得公式A*称称为A的的对偶式。偶式。o显然然A也是也是A*的的对偶式。偶式。例题1 写出下列表达式的写出下列表达式的对

4、偶式。偶式。（A）（B）（C）例1 解：解：这些表达式的些表达式的对偶式是：偶式是：（A）(PQ)R （B）(PQ)F（C）(PQ)(P(QS)例题2 求求 的的对偶式。偶式。解：因解：因为PQ(PQ)，故，故PQ 的的对偶式偶式为(PQ)，即，即 PQ。同理。同理PQ的的对偶式是偶式是PQ。定理1-7.1 设A和和A*是是对偶式，偶式，P1，P2，Pn是是出出现在在A和和A*中的原子中的原子变元，元，则 证明：由德明：由德.摩根定律摩根定律 (P Q)P Q (P Q)P Q故故 A(P1,P2,Pn)A*(P1,P2,Pn)同理同理A(P1,P2,Pn)A*(P1,P2,Pn)定理1-7.

5、2 设P1，P2，Pn是出是出现在公式在公式A和和B中中的所有原子的所有原子变元，如果元，如果ABAB，则A*B*A*B*。定义7、2 一个命一个命题公式称公式称为合取范式，当且，当且仅当它具有型式：当它具有型式：其中其中A1，A2，An都是由命都是由命题变元或其否元或其否定所定所组成的析取式。成的析取式。例(P QR)(PQ)Q是一个合取范式。(PQ)是否是合取范式？(PQ)是否是合取范式？是不是 定义7、3 一个命一个命题公式称公式称为析取范式，当且，当且仅当它具有型式：当它具有型式：其中其中A1，A2，An都是由命都是由命题变元或其否元或其否定所定所组成的合取式。成的合取式。例 P(P

6、QR)(PQ)是一个析取范式。(PQ)是否是析取范式？(PQ)是否是析取范式？是不是注：任何一个命题公式，求它的合取范式或析取范式，可以通过下面三个步骤进行：（1）将公式中的）将公式中的联结词化化归成成，及及。（2）利用德）利用德摩根律将否定符号摩根律将否定符号直接移到各个命直接移到各个命题变元之前。元之前。（3）利用分配律、）利用分配律、结合律将公式合律将公式归约为合取范式或析合取范式或析取范式。取范式。例题3 求求 的合取范式。的合取范式。例3 解：解：例题4 求求 的析取范式。的析取范式。例4 解：因解：因为有公式有公式故故 定义1-7、4 n个命个命题变元的合取式，称作元的合取式，称作

7、布尔合取或小项，其中每个，其中每个变元与它的否元与它的否定不能同定不能同时存在，但两者必存在，但两者必须出出现且且仅出出现一次一次。例如：例如：两个命两个命题变元元P、Q，其小，其小项为 P Q，P Q，P Q，P Q三个命三个命题变元元P、Q、R，其小，其小项为 P Q R，P Q R，PQ R，PQR，P Q R，P QR，PQ R，P Q R一般说来，一般说来，n个命题变元共有个命题变元共有2n个小项。个小项。可以得出可以得出结论：（1）没有两个小）没有两个小项是等价的是等价的（2）每个小）每个小项只只对应P和和Q的一的一组真真值指派，指派，使得使得该小小项的真的真值为T。记作：作：m1

8、1=P Q，m10=P Q，m01=P Q，m00=P Q总结出出规律：律：在小在小项 中，中，注：小注：小项有如下几个性有如下几个性质：（1）每一个小）每一个小项当其真当其真值指派与指派与编码相同相同时，其真，其真值为T，在其余，在其余2n-1种指派情况种指派情况下均下均为F。（2）任意两个不同小）任意两个不同小项的合取式永假。的合取式永假。（3）全体小）全体小项的析取式永的析取式永为真，真，记为：o定定义1-7、5 对于于给定的命定的命题公式，如果公式，如果有一个等价公式，它有一个等价公式，它仅由由小小项的析取的析取所所组成，成，则该等价式称作原式的等价式称作原式的主析取范主析取范式式。o

9、定理定理1-7、3 在真在真值表中，一个公式的表中，一个公式的真真值为T的指派的指派所所对应的的小小项的析取的析取，即，即为此公式的主析取范式。此公式的主析取范式。例：求(P Q)R的主析取范式。解：用真值表法：PQRP Q(PQ)RTTTTTTTFTFTFTFTTFFFTFTTTTFTFTFFFTTTFFFTF上式的主析取范式为：(PQR)(PQR)(PQR)(PQR)(PQR)m111 m101 m100 m011 m001=1,3,4,5,7PQRP Q(PQ)RTTTTTTFTFTTFFFTFTTTTFFTTTo例例题5 给定定PQ，P Q和和(P Q)，求求这些公式的主析取范式。些公

10、式的主析取范式。例5 解：三公式的真解：三公式的真值表如下表如下图所示，故所示，故PQPQ P Q(P Q)TTTTFTFFTTFTTTTFFTFTo例例题6 求求 的主析取的主析取范式。范式。例6 解：原式解：原式o由上例我由上例我们看到，一个命看到，一个命题公式的主析取范式，可公式的主析取范式，可由两种方法构成。由两种方法构成。一是由公式的真由公式的真值表得出，表得出，另一是由基本等价公式推出。其推演步由基本等价公式推出。其推演步骤可可归纳为：（1）化）化归为析取范式。析取范式。（2）除去析取范式中所有永假的析取）除去析取范式中所有永假的析取项。（3）将析取式中重复出）将析取式中重复出现的

11、合取的合取项和相同的和相同的变元合并。元合并。（4）对合取合取项补入没有出入没有出现的命的命题变元，即添加元，即添加(PP)式，然后，式，然后，应用分配律展开公式。用分配律展开公式。定义1-7、6 n个命个命题变元的析取式，称作元的析取式，称作布尔析取或大项，其中每个，其中每个变元与它的否定元与它的否定不能同不能同时存在，但两者必存在，但两者必须出出现且且仅出出现一一次。次。例如：两个命例如：两个命题变元元P、Q，其大，其大项为 P Q，PQ，P Q，PQ 三个命三个命题变元元P、Q、R，其大，其大项为P Q R，P Q R，P Q R，P Q R，P Q R，P Q R，P Q R，P Q

12、R一般说来，一般说来，n个命题变元共有个命题变元共有2n个大项个大项。也可以得出也可以得出结论：（1）没有两个大）没有两个大项是等价的是等价的（2）每个大）每个大项只只对应P和和Q的一的一组真真值指派，指派，使得使得该大大项的真的真值为F。记作：作：M00=P Q，M01=P Q，M10=P Q，M11=PQ总结出出规律：律：在大在大项 中，中，注：注：大项有如下性质大项有如下性质：（1）每一个大项当其真值指派与编码相同时，其）每一个大项当其真值指派与编码相同时，其真值为真值为F，在其余，在其余2n-1种指派情况下均为种指派情况下均为T。（2）任意两个不同大项的析取式为永真。）任意两个不同大项

13、的析取式为永真。（3）全体大项的合取式永为假，记为：）全体大项的合取式永为假，记为：o定定义1-7、7 对于于给定的命定的命题公式，如果有一个公式，如果有一个等价公式，它等价公式，它仅由大由大项的合取所的合取所组成，成，则该等等价式称作原式的价式称作原式的主合取范式。o定理1-7、4 在真在真值表中，一个公式的表中，一个公式的真值为F的指派所的指派所对应的大的大项的合取，即的合取，即为此公式的主此公式的主合取范式。合取范式。oo注：一个公式的主合取范式，亦可用基本等价注：一个公式的主合取范式，亦可用基本等价注：一个公式的主合取范式，亦可用基本等价注：一个公式的主合取范式，亦可用基本等价式推出，

14、其推演步式推出，其推演步式推出，其推演步式推出，其推演步骤为骤为：（1）化）化归为合取范式。（2）除去合取范式中所有）除去合取范式中所有为永真的合取永真的合取项。（3）合并相同的析取）合并相同的析取项和相同的和相同的变元。元。（4）对析取析取项补入没有出入没有出现的命的命题变元，即添加元，即添加(PP)式，然后，式，然后，应用分配律展开公式。用分配律展开公式。例：求例：求(P Q)(PQ)的主合取范式的主合取范式解：用真解：用真值表法：表法：PQ PQPQ(PQ)(PQ)TTFFFTFFTTFTTFTFFFFF原式原式(PQ)(P Q)M11 M00=0，3例：求例：求(P Q)R的主合取范式

15、。的主合取范式。解：用等价公式推解：用等价公式推导法：法：原式原式 (P Q)R(PQ)R(P R)(Q R)(P R (Q Q)(Q R(PP)(P Q R)(PQ R)(PQ R)(PQ R)(P Q R)(PQ R)(PQ R)=0,2,6例：求例：求(P Q)R的主析取范式。的主析取范式。解：用等价公式推解：用等价公式推导法：法：原式原式 (P Q)R(PQ)R(PQ(RR)(PP)(QQ)R)(PQ R)(PQR)(P Q R)(P Q R)(PQ R)(PQ R)(PQ R)(PQR)(P Q R)(P Q R)(PQ R)=1,3,4,5,7大家可以看到，当用等价公式推大家可以看到，当用等价公式推导的方法求得的方法求得一公式的主析取范式或主合取范式一公式的主析取范式或主合取范式时，可以方便地，可以方便地用用编码求得另一种主范式，比真求得另一种主范式，比真值表法快一些。表法快一些。求求 (PQ)的主析取范式，再用的主析取范式，再用编码大大项写出写出主合取范式。主合取范式。解：原式解：原式PQ m10=2 原式原式 M00 M01 M11 (P Q)(PQ)(PQ)=0,1,3例例题7 化化 为主合取范式。主合取范式。例7 解：解：