如何學好離散數學 離散數學是現代數學的一個重要分支，是計算機科學中基礎理論的核心課程。離散數學以研究離散量的結構和相互間的關係為主要目標，其研究物件一般地是有限個或可數個元素，因此他充分描述了計算機科學離散性的特點。由於離散數學在計算機科學中的重要性，因此，許多大學都把它作為研究生入學考試的專業課程中的一門，或者是一門中的一部分。 作為計算機系的一門課程，離散數學有與其它課程相通相似的部分，當然也有它自身的特點，現在我們就它作為考試內容時具有的特點作一個簡要的分析。 1、定義和定理多。 離散數學是建立在大量定義上面的邏輯推理學科。因而對概念的理解是我們學習這門學科的核心。在這些概念的基礎上，特別要注意概念之間的聯絡，而描述這些聯絡的實體則是大量的定理和性質。 在考試中的一部分內容就是考察大家對定義和定理的識記、理解和運用。如2002年上海交通大學的試題，問什麼是相容關係。如果知道的話，很容易得分；如果不清楚，那麼無論如何也得不到分數的。這型別題目往往因其難度低而在複習中被忽視。實際上這是一種相當錯誤的認識，在研究生入學考試的專業課試題中，經常出現直接考查對某知識點的識記的題目。對於這種題目，考生應該能夠準確、全面、完整地再現此知識點。任何的模糊和遺漏，都會造成極為可惜的失分。我們建議讀者，在複習的時候，對重要知識的記憶，務必以上面提到的“準確、全面、完整”為標準來要求自己，不能達到，就說明還不過關，還要下工夫。關於這一點，在後續章節中我們仍然會強調，使之貫穿於整個離散數學的複習過程中。 離散數學的定義主要分佈在集合論的關係和函式部分，還有代數系統的群、環、域、格和布林代數中。一定要很好地識記和理解。 2、方法性強。 離散數學的證明題中，方法性是非常強的，如果知道一道題用怎樣的方法證明，很輕易就可以證出來，反之則事倍功半。所以在平常複習中，要善於總結，那麼遇到比較陌生的題也可以遊刃有餘了。在本書中，我們為讀者總結了不少解題方法。讀者首先應該熟悉並且會用這些方法。同時我們還鼓勵讀者勤于思考，對於一道題，儘可能地多探討幾種解法。 3、有窮性。 由於離散數學較為“呆板”，出新題比較困難，不管什麼考試，許多題目是陳題，或者稍作變化的來的。“熟讀唐詩三百首，不會做詩也會吟。”如果拿到一本習題集，從頭到尾做過，甚至背會的話。那麼，在考場上就會發現絕大多數題見過或似曾相識。這時，要取得較好的成績也就不是太難的事情了。 本書是專門針對研究生入學考試而編寫的，適合於讀者對研究生入學考試的複習。如果還有時間的話，我們可以推薦兩本習題集。一本是左孝凌老師等編寫的《離散數學理論、分析、題解》，另一套有三本，是耿素雲老師等編寫的《離散數學習題集》。這兩套書大多數題都是相同的，只是由於某些符號和定義的不同，使得題目的設定和解法有些不同而已。 現在我們就分析一下研究生入學考試有哪些題型，以及我們應如何應付。 1、基礎題 基礎題就是考察對定義的識記，以及簡單的證明和推理。題目主要集中在數理邏輯部分和集合論部分。這些題目不需要思考，很容易上手。 這一部分的題目主要問題是要防止粗心大意和對定義記憶似是而非而丟的分數。不重視這一點的人將會在考試中吃大虧。如在主合取正規化中，極大項編碼對應的指派與真值表對應的指派相反，這一點在許多的參考書裡也會犯錯誤；還有是要防止沒有按照一定的方法而引起的錯誤，如我們在數理邏輯或者集合論裡作等價推演，可以省略若干不重要的步驟，只要老師和考生都清楚就可以了，而在推理理論裡則不能省略任何步驟，否則被認為是邏輯錯誤。 我們在學習中，還要注意融會貫通，例如，數理邏輯和集合論是相通的，因此記憶或者總結方法的時候可以綜合起來，這樣便於比較和理解。 2、定理應用題 本部分是最“死”的一部分，它主要體現了離散數學的方法性強的特點。並且這一部分佔了考試內容的大部分，我們必須在這一部分下功夫，記住了各種方法，也就拿到了離散數學的大部分分數。 下面我們就列出常用的幾種應用： ●證明等價關係：即要證明關係有自反、對稱、傳遞的性質。 ●證明偏序關係：即要證明關係有自反、反對稱、傳遞的性質。（特殊關係的證明就列出來兩種，要證明剩下的幾種只需要結合定義來進行）。 ●證明滿射：函式f：X??Y，即要證明對於任意的y??Y，都有x??X，使得f(x)=y。 ●證明入射：函式f：X??Y，即要證明對於任意的x1、x2??X，且x1≠x2，則f(x1) ≠f(x2)；或者對於任意的f(x1)=f(x2)，則有x1=x2。 ●證明集合等勢：即證明兩個集合中存在雙射。有三種情況：第一、證明兩個具體的集合等勢，用構造法，或者直接構造一個雙射，或者構造兩個集合相互間的入射；第二、已知某個集合的基數，如果為??，就設它和R之間存在雙射f，然後透過f的性質推出另外的雙射，因此等勢；如果為??0，則設和N之間存在雙射；第三、已知兩個集合等勢，然後再證明另外的兩個集合等勢，這時，先設已知的兩個集合存在雙射，然後根據剩下題設條件證明要證的兩個集合存在雙射。 ●證明群：即要證明代數系統封閉、可結合、有么元和逆元。（同樣，這一部分能夠作為證明題的概念更多，要結合定義把它們全部搞透徹）。 ●證明子群：雖然子群的證明定理有兩個，但如果考證明子群的話，通常是第二個定理，即設
如何學好離散數學 離散數學是現代數學的一個重要分支，是計算機科學中基礎理論的核心課程。離散數學以研究離散量的結構和相互間的關係為主要目標，其研究物件一般地是有限個或可數個元素，因此他充分描述了計算機科學離散性的特點。由於離散數學在計算機科學中的重要性，因此，許多大學都把它作為研究生入學考試的專業課程中的一門，或者是一門中的一部分。 作為計算機系的一門課程，離散數學有與其它課程相通相似的部分，當然也有它自身的特點，現在我們就它作為考試內容時具有的特點作一個簡要的分析。 1、定義和定理多。 離散數學是建立在大量定義上面的邏輯推理學科。因而對概念的理解是我們學習這門學科的核心。在這些概念的基礎上，特別要注意概念之間的聯絡，而描述這些聯絡的實體則是大量的定理和性質。 在考試中的一部分內容就是考察大家對定義和定理的識記、理解和運用。如2002年上海交通大學的試題，問什麼是相容關係。如果知道的話，很容易得分；如果不清楚，那麼無論如何也得不到分數的。這型別題目往往因其難度低而在複習中被忽視。實際上這是一種相當錯誤的認識，在研究生入學考試的專業課試題中，經常出現直接考查對某知識點的識記的題目。對於這種題目，考生應該能夠準確、全面、完整地再現此知識點。任何的模糊和遺漏，都會造成極為可惜的失分。我們建議讀者，在複習的時候，對重要知識的記憶，務必以上面提到的“準確、全面、完整”為標準來要求自己，不能達到，就說明還不過關，還要下工夫。關於這一點，在後續章節中我們仍然會強調，使之貫穿於整個離散數學的複習過程中。 離散數學的定義主要分佈在集合論的關係和函式部分，還有代數系統的群、環、域、格和布林代數中。一定要很好地識記和理解。 2、方法性強。 離散數學的證明題中，方法性是非常強的，如果知道一道題用怎樣的方法證明，很輕易就可以證出來，反之則事倍功半。所以在平常複習中，要善於總結，那麼遇到比較陌生的題也可以遊刃有餘了。在本書中，我們為讀者總結了不少解題方法。讀者首先應該熟悉並且會用這些方法。同時我們還鼓勵讀者勤于思考，對於一道題，儘可能地多探討幾種解法。 3、有窮性。 由於離散數學較為“呆板”，出新題比較困難，不管什麼考試，許多題目是陳題，或者稍作變化的來的。“熟讀唐詩三百首，不會做詩也會吟。”如果拿到一本習題集，從頭到尾做過，甚至背會的話。那麼，在考場上就會發現絕大多數題見過或似曾相識。這時，要取得較好的成績也就不是太難的事情了。 本書是專門針對研究生入學考試而編寫的，適合於讀者對研究生入學考試的複習。如果還有時間的話，我們可以推薦兩本習題集。一本是左孝凌老師等編寫的《離散數學理論、分析、題解》，另一套有三本，是耿素雲老師等編寫的《離散數學習題集》。這兩套書大多數題都是相同的，只是由於某些符號和定義的不同，使得題目的設定和解法有些不同而已。 現在我們就分析一下研究生入學考試有哪些題型，以及我們應如何應付。 1、基礎題 基礎題就是考察對定義的識記，以及簡單的證明和推理。題目主要集中在數理邏輯部分和集合論部分。這些題目不需要思考，很容易上手。 這一部分的題目主要問題是要防止粗心大意和對定義記憶似是而非而丟的分數。不重視這一點的人將會在考試中吃大虧。如在主合取正規化中，極大項編碼對應的指派與真值表對應的指派相反，這一點在許多的參考書裡也會犯錯誤；還有是要防止沒有按照一定的方法而引起的錯誤，如我們在數理邏輯或者集合論裡作等價推演，可以省略若干不重要的步驟，只要老師和考生都清楚就可以了，而在推理理論裡則不能省略任何步驟，否則被認為是邏輯錯誤。 我們在學習中，還要注意融會貫通，例如，數理邏輯和集合論是相通的，因此記憶或者總結方法的時候可以綜合起來，這樣便於比較和理解。 2、定理應用題 本部分是最“死”的一部分，它主要體現了離散數學的方法性強的特點。並且這一部分佔了考試內容的大部分，我們必須在這一部分下功夫，記住了各種方法，也就拿到了離散數學的大部分分數。 下面我們就列出常用的幾種應用： ●證明等價關係：即要證明關係有自反、對稱、傳遞的性質。 ●證明偏序關係：即要證明關係有自反、反對稱、傳遞的性質。（特殊關係的證明就列出來兩種，要證明剩下的幾種只需要結合定義來進行）。 ●證明滿射：函式f：X??Y，即要證明對於任意的y??Y，都有x??X，使得f(x)=y。 ●證明入射：函式f：X??Y，即要證明對於任意的x1、x2??X，且x1≠x2，則f(x1) ≠f(x2)；或者對於任意的f(x1)=f(x2)，則有x1=x2。 ●證明集合等勢：即證明兩個集合中存在雙射。有三種情況：第一、證明兩個具體的集合等勢，用構造法，或者直接構造一個雙射，或者構造兩個集合相互間的入射；第二、已知某個集合的基數，如果為??，就設它和R之間存在雙射f，然後透過f的性質推出另外的雙射，因此等勢；如果為??0，則設和N之間存在雙射；第三、已知兩個集合等勢，然後再證明另外的兩個集合等勢，這時，先設已知的兩個集合存在雙射，然後根據剩下題設條件證明要證的兩個集合存在雙射。 ●證明群：即要證明代數系統封閉、可結合、有么元和逆元。（同樣，這一部分能夠作為證明題的概念更多，要結合定義把它們全部搞透徹）。 ●證明子群：雖然子群的證明定理有兩個，但如果考證明子群的話，通常是第二個定理，即設