一、选择题

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 →?)( Ｃ.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

的（ ）。

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},*)成为独异点？（）

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 有（ ）。

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、下列图中是欧拉图的是（）

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

图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、写出以下无向图的邻接矩阵并画出其补图。

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的一棵最小生成树。

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

A