文档库 最新最全的文档下载
当前位置:文档库 › 离散数学 二元关系

离散数学 二元关系

离散数学 二元关系
离散数学 二元关系

第四章二元关系

1举出A={1, 2, 3}上关系R的例子,使其具有下述性质:

a)既是对称的,又是反对称的;

b)既不是对称的,又不是反对称的;

c)是传递的。

2举出一个集合上关系的例子,分别适合于自反,对称,传递中的两个且仅适合两个。

3如果关系R和S是自反的,对称的和传递的,证明R?S也是自反的,对称的和传递的。4设R1和R2是A上的二元关系,说明以下命题的真假:

a)若R1和R2是自反的,则R1 o R2是自反的;

b)若R1和R2是反自反的,则R1 o R2是反自反的;

c)若R1和R2是对称的,则R1 o R2是对称的;

d)若R1和R2是传递的,则R1 o R2是传递的。

5画出集合A={1, 2, 3, 4, 5, 6}在偏序关系“整除”下的哈斯图,并讨论:

a)写出{1, 2, 3, 4, 5, 6}的极大元,极小元,最大元,最小元;

b)分别写出{2, 3, 6}和{2, 3, 5}的上界,下界,上确界,下确界。

6是非判断:设R和S是A上的二元关系,确定下列命题是真还是假。如果命题为真,则证明之;如果命题为假,则给出一个反例。

(1)若R和S是传递的,则RèS是传递的。

(2)若R和S是传递的,则R?S是传递的。

(3)若R和S是传递的,则RoS是传递的。

(4)若R是传递的,则R-1是传递的。

(5)若R和S是自反的,则RèS是自反的。

(6)若R和S是自反的,则R?S是自反的。

(7)若R和S是自反的,则RoS是自反的。

(8)若R是自反的,则R-1是自反的。

(9)若R和S是对称的,则RèS是对称的。

(10)若R和S是对称的,则R?S是对称的。

(11)若R和S是对称的,则RoS是对称的。

(12)若R是对称的,则R-1是对称的。

(13)若R和S是反对称的,则RèS是反对称的。

(14)若R和S是反对称的,则R?S是反对称的。

(15)若R和S是反对称的,则RoS是反对称的。

(16)若R是反对称的,则R-1是反对称的。

7设R1和R2是集合A上的二元关系,

t(R1)∪t(R2)ít(R1∪R2)。

8设A={a,b,c,d},A上的二元关系R:R={(a,b), (b,a), (b,c),(c,d)}

(2)试求t(R),并画出它的关系图。

9确定下列各式是不是A={1,2,3,4,5}上的等价关系,如果是等价关系,请写出它的等价类。

(1){(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(1,5),(5,1),(3,5),(5,3)}

(2){(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(3,4),(4,3)};

(3){(1,1),(2,2),(3,3),(4,4)};

(4){(a,b)|4整除a-b},a,b?A;

(5){(a,b)|3整除a+b},a,b?A;

(6){(a,b)|a整除2-b},a,b?A。

10、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y2},

求(1)R (2) R-1。

11、举出集合A上的既是等价关系又是偏序关系的一个例子。()

12、集合A上的等价关系的三个性质是什么?( )

13、集合A上的偏序关系的三个性质是什么?( )

14、设S={1,2,3,4},A上的关系R={〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉}

求(1)R o R (2) R-1。

R-1 ={〈2,1〉,〈1,2〉,〈3,2〉,〈4,3〉}

15、设A={1,2,3,4,5,6},R是A上的整除关系,求R= {()}。

16、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=2y},求(1)R (2)

R-1。

17、设A={1,2,3,4,5,6},B={1,2,3},从A到B的关系R={〈x,y〉|x=y2},求R和R-1

的关系矩阵。

18、集合A={1,2,…,10}上的关系R={|x+y=10,x,y?A},则R的性质为()。

(1)自反的(2)对称的 (3)传递的,对称的 (4)传递的

应用离散数学-集合与关系

集合与关系《应用离散数学》 第3章 21世纪高等教育计算机规划教材

目录 3.1 集合及其运算 3.2 二元关系及其运算3.3 二元关系的性质与闭包3.4 等价关系与划分 3.5 偏序关系与拓扑排序3.6 函 数 3.7 集合的等势与基数3.8 多元关系及其应用

集合是现代数学中最重要的基本概念之一,数学概念的建立由于使用了集合而变得完善并且统一起来。集合论已成为现代各个数学分支的基础,同时还渗透到各个科学技术领域,成为不可缺少的数学工具和表达语言。对于计算机科学工作者来说,集合论也是必备的基础知识,它在开关理论、形式语言、编译原理等领域中有着广泛的应用。 本章首先介绍集合及其运算,然后介绍二元关系及其关系矩阵和关系图,二元关系的运算、二元关系的性质、二元关系的闭包,等价关系与划分、函数,最后介绍多元关系及其在数据库中的应用等。

3.1 集合及其运算 3.1.1 基本概念 集合是数学中最基本的概念之一,如同几何中的点、线、面等概念一样,是不能用其他概念精确定义的原始概念。集合是什么呢?直观地说,把一些东西汇集到一起组成一个整体就叫做集合,而这些东西就是这个集合的元素或叫成员。 例3.1 (1)一个班级里的全体学生构成一个集合。 (2)平面上的所有点构成一个集合。 (3)方程 的实数解构成一个集合。 (4)自然数的全体(包含0)构成一个集合,用N表示。 (5)整数的全体构成一个集合,用Z表示。 (6)有理数的全体构成一个集合,用Q表示。 (7)实数的全体构成一个集合,用R表示。

(8)复数的全体构成一个集合,用C表示。 (9)正整数集合Z+,正有理数集合Q+,正实数集合R+。(10)非零整数集合Z*,非零有理数集合Q*,非零实数集合R*。(11)所有n 阶(n≥2)实矩阵构成一个集合,用M n(R)表示,即

“离散数学”中的等价关系

“离散数学”中的等价关系 “离散数学”是计算机专业的重要基础课程和核心课程。通过该课程的教学,不仅要为学生们进一步学习本专业的后续课程提供必备的数学理论基础,更重要的是培养和提高学生的抽象思维能力和逻辑推理能力。与高等数学主要以连续量作为研究对象不同,离散数学主要以离散量作为主要的研究对象,内容包括数理逻辑、集合论、代数结构、图论以及组合数学、数论和离散概率等。由于这些内容在描述形式、研究方法和计算机应用领域等方面均存在着较大差异,且含有大量比较抽象的概念、定理和各种各样的形式化描述,因而学生普遍感到困难重重,学习效果不理想。因此,如何改进教学方法,提高教学效果,使学生们的抽象思维能力和逻辑推理能力真正得到提升,是“离散数学”课程教学过程中必须认真解决的重要课题。 1离散数学课程中的等价关系 1.1离散数学课程中等价关系的概念 定义1 设R为非空集合A上的二元关系。如果R是自反的、对称的和可传递的,则称R为A上的等价关系。 定义2 设R为非空集合A上的等价关系,x∈A,令[ x ]R={ y | y ∈A ∧xRy }, 则称[ x ]R 为x关于R的等价类,简记为[ x ]。 定义3 设R为非空集合A上的等价关系,以R的所有等价类作元素的集合称为A关于R的商集,记为A/R,即A/R={ [ x ]R| x∈A }。 根据定义1,很容易证明矩阵理论中的矩阵合同关系、相似关系都是等价关系;线性空间的同构关系也是一种等价关系。下面主要讨论离散数学中一些常见的等价关系。 1.2离散数学课程中各种具体的等价关系 数理逻辑中,命题公式A和B等值(记为A B)是指由它们构成的等价式A B 为永真式。命题公式的等值关系是建立在由所有命题公式构成的集合上的一种等价关系,这种等价关系将所有命题公式按其是否等值划分成若干个等价类,属于同一个等价类中的命题公式彼此等值,因而,只要清楚了等价类中某一个公式的性质,则与该公式同类的公式的性质也就完全清楚了。因此,命题公式的等值关系(等价关系)是获取命题公式性质的基石。 集合论中,集合A和B的等势是指从A到B存在一个双射函数即集合A中

离散数学第四章二元关系和函数知识点总结

集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y,按照一定的顺序组成的 二元组称为有序对,记作 实例:点的直角坐标(3,4) 有序对性质 有序性 (当x y时) 相等的充分必要条件是= x=u y=v 例1 <2, x+5> = <3y4, y>,求x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3 定义一个有序n (n3) 元组 是一个 有序对,其中第一个元素是一个有序n-1元组,即 = < , x n> 当n=1时, 形式上可以看成有序 1 元组. 实例 n 维向量是有序 n元组. 笛卡儿积及其性质 定义设A,B为集合,A与B 的笛卡儿积记作A B,即A B ={ | x A y B } 例2 A={1,2,3}, B={a,b,c} A B ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>, <3,a>,<3,b>,<3,c>} B A ={,,,,,, , ,} A={}, P(A)A={<,>, <{},>} 性质:

不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 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) 若A或B中有一个为空集,则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取 ∈A×(B∪C) x∈A∧y∈B∪C x∈A∧(y∈B∨y∈C) (x∈A∧y∈B)∨(x∈A∧y∈C) ∈A×B∨∈A×C ∈(A×B)∪(A×C) 所以有A×(B∪C) = (A×B)∪(A×C). 例3 (1) 证明A=B C=D A C=B D (2) A C=B D是否推出A=B C=D 为什么 解 (1) 任取 A C x A y C x B y D B D (2) 不一定. 反例如下: A={1},B={2}, C=D=, 则A C=B D 但是A B.

离散数学集合论练习题

集合论练习题 一、选择题 1.设B = { {2}, 3, 4, 2},那么下列命题中错误的是( ). A .{2}∈ B B .{2, {2}, 3, 4}B C .{2}B D .{2, {2}}B 2.若集合A ={a ,b ,{ 1,2 }},B ={ 1,2},则( ). A . B A ,且BA B .B A ,但BA C .B A ,但BA D .B A ,且BA 3.设集合A = {1, a },则P (A ) = ( ). A .{{1}, {a }} B .{?,{1}, {a }} C .{?,{1}, {a }, {1, a }} D .{{1}, {a }, {1, a }} 4.已知AB ={1,2,3}, AC ={2,3,4},若2 B,则( ) A . 1?C B .2? C C .3?C D .4?C 5. 下列选项中错误的是( ) A . ??? B . ?∈? C . {}??? D .{}?∈? 6. 下列命题中不正确的是( ) A . x {x }-{{x }} B .{}{}{{}}x x x ?- C .{}A x x =?,则xA 且x A ? D . A B A B -=??= 7. A , B 是集合,P (A ),P (B )为其幂集,且A B ?=?,则()()P A P B ?=( ) A . ? B . {}? C . {{}}? D .{,{}}?? 8. 空集?的幂集()P ?的基数是( ) A . 0 B .1 C .3 D .4 9.设集合A = {1,2,3,4,5,6 }上的二元关系R ={a , b ∈A , 且a +b = 8},则R 具有的性质为( ). A .自反的 B .对称的 C .对称和传递的 D .反自反和传递的

《应用离散数学》方景龙版3.4 等价关系与划分

§3.4 等价关系与划分 习题3.4 1. 对于给定的集合A 和其上的二元关系R ,判断R 是否为等价关系。 (1)A 为实数集,A y x ∈?,,2=-?y x xRy 。 (2)}321{,,=A ,A y x ∈?,,3≠+?y x xRy 。 (3)+=Z A ,即正整数集,A y x ∈?,,是奇数xy xRy ?。 (4))(X P A =,集合X 的基数2||≥X ,A y x ∈?,,x y y x xRy ?∨??。 (5))(X P A =,集合X 和C 满足X C ?,A y x ∈?,,C y x xRy ?⊕?。 解 略 2. 设}{d c b a A ,,,=,对于A 上的等价关系 A I c d d c a b b a R }{><><><><=,,,,,,, 画出R 的关系图,并求出A 中各元素关于R 的等价类。 解 R 的关系图如下: A 中各元素关于R 的等价类分别为: },{][][b a b a ==,},{][][d c d c == 3. 考虑单词的集合}{sit wind wash sky last sheet W ,,,,,=。1R 和2R 分别是由“具有同样多的字母”和“具有相同的开头字母”定义的等价关系。求由1R 和2R 确定的商集1/R W 和2/R W 。 解 略 4. 给出模6同余关系,并求出所有的模6同余类。 解 模6同余关系)}6(mod |{b a b a b a R ≡∧∈><=Z ,, 所有的模6同余类为: 510}|5{][,,,, =∈+=i z i z i Z 即 },20,15,10,5,0,5,10,15,20,{]0[ ----= },21,16,11,6,1,4,9,14,19,{]1[ ----=

离散数学题目大汇总

离散数学试题一(A 卷答案) 一、(10分)证明(A ∨B )(P ∨Q ),P ,(B A )∨P A 。 二、(10分)甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛,下列4 种判断都是正确的: (1)甲和乙只有一人参加; (2)丙参加,丁必参加; (3)乙或丁至多参加一人; (4)丁不参加,甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、(10分)指出下列推理中,在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1),US (3)xP (x ) P (4)P (y ) T (3),ES (5)Q (y ) T (2)(4),I (6)xQ (x ) T (5),EG 四、(10分)设A ={a ,b ,c},试给出A 上的一个二元关系R ,使其同时不满足自反性、反自反性、 五、(15分)设函数g :A →B ,f :B →C , (1)若f o g 是满射,则f 是满射。 (2)若f o g 是单射,则g 是单射。 六、(15分)设R 是集合A 上的一个具有传递和自反性质的关系,T 是A 上的关系,使得T R 且R ,证明T 是一个等价关系。 七、(15分)若是群,H 是G 的非空子集,则的子群对任意的a 、b ∈H 有 a * b -1∈H 。 八、(15分)(1)若无向图G 中只有两个奇数度结点,则这两个结点一定是连通的。 (2)若有向图G 中只有两个奇数度结点,它们一个可达另一个结点或互相可达吗 离散数学试题一(B 卷答案) 一、(15分)设计一盏电灯的开关电路,要求受3个开关A 、B 、C 的控制:当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。设F 表示灯亮。 u v w

离散数学集合的运算实验报告

大连民族学院 计算机科学与工程学院实验报告实验题目:集合的运算 课程名称:离散数学 实验类型:□演示性□验证性□操作性□设计性□综合性专业:网络工程班级:网络111班 学生姓名:张山学号:2011083123 实验日期:2013年12月22日实验地点:I区实验机房 实验学时:8小时实验成绩: 指导教师签字:年月日老师评语:

1 实验题目:集合的运算 实验原理: 1、实验内容与要求: 实验内容:本实验求两个集合间的运算,给定两个集合A、B,求集合A与集合B之间的交集、并集、差集、对称差集和笛卡尔乘积。 实验要求:对于给定的集合A、B。用C++/C语言设计一个程序(本实验采用 C++),该程序能够完成两个集合间的各种运算,可根据需要选择输出某种运算结果,也可一次输出所有运算结果。 2、实验算法: 实验算法分为如下几步: (1)、设计整体框架 该程序采取操作、打印分离(求解和输出分开)的思想。即先设计函数求解各部分运算并将相应结果传入数组(所求集合)中,然后根据需要打印运算结果。 (2)、建立一个集合类(Gather) 类体包括的数组a、b、c、d、e、f、g分别存储集合A、B以及所求各种运算的集合。接口(实现操作的函数)包括构造函数,菜单显示函数,求解操作函数,打印各种运算结果等函数。 (3)、设计类体中的接口 构造函数:对对象进行初始化,建立集合A与集合B。 菜单显示函数:设计提示选项,给使用者操作提示。 操作函数:该函数是程序的主题部分,完成对集合的所有运算的求解过程,并将结果弹入(存入)对应数组(集合)中,用于打印。 具体操作如下: 2 1*求交集:根据集合中交集的定义,将数组a、b中元素挨个比较,把共同元素选出来,并存入数组c(交集集合)中,即求得集合A、B的交集。 2*求并集:根据集合中并集的定义,先将数组a中元素依次存入数组g(并集集合)中,存储集合A中某元素前,先将其与已存入g中的元素依次比较,若相同则存入下一个元素,否则直接存入g中,直到所有A中元素存储完毕。接着

离散数学等价关系

离散数学是一门研究离散量结构及其相互关系的数学学科,是现代数学的重要分支。离散的含义是指不同的连接元素,主要根据离散量研究结构和它们之间的关系,其对象通常是有限的或可数的元素。离散数学已广泛应用于各个学科,尤其是计算机科学和技术。同时,离散数学也是计算机专业许多专业课程必不可少的高级课程,例如编程语言,数据结构,操作系统,编译技术,人工智能,数据库,算法设计和分析以及计算机理论基础。通过对离散数学的研究,我们不仅可以掌握处理离散结构的描述工具和方法,为后续课程创造条件,还可以提高抽象思维和严格的逻辑推理能力,打下坚实的基础。参与未来的创新研发工作。 随着信息时代的到来,以微积分为代表的连续数学在工业革命时代的主导地位发生了变化,离散数学的重要性逐渐为人们所认识。离散数学教授的思想和方法广泛地反映在计算机科学和技术及相关专业的各个领域,从科学计算到信息处理,从理论计算机科学到计算机应用技术,从计算机软件到计算机硬件,从人工智能到认知系统,所有这些都与离散数学密切相关。因为数字电子计算机是离散结构,所以它只能处理离散或离散的定量关系。因此,计算机科学本身以及与计算机科学及其应用密切相关的现代科学研究领域都面临着如何为离散结构建立相应的数学模型的问题。以及如何离散化通过连续数量关系建立的数学模型,以便可以通过计算机对其进行处理。

离散数学是一门综合性学科,由传统逻辑,集合论(包括函数),数论基础,算法设计,组合分析,离散概率,关系论,图论和树,抽象代数(包括代数系统,组)组成。,环,域等),布尔代数和计算模型(语言和自动机)。离散数学已应用于现代科学和技术的许多领域。 离散数学也可以说是计算机科学的基本核心学科。离散数学中有一个著名的典型例子-四色定理,也称为四色猜想,它是现代世界上三个主要的数学问题之一。它是由英国制图员弗朗西斯·古斯里(Francis guthrie)于1852年提出的。当他为地图着色时,他发现了一种现象:“每张地图只能用四种颜色着色,而具有共同边界的国家可以使用不同的颜色。”那么可以通过数学证明吗?100多年后的1976年,肯尼思·阿佩尔(Kenneth Appel)和沃尔夫冈·哈肯(Wolfgang Haken)使用了计算机辅助计算,这花了1200个小时和100亿次判断,终于证明了四色定理,这在世界上引起了轰动。这是离散数学与计算机科学合作的结果。 离散数学可以看作是数学与计算机科学之间的桥梁,因为离散数学不仅可以与诸如集合论和图论之类的数学知识区分开,而且与计算机科学中的数据库理论和数据结构有关,这可以导致人们进入计算机科学的思维领域,促进计算机科学的发展。

离散数学(二元关系)课后总结

第四章二元关系 例1 设A={0,1},B={a,b},求A?B ,B?A,A?A 。 解:A?B={<0,a>,<0,b>,<1,a>,<1,b>} B?A={,,,} A?A={<0,0>,<0,1>,<1,0>,<1,1>} 可见A×B≠B×A 例2、关于笛卡尔乘积的几个证明 1)如果A、B都是有限集,且|A|=m, |B|=n,则 |A?B |=mn. 证明:由笛卡尔积的定义及排列组合中的乘法原理,直接推得此定理。 2) A?Φ=Φ?B=Φ 3) ?对∪和∩满足分配律。 设A,B,C是任意集合,则 ⑴A?(B∪C)= (A?B)∪(A?C); ⑵A?(B∩C)= (A?B)∩(A?C); ⑶(A∪B)?C= (A?C)∪(B?C); ⑷(A∩B)?C= (A?C)∩(B?C) 证明⑴:任取∈A?(B∪C) ?x∈A ∧y∈B∪C ?x∈A ∧(y∈B∨y∈C) ?( x∈A ∧y∈B)∨(x∈A∧y∈C) ?∈A?B∨∈A?C ?∈(A?B)∪(A?C) 所以⑴式成立。 4)若C≠Φ,,则A?B?(A?C?B?C) ?(C?A?C?B). 证明: 必要性:设A?B,求证A?C?B?C 任取∈A?C ?x∈A∧y∈C?x∈B∧y∈C (因A?B) ?∈B?C 所以, A?C?B?C. 充分性:若CΦ≠, 由A?C?B?C 求证A?B 取C中元素y, 任取x∈A?x∈A∧y∈C?∈A?C ?∈B?C (由A?C?B?C ) ?x∈B∧y∈C? x∈B 所以, A?B. 所以A?B?(A?C?B?C) 类似可以证明A?B ?(C?A?C?B). 5) 设A、B、C、D为非空集合,则 A?B?C?D?A?C∧B?D. 证明: 首先,由A?B?C?D 证明A?C∧B?D. 任取x∈A,任取y∈B,所以x∈A∧y∈B ?∈A×B ?∈C×D (由A?B?C?D ) ?x∈C∧y∈D 所以, A?C∧B?D. 其次, 由A?C,B?D. 证明A?B?C?D 任取∈A×B ∈A×B ? x∈A∧y∈B ? x∈C∧y∈D (由A?C,B?D) ?∈C×D 所以, A?B?C?D 证毕.

离散数学 集合与关系 函数 习题 测验

一、已知A、B、C是三个集合,证明(A∪B)-C=(A-C)∪(B-C) 证明:因为 x∈(A∪B)-C?x∈(A∪B)-C ?x∈(A∪B)∧x?C ?(x∈A∨x∈B)∧x?C ?(x∈A∧x?C)∨(x∈B∧x?C) ?x∈(A-C)∨x∈(B-C) ?x∈(A-C)∪(B-C) 所以,(A∪B)-C=(A-C)∪(B-C)。 二、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>},求r(R)、s(R)和t(R),并作出它们及R的关系图。 解:r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R2=R5={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>, <5,5>} 三、证明等价关系 设R是集合A上的一个具有传递和自反性质的关系,T是A上的关系,使得∈T?∈R且∈R,证明T是一个等价关系。 证明因R自反,任意a∈A,有∈R,由T的定义,有∈T,故T自反。 若∈T,即∈R且∈R,也就是∈R且∈R,从而∈T,故T对称。 若∈T,∈T,即∈R且∈R,∈R且∈R,因R 传递,由∈R和∈R可得∈R,由∈R和∈R可得∈R,由∈R和∈R可得∈T,故T传递。 所以,T是A上的等价关系。 四、函数 设A、B、C、D是集合,f是A到B的双射,g是C到D的双射,令h:A×C→B×D且?∈A×C,h()=。证明h是双射。 证明:1)先证h是满射。 ?∈B×D,则b∈B,d∈D,因为f是A到B的双射,g是C到D的双射,所以存在a∈A,c∈C,使得f(a)=b,f(c)=d,亦即存在∈A×C,使得h()=

离散数学等价关系

离散数学等价关系 等价关系是设是非空集合A上的二元关du系,若R是自反的、对称的、传递的,则称R是A上的等价关系。给定非空集合A,若有集合S={S ,S ,…,S },其中S A,S(i=1,2,…,m)且S S = (i j)同时有S =A,称S是A的划分。研究等价关系的目的在于将集合中的元素进行分类,选取每类的代表元素来降低问题的复杂度,如软件测试时,可利用等价类来选择测试用例。 分成一块的有: 划分1:{{1,2,3,4}},对应的等价关系就是全域关系E,也就是A×A。分成两块的有: 划分2:{{1,2},{3,4}}, 划分3:{{1,3},{2,4}}, 划分4:{{1,4},{2,3}},分成三块的有: 划分5:{{1},{2,3,4}}, 划分6:{{2},{1,3,4}}, 划分7:{{3},{1,2,4}}, 划分8:{{4},{1,2,3}},分成四块的有: 划分9:{{1},{2},{3},{4}},对应的等价关系就是恒等关系I。 由划分求等价关系:∈R当且仅当a,b在同一个划分块中。扩展资料:

定义:若关系R在集合A中是自反、对称和传递的,则称R为A 上的等价关系。所谓关系R 就是笛卡尔积 A×A 中的一个子集。A 中的两个元素x,y有关系R,如果(x,y)∈R。我们常简记为 xRy。 自反:任意x属于A,则x与自己具有关系R,即xRx; 对称:任意x,y属于A,如果x与y具有关系R,即xRy,则y与x也具有关系R,即yRx; 传递:任意x,y,z属于A,如果xRy且yRz,则xRz。 x,y具有等价关系R,则称x,y R等价,有时亦简称等价。

离散数学-第七章二元关系课后练习习题及答案讲课教案

第七章作业 评分要求: 1. 合计100分 2. 给出每小题得分(注意: 写出扣分理由). 3. 总得分在采分点1处正确设置. 1 设R={|x,y∈N且x+3y=12}.【本题合计10分】 (1) 求R的集合表达式(列元素法); (2) 求domR, ranR; (3) 求R?R; (4) 求R?{2,3,4,6}; (5) 求R[{3}]; 解 (1) R={<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}【2分】 (2) domR={0,3,6,9,12}, ranR={0,1,2,3,4}【2分】 (3) R?R={<3,3>, <0,4>}【2分】 (4) R?{2,3,4,6}={<3,3>, <6,2>}【2分】 (5) R[{3}]={3}【2分】 2 设R,F,G为A上的二元关系. 证明: (1)R?(F∪G)=R?F∪R?G (2)R?(F∩G)?R?F∩R?G (3)R?(F?G)=(R?F)?G. 【本题合计18分:每小题6分,证明格式正确得3分,错一步扣1分】证明 (1)?, ∈R?(F∪G) ??t (xRt∧t(F∪G)y) 复合定义 ??t(xRt∧(tFy∨tGy) ∪定义 ??t((xRt∧tFy)∨(xRt∧tGy)) ∧对∨分配律 ??t(xRt∧tFy)∨?t(xRt∧tGy) ?对∨分配律 ?x(R?F)y∨x(R?G)y 复合定义 ?x(R?F∪R?G)y ∪定义 得证 (2)?, x(R?(F∩G))y ??t(xRt∧t(F∩G)y) 复合定义 ??t(xRt∧(tFy∧tGy)) ∩定义 ??t((xRt∧tFy)∧(xRt∧tGy)) ∧幂等律, ∧交换律, ∧结合律 ??t(xRt∧tFy)∧?t(xRt∧tGy) 补充的量词推理定律 ?x(R?F)y∧x(R?G)y 复合定义 ?x(R?F∪R?G)y ∪定义

离散数学等价关系

等价类: 在离散数学中,等价关系是指定义在集合A上的关系,满足自反的、对称的和传递的等性质。设R是定义在集合A上的等价关系,与A中一个元素a有关系的所有元素的集合叫做a的等价类。等价类应用十分广泛,如在编程语言中,我们使用等价类来判定标识符是不是表示同一个事物。 定义: 在离散数学中,等价关系是指定义在集合A上的关系,满足自反的、对称的和传递的等性质。设R是定义在集合A上的等价关系,与A中一个元素a有关系的所有元素的集合叫做a的等价类。A的关于R的等价类记作。当只考虑一个关系时,我们省去下表R并把这个等价类写作[a]。 在软件工程中,是把所有可能输入的数据,即程序的输入域划分成若干部分(子集),然后从每一个子集中选取少数具有代表性的数据作为测试用例,从而减少了数据输入量从而提高了效率,称之为等价类方法,该方法是一种重要的、常用的黑盒测试用例设计方法。 分类: 在离散数学中,等价类的划分基于以下定理:设R是定义在集合A上的等价关系。那么R的等价类构成S的划分。反过来,给定集合S的划分{ |i∈I},则存在一个等价关系R,它以集合作为它的等价类。 因为等价关系的a 在a 中和任何两个等价类要么相等要么不

交集不相交的性质。得出X 的所有等价类的集合形成X 的集合划分划分: 所有X 的元素属于一且唯一的等价类。反过来,X 的所有划分也定义了在X 上等价关系。 在软件工程中等价类划分及标准如下: 划分等价类 等价类是指某个输入域的子集合。在该子集合中,各个输入数据对于揭露程序中的错误都是等效的,并合理地假定:测试某等价类的代表值就等于对这一类其他值的测试,因此,可以把全部输入数据合理划分为若干等价类,在每一个等价类中取一个数据作为测试的输入条件就可以用少量代表性的测试数据取得较好的测试结果。等价类划分有两种不同的情况:有效等价类和无效等价类。 1)有效等价类 是指对于程序的规格说明来说是合理的、有意义的输入数据构成的集合。利用有效等价类可检验程序是否实现了规格说明所规定的功能和性能。 2)无效等价类 指对程序的规格说明是不合理的或无意义的输入数据所构成的集合。对于具体的问题,无效等价类至少应有一个,也可能多个。 设计测试用例时,要同时考虑这两种等价类。因为软件不仅要能接收合理的数据,也要能经受意外的考验,这样的测试才能确保软件具有更高的可靠性。 3.划分等价类的标准

离散数学期末复习题

离散数学期末复习题 第一章集合论 一、判断题 (1)空集是任何集合的真子集. ( 错 ) (2){ }φ是空集. ( 错 ) (3){}{ }a a a },{∈ ( 对 ) (4)设集合{}{ }{}{}A A 22,1,2,1,2,1?=则. ( 对 ) (5)如果 B A a ??,则A a ?或B a ?. ( 错 ) 解 B A a ??则B A B A a ?=?∈,即A a ∈且B a ∈,所以A a ?且B a ? (6)如果A ∪.,B A B B ?=则 ( 对 ) (7)设集合},,{321a a a A =,},,{321b b b B =,则 },,,,,{332211><><><=?b a b a b a B A ( 错 ) (8)设集合}1,0{=A ,则}1},0{,0},0{,1,,0,{><><><><=φφρ是A 2到A 的关系. ( 对 ) 解 A 2}},1{},0{,{A φ=, =?A A 2}1,,0,,1},1{,0},1{,1},0{,0},0{,1,,0,{><><><><><><><>

离散数学集合运算c语言

离散数学集合运算(第一次作业) C语言写法: #include //求长度的运算 void main() { int i,j,n; float A[]; float B[]; float C[]; \\用于存放A于B的交 float D[]; \\用于存放A与B的并 float E[]; \\用于存放A与B的差 float F[]; \\用于存放A与B的对称差 float G[]; \\用于存放A的幂集 int k; char x; n=strlen(A); for(i=0;i

printf(“\n”); } if(i >=n) { if(G[0]) cout <

离散数学-第七章二元关系课后练习习题及答案

离散数学-第七章二元关系课后练习习题及答案

第七章作业 评分要求: 1. 合计100分 2. 给出每小题得分(注意: 写出扣分理由). 3. 总得分在采分点1处正确设置. 1 设R={|x,y∈N且x+3y=12}.【本题合计10分】 (1) 求R的集合表达式(列元素法); (2) 求domR, ranR; (3) 求R?R; (4) 求R?{2,3,4,6}; (5) 求R[{3}]; 解 (1) R={<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}【2分】 (2) domR={0,3,6,9,12}, ranR={0,1,2,3,4}【2分】 (3) R?R={<3,3>, <0,4>}【2分】 (4) R?{2,3,4,6}={<3,3>, <6,2>}【2分】 (5) R[{3}]={3}【2分】 2 设R,F,G为A上的二元关系. 证明:

理定律 ?x(R?F)y∧x(R?G)y 复合定义 ?x(R?F∪R?G)y ∪定义 得证 (3)?, ∈R?(F?G) ??s (∈R∧∈(F?G)) ?定义 ??s (∈R∧?t (∈F∧∈G))) ?定义 ??s?t(∈R∧∈F∧∈G) 辖 域扩张公式 ??t?s((∈R∧∈F)∧∈G)存在量词交换 ??t(?s(∈R∧∈F)∧∈G)辖域收缩公式 ??t(∈(R?F)∧∈G) 复合定义 ?∈(R?F)?G 复合定义 得证 3 设F={|x-y+2>0∧x-y-2<0}是实数集R上的二元关系, 问F具有什么性质并说明理由. 【本题合计10分:每种性质2分----答对得1分,

离散数学作业1_集合与关系答案

离散数学作业1_集合与关系 1. 设A、B、C为任意三个集合,判断下列命题的真与假。如命题为真,则证明之;否则,举反例说明。 (1)若A?C=B?C,则A=B(假命题) (2)若A?C=B?C ,则A=B(假命题) (3)若A?C=B?C 且A?C=B?C ,则A=B (真命题,参考ppt 1.2节例8) 2.证明A-B=A∩~B. 证明思路:任取x∈A-B?……? x∈A∩~B 证明:任取x∈A-B?x∈A且x/∈B(根据相对补的定义) ? x∈A且x∈~B(根据绝对补的定义) ? x∈A∩~B 3. 设A={1,2,3,4,5,6},下面各式定义的R都是A上的二元关系。试分别以序偶、关系矩阵、关系图三种形式分别写出R。 (1) R={|x整除y};(2) R={|x是y的倍数}; (3) R={|(x-y)2∈A};(4) R={|x/ y是素数}。 解: (1) R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4.>,<2,6>,<3,3 >,<3,6>,<4,4>,<5,5>,<6,6>} (2) R={<1,1>,<2,1>,<2,2>,<3,1>,<3,3>,<4,1>,<4,2>,<4,4>,<5,1>,<5,5

>,<6,1>,<6,2>,<6,3>,<6,6>} (3) R={<1,2>,<1,3>,<2,1>,<2,3>,<2,4>,<3,2>,<3,4>,<3,1>,<3,5>,<4,3 >,<4,5>,<4,2>,<4,6>,<5,4>,<5,6>,<5,3>,<6,5>,<6,4>} (4) 质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。 100以内的质数有2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,在100内共有25个质数。 注:1既不是质数也不是合数。因为它的约数有且只有1这一个约数。 R={<2,1>,<3,1>,<4,2>,<5,1>,<6,2>,<6,3>} 4. 设R是A到B的二元关系,证明:对于A的任意子集A1和A2, R(A1∩A2) = R(A1)∩R(A2)当且仅当? a∈A,b∈A,且a≠b有R(a)∩R(b) = Φ. 证明(1)先证充分性(由后推前)即已知 ? a∈A, b∈A ,有R(a)∩R(b) = Φ, 目的是证明对于A的任意子集A1和A2, 有 R(A1∩A2) = R(A1)∩R(A2) (下面通过证明R(A1∩A2) ?R(A1)∩R(A2),以及R(A1)∩R(A2) ? R(A1∩A2))

二元关系(离散数学)

第二章二元关系 习题2.1 1. a)R = {<0, 0>, <0, 2>, <2, 0>, <2, 2>} b)R = {<1, 1>, <4, 2>} 2. R1? R2 = {<1, 2>, <2, 4>, <3, 3>, <1, 3>, <4, 2>} R1? R2 = {<2, 4>} dom R1= {1, 2, 3} dom R2= {1, 2, 4} ran R1= {2, 3, 4} ran R2= {2, 3, 4} dom (R1? R2) = {1, 2, 3, 4} ran (R1? R2) = {4} 3. 证明:(根据定义域和值域的定义进行证明) 因为 x ∈ dom (R1? R2) 当且仅当有y ∈ B使得 ∈ (R1? R2) 当且仅当有y ∈ B使得 ∈ R1或 ∈ R2 当且仅当有y ∈ B使得 ∈ R1或有y ∈ B使得 ∈ R2 当且仅当x ∈ dom (R1) 或x ∈ dom (R2) 当且仅当x ∈ dom (R1) ? dom (R2) 所以,dom (R1? R2) = dom (R1) ? dom (R2) 。 因为 若x ∈ ran (R1? R2),则有x ∈ A使得 ∈ (R1? R2) ; 有x ∈ A使得 ∈ R1且 ∈ R2 ; 有x ∈ A使得 ∈ R1且有x ∈ A使得 ∈ R2 ; x ∈ ran (R1) 且x ∈ ran (R2); x ∈ ran (R1) ? ran (R2)。 所以,ran (R1? R2) ? ran (R1) ? ran (R2)。 4. L = {<1, 2>, <1, 3>, <1, 6>, <2, 3>, <2, 6>, <3, 6> }; D = {<1, 1>, <1, 2>, <1, 3>, <1, 6>, <2, 2>, <2, 6>, <3, 3>, <3, 6>, <6, 6> };

离散数学作业2_集合与关系答案

离散数学作业2_集合与关系 1. 设A={1,2,3,4,5},R是集合A上的二元关系,aRb当且仅当a,<1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>} M R2=M R⊙M R= 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 所以,R2={……} M R3= M R2⊙M R= 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 所以,R3={……} (2) aR2b的充要条件是b-a≧2 (3) aR3b的充要条件是b-a≧3

2. 设A={a,b,c}, R={,,},求R2,R3,R4,R∞,R* 解: M R= 0 1 0 0 0 1 1 0 0 所以 M R2= 0 0 1 1 0 0 0 1 0 M R3= 1 0 0 0 1 0 0 0 1 继续计算可得M R4= M R, 所以, M R5= M R2, M R6= M R3, M R7= M R,…. 所以M R∞=M R∨M R2∨M R3=….,M R*=M I A∨M R∞ 因此, R2={……}, R3={……}, R4={......}, R∞={......},R*={......} 3.分别对下图中所给的两个关系,求R n,n N。 b o o a a o b o o c c o o d d o o e ⑴⑵ 解: (1) R={,,,}, 因此,

离散数学等价关系

概念问题 二进制关系:A和B的笛卡尔积的子集称为从A到B的二进制关系。集合上的关系:从a到a的关系。 关系的性质 反射,抗反射,对称,抗对称和传输。 没有列出概念,但应注意以下方面: (1)所有属性的概念都是逻辑表达式,即判断是非,必须严格按照定义判断是非; (2)它们都是用全名量词表示的逻辑表达式,因此必须为真才能保持一致; (3)它们全部由隐含条件语句表示。如果前提为假,则它也为真,也就是说,所有未出现在真之后再为假的内容都为真。 关系代表 (1)设置符号(适合定义和表示); (2)图表表示(适合直观感觉和观察特性); (3)关系矩阵表示(适合计算);特别地,关系矩阵是布尔矩阵,即逻辑矩阵,其描述A中的第i个元素是否与B中的第j个元素有关。 关系运作

(1)交叉,合并与区别 R1?R2————M1ùM2 R1èR2————M1úM2 (2)综合 合成操作非常重要且容易出错。注意其顺序以及对集合,图形和矩阵的相应计算。 自我及其综合运算形成力量。 例如,R 2对应于由点直接连接的边,这些点可以从图形上的每个点分两步到达。 另一个例子 R1°R2 ————M2M1 R ^ 2 ————M ^ 2 关系的应用 (1)n元关系的应用 一般来说,当2元关系扩展到N元关系时,它就成为数据库的基本框架。N元有序对是N个字段的记录,因此关系操作对应于数据库操作。我们只知道这部分内容(与数据库重复)。 (2)封闭的应用 首先,介绍了三种闭包的概念。如果用一句话来概括,R的自反/对称/传递闭包是包含R的自反/对称/传递关系中最小的。

然后其应用着重于掌握传递闭包的应用,它可以显示传递性直接通过连接边可到达的点的连通性。 然后讨论三个闭包的计算: (3)等价关系的应用 首先是等价关系的概念,以及等价类和划分的扩展概念。 其次,等价关系的应用仅仅是分类。因为等价与划分之间存在一一对应的关系。 A.如果一个关系是集合a上的等价关系,写出每个元素的等价类,然后删除重复项,则由非重复等价类组成的集合就是原始集合a的除法。B,如果子集族是集合A的划分,则根据“属于同一个子集的人如果有关系就可以配对”的规则,二元有序对的集合必须满足反射性,对称性和可传递性,是等价的关系。 (4)偏序关系的应用 第一个是偏序的概念,并扩展了“小于或等于”,“小于”和“可比”。然后是整个顺序,然后是良好顺序(自己比较概念)。

相关文档 最新文档