2008离散试题AB

二、选择题（共10题，每题2分，共20分） 1、下列数列中哪个可以成为无向树的度序列？( ) A、 1,1,1,1,2； B、 1,1,1,3,3； C、 1,1,1,2,2,3； D、 1,1,3,3,4 2、下列命题错误的是( ) A、? ? ? B、? ? ? C、? ? {?} D、? ? {?} 3、判断下列为双射函数的是( ) A、f：N→N，f(x) = x2 ＋ 1 B、f：Z→Z， f(x) = x mod 3 ?1f(x)??C、f：N→N， ?0若x为奇数 若x为偶数D、f：R→R，f(x) = x3 4、公式（p ? q）∧┐p的成真赋值是（ ） A、00 B、 01 C、 10 D、 11 5、无向图G如右图所示，下列对图G的判断，正确的是：( ) A、G是半哈密顿图 B、G是欧拉图 C、{e1, e2, e3}是G的边割集 D、G的点连通度为2 6、下列集合都对整除关系构成偏序集合，其中（ ）是格 A、{1, 2, 3, 4, 5} B、{1, 2, 3, 6, 9} C、{1, 2, 4, 8} D、{2, 3, 6, 12} 7、下列集合上的哪个运算是封闭并且可结合的 ( ) A、整数集合Z上的减法运算 B、非零整数集合Z*上的除法运算 C、全体n × n实矩阵上的矩阵加法运算，n ≥ 2 D、全体n × n实可逆矩阵上的矩阵减法运算，n ≥ 2 广东工业大学试卷用纸，共 3 页，第 5 页 8、公式?x(F(x) → (F(x) ∨ G(x)))是（ ）； A． 永真式 B、永假式 C、非永真式的可满足式 D、不能确定 9、A = {1, 2, 3, 4, 5, 6, 7}，R是A上的模3同余关系，则A / R = ( ) A、{{1, 2, 3}, {4, 5}, {6, 7}} B、{{1, 4, 7}, {2, 5}, {3, 6}} C、{{1, 4, 7}, {1, 5}, {1, 7}} D、{{1, 4, 7}, {2, 5}, {0, 3, 6}} 10、G??1,?1,i,?i?　,*(其中*是数的乘法运算i??1)是一个群,下列代数系统为G的子群的是(　　　　) A、<{-1}, *> B、<{i}, *> C、<{i, -i}, *> D、<{1, -1}, *> 三、(12分) 设A = ?1, 2, 3, 4?，A上二元关系R定义为：R = ??1, 2?, ?2, 1?, ?2, 3?, ?3, 4?? 求： (1) R的自反闭包 (2) R的对称闭包 (3) R的传递闭包 四、(12分) 有向图D如右图所示，求： (1) v4到v3 长度为1, 2的通路数。 (2) v3到v3 长度为4的回路数。 (3) D 中长度为3的通路数（含回路） (4) D的可达矩阵 五、(8分) 已知公式：p→(q→r)，求其主析取范式与主合取范式。 六、(8分) 证明：在代数系统中，若存在零元θ，则零元θ必唯一。 七、(10分) 在一阶谓词逻辑中构造下面推理的证明。 前提：?x(F(x) → (G(x)∧R(x)))，?xF(x)， 结论：?x(F(x) ∧ R(x))。 八、(6分) 证明：设T是n阶m条边的树，则m = n - 1。

广东工业大学试卷用纸，共 3 页，第 6 页