第二章析取范式与合取范式

1、2.2 析取范式与合取范式,简单析取式(简单合取式),命题变项及其否定称为。如p, p 仅有有限个文字构成的析取式称作简单析取式。 如 p, q; pp，pq ; pqr, pqr。,仅有有限个文字构成的合取式称作简单合取式。 如 p, q; pp，pq ; pqr, ppq 。,注意： 一个文字既是简单析取式，又是简单合取式。 一般用A1,A2,As表示s个简单析取式或s个简单合取式。,定理2.1,一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。 如：pp，ppr都是重言式； pq，pqr都不是重言式。 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。 如：

2、p p，p p r都是矛盾式； p q，p q r都不是矛盾式。,范式的定义,由有限个简单合取式构成的析取式称为析取范式。 由有限个简单析取式构成的合取式称为合取范式。 析取范式与合取范式统称为范式。,设 Ai(i=1,2,s)为简单合取式,则析取范式的形式: A=A1A2As 例如A=(pq)(qr)p,设 Ai(i=1,2,s)为简单析取式,则合取范式的形式: A=A1A2As 例如A=(pqr)(pq)r,思考：pqr 与pqr属于什么范式？,定理2.2,一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。,定理2.3 （

3、范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。,研究范式的目的是将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。,思考：怎样将公式转化为范式？,例2.7 求下面公式的析取范式与合取范式：,(pq) r,将公式转化为范式的步骤,消除联结词，,AB AB,缩小的作用范围,利用分配率，转化为析取（合取）范式,例2.7 求下面公式的析取范式与合取范式：,(pq) r,(pqr)(pr)(qr),极小项与极大项的定义,极小项：在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项

4、或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式为极小项。,例：p r q; p p r; p q p; p q r; p q r; p q r,思考: (1) n个命题变项共可产生多少个不同的极小项? (2)每个极小项有多少个成真赋值?,2n,一个,规定:成真赋值所对应的二进制数转换为十进制数i，就将所对应极小项记作mi,极小项与极大项的定义,极大项：在含有n个命题变项的简单析取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这

5、样的简单析取式为极大项。,例：p r q; p p r; p q p; p q r; p q r; p q r,思考: (1) n个命题变项共可产生多少个不同的极大项? (2)每个极大项有多少个成假赋值?,2n,一个,规定:成假赋值所对应的二进制数转换为十进制数i，就将所对应极大项记作Mi,p, q, r 形成的极小项与极大项,定理2.4 设mi与Mi是命题变项p1,p2,pn形成的极小项和极大项，则,mi Mi ， Mi mi,主析取范式(主合取范式),设由n个命题变项构成的析取范式中所有的简单合取式都是极小项，则称该析取范式为主析取范式。,设由n个命题变项构成的合取范式中所有的简单析取式都

6、是极大项，则称该合取范式主合取范式。,例如：(pq) r,(pqr)(pr)(qr),(pqr) (pqr)(pqr) (pqr）(pqr),例如：(pq) r,(pr)(qr)(pqr),定理2.5,任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是唯一的。,如何求主析取范式（主合取范式）？ 首先求等价的析取范式（合取范式） 然后对非极小项（或者非极大项）进行扩展。,最后，求出某公式的主析取范式（主合取范式）后，将极小项（极大项）都用名称写出，并且按极小项（极大项）名称的角标由小到大顺序排列。,求A=(rp)(q(pr)的主析取范式,例1：,解：,(rp)(q(pr) (rp)(q

7、p)(qr) (pr)(qp)(qr) (pr)(qq)(qp)(rr)(qr)(pp) (pqr)(pqr)(pqr)(pqr) m1 m3m6m7,结论: 公式的所有成真赋值对应主析取范式的所有极小项.,(rp)(q(pr)的主合取范式 (rp)(qp)(qr) (p r)(qp)(qr) (pr) q (pr) p (qr) (p q) (q r) (p p) (p r) (qr) (p q q) (q r q) (p r q) (p q r) (q r r) (p r r) (p q ) (q r) (p r q) (p q r) (q r) (p r) (p q ) (q r) (p

8、 r q) (p q r) (p r) (p q r) (p q r) (p q r) (p q r) M4 M5 M0 M2,结论: 公式的所有成假赋值对应主合取范式的所有极大项.,例2：,求A=(pq) r的主析取范式,(pq) r,(pqr)(pr)(qr),(pqr) (pqr)(pqr) (pqr)(pqr) (pqr) (pqr)(pqr) (pqr) m4 m1 m3 m7,求A=(pq) r的主合取范式,(pq) r,(pr)(qr)(pqr),(pq r) (p q r) ( p qr)(pqr),M0 M2 M6 M5,如何求一个公式的主析取范式？ （1）利用等值转化法 （

9、2）利用真值表 （3）通过主合取范式求逆,例3：,求命题公式pq的主析取范式和主合取范式。,方法1：真值表法,pq,m0 m1 m4,( p q) ( p q) ( p q),方法2：公式法,pq p q p (q q) q (p p) ( p q) ( p q) ( p q),m0 m1 m4,练习: 求 ( p q) (q r) 的主析取范式,公式法：,( p q) (q r) (p q) (q r) (p q r) (q r) (p q r) (q r p ) (q r p ) (p q r) ( p q r) m3 m7,练习: 求 ( p q) (q r) 的主析取范式,真值表法：,

10、( p q) (q r),m3 m7,练习: 求 ( p q) (q r) 的主析取范式,求合取范式：,( p q) (q r) (p q) (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) M0 M1 M4 M5 M2 M6,因此主析取范式为：,m3 m7,历史遗留问题: 我只给村里所有那些不给自己理发的人理发 只要别人有困难,他就帮忙,除非困难解决. a:别人有困难, b: 他帮忙 a b,作业 38 5题（1 、3） 注意总结规律 6题（2),作业问题: 整体较好

11、,都交了. 个别书写不认真,应付私事。 注意“” 的书写 P14 14题,(10)除非天下大雨，否则他不乘车上班。 p:天下大雨 q:他乘车上班 q p,2和4是素数，这是不对的。 p: 2是素数 q: 4是素数 (p q),P38 4题(4) (p q) (pq) (p q) (p q),(p q) (pq) (p q) p (p q) q (p p) (q p) (p q) (q q) (q p) (p q) (p q) (p q),主析取范式的用途,求公式的成真与成假赋值 判断公式的类型 判断两个命题公式是否等值 应用主析取范式分析和解决实际问题,例1: 求 (pq) (qp) 的成真赋

12、值,(pq) (q p) (p q) (q p) (p q) (q p) (p q) (p q) (pq) m0 m2 m3,即成真赋值为：0 0,1 0，1 1,(1)A为重言式当且仅当其主析取范式包含2n个极小项 (2) A为矛盾式当且仅当其主析取范式包不含极小项 (3) A为可满足式当且仅当其主析取范式包至少含一个极小项,例2：判断下列公式的类型,p (pq) p(pq) ( p q) (p q) (p q) (p q) (p q) (p q),m1 m0 m3 m2,重言式,(2) (pq)r (p q) r (pqr)(pqr)(pqr)(pqr) (pqr)(pqr),m1 m0

13、m7 m3 m5,若公式A、B含有相同的命题变项， A与B等值的充要条件是它们有相同的主析取范式。,例：问,(pq)r 与 p(qr) 是否等值,(pq)r (pq) r (pq) r (pqr)(pqr) (pqr)(pqr)(pqr) m5 m4 m7 m3 m1,p(qr) p (qr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) m3 m1 m2 m0 m5 m4 m7,例: 某科研所要从3名科研骨干A、B、C中挑选12名出国进修，由于工作需要，选派时要满足以下条件： （1）若A去，则B同去；（2）

14、若B去，则C不能去； （3）若C不去，则A或B可以去。 问所里有哪些选派方案？,解：设 p: A去; q: B去; r: C去,则选派方案应满足：(pr)(qr)(r(p q),(pr)(qr)(r(p q) (pr) (qr)(r pq) (pqr)(pqr) (pqr)(pqr)( pqr) M4 M6 M3 M7 M0 m1m2m5,因此,选派方案为（001，010，110）,2.3 联结词的完备集,n元真值函数的定义,自变量：n个命题变项 定义域：由0，1组成的长度为n的符号串全体。（2n） 值域：0，1 思考：n个命题变项可构成多少个不同的真值函数？,（22n）,每个真值函数对应唯一

15、一个主析取范式（主合取范式） 每个真值函数对应无穷多个与之等值的命题公式 每个命题公式对应唯一一个真值函数,联结词完备 设S是一个联结词集合，如果任何n(n1)元真值函数都可以由 仅含S中的联结词构成的公式表示，则称S是联结词完备集。,定理2.6 S=,是联结词完备集,证：因为任何n(n1)元真值函数都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词,，所以S=,是联结词完备集。,推论 以下联结词集都是完备集：(1) S1=, (2) S2=, (3) S3=, (4) S4=, (5) S5=,与非联结词,根据需要，人们还可构造形式上更为简单的联结词完备集。例如，在计算机硬件设计中，用

16、与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集。,定理2.7 ，都是联结词完备集,小 结 主要内容： 等值式 基本的等值式 主析取范式与主合取范式 联结词完备 要求 熟练掌握等值演算 熟练掌握公式主析取范式（主合取范式）的求法 会用主析取范式解决一些问题 会将公式化为联结词完备集中的公式,一、下列说法正确的是: A B 当且仅当AB是可满足式 A B 当且仅当A和B有相同的主析取范式 若A为重言式,则A的主析取范式含有个 2n极小项 若A为矛盾式,则A的主析取范式为1 若A为矛盾式,则A的主合取范式为1 任何公式A都能等值的化为联结词, 中的公式 任何公式A都能等值的化为联结词集合

17、, , 中的公式,二、用等值演算法来判断下列公式的类型,(pq)r q (p q) r q p0r 0 所有,该公式为矛盾式,三、用主析取范式法来判断下列公式的类型,并求其成真赋值,(pq) ( p q) (pq) (p q ) (p q) p q (p q) (p q) (p q) (p q) ( p q) (p q) (p q) ( p q) m2 m3 m0 该公式为可满足式,成真赋值为10,11,00,四、用主合取范式法来判断下列公式的类型,并求其成假赋值,(pq) ( p q),(pq) (p q ) (p q) p q (p p q) ( qp q) p q M1 该公式为可满足式, 成假赋值为01,五、已知公式A含3个命题变项p,q,r，并且它的成真赋值为001， 011,110，求A