Video在线视频

欢迎同学们来到《软件理论基础》Mooc课堂

现在介绍第二节，数学基础

这门课需要一些数学基础

主要是离散数学

一些内容，这里帮大家梳理

首先，要用到集合的知识

在集合里，用到幂集合

幂集合

是集合所有的子集构成的集合

集合 S 有 a、b、c 三个元素

它所有的子集

有空集、单个字母{a}、{b}、{c}、{a,b| 等等

S 的幂集合，用 2 的 S 次方表示

幂集合满足性质：

一个集合 S，|S|

表示集合 S 元素的个数

2^S 幂集合元素的个数

满足 2^|S| 的个数

这也是为什么

把幂集合记成 2^S

S = { a,b,c} ，2^S 这集合

元素的个数是 2^3 = 8

另外，介绍笛卡积

给两个集合 A 和 B

A 集合的元素

和 B 集合的元素构成

有序数对，用 AXB 表示

A 的元素作第一个元素

B 的元素作第二个元素，得到了这集合

叫做 A 和 B 的笛卡尔积

A 与 B 的笛卡尔积

它元素的个数等于 A 的元素的个数

乘以 B 的元素的个数

类似的

可以推广到多个集合的笛卡积

多个有序的元素的表示

另外，这里用到关系的概念

什么是两个集合的关系呢？

A 和 B 的笛卡尔积

它的任何子集 R

都叫做 A 与 B 的一个关系

A 与 B 的笛卡尔积中

任何一个子集都是 A 与 B 的一个关系

这个关系记为有序数对

譬如，实数“>”

大于，是实数集上的一个关系

关系中

非常重要的一个关系，叫做等价关系

等价关系满足自反性

任何元素 x，它与自己有关系

第二是对称性

如果 x 与 y 有关系

那 y 就与 x 有关系

第三是传递性

如果 x 与 y 有关系

y 与 z 有关系

则 x 与 z 也有关系

满足这三条性质的关系叫做等价关系

数学运算中“=”

满足自反性、对称性

传递性这三个性质

所以，“=”是数学运算中

一个等价关系

等价关系，应用中非常多

只要对集合上定义一个等价关系

就可以对这个集合优化

集合中任何一个元素 x

与 x 等价的元素

放在集合内，叫做一个等价类

记为 [x]_R

例如，集合 {1,2,3,4}

它的关系这样描述

从这个表述

大家可以验证，它满足

自反性、对称性和传递性

因此，这个关系是等价关系

在这个关系中

元素 1，与元素1等价的有 1 和 2

与元素 3 等价的有 3 和 4

可以对这个集合进行划分

表示成为

两两不交的一些子集

每一个集合就是一个等价类

下面介绍半群

什么是半群呢？

集合 S，给一个二元运算

如果这个运算

满足结合律

这个数学结构，集合和运算

叫做一个半群

如果运算很清楚时

这个半群简记为 S

如果二元运算

还满足交换律

这样的半群叫做可交换半群

幂集合，集合 S

2^S 是 S 的幂集合

它对 "并" 运算、“交”运算

都构成半群

整数集 Z，给减法

大家可以验证

它不构成半群

下面介绍同构

同构是两个半群

（S，*），（T，X）

如果有 S 到 T 的 一 一 对应 f

对集合 S 中任何两个元素 a 和 b

都有 f(a*b) = f(a) X f(b)

对任何 a、b 都成立

a 和 b 是 S 中的元素

这运算在S中

得到的也是 S 中的元素

f(a) 是 T 中的元素

f(b) 是 T 中元素

运算之后，还是 T 中元素

（a*b）是 S 的元素

f 作映射后，它是 T 中的元素

这两个都是 T 中元素

一般情况下，它们是不相同的

如果满足是相同的

称这两个半群是同构的

并且称 f 是这两个半群的同构映射

可以看出

假如集合 S 到集合 T 是一个同构映射

f 的逆一定存在

那么 f 的逆是从 T 到 S 的同构映射

从刚才的定义可以看出

证明两个半群同构的步骤：

第一步，必须有集合

S 到 T 的一个函数 f

函数 f 的定义域等于 S

第二步，证明映射 f 是 一 一 的

第三步，证明 f 是满射

第四步，证明 f(a*b) = f(a)圈f(b)

也就是这个映射关于两种运算

是可以交换的

能证明这四点是成立的

那么这两个半群同构

一个例子

S 集合是 {a, b, c}，T 是 {x, y, z}

它们的运算分别由两个表给出

第一个运算，S 运算用 “*” 表示

a 与 a 运算的结果是 a

a 与 b 运算，得到 b

a 与 c 运算，得到 c

同样，b 与 b 运算结果是 c

b 与 c 运算，得到 c

c 与 b 运算，得到 a，等等

再看“圈”运算

x 与 x 运算，得到 z

x 与 z 运算，得到 y

z 与 y 运算，得到 z

z 与 z 运算，得到 x，等等

这表定义了运算 “*”和“圈”

可以验证，这样的运算表

给出了半群 S 和 T

它们是同构的

这作为作业大家完成

下面介绍另一个概念--同态

它是两个半群的一个关系

给了半群 S 和半群 T

如果有一个映射或者函数 f

满足这样的条件

再不需要它是 一 一 映射

只要满足这个条件就 OK

称半群 S 和半群 T 同态

如果映射是映上的或者满射

称集合 T 是 S 的同态映像

例子

设集合 A ={0, 1}

另外一个集合是 A*

A*，后面要定义的

是 A 的闭包

它的运算是连接运算

后面也要定义的

“+”运算由这个表给出来

0+0 等于 0

0+1 等于 1

1+0 等于 1

1+1 等于 0

定义这个映射，是A*到A的

A* 是由一些 0、1 串构成的

α 这串，如果含 1 的个数是奇数

f(α) 等于 1

如果 α 含 1 的个数是偶数

那 f(α) 就是 0

可以证明

f 是一个同态映射

但 f 不是同构

大家课后练习

这节内容介绍完毕

谢谢大家！