離散數(shù)學(xué)作業(yè)

1、-離散數(shù)學(xué) 專業(yè)班級 學(xué)號 姓名 第一章 命題邏輯的基本概念一、單項選擇題1下列語句中不是命題的有（ ）.A 9+512 B. 1+3=5 C. 我用的電腦CPU主頻是1G嗎？D.我要努力學(xué)習(xí)。2. 下列語句是真命題為( )A. 1+2=5當(dāng)且僅當(dāng)2是偶數(shù) B.如果1+2=3，則2是奇數(shù)C. 如果1+2=5，則2是奇數(shù) D. 你上網(wǎng)了嗎？3. 設(shè)命題公式,則使公式取真值為1的p，q，r賦值分別是 ( )4. 命題公式為 ( )(A) 矛盾式(B) 僅可滿足式 (C) 重言式 (D) 合取范式5. 設(shè)p:我將去市里,q：我有時間命題“我將去市里，僅當(dāng)我有時間時”符號化為為( )6設(shè)P：我聽課,Q

2、：我看小說. “我不能一邊聽課，一邊看小說”的符號為（ ）A. ； B. ； C. ； D. 二、判斷下列語句是否是命題，若是命題是復(fù)合命題則請將其符號化（1）中國有四大發(fā)明。（2）2是有理數(shù)。（3）“請進！”（4）劉紅和魏新是同學(xué)。（5）a+b（6）如果買不到飛機票，我哪兒也不去。（8）侈而惰者貧，而力而儉者富。（韓非：韓非子·顯學(xué)）（9）火星上有生命。（10）這朵玫瑰花多美麗?。《?、將下列命題符號化，其中p:2<1,q:3<2（1）只要2<1，就有3<2。（2）如果2<1，則3³2。（3）只有2<1，才有3³2。（4）除非2

3、<1，才有3³2。（5）除非2<1，否則3³2。（6）2<1僅當(dāng)3<2。三、將下列命題符號化(1)小麗只能從筐里拿一個蘋果或一個梨。(2)王棟生于1992年或1993年。四、設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 （1）p(qr) （2）（pr）(qs) （3）（pqr）(pqr) (4)（rs）(pq) 五、用真值表判斷下列公式的類型：(1) p(pq)(pq) (2) (pr) (pq)(2)(pq) (qr) (pr)第二章 命題邏輯等值演算一、填空（1）給定兩個命題公式A，B，若 ，則稱A和B時等值的，記作AÛ

4、;B（2）德摩根律為： 。（3）蘊涵等值式為 。 （4）由已知的等值式推演出另外一些等值式的過程稱為 。二、用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.(1) (pqq)(2)(p(pq)(pr)(3)(pq)(pr)三、用等值演算法證明下面等值式(1)(pq)(pr)(p(qr)(2)(pq)(pq)(pq) (pq)三、用等值演算求下列公式的析取范式與合取范式。(1)(pq)(qp)(2)(pq)qr(3)(p(qr)(pqr)第三章 命題邏輯的推理理論一、 填空1.數(shù)理邏輯的的主要任務(wù)是 。推理是指 ， 前提是 ，結(jié)論是 。2.推理正確是指： 3.命

5、題公式A1，A,2，¼，A,k推B的推理正確當(dāng)且僅當(dāng) 二、先把下列命題符號化，再寫出前提、結(jié)論、推理的形式結(jié)構(gòu)，然后用真值表法、等值演算法證明下列推理是正確的。若今天是星期一，則明天是星期三。明天不是星期三，所以今天不是星期一。三、 自然推理系統(tǒng)下用直接法或用附加前提法或用歸謬法構(gòu)造推理證明 - 5 -(1)前提：pq,(qr),r結(jié)論：p (2)前提：qp,qs,st,tr結(jié)論：pq（3）前提：p(qr),sp,q （4）前提：pq,rq,rs結(jié)論：sr 結(jié)論：p 離散數(shù)學(xué)標(biāo)準(zhǔn)化作業(yè)紙 專業(yè)班級 學(xué)號 姓名 四、 在自然推理系統(tǒng)下構(gòu)造下列推理的證明1.如果我學(xué)習(xí)，那么我數(shù)學(xué)不會不及

6、格。如果不熱衷于玩游戲，那么我將學(xué)習(xí)。但我數(shù)學(xué)不及格。因此我熱衷于玩游戲。2.只要A曾到過受害者房間并且11點以前沒離開，A就是謀殺嫌犯。A曾到過受害者房間。如果A在11點以前離開，看門人就會看見他?？撮T人沒看見他。所以A是謀殺嫌犯。第四章 第五章一、1.設(shè)個體域D是正整數(shù)集合，確定下列命題為真的是（ ）A "x$y (xy=y)B. $x"y(x+y=y)C. $x"y(x+y=x) D. "x$y(y=2x) 2. 設(shè)謂詞P(x)：x是奇數(shù)，Q(x)：x是偶數(shù)，謂詞公式 $x(P(x)ÚQ(x)在哪個個體域中為真?( )A.自然數(shù)B. 實數(shù)

7、 C.復(fù)數(shù)D. (1)-(3)均成立3. 令R(x):x是實數(shù)，Q(x):x是有理數(shù)。則命題“并非每個實數(shù)都是有理數(shù)”的符號化表示為 二、在一階邏輯中將下列命題符號化:(1) 沒有不能表示成分?jǐn)?shù)的有理數(shù)。(2) 在北京賣菜的人不全是外地人。(3)烏鴉都是黑的。(4)有的人天天鍛煉身體。三、設(shè)個體域D=a,b,c,消去下列各式的量詞(1) "x $y(F(x) G(y)(2) "x $y(F(x) G(y)(3) "x F(x) $y G(y)四、設(shè)個體域D=1,2,3,4，F(xiàn)(x):x是2的倍數(shù)，G(x):x是奇數(shù)。將命題"x (F(x) Ø

8、G(y)中的量詞消去，并討論命題的真值。五、在自然推理系統(tǒng)用直接法或用附加前提法或用歸謬法構(gòu)造下列推理的證明 - 21 -（1）前提："x (F(x) G(x), "x F(x) 結(jié)論："x G(x) (2) 前提："x(F(x)G(x)結(jié)論："xF(x)"x G(x)(3) 前提："x(F(x)G(x)，$x G(x)結(jié)論：$x F(x)第六章 集合論一、單項選擇題1若集合A=a，b，B= a，b， a，b ，則（ ） AAÌB，且AÎB BAÎB，但AËB CAÌB，但A

9、ÏB DAËB，且AÏB2若集合A2，a， a ，4，則下列表述正確的是( )Aa， a ÎA B a ÍA C2ÎA DÎA3若集合A a，a，1，2，則下列表述正確的是( ) Aa，aÎA B2ÍACaÍA DÆÎA4若集合A=a，b， 1，2 ，B= 1，2，則（ ） AB Ì A，且BÎA BBÎ A，但BËA CB Ì A，但BÏA DBË A，且BÏA 5設(shè)集合A = 1, a ，則P

10、(A) = ( ) A1, a B,1, a C,1, a, 1, a D1, a, 1, a 6若集合A的元素個數(shù)為10，則其冪集的元素個數(shù)為（ ） A1024 B10 C100 D1二、1設(shè)集合A有n個元素，那么A的冪集合P(A)的元素個數(shù)為 2設(shè)集合Aa，b，那么集合A的冪集是 3.設(shè)A, B代表集合，命題A-B=ÆÛA=B的真值為 4. 設(shè)A, B為任意集合，命題A-B=ÆÛAÍB的真值為 5. 設(shè)集合A=Æ,a，則A的冪集P(A)= 6. 設(shè)集合A=a,b,c, B=c,d, 那么AB 三、（1）B、C為任意的三個集合，如果

11、AB=AC，判斷結(jié)論B=C 是否成立？并說明理由（2）B、C為任意的三個集合，如果AB=AC，判斷結(jié)論B=C 是否成立？并說明理由四、 1設(shè)集合Aa, b, c，B=b, d, e，求（1）BÇA； （2）AÈB； （3）AB； （4）BÅA2設(shè)A=a, b, 1, 2，B= a, b, 1, 1，試計算（1）（A-B） （2）（AB） （3）（AB）-（AB）五證明集合等式：A- B=A B六、某班有25個學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。已知6個會打網(wǎng)球的人都會打籃球或排球。求不會打球的人數(shù)

12、。第七章 二元關(guān)系（1）一、單項選擇題1集合A=1, 2, 3, 4, 5, 6, 7, 8上的關(guān)系R=<x，y>|x+y=10且x, yA，則R的性質(zhì)為（ ） A自反的 B對稱的 C傳遞且對稱的 D反自反且傳遞的2設(shè)集合A = 1，2，3，4，5，6 上的二元關(guān)系R =a , bêa , bA , 且a +b = 8，則R具有的性質(zhì)為（ ）A自反的 B對稱的C對稱和傳遞的 D反自反和傳遞的3集合Aa,b,c上二元關(guān)系R的關(guān)系矩陣MR， R( )，(A) <a,b>,<b,a>,<b,b>,<a,c> (B) <a,b

13、>,<b,a>,<b,b>,<c,b> (C) <a,b>,<a,a>,<b,b>,<c,a> (D) <a,b>,<b,a>,<b,b>,<c,a>4.設(shè)A=a，b，c，R=<a，a>，<b，b>，則R具有性質(zhì)（ ）(A) 自反的 (B) 反自反的 (C) 反對稱的 (D) 等價的二、填空題1設(shè)集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元關(guān)系，則R的有序?qū)蠟?2設(shè)集合A=0, 1, 2，B=0, 2,

14、 4,R是A到B的二元關(guān)系，則R的關(guān)系矩陣MR 3設(shè)集合A=a,b,c，A上的二元關(guān)系R=<a, b>,<c. a>，S=<a, a>,<a, b>,<c, c>則(R·S)1=4設(shè)集合A=a,b,c，A上的二元關(guān)系R=<a, b>, <b, a>, <b, c>, <c, d>，則二元關(guān)系R具有的性質(zhì)是三、設(shè)A=a，b，構(gòu)成集合（A）×A。四、(1)列出集合A=2,3,4上的恒等關(guān)系I A,全域關(guān)系EA,小于或等于關(guān)系LA,整除關(guān)系DA.(2)設(shè)A=a,b,c,d，

15、為A上的關(guān)系，其中= 求。adbc圖1五、設(shè)集合Aa, b, c, d上的二元關(guān)系R的關(guān)系圖如圖1所示（1）寫出R的表達式； （2）寫出R的關(guān)系矩陣； （3）求出R2 六、設(shè)集合A=1，2，3，4，R=<x, y>|x, yÎA；|x-y|=1或x-y=0，試（1）寫出R的集合表示； （2）畫出R的關(guān)系圖；（3）說明R滿足自反性，不滿足傳遞性第七章 二元關(guān)系（2）一、選擇題1. 設(shè)集合A=a,b上的二元關(guān)系R=<a,a>,<b,b>，則R ( )A. 是等價關(guān)系但不是偏序關(guān)系 B是偏序關(guān)系但不是等價關(guān)系C. 既是是等價關(guān)系又是偏序關(guān)系 D. 既不是

16、等價關(guān)系又不是偏序關(guān)系2. A=1、2、3，則A上不同等價關(guān)系有( ) A. 5 B.10 C. 15 D.83. 設(shè)A為有限集，元素個數(shù)為n個，P(A)為A的冪集，則P(A)的元素個數(shù)及的元素個數(shù)為( ) A B 及 C 及 D以上全不對4. 設(shè)A是非空集合，則A上的空關(guān)系不具有( )A反自反性 B自反性 C對稱性 D傳遞性5設(shè)，R是A上相等關(guān)系“=”，由R產(chǎn)生等價類有( ) A10個 B50個 C100個 D1個6.集合A的一個劃分，確定A的元素間的關(guān)系為( ). A全序關(guān)系B等價關(guān)系C偏序關(guān)系D擬序關(guān)系7集合A=1，2，3上的下列關(guān)系矩陣中符合等價關(guān)系條件的是（）A B C D8.給定A

17、=1、2、3上的關(guān)系R=<1, 1>, <2, 2>, <1, 3>, <3, 1>, <2, 3>則( )A R是自反的且傳遞 B R不反自反且不對稱C R是反對稱且不對稱 D R不自反且傳遞9.設(shè)A=，1，1，3，1，2，3則A上包含關(guān)系“”哈斯圖為（ ）二、設(shè)A=1，2，3，4,R=<1,1>,<2,2>,<3,3>,<4,4>,<2,3>,<3,2>是A上的等價關(guān)系嗎？如果是,給出給出每個元素的等價類；如果不是,請說明理由。三、設(shè)A=1，2，3，4，S=1

18、，2，3，4為A的一個分劃，求由S導(dǎo)出的等價關(guān)系.四、設(shè)集合A=1，2，3，6，8，12，24，36，R為A上整除關(guān)系，畫出R的哈斯圖，并指出B=2，6，8的極大元，極小元、最大元，最小元、及上確界和下確界。五、設(shè)A=1，2，3，4，在AA上定義二元關(guān)系R， <u,v>,<x,y>AA ，u,v> R <x,y>u + y = x + v.(1) 證明R 是AA上的等價關(guān)系.(2)確定由R 引起的對AA的劃分.第八章 函數(shù)一、選擇題1設(shè)A=a, b，B=1, 2，R1，R2，R3是A到B的二元關(guān)系，且R1=<a，2>, <b，2>

19、;，R2=<a，1>, <a，2>, <b，1>，R3=<a，1>, <b，2>，則（ ）不是從A到B的函數(shù) AR1和R2 BR2 CR3 DR1和R32.設(shè)A=a，b，c，B=1，2，作f：AB，則不同的函數(shù)個數(shù)為( )A 6 B.5 C. 9 D.83.下列函數(shù)中為雙射的是( ). AB CD4.設(shè)Z是整數(shù)集，E=,-4,-2,0,2,4，f：ZE，f（x）=2x，則f是( )A僅是滿射B僅是單射 C是雙射D無逆函數(shù)二、判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的? (1) f:NN, f(x)=x2+2 (2) f:N

20、N,f(x)=(x)mod 3, x除以3的余數(shù) (3) f:NN,f(x)= (4) f:N0,1,f(x)= (5) f:N-0R,f(x)=lgx (6) f:RR,f(x)=x2-2x-15 三、設(shè)X=a,b,c,d,Y=1,2,3,f=<a,1>,<b,2>,<c,3>,判斷以下命題的真假: (1)f是從X到Y(jié)的二元關(guān)系,但不是從X到Y(jié)的函數(shù); (2)f是從X到Y(jié)的函數(shù),但不是滿射,也不是單射的; (3)f是從X到Y(jié)的滿射,但不是單射; (4)f是從X到Y(jié)的雙射.四、設(shè)A=1,2，B=a,b,c,寫出所有A到B的函數(shù)，并說明所具有的性質(zhì)。五、已知集

21、合A和B且|A|=n，|B|=m，求A到B的二元關(guān)系數(shù)是多少？A到B的函數(shù)數(shù)是多少？ 六、設(shè)N是自然數(shù)集合，定義 N 上的二元關(guān)系R：R=(x,y): x ÎN, y ÎN, x+y 是偶數(shù)(1) 證明R是等價關(guān)系。 (2) 求 關(guān)系R的等價類。第十四、十五章 一、單項選擇題1一個無向圖有4個結(jié)點，其中3個的度數(shù)為2，3，3，則第4個結(jié)點的度數(shù)不可能是（ ）A.0 B. 1 C. 2 D. 42無向完全圖有 (    )條邊A. n        

22、0; B. n2    C.  n(n-1)      D. n(n-1)/23整數(shù)列（1，3，3，5，4）（ ）A可以簡單圖化 B. 不可圖化 C. 可圖化，不可簡單圖化4若答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是( ). 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).5設(shè)簡單圖G所有結(jié)點的度之和為12，則G一定有( ). A3條邊 B4條邊 C5條邊 D6條邊6設(shè)無向圖中有

23、6條邊，有一個3度頂點和一個5度頂點，其余頂點度為2，則該圖的頂點數(shù)是（）A3 B4 C5 D67下列各圖中既是歐拉圖，又是漢密爾頓圖的是（）A B C D8.設(shè)G為完全二部圖K2,3，下面命題中為真的是( )A.G為歐拉圖 B.G為哈密爾頓圖C.G為平面圖 D.G為正則圖二、填空1簡單無向圖有21條邊,3個4度結(jié)點,其余均為3度結(jié)點,則G有_個結(jié)點.2無向圖G=<V,E>,V=a,b,c,d,E=(a,b),(a,c),(a,d),(b,c),則它的鄰接矩陣為 ，該圖的補圖有 條邊。3.設(shè)K6是有6個點的完全圖，則K6共有_條邊。4. .已知n階無向簡單圖G有m條邊，則G的補圖G

24、有_條邊。5. 若一條路中，所有邊均不相同，則此路稱作_；若一條路中所有的結(jié)點均不相同，則稱此路為_。6設(shè)無向圖G有18條邊且每個頂點的度數(shù)都是3，則圖G有 個頂點。 7任一有向圖中，度數(shù)為奇數(shù)的結(jié)點有()個。 8. 無向連通圖G含有歐拉回路的充分必要條件是 9.已知n階無向圖G中有m條邊，各頂點的度數(shù)均為3。又已知2n-3=m，則m= .三、（1）已知無向圖G有12條邊，1度頂點有2個，2度、3度、5度頂點各1個，其余頂點度數(shù)均為4，求4度頂點的個數(shù)。（2）假設(shè)在圖G(有向圖或無向圖)中，有10條邊，4個3度的結(jié)點，其余結(jié)點的度數(shù)不大于2。問G中至少有幾個結(jié)點？四、判斷下圖是否歐拉圖，若是，找出一個歐拉回路。五設(shè)簡單無向圖G有n個結(jié)點,n+1條邊，證明G中至少有一上結(jié)點的度3。六、畫出彼德森圖，K5，K3,3，并判斷他們是否是歐拉圖，是否是哈密頓圖。第十六、十七章一、選擇題1設(shè)G是有6個結(jié)點的無向完全圖，從G中刪去( )條邊，則得到樹(A) 6 (B) 9 (C) 10 (D) 152設(shè)G是連通平面圖，G中有6個頂點8條邊，則G的面的數(shù)目是（