离散数学复习题(2)

________个结点。

41．图G为有n个结点、m条边的简单图，结点v的度数为k，e为G的一条边。

(1)G-v中有________个结点和________条边； (2)G-e中有________个结点和________条边。

42．设有向图D=，V={v1,v2,…vn},A(D)=(aij)n×n为的邻接矩阵，则

(1)D中结点vi的出度记作________，vi的入度记作________，vi的度数为________

(2)D中所有结点的出度之和为________，所有结点入度之和为________，所有度数之和为________。 43．设有向图D=， (1)已知邻接矩阵

?0?1A(D)???0??0001?000?? 100??010?则P(D)=________，D的图形为________。 (2) 已知邻接矩阵

?0?1A(D)???0??0001?010?? 000??010?则P(D)=________，D的图形为________。 (3) 已知邻接矩阵

?0?1A(D)???0??1000?010?? 000??010?则P(D)=________，D的图形为________。 44．n=________，无向完全图Kn是欧拉图；

n=________，无向完全图Kn仅存在欧拉通路而不存在欧拉回路。

45．构造一个欧拉图，其结点数和边数满足：?V?,?E?的奇偶性一样的图为________；?V?,?E?的相反的图为_______. 46．给定平面图如图G所示，则G的面数为________。 47．若连通平面图有4个结点,3个面，则它有_____条边。 48．无向完全图Kn，仅当n________时是平面图。 49．设A为非空集合，映射________，称为集合A上的二元运算。

50．非空集合A上的二元运算?，满足________，则称运算?是可交换的；满足________，则称运算?是可结合的。 51．e称为集合A上的二元运算?的单位元，则e既是________，又是________，即________。 52．把置换??123456?表示成互不相交轮换或对换??463125?的积是________，??123456?表示成互不相交轮换??326154?或对换的积是________。

53．设四元置换???，??1?________。 ??2314?54．代数系统同构具有________性和________性。 55．在环中，(a?b)3?________________________。 56．设(G，+，?)是环，若________运算满足________，则称(G，+，?)是交换环。

57．集合L上的两个二元运算∧和∨满足________律、________律和________律。则(L，∧，∨)是格。 58．在布尔代数中，有a?(a?b)?a?b，则其对偶式________成立。

59．设(L，gcd，lcm，0，1)是有界格，a是L中的一个元素，如果存在b使得________,________，则称b是a的余元素。

60．?设(B，+，?，0，1)是布尔代数，?a,b,c?B,则

(a?b)?(a?b?c)?(a?b?c)?(a?b?c)?________________.

?1234?二． 选择题：

1.下面联结词不具有交换律的是( )

(A)? (B) ? (C) ? (D)? 2.下面语句是真命题的为( )

(A) 我正在说谎 (B) (B)如果1+2=3,则雪是黑色的 (C) 如果1+2=5,则雪是黑色的 (D) 上网了吗?

3.下列联结词集合中,最小联结词组是( ) (A){?, ?} (B) {?,?} (C) {? } (D){ ?,?} 4.命题公式(P?(P?Q))?Q是( )

(A)矛盾式 (B) 蕴含式 (C) 重言式 (D)等价式 5.下列命题公式中,( )是重言式. (A)(P?Q) ?(Q?P) (B) (P?Q) ?P

(C) ?(P?Q) (D) (?P?Q)??(?P??Q) 6下列命题公式中,( )不是重言式.

(A)Q? (P?Q) (B) (P?Q) ?P (C)?(P??Q)?(?P?Q) (D) (?P?Q)?(P?Q) 7.重言式的否定为( )

(A) 重言式 (B) 矛盾式 (C)可满足式 (D) 蕴含式 8.命题公式P?(Q?P)为( )

(A) 重言式 (B) 可满足式 (C) 矛盾式 (D) 等值式

9.设A(x):x是人,B(x):x犯错误.命题“没有不犯错误的人”可以符号化为( )

(A)?x(A(x) ?B(X)) (B) ??x(A(x) ??B(x)) (C) ??x(A(x)?B(X)) (D) ??x(A(x)? ?B(X)) 10.设L(x):x是演员,J(x):x是教师,A(x,y):x佩服y,命题“所有演员都佩服某些教师”可以符号化为( ) (A)?x L(x) ??A(x,y) (B) ?x( L(x) ??y(J(y)?A(x,y)))

(C) ?x?y(L(x)?J(y)?A(x,y)) (D) ?x?y(L(x)?J(y)?A(x,y))

11.谓词公式?xP(x)??y? P(y)是( )

(A) 可满足式 (B)永真式 (C) 永假式 12. ?x(A(x)?B(x))与?xA(x)? ?x B(x)是

(A) 等价的 (B) 蕴含的 (C)重言蕴含的 13.设集合A={2,a,{3},4},那么下列命题中错误的是( ) (A){a}?A (B){a,4,{3}}?A (C) {a}?A (D)??A

14.设集合B={2,{a},3,4,2},那么下列命题中错误的是( )

(A){a}?B (B){2,{a},3,4,}?B (C) {a}?B (D){ }?B 15.设集合A={1,a},则2A=( )