一、單項選取題（本大題共15小題，每小題1分，共15分）在每小題列出四個備選項中只有一種是符合題目規定，請將其代碼填寫在題后括號內。錯選、多選或未選均無分。1．下列句子不是命題是（D）A．中華人民共和國首都是北京 B．張三是學生C．雪是黑色 D．太好了！2．下列式子不是謂詞合式公式是（B）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．(┐P∧R)→Q B．P∨Q∧R→┐RC．P∨(P∧Q) D．(┐P∨Q)(P→Q)4．在指定解釋下，下列公式為真是（）A．(x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,論域:{1,2}B．(x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,論域：{1,2}C．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4}D．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4}5．對于公式(x)(y)(P(x)∧Q(y))→(x)R(x,y)，下列說法對的是（）A．y是自由變元 B．y是約束變元C．(x)轄域是R(x，y) D．(x)轄域是(y)(P(x)∧Q(y))→(x)R(x,y)6．設論域為{1,2}，與公式(x)A(x)等價是（）A．A(1)∨A(2) B．A(1)→A(2)C．A(1)∧A(2) D．A(2)→A(1)7．設Z+是正整數集，R是實數集，f:Z+→R，f(n)=log2n,則f（）A．僅是入射 B．僅是滿射C．是雙射 D．不是函數8．下列關系矩陣所相應關系具備反對稱性是（）A． B．C． D．9．設R1和R2是集合A上相容關系，下列關于復合關系R1R2說法對的是（）A．一定是等價關系 B．一定是相容關系C．一定不是相容關系 D．也許是也也許不是相容關系10．下列運算不滿足互換律是（）A．a*b=a+2b B．a*b=min(a,b)C．a*b=|a-b| D．a*b=2ab11．設A是偶數集合，下列說法對的是（）A．<A,+>是群 B．<A,×>是群C．<A,÷>是群 D．<A,+>，<A,×>,<A,÷>都不是群12．設*是集合A上二元運算，下列說法對的是（）A．在A中關于于運算*左幺元一定有右幺元B．在A中關于于運算*左右幺元一定有幺元C．在A中關于于運算*左右幺元，它們不一定相似D．在A中關于于運算*幺元不一定有左右幺元13．題13圖最大出度是（）A．0 B．1C．2 D．314．下列圖是歐拉圖是（）15．一棵樹3個4度點，4個2度點，其他都是1度，那么這棵樹邊數是（）A．13 B．14C．15 D．16二、填空題（本大題共10小題，每小題2分，共20分） 請在每小題空格中填上對的答案。錯填、不填均無分。16．請寫出表達德摩根律兩個命題公式等價定理___________，___________。17．n個命題變元___________稱為小項，其中每個變元與它否定不能同步浮現，但兩者必要___________。18．前提引入規則：在證明任何環節上都可以___________，簡稱___________規則。19．自由變元代入規則是指對某___________浮現個體變元可用個體常元或用與原子公式中所有個體變元不同個體變元去代入，且___________。20．設A=,B={2,4}，則((A)=___________，A×B___________。21．設A={1,2,3,4}，A上二元關系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，則R2S=___________，(R-1)2=___________。22．設代數系統<A,·,*>是環，則<A,·>是___________，<A,*>是___________。23．在<Z7-{0},7>中，元素2階為___________，它生成子群為___________，其中7為模7乘法。24．設<A,≤>是一種___________，如果A中任意兩個元素均有___________，則稱<A，≤>為格。25．若一條___________中，所有___________均不相似，稱為跡。三、計算題（本大題共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．請通過等值演算法求┐(P∧Q)→(P∨Q)主析取范式。28．設A={1,2,3,4}，給定A上二元關系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R傳遞閉包。29．對題29圖所示格，找出它所有4元子格。30．用矩陣辦法求題30圖中結點ui，u5之間長度為2途徑數目。31．求題31圖最小生成樹。四、證明題（本大題共3小題，第32小題8分，第33、34小題各6分，共20分）32．用推理辦法證明(A∨B)→(C∧D),(D∨F)→E├A→E。33．證明：設<G,·>是一種群，則對于任意a,b∈G，必存在惟一x∈G使得a·x=b。34．設圖G有n個結點，n+1條邊，證明：G中至少有一種結點度數