離散填空題和答案

1、填空1、P :你努力，q :你失敗?！俺悄闩?，否則你將失敗”的翻譯為； “雖然你努力了，但還是失敗了”的翻譯為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=（列舉法）。則幺元是 ；是否有對稱性4、設(shè)代數(shù)系統(tǒng)，其中A=a，b，c,則幺元是 ；是否有對稱性5、n個結(jié)點的無向完全圖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、示三個集合，文圖中陰影部分的集合表達(dá)式為設(shè)P, Q的真值為0, R, S的真值為1,則(P v (Q - (R P) - (R vS)的真值=。若解釋I的論域D僅包含一個元素，則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= 。圖的補圖為。設(shè)A=a, b, c, d , A上二元運算如下:*bdac*bdacbdaac*bdac*bdacbdaac那么代數(shù)系統(tǒng)的幺元是 a ,有逆元的元素為 a,b c,d ，它們的逆 元分別為a,d,c,b。14. n個結(jié)點的樹中有 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是任意一一個整數(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具有反自反，反對稱，反傳遞 性質(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)的真值 為 。求一個公式的主析取或主合取式的方法，有 真值表 法和 等值演算 法。給定謂詞合式公式A,其中一部分公式形式為(Vx )B(x)或(3 x)B(x),則量詞V , 3后面所跟的x稱為 指導(dǎo)變元，而稱B為相應(yīng)量詞的 轄域

5、。集合X=a, b, c, d上二元關(guān)系 R=, , , , , , 則 R 的 自 反 閉 包 r(R)=,對稱閉包 s(R)=, , , , , ,。對代數(shù)系統(tǒng),其中*是S上的二元運算，若a, bES,且對任意的xES，都有a*x=x*a=x, b*x=x*b=b,則稱a為運算“*”的 單位元，稱b為運算“*”的 零元 。 設(shè)是群，則滿足結(jié)合律和 交換律，單位元，逆元。 一個連通且無回路的無向圖稱為樹。在簡單無向圖G=中，如果V中的每個結(jié)點都與其余的所有結(jié)點鄰接，則該圖 稱為 完全圖 ，如果V有n個結(jié)點，那么它還是正則圖。 任意兩個不同的小項的合取為矛盾式，全體小項的析取式必為重言式。設(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)= ,， 對稱閉包 s(R)= TOC o 1-5 h z 一,。 設(shè)Q為有理數(shù)集，笛卡爾集S=QXQ，*是S上的二元運算，V,ES, *=,則*運算的單位元是_。V E S,若aN0，則的逆元是_。 設(shè)*是集合S上的二元運算，若運算*滿足結(jié)合律 存在單位元，則稱為有么半群。

7、如下無向圖割點是_0，割邊是。 無向圖G具有生成樹，當(dāng)且僅當(dāng)_連通且無回路。G的所有生成樹中 權(quán)最小 的生成樹稱為最小生成樹。 所謂 簡單命題 是指不能再分解的命題，而復(fù)合命題是由一些簡單命題經(jīng)過聯(lián)結(jié) 詞復(fù)合而成的命題。 在命題演算中，兩個命題一的合取、析取、條件、雙條件均為復(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 是素數(shù)，則 domR=2，3, 4 :ranR= 1,2。設(shè)X=1，3, 5, 9，15, 45，R是X上的整除關(guān)系，則R是

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

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

10、，其余的都是1度頂點，則T中有 個1度頂點。 n階完全圖Kn的邊數(shù)為 n(n-1)/2。010161.右圖的鄰接矩陣A=001161.右圖的鄰接矩陣A=0100011062.設(shè)為代數(shù)系統(tǒng)，*運算如下:*a*aaabbccbcbcaccc則它的幺元為 ;零元為ca、b、c 的逆元分別為a b c無逆元。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 個二元關(guān)系。66. A=1, 2, 3上關(guān)系R= , 時，R既是對稱的又是反 對稱的。偏序集V

11、 A,R的哈斯圖為，貝 R = , U Q：我將去，R：我有時間，公式(Q T R) A (R T Q)的自然語言為我在當(dāng)且僅當(dāng)我有空。若P, Q為二命題，P Q真值為1,當(dāng)且僅當(dāng)P,Q 同為真命題或同為假命題對公式(VyP(x, y) a BzQ(x,z) v VxR(x, y)中自由變元進行代入的公式為一(VyP(,y)a3zQ(u,z)vVxR(x,v)。 若R是集合A上的偏序關(guān)系，則R滿足自反性 反對稱性 傳遞性。設(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 在一個有n個元素的集合上，可以有 種不同的關(guān)系，有 nn種不同的函數(shù)。若關(guān)系R是反對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以美對角線為對稱的元素不能同時為1, 在關(guān)系圖上兩個不同節(jié)點間的定向弧線，不可能成對出現(xiàn)。 設(shè)g。f是一個復(fù)合函數(shù)，若g和f都是滿射，則g。f為滿射若g和f都是單射，則g。f是。設(shè)A = 2, a ,3,4, B = a, 3,4,1，請在下列每對集合中填入適當(dāng)?shù)姆枺?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個結(jié)點，各結(jié)點的次數(shù)分別為2, 4, 4, 6, 5, 5, 2,則G中有 J4 條邊，根據(jù) 握手定理