安阳工学院离散数学.docx
《安阳工学院离散数学.docx》由会员分享，可在线阅读，更多相关《安阳工学院离散数学.docx（20页珍藏版）》请在冰点文库上搜索。
安阳工学院离散数学
安阳工学院离散数学
离散数学200题
一、单项选择题
1．下列是两个命题变元p，q的小项是（）
A．p∧┐p∧qB．┐p∨q
C．┐p∧qD．┐p∨p∨q
2．令p：
今天下雪了，q：
路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）
A．p→┐qB．p∨┐q
C．p∧qD．p∧┐q
3．下列语句中是命题的只有（）
A．1+1=10B．x+y=10
C．sinx+siny<0D．xmod3=2
4．下列等值式不正确的是（）
A．┐（x）A（x）┐A
B．（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）P（x,y）∧（x）（Q（x,z）→（x）（y）R（x,y,z）中量词x的辖域是（）
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．设R为实数集，函数f：
R→R，f（x）=2x，则f是（）
A．满射函数B．入射函数
C．双射函数D．非入射非满射
7．设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}}
8．设A={Ø}，B=P（P（A）），以下正确的式子是（）
A．{Ø,{Ø}}∈BB．{{Ø,Ø}}∈B
C．{{Ø},{{Ø}}}∈BD．{Ø,{{Ø}}}∈B
9.无向树T中有3个3度,2个2度顶点,其余顶点都是树叶，T有几片树叶。
A.8B.6C.4D.5
10.设A={a,b,c}，则下列哪个是集合A的划分。
A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a,b},{c}}D.{a,{b,c}}
11.设集合X={0,1,2,3}R是X上的二元关系，R={<0,0>,<0,2>,<1,0>,<1,1>,<2,3>,<3,2>,<3,3,>}，则哪个是R的关系矩阵MR。
A． B.C.D.
12.从下列描述中，指出不正确的表述。
A.P（{a,{b,c}}）={φ,{a},{{b,c}},{a,{b,c}}}B.P（{φ}）={φ,{φ}}
C.（φ）={φ}D.P（{a,{b,c}}）={{φ},{a},{{b,c}},{a,{b,c}}}
13.从下列图中找出欧拉图。
14.令F（x）:
x是金属，G（y）:
y是液体，H（x,y）:
x可以溶解在y中，则命题“任何金属可以溶解在某种液体中”可符号化为什么逻辑表达式。
A.（x）（F（x）∧（y）（G（y）∧H（x,y）））B.（x）（（x）F（x）→（G（y）→H（x,y）））
C.（x）（F（x）→（y）（G（y）∧H（x,y）））D.（x）（F（x）→（y）（G（y）→H（x,y））
15.在个体域D={a,b}中，指出与公式（x）A（x）等价又不含量词的公式。
A.A（a）∧A（b）B.A（a）→A（b）C.A（a）∨A（b）D.A（b）→A（a）
16.指出下列是命题的句子。
A.水开了吗?
B.x>1.5
C.再过9000年，地球上就没水了。
D.我没讲真话。
17.给定算式:
（（（a＋（b＊c））＊d－e）÷（f＋g））－（（h＊i）＊j）找出与此算式对应的波兰符号表示式。
A．－＊＊a＋bc＋def－g＊hij＊＊B.abc＊＋d＊e－fg＋÷hi＊j＊－
C．－÷－＊＋a＊bcde＋fg＊＊hijD.ab＋c＊de＋＊fgh＊－＋ij＊－
18.设N是自然数集，函数f:
N→N×N.f（n）＝﹤n,n＋1﹥,f（{5}）是什么。
A．满射函数B．单射函数C．{<5,6>}D．双射函数
19.已知（p→q）←→r的主析取范式是m1∨m3∨m4∨m7，指出与其对应的主合取范式。
A．m1∨m2∨m5∨m7B．M0∧M2∧M5∧M6
C．m0∧m3∧m5∧m6D．M1∨M3∨M5∨M6
20.设T（x）：
x具有性质T，S（y）：
y具有性质S。
命题“若存在x具有性质T，则所有的y都没有性质S“的符号化形式是什么。
A.x（T（x）→S（x））B.x（T（x）∧S（x））
C.xT（x）→yS（y）D.xT（x）→yØS（y）
21.判断下列各非负整数列哪个不是可图化的。
A.（5,5,4,4,2,1）B.（4,4,2,1,3）C.（5,4,3,2,2）D.（3,3,1,1）
22.设Z,N分别为整数和自然数集，函数g:
Z→N,g（x）＝|x|,g是什么函数。
A．满射函数B．满射非单射C．单射函数D．单射非满射
23.给定下列各图，判断哪些为简单图。
G1=,其中,V1={a,b,c,d,e},E1={（a,b）,（b,c）,（c,d）,（a,e）}
G2=,其中,V2=V1,E2={（a,b）,（b,e）,（e,b）,（a,e）,（d,e）}
D3=,其中,V3=V1,E3={,,,,,}
D4=,其中,V4=V1,E4={,,,,}
A.G1,D4B.G1,D3C.G2,D3,D4D.G2,D4
24.下列哪个不是平面图。
25设A={a,b,c}，B={1,2,3}，以下哪一个关系是从A到B的双射函数？
A、f={,,}B、f={,,}
C、f={,,,}D、f={,}
26.给定命题公式如右：
p∨（q∧┐r），指出公式的成真赋值。
A、无B、全体赋值C、000，100，101，111D、010，110，
27．设S={ø，{1}，{1，2}}，则P（S）有几个元素。
A、3B、6C、7D、8
28.下述哪一个不是命题？
A、离散数学是计算机系的一门必修课。
B、不存在最大偶数。
C、若我有空，我就看书。
D、请勿随地叶痰！
29.无向图G中有16条边，且每个结点的度数均为2，则结点数是多少。
A.8B.16C.4D.32
30.设集合X={0,1,2,3}R是X上的二元关系，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}，则哪个是R的关系矩阵MR。
A． B.C.D.
31.在个体域D={a,b}中，指出与公式（x）A（x）等价又不含量词的公式。
A.A（a）∧A（b）B.A（a）→A（b）C.A（a）∨A（b）D.A（b）→A（a）
32.指出下列是命题的句子。
A.今天出太阳了吗?
B.Y>3.14
C.再过8000年，地球上就没生命了。
D.我在说谎话。
33.给定算式:
（（（a＋（b＊c））＊d－e）÷（f＋g））＋（（h＊i）＊j）找出与此算式对应的波兰符号表示式。
A.－＊＊a＋bc＋def－g＊hij＊＊B.abc＊＋d＊e－fg＋÷hi＊j＊－
C.＋÷－＊＋a＊bcde＋fg＊＊hijD.ab＋c＊de＋＊fgh＊－＋ij＊－
34．设N是自然数集，函数f:
N→N×N.f（n）＝﹤n,n＋1﹥,f（{6}）是什么。
A．满射函数B．单射函数C．{<6,7>}D．双射函数
35.已知（p→q）←→r的主合取范式是M0∧M2∧M5∧M6，指出与其对应的主析取范式。
A．m1∧m2∧m5∧m7B．m1∨m3∨m4∨m7
C．M0∧M3∧M5∧M6D．M1∨M3∨M5∨M6
36.判断下列各非负整数列哪个不是可图化的。
A.（5,5,4,4,2,3）B.（4,4,2,1,3）C.（5,4,3,2,2）D.（3,3,1,1）
37.设Z,N分别为整数和自然数集，函数g:
Z→N,g（x）＝|x|,g是什么函数。
A．满射函数B．满射非单射C．单射函数D．单射非满射
38.设A={a,b,c}，B={1,2,3}，以下哪一个关系是从A到B的双射函数？
A、f={,,}B、f={,,}
C、f={,,,}D、f={,}
39.设P：
2是素数，Q：
3是素数，R：
是有理数，下列复合命题中假命题为哪
一个.
A（P∨Q）→RBR→（P∨Q）
C（P∧Q）→PD（R∨P）Q
40.设有集合A={a,b,c},Ø为空集，则下列哪一个表示是正确的.
A{a}∈AB{a}⊂ACa⊂ADØ∈A
41.称由前提，,…..Ak推出结论B的推理正确，则∧∧…..∧Ak→B应为下列表述中的哪一个.
A重言式或可满足式B可满足式C矛盾式D重言式
42.若P：
他聪明；Q：
他用功；则“他虽聪明，但不用功；”，可符号化为：
（）
A、P∨QB、P∧┐QC、P→┐QD、P∨┐Q
43．以下命题公式中，为永假式的是：
（）
A、P→（P∨Q∨R）
B、（P→┐P）→┐P
C、┐（Q→P）∧P
D、┐（P∨┐P）→（P∧┐P）
44.求一棵带权为1.5,2.5,3,4,5,6的最优3元树,其权为（）
A、30B、35C、37D、45
45给定命题公式如右：
p∨（q∧┐r），则公式的成真赋值为（①），公式的类型为（②）
①A、无B、全体赋值C、010，100，101，111D、010，100，101，110，111
②A、重言式B、矛盾式C、可满足式D、以上都不对
46设S={1，2，…,10}，≤是S上的整除关系，其中最大元是（②），最小元是（③）。
②、③:
A、1B、10C、6D、不存在
47.设有无向图1，则（）是一条哈密顿通路。
A、V7V1V6V5V4V3V2B、V1V2V3V4V5V6V7
C、V1V2V4V5V6D、V2V3V4
48.在个体域D={a,b}中，与公式（x）A（x）等价又不含量词的公式是（）
A.A（a）∧A（b）B.A（a）→A（b）C.A（a）∨A（b）D.A（b）→A（a）
49.下列是命题公式p∧（q∨┓r）的成真指派的是（）
A.110，111，100B.110，101，011C.所有指派D.无
50.给定命题公式如右：
p∨（q∧┐r），则公式的成真赋值为（①），公式的类型为（②）
①A、无B、全体赋值C、010，100，101，111D、010，100，101，110，111
②A、重言式B、矛盾式C、可满足式D、以上都不对
51设S={ø，{1}，{1，2}}，则P（S）有（）个元素。
A、3B、6C、7D、8
52设S={1，2，…,10}，≤是S上的整除关系，则的哈斯图是（①），其中
最大元是（②），最小元是（③）。
①A、一棵树B、一条链C、有向图D、以上都不对
②、③A、1B、10C、6D、不存在
53给定序列：
1）（2，2，2，2，2）2）（1，1，2，2，3）
3）（1，1，2，2，2）4）（0，1，3，3，3）
5）（1，3，4，4，5）
可以构成无向简单图的度数序列为（）。
A、1），3），4）B、1），2）C、1），3）D、3），4），5）
54在一棵无向树中有7片树叶，3个3度顶点，其余都是4度顶点，则该树有（）个
4度顶点。
A、1B、3C、5D、6
55设个体域是正整数集，则下列公式中真值为真的公式是（）
A.（x）（y）（x·y=0）
B.（x）（y）（x·y=1）
C.（x）（y）（x·y=2）
D.（x）（y）（z）（x-y=z）
56一棵无向树有2个4度顶点，3个3度顶点，其余的都是树叶，则该树有（）片树叶。
A、7B、8C、9D、10
57.下列语句中，（）是命题。
A.请把门关上B.地球外的星球上也有人
C.x+5>6D.下午有会吗？
58.命题公式﹁B→﹁A等价于（）
A.﹁A∨﹁BB.﹁（A∨B）
C.﹁A∧﹁BD.A→B
59.下列说法正确的是（）.
A．若B．若
C．若D．若
60．下列说法错误的是（）.
A．B．
C．D．
61．设，P（A）为A的幂集，则P（A）的元素个数为（）.
A．3 B．6C．7D．8
62.集合A的一个划分，确定A的元素间的关系为（）.
A．全序关系 B．等价关系 C．偏序关系 D．拟序关系
63设命题公式﹁（P∧（Q→﹁P））记作G，使G的真值指派为F的P，Q的真值是下列4个中的哪一个（）
（A）（T,F）（B）（F,T）（C）（T,F）（D）（F,T）
64.命题公式（P∧Q）→P是下列4个中的哪一个（）
（A）永真式（B）永假式（C）可满足式（D）合取范式
65．谓词公式xA（x）∧﹁xA（x）的类型是下列4个中的哪一个（）
（A）永真式（B）矛盾式
（C）非永真式的可满足式（D）不属于（A），（B），（C）任何类型
66．对任意集合S，S∪Ø=S，满足下面哪一个定律（）
（A）等幂律（B）零一律（C）同一律（D）互补律
67设A={1，2，3}，B={1，2，3，4，5}，C={2，3}，则（A∪B）+C=（）
（A）{1，2}（B）{2，3}（C）C={1，4，5}（D）{1，2，3}
68．当且仅当为下面4个中的哪一个时，无向图G是欧拉图（）
（A）G的所有结点的次数为偶数
（B）G的所有结点的次数为奇数
（C）G连通且所有结点的次数为偶数
（D）G连通且所有结点的次数为奇数
69.设集合A={a1,a2,a3,a4},B={b1,b2,b3},σ是从A到B的函数，σ={（a1,b2）,（a2,b2）,（a3,b1）,（a4,b3）}，则σ是下面4个中的哪一种（）
（A）双射；（B）满射但不是单射；
（C）单射但不是满射（D）非单射也非满射
70设G=为无向简单图，|V|=n，△（G）为图G中结点的最大次数，请指出下面4个中哪个不等式是正确的。
（A）△（G）n（D）△（G）≥n
71．设S1=Ø，S2={Ø}，S3=ρ（{Ø}），S4=ρ（Ø），以下命题为假的是哪一个（）
（A）S2∈S4（B）S1⊆S3（C）S4⊆S2（D）S4∈S3
72．设V={a,b,c,d}，则与V能构成强连通图的边集合是下面4个中哪一个（）
（A）E={（a,d）,（b,a）,（b,d）,（c,b）,（d,c）}
（B）E={（a,d）,（b,a）,（b,c）,（b,b）,（d,c）}
（C）E={（a,c）,（b,a）,（b,c）,（d,a）,（d,c）}
（D）E={（a,d）,（a,c）,（a,d）,（b,d）,（c,d）}
73设集合A={a1,a2,a3,a4},B={b1,b2,b3},σ是从A到B的函数，σ={（a1,b2）,（a2,b2）,（a3,b1）,（a4,b3）}，则σ是下面4个中的哪一种（）
（A）双射；（B）满射但不是单射；（C）单射但不是满射（D）非单射也非满射
74．当且仅当为下面4个中的哪一个时，无向图G是欧拉图（）
（A）G的所有结点的次数为偶数
（B）G的所有结点的次数为奇数
（C）G连通且所有结点的次数为偶数
（D）G连通且所有结点的次数为奇数
75~79.75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人
买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费
140元,恰好买2本书的有（）多少个学生.至少买2本书的学生花费（）元.买
1本书的有（）个学生.至少买1本书的有（）个学生.没买书的有（）个学生.
A.55B.40C.35D.15E.30F.130G.65H.140J.60K.10
80~86.为每个逻辑断言选择正确的解释。
T（x）：
x今天来上课，S（x）：
x学计算机专业的学生，P（x）：
x编程序，G（x）：
x玩游戏。
个体域是殷都大学。
xT（x）表示（），ØxT（x）表示（），xØT（x）表示（），x（S（x）→P（x））表示（），x（S（x）∧G（x））表示（），x（S（x）∧P（x））表示（），x（S（x）→G（x））表示（）。
A学计算机专业的学生会编程序，B殷都大学的学生都是计算机专业且会编程序。
C有些计算机专业的学生玩游戏，D所有同学今天都来上课了，E今天有同学没来上课。
F计算机专业的学生玩游戏，G今天没有同学来上课。
87~91对60个人的调查表明有25人阅读News,26人阅读Times,26人阅读Happy,9人
阅读News和Happy,11人阅读News和Times,8人阅读Times和Happy,还有8
人什么杂志也不阅读.问阅读全部3种杂志的有（）人,只阅读News的有（）人,
只阅读Times的有（）人,只阅读Happy的有（）人,只阅读一本杂志的有（）人.
A.5B.8C.3D.15E.30F.13G.65H.12J.60K.10
92设个体域是正整数集，则下列公式中真值为真的公式是（）
A.（x）（y）（x·y=0）B.（x）（y）（x·y=1）
C.（x）（y）（x·y=2）D.（x）（y）（z）（x÷y=2）
93设A={a,b,c},R是A的关系且R={,},则R是的（）
A.传递B.自反
C.对称D.反自反
94下述不是命题的是（）
A.做人真难啊!
B.后天是阴天。
C.2是偶数。
D.地球是方的。
95.命题公式P→（P∨Q∨R）是（）
A.恒真的B.恒假的
C.可满足的D.合取范式
96.设有A={a,b,c}上的关系R={,,,,}，则R不具有（）
A.自反性B.对称性
C.传递性D.反对称性
97下列等值式不正确的是（）
A．┐（"x）AÛ（$x）┐A
B．（"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）
98谓词公式（"x）P（x,y）∧（$x）（Q（x,z）→（$x）（"y）R（x,y,z））中量词（$x）的辖域是（）
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）
99设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（）
A．（X-Y）-Z=X-（Y∩Z）
B．（X-Y）-Z=（X-Z）-Y
C．（X-Y）-Z=（X-Z）-（Y-Z）
D．（X-Y）-Z=X-（Y∪Z）
100设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）
A．2个面B．3个面
C．4个面D．5个面
二、填空题
101.设p:
天下雨，q:
天刮风，r:
我去书店，则命题“如果天不下雨并且不刮风，我就去书店”的符号化形式为_______________。
102.设F（x）:
x是人，H（x,y）:
x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为______________________________。
103.设A={a，b}，则A上共有__________个不同的二元关系。
104.设A={1,2},B={2,3},C={a,b,c}，则（A∪B）×C=__________________________________。
105.无环有向图的关联矩阵的所有元素之和为
106.设G是完全二叉树，G有15个点，其中8个叶子，则G的总度数为__________。
107.设，，，则domR=。
108.设简单图G所有结点的度之和为12，则G一定有条边。
109.图4中结点V6的度数为____。
110.（p∧q）→r的主合取范式为________________________
111.┐（┐p→（q∨r））的成真赋值为______________________________。
112.（p∧q）→r的主合取范式为________________________。
113.设A={2,3,6,12},≤是A上的整除关系，则偏序集〈A，≤〉的最大元是_______。
114.设A={φ,{φ}},B={0,1},从A到B的双射函数有________个。
115.设G是完全二叉树，G有15个点，其中8个叶点，则G的分枝点数为________________。
116.一棵无向树有2个4度顶点，3个3度顶点，其余的都是树叶，则该树有片树叶。
117．设A={a,b,c}，B={1,2,3}，则A到B共可产生_____________个不同的双射函数。
118.某公司有销售人员82人，维修人员191人，既做销售又搞维修的人员20人，既非销售人员又非维修人员有912人，则该公司总人数为______。
119.设个体域是{a,b,c}，则（"x）S（x）等价于命题公式__________
120．一公式为之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定。
121．前束范式具有形式（Q1V1）（Q2V2）…（QnVn）A，其中Qi（1≤i≤n）为，A为的谓词公式。
122．设论域是{a,b,c}，则（x）S（x）等价于命题公式；（）S（x）等价于命题公式
123．设R为A上的关系，则R的自反闭包r（R）=，对称闭包s（R）=。
124．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是，其关系矩阵是。
125．设是一个偏序集，如果S中的任意两个元素都有和，则称S关于≤构成一个格。
1
升级会员 