离散数学实验报告

《离散数学实验报告》由会员分享，可在线阅读，更多相关《离散数学实验报告（30页珍藏版）》请在装配图网上搜索。

1、离散数学实验报告 题 目 专 业 学 号 姓 名 指导教师 提交日期 实验一 五种连结词的逻辑运算一.实验目的用C语言实现两个命题变元的合取、析取、蕴涵和等价表达式的计算。熟悉连接词逻辑运算规则，利用程序语言实现逻辑这几种逻辑运算。二.实验内容从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、蕴涵和等价四种运算的的真值。要求对输入内容进行分析，如果不符合0、1条件需要重新输入，程序有良好的输入输出界面。三. 实验过程1. 算法分析：编程语言为c语言合取/：p，q都为1的时候为1，其他为0 析取/：p，q都为0的时候为0，其他为1蕴含-：p为1，q为0时为0，其他为1 等价：p，q同真同假

2、流程图开始P为1或0P为1或0运算是否继续结束YYYNNN输入P值输入Q值输出结果2. 程序代码：#includeint main()int p,q,i,t; printf(*n); printf(* *n);printf( 欢迎进入逻辑运算软件n); printf(* *n);printf(*n);doprintf(请输入p的值(0或1);scanf(%d,&p);if(p!=0&p!=1)printf(输入有误);while(p!=0&p!=1); doprintf(请输入q的值(0或1);scanf(%d,&q); if(q!=0&q!=1)printf(输入有误);while(q!=0

3、&q!=1); doprintf(请选择要进行的操作n);printf(1:合取n2:析取n3:蕴含n4:等价n);scanf(%d,&i);switch(i)case 1:if(p&q) printf(合取运算：p/q=1n);else printf(合取运算：p/q=0n);break; case 2:if(p|q) printf(析取运算：p/q=1n);else printf(析取运算：p/q=0n);break; case 3:if(p&!q) printf(蕴含：p-q=0n);else printf(蕴含：p-q=1n); break;case 4:if(p&q)|(!p&!q)

4、 printf(等价运算：pq=1n);else printf(等价运算：pq=0n); break; printf(是否继续运算10n); scanf(%d,&t); while(t); return 0; 3.实验数据及结果分析；图1.初始界面图2.输入及选择进行的操作图3.循环操作图4.退出程序实验二 给任意命题公式输出其真值表一 、实验目的熟悉各命题公式，并会利用C语言编程求其真值。二 、实验内容在菜单上输入任给一命题公式，输出其真值表三. 实验过程1. 算法分析：算法逻辑如下：（1）任意设计一个真值判断表达式，并使其赋值计算（2）计算模拟器中所对应的一组真值指派下合式公式的真值。（3

5、）输出真值表中对应于模拟器所给出的一组真值指派及这组真值指派所对应的一行真值。（4）如果所输出的为真值，则页面提示“真命题”主范式：主析取范式：在含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单合取式为小项。由若干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的。主合取范式：在含有n个命题变元的简单析取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项。由若干个不同的大项组成的合取式称为主

6、合取范式;与A等价的主合取范式称为A的主合取范式。任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式,并且是惟一的。流程图开始输入式子计算变量数生成真值表输出真值表变量赋值运算式子输出结果归类主范式输出主范式结束循环是否结束YN2. 程序代码：#include stdio.h#include stdlib.h#include string.h#include conio.h#include math.h#define N 50 void panduan(int bN,int f);/赋值函数int tkh (char szN, char ccuN, int icuN, int h0

7、);/分级运算函数int fkh (char szN, char ccuN, int icuN, int h0);/主运算函数main() int i1,i2,d=1,icuN,kh=0,jg,j=0,h0;/icuN用于存放变量值,kh括号计数,jg存放结果 int bj=0,hqN,h=0,x=0,xqN;/hqN存放合取结果xqN存放析取结果 char szN,ccuN,sz0N,s;/szN存放式子,ccuN存放变量,sz0N也是用于存放式子 hq0=-1; xq0=-1; printf( *n);/标语 printf( n); printf( 欢迎进入菜单 n); printf( (

8、运算真值表，主范式，支持括号) n); printf( n); printf( 用!表示非 n); printf( 用&表示合取 n); printf( 用|表示析取 n); printf( 用表示蕴含 n); printf( 用表示等价 n); printf( n); printf( *nn); printf(请输入一个合法的命题公式:n);/输入式子 gets(sz);/读取式子 strcpy(sz0,sz);/复制式子 for(i1=0;i1=a & szi1=A & szi1=Z) for(i2=0;i2j;i2+) /判断并储存变量。 if(ccui2=szi1)/去除重复变量 d=

9、0; if(d=1) ccuj=szi1; j+; d=1; printf(nd该式子中的变量个数为：%dn,j);/输出变量个数 h0=j; printf(n输出真值表如下：n n); /输出真值表表头 for(i1=0;i1h0;i1+) printf( %c ,ccui1); printf( ); puts(sz); printf(n); for(i1=0;i1j;i1+) /先将所有的变量赋值为零。 icui1=0; for(i2=0;i2j;i2+)/输出真值表前项 printf( %d ,icui2); jg=tkh(sz,ccu,icu,h0); /用函数求结果 if(jg=0)

10、/结果为0，合取加1 hqh+=bj; else /否则，析取加1 xqx+=bj; printf( %dn,jg);/输出运算结果 strcpy(sz,sz0); for(i1=0;i1(int)pow(2,j)-1;i1+) +bj; panduan(icu,j-1); /赋值变量 jg=tkh(sz,ccu,icu,h0); if(jg=0)/结果为0，合取加1 hqh+=bj; else /否则，析取加1 xqx+=bj; strcpy(sz,sz0); /恢复被修改的数组。 for(i2=0;i2j;i2+) printf( %d ,icui2);/输出真值表前项 printf( %

11、dn,jg);/输出运算结果 if(hq0=-1)/不存在合取范式时 printf(n该命题公式不存在主合取范式。n); else printf(n该命题公式的主合取范式：nt); for(i1=0;i10)/判断并添加符号 printf(/); printf(M(%d),hqi1); /输出主合取范式 if(xq0=-1)/不存在析取范式时 printf(n该命题公式不存在主析取范式。n); else printf(nn该命题公式的主析取范式：nt); for(i1=0;i10)/判断并添加符号 printf(/); printf(m(%d),xqi1);/输出主析取范式 printf(n)

12、; printf(n欢迎下次再次使用！n );/结束 getch();void panduan(int bN,int f) / 二进制赋值。 int i; i=f; if(bf=0)/加1 bf=1; else/进位 bf=0; panduan(b,-i); int tkh (char szN,char ccuN,int icuN,int h0)/分级运算函数 int i,j,h,s,kh=0,wzN,a; char xs1N,ckhN; /xs1用来保存括号内的字符 ckh用来保存括号。 s=strlen(sz); for(i=0;is;i+) if(szi=( | szi=)/判断括号 w

13、zkh=i;/存储括号位置 ckhkh=szi;/存储括号类型 kh+; if(kh=0) return fkh(sz,ccu,icu,h0);/如果无括号，直接运行 else for(i=0;ikh;i+) if(ckhi=)/找到第一个） break; for(j=wzi-1+1,h=0;jwzi;j+,h+) /存储最内级括号中的内容 xs1h=szj; xs1h=0; a=fkh(xs1,ccu,icu,h0);/运行最内级括号的式子，得到结果 if(a=1)/判断并存储结果 szwzi-1=1; else szwzi-1=-2; for(j=wzi-1+1;js+wzi-1-wzi;

14、j+)/将括号后内容前移 szj=szj+wzi-wzi-1; szj=0; return tkh(sz,ccu,icu,h0);/循环执行 int fkh(char szN,char ccuN,int icuN,int h0)/主运算函数 int i,h=0,j=0,j1=0,j2=0,j3=0,j4=0,j5=0,i1,i2,p1=-1,p2=-1,s; char dtN; s=strlen(sz); if(s=1) if(sz0=-2)/判断是否是最后一项 return 0; else return 1; /1 就是sz0的值、 else for(i=0;is-j;i+) /先处理非 i

15、f(szi=!) for(i1=0;i1h0;i1+) if(szi+1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(p1=-1)/如果是数字，直接给P1 p1=szi+1; dtj+2=!p1;/非运算 szi=j+2; j+; p1=0; for(i1=i+1;i1s-j;i1+) szi1=szi1+1;/将后续式子前移一项 p1=-1; j1=j; for(i=0;is-j1-2*j2;i+) / 处理与 if(szi=&) for(i1=0;i1h0;i1+) if(szi-1=ccui1)/将

16、变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2; if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0; if(p1=-1) /如果是数字，直接给P1 p1=(int)(szi-1); if(p2=-1)/如果是数字，直接给P2 p2=(i

17、nt)(szi+1); dtj+2=p1 & p2;/与运算 szi-1=j+2; j+; j2+; p1=-1; p2=-1; for(i1=i;i1s-j1-2*j2;i1+)/将后续式子前移两项 szi1=szi1+2; i=i-1; for(i=0;is-j1-2*j2-2*j3;i+) / 处理或。 if(szi=|) for(i1=0;i1h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2j+2;i2+) if(szi-1=i2) /如果为前计算结果，

18、将结果赋值并给P1 p1=dti2; if(szi+1=i2)/如果为前计算结果，将结果赋值并给P2 p2=dti2; if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0; if(p1=-1)/如果是数字，直接给P1 p1=szi-1; if(p2=-1)/如果是数字，直接给P2 p2=szi+1; dtj+2=p1 | p2;/或运算 szi-1=j+2; j+; j3+; p1=-1; p2=-1; for(i1=i;i1s-j1-2*j2-2*j3;i1+)/将后续式子前移两项 szi1=szi

19、1+2; i-; for(i=0;is-j1-2*j2-2*j3-2*j4;i+) / 处理蕴含。 if(szi=) for(i1=0;i1h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1 p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2;if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-

20、2)/如果是前运算结果的0，则P2等于0 p2=0;if(p1=-1)/如果是数字，直接给P1 p1=szi-1;if(p2=-1)/如果是数字，直接给P2 p2=szi+1;dtj+2=!p1 | p2;/蕴含运算szi-1=j+2;j+;j4+;p1=-1;p2=-1; for(i1=i;i1s-j1-2*j2-2*j3-2*j4;i1+)/将后续式子前移两项 szi1=szi1+2;i-; for(i=0;is-j1-2*j2-2*j3-2*j4-2*j5;i+) / 处理等值。 if(szi=) for(i1=0;i1h0;i1+) if(szi-1=ccui1)/将变量赋值并给P1

21、p1=icui1; if(szi+1=ccui1)/将变量赋值并给P2 p2=icui1; for(i2=2;i2j+2;i2+) if(szi-1=i2) /如果为前计算结果，将结果赋值并给P1 p1=dti2; if(szi+1=i2) /如果为前计算结果，将结果赋值并给P2 p2=dti2; if(szi-1=-2)/如果是前运算结果的0，则P1等于0 p1=0; if(szi+1=-2)/如果是前运算结果的0，则P2等于0 p2=0; if(p1=-1)/如果是数字，直接给P1 p1=szi-1; if(p2=-1)/如果是数字，直接给P2 p2=szi+1; dtj+2=(!p1 |

22、 p2)&(!p2 | p1);/等值运算 szi-1=j+2; j+; j5+; p1=-1; p2=-1; for(i1=i;i1s-j1-2*j2-2*j3-2*j4-2*j5;i1+)/将后续式子前移两项 szi1=szi1+2; i-; return dtj+1;/返回结果 3. 实验数据及结果分析图1.初始界面图2.根据需要选择写出公式实验三 1、关系的闭包运算一 、实验目的熟悉关系的闭包运算，利用C语言编程实现五种关系闭包运算算法。二 、实验内容利用矩阵求解有限集上给定关系的自反、对称和传递闭包。三. 实验过程1. 算法分析：在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关

23、系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）；传递闭包则有两种算法（二选一即可）：算法1：直接根据计算，过程略。算法2：Warshall算法(1962)设R的关系矩阵为M(1)令矩阵A=M(2)置i=1(3)对所有的j，若Aj，i=1，则对于 k=1，2，n，令Aj，k=Aj，k+Ai，k 注：此处为逻辑加，可以使用运算符|(4) i=i+l(5)若in，则转到(3)，否则结束开始声明各子函数输入关系矩阵输入z z=1；调用自反闭包函数z=2，调用对称闭包函数z=3调用传递闭包函数结束 流程图2.程序代码：#include void output(

24、int s100); void zifan(int s2100); void duichen(int s2100); void chuandi2(int s2100); void chuandi1(int s2100); void aa(); int s100100,z;int d,n ,i,j;int main()aa();return 0;void aa() printf(请输入矩阵的行数M10n ); scanf(%d,&n); printf(请输入矩阵的列数N10n ); scanf(%d,&d); printf(请输入关系矩阵n); for(i=0;in;i+) printf(n);

25、printf(请输入矩阵的第%d行元素,i);for(j=0;jd;j+)scanf(%d,&sij); printf(输入对应序号选择算法n1:自反闭包n2:传递闭包1n3:传递闭包(Warhall算法)2n4:对称闭包n);scanf(%d,&z);switch(z) case 1:zifan(s); break; case 2:chuandi1(s);break; case 3:chuandi2(s);break; case 4:duichen(s); break;void output(int s100)printf(所求关系矩阵为n); for(i=0;in;i+) for(j=0;

26、jd;j+) printf(%d,sij); printf(n); void zifan(int s2100) for(i=0;in;i+) s2ii=1;output(s2);aa();void duichen(int s2100)int s1100100; for(i=0;in;i+) for(j=0;jd;j+) s1ji=s2ij; for(i=0;in;i+) for(j=0;j1) s2ij=1; output(s2);aa();void chuandi1(int s2100)int m100100,a100100,k,h; int t100100; for(i=0;in;i+)

27、for(j=0;jd;j+) aij=0; tij=s2ij; mij=s2ij;for(h=0;hn;h+) for(i=0;in;i+) for(j=0;jd;j+) if(mij=1) for(k=0;kn;k+)if(s2jk=1) aik=1; for(i=0;in;i+) for(j=0;j1) tij=1; output(t);aa();void chuandi2(int s2100)int k; for(i=0;in;i+) for(j=0;jn;j+) if(s2ji=1) for(k=0;kn;k+)s2jk+=s2ik; for(i=0;in;i+) for(j=0;j1

28、) s2ij=1;output(s2);aa();3.实验数据及结果分析图1.初始界面图2.根据需要选择各闭包实验三 2、任意两个集合的交集、并集和差集一 .实验目的集合论是一切数学的基础，集合的运算规则是集合论中的重要内容。通过该组实验，目的是让我们更加深刻地理解集合的概念和性质，并掌握集合的运算规则等。二 .实验内容通过对集合的掌握，利用C语言编程计算任意两个集合的交集、并集和差集运算。3. 实验过程1. 算法分析1.在求交集时，利用if找出两个集合的相同元素，并输出。2.在求并集时，将两个集合的元素属于其一或另一个。3.在求差集时，将一个集合减去交集，然后将其输出。2. 程序代码：#in

29、clude stdio.h #define M 5#define N 5void main() int i,j,k=-1,n=0; int jj=-1,bb=-1; int aM,bN,cM*N,dM+N,xM*N,yM+N; printf( 欢迎进入n); printf( 请输入一个集合n); for(i=0;iM;i+) scanf(%d,&ai); printf( 请输入另一个集合n); for(i=0;iM;i+) scanf(%d,&bi); for(i=0;iM;i+) for(j=0;jN;j+) if(ai=bj) k+; ck=ai; printf(n求交集:n); for(

30、i=0;i=k;i+) n=0; for(j=i+1;j=k;j+) if(ci!=cj) n+; if(n=k-i) jj+; xjj=ci; printf(%d ,ci); printf(n求并集 :n); for(i=0;iM;i+) di=ai; for(j=0;jN;j+) dM+j=bj; for(i=0;i=M+N-1;i+) n=0; for(j=i+1;j=M+N-1;j+) if(di!=dj) n+; if(n=M+N-1-i) bb+; ybb=di; printf(%d ,di); printf(n求差集:n); for(i=0;i=bb;i+) n=0; for(j

31、=0;j=jj;j+) if(yi!=xj) n+; if(n-1=jj) printf(%d ,yi); 3. 实验数据及结果分析图1.菜单界面图2.交集、并集、差集的实现实验三 3、全域关系和恒等关系一实验目的1.通过上机编写程序，可以进一步加深我们对关系中集合A上的恒等关系，以及从集合A到集合B上的恒等关系的理解。2.学会用程序去解决离散数学中的一些问题。3.增强我们编写程序的能力，提高了我们的逻辑思维能力。4.让我们更加熟悉的去使用word文档去整理这次的实验。二实验内容三实验过程1.算法分析用C语言实现，求集合A上的恒等关系以及从集合A到集合B上的全域关系。对于A上的恒等关系，只需让

32、二元关系的第一个元素和第二个元素相等即可；对于从A到B上的全域关系，即求A和B的笛卡尔积。让A中的第一个元素对应B中的每一个元素，让A中的第二个元素对应B中的每一个元素，依次进行下去，即可得到从A到B上的全域关系。流程图2. 程序代码：#includevoid main()int a20,b20,i,j,n,m,x,y;printf(请输入两个集合的元素的个数：n);scanf(%d%d,&n,&m);printf(请输入第一个集合的元素：n);for(i=1;i=n;i+) scanf(%d,&ai);printf(请输入第二个集合的元素：n);for(j=1;j=m;j+) scanf(%

33、d,&bj);printf(A集合的元素为：n);for(x=1;x=n;x+)printf(%d,ax); printf(n);printf(A集合的恒等关系为：n);for(x=1;x=n;x+) printf(,ax,ax); printf(n); printf(A到B的全域关系为：n);for(x=1;x=n;x+)for(y=1;y=m;y+)printf(,ax,by); printf(n); printf(B集合的元素为：n); for(y=1;y=m;y+) printf(%d,by); printf(n);printf(B集合的恒等关系为：n); for(y=1;y=n;y+

34、) printf(,by,by); printf(n); printf(B到A的全域关系为：n);for(y=1;y=m;y+)for(x=1;x=n;x+) printf(,by,ax); printf(n);四实验数据及结果分析图1.菜单界面图2.全域关系和恒等关系结束语离散数学课程在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言编译技术、人工智能、算法设计与分析等必不可少的先行课程。不但作为计算机科学与技术及相关专业的理论基础及核心主干课，对后续课程提供必需的理论支持。更重要的是旨在“通过加强数学推理，组合分析，离散结构，算法构思与设计，构建流程图等方面专门与反复的研究、训练及应用，培养提高学生的数学思维能力和对实际问题的求解能力。”通过对离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。- 29 -