離散填空題和答案

1、填空1、P :你努力，q :你失敗?！俺悄闩Γ駝t你將失敗”的翻譯為； “雖然你努力了，但還是失敗了”的翻譯為2、論域D=1，2，指定謂詞PP (1,1) P (1,2) P (2,1) P (2,2)TT F F則公式Vx3yP（y,x）真值為 3、設(shè) A=2，3，4，5，6上的二元關(guān)系 R = 1 x V y 尤是質(zhì)數(shù)，貝R=（列舉法）。則幺元是 ；是否有對(duì)稱性4、設(shè)代數(shù)系統(tǒng)，其中A=a，b，c,則幺元是 ；是否有對(duì)稱性5、n個(gè)結(jié)點(diǎn)的無(wú)向完全圖Kn的邊數(shù)為 6.設(shè) A = x | (x g N)且(x 5),B = x | x g E +且x 7 (N：自然數(shù)集，E+ 正偶A，B，C表

2、示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為設(shè)P, Q的真值為0, R, S的真值為1,則(P v (Q - (R P) - (R vS)的真值=。若解釋I的論域D僅包含一個(gè)元素，則xP(x) xP(x)在I下真值為 (T, F)。設(shè)A=1, 2, 3, 4, A上關(guān)系圖為則 R2 = 11.設(shè)A=a, b, c, d,其上偏序關(guān)系R的哈斯圖為則 R= 。圖的補(bǔ)圖為。設(shè)A=a, b, c, d , A上二元運(yùn)算如下:*bdac*bdacbdaac*bdac*bdacbdaac那么代數(shù)系統(tǒng)的幺元是 a ,有逆元的元素為 a,b c,d ，它們的逆 元分別為a,d,c,b。14. n個(gè)結(jié)點(diǎn)的樹(shù)中有 n

3、-1條邊。.15.設(shè) A = 0,1,2,3, A 上的關(guān)系為R = ,若 Rm = ，貝。m=3;若 Rn =奴則n =4。16 .設(shè) A = a,b,c , A 上的二元關(guān)系 R=,則 r(R),; S (R)=,.I是整數(shù)集，如果(I, +)是群，那么(I, +)的幺元是0； n是任意一一個(gè)整數(shù)，則n的逆元是 。若集合A=1, 2, 3上的二元關(guān)系R1和R2的關(guān)系圖如下所示，貝 R3R2 =,19.設(shè)f, g是自然數(shù)集N上的函數(shù)Vxc N, f (x) = x +1, g (x) = 2 x,貝 g f o g (x) = 2x+2。20.設(shè) A=a, b, c則 s (R)=A 上二元

4、關(guān)系 R= , , , 21. A=1, 2, 3, 4, 5, 6, A上二元關(guān)系T = x20.設(shè) A=a, b, c則 s (R)=T= , ；T的關(guān)系圖為T具有反自反，反對(duì)稱，反傳遞 性質(zhì)。集合A = ,2,2的冪集2A= ,2, 兒 2, ，2,2 。P, Q 真值為 0 ； R, S 真值為 1。則 wff (P (R v S) (P v Q) (R S)的真值 為 。求一個(gè)公式的主析取或主合取式的方法，有 真值表 法和 等值演算 法。給定謂詞合式公式A,其中一部分公式形式為(Vx )B(x)或(3 x)B(x),則量詞V , 3后面所跟的x稱為 指導(dǎo)變?cè)QB為相應(yīng)量詞的 轄域

5、。集合X=a, b, c, d上二元關(guān)系 R=, , , , , , 則 R 的 自 反 閉 包 r(R)=,對(duì)稱閉包 s(R)=, , , , , ,。對(duì)代數(shù)系統(tǒng),其中*是S上的二元運(yùn)算，若a, bES,且對(duì)任意的xES，都有a*x=x*a=x, b*x=x*b=b,則稱a為運(yùn)算“*”的 單位元，稱b為運(yùn)算“*”的 零元 。 設(shè)是群，則滿足結(jié)合律和 交換律，單位元，逆元。 一個(gè)連通且無(wú)回路的無(wú)向圖稱為樹(shù)。在簡(jiǎn)單無(wú)向圖G=中，如果V中的每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，則該圖 稱為 完全圖 ，如果V有n個(gè)結(jié)點(diǎn)，那么它還是正則圖。 任意兩個(gè)不同的小項(xiàng)的合取為矛盾式，全體小項(xiàng)的析取式必為重言式。設(shè)集

6、合 M=xl1WxW12,x 被 2 整除，xEZ,N=xl1WxW12,x 被 3 整除，xEZ，則MnN= J6.12，MUN=_。設(shè) X=1，2，3，f： X-X，g： X-X，f=, g=, ， 貝 f o g= , ， g o f=,o設(shè)A=a,b,c，R是A上的二元關(guān)系，且給定R=,，則R的自反閉包 r(R)= ,， 對(duì)稱閉包 s(R)= TOC o 1-5 h z 一,。 設(shè)Q為有理數(shù)集，笛卡爾集S=QXQ，*是S上的二元運(yùn)算，V,ES, *=,則*運(yùn)算的單位元是_。V E S,若aN0，則的逆元是_。 設(shè)*是集合S上的二元運(yùn)算，若運(yùn)算*滿足結(jié)合律 存在單位元，則稱為有么半群。

7、如下無(wú)向圖割點(diǎn)是_0，割邊是。 無(wú)向圖G具有生成樹(shù)，當(dāng)且僅當(dāng)_連通且無(wú)回路。G的所有生成樹(shù)中 權(quán)最小 的生成樹(shù)稱為最小生成樹(shù)。 所謂 簡(jiǎn)單命題 是指不能再分解的命題，而復(fù)合命題是由一些簡(jiǎn)單命題經(jīng)過(guò)聯(lián)結(jié) 詞復(fù)合而成的命題。 在命題演算中，兩個(gè)命題一的合取、析取、條件、雙條件均為復(fù)合命題。使公式(3x)(3y)(A(x) B(y) = (3x)A(x) (3y)B(y)成立的條件是 _A中不含 y， B中不含xo設(shè) A=1，2，3，4，R 是 A 上的二元關(guān)系，R=|x/y 是素?cái)?shù)，則 domR=2，3, 4 :ranR= 1,2。設(shè)X=1，3, 5, 9，15, 45，R是X上的整除關(guān)系，則R是

8、X上的偏序，其最大元是45 .，極小元是 。樹(shù)是不包含回路 的連通圖。45.設(shè)F(x):x是人，H(x,y):x與y一樣高，在一階邏輯中，命題“人都不一樣高”的符號(hào)化形式為_(kāi)N蜀/(F(x) a F(y) T T(x, y) 一 。(p v q) Ap T q從公式分類角度來(lái)看，它為 式。設(shè) R=,，則 R 的 對(duì) 稱 閉包是 ,。 Vx(A(x) a B(x) o = VxA(x) a V(x)B(x)。設(shè)F(x):x是人，H(x):x呼吸，在一階邏輯中，命題“凡人都呼吸”的符號(hào)化形式為_(kāi)V(x)(F(x) T H(x)。 一個(gè)3階有向圖的度序列是2，2，4，入度序列是2，0，2，出度序列是

9、0,2,2 。一無(wú)向圖存在生成樹(shù)的充分必要條件是無(wú)向圖是連通圖。 量詞否定等值式VxA(x) o = BxA(x)。設(shè) R 是 A=(1，2，3，4上的二元關(guān)系，R=,則 R 的對(duì)稱閉包是 ,。已知n階無(wú)向簡(jiǎn)單圖G有m條邊，則G的補(bǔ)圖有(n(n-1 )/2)-m條邊。已知n階無(wú)向圖G中有m條邊，各頂點(diǎn)的度數(shù)均為3。又已知2n-3=m，貝 g m=9.設(shè)G為9階無(wú)向圖，每個(gè)結(jié)點(diǎn)度數(shù)不是5就是6,則G中至少有 也 個(gè)5度結(jié)點(diǎn)。 有向圖中從v1到v2長(zhǎng)度為2的通路有 0 條。任何(n,m)圖G = (V,E),邊與頂點(diǎn)數(shù)的關(guān)系是_ d(v) = 2m。i=1已知一棵無(wú)向樹(shù)T有三個(gè)3頂點(diǎn)，一個(gè)2度頂點(diǎn)

10、，其余的都是1度頂點(diǎn)，則T中有 個(gè)1度頂點(diǎn)。 n階完全圖Kn的邊數(shù)為 n(n-1)/2。010161.右圖的鄰接矩陣A=001161.右圖的鄰接矩陣A=0100011062.設(shè)為代數(shù)系統(tǒng)，*運(yùn)算如下:*a*aaabbccbcbcaccc則它的幺元為 ;零元為ca、b、c 的逆元分別為a b c無(wú)逆元。63.設(shè) A=1, 2, 3, 4, A 上二元關(guān)系 R=, , , 畫出 R 的 關(guān)系圖。64.設(shè) A=, , B=,則 A D B = ,A oB =,65.設(shè)IAI=3,則A上有 232 =512 個(gè)二元關(guān)系。66. A=1, 2, 3上關(guān)系R= , 時(shí)，R既是對(duì)稱的又是反 對(duì)稱的。偏序集V

11、 A,R的哈斯圖為，貝 R = , U Q：我將去，R：我有時(shí)間，公式(Q T R) A (R T Q)的自然語(yǔ)言為我在當(dāng)且僅當(dāng)我有空。若P, Q為二命題，P Q真值為1,當(dāng)且僅當(dāng)P,Q 同為真命題或同為假命題對(duì)公式(VyP(x, y) a BzQ(x,z) v VxR(x, y)中自由變?cè)M(jìn)行代入的公式為一(VyP(,y)a3zQ(u,z)vVxR(x,v)。 若R是集合A上的偏序關(guān)系，則R滿足自反性 反對(duì)稱性 傳遞性。設(shè)M = x 1 x 12,x被2整除，x e Z, N = x|1 x 12,工被3整除，x e Z,貝g M c N =6, 12, M - N = 2, 4, 8, 1

12、0 在一個(gè)有n個(gè)元素的集合上，可以有 種不同的關(guān)系，有 nn種不同的函數(shù)。若關(guān)系R是反對(duì)稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以美對(duì)角線為對(duì)稱的元素不能同時(shí)為1, 在關(guān)系圖上兩個(gè)不同節(jié)點(diǎn)間的定向弧線，不可能成對(duì)出現(xiàn)。 設(shè)g。f是一個(gè)復(fù)合函數(shù)，若g和f都是滿射，則g。f為滿射若g和f都是單射，則g。f是。設(shè)A = 2, a ,3,4, B = a, 3,4,1，請(qǐng)?jiān)谙铝忻繉?duì)集合中填入適當(dāng)?shù)姆?hào)： e , c。(1) a B , (2) a ,4, 3 三 A。0,尤是奇數(shù)， 設(shè)A = 0,1, N為自然數(shù)集，f (x)= 若f： A A，則f是1,尤是偶數(shù)。雙射射的，若f：N - A，則f是滿 射的。設(shè)圖G = 中有7個(gè)結(jié)點(diǎn)，各結(jié)點(diǎn)的次數(shù)分別為2, 4, 4, 6, 5, 5, 2,則G中有 J4 條邊，根據(jù) 握手定理