離散數(shù)學試卷及答案1

FILENAME離散數(shù)學試卷（一）PAGE4PAGE5離散數(shù)學試卷（一）一、填空20%（每小題2分）1．設（N：自然數(shù)集，E+正偶數(shù)）則。2．A，B，C表示三個集合，文圖中陰影部分的集合表達式為ABCABC3．設P，Q的真值為0，R，S的真值為1，則的真值=。4．公式的主合取范式為。5．若解釋I的論域D僅包含一個元素，則在I下真值為。6．設A={1，2，3，4}，A上關(guān)系圖為則R2=。7．設A={a，b，c，d}，其上偏序關(guān)系R的哈斯圖為則R=。8．圖的補圖為。9．設A={a，b，c，d}，A上二元運算如下：*abcdabcdabcdbcdacdabdabc那么代數(shù)系統(tǒng)<A，*>的幺元是，有逆元的元素為，它們的逆元分別為。10．有n個結(jié)點，條邊的連通簡單圖是平面圖的必要條件______。二、選擇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上的二元關(guān)系有（）個。A．23；B．32；C．；D．。4、設R，S是集合A上的關(guān)系，則下列說法正確的是（）A．若R，S是自反的，則是自反的；B．若R，S是反自反的，則是反自反的；C．若R，S是對稱的，則是對稱的；D．若R，S是傳遞的，則是傳遞的。5、設A={1，2，3，4}，P（A）（A的冪集）上規(guī)定二元系如下則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上包含關(guān)系“”的哈斯圖為（）7、下列函數(shù)是雙射的為（）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—整數(shù)集，E—偶數(shù)集，N—自然數(shù)集，R—實數(shù)集）8、圖中從v1到v3長度為3的通路有（）條。A．0； B．1； C．2； D．3。9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（）10、在一棵樹中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點則該樹有（）個4度結(jié)點。A．1； B．2； C．3； D．4。三、證明26% 1.R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當且僅當<a,b>和<a,c>在R中有<.b,c>在R中。（8分）2．設函數(shù)，，若是滿射的，則是滿射的。3.G=<V,E>(|V|=v，|E|=e)是每一個面至少由k（k3）條邊圍成的連通平面圖，則，由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演16%用CP規(guī)則證明下題（每小題8分）1、2、五、計算18%1、設集合A={a，b，c，d}上的關(guān)系R={<a,b>,<b,a>,<b,c>,<c,d>}用矩陣運算求出R的傳遞閉包t(R)。（9分）2、如下圖所示的賦權(quán)圖表示某七個城市及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。（９分）一、填空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>