延安大学西安创新学院《离散数学》课件-第2章 命题逻辑等值演算

《延安大学西安创新学院《离散数学》课件-第2章 命题逻辑等值演算》由会员分享，可在线阅读，更多相关《延安大学西安创新学院《离散数学》课件-第2章 命题逻辑等值演算（62页珍藏版）》请在金锄头文库上搜索。

1、1主要内容主要内容l等值式与基本的等值式等值式与基本的等值式l等值演算与置换规则等值演算与置换规则l析取范式与合取范式，主析取范式与主合取范式析取范式与合取范式，主析取范式与主合取范式l联结词完备集联结词完备集l可满足性问题与消解法可满足性问题与消解法第二章第二章 命题逻辑等值演算命题逻辑等值演算延安大学西安创新学院离散数学22.1 等值式等值式定义定义2.1 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作，记作AB，并称，并称AB是是等值式等值式几点说明：几点说明：l定义中，定义中，A, B, 均为元语言符号均为元语言符号l A或或B中可能有哑元出现中可能有哑元出现.

2、 例如例如 (pq) ( p 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)

3、 r 4等值式例题等值式例题 (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)

4、 (A C)德摩根律德摩根律 (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 (

6、q r) （蕴涵等值式，置换规则）（蕴涵等值式，置换规则） ( 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) (

8、p q) (pq) r) 等值演算的应用举例等值演算的应用举例解解 (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 （同一律）（同一律）可

9、满足式，可满足式，101和和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 qp (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

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

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

15、其中i是该极小项成真赋值的十进制是该极小项成真赋值的十进制表示表示. 用用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 Mi, Mi mi 22主析取范式与主合取范式主析取范式与主合取范式主析取范式主析取范式由极小项构成的析取范式由极小项构成的析取范式主合取范式主合取范式由极大项构成的合取范式由极大项构成的合取范式例如，例如，n=3, 命题变项为命题变项为 p, q, r 时，时， ( pq r) ( p q r) m1 m3 主析取范式主析取范式 (p qr) ( pqr) M1 M7主合