离散数学复习题

命题逻辑：

1、 求公式q∧(p∨┐q)的主析取范式(m3)、主合取

范式(M0 M1 M2)。

求下列公式的主合取范式和主析取范式：

((?P?Q)?R) 合取

M0/M2/M6 析取m1.m3.m4.m5.m7

求公式A=p→((p→q)∧┐(┐q∨┐p))的主析取范式m3,并判断其类型？可满足式

2、将下列命题符号化： 1)、没有不犯错误的人。 2)、凡人都呼吸

3）、有的韶关市民没有去过南华寺。

证明:

1 、R??Q，R?S，S??Q，P?Q??P 2、P?Q，P?R，Q?S?R?S

2、构造下面命题推理的证明

如果我学习，那么我数学不会不及格；如果我不热衷于玩游戏机，那么我将学习；但我数学不及格，因此我热衷与玩游戏机。 3、构造下面命题推理的证明

如果今天是星期三，那么我有一次英语或数学测

验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。

4 已知张三或李四的彩票中奖，如果张三中奖，你是会知道的；如果李四中奖，王五也中奖了；现在你不知道张三中奖。试用逻辑推理来确定谁中奖了？ 并写出推理过程。

解 设P：张三中奖。Q：李四中奖。R：王五中奖。

S：你知道张三中奖。由题设得已知条件：P?Q，P?S，

Q?R，?S。则推理如下：

（1）?S P （2）P?S P （3）?P?S

T(2)E T(1)(3)I（4）?P （6）Q （7）Q?R P （8）R （9）Q?R

（5）P?Q P

T(4)(5)IT(6)(7)IT(6)(8)I

即李四和王五都中奖了。

三、图论与树：

1、画出满足下列要求的图。

①有一条欧拉回路和一条汉密尔顿回路。 ②有一条欧拉回路但没有汉密尔顿回路。 ③没有欧拉回路但有汉密尔顿回路。 ④既没有欧拉回路也没有汉密尔顿回路。

2、对下图给出的有向图G:

v1 v2 v3

计算它的邻接矩阵A及A2，A3，A4，说出从v1到v4的长度为l，2，3，4的拟路径各有多少条。

3、一棵树有n个结点度数为2 ，n个结点度数为3，? ，n个结点度数为k ，问它有几个度数为1的结点。(2+n3+?+(k-2)nk)

23kv4 v5 图

4、对于下图，利用克鲁斯克尔算法求一棵最小生成树。

5、求带权2、3、5、7、11、13的最优二叉树。 求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

6、用二叉树表示命题公式(P?(?P?Q))?((?P?Q)??R)。 6、求算式: ((a+(b?c)*d)-e)?(f+ g)的树形表示？

7画出结点数为5的所有不同构的无向树。

8、用中序、前序、后序三种行遍法，写出下图所示二叉树的有关算法。

9、（10分）已知：D=，V={1，2，3，4，5}，E={<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>}，求D的邻接距阵A和可达距阵P。

10有向图G如图所示，试求：

(1)求G的邻接矩阵A。 (2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？ (3)求出可达矩阵P。

11六名间谍a,b,c,d,e,f被擒，已知a懂汉语、法语和日语，

b懂德语、俄语和日语，c懂英语和法语，d懂西班牙

语，e懂英语和德语，f懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。

本文来源：https://www.bwwdw.com/article/0n1d.html