搜档网
当前位置:搜档网 › 离散数学试题与答案试卷一

离散数学试题与答案试卷一

离散数学试题与答案试卷一
离散数学试题与答案试卷一

离散数学试题与答案试卷一 一、填空 20% (每小题2分)

1.设 }7|{)},5()(|{<∈=<∈=+

x E x x B x N x x A 且且(N :自然数集,E + 正偶

数) 则 =?B A 。 2.A ,B ,C 表示三个集合,文图中阴影部分的集合表达式为 。

3.设P ,Q 的真值为0,R ,S 的真值为1,则

)()))(((S R P R Q P ?∨→?∧→∨?的真值=

4.公式P R S R P ?∨∧∨∧)()(的主合取范式为 。

5.若解释I 的论域D 仅包含一个元素,则 )()(x xP x xP ?→? 在I 下真值为 。

6.设A={1,2,3,4},A 上关系图为

则 R 2 = 。

7.设A={a ,b ,c ,d},其上偏序关系R 的哈斯图为

则 R= 。

8.图的补图为 。

9.设A={a ,b ,c ,d} ,A 上二元运算如下:

那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆元分别为 。

10.下图所示的偏序集中,是格的为 。

二、选择 20%

(每小题 2分)

1、下列是真命题的有( ) A . }}{{}{a a ?;

B .}}{,{}}{{ΦΦ∈Φ;

C . }},{{ΦΦ∈Φ;

D . }}{{}{Φ∈Φ。 2、下列集合中相等的有( )

A .{4,3}Φ?;

B .{Φ,3,4};

C .{4,Φ,3,3};

D . {3,4}。 3、设A={1,2,3},则A 上的二元关系有( )个。 A . 23 ; B . 32 ; C . 3

32

?; D . 2

23?。

4、设R ,S 是集合A 上的关系,则下列说法正确的是( ) A .若R ,S 是自反的, 则S R 是自反的; B .若R ,S 是反自反的, 则S R 是反自反的;

C .若R ,S 是对称的, 则S R 是对称的;

D .若R ,S 是传递的, 则S R 是传递的。

5、设A={1,2,3,4},P (A )(A 的幂集)上规定二元系如下

|}||(|)(,|,{t s A p t s t s R =∧∈><=则P (A )/ R=( )

A .A ;

B .P(A) ;

C .{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}};

D.{{Φ},{2},{2,3},{{2,3,4}},{A}}

6、设A={Φ,{1},{1,3},{1,2,3}}则A上包含关系“?”的哈斯图为()

7、下列函数是双射的为()

A.f : I→E , f (x) = 2x ;B.f : N→N?N, f (n) =

C.f : R→I , f (x) = [x] ;D.f :I→N, f (x) = | x | 。

(注:I—整数集,E—偶数集,N—自然数集,R—实数集)

8、图中从v1到v3长度为3 的通路有()条。

A.0;B.1;C.2;D.3。

9、下图中既不是Eular图,也不是Hamilton图的图是()

10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有()个4

度结点。

A.1;B.2;C.3;D.4 。

三、证明26%

1、R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当< a, b> 和在R中有<.b , c>在R中。(8分)

2、f和g都是群到< G2, *>的同态映射,证明的一个子

群。其中C=)}()(|{1x g x f G x x =∈且 (8分)

3、G= (|V| = v ,|E|=e ) 是每一个面至少由k (k ≥3)条边围成的连通平面

图,则2)

2(--≤

k v k e , 由此证明彼得森图(Peterson )图是非平面图。(11分)

四、逻辑推演 16%

用CP 规则证明下题(每小题 8分) 1、F A F E D D C B A →?→∨∧→∨, 2、)()())()((x xQ x xP x Q x P x ?→??→?

五、计算 18%

1、设集合A={a ,b ,c ,d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R 的传递闭包t (R)。 (9分)

2、如下图所示的赋权图表示某七个城市721,,,v v v 及预先算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间能够通信而且总造价最小。 (9分)

试卷二试题与答案

一、填空 20% (每小题2分)

1、 P :你努力,Q :你失败。“除非你努力,否则你将失败”的翻译为

;“虽然你努力了,但还是失败了”的翻译为 。 2、论域D={1,2},指定谓词P

则公式x ??真值为 。 2、 设S={a 1 ,a 2 ,…,a 8},B i 是S 的子集,则由B 31所表达的子集是

3、 设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则R=

(列举法)。

R 的关系矩阵M R =

5、设A={1,2,3},则A 上既不是对称的又不是反对称的关系

R= ;A 上既是对称的又是反对称的关系R= 。

6、设代数系统,其中A={a ,b ,c},

则幺元是 ;是否有幂等 性 ;是否有对称性 。

7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。

9、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())((的根树表示为

。 二、选择 20% (每小题2分)

1、在下述公式中是重言式为( )

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

B .))()(()(P Q Q P Q P →∧→??;

C .Q Q P ∧→?)(;

D .)(Q P P ∨→。

2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为( )。

A .0;

B .1;

C .2;

D .3 。

3、设}}2,1{},1{,{Φ=S ,则 S

2 有( )个元素。

A .3;

B .6;

C .7;

D .8 。 4、 设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系

},,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生

的S S ?上一个划分共有( )个分块。

A .4;

B .5;

C .6;

D .9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为

则R 具有( )性质。

A .自反性、对称性、传递性;

B .反自反性、反对称性;

C .反自反性、反对称性、传递性;

D .自反性 。 6、设 ,+ 为普通加法和乘法,则( )>+< ,,S 是域。 A .},,3|{Q b a b a x x S ∈+== B .},,2|{Z b a n x x S ∈==

C .},

12|{Z n n x x S ∈+== D .}0|{≥∧∈=x Z x x S = N 。

7、下面偏序集( )能构成格。

8、在如下的有向图中,从V 1到V 4长度为3 的道路有( )条。

A .1;

B .2;

C .3;

D .4 。 9、在如下各图中( )欧拉图。

10、

设R 是实数集合,“?”为普通乘法,则代数系统 是( )。

A .群;

B .独异点;

C .半群 。

三、证明 46%

1、 设R 是A 上一个二元关系,

)},,,(),(|,{R b c R c a A c A b a b a S >∈<>∈<∈∧∈><=且有对于某一个试证

明若R 是A 上一个等价关系,则S 也是A 上的一个等价关系。(9分)

2、 用逻辑推理证明:

所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。(11分)

3、 若B A f →:是从A 到B 的函数,定义一个函数A

B g 2:→对任意B b ∈有

)})(()(|{)(b x f A x x b g =∧∈=,证明:若f 是A 到B 的满射,则g 是从B 到 A 2

的单射。(10分)

4、 若无向图G 中只有两个奇数度结点,则这两个结点一定连通。(8分)

5、 设G 是具有n 个结点的无向简单图,其边数

2)2)(1(21

+--=

n n m ,则G 是

Hamilton 图(8分)

四、计算 14%

1、 设是一个群,这里+6是模6加法,Z 6={[0 ],[1],[2],[3],[4],[5]},

试求出的所有子群及其相应左陪集。(7分)

2、 权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。(7分)

试卷三试题与答案

一、 填空 20% (每空 2分)

1、 设 f ,g 是自然数集N 上的函数x x g x x f N x 2)(,1)(,

=+=∈?,

则=)(x g f 。

2、 设A={a ,b ,c},A 上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,

则s (R )= 。

3、 A={1,2,3,4,5,6},A 上二元关系}|,{是素数y x y x T ÷><=,则用列举

T= ; T 的关系图为

; T 具有 性质。 4、 集

}}

2{},2,{{Φ=A 的幂集

A 2= 。

5、 P ,Q 真值为0 ;R ,S 真值为1。则))()(())((S R Q P S R P wff ∧∧∨→∨∧的

真值为 。 6、 R

R Q P wff →∨∧?))((的

为 。

7、 设 P (x ):x 是素数, E(x):x 是偶数,O(x):x 是奇数 N (x,y):x 可以整数y 。

则谓词))),()(()((x y N y O y x P x wff

∧?→?的自然语言是

。 8、 谓词)),,()),(),(((u y x uQ z y P z x P z y x wff ?→∧???的前束范式为

二、 选择 20% (每小题 2分)

1、 下述命题公式中,是重言式的为( )。

A 、)()(q p q p ∨→∧;

B 、))())(()(p q q p q p →∧→??;

C 、q q p ∧→?)(;

D 、q p p ??∧)(。 2、 r q p wff

→∧?)(的主析取范式中含极小项的个数为( )。

A 、2;

B 、 3;

C 、5;

D 、0;

E 、 8 。 3、 给定推理

①))()((x G x F x →? P ②)()(y G y F → US ① ③)(x xF ? P ④)(y F ES ③ ⑤)(y G T ②④I ⑥)(x xG ?

UG ⑤

)())()((x xG x G x F x ??→?∴

推理过程中错在( )。

A 、①->②;

B 、②->③;

C 、③->④;

D 、④->⑤;

E 、⑤->⑥

4、 设S 1={1,2,…,8,9},S 2={2,4,6,8},S 3={1,3,5,7,9},S 4={3,4,5},

S 5={3,5},在条件31S X S X ??且下X 与( )集合相等。 A 、 X=S 2或S 5 ; B 、X=S 4或S 5;

C 、X=S 1,S 2或S 4;

D 、X 与S 1,…,S 5中任何集合都不等。 5、 设

R

S

P

上的关系,P

是所有人的集合,

},|,{的父亲是y x P y x y x R ∧∈><=,}

,|,{的母亲是y x P y x y x S ∧∈><=则R S

1

-表示关系 ( )。

A 、},|,{的丈夫是y x P y x y x ∧∈><;

B 、},|,{的孙子或孙女是y x P y x y x ∧∈><;

C 、 Φ;

D 、},|,{的祖父或祖母是y x P y x y x ∧∈><。 6、 下面函数( )是单射而非满射。

A 、12)(,

:2-+-=→x x x f R R f ;

B 、

x x f R Z f ln )(,:=→+

C 、的最大整数表示不大于x x x x f Z R f ][],[)(,:=→;

D 、12)(,

:+=→x x f R R f 。

其中R 为实数集,Z 为整数集,R +,Z +分别表示正实数与正整数集。 7、 设S={1,2,3},R 为S 上的关系,其关系图为

则R 具有( )的性质。

A 、 自反、对称、传递;

B 、什么性质也没有;

C 、反自反、反对称、传递;

D 、自反、对称、反对称、传递。 8、 设}}2,1{},1{,{Φ=S ,则有( )S ?。

A 、{{1,2}} ;

B 、{1,2 } ;

C 、{1} ;

D 、{2} 。 9、 设A={1 ,2 ,3 },则A 上有( )个二元关系。

A 、23 ;

B 、32 ;

C 、3

22; D 、2

32。 10、全体小项合取式为( )。

A 、可满足式;

B 、矛盾式;

C 、永真式;

D 、A ,B ,C 都有可能。 三、 用CP 规则证明 16% (每小题 8分) 1、F A F

E D D C B A →?→∨∧→∨,

2、)()())()((x xQ x xP x Q x P x ?∨??∨? 四、(14%)

集合X={<1,2>, <3,4>, <5,6>,… },R={<,>|x 1+y 2 = x 2+y 1} 。 1、 证明R 是X 上的等价关系。 (10分) 2、 求出X 关于R 的商集。(4分) 五、(10%)

设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R 的关系矩阵和关系图。(4分) 2、用矩阵运算求出R 的传递闭包。(6分)

六、(20%)

1、(10分)设f 和g 是函数,证明g f ?也是函数。

2、(10分)设函数S T f T S g →→::,证明 S T f →:有一左逆函数当且仅当f 是

入射函数。

卷号:4

湖北师范学院期末考试试卷

离散数学

一、选择题(选择真确答案,并将其代号写在题干后面的括号里,本题共6小题,每小题3分,共18分)

1 命题“小李和小王学习努力”的否定是:( )

(A)小李或小王学习不努力; (B) 小李和小王学习都不努力; (C)小李学习努力和小王学习不努力;(D) 小李和小王至少有一人学习努力。 2 设个体域{,}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 ∧∧∨。 3 A={1,2,3},A 上的如下二元关系中, ( )是函数。

(A)R1={<1,2>,<2,1>,,<2,2>}; (B)R2={<1,2>,<1,1>,<3,2>}; (C)R3={<1,1>,<2,2>}; (D)R4={<1,2>,,<2,3>,<3,3>}。 4下列代数系统(,)S *,哪个是群? ( ) (A) {0,1,3,5},S =*是模7加法; (B)S Q =(有理数集合),*是一般乘法; (C) S Z =(整数集合),*是一般减法; (D) {1,3,4,5,9},S =*是模11乘法。 5下面集合( )关于整除关系构成格。

(A){2,3,6,12,24,36} ; (B){1,2,3,4,6,8,12} ; (C){1,2,3,5,6,15,30} ; (D){3,6,9,12}。

6 {,,,,,}V a b c d e f =,{,,,,,E a b b c c a =<><><>,,,,a d d e <><>

,}f e <>,则有向图,G V E =<>是( )。

(A)强连通的 ; (B)单侧连通的 ; (C)弱连通的 ; (D)不连通的。 二、填空题(请将正确答案填入空格内,每小题3分,共18分) 1 设P :它占据空间,Q :它有质量,R :它不断运动,S :它叫做物质。

命题“占据空间的,有质量的而且不断运动的叫做物质”的符号化为 _____________________。

2 设A={1,2},P(A)表示A 的幂集,,则P(A) ? A =_____________________。 3.设{,,}A a b c =考虑下列子集:

}},{},,{{1c b b a S =,}},{},,{},{{2c a b a a S =,}},{},{{3c b a S =,}},,{{4c b a S =,

}}{},{},{{5c b a S =,}},{},{{6c a a S =

则A 的覆盖有 ,A 的划分有 。 4 设(,)A ≤是分配格,若对任意的,,a b c A ∈,如果有(,a b a c a b a c ∧=∧∨=∨成立,则

有 。

5 若连通平面图,G V E =<>共有r 个面,其中||,||V v E e ==,则它满足的Euler 公式

为 。 6 5个结点可以构成 棵非同构得无向树。 三、判断题(请在你认为正确的题后括号内打“√”,错误的打“×”,本题共6小题,每小题1分,共6分)

1设P ,Q 是两个命题,当且仅当P ,Q 的真值均为T 时,P Q ?的值为T 。( ) 2{}{,{}}?∈??且{}{,{}}????。( )

3 集合{,,}A a b c =上的关系{,,,}R a b a c =<><>是传递的。( ) 4任何循环群必定是阿贝尔群,反之亦真。( )

5设G 为无向图,若G 中恰好n 个结点,n-1条边,则G 必为一棵树。( ) 6平面图一定是连通图。( ) 四、计算题(本题共4小题,每小题6分,共24 分)

1求下式的主析取范式和主合取范式:

)()P Q P Q ?→?→?(。

2设集合A= {1,2,3,4}上的二元关系R1与R2定义如下: R1={<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<4,4>}, R2={<1,1>,<1,2>,<2,1>,<2,3>,<3,4>,<4,1>},

(1)写出R1的关系矩阵,并判断R1具有哪些性质? (2)求出R1R2。

3 设S = R \ {-1}(R 为实数集),ab b a b a ++=*。 (1)说明(,)S *是否构成群; (2)在S 中解方程732=**x 。

4 一棵树T 中,有3个2度结点,一个3度结点,其余结点都是树叶。 问T 中有几个结点?

五、应用题(本题共1小题,每小题10分,共10分)

下图给出的赋权图表示六个城市f e d c b a ,,,,,及架起城市间直接通讯线路的预测造价。

给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小总造价。 。

六、证明题(本题共3小题,每小题8分,共24分)

1.设{1,2,,9A =???,在A A ?上定义关系:,,R a b c d R <<><>>∈当且仅当

c b

d a +=+,证明R 是A A ?上的等价关系,并求出[2,5]R <>.

2.设G 是群,H 是G 的子群,x G ∈,证明:1

1{|}x H x

xhx h H --=∈是G 的子群。

3.将下列命题形式化,并证明结论的有效性:所有有理数都是实数,某些有理数是整数。因此,某些实数是整数。

《离散数学》试题五

一、判断题(每题1分,共10分)

1.在命运题逻辑中,任何命题公式的主合取范式都是存在的,并且是惟一的。 ( )

2. 011是公式r q p →∧)(的成真赋值 ( )

3.))(())(())()((y G y x F x y yG x xF ??∧????∨?? ( )

4. )()())()((x xG x xF x G x F x ?∨??∨? ( )

5.三种重要的二元关系是等价关系、偏序关系和函数关系,它们的共同特点是都具有自反性 。 ( )

6. 设F,R 都是二元关系,则(F ·R)-1

=F -1

·R -1

。 ( ) 7.设n 是任意一个正整数,则一定存在阶是n 的群. ( ) 8. 布尔代数是有界格,也是分配格. ( ) 9.无向完全图n K (n>2)一定是哈密顿图 ( ) 10.阶数至少是2 树的每一条边都是桥,因而它的

边连通度是1. ( )

二、空题(每小题2分,共20分)

1. 谓词公式?x(P(x,y)∧ ?tQ(t,z)→R(x,y,t))中量词?的辖域是 ___________________。

2.设F(x):x 是人,H(x,y):x 与y 一样高,在一阶逻辑中,命题“人都不一样高”的符号化形式为_______ ___。

3.q p q p →?∧∨)(从公式分类角度来看,它为__________式。

4.设R={<1,1>,<1,2>,<2,3>},则R 的对称闭包是 。

5.设A,B 是集合,=?=?==B A B A B A 那么,,2,4,3

6.<6Z ,⊕〉是模6加群, 则它的生成元是 。2⊕4= 7.整数加群是循环群,其生成元是 和 。

8.设≤><,A 是偏序集,如果_________ ____, 则称≤><,A 是(偏序)格。

9.一棵二叉树先序遍历得ABDECF ,中序遍历得DBEACF,则后序遍历的结果是________________。

10. r=5,当s= 时,完全二部图s r K ,才可能存在完美匹配。 。

三、计算题(1-4题每题8分;5-6题每题10分,共52分)

1.R 1={<1,2>,<2,1>,<2,3>,<3,2>},R 2={<2,2>,<2,3>,<3,1>} 求:(1) R 1-1

(2) R 1·R 2 (3)R 22

(4)t(R 1)(传递闭包) 2.设G=?

??

?

??

???? ??-=???? ??-=???? ??--=???? ??=0110,0110,1001,10

01d c b a ,G 上的运算是矩阵乘法。已知G 构成群。 (1)指出个元素的阶; (2)找出G 的全部子群;

(3)在同构的意义下G 是4阶循环群还是Klein 四元群?

3.(1)在一棵有2个2度顶点,4个3度顶点,其余顶点都是树叶的无向树中应该有几片树叶?

(2)画出两棵非同构的满足上述条件的无向树 。

4.设为一个偏序集,其中,A={1,2,3,4,6,9,24,54},R 是A 上的整除关系。

(1)画出的哈斯图; (2)求A 的极大元和极小元; (3)求B={4,6}的上确界和下确界。

5.求公式r q p ?→)(的主和取范式(化成M 1∧M 2∧M 3的形式)。

6.画一棵带权为2,2,2,3,3,4,5,8的最优二叉树T ,并计算它的权W (T )。 四、证明题(每小题6分,共18分) 1.前提: )(),(s r q r q p →→→→ 结论: s q p →∧)(

2.定理(子群判别法1)设H 是群的非空子集,则H ≤G 当且仅当 (1)?a ,b ∈H , a ?b ∈H ; (2)?a ∈H ,a -1

∈H 。

利用上述定理证明:设H 是群的非空有限子集。若H 关于?封闭,则H 是G 的子群。 3.用数学归纳法证明n 阶无向树T 有n-1边。

《离散数学》试题六

一、判断题(每题1分,共10分)

1.任何命题公式都存在惟一的析取范式。 ( )

2. 封闭的公式在任何解释下都变成命题。 ( )

3. )()(s r q p ∨∧∨?的层数是 3 ( )

4.))(())((x A B x x A B x →???→??. ( )

5. 设A,B,C 是三集合,已知A B =A C ,则一定有B =C. ( )

6.矩阵的等价、相似、合同都是等价关系。 ( )

7.已知a 是群集的二阶元,则={a,a 2

}. ( ) 8.有界格中某元的的补元不止一个,则它不是分配格。 ( ) 9.有向图是强连通的,则它一定是单向连通的,也弱连通的。 ( ) 10.二部图3,3K 是欧拉图也是哈密顿图。 ( ) 二、填空题(每小题2分,共20分)

1.p q q p →?∧∨))((从公式的类型看,它属于 式。

2.?∧?))()((x B x A x ___________________。

3.设F(x):x 是人,H(x):x 呼吸,在一阶逻辑中,命题“凡人 都呼吸”的符号化形式为_______ _________。

4.6阶循环群有 个子群。

5. A={a,b},则A 的幂集P(A)到自身的双射有__ _个。

6. A={1,2,3},S 是A 上所有置换构成的集合,>< ,S 构成群,则单位元是 ,???

? ??123321的逆元是 ,该元是 阶元。

7.一个3阶有向图的度序列是2,2,4,入度序列是2,0,2,出度序列是 。 8.一无向图存在生成树的充分必要条件是 。 9.最优二叉树有n 片树叶,则它有 分支点。

10. 下图的点连通度等于 ,边连通度等于_________

。三、计算题(每小题10分,共50分)

1.设A={a,b,c},B={b,c,d},C={d,e,f},R 1={<1,2>,<2,2>, <2,3>,<3,3>},R 2={<2,2>,<2,3>,<3,4>} 求 (1) B A ? (2) A ⊕B (3) R 1-1

(4) R 1·R 2 (5) R 1在A 上的限制。

2.其中,A={1,2,3,4},R={<1,2>,<2,2>,<2,3>,<3,4>},R 是A 上的二元关系。 (1)画出的R 的关系图;

(2)求R 的自反、对称、传递闭包;

3.S=Q ×Q,其中Q 为有理数集合,定义S 上的二元运算*,

?,∈S ,*=,

(1)求<3,4>*<1,2>.

(2)已知<-1,3>*=<-5,1>,求a,b. (3)*是可交换的吗?是可结合的吗?

4.在一个无向图中有6条边,3度顶点和5度顶点各1个,其余顶点都是2度点,该图有几个顶点?

5.在下图中,用克鲁斯卡尔算法构造最小生成树,写出边添加到生成树的边序列,并画出生

成树。

a

四、证明题(共20分)

1.前提:))()(()),()((x H x G x x H x F x →?∧?? 结论:))()((x F x G x ?→?

2.已知>+<),(Z M n (即整数集上2阶方阵构成的集合关于矩阵的加法)构成

群,H=??

????????∈???? ??Z a a a 00 (1) >+<),(Z M n 的单位元是什么? ?

??

?

??-4321的逆元是什么? (2)证明: H 是>+<),(Z M n 的子群. 3.叙述并证明关于连通平面图的欧拉公式。

《离散数学》试题七

一、选择题(每小题 2 分,共 20 分)

1、使命题公式p→(p∧q)为假的赋值是 ( )

A.10

B.01

C. 00

D.11 2、令p :今天下雪了,q :路滑,则命题“虽然今天下雪了,但是路不滑”可符号化为( )

A. p ∧┐q B .p ∨┐q C.p ∧q D .p →┐q

3、设B 不含有x ,下列一阶逻辑等值式不正确...

的是 ( ) A.B x xA B x A x ∧??∧?)())(( B.B x xA B x A x →??→?)())(( C. )()())()((x xB x xA x B x A x ?∧??∧?

D. )()())()((x xB x xA x B x A x ?∨??∨? 4、 设X ,Y ,Z 是集合,下列结论不正确...

的是( ) A .若X ?Y,则X Y=X B .(X-Y)-Z=X-(Y ∩Z) C .Φ=⊕X X D .)(~Y X Y X =-

5、设R 是集合A 上的二元关系,I A 是上的恒等关系,I A ?R 下面四个命题为真的是 ( )

A.R 是自反的

B.R 是传递的

C.R 是对称的

D.R 是反对称的 6、设函数f :N→N(N 为自然数集),f(n)=n+1,下面四个命题为真的是 ( ) A. f 是单射 B. f 是满射 C. f 是双射的 D.f 非单射非满射 7、集合A={1,2,3,4},则对 A 的元素进行分类正确的是( )

A. {Φ,{1,2},{3,4}}

B. {{1,2,3},{3,4}}

C. {{1},{3,4}}

D. {{1,2,3,4}} 8、无向完全图n K 有 ( )条边

A. n

B. n 2

C. n(n-1)

D. n(n-1)/2 9、 设G 是连通平面图,G 中有6个顶点8条边,则G 的面的数目是( )

A .2

B .3

C .4

D .5

10、一颗二叉树后序遍历的结果是bdeca ,中序遍历的结果是badce ,则 根结点的右子树有( )结点。

A .1

B .2

C .3

D .4 二、填空题(每题2分,共10分)

1、量词否定等值式???)(x xA ___________________。

2、设R 是A={1,2,3,4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R 的对称闭包是 。

3、A={1,2},>⊕<),(A P 是群,⊕是集合的对称差运算。该群的单位元是 ,{1}的逆元是 。

4、图G 是平面图的充分必要条件是没有收缩到___或 的子图。

5、无向图G=,V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,c)},则它的邻接矩阵为 ,该图的补图有 条边。 三、计算题(每题8分,共 48分)

1、求公式r q p ?→)(的主和取范式(化成M 1∧M 2∧M 3的形式)。

2、R 1={<1,2>,<1,3>,<2,3>,<3,3>}, R 2={<2,2>,<2,3>,<3,4>}, (1) 求 R 1-1

(2) 求12R R (3)R 1是函数吗? 3、(1)叙述等价关系的定义;

(2)设A={1,2,3,4},R={<1,1>,<2,2>,<3,3>,<4,4>,<2,3>,<3,2>}是A 上的等价关系吗?如果是,给出R 确定的对A 的分类;如果不是,请说明理由。

4、已知>?+<,),(2R M (即实数集上2阶方阵构成的集合关于矩阵的加法和乘法)构成的环。 (1)>?+<,),(2R M 的零位元是什么?单位元是什么? (2)说明 >?+<,),(2R M 不是无零因子环; (3)举例说明?不满足消去律。

5、求A 到其余顶点的最短路径。

6

4A

B

C D

E

6、求下PERT 图中各顶点的最早完成时间TE(v i )和最迟完成时间TL(v i ),并求出关键路径。

a e

j

四、证明题( 22分)

1、前提: ))()(()),()()((x R x F x x H x G x F x ∧?∧→?

结论: ))()()((x G x R x F x ∧∧?

2、设是可交换群,H={a ∈G |?k ∈N(正整数集),使a k

=e},

证明H 是G 的子群。

3、用数学归纳法证明,含有n 片树叶的最优二叉树有n-1个分支点.

《离散数学》试卷 八

一、选择题(每小题 2分,共 20 分。请将答案填在下面的表格内)

1、从集合分类的角度看,命题公式可分为( )

A.永真式、矛盾式

B. 永真式、可满足式、矛盾式

C. 可满足式、矛盾式

D. 永真式、可满足式 2、设B 不含有x ,))((B x A x →?等值于 ( )

A.B x xA →?)(

B.))((B x A x ∨?

C.B x xA →?)(

D.))((B x A x ∧? 3、设S,T,M 是集合,下列结论正确的是( )

A .如果S ∪T=S ∪M ,则T=M

B .如果S-T=Φ,则S=T

C .S S S =⊕

D .)(~T S T S =- 4、设R 是集合A 上的偏序关系,则R 不一定是( )

A.自反的

B. 对称的

C. 反对称的

D. 传递的 5 设R 为实数集,定义R 上4个二元运算,不满足结合律的是( )。 A. f 1(x,y)= x+y B. f 2(x,y)=x-y C. f 3(x,y)=xy D. f 4(x,y)=max{x,y} 6、设是一个格,则它不满足( )

A.交换律

B. 结合律

C. 吸收律

D. 消去律 7、设A={1,2},则群>?<),(A P 的单位元和零元是( )

A. Φ与A

B. A 与Φ

C. {1}与Φ

D. {1}与A 8、下列编码是前缀码的是( ).

A.{1,11,101}

B.{1,001,0011}

C. {1,01,001,000}

D.{0,00,000} 9、下图中既是欧拉图又是哈密顿图的是( )

A . 9K

B .10K

C .3,2K

D .3,3K 10、下图所示的二叉树中序遍历的结果是( )

离散数学考试题详细答案

离散数学考试题(后附详细答案) 一、命题符号化(共6小题,每小题3分,共计18分) 1.用命题逻辑把下列命题符号化 a)假如上午不下雨,我去看电影,否则就在家里读书或看报。 设P表示命题“上午下雨”,Q表示命题“我去看电影”,R表示命题“在家里读书”,S表示命题“在家看报”,命题符号化为:(PQ)(PRS) b)我今天进城,除非下雨。 设P表示命题“我今天进城”,Q表示命题“天下雨”,命题符号化为:Q→P或P→Q c)仅当你走,我将留下。 设P表示命题“你走”,Q表示命题“我留下”,命题符号化为:Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”,Q(x)表示“x是有理数”,命题符号化为: x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x,总存在y使得xy=1。 设R(x)表示“x是实数”,E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为: x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为:F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题(共6道题,共32分) 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋值。 (5分) (P→(Q→R))(R→(Q→P))(PQR)(PQR) ((PQR)→(PQR)) ((PQR) →(PQR)). ((PQR)(PQR)) ((PQR) (PQR)) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 (PQR(PQR(PQR(PQR(PQR(PQR 2.设个体域为{1,2,3},求下列命题的真值(4分) a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。(4分) x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假,并说明原因。(每小题2分,共4分)

离散数学试题与参考答案

《离散数学》试题及答案 一、选择题:本题共5小题,每小题3分,共15分,在每小题给出的四个选项中,只有一项是符合题目要求的。 1. 命题公式Q Q P →∨)(为 ( ) (A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取范式 2.设P 表示“天下大雨”, Q 表示“他在室内运动”,则命题“除非天下大雨,否则他不在室内运动”符号化为( )。 (A). P Q →; (B).P Q ∧; (C).P Q ?→?; (D).P Q ?∨. 3.设集合A ={{1,2,3}, {4,5}, {6,7,8}},则下式为真的是( ) (A) 1A (B) {1,2, 3}A (C) {{4,5}}A (D) A 4. 设A ={1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B C )= ( ) (A) {<1,c >,<2,c >} (B) {,<2,c >} (C) {,} (D) {<1,c >,} 5. 设G 如右图:那么G 不是( ). (A)哈密顿图; (B)完全图; (C)欧拉图; (D) 平面图. 二、填空题:本大题共5小题,每小题4分,共20分。把答案填在对应题号后的横线上。 6. 设集合A ={,{a }},则A 的幂集P (A )= 7. 设集合A ={1,2,3,4 }, B ={6,8,12}, A 到B 的关系R =},,2,{B y A x x y y x ∈∈=><, 那么R -1= 8. 在“同学,老乡,亲戚,朋友”四个关系中_______是等价关系. 9. 写出一个不含“→”的逻辑联结词的完备集 . 10.设X ={a ,b ,c },R 是X 上的二元关系,其关系矩阵为 M R =???? ? ?????001001101,那么R 的关系图为

(完整版)离散数学试卷及答案

离散数学试题(A卷答案) 一、(10分)求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解:(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、(10分)在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断: 甲说:王教授不是苏州人,是上海人。 乙说:王教授不是上海人,是苏州人。 丙说:王教授既不是上海人,也不是杭州人。 王教授听后说:你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人? 解设设P:王教授是苏州人;Q:王教授是上海人;R:王教授是杭州人。则根据题意应有: 甲:?P∧Q 乙:?Q∧P 丙:?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以,丙至少说对了一半。因此,可得甲或乙必有一人全错了。又因为,若甲全错了,则有?Q ∧P,因此,乙全对。同理,乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为:

((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此,王教授是上海人。 三、(10分)证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系,则由定理4.19知,tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )='R ,进而有tsr (R )?t ('R )='R 。 综上可知,tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、(15分)集合A ={a ,b ,c ,d ,e }上的二元关系R 为R ={}, (1)写出R 的关系矩阵。 (2)判断R 是不是偏序关系,为什么? 解 (1) R 的关系矩阵为: ??? ??? ? ? ? ?=100001100010100 10110 11111 )(R M (2)由关系矩阵可知,对角线上所有元素全为1,故R 是自反的;ij r +ji r ≤1,故R 是反对称的;可计算对应的关系矩阵为:

离散数学试题与答案

试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b

二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。

离散数学试卷及答案一

一、单项选择题(本大题共15小题,每小题1分,共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的,请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G,如果它的所有结点的度数都是偶数,那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图,G中有11个顶点5个面,则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中,表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数,·是复数乘法运算,则G=<{1,-1,i,-i},·>是群,下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集,A为集合,A的幂集为P(A),+、-、/为数的加、减、除运算,∩为集合的交 运算,下列系统中是代数系统的有( ) A.〈Z,+,/〉 B.〈Z,/〉 C.〈Z,-,/〉 D.〈P(A),∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q,*〉Q是全体有理数集,*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合,*是矩阵乘法运算 C.〈Z,ο〉,Z是整数集,ο定义为xοxy=xy,?x,y∈Z D.〈Z,+〉,Z是整数集,+是数的加法运算 7.设A={1,2,3},A上二元关系R的关系图如下: R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c},A上二元关系R={〈a,a〉,〈b,b〉,〈a,c〉},则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系,要使Ix∪{〈a,b〉,〈b,c〉,〈c,a〉,〈b,a〉}∪R为X上的 等价关系,R应取( ) A.{〈c,a〉,〈a,c〉} B.{〈c,b〉,〈b,a〉} C.{〈c,a〉,〈b,a〉} D.{〈a,c〉,〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下:论域D为实数集,a=0,f(x,y)=x-y,A(x,y):x

离散数学题库

常熟理工学院20 ~20 学年第学期 《离散数学》考试试卷(试卷库01卷) 试题总分: 100 分考试时限:120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题(每题2分,共20分) 1.下列表达式正确的有( ) (A)(B)(C)(D) 2.设P:2×2=5,Q:雪是黑的,R:2×4=8,S:太阳从东方升起,下列( )命题的真值为 真。 (A)(B)(C)(D) 3.集合A={1,2,…,10}上的关系R={|x+y=10,x,y A},则R 的性质为( ) (A)自反的(B)对称的(C)传递的,对称的(D)传递的 4.设,,其中表示模3加法,*表示模2乘法,在集合上 定义如下运算: 有称为的积代数,则的积代数幺元是( ) (A)<0,0> (B)<0,1> (C)<1,0> (D)<1,1> 5.下图中既不是Eular图,也不是Hamilton图的图是( ) 6.设为无向图,,则G一定是( ) (A)完全图(B)树(C)简单图(D)多重图 7.设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间”符号化为()。 (A) P Q (B)Q P (C)P Q (D) 8.在有n个结点的连通图中,其边数() (A)最多有n-1条(B)最多有n 条(C)至少有n-1条(D)至少有n条 9.设A-B=,则有() (A)B=(B)B(C)A B (D)A B 10.设集合A上有3个元素,则A上的不同的等价关系的个数为() (A)5 (B)7 (C)3 (D)6 二、填空题(每题2分,共20分)

1.n个命题变元组成的命题公式共有种不同的等价公式。 2.设〈L,≤〉为有界格,a为L中任意元素,如果存在元素b∈L,使,则称b是a 的补元。 3.设*,Δ是定义在集合A上的两个可交换二元运算,如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4.设T是一棵树,则T是一个连通且的图。 5.一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6.量词否定等价式? ("x)P(x) ?,? ($x)P(x) ?。 7.二叉树有5个度为2的结点,则它的叶子结点数为。 8.设是一个群,是阿贝尔群的充要条件是。9.集合S={α,β,γ,δ}上的二元运算*为 * αβγδ αδαβγ βαβγδ γβγγγ δαδγδ 那么,代数系统中的幺元是,α的逆元是。 10.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>} = 。 = 。 三、判断题(每题1分,共10分) 1.命题公式是一个矛盾式。() 2.,若,则必有。() 3.设S为集合X上的二元关系,则S是传递的当且仅当(S S)S。() 4.任何一棵二叉树的结点可对应一个前缀码。() 5.代数系统中一个元素的左逆元一定等于该元素的右逆元。() 6.一个有限平面图,面的次数之和等于该图的边数。() 7.A′B = B′A () 8.设*定义在集合A上的一个二元运算,如果A中有关于运算*的左零元θl和右零θr,则A中 有零元。() 9.一个循环群的生成元不是唯一的。() 10.任何一个前缀码都对应一棵二叉树。() 四、解答题(5小题,共30分) 1.(5分)什么是欧拉路?如何用欧拉路判定一个图G是否可一笔画出? 2.(8分)求公式 (P∨Q)R 的主析取范式和主合取范式。

离散数学试卷与答案22

一、单项选择题:(每小题1分,本大题共15分) 1.设A={1,2,3,4,5},下面( )集合等于A 。 A 、{1,2,3,4,5,6}; B 、}25{2≤x x x 是整数且; C 、}5{≤x x x 是正整数且; D 、}5{≤x x x 是正有理数且。 2.设A={{1,2,3},{4,5},{6,7,8}},下列各式中( )是错的。 A 、A ?Φ; B 、{6,7,8}∈A ; C 、{{4,5}}?A ; D 、{1,2,3}?A 。 3.六阶群的子群的阶数可以是( )。 A 、1,2,5; B 、2,4; C 、3,6,7; D 、2,3 。 4.设B A S ??,下列各式中( )是正确的。 A 、 domS ? B ; B 、domS ?A ; C 、ranS ?A ; D 、domS ? ranS = S 。 5.设集合Φ≠X ,则空关系X Φ不具备的性质是( )。 A 、自反性; B 、反自反性; C 、对称性; D 、传递性。 6.下列函数中,( )是入射函数。 A 、世界上每个人与其年龄的序偶集; B 、、世界上每个人与其性别的序偶集; B 、 一个作者的专著与其作者的序偶集; D 、每个国家与其国旗的序偶集。 7.><,*G 是群,则对*( )。 A 、满足结合律、交换律; B 、有单位元,可结合; C 、有单位元、可交换; D 、每元有逆元,有零元。 8.下面( )哈斯图所描述的偏序关系构成分配格。 9.下列( )中的运算符都是可交换的。 A 、→∨∧,,; B 、?→,; C 、???,,; D 、∧∨, 。

10.设G 是n 个结点、m 条边和r 个面的连通平面图,则m 等于( )。 A 、n+r-2 ; B 、n-r+2 ; C 、n-r-2 ; D 、n+r+2 。 11.n 个结点的无向完全图n K 的边数为( )。 A 、)1(+n n ; B 、2)1(+n n ; C 、)1(-n n ; D 、2 )1(-n n 。 12.下列图中( )是根树。 A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a G ; B 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a G ; C 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a G ; D 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 。 13.设P :2×2=5,Q :雪是黑的,R :2×4=8,S :太阳从东方升起,下列( )命题的真 值为真。 A 、R Q P ∧→ ; B 、S P R ∧→ ; C 、R Q S ∧→ ; D 、)()(S Q R P ∧∨∧。 14.下面( )命题公式是重言式。 A 、R Q P ∨→ ; B 、)()(Q P R P →∧∨ ; C 、)()(R Q Q P ∨?∨ ; D 、))()(())((R P Q P R Q P →→→→→→。 15.设L(x):x 是演员,J(x):x 是老师,A(x , y):x 钦佩y ,命题“所有演员都钦佩某些老师” 符号化为( )。 A 、)),()((y x A x L x →?; B 、))),()(()((y x A y J y x L x ∧?→? ; C 、)),()()((y x A y J x L y x ∧∧??; D 、)),()()((y x A y J x L y x →∧?? 。 二、填空题:(每空1分,本大题共15分) 1.设}2,121{Z x x x x M ∈≤≤=整除,被,}3,121{Z x x x x N ∈≤≤=整除,被, 则 =?N M ,=-N M 。 2.在一个有n 个元素的集合上,可以有 种不同的关系,有 种不同的函数。 3.若关系R 是反对称的,当且仅当关系矩阵中 ,在

离散数学试卷及答案(2)

一、填空 20% (每小题2分) 1、 P :你努力,Q :你失败。“除非你努力,否则你将失败”的翻译为 ;“虽然你努力了,但还是失败了”的翻译为 。 2、论域D={1,2},指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ,a 2 ,…,a 8},B i 是S 的子集,则由B 31所表达的子集是 。 3、 设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则R= (列举法)。 R 的关系矩阵M R = 。 5、设A={1,2,3},则A 上既不是对称的又不是反对称的关系R= ; A 上既是对称的又是反对称的关系R= 。 6、设代数系统,其中A={a ,b ,c}, 则幺元是 ;是否有幂等 性 ;是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。

9、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% (每小题2分) 1、在下述公式中是重言式为( ) A .)()(Q P Q P ∨→∧; B .))()(()(P Q Q P Q P →∧→??; C .Q Q P ∧→?)(; D .)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为( )。 A .0; B .1; C .2; D .3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A .3; B .6; C .7; D .8 。 4、 设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A .4; B .5; C .6; D .9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为

离散数学试卷二十三试题与答案

试卷二十三试题与答案 一、单项选择题:(每小题1分,本大题共10分) 1.命题公式)(P Q P ∨→是( )。 A 、 矛盾式; B 、可满足式; C 、重言式; D 、等价式。 2.下列各式中哪个不成立( )。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?; B 、)()())()((x xQ x xP x Q x P x ?∨??∨?; C 、)()())()((x xQ x xP x Q x P x ?∧??∧?; D 、Q x xP Q x P x ∧??∧?)())((。 3.谓词公式)())()((x Q y yR x P x →?∨?中的 x 是( )。 A 、自由变元; B 、约束变元; C 、既是自由变元又是约束变元; D 、既不是自由变元又不是约束变元。 4.在0 Φ之间应填入( )符号。 A 、= ; B 、?; C 、∈; D 、?。 5.设< A , > 是偏序集,A B ?,下面结论正确的是( )。 A 、 B 的极大元B b ∈且唯一; B 、B 的极大元A b ∈且不唯一; C 、B 的上界B b ∈且不唯一; D 、B 的上确界A b ∈且唯一。 6.在自然数集N 上,下列( )运算是可结合的。 (对任意N b a ∈,) A 、b a b a -=*; B 、),max(b a b a =*; C 、b a b a 5+=*; D 、b a b a -=*。 7.Q 为有理数集N ,Q 上定义运算*为a*b = a + b – ab ,则的幺元为( )。 A 、a ; B 、b ; C 、1; D 、0。 8.给定下列序列,( )可以构成无向简单图的结点度数序列。 A 、(1,1,2,2,3); B 、(1,1,2,2,2); C 、(0,1,3,3,3); D 、(1,3,4,4,5)。 9.设G 是简单有向图,可达矩阵P(G)刻划下列 ( )关系。 A 、点与边; B 、边与点; C 、点与点; D 、边与边。 10.一颗树有两个2度结点,1个3度结点和3个4度结点,则1度结点数为( )。 A 、5; B 、7; C 、9; D 、8。

离散数学模拟试卷和答案

北京语言大学网络教育学院 《离散数学》模拟试卷一 注意: 1.试卷保密,考生不得将试卷带出考场或撕页,否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律,考试作弊全部成绩以零分计算。 3.本试卷满分100分,答题时间为90分钟。 4.本试卷分为试题卷和答题卷,所有答案必须答在答题卷上,答在试题卷上不给分。 一、【单项选择题】(本大题共15小题,每小题3分,共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上,可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则( )。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集,则一定有( )。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是( )。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射,下列表述中错误的是( )。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习,q:小李取得好成绩,命题“除非小李努力学习,否则他不能取得好成绩”的符号化形式为( )。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有( )。 [A]3个 [B]6个 [C]8个 [D]9个

离散数学全部试卷

离散数学试题与答案试卷一 一、填空 20% (每小题2分) 1.设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且(N :自然数集,E + 正偶数) 则 =?B A 。 2.A ,B ,C 表示三个集合,文图中阴影部分的集合表达式为 。 3.设P ,Q 的真值为0,R ,S 的真值为1,则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4.公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5.若解释I 的论域D 仅包含一个元素,则 )()(x xP x xP ?→? 在I 下真值为 。 6.设A={1,2,3,4},A 上关系图为 则 R 2 = 。 8.图的补图为 。 二、选择 20% (每小题 2分) 1、下列是真命题的有( ) A . }}{{}{a a ?; B .}}{,{}}{{ΦΦ∈Φ; C . }},{{ΦΦ∈Φ; D . }}{{}{Φ∈Φ。 2、下列集合中相等的有( ) A B C

?;B.{Φ,3,4};C.{4,Φ,3,3};D.{3,4}。 A.{4,3}Φ 3、设A={1,2,3},则A上的二元关系有()个。 A.23 ;B.32 ;C.332?;D.223?。 4、设R,S是集合A上的关系,则下列说法正确的是() Rο是自反的; A.若R,S 是自反的,则S Rο是反自反的; B.若R,S 是反自反的,则S Rο是对称的; C.若R,S 是对称的,则S Rο是传递的。 D.若R,S 是传递的,则S 5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下 t s t s p A R= ∧ =则P(A)/ R=() < > ∈ s (| || |} {t ) , ( | , A.A ;B.P(A) ;C.{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}};D.{{Φ},{2},{2,3},{{2,3,4}},{A}} 7、下列函数是双射的为() A.f : I→E , f (x) = 2x ;B.f : N→N?N, f (n) = ; C.f : R→I , f (x) = [x] ;D.f :I→N, f (x) = | x | 。 (注:I—整数集,E—偶数集,N—自然数集,R—实数集) 8、图中从v1到v3长度为3 的通路有()条。 A.0;B.1;C.2;D.3。 9、下图中既不是Eular图,也不是Hamilton图的图是() 10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有()个4 度结点。 A.1;B.2;C.3;D.4 。

离散数学期末试卷及答案

一.判断题(共10小题,每题1分,共10分) 在各题末尾的括号内画 表示正确,画 表示错误: 1.设p、q为任意命题公式,则(p∧q)∨p ? p ( ) 2.?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3.初级回路一定是简单回路。( ) 4.自然映射是双射。( ) 5.对于给定的集合及其上的二元运算,可逆元素的逆元是唯一的。( ) 6.群的运算是可交换的。( ) 7.自然数集关于数的加法和乘法构成环。( ) 8.若无向连通图G中有桥,则G的点连通度和边连通度皆为1。( ) 9.设A={a,b,c},则A上的关系R={,}是传递的。( ) 10.设A、B、C为任意集合,则A?(B?C)=(A?B)?C。( ) 二、填空题(共10题,每题3分,共30分) 11.设p:天气热。q:他去游泳。则命题“只有天气热,他才去游泳”可符号 化为。 12.设M(x):x是人。S(x):x到过月球。则命题“有人到过月球”可符号 化为。 13.p?q的主合取范式是。 14.完全二部图K r,s(r < s)的边连通度等于。 15.设A={a,b},,则A上共有个不同的偏序关系。 16.模6加群中,4是阶元。 17.设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>},则R的传递闭包t(R) = 。. 18.已知有向图D的度数列为(2,3,2,3),出度列为(1,2,1,1),则有向图D的入度

列为。 19.n阶无向简单连通图G的生成树有条边。 20.7阶圈的点色数是。 三、运算题(共5小题,每小题8分,共40分) 21.求?xF(x)→?yG(x,y)的前束范式。 22.已知无向图G有11条边,2度和3度顶点各两个,其余为4度顶点,求G 的顶点数。 23.设A={a,b,c,d,e,f},R=I A?{,},则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。 24.求图示带权图中的最小生成树,并计算最小生成树的权。 25.设R*为正实数集,代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群?是群者,求其单位元及每个元素的逆元。 四、证明题(共3小题,共20分) 26 (8分)在自然推理系统P中构造下述推理的证明: 前题:p→(q∨r),?s→?q,p∧?s 结论:r 27 (6分)设是群,H={a| a∈G∧?g∈G,a*g=g*a},则是G的子群 28.(6分)设G是n(≥3)阶m条边、r个面的极大平面图,则r=2n-4。

离散数学试卷及答案(17)

一、判断正误20% (每小题2分) 1、设A.B. C是任意三个集合。 (1)若A∈B且B?C,则A?C。() (2)若A?B且B∈C,则A?C。() (3)若A?B且B∈C,则A?C。() (4)A) ( ) ( ) (C A B A C B ⊕ = ⊕。() (5)(A–B)?C=(A?C)-(B?C)。() 2、可能有某种关系,既不是自反的,也不是反自反的。() 3、若两图结点数相同,边数相等,度数相同的结点数目相等,则两图是同构的。() 4、一个图是平面图,当且仅当它包含与K 3, 3 或K 5 在2度结点内同构的子图。() 5、代数系统中一个元素的左逆元并一定等于该元素的右逆元。() 6、群是每个元素都有逆元的半群。() 二、8% 将谓词公式)) , ( ) ( ) ( ) (( )) , ( ) ( )( (z y Q z y P y y x Q x P x? ∧ ? → → ?化为前束析取范式与前束合取范式。 三、8% 设集合A={a,b,c,d}上的关系R={,,,}写出它的关系矩阵和关系图,并用矩阵运算方法求出R的传递闭包。 四、9% 1、画一个有一条欧拉回路和一条汉密尔顿回路的图。 2、画一个有一条欧拉回路,但没有一条汉密尔顿回路的图。 3、画一个有一条欧拉回路,但有一条汉密尔顿回路的图。

五、10% 证明:若图G是不连通的,则G的补图G 是连通的。 六、10% 证明:循环群的任何子群必定也是循环群。 七、12% 用CP规则证明: 1.F A F E D D C B A →?→∨∧→∨,。 2.?∨??∨?(()()())()()((x P x x Q x P x )()x Q x 。 八、10% 用推理规则证明下式: 前提: ))()()(()),()()(())()()(((y W y M y y W y M y x S x F x ?∧?→?→∧? 结论:?→?)()((x F x S ))(x 九、13% 若集合X={(1,2),(3,4),(5,6),……} }|,,,{12212211y x y x y x y x R +=+>><><<= 1、证明R 是X 上的等价关系。 2、求出X 关于R 的商集。 一、 填空 20%(每小题2分)

离散数学试题及解答

离散数学 2^m*n 一、选择题(2*10) 1.令P:今天下雨了,Q:我没带伞,则命题“虽然今天下雨了,但是我没带伞”可符号化为()。 (A)P→?Q (B)P∨?Q (C)P∧Q (D)P∧?Q 2.下列命题公式为永真蕴含式的是()。 (A)Q→(P∧Q)(B)P→(P∧Q) (C)(P∧Q)→P (D)(P∨Q)→Q 3、命题“存在一些人是大学生”的否定是(A),而命题“所有的人都是要死的”的否定 是()。 (A)所有人都不是大学生,有些人不会死 (B)所有人不都是大学生,所有人都不会死 (C)存在一些人不是大学生,有些人不会死 (D)所有人都不是大学生,所有人都不会死 4、永真式的否定是()。

(A)永真式(B)永假式(C)可满足式(D)以上均有可能 5、以下选项中正确的是()。 (A)0= ? (B)0 ? (C)0∈? (D)0?? 6、以下哪个不是集合A上的等价关系的性质?() )。 (A)2 (B)4 (C)3 (D)5 10.连通图G是一棵树,当且仅当G中()。 (A)有些边不是割边(B)每条边都是割边 (C)无割边集(D)每条边都不是割边

二、填空题(2*10) 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D是正整数集合,则命题?x?y(xy=y)的真值是______。 3、令R(x):x是实数,Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 4 5 6、设 7 8 (1)若A去,则C和D中要去1个人; (2)B和C不能都去; (3)若C去,则D留下 五、(15分)设A={1,2,3},写出下列图示关系的关系矩阵,并讨论它们的性质:

离散数学试卷及答案

填空10% (每小题 2 分) 1、若P,Q,为二命题,P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数,都存在比它大的实数” 令F(x):x 为实数,L(x, y) : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP(x) xQ(x)的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号,公式其余的部分不变,这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元,A的论域为D,A(x)关于y 是自由的,则被称为存 在量词消去规则,记为ES。 选择25% (每小题分) 1、下列语句是命题的有()。 A、明年中秋节的晚上是晴天; C、xy 0 当且仅当x 和y 都大于0; D 、我正在说谎。 2、下列各命题中真值为真的命题有()。 A、2+2=4当且仅当3是奇数; B、2+2=4当且仅当 3 不是奇数; C、2+2≠4 当且仅当3是奇数; D、2+2≠4当且仅当 3 不是奇数; 3、下列符号串是合式公式的有() A、P Q ; B、P P Q; C、( P Q) (P Q); D、(P Q) 。 4、下列等价式成立的有( )。 A、P QQ P ; B、P(P R) R; C、P (P Q) Q; D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ,且A1 A2 A n B 则 ( )。 A、称A1 A2 A n 为 B 的前 件; B 、称 B 为A1,A2 A n 的有效结论

C 、 x(M (x) Mortal (x)) ; D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为:个体域 D={2} ,P(x) :x>3, Q(x) :x=4则 A 的 真 值为( ) 。 A 、 1; B 、 0; C 、 可满足式; D 、无法判定。 9、 下列等价关系正确的是( )。 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) xP(x) Q ; D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在( )。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②; B 、④; C 、⑤; D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ,B 为二合式公式,且 B ,则( )。 7、 A 、 A C 、 A B 为重言式; B 、 B ; E 、 A B 为重言式。 人总是要死的”谓词公式表示为( )。 论域为全总个体域) M (x ) : x 是人; Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ; B M (x) Mortal (x)

最新离散数学试卷及答案 (1)

离散数学试题(A卷答案) 一、证明题(10分) 1) (P∧Q∧A→C)∧(A→P∨Q∨C)? (A∧(P?Q))→C。 证明: (P∧Q∧A→C)∧(A→P∨Q∨C) ?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((P∧Q∧A)∨(A∧?P∧?Q))∨C ??( A∧((P∧Q)∨(?P∧?Q)))∨C ??( A∧(P?Q))∨C

?(A∧(P?Q))→C 2) ?(P↑Q)??P↓?Q。 证明:?(P↑Q)??(?(P∧Q))??(?P∨?Q))??P↓?Q。 二、分别用真值表法和公式法求(P→(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式,并写出其相应的成真赋值和成假赋值(15分)。 证明: 公式法:因为(P→(Q∨R))∧(?P∨(Q?R)) ?(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R)) ?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))

?(?P∨Q∨R)∧(?P∨Q∨?Q)∧(?P∨Q∨?R)∧(?P∨R∨?Q)∧(?P∨R∨?R) ?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R) ? M∧5M∧6M 4 ? m∨1m∨2m∨3m∨7m 所以,公式(P→(Q∨R))∧(?P∨(Q?R))为可满足式,其相应的成真赋值为000、001、010、011、111:成假赋值为:100、101、110。 真值表法:

式,其相应的成真赋值为000、001、010、011、111:成假赋值为:100、101、110。 三、推理证明题(10分) 1)?P∨Q,?Q∨R,R→S P→S。 证明:(1)P附加前提

离散数学试卷及答案(1)

一、填空 20% (每小题2分) 1.设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且(N :自然数集,E + 正偶数) 则 =?B A 。 2.A ,B ,C 表示三个集合,文图中阴影部分的集合表达式为 。 3.设P ,Q 的真值为0,R ,S 的真值为1,则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4.公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5.若解释I 的论域D 仅包含一个元素,则 )()(x xP x xP ?→? 在I 下真值为 。 6.设A={1,2,3,4},A 上关系图为 则 R 2 = 。 7.设A={a ,b ,c ,d},其上偏序关系R 的哈斯图为 则 R= 。

8.图的补图为 。 9.设A={a ,b ,c ,d} ,A 上二元运算如下: 那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆元分别为 。 10.下图所示的偏序集中,是格的为 。 二、选择 20% (每小题 2分) 1、下列是真命题的有( ) A . }}{{}{a a ? ; B .}}{,{}}{{ΦΦ∈Φ; C . }},{{ΦΦ∈Φ; D . }}{{}{Φ∈Φ。 2、下列集合中相等的有( ) A .{4,3}Φ?; B .{Φ,3,4}; C .{4,Φ,3,3}; D . {3,4}。 3、设A={1,2,3},则A 上的二元关系有( )个。

A.23 ;B.32 ;C.332?;D.223?。 4、设R,S是集合A上的关系,则下列说法正确的是() R 是自反的; A.若R,S 是自反的,则S R 是反自反的; B.若R,S 是反自反的,则S R 是对称的; C.若R,S 是对称的,则S R 是传递的。 D.若R,S 是传递的,则S 5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下 t s p R= t s ∈ =则P(A)/ R=() < > ∧ A ) (| || |} ( , {t , | s A.A ;B.P(A) ;C.{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}};D.{{Φ},{2},{2,3},{{2,3,4}},{A}} 6、设A={Φ,{1},{1,3},{1,2,3}}则A上包含关系“?”的哈斯图为() 7、下列函数是双射的为() A.f : I→E , f (x) = 2x ;B.f : N→N?N, f (n) = ; C.f : R→I , f (x) = [x] ;D.f :I→N, f (x) = | x | 。 (注:I—整数集,E—偶数集,N—自然数集,R—实数集) 8、图中从v1到v3长度为3 的通路有()条。 A.0;B.1;C.2;D.3。 9、下图中既不是Eular图,也不是Hamilton图的图是()