东南大学薛晖hxue@seueducn.ppt

东南大学 薛 晖 hxueseu.edu.cn,离散数学,经典问题之一,一逻辑学家误入某部落，被囚于牢狱，酋长欲意放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可任意开启一门。现从两个战士中选择一人负责解答你所提的任何一个问题（Y/N），其中一个天性诚实，一人说谎成性，今后生死任你选择。”逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。逻辑学家应如何发问？,经典问题之二,某汽车司机违章驾驶，交警向他宣布处理决定：“要么扣留驾驶执照三个月，要么罚款1000元。”司机说：“我不同意。”如果司机坚持己见，那么，以下哪项实际上是他必须同意的？ A、扣照但不罚款。 B、罚款但不扣照。 C、既不罚款也不扣照。 D、既罚款又扣照。 E、如果做不到既不罚款也不扣照，那么就必须接受既罚款又扣照。,经典问题之二,某汽车司机违章驾驶，交警向他宣布处理决定：“要么扣留驾驶执照三个月，要么罚款1000元。”司机说：“我不同意。”如果司机坚持己见，那么，以下哪项实际上是他必须同意的？ A、扣照但不罚款。 B、罚款但不扣照。 C、既不罚款也不扣照。 D、既罚款又扣照。 E、如果做不到既不罚款也不扣照，那么就必须接受既罚款又扣照。,数理逻辑与计算机,一切能用数理逻辑抽像出来的逻辑问题，全都可以用计算机程序来解决 罗素和怀海德的巨著数学原理里给出了很多经典数学定理的证明过程，在若干年以后，书中越来越多的定理已能够用计算机程序自动证明出来,数理逻辑与计算机,1959年，美籍华人王浩教授只用9分钟的机器时间，就在计算机上证明了罗素和怀特海数学原理一书中的一阶逻辑部分的全部定理350多条，让罗素惊叹不已,幻方,据传说，大禹在4000多年前就观察到神龟背上的幻方 1977年美国旅行者1 号、2号宇宙飞船就带上了幻方以作为人类智慧的信号,幻方,幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15,幻方,一个n阶幻方是由整数1，2，3，n2按下述方式组成的n×n方阵： 该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数s s - 幻和,幻方,问题：哪些n存在幻方？ 如果有，则构造方法如何？,构造幻方,构造奇数阶幻方的方法： 将1放在最上一行的中间，其后的整数沿着自左下到右上的这条对角线按照自然顺序放置，同时作修正： 在到达顶行时，下一个整数要放在底行，所放位置就是把底行当作顶行上边一行时该数应该放置的位置 当到达最右边的一列时，下一个整数要放在最左边的一列上，所放位置就是把最左边的一列当作最右边那列的右边的列时该数应该放置的位置 当要放的位置上已经填好了整数，或上一个整数已经放在了幻方的右上角时，则当前要摆放的整数将放在紧挨上述位置的下方,Konigsberg七桥问题,在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？,一笔画问题,欧拉于1736年研究并解决了此问题，他把问题归结为“一笔画”问题，证明上述走法是不可能的 连通图可以一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2,中国邮递员问题,邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线? 中国邮递员问题由管梅谷教授在1960年提出，美国国家标准和技术研究院（NIST）首先将此问题命名为中国邮递员问题,中国邮递员问题,假设有一个镇有14条路及9个路口（路口分别编号为 1,2, ,9），如何找到一条最短路线?,欧拉回路,若图中有欧拉回路（图G的一个回路，若它恰通过G中每条边一次 ），则任何一个欧拉回路即为此问题的解 若图中不存在欧拉回路，其中必存在有奇数个边的端点，且这类的端点一定大于2个。因此有些边需要再重复一次，使奇数边的端点变为偶数边的端点,重复边,不存在欧拉回路，其中有4个路口（编号 1, 3, 6 及9）有奇数条路通过 现在要做：在图中使几个边重复，使图中所有的端点均有偶数边通过 问题：确定重复哪个边可以使原图的端点都有偶数边通过，且增加长度最少 ？,选择重复边,画出所有奇数边的端点的完全图 K4 ，边上的数字是从一端点到另一端点的最短长度 选择边 1,6 及 3,9，所有端点都经过一次，而总长度 4 + 2 = 6最短,问题的解,原来的图中，连接端点 1 和 6, 端点 3 和 9 的边再重复一次，所有端点均有偶数个边通过 任一个欧拉路径即为此问题的解答，如以下的端点顺序 1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1 即为一解。图中红色的部份即为重复的边,其它问题,网页推荐 地铁门控制 通讯网络的布局 航空调度和航班的设定 城市的交通管理和交通规划 。,离散数学 Discrete Mathematics,？,什么是离散数学,研究离散量的结构及相互关系的数学科学 离散结构：集合、关系、图等 离散量是指分散开来的、不存在中间值的量 研究对象:有限或可数个元素 自然数、整数，真假值，有限节点等 计算机技术的支撑科学：计算机只能处理离散的或离散化了的数量关系,与其他专业课关系,数据结构基础,离散数学,数据库原理,软件工程,操作系统,编译原理,人工智能,可计算性理论,离散数学的特点,知识点集中，概念和定理多 方法性强 - 构造模型的能力；算法设计的能力； 程序设计的能力 学数学就要做数学,教材及参考书,离散数学 屈婉玲、耿素云、张立昂著，高等教育出版社，2008 Discrete Mathematics and Its Applications（影印版） K.H.Rosen著，机械工业出版社，2003 离散数学 孙吉贵、杨凤杰、欧阳丹彤、李占山著，高等教育出版社，2002 离散数学左孝凌、李为鑑、刘永才编著，上海科学技术文献出版社，1994,课程安排,数理逻辑,集合论,代数结构,图论,课程安排,数理逻辑,集合论,代数结构,图论,数理逻辑,逻辑学分类 辩证逻辑：是研究事物发展的客观规律 形式逻辑：是研究思维的概念、判断和推理的问题 数理逻辑 数理逻辑 数学方法研究形式逻辑的一门科学 一般认为由莱布尼兹（Leibnitz） 率先提出 最基本组成部分：命题演算、谓词演算 应用：逻辑电路、自动控制、人工智能等,主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算,第一部分 数理逻辑,第一章 命题逻辑基本概念,命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值,第一节：命题与联结词,1.1 命题与联结词,命题：具有唯一真值的陈述句 唯一性：或真或假但不能两者都是的 命题所用符号：常用小写个英文字母 例子 十是整数 2100年人类将在月球生活 x=3 现在是几点？ 1+1=2 我现在说假话 我现在说真话,悖论！,1.1 命题与联结词,判断下列语句是否为命题 明天下雨 加拿大是一个国家 x+y4 注： 命题是陈述句，陈述句不一定是命题 命题有唯一真值，但真值可能受范围、时空、环境、判断标准、认识程度限制，一时无法确定,1.1 命题与联结词,命题分类 简单命题：不能被分解成更简单的命题 复合命题：简单命题+联结词 例子 豆沙包是由面粉和红豆做的 今天没有天晴 王华的成绩很好并且品德很好 小李是学数学或者计算机科学 如果天下雨，那么地下湿,1.1 命题与联结词,否定联结词 符号¬,读作“非”，“否定” 定义：命题 p p的否定式：复合命题“p的否定”（“非p”） 符号：p (符号称作否定联结词) p为真当且仅当p为假 例子 今天没有天晴 p：今天天晴,p,1.1 命题与联结词,合取联结词 符号,读作“合取” 定义：命题 p，q p与q的合取式：复合命题“p并且q” 符号：pq(符号称作合取联结词) pq为真当且仅当p和q同时为真 例子 王华的成绩很好并且品德很好 pq p：王华的成绩很好 q：王华的品德很好,1.1 命题与联结词,析取联结词 符号,读作“析取” 定义：命题 p，q p与q的析取式：复合命题“p或q” 符号：pq(符号称作析取联结词) pq为假当且仅当p和q同时为假 例子 小李是学数学或者计算机科学pq p：小李是学数学 q：小李是学计算机科学,1.1 命题与联结词,析取联结词（相容或） “排斥或” 排斥或： 符号 定义：命题 p，q 符号：pq 等价于(pq)(pq) pq为假当且仅当p和q同时为假或 同时为真 例子： 小李在教室看书或在图书馆上网 小李在看书或者听音乐,1.1 命题与联结词,例子 2或3是素数 小元元只能拿一个苹果或一个梨 王小红生于1988年或1989年,1.1 命题与联结词,蕴涵联结词 符号,读作“如果则”、“蕴涵” 定义：命题 p，q p与q的蕴涵式：复合命题“如果p，则q” 符号：pq(符号称作蕴涵联结词) pq为假当且仅当p为真，q为假 例子 如果天下雨，那么地下湿 pq p：天下雨 q：地下湿,1.1 命题与联结词,更多关于蕴含联结词 pq：q是p的必要条件 其他： pq的叙述方式：“只要p，就q”，“因为p，所以q”等 p为假，pq永远为真 如果给我一个支点，我能把 地球撬起来 区别于自然语言的“如果p,则q” p和q有内在联系,1.1 命题与联结词,更多例子 如果天晴，则雪是白的 如果不天晴，则雪是不是白的 由于交通阻塞，他迟到了 如果交通不阻塞，他就不会迟到 他没迟到，所以交通没阻塞 除非交通阻塞，否则他不会迟到 除非他迟到，否则交通没有阻塞 他迟到仅当交通阻塞,1.1 命题与联结词,给定命题pq 它的逆命题qp 它的反命题pq 它的逆反命题 qp 各种命题关系 pq qp qp pq,1.1 命题与联结词,等价式 符号,读作“当且仅当” 定义：命题 p，q p与q的等价式：复合命题“p当且仅当q” 符号：pq(符号称作等价联结词) pq为真当且仅当p与q真值相同 例子 当且仅当2+3=5，才有2是素数 pq p： 2+3=5 q： 2是素数,1.1 命题与联结词,联结词的定义总结,1.1 命题与联结词,联结词的优先级 、 括号最优先 同一优先级：从左到右 例子：求于命题pqr含义相同的命题 (p)q)r (pq)r p(qr) (pqr),1.1 命题与联结词,例： p：北京比天津人口多 q：224 r：乌鸦是白色的 求下列命题真值 (¬p q) (p ¬q) ) r (qr) (p¬r) (¬pr) (p¬r),T,T,F,1.1 命题与联结词,课堂练习：符号化下面命题 小强虽然不聪明，但很用功 小李学过英语或者法语 小李是上海人或者苏州人 金无足赤，人无完人 得道多助，失道寡助,pq,pq,pq,(pq)(pq),pq,1.1 命题与联结词,课堂练习： p：2+3=5 q：大熊猫产在中国 r：太阳从西方升起 求下列命题真值 (r(pq)(pr),T,F,T,F,F,第二节：命题公式及其赋值,1.2 命题公式及其赋值,命题常项：简单命题 命题变项：表示命题的变量 真值可以变化的陈述句 命题变项不是命题 命题变项用确定命题代入才能确定真值 命题所用符号：常用小写个英文字母 命题变量不同于代数式的变量 x+y4的x，y不是命题变量,1.2 命题公式及其赋值,合式公式（命题公式）的递归定义： 单个命题常项或命题变项是合式公式（原子命题公式） A为合式公式，则A是合式公式 A，B为合式公式,则（AB），（ AB）， （AB）， （ AB）为合式公式 4. 有限次应用1-3形成的符号串为合式公式 子公式B：给定合式公式A B是A的一部分 B是合式公式,1.2 命题公式及其赋值,符号说明 大写字母A，B表示合式公式 公式简写法则： 公式最外层括号可以省略 （ A）的括号可以省略 根据运算符优先级省略括号 省略括号不能影响公式解释,1.2 命题公式及其赋值,合式公式的树状展开 (AB)(C)(DC),AB,A,B,(C)(DC),(C),DC,C,D,C,1.2 命题公式及其赋值,例子 (AB)C (pq)(qr) (B) pqr,1.2 命题公式及其赋值,公式层次 若公式A是单个的命题变元，则称A为0层合式 称公式A是n+1(n0)层公式是指下面情况之一： A ¬B，B是n层公式 AB C，其中B，C分别为i层和j层公式，且nmax(i,j) AB C ，其中B，C的层次及n同(b) AB C ，其中B，C的层次及n同(b) AB C ，其中B，C的层次及n同(b) 若公式A的层次为k，则称A是k层公式 层次联结词数,1.2 命题公式及其赋值,例子：p,q,r,s为命题变元 (pq)r)s (pq)(qr) (pqr)s (pqr),4,3,5,1.2 命题公式及其赋值,命题公式的真值 命题变项的常量化：常项替换（解释） 例子：公式pqr 真值为T的解释 p:3是奇数；q:7是奇数；r:3乘7是奇数 真值为F的解释 p:3是奇数；q:7是奇数；r:3乘7是偶数 赋值 命题变项赋真命题命题变项的真值为T 命题变项赋假命题命题变项的真值为F,1.2 命题公式及其赋值,命题变项赋值 A中命题变项：p1,pn 对p1,pn赋值v：v(pi)=i ，i T,F 对A的真值递归定义 v(B)=T iff v(B)=F v(BC)=T iff v(B)=v(C)=T v(BC)=F iff v(B)=v(C)=F v(BC)=F iff v(B)=T，v(C)=F v(BC)=T iff v(B)=v(C) 赋值（解释）简写：1, 2,n n个变项的公式，共有2n个不同赋值,1.2 命题公式及其赋值,命题变项赋值 成真赋值：v(A)=T 成假赋值：v(A)=F 例子：公式(pq)r FFF(p=F,q=F,r=F) TFF?,(pq)r,F,F,F,1.2 命题公式及其赋值,真值表：A所有赋值列成表 真值表构造： 找出A中命题变项：p1,pn 列出2n个赋值（2进制加法形式） 从低到高写成公式各个层次 各个赋值：计算各层的真值,1.2 命题公式及其赋值,例：¬(pq)p),1.2 命题公式及其赋值,例：(p q) (pq¬p¬q),1.2 命题公式及其赋值,命题公式分类：A 重言式(永真式)：v(A)=T，对任意v 矛盾式(永假式)：v(A)=F，对任意v 可满足式：v(A)=T，对某个v 关系 重言式是可满足式，反之不一定成立 真值表判断 重言式：真值表最后一列全为T 矛盾式：真值表最后一列全为F 可满足式：真值表最后一列至少一个T,1.2 命题公式及其赋值,真值表有限性：给定n个命题变项 共有22n个真值表 例题：下列哪些具有相同真值？ pq qp (pq) (pq)p,1.2 命题公式及其赋值,例题,1.2 命题公式及其赋值,例题：下列哪些具有相同真值？ pq p(qr) (pq)(pr)p),1.2 命题公式及其赋值,例题,第一章 习题课,主要内容 命题、真值、简单命题与复合命题、命题符号化 联结词, , , , 及复合命题符号化 命题公式及层次 公式的类型 真值表及应用 基本要求 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 会求复合命题的真值 深刻理解合式公式及重言式、矛盾式、可满足式等 熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型,1. 将下列命题符号化 (1) 苹果树和梨树都是落叶乔木 (2) 王小红和李大明组成一个物理小组 (3) 王小红或李大明是物理组成员 (4) 王小红或李大明中的一人是物理组成员 (5) 只要天冷，小王就穿羽绒服 (6) 因为天冷，所以小王穿羽绒服 (7) 若小王不穿羽绒服，则天不冷 (8) 只有天冷，小王才穿羽绒服 (9) 除非天冷，小王才穿羽绒服 (10)除非小王穿羽绒服，否则天不冷 (11)如果天不冷，则小王不穿羽绒服 (12)小王穿羽绒服当且仅当天冷的时候,练习1,2. 设 p : 2是素数 q : 中国的国土面积比日本大 r : 江苏的省会是无锡 求下面命题的真值 (1) (pq)r (2) (qr)(pr) (3) (qr)(pr) (4) (qp)(pr)(rq),0,练习2,1,0,0,3. 用真值表判断下面公式的类型 (1) pr(qp) (2) (pq) (qp) r (3) (pq) (pr),练习3,练习3解答,(1) pr(qp),矛盾式,练习3解答,(2) (pq) (qp) r,永真式,练习3解答,(3) (pq) (pr),非永真式的可满足式,作业,14 19：（3），（5） 20：（3） 21：（3）,