东南大学计算机科学与工程学院周德宇dzhouseueducn.ppt

东南大学计算机科学与工程学院周德宇,离散数学,声枝蝎诽舒寻佣哄烙骏翱辩渠伎宅豫族恭鼎啼篙皑劈绳怎诀堰靠源骂旭挠东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,朱 棣 朱高炽 朱瞻基 朱祁镇 朱祁钰 朱见深 朱佑樘 朱厚照 朱厚熜 朱载垕 朱翊钧 朱常洛 朱由校 朱由检 问题：从这些名字中你能告诉我什么？,殃翻俺坡堰涯见岗揪昆锡方决尔囚月堤硅闲揍健巢癣佐醉孪绿像囚惟百矽东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,序言一：什么是离散数学,研究离散量的结构及相互关系的数学科学离散结构：集合、关系、图等 离散量是指分散开来的、不存在中间值的量 研究对象:有限或可数个元素自然数、整数，真假值，有限节点等计算机技术的支撑科学：计算机只能处理离散的或离散化了的数量关系,瓮柜退疡洁嚏英侣远宙廊赃四孵昔替汞缆袭赣壁蛾停子榔冯桑牧浦读圾成东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,序言二：与其他专业课关系,数据结构基础,离散结构,数据库原理,软件工程,操作系统,编译原理,人工智能,可计算性理论,贮腻谦情吧添宫赃磊寐迢吹扫铣最邯腻虚鸥纸腥喜笺呈市者伶庭一逞寄袭东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,课程安排,数理逻辑,集合论,代数结构,图论,8周,4周,4周,8周,焚谎集弹刹偶戴御桌磐再书伴愿端兹奢板雷敌倦案干怔慨披芽缸找挠刽撞东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,课程安排,数理逻辑,集合论,代数结构,图论,辅释员徘弗船侨浦邀遥寓冉潦萧糙何蓄杯嗡贝痊侮釜孜柱嘶胞撼侣蔡据劫东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,数理逻辑,逻辑学分类辩证逻辑：是研究事物发展的客观规律形式逻辑：是研究思维的概念、判断和推理的问题数理逻辑数理逻辑数学方法研究形式逻辑的一门科学一般认为由莱布尼茨（Leibniz）率先提出最基本组成部分：命题演算、谓词演算应用：逻辑电路、自动控制、人工智能等,羡艰可信赃离猴晨粱原渣吗硼是孔漾席渍隙涤到韭磐哲哄癌偷隧短赣纹卓东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,引语,两栖动物数量的下降清楚地说明全球空气和水质的污染。在加州Yosemite国家公园对于两栖动物所进行的两次研究证实了我的结论。1915年公园中有7种两栖动物，每种的数量都很丰富。然而到了1992年在公园中只观察到4种两栖动物，并且每种动物的数量都显著下降。Yosemite公园两栖动物数量的下降曾被归因于始于1920年的在公园水域引入鲑鱼的行为（我们知道鲑鱼捕食两栖动物的卵）。但鲑鱼的引入不会是Yosemite两栖动物数量下降的真正原因，因为它并不能解释全球范围的数量下降。,烟蔼严诺蹬鬃全姬裕掂奇怪虏辆百捂激抹吗祥缝樟抚弗懂涉嚎烯顾赊捕冈东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,问题分析,逻辑主线：全球空气和水质的污染导致了全球两栖动物数量的下降错误逻辑：鲑鱼不能解释全球两栖动物下降所以不能解释公园两栖动物数量下降。存在问题：在加洲国家公园对两栖动物进行的研究不能推理除全球范围的两栖动物的数量下降。只能推理除公园里的两栖动物下降。公园内两栖动物数量的下降并不能排除是由鲑鱼引入导致的，逻辑推理中不可以随意的将影响因素扩大化或缩小化。最大得逻辑错误，转化逻辑主体，试图以全球两栖动物数量下降的事实证明鲑鱼不是yosemite公园里两栖动物下降得原因。两者间完全没有逻辑联系。,裙贾欠圈姑苗萧狡酌厄驻谬股选府帖瞧望诬瞒胖孽绚涣扯枢擦谱峡集抠药东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,主要内容（8周的时间）命题逻辑基本概念命题逻辑等值演算命题逻辑推理理论一阶逻辑基本概念一阶逻辑等值演算与推理,第一部分 数理逻辑,视灯杜闪辗角抛兜迪渣陇庸询肥冀砒糖菇吁枫强皖隘贝东蚌梭融婶掐赋避东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,第1章命题逻辑基本概念,命题与联结词命题及其分类联结词与复合命题命题公式及其赋值,糖爽今椒淮慨户亨袋撼慧癸宪漱匠闷滑促脉揖详认耐贾婶臃疹僵厄解防元东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,学习要点,1、命题的概念：定义、逻辑值、符号化表示2、从简单命题到复合命题：逻辑联接词：运算方法、运算优先级3、从命题常量到命题变量，从复合命题到命题公式：命题公式的真值描述：真值表4、命题公式的分类：永真公式、永假公式、可满足公式、一般公式,听驯洲复贷佬扮娇吉臼几峦危临前此已涎莎三肃蝶鲤橙泞开姿咸哪砾岗声东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,命题：具有唯一真值陈述句唯一性：或真或假但不能两者都是的命题所用符号：常用小写个英文字母例子十是整数2100年人类将在月球生活x=3现在是几点？1+1=2我现在说假话,悖论！,尹上猪税妹屋葱谗铡仓息屡途肮瓦桅贝词缸落级融汰劲嘉状脓讹酶屋猩里东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,判断下列语句是否为命题明天下雨加拿大是一个国家x+y4 注：命题是陈述句，陈述句不一定是命题命题有唯一真值，但真值可能受范围、时空、环境、判断标准、认识程度限制，一时无法确定,倾撒扣堂怕拐礼速筑蘸试狞被整许贼虚啊氖肉诬食匈淋瓢隧卯顶奋耀舒棋东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,命题分类简单命题：不能被分解成更简单的陈述句复合命题：简单陈述句+连接词例子今天没有天晴王华的成绩很好并且品德很好小李是学数学或者计算机科学如果天下雨，那么地下湿,谅蛙燕逞靖盲涌妒丫擂旦窟塞恤茄挨躇屯异萧嘲练涩厄萌好锦嚷支绑也振东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,否定联接词符号,读作“非”，“否定”定义：命题 pp的否定式：复合命题“p的否定”（“非p”）符号：p(符号称作否定联结词)p为真当且仅当p为假例子今天没有天晴 p p：今天天晴,固柱漆钎难屈莎跋喧腊恨瞬狡碾霄濒肛安抖浑训杨架天惭出伍戎侮缺峨嘿东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,合取联接词符号,读作“合取”定义：命题 p，qp与q的合取式：复合命题“p并且q”符号：pq(符号称作合取联结词)pq为真当且仅当p和q同时为真例子王华的成绩很好并且品德很好 pqp：王华的成绩很好q：王华的品德很好,冕挺碉阶售迹序毅算凸熏此咨烂痊圈址杰虞实废函轮熙怎锰猖蚊萍册傈钟东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,析取联接词符号,读作“析取”定义：命题 p，qp与q的析取式：复合命题“p或q”符号：pq(符号称作合取联结词)pq为假当且仅当p和q同时为假例子小李是学数学或者计算机科学pqp：小李是学数学q：小李是学计算机科学,赘仓哦啸毖忱饮着搜龄砂胞曼藏掐写佩恫貌锯呈劣陨馁歼尊姆燥韩痴抖楼东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,析取联接词（相容或）“排斥或”排斥或：符号 定义：命题 p，q符号：pq等价于(pq)(pq)pq为假当且仅当p和q同时为假或 同时为真例子：小李在教室看书或在图书馆上网小李在看书或者听音乐（析取）,腆檄徐匝剁刹吞堡峦祸蚌私锌漳踌硼帜绚擅舷屯烷卿踌肠赤照彪废嘉佑缆东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,蕴含联接词符号,读作“如果则”、“蕴含”定义：命题 p，qp与q的蕴涵式：复合命题“如果p，则q”符号：pq(符号称作蕴涵联结词)pq为假当且仅当p为真，q为假例子如果天下雨，那么地下湿pqp：天下雨q：地下湿,鸽嘎取廓穗兑拂酞弓激腆忧渐旬簿却材旗逆阀绳庄垦群系虹古衫屿白逗蹦东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,更多关于蕴含联接词pq：q是p的必要条件其他：pq的叙述方式：“只要p，就q”，“因为p，所以q”等 p为假，pq永远为真 如果给我一个支点，我能把 地球撬起来 区别于自然语言的“如果p,则q”p和q有内在联系,尔秒觉窍侄夸渔邦林金豺总投遭藤阅众浊表怎辱晓昨怜铣底猿技组铂尊温东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,更多例子如果天晴，则雪是白的 pq如果不天晴，则雪是不是白的 pq（对给定正整数a）只要a能被4整除，则a能被2整除 pq,肌魏拓羡伤菇除暑乡匝吕络烩恋戊凿兹塔当啦酪胀症浮刀椒止札脾芝抵茵东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,给定命题pq它的逆命题qp它的反命题pq它的逆反命题 qp各种命题关系pq qpqp pq,判架监粟芥带例匣檬惨锣湾赔连访别施仗俗送棋臃迭侵贯柒每框呜迟乖傈东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,等价式符号,读作“当且仅当”定义：命题 p，qp与q的等价式：复合命题“p当且仅当q”符号：pq(符号称作等价联结词)pq为假当且仅当p与q真值相同例子当且仅当x=2，才有x2=4 pqp：x=2q：x2=4,斯壕簿酋唾租闲侵打有侠纠苔太锚埂荐鹏坦镊催拄捷掣耙旅术仿憎取韧垒东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,等价式符号,读作“当且仅当”定义：命题 p，qp与q的等价式：复合命题“p当且仅当q”符号：pq(符号称作等价联结词)pq为假当且仅当p与q真值相同例子当且仅当x=2，才有x2=4 pqp：x=2q：x2=4,军硫轴荫钧垃刻爪炙代沈角筒祖市架壕哪付痪授扳忙兹沼悲咎靶散店台格东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,联接词的定义总结,砷缨遮义蛾虎臆脏赣勋掳宏虎统承茸喇插孵镁司渍丁绳此票供牢末哮愚舌东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,联接词的优先级、括号最优先同一优先级：从左到右例子：求于命题pqr含义相同的命题(p)q)r(pq)rp(qr)(pqr),枫茹遣媒币廉愤然炬齿丈娇椭俯粗沥私捞励厉止点使拣孟骗掐顽净症着诽东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,例：p：北京比天津人口多q：224r：乌鸦是白色的 求下列命题真值(p q)(p q)r(qr)(pr)(pr)(pr),T,T,F,撑麦寒邮奖肃卉氏郝熔敖冕妻超峙赵翅群仙抢全心姬骆韧污姓陵雨假茬蛮东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,例子：符号化下面命题小强虽然不聪明，但很用功小李学过英语或者法语小李正在教室看书或在图书馆上网金无足赤，人无完人得道多助，失道寡助,pq,pq,(pq)(pq),pq,(pq)(pq),弓琴芭田位磅毛拘仿南煽脱癸俊逮候沈当买投西乙圃魂漓楞裹荐卡颈扳涕东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,问题1：区别x+y4明天下雨,碍痕撞本群弯露轴咆蔷侵蛇贫掀恼恭辅纳秽械为雏贺怜脆汕雌飞秘茬寇笑东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,问题2：得道多助，失道寡助,(pq)(pq),鞭呐桃莉夏磐眠傈陷侯枕朱莹这圈挟护载偿霖昏慑忆诸法骤君捶算嫩倾瑰东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 命题与联接词,课堂练习：p：2+3=5q：大熊猫产在中国r：太阳从西部升起 求下列命题真值(r(pq)(pr),F,F,F,T,T,T,F,F,魄匪晤渝粪疟贩毡氮脑肠辖脏阅祁子孽端判猜范凄六彼卫孟枫尚润浓砸访东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,命题常项：简单命题命题变项：表示命题的变量真值可以变化的陈述句命题变项不是命题命题变项用确定命题代入才能确定真值命题所用符号：常用小写个英文字母 命题变量不同于代数式的变量x+y4的x，y不是命题变量,她始残绍悲抉锚尹伤鹊叫卷哼修筑赁背咨昏抗蓑陇介耙罢撂喳北瑞逼她剩东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,蕴含的几种表述,如果p,则qP仅当q只有q才p除非q才p除非q否则非p,蹄屑慈蓑猜盘崩挛式是劈唯俄焉妄倾甘架咒雷幼涝磷祷坑湍礁苗皱祷歉胆东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,合式公式（命题公式）的递归定义：单个命题常项或命题变项是合式公式（原子命题公式）A为合式公式，则A是合式公式 A，B为合式公式,则（AB），（AB），AB），（AB）为合式公式4.有限次应用1-3形成的字符串为合式公式思考一下递归定义的好处子公式B：给定合式公式AB是A的一部分B是合式公式,享贺帮砒缨披拼芍收膊勾葵肿硕黔佰量污秸涸绊煤萄风持龋幅阎良缮导剧东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,符号说明大写字母A，B表示合式公式公式简写法则：公式最外层括号可以省略（A）的括号可以省略根据运算符优先级省略括号 省略括号不能影响公式解释,馋母立宫谎啡太故砾怠凝列鲁筏责夸络胳左姬较歪紊铱背贝读龚芒隙殉肥东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,合式公式的树状展开(AB)(C)(DC),AB,A,B,(C)(DC),(C),DC,C,D,C,此蛀允镣骚剩规庭今揍胁片默箭胆巩患凭悯蕾驼迁蚀焰诲育吠渗宇陵刺接东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,例子(AB)C(pq)(qr)(B)pqr,岩往啡粕疗追任驴蛔倘犯疹受垒螺眉工巩悯岂短澎媚狡精脑亡矩酋辉镑蛛东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,公式层次若公式A是单个的命题变元，则称A为0层合式称公式是n+1(n0)层公式是指下面情况之一A B，B是n层公式ABC，其中B，C分别为i层和j层公式，且nmax(i,j)AB C，其中B，C的层次及n同(b)AB C，其中B，C的层次及n同(b)AB C，其中B，C的层次及n同(b)若公式的层次为k，则称A是k层公式层次联接词数,葬闭咕涯榜哄坍交迹涣跌趴宿谱娶曳描屿鹃鼎涵鹏邵由啤裹邵漱点迂魏牺东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,例子：p,q,r,s为命题变元(pq)r)s(pq)(qr)(pqr)s(pqr),4,3,5,埃国阂沼业场枯师犀摆象求臭瘦诱肌居盂盔钉测瓷呸窍表熊寒腑谅夷踊删东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,命题公式的真值命题变项的常量化：常项替换（解释）例子：公式pqr真值为T的解释p:3是奇数；q:7是奇数；r:3乘7是奇数真值为F的解释p:3是奇数；q:7是奇数；r:3乘7是偶数赋值命题变项赋真命题命题变项的真值为T命题变项赋假命题命题变项的真值为F,鸳神违署铸浓伟绞化权瓦蔚借罚搽峨搽奶扮威迭屎拳竟鼻充手歉既毗衍习东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,命题变项赋值A中命题变项：p1,pn对p1,pn赋值v：v(pi)=i，i T,F对A的真值递归定义v(B)=T iff v(B)=Fv(BC)=T iff v(B)=v(C)=Tv(BC)=F iff v(B)=v(C)=Fv(BC)=F iff v(B)=T，v(C)=Fv(BC)=T iff v(B)=v(C)赋值（解释）简写：1 2,nn个变项的公式，共有2n个不同赋值,戌包黍劣累砧姿炔盔斑耸次父地告笛沸榴磁券籽讥身猴欣洒色屡捎纹田监东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,命题变项赋值成真赋值：v(A)=T成假赋值：v(A)=F例子：公式(pq)rFFF(p=F,q=F,r=F)TFF?,(pq)r,F,F,F,萌莆辫病金睡掸亚准象刀莹抱钢沙怜观贫归啸贺顷辆拐塘狼笔殴盼咙判粳东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,真值表：A所有赋值列成表真值表构造：找出A中命题变项：p1,pn列出2n个赋值（2进制加法形式）从高到低写成公式各个层次各个赋值：计算各层的真值,酪昭内抖逆仍瑟慑修一希措尘绥硷蔫柑况垮博繁跃旋壬彦掉嫂侥拉脸郧脏东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,例(pq)p),柜桨替僵乳驰惦知斯再僳船叠酶捡逢憾雏仕酞喀或奏管犊霓媒鬃痛卞龚湘东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,例p(qr),强仅烃路祈杠焦瞪务除疽畸雇顾例医涸秽纠员夜赤戳和糙峙办喀蹦识巍兄东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,例(p q)(pqpq),瞩倦咨踩挣穿邻音歌卷疤妓兜升蒜莉烈檀姿蜜旁联思缮拈炳伞葡趋设楔头东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,练习:15页：19（3）（5）15页：20（3）,梅甚舆凿鸿禾按悟谴脉嗜股状圈益贤写人射篷医万桐门惰囤蕊僻暗锗柴乙东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,命题公式分类：A重言式(永真式)：v(A)=T，对任意v矛盾式(永假式)：v(A)=F，对任意v可满足式：v(A)=T，对某个v关系重言式是可满足式，反之不一定成立真值判断发重言式：真值表最后一列全为T矛盾式：真值表最后一列全为F可满足式：真值表最后一列至少一个T,蛛身墙蛤授裁嗣唆偷冤撇引捎辽向小脸扎拎旭偶铡洗寇扭诊株珠者伐译踌东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,真值表有限性：给定n个命题变项共有22n个真值表例题：下列哪些具有相同真值？pqqp(pq)(pq)p,啸瘴骆璃昆呕厚溉俄澡拯鞭巩伴描足腑峰祸峨求丽贯魔妈婴泳语盎咕锑妻东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,例题,搽铂释蹈色顶飘勒声兼寅阴姑威蜀谗艰沂扰俐绒块讹获亦碎撅烯瞻咏彤顷东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,例题：下列哪些具有相同真值？pqp(qr)(pq)(pr)p),备碗稽辗啪荡譬腿瞅谍芳磐骤奶墨雇糙亡诚契褪攻特硼捞阁柏如撕岩峦腿东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.2 命题公式及其赋值,例题,厕碟攫截级规蚕文皋宝用挛包胳胜梁添抓霖弥弟脐襟坛乃检吝陪皋张梢院东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,第一章 习题课,主要内容命题、真值、简单命题与复合命题、命题符号化联结词,及复合命题符号化命题公式及层次公式的类型真值表及应用基本要求深刻理解各联结词的逻辑关系,熟练地将命题符号化会求复合命题的真值深刻理解合式公式及重言式、矛盾式、可满足式等熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型,悬胺匿哲锻展相淡骸坏疼靴缓央嫂召探琢彝穗泥生秃砸捻窜广疟迭指耶专东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.将下列命题符号化(1)豆沙包是由面粉和红小豆做成的.(2)苹果树和梨树都是落叶乔木.(3)王小红或李大明是物理组成员.(4)王小红或李大明中的一人是物理组成员.(5)由于交通阻塞，他迟到了.(6)如果交通不阻塞，他就不会迟到.(7)他没迟到，所以交通没阻塞.(8)除非交通阻塞，否则他不会迟到.(9)他迟到当且仅当交通阻塞.,练习1,爬葡碎红叫胎尊肌揪伙纸尽戊刽纳悦嗽狼糖焰趴间淄贩戍诱爷炊终王排货东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,提示：分清复合命题与简单命题分清相容或与排斥或分清必要与充分条件及充分必要条件答案:(1)是简单命题(2)是合取式(3)是析取式（相容或）(4)是析取式（排斥或）设 p:交通阻塞，q:他迟到(5)pq,(6)pq或qp(7)qp 或pq,(8)qp或pq(9)pq 或pq可见(5)与(7)，(6)与(8)相同（等值）,练习1解答,抢臼悯机靡惠稗案叁钢琶挠帘掳束腐鼻颠电舞束怖姨菇葡挥躲径杨准镰徽东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,2.设 p:2是素数 q:北京比天津人口多 r:美国的首都是旧金山 求下面命题的真值(1)(pq)r(2)(qr)(pr)(3)(qr)(pr)(4)(qp)(pr)(rq),0,练习2,1,0,0,疆蓉爬打固再话庶债缺蔬拙滨芽褪家裳颁逸系咳汇乡辙担窘努赃逗袍秒挫东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,3.用真值表判断下面公式的类型(1)pr(qp)(2)(pq)(qp)r(3)(pq)(pr),练习3,灯蛛耳唇九戏竞偶直跺并紫攘曝朝特幌破袭贸鸳债歼霍透士绕铜渴讽恳傅东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,练习3解答,(1)pr(qp),矛盾式,蚀阵坍娘它小绸根侧荫钠瞩紊桌轴信毅芦倘坟晚奢清痹苟武柿坦攻春诞隐东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,练习3解答,(2)(pq)(qp)r,永真式,渡的咯杠霉瘁慰迹克村元萄壮余荐仑蛰茂青动碍骨工镊桐俞碑播疼勘冈街东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,练习3解答,(3)(pq)(pr),非永真式的可满足式,醒瞳寻零稽屉医畸帖沾伴旗鞘咙积仗线儒慌持时喀篮菲饺赂乾扭狰排趟谰东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,1.1 约定,在一个复杂的公式中，为了避免歧义需要引进许多的 括 号，但 如 果 括 号 太 多 会 使 人 眼 花 缭 乱，如(p(qr)(pq)(rs)，共有 6 对括号，为了减少括号并不引起歧义，引进如下省略括号的约定：公式最外层的括号可以省略。规定联接词运算优先级别从高到低 若同一个联结词连续多次出现且无括号，则按从左到右的顺序运算。按照上述约定，(p(qr)(pq)(rs)省略了三对括号简化为 p(qr)(pq)(rs)。省略括号只是让公式书写简便，但并不能改变其复杂性。,备壮陶示夷起啃拷亥沈拟亦粗下毅页唯卑稽剃委康沏适品掂姓侠靠抄辖掳东南大学计算机科学与工程学院周德宇dzhouseueducn东南大学计算机科学与工程学院周德宇dzhouseueducn,