安阳工学院离散数学

离散数学200题一、单项选择题1．下列是两个命题变元p，q的小项是（）A．p∧┐p∧qB．┐p∨qC．┐p∧qD．┐p∨p∨q2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）A．p→┐qB．p∨┐qC．p∧qD．p∧┐q3．下列语句中是命题的只有（）A．1+1=10B．x+y=10C．sinx+siny<0D．xmod3=24．下列等值式不正确的是（）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)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={<a,b>,<b,a>,<c,d>,<d,c>}∪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．{{Ø,Ø}}∈BC．{{Ø},{{Ø}}}∈BD．{Ø,{{Ø}}}∈B9.无向树T中有3个3度,2个2度顶点,其余顶点都是树叶，T有几片树叶。A.8B.6C.4D.510.设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.5C.再过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∧M6C．m0∧m3∧m5∧m6D．M1∨M3∨M5∨M620.设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,E1>,其中,V1={a,b,c,d,e},E1={(a,b),(b,c),(c,d),(a,e)}G2=<V2,E2>,其中,V2=V1,E2={(a,b),(b,e),(e,b),(a,e),(d,e)}D3=<V3,E3>,其中,V3=V1,E3={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}D4=<V4,E4>,其中,V4=V1,E4={<a,b>,<a,b>,<b,c>,<d,e>,<c,d>}A.G1,D4B.G1,D3C.G2,D3,D4D.G2,D424.下列哪个不是平面图。25设A={a,b,c}，B={1,2,3}，以下哪一个关系是从A到B的双射函数？A、f={<a,2>,<b,2>,<c,1>}B、f={<a,3>,<b,1>,<c,2>}C、f={<a,1>,<b,2>,<c,3>,<a,3>}D、f={<a,1>,<b,2>}26.给定命题公式如右：p∨（q∧┐r），指出公式的成真赋值。A、无B、全体赋值C、000，100，101，111D、010，110，27．设S={ø，{1}，{1，2}}，则P（S）有几个元素。A、3B、6C、7D、828.下述哪一个不是命题？A、离散数学是计算机系的一门必修课。B、不存在最大偶数。(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.1080~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.1092设个体域是正整数集，则下列公式中真值为真的公式是()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={<a,b>,<a,c>},则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={<a,a>,<b,b>,<a,b>,<b,a>,<c,a>}，则R不具有()A.自反性B.对称性C.传递性D.反对称性97下列等值式不正确的是（）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)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)-YC．(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中的任意两个元素都有和，则称S关于≤构成一个格。126．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a•b，其中+和•是数的加法和乘法，则代数系统<Z,*>的幺元是，零元是。127．如下平面图有2个面R1和R2，其中deg(R1)=，deg(R2)=。128．无向图G具有一条欧拉回路，当且仅当G是，并且所有结点的度数都是。129.设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为___________________。130.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。131.设G是n阶无向带权边通图，各变的权均为a(a>0),设T是G的一棵最小生成树，则T的权W(T)=_______________________。132.设G1,G2,G3,G4都是4阶3条边的无向简单图，则它们之间至少有___________________个是同构的。133．设G是n（n2）阶二部图，又是平面图，则命题“G的对偶图是欧拉图”的真值为_______________________。134.设为整数集，，则f的值域ranf=___________。135.设则A上共有____________个不同的等价关系。136.设，恒等关系IA的传递闭包t(IA)=_________________。137.在实数集合R上定义二元运算如下：____________其中“-”为普通的减法，命题“是代数系统”的真值为___________________。138.在一阶逻辑中将命题”鸟都会飞翔”符号化___________________.139.在一阶逻辑中将命题”没有不爱看电影的人”符号化__________________140.将命题”如果今天是1号，则明天是2号”符号化___________________。141.R={<1,1>,<2,2>.}是A={1,2}上的二元关系,则R具有哪些性质__________________。141.设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为___________________。142.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。143.p∧q的成真赋值为________________________。144.设f={<1,2>,<3,4>}为整数集，则f的值域ranf=___________。145.设│A│=3则A上共有____________个不同的二元关系。146命题公式p∧(q∨┓r)的成真指派的是_______________。147q的主合取范式为____________。148A={ab}，则A上共有__________个不同的偏序关系。149设A={a,b,c}，B={1,2,3}，则A到B共可产生_____________个不同的双射函数。150设A是n(n≥1)元集，则A上共有22n个二元运算，其中有______________个是A到A的函数。三、计算与应用题151求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函数。152如果论域是集合{a,b,c}，试消去给定公式中的量词：。153设A={a,b,c}，P（A）是A的幂集，是集合对称差运算。已知<P(A),>是群。在群<P(A),>中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}。154用等值演算法求公式┐(p→q)(p→┐q)的主合取范式155画出5个具有5个结点5条边的非同构的无向连通简单图。156在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。设<A,R>为一个偏序集，其中，A={1，2，3，4，6，9，24，54},R是A上的整除关系。157.画出<A,R>的哈斯图；158.求R关于A的极大元；159.求B={4,6,9}的最小上界和最大下界。160设7个字母在通信中出现的频率如下:a:30%,b:20%,c:15%,d:10%,e:15%,f:5%,g:5%.编一个最佳2元前缀码.在这个前缀码中,a,b,c,d,e,f,g的码长分别是多少?传输10000个按上述比例出现的字母需要多少个二进制数字?161.设A={a,b,c,d,},R=IA∪{<a,b>,<b,a>,<c,d>,<d,c>,}是A上的等价关系，求商集A/R及各元素的等价类。162求公式p→((q∧r)∧(p∨(Øq∧Ør)))的主析取范式163判断推理是否正确设y＝2|x|,x为实数，推理如下：若y在x＝0可导，则y在x＝0连续。y在x＝0连续。所以，y在x＝0可导。在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,24}，≤是Z中的整除关系。163.求集合D={2,3,4,6}的极大元，极小元；164.求集合D={2,3,4,6}的最大元，最小元；165.求集合D={2,3,4,6}的最小上界和最大下界。166设集合A={1,3,5,7,9,11,13,15},A上的一个划分S={{1,15},{3,9,11,13},{5,7}}。试求由S导出的A上的等价关系R。167求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函数。168．用等值演算法求公式┐(p→q)∧(p→┐q)的主合取范式169．在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。设二元关系R={<{a},b>,<{φ},φ>,<{φ},{φ}>}求：171计算domR172计算ranR173计算R·R174计算R-1·R-1..设，，试求：176作出〈A，R〉的哈斯图177求A的最大元、最小元、上界、下