离散数学实验指导书(2011-5-16)

离散数学 实验指导书

姜楠 焉德军 李笑牛

（校内自编教材）

大连民族学院

计算机科学与工程学院

2011年3月

前 言

通常人们对离散数学教学的认识就是概念、定理、公式和解题。但是，离散数学不仅仅是这些，还有实验。在理论教学过程中，学生的活动只是“智力活动”，或更为直接地说是解题活动，教师在上面讲离散数学，而学生则每天在课堂上听课并在纸上做题目。这样，对多数学生而言，离散数学的发现探索活动没有能够真正开展起来。 离散数学实验教学，通常由教师提出问题，让学生在计算机上做实验，利用小组合作学习或者组织全班讨论，开展研究性学习活动；实验过程中，依靠计算机，让学生主动参与发展、探究、解决问题，从中获得离散数学研究、解决实际问题的过程体验、情感体验，产生成就感，进而开发学生的创新潜能，因而对离散数学实验课程教学进行研究具有重要意义。

利用计算机进行离散数学实验教学，不仅是开展离散数学研究性学习的一种有效方式，而且也为数据结构及程序设计课程教学的开展提升了层次。知识经济时代对创新人才的需求与离散数学教育中忽视学生创造性能力培养的矛盾日益凸显。在教学中倡导研究性学习，开展离散数学实验课程教学的研究与探索，与当前社会对离散数学教学的需求是一致的。

目前国内外很少有人对离散数学实验课程教学进行研究，尤其是国内进行这方面研究的人员更少，人们更重视离散数学理论课程教学的研究，忽视了离散数学实验课程对理论课程教学的辅助与促进作用，也忽视了离散数学实验课程与数据结构等课程的有机联系。因而我准备进行离散数学实验课程教学的研究与探索，以便更好的做好离散数学课程的教学改革工作。

本课程主要包括四个部分：集合与关系、图论、代数系统、数理逻辑。要求学生了解算法，理解运用C或C++语言把书中的部分内容的算法编写出能在计算机上运行的程序的思想，掌握实现离散数学部分算法程序设计的基本编程技术。

1

目 录

前 言 1 第一章 集合 3 实验一 集合的运算 3 实验二 求集合的笛卡儿乘积 6 第二章 关系 实验三 判断关系R的性质 实验四 判断关系R是否为等价关系 实验五 求等价类 实验六 由两个已知关系通过合成构造新的关系 实验七 关系的闭包运算 实验八 求关系个数的运算 实验九 求自反关系和对称关系的运算 实验十 求集合A上所有等价关系和偏序关系 二、求集合A上的所有偏序关系 实验十一 求满射函数 第三章 图论 实验十二 求可达矩阵的Warshall算法 实验十三 最小生成树的Kruskal算法 实验十四 判别图的连通性 实验十五 求无向图中顶点的度数 实验十六 求有向图中顶点的度数 第四章 代数系统 实验十七 判断是否为代数系统的算法 实验十八 判断是否为群的算法 第五章 数理逻辑 实验十九 构造合式公式的真值表

2

7 7 10 11 12 13 14 15 16 17 18 19 19 20 21 23 24 25 25 26 28 28

第一章 集合 实验一 集合的运算

一、求集合的并集

1、实验类型：操作性 2、实验目的

通过编程实现求给定集合A和B的并集C（C=A∪B）的运算。 3、 实验内容

已知所给集合A和B，求A与B 的并集C（C=A∪B）。 4、实验原理

因为并集的定义为：C={x|x∈A∨x∈B}，所以，只要将集合A与B合在一起就得到了并集C。但是，在一个集合中，同样的元素没必要出现两次或两次以上，所以，在将集合A送入并集C后，应将集合B中与A中相同的元素删除，再将集合B送入并集C之中。

5、实验仪器设备或软件环境及工具

运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。 6、实验要求

复习集合运算中交集的定义，实验由一人一组完成。所编程序能够通过编译，并能够实现求两个给定集合的交集。 7、实验步骤及注意事项

（1） 集合B的元素个数送M，集合A的元素个数送N。 （2） A?C。 （3） 1?i。

（4） 若i> M,则结束。

（5） 否则，对于j=1，2，??.，n，判断：bi=aj，若相等，则转（7）。 （6） 否则，bi?C。 （7） i+1?i，转（4）。

8、实验报告要求

（1）写出实验过程中遇到的问题及其解决过程。

（2）写出类c的算法并编写一个程序求给定集合A和B的并集。 （3）写出实验结束时的程序清单及运行结果及实验总结。

3

二、求集合的交集

1、实验类型：操作性 2、实验目的

通过编程实现求给定集合A和B的交集C（C=A∩B）的运算。 3、实验内容

已知所给集合A和B，求A与B 的交集C（C=A∩B） 4、实验原理

根据交集的定义：C={x|x∈A∧x∈B}，我们将集合A的各个元素与集合B的元素进行比较，若在集合B中存在某个元素并和集合A中一元素相等，则将该元素送入交集C之中。

5、实验仪器设备或软件环境及工具

运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。 6、实验要求

复习集合运算中并集的定义，实验由一人一组完成。所编程序能够通过编译，并能够实现求两个给定集合的并集。 7、实验步骤及注意事项

（1） 将集合A的元素送N。 （2） 1?i

（3） 若i>N,则结束。

（4） 否则，将ai与集合B中的每个元素进行比较，若ai与集合B中所有元素均

不相同，则转（6）。 （5） 否则，ai?C。 （6） i+1?i，转（3）。 8、实验报告要求

（1）写出实验过程中遇到的问题及其解决过程。

（2）写出类c的算法并编写一个程序给定集合A和B的交集。 （3）写出实验结束时的程序清单及运行结果及实验总结。

4