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

1、实验一命题逻辑公式化简【实验目的】加深对五个基本联结词(否定、合取、析取、条件、双条件)的理解、掌 握利用基本等价公式化简公式的方法。【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。实验用例：用化简命题逻辑公式的方法设计一个5人表决开关电路，要求3人以上(含3人)同意则表决通过(表决开关亮)。【实验原理和方法】(1)写出5人表决开关电路真值表，从真值表得出5人表决开关电路的主合取公式(或主析取公式)，将公式化简成尽可能含五个基本联结词最少的等价公式。(2)上面公式中的每一个联结词是一个开关元件，将它们定义成C语言中的函数。(3)输入5人表决值(0或1),调用上面定义的函数，将5人表决

2、开关电路真值表的等价公式写成一个函数表达式。(4)输出函数表达式的结果，如果是 1,则表明表决通过，否则表决不通过。参考代码：#include<stdio.h>int vote(int a,int b,int c,int d,int e)/五人中任取三人的不同的取法有10种。i f( a&&b&&c | a&&b&&d | a&&b&&e | a&&c&&d | a&&c&&e | a&&d&&

3、;e | b&&c&&d| b&&c&&e | b&&d&&e | c&&d&&e)return 1;elsereturn 0;void main()i nt a,b,c,d,e;printf("请输入第五个人的表决值(0或1,空格分开)：");scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);i f(vote(a,b,c,d,e)printf(" 很好，表决

4、通过！ n");elseprintf(" 遗憾，表决没有通过！n");/注：联结词不定义成函数，否则太繁实验二命题逻辑推理【实验目的】加深对命题逻辑推理方法的理解。【实验内容】用命题逻辑推理的方法解决逻辑推理问题。实验用例：根据下面的命题，试用逻辑推理方法确定谁是作案者，写出推理过程。(1)营业员A或B偷了手表；(2)若A作案，则作案不在营业时间；(3)若B提供的证据正确，则货柜末上锁；(4)若B提供的证据不正确，则作案发生在营业时间；(5)货柜上了锁。【实验原理和方法】(1)符号化上面的命题，将它们作为条件，营业员A偷了手表作为结论，得一个复合命题。(2)将复合

5、命题中要用到的联结词定义成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语言算法：i nt A,B,C,D,E;f or(A=0;A<=

6、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=%dn",A,B);/*实验结果是：A=0, B=1,即B偷了手表*/实验三集合运算【实验目的】掌握用计算机求集合的交、并、差和补运算的方法。【实验内容】编程实现集合的交、并、差和补运算。【实验原理和方法】(1)用数组A, B, C,

7、E表示集合。输入数组A, B, E (全集)，输入数据时要求检查数据是否重复(集合中的数据要求不重复)，要求集合A, B是集合E的子集。以下每一个运算都要求先将集合C置成空集。(2)二个集合的交运算：把数组A中元素逐一与数组B中的元素进行比较，将相同的元素放在数组 C中，数组C便是集合A和集合B的交。C语言算法：f or(i=0;i<m;i+)for(j=0;j<n;j+)if(ai=bj) ck+=ai;(3)二个集合的并运算：把数组 A中各个元素先保存在数组 C中。将数组B中的元素 逐一与数组B中的元素进行比较， 把不相同的元素添加到数组 C中，数组C便是集合A和集 合B的并。

8、C语言算法：for(i=0;i<m;i+)ci=ai;f or(i=0;i<n;i+)for(j=0;j<m;j+) if(bi=cj) break;if(j=m) cm+k=bi;k+;(4)二个集合的差运算：把数组 A中各个元素先保存在数组 C中。将数组B中的元素 逐一与数组B中的元素进行比较， 把相同的元素从数组 C中删除，数组C便是集合A和集合 B的差A-B。C语言算法：f or(i=0;i<m;i+) ci=ai;f or(i=0;i<n;i+)for(j=0;j<m;j+) if(bi=cj) for(k=j;k<m;k+)移位*/ck=c

9、k+1;/*m-;break;)(5)集合的补运算：将数组E中的元素逐一与数组 A中的元素进行比较，把不相同的元素保存到数组 C中，数组C便是集合A关于集合E的补集。求补集是一种种特殊的集合差运算。实验四二元关系及其性质【实验目的】掌握二元关系在计算机上的表示方法，并掌握如果判定关系的性质。【实验内容】编程判断一个二元关系是否为等价关系，如果是，求其商集。等价关系：集合A上的二元关系R同时具有自反性、对称性和传递性，则称R是A上的 等价关系。【实验原理和方法】(1) A上的二元关系用一个 nXn关系矩阵R=(ij )n n表示，定义一个nx n数组rnn 表示nx n矩阵关系。(2)若R对角线

10、上的元素都是1,则R具有自反性。C语言算法：int i,flag=1;for(i=0;i<N && flag ;i+)if(rii!=1) flag=0;如果flag=1 ,则R是自反关系(3)若R是对称矩阵，则 R具有对称性。对称矩阵的判断方法是：% R,有 rjiR。C语言算法：int i,j,flag=1;for(i=0;i<N && flag ;i+)for(j=i+1;j<N && flag;j+)if(rij &&rji!=1) flag=0;如果flag=1 ,则R是对称关系(4)关系的传递性判断方

11、法：对任意 i , j , k,若"1且限1有限1。C语言算法：int i,j,k,flag=1;for(i=0;i<N && flag;i+)for(j=0;j<N && flag;j+)for(k=0;k<N && flag;k+)if(rij &&rjk && rik!=1) flag=0;如果flag=1 ,则R是传递关系(5)求商集的方法：商集是由等价类组成的集合。已知R是等价关系，下面的算法是把等价类分行打印出来。C语言算法：int i,j,flag=1;int aN;for

12、(i=0;i<N;i+)ai=i+1;/*i 代表第i个元素*/for(i=0;i<N;i+)(if(ai)(printf("");for(j=0;j<N;j+)if(rij && aj!=0)*/printf("%d ",aj);/* 打印和第i个元素有关系的所有元素 aj=0;printf("n");实验五关系闭包运算【实验目的】掌握求关系闭包的方法。【实验内容】编程求一个关系的闭包，要求传递闭包用warshall方法。【实验原理和方法】设N元关元系用rNN表示，cNN表示各个闭包，函数 init

13、c(r) 表示将cNN 初始化为rNN。(1)自反闭包：r(R) R I a°C语言算法：将关系矩阵的对角线上所有元素设为1。initc(r);/*将关系矩阵的对角线上所有元素设为1*/for(i=0;i<N;i+)cii=1;(2)对称闭包：s(R) R RC语言算法：在关系矩阵的基础上，若rj1,令冲 1。initc(r);for(i=0;i<N;i+)for(j=0;j<N;j+)if(cij)cji=1;/* 将关系矩阵的对角线上所有元素设为1*/(3)传递闭包：t(R) RR2Rn ,或用warshall方法。方法1： t(R) R R2Rn ,下面求得的

14、关系矩阵 T=(bj)n n就是t(R)。int bNN;initc(r);/* 用 c 装好 r*/for(m=1;m<N;m+) /* 得 r 的 m次方，用 c 装好*/ for(i=0;i<N;i+)for(j=0;j<N;j+) bij=0;for(k=0;k<N;k+)bij+=cik*rkj;if(bij) bij=1; initc(b);/* 把r的m次方b赋名c c保存*/方法2： warshall 方法initc(r);/* 用 c 装女f r*/for(i=0;i<N;i+)for(j=0;j<N;j+)if(cji)for(k=0;k

15、<N;k+) cjk=cjk+cik;if(cjk) cjk=1;实验六欧拉图判定和应用【实验目的】掌握判断欧拉图的方法。【实验内容】判断一个图是不是，如果是，求出所有欧拉路【实验原理和方法】(1)用关系矩阵R=(rj)n n表示图。(2)对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。C语言算法：flag=1;for(i=1;i<=n && flag;i+)(sum=0;for(j=1；j<=n；j+)if(rij) sum+;if(sum%2=0) flag=0;)如果flag 该无向图是欧拉图(3)对有向图而言，若所有结点的入度等于出度，则该图为欧

16、拉图。C语言算法：flag=1;for(i=1;i<=n && flag;i+)(sum1=0;sum2=0;for(j=1;j<=n;j+)if(rij) sum1+;for(j=1;j<=n;j+)if(rji) sum2+;if(sum1%2=0 | sum2%2=0) flag=0;)如果flag 该有向图是欧拉图(4)求出欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有 欧拉路。C语言算法：int count=0,cur=0,rNN; / rNN为图的邻接矩阵，cur 为当前结点编号，count 为欧拉路的数量。int sequen

17、ceM;/ sequence保留访问点的序列，M为图的边数输入图信息；void try1(int k) /k表示边的序号(int i,pre=cur; /j保留前一个点的位置,pre为前一结点的编号for (i=0;i<N;i+)if (rcuri) / 当前第cur点到第i点连通(/删除当前点与第i点的边，记下第k次到达点i ,把第i个点设为当前点rcuri=0;cur=sequencek=i;if (k<M) try1(k+1); /试下一个点else prt1();/经过了所有边，打印一个解/上面条件不满足，说明当前点的出度为0,回溯，试下一位置rprei=1;cur=pre

18、;实验七最优二叉树的应用【实验目的】掌握求最优二叉树的方法。【实验内容】最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率，求各通信符号对应的前缀码。【实验原理和方法】(1)用一维数组fN存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信 符号的前缀码。(2)用链表保存最优二叉树，输出前缀码时可用树的遍历方法。#include <stdio.h>#include <stdlib.h>#define N 13struct tree float num;struct tree *Lnode;struct tree *Rnode;* fpN;/保存结点char

19、 s2*N;/放前缀码void inite_node(float f,int n)生成叶子结点int i;struct tree *pt;for(i=0;i<n;i+)pt=(struct tree *)malloc(sizeof(struct tree);/生成叶子结点pt->num=fi;pt->Lnode=NULL;pt->Rnode=NULL;fpi=pt;void sort(struct tree * array,int n)将第N-n个点插入到已排好序的序列中。int i;struct tree *temp;for(i=N-n;i<N-1;i+)if(

20、arrayi->num>arrayi+1->num)temp=arrayi+1;arrayi+1=arrayi; arrayi=temp;)struct tree * construct_tree(float f,int n)/建立树(int i;struct tree *pt; for(i=1;i<N;i+) (pt=(struct tree *)malloc(sizeof(struct tree);/生成非叶子结点pt->num=fpi-1->num+fpi->num;pt->Lnode=fpi-1;pt->Rnode=fpi; fpi

21、=pt;/w1+w2 sort(fp,N-i);) return fpN-1;)void preorder(struct tree *p,int k,char c) (int j; if(p!=NULL) (if(c=T) sk='0'else sk='1'if(p->Lnode=NULL) /P指向叶子printf("%.2f: ",p->num); for(j=0;j<=k;j+) printf("%c",sj);putchar('n'); ) preorder(p->Lnode

22、,k+1,T);preorder(p->Rnode,k+1,'r');void main()float fN=2,3,5,7,11,13,17,19,23,29,31,37,41);struct tree *head;inite_node(f,N); / 初始化结点head=construct_tree(f,N);/生成最优树s0=0;preorder(head,0,T);遍历树)实验八群的判定【实验目的】掌握群的判定方法。【实验内容】输入代数系统(A,*)的集合A和*运算的运算表，判断(A, *)是否是群。【实验原理和方法】(1)用一维数组an存贮集合Ao(2)用二维数组opnn存贮运算表。(3)根据群的定义，代数系统(A, *)若为群