下载文档原格式
离散数学关系离散数学关系是一种在有限集上定义的函数，用来描述两个集合之间的关系。
它是抽象数学中最基本的元素，它描述由一列实例构成的集合之间的关系。
离散数学关系有三种：一对一映射(one-to-one mapping)、可枚举映射(enumerable mapping)和量级(order)关系。
1、一对一映射：一对一映射是每个元素都有唯一的映射关系，一个域元素只能映射到一个定义域元素，而且每个定义域元素也只被一个域元素映射。
2、可枚举映射：可枚举映射是指有多个域元素可以映射到一个定义域元素，反之亦然，定义域元素也可以映射到多个域元素，但不一定要求每一个域元素都被映射。
3、量级(order)关系：量级关系是一种非抽象的关系，它可以用来描述元素之间的关系，但不能用唯一的映射关系表示。
量级关系表示一组元素之间的大小或者其他特征的排列顺序，比如“比”，“等于”，“交换”等等，它们可以表示不止一种关系。
二、关系的性质1、可满足性：可满足性是指关系的存在与否与域元素具体的值之间的关系。
可满足关系的存在可以通过满足一定的条件来进行检查，不满足的情况下就会说明这个关系不存在。
2、唯一性：唯一性是指关系的定义域与域元素之间的唯一映射关系。
唯一性可以用来确定定义域元素与域元素之间的唯一映射关系，它不能够产生重复的映射关系。
3、可枚举性：可枚举性是一种可以将定义域与域元素之间的映射关系一一列出来的性质。
可枚举性允许定义域元素有多个域元素与之映射，但它不一定满足唯一性。
4、可组合性：可组合性是一种可以将两个定义域之间的关系组合起来的性质。
可组合性可以将多个关系组合为一个或多个新的关系，从而可以更好的表达更多更复杂的关系。
三、应用1、在离散数学中，离散数学关系经常用来描述中间结果或概念之间的关系。
2、在计算机科学中，离散数学关系常常作为数据结构的基础，用来表示复杂的逻辑结构。
3、在数据库系统中，离散数学关系的应用非常广泛，用来表示不同表之间的关系。
第七章二元关系§1 有序对与笛卡尔积定义两个元素x与y按一定顺序排列构成的二元组称为一个有序对（或序偶），记为〈x,y〉，称x 为第一元素，y为第二元素。
性质 (1) ,,x y x y y x≠⇒〈〉≠〈〉(2) ,,x y u v x u y v〈〉=〈〉⇔=∧=例25 2,45,242xx x yx y+=⎧〈+〉=〈+〉⇒⎨=+⎩3,2x y⇒==−定义：设A、B为两个集合，称{},x y x A y B〈〉∈∧∈为集合A与B的笛卡尔积，记为A×B。
性质：(1) ,A A×=×=∅∅∅∅(2)笛卡尔积不满足交换律与结合律(3)笛卡尔积对并、交满足分配律×=××∪∪A B C A B A C()()()×=××∪∪B C A B A C A()()()×=××∩∩A B C A B A C()()()×=××∩∩B C A B A C A()()()(4)A C B D A B C D⊆∧⊆⇒×⊆×例A={1,2}，求P(A)×A。
§2 二元关系定义设R是集合，若R=∅或A≠∅且A中元素均为有序对，则称R为一个二元关系。
若〈x,y〉∈R，则称x与y有关系R，记为xRy。
定义：设A与B是两个集合，由A×B的子集定义的二元关系称为A到B的二元关系；当A=B 时，称之为A上的二元关系。
例 设A ={0,1}，则R 1={〈0,0〉,〈1,1〉}，R 2=∅， R 3=A ×A 都是A 上的二元关系。
例 设A 是n 元集，则A ×A 有n 2个元素，于是A ×A 有22n 个子集，由此得A 上有22n 个二元关系。
例 设A 是任一集合① 称∅是A 上的空关系 ② 称A ×A 是A 上的全域关系③ 称{},A I x x x A =〈〉∈是A 上的恒等关系。
第七章 特殊关系重点：等价关系、偏序关系的各种性质的判断和证明；难点：如何正确地掌握等价关系及相应的等价类与集合划分之间的关系；如何正确的理解和判断偏序关系的八种特殊元素。
7.1 等价关系1．等价关系设A 是任意非空的集合，R 是A 上的二元关系，如R 是自反的，对称的，传递的关系，则R 称为A 上的等价关系。
下面是一些特殊的等价关系：（1） 任一结合A 上的恒等关系I A 是等价关系； （2） 任一集合A 上的全关系A ×A 是等价关系；（3） 整数集合I 上的模m 同余关系R ＝{<x,y>|(x,y ∈I)∧(x-y)被m 所整除}是等价关系； 2． 等价类设A 是任一非空集合，R 是A 上的等价关系。
对∀x ∈A ，称[x]R = {y|(y ∈A)∧(<x,y>∈R)}为由x 所生成的关于R 的等价类，x 为生成元。
关于等价类，有如下性质：a) 对∀x ∈A ，x ∈[x]R ；b) 对∀x ，y ∈A ，（x≠y ），如y ∈[x]R ，则 [x]R ＝[y]R ，如y ∉[x]R ，则 [x]R∩[y]R ＝∅。
c)[]R x Ax A ∈=1． 划分设A 是非空集合，如存在一个A 的子集族π（π⊆P （A ）），满足以下条件： （1）∅∉π；（2）π中任两个不同的元素交集为空； （3）π中所有元素的并集等于A 。
则称π为A 的一个划分，且称π中元素为划分块。
2．商集从划分和等价类的等一知，A商关于R的一切等价类恰好可以构成集合A的一个划分，该划分为集合A在R下的商集，为此有：A/R ＝{[x]R |（一切x∈A）}称为集合A在R下的商集。
根据划分和商集的敌对你给一，在划分和等价关系之间存在着一一对应关系。
即给定集合A上的一个等价关系R，由R可以唯一产生集合A的一个划分π＝A/R，反之，对集合A的任一划分π＝{A1,A2,…,A k}，可唯一对应集合A上的一等价关系R ＝（A1×A1）∪（A2×A2）∪…∪（A k×A k）。
杭州电子科技大学
硕士研究生复试同等学力加试科目考试大纲
学院：网络空间安全学院加试科目：离散数学
一、命题逻辑
1、命题及逻辑连接词的概念，自然语言的命题符号化。
2、真值表、命题公式与赋值、命题公式的类型。
3、命题的等价演算。
4、范式。
5、命题公式的推理演算。
二、谓词逻辑
1、个体词、谓词、量词及自然语言命题符号化。
2、谓词公式的解释。
3、谓词公式的等价演算。
4、谓词公式的推理规则及演绎推理。
三、集合和关系
1、集合的概念及集合之间的关系。
2、集合的运算。
3、集合的基本等价式。
4、序偶的概念及笛卡儿积。
5、关系的定义及运算。
6、关系的性质。
7、关系的闭包。
8、等价关系与划分。
9、函数的概念与类型。
10、复合函数和逆函数及相关结论。
四、代数结构
1、代数系统的概念。
2、半群、有幺半群、群的概念及性质。
3、循环群、交换群、子群、正规子群等重要概念以及这些代数结构的特性。
4、陪集及拉格朗日定理的应用。
五、图论
1、图、子图、顶点的度等图论基本概念。
2、路、回路的概念，图的连通性及割集的概念。
3、最短通路。
4、树与生成树。
5、欧拉图和哈密尔顿图。
6、有向图的概述。
7、根树与最优二叉树。
参考书目：《应用离散数学》，方景龙、周丽编著，人民邮电出版社，2014.09。
离散数学第二版答案(6-7章)LT第六章 代数系统6.1第129页1． 证明：任取,x y I ∈，(,)*(,)g y x y x y x yx x y xy g x y ==+-=+-=，因此，二元运算*是可交换的； 任取,,x y z I ∈，(,(,))*(*)*()()g x g y z x y z x y z yz x y z yz x y z yz x y z xy xz yz xyz==+-=++--+-=++---+((,),)(*)*()*()(,(,))g g x y z x y z x y xy zx y xy z x y xy z x y z xy xz yz xyz g x g y z ==+-=+-+-+-=++---+=因此，运算*是可结合的。
该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。
2．证明：任取,,x y N x y ∈≠，由*,*x y x y x y x ==≠知，**y x x y ≠，*运算不是可交换的。
任取,,x y z N ∈，由(*)**x y z x z x ==，*(*)*x y z x y x ==知，(*)**(*)x y z x y z =，*运算是可结合的。
任取x N ∈，*x x x =，可知N 中的所有元素都是等幂的。
*运算有右么元，任取,x y N ∈，*x y x =，知N 中的所有元素都是右么元。
*运算没有左么元。
证明：采用反证法。
假定e 为*运算的左么元，取,b N b e ∈≠，由*的运算公式知*e b e =，由么元的性质知，*e b b =，得e b =，这与b e ≠相矛盾，因此，*运算没有左么元。
3．解： ① 任取y x I y x ≠∈,,的最小公倍数和y x y x =*的最小公倍数和的最小公倍数和y x x y x y ==*因此对于任意的y x I y x ≠∈,,都有x y y x **=，即二元运算*是可交换的。
西电离散数学习题答案《西电离散数学习题答案》离散数学是计算机科学和数学中的重要分支，它研究离散对象和离散关系的数学结构。
西安电子科技大学是中国著名的工科院校，其离散数学课程一直以严谨的教学和丰富的习题而闻名。
在这篇文章中，我们将为大家提供西电离散数学习题的答案，希望能够帮助大家更好地掌握离散数学的知识。
1. 集合论1) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求集合A和B的并集和交集。
答：A和B的并集为{1,2,3,4,5,6,7}，交集为{3,4,5}。
2) 若集合A={a,b,c}，B={b,c,d}，C={c,d,e}，求(A∩B)∪C。
答：(A∩B)∪C = {c,d}∪{c,d,e} = {c,d,e}。
2. 图论1) 给定一个简单图G，如果G有6个顶点和8条边，求G的度序列。
答：度序列为{2,2,2,2,1,1}。
2) 若一个图G有5个顶点和7条边，求G的连通分量数目。
答：连通分量数目为1，因为所有顶点都在同一个连通分量中。
3. 命题逻辑1) 设p为命题“今天下雨”，q为命题“我要带伞”，若今天下雨我就要带伞，用命题逻辑表示。
答：p→q。
2) 已知命题p为“我喜欢数学”，q为“我喜欢计算机”，用命题逻辑表示“我既喜欢数学又喜欢计算机”。
答：p∧q。
通过以上习题的答案，我们可以看到西电离散数学课程的内容涵盖了集合论、图论、命题逻辑等多个方面，而且题目设计严谨，能够帮助学生更好地理解和掌握离散数学的知识。
希望同学们在学习离散数学的过程中能够认真对待习题，不断巩固知识，提升自己的数学素养。
