離散數(shù)學(xué)習題集十五套

1、離散數(shù)學(xué)試題與試卷一20% （每小題 2 分）一、填空A = x | (x Î N )且(x < 5), B = x | x Î E +且x < 7 （N：自然數(shù)集，E+1設(shè)正偶A È B = 。數(shù)） 則2A，B，C 表示三個集合，陰影部分的集合表為 。3設(shè) P，Q 的為 0，R，S 的為 1，則Ø(P Ú (Q ® (R Ù ØP) ® (R Ú ØS) 的4公式(P Ù R) Ú (S Ù R) Ú ØP 的主合取范式為

2、 。=。$xP(x) ® "xP(x)5若解釋 I 的論域 D 僅包含一個元素，則在I 下為 。6設(shè) A=1，2，3，4，A圖為則 R2 = 。7設(shè) A=a，b，c，d，其上偏序R 的為則 R= 。8圖的補圖為。9設(shè) A=a，b，c，d ，A 上二元運算如下：1A BC那么代數(shù)系統(tǒng)<A，*>的 元是，有逆元的元素為，它們的逆元分別為。10下圖所示的偏序集中，是格的為。二、選擇 20% （每小題 2 分）1、下列是真命題的有（）a Í a；F ÎF, F；BFÎF,F；AFÎF。CD2、下列集合中相等的有（）A4，3 

3、00; F ；B F ，3，4；C4， F ，3，3；D3，4。3、設(shè) A=1，2，3，則A 上的二元有（）個。32´2 。23´3 ；A 23 ；32B； CD4、設(shè) R，S 是集合 A 上的，則下列說法正確的是（A. 若 R，S 是自反的， 則 R o S 是自反的；B. 若 R，S 是反自反的， 則 R o S 是反自反的；C. 若 R，S 是對稱的， 則 R o S 是對稱的；D. 若 R，S 是傳遞的， 則 R o S 是傳遞的。5、設(shè) A=1，2，3，4，P（A）（A 的冪集）上規(guī)定二元系如下）R = < s, t >| s, t Î p(

4、 A) Ù (| s |=| t | 則 P（A）/ R=（）2*abcda b cda bcdb cdac dabd abcAA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D F ，2，2，3，2，3，4，A6、設(shè) A= F ，1，1，3，1，2，3則 A 上包含“ Í ”的為（）7、下列函數(shù)是Af : I ®E ,Cf : R ®I ,的為（）Bf : N ®N´ N,f (n) = <n , n+1> ；Df :I ®N, f (x)=| x | 。f (x) = 2x ；f (x) = x

5、 ；（注：I整數(shù)集，E偶數(shù)集， N自然數(shù)集，R實數(shù)集）8、圖 中 從v1 到v3 長度為 3 的通路有（）條。A 0； B1；C 2；D 3。9、下圖中既不是 Eular 圖，也不是 Hamilton 圖的圖是（）10、在一棵樹中有 7 片樹葉，3 個 3 度結(jié)點，其余都是 4 度結(jié)點則該度結(jié)點。）個 4（A1； B2； C3； D4 。三、證明 26%、R 是集合 X 上的一個自反，求證：R 是對稱和傳遞的，當且僅當< a, b> 和<a , c>在R 中有<.b , c>在 R 中。（8 分）3、f 和 g 都是群<G1 ,>到< G2

6、, *>的同態(tài)，證明<C , >是<G1, >的一個子群。其中 C=x | x Î G1且f (x) = g(x)(8 分)、G=<V, E>(|V| = v，|E|=e ) 是每一個面至少由 k（k ³ 3）條邊圍成的連通平面e £ k(v - 2)k - 2圖，則， 由此證明（Peterson）圖是非平面圖。（11 分）四、邏輯推演 16%用 CP 規(guī)則證明下題（每小題 8 分）1、 A Ú B ® C Ù D, D Ú E ® F Þ A ® F2

7、、"x(P(x) ® Q(x) Þ "xP(x) ® "xQ(x)五、計算 18%1、設(shè)集合 A=a，b，c，d上的R=<a , b > ,< b , a > ,< b, c > , < c , d >用矩陣運算求出 R 的傳遞閉包 t (R)。（9 分）2、如下圖所示的賦表示某七個城市v1 , v2 ,L, v7 及預(yù)先算出它們之間的一些直接通信線路造價，試給出一個設(shè)計方案，使得各城市之間能夠通信而且總造價最小。（分）試卷一：一、填空 20% （每小題 2 分）1、0，1，2，3，4，

8、6； 2、(B Å C) - A ；3、1； 4、(ØP Ú S Ú R) Ù (ØP Ú ØS Ú R) ；5、1；6、<1,1>, <1,3>, <2,2>, <2,4> ；7、<a.b>,<a,c>,<a,d>,<b,d>,<c,d>IA ；8、U9、a ；a , b , c ,d ；a , d , c , d ；10、c;4二、選擇 20% （每小題 2 分）三、證明 26%1、 證：&qu

9、ot;a, b, c Î X< a, b >, < a, c > ÎRÞ“”若由 R對 稱 性 知< b, a >, < c, a > ÎR ，由 R 傳遞性得< b, c >ÎR若 < a, b > ÎR ， < a, c > ÎR< b, c >ÎRa, b Î X“ Ü ”有任意 ，因 < a, a > ÎR 若< a, b > ÎR 若 < a

10、, b > ÎR ， < b, c > ÎR即 R 是傳遞的。< b, a > ÎR所以 R 是對稱的。< b, a > ÎR Ù < b, c >Î R < a, c > ÎR則"a, b Î Cf (a) = g(a), f (b) = g(b)2、 證，有，又f (b-1 ) = f -1 (b) ,g(b-1 ) = g -1 (b) f (b-1 ) = f -1 (b) = g -1 (b) = g(b-1 ) f (a b-1

11、 ) = f (a) * f -1 (b) = g(a) * g(b-1 ) = g(a b -1 )a b -1 Î C3、 證：< C , >是 < G1 , >的子群。r2ekåi2e =d (F ) ³ rki=1r £v - e + r = 2 故設(shè) G 有 r 個面，則，即。而e £ k(v - 2)2 = v - e + r £ v - e + 2ekk - 2。（8 分）即得e £ k(v - 2)為 k = 5, e = 15, v = 10 ，這樣k - 2不成立，所以平面圖。（3

12、 分）二、 邏輯推演 16%1、 證明：5題目12345678910CDB、CCADCADBA A A Ú B A Ú B ® C Ù D C Ù D D D Ú E D Ú E ® F F A ® F2、證明 "xP(x) P(c) "x(P(x) ® Q(x) P(c) ® Q(c) Q(c) "xQ(x) "xP(x) ® "xQ(x)P（附加前提）TIPTITITIPTICPP（附加前提）USPUSTIUGCP三、 計

13、算18%1、 解：æ 0100001000öæ 1010010000öç÷0÷ç÷1÷= ç 1= ç 0= MMMo Mç 01÷ç 00÷RR2RRç0÷0ç0÷0èøèø，æ 0100001001öç÷0÷= ç 1M= Mo Mç 00÷RR3R2ç0÷

14、;0èø，æ 10ö01001000ç÷1÷= ç 0M= Mo Mç 00÷R4R3Rç0÷0èø6æ1110011öç÷= ç111÷M= M+ M+ M+ Mç 01÷t ( R)RR2R3R400ç0÷0èøt (R)=<a , a> , <a , b> , < a , c> , <a ,

15、 d > , <b , a > , < b ,b > , < b , c . > ,< b , d > , < c , d > 2、 解： 用（Kruskal）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：樹權(quán) C(T)=23+1+4+9+3+17=57 即為總造價。試卷二試題與一、填空 20% （每小題 2 分）1、 P：你努力，Q：你失敗?！俺悄闩Γ駝t你將失敗”的翻譯為 ；“雖然你努力了，但還是失敗了”的翻譯為 。2、論域 D=1，2，指定謂詞 P則公式"x$yP( y, x)為。2、 設(shè) S=a1 ，a2 ，a8，

16、Bi 是 S 的子集，則由 B31 所表達的子集是 。R = < x, y >| x < y Ú x是質(zhì)數(shù) ，則3、 設(shè) A=2 ， 3 ， 4 ， 5 ， 6 上的二元R= （列舉法）。R 的矩陣 MR= 。5 、設(shè) A=1 ， 2 ， 3 ，則 A 上 既 不 是 對 稱 的 又 不 是稱 的R= R= 。； A 上既是對稱的又是稱的7P (1,1)P (1,2)P (2,1)P (2,2)TTFF6、設(shè)代數(shù)系統(tǒng)<A，*>，其中 A=a，b，c,則元是； 是 否 有 冪 等性；是否有對稱性。7、4 階群必是群或群。8、下面偏序格是分配格的是。9、n

17、個結(jié)點的無向完全圖 Kn 的為，的充要條件是 。10、公式(P Ú (ØP Ù Q) Ù (ØP Ú Q) Ù ØR 的根樹表示為 。二、選擇 20% （每小題 2 分）1、在下述公式中是重言式為（）A (P Ù Q) ® (P Ú Q) ；B (P « Q) « (P ® Q) Ù (Q ® P) ；C Ø(P ® Q) Ù Q ；D P ® (P Ú Q)。(ØP 

18、4; Q) ® (ØQ Ú P)2、命題公式為（中極小項的個數(shù)為（），賦值的個數(shù)）。A0；B1；C2；D3 。3、設(shè) S = F,1,1,2 ，則2 S有（）個元素。A3；4、 設(shè) S = 1,B6；C7；D8 。2, 3 ，定義 S ´ S 上的等價R = << a,b >, < c, d >| < a, b >Î S ´ S, < c, d >Î S ´ S, a + d = b + c 則由R 產(chǎn) 生的 S ´ S 上一個劃分共有（）個分塊。8*

19、abca bca bcb bcc cbA4；5、設(shè) S = 1,B5；2, 3 ，SC6；D9 。R 的圖為則 R 具有（）性質(zhì)。A自反性、對稱性、傳遞性；B反自反性、D自反性 。稱性；C反自反性、稱性、傳遞性；+,o） < S, +, o > 是域。B S = x | x = 2n ,a, b Î Z6、設(shè)為普通加法和乘法，則（A S = x | x = a + b 3 ,a,b Î QC S = x | x = 2n + 1,n Î ZD S = x | x Î Z Ù x ³ 0= N。7、下面偏序集（）能格。8、在

20、如下的有中，從 V1 到 V4 長度為 3 的道路有（）條。A1；B2；C3；。D4 。9、在如下各圖中（）10、設(shè) R 是實數(shù)集合，“ ´ ”為普通乘法，則代數(shù)系統(tǒng)<R ，×> 是（）。A群；B獨異點；C半群 。9三、證明 46%1、 設(shè) R 是 A 上一個二元，S = < a,b >| (a,b Î A) Ù (對于某一個c Î A, 有< a, c >Î R且< c,b >Î R)試證 明若 R 是 A 上一個等價，則 S 也是 A 上的一個等價。（9 分）2、 用邏輯推

21、理證明：所有的舞蹈者都很有風度，是個學(xué)生且是個舞蹈者。因此有些學(xué)生很有風度。（11 分）f : A ® B 是從A 到 B 的函數(shù)，定義一個函數(shù) g : B ® 2 A 對任意 b Î B 有3、 若g(b) = x | (x Î A) Ù ( f (x) = b)，證明：若 f 是 A 到 B 的的。（10 分）2 A，則 g 是從 B 到4、 若無G 中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定連通。（8 分）m = 1 (n -1)(n - 2) + 225、 設(shè) G 是具有 n 個結(jié)點的無向簡單圖，其Hamilton 圖（8 分），則 G 是

22、四、計算 14%1、 設(shè)<Z6,+6>是一個群，這里+6 是模 6 加法，Z6=0 ，1，2，3，4，5，試求出<Z6,+6>的所有子群及其相應(yīng)。（7 分）2、 權(quán)數(shù) 1，4，9，16，25，36，49，64，81，100 構(gòu)造一棵最優(yōu)二試卷二：一、 填空 20%（每小題 2 分）。（7 分）B31 = B00011111 = a4 , a5 , a6 , a7 , a8 ØP ® QP Ù Q1 、；2 、 T3 、4 、R=<2,2>,<2,3>,<2,4>,<2,5>,<2,6&g

23、t;,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,æ 11 ö110101101011110çç 1÷1 ÷ç 01 ÷çç 1÷1 ÷ç 00÷èø3>,<5,4>,<5,5>,<5,6> ；R=<1,1>,<2,2&

24、gt;,<3,3>5、四R=<1,2>,<1,3>,<2,1> ；循環(huán)群 8、 B9、6、a ；否；有7、Klein101 n(n -1)2；圖中無奇度結(jié)點且連通 10 、二、選擇 20%（每小題 2 分）三、1、（證明 46%9 分）（1） S 自反的"a Î A ，由 R 自反，(< a, a >Î R) Ù (< a, a >Î R) ，< a, a >Î S（2） S 對稱的"a, b Î A< a, b >&#

25、206; S Þ (< a, c >Î R) Ù (< c, b >Î R)Þ (< a, c >Î R) Ù (< c, b >Î R)Þ< b, a >Î S（3） S 傳遞的"a, b, c Î A< a, b >Î S Ù < b, c >Î SLS 定義LR 對稱LR 傳遞Þ (< a, d >Î R) Ù (&

26、lt; d , b >Î R) Ù (< b, e >Î R) Ù (< e, c >Î R)Þ (< a, b >Î R) Ù (< b, c >Î R)Þ< a, c >Î S由（1）、（2）、（3）得；S 是等價2、11 分LR 傳遞LS 定義。證明：設(shè) P(x)：x 是個舞蹈者； Q(x) ：x 很有風度； S(x)：x 是個學(xué)生； 上述句子符號化為：a：前提： "x(P(x) ® Q(x)

27、、 S(a) Ù P(a)結(jié)論： $x(S (x) Ù Q(x)3 分 S(a) Ù P(a) "x(P(x) ® Q(x) P(a) ® Q(a) P(a) Q(a). S(a) S(a) Ù Q(a) $x(S(x) Ù Q(x)、0 分P PUSTI TI TI TIEG11 分11題目12345678910B、DD；DDBDABBBB、C： "b1 ,b2 Î B ,(b1 ¹ b2 ) Q f$a1 , a2 Î Af (a2 ),由于f是函數(shù), a1 ¹

28、 a2證明使f (a1 ) = b1 , f (a2 ) = b2 , 且 f (a1 ) ¹又 g(b1 ) = x | (x Î A) Ù ( f (x) =b1 ),g(b2 ) = x | (x Î A) Ù ( f (x) = b2 ) a1 Î g(b1 ), a2 Î g(b2 )但 a1 Ï g(b2 ), a2 Ï g(b1 ) g(b1 ) ¹ g(b2 )由b1,b2任意性知 ,g為4、8 分證明：設(shè) G 中兩奇數(shù)度結(jié)點分別為 u 和 v，若 u，v 不連通，則 G 至少有

29、兩個連通分支 G1、G2 ，使得 u 和 v 分別屬于 G1 和 G2，于是 G1 和 G2 中各含有 1 個奇數(shù)度結(jié)。點，這與圖論基本定理5、8 分，因而 u，v 一定連通。證明： 證 G 中任何兩結(jié)點之和不小于 n。不相鄰且d (u) + d (v) £ n -1,令V1 = u, v，則反證法：若兩結(jié)點 u，vG-V1³ 1 (n -1)(n - 2) + 2 - (n -1) 2m'是具有 n-2 個結(jié)點的簡單圖， 它的, 可得³ 1 (n - 2)(n - 3) + 1m'2，這與 G1=G-V1 為 n-2 個結(jié)點為簡單圖的題設(shè)，因而

30、G中任何兩個相鄰的結(jié)點度數(shù)和不少于 n。所以 G 為 Hamilton 圖.四、計算 14%1、 7 分解：子群有<0,+6>；<0,3,+6>；<0,2,4,+6>；<Z6,+6>0的0，3的：0，1；2，3；4，5：0，3；1，4；2，50，2，4的：0，2，4；1，3，5Z6 的：Z6 。2、 7 分試卷三試題與12一、填空 20% （每空 2 分）1、 設(shè) f，g 是自然數(shù)集 N 上的函數(shù)"x Î N,f (x) = x + 1 ,g(x) = 2x ，f o g(x) =。則2、 設(shè) A=a，b，c，A 上二元R=&

31、lt; a, a > , < a, b >,< a, c >, < c, c>,則 s（R）=。T = < x, y >| x ¸ y 是，則用列舉3、 A=1，2，3，4，5，6，A 上二元法T=；T 的圖為 ； 性質(zhì)。T 具有A = F, 2,2 4、 集合的冪集2 A =。(P Ù (R Ú S) ® (P Ú Q) Ù (R Ù S) 的5、 P，Q為 0 ；R，S為 1。則 wff為 。wff Ø(P Ù Q) Ú R) ®

32、; R6、的主合取范式為。7、 設(shè) P（x）：x 是， E(x)：x 是偶數(shù)，O(x)：x 是奇數(shù) N (x,y)：x 可以整數(shù) y。則謂詞 wff"x(P(x) ® $y(O( y) Ù N ( y, x) 的自然語言是 。"x"y($z(P(x, z) Ù P( y, z) ® $uQ(x, y, u) 的前束范式為8、 謂詞 wff。二、選擇 20% （每小題 2 分）1、 下述命題公式中，是重言式的為（）。A、( p Ù q) ® ( p Ú q) ； B、( p « q) &

33、#171; ( p ® q) Ù (q ® p) ；C、Ø( p ® q) Ù q ；D、( p Ù Øp) « q 。Ø( p Ù q) ® r 的主析取范式中含極小項的個數(shù)為（wff2、）。A 、2；B、 3；3、 給定推理C、5；D、0；E、 8 。13 "x(F (x) ® G(x) F ( y) ® G( y) $xF (x) F ( y) G( y) "xG(x) "x(F (x) ® G(x) 

34、2; "xG(x)PUSPESTIUG推理過程中錯在（）。A、-> B、-> C、-> D、-> E、->4、 設(shè) S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，Í S1 且 XË S3 下 X 與（S5=3，5，在條件 XA、 X=S2 或 S5 ；C、X=S1，S2 或 S4；）集合相等。B、X=S4 或 S5；D、X 與 S1，S5 中任何集合都不等。5、 設(shè)R和 SP， P是上 的是 所 有 人 的 集 合 ，R = < x, y >| x, y Î P 

35、7; x是y的父親， S = < x, y >| x, y Î P Ù x是y的母親則 S -1 o R 表示（）。A、< x, y >| x, y Î P Ù x是y的丈夫；B、< x, y >| x, y Î P Ù x是y的孫子或?qū)O女；D、< x, y >| x, y Î P Ù x是y的祖父或祖母。F ；C、6、 下面函數(shù)（）是而非。f : R ® R,-1；f (A、f : Z + ® R,f : R ® Z,f : R

36、74; R,f (x) = ln x ；f (x) = f (x) = 2x + 1。B、的最大整數(shù)；C、D、其中 R 為實數(shù)集，Z 為整數(shù)集，R+，Z+分別表示正實數(shù)與正整數(shù)集。7、 設(shè) S=1，2，3，R 為S 上的，其圖為則 R 具有（）的性質(zhì)。14A、 自C、反自反、稱、傳遞；B、什么性質(zhì)也沒有；D、自） Í S 。稱、傳遞；稱、稱、傳遞。8、 設(shè) S = F,1,1, 2，則有（A、1,2 ；B、1,2 ； C、1 ； D、2 。9、 設(shè) A=1 ,2 ,3 ，則 A 上有（）個二元。32； C、22 ； D、 23 。）。A、23； B、32 10、全體小項合取式為（A、

37、可滿足式； B、式； C、式； D、A，B，C可能。三、用 CP 規(guī)則證明 16% （每小題 8 分）1、 A Ú B ® C Ù D , D Ú E ® FÞA ® F2、"x(P(x) Ú Q(x)Þ"xP(x) Ú $xQ(x)四、（14%）集合 X=<1,2>, <3,4>, <5,6>, ，R=<<x1,y1>,<x2,y2>>|x1+y2 = x2+y1。1、 證明 R 是 X 上的等價2、

38、求出 X 關(guān)于 R 的。 （10 分）。（4 分）五、（10%）設(shè)集合 A= a ,b , c , d 要求 1、寫出 R 的R=< a, b > , < b , a > , < b , c > , < c , d >矩陣和圖。（4 分）2、用矩陣運算求出 R 的傳遞閉包。（6 分）六、（20%）1、（10 分）設(shè) f 和 g 是函數(shù)，證明 Ç g 也是函數(shù)。f分）設(shè)函數(shù) g : S ® T® S ，證明® S 有一左逆函數(shù)當且僅當 f 是f : Tf : T2、（10入射函數(shù)。：五、 填空 20%（每空

39、2 分）>a>a<>a<, ； 3 、1 、 2(x+1) ； 2 、< 2,1 >, < 3,1 >, < 5,1 >, < 4,2 >, < 6,2 >, < 6,3 > ；4、稱性、反自反性；4、F,F,2,2,F,2,2；5、1；6、(P Ú ØQ Ú R) Ù (ØP Ú Q Ú R) Ù (P Ú Q Ú R) ；7、任意 x，如果 x 是則；8、"x"y&quo

40、t;z$u(ØP(x, z) Ú ØP( y, z) Ú Q(x, y,u) 。一個 y，y 是奇數(shù)且y 整除 x六、 選擇20%（每小題 2 分）七、 證明16%(每小題 8 分)1、 A A Ú B A Ú B ® C Ù D C Ù D D D Ú E D Ú E ® F F A ® FP（附加前提）TIPTITITIPTICP2、Q "xP(x) Ú $)P(x) ® $xQ(x)本題可證 "x(P(x) Ú

41、 Q(x) Þ Ø("xP(x) ® $xQ(x)Ø("xP(x)P（附加前提） $x(ØP(x) ØP(a) "x(P(x) Ú Q(x) P(a) Ú Q(a) Q(a) $xQ(x)TEESPUSTIEG16題目12345678910CCCCABDADC Ø("xP(x) ® $xQ(x)八、 14%（1）證明：CP自反性： " < x, y >Î X , 由于x + y = x + y1、 << x, y

42、 >, < x, y >>Î RLR自反對稱性： " < x1 , y1 >Î X , " < x2 , y2 >Î X2、當<< x1 , y1 >, < x2 , y2 >>Î R時 即x1 + y2 = x2 + y1 也即x2 + y1 = x1 + y2故<< x2 , y2 >, < x1 , y1 >>Î RLR有對稱性傳遞性： " < x1 , y1 >Î X

43、 , " < x2 , y2 >Î X" < x3 , y3 >Î X3、當<< x1 , y1 >, < x2 , y2 >>Î R 且 << x2 , y2 >, < x3 , y3 >>Î R 時ì x1 + y2= x2 + y1(1)(2)即íx+ y = x + yî 2332(1) + (2)x1 + y2 + x2 + y3 = x2 + y1 + x3 + y2即 x1 + y3 = x3 +

44、 y1故 << x1 , y1 >, < x3 , y3 >>Î RLR有傳遞性由（1）（2）（3）知：R 是 X 上的先等價2、X/R=< 1 ,2 >R 九、 10%。æ 00ö10000ç÷= ç 110÷Mç 01÷R00ç0÷0èø ；1、圖æ 10ö01001ç÷= ç 001÷M= Mo Mç 00÷R2RR00ç0

45、÷0èø2、æ 01ö10000100ç÷0÷= ç 1M= Mo Mç 00÷R3R2Rç0÷0èø17æ 1010010öç÷= ç 001÷ = Moç 00÷R3RR00ç0÷0M= M, M= M,LèøR5R3R6R4= M R + M R2 + M R3 + MMt ( R)t (R)=<a , a>

46、, <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c ,d > 。六、 20%f Ç g = < x, y >| x Î= < x, y >| x Î1、（1）令h = f Ç g domf Ç g = domh = （2） h = < x, y >| x Î domf Ç對x

47、Î domh若有y1, y2使得y1 = h(x) = f (x) = g(x) ,由于f (或g)是函數(shù),有y1 = y2 即"x Î domh 有唯一y使得 f Ç g也是函數(shù)。2、證明："Þ"若f 有一左逆g ,則對"t Î故 g o f是入射,所以 f 是入射。"Ü" f" Î:® S定Tf是入射,( ),由 fT入fs 射,$ | t Î此時令=若 Ï (T,)g)fsts則對" Î則ogS(,s

48、)s只有一個值=(),) 故fgggtts即若f入射,必能構(gòu)造函數(shù)g,。試卷四試題與一、 填空 10% （每小題2 分）1、 若 P，Q，為二命題， P ® Q為 0 當且僅當。2、 命題“ 對于任意給定的正實數(shù)， 都比它大的實數(shù)” 令 F(x)： x為實數(shù)， L(x, y) : x > y則命題的邏輯謂詞公式為 。"xP(x) ® $xQ(x)3、 謂為詞合式公式的前束范式 。4、 將量詞轄域中出現(xiàn)的和指導(dǎo)變元交換為另一變元符號，公式其余的部分不變，這種稱為換名規(guī)則。5、 設(shè) x 是謂詞合式公式 A 的一個客體變元，A 的論域為 D，A(x)關(guān)于 y 是的

49、，則 被稱為量詞消去規(guī)則，記為ES。二、 選擇 25% （每小題 2.5 分）1、 下列語句是命題的有（）。B、 x + y > 0 ；A、 明年中秋節(jié)的晚上是晴天；C、 xy > 0 當且僅當 x 和y 都大于 0； D、我正在說謊。2、 下列各命題中為真題有（）。A、 2+2=4 當且僅當 3 是奇數(shù)；B、2+2=4 當且僅當 3 不是奇數(shù)；C、2+24 當且僅當 3 是奇數(shù)； D、2+24 當且僅當 3 不是奇數(shù)；3、 下列符號串是合式公式的有（ ）A、 P Û Q ；B、 P Þ P Ú Q ；C、(ØP Ú Q) 

50、7; (P Ú ØQ) ；D、Ø(P « Q) 。4、 下列等價式成立的有（）。A、 P ® Q Û ØQ ® ØP ；B、 P Ú (P Ù R) Û R ；P Ù (P ® Q) Û Q ；D、 P ® (Q ® R) Û (P Ù Q) ® R 。C、5、 若 A1 , A2 L An 和 B 為 wff，且 A1 Ù A2 ÙLÙ An Þ B 則（

51、）。A、稱 A1 Ù A2 ÙLÙ An 為 B 的前件；B、稱 B 為 A1 , A2 L An 的有效結(jié)論A1 Ù A2 ÙLÙ An Ù B Û FC 、 當 且 僅 當； D 、 當 且 僅 當A1 Ù A2 ÙLÙ An Ù ØB Û F 。6、 A，B 為二合式公式，且 A Û B ，則（）。A、 A ® B 為重言式；C、 A Þ B ；B、 A*D、 A*Þ B* ；Û B* ；E、 A &

52、#171; B 為重言式。197、 “人總是要死的”謂詞公式表示為（）。（論域為全總域）M(x)：x 是人；Mortal(x)：x 是要死的。A、 M (x) ® Mortal (x) ；B、 M (x) Ù Mortal(x)C、"x(M (x) ® Mortal(x) ；D、$x(M (x) Ù Mortal(x)8、 公式 A = $x(P(x) ® Q(x) 的解釋 I 為：域 D=2，P(x)：x>3, Q(x)：x=4 則 A的為（）。A、1； B、0；C、可滿足式； D、無法判定。9、 下列等價正確的是（）。A、&

53、quot;x(P(x) Ú Q(x) Û "xP(x) Ú "xQ(x) ；B、$x(P(x) Ú Q(x) Û $xP(x) Ú $xQ(x) ；C、"x(P(x) ® Q) Û "xP(x) ® Q ；D、$x(P(x) ® Q) Û $xP(x) ® Q 。10、 下列推理步驟錯在（ "x(F (x) ® G(x) F ( y) ® G( y) $xF (x) F ( y) G( y) $xG(x)）

54、。PUSPESTIEGA、；B、；C、；D、30%三、 邏輯公式 A = (P ® Q) Ù (Q ® P) « (P « Q) 的類1、 用等值演算法和型。（10 分）表法2、 下列，若成立請證明，若不成立請舉出反例：（10 分）已知 A Ú C Û B Ú C ，問 A Û B 成立嗎？已知ØA Û ØB ，問 A Û B 成立嗎？（1）（2）3、 如果廠方拒絕增資，那么就停止，除非超過一年并且工廠撤換了廠長。問：若廠方拒絕增資，面剛開始，是否能夠停止。（10

55、分）20四、計算 10%1、 設(shè)命題 A1，A2 的為 1，A3，A4為 0，求命題( A1 Ú ( A2 ® ( A3 Ù ØA1 ) « ( A2 Ú ØA4 ) 的。（5 分）2、 利用主析取范式，求公式Ø(P ® Q) Ù Q Ù R 的類型。（5 分）五、謂詞邏輯推理 15%符號化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。六、證明：（10%）設(shè)論域 D=a , b , c，求證： "xA(x) Ú "：十、

56、填空 10%（每小題 2 分）( A(x) Ú B(x) 。0；2、"x(F (x) Ù L(x,0) ® $y(F ( y) Ù L( y, x) ；3、1、P為 1，Q 的為$x(ØP(x) Ú Q(x) ；4、約束變元；5、$xA(x) Þ A( y) ，y 為 D 的某些元素。十一、選擇 25%（每小題 2.5 分）十二、邏輯30%1、（1）等值演算法A = (P ® Q) Ù (Q ® P) « (P « Q) Û (P « Q) &#

57、171; (P « Q) Û T（2）表法所以 A 為重言式。2、（1）不成立。21PQP ® QQ ® P(P ® Q) Ù (Q ® P)P « QA1111111100100101100010011111題目12345678910A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)若取C = T則A Ú T Û TB Ú T Û T 有 A Ú C Û B Ú C Û T但 A 與 B 不一定等價，可為任意不等價的公式。（

58、2）成立。證明： ØA Û ØB充要條件 ØA « ØB Û TT Û (ØA ® ØB) Ù (ØB ® ØA) Û ( A Ú ØB) Ù (B Ú ØA)即： Û (ØB Ú A) Ù (ØA Ú B) Û ( A ® B) Ù (B ® A) Û A « B所以

59、 A « B Û T 故A Û B 。3、解：設(shè) P：廠方拒絕增資；Q：停止；R超壺過一年；R：撤換廠長前提： P ® (Ø(R Ù S) ® ØQ) , P ® (Ø(R Ù S) ® ØQ) P Ø(R Ù S ) ® ØQ ØR ØR Ú ØS Ø(R Ù S ) ØQ停止是有效結(jié)論。ØR結(jié)論： ØQP,PPTIPTITETI四、計

60、算 10%(1 Ú (1 ® 0 Ù 0) « (1 Ú 1) = (1 Ú (1 ® 0) « 1解： = (1 Ú 0) « 1= 1 « 1= 1Ø(P ® Q) Ù Q Ù R Û Ø(ØP Ú Q) Ù (Q Ù R)Û (P Ù ØQ) Ù (Q Ù R) Û P Ù ØQ Ù Q &#

61、217; R Û F（1）（2）它無賦值，所以為式。五、謂詞邏輯推理 15%解： M (x) : x是人;F(x) : x是花;G(x) : x是雜草;H (x, y) : x喜歡y$x(M (x) Ù "y(F ( y) ® H (x, y)Þ "x(F (x) ® ØG(x)證明："x(M (x) ® "y(G( y) ® ØH (x, y) $x(M (x) Ù "y(F ( y) ® H (x, y)P22 M (a) 

62、7; "y(F ( y) ® H (a, y) M (a) "y(F ( y) ® H (a, y) "x(M (x) ® "y(G( y) ® ØH (x, y) M (a) ® "y(G( y) ® ØH (a, y) "y(G( y) ® ØH (a, y) "y(H (a, y) ® ØG( y) F (z) ® H (a, z) H (a, z) ® ØG(z) F (z) ® ØG(z) "x(F (x) ® ØG(x)ESTITIPUSTITEUSUSTIUG十三、證明 10%"xA(x) Ú "xB(x) Û ( A(a) Ù A(b) Ù A(c) Ú (B(a) Ù B(b) Ù B(c)Û ( A(a) Ú B(a) Ù ( A(a) Ú B(b) Ù ( A(a) Ú B(c)Ù ( A(b) Ú B(a)