Email：fws365@scu.edu.cn 2019年1月2日星期三 离散　　数学 计算机学院 冯伟森 Email：fws365@scu.edu.cn 2019年1月2日星期三.

Presentation on theme: "Email：fws365@scu.edu.cn 2019年1月2日星期三 离散　　数学 计算机学院 冯伟森 Email：fws365@scu.edu.cn 2019年1月2日星期三."— Presentation transcript:

1 Email：fws365@scu.edu.cn 2019年1月2日星期三
离散　　数学 计算机学院 冯伟森 2019年1月2日星期三

2 主要内容 1、范式 析取范式、合取范式、主析取（主合取）范式、极小项、极大项 2、求主析取范式和主合取范式的方法
1）真值表法 2）公式转换法 2019/1/2 计算机学院

3 1.5 命题公式的范式表示 问题：这样的标准 形式存在吗？ 是否唯一？
一个命题公式有无数多个和它等价的命题公式，用真值表或等价变换证明它们是否等价，往往比较困难，甚至连计算机也无法解决。 要解决这个问题，我们引入范式(公式的标准型)的概念。 范式——全名叫规范型式,又叫标准型式,正规型式。把公式进行标准化，正规化，就叫对公式求范式。 问题：这样的标准 形式存在吗？ 是否唯一？ 2019/1/2 计算机学院

4 定义1.16 命题变元或命题变元的否定称为句节。 有限个句节的析取式称为子句； 有限个句节的合取式称为短语。
有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。 2019/1/2 计算机学院

5 例1-5.1 Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 Ｐ∨Ｑ∨～Ｒ是子句、析取范式、合取范式；
～Ｐ∧Ｑ∧Ｒ是短语、析取范式、合取范式； （Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 （Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 2019/1/2 计算机学院

6 句子（Ｐ∨Ｑ∨～Ｒ）仅是子句、合取范式， 句子（～Ｐ∧Ｑ∧Ｒ）仅是短语、析取范式； 句子Ｐ∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既
不是析取范式也不是合取范式。但转换后： Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述两式的右端即是析取范式和合取范式。 2019/1/2 计算机学院

7 结论 从上述定义和例子可以得出如下关系： 单个的句节是一个子句、短语、析取范式、合取范式。 单个的子句是合取范式、
单个的短语是析取范式。 若省略外层括号，单个的子句也是析取范式，单个的短语也是合取范式。 析取范式、合取范式仅含联结词～ 、∧、∨，且～仅出现在命题变元前。 2019/1/2 计算机学院

8 定理1.6 任何命题公式都存在与之等价的合取范式与析取范式。
定理1.6 任何命题公式都存在与之等价的合取范式与析取范式。 证明： （1）利用等价公式中的等价式和蕴涵式将公式中的→、用联结词～ 、∧、∨来取代； （2）利用德摩根定律将否定号┐移到各个命题变元的前端； （3）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。 2019/1/2 计算机学院

9 例1-5.2 求（P∧（Q→R））→S的合取范式 解：（P∧（Q→R））→S  （P∧（～Q∨R））→S  ～（P∧（～Q∨R））∨S
（～P∨S）∨（Q∧～R）  （ ～P∨S∨Q）∧（ ～P∨S∨～R） 2019/1/2 计算机学院

10 主析取范式 一个公式的范式是不是唯一的呢？ 如 P∨（Q∧R） 由于范式不唯一， ∴直接用范式判断命题间等价还是不方便。
（P∨Q）∧（P∨R） （（P∨Q）∧P）∨（（P∨Q）∧R） （P∧P）∨（P∧Q)∨(P ∧ R）∨（Q∧R） 由于范式不唯一， ∴直接用范式判断命题间等价还是不方便。 因此需要对公式进一步规范化，即求公式的 主范式。 2019/1/2 计算机学院

11 定义1.17 在n个变元的短语中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则称这种短语为极小项。
由有限个极小项组成的析取式称为主析取范式。 以下是由两个原子构成的极小项的真值表 P Q P∧Q P∧～Q ～P∧Q ～P∧～Q 1 2019/1/2 计算机学院

12 ①任何两个命题公式（极小项）都不是相互等价的，并且只有一组真值指派，使得该公式的值为T。
由真值表可知： ①任何两个命题公式（极小项）都不是相互等价的，并且只有一组真值指派，使得该公式的值为T。 ②2个命题变元有2² = 4种不同的组合（极小项） 对于n个命题变元，共有2n个不同的极小项，记为 。 2019/1/2 计算机学院

13 极小项 公式 成真赋值 名称 0 0 0 1 1 0 1 1 2019/1/2 计算机学院

14 主合取范式 定义1.17 在n个变元的子句中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则这种子句称为极大项。
由有限个极大项组成的合取式称为 主合取范式。 以下是由两个原子构成的极大项的真值表 P Q P∨Q P∨～Q ～P∨Q ～P∨～Q 1 2019/1/2 计算机学院

15 由真值表可知：①任何两个极大项都不是相互等价的且只有一组真值指派使其值为F。
②2个命题变元有2² = 4种不同的组合（极大项）对于n个命题变元，共有2n个不同的极大项，记为 。 2019/1/2 计算机学院

16 极大项 公式 成假赋值 名称 0 0 0 1 1 0 1 1 2019/1/2 计算机学院

17 极小项与极大项的性质 没有两个不同的极小项是等价的，且每个极小项只有一组真值指派，使该极小项的真值为真；
没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假； 2019/1/2 计算机学院

18 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}  2019/1/2 计算机学院

19 极小项与极大项的性质（续） 极大项取值0“当且仅当”：如果极大项中出现的是原子本身，则原子赋值为0；如果出现的是原子的否定，则原子赋值为1。
当一个极大项在一种解释下取值0时，其余极大项在同一解释下取值1。 P Q P∨Q P∨～Q ～P∨Q ～P∨～Q 1 2019/1/2 计算机学院

20 极小项取值1 “当且仅当”：如果极小项中出现的是原子本身，则原子赋值为1；如果出现的是原子的否定，则原子赋值为0。
当一个极小项在一种解释下取值1时，其余极小项在同一解释下取值0。 P Q P∧Q P∧～Q ～P∧Q ～P∧～Q 1 2019/1/2 计算机学院

21 范式存在定理 定理1.7 在命题公式的真值表中，使公式取值0时的解释所对应的全部极大项的合取式，是该公式的主合取范式。
定理1.7 在命题公式的真值表中，使公式取值0时的解释所对应的全部极大项的合取式，是该公式的主合取范式。 定理1.8 在命题公式的真值表中，使公式取值1时的解释所对应的全部极小项的析取式，是该公式的主析取范式。 2019/1/2 计算机学院

22 例1-5.3设 G=(P→Q)R，求出它的主析取范式和主合取范式。
利用真值表求主析（合）取范式 求主析（合）取范式的方法有： 1、 真值表技术法 2、 公式转换法 例1-5.3设 G=(P→Q)R，求出它的主析取范式和主合取范式。 2019/1/2 计算机学院

23 例1-5.3（续） 解：首先列出其真值表如下： P Q R P→Q (P→Q)R 1 2019/1/2 计算机学院

24 例1-5.3（续） 1)、求公式的主析取范式 P Q R (P→Q）R 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 极小项 ～P∧～Ｑ∧Ｒ 极小项 ～P∧Ｑ∧Ｒ 极小项 P∧Ｑ∧～Ｒ 极小项 P∧Ｑ∧Ｒ 2019/1/2 计算机学院

25 例1-5.3（续） 将极小项全部进行析取后，可得到相应的主析取范式： G=（Ｐ→Ｑ）Ｒ
=（┐P∧┐Ｑ∧Ｒ）∨（┐P∧Ｑ∧Ｒ）∨（Ｐ∧┐Ｑ∧┐Ｒ）∨（Ｐ∧Ｑ∧Ｒ） 2019/1/2 计算机学院

26 例1-5.3（续） 2)、求公式的主合取范式 P Q R (P→Q)R 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 极大项 P∨Ｑ∨Ｒ 极大项 P∨～Ｑ∨Ｒ 极大项 ～P∨Ｑ∨～Ｒ 极大项 ～P∨～Ｑ∨Ｒ 2019/1/2 计算机学院

27 例1-5.3（续） 将极大项全部进行合取后，可得到相应的主合取范式： G=（Ｐ→Ｑ）Ｒ
= （P∨Ｑ∨Ｒ）∧（P∨～Ｑ∨Ｒ）∧（～Ｐ∨Ｑ∨～Ｒ）∧（～Ｐ∨～Ｑ∨Ｒ） 2019/1/2 计算机学院

28 公式转换法 （1）利用等价公式中的等价式和蕴涵式将公式中的→、用联结词～、∧、∨来取代；
（2）利用德摩根定律将否定号～移到各个命题变元的前端； （3）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。 （4）在析取范式的短语和合取范式的子句中，如同一命题变元出现多次，则将其化成只出现一次。 （5）去掉析取范式中所有永假式的短语和合取范式中所有永真式的子句，即去掉短语中含有形如P∧～P的子公式和子句中含有形如P∨～P的子公式。 2019/1/2 计算机学院

29 （6）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元P ，则可用公式： （～Ｐ∨Ｐ）∧Q=Q
（8）利用幂等律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。 2019/1/2 计算机学院

30 例1-5.4 利用公式的等价求G＝(P→Q)∧R的主合取范式和主析取范式。 解：G＝(P→Q)∧R＝(～P∨Q)∧R（蕴涵）
＝(～P∨Q∨(R∧～R))∧ ((～P∧P)∨(～Q∧Q)∨R)（添加R、P、Q） ＝(～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∨R)∧ (～P∨Q∨～R)∧(～P∨～Q∨R)（结合律） －－－－－主合取范式 2019/1/2 计算机学院

31 例1-5.4（续） G＝(P→Q)∧R＝(～P∨Q)∧R （蕴涵） ＝(～P∧R)∨(Q∧R)
＝(～P∧(～Q∨Q)∧R)∨((～P∨P)∧Q∧R) ＝(～P∧～Q∧R)∨(～P∧Q∧R)∨ (～P∧Q∧R)∨(P∧Q∧R) （分配律） ＝(～P∧～Q∧R)∨(～P∧Q∧R)∨(P∧Q∧R) ——主析取范式 2019/1/2 计算机学院

32 基本要求 理解析取范式、合取范式等概念 深刻理解极小项、极大项的定义，主析取范式、主合取范式等概念 熟练掌握求主析取（主合取）范式的方法
1）真值表技术法 2）公式转换法 2019/1/2 计算机学院

33 习题一 12(1)(3)、13、14、 15(1)(3)、18、19 2019/1/2 计算机学院