《命题逻辑》课件.ppt

《《命题逻辑》课件.ppt》由会员分享，可在线阅读，更多相关《《命题逻辑》课件.ppt（35页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学周勇周勇 （小）（小）要求要求 基本要求基本要求 考核考核1.考勤：按大学生手册执行（缺席三次取消考考勤：按大学生手册执行（缺席三次取消考试资格，迟到试资格，迟到10分钟不能进入教室）分钟不能进入教室）2.作业独立完成作业独立完成3.期中考试（？）期中考试（？）4.考教分离考教分离5.周三交作业（按自然班，班长负责），下一周三交作业（按自然班，班长负责），下一个周三返还个周三返还1.平时成绩平时成绩30%：作业：作业+考勤考勤2.期末成绩期末成绩70%离散数学离散数学是数学的几个分支的总称，研究基于是数学的几个分支的总称，研究基于离散空间而不是连续的数学结构。离散空间而不是连续

2、的数学结构。与微积分和分析等连续数学相对的。与微积分和分析等连续数学相对的。数理逻辑，集合论，代数系统，图论数理逻辑，集合论，代数系统，图论信息论，理论计算机科学，运筹学，概率论，信息论，理论计算机科学，运筹学，概率论，博弈论博弈论4 4/34/34 什么是数理逻辑？什么是数理逻辑？数理逻辑是用数学方法研究思维规律的一门学科。所数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指谓数学方法是指:用一套数学的符号系统来描述和处用一套数学的符号系统来描述和处理思维的形式与规律。因此，理思维的形式与规律。因此，数理逻辑又称为符号逻数理逻辑又称为符号逻辑。辑。数理逻辑的创始人数理逻辑的创始人-

3、莱布尼茨莱布尼茨(Leibniz,Gottfried Wilhelm)1646.7.1-1716.11.14 5/34德国数学家、物理学家、哲学家等，德国数学家、物理学家、哲学家等，一个举世罕见的科学天才。研究领域涉一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法及到逻辑学、数学、力学、地质学、法学、历史学、语言学、生物学以及外交、学、历史学、语言学、生物学以及外交、神学等诸多方面神学等诸多方面.出生于德国东部莱比锡的一个书香之出生于德国东部莱比锡的一个书香之家，父亲是莱比锡大学的道德哲学教授，家，父亲是莱比锡大学的道德哲学教授，母亲出生在一个教授家庭。莱布尼兹的母亲出生在

4、一个教授家庭。莱布尼兹的父亲在他年仅父亲在他年仅6 6岁时便去世了，给他留岁时便去世了，给他留下了丰富的藏书。下了丰富的藏书。1515岁时，进了莱比锡大学学习法律，一进校便跟上了岁时，进了莱比锡大学学习法律，一进校便跟上了大学二年级标准的人文学科的课程，还广泛阅读了培大学二年级标准的人文学科的课程，还广泛阅读了培根、开普勒、伽利略等人的著作，并对他们的著述进根、开普勒、伽利略等人的著作，并对他们的著述进行深入的思考和评价。在听了教授讲授欧几里德的行深入的思考和评价。在听了教授讲授欧几里德的几何原本几何原本的课程后，莱布尼兹对数学产生了浓厚的课程后，莱布尼兹对数学产生了浓厚的兴趣。的兴趣。171

5、7岁时他在耶拿大学学习了短时期的数学，岁时他在耶拿大学学习了短时期的数学，并获得了哲学硕士学位并获得了哲学硕士学位 。1919岁设计出世界第一台乘法器，被认为是现代机器数岁设计出世界第一台乘法器，被认为是现代机器数学的先驱者。学的先驱者。Leibniz(1646Leibniz(164617161716年年)之梦：有一天所有的知识，之梦：有一天所有的知识，包括精神和无形的真理，能够通过通用的代数演算放包括精神和无形的真理，能够通过通用的代数演算放入一个单一的演绎系统。入一个单一的演绎系统。16931693年，发现了机械能的能量守恒定律。年，发现了机械能的能量守恒定律。与牛顿并称为微积分的创立者。

6、与牛顿并称为微积分的创立者。系统阐述了二进制记数法，并把它和中国的八卦联系系统阐述了二进制记数法，并把它和中国的八卦联系起来。起来。6/34几何系统（公理）7/341.过相异两点，能作且只能作一直线（直线公理）。2.线段(有限直线)可以任意地延长。3.以任一点为圆心、任意长为半径，可作一圆(圆公理)。4.凡是直角都相等(角公理)。5.两直线被第三条直线所截，如果同侧两内角和小于两个直角，则两直线作延长时在此侧会相交。1.跟同一个量相等的两个量相等；即若 a=c 且 b=c，则 a=b（等量代换公理）。2.等量加等量，其和相等；即若 a=b 且 c=d，则 a+c=b+d（等量加法公理）。3.等

7、量减等量，其差相等；即若 a=b 且 c=d，则 a-c=b-d（等量减法公理）。4.完全叠合的两个图形是全等的（移形叠合公理）。5.全量大於分量，即 a+ba（全量大於分量公理）。公设：公理：几何系统（定理证明）8/34命题：在已知有限直线上可作一个等边三角形。ABC设AB为已知线段，证明可在其上作一个等边三角形证明：以A为圆心，AB长为半径作圆A（公设3）以B为圆心，AB长为半径作圆B（公设3）由两圆交点C作直线AC和BC（公设1）由圆定义可知AC=AB，BC=AB，则AC=BC=AB（公理1）所以，ABC为所求等边三角形主要内容主要内容9/34命题、命题逻辑联结词命题、命题逻辑联结词命题

8、变元、合式公式命题变元、合式公式重言式、永真蕴含、恒等式重言式、永真蕴含、恒等式带入规则、替换规则带入规则、替换规则对偶原理对偶原理范式及其判定问题范式及其判定问题命题演算的推理命题演算的推理概述概述1010/34/34现实语言现实语言翻译翻译判定判定推理推理应用：应用：计算机电路设计计算机电路设计 计算机程序构造计算机程序构造 程序正确性证明程序正确性证明1.1 命题与命题逻辑联结词命题与命题逻辑联结词一、命题一、命题 所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。和感叹句等因都不能判断其真

9、假，故都不是命题。定义定义：或者为真，或者为假而不是两者同时成立的陈述句被：或者为真，或者为假而不是两者同时成立的陈述句被称为一个命题。称为一个命题。或真或假，不能既真又假。或真或假，不能既真又假。例例1:1:判断下面语句是否是命题判断下面语句是否是命题华盛顿是美国的首都。华盛顿是美国的首都。多伦多是加拿大的首都。多伦多是加拿大的首都。1+101=110 1+101=110 几点了？几点了？x+1=3x+1=3真热呀！真热呀！坑爹坑爹神马都是浮云神马都是浮云11/34或真或假，或真或假，不能既真又不能既真又假假1.1 命题与命题逻辑联结词命题与命题逻辑联结词12/34理发师问题：理发师问题：理

10、发师只给所有不给自己理发的人理发理发师只给所有不给自己理发的人理发分析：分析：（1 1）理发师给自己理发）理发师给自己理发（2 2）理发师不给自己理发）理发师不给自己理发不能给自己理发不能给自己理发需要给自己理发需要给自己理发悖论悖论1.1 命题与命题逻辑联结词命题与命题逻辑联结词2.2.命题的真值及表示命题的真值及表示命题用大写的英文字母，如命题用大写的英文字母，如 ，表示。表示。P：今天是星期一。：今天是星期一。命题仅有两种可能的真值命题仅有两种可能的真值真和假，且二者只能居其一。真和假，且二者只能居其一。如如果一个命题的真值是真，则用果一个命题的真值是真，则用1或或True(T)来表示；

11、如果一个来表示；如果一个命题的真值是假，则用命题的真值是假，则用0或或False(F)来表示。来表示。13/34定义：定义：一个命题不能再分解为更简单的命题，这个命一个命题不能再分解为更简单的命题，这个命题称为题称为原子命题原子命题。如果如果下周日下雪，下周日下雪，那么那么我就去滑雪。我就去滑雪。如果如果下周日下周日不不下雨下雨并且并且没有考试，没有考试，那么那么我去海边玩。我去海边玩。这次演讲比赛，我们班将由赵明这次演讲比赛，我们班将由赵明或者或者张强参加。张强参加。1414/34/34命题命题原子命题原子命题？分子命题（复合命题）分子命题（复合命题）六种逻辑联结词六种逻辑联结词（1 1）联

12、结词）联结词“非非”，记为，记为“”，表示，表示“否定否定”的意思。的意思。（2 2）联结词）联结词“合取合取”，记为，记为“”，表示，表示“且且”的意的意思。思。（3 3）联结词）联结词“析取析取”，记为，记为“”，表示，表示“或或”的意的意思。思。（4 4）联结词）联结词“蕴涵蕴涵”，记为，记为“”“”，表示，表示“如果如果，则，则”的意思。的意思。（5 5）联结词）联结词“等价等价”，记为，记为“”，表示，表示“当且仅当当且仅当”的意思。的意思。（6 6）联结词）联结词“异或异或”，记为，记为“”，表示，表示“要么要么，要，要么么”的意思。的意思。1515/34/34定义 设P是一个命题

13、，则P的否定是一个新的命题，记作“”，读作“非P”。自然语言中的“非”、“不”和“没有”等否定词“”的意义如下表：否定否定或真值表：利用运算对象真值的所有可能组合判断命题的真假。16/34例：找出命题“熊孩子都是坑爹的”的否定。“并非所有的熊孩子都是坑爹的。”“所有的熊孩子都不是坑爹的。”否定否定对整体否定，不是对局部的否定17/34合取合取定义定义：表征意义表征意义两命题合取的真值表两命题合取的真值表1818/34/34或或合取合取1919/34/34析取定义：表征意义两命题析取的真值表20/34或析取21/34可兼或不可兼或异或 定义：表征意义双条件 的真值表22/34或蕴涵蕴涵定义：表征

14、意义蕴含 的真值表23/34或蕴涵蕴涵政治家竞选时许诺政治家竞选时许诺“如果我当选了，那么我将会打击腐败如果我当选了，那么我将会打击腐败”。如果今天是星期五，那么如果今天是星期五，那么2+2=4.2+2=4.与程序设计中与程序设计中if p then S语句的区别。语句的区别。2424/34/34现实世界中无意义的语言也可以翻译蕴涵蕴涵在在日日常常生生活活中中，用用条条件件式式表表示示前前提提和和结结论论之之间间的的因果或实质关系，这种条件式称为因果或实质关系，这种条件式称为形式条件命题形式条件命题。然然而而在在命命题题逻逻辑辑中中，一一个个条条件件式式的的前前提提并并不不要要求求与与结结论论

15、有有任任何何关关系系，这这种种条条件件式式称称为为实实质质条条件件命命题题。2525/34/34等价定义：表征意义等价 的真值表26/34或！注意！注意：由逻辑联结词联结的命题之间不需要任何关由逻辑联结词联结的命题之间不需要任何关系。系。优先次序优先次序：1.1 命题与命题逻辑联结词命题与命题逻辑联结词2727/34/34 （）（）句子到逻辑表达式的翻译句子到逻辑表达式的翻译步骤：步骤：确定给定的句子确定给定的句子是否为命题是否为命题；找出各找出各原子命题原子命题并确定句子中的连词为对应并确定句子中的连词为对应的的联结词联结词；用用正确的语法正确的语法把原命题表示成由原子命题、把原命题表示成由

16、原子命题、联结词和圆括号组成的公式。联结词和圆括号组成的公式。2828/34/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译翻译下列命题：翻译下列命题：(1)(1)他既聪明又用功。他既聪明又用功。(2)(2)他虽聪明但不用功。他虽聪明但不用功。解：解：原子命题原子命题 P：他聪明。：他聪明。Q：他用功。：他用功。则有：则有：(1)(1)翻译成：翻译成：P Q (2)(2)翻译成：翻译成：P Q2929/34/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译除非有时间，我才去看电影除非有时间，我才去看电影A：我有时间。：我有时间。B：我去看电影。：我去看电影。翻译为：翻译为：B A我不承认你是

17、对的，除非太阳从西边出来我不承认你是对的，除非太阳从西边出来A：我不承认你是对的。：我不承认你是对的。B：太阳从西边出来。：太阳从西边出来。翻译为：翻译为：B A3030/34/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译如果你和他都不固执己见的话，那么不愉如果你和他都不固执己见的话，那么不愉快的事情就不会发生了。快的事情就不会发生了。P：你固执己见。：你固执己见。Q：他固执己见。：他固执己见。R：不愉快的事情不会发生。：不愉快的事情不会发生。翻译为：翻译为：(P Q)R如果你和他不都是固执己见的话，如果你和他不都是固执己见的话，那么不那么不愉快的事情就不会发生了。愉快的事情就不会发生了。

18、(P Q)R3131/34/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译P：这个材料很有趣。：这个材料很有趣。Q：这个习题很难。：这个习题很难。R：这门课程使人喜欢。：这门课程使人喜欢。1、这个材料很有趣，而且这些习题很难。、这个材料很有趣，而且这些习题很难。2、这个材料无趣，习题也不难，那么，这门课程、这个材料无趣，习题也不难，那么，这门课程就不会使人喜欢。就不会使人喜欢。3、这个材料无趣，习题也不难，而且这门课程也、这个材料无趣，习题也不难，而且这门课程也不使人喜欢。不使人喜欢。4、这个材料很有趣意味着这些习题很难，反之亦、这个材料很有趣意味着这些习题很难，反之亦然。然。5、或者这个材

19、料很有趣，或者这些习题很难，而、或者这个材料很有趣，或者这些习题很难，而且两者恰具其一。且两者恰具其一。3232/34/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译除非你已满除非你已满1616周岁，否则只要你的身高不周岁，否则只要你的身高不足足4 4英尺就不能乘公园滑行铁道游乐车。英尺就不能乘公园滑行铁道游乐车。P：你能乘坐公园滑行铁道游乐车。：你能乘坐公园滑行铁道游乐车。Q：你身高不足：你身高不足4 4英尺。英尺。R：你已满：你已满1616周岁。周岁。翻译成：翻译成：(R Q)P3333/34/34逻辑难题逻辑难题一个岛上居住着两类人一个岛上居住着两类人骑士和流氓。骑士说骑士和流氓。骑士说的都是实话，而流氓只会说谎。你碰到两个人的都是实话，而流氓只会说谎。你碰到两个人A A和和B B，如果，如果A A说说“B B是骑士是骑士”，B B说说“我们两个不我们两个不是一类人是一类人”，请判断，请判断A A、B B到底是流氓还是骑士。到底是流氓还是骑士。解：解：首先假设首先假设P:AP:A是骑士；是骑士；Q:BQ:B是骑士是骑士如果如果A A是骑士是骑士如果如果A A是流氓是流氓3434/34/34作业作业P21P21：1,21,2，3 3，4 4（1 1）、（）、（3 3）P22:6P22:6（2 2）（）（4 4），9 93535/34/34http:/s/1mgpdFug