离散数学第二章-命题逻辑等值演算ppt课件.ppt

《离散数学第二章-命题逻辑等值演算ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章-命题逻辑等值演算ppt课件.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 命题逻辑等值演算第二章 命题逻辑等值演算2.1 等值式与等值演算等值式与等值演算 等值式与基本等值式等值式与基本等值式 真值表法与等值演算法真值表法与等值演算法2.2 范式范式 析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式等值式等值式等值式:若等价式若等价式AB是重言式是重言式, 则称则称A与与B等值等值, 记作记作AB, 并称并称AB是是等值式等值式说明说明: (1) 是是元语言符号元语言符号, 不要混同于不要混同于和和=(2) A与与B等值当且仅当等值当且仅当A与与B在所有可能赋值下的真值都相在所有可能赋值下的真值都相同同, 即即A与与B有相同

2、的真值表有相同的真值表(3) n个命题变项的真值表共有个命题变项的真值表共有 个个, 故每个命题公式都有故每个命题公式都有无穷多个等值的命题公式无穷多个等值的命题公式(4) 可能有哑元出现可能有哑元出现. 在在B中出现中出现, 但不在但不在A中出现的命题变中出现的命题变项称作项称作A的的哑元哑元. 同样同样,在在A中出现中出现, 但不在但不在B中出现的命题变中出现的命题变项称作项称作B的哑元的哑元. 哑元的值不影响命题公式的真值哑元的值不影响命题公式的真值.n22真值表法例例1 判断判断 (p q) 与与 p q 是否等值是否等值解解结论结论: (p q) ( p q) p q p q p q

3、 (p q) p q (p q)( p q) 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1真值表法(续)例例2 判断下述判断下述3个公式之间的等值关系个公式之间的等值关系: p(qr), (pq)r, (p q)r解解 p q r p(qr) (pq)r (p q)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)与与(p q)r等值等值, 但与但与(pq)r

4、不等值不等值基本等值式双重否定律双重否定律 AA幂等律幂等律 A AA, A AA交换律交换律 A 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)AB吸收律吸收律 A (A B)A, A (A B)A基本等值式(续)零律零律 A 11, A 00 同一律同一律 A 0A, A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB) (BA)假言易位假言易位

5、ABBA等价否定等值式等价否定等值式 ABAB归谬论归谬论 (AB) (AB) A等值演算等值演算等值演算: 由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则: 若若AB, 则则 (B) (A) 例例3 证明证明 p(qr) (p q)r证证 p(qr) p ( q r) （蕴涵等值式）（蕴涵等值式） ( pq) r （结合律）（结合律） (p q) r （德摩根律）（德摩根律） (p q) r （蕴涵等值式）（蕴涵等值式）实例等值演算不能直接证明两个公式不等值等值演算不能直接证明两个公式不等值. 证明两个公式不证明两个公式不等值的基本思想是找到一个赋值

6、使一个成真等值的基本思想是找到一个赋值使一个成真, 另一个成假另一个成假.例例4 证明证明: p(qr) (pq) r方法一方法一 真值表法（见例真值表法（见例2）方法二方法二 观察法观察法. 容易看出容易看出000使左边成真使左边成真, 使右边成假使右边成假.方法三方法三 先用等值演算化简公式先用等值演算化简公式, 再观察再观察.实例例例5 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1) q(pq) 解解 q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）

7、（矛盾律） 0 （零律）（零律）该式为矛盾式该式为矛盾式.实例(续)(2) (pq)( qp) 解解 (pq)( qp) ( p q)(qp) （蕴涵等值式）（蕴涵等值式） ( p q)( p q) （交换律）（交换律） 1该式为重言式该式为重言式.实例(续)(3) (p q) (pq) r) 解解 (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）非重言式的可满足式非重言式的可满足式. .如如101是它的成真赋值是它的成真赋值, ,000是它的是它的成假赋值成假赋值.总结总结:A为矛盾式当且仅当为矛盾式当且仅当

8、A0; A为重言式当且仅当为重言式当且仅当A1说明说明:演算步骤不惟一演算步骤不惟一, ,应尽量使演算短些应尽量使演算短些2.2 范式2.2.1 析取范式与合取范式析取范式与合取范式 简单析取式与简单合取式简单析取式与简单合取式 析取范式与合取范式析取范式与合取范式2.2.2 主析取范式与主合取范式主析取范式与主合取范式 极小项与极大项极小项与极大项 主析取范式与主合取范式主析取范式与主合取范式 主范式的用途主范式的用途简单析取式与简单合取式文字（文字（lettersletters）: :命题变项及其否定的统称命题变项及其否定的统称简单析取式简单析取式: :有限个文字构成的析取式有限个文字构成

9、的析取式( (也叫子句也叫子句（clause）) )如如 p, q, pq, p q r, 简单合取式简单合取式: :有限个文字构成的合取式有限个文字构成的合取式( (也叫子句也叫子句（phrase）) )如如 p, q, pq, p q r, 注意：一个文字既是简单析取式、又是简单合取式。注意：一个文字既是简单析取式、又是简单合取式。定理定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定某个命题变项和它的否定(2) 一个简单合取式是矛盾式当且仅当它同时含某个命题一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定变项

10、和它的否定析取范式与合取范式析取范式析取范式(disjunctive normal form)(disjunctive normal form) : :由有限个简单合由有限个简单合取式组成的析取式取式组成的析取式 A1 A2Ar, 其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式(conjunctive normal form)(conjunctive normal form) : :由有限个简单析由有限个简单析取式组成的合取式取式组成的合取式 A1 A2Ar , 其中其中A1,A2,Ar是是简单析取式简单析取式范式范式: :析取范式与合取范式的统称析取范式与合取范式的统称 定

11、理定理2.2 (1) 一个析取范式是矛盾式当且仅当它的每一个一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式简单合取式都是矛盾式(2) 一个合取范式是重言式当且仅当它的每一个简单析取一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式式都是重言式范式存在定理定理定理2.3 任何命题公式都存在着与之等值的析取范式与合任何命题公式都存在着与之等值的析取范式与合取范式取范式. .证证 求公求公式式A的范式的步骤：的范式的步骤：(1) 消去消去A中的中的, ABA B AB( A B) (AB)(2) 否定联结词否定联结词 的内移或消去的内移或消去 A A (A B)AB (A B)A

12、B范式存在定理(续)(3) 使用分配律使用分配律 A (B C)(A B) (A C) 求求合取合取范式范式 A (B C) (A B) (A C) 求求析取析取范式范式例例1 1 求求 (pq)r 的析取范式与合取范式的析取范式与合取范式解解 (pq)r ( p q)r (pq)r 析取范式析取范式 (pr) ( qr) 合取范式合取范式注意注意: 公式的析取范式与合取范式不惟一公式的析取范式与合取范式不惟一.极小项与极大项极小项极小项( (极大项极大项):):在含有在含有n个命题变项的简单合取式个命题变项的简单合取式( (简单简单析取式析取式) )中中, ,若每个命题变项均以文字的形式出现

13、且仅若每个命题变项均以文字的形式出现且仅出现一次，而且第出现一次，而且第i( (1 i n) )个文字个文字( (按下标或字母顺序按下标或字母顺序排列排列) )出现在左起第出现在左起第i位上位上, ,称这样的简单合取式称这样的简单合取式( (简单简单析取式析取式) )为为极小项极小项( (极大项极大项) )说明说明: :(1) n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个极大项个极大项(2) 2n个极小项个极小项( (极大项极大项) )均互不等值均互不等值(3) 用用mi表示第表示第i个极小项个极小项, ,其中其中i是该极小项成真赋值的是该极小项成真赋值的十进制表示十进制表示.

14、 用用Mi表示第表示第i个极大项个极大项, ,其中其中i是该极大项成是该极大项成假赋值的十进制表示假赋值的十进制表示, mi( (Mi) )称为极小项称为极小项( (极大项极大项) )的名的名称称. 极小项与极大项(续)定理定理2.4 设设mi 与与Mi是由同一组命题变项形成的极小项和是由同一组命题变项形成的极小项和极大项极大项, 则则 mi Mi , Mi mi 极小项极小项 极大项极大项 公式公式 成真赋值成真赋值 名称名称 公式公式 成假赋值成假赋值 名称名称 pq 0 0 m0 p q 0 0 M0 p q 0 1 m1 pq 0 1 M1 pq 1 0 m2 p q 1 0 M2 p

15、 q 1 1 m3 pq 1 1 M3 p,q形成的极小项与极大项形成的极小项与极大项主析取范式与主合取范式主析取范式主析取范式: :由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式: :由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变项为命题变项为p, q, r时，时， ( pq r) ( p q r) m1 m3 是主析取范式是主析取范式 (p qr) ( p qr) M1 M5 是主合取范式是主合取范式定理定理2.5 2.5 任何命题公式都存在着与之等值的主析取范式和任何命题公式都存在着与之等值的主析取范式和主合取范式主合取范式, , 并且是惟一的

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

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

18、例1(1(续续) ) 求求 (pq)r 的主析取范式与主合取范式的主析取范式与主合取范式解解 (1) (1) (pq)r (pq)r pq (pq) 1 同一律同一律 (pq) ( r r) 排中律排中律 (pqr) (pq r) 分配律分配律 m4 m5 r ( p p) ( q q)r 同一律同一律, 排中律排中律 ( pqr) ( p qr) (pqr) (p qr) m0 m2 m4 m6 分配律分配律得得 (pq)r m0 m2 m4 m5 m6可记作可记作 (0,2,4,5,6)实例(续)(2) (pq)r (pr) ( qr) pr p 0r 同一律同一律 p (qq)r 矛盾律

19、矛盾律 (p qr) (pqr) 分配律分配律 M1 M3 qr (pp)qr 同一律同一律, 矛盾律矛盾律 (pqr) ( pqr) 分配律分配律 M3 M7得得 (pq)r M1 M3 M7可记作可记作 (1,3,7)主析取范式的用途(1) 求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值设公式设公式A含含n个命题变项个命题变项, A的主析取范式有的主析取范式有s个极小项个极小项, 则则A有有s个成真赋值个成真赋值, 它们是极小项下标的二进制表示它们是极小项下标的二进制表示, 其余其余2n-s个赋值都是成假赋值个赋值都是成假赋值 例如例如 (pq)r m0 m2 m4 m5 m6 成真

20、赋值成真赋值: 000,010,100,101,110; 成假赋值成假赋值: 001,011,111主析取范式的用途(续)(2) 判断公式的类型判断公式的类型 设设A含含n个命题变项，则个命题变项，则 A为重言式当且仅当为重言式当且仅当A的主析取范式含的主析取范式含2n个极小项个极小项A为矛盾式当且仅当为矛盾式当且仅当 A的主析取范式不含任何极小项的主析取范式不含任何极小项, ,记作记作0 A为可满足式当且仅当为可满足式当且仅当A的主析取范式中至少含一个极小项的主析取范式中至少含一个极小项实例例例2 用主析取范式判断公式的类型用主析取范式判断公式的类型:(1) A (pq) q (2) B p

21、(p q) (3) C (p q)r解解 (1) A ( p q) q ( pq) q 0 矛盾式矛盾式(2) B p (p q) 1 m0 m1 m2 m3 重言式重言式(3) C (p q) r ( pq) r ( pq r) ( pqr) ( pq r) ( p q r) (pq r) (p q r) m0 m1 m3 m5 m7 非重言式的可满足式非重言式的可满足式主析取范式的用途(续)(3) 判断两个公式是否等值判断两个公式是否等值例例3 用主析取范式判断下面用主析取范式判断下面2组公式是否等值组公式是否等值:(1) p与与( p q)(p q)解解 p p ( q q) (pq)

22、(p q) m2 m3 ( p q)(p q) ( p q) (p q) (pq) (p q) m2 m3故故 p ( p q)(p q)实例(续)(2) (p q) r 与与 p (q r)解解 (p q) r (p qr) (p q r) ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m6 m7 p (q r) (p q) (p r) (p qr) (p q r) (pq r) (p q r) m5 m6 m7故故 (p q) r p (q r)实例例例4 某单位要从某单位要从A,B,C三人中选派若干人出国考察三人中选派若干人出国考察, 需满需满足下述条

23、件足下述条件:(1) 若若A去去, 则则C必须去必须去;(2) 若若B去去, 则则C不能去不能去;(3) A和和B必须去一人且只能去一人必须去一人且只能去一人.问有几种可能的选派方案问有几种可能的选派方案?解解 记记p:派派A去去, q:派派B去去, r:派派C去去(1) pr, (2) qr, (3) (pq) ( p q)求下式的成真赋值求下式的成真赋值 A=(pr) (qr) (pq) ( p q)实例(续)求求A的主析取范式的主析取范式 A=(pr) (qr) (pq) ( p q) ( p r) ( qr) (pq) ( p q) ( pq) ( pr) (rq) (rr) (pq)

24、 ( p q) ( pq) (pq) ( pr) (pq) (rq) (pq) ( pq) ( p q) ( pr) ( p q) (rq) ( p q) (pq r) ( p qr)成真赋值成真赋值:101,010结论结论: 方案方案1 派派A与与C去去, 方案方案2 派派B去去主合取范式由主析取范式求主合取范式由主析取范式求主合取范式设设没有出现的极小项是没有出现的极小项是siiimmmA21,21tjjjmmm其中其中t=2n-s, tjjjmmmA21tttjjjjjjjjjMMMmmmmmmA212121)(于是于是主合取范式(续)例例6 求求A=( pq r) ( p q r) (

25、p q r)的主合取范式的主合取范式解解 A m1 m3 m7 M0 M2 M4 M5 M6矛盾式的主合取范式含全部矛盾式的主合取范式含全部2n个极大项个极大项重言式的主合取范式不含任何极大项重言式的主合取范式不含任何极大项, 记作记作1基本要求深刻理解等值式的概念深刻理解等值式的概念牢记基本等值式的名称及它们的内容牢记基本等值式的名称及它们的内容熟练地应用基本等值式及置换规则进行等值演算熟练地应用基本等值式及置换规则进行等值演算理解文字、简单析取式、简单合取式、析取范式、理解文字、简单析取式、简单合取式、析取范式、合取范式的概念合取范式的概念深刻理解极小项、极大项的概念、名称及下角标与深刻理

26、解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小成真、成假赋值的关系，并理解简单析取式与极小项的关系项的关系熟练掌握求主范式的方法（等值演算、真值表等）熟练掌握求主范式的方法（等值演算、真值表等）会用主范式求公式的成真赋值、成假赋值、判断公会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值式的类型、判断两个公式是否等值练习题1: 判断公式类型1. 判断下列公式的类型判断下列公式的类型: (1) (pq)( qp)解 用等值演算法求主范式 (pq)(qp) (pq)(qp) (pq)(qp) (pq)(pq)(pq)(pq) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式 1 主合取范式重言式重言式练习题1: 判断公式类型（续）(2)(2) ( (p pq q) ) q q解 用等值演算法求公式的主范式 (pq)q (pq)q pqq 0 主析取范式 M0 M1 M2 M3 主合取范式矛盾式矛盾式解 用等值演算法求公式的主范式 (pq)p (pq)p p (pq)(pq) m0 m1 主析取范式 M2 M3 主合取范式(3) (pq)p练习题1: 判断公式类型（续）非重言式的可满足式非重言式的可满足式