离散数学实验报告__四个实验
温柔似野鬼°
611次浏览
2021年01月30日 00:56
最佳经验
本文由作者推荐
欧若拉简谱-啫啫煲
《
离散数学
》
课程设计
学
院
计算机学院
学生
学
号
指导教师
评阅意见
提交日期
2011
年
11
月
25
日
引言
《 离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信
息技术，生物技术等的核心基础 课程。它是研究离散量（如整数、有理数、有限
字母表等）
的数学结构、
性质及关系的 学问。
它一方面充分地描述了计算机科学
离散性的特点，为学生进一步学习算法与数据结构、程 序设计语言、操作系统、
编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、
网络、
计算机图形学等专业课打好数学基础；
另一方面，
通过学习离散数学课 程，
学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，
还可以培养 和提高抽象思维能力和严密的逻辑推理能力，
为今后爱念族皮及用计
算机处理大量的日常事务和 科研项目、
从事计算机科学和应用打下坚实基础。
特
别是对于那些从事计算机科学与理 论研究的高层次计算机人员来说，
离散数学更
是必不可少的基础理论工具。
实验一、
编程判断一个二元关系的性质（是否具有自
反性、反自 反性、对称性、反对称性和传递性）
一、前言引语
：
二元关系是离散数学中 重要的容。因为事物之间总是可以根
据需要确定相应的关系。
从数学的角度来看，
这类 联系就是某个集合中元素之间
存在的关系。
二、数学原理
：自反、对称、传递关系
设
A
和
B
都是已知的集合，
R
是
A
到
B
的一个确定的二元关 系，那么集合
R
就是
A
×
B
的一个合于
R={(x ,y)
∈
A
×
B|xRy}
的子集合
设
R
是集合
A
上的二元关系：
自反关系：对任意 的
x
∈
A,
都满足
∈
R
，则称
R
是自反的，或称
R
具有自反
性，即
R
在
A
上是自反的
(
x)((x
∈
A)
→
(
∈
R))=1
对称关系：对任意的
x,y
∈
A
，如果
∈
R
，那么
∈
R
，则称关系
R
是对称
的，
或称
R
具有对称性，
即
R
在
A
上是对称的
(
x)(
y)((x
∈
A)
∧
(y
∈
A)
∧
(
∈
R)
→
(
∈
R))=1
传递关系：对任意的
x,y,z∈
A
，如果
∈
R
且
R
，那么
∈
R
，则称关
系
R
是传递的，或称
R
具有传递性，即
R
在
A
上是 传递的
(
x)(
y)(
z)[ (x
∈
A)
∧
(y
∈
A)
∧
(z
∈
A)
∧
((
∈
R)
∧
(
R)
→
(
∈
R))]=1
三、实验原理
：通过二元关系与关系矩阵的联系，可以引入
N
维数组，以数
组 的运算来实现二元关系的判断。
图示：
性质
自反性
反自反性
对称性
反对称性
关系矩阵特性
主对角线元素全为
1
主对角线元素全为
0
对称矩阵
非主对角线上的元素等于
1
且与之对称
的元素等于
0
矩阵
（
M*M
）
中
1
所在的位置，
M
中与之相对应位置鲜红都为
1
传递性
四、实验环境
：
Windows 7 Ultimate
DEV C++
五、实验语言
：
C
语言
六、程序源代码
：
#include
#define N 4
main()
{
int i,j,k;
int f,e,z;
int M[N][N];
printf(
判断< br>R
是否为自反关系、对称关系、是否可传递？
n
printf(
请输入一个
4*4
的矩阵。
n
for(i=0;i
/*
输入一个
4*4
的矩阵
*/
for(j=0;j
scanf(
for(i=0;i
{
for(j=0;j
printf(
printf(
}
for(i=0;i
{
if(M[i][i]==1)//
判断自反性
{
if(i=N-1
e=0;
else
;
}
else if(M[i][i]==0)//
判断反自反性
{
if(i=N-1)
e=1;
else
;
}
else
{
e=2;
break;
}
}
for(i=0;i
{
for(j=0;j
if(M[i][j]!=M[j][i])//
判断对称性
{
f=1;
break;
}
}
for(i=0;i
{
for(j=0;j
if(M[i][j]==1)//
判断反对称性
{
if(M[j][i]==0)
{
if(i==(N-1)&&j==N-1)
f=0;
else
break;
}
}
}
if(f!=0&&f!=1)
{
f=2;
}
for(i=0;i
for(j=0;j
if(M[i][j]==1)
continue;
else
for(k=0;k
if(M[i][k]*M[k][i]==0)
continue;
else
z=0;
if(e==0)
printf(
关系
R
是自反关系
n
else if(e==1)
printf(
关系
R
是反自反关系
n
else if(e==2)
printf(
关系
R
是反自反关系
n
if(f==0)
printf(
关系
R
是反对称关系
n
else if(f==1)
printf(
关系
R
不是对称关系
n
else if(f==2)
printf(
关系
R
是对称关系
n
if(z==0)
printf(
关系
R
是不可传递关系
n
else
printf(
关系
R
是可传递关系
n
system(
}
七、程序运行截图
：
i
、程序启动截图：
ii
、程序输入截图：
iii
、程序运行结果截图
:
八、实验总结：
实验简洁高效地判断二元关系的性质。
实验二、
编程求一个二元关系的自反闭包、对称闭包、
传递闭包
一、前言引语
一个二元关系可能具有某种性质，也可能不具有这种性质。现在讨论怎 样
使一个二元关系变成具有指定性质的新关系，并且还要满足最小性条件。
二、
数学原理
自反闭包、对称闭包、传递闭包
设
R
是定义在
A
上的二元关系，若存在
A
上的关系
R
′满足：
1)
R
′是自反的
(
或对称的、或可传递的
)
，
2)
R
R
′，
3)
对
A
上任何其它满足
1
）和
2
）的关系
R
〞，都有：
R
′
R
〞。
则称
R
′为
R
的自反闭包
(
或对称闭包、
或传递闭包
)
，
分别记为
r(R)
、
(s(R)
和
t(R))
。< br>
三、
实验原理
Warshall
算法的基本思想
对每个结点
（从第一列开始）< br>，
找出所有具有到此结点的有向边的结点
（即
该列中元素为
1
的所在行的结点）
，再将这些结点所在行同该结点所在行进行逻
辑加后作为这些结点所在的新行 （添加新的有向边）
（反映了如果这些结点没有
到其它结点的有向边，
但有到该结点的 有向边，
再通过该结点间接到达其它结点，
根据传递闭包的定义，这些结点就必然有一条有向边 到达其它结点）
。
▪
设
R
是集合上的二元关系
,Mr
是
R
的关系矩阵
▪
(1)
置新矩阵
A:=Mr
▪
(2)
置
(
列
)
j:=1
▪
(3)
对所有的
i(1
≤
i
≤
n)
如
A(i,j)=1,
则对
k=1,2,
…,n
A(i,k):=A(i,k)
A(j,k)
▪
(
即将
A
的第
i
行与
A
的第
j
行 进行逻辑加后送回
A
的第
i
行
)
▪
(4)j:=j+1
▪
(5)
如
j
≤
n
转
(3),
否则停止。
四、实验环境：
Windows 7 Ultimate
DEV C++
五、实验编程语言：
C
语言
六、实验程序源代码
//source file:
#include
void War(int m,int n)
{
int i,j,k;
设置临时变量
int a = 0, b = 0;
设置临时变量
int arr[10][10];
for(a = 0; a < m; ++a)
{
printf(
请输入矩阵第
%d
行元素
:
for(b = 0; b < n; ++b)
{
scanf(
}
printf(
}
for(i = 0; i < m; i++)
{
for( j= 0; j < m; j++)
{
if(arr[j][i] == 1)
{
for(k = 0;k < n; k++)
{
arr[j][k]=arr[i][k] || arr[j][k];
}
}
}
}
printf(
所得的可传递闭包关系矩阵是：
n
for(i = 0;i < m; ++i)
{
for(j = 0;j < n; ++j)
{
printf(
}
printf(
}
}
//file:
#include
void main()
{
printf(利用
Warshall
算法求二元关系的可传递闭包
n
void War(int , int);
int m, n;
printf(
请输入矩阵 的行数
(
必须小于
10
）
：
scanf(
printf(
请输入矩阵的列数
(
必须小于
10
）
：
scanf(
War(m, n);