离散数学 第一部分：数理逻辑.pptVIP

吉建华，博士，副教授 jjh@3052 科技楼1403 离散数学 主讲：姚璐 hithdyl@126.com 电话S206 引 言 为什么离散数学在计算学科的知识掌握中有着举足轻重的意义呢? ？ 1.离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。离散数学是一门将数学与计算机紧密结合的学科。 2.日后的“数据结构”“线性代数”“概率论”都是与离散数学紧密连接的。 3.离散数学是很多高校考研的必考科目。如，哈工大，北大，北航，大连理工，吉大，山东大学。 前　言 本书一共11章，可略去第5章, 第6章,第11章的内容，略讲第1章, 第2章和第8章的部分内容.其它均为讲解重点。 计划是一个学期讲解《离散数学》, 有: 9周?4学时, 共36学时，包括课后习题的解答。最后一周为总复习。 如果遇到节假日, 可能还会减少2- 4学时. ！时间紧迫，希望大家能课前进行预习。 前　言 有事可以随时离开教室； 请将手机调为震动； 如果铃声真的响了，请不要在课上接电话； 如果实在想接，goto 1 上课要求 课堂要求： 作业要求： 请每人准备一本作业本。共八次作业。 讲课后题时请认真听讲并记录，课后会要求将此总结在作业本上。 考试题型与作业题类似，但决不相同，希望大家认真总结，勿抄袭。 命题联结词 1.否定式与否定联结词“?” 定义: 设p为命题，复合命题 “非p” 称为p的否定式，记作?p，符号?称作否定联结词. 2.合取式与合取联结词“∧” 定义: 设p,q为二命题,复合命题“p并且q”称为p与q的合取式，记作p∧q，∧称作合取联结词. 3.析取式与析取联结词“∨” 定义 设 p,q为二命题，复合命题“p或q”称作p与q的析取 式，记作p∨q，∨称作析取联结词. 例1: 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓既不聪明，也不用功. (3) 王晓虽然聪明，但不用功. (4) 王晓虽然不聪明，但他用功. (5) 王晓考了100分，可能是因为他聪明可能是因为他用功. 解 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) ? p∧?q (3) p∧?q (4) ? p∧q (5) p∨q 联结词与复合命题 定义 设 p,q为二命题，复合命题 “如果p,则q” 称作p与q的蕴涵式，记作p?q，并称p是蕴涵式的前件，q为蕴涵式的后件. ?称作蕴涵联结词. 4.蕴涵式与蕴涵联结词“?” 例2: 设 p:天冷，q:小王穿羽绒服， 将下列命题符号化 (1) 如果天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 如果天不冷，小王就不穿羽绒服. p?q p?q ? p? ? q 联结词与复合命题 定义 设p，q为二命题，复合命题 “p当且仅当q”称作p与q的等价式，记作p?q，?称作等价联结词. 说明: p?q 的逻辑关系:p与q互为充分必要条件 如：两圆面积相等当且仅当它们的半径相等. p:两圆面积相等；q:两圆半径相等 p?q 5.等价式与等价联结词“?” §第二章 一阶逻辑 量词: 表示数量的词 ?＊全称量词?: 表示“任意的”, “所有的”, “一切的” ?x 表示对个体域中所有的个体， ?x F(x)表示个体域中所有的个体都有性质F. 例如：所有的人都要死。x:人类； F（x）：x死。则 ?x F(x)成立。 ＊存在量词?: 表示“存在着”, “有的”, “有一个”，“至少有一个”。 ?x 表示存在个体域中的个体， ?x F(x)表示存在着个体域中的个体具有性质F 例如：有人可以活到100岁。x:人类G(x)：x活到一百岁. 则?x G(x)成立。 例3:A={1,2,3,4} ?x, x∈A, ?y,y ∈B,使x=y成立，求B. B={1,2} (B) B={1,2,3,4,5,6} (C)B={1,2,3,4} (D) B={1} 解:对每个x，x ∈A都至少存在一个y,y ∈B,使x=y，则A ?B 答案为：B，C 例4:A={1,2,3,4} ?x,?y(x∈A∧y∈B)使xy成立，求B. B