离散数学 ch2

1、东北石油大学东北石油大学离散数学离散数学Discrete Mathematics(第第2章章)School of Software, Northeast Petroleum University2Northeast Petroleum University计算机学院计算机学院School of computer & information technology本章主要内容本章主要内容第二章第二章 命题逻辑等值演算命题逻辑等值演算v 等值式与基本的等值式等值式与基本的等值式v 等值演算与置换规则等值演算与置换规则v 析取范式与合取范式，主析取范式与主合取范式析取范式与合取范式，主析取范式与主合取

2、范式v 联结词完备集联结词完备集v 可满足性问题与消解法可满足性问题与消解法本章本章10个定义，个定义，10个定理。个定理。本章与其他章的关系本章与其他章的关系v 是第一章的抽象与延伸是第一章的抽象与延伸v 是后续各章的先行准备是后续各章的先行准备3Northeast Petroleum University计算机学院计算机学院School of computer & information technology2.1 等值式等值式几点说明：几点说明： (1) 定义中，定义中，A, B, 均为元语言符号均为元语言符号(一一) 等值式概念等值式概念p, q, r, , (p q) ( p q)

3、对象语言对象语言 A B 元语言元语言(2) A或或B中可能有哑元出现中可能有哑元出现. 例如例如 pq ( p q) ( r r) r为左边公式的哑元为左边公式的哑元.定义定义2.1 若等价式若等价式AB是重言式，则称是重言式，则称 A 与与 B 等值等值, 记作记作 AB，并称，并称AB是是等值式等值式(3) 判断两个公式是否等值可用真值表。判断两个公式是否等值可用真值表。AB等价式等价式等值式等值式AB重言式重言式-4Northeast Petroleum University计算机学院计算机学院School of computer & information technology例题例

4、题例例1 判断下列各组公式是否等值判断下列各组公式是否等值:结论结论: : p(qr) (p q) r (2) p(qr) 与与 (pq) r (1) p(qr) 与与 (p q)r结论结论: : p(qr) 与与 (pq) r 不等值不等值5Northeast Petroleum University计算机学院计算机学院School of computer & information technology(二二) 基本等值式基本等值式(1) 双重否定律双重否定律(2) 幂等律幂等律(3) 交换律交换律(4) 结合律结合律(5) 分配律分配律 (6) 德摩根律德摩根律 (7) 吸收律吸收律 A

5、AA AA, A AAA BB A, A BB A(A B) CA (B C), (A B) CA (B C)A (B C)(A B) (A C), A (B C)(A B) (A C) (A B)AB (A B)ABA (A B)A, A (A B)A6Northeast Petroleum University计算机学院计算机学院School of computer & information technology(二二) 基本等值式基本等值式(8) 零律零律(9) 同一律同一律(10) 排中律排中律(11) 矛盾律矛盾律(12) 蕴涵等值式蕴涵等值式(13) 等价等值式等价等值式(14)

6、 假言易位假言易位(15) 等价否定等值式等价否定等值式(16) 归谬论归谬论A 11, A 00A 0A. A 1AAA1AA0ABA BAB(AB) (BA)ABBAABAB(AB) (AB) A特别提示：必须牢记这特别提示：必须牢记这16组等值式，这是继续学习的基础。组等值式，这是继续学习的基础。7Northeast Petroleum University计算机学院计算机学院School of computer & information technology(三三) 等值演算与置换规则等值演算与置换规则1. 等值演算等值演算:2. 置换规则置换规则:由已知的等值式推演出新的等值式的过

7、程由已知的等值式推演出新的等值式的过程假设假设: (A) 是含公式是含公式 A 的命题公式的命题公式 (B) 是用公式是用公式B置换置换 (A)中所有的中所有的 A后得到的命题公式后得到的命题公式. 若若 BA，则，则 (B)(A). AB A B (AB) = (AB) C (AB) C ( A B) C ( A B) = ( A B) C8Northeast Petroleum University计算机学院计算机学院School of computer & information technology(四四) 等值演算应用举例等值演算应用举例1 证明两个公式等值证明两个公式等值 例例2

8、证明证明 (pq)r (pr) (qr)注意：用等值演算不能直接证明两个公式不等值注意：用等值演算不能直接证明两个公式不等值 例例3 证明证明 (pq)r 与与p(qr)不等值不等值2 判断公式类型判断公式类型 A为矛盾式当且仅当为矛盾式当且仅当A 0 A为重言式当且仅当为重言式当且仅当A 1例例4 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型 (1) (pq)pq (2) (p(pq)r (3) p(pq) p)q) 重言式重言式矛盾式矛盾式可满足式可满足式易知易知000, 010是左边成真赋值，右边成假赋值。是左边成真赋值，右边成假赋值。9Northeast Petrole

9、um University计算机学院计算机学院School of computer & information technology2.2 析取范式与合取范式析取范式与合取范式1 文字文字:2 简单析取式简单析取式:3 简单合取式简单合取式:4 析取范式析取范式:5 合取范式合取范式:6 范式范式:(一一) 范式定义范式定义说明：说明：v 单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式v 形如形如 pq r, p qr 的的公式既是析取范式，又是合取公式既是析取范式，又是合取范式范式命题变项及其否定的总称命题变项及其否定的总称有限个文字构成的析取式有限个文字构成的

10、析取式有限个文字构成的合取式有限个文字构成的合取式由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式析取范式与合取范式的总称析取范式与合取范式的总称10Northeast Petroleum University计算机学院计算机学院School of computer & information technology(二二) 范式性质范式性质定理定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含有某一个简单析取式是重言式当且仅当它同时含有某 个命题变项和它的否定式个命题变项和它的否定式.(2) 一个简单合取式是矛盾式

11、当且仅当它同时含有某一个简单合取式是矛盾式当且仅当它同时含有某 个命题变项和它的否定式个命题变项和它的否定式.定理定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合取一个析取范式是矛盾式当且仅当它每个简单合取 式都是矛盾式式都是矛盾式.(2) 一个合取范式是重言式当且仅当它的每个简单析一个合取范式是重言式当且仅当它的每个简单析 取式都是重言式取式都是重言式.11Northeast Petroleum University计算机学院计算机学院School of computer & information technology(三三) 范式求解方法范式求解方法定理定理2.3 (范式存在

12、定理范式存在定理) 任何命题公式都存在与之等值的析取范式与合取范式任何命题公式都存在与之等值的析取范式与合取范式 求公式求公式A的范式的步骤：的范式的步骤：(1) 消去消去A中的中的 , (若存在若存在) (2) 否定联结词否定联结词 的内移或消去的内移或消去 (3) 使用分配律使用分配律12Northeast Petroleum University计算机学院计算机学院School of computer & information technology例例5 求求(pq) r的析取范式与合取范式的析取范式与合取范式解解 (1) (pq) r ( pq) r (消去消去 ( pq)r)(r(

13、 pq) (消去消去 ( ( pq)r)( r pq) (消去消去 (p q)r)( pq r) (否定号内移否定号内移) (pr)( qr)( pq r) (对对分配律分配律) (2) (pq) r (p q)r)( pq r) (p q p )(p qq)(p q r) (r p)(rq)(r r) (p q r)( pr)(qr)(三三) 范式求解方法范式求解方法13Northeast Petroleum University计算机学院计算机学院School of computer & information technology(四四) 极小项与极大项极小项与极大项定义定义2.4: 极

14、小项与极大项极小项与极大项(假设共有假设共有n个命题变项个命题变项)极小项极小项: (1) 必须是简单合取式必须是简单合取式; (2) 每个命题变项必须以文字形式出现且仅出现一次每个命题变项必须以文字形式出现且仅出现一次; (3) 每个文字必须按顺序出现每个文字必须按顺序出现; 称这样的简单合取式为称这样的简单合取式为极小项极小项.极大项极大项: (1) 必须是简单析取式必须是简单析取式; (2) 每个命题变项必须以文字形式出现且仅出现一次每个命题变项必须以文字形式出现且仅出现一次; (3) 每个文字必须按顺序出现每个文字必须按顺序出现; 称这样的简单合取式为称这样的简单合取式为极大项极大项.

15、14Northeast Petroleum University计算机学院计算机学院School of computer & information technology(四四) 极小项与极大项极小项与极大项(1) n个命题变项有个命题变项有2n个极小项和个极小项和2n个极大项个极大项(2) 2n个极小项均互不等值个极小项均互不等值; 2n个极大项均互不等值个极大项均互不等值(3) 第第i个极小项名称为个极小项名称为mi , 其中其中i是该极小项成真赋值的是该极小项成真赋值的 十进制表示十进制表示. (4) 第第i个极大项名称为个极大项名称为Mi , 其中其中i是该极大项成假赋值的是该极大项成

16、假赋值的 十进制表示十进制表示. 几点说明几点说明:15Northeast Petroleum University计算机学院计算机学院School of computer & information technology(五五) 极小项极大项实例极小项极大项实例由两个命题变项由两个命题变项 p, q 形成的极小项与极大项形成的极小项与极大项极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 pq p qpqp q p q pq p q pq 0 00 11 01 1 0 00 11 01 1 m0m1m2m3M0M1M2M316Northeast Pet

17、roleum University计算机学院计算机学院School of computer & information technology(五五) 极小项极大项实例极小项极大项实例极小项极小项极大项极大项公式公式成真赋值成真赋值 名称名称公式公式成假赋值成假赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r p q r0 0 00 0 10 1 0

18、0 1 11 0 01 0 11 1 01 1 1 M0M1M2M3M4M5M6M7由三个命题变项由三个命题变项 p, q, r 形成的极小项与极大项形成的极小项与极大项. mi与与Mi的关系的关系(定理定理2.4)： mi Mi , Mi mi 17Northeast Petroleum University计算机学院计算机学院School of computer & information technology(六六) 主析取范式与主合取范式主析取范式与主合取范式定义定义2.5 主析取范式主析取范式 主合取范式主合取范式例如：例如：n=3, 命题变项为命题变项为 p, q, r 时，时，

19、( pq r) ( p q r) m1 m3 (p qr) ( pqr) M1 M7 由极小项构成的析取范式由极小项构成的析取范式由极大项构成的合取范式由极大项构成的合取范式 任何命题公式都存在与之等值的主析取范式和主合取任何命题公式都存在与之等值的主析取范式和主合取 范式范式, 并且是唯一的。并且是唯一的。主析取范式主析取范式 主合取范式主合取范式定理定理2.5 (主范式的存在唯一定理主范式的存在唯一定理)18Northeast Petroleum University计算机学院计算机学院School of computer & information technology(七七) 求主范式

20、的步骤求主范式的步骤求主析取范式的步骤求主析取范式的步骤:设设 A 含含n命题变项命题变项p1, p2, , pn(1) 求析取范式求析取范式 A =B1 B2 Bs , 其中其中Bj是简单合取式是简单合取式(2) 若若 Bj 既不含既不含 pi , 又不含又不含 pi , 则将则将 Bj 展开成展开成 Bj Bj (pipi) (Bj pi) (Bj pi) 重复这个过程重复这个过程, 直到所有简单合取式都是长度为直到所有简单合取式都是长度为n的极的极 小项为止小项为止(3) 消去重复出现的极小项消去重复出现的极小项, 即用即用mi代替代替mi mi(4) 将极小项按下标从小到大排列将极小项

21、按下标从小到大排列19Northeast Petroleum University计算机学院计算机学院School of computer & information technology(七七) 求主范式的步骤求主范式的步骤求主合取范式的步骤求主合取范式的步骤:设设A含含n个命题变项个命题变项p1,p2,pn(1) 求析取范式求析取范式 A =B1 B2 Bs , 其中其中Bj是简单析取式是简单析取式 (2) 若某个若某个 Bj 既不含既不含 pi , 又不含又不含 pi , 则将则将 Bj 展开成展开成 Bj Bj (pi pi) (Bj pi) (Bjpi) 重复这个过程重复这个过程,

22、直到所有简单析取式都是长度为直到所有简单析取式都是长度为n的极的极 大项为止大项为止(3) 消去重复出现的极大项消去重复出现的极大项, 即用即用 Mi 代替代替Mi Mi(4) 将极大项按下标从小到大排列将极大项按下标从小到大排列20Northeast Petroleum University计算机学院计算机学院School of computer & information technology(八八) 求主范式求主范式实例实例例例6 求公式求公式 (pq)r 的主析取范式和主合取范式的主析取范式和主合取范式解解 (pq)r (p q) r (析取范式析取范式) (p q) (p q) (

23、r r) (p qr) (p q r) m6 m7 r ( p p) ( q q) r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7 , 代入代入并排序，得并排序，得 (pq)r m1 m3 m5 m6 m7 (主析取范式主析取范式)21Northeast Petroleum University计算机学院计算机学院School of computer & information technology(八八) 求主范式求主范式实例实例 (pq)r (p r) (q r) (合取范式合取范式) p r p (qq) r (p q r) (pq r) M0

24、 M2 q r (pp) q r (p q r) ( p q r) M0 M4 , 代入代入 并排序，得并排序，得 (pq)r M0 M2 M4 (主合取范式主合取范式)22Northeast Petroleum University计算机学院计算机学院School of computer & information technology例如例如 (pq)r m1 m3 m4 m7成真赋值为：成真赋值为：成假赋值为：成假赋值为： (九九) 主范式的应用主范式的应用1.求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值001, 011, 100, 111000, 010, 101, 1102.

25、 判断公式的类型判断公式的类型 A的主析取范式含全部的主析取范式含全部2n个极小项个极小项 A的主合取范式不含任何极大项的主合取范式不含任何极大项, 记为记为1A为重言式为重言式 A的主合取范式含全部的主合取范式含全部2n个极大项个极大项 A的主析取范式不含任何极小项的主析取范式不含任何极小项, 记为记为0A为矛盾式为矛盾式 A的主析取范式至少含一个但非全部极小项的主析取范式至少含一个但非全部极小项 A的主合取范式至少含一个但非全部极大项的主合取范式至少含一个但非全部极大项A为非重言式的可满足式为非重言式的可满足式23Northeast Petroleum University计算机学院计算机

26、学院School of computer & information technology例例7 用主范式判断公式的类型用主范式判断公式的类型 (1) (pq) q (2) p(p q) (3) (p q)r(九九) 主范式的应用主范式的应用解解 (1) ( p q) q ( pq) q 0 矛盾式矛盾式 (2) p (p q) 1 重言式重言式 (3) (p q) r ( pq) r ( p r) ( q r) ( pq r) ( p q r) ( pq r) (pq r) M2 M4 M6 非重言式的可满足式非重言式的可满足式24Northeast Petroleum University

27、计算机学院计算机学院School of computer & information technology3. 判断两个公式是否等值判断两个公式是否等值例例8 用主范式判以下每一组公式是否等值用主范式判以下每一组公式是否等值 p(qr) 与与 (p q)r p(qr) 与与 (pq)r(九九) 主范式的应用主范式的应用解解 p(qr) p q r M6 (p q)r (p q) r p q r M6 (pq)r ( p q) r (p q) r (p r) ( q r) (p q r) (p q r) (p q r) ( p q r) M0 M2 M6显见，显见，中的两公式等值，而中的两公式等

28、值，而的不等值的不等值.25Northeast Petroleum University计算机学院计算机学院School of computer & information technology4. 解实际问题解实际问题例例9 某单位要从某单位要从A,B,C三人中选派若干人出国考察三人中选派若干人出国考察, 需满足下需满足下 述条件述条件: (1) 若若A去去, 则则C必须去必须去; (2) 若若B去去, 则则C不能去不能去; (3) A和和B必须去一人且只能去一人必须去一人且只能去一人. 问有几种可能的选派方案问有几种可能的选派方案?(九九) 主范式的应用主范式的应用解解 记记 p:派派A去

29、去, q:派派B去去, r:派派C去去 (1) pr, (2) qr, (3) (pq) ( p q) 求下式的成真赋值求下式的成真赋值 A=(pr) (qr) (pq) ( p q)26Northeast Petroleum University计算机学院计算机学院School of computer & information technology求求A的主析取范式的主析取范式 A=(pr) (qr) (pq) ( p q) ( p r) ( qr) (pq) ( p q) ( pq) ( pr) (rq) (rr) (pq) ( p q) ( pq) (pq) ( pr) (pq) (r

30、q) (pq) ( pq) ( p q) ( pr) ( p q) (rq) ( p q) (pq r) ( p qr)成真赋值成真赋值:101,010结论结论: 方案方案1 派派A与与C去去, 方案方案2 派派B去去(九九) 主范式的应用主范式的应用27Northeast Petroleum University计算机学院计算机学院School of computer & information technology1 由主析取范式确定主合取范式由主析取范式确定主合取范式(十十) 两种主范式的转化两种主范式的转化3 主范式个数主范式个数4 主范式与真值表主范式与真值表:2 由主合取范式确定主

31、析取范式由主合取范式确定主析取范式28Northeast Petroleum University计算机学院计算机学院School of computer & information technology2.3 联结词的完备集联结词的完备集 定义定义2.6 1元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFFF:0,1n 0,1 n22n个命题变项共可构成个命题变项共可构成 个不同的个不同的n元真值函数元真值函数. 举例(一一) 真值函数真值函数29Northeast Petroleum University计算机学院计算机学院Schoo

32、l of computer & information technology举例举例p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF2元真值函数元真值函数30N

33、ortheast Petroleum University计算机学院计算机学院School of computer & information technology(二二)真值函数与命题公式的关系真值函数与命题公式的关系 1 每个真值函数与许多命题公式等值每个真值函数与许多命题公式等值(一对多映射一对多映射)。)2(0F所有矛盾式所有矛盾式 )2(15F所有重言式所有重言式 )2(13Fpq (pq) (pq) )2(0Fm0 )2(1Fm1 )2(2Fm2 )2(3Fm2 m3 pq, p q 都对应都对应)2(13F2 任何一个含任何一个含n个命题变项的命题公式个命题变项的命题公式A都对应

34、唯一的都对应唯一的n元元 真值函数真值函数 F , F 恰好为恰好为A的真值表的真值表. 3 每个真值函数与唯一主范式等值每个真值函数与唯一主范式等值(一对一映射一对一映射)。4 等值的公式对应的真值函数相同等值的公式对应的真值函数相同. 31Northeast Petroleum University计算机学院计算机学院School of computer & information technology(三三) 联结词完备集联结词完备集定义定义2.7: 联结词完备集联结词完备集 设设S是一个联结词集合是一个联结词集合, 如果任何如果任何n(n 1)元真值函数元真值函数都可以由仅含都可以由仅

35、含S中的联结词构成的公式表示中的联结词构成的公式表示, 则称则称 S是是联结词完备集联结词完备集。定理定理2.6 S = , , 是联结词完备集是联结词完备集证明证明: 在主析取范式中在主析取范式中, 仅含联结词仅含联结词 , , 。因为任何因为任何n元真元真 值函数都与唯一主析取范式等值值函数都与唯一主析取范式等值, 所以所以S是联结词完备是联结词完备 集。集。32Northeast Petroleum University计算机学院计算机学院School of computer & information technology(三三) 联结词完备集联结词完备集推论推论 以下都是联结词完备集

36、以下都是联结词完备集 (1) S1 = , , , (2) S2 = , , , , (3) S3 = , (4) S4 = , (5) S5 = , 证明证明 (1), (2) 在联结词完备集中加入新的联结词后仍为完备集在联结词完备集中加入新的联结词后仍为完备集 (3) 因因 , , 是完备集，是完备集，A B ( AB) 故故 , 是完备集。是完备集。 (4) 因因 , , 是完备集，是完备集， A B ( AB) 故故 , 是完备集。是完备集。 (5) 因因 , 是完备集，是完备集，A BA B 故故 , 是完备集。是完备集。33Northeast Petroleum Universit

37、y计算机学院计算机学院School of computer & information technology(四四) 单元素完备集单元素完备集定义定义2.8 与非联结词；或非联结词与非联结词；或非联结词设设 p, q为两个命题为两个命题, (p q)称作称作p与与q的的与非式与非式,记作记作 p q, 称为称为与非联结词与非联结词 (p q)称作称作p与与q的的或非式或非式,记作记作 p q, 称为称为或非联结词或非联结词定理定理2.7 与与 为联结词完备集为联结词完备集. 证明证明 , , 为完备集为完备集 p (p p) p p p q ( pq) pq (p p) (q q) p q (

38、p q) (p q) (p q) (p q) 得证得证 为联结词完备集为联结词完备集. 对对 类似可证类似可证34Northeast Petroleum University计算机学院计算机学院School of computer & information technology第二章第二章 小结小结l 等值式概念等值式概念l 16组基本等值式组基本等值式l 置换规则及等值演算置换规则及等值演算l 概念概念: 文字、简单析取式、简单合取式、析取范式、合取文字、简单析取式、简单合取式、析取范式、合取 范式、极小项、极大项、主析取范式、主合取范式。范式、极小项、极大项、主析取范式、主合取范式。l

39、主范式的求法主范式的求法(等值演算、真值表等值演算、真值表)l 主范式的应用主范式的应用: 求公式的成真赋值、成假赋值、判断公式求公式的成真赋值、成假赋值、判断公式 的类型、判断公式是否等值的类型、判断公式是否等值l 联结词完备集联结词完备集l 命题逻辑概念及运算的简单应用命题逻辑概念及运算的简单应用35Northeast Petroleum University计算机学院计算机学院School of computer & information technology巩固练习巩固练习1:概念概念1. 设设A与与B为含为含n个命题变项的公式，判断下列命题是否为真？个命题变项的公式，判断下列命题是

40、否为真？ (1) AB当且仅当当且仅当A与与B有相同的主析取范式有相同的主析取范式 (2) 若若A为重言式，则为重言式，则A的主合取范式为的主合取范式为0 (3) 若若A为矛盾式，则为矛盾式，则A的主析取范式为的主析取范式为1 (4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式 (5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公式说明说明:(2) 重言式的主合取范式不含任何极大项重言式的主合取范式不含任何极大项, 记为记为1. (3) 矛盾式的主析矛盾式的主析取取范式不含任何极小项范式不含任何极小项, 记为记为0. (4) , 不是完备集，如矛

41、盾式不能写成不是完备集，如矛盾式不能写成 , 中的公式中的公式. (5) , 是完备集是完备集. 真真假假假假假假真真36Northeast Petroleum University计算机学院计算机学院School of computer & information technology巩固练习巩固练习2: 判断公式类型判断公式类型2. 判断下列公式的类型判断下列公式的类型: (1) (pq)( qp)重言式重言式解解 用等值演算法求主范式用等值演算法求主范式 (pq)( qp) ( p q) (qp) (pq) (qp) (p q p) ( q qp) 1(2) (pq) q解解 用等值演算

42、法求公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0矛盾式矛盾式37Northeast Petroleum University计算机学院计算机学院School of computer & information technology(3) (pq)p巩固练习巩固练习2: 判断公式类型判断公式类型(续续)非重言式的可满足式非重言式的可满足式解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式38Northeast Petroleum University计算机学

43、院计算机学院School of computer & information technology 巩固练习巩固练习3: 求公式的主范式求公式的主范式3 已知命题公式已知命题公式A中含中含3个命题变项个命题变项p, q, r，并知道它的成真，并知道它的成真 赋值为赋值为001, 010, 111, 求求A的主析取范式和主合取范式，及的主析取范式和主合取范式，及A对应的真值函数对应的真值函数.解解A的主析取范式为的主析取范式为m1 m2 m7A的主合取范式为的主合取范式为M0 M3 M4 M5 M6 p q r F p q r F0 0 0 0 1 0 0 00 0 1 1 1 0 1 00 1

44、 0 1 1 1 0 00 1 1 0 1 1 1 1p q r F p q r F0 0 0 0 1 0 0 00 0 1 1 1 0 1 00 1 0 1 1 1 0 00 1 1 0 1 1 1 139Northeast Petroleum University计算机学院计算机学院School of computer & information technology巩固练习巩固练习4: 联结词完备集联结词完备集4将将A = (pq) r改写成下述各联结词集中的公式改写成下述各联结词集中的公式: (1) , , (2) , (3) , (4) , (5) (6) 解解 (1) (pq) r

45、 ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)40Northeast Petroleum University计算机学院计算机学院School of computer & information technology巩固练习巩固练习4: 联结词完备集联结词完备集(续续) (4) (pq) r ( (pq)r) (pq)r) (5) (pq) r (p q) r (p q) r (p q) r) (p q) r) (p q) r) (6) (pq) r ( pq) r ( ( pq)r) ( pq)r (p p) (q q) (r

46、 r) 说明说明: 答案不唯一答案不唯一41Northeast Petroleum University计算机学院计算机学院School of computer & information technology巩固练习巩固练习5: 应用题应用题5. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选某公司要从赵、钱、孙、李、周五名新毕业的大学生中选 派一些人出国学习派一些人出国学习. 选派必须满足以下条件：选派必须满足以下条件： (1) 若赵去，钱也去若赵去，钱也去. (2) 李、周两人中至少有一人去李、周两人中至少有一人去. (3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人. (4)

47、 孙、李两人同去或同不去孙、李两人同去或同不去. (5) 若周去，则赵、钱也去若周去，则赵、钱也去. 用等值演算法分析该公司如何选派他们出国？用等值演算法分析该公司如何选派他们出国？42Northeast Petroleum University计算机学院计算机学院School of computer & information technology巩固练习巩固练习5: 应用题应用题(续续)解此类问题的步骤：解此类问题的步骤： 1.设简单命题并符号化设简单命题并符号化 2. 用复合命题描述各条件用复合命题描述各条件 3. 写出由复合命题组成的合取式写出由复合命题组成的合取式 4. 将合取式化成

48、析取式将合取式化成析取式(最好是主析取范式最好是主析取范式) 5. 求成真赋值求成真赋值, 并做出解释和结论并做出解释和结论43Northeast Petroleum University计算机学院计算机学院School of computer & information technology巩固练习巩固练习5: 应用题应用题(续续)解解 1. 设简单命题并符号化设简单命题并符号化 2. 写出复合命题写出复合命题 (1) 若赵去，钱也去若赵去，钱也去 (2) 李、周两人中至少有一人去李、周两人中至少有一人去 (3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人 (4) 孙、李两人同去或同不

49、去孙、李两人同去或同不去 (5) 若周去，则赵、钱也去若周去，则赵、钱也去pqs u(qr) ( q r)(r s) ( rs)u(p q) 设设 p: 派赵去派赵去, q: 派钱去派钱去, r: 派孙去派孙去, s: 派李去派李去, u: 派周去派周去 44Northeast Petroleum University计算机学院计算机学院School of computer & information technology3. 设设(1)(5)构成的合取式为构成的合取式为A 巩固练习巩固练习5: 应用题应用题(续续)4. 化成析取式化成析取式A = (pq) (s u) (qr) ( q r)

50、 (r s) ( rs) (u(p q)结论：由上述析取式可知，结论：由上述析取式可知，A的成真赋值为的成真赋值为00110与与11001， 派孙、李去派孙、李去(赵、钱、周不去赵、钱、周不去) 派赵、钱、周去派赵、钱、周去(孙、李不去孙、李不去)A ( pq r su) (p qrs u)45Northeast Petroleum University计算机学院计算机学院School of computer & information technology巩固练习巩固练习5: 应用题应用题(续续)A ( p q) (qr) ( q r) (s u) ( u (p q) (r s) ( rs)

51、 B1=( p q) (qr) ( q r) ( p qr) ( pq r) (qr) (分配律分配律)B2=(s u) ( u (p q) (su) (p q s) (p q u) (分配律分配律)B1 B2 ( p qr su) ( pq r su) (qr su) (p qr s) (p qr u)再令再令 (r s) ( rs)=B3，则，则 B1 B2 B3 ( pq r su) (p qrs u)46Northeast Petroleum University计算机学院计算机学院School of computer & information technology习题二习题二(部分

52、习题解答部分习题解答)3 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型, 并求出成真赋值。并求出成真赋值。 (1) (p qq)解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (p qq) ( ( p q) q) ( p q)q 0 主析取范式主析取范式矛盾式矛盾式47Northeast Petroleum University计算机学院计算机学院School of computer & information technology习题二习题二(部分习题解答部分习题解答) (2) (p(p q) (pr)解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (

53、p(p q) (pr) ( p (p q) ( p r) p p q r 1 主主合合取范式取范式重言式重言式48Northeast Petroleum University计算机学院计算机学院School of computer & information technology习题二习题二(部分习题解答部分习题解答) (3) (p q)(p r)解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (p q)(p r) (p q) (p r) ( pq) (p r) ( pq ( r r) (p ( q q) r) ( pqr) ( pq r) (pq r) (p q r) m0 m1

54、 m5 m7 主析取范式主析取范式非重言式的可满足式非重言式的可满足式成真赋值成真赋值: 000, 001, 101, 11149Northeast Petroleum University计算机学院计算机学院School of computer & information technology习题二习题二(部分习题解答部分习题解答)4 用等值演算法证明下面等值式用等值演算法证明下面等值式(1) p (p q) (pq)(2) (pq) (pr) (p(q r)(3) (pq) (p q)(p q)(4) (pq) ( p q) (p q)(p q)证明证明:(1) p p (qq) (p q

55、) (pq)(2) (p(q r) ( p (q r) ( p q) ( p r) (pq) (pr)(3) (p q)(p q) (p q) ( pq) (pp) (p q) (qp) (qq) (pq) (qp) ( p q) ( q p) (pq) (qp) (pq) (4) (pq) ( p q) (pp) (p q) ( qp) ( q q) (p q)(p q)50Northeast Petroleum University计算机学院计算机学院School of computer & information technology习题二习题二(部分习题解答部分习题解答)5 求下列公式

56、的主析取范式，并求成真赋值。求下列公式的主析取范式，并求成真赋值。(1) ( pq)( q p)(2) ( pq) (q r)解解: (1) ( pq)( q p) (p q) ( q p) ( pq) (p ( q q) ( p p)q) ( pq) (pq) (p q) ( pq) (pq) ( pq) (pq) (p q) m0 m2 m3 成真赋值成真赋值: 00, 10, 11 (2) ( pq) (q r) (p q) (q r) (p q r) ( p p) q r) (p q r) ( p q r) (p q r) m3 m7 成真赋值成真赋值: 011, 11151North

57、east Petroleum University计算机学院计算机学院School of computer & information technology习题二习题二(部分习题解答部分习题解答) (3) (p (q r)(p q r)解解 用等值演算法求公式的主析取范式用等值演算法求公式的主析取范式 (p (q r)(p q r) ( p ( qr) (p q r) ( p p q r) ( qr p q r) 1 (重言式重言式) 成真赋值成真赋值: 000, 001, 010, 011, 100, 101, 110, 11152Northeast Petroleum University计算机学院计算机学院School of computer & information technology习题二习题二(部分习题解答部分习题解答)解解 (1) (qp)p ( qp)p q pp 0 (矛盾式矛盾式) 成假赋值成假赋值: 00, 01, 10, 11 (2) (p q) ( p r)( p p r) ( p q r)( p q r)M4 成假赋值成假赋值: 100 (3) (p(p q) r p p q r 1 重言式重言式, 无成假赋值无成假赋值6 求下列公式的主合取范式，并求成