第1頁共1頁在您完成作業過程中，如有疑難，請登錄學院網站“輔導答疑”欄目，與老師進行交流討論！《離散數學》作業一、選擇或填空1．下列公式中哪些是永真式？()A.(┐PQ)→(Q→R)B.P→(Q→Q)C.(PQ)→PD.P→(PQ)2．設全體域D是正整數集合，確定下列命題的真值：A.xy(xy=y)()B.xy(x+y=y)()C.xy(x+y=x)()D.xy(y=2x)()3．有n個結點的樹，其結點度數之和是()。4．舉出集合A上的既是等價關系又是偏序關系的一個例子。()5．群<G,*>的等冪元是()，有()個。6．下面給出的集合中，哪一個不是前綴碼()。A.{a，ab，110，a1b11}B.{01，001，000，1}C.{1，2，00，01，0210}D.{12，11，101，002，0011}7．下列哪些公式為永真蘊含式？()A.Q=>Q→PB.Q=>P→QC.P=>P→QD.P(PQ)=>P8．設P：我生病，Q：我去學校，則下列命題可符號化為()。（1）若我生病，則我不去學校(2)當且僅當我生病時，我才不去學校9．任一有向圖中，度數為奇數的結點有()個。10．集合A上的等價關系的三個性質是什么？()11．群＜A,*＞的等冪元有()個，是()，零元有()個。12．一個圖的歐拉回路是一條通過圖中()的回路。13．設有下列公式，請問哪幾個是永真蘊涵式?()A.P=>PQB.PQ=>PC.PQ=>PQD.P(P→Q)=>QE.(P→Q)=>PF.P(PQ)=>P14．判斷下列命題哪幾個為正確？()A.{Ф}∈{Ф，{{Ф}}}B.{Ф}{Ф，{{Ф}}}C.Ф∈{{Ф}}D.Ф{Ф}E.{a,b}∈{a,b,{a},{b}}15．設a是10階群的生成元，則a4是()階元素，a3是()階元素。16．設G是一個哈密爾頓圖，則G一定是()。A.歐拉圖B.樹C.平面圖D.連通圖17．設G是一棵樹，則G的生成樹有()棵。A.0B.1C.2D.18．設無向圖G有16條邊且每個頂點的度數都是2，則圖G有()個頂點。A.10B.4C.8D.1619．Ａ，Ｂ，Ｃ是三個集合，則下列哪幾個推理正確：A.AB，BC=>ACB.AB，BC=>A∈BC.A∈B，B∈C=>A∈C20．設S={１，２，３，４}，Ａ上的關系Ｒ＝｛〈1，2〉，〈2，1〉，〈2，3〉，〈3，4〉｝，求(1)RR(2)R-1。21．一棵無向樹的頂點數n與邊數m關系是()。22．設A={3，6，9}，A上的二元運算*定義為：a*b=min{a，b}，則在獨異點<A，*>中，單位元是()，零元是()。23．設G是有n個結點m條邊的連通平面圖，且有k個面，則k等于:A.m-n+2B.n-m-2C.n+m-2D.m+n+2。24．設無向圖G有18條邊且每個頂點的度數都是3，則圖G有()個頂點。A.10B.4C.8D.1225、A，B，C是三個集合，則下列哪個推理正確?()(1)AB，BCAC(2)AB，BCAB(3)AB，BCAC26、判斷下列命題哪個正確?()(1){Ф}{Ф,{{Ф}}}(2){Ф}{Ф,{{Ф}}(3)Ф{{Ф}}(4)Ф={Ф}27、設T是一棵樹，則T是一個().(1)歐拉圖(2)哈密爾頓圖(3)連通圖28、下列公式中哪個不是蘊涵式?()(1)PPQ(2)PQP(3)PQPQ(4)P(P→Q)Q39、下面給出的集合中，哪一個不是前綴碼().(1){a，ab，110，a1b11}(2){01，001，000，1}(3){1，2，00，01，0210}(4){12，11，101，002，0011}306階有限群的任何子群一定不是().(1)2階(2)3階(3)4階(4)6階31、在有n個頂點的連通圖中，其邊數().(1)最多有n-1條(2)至少有n-1條(3)最多有n條(4)至少有n條32、下列哪一種圖不一定是樹?()(1)無簡單回路的連通圖(2)有n個頂點n-1條邊的連通圖(3)每對頂點間都有通路的圖(4)連通但刪去一條邊便不連通的圖33、下面給出的集合中，哪一個是前綴碼?()(1){0，10，110，101111}(2){01，001，000，1}(3){b，c，aa，ab，aba}(4){1，11，101，001，0011}34、有限布爾代數的元素的個數一定等于().(1)偶數(2)奇數(3)4的倍數(4)2的正整數次冪35、在自然數集N上，下列哪種運算是可結合的?()(1)a*b=a-b(2)a*b=max{a,b}(3)a*b=a+2b(4)a*b=|a-b|36、判斷下列命題哪個為真?()(1)A-B=B-AA=B(2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若A的一個元素屬于B，則A=B二、求下列各公式的主析取范式和主合取范式1．PQ2．Q→(PR)3．P→Q4．(P→Q)(RP)5．PQ6Q→(PR)7(P→Q)(P→R)三、證明1．PQ，P→R,Q→S=>RS2．A→(CB)，B→A，D→C=>A→D3．P→Q，QR，R，SP=>S4．BD，(E→F)→D，E=>B5．A→(B→C)，C→(DE)，F→(DE),A=>B→F6、A→(B→C)，C→(DE)，F→(DE),AB→F.7、BD，(E→F)→D，EB.8、A→(CB)，B→A，D→CA→D.9、P→Q，QR，RSP.四、設Ａ，Ｂ，Ｃ是三個集合，證明1．(A－B)∪(A－C)=A－(B∩C)2．A∩B=A∩C，∩B=∩C，則C=B3．A∩(B－C)＝(A∩B)－(A∩C)4．A－(B∪C)＝(A－B)－C5．(A－B)∩(A－C)=A－(B∪C)五、證明1．設e和0是關于A上二元運算*的單位元和零元，如果|A|>1，則e0。2．任一圖中度數為奇數的結點是偶數個。3．設群＜G，＊＞除單位元外每個元素的階均為2，則＜G，＊＞是交換群。4．在一個連通簡單無向平面圖G=〈V，E，F〉中若|V|3，則|E|3|V－6。5．單位元有惟一逆元。6．7．設代數系統<G,*>是一個群，則G除單位元以外無其它等冪元。8．若連通簡單無向平面圖G有n個結點，m條邊，k個面，且每個面至少由k(k3)條邊圍成，則mk(ｎ－2)／(ｋ－2)。9．證明在元素不少于兩個的群中不存在零元。10．素數階循環群的每個非單位元都是生成元。11．設G=〈V，E〉是一個連通且|V|=|E|+1的圖，則G中有一個度為1的結點。12．給定無向連通簡單平面圖G=<V,E,F>，且|V|=6,|E|=12,則對于任意fF,deg(f)=3。13．證明在一個群中單位元是惟一的。14．在一個群〈G，*〉中，若G中的元素a的階是k，即|a|=k，則