離散數(shù)學(xué)自測題及答案一、選擇題1.設(shè)集合$A={1,2,3}$，$B={2,3,4}$，則$AcapB$等于（）A.${1,2,3,4}$B.${2,3}$C.${1,4}$D.$varnothing$答案：B分析：交集是由所有既屬于集合$A$又屬于集合$B$的元素所組成的集合，$A$和$B$中共同元素是$2$和$3$，所以$AcapB={2,3}$。2.下列命題中，為真命題的是（）A.$plandnegp$B.$plornegp$C.$neg(plorq)$D.$negplandnegq$答案：B分析：根據(jù)邏輯運(yùn)算規(guī)則，對于任意命題$p$，$p$與$negp$必有一個為真，所以$plornegp$恒為真，這是排中律；而$plandnegp$恒為假；$neg(plorq)$等價于$negplandnegq$，其真假取決于$p$和$q$的取值。3.設(shè)$R$是集合$A$上的自反關(guān)系，則（）A.對于任意$ainA$，$(a,a)notinR$B.存在$ainA$，$(a,a)inR$C.對于任意$ainA$，$(a,a)inR$D.存在$ainA$，$(a,a)notinR$答案：C分析：自反關(guān)系的定義是對于集合$A$中的任意元素$a$，都有$(a,a)inR$。4.設(shè)函數(shù)$f:NtoN$（$N$為自然數(shù)集），$f(n)=2n$，則$f$是（）A.滿射但不是單射B.單射但不是滿射C.雙射D.既不是單射也不是滿射答案：B分析：單射是指不同的自變量對應(yīng)不同的函數(shù)值，對于$f(n)=2n$，若$f(n_1)=f(n_2)$，即$2n_1=2n_2$，可得$n_1=n_2$，所以是單射；滿射是指值域等于陪域，$f$的值域是偶數(shù)集，是自然數(shù)集$N$的真子集，所以不是滿射。5.公式$forallx(P(x)toQ(x))$中，$forallx$的轄域是（）A.$P(x)$B.$Q(x)$C.$P(x)toQ(x)$D.$forallx(P(x)toQ(x))$答案：C分析：量詞的轄域是指該量詞所作用的范圍，在$forallx(P(x)toQ(x))$中，$forallx$作用的范圍是$P(x)toQ(x)$。二、填空題1.設(shè)集合$A={a,b,c}$，則$A$的冪集$P(A)$的元素個數(shù)為______。答案：8分析：若集合$A$中有$n$個元素，則其冪集$P(A)$的元素個數(shù)為$2^n$，$A$中有$3$個元素，所以$P(A)$的元素個數(shù)為$2^3=8$。2.命題公式$(ptoq)landp$的主析取范式為______。答案：$plandq$分析：先將$(ptoq)landp$化簡，$ptoq$等價于$negplorq$，則$(ptoq)landp$等價于$(negplorq)landp$，根據(jù)分配律可得$(negplandp)lor(qlandp)$，因為$negplandp$為假，所以結(jié)果為$plandq$。3.設(shè)集合$A={1,2,3}$上的關(guān)系$R={(1,2),(2,3)}$，則$R$的傳遞閉包$t(R)$為______。答案：${(1,2),(2,3),(1,3)}$分析：傳遞閉包是包含$R$且滿足傳遞性的最小關(guān)系。因為$(1,2)inR$且$(2,3)inR$，根據(jù)傳遞性可得$(1,3)$也應(yīng)在傳遞閉包中，所以$t(R)={(1,2),(2,3),(1,3)}$。4.設(shè)圖$G$有$n$個頂點，$m$條邊，且$G$是連通圖，則$m$與$n$的關(guān)系滿足______。答案：$mgeqn-1$分析：對于連通圖，至少需要$n-1$條邊才能保證連通，所以$mgeqn-1$。5.設(shè)$G$是群，$ainG$，$|a|$表示元素$a$的階，若$|a|=5$，則$|a^3|$為______。答案：5分析：設(shè)$|a^3|=k$，則$(a^3)^k=e$（$e$為群的單位元），即$a^{3k}=e$。因為$|a|=5$，所以$5$是使得$a^n=e$成立的最小正整數(shù)，那么$5$整除$3k$，又因為$(3,5)=1$，所以$5$整除$k$。而$(a^3)^5=a^{15}=(a^5)^3=e$，所以$|a^3|=5$。三、判斷題1.空集是任何集合的真子集。（）答案：錯誤分析：空集是任何非空集合的真子集，空集是它本身的子集，但不是真子集。2.若$ptoq$為真，則$p$為真且$q$為真。（）答案：錯誤分析：$ptoq$為真有三種情況：$p$假$q$真、$p$真$q$真、$p$假$q$假。3.關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律。（）答案：正確分析：設(shè)$R$是從$A$到$B$的關(guān)系，$S$是從$B$到$C$的關(guān)系，$T$是從$C$到$D$的關(guān)系，則$(RcircS)circT=Rcirc(ScircT)$。4.一個圖是歐拉圖當(dāng)且僅當(dāng)它的所有頂點的度數(shù)都是偶數(shù)。（）答案：正確分析：這是歐拉圖的判定定理，一個無向圖是歐拉圖的充要條件是圖是連通的且所有頂點的度數(shù)都是偶數(shù)。5.群中每個元素的逆元是唯一的。（）答案：正確分析：設(shè)$G$是群，$ainG$，假設(shè)$b$和$c$都是$a$的逆元，則$acdotb=e$，$acdotc=e$，那么$b=bcdote=bcdot(acdotc)=(bcdota)cdotc=ecdotc=c$，所以逆元唯一。四、解答題1.求集合$A={1,2,3}$到集合$B={a,b}$的所有不同的函數(shù)。解：根據(jù)函數(shù)的定義，對于集合$A$中的每個元素，在集合$B$中都有唯一的元素與之對應(yīng)。$A$中有$3$個元素，每個元素都有$2$種對應(yīng)方式。第一個元素$1$可以對應(yīng)$a$或$b$，有$2$種選擇；第二個元素$2$也有$2$種選擇；第三個元素$3$同樣有$2$種選擇。根據(jù)乘法原理，不同函數(shù)的個數(shù)為$2^3=8$個。具體的函數(shù)如下：$f_1(1)=a,f_1(2)=a,f_1(3)=a$；$f_2(1)=a,f_2(2)=a,f_2(3)=b$；$f_3(1)=a,f_3(2)=b,f_3(3)=a$；$f_4(1)=a,f_4(2)=b,f_4(3)=b$；$f_5(1)=b,f_5(2)=a,f_5(3)=a$；$f_6(1)=b,f_6(2)=a,f_6(3)=b$；$f_7(1)=b,f_7(2)=b,f_7(3)=a$；$f_8(1)=b,f_8(2)=b,f_8(3)=b$。2.用真值表法判斷命題公式$(ptoq)leftrightarrow(negplorq)$是否為重言式。解：列出真值表如下：|$p$|$q$|$ptoq$|$negp$|$negplorq$|$(ptoq)leftrightarrow(negplorq)$||---|---|---|---|---|---||0|0|1|1|1|1||0|1|1|1|1|1||1|0|0|0|0|1||1|1|1|0|1|1|從真值表可以看出，對于$p$和$q$的所有可能取值，$(ptoq)leftrightarrow(negplorq)$的真值都為$1$，所以該命題公式是重言式。3.設(shè)集合$A={1,2,3,4}$，$R$是$A$上的關(guān)系，$R={(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)}$。（1）判斷$R$是否為等價關(guān)系，并說明理由。（2）若是等價關(guān)系，求$A$中各元素的等價類。解：（1）-自反性：對于任意$ainA$，都有$(a,a)inR$，如$(1,1)$，$(2,2)$，$(3,3)$，$(4,4)$都在$R$中，所以$R$具有自反性。-對稱性：若$(a,b)inR$，則$(b,a)inR$。例如$(1,2)inR$且$(2,1)inR$，$(3,4)inR$且$(4,3)inR$，所以$R$具有對稱性。-傳遞性：若$(a,b)inR$且$(b,c)inR$，則$(a,c)inR$。經(jīng)檢驗，對于所有滿足條件的$(a,b)$和$(b,c)$，都有$(a,c)inR$，所以$R$具有傳遞性。由于$R$具有自反性、對稱性和傳遞性，所以$R$是等價關(guān)系。（2）-$[1]={xinA|(x,1)inR}={1,2}$；-$[2]={xinA|(x,2)inR}={1,2}$；-$[3]={xinA|(x,3)inR}={3,4}$；-$[4]={xinA|(x,4)inR}={3,4}$。4.設(shè)$G$是一個有$6$個頂點，$11$條邊的簡單無向圖，證明$G$中必存在度數(shù)大于等于$4$的頂點。證明：假設(shè)$G$中所有頂點的度數(shù)都小于$4$，即每個頂點的度數(shù)最大為$3$。根據(jù)握手定理，$sum_{vinV}deg(v)=2m$（其中$V$是頂點集，$m$是邊數(shù)）。因為有$6$個頂點，每個頂點度數(shù)最大為$3$，那么$sum_{vinV}deg(v)leq6x3=18$，又因為$sum_{vinV}deg(v)=2m$，$m=11$，所以$sum_{vinV}deg(v)=22$。$22>18$，這與假設(shè)矛盾，所以$G$中必存在度數(shù)大于等于$4$的頂點。5.設(shè)$G=langleZ_6,+_6rangle$是模$6$剩余類加群，求$G$的所有子群。解：根據(jù)拉格朗日定理，子群的階是群的階的因子，$|G|=6$，$6$的正因子有$1$，$2$，$3$，$6$。-當(dāng)子群的階為$1$時，子群為${[0]}$。-當(dāng)子群的階為$2$時，設(shè)子群為$H$，由元素生成，考慮元素的階，$[3]$的階為$2$，則子群$H=langle[3]rangl