《离散数学chapter1_1》由会员分享，可在线阅读，更多相关《离散数学chapter1_1（56页珍藏版）》请在金锄头文库上搜索。
1、1离 散 数 学Discrete Mathematics2教师：张艳联系方式：Tel：13691620716,787675Email: Office: 南区计软大楼1033房间3辞海：研究离散结构的数学分 科。Discrete Math.离散数学研究离散量的结构及其相互关系的数学 学科，是现代数学的一个重要分支。离散的含义是指不同的连接在一起的元素，研究对象一般是有限个或可数个元素。4离散数学的内容：数理逻辑（Mathematics Logic)集合论(Sets)代数结构（Algbra Structure)图论（Graph Theory)组合论（Combination)线性代数(Linear
2、Algbra )概率论（Propobility Theory)5离散数学课程设置：计算机系核心课程信息类专业必修课程其它类专业的重要选修课程6离散数学的后继课程：编译技术、算法分析与设计、人工智能、数据库、操作系统、程序设计语言7开设目的： 通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与研究和开发工作打下坚实的基础。 8离散数学课程的学习方法:强调：逻辑性、抽象性；注重：概念、方法与应用9教材：耿素云、屈婉玲、张立昂离散数学（第五版）清华大学出版社2013年 10上课时间：117周考核：平时：30%（
3、作业+考勤）考试：70%11教学内容:数理逻辑（Mathematics Logic）集合论（Sets）图论（Graph Theory）代数结构（Algebra Structure）组合论（Combination） 离散数学张艳 数理逻辑部分第1章 命题逻辑第2章 一阶逻辑有一个仓库被盗，公安人员经侦察，怀疑甲乙丙丁 四人作案。又经细查，知道这四人中只有两人作 案。 在盗窃案发生的那段时间，可靠的线索有：甲乙两人有且只有一个人去过仓库乙和丁不会同时去仓库丙若去仓库，丁必一同去丁若没去仓库，则甲也没去 试判断到底是哪两个人作案呢？引例：数理逻辑研究中心问题是推理。推理是从前提导出结论的思维过程，前
4、提是指已知 的命题公式，结论是从前提出发应用推理规则推出 的命题公式。第1章 命题逻辑 1.1 命题符号化及联结词1.2 命题公式及分类1.3 等值演算1.4 范式1.5 联结词全功能集1.6 组合电路1.7 推理理论171.1 命题符号化及联结词 n 命题与真值n 原子命题n 复合命题n 联结词 命题与真值 命题: 能判断真假的陈述句(具有唯一真值的陈述句) 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题(判断为正确) 假命题: 真值为假的命题(判断为错误)注意: 感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是 命题 例 下列句子中那些
5、是命题？ (1) 是无理数.(2) 2 + 5 8.(3) x + 5 3.(4) 你有铅笔吗？(5) 这只兔子跑得真快呀！(6) 请不要讲话！(7) 我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)(7)都不是命题命题n判断一个句子是否为命题：首先看它是否为陈述句然后看它的真值是否唯一注意：真值是否唯一与是否知道它的真值是两回事存在外星人案例：聪明的囚徒n古时候有个国王，他自作聪明的做出了一个对处 死囚犯的规定：囚徒可以任意说出一句话，而且 这句话是马上可以验证其真假的。如果囚徒说的 是真话，就绞死，如果说的是假话，就砍头。很 多囚徒要么被绞死，要么被砍头。但有一个聪明 的囚
6、徒，他说了一句巧妙的话，结果使国王既不 能绞死他，也不能砍他头，只好放了他。你知道 这个囚徒说的是什么话么？我被砍头命题的分类 1.简单命题(原子命题)：简单陈述句构成的命题。不能分解为更简单的句子。简单命题符号化 用小写英文字母 p, q, r, ,pi,qi,ri (i1）表示简单命题用“1”表示真，用“0”表示假例如，令p： 是有理数，则 p 的真值为 0q：2 + 5 = 7，则 q 的真值为 1 命题符号化例：将下列命题符号化(1) 深圳不是中国的首都。(2) 张三虽然学习努力但成绩并不优秀。 n由此我们进一步明确指出：原子命题是用肯定语气表达的具有真假意义 的简单陈述句。上述例题中
7、。直接令p表示“深圳不是中国的首 都”。来做符号化，是不符合要求的。在上述第2个命题中，如果简单地用一个符号p 表示“张三虽然学习努力但成绩并不优秀”做符号 化就更不符合符号化的要求了。命题的分类 2. 复合命题：由简单命题与联结词按一定规则复合而成的命题 联结词与复合命题 1.否定式与否定联结词“”定义 设p为命题，复合命题 “非p”（或 “p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p 为真当且仅当p为假。pp0110例：将下列命题符号化。（1）深圳不是中国的首都。联结词与复合命题 2.合取式与合取联结词“”定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为
8、p与q的合取式，记作pq. 称作合取联结词，并规定 pq为真当且仅当p与q同时为真。注意：描述合取式的灵活性与多样性；分清简单命题与复合命题 。pqp q000010100111例：将下列命题符号化(2) 张三虽然学习努力但成绩并不优秀。例： 将下列命题符号化. (1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.解： 令 p：王晓用功，q：王晓聪明，则(1) pq(2) pq(3) qp.例 (续) 令 r : 张辉是三好学生，s :王丽是三好学生(4) rs.(5) 令 t : 张辉与王丽是同学，
9、t 是简单命题 .说明:(1)(4)说明描述合取式的灵活性与多样性.(5) 中“与”联结的是句子的主语成分，因而(5) 中句子是简单命题.联结词与复合命题(续)定义 设 p,q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定pq为假当且仅当p与q同时为假.pqp q000011101111323.析取式与析取联结词“”例：将下列命题符号化。(1) 2或4是素数。(2) 2或3是素数。(3) 4或6是素数。(4) 小元元只能拿一个苹果或一个梨。(5) 王晓红生于1975年或1976年。注意区分相容 或与排斥或解：令 p:2是素数, q:3是素数, r:4是素数,
10、s:6是素数,则 (1), (2), (3) 均为相容或.分别符号化为: pr , pq, rs, 它们的真值分别为 1, 1, 0. 而 (4), (5) 为排斥或.令 t :小元元拿一个苹果，u:小元元拿一个梨，则 (4) 符号化为 (tu) (tu).令v :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (vw)(vw), 又可符号化为 vw , 为什么? 析取联结词n在使用析取联结词时：首先分析表达的是相容或还是排斥或若是相容或，以及p, q不能同时为真的排斥或 ，均可直接符号化为pq的形式联结词与复合命题(续)定义 设 p,q为二命题，复合命题 “如果p,
11、则q” 称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，pq为假当且仅当 p 为真 q 为假.4.蕴涵式与蕴涵联结词“”pqp q001011100111蕴涵联结词npq 的逻辑关系：q 为 p 的必要条件或是p为 q 的充分条件 “如果 p，则 q ” 的不同表述法很多：若 p，就 q只要 p，就 qp 仅当 q只有 q 才 p除非 q, 才 p 或 除非 q, 否则非 p，n注意：当 p 为假时，pq 为真常出现的错误：不分充分与必要条件例：设 p:天冷，q:小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服.(2) 因为天冷，
12、所以小王穿羽绒服.(3) 若小王不穿羽绒服，则天不冷.(4) 只有天冷，小王才穿羽绒服.(5) 除非天冷，小王才穿羽绒服.(6) 除非小王穿羽绒服，否则天不冷.(7) 如果天不冷，则小王不穿羽绒服.(8) 小王穿羽绒服仅当天冷的时候.注意： pq 与 qp 等值（真值相同） pq pq pqpqqp qpqp qp联结词与复合命题(续)定义 设p，q为二命题，复合命题 “p当且仅当q”称作p 与q的等价式，记作pq，称作等价联结词.并 pq规为真当且仅当p与q同时为真或同时为假.说明:(1) pq 的逻辑关系:p与q互为充分必要条件(2) pq为真当且仅当p与q同真或同假5.等价式与等价联结词
13、“”等价联结词pqp q00101010011140例： 求下列复合命题的真值(1) 2 + 2 4 当且仅当 3 + 3 6.(2) 2 + 2 4 当且仅当 3 是偶数.(3) 2 + 2 4 当且仅当 太阳从东方升 起.(4) 2 + 2 4 当且仅当 美国位于非洲.它们的真值分别为 1，0，1，0.联结词与复合命题(续)以上给出了5个联结词：, , , , ，组成一个联结词集合, , , , ，联结词的优先顺序为：, , , , ; 如果出现的联结词同级，又无括号时，则按从左到右的顺序运算; 若遇有括号时，应该先进行括号中的运算。1.2 命题公式及分类命题变项与合式公式 公式的赋值 真
14、值表 命题的分类重言式矛盾式可满足式命题变项与合式公式 命题常项：简单命题命题变项：真值不确定的陈述句命题公式：由命题常项、命题变项、联结词、括号 组成的复合命题命题变项与合式公式 定义：合式公式 (命题公式, 公式) 递归定义：(1) 单个命题常项或变项 p,q,r,pi ,qi ,ri ,0,1是合式公式 (2) 若A是合式公式，则 (A)也是合式公式(3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式(4) 只有有限次地应用(1)(3)形成的符号串才是合 式公式 说明: (A)、 (AB)等的外层括号可以省去 合式公式的层次 定义 (1) 若公式A是单
15、个的命题变项, 则称A为0层公式. (2) 称A是n+1(n0)层公式是指下面情况之一：(a) A=B, B是n层公式；(b) A=BC, 其中B,C分别为i层和j层公式，且n=max(i, j)；(c) A=BC, 其中B,C的层次及n同(b)；(d) A=BC, 其中B,C的层次及n同(b)；(e) A=BC, 其中B,C的层次及n同(b). 合式公式的层次 (续)例如： 公式p 0层p 1层pq 2层(pq)r 3层(pq) r)(rs) 4层公式的赋值 定义： 给公式A中的命题变项 p1, p2, , pn指定 一组真值称为对A的一个赋值或解释 成真赋值: 使公式为真的赋值 成假赋值: 使公式为假的赋值 说明：赋值=12n之间不加标点符号，i=0或1.A中仅出现 p1, p2, , pn，给A赋值12n是 指 p1=1
