《苏XI友无密码课件 第1章 命题逻辑》由会员分享，可在线阅读，更多相关《苏XI友无密码课件 第1章 命题逻辑（108页珍藏版）》请在金锄头文库上搜索。
1、,离散数学主讲教师：苏喜友,北京林业大学 苏喜友,1,绪论,离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。,北京林业大学信息学院 苏喜友,2,绪论,一、离散数学在计算机科学中的地位和作用 离散数学为计算机科学与技术的发展奠定了重要的数学基础。 不仅离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着计算机科学与技术的发展。,北京林业大学信息学院 苏喜友,3,绪论,例如： 布尔代数为开关电路的研究提供了重要的分析工具，并且导致建立了一门完整的数字逻辑理论； 谓词演算
2、成为程序理论的一种重要的研究工具，即研究程序正确性问题； 代数系统的理论被用于对数据结构的研究，产生了抽象数据类型的理论，代数系统也成为编码理论的数学基础； 平面图的理论用于印刷电路板的设计；,北京林业大学信息学院 苏喜友,4,绪论,图论的概念和理论广泛用于人工智能、操作系统、数据结构、数据检索等； 图灵机模型和递归函数理论构成了可计算性理论的研究基础，图灵机模型和可计算性理论为第一台电子计算机的诞生奠定了理论基础。,北京林业大学信息学院 苏喜友,5,绪论,概括来说，离散数学与计算机科学中的数据结构、操作系统、编译理论、数字逻辑理论、算法分析、逻辑程序设计、系统结构、容错诊断、机器定理证明、人
3、工智能等课程有着紧密的联系。 因此,离散数学便成为了学习、掌握和研究计算机科学与技术以及信息管理与信息系统的必需的理论基础。,北京林业大学信息学院 苏喜友,6,绪论,二、离散数学的特征 离散数学的研究对象是各种各样的离散量的结构及其离散量之间的关系，并且一般是有限个或者可数个元素，如自然数、真假值、字母表等。 同时，在离散数学中，也非常重视“能行性”问题的研究，即要解决一个问题，首先要证明此问题解的存在性，但是仅仅解决存在性是不够的，还需要找出得到此问题解的步骤来，而且其步骤应是有限的、有规则的，这与连续数学中的讨论方式完全不同。,北京林业大学信息学院 苏喜友,7,绪论,离散数学的上述特征使它
4、成为研究计算机科学的基本数学工具。由于计算机（不管是硬件还是软件）是一个离散的结构，故计算机科学的研究对象大都呈离散形式，这与离散数学的研究对象是一致的。 同时，在计算机科学中任何一个问题（不管是硬件还是软件）不仅要解决解的存在性，而且更需要解的能行性。 因此，离散数学就成为了研究计算机科学最合适的工具。,北京林业大学信息学院 苏喜友,8,绪论,三、离散数学的主要内容 由于离散数学以离散量为研究对象，故一切以离散现象为研究对象或作为其研究对象之一的数学均属于离散数学。 所以，离散数学是一门综合的数学学科，它由多门数学分支组成，每一个分支基本上可以看成是一门独立的学科，它们从不同的角度出发，研究
5、各种离散量之间数与形的关系，同时，这些分支又互相联系。,北京林业大学信息学院 苏喜友,9,绪论,离散数学的主要内容有：数理逻辑、集合论、代数结构、图论、自动机理论、递归函数论、组合数学、数论、离散概率等。,北京林业大学信息学院 苏喜友,10,第一部分 数理逻辑（Mathematical Logic),逻辑学是研究推理的科学，具有十分悠久的历史。 形式逻辑是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。 辩证逻辑是以辩证法认识论的世界观为基础的逻辑学。 数理逻辑是数学化的逻辑学，是用数学方法研究推理的科学，其历史只有300多年。,北京林业大学信息学院 苏喜友,11,第一部分 数理逻
6、辑（Mathematical Logic),所谓数学的方法就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑(Symbolic Logic)。 为什么要学习数理逻辑呢？ 程序的一般描述：程序算法数据算法逻辑控制 为了更好地使用计算机，就必须学习数理逻辑。同时，通过对推理规律和证明方法的学习，可以培养自己的逻辑思维能力，提高证明问题的技巧。,北京林业大学信息学院 苏喜友,12,第一部分 数理逻辑（Mathematical Logic),关于数理逻辑在计算机科学中的重要地位荷兰计算机科学家戴克斯特拉（Dijkstra）曾经这样形象地说：我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟
7、了。我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说了，可我不知道。要是我能年轻20岁的话，就要回去学逻辑。,北京林业大学信息学院 苏喜友,13,第一部分 数理逻辑（Mathematical Logic),数理逻辑既是数学又是逻辑学。它研究数学中的逻辑问题，用数学的方法研究形式逻辑。其中, 关于形式语言的研究，为建立计算机用语言提供了基础； 关于形式系统的语法、语义的研究解决了计算机软件的语言问题； 计算机的线路可用命题演算的公式来表示； 机器证明、程序设计逻辑、程序正确性证明无一不是数理逻辑的研究成果。 因而，数理逻辑是计算机科学的基础理论之一。,
8、北京林业大学信息学院 苏喜友,14,第一章 命题逻辑,命题逻辑（Propositional Logic）研究命题和命题联结词的逻辑结构、命题之间的推理关系.1 命题符号化及联结词2 命题公式与赋值3 等值演算4 联结词全功能集5 范式6 推理理论,北京林业大学信息学院 苏喜友,15,1 命题符号化及联结词,一、什么是命题？定义1 可以辨别真假的陈述句称为命题（Proposition）. 做为命题的陈述句所表达的判断只有两种结果, 正确的或错误的, 称这种判断的结果为命题的真值. 真值只能取两个值: 真或假.真判断正确;假判断错误. 任何命题的真值都是唯一的. 因而又可以称命题是具有唯一真值的陈
9、述句.真值为真的命题称为真命题, 如太阳是圆的;真值为假的命题称为假命题, 如月亮是方的.,北京林业大学信息学院 苏喜友,16,1 命题符号化及联结词,例1 判断下列句子中哪些是命题. （1）2是素数. （2） 是有理数. （3） x+y10. （4）太阳从西方升起. （5）乌鸦是黑色的. （6）今天天气真好啊！ （7）地球外的星球上也有生物. （8）你要出去吗？ （9）请把门关上！ （10）我正在说谎.,真命题,假命题,真命题,真值唯一,假命题,感叹句,疑问句,祈使句,没有确定的真值,真值不唯一,北京林业大学信息学院 苏喜友,17,1 命题符号化及联结词,命题用p,q,r,s,; pi,qi
10、,ri,si,来表示.如: p:2是素数.q: 是有理数. 将命题的真值也符号化.真1，假0.,北京林业大学信息学院 苏喜友,18,1 命题符号化及联结词,定义2（1）简单命题(Simple Proposition)指陈述句是一个简单句的命题, 亦称为原子命题.（2）复合命题(Compound Proposition)由简单命题用联结词及其它辅助符号组成的新命题.复合命题亦称为分子命题.简单命题与复合命题统称为命题.,北京林业大学信息学院 苏喜友,19,1 命题符号化及联结词,例2（1）今天天气很冷.（2）今天天气很冷并且刮风.（3）今天天气很冷并且刮风, 但室内暖和.,北京林业大学信息学院
11、苏喜友,20,1 命题符号化及联结词,二、命题联结词定义3 否定（Negation）词:设p为任一命题, 复合命题“非p”（或“p的否定”）称为p的否定式, 记作p, 为否定联结词, p为真当且仅当p为假.p的真值表：,北京林业大学信息学院 苏喜友,21,1 命题符号化及联结词,在自然语言中，和对应的词有：不，不是，无，没有，非，并非，并不等. 例如： p：2 是素数，真值为1.p: 2不是素数，真值为0.,北京林业大学信息学院 苏喜友,22,1 命题符号化及联结词,定义4 合取（Conjunction）词: 设p、q为两命题, 复合命题“p并且q”(或“p和q”)称为p与q的合取式, 记作p
12、q, 为合取联结词, pq为真当且仅当p与q同时为真.,pq的真值表如右：,合取联结词在用法上很灵活,自然语言中的和, 与, 且, 并且, 以及, 及, 既,又, 不但,而且, 虽然,但是等都可以化为符号.,北京林业大学信息学院 苏喜友,23,1 命题符号化及联结词,例3 将下列命题符号化: （1）张路既聪明又用功. （2）张路不仅聪明, 而且用功. （3）张路虽然不太聪明, 但他很用功. （4）张路不是不聪明, 而是不用功. （5）张路与张强是好朋友.,设P：张路聪明, q：张路用功.,pq,pq,pq,()pq,设r：张路与张强是好朋友.,r,北京林业大学信息学院 苏喜友,24,1 命题符
13、号化及联结词,定义5 析取（Disjunction）词：设p、q为两命题, 复合命题“p或q”称为p与q的析取式, 记作pq, 为析取联结词, pq为真当且仅当p与q中至少一个为真.,pq的真值表如右：,在自然语言中与析取联结词对应的词有：或, 或者, 或许, 可能, 也许等.,北京林业大学信息学院 苏喜友,25,1 命题符号化及联结词,析取联结词的逻辑关系是明确的，但自然语言中的“或”具有二义性，用“或”联结的命题，有时具有相容性，有时又具有排斥性.,北京林业大学信息学院 苏喜友,26,1 命题符号化及联结词,（1）设p:今天刮风, q:今天下雨.,例4 将下面命题符号化： （1）今天刮风或
14、下雨. （2）灯泡坏了或开关坏了. （3）我向东行或向西行. （4）派老王或老李中的一人到上海开会.,pq,pq,（2）设p：灯泡坏了, q：开关坏了.,（3）设p:我向东行, q:我向西行.,(pq)(pq),（4）设p:派老王到上海开会, q:派老李到上海开会.,(pq)(pq),解：,（3）的等价命题：我向东行而没向西行, 或我向西行而没向东行.,（4）的等价命题：派老王而不派老李到上海开会, 或者派老李而不派老王到上海开会.,北京林业大学信息学院 苏喜友,27,1 命题符号化及联结词,定义6 蕴涵（Implication）词：设p、q为两命题,复合命题“如果p, 则q”称为p与q的蕴涵
15、式, 记作pq, 称p为蕴涵式的前件, q为蕴涵式的后件, 称作蕴涵联结词, pq为假当且仅当p为真q为假.,pq的真值表如右：,对于蕴涵联结词, 在自然语言中有多种不同的表示方式, 如当,则, 若(如果, 假如), 那么(则), 除非, 才能, 只要,就, 只有, 才等.,北京林业大学信息学院 苏喜友,28,1 命题符号化及联结词,pq的逻辑关系是：p是q的充分条件, q是p的必要条件. 但要注意：（1）在自然语言里, 特别是在数学中, q是p的必要条件有不同的叙述方式, 如“只要p就q”,“只有q才p”,“p仅当q”等都可以转化为pq的形式;（2）在自然语言里,“如果p, 则q”中p与q往
16、往有某种内在联系, 而在数理逻辑里, p与q不一定有什么内在联系;（3）在数学和其它自然科学中,“如果p, 则q”往往表示的是前件为真, 后件也为真的推理关系. 但在数理逻辑中, 当p为假时, pq为真.,北京林业大学信息学院 苏喜友,29,1 命题符号化及联结词,例5 将下列命题符号化: （1）若3+3=6, 则地球是运动的. （2）只要a是4的倍数, a就是2的倍数. （3）只有a是2的倍数, a才能是4的倍数. （4）a是4的倍数, 仅当a是2的倍数. （5）除非a是2的倍数, a才能是4的倍数. （6）只有a是4的倍数, a才能是2的倍数.,解：,rs,rs,（2）（6）设r:a是4的倍数, s:a是2的倍数.,pq,sr,（1）设p:3+3=6, q:地球是运动的.,rs,rs,
