北京大學現代遠端教育2023年秋季學期期末考試試卷a
為無向連通圖g(m,n) 的一棵生成樹，則對應t的基本回路數為（m-n+1）[ 是 ]
2、每條邊都是橋的無向連通圖必是樹是 ]
3、非平凡無向樹 t 至少 1 片樹葉非 ]
4、11 階無向連通圖 g 中有 17 條邊，其任一棵生成樹 t 中必有6條樹枝 [ 非 ]
5、無向圖g中有10條邊,4個3度頂點,其餘頂點度數全是2,共有 8 個頂點. [ 是]
6、二元正則樹有奇數個頂點對 ]
7、n（n ≥ 1）階有向完全圖都是有向尤拉圖對 ]
8、無向連通圖 g（m,n）的每一條邊都可以成為他的某一生成樹的樹枝。 [ x ]
9、邊數 m 等於 n-1 的 n 階無向圖都是樹x ]
10、10 階無向連通圖 g 有m 條邊，則生成樹 t 對應的基本割集數目為 9 ［ ］
11．樹ｔ有ｍ條邊，ｎ個頂點，則有是］
12可以是乙個圖的頂點度數列 ［非］
13．作為有向圖中有向邊始點的次數叫出度是 ]
14．10 階無向簡單圖 g 中有 6 個奇數度頂點，其補圖中必有４個奇數度頂點 [是 ]
15．10、11 階無向簡單連通圖 g 中，頂點間的最大距離是 11x ]
11、11 條邊的圖 g 中，所有頂點的度數之和為 22
12、11 階無向簡單圖g中有 6個奇數度頂點，其補圖中必有 5個奇數度頂點 [ x ]
13、圖ｇ中２個３度頂點，３個４度頂點，４個５度頂點，則ｇ中有１８條邊．[ ]
14、10 階無向連通圖 g 有m 條邊，則生成樹 t 對應的基本割集數目為9。 ［ ］
15. 邊數 m 等於 n-1 的 n 階無向圖都是樹x ]
16.無向樹的任何邊都是橋
17.無向連通圖g（n，m）的每一棵生成樹都有 n-1 條樹枝
18、無向連通圖g（n，m）的每一條邊都可以成為他的某一生成樹的樹枝。[ x ]
19、一棵樹中有 i 個頂點的度數為 i（i=2，…k），其餘頂點都是樹葉。
當 k = 4 時，問樹葉多少片？（10 分）
三、填空題.(每題 2 分，共 16 分）
1、個體域是人類，則命題」人固有一死」應符號化為 ( x f（x） ) 。
2、命題應為能判斷對錯的( 陳述 )句。
3、令 p：天下雨；q：乘汽車。命題 』』如果天下雨，則乘汽車』』 符號化為 (ｐ→ｑ )
4、任乙個命題公式至少 ( 1 ) 個主析取正規化 .
5、命題 」明天不下雨，也沒有太陽，將是陰天。」 應符號化為 ( ┐p∧┐q∧r ).
6、命題公式 p 的主合取正規化為 ( ∏( 0 ) )
7、命題公式 p∧┐q∧r 的主析取正規化為 ( ∑( 5 ) )
8、個體域為自然數集合,則 x+y = y+x ( 是 ) 命題。
１３．令 f（x）：x是兔子；g（y）：y是烏龜；h（x，y）：x 比y 跑得快。將命題 「 所有兔子不比某些烏龜跑得快」 符號化為：
（x（f（x）→﹃ 彐y（g（y）∧h（x，y））） ）
14、設個體域是自然數集合，p 代表 xy彐z f（x－y = z），則 p ( 是假 )命題。
15、令 p 代表一階邏輯公式 g（x）與 g（y）等值，則 p（ 是假 ）命題。
1６．命題公式（﹁ｐ∧ｐ）→ｑ的型別是（ 永真式 ）．
17．任何圖中，度數為奇數的頂點個數為 （ 偶數 ）
18．在命題邏輯中，任何命題公式都( 有唯一的乙個 ) 主合取正規化.
19．設域為正整數集合，命題 x 彐y（x＞y）的真值為 （ ０ ）
20令 p：經一塹；q：長一智。命題』』只有經一塹，才能長一智』』符號化為[ b]
a． p→q； b． q→p； c． p∧q； d． ﹁q→﹁p
天氣好；q：我們去遊玩．將命題＂除非天氣好，否則我們不去遊玩＂符號化為［ｂ］
a． p→q； b． q→p； c． p∧q； d． ﹁q→﹁p
22.命題公式ｐ→(ｐ∧ｑ)為假的賦值是ｐ,ｑ分別為（（１，０））
23、明天不下雨，也沒有太陽，將是陰天。
┐p∧┐q∧r。
24、人固有一死。
x（f（x）→g（x））。
25、有的汽車不見得比所有的火車跑得慢。
﹁l（x,y）））。
26、x + 3 y = 3 y + x。
符號化為：p或
。27、即使張三和李四考分相等，也只有一人被我校錄取。
p∧（（q∧┐r）∨（┐q∧r））。
28.任何命題公式都有唯一的主析取正規化和唯一的主合取正規化是 ]
29.任何命題公式都有唯一的與其等值的析取正規化和唯一的與其等值的合取正規化 [ 非 ]
30.任何命題公式都有唯一的與其等值的析取正規化和唯一的與其等值的合取正規化 [ 非 ]
31.任何命題公式都有唯一的與其等值的析取正規化非 ]
32.任何命題公式都有唯一的與其等值的合取正規化非 ]
33.公式a有n個命題變元,其主析取正規化中有k個極小項,m 個極大項,則m+k=2n [ 是 ]
34.有 n 個命題變元的永真式,其主析取正規化中有 k =2n 極小項,則極大項數m=0 [是 ]
35.有n個命題變元的永假式,其主析取正規化中有 k=0 個極小項,則極大項數 m=2n [ 是 ]
36.有n個命題變元的可滿足式,其主析取正規化中有k個極小項,m個極大項,則 037.公式 ﹃(q→p)∧p 的型別是永假式是 ]
38.命題 」這台機器不能用」 應符號化為 ( ﹃f（a）或﹃p )
四、設 s =，s上的關係 r 如下：r = ，試完成下列要求（每要求 3 分，共 12 分）
1、給出 r 的所有元素。r= ∪is。
2、給出 ranr 的表示式。 ranr =
3、指出 r 的性質。自反，反對稱，傳遞。
4、給出 domr 的表示式。 domr = 。
2、設 a =，r = 是集合 a 上的二元關係，試求：
（1）r 的表示式。 =∪ia
2。 。-1
（2）r 的關係圖。
0。 。1
2 （3）r 的性質。 自反，對稱，傳遞。
３．設集合是ａ上的乙個劃分．求
（１）給出有確定的等價關係
ia ．
（２）給出ｒ的圖示．
（３）給出ａ的元素的自然對映
4. 設 s =，s 上的關係 r 如下，完成諸項要求。（ 分）。
r = 。
1、 domr =
2、 ranr =
3、 說明 r 的性質。
4、 求復合 r 。r 的表示式
5. 若關係 r 具有對稱性，則復合r 。r 也具有對稱性。
∵對稱性，∴ r = r-1 ，對復合（r 。r）求逆，有（r 。r）-1 = r-1 。r-1 = r
r，得證。
6.集合 s=，r 是 x 上的二元關係，根據 ri（z）如下的謂語表示式，對於所有x，y∈x，分別列出ri（z），i=1，2，3的元素 z。
1、 r1 = 。
=2、r2 = 。
=3、r3 = 。
=2、 r1 = 。
= 。3、 r2 = 。
=。4、 r3 = 。
<-1,1>,<0,0>,<1,1>}。
離散數學題目總結
第一章1 只有努力學習，認真複習，才能取得好成績。解 p 努力學習。q 認真複習。r 取得好成績。p q r p q r r p q 2 正規化 例 求公式 p r p q r 的和取正規化 原式 p r p q r p q r p r p q p r p q r 和取正規化 0,1,3,4,6 2...
離散數學 複習
第1章命題邏輯 本章重點 命題與聯結詞，公式與解釋，真值表，公式的型別及判定,主 析取 合取 正規化，命題邏輯的推理理論.一 重點內容 1.命題 命題表述為具有確定真假意義的陳述句。命題必須具備二個條件 其一，語句是陳述句 其二，語句有唯一確定的真假意義.2.六個聯結詞及真值表 否定聯結詞，p是命題...
離散數學作業
離散數學集合論部分形成性考核書面作業 本課程形成性考核書面作業共3次，內容主要分別是集合論部分 圖論部分 數理邏輯部分的綜合練習，基本上是按照考試的題型 除單項選擇題外 安排練習題目，目的是通過綜合性書面作業，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點複習，爭取盡快掌握 本次形考書面作業是第...