The Foundations: Logic and Proofs
基本结构: 集合, 函数,
序列, 求和, 矩阵
Copyright By PowCoder代写 加微信 powcoder
大连东软信息学院/大数据科学系
Section 2.3
定义: 令 A 和 B 是非空集合。
从A 到 B 的函数f, 写成 f : A → B ，是对集合A中每个元素到集合B 中一个元素的一种指派。
写成 f (a) = b ，如果b 是 B 中唯一的一个元素通过函数 f 指派给 A中的元素 a。
函数也称为映射或变换
函数f: A → B 也可由 A×B 的子集(关系)来定义。此子集被限制为一个关系，其中没有两个元素的关系具有相同的第一元素。
函数 f ，对于 A 到 B 的关系, 对于每一个a∈ A，有且仅有一个序偶 (a, b)。
函数可以以不同的方式指定:
f(x) = x + 1
给定一个整数n, 输出第 n个 Fibonacci 数。
为什么下列几个选项中的f不是从R到R的函数？
f(x) = 1/x
f(x) = sqrt(x)
给定 f: A → B
A 是 f 的定义域。
B 是 f 的陪域。
如果 f(a) = b,
那么 b 是a 的像。
f 的值域是 A 中元素的所有像的集合。 也就是 f(A)。
两个函数是相等的，当它们有相同的定义域、陪域，且定义域中的每个元素映射到陪域中相同的元素时。
如果 ，S 是 A 的子集，那么
f {c,d} 是 ?
f {a,b,c,} 是 ?
单射函数Injections
定义: 函数 f 称为是一对一的（one-to-one） , 或者单射函数, 当且仅当 对f 定义域中所有的a 和 b ，f(a) = f(b) 蕴含a = b。
一个函数如果是一对一的，称为单射的。
满射函数Surjections
定义: 函数 f 从 A 到 B 称为映上或者满射, 当且仅当 对每个元素 有元素 使得
函数 f 如果是映上的就称为是满射的。
双射函数 Bijections
定义: 函数 f 是一一对应, 或双射函数, 如果它既是一对一的又是映上的 (单射且满射)。
证明 f 是一对一或者映上的
例 1: 令 f 是从{a,b,c,d } 到 {1,2,3}的函数，
定义 f (a) = 3, f (b) = 2, f (c) = 1, 以及 f (d) = 3 。 f 是映上函数吗?
解: 是, 因为陪域中的所有元素是定义域的像。 如果陪域更改为{1,2,3,4}, f 不是映上的。
证明 f 是一对一或者映上的
例 2: 函数 f (x) = x2 是映上 ? 整数集合到整数集合
解: 不是, 因为不存在整数 x 使得 x2 = −1 。
证明f 是一对一或映上的
要证明f是单射的，证明
要证明f不是单射的，找到
要证明f是满射的，考虑y ，找到 ，s.t. f(x) = y
要证明f不是满射的，找到 , 使得 , 有 f(x) ≠ y
判断下列从{a,b,c,d}到它自身的函数是否是一对一的？
f(a)=b, f(b)=a, f(c)=c, f(d)=d
f(a)=b, f(b)=b, f(c)=d, f(d)=c
f(a)=d, f(b)=b, f(c)=c, f(d)=d
判断下列从Z到Z的函数是否是一对一的？
f(n) = n-1
f(n) = n2+1
判断下列情况下的函数f:Z×Z→Z是否是映上的？
判断下列各是否是从R到R的双射函数？
定义: 令 f 为从集合A 到 B 的双射函数，那么 f 的反函数表示为 , 是从集合B 到 A的函数
f 不是双射的则不存在反函数， 为什么?
令 f 是 {a,b,c} 到 {1,2,3} 的函数，有 f(a) = 2, f(b) = 3, 和 f(c) = 1 。 如果 f 可逆，其反函数是什么?
解: 因为函数 f 是双射的，所以f 是可逆的。
反函数 f–1 (1) = c, f–1 (2) = a, f–1 (3) = b。
令 f: Z Z ，且 f(x) = x + 1 。 如果 f 可逆，其反函数是什么?
解: 函数 f 可逆，因为f 是一一对应的。
反函数 f–1 (y) = y – 1
令 f: R → R 使得 。如果 f 可逆，其反函数是什么?
解: 函数f 不可逆，因为它不是一一对应的。
定义: 令 f: B → C, g: A → B。函数 f 和 g 的合成, 是从 A 到 C 的函数，表示为
例1: 如果 和 , 那么
例 2: 令 g 是从 {a,b,c} 到自身的函数，有 g(a) = b, g(b) = c, g(c) = a。令 f 是从集合{a,b,c} 到{1,2,3} 的函数，有f(a) = 3, f(b) = 2, f(c) = 1 。
f 和 g，g 和 f 的合成分别是什么？
解: f∘g 是 f∘g (a)= f(g(a)) = f(b) = 2
f∘g (b)= f(g(b)) = f(c) = 1
f∘g (c)= f(g(c)) = f(a) = 3
g∘f 是没有定义的，因为 f 的值域不是 g 的定义域的子集。
例 3: 令 f ， g 是从Z到Z的函数，定义 f(x) = 2x + 3 ， g(x) = 3x + 2 。求f∘g ， g∘f ?
f∘g (x)= f(g(x)) = f(3x + 2) = 2(3x + 2) + 3 = 6x + 7
g∘f (x)= g(f(x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11
假定，g是从A到B的函数，f是B到C的函数。
如果f和g均是一对一的函数，那么f∘g 也是一对一函数。
如果f和g均为映上函数，那门f∘g 也是映上函数。
如果f∘g 是映上的，能否得出结论g是映上的？
令 f 为从集合A 到集合 B 的函数。
函数 f 的图是序偶集合{(a,b) | a ∈A 且 f(a) = b}。
f(n) = 2n + 1 从Z 到 Z 的图
f(x) = x2从Z 到 Z 的图
下取整函数 小于或等于 x 的最大整数。
上取整函数 大于或等于 x 的最小整数。
图 (a) 下取整函数 (b) 上取整函数
例: 证明 x 是一实数, 那么 ⌊2x⌋= ⌊x⌋ + ⌊x + 1/2⌋
解: 令 x = n + ε, 其中 n 是一整数，且 0 ≤ ε< 1.
case 1： ε < ½
2x = 2n + 2ε ， ⌊2x⌋ = 2n, 因为 0 ≤ 2ε< 1.
⌊x + 1/2⌋ = n, 因为 x + ½ = n + (1/2 + ε ) ， 0 ≤ ½ +ε < 1.
因此, ⌊2x⌋ = 2n ， ⌊x⌋ + ⌊x + 1/2⌋ = n + n = 2n.
case 2: ε ≥ ½
2x = 2n + 2ε = (2n + 1) +(2ε − 1) ， ⌊2x⌋ =2n + 1, 因为 0 ≤ 2 ε - 1< 1.
⌊x + 1/2⌋ = ⌊ n + (1/2 + ε)⌋ = ⌊ n + 1 + (ε – 1/2)⌋ = n + 1 ，因为 0 ≤ ε – 1/2< 1.
因此, ⌊2x⌋ = 2n + 1 ， ⌊x⌋ + ⌊x + 1/2⌋ = n + (n + 1) = 2n + 1.
定义: f: N → Z+ , f(n) = n! 是前n 个非负整数的乘积。
f(n) = 1 ∙ 2 ∙∙∙ (n – 1) ∙ n, f(0) = 0! = 1
f(1) = 1! = 1
f(2) = 2! = 1 ∙ 2 = 2
f(6) = 6! = 1 ∙ 2 ∙ 3∙ 4∙ 5 ∙ 6 = 720
f(20) = 2,432,902,008,176,640,000.
Stirling’s Formula:
部分函数(optional)
定义: 函数f 被称是从集合 A 到集合 B 的部分函数，如果对A的一个子集中的每个元素 a, 都指派一个唯一的 B 中的b。
集合A的子集 和 B 是 f 的定义域和陪域。
f 是无定义的，对于A 中但不在f 定义域中的元素。
当 f 的定义域等于 A, 就说 f 是全函数。
例: f: N → R ， f(n) = √n 是从Z 到 R 的部分函数，定义域是非负整数。 f 对于负整数是无定义的。
单射, 满射, 双射
下取整、上取整、阶乘函数
部分函数 (optional)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com