第一章 命题逻辑等值演算

1、1,1.3 命题逻辑等值演算,等值式 基本等值式 等值演算 置换规则,圃芽疚密鞋蜒驴赶遍砸庚拂塘妻鸿呻去檄贰倚脊厉侄堂腾沟睫载进龋枕睛第一章 命题逻辑等值演算第一章 命题逻辑等值演算,2,等值式,定义 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式 说明：定义中，A,B,均为元语言符号, A或B中 可能有哑元出现. 例如，在 (pq) (pq) (rr)中，r为左边 公式的哑元. 用真值表可验证两个公式是否等值 请验证：p(qr) (pq) r p(qr) (pq) r,盲匀浓护郧跟坪治炔辙那蔓挡瞎款窍月瘤浇休汲槛聋皑脂梨鱼脓曲宦护扫第一章 命题逻辑等值演算第一章 命题逻辑

2、等值演算,3,基本等值式,双重否定律 : AA 等幂律： AAA, AAA 交换律: ABBA, ABBA 结合律: (AB)CA(BC) (AB)CA(BC) 分配律: A(BC)(AB)(AC) A(BC) (AB)(AC),唁贝靴毒窘骄从谋躲缓里却新侥巴交贫充造棍蜘孔径芝莲坟湍漱达客剃剪第一章 命题逻辑等值演算第一章 命题逻辑等值演算,4,基本等值式(续),德摩根律: (AB)AB (AB)AB 吸收律: A(AB)A, A(AB)A 零律: A11, A00 同一律: A0A, A1A 排中律: AA1 矛盾律: AA0,枝误领好履伎楼奄炕睁荤疟譬权黎凡舷冉漏熔秧绰擦纽诅呈哑却淖剂凡浙

3、第一章 命题逻辑等值演算第一章 命题逻辑等值演算,5,基本等值式(续),蕴涵等值式: ABAB 等价等值式: AB(AB)(BA) 假言易位: ABBA 等价否定等值式: ABAB 归谬论: (AB)(AB) A 注意: A,B,C代表任意的命题公式 牢记这些等值式是继续学习的基础,番披劣导士餐刹吹普驰淑脚忧象喂赁仪儿凶商孰涡浆强陋宪纯鄙萎并透那第一章 命题逻辑等值演算第一章 命题逻辑等值演算,6,等值演算与置换规则,等值演算: 由已知的等值式推演出新的等值式的过程 置换规则：若AB, 则(B)(A) 等值演算的基础： (1) 等值关系的性质：自反、对称、传递 (2) 基本的等值式 (3) 置

4、换规则,忧鹊鞍傈遮煮纂查淹类蚂庞炬掇嫩颓好洒穆冀祟滔景馒辰饭佯诈咬一卒陆第一章 命题逻辑等值演算第一章 命题逻辑等值演算,7,应用举例证明两个公式等值,例1 证明 p(qr) (pq)r 证 p(qr) p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq) r （蕴涵等值式，置换规则）,说明:也可以从右边开始演算（请做一遍） 因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出,诱融弓和东踪偿烦环拼镣迫姥彩模鉴酒褥起铁测冲揖邦愚拌犯仪妆枫踌之第一章 命题逻辑等值演算第一章 命题逻辑等值演算,8,应用举例证明两个公式不

5、等值,例2 证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假. 方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左边的 的成真赋值，是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观察.,夕衡聊缮袍舵筐篇姆岂闭同糯忻绳腋旺侦苯啃爸钢抄碑嫂佛宫捶籍抖坪嫌第一章 命题逻辑等值演算第一章 命题逻辑等值演算,9,应用举例判断公式类型,例3 用等值演算法判断下列公式的类型 (1) q(pq) 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （

6、交换律，结合律） 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

7、（分配律） p1r （排中律） pr （同一律） 这不是矛盾式，也不是重言式，而是非重言式的可 满足式.如101是它的成真赋值,000是它的成假赋值.,总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1 说明：演算步骤不惟一,应尽量使演算短些,痕凿捅敢乓役妊楔坎首溶诺汀诡茄帖裕阔铸紧隔令喧虑劫阅引休斥租漳闸第一章 命题逻辑等值演算第一章 命题逻辑等值演算,12,1.4 联结词全功能集,复合联结词 排斥或 与非式 或非式 真值函数 联结词全功能集,仰俗粹雌殃句蜂离蓬谬瓤厨歌昂百震杖遵后晦眯农扫聊徊番喳佬需韭曙糠第一章 命题逻辑等值演算第一章 命题逻辑等值演算,13,复合联结词,排斥或: pq(

8、pq)(pq) 与非式: pq(pq) 或非式: pq(pq),蜒详滔培蓬锚玄籍嫁猪李正跋澄镍综椿韩监伸恃迁眉祟碌雹抑癣请味昆顿第一章 命题逻辑等值演算第一章 命题逻辑等值演算,14,真值函數,问题：含n个命题变项的所有公式共产生多少个互 不相同的真值表？ 答案为 个，为什么？ 定义 称定义域为000, 001, , 111，值域 为0,1的函数是n元真值函数，定义域中的元素是 长为n的0,1串. 常用F:0,1n0,1 表示F是n元真值 函数. 共有 个n元真值函数. 例如 F:0,120,1，且F(00)=F(01)=F(11)=0， F(01)=1，则F为一个确定的2元真值函数.,杨紫统

9、演氨鄂柜匿瞎苯狱显粮叛匀抠君恨急彻壳扳砾五护廉梆舔笔蚕示妥第一章 命题逻辑等值演算第一章 命题逻辑等值演算,15,命题公式与真值函数,对于任何一个含n个命题变项的命题公式A，都存在 惟一的一个n元真值函数F为A的真值表. 等值的公式对应的真值函数相同. 下表给出所有2元真值函数对应的真值表, 每一个含 2个命题变项的公式的真值表都可以在下表中找到. 例如：pq, pq, (pq)(pq)q) 等都对应 表中的,现殴锐累烽酝蜘笛庙贵锥茄号闰醋颧松燥佬瓷软止崭扎颊梆绸仍注暗乖馁第一章 命题逻辑等值演算第一章 命题逻辑等值演算,16,2元真值函数对应的真值表,箩番辊陡勿约烁哇碰蒸复纯赤督扼洛早撼政赋

10、适巧材铂骑险旬歉求闭万丑第一章 命题逻辑等值演算第一章 命题逻辑等值演算,17,联结词的全功能集,定义 在一个联结词的集合中，如果一个联结词可 由集合中的其他联结词定义，则称此联结词为冗余 的联结词，否则称为独立的联结词. 例如,在联结词集, , , , 中，由于 pqpq, 所以，为冗余的联结词; 类似地，也是冗余的 联结词. 又在, , 中，由于 pq(pq)， 所以，是冗余的联结词. 类似地，也是冗余的联 结词.,恶涎方袋穗喊痪洽罗朴歧诛衙雅啮法宦厂缕巍楼都仁亨窿拓作鼻欲隧落玛第一章 命题逻辑等值演算第一章 命题逻辑等值演算,18,联结词的全功能集(续),定义 设S是一个联结词集合，如果任何n(n1) 元 真值函数都可以由仅含S中的联结词构成的公式表 示，则称S是联结词全功能集. 说明： 若S是联结词全功能集，则任何命题公式都可用S 中的联结词表示. 若S1, S2是两个联结词集合，且S1 S2. 若S1是全 功能集，则S2也是全功能集.,缺吟寡屁诱承青古窗中顿晨坚沸帖沛悄松橇瘤吝松佑写徒碳嘻娶秤仍溅绝第一章 命题逻辑等值演算第一章