离散数学实验报告.doc
目 录实验一 联结词的运算实验二 根据矩阵的乘法求复合关系实验三 利用warshall算法求关系的传递闭包实验四 图的可达矩阵实现8 / 9实验一 联结词的运算一实验目的通过上机实验操作.将命题连接词运算融入到C语言的程序编写中.一方面加强对命题连接词运算的理解.另一方面通过编程实现命题连接词运算.帮助学生复习和锻炼C语言知识.将理论知识与实际操作结合.让学生更加容易理解和记忆命题连接词运算。二实验原理<1> 非运算, 符号:ù ,当P=T时 .ùP为F, 当P=F时 .ùP为T 。<2> 合取, 符号: , 当且仅当P和Q的真值同为真.命题PQ的真值才为真；否则.PQ的真值为假。<3> 析取, 符号: , 当且仅当P和Q的真值同为假.命题PQ的真值才为假；否则.PQ的真值为真。<4> 异或, 符号: , 当且仅当P和Q的真值不同时.命题PQ的真值才为真；否则.PQ的真值为真。<5> 蕴涵, 符号: , 当且仅当P为T,Q为F时.命题PQ的真值才为假；否则.PQ的真值为真。<6> 等价, 符号: , 当且仅当P,Q的真值不同时.命题PQ的真值才为假；否则.PQ的真值为真。三实验内容编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。4 算法程序#include<stdio.h>void main<>printf<"请输入P、Q的真值n">int a,b;scanf<"%d%d",&a,&b>int c,d;if<a=1> c=0;else c=1; if<b=1>d=0;else d=1; printf<"非P、Q的结果为%d.%dn",c,d>int e;if<a=1&&b=1>e=1;else e=0;printf<"合取的结果为%dn",e>int f;if<a=0&&b=0>f=0;else f=1;printf<"析取的结果为%dn",f>int g;if<a=1&&b=0>g=0;else g=1;printf<"单条件的结果为%dn",g>int h;if<a=b>h=1;else h=0;printf<"双条件的结果为%dn",h>内容格式：新罗马.五号.行间距固定值18磅五实验结果六心得体会通过编程.学会了析取、合取、单条件连接词、双条件连接词的用法。实验二 根据矩阵的乘法求复合关系一实验目的复合运算是一种重要的二元关系运算.可用于二元关系的合成.二元关系的性质判断.二元关系传递闭包的运算等方面.通过编程实现二元关系的复合运算.帮助同学们理解复合运算的过程.复合形成新的二元关系中的序偶是如何产生的。二实验原理复合运算能由两个二元关系生成一个新的二元关系。设XY<R关系>.YZ<S关系>.则称XZ<RS关系>为R和S的复合关系.并规定为：RS=<x,z>|xXzZy<yY<x,y>R<y,z>S>关系可用矩阵表示.故复合运算也可用矩阵表示。设有三个集合：X=x1,x2xm,Y=y1,y2yn,Z=z1,z2zp, .|X|=m, |Y|=n, |Z|=p,MR=aikm×n .MS=akjn×p则复合关系RS的关系矩阵为：MRS= MRMS=cij m×p 代表逻辑加.满足00=0.01=1,10=1.11=1代表逻辑乘.满足00=0.01=0,10=0.11=1三实验内容将二元关系用关系矩阵表示.通过两个关系矩阵对应行列元素先进行逻辑乘.后进行逻辑加生成新的关系矩阵中的每一个元素。新的关系矩阵所对应的二元关系就是两个二元关系复合形成的.编程实现这一复合过程。四算法程序#include <stdio.h>int main<>int a100100,b100100,c100100,i,j,k,n;printf<"请输入集合X中元素个数：">scanf<"%d",&n>printf<"请输入关系矩阵Mr的格式：n">for<i=0;i<n;i+>for<j=0;j<n;j+>scanf<"%d",&aij>printf<"请输入关系矩阵Ms的格式：n">for<i=0;i<n;i+>for<j=0;j<n;j+>scanf<"%d",&bij>for<i=0;i<n;i+>for<j=0;j<n;j+> if<aij=1>for<k=0;k<n;k+> if<bjk=1>cik=1;for<i=0;i<n;i+>for<j=0;j<n;j+>if<cij!=1>cij=0;printf<"n">printf<"关系矩阵Mr和Ms的复合运算结果是：n">for<i=0;i<n;i+>for<j=0;j<n;j+>printf<"%d ",cij>printf<"n">return 0;五实验结果实验结果截图大小为：宽10cm×高8cm六心得体会通过编程.更加深入的了解了矩阵复合运算法则。实验三 利用warshall算法求关系的传递闭包一实验目的对于一个二元关系R,它的传递闭包<t<R>>就是包含R,并且具有传递性质的最小二元关系。传递闭包在图论、数据库、编译原理、计算机形式语言中都有重要的应用。warshall算法是计算传递闭包的一种有效算法.通过编程实现warshall算法.帮助同学们更好地理解传递闭包的生成过程。二实验原理设X是含有n个元素的集合.R是X上的二元关系.则：以上计算传递闭包时需要按照复合关系定义求.这是比较麻烦的.特别当有限集合元素比较多时计算量很大。1962年Warshall提出了一个求t<R>的有效计算方法：设R是n个元素集合上的二元关系.是R的关系矩阵：第一步：置新矩阵M.；第二步：置i.；第三步：对.若M的第j行i列处为1.则对作如下计算：将M的第j行第k列元素与第i行第k列元素进行逻辑加.然后将结果送到第j行k列处.即 ；第四步：；第五步：若.转到第三步.否则停止。三实验内容将二元关系用关系矩阵表示.编程实现Warshall算法.获得二元关系传递闭包的关系矩阵。四算法程序#include <stdio.h>#include <math.h>void main<>int A1010;int n,i,j,k;printf<"输入关系矩阵的维数n<n<10>n">scanf<"%d",&n>printf<"输入n*n个数据<0 or 1>n">for<i=1;i<=n;i+>for<j=1;j<=n;j+>scanf<"%d",&Aij>if<Aij!=1&&Aij>printf<"There is an error">for<i=1;i<=n;i+>for<j=1;j<=n;j+>for<k=1;k<=n;k+>if<Aij&&<Aik|Ajk>>Aik=1;printf<"传递闭包的关系矩阵:n">for<i=1;i<=n;i+>for<j=1;j<=n;j+>printf<"%2d",Aij>printf<"n">五实验结果六心得体会通过编程.深入了解什么是Warshall算法.也加深了对传递闭包的了解。实验四 图的可达矩阵实现一实验目的可达矩阵表明了图中任何两个不同的结点之间是否存在至少一条道路.以及在任何结点处是否存在着回路。可达性矩阵是判别一个有向图是否为强连通图或弱连通图的有效工具.通过编程实现图形的可达矩阵.帮助同学们掌握可达矩阵生成方法。二实验原理定义 设G=V.E是一个n阶的有向简单图.。定义矩阵.其中称P是图G的可达矩阵。求可达矩阵可以先构造A.再构造.最后利用关系确定P的元素从而构造出P。显然.这种先求再构造P的方法很费事 。如果我们把邻接矩阵A当作关系矩阵.那么求可达矩阵就相当于求A的传递闭包.因此可以仿照集合论中求关系的传递闭包的办法.求可达矩阵P。三实验内容将图形中的边表达成二元关系.计算该二元关系的传递闭包.并将传递闭包表达成关系矩阵.该关系矩阵就是图形的可达矩阵.编程实现求可达矩阵的过程。四算法程序#include<stdio.h> #define N 4 void TransitiveClosure<int distNN,int tNN>/寻找可达矩阵 for<int i=0;i<N;i+>/进行遍历 for<int j=0;j<N;j+> if<<i=j>|<distij>=1> tij=1; else tij=0; for<int k=0;k<N;k+> for<int i=0;i<N;i+> for<int j=0;j<N;j+> tij=tij|<tik&&tkj>void main<> int i,j; int distNN=1,0,0,0, 0,1,1,1, 0,1,1,0, 1,0,1,1; printf<"邻接矩阵举例如下：n">for< i=0;i<N;i+>for< j=0;j<N;j+>printf<"%d ",distij>printf<"n"> int tNN=0; TransitiveClosure< dist, t>printf<"其对应可达矩阵如下：n"> for< i=0;i<N;i+> for< j=0;j<N;j+> printf<"%d ",tij> printf<"n"> 五实验结果六心得体会有了邻接矩阵.通过遍历.判断是否可达.通过for语句找出可达矩阵。
