《離散數(shù)學(xué)（微課版）》期末試卷（含答案）

學(xué)院系別姓名學(xué)號………密………封………線………以………內(nèi)………答………題………無………效……第5頁共6頁電子科技大學(xué)二零二至二零二學(xué)年第二學(xué)期期末（B卷）課程考試題（分鐘）考試形式：考試日期年月日一二三四五六七八九十總分評卷教師一、選擇題（1～15是單選，16～20是多選，單選每小題1分，多選每小題2分，共計(jì)25分）1.下列公式中，那一個是永假的（ ）。 A、(P∧Q)→P B、(P∨Q)→P C、P→(P∨Q) D、((P∧Q)→Q）2.下列公式中，哪一個不是析取范式（ ）。 A、P∨Q B、P∧Q C、(P∨Q) D、(P∧Q)3、如果命題公式G=P∧Q，則下列之一哪一個等價(jià)（）。A、G=(P→Q) B、G=(P∨Q) C、G=(P→Q) D、G=(P→Q)4、設(shè)X、Y是兩個集合|X|＝m，|Y|＝n，則從X到Y(jié)可產(chǎn)生（）個不同的函數(shù)。A、nm B、mn C、m×n D、2m×n5、設(shè)G是具有n個結(jié)點(diǎn)的有向完全圖，則G中有（）條邊。A、n2 B、n(n－1) C、2n(n－1) D、6、下列公式中，是永真式的是()。A、P∨1 B、P→T C、P∨T D、P∧T7、下列公式中，（）是析取范式。A、(P∧Q) B、(P∨Q) C、(P∨Q) D、(P∧Q)8、下面哪一種格不是特殊格（）。A、子格 B、分配格 C、模格 D、有界格9、5個結(jié)點(diǎn)7條邊的簡單圖共有（）種。A、2 B、3 C、5 D、710、下列圖中，（）是平面圖。 A、B、 C、 D、11、每個無向樹至少有（）片樹葉。A、1B、2 C、3 D、412、每個無限循環(huán)群有（）個生成元。A、1 B、2 C、3 D、413、設(shè)R是集合A＝{1,2,3}上的二元關(guān)系，R＝{<2,1>,<2,3>,<1,3>},則下列（）不成立。A、R是自反關(guān)系 B、R是反自反關(guān)系 C、R是反對稱關(guān)系 D、R是傳遞關(guān)系14、設(shè)G是一個18階群，a是G中任意一個元素，則a的周期一定不是（）。A、2 B、4 C、9 D、615、命題公式A與B是等價(jià)的，是指（D）。A、A與B有相同的原子變元 B、A與B是可滿足的C、當(dāng)A的真值為真時，B的真值也為真 D、A與B有相同的真值16、設(shè)R、S是集合A上的關(guān)系，則下述（ ）不一定成立。A若R、S傳遞，則傳遞 B若R、S對稱，則對稱C若R、S自反，則自反 D若R、S反自反，則反自反5142376E若514237617、下列圖中，那些是右圖的強(qiáng)分圖。（）1423142314231436565A B C D E18、下列圖中，存在完美匹配的圖是（）19、下列哈斯圖中，不是格的有（）。 A B C D E20、若<G,*>是一個群，則運(yùn)算“*”不一定滿足（）。A、交換率 B、消去律 C、冪等律 D、分配律二、名詞解釋（每小題3分，共15分）1、什么叫謂詞公式的解釋。2、試述函數(shù)中滿射函數(shù)的定義。3、敘述極大連通分支的定義。4、試述代數(shù)系統(tǒng)中子代數(shù)的定義。5、試述格的定義三、判斷分析改錯題（每小題5分，共10分）1、設(shè)<Z，+>是一個代數(shù)系統(tǒng)，Z是正整數(shù)集合，“＋”是一般的加法運(yùn)算，Z上的函數(shù)f為：f(x)=5x-7，則函數(shù)f能構(gòu)成代數(shù)系統(tǒng)的自同構(gòu)嗎？為什么？2、設(shè)A，B，C為任意命題公式。已知，問嗎？bacdefgbacdefg1、設(shè)集合A＝｛a,b,c,d,e,f,g｝上的偏序關(guān)系如右圖所示,求A的最大元、最小元、極大元和極小元，并求A的子集B＝｛a,b,c,d｝的上確界和下確界。2、設(shè)個體域D={a,b,c}，消去以下各式中的量詞：（1）；（2）3、求命題公式(PQ)R的主析取范式和主合取范式。4、設(shè)是群，運(yùn)算“”定義如下：，有：試驗(yàn)證該代數(shù)系統(tǒng)是否是一個循環(huán)群？如是，請求出該循環(huán)群的全部生成元，幺元，每個元素的逆元。五、綜合證明題（共18分）將下面的推理符號化，然后用邏輯推理的方法證明之。 1、每個在學(xué)校讀書的人都獲得知識。所以如果沒有人獲得知識就沒有人在學(xué)校讀書。（個體域是人的集合）。2、設(shè)<G,*>是群，H，K是其子群，在G上定義二元關(guān)系R：使得。證明：R是G上的等價(jià)關(guān)系.答案1～15是單選，16～20是多選，單選每小題1分，多選每小題2分，共計(jì)25分）1.D2.C3、B4、A5、B6、A7、D8、B9、B10、C11、A12、B13、A14、B15、D16、A,E17、D,E18、D19、A,B,E20、A,C,D二、名詞解釋（略）三、判斷分析改錯題（每小題5分，共10分）1、答：不是。顯然，Z上的函數(shù)f既是單射又是滿射。但是對，有顯然，，即不滿足同態(tài)條件，因此函數(shù)f不能構(gòu)成代數(shù)系統(tǒng)的自同構(gòu)2、設(shè)A，B，C為任意命題公式。已知，問嗎？答：不一定。因?yàn)楫?dāng)，時，有同樣的真值T，此時，成立，但是，卻不成立。四、計(jì)算題（每小題8分，共32分）1、最大元最小元極大元極小元上界下界上確界下確界gdgdgdgd2、解：（1）（2）3、解：方法1PQRP→Q(P→Q)R0001000111010100111110001101001101011111主析取范式為（使公式為1的解釋所對應(yīng)的極小項(xiàng)的析?。?P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式為（使公式為0的解釋所對應(yīng)的極大項(xiàng)的合取）：(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)方法2：(P→Q)R=((P→Q)→R)∧(R→(P→Q))=((P→Q)∨R)∧(R∨(P→Q))=((P∨Q)∨R)∧(R∨P∨Q)=(((P)∧Q)∨R)∧(P∨Q∨R)=((P∧Q)∨R)∧(P∨Q∨R)=(P∨R)∧(Q∨R)∧(P∨Q∨R)=(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)∧(P∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) 主合取范式=M0∧M2∧M5∧M6=m1∨m3∨m4∨m7=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) 主析取范式4、證明：a,b∈I，顯然a*b=a+b+2∈I，所以“*”關(guān)于I是封閉的。a,b,c∈I,(a*b)*c=(a*b)+c+2=(a+b+2)+c+2=a+(b+c+2)+2=a+(b*c)+2=a*(b*c),所以“*”是可結(jié)合的。存在-2∈I，使得a∈I，都有(-2)*a=a*(-2)=a+(-2)+2=a，所以-2是<I,*>的幺元。a∈I，存在-a-4∈I，使得a*(-4-a)=(-4-a)*a=a+(-4-a)+2=-2，所以-4-a是a的逆元。故<I,*>是群。設(shè)a是<I,*>的生成元，則存在i,j∈I,使得1＝ai＝ia+2(i-1)，2＝aj＝j(luò)a+2(j-1)，所以1＝2-1=ja+2(j-1)-(ia+2(i-1))=a(j-i)+2(j-i)，所以，因?yàn)閍∈I，所以j-i＝1或j-i＝-1，即a＝-1或a＝-3。當(dāng)a＝-1時，x∈I，存在x+2∈I，使得x=(-1)x+2。當(dāng)a＝-3時，x∈I，存在-x-2∈I，使得x=(-3)-x-2。故<I,*>是循環(huán)群，全部生成元為-1和-3，幺元為-2，每個元素a的逆元為-4-a。五、綜合證明題（共18分）將下面的推理符號化，然后用邏輯推理的方法證明之。 1、解：設(shè)f(x)：x是在學(xué)校讀書；g(x)：x獲得知識，則句子可以符號化為：證明：使用CP規(guī)則。P（附加前提）T,(1),EUS,(2)PUS,(4)T,(3),(5),IUG,(6)T,(7),E2、證明：①a∈G，因?yàn)?lt;G,*>是群，存在e∈G，使得a=e*a*e-1，由已知得<a,a>∈R，所以R是自反的。②a,b∈G，若<a,b>∈R，則存在Q,H∈G使得b=Q