華中科技大學(xué)2021年《離散數(shù)學(xué)》期末試題及答案

一、判斷題(本大題共10小題，每小題1分，共10分)1、階大于1的樹都是二部圖。（T ）2、xP(x)∧xQ(x)=>x(P(x)∧Q(x))（F ）3、空集是任何集合的子集。（T ）4、若R和S是自反的，則RS是自反的（T ）5、若R和S是對稱的，則RS是對稱的（F ）6、任何一個合式公式都可以化簡為只含邏輯運算符┐和∧的形式。（T ）7、若無向圖中恰有兩個度為奇數(shù)的結(jié)點，則這兩個結(jié)點必相互可達(dá)。（T ）8、<S，*>是獨異點。T={x|x∈S,x*x=x}，<T，*>也是獨異點（F ）9、任何一棵階不小于2的樹中至少有兩片樹葉（T ）10、n階連通無向圖至少有n條邊（F ）二、單向選擇與填空題(本大題共20小題，每小題2分，共40分)1、關(guān)于命題變元P1,P2,…,Pn的指派共有（B ）種A、2n B、2n C、n2 、22n2、設(shè)P：我將去鎮(zhèn)上Q：我有時間。命題“我將去鎮(zhèn)上，僅當(dāng)我有時間”符化為（A ）A、PQ B、QP CPQ D3、下面哪一個命題是假命題（B ）

QPA2是偶數(shù)，那么一個公式的主析取范式唯一2是偶數(shù)，那么一個公式的主析取范式不唯一C2是奇數(shù)，那么一個公式的主析取范式唯一D24、下列各式中不正確的是（C ）A、x(P(x)∨Q(x))xP(x)∨xQ(x)B、x(P(x)∧Q(x))xP(x)∧xQ(x)C、x(P(x)∨Q(x))xP(x)∨xQ(x)D、x(P(x)∧Q)xP(x)∧Q5、若公式的主合取范式為∏0145，則公式的主析取范式為（C ）A、∑（0，1，4，5） 、∏（0，1，4，5）C、∑（2，3，6，7） D、∏（2，3，6，7）6A={a,{a}},下列選項錯誤的是（B）A、{a}P(A) B、{a}P(A) C、{{a}}P(A) D、{{a}}P(A)7、設(shè)集合A={a,b,c},R是A上的二元關(guān)系，R={<a,a>,<a,b>,<a,c>,<c,a>,<c,c>}，則R是（C ）A、反自反的 、反對稱的 C、可傳遞的 D、不可傳遞的8、R是反對稱的當(dāng)且僅當(dāng)（D ）A、IAR 、{a} R∩IA=ф C、R=R-1 D、R∩R-1IA9、任何無向圖中結(jié)點間的可達(dá)系是（ B ）A、偏序關(guān)系 B、等價關(guān)系 C、相容關(guān)系 D、擬序關(guān)系10、設(shè)集合A={a,b,c}，則A上可以形成（C ）種不同的等價關(guān)A、3 、4 C、5 D、6、Z是整數(shù)集合，Z+表示非負(fù)整數(shù)集合，函數(shù)f定義為：Z(x)=|x|，f是（ B ）A、單射 、滿射 C、雙射 D、恒等12、設(shè)N是自然數(shù)集合，f和g是N到N的函數(shù)，且f(n)=2n+1,g則復(fù)合函數(shù)f。g(n)=(C )A、n4 、4n+3 C、2n2+1 D、(2n+1)213、R是實數(shù)集，*為普通乘法，則<R,*>不能構(gòu)成（C ）A、半群 、獨異點 C、群14、若簡單連通平面圖G有4個結(jié)點，3個面，則G有（C ）邊A、3 B、4 C、5 D、215一棵樹有兩個2度頂點一個3度頂點三個4度頂點則該樹（D 片樹葉A、2 B、7 C、8 D、9設(shè)A={1，2，3}，B={a,b,c},則從A到B有 6 個不同的雙射函數(shù)。11階的群有 2 個不同的子群。L（x）:x.G(x):x是金子。命題“閃光的未必是金子”符號化為┐ x(L(x)→G(x)) 。19、設(shè)A中有n個元素，則A上有 2n 個不同的既是對稱的又是反對稱的二元關(guān)系。2、設(shè)A是非空有限集，代數(shù)系統(tǒng)（，∪，∩）中（）對∪運算的元是 A ，P（A）對∩運算的單位元（么元）是 A三、證明題(共20分)1（10分）請將下列命題符號化，并進(jìn)行形式證明每個智力正常并且勤奮的人都可以獲得成功,有些人不曾獲得過成功,所以有些人智力不正?；蛘卟磺趭^。（注：設(shè)個體域為全體人的集合Z(x): x智力正常；Q(x):x勤,S(x):x獲得成功）2（10分）<G,*>a∈GH={y|y*a=a*y證明:<H,*>是<G,*>的子群。四、計算及作圖題(共30分)1（10分）F=P∧

Q∨P∧Q∧R的主析取范式和主合取范式。2（10分）A={a、b、c}AA的所有劃分構(gòu)成的集合P，畫出<P，細(xì)分〉的哈斯圖。3（10分