第一章 命题逻辑(11-12).ppt

2020/6/7,1,离散数学,李瑞红软件学院,2020/6/7,2,课程性质,离散数学（又称计算机数学）是理工各专业的专业必修课，是数学中涉及面非常广泛的一门学科。它不仅是计算机科学中重要的基础理论之一，是学习后续计算机专业课程不可缺少的数学工具，也是培养学生抽象思维能力和逻辑推理能力的核心课程。,2020/6/7,3,课程目标,离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。,2020/6/7,4,与其他课程的关系,离散数学与计算机科学的其他课程，如：数据结构、操作系统、编译原理、算法分析、人工智能等有密切关系。它是这些课程的先导和基础课程。,2020/6/7,5,教材与参考书,离散数学上海科学技术文献出版社，1982，左孝凌等编著离散数学高等教育出版社，2008屈婉玲等编著,2020/6/7,6,课程内容,本课程根据大纲的内容和相关独立性可分为四大部分：第一部分数理逻辑包括命题逻辑；谓词逻辑第二部分集合论包括集合与关系；函数第三部分代数系统包括代数结构；格与布尔代数第四部分图论,2020/6/7,7,学习方法,本课程有两个特点：（1）定义、定理多本课程内容=定义+定理+例题（2）课外作业比较多,2020/6/7,8,学习方法,为了学好这门课程，特提出三点要求：（1）弄懂定义、定理，弄懂例题，加深对定义、定理的理解；（2）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。,2020/6/7,9,学习方法,最后，做两点说明：（1）考试内容以课堂上讲的内容为范围；（2）每次课后布置作业。希望大家认真完成。,2020/6/7,10,第一篇数理逻辑,逻辑学：研究思维形式及思维规律的科学。辨证逻辑：研究事物发展的规律。形式逻辑：对思维的形式结构和规律进行研究。数理逻辑：是用数学的方法研究概念、判断和推理的科学，属于形式逻辑。,2020/6/7,11,第一章命题逻辑,1-1命题及其表示法1-2联结词1-3命题公式与翻译1-4真值表与等价公式1-5重言式与蕴含式1-6其他联结词1-7对偶与范式1-8推理理论,2020/6/7,12,第一章命题逻辑,教学目的及要求：深刻理解和掌握命题逻辑中基本概念和基本方法教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、对偶与范式、推理理论。教学重点：命题逻辑中的基本概念和基本推理方法。教学难点：推理理论,2020/6/7,13,1.1命题,定义1.1：具有确定真假值的陈述句叫命题。该定义有两层含义：（1）命题是陈述句。其它的语句，如疑问句、祈使句、感叹句均不是命题；（2）这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假。,2020/6/7,14,1.1命题,命题的真值作为命题的陈述句所表示的判断结果称为命题的真值，真值只取两个值：真或假。凡是与事实相符的陈述句是真命题，而与事实不符合的陈述句是假命题。通常用1（或字母T）表示真，用0（或字母F）表示假。,2020/6/7,15,1.1命题,例判断下列语句是否为命题，并指出其真值。（1）北京是中国的首都。（2）5可以被2整除。（3）2+2=5。（4）请勿吸烟！（5）乌鸦是黑色的吗？（6）这个小男孩多勇敢啊！（7）别的星球上有生物。（8）我正在说谎。,2020/6/7,16,1.1命题,注意：一个语句本身是否能分辨真假与我们是否知道它的真假是两回事。也就是说，对于一个句子，有时我们可能无法判定它的真假，但它本身却是有真假的，那么这个语句是命题，否则就不是命题。悖论不是命题。,2020/6/7,17,1.1命题,命题的分类原子命题：是指不能再分解为更简单命题的命题；复合命题：若干个原子命题使用适当的联结词所组成的新命题。例如“雪是白的”是原子命题；“昨天下雨，而且打雷”，“如果明天天晴我就去打球或者游泳”都是复合命题。,2020/6/7,18,1.1命题,命题的表示法在数理逻辑中，使用26个大写英文字母A、B、CZ或用带下标的大写字母或用数字，如Ai，12等表示命题。表示命题的符号称为命题标识符。例P：今天下雨。12：今天下雨。,2020/6/7,19,1.1命题,定义1.2一个命题标识符如表示确定的命题，称为命题常量；如果命题标识符只表示任意命题的位置标志，它不能确定真值，称为命题变元。如果命题符号P代表命题常量则意味它是某个具体命题的符号化，如果P代表命题变元则意味着它可指代任何具体命题。命题变元不是命题。本书中如果没有特别指明，通常来说命题符号P等是命题变元，即可指代任何命题。,2020/6/7,20,1.2联结词,在数理逻辑中，复合命题是由原子命题与逻辑联结词组合而成。联结词：联结命题的词。联结词又称逻辑联结词或真值联结词。联结词(,),2020/6/7,21,1.2联结词,（1）否定“”（或“”）设P为一命题，P的否定是一个新命题，记作“P”，读作“非P”。否定词（Negation）是一元联结词。相当于自然语言中的“非”、“不”等，真值表如右图。,2020/6/7,22,1.2联结词,（1）否定“”（或“”）举例：每一种生物均是动物。F：有一些生物不是动物。T这里不能讲成“每一种生物都不是动物”。对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。,2020/6/7,23,1.2联结词,（2）合取“”两个命题P和Q的合取是一个复合命题，记作“PQ”。读作“P与Q”。合取词（Conjunction）是二元联结词。相当于自然语言中的“与”、“并且”、“而且”、“也”等，真值表如右图。,2020/6/7,24,1.2联结词,（2）合取“”举例(a)P：王华的成绩很好Q：王华的品德很好。PQ：王华的成绩很好并且品德很好。(b)P：我们去种树Q：房间里有一台电视机PQ：我们去种树与房间里有一台电视机。,2020/6/7,25,1.2联结词,（2）合取“”举例(c)P：今天下大雨Q：3+3=6。PQ：今天下大雨与3+3=6。由例(b)(c)可见，在日常生活中，合取词应用在两个有关系的命题之间。而在逻辑学中，合取词可以用在两个毫不相干的命题之间。,2020/6/7,26,1.2联结词,（3）析取“”两个命题P和Q的析取是一个复合命题，记作“PQ”。读作“P或Q”。析取词（Disjunction）是二元联结词。相当于自然语言中的“或”、“要么要么”等，真值表如右图。,2020/6/7,27,1.2联结词,区分“可兼或”与“不可兼或”（1）今晚我在家看电视或去剧场看戏。（2）他可能是100米或400米赛跑的冠军。（3）他昨天做了二十或三十道习题。（4）灯泡有故障或开关有故障。（5）今晚写字或看书。（6）今天下雨或打雷。（7）他通过电视看杂技或到剧场看杂技。（8）他乘火车去北京或乘飞机去北京。,2020/6/7,28,1.2联结词,（3）析取“”例P：王晓学过英语。Q：王晓学过法语。PQ：王晓学过英语或王晓学过法语。,2020/6/7,29,1.2联结词,（4）条件“”给定两个命题P和Q，其条件命题是一个复合命题，记作“PQ”。读作“如果P，那么Q”或“若P则Q”。P称为前件，Q称为后件。条件词是二元联结词。相当于自然语言中的“若则”、“如果就”、“只有才”，真值表如右图。,2020/6/7,30,1.2联结词,（4）条件“”举例（a）P：我拿起一本书。Q：我一口气读完了这本书。PQ：如果我拿起一本书，则我一口气读完了这本书。(b)P：月亮出来了Q：33=9PQ：如果月亮出来了，则33=9。,2020/6/7,31,1.2联结词,（4）条件“”通常称：(a)为形式条件命题前提和结果有某种形式和内容上的联系。(b)为实质条件命题前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。所以,是形式条件命题一定是实质条件命题,反之不一定。“”是实质条件命题。,2020/6/7,32,1.2联结词,（4）条件“”例：我买到了鱼；:我吃鱼。：如果我买到了鱼，则我吃鱼。但“如果我没买到鱼，则我吃鱼”，在日常生活中不可能，但在单条件命题的定义中是允许的。,2020/6/7,33,1.2联结词,（5）双条件“”给定两个命题P和Q，其复合命题pq称作双条件命题，读作“P当且仅当Q”。双条件词是二元联结词。相当于自然语言中的“等价”、“当且仅当”、“充要条件”等，真值表如右图。,2020/6/7,34,1.2联结词,（5）双条件“”举例（a）：ABC是等腰三角形：ABC