FILENAME離散數學試卷（一）PAGE4PAGE5離散數學試卷（一）一、填空20%（每小題2分）1．設（N：自然數集，E+正偶數）則。2．A，B，C表示三個集合，文圖中陰影部分的集合表達式為ABCABC3．設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上二元運算如下：*abcdabcdabcdbcdacdabdabc那么代數系統<A，*>的幺元是，有逆元的元素為，它們的逆元分別為。10．有n個結點，條邊的連通簡單圖是平面圖的必要條件______。二、選擇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}}6、設A={，{1}，{1，3}，{1，2，3}}則A上包含關系“”的哈斯圖為（）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的通路有（）條。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% 1.R是集合X上的一個自反關系，求證：R是對稱和傳遞的，當且僅當<a,b>和<a,c>在R中有<.b,c>在R中。（8分）2．設函數，，若是滿射的，則是滿射的。3.G=<V,E>(|V|=v，|E|=e)是每一個面至少由k（k3）條邊圍成的連通平面圖，則，由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演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、;二、選擇20%（每小題2分）題目12345678910答案CDB、CCADCADBD三、證明26%證：“”若由R對稱性知，由R傳遞性得“”若，有任意，因若所以R是對稱的。若，則即R是傳遞的。2、證明：，，∵是滿射，∴，使，令，則，∴是滿射。證：①設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)={<a,a>,<a,b>,<a,c>