《离散数学-耿素云PPT(第5版)1.3-4》由会员分享，可在线阅读，更多相关《离散数学-耿素云PPT(第5版)1.3-4（34页珍藏版）》请在金锄头文库上搜索。
1、11.3 命题逻辑等值演算 等值式 基本等值式 等值演算 置换规则2等值式 定义 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式 说明：定义中，A,B,均为元语言符号, A或B中 可能有哑元出现. 例如，在 (pq) (pq) (rr)中，r为左边 公式的哑元. 用真值表可验证两个公式是否等值 请验证：p(qr) (pq) rp(qr) (pq) r 3基本等值式 双重否定律 : AA 等幂律： AAA, AAA 交换律: ABBA, ABBA 结合律: (AB)CA(BC) (AB)CA(BC) 分配律: A(BC)(AB)(AC) A(BC) (AB)(AC)4基本等值
2、式(续)德摩根律: (AB)AB(AB)AB 吸收律: A(AB)A, A(AB)A 零律: A11, A00 同一律: A0A, A1A 排中律: AA1 矛盾律: AA05基本等值式(续)蕴涵等值式: ABAB 等价等值式: AB(AB)(BA) 假言易位: ABBA 等价否定等值式: ABAB 归谬论: (AB)(AB) A 注意: A,B,C代表任意的命题公式牢记这些等值式是继续学习的基础6等值演算与置换规则 等值演算: 由已知的等值式推演出新的等值式的过程 置换规则：若AB, 则(B)(A) 等值演算的基础：(1) 等值关系的性质：自反、对称、传递(2) 基本的等值式(3) 置换规则
3、 7应用举例证明两个公式等值 例1 证明 p(qr) (pq)r 证 p(qr) p(qr) （蕴涵等值式，置换规则）(pq)r （结合律，置换规则）(pq)r （德摩根律，置换规则）(pq) r （蕴涵等值式，置换规则） 说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出 8应用举例证明两个公式不等值例2 证明: p(qr) (pq) r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假.方法一 真值表法（自己证）方法二 观察赋值法. 容易看出000, 010等是左边的 的成真赋值，是右
4、边的成假赋值.方法三 用等值演算先化简两个公式，再观察.9应用举例判断公式类型 例3 用等值演算法判断下列公式的类型 (1) q(pq) 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 由最后一步可知，该式为矛盾式. 10例3 (续)(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1由最后一步可知，该式为重言式. 问：最后一步为什么等值于1？ 11例3 (续)(3) (pq)(pq)r) 解 (pq)(pq)r) (p(qq)r （分配律） p1
5、r （排中律） pr （同一律）这不是矛盾式，也不是重言式，而是非重言式的可 满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些121.4 范式 析取范式与合取范式 主析取范式与主合取范式 13析取范式与合取范式 文字:命题变项及其否定的总称 简单析取式:有限个文字构成的析取式 如 p, q, pq, pqr, 简单合取式:有限个文字构成的合取式 如 p, q, pq, pqr, 析取范式:由有限个简单合取式组成的析取式A1A2Ar, 其中A1,A2,Ar是简单合取式合取范式:由有限个简单析取式组成的合
6、取式A1A2Ar , 其中A1,A2,Ar是简单析取式14析取范式与合取范式(续)范式:析取范式与合取范式的总称 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 pqr, pqr既是析取范式，又是合取范式 (为什么?) 15命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式与合取范式. 求公式A的范式的步骤：(1) 消去A中的, （若存在）(2) 否定联结词的内移或消去(3) 使用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一16求公式的范式举例 例 求下列公式的析取范式与合取范式 (
7、1) A=(pq)r 解 (pq)r (pq)r （消去） pqr （结合律）这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式组成的合取式）17求公式的范式举例(续)(2) B=(pq)r 解 (pq)r (pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定号内移德摩根律）这一步已为析取范式（两个简单合取式构成）继续： (pq)r (pr)(qr) （对分配律）这一步得到合取范式（由两个简单析取式构成） 18极小项与极大项 定义 在含有n个命题变项的简单合取式(简单析取式)中， 若每个命题变项均以文字的形式出现且仅出现一次，称这 样
8、的简单合取式(简单析取式)为极小项(极大项）.说明：n n个命题变项产生2n个极小项和2n个极大项n 2n个极小项（极大项）均互不等值n 在极小项和极大项中文字均按下标或字母顺序排列n 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示, mi(Mi)称为极小项(极大项)的名称. n mi与Mi的关系: mi Mi , Mi mi 19极小项与极大项(续)由p, q两个命题变项形成的极小项与极大项 公式 成真赋值名称 公式 成假赋值名称 p qp qp qp q0 00 11 01 1 m0 m1 m2 m3 p q p
9、 qp qp q 0 00 11 01 1 M0 M1 M2 M3 极小项 极大项 20由p, q, r三个命题变项形成的极小项与极大项 极小项 极大项 公式 成真 赋值名称 公式 成假 赋值名称 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 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1m0 m1 m2 m3 m4 m5 m6 m7p 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 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1
10、1 1 0 1 1 1M0 M1 M2 M3 M4 M5 M6 M7 21主析取范式与主合取范式 主析取范式: 由极小项构成的析取范式 主合取范式: 由极大项构成的合取范式例如，n=3, 命题变项为p, q, r时，(pqr)(pqr) m1m3 是主析取范式 (pqr)(pqr) M1M5 是主合取范式 A的主析取范式: 与A等值的主析取范式A的主合取范式: 与A等值的主合取范式. 22主析取范式与主合取范式(续)定理 任何命题公式都存在着与之等值的主析取范 式和主合取范式, 并且是唯一的. 用等值演算法求公式的主范式的步骤：(1) 先求析取范式（合取范式）(2) 将不是极小项（极大项）的简
11、单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3) 极小项（极大项）用名称mi（Mi）表示，并 按角标从小到大顺序排序. 23求公式的主范式例 求公式 A=(pq)r的主析取范式与主合取范式.(1) 求主析取范式 (pq)r (pq)r , （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 , 24求公式的主范式(续)r(pp)(qq)r(pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得(pq)r m1m3m5 m6m7（主析取范式） 25求公式的主范式(
12、续)(2) 求A的主合取范式 (pq)r (pr)(qr) , （合取范式） pr p(qq)r (pqr)(pqr) M0M2, 26求公式的主范式(续)qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得(pq)r M0M2M4 （主合取范式） 27主范式的用途与真值表相同 (1) 求公式的成真赋值和成假赋值例如 (pq)r m1m3m5 m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值. 类似地，由主合取范式也可立即求出成假赋值和成真赋值. 28主范式的用途(续)(2) 判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项A的主合取范式为1. A为矛盾式 A的主析取范式为0 A的主合取范式含2n个极大项 A为非重言式的可满足式 A的主析取范式中至少含一个且不含全部极小项 A的主合取范式中至少含一个且不含全部极大项 29主范式的用途(续)例 用主析取范式判断下述两个公式是否等值： p(qr) 与 (pq)r p(qr) 与 (pq)r 解 p(qr) = m
