《离散数学(第4、5讲)》由会员分享，可在线阅读，更多相关《离散数学(第4、5讲)（45页珍藏版）》请在金锄头文库上搜索。
1、冯伟森 Email：Tel: 13808192275*计算机学院2主要内容n1、范式析取范式、合取范式、主析取（主合取）范式、极小项、极大项2、求主析取范式和主合取范式的方法1）真值表法 2）等价变换法 3、命题公式的蕴涵 1）九类蕴涵关系2）蕴涵关系的基本性质*计算机学院31.5 命题公式的范式表示一个命题公式可有无穷多个和它等价的命题公式，用真值表或等价变换证明它们是否等价，往往比较困难，甚至连计算机也无法解决。要解决判定问题，可用范式(公式的标准型)。范式全名叫规范型式,又叫标准型式,正规型式。把公式进行标准化，正规化，就叫对公式求范式。*计算机学院4定义1.16命题变元或命题变元的否定
2、称为句节。 有限个句节的析取式称为子句； 有限个句节的合取式称为短语。 有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。*计算机学院5例1-5.1 、是句节、子句、短语、析取范式、合取范式。 是子句、析取范式、合取范式； 是短语、析取范式、合取范式； （）（）是析取范式。 （）（）是合取范式。*计算机学院6 句子（）仅是子句、合取范式， 句子（）仅是短语、析取范式； 句子（）、 （）既 不是析取范式也不是合取范式。但转换后：（）=（）=上述两式的右端即是析取范式和合取范式。*计算机学院7结 论从上述定义和例子可以得出如下关系：1. 单个的句节是一个子句、短语、析取范式、 合取
3、范式。 2. 单个的子句是合取范式、 3. 单个的短语是析取范式。 4. 若省略外层括号，单个的子句也是析取范式 ，单个的短语也是合取范式。 5. 析取范式、合取范式仅含联结词 、 ，且仅出现在命题变元前。*计算机学院8定理1.6 任何命题公式都存在与之等价的合 取范式与析取范式。证明： （1）利用等价公式中的等价式和蕴涵式将公式 中的、用联结词 、来取代； （2）利用德摩根定律将否定号移到各个命题 变元的前端； （3）利用结合律、分配律、吸收律、幂等律、 交换律等将公式化成其等价的析取范式和合取范 式。*计算机学院9例1-5.2求（P（QR）S的合取范式 解：（P（QR）S （P（QR）S
4、（P（QR）S P（ QR）S （PS）（QR） （ PSQ）（ PSR）*计算机学院10主析取范式 一个公式的范式是不是唯一的呢？ 如P（QR） （PQ）（PR） （PQ）P（PQ）R（PP）（PQ)(P R）（QR）由于范式不唯一， 直接用范式判断命题间等价还是不方便。因此需要求公式的主范式。*计算机学院11 定义1.17 在n个变元的短语中，若每一个变元与其否 定并不同时存在，且二者之一必出现且仅出现一次， 则称这种短语为极小项。 由有限个极小项组成的析取式称为 主析取范式。 以下是由两个原子构成的极小项的真值表PQPQPQPQPQ111000100100010010000001*计算机
5、学院12由真值表可知： 任何两个命题公式（极小项）都不是相互等价 的，并且只有一组真值指派，使得该公式的值 为T。 2个命题变元有2 = 4种不同的组合（极小项）对于n个命题变元，共有2n个不同的极小项，记 为极小项公式成真赋值 名称0 00 11 01 1*计算机学院13*计算机学院14主合取范式定义1.17 在n个变元的子句中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则这 种子句称为极大项。由有限个极大项组成的合取式称为 主合取范式。以下是由两个原子构成的极大项的真值表PQPQPQPQPQ111110101101011011000111*计算机学院15 由真值表可知
6、：任何两个极大项都不是相互 等价的且只有一组真值指派使其值为F。 2个命题变元有2 = 4种不同的组合（极大项）对于n个命题变元，共有2n个不同的极大项 ，记为 。*计算机学院16极大项公式成假赋值 名称0 00 11 01 1*计算机学院171. 没有两个不同的极小项是等价的，且每个 极小项只有一组真值指派，使该极小项的真 值为真；2. 没有两个不同的极大项是等价的，且每个极 大项只有一组真值指派，使该极大项的真值 为假；极小项与极大项的性质*计算机学院183. mi=Mi；Mi=mi；i=0,1,2,2n-14. MiMj=T；mimj=F；ij；i,j0,1,2,2n-15. *计算机学
7、院19极小项与极大项的性质（续）6. 极大项取值0“当且仅当”：如果极大项中出现的是原子本身，则原子赋值为0；如果出现 的是原子的否定，则原子赋值为1。 7. 当一个极大项在一种解释下取值0时，其余 极大项在同一解释下取值1。PQPQPQPQPQ111110101101011011000111*计算机学院208. 极小项取值1 “当且仅当”：如果极小项中出现的是原子本身，则原子赋值为1；如果出现 的是原子的否定，则原子赋值为0。 9. 当一个极小项在一种解释下取值1时，其余 极小项在同一解释下取值0。PQPQPQPQPQ 111000 100100 010010 000001范式存在定理*计算
8、机学院21 定理1.7 在命题公式的真值表中，使公式取 值0时的解释所对应的全部极大项的合取式， 是该公式的主合取范式。 定理1.8 在命题公式的真值表中，使公式取 值1时的解释所对应的全部极小项的析取式， 是该公式的主析取范式。*计算机学院22基本要求n理解析取范式、合取范式等概念深刻理解极小项、极大项的定义，主析取范式、主合取范式等概念*计算机学院23利用真值表求主析（合）取范式例1-5.3 设 G=(PQ)R，求出它的主析 取范式和主合取范式。 求主析（合）取范式的方法有： 1、 真值表技术法 2、 公式转换法 *计算机学院24解：首先列出其真值表如下：PQRPQ (PQ)R 00010
9、 00111 01010 01111 10001 10100 11010 11111例1-5.3（续）*计算机学院25 1)、求公式的主析取范式P Q R(PQ）R0 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 极小项极小项极小项极小项PPP*计算机学院26 将极小项全部进行析取后，可得到相应的主析 取范式： G=（） =（P）（P）（ ）（）例1-5.3（续）*计算机学院27 2)、求公式的主合取范式P Q R(PQ)R0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0
10、 1 1 0 1 0 1 1 0 0 1 1 1 1例1-5.3（续）极大项极大项极大项极大项P PPP*计算机学院28 将极大项全部进行合取后，可得到相应的主合 取范式： G=（） = （P）（P）（ ）（） 例1-5.3（续）*计算机学院29公式转换法 （1）利用等价公式中的等价式和蕴涵式将公式中的 、用联结词、来取代； （2）利用德摩根定律将否定号移到各个命题变元 的前端； （3）利用结合律、分配律、吸收律、幂等律、交换律 等将公式化成其等价的析取范式和合取范式。 （4）在析取范式的短语和合取范式的子句中，如同一 命题变元出现多次，则将其化成只出现一次。 （5）去掉析取范式中所有永假式的
11、短语和合取范式中 所有永真式的子句，即去掉短语中含有形如PP的 子公式和子句中含有形如PP的子公式。*计算机学院30 （6）若析取范式的某一个短语中缺少该命题公式中所 规定的命题变元P ，则可用公式： （）Q=Q 将命题变元P补进去，并利用分配律展开，然后合并相 同的短语，此时得到的短语将是标准的极小项； （7）若合取范式的某一个子句中缺少该命题公式中所 规定的命题变元P ，则可用公式： （）Q=Q 将命题变元P补进去，并利用分配律展开，然后合并相 同的子句，此时得到的子句将是标准的极大项。 （8）利用幂等律将相同的极小项和极大项合并，同时 利用交换律进行顺序调整，由此可转换成标准的主析 取范
12、式和主合取范式。 *计算机学院31利用公式的等价求G(PQ)R的主合取范式和 主析取范式。 解：G(PQ)R(PQ)R（蕴涵） (PQ(RR)(PP)(QQ)R)（添加R、P、Q） (PQR)(PQR) (PQR)(PQR) (PQR)(PQR) （分配律） (PQR)(PQR)(PQR) (PQR)(PQR)（结合律） 主合取范式例1-5.4*计算机学院32G(PQ)R(PQ)R （蕴涵） (PR)(QR) (P(QQ)R)(PP)QR) (PQR)(PQR) (PQR)(PQR) （分配律） (PQR)(PQR)(PQR) 主析取范式例1-5.4（续）*计算机学院3316 命题公式的蕴涵
13、定义1.18 设A和B是两个合适公式，如果在 任何解释下，A取值1时B也取值1，则称公式A 蕴涵公式B，并记A B。 定理1.11 AB iff AB为永真式。 注意：蕴涵和条件联结词是完全不同的。是命题联结词，AB是一个命题公式；是公式间关系符，AB不是一个命题公式，仅表示A，B间的蕴涵关系。*计算机学院34基本蕴涵（关系）式（蕴涵定律）I1：PQ P ， PQQ I2: （PQ）P ，（PQ）Q I3：PPQ ， QPQ I4：PPQ ， QPQ I5：P（PQ） Q 假言推论 I6：Q（PQ） P 拒取式（否定式假言推论） I7：P（PQ） Q 析取三段论 I8：（PQ）（QR） PR 假言三段论扩充法则简化法则*计算机学院35基本蕴涵（关系）式（续）I9：（PQ）（PR）（QR） R 二难推论I10：（PQ）（RS）（PR）（QS） I11：（PQ）（QR） PR等价三段论 I12：（PQ）（PR） QR 归结原理解释：（PQ）（PR） QR *计算机学院36蕴涵关系的性质 自反性 A A 反对称性:如果A B，B A，iff A B A B 且A为永真式，则B必为永真式*计算机学院37传递性，如果A B，B C，则A C【证明】 由已知条件A B，且 B
