离散数学1.7课件

1、离散数学,1,一、对偶 最小联结词组 大部分等价公式成对出现 定义 在给定的命题公式中，将联结词换成，将换成 ，若有特殊变元F和T亦相互取代，所得公式A*称为A的对偶式。 显然，A也为A*的对偶式。,17 对偶与范式,离散数学,2,例：,例：写出下列表达式的对偶式 (P Q) R (P Q) R (P Q) T (P Q) F (P Q) (P (Q S) (P Q) (P (Q S),离散数学,3,定理设A和A*是对偶式， P1,P2,Pn是出现在A和A*中的原子变元，则 A（ P1、P2、Pn ） A*（ P1、P2、 Pn） A（P1、P2、 Pn） A*（ P1、P2、Pn ）,定理,

2、定理设P1,P2,Pn是出现在公式A和B中的所有原子变元，如果A B，则A* B*,离散数学,4,由于同一个命题公式可以有不同的表达形式，而不同的表达形式可以显示很不同的特征。某种特定类型的表达可以显示出从某一角度考虑极为重要的性质。但上述的不同表达形式却对我们研究命题演算带来了一定的困难。因此，从理论上讲，有必要对命题公式的标准形式问题进行一个深入的研究，使公式达到规范化。为此，引入范式这一概念，范式给各种千变万化的公式提供了一个统一的表达形式，同时，范式的研究对命题演算的发展起了极其重要的作用。,二、范式,离散数学,5,定义 一个命题公式称为合取范式，当且仅当它具有形式： A1A2An (

3、n1) 其中A1，A2，An都是由命题变元或其否定所组成的析取式。 例：P，P，PQR，(PQ)(PQ)，PQR等都是合取范式。,合取范式,离散数学,6,定义 一个命题公式称为析取范式，当且仅当它具有形式： A1A2An (n1) 其中A1，A2，An都是由命题变元或其否定所组成的合取式。 例： P，P，PQR，(PQ)(PQ)，PQR等都是析取范式。,析取范式,离散数学,7,任何一个命题公式，求它的合取范式和析取范式，可以通过下面三个步骤进行： 1）简化联结词：将公式中的联结词化归成，及。 2）否定深入：利用德摩根律将直接移到各个命题变元之前。 3）归约：利用分配律、结合律归约为合取范式或析

4、取范式。,求合取范式和析取范式,离散数学,8,例,求公式：(PQ)R的析取范式和合取范式。,解：(PQ)R (PQ)R (PQ)R析取范式 (PQ)R (PQ)R (PR)(QR)合取范式,离散数学,9,定义 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 例：P32 性质： 1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2n1种指派情况下均为F。 2）任意两个不同小项的合取式永假。 3）全体小项的析取式永真。,小项,离散数学,10,mimj=0；ij；,j0,1,2,2n-1,离散数学,11,定义 对于给定的命题公式，如

5、果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。 定义 在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。,主析取范式,离散数学,12,1）公式的真值表 2）基本等价公式推出 步骤： 化归为析取范式 除去析取范式中所有永假的析取项。 将析取式中重复出现的析取项和相同的变元合并。 对析取项补入没有出现的命题变元，即添加（P P）式，然后，应用分配律展开公式。,求一个命题公式的主析取范式的方法：,离散数学,13,定义 n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 性质： 1）每一个

6、大项当其真值指派与编码相同时，其真值为F，在其余2n1种指派情况下均为T。 2）任意两个不同大项的析取式永永真。 3）全体大项的合取式永假。,大项,离散数学,14,MiMj=1；ij；i,j0,1,2,2n-1,离散数学,15,定义 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。 定义 在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。,主合取范式,离散数学,16,1）公式的真值表 2）基本等价公式推出 步骤： 化归为合取范式 除去合取范式中所有永真的合取项。 合并相同的合取项和相同的变元。 对合取项补入没有出现的

7、命题变元，即添加（P P）式，然后，应用分配律展开公式。,求一个命题公式的主合取范式的方法：,离散数学,17,编码,离散数学,18,含有n个命题变元的小项mi和大项Mi，可以看作含有n个命题变元的公式，因此共有2n个不同的指派。,这2n个不同的指派中，有且仅有一个指派使得mi为1，即对mi中以变元形式出现的变元指派为1，以变元的否定形式出现的变元指派为0； 这2n个不同的指派中，有且仅有一个指派使得Mi为0，即对Mi中以变元形式出现的变元指派为0，以变元的否定形式出现的变元指派为1。,离散数学,19,小项 mi,mi为1的 指派I,大项 Mi,Mi为0的 指派I,指派I,I下为1的 小项mi,

8、指派I,I下为0的 大项Mi,离散数学,20,例 设G=(PQ)R，求出它的主析取范式和主合取范式。,解：首先列出其真值表如下：,例,离散数学,21,(1).求主析取范式 (a).从真值表知，该公式G恰有三个指派使其公式取值为“真”。为此，选出已给公式取值为“1”所在行所对应的变元取值如下： 2.0014.0118.111 (b).将上面选出的各行变元取值“还原”成相应的原子命题符号，值为“1”者“还原”成原变量，值为“0”者“还原”成原变量的否定，并构成相应的小项。则有： 2.PQR该小项恰有唯一的一组指派0，0，1使其取值为“真”。 4.PQR该小项恰有唯一的一组指派0，1，1使其取值为“

9、真”。 8.PQR该小项恰有唯一的一组指派1，1，1使其取值为“真”。,续,离散数学,22,(c).则上述小项的析取为对应的主析取范式。 G(PQ)R (PQR)(PQR)(PQR) (2).求主合取范式 (a).从真值表知，该公式G恰有五个指派使其公式取值为“假”。为此，选出已给公式取值为“0“所在行所对应的变元之值如下： 1.0 0 03.0 1 05.1 0 06.1 0 17.1 1 0 (b).将上面选出的各行变元之值“还原”成相应的原子命题符号，值为“1”者“还原”成原变量的否定，值为“0”者“还原”成原变量，并构成相应的大项。则有 1.PQR该大项恰有唯一的一组指派0，0，0使其

10、取值为“假”。,续,离散数学,23,3.PQR该大项恰有唯一的一组指派0，1，0使其取值为“假”。 5.PQR该小项恰有唯一的一组指派1，0，0使其取值为“假”。 6.PQR该大项恰有唯一的一组指派1，0，1使其取值为“假”。 7.PQR该大项恰有唯一的一组指派1，1，0使其取值为“假”。 (c).则上述大项的合取为对应的主合取范式。 G=(PQ)R (PQR)(PQR)(PQR) (PQR)(PQR)。,续,离散数学,24,例:利用公式的等价求G(PQ)R的主析取范式和主合取范式。 解：G=(PQ)R (PQ)R (PQ(RR)(PP)(QQ)R) (PQR)(PQR) (PQR)(PQR)

11、 (PQR)(PQR) (PQR)(PQR)(PQR) (PQR)(PQR) 主合取范式,例,离散数学,25,G(PQ)R (PQ)R (PR)(QR) (P(QQ)R)(PP)QR) (PQR)(PQR) (PQR)(PQR) (PQR)(PQR)(PQR) 主析取范式,续,离散数学,26,若为G的主析取范式，则 为G的主析取范式，其中： mji(i=1,2,2n-k)是mi(i=0,1,2n-1)中去掉mli(i=1,2,k)后剩下的小项，则:,为G的主合取范式。,主范式间转换,离散数学,27,若为G的主合取范式，则 为G的主合取范式，其中： Mji(i=1,2,2n-k)是Mi(i=0,1,2n-1)中去掉Mli(i=1,2,k)后剩下的大项，则:,为G的主析取范式。,主范式间转换,离散数学,28,设G(PQ)(PR)(QR)，求其对应的主析取范式和主合取范式。,解：G(PQ)(PR)(QR) (PQ(RR) (P(QQ)R)(PP)QR) (PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (PQR)(PQR) (PQR)(PQR) m1m3m6m7-主析取范式,例,离散数学,29,Gm0m2m4m5 GG(m0m2m4m5) m0m2m4m5 M0M2M4M5 =(PQR)(PQR) (PQR)(PQR) -主合取范式,续,离散数学,30,任