离散数学 第八章

17
证明
(2) 假设存在x1, x2∈A使得 由合成定理有 f g(x1)=f g(x2)
g(f(x1))=g(f(x2)) 因为g:B→C是单射的, 故 f(x1)=f(x2). 又由于f:A→B是单射的, 所 以x1=x2. 从而证明f g:A→C是单射的. (3)由(1)和(2)得证. 注意：定理逆命题不为真, 即如果f g:A→C是单射(或满射、双 射)的, 不一定有 f:A→B 和 g:B→C都是单射(或满射、双射)的.
16
函数复合与函数性质
定理8.2 设f:A→B, g:B→C (1) 如果 f:A→B, g:B→C是满射的, 则 fg:A→C也是满射的 (2) 如果 f:A→B, g:B→C是单射的, 则 fg:A→C也是单射的 (3) 如果 f:A→B, g:B→C是双射的, 则 fg:A→C也是双射的 证 (1) 任取c∈C, 由g:B→C的满射性, b∈B使得 g(b)=c. 对于这个b, 由 f:A→B的满射性，a∈A使得 f(a)=b. 由合成定理有 fg(a) = g(f(a)) = g(b) = c 从而证明了fg:A→C是满射的
4
实例
例1 设A={1,2,3}, B={a,b}, 求BA. 解BA={ f0, f1, … , f7}, 其中 f0 = {<1,a>,<2,a>,<3,a>} f1 = {<1,a>,<2,a>,<3,b>} f2 = {<1,a>,<2,b>,<3,a>} f3 = {<1,a>,<2,b>,<3,b>} f4 = {<1,b>,<2,a>,<3,a>} f5 = {<1,b>,<2,a>,<3,b>} f6 = {<1,b>,<2,b>,<3,a>} f7 = {<1,b>,<2,b>,<3,b>}

西南科技大学
6
计算机科学与技术学院
Discrete Mathematics 为方便起见，在无向图中往往用字母ei表示 边。例如，在上图中，用e1表示边(v2,v2)，e2 表示边(v1,v2)等。 对于一个确定的图，我们不关心顶点的位置， 边的长短与形状，因此，所画出的图的图形可 能不唯一。 定义 一个有向图G是一个二元组<V,E>，即 G=<V,E>，其中
西南科技大学
4
计算机科学与技术学院
Discrete Mathematics 定义 一个无向图G是一个二元组<V,E>，即 G=<V,E>，其中
(1). V是一个非空的集合，称为G的顶点集， V中元素称为顶点或结点；
(2). E是无序积 的一个多重子集 (元素可重复 出现的集合为多重集)，称E为G的边集，E中元 素称为无向边或简称边。 在一个图G=<V,E>中，为了表示V和E分别 为G的顶点集和边集，常将V记成V(G)，而将E 记成E(G)。
由于2m，
为偶数，所以
也为偶数。
可是,vV1时，d(v)为奇数，偶数个奇数之和才能 为偶数，所以|V1|为偶数。结论得证。
西南科技大学
17
计算机科学与技术学院
Discrete Mathematics 对有向图来说，还有下面的定理： 定理 设G=<V,E>为有向图， V={v1,v2,…,vn} ， |E|=m，则
(5).设E´ E且E´ ≠Φ ，以E´为边集，以E´中边
关联的顶点的全体为顶点集的G的子图，则称G´是由 边集E´导出的G的子图。
西南科技大学
26
计算机科学与技术学院
Discrete Mathematics 例如，在下图中，(2)，(3)均为(1)的子图；(3)是 生成子图；(2)是顶点子集{v1,v2}的导出子图，也

理学院
第八章 代数系统基础
第八章 代数系统基础
8.1 代数系统概念 8.2 半群与独异点 8.3 群的基本定义与性质 8.4 子群与陪集 8.5 循环群和置换群 8.6 环和域
2
一、基本概念
定义1: 设A是个非空集合且函数f:A*A→A，则称f为 A上的二元运算。
二元运算的两个重要特点： 一是运算封闭性，集合内任意两个元素都可以运算，运算后仍在同
主要包括运算所具有的算律和特殊元素 算律主要：结合律、交换律、分配律、吸收律和消去律 特殊元素：等幂元、幺元、零元和逆元。
9
1.结合律
定义3: 设代数系统<A,*>，对于A中任意元素a,b,c， (ab)c=a(bc)，都称运算满足结合律，或是可结合的 。
实数集合上的加法和乘法满足结合律。幂集P(A)上的交、并和对称差 都满足结合律。矩阵的加法和乘法满足结合律。代数系统(Nk,＋k)和 (Nk, ×k)中的＋k和×k都满足结合律。
例设<A,*>是一个代数系统，其中*定义为a*b=a，证明运算是不可交 换的。
11
3.幂等律
定义5: 设代数系统<A,*>，对于A中任意元素有 x*x=x，则称运算*在A上满足幂等律。
设A为集合，<P(A), ∩>和<P(A), ∪>中的∩和换律、结合律和幂等律。
则称<A,*>是群。
如果<A,>是独异点且每个元素存在逆元，则称<A,>是群。 （R，+），（Z，+）都是群，幺元为零，x -1 = -x；（R-{0}，×）是群，幺
元为1，x -1 =1/x ；<Q,>不是群，1是幺元，而0是无逆元。

定义 8.4 若 m, n∈N 使 m∈n, 则称 m小于n ( 或 n大于m ), 记为 m＜n ( 或 n＞m)。
“小于” 关系 ＜是自然数集 N上的反自反、反对称、传
递
的二元关系
可以用归纳定义法在 N 上定义 “ + ” 与 “ ·” 如下 ：
[加法/乘法] 对任意的 n, m∈ N ，令
i) m + 0 = m，
构造自然数系统＜N，+，·＞
冯 诺依曼（Von Neumann）方案：
0= 1 = 0+ = { } = { 0 } 2 = 1+ = { , { } } = { 0, 1 } 3 = 2+ = { , { }, { , { } } } = { 0, 1, 2 } n+1 = n+ = = { 0, 1, , n }
自然数集合 N（归纳定义法）
i) 0∈N， 这里 0 = ； ii) 若 n∈ N ，则 n＋∈ N ； iii) 若 S N 满足
1) 0∈S 2) 如果 n∈S, 则 n+∈S 则 S = N。
（极小化）
大于/小于、加法、乘法
对每个自然数 n∈ N ，皆有 n∈n＋ 及 n n＋，据此有:
自然数和归纳法
主要概念： 集合的后继 主要方法：归纳原理、第一归纳法、第二归纳法
自然数的引进方法
① 公理化方法：皮亚诺公理（G. Peano）； ② 构造性方法：借助集合论，具体构造出 N。
自然数构造的出发点
1) 自然数的各种性质 ( 运算、大小次序 及 基本定律 ) , 都可以从 Peano 公理一一推导出来；
∪ ( n＋ ) ＋ = ∪ ( n＋∪{ n＋ } ) = ( ∪ n＋ ) ∪ (∪{ n＋ } ) = n ∪ n＋ = n＋ 。