离散数学期末试卷及答案20套

1A第8页共8页一、单选题（20小题，每小题2分，共40分）得分1、设A={1，2，3}上的关系如下，有传递性的有（）。A．{<1，2>，<2，1>，<1，3>，<3，1>}B．{<1,3>，<3,1>}C．{<1，2>，<2,3>，<1，1>}D．{<1,2>，<3，2>}2、下列语句是命题的是（）A． 明年中秋节的晚上是晴天 B．C．请保持安静 D．我正在说谎3、下列哪个命题是假命题（）．A．如果2+2=4，则太阳从东方升起；B．如果2+2=4，则太阳从西方升起；C．如果2+24，则太阳从东方升起；D．如果2+24，则太阳从西方升起．4、设是正实数集，Ｒ是实数集，ｆ：ｆ，则ｆ是（）．A．是入射不是满射 B．是满射不是入射C．既非入射也非满射 D．是双射5、下列等价式不成立的是（）．A．B．C．D．．6、n阶完全图的边数为（）。A．n(n-1)/2；B．n-1；C．n+1；D．2n(n-1)7、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（）．A．ｎ－ｍ－１；B．ｎ－ｍ＋１；C．ｍ－ｎ＋１；D．ｍ－ｎ－１．8、设为整数集，：，，则是（）．A．是入射不是满射B．是满射不是入射C．既非入射也非满射D．是双射．9、设是一个复合映射。下列哪个命题是假命题（）．A．若是满射，则是满射 B．若是入射，则是入射C．若是双射，则和都是双射 D．若和都是双射，则是双射10、设，则有（）。A．{{1,2}}；B．{1,2}；C．{1}；D．{2}11、下列各图是欧拉图的是（）．ABCD12、在下述公式中是重言式为（）A．¬ B．C． D．P（QR）13、设，下列二元关系为到的函数的是()A．B．C．D．14、设为无向图，=7，=23，则G一定是（）。A．完全图；B．树；C．简单图；D．多重图15、下列各式哪个是错的（）？A.;B.{};C.;D.{,{}16、令:是金属，：是液体，：可以溶解在中，则命题“任何金属可以溶解在某种液体中”可符号化为（）．A．B．C．D．17、下面四组数能构成无向图的度数列的有（）。A．2,3,4,5,6,7；B．1,2,2,3,4；C．2,1,1,1,2；D．3,3,5,6,018、无向图是欧拉图，当且仅当（）．A．连通且所有结点的度数为偶数；B．的所有结点的度数为偶数；C．连通且所有结点的度数为奇数；D．的所有结点的度数为奇数．19、下列关系中能构成函数的是（）。A．；B．；C．；D．20、下列哪个谓词公式与等价？（）。A．B．C．D．二、填空题（20小题，每空1分，共20分）得分1、在偏序集中，，≤是上的整除关系，则的极大元是2、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则=3、命题公式的逆反式是。4、设，则A的幂集是．5、设表示“x是金子”，表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为。6、写出下表中所定义的命题联结词0001101100017、设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为．8、在偏序集中，其中={2,3,6,12,24,36}，≤是中的整除关系，则集合={2,3,6}的极大元是9、在下图所给的偏序集中，集合的上确界是。10、设A为任一集合，则．11、在下图所给的偏序集中，集合的下确界是。12、一棵树有2个度为2的结点，1个度为3的结点，4个度为4的结点，1个度为5的结点，其余均是度为1的结点，则有个度为1的结点．13、命题公式¬（PQ）的主析取范式为14、完全图K5的边数是。15、设是到的函数，若，则称为双射。16、设上的关系的关系图如下，从关系图可知具有的性质是．17、设表示“我将取得好成绩”，表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为。18、设是图的邻接矩阵，，则图中由到长度为的路径的条数为．19、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中称为树叶。20、设=｛｛，｛｝｝｝，则×=。其中表示集合的幂集．三、简答题（4小题，每小题6分，共24分）得分1、对有向图求解下列问题：1）写出邻接矩阵；2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。第2页共3页第1页共3页2、以给定权2，4，5，8，13，15，18，25构造一棵最优二叉树．3、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。子集上确界下确界4、今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示．要求设计一个最经济的煤气管道路线，并求所需的总费用．AABCDEFGHIJKS2222223.55452634531四、证明题（2小题，每小题8分，共16分）得分1、设函数，，证明是双射的。2、符号化下列命题并推证其结论．所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数．）．

一、单选题（20小题，每小题2分，共40分）1、D2、A3、B4、D5、B6、A7、C8、C9、C10、A11、B12、B13、A14、D15、C16、C17、B18、A19、B20、D二、填空题（20小题，每空1分，共20分）1、4，5，62、3、4、5、或6、∧7、或8、69、10、11、12、1413、（P∧┐Q）∨（┐P∧Q）14、1015、既是单射又是满射16、反自反性、反对称性和传递性17、18、19、出度为0的结点20、1B第8页共8页三、简答题（4小题，每小题6分，共24分）1、解：邻接矩阵为：（2分）（2分）由到长度为2的路有1条，由到长度为4的路有3条。(1分）3）的可达性矩阵为（1分）2、（根据树的完整程度酌情减分）3、答：子集上确界下确界无无4、解：该问题相当于求图的最小生成树问题，此图的最小生成树为：（4分）因此如图铺设煤气管道所需费用最小，最小费用为：2＋2＋2＋2＋2＋2＋2+3＋3+4+1＝25（万元）．（2分）四、证明题（2小题，每小题8分，共16分）1、证明：①假设存在，使得，则且，那么且，由此得，即f是入射。 （3分）②任取，均有，使得，从而是满射。（3分）综合①②知是双射。 （2分）2、该命题符号化为：（2分）证:(1)P(6)T(2)I（1分）(2)ES(1)（1分）(7)T(4),(5)I（1分）(3)P(8)T(6),(7)I（1分）(4)US(3)（1分）(9)EG(8)（1分）(5)T(2)I

一、单选题（20小题，每小题2分，共40分）得分1、下列等价式不成立的是（）．A．B．C．D．．2、令:是金属，：是液体，：可以溶解在中，则命题“任何金属可以溶解在某种液体中”可符号化为（）．A．B．C．D．3、设，下列二元关系为到的函数的是()A．B．C．D．4、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（）．A．ｎ－ｍ－１；B．ｎ－ｍ＋１；C．ｍ－ｎ＋１；D．ｍ－ｎ－１．5、无向图是欧拉图，当且仅当（）．A．连通且所有结点的度数为偶数；B．的所有结点的度数为偶数；C．连通且所有结点的度数为奇数；D．的所有结点的度数为奇数．6、设，则有（）。A．{{1,2}}；B．{1,2}；C．{1}；D．{2}7、下列关系中能构成函数的是（）。A．；B．；C．；D．8、下面四组数能构成无向图的度数列的有（）。A．2,3,4,5,6,7；B．1,2,2,3,4；C．2,1,1,1,2；D．3,3,5,6,09、设是正实数集，Ｒ是实数集，ｆ：ｆ，则ｆ是（）．A．是入射不是满射 B．是满射不是入射C．既非入射也非满射 D．是双射10、下列哪个谓词公式与等价？（）。A．B．C．D．11、设为整数集，：，，则是（）．A．是入射不是满射B．是满射不是入射C．既非入射也非满射D．是双射．12、下列语句是命题的是（）A． 明年中秋节的晚上是晴天 B．C．请保持安静 D．我正在说谎13、设A={1，2，3}上的关系如下，有传递性的有（）。A．{<1，2>，<2，1>，<1，3>，<3，1>}B．{<1,3>，<3,1>}C．{<1，2>，<2,3>，<1，1>}D．{<1,2>，<3，2>}14、下列各图是欧拉图的是（）．ABCD15、下列哪个命题是假命题（）．A．如果2+2=4，则太阳从东方升起；B．如果2+2=4，则太阳从西方升起；C．如果2+24，则太阳从东方升起；D．如果2+24，则太阳从西方升起．16、n阶完全图的边数为（）。A．n(n-1)/2；B．n-1；C．n+1；D．2n(n-1)17、在下述公式中是重言式为（）A．¬ B．C． D．P（QR）18、设是一个复合映射。下列哪个命题是假命题（）．A．若是满射，则是满射 B．若是入射，则是入射C．若是双射，则和都是双射 D．若和都是双射，则是双射19、下列各式哪个是错的（）？A.;B.{};C.;D.{,{}20、设为无向图，=7，=23，则G一定是（）。A．完全图；B．树；C．简单图；D．多重图二、填空题（20小题，每空1分，共20分）得分1、设表示“我将取得好成绩”，表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为。2、设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为．3、在下图所给的偏序集中，集合的上确界是。4、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则=5、设=｛｛，｛｝｝｝，则×=。其中表示集合的幂集．6、设是图的邻接矩阵，，则图中由到长度为的路径的条数为．7、一棵树有2个度为2的结点，1个度为3的结点，4个度为4的结点，1个度为5的结点，其余均是度为1的结点，则有个度为1的结点．8、写出下表中所定义的命题联结词0001101100019、完全图K5的边数是。10、命题公式¬（PQ）的主析取范式为11、设A为任一集合，则．12、在偏序集中，，≤是上的整除关系，则的极大元是13、设表示“x是金子”，表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为。14、在下图所给的偏序集中，集合的下确界是。15、命题公式的逆反式是。16、设，则A的幂集是．17、设上的关系的关系图如下，从关系图可知具有的性质是．18、设是到的函数，若，则称为双射。19、在偏序集中，其中={2,3,6,12,24,36}，≤是中的整除关系，则集合={2,3,6}的极大元是20、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中称为树叶。三、简答题（4小题，每小题6分，共24分）得分1、对有向图求解下列问题：1）写出邻接矩阵；2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。第2页共3页第1页共3页2、今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示．要求设计一个最经济的煤气管道路线，并求所需的总费用．AABCDEFGHIJKS2222223.554526345313、以给定权2，4，5，8，13，15，18，25构造一棵最优二叉树．4、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。子集上确界下确界四、证明题（2小题，每小题8分，共16分）得分1、设函数，，证明是双射的。2、符号化下列命题并推证其结论．所有有理数是实数，某些有理数是整数，因此某些实数是整数（设：是有理数，：是实数，：是整数．）．

一、单选题（20小题，每小题2分，共40分）1、B2、C3、A4、C5、A6、A7、B8、B9、D10、D11、C12、A13、D14、B15、B16、A17、B18、C19、C20、D二、填空题（20小题，每空1分，共20分）1、2、或3、4、5、6、7、148、∧9、1010、（P∧┐Q）∨（┐P∧Q）11、12、4，5，613、或14、15、16、17、反自反性、反对称性和传递性18、既是单射又是满射19、620、出度为0的结点2A第8页共8页三、简答题（4小题，每小题6分，共24分）1、解：邻接矩阵为：（2分）（2分）由到长度为2的路有1条，由到长度为4的路有3条。(1分）3）的可达性矩阵为（1分）2、解：该问题相当于求图的最小生成树问题，此图的最小生成树为：（4分）因此如图铺设煤气管道所需费用最小，最小费用为：2＋2＋2＋2＋2＋2＋2+3＋3+4+1＝25（万元）．（2分）3、（根据树的完整程度酌情减分）4、答：子集上确界下确界无无四、证明题（2小题，每小题8分，共16分）1、证明：①假设存在，使得，则且，那么且，由此得，即f是入射。 （3分）②任取，均有，使得，从而是满射。（3分）综合①②知是双射。 （2分）2、该命题符号化为：（2分）证:(1)P(6)T(2)I（1分）(2)ES(1)（1分）(7)T(4),(5)I（1分）(3)P(8)T(6),(7)I（1分）(4)US(3)（1分）(9)EG(8)（1分）(5)T(2)I

一、单选题（20小题，每小题2分，共40分）得分1、下列蕴含式不成立的是（）.A． B．C． D．.2、集合上的关系为一个偏序关系，当且仅当具有（）。A．自反性、对称性和传递性 B．自反性、反对称性和传递性C．反自反性、对称性和传递性 D．反自反性、反对称性和传递3、设是一个复合映射。下列哪个命题是假命题（）．A．若是满射，则是满射 B．若是入射，则是入射C．若是双射，则和都是双射 D．若和都是双射，则是双射4、设={1，2，3}，上的二元关系=，则的对称闭包是（）．A． B． C． D．5、下列各图是欧拉图的是（）．6、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（）．A．ｎ－ｍ－１；B．ｎ－ｍ＋１；C．ｍ－ｎ＋１；D．ｍ－ｎ－１．7、前提条件：P（QS），Q,PR,则它的有效推论为（）A．S B．RS C．P D．RQ8、命题公式中极小项的个数为（ ）A．0 B．1 C．2 D．39、谓词演算中，是的有效结论，其理论依据是（）．A．全称指定规则（US）C．全称推广规则（UG）B．存在指定规则（ES）D．存在推广规则（EG）．10、设，集合上的等价关系所确定的的划分的是{{a},{b,c}}，则=()A．{<a,a>,<b,b>,<c,b>,<b,c>,<c,c>}B．{<a,b>,<b,a>,<c,b>,<b,c>}C．{<a,b>,<b,a>,<c,b>}D．{<a,a>,<a,b>,<b,a>,<c,b>,<b,c>,<c,c>}11、设N为自然数集，：NN，则是()．A．是入射不是满射 B．既非入射也非满射C．是满射不是入射 D．是双射12、下面给出的四个图中，哪个不是汉密尔顿图（）．13、下列哪个命题是假命题（）．A．如果2+2=4，则太阳从东方升起；B．如果2+2=4，则太阳从西方升起；C．如果2+24，则太阳从东方升起；D．如果2+24，则太阳从西方升起．14、具有个结点的完全图是欧拉图，则为()。A．偶数；B．奇数；C．9；D．10．15、命题“所有的马都比某些牛跑得快”的符号化公式为（）假设：H（x）：x是马，C（y）：y是牛，F（x，y）：x跑得比y快。A．(x)(H（x）(y)((C（y）F(x,y)))B．(x)(H（x）(y)((C（y）F(x,y)))C．(x)(H（x）(y)((C（y）F(x,y)))D．(y)(x)(H（x）((C（y）F(x,y)))16、n阶完全图结点v的度数为（）。A．n；B．n-1；C．n+1；D．2(n-1)17、下面哪个图是强连通的（）．18、设是图的邻接矩阵，，则为（）．A．结点的度数；B．结点的度数；C．结点的入度；D．图中由到长度为的路径的条数．19、设有向图，其中，，则G是（）。A．强连通图B．单向连通图C．弱连通图D．非连通图20、，其中，为集合的对称差运算，则方程的解为（）。A．；B．；C．；D．二、填空题（20小题，每空1分，共20分）得分1、在任何图中，其奇数度结点的个数必为。2、完全图K5的边数是。3、无向图中有10条边，且每个结点的度数均为4，则结点数是．4、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中称为树根。5、设，上的二元关系=，则具有性。6、在下图所给的偏序集中，集合的下确界是。7、设是A到B的函数，若使是B到A的函数，必须满足8、设P，Q的真值为0，R，S的真值为1，则的真值=。9、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的极小元是10、以为子集的最少元素的集合为．11、设R是集合A上的二元关系，则r(R)=12、设R是实数集合，，，且，则13、给定命题公式：P（P（Q(QR)）则它的成假值为。14、集合上的关系，则=。15、由前提（x）（F（x）H（x））,（x）H（x）可得出的有效结论是16、写出下表中各列所定义的命题联结词00011011000117、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为。18、设,则=．其中表示集合的幂集．19、谓词公式（F（x,y）R（x,y））R（x,y）是（重言式，矛盾式，可满足式）20、设是到的函数，若，则称为双射。三、简答题（4小题，每小题6分，共24分）得分1、对有向图求解下列问题：1）写出邻接矩阵；2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。2、以给定权1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。3、下图给出的赋权图表示五个城市A、B、C、D、E及架起城市间直接通讯线路的预测造价（以千万RMB计）。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。4、设={1,2,3,5,6,10,15,30}，“／”为集合上的整除关系。〈，／〉是否为偏序集?若是，画出其哈斯图。四、证明题（2小题，每小题8分，共16分）得分1、符号化下列命题并推证其结论．任何人如果他喜欢音乐,他就不喜欢体育．每个人或者喜欢体育，或者喜欢美术．有的人不喜欢美术．因而有的人不喜欢音乐．（设M(x)：x喜欢音乐，S(x)：x喜欢体育，Ａ(x)：ｘ喜欢美术．个体域是人类集合）2、设函数，，证明是双射的。

一、单选题（20小题，每小题2分，共40分）12345678910ABCCBCBDAA11121314151617181920BDBBCBADCA二、填空题（20小题，每空1分，共20分）1、偶数2、103、54、入度为0的结点5、对称6、7、f是双射8、19、2,310、11、12、13、00014、15、（x）F（x）16、∧17、818、819、矛盾式20、既是单射又是满射三、简答题（4小题，每小题6分，共24分）1、解：邻接矩阵为：（2分）（2分）由到长度为2的路有1条，由到长度为4的路有2条。(1分）3）的可达性矩阵为（1分）2、（根据树的完整程度酌情减分）3、解：根据克鲁斯科尔算法，最小生成树如图所示，即包含如下四条边： （4分）C(A,B),C(B,C),C(D,E),C(B,E)C(T)=3+6+2+4=15(千万RMB) （2分）4、答：（1）〈，／〉是偏序集。（2分）（2）其哈斯图为：（4分）四、证明题（2小题，每小题8分，共16分）1、（1）该命题符号化为：（（ｘ）（M（x）→S（x））∧（ｘ）（S（x）∨A（x））∧（x）A（x））→（（x）M（x））（2分）（2）（6分）证：（1）（x）A（x）P（2）A（a）ES（1） （3）（ｘ）（S（x）∨A（x））P （4）S（a）∨A（a）US（3） （5）S（a）T（2）（4）I （6）（ｘ）（M（x）→S（x））P （7）M（a）→S（a）US（6） （8）S（a）→M（a）T（7）E （9）M（a）T（5）（8）I （10）（x）M（x）EG（9）2、证明：①假设存在，使得，则且，那么且，由此得，即f是入射。（3分）②任取，均有，使得，从而是满射。（3分）综合①②知是双射。 （2分）

一、单选题（20小题，每小题2分，共40分）得分1、设，集合上的等价关系所确定的的划分的是{{a},{b,c}}，则=()A．{<a,a>,<b,b>,<c,b>,<b,c>,<c,c>}B．{<a,b>,<b,a>,<c,b>,<b,c>}C．{<a,b>,<b,a>,<c,b>}D．{<a,a>,<a,b>,<b,a>,<c,b>,<b,c>,<c,c>}2、设是一个复合映射。下列哪个命题是假命题（）．A．若是满射，则是满射 B．若是入射，则是入射C．若是双射，则和都是双射 D．若和都是双射，则是双射3、下面给出的四个图中，哪个不是汉密尔顿图（）．4、下列蕴含式不成立的是（）.A． B．C． D．.5、下面哪个图是强连通的（）．6、具有个结点的完全图是欧拉图，则为()。A．偶数；B．奇数；C．9；D．10．7、下列各图是欧拉图的是（）．8、，其中，为集合的对称差运算，则方程的解为（）。A．；B．；C．；D．9、前提条件：P（QS），Q,PR,则它的有效推论为（）A．S B．RS C．P D．RQ10、设有向图，其中，，则G是（）。A．强连通图B．单向连通图C．弱连通图D．非连通图11、下列哪个命题是假命题（）．A．如果2+2=4，则太阳从东方升起；B．如果2+2=4，则太阳从西方升起；C．如果2+24，则太阳从东方升起；D．如果2+24，则太阳从西方升起．12、设={1，2，3}，上的二元关系=，则的对称闭包是（）．A． B． C． D．13、设是图的邻接矩阵，，则为（）．A．结点的度数；B．结点的度数；C．结点的入度；D．图中由到长度为的路径的条数．14、命题公式中极小项的个数为（ ）A．0 B．1 C．2 D．315、集合上的关系为一个偏序关系，当且仅当具有（）。A．自反性、对称性和传递性 B．自反性、反对称性和传递性C．反自反性、对称性和传递性 D．反自反性、反对称性和传递16、设N为自然数集，：NN，则是()．A．是入射不是满射 B．既非入射也非满射C．是满射不是入射 D．是双射17、命题“所有的马都比某些牛跑得快”的符号化公式为（）假设：H（x）：x是马，C（y）：y是牛，F（x，y）：x跑得比y快。A．(x)(H（x）(y)((C（y）F(x,y)))B．(x)(H（x）(y)((C（y）F(x,y)))C．(x)(H（x）(y)((C（y）F(x,y)))D．(y)(x)(H（x）((C（y）F(x,y)))18、设G=〈V，E〉为（ｎ，ｍ）连通图，则要确定Ｇ的一棵生成树，必删去Ｇ的边数是（）．A．ｎ－ｍ－１；B．ｎ－ｍ＋１；C．ｍ－ｎ＋１；D．ｍ－ｎ－１．19、谓词演算中，是的有效结论，其理论依据是（）．A．全称指定规则（US）C．全称推广规则（UG）B．存在指定规则（ES）D．存在推广规则（EG）．20、n阶完全图结点v的度数为（）。A．n；B．n-1；C．n+1；D．2(n-1)二、填空题（20小题，每空1分，共20分）得分1、设是到的函数，若，则称为双射。2、谓词公式（F（x,y）R（x,y））R（x,y）是（重言式，矛盾式，可满足式）3、设,则=．其中表示集合的幂集．4、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为。5、写出下表中各列所定义的命题联结词0001101100016、在下图所给的偏序集中，集合的下确界是。7、设是A到B的函数，若使是B到A的函数，必须满足8、设P，Q的真值为0，R，S的真值为1，则的真值=。9、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的极小元是10、以为子集的最少元素的集合为．11、设R是集合A上的二元关系，则r(R)=12、设R是实数集合，，，且，则13、给定命题公式：P（P（Q(QR)）则它的成假值为。14、集合上的关系，则=。15、由前提（x）（F（x）H（x））,（x）H（x）可得出的有效结论是16、设，上的二元关系=，则具有性。17、一棵有向树T，若T恰有一个结点的入度为0，其余所有结点的入度都为1，则称T为根树。其中称为树根。18、无向图中有10条边，且每个结点的度数均为4，则结点数是．19、完全图K5的边数是。20、在任何图中，其奇数度结点的个数必为。三、简答题（4小题，每小题6分，共24分）得分1、对有向图求解下列问题：1）写出邻接矩阵；2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。2、以给定权1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。3、设={1,2,3,5,6,10,15,30}，“／”为集合上的整除关系。〈，／〉是否为偏序集?若是，画出其哈斯图。4、下图给出的赋权图表示五个城市A、B、C、D、E及架起城市间直接通讯线路的预测造价（以千万RMB计）。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。四、证明题（2小题，每小题8分，共16分）得分1、设函数，，证明是双射的。2、符号化下列命题并推证其结论．任何人如果他喜欢音乐,他就不喜欢体育．每个人或者喜欢体育，或者喜欢美术．有的人不喜欢美术．因而有的人不喜欢音乐．（设M(x)：x喜欢音乐，S(x)：x喜欢体育，Ａ(x)：ｘ喜欢美术．个体域是人类集合）

一、单选题（20小题，每小题2分，共40分）12345678910ACDAABBABC11121314151617181920BCDDBBCCAB二、填空题（20小题，每空1分，共20分）1、既是单射又是满射2、矛盾式3、84、85、∧6、7、f是双射8、19、2,310、11、12、13、00014、15、（x）F（x）16、对称17、入度为0的结点18、519、1020、偶数三、简答题（4小题，每小题6分，共24分）1、解：邻接矩阵为：（2分）（2分）由到长度为2的路有1条，由到长度为4的路有2条。(1分）3）的可达性矩阵为（1分）2、（根据树的完整程度酌情减分）3、答：（1）〈，／〉是偏序集。（2分）（2）其哈斯图为：（4分）4、解：根据克鲁斯科尔算法，最小生成树如图所示，即包含如下四条边： （4分）C(A,B),C(B,C),C(D,E),C(B,E)C(T)=3+6+2+4=15(千万RMB) （2分）四、证明题（2小题，每小题8分，共16分）1、证明：①假设存在，使得，则且，那么且，由此得，即f是入射。（3分）②任取，均有，使得，从而是满射。（3分）综合①②知是双射。 （2分）2、（1）该命题符号化为：（（ｘ）（M（x）→S（x））∧（ｘ）（S（x）∨A（x））∧（x）A（x））→（（x）M（x））（2分）（2）（6分）证：（1）（x）A（x）P（2）A（a）ES（1） （3）（ｘ）（S（x）∨A（x））P （4）S（a）∨A（a）US（3） （5）S（a）T（2）（4）I （6）（ｘ）（M（x）→S（x））P （7）M（a）→S（a）US（6） （8）S（a）→M（a）T（7）E （9）M（a）T（5）（8）I （10）（x）M（x）EG（9）

一、单选题（20小题，每小题2分，共40分）得分1、，其中，为集合的对称差运算，则方程的解为（）。A．；B．；C．；D．2、给定命题公式：（PQ）（PR），与之等价的是（）A．P（QR）B．P（QR）C．P（QR）D．P（QR）3、设为实数集，函数：，，则是（）．A．是入射不是满射 B．是满射不是入射C．既非入射也非满射 D．是双射4、设N为自然数集，：NN，则是()．A．是入射不是满射 B．既非入射也非满射C．是满射不是入射 D．是双射5、下图中既不是欧拉图，也不是汉密尔顿图的图是（）。ABCD6、一个无向树中有7条边，则它结点数为()。A.5；B.6；C.7；D.8．7、设是集合上的任意函数，下列哪个命题是真命题（）．A． B．C． D．8、下列各图是欧拉图的是（）．9、设，以下哪一个关系是从到的满射（）．A． B．C． D．10、设和是集合上的任意两个关系，则下列命题为真的是（）．A．若和是自反的，则也是自反的B．若和是非自反的，则也是非自反的C．若和是对称的，则也是对称的D．若和是传递的，则也是传递的11、给定命题公式如下：（PQ）（PQ）该命题公式的成真赋值个数（）A．0B．1C．2D．312、设，则有（）个元素。A．3；B．6；C．7；D．813、谓词公式中量词（）辖域是（）。A． B．C． D．14、下面哪个图是强连通的（）．15、下列等价公式正确的是（）。A．；B．；C．；D．．16、下面四组数能构成无向简单图的度数列的有（）。A．2,2,2,2,2,2；B．1,2,3,4,5,5；C．1,2,3,4,5,6；D．2,2,3,4,5,617、无向图中有16条边，且每个结点的度数均为2，则结点数是（）．A．8B．16C．4D．3218、设A={1，2，3}，关系R是A上的二元关系，且R={<1，2>}，则关系R所具有的性质是（）A．自反性，反对称性，可传递性B．反自反性，反对称性，可传递性C．自反性，对称性，可传递性D．反自反性，反对称性19、谓词演算中，是的有效结论，其理论依据是（）．A．全称指定规则（US）C．全称推广规则（UG）B．存在指定规则（ES）D．存在推广规则（EG）．20、由前提：(x)(P（x）（Q（x）R（x）），(x)(P（x）（R（x）S（x）））,(x)(P（x）S（x））,则它的有效推论为（）A．(x)(P（x）Q（x））B．(x)(P（x）Q（x））C．(x)(P（x）Q（x））D．(x)(P（x）Q（x））二、填空题（20小题，每空1分，共20分）得分1、设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为．2、设表示“我将去书店”，表示“我有时间”，则命题“我将去书店，仅当我有时间”符号化为。3、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最大元是4、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G)=，则的入度为。5、设,则的双射共有．6、设，则=。其中表示集合Ａ的幂集。7、设R是实数集合，，，且，则8、命题公式¬（PQ）的主合取范式为9、设=｛｛，｛｝｝｝，则×=。其中表示集合的幂集．10、设，上的二元关系=，则具有___________________性。11、设集合Ａ＝｛ａ，ｂ，ｃ｝上的关系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，则Ｒ具有____________________________12、设表示“我将取得好成绩”，表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为。13、设A为任一集合，则．14、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为。15、对谓词公式（（x）P（x）（y）Q（y））（x）R（x）中约束变元应用变换规则所得到的前束范式是16、命题公式¬（PQ）的主析取范式为17、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则=18、设是到的函数，当为双射时，是到的函数，=19、无向图中有10条边，且每个结点的度数均为4，则结点数是．20、无向图G具有生成树，当且仅当___________________。三、简答题（4小题，每小题6分，共24分）得分1、设={1,2,3,5,6,10,15,30}，“／”为集合上的整除关系。〈，／〉是否为偏序集?若是，画出其哈斯图。2、下图给出的赋权图表示七个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。3、对有向图求解下列问题：1）写出邻接矩阵；2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。第2页共3页第3页共3页4、以给定权1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。四、证明题（2小题，每小题8分，共16分）得分1、证明函数，是双射。2、任何人如果他喜欢步行，他就不喜欢乘汽车。每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。（设：喜欢步行，：喜欢乘汽车，：骑自行车．个体域为所有人的集合）

一、单选题（20小题，每小题2分，共40分）1、A2、C3、A4、B5、B6、D7、C8、B9、B10、A11、C12、D13、D14、A15、B16、A17、B18、B19、A20、C二、填空题（20小题，每空1分，共20分）1、或2、3、无4、35、66、7、8、(P∨Q)∧(┐P∨┐Q)9、10、对称11、传递性、反对称性12、13、14、815、（x）（y）（z）（P（x）Q（y））R（z））16、17、18、19、520、图G连通2B第7页共8页三、简答题（4小题，每小题6分，共24分）1、答：（1）〈，／〉是偏序集。（2分）（2）其哈斯图为：（4分）2、解：该问题相当于求图的最小生成树问题，此图的最小生成树为： （4分）因此如图架线使得各城市间能够通讯且总造价最小，最小造价费用为：1＋3＋4＋8＋9＋23＝48．（2分）3、解：邻接矩阵为：（2分）（2分）由到长度为2的路有1条，由到长度为4的路有2条。(1分）3）的可达性矩阵为（1分）4、（根据树的完整程度酌情减分）四、证明题（2小题，每小题8分，共16分）1、证明：①任取，且，则所以，即f是入射。 （3分）②对任意的，都存在，使得，从而是满射。 （3分）综合①②知是双射。 （2分）2、该命题符号化为：（2分）证明:(1)P(2)ES(1)（1分）(3)P(4)US(3) （1分）(5)T(2)(4)I （1分）(6)P(7)US(6) （1分）(8)T(5),(7)I （1分）(9)EG(8) （1分）一、单选题（20小题，每小题2分，共40分）得分1、给定命题公式如下：（PQ）（PQ）该命题公式的成真赋值个数（）A．0B．1C．2D．32、下面哪个图是强连通的（）．3、无向图中有16条边，且每个结点的度数均为2，则结点数是（）．A．8B．16C．4D．324、设，以下哪一个关系是从到的满射（）．A． B．C． D．5、给定命题公式：（PQ）（PR），与之等价的是（）A．P（QR）B．P（QR）C．P（QR）D．P（QR）6、设，则有（）个元素。A．3；B．6；C．7；D．87、下列各图是欧拉图的是（）．8、，其中，为集合的对称差运算，则方程的解为（）。A．；B．；C．；D．9、下面四组数能构成无向简单图的度数列的有（）。A．2,2,2,2,2,2；B．1,2,3,4,5,5；C．1,2,3,4,5,6；D．2,2,3,4,5,610、设和是集合上的任意两个关系，则下列命题为真的是（）．A．若和是自反的，则也是自反的B．若和是非自反的，则也是非自反的C．若和是对称的，则也是对称的D．若和是传递的，则也是传递的11、设N为自然数集，：NN，则是()．A．是入射不是满射 B．既非入射也非满射C．是满射不是入射 D．是双射12、设为实数集，函数：，，则是（）．A．是入射不是满射 B．是满射不是入射C．既非入射也非满射 D．是双射13、设A={1，2，3}，关系R是A上的二元关系，且R={<1，2>}，则关系R所具有的性质是（）A．自反性，反对称性，可传递性B．反自反性，反对称性，可传递性C．自反性，对称性，可传递性D．反自反性，反对称性14、谓词演算中，是的有效结论，其理论依据是（）．A．全称指定规则（US）C．全称推广规则（UG）B．存在指定规则（ES）D．存在推广规则（EG）．15、谓词公式中量词（）辖域是（）。A． B．C． D．16、由前提：(x)(P（x）（Q（x）R（x）），(x)(P（x）（R（x）S（x）））,(x)(P（x）S（x））,则它的有效推论为（）A．(x)(P（x）Q（x））B．(x)(P（x）Q（x））C．(x)(P（x）Q（x））D．(x)(P（x）Q（x））17、下图中既不是欧拉图，也不是汉密尔顿图的图是（）。ABCD18、下列等价公式正确的是（）。A．；B．；C．；D．．19、设是集合上的任意函数，下列哪个命题是真命题（）．A． B．C． D．20、一个无向树中有7条边，则它结点数为()。A.5；B.6；C.7；D.8．二、填空题（20小题，每空1分，共20分）得分1、命题公式¬（PQ）的主析取范式为2、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最大元是3、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为。4、命题公式¬（PQ）的主合取范式为5、设，上的二元关系=，则具有___________________性。6、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G)=，则的入度为。7、无向图G具有生成树，当且仅当___________________。8、设，则=。其中表示集合Ａ的幂集。9、设=｛｛，｛｝｝｝，则×=。其中表示集合的幂集．10、无向图中有10条边，且每个结点的度数均为4，则结点数是．11、设R是实数集合，，，且，则12、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则=13、对谓词公式（（x）P（x）（y）Q（y））（x）R（x）中约束变元应用变换规则所得到的前束范式是14、设表示“我将去书店”，表示“我有时间”，则命题“我将去书店，仅当我有时间”符号化为。15、设集合Ａ＝｛ａ，ｂ，ｃ｝上的关系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，则Ｒ具有______________________________16、设A为任一集合，则．17、设是到的函数，当为双射时，是到的函数，=18、设,则的双射共有．19、设表示“我将取得好成绩”，表示“我努力学习”，则命题“我将取得好成绩，仅当我努力学习”符号化为。20、设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为．三、简答题（4小题，每小题6分，共24分）得分1、以给定权1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。2、对有向图求解下列问题：1）写出邻接矩阵；2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。第2页共3页第1页共3页3、下图给出的赋权图表示七个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。4、设={1,2,3,5,6,10,15,30}，“／”为集合上的整除关系。〈，／〉是否为偏序集?若是，画出其哈斯图。四、证明题（2小题，每小题8分，共16分）得分1、证明函数，是双射。2、任何人如果他喜欢步行，他就不喜欢乘汽车。每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。（设：喜欢步行，：喜欢乘汽车，：骑自行车．个体域为所有人的集合）

一、单选题（20小题，每小题2分，共40分）1、C2、A3、B4、B5、C6、D7、B8、A9、A10、A11、B12、A13、B14、A15、D16、C17、B18、B19、C20、D二、填空题（20小题，每空1分，共20分）1、（P∧┐Q）∨（┐P∧Q）2、无3、84、(P∨Q)∧(┐P∨┐Q)5、对称6、37、图G连通8、9、10、511、12、13、（x）（y）（z）（P（x）Q（y））R（z））14、15、传递性、反对称性16、17、18、619、20、或三、简答题（4小题，每小题6分，共24分）1、（根据树的完整程度酌情减分）2、解：邻接矩阵为：（2分）（2分）由到长度为2的路有1条，由到长度为4的路有2条。(1分）3）的可达性矩阵为（1分）3、解：该问题相当于求图的最小生成树问题，此图的最小生成树为： （4分）因此如图架线使得各城市间能够通讯且总造价最小，最小造价费用为：1＋3＋4＋8＋9＋23＝48．（2分）4、答：（1）〈，／〉是偏序集。（2分）（2）其哈斯图为：（4分）四、证明题（2小题，每小题8分，共16分）1、证明：①任取，且，则所以，即f是入射。 （3分）②对任意的，都存在，使得，从而是满射。 （3分）综合①②知是双射。 （2分）2、该命题符号化为：（2分）证明:(1)P(2)ES(1)（1分）(3)P(4)US(3) （1分）(5)T(2)(4)I （1分）(6)P(7)US(6) （1分）(8)T(5),(7)I （1分）(9)EG(8) （1分）

一、单选题（20小题，每小题2分，共40分）得分1．设A为图G的邻接矩阵，的主对角线元素之和为600，则G上有（）个三角形。A．100；B．200；C．300；D．6002．设，则有（）。A．{{1,2}}；B．{1,2}；C．{1}；D．{2}3．下列关系中能构成函数的是（）。A．；B．；C．；D．4．52张扑克牌分配给4个桥牌比赛者进行比赛，那么扑克牌集合A到桥牌比赛者集合B的函数是（）。A.入射B.满射C.双射D.映射5．下列符号串是合式公式的是（）A、；B、；C、；D、。6．关系R所具有的关系矩阵，则关系R所具有的性质是（）A．自反的，对称的，可传递的B．自反的，反对称的，可传递的C．自反的，对称的D．都不是7．下列等价式不成立的是（）．A．B．C． D．．8．设，以下哪一个关系是从到的满射()。A．B．C．D．9．下列各图不是欧拉图的是（）．10．设图G有5个结点，若各结点的度数分别为：3,4,6,2,3,则G有（）条边。A．10；B．20；C．9；D．18．11．下列句子是命题的是()．A．再过5000年，地球上就没水了．B．．C．水开了吗?D．我正在说谎．12．下列等价公式正确的是（）．A．；B．；C．；D．．13．给定公式：(x)(A（x）B），与之等价的公式是（）A．(x)A（x）B B．(x)A（x）BC．B(x)A（x） D．B(x)A（x）14．下面哪个图是强连通的（）．15．下图中是哈密尔顿图的是（）。16．命题公式中极小项的个数为（ ）A．0 B．1 C．2 D．317．下列等价式不成立的是（）.A．;B．C．D．18．设，下列二元关系为到的函数的是()A．B．C．D．19．下面哪一种图不一定是树（）．A．无圈的连通图；B．有ｎ个结点ｎ－１条边的连通图；C．每对结点间都有路的图；D．连通但删去一条边就不连通的图．20．设为无向图，=7，=23，则G一定是（）。A．完全图；B．树；C．简单图；D．多重图二、填空题（20小题，每空1分，共20分）得分1．设命题公式的真值表为00001111001100110101010100101100则命题公式的主析取范式为。2．设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为．3．设A为任一集合，则．4．设是到的函数，如果，则称为5．设集合Ａ＝｛ａ，ｂ，ｃ｝上的关系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，ｔ（Ｒ）＝6．完全图K5的连通分支数是。7．设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G)=，则的出度为。8．对谓词公式（（x）P（x）（y）Q（y））（x）R（x）中约束变元应用变换规则所得到的前束范式是9．设的函数，且，则。10．设表示“天下雨”，表示“我骑自行车上班”，则命题“除非下雨，否则我骑自行车上班”符号化为。11．写出下表中所定义的命题联结词00011011011112．命题公式（PQ）（QP）的主析取范式为。13．设是集合上的二元关系，则=。14．命题公式的逆反式是。15．在偏序集中，其中={2,3,6,12,24,36}，≤是中的整除关系，则集合={2,3,6}的极大元是16．设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则的关系矩阵是。17．设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为。18．设R是实数集合，，，且，则19．在任何有向图中，=。20．在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的极小元是三、简答题（4小题，每小题6分，共24分）得分1．以给定权2，4，5，8，13，15，18，25构造一棵最优二