《离散数学》
实验报告
姓名:
学号:
班级:
实验一 连结词逻辑运算
一.实验目的
实现二元合取、析取、蕴涵和等价表达式的计算。熟悉连接词逻辑运算规则,利用程序语言实现逻辑这几种逻辑运算。
二.实验内容
从键盘输入两个命题变元P和Q的真值,求它们的合取、析取、蕴涵和等价四种运算的真值。要求对输入内容进行分析,如果不符合0、1条件需要重新输入,程序有良好的输入输出界面。
三.实验环境
使用Microsoft Visual C++6.0为编程软件,采用称C/C++语言为编程语言实现。
四.实验过程
1.算法分析:
合取: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,a,b,c,d,p,q;
printf(" P的值");
for(P=0;P<2;P++)
{
for(Q=0;Q<2;Q++)
printf("\t%d",P);
}
printf("\n Q的值");
for(P=0;P<2;P++)
{
for(Q=0;Q<2;Q++)
printf("\t%d",Q);
}
printf("\n 非P的值");
for(P=0;P<2;P++)
{
for(Q=0;Q<2;Q++)
{
if(P==0)/*判断非P的值*/
p=1;
else
p=0;
printf("\t%d",p);
}
}
printf("\n 非Q的值");
for(P=0;P<2;P++)
{
for(Q=0;Q<2;Q++)
{
if(Q==1)/*判断非Q的值*/
q=0;
else
q=1;
printf("\t%d",q);
}
}
printf("\n P与Q的值");
for(P=0;P<2;P++)
{
for(Q=0;Q<2;Q++)
{
if(Q==0||P==0)/*判断P与Q的值*/
a=0;
else
a=1;
printf("\t%d",a);
}
}
printf("\n P或Q的值");
for(P=0;P<2;P++)
{
for(Q=0;Q<2;Q++)
{
if(Q==1||P==1)/*判断P或Q的值*/
b=1;
else
b=0;
printf("\t%d",b);
}
}
printf("\nP蕴含Q的值");
for(P=0;P<2;P++)
{
for(Q=0;Q<2;Q++)
{
if(P==1&&Q==0)/*判断P蕴含Q的值*/
c=0;
else
c=1;
printf("\t%d",c);
}
}
printf("\nP等价Q的值");
for(P=0;P<2;P++)
{
for(Q=0;Q<2;Q++)
{
if(P==Q)/*判断P等价Q的值*/
d=1;
else
d=0;
printf("\t%d",d);
}
}
printf("\n");
return 0;
}
3.实验数据及结果分析:
实验二 关系的复合运算及逆运算
一.实验目的
熟悉关系的复合运算和逆运算,编程实现关系复合运算和逆运算算法。
二.实验内容
利用矩阵求解有限集上的复合关系和逆关系。
三.实验过程
1.算法分析:
复合运算就将两个用矩阵表示的关系进行复合,即在第一个矩阵中寻找值为1的元素坐标(i ,j ),在第二个矩阵第j行寻找值为1的元素,若有,且坐标为(j ,k ),则产生的新的关系的矩阵中坐标为(i ,k )的元素值为1。
逆运算就是将用矩阵中值为1的元素坐标(i ,j)对调,产生新的关系的矩阵中坐标为(j ,i )的元素值为1。
2.程序代码:
//关系的复合运算
#include<iostream>
using namespace std;
int main()
{
int a[100][100],b[100][100],c[100][100],i,j,k,n;
cout<<"请输入集合X中元素的个数:";
cin>>n;
cout<<"请输入关系矩阵Mr的格式:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cin>>a[i][j];
}
cout<<"请输入关系矩阵Ms的格式:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cin>>b[i][j];
}
for(i=0;i<n;i++) //进行复合运算
{
for(j=0;j<n;j++)
if(a[i][j]==1)
for(k=0;k<n;k++)
if(b[j][k]==1)
c[i][k]=1;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(c[i][j]!=1)
c[i][j]=0;
}
cout<<endl;
cout<<"关系矩阵Mr与Ms的复合运算结果是:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<c[i][j]<<" ";
cout<<endl;
}
return 0;
}
//关系的逆运算
#include<stdio.h>
int main()
{
int a[100][100],b[100][100],n,i,j,index;
printf("请输入集合X中元素的个数:");
scanf("%d",&n);
printf("请输入关系矩阵Mr的格式:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
for(i=0;i<n;i++)//进行逆运算
{
for(j=0;j<n;j++)
if(a[i][j]==1)
{
index=i;
i=j;
j=index;
b[i][j]=1;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(b[i][j]!=1)
b[i][j]=0;
}
printf("\n关系矩阵M rc为:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d ",b[i][j]);
printf("\n");
}
return 0;
}
3.实验数据及结果分析:
实验三 关系的闭包运算
一.实验目的
熟悉关系的闭包运算,编程实现关系闭包运算算法。
二.实验内容
利用矩阵求解有限集上给定关系的自反、对称和传递闭包。
三.实验过程
1.算法分析:
在三种闭包中自反和对称闭包的求解很容易,对矩阵表示的关系,其自反闭包只要将矩阵的主对角线全部置为1就可;对称闭包则加上关系的转置矩阵(逻辑加法);传递闭包则直接根据t(R)=R +。
2.程序代码:
#include<iostream>
using namespace std;
void deliver(int x[100][100],int y[100][100],int n);
int main()
{
int i,j,n,R[100][100],r[100][100],s[100][100],t[100][100];
cout<<"请输入矩阵的阶:";
cin>>n;
cout<<endl<<"请输入R的关系矩阵:"<<endl;
for(i=0;i<n;i++) //输入R的关系矩阵
{
for(j=0;j<n;j++)
cin>>R[i][j];
}
for(i=0;i<n;i++) //将R的关系矩阵赋值给r,s,t
{
for(j=0;j<n;j++)
{
r[i][j]=R[i][j];
s[i][j]=R[i][j];
t[i][j]=R[i][j];
}
}
for(i=0;i<n;i++) //自反闭包运算
{
if(r[i][i]==0)
r[i][i]=1;
}
cout<<endl<<"自反闭包关系矩阵r(R):"<<endl;
for(i=0;i<n;i++) //输出r的关系矩阵
{
for(j=0;j<n;j++)
cout<<r[i][j]<<" ";
cout<<endl;
}
for(i=0;i<n;i++) //对称闭包运算
{
for(j=0;j<i;j++)
{
if(s[i][j]==1||s[j][i]==1)
{
s[i][j]=1;
s[j][i]=1;
}
}
}
cout<<endl<<"对称闭包关系矩阵s(R):"<<endl;
for(i=0;i<n;i++) //输出s的关系矩阵
{
for(j=0;j<n;j++)
cout<<s[i][j]<<" ";
cout<<endl;
}
deliver(t,R,n); //关于传递闭包的函数
return 0;
}
void deliver(int x[100][100],int y[100][100],int n)//关于传递闭包的函数
{
int i,j,k,m,z[100][100];
for(m=0;m<n;m++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(x[i][j]==1)
{
for(k=0;k<n;k++)
if(y[j][k]==1) //进行复合运算
z[i][k]=1;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(z[i][j]!=1)
z[i][j]=0;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
x[i][j]=x[i][j]+z[i][j]; //进行传递闭包运算
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(x[i][j]!=0)
x[i][j]=1;
}
}
cout<<endl<<"传递闭包关系矩阵t(R):"<<endl;
for(i=0;i<n;i++) //输出x的关系矩阵
{
for(j=0;j<n;j++)
cout<<x[i][j]<<" ";
cout<<endl;
}
}
3.实验数据及结果分析:
实验四 图的矩阵表示
一.实验目的
熟悉图的矩阵表示方法——邻接矩阵、可达矩阵和关联矩阵。
二.实验内容
利用邻接矩阵得到的可达矩阵来求解图的连通性质。
三.实验过程
1.算法分析:
可达矩阵表示图中任意两个节点间的可达关系,而邻接矩阵表示图中任意两个节点的邻接关系。求解邻接矩阵可知任意两个节点之间是否存在互相连通的路,从而判断是否可达。
2.程序代码:
#include<iostream>
using namespace std;
void main()
{
int i,j,k,n,m,a[100][100],b[100][100],c[100][100],d[100][100];
cout<<"请输入矩阵阶数:";
cin>>n;
cout<<"请输入邻接矩阵a:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>a[i][j];
b[i][j]=a[i][j];
}
}
for(i=0;i<n;i++) //矩阵d为零矩阵
{
for(j=0;j<n;j++)
d[i][j]=0;
}
for(m=0;m<n;m++)
{
for(i=0;i<n;i++) //矩阵c为零矩阵
{
for(j=0;j<n;j++)
c[i][j]=0;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
c[k][i]=c[k][i]+b[k][j]*a[j][i]; //矩阵的乘法运算
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
b[i][j]=c[i][j];
d[i][j]=d[i][j]+b[i][j];
}
}
cout<<"m为"<<m+1<<",矩阵b为:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<b[i][j]<<" ";
cout<<endl;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(d[i][j]!=0)
d[i][j]=1;
}
cout<<"可达矩阵d为:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<d[i][j]<<" ";
cout<<endl;
}
}
3.实验数据及结果分析:
第二篇:离散数学上机---二元关系
**大学集合论与图论上机实验报告
一、实验目的
1. 通过上机程序,进一步加深对二元关系传递性判别,自反闭包,对称闭包,传递闭包的理解。
2. 掌握传递性判别。
3. 学会用程序解决离散数学中的问题。
4. 增强我们编写程序的能力。
二、实验内容
实验1:二元关系传递性判别
实验2:有限集上给定关系的自反、对称和传递闭包
三、使用环境
Windows 7 vs2012
四、核心代码及调试过程
//实验一传递性
#include <iostream>
using namespace std;
void main()
{
int n,i,j,k;
int m=0;
cout<<"请输入矩阵的行列数n:";
cin>>n;
int a[20][20];
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<"请输入a["<<i<<"]["<<j<<"]:";
cin>>a[i][j];
}
} //输入R矩阵
cout<<"R的关系矩阵为:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
} //输出R矩阵
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]!=0)
{
for(k=1;k<=n;k++)
{
if(a[i][k]<a[j][k]) {
m=m+1;
}
}
}
}
}
if(m==0) cout<<"R有传递关系"<<endl;
else cout<<"R没有传递关系"<<endl;
}
//实验2:
//1)自反闭包
#include <iostream>
using namespace std;
void main()
{
int n,i,j;
cout<<"请输入矩阵的行列数n:";
cin>>n;
int a[20][20];
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<"请输入a["<<i<<"]["<<j<<"]:";
cin>>a[i][j];
}
}
cout<<"R的关系矩阵为:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]!=0)
{
a[i][i]=1;
a[j][j]=1; }
}
}
cout<<"R的关系矩阵为:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
//2)对称闭包
#include <iostream>
using namespace std;
void main()
{
int n,i,j;
cout<<"请输入矩阵的行列数n:";
cin>>n;
int a[20][20];
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<"请输入a["<<i<<"]["<<j<<"]:";
cin>>a[i][j];
}
}
cout<<"R的关系矩阵为:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]!=0)
{
a[j][i]=1; }
}
}
cout<<"R的对称闭包矩阵为:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
//3)传递闭包
#include <iostream>
using namespace std;
void main()
{
int n,i,j,k;
int m=0;
cout<<"请输入矩阵的行列数n:";
cin>>n;
int a[20][20];
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<"请输入a["<<i<<"]["<<j<<"]:";
cin>>a[i][j];
}
}
cout<<"R的关系矩阵为:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
{
if(a[i][j]==1)
{
for(k=1;k<=n;k++)
{
a[i][k]=a[i][k]+a[j][k];
if(a[i][k]==2) a[i][k]=1;
}
}
}
}
cout<<"R的传递闭包矩阵为:"<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
实验1:
实验2:
1)自反闭包
2)对称闭包
3)传递闭包
五、总结
通过这次的实验,使我明白了,平日里学习不能浅尝辄止,必须要知道它的方法。做这次实验前我以为我对这块知识已经很熟了,但实际做的时候,发现我还是不是特别懂,必须要反复看书。其次,让我知道了,我平时学的数学知识可以很好的跟计算机结合,让我对程序设计有了更好的认识。