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

实验四 判断关系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