中南大學(xué)離散數(shù)學(xué)復(fù)習(xí)資料(習(xí)題)

PAGEPAGE4離散數(shù)學(xué)課程測(cè)試題判斷（）1.若wffA是可滿足式，那么~A是矛盾式。（）2.P=>P∨Q是合適公式。（）3.x(A(x)→B)→(xA(x)→B)是重言式。（）4.可滿足式的代入實(shí)例一定是可滿足式。（）5.wffA(P)=P的對(duì)偶式為~P。（）6.若A*和B*是wffA和B的對(duì)偶式，且A=>B，則A*=>B*。（）7.重言式的主析取范式為T。（）8.空集是非空集合的一個(gè)元素。（）9.設(shè)A和X是集合，則X∈2AiffXA。（）10.設(shè)A、B、C和D是四個(gè)非空集合,且A×CB×D，則AB且CD。（）11.傳遞關(guān)系的對(duì)稱閉包仍是傳遞的。（）12.非空集合上的關(guān)系不是對(duì)稱的，則必是反對(duì)稱的。（）13.若R和S是二個(gè)有完全相同的二元組的集合，則稱它們是相等的二元關(guān)系。（）14.設(shè)Ａ是一個(gè)非空集合，則Ａ上的等價(jià)關(guān)系都不是偏序關(guān)系。（）15.有限集上的全序關(guān)系必是良序關(guān)系。（）16.有限集上的偏序關(guān)系必是全序關(guān)系。（）17.<A;R>是偏序集，則Ａ的任何非空子集必有極小元。（）18.<A;R>是偏序集，則Ａ的非空子集Ｂ的上確界必是Ｂ的最大元。（）19.<A;R>是全序集，則Ａ的任何非空子集必有唯一極小元。（）20.<A;R>是全序集，則Ａ的非空子集Ｂ的下確界必是Ｂ的最小元。（）21.無限集必與它的真子集等勢(shì)。（）22.若AB，且A與B等勢(shì)，則B是無限集。（）23.若AB，則#A<#B。（）24.連通的4度正則圖一定沒有橋。（）25.p階圖的直徑不可能等于p。選擇（）1.是wff（P→Q）∧R∧(S→(P→Q))的代入實(shí)例的有 ①P∧R∧(S→P) ②(~P→Q)∧~R∧(~S→(~P→Q)) ③(P→Q)∧S∧(R→(P→Q)) ④(P→Q)∧R∧(R→(P→Q))（）2.與公式x((P(x)∧yQ(y))∧zR(z))→S(t)等價(jià)的有： ①u((P(u)∧yQ(y))∧zR(z))→S(t) ②u((P(u)∧uQ(u))∧zR(z))→S(t) ③u((P(u)∧uQ(u))∧uR(u))→S(t) ④u((P(u)∧uQ(u))∧uR(u))→S(u)（）3.下列關(guān)系中正確的有： ①{a}∈{a,{a}} ②{a}{a,{a}} ③{a}∈{a,{{a}}} ④{a}{a,{{a}}} ⑤{a}∈{{a},{{a}}} ⑥{a}{{a},{{a}}}（）4.設(shè)A=P(P(P(Φ)))，下列關(guān)系式中正確的有： ①Φ∈A ②ΦA(chǔ) ③{Φ}∈A④{Φ}A ⑤{{Φ}}∈A ⑥{{Φ}}A（）5.下列說法中正確的有：①任何集合都不是它自身的元素②任何集合的冪集都不是空集③若Ａ×Ｂ＝Φ，則Ａ＝Ｂ＝Φ④任意兩集合的笛卡爾積都不是空集（）6.{1,2,3,4,5}上的關(guān)系R={<1,1>,<1,3>,<2,3>}是①自反的②反自反的③對(duì)稱的④反對(duì)稱的⑤傳遞的（）⒎空集上的空關(guān)系是關(guān)系。①相容②等價(jià)③偏序④擬序⑤良序（）⒏集Ａ={0,1}上的恒等關(guān)系ＩA是關(guān)系。①相容②等價(jià)③偏序④擬序⑤良序（）⒐{1,2,3,4,5}上的全關(guān)系是關(guān)系。①相容②等價(jià)③偏序④擬序⑤良序（）⒑{1,2,3,4,5}上的全序關(guān)系一定是關(guān)系。①相容②等價(jià)③偏序④擬序⑤良序（）11.{1,2,3,4,5}上的良序關(guān)系一定是①自反的②反自反的③對(duì)稱的④反對(duì)稱的⑤傳遞的（）12.設(shè)Ｒ和Ｓ都是Ａ到Ｂ的關(guān)系，則下列關(guān)系式中正確的有：①(Ｒ∪Ｓ)-1＝Ｒ-1∪Ｓ-1②(Ｒ∩Ｓ)-1＝Ｒ-1∩Ｓ-1③(Ｒ－Ｓ)-1＝Ｒ-1－Ｓ-1④(Ｒeq\o\ac(○,＋)Ｓ)-1＝Ｒ-1eq\o\ac(○,＋)Ｓ-1（）13.函數(shù)f：Ｒ×Ｒ→Ｒ×Ｒ，f(<x,y>)=<x+y,x-y>是①入射②滿射③雙射④以上答案都不對(duì)（）14.設(shè)Σ={a,b}為字母表，則f：Σ*→Σ*，f(x)=axb是①入射②滿射③雙射④以上答案都不對(duì)（）15.若f、g是Ａ上的函數(shù)且g·f是雙射，則①f和g都是雙射②f為滿射③g為入射④f有左逆 ⑤g有右逆（）16.設(shè)p階圖G不含圈，且恰有p-1條邊（p≥2），則①G連通 ②G的任一邊都是橋③G是樹 ④加入任一邊，G便含圈（）17.下列序列中，有哪個(gè)（些）不可能是一棵樹的度序列： ①(1,1,2,2,2,2,2,2) ②(1,1,1,2,2,2,2,3) ③(1,1,2,2,2,2,3,3) ④(1,1,1,1,4,4,4,4)填空1.公式A(P,Q,R)=Q∧R∨P∧R∨T∧~P∧R的對(duì)偶式為A*=。2.若公式A(P,Q,R,S)的主析取范式為∑1,3,4,5,7，則A的主合取范式為∏。3.給命題變?cè)狿和Q指派真值T，R和S指派真值F，公式P∨(Q→R∧~P)→~Q∨S的真值為。4.量詞表示“有且僅有”，xP(x)表示恰好有一個(gè)個(gè)體滿足謂詞P。那么用量詞，及等號(hào)“=”表示謂詞后得到的公式__________與xP(x)有相同的意義。5.若用謂詞I(x)表示“x是整數(shù)”，E(x)表示“x=y”，G(x,y)表示“x>y”，那么命題“對(duì)任何整數(shù)x和y，x≤y且y≤x是x=y的充要條件”的謂詞表達(dá)式為：。6.給定論域D={1，2}和謂詞P：P(1,1)=T，P(1,2)=F，P(2,1)=F，P(2,2)=T，公式xy(P(x,y)→P(y,x))的真值為。7.若集Ａ={1,2,3,4}上的關(guān)系Ｒ={<1,2>,<2,3>,<3,4>}，Ｓ={<2,4>,<1,2>,<3,1>}，則dom(Ｒ·Ｓ)=。8.若A={a,b}，B={1,2}，則BA=。9.用ε表示字母表Σ={a,b}上的空串，定義f：Σ*→Σ*如下：x∈Σ*f(x)=axb則f({ε,a,b})=。10.用ε表示字母表Σ={a,b}上的空串，定義f：Σ*→Σ*如下：x∈Σ*f(x)=axb則f()={aab,abb,ab}。11.在集Ａ={1,2}上可定義兩個(gè)不同的等價(jià)關(guān)系，它們是和。12.若Ｒ為集合Ａ上的等價(jià)關(guān)系，ab，那么等價(jià)類[a]R和[b]R的交[a]R∩[b]R=。13.若G是p階k度正則圖，則它有條邊，它的補(bǔ)圖有條邊。14.考慮下圖，它含有_________等割點(diǎn)，___________等橋（列出具體的頂點(diǎn)和邊）。VV2V4 V4V5V1V5V1V3 V3四、計(jì)算與作圖1.若集合Ａ={1,2,3,4}上的關(guān)系Ｒ={<1,1>,<2,3>,<3,2>,<3,4>,<4,1>}。請(qǐng)用集合列舉表示法表示r(Ｒ)、用關(guān)系圖表示s(Ｒ)，用關(guān)系矩陣表示t(Ｒ)。2.設(shè)R和S都是{1,2,3,4,5}上的二元關(guān)系，且R={<2,4>,<4,1>,<3,5>,<5,3>}，S={<1,2>,<3,4>,<5,2>}，則R·S=，R2=，t(R)=。3.設(shè)Ａ={3,6,9,15,54,90,135,180}，｜為自然數(shù)的整除關(guān)系。畫出<Ａ;｜>的Ｈasse圖，并求{6,15,90}的上、下確界。4.設(shè)Ａ＝{a,b},Ｂ＝{1,2,3,4}，f＝{<a,1>,<b,2>}是Ａ到Ｂ的函數(shù)，試找出f的所有左逆和右逆(如果存在的話)。5.設(shè)Ａ＝{1,2,3,4,5},Ｂ＝{a,b}，f＝{<1,a>,<2,a>,<3,b>,<4,a>,<5,b>}是Ａ到Ｂ的函數(shù)，試找出f的所有左逆和右逆(如果存在的話)。6.定義Ａ＝{1,2}×{1,2,3}上的等價(jià)關(guān)系Ｒ如下：<x,y>,<u,v>∈Ａ，<x,y>Ｒ<u,v>iffx+y=u+v。求出商集Ａ/Ｒ。7.設(shè)Ａ＝{1,2}，定義ＡＡ上的等價(jià)關(guān)系Ｒ如下：f,g∈ＡＡ，fＲgifff(A)=g(A)。試求出商集ＡＡ/Ｒ。8.某班級(jí)成立了三個(gè)運(yùn)動(dòng)隊(duì)：籃球隊(duì)、排球隊(duì)和足球隊(duì)。今有張、王、李、趙、陳5名同學(xué)，若已知張、王為籃球隊(duì)員；張、李、趙為排球隊(duì)員；李、趙、陳為足球隊(duì)員，問能否從這5人中選出3名不兼職的隊(duì)長(zhǎng)？圖示出所有不同構(gòu)的六階樹。10.找出下圖的一個(gè)最小生成樹。bbcad546036388404820452815383062251210hgef五、證明題1.A→(B→C),C∧D→E,~P→D∧~E=>A→(B→P)2.判斷下列公式是不是永真式，并加以說明：(xP(x)→xQ(x))x(P(x)→Q(x))3.設(shè)A、B是兩個(gè)集合，證明：ABiffP(A)P(B)4．設(shè)U是全集，對(duì)U的任何子集A定義A的特征函數(shù)ΧA如下：0x0xA1xAΧA：U{0,1} ΧA(x)= 證明：f(A)=XA