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

大连民族学院计算机科学与工程学院实验报告实验题目：1.二元关系2.代数系统课程名称：离散数学实验类型：□演示性□验证性□操作性□设计性综合性专业：软件工程班级：132班学生姓名：黄正勤学号：2013082204实验日期：2014年11月22日—12月15日实验地点：金石滩校区机房实验学时：16学时实验成绩：指导教师：焉德军姜楠二元关系（一）1.实验题目对给定表示有穷集上关系的矩阵，确定这个关系是否是自反的或反自反的；对称的或反对称的；是否传递的。2.实验原理从给定的关系矩阵来断判关系R是否为自反是很容易的。若flay（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若flay（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若flay（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。而对于对称性，只需要判断矩阵所有的flay[i][j]与其对应的flay[j][i]是否都相等；若全部相等，则为对称；否则反之。对于传递性，则需要利用线性代数的方法求出R的关系矩阵的平方矩阵，只需验证所有的flag[i][j]（R的关系矩阵的平方矩阵）等于1的地方，在flay[i][j]（R的关系矩阵）等于1，则具有传递性；否则反之。3.实验的步骤及实验记录011（1）先输入一个整数，表示矩阵的阶数。接着输入矩阵，这里以输入矩阵001000例，在根据矩阵左上到右下的flay[i][i]的值是否为1判断矩阵是否自反或反自反，判断矩阵是否自反或反自反的代码如下：for(i=0;ia;i++){for(j=0;ja;j++){if(i==j){if(flay[i][j]==1)count_1++;elseif(flay[i][j]==0)count_2++;}}if(count_1==a)cout自反endl;elseif(count_2==a)cout反自反endl;输入矩阵后输出的实验结果如下：（2）判断对称的或反对称只需要flay[i][j]是否与flay[j][i]相等；若全部相等，则为可对称；否则反之。代码如下：for(i=0;ia;i++){for(j=0;ja;j++){if(flay[i][j]==flay[j][i])count_1++;else{count_2=1;break;}}if(count_1==a*a)cout对称性endl;elseif(count_2==1){cout反对称endl;break;}}运行结果如下：（3）而对于判别是否具有传递性，则相对前面两个性质来说比较复杂，关键是求出原矩阵flay的平方矩阵flag，这里通过线性代数的方法求出flay矩阵的平方矩阵flag，求平方矩阵的方法是：第一个矩阵flay[i][j]等于flay[i][j]乘以第二个矩阵的第j列之总和；j++完后再i++，以后便可求出平方矩阵。然后在比较在平方矩阵flag[i][j]为1的位置，在原矩阵flay[i][j]中是否都为1；若flag矩阵中所有的为1的地方，在flay中都为1，则具有传递性；否则反之；最后输出该平方矩阵。代码如下所示：intk;for(i=0;ia;i++){for(j=0;ja;j++){flag[i][j]=0;for(k=0;ka;k++)flag[i][j]=flag[i][j]+flay[i][k]*flay[k][j];}if(flag[i][j]==1)count_2++;}for(i=0;ia;i++){for(j=0;ja;j++){if(flag[i][j]==1&&flay[i][j]==1)count_3++;elseif(flag[i][j]==1&&flay[i][j]==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;ia;i++){for(k=0;ka;k++)coutflag[i][k];cout\bendl;}运行结果如下：以上便是对自反或反自反，对称或反对称，是否传递等性质的判断过程，代码及运行代码的结果。4.实验总结此题为验证性题目，验证性题目主要是通过其原理以及相关的概念来证明。通过此题对验证性题目的分析有很大的提高。(二)1.实验题目判断一个二元关系是否为等价关系，如果是，求其商集。2.实验原理要判断一个二元关系是否是等价关系，则要判断这个关系是否具有自反性，对称性和传递性；假如这三个条件都同时符合，则该二元关系具有等价关系。这里以为A={1，2，3，4,5,6,7}，R={1,4,1,7,4,1,4,7,7,1,7,4,2,5,5,2,3,6,6,3}UIa为例。自反性的判别与上题一样，都是判别flay[i][i]是否都等于1；若flay[i][i]全部等于1，则具有自反性；否则反之。对于对称性与上题也一样，就是判断所有的flay[i][j]与flay[j][i]是否全部相等；若全部相等，则具有对称性；否则反之。传递性的判断，则需要利用线性代数的方法求出R的关系矩阵的平方矩阵，只需验证所有的flag[i][j]（R的关系矩阵的平方矩阵）等于1的地方，在flay[i][j]（R的关系矩阵）等于1，则具有传递性；否则反之。3.实验步骤及实验记录（1）先输入一个整数，表示矩阵的阶数；接着输出初始空矩阵。然后一组一组的输入R在A上的关系，输入00时结束；接着输出关系矩阵，判别与输入的关系是否一致。代码如下所示：voidInput(){for(i=1;i=n;i++){for(j=1;j=n;j++)flay[i][j]=0;}for(i=1;i=n;i++){for(j=1;j=n;j++)coutflay[i][j];coutendl;}R();}voidR(){cout请输入两个位置有关系的数值,输入“00”结束R的输入：endl;cinab;if(a!=0&&b!=0){flay[a][b]=1;R();}}voidOutput(){for(i=1;i=n;i++){for(j=1;j=n;j++)coutflay[i][j];coutendl;}}代码运行结果如下所示：（2）在根据矩阵左上到右下flay[i][i]的值是否为1判断矩阵是否是自反或反自反，判断矩阵是否自反或反自反的代码如下：intcount=0;for(i=1;i=n;i++){for(j=1;j=n;j++){if(i==j){if(flay[i][j]==1)count_1++;elseif(flay[i][j]==0)count_2++;}}}if(count_1==n){cout自反性endl;syb_3=1;}elsecout反自反性endl;代码运行结果如下所示：（3）判断对称的或反对称只需要flay[i][j]是否与flay[j][i]相等；若全部相等，则为可对称；否则反之。代码如下：for(i=1;i=n;i++){for(j=1;j=n;j++){if(flay[i][j]==flay[j][i])count_1++;else{count_2=1;break;}}if(count_2==1){break;}}if(count_2==1){cout反称性endl;}else{cout对称性endl;syb_1=1;}代码运行结果如下所示：（4）而对于判别是否具有传递性，则相对前面两个性质来说比较复杂，关键是求出原矩阵flay的平方矩阵flag，这里通过线性代数的方法求出flay矩阵的平方矩阵flag，求平方矩阵的方法是：第一个矩阵flay[i][j]等于flay[i][j]乘以第二个矩阵的第j列之总和；j++完后再i++，以后便可求出平方矩阵。然后在比较在平方矩阵flag[i][j]为1的位置，在原矩阵flay[i][j]中是否都为1；若flag矩阵中所有的为1的地方，在flay中都为1，则具有传递性；否则反之；最后输出该平方矩阵。代码如下所示：intk;for(i=1;i=n;i++){for(j=1;j=n;j++){flag[i][j]=0;for(k=1;k=n;k++)flag[i][j]=flag[i][j]+flay[i][k]*flay[k][j];if(flag[i][j]!=0)count_2++;}}for(i=1;i=n;i++){for(j=1;j=n;j++){if(flag[i][j]!=0&&flay[i][j]==1){flag[i][j]=1;count_3++;}elseif(flag[i][j]!=0&&flay[i][j]==0){flag[i][j]=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++)coutflag[i][k];cout\bendl;}代码运行结果如下所示：(5)对于商集，只需判断哪个几个原变元之间同时具有自反，对称和传递关系即可。代码如下所示：cout其商集为：endl;inta[100];if(syb_1==1&&syb_2==1&&syb_3==1){for(i=1;i=n;i++){a[i]=i;}for(i=1;i=n;i++){if(a[i]!=0){cout{;for(j=1;j=n;j++){if(flay[i][j]!=0&&a[j]!=0){couta[j];a[j]=0;}}cout'\b'};}}}else{cout不是等价关系endl;cout不存在商集endl;}运行结果如下：4.实验总结通过此题不仅可以熟悉等价关系的概念和条件，还可以理解商集的含义以及求商集的方法。提高对问题的分析能力和答题能力。代数系统1.实验题目输入代数系统〈G，*〉的集合G和*运算的运算表，判断〈G，*〉是否是群。2.实验原理判断一个代数系统是否为群的三个条件为：该代数系统是可结合的半群，具有幺元的独异点，G上每个元素都有逆元。即G,*是代数系统，*为二元运算，如果*运算时可结合的，存在单位元e在G内，并且对G中任何元素X都有X-1在G内，则称为群。证明*运算可结合的原理是(X*Y)*Z=X*(Y*Z)即可。要证明死独异点，则要证el*X=x且X*er=X，则e就是幺元即可。而要证明有逆元，即证明yl*X=e(e为逆元)且X*yr=e（e为逆元）则y就是逆元即可。这就是证明群的原理。3.实验步骤及实验记录*eabceeabc本题以代数系统aaecb为例bbceaccbae(1)输入一个整数N，表示有N个变量；在逐个输入变元，然后在逐个输入两个变元关于*运算后相应的结果，最后输出该代数系统。代码如下：cout请输入变元的个数：;cinn;for(k=1;k=n;k++){cout请输入第k个变元:;cinflay[k];}for(i=1;i=n;i++)for(j=1;j=n;j++){cout请输入flay[i]与flay[j]做运算后的结果：;cina[i][j];}运行结果如下所示：（2）证明可结合性，其原理是在一个代数系统中(X*Y)*Z=X*(Y*Z)，此处是