【正文】 當 G 是 ( )，G的生成樹只有一棵。 答：它是連通圖 6設 G是一棵樹， n,m分別表示頂點數(shù)和邊數(shù)，則 9 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能確定。 (1) {a， ab， 110， a1b11} (2) {01， 001， 000， 1} (3) {1， 2， 00， 01， 0210} (4) {12， 11， 101， 002， 0011} 答： (1) 6 n個結點的有向完全圖邊數(shù)是 ( )，每個結點的度數(shù)是 ( )。 答：所有邊一次且恰好一次 6有 n個結點的樹，其結點度數(shù)之和是 ( )。 答： 2 )1( ?nn , n1 60、一棵無向樹的頂點數(shù) n與邊數(shù) m關系是 ( )。 答：以 v為起點的邊的條數(shù)， 以 v為終點的邊的條數(shù) 5設 G是一棵樹，則 G 的生成樹有 ( )棵。 (1) 歐拉圖 (2) 樹 (3) 平面圖 (4) 連通圖 答： (4) 5下面給出的集合中，哪一個是前綴碼？ ( ) (1) {0， 10， 110， 101111} (2) {01， 001， 000， 1} 8 (3) {b， c， aa， ab， aba} (4) {1， 11， 101， 001， 0011} 答：（ 2） 5一個圖的哈密爾頓路是一條通過圖中 ( )的路。 (1) 2階 (2) 3 階 (3) 4 階 (4) 6 階 答： (3) （格與布爾代數(shù)部分） 5下列哪個偏序集構成有界格（ ） (1) （ N,? ） (2) （ Z,? ） (3) （ {2,3,4,6,12},|（整除關系）） (4) (P(A),? ) 答： (4) 5有限布爾代數(shù)的元素的個數(shù)一定等于（ ）。 答： k 7 4在自然數(shù)集 N上，下列哪種運算是可結合的？（ ） (1) a*b=ab (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|ab| 答： (2) 50、任意一個具有 2個或以上元的半群，它（ ）。 答： H,? 是群 或 a， b ?G， a? b?H， a1?H 或 a,b ?G， a? b1?H 4群＜ A,*＞的等冪元有 ( )個，是 ( )，零元有 ( )個。 答：循環(huán)群，任一非單位元 4設〈 G,*〉是一個群， a,b,c∈ G，則 (1) 若 c? a=b，則 c=( )； (2) 若 c? a=b? a，則 c=( )。 答： 5， 10 4群 G,*的等冪元是 ( )，有 ( )個。 答： 6,4 4代數(shù)系統(tǒng) G,*是一個群，則 G的等冪元是 ( )。 答： 2， 6 3設 A={3,6,9}， A 上的二元運算 *定義為： a*b=min{a,b}，則在獨異點 6 A,*中，單位元是 ( )，零元是 ( )； 答： 9， 3 （半群與群部分） 3設〈 G,*〉是一個群，則 (1) 若 a,b,x∈ G， a? x=b，則 x=( )； (2) 若 a,b,x∈ G， a? x=a? b，則 x=( )。 答： R的關系矩陣 =??????????????????000000001000000001 R1? 的關系矩陣 =??????????000000010000000001 3集合 A={1,2,… ,10}上的關系 R={x,y|x+y=10,x,y?A}，則 R 的性質(zhì)為（ ）。 答： R={1,1,2,2,3,3,4,4,5,5,6,6,1,2,1,3,1,4, 1,5,1,6,2,4,2,6,3,6} 3設Ａ＝｛ 1,2,3,4,5,6｝， B={1,2,3}，從Ａ到 B的關系Ｒ＝｛〈 x,y〉 |x=2y｝，求 (1)R (2) R1 。 ( ) 答： A上的恒等關系 集合 A上的等價關系的三個性質(zhì)是什么？ ( ) 答：自反性、對稱性和傳遞性 3集合 A上的偏序關系的三個性質(zhì)是什么？ ( ) 5 答：自反性、反對稱性和傳遞性 3設 S={１ ,２ ,３ ,４ }，Ａ上的關系Ｒ＝｛〈 1,2〉，〈 2,1〉，〈 2,3〉，〈 3,4〉｝ 求 (1)R? R (2) R1 。 答：（ 2） 2Ａ，Ｂ，Ｃ是三個集合，則下列哪幾個推理正確： (1) A? B， B? C= A? C (2) A? B， B? C= A∈ B (3) A∈ B， B∈ C= A∈ C 答：（ 1） （二元關系部分） 2設Ａ＝｛ 1,2,3,4,5,6｝， B={1,2,3}，從Ａ到 B的關系Ｒ＝｛〈 x,y〉 |x=y2｝，求 (1)R (2) R1 。 答：（ 2） 2設 A∩ B=A∩ C， A ∩ B=A ∩ C，則 B( )C。 答： 32 1設 P={x|(x+1)2 ? 4 且 x?R},Q={x|5? x2 +16且 x?R},則下列命題哪個正確（ ） (1) Q? P (2) Q? P (3) P? Q (4) P=Q 答：（ 3） 下列各集合中，哪幾個分別相等 ( )。 (1) {a}?P(A) (2) {a}? P(A) (3) {{a}}?P(A) (4) {{a}}? P(A) 答： (2) 1在 0（ ） ? 之間寫上正確的符號。則命題“并非每個實數(shù)都是有理 3 數(shù)”的符號化表示為（ ）。 答： ? P ， Q?P 1謂詞公式 x(P(x) yR(y))?Q(x)中量詞 x的轄域是（ ）。 答： 2不是偶數(shù)且 3不是負數(shù)。 (1) 只有在生病時，我才不去學校 (2) 若我生病，則我不去學校 (3) 當且僅當我生病時，我才不去學校 (4) 若我不生病，則我一定去學校 答：（ 1） PQ?? （ 2） QP ?? （ 3） QP ?? （ 4） QP?? 設個體域為整數(shù)集，則下列公式的意義是 ( )。 (5) 前進！ (6) 給我一杯水吧！ 答：（ 1） 是， T （ 2） 是， F （ 3） 不是 （ 4） 是， T （ 5） 不是 （ 6） 不是 命題“存在一些人是大學生”的否定是 ( )，而命題“所有的人都是要死的”的否定是 ( )。 (2) 陜西師大是一座工廠。若是，給出命題的真值。 1 《離散數(shù)學》題庫答案 一、選擇或填空 （數(shù)理邏輯部分） 下列哪些公式為永真蘊含式？ ( ) (1)? Q=Q→ P (2)? Q=P→ Q (3)P=P→ Q (4)? P? (P? Q)=? P 答：（ 1），（ 4） 下列公式中哪些是永真式？ ( ) (1)(┐ P? Q)→ (Q→ ? R) (2)P→ (Q→ Q) (3)(P? Q)→ P (4)P→ (P? Q) 答：（ 2），（ 3），（ 4） 設有下列公式，請問哪幾個是永真蘊涵式 ?( ) (1)P=P? Q (2) P? Q=P (3) P? Q=P? Q (4)P? (P→ Q)=Q (5) ? (P→ Q)=P (6) ? P? (P? Q)=? P 答：（ 2），（ 3），（ 4），（ 5），（ 6） 公式 x((A(x) B(y， x)) z C(y， z)) D(x)中，自由變元是 ( )，約束變元是 ( )。 答： x,y, x,z 判斷下列語句是不是命題。 ( ) (1) 北京是中華人民共和國的首都。 (3) 你喜歡唱歌嗎？ (4) 若 7+8＞ 18，則三角形有 4條邊。 答：所有人都不是大學生，有些人不會死 2 設 P：我生病， Q：我去學校，則下列命題可符號化為 ( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（ 1）對任一整數(shù) x存在整數(shù) y滿足 x+y=0（ 2）存在整數(shù) y 對任一整數(shù) x滿足 x+y=0 設全體域 D是正整數(shù)集合，確定下列命題的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（ 1） F （ 2） F （ 3） F （ 4） T 設謂詞 P(x)： x是奇數(shù)， Q(x)： x是偶數(shù)，謂詞公式 x(P(x) Q(x))在哪個個體域中為真 ?( ) (1) 自然數(shù) (2) 實數(shù) (3) 復數(shù) (4) (1)(3)均成立 答：（ 1） 1命題“ 2是偶數(shù)或 3是負數(shù)”的否定是（ ）。 1永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可滿足式 (4) (1)(3)均有可能 答：（ 2） 1公式 (? P? Q)? (? P? ? Q)化簡為（ ），公式 Q?(P? (P? Q))可化簡為（ ）。 答： P(x) yR(y) 1令 R(x):x是實數(shù)， Q(x):x是有理數(shù)。 答： ? x(R(x)?Q(x)) （集合論部分） 1設 A={a,{a}}，下列命題錯誤的是（ ）。 (1) = (2) ? (3) ? (4) ? 答： (4) 1若集合 S的基數(shù) |S|=5，則 S的冪集的基數(shù) |P(S)|=（ ）。 (1) A1={a,b} (2) A2={b,a} (3) A3={a,b,a} (4) A4={a,b,c} (5) A5={x|(xa)(xb)(xc)=0} (6) A6={x|x2(a+b)x+ab=0} 答： A1=A2=A3=A6， A4=A5 2若 AB=Ф，則下列哪個結論不可能正確？ ( ) (1) A=Ф (2) B=Ф (3) A? B (4) B? A 答：（ 4） 2判斷下列命題哪個為真 ?( ) (1) AB=BA = A=B (2) 空集是任何集合的真子集 (3) 空集只是 非空集合的子集 (4) 若 A的一個元素屬于 B，則 A=B 答：（ 1） 4 2判斷下列命題哪幾個為正確？ ( ) (1) {Ф }∈ {Ф ,{{Ф }}} (2) {Ф }? {Ф ,{{Ф }}} (3) Ф∈ {{Ф }} (4) Ф ? {Ф } (5) {a,b}∈ {a,b,{a},} 答：（ 2），（ 4） 2判斷下列命題哪幾個正確？ ( ) (1) 所有空集都不相等 (2) {Ф }? Ф (4) 若 A為非空集，則 A? A成立。 答： =（等于） 2判斷下列命題哪幾個正確？ ( ) (1) 若 A∪ B＝ A∪ C，則 B＝ C (2) {a,b}={b,a} (3) P(A∩ B)? P(A)∩ P(B) （ P(S)表示 S的冪集） (4) 若 A為非空集，則 A? A∪ A成立。 答：（ 1） R={1,1,4,2} (2) R1? ={1,1,2,4} 2舉出集合 A上的既是等價關系又是偏序關系的一個例子。 答： R? R ={〈 1,1〉，〈 1,3〉，〈 2,2〉，〈 2,4〉 } R1 =｛〈 2,1〉，〈 1,2〉，〈 3,2〉，〈 4,3〉｝ 3設Ａ＝｛ 1， 2， 3， 4， 5， 6｝，Ｒ是 A上的整除關系，求 R= {( )}。 答：（ 1） R={1,1,4,2,6,3} (2) R1? ={1,1,2,4,(36} 3設Ａ＝｛ 1,2,3,4,5,6｝， B={1,2,3}， 從Ａ到 B的關系Ｒ＝｛〈 x,y〉 |x=y2｝，求 R和 R1的關系矩陣。 (1) 自反的 (2) 對稱的 (3) 傳遞的，對稱的 (4) 傳遞的 答：（ 2） （代數(shù)結構部分） 3設 A={2,4,6}， A 上的二元運算 *定義為： a*b=max{a,b}，則在獨異點A,*中，單位元是 ( )，零元是 ( )。 答： （ 1） a ??1 b （ 2） b 設 a是 12階群的生成元， 則