一、單項選擇題（本大題共15小題，每小題1分，共15分）未選均無分。1．下列句子命題的是（D ）A．中華人民共和國的首都是北京C．雪是黑色的2．下列式子謂詞合式公式的是（BB．張三是學(xué)生D．太好了！）A（）P→R)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)→QB．P∨Q∧R→┐RC．P∨(P∧Q)D．(┐P∨Q)(P→Q)4．在指定的解釋下，下列公式為真的是（）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是自由變元C．(x)的轄域是R(x,y)

B．y是約束變元D．(x)的轄域是(y)(P(x)∧Q(y))→(x)R(x,y)設(shè)論域{1,2}，與公(x)A(x)等價的是（ ）A．A(1)∨A(2)C．A(1)∧A(2)

B．A(1)→A(2)D．A(2)→A(1)設(shè)Z+是正整數(shù)集是實數(shù)集，f:Z+→R,f(n)=log2n,則f（ ）C．是雙射

僅是滿射D下列關(guān)系矩陣所相應(yīng)的關(guān)系具有反對稱性的是（ ）1 0 1A．0 1 1

1 0 0B．0 1 1 1 0 00 0 1 C．0 0 1 0 0

1 0 11 0 1 D． 1 0 09 1 ．設(shè)R和R是集合A上的相容關(guān)系，下列關(guān)于復(fù)合關(guān)系R R9 1 2 1 2一定是等價關(guān)系C下列運算互換律的是（

一定是相容關(guān)系Da*b=a+2bC．a(chǎn)*b=|a-b|

D．a(chǎn)*b=2ab設(shè)A是偶數(shù)集合，下列說法對的的是（ ）<A,+>是群C．<A,÷>

<A,×>是群D．<A,+>,<A,×>,<A,÷>都不是群設(shè)是集合A上的二元運算，下列說法對的的是（ ）A的左幺元一定有右幺元A的左右幺元一定有幺元A的左右幺元，它們不一定相同A的幺元不一定有左右幺元13．題13圖的最大出度是（A．0）B．1C．2D．314．下列圖是歐拉圖的是（）一棵樹的3個4度點，4個2度點，其它的都是1度，那么這棵樹的邊數(shù)是（ ）A．13 B．14C．15 D．16二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上對的答案。錯填、不填均無分。請寫出表達德摩根律的兩個命題公式等價定， 。17．n個命題變元稱為小項，其中每個變元與它的否認不能同時出現(xiàn)，但兩者必18．前提引入規(guī)則：在證明的任何環(huán)節(jié)上都可，簡規(guī)則。19．自由變元代入規(guī)則是指對某 出現(xiàn)的個體變元可用個體常元或用與原子公式中所有個體變元不的個體變元去代入，。20．設(shè)A=,B={2,4}，則( (A)= ，A×B 。21．設(shè)A={1,2,3,4},A上的二元關(guān)系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，則R2S= ，(R-1)2= 。22．設(shè)代數(shù)系<A,·,*>是環(huán)，<A,·>是 ，<A,*>是 。<Z7-{0},7>中，元素2的階，它生成的子群，其7為模7乘法。<A,≤>是一，假如A中任意兩個元素都，則<A,≤>為格。若一中，所有均不相同，稱為跡。三、計算題（本大題共6小題，每小題5分，共30分）26={1,2(1)=2,(2)=1,(1)F,S(2)T,G(1,2)T,G(2,1)=S(,)))的真值。27．請通過等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。28．設(shè)A={1,2,3,4}，給定A上二元關(guān)系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的傳遞閉包。294元子格。30u，u2的途徑的數(shù)目。i 531圖的最小生成樹。四、證明題（本大題共3小題，第32小題8分，第33、34小題各6分，共20分）(A∨B)→(C∧D),(D∨F)→E├A→E。<G,·>a,b∈Gx