第一篇：學習《離散數學》心得體會

學習《離散數學》心得體會

計算機3班

120210324 羅 鴻

起先以為《離散數學》講的是比高數更加深奧的數學問題，其實不為然?！峨x散數學》是計算機科學與技術專業(yè)的一門重要的專業(yè)基礎課程,它在計算機科學中有著廣泛的應用。離散數學，對絕大多數學生來說是一門十分困難的課程，當然也包括我在內。開始學的時候有點蒙，加上老師講課有點口音，速度很快，課下也沒及時地去復習，所以學得不是很好。

第一章學了數理邏輯，前面的幾節(jié)學得還可以，可是后面幾節(jié)就不行了。學習謂詞時中，起初我并不知道它到底要講些什么東西，將命題拆了幾大塊，又莫名奇妙將這些小塊用聯結詞組合在一起，還對它們進行一系列的判斷，越學越沒想法。也許是自己的邏輯能力不是很好。

接下來學習了圖論，這里所說的圖并不是幾何學中的圖形，而是客觀世界中某些具體事物間聯系的一個數學抽象，用頂點代表事物，用邊表示各式物間的二元關系，如果所討論的事物之間有某種二元關系，我們就把相應的頂點練成一條邊。這種由頂點及連接這些頂點的邊所組成的圖就是圖論中所研究的圖。由于它關系著客觀世界的事物，所以對于解決實際問題是相當有效的。這一章概念很多，也讓我也感覺很亂，這一章基本都是自學的，因為老師很快就過了，自己也是迷糊迷糊的。所以只能在課后多下功夫了。

通過學習這一門課程，讓我明白了很多。我們不能夠過多的去依賴老師，去抱怨老師的不好，往往是我們做的不夠好。在大學主要是靠自學，學會怎樣去學 1習。正如老師所說的“不以規(guī)矩，不能成方圓”。最重要的就是要找到合適自己解決問題的方法。學習任何課程，都是為了解決實際問題。離散數學也是如此，有了對概念的理解。有了正確的思考問題的方式，解決問題的時候就不會走彎路了，也就說基本的解決問題的方法就自然而然地掌握了。

第二篇：離散數學學習心得體會

離散數學學習心得體會

我相信很多人聽過一個謎題，在你面前有兩個神，一個天使一個惡魔，你不知道哪個是天使哪個是惡魔，同時你面前有兩條你不知道通往何處的路，一條通往天堂，一條通往地獄。但是我們知道天使只說真話，惡魔只說假話，現在你只能向你面前的某一個神問一個問題，請問怎么能夠問出通往天堂的路。

只需要問其中一個神：“另一個神會說哪條路去天堂？”。

假設你問的是天使，因為惡魔會騙人指向去地獄的路，天使只說實話。所以天使會如實的指向地獄的路。

假設你問的是惡魔，天使會指向去天堂的路，但是惡魔只說謊話，所以他會指向去地獄的路。

也就是說無論是你問的是什么神，他們都會指向去地獄的那條路。事件P為真，事件Q為假時，P且Q為假。仔細一想，天使說的話必定為真，惡魔說的話必定為假那我們那我們把他們兩個的話取且運算，就必定為假。

我在第一次解決這個問題時有一些驚訝，很多看上去很淺顯而又比較簡單的知識在應用時，我卻沒有任何意識，這就是因為我從來沒有去理解過這些知識。

從初中開始我們對函數就耳濡目染，學習了編程之后我對函數的理解就是輸入一個值進入函數，函數就返回一個值。不過現在對函數的理解變?yōu)榱擞成?，函數是從某一個集合映射到另一個集合的關系。在應用時，函數需要理解的概念不多。但是我們對函數必須有一些思考，不能廉價的認為函數就是某個公式然后代入數字計算。我們將函數想象成映射或者是轉換。

從數學的角度來說，關系是笛卡兒的子集，就是一個二維表，還可以是一個矩陣，一個有向圖

n元關系，多個（>2）集合的笛卡兒的子集，集合的個數叫關系的階叫做n.類似n個數

可以用集合，圖，矩陣來表示二元關系

關于離散數學中的關系，會出現以下幾個概念，二元關系，等價關系，整除關系。

第六章“圖”和第七章“樹及其應川”可以歸為“圖論”。在剛接觸到“圖”這一章的時候我是抱著好奇之心去學習的，因為這章都足關于“圖”，想了解一下和幾何圖形的差別，所以覺得善氏幾何的我應該能夠把它學好。但足不可否認，隨著知識的深入，這一章一定會比前面的更難理解，更難學。因此，上課的時候聽得格外認真，我才真正了解到它并不足枯燥乏味的，它的用途非常廣泛．并幾應用于我們整個日常生活中。比如：怎樣布線才能使每一部電話互相連通，并幾花費最??？從首府到母州州府的最短路線足什么？ , n項任務怎樣才能最有效地由 n 個人完成？管道網絡中從源點到集匯點的單位時間最大流是多少？一個計算機芯片需要多少層才能使得同一層的路線互不相交？怎樣安排一個體育聯盟季度賽的口程表使其在最少的周數內完成？一位流動推銷員要以怎樣的順序到達每一個城市才能使得旅行時間最短？我們能用4 種顏色來為每張地圖的各個區(qū)域著色并使得相鄰的區(qū)域具有不同的顏色嗎？這些問題以及其他一些實際問題都涉及“圖論”。這里所說的圖并不是幾何學中的圖形，而足客觀世界中某些具體事物間聯系的一個數學抽象，用頂點代表事物，用 邊表示各式物間的二元關系，如果所討論的事物之問有某種二元關系，我們就把相應的項點練成一條邊。這種由頂點及連接這些頂點的邊所組成的圖就是圖論中所研究的圖。由于它關系著客觀世界的事物，所以對于解決實際問題是相當有效的。哥尼斯堡橋問題（七橋問題），這個共名的數學難題．在經過如此漫民的時間最終還是瑞士數學家歐拉利川圖論解決 它并得出沒有一種方法使得從這塊陸地中的任意一塊開始，通過每一座橋恰好一次再回到原點。

樹是指沒有回路的連通圖。它是連通圖中最簡單的一類圖，許多問題對一般連通圖未能解決或者沒有簡單的方法，而對于樹，則己圓滿解決，幾方法較為簡單。而幾在許多不同領域中有著廣泛的應川。例如家譜圖就是其中之一。如果將每個人用一個項點來表示，并幾在父子之問連一條邊，便得到一個樹狀圖。圖論中最著名的應該就是圖的染色問題。這個問題的研究來源于著名的四色問題。四色問題是圖論中也許是全部數學中最出名、最難得一個問題之一。所謂四色猜想就足在平面中任何一張地圖，總可以用至多四種顏色給每一個國家染色，使得任何相鄰岡家的顏色是不同的。四色問題粗看起來似乎與我們所討論的圖沒有什么聯系。其實也是可以轉化為圖論中的問題來討淪。首先從地圖出發(fā)來構作一個圖，讓每一個項點代表地圖的一個區(qū)域，如果兩個區(qū)域有一段公共邊界線，就在相應的頂點之間連上一條邊。由于地圖中每一塊區(qū)域對應圖的一個頂點，兩個相鄰項點對應兩個相鄰的區(qū)域。所以對地圖染色使相鄰的區(qū)域染以不同的顏色相當于對圖的每個頂點染以相應的一種顏色，使得相鄰的頂點有不同的顏色?？傊瑘D淪是數學科學的一個分支，而四色問題足典型的圖論課題。通過對圖淪的初步理解和認識，我深深地認識到，圖論的概念雖然有其直觀、通俗的方面．但是這許多口常生活川語被引入圖淪后就都有廠其嚴格、確切的含義。我們既要學會通過術語的通俗含義更快、更好地理解圖淪概念，又要注意保持術語起碼的嚴格。

對于有向樹，有當略去其所有的有向邊的方向時我們可以得到的無向圖如果是樹那么它就是有向樹。一棵平凡的有向樹，如果他的結點中恰有一個是入度為0的其他的入度都是1那么它就是一個根樹，也可以叫它外向樹。入度為0的結點就是根。出度為0的結點就是葉。出度大于0的就是內點。內點和根統稱為分支點。從根到任意一個結點的通路長度就可以反映出它的層數，所有的結點中層數最大的就叫做高，反映到實際的幾何圖形上也可以看出高的實際意義與深度比較類似。圖在家族關系的描述里有如果一個結點到另外一個結點可達那么可以叫它之前的為祖先，后面的是后代，而對于直接相連的有著父親兒子以及兄弟之間的關系描述。如果再對樹的層級進行細分又可以有兄弟的描述。這里有規(guī)定了每一個層次上的結點的次序的根樹就可以叫它有序樹。在根樹的實際應用中有著k元樹的概念。如果每個分支點最多有k個兒子那么就可以叫它為k元樹。如果每個結點都有著k個兒子。那么t就是k元完全樹。對于有序的k元完全樹，我們又可以叫它為k元有序完全樹。特殊的，在k元完全樹里取其某個分支點作為根結點以及其全體后代形成的導出子樹又可以稱為是以那個點為根結點子樹。特殊的二元有序樹的每個結點可以有左子樹與右子樹。每個結點最多有兩個子樹。利用樹的性質以及握手定理可以得出k元完全樹的公式（k-1）*i=t-1。在這里的證明題目可以有著多種的解法?？梢杂枚x列式，分別對葉以及分支點用歸納法，使用握手定力以及公式。要開拓思路。森林可以生成樹，根樹可以轉化為二元樹。根樹轉化為二元樹的重點在于保留父親與左邊第一個兒子的連線，同時還要將兄弟用從左到右的有向邊進行連接。轉化的要點在于弟弟變成右兒子。在此基礎上還有森林轉化為二元樹的算法。算法是先將森林中的每一棵樹都轉化為二元樹，再將剩下的每一棵二元樹作為左邊的二元樹的根的右子樹，直到所有的二元樹都連成一顆二元樹為止。

然后是樹的遍歷。樹的遍歷中有如果對其對根的操作進行分類，有先根次序、中根次序以及后根次序。顧名思義進行調用以及理解。

通過對于這門課的學習，使我理解了數學與計算機之間的很多聯系，鍛煉我們的思維方式，對待問題要多方面考慮。離散數學也是學習數學科學中所有高級課程的必經之路，這門課將很多東西聯系了起來，也使我對于數學有了新的認識。

第三篇：離散數學心得體會

離散數學心得體會

離散數學，對絕大多數學生來說是一門十分困難的課程，當然也包括我在內，而當初選這門課是想挑戰(zhàn)一下自己。通過這一學期的學習，我對這門課程有一些初步的了解，現在的心情和當初也很不相同。

在還沒有接觸的時候，看見課本就想退縮，心想：這是什么課程啊，這叫數學嗎，這些符號都是之前沒有見過的呢！但是既然都說是挑戰(zhàn)就沒有退縮的道理。雖然不能說是抱著“視死如歸”的精神，至少能說是忐忑不安。第一次聽老師講課的時候已經是落后別人兩次課，前面的知識都是自己看書，所以難免有些看不懂，在聽老師講課的時候有些定義性的東西就會混淆，我自認為是個越挫越勇的人，并沒有因此退縮。超乎想象的是，老師講課好仔細，好詳細，因為前面的知識是為后面做鋪墊，所以在后面老師經常強調，那么，我錯過的東西也都掌握了。

在聽過老師講解以后，我覺得前三章自己都能很好的掌握。后面的開始深入一些，對于好多以前沒有接觸過的名詞定義不能馬上理解，但是只要跟著老師的思維走，上課認真聽講，課后看一下書本就能懂。有了這些認知，我覺得這門課的難點在于課程比較枯燥，好多理論的知識需要我們去理解。

前三章主要是認識邏輯語言符號，了解了數理邏輯的特點，并做一些簡單的邏輯推理和運算。這些知識都是以前所學的進一步轉換，只要將數學的函數符號邏輯化就行。也就是說，那些符號知識形式上的不同，實質上是一樣的。不同的是，之前的數學只需要運用結論證明其他的案例等。但是邏輯數學不僅要知其然還要知其所以然，運用結論正結論。即使如此，我還是覺得這幾章學著很輕松，只要熟練掌握公式定理就會覺得離散數學并不像之前想象的那么困難。第四章講的是關系。這一章，進一步認識、運用數理邏輯語言，熟練強化練習，深入理解。這一章的難度相較于前幾章要繁瑣些，有很多的符號轉換，運算，運算過程很復雜。對于計算能力不強的我來說，這一章或許是最吃力的，即使知道原理也需要通過大量的練習強化鞏固，而這其中用到的還有線性代數里面的矩陣。第五章學的是函數，定義和高中所學一樣，只不過是把它轉換運用于數理邏輯，并用邏輯符號進行運算。雖說如此，但是這其中仍然有更深層次的概念和邏輯公式，如果單純的用原有的思維是很難想透徹的。

第六章“圖”和第七章“樹及其應用”可以歸為“圖論”。在剛接觸到“圖”這一章的時候我是抱著好奇之心去學習的，因為這章都是關于“圖”，想了解一下和幾何圖形的差別，所以覺得善長幾何的我應該能夠把它學好。但是不可否認，隨著知識的深入，這一章一定會比前面的更難理解，更難學。因此，上課的時候聽得格外認真，課后還找了一些相關書籍閱覽。在看過這些書籍以后，我才真正了解到它并不是枯燥乏味的，它的用途非常廣泛，并且應用于我們整個日常生活中。比如：怎樣布線才能使每一部電話互相連通，并且花費最?。繌氖赘矫恐葜莞淖疃搪肪€是什么？n項任務怎樣才能最有效地由n個人完成？管道網絡中從源點到集匯點的單位時間最大流是多少？一個計算機芯片需要多少層才能使得同一層的路線互不相交？怎樣安排一個體育聯盟季度賽的日程表使其在最少的周數內完成？一位流動推銷員要以怎樣的順序到達每一個城市才能使得旅行時間最短？我們能用4種顏色來為每張地圖的各個區(qū)域著色并使得相鄰的區(qū)域具有不同的顏色嗎？這些問題以及其他一些實際問題都涉及“圖論”。

這里所說的圖并不是幾何學中的圖形，而是客觀世界中某些具體事物間聯系的一個數學抽象，用頂點代表事物，用邊表示各式物間的二元關系，如果所討論的事物之間有某種二元關系，我們就把相應的頂點練成一條邊。這種由頂點及連接這些頂點的邊所組成的圖就是圖論中所研究的圖。由于它關系著客觀世界的事物，所以對于解決實際問題是相當有效的。哥尼斯堡橋問題（七橋問題），這個著名的數學難題，在經過如此漫長的時間最終還是瑞士數學家歐拉利用圖論解決了它，并得出沒有一種方法使得從這塊陸地中的任意一塊開始，通

過每一座橋恰好一次再回到原點。

樹是指沒有回路的連通圖。它是連通圖中最簡單的一類圖，許多問題對一般連通圖未能解決或者沒有簡單的方法，而對于樹，則已圓滿解決，且方法較為簡單。而且在許多不同領域中有著廣泛的應用。例如家譜圖就是其中之一。如果將每個人用一個頂點來表示，并且在父子之間連一條邊，便得到一個樹狀圖。

圖論中最著名的應該就是圖的染色問題。這個問題的研究來源于著名的四色問題。四色問題是圖論中也許是全部數學中最出名、最難得一個問題之一。所謂四色猜想就是在平面上任何一張地圖，總可以用至多四種顏色給每一個國家染色，使得任何相鄰國家的顏色是不同的。四色問題粗看起來似乎與我們所討論的圖沒有什么聯系。其實也是可以轉化為圖論中的問題來討論。首先從地圖出發(fā)來構作一個圖，讓每一個頂點代表地圖的一個區(qū)域，如果兩個區(qū)域有一段公共邊界線，就在相應的頂點之間連上一條邊。由于地圖中每一塊區(qū)域對應圖的一個頂點，兩個相鄰頂點對應兩個相鄰的區(qū)域。所以對地圖染色使相鄰的區(qū)域染以不同的顏色相當于對圖的每個頂點染以相應的一種顏色，使得相鄰的頂點有不同的顏色?？傊瑘D論是數學科學的一個分支，而四色問題是典型的圖論課題。

通過對圖論的初步理解和認識，我深深地認識到，圖論的概念雖然有其直觀、通俗的方面，但是這許多日常生活用語被引入圖論后就都有了其嚴格、確切的含義。我們既要學會通過術語的通俗含義更快、更好地理解圖論概念，又要注意保持術語起碼的嚴格。

本以為枯燥乏味的離散數學竟然會是貼近生活是我意想不到的，這些歷史難題等等，都讓我對它產生了一定的興趣，雖然不可否認的是，對我來說它確實是一門很難很深奧很抽象的課程，但是仍然不減我對圖論產生的興趣，或許這也就是我選擇這門課程最大的收獲吧。

第四篇：學習離散數學總結范文

學習離散數學的心得體會

姓名：

學號：1

班級：計算機

離散數學，對絕大多數學生來說應該都會是一門十分困難的課程，當然也包括我在內。通過這一學期的學習，我對這門課程有一些初步的了解，現在的心情和當初也很不相同。

在還沒有接觸的時候，看見課本就想退縮，心想：這是什么課程啊，這叫數學嗎，這些符號都是之前沒有見過的呢！但是既然都說是挑戰(zhàn)就沒有退縮的道理。雖然不能說是抱著“視死如歸”的精神，至少能說是忐忑不安。在聽老師講課的時候有些定義性的東西總會混淆，我自認為是個越挫越勇的人，并沒有因此退縮。超乎想象的是，老師講課好仔細，好詳細，因為前面的知識是為后面做鋪墊，所以在后面老師經常強調。

而且老師每兩次課都會布置作業(yè)，這讓我們在完成作業(yè)的時候對上過的內容進行了加深，有利于我們更好的學習離散數學。而且每次作業(yè)老師都很認真批改，錯誤的地方都會給你圈出來，以便于我們自己更好的完成訂正。錯誤的地方，經過老師認真仔細的講解，更讓我們對知識點及解題技巧有了一定的認知。當一題題目本來不會做錯了但是經過老師講解聽講到會做這題題目的時候，這種成就感還是相當不錯的呢。難得有這么認真又負責的老師，讓我本來對數學沒什么興趣的人居然也會漸漸地對數學產生了興趣。有了這些認知，我覺得這門課的難點在于課程比較枯燥，好多理論的知識需要我們去理解。

前三章主要是認識邏輯語言符號，了解了數理邏輯的特點，并做一些簡單的邏輯推理和運算。這些知識都是以前所學的進一步轉換，只要將數學的函數符號邏輯化就行。也就是說，那些符號知識形式上的不同，實質上是一樣的。不同的是，之前的數學只需要運用結論證明其他的案例等。但是邏輯數學不僅要知其然還要知其所以然，運用結論正結論。即使如此，我還是覺得這幾章學著很輕松，只要熟練掌握公式定理就會覺得離散數學并不像之前想象的那么困難。

第四章講的是關系。這一章，進一步認識、運用數理邏輯語言，熟練強化練習，深入理解。這一章的難度相較于前幾章要繁瑣些，有很多的符號轉換，運算，運算過程很復雜。對于計算能力不強的我來說，這一章或許是最吃力的，即使知道原理也需要通過大量的練習強化鞏固，而這其中用到的還有線性代數里面的矩陣。

第五章學的是函數，定義和高中所學一樣，只不過是把它轉換運用于數理邏輯，并用邏輯符號進行運算。雖說如此，但是這其中仍然有更深層次的概念和邏輯公式，如果單純的用原有的思維是很難想透徹的。

第六章“圖”和第七章“樹及其應用”可以歸為“圖論”。在剛接觸到“圖”這一章的時候我是抱著好奇之心去學習的，因為這章都是關于“圖”，想了解一下和幾何圖形的差別，所以覺得善長幾何的我應該能夠把它學好。但是不可否認，隨著知識的深入，這一章一定會比前面的更難理解，更難學。因此，上課的時候聽得格外認真，課后還找了一些相關書籍閱覽。在看過這些書籍以后，我才真正了解到它并不是枯燥乏味的，它的用途非常廣泛，并且應用于我們整個日常生活中。比如：怎樣布線才能使每一部電話互相連通，并且花費最??？從首府到每州州府的最短路線是什么？n項任務怎樣才能最有效地由n個人完成？管道網絡中從源點到集匯點的單位時間最大流是多少？一個計算機芯片需要多少層才能使得同一層的路線互不相交？怎樣安排一個體育聯盟季度賽的日程表使其在最少的周數內完成？一位流動推銷員要以怎樣的順序到達每一個城市才能使得旅行時間最短？我們能用4種顏色來為每張地圖的各個區(qū)域著色并使得相鄰的區(qū)域具有不同的顏色嗎？這些問題以及其他一些實際問題都涉及“圖論”。

這里所說的圖并不是幾何學中的圖形，而是客觀世界中某些具體事物間聯系的一個數學抽象，用頂點代表事物，用邊表示各式物間的二元關系，如果所討論的事物之間有某種二元關系，我們就把相應的頂點練成一條邊。這種由頂點及連接這些頂點的邊所組成的圖就是圖論中所研究的圖。由于它關系著客觀世界的事物，所以對于解決實際問題是相當有效的。哥尼斯堡橋問題（七橋問題），這個著名的數學難題，在經過如此漫長的時間最終還是瑞士數學家歐拉利用圖論解決了它，并得出沒有一種方法使得從這塊陸地中的任意一塊開始，通過每一座橋恰好一次再回到原點。

樹是指沒有回路的連通圖。它是連通圖中最簡單的一類圖，許多問題對一般連通圖未能解決或者沒有簡單的方法，而對于樹，則已圓滿解決，且方法較為簡單。而且在許多不同領域中有著廣泛的應用。例如家譜圖就是其中之一。如果將每個人用一個頂點來表示，并且在父子之間連一條邊，便得到一個樹狀圖。

圖論中最著名的應該就是圖的染色問題。這個問題的研究來源于著名的四色問題。四色問題是圖論中也許是全部數學中最出名、最難得一個問題之一。所謂四色猜想就是在平面上任何一張地圖，總可以用至多四種顏色給每一個國家染色，使得任何相鄰國家的顏色是不同的。四色問題粗看起來似乎與我們所討論的圖沒有什么聯系。其實也是可以轉化為圖論中的問題來討論。首先從地圖出發(fā)來構作一個圖，讓每一個頂點代表地圖的一個區(qū)域，如果兩個區(qū)域有一段公共邊界線，就在相應的頂點之間連上一條邊。由于地圖中每一塊區(qū)域對應圖的一個頂點，兩個相鄰頂點對應兩個相鄰的區(qū)域。所以對地圖染色使相鄰的區(qū)域染以不同的顏色相當于對圖的每個頂點染以相應的一種顏色，使得相鄰的頂點有不同的顏色?？傊瑘D論是數學科學的一個分支，而四色問題是典型的圖論課題。

通過對圖論的初步理解和認識，我深深地認識到，圖論的概念雖然有其直觀、通俗的方面，但是這許多日常生活用語被引入圖論后就都有了其嚴格、確切的含義。我們既要學會通過術語的通俗含義更快、更好地理解圖論概念，又要注意保持術語起碼的嚴格。

本以為枯燥乏味的離散數學竟然會是貼近生活，這些歷史難題等等，都讓我對它產生了一定的興趣，雖然不可否認的是，對我來說它確實是一門很難很深奧很抽象的課程，但是仍然不減我對圖論產生的興趣，或許這也就是我選擇這門課程最大的收獲吧。

第五篇：離散數學

離散數學課件作業(yè)

第一部分 集合論

第一章集合的基本概念和運算

1-1 設集合 A ={1，{2}，a，4，3}，下面命題為真是[ B ]

A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2} ? A。

1-2 A,B,C 為任意集合，則他們的共同子集是[ D ]

A．C；B．A；C．B；D．?。

1-3 設 S = {N，Z，Q，R}，判斷下列命題是否成立 ？

（1）N ? Q，Q ∈S，則 N ? S［不成立］

（2）-1 ∈Z，Z ∈S，則-1 ∈S［不成立］

1-4 設集合 A ={3，4}，B = {4，3} ∩ ?，C = {4，3} ∩{ ? }，D ={ 3，4，? }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F = { 4，?，3，3}，試問哪兩個集合之間可用等號表示 ？

答：A = E；B = C；D = F

1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 }

（2）A = { x│x ∈N 且 3－x 〈 3 }

答：（1）A = { 0，1，2，3 }；

（2）A = { 1，2，3，4，……} = Z+；

第二章二元關系

2-1 給定 X =（3, 2，1），R 是 X 上的二元關系，其表達式如下：

R = {〈x，y〉x，y ∈X 且 x≤ y }

求：(1)domR =?;(2)ranR =?;(3)R 的性質。

答：R = {<2，3>，<1,2>，<1,3>}；

DomR={R中所有有序對的x}={2,1,1}={2,1};

RanR={R中所有有序對的y}={3,2,3}={3,2}；

R 的性質:反自反,反對稱,傳遞性質.2-2 設 R 是正整數集合上的關系，由方程 x + 3y = 12 決定，即

R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，試求：

（1）R 的列元表達式；（2）給出 dom（R。R）。

答：根據方程式有：y=4-x/3，x 只能取 3，6,9。

（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；

至于(2),望大家認真完成合成運算 R。R={<3,3>}.然后,給出 R。R 的定義域,即

（2）dom（R。R）= {3}。

2-3 判斷下列映射 f 是否是 A 到 B 的函數；并對其中的 f：A→B 指出他的性質，即

是否單射、滿射和雙射，并說明為什么。

（1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。

（2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。

（3）A = B = R，f=x。

（4）A = B = N，f=x2。

（5）A = B = N，f = x + 1。

答：（1）是 A 到 B 的函數，是滿射而不是單射；

（2）是雙射；

（3）是雙射；

（4）是單射，而不是滿射；

（5）是單射而不是滿射。

2-4 設 A ={1，2，3，4}，A 上的二元關系

R ={〈x，y〉︱（x-y）能被3整除}，則自然映射 g：A→A/R使 g(1)=[C]

A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。

2-5 設 A ={1，2，3}，則商集A/IA =[D]

A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。

2-6．設ｆ(x)＝x+1，ｇ(x)＝x-1 都是從實數集合Ｒ到Ｒ的函數，則ｆ。ｇ＝[C]

A．x+1；B．x-1；C．x；D．x2。

第三章 結構代數(群論初步)

3-1 給出集合及二元運算，闡述是否代數系統，何種代數系統 ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元運算 *是普通乘法。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元運算。定義如下：對于所有 ai，aj ∈S2，都有 ai。aj = ai。

（3）S3 = {0，1}，二元運算 * 是普通乘法。

答：（1）二元運算*在S1上不封閉．所以，＂S1，*＂不能構成代數系統。

（2）由二元運算的定義不難知道。在 S2 內是封閉的，所以，〈S2?！禈嫵纱鷶?/p>

系統；然后看該代數系統的類型：該代數系統只是半群。

（3）很明顯，〈{0，1}，*〉構成代數系統；滿足結合律，為半群；1是幺元，為獨異

點；而 0 為零元；結論：僅為獨異點，而不是群。

3-2 在自然數集合上，下列那種運算是可結合的［A］

A．x*y = max(x,y)；B．x*y = 2x+y ；

C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 設 Z 為整數集合，在 Z 上定義二元運算。，對于所有 x，y ∈Z都有

x。y=x + y，試問〈Z?！的芊駱嫵扇?，為什麼 ？

答：由題已知，集合Z滿足封閉性；二元運算滿足結合律，依此集合Z為半群；有幺元為 －5，為獨異點.假設代數系統的幺元是集合中的元素 e,則一個方程來自于二元運算定義, 即e。x= e + x，一個方程來自該特殊元素的定義的性質,即e。x = x.由此而來的兩個方程聯立結果就有: e+x=x 成立.削去 x,e=0 的結果不是就有了嗎!；每個元素都有逆.求每個元素的逆元素,也要解聯方程,如同求幺元一樣的道理；結論是：代數系統〈 Z。〉構成群。

第二部分圖論方法

第四章 圖

4-1 10 個頂點的簡單圖 G 中有 4 個奇度頂點，問 G 的補圖中有幾個偶數度頂點 ？ 答：因為10階完全圖的每個頂點的度數都是n-1=9――為奇數。這樣一來，一個無向簡單圖 G 的某頂點的度數是奇數，其補圖的相應頂點必偶數，因為一個偶數與一個奇數之和才是奇數．所以，Ｇ的補圖中應有 10-4＝6 個奇數度頂點。

4-2 是非判斷：無向圖G中有10條邊,4個3度頂點,其余頂點度數全是2,共有 8 個頂點.[是]

4-3 填空補缺：1條邊的圖 G 中，所有頂點的度數之和為[2]

第五章樹

5-1握手定理的應用（指無向樹）

（1）在一棵樹中有 7 片樹葉，3 個 3 度頂點，其余都是 4 度頂點，問有(有1個4度頂點)個？

（2）一棵樹有兩個 4 度頂點，3 個 3 度頂點，其余都是樹葉，問有(9個1度頂點)片？

5-2 一棵樹中有 i 個頂點的度數為 i（i=2，…k），其余頂點都是樹葉(即一度頂點)，問樹葉多少片？設有x片,則 x=

答：假設有 x 片樹葉，根據握手定理和樹的頂點與邊數的關系，有關于樹葉的方程，解方程得到樹葉數 x = Σi（i—2）i + 2，（i = 2，3，……k）。

5-3 求最優(yōu) 2 元樹：用 Huffman 算法求帶權為 1，2，3，5，7，8 的最優(yōu) 2 元樹 T。試問：（1）T 的權 W（T）？（2）樹高幾層 ？

答：用 Huffman 算法，以 1，2，3，5，7，8 為權，最優(yōu) 2 元樹 T ；然后，計算并回答所求問題：（1）T 的權 W（T）= 61；（2）樹高幾層：4 層樹高。

5-4以下給出的符號串集合中，那些是前綴碼？將結果填入[]內.B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]

5-5(是非判斷題)11階無向連通圖G中17條邊，其任一棵生成樹 T 中必有6條樹枝 [非]

5-6(是非判斷題)二元正則樹有奇數個頂點。[是]

5-7 在某次通信中 a，b，c，d，e 出現的頻率分別為 5%;10%;20%;30%;35%.求傳輸他們的最佳前綴碼。

1、最優(yōu)二元樹 T；2.每個字母的碼字；

答：每個字母出現頻率分別為：G、D、B、E、Y：14%，O：28%；(也可以不歸一,某符號

出現次數即為權，如右下圖).。100（近似）7.。563..4。282..2..2。..1..14141414111

1所以，得到編碼如下：G（000），D（001），B（100），E（101），Y（01），O（11）。

第三部分邏輯推理理論

第六章 命題邏輯

6-1 判斷下列語句是否命題，簡單命題或復合命題。

（1）2月 17 號新學期開始。[真命題]

（2）離散數學很重要。[真命題]

（3）離散數學難學嗎 ？[真命題]

（4）C 語言具有高級語言的簡潔性和匯編語言的靈活性。[復合命題]

（5）x + 5 大于 2。[真命題]

（6）今天沒有下雨，也沒有太陽，是陰天。[復合命題]

6-2 將下列命題符號化.（1）2 是偶素數。

（2）小李不是不聰明，而是不好學。

（3）明天考試英語或考數學。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

答：（1）符號化為： p ∧ q。

（2）符號化為：p ∧ ﹃q。

（3）符號化為：p ∨ q。

（4）符號化為：（﹃p ∧ q）∨（p ∧ ﹃q）。

6-3分別用等值演算法,真值表法,主析取范式法,判斷下列命題公式的類型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；

（2）Σ（0，1，2，3）；

（3）Σ（1，3）。

以下兩題(6-4;6-5)為選擇題,將正確者填入[]內.6-4 令 p：經一塹；q：長一智。命題’’只有經一塹，才能長一智’’符號化為[B]

A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p

6-5 p：天氣好；q：我去游玩．命題 ”如果天氣好，則我去游玩” 符號化為［B］

A． p→q；B．q→p；C．p∧q；D．﹁q→p

6-6證明題:用不同方法(必須有構造證明法)判斷推理結果是否正確。

如果今天下雨，則明天不上體育課。今天下雨了。所以，明天沒有上體育課。答：將公式分成前提及結論。

前提：（p→﹃q），p；

結論：﹃q；

證明：（1）（p→﹃q）前提引入

（2）p前提引入

（3）（p→﹃q）∧p（1）（2）假言推理

（4）﹃q

要證明的結論與證明結果一致，所以推理正確。

第七章謂詞邏輯

7-1 在謂詞邏輯中用 0 元謂詞將下列命題符號化

（1）這臺機器不能用。

（2）如果 2 ＞ 3，則 2 ＞ 5。

答：（1）﹃F（a）。

（2）L（a，b）→ H（a，z）。

7-2 填空補缺題：設域為整數集合Ｚ，命題?x?y彐z（x-y=z）的真值為（0）

7-3在謂詞邏輯中將下列命題符號化

（1）有的馬比所有的牛跑得慢。

（2）人固有一死。

答：（1）符號化為：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。

（2）與（1）相仿，要注意量詞、聯結詞間的搭配：

x（F（x）→y（G（y）→ H（x，y）））。

《附錄》習題符號集

? 空集, ∪ 并, ∩ 交,⊕ 對稱差,～ 絕對補,∑ 累加或主析取范式表達式縮寫 , － 普通減法, ÷ 普通除法, ㏑ 自然對數, ㏒ 對數，﹃ 非，?量詞 ”所有”，”每個”，∨ 析取聯結詞，∧ 合取聯結詞，彐 量詞”存在”，”有的”。

2010年8月12號。