离散数学2009年4月考试真题（02324）

今有n个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明：

(1)当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边(或右边)的人的朋友。

(2)当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友。

构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。

证明：边e是图G的一条割边，当且仅当图G中不存在包含边e的简单回路。

R是集合A上自反和传递的关系，试证明：

在整数集Z上定义：是一个群。

设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画的哈斯图，并求A中的最大元、最小元、极大元、极小元。

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

已知A={{}，{?，1}}，B={{，1}，{1}}，计算A∪B，A⊕B，A的幂集P(A)。

下图给出了一个有向图。

(1)求出它的邻接矩阵A;(2)求出A²，A³，A⁴及可达矩阵P。

构造命题公式的真值表。