四川大学计算机学院 离散数学(第4、5讲).pptVIP

* 计算机学院 * mi=～Mi； Mi=～mi； i=0,1,2,…,2n-1 Mi∨Mj=T； mi∧mj=F； i≠j； i,j∈{0,1,2,…,2n-1}  * 计算机学院 * 极小项与极大项的性质（续） 极大项取值0“当且仅当”：如果极大项中出现的是原子本身，则原子赋值为0；如果出现的是原子的否定，则原子赋值为1。 当一个极大项在一种解释下取值0时，其余极大项在同一解释下取值1。 P Q P∨Q P∨～Q ～P∨Q ～P∨～Q 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 * 计算机学院 * 极小项取值1 “当且仅当”：如果极小项中出现的是原子本身，则原子赋值为1；如果出现的是原子的否定，则原子赋值为0。 当一个极小项在一种解释下取值1时，其余极小项在同一解释下取值0。 P Q P∧Q P∧～Q ～P∧Q ～P∧～Q 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 范式存在定理 * 计算机学院 * 定理1.7 在命题公式的真值表中，使公式取值0时的解释所对应的全部极大项的合取式，是该公式的主合取范式。 定理1.8 在命题公式的真值表中，使公式取值1时的解释所对应的全部极小项的析取式，是该公式的主析取范式。 * 计算机学院 * 利用真值表求主析（合）取范式 例1-5.3设 G=(P→Q)?R，求出它的主析取范式和主合取范式。 求主析（合）取范式的方法有： 1、 真值表技术法 2、 公式转换法 * 计算机学院 * 解：首先列出其真值表如下： P Q R P→Q (P→Q)?R 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 例1-5.3（续） * 计算机学院 * 1)、求公式的主析取范式 P Q R (P→Q）?R 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 例1-5.3（续） ～P∧～Ｑ∧Ｒ 极小项 极小项 极小项 极小项 ～P∧Ｑ∧Ｒ P∧?Ｑ∧～Ｒ P∧Ｑ∧Ｒ * 计算机学院 * 将极小项全部进行析取后，可得到相应的主析取范式： G=（Ｐ→Ｑ）?Ｒ =（┐P∧┐Ｑ∧Ｒ）∨（┐P∧Ｑ∧Ｒ）∨（Ｐ∧┐Ｑ∧┐Ｒ）∨（Ｐ∧Ｑ∧Ｒ） 例1-5.3（续） * 计算机学院 * 2)、求公式的主合取范式 P Q R (P→Q)?R 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 例1-5.3（续） 极大项 极大项 极大项 极大项 P∨Ｑ∨Ｒ P∨～Ｑ∨Ｒ ～P∨Ｑ∨～Ｒ ～P∨～Ｑ∨Ｒ * 计算机学院 * 将极大项全部进行合取后，可得到相应的主合取范式： G=（Ｐ→Ｑ）?Ｒ = （P∨Ｑ∨Ｒ）∧（P∨～Ｑ∨Ｒ）∧（～Ｐ∨Ｑ∨～Ｒ）∧（～Ｐ∨～Ｑ∨Ｒ） 例1-5.3（续） * 计算机学院 * 公式转换法 （1）利用等价公式中的等价式和蕴涵式将公式中的→、?用联结词～、∧、∨来取代； （2）利用德?摩根定律将否定号～移到各个命题变元的前端； （3）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。 （4）在析取范式的短语和合取范式的子句中，如同一命题变元出现多次，则将其化成只出现一次。 （5）去掉析取范式中所有永假式的短语和合取范式中所有永真式的子句，即去掉短语中含有形如P∧～P的子公式和子句中含有形如P∨～P的子公式。 * 计算机学院 * （6）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元P ，则可用公式： （～Ｐ∨Ｐ）∧Q=Q 将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项； （7）若合取范式的某一个子句中缺少该命题公式中所规定的命题变元P ，则可用公式： （～Ｐ∧Ｐ）∨Q=Q 将命题变元P补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是标准的极大项。 （8）利用幂等律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。 * 计算机学院 * 利用公式的等价求G＝(P→Q)∧R的主合取范式和主析取范式。 解：G＝(P→Q)∧R＝(～P∨Q)∧R（蕴涵） ＝(～P∨Q∨(R∧～R))∧