离散数学复习
内容大概有, 集合论, 关系理论, 图论, 排列组合, 近世代数
集合论
集合: 无序, 互异, 确定
集合间的关系
- 被包含关系(子集)
性质:
- 自反性, 任何集合A, 都有A是A的子集 (mathjax还是用不了, 气的昏古七…)
- 传递
- 反对称, 若A是B的子集, B是A的子集, 那么A = B
- 相等关系
性质
- 自反性
- 传递性
- 对称性
- 真包含
性质
- 传递性
特殊集合
全集
全集就是论域空集
- 对于任何集合A, 都有空集是A的子集
- 空集是唯一的
- 幂集
由A的所有子集构成的集合, 称之为A的幂集, 记为P(A)或者2^A
例如,{a, b}的幂集是{空集, {a}, {b}, {a, b}}
集合中元素的个数称作是集合的基数, 记为|A|
对于给定集合A, 如果|A| = n, 则|P(A)| = 2^n
幂集元素编码…这个其实很显然但也很有用
无限集合
等势(~), A, B两个集合, 若在A, B之间存在一一对应的关系, 则称A, B是等势的
若A,B相等, 那么A, B等势…反之不成立
与自然数集合等势的集合，统称可数集合
开区间(0,1)称为不可数集合, 和它等势的都是不可数集合
计数问题
排列组合
鸽巢原理
容斥原理
加法原理算是容斥的特殊情况, 加法原理里涉及到的集合之间是没有交集的…如果有交集, 那这个时候就要用到容斥原理了
计数原理(生产函数)
给定一个数列a0, a1, …, ak,….
设计一个函数G(x) = \sum_{k=0}a_k * x^k
就像是进制表示的感觉..~
感觉这个比较厉害…
例子
有4只不同颜色 (红，黄，蓝，绿)的球，允许在4只球中重复取出r次，并且要求满足：其中的红球至多取到2次、黄球至多取到3次、蓝球和绿球都至多取到1次, 问有多少种取法…?
取不同颜色的球, 积事件
取同一颜色的球, 或者不取或者逐渐增加至上限值, 和事件
所以
用多项式(1+x+x^2)来表示最多取到两次红球事件…其他类似
则
G(x) = (1 + x + x^2) * (1 + x + x^2 + x^3) * (1 + x) * (1 + x)
= 1 + 4x + 8x^2 + 11x^3 + 8x^5 + 4x^6 + x^7
X^6的系数4代表的是…选6次…满足条件的选法有4种..恩, 我觉得OK
关系
关系就是有序元祖的集合..
序偶: 由两个对象(但并不一定是简单元素) x 和 y组成的序列叫做序偶
有序n元组: <<x1, x2, x3, ..., xn-1>, xn>叫做有序n元组, 第一个元素是一个有序n-1元祖
并且能够简单记为<x1, x2, x3, ..., xn>
笛卡尔积: 记为X
- 笛卡尔积满足结合律, 不满足交换律
- 笛卡尔积对于交和并满足那个分配律
约定 A1 X A2 X A3 = (A1 X A2) X A3
A1 X A2 X A3 X A4 = (A1 X A2 X A3 ) X A4 = ((A1 X A2) X A3) X A4
另外有 A X A X A…A = A^n
n元关系算是n元的笛卡尔积的一个…子集…?
函数
函数是一种特殊的关系
一个关系要称为函数, 需要满足
- dom(f) = A
对于任意的x属于A, 存在y属于B, 使得f(x) = y - 单值性
若f(x) = y1,f(x) = y2, 则y1 = y2
函数与一般的关系相比, 有如下的差别:
- 从A到B的关系有
2 ^ (|A| * |B|)个,但A到B的函数只有|B| ^ |A|个 - 关系中序偶的第一个元素可以相同, 而函数则不可以
- 每个函数的基数都是
|A|个(|f| = |A|), 但关系的基数是从零一直到|A| * |B|
也就是说, 序偶中的第一个元素就是出现一次的自变量, 对于每个自变量有|B|种取值, 所以有|B| * |B| * ...共有|A|相乘. 所以就是|B| ^ |A|
也就是说..定义域一定等于A, 但值域不一定等于B, 对吧…值域是B的子集
函数相等条件是
定义域相等, 值域相等 是B相等, 对应关系相等
常用函数
对于一个函数, 若
A = B…而且对于所有的x, 都有f(x) = x, 则叫做恒等函数I_A存在b属于B, 对于所有的x属于A, 都有
f(x) = b, 则称f为常值函数对实数x, f(x)为大于等于x的最小的整数, 则称f(x)为上取整函数, 写法是写个顶
对实数x, f(x)为小于等于x的最小的整数, 则称f(x)为下取整函数, 写法是写个底…这个下取整其实更常用
函数运算
代数系统
这个比较复杂, 计划一下是否继续复习