离散数学实验报告

大连民族学院

计算机科学与工程学院实验报告

实验题目： 关系部分实验 课程名称： 离散数学 实验类型：□演示性 □验证性 □操作性 □设计性 ■综合性 专业： 网络工程 班级： 102 班 学生姓名：隋玉兴 学号：2010083220

实验日期：2011 年 12 月 25 日 实验地点：五机房 实验学时： 实验成绩：

指导教师签字： 年 月 日

一．实验目的

本实验课程是信息专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。

熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。

二. 实验内容

A集合的运算

1求集合的并集：已知所给集合A和B，求A与B 的并集C（C=A∪B） 2求集合的交集：已知所给集合A和B，求A与B 的交集C（C=A∩B） 3求集合的差集：已知所给集合A和B，求A与B的差集C（C=A-B）。

B判断关系R的性质

1判断关系R是否为自反关系：已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为自反关系

2判断关系R是否为对称关系： 已知关系R由关系矩阵M给出，要求判断由M表示的这个

关系是否为对称关系

C求无向图中顶点的度数

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

D判断是否为群的算法

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

（1）是否为半群； （2）是否为含幺半群； （3）是否为群。

三.实验环境；

使用visual C++6.0为编程软件，采用C语言为编程语言实现。

四. 实验原理和实现过程（算法描述）；

A集合的运算

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

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

3求集合的差集：差集C的定义：差集C={x|x∈A∧x?B}，即对于集合A中的元素ai，若不存在bj∈B（j=1，2，?..，m），使得ai=bj，则ai ∈差集C。

B判断关系R的性质

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

2判断关系R是否为对称关系：从给定的关系矩阵来判断关系R是否为对称是很容易的。若M（R的关系矩阵）为对称矩阵，则R是对称关系；若M为反对称矩阵，则R是反对称关系。因为R为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。

3判关系R是否为可传递关系：一个关系R的可传递性定义告诉我们，若关系R是可传递的，则必有：mik=1∧mkj=1? mij=1。这个式子也可改写成为： mij =0? mik =0∨mkj=0。我们可以根据后一个公式来完成判断可传递性这一功能的。可传递性也是等价关系的必要条件，所以，本算法也可以作为判等价关系算法的子程序给出。

C求无向图中顶点的度数

设无向图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作为边的端点次数之和。

D构造合式公式的真值表

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)也是合式公式； ④ 只有有限次地应用(1)~(3)形成的符号串才是合式公式。

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

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

真值表:命题公式在所有可能的赋值下的取值的列表，含n个变项的公式有2个赋值。 构造真值表有如下约定： ① 命题变元按字典序排列；

② 对公式的每个解释，以二进制数从小到大或者从大到小顺序列出；

n

③ 若公式复杂，可先列出各子公式的真值(若有括号,则应从里层向外层展开)，最后列出所给公式的真值。

五 源程序清单；

A题部分源代码： B题部分源代码： C题部分源代码： D题部分源代码：

六. 其他收获和体会。

这个实验分4个题，A类题其实是很简单的，而C类题 …… 此处隐藏：2286字，全部文档内容请下载后查看。喜欢就下载吧 ……