离散数学-04-关系的性质

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

集合与关系《应用离散数学》 第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)表示，即

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

集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体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、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图 3、序偶与迪卡尔积 本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求] 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题] P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析] 1、集合的概念 因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。 2、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析] 例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解 }}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A }}2,1{},2{},1{,{)(φρ=B 于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ

离散数学关系性质的C++或C语言判断实验报告

1.【实验目的】 对称： 通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法 自反： 通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 2.【实验内容】 已知关系R 由关系矩阵M 给出，要求判断由M 表示的这个关系是否为对称关 系。假定R 的关系矩阵为：?????? ? ??=1234210330124321M 3.【实验要求】 C 语言编程实现 4.【算法描述】 对称： 从给定的关系矩阵来判断关系R 是否为对称是很容易的。若M （R 的关系矩阵）为对称矩阵，则R 是对称关系；若M 为反对称矩阵，则R 是反对称关系。因为R 为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。 算法实现： （1） 输入关系矩阵M （M 为n 阶方阵）； （2） 判断对称性，对于i=2，3，….，n ；j=1，2,……，i-1，若存在m ij =m ji ， 则R 是对称的； （3） 判断反对称性； （4） 判断既是对称的又是反对称的； （5） 判断既不是对称的又不是反对称的； （6） 输出判断结果。

自反： 从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。 算法实现 （1）输入关系矩阵M（M为n阶方阵）。 （2）判断自反性，对于i=1，2，….，n；若存在m =0，则R不是自反 ii =1，则R是自反的；否则R既不是自反关系也不是的；若存在m ii 反自反关系。 （3）输出判断结果。 源代码 #include void z(); void r(); void main() { int d; while(d) { printf("欢迎使用关系性质的判断系统\n\n 1. 对称关系的判断 2. 自反关系的判断\n\n请输入选项："); scanf("%d",&d); switch(d){ case 1: r();break; case 2: z();break; case 0: break; }

离散数学二元关系传递性判别、闭包方法实验报告

离散数学二元关系传递性判别、闭包方法实验报告 学院：理学院班级：11信息与计算科学1班 姓名：***学号：************* 一、实验目的 1. 通过上机程序，进一步加深对二元关系传递性判别，自反闭包，对称闭包，传递闭 包的理解。 2. 掌握传递性判别，Warshall算法。 3. 学会用程序解决离散数学中的问题。 4. 增强我们编写程序的能力 二、实验内容 实验1：二元关系传递性判别 实验2：有限集上给定关系的自反、对称和传递闭包（用Warshall算法）。 三、实验环境 在microsoft visual c++实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。 四、实验原理和实现过程 实验1： #include using namespace std; void main() { intn,i,j,k; int m=0; //m是判断传递关系计数参数 cout<<"请输入矩阵的行列数n:"; cin>>n; int a[20][20]; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout<<"请输入a["<>a[i][j]; } } //输入R矩阵 cout<<"R的关系矩阵为："<

} cout< using namespace std; void main() { intn,i,j; cout<<"请输入矩阵的行列数n:"; cin>>n; int a[20][20]; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout<<"请输入a["<>a[i][j]; } } cout<<"R的关系矩阵为："<

离散数学关系的闭包运算

《离散数学》 实验报告 学院软件学院 专业软件工程 指导教师邹丽娜 学号10008118 姓名冯立勇 提交日期2011-12-25

实验二 关系的闭包运算 一 、实验目的 熟悉关系的闭包运算，编程实现关系闭包运算算法。 一 、实验内容 利用矩阵求解有限集上给定关系的自反、对称和传递闭包。 三. 实验过程 1. 算法分析： 在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）；传递闭包则有两种算法（二选一即可）： 算法1：直接根据 n i i R R t 1 )(== 计算，过程略。 算法2：Warshall 算法(1962) 设R 的关系矩阵为M (1)令矩阵A=M (2)置i=1 (3)对所有的j ，若A[j ，i]=1，则 对于 k=1，2，…，n ，令A[j ，k]=A[j ，k]+A[i ，k] 注：此处为逻辑加，可以使用运算符|| (4) i=i+l ． (5)若i ≤n ，则转到(3)，否则结束． 流程图

2. 程序代码： #include void output(int s[][100]); void zifan(int s2[][100]); void duichen(int s2[][100]); void chuandi2(int s2[][100]); void chuandi1(int s2[][100]); void aa(); int s[100][100],z; int d,n ,i,j; int main(){aa();return 0;} void aa() { printf("请输入矩阵的行数(必须小于10)\n "); scanf("%d",&n); printf("请输入矩阵的列数(必须小于10)\n "); scanf("%d",&d); printf("请输入关系矩阵\n"); for(i=0;i

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

第四章二元关系 例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()＝

《离散数学(第三版)》方世昌 的期末复习知识点总结

《离散数学》期末复习提要 《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。 离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容 1、集合论部分（集合的基本概念和运算、关系及其性质）； 2、数理逻辑部分（命题逻辑、谓词逻辑）； 3、图论部分（图的基本概念、树及其性质）。 学习建议 离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 教学要求的层次 各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。 一、各章复习要求与重点 第一章集合 [复习知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、De Morgan 律等），文氏（Venn）图 3、序偶与迪卡尔积 本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]

1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题] P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析] 1、集合的概念 因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。 2、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析] 例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解 }}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A }}2,1{},2{},1{,{)(φρ=B 于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ 例2 设{}{}Φ=,,,,b a b a A ，试求： (1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。 解 (1){}{}{ }Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{ }Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~???=??? 证明

离散数学符号表

《离散数学》符号表 ? 全称量词（任意量词） ? 存在量词 ├ 断定符（公式在L 中可证） ╞ 满足符（公式在E 上有效，公式在E 上可满足） ┐ 命题的“非”运算 ∧ 命题的“合取”（“与”）运算 ∨ 命题的“析取”（“或”，“可兼或”）运算 → 命题的“条件”运算 ? 命题的“双条件”运算的 B A ? 命题A 与B 等价关系 B A ? 命题A 与B 的蕴涵关系 * A 公式A 的对偶公式 wff 合式公式 iff 当且仅当 V 命题的“不可兼或”运算（ “异或门” ） ↑ 命题的“与非” 运算（ “与非门” ） ↓ 命题的“或非”运算（ “或非门” ） □ 模态词“必然” ◇ 模态词“可能” φ 空集 ? 属于（?不属于） A μ（·） 集合A 的特征函数 P （A ） 集合A 的幂集 A 集合A 的点数 n A A A ??? （n A ） 集合A 的笛卡儿积 R R R =2 )(1R R R n n -= 关系R 的“复合” 0? 阿列夫零 ? 阿列夫

? 包含 ? 真包含 ∪ 集合的并运算 ∩ 集合的交运算 - （～） 集合的差运算 ⊕ 集合的对称差运算 m + m 同余加 m ? m 同余乘 〡 限制 R x ][ 集合关于关系R 的等价类 A /R 集合A 上关于R 的商集 )(A R π 集合A 关于关系R 的划分 )(A R π 集合A 关于划分π的关系 ][a 元素a 产生的循环群 R a ][ 元素a 形成的R 等价类 r C 由相容关系r 产生的最大相容类 I 环，理想 )/(n Z 模n 的同余类集合 ) (mod k b a ≡ a 与b 模k 相等 )(R r 关系R 的自反闭包 )(R s 关系R 的对称闭包 +R ，)(R t 关系R 的传递闭包 *R ，)(R rt 关系R 的自反、传递闭包 .i H 矩阵H 的第i 个行向量 j H . 矩阵H 的第j 个列向量 CP 命题演绎的定理（CP 规则） EG 存在推广规则（存在量词引入规则） ES 存在量词特指规则（存在量词消去规则） UG 全称推广规则（全称量词引入规则）

二元关系(离散数学)

第二章二元关系 习题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> }；

离散数学作业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)）

《离散数学(第三版)》方世昌的期末深刻复习知识点归纳含例题

《离散数学（第三版）》方世昌的期末复习知识点总结含例题 一、各章复习要求与重点 第一章集合 [复习知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、De Morgan 律等），文氏（Venn）图 3、序偶与迪卡尔积 本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求] 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [疑难解析] 1、集合的概念 因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。 2、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功

训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析] 例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解 }}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A }}2,1{},2{},1{,{)(φρ=B 于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ 例2 设{}{}Φ=,,,,b a b a A ，试求： (1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。 解 (1){}{}{}Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{}Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~???=??? 证明 ()()()()()() ()()()()()() ()()()()()() B A B A B A B A B B B A A B A A B B A A B A B A B A ~~~~~~~~~~~~~???=Φ?????Φ=???????=?????=??? 第二章 二元关系 [复习知识点] 1、关系、关系矩阵与关系图 2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包）

离散数学作业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={,,,}, 因此,

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

离散数学作业 作业6 ——等价关系 1. 设R和S均为A上的等价关系，确定下列各式，哪些是A上的等价关系？如果是，证明之；否则，举反例说明。 （1）R∩S （2）R∪S （3）r (R-S) （4）R- S （5）R?S （6）R2 解：(1),(6)正确，其余错误。 2. R是集合A上的二元关系， a,b,c ,若aRb,且bRc,有cRb,则称R是循环关系。证明R是自反和循环的，当且仅当R是一等价关系。 分析: 需要证明两部分: (1)已知R是自反和循环的，证明:R是一等价关系 (2)已知R是一等价关系, 证明R是自反和循环的. 证明：（1）先证必要性。只需要证明R是对陈的和传递的。 任取(x,y)∈R。因为R是自反的，所以(y,y)∈R。由R是循环的可得(y,x)∈R，即R是对陈的。 任取(x,y)，(y,z)∈R。因R是循环的，所以(z,x)∈R。由R对称性得(x,z)∈R，即R是传递的。 （2）证充分性。只需要证明R是循环的。任取(x,y)，(y,z)∈R，下证(z,x)∈R。由于R是传递的，所以(x,z)∈R。又由R是对称的得(z,x)∈R。所以R是循环的。 3. 设|A|=n，在A上可以确定多少个不同的等价关系？ 解：2n!/((n+1)n!n!)

4. 给定集合S={ 1 , 2 , 3, 4, 5 }，找出S 上的等价关系R ，此关系R 能够产生划分{{1，2}，{3}，{4，5}}，并画出关系图。 解：{(1,2),(2,1),(4,5),(5,4)}S R I =? 5. 设A={1，2，3，4，5}。R 是集合A 上的二元关系，其关系矩阵如下图所示。求包含R 的最小等价关系和该等价关系所确定的划分。 ????????????????=0010001000 000000101000001R M 分析: 可以证明tsr(R)是包含R 的最小等价关系. 解：包含R 的最小等价关系的矩阵表示如下： 100000 1010001010 101000101?? ? ? ? ? ? ??? 上述等价关系确定的划分为{{1},{2,4},{3,5}}. 6. 自学华氏(WalShall)算法，写出算法的基本概念、基本步骤和一个 求解传递闭包的具体实例，并可清晰讲解算法整体实现过程。 7. （选做题）设R 与S 是A 上的等价关系，证明： （1）R S 是A 上的等价关系，iff R S=S R ； （2）R ∪S 是A 上的等价关系，if R S ?S 且 S R ?R. 分析: iff 是if and only if 的缩写, 是当且仅当的意思. 证明：（1）先证必要性。任取(x,z)∈R S ，则存在y 使得xRy,ySz 。因为R 与S 是A 上的等价关系，所以R 与S 是对陈的，即yRx,zSy,所以

离散数学N元集合关系个数计算

Author ：ssjs Mail ： 看了离散数学中的关系整理了一点关于n 元集合中各种关系的计算，现写下这个方便大家学习交流理解。对文章所致一切后果不负任何责任，请谨慎使用。 如有错误之处请指正。 定义： 1，对称：对于a,b R a b ∈∈∈),b (),a (,A 有如果只要 2，反对称：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当 3，自反：如果对每个元素R ),(A a ∈∈a a 有 4，反自反：如果对于每个R ),(A a ?∈a a 有 5，传递：如果对R ),(,R ),(R ),(,A ,,∈∈∈∈c a c b b a c b a 则且 6，非对称：如果R ),(R ),(?∈a b b a 推出【注】其中是含（a,a)这样的有序对的。 【重要】集合A 的关系是从A 到A 的关系 （也就是说集合A 的关系是A A ?的子集）。 如下结论： N 元集合上的自反关系数为：)1(2 -n n N 元集合上的对称关系数为：2/)1(2+n n N 元集合上的反对称关系数为：2/)1(n 3 2-n n N 元集合上的非对称关系数为：2/)1(3-n n N 元集合上的反自反关系数为：)1(n 2-n N 元集合上的自反和对称关系数为：2/)1(n 2-n N 元集合上的不自反也不反自反关系数为：)1(n n 222 2-?-n 下面是上面结论的计算 1，自反 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由自反定义可知，对R ),(A a ∈∈?a a 有所以n 个有序对()).....3,2,1i X ,X (n i i =其中一定在所求关系中，否则的话此关系就不是自反的了，那么还有n n -2个有序对，所以由集合子集对应二进制串可得自反关系数为)1(n 222--=n n n 下图有助于理解。 （1,1) (2,2).......(n,n) | (1,2) (1,3).........(n-1,n) N n n -2个有序对 2，对称 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由对称定义可知，对于R a b b ∈∈∈),b (),a (,A ,a 有只要。另外知道在n 平方个有序对中有n 个有序对()).....3,2,1i X ,X (n i i =其中，相应的就有n n -2个有序对（X,Y)且X Y ≠，定义可知后面 的n n -2个有序对只能成对出现，所以有2/)(n 2n -对。前面的那n 对可以出现任意多对。

010_离散数学

湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：考试科目名称：离散数学 一、试卷结构 1) 试卷成绩及考试时间 本试卷满分为100分，考试时间为180分钟。 2)答题方式：闭卷、笔试 3)试卷内容结构 集合论40% 数理逻辑40% 图论20% 4)题型结构 a: 填空题，5小题，每小题5分，共25分 b: 计算题，3小题，每小题10分，共30分 c: 证明题，3小题，每小题15分，共45分 二、考试内容与考试要求 1、集合论 考试内容 集合及其表示集合的运算与性质二元关系的概念二元关系的五种性质关系矩阵与关系图关系的各种运算与性质关系闭包与性质相容关系等价关系序关系部分函数、满射、内射、双射的概念可逆、左可逆、右可逆函数特征函数集合的基数与性质 考试要求 （1）理解集合的表示、二元关系的概念、部分函数、满射、内射、双射的概念可逆、左可逆、右可逆函数的概念； （2）掌握集合的运算与性质、关系的五种性质、关系的运算与性质、关系闭包与性质、相容关系、等价关系、序关系. （3）了解特征函数集合的基数与性质．

2、数理逻辑 考试内容 命题与命题的真值五个基本联结词命题符号化合式公式真值表合式公式的类型等价式、蕴含式的证明范式和判定问题求主范式的方法变元、谓词和量词量词的辖域、前束范式合式公式的解释、求合式公式在给定解释下真值的方法 考试要求 （1）理解命题与命题的真值、联结词、合式公式与真值表、变元、谓词和量词等概念． （2）掌握合式公式的类型、等价式、蕴含式的证明、求主范式的方法、合式公式的解释、以及求在给定解释下真值的方法． （3）了解量词的辖域、前束范式． 3、图论 考试内容 图的基本概念路与回路和连通性图的矩阵表示欧拉图和哈密顿图平面图对偶图与着色树与生成树根树及其应用 考试要求 （1）理解图、路、回路和连通性等基本概念． （2）掌握一些特殊图类的性质，树的特征与应用． 三、参考书目 [1] 左孝凌等，《离散数学》，上海科技文献出版社，1982年 [2] 王兵山、张强、毛晓光，《离散数学》，国防科技大学出版社，1998年 [3] 耿素云、屈宛玲，《离散数学》，高等教育出版社，2003年

离散数学测验题集合与关系(2012)答案

离散数学测验题——集合与关系(2012--2013) 班级学号姓名 注意事项： 1.独立完成，严禁抄袭！满分100分。 2.最迟上交时间：2012年10月31日（星期三）上课之前交齐。过时不交，成绩记为零。 3.在A4大小的纸上完成并装订好。 一、（52分）给定集合A={a, b, c, d}，且A中的关系R： R ={, , , , , } 请回答以下各问题： 1.写出R的关系矩阵。（5分） 解： 0110 1000 0001 0101 R M ?? ?? ?? = ?? ?? ?? . 2.画出R的关系图。（5分） 3.求包含R的最小的等价关系R*(用关系矩阵表示) （15分），并写出商集A/R*（6分）。 解：由 0110 1000 0001 0101 R M ?? ?? ?? = ?? ?? ?? ，得到 () 1110 1100 0011 0101 A r R R I M M M ?? ?? ?? =∨= ?? ?? ?? ，()()() 1110 1101 1011 0111 T sr R r R r R M M M ?????? =∨= ?? ?? ?? ,

() ()()2 34() ()()11111111 (11111) 11 1sr R sr R sr R M M M ??????====?????? 故()()*3 () ()()2()...tsr R sr R sr R sr R R M M M M M ∨∨∨==1111111111111 111????? ?=?????? ， 即R *={, , , ,, , , , , , , , , , , }. 根据此等价关系中各元素之间的关系以及具有等价关系的元素应该在同一个划分块中的原则可知， A /R *={ {a,b,c,d} }. 4.分别用关系矩阵表示出R 的自反闭包r (R ) （4分）、对称闭包s (R ) （4分）。 解：()0 1101 0001 1101000010011000001001000110101000 10 10 1A r R R I M M M ??????????????????=∨=∨=?????????????????? ， ()0110100110010 1 1 1T s R R R M M M ??????=∨=?????? . 5.求传递闭包t (R )。（写出计算步骤）（10分） 解：0 1101 00000010 10 1R M ????? ?=?? ????，经计算2R R M M =⊙1 001011001011 10 1R M ????? ?=?????? ， 23R R M M =⊙01 111 00111011 111R M ????? ?=??????