CHOI復習j1.21. 命題判斷（14分）1.1-1.3P32-A小李和小王是同班同學 B小豬不是鮮花C3-2n<0D若2+2=4,則太陽西方升起。上述語句中，—是簡單命題，—不是命題，—是符合命題且真值為假，_是符合命題且真值為真。（參考答案：ACDB）2. 命題符號化（24分）1.5（7）（3）P32-P：天下人雨，q：他乘公共汽車去上班，命題“除非天下大雨，否則他不乘公共汽車去上班”可符號化為—o（參考答案：q-p必要條件為后件）r：天很冷，s：老李來了，命題“雖然天很冷，老李還是來了”可符號化為_,（參考答案rAs）3. 五個真值表（24分）1.6（2）（4）P32-P0,r1,q、s都是命題，則命題公式（3or）Jqvs） ,命題公式->3v（qCr人「p〉））tCr「s）的真值為 。（參考答案：0,1）p、q填空。（14分）朕本概念px>0（x是整數(shù)），q：太陽從西方升起，則_是命題，_是命題變項，是命題常項，_不是命題。（參考答案：q，p,q,p）命題符號化，相容或與排斥或設r：現(xiàn)在小李在圖書館，s：現(xiàn)在小李在學生宿舍，則“現(xiàn)在小李在圖書館或學生宿舍”可符號化為—。（參考答案：B）ArVsB（rA-'sJV（"YAs）

CrAsD（rA-'s）或（~YAS）§1.2命題公式及分類已知：A是含三個命題變項的命題公式，且A（001）=0,A（100）=l,則A是 o（D）A矛盾是B可滿足式C重言式D非重言式的可滿足式§1.3等值演算用等值演算法證明等值式：（p/\q）f中（q-r）.（演算的每一步都要寫依據(jù)）§1.4范式（14分）A（p,q）的真值表PqA(p,q)000011100111求A的永主析取范式、主合取范式、成真賦值和成假賦值。（參考答案：miVm3,0111,0010）（2分）命題公式B（p,qj）=（「p/\r7\「q）的主析取范式是 。（參考答案：C）Am2 BM6 Cmi DM5E命題公式B（pzq,r）=（-pV-qVr）W主析取范式是 。（參考答案：A）AmoVmiVm2Vm3Vm4Vm5Vm7BIVkCmiDMi§1.5全功能集（2分） 不是聯(lián)結詞全功能集。（參考答案：D）A{t}

B{--*}

C{-V} D{A,V} 是聯(lián)結詞全功能集。（參考答案：A）A{l,}

B{V,A}C{V}

D{A}§1.6組合電路（習題1.16）有一盞燈由三個開關控制，要求按任何一個開關都能使燈由黒變亮或由亮變黑,試設計這樣的一個電路。（解題基本步驟：狀態(tài)設置、設計真值表、寫主析取范式、化簡、繪制電路.答案不唯一）§1.7推理理論（習題1.19（1））用直接證明法或歸謬法證明下面的推理.前提：證明：...

pA^q）,「qVr,~T.結論：~p-（習題1.19⑶）用直附加前提法證明卞面的推理.前提：P~*q.結論：P-*（pAq）.證明：...（例題1.28）公安人員審查一件盜竊案，已知事實如下：李或王盜竊了錄音機；若李盜竊了錄音機，則作案時間不能發(fā)生在午夜前;若王的證詞正確，則午夜時屋里燈光未滅；若王的證詞不正確，則作案時間發(fā)生在午夜前：午夜時屋里燈光滅了.試問盜竊錄音機的是李還是王，并證明你的結論。p：李盜竊了錄音機；r：作案時間發(fā)生在午夜前；s：王的證詞正確；t：午夜時屋里燈光滅了.前提：pVq,pf~T,s-*t,飛~*「，飛.結論：q.證明：...CH02復習題§2.1例2.1（3）將命題“若李一的成績比王二高，王二的成績比吳三高，那么李一的成績比吳三高”用0詞符號化。H(x,y)x的y高，a：李一，b：王二，c:吳三則命題可符號化為H(a,b)AH(b,c)H(a,c)§2.1例2.4(4)F(x)x是素數(shù)，G(x)x是奇數(shù)則命題可符號化為x(F(x)AG(x))x(F(x)G(x))14分)給定解釋I，對一階邏輯合式公式中每個 出現(xiàn)的 指定 中的一個元素，稱作在 下的賦值。(自由個體變項個體域解釋I)§2.2下面的一階邏輯合式公式 不是閉式。(D有自由出現(xiàn))Ax(F(x)G(X))By(F(x,y)G(x))CxF(x)yG(y)DxF(x,y)yG(y)§2.2下面各種敘述， 不正確。(C例2.8(5))也町改造成正誤判斷A在給定的解釋和賦值卞，任何一階邏輯合式公式都是命題VP45-B閉公式的真值與賦值無關，只需要給定解釋C非閉式的公式的真值只與賦值有關D可滿足式可能是邏輯有效式§2.3在四個合式公式

(尸(x)T(G(y)/\〃(尤y)))、Vx(尸(x)T3y(G(y)人〃(x,y)))、V4(F3"(X))「丑(尸323)中共有 個是前束范式。(參考答案：A)A2 B3 C1 D0(*參考答案:B)已知F(x)亠>王丫(必3人F(x)),Gi(x)二Vxr(MCY)A 尸3),G：(x)二G3(X)*XW3T「F3),則在G：(x)、G,x)和Gs(x)中，有 個是F(x)的前束范式A0 B3 C2 D1例2.11(3)xF(x)G(x)解：xF(x)G(x)xF(x)xG(x)(蘊涵等值式)xF(x)xG(x)(量詞否定等值式)xF(x)G(x))(量詞分配等值式)解法2：xF(x)G(x)

xF(x)yG(y)(換名規(guī)則)x(F(x)yG(y))(量詞擴xyF(x)G(y))(量詞擴TH2.2⑵④)/3xF(x)G(x)F(y)G(x))/§2.4例2.17設個體域D={a,b}t消去公式x(F(x)AyG(y))中的量詞。CH03復習題判斷(1分/每小題)若集合A={1,{1,2},3},則2A若集合B={2,{a,b}},則{a,b}B(X)

(X)單選(2分/每小題)下面的集合算式 AA-(BUC)=A-B)U(A-C)BA_B=AA?B

CAADABA-B=已知B={{a,b},c},則|P(A)|= .(VP(A)={,{c},{{a,b}},B},AA)A|{,{c},{{a,b}},B}| B2 C3 D8填空(2分/每小題)若|P(A)|=128,則|A|= .(V|P(A)|=27/A7)設A={lz33}>貝'J|A|= .VA={1,3}???2)計算(8分/每小題)某班有48個學生，第一次作業(yè)優(yōu)秀7人，第二次作業(yè)優(yōu)秀6人，兩次作業(yè)都沒得優(yōu)秀的41人，求兩次作業(yè)都得優(yōu)秀的人數(shù)。(求解過程參見[例3.12],參考答案：6)解：用A、B分別表示第一次和第二次作業(yè)優(yōu)秀的人數(shù)集合，E為某班全則：|E|=48,|A|=7,|B|=6,|?AC?B|=41|?AC?B|=|E卜(|A|+|B|)+|ADB||ADB|=41-48+(7+6)=6己知A二{{a,b},c,d},B={c,d},計算ADB、AUB、A-B、AB。(P74-3.13(l))畫圖畫(AC?B)U(C-B)的文氏圖。(3.15(3))證明：(AC?B)U (C-B)=(AUC)一B證：左式二(AC?B)= U(CH?B)

(3.27/差交運算轉換)(AUC)Cl?B=(AUC)-B

(3.8/分配律)(3.27/差交運算轉換)離散CH04復習J判斷（1分/每小題）§4.11.AAXAA2.若集合B={2,{a,b}},則{a,b}B（X）

（V）單選（2分/每小題）§4.13.A是任意集合，{〈x,x>|xA}稱作 關系。（???恒等關系蘊含其是A上的???B）A空4. 設A={a,b,

B恒等 C全域 DA上的R={<a,a>,<a,b>,<b,b>,<b,c>,<c,a>,<c,b>},則 是R的關系矩陣。（參見P80-,參考答案：（A）BCD設S={1,2,3,4},R是S上的關系，其關系矩陣是，R的關系圖中有_個環(huán)A1 B3 C6 D7填空（2分/每小題）§4.1A、B是任意兩個集合，若|A|=m,|B|=n,貝lJ|P（AXB）|= 。 （）設A是任意集合，|A|=n,則A上有 個不同的二元關系。（,|AXA|=n2）§4.5R是集合A上的等價關系，如果有序對<a,b>R,則記作 。（a?b）若R是集合A上的偏序關系，則可將此偏序關系簡記作;有序對<x,y>,可記作 o（ab）計算（8分/每小題）§4.210. 己知關系R={<2,{2}>,<{2},{2,{2}}>},求RR、R{2}、R[{2}].（同例4.7理解定義4.9）解：RR={<2,{2,{2}}>}R⑵={<2,{2}>}限制R[{2}]=ran（R{2}）=ran{<2,{2}>}={{2}}像集11. 已知人*,b,c,d},RiR2ARx={<a,a>,<a,b>,<b,d>},R2={<a,d>,<b,c>,<b,d>,<c,b>}R2R1解：V<a?a>Ri<a,d>R2,<a,d>R2Ri<a,b>Ri<b,0R2,0R2R1<a,b>Ri<b,d>R2,??<a,d>R2Ri故R2Ri={<a,d>,<a,0}證明題綜合：§1§3§4關系性質的定義12.ARiR2RLAR2證明：參見主教材P87-AP（A）R是偏序關系證明：xP(A),都有xx-<x,x>R???R是自反的<x,y>RAxHyxyAxHyxy (集合包含關系的定義)yx<y,x>R(包含關系的定義)/.R是反對稱的x、t、yP(A),?<x,t>RA<t/y>RxtAtyR的定義)xy<x,

(集合運算律)(關系R的定義)...R是傳遞的RR的自反閉包「(R)s(R)t(R)?15.畫<{1234567,8},R整除〉的哈斯圖。16.fN-N,是否是滿射、單射、雙射，為什么?f的對應關系圖如右，由圖可知1ff是單射。離散 CH05選擇一個最合適的答案1?下圖中的邊亠租邊序列『：eoeie2e3e4e5稱為 。(A)D復雜通路2?卞面有向圖中的頂點序列VoViV2V3V4V2V5稱為 o(C)A路徑 B初級通路 C簡單通路 D復雜通路 能構成圖的度數(shù)序列。(C)A(3,3,2,1)B(2,3,2)C(1) D(3,3,3)填空：設G(V,E)是n階有向簡單圖，若u,膽V,都有 ,則稱G是n階有向完全圖。(<—v>eEA<v,u>eE)G(V,E)是n階有向完全圖，通常記為 o(K,,)在下面的有向圖中，從V2到V2的長度為2的初級回路是 °vevev2411237?在下面的無向圖中，頂點 是割點，邊 是橋。(璉)(e)38?設G是有向圖或無向圖，稱p(G)是圖G的 o(連通分支個數(shù))簡答(6分每小題)§5.29. 下面三個無向圖，它們之間哪些同構，哪些不同構。若不同構，為什么？若同構，請建立頂點之間的雙射。2GiG2不同構，因為圖$G2存在度不相同的頂點?！?分同理2

G3.GiG3

...2分

...2分4°^^0B建立頂點之間的如下對應關系f: 3-C,4-*f是雙射，并且兩圖的邊也一一對應。R 10?無向圖的（點）著色：P132-例5.5 R 11圖強連通，圖單向連通，圖弱連通，圖非連通。必 D D2 3參考答案：D2、6.D4、DJ12?應用題P133-[例5.6]離散 CH06選擇一個最合適的答案1. 下面三種說法，其中不正確的有個。（C條件）①Hall定理是二部圖G（V“V.E）存在完備匹配的充要條件②無論是有向圖還是無向圖，都有判斷其是否存在歐拉通路和歐拉回路的充要條件③目前只有判斷哈密頓圖的充分條件A0 B3 C1 D22.

下面（A）四種說法，其中正確的有 個。②存在是歐拉圖不是哈密頓圖的無向圖①存在既是歐拉圖又是哈密頓圖的無向圖③存在不是歐拉圖卻是哈密頓圖的無向圖

④存在既不是歐拉圖又不是哈密頓圖的無向圖D1填空§6.13.用GM,Q表示二部圖G,|X|=n,|V2|=m,記號表示圖G為 （完全二部圖）§6.44 若圖G畫在平面上使得除頂點處外沒有

G為平面圖。（邊交叉）5?卞面的平面圖共有 個面，其中無限面Ro的次數(shù)deg（Ro）= (3,8)平而圖6-1

o(9)應用題：

非連通平而圖6-2P151-習題6.5 （二部圖的應用）P151-6.15（哈密頓圖的應用）P152-6.18（歐拉通路或歐拉回路的應用）*P152-6.23（平面圖在作色中的應用）離散CH07復習J§7.1P165-I12設n階連通無向圖G（V,Q有m條邊，G的生成樹有 條邊。（n-1,m-n+l）P167-7.54個頂點非同構無向樹。（2種）P173-7.16（3）4個頂點非同構的根樹（4種）

條邊，余樹有下面三條敘述中有