离散结构2.2.ppt

《离散结构2.2.ppt》由会员分享，可在线阅读，更多相关《离散结构2.2.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.2.2 主析取范式与主合取范式音乐能激发或抚慰情怀，绘画使人赏心悦目，诗歌能动人心弦，哲学使人获得智慧，科学可改善物质生活，但数学能给予以上的一切-克莱因 命题等值验算的一个应用：将下图所示的逻辑电路简化,解：将上述逻辑电路写成命题公式：,利用等值式将公式化简,分配律,结合律,等幂律,所以，该电路可简化为下图 ：,2.2.2 主析取范式与主合取范式,1、简单析取式，简单合取式。,2、析取范式，合取范式。,为合取范式。,2、析取范式，合取范式。,为析取范式。,2、析取范式，合取范式。,求范式步骤：,(2) 否定联结词消去或内移。,(3) 利用分配律。,(1) 消去联结词,解：原式,消去,内移

2、,消去,上式即析取范式,解：原式,消去,内移,消去,上式即合取范式,2.2.2 主析取范式与主合取范式数学中的一些美丽定理具有这样的特性：它们极易从事实中归纳出来，但证明却隐藏的极深。 高斯,极小项与极大项的定义 在含有n个命题变项的简单合（析）取式中，若每个命题变项和它的否定不同时出现，而二者之一必出现且仅出现一次，称这样的简单合（析）取式为极小（大）项minimal(maximal) item。 如命题公式(p q) (p r)的极小项有pq r、 p q r、 p q r、 p q r 等。 p q rr和p q是否为上述公式的极小项？ 考虑： n个命题变项可产生多少个极小（大）项？,2

3、.2.2 析取范式(disjunction normal form),每个极小项，如p1 p2 p3 pn,有且仅有一个成真赋值，若成真赋值所对应的二进制数转化为十进制数为i，就将所对应的极小项记作mi。,极大项,记法,主析取范式与主合取范式的定义,两种求法，等值式法和真值表法。,定理：任何命题公式的主析取范式、主合取范式 都存在且都是唯一的。,disjunction normal form,求解方法1： 1。将命题公式转换为析（合）取范式； 2。判断析（合）取范式中的简单合（析）取式是否为命题公式的极小（大）项，若不是则进行补项。 Ai Ai 1 Ai (pj pj) (Ai pj ) (A

4、i pj) Ai Ai 0 Ai (pj pj) (Ai pj ) (Ai pj) 求解方法2: 1.求命题公式的真值表; 2. 列出使命题公式为真的指派所对应的极小项; 3. 将2列出的极小项进行析取.,disjunction normal form,例：求(p q) r的主析取/合取范式。 接前(p q r ) (r p) (rq ) (析取范式) (p q r ) (q q) (r p) (p p) (r 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) m1 m3m4 m (主析

5、取范式),disjunction normal form,例：求(p q) r的主析取/合取范式。 接前(pr)( qr)( rpq ) (合取范式） (pr)(q q)(pp) ( qr)( rpq ) (pqr)(pqr) (p qr)(pqr) (pq r ) (pqr)(pqr) (p qr) (pq r ) M0M2M5 M6,解：(1) 列真值表,解：(2) 的成真赋值有010，100，101，110，111,(3) 对应的十进制数为2，4，5，6，7,所以的主析取范式为,disjunction normal form,练习：求主析取/合取范式。 1、( p q) (p r) 2、

6、(p q) (p r),1(p q r ) (p q r )(pq r) (pq r) (主合取范式) M0M1M4 M6 (p qr) (p q r) ( pq r) ( pq r ) (主析取范式) 2 p q r (主合取范式) m0 m1 m2 m3m5 m6 m,disjunction normal form,主析取范式的用途（主合取范式类似讨论）： 1、求公式的成真/成假赋值： 若公式A中含有n个命题变项，且A的主析取范式含s 个极小项，则A有s个成真赋值，有2n-s个成假赋值。 2、判断公式的类型： 设公式A中含有n个命题变项，则： （1）A为重言式 A的主析取范式含全部2n个极

7、小项。 （2）A为矛盾式 A的主析取范式不含任何极小项，记A的主析取范式为0。 （3）A为可满足式A的主析取范式至少含一个极小项。,disjunction normal form,练习：求下列公式的主析取范式，并判断公式的类型。 1、( p q) (q p) 2、(p p ) (q q) r) 3、 (p q) (q r) (p r) 3、判断两个命题是否等值： 设公式A、B中共含有n个命题变项，按n个命题变项求出A、B的主析取范式A、B。若A=B ，则A B，否则A、B不等值 。 练习：1、(p q) (p r) 与 p (q r) 2、 p (q r) 与 p (q r),disjunct

8、ion normal form,解：1、 (p q) (p r) ( p q) ( p r) p ( q r) m0 m1 m2 m3m p (q r) p ( q r) m0 m1 m2 m3m 所以 (p q) (p r) p (q r),disjunction normal form,解： 2、 p (q r) p ( q r) m0 m1 m2 m3m p (q r) p q r m0 m1 m3 m4 m5m6 m 所以 (p q) (p r) 与 p (q r) 不等值。,disjunction normal form,4、解决实际问题： 某勘探队有3名队员，有一天取得一块矿样，3

9、人判断如下： 甲说：这不是铁，也不是铜。 乙说：这不是铁，是锡。 丙说：这不是锡，是铁。 经实验室鉴定发现，其中一人的两个判断全对，一人判对一半，另一人全错。试根据以上情况，判断矿样的种类。,disjunction normal form,解: 设 p:矿样是铁。q :矿样是铜。r :矿样是锡。 根据题设知有六种情况： 甲正确，乙对一半，丙全错； 甲正确，乙全错，丙对一半； 甲对一半，乙正确，丙全错； 甲对一半，乙全错，丙正确； 甲全错，乙正确，丙对一半； 甲全错，乙对一半，丙正确。,disjunction normal form,以上六种情况对应公式分别为： (pq) (pr)(pr) (p

10、r) 0 (pq) (pr)(pr)(p r) 0 (pq)(pq)(pr)(pr)pq r (pq)(pq)(pr)(p r)p q r (pq)( pr)(pr)(p r) 0 (pq) (pr) ( pr) ) (p r) 0,disjunction normal form,解: 设 判断经过为F，则： F (pq r) (p q r) 但不能同时为铜又为锡，因而只能对应p q r，即不是铜，也不是锡，而是铁。,2.2.2 合取范式(conjunction normal form),每个极大项，如p1 p2 p3 pn,有且仅有一个成假赋值，若成假赋值所对应的二进制数转化为十进制数为i，

11、就将所对应的极小项记作Mi。,conjunction normal form,定理2 极小项与极大项关系 设mi和Mi是命题变项p1 ， p2 ， pn形成的极小项和极大项，则 mi Mi ， Mi mi,(3) 对应的十进制数为0，1，3。,conjunction normal form,关于主合取范式 1、由公式的主析取范式求主合取范式 设公式A中含有n个命题变项，且A的主析取范式含s 个极小项，即 A mi1 mi2 mis，0ij 2n-1,j=1,2, ,s. 没出现的极小项为mj1 , mj2 mjs,它们的脚标的二进制表示为A的成真赋值，因而A的主析取范式为 A= mj1 mj2 mjs,析取范式与合取范式,A A ( mj1 mj2 mjs) mj1 mj2 mjs Mj1 Mj2 Mjs,由主析取范式求主合取范式的一个应用：,(2) 写出与(1)中极小项角码相同的极大项，,36,析取范式与合取范式,2、重言式与矛盾式的主合取范式 设公式A中含有n个命题变项，则： （1）A为矛盾式 A的主合取范式含全部2n个极大项。 （2）A为重言式 A的主合取范式不含任何极大项，记A的主合取范式为1。 （3）A为可满足式 A的主合取范式中极大项的个数一定小于2n 。,