《离散数学(第四版)讲义1.doc》由会员分享，可在线阅读，更多相关《离散数学(第四版)讲义1.doc（17页珍藏版）》请在金锄头文库上搜索。
1、引 言Discrete Math. 离散数学 研究离散对象及其相互间关系的一门数学学科。 研究离散结构的数学分支。（辞海）计算机科学、信息科学、数字化科学的数学基础离散数学的内容： 数理逻辑(Mathematics Logic) 集合论(Sets) 代数结构(Algebra Structure) 图论(Graph Theory) 组合论(Combination) 线性代数(Linear Algebra) 概率论(Probability Theory) 与高等数学的区别教学内容：数理逻辑(Mathematics Logic)集合论(Sets)代数结构(Algebra Structure)图论(G
2、raph Theory) 离散数学的由来与发展： 一、古老 历史： 计数：自然数 发展： 图论：Konigsberg七桥问题 二、年青 新生： 计算机：二进制运算离散数学课程设置： 计算机系核心课程 信息类专业必修课程 其它类专业的重要选修课程离散数学的后继课程： 数据结构、编译技术、 算法分析与设计、人工智能、 数据库、离散数学课程的学习方法： 强调：逻辑性、抽象性； 注重：概念、方法与应用参考教材：1、离散数学（耿素云，屈婉玲，北大版）2、离散数学（方世昌，西安电子科大版）3、离散数学结构（第三版、影印版）（Bernard Kolman、Robert C.Busby、Sharon Ross
3、，清华版）4、离散数学提要与范例（阮传概、卢友清，北京广播学院版）第一章 命题逻辑（Proposition Logic）1、命题符号化及联结词2、命题公式及分类3、等值演算4、联结词全功能集5、对偶与范式6、推理理论逻辑学： 研究推理的一门学科数理逻辑： 用数学方法研究推理的一门数学学科 一套符号体系 + 一组规则数理逻辑的内容： 古典数理逻辑： 命题逻辑、谓词逻辑 现代数理逻辑： 逻辑演算、公理化集合论、递归论、模型论、证明论1、命题符号化及联结词命题(Proposition)：一个有确定真或假意义的语句。EXAMPLE 1 下列句子都是命题： 1. 华盛顿是美国的首都。 2. 多伦多是加拿
4、大的首都。 3. 1+1=2。 4. 2+2=3。 命题1和3是真命题，2和4是假命题。EXAMPLE 2 考虑如下句子： 1. 现在几点了？ 2. 认真阅读一下。 3. x+1=2. 4. x+y=z. 句子1和2不是命题，因为它们都不是陈述句。句子3和4不是命题，由于x，y和z的值不确定，使得它们的真值都不唯一。命题的语句形式： 陈述句非命题语句： 疑问句、命令句、感叹句、 非命题陈述句：悖论语句（真值不唯一）命题的符号表示： 大小写英文字母：P、Q、R、 p 、q 、r命题真值(Truth Values)的表示： 真：T、1 假：F、0命题语句真值确定的几点说明： 1、时间性 2、区域性
5、 3、标准性命题真值间的关系表示： 真值表(Truth Table) DEFINITION 1. 设p为任一命题，复合命题“非p”（或“p的否定”）称为p的否定式。记作 p 。 为否定联结词。真值表见Table 1。(Let p be a proposition. The statement “It is not the case that p.” is another proposition, called the negation of p. The negation of p is denoted by p. The proposition p is read “not p.”)p的否定
6、Table 1 Table1：否定命题的真值表pp1001EXAMPLE 3 设p表示“今天是星期五”，则 p表示“今天不是星期五”。显然，当p的真值为0时， p的真值为1。DEFINITION 2. 设p，q为两命题，复合命题“p并且q”（或“p和q”）称作p与q的合取式。记作pq。 为合取联结词。真值表见Table 2。(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 and is f
7、alse otherwise. The proposition pq is called the conjunction of p and q. )p和q的合取Table 2 Table2：两个命题的合取的真值表p qp q0 00 11 01 10001EXAMPLE 4 用p表示命题“今天是星期五”，q表示命题“今天下雨”， 则命题p与q的合取式是什么？解答： p与q的合取式 pq是“今天是星期五，而且今天下雨。”如果是星期五，又下雨，则该命题为真；如果是除星期五外的任意一天，或者虽是星期五但没下雨，则该命题为假。DEFINITION 3. 设p，q为两命题，复合命题“p或q” 称作p与q
8、的析取式。记作pq。为析取联结词。真值表见Table 3。 (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.)p和q的析取Table 3 Table3：两个命题的析取的真值表p qp q0 00 11 01 10111EXAMPLE 5 还
9、是以Example 4 为例，命题p与q的析取式是什么？解答： p与q的析取式 pq是“今天是星期五或今天下雨。”只有今天既不是星期五，又没有下雨，则该命题为假；如果今天是星期五或者今天下雨了（包括下雨的星期五），则该命题就为真。DEFINITION 4. 设p，q为两命题，复合命题“如果p，则q”称作p与q的蕴含式。 记作 pq。称p为蕴含式的前件(hypothesis)，q为蕴含式的后件(conclusion)。称作蕴含联结词。真值表见Table 4。(Let p and q be propositions.The implication pq is the proposition tha
10、t is false when p is true and q is false and true otherwise. )如果p，则q单条件， 蕴涵p：前提 q：结论Table 4 Table4：蕴含式p q的真值表p qp q0 00 11 01 11101EXAMPLE 6 用p表示命题“天下雨”，用q表示命题“我骑自行车上班”，将下列命题符号化： （1）只要不下雨，我就骑自行车上班。 （2）只有不下雨，我才骑自行车上班。解答： （1）中， p是q的充分条件，因而符号化为 pq；（2）中， p是q的必要条件，因而符号化为q p。DEFINITION 5. 设p，q为两命题，复合命题“p当
11、且仅当q”称作p与q的等价式。记作pq，称作等价联结词。真值表见Table 5。(Let p and q be propositions, The biconditional pq is the proposition that is true when p and q have the same truth values and is false otherwise.)p当且仅当q双条件，等价Table 5 Table5：等价式p q的真值表p qp q0 00 11 01 11001EXAMPLE 7 将下一命题符号化： “只有（仅当）你是计算机科学系的学生 (c) 或者你不是新生 (f)
12、，你才可以通过校园网上Internet (a)。”解答： a (cf )EXAMPLE 8 将下一命题符号化：“如果你身高小于4英尺（r），你就不能乘坐过山车（q），除非你超过了16岁（s）。”解答：(1) (r s) q. 如果你身高小于4英尺，而且你不超过16岁，那么你就不能乘坐过山车。(2) s(r q).如果你不超过16岁，那么当你身高小于4英尺时，你就不能乘坐过山车。EXAMPLE 9 “说离散数学是枯燥无味的或毫无价值的，那是不对的。”p：离散数学是有味道的；q：离散数学是有价值的；解答：符号化为：( p q)2、命题公式及分类P、Q、R 称为原子命题(Atomic Proposition)。原子命题或加上逻辑联结词组成的表达式成为复合命题(Compositional Proposition)。从命题常量 到 命题变量(Propositional Variable)命题公式：1. 原子命题是命题公式；2. 设P是命题公式，则P也是命题公式；3. 设P、Q是命题公式，则 (PQ)、(PQ)、(PQ)、(P Q) 也是命题公式；4. 有限次地使用1、2、3
