四川大学 计算机学院 冯伟森 离散数学(第30讲)
- 格式：ppt
- 大小：595.00 KB
- 文档页数：24
文档推荐
-
四川大学计算机学院多媒体基础量化页数:30
-
2009年四川大学计算机学院录取名单页数:12
-
四川大学计算机学院石兵代数系统页数:40
下载文档原格式
合集下载
离散数学考试题2006
四川大学期末考试试题（闭卷）（2007-2008学年第1学期）课程号：30485040、31100340 课程名称：离散数学（A卷）任课教师：冯伟森、石兵、常致全、周莉适用专业年级：2006级计算机科学与技术、软件工程学号：姓名：一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分1、下列公式中，（ d ）不是永真式。
①（P∧Q）→Q ② P→（P∨Q）③（P→Q）↔（～Q→～P ）④（～P∨Q）∧（～（～P∧～Q））2、下列谓词公式中是前束范式的是（c ）①)()()()(xGxxFx∃⌝∧∀②)()()()(yGyxFx∀∨∀③)),()()()((yxQxPyx→∃∀④)),()()()((yxQyxPx∃→∀3、对任意集合A、B、C，下列命题中为真的是（ c ）。
①若A⊆B 且 B∈C，则A∈C ②若A⊆B 且 B∈C，则A⊆C③若A∈B 且 B⊆C，则A∈C ④若A⊆B 且 B∈C，则A∉C4、设R、S 都是集合A上的二元关系，下列命题中（ b ）不真。
①若R、S 都是自反的，则R∪S是自反的②若R、S 都是反自反的，则R∪S是反自反的③若R、S 都是对称的，则R∪S是对称的④若R、S 都是传递的，则R∪S 是传递的5、设R1、R2都是集合A上的等价关系，下列关系中是A上的等价关系的是（ b ）。
① （A ×A ）-R1 ② R1∩R2 ③ r （R1-R2） ④ R1-R2 6、设集合A={1，2，3，4}，下列A 上的关系构成A 到A 的映射的是（ d ）。
① f1={(2,1),(2,4),(3,4),(4,1)} ② f2={(4,4),(3,1),(1,2),(4,2)} ③ f3={(1,1),(2,1),(1,2),(3,4)} ④ f4={(1,4),(2,1),(3,4),(4,1)} 7、设集合A={1，2，3，4，6，9}，则下列子集族中构成A 的一个划分的是（ ）。
四川大学离散期末考试题附标准答案
四川大学离散期末考试题附标准答案本文档记录了四川大学离散数学期末考试相关的题目，并提供了每个问题的标准答案。
离散数学作为一门重要的数学基础课程，为计算机科学、信息技术以及其他相关学科提供了重要的理论支持。
通过解析这些题目和答案，可以加深对离散数学的理解，提升解题能力。
1. 题目1问题：设A、B、C三个集合满足：A={1,2,3,4,5}，B={3,4,5,6,7}，C={4,5,6,7,8}。
求(A∪B)∩C。
答案：集合A∪B表示将集合A和集合B中的元素合并，去重得到的结果集合。
∩表示求两个集合的交集。
因此，(A∪B)∩C表示先将集合A和集合B合并去重，然后再和集合C求交集。
具体操作如下： 1. 将集合A和集合B的元素合并：A∪B = {1,2,3,4,5,6,7}。
2. 将(A∪B)与集合C求交集：(A∪B)∩C = {4,5}。
所以，(A∪B)∩C = {4,5}。
2. 题目2问题：对于一个图G=(V, E)，其中V={a, b, c, d, e}表示节点集合，E表示边集合。
给定边集E = {(a, b), (b, c), (c, d), (d, e), (e, a)}，请问该图是否是欧拉图？答案：欧拉图是指一类特殊的连通图，可以经过每条边且每条边只经过一次的路径称为欧拉路径。
具有欧拉路径的图称为欧拉图或半欧拉图。
欧拉图有以下两个性质： - 每个顶点的度数都是偶数，或者只有两个顶点的度数是奇数，其余顶点的度数都是偶数。
- 图是连通的。
对于给定的图G=(V, E)，需要满足以上两个性质才能判断该图是否是欧拉图。
具体操作如下： 1. 统计每个顶点的度数： - a的度数为2 -b的度数为2 - c的度数为2 - d的度数为2 - e的度数为2由此可知，每个顶点的度数都是偶数，满足欧拉图的第一个性质。
2. 判断图是否是连通的：通过观察边集E = {(a, b), (b, c), (c, d), (d, e), (e, a)}，可以看出这个图是一个环，即从任意一个顶点出发，可以经过每条边且每条边只经过一次返回原点。
四川大学离散数学（冯伟森版）课后习题答案习题参考解答（图论部分）
四川大学离散数学（冯伟森版）课后习题答案习题参考解答（图论部分）习题十1. 设G 是一个(n ，m)简单图。
证明：，等号成立当且仅当G 是完全图。
证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限max(d(v)) ≤ n-1, G 图的总点度上限为max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。
根据握手定理，G 图边的上限为max(m) ≤ n(n-1)/2,所以。
（2） =〉G 是完全图因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。
所以，G 的每个结点的点度都为n-1，G 为完全图。
G 是完全图 =〉因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数。
■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。
证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。
与题设m = n+1，矛盾。
因此，G 中存在顶点u ，d （u ）≥3。
■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）；（2）（6，3，3，2，2）（3）（4，4，2，2，4）；（4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。
因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。
可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。
最后，将奇数序列对应的点两两一组，添加连线即可。
下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) v 1v 5v 3v 4v 2将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。
离散数学模拟题(川大版)
1、下列是真命题的有（ CD ） A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ． }},{{ΦΦ∈Φ；D ． }}{{}{Φ∈Φ。
2、下列集合中相等的有（ BC ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。
3、设A={1，2，3}，则A 上的二元关系有（ C ）个。
A ． 23 ； B ． 32 ； C ． 332⨯； D ． 223⨯。
4、设R ，S 是集合A 上的关系，则下列说法正确的是（ A ） A ．若R ，S 是自反的， 则S R 是自反的； B ．若R ，S 是反自反的， 则S R 是反自反的； C ．若R ，S 是对称的， 则S R 是对称的； D ．若R ，S 是传递的， 则S R 是传递的。
5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下|}||(|)(,|,{t s A p t s t s R =∧∈><=则P （A ）/ R=（ D ）A ．A ；B ．P(A) ；C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“⊆”的哈斯图为（ C ）7、下列函数是双射的为（ A ）A ．f : I →E , f (x) = 2x ；B ．f : N →N ⨯N, f (n) = <n , n+1> ；C ．f : R →I , f (x) = [x] ；D ．f :I →N, f (x) = | x | 。
（注：I —整数集，E —偶数集， N —自然数集，R —实数集） 8、图 中 从v 1到v 3长度为3 的通路有（ D ）条。
A．0；B．1；C．2；D．3。
9、下图中既不是Eular图，也不是Hamilton图的图是（ B ）10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ A ）个4度结点。
网络工程专业《离散数学》本科课程教学大纲
网络工程专业《离散数学》本科课程教学大纲（2022版）计算机学院2022年编制一、课程基本信息课程代码：128003课程名称：离散数学学分/学时：4.5学分/72学时课程类别：专业教育模块课程性质：专业基础课开课学期：第三学期授课对象：22网络工程本先修课程：高等数学、线性代数二、课程简介《离散数学》课程在讲授利用离散问题进行建模、数学理论、计算机求解方法和技术知识的同时，培养学生的数学抽象能力和严密的逻辑推理能力，通过本课程的学习，可以增强学生使用离散数学知识进行分析问题和解决实际问题的能力，为后续的计算机专业课程打下坚实的基础。
主要内容包括命题逻辑基本概念、等值演算、推理理论，一阶逻辑基本概念、推理理论，集合代数、二元关系、函数、基本组合计数公式、图的基本概念、欧拉图与哈密顿图、树、代数系统。
通过本课程的学习，学生能够掌握离散数学的基本知识、概念、公式及其应用，掌握离散数学中的常规逻辑推断方法，能够具备有效地收集、整理和分析数据的能力，并对所考察的问题作出推断或预测，以及应用数据挖掘和数据分析方法解决实际问题的能力，从而为今后学习、工作和发展建立良好的知识储备。
三、课程具体目标1.通过该课程的教学，了解并掌握计算机科学中普遍地采用离散数学中的一些基本概念、基本思想和基本方法。
通过本课程的学习将得到良好的数学训练，提高抽象思维能力和逻辑推理能力，掌握有关逻辑和证明的基本技巧和方法，理解并能初步运用离散结构进行问题建模和求解，从而为其学习计算机专业各门后续课程做好必要的知识准备，并为从事计算机的应用提供理论基础。
【毕业要求1.1工程知识】（M）2.掌握命题逻辑基本概念、等值演算、推理理论，一阶逻辑基本概念、推理理论，集合代数、二元关系、函数、基本的组合计数、图论等知识的相关的基本概念、基本表示和一些相关运算。
【毕业要求1.1工程知识】（M）3.在传统模式课堂上让学生自带移动智能终端（BYOD，Bring Your Own Device）开展即时互动反馈的信息化教学新模式，以满足教师和学生课堂教学互动与即时反馈需求，从而激发学生的独立思考、自主学习和探究的能力。
离散数学-有限集与无限集(课件)
课件结构
首先介绍离散数学的基本概念和研究对象， 然后详细阐述有限集与无限集的定义、性质 及其在数学和计算机科学中的应用，最后通 过实例和练习题帮助学生巩固所学知识。
有限集定义
有限集是指包含有限个元素的集合。
对于任意自然数n，如果一个集合的 元素个数不超过n，则该集合为有限 集。
有限集性质
02
01
差集
补集
有限集A与有限集B的差集A-B 仍然是有限集，其元素个数等 于集合A的元素个数减去集合A 与集合B的交集元素个数。
在全集U中，有限集A的补集 U-A仍然是有限集，其元素个 数等于全集U的元素个数减去 集合A的元素个数。
02
无限集
无限集定义
无限集是一个元素数量无法穷 尽的集合。
对于任意正整数n，无限集总能 找到至少n个不同的元素。
THANK YOU
感谢聆听
可数集与不可数集
详细阐述了可数集与不可数集的概念、性质及证 明方法。
离散数学在其他学科中的应用
简要概述了离散数学在计算机科学、数学分析、 物理学等学科中的应用。
对未来研究的展望
• 深入研究无限集的性质：尽管我们已经对无限集有了一定的了解，但仍有许多 未解决的问题和需要进一步探讨的性质。
• 拓展可数集与不可数集的研究领域：目前可数集与不可数集的研究主要集中在 一些特定领域，未来可以尝试将这些理论应用到更广泛的领域中。
示例
若A={1,2,3}，B={2,3,4}，则A-B={1}。
04
有限集与无限集的应用
在数学领域的应用
集合论基础
有限集和无限集是集合论的基 本概念，对于研究集合的性质 、关系、运算等具有重要意义 。
数论研究
在数论中，有限集和无限集的 概念对于研究整数的性质、分 布、素数等问题具有重要作用 。
首先介绍离散数学的基本概念和研究对象， 然后详细阐述有限集与无限集的定义、性质 及其在数学和计算机科学中的应用，最后通 过实例和练习题帮助学生巩固所学知识。
有限集定义
有限集是指包含有限个元素的集合。
对于任意自然数n，如果一个集合的 元素个数不超过n，则该集合为有限 集。
有限集性质
02
01
差集
补集
有限集A与有限集B的差集A-B 仍然是有限集，其元素个数等 于集合A的元素个数减去集合A 与集合B的交集元素个数。
在全集U中，有限集A的补集 U-A仍然是有限集，其元素个 数等于全集U的元素个数减去 集合A的元素个数。
02
无限集
无限集定义
无限集是一个元素数量无法穷 尽的集合。
对于任意正整数n，无限集总能 找到至少n个不同的元素。
THANK YOU
感谢聆听
可数集与不可数集
详细阐述了可数集与不可数集的概念、性质及证 明方法。
离散数学在其他学科中的应用
简要概述了离散数学在计算机科学、数学分析、 物理学等学科中的应用。
对未来研究的展望
• 深入研究无限集的性质：尽管我们已经对无限集有了一定的了解，但仍有许多 未解决的问题和需要进一步探讨的性质。
• 拓展可数集与不可数集的研究领域：目前可数集与不可数集的研究主要集中在 一些特定领域，未来可以尝试将这些理论应用到更广泛的领域中。
示例
若A={1,2,3}，B={2,3,4}，则A-B={1}。
04
有限集与无限集的应用
在数学领域的应用
集合论基础
有限集和无限集是集合论的基 本概念，对于研究集合的性质 、关系、运算等具有重要意义 。
数论研究
在数论中，有限集和无限集的 概念对于研究整数的性质、分 布、素数等问题具有重要作用 。
离散数学(第30讲习题课5)讲解
2m d(w) d(w) d(u) d(v) 4(n 2) 5
wG
wu、v
4(n-1) ≥ 4(n-2)+5，矛盾
所以 uv E 。
2019/6/13
计算机学院
15
16、 证明:在 完 全二叉树 中 ， 边 的 数 目 等 于
2（t-1），式中t是叶的数目。
证： 由 Euler 公式， n-m+f=2 ∴ 6-12+f=2 f=8 即面数为 8， ∵对每个面，其度数≥ 3 ∴总面度≥ 3×8=24 ∵总面度=2×m=24 ∴每个面的度数为 3
2019/6/13
计算机学院
19
5、证明：少于30条边的简单平面至少有一个顶 点的度不大于4。
证：（反证法） 设所有顶点的度数≥ 5 由定理12.5 m≤3n-6 ∵ 5n/2 ≤m≤3n-6 ∴ n≥12 则 m≥5n/2≥5×12/2=30 与 m＜30矛盾
2019/6/13
计算机学院
8
2019/6/13
计算机学院
9
V1 1
V2
2
V3
3
V4 V6
7 V5
5
费用=18
2019/6/13
计算机学院
10
例三
设图G是具有6个顶结点、12条边的无向 简单图, 证明图 G 是哈密顿图。
证明：已知一个图是哈密顿图的充分条件是： 图中任意不同两点的度数之和大于等于n。
则v1v2,…,v4k+1v1构成一个Hamilton圈。 2）v1v4k+1E，则 vi1 , vi2 ,, vi2k 与v1邻接
2019/6/13
计算机学院
21
冯伟森_栾新成_离散数学_机械工业出版社 教程课间 精品课程系列 教材(第39讲总复习二)剖析
k 2
i
L ( k 2)nk 2 ( i k 2)
k 2
2018/10/15 计算机学院 15
i
例4
用克鲁斯克尔算法求下图（a）中赋权图 的最小生成树。
4 1 v4
v1 v v4 v 1 v v v v 1 v 1 v 4 v 4 1 1 4 4 3 2 2 1 1 3 2 31 3 2 3 1 3 2 2 v8 v 1 v5 v5 2 1 v5 v1 8v v8 v8 v 5 v v5 5v5v5 v 5 6 12 11 8 8v8 8 5 6 6 v6 5 v7 5 5 6 v v 6 v6 v7 8v7v7 7 8 7 9 98 v2 10 v3 v2 (d) (f) v v3 v3 (e) (a) (b) (c) (h) 3 (g)
v2
v1
0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
该图的邻接和可达性矩阵为
0 0 P 0 0 0
v3
v4
v5
采用Warshall 算法来求可达性 矩阵P
2018/10/15计算机学院 Nhomakorabea13
0 0 PT = 1 1 1
4
G2中长度为2的通路（含回路）总数为11，其中5条为回路。 G2中长度为3的通路（含回路）总数为16，其中3条为回路。
2018/10/15 计算机学院 12
例2
利用可达性矩阵求右图的 所有强分图。 解
0 0 A = 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0
2018/10/15
计算机学院
6
二、基本要求
i
L ( k 2)nk 2 ( i k 2)
k 2
2018/10/15 计算机学院 15
i
例4
用克鲁斯克尔算法求下图（a）中赋权图 的最小生成树。
4 1 v4
v1 v v4 v 1 v v v v 1 v 1 v 4 v 4 1 1 4 4 3 2 2 1 1 3 2 31 3 2 3 1 3 2 2 v8 v 1 v5 v5 2 1 v5 v1 8v v8 v8 v 5 v v5 5v5v5 v 5 6 12 11 8 8v8 8 5 6 6 v6 5 v7 5 5 6 v v 6 v6 v7 8v7v7 7 8 7 9 98 v2 10 v3 v2 (d) (f) v v3 v3 (e) (a) (b) (c) (h) 3 (g)
v2
v1
0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
该图的邻接和可达性矩阵为
0 0 P 0 0 0
v3
v4
v5
采用Warshall 算法来求可达性 矩阵P
2018/10/15计算机学院 Nhomakorabea13
0 0 PT = 1 1 1
4
G2中长度为2的通路（含回路）总数为11，其中5条为回路。 G2中长度为3的通路（含回路）总数为16，其中3条为回路。
2018/10/15 计算机学院 12
例2
利用可达性矩阵求右图的 所有强分图。 解
0 0 A = 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0
2018/10/15
计算机学院
6
二、基本要求
四川大学离散数学教学大纲[2011软件]
（Discrete Mathematical and Its Applications），Kenneth.Rosen 著，
袁崇义 屈婉玲 等译 机械工业出版社（2007.6）
2、《离散数学（修订版）》耿素云、屈婉玲高等教育出版社（2004．4）
3、《离散数学学习指导与习题解析》耿素云、屈婉玲
高等教育出版社2005．3
3、由于离散数学作为一门数学课程，习题训练是个重要环节，但由于该书的部分习题较难，请大家在布置习题时注意；
4、由于学生普遍反映对习题不知道怎样下手，因此在主要章节讲授完成后，我们安排了一次习题课（共计有7次），大家可利用此时间对前面的主要内容进行总结，同时向学生讲解一些典型例题和习题以指导学生；
5、实验：可在数理逻辑、关系、图论及布尔代数部分各布置一次实验；
1.欧拉图及其应用。
2.哈密顿图及其应用。
第14章 代数系统（2个学时）
1.二元运算及其性质。
2.代数系统。
第15章 半群与群（2个学时）
1. 几个典型代数系统。
2. 同态与同构。
第17章格与布尔代数（8个学时）
1．格的定义及性质、子格与格同态。
2．分配格、有补格、Demorgan律。
3．布尔代数。
第1章命题逻辑（12个学时）
1．命题、真值、逻辑联结词、合适公式及真值表、重言式、矛盾式、可满足公式。
2．命题公式的等价、基本等价式、等价的性质、对偶式、联结词的完备集、命题公式的范式构造。
3．命题公式的蕴含、基本蕴含式、蕴含的性质。
4．命题逻辑的推理方法、规则、过程、消解原理的应用。
第2章一阶谓词逻辑（8个学时）
2.图的道路、回路、连通性问题、连通度定理。
3.图的邻接矩阵、关联矩阵、回路矩阵问题。
袁崇义 屈婉玲 等译 机械工业出版社（2007.6）
2、《离散数学（修订版）》耿素云、屈婉玲高等教育出版社（2004．4）
3、《离散数学学习指导与习题解析》耿素云、屈婉玲
高等教育出版社2005．3
3、由于离散数学作为一门数学课程，习题训练是个重要环节，但由于该书的部分习题较难，请大家在布置习题时注意；
4、由于学生普遍反映对习题不知道怎样下手，因此在主要章节讲授完成后，我们安排了一次习题课（共计有7次），大家可利用此时间对前面的主要内容进行总结，同时向学生讲解一些典型例题和习题以指导学生；
5、实验：可在数理逻辑、关系、图论及布尔代数部分各布置一次实验；
1.欧拉图及其应用。
2.哈密顿图及其应用。
第14章 代数系统（2个学时）
1.二元运算及其性质。
2.代数系统。
第15章 半群与群（2个学时）
1. 几个典型代数系统。
2. 同态与同构。
第17章格与布尔代数（8个学时）
1．格的定义及性质、子格与格同态。
2．分配格、有补格、Demorgan律。
3．布尔代数。
第1章命题逻辑（12个学时）
1．命题、真值、逻辑联结词、合适公式及真值表、重言式、矛盾式、可满足公式。
2．命题公式的等价、基本等价式、等价的性质、对偶式、联结词的完备集、命题公式的范式构造。
3．命题公式的蕴含、基本蕴含式、蕴含的性质。
4．命题逻辑的推理方法、规则、过程、消解原理的应用。
第2章一阶谓词逻辑（8个学时）
2.图的道路、回路、连通性问题、连通度定理。
3.图的邻接矩阵、关联矩阵、回路矩阵问题。
基于粗糙集理论不完备信息系统的数据挖掘
基于粗糙集理论不完备信息系统的数据挖掘
胡旺;冯伟森;李志蜀;韦力凡
【期刊名称】《四川大学学报（自然科学版）》
【年(卷),期】2004(041)004
【摘要】提出了一种基于推广的粗糙集理论直接在不完备信息系统上进行数据挖掘的方法,并给出了该方法的算法和实例.该方法利用粗糙集理论直接对不完备信息系统进行知识约简,然后根据获得的约简集建立知识层次树,利用规则的支持度闽值s0和置信度阈值c0从知识层次树的压缩搜索空间中提取不完备系统的规则集.该方法保持了原始数据和数据挖掘所获得的知识的真实性.另外,还提出了知识规则的上、下支持度,上、下置信度,规则粗糙度等概念,以便指导用户更好地利用数据挖掘所获得的知识.
【总页数】5页(P744-748)
【作者】胡旺;冯伟森;李志蜀;韦力凡
【作者单位】四川大学计算机学院,成都,610065;四川大学计算机学院,成
都,610065;四川大学计算机学院,成都,610065;四川大学计算机学院,成都,610065【正文语种】中文
【中图分类】TP391
【相关文献】
1.基于粗糙集理论的不完备信息系统中知识约简的研究 [J], 袁鸿燕
2.拖拉机装配车间调度系统设计—基于粗糙集理论和大数据挖掘 [J], 郅芬香; 王留
芳; 梁硕
3.基于局部粗糙集研究不完备信息系统的理论 [J], 刘瑶瑶
4.基于局部粗糙集研究不完备信息系统的理论 [J], 刘瑶瑶
5.基于粗糙集理论的数据挖掘在CRM中的应用 [J], 张丽莉
因版权原因，仅展示原文概要，查看原文内容请购买。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2013-7-5 计算机学院 5
可以由一个已知的群来构造出一个新的群。 定理15.5 设<G，*>是一个群，aG， 构 造映射a：G→G，使对 xG， a（x）=a*x ，令H={a| aG}，则对于函 数的复合运算“”， <H，>是群。 (证明作为练习）
2013-7-5
计算机学院
而n阶非奇异矩阵乘群<Mn ，×> 、 n次对
称群<Sn，>等都不是交换群。
2013-7-5 计算机学院 21
定理15.9
设<G ， * >是一个群，则<G ， * > 为 交换群的充分必 要条件是：对a，bG，有(a*b)² ＝a² *b² 证明 “” 对a，bG，由于运算“*”是可交换的，所以 有： (a*b)² ＝(a*b)*(a*b)＝a*(b*a)*b ＝a*(a*b)*b＝(a*a)*(b*b)＝a² 。 *b² “” 对a，bG，若有(a*b)² ＝a² ，则： *b² (a*b)*(a*b)＝(a*a)*(b*b)，
2013-7-5 计算机学院 3
该定理是群的另一 如果<G,*>是半群，并且对 种等价定义形式
定理15.4 1) 群 G 中 每 个 元 素 都 是 可 消 去 的 ， 即 如 果 a*b=a*c，则必有b=c。(运算满足消去律) 2) 群G中除幺元e外无其它幂等元； 3) 阶大于1的群G不可能有零元； 4) 群G中的任意两个元素a, b，都有 (a*b)-1＝b-1*a-1。 5) 群G的运算表中任意一行(列)都没有两个相同 的元素（重复元素）；
冯伟森
Email：fws365@ 2013年7月5日星期五
主要内容
一个非常重要的代数系统——群。 主要从以下几个方面来介绍： 1) 群的概念和基本性质。 2) 群的子群和性质。 3) 交换群（Abel群） 4) 循环群
2013-7-5
计算机学院
2
群
定理15.3 a，bG，都存在x，yG 使x*a=b，a*y=b，则 <G,*>是群。群中元素的数目称为群的阶。 证明： 设 aG，方程 x*a=a 的解为e1，
2013-7-5 计算机学院 11
2) 幺 元 存 在 ： 由 于 SΦ ， 所 以 有 aS ， 由 对 a,bS,有a*b-¹S,取a＝b,有eG＝a*a-¹S， 3) 逆元存在：对a,bS，有a*b-1S， 对bS，由eGS，有b-¹＝eG*b-¹S； 4) 封闭性：对a,bS，由3)知：b-¹S，由条 为什么?该推论 件知：a*(b-¹)-¹S，即a*bS. 的证明作为练习 由1)、2)、3)、4)知:<S,*>是<G,*>的子群。 推论：当<G,*>是有限群时，对非空子集S，如对 a,bS， 有a*bS，则<S,*>是<G,*>的子群。 （即只需判断在S中运算是否封闭即可）
2013-7-5 计算机学院 15
例15-2.3
设<G，*>是一个群，H1，H2是G的两个子群。证明 H＝H1∩H2是G的子群。 证明 1)、非空性和幺元存在：由于H1 ，H2 是G的两个子 群，所以有：eH1，eH2，即有eH1∩H2； 2)、封闭性：对a，bH，有a，bH1∩H2， 即a，bH1，a，bH2， 由于H1，H2都是G的子群，所以有： a*bH1，a*bH2，即有：a*bH1∩H2 3)、逆元存在：对aH，有aH1∩H2 ，即aH1 ，aH2 ， 由于H1，H2都是G的子群，所以有： a-1H1，a-1H2，即有：a-1H1∩H2。 由1)、2)、3)知：<H，*>是<G，*>的一个子群。
2013-7-5 计算机学院 20
交换群
定义15.3 若群<G ， * >中的运算“*”是可交换的 运算，则称该群<G，*>是一个交换群（或阿贝 尔(Abel)群）。
例15-3.1
整数加群<Z，+>，实数加群<R，+>，有理
数加群<Q，+>，剩余类乘群<Z17-{[0]}，>、
实数乘群<R-{0}，×> 都是交换群。
2013-7-5 计算机学院 10
定理15.8 设<G，*>是一个群，S是G的一个非 空子集，则<S，*> 是<G，*>的子群的充要条 件是： 对a，bS，有a*b-1S。 证明 “”设S是G的子群，对a，b S，由群 的定义知，b-1S，即有a*b-1S。 所以必要性成立；
“”由子群的定义知，需证明如下四点： 1) S是非空的子集；
封闭的；
2013-7-5 计算机学院 8
由S是G的子集可得结合律也成立； 由于 e=a0S ，所以S中有幺元； 又∵an S有逆元a-n使an*a-n=e
∴综上所述，<S，*>是<G，*>的子群。
特别：由群的一个元素a生成的子群记为(a)。 如：在<Z，+>中，2的生成子群（2）是由全体偶 数关于加法构成的群；而1生成的子群（1）正 好是Z本身。
2013-7-5 计算机学院 18
<Zk-{[0]} ，>是不是群呢？不一定！ Z4-{[0]}={[1]，[2]，[3]}， 可以证明：当k 而[2][2]=[0] Z4-{[0]} 是素数时， ∴ <Z4-{[0]}，>不是群。 <Zk-{[0]} ，> 而Z5-{[0]}={[1]，[2]，[3]，[4]} 一定是群。 其运算表如右图， [1] [2] 运算是封闭的，可结合的； [1] [1] [2] [1]是幺元，[1]、[4]的逆元 [2] [2] [4] 是自身，[2]、[3]互为逆元；[3] [3] [1] 因此<Z5-{[0]} ，>是群。 [4] [4] [3]
2013-7-5 计算机学院 13
3)、逆元存在：对aC，有： 对xG，a*x＝x*a ∵CG，∴aG，即有：a-1G，有： a-1*(a*x)*a-1＝a-1*(x*a)*a-1， 即有：x*a-1＝a-1*x，所以a-1C。 由1)、2)、3)知:<C,*>是<G,*>的一个子群。
6
子群
定义15.2 设<G，*>是一个群，S是G的一个非空 子集，若S也是群，则称<S，*>是<G，*>的一
个子群。
一般来说，对任意的群<G，*>，都有两个
子群<{e}，*>，<G，*>，我们称此两个子群为
该群的平凡子群,而若有子群<S,*>,且S{e}和 SG，则称<S，*>为<G，*>的真子群。
2013-7-5
计算机学院
7
另外，由群中的一个元素也可生成一个子群。 定义 a-k=（ak）-1 定理15.6 设<G，*>是一个群，对任意的a∈G， 令 S＝{an|n∈Z，Z是整数}， 则<S，*>是<G，*>的子群。 证明：因为a∈S，所以显然S是G的非空子集。 对任意的an，am∈S，则an*am＝an+m ∈S G ， 由n,m∈Z，有n+m∈Z，所以an+m∈S，即运算是
201>是一个群，H1 ，H2 ，…，Hn 是G的n个子群，则有H＝H1∩H2∩…∩Hn 是G的子群。
2013-7-5
计算机学院
17
例15-2.4
设Zk表示整数集Z上的模k剩余类集合，即 Zk={[0]，[1]，[2]，…，[k-1]} 在Zk上定义运算和如下： [i][j]=[t]（i+j）t（mod k） [i][j]=[t]ijt（mod k） <Zk ，>是群（剩余类加群）。[0]是的幺元， 每元[i]的逆元是[k-i]。 <Zk ，>不是群，因为虽然它满足封闭性和可结 合性，且[1]是它的幺元，但是[0]无逆元， 所以它仅仅是一个含幺半群。
2013-7-5 计算机学院 12
例15-2.1
设<G，*>是一个群，令： C＝{a|aG且对xG，有：a*x＝x*a} 证明<C，*>是<G，*>的一个子群。 证明1)、非空性：对xG，由于幺元eG存在， 所以有e*x＝x*e＝x，即eC，所以C是非空的； 2)、封闭性：对a，bC，则有：对xG a*x＝x*a， b*x＝x*b， ∴(a*b)*x＝a*(b*x)＝a*(x*b) ＝(a*x)*b＝(x*a)*b＝x*(a*b)， 即：a*bC；
∵ 对tG，方程 a*y=t 有解y0， ∴ e1*t= e1*（a*y0）=（e1*a）*y0 =a*y0=t 即对tG，必有e1*t=t， e1是G中的左幺元。 也可以证明G中有右幺元e2，所以G中有幺元e= e1 = e2 。 同理，对bG，方程x*b=e有解x0，这个x0是b的左逆 此定理说明:在群的定义中幺元及逆元的条件可用方程有解 来代替。另外，群的定义中的幺元条件可用存在左幺元 元，方程b*y=e的解是b的右逆元，且左右逆元相等，从而 （右幺元）的条件代替，逆元的条件可用存在左逆元（右 b有逆元。所以，<G,*>是群。 逆元）的条件代替，
2013-7-5
计算机学院
14
例15-2.2
设<Z，+>是一个整数加群，令： H＝{nk|kZ且n是一个取定的自然数}， 证明：<H,+>是<Z,+>的一个子群。 证明 1)、非空性：显然； 2)、封闭性： 对a，bH，有a＝nk1，b＝nk2 (k1，k2Z)， a+b＝nk1+nk2＝n(k1+k2)H (k1+k2Z)； 3)、逆元存在：对aH，有a＝nk1 (k1Z)， 则a-¹ ＝-a＝-nk1＝n(-k1)H (-k1Z)。 由1),2),3)知<H，+>是<Z，+>的一个子群。
可以由一个已知的群来构造出一个新的群。 定理15.5 设<G，*>是一个群，aG， 构 造映射a：G→G，使对 xG， a（x）=a*x ，令H={a| aG}，则对于函 数的复合运算“”， <H，>是群。 (证明作为练习）
2013-7-5
计算机学院
而n阶非奇异矩阵乘群<Mn ，×> 、 n次对
称群<Sn，>等都不是交换群。
2013-7-5 计算机学院 21
定理15.9
设<G ， * >是一个群，则<G ， * > 为 交换群的充分必 要条件是：对a，bG，有(a*b)² ＝a² *b² 证明 “” 对a，bG，由于运算“*”是可交换的，所以 有： (a*b)² ＝(a*b)*(a*b)＝a*(b*a)*b ＝a*(a*b)*b＝(a*a)*(b*b)＝a² 。 *b² “” 对a，bG，若有(a*b)² ＝a² ，则： *b² (a*b)*(a*b)＝(a*a)*(b*b)，
2013-7-5 计算机学院 3
该定理是群的另一 如果<G,*>是半群，并且对 种等价定义形式
定理15.4 1) 群 G 中 每 个 元 素 都 是 可 消 去 的 ， 即 如 果 a*b=a*c，则必有b=c。(运算满足消去律) 2) 群G中除幺元e外无其它幂等元； 3) 阶大于1的群G不可能有零元； 4) 群G中的任意两个元素a, b，都有 (a*b)-1＝b-1*a-1。 5) 群G的运算表中任意一行(列)都没有两个相同 的元素（重复元素）；
冯伟森
Email：fws365@ 2013年7月5日星期五
主要内容
一个非常重要的代数系统——群。 主要从以下几个方面来介绍： 1) 群的概念和基本性质。 2) 群的子群和性质。 3) 交换群（Abel群） 4) 循环群
2013-7-5
计算机学院
2
群
定理15.3 a，bG，都存在x，yG 使x*a=b，a*y=b，则 <G,*>是群。群中元素的数目称为群的阶。 证明： 设 aG，方程 x*a=a 的解为e1，
2013-7-5 计算机学院 11
2) 幺 元 存 在 ： 由 于 SΦ ， 所 以 有 aS ， 由 对 a,bS,有a*b-¹S,取a＝b,有eG＝a*a-¹S， 3) 逆元存在：对a,bS，有a*b-1S， 对bS，由eGS，有b-¹＝eG*b-¹S； 4) 封闭性：对a,bS，由3)知：b-¹S，由条 为什么?该推论 件知：a*(b-¹)-¹S，即a*bS. 的证明作为练习 由1)、2)、3)、4)知:<S,*>是<G,*>的子群。 推论：当<G,*>是有限群时，对非空子集S，如对 a,bS， 有a*bS，则<S,*>是<G,*>的子群。 （即只需判断在S中运算是否封闭即可）
2013-7-5 计算机学院 15
例15-2.3
设<G，*>是一个群，H1，H2是G的两个子群。证明 H＝H1∩H2是G的子群。 证明 1)、非空性和幺元存在：由于H1 ，H2 是G的两个子 群，所以有：eH1，eH2，即有eH1∩H2； 2)、封闭性：对a，bH，有a，bH1∩H2， 即a，bH1，a，bH2， 由于H1，H2都是G的子群，所以有： a*bH1，a*bH2，即有：a*bH1∩H2 3)、逆元存在：对aH，有aH1∩H2 ，即aH1 ，aH2 ， 由于H1，H2都是G的子群，所以有： a-1H1，a-1H2，即有：a-1H1∩H2。 由1)、2)、3)知：<H，*>是<G，*>的一个子群。
2013-7-5 计算机学院 20
交换群
定义15.3 若群<G ， * >中的运算“*”是可交换的 运算，则称该群<G，*>是一个交换群（或阿贝 尔(Abel)群）。
例15-3.1
整数加群<Z，+>，实数加群<R，+>，有理
数加群<Q，+>，剩余类乘群<Z17-{[0]}，>、
实数乘群<R-{0}，×> 都是交换群。
2013-7-5 计算机学院 10
定理15.8 设<G，*>是一个群，S是G的一个非 空子集，则<S，*> 是<G，*>的子群的充要条 件是： 对a，bS，有a*b-1S。 证明 “”设S是G的子群，对a，b S，由群 的定义知，b-1S，即有a*b-1S。 所以必要性成立；
“”由子群的定义知，需证明如下四点： 1) S是非空的子集；
封闭的；
2013-7-5 计算机学院 8
由S是G的子集可得结合律也成立； 由于 e=a0S ，所以S中有幺元； 又∵an S有逆元a-n使an*a-n=e
∴综上所述，<S，*>是<G，*>的子群。
特别：由群的一个元素a生成的子群记为(a)。 如：在<Z，+>中，2的生成子群（2）是由全体偶 数关于加法构成的群；而1生成的子群（1）正 好是Z本身。
2013-7-5 计算机学院 18
<Zk-{[0]} ，>是不是群呢？不一定！ Z4-{[0]}={[1]，[2]，[3]}， 可以证明：当k 而[2][2]=[0] Z4-{[0]} 是素数时， ∴ <Z4-{[0]}，>不是群。 <Zk-{[0]} ，> 而Z5-{[0]}={[1]，[2]，[3]，[4]} 一定是群。 其运算表如右图， [1] [2] 运算是封闭的，可结合的； [1] [1] [2] [1]是幺元，[1]、[4]的逆元 [2] [2] [4] 是自身，[2]、[3]互为逆元；[3] [3] [1] 因此<Z5-{[0]} ，>是群。 [4] [4] [3]
2013-7-5 计算机学院 13
3)、逆元存在：对aC，有： 对xG，a*x＝x*a ∵CG，∴aG，即有：a-1G，有： a-1*(a*x)*a-1＝a-1*(x*a)*a-1， 即有：x*a-1＝a-1*x，所以a-1C。 由1)、2)、3)知:<C,*>是<G,*>的一个子群。
6
子群
定义15.2 设<G，*>是一个群，S是G的一个非空 子集，若S也是群，则称<S，*>是<G，*>的一
个子群。
一般来说，对任意的群<G，*>，都有两个
子群<{e}，*>，<G，*>，我们称此两个子群为
该群的平凡子群,而若有子群<S,*>,且S{e}和 SG，则称<S，*>为<G，*>的真子群。
2013-7-5
计算机学院
7
另外，由群中的一个元素也可生成一个子群。 定义 a-k=（ak）-1 定理15.6 设<G，*>是一个群，对任意的a∈G， 令 S＝{an|n∈Z，Z是整数}， 则<S，*>是<G，*>的子群。 证明：因为a∈S，所以显然S是G的非空子集。 对任意的an，am∈S，则an*am＝an+m ∈S G ， 由n,m∈Z，有n+m∈Z，所以an+m∈S，即运算是
201>是一个群，H1 ，H2 ，…，Hn 是G的n个子群，则有H＝H1∩H2∩…∩Hn 是G的子群。
2013-7-5
计算机学院
17
例15-2.4
设Zk表示整数集Z上的模k剩余类集合，即 Zk={[0]，[1]，[2]，…，[k-1]} 在Zk上定义运算和如下： [i][j]=[t]（i+j）t（mod k） [i][j]=[t]ijt（mod k） <Zk ，>是群（剩余类加群）。[0]是的幺元， 每元[i]的逆元是[k-i]。 <Zk ，>不是群，因为虽然它满足封闭性和可结 合性，且[1]是它的幺元，但是[0]无逆元， 所以它仅仅是一个含幺半群。
2013-7-5 计算机学院 12
例15-2.1
设<G，*>是一个群，令： C＝{a|aG且对xG，有：a*x＝x*a} 证明<C，*>是<G，*>的一个子群。 证明1)、非空性：对xG，由于幺元eG存在， 所以有e*x＝x*e＝x，即eC，所以C是非空的； 2)、封闭性：对a，bC，则有：对xG a*x＝x*a， b*x＝x*b， ∴(a*b)*x＝a*(b*x)＝a*(x*b) ＝(a*x)*b＝(x*a)*b＝x*(a*b)， 即：a*bC；
∵ 对tG，方程 a*y=t 有解y0， ∴ e1*t= e1*（a*y0）=（e1*a）*y0 =a*y0=t 即对tG，必有e1*t=t， e1是G中的左幺元。 也可以证明G中有右幺元e2，所以G中有幺元e= e1 = e2 。 同理，对bG，方程x*b=e有解x0，这个x0是b的左逆 此定理说明:在群的定义中幺元及逆元的条件可用方程有解 来代替。另外，群的定义中的幺元条件可用存在左幺元 元，方程b*y=e的解是b的右逆元，且左右逆元相等，从而 （右幺元）的条件代替，逆元的条件可用存在左逆元（右 b有逆元。所以，<G,*>是群。 逆元）的条件代替，
2013-7-5
计算机学院
14
例15-2.2
设<Z，+>是一个整数加群，令： H＝{nk|kZ且n是一个取定的自然数}， 证明：<H,+>是<Z,+>的一个子群。 证明 1)、非空性：显然； 2)、封闭性： 对a，bH，有a＝nk1，b＝nk2 (k1，k2Z)， a+b＝nk1+nk2＝n(k1+k2)H (k1+k2Z)； 3)、逆元存在：对aH，有a＝nk1 (k1Z)， 则a-¹ ＝-a＝-nk1＝n(-k1)H (-k1Z)。 由1),2),3)知<H，+>是<Z，+>的一个子群。