当前位置:文档之家› 离散数学实验指导书及其答案

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

实验一命题逻辑公式化简【实验目的】加深对五个基本联结词(否定、合取、析取、条件、双条件)的理解、掌握利用基本等价公式化简公式的方法。

【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。

实验用例:用化简命题逻辑公式的方法设计一个5人表决开关电路,要求3人以上(含3人)同意则表决通过(表决开关亮)。

【实验原理和方法】(1)写出5人表决开关电路真值表,从真值表得出5人表决开关电路的主合取公式(或主析取公式),将公式化简成尽可能含五个基本联结词最少的等价公式。

(2)上面公式中的每一个联结词是一个开关元件,将它们定义成C语言中的函数。

(3)输入5人表决值(0或1),调用上面定义的函数,将5人表决开关电路真值表的等价公式写成一个函数表达式。

(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&&e || b&&c&&d || b&&c&&e || b&&d&&e || c&&d&&e)return 1;e lsereturn 0;}void main(){i nt a,b,c,d,e;p rintf("请输入第五个人的表决值(0或1,空格分开):");s canf("%d%d%d%d%d",&a,&b,&c,&d,&e);i f(vote(a,b,c,d,e))printf("很好,表决通过!\n");e lseprintf("遗憾,表决没有通过!\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语言算法:i nt A,B,C,D,E;f or(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语言算法:f or(i=0;i<m;i++)for(j=0;j<n;j++)if(a[i]==b[j]) c[k++]=a[i];(3)二个集合的并运算:把数组A中各个元素先保存在数组C中。

将数组B中的元素逐一与数组B中的元素进行比较,把不相同的元素添加到数组C中,数组C便是集合A和集合B的并。

C语言算法:for(i=0;i<m;i++)c[i]=a[i];f or(i=0;i<n;i++){for(j=0;j<m;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语言算法:f or(i=0;i<m;i++)c[i]=a[i];f or(i=0;i<n;i++)for(j=0;j<m;j++)if(b[i]==c[j]){for(k=j;k<m;k++)c[k]=c[k+1];/*移位*/m--;break;}(5)集合的补运算:将数组E中的元素逐一与数组A中的元素进行比较,把不相同的元素保存到数组C中,数组C便是集合A关于集合E的补集。

求补集是一种种特殊的集合差运算。

实验四 二元关系及其性质【实验目的】掌握二元关系在计算机上的表示方法,并掌握如果判定关系的性质。

【实验内容】 编程判断一个二元关系是否为等价关系,如果是,求其商集。

等价关系:集合A 上的二元关系R 同时具有自反性、对称性和传递性,则称R 是A 上的等价关系。

【实验原理和方法】(1)A 上的二元关系用一个n ×n 关系矩阵R=n n ij r ⨯)(表示,定义一个n ×n 数组r[n][n]表示n ×n 矩阵关系。

(2)若R 对角线上的元素都是1,则R 具有自反性。

C 语言算法:int i,flag=1;for(i=0;i<N && flag ;i++)if(r[i][i]!=1) flag=0; 如果flag=1, 则R 是自反关系(3)若R 是对称矩阵,则R 具有对称性。

对称矩阵的判断方法是:R r R r ji ij ∈∀∈∀有,。

C 语言算法:int i,j,flag=1;for(i=0;i<N && flag ;i++)for(j=i+1;j<N && flag;j++)if(r[i][j] &&r[j][i]!=1) flag=0; 如果flag=1, 则R 是对称关系(4)关系的传递性判断方法:对任意i ,j ,k ,若111===ik jk ij r r r 有且。

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(r[i][j] &&r[j][k] && r[i][k]!=1) flag=0; 如果flag=1, 则R 是传递关系(5)求商集的方法:商集是由等价类组成的集合。

已知R 是等价关系,下面的算法是把等价类分行打印出来。

C 语言算法:int i,j,flag=1;int a[N];for(i=0;i<N;i++)a[i]=i+1;/*i代表第i个元素*/for(i=0;i<N;i++){if(a[i]){printf("{ ");for(j=0;j<N;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)自反闭包:A I R R r =)(。

C 语言算法: 将关系矩阵的对角线上所有元素设为1。

initc(r);/*将关系矩阵的对角线上所有元素设为1*/for(i=0;i<N;i++) c[i][i]=1;(2)对称闭包:R R R s '= )(C 语言算法: 在关系矩阵的基础上,若1,1==ji ij r r 令。

initc(r);for(i=0;i<N;i++)for(j=0;j<N;j++) if(c[i][j]) c[j][i]=1;/*将关系矩阵的对角线上所有元素设为1*/(3)传递闭包:n R R R R t 2)(=,或用warshall 方法。

方法1:n R R R R t 2)(=,下面求得的关系矩阵T=n n ij b ⨯)(就是)(R t 。

int b[N][N];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++){b[i][j]=0;for(k=0;k<N;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;i<N;i++)for(j=0;j<N;j++)if(c[j][i])for(k=0;k<N;k++){c[j][k]=c[j][k]+c[i][k];if(c[j][k]) c[j][k]=1;}实验六 欧拉图判定和应用【实验目的】掌握判断欧拉图的方法。

相关主题