第一章 命题逻辑-1st

《第一章 命题逻辑-1st》由会员分享，可在线阅读，更多相关《第一章 命题逻辑-1st（32页珍藏版）》请在文档大全上搜索。

1、离散数学授课教师：曹晓东教授联系电话：13889564495办公电话：87571519办公地点：综合楼305离散数学离散数学第一章第一章 命题逻辑命题逻辑3/34 什么是数理逻辑？什么是数理逻辑？数理逻辑是用数学方法研究思维规律的一门学科。数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指所谓数学方法是指: :用一套数学的符号系统来描述和用一套数学的符号系统来描述和处理思维的形式与规律。因此，处理思维的形式与规律。因此，数理逻辑又称为符数理逻辑又称为符号逻辑。号逻辑。 数理逻辑的创始人数理逻辑的创始人-莱布尼茨莱布尼茨(Leibniz, Gottfried Wilhelm) 1646

2、.7.1-1716.11.14 4/34德国数学家、物理学家、哲学家等，德国数学家、物理学家、哲学家等，一个举世罕见的科学天才。研究领域涉一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法及到逻辑学、数学、力学、地质学、法学、历史学、语言学、生物学以及外交、学、历史学、语言学、生物学以及外交、神学等诸多方面神学等诸多方面. .出生于德国东部莱比锡的一个书香之出生于德国东部莱比锡的一个书香之家，父亲是莱比锡大学的道德哲学教授，家，父亲是莱比锡大学的道德哲学教授，母亲出生在一个教授家庭。莱布尼兹的母亲出生在一个教授家庭。莱布尼兹的父亲在他年仅父亲在他年仅6 6岁时便去世了，给他留

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

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

5、它和中国的八卦联系系统阐述了二进制记数法，并把它和中国的八卦联系起来。起来。5/34主要内容主要内容6/34 命题、命题逻辑联结词命题、命题逻辑联结词 命题变元、合式公式命题变元、合式公式 重言式、永真蕴含、恒等式重言式、永真蕴含、恒等式 带入规则、替换规则带入规则、替换规则 对偶原理对偶原理 范式及其判定问题范式及其判定问题 命题演算的推理命题演算的推理1.1概述概述7/34现实语言现实语言翻译翻译判定判定推理推理应用：应用：计算机电路设计计算机电路设计 计算机程序构造计算机程序构造 程序正确性证明程序正确性证明1.2命题与命题逻辑联结词命题与命题逻辑联结词一、命题一、命题 所谓命题，是指具

6、有非真必假的陈述句。而疑问句、所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命祈使句和感叹句等因都不能判断其真假，故都不是命题。题。 1.定义：一个具有真假意义的陈述句被称为一定义：一个具有真假意义的陈述句被称为一 个命题。个命题。 或真或假，不能既真又假。或真或假，不能既真又假。 例例1:判断下面语句是否是命题判断下面语句是否是命题 华盛顿是美国的首都。华盛顿是美国的首都。 多伦多是加拿大的首都。多伦多是加拿大的首都。 1+101=110 几点了？几点了？ x+1=3 真热呀！真热呀！8/34或真或假，或真或假，不能既真不能既真又假又假1.2命题与

7、命题逻辑联结词命题与命题逻辑联结词9/34 理发师问题：理发师问题：理发师给所有不给自己理发的人理发理发师给所有不给自己理发的人理发分析：分析：（1）理发师给自己理发）理发师给自己理发（2）理发师不给自己理发）理发师不给自己理发不能给自己理发不能给自己理发需要给自己理发需要给自己理发悖论悖论1.2命题与命题逻辑联结词命题与命题逻辑联结词一、命题一、命题 2.命题的真值及表示命题的真值及表示命题用大写的英文字母，如命题用大写的英文字母，如 ， ， 表示。表示。 P：今天是星期二。：今天是星期二。命题仅有两种可能的真值命题仅有两种可能的真值真和假，且二者只能居其真和假，且二者只能居其一。一。如果一

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

9、（复合命题）分子命题（复合命题）5种逻辑联结词种逻辑联结词 否定词否定词“并非并非” 合取词合取词“并且并且” 析取词析取词“或者或者” 蕴含词蕴含词“如果如果，那么，那么”（单向词）（单向词） 双向蕴含词双向蕴含词“当且仅当当且仅当”（双向词）（双向词）12/34 定义：设P是一个命题，则P的否定是一个新的命题，记作“ ”，读作“非P”。 否定词“”的意义如下表：否定否定PPPTFFTPP0110或真值表：利用运算对象真值的所有可能组合判断命题的真假。13/34 例：找出命题“所有的素数都是奇数”的否定。 “并非所有的素数都是奇数。” “所有的素数都不是奇数。”否定否定对整体否定，不是对局部

10、的否定14/34合取合取 定义：定义： 表征意义表征意义两命题合取的真值表两命题合取的真值表PQ（在命题 和 均为真时为真，否则为假。）15/34PQPQPQ设 和 是命题，则用表示命题“ 并且 ”。PQPQPQPQFFFFTFTFFTTT000010100111或或合取合取PQPQ命题 ： 今天是星期五。命题 ： 今天下雨。找出命题 和 的合取PQ解：表示“今天是星期五并且下雨”。这一命题在下雨的星期五成真，不下雨的星期五和不是星期五的日子都为假。16/34析取 定义： 表征意义两命题析取的真值表PQ（在命题 和 均为假时为假，否则为真。）17/34PQPQPQ设 和 是命题，则用表示命题“

11、 或者 ”。PQPQPQPQFFFFTTTFTTTT000011101111或析取PQPQ例：命题 ： 李明在教室。命题 ： 张强是个好教练。找出命题 和 的析取PQ解：表示“李明在教室或张强是个好教练”。PQ例：命题 ： 李明在教室。命题 ： 李明在网球场。表示命题“李明在教室或在网球场”？18/34可兼或不可兼或异或 定义： 表征意义双条件 的真值表PQ（在 和 中恰有一个为真时为真，否则为假。）19/34PQP QPQ设 和 是命题，则用表示命题“ 异或 ”。PQP QPQP QFFFFTTTFTTTF000101011110P Q或单条件定义： 表征意义蕴含 的真值表PQ（在 为真而

12、为假时为假，否则为真。）20/34PQPQPQ设 和 是命题，则用表示命题“如果 那么 ”。PQPQPQPQFFTFTTTFFTTT001100011111PQ或单条件单条件 政治家竞选时许诺政治家竞选时许诺“如果我当选了，那么我将会减税如果我当选了，那么我将会减税”。 如果今天是星期五，那么如果今天是星期五，那么2+2=4. 与程序设计中与程序设计中if p then S语句的区别。语句的区别。21/34现实世界中无意义的语言也可以翻译单条件单条件 在日常生活中，用条件式表示前提和结论之间在日常生活中，用条件式表示前提和结论之间的因果或实质关系，这种条件式称为的因果或实质关系，这种条件式称为

13、形式条件形式条件命题命题。 然而在命题逻辑中，一个条件式的前提并不要然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式称为求与结论有任何关系，这种条件式称为实质条实质条件命题件命题。22/34双条件 定义： 表征意义双条件 的真值表PQ（在 和 具有相同的真值时为真，否则为假。）23/34PQPQPQ设 和 是命题，则用表示命题“ 等值于 ”。PQPQPQPQFFTFTFTFFTTT001100010111PQ或1.2命题与命题逻辑联结词命题与命题逻辑联结词 注意：注意：由逻辑联结词联结的命题之间不需要任何关由逻辑联结词联结的命题之间不需要任何关系。系。 优先次序：优先次序

14、：()PQRPQR24/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译 步骤：步骤：确定给定的句子确定给定的句子是否为命题是否为命题；找出各找出各原子命题原子命题并确定句子中的连词为对应并确定句子中的连词为对应的的联结词联结词；用用正确的语法正确的语法把原命题表示成由原子命题、把原命题表示成由原子命题、联结词和圆括号组成的公式。联结词和圆括号组成的公式。25/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译 翻译下列命题：翻译下列命题：(1)他既聪明又用功。他既聪明又用功。(2)他虽聪明但不用功。他虽聪明但不用功。解：解：原子命题原子命题 P：他聪明。：他聪明。 Q：他用功。：他用功。则有：

15、则有： (1)翻译成：翻译成： P Q (2)翻译成：翻译成： P Q26/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译 除非有时间，我才去看电影除非有时间，我才去看电影 A：我有时间。：我有时间。 B：我去看电影。：我去看电影。翻译为：翻译为： B A 我不承认你是对的，除非太阳从西边出来我不承认你是对的，除非太阳从西边出来 A：我不承认你是对的。：我不承认你是对的。 B：太阳从西边出来。：太阳从西边出来。翻译为：翻译为： B A27/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译 如果你和他都不固执己见的话，那么不愉如果你和他都不固执己见的话，那么不愉快的事情就不会发生了。快的事情就

16、不会发生了。 P：你固执己见。：你固执己见。 Q：他固执己见。：他固执己见。 R：不愉快的事情不会发生。：不愉快的事情不会发生。翻译为：翻译为： (PQ)R 如果你和他不都是固执己见的话，如果你和他不都是固执己见的话，那么不那么不愉快的事情就不会发生了。愉快的事情就不会发生了。 (PQ)R28/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译P：这个材料很有趣。：这个材料很有趣。Q：这个习题很难。：这个习题很难。R：这门课程使人喜欢。：这门课程使人喜欢。1、这个材料很有趣，而且这些习题很难。、这个材料很有趣，而且这些习题很难。2、这个材料无趣，习题也不难，那么，这门课程、这个材料无趣，习题也不

17、难，那么，这门课程就不会使人喜欢。就不会使人喜欢。3、这个材料无趣，习题也不难，而且这门课程也、这个材料无趣，习题也不难，而且这门课程也不使人喜欢。不使人喜欢。4、这个材料很有趣意味着这些习题很难，反之亦、这个材料很有趣意味着这些习题很难，反之亦然。然。5、或者这个材料很有趣，或者这些习题很难，而、或者这个材料很有趣，或者这些习题很难，而且两者恰具其一。且两者恰具其一。29/34句子到逻辑表达式的翻译句子到逻辑表达式的翻译 除非你已满除非你已满16周岁，否则只要你的身高周岁，否则只要你的身高不足不足4英尺就不能乘公园滑行铁道游乐车。英尺就不能乘公园滑行铁道游乐车。 P：你能乘坐公园滑行铁道游乐

18、车。：你能乘坐公园滑行铁道游乐车。 Q：你身高不足：你身高不足4英尺。英尺。 R：你已满：你已满16周岁。周岁。翻译成：翻译成：(R Q) P30/34逻辑难题逻辑难题 一个岛上居住着两类人一个岛上居住着两类人骑士和流氓。骑士骑士和流氓。骑士说的都是实话，而流氓只会说谎。你碰到两个说的都是实话，而流氓只会说谎。你碰到两个人人A和和B，如果，如果A说说“B是骑士是骑士”，B说说“我们两我们两个不是一类人个不是一类人”，请判断，请判断A、B到底是流氓还是到底是流氓还是骑士。骑士。 解：解：首先架设首先架设P: A是骑士；是骑士；Q: B是骑士是骑士如果如果A是骑士是骑士如果如果A是流氓是流氓31/34作业作业 教材教材P7： 3（2）（）（3）（）（4） ，4（1）、（）、（3） ，5（2）（）（4）,6,7,8,932/34