上图为三阶洛书
组合数学中有许多象幻方这样精巧的结构。 1977年美国旅行者1号、2号宇宙飞船就带 上了幻方以作为人类智慧的信号。
2200BC
4 3 8
9 5 1
2 7 6
神 农 幻 方
1 12 8 13
15世纪 15 14 6 10 3 7 11
4 9 5
４ 阶 幻 方
2 16
实例四：Tiling（阿基米德手稿）问题
27
联结词

否定联结词 否定式p: 非p (p的否定) p 为真当且仅当p为假

合取联结词 合取式pq:p并且q (p与q) pq为真当且仅当p与q同时为真 析取联结词 析取式pq: p或q pq为假当且仅当p与q同时为假
28

联结词(续)
• 排斥或联结词 排斥或p q: p并且非q, 或者q并且非p p q为真当且仅当p与q中一个为真,另一个为假 •蕴涵联结词 蕴涵式pq:如果p,则q pq为假当且仅当 p 为真 q 为假
• 等价联结词 等价式pq:p当且仅当q pq为真当且仅当p与q同时为真或同时为假
29
实例
设p:2是偶数, q:1+1=3, 则 p的真值为 1 ¬ p的真值为 0 q的真值为 0 ¬ q的真值为 1
pq的真值为 0
p¬ q的真值为 1
pq的真值为 0
pq的真值为 1 p¬ q的真值为 1 p q的真值为 1
实例三：哥尼斯堡七桥问题

近代图论的历史可追溯到18世纪的七桥问题— 穿过Königsberg城的七座桥，要求每座桥通过 一次且仅通过一次。
Euler1736年证明了不可能存在这样的路线。

Euler 定理

如果一个图包含一条经过每条边恰好一次的闭途径， 则称这个图为欧拉图。 对任意的非空连通图，若它是欧拉的, 当且仅当它没 有奇度点。

当今数学家借助计算机得出的答案是17152 种拼法，这在当时是相当困难的。
Periodic Tilings
Non-Periodic Tilings
Symmetric Tilings
Penrose Tilings
Symmetric Tilings
实例五：栈排序问题(Knuth, 1960’s)

无尺度网络的一个例子

因特网是一个无尺度 网络，左图的星爆形 结构描绘了从某一测 试站点到其他约十万 个站点的最短连结路 径。图中以相同的颜 色来表示相类似的站 点。
第1章 数学语言与证明方法
本章主要内容

1.1 常用数学符号 ——集合符号、运算符号、逻辑符号

1.2 集合及其运算 1.3 证明方法概述
实例五：无尺度网络问题

20世纪20年代，由Karinthy提出。 1950年， Pool 和 Kochen提出这样一个问题：“两 个毫无关系的人，要让他们互相认识，至少要经过 多少人？”

美国哈佛大学社会心理学家S. Milgram在1967年做 过一项有趣的实验，据说他从内布拉斯加州的奥马 哈随机选了300人，然后请他们每个人尝试寄一封 信到波士顿的一位证券业务员。寄信的规则很简单， 就是任何收信者只能把信寄给自己熟识的人。
离散数学
主讲教师：李向军 南昌大学信息工程学院计算机系
2010年9月
1
教材与教学参考书
教材：
离散数学（第2版） 屈婉玲、耿素云、张立昂 主编 清华大学出版社, 2008.2
教学参考书：
离散数学习题解答与学习指导（第2版）
屈婉玲、耿素云、张立昂 主编
清华大学出版社，2008.2
离散数学是现代数学的一个重要分支。是计算机科学

答案：“猜对的人戴着黑帽子”是真的，所以猜对的人肯定的 说：“我戴的是黑帽子”。
集合论：是研究集合一般性质的数学分支，它的 创始人是康托尔( G, Cantor，1845－1918)。在
现代数学中，每个对象(如数，函数等)本质上都是集合，
都可以用某种集合来定义，数学的各个分支，本质上都 是在研究某一种对象集合的性质。集合论的特点是研究 对象的广泛性，它也是计算机科学与工程的基础理论和 表达工具，而且在程序设计，数据结构，形式语言，关 系数据库，操作系统等都有重要应用。 本课程在第四，五章中介绍集合论中的关系和函数部 分的内容。
图论：是一个古老的数学分支，它起源于游戏难题的
研究。图论的内容十分丰富，应用得相当广泛，许多学
科，诸如运筹学、信息论、控制论、网络理论、博弈论、 化学、生物学、物理学、社会科学、语言学、计算机科 学等，都以图作为工具来解决实际问题和理论问题。随 着计算机科学的发展，图论在以上各学科中的作用越来 越大，同时图论本身也得到了充分的发展。 本课程在第六，七两章中介绍与计算机科学关系密 切的图论的内容。
和一阶谓词逻辑的内容。
实例一：聪明助手问题
著名物理学家爱因斯坦出过如下一道题： 一个土耳其商人，想找一个十分聪明的助手协助他经商，有两 个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个人 带进一间漆黑的屋子里，他打开电灯后说：“这张桌子上有五顶 帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且 把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上 ，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色 的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴 在头上，同时商人将余下的两顶帽子藏了起来接着把电灯打开， 这时那两个应试者看到商人头上戴的是一顶红帽子，过了一会儿 ，其中一个人便喊到：“我戴的是黑帽子。” 请问这个人猜得对吗？是怎么推导出来的？
实例二：理发师悖论（Paradox）
在某个城市中有一位理发师，他的广告词是这样写的：“本人 的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸 的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找 他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是， 有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓 起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮 脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果 他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己 刮脸。 这与由著名数学家伯特兰· 罗素（Russel，1872—1970）提出 的罗素悖论问题相似： 把所有集合分为2类，第一类中的集合以其自身为元素，第 二类中的集合不以自身为元素，假令第一类集合所组成的集合为 P，第二类所组成的集合为Q，于是有P={A∣A∈A}，Q={A∣AA}， 问，Q∈P 还是 Q∈Q？
相关重要结论



“6度分离” —对每个人来说，平均大约只需 要通过６个人就能将信寄到目的地。 研究无尺度网络及其结构，对于防备黑客攻 击、防治流行病、和开发新药等，都具有重 要的意义。 在1999年，Barab´asi et al.发现在因特网上， 任意两个网页间的链接最多为19次。(Nature 401, 1999)
32
重言式,矛盾式与可满足式
重言式(永真式):无成假赋值的命题公式 矛盾式(永假式):无成真赋值的命题公式 可满足式:不是矛盾式的命题公式 例如, A= (pq)(rp)是可满足式, 但不是重言式, B= (pq)(pq)(pq)(pq)是重言式, C= p(pq)(pq)是矛盾式.

Königsberg桥对应的图
组合计数理论：是一个研究离散结构的存在、计数、
分析和优化等问题的数学分支。上世纪60年代以来，随着 计算机的诞生，组合计数理论得到了迅速发展， “为上世 纪计算机革命奠定了基础”，计算机之所以被称之为电脑， 就是因为计算机被人编写了程序，而程序就是算法。算法 运行效率和存储需求分析需要大量的组合计数思想，正是 因为有了组合算法，才使人感到计算机好像是有思维的。 本课程在第八，九和十三章中介绍组合计数理论中的组 合计数基础、容斥原理和递推方程与生成函数等内容。
实例三：幻方问题
我国古代的河洛图(幻方)问题

传说在公元前23世纪大禹 治水的时候，在黄河支流 洛水中，浮现出一个 大乌 龟，甲上背有9种花点的 图案，人们将图案中的花 点数了一下，竞惊奇地发 现9种花点数正巧是1—9 这9个数，各数位置的排 列也相当奇妙，横的3行、 纵的3列以及两对角线上 各自的数字之和都为15。

命题变项:取值为0或1的变元, 也用p,q,r等表示. 命题公式:用联结词和圆括号把命题和命题变项按照一定 规则连接起来的符号串, 常用A,B,C等表示. 例如, A=(pq)(rp)
公式的赋值:对公式中每一个命题变项给定一个值(0或1). 公式的成真赋值:使公式为真的赋值. 公式的成假赋值:使公式为假的赋值. 例如, p=1,q=1,r=1是A的成真赋值, p=0,q=1,r=0是A的成假赋值.
中基础理论的核心课程，为计算机科学提供了有力的理论
基础和工具。离散数学的基本思想、概念和方法广泛地渗 透到计算机科学与技术发展的各个领域，而且其基本理论 和研究成果更是全面而系统地影响和推动着其发展。 离散数学的内容十分丰富，最重要，最核心的是：数理 逻辑、集合论、图论、组合计数理论和代数系统。 本课程将围绕这五个部分相关知识展开介绍。
p¬q的真值为 0
¬ pq的真值为 0 ¬ p¬ q的真值为 1 ¬ p q的真值为 0
30
p ¬ q的真值为 0
¬ p ¬ q的真值为 1
实例(续)
pq的真值为 0 ¬ pq的真值为 1
p¬ q的真值为 1
¬ p¬ q的真值为 1
又设 r:今天是星期一, s:明天是星期二, t:明天是星期三 rs的真值为 1

模式: 对任意一个排列π , 最小的元素用１代 替，次小的元素用２代替……以此类推， 这样得到的排列叫π的模式。 例如 914的模式为：312 37925 的模式为： 24513