离散数学第一章

1、离散数学，教学人民教师：陈荧光莹总学时： 48课每周： 118周2010年9月，指定教材：离散数学，左孝凌，李为监，刘永才编，上海科学技术文献出版社工具书：研究离散数学，耿素云，曲婉玲编离散数学概念，离散数学(Discrete Math )离散量关系的科学离散结构的数学分科(数学) 计算机科学、信息科学、数字科学的数学基础、离散数学的内容研究对象离散量(真假值、自然数、集合、字母、图等)之间的关系和结构具体的内容数学逻辑(sets )组合论(graph )离散数学的应用数学逻辑程序设计、逻辑设置修订、自动智能集合论算法设置修订和分析、编码、数据库代数结构加密、容错分析图修订机科学和应用的各个领

2、域的离散数学为修订机应用专业的大多数课程提供了必要的数学工具，有助于培养我们的抽象思维和逻辑推理能力。 离散数学课程的设置，计算机类核心课程信息类专业必修课程其他类专业的重要选修课程，教学目的和方法，教学目的的目的是通过学习本课程来培养和提高学生的抽象思维能力和逻辑性推理能力。 人民教师方面注意以阐述概念来龙去脉和论证推论的逻辑性严密性为目标的理论的实用化，培养学生解决实际问题的能力。 学生方面要把主观能动性发挥到一盏茶，上课前要尽量预习，在课堂上取得最好的听讲效果，课后要尽量多做练习题，从中理解并掌握相关概念。第一篇数理逻辑、第一章命题逻辑第二章谓词逻辑、第一章命题逻辑、内容命题及其表现法连

3、接词命题式和翻译真值表等价式重言式和包含式其他连接词对偶和正规推论理论、命题及其表现法(1)、命题概念确定真值的记叙文命题的真值总是对于一个确定命题具有“值”的真值是“真”， 只有“假”两种真： t或1假： f或01句用命题判断有木有的关键：1.用记叙文有木有2 .能否确定真值，即真值是唯一的有木有，例1用命题有木有(1)巴黎对法国判断有木有(否，感叹句) (7)你吃饭了吗？ (不，疑问句) (8)我在撒谎(不，残奥船坞)，命题及其表现法(2)，原子命题不能分解为更简单的陈述句称为原子命题复合命题连接词，由标点符号和原子命题复合构成的命题称为复合命题，所有命题都应该有确定的真值(2)李先生在宿

4、舍(1)是原子命题，(2)、(3)是复合命题，我们不能划船行驶的复合命题我是原子命题，命题和其表现法(3)，命题识别符在数理逻辑中，我们使用大写字母a，b，p，q，p :今天下雨。 今天下雨。 A1:今天下雨。 p，12和A1表示命题识别符，命题和其表现法(4)，命题常数如果表示命题识别符确定的命题，则称为命题常数。 命题参数1个命题识别符只表示任意命题的位置标志时，称为命题参数。 命题参数可以表示任意命题，不能确定真值，所以命题参数不是命题。 当命题参数p被特定命题替换时，p可以确定真值。命题参数表示原子命题时，将其参数称为原子参数。 p :今天下雨了q :张三说唱的p和q是命题常数，P1是

5、命题，没有明确表示P1是什么命题，所以P1是命题参数或者分量。连接词、连接词是复合命题中的重要构成部分，用否定提取条件的二条件、否定定义1-2.1否定(Negation ) :“非”、“”表示。 把p作为命题，把p的否定作为新命题，标记为p。 读作“非p”。 P:3的素数P:3不是素数，例如p :北京牌是中国的首都p :北京牌是中国的首都p :天空没有下雨p :天空没有下雨，否定词可以用右表定义。 本表称为p的真值表说明： (1)否定为一元联结词(1)，并且只有在p、q的真值为t作为云同步时，PQ为t，其他情况下，PQ的真值为F P :今天晴天，q :昨天晴天，r :房间10台PQ :今天和昨

6、天都晴天，房间10台明天下雨正在看电视。 PQ的真值表是如右表所示的性质。 (1)PPP(2)pqqp(3)将以下命题编码化： (1)吴颖既学习又聪明；(2)吴颖不仅学习聪明；(3)吴颖聪明，但不学习取连接词的实例，pq，pq，pq，p:张辉是三好生，q:王丽是三好生，取连接词的实例今天下雨，明天下雨，明天下雨，明天下雨，这两天下雨，我们唱歌，跳舞，连接p q他很聪明，但是没有学习。 他不仅聪明，而且用功。 他不是不聪明，而是不学习。 (p) q是表示共现关系的常用语：不仅仅是一边，而且，看and、and、and、and、and等的连接词的话就留心不要马上使用。 张辉和王丽是孪生子。 p:张辉

7、和王丽对孪生子(简单命题)的注意：数学逻辑中两个没有内在联系的命题可以用连接词连接。p :去看电影q :房间里有10张桌子。 正在用逻辑学行政许可。 提取定义1-2.3的两个命题p和q的提取是一个新的复合命题，写作p q，读作p或q，只有当p和q的真值在云同步中为f时，p q是f，其他情况下，p q的真值都是t的例子： (1)P :学生们学过计算机q :学生们学过数学(2) 今晚我在家看电视、去影剧院看电影(3)小李现在在打排球、打男低音的自然语言中，或者有很多了解的PQ的真值表如右表所示的性质： (1) PP (2) pq qp (3) (pq ) RP (QR ) (4) pq (1)对以

8、下命题进行编码： (1) 2或4是素数。(2)小元只能取一个苹果或梨。(3)王小红出生于1975年或一九七九年。提取连接词的实例，解： 2或4是素数。(2)小元只能取一个p:2是素数。 并且，设p的真值为t，q的真值为f时，PQ的真值为f，其他情况下，PQ的真值全部为t，我们将p作为前提或前提，q作为后件或结论例(1)P :雪为黑色，q :太阳从西边升起PQ :雪，那么，给你买新衣服PQ的真值表在自然语言中，对于“如果是那样的话”这个词，前提是假的情况下，不论结论是真是假，这个词的意思大多无法判断。 在数学逻辑中，如果前提是假，则无论结论的真实性如何，PQ的真值都是t。 原因是什么？ 例如，张

9、三对李四说：“去了图书馆一定会借那本书给你。 这个词可以表示命题pq (p表示：张三行图书馆，q表示：张三借那本书)。 后来张三有事没去图书馆，也就是P=F，这时PQ是真的。 我们应该理解为张三说了实话。 也就是说，如果他去图书馆，我们相信他一定会为李四借书。 这种理解也称为善意推断。 解释(1)“(2)前因为f时，条件命题必定是T (3)自然语言，“p的话q”中p和q之间有一定的内在联系，但是在数理逻辑中p和q不一定有相互关系，条件联系的注意： p为假的情况下，PQ总是真的。 如果天气好，我就去玩。 p q一拿到这本小说，我就把它看完。 如果雪是黑色的，太阳就会从西边升起。 p q，条件连接

10、词的实例，我要去旅行。 只有在我有时间的时候。 p:我旅行q:我有时间p q p:不下雨q:我骑自行车上班除非下雨，我骑自行车上班只是p q不下雨，我骑自行车上班。 q p，条件连接词的实例，只要你不努力就不能成功。 只要你不努力，你就不会成功。p:如果p是q的一盏茶条件q是p的必要条件(如果)，则p是p；q是q，所以q p不是q；p不是q，则p不是p；p :冷的王老板是(3)王老板不穿羽绒衣，则不冷；(4)只是冷，而王老板穿羽绒衣；(5)除非冷，则王老板穿羽绒衣的条件连接词实例，pq、pq、qp或pq、qp、pq或qp、pq或qp、qp、条件连接词实例， 如果今天是礼拜日，则给出2=5. (

11、永远为真)的二条件定义1-2.5两个命题p和q，将其复合命题PQ称为二条件命题，读为“p当且只有q”，在p和q的真值相同的情况下，PQ的真值为t，否则PQ的真值为f。 (1)p:2 :两个三角形全等q :两个三角形的三组对应边相等的pq :两个三角形全等，仅这些三组对应边相等(2)P:5 5=10，q :雪为白色的pq:5=10，仅雪为白色的b=0 PQ :a2 b2=0且a=0， 仅b=0 PQ的真值表如右表所示， (1)为二元连接词(2)也同样没有因果对应关系，根据连接词的定义判断命题真值，例如以下的各命题的真值(1)2 2=4当，且3为奇数(2)2 2=4当，且3为奇数(3) 且3不是奇数的情况下，分析命题编码、自然语言被翻译成逻辑式命题编码的步骤(2)使用适当的连结词连结原子命题，构成复合命题的编码形式、命题编码、编码， 句子用命题确定有木有是不需要翻译的.确定句子中的连接词可以对应哪个命题连接词.正确表示原子命题和命题连接词.如果不能用逻辑关系翻译就可以把失败编码化： P:你努力、 q3360只有好好睡一觉失