離散數(shù)學(xué)3關(guān)系

1、南京工程學(xué)院實(shí) 驗(yàn) 報(bào) 告課程名稱(chēng) 離散數(shù)學(xué) 實(shí)驗(yàn)項(xiàng)目名稱(chēng) 關(guān)系 實(shí)驗(yàn)學(xué)生班級(jí) K網(wǎng)絡(luò)工程121 實(shí)驗(yàn)學(xué)生姓名 王云峰 學(xué)號(hào) 240121525 實(shí)驗(yàn)時(shí)間 11月15日實(shí)驗(yàn)地點(diǎn) 信息樓 實(shí)驗(yàn)成績(jī)?cè)u(píng)定 指導(dǎo)教師簽字 年月日一、實(shí)驗(yàn)?zāi)康暮鸵箨P(guān)系是集合論中的一個(gè)十分重要的概念，關(guān)系性質(zhì)的判定是集合論中的重要內(nèi)容。通過(guò)該組實(shí)驗(yàn)，目的是讓學(xué)生更加深刻地理解關(guān)系的概念和性質(zhì)，并掌握關(guān)系性質(zhì)的判定等。實(shí)驗(yàn)要求實(shí)現(xiàn)判斷任意一個(gè)關(guān)系是否為自反關(guān)系、對(duì)稱(chēng)關(guān)系、傳遞關(guān)系。二、實(shí)驗(yàn)主要儀器和設(shè)備計(jì)算機(jī)三、實(shí)驗(yàn)方法與步驟（需求分析、算法設(shè)計(jì)思路、流程圖等）判斷任意一個(gè)關(guān)系是否為自反關(guān)系、對(duì)稱(chēng)關(guān)系、傳遞關(guān)系和等價(jià)關(guān)系？

2、若是等價(jià)關(guān)系，求出其所有等價(jià)類(lèi)。設(shè)RÍA×A，(1)若"x(xA®xRx)，稱(chēng)R是自反的；(2)若"x"y(x、yAxRy®yRx)，稱(chēng)R是對(duì)稱(chēng)的；(3)若"x"y"z(x、y、zAxRyyRz®xRz)，稱(chēng)R是傳遞的；(4)若R是自反的、對(duì)稱(chēng)的和傳遞的，則稱(chēng)R是等價(jià)關(guān)系。在程序?qū)崿F(xiàn)中，集合和關(guān)系用都用集合方式輸入。四、實(shí)驗(yàn)原始紀(jì)錄（源程序、數(shù)據(jù)結(jié)構(gòu)等）#include<stdio.h>#include<string.h>int n;/集合中元素的個(gè)數(shù)char

3、*A,*S,*F,*DJL;/S為集合,A為集合S的元素組成的字符數(shù)組/F為A上的二元關(guān)系集合,DJLi為第i個(gè)等價(jià)類(lèi)元素組成的集合int *R;/R為關(guān)系F的關(guān)系矩陣void Set_To_Array(char *Set,char *Array)/將集合轉(zhuǎn)化為一維字符數(shù)組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)/一維字符數(shù)組轉(zhuǎn)化為集合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(yíng)中的下標(biāo)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)/對(duì)稱(chēng)性判定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統(tǒng)計(jì)等價(jià)類(lèi)數(shù)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("等價(jià)類(lèi)分別為：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("請(qǐng)輸入集合A="); scanf("%s&q

8、uot;,S); Set_To_Array(S,A); printf("請(qǐng)輸入集合%s上的一個(gè)二元關(guān)系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("關(guān)系%s是%s上的等價(jià)關(guān)系,"); Get_Djl(R); else if(Judge_zf

9、x(R)printf("關(guān)系%s是自反的n",F); if(Judge_dcx(R)printf("關(guān)系%s是對(duì)稱(chēng)的n",F); if(Judge_cdx(R)printf("關(guān)系%s是傳遞的n",F); 5、 實(shí)驗(yàn)結(jié)果及分析（計(jì)算過(guò)程與結(jié)果、數(shù)據(jù)曲線(xiàn)、圖表等）6、 設(shè)RÍA×A，(1)若"x(xA®xRx)，稱(chēng)R是自)若"x"y(x、yAxRy®yRx)稱(chēng)R是對(duì)稱(chēng)的；(3)若"x"y"z(x、y、zAxRyyRz®xRz)，

10、稱(chēng)R是傳遞的；4)若R是自反的、對(duì)稱(chēng)的和傳遞的，則稱(chēng)R是等價(jià)關(guān)系。在程序?qū)崿F(xiàn)中，集合和關(guān)系用都用集合方式輸入。六、實(shí)驗(yàn)總結(jié)與思考判斷任意一個(gè)關(guān)系是否為自反關(guān)系、對(duì)稱(chēng)關(guān)系、傳遞關(guān)系和等價(jià)關(guān)系？若是等價(jià)關(guān)系，求出其所有等價(jià)類(lèi)。設(shè)RÍA×A，(1)若"x(xA®xRx)，稱(chēng)R是自反的；(2)若"x"y(x、yAxRy®yRx)，稱(chēng)R是對(duì)稱(chēng)的；(3)若"x"y"z(x、y、zAxRyyRz®xRz)，稱(chēng)R是傳遞的；(4)若R是自反的、對(duì)稱(chēng)的和傳遞的，則稱(chēng)R是等價(jià)關(guān)系。在程序?qū)崿F(xiàn)中，集合和關(guān)系用

11、都用集合方式輸入。 抽象原則：任給一個(gè)性質(zhì)P，就確定了一個(gè)集合A，A的元素恰好是具有性質(zhì)P的對(duì)象。子集、包含、包含于、真包含、全集U 、基數(shù)#A-元素個(gè)。冪集(A)：A的全部子集的集合交、并、差、補(bǔ)集。有窮集的計(jì)數(shù)原理：#(ABC)=#A+#B+#C-#(AB) -#(AC) -#(BC)+#(ABC)4. 空串、連接運(yùn)算、字母表、*、語(yǔ)言、閉包A*=A0A1 A0=正閉包A+= A15. 有序偶<x,y>：將2個(gè)對(duì)象xy按規(guī)定的順序構(gòu)成的序列。笛卡爾乘積A×B=<x,y>|xAyB,AB是集合二元關(guān)系R：任何有序偶的集合R。 <x,y>R、xRy

12、、xy有關(guān)系R定義域dom(R)、值域ran(R)全域關(guān)系Ux、恒等關(guān)系Ix關(guān)系矩陣、關(guān)系圖自反的、反自反的、對(duì)稱(chēng)的、反對(duì)稱(chēng)的、傳遞的復(fù)合關(guān)系RS：R是X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，則X到Z的一個(gè)關(guān)系RS滿(mǎn)足結(jié)合律 逆關(guān)系R-1 （RS)-1=S-1 R-1自反閉包r(R)=RIx、對(duì)稱(chēng)閉包s(R)=RR-1、傳遞閉包t(R)=R1 R2偏序：關(guān)系是自反的、反對(duì)稱(chēng)的、傳遞的全序、線(xiàn)序：可比嚴(yán)格偏序：反自反、傳遞的遮蓋、哈斯圖、最大元、極大元、上界、最小上界良序的：每個(gè)非空子集有最小元覆蓋、劃分、等價(jià)關(guān)系：自反的、對(duì)稱(chēng)的、傳遞的由x代表的等價(jià)類(lèi)xR=y|yXxRy (R:模6同余,1R=7,

13、13,. )函數(shù)f：是一個(gè)關(guān)系<x,y1><x,y2>都屬于f，則y1=y2f:XY :f是X到集合Y的關(guān)系，dom(f)=X自變量、象源、值、象偏函數(shù)f：對(duì)每個(gè)x dom(f)有唯一的y使<x,y>f-不屬于dom(f)的未定義全函數(shù) 滿(mǎn)射的(每個(gè)y都有x)、單射的(每個(gè)x射向不同y)、雙射的、反函數(shù)集合A的特征函數(shù)A(x)=1/0,xA/不屬于A(yíng) 集合的后繼集合A+=AA 0=?是自然數(shù)，n是則n+是，有限次使用規(guī)傳遞性、三岐性<>=、良基性數(shù)學(xué)歸納法：若P(0)是真的，mN,P(m)=>P(m+),則nN,P(n)是真的集合等勢(shì)AB：A,B的元素之間是一一對(duì)應(yīng)的。 存在雙射、抽屜原理：有窮集合AB，#A=m，#B=n，m