编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、.ppt

《编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学是计算机科学(编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、计算机网络等)、数学、数字电路、人工智能等多学科的共同语言和基础。本学期将讲授数理逻辑与图论个部分。其中数理逻辑讲授命题逻辑、谓词逻辑两部分，分别由Boole于1847年和Frege于1879年建立。命题逻辑把简单命题作为基本单元进行推理演算；而谓词逻辑对简单命题进一步剖析，并考虑到变量数量的一般与个别。前言1例1：在举重比赛中，有两名副裁判，一名主裁判。当两名以上裁判（必须包括主裁判在内）认为运动员举杠铃合格，按电钮，才裁决合格。试用与非门设计该电路。解：设主裁判为变元A，副裁判分别为变元B和变元C；按电

2、钮为1，不按为0。表示合格与否的灯为Y，合格为1，否则为0。（1）根据逻辑要求列出真值表。关于命题逻辑的两个有趣例子2真值表3（2）由真值表写出表达式：（3）化简：这个小例子涉及到简单命题、复合命题、逻辑联结词的定义、运算优先权、联结词的完备集(例如“与非联结词”构成一个完备集)等等。我们都将介绍到。4（4）画出逻辑电路图：5例2：设计一个楼上、楼下开关的控制逻辑电路来控制楼梯上的路灯。使之在上楼前，用楼下开关打开电灯，上楼后，用楼上开关关灭电灯；或者在下楼前，用楼上开关打开电灯，下楼后，用楼下开关关灭电灯。解：设楼上开关为变元A，楼下开关为变元B，灯泡为变元Y。并设A、B向上时为1，向

3、下时为0；灯亮时Y为1，灯灭时Y为0。6本题的解题关键在于：不管开关和灯处于什么状态，灯的状态改变当且仅当只有一个开关的状态发生改变。因此，本题有多解。（1）若A=0,B=0时Y=0，则相应真值表设计如下7相应逻辑表达式为用异或门实现8（2）若A=0,B=0时Y=1，则相应真值表设计如下相应逻辑表达式为9用同或门实现10第1章命题逻辑的基本概念内容：命题逻辑研究的是命题的推理演算．这一章介绍命题逻辑的基本概念，包括引入命题联结词，讨论合式公式、重言式以及自然语句的形式化等内容．11命题逻辑的基本概念命题定义：命题是一个非真即假(不可兼)的陈述句．有两层意思，首先命题是一个陈述句，其次真假

4、不可兼．命题的取值称为真值．通常用T表示真值为真，用F表示真值为假．因为只有两种取值，所以这样的命题逻辑称为二值逻辑．12举例说明(1)“雪是白的”是命题，真值为真(2)“雪是黑的”是命题．真值为假(3)“好大的雪啊”不是陈述句，不是命题．(4)“一个偶数可表示成两个素数之和”．是命题，不知真值．(5)“1+101＝110”．是命题，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真值为真．可见，这个命题的真值与所讨论问题的范围(论域)有关．13命题变项命题变项定义：约定用大写字母表示命题，如以P表示“雪是白的”，Q表示“北京是中国的首都”等．当P表示任一命题时，P就称为命题

5、变项(变元)．命题与命题变项区别：命题与命题变项含义是不同的，命题指具体的陈述句，是有确定的真值，而命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值，命题与命题变项像数学中常量与变量的关系一样．在不混淆的情况下，逻辑演算中不再区分它们了。14简单命题和复合命题简单命题定义：简单命题又称原子命题，它是不包含任何的与、或、非一类联结词的命题．如1．1．1中例子．这样的命题不可再分割，如再分割就不是命题了．而像命题“雪是白的而且l+l＝2”，就不是简单命题，它可以分割为“雪是白的”以及“1十1＝2”两个简单命题，联结词是“而且”．命题逻辑与谓词逻辑区别：命

6、题逻辑中将简单命题作为一个不可分的整体来看待．在谓词逻辑里，才对命题中的主谓结构进行深入分析．15复合命题定义：把一个或几个简单命题用联结词(如与、或、非)联结所构成的新的命题称为复合命题．复合命题真值判断：复合命题自然也是陈述句，其真值依赖于构成该复合命题的各简单命题的真值以及联结词，如“张三学英语和李四学日语”就是一个复合命题，由简单命题“张三学英语”“李四学日语”经联结词“和”联结而成，这两个简单命题真值均为真时，该复合命题方为真．16数理逻辑关心什么？不关心内容：这些具体的陈述句的真值究竟为什么是真还是假。关心形式：关心的仅是命题可以被赋予真或假这样的可能性，以及规定了真值后怎样

7、与其他命题发生联系．17命题联结词及真值表联结词可将命题联结起来构成复杂的命题，从而使命题逻辑的内容变得丰富起来。值得注意的是逻辑联结词与日常自然用语中的有关联结词的共同点和不同点．18常用的逻辑联结词称谓、读法、记号：否定词“”是个一元联结词，亦称否定符号，读作非。一个命题P加上否定词就形成了一个新的命题，记作P。否定词的运算规则真值表：1.否定词19PPTFFT真值表描述了命题之间的真值关系，很直观。真值表是命题逻辑里研究