1、.華南理工大學網絡教育學院20162017 學年度第一學期期末考試離散數學試卷（模擬卷）（客觀題電腦給分，主觀題依過程給分）教學中心：專業層次：學號：姓名：座號：注意事項 ： 1.本試卷共三 大題，滿分 100分， 考試時間 90 分鐘 ，閉卷；2. 考前請將以上各項信息填寫清楚；3.所有答案必須做在答題紙上, 做在試卷、草稿紙上無效；4 考試結束，試卷、答題紙、草稿紙一并交回。一、單項選擇題（本大題30 分，每小題 6 分）1設， P：他聰明； Q：他用功。在命題邏輯中，命題：“他既聰明又用功。 ” 可符號化為： ()APQBPQCPQDPQ【答案： A 】2下列式子 ()是永真式AQ（PQ

2、）BP（PQ）C（PQ）PD（P Q）Q【答案： C】3設 S（x）：x 是運動員， J（y）：y 是教練員， L（x，y）： x 欽佩 y。命題“所有運動員都欽佩一些教練員”的符號化公式是()A x（S（x）y（J（y）L （x， y）B x y（ S（ x）（J（y）L（x，y）C x（S（x）y（J（y）L（x，y）D y x（S（ x）（ J（ y）L（ x， y）【答案： C】4下列命題是真的是 ()A如果 A? B及 BC,則 A? CB如果 A? B 及 BC,則 ACC如果 AB 及 B? C,則 A? CD如果 AB 及 B? C,則 AC【答案： D】5設 G 是 n 有個

3、結點， m 條邊的簡單有向圖。 若 G 是連通的，則 m 的下界是（）A nB n 1C n n 1D 1 n n 1【答案： B】2二、判斷題（本大題 20 分，每小題 4 分）1. 設 A ，B 是命題公式，則蘊涵等值式為ABAB。（ × ）2、 x yA(x,y)y xA(x,y)。（ × ）3、(x)（ P(x)Q(x) ）( x) （ P(x)Q(x)）。（ ）;.4集合 A=1,2,3 上的關系 <1,1>,<2,2>,<3,3>,<1,2> 是傳遞的。（ ）5無向連通圖 G 的任意兩結點之間都存在一條路。（ ）三

4、、解答題（計算或者證明題：本大題50 分，每小題 10 分）1設命題公式為（ PQ）P）Q。（ 1）求此命題公式的真值表；（ 2）給出它的析取范式；（ 3）判斷該公式的類型。解 （1）真值表如下PQP P Q（PQ） P（P Q） P） Q001001011111100101110101（2） （P Q） P） Q（P Q） P） Q（PQ）P）Q（PQ） （Q P）1（析取范式）（ P Q） （ P Q） （P Q） （P Q）（主析取范式）（3）該公式為重言式2. 證明 前提：（ PQ），QR，R結論： P證（1）QRP（2） RP（3） Q（1）（2）析取三段論（4） （PQ）P（5）P

5、Q（4）等價轉換（6） P（3）（5）析取三段論3設 R 是集合 A = 2, 4, 5, 10, 12, 20, 25上的整除關系。(1) 給出關系 R；12 20（2） 給出 COV A10 254（3） 畫出關系 R 的哈斯圖；25（4） 給出關系 R 的極大、極小元、最大、最小元。解 R=<2,4>,<2,10>, <2,12>,<2,20>,<4,12>,<4,20>，<5,10>,<5,20>,<10,20>,<5,25>I ACovA=<2,4>,&

6、lt;2,10>, <4,12>,<4,20>，<5,10>,<10,20>,<5,25>哈斯圖如右上所示，由圖看出該偏序集沒有最大元和最小元，12、 20、 25 都是極大元，;.2 和 5 都是極小元。4求帶權圖 G 的最小生成樹，并計算它的權值。123解1CT123175. 選做題（二選一）5.1 給定權為 2， 6， 3， 9， 4；構造一顆最優二叉樹和樹權。解2346924954691569991592445623WT 4(23)342695324或23469546991591545 692423W T 3(23)242(69)535.2求帶權為 1，1，2，3，3，4，5，6， 7， 8 的最優三元樹和樹權解 112334567843345678104567810157825 15增加 0，再作表如下011233456782233456787345678712 6782