离散数学).ppt

* 计算机学院 * 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) ——主析取范式 例1-5.4（续） * 计算机学院 * 基本要求 理解析取范式、合取范式等概念 深刻理解极小项、极大项的定义，主析取范式、主合取范式等概念 熟练掌握求主析取（主合取）范式的方法 1）真值表技术法 2）公式转换法 * 计算机学院 * 习题一 12(1)(3)、13、14、 15(1)(3)、18、19 计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 主要内容 1、范式 析取范式、合取范式、主析取（主合取）范式、极小项、极大项 2、求主析取范式和主合取范式的方法 1）真值表法 2）公式转换法 * 计算机学院 * 1.5 命题公式的范式表示 一个命题公式有无数多个和它等价的命题公式，用真值表或等价变换证明它们是否等价，往往比较困难，甚至连计算机也无法解决。 要解决这个问题，我们引入范式(公式的标准型)的概念。 范式——全名叫规范型式,又叫标准型式,正规型式。把公式进行标准化，正规化，就叫对公式求范式。 问题：这样的标准 形式存在吗？ 是否唯一？ * 计算机学院 * 定义1.16 命题变元或命题变元的否定称为句节。 有限个句节的析取式称为子句； 有限个句节的合取式称为短语。 有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。 * 计算机学院 * 例1-5.1 Ｐ、～Ｐ是句节、子句、短语、析取范式、合取范式。 Ｐ∨Ｑ∨～Ｒ是子句、析取范式、合取范式； ～Ｐ∧Ｑ∧Ｒ是短语、析取范式、合取范式； （Ｐ∧Ｑ）∨（～Ｐ∧Ｑ）是析取范式。 （Ｐ∨Ｑ）∧（～Ｐ∨Ｑ）是合取范式。 * 计算机学院 * 句子（Ｐ∨Ｑ∨～Ｒ）仅是子句、合取范式， 句子（～Ｐ∧Ｑ∧Ｒ）仅是短语、析取范式； 句子Ｐ∨（Ｑ∨～Ｒ）、 ～（Ｑ∨Ｒ）既 不是析取范式也不是合取范式。但转换后： Ｐ∨（Ｑ∨～Ｒ）=Ｐ∨Ｑ∨～Ｒ ～（Ｑ∨Ｒ）=～Ｑ∧～Ｒ 上述两式的右端即是析取范式和合取范式。 * 计算机学院 * 结论 从上述定义和例子可以得出如下关系： 单个的句节是一个子句、短语、析取范式、合取范式。 单个的子句是合取范式、 单个的短语是析取范式。 若省略外层括号，单个的子句也是析取范式，单个的短语也是合取范式。 析取范式、合取范式仅含联结词～ 、∧、∨，且～仅出现在命题变元前。 * 计算机学院 * 定理1.6 任何命题公式都存在与之等价的合取范式与析取范式。 证明： （1）利用等价公式中的等价式和蕴涵式将公式中的→、?用联结词～ 、∧、∨来取代； （2）利用德?摩根定律将否定号┐移到各个命题变元的前端； （3）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。 * 计算机学院 * 例1-5.2 求（P∧（Q→R））→S的合取范式 解：（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） * 计算机学院 * 主析取范式 一个公式的范式是不是唯一的呢？ 如 P∨（Q∧R） ?（P∨Q）∧（P∨R） ?（（P∨Q）∧P）∨（（P∨Q）∧R） ?（P∧P）∨（P∧Q)∨(P ∧ R）∨（Q∧R） 由于范式不唯一， ∴直接用范式判断命题间等价还是不方便。 因此需要对公式进一步规范化，即求公式的 主范式。 * 计算机学院 * 定义1.17 在n个变元的短语中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则称这种短语为极小项。 由有限个极小项组成的析取式称为主析取范式。 以下是由两个原子构成的极小项的真值表 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 * 计算机学院 * 由真值表可知： ①任何两个命题公式（极小项）都不是相互等价的，并且只有一组真值指派，使得该公式的值为T。 ②2个命题变元有22 = 4种不同的组合（极小项） 对于n个命题变元，共有