离散数学试题库10

一、选择题

1、由n 个命题变元组成不等值的命题公式的个数为()

A.2n

B.2n

C.n 2 D .2n

2

2、“所有的人都是要死的。苏格拉底是人,所以苏格拉底是要死的。”则该句话( )

A .不是命题

B .是真命题

C .是假命题

D .是悖论

3、若P 表示“他聪明”,Q 表示“他用功”,则“他聪明但不用功”可符号化为( )

A .P ∨Q

B .P ∧?Q

C .P →?Q

D .P ∨?Q

4、若p 表示“天下雨”,q 表示“他乘车上班”,则“只有天下大雨,他才乘车上班”可符号化为( )

A .p →q

B .q →p

C .p →?q

D .?q →p

5、下列命题公式中,为永假式的是( )。

A .P →(P ∨Q ∨R )

B .(P →?P )→?P

C .?(Q →P )∧P

D . ?(? P ∨P )→(?P ∧P )

6、一个公式在等价意义下,下面哪个写法是唯一的( )。

A .析取范式

B .合取范式

C .主析取范式

D .以上答案都不对

7、下列语句中哪个是真命题( )。

A .我正在说谎。

B .如果1+2=3,那么雪是黑色的。

C .如果1+2=5,那么雪是白色的。

D .严禁吸烟

8、下面哪个联结词运算不可交换?()

A.∧

B.→

C.∨

D.?

9、 命题公式(P ∧ (P →Q)) →Q 是()。

A.矛盾式

B.蕴含式

C.重言式

D.等值式

10、下面哪个命题公式是重言式?()

A.(P →Q)∧(Q → P)

B.(P ∧Q)→P

C.(?P ∨Q)∧?(?P ∧?Q)

D.?(P ∨Q)

11、下列哪一组命题公式是等值的?()

A. ?P ∧?Q,P ∨Q

B.A →(B →A),?A →(A →?B)

C. Q →(P ∨Q),?Q ∧ (P ∨Q)

D.?A ∨ (A ∧B),B

12、命题公式?(P ∧Q)→R 的成真赋值为()

A.000,001,110

B.001,011,101,110,111

C.全体赋值

D.无

13、如果A ?B 成立,则以下各种蕴含关系哪一个成立?()

A.B ?A

B.?A ??B

C.?B ??A

D.?A ?B

14、设命题公式))((r q p p G →∧→=,则G 是( )。

A. 恒假的

B. 恒真的

C. 可满足的

D. 析取范式

15、下列命题公式中,为永假式的是( )。

A .P →(P ∨Q ∨R )

B .(P →?P )→?P

C .?(Q →P )∧P

D . ?(? P ∨P )→(?P ∧P )

16、设命题公式)(Q P P G ∨→=,则G 是( )。

A. 恒假的

B. 恒真的

C. 可满足的

D. 析取范式

17、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x 的作用域是()

A. ?x(P(x)∨?yR(y))

B.P(x)

C. (P(x)∨?yR(y))

D.P(x),Q(x)

18、谓词公式?x(P(x)∨?yR(y))→Q(x)中变元x 是()

A.自由变量

B.约束变量

C.既不是自由变量也不是约束变量

D.既是自由变量也是约束变量

19、若个体域为整体域,下列公式中哪个值为真?()

A.?x ?y(x+y=0)

B.?y ?x(x+y=0)

C.?x ?y(x+y=0)

D.??x ?y(x+y=0)

20、设谓词P(x):x 是奇数,Q(x):x 是偶数,谓词公式?x(P(x)∧Q(x))在下面哪个论域中是可满足的?()

A.自然数集

B.整数集

C.实数集

D.以上均不成立

21、设C(x):x 是运动员,G(x):x 是强壮的。命题“没有一个运动员不是强壮的”可符号化为()

A.??x(C(x)∧?G(x))

B.??x(C(x)→?G(x))

C.??x(C(x)∧?G(x))

D.??x(C(x)→?G(x))

22、设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))

23、设Z(x):x 是整数,N(x):x 是负数,S(x,y):y 是x 的平方,则“任何整数的平方非负”可表示为下

述谓词公式()

A.?x ?y(Z(x)∧S(x,y)→?N(y))

B.?x ?y(Z(x)∧S(x,y)→?N(y))

C.?x ?y(Z(x)→S(x,y)∧?N(y))

D.?x(Z(x)∧S(x,y)→?N(y))

24、令F(x):x 是火车,G(y):y 是汽车,H(x,y):x 比y 快。则语句“某些汽车比所有的火车慢”可表示

为()

A.?y(G(y)→?x(F(x)∧H(x,y)))

B.?y(G(y)∧?x(F(x)→H(x,y)))

C.?x ?y(G(y)→(F(x)∧H(x,y)))

D.?y(G(y)→?x(F(x)→H(x,y)))

25、设个体域A={a,b},公式?xP(x)∧?xS(x)在A 中消去量词后应为()

A.P(x)∧S(x)

B.P(a)∧P(b)∧(S(a)∨S(b))

C.P(a)∧S(b)

D.P(a)∧P(b)∧S(a)∧S(b)

26、在谓词演算中,下列各式哪个是正确的?()

A.?x ?yA(x,y)??y ?xA(x,y)

B.?x ?yA(x,y)??y ?xA(x,y)

C.?x ?yA(x,y)??x ?yA(x,y)

D.?x ?yA(x,y)??y ?xA(x,y)

27、下列各式哪个不正确?()

A.?x(P(x)∨Q(x))??xP(x)∨?xQ(x)

B.?x(P(x)∧Q(x))??xP(x)∧?xQ(x)

C.?x(P(x)∨Q(x))??xP(x)∨?xQ(x)

D.?xP(x)∧Q)??xP(x)∧Q

28、下面谓词公式哪个是前束范式?()

A.?x ?y ?z(B(x,y)→A(z))

B.??x ?yB(x,y)

C.?x ?y ?x(A(x,y)∧B(x,y))

D.?x(A(x,y)→?yB(y))

29、在谓词演算中:P(a)是?xP(x)的有效结论,其理论根据是()

A.全称规定规则(US)

B.全称推广规则(UG)

C.存在规定规则(ES)

D.存在推广规则(EG)

30、谓词公式),,(),,(z y x yG z y x xF ?→?中的变元x ( )。

A .是自由变元但不是约束变元

B .既不是自由变元又不是约束变元

C .既是自由变元又是约束变元

D .是约束变元但不是自由变元

31、设B 是不含变元x 的公式,谓词公式))((B x A x →?等价于 ( )

A .

B x xA →?)( B .B x xA →?)( C.B x A →)( D. xB x xA ?→?)(

32、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( )。

A .是自由变元但不是约束变元

B .既不是自由变元又不是约束变元

C .既是自由变元又是约束变元

D .是约束变元但不是自由变元

33、设论域E={a, b},且P(a,a)=1 P(a,b)=0 P(b,a)=1 P(b,b)=0 则在下列公式中真值为1的是

( )

A.?x ?yP(x,y)

B.?x ?yP(x,y)

C.?xP(x,x)

D. ?x ?yP(x,y)

34、下列命题公式中,为永假式的是( )。

A .P →(P ∨Q ∨R )

B .(P →?P )→?P

C .?(Q →P )∧P

D . ?(? P ∨P )→(?P ∧P )

35、设A={1,2,3},则下列关系R 不是等价关系的是( )

A .R={<1,1>,<2,2>,<3,3>}

B .R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}

C .R={<1,1>,<2,2>,<3,3>,<1,4>}

D .R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>,<3,1>,<3,2>}

36、设R 为实数集,映射σ=R →R ,σ(x )= -x 2+2x-1,则σ是( )。

A .单射而非满射

B .满射而非单射

C .双射

D .既不是单射,也不是满射

37、设集合A={1, 2, 3 },A 上的关系R={<1, 1 >,<2, 2 > },则R 不具有( )性质。

A.自反性

B.对称性

C.传递性

D. 反对称性

38、设集合},{y x X =,则=-X x P )(( )。

}}.

,{},{},{{.}};,{},{},{,{.}};{},{,{.}};

{},{{.y x y x D y x y x C y x B y x A φφ 39、设集合A={1, 2, 3 },A 上的关系R={<1, 1 >,<2, 2 > },则R 不具有( )性质。

A.自反性

B.对称性

C.传递性

D. 反对称性

40、空集?的幂集P(?)的基数是()

A.0

B.1

C.3

D.4

41、集合A={1,2,…,10}上的关系R={|x+y=10,x ∈A,y ∈A},则R 的性质为()

A.自反的

B.对称的

C.传递的,对称的

D.反自反的,传递的

42、设R 1,R 2是集合A={a ,b ,c ,d}上的两个关系,其中R 1={〈a ,a 〉,〈b ,b 〉,〈b ,c 〉,〈d ,d 〉},

R 2={〈a ,a 〉,〈b ,b 〉,〈b ,c 〉,〈c ,b 〉,〈d ,d 〉}, 则 R 2是R 1的( )闭包。

A .自反

B .对称

C .传递

D .以上都不是

43、设集合A={a, b},A 上的关系R={,},则R ( )

A. 是等价关系但不是偏序关系

B.是偏序关系但不是等价关系

C. 既是等价关系又是偏序关系

D. 既不是等价关系又不是偏序关系

44、设R 为实数集,映射σ=R →R ,σ(x )= -x 2+2x-1,则σ是( )。

A .单射而非满射

B .满射而非单射

C .双射

D .既不是单射,也不是满射

45、设(A ,≤)是偏序集,则A ( )。

A . 必有最小元和极小元

B .不一定有最小元,肯定有极小元

C .不一定有极小元,肯定有最小元

D .不一定有最小元,也不一定有极小元

46、设R 1,R 2是集合A={a ,b ,c ,d}上的两个关系,其中R 1={<a,a >,<b,b >,<b,c >,<d,d >},R 2={<

a,a >,<b,b >,<b,c >,<c,b >,<d,d >}, 则 R 2是R 1的( )闭包。

A .自反

B .对称

C .传递

D .以上都不是

47、空集?的幂集P(?)的基数是()

A.0

B.1

C.3

D.4

48、集合A={1,2,…,10}上的关系R={|x+y=10,x ∈A,y ∈A},则R 的性质为()

A.自反的

B.对称的

C.传递的,对称的

D.反自反的,传递的

49、设集合A={a,b,c},R 是A 上的二元关系,R={,,,},那么R 是()

A.反自反的

B.反对称的

C.可传递的

D.不可传递的

50、设R 和S 是集合A 上的等价关系,则R ∪S 的对称性()

A.一定成立

B.一定不成立

C.不一定成立

D.不可能成立

51、设集合A={a, b, c, d},B={1,2,3,4},则从A 到B 的函数f={,,,}是( )。

A. 双射

B. 单射

C. 满射

D. 即不是满射又是不是单射函数

52、设(A ,≤)是偏序集,则A ( )。

A . 必有最大元和极大元

B .不一定有最大元,肯定有极大元

C .不一定有极大元,肯定有最大元

D .不一定有最大元,也不一定有极大元

53、集合},,,,{e d c b a A =,偏序关系R 的哈斯图如下图所示,若A 的子集},,{e d c B =,则元素c 为B

的( )。

离散数学试题库10

A. 下界;

B. 最大下界;

C. 最小上界;

D. 以上答案都不对。

54、设集合},{y x X =,则=-X x P )(( )。

}}.,{},{},{{.}};,{},{},{,{.}};{},{,{.}};

{},{{.y x y x D y x y x C y x B y x A φφ

55、设S={a,b},则S 上总共可定义的二元运算的个数是()

A.4

B.8

C.16

D.32

56、设集合A={1,2,3,…,10},下面定义的哪种运算关于集合A 是不封闭的?()

A. x*y=max{x,y}

B. x*y=min{x,y}

C. x*y=GCD(x,y),即x ,y 的最大公约数

D. x*y=LCM(x,y),即x ,y 的最小公倍数

57、在自然数集N 上,下列哪种运算是可结合的?()

A.a*b=a-b

B.a*b=max{a,b}

C.a*b=a+2b

D.a*b=|a-b|

58、对自然数集N ,下列哪种运算不是可结合的?()

A.a*b=a+b+3

B.a*b=min{a,b}

C.a*b=a+2b

D.a*b=a ?b(mod 3)

59、下列运算中,哪种运算关于整数集不能构成半群?()

A.a οb=max{a,b}

B.a οb=b

C.a οb=2ab

D.a οb=|a-b|

60、*运算如下表所示,哪个能使({a,b},*)成为独异点?()

离散数学试题库10

61、Q 是有理数,(Q,*)(其中*为普通乘法)不能构成()

A.群

B.独异点

C.半群

D.交换半群

62、R 为实数集,运算*定义为:a,b ∈R ,a*b=a ?|b|,则代数系统(R,*)是()

A.半群

B.独异点

C.群

D.阿贝尔群

63、下列代数系统(S,*)中,哪个是群?()

A. S={0,1,3,5},*是模7的加法

B .S=Q(有理数集合),*是一般乘法

C .S=Z(整数集合),*是一般乘法

D .S={1,3,4,5,9},*是模11的乘法

64、具有如下定义的代数系统(G,*),哪个不够成群?()

A . G={1,10},*是模11的乘法

B. G={1,3,4,5,9},*是模11的乘法

C. G=Q ,*是普通加法

D. G=Q ,*是普通乘法

65、设x ,y 是群(G,*)的任意两个元素,n 是大于0的整数,x n 表示n 个x 进行乘法运算,则下述等式

中哪个不成立?()

A .(x*y)n =x n *y n

B .(x*y)n+1=x*(y*x) n *y

C .y*(x*y) n *y =(y*x) n *y

D .(x*y) n *x= x*(y*x) n

66、任何一个有限群在同构的意义下可以看作是()

A.循环群

B.置换群

C.交换群

D.阿贝尔群

67、若(H,*)是(G,*)的真子群,且|H|=n ,|G|=m ,则有()

A.n 整除m

B.m 整除n

C.n 整除m 且m 整除n

D.n 不整除m 且m 不整除n

68、6阶群的任何非平凡子群一定不是()

A.2阶

B.3阶

C.4阶

D.6阶

69、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群…………( ) b a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b

a a b

a *

70、半群、群及独异点的关系是( )

A .{群}?{独异点}?{半群} B.{独异点}?{半群}?{群}

C. {独异点}?{群}?{半群}

D.{半群}?{独异点}?{群}

71、下列二元运算在所给的集合上封闭的是( )

A . S={2x-1|x ∈Z +},S 关于普通的加法运算

B . S={0,1},S 关于普通的加法运算

C . 整数集合Z 和普通的减法运算

D . S={x | x=2n ,n ∈Z +},S 关于普通的加法运算

72、下列二元运算在所给的集合上不封闭的是( )

E . S={2x-1|x ∈Z +},S 关于普通的乘法运算

F . S={0,1},S 关于普通的乘法运算

G . 整数集合Z 和普通的减法运算

H . S={x | x=2n ,n ∈Z +},S 关于普通的加法运算

73、下列各代数系统中,不含零元素的是 ( )

A .>*<),(R M n , )(R M

n 是全体n 阶实矩阵集合,*是矩阵乘法运算。

B .>< ),(S p ,)(S p 是集合S 的幂集合, 是集合的并运算。

C .>+<,R ,R 是有理数集,+是数的加法运算。

D .>< ,I ,I 是整数集, 是数的乘法运算。

74、设i 是虚数,·是复数乘法运算,则G=<{1,i ,-1,-i },·>是群,下列不是G 的子群的是 (

) A .<{1,i},·> B. <{1},·> C .<{1,-1},·> D.<{1,i ,-1,-i},·>

75、 设图G 是有6个顶点的连通图,总度数为20,则从G 中删去( )边后使之变成树。

A .10 B. 5 C. 3 D. 2

76、下列叙述不正确的是 ( )

A . 若一条路中所有的边均不相同,称作迹。

B . 若一条路中所有的顶点均不相同,称作通路。

C . 若图G 多于一个连通分支,则G 不连通。

D . 存在六个结点的自补图。

77、 已知图G 的邻接矩阵为 则G 有( )。

离散数学试题库10

A. 5点,8边

B. 6点,7边

C. 5点,7边

D. 6点,8边

78、下列关于树的叙述不正确的是 ( )

A .无回路的连通图 B. 树中的树叶可少于两片

C. 每一对结点之间有且仅有一条回路

D. 树中任何边均为桥

79、设图G是有6个顶点的连通图,总度数为20,则从G中删去()边后使之变成树。

A .10 B. 5 C. 3 D. 2

80、下列图中是欧拉图的是()

离散数学试题库10

离散数学试题库10

离散数学试题库10

离散数学试题库10

A B C D

81、下列各组数中,能构成无向图的度数列是1()

A.1,1,1,2,4 B.1,2,3,4,5

C.0,1,0,2,4 D.1,2,3,3,5

82、在具有n个结点的无向连通图中,()。

A. 恰好有n条边

B. 恰好有n-1条边

C. 最多有n条边

D. 至少有n条边

83、下列各组数中,能构成无向图的度数列是()

A.1,1,1,2,4 B.1,2,3,4,5

C.0,1,0,2,4 D.1,2,3,3,5

84、无向图G中的边e是G的割边的充要条件是()。

A .e是重边 B. e不是重边

C. e不包含在G的任一简单回路中

D. e不包含在G的某一回路中

85、有n个结点的连通图中,其边数()

A.最多有n-1条

B.至少有n-1条

C.最多有n条

D.至少有n条

86、设G=为无环的无向图,|V|=6,|E|=16,则G是()

A.完全图

B.零图

C.简单图

D.多重图

87、含5个结点、3条边的不同构的简单图有()

A.2个

B.3个

C.4个

D.5个

88、设G为有n个结点的简单图,则有()

A.△(G)

B.△(G)≤n

C.△(G)>n

D.△(G)≥n

89、设G=(n,m),且G中每个结点的度数不是k就是k+1,则G中度为k的结点的个数是()

A.n/2

B.n(n+1)

C.nk

D.n(k+1)-2m

90、给定下列序列,可构成无向简单图的结点度数序列的是()

A.(1,1,2,2,3)

B.(1,1,2,2,2)

C.(0,1,3,3,3)

D.(1,3,4,4,5)

91、图G和G’的结点和边分别存在一一对应关系是G和G’同构的()

A.充分条件

B.必要条件

C.充要条件

D.既不充分也不必要条件

92、若简单图G与其补图G同构,称G为自补图。则含5个结点不同构的无向自补图的个数为()

A.0

B.1

C.2

D.3

93、设G=为无向图,u,v V,若u,v连通,则()

A.d(u,v)>0

B.d(u,v)=0

C.d(u,v)<0

D.d(u,v)≥0

94、任何无向图中结点间的连通关系是()

A.偏序关系

B.等价关系

C.相容关系

D.拟序关系

95、设D=为有向图,V={a,b,c,d,e,f},E={,,,,}是()

A.强连通图

B.单向连通图

C.弱连通图

D.不连通图

96、一棵树有2个4度顶点,3个3度顶点,其余都是树叶,则该树中树叶的个数是()

A .8 B.9 C. 10 D. 11

二、填空题

1、设命题公式)(R Q P G →?→=,则使公式G 为假的解释是 、

和 。

2、已知命题))((R Q P G ∧→?=,则所有使G 取真值1的解释是 、 、 和 。

3、 公式(P ∧Q)→(R ∨S)真值表中共有 种真值指派。

4、设p :1+1=5,q :明天是阴天。则命题“只要1+1=5,那么明天是阴天”可符号化为________ _,

其真值为________ _。

5、 任意两个不同极小项的合取为 式,全体极小项的析取式必为 。

6、命题公式?(P →Q)的主析取范式为 ,主合取范式的编码表示为 。

7、已知公式A(P,Q,R)的主合取范式为M 0∧M 3∧M 5,它的主析取范式为(写成编码形式) 。

8、命题公式?(P ?Q)的主析取范式为 ,其编码表示为 ,主合取范式的编码表示

为 。

9、 对于前提:S →?Q ,S ∨R ,?R, ?P ?Q ,其有效结论为 。

10、对于前提:(P ∧Q) →R ,?R ∨S, ?S ,其有效结论为 。

11、两个重言式的析取是 ,一个重言式与一个矛盾式的析取是 。

12、A 、B 为两个命题公式,A ?B 当且仅当 ,A ?B 当且仅当 。

13、设P 、Q 为两个命题公式,德●摩根律可表示为 ,吸收率可表示为 。

14、设x x F :)(是兔子,()y y G :是乌龟,x y x H :),(比y 跑得快,则“并不是所有的兔子都比乌龟跑得

快。”可符号化为

15、设是人x x M :)(,()x x D :是要死的,则“所有的人都是要死的”可符号化为 将公式化成等价的前束范式,=→?→???)))()((),((x R z zQ y x yP x

16、设是火车x x F :)(,()y y G :是汽车,x y x H :),(比y 快,则“每一列火车都比某些汽车快。”可符

号化为

17、令R(x):x 是实数,Q(x):x 是有理数。命题“并非每个实数都是有理数”。其符号化为 。

命题“虽然有些实数是有理数,但并非一切实数都是有理数”。则其符号化可表示为 。

18、设G(x):x 是金子,F(x):x 是闪光的,则命题“金子是闪光的,但闪光的不一定是金子”符号化

为 。

19、设C(x):x 是计算机,P(x,y):x 能做y ,I(x):x 是智能工作,则命题“并非所有智能工作都能由计算

机来做”符号化为 。

20、设Q(x):x 是偶数,P(x):x 是素数,则命题“存在惟一一个偶素数”可符号化为 ,“至多存在

一个偶素数”可符号化为 。

21、设Q(x):x 是奇数,Z(x):x 是整数,则语句“不是所有整数都是奇数”所对应的谓词公式为 。

22、设个体域为自然数集,P(x):x 是奇数,Q(x):x 是偶数,则命题“不存在既是奇数又是偶数的自然数”

可符号化为 。

23、设个体域为全总个体域,R(x):x 是实数,Q(x):x 是有理数,Z(x):x 是整数,则命题“所有的有理

数是实数”,“有些有理数是整数”,“有些有理数是实数担不是整数”符号化分别

为 , , 。

23、?x ?y(P(x,y)∧Q(y,z))∧?xP(x,y)中?x 的作用域为 ,?y 的作用域为 ,?x 的作用域

为 。

24、公式?x(P(x)→Q(x,y)∨?R(y,z))→S(x)中自由变量为 ,约束变量为 。

25、已知集合A={φ,1, 2},则A 的幂集为________ ____________。

26、将公式化成等价的前束范式,=→?→???)))()((),((x R z zQ y x yP x

27、设谓词的定义域为},,{c b a ,将表达式))()((x Q x P x →?中的量词消除,写成与之等价的命题公式

是 。

28、设谓词的定义域为},,{c b a ,将表达式))()((y Q x P y x →??中的量词消除,写成与之等价的命题公

式是 。

29、设A(x):x 是运动员,B(x):x 是强壮的.命题“没有一个运动员不是强壮的”可符号化为

30、 是公式)(),(y yG x y xF ?→?的前束范式。

31、设A 、B 是两个集合,其中A={1,2},B={a,b,c},则A ×B= ,B ×

A= ,所以笛卡尔积不满足 律。

32、R 1,R 2是集合A={a ,b ,c ,d}上的二元关系,其中R 1={<a,a >,<a,b ><b,d >},R 2={<a,d >, <

b,c >,<b,d >,<c,b >},则

R 1 ?R 2 = ,

R 12= 。

33、设集合A d c b a A },,,,{=上的二元关系R={<a,a >, <a,c >, <b,a >, <c,c >, <c,d >, <d,c >}

则1-R 的关系矩阵=-1R M ,

1-R 的关系图为 。

34、设集合}24,12,8,6,4,3,2{=A ,R 为A 上的整除关系,集合A 中的极大元是 ;

极小元 ;

35、设函数f :X →Y ,如果对X 中的任意两个不同的x 1和x 2,它们的象y 1和y 2也不同,我们说f 是 函

数,如果ranf=Y ,则称f 是 函数。

36、设R 为非空集合A 上的等价关系,其等价类记为[x]R 。A y x ∈?,,若R y x >∈<,,则[x]R 与[y]R 的关系

是 ,而若R y x >?<,,则[x]R ∩[y]R = 。

37、设集合A={}3,2,1,R 为A 上的二元关系,

R={<1,2><3,1>,<2,3>} 则=)(R t 。

38、设A={a,b,c}上偏序关系(P(A),?),则P(A)的子集B={?,{a},{b},{a,b},{b,c}}的极大元是 ,最

大元是 ,上界是 ,下确界是 。

39、A={2,3,4,5,6,8,10,12,24},R 是A 上的整除关系。那么A 的极大元是 ,极小元是 。

34. A={1,2,3,4,5,6,7,8,9,10,11,12},R 是A 上的整除关系。子集B={2,4,6},那么B 的最大元

是 ,B 的最小元是 ,B 的上界是 ,B 的下界是 。

40、A={1,2,3,4,5,6,8,10,24,36},R 是A 上的整除关系。子集B={1,2,3,4},那么B 的上界是 ,B 的

下界是 ,B 的上确界是 ,B 的下确界是 。

41、代数结构<A ,*>满足 、 、 、 ,称为群。

42、R 是集合A 上的二元关系,如果关系R 同时具有 性、 性和 性,则

称R 是偏序关系。

43、 设A 、B 是两个集合,其中A={3,4},B={c ,d},则A ×B= ,B ×

A= ,所以笛卡尔积不满足 律。

44、设集合}24,12,8,6,4,3,2{=A ,R 为A 上的整除关系,集合A 中的极大元是 ;

极小元 ;

45、设〈S ,*〉是群,那么S 中除 外,不可能有别的幂等元;若〈S ,*〉有零元,则||S = 。

46、 设有向图D 的邻接矩阵A(D)=????????????0100

100001000121,则长度为2的通路有 条. 47、设4

44{},3,2,1,0{4≥+-+<++=⊕=y x y x y x y x y x Z ,则),(4⊕Z 的生成元 是 或 。

48、具有16个结点的完全无向图其边数一定为______________条。

49、无向图G 如图所示,则G 的全部点割集为 ,则G 的全部边

割集为 ,△(G )= , δ(G )= 。

50、 设有向图D 的邻接矩阵A(D)=????????????0100

100001000121,则长度为2的通路有 条. 51、 设6

66{

},5,4,3,2,1,0{6≥+-+<++=⊕=y x y x y x y x y x Z ,则),(6⊕Z 的生成元 是 或 . 52、具有16个结点的完全有向图其边数一定为______________。

53、无向图G 是由k(k>2)棵树组成的森林,至少要添加 条边才能使G 成为一棵树.

54、设集合A={2,3,4,6,8,12,24},R 为A 上的整除关系,集合A 中的极大元是 ;极小元 ;

55、设A={a,b},B={1,2,3},则可定义 个不同的B 到A 的满射。

56、设群>⊕=<}),,({b a P G ,其中⊕为集合的对称差运算,那么群方程}{},{b b a X =⊕的解是X = 。

57、 集合Z m ={[0],[1],[2],…,[m-1]},在Z m 上定义运算+m 为:对任意的[i],[j]∈Z m 有:[i]+m [j]=[(i+j )(modm )],则的幺元是 ,[i]∈Z m 的逆元是 。

58、无向图G 如图1所示,则G 的点连通度为 。

d c

a

e b

离散数学试题库10

离散数学试题库10

图1 图2

59、有向图D 如图2所示,则有向图D 的邻接矩阵A= , D 中长度为2的回路有 条。

三、综合题

1、求公式)()(q p q p ∨?→→?的主析取范式。

2、求公式r q p ?→)(的主析取范式。

3、求公式r q p →?)(的主合取范式。

4、求公式)))(((R Q Q P P →?∨→?∨的主析取范式。并由主析取范式求主合取范式。

5、证明))()(())()((x xQ x xP x Q x P x ?→?→→?为重言式。

6、证明等价式R R P R Q R Q P ?∧∨∧∨∧?∧?)()())((

7、用推理规则证明下列推理的正确性:如果A 努力工作,那么B 或C 感到愉快;如果B 愉快,那么A 不努力工作;如果D 愉快那么C 不愉快。所以,如果A 努力工作,则D 不愉快。

8、用等值演算法证明?P ∧?(P →Q)是矛盾式。

9、设A(x),B(x)均为含有自由变量x 的任意谓词公式,证明:

?x(A(x)→B(x))??xA(x)→?xB(x)

10、设R 1,R 2为A 上的关系,证明:1211121)(---?=?R R R R 。

11、设R 1,R 2为A 上的关系,证明:1211121)(---?=?R R R R 。

12、证明:设R 为非空集合A 上的等价关系, 则

(1)?x ∈A ,[x]是A 的非空子集;

(2)∪{[x]|x ∈A}=A.

13、设〈A,R 〉为一个偏序集,其中A={1,2,3,4,6,9,24,54} ,R 是A 上的整除关系。(1)画出〈A,R 〉的哈斯图;(2)求R 关于A 的极大元;(3)求B={4,6,9}的最小上界和最大下界。

14、设集合A={}3,2,1,R 为A 上的二元关系,R={<1,2><3,1>,<2,3>} ,求2

R ,)(R r ,)(R s ,)(R t 的集合表达式。

15、A 、B 、C 、D 四个人中要派两个人出差,需满足如下条件:

(1)若A 去,则C 和D 中要去一人;

(2)B 和C 不能都去;

(3)C 去则D 要留下。问有几种派法?如何派?

16、在自然推理系统F 中,构造下面推理的证明:任何人如果喜欢音乐就不喜欢体育。每个人或者喜欢体育或者喜欢美术。有的人不喜欢美术,因而有的人不喜欢音乐。(个体域为人类集合)

17、在自然推理系统F 中,构造下面推理的证明:

没有白色的乌鸦,北京鸭都是白色的。因此,北京鸭都不是乌鸦。(个体域为全总论域)

18、在自然推理系统F 中,构造下面推理的证明:

每个喜欢数学的人都不喜欢语文。每个人或者喜欢语文或者喜欢英语。有的人不喜欢英语,所以有的人不喜欢数学。(个体域为人类集合)

19、在自然推理系统F 中,构造下面推理的证明:

只要A 曾到过受害者房间并且11点以前没离开,A 就犯了谋杀罪。A 曾到过受害者房间。如果A 在11点以前离开,看门人会看见他。看门人没有看见他,所以A 犯了谋杀罪。

20、在自然推理系统F 中,构造下面推理的证明:

每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车,所以有的人不喜欢步行。(个体域为人类集合)(10分)

21、某班有学生60人,其中有38人选修Visual C++课程,有l6人选修Visual Basic 课程。有21人选修Java 课程;有3人这三门课程都选修,有2人这三门课程都不选修,问仅选修两门课程的学生人数是多少?

22、A={1,2,3,4},R 是A ×A 上的关系,A A v u y x ?>∈<>

yu xv v u R y x =>?<><,,。

(1)证明R 是一个等价关系;(2)确定由R 引起的对A ×A 的划分

23、设C*={a+bi | a,b 为实数,且a ≠0}。其中i 是虚数单位。在C*上定义:

R={| a+bi ∈C*∧c+di ∈C*∧ac >0}

(1)证明:R 是C*上的等价关系;

(2)给出R 产生的等价类。(8分)

24、设R 是A 上的自反的和传递的,如下定义A 上的关系T ,使得

A y x ∈?, ,R x y R y x T y x >∈<∧>∈?<>∈<,,,

证明:T 是A 上的等价关系。

25、A={1,2,3,4},R 是A ×A 上的关系,A A v u y x ?>∈<>

u y v x v u R y x +=+>?<><,,。

(1)证明R 是一个等价关系;

(2)确定由R 引起的对A ×A 的划分。

26、设G=<a >是12阶循环群,求出G 的所有子群。

27、设G=<a >是10阶循环群,求出G 的所有子群。

28、设Z 为整数集合,在Z 上定义二元运算 如下:2,,-+=∈?y x y x Z y x

证明:Z 关于 运算构成群。

29、证明:素数阶群均为循环群。

30、设G=<a >是16阶循环群,求出G 的所有子群。

31、代数系统<H ,*>是群<G ,*>的一个子群,证明以下结论:

(1)当a ∈H 时,H 关于a 的左右陪集为aH=Ha=H

(2)关系R ={<a , b >|a ∈G,b ∈G 且a -1*b ∈H }是等价关系且对任意a ∈G,有aH=[a].

32、写出以下无向图的邻接矩阵并画出其补图。

离散数学试题库10

33、在一棵有2个2度顶点,4个3度顶点,其余顶点都是树叶的无向树中,应该有几片树叶?(2)画出两棵非同构的满足(1)中顶点度数的无向树T1和T2。

34、证明:6阶群中必含3阶元。

35、证明:阶小于6的群均是交换群。

36、7阶无向树中有3片树叶和1个3度结点,其余3个结点的度数均无1和3。画出满足要求的所有非同构的无向树。

37、画出所有五阶非同构的无向树。

38、利用Kruskal 算法求图G的一棵最小生成树。

离散数学试题库10

39、用K ruskal算法求下列权图的最小生成树,并求最小生成树的权数.

离散数学试题库10

A

相关推荐
相关主题
热门推荐