2023年安徽工业大学离散数学实验报告

《离散数学》实验报告

专

业软件工程

班

级163班

姓名周掌珍

学

号

授课教师杨思春

二。一七年六月

目录

实验一联结词的运算

实验二集合的运算

实验三二元关系的性质鉴定

实验四图的矩阵运算

实验一联结词的运算

一.实验目的

通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题

连接词运算的理解，另一方面通过编程实现命题连接词运算,帮助学生复习和锻炼c语言知

识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。

二.实验原理

(1)非运算，符号：1，当P=T时，］p为F,当P=F时，1P为T。

(2)合取，符号：A,当且仅当P和Q的真值同为真，命题PAQ的真值才为真；

否则,PAQ的真值为假。

(3)析取，符号：V,当且仅当P和Q的真值同为假，命题PVQ的真值才为假;

否则，PVQ的真值为真。

(4)异或，符号：▽,当且仅当P和Q的真值不同时，命题PVQ的真值才为

真；否则，PVQ的真值为真。

(5)蕴涵，符号：一，当且仅当P为T,Q为F时，命题P-Q的真值才为假;否

则，P-Q的真值为真。

(6)等价，符号：一，当且仅当P,Q的真值不同时，命题P-Q的真值才为假；

否则，P-Q的真值为真。

三.实验内容

编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。

四.算法程序

内容格式:新罗马，小五号，行间距固定值18磅

#inc1ude<stdio.h>

intmain()

charm；

»intP,Q;

printf("请输入P,Q的真值与逻辑连接词:(P逻辑联结Q)\na：与\tb：或\tc(请先输入0):非\td:

蕴含\te:等价\tf:异或'n");

scanf("%d%c%dH,&P,&m,&Q);

»switch(m)

caseza':。if(P==1&&Q==1)pintf("P与Q=l\n”)；

o。。e1seprintf("p合取Q=0\n")；break；

-case'b>if(P==0&&Q==0)printf("P或Q=0\n");

。。。笛1seprintf("P或Q=1\n")；break;

yase'c"：^if(P==l)printf("非P=0\n")；

ggc1seprintf("非P=1\n");brcak;

ocase'd>if(P==l&&Q==O)printf("P蕴含Q=0\n");

gelseprintf("P蕴含Q=l\n")；break;

ocase'e,if(P==Q)printf("P等价Q=l\n'*);

g。。e1seprintf（"P等价Q=0\n"）;break;

ocase'f：ooif（P二二Q）printf（"P异或Q=0\n”）；

»®delseprintf（nP异或Q=l\nH）;break;

0）

五.实验结果

实验结果截图大小为:宽（10cm）乂高（8011）

r

■*C:\Users\Administrator\Desktop\Debug\0.exe"

:等价f:异或

Ibl

，或。=1

lessanykeytocontinue

六.心得体会

内容格式:宋体，五号,行间距固定值18磅

实验二集合的运算

一.实验目的

集合运算重要涉及并运算，交运算，相对差，对称差运算,集合论的语言适合于描述和

研究离散对象及其关系,所以也是计算机科学与工程的理论基础,在程序设计、关系数据库、

排队论、开关理论，形式语言和自动机理论等学科领域中都有重要的应用。集合运算是学

习集合论的基础,通过编程实现集合的相关运算,帮助同学们学好集合论相关知识打下基

础。

二.实验原理

交运算:任何二个集合A和B的交集AnB是由A和B所共有的所有元素构成的集合，

即：ACB={x|xGAAxeB}

并运算:A、B是任意二个集合,A和B的并集AUB是由A和B的所有元素构成的集合。

即：AUB={x|xeAVxeB}

相对差：设A和B是二个任意集合,B对A的相对差(A-B)是由属于A且不属于B的所

有元素组成的集合。即：A—B={x|XGAAxgB}={x|xeAA-ixeB)

对称差:设A、B是任意二集合，A和B的环和记作A㊉B。

即：AGB=(A-B)U(B—A)=(ACTB)U(BA〜A)

或者xe(A㊉B)oxe{xIxeAVxeB)

三.实验内容

进一步理解集合的四种基本运算,根据每个运算定义,编程实现各个运算。

四.算法程序

内容格式:新罗马，小五号,行间距固定值18磅

交集运算：

#inc1ude<stdio.h>

intmain()

»inta[10]»b[10],c[20],i,m,n,j,k=0;

叩rintf("请输入集合A,集合B中的元素个数:\n");

oscanf("%d%d”,&m,&n);

»printf("请输入集合A的元素:\n")；

ofor(i=0；i<m;i++)

scanf(%dn,&a|i])；

oprintf("请输入集合B的元素：、n”)；

ofor(i=0；i<n；i++)

gscanf("%dn,&b[i])；

叩rintf("A={n);

gfor(i=0;i<m;i++)

-printf("%d；',a[i])；

®»putchar(\b')；

gprintf("}\nn);

printf(”B={")；

ofor(i=0;i<n；i++)

printf("％d,”，b[i]);

®<>putchar('\b')；

加rintf(,,}\nH);

for(i=0;i<m;i++)

for(j=0;j<n;j++)

«if(a[i]==b[j1)c[k++]=a[i];

叩rintf(”AAB=(")；

«for(i=0;i<k；i++)

。printf("%d,"，c[i]);

oputchar('\b')；

叩rintf("}\nH);

)

并集运算：

#include<stdio.h>

intmain()

(

inta[10],b[10],c[20],i,m,nJ,k=0;

叩rintf("请输入集合A,集合B中的元素个数:\n")；

oscanf(”%d%d”,&m,&n);

叩rintf("请输入集合A的元素：\n")；

ofbr(i=0；i<m;i++)

ascanf("％d”,&a[i])；

printf("请输入集合B的元素：\nH);

»for(i=0;i<n;i++)

~scanf("%d",&b[i])；

printf(nA={n);

gfor(i=0;i<m;i++)

。叩rintf(n%d,",a[i]);

叩utcharC\b');

printf("[\nM);

oprintf("B={");

gfor(i=0;i<n；i++)

«printf("%d,",b[i])；

putchar(1\b');

gprintf(")\n")；

0

ofor(i=0;i<m;i++)

gc[k++]=a[i|;

dbr(j=O;jVn；j++)

U

gfor(i=0;i<m;i++)

g“f(b[j1==c[i])break;

gif(i==m)c[k++]=b[j];

。}

oprintf("AUB={");

8for(i=0;i<k;i++)

printf(H%d,"，c[i])；

gputchar('\b');

^printf("}\nM);

1

相对差：

#include<stdio.h>

intmain()

(

。inta[10],b[10],c[20],i,m,n,j,k=O,t;

qprintf("请输入集合A,集合B中的元素个数：\n");

®scanf("%d%d”,&m,&n);

oprintf("请输入集合A的元素:\n”)；

ffor(i=0;i<m；i++)

。scanf("%d",&aEi]);

oprintf(H请输入集合B的元素:\n”)；

efbr(i=0;i<n;i++)

gscanf(M%dn,&b[i])；

叩rintf("A={");

ofor(i=0；i<m;i++)

ooprintf("%da[i]);

o®putchar(W);

。printf("}\n”)；

»printf("B={n);

gfbr(i=0;ivn;i++)

。。叩rintf("％dj,b[i]);

。putchar('\b');

。。printf("}\n");

0

ofor(i=0;ivm;i++)

ac[k++]=a[i];

for(j=0；j<n;j++)

(

。for(i=0;i<m;i++)

。if(b|j]==c[i])

0001

38for(t=i；t<k;t++)

008{

080C[t]=C[t+1]；

I

k--；

009}

)

«printf("A-B=(”);

oofor(i=0;i<k；i++)

aprintf(n%d,n,cLi]);

。。putchar(,\b/);

oprintf("}\n");

)

对称差：

#inc1ude<stdio.h>

intmain()

(

ointa|10],b[l0],c[20],cl[20],c2[20],i,m,n,j,kl=O,k2=0,k=0,t;

叩rintf("请输入集合

oscanf("%d'\&b|i])；

叩rintf("A={")；

。for(i=0；i<m；i++)

。叩rintf(”％d,",a[i]);

。叩utchar(z\b');

叩rintf("}\n");

Printf(HB={")；

ofor(i=0;i<n;i++)

。。叩rintf(H%d,",b[i]);

Mputchar('\b');

print。}\n");

ofbr(i=0；i<m;i++)

®cl[k1++]=a[i]；

fbr(j=0;jvn;j++)

。｛

ofor(i=0；i<m;i++)

。。if(b|j]==cl[i])

do｛

。for(t=i;t<k1;t++)

000(

8。C1[t]=C1[t+1];

OOdj

ok1—；

000|

I

for(j=O;j〈nj++)

。笛2[k2++]=b[j];

fifbr(j=0;jvm;j++)

。｛

o®for(i=0;i<n;i++)

if(a[j]==c2[i])

ggfor(t=i;t<k2；t++)

gg{

°80c2[t]=c2[t+1];

ggk2—;

°}

»for(i=0;i<kl;i++)

c[k++]=c1Ei]；

ofor(j=0;j<k2;j++)

。{

odfor(i=0；i<k1；i++)

。。if(c2[j]==c[i])break;

°°if(i==kl)c[k++]=c2[j];

。}

sprintf("A㊉B={");

。for(i=O;i<k;i++)

。opnntf("%d；;c[i])；

oaputchar('\br);

printf(',}\nn);

I

五.实验结果

实验结果截图大小为:宽（10cm）X高（8cm）

交集运算：

•■C:\Users\Administrator\De5ktop\Debug\0.exe*1

请输入集合A,集合B中的元素个数:

请输入集合A的元素：

1234

请输入集合B的元素：

23456

A=<］，234）

B=<234,5,6）

AP|B=<2,3,4）

Pressanykeytocontinue

并集运算

*'C:\Users\Administrator\Desktop\Debug\O.exe"

请输入集合A，集合B中的元素个数:

34

请输入集合A的元素：

123

请输入集合B的元素：

3456

A=<1,2,3)

B=<345-6)

AljB=<1,2,3,4,5,6>

Pressanykeytocontinue

相对差运算

"C:\Users\Administrator\Desktop\Debug\0.exe"

请输入集合*集合B中的元素个数:

请输入集合A的元素：

1234

请输入集合B的元素：

34567

A=<1,2,3,4>

B=<345,6,7)

A-B=<1,2)

Pressanykeytocontinue

对称差运算

口|回

••C:\Users\Administrator\Desktop\Debug\O.exe".

六.心得体会

内容格式：宋体,五号，行间距固定值18磅

西验三二元关系的性质鉴定

一.实验目的

二元关系是离散数学中的一个重要的基本概念，定义在某一集合上的二元关系有自反

性、反自反性、对称性、反对称性和传递性，二元关系的性质是学习特殊二元关系的基础,

通过编程判断二元关系的性质，帮助同学们更好地理解二元关系相关性质定义。

二.实验原理

自反性质：设R是X集合上的二元关系，对于每一个xWX,若有xRx,则称R是自反关

系。

反自反性质：设R是X上的二元关系，对于每一个xX,有xRx,则称R有反自反的关

系。

对称性质：设R是X上的二元关系，对于每一个x,ydX。若xRy时有yRx,则称R

是对称关系。

反对称性质：设R是X集合上的二元关系，对于每一个〈x,y>GR(x*y),若<y,x

>任eR,则称R是反对称关系。

传递性质：设R为定义在集合X上的二元关系,假如对于任意的x,y,zCX,每当xRy,y

Rz时就有xRz,称关系R在X上是传递的。

三.实验内容

编程输入一个集合以及该集合上的一种二元关系，判断该二元关系具有哪些性质。

四.算法程序

内容格式:新罗马，小五号,行间距固定值18磅

#inc1ude<stdio.h>

intm,n,i,j,k；

intX[20],R[20];

voidzifan()

(

®k=0;

4or(i=0;i<m;i++)

。for(j=0；j<2*n；j=j+2)

o«if(R[j]==R|j+ll&&R[j]==X[i])k++；

f(k==m)printf("R具有自反性\n");

Af(k==0)printf(0R具有反自反性\n");

1

voidduichen()

。k=0;

4or(j=0;j<2*n；j=j+2)

for(i=0;i<2*n;i=i+2)

ggif(R[j]==R[i+l]&&R[j+l]==R[i])k++;

“f(k==n)printf("R具有对称性\n")；

if(k==0)printf("R具有反对称性\n")；

1

voidchuandi()

(

oints;

for(j=0;j<2*n;j=j+2)

(

“for(i=0；i<2*n;i=i+2)

^if(R|j4-l]==R[i])

ggk=0;

。©fbr(s=O；s<2*n；s=s+2)

aif(R(s]==R[j]&&R|s+l]==R[i+1])k++;

if(k==0)return0;

00&|

°)

oif(j==2*n)printf("R具有传递性'n");

)

intmain()

｛叩rintf("请输入集合X中的元素个数和关系R中的序偶个数:\n");

^scanf("%d%d”，&m,&n);

printf（"请输入集合X:\n"）;

0for(i=0;iVm;i++)

8scanf("%d",X+i)；

叩rintf("请输入关系R:(每两个连续输入的数是一个序偶!)\n")；

ofor(i=0；i<2*n;i++)

gscanf(”%d",R+i);

printf("集合X:\nX={")；

ofor(i=0;i<m；i++)

oprintf("％d,",X[i])；

oprintf("\b}\n^^);

printf("关系R:\nR={");

for(i=0;i<2*n：i=i+2)

-printf(H<%d,%d>,u,R[i],R[i+1])；

oprintf("\b}\n”);

zifan();

duichen()；

chuandi();

}

五.实验结果

实验结果截图大小为：宽（10cm）X高（8cm）

J・C:\Users\Administrator\De5ktop\Debug\茗学3.…、°I回.

请输入集合X巾的元素个数和关系R中的序偶个数：

24

请瑜入集合X：

12

请输入关系R：(每两个连续输入的数是一个序偶！)

12211122

集合X：

X=<1,2>

关系R：

R=<<1,2>,<2,1>,<1,1>,<2,2»

R具有同皮隹

R具有对称任

R具有*递屉

Pkessanykeytocontinue

六.心得体会

内容格式:宋体，小五号,行间距固定值18磅

实验四图的矩阵运算

一.实验目的

图形的矩阵涉及邻接矩阵、可达矩阵和关联矩阵,它们描述了一个图形节点与边之间的

关系。可达矩阵表白了图中任何两个不同的结点之间是否存在至少一条道路，以及在任何

结点处是否存在着回路。可达性矩阵是判别一个有向图是否为强连通图或弱连通图的有效

工具,通过编程实现图形的矩阵,帮助同学们掌握图形矩阵生成方法。

二.实验原理

定义设G=(V,E)是图，节点集合己编号V={vl,v2,…，vn},则G的邻接矩

阵A(G)=(aij)nxn中元素an表达为：

1若〈斗,GE

0若/E

定义设仃=(V,E)是无向图,节点集合和边集合均已编号V={h,V2,…,vj

E={e,,ez,…，eJ,则G的关联矩阵"(G)=中元素mu为

L匕是e」的起点

畋y=«-1,乙是3的终点，i=1,2,―,n;j=1,2,…，m。

0,乙与e,不关联

定义设G=(V,E)是一个〃阶的有向简朴图，£=乙}。定义矩阵

尸=(P")"X"，其中

=p,从匕至存在非零的有向道路

“一[o,其它，

称P是图G的可达矩阵。

求可达矩阵可以先构造A,A?,…,A",再构造8“=A+A?+…A”,最后运用关系

=fl,若与⑻〉0,

Pij=[0,若热⑺=0,

拟定P的元素Pu从而构造出几

显然，这种先求A,A2,A3,…,A”,8“再构造P的方法很费事。假如我们把邻接矩阵

A当作关系矩阵，那么求可达矩阵就相称于求A的传递闭包，因此可以仿照集合论中求关系

的传递闭包的办法,求可达矩阵Po

三.实验内容

通过编程，将图形的邻接矩阵、关联矩阵、可达矩阵表达出来。

四.算法程序

内容格式:新罗马，小五号,行间距固定值18磅

邻接矩阵：

#inc1ude<stdio.h>

main()

(

Eta[4][4],iJ;

ofor（i=0；i<4；i++）

。for(j=0;j<4；j++)

。。。scanf("％d”,&aEi]|j]);

or(i=0;i<4：i++)

。{

gfbr(j=0;j<4；j++)

wprintf("%d",a[i][j]);

。叩rintf("\n")；

)

for(i=0;i<4;i++)

®for(j=0;j<4；j++)

g。if(a[i][j]==a[j][i])break;

。。叩rintf("该矩阵是邻接矩阵!

}

关联矩阵：

#inelude”stdio.h”

intmain()

(

»inti,j,n,m,a[10][10]；

printf("输入该矩阵为几个点:\n”)；

oscanf("%d",&n);

叩rintf("输入该矩阵为几条边:\n")；

◎scanf("％d",&m)；

叩「intf("输入点与边之间的关系，有关系起点为1,终点为一1,没有关系为0:\n");

◎for(i=1；i<=n;i++)

叩rintf("v%d",i);

◎printf(H\n")；

®for(i=0;i<m：i++)

U

gprintf("n%d",i+1);

ofbr(j=0;j<n；j++)

scanf(”%d*,,&a[i][j]);

o}

return0;

)

可达矩阵：

#include"stdio.h"

main()

(

◎inti,j,n,m,a[10][10];

叩rintfC输入该有向矩阵为几阶简朴矩阵：\n")；

oscanf("%d",&n)；

叩rintf(”输入点与点之间的关系:\n”)；

。for(i=1;i<=n;i++)

叩rintf("v%d';i);

叩rimf("\n”)；

Or(i=0;i<n;i++)

。{

~>printf("v%d",i+1);

^fbr(j=0;j<n;j++)

scanf("%du,&a[i][j]);

ofor(i=0;i<n；i++)

®for(j=O;j<n;j++)

(

a[i][j]=1;

.if(a[i][j]!=O)

gfor(m=j;m<n;m++)

痴f(a[j][m]==1)

fta[i][m]=1;

同i][i]=1;

)

)

printf(”输出可达关系,可达为1,不可达关系为0:\n")；

»fbr(i