离散数学实验指导书及其答案

因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结实验一命题逻辑公式化简【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。实验用例：用化简命题逻辑公式的方法设计一个5人表决开关电路，要求3人以上（含3人）同意则表决通过（表决开关亮）。【实验原理和方法】（1）写出5人表决开关电路真值表，从真值表得出5人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。（2）上面公式中的每一个联结词是一个开关元件，将它们定义成C语言中的函数。（3）输入5人表决值（0或1），调用上面定义的函数，将5人表决开关电路真值表的等价公式写成一个函数表达式。（4）输出函数表达式的结果，如果是1，则表明表决通过，否则表决不通过。参考代码：#includestdio.hintvote(inta,intb,intc,intd,inte){//五人中任取三人的不同的取法有10种。if(a&&b&&c||a&&b&&d||a&&b&&e||a&&c&&d||a&&c&&e||a&&d&&e||b&&c&&d||b&&c&&e||b&&d&&e||c&&d&&e)return1;elsereturn0;}voidmain(){inta,b,c,d,e;printf(请输入第五个人的表决值（0或1，空格分开）：);scanf(%d%d%d%d%d,&a,&b,&c,&d,&e);if(vote(a,b,c,d,e))printf(很好，表决通过！\n);elseprintf(遗憾，表决没有通过！\n);}//注：联结词不定义成函数，否则太繁因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结实验二命题逻辑推理【实验目的】加深对命题逻辑推理方法的理解。【实验内容】用命题逻辑推理的方法解决逻辑推理问题。实验用例：根据下面的命题，试用逻辑推理方法确定谁是作案者，写出推理过程。（1）营业员A或B偷了手表；（2）若A作案，则作案不在营业时间；（3）若B提供的证据正确，则货柜末上锁；（4）若B提供的证据不正确，则作案发生在营业时间；（5）货柜上了锁。【实验原理和方法】（1）符号化上面的命题，将它们作为条件，营业员A偷了手表作为结论，得一个复合命题。（2）将复合命题中要用到的联结词定义成C语言中的函数，用变量表示相应的命题变元。将复合命题写成一个函数表达式。（3）函数表达式中的变量赋初值1。如果函数表达式的值为1，则结论有效，A偷了手表，否则是B偷了手表。用命题题变元表示：A:营业员A偷了手表B:营业员B偷了手表C:作案不在营业时间D:B提供的证据正确E:货柜末上锁则上面的命题符号化为(A||B)&&(!A||C)&&(!D||E)&&(D||!C)&&!E要求找到满足上面式子的变元A，B的指派便是结果。C语言算法：intA,B,C,D,E;for(A=0;A=1;A++)for(B=0;B=1;B++)for(C=0;C=1;C++)for(D=0;D=1;D++)for(E=0;E=1;E++)if((A||B)&&(!A||C)&&(!D||E)&&(D||!C)&&!E)printf(A=%d,B=%d\n,A,B);}/*实验结果是：A=0，B=1，即B偷了手表*/因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结实验三集合运算【实验目的】掌握用计算机求集合的交、并、差和补运算的方法。【实验内容】编程实现集合的交、并、差和补运算。【实验原理和方法】（1）用数组A，B，C，E表示集合。输入数组A，B，E（全集），输入数据时要求检查数据是否重复（集合中的数据要求不重复），要求集合A，B是集合E的子集。以下每一个运算都要求先将集合C置成空集。（2）二个集合的交运算：把数组A中元素逐一与数组B中的元素进行比较，将相同的元素放在数组C中，数组C便是集合A和集合B的交。C语言算法：for(i=0;im;i++)for(j=0;jn;j++)if(a[i]==b[j])c[k++]=a[i];（3）二个集合的并运算：把数组A中各个元素先保存在数组C中。将数组B中的元素逐一与数组B中的元素进行比较，把不相同的元素添加到数组C中，数组C便是集合A和集合B的并。C语言算法：for(i=0;im;i++)c[i]=a[i];for(i=0;in;i++){for(j=0;jm;j++)if(b[i]==c[j])break;if(j==m){c[m+k]=b[i];k++;}}（4）二个集合的差运算：把数组A中各个元素先保存在数组C中。将数组B中的元素逐一与数组B中的元素进行比较，把相同的元素从数组C中删除，数组C便是集合A和集合B的差A-B。C语言算法：for(i=0;im;i++)c[i]=a[i];for(i=0;in;i++)for(j=0;jm;j++)if(b[i]==c[j]){for(k=j;km;k++)c[k]=c[k+1];/*移位*/m--;因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结break;}（5）集合的补运算：将数组E中的元素逐一与数组A中的元素进行比较，把不相同的元素保存到数组C中，数组C便是集合A关于集合E的补集。求补集是一种种特殊的集合差运算。因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结实验四二元关系及其性质【实验目的】掌握二元关系在计算机上的表示方法，并掌握如果判定关系的性质。【实验内容】编程判断一个二元关系是否为等价关系，如果是，求其商集。等价关系：集合A上的二元关系R同时具有自反性、对称性和传递性，则称R是A上的等价关系。【实验原理和方法】（1）A上的二元关系用一个n×n关系矩阵R=nnijr)(表示，定义一个n×n数组r[n][n]表示n×n矩阵关系。（2）若R对角线上的元素都是1，则R具有自反性。C语言算法：inti,flag=1;for(i=0;iN&&flag;i++)if(r[i][i]!=1)flag=0;如果flag=1，则R是自反关系（3）若R是对称矩阵，则R具有对称性。对称矩阵的判断方法是：RrRrjiij有,。C语言算法：inti,j,flag=1;for(i=0;iN&&flag;i++)for(j=i+1;jN&&flag;j++)if(r[i][j]&&r[j][i]!=1)flag=0;如果flag=1，则R是对称关系（4）关系的传递性判断方法：对任意i，j，k，若111ikjkijrrr有且。C语言算法：inti,j,k,flag=1;for(i=0;iN&&flag;i++)for(j=0;jN&&flag;j++)for(k=0;kN&&flag;k++)if(r[i][j]&&r[j][k]&&r[i][k]!=1)flag=0;如果flag=1，则R是传递关系（5）求商集的方法：商集是由等价类组成的集合。已知R是等价关系，下面的算法是把等价类分行打印出来。C语言算法：inti,j,flag=1;inta[N];因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结for(i=0;iN;i++)a[i]=i+1;/*i代表第i个元素*/for(i=0;iN;i++){if(a[i]){printf({);for(j=0;jN;j++)if(r[i][j]&&a[j]!=0){printf(%d,a[j]);/*打印和第i个元素有关系的所有元素*/a[j]=0;}printf(}\n);}}因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结实验五关系闭包运算【实验目的】掌握求关系闭包的方法。【实验内容】编程求一个关系的闭包，要求传递闭包用warshall方法。【实验原理和方法】设N元关元系用r[N][N]表示，c[N][N]表示各个闭包，函数initc(r)表示将c[N][N]初始化为r[N][N]。（1）自反闭包：AIRRr)(。C语言算法：将关系矩阵的对角线上所有元素设为1。initc(r);/*将关系矩阵的对角线上所有元素设为1*/for(i=0;iN;i++)c[i][i]=1;（2）对称闭包：RRRs)(C语言算法：在关系矩阵的基础上，若1,1jiijrr令。initc(r);for(i=0;iN;i++)for(j=0;jN;j++)if(c[i][j])c[j][i]=1;/*将关系矩阵的对角线上所有元素设为1*/（3）传递闭包：nRRRRt2)(，或用warshall方法。方法1：nRRRRt2)(，下面求得的关系矩阵T=nnijb)(就是)(Rt。intb[N][N];initc(r);/*用c装好r*/for(m=1;mN;m++)/*得r的m次方,用c装好*/{for(i=0;iN;i++)for(j=0;jN;j++){b[i][j]=0;for(k=0;kN;k++)b[i][j]+=c[i][k]*r[k][j];if(b[i][j])b[i][j]=1;}initc(b);/*把r的m次方b赋给c保存*/因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结方法2：warshall方法initc(r);/*用c装好r*/for(i=0;iN;i++)for(j=0;jN;j++)if(c[j][i])for(k=0;kN;k++){c[j][k]=c[j][k]+c[i][k];if(c[j][k])c[j][k]=1;}因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结实验六欧拉图判定和应用【实验目的】掌握判断欧拉图的方法。【实验内容】判断一个图是不是，如果是，求出所有欧拉路【实验原理和方法】（1）用关系矩阵R=nnijr)(表示图。（2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。C语言算法：flag=1;for(i=1;i=n&&flag;i++){sum=0;for(j=1;j=n;j++)if(r[i][j])sum++;if(sum%2==0)flag=0;}如果flag该无向图是欧拉图（3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。C语言算法：flag=1;for(i=1;i=n&&flag;i++){sum1=0;sum2=0;for(j=1;j=n;j++)if(r[i][j])sum1++