离散期末套.docxVIP

离散数学试题与答案试卷一一、填空 20% （每小题2分）2．A，B，C表示三个集合，文图中阴影部分的集合表达式为。3．设P，Q 的真值为0，R，S的真值为1，则的真值= 。4．公式的主合取范式为。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上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统A，*的幺元是，有逆元的元素为，它们的逆元分别为。10．下图所示的偏序集中，是格的为任俩个点有唯一的最大下届和最小上届。二、选择 20% （每小题 2分）1、下列是真命题的有（　　　）A．；B．；C．； D．。2、下列集合中相等的有（bc） 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．。A上的二元关系是类 R={(a,b)} ,其中a，b均属于A，但不同(a,b)的组合决定关系即每个二元关系R 实际上是A*A的幂集的子集A*A有3*3个元素，A*A的幂集中含2^(3*3)个集合，2^3仅是A的幂集中集合个数，若是一元关系是2^3个4、设R，S是集合A上的关系，则下列说法正确的是（） A．若R，S 是自反的，则是自反的； B．若R，S 是反自反的，则是反自反的； C．若R，S 是对称的，则是对称的； D．若R，S 是传递的，则是传递的。7、下列函数是双射的为（）A．f : IE , f (x) = 2x ； B．f : NNN, f (n) = n , n+1 ；C．f : RI , f (x) = [x] ； D．f :IN, f (x) = | x | 。（注：I—整数集，E—偶数集， N—自然数集，R—实数集）8、图中从v1到v3长度为3 的通路有（ d ）条。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是对称和传递的，当且仅当 a, b 和a , c在R中有.b , c在R中。（8分）证：“”若由R对称性知，由R传递性得“”若，有任意，因若所以R是对称的。若，则即R是传递的。f和g都是群G1 ,★到 G2, *的同态映射，证明C , ★是G1, ★的一个子群。其中C= (8分)证，有，又★★★ C , ★ 是 G1 , ★的子群。证明子群：1，，有a*b的逆属于C2，有封闭性，可逆性G=V, E (|V| = v，|E|=e ) 是每一个面至少由k（k3）条边围成的连通平面图，则，由此证明彼得森图（Peterson）图是非平面图。（11分）解，①设G有r个面，则（度数大于边数），即。而故即得。（8分）②彼得森图为，这样不成立，四、逻辑推演 16%用CP规则证明下题（每小题 8分）1、2、五、计算 18%1、设集合A={a，b，c，d}上的关系R={a , b , b , a , b, c , c , d }用矩阵运算求出R的传递闭包t (R)。（9分）2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。　　（９分）试卷一答案：一、填空 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、{a.b,a,c,a,d,b,d,c,d} IA ；8、9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% （每小题 2分）题目12345678910答案C DB、CCADCADBA逻辑推演 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)={a , a , a , b , a