离散数学3关系

1、南京工程学院实 验 报 告课程名称 离散数学 实验项目名称 关系 实验学生班级 K网络工程121 实验学生姓名 王云峰 学号 240121525 实验时间 11月15日实验地点 信息楼 实验成绩评定 指导教师签字 年月日一、实验目的和要求关系是集合论中的一个十分重要的概念，关系性质的判定是集合论中的重要内容。通过该组实验，目的是让学生更加深刻地理解关系的概念和性质，并掌握关系性质的判定等。实验要求实现判断任意一个关系是否为自反关系、对称关系、传递关系。二、实验主要仪器和设备计算机三、实验方法与步骤（需求分析、算法设计思路、流程图等）判断任意一个关系是否为自反关系、对称关系、传递关系和等价关系？

2、若是等价关系，求出其所有等价类。设RÍA×A，(1)若"x(xA®xRx)，称R是自反的；(2)若"x"y(x、yAxRy®yRx)，称R是对称的；(3)若"x"y"z(x、y、zAxRyyRz®xRz)，称R是传递的；(4)若R是自反的、对称的和传递的，则称R是等价关系。在程序实现中，集合和关系用都用集合方式输入。四、实验原始纪录（源程序、数据结构等）#include<stdio.h>#include<string.h>int n;/集合中元素的个数char

3、*A,*S,*F,*DJL;/S为集合,A为集合S的元素组成的字符数组/F为A上的二元关系集合,DJLi为第i个等价类元素组成的集合int *R;/R为关系F的关系矩阵void Set_To_Array(char *Set,char *Array)/将集合转化为一维字符数组int i,j;j=0;for(i=1;i<(int)strlen(Set)-1;i=i+2)Arrayj+=Seti;Arrayj='0'void Array_To_Set(char *Array,char *Set)/一维字符数组转化为集合int i,j;j=0; Setj+=''f

4、or(i=0;Arrayi!='0'i+)Setj+=Arrayi;Setj+=','if(j>1)Setj-1=''Setj='0'else Setj+=''Setj='0'int Get_xh(char *A,char ch)/返回字符在A中的下标int i;for(i=0;i<n;i+)if(Ai=ch)return i;void Relation_To_Matrix(char *F,int *R)int i,j,s,t;for(i=0;i<n;i+)for(j=0;j<

5、;n;j+)Rij=0;for(i=2;i<(int)strlen(F);i=i+6)s=Get_xh(A,Fi);t=Get_xh(A,Fi+2);Rst=1;int Judge_zfx(int *R)/自反性判定int i;for(i=0;i<n;i+)if(Rii=0)return 0;return 1;int Judge_dcx(int *R)/对称性判定int i,j; for(i=1;i<n;i+)for(j=0;j<i;j+)if(Rij!=Rji)return 0;return 1;int Judge_cdx(int *R)/传递性判定int i,j,k

6、,*B; B=new int*n;for(i=0;i<n;i+)Bi=new intn;for(i=0;i<n;i+)for(j=0;j<n;j+)for(k=0;k<n;k+)Bij=Rik&&Rkj; for(i=0;i<n;i+)for(j=0;j<n;j+)if(Bij>Rij)return 0;return 1;void Get_Djl(int *R)int i,j,m=0,ip;/m统计等价类数DJL=new char*n;for(i=0;i<n;i+)if(Ai)ip=0;DJLm=new charn;DJLmip+

7、=Ai;for(j=i+1;j<n;j+)if(Aj&&Rij)DJLmip+=Aj;Aj=0;DJLmip='0'm+; printf("等价类分别为：n");for(i=0;i<m;i+) Array_To_Set(DJLi,S);printf("%s ",S);printf("n");void main() int i,j; S=new char; F=new char; A=new char; printf("请输入集合A="); scanf("%s&q

8、uot;,S); Set_To_Array(S,A); printf("请输入集合%s上的一个二元关系F=",S); scanf("%s",F); n=strlen(A); R=new int*n; for(i=0;i<n;i+)Ri=new intn; Relation_To_Matrix(F,R); if(Judge_zfx(R)&&Judge_dcx(R)&&Judge_cdx(R) printf("关系%s是%s上的等价关系,"); Get_Djl(R); else if(Judge_zf

9、x(R)printf("关系%s是自反的n",F); if(Judge_dcx(R)printf("关系%s是对称的n",F); if(Judge_cdx(R)printf("关系%s是传递的n",F); 5、 实验结果及分析（计算过程与结果、数据曲线、图表等）6、 设RÍA×A，(1)若"x(xA®xRx)，称R是自)若"x"y(x、yAxRy®yRx)称R是对称的；(3)若"x"y"z(x、y、zAxRyyRz®xRz)，

10、称R是传递的；4)若R是自反的、对称的和传递的，则称R是等价关系。在程序实现中，集合和关系用都用集合方式输入。六、实验总结与思考判断任意一个关系是否为自反关系、对称关系、传递关系和等价关系？若是等价关系，求出其所有等价类。设RÍA×A，(1)若"x(xA®xRx)，称R是自反的；(2)若"x"y(x、yAxRy®yRx)，称R是对称的；(3)若"x"y"z(x、y、zAxRyyRz®xRz)，称R是传递的；(4)若R是自反的、对称的和传递的，则称R是等价关系。在程序实现中，集合和关系用

11、都用集合方式输入。 抽象原则：任给一个性质P，就确定了一个集合A，A的元素恰好是具有性质P的对象。子集、包含、包含于、真包含、全集U 、基数#A-元素个。幂集(A)：A的全部子集的集合交、并、差、补集。有穷集的计数原理：#(ABC)=#A+#B+#C-#(AB) -#(AC) -#(BC)+#(ABC)4. 空串、连接运算、字母表、*、语言、闭包A*=A0A1 A0=正闭包A+= A15. 有序偶<x,y>：将2个对象xy按规定的顺序构成的序列。笛卡尔乘积A×B=<x,y>|xAyB,AB是集合二元关系R：任何有序偶的集合R。 <x,y>R、xRy

12、、xy有关系R定义域dom(R)、值域ran(R)全域关系Ux、恒等关系Ix关系矩阵、关系图自反的、反自反的、对称的、反对称的、传递的复合关系RS：R是X到Y的关系，S是从Y到Z的关系，则X到Z的一个关系RS满足结合律 逆关系R-1 （RS)-1=S-1 R-1自反闭包r(R)=RIx、对称闭包s(R)=RR-1、传递闭包t(R)=R1 R2偏序：关系是自反的、反对称的、传递的全序、线序：可比严格偏序：反自反、传递的遮盖、哈斯图、最大元、极大元、上界、最小上界良序的：每个非空子集有最小元覆盖、划分、等价关系：自反的、对称的、传递的由x代表的等价类xR=y|yXxRy (R:模6同余,1R=7,

13、13,. )函数f：是一个关系<x,y1><x,y2>都属于f，则y1=y2f:XY :f是X到集合Y的关系，dom(f)=X自变量、象源、值、象偏函数f：对每个x dom(f)有唯一的y使<x,y>f-不属于dom(f)的未定义全函数 满射的(每个y都有x)、单射的(每个x射向不同y)、双射的、反函数集合A的特征函数A(x)=1/0,xA/不属于A 集合的后继集合A+=AA 0=?是自然数，n是则n+是，有限次使用规传递性、三岐性<>=、良基性数学归纳法：若P(0)是真的，mN,P(m)=>P(m+),则nN,P(n)是真的集合等势AB：A,B的元素之间是一一对应的。 存在双射、抽屉原理：有穷集合AB，#A=m，#B=n，m