最新离散数学知识点讲课讲稿.docx

学习资料
绪论
研究对象：离散量
研究方法：解的存在性 解的能行性
研究内容：数理逻辑 集合 代数系统 图论 离散概率 组合数学
例题 1、 A、 B、 C、 D 四人参加四次长跑，问： “ A 在 B 前三次， B 在 C 前三次， C 在 D 前三次， D 在 A 前三次”是否有解，若有求出，否则说明理由。
方法一：

A

ABCD

n 个元素的环形排列可拆成

n 个元素的
D

B

BCDA
CDAB
DABC

线性排列
C
方法二：集合
Sa={X|A 在 B 前 }

Sa∩ Sb∩ Sc={A B C D}
Sb={X|B 在

C 前 }

Sa∩ Sb∩ Sd={D A B C}
Sc={X|C 在

D 前 }

Sa∩ Sc∩Sd={C D A B}
Sd={X|D 在

A 前 }

Sb∩ Sc∩Sd={B C D A}
例题 2：在边长为 1 的正方形中任取五个点，则至少有两个点的距离≤√ 2/2。
“中点分隔”将边长为 1 的正方形分成四个
边长为 1/2 的小正方形，从中任取五个小点，
必有两个小点来自一个小正方形。
例题 3：“布鲁英序列” ----应用
精品文档
学习资料
旋转鼓的设计，设旋转鼓有
8 个区域，旋转一圈可识别三位二进制数，如何确定磁粉位置。
（阴影 0，非阴影 1）
0—1—1—1
000
001
0001
0— 1—1—1
010
011
1
0
100
101
1
110
111
1
思考题：四位二进制 a1 a2 a3 a4
例题 4：有五位小姐排成一排，所有小姐姓不同，穿的衣服颜色不同，喝不同的饮料，养不同的宠物，吃不同的水果，已知：

， 穿绿衣服的小姐在喝咖啡





问每位小姐怎么站，她们分别养什么宠物，吃什么水果，喝什么饮料，穿什么颜色衣服，姓什么。
1
2
3
4
5
姓
赵
陈
钱
江
翁
吃
梨
桔子
西瓜
香蕉
苹果
喝
开水
茶
牛奶
咖啡
香槟
精品文档
学习资料
颜色 黄 蓝 红 绿 白
宠物 猫 鱼 鸟 狗
例题 5：同态加密
R+ f:a^x(a>1) R* f(x+y)=f(x)*f(y)
X f(x)
y f(y)
x+y f(x+y)
例题 6:100 被 2、 3、5 任意个整除
A={X| 被 2
整除 }
|A|=[100/
2]=50
2
B={X|被 3
整除 }
|B|=[100/
1
3
3]=33
4
6
5
C={X|被 5
整除 }
|C|=[100/ 5]=20
8
7
|A ∩ B|=16
|A ∩ C|=10
|B ∩ C|=6
|A ∩ B∩C|=3
1:|A|-|A ∩ B|-|A ∩ C|+|A ∩ B∩ C|=27
8:| U|-|A ∪ B∪C|=|U|-(|A|+|B|+|C|-|A ∩B|-|A ∩ C|-
|B ∩