《ch2命题逻辑等值演算课件》由会员分享，可在线阅读，更多相关《ch2命题逻辑等值演算课件（62页珍藏版）》请在金锄头文库上搜索。
1、1主要内容主要内容l等值式与基本的等值式等值式与基本的等值式l等值演算与置换规则等值演算与置换规则l析取范式与合取范式，主析取范式与主合取范式析取范式与合取范式，主析取范式与主合取范式l联结词完备集联结词完备集l可满足性问题与消解法可满足性问题与消解法第二章第二章 命题逻辑等值演算命题逻辑等值演算22.1 等值式等值式定义定义2.1 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作，记作AB，并称，并称AB是是等值式等值式几点说明：几点说明：l定义中，定义中，A, B, 均为元语言符号均为元语言符号l A或或B中可能有哑元出现中可能有哑元出现. 例如例如 (pq) ( p
2、 q) ( r r) r为左边公式的哑元为左边公式的哑元. l用真值表可检查两个公式是否等值用真值表可检查两个公式是否等值请验证：请验证： p(qr) (p q) r p(qr) 不与不与 (pq) r 等值等值3等值式例题等值式例题例例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 rp q00000011 结论结论: : p(qr) (p q) r 4等值式例题等值式例题
3、 (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 不等值不等值5基本等值式基本等值式双重否定律双重否定律 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)德摩根律德摩根律
4、 (A B)AB (A B)AB吸收律吸收律 A (A B)A, A (A B)A6基本等值式基本等值式零律零律 A 11, A 00同一律同一律 A 0A. A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB) (BA)假言易位假言易位 ABBA等价否定等值式等价否定等值式 ABAB归谬论归谬论 (AB) (AB) A特别提示：必须牢记这特别提示：必须牢记这16组等值式，这是继续学习的基础组等值式，这是继续学习的基础7等值演算与置换规则等值演算与置换规则1. 等值演算等值演算由已知的等值式推演出新的等值式的过程由已知的等值式推演出
5、新的等值式的过程2. 等值演算的基础：等值演算的基础： (1) 等值关系的性质：自反性、对称性、传递性等值关系的性质：自反性、对称性、传递性 (2) 基本的等值式基本的等值式 (3) 置换规则（见置换规则（见3）3. 置换规则置换规则 设设 (A) 是含公式是含公式 A 的命题公式，的命题公式， (B) 是用公式是用公式 B 置换置换 (A) 中所有的中所有的 A 后得到的命题公式后得到的命题公式 若若 BA，则，则 (B)(A)8等值演算的应用举例等值演算的应用举例证明两个公式等值证明两个公式等值例例2 证明证明 p(qr) (p q)r证证 p(qr) p ( q r) （蕴涵等值式，置换
6、规则）（蕴涵等值式，置换规则） ( pq) r （结合律，置换规则）（结合律，置换规则） (p q) r （德摩根律，置换规则）（德摩根律，置换规则） (p q)r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则）今后在注明中省去置换规则今后在注明中省去置换规则注意：用等值演算不能直接证明两个公式不等值注意：用等值演算不能直接证明两个公式不等值9证明两个公式不等值证明两个公式不等值例例3 证明证明 p(qr) 与与 (pq)r 不等值不等值证证 方法一方法一 真值表法真值表法, 见例见例1(2)方法二方法二 观察法观察法. 观察到观察到000, 010是左边的成真赋值，是右是左边的成真赋值，是
7、右边的成假赋值边的成假赋值 方法三方法三 先用等值演算化简公式，然后再观察先用等值演算化简公式，然后再观察 p(qr) pq r (pq)r ( p q) r(pq) r 更容易看出前面的两个赋值分别是更容易看出前面的两个赋值分别是左边的成真赋左边的成真赋 值和右边的成假赋值值和右边的成假赋值等值演算的应用举例等值演算的应用举例10判断公式类型判断公式类型: A为矛盾式当且仅当为矛盾式当且仅当A 0 A为重言式当且仅当为重言式当且仅当A 1例例4 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型 (1) q(pq) (2) (pq)( qp) (3) (p q) (pq) r) 等
8、值演算的应用举例等值演算的应用举例解解 (1) q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）矛盾式矛盾式11判断公式类型判断公式类型(2) (pq)( qp) ( p q)(qp) （蕴涵等值式）（蕴涵等值式） ( p q)( p q) （交换律）（交换律） 1重言式重言式(3) (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）可满足式，可满足式，101和和
9、111是成真赋值，是成真赋值，000和和010等是成假赋值等是成假赋值. 122.2 析取范式与合取范式析取范式与合取范式基本概念基本概念(1) 文字文字命题变项及其否定的总称命题变项及其否定的总称(2) 简单析取式简单析取式有限个文字构成的析取式有限个文字构成的析取式 p, q, pq, p q r, (3) 简单合取式简单合取式有限个文字构成的合取式有限个文字构成的合取式 p, q, pq, p q r, (4) 析取范式析取范式由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 p, p q, pq, (pq) ( p qr) (q r)(5) 合取范式合取范式由有限个简单析取
10、式组成的合取式由有限个简单析取式组成的合取式 p, pq, p q, (p q)p (p q r)(6) 范式范式析取范式与合取范式的总称析取范式与合取范式的总称13范式概念范式概念说明：说明：l单个文字既是简单析取式，又是简单合取式单个文字既是简单析取式，又是简单合取式l形如形如 pq r, p qr 的的公式既是析取范式，又是合公式既是析取范式，又是合取范式取范式14范式的性质范式的性质定理定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含有某一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式个命题变项和它的否定式.(2) 一个简单合取式是矛盾式当且仅当它同时含有某个
11、命题一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式变项和它的否定式.定理定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式取式都是矛盾式.(2) 一个合取范式是重言式当且仅当它的每个简单析取式都一个合取范式是重言式当且仅当它的每个简单析取式都是重言式是重言式.15命题公式的范式命题公式的范式定理定理2.3（范式存在定理）（范式存在定理） 任何命题公式都存在与之等值的析取范式与合取范式任何命题公式都存在与之等值的析取范式与合取范式公式公式A的析取的析取(合取合取)范式范式与与A等值的等值的析取析取(合取合取)范式范
12、式求公式求公式A的范式的步骤：的范式的步骤： (1) 消去消去A中的中的, （若存在）（若存在） ABA B AB( A B) (AB) (2) 否定联结词否定联结词 的内移或消去的内移或消去 A A (A B)AB (A B)AB16命题公式的范式命题公式的范式 (3) 使用分配律使用分配律 A (B C)(A B) (A C) 求合取范式求合取范式 A (B C) (A B) (A C) 求析取范式求析取范式公式范式的不足公式范式的不足不惟一不惟一17求公式的范式求公式的范式例例5 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式 (1) (pq)r (2) (pq)r解解 (
13、1) (pq)r ( pq)r （消去（消去） pqr （结合律）（结合律）最后结果既是析取范式最后结果既是析取范式(由由3个简单合取式组成的析取式个简单合取式组成的析取式)，又，又是合取范式是合取范式(由一个简单析取式组成的合取式由一个简单析取式组成的合取式) 18 (2) (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r （消去第二个（消去第二个） (p q) r （否定号内移（否定号内移德摩根律德摩根律) 析取范析取范式式 (p r) (q r) （ 对对 分配律）分配律） 合取范式合取范式求公式的范式求公式的范式19极小项与极大项极小项与极大项定义定义2.4 在含有
14、在含有n个命题变项的简单合取式（简单析取式）个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第一次，而且第i个文字出现在左起第个文字出现在左起第i位上（位上（1 i n），称这），称这样的简单合取式（简单析取式）为样的简单合取式（简单析取式）为极小项极小项（极大项极大项）.几点说明：几点说明：ln个命题变项有个命题变项有2n个极小项和个极小项和2n个极大项个极大项l2n个极小项（极大项）均互不等值个极小项（极大项）均互不等值l用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值的
15、十进制是该极小项成真赋值的十进制表示表示. 用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极大项成假赋值的是该极大项成假赋值的十进制表示十进制表示. mi（Mi）称为极小项（极大项）的名称）称为极小项（极大项）的名称. 20实例实例由两个命题变项由两个命题变项 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 1M0M1M2M321实例实例极小极小项项极大极大项项公式
16、公式成真成真赋值赋值名称名称公式公式成假成假赋值赋值名称名称 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 形成的极小项与极大项形成的极小项与极大项. mi与与Mi的关系：的关系： mi M
17、i, Mi mi 22主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变项为命题变项为 p, q, r 时，时， ( pq r) ( p q r) m1 m3 主析取范式主析取范式 (p qr) ( pqr) M1 M7主合取范式主合取范式公式公式A的主析取的主析取(合取合取)范式范式与与A 等值的主析取等值的主析取(合取合取)范式范式 定理定理2.5 (主范式的存在惟一定理主范式的存在惟一定理) 任何命题公式都存在与之等值的主析取范式和主合取范
18、式任何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的并且是惟一的23求公式主范式的步骤求公式主范式的步骤求公式主析取范式的步骤求公式主析取范式的步骤:设公式设公式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求公式主范式的步骤求公式主范式的步骤求公式的主合取范式的步骤求公式的主合取范式的步骤:设公式设公式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) 重复这个过程重复这个过程, 直到所有简单析取
20、式都是长度为直到所有简单析取式都是长度为n的极的极 大项为止大项为止(3) 消去重复出现的极大项消去重复出现的极大项, 即用即用Mi代替代替Mi Mi(4) 将极大项按下标从小到大排列将极大项按下标从小到大排列25实例实例例例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 , 代入代入并排序，
21、得并排序，得 (pq)r m1 m3 m5 m6 m7 （主析取范式）（主析取范式）26实例实例 (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 （主合取范式（主合取范式）27主范式的应用主范式的应用1.1.求公式的成真成假赋求公式的成真成假赋值值 设公式设公式A含含n个命题变项个命题变项, A的主析取范式有的主析取范式有s个极小项个极小项, 则则A 有有s个成真赋值个成真赋值
22、, 它们是极小项下标的二进制表示它们是极小项下标的二进制表示, 其余其余2n-s 个赋值都是成假赋值个赋值都是成假赋值 例如例如 (pq)r m1 m3 m5 m6 m7成真赋值为成真赋值为 001, 011, 101, 110, 111，成假赋值为成假赋值为 000, 010, 100. 类似地，由主合取范式也立即求出成假赋值和成真赋值类似地，由主合取范式也立即求出成假赋值和成真赋值. 282. 判断公式的类型判断公式的类型 设设A含含n个命题变项个命题变项. A为重言式为重言式 A的主析取范式含全部的主析取范式含全部2n个极小项个极小项 A的主合取范式不含任何极大项的主合取范式不含任何极大
23、项, 记为记为1. A为矛盾式为矛盾式 A的主合析取范式含全部的主合析取范式含全部2n个极大项个极大项 A的主析取范式不含任何极小项的主析取范式不含任何极小项, 记为记为0. A为非重言式的可满足式为非重言式的可满足式 A的主析取范式中至少含一个、但不是全的主析取范式中至少含一个、但不是全 部极小项部极小项 A的主合取范式中至少含一个、但不是全的主合取范式中至少含一个、但不是全 部极大项部极大项.主范式的应用主范式的应用29例例7 用主析取范式判断公式的类型用主析取范式判断公式的类型:(1) A (pq) q (2) B p(p q) (3) C (p q)r解解 (1) A ( p q) q
24、 ( 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 非重言式的可满足式非重言式的可满足式主范式的应用主范式的应用303. 判断两个公式是否等值判断两个公式是否等值例例8 用主析取范式判以下每一组公式是否等值用主析取范式判以下每一组公式是否等值 p(qr) 与与 (p q)r p(qr) 与与 (pq)r解解 p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r
25、= m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4 m5 m7显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值.主范式的应用主范式的应用314. 解实际问题解实际问题例例9 某单位要从某单位要从A,B,C三人中选派若干人出国考察三人中选派若干人出国考察, 需满足下需满足下 述条件述条件: (1) 若若A去去, 则则C必须去必须去; (2) 若若B去去, 则则C不能去不能去; (3) A和和B必须去一人且只能去一人必须去一人且只能去一人. 问有几种可能的选派方案问有几种可能的选派方案?解解 记记 p:派派A去去, q:派派B去去, r:派派C去去(1)
26、 pr, (2) qr, (3) (pq) ( p q)求下式的成真赋值求下式的成真赋值 A=(pr) (qr) (pq) ( p q)主范式的应用主范式的应用32求求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去
27、去, 方案方案2 派派B去去主范式的应用主范式的应用33由主析取范式确定主合取范式由主析取范式确定主合取范式例例10 设设A有有3个命题变项个命题变项, 且已知且已知A= m1 m3 m7, 求求A的主合取的主合取范式范式.解解 A的成真赋值是的成真赋值是1,3,7的二进制表示的二进制表示, 成假赋值是在主析取成假赋值是在主析取范式中没有出现的极小项的下角标范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示的二进制表示, 它它们恰好是们恰好是A的主合取范式的极大项的下角标的主合取范式的极大项的下角标, 故故 A M0 M2 M4 M5 M6用成真赋值和成假赋值确定主范式用成真赋值和成
28、假赋值确定主范式由主合取范式确定主析取范式由主合取范式确定主析取范式用真值表确定主范式用真值表确定主范式 342.3 联结词的完备集联结词的完备集定义定义2.6 称称F:0,1n 0,1 为为n元真值函数元真值函数. 0,1n=000, 001, , 111，包含，包含 个长为个长为n的的0,1符号串符号串. 共有共有 个个n元真值函数元真值函数. 1元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1 35真值函数真值函数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
29、 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 12元真值函数元真值函数36公式与真值函数公式与真值函数任何一个含任何一个含n个命题变项的命题公式个命题变项的命题公式A都对应惟一的一个都对应惟一的一个n元元真值函数真值函数 F , F 恰好为恰好为A的真值表的真值表. 等值的公式对应的真值函数相同等值的公式对应的真值函数相同. 例如：例如：pq, p q 都对应都对应37联结词完备集联结词完备集定义定义2.7 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1) 元真值函
30、元真值函数都可以由仅含数都可以由仅含S中的联结词构成的公式表示，则称中的联结词构成的公式表示，则称S是是联结联结词完备集词完备集若若S是联结词完备集是联结词完备集, 则任何命题公式都可由则任何命题公式都可由S中的联结词表示中的联结词表示定理定理2.6 S = , , 是联结词完备集是联结词完备集证明证明 由范式存在定理可证由范式存在定理可证38联结词完备集联结词完备集推论推论 以下都是联结词完备集以下都是联结词完备集 (1) S1 = , , , (2) S2 = , , , , (3) S3 = , (4) S4 = , (5) S5 = , 证明证明(1),(2) 在联结词完备集中加入新的
31、联结词后仍为完备集在联结词完备集中加入新的联结词后仍为完备集(3) A B ( AB)(4) A B ( AB)(5) ABA B , ,不是联结词完备集不是联结词完备集, 0不能用它表示不能用它表示它的子集它的子集 , , , , , ,等都不是等都不是39复合联结词复合联结词定义定义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
32、.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) 得证得证 为联结词完备集为联结词完备集. 对对 类似可证类似可证402.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( p q r, p qs)= q rs41消解规则消解规则定理定理2.8 C1 C2 Res(C1,C2)证证 记记C
34、= 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. 把扩张到把扩张到l(和和lc)上上:若若l=p, 则令则
35、令 (p)=0; 若若lc=p, 则令则令 (p)=1. 恒有恒有 (lc)=1, 从而从而 满足满足C2. 得证得证C1 C2是可满足的是可满足的.注意注意: C1 C2与与Res(C1,C2)有相同的可满足性有相同的可满足性, 但不一定等值但不一定等值.42消解序列与合取范式的否证消解序列与合取范式的否证定义定义2.10 设设S是一个合取范式是一个合取范式, C1,C2,Cn是一个简单析取式是一个简单析取式序列序列. 如果对每一个如果对每一个i(1 i n), Ci是是S的一个简单析取式或者的一个简单析取式或者是是Res(Cj,Ck)(1 jki), 则称此序列是由则称此序列是由S导出导出
36、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消解算法消解算法消解算法消解算法输入输入: 合式公式合式公式A输出输出: 当当A是可满足时是可满
37、足时, 回答回答“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消解算法消解算法10. For C1 S1, C2 S1且且C1 C211. If C1, C2可以消解可以消解 then12. 计算计算CRes(C1,C2)13. If C= then
38、14. 输出输出“No”, 计算结束计算结束 15. If C S0且且C S1 then16. S2S2 C17. If S2= then 18. 输出输出“Yes”, 计算结束计算结束19. Else S0S0 S1, S1S2, S2, goto 345消解算法例题消解算法例题例例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, S2= Res(p q, pq)=p Res(pq, q
39、r)=pr Res(pq, q r)= p r Res(qr, q r)=q S2=p r, p r, q循环循环2 S0=p, p q, pq, qr, q r, S1=p r, p r, q, S2= Res(pq, q)=p46消解算法例题消解算法例题 Res(qr, p r)=p q Res(q r, pr)=p q Res(p r, pr)=p S2= 输出输出“Yes”47第二章第二章 习题课习题课作业：作业：P42 4 (1),(3); 5 (1),(3) ;8 (3);12 ;27(1);30P42 4 (1),(3); 5 (1),(3) ;8 (3);12 ;27(1);3
40、0主要内容主要内容l等值式与等值演算等值式与等值演算l基本等值式（基本等值式（1616组，组，2424个公式）个公式）l主析取范式与主合取范式主析取范式与主合取范式l联结词完备集联结词完备集l消解法消解法48基本要求基本要求l深刻理解等值式的概念深刻理解等值式的概念l牢记基本等值式的名称及它们的内容牢记基本等值式的名称及它们的内容l熟练地应用基本等值式及置换规则进行等值演算熟练地应用基本等值式及置换规则进行等值演算l理解文字、简单析取式、简单合取式、析取范式、合取范理解文字、简单析取式、简单合取式、析取范式、合取范式的概念式的概念l深刻理解极小项、极大项的概念、名称及下角标与成真、深刻理解极小
41、项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系成假赋值的关系，并理解简单析取式与极小项的关系l熟练掌握求主范式的方法（等值演算、真值表等）熟练掌握求主范式的方法（等值演算、真值表等）l会用主范式求公式的成真赋值、成假赋值、判断公式的类会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值型、判断两个公式是否等值l会将公式等值地化成指定联结词完备集中的公式会将公式等值地化成指定联结词完备集中的公式l会用命题逻辑的概念及运算解决简单的应用问题会用命题逻辑的概念及运算解决简单的应用问题l掌握消解规则及其性质掌握消解规则及其性质l会用消解算法判
42、断公式的可满足性会用消解算法判断公式的可满足性49练习练习1:概念概念1. 设设A与与B为含为含n个命题变项的公式，判断下列命题是否为真？个命题变项的公式，判断下列命题是否为真？(1) AB当且仅当当且仅当A与与B有相同的主析取范式有相同的主析取范式(2) 若若A为重言式，则为重言式，则A的主合取范式为的主合取范式为0(3) 若若A为矛盾式，则为矛盾式，则A的主析取范式为的主析取范式为1(4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公式说明说明:(2) 重言式的主合取范式不含任何极大项，为重言
43、式的主合取范式不含任何极大项，为1. (3) 矛盾式的主合析范式不含任何极小项矛盾式的主合析范式不含任何极小项, 为为0. (4) , 不是完备集，如矛盾式不能写成不是完备集，如矛盾式不能写成 , 中的公式中的公式. (5) , 是完备集是完备集. 真真假假假假假假真真50练习练习2: 判断公式类型判断公式类型解解 用等值演算法求主范式用等值演算法求主范式 (pq)( qp) ( p q) (qp) (pq) (qp) (pq) ( p q) (p q) ( pq) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式主析取范式 1 主合取范式主合取范式2. 判断下列公式的类型判断下列公
44、式的类型: (1) (pq)( qp)重言式重言式51练习题练习题2(续续)解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式(2) (pq) q矛盾式矛盾式52解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式(3) (pq)p练习练习2(续续)非重言式的可满足式非重言式的可满足式53练习练习3：求公式的主范式求公式的主范式3已知命题公式已
45、知命题公式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 0 1 1 1 0 00 1 1 0 1 1 1 154练习练习4：联结词完备集联结词完备集4将将A = (pq) r改写成下述各联结词集中的公式改写成下述各联结词集
46、中的公式: (1) , , (2) , (3) , (4) , (5) (6) 解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)55练习练习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 r) 说明：答案不惟一说明：答案不惟一56练习练习5：应用题：应用题5. 某公司要从赵、钱、
47、孙、李、周五名新毕业的大学生中选某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习派一些人出国学习. 选派必须满足以下条件：选派必须满足以下条件：(1) 若赵去，钱也去若赵去，钱也去.(2) 李、周两人中至少有一人去李、周两人中至少有一人去(3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人.(4) 孙、李两人同去或同不去孙、李两人同去或同不去.(5) 若周去，则赵、钱也去若周去，则赵、钱也去. 用等值演算法分析该公司如何选派他们出国？用等值演算法分析该公司如何选派他们出国？57练习练习5解答解答解此类问题的步骤：解此类问题的步骤：1.设简单命题并符号化设简单命题并符号化2
48、. 用复合命题描述各条件用复合命题描述各条件3. 写出由复合命题组成的合取式写出由复合命题组成的合取式4. 将合取式成析取式（最好是主析取范式）将合取式成析取式（最好是主析取范式）5. 求成真赋值求成真赋值, 并做出解释和结论并做出解释和结论58练习练习5解答解答解解1. 设简单命题并符号化设简单命题并符号化设设 p: 派赵去，派赵去，q: 派钱去，派钱去，r: 派孙去，派孙去，s: 派李去，派李去，u: 派周去派周去2. 写出复合命题写出复合命题(1) 若赵去，钱也去若赵去，钱也去 pq(2) 李、周两人中至少有一人去李、周两人中至少有一人去 s u(3) 钱、孙两人中去且仅去一人钱、孙两人
49、中去且仅去一人 (qr) ( q r)(4) 孙、李两人同去或同不去孙、李两人同去或同不去 (r s) ( rs)(5) 若周去，则赵、钱也去若周去，则赵、钱也去 u(p q) 59 3. 设设(1)(5)构成的合取式为构成的合取式为A A = (pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)4. 化成析取式化成析取式 A ( pq r su) (p qrs u)结论：由上述析取式可知，结论：由上述析取式可知，A的成真赋值为的成真赋值为00110与与11001， 派孙、李去（赵、钱、周不去）派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去）派赵、钱、
50、周去（孙、李不去）练习练习5解答解答60练习练习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) （分配律）（分配律） 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)61练习练习6:消解法
51、消解法6. 构造公式构造公式A=(p q) ( q r) ( p q)r的否证的否证, 从而从而证明证明它是矛盾式它是矛盾式.解解 消解序列消解序列: p q A的简单析取式的简单析取式 p q A的简单析取式的简单析取式 q ,消解消解 q r A的简单析取式的简单析取式 r A的简单析取式的简单析取式 q ,消解消解 ,消解消解这是这是A的一个否证的一个否证, 从而证明从而证明A是矛盾式是矛盾式. 62练习练习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”,计算结束计算结束.
