怎樣學好離散數學

2021-03-07 06:16:45 字數 4797 閱讀 8308

1樓:匿名使用者

如何學好離散數學

離散數學是現代數學的一個重要分支,是電腦科學中基礎理論的核心課程。離散數學以研究離散量的結構和相互間的關係為主要目標,其研究物件一般地是有限個或可數個元素,因此他充分描述了電腦科學離散性的特點。由於離散數學在電腦科學中的重要性,因此,許多大學都把它作為研究生入學考試的專業課程中的一門,或者是一門中的一部分。

作為計算機系的一門課程,離散數學有與其它課程相通相似的部分,當然也有它自身的特點,現在我們就它作為考試內容時具有的特點作一個簡要的分析。

1、定義和定理多。

離散數學是建立在大量定義上面的邏輯推理學科。因而對概念的理解是我們學習這門學科的核心。在這些概念的基礎上,特別要注意概念之間的聯絡,而描述這些聯絡的實體則是大量的定理和性質。

在考試中的一部分內容就是考察大家對定義和定理的識記、理解和運用。如2023年上海交通大學的試題,問什麼是相容關係。如果知道的話,很容易得分;如果不清楚,那麼無論如何也得不到分數的。

這型別題目往往因其難度低而在複習中被忽視。實際上這是一種相當錯誤的認識,在研究生入學考試的專業課試題中,經常出現直接考查對某知識點的識記的題目。對於這種題目,考生應該能夠準確、全面、完整地再現此知識點。

任何的模糊和遺漏,都會造成極為可惜的失分。我們建議讀者,在複習的時候,對重要知識的記憶,務必以上面提到的「準確、全面、完整」為標準來要求自己,不能達到,就說明還不過關,還要下工夫。關於這一點,在後續章節中我們仍然會強調,使之貫穿於整個離散數學的複習過程中。

離散數學的定義主要分佈在集合論的關係和函式部分,還有代數系統的群、環、域、格和布林代數中。一定要很好地識記和理解。

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之間存在雙射;第

三、已知兩個集合等勢,然後再證明另外的兩個集合等勢,這時,先設已知的兩個集合存在雙射,然後根據剩下題設條件證明要證的兩個集合存在雙射。

●證明群:即要證明代數系統封閉、可結合、有么元和逆元。(同樣,這一部分能夠作為證明題的概念更多,要結合定義把它們全部搞透徹)。

●證明子群:雖然子群的證明定理有兩個,但如果考證明子群的話,通常是第二個定理,即設是群,s是g的非空子集,如果對於s中的任意元素a和b有a*b-1s,則是的子群。對於有限子群,則可考慮第一個定理。

●證明正規子群:若是一個子群,h是g的一個子集,即要證明對於任意的ag,有ah=ha,或者對於任意的hh,有a-1 *h*ah。這是最常見的題目中所使用的方法。

●證明格和子格:子格沒有條件,因此和證明格一樣,證明集合中任意兩個元素的最大元和最小元都在集合中。

圖論雖然方法性沒有前幾部分的強,但是也有一定的方法,如最長路徑法、構造法等等。

3、難題

難題就是考試中比較難以下手,大多考生作不出來,用來拉開分數檔次的題。那麼,遇到難題我們怎麼下手分析呢?

難題主要有以下四種,我們來逐一進行分析:

①綜合題

綜合題就是內容涵蓋若干章的問題,這樣的題大多數是在群論裡面的陪集、拉格朗日定理、正規子群、商群這一部分中。這一部分結合的內容很多,而且既複雜又難理解,是整個離散數學中的難點。

首先拉格朗日定理把群和等價關係、劃分結合在一起,又與群的階數相掛鉤(在子群中有一部分階方面的題是比較難的題,它的解法依據就在此處);然後商群將兩個群結合在一起,因為兩個群的元素是不同的,因此必須時刻概念清楚才不至於混亂;接著同餘關係把群和關係相結合,定義了一種新的關係;自然同態把正規子群和商群相聯絡,也成為某些證明題的著眼處;核的定義和群同態定理給出了正規子群的另一種證明方法,因為核就是正規子群……

當然,綜合題不僅此一處,離散數學是一個融會貫通的學科,像集合論,圖論等都可能成為綜合題的命題點。

對於綜合題,我們可以從兩方面下手,首先不管題設如何,看所要證明的問題,按照定理應用的題型著眼,設出所需要的格式,然後進行進一步推演;其次可以先看題設,應用已知條件的性質定理向前推幾步,看看哪一個性質更能夠接近所問,題目也就迎刃而解了。

②例外題

例外題有兩個含義,首先是對於定理應用題而言的,對於一個概念的判定定理和性質定理不是唯一的,而定理應用題是給出的是最常出題的定理,因此有的考題可能考出一個不常用的定理。

其次例外題還有一種題型是與我們平常思維相悖的問題,如:有一些題目給出一個結論,說如果它正確的話請指出來,錯誤的話則請證明,憑做題經驗通常是要選擇證明的那條思路。其實也不妨用一些時間看看能不能指出來,從而不用證明。

請看下面的例子:

③ 偏題

常常有的參考書會說某某章是非重點,不會考到之類的話,這是非常錯誤和有害的。其結果是令這些章成為讀者複習中的盲點,成為難題的又一種。這些章通常概念少,定理不多,因此題目本身不難。

但由於沒有好好複習或者根本沒有複習,考試中又出了題目,故此拿不到分數則是非常令人懊喪的。所以我們建議讀者進行全面複習,除非是所報考院校明確說明不考的部分,其餘內容一律要認真複習。即使是複習時間比較少,也必須做到至少是瞭解了基本概念和定義。

對於離散數學而言,函式一章中的基數部分和格和布林代數一章是人們容易忽略的問題。

我們平時複習的時候,不管是什麼課程,一定不能留死角,而這些地方出的題目由於它的本身內容的侷限性,又往往是非常簡單的。丟了十分可惜。

④ 錯題

專業課的題目是由較少老師出的,並不像基礎課那樣經過多方面的論證,因此出錯題也不奇怪(雖然非常非常之少),如果我們遇到了一道題目,經過我們判斷和推演得到相悖的答案,不要過分迷信題目的權威性,因為它可能是錯題。

下面講一下離散證明題的證明方法:

1、直接證明法

直接證明法是最常見的一種證明的方法,它通常用作證明某一類東西具有相同的性質,或者符合某一些性質必定是某一類東西。

直接證明法有兩種思路,第一種是從已知的條件來推出結論,即看到條件的時候,並不知道它怎麼可以推出結論,則可以先從已知條件按照定理推出一些中間的條件(這一步可能是沒有目的的,要看看從已知的條件中能夠推出些什麼),接著,選擇可以推出結論的那個條件繼續往下推演;另外一種是從結論反推回條件,即看到結論的時候,首先要反推一下,看看從哪些條件可以得出這個結論(這一步也可能是沒有目的的,因為並不知道要用到哪個條件),以此類推一直到已知的條件。通常這兩種思路是同時進行的。

2、反證法

反證法是證明那些「存在某一個例子或性質」,「不具有某一種的性質」,「僅存在唯一」等的題目。

它的方法是首先假設出所求命題的否命題,接著根據這個否命題和已知條件進行推演,直至推出與已知條件或定理相矛盾,則認為假設是不成立的,因此,命題得證。

3、構造法

證明「存在某一個例子或性質」的題目,我們可以用反證法,假設不存在這樣的例子和性質,然後推出矛盾,也可以直接構造出這麼一個例子就可以了。這就是構造法,通常這樣的題目在圖論中多見。值得注意的是,有一些題目其實也是本型別的題目,只不過比較隱蔽罷了,像證明兩個集合等勢,實際上就是證明「兩個集合中存在一個雙射」,我們即可以假設不存在,用反證法,也可以直接構造出這個雙射。

4、數學歸納法

數學歸納法是證明與自然數有關的題目,而且這一型別的題目可以遞推。作這一型別題目的時候,要注意一點就是所要歸納內容的選擇。

離散數學這倆為什麼不是合式公式,離散數學裡為什麼prq不是合式公式

命題來公式是由命題常項 命題變項 聯自結詞 括號等組成的符號串,但不是由這些符號任意組成的符號串都是命 題公式。因此,必須給出命題公式的嚴格定義。定義1.6編輯 1 單個命題常項或變項是合式公式 2 如果a是合式公式,則 a也是合式公式 3 如果a,b是合式公式,則p q p q p q p q也是...

關於離散數學的題,請人幫忙解答,關於離散數學的一個題,請人幫忙解答!

用排斥原理解復 決瘋簡單。設參加足球比制 賽的人為bai集合a 設參加籃球的比du賽的人為集 zhi合b 設參加排球dao的比賽的人為集合c 則有 由於交併不好打,用減代表交,用加代表並 a 28,b 29,c 26,a b 7,b c 9,a c 11 有加法排斥原理知 a b c a b c a...

簡單的離散數學問題,離散數學幾條簡單問題

1.s上的有序對有 1,1 1,2 2,1 2,2 4個 偏序關係需要滿足自反,反對稱,傳遞 即 1,1 2,2 都屬於偏序集,1,2 2,1 不能同時屬於偏序集 所以一共有2 2 1 3個偏序關係 因為s上有序對有4個,所以二元關係有2 4 16個2 4個元素集合的滿射,即是4個元素集合的雙射個數...