同构映射的定义同构映射的定义
§6.8 线性空间的同构一、
同构映射的定义
一、同构映射的定义
二、同构的有关结论
我们知道，在数域P 上的n 维线性空间V 中取定一组基后，V 中每一个向量有唯一确定的坐标向量的坐标是P 上的n 元数组，因此属于P n . 这样一来，取定了V 的一组基对于V 中每一个向量，令在这组基下的坐标与对应，就得到V 到P n 的一个单射
反过来，对于P n 中的任一元素是V 中唯一确定的元素，并且即也是满射.因此，
是V 到P n 的一一对应.引入12(,,,),n a a a L α12,,,,n εεεL αα12(,,,)n a a a L α12:,(,,,)
n n V P a a a σα→a L 12(,,,),
n a a a L 1122n n
a a a αεεε=+++L 12()(,,,),
n a a a σα=L σσ
这个对应的重要必性表现在它与运算的关系上.任取设
,,V αβ∈12()(,,,)n b b b σβ=L 1122,n n a a a αεεε=+++L 1122n n b b b βεεε=+++L 12()(,,),n a a a σα=L 则1122()(,,)
n n a b a b a b σαβ+=+++L 12()(,,)n k ka ka ka k P
σα=?∈L 归结为它们的坐标的运算.
这就是说，向量用坐标表示后，它们的运算可以1212(,,)(,,,)()()n n a a a b b b σασβ=+=+L L 12(,,)(),
n k a a a k σα==L 从而
一、同构映射的定义
设都是数域P 上的线性空间，如果映射,V V ′具有以下性质：
V V σ′→：则称的一个同构映射，并称线性空间V V σ′是到同构，记作V V ′与.
V V ′?ii) ()()(),
,V σαβσασβαβ+=+?∈iii) ()(),,k k k P V
σασαα=?∈?∈i) 为双射
σ
为V 的一组基，则前面V 到P n 的一一对应
例1 V 为数域P 上的n 维线性空间，12,,,n εεεL :,
n
V P σ→12(,,,)n a a a αa L V α?∈这里为在基下的坐标，α12(,,,)n a a a L 12,,,n εεεL 就是一个V 到P n 的同构映射，所以.n
V P ?
1 数域P 上任一n 维线性空间都与P n 同构.
二、同构的有关结论
同构映射，则有
()()()00,.
σσασα=?=?1）2 设是数域P 上的线性空间，
的V V σ′是到,V V ′2）1122()
r r k k k σααα+++L 1122()()(),
r r k k k σασασα=+++L ,,1,2,,.
i i V k P i r α∈∈=L
线性相关（线性无关）.
3）V 中向量组线性相关（线性无关）12,,,r αααL 的充要条件是它们的象12(),(),,()r σασασαL 4）dim dim .
V V ′=5）的逆映射为的同构映射.
V V σ′→：1σ?V V ′到是的子空间，且V ′dim dim ().
W W σ=(){()}
W W σσαα=∈6）若W 是V 的子空间，则W 在下的象集
σ
中分别取即得
01,k k ==?与()()()
00,σσασα=?=?证：1）在同构映射定义的条件iii)()()k k σασα=2）这是同构映射定义中条件ii)与iii)结合的结果.
3）因为由11220
r r k k k ααα+++=L 可得1122()()()0
r r k k k σασασα+++=L 反过来，由1122()()()0r r k k k σασασα+++=L 可得1122()0.
r r k k k σααα+++=L
而是一一对应，只有σ(0)0.
σ=所以可得11220.
r r k k k ααα+++=L 因此，
线性相关（线性无关）12,,,r αααL 12(),(),,()r σασασα?L 线性相关（线性无关）.
4）设为V 中任意一组基.
12,d ,,im ,n V n εεε=L 由2）3）知，
为的一组基.σ12(),(),,()n σεσεσεL 所以dim dim .
V n V ′==
11(())()σσαβσσαβαβ??′′′′′′
+=+=+o 任取,,V αβ′′′∈11,,V V I I σσ
σσ??′==o o I 为恒等变换.1111()()(())(())σσασσβσσασσβ????′′′′=+=+o o 11(()())
σσασβ??′′=+5）首先是1－1对应，并且
1:V V σ?′→同理，有11()(),
,k k V k P
σασαα??′′′′=?∈?∈所以，为的同构映射.1σ?V V ′到σ再由是单射，有111()()()σαβσασβ???′′′′+=+σ
6）首先，()()W V V σσ′
?=()()(),W W σσσ∈∴≠?
Q 且0=0其次，对有W 中的向量(),,W αβσ′′?∈,αβ使()(),.
σαασββ′′==于是有()()()
αβσασβσαβ′′+=+=+()(),k k k k P
ασασα′==?∈由于W 为子空间，所以,.W k W αβα+∈∈从而有()(),.
W k W αβσασ′′′+∈∈
由2可知，同构映射保持零元、负元、线性组合dim dim ().
W W σ=故所以是的子空间.
V ′()W σ()
W W σ?显然，也为W 到的同构映射，即
()W σσ注及线性相关性，并且同构映射把子空间映成子空间.
证：设为线性空间的同构,:V V V V στ′′′′→→：3 两个同构映射的乘积还是同构映射.
()()()()
τσαβτσασβ+=+o ()()()()()()τσατσβτσατσβ=+=+o o ()()()()()
k k k τσατσατσα==o ()()()
k k τσατσα==o 任取,,V k P αβ∈∈，有
映射，则乘积是的1－1对应.V V ′′到τσo 所以，乘积是的同构映射.
V V ′′到τσo
同构关系具有：
反身性：对称性：传递性：注
,V V V V V V σττσ′′′′′′????o V
I V V
?1V V V V
σσ?′′???
4 数域P 上的两个有限维线性空间同构12,V V 12dim dim .
V V ?=证：""?""?若由性质2之4）即得
12,V V ?12dim dim .
V V =（法一）若12dim dim ,
V V =12.
V V ∴?由性质1，有12,n n
V P V P ??
设分别为V 1,V 2的一组基.1221,,;,,n n e e e εεεL L 定义使
12:,V V σ→11221,
n n a a a V αεεε?=+++∈L 1122()n n
a e a e a e σα=+++L 则就是V 1到V 2的一个映射.
σ（法二：构造同构映射）
""?又任取设11,,n n
i i i i i i a b αεβε====∑∑1,,V αβ∈1,2,,,i n =L 从而，所以是单射.
.αβ=σ若即
则()(),σασβ=11,n n i i i i i i a e b e ===∑∑,
i i a b =
任取设2,V α′∈1,
n
i i i a e α=′=∑所以是满射.
σ再由的定义，有σ(),1,2,,i i e i n σε==L ()()(),
σαβσασβ+=+()(),
k k σασα=易证，对有
1,,k P V αβ??∈∈12.
V V ?所以是V 1到V 2的一个同构映射，故σ则有使11,n i i i a V αε==∈∑().
σαα′=
例2 把复数域看成实数域R 上的线性空间，证法一：证维数相等
证明：2
C R ?首先，
可表成1,,x a bi a b R =+∈,x C x ?∈其次，若则0.
a bi a
b =1+=0,=所以，1，i 为C 的一组基，dim 2.
C =又，2dim 2
R =2dim dim .C R =所以，12.
V V ?故，
证法二构造同构映射
则为C 到R 2的一个同构映射.
σ作对应()()2
:,,.C R a bi a b σσ→+=作成实数域R 上的线性空间.
把实数域R 看成是自身上的线性空间.
,k
a b ab k a a
⊕==o 例3 全体正实数R +关于加法⊕与数量乘法：
o 证明：并写出一个同构映射. ,R R +?
证作对应():,ln ,R R a a a R σσ++→=?∈易证为的1－1对应.σR R +
到且对有
,,,a b R k R +?∈?∈()()()()ln ln ln a b ab ab a b a b σσσσ⊕===+=+()()()ln ln k
k k a a a k a k a σσσ====o 所以，为的同构映射.σR R +到故.R R +?方法二作对应():,,x R R x e x R ττ+→=?∈易证：为的1－1对应，而且也为同构映射.
R R +到τ事实上，为的逆同构映射.
τσ
映射基础知识
映射基础知识 一、映射 1.映射概念 定义设X、Y是两个非空集合,如果存在一个法则f,使得对X中每个元素 x,按法则f,在Y中有唯一确定的元素y与之对应,么称f为从X到Y的映射, 记作 f:x→y, 其中y称为元素x(在映射/下)的像,并记作f(x),即 y=f(x), 而元素x称为元素y(在映射f下)的一个原像;集合X称为映射f的定义域,记 作D,即D=X;X中所有元素的像所组成的集合称为映射f的值域,记作R或 f(X),即 R=f(X)=f(x)lx∈X 从上述映射的定义中,需要注意的是: (1)构成一个映射必须具备以下三个要素:集合X,即定义域D=X;集合 Y,即值域的范围:R,Cy;对应法则f,使对每个x∈X,有唯一确定的y= f(x)与之对应 (2)对每个x∈X,元素x的像y是唯一的;而对每个y∈R,元素y的原像不 一定是唯一的;映射f的值域R是Y的一个子集,即Rcy,不一定R=y 2.逆映射与复合映射 设f是X到Y的单射,则由定义,对每个y∈R,有唯一的x∈X,适合 f(x)=y.于是,我们可定义一个从R到X的新映射g,即 g:R→X, 对每个y∈R,规定g(y)=x,这x满足f(x)=y个映射g称为f的逆映射,记作f, 其定义域D=R,值域R=X. 按上述定义,只有单射才存在逆映射.所以在例1、例2、例3中,只有例3 中的映射f才存在逆映射f,这个就是反正弦函数的主值 f'(x)=arcsin x, x [-1 1], 其定义域D=[-1,1],值域R=- 设有两个映射 g:X→y1， f:2→z, 其中Y1CY2,则由映射g和f可以定出一个从X到Z的对应法则,它将每个 x∈X映成fg(x)]∈Z.显然,这个对应法则确定了一个从X到Z的映射,这个 映射称为映射g和f构成的复合映射,记作fg,即 fg:→z,(fg)(x)=fg(x)],x∈X. 由复合映射的定义可知,映射g和f构成复合映射的条件是:g的值域R必 须包含在f的定义域内,即RCD否则,不能构成复合映射.由此可以知道,映 射g和f的复合是有顺序的,fg有意义并不表示gf也有意义即使 fg与gf都有意义,复合映射fg与gf也未必相同。
离散数学考试题
离散数学测试题 一．选择题（10*2） 1.设L (x )：x 是演员，J (y )：y 是老师，A (x ,y )：x 佩服y. 那么命题“所有演员都佩服某些老 师”符号化为( ) (A) ),()(y x A x xL →? (B) ))),()(()((y x A y J y x L x ∧?→? (C) )),()()((y x A y J x L y x ∧∧?? (D) )),()()((y x A y J x L y x →∧?? 2.令F(x):x 是有理数，G(x):x 是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为 （ ） A.?x(F(x)∧G(x))∧?x(G(x)→?F(x)) B.?x(F(x)→G(x))∧?x(G(x)∧?F(x)) C.?x(F(x)∧G(x))∧?x(G(x)∧?F(x)) D.?x(F(x)→G(x))∧?x(G(x)→?F(x)) 3．设R 是集合A={a,b,c,d}上的二元关系， R={
第2讲函数与映射的概念复习.docx
第2讲函数与映射的概念 ★知识梳理 1.函数的概念 (1)函数的定义：设A、B是两个非空的数集,如果按照某种对应法则于，对于集合A中的每一个数x ,在集合B中都冇唯一确定的数和它对应,那么这样的对应叫做从4到B的一个函数，通常记为y = /(x),x G A (2)函数的定义域、值域 在函数y = /(x),x G A中，x叫做口变量，x的取值范碉A叫做y = /0)的定义域；与x的值和对应的y值叫做函数值，函数值的集介｛f(x)卜e A｝称为函数y = f(x)的值域。 (2)函数的三要素：定义域、值域和对应法则 2.映射的概念:设A、B是两个集合，如果按照某种对应法则/,对于集合A中的任意元素，在集合B小都有唯-确泄的元素与Z对应,那么这样的单值对应叫做从A到B的映射，通常记为f : A — B ★重、难点突破 重点：掌握映射的概念、函数的概念，会求函数的定义域、值域 难点：求函数的值域和求抽象两数的定义域 重难点：1?关于抽象函数的定义域 求抽象函数的定义域，如果没冇弄清所给函数Z间的关系，求解容易出错误问题1：已知函数y = /(x)的定义域为[a, b],求y = /(x + 2)的定义域. 问题2：己知y = /(x + 2)的定义域是[d, b],求函数y = f (x)的定义域. 1.求值域的几种常用方法 (1 )配方法：对于(可化为)'、二次函数型〃的函数常用配方法，如求函数y = -sin2兀一2cosx + 4, 变为y = - sin? x-2cosx + 4 = (cosx-1)2 + 2解决. (2)基本函数法：一些由基木函数复合而成的函数可以利用基本函数的值域来求，如函数y = log j (-x2 + 2x + 3)就是利用函数y = log丨u和u = -x2 + 2兀+ 3的值域来求. 2 2 2JC + 1 (3)判别式法：通过对二次方程的实根的判别求值域。如求函数/ 的值域 兀'―2兀+ 2 山)，=严+1得y/—2(y + i)x + 2y — l = 0,若y = 0 ,则得 % = 所以y = 0 x - 2x + 2 2 是函数值域中的一个值；若y ^0 ,则由△ = [—2(y + l)『—4y(2y —1)? 0得
图同构问题综述
图同构问题综述 数据科学与计算机学院 黄**1******3 2016.05.26
1概述 芝加哥大学计算机科学教授LászlóBabai在2015年11月宣布了一个能在拟多项式时间内解决图同构问题的新算法，该算法还有待进一步审查以确定其正确性.如果最终被证明是正确的，那么这将是计算机理论领域的一项非常重要的成果. 图的同构问题可以分为四类：精确图同构问题、精确子图同构问题、不精确图同构问题和不精确子图同构问题.其中后三个问题已经被证明是NP完全问题，而对于精确图同构问题的复杂性问题，目前还没有明确的结果，即尚不清楚它是P问题还是NP完全问题，但至少知道它是NP问题. 本文是图同构问题的一个综述，首先给出图同构问题的定义，接着介绍了图同构问题判定算法的研究现状和应用，最后介绍一些具体的判定算法. 2图同构的概念 一个图可以存在多种不同的形式，这些不同形式的图都具有相同数目的顶点、边，而且边还具有相同的连接性.这些不同形式的图就是同构. 直观上地说，如果两个图G1和G2有相同数目的顶点和边，并且边的连接性也相同，那么就说这两个图是同构的.我们可以把一个图看做是另一个图经过扭曲得到的.下面给出图同构的严格定义. 给定两个无向简单图G和H，如果存在一个双射f:V(G)→V(H)，使得对于任意的u,v∈V(G)，有?u,v?∈E(G)当且仅当?f(u),f(v)?∈E(V)，则称图G和H是同构的，记为G?H. 如果G1?G2，那么： (1)|V(G1)|=|V(G2)|. (2)|E(G1)|=|E(G2)|. (3)G1和G2的度序列相同. (4)如果{v1,v2,...,v k}是G1的长度为k的圈，那么{f(v1),f(v2),...,f(v k)}是G2长 度为k的圈. 上述的条件是两个图G1和G2同构的必要条件，下面给出几个充分条件： (1)G1?G2当且仅当G1?G2，其中G1和G2都是简单图. (2)G1?G2如果它们有相同的邻接矩阵. (3)G1?G2当且仅当它们相应的子图也同构.
映射详解(经典)
课题：§1.2.2映射 教学目的：（1）了解映射的概念及表示方法，了解象、原象的概念； （2）结合简单的对应图示，了解一一映射的概念． 教学重点：映射的概念． 教学难点：映射的概念． 教学过程： 一、引入课题 复习初中已经遇到过的对应： 1．对于任何一个实数a，数轴上都有唯一的点P和它对应； 2．对于坐标平面内任何一个点A，都有唯一的有序实数对(x,y)和它对应； 3．对于任意一个三角形，都有唯一确定的面积和它对应； 4．某影院的某场电影的每一张电影票有唯一确定的座位与它对应； 5．函数的概念． 二、新课教学 1．我们已经知道，函数是建立在两个非空数集间的一种对应，若将其中的条件“非空数集”弱化为“任意两个非空集合”，按照某种法则可以建立起更为普通的元素之间的对应关系，这种的对应就叫映射（mapping）（板书课题）． 2．先看几个例子，两个集合A、B的元素之间的一些对应关系 （1）开平方； （2）求正弦 （3）求平方； （4）乘以2； 3．什么叫做映射？ 一般地，设A、B是两个非空的集合，如果按某一个确定的对应法则f，使对于集合A中的任意一个元素x，在集合B中都有唯一确定的元素y与之对应，那么就称对应f：A→B为从集合A到集合B的一个映射（mapping）． 记作“f：A→B” 说明： （1）这两个集合有先后顺序，A到B的射与B到A的映射是截然不同的．其
中f表示具体的对应法则，可以用汉字叙述． （2）“都有唯一”什么意思？ 包含两层意思：一是必有一个；二是只有一个，也就是说有且只有一个的意思。4．例题分析：下列哪些对应是从集合A到集合B的映射？ （1）A={P | P是数轴上的点}，B=R，对应关系f：数轴上的点与它所代表的实数对应； （2）A={ P | P是平面直角体系中的点}，B={（x，y）| x∈R，y∈R}，对应关系f：平面直角体系中的点与它的坐标对应； （3）A={三角形}，B={x | x是圆}，对应关系f：每一个三角形都对应它的内切圆； （4）A={x | x是新华中学的班级}，B={x | x是新华中学的学生}，对应关系f：每一个班级都对应班里的学生． 思考： 将（3）中的对应关系f改为：每一个圆都对应它的内接三角形；（4）中的对应关系f改为：每一个学生都对应他的班级，那么对应f：B A是从集合B到集合A的映射吗？ 5．完成课本练习 三、作业布置 补充习题
5种图同构算法的比较
A Performance Comparison of Five Algorithms for Graph Isomorphism P. Foggia, C.Sansone, M. Vento Dipartimento di Informatica e Sistemistica Via Claudio, 21 - I 80125 - Napoli, Italy {foggiapa, carlosan, vento}@unina.it Abstract Despite the significant number of isomorphism algorithms presented in the literature, till now no efforts have been done for characterizing their performance. Consequently, it is not clear how the behavior of those algorithms varies as the type and the size of the graphs to be matched varies in case of real applications. In this paper we present a benchmarking activity for characterizing the performance of a bunch of algorithms for exact graph isomorphism. To this purpose we use a large database containing 10,000 couples of isomorphic graphs with different topologies (regular graphs, randomly connected graphs, bounded valence graph), enriched with suitably modified versions of them for simulating distortions occurring in real cases. The size of the considered graphs ranges from a few nodes to about 1000 nodes. 1. Introduction The exact graph matching problem is of interest in a variety of different pattern recognition contexts. In fact, graphs are used to support structural descriptions as well as for low level image representations. As it is well known, among the different types of graph matching algorithms, subgraph isomorphism is a NP-complete problem [10], while it is still an open question if also graph isomorphism is a NP-complete problem. So, time requirements of brute force matching algorithms (either in case of isomorphism or subgraph isomorphism) increase exponentially with the size of the input graphs, restricting the applicability of graph based techniques to problems implying graphs with a small number of nodes and edges. During the last decades significant research efforts have been devoted to improve performances of the matching algorithms, both in terms of computational time and memory requirements. Some algorithms reduce the computational complexity of the matching process by imposing topological restrictions on the graphs [1, 11, 14, 22] An alternative approach for reducing the matching complexity is that of using an adequate representation of the searching process and pruning unprofitable paths in the search space. In this way, no restrictions must be imposed on the structure of the
函数与映射的概念及其表示方法
函数与映射的概念 ★知识梳理 1．函数的概念 (1)函数的定义： 设B A 、是两个非空的数集，如果按照某种对应法则f ，对于集合A 中的每一个数x ，在集合B 中都有唯一确定的数和它对应，那么这样的对应叫做从A 到B 的一个函数，通常记为A x x f y ∈=),( (2)函数的定义域、值域 在函数A x x f y ∈=),(中，x 叫做自变量，x 的取值范围A 叫做)(x f y =的定义域；与x 的值相对应的y 值叫做函数值，函数值的集合{} A x x f ∈)(称为函数)(x f y =的值域。 (2)函数的三要素：定义域、值域和对应法则 2．映射的概念 设B A 、是两个集合，如果按照某种对应法则f ，对于集合A 中的任意元素，在集合B 中都有唯一确定的元素与之对应，那么这样的单值对应叫做从A 到B 的映射，通常记为 B A f →: ★重、难点突破 重点：掌握映射的概念、函数的概念，会求函数的定义域、值域 难点：求函数的值域和求抽象函数的定义域 重难点：1．关于抽象函数的定义域 求抽象函数的定义域，如果没有弄清所给函数之间的关系，求解容易出错误 问题1：已知函数)(x f y =的定义域为][b a ，，求)2(+=x f y 的定义域 [误解]因为函数)(x f y =的定义域为][b a ，，所以b x a ≤≤，从而222+≤+≤+b x a 故)2(+=x f y 的定义域是]2,2[++b a [正解]因为)(x f y =的定义域为][b a ，，所以在函数)2(+=x f y 中，b x a ≤+≤2， 从而22-≤≤-b x a ，故)2(+=x f y 的定义域是]2,2[--b a 即本题的实质是求b x a ≤+≤2中x 的范围 问题2：已知)2(+=x f y 的定义域是][b a ，，求函数)(x f y =的定义域 [误解]因为函数)2(+=x f y 的定义域是][b a ，，所以得到b x a ≤+≤2，从而
华东交通大学离散数学考试试卷整理版
华东交通大学 离散数学 期考试卷（一） （ A ）卷 课程名称： 离散数学 课程类别：必、限、任 考试方式：闭卷（√）、开卷(范围)（ ）： 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人签名 题分 20 30 8 7 5 8 7 7 8 100 得分 考生注意事项：1、本试卷共 8 页，总分 100 分，考试时间 120 分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 一、 填空题(每小题2分，共20分) 1、集合A = {{1}, {2, 3}}，则P (A )＝_________________________________。 2、集合A = {a , b }，则笛卡儿积A ?A ＝_______________________________。 3、设A ={1, 2, 3}，G =
为群，其中⊕为集合的对称差运算，那么方程{1, 2, 3} ⊕ X = {1, 2}的解是_______________________________________________________________。 4、在一阶逻辑中，“有些人不喜欢吃早饭” 的符号化形式为___________________________ ____________________________________________________________________________。 5、集合A = {a , b , c }，A 上等价关系R ＝{, , ,
同构映射的定义同构映射的定义
§6.8 线性空间的同构一、 同构映射的定义 一、同构映射的定义 二、同构的有关结论
我们知道，在数域P 上的n 维线性空间V 中取定一组基后，V 中每一个向量有唯一确定的坐标向量的坐标是P 上的n 元数组，因此属于P n . 这样一来，取定了V 的一组基对于V 中每一个向量，令在这组基下的坐标与对应，就得到V 到P n 的一个单射 反过来，对于P n 中的任一元素是V 中唯一确定的元素，并且即也是满射.因此， 是V 到P n 的一一对应.引入12(,,,),n a a a L α12,,,,n εεεL αα12(,,,)n a a a L α12:,(,,,) n n V P a a a σα→a L 12(,,,), n a a a L 1122n n a a a αεεε=+++L 12()(,,,), n a a a σα=L σσ
这个对应的重要必性表现在它与运算的关系上.任取设 ,,V αβ∈12()(,,,)n b b b σβ=L 1122,n n a a a αεεε=+++L 1122n n b b b βεεε=+++L 12()(,,),n a a a σα=L 则1122()(,,) n n a b a b a b σαβ+=+++L 12()(,,)n k ka ka ka k P σα=?∈L 归结为它们的坐标的运算. 这就是说，向量用坐标表示后，它们的运算可以1212(,,)(,,,)()()n n a a a b b b σασβ=+=+L L 12(,,)(), n k a a a k σα==L 从而
一、同构映射的定义 设都是数域P 上的线性空间，如果映射,V V ′具有以下性质： V V σ′→：则称的一个同构映射，并称线性空间V V σ′是到同构，记作V V ′与. V V ′?ii) ()()(), ,V σαβσασβαβ+=+?∈iii) ()(),,k k k P V σασαα=?∈?∈i) 为双射 σ
映射及映射法及例题
映射及映射法及例题 知识、方法、技能 1．映射的定义 设A ，B 是两个集合，如果按照某种对应法则f ，对于集合A 中的任何一个元素，在集合B 中都有惟一的元素和它对应，这样的对应叫做从集合A 到集合B 的映射，记作.:B A f → （1）映射是特殊的对应，映射中的集合A ，B 可以是数集，也可以是点集或其他集合，这两个集合有先后次序，从A 到B 的映射与从B 到A 的映射是截然不同的. （2）原象和象是不能互换的，互换后就不是原来的映射了. （3）映射包括集合A 和集合B ，以及集合A 到B 的对应法则f ，三者缺一不可. （4）对于一个从集合A 到集合B 的映射来说，A 中的每一个元素必有惟一的，但B 中的每一个元素都不一定都有原象.如有，也不一定只有一个. 2．一一映射 一般地，设A 、B 是两个集合，.:B A f →是集合A 到集合B 的映射，如果在这个映射下，对于集合A 中的不同元素，在集合B 中有不同的象，而且B 中每一个元素都有原象，那么个这个映射叫做A 到B 上的一一映射. 3．逆映射 如果f 是A 与B 之间的一一对应，那么可得B 到A 的一个映射g ：任给B b ∈，规定 a b g =)(，其中a 是b 在f 下的原象，称这个映射g 是f 的逆映射，并将g 记为f —1. 显然有（f — 1）— 1= f ，即 如果f 是A 与B 之间的一一对应，则f —1是B 与A 之间的一一对应，并且f — 1的逆映射 是f . 事实上，f — 1是B 到A 的映射，对于B 中的不同元素b 1和b 2，由于它们在f 下的原象不 同，所以b 1和b 2在f —1下的像不同，所以f — 1是1－1的. 任给b a f A a =∈)(,设，则a b f =-)(1 .这说明A 中每个元素a 在f —1都有原象.因此， f —1 是映射上的. 这样即得f —1是B 到A 上的1－1映射，即f —1是B 与A 之间一一对应.从而f — 1有逆映 射.:B A h →由于任给b a h A a =∈)(,设，其中b 是a 在f —1 下的原象，即f — 1(b)=a ，所以， f(a)=b ，从而f h a f b a h ===得),()(，这即是f —1 的逆映射是f . 赛题精讲 Ⅰ映射 关映射的高中数学竞赛题是常见题型之一，请看下述试题. 例1：设集合},,,,|),,,{(},,110|{M d c b a d c b a F x x x M ∈=∈≤≤=集合Z 映射f ：F →Z.使 得v u y x v x y u y x v u cd ab d c b a f f f ,,,,66),,,(,39),,,(.),,,(求已知→→-→的值. 【思路分析】应从cd ab d c b a f -→),,,(入手，列方程组来解之. 【略解】由f 的定义和已知数据，得
《离散数学》期终试题-软件学院-2005-1-中文版
《离散数学》期末考试 南京大学软件学院2005年1月 1.A, B是任意集合，证明：A?~B=φ当且仅当A?B。 2.某系120名学生中有100人选修德语、法语和俄语三门课中的至少一门。已知：有65 人选法语，45人选德语，42人选俄语，20人选法语和德语，25人选法语和俄语，15人选俄语和德语。有多少人是三门课全选的？ 3.A, B, C是任意集合，证明： （1）A?(B-C) =（A?B）- (A?C) （2）A?(B-C) =（A?B）- (A?C)是否成立？证明你的结论。 4.以下是定义在正整数集上的关系，讨论每个关系所满足的性质： （1）“x比y大”（2）“xy是某个整数的平方”（3）“x+4y=10” 5.设A是含4个元素的集合，A上分别可以定义多少满足下列条件的不同的关系： （1）对称关系（2）反对称关系（3）等价关系 6.设g: A→B是双射，证明如下定义的f也是双射：f : ρ(A)→ρ(B): ?S∈ρ(A), f(S)={g(x)|x∈S} 7.假设群G与G’同构，同构映射是f : G→G’。证明： （1）f (e)=e’, 其中：e和e’分别是G和G’单位元素。 （2）f (a -1)=[f (a)]-1, 其中：a是G中任一元素。 8.给定字母表∑={a,b}, 写出定义下列语言L的正则文法和相应的正则表达式 （1）L包含所有恰好含一个b的串。（2）L包含所有不含连续的a串。 9.设k是一给定的正整数。G是一个可交换群。定义函数f : G→G, ?a∈G, f (a)=a k。证明: f 是G上的同构映射。 10.设M={
离散数学深刻复知识题(全)
离散数学复习资料 一、填空 1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:),(则命题的逻辑谓词公式为 。 2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集” 则A= 。 4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词 (()(()(,)))x P x y O y N y x ?→?∧ 的自然语言是 对于任意一个素数都存在一个奇数使 该素数都能被整除 。 5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ??∨?写成不含量词的形式是 。 6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ???∧→?的前束范式为 。 7. 命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ， ～Φ= 。 9. 设={256},{234},{134}A B C ==， ，，，，，，则A-B= ，A ⊕B = ，A ×C = 。 10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，
线性空间的同构
§8 线性空间的同构 一、数域 P 上的 n 维线性空间 n P 二、数域 P 上的一般的n 维线性空间 V 例如：[]n P x 等 设n εεε,,,21 是线性空间V 的一组基，在这组基下，V 中每个向量都有确定的坐标， 而向量的坐标可以看成n P 元素，因此向量与它的坐标之间的对应实质上就是V 到n P 的 一个映射.显然这个映射是单射与满射，换句话说，坐标给出了线性空间V 与n P 的 一个双射. 这个对应的重要性表现在它与运算的关系上.设 n n a a a εεεα+++= 2211, n n b b b εεεβ+++= 2211 而向量,,βα的坐标分别是),,,(21n a a a ,),,,(21n b b b ，那么 n n n b a b a b a εεεβα)()()(222111++++++=+ ; n n ka ka ka k εεεα+++= 2211. 于是向量,βα+αk 的坐标分别是 ),,,(),,,(),,,(21212211n n n n b b b a a a b a b a b a +=+++, ),,,(),,,(2121n n a a a k ka ka ka =. 以上的式子说明在向量用坐标表示之后，它们的运算就可以归结为它们坐标的运算. 因而线性空间V 的讨论也就可以归结为n P 的讨论. 三、线性空间同构 1．定义11 数域P 上两个线性空间V 与V '称为同构的，如果由V 到V '有一个双射σ，
具有以下性质： 1）)()()(βσασβασ+=+; 2) ).()(ασασk k = 其中βα,是V 中任意向量，k 是P 中任意数.这样的映射σ称为同构映射. 前面的讨论说明在n 维线性空间V 中取定一组基后，向量与它的坐标之间的对应 就是V 到n P 的一个同构映射.因而，数域P 上任一个n 维线性空间都与n P 同构. 2．同构映射具有下列性质 由定义可以看出，同构映射具有下列性质： (1). )()(,0)0(ασασσ-=-=. (2). )()()()(22112211r r r r k k k k k k ασασασααασ+++=+++ . (3).V 中向量组r ααα,,,21 线性相关?它们的象)(,),(),(21r ασασασ 线性相关. 因为维数就是空间中线性无关向量的最大个数，所以由同构映射的性质可以推知， 同构的线性空间有相同的维数. (4). 如果1V 是V 的一个线性子空间，那么，1V 在σ下的象集合 {}11|)()(V V ∈=αασσ 是)(V σ的子空间，并且1V 与)(1V σ维数相同. (5). 同构映射的逆映射以及两个同构映射的乘积还是同构映射. 同构作为线性空间之间的一种关系，具有反身性、对称性与传递性. 既然数域P 上任意一个n 维线性空间都与n P 同构，由同构的对称性与传递性即得， 数域P 上任意两个n 维线性空间都同构. 3. 定理12 数域P 上两个有限维线性空间同构的充要条件是它们有相同的维数. 由线性空间的抽象讨论中，并没有考虑线性空间的元素是什么，也没有考虑其中运算 是怎样定义的，而只涉及线性空间在所定义的运算下的代数性质.从这个观点看来， 同构的线性空间是可以不加区别的.因之，定理12说明了，维数是有限维线性空间的 唯一的本质特征.
3.映射函数的定义
映射函数的定义 1．设是集合A 到集合B 的映射，且集合B 中的每一个元素都有原象，若，则等于（ ） A ．{0} B ．{2} C ．{0,2} D ．{-2,0} 2．下列各对应中,构成映射的是 （ ） 3．设集合A ＝B ＝{(,),}x y x R y R ∈∈，从A 到B 的映射在映射下，B 中的元素为（4，2）对应的A 中元素为 （ ） A ．（4，2） B ．（1，3） C ． （3,1） D ．（6,2） 4．设集合和集合都是自然数集合，映射,把集合中的元素映射到集合中的元素 ,则在映射下，象20的原象是（ ） A.2 B.3 C.4 D.5 5．设A={|02x x ≤≤}, B={y | 0≤y ≤3 }, 下列各图中不能表示从集合A 到B 的映射是( ) A ． B ． C ． D ． :||f x x →{2,0,2}A =-A B ) ,(),(:y x y x y x f -+→
6．下列图像表示函数图像的是（） y x y x y x y x A B C D 7．下列图像中，是函数图像的是（） A. (1) (2) B.(2) (3) C.(2)(4) D.(1) (3) 8．下列各图像中，不可能 ．．．是函数 ()x f y=的图像的有几个（） A.1个 B.2个 C.3个 D.4个 9．集合A 中含有2个元素，集合A到集合A可构成个不同的映射. 10．已知集合Ａ＝｛１，２，３，４｝，Ｂ＝｛－１，－２｝，设映射ｆ：Ａ→Ｂ， 如果集合Ｂ中的元素都是Ａ中元素在ｆ下的象，那么这样的映射有 _________________________个． o x y ① o y x ② o y x ③ o y x ④ 试卷第2页，总2页
离散数学网上作业题
东北农业大学网络教育学院 离散数学复习题 复习题一 一、证明 1、对任意两个集合B A 和，证明 ()()A B A B A =??- 2、构造下面命题推理的证明 如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。 二 、计算 1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。 (2)画一个有一条欧拉回路但没有汉密顿回路的图 (3)画一个没有欧拉回路但有一条汉密顿回路的图 2、设()(){ }212,，，个体域为为，整除为 SDH映射、定位和复用的概念 在将低速支路信号复用成STM-N信号时，要经过3个步骤：映射、定位、复用。 1. 定位是指通过指针调整，使指针的值时刻指向低阶VC帧的起点在TU净负荷中或高阶VC帧的起点在AU净负荷中的具体位置，使收端能据此正确地分离相应的VC，这部分内容在下一节中将详细论述。 2.复用的概念比较简单，复用是一种使多个低阶通道层的信号适配进高阶通道层（例如TU12(×3)→TUG2(×7)→TUG3(×3)→VC4）或把多个高阶通道层信号适配进复用层的过程（例如AU-4(×1)→AUG(×N)→STM-N）。复用也就是通过字节间插方式把TU组织进高阶VC或把AU组织进STM-N的过程。由于经过TU和AU指针处理后的各VC支路信号已相位同步，因此该复用过程是同步复用，复用原理与数据的串并变换相类似。 PDH140Mbit/s、34Mbit/s、2Mbit/s信号适配进标准容器的方式是什么装入方式？ 一般都属于异步装入方式，因为要经过相应的塞入比特进行码速调整才能装入。例如， 在将2Mbit/s的信号适配进C12时，不能保证每个C12正好装入的是一个E1帧。 3.映射是一种在SDH网络边界处（例如SDH/PDH边界处），将支路信号适配进虚容器的过程。象我们经常使用的将各种速率（140Mbit/s、34Mbit/s、2Mbit/s）信号先经过码速调整，分别装入到各自相应的标准容器中，再加上相应的低阶或高阶的通道开销，形成各自相对应的虚容器的过程。 为了适应各种不同的网络应用情况，有异步、比特同步、字节同步三种映射方法与浮动VC和锁定TU两种模式。 1）异步映射 异步映射对映射信号的结构无任何限制（信号有无帧结构均可），也无需与网络同步（例如PDH信号与SDH网不完全同步）。利用码速调整将信号适配进VC的映射方法。在映射时通过比特塞入将其打包成与SDH网络同步的VC信息包，在解映射时，去除这些塞入比特，恢复出原信号的速率，也就是恢复出原信号的定时。因此说低速信号在SDH网中传输有定时透明性，即在SDH网边界处收发两端的此信号速率相一致（定时信号相一致）。 此种映射方法可从高速信号中（STM-N）中直接分/插出一定速率级别的低速信号（例如2Mbit/s、34Mbit/s、140Mbit/s）。因为映射的最基本的不可分割单位是这些低速信号，所以分/插出来的低速信号的最低级别也就是相应的这些数率级别的低速信号。 2）比特同步映射 此种映射是对支路信号的结构无任何限制，但要求低速支路信号与网同步（例如E1信号保证8000帧/秒），无需通过码速调整即可将低速支路信号打包成相应的VC的映射方法，注意：VC时刻都是与网同步的。原则上讲此种映射方法可从高速信号中直接分/插出任意速率的低速信号，因为在STM-N信号中可精确定位到VC，由于此种映射是以比特为单位的同步映射，那么在VC中可以精确的定位到你所要分/插的低速信号具体的那一个比特的位置上，这样理论上就可以分/插出所需的那些比特，由此根据所需分/插的比特不同，可上/下不同速率的低速支路信号。异步映射将低速支路信号定位到VC一级后就不能再深入细化的定位了，所以拆包后只能分出VC相应速率级别的低速支路信号。比特同步映射类似于将以比特为单位的低速信号（与网同步）进行比特间插复用进VC中，在VC中每个比特的位置是可预见的。 函数与映射的概念知识梳理第 1 页 共 1 页 函数与映射的概念主要知识梳理 ●函数的基本概念： 1、函数的定义：设B A ,是非空的数集，如果按某个确定的对应关系f ，使对于集合A 中的任意一个元素x ，在集合B 中都有唯一确定的数)(x f 和它对应，则称B A f →:为从A 到B 的一个函数。 ①关键词：非空的数集、任意性、唯一性 ②作用：判断一个对应是否是函数 2、函数的三要素： 定义域A 、值域(?B)、对应法则f （定义域和对应法则最为关键） 作用：判断两函数是否是同一函数的依据（只要判断定义域和对应法则是否相同即可） ●函数的表示方法： 解析式法，列表法，图像法 ●分段函数与复合函数 分段函数：? ??∈∈=)()()()()(21D x x h D x x g x f ，复合函数：))((x g f y = ●映射的概念 1、定义：设设B A ,是非空集合，如果按某个确定的对应关系f ，使对于集合A 中的任意一个元素x ， 在集合B 中都有唯一确定的数)(x f 和它对应，则称B A f →:为从A 到B 的一个映射。 ①关键词：非空集合、任意性、唯一性 ②作用：判断一个对应是否是映射 2、映射的三要素： 原象集A 、象集(?B)、对应法则f 作用：判断两映射是否是同一映射的依据（只要判断原象集和对应法则是否相同即可） 3、函数是特殊的映射； ●反函数 1、概念; 设函数()y f x =的定义域为A ，值域为C ，由()y f x =求出()x y ?=.如果对于C 中 每个y 值，在A 中都有唯一的值和它对应，那么()x y ?=为以y 为自变量的函数，叫做()y f x =的反函数，记作1()y f x -=，（x C ∈） 2、存在反函数的条件：函数()y f x =在定义域内单调（一 一映射） 3、求反函数的一般步骤： （1）求原函数的值域； （2）反解，由()y f x =解出)(y x ?=； （3）写出反函数的解析式1()y f x -=（互换,x y ），并注明反函数的定义域（即原函数的值域）. 4、互为反函数的两个函数具有如下性质： （1）反函数的定义域、值域上分别是原函数的值域、定义域； （2）互为反函数的两个函数在各自的定义域内具有相同的单调性；它们的图象关于x y = 对称； （3）?=b a f )(a b f =-)(1 ●常见的思想方法 1、主要思想: ①数形结合:-------树形图 ②分类讨论：①按象的个数分类；②按原象个数分类； ③按对应关系（一对一、多对一，不能一对多）分类. 2、易错易混点 ①映射B A f →:与函数的定义).(x f y =-----A 中元素的任意性和B 中元素的唯一性? ②一个映射与某一对应的值. ③定义域与原象集以及与集合A 的关系. 值域与象集以及集合B 的关系. 3、主要题型: ①判断映射与函数； ②知原象、象、对应法则三者中的任意二个求余下一个； ③求映射与函数的个数.(注意分类讨论、注意和排列组合知识的综合应用)SDH映射、定位和复用的概念
函数与映射的概念主要知识梳理