析取范式与合取范式.ppt
39页
§2.2 §2.2 析取范式与合取范式析取范式与合取范式1.简单析取式简单析取式(简单合取式简单合取式)Ø命题变项及其否定称为文字文字如p, pØ仅有有限个文字构成的析取式称作简单析取式简单析取式 如 p, ┐q; p∨┐p，┐p∨q ; ┐p∨┐q∨r, p∨┐q∨r Ø仅有有限个文字构成的合取式称作简单合取式简单合取式 如 p, ┐q; ┐p∧p，p∧┐q ; p∧q∧┐r, ┐p∧p∧q 注意：• 一个文字既是简单析取式，又是简单合取式• 一般用A1,A2,…,As表示s个简单析取式或s个简单合取式 2. 定理定理2.1Ø 一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式 如：p∨┐p，p∨┐p∨r都是重言式； ┐p∨q，┐p∨┐q∨r都不是重言式 Ø 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式如：p∧ ┐p，p∧ ┐p∧ r都是矛盾式； p∧ ┐ q，┐p∧ q∧ ┐ r都不是矛盾式 3.范式的定义范式的定义Ø 由有限个简单合取式构成的析取式称为析取范式析取范式Ø 由有限个简单析取式构成的合取式称为合取范式合取范式Ø 析取范式与合取范式统称为范式。
范式• 设 Ai(i=1,2,…,s)为简单合取式,则析取范式的形式: A=A1∨A2∨…∨As 例如A=(p∧┐q)∨(┐q∧┐r)∨p • 设 Ai(i=1,2,…,s)为简单析取式,则合取范式的形式: A=A1∧A2∧…∧As 例如A=(p∨q∨r)∧(┐p∨┐q)∧r • 思考：┐p∧q∧r 与p∨┐q∨r属于什么范式？ 4.定理定理2.2Ø 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式Ø 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式5.定理定理2.3 （范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式 • 研究范式的目的是将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式思考：怎样将公式转化为范式？ Ø例2.7 求下面公式的析取范式与合取范式： (p→q) r 先求合取范式 (p→q) r (┐p∨q) r （消去→） ((┐p∨q)→r)∧(r→(┐p∨q)) （消去 ） (┐(┐p∨q)∨r)∧(┐r∨┐p∨q) （消去→） ((p∧┐q)∨r)∧(┐p∨q∨┐r) （否定号内移） (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r) （∨对∧分配律） 6.将公式转化为范式的步骤将公式转化为范式的步骤①消除联结词，，A→B ┐A∨B A B (A B) ∧(B A) (┐A∨B)∧(A∨┐B ②缩小┐的作用范围┐┐A A ┐(A∧B) ┐A∨┐B ┐(A∨B) ┐A∧┐B ③利用分配率，转化为析取（合取）范式 A∧(B∨C) (A∧B)∨(A∧C) A∨(B∧C) (A∨B)∧(A∨C) Ø例2.7 求下面公式的析取范式与合取范式： (p→q) r 求析取范式 (p→q) r (┐p∨q) r （消去→） ((┐p∨q)→r)∧(r→(┐p∨q)) （消去 ） (┐(┐p∨q)∨r)∧(┐r∨┐p∨q) （消去→） ((p∧┐q)∨r)∧(┐p∨q∨┐r) （否定号内移） (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r） ∨(r∧┐p)∨(r∧q)∨(r∧┐r) （∨对∧分配律） (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) 7.极小项与极大项的定义极小项与极大项的定义Ø极小项：极小项：在含有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 7.极小项与极大项的定义极小项与极大项的定义Ø极大项：极大项：在含有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 极小项 解释 记法极大项解释记法pqr 000m0p q r000M0pqr 001m1p q r001 M1pqr 010m2p q r010 M2pqr 011m3p q r011 M3pqr 100m4p q r100M4pqr 101m5p q r101M5pqr 110m6p q r110M6pqr 111m7p q r111M7p, q, r 形成的极小项与极大项 8.定理定理2.4 设mi与Mi是命题变项p1,p2,……,pn形成的极小项和极大项，则┐mi Mi ， ┐Mi mi 9.主析取范式主析取范式(主合取范式主合取范式)Ø 设由n个命题变项构成的析取范式中所有的简单合取式都是极小项，则称该析取范式为主析取范式。
Ø设由n个命题变项构成的合取范式中所有的简单析取式都是极大项，则称该合取范式主合取范式 例如：(p→q) r(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) (p∧┐q∧┐r) ∨ (┐p∧┐q∧r)∨(┐p∧q∧r) ∨(┐p∧q∧r）∨(p∧q∧r) 例如：(p→q) r(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r) 10. 定理定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是唯一的Ø 如何求主析取范式（主合取范式）？• 首先求等价的析取范式（合取范式）• 然后对非极小项（或者非极大项）进行扩展A A ∨(P∧┐P) （A ∨ P）∧（ A ∨ ┐P ）A A ∧ (P ∨ ┐P) （A ∧ P） ∨ （ A ∧ ┐P ）• 最后，求出某公式的主析取范式（主合取范式）后，将极小项（极大项）都用名称写出，并且按极小项（极大项）名称的角标由小到大顺序排列 求A=(rp)(q(pr))的主析取范式例例1：解：(rp)(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) (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=(p→q) r的主析取范式 (p→q) r(p∧┐q∧┐r)∨(┐p∧r)∨(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) m4 ∨ m1 ∨ m3 ∨ m7求A=(p→q) r的主合取范式(p→q) r(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)(p∨q ∨ r)∧ (p∨ ┐ q ∨ r) ∧(┐ p ∨ ┐q∨r)∧(┐p∨q∨┐r)M0 M2 M6 M5 如何求一个公式的主析取范式？（1）利用等值转化法（2）利用真值表（3）通过主合取范式求逆 例例3：求命题公式p→q的主析取范式和主合取范式。
方法1：真值表法pqp →q001011100111p→qm0 m1 m4( p q) ( p q) ( p q) 方法2：公式法p→qp 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) (q r) 的主析取范式真值表法：pqr p p → 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 历史遗留问题: (1)我只给村里所有那些不给自己理发的人理发 (2)只要别人有困难,他就帮忙,除非困难解决.(3) a:别人有困难, b: 他帮忙(4) a b作业作业 ＰＰ38 5题（题（1 、、3）） 注意总结规律注意总结规律 6题（题（2) 作业问题: • 整体较好,都交了.• 个别书写不认真,应付私事。
• 注意“” 的书写P14 14题(10)除非天下大雨，否则他不乘车上班 p:天下大雨 q:他乘车上班 q → p(14) 2和4是素数，这是不对的15) p: 2是素数 q: 4是素数 (16) (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) 11.主析取范式的用途主析取范式的用途Ø 求公式的成真与成假赋值Ø 判断公式的类型Ø 判断两个命题公式是否等值Ø 应用主析取范式分析和解决实际问题 例1: 求 (p→q)→ (q∨p) 的成真赋值A m1∨m2∨…∨ms(p→q)→ (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 p→q q qp(p→q)→ (qp)00 1011101 1100010 0111111 01011 A m1∨m2∨…∨ms(1)A为重言式当且仅当其主析取范式包含2n个极小项(2) A为矛盾式当且仅当其主析取范式包不含极小项(3) A为可满足式当且仅当其主析取范式包至少含一个极小项例2：判断下列公式的类型(1) p→ (pq)(2) p(pq)(3) ( 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等值的充要条件是它们有相同的主析取范式。
例：问 (p→q)→r 与 p→(q→r) 是否等值(p→q)→r (pq) r (pq) r(pqr)(pqr) (pqr)(pqr)(pqr)m5 m4 m7 m3 m1p→(q→r) 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中挑选1~2名出国进修，由于工作需要，选派时要满足以下条件：（1）若A去，则B同去；（2）若B去，则C不能去；（3）若C不去，则A或B可以去问所里有哪些选派方案？解：设 p: A去; q: B去; r: C去则选派方案应满足：(p→r)(q→r)(r→(p q))(p→r)(q→r)(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 联结词的完备集 1. n元真值函数的定义元真值函数的定义 自变量：n个命题变项定义域：由0，1组成的长度为n的符号串全体。
2n） 值域：{0，1}思考：n个命题变项可构成多少个不同的真值函数？（22n）Ø 每个真值函数对应唯一一个主析取范式（主合取范式）Ø 每个真值函数对应无穷多个与之等值的命题公式Ø每个命题公式对应唯一一个真值函数 2.2.联结词完备联结词完备3. 设S是一个联结词集合，如果任何n(n≥1)元真值函数都可以由4.仅含S中的联结词构成的公式表示，则称S是联结词完备集3.3.定理定理2.6 S={┐,∧,∨}是联结词完备集 证：因为任何n(n≥1)元真值函数都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词┐,∧,∨，所以S={┐,∧,∨}是联结词完备集 推论推论 以下联结词集都是完备集： (1) S1={┐,∧,∨, →} (2) S2={┐,∧,∨,→, } (3) S3={┐,∧} (4) S4={┐,∨} (5) S5={┐,→} p∨q ┐┐( p∨q) ┐(┐p ∧ ┐q) 4. 与非联结词与非联结词• 根据需要，人们还可构造形式上更为简单的联结词完备集。
例如，在计算机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集Ø 设p、q为两个命题，复合命题“p与q的否定式”称作p,q的与非式与非式 记作p↑q即 p↑q ┐(p∧q）, 符号↑称作与非联结词Ø p↓q 表示或非式或非式 ，即p↓q ┐(p∨q） Ø 定理2.7 {↑}，{↓}都是联结词完备集 小小 结结1主要内容：Ø等值式 Ø基本的等值式Ø主析取范式与主合取范式Ø联结词完备2要求3熟练掌握等值演算4熟练掌握公式主析取范式（主合取范式）的求法5会用主析取范式解决一些问题6会将公式化为联结词完备集中的公式 一、下列说法正确的是一、下列说法正确的是: •A B 当且仅当AB是可满足式•A B 当且仅当A和B有相同的主析取范式 •若A为重言式,则A的主析取范式含有个 2n极小项•若A为矛盾式,则A的主析取范式为1•若A为矛盾式,则A的主合取范式为1•任何公式A都能等值的化为联结词{∧, ∨}中的公式•任何公式A都能等值的化为联结词集合{→, ┐, ∧}中的公式 二、用等值演算法来判断下列公式的类型、用等值演算法来判断下列公式的类型(p→q)∧r ∧q(p ∧q) ∧r ∧qp∧0∧r0 所有,该公式为矛盾式三、用主析取范式法来判断下列公式的类型三、用主析取范式法来判断下列公式的类型,并求其成真赋值并求其成真赋值(p→q) → ( 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 四、用主合取范式法来判断下列公式的类型四、用主合取范式法来判断下列公式的类型,并求其成假赋值并求其成假赋值(p→q) → ( p→ q)(pq) (p q ) (p q) p q(p p q) ( qp q) p qM1 该公式为可满足式, 成假赋值为01 五、五、已知公式A含3个命题变项p,q,r，并且它的成真赋值为001， 011,110，求A 的主合取范式和主析取范式。
解：成真赋值对应的极小项为：m1,m3,m6 故主析取范式为：A m1 m3 m6故主合取范式为 A M0 M2 M4 M5 M7 六、用等值演算证明下属等值式六、用等值演算证明下属等值式(p q)(p q) (p q) (p q)证： (p q)(p q) (p p) (p q) ( q p) ( q q) (p q) ( q p) (p q) (p q) 七、将下列公式化成与之等值且仅含七、将下列公式化成与之等值且仅含{→，， }的公式的公式(pq)r( (pq) r)((pq) → r)((p → q) → r)(pq)r(p → q) r((p → q) r)((p → q) → r) 。
