单选题 （共 10 题 ），每题只有一个选项正确
在下述公式中是重言式为
$\text{A.}$ $(P \wedge Q) \rightarrow(P \vee Q)$;
$\text{B.}$ $(P \leftrightarrow Q) \leftrightarrow((P \rightarrow Q) \wedge(Q \rightarrow P))$;
$\text{C.}$ $\neg(P \rightarrow Q) \wedge Q$;
$\text{D.}$ $P \rightarrow(P \vee Q)$ 。
命题公式 $(\neg P \rightarrow Q) \rightarrow(\neg Q \vee P)$ 中极小项的个数为 ________ , 成真赋值的个数为 ________
$\text{A.}$ 0
$\text{B.}$ 1
$\text{C.}$ 2
$\text{D.}$ 3
设 $S=\{\Phi,\{1\},\{1,2\}\}$, 则 $2^S$ 有 ________ 个元素
$\text{A.}$ 3
$\text{B.}$ 6
$\text{C.}$ 7
$\text{D.}$ 8
设 $S=\{1,2,3\}$, 定义 $S \times S$ 上的等价关系
$R=\{\langle < a, b\rangle,\langle c, d\rangle \mid\langle a, b\rangle \in S \times S,\langle c, d\rangle \in S \times S, a+d=b+c\}$ 则由 $\mathrm{R}$ 产生的 $S \times S$ 上一个划分共有 ________ 个分块
$\text{A.}$ 4
$\text{B.}$ 5
$\text{C.}$ 6
$\text{D.}$ 7
设 $S=\{1,2,3\}, \mathrm{S}$ 上关系 $\mathrm{R}$ 的关系图为则 $\mathrm{R}$ 具有 ________ 性质
$\text{A.}$ 自反性、对称性、传递性;
$\text{B.}$ 反自反性、反对称性;
$\text{C.}$ 反自反性、反对称性、传递性;
$\text{D.}$ 自反性 。
设,$+ \circ$ 为普通加法和乘法, 则 ________ $ < S,+, \circ >$ 是域。
$\text{A.}$ $S=\{x \mid x=a+b \sqrt{3}, \quad a, b \in Q\}$
$\text{B.}$ $S=\{x \mid x=2 n, \quad a, b \in Z\}$
$\text{C.}$ $S=\{x \mid x=2 n+1, \quad n \in Z\}$
$\text{D.}$ $S=\{x \mid x \in Z \wedge x \geq 0\}=\mathrm{N}$ 。
下面偏序集 ________ 能构成格
$\text{A.}$ 
$\text{B.}$ 
$\text{C.}$ 
$\text{D.}$ 
在如下的有向图中, 从 $\mathrm{V}_1$ 到 $\mathrm{V}_4$ 长度为 3 的道路有 ( ) 条。
$\text{A.}$ 1
$\text{B.}$ 2
$\text{C.}$ 3
$\text{D.}$ 4
在如下各图中（ ）欧拉图
$\text{A.}$ 
$\text{B.}$ 
$\text{C.}$ 
$\text{D.}$ 
设 $\mathrm{R}$ 是实数集合, “ $\mathrm{x}$ ” 为普通乘法, 则代数系统 $ < \mathrm{R}, \times>$ 是
$\text{A.}$ 群;
$\text{B.}$ 独异点
$\text{C.}$ 半群
$\text{D.}$ 环
填空题 （共 10 题 ），请把答案直接填写在答题纸上
$\mathrm{P}$ : 你努力, $\mathrm{Q}$ : 你失败。 “除非你努力, 否则你将失败” 的翻译为 ________ ; 虽然你努力了, 但还是失败了” 的翻译为 ________
论域 $\mathrm{D}=\{1,2\}$, 指定谓词 $P$
则公式 $\forall x \exists y P(y, x)$ 真值为
设 $S=\left\{a_1, a_2, \cdots, a_8\right\}, B_i$ 是 $S$ 的子集, 则由 $B_{31}$ 所表达的子集是
设 $\mathrm{A}=\{2,3,4,5,6\}$ 上的二元关系 $R=\{\langle x, y\rangle \mid x < y \vee x$ 是质数 $\}$, 则 $\mathrm{R}=$ ________ (列举法)。
$\mathrm{R}$ 的关系矩阵 $\mathrm{M}_{\mathrm{R}}=$ ________
设 $\mathrm{A}=\{1,2,3\}$, 则 $\mathrm{A}$ 上既不是对称的又不是反对称的关系 $\mathrm{R}=$ ________ $A$ 上既是对称的又是反对称的关系 $R=$ ________
设代数系统 $ < \mathrm{A}, *>$,
其中 $\mathrm{A}=\{\mathrm{a}, \mathrm{b}, \mathrm{c}\}$,
则幺元是 ________ , 是否有幂等性 ________ ; 是否有对称性 ________
4 阶群必是 ________ 群或 ________ 群
下面偏序格是分配格的是
$\mathrm{n}$ 个结点的无向完全图 $\mathrm{K}_{\mathrm{n}}$ 的边数为 ________ , 欧拉图的充要条件是 ________
公式 $(P \vee(\neg P \wedge Q)) \wedge((\neg P \vee Q) \wedge \neg R$ 的根树表示为
解答题 （共 7 题 ），解答过程应写出必要的文字说明、证明过程或演算步骤
设 $\mathrm{R}$ 是 $\mathrm{A}$ 上一个二元关系，
$S=\{\langle a, b>|(a, b \in A) \wedge($ 对于某一个 $c \in A$, 有 $\langle a, c>\in R$ 且 $\langle c, b>\in R)\}$ 试证明若 $\mathrm{R}$是 $\mathrm{A}$ 上一个等价关系, 则 $\mathrm{S}$ 也是 $\mathrm{A}$ 上的一个等价关系。
用逻辑推理证明:所有的舞蹈者都很有风度, 王华是个学生且是个舞蹈者。因此有些学生很有风度。
若 $f: A \rightarrow B$ 是从 $\mathrm{A}$ 到 $\mathrm{B}$ 的函数, 定义一个函数 $g: B \rightarrow 2^A$ 对任意 $b \in B$ 有 $g(b)=\{x \mid(x \in A) \wedge(f(x)=b)\}$, 证明: 若 $\mathrm{f}$ 是 $\mathrm{A}$ 到 $\mathrm{B}$ 的满射, 则 $\mathrm{g}$ 是从 B 到 $2^A$ 的单射。
证明：若无向图 $\mathrm{G}$ 中只有两个奇数度结点, 则这两个结点一定连通。
设 $\mathrm{G}$ 是具有 $\mathrm{n}$ 个结点的无向简单图, 其边数 $m=\frac{1}{2}(n-1)(n-2)+2$, 则 $\mathrm{G}$ 是 Hamilton 图
设 $\left\langle\mathrm{Z}_6,{ }_{+6}>\right.$是一个群, 这里 +6 是模 6 加法, $\mathrm{Z}_6=\{[0],[1],[2],[3],[4],[5]\}$, 试求出 $\left\langle\mathrm{Z}_6,{ }_6>\right.$ 的所有子群及其相应左陪集。
权数 $1,4,9,16,25,36,49,64,81,100$ 构造一棵最优二叉树。