第一次课绪论与数理逻辑初步

1、10/10/2020,Discrete Math. , Hongzhi Qiao,1,Discrete Mathematics 30课时，15次课 联系方式：,10/10/2020,Discrete Math. , Hongzhi Qiao,2,绪论,离散数学是指计算机科学中所使用的各种离散的数学结构。 结构是指系统中的各个组成部分有机地搭配和排列。 任何事物都有自己的结构。 每一门学科也有自己的结构。,10/10/2020,Discrete Math. , Hongzhi Qiao,3,绪论,1. 人体的结构 人体由大脑、五官、四肢、心、肝、肺等器官所组成。 基本元素是各种细胞。 2. 房屋

2、的结构 房屋由地基、墙、门、窗、地板、房顶等建筑物所组成。 基本材料是砖、瓦、钢筋、水泥、石灰等。 3. 学校的结构 学校由若干院、系、所、处、科室、班级等单位所组成。 基本成员是教师、学生、管理人员、实验人员等。 4. 计算机的结构 计算机由主板、CPU、内存条、硬盘、软驱、电源、机箱、显示器、键盘、鼠标等部件所组成。 基本成员是各种超大规模集成电路芯片。,10/10/2020,Discrete Math. , Hongzhi Qiao,4,绪论,化学的结构 化学主要由无机化学和有机化学所组成。 基本成员是各种化学元素。 物理的结构 物理主要由力学、电学、光学、热学所组成。 基本成员是各种场

3、。 数学的结构 数学主要由连续数学和离散数学所组成。 基本成员是各种集合的元素。,10/10/2020,Discrete Math. , Hongzhi Qiao,5,绪论,1. 离散数学是离散的数学结构的缩写。 2. 离散数学的研究对象是世间一切事物之间的关系。 3. 离散数学所采用的研究方法有集合、代数、图、数理逻辑等。,10/10/2020,Discrete Math. , Hongzhi Qiao,6,离散数学的内容： 数理逻辑（Mathematics Logic) 集合论(Sets) 组合论（Combination) 图论（Graph Theory) 代数结构（Algbra Stru

4、cture) 线性代数(Linear Algbra ) 概率论（Propobility Theory),绪论,10/10/2020,Discrete Math. , Hongzhi Qiao,7,绪论,数理逻辑 计算机是数理逻辑和电子学相结合的产物 集合论 集合：一种重要的数据结构 关系：关系数据库的理论基础 函数：所有计算机语言中不可缺少的一部分 图论 数据结构、操作系统、编译原理、计算机网 络原理的基础 代数系统 计算机编码和纠错码理论 数字逻辑设计基础 计算机使用的各种运算,10/10/2020,Discrete Math. , Hongzhi Qiao,8,18世纪，东普鲁士的哥尼斯堡

5、（现今叫加里宁格勒，在波罗的海南岸）是一座景致迷人的城市，普勒格尔河横贯其境，并在这儿形成两条支流，把整座城市分割成4个区域：河的两岸（A和B），河中的岛（C）和两条支流之间的半岛（D）。当时有七座桥横跨普勒格尔河及其支流，把河岸、半岛和河心岛连接起来。有人在游览时提出这样的问题：能否从某个地方出发，穿过所有的桥各一次后再回到出发点.,Konigsberg七桥问题,绪论,10/10/2020,Discrete Math. , Hongzhi Qiao,9,离散数学课程设置： 计算机系核心课程 信息类专业必修课程 其它类专业的重要选修课程,绪论,10/10/2020,Discrete Math.

6、 , Hongzhi Qiao,10,离散数学的后继课程： 数据结构、编译技术、 算法分析与设计、人工智能、 数据库、,绪论,10/10/2020,Discrete Math. , Hongzhi Qiao,11,教材： 离散数学（第二版） 方世昌 编著 西安电子科技大学出版社出版,绪论,10/10/2020,Discrete Math. , Hongzhi Qiao,12,参考教材： Discrete Mathematics and Its Application (Forth Edition: 1998) Author: Kenneth H. Reson Publisher: McGraw

7、-Hill 机械工业出版社 http:/,绪论,10/10/2020,Discrete Math. , Hongzhi Qiao,13,教学内容:,数理逻辑（Mathematics Logic) 集合论(Sets) 图论（Graph Theory),绪论,10/10/2020,Discrete Math. , Hongzhi Qiao,14,离散数学课程的学习方法: 强调：逻辑性、抽象性； 注重：概念、方法与应用,绪论,10/10/2020,Discrete Math. , Hongzhi Qiao,15,绪论,概念（正确） 必须掌握好离散数学中大量的概念 判断（准确） 根据概念对事物的属性进

8、行判断 推理（可靠） 根据多个判断推出一个新的判断,10/10/2020,Discrete Math. , Hongzhi Qiao,16,第一章 - 数理逻辑,1.1.1 命题逻辑 Proposition Logic,逻辑学： 研究推理的一门学科 数理逻辑： 用数学方法研究推理的一门数学学科,- 一套符号体系 + 一组规则,10/10/2020,Discrete Math. , Hongzhi Qiao,17,数理逻辑的内容： 古典数理逻辑： 命题逻辑、谓词逻辑 现代数理逻辑： 公理化集合论、递归论、模型论、证明论,第一章 - 数理逻辑,10/10/2020,Discrete Math. ,

9、 Hongzhi Qiao,18,命题 Proposition 一个有确定真或假意义的语句.,命题逻辑 Proposition Logic,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,19,命题是一个非真即假（不可兼）的陈述句。有两层意思，首先命题是一个陈述句，而命令句、疑问句和感叹句都不是命题。其次是说这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能不真又不假，也不能又真又假。 凡与事实相符的陈述句为真语句，而与事实不符的陈述句为假语句。,第一章 - 数理逻辑,10/10/2020,Discrete Math. ,

10、 Hongzhi Qiao,20,这就是说，一个命题具有两种可能的取值（又称真值）为真或为假，又只能取其一。通常用大写字母T表示真值为真，用F表示真值为假，有时也可分别用1和0表示它们。 因为只有两种取值，所以这样的命题逻辑也称为二值逻辑。 我们把以这种非真必假的命题作为研究对象的逻辑称为古典逻辑，但也有人反对关于命题的这种观点，认为存在既不真也不假的命题，例如：直觉主义逻辑、多值逻辑等。,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,21,举例：下列句子不是命题。 （1） 8大于12吗？ （2） 请勿吸烟。 （3） X大于Y。 （4）

11、 本页这一行的这句话是假话。,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,22,（1）是一个疑问句，不是陈述句。 （2）是一个祈使句。 （3）是一个不能确定其真假的句子，它可能为真，也可能为假，从而不为命题。在判断一个语句是否是命题时，从语法上就是看他是否是陈述句。但值得注意的是，这里所说的陈述句不包括那些“自指谓”的语句。 （4）这个语句，它的结论是对自身而言的，就是所谓“自指谓”的。这种自指谓的语句往往会产生自相矛盾的结论，即悖论。,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qi

12、ao,23,All the following statements are propositions. 1. Washington, D.C., is the capital of the United States of America. 2. Toronto is the capital of Canada. 3. 1+1=2. 4. 2+2=3.,Propositions 1 and 3 are true, whereas 2 and 4 are false.,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,24,Consider

13、 the following sentences. 1. What time is it? 2. Read this carefully. 3. x+1 =2. 4. x+y = z.,Sentences 1 and 2 are not propositions because they are not statements. Sentences 3 and 4 are not propositions because they are neither true nor false, since the variables in these sentences have not been as

14、signed values. Various ways to form propositions from sentences of this type will be discussed in Section 1.3.,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,25,命题的语句形式 陈述句 非命题语句： 疑问句 命令句 感态句 非命题陈述句：悖论语句,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,26,命题的符号表示： 大小写英文字母：P、Q、R、 p 、q 、r、。 命题

15、真值（Truth Values）的表示： 真：T、1 假：F、0,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,27,命题语句真值确定的几点说明： 1、时间性 2、区域性 3、标准性 命题真值间的关系表示： 真值表（Truth Table),第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,28,Let p be a proposition. The statement It is not the case that p. is another proposition, called

16、 the negation of p. The negation of p is denoted by p. The proposition p is read not p.,p的否定,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,29,Find the negation of the proposition Today is Friday and express this in simple English.,The negation is It is not the case that today is Friday. This n

17、egation can be more simply expressed by Today is not Friday.,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,30,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,31,Let p and q be propositions. The proposition p and q, denoted by pq, is the proposition that is true when both p and q are true a

18、nd is false otherwise. The proposition pq is called the conjunction of p and q. The truth table for pq is shown in Table 2.,p和q的合取,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,32,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,33,Find the conjunction of the propositions p and q where p is

19、 the proposition Today is Friday and q is the proposition It is raining today.,Solution: The conjunction of these propositions, pq, is the proposition Today is Friday and it is raining today. This proposition is true on rainy Fridays and is false on any day that is not a Friday and on Fridays when i

20、t does not rain.,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,34,Let p and q be propositions.The proposition p or q, denoted by pq,is the proposition that is false when p and q are both false and true otherwise. The proposition pq is called the disjunction of p and q. The truth table for pq i

21、s shown in Table 3.,p和q的析取,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,35,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,36,What is the disjunction of the propositions p and q where p and q are the same propositions as in Example 4?,Solution: The disjunction of p and q, p q, is the prop

22、osition Today is Friday or it is raining today. This proposition is true on any day that is either a Friday or a rainy day (including rainy Fridays). It is only false on days that are not Fridays when it also does not rain.,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,37,Let p and q be propos

23、itions.The implication p q is the proposition that is false when p is true and q is false and true otherwise. In this implication p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).,如果p,则q,单条件, 蕴涵 P:前提 Q:结论,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hon

24、gzhi Qiao,38,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,39,“PQ”真假值的这种取法也有人为因素，表现在： （1） 根据PQ真假值取法的定义可以看出，若P为假，不论Q是否为真，则PQ为真。 我们来看 命题：如果月亮从西边出来，则太阳也从西边出来。由定义这是一个真命题，但这使人感到有点不自然，既然月亮不会从西边出来，我们完全可以认为这个命题毫无用处或毫无意义。但是，我们感兴趣的主要是（数学）推理和证明的方法，在这种情况下，命题PQ真的意义在于我们能从P真推出Q真，而没有必要追求从P假能推出什么来。 例如，关于整数的如下命

25、题：对某个实数n，如果n 2，那么n*2 4。这是个真命题，而无须考虑命题变项取什么值。,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,40,（2） 蕴涵词可以连接两个以上意义毫不相干的命题，只要前件和后件满足P ? Q为真的定义所规定的条件，我们便可说“PQ为真”。PQ真假的这种规定也引起了争论。 例如：如果地球停止了转动，则大熊猫产在中国。 但注意到，我们关心的是推理，关心能否从P真推出Q真，不关心各命题之间实际意义是否有联系。,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,

26、41,Find the converse and the contrapositive of the implication If today is Thursday, then I have a test today.,Solution: The converse is If I have a test today, then today is Thursday. And the contrapositive of this implication is If I do not have a test today, then today is not Thursday.,第一章 - 数理逻辑,10/10/2020,Discrete Math. , Hongzhi Qiao,42,Let p and q be propositions, The biconditional p q is the proposition that is true when p and q have the same truth values and is false otherwise. The truth table for p q is shown in Table 6.,P当且仅当q,双条件，等价,第一