离散数学(上)模拟题

离散数学模拟试题离散数学模拟试题1一、单项选择题（本大题共8小题，每小题2分，共16分）1.p:a是2的倍数，q:a是4的倍数。

命题“除非a是2的倍数，否则a不是4的倍数。

”符号化为（）；A．p→q B．q→pC．p→?q D．?p→q2.设解释Ⅰ如下:个体域D＝{a,b}，F(a,a)= F(b,b)=0,F(a,b)=F(b,a)=1,在解释Ⅰ下,下列公式中真值为1的是（）；A. ?x?yF(x,y)B. ?x?yF(x,y)C. ?x?yF(x,y)D.??x?yF(x,y)3.设G为n阶m条边的无向简单连通图，下列命题为假的是A.G一定有生成树B.m一定大于等于nC.G不含平行边和环D.G的最大度?（G）≤n-14.设G为完全图K5，下面命题中为假的是（）A. G为欧拉图B.G为哈密尔顿图C. G为平面图D.G为正则图5.对于任意集合X,Y,Z,则A. X∩Y=X∩Z?Y=ZB. X∪Y=X∪Z?Y=ZC. X－Y=X－Z?Y=ZD. X⊕Y=X⊕Z?Y=Z6.下面等式中唯一的恒等式是A.A∪B∪C－(A∪B)=CB. A⊕A=AC. A－(B×C)=(A－B)×( A－C )D.A×(B－C)=(A×B)－(A×C)7.设R为实数集,定义*运算如下:a*b=∣a+b-ab∣, 则*运算满足A.结合律B.交换律C.有幺元D.冥等律8.在有补格L中, 求补A. 是L中的一元运算B.一定有唯一的补元C.不一定是L中的一元运算D.可能没有补元.二、填空题（本大题共8小题，每空3分，共24分）请在每小题的空格中填上正确答案。

错填、不填均无分。

1.含n个命题变项的重言式的主合取范式为.2.设个体域为整数集合Z，命题?x?y(xy=1)的真值为.3.任何一棵非平凡树至少有片树叶.4.已知n阶无向简单图G有m条边, 则G的补图G有条边.5.设R={〈{1},1〉,〈1,{1}〉, 〈2,{3}〉, 〈{3},{2}〉},则domR⊕ranR= .6.设A={1,2}, B={1,2,3},则从A到B的不同函数有个.7.如果无向连通图G有n个顶点m条边，并且m≥n，则G中必含有.8.设B为布尔代数,a,b,c∈B，则（a∧b）∧(a∨c)∨a的化简式.三、简答题（本大题共8小题，每小题5分，共40分）1.设p：2＋2＝4，q：3＋3＝7，r：4＋4＝8，求下列各复合命题的真值：(1)(p∧q)?r(2)(p?r)?(q?r)(3)(p∨┐q)→(q→r)(4) ┐q→(p?r)(5) (p∨q)→(┐p∧┐q∧r)2.求公式?x (┐?yF(x,y) →?zG(x,z))的前束范式.3.已知无向图G有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点的度数均为4，求4度顶点的个数.4.已知连通的平面图G的阶数n=6,边数m=8,面数r=4.求G的对偶图G*的阶数n*,边数m*,面数r*.5.设A={{a,{b}},c,{c },{a,b}},B={{a,b},{b}},计算(1)A∩B(2)A⊕B(3)P(B)6.设函数f:N→N,f(n)=2n+1，这里N是自然数的集合，回答f 是否为单射的、满射的或双射的？并说明理由。

一、填空1．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。

2．一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是__________________，其主合取范式是_________________。

3．设A={a,b,c}，B={b,c,d,e}，C={b,c}，则( A ⋃ ⊕＝____________。

4．幂集P(P(∅)) ＝________________。

5．设A为任意集合，请填入适当运算符，使式子A________A=∅；A________A’=∅成立。

6．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则D(R)=____________，R(R)=____________。

7．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，S n}，其中S i⊆A，S i≠Ø，i=1，2，…，n，且______ _____；进一步若_____ _______，则S是集合A的划分。

8．两个重言式的析取是____ ____式，一个重言式和一个永假式的合取式是式。

9．公式┐(P∨Q) ←→(P∧Q)的主析取范式是。

10. 已知Π={{a}{b,c}}是A={a,b,c}的一个划分，由Π决定的A上的一个等价关系是。

二、证明及求解1．求命题公式（P→Q）→（Q∨P）的主析取范式。

2．推理证明题1）⌝P∨Q，⌝Q∨R，R→S⇒P→S。

2) (∀x)(P(x)→Q(y)∧R(x))，(∃x)P(x)⇒Q(y)∧(∃x)(P(x)∧R(x))x)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。

3．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y=2试求R S R。

4．证明：R是传递的⇔R*R⊆R。

5．设R是A上的二元关系，S={<a, b>| 存在c∈A，使<a, c>∈R，且<c, b>∈R}。

离散数学练习题一、选择题1、G是一棵根树，则（A ）。

A、G一定是连通的B、G一定是强连通的C、G只有一个顶点的出度为0D、G只有一个顶点的入度为12、下面哪个语句不是命题（C ）。

A、中国将成功举办2008年奥运会B、一亿年前地球发生了大灾难C、我说的不是真话D、哈密顿图是连通的3、设R是实数集合，在上定义二元运算*：a，b∈R，a*b=a+b-ab，则下面的论断中正确的是（C ）。

A、0是*的零元B、1是*的幺元C、0是*的幺元D、*没有等幂元4、设G是群，当G有（D ）个元素时，不能肯定G是交换群。

A.4B.5C.6D.75、无向完全图K3的不同构的生成子图有（ D ）个。

A. 6B.5C. 4D. 36、在自然数N上定义的二元运算∙，满足结合律的是( C )。

A.a∙b=a－bB. a∙b=a+2bC. a∙b=max{a,b}D. a∙b=∣a－b∣7、设集合A＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是( D )。

A.1∈AB.{{4,5}}⊂AC. {1,2,3}⊆AD.∅∈A8、由5个结点可构成的根树中，其叉数m最多为( D )。

A.2B.3C.5D. 49、设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A是不封闭的？（D ）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的最小公倍数10、仅有一个孤立结点的图称为( B )。

A.零图B.平凡图C.补图D.子图11. 下列各组数中，哪个可以构成无向图的度数列（B ）。

A.1，1，1，2，2B.2，2，2，2，3C.1，2，2，4，6D.2，3，3，312. *是定义在Z上的二元运算，y*=∈+,，则*的幺元和零元分别是（D ）。

∀,xyyxxZyx-A.不存在，0B.0，1C.1，不存在D.不存在，不存在 13. 设N N N f ,:→为自然数，且⎪⎩⎪⎨⎧=为偶数若为奇数若x xx x f 21)(则})0({)0(f f 和分别是（B ）。

《离散数学》模拟试题一、（每小题3分，共30分）填空题：1．集合{1, {2}}的幂集为。

2．某人有8件衬衫、4条裤子、5双鞋，全套衣服共有种可能的搭配。

3．令P：明天下雨；Q：明天下雪。

R：我将去学校。

命题“除非明天不下雨并且不下雪，否则我将不去学校。

”的符号化形式为。

4．令F(x)：x会叫，G(x)：x会咬人，D(x)：x是狗。

命题“会叫的狗未必会咬人。

”符号化为。

5．设A、B为任意命题公式，用A、B表示的命题公式基本等价关系中，等价转换式为、蕴涵转换式为、假言易位为。

6．设|A|=3，则A上可定义个不同的关系、个不同的函数、个不同的双射函数。

7．〈A，R〉为偏序集，其中A={1, 2, 3, 4, 6, 9, 24, 54}，R是A上的整除关系，对A的子集B={1, 2, 3}，B的极大元为、上界为、上确界为。

8．集合A={1，2，3}，I A={＜x，x＞| x∈A})为A上的恒等关系，则I A 具有性质。

9．令S={a, b, c }，在S上定义的二元运算*如下运算表所示：则运算*（满足/不满足）交换律、单位元、零元。

10．设有代数系统B=＜S，*＞，其中载体S={a, b, c, d}，二元运算*定义为：分别给出B的三个不同子代数的载体、和。

二、（10分）设R为任意非空集合A上的关系，证明：R∪I A为R的自反闭包，其中I A为A上的相等关系。

三、1．（6分）用公式等价转换法证明：()()→→=∧→P Q R P Q R 2．（8分）用真值表法求公式()=⌝→∨的主析取范式和主合A P Q R取范式。

四、A={a, b, c, d, e }，R是A上的关系，且R={〈a, b〉，〈a, c〉，〈e, d〉}，设R*=tsr(R)，则R*为A上的等价关系。

1．（6分）给出R*的关系矩阵并画出R*的关系图；2．（6分）写出商集A/ R*。

五、（14分）用演绎法证明下述论断的正确性。

→1．()()∨→∧，()∨→⇒P UP Q R SS T U2．()(()())x H x∃⌝∀∨，()()x G x H xx F x G x∀→⌝，()(()())⇒()()∃⌝x F x六、（10分）函数f：A→B，g：B→C，复合函数f g：A→C。

北京语言大学网络教育学院《离散数学》模拟试卷一注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。

请监考老师负责监督。

2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。

3.本试卷满分100分，答题时间为90分钟。

4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。

一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。

1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。

[A] 3[B] 8[C]9[D]272、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。

[A] 3,8 [B]{}3 [C]{}8 [D]{}3,83、若X 是Y 的子集，则一定有（ ）。

[A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X4、下列关系中是等价关系的是（ ）。

[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→q7、设A={a,b,c},则A 到A 的双射共有（ ）。

[A]3个 [B]6个 [C]8个 [D]9个8、一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（）。

[A] G没有奇数度结点 [B] G有1个奇数度结点[C] G有2个奇数度结点[D] G没有或有2个奇数度结点9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是（）。

离散数学练习题(含答案)离散数学试题第一部分选择题1.下列命题变元p，q的小项是(C)。

A。

p∧┐p∧qB。

┐p∨qC。

┐p∧qD。

┐p∨p∨q2.命题“虽然今天下雪了，但是路不滑”可符号化为(D)。

A。

p→┐qB。

p∨┐qC。

p∧qD。

p∧┐q3.只有语句“1+1=10”是命题(A)。

A。

1+1=10B。

x+y=10___<0D。

x mod 3=24.下列等值式不正确的是(C)。

A。

┐(x)A(x)┐AB。

(x)(B→A(x))B→(x)A(x)C。

(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D。

(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y) 5.量词x的辖域是“Q(x,z)→(x)(y)R(x,y,z)”(C)。

A。

(x)Q(x,z)→(x)(y)R(x,y,z))B。

Q(x,z)→(y)R(x,y,z)C。

Q(x,z)→(x)(y)R(x,y,z)D。

Q(x,z)6.设A={a,b,c,d}，A上的等价关系R={。

}∪IA则对应于R的A的划分是(D)。

A。

{{a},{b,c},{d}}B。

{{a,b},{c},{d}}C。

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

{{a,b},{c,d}}7.设A={Ø}，B=P(P(A))，以下正确的式子是(A)。

A。

{Ø,{Ø}}∈BB。

{{Ø,Ø}}∈BC。

{{Ø},{{Ø}}}∈BD。

{Ø,{{Ø}}}∈B8.集合相对补运算中，不正确的等式是(A)。

A。

(X-Y)-Z=X-(Y∩Z)B。

(X-Y)-Z=(X-Z)-YC。

(X-Y)-Z=(X-Z)-(Y-Z)D。

(X-Y)-Z=X-(Y∪Z)9.在自然数集N上，不可结合的定义的运算是(D)。

A。

a*b=min(a,b)B。

a*b=a+bC。

a*b=GCD(a,b) (a,b的最大公约数)D。

网络学院离散数学模拟试题1 考试时间120 分钟考试方式：开卷专业年级姓名学号一、选择填空题(每个空格3分,共30分)1．设A，B是集合，且φA，则_____必定成立。

D-B=A．A=B B．B⊆A C．A∩B=φD．A⊆B 2．{φ,{φ}}－φ=_____;CＡ. φ B. {φ} C. {φ,{φ}} D. {{φ}}3．设集合A={{0}}，则P(A) =_____。

DA. P(P({0}))B. P({0})∪φC. P({0})∪{{0}}D. {φ,{{0}}}4．设有集合A={1,2,3,4}，则从A到{0,1}的不同的函数有____个。

EA．0 B．1 C．4 D．12 E. 16 F. 24 G. 32 5．设G=(a)为12阶循环群，则G没有____阶子群。

EA．1 B．2 C．3 D．4 E. 5 F. 66．凡_____都满足消去律。

DA. 代数系统B. 半群C. 独异点D. 群7．从无向完全图K中至少删除____条边后，所得的图将成为平面图。

B5A．0 B．1 C．2 D．38．若无向图G是有99个结点，9个连通分量，则G中的边数必_____。

C A. ≤90 B. =90 C. ≥90 D. =100 E. ≥1009．下列句子中为命题的是_____。

AA．今天不是星期六。

B．考场内禁用手机！C．今天是周末吗？D．今天真冷呀！10． 任意两个不同极大项的析取式必为______。

AA. 永真公式B. 可满足公式C. 永假公式D. 等值公式二、求出谓词公式(,)(,,)u v F u v w G u v w ∃∃→∀的前束范式。

(10分)解：(,)(,,)u v F u v w G u v w ∃∃→∀ ⇔1111(,)(,,)u u F u v w G u v w ∃∃→∀ ⇔111(,)(,,)u v F u v w G u v w ⌝∃∃∨∀ ⇔1111(,)(,,)u y F u v w G u v w ∀∀⌝∨∀⇔1111(,)(,,)u v wF u vG u v w ∀∀∀⌝∨（）三、用形式证明的方法证明下列论证的有效性：“本班有些同学是有经验的C++程序员，任何C++程序员都知道对象的概念。

专科《离散数学模拟》试题（一）姓名______________ 学号______________ 成绩______________一、填空（每小题5分，共25分）1．设}41,,3|{≤≤∈==K N k k x x A ，则用列举法表示A =_____________________。

2．设}2,{φ=A ，则A 的幂集=A 2________________________。

3．设)}1,2(),2,4(),3,1{(=ρ是A 到B 的关系，则ρ的逆关系=ρ~_______________。

4．下图G 的邻接矩阵A =__________________________5．设}},3,2{,3,2{φ=A ，则=-}}3,2{{A ____________________________。

二、选择题（将正确答案的编号填入相应题目后面的括号中，每小题5分，共20分） 1．设集合}3,2,1{=A ，A 上的关系)}1,1(),1,2(),1,3(),3,2{(=ρ，则ρ是（ ）。

A ．自反的B ．反对称的C ．可传递的2．设有函数Z Z Z f →⨯:（Z 表示非负整数集），定义为y x y x f +=),(，则f 是（ ）。

A ．满射B ．内射C ．双射3．设}4,3,2,1{=A ，则A 的分划有（ ）。

A ．}}3{},4,2{),1{(B ．}}4{},3,2{{C ．}}4{},3,2,1{{4．设简单图G 所有结点的度之和为12，则G 一定有（ ）。

A ．3条边 B ．4条边 C ．6条边4v 3v 2v 1v三、问答题（每小题6分，共42分）1．下图G 是否二部图？若是，找出它的互补结点子集。

2．设有命题公式)(Q P P F →⌝∨=，问F 是否求真公式？为什么？3．判断下图是否欧拉图，若是，找出一个欧拉回路。

v 2v 1v 53v 5v4．设1ρ和2ρ是集合A 上的偏序关系，问1ρ－2ρ是A 上的偏序关系吗？为什么？5．判断下述命题公式的等值关系是否成立P Q P Q P Q ∨⌝⇔→∧→)((6．将下一命题符号化。

《离散数学》模拟题北航10秋学期《离散数学》模拟题⼀⼀、单项选择题（本⼤题共15⼩题，每⼩题2分，共30分）1.∑中所有有限长度的串形成的集合记为∑* ，容易证得∑*上的连接运算不满⾜交换律，但满⾜（ A ） A ．结合律 B ．分配律 C ．幂等律 D ．吸收律 2.Klein 群中元素a,b,c 的阶为（ B ）。

A ．1B ．2C ．3D ．4 3.群G 的元素x 的所有幂的集合为G 的⼦群,称由x ⽣成的⼦群。

记为（ A ）. A ． B ．(x) C ．x D ．[x] 4.交换环是指乘法满⾜（ A ）。

A ．交换律B ．结合律C ．分配律D ．吸收律 5.⾄少有（ B ）元素的含单位元、⽆零因⼦环称为除环。

A ．⼀ B ．⼆ C ．三 D ．四 6.∨,∧满⾜( C )的格称为分配格A ．交换律B ．结合律C ．分配律D ．幂等律 7.若L 为有限布尔代数,则（ B ）正整数n ，L 与含有n 个元素的集合A 的幂集同构。

A ．不存在 B ．存在 C ．有可能存在 8.有向图D 的顶点v 作为边的始点的次数之和称为v 的出度，记为d +(v)， v 作为边的终点的次数之和称为v 的⼊度，记为d -(v)，v 的度数d(v)= ( A )。

A ．d +(v)+d -(v)B ．d +(v)C ．d -(v)D ．d +(v)*d -(v) 9.若通路Г=v 0e 1v 1e 2…e 1v 1 中所有顶点互不相同(所有边⾃然互不相同)时称为（ B ） A ．初级回路 B ．路径 C ．复杂通路D ．迹 10.在n 阶图中，若⼀顶点存在到⾃⾝的回路，则必存在从该顶点到⾃⾝的长度不超过( B )的回路。

A ．n-1 B ．n C ．n+1 D ．2n 11.“⼈总是要死的”谓词公式表⽰为（ C ）。

（论域为全总个体域）M(x)：x 是⼈；Mortal(x)：x 是要死的。

A ．)()(x Mortal x M →； B ．)()(x Mortal x M ∧C ．))()((x Mortal x M x →?； D ．))()((x Mortal x M x ∧?12. 公式))()((x Q x P x A →?=的解释I 为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A 的真值为（ A ）。