4.3逆函数.pdf

离散数学 Discrete Mathematics 4.3逆函数 张晓 西北工业大学计算机学院 zhangxiao@nwpu.edu.cn 201145 4.3.1 逆函数 -1-1 给定一个关系给定一个关系RR,, 颠倒颠倒RR的所有序偶的所有序偶,, 得到逆关系得到逆关系RR--11 .. 给定一个关系给定一个关系RR,, 颠倒颠倒RR的所有序偶的所有序偶,, 得到逆关系得到逆关系RR .. 给定一个函数给定一个函数ff ,, 颠倒颠倒ff 的所有序偶的所有序偶,, 得到的关系却未得到的关系却未 给定一个函数给定一个函数ff ,, 颠倒颠倒ff 的所有序偶的所有序偶,, 得到的关系却未得到的关系却未 必是函数必是函数.. 必是函数必是函数.. 例如例如,, XX =｛｛11,, 2,2, 3｝3｝,, YY =｛｛aa,, bb,, cc｝,｝, 例如例如,, XX ｛｛11,, 22,, 33｝｝,, YY ｛｛aa,, bb,, cc｝｝,, ff =｛｛11,, aa〉,〉, 22,, aa〉,〉, 33,, cc〉｝〉｝是一函数是一函数.而.而 ff ｛｛11,, aa〉〉,, 22,, aa〉〉,, 33,, cc〉〉｝｝是一函数是一函数..而而 f =｛｛aa, 1〉, 1〉, , aa, 2〉, 2〉, , cc, 3〉, 3〉｝｝不是不是从从YY到到XX ｛｛aa, 1, 1〉〉, , aa, 2, 2〉〉, , cc, 3, 3〉〉｝｝不是不是从从YY到到XX 的函数的函数. . 的函数的函数. . 但如果但如果f f 是从是从XX到到YY的双射函数的双射函数, 则定理, 则定理4.3―1说明4.3―1说明 f 但如果但如果f f 是从是从XX到到YY的双射函数的双射函数, , 则定理则定理4.3―14.3―1说明说明 是是YY到到XX的双射函数的双射函数.. 是是YY到到XX的双射函数的双射函数.. 2011110 离散数学 2 定理定理4.3―14.3―1 设f :X→Y是一双射函数, 那么f f 的的 定理定理4.3―14.3―1 f f 的的 逆关系逆关系 f 是一双射函数是一双射函数, :Y→X. 逆关系逆关系 是一双射函数是一双射函数 f 证证 证明思路证明思路：： 证证 证明思路证明思路：： 先证明逆函数是先证明逆函数是YY→→XX的函数的函数，其次证明是满射和单射的，其次证明是满射和单射的。。 先证明逆函数是先证明逆函数是YY→→XX的函数的函数，，其次证明是满射和单射的其次证明是满射和单射的。。 考虑对应于f 和 f 的序偶集合 f = { x ,y |x ∈X ∧ y ∈Y ∧ f (x ) = y } ~ f = { x ,y | x ,y ∈ f } 2011110 离散数学 3 ①因为f是满射的，每一y∈Y出现于一序偶x,y 中，因此， 每一y∈Y 都有y,x ∈ f 再者，因f是单射的，对每一y∈Y，最多有一个x∈X使 x,y ∈ f，因此，仅有一个x∈X使得y,x ∈ 。 f 由