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

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

1、1/632.1 等值式等值式定义定义2.1 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作记作AB，并称，并称AB是是等值式。等值式。几点说明：几点说明：l定义中，定义中，A, B,均为元语言符号均为元语言符号l用真值表可检查两个公式是否等值用真值表可检查两个公式是否等值2/63等值式例题等值式例题例例1 判断下列各组公式是否等值。判断下列各组公式是否等值。 (1) p(qr) 与与 (p q) r 11111101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (p q)rp(qr)qr p q

2、rp q00000011 结论结论: : p(qr) (p q) r 3/63等值式例题等值式例题 (2) p(qr) 与与 (pq) r 01011101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq)rp(qr)qr p q rpq11110011 结论结论: : p(qr) 与与 (pq) r 不等值不等值4/63基本等值式基本等值式双重否定律双重否定律 AA幂等律幂等律 A AA, A AA交换律交换律 A BB A, A BB A结合律结合律 (A B) CA (B C), (A B) CA (B C)分

3、配律分配律 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)A5/63基本等值式基本等值式零律零律 A 11, A 00同一律同一律 A 0A. A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB) (BA)假言易位假言易位 ABBA等价否定等值式等价否定等值式 ABAB归谬论归谬论 (AB) (AB) A特别提示特别提示：必须牢记这：必须牢记这16组等值式组等值式(24式式)，这是继，这是继续学习的基础。续学

4、习的基础。6/63等值演算与置换规则等值演算与置换规则1. 等值演算等值演算由已知的等值式推演出新的等值式由已知的等值式推演出新的等值式的过程的过程2. 等值演算的基础：等值演算的基础： (1) 等值关系的性质：自反性、对称性、传递性等值关系的性质：自反性、对称性、传递性 (2) 基本的等值式基本的等值式 (3) 置换规则置换规则3. 置换规则置换规则 设设 (A) 是含公式是含公式 A 的命题公式，的命题公式， (B) 是用公式是用公式 B 置换置换 (A) 中所有的中所有的 A 后得到的命题公式。后得到的命题公式。 若若 BA，则，则 (B)(A)。7/63等值演算的应用举例等值演算的应用

5、举例证明两个公式等值证明两个公式等值例例2 证明证明 p(qr) (p q)r证证 p(qr) p ( q r) （蕴涵等值式，置换规则）（蕴涵等值式，置换规则） ( pq) r （结合律，置换规则）（结合律，置换规则） (p q) r （德摩根律，置换规则）（德摩根律，置换规则） (p q)r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则）注意注意：用等值演算不能直接证明两个公式不等值：用等值演算不能直接证明两个公式不等值8/63证明两个公式不等值证明两个公式不等值例例3 证明证明 p(qr) 与与 (pq)r 不等值不等值证证 方法一方法一 真值表法真值表法, 见例见例1(2) 方法二

6、观察法。 观察到000, 010是左边的成真 赋值，是右边的成假赋值 方法三方法三 先用等值演算化简公式，然后再观察先用等值演算化简公式，然后再观察 p(qr) pq r (pq)r ( p q) r(pq) r 更容易看出前面的两个赋值分别是更容易看出前面的两个赋值分别是左边的成真左边的成真赋值和右边的成假赋值赋值和右边的成假赋值等值演算的应用举例等值演算的应用举例9/63判断公式类型判断公式类型: A为矛盾式当且仅当为矛盾式当且仅当A 0 A为重言式当且仅当为重言式当且仅当A 1例例4 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型 (1) q(pq) (2) (pq)( q

7、p) (3) (p q) (pq) r) 等值演算的应用举例等值演算的应用举例10/63等值演算的应用举例等值演算的应用举例解解 (1) q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）矛盾式矛盾式11/63判断公式类型判断公式类型(2) (pq)( qp) ( p q)(qp) （蕴涵等值式）（蕴涵等值式） ( p q)( p q) （交换律）（交换律） 1重言式重言式(3) (p q) (pq) r) (p (qq) r （分配律）（分配律

8、） p 1 r （排中律）（排中律） p r （同一律）（同一律）可满足式，可满足式，101和和111是成真赋值，是成真赋值，000和和010等是成等是成假赋值假赋值. 12/632.2 析取范式与合取范式析取范式与合取范式基本概念基本概念(1) 文字文字命题变项及其否定的总称命题变项及其否定的总称(2) 简单析取式简单析取式仅由有限个文字构成的析取式仅由有限个文字构成的析取式 p, q, pq, p q r, (3) 简单合取式简单合取式仅由有限个文字构成的合取式仅由有限个文字构成的合取式 p, q, pq, p q r, (4) 析取范式析取范式由有限个简单合取式组成的析取式由有限个简单合

9、取式组成的析取式 p, p q, pq, (pq) ( p qr) (q r)(5) 合取范式合取范式由有限个简单析取式组成的合取式由有限个简单析取式组成的合取式 p, pq, p q, (p qp (p q r)(6) 范式范式析取范式与合取范式的总称析取范式与合取范式的总称13/63说明：说明：l 单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式l 形如形如 pq r, p qr 的的公式既是析取范式，公式既是析取范式，又是合取范式又是合取范式定理定理2.1 (1) 一个简单析取式是重言式当且仅当它同一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定

10、式。时含有某个命题变项和它的否定式。(2) 一个简单合取式是矛盾式当且仅当它同时含有某一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式。个命题变项和它的否定式。14/63范式的性质范式的性质定理定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式。简单合取式都是矛盾式。(2) 一个合取范式是重言式当且仅当它的每个简单析一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。取式都是重言式。定理定理2.3（范式存在定理）（范式存在定理） 任何命题公式都存在与之等值的析取范式与合任何命题公式都存在与之等值的析取范式与合取范式

11、。取范式。15/63命题公式的范式命题公式的范式求公式求公式A的范式的步骤：的范式的步骤： (1) 消去消去A中的中的, （若存在）（若存在） ABA B AB( A B) (AB) (2) 否定联结词否定联结词 的内移或消去的内移或消去 A A (A B)AB (A B)AB (3) 使用分配律使用分配律 A (B C)(A B) (A C) 求合取范式求合取范式 A (B C) (A B) (A C) 求析取范式求析取范式公式范式的不足公式范式的不足不惟一不惟一16/63求公式的范式求公式的范式例例5 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式 (1) (pq)r (2)

12、 (pq)r解解 (1) (pq)r ( pq)r （消去（消去） pqr （结合律）（结合律）最后结果既是析取范式最后结果既是析取范式(由由3个简单合取式组成的析个简单合取式组成的析取式取式)，又是合取范式，又是合取范式(由一个简单析取式组成的合由一个简单析取式组成的合取式取式) 。17/63 (2) (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r （消去第二个（消去第二个） (p q) r （否定号内移（否定号内移) 析取范式析取范式 (p r) (q r) （ 对对 分配律）分配律） 合取范式合取范式求公式的范式求公式的范式18/63极小项与极大项极小项与极大项定义

13、定义2.4 在含有在含有n个命题变项的简单合取式（简单析取个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第且仅出现一次，而且第i个文字出现在左起第个文字出现在左起第i位上位上（1 i n），称这样的简单合取式（简单析取式）为），称这样的简单合取式（简单析取式）为极小项极小项（极大项极大项）。）。几点说明：几点说明：l n个命题变项有个命题变项有2n个极小项和个极小项和2n个极大项个极大项l 2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值l 用用mi表示第表示第i个极小项，其中个极小项，

14、其中i是该极小项成真赋值是该极小项成真赋值的十进制表示的十进制表示. 用用Mi表示第表示第i个极大项，其中个极大项，其中i是该是该极大项成假赋值的十进制表示极大项成假赋值的十进制表示. mi（Mi）称为极小）称为极小项（极大项）的名称。项（极大项）的名称。19/63实例实例由两个命题变项由两个命题变项 p, q 形成的极小项与极大项形成的极小项与极大项极小项极小项极大项极大项公式公式成真赋成真赋值值名称名称公式公式成假赋成假赋值值名称名称 pq p qpqp q 0 0 0 1 1 0 1 1 m0m1m2m3 p q pq p q pq 0 0 0 1 1 0 1 1M0M1M2M320/6

15、3实例实例极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 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 00 1 11 0 01 0 11 1 01 1 1 M0M1M2M3M4M5M6M7由三个命题变项由三个命题变项 p, q, r 形成的极小项与极大项形成的极小项与极大项。m

16、i与与Mi的关系：的关系： mi Mi, Mi mi 21/63主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变项为命题变项为 p, q, r 时，时， ( pq r) ( p q r) m1 m3 主析取范式主析取范式 (p qr) ( pqr) M1 M7主合取范式主合取范式定理定理2.5 (主范式的存在惟一定理主范式的存在惟一定理) 任何命题公式都存在与之等值的主析取范式和主任何命题公式都存在与之等值的主析取范式和主合取范式合取范式, 并

17、且是惟一的。并且是惟一的。22/63求公式主范式的步骤求公式主范式的步骤求公式主析取范式的步骤求公式主析取范式的步骤:设公式设公式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) 消去重复出现的极小项消去重复出现的极小项,

18、即用即用mi代替代替mi mi(4) 将极小项按下标从小到大排列将极小项按下标从小到大排列23/63求公式主范式的步骤求公式主范式的步骤求公式的主合取范式的步骤求公式的主合取范式的步骤:设公式设公式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的的极大

19、项为止极大项为止(3) 消去重复出现的极大项消去重复出现的极大项, 即用即用Mi代替代替Mi Mi(4) 将极大项按下标从小到大排列将极大项按下标从小到大排列24/63实例实例例例6 (1) 求公式求公式 A=(pq)r的主析取范式和主合的主析取范式和主合取范式。取范式。 解解 (pq)r (p q) r （析取范式）（析取范式） (p q) (p q) ( 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

20、 m6 m7 (主析取范式主析取范式)25/63实例实例 (pq)r (p r) (q r) （合取范式）（合取范式） p r p (qq) r (p q r) (pq r) M0 M2 q r (pp) q r (p q r) ( p q r) M0 M4 , 代入代入 并排序，得并排序，得 (pq)r M0 M2 M4 (主合取范式主合取范式)26/63主范式的应用主范式的应用1.1.求公式的成真成假赋求公式的成真成假赋值值 设公式设公式A含含n个命题变项个命题变项, A的主析取范式有的主析取范式有s个极个极小项小项, 则则A有有s个成真赋值个成真赋值, 它们是极小项下标的二它们是极小项下

21、标的二进制表示进制表示, 其余其余2n-s个赋值都是成假赋值个赋值都是成假赋值 例如例如 (pq)r m1 m3 m5 m6 m7成真赋值为成真赋值为 001, 011, 101, 110, 111，成假赋值为成假赋值为 000, 010, 100. 类似地，由主合取范式也立即求出成假赋值和成真类似地，由主合取范式也立即求出成假赋值和成真赋值。赋值。27/632. 判断公式的类型判断公式的类型 设设A含含n个命题变项个命题变项. A为重言式为重言式 A的主析取范式含全部的主析取范式含全部2n个极小项个极小项 A的主合取范式不含任何极大项的主合取范式不含任何极大项, 记为记为1. A为矛盾式为矛

22、盾式 A的主合析取范式含全部的主合析取范式含全部2n个极大项个极大项 A的主析取范式不含任何极小项的主析取范式不含任何极小项, 记为记为0. A为非重言式的可满足式为非重言式的可满足式 A的主析取范式中至少含一个、但不是全部极小项的主析取范式中至少含一个、但不是全部极小项. A的主合取范式中至少含一个、但不是全部极大项的主合取范式中至少含一个、但不是全部极大项.主范式的应用主范式的应用28/63例例7 用主析取范式判断公式的类型用主析取范式判断公式的类型:(1) A (pq) q (2) B p(p q) (3) C (p q)r解解 (1) A ( p q) q ( pq) q 0 矛盾式矛

23、盾式(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 非重言式的可满足式非重言式的可满足式主范式的应用主范式的应用29/633. 判断两个公式是否等值判断两个公式是否等值例例8 用主析取范式判以下每一组公式是否等值用主析取范式判以下每一组公式是否等值 p(qr) 与与 (p q)r p(qr) 与与 (pq)r解解 p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r = m0 m1 m2 m

24、3 m4 m5 m7 (pq)r = m1 m3 m4 m5 m7显见，中的两公式等值，而的不等值显见，中的两公式等值，而的不等值.主范式的应用主范式的应用30/634. 解实际问题解实际问题例例9 某单位要从某单位要从A,B,C三人中选派若干人出国考察三人中选派若干人出国考察, 需满足下述条件需满足下述条件: (1) 若若A去去, 则则C必须去必须去; (2) 若若B去去, 则则C不能去不能去; (3) A和和B必须去一人且只能去一人必须去一人且只能去一人. 问有几种可能的选派方案问有几种可能的选派方案?解解 记记 p:派派A去去, q:派派B去去, r:派派C去去(1) pr, (2) q

25、r, (3) (pq) ( p q)求下式的成真赋值求下式的成真赋值 A=(pr) (qr) (pq) ( p q)主范式的应用主范式的应用31/63求求A的主析取范式的主析取范式 A=(pr) (qr) (pq) ( p q) ( p r) ( qr) (pq) ( p q) ( pq) ( pr) (rq) (rr) (pq) ( 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去去, 方案方案

26、2 派派B去去主范式的应用主范式的应用32/63由主析取范式确定主合取范式由主析取范式确定主合取范式例例10 设设A有有3个命题变项个命题变项, 且已知且已知A= m1 m3 m7, 求求A的主合取范式的主合取范式.解解 A的成真赋值是的成真赋值是1,3,7的二进制表示的二进制表示, 成假赋值是成假赋值是在主析取范式中没有出现的极小项的下角标在主析取范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示的二进制表示, 它们恰好是它们恰好是A的主合取范式的极大项的主合取范式的极大项的下角标的下角标, 故故 A M0 M2 M4 M5 M6用成真和成假赋值确定主范式用成真和成假赋值确定主范式

27、说明说明：1)由主合取范式确定主析取范式由主合取范式确定主析取范式 2)用真值表确定主范式用真值表确定主范式 33/632.3 联结词的完备集联结词的完备集定义定义2.6 称称F:0,1n 0,1 为为n元真值函数元真值函数。 0,1n=000, 001, , 111，包含，包含 个长为个长为n的的0,1符号串符号串. 共有共有 个个n元真值函数元真值函数。 n22n21元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF34/63真值函数真值函数p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

28、 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元真值函数元真值函数35/63公式与真值函数公式与真值函数)2(13F 任何一个含任何一个含n个命题变项的命题公式个命题变项的命题公式A都对应惟都对应惟一的一个一的一个n元真值函数元真值函数 F , F

29、恰好为恰好为A的真值表。的真值表。 等值的公式对应的真值函数相同。等值的公式对应的真值函数相同。 例如：例如：pq, p q 都对应都对应说说明明：真值函数与主析取范式（真值函数与主析取范式（主合取范式）主合取范式）36/63联结词完备集联结词完备集定义定义2.7 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1) 元真元真值函数都可以由仅含值函数都可以由仅含S中的联结词构成的公式表示，则中的联结词构成的公式表示，则称称S是是联结词完备集。联结词完备集。若若S是联结词完备集是联结词完备集, 则任何命题公式都可由则任何命题公式都可由S中的联结中的联结词表示。词表示。定理定理2

30、.6 S = , , 是联结词完备集。是联结词完备集。证明证明 由范式存在定理可证。由范式存在定理可证。37/63联结词完备集联结词完备集推论推论 以下都是联结词完备集以下都是联结词完备集 (1) S1 = , , , (2) S2 = , , , , (3) S3 = , (4) S4 = , (5) S5 = , 证明证明 (1),(2) 显然。显然。(3) A B ( AB)(4) A B ( AB)(5) ABA B , ,不是联结词完备集不是联结词完备集, 0不能用它表示；不能用它表示；它的子集它的子集 , , , , , ,等都不是。等都不是。38/63复合联结词复合联结词定义定义

31、2.8 设设 p, q 为两个命题为两个命题, (p q)称作称作p与与q的的与非与非式式, 记作记作p q, 即即 p q (p q), 称为称为与非联结词。与非联结词。 (p q) 称作称作 p 与与 q 的的或非式或非式, 记作记作 p q, 即即 p q (p q), 称为称为或非联结词。或非联结词。定理定理2.7 与与 为联结词完备集。为联结词完备集。 证明证明 , , 为完备集为完备集 p pp (p p) p p p q ( pq) pq (p p) (q q) p q (p q) (p q) (p q) (p q) 得证得证 为联结词完备集。为联结词完备集。 对对 类似可证。类

32、似可证。39/632.4 可满足性问题与消解法可满足性问题与消解法命题公式的可满足性问题命题公式的可满足性问题任何一个命题公式都能化成等值的合取范式任何一个命题公式都能化成等值的合取范式 （由有限个简单析取式组成的合取式）（由有限个简单析取式组成的合取式）约定：简单析取式不同时含某个命题变项和它的否定。约定：简单析取式不同时含某个命题变项和它的否定。不含任何文字的简单析取式称作空简单析取式不含任何文字的简单析取式称作空简单析取式,记作记作 .规定：规定： 是不可满足的。是不可满足的。 40/632.4 可满足性问题与消解法可满足性问题与消解法S:合取范式合取范式, C:简单析取式简单析取式,

33、l:文字文字, :赋值赋值. 带下角标或带下角标或 文字文字l的补的补lc: 若若l=p,则则lc= p; 若若l= p,则则lc=p.S S : S是可满足的当且仅当是可满足的当且仅当S 是可满足的是可满足的.定义定义2.9 设设C1=l C1 , C2=lc C2 , C1 和和C2 不含不含l和和lc, 称称C1C2 为为C1和和C2(以以l和和lc为为消解文字消解文字)的的消解式消解式或或消解结消解结果果, 记作记作Res(C1,C2)。亦即。亦即Res(C1,C2)= C1C2 。例如例如, Res( p q r, p qs)= q rs41/63消解规则消解规则定理定理2.8 C1

34、 C2 Res(C1,C2)证证 记记C= Res(C1,C2)=C1C2 , 其中其中l和和lc为消解文字为消解文字, C1=l C1 , C2=lc C2 , 且且C1 和和C2 不含不含l和和lc. 假设假设C1 C2是可满足的是可满足的, 是它的满足赋值是它的满足赋值, 不妨设不妨设 (l)=1. C2必含有文字必含有文字l l, lc且且 (l )=1. C中含有中含有l , 故故 满足满足C. 反之反之, 假设假设C是可满足的是可满足的, 是它的满足赋值是它的满足赋值. C必有必有l 使得使得 (l )=1, 不妨设不妨设C1 含含l , 于是于是 满足满足C1. 把把 扩张扩张到

35、到l(和和lc)上上: 若若l=p, 则令则令 (p)=0; 若若lc=p, 则令则令 (p)=1. 恒有恒有 (lc)=1, 从而从而 满足满足C2. 得证得证C1 C2是可满足的是可满足的. 注意注意: C1 C2与与Res(C1,C2)有相同的可满足性有相同的可满足性, 但不一但不一定等值定等值.42/63消解序列与合取范式的否证消解序列与合取范式的否证定义定义2.10 设设S是一个合取范式是一个合取范式, C1,C2,Cn是一个简是一个简单析取式序列单析取式序列. 如果对每一个如果对每一个i(1 i n), Ci是是S的一个的一个简单析取式或者是简单析取式或者是Res(Cj,Ck)(1

36、 jki), 则称此序列则称此序列是由是由S导出导出Cn的的消解序列消解序列. 当当Cn= 时时, 称此序列是称此序列是S的的一个一个否证否证.定理定理2.9 一个合取范式是不可满足的当且仅当它有一个合取范式是不可满足的当且仅当它有否证否证.例例11 用消解规则证明用消解规则证明S=( p q) (p qs) (q s)q是不可满足的是不可满足的.证证 C1= p q, C2= p qs, C3=Res(C1,C2)=qs, C4=q s, C5=Res(C3,C4)=q, C6= q, C7=Res(C5,C6)= , 这是这是S的否证的否证.43/63消解算法消解算法输入输入: 合式公式合

37、式公式A输出输出: 当当A是可满足时是可满足时, 回答回答“Yes”; 否则回答否则回答“No”.1. 求求A的合取范式的合取范式S2. 令令S0, S2, S1S的所有简单析取式的所有简单析取式3. For C1 S0和和C2 S14. If C1, C2可以消解可以消解 then5. 计算计算CRes(C1,C2)6. If C= then7. 输出输出“No”, 计算结束计算结束 8. If C S0且且C S1 then9. S2S2 C44/63消解算法消解算法10. For C1 S1, C2 S1且且C1 C211. If C1, C2可以消解可以消解 then12. 计算计算C

38、Res(C1,C2)13. If C= then14. 输出输出“No”, 计算结束计算结束 15. If C S0且且C S1 then16. S2S2 C17. If S2= then 18. 输出输出“Yes”, 计算结束计算结束19. Else S0S0 S1, S1S2, S2, goto 345/63消解算法例题消解算法例题例例12 用消解算法判断下述公式是否是可满足的用消解算法判断下述公式是否是可满足的: p (p q) (pq) (qr) (q r)解解 S= p (p q) (pq) (qr) (q r)循环循环1 S0=, S1=p, p q, pq, qr, q r, S

39、2= Res(p q, pq)=p Res(pq, qr)=pr Res(pq, q r)= p r Res(qr, q r)=q S2=p r, pr, q46/63消解算法例题消解算法例题 Res(qr, p r)=p q Res(q r, pr)=p q Res(p r, pr)=p S2= 输出输出“Yes”循环循环2 S0=p, p q, pq, qr, q r, S1=p r, pr, q, S2= Res(pq, q)=p47/63练习练习1:概念概念1. 设设A与与B为含为含n个命题变项的公式，判断下列命题是个命题变项的公式，判断下列命题是否为真？否为真？(1) AB当且仅当A

40、与B有相同的主析取范式(2) 若A为重言式，则A的主合取范式为0(3) 若A为矛盾式，则A的主析取范式为1(4) 任何公式都能等值地化成, 中的公式(5) 任何公式都能等值地化成, , 中的公式真真假假假假假假真真48/63练习练习1:概念概念说明说明:(2) 重言式的主合取范式不含任何极大项，为重言式的主合取范式不含任何极大项，为1. (3) 矛盾式的主合析范式不含任何极小项矛盾式的主合析范式不含任何极小项， 为为0. (4) , 不是完备集，如矛盾式不能写成不是完备集，如矛盾式不能写成 , 中的中的公式公式. (5) , 是完备集是完备集. 49/63练习练习2: 判断公式类型判断公式类型

41、解解 用等值演算法求主范式用等值演算法求主范式 (pq)( qp) ( p q) (qp) (pq) (qp) (pq) ( p q) (p q) ( pq) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式主析取范式 1 主合取范式主合取范式2. 判断下列公式的类型判断下列公式的类型: (1) (pq)( qp)重言式重言式50/63练习题练习题2(续续)解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式(2) (pq) q矛盾式矛盾式51/63解解 用等值演算

42、法求公式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式(3) (pq)p练习练习2(续续)非重言式的可满足式非重言式的可满足式52/63练习练习3：求公式的主范式求公式的主范式3已知命题公式已知命题公式A中含中含3个命题变项个命题变项p, q, r，并知道，并知道它的成真赋值为它的成真赋值为001, 010, 111, 求求A的主析取范式的主析取范式和主合取范式，及和主合取范式，及A对应的真值函数对应的真值函数.解解 A的主析取范式为的主析取范式为m1 m2 m7A的主合取范式为的

43、主合取范式为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 0 1 1 1 0 00 1 1 0 1 1 1 153/63练习练习4：联结词完备集联结词完备集4将将A = (pq) r改写成下述各联结词集中的公式改写成下述各联结词集中的公式: (1) , , (2) , (3) , (4) , (5) (6) 解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)54/63练习练习4 解答解答 (4) (pq) r ( (pq)r)

44、 (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 r) 说明：答案不惟一说明：答案不惟一55/63练习练习5：应用题：应用题5. 某公司要从赵、钱、孙、李、周五名新毕业的大某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习学生中选派一些人出国学习. 选派必须满足以下条选派必须满足以下条件：件：(1) 若赵去，钱也去若赵去，钱也去.(2) 李、周两人中至少有一人去李、周两人中至少有一人去(3) 钱、孙两人中

45、去且仅去一人钱、孙两人中去且仅去一人.(4) 孙、李两人同去或同不去孙、李两人同去或同不去.(5) 若周去，则赵、钱也去若周去，则赵、钱也去. 用等值演算法分析该公司如何选派他们出国？用等值演算法分析该公司如何选派他们出国？56/63练习练习5解答解答解此类问题的步骤：解此类问题的步骤：1.设简单命题并符号化设简单命题并符号化2. 用复合命题描述各条件用复合命题描述各条件3. 写出由复合命题组成的合取式写出由复合命题组成的合取式4. 将合取式成析取式（最好是主析取范式）将合取式成析取式（最好是主析取范式）5. 求成真赋值求成真赋值, 并做出解释和结论并做出解释和结论57/63练习练习5解答解答

46、解解1. 设简单命题并符号化设简单命题并符号化设设 p: 派赵去，派赵去，q: 派钱去，派钱去，r: 派孙去，派孙去，s: 派李去，派李去，u: 派周去派周去2. 写出复合命题写出复合命题(1) 若赵去，钱也去若赵去，钱也去 pq(2) 李、周两人中至少有一人去李、周两人中至少有一人去 s u(3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人 (qr) ( q r)(4) 孙、李两人同去或同不去孙、李两人同去或同不去 (r s) ( rs)(5) 若周去，则赵、钱也去若周去，则赵、钱也去 u(p q) 58/63 3. 设设(1)(5)构成的合取式为构成的合取式为A A = (pq) (

47、s u) (qr) ( q r) (r s) ( rs) (u(p q)4. 化成析取式化成析取式 A ( pq r su) (p qrs u)结论：由上述析取式可知，结论：由上述析取式可知，A的成真赋值为的成真赋值为00110与与11001， 派孙、李去（赵、钱、周不去）派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去）派赵、钱、周去（孙、李不去）练习练习5解答解答59/63练习练习5解答解答A ( p q) (qr) ( q r) (s u) ( u (p q) (r s) ( rs) B1=( p q) (qr) ( q r) ( p qr) ( pq r) (qr) （分配律）

48、（分配律） 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)60/63练习练习6:消解法消解法6. 构造公式构造公式A=(p q) ( q r) ( p q)r的否证的否证, 从而证明它是矛盾式从而证明它是矛盾式.解解 消解序列消解序列: p q A的简单析取式的简单析取式 p q A的简单析取式的简单析取式 q ,消解消解 q r

49、 A的简单析取式的简单析取式 r A的简单析取式的简单析取式 q ,消解消解 ,消解消解这是这是A的一个否证的一个否证, 从而证明从而证明A是矛盾式是矛盾式. 61/63练习练习7:消解法消解法7. 用消解法判断下述公式是否是可满足的用消解法判断下述公式是否是可满足的: (pq) (qr) ( qr)解解 S=(pq) (qr) ( qr)第第1次循环次循环 S0=,S1=pq, qr, qr, S2=pq, qr 消解得到消解得到pr qr, qr消解得到消解得到 rS2=pr, r第第2次循环次循环 S0=pq, qr, qr,S1=pr, r, S2=S2=输出输出“Yes”,计算结束计

50、算结束. 62/63总总 结结主要内容主要内容l等值式与等值演算等值式与等值演算l基本等值式基本等值式（16组，组，24个公式个公式）l主析取范式与主合取范式主析取范式与主合取范式l联结词完备集联结词完备集l消解法消解法基本要求基本要求l 深刻理解等值式的概念l 牢记基本等值式的名称及它们的内容l 熟练地应用基本等值式及置换规则进行等值演算63/63总总 结结l 理解文字、简单析取式、简单合取式、析取范式、合取范式的概念l 深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系l 熟练掌握求主范式的方法（等值演算、真值表等）l 会用主范式求公式的成真赋