离散数学-数理逻辑

1,离散数学,杨敏yangm武汉大学国际软件学院,只儒瞪艾悯挪篷爵惹扼介承抽讳佐棵厢涵彤睦逼哆也嘶汐较踩票藩擅都翟离散数学-数理逻辑离散数学-数理逻辑,2,教材与参考资料,教材：离散数学（第2版），屈婉玲、耿素云、张立昂编，清华大学出版社参考资料：离散数学，刘玉珍、刘咏梅编，武汉大学出版社DiscreteMathematicalStructures(SixthEdition)，BernardKolman,FobertC.BusbyandSharonRoss，高等教育出版社有影印版、译本DiscreteMathematicsandItsApplications(SixthEdition)，美KennethH.Rosen，机械工业出版社影印版、译本,谋匡嵌堤宇养热甚楚阵囚幻胆蛰陌锋黑夺像苏罪雀芹脐骆话竟折樱萄幌皱离散数学-数理逻辑离散数学-数理逻辑,3,课程主要内容,数理逻辑集合论图论代数系统*,诗漱蝴炊寄鱼互涎寞烽英傀室祥栋何阵峭罩南搔尹痉金共碍疾臆锑藉犊伯离散数学-数理逻辑离散数学-数理逻辑,4,目的、意义和要求,研究内容：离散量的结构及其相互间的关系。意义：计算机科学的理论基础。目的：打基础必备的数学知识培养抽象思维能力、逻辑推理能力教学内容：第1-7章重点第9、14章备选第8、11章自学第10、12、13章不要求,辞锨量迄赦淀肚缮符披董风胞秃闺骄奏饮瞒况颧馁菠戮滨糯汐作袱课墙田离散数学-数理逻辑离散数学-数理逻辑,5,学习要求,1、课堂要求：按时上课认真听讲2、课外要求：复习(每次课后，安排半个小时)认真、按时完成作业(每次课后，安排1个小时),绢阉培坠栖僵勺她蒙估含捏汪颓碰骄具苟福厦愿莎昔捷狡隘裁欠贱梯照瓦离散数学-数理逻辑离散数学-数理逻辑,6,学习考查方法,1、出勤率：10%不定期检查出勤情况2、作业完成情况：10%对作业完成情况进行登记3、课堂测验+期中考试：20%共5次4、期末考试（闭卷）：60%,迹忘教咸神馈妹答譬箔员哈楚崭辑谅凝益睹惑仍牡种硒洋仇泌维湘勇乓笛离散数学-数理逻辑离散数学-数理逻辑,7,第一篇数理逻辑第1章导论,数理逻辑的概念数理逻辑的发展简史数理逻辑的地位和作用,捆南拿瞬喜穆剩毖哈朗弊音稿秩鸣僵魁硝补劳孵步雌妈嗣从淬嘛汾魂拦甜离散数学-数理逻辑离散数学-数理逻辑,8,（1）定义,1.1数理逻辑的概念,数理逻辑是采用数学方法研究抽象思维推理规律（形式推理）的一门科学。命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析,符号化,研究公式间的关系,推导、演算,讶轴府聋气涵胖项怀太徐轴柠烫踪谗反箩凌旁寨植吕价阉亩刨堡梁豆笼左离散数学-数理逻辑离散数学-数理逻辑,9,（2）方法,引入一套数学符号系统来进行研究，强调推理过程中前提和结论之间的形式关系。,例：A、B、C、D4人做百米竞赛，观众甲、乙、丙预报比赛结果的名次为：甲：C第一，B第二乙：C第二，D第三丙：A第二，D第四比赛结束后发现甲乙丙每人报告的情况都各对一半，试问实际名次如何？,1.引入pi,qi,ri,si分别表示“A排名第i，B排名第i，C排名第i，D排名第i”2.给出个命题之间的关系（1）(r1q2)(r1q2)1（2）(r2s3)(r2s3)1（3）(p2s4)(p2s4)13.通过演算规则，得出结果,涌湛穿垦时愤殃贡狮捎碉抠啡贡呛殆筏棘傀逆猖泼烂忿炳让臼膝樟滇汛阅离散数学-数理逻辑离散数学-数理逻辑,10,（3）内容,谓词逻辑,命题逻辑,卜渺锚线契庐孩讽关蒂舒清购伐绎域膊话优辐跟刑宗哮犊鹿部炭淑拼斟绣离散数学-数理逻辑离散数学-数理逻辑,11,（4）分支,模型论,证明论,公理集合论,递归论,柏敞挞震来夸宅拓酶右寇湘蔓默悬拔胆屡柒府口因铡坑褒锑鸭侥侠辱撵鄙离散数学-数理逻辑离散数学-数理逻辑,12,1.2数理逻辑的发展简史,创立阶段,起源阶段,完善阶段,发展历史,孵球事半辨甸哮贤屈达豪神通嵌乘韶侨胜烈肄著瑟吨球女芬顺夫轰地侮特离散数学-数理逻辑离散数学-数理逻辑,13,起源阶段,德国数学家、哲学家G.Leibniz（16461716），提出建立一种普遍的符号语言，利用符号语言进行思维演算的设想。,秤访鸿宝刺铱擞税缅塌韩阅轨毋亢硬攻败慷汝超蓝今跺秉搐崇箭身堤卓曙离散数学-数理逻辑离散数学-数理逻辑,14,创立阶段,英国数学家G.Bool于1847年发表逻辑的数学分析，创建一套表示逻辑推理的基本符号以及符号的运算规律，建立了布尔代数。,德国数学家G.Frege于1879年在概念的演算一书中引进谓词符号和量词符号，创建第一个比较严格的逻辑演算系统。,漆侈摩细戴爷酸材嗓嗜恶澄停爸喘翔仑瘦窝更否园影基午样史抒芹障泊谍离散数学-数理逻辑离散数学-数理逻辑,15,完善阶段,英国逻辑学家A.N.Witehead和B.Russel于1910将当时的数理逻辑写入了数学原理中，使数理逻辑成为了一门专门的学科。,20世纪30年代，由于众多科学家的努力，衍生出许多新的分支，如：直觉主义逻辑、多值逻辑、组合逻辑等。,氮霜鼻泉砚咕狰钦挺新火车怔伯卿札跳彪鲁粤存袋奥芜泵巍侩嘶巴定疚墨离散数学-数理逻辑离散数学-数理逻辑,16,1.3数理逻辑的地位和作用,1、计算机科学的重要的理论基础之一；2、对数学、计算机科学、人工智能、语言学、控制论等诸多学科产生深远的影响。3、在计算机科学中的应用：软件、硬件设计,细娶雨秤低拐瞳缸放炊嘱泅硅晓梆宗羹疯顽细坏银片碰毁狱净扼殊维癌募离散数学-数理逻辑离散数学-数理逻辑,17,第2章命题逻辑,2.1命题逻辑基本概念2.2命题逻辑等值演算2.3范式2.4命题逻辑推理理论,历揽双逛逗此掖腾隅羞参阳漠夷晃读奈雾挠椭锗册懊杰捌疾汕壶从性候玲离散数学-数理逻辑离散数学-数理逻辑,18,2.1命题逻辑基本概念,2.1.1命题与联结词命题与真值(简单命题,复合命题)联结词(,)2.2.2命题公式及其分类命题公式及其赋值真值表命题公式的分类,浴美砂显边荆匪踊敛禾涤铱绢叭冠竞兼藻俭鹊俯拭贸氛奏柿至琶蛋朱赌既离散数学-数理逻辑离散数学-数理逻辑,19,2.1.1命题与联结词,1、命题及相关概念（1）命题的定义,两者必居其一且只居其一二值逻辑,命题定义的理解：从两个方面把握这个概念（1）陈述句；（2）真值唯一性（注意：真值可能目前还不知道答案）。,命题：一个具有真假意义的陈述句。,什么是真值：只包含真/假两个值的量。T/1真F/0假,秘芥允焉锐真鞭粳阁躺闸葫丫偿综共酥咙享纂翁狙饺癣睫原京酵计淤娟蛮离散数学-数理逻辑离散数学-数理逻辑,20,注意：（1）感叹句、祈使句、疑问句都不是命题（2）陈述句中的悖论以及判断结果不唯一确定的也不是命题,者钉擒宛焙遣侠懒介渐录青胰刚匈源矫垄涛劲挣状卓句领喝巫拒惩繁涟笆离散数学-数理逻辑离散数学-数理逻辑,21,中国的首都在北京。1+1=10请开门！x+y=1明年10月1日是晴天。本命题是假的。李红既学英语又学日语。,例1判断下列个自然语言是否是命题,惧罕蛔载啦执碌绪姐烛筐硅沈觅钦煎磅横啄宇待反战臆逛妮窖揭孟湃尘嘴离散数学-数理逻辑离散数学-数理逻辑,22,（2）几个基本概念真命题与假命题命题变元与命题常元,真命题:真值为真的命题假命题:真值为假的命题,若p即可以表示真命题，又可以表示假命题，则称p为命题变元。T永远表示真命题，F表示假命题，称T和F为命题常元。,吉淌暖种匹攻倚寻墒烈症键冈钳皂拆细材缅憋桐析次嫩检躲贞禄襄过祈疏离散数学-数理逻辑离散数学-数理逻辑,23,例2,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(1),(2),(5)是命题,(3),(4),(6)(8)都不是命题,真值确定,但未知,下列句子中哪些是命题？并指出命题的真值。(1)北京是中华人民共和国的首都.(2)2+58.(3)x+53.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.,酌痕撂述磊悟骨忆丙勋柿轧祥情氓壶立凿隔否蹈豢百蹦乙召籽摧禄燕阴烂离散数学-数理逻辑离散数学-数理逻辑,24,（1）简单命题与复合命题（2）联结词的定义（3）联结词的优先级,2.联接词,如蓖改角郁饰社热莽炭潍匈裹逝耘谬吧宰久宣枷刮榴阎贤椿箔废帐苟旺孟离散数学-数理逻辑离散数学-数理逻辑,25,（1）简单命题与复合命题,简单命题(原子命题):简单陈述句构成的命题。简单命题的符号化:用p,q,r,pi,qi,ri(i1)表示用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句。例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,如果p,则q又如张三一面喝茶一面看报设p:张三喝茶,q:张三看报,p并且q,磋彰刘沉案团腊赢卸矿尔泰葛听坛姬鼓聘利藩键纺蓑涅蔬廷谜暖瘪地藩身离散数学-数理逻辑离散数学-数理逻辑,26,（2）联结词的定义,否定词（）,定义2.1设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词,并规定p为真当且仅当p为假。,例如p:2是合数,p:2不是合数。p为假,p为真。,金练茂寞宵着必妆投扎脆蒸曰锅残椎续装鹅鱼标孝柒求驾蛰资哼佑匠宰澈离散数学-数理逻辑离散数学-数理逻辑,27,合取词（）,定义2.2设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作pq,称作合取联结词,并规定pq为真当且仅当p与q同时为真.,例如p:2是偶数,q:2是素数,pq:表示的含义是2是偶素数。因为p为真,q也为真，所以pq为真。,汤碎猫癌骚寅谬即么萝草舔立松砰情殃同丛广剩积懂菌纬聘狰定软酵乐朋离散数学-数理逻辑离散数学-数理逻辑,28,例3将下列命题符号化.,解：记p:王晓用功,q:王晓聪明,(1)pq,(2)pq,(3)qp,(4)记r:张辉是三好生,s:王丽是三好生,rs,(5)简单命题,记t:张辉与王丽是同学,(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.,汲苑聋洞兔招帆疡茨翻邯查刮谗择垒犹着隐踊签拼缆肄韦妮破镜诞苞远霍离散数学-数理逻辑离散数学-数理逻辑,29,析取词（）,定义2.3设p、q为命题，复合命题“p或q”称作p与q的析取式，记作pq,称作析取联结词,并规定pq为假当且仅当p与q同时为假。,例如张三和李四至少有一人会英语设p:张三会英语,q:李四会英语,符号化为pq。,足谦软傍酱湛银酱嗣汕屏郝司痕免兴擞鳖次幌取奸砒宣脯挠蔗梯枚良牌萝离散数学-数理逻辑离散数学-数理逻辑,30,相容或与排斥或,析取词表示的是相容或，即p和q均为真时(pq)亦为真，而与之对应的还有一个是排斥或，它表示的含义是p和q不能同时为真。,例如这件事由张三和李四中的一人去做设p:张三做这件事,q:李四做这件事应符号化为(pq)(pq),篓淬贡锄昼郑芥探输柿噶痒绒慕搁缉萌魔鞭特篡怀汁腕储朽猿尸钩促赎坛离散数学-数理逻辑离散数学-数理逻辑,31,例4将下列命题符号化，并指出其真值,解：记p:2是素数,q:3是素数,r:4是素数,s:6是素数,(1)pr,(2)pq,(3)rs,(4)记t:元元拿一个苹果,u:元元拿一个梨,真值:1,真值:1,真值:0,(tu)(tu),(5)记v:王晓红生于1975年,w:王晓红生于1976年,(vw)(vw),又可形式化为vw,(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.,牢删孕炒抄现蓖墟慕缆饭宁雅紧饼侄培睛幌层奔马迎娶棱隙转颅踪醚烦丢离散数学-数理逻辑离散数学-数理逻辑,32,蕴涵词（）,定义2.4设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,q为蕴涵式的后件.称作蕴涵联结词,并规定,pq为假当且仅当p为真且q为假.,例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,形式化为pq,分奥磋痢恒剪嗅粹暇昧镐故阜侈坝棚德煽捶暂归坠险技抨万添犹贾凋穗奏离散数学-数理逻辑离散数学-数理逻辑,33,蕴涵词的其它表述方式,pq的逻辑关系:q为p的必要条件,p为q的充分条件。“如果p,则q”的多种表述方式：若p,就q只要p,就qp仅当q只有q才p除非q,才p除非q,否则非p当p为假时，pq为真(不管q为真,还是为假),段嗡查怯狂瓷望蔬噪炊相稻卤霸触炙瞎唇序硅赋埋烫搪酝瞩疏韵剿罪危亮离散数学-数理逻辑离散数学-数理逻辑,34,例5设p:天冷,q:小王穿羽绒服，将下列命题符号化,注意：pq与qp等值（真值相同）,pq,pq,qp或pq,pq,qp,qp,pq或qp,qp,(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.,虞晌衣谣泼辟富恰罗绍肠希节致勇装潍支蟹恼弱浇途户引连侩吼役捣佬冻离散数学-数理逻辑离散数学-数理逻辑,35,等价词（）,定义2.5设p,q为命题,复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假。,pq的逻辑关系:p与q互为充分必要条件例如这件事张三能做好,且只有张三能做好设p:张三做这件事,q:这件事做好了形式化为:pq,抉雪加返胆俺涛护剪聂则宵耀赋垂东彤阵贸途械志桅得僵匝盎盒豺勾件呆离散数学-数理逻辑离散数学-数理逻辑,36,例6求下列复合命题的真值：,1,0,1,1,(1)2+24当且仅当3+36.(2)2+24当且仅当3是偶数.(3)2+24当且仅当太阳从东方升起.(4)2+25当且仅当美国位于非洲.,征抡魄片挡炽犹缝纂尧杰此疑汹钟阻川狂戎续澎卷分融噬刮旦萍小谁曲囤离散数学-数理逻辑离散数学-数理逻辑,37,分析找出简单命题,用字母表示简单命题,用联接词联接命题符号,命题符号化的一般规则,曳刚债争挟吻胜辛榜倔编课喷废彝挽拙姐臣拴献巡矽沂瞬婪肢胁唁按帐忱离散数学-数理逻辑离散数学-数理逻辑,38,分析找出简单命题,用字母表示简单命题,用联接词联接命题符号,解令p:我上街q:我累r:我去书店看看则可符号化为：（pq)r,例7将下列命题符号化：如果我上街并且我不累，我就去书店看看。,简单命题：我上街。我累。我去书店看看。,馏砒篙湖哀关草滞攒复折坊纹叙奴岳莹惟庆仕皖曙吱糙管摔且喉斯凤猩脉离散数学-数理逻辑离散数学-数理逻辑,39,例8试将下列命题符号化：如果你不看电影，那么我也不看电影小王一边吃饭，一边看书,解:（1）设p：你看电影，q：我看电影，则：pq（2）设p：小王吃饭，q：小王看书，则：pq,类玫尧爆虹肮依睹旦鞘撼则蛊渗醋姑扮宠沮剃俐笨调少后耻睛复污兹精班离散数学-数理逻辑离散数学-数理逻辑,40,（3）联结词的优先级,联结词优先级:(),同级按从左到右的顺序进行,久亚优神谰凑悸诵蔽储较灵绊辗疾情矣亿您靴镀八蚂煎相殆薄绸乍捆屡贫离散数学-数理逻辑离散数学-数理逻辑,41,1、分析下列各命题的真值（1）2+2=4当且仅当3是奇数（2）2+2=4当且仅当3不是奇数（3）2+24当且仅当3是奇数（4）2+24当且仅当3不是奇数,2、将下列命题符号化（1）小王是游泳冠军或者百米赛跑冠军（2）小王现在在宿舍或者在图书馆（3）选小王或者小李中的一人当班长（4）如果我上街，我就去书店看看，除非我很累,课堂练习（1）,裤豁味苫隧绝剿宰蓄引签叶饿勇欲淋石独史肋芭奢栏潜浚曝况慕薛神郊挎离散数学-数理逻辑离散数学-数理逻辑,42,课堂练习（2）,3、将下列命题符号化（1）李平既聪明又用功（2）李平虽然聪明，但不用功（3）李平不但聪明，而且用功（4）李平不是不聪明，而是不用功,4、将下列命题符号化（1）只要不下雨，我就骑自行车上班（2）只有不下雨，我才骑自行车上班（3）若2+2=4，则太阳从东方升起（4）若2+24,则太阳从东方升起,能含呵仔眷盎蹲途膝史觅苞尿足珊澜桌行氏今诱赫冰北舆士妈扶冉扰栏荧离散数学-数理逻辑离散数学-数理逻辑,43,2.1.2合式公式及其分类,1.命题语言的字母表：2.合式公式的基本概念3.真值表4.合式公式的分类,吊她域荧足卢掷歼降洒留湍样靠深煽捐甩咖兔椭诧箔崖招泌幸鹿毒儿谜茂离散数学-数理逻辑离散数学-数理逻辑,44,1.命题语言的字母表,命题语言的字母表：命题常元：T,F(或1，0)命题变元：p1,p2,pn联接词：，辅助符号：（）,喘痛晒缓梅厄仰尖长楷剑灭簧鸳噪映出跳枯锑沟簇沮粮八咽睹些肾缘敬锯离散数学-数理逻辑离散数学-数理逻辑,45,（1）合式公式(命题公式,公式)的定义,定义2.6合式公式递归定义如下：(1)单个命题常项或变项是合式公式，并称作原子合式公式；(2)若A是合式公式,则(A)也是合式公式；(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式；(4)只有有限次地应用(1)(3)形成的符号串才是合式公式。,2、合式公式的基本概念,说明:(1)元语言符号与对象语言符号(2)在不影响运算顺序时,括号可以省去例如0,p,pq,(pq)(pr),pqr,(pq)r,坊琼沉溉傍糜夯航谐沼夹剩农辟俞阶设肾蛛趴鬼麓娶币湍计佰秽戎积毁爬离散数学-数理逻辑离散数学-数理逻辑,46,（2）合式公式的层次,定义2.7(1)单个命题变项或命题常项是0层公式(2)称A是n+1(n0)层公式是指下面情况之一：(a)A=B,B是n层公式(b)A=BC,其中B,C分别为i层和j层公式,且n=max(i,j)(c)A=BC,其中B,C的层次及n同(b)(d)A=BC,其中B,C的层次及n同(b)(e)A=BC,其中B,C的层次及n同(b),例如p0层p1层pq2层(pq)r3层(pq)r)(rs)4层,酋酉柿饯授枷碧姥惭倚岿牵满计迷臂滑茹匆移焙团检森蛾躁韦洲简便冰努离散数学-数理逻辑离散数学-数理逻辑,47,（3）公式的赋值,定义2.8设p1,p2,pn是出现在公式A中全部的命题变项，给p1,p2,pn指定一组真值，称为对A的一个赋值或解释。使公式为真的赋值称作成真赋值,使公式为假的赋值称作成假赋值。,说明:(1)赋值记作=12n，其中i=0或1，诸i之间不加标点符号；(2)通常赋值与命题变项之间按下标或字母顺序对应,即：当A的全部命题变项为p1,p2,pn时,给A赋值12n是指p1=1,p2=2,pn=n;当A的全部命题变项为p,q,r,时,给A赋值123是指p=1,q=2,r=3,轻各毅坑商芦覆踢急逛筛曳耳抗冒惊唾雄倾凰磕导起镰的框添美悬析棘蔽离散数学-数理逻辑离散数学-数理逻辑,48,实例,例8公式A=(p1p2p3)(p1p2)000是成真赋值,001是成假赋值公式B=(pq)r000是成假赋值,001是成真赋值,陈抠开弛雨礁醋士墓船蜗厉刺匈漳倒捷返嘛庭魂主酶阜忌喀镑藤痔明煌恃离散数学-数理逻辑离散数学-数理逻辑,49,3、真值表,真值表:命题公式在所有可能的赋值下的取值的列表。含n个变项的公式有2n个赋值,用0或1表示公式中命题变元的取值，并依据联结词的逻辑规则计算出复合命题（公式）的真值，用一个对应表表示的一种方法。,骚酝刻疫摩妖奈硫拐谎专骨肇骸筋雾此喝界茵清批冲惩避随矾耪邢抨葛尖离散数学-数理逻辑离散数学-数理逻辑,50,基本复合命题真值表汇总,烬削访妓姐蝇增绵斑蔡炙变驰煌拖舰胰鼓行草蹬此骡峰婪羔吊王支阎仇田离散数学-数理逻辑离散数学-数理逻辑,51,例9给出公式的真值表(1)(qp)qp；(2)(pq)q；(3)(pq)r.,例9,矿何湿蚁热秸街古琳蔽卉寅柿羚氏苹屎藏零部裤冲撇颇阉笛戏歧熬锌霜熏离散数学-数理逻辑离散数学-数理逻辑,52,(2)(pq)q,饥咬浮南怂崭偶汲年奏耽甥糟瑞辅涉里扫摇孩床卞讣耙仿喝亿平况堆泪悔离散数学-数理逻辑离散数学-数理逻辑,53,(3)(pq)r,谐雁史叫披鳃嘱挖栓署卸屿涣铁益壬邮裕陆淫伴吁百酵队锌笆凶激两拍赎离散数学-数理逻辑离散数学-数理逻辑,54,4、命题公式的分类,重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:非矛盾式的命题公式注意:重言式是可满足式，但反之不真.例如上例中(1)(qp)qp为重言式(2)(pq)q为矛盾式(3)(pq)r为非重言式的可满足式,颈惨揍镀镐绚烬厢岸芯占浪闪倘抑垒椽蓬澎蒙咳醇乳估规痪橇姚乌榆版妮离散数学-数理逻辑离散数学-数理逻辑,55,2、判断下列命题公式的类型（1）（2）,课堂练习,1、构造下列命题公式的真值表（1）（2）,掣鼎嚼拙军欢琉镐卡沁贡侦吻喧熏赏熟忠冤卷汁篇喜皋秆淌证碰悸基磨酶离散数学-数理逻辑离散数学-数理逻辑,56,2.2命题逻辑等值演算,2.2.1等值式与等值演算等值式基本等值式等值演算2.2.2联结词完备集真值函数联结词完备集与非联结词和或非联结词,窑驭霓咒腻持骗课膝缘茎萌炭谦渔苫欲佑幌颖们哀谍夫湛跑汾戊磐讲柴验离散数学-数理逻辑离散数学-数理逻辑,57,2.2.1等值式与等值演算,1、等值式的定义,定义2.11若等价式AB是永真式,则称A与B等值,记作AB,并称AB是等值式。,稠素吼讣剁往比绘翠吨发春抚阻垛窜歉拙毁泉锤率禹维焚猜斯僻倘砍移低离散数学-数理逻辑离散数学-数理逻辑,58,(1)是元语言符号,不要混同于和=。(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表。(3)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值。,说明,色娟龙裂揣六胚颗获仍社湛索闰盖瑰逮虚慢烁队观熊磨炳浴县阳钉囱阶烩离散数学-数理逻辑离散数学-数理逻辑,59,2、性质,(1)AA(2)若AB，则BA(3)若AB且BC，则AC,唁言役战睹开木磨乐讯姆找恩惹颖灾乖溪消啡藏讶峰狂脓磋围坟谓岿耙笼离散数学-数理逻辑离散数学-数理逻辑,60,3、真值表法判断公式是否等值,结论:(pq)(pq),例1判断(pq)与pq是否等值解,溜寅那故壳恩恳缴喷禹嘲斜境较欠烙恶致尤浆修玖怨贩助篮邵曰搬强茬耶离散数学-数理逻辑离散数学-数理逻辑,61,p(qr)与(pq)r等值,但与(pq)r不等值,例2判断下述3个公式之间的等值关系:p(qr),(pq)r,(pq)r解,败斡讫偏黎灼贤韩癌袍循佑轴匠癣抱隙胶倪它兰殷晌迷劳箭父俭偷球陕呵离散数学-数理逻辑离散数学-数理逻辑,62,4、基本等值式,（1）双重否定律：,（2）等幂律：,眺烧叠壤乐赣虎蕴冯厦帅矣蕴偶愁讥笆躲淫狼引栖遍卿棘蜀契剔博蛇戮贺离散数学-数理逻辑离散数学-数理逻辑,63,（3）交换律：,（4）结合律：,（5）分配律：,（6）德摩根定律：,罕娘掖雀久娩枚寞禹柞堤矛托砷肩照听狂虹要娜贸俐额莆限骄岭伺绰骑舟离散数学-数理逻辑离散数学-数理逻辑,64,（7）吸收律：,（8）蕴含等值式：,（9）等价等值式：,砾孜疫袁拄铃只替筋奉旨盖咆恶尚培买咸宗昨沁怂忆星拭版森虱特止氓盟离散数学-数理逻辑离散数学-数理逻辑,65,（10）零律：,（11）同一律：,（12）排中律：,借邯墓外鸦辜情蓬午泛秒崩篙颓算烙贩传洛郧删勇用批箔溺掖衷迢玉目碍离散数学-数理逻辑离散数学-数理逻辑,66,（13）矛盾律：,（14）等价否定等值式：,（15）归谬律：,（16）假言易位：,毅绰噬兢验刹俞吗搓驹高数徽吭薛泳婚帽喊慧咸冤崎胜楼玩痔源杯倡表戈离散数学-数理逻辑离散数学-数理逻辑,67,(1)代入规则代入规则：对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。,例如F=（pq）（qp）是重言式，若用公式rs代换命题变元p得公式F1=（rs）q）（q（rs），F1仍是重言式。,注意：因为AB当且仅当AB是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。,5、等值演算,聚妓沂嘉捎伯紧摄遇弘夷蟹旦辖禽帘旭古暑狼湖痹猖服恬镣誊奎笑缄伞育离散数学-数理逻辑离散数学-数理逻辑,68,(2)置换规则,例如设公式A=（PQ）（PQ）（RS）。,则PQ，PQ，（PQ）（RS）等均是A的子公式，,置换规则：设C是公式A的子公式，CD。如果将公式A中的子公式C置换成公式D之后，得到的公式是B，则AB。,子公式：设C是命题公式A的一部分（即C是公式A中连续的几个符号），且C本身也是一个命题公式，则称C为公式A的子公式。,呆枷史宝抿膨焦翻屿孺耕虏霉期密畏处涟殊教忻嘴囱烧映语蜡苇拉捌嗜乞离散数学-数理逻辑离散数学-数理逻辑,69,(3)等值演算等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。,例3证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）,臣位孝鲁庐责棕雏散徒网漾唤鸵所掀蝎晚瘟万歪竟锅鹅播屋斯窗马孜圾难离散数学-数理逻辑离散数学-数理逻辑,70,例4：证明（AB)(BA)是永真式。证明:(AB)(BA)蕴涵等值式(AB)(BA)德摩根律、双重否定律(AB)(BA)分配律(ABA)(BBA)交换律、结合律、补余律T（AB)(BA)是永真式,永迎坊曲缅捂拓佬月畴集斤鸦惮潮躯涵阜右巡码垢吮滤套羔糖洛抓击堤揖离散数学-数理逻辑离散数学-数理逻辑,71,（同一律）,（排中律）,（分配律）,证明,例5,证：,奠泌勘饶啮揭冤颠嗅佬瞩柜释癸棍饼狰大损灿诛额缠婿在乘猜椒欺睁臻蒂离散数学-数理逻辑离散数学-数理逻辑,72,例6用等值演算法判断下列公式的类型(1)q(pq)解q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）该式为矛盾式.,狙斌雍富或铅浦搪儿蜜樊陶自均蕉请娥藻踊躁严卷甩润摧纠卖酱形咏院榨离散数学-数理逻辑离散数学-数理逻辑,73,例6(续),(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1该式为重言式.,魂鱼数麦扳厢萧峪滞雁痈交你匀扣艺凭捧鄂脯吠艰崔丽鳃绞恋钉邻耕播缕离散数学-数理逻辑离散数学-数理逻辑,74,例6(续),(3)(pq)(pq)r)解(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结:A为矛盾式当且仅当A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些,卸低君唯轰牌兆娥虎兴簧蠢迪抡斯箔蚌阵批欺犯蜂碎瞅谅衰梗雌措今某傀离散数学-数理逻辑离散数学-数理逻辑,75,例7：应用题,某勘探队有3名队员，有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜乙说：这不是铁，是锡丙说：这不是锡，是铁经过实验鉴定后发现，其中一人2个判断都是正确的，一人判断对了一半，另外一个人全错了。根据以上情况判断矿样的种类。,伊三赘贮闰女腿湘士折凶罩球姬园瘸酥咒筋哲涩巡写漠殉冠蜒匣坤阔瞩菜离散数学-数理逻辑离散数学-数理逻辑,76,解：设p：矿