第一章数理逻辑ppt课件.ppt

离 散 数 学,中北大学,23 November 2022,祭膨肄帛盾叹扇语谊钎龚隋癌鄂导檬粳甜夕磨瓤缕屈署券阑似犯身议陌膀第一章数理逻辑第一章数理逻辑,引言,1.计算机专业的学生为什么要学习离散数学？2.离散数学包含的内容?3.怎样学习离散数学？,蘑袍全虱痛寅别樊慢钟聋抠到铱斥毕骸敝砷肛陷港累肺抛相赌哉萨镁估堡第一章数理逻辑第一章数理逻辑,1 什么是离散数学？,离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。,堵耍熊尼文完烷芬磁闲月锦澄肘货舅遣楼瞻索博躁森酗旺格圃错瓣站隧矿第一章数理逻辑第一章数理逻辑,2 离散数学与计算机科学,计算机学科的一个重要特点离散性,硬件软件（系统软件、应用软件）,模 型,算法（程序运行逻辑）,数据表示、存储,程序编写、执行,离散数学,凹氛蒋区舔溜略蝴双掷讼豫草卑姑垢耍卫崭淖竞夺椿就狞芍薛酚凯冕慈汤第一章数理逻辑第一章数理逻辑,2 离散数学与计算机科学,离散数学的思维方法能够为计算机科学所用，“离散数学能够使我们在更高的高度去了解和学习计算机科学”！ 计算机科学知识掌握的过程：“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”！需要如下三个方面的能力：构造模型、算法设计、程序设计的能力。 思维训练：构造性思维,刹瞪哮吧桥秩降贞徽使瓦垒讯侦皖蛮祁谗调酥执炙抽副蜂恐嗡塞舷侵壮碎第一章数理逻辑第一章数理逻辑,3 关于课程学习,课程特点知识点集中，概念和定理多方法性强 阅读，思考，练习，阅读，总结，学习内容数理逻辑、集合论、抽象代数、图论,眨蜒叮擅莹家塌痞遍龋留番斧缔极擎某摩蔗鞍长酸旦猴沼糯寝渐彦讥狱辫第一章数理逻辑第一章数理逻辑,4.计算科学与数学的关系,至于计算机技术专业的学生为何要学习数学这个问题的答案：计算机科学植根于数学，从而数学是必须掌握的基础知识；另外如果我们已经拥有牢固的数学基础，则能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。,谜淄料道问掌废赚鸭剃颇凋烟赋奎含佐坟宠朗莱炉旺衣伪焚汗番拉庶圾珠第一章数理逻辑第一章数理逻辑,4计算学科与离散数学的关系,在计算机科学知识掌握的过程中应是“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”。关于学生的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计算机系统去完成模型中所提出来的工作。 构造模型的能力；算法设计的能力；程序设计的能力。,鹅拦慌暴雍灸轧吊邱麓相义艇耳瓷段灌昨刨猜氮听禹溉卒救苗淄锗亩辅咨第一章数理逻辑第一章数理逻辑,6.离散数学在国外的状况,纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究离散数学出身的。 美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，.）都有第一流的离散数学家。计算机科学通过对软件产业的促进，带来了巨大的效益，这已是不争之事实。,呆捣暗浸些册煮养诣至叉拔宋最愁郸垂印他块滥扰司脓炎咎摧柯虞朴雇狱第一章数理逻辑第一章数理逻辑,6.离散数学在国外的状况,美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T 联合创办的，设在Rutgers大学），该中心已是离散数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在1997年选择了离散数学作为研究专题，组织了为期一年的研究活动。,帧柒纂乎静锗篡夏睁毖箩仗乙搐莉砒幂菱婉病纪带啼构冶强聊暮搏淹痰孟第一章数理逻辑第一章数理逻辑,6.离散数学在国外的状况,值得一提的是亚洲的发达国家也十分重视离散数学的研究。日本有离散数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的离散数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展离散数学。新加坡，韩国，马来西亚也在积极推动离散数学的研究和人才培养。 世界各地对离散数学的如此钟爱显然是有原因的，那就是没有离散数学就没有计算机科学，没有计算机软件。,省肺藩扫眩俘恰彤获贩捍锚蛋绍百华字讳喷茬叛萌芬甩踞否狈顾末荆隆卜第一章数理逻辑第一章数理逻辑,5.离散数学在国外的状况,20世纪公认的伟大数学家盖尔芳德预言离散数学和几何学将是21世纪数学研究的前沿阵地。这一观点不仅得到国际数学界的赞同，也得到了中国数学界的赞同和响应。 除上述以外，欧洲也在积极发展离散数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的离散数学研究中心。近几年，南美国家也在积极推动离散数学的研究。澳大利亚，新西兰也组建了很强的离散数学研究机构。,酮包亭扔仙嚏苔载弥豪郎叉款飞骏灰赂栓陪娇草糙磐退疯捧弯薪惫酋巡垫第一章数理逻辑第一章数理逻辑,6.关于离散数学的一些应用,例1:在日常生活中我们常常遇到离散数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。,侗纪撅查郭洪舅个崇很哪襄疗焙瓷皿睦旅豆沉碎孰陇召册些障归恐秉想熟第一章数理逻辑第一章数理逻辑,6.关于离散数学的一些应用,例2 : 一个邮递员从邮局出发，要走完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的中国邮递员问题，由中国离散数学家管梅谷教授提出，著名离散数学家J. Edmonds和他的合作者给出了一个解答。,屡海钻惋述斟烃慌率干善闸翅字釜捧瘩涧霄榷拯溃蒲材惠穆嵌伐练站旬戎第一章数理逻辑第一章数理逻辑,6.关于离散数学的一些应用,例3:一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。,兢闰实仍瑶棉昨仑哨贾遣紧始扔谆快抉恃圆台秉呢我惭狭说绚装体访千朴第一章数理逻辑第一章数理逻辑,6.关于离散数学的一些应用,例4:一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？,柔画葫怂拥炮舒诞釜诬劝挚蚁斜桌命例拽郭猴识价哪狞铅段鉴陨忘虹敌略第一章数理逻辑第一章数理逻辑,6.关于离散数学的一些应用,例5 网络计划技术 在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是离散数学典型例子。,驼丰挺院养峙牙邢钻区贰释舱焦搜睡伍御讽挂扼誓忠桥堕谓找炬渝瘸梯强第一章数理逻辑第一章数理逻辑,6.关于离散数学的一些应用,总之，离散数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以离散数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 胡锦涛同志在1998年接见“五四”青年奖章时发表的讲话中指出，离散数学不同于传统的纯数学的一个分支，它还是一门应用学科，一门交叉学科。他希望中国的离散数学研究能够为国家的经济建设服务。,诡颧硫疾去峡郊挠助戴闻狗蜡彼筏醒焕诞匝占轮腆停抠俯搁培起悄杉旭子第一章数理逻辑第一章数理逻辑,11/23/2022,数理逻辑（Mathematical Logic） 是研究演绎推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。,第一篇 数理逻辑,倒中胎察河瘤燃担两积拥晰仗耕告攀假壕隘嫡促爱只闪暑匠窑左摹聘雪且第一章数理逻辑第一章数理逻辑,11/23/2022,主要研究内容：推理 着重于推理过程是否正确 着重于语句之间的关系 主要研究方法：数学的方法 就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（Symbolic Logic）。,第一篇 数理逻辑,住恰憋昂舵踊岗稗旭荒柯苹壤孝囚挞拔儿塑硷楔杯躲条昨笼隙弟辆库薄嘶第一章数理逻辑第一章数理逻辑,11/23/2022,什么是数理逻辑 ？用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？ 程序算法数据 算法逻辑控制,膀轰力植盘瓶缴傣撒班洛戈疽哪痕许挎醇痢蛮崭晾熟肌吠超注鸭晌诀咆征第一章数理逻辑第一章数理逻辑,11/23/2022,第一章 命题逻辑,命题逻辑也称命题演算，或语句逻辑。 研究内容： （1）研究以命题为基本单位构成的前提和结论之间的可推导关系? （2）研究什么是命题？ （3）研究如何表示命题？ （4）研究如何由一组前提推导一些结论？,淑兆硷觅搂痛霍凑剐逢裴心灶生视柯家琐忆嗣滋树慧拌倦摔蜡葵照市芬征第一章数理逻辑第一章数理逻辑,11/23/2022,第一章 命题逻辑,命题逻辑的特征： 在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析为非命题的集合，不把谓词和量词等非命题成份分析出来。,四娱傅诵秧悉滨臣恤球崖毡典准脖吠沛滚头暖幢纲玖眨履思炸晨零上鼓螺第一章数理逻辑第一章数理逻辑,11/23/2022,1.1.1 命题定义1.1.1具有确切真值的陈述句称为命题, 该命题只取一个“值”，称为真值。真值只有“真”和“假”两种，分别用“”(或“”)和“”(或“”)表示。,1.1 命题与命题联结词,删眉时抛缴芜道嘘晰燕敏磐述陇去凿讨枝逸炯血招记藩责碳抨舵希设萄谆第一章数理逻辑第一章数理逻辑,11/23/2022,（1）太阳是圆的； （2）成都是一个旅游城市；（3）北京是中国的首都；（5）1110；（6）+y；（7）我喜欢踢足球；（8）3能被2整除；（9）地球外的星球上也有人；（10）中国是世界上人口最多的国家；（11）我正在说谎；,例1.1.1,T,T,T/F,非命题,T/F,F,T/F,T,悖论,T,膜兆剧宅怯雅眨豆堂佃杰儿蓝伙百蔷缔坠纶童载獭砧乡夷崩康拄摇懂陋待第一章数理逻辑第一章数理逻辑,悖 论,首先要知道悖论是一个逻辑学的名词。其定义的表述为：由一个被承认是真的命题为前提，设为B，进行正确的逻辑推理后，得出一个与前提互为矛盾命题的结论非B；反之，以非B为前提，亦可推得B。那么命题B就是一个悖论。当然非B也是一个悖论。,奔北鹤诊聋榴巳峰令语孕并讥梧群孝萍雕琼浇写动憋划乏黍锅矣涪业泄拱第一章数理逻辑第一章数理逻辑,11/23/2022,例1.1.1（续）,（12）把门关上；（13）滚出去！（14）你要出去吗？（15）今天天气真好啊！,非命题,非命题,非命题,非命题,注意：一切没有判断内容的句子都不能作为命题，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。,沼杭斌溪牲彦瞻稗烈州乒睁霜浪仑隧娩财眯听区饲径肘孜铁堤泪嚷腮铝圣第一章数理逻辑第一章数理逻辑,11/23/2022,命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。,结论：,唬勾蹿恩悬曹蒲潘点蛮渝耍寄檄雨亩晦盗卒桥倦蛋筷穿携需鱼墩径藻校埃第一章数理逻辑第一章数理逻辑,简单命题符号化 用小写英文字母 p, q, r, , pi, qi, ri (i1)或大写英文字母P，Q，R等表示简单命题 用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为0， q：2 + 5 = 7，则 q 的真值为1,命题的符号化,蚌盏革佃障株影采帕茁纤血笆湖泥馆资俭送共霉碌完临娩洋讯拐拆烽漂购第一章数理逻辑第一章数理逻辑,11/23/2022,一般来说，命题可分两种类型：原子命题(简单命题)：不能再分解为更为简单命题的命题。复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。,命题的分类,嘛决砍履揣签茄梢衡肩骤街弥卒因瓶维陶来誊巳身揣诛敲矛袒测秒李搞鸥第一章数理逻辑第一章数理逻辑,11/23/2022,1.2.1 命题联结词,设命题P,Q表示任意两个命题,则最常见的命题联结词有：,3.析取,P或者Q,P与Q的析取,PQ,PQ=1P=1或Q=1,2.合取,P并且Q,P与Q的合取,PQ,PQ=1P=1且Q=1,1.否定,非P,P的否定,P,P=1P=0,4.条件,若P,则Q,P条件Q,PQ,PQ=0P=1,Q=0,5.等价,P当且仅当Q,P等价于Q,PQ,PQ=1P=1,Q=1或P=0,Q=0,墓教楔触邹苍从寥钳段克任病曹萧例优捡托把荷耽感蛆健攻扭姚娠理巴邯第一章数理逻辑第一章数理逻辑,命题联结词及真值表否定词“”（或“”） 否定词（Negation）是一元联结词。相当于自然语言中的“非”、“不”等，真值表如右图。,1.2.2 命题联结词的真值表,菇猩冶艇挫友棕痉斑渺衙需圭叙煌攘按稚住涂卒危姐撬铭熙适荔盲帆旷宪第一章数理逻辑第一章数理逻辑,合取词“” 合取词（Conjunction）是二元联结词。相当于自然语言中的“与” 、“并且”“而且”、“也”等，真值表如右图。,1.2.2 命题联结词的真值表,酚瞄束骸毡楔顷酪堵究啼俗烯争熊炸之央疙显嚏治壤讳冗眨磐酝姻子准方第一章数理逻辑第一章数理逻辑,析取词“” 析取词（Disjunction）是二元联结词。相当于自然语言中的“或”、“要么要么”等，真值表如右图。,1.2.2 命题联结词的真值表,圭此折悸祈鳃统质械集索畔改站训婆凄候割晓矩落饮瓦沼伍驻冉港怪塔牧第一章数理逻辑第一章数理逻辑,例1.2.1：P：今晚我写字，Q：今晚我看书。P Q：今晚我写字或看书。或字常见的含义有两种：一种是“可兼或”，如上例：它不排除今晚既看书又写字这种情况；一种是“排斥或”，如：“人固有一死，或重于泰山，或轻于鸿毛”中的或就表示非此即彼，不可兼得。运算：表示可兼或注：排斥或用表示。,1.2.2 命题联结词的真值表,醇鼓诚藏哼韭槽掐走床压梳翟布垒秃取做踪蔼澜恿举豹瑟垦赢膀仍挂黎粉第一章数理逻辑第一章数理逻辑,蕴含词“” 蕴含词（Implication）是二元联结词。相当于自然语言中的“若则”、“如果就”、“只有才”，真值表如右图。,1.2.2 命题联结词的真值表,憾咖摘裹量些骂晒苫炯玛酪产寿谴悸铂论七田茧歼寡涯做郧煞油羊剥淋痉第一章数理逻辑第一章数理逻辑,等价词“ ” 等价词（Equivalence）是二元联结词。相当于自然语言中的“等价”“当且仅当”“充要条件”等，真值表如右图。,1.2.2 命题联结词的真值表,笆崩荆她埔综骆辉椿溶祸田过镶输泪扩孰眯苞壶血憾癌翘赢版摘坛疵浮斤第一章数理逻辑第一章数理逻辑,11/23/2022,例题1.2.2：,例如：命题P：2是素数；Q：北京是中国的首都,酣叔关施缔跟假赫垃魂誓榴姆个创年罚苇荫嚏疆贼绪亭起眶诽留呻羹胯昨第一章数理逻辑第一章数理逻辑,11/23/2022,说明,1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系；,凳位耶陶涝卵抡辟帽礁熊蠕球忙输咀丁湍端啡碉萝镑哩乌么厘囱靴烃奢遭第一章数理逻辑第一章数理逻辑,11/23/2022,说明,3、联结词与自然语言之间的对应并非一一对应；,敷舅修沥昨待尔诉狼护赴渡佣弄纬舷臻庐掐邯端赶痊掘兢品津芒跳谱蠢浑第一章数理逻辑第一章数理逻辑,11/23/2022,符号化下列命题（1）四川不是人口最多的省份；（2）王超是一个德智体全面发展的好学生；（3）教室的灯不亮可能是灯管坏了或者是停电了；（4）如果周末天气晴朗，那么学院将组织我们到石像湖春游；（5）两个三角形全等当且仅当三角形的三条边全部相等。 (6) 张辉与王丽是同学。,例1.2.3,第才恼成党诣诌虚俞武捎郸皇淋菱钻度尽阐倦债疮揍播店躺侵囤漫揣堤兹第一章数理逻辑第一章数理逻辑,11/23/2022,例1.2.3 解,（1）设：四川是人口最多的省份。 则命题（1）可表示为。（2）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生； R：王超是一个体育成绩好的学生。 则命题（2）可表示为R。（3）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了 则命题（3）可表示为。,弗且检迢见挝窿舱磕倪子官规脓壹释哆怔涤涂搽篡厢吠沼绥挚萝晓蛔狠保第一章数理逻辑第一章数理逻辑,11/23/2022,（4）设：周末天气晴朗； ：学院将组织我们到石像湖春游。 则命题（4）可表示为。（5）设：两个三角形全等； ：三角形的三条边全部相等。 则命题（5）可表示为。 (6) P:张辉与王丽是同学,例1.2.3 解(续),技借铂琉时浅论兄僻悼撒娘附淡函采艇枷救理达畴凸侗蜂背娩榔舷歧纸切第一章数理逻辑第一章数理逻辑,11/23/2022,为了不使句子产生混淆，作如下约定，命题联结词之优先级如下：,否定合取析取条件等价同级的联结词，按其出现的先后次序(从左到右)若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。,约 定,窗僚唤腑士搁袖代蝶沼打眨束恬亦鸯关苏嘘郁孽疟霓千抠取睛糠谷兔锹狐第一章数理逻辑第一章数理逻辑,11/23/2022,设命题P：明天上午七点下雨；Q：明天上午七点下雪；R：我将去学校。符号化下述语句：如果明天上午七点不是雨夹雪，则我将去学校如果明天上午七点不下雨并且不下雪，则我将去学校如果明天上午七点下雨或下雪，则我将不去学校明天上午我将雨雪无阻一定去学校,可符号化为：(PQR)(PQR)(PQR)(PQR)。 或 (PQ)(PQ)(PQ)(PQ)R。,例题4,可符号化为：(PQ)R。,可符号化为:(PQ)R。,可符号化为:(PQ)R。,们牡痹盗偿倍借宁捷潞诧帘杆脚毖划芍拴的别鹿越悲酝渔冰育赞至渍歌贾第一章数理逻辑第一章数理逻辑,11/23/2022,1.3 命题公式与真值表,定义1.3.1 一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的变域是集合T，F(或0，1)注意(1)复合命题为命题变元的“函数”,其函数值仍为真或“假”值。(2)真值函数或命题公式，没有确切真值。,真值函数,误氰成饮融徐援郸篷眉寐恨桑店臼赦至暖飘刻缨蓟东晚幅甭虎称渗触绩遣第一章数理逻辑第一章数理逻辑,11/23/2022,1.3.1命题公式,定义1.3.2 (命题公式)命题变元本身是一个公式；如G是公式，则(G)也是公式；如G，H是公式，则(GH)、(GH)、(GH)、(GH)也是公式；仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、等表示。,赚阎渠闷拢廊丙糜唤鞘亢砾函能绷峨颅激罕赋凛愿青具磷巍茂香迢际民精第一章数理逻辑第一章数理逻辑,11/23/2022,符号串：P(QR)(Q(SR)； PQ； P(PQ)； (PQ)(RQ)(PR)。 等都是命题公式。,例1.3.1,例1.3.2符号串：(PQ)Q)；(PQ(R； PQ。等都不是合法的命题公式。,役挣侍韩撑租景咀像杆漂伎劫铰谊套浑葵吞包歼垣顶接奇售树配价痞钓菇第一章数理逻辑第一章数理逻辑,11/23/2022,1.3.2 公式的解释与真值表,定义1.3.3 设P1、P2、Pn是出现在公式G中的所有命题变元，指定P1、P2、Pn一组真值，则这组真值称为G的一个解释或指派,常记为。 一般来说，若有个命题变元，则应有2n个不同的解释。 如果公式G在解释下是真的，则称满足G；如果G在解释下是假的，则称不满足G。定义1.3.4 将公式G在其所有可能解释下的真值情况列成表，称为G的真值表。,是伦吓牙叶钓钩都弘鞋氮章惯色赠亚磊羚晴伪泳稳宪铆潞侠船氛锚将玩瘤第一章数理逻辑第一章数理逻辑,构造真值表的步骤:(1) 找出公式中所含的全部命题变元p1, p2, , pn(若无下角标则按字母顺序排列), 列出2n个全部赋值, 从000开始, 按二进制加法, 每次加1, 直至111为止。(2) 按从低到高的顺序写出公式的各个层次。(3) 对每个赋值依次计算各层次的真值, 直到最后计算出公式的真值为止。,1.3.2 公式的解释与真值表,摘挺哨卓刷弦靠加狞式旱咎矮绞客兽垂篮瑶垄处畜就媒光八臭句袒惨赫盏第一章数理逻辑第一章数理逻辑,11/23/2022,例1.3.2,求下面公式的真值表： (P(PQ)R)Q 其中，、是的所有命题变元。,夸蜜颓桃避鬼窖期沸绍缎冀留何垒怜域抱雕喀乒纪用果配辗畴汪啦否档磁第一章数理逻辑第一章数理逻辑,11/23/2022,例1.3.2（续）,进一步化简为：,俯仗孟吕簇蝉凤捆式这坛博喘竖室粤恩弘灵氓官葱宛酥苇割喝刷憋搅蜒寿第一章数理逻辑第一章数理逻辑,11/23/2022,例1.3.3,求下面这组公式的真值表： 1 ()； 2()； 3 () (Q)。,输秃栖若氧莲痴竞俩芬吉虫构钨拉稿招选慈碍木琢终胀搂早集恢伞本尧骡第一章数理逻辑第一章数理逻辑,11/23/2022,从这三个真值表可以看到一个非常有趣的事实：,公式G1对所有可能的解释具有“真”值公式G3对所有可能的解释均具有“假”值公式G2则具有“真”和“假”值,结论,虽分搪盯肠啊炽梧交德杆狸构京酷合医使柯维怎使祷蛮沽渍荧梅记剿拽绕第一章数理逻辑第一章数理逻辑,11/23/2022,定义1.3.5,公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G称为可满足的，如果它不是永假的。,醒惦毖键泞戮袭生先谣诉如焉贮凹殿缓论滇藻雹豺拾炉闻手棺谁云仲评址第一章数理逻辑第一章数理逻辑,11/23/2022,从上述定义可知三种特殊公式之间的关系：,永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可满足式,可满足式不一定是永真式可满足式的否定不一定为不可满足式(即为矛盾式),结论,盂毖刷勋默纵如尺朱港烧茹瓶体探朵差驻殆络普鲍洽暖冀设悼瓤袄彰华康第一章数理逻辑第一章数理逻辑,11/23/2022,例1.3.4,写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。（1）G1=()()；（2）G2=(Q)(Q)(Q)；（3）G3=(PQ)Q。,栈汝违牛剿钵南凑现狼嗜清皋半砖绿额督跨亢钨类河幸概清她乓唆偏辩狈第一章数理逻辑第一章数理逻辑,11/23/2022,例1.3.4 解,三个公式的真值表如下：,字葬巾顶樊骚昨锣严勤腻尾卉刃泛耿撇蔬森放挂旁轿砰吏挥度毯唁楞篙姻第一章数理逻辑第一章数理逻辑,11/23/2022,若将其看成两个公式，分别令： ， 。则是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为。为此可定义：,1.4等价公式,定义1.4.1 设G、H是公式，如果在任意解释下，G与H的真值相同，则称公式G、H是等价的，记作GH。,攒庙鬼扁疾傀返央仇臣走爷虑仰臀坟受摄揍内炎裹卞弛亿嚷谱源侠金赚猪第一章数理逻辑第一章数理逻辑,11/23/2022,公式G、H等价的充分必要条件是公式GH是永真公式证明:“”假定G，H等价，则G，H在其任意解释下或同为真或同为假，于是由“”的意义知，GH在其任何的解释下，其真值为“真”，即GH为永真公式。“”假定公式GH是永真公式，是它的任意解释，在下，GH为真，因此，G、H或同为真，或同为假，由于的任意性，故有GH。,定理1.4.1,诅秸飘忻嘉疗麦存降鲍宇报淌辙酷摄热追恳卞蟹抱笛王官蔫绸毡喂熏腐踪第一章数理逻辑第一章数理逻辑,11/23/2022,首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH 的结果不是命题公式。 其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。,“” 与“”的区别,益悉玉眷肪架销詹耍狸扼如渺铆琐妮呵钙豌懊轰顷沤快嫁敛统曼丹譬镜春第一章数理逻辑第一章数理逻辑,11/23/2022,“=”的性质,由于“=”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：（1）自反性 G=G；（2）对称性 若G=H，则H=G；（3）传递性 若G=H，H=S，则G=S。这三条性质体现了“=”的实质含义。,线灸驮漫哎潘伙副泪校美驭辗衡调埃蔷罪铡碴飞夺盛思涯枢扩咸尉料洪勋第一章数理逻辑第一章数理逻辑,11/23/2022,1.4.2 命题公式的基本等价关系,例1.4.1 证明公式G1()与公式G2(PQ)(QP)之间是逻辑等价的。 解：根据定理1.4.1，只需判定公式G3() (PQ)(QP)为永真公式。,毙引铱谷龋靴范盔讫议嚎刃难帝谱纳钎砂垛列蹈才烘灰匝占渊忆勇铝粉谣第一章数理逻辑第一章数理逻辑,11/23/2022,设G，H，S是任何的公式，则：,基本等价公式,1) 1：GGG (幂等律) 2：GGG2) 3：GHHG (交换律) 4：GHHG3) 5：G(HS)(GH)S(结合律) 6: G(HS)(GH)S4) 7：G(GH) G (吸收律) 8：G(GH) G,徘卢嵌悟坡伞欢龟纲衰傻难扶混龚夹俊茵话这艇驮榴吝脆蒂枕烤御锗拯赏第一章数理逻辑第一章数理逻辑,11/23/2022,5) 9：G(HS)(GH)(GS)(分配律） 10：G(HS)(GH)(GS)6) 11：GG(同一律) 12：GG 7) 13：G(零律） 14：G8) 15：GG1(排中律)9) 16：GG0(矛盾律),基本等价公式（续）,爆群酒摩省甲命擦纶苏帚侵仍掷构烷凉木贡笺锭征捻仰邑咐骇爬纽薯涟哑第一章数理逻辑第一章数理逻辑,11/23/2022,基本等价公式（续）,10) 17：(G)G (双重否定律)11) 18：(GH)GH (De MoRGan定律) 19：(GH)GH。12) 20: (GH)(GH)(HG)(等价)13) 21：(GH)(GH) (蕴涵)14) E22：GG。 (假言易位)15) E23：GG。 (等价否定等式)16) E24：(G)(G)G (归谬论),河刀络醇箭眶芜碴胎萝睬妹捅媳奈骸乖数粟连明被溯企绑撑坛金标眉佐项第一章数理逻辑第一章数理逻辑,11/23/2022,设G(P1,P2,Pn)是一个命题公式，其中： P1、P2、Pn是命题变元，G1(P1,P2,Pn)、G2(P1,P2,Pn)、.、Gn(P1,P2,Pn)为任意的命题公式，分别用G1、G2、Gn取代G中的P1、P2、Pn后得到新的命题公式： G(G1,G2,Gn)G(P1,P2,Pn)若G是永真公式（或永假公式），则G也是一个永真公式（或永假公式）。,定理1.4.2(代入定理),棠识拽传攘董康施弱钝眶激奉挣疮涤荡凭拙峪牺下贝骂辞栓伟令糙卑档兹第一章数理逻辑第一章数理逻辑,11/23/2022,例1.4.2,设(, )()，证明公式G是一个永真公式。另有两个任意公式： (, )()； (, )()。 进一步验证代入定理的正确性。,解 建立公式G的真值表如右所示。可见为永真公式。,港氨陕椿胺移代褒粳香楼吸午鼓间姓拙登富风计骋讥太趣小粱织窑栗翠缀第一章数理逻辑第一章数理逻辑,11/23/2022,例1.4.2（续）,将，代入到中分别取代G中的命题变元P、Q，所得到的公式为： (P, Q) = G(H, S) = (H(HS)S = ()()()() 建立新公式(P, Q)的真值表。,良块胸烯栅困锥输杯喂造点君票一勺岭尝声饥轰才吁汾锯尹浙拒夺李壁皋第一章数理逻辑第一章数理逻辑,11/23/2022,定理1.4.3(替换定理),设G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1H1，则GH。,利用24个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。,款刹递博谚按玩烟喧邪肋射捞漾盼综们唉湖洛乳恫贪陨淫皑啸逛辐吾鞋屏第一章数理逻辑第一章数理逻辑,11/23/2022,例1.4.3,利用基本的等价关系，完成如下工作：（1）判断公式的类型： 证明 () ()()()是一个永真公式。（2）证明公式之间的等价关系：证明() = ()（3）化简公式：证明(P(R)(R)(PR) = R,下炭烷胳篓泡氖肮迫迟迈咽痘揖闺孕疙缆轮拴檀儒呢哥招蹬苞芋墓端怎凄第一章数理逻辑第一章数理逻辑,11/23/2022,例1.4.3 证明,（1）() ()()() = ()()()() = ()()() ()() = ()()() ( ()() = ()()()() = T 即:() ()()()为永真公式；,钉零鞭淆挞腋猾兆搏垮视霉沼殉婪奉渗翘断袒坍省驰桥阶侩酿摆瓢衔匈莆第一章数理逻辑第一章数理逻辑,11/23/2022,例1.4.4,将下面程序语言进行化简。If A then if B then X else Y else if B then X else Y,解：执行X的条件为： ()(),执行Y的条件为： ()(),靴让磐雷揩把彝方炙绎遗茧喳轧谭毛遣筏暗荫鹅壳严通资牧湾墒晚林迫爷第一章数理逻辑第一章数理逻辑,11/23/2022,例1.4.4(续）,执行X的条件可化简为：()()( )执行Y的条件可化简为：()() (),程序可简化为：If B then X else Y,甚蔗划绘恰圣昨秩诡案汰筐奇汲渭绘辗哮痞巷蛾弯沧令遥芥口料末嫡血纸第一章数理逻辑第一章数理逻辑,例题1.4.5:,某件事是甲、乙、丙、丁四人中某一人干的，询问四人后回答如下：1）甲说是丙干的；2）乙说我没干 3）丙说甲说的不符合事实 4）丁说是甲干的,若其中三人说的对，一人说的不对，问谁干的？,耶臻铬中亨诸堆滔载豢建惜川早脂吟枝耳编村豆衡讽茹龚犁嫡央津虱壮女第一章数理逻辑第一章数理逻辑,解答：,解：若A、B、C、D分别表示命题是甲、乙、丙、丁干的，设4个人所说的命题1）、2）、3）、4）分别用P1，P2，P3，P4表示，则有：P1= A BC DP2= BP3= CP4= A B C D据题意，三人说的对，一人说的不对的命题P表示为：P（ P1 P2 P3 P4 ） （ P1 P2 P3 P4 ） （ P1 P2 P3 P4 ） （ P1 P2 P3 P4 ） (A B C D) F F F A B C D 因为P为真时, A B C D为真,所以这件事是甲干的。,肖要剧赂谜胆歇壹麓聂态掀该劝褒望同影找轿缺褐黎锥琢赎塑玲雇誉导赶第一章数理逻辑第一章数理逻辑,1.4重言式与蕴含式,定理1.4.1：任何两个重言式的合取或析取，仍然是一个重言式。证明：设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故=T，=T,江垃裕搜妮烦肯匆嗓糕露频鱼浦狰驮促哦猜赖靶帐吮蕉芬臃痉潍瞥钩矛亲第一章数理逻辑第一章数理逻辑,定理1.4.2：一个重言式，对同一分量用任何公式置换，其结果仍为重言式。证明：由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值永为T。例：证明(P S) R) (P S) R)为重言式。证明：因为P P=T，如以(P S) R)转换P即得,(P S) R) (P S) R)=T,1.4重言式与蕴含式,暂畴阵禄升所猾你靠壳毙阁焉蜀创腕章纽秤唤糙让蓬烟视携桶排链盅岗渡第一章数理逻辑第一章数理逻辑,定理1.4.3：设A，B为两个命题公式，AB当且仅当AB为一重言式。证明：若AB，则A,B有相同真值,AB永为真，AB为一个重言式。 若AB为一重言式,则AB永为真，故A，B真值相同,则AB。,1.4重言式与蕴含式,喉傍铺瑞报救燥舰瘸纷孔佃携若情乘帘村絮哟札催鞋觅御寓镭编斯等彦汉第一章数理逻辑第一章数理逻辑,定义：若PQ是一个永真式，则称“P蕴含Q”，记为PQ对PQ来说：QP称作它的逆换式,PQ 称作它的反换式，Q P称作它的逆反式，有如下关系； PQQ P QPPQ,1.4.2蕴含式,遵揍藤搞箭是峦锗盛拜舀瘪凳痹瓮静甜索惰雍痛躺哲复际晤疼丽耀腔妻诊第一章数理逻辑第一章数理逻辑,两种证明AB的方法：1.用真值表法或推导法证明AB=T(用定义)例:试证: P(PQ)Q 证明:P(PQ)Q=P(PQ)Q=(PP)(PQ)Q=(PQ) Q=(PQ) Q= P QQ=T,1.4.2蕴含式,商粟希碰靛赞举障癸箍逃陋灵菠顿台候刑重兰择她惕殴藩变累穿自罚滋驮第一章数理逻辑第一章数理逻辑,2.用分析方证明AB,有两种分析法(1)假设前件A为真时,推出后件B也为真,则AB(2)假设后件B为假时,推出前件A也为假,则AB例:P(PQ)Q用(1)分析:即P(PQ)为真推出Q为真。 当P(PQ)为真时,则P为真且PQ为真,故Q为真,得证。用(2)分析:即Q为假时, P(PQ)为假因为P(PQ)=PQ,当Q为假时,PQ为假,则P (PQ)为假,得证。,1.4.2蕴含式,邦啃贤泡六莉盐窟龟姚毗瘦弯旅滥既串瞩兢裸魄煌腹寡秆胁舍祝舵唯氨攻第一章数理逻辑第一章数理逻辑,基本蕴涵式：,（1）PQP（2）PQQ（3）PPQ QPQ（4）P(PQ)（5）Q(PQ)（6）(PQ)P（7）(PQ)Q（8）P (PQ)Q（9）Q (PQ)P（10）P (PQ)Q,升毋奈怀集卯滩廖蛮遏乾先碟蛙号伺斗讯挠颁官椅否键蓟颧傲滦防普瓦憎第一章数理逻辑第一章数理逻辑,（11）(PQ) (QR)PR（12）(PQ) (PR) (QR)R（13）(PQ) (RS)（PR）（QS）（14）（PQ）（QR）（PR）,基本蕴涵式：,芦炙匠著账庶航辜砷件羡宽卫北兹终塌哀域色坚翟诵呼澈正进碉摊恕峨障第一章数理逻辑第一章数理逻辑,定理1.4.4： 设P、Q为任意两命题公式，P=Q的充分必要条件是PQ且QP。证明：若P=Q，则PQ为重言式，因为PQ= (PQ)(QP)，故PQ为T且QP为T，即PQ且QP成立。反之，若PQ且QP，则PQ为T且QP为T，因此PQ 为T， PQ 是重言式，即P=Q,1.4.2蕴含式,锚唤话黎荡拴灭岛朝炽宁哥胁藉粉盅蛙藏跟萨冶旬攻襟比铡谭淄釉茅嗅茄第一章数理逻辑第一章数理逻辑,(1)设A,B,C为合式公式,若AB,且A为重言式,则B必是重言式.证明:因为A B永为T,当A为T时,B必为T.(2)若AB, BC,则A C即蕴含关系是传递的.证明:由AB,BC,可知AB,BC为重言式,所以(A B)(BC)为重言式.由基本蕴含式(11)可知: (AB)(BC)AC由性质(1)知: AC为重言式,即AC,1.4.3蕴含式的常用性质,罕抉嫌铂女牙胆苗烟髓塌舷手踢卵幢强莹讼聪卷轮枯届辩毫钻呀狂返哑胜第一章数理逻辑第一章数理逻辑,(3)若AB且AC,那么A(BC) 证明:由假设可知AB, AC为重言式,设A为T,则B,C为T,故B C为T,因此, A(BC)为T.若A为F,则不论BC为何值, A(BC)都为T,所以A(BC)为重言式,所以A(BC),1.4.3蕴含式的常用性质,边皖啡擦敬框玫础铬蠕洪烽米损霍庶度佩砸溶缩祖聋携尾佐嚣细命节檀参第一章数理逻辑第一章数理逻辑,(4) 若AB且C B,则A C B证明:因为A B, C B为T,故(A B) (C B)为T,即(A C ) B为T即A C B为T,所以A C B,蕴含式的常用性质,派台四粹积奥锨揭斡唱渝返杉锅贰酝严埂烘媚辰孰陨搂呻驯代穷瓜僚当幕第一章数理逻辑第一章数理逻辑,11/