離散數(shù)學(xué)期末考試試題

1、離散數(shù)學(xué)期末考試試題一、 填空題（每空2分，合計(jì)20分）1. 設(shè)個(gè)體域?yàn)? ，。則在此解釋下公式的真值為_(kāi)。 2. 設(shè)我是大學(xué)生，我喜歡數(shù)學(xué)。命題“我是喜歡數(shù)學(xué)的大學(xué)生”為可符合化為 。3. 設(shè)，則=_，=_。4. 合式公式是永_式。5. 給定集合，在集合上定義兩種關(guān)系： , ， 則，。6. 設(shè)是群上的幺元，若且,則=_ , =_。7 公式的對(duì)偶公式為 。8. 設(shè), 是上的整除關(guān)系，則偏序集的最大元是_，極小元是_ _。9. 一棵有6個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)，有_個(gè)內(nèi)點(diǎn)；而若一棵樹(shù)有2個(gè)結(jié)點(diǎn)度數(shù)為2，一 個(gè)結(jié)點(diǎn)度數(shù)為3，3個(gè)結(jié)點(diǎn)度數(shù)為4，其余是葉結(jié)點(diǎn)，則該樹(shù)有_個(gè)葉結(jié)點(diǎn)。10. 設(shè)圖, ，若G的鄰

2、接矩陣，則=_, =_。二、選擇題（每題2分，合計(jì)20分）1下列各式中哪個(gè)不成立（ ）。 A、 ；B、；C、；D、。2謂詞公式中的 x是（ ）。 A、自由變?cè)?B、約束變?cè)?C、既是自由變?cè)质羌s束變?cè)?D、既不是自由變?cè)植皇羌s束變?cè)?集合的以下運(yùn)算律不成立的是( )。 AB CD4. 公式換名（ ）。 A. B. C. D. 。5. 設(shè)集合，是有窮集合，且，則從到有（ ）個(gè)不同的雙射函數(shù)。 A、 ； B、 ； C、 ； D、 。6設(shè)，上的等價(jià)關(guān)系， 則對(duì)應(yīng)于的的劃分是（） A B C D7. 設(shè)，則上的二元關(guān)系有（ ）個(gè)。A B. C D8下面集合（ ）關(guān)于減法運(yùn)算是封閉的。A、N

3、 ； B、 ； C、 ； D、。9.設(shè)集合，是上的二元關(guān)系，則的關(guān)系矩陣MR是( ) A B. C. D. 10 一個(gè)連通的無(wú)向圖，如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它具有一條( )A.漢密爾頓回路 B.歐拉回路 C.漢密爾頓通路 D.初級(jí)回路三、計(jì)算題（每題8分 合計(jì)40分）1 寫(xiě)出命題公式的真值表。2 集合上的偏序關(guān)系|為整除關(guān)系。設(shè)，試畫(huà)出<A, |>的哈斯圖，并求集合B和C中關(guān)于|的極大元、最大元、下界和下確界。3. 求命題公式的主析取范式。4.求下圖所示的邊賦權(quán)圖的一棵最小生成樹(shù)。5. 已知某有向圖的鄰接矩陣如下： 試求：到的長(zhǎng)度為4的有向路徑的條數(shù)。四 證明題（每題10分， 合計(jì)20分）1. 設(shè)論域D為全總個(gè)體域，謂詞G(x)：x是研究生，T(x)：x是推薦免試者，K(x)：x是統(tǒng)考選拔者。在謂詞邏輯中符號(hào)化下列各命題，推證結(jié)論的有效性?！八械难芯可蛘呤峭扑]免試者或者是統(tǒng)考選拔者；并非所有的研究生都是推