离散数学结构试题集4

第一篇：离散数学结构试题集4

第1章

一.填空题

1.2.公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。

3.4.5.6.7.全体小项的析取式必为____________________式。

8.P,Q为两个命题，则德摩根律可表示为7.全体小项的析取式必为_________式。

9.P,Q为两个命题，则吸收律可表示为____________________。

10.设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为_____ _______________。

11.设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为_________ ___________。

12.13.14./ 36

15.设P、Q为两个命题，交换律可表示为____________________。

16.17.命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________。

18.19.20.21.P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为_______________ _____。

22.23.24.一个重言式和一个矛盾式的合取是____________________。

25.全体小项的析取式为____________________。

26.命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________。

27.28.设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为____________________。

29./ 36 30.二.选择题

1.2.3.在除﹁之外的四大联结词中，满足结合律的有几个（）。

A.2

B.3

C.4

D.1

4.判断下列语句哪个是命题（）。

A.你喜欢唱歌吗？

B.若7+8＞18，则三角形有4条边。

C.前进！

D.给我一杯水吧！

5.6.7.8.永真式的否定是（）

A.永真式 B.永假式 C.可满足式 D.A--D均有可能 / 36

9.下面哪一个是假命题（）。

A.如果2是偶数，那么一个公式的析取范式唯一。

B.如果2是偶数，那么一个公式的析取范式不唯一。

C.如果2是奇数，那么一个公式的析取范式唯一。

D.如果2是奇数，那么一个公式的析取范式不唯一。

10.设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班 ”的符号化形式为（）。

A.p→q

B.q→p

C.p→┐q

D.┐p→q

11.设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好 成绩”的符号化形式为（）。

A.p→q

B.q→p

C.┐q→p

D.┐p→q

12.下面4个推理定律中，不正确的为（）。

A.A=>(A∨B)(附加律)

B.(A∨B)∧┐A=>B(析取三段论)

C.(A→B)∧A=>B(假言推理)

D.(A→B)∧┐B=>A(拒取式)

13.使命题公式p→(p∧q)为假的赋值是（）。

A.10

B.01

C.00

D.11

14.令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。

A.p∧┐q

B．p∨┐q C.p∧q

D．p→┐q

15.一个公式在等价意义下，下面哪个写法是唯一的（）。

Ａ．析取范式

B．合取范式

Ｃ．主析取范式

D．以上答案都不对

16.令p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学了”可符号化

为（）。

A．p→┐q

B．p∨┐q C．p∧q

D．p∧┐q

17.下列各组公式中哪组互为对偶（）。(P为原子命题，A为复合命题)A.P,P

B.P, ┐P C.A,(A*)*

D.A,A 18./ 36

19.20.21.22.23.24.25.下列语句哪个是命题（）。

A.9+5≤12

B.x+3=5 C.我用的计算机CPU主频是1G吗？

D 我正在说谎。/ 36

26.27.28.n个命题变元可产生（）个互不等价的大项。

A.n

B.n2

C.2n

D.2n

29.下列各命题中真值为真的命题有（）。

A.2+2=4当且仅当3是奇数

B.2+2=4当且仅当3不是奇数

C.2+2≠4当且仅当3是奇数

D.2+2≠5当且仅当3不是奇数

30.下列语句哪个不是命题（）。

A.雪是黑的。

B.天气多好啊！

C.今天下雨。

D 我学英语，或者我学日语。

三.判断题

1.“我正在说谎。”是一个命题。

（）

2.一个命题标识符如表示确定的命题，就称为命题常量。（）

3.“她昨天做了一顿或两顿饭。”是个原子命题。（）

4.命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一 个命题。（）

5.如果A和B是合式公式，那么(A→ B)是合式公式。（）

6.原子谓词公式是合式公式。（）

7.一般来说，n个命题变元组成的命题公式共有2n中真值情况。（）

8.任何两个重言式的合取或析取，仍然是一个重言式。（）/ 36 9.重言式和矛盾式的析取是重言式。（）

10.在真值表中，一个公式的真值为F的指派所对应的大项的析取，即为此公式的主析取范式。（）

11.从假的命题出发，能证明任何命题。（）

12.全体小项的析取式永为假。（）

13.连接词↑和↓是可交换的，也是可结合的。（）

14.P→Q =〉P→P∧Q。（）

15.由n个命题变元组成不等值的命题公式的个数为2n。（）

四.计算题

1.2.3.4.5.6.7.8.9./ 36

10.11.12.13.14.15.五.证明题 / 36 1.2.3.第2章

一.填空题

1.2.3.4.5.6.7./ 36 8.9.10.11.12.13.14.15.16.17./ 36 18.19.20.21.22.23.24.25.二.选择题 / 36 1.2.3.4./ 36

5.6.7.8.9./ 36

10.11.12.13./ 36 14.15.16.17.18./ 36

19.20.21.22.23.24./ 36

25.26.27.28.29./ 36 30.三.判断题

1.“如果1+2=3，则4+5=9。”是真命题。（）

2.约束变元换名时，一定要更改为作用域中没有出现的变元名称。（）

3.4.简单命题函数由一个谓词和一些客体变元组成。（）

5.单独一个谓词，不是完整的命题。（）

6.任意一个谓词公式均和一个前束范式等价。（）

7.8.9.10.11.12.13./ 36

14.15.四.计算题 1.2.3.4.5.6.7.8.9./ 36

10.五.证明题 1.2.3.4.第3章

一.填空题

1.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则A∪B=_________________。

2.A，B，C表示三个集合，图中阴影部分的集合表达式为____________________。/ 36

3.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则A°B=_______________。

4.设A={1，2，3，4}，A上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图_ ________________。

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

则 R=_______________________。

6.设A={1，2，3}，则A上既不是对称的又不是反对称的关系为R=____________________。

7.设A={1，2，3}，则A上既是对称的又是反对称的关系为R=_____________________。

8.设|A|=3，则A上有________________个二元关系。

9.偏序集〈Ρ（{a,b}），⊆〉的哈斯图为________________。

10.集合A={2，3，6，12，24，36}上偏序关系R的Hass图为 / 36

则集合B={2，3，6，12}的上界是_________________。

11.对集合X和Y，设|X|=m，|Y|=n，则从X到Y的函数有__________________个。

12.关系R的自反闭包r(R)＝________________。

13.关系R的对称闭包s(R)＝_________________。

14.关系R的传递闭包t(R)＝_____________________。

15.若R是集合A上的偏序关系，则R满足___________________。

16.若R是集合A上的等价关系，则R满足____________________。

17.若R是集合A上的相容关系，则R满足__________________。

18.集合A={2，3，6，12，24，36}上偏序关系R的Hass图为

则集合B={2，3，6，12}的上确界是_____________。/ 36 19.设A，B是两集合，其中A={a，b，c}，B={a，b}，则A-B=_______________。

20.设R={,,}，则ran(R)=______________。

21.设R={,,}，则dom(R)=________________。

22.设R={,,}，则FLD(R)=_________________。

23.设A={a，b}，B＝｛1，2，3｝，则A×B=__________________。

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

25.设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的自反闭包是__ ________________。

26.设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的传递闭包是__ __________________。

27.集合A={2，3，6，12，24，36}上偏序关系R的Hass图为

则集合B={2，3，6，12}的下确界是__________________。

28.设A,B是集合，|A|=3，|B|=4，|A∩B|=2，那么|A∪B|=_____________。

29.集合A有n个元素，则A的幂集有___________个元素。

30.一个集合的非平凡子集包括___________和全集。

31.集合A={2，3，6，12，24，36}上偏序关系R的Hass图为 / 36

则集合B={2，3，6，12}的下界是_______________。

32.集合A={∅,a}，则A的幂集P(A)=____________。

33.设A,B为集合，则命题A-B=∅<=>A=B的真值为（填“真”或“假”或“不可判别”）____ ____。

34.设A={a,b,c,d}，A上的等价关系R=IA∪{(b,c),(c,b),(a,d),(d,a)}，则对 应于R的A的划分是_______________。

35.给定集合A＝{1,2,3,4,5},R是A上的等价关系，且此关系R能产生划分{{1,2},{3,4,5}}, 则R=_________________。

二.选择题

1.设A={1,2,3}，则A上有（）个二元关系。

A.23

B.32

C.2^{2^3}

D.2 ^{3^2}

2.设X，Y，Z是集合，下列结论不正确的是（）。

A．若X⊆Y,则X∩Y=X

B．(X-Y)-Z=X-(Y∩Z)C．X⊕X=∅

D．X-Y=X∩(~Y)

3.设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R的性质是（）。

A.自反、对称、传递的 B.自反、对称、反对称的C.对称、反对称、传递的 D.只有对称性

4.设R和S是P上的关系，P是所有人的集合，R={|x,y∈P∧x是y的父亲}，S={|x, y∈P∧x是y的母亲} 则S-1 °R表示关系（）。

A、{|x,y∈P∧x是y的丈夫} B、{|x,y∈P∧x是y的孙子或孙女} C、∅ / 36 D、{|x,y∈P∧x是y的祖父或祖母}

5.若X是Y的子集，则一定有（）。

A.X不属于Y

B.X∈Y

C.X真包含于Y

D.X∩Y=X

6.下列式子中正确的是（）。

A．∅=0

B． ∅∈∅

C．∅∈{a，b}

D．∅∈{∅}

7.下面那条不是偏序关系的性质：（）

A).自反性

B)相容性

C)传递性

D)反对称性

8.关于闭包运算，下面那条性质不对（）

A)rs(R)=sr(R)

B)rt(R)=tr(R)C)st(R)=ts(R)

D)rtr(R)=tr(R)

9.划分必然诱导一个（）

A）等价关系

B)偏序关系

C)同余关系

D)同态关系

10.设某集合有m个元素，则可以构成（）个子集。

A)m

B)m!

C)2m

D)2m-1

11.A, B为两个集合，如果A⊆B，则下面那个是错误的。（）

A)A∩B≠∅

B)~B⊆~A

C)(B-A)∪A=B

D)(B-A)∪A=A

12.设S={1,2,3}，S上关系R的关系图为

则R具有（）性质。

A．自反性、对称性、传递性；

B．反自反性、反对称性；

C．反自反性、反对称性、传递性；

D．自反性。

13.设A={∅，{1}，{1，3}，{1，2，3}}则A上包含关系“⊆”的哈斯图为（/ 36）

14.集合A={1，2，3，4}上的偏序关系图为

则它的哈斯图为（）。/ 36

15.集合A={1，2，3，4}上的偏序关系为）。

16.设R，S是集合A上的关系，则下列（A、R,S自反的，则R°S是自反的；

B、若R,S对称的，则R°S是对称的；

C、若R,S传递的，则R°S是传递的；

D、若R,S反对称的，则R°S是反对称的

17.设X为集合，|X|=n，在X上有（A、n2；

B、2n；

C、2^{2^n}；2。

18.下图描述的偏序集中，子集{b,e,f}的上界为（/ 36，则它的Hass图为（）断言是正确的。）种不同的关系。

D、2^{n^）。}

A、b,c ；

B、a,b ；

C、b；

D、a,b,c。

19.设R，S是集合A上的关系，则下列说法正确的是（）。

A．若R，S 是自反的，则R°S是自反的；

B．若R，S 是反自反的，则R°S是反自反的；

C．若R，S 是对称的，则R°S是对称的；

D．若R，S 是传递的，则R°S是传递的。

20.设R是集合A上的二元关系，IA是A上的恒等关系，IA⊆R下面四 个命题为真的是（）。

A.R是自反的B.R是传递的C.R是对称的 D.R是反对称的

21.已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（）

A．10

B．5

C．20

D．13

22.设X，Y，Z是集合，下列结论不正确的是（）。

A．若X⊆Y,则X∩Y=X

B．(X-Y)-Z=X-(Y∩Z)C．X ⊕X=∅

D．X-Y=X∩(~Y)

23.设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划 分是（）。

A．{{a},{b,c},{d}}

B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}}

D．{{a,b},{c,d}}

24.设R是集合A上的二元关系，IA是A上的恒等关系，IA⊆R下面四 个命题为真的是（）A.R是自反的B.R是传递的C.R是对称的 D.R是反对称的

25.集合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}}

26.设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是（）。

(A){2}∈A

(B){a}⊆A

(C)∅⊆{{a}}⊆B⊆E

(D){{a},1,3,4}⊂B

27.设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备（）.(A)自反性

(B)传递性

(C)对称性

(D)反对称性

28.设A, B为集合，当（）时A－B＝B.(A)A＝B(B)A⊆B(C)B⊆A(D)A＝B＝∅.29.设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有（）。

(A)自反性

(B)传递性

(C)对称性

(D)以上答案都不对 / 36

30.下列关于集合的表示中正确的为（）。

(A){a}∈{a,b,c}(B){a}⊆{a,b,c}(C)∅∈{a,b,c}

(D){a,b}∈{a,b,c}

31.设R和S是集合A上的关系，若R和S是传递的，则（）

(A)R∩S是传递的；

(B)R∪S是传递的；

(C)R°S是传递的；

(D)以上都不对。

32.设集合X为人的全体，在X上定义关系R、S为R={| a，b∈X∧a是b的父亲}，S={|a，b∈X∧a是b的母亲|，那么关系{| a，b∈X∧a是b的祖母}的表达式为（）

(A)R°S

(B)R-1 °S

(C)S°R

(D)R°S-1

33.下列命题正确的是

（）(A){1,2}⊆{{1,2},{1,2,3},1}

(B){1,2}⊆{1,{1,2},{1,2,3},2}(C){1,2}⊆{{1},{2},{1,2}}

(D){1,2}∈{1,2,{2},{1,2,3}}

34.下列关系矩阵所对应的关系具有反自反性的是（）

35.设R1和R2是集合A上的相容关系，下列关于R1 &opl us;R2的说法正确的是（）

(A)一定是相容关系；

(B)一定不是相容关系；

(C)可能是也可能不是相容关系；

(D)一定是等价关系。

三.判断题

1.设集合A={ a,b,c,d,e,f}，那么S1= {∅, {a,b},{c,d},{f}}是集合A的一个覆盖。（）

2.恒等关系既是等价关系又是偏序关系。

（）/ 36 3.设F,R都是二元关系,则(F°R)-1=F-1 °R-1。

（）

4.设A,B,C是三集合，已知A∪B＝A∪C，则一定有B＝C。

（）

5.设集合A={ a,b,c,d,e,f}，那么S1= { {a,b},{c,d,e},{e,f } }是集合A的划分。（）

6.集合A上的等价关系确定了A的一个划分。（）

7.集合A上的偏序关系的三个性质是反自反性、对称性和传递性。

（）

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

（）

9.R的自反传递闭包也一定满足自反关系，传递关系。（）

10.偏序集合中，链上的任何两个元素都是有关系的。（）

11.设R是实数集，R上的关系f={||x-y|<2,x,y∈R}，R是相容关系。（）

12.空集是任何集合的真子集。（）

13.设集合A、B、C为任意集合，若A×B = A×C，则B = C。

（）

14.若集合A上的关系R是对称的，则R-1也是对称的。

15.空集是唯一的。

（）

16.全集不是唯一的。

（）

17.对于一个给定的集合，其划分是唯一的。

（）

18.设R为X上的二元关系，则R是对称的<=>R=Rc。

（）

19.设R为X上的二元关系，则R是反对称的<=>R∩Rc⊆IX。

（）

20.设R为X上的二元关系，则R是传递的<=>(R°R)⊆R。

（）

四.计算题

1.设S={1,2,3,4,6,8,12,24}，“≤”为S上整除关系，问：

（1）偏序集的Hass图如何？

（2）偏序集的极小元、最小元、极大元、最大元是什么?

2.A={a，b，c，d}，R={,,},R是集合A上的二元关系。/ 36（1）画出的R的关系图；

（2）求R的自反闭包和对称闭包。

3.在实数平面上，画出关系R={|x-y+2>0∧x-y-2<0}，并判定关系的特殊性质。

4.R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}，(1)求 R1-1

(2)求R2 °R1

5.设集合A＝{a,b,c,d}上的关系R＝{,,,}，写出它的关系矩阵和关 系图，并用矩阵运算方法求出R的传递闭包。

6.设R是自然数集合N上的关系，且xRy<=>x+2y=10。

(1)求dom R；

(2)说明R具有的性质(自反、反自反、对称、反对称、传递)。

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

（1）画出R的哈斯图；

（2）求A的极大元和极小元；

（3）求B={4,6}的上确界和下确界

8.集合S={1，2，3，4，5}，找出S上的等价关系，此关系能产生划分{{1，2}，{3}，{4，5 }}，并画出关系图。

9.集合上的关系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>},写出关系矩阵，画出关系图并讨论R的性质。

10.下图是偏序集的哈斯图，（1）写出集合A,R;（2）求A的极大元和极小元；

（3）求B={e,f}的上确界和下确界。

11.设A={1,3,5,7}，定义A上的二元关系R:∈R <=> a

/ 36

12.A={a,b,c,}, R1={,,,},R2={,,}, 求：(1)R1-

1(2)R2 °R1

13.R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>} 求：(1)R1-1

(2)R1·R2

(3)R12

14.设A是正整数m=20的因子的集合，并设≤为整除关系。画出A上的偏序集合图(哈斯图)，并指出A中的极大元和极小元，最大元和最小元。

五.证明题

1.令I是整数集合，I上关系R定义为：R＝{|x-y可被3整除}，求证R是自反、对称和传 递的。

2.设A、B、C是任意集合，证明：A-(B∪C)=(A-B)∩(A-C)

3.如果集合A上的关系R和S是反自反的、对称的和传递的，证明：是A上的等价关系。

4.集合A的任一划分S诱导了A的一个等价关系R。

5.A, B为两个任意集合，求证：A－(A∩B)=(A∪B)－B.6.试证明实数集R上的小于等于关系“≤” 是偏序关系。

7.设R,S为二元关系, 试证明(R°S)c =S c °Rc.8.设A、B、C为任意三个集合，证明A×(B∪C)=(A×B)∪(A×C)。

第4章

一.填空题

1.设f是集合X到集合Y的一个关系，如果对∀x∈X，有唯一的y∈Y使得∈f，则称关系

f为X到Y的__________。

2.设X，U，V，Y都是实数集，f1:X->U，且f1(x)=ex； f2:U->V，且f2(u)=u(1+u)；f3:V->Y，且f3

(v)=cosv。那么f3°f2 °f1的 定义域是__________ ____。

3.设X，U，V，Y都是实数集，f1:X->U，且f1(x)=ex；

/ 36 f2:U->V，且f2(u)=u(1+u)；f3:V->Y，且f3

(v)=cosv。那么f3°f2 °f1(x)=______________。

4.F={,,}______（“是”或者“不是”）函数。

5.F={,}_______（“是 ”或者“不是”）函数。

6.设f，g是自然数集N上的函数，∀x∈N，f(x)=x+1，g(x)=2x，则f°g(x)＝_______。

7.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是

______函数。

8.设函数f:A→B, 则f 的逆关系是函数当且仅当f 是________（“入射”或“满射”或“ 双射”）。

9.若函数f:A→B存在逆函数f-1,则 f-1 °f =_________。

10.若函数f:A→B存在逆函数f-1,则f° f-1=_________。

11.如果IA=_______，则称IA：A→A为集合X上的恒等函数。

12.函数f:I->I,f(j)=j(mod3)______（“是”或者“不是”）入射函数。

13.函数射函数。

_____（“是”或者“不是”）满14.函数f:I->I,f(j)=j(mod3)_______(“是”或者“不是”)双射函数。

15.函数f:I->N,f(i)=|2i|+1_______（“是”或者“不是”）入射函数。

16.函数________（“是”或者“不是”）满射函数。

17.函数f:I->I,f(j)=j(mod3)______（“是”或者“不是”）双射函数。

/ 36 18.函数f:R->R,f(r)=2r-15_____（“是”或者“不是”）入射函数。

19.函数f:I->I,f(j)=j(mod3)_______（“是”或者“不是”）满射函数。

20.函数f:I->I,f(j)=j(mod3)_______（“是”或者“不是”）双射函数。

二.选择题

1.设集合A，B是有穷集合，且|A|=m，|B|=n，则从A到B有（）个不同的双射函 数。

A、n ；

B、m ；

C、n!；

D、m!。

2.下列命题正确的有（）。

A、若g,f是满射，则g°f是满射；

B、若g°f是满射，则g,f都是满射；

C、若g°f是单射，则g,f都是单射；

D、若g°f是双射，则f是双射。

3.设f，g是函数，当（）时，f=g。

A、∀x∈domf 都有f(x)=g(x)；

B、domg⊆domf且f⊆g；

C、f与g的表达式相同；

D、domg=domf,rangef=rangef

4.N是自然数集，定义f:N->N,f(x)=(x)mod3（即x除以3的余数），则f是（。

A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。

5.下列关系中能构成函数的是（）。

A、{|(x,y∈N)∧(x+y<10)}；B、{|(x,y∈R)∧(y=x2)}；

C、{|(x,y∈R)∧(y2 =x)}； D、{|(x,y∈I)∧(x≡y mod3)}

6.下面函数（）是单射而非满射。

A、f：R->R，f(x)=-x2 +2x-1； B、f:Z+->R，f(x)=ln x；

C、f:R->Z，f(x)=[x],[x]表示不大于x的最大整数；

D、f:R->R，f(x)=2x+1。

7.若函数g和f的复合函数g°f 是双射，则（）一定是正确的。

A、g是入射；B、f是入射；C、g是双射；D、f是满射。

8.X={a，b，c，d，e}，Y={1，2，3，4}，f从X到Y的映射，其中f(a)=2, f(b)=4, f(c)=1, f(d)=3,f(e)=4,则f是（）。

A双射

B 满射

C 单射

D 以上都不是

9.对于下面函数f的描述，那条不对（）

A)f(x)的像必然唯一存在B)如果f存在逆函数，则必是满射的

/ 36）C)如果f是入射的，则必存在逆函数

D)如果f是双射的，则必是入射的

10.设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是（）。

A.f是单射

B.f是满射

C.f是双射的D.f非单射非满射

三.判断题

1.若X和Y的元素个数相同，即|X|=|Y|，则f : X->Y是入射的当且仅当它是一个满射。（）

2.设f : X->Y是满射，即对任意的y∈Y，必存在x∈X，使得f(x)= y成立。（）

3.一个函数必然是一个关系。（）

4.一个关系就是一个函数。（）

5.函数f : X->Y就是从集合X到集合Y的一个映射。（）

四.计算题

1.设R是实数集合，σ,τ,φ是R上的三个映射，σ(x)= x+3, τ(x)= 2x, φ(x)＝ x/4 ,试求复合映射σ•τ，σ•σ, σ•φ, φ•τ，σ•φ•τ.2.下面有三个关系图，判断它们是函数否？如果不是，请说明原因。

3.设A={1,2,3,4},B={x,y,z,w},决定下列(1)--(5)的每个关系R是不是从A到B的一个函数。如果是一个函数,找出其定义域和值域,并确定它是不是入射的或满射的。

(1){<1,x>,<2,x>,<3,z>,<4,y>};(2){<1,z>,<2,x>,<3,y>,<4,z>,<2,w>};(3){<1,z>,<2,w>,<3,x>,<4,y>};(4){<1,w>,<2,w>,<4,x>}(5){<1,y>,<2,y>,<3,y>,<4,y>}。

/ 36

4.设集合A={1,2,3}, f、g是集合A到A的函数，f={<1,2>,<2,3>,<3,1>}，g={<1,2>,<2,1>, <3,3>}, 计算f °g，g °f。

5.设集合A={1,2,3},B={a,b}, f:A->B, 且f={<1,a>,<2,b>,<3,b>}，试判断f是不是一个函 数?如果是函数，是否存在逆函数？

五.证明题

1.令g οf 是一个复合函数。若g 和 f 是满射，则g οf是满射的。

2.设f °g是复合函数，证明：如果f °g是满射的，那么f是满射的。

3.设f °g是复合函数，证明：如果f °g是入射的，那么g是入射的。

/ 36

第二篇：离散数学期末试题

离散数学考试试题（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)M0∧M1

m2∨m3∨m4∨m5∨m6∨m7

二、（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上的二元关系，则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。

若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)R。则 ''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的关系矩阵为： ''''10M(R)000111111010101

00110001(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；rij＋rji≤1，故R是反对称的；可计算对应的关系矩阵为：

10M(R2)000由以上矩阵可知R是传递的。

111111010101M(R)

00110001

五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。证明：因为

∈(A－B)×Cx∈(A－B)∧y∈C

(x∈A∧xB)∧y∈C

(x∈A∧y∈C∧xB)∨(x∈A∧y∈C∧yC)(x∈A∧y∈C)∧(xB∨yC)(x∈A∧y∈C)∧(x∈B∧y∈C)∈(A×C)∧(B×C)∈(A×C)－(B×C)所以，(A－B)×C＝(A×C－B×C)。

六、（10分）设f：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f、g和h。

解 因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。

由hgf＝IA，得f＝hg；由fhg＝IB，得g＝fh；由gfh＝IC，得h＝gf。－

1－1

－1－1－1

－1

七、（15分）设是一代数系统，运算*满足交换律和结合律，且a*x＝a*yx＝y，证明：若G有限，则G是一群。

证明 因G有限，不妨设G＝{a1，a2，…，an}。由a*x＝a*yx＝y得，若x≠y，则a*x≠a*y。于是可证，对任意的a∈G，有aG＝G。又因为运算*满足交换律，所以aG＝G＝Ga。令e∈G使得a*e＝a。对任意的b∈G，令c*a＝b，则b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由运算*满足交换律得e*b＝b，所以e是关于运算*的幺元。对任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由运算*满足交换律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。

八、（20分）（1）证明在n个结点的连通图G中，至少有n－1条边。

证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。

设G中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。

2（2）给定简单无向图G＝，且|V|＝m，|E|＝n。试证：若n≥Cm1＋2，则G是哈密尔顿图。

2证明 若n≥Cm。1＋2，则2n≥m－3m＋6（1）

2若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝

wVd(w)＜m＋(m－2)(m－3)＋m＝m－

23m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。离散数考试试题（B卷及答案）

一、（10分）使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)

(P∧Q)∨(P∧Q)(QP)∧(P∨Q)(Q∨P)∧(P∨Q)(P∧Q)∨(Q∧Q)∨(P∧P)∨(P∧Q)(P∧Q)∨P

(P∧Q)∨(P∧(Q∨Q))(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)所以，(PQ)(P∧Q)(QP)∧(P∨Q)。

二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。

解 设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为： AB∨C，BA，DCAD

(1)A 附加前提(2)AB∨C P(3)B∨C T(1)(2)，I(4)BA P(5)AB

T(4)，E(6)B T(1)(5)，I(7)C T(3)(6)，I(8)DC P(9)D T(7)(8)，I(10)AD CP

三、（10分）证明xy(P(x)Q(y))(xP(x)yQ(y))。xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)(xP(x)yQ(y))

四、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解 P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}}

五、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)画出R的关系图。(2)写出R的关系矩阵。

(3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为：

10M(R)11反自反的；由于矩阵不对称，R不是对称的；

经过计算可得

1011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是10M(R2)111011101100M(R)，所以R是传递的。00

六、（15分）设函数f：R×RR×R，f定义为：f()＝。(1)证明f是单射。(2)证明f是满射。(3)求逆函数f。

(4)求复合函数ff和ff。

证明(1)对任意的x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。

(2)对任意的∈R×R，令x＝－1－

1uwuwuwuwuw，y＝，则f()＝<＋，－22222uw>＝，所以f是满射。2(3)f()＝<－1－1uwuw，>。22－1

－1(4)ff()＝f(f())＝f()＝<

xyxyxy(xy)，>＝

444

55ff()＝f(f())＝f()＝＝<2x，2y>。

七、（15分）给定群，若对G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a*b＝(a*b)，3试证是Abel群。

证明 对G中任意元a和b。

因为a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。

于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。

由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。

八、（15分）（1）证明在n个结点的连通图G中，至少有n－1条边。

证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。

设G中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。

（2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝是不连通的例子。解 下图满足条件但不连通。

12344

333334

34333

4333

133

113

122244 6

第三篇：大学离散数学复习试题

离散数学练习题目

一、选择题

1．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是错的。

A、A； B、{6，7，8}A； C、{{4，5}}A； D、{1，2，3}A。

2.已知集合A={a,b,c},B={b,c,e},则 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ

3.下列语句中，不是命题的是____A_________ A.我说的这句话是真话； B.理发师说“我说的这句话是真话”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以这些煤不会燃烧；

4.下面___D______命题公式是重言式。

A.PQR ； B.(PR)(PQ)；C.(PQ)(QR)；

D、(P(QR))((PQ)(PR))。

5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3

6．设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为___D______。

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))。7.关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是__B_____ A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）

B．z是该谓词公式的约束变元

C．（x）的辖域是P（x,y）D．x是该谓词公式的约束变元 8． 设SAB，下列各式中____B___________是正确的。

A、domSB ； B、domSA； C、ranSA； D、domS  ranS = S。9．设集合X，则空关系X不具备的性质是____A________。

A、自反性； B、反自反性； C、对称性； D、传递性。

10.集合A，R是A上的关系，如果R是等价关系，则R必须满足的条件是__D___ A.R是自反的、对称的 B.R是反自反的、对称的、传递的 C.R是自反的、对称的、不传递的 D.R是自反的，对称的、传递的 11.集合A={a,b,c,d},B={1,2,3},则下列关系中__ACD______是函数

A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} 已知集合 RA,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},则顶点2的入度和出度分别是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.设完全图Kn有n个结点(n≥2)，m条边，当下面条件__C____满足时，Kn中存在欧拉回路．

A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数 14.下面叙述正确的是____B______ A.二部图K3,3是欧拉图 B.二部图是平面图

K3,3是哈密尔顿图

C.二部图 K3,32

D.二部图K3,3是既不是欧拉图也不哈密尔顿图

15.已知某平面图的顶点数是12，边数是14，则该平面图有__D___个面 A.3 B.2 C.5 D.4 16．设G是n个结点、m条边和r个面的连通平面图，则m等于___A____。

A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面几种代数结构中，不是群的是___D____ A. B. C. D.(这里Z，Q，R，N分别表示整数集、有理数集、实数集、自然数集，+普通加法)

二、问答题

1.在程序设计过程中，有如下形式的判断语句： if(a>=0)if(b>1)if(c<0)cout<

请将这段程序化简，并说明化简的理由。解：简化的程序：

if(a>=0 && b>1 && c<0)cout<

设置命题变量： p: a>=0；q:b>1;r:c<0;s:cout<

A=P→(q→(r→s))经过等值演算可得，A与下面的公式是等值的 P∧q∧r→s

2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①证明R是偏序关系。

②写出偏序集（A，R）的极小元、极大元；最小元、最大元 ③写出A的子集B={1,2,3,6}的最小上界、最大下界

解：①根据整除性质可知，R满足自反性，反对称性，传递性。所以R是A上的偏序关系。

②偏序集（A，R）的极小元：1，极大元：5, 6，7，8，9 最小元：1； 最大元：无

③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1

3.(1)m个男孩子，n个女孩排成一排，任何两个女孩不相邻，有多少种排法？

(n<=m)插空问题

(2)如果排成一个园环，又有多少种排法？

解：(1)考虑5个男孩，5个女孩的情况

男孩的安排方法： _B_B_B_B_B_ 排列总数P(5,5)女孩的安排方法：6个位置安排5个女孩，排列中数 P(6,5)所以：总的排列方法数是 m!*p(m+1,n)

(2)考虑男孩的圆排列情况，结果是(m-1)!*p(m,n)

4.某商家有三种品牌的足球，每种品牌的足球库存数量不少于10只，如果我想买5只足球，有多少种买法？如果每种品牌的足球最少买一只，有多少种买法？

解：①这是一个多重集的组合问题

类别数是k=3，选取的元素个数是 r=5 多重集组合数的计算公式是 N所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由选取的球只有2个 k=3,r=2 N=C(3+2-1,2)=C(4,2)=6

(rk1)!C(kr1,r)

r!(k1)!

5．某软件公司将职工分为三种岗位。该公司65人，有些职工（例如项目管理人员、设计人员）可能从事不止一个岗位的工作。每个职工至少被分在一个岗位。现在软件设计岗位（岗位A）（包括需求分析、概要设计和详细设计等工作）的人数是15人，代码编写岗位（岗位B）的人数是32人，软件测试岗位（岗位C）的人数是28人，同时参加岗位A和岗位B的有12人, 同时参加岗位B和岗位C的有8人, 同时参加岗位A和岗位C组的有3人，问，三个岗位参加的有多少人？

解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 设S表示全班同学总人数，则 |S|=65 求：|A∩B∩C|=？

根据容斥原理：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因为每个同学至少参加一个小组，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三个小组都参加的人数是13人

6.证明组合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)

说明：也可以直接利用组合演算公式进行演算 7.求1228的个位数是多少? 解：1228的个位数就是1228 mod 10的余数1228mod10(12mod10)28mod1024*7mod10(27mod10)4mod108mod1064

8.已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于2, 问G至少有多少个顶点?

解：由握手定理∑d(v)=2m=20，度数为3的顶点有3个占去12度，还有8度由其余顶点占有，而由题意，其余顶点的度数可为0，1，当均为1时所用顶点数最少，所以应有8个顶点占有此8度，即G中至少有8+4=12个顶点。

9刑侦人员审一件盗窃案时，已经掌握的线索如下：（1）甲或乙盗窃了电脑。

（2）若甲盗窃了电脑，则作案时间不能发生在午夜前。（3）若乙证词正确，则在午夜时屋里灯光未灭。（4）若乙证词不正确，则作案时间发生在午夜前。（5）午夜时屋里灯光灭了。

请通过命题逻辑推理，推论出谁是真正的盗窃犯？（写出详细的推理步骤）解 设p： 甲盗窃了电脑，q： 乙盗窃了电脑，r： 作案时间发生在午夜前，s： 乙证词正确，t：午夜时屋里灯光灭了。

前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。

10.插入排序算法的时间T与数据规模n的递推关系如下，求出T与n的显示关系表达式

T(n)T(n1)n1 T(1)0

解：

T(n)T(n1)n1 T(n2)n2n1T(n3)n3n2n1 T(nk)nkn2n1T(nk)kn-(12k)k(k1)T(nk)kn2令n-k=1，那么 k=n-1，所以：

n(n1)n(n1)n(n1) T(n)T(1)0222答：T与n的显示关系是：T(n)

11.解下列一阶同余方程组

n(n1)2x1(mod 3)x2(mod 4)x3(mod 5)解：已知a11,a22,a33;m13,m24,m35 方程组的齐次通解是：xkLcm(1,2,3)6k 60k 根据中国剩余定理，特解是：

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)M1m2m320,M2m1m315,M3m1m212 111M1mod m1是下列同余方程的解

3)，解得：x=2，即M12 M1x1(mod m1)即20x1(mod11同理可解得：M23，M33 11 7

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)mod m（120221533123）mod 60111所以：(4090108)mod 60238mod 6058

同余方程组的解是 xxx06k58 60k

12.假设需要加密的明文数据是a=8,选取两个素数p=7,q=19,使用RSA算法： ① 计算出密钥参数

② 利用加密算法计算出密文c ③ 利用解密算法根据密文c反求出明文a 解：① 取 p=7,q=19;计算 n=p*q=7*19=133 计算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 选取较小的数w,使w与108互质, 5是最小的,于是w=5 计算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余数为1, 于是算出d=65 至此加密、解密参数计算完成：

公钥w=5,n=133.私钥d=65,n=133.② 加密

cmwmodn85mod133((82mod133)*(83mod133))mod133

(64*113)mod13350③ 解密

acdmodn5065mod133

aA0A6 其中，A050, Ai(Ai1)2

根据上述递推公式可以计算出：A1502mod133106,A21062mod13364

A3642mod133106，„„, A61062mod13364 aA0A6(50*64)mod1338

解密后的明文与原来的明文是相等的，所以算法正确。

13.设A={1，2，3，4，6，9，12，24},R定义为R{(a,b)|ab(mod 3)}，（1）证明R是一个等价关系；（2）写出A的商集；

14.基于字典序的组合生成算法

问题说明：假设我们需要从5个元素中选取3个的所有组合，已知组合个数为 C（５，３）＝１０，按字典序，其具体组合为： 123,124,125,134,135,145,234,235,245,345 所谓按字典序生成组合，就是已知当前的组合（例如135），求下一个组合（例如，145）。下面给出算法的函数头：

//数组s[]:函数运行前，保存当前的组合，函数结束后，是新生成的下一个组合 //n,r:表示从n个元素中选取r个元素的组合 void next_comb(int s[],int n,int r)解：

void next_comb(into s[],int n,int r){

int j,m,max_val;

max_val=n;

m=r;

while(s[m]==max_val)

{

m=m-1;

max_val=max_val-1;

}

s[m]=s[m]+1;

for(j=m+1;j

s[j]=s[j-1]+1;}

15.某单位要从A,B,C三人选派若干人出国考察, 需满足下述条件:(1)若A去, 则C必须去;(2)若B去, 则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案? 9

第四篇：离散数学10年7月份试题

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，{2}，{1，2}}，则下列表述正确的是(B)．

A．2AB．{1}AC．1AD．2  A

2．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为

(D)．A．6B．4C．3D．5

3．设无向图G的邻接矩阵为则G的边数为(B)．, A．1B．7C．6D．14 0111

11111 0011000010011010

4．设集合A={a}，则A的幂集为(C)． A．{{a}}B．{a，{a}}C．{，{a}}D．{，a} 5．下列公式中(B)为永真式． A．AB  ABB．AB  (AB)C．AB  ABD．AB  (AB)

二、填空题（每小题3分，本题共15分）

6．命题公式PP的真值是假（或F，或0）．7．若无向树T有5个结点，则T的边数为

8．设正则m叉树的树叶数为t，分支数为i，则(m-1)it

9．设集合A={1，2}上的关系R＝{<1, 1>,<1, 2>}，则在R中仅需加一个元素，就可使新得到的关系为对称的．10．(x)(A(x)→B(x，z)∨C(y))中的自由变元有z，y．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“今天上课．”翻译成命题公式．

设P：今天上课，则命题公式为：P．

12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．

设 P：他去操场锻炼，Q：他有时间，则命题公式为：P Q．

四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．

13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．

错误． 因为A中元素2没有B中元素与之对应，故f不是A到B的函数．

14．设G是一个有4个结点10条边的连通图，则G为平面图．

错误．不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．

五．计算题（每小题12分，本题共36分）

15．试求出（P∨Q）→（R∨Q）的析取范式．

（P∨Q）→（R∨Q） ┐(P∨Q)∨（R∨Q）

(┐P∧┐Q)∨（R∨Q）

(┐P∧┐Q)∨R∨Q（析取范式）

16．设A={{1}, 1, 2}，B={ 1, {2}}，试计算

（1）A∩B（2）A∪B（3）A （A∩B）．

（1）A∩B={1}（2）A∪B={1, 2, {1}, {2}}（3）A（A∩B）={{1}, 1, 2}

17．图G=，其中V={ a, b, c, d }，E={(a, b),(a, c),(a, d),(b, c),(b, d),(c, d)}，对应边的权值依次为1、2、3、1、4及5，试

（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值． 3（1）G的图形表示如图一所示：ad

01111011110111 5 11 51 b c1 0b c 图二 a 3d（2）邻接矩阵：图一

（3）最小的生成树如图二中的粗线所示：权为：1+1+3=5

六、证明题（本题共8分）

18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

证明：设xA，因为R自反，所以x R x，即< x, x>R；

又因为S自反，所以x R x，即< x, x >S．

即< x, x>R∩S

故R∩S自反．

第五篇：离散数学单元测试试题1

临沂大学2015—2016学第1学期

离散数学单元测试试题一

(适用于2014级计算机科学与技术、软件工程、网络工程专业本科学生)

一、选择题(共10题，每题3分，共30分)1.下列语句中为命题的是（D)。A.这朵花是谁的？ B.这朵花真美丽啊！C.这朵花是你的吗？ D.这朵花是他的。

2.若p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为(B)。A.p∨q

B.p∧┐q

C.p→┐q

D.p∨┐q 3.命题公式p∨q→q的公式类型为（D)。A.矛盾式 B.非重言可满足式 C.重言式

D.条件式

4.若F(x)：x是有理数，G(x)：x能被2整除，则“有的有理数能被2整除”，可符号化为（A)。

A.x(F(x)∧G(x))

B.F(x)∧G(x)

C.xF(x)

D.xG(x)5.设F(x)表示x是火车，G(x)表示y是汽车，H(x，y)表示x比y快，命题“某些汽车比所有火车慢”的符号化公式是（B)。

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)))6．设集合A={1,2,3},A上的关系R={<1,2>,<1,3>,<3,3>},则R具有(D)。A.自反性 B.传递性 C.对称性 D.以上答案都不对

######7.谓词公式x(P(x)∨yR(y))→Q(x)中的 x是(C)。A.自由变元 B.约束变元

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

8.设X、Y是两个集合且|X|＝n，|Y|＝m，则从X到Y可产生(A)个二元关系。A.n  m B.mn

C.2n m D.nm 9.下列关于集合的表示中正确的为(C)。A.{a}{a,b,c} B.{a}{a,b,c}

C.{a,b,c} D.{a,b}{a,b,c} 10．设集合A={1,2,3,4,5},下列哪些是集合A的划分(D)。A.{{1,2},{3,5}}

B.{{1,2,3,4},5} C.{ ,{1,2},{3},{4,5}} D.{{1},{2},{3},{4},{5}}

二、填空题(共10空，每空3分，共30分)1.设p：2＋2＝5，q：明天是阴天，则命题“只要2＋2＝5，那么明天是阴天”可符号化为 p->q，其真值是 1。

2.设p:你陪伴我，q:你代我叫车子，r:我出去，则“如果你不陪伴我或不代我叫车子,我就不出去。”的符号化形式为 ¬p/¬q->r。

3.设p: 天下雨，q: 天刮风，r: 我去书店，则“如果天不下雨并且不刮风，我就去书店”的符号化形式为。

4.设S(x)∶x是大学生；K(x)∶x是运动员。则“有些运动员不是大学生”的符号化为。

5.设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则“小李非常聪明且能干”的符号化形式为。

6.设F(x): x是人，G(x): x用右手写字，则“有的人并不用右手写字”的符号化形式为。

7.设S(x)：x是学生；L(x)：x喜欢英语。则“有些学生喜欢英语”的符号化为：。8.在公式x(P(z)→Q(x,z))∧zR(x,z)中，x的辖域是

，z的辖域是。

三、计算与证明(共2题，每题20分，共40分)1.用等值演算求下公式的主析取范式(p→q)∧r。

2.在命题逻辑自然推理系统中，构造下面推理的证明。前提： p∨q, q→r, p→s, ┐s，结论：r ∧

(p∨q)。