[音乐]
[音乐] [音乐]
各位大家好,本次介绍
离散数学导论,主要会介绍我们后面会用到的一些基本的符号和定义 首先是常用的数集符号。
我们在后面会用 N 来表示自然数集,包括 {1,2,4,5}等等
而整数集是用大写字母 Z 表示 有理数集是用 Q
表示,而实数集用 R 表示 我们对实数
定义了两个特殊的函数,分别叫做向上取整函数和向下取整函数
其中向下取整函数是取小于等于 x 的最大的整数
而相应的向上取整函数是大于等于 x 的最小的整数 我们看几个例子。
我们说对 [0.9999] 这样一个 实数,我们向下取整的话,那么
会输出 0 ,而对负的 3/4 向下取整,我们说
小于等于 -3/4 的最大的正数是 -1 所以输出 -1
,类似地 当输入为 π 的时候,我们向上取整。
那么大于等于 π 的最大的 最小的整数是 4,所以它输出的是 4,类似地,
[5.778] 大于等于这个实数的最小的整数是 6 ,所以输出 自然数 6。
我们还会用到两个 符号,一个是连续求和的符号,一个是连续求乘积的符号
分别用大写的 Σ 和大写的 Π 表示 大家一旦看到这两个符号,比如说第一个
Σ i 等于 1 到 nai 的话表示我们去 a1 加到 a2 一直加到
an 而连续的乘,大写的 Π i 从 1 到 nai 的话表
示 a1 乘以 a2 一直乘到 an ,这两个符号在后面的课程中会反复的用到
那么我们这里还会用到的一个重要的符号,类似集合相关的一些符号 我们用小 x
∈ 大 A 表示 x 是集合 A 中的一个元素 那么
A 集合怎么样表示呢?一种比较常见的方式是我们 把大
A 集合中的元素列出来,而在集合的两边用花括弧表示
当然我们说另外一种常见的方式是用 大 A 集合中的元素满足的性质来描述集合大
A 有一个特别重要而又特殊的集合是空集,我们用
这里的这个符号来表示,∅ 来表示 空集是表示不含有任何元素的这样一个集合
那么给了一个集合之后,如果我们想要表示这个集合的大小 用什么符号呢?用大
A 两边加两个竖线,也就类似于绝对值函数的这样一个符号来表示
看一个例子,我们说包含有 丨{1,5,7}丨这三个元素的集合呢 它的大小是 3。
那么集合之间的关系常见的符号有集合的 相等,比如说
A 和 B 相等是什么意思?我们是说所有集合 A 中的元素 都在集合
B 中,并且集合 B 中的元素也都在集合 A 中 那么相应地,我们可以定义
A 是 B 的子集或者说 A 是 B 的真子集 第一个说 A 是 B 的子集是说:凡是
A 的元素都一定在集合 B 中 而 A 是 B 的真子集是说:不但
A 的元素 都在 B 中,并且 B 中必然含有至少一个元素它不在
A 中 我们想强调一点就是集合中的元素的顺序是没有关系的 并且集合中的元素是不具重复的。
也就是说比如说大 A 中出现了两次 小 x
的话,那么我们在最后的表达中它等价于只出现了一次 x
这里我们想介绍两个在 后面也会一直用到的对象。
一个是无序二元组,一个是有序二元组 无序二元组其实就是一个含有两个元素的这样 一个集合。
我们说用这里的 花括号包含了 {x,y}
来表示,要注意它 因为它本身是一个集合,所以 {x,y}
集合等于 {y,x} 这样的一个集合 当然如果 x 和 y
相等的话,我们刚才提到了重复的元素 它会等价于只含有一个元素
x 这样的一个集合 那什么是有序二元组呢?有序二元组注意我们不再用花括弧表示,这里是用了圆括弧
有序二元组的一个重要特点是说:我们说一个 有序二元组 {x,y}
与另外一个有序二元组 {x´,y´} 相等 当且仅当它们的第一个元素也就是
x 和 x´ 相等,并且它们的第二个元素也就是 y 和 y´ 相等
注意在这里,一般来说 {x,y} 的有序二元组和 {y,x}
所对应的有序二元组就不再一样 我们想提一句的是实际上有序二元组可以通过集合来定义出来
但是对于本课程而言,我们仍然把有序二元组作为一个单独的对象,在这里给出了它的这样- 一个定义
好了我们接下来想介绍一下集合上的一些操作 我们看一个例子,比如说大
A 是包含 {1,2,4} 三个元素,大 B 集合是包括 {2,3} 两个元素
我们首先想看的第一个操作是两的 A 次方 这样一个符号,它表示的集合的幂集。
什么是幂集?就是说我们取大 A 集合的所有子集 把它在这里列出来,我们说空集是任何集合的子集
接着我们考虑了只包含 A 中一个元素所形成的集合,分别是 包含只包含
{1} 的集合、 只包含 {2} 的集合和只包含 {4} 的集合 接着第三行列出来的是包含了
A 中两个元素所形成的集合,分别是 {1,2}、 {1,4} 和
{2,4} 子集 然后最后一行也就是第四行的这个
集合呢,就是大 A 集合本身,任何集合都是它本身的一个子集
接着我们看集合间的第二个操作,是 A 并上 B A 并上
B 的意思是我们把 A 和 B 中的元素放在一起
大家可以看到对于我们给出这个例子放在一起 就得到一个新的集合,是
{1,2,3,4} 含有四个元素的集合 接着我们第,集合的交
A 交上 B 是说我们取两个集合中的共同的部分
那么在这个例子中,它是生成一个集合是只包含元素 2 那么什么是接下来这个操作是
A 减去 B 呢? 就是在 A 集合中除掉也在 B 集合中的元素
对我们这个特殊的例子来说,我们说 2 这个元素在 A 中也在
B 中,所以说我们在 A 减去 B 的时候就得到了 {1,4}
这样一个集合 那么最后一个集合操作我们把它叫做笛卡尔积,表现写成是两个集合相乘的这样一个形式
它会输出什么呢?它会输出一个有序二元组所组成的集合 这里面有序二元组的第一元素都是来自
A ,而第二个元素都来自 B 比如说我们看第一行,我们说 1
是来自 A 的,2 是来自 B 类似地,1 是来自 A ,3
是来自 B 那么我们说它第一个元素一共有三种取法,而第二项元素一共有两种取法
所以它的笛卡尔积中间的元素的大小,元素的个数一共是有六个
好了我们说关于集合 有一些基本的等式,比如说并集的交换
律,交集的交换律以及并和交之间的分配律 以及在这里最后两行,是那 著名的德摩根律。
因为这门课程不是一门专门的集合 论课程,所以我们在这里只是简单地罗列了一下这些等式关系
还有一个在本课程中会很重要的概念是函数 小
f(x)→y 它表示一个定义域有大 X ,值域为
Y 的这样一个函数 我们说函数的重要的特点是说 对大
X 中的每个函数都有大 Y 中唯一的一个值 与这个输入所对应
那么我们定义函数的复合就说给了两个函数,我们已经知道小 f 是 从
X 到 Y 的这样一个函数,小 g 是从 Y 到 Z 的一个函数,那么复合函数是什么呢?我们说
g 复合 f 定义域为,我们先使用小 f 函数 得到小
f(x) ,然后再把小 f(x) 的值通过 g 函数映射到 Z
上的一个值 我们看一个例子,我们说小 f 是从实数到实数的一个函数,它是定义为
sinx 而 g 是从实数到整数的一个函数,它是定义为 x 的向上取整
那么这两个函数复合简单地推导就它是 sinx 函数向上取整。
它就是一个从 实数到整数的这样一个函数
有一些特殊而重要的函数 就说什么是单射函数?就是说如果不同的
输入,它一定会对应不同的输出的话,那么我们称这样的函数具有单射性质 比如说自然数到自然数所定义的
f(x) = x + 1 这个函数 它显然是一个单射函数。
第二个重要的函数是满射函数 就是我们说一般来讲,给了一个函数,它的定义域
定义域中的每一个输入都一定有一个值,但是值域中的每一个元素不一定在 大
X 中有一个对应的原像,但是满射函数是说,如果对大 Y
中的 任何一个值都一定能够找到一个原像小 x,使得小 f(x)
= y 的话 那么这就是一个满射函数,我们看一个例子,是从
去掉零的整数集合映射到自然数的取 绝对值的这样一个函数,我们说,很显然这是一个满射函数
那什么是双射函数呢?就是说一个函数如果 它既是一个单射函数,也就是说不同的输入对应到不同的输出
它又是一个满射函数,也就对每一个值,它都能找到一个原像的话,那么我们称这样的函数是- 一个双射函数
双射函数在我们后续课程中会变得非常重要 我们看一个例子,就说还是实数到实数的这样一个函数
f(x) = x³ 可以验证它确实是一个单射函数,也是一个满射函数
我们把函数的概念推广就可以得到关系 什么是集合 A 上的一个关系
R?我们说 R 是 A x A,也就是 A 的笛卡尔积的一个子集
我们用 xRy 这个符号来表示 (x,y)
这个有序对是属于 R 的,要特别注意的是,我们这里现在 使用的是有序对。
关系经常我们会用图形 来表示它,以增强我们对它的理解,直观的理解
xRy 经常是用 x,用一个点来表示,y 也用一个点来表示,然后
一个有像编也就是 x 到 y 的这样一个箭头表示这个有序对 (x,y)
在 R 关系中,那么当 x 和 y 相等的时候呢,我们经常是用这样一个
字环,就是从这个点到本身的一个箭头来表示 xRx
我们说关系也有一些特殊的性质 对 A 上的关系
R,我们说 R 具有,第一个是自反性,自反性是说 对任意的
A 中一个元素小 x,如果 (x,x) 这个有序对它都在关系
R 中,那我们称它为一个自反的关系,用图象来表示的话,就是对每一点
x 它都有到自己的一个环 我们看一个例子,就是自然数上的小于等于关系,我们说它满足自反性,因为每一个
自然数都小于等于它本身,第二个是对称性 对称性是定义为对任意的两个
x,y 属于 A,如果 (x,y) 这个有序对在关系 R
中,那么 (y,x) 也一定在关系 R 中,如果这个 y 是满足这个性质的话,我们就称
关系具有对称性,从图形的表示,如果x,y 之间有一个箭头,那么
y 到 x 也必然有一个箭头 我们看一个例子,我们说自然数上的等于关系它是一个自反的关系
因为如果 x,y 都是自然数,x 等于 y 的话,那么显然 y 也是等于 x
的 那么什么是反对称性?反对称性是说对任意两个元素
x,y 如果我既有 xRy,又有 yRx 的话,那么唯一的可能性是 x
和 y 必然相等 换句话说,就说如果 x 和 y 不相等的话
它们之间不可能有 x 到 y 的箭头以及 同时有 y
到 x 的箭头,我们看一个反对称性的一个例子,我们说
自然数上的小于等于关系是一个反对称关系,因为如果 x 小于等于 y,又有
y 小于等于 x 的话 在自然数上一定能够推出 x 和 y 一定是相等
最后一个重要的性质是传递性,我们说对三个元素 x,y,z
传递性说,如果 xRy 和 yRz 同时成立,那么我们一定能够得到
(x,z) 这个有序对它也在关系 R 中 从图像来讲,如果
x 到 y 有一个箭头,y 到 z 有一个箭头 那么我们应该能够得到 x
到 z 也有一个箭头 一个简单的例子,还是自然数上的小于等于关系,三个自然数
x 小于等于 y,y 小于等于 z 的话,那么自然数上能够推出 x 一定是小于等于 z
的 我们从关系的特殊的性质能够进一步导出一些
重要关系的定义,第一个是等价关系 就是说,如果这个关系同时具有自反性、
对称性 和传递性的话,那么我们称这样的一个关系是等价关系
还是看一个例子,这里是说自然数上的 ≡6 相等的关系,我们说它是一个等价关系
≡6 相等的定义是说两个自然数 x 和 y 如果它们除以 6
的余数是相等的话,那么我们就说它是 ≡6 相等,比如说 6 和 12
除以 6 的余数都是 0,那么它们 ≡6 相等 类似的 1 和 7 除以 6 都是余数为
1,那么也是 ≡6 相等 可以证明它是自反、 对称并且是传递
那么什么是偏序关系?偏序关系我们说一个关系 R
它如果同时具有自反性 反对称性和传递性,那么我们称它为一个 偏序关系。
注意等价和偏序关系的区别就在于 一个是用对称性来定义,另外一个是用反对称性
我们同样的看一个,一个偏序的例子,我们说自然数上的小于等于关系就是一个偏序关系
显然它满足自反,任何自然数小于等于它本身,第二个是反对称性,我们刚才讲了,x 小于等于
y,y 也小于等于 x 的话 那么 x 和 y 必然相同,我们讲了等价关系
之后,我们想要引入一个重要的概念,是所谓的等价类 就说我们已经知道
R 是一个等价关系,那么我们定义 R[x] R[x]
被定义为什么呢?定义为一个集合,它是所有的 y x 和
y 这个有序对在关系 R 中 用 R[x] 来表示元素 x 在关系
R 下的等价类 我们还是看一个例子,我们说自然数上的那个
≡6 相等的关系,刚才我们 讲了它是一个等价关系,那么这个 ≡6
相等的关系,它所定义出来的等价类是什么样子呢? 我们说元素
0 在≡6 相等这个关系下的包含
所有除以 6 余数为 0 的这些数,比如说 0,6,12
等等,再比如说看最后一个 当我们输入为 5 的时候
它是,这个等价类中包含了所有的除 6 余 5 的数,那么就是
5,11,17 等等 这样一些数。
我们 说关于等价类,它有一个,有一些比较重要的性质,第一个性质是说
如果我们找到了这个等价类,那么对任意的小 x 属于 A,R[x] 都一定是为 非空的。
第二个性质是说,对任意的两个 x,y 元素 要不然
R[x] 和 R[y] 完全相等,要不然它们相交为空
我们看一下这个性质的证明,第一个性质是比较显然的,我们说大 A 中的每一个元素小 x
它一定是在 R[x] 中,这是由 关系
R 它因为是一个等价关系,所以它一定具有自反性,所以
x 一定是 R[x],所以 x 一定在 R[x] 中,第二个我们证明
两个等价类它们要不然完全重合,要不然完全不相交,是怎么样证呢 就说如果它们相交为空,那么结论已经成立了
现在我们假设它相交不为空,我们假设有一个小 z,是在 R[x] 交上 R[y]
里面 那么根据定义这说明什么呢?这是说明 xRz 和 yRz
同时成立 那么根据对称性,我们从 xRz 我们能够得到
zRx,类似的我们也可以得到zRy 但这个时候我们考虑
R[x] 这个等价类中的任何一个元素 x'
x' 在 R[x] 中也就是说明了xRx'
成立 那么根据传递性,我们从 xRx'
和 zRx 这两个马上可以得到 zRx'
那么我们这次,再一次使用传递性,我们是使用了 yRz
和 zRx',我们用传递性马上可以得到
yRx',yRx' 根据定义来讲我们就
马上知道 x' 是在 R[y] 中 那么注意到 x' 是 R[x]
中的任意一个元素 前面的推论又说明了x' 也一定在
R[y] 中,所以我们马上得到 R[x] 一定是 R[y] 的一个子集 但这个证明也可以类似地对
R[y] 来进行这样一个推导,我们可以得到 R[y] 也是 R[x]
的一个子集 所以我们把这两部分,这两个子集关系合起来,我们马上就得到了
R[x] 和 R[y] 相等,换句话说,R[x] 和 R[y]
它们如果有一个 相交的元素,那么它们一定是完全重合的,这就得到了我们原始的这样一个性质
等价类,它们要不然相交为空,要不然是完全重合
一个相关的重要概念叫做划分,就是给了一个集合
A,如果我们把它的一些子集放在一起 把它记成 π,π中间的元素
B1,B2 一直到Bn 每一个都是 A 的一个子集,并且这个 π
中的每一个元素它们满足什么性质?满足不相交性,也就说 i
和 j 不相等的时候 Bi 和 Bj 的交一定为空,但是它
同时又满足第三个条件覆盖性,也就说我把所有的这些 B1,B2
一直到 Bn 并起来的话,它得到所有 A 中的元素,那么 这样的一个 π
叫做原始 A 的一个划分 大家可以看到划分这个定义本身是简单的,但是
我们想强调的是有一个重要的划分是什么 是给了集合
A 上的一个等价关系之后,那么我们说等价类集合实际上形成了一个划分
注意我们这里用大 Π,大写的 Π 表示, 大 Π 等于所有的 R[x]
的集合 注意 R[x] 就是我们刚刚定义的,x 元素在关系
R 下的那个等价类 我们说大 Π 一定是一个划分,为什么呢?这个就是我们刚刚所证明的那个一个性质
每一个 R[x] 都一定非空,并且
x 和 y R[x] 和 R[y] 要不然相等,要不然相交为空
并且所有的并起来的话,显然就是得到了整个 A 的这样一个集合 我们要注意这个大
Π 我们在后面,不同的场合都会用到这个定义 好了,我们对那个划分有一个直观的
描述,这里是,我们用一个大圆表示大 A 中所有的元素
那什么,同时又给了 A 上的一个关系 R
它,假设它是一个等价关系,那么我们可以用 等价关系对原始的集合 A 中的元素做划分
比如说第一个扇,第一个扇面中,我们说它放入的是所有跟 R[x] 在关系
R 下相等的那些元素,比如说 R[y] 是另外一些元素,R[z]
是另外一些元素,我们说这些扇面,它们要不然是完全重合,要不然是 完全不相交。
好了,这门课程中我们 还会用到一些逻辑符号,比如说对任意
x,存在 x,否定 合取,析取,还有条件,双向条件以及蕴含,当且仅当关系等
关于这门课中用到的更多的一些基础知识呢,在我们的这两本主要的参考书中都能够
找到,第一章的部分都有详细的介绍。
好了,谢谢大家 [音乐]