离散数学试题库10

、选择题

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

2n 2

C.n B.2 A.2n

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

B .是真命题 C .是假命题 D .是悖论 A .不是命题

可符号化为( 3、 若P表示“他聪明”，Q表示“他用功”，则“他聪明但不用功” B. PA — Q C. PT — Q D. PV — Q A. PV Q

” ,则“只有天下大雨, 他才乘车上4 、 若p表示“天下雨”，q表示“他乘车上班”

班” A B. q— p C. p— _ q D. _ qT p . p— q

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

A . P—( PV Q V R) B. (PT 一 P— 一 P CD . —(—PV P)T (— PA P) . 一 ( Q— P )A P 6、 一个公式在等价意 义下，下面哪个写法是唯一的( )°

7 、 下列语句中哪个是真命题( A .我正在说谎。

B .如果1+2=3，那么雪是黑色的。 C.如果1+2=5，那么雪是白色的。 D .严禁吸烟 8、 下面哪个联结词运算不可交换？() A. B.r C. 9 、 命题公式(P (P—；Q)) -/Q 是()。 A.矛盾式 B.蕴含式 C.重言式 10、 下面哪个命题公式是重言式？()

A.(P—Q) (Q—• P) B.(P Q) >P C.(D.—(P Q) —P Q) _(一P -Q)

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

2

n

可符号化为( )

A .析取范式 B .合取范式 C.主析取范式 D .以上答案都不对

D.等值式

A. 一P Q,P Q B.Ar(B》A),—Ar(A LB)

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 B. —A—— C.—B—一 D. —A二 C.全体赋值 D.无 B A B 13、 如果A—B成立，则以下各种蕴含关系哪一个成立？() 14、设命题公式 G = p》p (q > r))，则 G 是(

A.B= A A.恒假的 D.析取范式 C. 可满足的 B.恒真的

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

B. (PT — P)T P A . PV Q V R)

D -(—PVP)- PA P) C . 一 (QTP )A P

. )° 16、 设命题公式G二P》P Q)，则G是(

A.恒假的 B.恒真的 C.可满足的 D.析取范式

(

(

_17、 谓词公式~x(P(x) •• TyR(y))r Q(x)中量词x的作用域是() A. -x(P(x) . TyR(y)) B.P(x) C. (P(x) yR(y)) D.P(x) , Q(x)

18、 谓词公式 _x(P(x^-JyR(y)^ Q(x)中变元 x 是() A.B.约束变量 自由变量

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

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

A. _x y(x+y=0) B. y _x(x+y=O)

第1页共12页

C.-x-y(x+y=O) D.— x y(x+y=O)

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)—l x(F(x) > H(x,y)))

25、 设个体域 A={a,b},公式-xP(x)八二IxS(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) yTxA(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)) hxP(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)rA(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.

C.存在规定规则(ES)

全称规定规则(US) B.全称推广规则(UG) D.存在推广规则(EG)

)。

30、 谓词公式 ~xF(x, y, z)—• -yG(x, y,z)中的变元 x ( A .是自由变元但不是约束变元 B •既不是自由变元又不是约束变元 C .既是自由变元又是约束变元 D .是约束变元但不是自由变元 31、 设B是不含变元x的公式，谓词公式 —x(A(x) > B)等价于 ( A. xA(x)— B B. - xA(x)r B C.A(x)— B D. ~xA(x)— 32、谓词公式 F (x, y, z)—JxTyG(x, y,z)中的变元 x (

)

*B

)。

第2页共12页

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

第3页共12页

C .既是自由变元又是约束变元 D .是约束变元但不是自由变元

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

A. x-yP(x,y) B. -x-yP(x,y) C.

-xP(x,x) D. -x yP(x,y)

34、下列命题公式中，为永假式的是(

)。

A .

PV Q V R)

B. (PT 一 P— 一 P

C. 一 ( QT P )A P

D . -(一 PV P)T (— PA 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>} 2

36、 设 R 为实数集，映射 c=R >R,r （x） = -x2+2x-1 U ；:■是（ ）。

A .单射而非满射 B .满射而非单射 C.双射 D .既不是单射，也不是满射 37、 设集合A={1,2, 3 } , A上的关系R={<1, 1 >,<2, 2 > } ，则R不具有（ ）性质。

A.自反性 B.对称性 C.传递性 D.

反对称性 38、 设集合 X ={x, y}，则 P（x） - X =（

）。

A- {{ x}, {y}}; B. { ,{x}, {y}}; C. { ,{x}, {y}, {x, y}};

D. {{ x}, { y}, {x, y}}.

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、 设 R1, R2是集合 A={a , b,

c,

d}上的两个关系，其中 R1={〈 a〉〉〈 b,

b>, <

b,

c〉，〈d, d> },

R2={ , < b, b>, < b, c>, < c, b>, < d, d> },贝U R2是 R1 的（ ）闭包。 A .自反 B .对称 C .传递 D .以上都不是 43、 设集合 A={a, b} , A 上的关系 R={,}，贝U R （ ） A.是等价关系但不是偏序关系 B.是偏序关系但不是等价关系 C.既是等价关系又是偏序关系 D. 既不是等价关系又不是偏序关系 44、设R为实数集，映射 c=R >R, 2

c (x) = -x +2x-1，则■::是(

A .单射而非满射 B .满射而非单射 C.双射 D .既不是单射，也不是满射 45、设（A，◎是偏序集，贝U A ）。 （ A .必有最小元和极小元 B .不一定有最小元，肯定有极小元 C.不一定有极小元，肯定有最小元 D .不一定有最小元，也不一定有极小元

46、设 R1, R2 是集合 A={a , b, c, d}上的两个关系，其中 R1={ v a,a>, v b,b>,v b,c>, v d,d>}, R2={ v

a,a>,v b,b>,v b,c>,v c,b>,v d,d>}, 则R2是R1的（

）闭包。 A .自反 B.对称 C.传递 D .以上都不是 47、空集.一的幕集P（._）的基数是（）

A.0 B.1 C.3 48、集合

D.4 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.不可传递的

第4页共12页

a, 50、 设R和S是集合A上的等价关系，则 R U S的对称性（）

A. 一定成立 B. 一定不成立 C.不一定成立 D.不可能成立

第5页共12页

51、设集合 A={a, b, c, d},B={1,2,3,4}, 则从 A到 B的函数 f={,,,}是（ A.双射 B. 单射 C. 满射 D. 即不是满射又是不是单射函数 （ ）。

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

52、设（A，乞）是偏序集，贝U A

D •不一定有最大元，也不一定有极大元

A .必有最大元和极大元

55、 设S={a,b}，贝U S上总共可定义的二元运算的个数是（）

C.不一定有极大元，肯定有最大元 53、集合A ={a,b, c, d, e}，偏序关系 的（ ）。

A.下界； B.最大下界；

C.最小上界； D.以上答案都不对。 54、设集合 X ={x, y}，则 P（x） -X =（

R的哈斯图如下图所示，若

）。

A的子集B ={c, d,e}，则元素c为B

A. {{x}, {y}}; B. { ,{x}, {y}}; D. {{x}, {y}, {x, y}}.

A是不封闭的？（）

）

C. { ,{x}, {y}, {x, y}};

A.4 B.8 C.16 D.32 56、 设集合A={1,2,3,…,10}下面定义的哪种运算关于集合

A. x*y=max{x,y} B. x*y=mi n{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

58、 对自然数集 N，下列哪种运算不是可结合的？（）

A.a*b=a+b+3 B.a*b=min{a,b} C.a*b=a+2b

59、 下列运算中，哪种运算关于整数集不能构成半群？（）

A.a o b=max{a,b} B.a o b=b

D.a*b=|a-b|

D.a*b=a b（mod 3）

A B. C. D.

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 的乘法

、 具有如下定义的代数系统 （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的整数，xn表示n个x进行乘法运算，则下述等式 中哪个不成立？（）

A . （x*y） n=x n*y n

n+1

n

B. （x*y） =x*（y*x） *y

C. y*（x*y） n*y =（y*x） n*y D. （x*y） n*x= x*（y*x） n

第6页共12页

66、任何一个有限群在同构的意义下可以看作是 （） C.交换群 A.循环群 B.置换群

67、若（H,*）是（G,*）的真子|H|=n， |G|=m，则有（）

D.阿贝尔群

B.m整除n

A.n整除m D.n不整除m且 C.n整除m且m整除n 68、6阶群的任何非平凡子群一定不是 （） C.4阶

A.2阶 B.3阶 69、*运算如下表所示，哪个能使（{a,b}

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

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

{群}二{半群} D.{ C. {独异点}

群，且

m不整除n

D.6阶

独异点}二{半群}二{群} 半群}二{独异点}

{群}

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

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

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

D . S={x | x=2 n, n • Z+}, S关于普通的加法运算 72、下列二元运算在所给的集合上不封闭的是（

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

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

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

n+

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

73、 下列各代数系统中，不含零元素的是 （ ） A . ::: Mn（R）/ , Mn （R）是全体n阶实矩阵集合，“是矩阵乘法运算。

B . < p（S）, - , p（S）是集合S的幕集合， 是集合的并运算。 C. ::: , R是有理数集，•是数的加法运算。 D . ::: I/ ■ , I是整数集，•是数的乘法运算。

74、 设i是虚数，•是复数乘法运算，则G= V{1 ,i,-1，-i } , •>是群，下列不是G的子群的是 （

A . < {1 , i} , •> B. < {1} , •> C.v {1 , -1}, •> D.v{1 , i, -1, -i} , •>

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

A.若一条路中所有的边均不相同，称作迹。 A .10 B. 5 C. 3 D. 2 B .若一条路中所有的顶点均不相同，称作通路。 76、 下列叙述不正确的是 （ ）

C.若图G多于一个连通分支，则 G不连通。 D .存在六个结点的自补图。

77、 已知图 G的邻接矩阵为 则G有（ LI 1 1 1 1

1O1OO 1 1

A. 5点，8边

B. 6点，7边 D. 6点，8边

O1 L lOLO 1 1 CI1 1 O

C. 5点，7边

78、下列关于树的叙述不正确的是 （ ） A .无回路的连通图 B.树中的树叶可少于两片

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

D.树中任何边均为桥

第7页共12页

G中删去( )边后使之变成树。

D

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

A. 1,1,1,2,4 C. 0,1,0,2,4

1(

)

B

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

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

A.恰好有n条边 C. 最多有n条边

B. 恰好有n-1条边 D. 至少有n条边

)

. 1,2,3,4,5 . 1,2,3,3,5

83、 下列各组数中，能构成无向图的度数列是( A. 1,1,1,2,4 C. 0,1,0,2,4

B D

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.简单图 87、 含5个结点、3条边的不同构的简单图有()

C.4个 B.3个 A.2个

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

D.多重图D.5个

D. △ (G) > n A. △ (G)n

、 k就是k+1，则G中度为k的结点的个数是() 设G=(n,m)，且G中每个结点的度数不是 A. D.n( k+1)-2m B.n(n+1) C.nk n/2 给定下列序列，可构成无向简单图的结点度数序列的是() 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、 A.0 93、

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

B.1 u,w V，若u,v连通，则()

设G=为无向图, C.2 D.3

A.d(u,v)>0 B.d(u,v)=0 C.d(u,v)<0 D.d(u,v) > 0 94、

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

B.等价关系

C.相容关系

D.拟序关系

V={a,b,c,d,e,f}, E={,,,,} 是 ()

D. 不连通图 C.弱连通图

)

A.偏序关系

95、 设D=为有向图，

A.强连通图 B.单向连通图

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

B.9

C. 10

D. 11

第8页共12页

二、填空题

1、 设命题公式G二P

-(Q > R),则使公式G为假的解释是 _______________________________________ 、

和 ______________________ 。 2、 已知命题 G = -(P > (Q R))，则所有使 和 ______________________ 。

3、 公式(P A Q)T (R V S)真值表有 ___________ 种真值指派。

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

其真值为 _________ _______ 。 5、 任意两个不同极小项的合取为 ____________ 式，全体极小项的析取式必为 ____________ 。 6、 命题公式 -(P >Q)的主析取范式为 __________ ,主合取范式的编码表示为 __________ 。

7、 已知公式A(P,Q,R)的主合取范式为 Mo M3 M5,它的主析取范式为(写成编码形式) ___________________ 。 &命题公式 -(P—Q)的主析取范式为 ____________ ，其编码表示为 ___________ ，主合取范式的编码表示 为 __________ 。

9、 对于前提：S LQ, S R, -R, —P^Q，其有效结论为 _________________ 。 10、 对于前提：(P Q) >R，一R S, -S，其有效结论为 ____________ 。 11、 两个重言式的析取是 ，一个重言式与一个矛盾式的析取是 12、 A、B为两个命题公式， A B当且仅当 ____________ , A=B当且仅当 ____________ 。 13、 设P、Q为两个命题公式，德•摩根律可表示为 __________ ，吸收率可表示为 ________ 。 14、 设F(x) :x是兔子，G y : y是乌龟，H (x,y):x比y跑得快，则“并不是所有的兔子都比乌龟跑得

快。”可符号化为 _________________________________________

15、 设M (x): x是人，D x : x是要死的，则“所有的人都是要死的”可符号化为 ___________________________ 将公式化成等价的前束范式，

G取真值1的解释是 _______________ 、 _____________ 、

x( — yP(x,y) > ( zQ(z) > R(x)))二 ______________________

”可符

16、 设F(x): x是火车，G y : y是汽车，H (x, y) : x比y快，则“每一列火车都比某些汽车快。 号化为 ____________________________________________

17、 令R(x) : x是实数，Q(x) : x是有理数。命题“并非每个实数都是有理数” 。其符号化为 ________ 。 命题“虽然有些实数是有理数，但并非一切实数都是有理数” 。则其符号化可表示为 ___________ 。 18、 设G(x) : x是金子，F(x): x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”符号化 为 。 19、 设C(x): x是计算机，P(x,y): x能做y, l(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))八TxP(x,y)中-x的作用域为 ________________ , -y的作用域为 _________ , x的作用域 为 __________ 。 24、 公式-x(P(x)—；Q(x,y) R(y,z))—； S(x)中自由变量为 ______，约束变量为 ___________ 。 25、 已知集合 A={ Q ,1,2}，则 A 的幕集为 26、 将公式化成等价的前束范式， 27、设谓词的定义域为

__ _______________ _______________ 。

x(_ yP(x, y)r ( zQ(z)「・ R(x))) = ___________________________

{a,b, C}，将表达式-x(P(x) > Q(x))中的量词消除，写成与之等价的命题公式

第9页共12页

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

式是 __________________________ 。

29、 设A(x):x是运动员，B(x):x 是强壮的.命题“没有一个运动员不是强壮的”可符号化为 _____________________ 30、 _____________________________ 是公式 TxF (y, x) “ JyG( y)的前束范式。 31、 设 A、B 是两个集合，其中

A={1 , 2} , B={a,b,c},贝U A X B= __________________________ , B X

R1={ v a,a>,v a,b>v b,d> }, R2={ v a,d>, v b,c>,v

A= ________________________ ，所以笛卡尔积不满足 _________________律。 32、 R1, R2 是集合 A={a , b, c, d}上的二兀关系，其中

b,d>,v c,b>}，贝U

R1 R2 = ________________________________________ , R12= __________________________________________ 。

33、 设集合 A二{a,b,c,d}, A上的二元关系 R={ v a,a>, v a,c>, v b,a>, v c,c>, v c,d>, v d,c>} 则R J的关系矩阵M R1二 _______________________ ,

R的关系图为 ___________________ 。

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

极小元 ________________________ ;

35、 设函数f:XTY，如果对X中的任意两个不同的X1和X2,它们的象％和y也不同，我们说f是 _______________ 函

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

36、 设R为非空集合 A上的等价关系，其等价类记为 [X]R。-xy A，若：::x,y .• R，则[X]R与[y]R的关系

是 ___________________ ，而若 ：::x, y JR，则[x] R n [y] R= ____________________ 。 37、 设集合A=〈1,2,31, R为A上的二元关系，

R={ v 1,2>v 3,1 > ,v 2,3>}则t(R)二 ___________________________________________ 。

38、 设 A={a,b,c}上偏序关系(P(A),)，贝U 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、 代数结构v A, * >满足 _________ 、 42、 R是集合A上的二元关系，如果关系 称R是偏序关系。

43、 设 A、B 是两个集合，其中

A={3 , 4} , B={c , d}，贝U A X B= _________________________ , B X

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

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

、 __________ 、 ____________ ，称为群。

R同时具有 __________ 性、

性和

性，则

极小元

第8页共12页

;

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

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

卫

01

0

,则长度为2的通路有

5

47、设 Z4 二{0123}, x 二 y ={

x + y x + y —4

x y ：： 4

，则(Z4,㊉)的生成元

x y亠4

条。

，则G的全部边

48、具有16个结点的完全无向图其边数一定为 49、无向图G如图所示，贝U G的全部点割集为

割集为 ,△( G)=

1 01

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

1 0 ,则长度为2的通路有

1 0 0 1

\",则(Z6,二)的生成元 x y _ 6

x y6

51、 设 Z6 二{0,123,4,5}, x 二 y 讯

x y _6

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、设群G = ■ P({a,b}),二•，其中二为集合的对称差运算，那么群方程 X = _____________________ 。

57、集合 Zm={[0],[1],[2] , , , [m-1]}，在 Zm 上定义运算 +m 为：对任意的[i] , [j] € Zm 有：[i]+m[j]=[ ( i+j ) (modm)]，贝y 的幺元是 ________________ , [i] € Zm的逆元是 ____________________ 。 58、无向图 G如图1所示，则 G的点连通度为 ______________

X 二{a,b}二{b}的解是

第11页共12页

图2

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

1、 求公式(一p— q)— (—p q)的主析取范式。 2、 求公式(p-. q).r r的主析取范式。 3、 求公式(pi q)r的主合取范式。

4、 求公式P (―P》(Q (―Q > R)))的主析取范式。并由主析取范式求主合取范式。 5、证明-x(P(x) > Q(x))

> ( xP(x)》xQ(x))为重言式。

6、 证明等价式(一P (—Q R)) (Q R) (P R)二 R

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、 11、

设 设

Ri，R2 为 A 上的关系，证明：(R -

R2)

J

= R「- R2J。

R1，R2 为 A 上的关系，证明：(R 一 R2)，= R「一.

则

R2‘。

12、 证明：设R为非空集合A上的等价关系，

(1) ? x € A , [x]是A的非空子集；

(2) U {[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= 1,2,3\\ R 为 A 上的二元关系，R={ v 1,2>v 3,1>,v 2,3>}，求 R2 , r(R) , s(R) , t(R) 的集合表达式。

15、 A、B、C、D四个人中要派两个人出差，需满足如下条件： (1) 若A去，贝U C和D中要去一人； (2) B和C不能都去；

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

16、 在自然推理系统 F中，构造下面推理的证明：任何人如果喜欢音乐就不喜欢体育。每个人或者喜欢体 育或者喜欢美术。有的人不喜欢美术，因而有的人不喜欢音乐。

第12页共12页

(个体域为人类集合)

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

没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。 18、 在自然推理系统 F中，构造下面推理的证明：

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

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

只要A曾到过受害者房间并且 11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果 A在 11点以前离开，看门人会看见他。看门人没有看见他，所以 20、 在自然推理系统 F中，构造下面推理的证明：

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

21、 某班有学生60人，其中有38人选修Visual C++课程，有16人选修Visual Basic课程。有21人选修Java 课程；有3人这三门课程都选修，有

2人这三门课程都不选修，问仅选修两门课程的学生人数是多少？

A犯了谋杀罪。

(个体域为全总论域)

22、 A={1 , 2, 3, 4}, R 是 A X A 上的关系，一 :::x, y .,：：:U,V • A A ,

::x, y R ：： u, v xv = yu。

(1)证明R是一个等价关系；(2)确定由R引起的对A X A的划分 23、 设C*={a+bi | a,b为实数，且a^ 0}。其中i是虚数单位。在 C*上定义：

R={| a+bi € C* A c+di € C* A ac> 0} (1) 证明：R是C*上的等价关系； (2) 给出R产生的等价类。(8分)

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

_x, y A ，

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

:: x, yxWTu：： x, y >E R :： y,xR

25、 A={1 , 2, 3, 4}, R 是 A X A 上的关系，一 ：：X, y ，:: u,v A A ,

::x, y R ：： u, v x v = y u。

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

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

26、 设G= v a>是12阶循环群，求出 G的所有子群。 27、 设G= v a>是10阶循环群，求出 G的所有子群。

28、 设Z为整数集合，在 Z上定义二元运算•如下：—x,y・Z,x」= x，y-2 证明：Z关于•运算构成群。 29、 证明：素数阶群均为循环群。

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

31、 代数系统V H, * >是群V Q * >的一个子群，证明以下结论： (1) 当a€H时,H关于a的左右陪集为aH=Ha=H

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

第13页共12页

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

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

34、 证明：6阶群中必含3阶元。 35、 证明：阶小于 6的群均是交换群。

2）

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

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

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

39、用 Kruskal

算法求下列权图的最小生成树 ,并求最小生成树的权数.

第14页共12页