离散数学关系的闭包运算
《离散数学》
实验报告
学院软件学院
专业软件工程
指导教师邹丽娜
学号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)，否则结束．
流程图
开始
声明各子函数
输入关系矩阵
输入z
z=1；调用自反闭包函数 z=2，调用对称闭包函数 z=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 { printf("\n"); printf("请输入矩阵的第%d行元素",i); for(j=0;j scanf("%d",&s[i][j]); } printf("输入对应序号选择算法\n1:自反闭包\n2:传递闭包1\n3:传递闭包(Warhall算法)2\n4:对称闭包\n"); scanf("%d",&z); switch(z) { case 1:zifan(s); break; case 2:chuandi1(s);break; case 3:chuandi2(s);break; case 4:duichen(s); break; } } void output(int s[][100]) {printf("所求关系矩阵为\n"); for(i=0;i {for(j=0;j printf("%d",s[i][j]); printf("\n"); } } void zifan(int s2[][100]) { for(i=0;i s2[i][i]=1; output(s2);aa(); } void duichen(int s2[][100]) {int s1[100][100]; for(i=0;i for(j=0;j s1[j][i]=s2[i][j]; for(i=0;i for(j=0;j {s2[i][j]=s2[i][j]+s1[i][j]; if(s2[i][j]>1) s2[i][j]=1; } output(s2); aa(); } void chuandi1(int s2[][100]) {int m[100][100],a[100][100],k,h; int t[100][100]; for(i=0;i for(j=0;j { a[i][j]=0; t[i][j]=s2[i][j]; m[i][j]=s2[i][j];} for(h=0;h {for(i=0;i for(j=0;j if(m[i][j]==1) {for(k=0;k if(s2[j][k]==1) a[i][k]=1; } for(i=0;i for(j=0;j { m[i][j]=a[i][j]; t[i][j]+=a[i][j]; a[i][j]=0; if(t[i][j]>1) t[i][j]=1; } } output(t);aa(); } void chuandi2(int s2[][100]) {int k; for(i=0;i for(j=0;j if(s2[j][i]==1) for(k=0;k for(i=0;i for(j=0;j if(s2[i][j]>1) s2[i][j]=1; output(s2);aa(); } 3.实验数据及结果分析 大连民族学院 计算机科学与工程学院实验报告 实验题目：集合的运算 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性专业：网络工程班级：网络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类似，这里不再重复。 实验步骤： 一、分析实验 阅读实验指导书和离散数学课本，充分理解整个实验的实验内容及要求，以便对实验进行科学的设计。然后对整个实验进行“解剖”，即把整个实验系统地分成若干 闭包运算实验报告 姓名：卢志华学号：1045532116 一、实验目的 1.通过上机程序，进一步加深对关系中自反闭包，对称闭包，传递闭包的理解。 2.掌握Warshall算法。 3.学会用程序解决离散数学中的问题。 4.增强我们编写程序的能力。 二、实验内容 计算已输入集合的关系的自反闭包、对称闭包和传递闭包，传递闭包要求使用Warshall 算法 三、实验环境 我的实验是在VC++6.0实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。 四、实验原理和实现过程 下面我就具体分析一下每一种闭包运算的设计： 自反闭包的设计：我们只要把关系矩阵的对角线的元素全赋值为1就可以了。 求自反闭包的程序如下： void Relation::R_r() { for(int i=0;i 设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)，否则结束 具体程序如下： void Relation::R_t() { for(int i=0;i 离散数学知识点总结 一、各章复习要求与重点 第一章 集 合 [复习知识点] 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 ρρ 基本等值式 1.双重否定律A?┐┐A 2.幂等律 A ? A∨A, A ? A∧A 3.交换律A∨B ? B∨A，A∧B ? B∧A 4.结合律(A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C) 5.分配律A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律） 6.德·摩根律┐(A∨B) ?┐A∧┐B ┐(A∧B) ?┐A∨┐B 7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A 8.零律A∨1 ? 1,A∧0 ? 0 9.同一律A∨0 ? A，A∧1 ? A 10.排中律A∨┐A ? 1 11.矛盾律A∧┐A ? 0 12.蕴涵等值式A→B ?┐A∨B 13.等价等值式A?B ? (A→B)∧(B→A) 14.假言易位A→B ?┐B→┐A 15.等价否定等值式 A?B ?┐A?┐B 16.归谬论(A→B)∧(A→┐B) ?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。 推理定律--重言蕴含式 (1) A ? (A∨B) 附加律 (2) (A∧B) ? A 化简律 (3) (A→B)∧A ? B 假言推理 (4) (A→B)∧┐B ?┐A 拒取式 (5) (A∨B)∧┐B ? A 析取三段论 (6) (A→B) ∧(B→C) ? (A→C) 假言三段论 (7) (A?B) ∧(B?C) ? (A ? C) 等价三段论 (8) (A→B)∧(C→D)∧(A∨C) ?(B∨D) 构造性二难 (A→B)∧(┐A→B)∧(A∨┐A) ? B 构造性二难(特殊形式) (9)(A→B)∧(C→D)∧(┐B∨┐D) ?(┐A∨┐C) 破坏性二难 闭包概念 以下是写的比较科学规范的闭包求解方法，设X和Y均为关系R的属性集的子集，F 是R上的函数依赖集，若对R的任一属性集B，一旦X→B，必有B?Y，且对R的任一满足以上条件的属性集Y1 ，必有Y?Y1，此时称Y为属性集X在函数依赖集F下的闭包，记作X＋。 计算关系R的属性集X的闭包的步骤如下： 第一步：设最终将成为闭包的属性集是Y，把Y初始化为X； 第二步：检查F中的每一个函数依赖A→B，如果属性集A中所有属性均在Y中，而B 中有的属性不在Y中，则将其加入到Y中； 第三步：重复第二步，直到没有属性可以添加到属性集Y中为止。最后得到的Y就是X＋ 例（1）：设有关系模式R(U，F)，其中U={A，B，C，D，E，I}，F={A→D，AB→E，BI→E，CD→I，E→C}，计算(AE)+ 解: (1) 令X={AE}，X(0)=AE (2)在F中寻找尚未使用过的左边是AE的子集的函数依赖，结果是: A→D，E→C；所以X(1)=X(0)DC=ACDE，显然X(1)≠X(0). (3) 在F中寻找尚未使用过的左边是ACDE的子集的函数依赖，结果是: CD→I；所以X(2)=X(1)I=ACDEI。虽然X（2）≠X(1)，但F中寻找尚未使用过函数依赖的左边已经没有X（2）的子集，所以不必再计算下去，即(AE)+=ACDEI。 说白话一点：闭包就是由一个属性直接或间接推导出的所有属性的集合。 例如：f={a->b，b->c，a->d，e->f}；由a可直接得到b和d，间接得到c，则a的闭包就是{a，b，c，d} 候选码的求解理论和算法 对于给定的关系R（A1，A2，…An）和函数依赖集F，可将其属性分为4类：L类仅出现在函数依赖左部的属性。 R 类仅出现在函数依赖右部的属性。 N 类在函数依赖左右两边均未出现的属性。 LR类在函数依赖左右两边均出现的属性。 定理：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，则X必为R的任一候选码的成员。 推论：对于给定的关系模式R及其函数依赖集F，若X（X∈R）是L类属性，且X+ 《离散数学》 实验报告 学院软件学院 专业软件工程 指导教师邹丽娜 学号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 离散数学二元关系传递性判别、闭包方法实验报告 学院：理学院班级：11信息与计算科学1班 姓名：***学号：************* 一、实验目的 1. 通过上机程序，进一步加深对二元关系传递性判别，自反闭包，对称闭包，传递闭 包的理解。 2. 掌握传递性判别，Warshall算法。 3. 学会用程序解决离散数学中的问题。 4. 增强我们编写程序的能力 二、实验内容 实验1：二元关系传递性判别 实验2：有限集上给定关系的自反、对称和传递闭包（用Warshall算法）。 三、实验环境 在microsoft visual c++实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。 四、实验原理和实现过程 实验1： #include } cout< 题目：关系的3种基本运算 代码段： #include 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 个有序对 计算机专业通知：计算机资料就是同学们网上学习的阶段测试和简答练习等资料，请同学们打印下来复习，如有新的资料更新会通知大家！（以下资料只是网上一部分） 离散数学 一、单项选择题 1、（p∨(q∧r)）→(p∧q∧r)的主析取范式是：（B ） A. ∑(0,1) B. ∑(0,1,7) C. ∑(0,7) D. ∑(1,7) 2、下列是真命题的是（A ） A. 2是素数 B. 2+3=6 C. 雪是黑色的 D. 3能被2整除 3、设P：我们划船，Q：我们跳舞，命题“我们不能既划船又跳舞”符号化为（B ） A. P Q B. ┐（P∧Q） C. ┐P∧┐Q D. ┐P∧Q 4、设谓词P(x):x是奇数,Q(x):x是偶数,谓词公式 x(P(x)Q(x))在哪个个体域中为真 (A) A. 自然数 B. 实数 C. 复数 D. 前面三者均成立 5、当P的真值是1,Q的真值是1 R的真值是0，下列复合命题中真值为0的是（D ） A. （PvQ）→R B. R→(P ? Q) C. (PvR) →Q D. (P ?R)??Q 6、设A=｛1，2，3｝，则下列说法正确的是（C ） A. R={<1,1>，<2，2>，<3，3>，<1,2>}在A上是反自反的 B. R=｛<2，3>，<3，2>｝在A上是自反的 C. R=｛<1，2>，<2，1>，<3，3>在A上是对称的 D. R={<1，2>，<1，3>}在A上是对称的 7、下面关于集合的表示中，正确的是(B )． A. φ＝0 B. φ∈{φ} C. φ∈φ D. φ∈{a，b} 8、设A={?}，B=P（P（A）），以下不正确的式子是（）（分数：1分） A. ．{{? }，{{? }}，{?，{? }}}包含于B B. {{{? }}}包含于B C. {{?，{? }}}包括于B D. {{? }，{{?，{? }}}}包含于B 标准答案是：D。您的答案是： 9、六阶群的子群的阶数可以是（）。（分数：1分） A. 1，2，5 B. 2，4 C. 3，6，7 D. 2，3 标准答案是：D。您的答案是： 10、设G是n个结点、m条边和r个面的连通平面图，则m等于（）。（分数：1分） A. n+r-2 B. n-r+2 C. n-r-2 D. n+r+2 标准答案是：A。您的答案是： 集合论部分 第三章、集合的基本概念和运算 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） 民族学院 计算机科学与工程学院实验报告 实验题目：集合的运算 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性专业：网络工程班级：网络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类似，这里不再重复。 实验步骤： 一、分析实验 阅读实验指导书和离散数学课本，充分理解整个实验的实验容及要求，以便对实验进行科学的设计。然后对整个实验进行“解剖”，即把整个实验系统地分成若干部 实验2 关系的运算 （1）关系的幂运算 输入：集合A，二元关系集合R，幂次n 输出：R的n次幂 要求：尽量使运算的计算量最小 （2）关系闭包的计算 输入：集合A，二元关系集合R 输出：R的传递闭包t(R) 要求： (a)采用Warshall 算法（89页） (b)编写代码判断输出t(R)为传递闭包程序代码: #include Mat E; Mat D[100]; //用来存储矩阵 int n; public: void inputs();//将集合存入向量中 void inputa();//将读入的关系转化为关系矩阵 void print();//输出关系矩阵 void mi(); int Warshall(); };//定义类 int n,m;//全局变量，下文中使用 void Relation::inputs(){ cout<<"输入集合"; for(int a;cin>>a;){ s.push_back(a); if(getchar()=='\n') break;} }//将集合存入向量中 void Relation::inputa(){//将读入的关系转化为关系矩阵 cout<<"输入关系"; int i,j,e,r; for(i=0;i 实验二关系闭包计算 实 验 报 告 学院：计算机科学与软件学院指导老师：石陆魁 班级：116班 姓名：薛捷星 学号：112547 一、实验目的 熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。 二、实验内容与要求 定义6 设R是A上的二元关系，R的自反（对称、传递）闭包是关系R1，则 ①R1是自反的（对称的、传递的） ②R?R1 ③对任何自反的（对称的、传递的）关系R2，若R?R2，则R1?R2。 R的自反、对称和传递闭包分别记为r(R)、s(R)和t(R)。 定理1 令R?A?A，则 ①r(R)=R∪IA ②s(R)=R∪R-1 ③t(R)=R∪R2∪R3… Warshall算法：设R是n个元素集合上的二元关系，M是R的关系矩阵； (1)置新矩阵A:=M (2)置i:=1； (3)for j=1 to n do if A[j,i]=1 then do for k=1 to n do A[j,k]:=A[j,k]+A[i,k] (4)i=i+1； (5)if i<=n then to (3) else stop 本实验要求从键盘输入一个关系的关系矩阵，计算其自反闭包、对称闭包和传递闭包，计算传递闭包时使用Warshall算法。用C语言或MA TLAB实现。 三、源程序 #include { int i,j,k,a[n][n],I[n][n]={1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1},b[n][n],r[n][n]; printf("输入R的关系矩阵:\n"); for(i=0;i 离散数学实验报告 专业班级：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 《离散数学》期末复习提要 《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。 离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容 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语言写法： #include printf(“\n”); } if(i >=n) { if(G[0]) cout < 湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：考试科目名称：离散数学 一、试卷结构 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年7离散数学(集合的运算)实验报告
闭包运算实验报告1
离散数学知识点总结
离散数学公式
闭包概念
离散数学关系的闭包运算
离散数学二元关系传递性判别、闭包方法实验报告
关系的3种基本运算
离散数学N元集合关系个数计算
离散数学
离散数学第三章集合的基本概念和运算知识点总结
离散数学(集合地运算)实验报告材料
离散数学实验-C-++关系的运算(幂运算-闭包运算)
试验二关系闭包计算
离散数学集合运算C++或C语言实验报告
《离散数学(第三版)》方世昌 的期末复习知识点总结
离散数学集合运算c语言
010_离散数学