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

1、2.2 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 一个析取范式是矛盾式

3、当且仅当它的每个简单合取式都是矛盾式。 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。 定理定理2.3 （范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。 研究范式的目的是将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。思考：怎样将公式转化为范式？例2.7 求下面公式的析取范式与合取范式： (pq) r 先求合取范式 (pq) r (pq) r （消去） (pq)r)(r(pq) （消去 ） (pq)r)(rpq) （消去） (pq)r)(pqr) （否定号内移） (pr)(qr)(pqr) （对分配律） 将公式转化为范式

4、的步骤将公式转化为范式的步骤 消除联结词，AB AB A B (A B) (B A) (AB)(AB 缩小的作用范围A A (AB) AB (AB) AB 利用分配率，转化为析取（合取）范式 A(BC) (AB)(AC) A(BC) (AB)(AC) 例2.7 求下面公式的析取范式与合取范式： (pq) r 求析取范式 (pq) r (pq) r （消去） (pq)r)(r(pq) （消去 ） (pq)r)(rpq) （消去） (pq)r)(pqr) （否定号内移） (pqp)(pqq)(pqr） (rp)(rq)(rr) （对分配律） (pqr)(pr)(qr) 极小项与极大项的定义极小项与

5、极大项的定义极小项：极小项：在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第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个命题变项的简

6、单析取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第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 极小项 解释 记法极大项解释记法pqr 000m0p q r000M0pqr 001m1p q r001 M1pqr 010m2

7、p q r010 M2pqr 011m3p q r011 M3pqr 100m4p q r100M4pqr 101m5p q r101M5pqr 110m6p q r110M6pqr 111m7p q r111M7p, q, r 形成的极小项与极大项 定理定理2.4 设mi与Mi是命题变项p1,p2,pn形成的极小项和极大项，则mi Mi ， Mi mi 主析取范式主析取范式(主合取范式主合取范式) 设由n个命题变项构成的析取范式中所有的简单合取式都是极小项，则称该析取范式为主析取范式。 设由n个命题变项构成的合取范式中所有的简单析取式都是极大项，则称该合取范式主合取范式。 例如：(pq) r

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

9、)(q(pr)(rp)(qp)(qr)(pr)(qp)(qr)(pr)(qq)(qp)(rr)(qr)(pp)(pqr)(pqr)(pqr)(pqr) m1 m3m6m7A A (P P) （A P） （ A P ）结论: 公式的所有成真赋值对应主析取范式的所有极小项.(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) (

10、q r) (p r) (p q ) (q r) (p 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如何求一个公式的主析取范

11、式？（1）利用等值转化法（2）利用真值表（3）通过主合取范式求逆例例3：求命题公式pq的主析取范式和主合取范式。 方法1：真值表法pqp q001011100111pqm0 m1 m4( p q) ( p q) ( p q) 方法2：公式法pqp q p (q q) q (p p)( p q) ( p q) ( p q) M2 p qm0 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

12、) (q r) 的主析取范式真值表法：pqr p p qq r( p q) (q r)00010000011000010110001111111000100101010011001001110111( 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历史遗留问题: 我只给村里所有那

13、些不给自己理发的人理发 只要别人有困难,他就帮忙,除非困难解决. a:别人有困难, b: 他帮忙(1) a b作业作业 38 5题（题（1 、3） 注意总结规律注意总结规律 6题（题（2)作业问题: 整体较好,都交了. 个别书写不认真,应付私事。 注意“” 的书写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)

14、 (p q)(p q) (p q)主析取范式的用途主析取范式的用途 求公式的成真与成假赋值 判断公式的类型 判断两个命题公式是否等值 应用主析取范式分析和解决实际问题例1: 求 (pq) (qp) 的成真赋值A m1m2ms(pq) (q p) (p q) (q p)(p q) (q p) (p q) (p q) (pq) m0 m2 m3即成真赋值为：0 0,1 0，1 1pq p pq q qp(pq) (qp)00 1011101 1100010 0111111 01011A m1m2ms(1)A为重言式当且仅当其主析取范式包含2n个极小项(2) A为矛盾式当且仅当其主析取范式包不含极小

15、项(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 m7 m3 m5pqrpq(pq)r0000100101010100111110010101111101011111 若公式A、B含有相同的命题变项， A与B等值的充要条件是它们有相同的主析取范式。例：问 (pq)r 与 p(qr) 是否等值(pq)r (pq) r (p

16、q) r(pqr)(pqr) (pqr)(pqr)(pqr)m5 m4 m7 m3 m1p(qr) p (qr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr)m3 m1 m2 m0 m5 m4 m7M6例例: 某科研所要从3名科研骨干A、B、C中挑选12名出国进修，由于工作需要，选派时要满足以下条件：（1）若A去，则B同去；（2）若B去，则C不能去；（3）若C不去，则A或B可以去。问所里有哪些选派方案？解：设 p: A去; q: B去; r: C去则选派方案应满足：(pr)(qr)(r(p q)(pr)(qr

17、)(r(p q) (pr) (qr)(r pq)(pqr)(pqr) (pqr)(pqr)( pqr)M4 M6 M3 M7 M0 m1m2m5因此,选派方案为（001，010，110）2.3 2.3 联结词的完备集 n元真值函数的定义元真值函数的定义 自变量：n个命题变项定义域：由0，1组成的长度为n的符号串全体。（2n） 值域：0，1思考：n个命题变项可构成多少个不同的真值函数？ （22n） 每个真值函数对应唯一一个主析取范式（主合取范式） 每个真值函数对应无穷多个与之等值的命题公式每个命题公式对应唯一一个真值函数 联结词完备联结词完备 设S是一个联结词集合，如果任何n(n1)元真值函数都

18、可以由 仅含S中的联结词构成的公式表示，则称S是联结词完备集。 定理定理2.6 S=,是联结词完备集 证：因为任何n(n1)元真值函数都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词,，所以S=,是联结词完备集。 推论推论 以下联结词集都是完备集： (1) S1=, (2) S2=, (3) S3=, (4) S4=, (5) S5=, pq ( pq) (p q) 与非联结词与非联结词 根据需要，人们还可构造形式上更为简单的联结词完备集。例如，在计算机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集。 设p、q为两个命题，复合命题“p与q的否定式”称作p,q的

19、与非与非式式 记作pq。即 pq (pq）, 符号称作与非联结词。 pq 表示或非式或非式 ，即pq (pq） 定理2.7 ，都是联结词完备集 小小 结结主要内容： 等值式 基本的等值式 主析取范式与主合取范式 联结词完备 要求 熟练掌握等值演算 熟练掌握公式主析取范式（主合取范式）的求法 会用主析取范式解决一些问题一会将公式化为联结词完备集中的公式一、下列说法正确的是一、下列说法正确的是: A B 当且仅当AB是可满足式 A B 当且仅当A和B有相同的主析取范式 若A为重言式,则A的主析取范式含有个 2n极小项 若A为矛盾式,则A的主析取范式为1 若A为矛盾式,则A的主合取范式为1 任何公式A都能等值的化为联结词, 中的公式 任何公式A都能等值的化为联结词集合, , 中的公式二、用等值演算法来判断下列公式的类型、用等值演算法来判断下列公式的类型(pq)r q(p q) r