离散数学实验指导书2015 年3月6 日绪言通常对离散数学教学的认识就是上课老师讲述一个个概念、定理、公式和例题，学生背概念、公式，理解基础上记忆定理，然后据此做证明题、计算以及解题。
实质上离散数学不仅仅是这些，还有实验。
在理论教学过程中，学生的活动只是“智力活动”，或更为直接地说是解题活动，教师在上面讲离散数学，而学生则每天在课堂上听课并在纸上做题目。
这样，对多数学生而言，离散数学的发现探索活动没有能够真正开展起来。
离散数学实验教学，通常由教师提出问题，让学生在计算机上做实验，利用小组合作学习或者组织全班讨论，开展研究性学习活动；实验过程中，依靠计算机，让学生主动参与发展、探究、解决问题，从中获得离散数学研究、解决实际问题的过程体验、情感体验，产生成就感，进而开发学生的创新潜能，因而对离散数学实验课程教学进行研究具有重要意义。
利用计算机进行离散数学实验教学，不仅是开展离散数学研究性学习的一种有效方式，而且也为数据结构及程序设计课程教学的开展提升了层次。
知识经济时代对创新人才的需求与离散数学教育中忽视学生创造性能力培养的矛盾日益凸显。
在教学中倡导研究性学习，开展离散数学实验课程教学的研究与探索，与当前社会对离散数学教学的需求是一致的。
目前国内外很少有人对离散数学实验课程教学进行研究，尤其是国内进行这方面研究的人员更少，人们更重视离散数学理论课程教学的研究，忽视了离散数学实验课程对理论课程教学的辅助与促进作用，也忽视了离散数学实验课程与数据结构等课程的有机联系。
因而本学期离散数学课程组依据“2014培养方案”准备进行离散数学实验课程教学的研究与探索，以便更好的做好离散数学课程的教学改革工作。
主要包括四个部分：集合与关系、数理逻辑、代数系统、图论。
要求学生了解算法，理解运用C或C++语言（也可以是其他高级程序设计语言）把书中的部分内容的算法编写出能在计算机上运行的程序的思想，掌握实现离散数学部分算法程序设计的基本编程技术。
目录绪言 (2)实验一求集合的运算——并运算 (4)实验二求集合的运算——交运算 (6)实验三求集合的运算——差运算 (8)实验四求集合的笛卡儿乘积 (10)实验五判断关系R是否为自反关系 (12)实验六判断关系R是否为对称关系 (14)实验七判关系R是否为可传递关系 (16)实验八判断关系R是否为等价关系 (18)实验九求等价类 (19)实验十由两个已知关系通过合成构造新的关系 (20)实验十一关系的闭包运算 (21)实验十二求满射函数 (22)实验十三命题逻辑实验一——构造命题公式的真值表 (24)实验十三命题逻辑实验二——三个老师问题 (26)实验十四判断是否为代数系统的算法 (28)实验十五判断是否为群的算法 (29)实验十六求可达矩阵的Warshall算法 (31)实验十七最小生成树的Kruskal算法 (32)实验十八判别图的连通性 (34)实验一求集合的运算——并运算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、实验仪器设备或软件环境及工具长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。
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）写出实验结束时的程序清单及运行结果及实验总结。
实验二求集合的运算——交运算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、实验仪器设备或软件环境及工具长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。
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）写出实验结束时的程序清单及运行结果及实验总结。
实验三求集合的运算——差运算1、实验类型：基础实验2、实验目的通过编程实现求给定集合A和B的差集C（C=A-B）的运算。
3、实验内容已知所给集合A和B，求A与B的差集C（C=A-B）。
4、实验原理差集C的定义：差集C={x|x∈A∧x∉B}，即对于集合A中的元素a i，若不存在bj ∈B（j=1，2，…..，m），使得ai=bj，则ai∈差集C。
5、实验仪器设备或软件环境及工具长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。
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）写出实验结束时的程序清单及运行结果及实验总结。
实验四求集合的笛卡儿乘积1、实验类型：设计实验2、实验目的通过编程实现求给定集合A和B的笛卡儿乘积C（C=A×B）的运算。
3、实验内容已知所给集合A和B，求A与B的笛卡儿乘积C（C=A×B）。
4、实验原理笛卡儿乘积是以有序偶为元素组成的集合，它的定义为C={<x,y>|x∈A∧y ∈B}。
所以，欲求笛卡儿乘积。
只需取尽由集合A的元素及集合B的元素，并构成序偶<ai ，bj>送入C之中即可。
5、实验仪器设备或软件环境及工具长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。
6、实验要求复习笛卡儿乘积的定义，实验由一人一组完成。
所编程序能够通过编译，并能够实现求两个给定集合的笛卡儿乘积。
7、实验步骤及注意事项（1）将集合A的元素个数送入N。
（2）将集合B的元素个数送入M。
（3）1⇒i。
（4）若i>N,则结束。
（5）1⇒j。
（6）若j>M，则转（9）。
（7）<ai ，bj>⇒C。
（8）j+1⇒j，转（6）。
（9）i+1⇒i，转（4）。
8、实验报告要求（1）写出实验过程中遇到的问题及其解决过程。
（2）写出类c的算法并编写一个程序给定集合A和B的交集。
（3）写出实验结束时的程序清单及运行结果及实验总结。
9、思考题如何编程实现求有限个集合（集合的个数大于2）的笛卡尔乘积。
实验五判断关系R是否为自反关系1、实验类型：设计实验2、实验目的通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。
3、实验内容已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为自反关系。
4、实验原理从给定的关系矩阵来断判关系R是否为自反是很容易的。
若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。
本算法可以作为判等价关系算法的子程序给出。
5、实验仪器设备或软件环境及工具长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。
6、实验要求复习关系的性质，实验由一人一组完成。
所编程序能够通过编译，并能够实现对给定集合上的关系自反性质的判定。
7、实验步骤及注意事项（1）输入关系矩阵M（M为n阶方阵）。
=0，则R不是自反（2）判断自反性，对于i=1，2，….，n；若存在mii=1，则R是自反的；否则R既不是自反关系也不是的；若存在mii反自反关系。
（3）输出判断结果。
8、实验报告要求（1）写出实验过程中遇到的问题及其解决过程。
（2）写出类c的算法并编写一个程序判断给定集合上的关系是否为自反的。
（3）写出实验结束时的程序清单及运行结果及实验总结。
实验六判断关系R是否为对称关系1、实验类型：设计实验2、实验目的通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。
3、实验内容已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为对称关系。
4、实验原理从给定的关系矩阵来判断关系R是否为对称是很容易的。
若M（R的关系矩阵）为对称矩阵，则R是对称关系；若M为反对称矩阵，则R是反对称关系。
因为R为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。
5、实验仪器设备或软件环境及工具长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。
6、实验要求复习关系的性质，实验由一人一组完成。
所编程序能够通过编译，并能够实现对给定集合上的关系对称性质的判定。
7、实验步骤及注意事项（1）输入关系矩阵M（M为n阶方阵）；（2）判断对称性，对于i=2，3，….，n；j=1，2,……，i-1，若存在mij =mji，则R是对称的；（3）判断反对称性；（4）判断既是对称的又是反对称的；（5）判断既不是对称的又不是反对称的；（6）输出判断结果。