离散数学实验汇报.doc

大连民族学院 计算机科学与工程学院实验报告 实验题目： 关系部分实验 课程名称： 离散数学 实验类型：□演示性 □验证性 □操作性 □设计性 ■综合性 专业： 网络工程 班级： 102 班 学生姓名：隋玉兴 学号：2010083220 实验日期：2011 年 12 月 25 日 实验地点：五机房 实验学时： 实验成绩： 指导教师签字： 年 月 日 实验目的 本实验课程是信息专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。 二. 实验内容 A集合的运算 1求集合的并集：已知所给集合A和B，求A与B 的并集C（C=A∪B） 2求集合的交集：已知所给集合A和B，求A与B 的交集C（C=A∩B） 3求集合的差集：已知所给集合A和B，求A与B的差集C（C=A-B）。 B判断关系R的性质 1判断关系R是否为自反关系：已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为自反关系 2判断关系R是否为对称关系： 已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为对称关系 C求无向图中顶点的度数 给定无向图的各边所关联的顶点对，编程设计求出每个顶点的度数。 D判断是否为群的算法 给出一个代数系统G,* ，其中：G={1，2，…，n}，* 运算由运算表矩阵给出，要判断： （1）G,* 是否为半群； （2）G，*是否为含幺半群； （3）G，*是否为群。 三.实验环境； 使用visual C++6.0为编程软件，采用C语言为编程语言实现。 四. 实验原理和实现过程（算法描述）； A集合的运算 1求集合的并集：根据交集的定义：C={x|x∈A∧x∈B}，我们将集合A的各个元素与集合B的元素进行比较，若在集合B中存在某个元素并和集合A中一元素相等，则将该元素送入交集C之中。 2求集合的交集：根据交集的定义：C={x|x∈A∧x∈B}，我们将集合A的各个元素与集合B的元素进行比较，若在集合B中存在某个元素并和集合A中一元素相等，则将该元素送入交集C之中。 3求集合的差集：差集C的定义：差集C={x|x∈A∧xB}，即对于集合A中的元素ai，若不存在bj∈B（j=1，2，…..，m），使得ai=bj，则ai ∈差集C。 B判断关系R的性质 1判断关系R是否为自反关系：从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。 2判断关系R是否为对称关系：从给定的关系矩阵来判断关系R是否为对称是很容易的。若M（R的关系矩阵）为对称矩阵，则R是对称关系；若M为反对称矩阵，则R是反对称关系。因为R为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。 3判关系R是否为可传递关系：一个关系R的可传递性定义告诉我们，若关系R是可传递的，则必有：mik=1∧mkj=1 mij=1。这个式子也可改写成为： mij =0 mik =0∨mkj=0。我们可以根据后一个公式来完成判断可传递性这一功能的。可传递性也是等价关系的必要条件，所以，本算法也可以作为判等价关系算法的子程序给出。 C求无向图中顶点的度数 设无向图G=V,E, ek=(vi,vj)?E, 称vi , vj为ek 的端点, ek与vi (vj)关联。若vi= vj，则称ek 为环loop. 无边关联的顶点称作孤立点. 若vi 1 vj, 则称ek 与vi (vj)的关联次数为1; 若vi = vj, 则称ek 与vi 的关联次数为2; 若vi不是边e的端点, 则称e与vi 的关联次数为0。设G=V,E为无向图, v?V,v的度数(度) d(v)是v作为边的端点次数之和。 D构造合式公式的真值表 1）逻辑联结词的定义方法 逻辑连接词“非”：设p为命题, 复合命