离散数学实验报告__四个实验.docx

《离散数学》课程设计学 院 计算机学院学生姓名 学 号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。实验一、 编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性）一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。二、数学原理：自反、对称、传递关系设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合设R是集合A上的二元关系：自反关系：对任意的x∈A,都满足x,x∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的(x)((x∈A)→(x,x∈R))=1对称关系：对任意的x,y∈A，如果x,y∈R，那么y,x∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的 (x)(y)((x∈A)∧ (y∈A)∧(x,y∈R)→(y,x∈R))=1传递关系：对任意的x,y,z∈A，如果x,y∈R且y,z∈R，那么x,z∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的 (x)(y)(z)[(x∈A)∧(y∈A)∧(z∈A)∧((x,y∈R)∧(y,z∈R)→(x,z∈R))]=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。图示：性质关系矩阵特性自反性主对角线元素全为1反自反性主对角线元素全为0对称性对称矩阵反对称性非主对角线上的元素等于1且与之对称的元素等于0传递性矩阵（M*M）中1所在的位置，M中与之相对应位置鲜红都为1四、实验环境：Windows 7 Ultimate DEV C++五、实验语言：C 语言六、程序源代码：#includestdio.h#define N 4main(){ int i,j,k; int f,e,z; int M[N][N]; printf(判断R是否为自反关系、对称关系、是否可传递？\n); printf(请输入一个4*4的矩阵。\n); for(i=0;iN;i++) /*输入一个4*4的矩阵*/ for(j=0;jN;j++) scanf(%d,M[i][j]); for(i=0;iN;i++) { for(j=0;jN;j++) printf(%4d,M[i][j]); printf(\n); } for(i=0;iN;i++) { if(M[i][i]==1)//判断自反性 { if(i=N-1 e=0; else ; } else if(M[i][i]==0)//判断反自反性 { if(i=N-1) e=1; else ; } else { e=2; break; } } for(i=0;iN;i++) { for(j=0;jN;j++) if(M[i][j]!=M[j][i])//判断对称性 { f=1; break; } } for(i=0;iN;i++) { for(j=0;jN;j++) if(M[i][j]==1)//判断反对称性 { if(M[j][i]==0) { if(i==(N-1)j==N-1) f=0; else break; } } } if(f!=0f!=1) { f=2; } for(i=0;iN;i++)//判断可传递性 for(j=0;jN;j++) if(M[i][j]==1) continue; else for(k=0;kN;k++) if(M[i][k]*M[k][i]==0) continue; else z=0; if(e==0) printf(关系R是自反关系\n); else if(e==1) printf(关系R是反自反关系