《离散数学》
实验报告
题目
专业
学号
姓名
指导教师
提交日期
实验一五种连结词的逻辑运算
一.实验目的
用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.程序代码：
#include
intmain()
{
intp,q,i,t;
printf("\n");
printf("\n");
printf("欢迎进入逻辑运算软件\n");
printf("\n");
printf("\n");
do{
printf("请输入p的值(0或1)");
scanf("%d",&p);
if(p!=0&&p!=1)
printf("输入有误");
}while(p!=0&&p!=1);
do{
printf("请输入q的值(0或1)");
scanf("%d",&q);
if(q!=0&&q!=1)
printf("输入有误");
}while(q!=0&&q!=1);
do{
printf("请选择要进行的操作\n");
printf("1:合取\n2:析取\n3:蕴含\n4:等价\n");
scanf("%d",&i);
switch(i){
case1:{
if(p&&q)printf("合取运算：p/\q=1\n");
elseprintf("合取运算：p/\q=0\n");
break;
}
case2:{
if(p||q)printf("析取运算：p\/q=1\n");
elseprintf("析取运算：p\/q=0\n");
break;
}
case3:{
if(p&&!q)printf("蕴含：p->q=0\n");
elseprintf("蕴含：p->q=1\n");
break;}
case4:{
if((p&&q)||(!p&&!q))printf("等价运算：p<->q=1\n");
elseprintf("等价运算：p<->q=0\n");
break;}
}printf("是否继续运算1\\0\n");
scanf("%d",&t);
}while(t);
return0;
}
3.实验数据及结果分析；
图1.初始界面
图2.输入及选择进行的操作
图3.循环操作
图4.退出程序
实验二给任意命题公式输出其真值表
一、实验目的
熟悉各命题公式，并会利用C语言编程求其真值。
二、实验内容
在菜单上输入任给一命题公式，输出其真值表
三.实验过程
1.算法分析：
算法逻辑如下：
（1）任意设计一个真值判断表达式，并使其赋值计算
（2）计算模拟器中所对应的一组真值指派下合式公式的真值。
（3）输出真值表中对应于模拟器所给出的一组真值指派及这组真值指派所对应的一行真值。
（4）如果所输出的为真值，则页面提示“真命题”
主范式：
主析取范式在含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单合取式为小项由若干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的主析取范式任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的主合取范式在含有n个命题变元的简单析取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项由若干个不同的大项组成的合取式称为主合取范式;与A等价的主合取范式称为A的主合取范式任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式,并且是惟一的
程序代码：
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"conio.h"
#include"math.h"
#defineN50
voidpanduan(intb[N],intf);//赋值函数
inttkh(charsz[N],charccu[N],inticu[N],inth0);//分级运算函数
intfkh(charsz[N],charccu[N],inticu[N],inth0);//主运算函数
main()
{
inti1,i2,d=1,icu[N],kh=0,jg,j=0,h0;//icu[N]用于存放变量值,kh括号计数,jg存放结果
intbj=0,hq[N],h=0,x=0,xq[N];//hq[N]存放合取结果xq[N]存放析取结果
charsz[N],ccu[N],sz0[N],s;//sz[N]存放式子,ccu[N]存放变量,sz0[N]也是用于存放式子
hq[0]=-1;
xq[0]=-1;
printf("\n");//标语
printf("\n");
printf("欢迎进入菜单\n");
printf("(运算真值表，主范式，支持括号)\n");
printf("\n");
printf("用!表示非\n");
printf("用&表示合取\n");
printf("用|表示析取\n");
printf("用^表示蕴含\n");
printf("用~表示等价\n");
printf("\n");
printf("\n\n");
printf("请输入一个合法的命题公式:\n");//输入式子
gets(sz);//读取式子
strcpy(sz0,sz);//复制式子
for(i1=0;i1
{
if(sz[i1]=='')''||sz[i1]==''('')//存储括号数量
kh++;
if(sz[i1]>=''a''&&sz[i1]<=''z''||sz[i1]>=''A''&&sz[i1]<=''Z'')
{
for(i2=0;i2
if(ccu[i2]==sz[i1])//去除重复变量
d=0;
if(d==1)
{
ccu[j]=sz[i1];
j++;
}
d=1;
}
}
printf("\nd该式子中的变量个数为：%d\n",j);//输出变量个数
h0=j;
printf("\n输出真值表如下：\n\n");//输出真值表表头
for(i1=0;i1
printf("%c",ccu[i1]);
printf("");
puts(sz);
printf("\n");
for(i1=0;i1
icu[i1]=0;
for(i2=0;i2
printf("%d",icu[i2]);
jg=tkh(sz,ccu,icu,h0);//用函数求结果
if(jg==0)//结果为0，合取加1
hq[h++]=bj;
else//否则，析取加1
xq[x++]=bj;
printf("%d\n",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
hq[h++]=bj;
else//否则，析取加1
xq[x++]=bj;
strcpy(sz,sz0);//恢复被修改的数组。
for(i2=0;i2
printf("%d",icu[i2]);//输出真值表前项
printf("%d\n",jg);//输出运算结果
}
if(hq[0]==-1)//不存在合取范式时
printf("\n该命题公式不存在主合取范式。\n");
else
{
printf("\n该命题公式的主合取范式：\n\t");
for(i1=0;i1
{
if(i1>0)//判断并添加符号
printf("\\/");
printf("M(%d)",hq[i1]);//输出主合取范式
}
}
if(xq[0]==-1)//不存在析取范式时
printf("\n该命题公式不存在主析取范式。\n");
else
{
printf("\n\n该命题公式的主析取范式：\n\t");
for(i1=0;i1
{
if(i1>0)//判断并添加符号
printf("/\\");
printf("m(%d)",xq[i1]);//输出主析取范式
}
}
printf("\n");
printf("\n欢迎下次再次使用！\n");//结束
getch();
}
voidpanduan(intb[N],intf)//二进制赋值。
{
inti;
i=f;
if(b[f]==0)//加1
b[f]=1;
else//进位
{
b[f]=0;
panduan(b,--i);
}
}
inttkh(charsz[N],charccu[N],inticu[N],inth0)//分级运算函数
{
inti,j,h,s,kh=0,wz[N],a;
charxs1[N],ckh[N];//xs1用来保存括号内的字符ckh用来保存括号。
s=strlen(sz);
for(i=0;i
if(sz[i]==''(''||sz[i]=='')'')//判断括号
{
wz[kh]=i;//存储括号位置
ckh[kh]=sz[i];//存储括号类型
kh++;
}
if(kh==0)
returnfkh(sz,ccu,icu,h0);//如果无括号，直接运行
else
{
for(i=0;i
if(ckh[i]=='')'')//找到第一个）
break;
for(j=wz[i-1]+1,h=0;j
xs1[h]=sz[j];
xs1[h]=''\0'';
a=fkh(xs1,ccu,icu,h0);//运行最内级括号的式子，得到结果
if(a==1)//判断并存储结果
sz[wz[i-1]]=1;
else
sz[wz[i-1]]=-2;
for(j=wz[i-1]+1;j
sz[j]=sz[j+wz[i]-wz[i-1]];
sz[j]=''\0'';
returntkh(sz,ccu,icu,h0);//循环执行
}
}
intfkh(charsz[N],charccu[N],inticu[N],inth0)//主运算函数
{
inti,h=0,j=0,j1=0,j2=0,j3=0,j4=0,j5=0,i1,i2,p1=-1,p2=-1,s;
chardt[N];
s=strlen(sz);
if(s==1)
if(sz[0]==-2)//判断是否是最后一项
return0;
else
return1;//1就是sz[0]的值、
else
{
for(i=0;i
if(sz[i]==''!'')
{
for(i1=0;i1
if(sz[i+1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(p1==-1)//如果是数字，直接给P1
p1=sz[i+1];
dt[j+2]=!p1;//非运算
sz[i]=j+2;
j++;
p1=0;
for(i1=i+1;i1
sz[i1]=sz[i1+1];//将后续式子前移一项
}
p1=-1;
j1=j;
for(i=0;i
if(sz[i]==''&'')
{
for(i1=0;i1
{
if(sz[i-1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==ccu[i1])//将变量赋值并给P2
p2=icu[i1];
}
for(i2=2;i2
{
if(sz[i-1]==i2)//如果为前计算结果，将结果赋值并给P1
p1=dt[i2];
if(sz[i+1]==i2)//如果为前计算结果，将结果赋值并给P2
p2=dt[i2];
}
if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(sz[i+1]==-2)//如果是前运算结果的0，则P2等于0
p2=0;
if(p1==-1)//如果是数字，直接给P1
p1=(int)(sz[i-1]);
if(p2==-1)//如果是数字，直接给P2
p2=(int)(sz[i+1]);
dt[j+2]=p1&&p2;//与运算
sz[i-1]=j+2;
j++;
j2++;
p1=-1;
p2=-1;
for(i1=i;i1
sz[i1]=sz[i1+2];
i=i-1;
}
for(i=0;i
if(sz[i]==''|'')
{
for(i1=0;i1
{
if(sz[i-1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==ccu[i1])//将变量赋值并给P2
p2=icu[i1];
}
for(i2=2;i2
{
if(sz[i-1]==i2)//如果为前计算结果，将结果赋值并给P1
p1=dt[i2];
if(sz[i+1]==i2)//如果为前计算结果，将结果赋值并给P2
p2=dt[i2];
}
if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(sz[i+1]==-2)//如果是前运算结果的0，则P2等于0
p2=0;
if(p1==-1)//如果是数字，直接给P1
p1=sz[i-1];
if(p2==-1)//如果是数字，直接给P2
p2=sz[i+1];
dt[j+2]=p1||p2;//或运算
sz[i-1]=j+2;
j++;
j3++;
p1=-1;
p2=-1;
for(i1=i;i1
sz[i1]=sz[i1+2];
i--;
}
for(i=0;i
if(sz[i]==''^'')
{
for(i1=0;i1
{
if(sz[i-1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==ccu[i1])//将变量赋值并给P2
p2=icu[i1];
}
for(i2=2;i2
{
if(sz[i-1]==i2)//如果为前计算结果，将结果赋值并给P1
p1=dt[i2];
if(sz[i+1]==i2)//如果为前计算结果，将结果赋值并给P2
p2=dt[i2];
}
if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(sz[i+1]==-2)//如果是前运算结果的0，则P2等于0
p2=0;
if(p1==-1)//如果是数字，直接给P1
p1=sz[i-1];
if(p2==-1)//如果是数字，直接给P2
p2=sz[i+1];
dt[j+2]=!p1||p2;//蕴含运算
sz[i-1]=j+2;
j++;
j4++;
p1=-1;
p2=-1;
for(i1=i;i1
sz[i1]=sz[i1+2];
i--;
}
for(i=0;i
if(sz[i]==''~'')
{
for(i1=0;i1
{
if(sz[i-1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==ccu[i1])//将变量赋值并给P2
p2=icu[i1];
}
for(i2=2;i2
{
if(sz[i-1]==i2)//如果为前计算结果，将结果赋值并给P1
p1=dt[i2];
if(sz[i+1]==i2)//如果为前计算结果，将结果赋值并给P2
p2=dt[i2];
}
if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(sz[i+1]==-2)//如果是前运算结果的0，则P2等于0
p2=0;
if(p1==-1)//如果是数字，直接给P1
p1=sz[i-1];
if(p2==-1)//如果是数字，直接给P2
p2=sz[i+1];
dt[j+2]=(!p1||p2)&&(!p2||p1);//等值运算
sz[i-1]=j+2;
j++;
j5++;
p1=-1;
p2=-1;
for(i1=i;i1
sz[i1]=sz[i1+2];
i--;
}
returndt[j+1];//返回结果
}
}
实验数据及结果分析
图1.初始界面
图2.根据需要选择写出公式
实验三1、关系的闭包运算
一、实验目的
熟悉关系的闭包运算，利用C语言编程实现五种关系闭包运算算法。
二、实验内容
利用矩阵求解有限集上给定关系的自反、对称和传递闭包。
三.实验过程
1.算法分析：
在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）；传递闭包则有两种算法（二选一即可）：
算法1：直接根据计算，过程略。
算法2：Warshall算法(1962)
设R的关系矩阵为M
(1)令矩阵A=M
(2)置i=1
(3)对所有的j，若A[j，i]=1，则
对于k=1，2，…，n，令A[j，k]=A[j，k]+A[i，k]
注：此处为逻辑加，可以使用运算符||
(4)i=i+l．
(5)若i≤n，则转到(3)，否则结束．
流程图
2.程序代码：
#include
voidoutput(ints[][100]);
voidzifan(ints2[][100]);
voidduichen(ints2[][100]);
voidchuandi2(ints2[][100]);
voidchuandi1(ints2[][100]);
voidaa();
ints[100][100],z;
intd,n,i,j;
intmain(){aa();return0;}
voidaa()
{
printf("请输入矩阵的行数M<10\n");
scanf("%d",&n);
printf("请输入矩阵的列数N<10\n");
scanf("%d",&d);
printf("请输入关系矩阵\n");
for(i=0;i
{printf("\n");
printf("请输入矩阵的第%d行元素",i);
for(j=0;j
scanf("%d",&s[i][j]);
}
printf("输入对应序号选择算法\n1:自反闭包\n2:传递闭包1\n3:传递闭包(Warhall算法)2\n4:对称闭包\n");
scanf("%d",&z);
switch(z)
{
case1:zifan(s);break;
case2:chuandi1(s);break;
case3:chuandi2(s);break;
case4:duichen(s);break;
}
}
voidoutput(ints[][100])
{printf("所求关系矩阵为\n");
for(i=0;i
{for(j=0;j
printf("%d",s[i][j]);
printf("\n");
}
}
voidzifan(ints2[][100])
{
for(i=0;i
s2[i][i]=1;
output(s2);aa();
}
voidduichen(ints2[][100])
{ints1[100][100];
for(i=0;i
for(j=0;j
s1[j][i]=s2[i][j];
for(i=0;i
for(j=0;j
{s2[i][j]=s2[i][j]+s1[i][j];
if(s2[i][j]>1)
s2[i][j]=1;
}
output(s2);
aa();
}
voidchuandi1(ints2[][100])
{intm[100][100],a[100][100],k,h;
intt[100][100];
for(i=0;i
for(j=0;j
{a[i][j]=0;
t[i][j]=s2[i][j];
m[i][j]=s2[i][j];}
for(h=0;h
{for(i=0;i
for(j=0;j
if(m[i][j]==1)
{for(k=0;k
if(s2[j][k]==1)
a[i][k]=1;
}
for(i=0;i
for(j=0;j
{m[i][j]=a[i][j];
t[i][j]+=a[i][j];
a[i][j]=0;
if(t[i][j]>1)
t[i][j]=1;
}
}
output(t);aa();
}
voidchuandi2(ints2[][100])
{intk;
for(i=0;i
for(j=0;j
if(s2[j][i]==1)
for(k=0;k
s2[j][k]+=s2[i][k];
for(i=0;i
for(j=0;j
if(s2[i][j]>1)
s2[i][j]=1;
output(s2);aa();
}
3.实验数据及结果分析
图1.初始界面
图2.根据需要选择各闭包
实验三2、任意两个集合的交集、并集和差集
一.实验目的
集合论是一切数学的基础，集合的运算规则是集合论中的重要内容。通过该组实验，目的是让我们更加深刻地理解集合的概念和性质，并掌握集合的运算规则等。
二.实验内容
通过对集合的掌握，利用C语言编程计算任意两个集合的交集、并集和差集运算。
实验过程
算法分析
1.在求交集时，利用if找出两个集合的相同元素，并输出。
2.在求并集时，将两个集合的元素属于其一或另一个。
3.在求差集时，将一个集合减去交集，然后将其输出。
程序代码：
#include"stdio.h"
#defineM5
#defineN5
voidmain()
{
inti,j,k=-1,n=0;
intjj=-1,bb=-1;
inta[M],b[N],c[MN],d[M+N],x[MN],y[M+N];
printf("欢迎进入\n");
printf("请输入一个集合\n");
for(i=0;i
scanf("%d",&a[i]);
printf("请输入另一个集合\n");
for(i=0;i
scanf("%d",&b[i]);
for(i=0;i
{
for(j=0;j
if(a[i]==b[j])
{
k++;
c[k]=a[i];
}
}
printf("\n求交集:\n");
for(i=0;i<=k;i++)
{
n=0;
for(j=i+1;j<=k;j++)
{
if(c[i]!=c[j])
{
n++;
}
}
if(n==k-i)
{
jj++;
x[jj]=c[i];
printf("%d",c[i]);
}
}
printf("\n求并集:\n");
for(i=0;i
d[i]=a[i];
for(j=0;j
d[M+j]=b[j];
for(i=0;i<=M+N-1;i++)
{
n=0;
for(j=i+1;j<=M+N-1;j++)
{
if(d[i]!=d[j])
{
n++;
}
}
if(n==M+N-1-i)
{
bb++;
y[bb]=d[i];
printf("%d",d[i]);
}
}
printf("\n求差集:\n");
for(i=0;i<=bb;i++)
{
n=0;
for(j=0;j<=jj;j++)
{
if(y[i]!=x[j])
{
n++;
}
}
if(n-1==jj)
printf("%d",y[i]);
}
}
实验数据及结果分析
图1.菜单界面
图2.交集、并集、差集的实现
实验三3、全域关系和恒等关系
一．实验目的
1.通过上机编写程序，可以进一步加深我们对关系中集合A上的恒等关系，以及从集合A到集合B上的恒等关系的理解。
2.学会用程序去解决离散数学中的一些问题。
3.增强我们编写程序的能力，提高了我们的逻辑思维能力。
4.让我们更加熟悉的去使用word文档去整理这次的实验。
二．实验内容
三．实验过程
1.算法分析
用C语言实现，求集合A上的恒等关系以及从集合A到集合B上的全域关系。对于A上的恒等关系，只需让二元关系的第一个元素和第二个元素相等即可；对于从A到B上的全域关系，即求A和B的笛卡尔积。让A中的第一个元素对应B中的每一个元素，让A中的第二个元素对应B中的每一个元素，依次进行下去，即可得到从A到B上的全域关系。
流程图
程序代码：
#include
voidmain()
{
inta[20],b[20],i,j,n,m,x,y;
printf("请输入两个集合的元素的个数：\n");
scanf("%d%d",&n,&m);
printf("请输入第一个集合的元素：\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("请输入第二个集合的元素：\n");
for(j=1;j<=m;j++)
scanf("%d",&b[j]);
printf("A集合的元素为：\n");
for(x=1;x<=n;x++)
printf("%d",a[x]);
printf("\n");
printf("A集合的恒等关系为：\n");
for(x=1;x<=n;x++)
printf("<%d,%d>",a[x],a[x]);
printf("\n");
printf("A到B的全域关系为：\n");
for(x=1;x<=n;x++)
for(y=1;y<=m;y++)
printf("<%d,%d>",a[x],b[y]);
printf("\n");
printf("B集合的元素为：\n");
for(y=1;y<=m;y++)
printf("%d",b[y]);
printf("\n");
printf("B集合的恒等关系为：\n");
for(y=1;y<=n;y++)
printf("<%d,%d>",b[y],b[y]);
printf("\n");
printf("B到A的全域关系为：\n");
for(y=1;y<=m;y++)
for(x=1;x<=n;x++)
printf("<%d,%d>",b[y],a[x]);
printf("\n");
}
四．实验数据及结果分析
图1.菜单界面
图2.全域关系和恒等关系
结束语
离散数学课程在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言编译技术、人工智能、算法设计与分析等必不可少的先行课程。不但作为计算机科学与技术及相关专业的理论基础及核心主干课，对后续课程提供必需的理论支持。更重要的是旨在“通过加强数学推理，组合分析，离散结构，算法构思与设计，构建流程图等方面专门与反复的研究、训练及应用，培养提高学生的数学思维能力和对实际问题的求解能力。”通过对离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
-3-
开始
P为1或0
P为1或0
运算
是否继续
结束
Y
Y
Y
N
N
N
输入P值
输入Q值
输出结果
开始
输入式子
计算变量数
生成真值表
输出真值表
变量赋值
运算式子
输出结果
归类主范式
输出主范式
结束
循环是否结束
Y
N
开始
声明各子函数
输入关系矩阵
输入z
z=1；调用自反闭包函数
z=2，调用对称闭包函数
z=3调用传递闭包函数
结束
|
|
