离散数学实验报告.doc

大连民族学院计算机科学与工程学院实验报告实验题目： 关系部分实验 课程名称： 离散数学 实验类型：演示性 验证性 操作性 设计性 综合性专业： 网络工程 班级： 102 班学生姓名：隋玉兴 学号：2010083220 实验日期：2011 年 12 月 25 日 实验地点：五机房实验学时： 实验成绩：指导教师签字： 年 月 日 一 实验目的本实验课程是信息专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。二. 实验内容A集合的运算1求集合的并集：已知所给集合A和B，求A与B 的并集C（C=AB）2求集合的交集：已知所给集合A和B，求A与B 的交集C（C=AB）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|xAxB，我们将集合A的各个元素与集合B的元素进行比较，若在集合B中存在某个元素并和集合A中一元素相等，则将该元素送入交集C之中。2求集合的交集：根据交集的定义：C=x|xAxB，我们将集合A的各个元素与集合B的元素进行比较，若在集合B中存在某个元素并和集合A中一元素相等，则将该元素送入交集C之中。3求集合的差集：差集C的定义：差集C=x|xAxB，即对于集合A中的元素ai，若不存在bjB（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=1mkj=1 mij=1。这个式子也可改写成为： mij =0 mik =0mkj=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=为无向图, vV,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的合取式, 记作pq, 称作合取联结词。它的真值是这样定义的：当且仅当 P 和 q 的真值都为 T 时，Pq 的真值才为 T，否则Pq 的直值为 F。逻辑连接词“析取”：设 p,q为命题, 复合命题“p或q”称作p与q的析取式,记作pq, 称作析取联结词。它的真值是这样定义的：当且仅当 P 和 q 的真值都为 假（F） 时，P q 的真值才为 F，否则P q 的直值为 T。逻辑连接词“蕴涵”：设 p,q为二命题, 复合命题 “如果p,则q” 称作p与q的蕴涵式, 记作pq. 称作蕴涵联结词，运算对象P叫做前提（premise） 、假设(Hypothesis) 或前件，而q 叫做 结论(Conclusion) 或 后件。它的真值是这样定义的：当且仅当 P 是T ，而 q 是 F 时，P q 的真值才为 F，否则P q 的直值为 T。逻辑连接词“等价”：设p, q为命题, 复合命题 “p当且仅当q”称作p与q的等价式, 记作pq, 称作等价联结词。它的真值是这样定义的：当且仅当 P 和 q 有相同的真值 时，P n q 的真值才为 T，否则 P n q 的直值为 F。（2）合式公式的表示方法复合命题：由简单命题通过联结词联结而成的新命题叫复合命题。合式公式(命题公式,公式)递归定义如下： 单个命题常项或变项是合式公式,并称作原子合式公式； 若A是合式公式, 则 (A)也是合式公式； 若A, B是合式公式, 则(AB), (AB), (AB), (AB)也是合式公式； 只有有限次地应用(1)(3)形成的符号串才是合式公式。给出任意一个合式公式，我们可以将它用C程序表示出来，并且能够计算它在各组真值指派下所应有的真值（或是逻辑运算的结果）。这有多种方法。上面我们已经给出了逻辑连结词的定义，根据这种定义方法，我们也可以把一个合式公式表示成为条件语句中的条件表达式，这样我们就可以得到该合式公式的逻辑运算结果了。（3）任意合式公式的真值表真值：一个命题的真或假称为命题的真值。真值表:命题公式在所有可能的赋值下的取值的列表，含n个变项的公式有2n个赋值。构造真值表有如下约定： 命题变元按字典序排列； 对公式的每个解释，以二进制数从小到大或者从大到小顺序列出； 若公式复杂，可先列出各子公式的真值(若有括号,则应从里层向外层展开)，最后列出所给公式的真值。五 源程序清单；A题部分源代码：B题部分源代码：C题部分源代码：D题部分源代码：六. 其他收获和体会。这个实验分4个题，A类题其实是很简单的，而C类题如果是在B类题的基础上构建，相对来说也是一个不困难的题，所以主要在B类题上花费了大量时间，一开始想用中序表达式转变为逆波兰式的方法来解决，但是总有一些零零散散的问题困扰，况且对于栈和二叉树之类的东西在学习C语言时接触很少，所以困难更大，经过多次失败后，还是最后用最简单同时也是最麻烦的方法来解决这个问题。利用函数一步步来解决，所以在个别功能上来说有一些不完美，比如纠错，因为时间有限，有个别地方没有设置出错提示。也许是很久没看C语言了，导致很多基本的语句都已经并不熟练了，通过这次实验，让我从一定程度上找回了一点以前做课程设计时的感觉。在编程过程中，最重要的其实是对细节方面的把握。A类题的逻辑抽象和编程语言的表达都非常基础，所以能不能把程序的细节考虑完善是非常重要的，有没有输入提示，错误提示等等，这些东西是考验一个人考虑问题的全面性的一个方式，我们应该从现在就养成这样良好的习惯。B类题，在设计上主要有以下几个问题：1.优先级的问题，要如何解决优先级的问题，最后我直接用先后执行来解决。2.括号问题，对于运算来说，解决括号问题很重要，而我是从最内级括号向外层层运算，最后得出结果。3.真值表问题，真值表