离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
77-同构与同态
Loading...
来自 Peking University 的课程
离散数学概论 Discrete Mathematics Generality
150 个评分
从本节课中
抽象代数
与讲师见面
陈斌副教授
北京大学
[音乐] Hi，欢迎回来。
接下来呢我们来讨论这个代数结构之间的关系。
终于到了这个时候啦，那么对于两个代数结构来说，我们先来看看一个例子。
下面呢有这两个图呢是 两个代数结构的它的两个的运算的表，定义运算的表。
这里是两个，哪两个呢？一个呢是，代数结构呢是由两个元素构成了一个A， 一个集合A，一个空集，它的并集。
然后 另外一个呢是1和0，它就真值啦，真或假。
那么它是一个析取运算。
当然我们在学这个，学习这个 集合的时候，学习这个逻辑连接词的时候，我们都会感觉到
而这个并集和这个析取，它有点 类似。
当然实际上并集是通过析取这个逻辑连接词来进行定义的 吧。
但是呢，我们也可以看到，把它变成了这个代数结构之后，它们有多相似。
我们来看这两张表。
左边这张表呢，是这个 A空集，再加上求并集运算的这么一个代数结构。
而右边这张表，它是1,0和析取， 它的一个代数结构的这个运算的表。
那么我们从这两个代数结构看来，实际上除了符号之外， 它的结构是完全是相同的。
那么都是，比如说都是空，然后A，然后有空集空集A，然后 A，然后。
那么这个0，1呢，0，0，1，然后1，1，1。
如果我们假设说有一个符号的变换，
就是有个一一对应的一个映射，那么它们之间呢就可以完全就可以相互转换。
比如说我们把A 替换成1，把空集替换成0，然后呢把这个
并集的这个操作，这个运算呢替换成析取， 那么整个呢这个代数结构就变成了另外一个代数结构。
那反过来呢也是一样的， 所以我们可以看出来，这两个代数结构，它虽然在内容，它含义
运算的含义和载体的具体的元素的这个含义都完全不同。
但是呢它们却可以做一一的这个转换，这种同构的关系，让我们再去想起来
这个在图论当中我们讨论这个同构图，这样的一个同构的 关系，对吧？它也是存在一个映射，可以把一个图的节点
顶点映射成另外一个图的顶点，然后随之它的边呢也一一地对应
过去，那么这两个图呢，就我们可以说，看成是一样的图，它们具有相同的结构，也会
具有类似，就会有相同的，很多的性质上都是相同的。
那么这种代数结构之间的这个相似关系，我们从这个
直观的图形，从它的转换，具体的这个代数结构之间的这种对比，
再进一步，我们看看抽象的情况是什么样子的。
那么首先呢我们定义一个同类型的代数结构，什么是同类型呢？
就是首先，它要在载体集合上，载体的基数是一样的。
也就是说它得到的这个数量，包含的元素的数量是相等的，而且，
它们所包含的这个运算，它的元数也是相同，那么这就称作为同类型的代数结构。
那么我们相信同类型的代数结构有很多。
那么在同类型的代数结构里头，如果再进一步呢，就有所谓的同构的代数结构。
那么同构的定义是这样，它存在一个S到S'的一个一一映射h， 这是一个一一映射的函数，就是一个双射函数了。
那么S当中的运算的像，
等于运算数它先映到S'里头，再在
S'里头做*'的这个运算，这两个运算的结果是相等的。
也就是用表达式来表达呢就是这样，x*y，因为x,y呢都是属于S的，
那么x*y它会有一个结果，再把这个结果呢做这个双射函数映射到S'， 得到了一个值，那么就是运算的项。
它会等于什么呢？把x做一个映射，x的像，
y做一个映射，y的像，然后这两个像呢，在S'里头做*'的 运算。
然后这样呢，如果它们相等的话，那么 我们就称作为这个S和S'这两个代数结构是
同构的，那当然这个*呢是S上的运算，* '呢是S'上的这个运算。
那么对于更为一般的情形是这样的，我们为了表达
在代数结构之间，更为一般性的这种相似关系呢，我们又引入了所谓的同态映射这么一个概念。
那么也就是说对于一个代数结构S，然后 △，#，和S'，△'和#'这两个代数结构，
如果它存在一个函数，S到S'的一个函数， 其中呢对于这个S当中的任意的元素a,b，
它都满足下面这两个条件，实际上就是刚才说的 就是运算结果的像等于运算数的像的运算结果。
也就是△a它就经过运算，然后再经过
h的映射，它会等于h(a)再做△'的运算，它就相等，这是一个一元运算。
那对于二元运算来讲，a#b，它的像 对吧？做h这个映射，它会等于h(a)和h(b)
然后再做#'的这个运算，如果也会相等的话，
那么就把这个函数h，就称之为代数结构S到S'的一个同态映射。
那么如果说这个h是一个单射函数，那么就称作为单同态，单一同态。
那么如果h是一个满射函数，那么就称之为满同态。
那么h是一个双射函数的话，那么就称之为一个同构映射。
那么这两个代数结构之间呢就称之为是一个同构的代数结构。
那么关于同态映射呢，它实际上表现了
两个代数结构之间一种相似啊或者等效的这种关系。
也就是它们在讨论它们这个对象的性质以及
这个运算的性质上，很多方面它可能都会是相同或者相近的， 这样都表明了一个同态映射。
我们来举一个例子。
通常呢，我们在学习算术的时候，我们 总会感觉这个加法和乘法有很多相似的性质。
那么这个怎么个相似法呢？我们可能也说不出一个所以然来，
我们现在在抽象代数这呢，我们就来给大家分析一下，它们是如何相似的。
好，我们在做这个R，就是实数集合上的加法，和实数集合上的乘法，
那么这两个的分是不同的这个代数结构。
那么在它们之间实际上存在着一个单一同态映射，
f(x)，那么我们把这个f(x)呢定义为2的x次幂。
这是一个幂函数。
那么这样呢， 我们就可以列出这个单一同态映射的它的定义。
就说f(x+y)，那么这是加法啊，x+y那么它就等于2的x+y次幂。
那么根据幂运算的性质，2的x+y次幂，就应该等于2的x次幂，乘以2的y次幂。
那么这个2的x次幂呢就等于 f(x)了，2的y次幂就是f(y)，然后它们之间
有一个相乘，那这样呢就这个单一同态映射f
就把这个加法，就把R的加法变成了R的乘法。
那么这样呢，因为这个f(x)它是一个单射函数，它并不满，因为在
这个实数集合里头，2的x次幂，它不会小于0， 甚至不会等于0。
所以呢，但是我们如果把这个R 乘法改成这个正实数上的乘法，
就是R+乘法的话，那么这样呢f(x)它就变成了一个双射函数了。
那么这样呢，f(x)就会变成一个同构映射，那这样呢， 最终的结论就是，实数集合上的加法和
正实数集合上的乘法，这两个代数结构，它们是同构的。
所以呢，我们说加法和乘法很类似，或者它们具有很多相近的这个性质。
那么就从这儿来的，我们可以构造出一个这个
同态映射和同构映射来证明它们之间呢是具有
同构这样的一个性质。
当然，我们还可以另外有一个例子，是一个满同态的映射的例子。
那么这个呢就是由字符串上的集合，和字符串上的运算，
就是连接运算，我们知道把字符串，如果a,b和b,c进行连接，就会变成ab,bc， 那么它就变长了嘛。
那么 跟自然数集合上的加法之间，它实际是是存在一个满同态的映射，它存在一个满射函数。
就是求字符串的长度这么一个函数，这个函数呢把这个w 变成一个自然数，把一个字符串变成一个自然数，也就是它的长度了。
那么当然它是一个满射函数。
那么这个满射，满同态呢是这样表达的，就是 u连接上v，它的长度呢就等于
u连接v的这个长度。
然后呢u连接v的长度呢是等于u的长度加上v的长度。
那这样呢就是length(u)+length(v)，所以呢就把这个连接运算，
转换成这个自然数的加法运算了。
这是一个满同态。
那么这个表明了说字符串上的这个连接运算和这个自然数加法之间 又存在一种相似的性质。
那么这种相似性呢实际上它有很多的应用。
比如说我们这样呢就可以用连接，字符上的连接，或者说其他什么
其他什么东西的连接来模拟这个加法运算，对吧？那既然它们是同态映射， 那么它就可以用来模拟这个加法运算。
那么这个呢实际上也有应用，就是 在我们的所谓的DNA计算当中，它是一个分子级的这个运算，在DNA计算技术里边，
那么它就实际上是把这个DNA的片段做一个剪切和拼接这么一个操作。
那么把剪切呢就映射到减法了，把拼接
那么就变成了像类似于字符串连接这样，就可以用来 模拟这个加法。
所以呢基本的运算都进行模拟了以后，那么DNA的分子
以及分子之间的用酶来进行分子之间的拼接和剪切。
或者说进行复制，那么就会变成一个拥有计算能力的一个
一个机器，那这样呢，就最终也是实现了
DNA计算这样的一个非常高效的一个计算的方式。
