2010-7自學(xué)離散數(shù)學(xué)試題.doc

全國2010年7月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個備選項(xiàng)中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1下列句子不是命題的是（）A中華人民共和國的首都是北京B張三是學(xué)生C雪是黑色的D太好了！2下列式子不是謂詞合式公式的是（）A（x）P(x)R(y)B(x) P（x）(x)(P(x)Q(x)C(x)($y)(P(x)Q(y)($x)R(x)D(x)(P(x,y)Q(x,z)($z)R(x,z)3下列式子為重言式的是（）A(PR)QBPQRRCP(PQ)D(PQ)(PQ)4在指定的解釋下，下列公式為真的是（）A(x)(P(x)Q(x),P(x):x=1,Q(x):x=2,論域:1,2B($x)(P(x)Q(x),P(x):x=1,Q(x):x=2,論域: 1,2C($x)(P(x) Q(x),P(x):x2,Q(x):x=0,論域:3,4D(x)(P(x)Q(x),P(x):x2,Q(x):x=0,論域:3,45對于公式(x) ($y)(P(x)Q(y)($x)R(x,y)，下列說法正確的是（）Ay是自由變元By是約束變元C($x)的轄域是R(x, y)D(x)的轄域是($y)(P(x)Q(y)($x)R(x,y)6設(shè)論域?yàn)?,2，與公式(x)A(x)等價(jià)的是（）AA(1)A(2)BA(1)A(2)CA(1)A(2)DA(2)A(1)7設(shè)Z+是正整數(shù)集，R是實(shí)數(shù)集，f:Z+R, f(n)=log2n ,則f（）A僅是入射B僅是滿射C是雙射D不是函數(shù)8下列關(guān)系矩陣所對應(yīng)的關(guān)系具有反對稱性的是（）ABCD9設(shè)R1和R2是集合A上的相容關(guān)系，下列關(guān)于復(fù)合關(guān)系R1R2的說法正確的是（）A一定是等價(jià)關(guān)系B一定是相容關(guān)系C一定不是相容關(guān)系D可能是也可能不是相容關(guān)系10下列運(yùn)算不滿足交換律的是（）Aa*b=a+2bBa*b=min(a,b)Ca*b=|a-b|Da*b=2ab11設(shè)A是偶數(shù)集合，下列說法正確的是（）A是群B是群C是群D, ,都不是群12設(shè)*是集合A上的二元運(yùn)算，下列說法正確的是（）A在A中有關(guān)于運(yùn)算*的左幺元一定有右幺元B在A中有關(guān)于運(yùn)算*的左右幺元一定有幺元C在A中有關(guān)于運(yùn)算*的左右幺元，它們不一定相同D在A中有關(guān)于運(yùn)算*的幺元不一定有左右幺元13題13圖的最大出度是（）A0B1C2D314下列圖是歐拉圖的是（）15一棵樹的3個4度點(diǎn)，4個2度點(diǎn)，其它的都是1度，那么這棵樹的邊數(shù)是（）A13B14C15D16二、填空題（本大題共10小題，每小題2分，共20分）請?jiān)诿啃☆}的空格中填上正確答案。錯填、不填均無分。16請寫出表示德摩根律的兩個命題公式等價(jià)定理_，_。17n個命題變元的_稱為小項(xiàng)，其中每個變元與它的否定不能同時(shí)出現(xiàn)，但兩者必須_。18前提引入規(guī)則：在證明的任何步驟上都可以_，簡稱_規(guī)則。19自由變元代入規(guī)則是指對某_出現(xiàn)的個體變元可用個體常元或用與原子公式中所有個體變元不同的個體變元去代入，且_。20設(shè)A=,B=2,4，則(A)=_，AB_。21設(shè)A=1,2,3,4, A上的二元關(guān)系R=,S=,，則R2S=_，(R-1)2=_。22設(shè)代數(shù)系統(tǒng)是環(huán)，則是_，是_。23在中，元素2的階為_，它生成的子群為_，其中7為模7乘法。24設(shè)是一個_，如果A中任意兩個元素都有_，則稱為格。25若一條_中，所有的_均不相同，稱為跡。三、計(jì)算題（本大題共6小題，每小題5分，共30分）26給定論域D=1,2，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在該賦值下，求式子$x(S( f(x)G(x, f(x)的真值。27請通過等值演算法求(PQ)(PQ)的主析取范式。28設(shè)A=1,2,3,4，給定A上二元關(guān)系R=,，求R的傳遞閉包。29對題29圖所示格，找出它的所有的4元子格。30用矩陣的方法求題30圖中結(jié)點(diǎn)ui，u5之間長度為2的路徑的數(shù)目。31求題31圖的最小生成樹。四、證明題（本大題共3小題，第32小題8分，第33、34小題各6分，共20分）32用推理方法證明(AB)(CD),(DF)EAE。33證明：設(shè)是一個群，則對于任意a,bG，必存在惟一的xG使得ax=b。34設(shè)圖G有n個結(jié)點(diǎn)，n+1條邊，證明：G中至少有一個結(jié)點(diǎn)度數(shù)3。五、應(yīng)用題（本大題共2小題，第35小題