离散数学实验报告

实验一 命题逻辑推理

1.实验用例

根据下面的命题，试用逻辑推理方法确定谁是作案者，写出推理过程。 （1）营业员A或B偷了手表； （2）若A作案，则作案不在营业时间； （3）若B提供的证据正确，则货柜末上锁；

（4）若B提供的证据不正确，则作案发生在营业时间； （5）货柜上了锁。

2.实验目的

加深对命题逻辑推理方法的理解。

3.实验内容

用命题逻辑推理的方法解决逻辑推理问题。

4.实验原理和方法

（1）符号化上面的命题，将它们作为条件，营业员A偷了手表作为结论，得一个复合命题。

（2）将复合命题中要用到的联结词定义成C语言中的函数，用变量表示相应的命题变元。将复合命题写成一个函数表达式。

（3）函数表达式中的变量赋初值1。如果函数表达式的值为1，则结论有效， A偷了手表，否则是B偷了手表。

用命题题变元表示： A:营业员A偷了手表 B:营业员B偷了手表 C:作案不在营业时间 D:B提供的证据正确 E:货柜末上锁

则上面的命题符号化为 (A||B) && (!A||C) && (!D||E) && (D||!C) && !E 要求找到满足上面式子的变元A，B的指派便是结果。

5．实验代码

6．实验结果

B偷了手表

实验二 关系的运用

1.实验原理和方法

在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）

2．实验代码

5．实验结果

1.自反闭包

2.传递闭包

3.对称闭包

实验三 图论

1.实验用例

如下图所示的赋权图表示某七个城市 及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最小值.

2实验原理和方法

为了求解最小代价，使花费的总代价最小，这是数学中经典的求解最小耗费生成树的算法。其核心思想是寻找每一步的最优解继而求得全局最优解。 为了求得最小耗费生成树，我们运用数学中经典的Krusal算法，此算法的核心思想是：

1、 假设该图G是不连通的，对该图的边以非降序权重新排列 2、 对于排序表中的每条边，如果现在把它放入T不会形成回路的话，

则把它加入到生成树T中；否则丢弃 3、 输出最小生成树的结果，得到我们想要的答案

3.实验代码

因而最后求得的最小耗费是：此时的最小耗费是：23+1+4+9+3+17=57（万元）

实验四 最优二叉树在通信编码中的应用

1.实验内容

输入一组通信符号的使用频率，求各通信符号对应的前缀码。

2.实验原理和方法

（1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。

（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。

3．实验代码

4．实验结果