第一篇：同濟大學考博離散數學試題2006年試題
同濟大學考博離散數學試題2006年試題（330）
一、二、給出下列定義，簡要敘述其作用。（15分）（1）關系；（2）合取范式；（3）格 證明下列命題(50分)
n1.集合A的冪集P???中元素個數為2。
(答案參見《離散數學 理論·分析·題解》第148頁3—66)
2.一有向圖G=(V,E)，其基本回路長度不大于|V|，V是結點集。
(答案可借鑒《離散數學》第280頁定理7-2.1證明，此時有結點vj=vk，j=k)
3.代數系統?S,??，運算“?”若存在單位元素，則必惟一。
(答案參見《離散數學》p181定理5-2.1證明，零元證明參見《離散數學 理論·分析·題解》p268 5—6)
4.。（P?Q）?R?（P?R）?（?Q?R）
5.設
證明(a?b)?(b?c)?(a?b)?(a?c)。?b?c（注：?為偏序關系符號），(答案參見《離散數學 理論·分析·題解》第326頁6—10)
三、綜合題(35分，第1題15分，第2題20分)
1． 有集合?3,5,15?,?1,2,3,6,12?,?3,9,27,54?，其上面的偏序關系為整除，畫出集合的偏序關系圖，并指出哪個是全序關系。(答案參見《離散數學 理論·分析·題解》第184頁3—136)
2． 有一農村集市平時每天開放，遇雨天則三天開放一次，用有限狀態機實現該模型。離散
1． 函數、映射和關系的定義及其它們間的不同。
2． 根據所給出的條件構造一個自動機，并轉換成另一種自動機形式。
3． 證明謂詞關系式兩邊等價。
4． 有關群、子群的相關證明。
5． 證明某偏序關系是否是格。
6． 有關左陪集和右陪集的一個證明。
第二篇：同濟大學考博離散數學試題2007年試題
同濟大學考博離散數學試題2007年試題（330）
一、寫出定義（15分）（1）格；（2）置換；（3）圖。
二、證明下列命題(50分)
1.不記得
2.等價式證明題。
3.下列合取范式是否為可滿足的：
E＝（X1∨ˉX2）∧（ˉX1∨X2）∧ˉX3(答案：可滿足解為（1,1,0）或(0,0,0)，可能用真值表法求解比較好)
4.不記得
5.證明圖的邊數與圖的度數的關系，即圖的度數為2n，n為邊數。(答案見《離散數學》第274頁定義7-1.2證明)
三、綜合題(35分，第1題15分，第2題20分)
1． 不記得
2．找一種9個a，9個b，9個c的圓形排列，使由字母｛a,b,c｝組成的長度為3的27個字的每個字僅出現一次。
(答案參見《離散數學 理論·分析·題解》第387頁7—
第三篇：同濟大學考博離散數學試題2008年試題（最終版）
同濟大學考博離散數學試題2008年試題（330）
一、名詞解釋并說明其作用（15分）
1．格2.關系3.代數系統
二、證明下列命題（50分）
1．2．
3．4．
5．三、1．
2．3．
數。R為等價關系，則必有等價類 一個圖是歐拉圖的充要條件是圖中各點的度為偶數 證明兩條件命題等價，例如：A?B??A?B 半群中單位元e唯一 格中a?b?c?d，類似證明(a?b)?c?b 綜合題（35分）給定兩個圖，說明其同構 畫?a,b,c,d?的冪集對應的哈斯圖 設計一個有限狀態機M，接收a、b字符，a的個數為偶數，b的個數為3的倍
第四篇：離散數學試題
中央電大離散數學試題
月
一、單項選擇題（每小題3分，本題共15分）
1．若集合A={1，{2}，{1，2}}，則下列表述正確的是()．
A．2?AB．{1}?A
C．1?AD．2 ? A
2．已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數為
()．
A．6B．4C．3D．
53．設無向圖G的鄰接矩陣為
?01111??10011????10000???11001????11010??
則G的邊數為()．
A．1B．7C．6D．14 4．設集合A={a}，則A的冪集為()．
A．{{a}}B．{a，{a}}
C．{?，{a}}D．{?，a}
5．下列公式中()為永真式．
A．?A??B ? ?A??BB．?A??B ? ?(A?B)
C．?A??B ? A?BD．?A??B ? ?(A?B)
二、填空題（每小題3分，本題共15分）
6．命題公式P??P的真值是
7．若無向樹T有5個結點，則T的邊數為．
8．設正則m叉樹的樹葉數為t，分支數為i，則(m-1)i
9．設集合A={1，2}上的關系R＝{<1, 1>,<1, 2>}，則在R中僅需加一個元素，就可使新得到的關系為對稱的．
10．(?x)(A(x)→B(x，z)∨C(y))中的自由變元有．
三、邏輯公式翻譯（每小題6分，本題共12分）
11．將語句“今天上課．”翻譯成命題公式．
12．將語句“他去操場鍛煉，僅當他有時間．”翻譯成命題公式．
四、判斷說明題（每小題7分，本題共14分）
判斷下列各題正誤，并說明理由．
13．設集合A={1，2}，B={3，4}，從A到B的關系為f={<1, 3>}，則f是A到B的函數．
14．設G是一個有4個結點10條邊的連通圖，則G為平面圖．
五．計算題（每小題12分，本題共36分）
15．試求出（P∨Q）→（R∨Q）的析取范式．
16．設A={{1}, 1, 2}，B={ 1, {2}}，試計算
（1）（A∩B）（2）（A∪B）（3）A ?（A∩B）．
17．圖G=
（1）畫出G的圖形；
（2）寫出G的鄰接矩陣；
（3）求出G權最小的生成樹及其權值．
六、證明題（本題共8分）
18．試證明：若R與S是集合A上的自反關系，則R∩S也是集合A上的自反關系．
中央電大2010年7月離散數學
試題解答
(供參考)
一、單項選擇題（每小題3分，本題共15分）
1．B2．D3．B4．C5．B
二、填空題（每小題3分，本題共15分）
6．假（或F，或0）
7．48．t-
19． <2, 1>
10．z，y
三、邏輯公式翻譯（每小題6分，本題共12分）
11．設P：今天上課，（2分）則命題公式為：P．（6分）
12．設 P：他去操場鍛煉，Q：他有時間，（2分）則命題公式為：P ?Q．（6分）
四、判斷說明題（每小題7分，本題共14分）
13．錯誤．（3分）因為A中元素2沒有B中元素與之對應，故f不是A到B的函數．（7分）
14．錯誤．（3分）不滿足“設G是一個有v個結點e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．”（7分）
五．計算題（每小題12分，本題共36分）
15．（P∨Q）→（R∨Q）? ┐(P∨Q)∨（R∨Q）（4分）
?(┐P∧┐Q)∨（R∨Q）（8分）
?(┐P∧┐Q)∨R∨Q（析取范式）（12分）
16．（1）（A∩B）={1}（4分）
（2）（A∪B）={1, 2, {1}, {2}}（8分）
（3）A?（A∩B）={{1}, 1, 2}（12分）
17．（1）G的圖形表示如圖一所示：ad1
5b c（3分）圖一
（2）鄰接矩陣：
?0?1?10111?1??（6分）??1101?
?1110??
（3）最小的生成樹如圖二中的粗線所示：
a 3d5
b圖二1c
權為：1+1+3=5
六、證明題（本題共8分）
18．證明：設?x?A，因為R自反，所以x R x，即< x, x>?R；
又因為S自反，所以x R x，即< x, x >?S．即< x, x>?R∩S故R∩S自反．
10分）12分）（4分）（6分）（8分）（（
第五篇：離散數學試題+答案
www.tmdps.cn 專注于收集各類歷年試卷和答案
一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內。1.一個連通的無向圖G，如果它的所有結點的度數都是偶數，那么它具有一條（）A.漢密爾頓回路
B.歐拉回路 C.漢密爾頓通路
D.初級回路
2.設G是連通簡單平面圖，G中有11個頂點5個面，則G中的邊是（）A.10
B.12
C.16
D.14 3.在布爾代數L中，表達式(a∧b)∨(a∧b∧c)∨(b∧c)的等價式是（）A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.設i是虛數，·是復數乘法運算，則G=<{1,-1,i,-i},·>是群，下列是G的子群是（）A.<{1},·>
B.〈{-1},·〉
C.〈{i},·〉
D.〈{-i},·〉
5.設Z為整數集，A為集合，A的冪集為P(A),+、-、/為數的加、減、除運算，∩為集合的交運算，下列系統中是代數系統的有（）A.〈Z，+，/〉
B.〈Z，/〉 C.〈Z，-，/〉
D.〈P(A)，∩〉 6.下列各代數系統中不含有零元素的是（）A.〈Q，*〉Q是全體有理數集，*是數的乘法運算
B.〈Mn(R),*〉,Mn(R)是全體n階實矩陣集合，*是矩陣乘法運算 C.〈Z，?〉，Z是整數集，?定義為x?xy=xy,?x,y∈Z D.〈Z，+〉，Z是整數集，+是數的加法運算
7.設A={1,2,3}，A上二元關系R的關系圖如下： R具有的性質是 A.自反性 B.對稱性 C.傳遞性 D.反自反性
8.設A={a,b,c}，A上二元關系R={〈a,a〉，〈b,b〉〈,a,c〉}，則關系R的對稱閉包S(R)是（）A.R∪IA
B.R
C.R∪{〈c,a〉}
D.R∩IA 9.設X={a,b,c},Ix是X上恒等關系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為X上的等價關系，R應取（）A.｛〈c,a〉，〈a,c〉｝
B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉}
D.{〈a,c〉，〈c,b〉} 10.下列式子正確的是（）A.?∈?
B.???
C.{?}??
D.{?}∈?
11.設解釋R如下：論域D為實數集，a=0,f(x,y)=x-y,A(x,y):x www.tmdps.cn 專注于收集各類歷年試卷和答案 D.(?x)(?y)(A(x,y)→A(f(x,a),a))12.設B是不含變元x的公式，謂詞公式(?x)(A(x)→B)等價于（）A.(?x)A(x)→B B.(?x)A(x)→B C.A(x)→B D.(?x)A(x)→(?x)B 13.謂詞公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中變元x（）A.是自由變元但不是約束變元 B.既不是自由變元又不是約束變元 C.既是自由變元又是約束變元 D.是約束變元但不是自由變元 14.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號化為（）A.P∨Q B.P∧┐Q C.P→┐Q D.P∨┐Q 15.以下命題公式中，為永假式的是（）A.p→(p∨q∨r) B.(p→┐p)→┐p C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p) 二、填空題(每空1分，共20分)16.在一棵根樹中，僅有一個結點的入度為______，稱為樹根，其余結點的入度均為______。17.A={1,2,3,4}上二元關系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的關系矩陣MR中m24=______,m34=______。18.設〈s,*〉是群，則那么s中除______外，不可能有別的冪等元；若〈s,*〉有零元，則|s|=______。19.設A為集合，P(A)為A的冪集，則〈P(A)，是格，若x,y∈P(A),則x,y最大下界是______，?〉最小上界是______。 20.設函數f:X→Y,如果對X中的任意兩個不同的x1和x2，它們的象y1和y2也不同，我們說f是______函數，如果ranf=Y，則稱f是______函數。 21.設R為非空集合A上的等價關系，其等價類記為〔x〕R。?x,y∈A，若〈x,y〉∈R，則 〔x〕R與〔y〕R的關系是______，而若〈x,y〉?R，則〔x〕R∩〔y〕R=______。 22.使公式(?x)(?y)(A(x)∧B(y))?(?x)A(x)∧(?y)B(y)成立的條件是______不含有y，______不含有x。23.設M(x):x是人，D(s):x是要死的，則命題“所有的人都是要死的”可符號化為(?x)______,其中量詞(?x)的轄域是______。24.若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是相容的，若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是不相容的。 25.判斷一個語句是否為命題，首先要看它是否為，然后再看它是否具有唯一的。 三、計算題(共30分)26.(4分)設有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長度為2的路的總數和回路總數。 27.(5)設A={a,b},P(A)是A的冪集，?是對稱差運算，可以驗證 是群。設n是正整數，求({a}-1{b}{a})n?{a}-n{b}n{a}n 28.(6分)設A={1,2,3,4,5},A上偏序關系 R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA; www.tmdps.cn 專注于收集各類歷年試卷和答案 (1)作出偏序關系R的哈斯圖 (2)令B={1,2,3,5}，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.(6分)求┐(P→Q)?(P→┐Q)的主合取范式并給出所有使命題為真的賦值。 30.(5分)設帶權無向圖G如下，求G的最小生成樹T及T的權總和，要求寫出解的過程。 31.(4分)求公式┐((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)的前束范式。 四、證明題(共20分)32.(6分)設T是非平凡的無向樹，T中度數最大的頂點有2個，它們的度數為k(k≥2),證明T中至少有2k-2片樹葉。 33.(8分)設A是非空集合，F是所有從A到A的雙射函數的集合，?是函數復合運算。 證明：〈F, ?〉是群。 34.(6分)在個體域D={a1,a2,?，an}中證明等價式： (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x) 五、應用題(共15分)35.(9分)如果他是計算機系本科生或者是計算機系研究生，那么他一定學過DELPHI語言而且學過C++語言。只要他學過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結論。 36.(6分)一次學術會議的理事會共有20個人參加，他們之間有的相互認識但有的相互不認識。但對任意兩個人，他們各自認識的人的數目之和不小于20。問能否把這20個人排在圓桌旁，使得任意一個人認識其旁邊的兩個人?根據是什么? 參考答案 一、單項選擇題(本大題共15小題，每小題1分，共15分) 1.B 2.D 3.A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C 二、填空題 16.0 17.1 0 18.單位元 19.x∩y x∪y 20.入射 滿射 21.［x］R=［y］R 22.A(x) B(y)23.(M(x)→D(x)) M(x)→D(x) www.tmdps.cn 專注于收集各類歷年試卷和答案 24.可滿足式 永假式(或矛盾式)25.陳述句 真值 三、計算題 ?1100??1010???26.M=?? 1011????0011???2?2?M=??2??1110?111??? 121?011??M2ij?18,ij?6 ?M2i?1??i?1j?144 G中長度為2的路總數為18，長度為2的回路總數為6。 27.當n是偶數時，?x∈P(A),xn=? 當n是奇數時，?x∈P(A),xn=x 于是：當n是偶數，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n =??(｛a｝-1)n｛b｝n｛a｝n=????? 當n是奇數時，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝?(｛a｝-1)n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝?｛a｝-1｛b｝｛a｝=? 28.(1)偏序關系R的哈斯圖為 (2)B的最大元：無，最小元：無； 極大元：2，5，極小元：1，3 下界：4，下確界4； 上界：無，上確界：無 29.原式?(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q)) ((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q)) (┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q)) (┐(P∧┐Q)∨(P∧┐Q)) (P∧Q)∨(P∧┐Q) P∧(Q∨┐Q) P∨(Q∧┐Q) (P∨Q)∧(P∨┐Q) 命題為真的賦值是P=1,Q=0和P=1,Q=1 www.tmdps.cn 專注于收集各類歷年試卷和答案 30.令e1=(v1,v3)，e2=(v4,v6) e3=(v2,v5)，e4=(v3,v6) e5=(v2,v3)，e6=(v1,v2) e7=(v1,v4)，e8=(v4,v3) e9=(v3,v5)，e10=(v5,v6) 令ai為ei上的權，則 a1 取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權和=1+2+3+4+5=15 31.原式?┐(?x1F(x1,y)→?y1G(x,y1))∨?x2H(x2) (換名) ?┐?x1?y1(F(x1,y)→G(x,y1))∨?x2H(x2) ??x1?y1┐(F(x1,y1)→G(x,y1))∨?x2H(x2) ??x1?y1?x2(┐(F(x1,y1)→G(x,y1))∨H(x2) 四、證明題 32.設T中有x片樹葉，y個分支點。于是T中有x+y個頂點，有x+y-1 條邊，由握手定理知T中所有頂點的度數之的 x?y ?d(vi)=2(x+y-1)。 i?又樹葉的度為1，任一分支點的度大于等于2 且度最大的頂點必是分支點，于是 x?y ?d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i?1 從而2(x+y-1)≥x+2y+2k-4 x≥2k-2 33.從定義出發證明：由于集合A是非空的，故顯然從A到A的雙射函數總是存在的，如A上恒等函數，因此F非空 (1)?f,g∈F,因為f和g都是A到A的雙射函數，故f?g也是A到A的雙射函數，從而集合F關于運算?是封閉的。 (2)?f,g,h∈F,由函數復合運算的結合律有f?(g?h)=(f?g)?h故運算?是可結合的。 (3)A上的恒等函數IA也是A到A的雙射函數即IA∈F,且?f∈F有IA?f=f?IA=f,故IA是〈F，?〉中的幺元 (4)?f∈F,因為f是雙射函數，故其逆函數是存在的，也是A到A的雙射函數，且有f?f-1=f-1?f=IA,因此f-1是f的逆元 由此上知〈F，?〉是群 34.證明(?x)(A(x)→B(x))? ?x(┐A(x)∨B(x)) www.tmdps.cn 專注于收集各類歷年試卷和答案 ?(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨?∨(┐A(an)∨B(an))) ?(┐A(a1)∨A(a2)∨?∨┐A(an)∨(B(a1)∨B(a2)∨?∨(B(an)) ?┐(A(a1)∧A(a2)∧?∧A(an))∨(┐B(a1)∨B(a2)∨?∨(B(an)) ?┐(?x)A(x)∨(?x)B(x)?(?x)A(x)→(?x)B(x) 五、應用題 35.令p：他是計算機系本科生 q：他是計算機系研究生 r：他學過DELPHI語言 s:他學過C++語言 t:他會編程序 前提：(p∨q)→(r∧s),(r∨s)→t 結論：p→t 證①p P(附加前提) ②p∨q T①I ③(p∨q)→(r∧s) P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r∨s T⑤I ⑦(r∨s)→t P(前提引入) ⑧t T⑤⑥I 36.可以把這20個人排在圓桌旁，使得任一人認識其旁邊的兩個人。 根據：構造無向簡單圖G= ?Vi∈V,d(vi)是與vi相互認識的人的數目，由題意知?vi,vj∈V有d(vi)+d(vj)?20,于是G中存在漢密爾頓回路。 設C=Vi1Vi2?Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。
點擊咨詢 