離散數(shù)學習題集(十五套)

1、離散數(shù)學試題與答案試卷一一、填空 20% （每小題2分）1設 （N：自然數(shù)集，E+ 正偶數(shù)） 則 。2A，B，C表示三個集合，文圖中陰影部分的集合表達式為 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 dabcda b c db c d ac d a bd a b c那么代數(shù)系統(tǒng)<A，*>的幺元是

2、，有逆元的元素為 ，它們的逆元分別為 。10下圖所示的偏序集中，是格的為 。 二、選擇 20% （每小題 2分）1、下列是真命題的有（）A ； B；C ； D 。2、下列集合中相等的有（ ） A4，3；B，3，4；C4，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的冪集）上規(guī)定二元

3、系如下則P（A）/ R=（ ）AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、設A=，1，1，3，1，2，3則A上包含關系“”的哈斯圖為（ ）7、下列函數(shù)是雙射的為（ ）Af : IE , f (x) = 2x ； Bf : NNN, f (n) = <n , n+1> ；Cf : RI , f (x) = x ； Df :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圖，也不是Ha

4、milton圖的圖是（ ）10、在一棵樹中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點則該樹有（ ）個4度結(jié)點。A1；B2；C3；D4 。三、證明 26%、 R是集合X上的一個自反關系，求證：R是對稱和傳遞的，當且僅當< a, b> 和<a , c>在R中有<.b , c>在R中。（8分）、 f和g都是群<G1 ,>到< G2, *>的同態(tài)映射，證明<C , >是<G1, >的一個子群。其中C= (8分)、 G=<V, E> (|V| = v，|E|=e ) 是每一個面至少由k（k3）條邊圍成的連通平

5、面圖，則， 由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演 16%用CP規(guī)則證明下題（每小題 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；

6、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、c; 二、選擇 20% （每小題 2分）題目12345678910答案C DB、CCADCADBA三、證明 26%1、 證：“” 若由R對稱性知，由R傳遞性得 “” 若，有 任意 ，因若 所以R是對稱的。若， 則 即R是傳遞的。2、 證，有 ，又 < C ,

7、> 是 < G1 , >的子群。3、 證：設G有r個面，則，即 。而 故即得 。（8分）彼得森圖為，這樣不成立，所以彼得森圖非平面圖。（3分） 一、 邏輯推演 16%1、 證明：P（附加前提）TIPTITITIPTICP2、證明 P（附加前提）USPUSTIUGCP二、 計算 18%1、 解： ， ，t (R)=<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d >

8、; , < c , d > 2、 解： 用庫斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：樹權C(T)=23+1+4+9+3+17=57即為總造價。試卷二試題與答案一、填空 20% （每小題2分）1、 P：你努力，Q：你失敗?！俺悄闩?，否則你將失敗”的翻譯為 ；“雖然你努力了，但還是失敗了”的翻譯為 。2、論域D=1，2，指定謂詞PP (1,1)P (1,2)P (2,1)P (2,2)TTFF則公式真值為 。2、 設S=a1 ，a2 ，a8，Bi是S的子集，則由B31所表達的子集是 。3、 設A=2，3，4，5，6上的二元關系，則R= （列舉法）。R的關系矩陣M

9、R= 。5、設A=1，2，3，則A上既不是對稱的又不是反對稱的關系R= ；A上既是對稱的又是反對稱的關系R= 。*a b cabca b cb b cc c b6、設代數(shù)系統(tǒng)<A，*>，其中A=a，b，c,則幺元是 ；是否有冪等 性 ；是否有對稱性 。7、4階群必是 群或 群。8、下面偏序格是分配格的是 。9、n個結(jié)點的無向完全圖Kn的邊數(shù)為 ，歐拉圖的充要條件是 。10、公式的根樹表示為 。二、選擇 20% （每小題2分）1、在下述公式中是重言式為（ ）A；B；C； D。2、命題公式 中極小項的個數(shù)為（ ），成真賦值的個數(shù)為（ ）。A0； B1； C2； D3 。3、設，則 有（

10、 ）個元素。A3； B6； C7； D8 。4、 設，定義上的等價關系則由 R產(chǎn) 生的上一個劃分共有（ ）個分塊。A4； B5； C6； D9 。5、設，S上關系R的關系圖為則R具有（ ）性質(zhì)。A自反性、對稱性、傳遞性； B反自反性、反對稱性；C反自反性、反對稱性、傳遞性； D自反性 。6、設 為普通加法和乘法，則（ ）是域。A BC D= N 。7、下面偏序集（ ）能構(gòu)成格。8、在如下的有向圖中，從V1到V4長度為3 的道路有（ ）條。A1； B2； C3； D4 。9、在如下各圖中（ ）歐拉圖。10、設R是實數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng)<R ，×> 是（ ）。A

11、群； B獨異點； C半群 。三、證明 46%1、 設R是A上一個二元關系，試證明若R是A上一個等價關系，則S也是A上的一個等價關系。（9分）2、 用邏輯推理證明：所有的舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。（11分）3、 若是從A到B的函數(shù)，定義一個函數(shù)對任意有，證明：若f是A到B的滿射，則g是從B到 的單射。（10分）4、 若無向圖G中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定連通。（8分）5、 設G是具有n個結(jié)點的無向簡單圖，其邊數(shù)，則G是Hamilton圖（8分）四、計算 14%1、 設<Z6,+6>是一個群，這里+6是模6加法，Z6=0 ，1，2，3，

12、4，5，試求出<Z6,+6>的所有子群及其相應左陪集。（7分）2、 權數(shù)1，4，9，16，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二叉樹。（7分）試卷二答案：一、 填空 20%（每小題2分）1、；2、T 3、4、R=<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,&l

13、t;5,5>,<5,6>； 5、R=<1,2>,<1,3>,<2,1>；R=<1,1>,<2,2>,<3,3> 6、a ；否；有 7、Klein四元群；循環(huán)群 8、 B 9、；圖中無奇度結(jié)點且連通 10 、二、 選擇 20%（每小題 2分）題目12345678910答案B、DD；DDBDABBBB、C三、 證明 46%1、（9分）（1） S自反的，由R自反，（2） S對稱的（3） S傳遞的由（1）、（2）、（3）得；S是等價關系。2、11分證明：設P(x)：x 是個舞蹈者； Q(x) ：x很有風度； S(

14、x)：x是個學生； a：王華上述句子符號化為：前提：、 結(jié)論： 3分PPUSTI TITITIEG11分、0分證明 ：。4、8分證明：設G中兩奇數(shù)度結(jié)點分別為u 和v，若 u，v不連通，則G至少有兩個連通分支G1、G2 ，使得u和v分別屬于G1和G2，于是G1和G2中各含有1個奇數(shù)度結(jié)點，這與圖論基本定理矛盾，因而u，v一定連通。5、8分證明： 證G中任何兩結(jié)點之和不小于n。反證法：若存在兩結(jié)點u，v 不相鄰且,令，則G-V1是具有n-2個結(jié)點的簡單圖，它的邊數(shù),可得，這與G1=G-V1為n-2個結(jié)點為簡單圖的題設矛盾，因而G中任何兩個相鄰的結(jié)點度數(shù)和不少于n。所以G為Hamilton圖.四、

15、 計算 14%1、 7分解：子群有<0,+6>；<0,3,+6>；<0,2,4,+6>；<Z6,+6>0的左陪集：0，1；2，3；4，50，3的左陪集：0，3；1，4；2，50，2，4的左陪集：0，2，4；1，3，5Z6的左陪集：Z6 。2、 7分試卷三試題與答案一、 填空 20% （每空 2分）1、 設 f，g是自然數(shù)集N上的函數(shù)，則 。2、 設A=a，b，c，A上二元關系R=< a, a > , < a, b >,< a, c >, < c, c> , 則s（R）= 。3、 A=1，2，3，4，

16、5，6，A上二元關系，則用列舉法 T= ；T的關系圖為 ；T具有 性質(zhì)。4、 集合的冪集= 。5、 P，Q真值為0 ；R，S真值為1。則的真值為 。6、 的主合取范式為 。7、 設 P（x）：x是素數(shù)， E(x)：x 是偶數(shù)，O(x)：x是奇數(shù) N (x,y)：x可以整數(shù)y。則謂詞的自然語言是 。8、 謂詞的前束范式為 。二、 選擇 20% （每小題 2分）1、 下述命題公式中，是重言式的為（ ）。A、； B、；C、； D、。2、 的主析取范式中含極小項的個數(shù)為（ ）。A 、2； B、 3； C、5； D、0； E、 8 。3、 給定推理PUSPESTIUG推理過程中錯在（ ）。A、->

17、 B、-> C、-> D、-> E、->4、 設S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在條件下X與（ ）集合相等。A、 X=S2或S5 ； B、X=S4或S5；C、X=S1，S2或S4； D、X與S1，S5中任何集合都不等。5、 設R和S是P上的關系，P是所有人的集合，則表示關系 （ ）。A、；B、；C、 ； D、。6、 下面函數(shù)（ ）是單射而非滿射。A、；B、；C、；D、。其中R為實數(shù)集，Z為整數(shù)集，R+，Z+分別表示正實數(shù)與正整數(shù)集。7、 設S=1，2，3，R為S上的關系，其關系圖為 則R具有（ ）的性

18、質(zhì)。A、 自反、對稱、傳遞； B、什么性質(zhì)也沒有；C、反自反、反對稱、傳遞； D、自反、對稱、反對稱、傳遞。8、 設，則有（ ）。A、1,2 ；B、1,2 ； C、1 ； D、2 。9、 設A=1 ,2 ,3 ，則A上有（ ）個二元關系。A、23 ； B、32 ； C、； D、。10、全體小項合取式為（ ）。A、可滿足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。三、 用CP規(guī)則證明 16% （每小題 8分）1、2、四、（14%） 集合X=<1,2>, <3,4>, <5,6>, ，R=<<x1,y1>,<x2,y2&g

19、t;>|x1+y2 = x2+y1 。1、 證明R是X上的等價關系。 （10分）2、 求出X關于R的商集。（4分）五、（10%）設集合A= a ,b , c , d 上關系R=< a, b > , < b , a > , < b , c > , < c , d > 要求 1、寫出R的關系矩陣和關系圖。（4分） 2、用矩陣運算求出R的傳遞閉包。（6分）六、（20%）1、（10分）設f和g是函數(shù)，證明也是函數(shù)。2、（10分）設函數(shù)，證明 有一左逆函數(shù)當且僅當f是入射函數(shù)。答案：五、 填空 20%（每空2分）1、2(x+1)；2、；3、；4、反對

20、稱性、反自反性；4、；5、1；6、；7、任意x，如果x是素數(shù)則存在一個y，y是奇數(shù)且y整除x ；8、。六、 選擇 20%（每小題 2分）題目12345678910答案CCCCABDADC七、 證明 16%(每小題8分)1、P（附加前提）TIPTITITIPTICP2、 P（附加前提）TEESPUSTIEGCP八、 14%（1） 證明：1、 自反性： 2、 對稱性： 3、 傳遞性：即由（1）（2）（3）知：R是X上的先等價關系。2、X/R=九、 10%1、； 關系圖2、 t (R)=<a , a> , <a , b> , < a , c> , <a ,

21、d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > 。 六、 20%1、（1）（2）。2、證明：。*則<B4,*>是一個群（稱作Klein四元群答案：十、 填空 15%（每小題3分）1、；2、奇數(shù)；3、5；4、n；5、臂力小者 十一、 選擇 15%（每小題 3分）題目12345答案BCBBA十二、 證明 34%1、（10分）證明：用n個頂點v1，vn表示n個人，構(gòu)成頂點集V=v1，vn，設，無向圖G=（V，E）現(xiàn)證G中至少有兩個結(jié)點度數(shù)相同。

22、事實上，（1）若G中孤立點個數(shù)大于等于2，結(jié)論成立。（2） 若G中有一個孤立點，則G中的至少有3個頂點，現(xiàn)不考慮孤立點。設G中每個結(jié)點度數(shù)均大于等于1，又因為G為簡單圖，所以每個頂點度數(shù)都小于等于n-1，由于G中頂點數(shù)到值只能是1，2，n-1這n-1個數(shù)，因而取n-1個值的n個頂點的度數(shù)至少有兩個結(jié)點度數(shù)是相同的。2、（8分）證：設G中兩個奇數(shù)度結(jié)點分別為u，v。若 u，v不連通，即它們中無任何通路，則至少有兩個連通分支G1、G2，使得u，v分別屬于G1和G2。于是G1與G2中各含有一個奇數(shù)度結(jié)點，與握手定理矛盾。因而u，v必連通。3、（8分）證：n=6,m=12 歐拉公式n-m+f=2知 f

23、=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個面用3條邊圍成。4、（10分） 證：設循環(huán)群A，·的生成元為a，同態(tài)映射為f，同態(tài)像為<f（A），*>，于是都有對n=1有n=2, 有若n=k-1時 有對n=k時，這表明，f(A)中每一個元素均可表示為，所以<f(A),*>是以f(a) 生成元的循環(huán)群。十三、 中國郵遞員問題 14%解：圖中有4個奇數(shù)結(jié)點，（1） 求任兩結(jié)點的最短路再找兩條道路使得它們沒有相同的起點和終點，且長度總和最短：（2） 在原圖中復制出，設圖G，則圖G中每個結(jié)點度數(shù)均為偶數(shù)的圖G存在歐拉回路，歐拉回路C權長為43。十

24、四、 根樹的應用13%解：用100乘各頻率并由小到大排列得權數(shù)（1） 用Huffman算法求最優(yōu)二叉樹：（2） 前綴碼用 00000傳送 5；00001傳送 6；0001傳送 7；100傳送 3；101傳送 4；001傳送 2；11傳送 1；01傳送 0 （頻率越高傳送的前綴碼越短）。十五、 10%證明：（1） 乘：由運算表可知運算*是封閉的。（2） 群：即要證明，這里有43=64個等式需要驗證但： e是幺元，含e的等式一定成立。ab=a*b=b*a，如果對含a，b的等式成立，則對含a、b、ab的等式也都成立。剩下只需驗證含a、b等式，共有23=8個等式。即：(a*b)*a=ab*a=b=a*

25、(b*a)=a*ab=b； (a*b)*b=ab*b=a=a*(b*b)=a*e=a；(a*a)*a=e*a=a=a*(a*a)=a*e=a ； (a*a)*b=e*b=b=a*(a*b)=a*ab=b；(b*b)*a=e*a=a=b*(b*a)=b*ab=a； (b*b)*b=e*b=b=b*(b*b)=b*e=b；(b*a)*a=ab*a=b=b*(a*a)=b*e=b ； (b*a)*b=ab*b=a=b*(a*b)=b*ab=a 。（3） 幺： e為幺元（4） 逆：e -1=e ；a -1=a ；b -1=b ； (ab) -1=ab 。所以<B4,*>為群。試卷八試題與答

26、案一、 填空 15% （每小題 3分）1、 n階完全圖Kn的邊數(shù)為 。2、 右圖 的鄰接矩陣A= 。 3、 圖 的對偶圖為 。4、 完全二叉樹中，葉數(shù)為nt，則邊數(shù)m= 。5、 設< a,b,c, * >為代數(shù)系統(tǒng)，* 運算如下：*abcaabcbbaccccc則它的幺元為 ；零元為 ； a、b、c的逆元分別為 。二、 選擇 15% （每小題 3分）1、 圖 相對于完全圖的補圖為（ ）。 2、 對圖G 則分別為（ ）。A、2、2、2； B、1、1、2； C、2、1、2； D、1、2、2 。3、 一棵無向樹T有8個頂點，4度、3度、2度的分枝點各1個，其余頂點均為樹葉，則T中有（ ）

27、片樹葉。A、3； B、4； C、5； D、64、 設<A，+，·>是代數(shù)系統(tǒng)，其中+，·為普通的加法和乘法，則A=（ ）時<A，+，·>是整環(huán)。A、； B、；C、； D、。5、 設A=1，2，10 ，則下面定義的運算*關于A封閉的有（ ）。A、 x*y=max(x ,y)； B、x*y=質(zhì)數(shù)p的個數(shù)使得；C、x*y=gcd(x , y)； (gcd (x ,y)表示x和y的最大公約數(shù))；D、x*y=lcm(x ,y) （lcm(x ,y) 表示x和y的最小公倍數(shù)）。三、 證明 45% 1、設G是（n,m）簡單二部圖，則。（8分）2、設G為具

28、有n個結(jié)點的簡單圖，且則G是連通圖。（8分）3、設G是階數(shù)不小于11的簡單圖，則G或中至少有一個是非平圖。（14分）4、記“開”為1，“關”為0，反映電路規(guī)律的代數(shù)系統(tǒng)0，1，+，·的加法運算和乘法運算。如下：+01·01001000110101證明它是一個環(huán)，并且是一個域。（15分）四、 生成樹及應用 10%1、（10分）如下圖所示的賦權圖表示某七個城市及預先測算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間既能夠通信而且總造價最小。2、（10分）構(gòu)造H、A、P、N、E、W、R、對應的前綴碼，并畫出與該前綴碼對應的二叉樹，寫出英文短語HAPPY NE

29、W YEAR的編碼信息。五、 5%對于實數(shù)集合R，在下表所列的二元遠算是否具有左邊一列中的性質(zhì)，請在相應位上填寫“Y”或“N”。MaxMin+可結(jié)合性可交換性存在幺元存在零元答案：十六、 填空 15%（每小題3分）1、；2、；3、；4、；5、a，c，a、b、沒有十七、 選擇 15%（每小題 3分）題目12345答案AACDA，C十八、 證明 45%1、 （8分）：設G=（V，E），對完全二部圖有當時，完全二部圖的邊數(shù)m有最大值。故對任意簡單二部圖有。2、 （8分）反證法：若G不連通，不妨設G可分成兩個連通分支G1、G2，假設G1和G2的頂點數(shù)分別為n1和n2，顯然。與假設矛盾。所以G連通。3、

30、（14分）（1）當n=11時，邊數(shù)條，因而必有或的邊數(shù)大于等于28，不妨設G的邊數(shù)，設G有k個連通分支，則G中必有回路。（否則G為k棵樹構(gòu)成的森林，每棵樹的頂點數(shù)為ni，邊數(shù)mi，則, 矛盾）下面用反證法證明G為非平面圖。假設G為平面圖，由于G中有回路且G為簡單圖，因而回路長大于等于3 。于是G的每個面至少由g ()條邊圍成，由點、邊、面數(shù)的關系，得：而 矛盾，所以G為非平面圖。（2）當n>11時，考慮G的具有11個頂點的子圖，則或必為非平面圖。如果為非平面圖，則為非平面圖。如果為非平面圖，則為非平面圖。4、 （15分）1）0，1，+，·是環(huán)0，1，+是交換群乘：由“+”運算表

31、知其封閉性。由于運算表的對稱性知：+運算可交換。群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1 ；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0 結(jié)合律成立。 幺：幺元為0。逆：0，1逆元均為其本身。所以，<0，1，+>是Abel群。<0，1，·>是半群乘：由“· ”運算表知封閉群： (0·0)·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）=1；（0·1）&#

32、183;0=0·（1·0）=1 ；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0 ；·對+的分配律對 0·（x+y）=0=0+0=(0·x)+(0·y) 1·（x+y）當x=y (x+y)=0 則當（）則所以均有同理可證：所以·對+ 是可分配的。由得，<0，1，+，·>是環(huán)。（2）<0，1，+，·>是域因為<0，1，+，·>是有限環(huán)，故只需證明是整

33、環(huán)即可。乘交環(huán)： 由乘法運算表的對稱性知，乘法可交換。含幺環(huán)：乘法的幺元是1無零因子：1·1=10因此0，1，+，·是整環(huán)，故它是域。十九、 樹的應用 20%1、（10分）解： 用庫斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：樹權C(T)=23+1+4+9+3+17=57即為總造價五、（10分）由二叉樹知H、A、P、Y、N、E、W、R對應的編碼分別為000、001、010、011、100、101、110、111。顯然000，001，010，011，100，101，110，111為前綴碼。英文短語HAPPY NEW YEAR 的編碼信息為000 001 010

34、 010 011 100 101 001 001 101 001 111六、5%MaxMin+可結(jié)合性YYY可交換性YYY存在幺元NNY存在零元NNN試卷九試題與答案一、 填空 30% （每空 3分）1、 選擇合適的論域和謂詞表達集合A=“直角坐標系中，單位元（不包括單位圓周）的點集”則A= 。2、 集合A=,的冪集P(A) = 。3、 設A=1，2，3，4，A上二元關系R=<1，2>，<2，1>，<2，3>，<3，4>畫出R的關系圖 。4、 設A=<1,2>,<2 , 4 >,<3 , 3 > , B=<

35、;1,3>,<2,4>,<4,2>,則= 。= 。5、 設|A|=3，則A上有 個二元關系。6、 A=1，2，3上關系R= 時，R既是對稱的又是反對稱的。7、 偏序集的哈斯圖為，則= 。8、 設|X|=n，|Y|=m則（1）從X到Y(jié)有 個不同的函數(shù)。（2）當n , m滿足 時，存在雙射有 個不同的雙射。9、 是有理數(shù)的真值為 。10、 Q：我將去上海，R：我有時間，公式的自然語言為 。11、 公式的主合取范式是 。12、 若是集合A的一個分劃，則它應滿足 。二、 選擇 20% （每小題 2分）1、 設全集為I，下列相等的集合是（ ）。A、； B、；C、； D、。2

36、、 設S=N，Q，R，下列命題正確的是（ ）。A、； B、；C、； D、。3、 設C=a,b,a,b，則分別為（ ）。A、C和a,b；B、a,b與；C、a,b與a,b；D、C與C4、 下列語句不是命題的有（ ）。A、 x=13； B、離散數(shù)學是計算機系的一門必修課； C、雞有三只腳；D、太陽系以外的星球上有生物； E、你打算考碩士研究生嗎？5、 的合取范式為（ ）。A、 ；B、 ；C、 D、。6、 設|A|=n，則A上有（）二元關系。A、2n ； B、n2 ； C、； D、nn ； E、。7、 設r為集合A上的相容關系，其簡化關系圖（如圖），則 I r產(chǎn)生的最大相容類為（ ）；A、； B、；

37、C、； D、II A的完全覆蓋為（ ）。A、； B、；C、； D、。8、 集合A=1，2，3，4上的偏序關系圖為 則它的哈斯圖為（ ）。9、 下列關系中能構(gòu)成函數(shù)的是（ ）。A、；B、；C、； D、。10、N是自然數(shù)集，定義（即x除以3的余數(shù)），則f是（ ）。A、滿射不是單射；B、單射不是滿射；C、雙射；D、不是單射也不是滿射。三、 簡答題 15% 1、(10分)設S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”為S上整除關系，問：（1）偏序集的Hass圖如何？（2）偏序集的極小元、最小元、極大元、最大元是什么?2、（5分）設解釋R如下：DR是實數(shù)集，DR中特定元素a=0

38、，DR中特定函數(shù)，特定謂詞，問公式的涵義如何？真值如何？四、 邏輯推理 10%或者邏輯難學，或者有少數(shù)學生不喜歡它；如果數(shù)學容易學，那么邏輯并不難學。因此，如果許多學生喜歡邏輯，那么數(shù)學并不難學。五、10%設X=1,2,3,4,5，X上的關系R=<1,1> , < 1 , 2 > , <2 , 4 > , < 3 , 5 > , < 4 , 2 > ，用Warshall方法，求R的傳遞閉包t (R)。六、證明 15%1、 每一有限全序集必是良序集。（7分）2、 設是復合函數(shù)，如果滿射，則也是滿射。（8分）答案二十、 填空 20%（每小

39、題2分）1、；2、；3、見右圖；4、< 1 , 2 > , < 2 , 4 > , <3 , 3 > , < 1，3 >，<2,4> ,<4,2>、< 1 , 4 > , < 2 , 2 > ；5、29； 6、< 1 , 1 > , < 2 , 2 > , <3 , 3 > ；7、<a,b>,<a,d>,<a,e>,<b,d>,<b,e>,<a,c>,<a,f>,<a,g&g

40、t;,<c,f>,<c,g>；8、mn 、n=m、n!；9、假；10、我將去上海當且僅當我有空；11、；12、。二十一、 選擇 20%（每小題 2分）題目12345678910答案A、DCBA、EB、DCB、D；CABD二十二、 簡答題 15%1、（10分）（1）=<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6

41、>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>covS=<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,<6,12> ,<8,24>,<12,24>Hass圖為 （2）極小元、最小元是1，極大元、最大元是 24。2、（5分） 解：公式A涵義為：對

42、任意的實數(shù)x,y,z，如果x<y 則 (x-z) < (y-z) A的真值為： 真（T）。二十三、 邏輯推理 10%解：設P：邏輯難學；Q：有少數(shù)學生不喜歡邏輯學；R：數(shù)學容易學符號化：證：PTEPTITE二十四、 （10分）解：1時，1,1=1, A =2時，A1,2=A4,2=1A=3時，A的第三列全為0，故A不變4時A1,4=A2,4=A4,4=1A=5時，A的第五行全為0，故A不變。所以t (R)=<1,1>, <1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<

43、4,4>。二十五、 證明 15%1、（7分）證明：設，全序集。若不是良序集，那么必有一子集，在B中不存在最小元素，由于B是一有限集合，故一定可找出兩元素x ,y是無關的，由于是全序集。所以x ,y必有關系，矛盾。故必是良序集。2、（8分）證明：設， 由于滿射，故必有使得，由復合函數(shù)定義知，存在使得，又因為g是函數(shù)，必對任，必使，任每個z在g作用下都是Y中元素的一個映象，由Z的任意性，所以g是滿射。試卷十試題與答案一、 填空 10% （每小題 2分）1、 若P，Q為二命題，真值為1，當且僅當 。2、 對公式中自由變元進行代入的公式為 。3、 的前束范式為 。4、 設x是謂詞合式公式A的一個客體變元，A的論域為D，A（x）關于y的自由的，則 被稱為全稱量詞消去規(guī)則，記為US。5、 與非門的邏輯網(wǎng)絡為 。二、 選擇 30% （每小題 3分）1、 下列各符號串，不是合式公式的有（ ）。A、； B、；C、； D、。2、 下列語句是命題的有（