------------------------------------------作者xxxx------------------------------------------日期xxxx离散
数学试题
八年级上册数学北师大八年级数学期末考试题必修一高中数学函数北京市东城区是哪个区高等学校统一招生考试
(十五套)【精品文档】【精品文档】【精品文档】【精品文档】【精品文档】【精品文档】087ynu离散数学
试题
中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载
与答案试卷一一、填空20%（每小题2分）1．设（N：自然数集，E +正偶数）则。2．A，B，C
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示三个集合，文图中阴影部分的集合表达式为ABC。3．设P，Q的真值为0，R，S的真值为1，则的真值=。4．
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
的主合取范式为。5．若解释I的论域D仅包含一个元素，则在I下真值为。6．设A={1，2，3，4}，A上关系图为则R2=。7．设A={a，b，c，d}，其上偏序关系R的哈斯图为则R=。8．图的补图为。9．设A={a，b，c，d}，A上二元运算如下：*abcdabcdabcdbcdacdabdabc那么代数系统
的幺元是，有逆元的元素为，它们的逆元分别为。10．下图所示的偏序集中，是格的为。二、选择20%（每小题2分）1、下列是真命题的有（ ）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．；D．。4、设R，S是集合A上的关系，则下列说法正确的是（）A．若R，S是自反的，则是自反的；B．若R，S是反自反的，则是反自反的；C．若R，S是对称的，则是对称的；D．若R，S是传递的，则是传递的。5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下则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}}06、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（）7、下列函数是双射的为（）A．f:IE,f(x)=2x；B．f:NNN,f(n)=；C．f:RI,f(x)=[x]；D．f:IN,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%R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当和在R中有<.b,c>在R中。（8分）f和g都是群到的同态映射，证明是的一个子群。其中C=(8分)G=(|V|=v，|E|=e)是每一个面至少由k（k3）条边围成的连通平面图，则，由此证明彼得森图（Peterson）图是非平面图。（11分）四、逻辑推演16%用CP规则证明下题（每小题8分）1、2、五、计算18%1、设集合A={a，b，c，d}上的关系R={,,,}用矩阵运算求出R的传递闭包t(R)。（9分）2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
，使得各城市之间能够通信而且总造价最小。 （９分）试卷一答案：一、填空20%（每小题2分）1、{0，1，2，3，4，6}；2、；3、1；4、；5、1；6、{<1,1>,<1,.3>,<2,2>,<2,4>}；7、{,,,,}IA；8、9、a；a,b,c,d；a,d,c,d；10、c;二、选择20%（每小题2分）题目12345678910答案CDB、CCADCADBA三、证明26%证：“”若由R对称性知，由R传递性得“”若，有任意，因若所以R是对称的。若，则即R是传递的。证，有，又★★★是的子群。证：①设G有r个面，则，即。而故即得。（8分）②彼得森图为，这样不成立，所以彼得森图非平面图。（3分）逻辑推演16%证明：①P（附加前提）②T①I③P④T②③I⑤T④I⑥T⑤I⑦P⑧T⑥⑦I⑨CP2、证明①P（附加前提）②US①③P④US③⑤T②④I⑥UG⑤⑦CP计算18%解：，，t(R)={,,,,,,,,}解：用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。试卷二试题与答案一、填空20%（每小题2分）P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻y译为；“虽然你努力了，但还是失败了”的翻译为。2、论域D={1，2}，指定谓词PP(1,1)P(1,2)P(2,1)P(2,2)TTFF则公式真值为。设S={a1，a2，…，a8}，Bi是S的子集，则由B31所表达的子集是。设A={2，3，4，5，6}上的二元关系，则R=（列举法）。R的关系矩阵MR=。5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R=；A上既是对称的又是反对称的关系R=。*abcabcabcbbcccb6、设代数系统，其中A={a，b，c},则幺元是；是否有幂等性；是否有对称性。7、4阶群必是群或群。8、下面偏序格是分配格的是。9、n个结点的无向完全图Kn的边数为，欧拉图的充要条件是。10、公式的根树表示为。二、选择20%（每小题2分）1、在下述公式中是重言式为（）A．；B．；C．；D．。2、命题公式中极小项的个数为（），成真赋值的个数为（）。A．0；B．1；C．2；D．3。3、设，则有（）个元素。A．3；B．6；C．7；D．8。设，定义上的等价关系则由R产生的上一个划分共有（）个分块。A．4；B．5；C．6；D．9。5、设，S上关系R的关系图为则R具有（）性质。A．自反性、对称性、传递性；B．反自反性、反对称性；C．反自反性、反对称性、传递性；D．自反性。6、设为普通加法和乘法，则（）是域。A．B．C．D．=N。7、下面偏序集（）能构成格。8、在如下的有向图中，从V1到V4长度为3的道路有（）条。A．1；B．2；C．3；D．4。9、在如下各图中（）欧拉图。10、设R是实数集合，“”为普通乘法，则代数系统是（）。A．群；B．独异点；C．半群。三、证明46%设R是A上一个二元关系，试证明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）若是从A到B的函数，定义一个函数对任意有，证明：若f是A到B的满射，则g是从B到的单射。（10分）若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）设G是具有n个结点的无向简单图，其边数，则G是Hamilton图（8分）四、计算14%设是一个群，这里+6是模6加法，Z6={[0]，[1]，[2]，[3]，[4]，[5]}，试求出的所有子群及其相应左陪集。（7分）权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）试卷二答案：填空20%（每小题2分）1、；2、T3、4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>}6、a；否；有7、Klein四元群；循环群8、B9、；图中无奇度结点且连通10、选择20%（每小题2分）题目12345678910答案B、DD；DDBDABBBB、C证明46%1、（9分）S自反的，由R自反，，S对称的S传递的由（1）、（2）、（3）得；S是等价关系。2、11分证明：设P(x)：x是个舞蹈者；Q(x)：x很有风度；S(x)：x是个学生；a：王华上述句子符号化为：前提：、结论：……3分①P②P③US②④T①I⑤T③④I⑥T①I⑦T⑤⑥I⑧EG⑦……11分３、１0分证明：。4、8分证明：设G中两奇数度结点分别为u和v，若u，v不连通，则G至少有两个连通分支G1、G2，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。5、8分证明：证G中任何两结点之和不小于n。反证法：若存在两结点u，v不相邻且,令，则G-V1是具有n-2个结点的简单图，它的边数,可得，这与G1=G-V1为n-2个结点为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于n。所以G为Hamilton图.计算14%d7分解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>{[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]}{[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]}{[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]}Z6的左陪集：Z6。7分试卷三试题与答案填空20%（每空2分）设f，g是自然数集N上的函数，则。设A={a，b，c}，A上二元关系R={,,,},则s（R）=。A={1，2，3，4，5，6}，A上二元关系，则用列举法T=；T的关系图为；T具有性质。集合的幂集=。P，Q真值为0；R，S真值为1。则的真值为。的主合取范式为。设P（x）：x是素数，E(x)：x是偶数，O(x)：x是奇数N(x,y)：x可以整数y。则谓词的自然语言是。谓词的前束范式为。选择20%（每小题2分）下述命题公式中，是重言式的为（）。A、；B、；C、；D、。的主析取范式中含极小项的个数为（）。A、2；B、3；C、5；D、0；E、8。给定推理①P②US①③P④ES③⑤T②④I⑥UG⑤推理过程中错在（）。A、①->②;B、②->③;C、③->④;D、④->⑤;E、⑤->⑥设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。X=S2或S5；B、X=S4或S5；C、X=S1，S2或S4；D、X与S1，…，S5中任何集合都不等。设R和S是P上的关系，P是所有人的集合，，则表示关系（）。A、；B、；C、；D、。下面函数（）是单射而非满射。A、；B、；C、；D、。其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。设S={1，2，3}，R为S上的关系，其关系图为则R具有（）的性质。自反、对称、传递；B、什么性质也没有；C、反自反、反对称、传递；D、自反、对称、反对称、传递。设，则有（）。A、{{1,2}}；B、{1,2}；C、{1}；D、{2}。设A={1,2,3}，则A上有（）个二元关系。A、23；B、32；C、；D、。10、全体小项合取式为（）。A、可满足式；B、矛盾式；C、永真式；D、A，B，C都有可能。用CP规则证明16%（每小题8分）1、2、四、（14%）集合X={<1,2>,<3,4>,<5,6>,…}，R={<,>|x1+y2=x2+y1}。证明R是X上的等价关系。（10分）求出X关于R的商集。（4分）五、（10%）设集合A={a,b,c,d}上关系R={,,,}要求1、写出R的关系矩阵和关系图。（4分）2、用矩阵运算求出R的传递闭包。（6分）六、（20%）1、（10分）设f和g是函数，证明也是函数。2、（10分）设函数，证明有一左逆函数当且仅当f是入射函数。答案：填空20%（每空2分）1、2(x+1)；2、；3、；4、反对称性、反自反性；4、；5、1；6、；7、任意x，如果x是素数则存在一个y，y是奇数且y整除x；8、。选择20%（每小题2分）题目12345678910答案CCCCABDADC证明16%(每小题8分)1、①P（附加前提）②T①I③P④T②③I⑤T④I⑥T⑤I⑦P⑧T⑥⑦I⑨CP2、①P（附加前提）②T①E③ES②④P⑤US④⑥T③⑤I⑦EG⑥⑧CP14%证明：自反性：对称性：传递性：即由（1）（2）（3）知：R是X上的先等价关系。2、X/R=10%1、；关系图2、t(R)={,,,,,,,,}。六、20%1、（1）（2）。2、证明：。。试卷四试题与答案填空10%（每小题2分）若P，Q，为二命题，真值为0当且仅当。命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，则命题的逻辑谓词公式为。谓词合式公式的前束范式为。将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则被称为存在量词消去规则，记为ES。选择25%（每小题分）下列语句是命题的有（）。明年中秋节的晚上是晴天；B、；C、当且仅当x和y都大于0；D、我正在说谎。下列各命题中真值为真的命题有（）。2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；C、2+2≠4当且仅当3是奇数；D、2+2≠4当且仅当3不是奇数；下列符号串是合式公式的有（）A、；B、；C、；D、。下列等价式成立的有（）。A、；B、；C、；D、。若和B为wff，且则（）。A、称为B的前件；B、称B为的有效结论C、当且仅当；D、当且仅当。A，B为二合式公式，且，则（）。A、为重言式；B、；C、；D、；E、为重言式。“人总是要死的”谓词公式表示为（）。（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。A、；B、C、；D、公式的解释I为：个体域D={2}，P(x)：x>3,Q(x)：x=4则A的真值为（）。A、1；B、0；C、可满足式；D、无法判定。下列等价关系正确的是（）。A、；B、；C、；D、。下列推理步骤错在（）。①P②US①③P④ES③⑤T②④I⑥EG⑤A、②；B、④；C、⑤；D、⑥逻辑判断30%用等值演算法和真值表法判断公式的类型。（10分）下列问题，若成立请证明，若不成立请举出反例：（10分）已知，问成立吗？已知，问成立吗？如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。问：若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10分）四、计算10%设命题A1，A2的真值为1，A3，A4真值为0，求命题的真值。（5分）利用主析取范式，求公式的类型。（5分）五、谓词逻辑推理15%符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。六、证明：（10%）设论域D={a,b,c}，求证：。答案：填空10%（每小题2分）1、P真值为1，Q的真值为0；2、；3、；4、约束变元；5、，y为D的某些元素。选择25%（每小题分）题目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)逻辑判断30%1、（1）等值演算法（2）真值表法PQA1111111100100101100010011111所以A为重言式。2、（1）不成立。若取但A与B不一定等价，可为任意不等价的公式。（2）成立。证明：即：所以故。3、解：设P：厂方拒绝增加工资；Q：罢工停止；R罢工超壶过一年；R：撤换厂长前提：结论：①P②P③T①②I④P⑤T④I⑥T⑤E⑦T③⑥I罢工不会停止是有效结论。四、计算10%解：它无成真赋值，所以为矛盾式。五、谓词逻辑推理15%解：证明：⑴P⑵ES⑴⑶T⑵I⑷T⑵I⑸P⑹US⑸⑺T⑶⑹I⑻T⑺E⑼US⑷⑽US⑻⑾T⑼⑽I⑿UG⑾证明10%试卷五试题与答案一、填空15%（每空3分）1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有个5度结点。2、n阶完全图，Kn的点数X(Kn)=。3、有向图中从v1到v2长度为2的通路有条。4、设[R，+，·]是代数系统，如果①[R，+]是交换群②[R，·]是半群③则称[R，+，·]为环。5、设是代数系统，则满足幂等律，即对有。二、选择15%（每小题3分）下面四组数能构成无向简单图的度数列的有（）。A、（2，2，2，2，2）；B、（1，1，2，2，3）；C、（1，1，2，2，2）；D、（0，1，3，3，3）。下图中是哈密顿图的为（）。如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（）A、真；B、假。下列偏序集（）能构成格。设，*为普通乘法，则[S，*]是（）。A、代数系统；B、半群；C、群；D、都不是。三、证明48%1、（10%）在至少有2个人的人群中，至少有2个人，他们有相同的朋友数。2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。3、（8%）证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。4、（10%）证明循环群的同态像必是循环群。5、（12%）设是布尔代数，定义运算*为，求证[B，*]是阿贝尔群。四、计算22%1、在二叉树中求带权为2，3，5，7，8的最优二叉树T。（5分）求T对应的二元前缀码。（5分）下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。答案：一、填空（15%）每空3分1、6；2、n；3、2；4、+对·分配且·对+分配均成立；5、。二、选择（15%）每小题3分题目12345答案A,BB,DBCD三、证明（48%）1、（10分）证明：用n个顶点v1，…，vn表示n个人，构成顶点集V={v1，…，vn}，设，无向图G=（V，E）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2）若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中n顶点其度数取值只能是1，2，…，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。2、（8分）证：设G中两个奇数度结点分别为u，v。若u，v不连通则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。3（8分）证：n=6,m=12欧拉公式n-m+f=2知f=2-n+m=2-6-12=8由图论基本定理知：，而，所以必有，即每个面用3条边围成。4（10分）证：设循环群[A，·]的生成元为a，同态映射为f，同态像为[f（A），*]，于是都有对n=1有n=2,有若n=k-1时有对n=k时，这表明，f(A)中每一个元素均可表示为，所以[f(A),*]为f(a)生成的循环群。5、证：交换律：有结合律：有而：幺：有逆：综上所述：[B，*]是阿贝尔群。四、计算（22%）1、（10分）（1）（5分）由Huffman方法,得最佳二叉树为：（2）（5分）最佳前缀码为：000，001，01，10，112、（12分）图中奇数点为E、F，d(E)=3,d(F)=3,d(E,F)=28p=EGF复制道路EG、GF，得图G‘，则G‘是欧拉图。由D开始找一条欧拉回路：DEGFGEBACBDCFD。道路长度为：35+8+20+20+8+40+30+50+19+6+12+10+23=281。试卷六试题与答案填空15%（每小题3分）n阶完全图结点v的度数d(v)=。设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则Nk=。算式的二叉树表示为。如图给出格L，则e的补元是。一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是。二、选择15%（每小题3分）1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是（）。A、群；B、环；C、域；D、格。2、设[{a,b,c}，*]为代数系统，*运算如下：*abcaabcbbaccccc则零元为（）。A、a；B、b；C、c；D、没有。3、如右图相对于完全图K5的补图为（）。4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（）4度结点。A、1；B、2；C、3；D、4。5、设[A，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（）时，[A，+，·]是整环。A、；B、；C、；D、。三、证明50%1、设G是（n,m）简单二部图，则。（10分）2、设G为具有n个结点的简单图，且，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：+01·01001000110101证明它是一个环，并且是一个域。（14分）是一代数格，“≤”为自然偏序，则[L，≤]是偏序格。（16分）四、10%设是布尔代数上的一个布尔表达式，试写出的析取范式和合取范式（10分）五、10%如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。答案：一、填空15%（每小题3分）1、n-1；2、n(k+1)-2m；3、如右图；4、0；5、臂力小者二、选择15%（每小题3分）题目12345答案DCAAD三、证明50%证：设G=（V，E）对完全二部图有当时，完全二部图的边数m有最大值故对任意简单二部图有。证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然与假设矛盾。所以G连通。（1）[{0，1}，+，·]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。群：（0+0）+0=0+（0+0）=0；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0……结合律成立。幺：幺元为0。逆：0，1逆元均为其本身。②[{0，1}，·]是半群乘：由“·”运算表知封闭群：（0·0）·0=0·（0·0）=0；（0·0）·1=0·（0·1）=0；（0·1）·0=0·（1·0）=0；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0。③·对+的分配律Ⅰ0·（x+y）=0=0+0=(0·x)+(0·y)；Ⅱ1·（x+y）当x=y(x+y)=0则；当（）则所以均有同理可证：所以·对+是可分配的。由①②③得，[{0，1}，+，·]是环。（2）[{0，1}，+，·]是域因为[{0，1}，+，·]是有限环，故只需证明是整环即可。①乘交环：由乘法运算表的对称性知，乘法可交换。②含幺环：乘法的幺元是1③无零因子：1·1=1≠0因此[{0，1}，+，·]是整环，故它是域。4、证：（1）“≤”是偏序关系，≤自然偏序①反自反性：由代数格幂等关系：。②反对称性：若即：，则③传递性：则：（2）在L中存在{x,y}的下（上）确界设则：事实上：若{x,y}有另一下界c，则是{x,y}最大下界，即同理可证上确界情况。四、14%解：函数表为：00000011010001111000101111011111析取范式：合取范式：五、10%解：用库斯克（Kruskal）算法求产生的最优树。算法为：结果如图：树权C(T)=23+1+4+9+3+17=57（万元）即为总造价试卷七试题与答案填空15%（每小题3分）任何(n,m)图G=(V,E),边与顶点数的关系是。当n为时,非平凡无向完全图Kn是欧拉图。已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有个1度顶点。n阶完全图Kn的点色数X(KN)=。一组学生,用两两扳腕子比赛来测定臂力大小,则幺元是。选择15%（每小题3分）1、下面四组数能构成无向图的度数列的有()。 A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。2、图的邻接矩阵为()。A、；B、；C、；D、。3、下列几个图是简单图的有()。G1=(V1,E1),其中V1={a,b,c,d,e},E1={ab,be,eb,ae,de}；G2=(V2,E2)其中V2=V1,E2={,,,,,}；G=(V3,E3),其中V3=V1,E3={ab,be,ed,cc}；G=(V4,E4),其中V4=V1,E4={（a,a）,（a,b）,（b,c）,（e,c）,（e,d）}。4、下列图中是欧拉图的有()。5、，其中，为集合对称差运算，则方程的解为（）。A、；B、；C、；D、。证明34%证明：在至少有2个人的人群中，至少有2个人，他的有相同的朋友数。（8分）若图G中恰有两个奇数顶点，则这两个顶点是连通的。（8分）证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。（8分）证明循环群的同态像必是循环群。（10分）中国邮递员问题13%求带权图G中的最优投递路线。邮局在v1 点。根树的应用13%在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。10%设B4={e,a,b,ab}，运算*如下表，*则是一个群（称作Klein四元群答案：填空15%（每小题3分）1、；2、奇数；3、5；4、n；5、臂力小者选择15%（每小题3分）题目12345答案BCBBA证明34%1、（10分）证明：用n个顶点v1，…，vn表示n个人，构成顶点集V={v1，…，vn}，设，无向图G=（V，E）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2）若G中有一个孤立点，则G中的至少有3个顶点，现不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中顶点数到值只能是1，2，…，n-1这n-1个数，因而取n-1个值的n个顶点的度数至少有两个结点度数是相同的。2、（8分）证：设G中两个奇数度结点分别为u，v。若u，v不连通，即它们中无任何通路，则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。3、（8分）证：n=6,m=12欧拉公式n-m+f=2知f=2-n+m=2-6-12=8由图论基本定理知：，而，所以必有，即每个面用3条边围成。4、（10分）证：设循环群[A，·]的生成元为a，同态映射为f，同态像为，于是都有对n=1有n=2,有若n=k-1时有对n=k时，这表明，f(A)中每一个元素均可表示为，所以是以f(a)生成元的循环群。中国邮递员问题14%解：图中有4个奇数结点，求任两结点的最短路再找两条道路使得它们没有相同的起点和终点，且长度总和最短：在原图中复制出，设图G‘，则图G‘中每个结点度数均为偶数的图G‘存在欧拉回路，欧拉回路C权长为43。根树的应用13%解：用100乘各频率并由小到大排列得权数用Huffman算法求最优二叉树：前缀码用00000传送5；00001传送6；0001传送7；100传送3；101传送4；001传送2；11传送1；01传送0（频率越高传送的前缀码越短）。10%证明：乘：由运算表可知运算*是封闭的。群：即要证明，这里有43=64个等式需要验证但：①e是幺元，含e的等式一定成立。②ab=a*b=b*a，如果对含a，b的等式成立，则对含a、b、ab的等式也都成立。③剩下只需验证含a、b等式，共有23=8个等式。即：(a*b)*a=ab*a=b=a*(b*a)=a*ab=b；(a*b)*b=ab*b=a=a*(b*b)=a*e=a；(a*a)*a=e*a=a=a*(a*a)=a*e=a；(a*a)*b=e*b=b=a*(a*b)=a*ab=b；(b*b)*a=e*a=a=b*(b*a)=b*ab=a；(b*b)*b=e*b=b=b*(b*b)=b*e=b；(b*a)*a=ab*a=b=b*(a*a)=b*e=b；(b*a)*b=ab*b=a=b*(a*b)=b*ab=a。幺：e为幺元逆：e-1=e；a-1=a；b-1=b；(ab)-1=ab。所以为群。试卷八试题与答案填空15%（每小题3分）n阶完全图Kn 的边数为。右图的邻接矩阵A=。图的对偶图为。完全二叉树中，叶数为nt，则边数m=。设<{a,b,c},*>为代数系统，*运算如下：*abcaabcbbaccccc则它的幺元为；零元为；a、b、c的逆元分别为。选择15%（每小题3分）图相对于完全图的补图为（）。对图G则分别为（）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（）片树叶。A、3；B、4；C、5；D、6设是代数系统，其中+，·为普通的加法和乘法，则A=（）时是整环。A、；B、；C、；D、。设A={1，2，…，10}，则下面定义的运算*关于A封闭的有（）。x*y=max(x,y)；B、x*y=质数p的个数使得；C、x*y=gcd(x,y)；(gcd(x,y)表示x和y的最大公约数)；D、x*y=lcm(x,y)（lcm(x,y)表示x和y的最小公倍数）。证明45%1、设G是（n,m）简单二部图，则。（8分）2、设G为具有n个结点的简单图，且则G是连通图。（8分）3、设G是阶数不小于11的简单图，则G或中至少有一个是非平图。（14分）4、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：+01·01001000110101证明它是一个环，并且是一个域。（15分）生成树及应用10%1、（10分）如下图所示的赋权图表示某七个城市及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。 2、（10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。5%对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。MaxMin+可结合性可交换性存在幺元存在零元答案：填空15%（每小题3分）1、；2、；3、；4、；5、a，c，a、b、没有选择15%（每小题3分）题目12345答案AACDA，C证明45%（8分）：设G=（V，E），对完全二部图有当时，完全二部图的边数m有最大值。故对任意简单二部图有。（8分）反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然。与假设矛盾。所以G连通。3、（14分）（1）当n=11时，边数条，因而必有或的边数大于等于28，不妨设G的边数，设G有k个连通分支，则G中必有回路。（否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则,矛盾）下面用反证法证明G为非平面图。假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3。于是G的每个面至少由g()条边围成，由点、边、面数的关系，得：而矛盾，所以G为非平面图。（2）当n>11时，考虑G的具有11个顶点的子图，则或必为非平面图。如果为非平面图，则为非平面图。如果为非平面图，则为非平面图。（15分）1）[{0，1}，+，·]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。群：（0+0）+0=0+（0+0）=0；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0……结合律成立。幺：幺元为0。逆：0，1逆元均为其本身。所以，<{0，1}，+>是Abel群。②<{0，1}，·>是半群乘：由“·”运算表知封闭群：(0·0)·0=0·（0·0）=0；（0·0）·1=0·（0·1）=1；（0·1）·0=0·（1·0）=1；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0；…③·对+的分配律对Ⅰ0·（x+y）=0=0+0=(0·x)+(0·y)Ⅱ1·（x+y）当x=y(x+y)=0则当（）则所以均有同理可证：所以·对+是可分配的。由①②③得，<{0，1}，+，·>是环。（2）<{0，1}，+，·>是域①乘交环：由乘法运算表的对称性知，乘法可交换。因为<{0，1}，+，·>是有限环，故只需证明是整环即可。②含幺环：乘法的幺元是1③无零因子：1·1=1≠0因此[{0，1}，+，·]是整环，故它是域。树的应用20%1、（10分）解：用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价五、（10分）由二叉树知H、A、P、Y、N、E、W、R对应的编码分别为000、001、010、011、100、101、110、111。显然{000，001，010，011，100，101，110，111}为前缀码。英文短语HAPPYNEWYEAR的编码信息为000001010010011100101001001101001111六、5%MaxMin+可结合性YYY可交换性YYY存在幺元NNY存在零元NNN试卷九试题与答案填空30%（每空3分）选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A=。集合A={,{}}的幂集P(A)=。设A={1，2，3，4}，A上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图。设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则=。=。设|A|=3，则A上有个二元关系。A={1，2，3}上关系R=时，R既是对称的又是反对称的。偏序集的哈斯图为，则=。设|X|=n，|Y|=m则（1）从X到Y有个不同的函数。（2）当n,m满足时，存在双射有个不同的双射。是有理数的真值为。Q：我将去上海，R：我有时间，公式的自然语言为。公式的主合取范式是。若是集合A的一个分划，则它应满足。选择20%（每小题2分）设全集为I，下列相等的集合是（）。A、；B、；C、；D、。设S={N，Q，R}，下列命题正确的是（）。A、；B、；C、；D、。设C={{a},{b},{a,b}}，则分别为（）。A、C和{a,b}；B、{a,b}与；C、{a,b}与{a,b}；D、C与C下列语句不是命题的有（）。x=13；B、离散数学是计算机系的一门必修课；C、鸡有三只脚；D、太阳系以外的星球上有生物；E、你打算考硕士研究生吗？的合取范式为（）。A、；B、；C、D、。设|A|=n，则A上有（）二元关系。A、2n；B、n2；C、；D、nn；E、。设r为集合A上的相容关系，其简化关系图（如图），则[I]r产生的最大相容类为（）；A、；B、；C、；D、[II]A的完全覆盖为（）。A、；B、；C、；D、。集合A={1，2，3，4}上的偏序关系图为则它的哈斯图为（）。下列关系中能构成函数的是（）。A、；B、；C、；D、。10、N是自然数集，定义（即x除以3的余数），则f是（）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。简答题15%1、(10分)设S={1,2,3,4,6,8,12,24}，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?2、（5分）设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？逻辑推理10%或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑并不难学。因此，如果许多学生喜欢逻辑，那么数学并不难学。五、10%设X={1,2,3,4,5}，X上的关系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}，用Warshall方法，求R的传递闭包t(R)。六、证明15%每一有限全序集必是良序集。（7分）设是复合函数，如果满射，则也是满射。（8分）答案填空20%（每小题2分）1、；2、；3、见右图；4、{<1,2>,<2,4>,<3,3>,<1，3>，<2,4>,<4,2>}、{<1,4>,<2,2>}；5、29；6、{<1,1>,<2,2>,<3,3>；7、{,,,,,,,,,}；8、mn、n=m、n!；9、假；10、我将去上海当且仅当我有空；11、；12、。选择20%（每小题2分）题目12345678910答案A、DCBA、EB、DCB、D；CABD简答题15%1、（10分）（1）≤={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>}covS={<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,<6,12>,<8,24>,<12,24>}Hass图为（2）极小元、最小元是1，极大元、最大元是24。2、（5分）解：公式A涵义为：对任意的实数x,y,z，如果x,<1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>}。证明15%1、（7分）证明：设，全序集。若不是良序集，那么必有一子集，在B中不存在最小元素，由于B是一有限集合，故一定可找出两元素x,y是无关的，由于是全序集。所以x,y必有关系，矛盾。故必是良序集。2、（8分）证明：设，由于满射，故必有使得，由复合函数定义知，存在使得，又因为g是函数，必对任，必使，任每个z在g作用下都是Y中元素的一个映象，由Z的任意性，所以g是满射。试卷十试题与答案填空10%（每小题2分）若P，Q为二命题，真值为1，当且仅当。对公式中自由变元进行代入的公式为。的前束范式为。设x是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y的自由的，则被称为全称量词消去规则，记为US。与非门的逻辑网络为。选择30%（每小题3分）下列各符号串，不是合式公式的有（）。A、；B、；C、；D、。下列语句是命题的有（）。A、2是素数；B、x+5>6；C、地球外的星球上也有人；D、这朵花多好看呀！。下列公式是重言式的有（）。A、；B、；C、；D、下列问题成立的有（）。若，则；B、若，则；C、若，则；D、若，则。命题逻辑演绎的CP规则为（）。在推演过程中可随便使用前提；B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C、如果要演绎出的公式为形式，那么将B作为前提，设法演绎出C；D、设是含公式A的命题公式，，则可用B替换中的A。命题“有的人喜欢所有的花”的逻辑符号化为（）。设D：全总个体域，F（x）：x是花，M(x)：x是人，H(x,y)：x喜欢yA、；B、；C、；D、。公式换名（）。A、；B、；C、；D、。给定公式，当D={a,b}时，解释（）使该公式真值为0。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=1下面蕴涵关系成立的是（）。A、；B、；C、；D、。10、下列推理步骤错在（）。①P②US①③ES②④UG③⑤EG④A、①→②；B、②→③；C、③→④；D、④→⑤。逻辑判断28%1、（8分）下列命题相容吗？2、（10分）用范式方法判断公式是否等价。3、（10分）下列前提下结论是否有效？今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。计算12%1、（5分）给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。求复合命题：的真值。2、（7分）给定解释I：D={2，3}，L（x,y）为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,求谓词合式公式的真值。逻辑推理20%1、（10分）所有有理数是实数，某些有理数是整数，因此某些实数是整数。2、（10分）符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。答案填空15%（每小题3分）1、P，Q的真值相同；2、；3、；4、；5、。选择30%（每小题3分）题目12345678910答案B、CA、CBC、DCDAB、CB、DC逻辑判断28%1、（8分）①P②AP③BT①②I④P⑤T④E⑥T⑤I⑦FT③⑥I所以不相容。2、（10分）所以两式等价。3、设P：今天天晴，Q：今天下雨，R：我不看书，S：我看电影符号化为：①P②P③T①②I④T③I⑤P⑥T⑤E⑦T④⑥I结论有效。计算12%1、（5分）解：P，Q是真命题，R是假命题。2、（7分）逻辑推理20%1、（10分）解：设R(x)：x是实数，Q(x)：x是有理数，I(x)：x是整数符号化：前提：，结论：①P②ES①③P④US③⑤T②I⑥T④⑤I⑦T②I⑧T⑥⑦I⑨EG⑧2、解：F(x)：x是病人，G(x)：x是医生，H(x)：x是骗子，L(x,y)：x相信y符号化：前提：结论：⑴P⑵ES⑴⑶T⑵I⑷T⑵I⑸P⑹US⑸⑺T⑶⑹I⑻T⑺E⑼US⑷⑽US⑻⑾T⑼⑽I⑿UG⑾卷十一试题与答案填空20%（每小题2分）1、称为命题。2、命题P→Q的真值为0，当且仅当。3、一个命题含有4个原子命题，则对其所有可能赋值有种。4、所有小项的析取式为。5、令P（x）：x是质数，E（x）：x是偶数，Q（x）：x是奇数，D（x，y）：x除尽y.则的汉语翻译为。6、设S={a，b,c}则S6的集合表示为。7、P（P()）=。8、=。9、设R为集合A上的关系，则t（R）=。10、若R是集合A上的偏序关系，则R满足。选择20%（每小题2分）下列命题正确的有（）。若是满射，则是满射；B、若是满射，则都是满射；C、若是单射，则都是单射；D、若单射，则是单射。设f，g是函数，当（）时，f=g。A、；B、；C、；D、。下列关系，（）能构成函数。A、；B、；C、；D、。下列函数（）满射；（）单射；（）双射（）；一般函数（）。A、；B、（除以3的余数）；C、；D、。集合A={1，2，3，4}上的偏序关系为，则它的Hass图为（）。设集合A={1，2，3，4，5}上偏序关系的Hass图为则子集B={2，3，4}的最大元（）；最小元（）；极大元（）；极小元（）；上界（）；上确界（）；下界（）；下确界（）。无，4，2、3，4，1，1，4，4；B、无，4、5，2、3，4、5，1，1，4，4；C、无，4，2、3，4、5，1，1，4，4；D、无，4，2、3，4，1，1，4，无。设R，S是集合A上的关系，则下列（）断言是正确的。自反的，则是自反的；B、若对称的，则是对称的；C、若传递的，则是传递的；D、若反对称的，则是反对称的设X为集合，|X|=n，在X上有（）种不同的关系。A、n2；B、2n；C、；D、。下列推导错在（）。①P②US①③ES②④UG③A、②；B、③；C、④；D、无。10、“没有不犯错误的人”的逻辑符号化为（）。设H（x）：x是人，P（x）：x犯错误。A、；B、；C、；D、。命题演绎28%1、（10分）用反证法证明。2、（8分）用CP规则证明。3、（10分）演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。8%将化为与其等价的前束范式。五、8%A={a,b,c,d}，R={,,,}为A上的关系，利用矩阵乘法求R的传递闭包，并画出t（R）的关系图。六、证明16%（8分）设A={1，2，3，4}，在P（A）上规定二元关系如下：P（A）证明R是P（A）上的等价关系并写出商集P（A）/R。（8分）设f是A到A的满射，且，证明f=IA。答案填空20%（每小题2分）能够断真假的阵述句；2、P的真值为1，Q的真值为0；3、24=16；4、永真式；5、任意两数x、y,如果x是偶数且能除尽y，则y一定是偶数；6、S110={a,b}；7、；8、；9、；10、自反性、反对称性、传递性二、选择20%（每小题2分）题目12345678910答案A、DBC、DC、D；A、D；D；BCAADCB、D三、命题演绎28%1、（10分）证明：⑴P（附加前提）⑵T⑴E⑶P⑷T⑶E⑸P⑹T⑷⑸E⑺T⑹E⑻T⑺I⑼T⑵⑻I⑽P⑾T⑽E⑿T⑾E⒀T⑼⑿I2、（8分）①P（附加前提）②P③T①②I④P⑤T③④I⑥T⑤E⑦CP3、证明：设Q（x）：x是有理数，R(x)：x是实数，N(x)：x是无理数，C(x)：x是虚数。前提：结论：⑴P⑵US⑴⑶P⑷US⑶⑸P⑹US⑸⑺T⑹E⑻T⑵⑺I⑼T⑷⑺I⑽T⑻⑼I⑾T⑽E⑿UG⑾四、8%解：五、8%解：所以t（R）={,,,,,,,,}关系图为六、证明16%1、（8分）证明：⑴P（A），由于，所以，即R自反的。⑵P（A），若，则，，R是对称的。⑶P（A），若：，即：所以R是传递的。由⑴⑵⑶知，R是等价关系。P（A）/R={[]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，[{1，2，3，4}]R}2、（8分）证明：因为f是满射，所以，存在使得，又因为f是函数，所以即由所以，又，所以由a的任意性知：f=IA。卷十二试题与答案填空20%（每空2分）设集合A={1，2，3，4，5，6，7，8，9，10}，定义A上的二元关系“≤”为x≤y=x|y,则=。设，定义A上的二元运算为普通乘法、除法和加法，则代数系统中运算*关于运算具有封闭性。设集合S={α，β，γ，δ，ζ}，S上的运算*定义为*αβγδζααβ
浙公网安备 33021202002483