离散数学 关系R的传递闭包问题

用C语言编写程序，实现用Warshall算法解决关系R的传递闭包问题

1 1 0 0 0 0 0

0 0 0 1 0 0 0

R= 0 0 0 0 1 0 0

0 1 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

算法：

#include "stdio.h"

void main()

{

int i,j,n;

int a[7][7];

for(i=0;i<7;i++)

{

for(j=0;j<7;j++)

scanf("%d",&a[i][j]);

}

printf("the original matrix is: \n");

for(i=0;i<7;i++)

{

for(j=0;j<7;j++)

printf("%7d",a[i][j]);

printf("\n");

}

printf("\n");

for(j=0;j<7;j++)

{

for(i=0;i<7;i++)

{

if(a[i][j]==1)

{

for(n=0;n<7;n++)

a[i][n]=a[i][n]|a[j][n];

}

}

}

printf("the result is:");

printf("\n\n");

for(i=0;i<7;i++)

{

for(j=0;j<7;j++)

printf("%7d",a[i][j]);

printf("\n");

}

}

运行结果：

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

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

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

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

实验题目：集合的运算 实验原理： 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。 菜单显示函数：设计提示选项，给使用者操作提示。 操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。 具体操作如下：

1*求交集：根据集合中交集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。 2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着把b中元素依次存入数组g（并集集合）中，存储前将b中每个元素依次与已存入数组g中的集合A的元素比较，若数组g中没有与该元素相同的元素，则将该元素存入g（并集集合）中，否则进行下一次比较，直到所有b中元素比较并存储完毕，即求得A与B 的并集。 3*求差集：根据集合中差集的定义知，差集分为两部分，A对B的差集（数组d）和B对A的差集（e）。设计求解A对B的差集，将集合A中元素依次与B中元素比较，若B中无元素与该元素相同，则将其存入数组d中（同时删除d中相同的元素，操作方法与求并集时删除相同元素类似），否则进行下一轮比较，直到A中所有元素比较完毕，即求得A对B的差集（数组d）。求解B对A的差集方法与求解A对B 的差集类似，这里不再重复。 4*求对称差：根据集合中对称差集的定义，将3*中所求两部分差集求并集并存入数组f中即可。操作过程与求并集相似，这里不再重复。 5*求笛卡尔乘积：根据集合中笛卡尔乘积集的定义，分为A*B和B*A。先设计A*B是我算法，将a中元素循环依次与b中元素配对即可。求B*A与求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 ．反自反和传递的

离散数学知识点总结

离散数学知识点总结 一、各章复习要求与重点 第一章 集 合 [复习知识点] 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的关系矩阵为："<

离散数学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 个有序对

离散数学第三章集合的基本概念和运算知识点总结

集合论部分 第三章、集合的基本概念和运算 3.1 集合的基本概念集合的定义与表示 集合与元素 集合没有精确的数学定义 理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员集合的表示 列元素法A={ a, b, c, d } 谓词表示法B={ x | P(x) } B 由使得P(x) 为真的x构成常用数集 N, Z, Q, R, C 分别表示自然数、整数、有理数、 实数和复数集合，注意0 是自然数. 元素与集合的关系：隶属关系 属于∈，不属于? 实例 A={ x | x∈R∧x2-1=0 }, A={-1,1} 1∈A, 2?A 注意：对于任何集合A 和元素x (可以是集合)， x∈A和x?A 两者成立其一，且仅成立其一.

集合之间的关系 包含（子集）A?B??x (x∈A→x∈B) 不包含A?B??x (x∈A∧x?B) 相等A = B?A?B∧B?A 不相等A≠B 真包含A?B?A?B∧A≠B 不真包含A?B 思考：≠和?的定义 注意∈和?是不同层次的问题 空集?不含任何元素的集合 实例{x | x2+1=0∧x∈R} 就是空集 定理空集是任何集合的子集 ??A??x (x∈?→x∈A) ?T 推论空集是惟一的. 证假设存在?1和?2，则?1??2 且?1??2，因此?1=?2全集E 相对性

在给定问题中，全集包含任何集合，即?A (A?E ) 幂集定义P(A) = { x | x?A } 实例 P(?) = {?}， P({?}) = {?,{?}} P({1,{2,3}})={?,{1},{{2,3}},{1,{2,3}}} 计数 如果|A| = n，则|P(A)| = 2n 3.2 集合的基本运算 集合基本运算的定义??-~⊕ 并A?B = { x | x∈A∨x∈B } 交A?B = { x | x∈A∧x∈B } 相对补A-B = { x | x∈A∧x?B } 对称差A⊕B = (A-B)?(B-A) = (A?B)-(A?B) 绝对补~A = E-A 文氏图（John Venn）

离散数学关系的闭包运算

《离散数学》 实验报告 学院软件学院 专业软件工程 指导教师邹丽娜 学号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

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

一、已知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()＝

离散数学(集合地运算)实验报告材料

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

实验题目：集合的运算 实验原理： 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。 菜单显示函数：设计提示选项，给使用者操作提示。 操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。 具体操作如下：

1*求交集：根据集合集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。 2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着把b中元素依次存入数组g（并集集合）中，存储前将b中每个元素依次与已存入数组g中的集合A的元素比较，若数组g中没有与该元素相同的元素，则将该元素存入g（并集集合）中，否则进行下一次比较，直到所有b中元素比较并存储完毕，即求得A与B 的并集。 3*求差集：根据集合中差集的定义知，差集分为两部分，A对B的差集（数组d）和B对A的差集（e）。设计求解A对B的差集，将集合A中元素依次与B中元素比较，若B中无元素与该元素相同，则将其存入数组d中（同时删除d中相同的元素，操作方法与求并集时删除相同元素类似），否则进行下一轮比较，直到A中所有元素比较完毕，即求得A对B的差集（数组d）。求解B对A的差集方法与求解A对B 的差集类似，这里不再重复。 4*求对称差：根据集合中对称差集的定义，将3*中所求两部分差集求并集并存入数组f中即可。操作过程与求并集相似，这里不再重复。 5*求笛卡尔乘积：根据集合中笛卡尔乘积集的定义，分为A*B和B* A。先设计A* B是我算法，将a中元素循环依次与b中元素配对即可。求B* A与求A* B类似，这里不再重复。 实验步骤： 一、分析实验 阅读实验指导书和离散数学课本，充分理解整个实验的实验容及要求，以便对实验进行科学的设计。然后对整个实验进行“解剖”，即把整个实验系统地分成若干部

离散数学集合运算C++或C语言实验报告

离散数学实验报告 专业班级：12级计算机本部一班姓名：鲍佳珍 学号：201212201401016 实验成绩： 1．【实验题目】 命题逻辑实验四 2．【实验目的】 掌握用计算机求集合的交、并、差和补运算的方法。 3．【实验内容】 编程实现集合的交、并、差和补运算。 4、【实验要求】 C或C＋＋语言编程实现 5.【算法描述】 （1）用数组A，B，C，E表示集合。假定A={1,3，4，5，6，7，9，10}, B={2，,3，4，7，8，10}, E={1,2，3，4，5，6，7，8，9，10}, 输入数组A，B，E（全集），输入数据时要求检查数据是否重复（集合中的数据要求不重复），要求集合A，B是集合E的子集。 以下每一个运算都要求先将集合C置成空集。 （2）二个集合的交运算：A?B={x|x∈A且x∈B} 把数组A中元素逐一与数组B中的元素进行比较，将相同的元素放在数组C 中，数组C便是集合A和集合B的交。 C语言算法： for(i=0;i

for(j=0;j int main(){

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

《离散数学》期末复习提要 《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。 离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容 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 ~~~~???=??? 证明

离散数学集合运算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_集合与关系答案

离散数学作业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,所以