大连民族大学软件工程离散数学课程设计.docx

《大连民族大学软件工程离散数学课程设计.docx》由会员分享，可在线阅读，更多相关《大连民族大学软件工程离散数学课程设计.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大连民族学院计算机科学与工程学院实验报告实验题目： 1. 二元关系 2. 代数系统 课程名称： 离散数学 实验类型：演示性 验证性 操作性 设计性 R综合性专业：软件工程 班级：132班 学生姓名：黄正勤 学号：2013082204 实验日期：2014年11月22日12月15日 实验地点：金石滩校区机房实验学时：16学时 实验成绩：指导教师：焉德军 姜楠 二元关系（一）1. 实验题目对给定表示有穷集上关系的矩阵，确定这个关系是否是自反的或反自反的；对称的或反对称的；是否传递的。2. 实验原理从给定的关系矩阵来断判关系R是否为自反是很容易的。若flay（R的关系矩阵）的主对角线元素均为1，则R是

2、自反关系；若flay（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若flay（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。而对于对称性，只需要判断矩阵所有的flayij与其对应的flayji是否都相等；若全部相等，则为对称；否则反之。对于传递性，则需要利用线性代数的方法求出R的关系矩阵的平方矩阵，只需验证所有的flagij（R的关系矩阵的平方矩阵）等于1的地方，在flayij（R的关系矩阵）等于1，则具有传递性；否则反之。3. 实验的步骤及实验记录 0 1 1（1）先输入一个整数，表示矩阵的阶数。接着输入矩阵，这里以输入矩阵0 0 1 0 0 0例，

3、在根据矩阵左上到右下的flayii的值是否为1判断矩阵是否自反或反自反，判断矩阵是否自反或反自反的代码如下：for (i = 0; i a; i +)for (j = 0; j a; j+) if (i = j)if (flay ij = 1)count_1 +;else if (flay ij = 0)count_2 +;if (count_1 = a)cout 自反 endl;else if (count_2 = a)cout 反自反 endl;输入矩阵后输出的实验结果如下：（2）判断对称的或反对称只需要flayij是否与flayji相等；若全部相等，则为可对称；否则反之。代码如下：for

4、 (i = 0; i a; i +)for (j = 0; j a; j+)if (flay ij = flay ji)count_1 +;elsecount_2 = 1;break;if (count_1 = a * a)cout 对称性 endl;else if (count_2 = 1)cout 反对称 endl;break;运行结果如下：（3） 而对于判别是否具有传递性，则相对前面两个性质来说比较复杂，关键是求出原矩阵flay的平方矩阵flag，这里通过线性代数的方法求出flay矩阵的平方矩阵flag，求平方矩阵的方法是：第一个矩阵flayij等于flayij乘以第二个矩阵的第j列之总

5、和；j+完后再i+，以后便可求出平方矩阵。然后在比较在平方矩阵flagij为1的位置，在原矩阵flayij中是否都为1；若flag矩阵中所有的为1的地方，在flay中都为1，则具有传递性；否则反之；最后输出该平方矩阵。代码如下所示：int k;for (i = 0; i a; i +)for (j = 0; j a; j+) flag ij = 0;for (k = 0; k a; k +)flag ij = flag ij + flay ik * flay kj;if (flag ij = 1)count_2 +;for (i = 0 ; i a ; i +)for (j = 0; j a;

6、 j+)if (flag ij = 1 & flay ij = 1)count_3 +;else if (flag ij = 1 & flay ij = 0)count_1 = 1;break;if (count_1 = 1)break;if (count_2 = count_3 & count_2 != 0 & count_3 != 0)cout 传递性 endl;elsecout 非传递性 endl;cout 该矩阵的平方为： endl;for (i=0; i a; i+)for (k=0; k a; k+)cout flag ik ;cout b endl;运行结果如下：以上便是对自反或

7、反自反，对称或反对称，是否传递等性质的判断过程，代码及运行代码的结果。4. 实验总结此题为验证性题目，验证性题目主要是通过其原理以及相关的概念来证明。通过此题对验证性题目的分析有很大的提高。 (二)1. 实验题目判断一个二元关系是否为等价关系，如果是，求其商集。2. 实验原理要判断一个二元关系是否是等价关系，则要判断这个关系是否具有自反性，对称性和传递性；假如这三个条件都同时符合，则该二元关系具有等价关系。这里以为A=1，2，3，4,5,6,7，R=, U Ia 为例。自反性的判别与上题一样，都是判别flayii是否都等于1；若flayii全部等于1，则具有自反性；否则反之。对于对称性与上题也

8、一样，就是判断所有的flayij与flayji是否全部相等；若全部相等，则具有对称性；否则反之。传递性的判断，则需要利用线性代数的方法求出R的关系矩阵的平方矩阵，只需验证所有的flagij（R的关系矩阵的平方矩阵）等于1的地方，在flayij（R的关系矩阵）等于1，则具有传递性；否则反之。3. 实验步骤及实验记录（1） 先输入一个整数，表示矩阵的阶数；接着输出初始空矩阵。然后一组一组的输入R在A上的关系，输入0 0时结束；接着输出关系矩阵，判别与输入的关系是否一致。代码如下所示：void Input ()for (i = 1; i = n; i +)for (j = 1; j = n; j+)

9、flay ij = 0;for (i = 1; i = n; i +)for (j = 1; j = n; j+)cout flay ij ;cout endl;R();void R()cout 请输入两个位置有关系的数值,输入“0 0”结束R的输入： a b;if (a != 0 & b != 0)flay ab = 1;R();void Output()for (i = 1; i = n; i +)for (j = 1; j = n; j+)cout flay ij ;cout endl;代码运行结果如下所示：（2） 在根据矩阵左上到右下flayii的值是否为1判断矩阵是否是自反或反自反，

10、判断矩阵是否自反或反自反的代码如下：int count = 0;for (i = 1; i = n; i +)for (j = 1; j = n; j+) if (i = j)if (flay ij = 1)count_1 +;else if (flay ij = 0)count_2 +;if (count_1 = n)cout 自反性 endl;syb_3 = 1;elsecout 反自反性 endl;代码运行结果如下所示：（3） 判断对称的或反对称只需要flayij是否与flayji相等；若全部相等，则为可对称；否则反之。代码如下：for (i = 1; i = n; i +)for (j

11、 = 1; j = n; j+)if (flay ij = flay ji)count_1 +;elsecount_2 = 1;break;if (count_2 = 1)break;if (count_2 = 1)cout 反称性 endl;elsecout 对称性 endl;syb_1 = 1;代码运行结果如下所示：（4） 而对于判别是否具有传递性，则相对前面两个性质来说比较复杂，关键是求出原矩阵flay的平方矩阵flag，这里通过线性代数的方法求出flay矩阵的平方矩阵flag，求平方矩阵的方法是：第一个矩阵flayij等于flayij乘以第二个矩阵的第j列之总和；j+完后再i+，以后便

12、可求出平方矩阵。然后在比较在平方矩阵flagij为1的位置，在原矩阵flayij中是否都为1；若flag矩阵中所有的为1的地方，在flay中都为1，则具有传递性；否则反之；最后输出该平方矩阵。代码如下所示：int k;for (i = 1; i = n; i +)for (j = 1; j = n; j+) flag ij = 0;for (k = 1; k = n; k +)flag ij = flag ij + flay ik * flay kj;if (flag ij != 0)count_2 +;for (i = 1 ; i = n ; i +)for (j = 1; j = n; j

13、+)if (flag ij != 0 & flay ij = 1)flag ij = 1;count_3 +;else if (flag ij != 0 & flay ij = 0)flag ij = 1;count_1 = 1;break;if (count_1 = 1)break;if (count_2 = count_3 & count_2 != 0 & count_3 != 0)cout 传递性 endl;syb_2 = 1;elsecout 非传递性 endl;cout 该矩阵的平方为： endl;for (i = 1; i = n; i +)for (k = 1; k = n; k

14、 +)cout flag ik ;cout b endl;代码运行结果如下所示：(5) 对于商集，只需判断哪个几个原变元之间同时具有自反，对称和传递关系即可。代码如下所示：cout 其商集为： endl;int a100;if (syb_1 = 1 & syb_2 = 1 & syb_3 = 1)for(i = 1; i = n; i +)ai = i;for(i = 1; i = n; i +)if(ai != 0)cout ;for(j = 1; j = n; j +)if(flayij != 0 & aj != 0)cout aj ;aj = 0;cout b ;elsecout 不是等

15、价关系 endl;cout 不存在商集 endl;运行结果如下：4. 实验总结通过此题不仅可以熟悉等价关系的概念和条件，还可以理解商集的含义以及求商集的方法。提高对问题的分析能力和答题能力。代数系统1. 实验题目输入代数系统G，*的集合G和 * 运算的运算表，判断G，*是否是群。2. 实验原理判断一个代数系统是否为群的三个条件为：该代数系统是可结合的半群，具有幺元的独异点，G上每个元素都有逆元。即是代数系统，*为二元运算，如果*运算时可结合的，存在单位元e在G内，并且对G中任何元素X都有X-1在G内，则称为群。证明 * 运算可结合的原理是(X * Y) * Z = X * (Y * Z)即可。

16、要证明死独异点，则要证el * X = x 且 X * er = X， 则e就是幺元即可。而要证明有逆元，即证明yl * X = e(e为逆元)且X * yr = e（e为逆元）则y就是逆元即可。这就是证明群的原理。3. 实验步骤及实验记录* eabce eabc本题以代数系统a aecb为例b bceac cbae(1) 输入一个整数N，表示有N个变量；在逐个输入变元，然后在逐个输入两个变元关于 * 运算后相应的结果，最后输出该代数系统。代码如下：cout n;for (k = 1; k = n; k +)cout 请输入第 k flay k;for (i = 1; i = n; i +)f

17、or (j = 1; j = n; j +)cout 请输入 flay i 与 flay j aij;运行结果如下所示：（2） 证明可结合性，其原理是在一个代数系统中(X * Y) * Z = X * (Y * Z)，此处是本人认为用代码证明群的难点所在。需要用一个compute（i, j）函数去查找X,Y关于* 运算后的结果，再用conpute（i， j）函数返回来的值在做一次compute(i, j)函数得出最后结果。这样既可以比较（X * Y）* Z 与 X * （Y * Z）的值是否一样。代码如下：void JieHe()for (i = 1; i = n; i +)for (j =

18、1; j = n; j +)for (k = 1; k = n; k +)if (compute (compute (i, j), k) = compute (i, compute (j, k)count_1 +;elsecount_2 = 1;break;if (count_2 = 1)break;if (count_2 = 1)break;if (count_2 = 1)cout 该代数系统不可结合！ endl;exit (0);if (count_1 = n * n * n)cout *运算可结合！ endl 该代数系统为半群！ endl endl;int compute (int x,

19、 int y)for ( t = 1; t = n; t +)if (flay t = axy)return t;return -1; 运行结果如下所示：（3） 证明有幺元，即为独异点。要证明el * X = x 且 X * er = X， 则e就是幺元。代码如下所示：for (i = 1, s = 1; i = n; i +)count_1 = 0;count_2 = 0;for (j = 1; j = n; j +)if (aij = flay j)count_1 +;if (count_1 = n)for (k= 1; k = n; k +)if (aki = flay k)count_

20、2 +;if (count_2 = n)cout 幺元为： flay i endl;s = flay i;count_3 +;if (count_3 != 0)cout 该代数系统是独异点！ endl endl;elsecout 该代数系统不是独异点！ endl endl;exit (0);运行结果如下：（4） 证明有逆元。即证明yl * X = e(e为幺元)且X * yr = e（e为幺元）则y就是逆元。代码如下所示：for (i = 1; i = n; i +)for (j = 1; j = n; j +)if (aij = s & aji = s)cout flay i 是 flayj 的逆元！ endl;count_4 +;cout endl;if (count_4 = n)cout 该代数系统存在逆元！ endl 恭喜您，该代数系统是群！ endl endl;elsecout 此代数系统不是群！ endl;代码运行结果如下：4. 实验总结此题为验证性题目，通过做出此题，了解了群的概念，群的定义以及求群的条件，即：运算可结合，存在单位元，每个原变元都存在逆元。此题还涉及到了矩阵相乘的方法，可以很好的锻炼思维能力和理解能力。