离散数学析取范式与合取范式.ppt

1、1,1.4 析取范式与合取范式,简单析取式与简单合取式 析取范式与合取范式 主析取范式与主合取范式,2,定义 文字:命题变项及其否定的总称. 简单析取式:有限个文字构成的析取式. 如 p, q, pq, pqr, 简单合取式:有限个文字构成的合取式. 如 p, q, pq, pqr, ,1）一个简单析取式为重言式当且仅当它同时含 有一个命题变项及它的否定；,2）一个简单和取式为矛盾式当且仅当它同时含 有一个命题变项及它的否定.,由定义易知：,3,由有限个简单合取式组成的析取式. A1A2Ar , 其中A1, A2, , Ar 是简单合取式 合取范式:由有限个简单析取式组成的合取式. A1A2A

2、r , 其中A1, A2, , Ar 是简单析取式,由定义易知：,析取范式:,1）在析取范式（合取范式）中没有联结词,2）联结词 只出现在原子命题前面.,3）析取范式（合取范式）是合取式（析取式）的析取式（合取式）.,4,范式:析取范式与合取范式的总称. 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 形如pqr, pqr 的公式既是析取范式， 又是合取范式 (为什么?),5,任何命题公式都存在着 与之等值的析取范式与合取范式. 求公式A的范式的步骤： (1) 消去A中的, （若存在） (2) 内移或消去否定联结词

3、 (3) 利用分配律 对分配（析取范式） 对分配（合取范式） 公式的范式存在，但不惟一，这是它的局限性.,定理（范式存在定理）,6,求公式的范式举例,例1.15 求下列公式的析取范式与合取范式: (1) A = ( pq)r 解 (pq)r (pq)r （消去） pqr （结合律） 这既是A的析取范式（由3个简单合取式组成的 析取式），又是A的合取范式（由一个简单析 取式组成的合取式）,7,(2) B = ( pq)r 解: (pq)r (pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定号内移德摩根律） 这一步已为析取范式（两个简单合取式构成） 继续： (pq)r (p

4、r)(qr) （对分配律） 这一步得到合取范式（由两个简单析取式构成）,8,例1.16 (1)求( pq) (p r) 的析取范式; 解: ( pq) (p r) ( pq) ( p r) （消去） ( pq) ( p r) （双重否定律） ( p p)(q p)( p r)(q r) （对分配） (q p)( p r)(q r) （零律,同一律）,9,(2) 求 ( p q) (p r) 的合取范式。 解: ( p q) (p r) (p q) ( p r) （消去） (p q p) (pq r) （ 对 分配） p q r （排中律,同一律）,10,极小项,定义 在含有n个命题变项的简单合

5、取式中， 若每个命题变项均以文字的形式在其中出现 且只出现一次，而且第i（1 i n）个文字出 现在左起第 i 位上，这样的简单合取式称为 极小项. 如： p q， p q r,11,说明：n个命题变项产生2n个极小项，2n个极小 项均互不等值. 用mi 表示第i个极小项，其中i是 该极小项成真赋值的十进制表示, mi 称为极小 项的名称.,12,p q,p q,p q,p q,0 0,0 1,1 0,1 1,由 p, q 两个命题变项形成的极小项:,13,由 p, q, r 三个命题变项形成的极小项:,14,主析取范式,主析取范式: 由极小项构成的析取范式. 例如，n=3, 命题变项为p,

6、q, r时， (pqr)(pqr) m1m3 是主析取范式 A的主析取范式: 与A等值的主析取范式.,15,定理 任何命题公式都存在着与之等值的主析取 范式, 并且是惟一的. 用等值演算法求公式的主析取范式的步骤： (1) 先求析取范式; (2) 将不是极小项的简单合取式化成与之等值的 若干个极小项的析取，需要利用同一律、排中 律、分配律、等幂律 (3) 极小项用名称mi 表示，按角标从小到大顺序排序.,16,求公式的主析取范式,例1.17 求公式 (pq)r 的主析取范式. (pq)r (pq)r , （析取范式） 其中 (pq) (pq)(rr) (pqr)(pqr) m6m7 , ,17

7、,r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7（主析取范式）,18,例1.18 求下列公式的主析取范式. (pq) ( p r ) ( p q) r ) p 答案: (1) (pq) ( p r ) m2 m3m5 m7 (2) ( p q) r ) p m2 m4m5 m6m7,19,例1.19 由( p q) r 的真值表求其主析取范式.,0 0 0,0 0 1,0 1 0,1 1 1,0 1 1,1 0 0,1 0 1,1 1 0,1,1,1,0,0,1,1,1,1,1,1,0,0,0,0,0,

8、主析取范式为： m3m5m7,20,作业:P36 17(1)(3)，18(1)，19,21,1. 证明： p(qr) (pq)r (p q) (p q) p 2. 求主析取范式： (p q) r ( pq) ( qr ) (3) ( pq) q r (4) ( pq) r,课堂练习：,(0, 1, 3, 7),(1, 3, 5, 7),(5),(1, 3, 4, 5, 7),22,主范式的用途与真值表相同,(1) 求公式的成真赋值和成假赋值 例如 (pq)r m1m3m5 m6m7， 其成真赋值为001, 011, 101, 110, 111， 其余的赋值 000, 010, 100为成假赋值

9、.,23,设A含n个命题变项，则 A为重言式 A的主析取范式含2n个极小项 A为矛盾式 A的主析取范式为0 A为非重言式的可满足式 A的主析取范式中至少含一个但不含 全部极小项,(2) 判断公式的类型,24,例1.20 用主析取范式判断下述两公式是否等值： p(qr) 与 (pq)r p(qr) 与 (pq)r 解: p(qr) m0m1m2m3 m4m5 m7 (pq)r m0m1m2m3 m4m5 m7 (pq)r m1m3 m4m5 m7 显见，中两公式等值，而的两公式不等值.,(3) 判断两个公式是否等值,25,(4) 分析和解决一些实际问题,例1.21 某公司要从赵、钱、孙三名新毕业

10、的 大学生中选派一些人出国学习，选派必须满足 以下条件： (1) 若赵去，则孙也可以去； (2) 若钱去，则孙不能去； (3) 若孙不去，则赵或钱可以去. 试用主析取范式法分析该公司如何选派他们出国？,26,解此类问题的步骤为： 将简单命题符号化； 写出各复合命题； 写出由中复合命题组成的合取式； 求中所得公式的主析取范式。,27,解: 设p：派赵去，q：派钱去，r：派孙去. (1) p r (2) q r (3) r (p q) (1) (3)构成的合取式为 A=( p r )(q r)(r (p q),28, A的演算: A (pqr)(pqr)(pqr) (1, 2, 5) 结论： 由可

11、知，A的成真赋值为001、010、101， 因而方案有三个： 孙去（赵、钱不去）； 钱去（赵、孙不去）； 赵、孙（钱不去）.,29,极大项,定义 在含有n个命题变项的简单析取式中， 若每个命题变项均以文字的形式在其中出现 且只出现一次，而且第i（1 i n）个文字出 现在左起第 i 位上，这样的简单析取式称为 极大项.,30,说明：n个命题变项产生2n个极大项，2n个极大 项均互不等值. 用Mi 表示第i个极大项，其中i是 该极大项成假赋值的十进制表示, Mi 称为极大 项的名称.,31,p q,p q,p q,p q,0 0,1 0,0 1,1 1,由 p, q 两个命题变项形成的极大项,3

12、2,由p, q, r三个命题变项形成的极大项,33,极小项与极大项比较,由p, q两个命题变项形成的极小项与极大项,34,由p, q, r三个命题变项形成的极小项与极大项,35,主合取范式: 由极大项构成的合取范式. 例如，n = 3, 命题变项为p, q, r时， (pqr)(pqr) M1M5 是主合取范式 A的主合取范式: 与A等值的主合取范式.,由上述比较可知：,极小项mi 与极大项Mi的关系: mi Mi , Mi mi,36,求主合取范式的方法：,1. 等值演算法： (1) 先求合取范式; (2) 将不是极大项的简单析取式化成与之等值的 若干个极大项的合取，需要利用零律、同一律、 排中律、分配律、等幂律 ; (3) 极大项用名称Mi 表示，按角标从小到大顺序排序.,37,求公式的主合取范式,例1.22 求公式 (pq)r的主合取范式. (pq)r (pr)(qr) , （合取范式） pr p(qq)r (pqr)(pqr) M0M2 ,38,qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得 (pq)r M0