离散数学实验指导书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，判断：b
i =a
j
，若相等，则转（7）。
（6）否则，b
i?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）否则，将a
i 与集合B中的每个元素进行比较，若a
i
与集合B中所有元
素均不相同，则转（6）。
（5）否则，a
i?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，若不存
在b
j ∈B（j=1，2，…..，m），使得a
i
=b
j
，则a
i
∈差集C。
5、实验仪器设备或软件环境及工具
长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。
6、实验要求
复习集合运算中差集的定义，实验由一人一组完成。所编程序能够通过编译，并能够实现求两个给定集合的差集。
7、实验步骤及注意事项
（1）将集合A的元素个数送N。
（2）1?i。
（3）i>N，则结束。
（4）否则，将a
i 与集合B中的每个元素相比较，若a
i
与集合B中的某个
元素相同，则转（6）。
（5）否则，a
i?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={
成序偶 i ，b j >送入C之中即可。 5、实验仪器设备或软件环境及工具 长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。 6、实验要求 复习笛卡儿乘积的定义，实验由一人一组完成。所编程序能够通过编译，并能够实现求两个给定集合的笛卡儿乘积。 7、实验步骤及注意事项 （1）将集合A的元素个数送入N。 （2）将集合B的元素个数送入M。 （3）1?i。 （4）若i>N,则结束。 （5）1?j。 （6）若j>M，则转（9）。 （7） i ，b j >?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；若存在m ii =1，则R是自反的；否则R既不是自反关系也不是的；若存在m ii 反自反关系。 （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，若存在m ij =m ji ， 则R是对称的；（3）判断反对称性； （4）判断既是对称的又是反对称的； （5）判断既不是对称的又不是反对称的； （6）输出判断结果。 8、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类c的算法并编写一个程序判断给定集合上的关系是否为对称的。（3）写出实验结束时的程序清单及运行结果及实验总结。 实验七判关系R是否为可传递关系 1、实验类型：设计性 2、实验目的 通过算法设计并编程实现对给定集合上的关系是否为传递关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 3、实验内容 已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为传递关系。 4、实验原理 =1一个关系R的可传递性定义告诉我们，若关系R是可传递的，则必有：m ik =1? m ij=1。这个式子也可改写成为： m ij=0? m ik=0∨m kj=0。我们可以根∧m kj 据后一个公式来完成判断可传递性这一功能的。可传递性也是等价关系的必要条件，所以，本算法也可以作为判等价关系算法的子程序给出。 5、实验仪器设备或软件环境及工具 长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。 6、实验要求 复习关系的性质，实验由一人一组完成。所编程序能够通过编译，并能够实现对给定集合上的关系传递性质的判定。 7、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）设计出类c的算法并编写一个程序判断给定集合上的关系是否为传递的。（3）写出实验结束时的程序清单及运行结果及实验总结。 8、思考题 写出另一种判断关系传递性的算法，即在M(R·R)中，若任意r′ij=1 ，则中相应的元素r ij=1，并据此设计出关系传递性质判断的程序。 M R 实验八判断关系R是否为等价关系 1、实验类型：设计实验 2、实验目的 通过算法设计并编程实现对给定集合上的关系是否为自反的、对称的和传递关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断等价关系的方法。 3、实验内容 给定R的关系矩阵，据此判断所给关系R是否为等价关系。 4、实验原理 设R为非空集合A上的关系. 如果R是自反的、对称的和传递的, 则称R 为A上的等价关系。 5、实验仪器设备或软件环境及工具 长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。 6、实验要求 复习关系的性质，实验由几个人一组完成。所编程序能够通过编译，并能够实现对给定集合上的关系性质的判定。 7、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类c的算法并编写一个程序判断给定集合上的关系是否为等价关系。（3）写出实验结束时的程序清单及运行结果及实验总结。 8、思考题 设计一个程序，求出对给定的有限集合的所有划分。 实验九求等价类 1、实验类型：设计实验 2、实验目的 通过算法设计并编程实现对给定集合上的关系是否为自反的、对称的和传递关系的判断，加深学生对等价关系和等价类的理解，掌握求等价类的方法。 3、实验内容 给定一个集合A，及其上的一个等价关系R，求R上的等价类。 4、实验原理 给定任意关系，欲判断R是否为等价关系，可用实验八所给出的程序。但是，如果给定一个等价关系，那么它的关系矩阵必为对称矩阵。为了节省存储空间，只要存放关系矩阵的一半就可以了（另一半与这一半相同）。我们可以用一维数组来存放关系矩阵的下三角矩阵（包括主对角线在内），具体对应关系如下：根据等价类的定义可知，等价类内的各元素之间均有R关系，所以在构造等价类时，只要依据所给关系矩阵，把所有相互有R关系的各元素归为一类就可以了。在输出时，把每一类显示在同一行上。 5、实验仪器设备或软件环境及工具 长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。 6、实验要求 复习等价关系和等价类的定义，实验由几个人一组完成。所编程序能够通过编译，并能够实现求出给定集合上等价关系的等价类。 7、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）写出类c的算法并编写一个程序求出给定集合上的等价关系的等价类。（3）写出实验结束时的程序清单及运行结果及实验总结。 实验十由两个已知关系通过合成构造新的关系 1、实验类型：设计实验 2、实验目的 通过算法设计并编程实现求对给定的关系的合成关系，加深学生对合成关系运算的理解。 3、实验内容 设关系A是从集合X={1，2，….，n}到集合Y={1，2，…..，m}的二元关系，而关系B是从集合Y到集合Z={1，2，….，p}的二元关系，求A与B的合成关系C。 4、实验原理 由关系合成的定义可知：A B={ 5、实验仪器设备或软件环境及工具 长春工业大学计算机科学与工程学院计算机与信息综合实验中心提供相关软、硬件环境；学生也可自带实验设备。 6、实验要求 复习关系合成的定义，实验由一人一组完成。所编程序能够通过编译，并能够实现求给定集合上的关系的合成的运算。 7、实验报告要求 （1）写出实验过程中遇到的问题及其解决过程。 （2）设计出类c的算法并编写一个程序求出给定的两个关系的合成关系。（3）写出实验结束时的程序清单及运行结果及实验总结。 《离散数学》实验报告专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月 目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现 实验一联结词的运算 一.实验目的 通过上机实验操作,将命题连接词运算融入到C语言的程序编写中,一方面加强对命题连接词运算的理解,另一方面通过编程实现命题连接词运算,帮助学生复习与锻炼C语言知识,将理论知识与实际操作结合,让学生更加容易理解与记忆命题连接词运算。 二.实验原理 (1) 非运算, 符号:? ,当P=T时 ,?P为F, 当P=F时 ,?P为T 。 (2) 合取, 符号: ∧ , 当且仅当P与Q的真值同为真,命题P∧Q的真值才为真;否则,P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P与Q的真值同为假,命题P∨Q的真值才为假;否则,P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P与Q的真值不同时,命题P▽Q的真值才为真;否则,P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时,命题P→Q的真值才为假;否则,P→Q 的真值为真。 (6) 等价, 符号: ? , 当且仅当P,Q的真值不同时,命题P?Q的真值才为假;否 则,P→Q的真值为真。 三.实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include 实验1 1实验内容 （1）求任意一个命题公式的真值表。 （2）利用真值表求任意一个命题公式的主范式。 （3）利用真值表进行逻辑推理。 注：（2）和（3）可在（1）的基础上完成。 2实验目的 真值表是命题逻辑中的一个十分重要的概念，利用它几乎可以解决命题逻辑中的所有问题。例如，利用命题公式的真值表，可以判断命题公式的类型、求命题公式的主范式、判断两命题公式是否等价，还可以进行推理等。 本实验通过编写一个程序，让计算机给出命题公式的真值表，并在此基础上进行命题公式类型的判定、求命题公式的主范式等。目的是让学生更加深刻地理解真值表的概念，并掌握真值表的求解方法及其在解决命题逻辑中其他问题中的应用。 3算法的主要思想 利用计算机求命题公式真值表的关键是：①给出命题变元的每一组赋值；②计算命题公式在每一组赋值下的真值。 真值表中命题变元的取值具有如下规律：每列中0 和1 是交替出现的，且0 和1 连续出现的个数相同。n 个命题变元的每组赋值的生成算法可基于这种思想。 含有n个命题变元的命题公式的真值的计算采用的方法为“算符优先法”。 为了程序实现的方便，约定命题变元只用一个字母表示，非、合取、析取、蕴含和等价联结词分别用！、&、|、－、＋来表示。 算符之间的优先关系如表1-1所示： 表1-1算符优先级 优先算法，我们采用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是： （1）首先设置操作数栈为空栈，符号“@”为运算符的栈底元素； （2）调用函数Divi（exp，myopnd）得到命题公式包含的命题变元序列myopnd （按字典序排列，同一个命题变元只出现一次）； （3）依次读入命题公式中的每个字符，若是命题变元则其对应的赋值进OPND 栈，若是运算符，则和OPTR栈的栈顶运算符比较后作相应操作，直至整个命题公式求值完毕。 离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间 目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。 实验一命题逻辑公式化简 【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。 【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。 实验用例：用化简命题逻辑公式的方法设计一个 5 人表决开关电路，要求 3 人以上（含 3 人）同意则表决通过（表决开关亮）。 【实验原理和方法】 （1）写出5人表决开关电路真值表，从真值表得出5 人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。 （2）上面公式中的每一个联结词是一个开关元件，将它们定义成 C 语言中的函数。 （3）输入5人表决值（0或1），调用上面定义的函数，将5人表决开关电路真值表的等价公式写成一个函数表达式。 （4）输出函数表达式的结果，如果是1，则表明表决通过，否则表决不通过。 参考代码： #include 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以 根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足 《离散数学》实验报告 专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月 目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现 实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当P=T时，P为F, 当P=F时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当P,Q的真值不同时，命题P?Q的真值才为假；否则，P→Q的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include 大连民族学院 计算机科学与工程学院实验报告 实验题目：判断关系的性质 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性 专业：班级：学生姓名：学号： 实验日期：年月日实验地点： 实验学时：实验成绩： 指导教师签字：年月日 实验报告正文部分（具体要求详见实验报告格式要求） 实验报告格式 [实验题目] 判断关系的性质 [实验目的] 使学生掌握利用计算机语言实现判断关系性质的基本方法。[实验环境] Microsoft Visual C++6.0 [实验原理] 实验内容与要求：对给定表示有穷集上关系的矩阵，确定这个关系是否是自反的或反自反的；对称的或反对称的；是否传递的。 通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示： 程序源代码： #include scanf("%d",&M[i][j]); for(i=0;i 离散数学实验报告 姓名： 学号： 班级： 实验地点： 实验时间： 1 实验目的和要求 运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下： 八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km 。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？ 2 实验环境和工具 实验环境：Windows 7 旗舰版 工具：Dev-C++ 5.8.3 3 实验过程 3.1 算法流程图 3.2程序核心代码 //油管铺设问题Prim算法实现 #include /*输出邻接矩阵g*/ void DispMat(MGraph g){ int i,j; for (i=0;i 《离散数学》实验报告 专业 班级 姓名 学号 授课教师 二 O 一六年十二月 目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系实验三利用算法求关系的传递闭包实验四图的可达矩阵实现 实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当时，P为F, 当时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: → , 当且仅当P为为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当的真值不同时，命题P?Q的真值才为假；否则，P→Q 的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 <> () { ; ("请选择运算方式\n"); ("1.析取\n"); ("2.合取\n"); ("3.非\n"); ("4.蕴含\n"); ("5.等价\n"); m; (""); ( m>=1 m<=4 ) { ("请输入P Q的值\n"); (" " ); = 1; (m) { 1( ( >= 1)( < 4 ) ) { (0 0) ("P 析取Q = 0\n"); ("P 析取Q = 1\n"); ; (4) ; ("请输入P Q的值\n"); (" " ); } ; 2( ( >= 0)( < 4 ) ) { (1 1) ("P 合取Q = 1\n"); ("P 合取Q = 0\n"); ; (4) ; ("请输入P Q的值\n"); (" " ); } ; 3( ( >= 0)( < 4 ) ) { (0) ("非Q = 1\n"); ("非Q = 0\n"); 1.【实验目的】 对称： 通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法 自反： 通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 2.【实验内容】 已知关系R 由关系矩阵M 给出，要求判断由M 表示的这个关系是否为对称关 系。假定R 的关系矩阵为：?????? ? ??=1234210330124321M 3.【实验要求】 C 语言编程实现 4.【算法描述】 对称： 从给定的关系矩阵来判断关系R 是否为对称是很容易的。若M （R 的关系矩阵）为对称矩阵，则R 是对称关系；若M 为反对称矩阵，则R 是反对称关系。因为R 为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。 算法实现： （1） 输入关系矩阵M （M 为n 阶方阵）； （2） 判断对称性，对于i=2，3，….，n ；j=1，2,……，i-1，若存在m ij =m ji ， 则R 是对称的； （3） 判断反对称性； （4） 判断既是对称的又是反对称的； （5） 判断既不是对称的又不是反对称的； （6） 输出判断结果。 自反： 从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。 算法实现 （1）输入关系矩阵M（M为n阶方阵）。 （2）判断自反性，对于i=1，2，….，n；若存在m =0，则R不是自反 ii =1，则R是自反的；否则R既不是自反关系也不是的；若存在m ii 反自反关系。 （3）输出判断结果。 源代码 #include 《离散数学》 实验报告 题目 专业 学号 姓名 指导教师 提交日期 实验一五种连结词的逻辑运算 一.实验目的 用C语言实现两个命题变元的合取、析取、蕴涵和等价表达式的计算。熟悉连接词逻辑运算规则，利用程序语言实现逻辑这几种逻辑运算。 二.实验内容 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、蕴涵和等价四种运算的的真值。要求对输入内容进行分析，如果不符合0、1条件需要重新输入，程序有良好的输入输出界面。 三. 实验过程 1. 算法分析： 编程语言为c语言 合取/\：p，q都为1的时候为1，其他为0 析取\/：p，q都为0的时候为0，其他为1 蕴含->：p为1，q为0时为0，其他为1 等价<->：p，q同真同假 流程图 2. 程序代码： #include do{ printf("请输入q的值(0或1)"); scanf("%d",&q); if(q!=0&&q!=1) printf("输入有误"); }while(q!=0&&q!=1); do{ printf("请选择要进行的操作\n"); printf("1:合取\n2:析取\n3:蕴含\n4:等价\n"); scanf("%d",&i); switch(i){ case 1:{ if(p&&q) printf("合取运算：p/\q=1\n"); else printf("合取运算：p/\q=0\n"); break; } case 2:{ if(p||q) printf("析取运算：p\/q=1\n"); else printf("析取运算：p\/q=0\n"); break; } case 3:{ if(p&&!q) printf("蕴含：p->q=0\n"); else printf("蕴含：p->q=1\n"); break;} case 4:{ if((p&&q)||(!p&&!q)) printf("等价运算：p<->q=1\n"); else printf("等价运算：p<->q=0\n"); break; } }printf("是否继续运算1\\0\n"); scanf("%d",&t); }while(t); return 0; } 离散数学实验指导书2015 年3月6 日 绪言 通常对离散数学教学的认识就是上课老师讲述一个个概念、定理、公式和例题，学生背概念、公式，理解基础上记忆定理，然后据此做证明题、计算以及解题。实质上离散数学不仅仅是这些，还有实验。在理论教学过程中，学生的活动只是“智力活动”，或更为直接地说是解题活动，教师在上面讲离散数学，而学生则每天在课堂上听课并在纸上做题目。这样，对多数学生而言，离散数学的发现探索活动没有能够真正开展起来。 离散数学实验教学，通常由教师提出问题，让学生在计算机上做实验，利用小组合作学习或者组织全班讨论，开展研究性学习活动；实验过程中，依靠计算机，让学生主动参与发展、探究、解决问题，从中获得离散数学研究、解决实际问题的过程体验、情感体验，产生成就感，进而开发学生的创新潜能，因而对离散数学实验课程教学进行研究具有重要意义。 利用计算机进行离散数学实验教学，不仅是开展离散数学研究性学习的一种有效方式，而且也为数据结构及程序设计课程教学的开展提升了层次。知识经济时代对创新人才的需求与离散数学教育中忽视学生创造性能力培养的矛盾日益凸显。在教学中倡导研究性学习，开展离散数学实验课程教学的研究与探索，与当前社会对离散数学教学的需求是一致的。 目前国内外很少有人对离散数学实验课程教学进行研究，尤其是国内进行这方面研究的人员更少，人们更重视离散数学理论课程教学的研究，忽视了离散数学实验课程对理论课程教学的辅助与促进作用，也忽视了离散数学实验课程与数据结构等课程的有机联系。因而本学期离散数学课程组依据“2014培养方案”准备进行离散数学实验课程教学的研究与探索，以便更好的做好离散数学课程的教学改革工作。 主要包括四个部分：集合与关系、数理逻辑、代数系统、图论。要求学生了解算法，理解运用C或C++语言（也可以是其他高级程序设计语言）把书中的部分内容的算法编写出能在计算机上运行的程序的思想，掌握实现离散数学部分算法程序设计的基本编程技术。 离散数学实验报告 题目：判断关系R是否为对称关系院系： 班级： 姓名： 学号： 【实验目的】 学会用编程实现判断关系是否为对称关系，反对称关系，既对称又反对称，既不对称又不反对称。 【实验内容】 编写C++程序,实现对关系矩阵R是否为对称关系、反对称关系、既是对称关系又是反对称关系、既不是对称关系又不是反对称关系的判断，并输出结果。关系矩阵R的内容参照离散数学书 p54-【例2-28】【例2-29】【例2-30】. 增加内容：根据实际程序编写情况,完成对关系矩阵R是否为传递关系的判断.（不包含于报告中） 【实验原理】 对称性：设R含于A×A，对于任意x，y∈A，如果（x,y）∈R，那么有（y，x）∈R。 反对称性：设R含于A×A，对于任意x，y∈A，若x≠y，如果（x,y）∈R 与（y，x）∈R不能同时成立。 Ia(恒等关系）中的元素不影响对称性与反对称性。 【程序代码】 #include { if(i!=j) { if(a[i][j]==1&&a[j][i]==1) x++; if(a[i][j]==1&&a[j][i]!=1) y++; } else { if(a[i][j]==1) z++; } } } if(x!=0&&y==0) printf("关系矩阵为对称关系\n"); if(y!=0&&x==0) printf("关系矩阵为反对称关系\n"); if(z!=0&&x==0&&y==0) printf("关系矩阵既为对称关系也为反对称关系："); if(x&&y) printf("关系矩阵既不是对称关系也不是反对称关系："); return 0; } 【实验结果】 【实验心得】 此次实验让我深刻的体会到离散数学关系性质的相关内容也让我深刻地体会到关 一、实验目的：掌握图的存储表示和以及图的最小生成树算法。 二、实验内容： 1.实现图的存储，并且读入图的内容。 2.利用克鲁斯卡尔算法求网络的最小生成树。 3.实现构造生成树过程中的连通分量抽象数据类型。 4.以文本形式输出对应图的最小生成树各条边及权值。 三、实验要求： 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 需求分析： 1、利用克鲁斯卡尔算法求网的最小生成树； 2、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列； 3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩 阵以及按权排序后的边和最后得到的最小生成树； 克鲁斯卡尔算法：假设WN=(V,{E}) 是一个含有n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有n-1条边为止。 测试数据： 自行指定图进行运算 四、详细设计 源程序 #include 《离散数学》实验报告 姓名： 学号： 班级： 实验一连结词逻辑运算 一.实验目的 实现二元合取、析取、蕴涵和等价表达式的计算。熟悉连接词逻辑运算规则，利用程序语言实现逻辑这几种逻辑运算。 二.实验内容 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、蕴涵和等价四种运算的真值。要求对输入内容进行分析，如果不符合0、1条件需要重新输入，程序有良好的输入输出界面。 三.实验环境 使用Microsoft Visual C++6.0为编程软件，采用称C/C++语言为编程语言实现。 四.实验过程 1.算法分析: 合取：p，q都为1的时候为1，其他为0 析取：p，q都为0的时候为0，其他为1 蕴含：p为1，q为0时为0，其他为1 等价：p，q同真同假 2.程序代码: #include p=1; else p=0; printf("\t%d",p); } } printf("\n 非Q的值"); for(P=0;P<2;P++) { for(Q=0;Q<2;Q++) { if(Q==1)/*判断非Q的值*/ q=0; else q=1; printf("\t%d",q); } } printf("\n P与Q的值"); for(P=0;P<2;P++) { for(Q=0;Q<2;Q++) { if(Q==0||P==0)/*判断P与Q的值*/ a=0; else a=1; printf("\t%d",a); } } printf("\n P或Q的值"); for(P=0;P<2;P++) { for(Q=0;Q<2;Q++) { if(Q==1||P==1)/*判断P或Q的值*/ b=1; else b=0; printf("\t%d",b); } } printf("\nP蕴含Q的值"); for(P=0;P<2;P++) 《离散数学应用实践》 实验报告 课序号： 03 学号： 姓名： 任课教师：陈瑜 评阅成绩： 评阅意见： 提交报告时间：2014年 1 月 3 日 判断图的强连通，单连通，弱连通，判断树， 求强分图 （一）问题描述 （二）算法分析 （三）程序源代码 （四）测试数据与运行结果 （五）算法复杂性分析与讨论 （一）问题描述 编写一个程序，从控制台输入一个用邻接矩阵表示的图，程序实现判断该图的强连通性，弱连通性，单连通性，判断该图是否为树，求强分图等操作，并从控制台输出判断结果。 （二）算法分析 程序流程图： 1.判断图的强连通性 运用warshall算法先求其可达矩阵，判断可达矩阵元素是否全为一，全为一则具有强连通性；否则不具有。 2.判断图的单连通性 运用warshall算法先求其可达矩阵，判断可达矩阵元素与其对角元素是否全为零,全为零则不具有单连通性；否则具有。 3.判断图的弱连通性 先求其基图，若可达矩阵元素与其对角元素有一个为一，则将其都置一，同时将其可达矩阵主对角线元素全置一，从而得到其基图。然后再运用warshall算法求其可达矩阵，判断其强连通性，若其基图具有强连通性，则此图具有弱连通性；否则不具有。 4.判断图是否为树 此部分是对于无向图进行判断，先判断此图的强连通性，若不具有强连通性，则不是树；若具有强连通性，再统计其节点总度数，求其边数，如果边数等于顶点数减一，则为树，否则不为树。 5.求图的强分图 同样，先运用warshall算法先求其可达矩阵，然后对其可达矩阵求其转置，与其转置中的对应元素进行“&&”处理，并置主对角元素为一，得到其强分图矩阵。 下面是求强分图的伪码： While（i 《MATLAB及应用》实验指导书 班级： 姓名： 学号： 总评成绩： 汽车工程系 电测与汽车数字应用中心 目录 实验04051001 MATLAB语言基础 (1) 实验04051002 MATLAB科学计算及绘图 (5) 实验04051003 MATLAB综合实例编程 (7) 实验04051001 MATLAB 语言基础 1实验目的 1) 熟悉MATLAB 的运行环境 2) 掌握MATLAB 的矩阵和数组的运算 3) 掌握MATLAB 符号表达式的创建 4) 熟悉符号方程的求解 2实验内容 说明：从下面的题目、第1~4章课后习题中任选10题，学号为奇数的选择奇数号题，学号为偶数的选择偶数号题，并在答案之前标注题目来源，例如“课本第1章题2”、“指导书题3”等。可以采用notebook 格式输出结果（关于notebook 请查阅其他参考资料，或上网搜索） 例如： 课本第4章题1.一个半径为r 的求体积V 和表面积A 分别为:3 3 4r V π= 、24r A π= a.给出以下程序的伪代码描述：计算当30≤≤r 米时的V 和A ，并同时绘制V 相对于A 的图形。 b.编写和运行部分a 中所描述的程序。 解：clc,clear; r=0:0.1:3; V=4/3*pi*r.^3; A=4*pi*r.^2; plot(A,V);grid on; xlabel('Surface Area'); ylabel('Volume'); 1.在一个已知的测量矩阵T（100×100）中，删除整行全为0的行，删除整列内容全为0的整列 （判断某列元素是否为0方法：检查T(: , i) .* (T(: , j))是否为0）。 2.假设汽车系在下列各年度的人口统计如表所示 试用一个二维矩阵STU表示上述数据，并请计算出下列各数值： （1）汽车系在2002~2006年之间的每年平均新生、毕业生人数。 （2）5年来汽车系共有多少毕业生？ （3）在哪几年，新生数目比毕业生多？ （4）5年来每年的毕业生对新生的比例平均值为何？ 3.完成下列矩阵运算： 云南大学数学系《离散数学实验》上机实验报告 一、实验目的 求两个布尔矩阵的乘积 二、实验内容 1.描述布尔矩阵乘积的算法 2.编程实现布尔矩阵的乘积 三、使用环境 TC 四、算法介绍 Algorithm：the Boolean product Input：two Boolean matrices and Output：the Boolean product Begin Step1: FOR i=1 THRU m FOR j=1 THRU n FOR k=1 THRU p IF(=1 and =1) THEN =1 BREAK ELSE =0 Step2: RETURN([]) End 五、调试过程 1.程序代码： #include flag=0; for(k=0;k “离散数学”实验报告 （实验C） 专业：自动化 班级：0804班 学号：000000 姓名：何有* 日期：2010年10月31日 一、实验目的 通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，包括联结词、真值表、主范式等，提高学生编写实验报告、总结实验结果的能力，培养学生的逻辑思维能力和算法设计的思想，能够独立完成简单的算法设计和分析，进一步用它们来解决实际问题，帮助学生学习掌握C/C++语言程序设计的基本方法和各种调试手段，使学生具备程序设计的能力。 二、实验内容 求任意一个命题公式的真值表，并根据真值表求主范式。 三、实验环境 C语言编程环境。 四、实验原理和实现过程 （一）、关于命题公式的形式和运算符（即联结词）的运算 首先根据离散数学的相关知识，命题公式由命题变元和运算符（即联结词）组成，命题变元用大写字母英文表示（本次试验没有定义命题常元T和F，即T、F都表示命题变元），每个命题变元都有两种真值指派0和1，对应于一种真值指派，命题公式有一个真值，由所有可能的指派和命题公式相应的真值按照一定的规范构成的表格称为真值表。 目前离散数学里用到的包括扩充联结词总共有九种，即析取（或）、合取（与）、非、蕴含、等值、与非、或非、异或、蕴含否定，常用的为前五种，其中除了非运算为一元运算以外，其它四种为二元运算。所以本次实验设计时只定义了前五种运算符，同时用“/”表示非，用“*”表示合取，用“+”表示析取，用“>”表示蕴含，用“:”表示等值，且这五种运算符的优先级依次降低，如果需用括号改变运算优先级，则用小括号()改变。 以下为上述五种运算符运算时的一般真值表，用P和Q表示命题变元：1．非，用“/”表示 《离散数学》课程实验指导书 《离散数学》实验指导书 合肥工业大学计算机与信息学院 王晓华，杨娟，李书杰，汪荣贵 2019年09月 目录 目录 (1) 概述 (3) 第一篇数理逻辑 (4) 实验1 逻辑运算表示与验证 (4) 1.1 实验要求和目的 (4) 1.2 实验课时 (4) 1.3 实验环境 (4) 1.4 实验平台简介 (4) 实验2 交通信号灯模型设计 (6) 2.1 实验要求和目的 (6) 2.2 实验课时 (6) 2.3 实验环境 (6) 2.4 思考题 (6) 第二篇集合与关系 (7) 实验3 小型关系数据库系统实现 (7) 3.1 实验要求和目的 (7) 3.2 实验课时 (7) 3.3 实验环境 (7) 3.4 实验平台简介 (7) 实验4 关系的闭包运算及Floyd-Warshall算法求解 (10) 4.1 实验要求和目的 (10) 4.2 实验课时 (10) 4.3 实验环境 (10) 4.4 实验平台简介 (10) 第三篇整数论 (12) 实验5 数论之模运算 (12) 5.1 实验要求和目的 (12) 5.2 实验课时 (12) 5.3 实验环境 (12) 5.4 实验平台简介 (12) 第四篇图论 (16) 实验6 最短路径的Dijstra与Floyd-Warshal算法实现 (16) 6.1 实验要求和目的 (16) 6.2 实验课时 (16) 6.3 实验环境 (16) 6.4 实验平台简介 (16) 实验7 欧拉回路的DFS或Fleury算法求解 (20) 7.1 实验要求和目的 (20) 7.2 实验课时 (20) 7.3 实验环境 (20) 7.4 实验平台简介 (20) 实验8 最优树的Huffman算法求解 (22) 8.1 实验要求和目的 (22) 8.2 实验课时 (22) 8.3 实验环境 (22) 8.4 实验平台简介 (22) 实验9 多相位交通信号灯智能控制模型设计与算法实现 (24) 9.1 实验要求和目的 (24) 9.2 实验课时 (25) 9.3 实验环境 (25) 9.4 思考题 (25) 附录A：实验报告 (26)离散数学实验报告
离散数学上机实验1
离散数学实验报告
(完整版)离散数学实验指导书及其答案
离散数学实验报告--四个实验!!!
离散数学实验报告()
离散数学实验报告
离散数学实验报告
离散数学实验报告格式
离散数学关系性质的C++或C语言判断实验报告
离散数学实验报告
离散数学实验指导书
离散数学实验报告
离散数学--最小生成树实验报告
最新离散数学上机实验报告
离散数学实践试验报告--格式
《MATLAB及Simulink应用》实验指导书+答案
离散数学实验报告2
离散数学实验报告
《离散数学》实验指导书-2019版
相关主题
文本预览