离散数学-命题逻辑3.ppt

《离散数学-命题逻辑3.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最小联结词组指可表示出其它所有联结词的最小联结词集合。如：{┒，∨}，{┒，∧}，{↑}，{↓}都可构成最小联结词组。例：写出P∨Q分别用{┒，∧}，{↑}，{↓}表示的等价式。解：(1)用{┒，∧}表示的等价式P∨Q⇔┒(┒P∧┒Q)德.摩根定理(2)用{↑}表示的等价式P∨Q⇔┒(┒P∧┒Q)德.摩根定理⇔(┒P)↑(┒Q)⇔(P↑P)↑(Q↑Q)(3)用{↓}表示的等价式P∨Q⇔┒(P↓Q)⇔(P↓Q)↓(P↓Q)对偶与范式从上节可看到命题公式的最小联结词组为{┒,∨}或{┒,∧}，但实际上为了使用方便，命题公式常常同时包含{┒,∨,∧}。我们认为这样的公式∨与∧存在对偶规律。定义1-

2、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中的所有原子变元，如果A⇔B，则A*⇔B*。定义7、2一个命题公式称为合取范式，当且仅当它具有型式：其中A1，A2，…An都是由命题变元或其否定所组成的析取式。定义7、3一个命题公式称为析取范式，当且仅当它具有型式：其中A1，A2，…An都是由命题变元或其

3、否定所组成的合取式。注：任何一个命题公式，求它的合取范式或析取范式，可以通过下面三个步骤进行：（1）将公式中的联结词化归成∧，∨及┒。（2）利用德·摩根律将否定符号┒直接到各个命题变元之前。（3）利用分配律、结合律将公式归约为合取范式或析取范式。例题3求的合取范式。例题4求的析取范式。定义1-7、4n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。注：小项有如下几个性质：（1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1种指派情况下均为F。（2）任意两个不同小项的合取式永假。（3）全体小项的析取式永为真，记为：定义1-

4、7、5对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。定理1-7、3在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。例题5给定P→Q，P∨Q和┒(P∧Q)，求这些公式的主析取范式。例题6求的主析取范式。由上例我们看到，一个命题公式的主析取范式，可由两种方法构成。一是由公式的真值表得出，另一是由基本等价公式推出。其推演步骤可归纳为：（1）化归为析取范式。（2）除去析取范式中所有永假的析取项。（3）将析取式中重复出现的合取项和相同的变元合并。（4）对合取项补入没有出现的命题变元，即添加(P∨┒P)式，然后，应用分配律

5、展开公式。定义1-7、6n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。注：大项有如下性质：（1）每一个大项当其真值指派与编码相同时，其真值为F，在其余2n-1种指派情况下均为T。（2）任意两个不同大项的析取式为永真。（3）全体大项的合取式永为假，记为：定义1-7、7对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。定理1-7、4在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。例给定P→Q，P∨Q和┒(P∧Q)，求这些公式的主合取范式解：PQP→QP∨Q┒(

6、P∧Q)TTTTFTFFTTFTTTTFFTFT注意:T对应变元的否定，F对应变元注：一个公式的主合取范式，亦可用基本等价式推出，其推演步骤为：（1）化归为合取范式。（2）除去合取范式中所有为永真的合取项。（3）合并相同的析取项和相同的变元。（4）对析取项补入没有出现的命题变元，即添加(P∧┒P)式，然后，应用分配律展开公式。例题7化为主合取范式。BACK注意:任何式子的主析取范式和主合取范式只需　要求得其一即可.例：求（PQ）（ＰＲ）主析取范式和主合取范式由前例，该式的主合取范式为(ＰＱＲ)(ＰＱＲ)(ＰＱＲ)(ＰＱＲ)其编码为１０１,１００,０１０

7、,０００即０,２,４,５所以（PQ）（ＰＲ）（ＰＱＲ）（ＰＱＲ）（ＰＱＲ）（ＰＱＲ）=０，２，４，５１，３，６，７=（ＰＱＲ）（ＰＱＲ）（ＰＱＲ）（ＰＱＲ）本节结束例1解：这些表达式的对偶式是：（A）(P∧Q)∨R（B）(P∨Q)∧F（C）┒(P∧Q)∨(P∧┒(Q∨┒S))例2解：因为P↑Q⇔┒(P∧Q)，故P↑Q的对偶式为┒(P∨