CS02

关于离散数学—计算科学最主要的基础PP88-94，2.4.1构造性数学基础（数理逻辑、代数系统、图论、集合论等）PP101-104，2.5计算科学与数学和其他相关学科的关系2.1数理逻辑•学点逻辑•三段论推理•同一律A，矛盾律A∧～A，排中律A∨～A。•一个哲学家来到一原始的土人部落，被土人抓住。头人说：现在你说一句话，若所说的是真话，则将你带到真神前处死，若所说的是假话，则将你带到假神前处死。•哲学家怎么办？•用数理逻辑方法来分析这一问题A(x):x为真话①B:死在真神前②C:死在假神前③A(x)B④~A(x)C⑤x=“死在假神前”可能：真话∨假话若A(“死在假神前”)├C├~A(“死在假神前”)若~A(“死在假神前”)├B├A(“死在假神前”)非真非假，只能不死。2.1有一逻辑学家，误入某部落，被拘于牢狱。酋长意欲放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可任开一门。为协助你脱逃，今加派两名战士，你可向其中一人提问一次。唯可虑者，此两名战士中，一名天性诚实，一名说谎成性。今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。请问，该逻辑学家是如何发问的？思考题2.2克里克岛是希腊的一个海洋小岛，岛上居住着许多人。这个岛上有一个奇怪的现象，一部分人说假话，另一部分人说真话，令游客大伤脑筋。不过，好在岛上的居民有一个特点，说真话的人从来不说假话，说假话的人从来不说真话。一次，一个游客分别向三个岛上的居民问路后，为了弄清楚谁说的是真话，游客向三个人中的每一个人都提了一个同样的问题：谁是说谎者？结果A答：“B和C都是说谎者”，B答：“A和C都是说谎者”，C答：“A和B至少有一个是说谎者”。试问，游客有没有办法弄清楚谁是说谎者？•“永恒的真理”没有用处–如果天下雨，小李进行室内的各种运动，如单双杠，跳马，吊环，乒乓球等。–如果天不下雨，小李进行室外的各种运动，如足球，长跑，标枪，铁饼等。–现在天或者下雨或者不下雨，小李会做什么？AB,BC,可证AC但：AB∨~(AB)说了等于不说。•矛盾可以推出一切–如果天下雨，小李进行室内的各种运动，如单双杠，跳马，吊环，乒乓球等。–如果天不下雨，小李进行室外的各种运动，如足球，长跑，标枪，铁饼等。–现在天既下雨又不下雨，小李会做什么？2.2集合论•德国数学家康托G.Cantor（1845-1918）创立了集合论，对数学概念作了重要的扩充，对数学基础的研究产生了重大影响，并逐步发展成为数学的重要基础。•概括原则：任给一个性质p,可把所有满足性质P的对象汇集在一起而构成一个集合。用符号表示：G={g|P(g)}–g表示集合G的任一元素–P(g)表示G的元素g具有性质P–{}表示把所有具有性质P的对象g汇集成一个集合•概括原则的另一表达形式(g)(gGP(g))即G的任一元素g必具有性质P，而任一具有性质P的对象必为集合G的元素。–偶数的集合：S1={n|n能被2整除}–S1={2,4,6,8,10,……}–平方数的集合：S2={n|n为自然数的平方}–S2={1,4,9,16,25,36,……}•特征函数–P(g)表示对象g具有性质P，这可用一个谓词来表示，谓词是值域只有两个值（真/假）的函数。我们将P称为集合G的特征函数。–上述两个集合的特征函数是什么？–集合的并、交、补运算对应于特征函数的析取、合取、取反运算。S1∪S2={1,2,4,6,8,9,……}={n|n能被2整除∨n为自然数的平方}S1∩S2={4,16,36,64,……}={n|n能被2整除∧n为自然数的平方}S1={1,3,5,7,……}={n|~(n能被2整除)}•全体大于部分？S0={1,2,3,4,……}S1={2,4,6,8,……}={1×2,2×2,3×2,4×2,……}S2={1,4,9,16,……}={12,22,32,42,……}•理发师悖论–1901年罗素（B.Russell）在集合论概括原则的基础上发现的罗素悖论，从而导致了数学发展史上的第三次危机。–罗素悖论：S={x∣xS}。–理发师悖论一个村庄的理发师宣布了这样一条规定：“给且只给村里所有自己不刮胡子的人刮胡子。”理发师给不给自己刮胡子呢？理发师给自己刮胡子理发师不给自己刮胡子。思考题2.3克里克岛上的真假话判别问题:能不能通过向一个克里克人问一个问题就确定他是不是说假话的人？克里特岛风光2.3图论•哥尼斯堡（Konigsberg）七桥问题寻找走遍7座桥，且只许走过每座桥一次，最后又回到原出发点的路径。北区南区岛区东区•1736年大数学家列昂纳德.欧拉（L.Euler）发表了关于哥尼斯堡七桥问题的论文：“与位置几何有关的一个问题的解”。A岛区B东区C北区D南区•该图将哥尼斯堡七桥问题抽象为一个数学问题：经过图中每边一次且仅一次的回路问题。有这样回路的图称为欧拉图。•图G:(V(G),E(G))，顶点的集合V(G)和边的集合E(G)组成的偶对。•顶点的次数：连到该顶点的边的个数。•对任意一个河道图与任意多座桥，判定可能不可能每座桥恰好走过一次的判定规则：1如果通奇数座桥的地方（即奇次数的顶点）不止两个，满足要求的路线是找不到的。2如果只有两个地方通奇数座桥，可以从这两个地方之一出发找到所要求的路线，但不能回到原地。3如果没有一个地方是通奇数座桥的，则无论从哪里出发所要求的路线都能实现。•欧拉回路是指从图中某顶点出发，经过图中每一条边一次，又回到该顶点的通路。•哈密尔顿回路问题：在某个图G中能不能找到这样的路径，即从一点出发不重复地走过所有的顶点最后又回到原出发点。•图论：对现实问题进行抽象的一个强有力的数学工具。图可以代表：–电路，水网络，通信网络，交通网络，地图等有形的结构。–抽象关系，例如一群人之间的关系网络：点代表人，凡有边相连的两个点表示他们互相认识，否则表示不认识。•应用：计算科学、运筹学、信息论、控制论等学科•随着计算科学的发展，图论在计算科学中的作用越来越大，同时图论本身也得到了充分的发展。思考题2.4在有奇次数顶点的图中，能否有欧拉回路？对图G是否存在欧拉回路，能否给出充分必要条件？2.5对图G是否存在哈密尔顿回路，能否给出充分必要条件？2.6一笔画问题：如何判别一个图能否一笔画出？3.4代数•抽象代数(AbstractAlgebra，近世代数ModernA1gebra)–经典代数(C1assica1A1gebra)：初等代数、高等代数、线性代数，研究对象主要是代数方程和线性方程组。–抽象代数：研究对象是代数系。–代数系：由一个集合和定义在这个集合中的一种运算或若干种运算所构成的一个系统。例：(Z，十)(Z，十，·)。•抽象代数的应用领域：近代物理、近代化学、计算机科学、数字通信、系统工程等，是现代科学技术的数学基础之一。•与抽象代数应用有关的一些实际问题。•例1用n种颜色的珠子做成有m颗珠子的项链，问可做成多少种不同类型的项链?12834567思考题2.7用黑、白2种颜色的珠子做成有5颗珠子的项链，问可以做成多少种不同类型的项链?•随着n与m的增加，用枚举法越来越困难，因而必须寻找更加有效的可解决一般的任意正整数n与m的方法。采用群论方法可完全解决此问题，且至今尚未发现其它更为简单有效的方法。•n=3,m=6时，共有92种不同的项链。•例2分子结构的计数问题–在化学中研究由某几种元素可合成多少种不同物质的问题，由此可以指导人们在大自然中寻找或人工合成这些物质。–在一个苯环上结合H原子或CH3原于团，问可能形成多少种不同的化合物?CCCCCCCH3CH3HHHH•例3正多面体着色问题对一个正多面体的顶点或面用n种颜色进行着色。问有多少种不同的着色方法?用n种颜色对正六面体的面着色，问有多少种不同的着色方法?•首先建立此问题的数学模型设n种颜色的集合为A＝{a1,a2,...,an}，正六面体的面集合为B={b1,b2,b3,b4,b5,b6},则每一种着色法对应一个映射：f：B→A，反之，每一个映射f：B→A对应一种着色法。由于每一个面的颜色有n种选择，所以全部着色法的总数为n6。2.8用2种颜色对正六面体的面着色，问有多少种不同的着色方法?思考题•例4数字通信的可靠性问题–用数字表示信息的方法称为编码。–编码学就是一门研究高效编码方法的学科。–简单检错码一奇偶性检错码用6位二进制码来表示26个英文字母A：000011B：000101C:000110D：001001……E:110101–简单纠错码——重复码设用3位二进制重复码表示A，B两个字母如下：A：000B：111接收的一方对收到的信息码译码如下：接收信息：000001010011l0010111011l译码：AAABABBB•例5几何作图问题–二倍立方体问题作一个立方体使其体积为一已知立方体体积的两倍。–三等分任意角问题给定任意一个角，将其三等分。–圆化方问题给定一个圆，作一个正方形使其面积等于已知圆的面积。–n等分一个圆周。•与代数关系密切的领域有：数据库，形式语言与自动机，人工智能，网络与通信等。•2.9如何用圆规和直尺五等分一个圆周?思考题