1、精品文檔設(shè) D 的結(jié)點(diǎn)數(shù)大于通路中至少有一條回路B.D1，D=<V ,E> 是強(qiáng)連通圖，當(dāng)且僅當(dāng)（中有通過(guò)每個(gè)結(jié)點(diǎn)至少一次的回路D .DC.D）15. A.D 中至少有一條中有通過(guò)每個(gè)結(jié)點(diǎn)至少一次的通路在室內(nèi)運(yùn)動(dòng)”可符合化,Q1.設(shè) P：天下大雨： 他在室內(nèi)運(yùn)動(dòng),命題 “除非天下大雨，否則他不為（）Q A. PQ B. PQ QD.P C. P 2.下列命題聯(lián)結(jié)詞集合中，是最小聯(lián)結(jié)詞組的是（） A.， B.， D.， ， C.） 3.下列 命題為假命題的是（數(shù)，那么一個(gè)公式的析取范式不惟一奇數(shù)，那么一個(gè)公式的析取范式不惟一 是偶數(shù)，那么一個(gè)公式的析取范式惟一B. 如果 2 是奇數(shù)，

2、那么一個(gè)公式的析取范式惟一D. 如果 2 Q(x) 中變?cè)?x 是（）yR(y)4.A.如果 2 是偶C.如果 2 是謂詞公式x(P(x) A. 自由變?cè)?B. 約束變?cè)?C.既不是自由變?cè)膊皇羌s束變?cè)?5.若個(gè)體域 為整數(shù)集，下列公式中值為真的是（ ）D.既是自由變?cè)彩羌s束變A.xy(x+y=0) B.yx(x+y=0)x y(x+y=0)） 6.下列命題中不正確的是（B.xA.x x -xx -xA=B D.A-B= A且 x AxC.A=x x,則 22+16 5x, 則下列選項(xiàng)正確的是（） 7.設(shè)P=x|(x+1)Q=x|x 4 ，A.P Q B.P QD.Q=PPC.Q(A）8

3、.下列表達(dá)式中不成立的是（ C) B)C=(AD.(A-B)××× C)-(BC) B) × C=(A× C)C)(A B.A(BC)=(AB) A.A(B × C) C.(A (BC)=(A(xy(x) ()(P() Qy) x)） y(x,) ，下列說(shuō)法正確的是（ R對(duì)于公式5 y是約束變?cè)狟 A y是自由變?cè)?的轄域是), R() C(x的轄域是xyx(D)(yx )yQ )(P)(x(x(R)y,精品文檔精品文檔） )等價(jià)的是（1,2，與公式(x)A(x6設(shè)論域?yàn)锳 A(1) A(2) B A(1) A(2)D(2) A(2)

4、 A(1)C A(1) A 14 下列圖是歐拉圖的是（） 度，那么這棵樹(shù)的邊數(shù)是（度點(diǎn)， 4 個(gè) 2 度點(diǎn)，其它的都是115一棵樹(shù)的3 個(gè) 414 13BA16C 15 D二、填空題。 A B=_ ，則 A A=_， 16.設(shè)A=1,2,3，B=3,4,5。的自反閉包r(R)=_， <3,4>,<2,2>，則R 設(shè)A=1,2,3,4,5，R A×A，R=<1,2>17.。對(duì)稱(chēng)閉包t(R)=_ _。_ 為兩個(gè)命題， 德摩根律可表示為， 吸收律可表示為18.設(shè) P、Q 時(shí)，其真值為當(dāng)論域?yàn)?,2 x=1,Q(x) x=2, 19.對(duì)于公式 x(P(x)

5、 Q(x) ，其中 P(x) _ 。當(dāng)論域?yàn)?0,1,2 時(shí)，其真值為_(kāi) ,10101101- A)=_ _, (v,若 G 的鄰接矩陣deg，則 ,v,v23. 設(shè)圖G<V,E>,V=v,v 1243100110010+。 deg(v)=_ 4 R=<1,2>,<3,4>,<2,2>,上定義兩種關(guān)系：A=1,2,3,4,5，在集合A25. 給定集合， 。則S=<4,2>,<2,5>,<3,1>,<1,3>，_?_S?R _SR精品文檔精品文檔B_ 。 A)=_ ， A × 20設(shè) A=

6、,B=2,4 ，則 P(P(，則, S=<1,3>,<2,4>,<4,2>=1,2,3,4, A上的二元關(guān)系R=<1,2>,<2,4>,<3,3>21設(shè) A 22- 1R=_) 。R S=_ ，( _ 均不相同， 稱(chēng)為跡。 25 若一條 _中，所有的分， 30 題 8 題各 5 分，第 28、 296 分，第、三、計(jì)算題（本大題共5 小題，第2627 題各共 30分）的關(guān)系圖， 并，畫(huà)出 R 上的等價(jià)關(guān)系A(chǔ)=a,b,c,d ，AR=<a,b>,<b,a>,<c,d>,<d,c>

7、; I26. 設(shè) A A中各元素的等價(jià)類(lèi)。求出）的真值表。Q （ P 構(gòu)造命題公式（ QP ）27. ） P Q求下列公式的主析取范式和主合取范式：P（ QP ）（28.<a, b>, <a, e>, <b, e>,<c, e>, <d,，<a, c>A ，R 為上的關(guān)系， R=<a, d>A=a, b, c, d, e29.設(shè)中的最大元， 最小元， 極大元， 極小元。A ，R> 的哈斯圖，并求<A e>I ，試畫(huà) A 的 G 的路有幾條？其中有幾條回路？（2）寫(xiě)出 4G1 如圖所示，給定圖30.G （）中長(zhǎng)度為可達(dá)矩陣。精品文檔精品文檔30 分）三、計(jì)算題（本大題共6 小題，每小題 5 分，共求式 , GTGTSFSff=1,2給定論域26D ，(1)=2, (2)=1, (1)=, (2)=, (1,2)=, (2,1)=T 在該賦值下，精品文檔精品文檔子 x(S( f(x) G(x, f(x) 的真值。27請(qǐng)通過(guò)等值演算法求(P Q) (P Q) 的主析取范式。28設(shè) A=1,2,3,4 ，給定A 上二元關(guān)系R=<1,1&g