当前位置:首页 >> IT/计算机 >> 安徽大学2005-2006学年第二学期《离散数学》期末考试试卷(A卷)

安徽大学2005-2006学年第二学期《离散数学》期末考试试卷(A卷)


2005安徽大学 2005-2006 学年第二学期 离散数学》期末考试试卷( 《离散数学》期末考试试卷(A 卷)
一、选择题(每小题 2 分,共 20 分) 1.在自然数集 N 上,下列运算中可结合的是( A. a * b = a b B. a * b = max{a, b} C. a * b = a + 2b D. a * b = a b )

2.二元运算*有两个左零元,则*一定( ) A.满足结合律 B.满足交换律 C.不满足结合律 D.不满足交换律 3.设 < A,* > 是二元代数系统,元素 a ∈ A 有左逆元 a l1 和右逆元 a r1 ,若运算*满 足( )律,则 a l1 = a r1 。 A.结合 B.交换 C.等幂 D.分配 4.下列代数 < S ,* > 中, ( )是群。 A. S = {0,1, ,3,5} ,*是模 7 加法 B. S = Q (有理数集) ,*是普通乘 法 C. S = Z (整数集合) ,*是一般减法 D. S = {1,3,4,5,9} ,*是模 11 乘法 )子群。 5.群 < N 12 ,+ 12 > 总共有( A.4 B.6 C.8 D.12 6.下面( )集合关于指定的运算构成环。 3 A. {a + b 2} | a, b ∈ Z } ,关于数的加法和乘法 B. {n 阶实数矩阵 } ,关于矩阵的加法和乘法 C. {a + b 2} | a, b ∈ Z } ,关于数的加法和乘法
a b D. b a a, b ∈ Z ,关于矩阵的加法和乘法 7.N 是自然数集, ≤ 是小于等于关系,则 < N , ≤> 是( ) A.有界格 B.有补格 C.分配格 D.有补分配格 8.在布尔格 < B,*,⊕, ' ,0,1 > 中有 3 个原子 a1 , a 2 , a3 ,则 a1' = (



A. a 2 * a 3

B. a 2 ⊕ a 3

C. a * a
' 2

' 3

D. a ⊕ a
' 2

' 3

9.含有 5 个结点、3 条边的不同构的简单图有( ) A.2 个 B.3 个 C.4 个 D.5 个 10.一个无向图有 4 个结点,其中 3 个度数为 2,3,3,则第 4 个结点度数不可能 是( ) A.0 B.1 C.2 D.4 二、填空题(每空 2 分,共 20 分) 1 1 . 设 < G,× > 为 非 零 实 数 乘 法 群 , f : G → G 是 同 态 映 射 , f ( x) = , 则 x f (G ) = ________, Ker ( f ) = ________。

1

2.设 H = {0,4,8} , < H ,+12 > 是群 < N 12 ,+ 12 > 的子群,其中 N 12 = {0,1,2,...,11} , +12 是 模 12 加 法 , 则 < N 12 ,+ 12 > 有 ________ 个 真 子 群 , H 的 左 培 集 3H = ____________, 4 H = ____________。 3.在有界分配格中,具有补元的元素集合组成一个______格。 无向完全图 K n 是欧拉图;n = ________时, 无向完全图 K n 4.n 为________数时, 仅存在欧拉路径而不存在欧拉回路。 5. 一棵树有 2 个 2 度结点, 个 3 度结点, 个 4 度结点, 1 3 则其 1 度结点数为________。 6.无向图 G 是有 k ( k ≥ 2 )棵树组成的森林,至少要添加_______条边才能使 G 成为一棵树。 三、综合题(每小题 10 分,共 60 分) 1 . 设 < G,* > 是 一 个 群 , 证 明 : 对 于 G 中 任 意 的 a, b, c, d , a1 , b1 , c1 , d1 , 如 果 a * c = a1 * c1 , a * d = a1 * d1 , b * c = b1 * c1 。则有 b * d = b1 * d1 。

2 . 设 < A,* > 和 < B, > 是 两 个 群 。 < A,* > 和 < B, > 的 笛 卡 尔 积 是 代 数 系 统 < A × B, > , 其中 是一个二元运算, 使得对 A × B 中的任意 < a1 , b1 > 和 < a2 , b2 > , 有 < a1 , b1 > < a 2 , b2 >=< a1 * a 2 , b1 b2 > 。证明: < A × B, > 也是一个群。

3.设 < G,* > 是一个群。令 H = {a | a ∈ G, 且对一切 b ∈ G ,有 a * b = b * a} 。证明: H 是一个正规子群。

4.设 < L, ≤> 为一个格,试证明: < L, ≤> 为分配格的充要条件是对于任意的 a, b, c ∈ L ,有 (a ⊕ b) * c ≤ a ⊕ (b * c) 。

5.下列是布尔代数 < {0,1, a, b},*,⊕, ' ,0,1 > 上的布尔表达式,试求出它们的主析取 范式和主合取范式: (1) f ( x, y ) = (b * ( x ⊕ y )) ⊕ ( x * y ) 。 (2) f ( x, y, z ) = (a * x * y ) ⊕ (b * z ) 。 6.证明 (1)设 G 是具有 n 个结点的无向简单图, 其边数 m =
1 (n 1)(n 2) + 2 。 试证明 G 2

是哈密尔顿图。 (2)设简单平面图 G 中结点数 n = 7 ,边数 m = 15 ,证明: G 是连通的。

2

2005安徽大学 2005-2006 学年第二学期 离散数学》期末考试试卷( 卷答案) 《离散数学》期末考试试卷(A 卷答案) 一、选择题(2 × 10=20 分) B,D,A,D,B,C,C,B,C,B 二、填空题(每空 2 分,总 2 × 10=20 分) 1. G , {1} 2.4, {3,7,11} , {0,4,8} 3.子 4.奇,2 5.9 6. k 1 三、综合题(每小题 10 分,总 6 × 10=60 分) 1.证明:因为 < G ,* > 是一个群,则 x, y ∈ G ,有 ( x * y ) 1 = y 1 * x 1 (1 分) x * x 1 = e (1 分) 。所以, b * d = b * (c * c 1 ) * (a 1 * a ) * d (2 分) = (b * c) * (c 1 * a 1 ) * (a * d ) = (b1 * c1 ) * (a * c) 1 * (a1 * d 1 ) = (b1 * c1 ) * (a1 * c1 ) 1 * (a1 * d 1 ) = (b1 * c1 ) * (c1 * a1 ) * (a1 * d 1 ) = b1 * (c1 * c1 1 ) * ( a1 1 * a1 ) * d1 = b1 * d1
1 1

(1 分) (1 分) (1 分) (1 分) (1 分) (1 分)

2.证明: (1)由*, 运算的封闭性,可知 运算的封闭性。 分) (1 (1 (2)由*, 运算的结合性,可知 运算的结合性。 分) (3)设 e A , e B 分别是 A 和 B 的幺元。因为 < a, b > < e A , eB >=< a * e A , b eB >=< a, b > < e A , eB > < a, b >=< e A * a, eB b >=< a, b > 所以, < e A , eB > 是代数系统 < A × B, > 的幺元。 分) (4 (4)设 A × B 中任一元素 < a, b > ,因为 < a, b > < a 1 , b 1 >=< a * a 1 , b b 1 >=< e A , e B > < a 1 , b 1 > < a, b >=< a 1 * a, b 1 b >=< e A , e B > 所以, < a, b > 的逆元是 < a 1 ,b 1 > 。 分) (4 综上所述, < A × B, > 构成群。 3.证明:先证 < H ,* > 是一个子群。对于 H 中任意元素 a 和 c ,对一切 b ∈ G ,有 a * b = b * a , c * b = b * c ,即 c 1 * b = b * c 1 。 分)所以,对一切 b ∈ G ,有 (2 1 1 ( a * c ) * b = a * (c * b ) (2 分) 1 = a * (b * c ) (1 分) 1 = ( a * b) * c (1 分)

3

= (b * a ) * c 1

(1 分)

= b * (a * c 1 ) (1 分) 1 所以, a * c ∈ H ,故 < H ,* > 是一个子群。 对 G 中任一元素 b 和 H 中任一元素 a ,有 a * b = b * a ,所以 H * b = b * H , (2 则 H 为正规子群。 分) 4.证明:设 < L, ≤> 是分配格。由 a * c ≤ a , (b * c ) ≤ (b * c ) ,可得 ( a * c ) ⊕ (b * c ) ≤ a ⊕ (b * c ) ,而 ( a ⊕ b) * c = ( a * c ) ⊕ (b * c ) 所以 ( a ⊕ b) * c ≤ a ⊕ (b * c ) 。 分) (4 反之,若对于任意的 a, b, c ∈ L ,有 ( a ⊕ b) * c ≤ a ⊕ (b * c ) ,则可得 ( a ⊕ b) * c = ((b ⊕ a ) * c ) * c 由已知条件 ≤ (b ⊕ (a * c )) * c = ((a * c ) ⊕ b) * c 由已知条件 (4 分) ≤ ( a * c ) ⊕ (b * c ) 又由 a * c ≤ ( a ⊕ b) * c 和 b * c ≤ ( a ⊕ b) * c ,可得 ( a * c ) ⊕ (b * c ) ≤ ( a ⊕ b ) * c (2 分) 于是有 ( a ⊕ b) * c = ( a * c ) ⊕ (b * c ) 5.解 (1) f ( x, y ) = (b * ( x ⊕ y )) ⊕ ( x ⊕ y ) = (b * x ) ⊕ (b * y ) ⊕ ( x * y ) = (b * x * ( y ⊕ y ' )) ⊕ (b * ( x ⊕ x ' ) * y ) ⊕ ( x * y ) = (b * x * y ) ⊕ (b * x * y ' ) ⊕ (b * x * y ) ⊕ (b * x ' * y ) ⊕ ( x * y ) = ( x * y ) ⊕ (b * x * y ' ) ⊕ (b * x ' * y ) (主析取范式,3 分) f ( x, y ) = (b * ( x ⊕ y )) ⊕ ( x ⊕ y ) = (b ⊕ ( x * y )) * (( x ⊕ y ) ⊕ ( x * y )) = (b ⊕ x) * (b ⊕ y ) * ( x ⊕ y ) = (b ⊕ x ⊕ ( y * y ' )) * (b ⊕ ( x * x ' ) ⊕ y ) * ( x ⊕ y ) = (b ⊕ x ⊕ y ) * (b ⊕ x ⊕ y ' ) * (b ⊕ x ⊕ y ) * (b ⊕ x ' ⊕ y ) * ( x ⊕ y ) = ( x ⊕ y ) * (b ⊕ x ⊕ y ' ) * (b ⊕ x ' ⊕ y ) (主合取范式,2 分) (2) f ( x, y , z ) = ( a * x * y ) ⊕ (b * z ) = (a * x * y * ( z ⊕ z ' )) ⊕ (b * ( x ⊕ x ' ) * ( y ⊕ y ' ) * z ) = (a * x * y * z ) ⊕ (a * x * y * z ' )) ⊕ (b * x * ( y ⊕ y ' ) * z ) ⊕ (b * x ' * ( y ⊕ y ' ) * z ) = (a * x * y * z ) ⊕ (a * x * y * z ' )) ⊕ (b * x * y * z ) ⊕ (b * x * y ' * z ) ⊕ (b * x ' * y * z ) ⊕ (b * x ' * y ' * z ) = ( x * y * z ) ⊕ (a * x * y * z ' )) ⊕ (b * x * y ' * z ) ⊕ (b * x ' * y * z ) ⊕ (b * x ' * y ' * z ) (主析取范式,3 分) f ( x, y , z ) = ( a * x * y ) ⊕ (b * z ) = ( a ⊕ b) * (a ⊕ z ) * ( x ⊕ b) * ( x ⊕ z ) * ( y ⊕ b) * ( y ⊕ z ) = (a ⊕ ( x * x ' ) ⊕ ( y * y ' ) ⊕ z ) * (b ⊕ x ⊕ ( y * y ' ) ⊕ ( z * z ' )) * ( x ⊕ ( y * y ' ) ⊕ z ) * (b ⊕ ( x * x ' ) ⊕ y ⊕ ( z * z ' )) * (( x * x ' ) ⊕ y ⊕ z )
4

= (a ⊕ x ⊕ y ⊕ z ) * (a ⊕ x ⊕ y ' ⊕ z ) * (a ⊕ x ' ⊕ y ⊕ z ) * (a ⊕ x ' ⊕ y ' ⊕ z ) * (b ⊕ x ⊕ y ⊕ z ) * (b ⊕ x ⊕ y ⊕ z ' ) * (b ⊕ x ⊕ y ' ⊕ z ) * (b ⊕ x ⊕ y ' ⊕ z ' ) * ( x ⊕ y ⊕ z ) * ( x ⊕ y ' ⊕ z ) * (b ⊕ x ⊕ y ⊕ z ) * (b ⊕ x ⊕ y ⊕ z ' ) * (b ⊕ x ' ⊕ y ⊕ z ) * (b ⊕ x ' ⊕ y ⊕ z ' ) * ( x ⊕ y ⊕ z ) * ( x ' ⊕ y ⊕ z ) = ( x ⊕ y ⊕ z ) * ( x ⊕ y ' ⊕ z ) * ( x ' ⊕ y ⊕ z ) * (a ⊕ x ' ⊕ y ' ⊕ z ) * (b ⊕ x ⊕ y ⊕ z ' ) * (b ⊕ x ⊕ y ' ⊕ z ' ) * (b ⊕ x ' ⊕ y ⊕ z ' ) (主合取范式,2 分) (也可列表求权值 f ( x, y ) , x, y ∈ {0,1} ,然后直接写出范式) 6.(1)证明:证明 G 中任何两个不相邻的结点的度数之和均大于等于 n 。否则存 在两个结点的简单图,且 deg( u ) + deg( v) ≤ n 1 。令 V1 = {u, v} ,G1 = G V1 ,则 G1 1 是 具 有 n 2 个 结 点 简 单 图 , 它 的 边 数 m ' ≥ ( n 1)( n 2) + 2 ( n 1) , 可 得 2 1 m ' ≥ ( n 2)( n 3) + 1 ,这与 G1 为 n 2 个结点简单图矛盾,因而 G 中任何两个不 2 相邻的结点的度数之和均大于等于 n 。 (同理可证,任何相邻结点的度数之和均大 于等于 n 。 )故 G 是哈密尔顿图。 分) (5 (2) 证明: (反证法) G 为非连通的, 设 具有 ω ≥ 2 个连通分支 G1 , G2 ,..., Gω 。 Gi 设 的结点数为 ni ,边数为 mi , i = 1,2,..., ω 。 若存在 n j = 1 ,则 ω 必为 2,因为只有此时 G 为一个平凡图并上一个 K 6 才能 使其边数为 15,可是 K 6 不是平面图,这矛盾于 G 为平面图这个事实,所以不存 在 n j = 1 。 分) (1 若存在 n j = 2 , G j 中至多有一条边(简单图) ,另外 5 个结点构成 K 5 时边数 最多,但其值也仅为 10 条边,这与 G 有 15 条边矛盾。 分) (2 综上所述, ni 必大于等于 3, i = 1,2,..., ω 。由简单平面图可得:
mi ≤ 3ni 6 , i = 1,2,..., ω

求和得: m ≤ 3n 6ω 。将 n = 7 , m = 15 代入得:15 ≤ 21 6ω ω ≤ 1 。这与 ω ≥ 2 矛盾。故 G 必为连通图。 分) (3

5


赞助商链接
更多相关文档:

安徽大学2004-2005学年第一学期离散数学期末试卷

安徽大学 2004-2005 学年第学期 《离散数学》期末考试试卷(A 卷) 离散数学》期末考试试卷(年级 大登项分一 专业 二三 姓名 四五 学号 六七 座位号 ---...

安徽大学离散数学(上)试卷及参考答案

安徽大学 20 09 — 20 10 学年第 1 学期 《 离散数学 》考试试卷(A 卷)(时间 120 分钟)院/系 专业 姓名 学号 题得 号分 一 二 三 四 五 六 七 ...

安徽大学2010-2011《离散数学下》试卷A及答案

安徽大学2010-2011《离散数学下》试卷A及答案_工学_高等教育_教育专区。安徽大学...2 安徽大学 20 10 —20 11 学年第 2 学期 《 离散数学(下) 》(A卷)...

安徽大学 2012-2013年度 第二学期《离散数学下》试卷

安徽大学 2012 —2013 学年第 2 学期答 题勿超装订线 ---装---...《 离散数学(下) 》考试试卷(A 卷)(闭卷 时间 120 分钟) 考场登记表序号题 号得分...

安徽大学__2011-2012年《离散数学下》试卷B

学年第 2 学期 《 离散数学(下) 》考试试卷(B 卷)(闭卷 时间 120 分钟)...GCD( x, y) ; 4.六阶群的子群的阶数可以是( A.1,2,5; C.3,6,7...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com