《离散数学》
实验报告
学 院 科信软件学院
专 业 计算机科学与技术
指导教师 邹丽娜
学 号 10999181
姓 名 赵辉
提交日期 20##-12-23
实验一连结词逻辑运算
一.实验目的
实现二元合取、析取、蕴涵和等价表达式的计算。熟悉连接词逻辑运算规则，利用程序语言实现逻辑这几种逻辑运算。
二.实验内容
从键盘输入两个命题变元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<stdio.h>
int main()
{
int p,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){
case 1:{
if(p&&q) printf("合取运算：p/\\q=1\n");
else printf("合取运算：p/\\q=0\n");
break;
}
case 2:{
if(p||q) printf("析取运算：p\\/q=1\n");
else printf("析取运算：p\\/q=0\n");
break;
}
case 3:{
if(p&&!q) printf("蕴含：p->q=0\n");
else printf("蕴含：p->q=1\n");
break;}
case 4:{
if((p&&q)||(!p&&!q)) printf("等价运算：p<->q=1\n");
else printf("等价运算：p<->q=0\n");
break; }
}printf("是否继续运算1\\0\n");
scanf("%d",&t);
}while(t);
return 0;
}
3.实验数据及结果分析；
初始界面
输入及选择进行的操作
循环操作
退出
实验二关系的闭包运算
一、实验目的
熟悉关系的闭包运算，编程实现关系闭包运算算法。
一、实验内容
利用矩阵求解有限集上给定关系的自反、对称和传递闭包。
三. 实验过程
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. 程序代码：(c++)
#include<iostream.h>
int m,n;
void zifan(int a[100][100]){
int i,j;
a[0][0]=a[1][1]=a[2][2]=a[3][3]=1;
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
{cout<<a[i][j];
cout<<" ";}
cout<<endl;}
}
void duichen(int a[100][100]){
int i,j;
int c[100][100];
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
{c[i][j]=a[i][j]||a[j][i];
cout<<c[i][j]<<" ";}
cout<<endl;}
}
void chuandi(int a[100][100]){
int i,j,k;
int c[100][100];
for(k=0;k<m;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i][j]=a[i][j]||a[i][k+1]&&a[k+1][j];
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
cout<<c[i][j]<<" ";
cout<<endl;}
}
int main(){
int i,j,z;
int b[100][100];
cout<<"input the matrix"<<endl;
cout<<"请输入矩阵的行数<必须小于10>:";
cin>>m;
cout<<endl;
cout<<"请输入矩阵的列数<必须小于10>:";
cin>>n;
cout<<endl;
for(i=0;i<m;i++)
{cout<<"请输入第"<<i<<"行元素:"<<endl;
for(j=0;j<n;j++)
cin>>b[i][j];}
int t;
do{
cout<<"请输入要选择的操作:"<<endl;
cout<<"1自反闭包的关系矩阵为:"<<endl;
cout<<"2对称闭包的关系矩阵为:"<<endl;
cout<<"3传递闭包的关系矩阵为:"<<endl;
cin>>z;
switch(z){
case 1: zifan(b);break;
case 2: duichen(b);break;
case 3: chuandi(b);break;
}
cout<<"是否继续（继续1退出0）：";
cin>>t;}while(t);
return 0;
}
3.实验数据及结果分析
输入
进行操作1：自反闭包
进行操作2：对称闭包
进行操作3传递闭包
退出
第二篇：离散数学实验报告
离散数学闭包实验报告
专业 10计算机科学与技术（嵌入式软件人才培养方向）
学号 1045534148
姓名 周谦益
时间 20##—11--15
一、实验目的
1. 通过上机程序，进一步加深对关系中自反闭包，对称闭包，传递闭包的理解。
2. 掌握Warshall算法。
3. 学会用程序解决离散数学中的问题。
4. 增强我们编写程序的能力。
二、实验内容
求有限集上给定关系的自反、对称和传递闭包（用Warshall算法）。
三、实验环境
我的实验是在Vs2008实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。
四、实验原理和实现过程
设计思路
在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则只需要将矩阵中数值为1的元素关于主对角线对称的元素数值也设为1就可以了；而对于传递闭包，用Warshall算法可以很方便的计算出来。下面我就来具体分析一下每一种闭包运算的设计。
自反闭包的设计：我们只要把关系矩阵的对角线的元素全赋值为1就可以啦。具体程序如下：
求自反闭包的程序：
int Relation::Reflexive()//求自反闭包的函数
{
for(int i=0;i<Len;i++)
if(!R[i][i])return(0);
return(1);
};
对称闭包的求法：对于对称闭包，我们只只需要将矩阵中数值为1的元素的对称位置的元素数值也设为1就可以了。具体程序如下：
对称闭包：
int Relation::Symmetric()//对称闭包的函数
{
int i,j,K=Len-1;
for(i=0;i<K;i++)
for(j=i+1;j<Len;j++)
if(R[i][j]!=R[j][i])return(0);
return(1);
};
传递闭包设计：传递闭包我主要用Warshall算法来求。
书上的Walshall算法的伪代码如下：
设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)，否则结束
根据Warshall算法，我设计求出了关系的传递闭包，具体程序如下：
int Relation::Transitive()//传递闭包函数
{
Relation t;
t=C_t(1);
for(int i=0;i<Len;i++)
for(int j=0;j<Len;j++)
if(R[i][j]!=t.R[i][j])return(0);
return(1);
};
把上面的每个子函数串在一起，再加上主函数，就可以实现这次实验的要求。
程序的完整代码如下所示：
#include "stdafx.h"
#include <iostream>
using namespace std;
int const Max=20;
class Relation
{
protected:
int Len,A[Max],R[Max][Max];
int Index(int x);
public:
Relation(){Len=0;};//空集A，空关系R
Relation(int *p,int Q[Max][Max],int n);//n个元素集合A及其关系
int IsofA(int x);//x是否属于A
int IsofR(int x,int y);
Relation UnionA(Relation R1);//AUR1
Relation CrossR(Relation R1);
Relation C_r();
Relation C_s();
Relation C_t();
Relation C_t(int);
int Reflexive();
int Symmetric();//判断R是否对称
int Transitive();
int Equivalent_Relations();
void PrintA();
void PrintR();
};
int Relation::Index(int x)
{
int i;
for(i=0;i<Len;i++)
if(A[i]==x)return(i);
return(-1);
};
Relation::Relation(int *p,int Q[Max][Max],int n)
{
int i,j;
for(i=0;i<n;i++)
{
A[i]=p[i];
for(j=0;j<n;j++)
R[i][j]=Q[i][j];
};
Len=i;
};
int Relation::Reflexive()//求自反闭包的函数
{
for(int i=0;i<Len;i++)
if(!R[i][i])return(0);
return(1);
};
int Relation::Symmetric()//对称闭包的函数
{
int i,j,K=Len-1;
for(i=0;i<K;i++)
for(j=i+1;j<Len;j++)
if(R[i][j]!=R[j][i])return(0);
return(1);
};
int Relation::IsofA(int x)
{
for(int i=0;i<Len;i++)
if(A[i]==x)return(1);
return(0);
};
int Relation::IsofR(int x,int y)
{
int i,j;
i=Index(x);
j=Index(y);
if(i==-1||j==-1||R[i][j]==0)return(0);
return(1);
};
Relation Relation::UnionA(Relation R1)
{
int i,j;
Relation t;
for(i=0;i<Len;i++)t.A[i]=A[i];
t.Len=Len;
for(j=0;j<R1.Len;j++)
{
for(i=0;i<Len;i++)
if(t.A[i]==R1.A[j])break;
if(i>=Len)t.A[t.Len++]=R1.A[j];
};
for(i=0;i<t.Len;i++)
for(j=0;j<t.Len;j++)
t.R[i][j]=0;
return(t);
};
Relation Relation::CrossR(Relation R1)
{
int i,j;
Relation t;
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=0;j<Len;j++)
t.R[i][j]=R[i][j] && R1.R[i][j];
};
t.Len=Len;
return(t);
};
Relation Relation::C_r()//自反闭包
{
int i,j;
Relation t;
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=0;j<Len;j++)
{
t.R[i][j]=R[i][j];
if(i==j)t.R[i][j]=1;
};
};
t.Len=Len;
return(t);
};
Relation Relation::C_s()//对称闭包
{
int i,j;
Relation t;
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=i;j<Len;j++)
{
if(R[i][j]==1)t.R[i][j]=t.R[j][i]=1;
else
{
if(R[j][i]==1)t.R[i][j]=t.R[j][i]=1;
else t.R[i][j]=t.R[j][i]=0;
};
};
};
t.Len=Len;
return(t);
};
Relation Relation::C_t()//传递闭包
{
int i,j,k,l,v;
Relation t;
int M[Max][Max],N[Max][Max];
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=0;j<Len;j++)
t.R[i][j]=M[i][j]=R[i][j];
};
for(i=1;i<Len;i++)//共Len-1次
{
for(j=0;j<Len;j++)//行
for(k=0;k<Len;k++)//列
{
v=0;
for(l=0;l<Len;l++)//对行列加乘
v=v||M[j][l]&&R[l][k];//布尔加乘
N[j][k]=v;
};
for(j=0;j<Len;j++)
for(k=0;k<Len;k++)
{
t.R[j][k]=t.R[j][k]||N[j][k];
M[j][k]=N[j][k];
};
};
t.Len=Len;
return(t);
};
Relation Relation::C_t(int x)
{
int i,j,l;
Relation t;
for(i=0;i<Len;i++)
{
t.A[i]=A[i];
for(j=0;j<Len;j++)
t.R[i][j]=R[i][j];
};
for(i=0;i<Len;i++)
{
for(j=0;j<Len;j++)
if(t.R[j][i]==1)
{
for(l=0;l<Len;l++)
t.R[j][l]=t.R[j][l]||t.R[i][l];
};
};
t.Len=Len;
return(t);
};
int Relation::Transitive()//求传递闭包函数
{
Relation t;
t=C_t(1);
for(int i=0;i<Len;i++)
for(int j=0;j<Len;j++)
if(R[i][j]!=t.R[i][j])return(0);
return(1);
};
int Relation::Equivalent_Relations()
{
return(this->Reflexive()&&Symmetric()&&Transitive());
};
void Relation::PrintA()
{
int i;
if(Len==0)cout<<"空集\n";
else
{
for(i=0;i<Len;i++)
{
cout<<A[i]<<'\t';
if((i+1)%10==0)cout<<endl;
};
};
cout<<endl;
};
void Relation::PrintR()
{
int i,j;
if(Len==0)cout<<"空关系\n";
else
{
for(i=0;i<Len;i++)
{
cout<<"第"<<i<<"行："<<endl;
for(j=0;j<Len;j++)
{
cout<<R[i][j]<<'\t';
if((i+1)%10==0)cout<<endl;
};
};
};
cout<<endl;
};
int main(int argc, char* argv[])
{
int B[10]={10,11,12,13,14,15,16,17,18,19};
int C[6]={30,31,12,16};
int M1[Max][Max]={{0,1,0,1},{1,1,0,1},{0,0,1,0},{0,1,0,1}};
Relation R1,R2(C,M1,4);
Relation Rb(B,M1,4);
Rb.PrintA();
Rb.PrintR();
cout<<Rb.IsofA(12)<<"isof12!"<<endl;
cout<<Rb.IsofA(15)<<"isof15!"<<endl;
cout<<Rb.IsofR(10,11)<<"isof 10-11!"<<endl;
cout<<Rb.IsofR(9,11)<<"isof 9-11!"<<endl;
cout<<Rb.IsofR(10,21)<<"isof 10-21!"<<endl;
R1=R2.CrossR(Rb);
R1.PrintR();
cout<<"等价:"<<R1.Equivalent_Relations()<<endl;
cout<<"R2\n";
R2.PrintR();
cout<<"R1\n";
R1.PrintR();
cout<<"Reflexive:"<<R1.Reflexive()<<endl;
cout<<"Symmetric:"<<R1.Symmetric()<<endl;
cout<<"Transitive:"<<R1.Transitive()<<endl;
R1=R2.C_r();
R1.PrintR();cout<<"C_r\n";cout<<"Reflexive:"<<R1.Reflexive()<<endl;
R1=R2.C_s();
R1.PrintR();cout<<"C_s\n";cout<<"Symmetric:"<<R1.Symmetric()<<endl;
R1=R2.C_t();
R1.PrintR();cout<<"C_t\n";
R1=R2.C_t(1);cout<<"Transitive:"<<R1.Transitive()<<endl;
R1.PrintR();cout<<"C_r\n";
cout<<"等价:"<<R1.Equivalent_Relations()<<endl;
Rb=R2.CrossR(R1);
cout<<"Cross\n";
cout<<"Rb\n";
Rb.PrintR();
cout<<"Hello World!\n";
return 0;
getchar();
}
五、实验输入输出和数据
程序输出时会依次输出自反闭包，对称闭包和传递闭包，并且会分别输出各个闭包的关系序偶和关系矩阵。
输入结束）。
六、心得体会
通过本次实验让我进一步加深了对关系的理解，也掌握了有关关系的一些运算，同时也提高了我的编程能力，学会了使用Warshall算法。我认为这是一次很有意义的实验。