离散数学实验指导书(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

三、求集合的差集

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中的元素ai，若不存在bj∈B（j=1，2，?..，m），使得ai=bj，则ai ∈差集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）写出实验结束时的程序清单及运行结果及实验总结。

5

实验二 求集合的笛卡儿乘积

1、实验类型：设计性 2、实验目的

通过编程实现求给定集合A和B的笛卡儿乘积C（C=A×B）的运算。 3、实验内容

已知所给集合A和B，求A与B的笛卡儿乘积C（C=A×B）。 4、实验原理

笛卡儿乘积是以有序偶为元素组成的集合，它的定义为C={|x∈A∧y∈B}。所以，欲求笛卡儿乘积。只需取尽由集合A的元素及集合B的元素，并构成序偶送入C之中即可。

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

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

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

（1） 将集合A的元素个数送入N。 （2） 将集合B的元素个数送入M。 （3） 1?i。 （4） 若i>N,则结束。 （5） 1?j。

（6） 若j>M，则转（9）。 （7） ?C。 （8） j+1?j，转（6）。 （9） i+1?i，转（4）。 8、实验报告要求

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

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

如何编程实现求有限个集合（集合的个数大于2）的笛卡尔乘积。

6

第二章 关系

实验三 判断关系R的性质

一、判断关系R是否为自反关系 1、实验类型：设计性 2、实验目的

通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 3、实验内容

已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为自反关系。 4、实验原理

从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。

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

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

复习关系的性质，实验由一人一组完成。所编程序能够通过编译，并能够实现对给定集合上的关系自反性质的判定。 7、实验步骤及注意事项

（1） 输入关系矩阵M（M为n阶方阵）。

（2） 判断自反性，对于i=1，2，?.，n；若存在mii=0，则R不是自反的；

若存在mii=1，则R是自反的；否则R既不是自反关系也不是反自反关系。

（3） 输出判断结果。

8、实验报告要求

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

（2）写出类c的算法并编写一个程序判断给定集合上的关系是否为自反的。 （3）写出实验结束时的程序清单及运行结果及实验总结。

7

二、 判断关系R是否为对称关系

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 3、实验内容

已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为对称关系。 4、实验原理

从给定的关系矩阵来判断关系R是否为对称是很容易的。若M（R的关系矩阵）为对称矩阵，则R是对称关系；若M为反对称矩阵，则R是反对称关系。因为R为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。 5、实验仪器设备或软件环境及工具

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

复习关系的性质，实验由一人一组完成。所编程序能够通过编译，并能够实现对给定集合上的关系对称性质的判定。 7、实验步骤及注意事项

（1） 输入关系矩阵M（M为n阶方阵）；

（2） 判断对称性，对于i=2，3，?.，n；j=1，2,??，i-1，若存在mij=mji，则R

是对称的； （3） 判断反对称性；

（4） 判断既是对称的又是反对称的； （5） 判断既不是对称的又不是反对称的； （6） 输出判断结果。 8、实验报告要求

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

（2）写出类c的算法并编写一个程序判断给定集合上的关系是否为对称的。 （3）写出实验结束时的程序清单及运行结果及实验总结。

8

三、 判关系R是否为可传递关系 1、实验类型：设计性 2、实验目的

通过算法设计并编程实现对给定集合上的关系是否为传递关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 3、实验内容

已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为传递关系。 4、实验原理

一个关系R的可传递性定义告诉我们，若关系R是可传递的，则必有：mik=1∧mkj=1? mij=1。这个式子也可改写成为： mij =0? mik =0∨mkj=0。我们可以根据后一个公式来完成判断可传递性这一功能的。可传递性也是等价关系的必要条件，所以，本算法也可以作为判等价关系算法的子程序给出。 5、实验仪器设备或软件环境及工具

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

复习关系的性质，实验由一人一组完成。所编程序能够通过编译，并能够实现对给定集合上的关系传递性质的判定。 7、实验报告要求

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

（2）设计出类c的算法并编写一个程序判断给定集合上的关系是否为传递的。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8、思考题

写出另一种判断关系传递性的算法，即在M(R·R)中，若任意r′ij=1 ，则MR中相应的元素rij=1，并据此设计出关系传递性质判断的程序。

9

实验四 判断关系R是否为等价关系

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现对给定集合上的关系是否为自反的、对称的和传递关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断等价关系的方法。 3、实验内容

给定R的关系矩阵，据此判断所给关系R是否为等价关系。 4、实验原理

设R为非空集合A上的关系. 如果R是自反的、对称的和传递的, 则称R为A上的等价关系。

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

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

复习关系的性质，实验由几个人一组完成。所编程序能够通过编译，并能够实现对给定集合上的关系性质的判定。 7、实验报告要求

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

（2）写出类c的算法并编写一个程序判断给定集合上的关系是否为等价关系。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8、思考题

（1）设计一个程序，求出对给定的有限集合的所有划分。

（2）集合X={a,b,c,d,e,f},并且X中有关系R={,,,, ，,,,,}，编程求解R的关系矩阵及X对R的商集。

10

实验五 求等价类

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现对给定集合上的关系是否为自反的、对称的和传递关系的判断，加深学生对等价关系和等价类的理解，掌握求等价类的方法。 3、实验内容

给定一个集合{1，2，?..，n}，及其上的一个等价关系R，求R上的等价类。 4、实验原理

给定任意关系，欲判断R是否为等价关系，可用实验八所给出的程序。但是，如果给定一个等价关系，那么它的关系矩阵必为对称矩阵。为了节省存储空间，只要存放关系矩阵的一半就可以了（另一半与这一半相同）。我们可以用一维数组来存放关系矩阵的下三角矩阵（包括主对角线在内），具体对应关系如下：

根据等价类的定义可知，等价类内的各元素之间均有R关系，所以在构造等价类时，只要依据所给关系矩阵，把所有相互有R关系的各元素归为一类就可以了。在输出时，把每一类显示在同一行上。 5、实验仪器设备或软件环境及工具

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

复习等价关系和等价类的定义，实验由几个人一组完成。所编程序能够通过编译，并能够实现求出给定集合上等价关系的等价类。 7、实验报告要求

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

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

11

实验六 由两个已知关系通过合成构造新的关系

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求对给定的关系的合成关系，加深学生对合成关系运算的理解。 3、实验内容

设关系A是从集合X={1，2，?.，n}到集合Y={1，2，?..，m}的二元关系，而关系B是从集合Y到集合Z={1，2，?.，p}的二元关系，求A与B的合成关系C。 4、实验原理

由关系合成的定义可知：A?B={|有y∈Y使∈A且∈B}。若用关系矩阵来表示关系，则关系的合成运算类似于数值矩阵的乘法。不同的是用“∧”代替乘，用“∨”代替加。其中，0∨0=0，0∧0=0，0∨1=1，0∧1=0，1∨0=1，1∧0=0，1∨1=1，1∧1=1

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

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

复习关系合成的定义，实验由一人一组完成。所编程序能够通过编译，并能够实现求给定集合上的关系的合成的运算。 7、实验报告要求

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

（2）设计出类c的算法并编写一个程序求出给定的两个关系的合成关系。 （3）写出实验结束时的程序清单及运行结果及实验总结。

12

实验七 关系的闭包运算

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求给定关系的各种闭包运算，加深学生对闭包运算的概念的理解。 3、实验内容

给定关系R，求R的自反闭包及R的对称闭包。 4、实验原理

若关系R的关系矩阵为M，而自反闭包为A（即r（R）=A），对称闭包为B（即S（R）=B），则A=M∨I B=M∨MT 其中，I为恒等矩阵，MT为M的转置矩阵。 5、实验仪器设备或软件环境及工具

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

复习关系闭包的定义，实验由几人一组完成。所编程序能够通过编译，并能够实现求出给定关系的闭包的运算。 7、实验报告要求

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

（2）写出类c的算法并编写一个程序求出给定关系的闭包。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8、思考题

设计出求关系R的传递闭包的Warshall算法的程序。

13

实验八 求关系个数的运算

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求给定集合上关系的个数，加深学生对关系概念的理解。 3、实验内容

给定一个4元素集合A，求出A上所有不同的关系并显示出来。 4、实验原理

设A,B为集合,A×B的任何子集所定义的二元关系叫做从 A 到 B 的二元关系, 当 A=B 时则叫做 A上的二元关系.

关系的计数：若|A|=n, |B|=m, |A×B|=nm, A×B 的子集有2nm 个。所以从A到B有2 个不同的二元关系. |A|=n, A上有2个不同的二元关系. 5、实验仪器设备或软件环境及工具

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

复习关系的定义，实验由几人一组完成。所编程序能够通过编译，能够实现求出给定的4元素集合A上所有不同的二元关系并显示出来。 7、实验报告要求

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

（2）写出类c算法并编写一个程序求出给定的4元素集合A上所有不同的二元关系。 （3）显示所有求出的二元关系。

（4）写出实验结束时的程序清单及运行结果及实验总结。 8、思考题

设计出求n个元素集合A上所有不同关系的程序。

nm

n2 14

实验九 求自反关系和对称关系的运算

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求给定集合上所有不同的自反关系和对称关系，加深学生对关系性质的理解。 3、实验内容

给定一个5元素集合A，求出A上所有不同的自反关系、对称关系和传递关系并显示出来。 4、实验原理

设R为集合A上的关系，如果对A中每一x,都有xRx,那么R是自反的。即A上的关系R是自反的（Reflexive）；若?x?y(x,y∈A∧∈R→∈R),则称R为A上对称的(symmetric)关系；若?x?y?z(x,y,z∈A∧∈R∧∈R→∈R),则称R是A上的传递关系。 5、实验仪器设备或软件环境及工具

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

复习关系性质的定义，实验由几人一组完成。所编程序能够通过编译，能够实现求出给定的5元素集合A上所有不同的自反关系和对称关系并显示出来。 7、实验报告要求

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

（2）写出类c的算法并编写一个程序求出给定的6元素集合A上所有不同的自反关系和对称关系。

（3）显示所有求出的自反关系和对称关系。

（4）写出实验结束时的程序清单及运行结果及实验总结。

15

实验十 求集合A上所有等价关系和偏序关系

一、求集合A上所有等价关系 1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求给定集合上所有不同的等价关系，加深学生对等价关系定义及性质的理解。 3、实验内容

给定一个7元素集合A，求出A上所有不同的等价关系并显示出来。 4、实验原理

设R为非空集合A上的关系. 如果R是自反的、对称的和传递的, 则称R为A上的等价关系。

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

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

复习等价关系的定义和性质，实验由几人一组完成。所编程序能够通过编译，能够实现求出给定的7元素集合A上所有不同的等价关系并显示出来。 7、实验报告要求

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

（2）写出类c的算法并编写一个程序求出给定的7元素集合A上所有不同的等价关系。

（3）显示所有求出的等价关系。

（4）写出实验结束时的程序清单及运行结果及实验总结。

16

二、求集合A上的所有偏序关系 1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求给定集合上所有不同的偏序关系，加深学生对偏序关系定义及性质的理解。 3、实验内容

给定一个5元素集合A，求出A上所有不同的偏序关系并显示出来。 4、实验原理

设R为非空集合A上的关系，如果R是自反的、反对称的和传递的, 则称R为A上的偏序关系。

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

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

复习偏序关系的定义和性质，实验由几人一组完成。所编程序能够通过编译，能够实现求出给定的5元素集合A上所有不同的偏序关系并显示出来。 7、实验报告要求

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

（2）写出类c的算法并编写一个程序求出给定的5元素集合A上所有不同的偏序关系。

（3）显示所有求出的偏序关系。

（4）写出实验结束时的程序清单及运行结果及实验总结。

17

实验十一 求满射函数

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

通过算法设计并编程实现求出从集合A到B上的所有满射函数的个数，加深学生对函数性质的理解。 3、实验内容

设A、B为有限集合，且|A|=m，|B|=n，求出从集合A到B的所有满射函数个数。 4、实验原理

从A到B的满射函数定义为：设 f : A→B,若ranf = B, 则称 f : A→B是满射的（或称为映到的），函数f 为满射的必要条件是 |A|≥|B|。否则就不是满射函数了。对于所给的问题，可以使用公式：

nn?1n?21F=Cn·nm－Cn·(n?1)m+Cn·(n?2)m－??.+ (?1)n?1Cn·1m

来求得其解。但是在这儿，我们也可以使用计算机中常用的一种方法——枚举法来求解。

枚举法就是一个个的列出所有满足条件的函数，并将其记录下来，当枚举结束时就可得到欲求函数的数目。对于上面提出的问题，相当于把n个不同的数字放到m个位置上去的所有不同的方法。其中，数字是可重复出现的，但是每个数字必须都出现过至少一次才是满射函数。 5、实验仪器设备或软件环境及工具

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

预习函数的定义和函数的性质，实验由几人一组完成。所设计的程序能够通过编译，并能够实现求从集合A到B上的所有满射函数的个数。 7、实验报告要求

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

（2）设计出类c的算法并编写一个程序求出从集合A到B上的所有满射函数的个数。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8、思考题

设计出一个类c的算法，并编写一个程序求出从集合A到B上的所有单射函数的个数。

18

第三章 图论

实验十二 求可达矩阵的Warshall算法

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

通过算法设计并编程实现求出给定n个结点的图G的可达矩阵P，加深学生对可达矩阵的理解。 3、实验内容

给定n个结点的图G的邻接矩阵A，求G的可达矩阵P。 4、实验仪器设备或软件环境及工具

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

复习图的矩阵表示部分的内容，实验由一人一组完成。所设计的程序能够通过编译，并能够实现从给定n个结点的图G的邻接矩阵A，求出G的可达矩阵P 6、实验步骤及注意事项

（1） 将图G的邻接矩阵送入P（n，n）中。 （2） 1?i。 （3） 1?j。

（4） 对于k=1，2，?，n，作：Pjk∨（Pji∧Pik）?Pjk （5） j+1?j，若j?n，则转（4）。

（6） i+1?i，若i?n，则转（3），否则结束。 7、实验报告要求

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

（2）写出类c的算法并写出一个程序求给定n个结点的图G的可达矩阵P （3）写出实验结束时的程序清单及运行结果及实验总结。

19

实验十三 最小生成树的Kruskal算法

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。 3、实验内容

给定无向连通加权图，编程设计求出其一棵最小生成树。 4、实验原理

设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。 5、实验仪器设备或软件环境及工具

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

复习树及最小生成树的定义，实验由一人一组完成。所设计程序能够通过编译，并能够求出给定无向连通加权图的一棵最小生成树。 7、实验步骤及注意事项

（1） 边依小到大顺序得l1，l2，?，lm。 （2） 置初值：??S，0?i，1?j。 （3） 若i=n-1，则转（6）。

（4） 若生成树边集S并入一条新的边lj之后产生的回路，则j+1?j，并转（4）。 （5） 否则，i+1?i；lj?S（i）；j+1?j，转（3）。 （6） 输出最小生成树S。 （7） 结束。 8、实验报告要求

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

（2）写出类c的算法，并写一个程序求出给定无向连通加权图的一棵最小生成树。 （3）写出实验结束时的程序清单及运行结果及实验总结。

20

实验十四 判别图的连通性

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现，使学生掌握利用计算机语言判别图的连通性的基本方法。 3、实验内容

给定n个结点的有向图的邻接矩阵，可判断该图是否为强连通的，单向连通的，或弱连通的。 4、实验原理

对于给定的邻接矩阵A，我们可以用前面给出的可达矩阵Warshall算法求出A所表示的图的可达矩阵P。对于可达矩阵P来说，如果P的所有元素均为1，则所给的有向图是强连通的；对于P的所有元素（除主对角线元素外）Pij来说，均有：Pij+Pji>0，则所给有向图是单向连通的。当所给有向图既不是强连通的，又不是单向连通的时候，我们改造邻接矩阵为：对于矩阵A中所有的元素（除主对角线的元素外）aij，若aij=1或aji=1，则1?aij且1?aji。对于这样改造之后所得到的新的矩阵A’（A’相当于原有向图忽略方向之后所得到的无向图的邻接矩阵），再用前面所述的方法进行判断，当P’的所有元素（除主对角线的元素外）均为1时，原有向图是弱连通图；否则，原有向图是不连通的。

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

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

复习图的强连通、单向连通和弱连通的定义，实验由几人一组完成。所编程序能够通过编译，并能够对给定n个结点的有向图的邻接矩阵，判断该图是否为强连通的，单向连通的，或弱连通的。 7、实验步骤及注意事项 （1）输入邻接矩阵A（n，n）。 （2）A（n，n）?P（n，n）。

（3）调用求可达矩阵子程序求出可达矩阵P。 （4）调用强连通或单向连通子程序。

（5）若为强连通或单向连通的，则输出其标志，转结束；否则转（6）。 （6）改造A阵为 A’，且A’ ?P（n,n）。

21

（7）调用求可达矩阵子程序。

（8）调用判断连通或单向连通子程序。

（9）若为强连通的，则输出原有向图是弱连通的；否则输出原有向图是非连通的。 （10）结束。 8、实验报告要求

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

（2）写出类c的算法，并编写一个程序求出给定n个结点的有向图的邻接矩阵，据此判断该图是否为强连通的，单向连通的，或弱连通的。 （3）写出实验结束时的程序清单及运行结果及实验总结。

22

实验十五 求无向图中顶点的度数

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求出给定无向图顶点的度数，加深学生对关联及度的定义的理解。 3、实验内容

给定无向图的各边所关联的顶点对，编程设计求出每个顶点的度数。 4、实验原理

设无向图G=, ek=(vi,vj)?E, 称vi , vj为ek 的端点, ek与vi (vj)关联。若vi= vj，则称ek 为环loop. 无边关联的顶点称作孤立点. 若vi ? vj, 则称ek 与vi (vj)的关联次数为1; 若vi = vj, 则称ek 与vi 的关联次数为2; 若vi不是边e的端点, 则称e与vi 的关联次数为0。设G=为无向图, v?V,v的度数(度) d(v)是v作为边的端点次数之和。

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

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

复习无向图中关联和度的定义，实验由一人一组完成。所设计程序能够通过编译；并能够根据给定无向图的各边所关联的顶点对，编程设计求出每个顶点的度数。 8、实验报告要求

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

（2）写出类c的算法，并写一个程序求出给定无向图的各边所关联的顶点对的每个顶点的度数。

（3）写出实验结束时的程序清单及运行结果及实验总结。

23

实验十六 求有向图中顶点的度数

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求出给定有向图顶点的度数，加深学生对关联及出度和入度的定义的理解。 3、实验内容

给定有向图的各边所关联的有序顶点对，编程设计求出每个顶点的入度和出度。 4、实验原理

设有向图D=, 其中V??称为顶点集, 其元素称为顶点或结点; E是V?V的多重子集, 称为边集, 其元素称为有向边，简称边。对有向图. 设ek =? vi, vj ?是有向图的一条边, 又称vi是ek的始点, vj是ek的终点, vi邻接到vj, vj邻接于vi。

v的入度d?(v)是v作为边的终点次数之和；v的出度d+(v)是v作为边的始点次数之和；v的度数(度) d(v)是v作为边的端点次数之和。其中d(v)= d+(v)+ d?(v) 5、实验仪器设备或软件环境及工具

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

复习有向图中关联、邻接和入度及出度的定义，实验由一人一组完成。所设计程序能够通过编译；并能够根据给定无向图的各边所关联的有序顶点对，编程设计求出每个顶点的入度和出度。 8、实验报告要求

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

（2）写出类c的算法，并写一个程序求出给定有向图的各边所关联的顶点对的每个顶点的入度和出度。

（3）写出实验结束时的程序清单及运行结果及实验总结。

24

第四章 代数系统

实验十七 判断是否为代数系统的算法

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现加深学生对代数系统的定义的理解。 3、实验内容

给定一个数字集合X={0，1，?..，n}，并给出一个运算*（*运算由运算表给出），要求能够判断出：

（1）是否为代数系统。 （2）* 运算是否是可交换的。 （3）* 运算是否是可结合的。 4、实验仪器设备或软件环境及工具

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

复习代数系统的定义，实验由几人一组完成。所编程序能够通过编译，并能够对给定的一个数字集合X={0，1，?..，n}与一个运算*（*运算由运算表给出），判断出是否为代数系统、* 运算是否是可交换的、* 运算是否是可结合的。 6、实验报告要求

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

（2）写出类c的算法，并编写一个程序判断出是否为代数系统、* 运算是否是可交换的、* 运算是否是可结合的。

（3）写出实验结束时的程序清单及运行结果及实验总结。 7、思考题

如果所给集合X由字母组成，如何编程判断是否为代数系统。

25

实验十八 判断是否为群的算法

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现加深学生对半群、含幺半群和群的定义的理解。 3、实验内容 要判断：

（1）是否为半群； （2）是否为含幺半群； （3）是否为群。 4、实验原理

对于代数系统，若*运算是可结合的，则是半群。显然，这一点与上一个实验中判断 * 运算的可结合性是完全一致的。若是半群且*运算有幺元，则是含幺半群。若是含幺半群，且每个元素关于* 运算都是可逆的，则是群。

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

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

复习半群、含幺半群和群的定义，实验由几人一组完成。所编程序能够通过编译，并能够对给定的一个代数系统判断出其是否为半群、含幺半群和群。 7、实验步骤

（1）判断是否满足结合律

①对于i=0，1，?，n，作②（2）。 ②对于j=0，1，?，n，作③。 ③对于k=0，1，?，n，作④~⑤。 ④x=aij；y=ajk。

⑤若axk?aiy，则* 运算不是可结合的，转⑦。 ⑥* 运算是可结合的。 ⑦结束。 （2）判断是否为群

①输入* 运算的运算表

26

给出一个代数系统，其中：G={1，2，?，n}，* 运算由运算表矩阵给出，

②（判断幺元）对于i=1，2，?，n，作（3）。

③对于所有的j（j=1，2，?，n），若A（i，j）=j且A（j，i）=j，则：i为幺元，i?y，转（5）。

④ 无幺元，转（8）。

⑤（判断逆元）对每一个i（i=1，2，?，n），作（6）。

⑥若存在j（j=1，2，?，n）使得：A（i，j）=Y且A（j，i）=y，则i有逆元，继续检查下一个i，否则i无逆元， 不是群，转（8）。

⑦ 是群。 ⑧结束。 8、实验报告要求

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

（2）设计出类c的算法并编写一个程序判断出所给代数系统G={1，2，?，n}，* 运算由运算表矩阵给出）是否为半群；是否为含幺半群；是否为群。 （3）写出实验结束时的程序清单及运行结果及实验总结。 9、思考题

如果所给代数系统，其中集合G由字母组成，如何编程判断是否为半群；是否为含幺半群；是否为群？

27

第五章 数理逻辑

实验十九 构造合式公式的真值表

1、 实验类型：验证性 2、 实验目的：

使学生熟练掌握利用计算机语言实现逻辑运算的基本方法。 3、

实验内容

对给出的任意一个合式公式（不超过四个命题变元），使学生会用C语言的程序编程表示出来，并且能够计算它在各组真值指派下所应有的真值，画出其真值表。 4、 实验原理

（1）逻辑联结词的定义方法

逻辑连接词“非”：设p为命题, 复合命题 “非p”(或 “p的否定”)称为p的否定式, 记作?p。符号?称作否定联结词,其真值是这样定义的：若 P 的真值是T,那么┐P真值是F；若P的真值是F,则┐P 的真值是T。

逻辑连接词“合取”：设p,q为二命题, 复合命题“p并且q”(或“p与q”)称为p与q的合取式, 记作p∧q, ∧称作合取联结词。它的真值是这样定义的：当且仅当 P 和 q 的真值都为 T 时，P∧q 的真值才为 T，否则P∧q 的直值为 F。

逻辑连接词“析取”：设 p,q为命题, 复合命题“p或q”称作p与q的析取式,记作p∨q, ∨称作析取联结词。它的真值是这样定义的：当且仅当 P 和 q 的真值都为 假（F） 时，P ∨ q 的真值才为 F，否则P ∨q 的直值为 T。

逻辑连接词“蕴涵”：设 p,q为二命题, 复合命题 “如果p,则q” 称作p与q的蕴涵式, 记作p?q. ?称作蕴涵联结词，运算对象P叫做前提（premise） 、假设(Hypothesis) 或前件，而q 叫做 结论(Conclusion) 或 后件。它的真值是这样定义的：当且仅当 P 是T ，而 q 是 F 时，P→ q 的真值才为 F，否则P →q 的直值为 T。

逻辑连接词“等价”：设p, q为命题, 复合命题 “p当且仅当q”称作p与q的等价式, 记作p?q, ?称作等价联结词。它的真值是这样定义的：当且仅当 P 和 q 有相同的真值 时，P ? q 的真值才为 T，否则 P ? q 的直值为 F。 （2）合式公式的表示方法

复合命题：由简单命题通过联结词联结而成的新命题叫复合命题。 合式公式(命题公式,公式)递归定义如下：

① 单个命题常项或变项是合式公式,并称作原子合式公式； ② 若A是合式公式, 则 (?A)也是合式公式；

③ 若A, B是合式公式, 则(A?B), (A?B), (A?B), (A?B)也是合式公式；

28

④ 只有有限次地应用(1)~(3)形成的符号串才是合式公式。

给出任意一个合式公式，我们可以将它用C程序表示出来，并且能够计算它在各组真值指派下所应有的真值（或是逻辑运算的结果）。这有多种方法。上面我们已经给出了逻辑连结词的定义，根据这种定义方法，我们也可以把一个合式公式表示成为条件语句中的条件表达式，这样我们就可以得到该合式公式的逻辑运算结果了。 （3）任意合式公式的真值表

真值：一个命题的真或假称为命题的真值。

真值表:命题公式在所有可能的赋值下的取值的列表，含n个变项的公式有2n个赋值。

构造真值表有如下约定： ① 命题变元按字典序排列；

② 对公式的每个解释，以二进制数从小到大或者从大到小顺序列出； ③ 若公式复杂，可先列出各子公式的真值(若有括号,则应从里层向外层展开)，最后列出所给公式的真值。 5、

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

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

实验要求

（1） 学生在实验操作过程中自己动手独立完成，几人为1组。

（2） 利用C语言或其他计算机语言编出基本逻辑运算程序和实现较复杂的命

题公式真值表的程序。 （3） 完成实验报告。 6、实验步骤及注意事项

（1）已知命题p和q的真值，求出它们的合取、析取、蕴涵和等价的真值。 （2）合式公式的表示

给出任意一个合式公式，我们可以将它用C程序表示出来，并且能够计算它在各组真值指派下所应有的真值（或是逻辑运算的结果）。

（3）构造任意合式公式的真值表

给出任意变元（不超过四个命题变元）的合式公式，构造该合式公式的真值表。 7、

思考题

（1） 试编程证明(? P?Q )? (P ?Q )为永真式。

（2） 公式类型可分为永真式、永假式和偶然式。构造算法，用程序判断任一公

式的类型，并输出相应的结果。

29

本文来源：https://www.bwwdw.com/article/rgj7.html