《离散数学》题库及答案

(1) 2 (2) 4 (3) 3 (4) 5

答：（3）

76、在有n个顶点的连通图中，其边数（ ）。

(1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条

答：（2）

77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。

(1) 5 (2) 7 (3) 8 (4) 9

答：（4）

78、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。

(1) n (2) 2n (3) n-1 (4) 2

答：（1）

79、下列哪一种图不一定是树（ ）。

(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图

答：（3）

80、连通图G是一棵树当且仅当G中（ ）。 (1) 有些边是割边 (2) 每条边都是割边

(3) 所有边都不是割边 (4) 图中存在一条欧拉路径

13

答：（2）

（数理逻辑部分）

二、求下列各公式的主析取范式和主合取范式： 1、(P→Q)?R

解：(P→Q)?R?(?P?Q )?R

?(?P?R)?(Q?R) （析取范式）

?(?P?(Q??Q)?R)?((?P?P)?Q?R)

?(?P?Q?R)?(?P??Q?R)?(?P?Q?R)?(P?Q?R) ?(?P?Q?R)?(?P??Q?R)?(P?Q?R)（主析取范式）

?((P→Q)?R)?(?P??Q??R)?(?P?Q??R)?(P??Q?R)

?(P?Q??R)?( P??Q??R)（原公式否定的主析取范式）

(P→Q)?R?(P?Q?R)?(P??Q?R)?(?P?Q??R)

?(?P??Q?R)?(?P?Q?R)（主合取范式）

2、(P?R)?(Q?R)??P

解： (P?R)?(Q?R)??P（析取范式）

?(P?(Q??Q)?R)?((P??P)?Q?R)?(?P?(Q??Q)?(R??R)) ?(P?Q?R)?(P??Q?R)?(P?Q?R)?(?P?Q?R)

?( ?P?Q?R)?( ?P?Q??R)?(?P??Q?R)?(?P??Q??R)

?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P?Q??R) ? (?P??Q?R)?(?P??Q??R) (主析取范式)

14

?（(P?R)?(Q?R)??P）

（原公式否定的主析取范式） ?(P??Q??R)?(P?Q??R）

(P?R)?(Q?R)??P ?(?P?Q?R)?(?P??Q?R)（主合取范式）

3、(?P→Q)?(R?P)

解：(?P→Q)?(R?P)

?(P?Q)?(R?P)（合取范式）

?(P?Q?(R??R))?(P?(Q??Q))?R)

?(P?Q?R)?(P?Q??R)?(P?Q?R)?(P??Q?R) ?(P?Q?R)?(P?Q??R)?(P??Q?R)（主合取范式） ?((?P→Q)?(R?P))

?(P??Q??R)?(?P?Q?R)?(?P??Q?R)?(?P?Q??R)

?(?P??Q??R)（原公式否定的主合取范式）

(?P→Q)?(R?P)

?(?P?Q?R)?(P??Q??R)?(P?Q??R)?(P??Q?R)?(P?Q?R) （主析取范式）

4、Q→(P??R)

解：Q→(P??R)

??Q?P??R（主合取范式） ?（Q→(P??R)）

?(?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(?P?Q?R)

?(P??Q?R)?(P?Q??R)?(P?Q?R）（原公式否定的主合取范式）

Q→(P??R)

15

?(P?Q?R)?(P?Q??R)?(P??Q?R)?(P??Q??R)?(?P?Q??R)

?(?P??Q?R)?(?P??Q??R）（主析取范式）

5、P→(P?(Q→P))

解：P→(P?(Q→P))

??P?(P?(?Q?P)) ??P?P ? T (主合取范式)

?(?P??Q)?(?P?Q)?(P??Q)?(P?Q)（主析取范式）

6、?(P→Q)?(R?P)

解： ?(P→Q)?(R?P)??(?P?Q)?(R?P)

?(P??Q)?(R?P)（析取范式） ?(P??Q?(R??R))?(P?(?Q?Q)?R)

?(P??Q?R)?(P??Q??R)?(P??Q?R)?(P?Q?R) ?(P??Q?R)?(P??Q??R)?(P?Q?R)（主析取范式） ?(?(P→Q)?(R?P))?(P?Q??R)?(?P?Q?R)?(?P??Q?R)

? (?P??Q??R)?(?P?Q??R)（原公式否定的主析取范式）

?(P→Q)?(R?P)?(?P??Q?R)?(P??Q??R)?(P?Q??R)

?(P?Q?R)?(P??Q?R)（主合取范式）

7、P?(P→Q)

解：P?(P→Q)?P?(?P?Q)?(P??P)?Q

?T(主合取范式)

?(?P??Q)?(?P?Q)?(P??Q)?(P?Q)（主析取范式）

16