离散数学之函数和运算纲要

3.1 函数

函数定义

• 在X×Y创造出的序偶集合里, 如果对于所有a∈X集合, 都有唯一的b∈Y集合, 使得<a,b>∈f, 则称f是从X集合到Y集合的一个函数(也叫映射, 在严格的数学理论里, 函数范围更小, 函数限制X集合和Y集合中必须是数, 函数要求f是映上的).
• 函数记作 f: X->Y, x∈X集合称为函数f的变元, y∈Y集合称为变元x在f下的值(象), 记为f(x).
• 注意:
  • D(f) = X, 所有a∈X集合都得有对应的b∈Y集合;
  • 虽然和严格情况下的数学理论有差异, 但是这里我们只要求关系f的值域R(f)是Y的一个子集.
• 底函数 = floor(x); 顶函数 = ceil(x);

特征函数

• A(x) = 1, x∈A; 0, x∉A;
• 空集: A(x)恒等于0;
• 全集E : A(x)恒等于1;
• B包含A: A(x)≤ B(x) 对所有x∈X集合总是成立;
• B集合=A集合: A(x)=B(x) 对所有x∈X集合总成立;
• 集合的交并差补运算:
• A集合∩B集合: A(x)*B(x), 对所有x∈X集合进行运算;
• A集合∪B集合: A(x)+B(x)-A(x)*B(x); 加起来去掉重叠的;
• A集合-B集合: A(x)-A(x)*B(x), A去掉AB都有的,留下自己独有的;
• A集合的补集: 1-A(x),

受限VS扩展

• 受限, 缩小定义域D(f), 扩展, 扩大定义域D(f);
• 若f是从集合X到集合Y的一个函数, 即对所有a∈X都有对应的b∈Y来组成<a,b>序偶, 有一个集合A是X的子集, 则f∩(A×Y), 定义是从A到Y, 显然是f在A上的受限; 假设叫其h, 那么f定义是从X到Y函数, 是对h这样A到Y函数的扩展;

映上=满射, 映内=没满射, 一对一=单射, 一一对应=双射

• 函数f: X->Y 的值域R(f)=Y集合, 是映上/满射; Y真包含了R(f), 那么是映内, 没射满;
• f(a) 总是≠ f(b), 叫做一对一, 单射; 对每个y∈Y都有相互不同的x∈X对应的话, 是一一对应, 也就是说映上且一对一是一一对应;
• 实例化: 如果说全中国的男人和女人数目相等, 且都能配对结婚没人打光棍, 我们说这是双射,一一对应的, 因为从女人X到男人Y的映射, 满足映上(满射, 所有男人m∈Y都有一个女人射向他), 一对一(单射的, 每个女人嫁给了不同的男人, 没有任何两个女人嫁给同一个老公), 所以满足了一一对应, 双射关系;
• 如果说海淀区有个新小区摇号, 每个人最多只能买一套, 那么f: X->Y首先是单射的, 每个房子∈X, 都能有一个不同的买主∈Y来对应, 但是因为房子总是紧张的, 肯定很多人排队也买不到, 所以f也是映内的;

函数的复合运算

• f:X->Y, g:Y->Z, f·g={<x,z>| 存在y∈Y, 使得y=f(x), 且z=g(y)}
• 所以 f·g(x), 就是从g(f(x));
• 服从结合律, 但是必然不满足交换律, 毕竟这里面约定了顺序;

函数f的逆和恒等函数

• f的可逆性: 只有f满足了一一对应, 也就是既要映上(保证Y上每个元素都能对回去), 又得一对一(保证Y上每个元素对回去只对到唯一的一个值), 才能是可逆的, 才有f^(-1)存在, 这是因为函数的X内每个元素都得有对应值;
• 恒等函数: Ix = {<x,x>}称为恒等函数; 也可以写作 f: X->X(f(a)=a总是成立);
• 可逆复合等价恒等性质: 显然, 直观上能明白, 如果f是可逆的, 那么f·f^(-1) = Ix, 因为X->Y->X, 其实X和Y之间是双向箭头, 每个a∈X的箭头最后又指向a自己; f^(-1)·f = Iy, 因为Y->X->Y, 每个b∈Y的箭头最后指回b自己;
• 所以, f:X→Y, g:Y→X, 那么g=f逆 等价于 f·g = Ix 且 g·f = Iy;