第一篇：2009年4月離散數學試題(附答案)
全國2009年4月自學考試離散數學試題（附答案）
課程代碼：02324
一、單項選擇題（本大題共15小題，每小題1分，共15分）
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。/S 1．下列為兩個命題變元P，Q的小項是（）A．P∧Q∧? P B．? P∨Q C．? P∧Q
D．? P∨P∨Q 2．下列語句中是真命題的是（）A．我正在說謊
B．嚴禁吸煙
C．如果1+2=3，那么雪是黑的
D．如果1+2=5，那么雪是黑的 3．設P：我們劃船，Q：我們跑步。命題“我們不能既劃船又跑步”符號化為（）A．? P∧? Q B．? P∨? Q C．?（P?Q）
D．?（? P∨? Q）
4．命題公式（P∧（P→Q））→Q是（）A．矛盾式 B．蘊含式 C．重言式
D．等價式
5．命題公式?（P∧Q）→R的成真指派是（）A．000，001，110，B．001，011，101，110，111 C．全體指派
D．無
6．在公式（?x）F（x，y）→（? y）G（x，y）中變元x是（）A．自由變元
B．約束變元
C．既是自由變元，又是約束變元
D．既不是自由變元，又不是約束變元
7．集合A={1，2，?，10}上的關系R={
C．傳遞的、對稱的
D．反自反的、傳遞的
8．若R和S是集合A上的兩個關系，則下述結論正確的是（）A．若R和S是自反的，則R∩S是自反的 B．若R和S是對稱的，則R?S是對稱的 C．若R和S是反對稱的，則R?S是反對稱的 D．若R和S是傳遞的，則R∪S是傳遞的
全國2009年4月自學考試離散數學試題）
9．R={<1，4>，<2，3>，<3，1>，<4，3>}，則下列不是．．t（R）中元素的是（）A．<1，1> C．<1，3>
B．<1，2> D．<1，4> 10．設A={{1，2，3}，{4，5}，{6，7，8}}，下列選項正確的是（）A．1∈A C．{{4，5}}?A
B．{1，2，3}?A D．?∈A 11．在自然數集N上，下列運算是可結合的是（）A．a?b=a-2b C．a?b=-a-b
B．a?b=min{a，b} D．a?b=|a-b| 12．在代數系統中，整環和域的關系是（）A．整環一定是域 C．域一定是整環
B．域不一定是整環 D．域一定不是整環
13．下列所示的哈斯圖所對應的偏序集中能構成格的是（）
A． B．
C． D．
14．設G為有n個結點的簡單圖，則有（）A．Δ(G)＜n C．Δ(G)＞n
B．Δ(G)≤n D．Δ(G)≥n
15．具有4個結點的非同構的無向樹的數目是（）A．2 C．4
二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。
B．3 D．5 16．（?x）（?y）（P（x，y）Q（y，z））∧?xP（x，y）中?x的轄域為________，?x的轄域為________。17．兩個重言式的析取是________式，一個重言式與一個矛盾式的析取是________式。
18．設N是自然數集合，f和g是N到N的函數，且f（n）=2n+1，g（n）=n，那么復合函數（f?f）（n）
全國2009年4月自學考試離散數學試題
2=________（g?f）（n）=________。
19．設復合函數g?f是從A到C的函數，如果g?f是滿射，那么________必是滿射，如果g?f是入射，那么________必是入射。
20．設A={1，2}，B={2，3}，則A-A=________，A-B=________。
21．設S是非空有限集，代數系統
中，其中P（S）為集合S的冪集，則P（S）對∪運算的單位元是________，零元是________。
+>中，2的階是________。22．在
?0125．設圖D=
三、計算題（本大題共5小題，第26、27小題各5分，第28、29小題各6分，第30小題8分，共30分）
+B，A的冪集P（A）26．已知A={{?}，{?，1}}，B={{?，1}，{1}}，計算A∪B，A○。
27．構造命題公式（（P∧Q）→P）∨R的真值表。
28．下圖給出了一個有向圖。（1）求出它的鄰接矩陣A；（2）求出A2，A3，A4及可達矩陣P。
29．求下列公式的主合取范式和主析取范式：P∨（? P→（Q∨（? Q→R）））
30．設A={1，2，3，4，6，8，12，24}，R為A上的整除關系，試畫
四、證明題（本大題共3小題，第31、32小題各6分，第33小題8分，共20分）31．在整數集Z上定義：a?b?a?b?2,?a,b?Z，證明：
全國2009年4月自學考試離散數學試題
33．證明：邊e是圖G的一條割邊，當且僅當圖G中不存在包含邊e的簡單回路。
五、應用題（本大題共2小題，第34小題6分，第35小題9分，共15分）34．構造下面推理的證明。
如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當小趙去看電影時，小李也去。
35．今有n個人，已知他們中任何2人的朋友合起來一定包含其余n-2人。試證明：
（1）當n≥3時，這n個人能排成一列，使得中間任何人是其兩旁的人的朋友，而兩頭的人是其左邊（或右邊）的人的朋友。
（2）當n≥4時，這n個人能排成一圓圈，使得每個人是其兩旁的人的朋友。
全國2009年4月自學考試離散數學試題
第二篇：離散數學試題+答案
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中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。 《離散數學》試題及答案 一、選擇題：本題共5小題，每小題3分，共15分，在每小題給出的四個選項中，只有一項是符合題目要求的。 1.命題公式(P?Q)?Q為() (A)矛盾式(B)可滿足式(C)重言式(D)合取范式 2．設P表示“天下大雨”，Q表示“他在室內運動”，則命題“除非天下大雨，否則他不在室內運動”符號化為（）。 (A)． P?Q；(B)．P?Q；(C)．?P??Q；(D)．?P?Q． 3.設集合A={{1,2,3}, {4,5}, {6,7,8}}，則下式為真的是() (A)1?A(B){1,2, 3}?A (C){{4,5}}?A(D)??A 4.設A＝{1,2},B={a,b,c},C={c,d}, 則A×(B?C)=() (A){<1,c>,<2,c>}(B){ 5.設G如右圖：那么G不是().(A)哈密頓圖；(B)完全圖； (C)歐拉圖；(D)平面圖.二、填空題：本大題共5小題，每小題4分，共20 6.設集合A={?,{a}}，則A的冪集P(A7.設集合A={1,2,3,4 }, B={6,8,12}, A到B的關系R＝{?x,y?y?2x,x?A,y?B},那么R1＝－ 8.在“同學，老鄉，親戚，朋友”四個關系中_______是等價關系.9.寫出一個不含“?”的邏輯聯結詞的完備集.10.設X＝{a,b,c}，R是X上的二元關系，其關系矩陣為 ?101??，那么R的關系圖為 MR＝?100????100?? 三、證明題（共30分） 11.（10分）已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C) 12.（10分）構造證明：(P?(Q?S))∧(?R∨P)∧Q?R?S （0,1）13.（10分）證明與[0,1)，[0,1)與[0,1]等勢。 四、解答題(共35分) 14.（7分）構造三階幻方（以1為首項的9個連續自然數正好布滿一個3?3方陣，且方陣中的每一行, 每一列及主、副對角線上的各數之和都相等.） 15.（8分）求命題公式(P?Q)?(?P??Q)的真值表.16.（10分）設R1是A1＝{1,2}到A2＝(a,b,c)的二元關系，R2是A2到A3＝{?,?}的二元關系，R1= {<1,a>,<1,b>,<2,c>}, R2={ 畢節學院《離散數學 》課程試卷 求R1?R2的集合表達式.17.（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？ 三個條件：(1)若A去，則C和D中要去1個人；(2)B和C不能都去； (3)若C去，則D留下。 一、單項選擇題(每小題3分，共15分) 1.B2.C3.C4.A5.B 二、填空題(每小題4分，共20分) 6.{?,{?},{{a}},{?,{a}}} 7.{<6,3>,<8,4> }8.老鄉 9.{?,?}或{?,?} 或 {?}或 {?} 10.見 f(0)?0??111?························································································ 10分 ,n?1,?A ·?f()?n?1n?n ??f(x)?x,x?[0,1)?A 14.85 1 2 7 6 填對每個格得1分。 15.表中最后一列的數中，每對1個數得2分.?110?16.MR1???,(2分)001?? MR2?01??(4分)??01????00?? ?01??01???01?(6分)???00?????00???110? MR1?R2????001? R1?R2?{?1,??}(10分) 17.解設A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據題意應有：A?C?D，?(B∧C)，C??D必須同時成立。······························································································ 2分 因此(A?C?D)∧?(B∧C)∧(C??D) ?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D) ?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D)) ?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D) ∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D) ∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D) ?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D) ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D) ?T ··································································································································· 8分 畢節學院《離散數學 》課程試卷 故有三種派法：B∧D，A∧C，A∧D。······································································· 10分 畢節學院《離散數學 》課程試卷 中央電大離散數學試題 月 一、單項選擇題（每小題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分）（（ 全國2008年4月自考離散數學試題 課程代碼：02324 一、單項選擇題(本大題共15小題，每小題1分，共15分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。 1.設P：天下大雨,Q：他在室內運動,命題“除非天下大雨，否則他不在室內運動”可符合化為（） A.?P∧QB.?P→Q C.?P→?QD.P→?Q 2.下列命題聯結詞集合中，是最小聯結詞組的是（） A.{?，}B.{?，∨，∧} C.{?，∧}D.{∧，→} 3.下列命題為假命題的是（） A.如果2是偶數，那么一個公式的析取范式惟一 B.如果2是偶數，那么一個公式的析取范式不惟一 C.如果2是奇數，那么一個公式的析取范式惟一 D.如果2是奇數，那么一個公式的析取范式不惟一 4.謂詞公式 x(P(x)∨yR(y))→Q(x))中變元x是（） A.自由變元B.約束變元 C.既不是自由變元也不是約束變元D.既是自由變元也是約束變元 5.若個體域為整數減，下列公式中值為真的是（） A.xy(x+y=0)B.y x(x+y=0)C.x y(x+y=0)D.?xy(x+y=0) 6.下列命題中不正確的是（） A.x∈{x}-{{x}}B.{x}?{x}-{{x}} C.A={x}∪x,則x∈A且x?AD.A-B=??A=B 7.設P={x|(x+1)2≤4}，Q={x|x2+16≥5x},則下列選項正確的是（A.P?QB.P?Q C.Q?PD.Q=P 8.下列表達式中不成立的是（） A.A∪(B?C)=(A∪B)?(A∪C)B.A∩(B?C)=(A∩B)?(A∩C)C.(A?B)×C=(A×C)?(B×C)D.(A-B)×C=(A×C)-(B×C)9.半群、群及獨異點的關系是（） A.{群}?{獨異點}?{半群}B.{獨異點}?{半群}?{群} C.{獨異點}?{群}?{半群}D.{半群}?{群}?{獨異點} 10.下列集合對所給的二元運算封閉的是（） A.正整數集上的減法運算 B.在正實數的集R+上規定為ab=ab-a-b a,b∈R+ C.正整數集Z+上的二元運算為xy=min(x,y)x,y∈Z+ D.全體n×n實可逆矩陣集合Rn×n上的矩陣加法 11.設集合A={1，2，3}，下列關系R中不是等價關系的是（）A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}） C.R={<1,1>,<2,2>,<3,3>,<1,2>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 12.下列函數中為雙射的是（） A.f：Z→Z,f(j)=j(mod)B.f：N→N,f(j)= C.f：Z→N,f(j)=|2j|+1D.f：R→R,f(r)=2r-15 13.設集合A={a,b, c}上的關系如下，具有傳遞性的是（） A.R={ 14.含有5個結點，3條邊的不同構的簡單圖有（） A.2個B.3個 C.4個D.5個 15.設D的結點數大于1，D= A.D中至少有一條通路B.D中至少有一條回路 C.D中有通過每個結點至少一次的通路D.D中有通過每個結點至少一次的回路 二、填空題(本大題共10小題，每小題2分，共20分)請在每小題的空格中填上正確答案。錯填、不填均無分。 16.設A={1,2,3}，B={3,4,5}，則A?A=___________，A?B=___________。 17.設A={1,2,3,4,5}，R?A×A，R={<1,2>，<3,4>,<2,2>}，則R的自反閉包r(R)=__________。 對稱閉包t(R)=__________。 18.設P、Q為兩個命題，德摩根律可表示為_____________，吸收律可表示為____________。 19.對于公式 x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,當論域為{1,2}時，其真值為_____________ ,當論域為{0,1,2}時，其真值為_____________。 20.設f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,則復合函數 ,。 21.3個結點可構成_________個不同構的簡單無向圖，可構成________個不同構的簡單有向圖。 22.無向圖G= Δ(G)=_____________，G的最小度δ(G)=_____________。 23.設圖G 24.格L是分配格，當且僅當L既不含有與_______同構的子格，也不含有與______同格的子格。 25.給定集合A={1,2,3,4,5}，在集合A上定義兩種關系：R={<1,2>,<3,4>,<2,2>}, S={<4,2>,<2,5>,<3,1>,<1,3>}，則。 三、計算題（本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分） 26.設A={a,b,c,d}，A上的等價關系R={ 27.構造命題公式?（P∨Q）（?P∧Q）的真值表。 28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（?P∧Q）） 29.設A={a, b, c, d, e}，R為A上的關系，R={ 30.給定圖G如圖所示，（1）G中長度為4的路有幾條？其中有幾條回路？（2）寫出G的可達矩陣。 四、證明題（本大題共3小題，第31、32題各6分，第33題8分，共20分） 31.設（L，≤）是格，試證明： a, b, c ∈L, 有a∧（b∨c）≥（a∧b）∨（a∧c）； a∨（b∧c）≤（a∨b）∧（a∨c）。 32.設R是A上的自反和傳遞關系，如下定義A上的關系T，使得 x, y∈A， 證明T是A上的等價關系。 33.設有G= 五、應用題（本大題共2小題，第34題7分，第35題8分，共15分） 34.構造下面推理的證明。 每個喜歡步行的人都不喜歡坐汽車，每個人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。 35.今要將6人分成3組（每組2個人）去完成3項任務。已知每個人至少與其余5個人中的3個人能相互合作。 （1）能否使得每組的2個人都能相互合作？ （2）你能給出幾種不同的分組方案？ 《離散數學》試題及答案3 一、填空題設集合A,B，其中A＝{1,2,3}, B= {1,2}, 則A?(B)＝ __________________________.2.設有限集合A, |A| = n, 則 |?(A×A)| = __________________________.3.設集合A = {a, b}, B = {1, 2}, 則從A到B的所有映射是__________________________ _____________, 其中雙射的是__________________________.4.已知命題公式G＝?(P?Q)∧R，則G的主析取范式是_______________________________ __________________________________________________________.5.設G是完全二叉樹，G有7個點，其中4個葉點，則G的總度數為__________，分枝點數為________________.6 設A、B為兩個集合, A= {1,2,4}, B = {3,4}, 則從A?B＝_________________________;A?B＝_________________________;A－B＝ _____________________.7.設R是集合A上的等價關系，則R所具有的關系的三個特性是______________________, ________________________, _______________________________.8.設命題公式G＝?(P?(Q?R))，則使公式G為真的解釋有__________________________，_____________________________, __________________________.9.設集合A＝{1,2,3,4}, A上的關系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 則R1?R2 = ________________________,R2?R1 =____________________________,R12 =________________________.10.設有限集A, B，|A| = m, |B| = n, 則| |?(A?B)| = _____________________________.11 設A,B,R是三個集合，其中R是實數集，A = {x |-1≤x≤1, x?R}, B = {x | 0≤x < 2, x?R},則A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ ,.13.設集合A＝{2, 3, 4, 5, 6}，R是A上的整除，則R以集合形式(列舉法)記為___________ _______________________________________________________.14.設一階邏輯公式G = xP(x)?xQ(x)，則G的前束范式是__________________________ _____.15.設G是具有8個頂點的樹，則G中增加_________條邊才能把G變成完全圖。 16.設謂詞的定義域為{a, b},將表達式xR(x)→xS(x)中量詞消除，寫成與之對應的命題公式是__________________________________________________________________________.17.設集合A＝{1, 2, 3, 4}，A上的二元關系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。則R?S＝_____________________________________________________, R2＝______________________________________________________.二、選擇題 設集合A={2,{a},3,4}，B = {{a},3,4,1}，E為全集，則下列命題正確的是()。 (A){2}?A(B){a}?A(C)??{{a}}?B?E(D){{a},1,3,4}?B.設集合A={1,2,3},A上的關系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，則R不具備().(A)自反性(B)傳遞性(C)對稱性(D)反對稱性 設半序集(A,≤)關系≤的哈斯圖如下所示，若A的子集B = {2,3,4,5},則元素6為B的()。 (A)下界(B)上界(C)最小上界(D)以上答案都不對下列語句中，()是命題。 (A)請把門關上(B)地球外的星球上也有人 (C)x + 5 > 6(D)下午有會嗎？ 設I是如下一個解釋：D＝{a,b}, 則在解釋I下取真值為1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供選擇答案中的數值表示一個簡單圖中各個頂點的度，能畫出圖的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.設G、H是一階邏輯公式，P是一個謂詞，G＝xP(x), H＝xP(x),則一階邏輯公式G?H是().(A)恒真的(B)恒假的(C)可滿足的(D)前束范式.設命題公式G＝?(P?Q)，H＝P?(Q??P)，則G與H的關系是()。 (A)G?H(B)H?G(C)G＝H(D)以上都不是.9 設A, B為集合，當()時A－B＝B.(A)A＝B(B)A?B(C)B?A(D)A＝B＝?.設集合A = {1,2,3,4}, A上的關系R＝{(1,1),(2,3),(2,4),(3,4)}, 則R具有()。 (A)自反性(B)傳遞性(C)對稱性(D)以上答案都不對下列關于集合的表示中正確的為()。 (A){a}?{a,b,c}(B){a}?{a,b,c}(C)??{a,b,c}(D){a,b}?{a,b,c} 12 命題xG(x)取真值1的充分必要條件是().(A)對任意x，G(x)都取真值1.(B)有一個x0，使G(x0)取真值1.(C)有某些x，使G(x0)取真值1.(D)以上答案都不對.13.設G是連通平面圖，有5個頂點，6個面，則G的邊數是().(A)9條(B)5條(C)6條(D)11條.14.設G是5個頂點的完全圖，則從G中刪去()條邊可以得到樹.(A)6(B)5(C)10(D)4.15.設圖G的相鄰矩陣為，則G的頂點數與邊數分別為().(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、計算證明題 1.設集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R為整除關系。 (1)畫出半序集(A,R)的哈斯圖； (2)寫出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界； (3)寫出A的最大元，最小元，極大元，極小元。 2.設集合A＝{1, 2, 3, 4}，A上的關系R＝{(x,y)| x, y?A 且 x ? y}, 求 (1)畫出R的關系圖； (2)寫出R的關系矩陣.3.設R是實數集合，?,?,?是R上的三個映射，?(x)= x+3, ?(x)= 2x, ?(x)＝ x/4,試求復合映射???，???, ???, ???，?????.4.設I是如下一個解釋：D = {2, 3}, abf(2)f(3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011 試求(1)P(a, f(a))∧P(b, f(b));(2)xy P(y, x).5.設集合A＝{1, 2, 4, 6, 8, 12}，R為A上整除關系。 (1)畫出半序集(A,R)的哈斯圖； (2)寫出A的最大元，最小元，極大元，極小元； (3)寫出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.6.設命題公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。 7.(9分)設一階邏輯公式：G =(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.設R是集合A = {a, b, c, d}.R是A上的二元關系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)； (2)畫出r(R), s(R), t(R)的關系圖.11.通過求主析取范式判斷下列命題公式是否等價： (1)G =(P∧Q)∨(?P∧Q∧R) (2)H =(P∨(Q∧R))∧(Q∨(?P∧R)) 13.設R和S是集合A＝{a, b, c, d}上的關系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.(1)試寫出R和S的關系矩陣； (2)計算R?S, R∪S, R－1, S－1?R－1.四、證明題 1.利用形式演繹法證明：{P→Q, R→S, P∨R}蘊涵Q∨S。 2.設A,B為任意集合，證明：(A-B)-C = A-(B∪C).3.(本題10分)利用形式演繹法證明：{?A∨B, ?C→?B, C→D}蘊涵A→D。 4.(本題10分)A, B為兩個任意集合，求證： A－(A∩B)=(A∪B)－B.參考答案 一、填空題 1.{3};{{3},{1,3},{2,3},{1,2,3}}.2..3.?1= {(a,1),(b,1)}, ?2= {(a,2),(b,2)},?3= {(a,1),(b,2)}, ?4= {(a,2),(b,1)};?3, ?4.4.(P∧?Q∧R).5.12, 3.6.{4}, {1, 2, 3, 4}, {1, 2}.7.自反性；對稱性；傳遞性.8.(1, 0, 0),(1, 0, 1),(1, 1, 0).9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2m?n.11.{x |-1≤x < 0, x?R};{x | 1 < x < 2, x?R};{x | 0≤x≤1, x?12.12;6.13.{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}.14.x(?P(x)∨Q(x)).15.21.16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(1, 3),(2, 2)};{(1, 1),(1, 2),(1, 3)}.二、選擇題 1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.15.D 三、計算證明題 1.(1) (2)B無上界，也無最小上界。下界1, 3;最大下界是3.(3)A無最大元，最小元是1，極大元8, 12, 90+;極小元是1.2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1) (2) 3.(1)???＝?(?(x))＝?(x)+3＝2x+3＝2x+3.(2)???＝?(?(x))＝?(x)+3＝(x+3)+3＝x+6,(3)???＝?(?(x))＝?(x)+3＝x/4+3,(4)???＝?(?(x))＝?(x)/4＝2x/4 = x/2，(5)?????＝??(???)＝???+3＝2x/4+3＝x/2+3.4.(1)P(a, f(a))∧P(b, f(b))= P(3, f(3))∧P(2, f(2))= P(3, 2)∧P(2, 3)= 1∧0 = 0.(2)xy P(y, x)= x(P(2, x)∨P(3, x)) R}.6 =(P(2, 2)∨P(3, 2))∧(P(2, 3)∨P(3, 3))=(0∨1)∧(0∨1)= 1∧1 = 1.5.(1) (2)無最大元，最小元1，極大元8, 12;極小元是1.(3)B無上界，無最小上界。下界1, 2;最大下界2.6.G = ?(P→Q)∨(Q∧(?P→R))= ?(?P∨Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧P)∨(Q∧R) =(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(?=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = ?(3, 4, 5, 6, 7).7.G =(xP(x)∨yQ(y))→xR(x)= ?(xP(x)∨yQ(y))∨xR(x)=(?xP(x)∧?yQ(y))∨xR(x)=(x?P(x)∧y?Q(y))∨zR(z)= xyz((?P(x)∧?Q(y))∨R(z)) 9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}，t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}； (2)關系圖: 11.G＝(P∧Q)∨(?P∧Q∧R) ＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)＝m6∨m7∨m3 ＝?(3, 6, 7) H =(P∨(Q∧R))∧(Q∨(?P∧R))＝(P∧Q)∨(Q∧R))∨(?P∧Q∧R) ＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)∨(P∧Q∧R)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝?(3, 6, 7) G,H的主析取范式相同，所以G = H.13.(1) P∧Q∧R)7 (2)R?S＝{(a, b),(c, d)}，R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－1＝{(a, a),(c, a),(c, b),(d, c)}, S－1?R－1＝{(b, a),(d, c)}.四 證明題 1.證明：{P→Q, R→S, P∨R}蘊涵Q∨S(1)P∨RP (2)?R→PQ(1)(3)P→QP (4)?R→QQ(2)(3)(5)?Q→RQ(4)(6)R→SP (7)?Q→SQ(5)(6)(8)Q∨SQ(7) 2.證明：(A-B)-C =(A∩~B)∩~C = A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C) 3.證明：{?A∨B, ?C→?B, C→D}蘊涵A→D(1)AD(附加)(2)?A∨BP(3)BQ(1)(2)(4)?C→?BP(5)B→CQ(4)(6)CQ(3)(5)(7)C→DP(8)DQ(6)(7)(9)A→DD(1)(8) 所以 {?A∨B, ?C→?B, C→D}蘊涵A→D.4.證明：A－(A∩B)= A∩~(A∩B)＝A∩(~A∪~B) ＝(A∩~A)∪(A∩~B)＝?∪(A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪? = A－B 所以：A－(A∩B)=(A∪B)－B.8 1.離散數學試題及答案2 離散數學試題 一.多重選擇填空題 (本題包括16個空格，每個空格3分，共48分。每道小題都可能有一個以上的正確選項，須選出所有的正確選項，不答不得分，多選、少選或選錯都將按比例扣分。)1．命題公式(P∧(P→Q))→Q是_____式。 (1)重言(2)矛盾(3)可滿足(4)非永真的可滿足 2．給定解釋I=(D,)=(整數集，{f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):x (1)100(2)99(3)2048(4)1024(5)512 4．集合Ａ={x|x是整數，<30}，Ｂ={x|x是質數，x<20}，C={1,3,5}，則① =_____;② =_____;③ =_____;④ =_____。(1){1,2,3,5}(2)(3){0}(4){1,3,5,7,11,13,17,19}(5){1,3,5,7}(6){7,11,13,17,19} 5．設A、B、C是集合，下列四個命題中，_____在任何情況下都是正確的。(1)若A B且B∈C，則A∈C(2)若A B且B∈C，則A C(3)若A∈B且B C，則A C(4)若A∈B且B C，則A∈C 6．設集合Ａ={a,b,c,d,e,f,g}，Ａ的一個劃分 ={{a,b},{c,d,e},{f,g}}，則 所對應的等價關系有_____個二元組。 (1)14(2)15(3)16(4)17(5)8(6)49(7)512 7．S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除關系。S的子集Ｂ＝{2,4,6｝，則在(S，≤)中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上確界是_____；Ｂ的下確界是_____。 (1)不存在的(2)36(3)24(4)12(5)6(6)1(7)2 8．設有有限布爾代數(B,+,*,’,0,1)，則 =_____能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)9 9．G={0,1,2,?,n}，n∈N，定義 為模n加法，即x y=(x+y)mod n，則代數系統(G，)_____。 (1)是半群但不是群(2)是無限群(3)是循環群(4)是變換群(5)是交換群 10．n個結點、m條邊的無向連通圖是樹當且僅當m=_____。(1)n+1(2)n(3)n-1(4)2n-1 二請給出命題公式 的主析取范式。(10分)三假設下列陳述都是正確的：(1)學生會的每個成員都是學生并且是班干部； (2)有些成員是女生。問是否有成員是女班干部？請將上述陳述和你的結論符號化，并給出你的結論的形式證明。(10分)四設R和S是集合Ｘ上的等價關系,則S∩R必是等價關系。(10分) 參考答案 一、1.1、3 2.4 3.4 4.1；4；2；2 5.4 6.4 7.1；7；4；7 8.2、4、6 9.3、4 10.3 二、分析：求給定命題公式的主析取范式與主合取范式，通常有兩種方法——列表法和等值演算法。(1)列表法 列出給定公式的真值表，其真值為真的賦值所對應的極小項的析取，即為此公式的主析取范式。(2)等值演算法 在等值演算中，首先將公式中的蘊涵聯結詞和等價聯結詞化去，使整個公式化歸為析取范式，然后刪去其中所有的永假合取項，再將析取式中重復出現的合取項合并和合并合取項中相同的命題變元，最后對合取項添加沒有出現的命題變元，就是合取 ,經過化簡整理，即可得到主析取范式。解：（1）列表法 設 000011111 001010100 010010100 011110100 100001000 101000010 110000010 111100111 根據真值表中 真值為1的賦值所對應的極小項的析取，即為 的主析取范式。由表可知 （2）等值演算 三、解：有成員是女班干部。 將命題符號化，個體域為全總個體域。 ：x是學生會的成員。：x是學生 ：x是班干部 ：x是女性 前提：，結論： 證明： ① P ② ES①，e為額外變元 ③ P ④ T③ ⑤ T② ⑥ T② ⑦ T④⑤⑥ ⑧ T② ⑨ T⑤⑦⑧ ⑩ EG⑨ 離散數學試題及答案1 離散數學考試試題（A卷及答案） 一、（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？ (1)若A去，則C和D中要去1個人； (2)B和C不能都去； (3)若C去，則D留下。 解 設A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據題意應有：A?C?D，?(B∧C)，C??D必須同時成立。因此 (A?C?D)∧?(B∧C)∧(C??D) ?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D) ?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D) ∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D) ∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D) ?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)?T 故有三種派法：B∧D，A∧C，A∧D。 二、（15分）在謂詞邏輯中構造下面推理的證明：某學術會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。 解：論域：所有人的集合。()： 是專家；()： 是工人；()： 是青年人；則推理化形式為： (()∧())，()(()∧())下面給出證明： (1)()P (2)(c)T(1)，ES(3)(()∧())P (4)(c)∧(c)T(3)，US(5)(c)T(4)，I (6)(c)∧(c)T(2)(5)，I 11(7)(()∧())T(6)，EG 三、（10分）設A、B和C是三個集合，則A?B??(B?A)。 證明：A?B?x(x∈A→x∈B)∧x(x∈B∧x?A)?x(x?A∨x∈B)∧x(x∈B∧x?A)??x(x∈A∧x?B)∧?x(x?B∨x∈A)??x(x∈A∧x?B)∨?x(x∈A∨x?B)??(x(x∈A∧x?B)∧x(x∈A∨x?B))??(x(x∈A∧x?B)∧x(x∈B→x∈A))??(B?A)。 四、（15分）設A＝{1，2，3，4，5}，R是A上的二元關系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝ Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。 五、（10分）R是非空集合A上的二元關系，若R是對稱的，則r(R)和t(R)是對稱的。 證明 對任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對稱的。 下證對任意正整數n，Rn對稱。 因R對稱，則有xR2y?z(xRz∧zRy)?z(zRx∧yRz)?yR2x，所以R2對稱。若 對稱，則x y?z(x z∧zRy)?z(z x∧yRz)?y x，所以 對稱。因此，對任意正整數n，對稱。 對任意的x、y∈A，若xt(R)y，則存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是對稱的。 六、（10分）若f：A→B是雙射，則f－1：B→A是雙射。 證明 因為f：A→B是雙射，則f－1是B到A的函數。下證f－1是雙射。 對任意x∈A，必存在y∈B使f(x)＝y，從而f－1(y)＝x，所以f－1是滿射。 對任意的y1、y2∈B，若f－1(y1)＝f－1(y2)＝x，則f(x)＝y1，f(x)＝y2。因為f：A→B是函數，則y1＝y2。所以f－1是單射。 綜上可得，f－1：B→A是雙射。 七、（10分）設 證明 因為 因為S是有限集，所以必存在j＞i，使得 ＝。令p＝j－i，則 ＝ *。所以對q≥i，有 ＝ *。 因為p≥1，所以總可找到k≥1，使得kp≥i。對于 ∈S，有 ＝ * ＝ *(*)＝?＝ *。 令a＝，則a∈S且a*a＝a。 八、（20分）（1）若G是連通的平面圖，且G的每個面的次數至少為l(l≥3)，則G的邊數m與結點數n有如下關系： m≤(n－2)。 證明 設G有r個面，則2m＝ ≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤(n－2)。 （2）設平面圖G＝ 證明 設G*＝ 離散數學考試試題（B卷及答案） 一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R 證明 因為S∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。 (1)?R 附加前提 (2)P?R P (3)?P T(1)(2)，I(4)P∨Q P (5)Q T(3)(4)，I(6)Q?S P(7)S T(5)(6)，I(8)?R?S CP(9)S∨R T(8)，E 二、（15分）根據推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。 設P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個體域：人的集合，則命題可符號化為：x(P(x)?(A(x)∨B(x)))，x(A(x)?Q(x))，?x(P(x)?Q(x))x(P(x)∧B(x))。 (1)?x(P(x)?Q(x))P (2)?x(?P(x)∨Q(x))T(1)，E(3)x(P(x)∧?Q(x))T(2)，E(4)P(a)∧?Q(a)T(3)，ES(5)P(a)T(4)，I(6)?Q(a)T(4)，I (7)x(P(x)?(A(x)∨B(x))P (8)P(a)?(A(a)∨B(a))T(7)，US(9)A(a)∨B(a)T(8)(5)，I(10)x(A(x)?Q(x))P (11)A(a)?Q(a)T(10)，US(12)?A(a)T(11)(6)，I(13)B(a)T(12)(9)，I (14)P(a)∧B(a)T(5)(13)，I(15)x(P(x)∧B(x))T(14)，EG 三、（10分）某班有25名學生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網球，還有2人會打這三種球。而6個會打網球的人都會打另外一種球，求不會打這三種球的人數。 解 設A、B、C分別表示會打排球、網球和籃球的學生集合。則： |A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。 因為|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不會 13 打這三種球的共5人。 四、（10分）設A1、A2和A3是全集U的子集，則形如 Ai?(Ai?為Ai或)的集合稱為由A1、A2和A3產生的小項。試證由A1、A2和A3所產生的所有非空小項的集合構成全集U的一個劃分。 證明 小項共8個，設有r個非空小項s1、s2、?、sr(r≤8)。 對任意的a∈U，則a∈Ai或a∈，兩者必有一個成立，取Ai?為包含元素a的Ai或，則a∈ Ai?，即有a∈ si，于是U? si。又顯然有 si?U，所以U＝ si。 任取兩個非空小項sp和sq，若sp≠sq，則必存在某個Ai和 分別出現在sp和sq中，于是sp∩sq＝?。 綜上可知，{s1，s2，?，sr}是U的一個劃分。 五、（15分）設R是A上的二元關系，則：R是傳遞的?R*R?R。 證明(5)若R是傳遞的，則 反之，若R*R?R，則對任意的x、y、z∈A，如果xRz且zRy，則 六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結點數、邊數和面數。 證明 對G的邊數m作歸納法。 當m＝0時，由于G是連通圖，所以G為平凡圖，此時n＝1，r＝1，結論自然成立。 假設對邊數小于m的連通平面圖結論成立。下面考慮連通平面圖G的邊數為m的情況。 設e是G的一條邊，從G中刪去e后得到的圖記為G?，并設其結點數、邊數和面數分別為n?、m?和r?。對e分為下列情況來討論： 若e為割邊，則G?有兩個連通分支G1和G2。Gi的結點數、邊數和面數分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。 若e不為割邊，則n?＝n，m?＝m－1，r?＝r－1，由歸納假設有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。 由數學歸納法知，結論成立。 七、（10分）設函數g：A→B，f：B→C，則： (1)fog是A到C的函數； (2)對任意的x∈A，有fog(x)＝f(g(x))。 證明(1)對任意的x∈A，因為g：A→B是函數，則存在y∈B使 對任意的x∈A，若存在y1、y2∈C，使得 綜上可知，fog是A到C的函數。 (2)對任意的x∈A，由g：A→B是函數，有 八、（15分）設 證明 對于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以 若 若 綜上可得，R是G中的一個等價關系。 對于任意的b∈[a]R，有 發到哪？給個郵箱啊~~~~~~~ 一、填空 20%（每小題2分） 1．設（N：自然數集，E???+ 正偶數）則。 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 d a b c d a b c d b c d a c d a b d a b c 那么代數系統 10．下圖所示的偏序集中，是格的為。 二、選擇 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 : I E , f(x)= 2x ； B．f : N N N, f(n)= C．f : R I , f(x)= [x] ； D．f :I N, 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> 和在R中有<.b , c>在R中。（8分） 2、f和g都是群 3、G= 四、邏輯推演 16% 用CP規則證明下題（每小題 8分） 1、2、五、計算 18% 1、設集合A={a，b，c，d}上的關系R={ ,< b , a > ,< b, c > , < c , d >}用矩陣運算求出R的傳遞閉包t(R)。（9分） 2、如下圖所示的賦權圖表示某七個城市 及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。（9分） 試卷一答案： 一、填空 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、{ 8、9、a ；a , b , c ,d ；a , d , c , d ； 10、c; 二、選擇 20%（每小題 2分） 題目 1 2 3 4 5 6 7 8 9 10 答案 C D B、C C A D C A D B A 三、證明 26% 1、證： “ ” 若 由R對稱性知，由R傳遞性得 “ ” 若，有 任意，因 若 所以R是對稱的。 若，則 即R是傳遞的。 2、證，有，又 ★ ★ ★ < C , ★> 是 < G1 , ★>的子群。 3、證： ①設G有r個面，則，即。而 故 即得。（8分） ②彼得森圖為，這樣 不成立，所以彼得森圖非平面圖。（3分） 二、邏輯推演 16% 1、證明： ① P（附加前提） ② T①I ③ P ④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P ⑧ T⑥⑦I ⑨ CP 2、證明 ① P（附加前提） ② US① ③ P ④ US③ ⑤ T②④I ⑥ UG⑤ ⑦ CP 三、計算 18% 1、解：，t(R)={ , , < a , c> , , , < b ,b > , < b , c.> , < b , d > , < c , d > } 2、解： 用庫斯克（Kruskal）算法求產生的最優樹。算法略。結果如圖： 樹權C(T)=23+1+4+9+3+17=57即為總造價。第三篇：離散數學試題與答案
第四篇：離散數學試題
第五篇：全國2008年4月自考離散數學試題
點擊咨詢 