《离散数学》实验报告专业班级姓名学号授课教师二 O 一六年十二月目录实验一联结词的运算实验二根据矩阵的乘法求复合关系实验三利用算法求关系的传递闭包实验四图的可达矩阵实现实验一联结词的运算一．实验目的通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。

二．实验原理(1) 非运算, 符号: ,当时，P为F, 当时，P为T 。

(2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。

(3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。

(4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。

(5) 蕴涵, 符号: → , 当且仅当P为为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。

(6) 等价, 符号: ↔, 当且仅当的真值不同时，命题P↔Q的真值才为假；否则，P→Q 的真值为真。

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

四．算法程序<>(){;("请选择运算方式\n");("1.析取\n");("2.合取\n");("3.非\n");("4.蕴含\n");("5.等价\n");m;("");( m>=1 m<=4 ){("请输入P Q的值\n");(" " );= 1;(m){1( ( >= 1)( < 4 ) ){(0 0)("P 析取Q = 0\n");("P 析取Q = 1\n");;(4) ;("请输入P Q的值\n");(" " );};2( ( >= 0)( < 4 ) ){(1 1)("P 合取Q = 1\n");("P 合取Q = 0\n");;(4) ;("请输入P Q的值\n");(" " );};3( ( >= 0)( < 4 ) ){(0) ("非Q = 1\n");("非Q = 0\n");(0) ("非P = 1\n");("非P = 0\n");;(4) ;("请输入P Q的值\n");(" " );};4( ( >= 0)( < 4 ) ){( 1 (0 0))("P 蕴含Q = 1\n");(1 0)("P 蕴含Q = 0\n");;(4) ;("请输入P Q的值\n");(" " );};5( ( >= 0)( < 4 ) ){()("P 等价Q = 1\n");("P 等价Q = 0\n");;(4) ;("请输入P Q的值\n");(" " );};}("请重新选择运算方式\n");("");}0;}五．实验结果六．心得体会通过将命题连接词运算融入到程序编写中，既加强我对命题连接词运算的理解，又通过编程实现命题连接词运算帮助我复习C语言知识，通过设计算法可以使得数学中逻辑算法用程序来实现，这样只要借助计算机的程序就可以很方便的将一些复杂的逻辑运算轻松地解决。

主函数中设计的代码虽然代码过长，但是结构明显，但是可以拆分为一个菜单函数，和一个指令输入函数，这样整体的机构更加简洁，方便代码的维护。

实验二根据矩阵的乘法求复合关系一．实验目的复合运算是一种重要的二元关系运算，可用于二元关系的合成，二元关系的性质判断，二元关系传递闭包的运算等方面，通过编程实现二元关系的复合运算，帮助同学们理解复合运算的过程，复合形成新的二元关系中的序偶是如何产生的。

二．实验原理复合运算能由两个二元关系生成一个新的二元关系。

设X →Y(R 关系)，Y →Z(S 关系)，则称X →Z(R ◦S 关系)为R 和S 的复合关系，并规定为：R ◦{<>∈X ∧z ∈Z ∧∃y(y ∈Y ∧<>∈R ∧<>∈S)}关系可用矩阵表示，故复合运算也可用矩阵表示。

设有三个集合：{x 12…}{y 12…}{z 12…},Z Y X S R −→−−→−，, , []m ×n ，[]n ×p 则复合关系R ◦S 的关系矩阵为：◦ ◦[] m ×p )(1kjik nk ij b a c ∧=∨=∨代表逻辑加，满足0∨0=0，0∨1=1,1∨0=1，1∨1=1 ∧代表逻辑乘，满足0∧0=0，0∧1=0,1∧0=0，1∧1=1三．实验内容将二元关系用关系矩阵表示，通过两个关系矩阵对应行列元素先进行逻辑乘，后进行逻辑加生成新的关系矩阵中的每一个元素。

新的关系矩阵所对应的二元关系就是两个二元关系复合形成的，编程实现这一复合过程。

四．算法程序<> N 100 () { ;("请输入的值："); (" ", , ); ;R[N][N][N][N]; ("输入R 的序偶:\n"); (0<) (0<){( "", [i][j]);(R[i][j]0 R[i][j]1)R[i][j] = 0;}("输入S的序偶:\n");(0<)(0<){("", [j][s]);(S[j][s]0 S[j][s]1)S[j][s] = 0;}[N][N];(0<)(0<){= 0;(0<){R[i][j] * S[j][s];( 0)[i][s] = 1;[i][s] = 0;}}("R的矩阵是:\n");(0<){(0<)(" " [i][j]);( "\n");}("S的矩阵是:\n");(0<){(0<)(" " [i][s]);("\n");}("R复合S结果为:\n");(0<){(0<)(" "[i][s]);("\n");}0;}五．实验结果六．心得体会利用算法的兼容性使算法优化实现计算多维矩阵的复合运算，避免键盘输入产生的其他数值，影响代码结果的正确性。

实验三利用算法求关系的传递闭包一．实验目的对于一个二元关系R,它的传递闭包(t(R))就是包含R,并且具有传递性质的最小二元关系。

传递闭包在图论、数据库、编译原理、计算机形式语言中都有重要的应用。

算法是计算传递闭包的一种有效算法，通过编程实现算法，帮助同学们更好地理解传递闭包的生成过程。

二．实验原理设X 是含有n 个元素的集合，R 是X 上的二元关系，则： 23()n t R R R R R =以上计算传递闭包时需要按照复合关系定义求iR ，这是比较麻烦的，特别当有限集合元素比较多时计算量很大。

1962年提出了一个求t(R)的有效计算方法：设R 是n 个元素集合上的二元关系，R M 是R 的关系矩阵： 第一步：置新矩阵M ，R M M ←； 第二步：置i ，1←i ；第三步：对)1(n j j ≤≤，若M 的第j 行i 列处为1，则对n k ,,2,1 =作如下计算： 将M 的第j 行第k 列元素与第i 行第k 列元素进行逻辑加，然后将结果送到第j 行k 列处，即 ],[],[],[k i M k j M k j M ∨←； 第四步：1+←i i ；第五步：若n i ≤，转到第三步，否则停止。

三．实验内容将二元关系用关系矩阵表示，编程实现算法，获得二元关系传递闭包的关系矩阵。

四．算法程序<>N 10( y){1;(00)0;a;}(){[N][N] ;M[N][N];;("请输入关系矩阵的阶数:\n");("");("请输入关系矩阵* :\n");(0<)(0<){(""[i][j]);( [i][j]0 [i][j]1 )[i][j] = 0;M[i][j] = [i][j];}i = 0;(i<n){(0<)(M[j][i]1)(0<)M[j][k] = (M[j][k][i][k]);;}( "关系矩阵为:\n");(0<){(0<)(" " [i][j] );("\n");}("结果为:\n");(0<){(0<)(" "[i][j]);("\n");}0;}五．实验结果六．心得体会数组和循环嵌套可以使得数学中逻辑算法用程序来实现，通过编写矩阵的传递闭包算更加深刻的理解了算法的计算原理。

对于输出的闭包关系中每对序偶输入时用空格隔开，行末用回车结束。

实验四图的可达矩阵实现一．实验目的可达矩阵表明了图中任何两个不同的结点之间是否存在至少一条道路，以及在任何结点处是否存在着回路。

可达性矩阵是判别一个有向图是否为强连通图或弱连通图的有效工具，通过编程实现图形的可达矩阵，帮助同学们掌握可达矩阵生成方法。

二．实验原理定义 设（V ，E ）是一个n 阶的有向简单图，{}n v v v V ,,,21 =。

定义矩阵n n j i p P ⨯=)(，其中⎩⎨⎧=，，v v p j i ij 其它存在非零的有向道路到从,0,1称P 是图G 的可达矩阵。

求可达矩阵可以先构造A ，nA A ,,2 ，再构造n n A A AB ++=2，最后利用关系⎪⎩⎪⎨⎧=>=，b ，b p n tj n ij ij 0,00,1)()(若若 确定P 的元素ij p 从而构造出P 。