离散数学-命题逻辑3

最小联结词组,指可表示出其它所有联结词的最小联结词集合。如：，都可构成最小联结词组。例：写出PQ分别用，表示的等价式。解：(1)用，表示的等价式PQ(PQ)德.摩根定理,(2)用表示的等价式PQ(PQ)德.摩根定理(P)(Q)(PP)(QQ)(3)用表示的等价式PQ(PQ)(PQ)(PQ),对偶与范式,从上节可看到命题公式的最小联结词组为,或,，但实际上为了使用方便，命题公式常常同时包含,。我们认为这样的公式与存在对偶规律。定义1-7、1在给定的命题公式中，将联结词换成，将换成，若有特殊变元F和T亦相互取代，所得公式A*称为A的对偶式。显然A也是A*的对偶式。,例题1写出下列表达式的对偶式。（A）（B）（C）例题2求的对偶式,定理1-7.1设A和A*是对偶式，P1，P2，Pn是出现在A和A*中的原子变元，则定理1-7.2设P1，P2，Pn是出现在公式A和B中的所有原子变元，如果AB，则A*B*。,定义7、2一个命题公式称为合取范式，当且仅当它具有型式：其中A1，A2，An都是由命题变元或其否定所组成的析取式。定义7、3一个命题公式称为析取范式，当且仅当它具有型式：其中A1，A2，An都是由命题变元或其否定所组成的合取式。,注：任何一个命题公式，求它的合取范式或析取范式，可以通过下面三个步骤进行：（1）将公式中的联结词化归成，及。（2）利用德摩根律将否定符号直接到各个命题变元之前。（3）利用分配律、结合律将公式归约为合取范式或析取范式。例题3求的合取范式。例题4求的析取范式。,定义1-7、4n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。注：小项有如下几个性质：（1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1种指派情况下均为F。（2）任意两个不同小项的合取式永假。（3）全体小项的析取式永为真，记为：,定义1-7、5对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。定理1-7、3在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。例题5给定PQ，PQ和(PQ)，求这些公式的主析取范式。例题6求的主析取范式。,由上例我们看到，一个命题公式的主析取范式，可由两种方法构成。一是由公式的真值表得出，另一是由基本等价公式推出。其推演步骤可归纳为：（1）化归为析取范式。（2）除去析取范式中所有永假的析取项。（3）将析取式中重复出现的合取项和相同的变元合并。（4）对合取项补入没有出现的命题变元，即添加(PP)式，然后，应用分配律展开公式。,定义1-7、6n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。注：大项有如下性质：（1）每一个大项当其真值指派与编码相同时，其真值为F，在其余2n-1种指派情况下均为T。（2）任意两个不同大项的析取式为永真。,（3）全体大项的合取式永为假，记为：定义1-7、7对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。定理1-7、4在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。,例给定PQ，PQ和(PQ)，求这些公式的主合取范式解：,注意:T对应变元的否定，F对应变元,注：一个公式的主合取范式，亦可用基本等价式推出，其推演步骤为：（1）化归为合取范式。（2）除去合取范式中所有为永真的合取项。（3）合并相同的析取项和相同的变元。（4）对析取项补入没有出现的命题变元，即添加(PP)式，然后，应用分配律展开公式。例题7化为主合取范式。,BACK,注意:任何式子的主析取范式和主合取范式只需要求得其一即可.,例：求（PQ）（）主析取范式和主合取范式由前例，该式的主合取范式为()()()()其编码为,即,所以（PQ）（）（）（）（）（）=，=（）（）（）（）,本节结束,例1解：这些表达式的对偶式是：（A）(PQ)R（B）(PQ)F（C）(PQ)(P(QS)