离散数学课件：第1章 命题逻辑2

1、11.3 命题逻辑等值演算命题逻辑等值演算 等值式等值式基本等值式基本等值式等值演算等值演算置换规则置换规则2等值式等值式 定义定义 对命题公式对命题公式A与与B ，若等价式，若等价式AB是重言式，是重言式，则称则称A与与B等值等值，记作，记作AB，并称，并称AB是是等值式等值式分清楚分清楚 =、 和和 意义区别意义区别验证两个公式是否等值，可用真值表验证两个公式是否等值，可用真值表请验证：请验证：p(qr) (p q) r p(qr) (pq) r 3基本等值式基本等值式 双重否定律双重否定律 : AA等幂律等幂律： A AA, A AA交换律交换律: A BB A, A BB A结合律结合

2、律: (A B) CA (B C) (A B) CA (B C)分配律分配律: A (B C)(A B) (A C) A (B C) (A B) (A C)4基本等值式基本等值式( (续续) )德德摩根律摩根律: (A B)AB (A B)AB吸收律吸收律: A (A B)A, A (A B)A零律零律: A 11, A 00 同一律同一律: A 0A, A 1A排中律排中律: AA1矛盾律矛盾律: AA05基本等值式基本等值式( (续续) )蕴涵等值式蕴涵等值式: ABA B等价等值式等价等值式: AB(AB) (BA)假言易位假言易位: ABBA等价否定等值式等价否定等值式: ABAB归谬

3、论归谬论: (AB) (AB) A注意注意:上述上述A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式牢记这些等值式是继续学习的基础是继续学习的基础6等值演算与置换规则等值演算与置换规则 等值演算等值演算: 由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则：若：若AB, 则则 (B) (A) 等值演算一般基于以下等值演算一般基于以下3 3点：点： (1) 等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递 (2) 基本的等值式基本的等值式 (3) 置换规则置换规则 7应用举例应用举例证明两个公式等值证明两个公式等值 例例1 证明证

4、明 p(qr) (p q)r证证 p(qr) p ( q r) （蕴涵等值式，置换规则）（蕴涵等值式，置换规则） ( pq) r （结合律，置换规则）（结合律，置换规则） (p q) r （德（德 摩根律，置换规则）摩根律，置换规则） (p q) r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则） 说明说明: :也可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍） 因为每一步都会用置换规则，可不写出。因为每一步都会用置换规则，可不写出。 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 8应用举例应用举例证明两个公式不等值证明两个公式不等值例例2 证明证明: p(qr

5、) (pq) r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假. 方法一方法一 真值表法（自己证）真值表法（自己证） 方法二方法二 观察赋值法观察赋值法. 容易看出容易看出000, 010等是左边的等是左边的的成真赋值，是右边的成假赋值的成真赋值，是右边的成假赋值. 方法三方法三 用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.9应用举例应用举例判断公式类型判断公式类型 例例3 用等值演算法判断下列公式的类型用等值演算法判

6、断下列公式的类型(1) q(pq) 解解 q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德（德 摩根律）摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式. 10例例3 (续续)(2) (pq)( qp) 解解 (pq)( qp) ( p q)(qp) （蕴涵等值式）（蕴涵等值式） ( p q)( p q) （交换律）（交换律） 1 （最后这步为什么等值于最后这步为什么等值于1？）？） 由最后一步可知，该式为重言式由最后一步可知，该式为重言式. （一

7、开始用假言一开始用假言易位也可易位也可）11例例3 (续续)(3) ( (p q) (pq) ) r 解解 ( (p q) (pq) ) r ( p (qq) ) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式的可这不是矛盾式，也不是重言式，而是非重言式的可满足式满足式. .如如101是它的成真赋值是它的成真赋值, ,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一, ,应尽量使演算短些应尽量使演

8、算短些121.4 范式范式 析取范式与合取范式析取范式与合取范式 主析取范式与主合取范式主析取范式与主合取范式 13析取范式与合取范式析取范式与合取范式 文字文字: :命题变项及其否定的统称命题变项及其否定的统称简单析取式简单析取式: :有限个文字构成的析取式有限个文字构成的析取式如如 p, q, pq, p q r, 简单合取式简单合取式: :有限个文字构成的合取式有限个文字构成的合取式如如 p, q, pq, p q r, 析取范式析取范式: :由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A1 A2Ar, 其中其中A1,A2,Ar是是简单合取式简单合取式合取范式合取范式:

9、 :由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 A1 A2Ar , 其中其中A1,A2,Ar是是简单析取式简单析取式14析取范式与合取范式析取范式与合取范式( (续续) )范式范式: :析取范式与合取范式的总称析取范式与合取范式的总称 公式公式A的析取范式的析取范式: 与与A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式: 与与A等值的合取范式等值的合取范式特别注意：特别注意： 单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式形如：形如：pq r, p qr 既是析取范式，又是合既是析取范式，又是合取范式取范式(为什么为什么?) 15命

10、题公式的范式命题公式的范式 定理定理 任何命题公式都存在着与之等值的析取范式任何命题公式都存在着与之等值的析取范式与合取范式与合取范式. .（构造证明）求公（构造证明）求公式式A的范式的步骤：的范式的步骤： (1) 消去消去A中的中的, （若存在）（若存在） (2) 否定联结词否定联结词 的内移或消去的内移或消去 (3) 使用分配律使用分配律 对对 分配（求析取范式）分配（求析取范式） 对对 分配（求合取范式）分配（求合取范式）以上步骤说明公式的范式存在以上步骤说明公式的范式存在，但不惟一，但不惟一16求公式的范式举例求公式的范式举例 例例 求下列公式的析取范式与合取范式求下列公式的析取范式与

11、合取范式(1) A=(pq)r解解 (pq)r ( pq)r （消去（消去） pqr （结合律）（结合律）这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析个简单合取式组成的析取式），又是取式），又是A的合取范式（由一个简单析取式的合取范式（由一个简单析取式组成的合取式）组成的合取式）17求公式的范式举例求公式的范式举例( (续续) )(2) B=(pq)r解解 (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r （消去第二个（消去第二个） (p q) r （否定号内移（否定号内移德德 摩根律）摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（

12、两个简单合取式构成）继续：继续： (p q) r (p r) (q r) （ 对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成） 18极小项与极大项极小项与极大项 定义定义 在含有在含有n个命题变项的简单合取式个命题变项的简单合取式( (简单析取式简单析取式) )中，中，若若每个命题变项的文字形式均出现且仅一次出现每个命题变项的文字形式均出现且仅一次出现，称这，称这样的简单合取式样的简单合取式( (简单析取式简单析取式) )为为极小项极小项( (极大项）极大项）.说明：说明：n n个命题变项产生个命题变项产生2n个极小项和个极小项和2n个

13、极大项个极大项n 2n个极小项（极大项）个极小项（极大项）互不等值互不等值n 在极小项和极大项中，在极小项和极大项中，文字均按下标或字母顺序排列文字均按下标或字母顺序排列n 用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值的十进是该极小项成真赋值的十进制表示制表示. 用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成假赋值是该极大项成假赋值的十进制表示的十进制表示, mi( (Mi) )称为极小项称为极小项( (极大项极大项) )的名称的名称. n mi与与Mi的关系（对偶性）的关系（对偶性）: : mi Mi , Mi mi 19极小项与极大项极小项与极大

14、项( (续续) )由由p, q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 公式公式 成成真真赋值赋值名称名称 公式公式 成成假假赋值赋值名称名称 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M2M3 极小项极小项 极大项极大项 20 由由p, q, r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项 极小项极小项 极大项极大项 公式公式 成成真真赋值赋值名称名称 公式公式 成成假假赋值赋值名称名称 p q r p q r p q r p q rp q

15、 rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 21主析取范式与主合取范式主析取范式与主合取范式 主析取范式主析取范式: : 由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式: : 由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变项为命题变项为p, q

16、, r时，时， ( pq r) ( p q r)（或（或 m1 m3）是一个是一个主析取主析取范式范式 (p qr) ( p qr) （或（或 M1 M5 ）是一个）是一个主合取主合取范式范式 A的主析取范式的主析取范式: 与与A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式: : 与与A等值的主合取范式等值的主合取范式. 22主析取范式与主合取范式主析取范式与主合取范式( (续续) )定理定理 任何命题公式都任何命题公式都存在存在着与之等值的主析取范着与之等值的主析取范式和主合取范式式和主合取范式, 并且是并且是唯一唯一的的. . 用用等值演算法等值演算法求公式的主范式的步骤：

17、求公式的主范式的步骤： (1) 先求析取范式（合取范式）先求析取范式（合取范式） (2) 将不是极小项（极大项）的简单合取式（简将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等律）、排中律（矛盾律）、分配律、幂等律等. (3) 极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，并）表示，并按按角标从小到大顺序排序角标从小到大顺序排序. 23求公式的主范式求公式的主范式例例 求公式求公式 A=(

18、pq)r的主析取范式与主合的主析取范式与主合 取范式取范式. . (1) 求主析取范式求主析取范式 (pq)r (p q) r , （析取范式）（析取范式） (p q) (p q) ( r r) (p qr) (p q r) m6 m7 , 24求公式的主范式求公式的主范式( (续续) ) 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（主析取范式）主析取范式） 25求公式的主范式求公式的主范式( (续续) ) (2) 求求A的主合取范式的主合

19、取范式 (pq)r (p q) r (p r) (q r) , （合取范式）（合取范式） p r p (qq) r (p q r) (pq r) M0 M2, 26求公式的主范式求公式的主范式( (续续) ) q r (pp) q r (p q r) ( p q r) M0 M4 , 代入并排序，得代入并排序，得 (pq)r M0 M2 M4 （主合取范式）（主合取范式） 求主范式的其他方法- -用公式用公式A的真值表求的真值表求A的主范式的主范式.先列出先列出A的真值表，找出所有成真赋值（或的真值表，找出所有成真赋值（或成假赋值）成假赋值）- -由公式由公式A的主析取范式确定它的主合取范式，

20、的主析取范式确定它的主合取范式，反之亦然反之亦然. 方法是。？方法是。？2728主范式的用途主范式的用途与真值表相同与真值表相同 (1) 求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值 例如例如 (pq)r m1 m3 m5 m6 m7， 其成真赋值为其成真赋值为001, 011, 101, 110, 111， 其余的赋值其余的赋值 000, 010, 100为为成假赋值成假赋值. 类似地，由主合取范式也可立即求出成类似地，由主合取范式也可立即求出成 假赋值和成真赋值假赋值和成真赋值. 29主范式的用途主范式的用途( (续续) ) (2) 判断公式的类型判断公式的类型 设设A含含n个命题

21、变项，则个命题变项，则 A为重言式为重言式A的主析取范式含的主析取范式含2n个极小项个极小项 A的主合取范式为的主合取范式为1.A为矛盾式为矛盾式 A的主析取范式为的主析取范式为0 A的主合取范式含的主合取范式含2n个极大项个极大项A为非重言式的可满足式为非重言式的可满足式A的主析取范式中至少含一个但不含全部极小项的主析取范式中至少含一个但不含全部极小项A的主合取范式中至少含一个但不含全部极大项的主合取范式中至少含一个但不含全部极大项 30主范式的用途主范式的用途( (续续) )例例 用主析取范式判断下述两个公式是否等值：用主析取范式判断下述两个公式是否等值： p(qr) 与与 (p q)r

22、p(qr) 与与 (pq)r解解 p(qr) m0 m1 m2 m3 m4 m5 m7 (p q)r m0 m1 m2 m3 m4 m5 m7 (pq)r m1 m3 m4 m5 m7故中的两公式等值，而的不等值故中的两公式等值，而的不等值. 实际上这两题求主合取范式判断更快实际上这两题求主合取范式判断更快(3) 判断两个公式是否等值判断两个公式是否等值31主范式的用途主范式的用途( (续续) )例例 某公司要从赵、钱、孙、李、周五名新毕业某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习的大学生中选派一些人出国学习. 选派必须满足选派必须满足以下条件：以下条件： (1)(1)

23、若赵去，钱也去；若赵去，钱也去； (2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去； (3)(3)钱、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人； (4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去； (5)(5)若周去，则赵、钱也去若周去，则赵、钱也去. 试用主析取范式法分析该公司如何选派他们出国？试用主析取范式法分析该公司如何选派他们出国？32例例 (续续)解此类问题的步骤为：解此类问题的步骤为： 将简单命题符号化将简单命题符号化 写出各复合命题写出各复合命题 写出由中复合命题组成的合取式写出由中复合命题组成的合取式 求求中所得公式的主析取范式中所得公式的主析取范式 （从而看出是（