探討離散數(shù)學(xué)各部分在教學(xué)中的相關(guān)性7200字

1、探討離散數(shù)學(xué)各部分在教學(xué)中的相關(guān)性7200字 摘要：離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課, 它的四個(gè)部分?jǐn)?shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論分別是相對(duì)獨(dú)立的分支, 但都是對(duì)離散對(duì)象的討論, 因此它們之間仍然有著或深或淺的聯(lián)系。文章探討各部分在教學(xué)中的相關(guān)性, 找出它們共性的部分, 使其在教學(xué)中相互關(guān)聯(lián)、相互融合, 以加深學(xué)生掌握知識(shí)的熟練度, 提高學(xué)習(xí)效率。關(guān)鍵詞：離散數(shù)學(xué); 相關(guān)性; 教學(xué);Discussion on the Correlation of the Contents of Discrete MathematicsAbstract：Discrete Mathematics is a sp

2、ecialized basic course of computer science. Its four parts, mathematical logic, set theory, algebraic structure and graph theory, are relatively independent branches, but they all discuss discrete objects, so there are deep or shallow connections between them. In order to improve the proficiency of

3、students in discrete mathematics knowledge, this paper discusses the correlation of the four parts in the teaching to find out their common part and make them to interrelate and integrate each other in the teaching.Keyword：discrete mathematics; correlation; teaching;離散數(shù)學(xué)課程是計(jì)算機(jī)專業(yè)的核心基礎(chǔ)課, 主要研究離散量的結(jié)構(gòu)和相互

4、關(guān)系。學(xué)習(xí)該課程可以培養(yǎng)學(xué)生的邏輯推理能力、抽象思維能力、縝密概括能力, 并且為后續(xù)的專業(yè)課如數(shù)據(jù)結(jié)構(gòu)、數(shù)字邏輯電路、數(shù)據(jù)庫(kù)等作基礎(chǔ)1。離散數(shù)學(xué)主要包括四個(gè)部分的內(nèi)容:數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論。數(shù)理邏輯主要研究離散對(duì)象的推理和形式化方法, 集合論研究離散結(jié)構(gòu)的表示和描述工具, 代數(shù)結(jié)構(gòu)研究離散結(jié)構(gòu)的代數(shù)模型, 圖論研究離散結(jié)構(gòu)的關(guān)系模型。長(zhǎng)期以來(lái), 這四個(gè)部分呈現(xiàn)的特點(diǎn)就是內(nèi)容散;, 各部分之間的聯(lián)系不緊密2。這種情況會(huì)導(dǎo)致學(xué)生學(xué)到后面部分的內(nèi)容時(shí), 對(duì)前面已學(xué)習(xí)的內(nèi)容容易遺忘。事實(shí)上, 四個(gè)部分都是對(duì)離散對(duì)象進(jìn)行討論, 它們之間仍然有著或深或淺的聯(lián)系。在教學(xué)實(shí)踐中, 為了避免學(xué)生遺忘

5、前期所學(xué)知識(shí)點(diǎn), 使學(xué)生在學(xué)習(xí)新知識(shí)的同時(shí)也能關(guān)聯(lián)復(fù)習(xí)前面的內(nèi)容, 現(xiàn)對(duì)各部分知識(shí)的相關(guān)性進(jìn)行探討并總結(jié)歸納如下。1 集合論與數(shù)理邏輯(1) 數(shù)理邏輯描述離散對(duì)象的形式化方法, 提供了集合部分的表示方法。集合的表示方法有列元素法和謂詞表示法, 列元素法是把集合的元素都列舉出來(lái), 而謂詞表示法采用的就是數(shù)理邏輯的描述方法, 描述集合的元素滿足的條件, 如集合A=3, 4, 5是列元素表示法, 用謂詞表示法表示為A=x|x∈Z∧2集合運(yùn)算的定義形式也采用謂詞表示法, 如集合的廣義交運(yùn)算, ∩A=x|?z (z∈A→x∈z) 3, 定義中元素x

6、滿足的條件用謂詞描述, 元素x滿足的條件為對(duì)A所有的元素z, x都是z的元素, 即集合A的所有元素的公共元素構(gòu)成的集合。(2) 集合運(yùn)算的主要算律與命題邏輯的等值式算律相近, 如都具有冪等律、交換律、結(jié)合律、分配律、雙重否定律、德摩根律、吸收律、排中律、矛盾律等, 如集合運(yùn)算的吸收律A∪ (A∩B) =A, 邏輯運(yùn)算的吸收律A∨ (A∧B) ?A, 又如邏輯運(yùn)算的德摩根律? (A∨B) ?A∧?B, 在集合運(yùn)算中絕對(duì)補(bǔ)運(yùn)算也有德摩根律? (A∪B) =?A∩?B, 相對(duì)補(bǔ)運(yùn)算也有德摩根律, 比如對(duì)C的相對(duì)補(bǔ)運(yùn)算滿足C- (A∪

7、B) = (C-A) ∩ (C-B) 。將這些運(yùn)算性質(zhì)對(duì)比學(xué)習(xí), 一方面可以復(fù)習(xí)鞏固已學(xué)知識(shí), 另一方面也有助于對(duì)新知識(shí)的理解。(3) 集合論部分的常用證明方法之一命題演算證明法, 是根據(jù)運(yùn)算的定義用數(shù)理邏輯的等值式或者推理進(jìn)行證明。如果證明X?Y:任取x, x∈X?…?x∈Y;如果證明X=Y:任取x, x∈X?…?x∈Y。例如用命題演算法證明關(guān)系的復(fù)合運(yùn)算對(duì)并運(yùn)算的分配律, F° (G∪H) =F°G∪F°H,任取,∈F° (G∪H)?t (&isin

8、;F∧∈G∪H) 復(fù)合運(yùn)算的定義?t (∈F∧ (∈G∨∈H) ) 并運(yùn)算的定義?t ( (∈F∧∈H) ∨ (∈F∧∈H) ) 邏輯運(yùn)算∧對(duì)∨的分配律?t (∈F∧∈G) ∧?t (∈F∧∈H) 一階邏輯量詞分配等值式?∈F°G∧∈F°H復(fù)合運(yùn)算的定義?∈F°G∪F°H并運(yùn)算的定義所以有F° (G&c

9、up;H) =F°G∪F°H。命題演算的證明法充分利用了數(shù)理邏輯的研究?jī)?nèi)容, 即對(duì)離散對(duì)象的推理和形式化方法。將集合論與數(shù)理邏輯結(jié)合起來(lái)學(xué)習(xí), 有助于學(xué)生更好地理解和掌握兩部分內(nèi)容。2 代數(shù)結(jié)構(gòu)與集合論(1) 代數(shù)系統(tǒng)的二元運(yùn)算和一元運(yùn)算是以函數(shù)的形式定義的, 如設(shè)S為集合, 函數(shù)fSxS→S稱為S上的二元運(yùn)算, 對(duì)于運(yùn)算f () =z, 也可以用運(yùn)算符表示為xy=z, 對(duì)于一元運(yùn)算, 稱函數(shù)fS→S為S上的一元運(yùn)算, 對(duì)于運(yùn)算f (x) =y, 也可以用運(yùn)算符表示為*x=y。(2) 在討論二元運(yùn)算的運(yùn)算性質(zhì)和特異元素的時(shí)候, 也常常以集合中的運(yùn)算為

10、例作分析。例如討論冪集P (S) 上的∪、∩、⊕運(yùn)算, ∪和∩滿足冪等律、交換律、結(jié)合律、分配律、吸收律等, ∪運(yùn)算的單位元是?, 零元是S, ∩運(yùn)算的單位元是S, 零元是?。⊕運(yùn)算滿足交換律、結(jié)合律、消去律, 不滿足冪等律, 單位元是?, 每個(gè)元素A的逆元是A。又如對(duì)于AA中函數(shù)的復(fù)合運(yùn)算, 滿足結(jié)合律, 不滿足交換律、冪等律、消去律, 單位元是IA, 雙射函數(shù)有逆元, 是其反函數(shù)f-1。以這些集合論中的運(yùn)算為例來(lái)討論, 可以在學(xué)習(xí)運(yùn)算性質(zhì)和特異元素的定義的同時(shí), 對(duì)前面所學(xué)知識(shí)再次進(jìn)行復(fù)習(xí), 同時(shí)加深對(duì)兩部分內(nèi)容的理解

11、。(3) 討論代數(shù)系統(tǒng)中的陪集時(shí), 將陪集與二元關(guān)系的等價(jià)類進(jìn)行關(guān)聯(lián)討論, 可以更深入地探討陪集的性質(zhì)。設(shè)G是群, H是G的子群, 在G上定義二元關(guān)系R:?a, b∈G, ∈R?ab-1∈H, 則R是G上的等價(jià)關(guān)系, 且aR=Ha3。根據(jù)定義可知, a關(guān)于R的等價(jià)類就是以a為代表元素的H的右陪集, 因此陪集就有了等價(jià)類的特點(diǎn)和性質(zhì)。在這一部分, 可以同時(shí)復(fù)習(xí)等價(jià)關(guān)系的定義, 對(duì)R是等價(jià)關(guān)系進(jìn)行分析, R滿足自反性?a∈G?∈R;R滿足對(duì)稱性, ?∈R?∈R;R滿足傳遞性, ?∈R∧∈R?&isin

12、;R。另外復(fù)習(xí)等價(jià)類的性質(zhì)并轉(zhuǎn)換為陪集的性質(zhì), 如每個(gè)陪集 (等價(jià)類) 都是集合G的非空子集, 任意兩個(gè)陪集 (等價(jià)類) 或者相等或者不交, 所有陪集 (等價(jià)類) 的并即為G, 并可以根據(jù)這些性質(zhì)引入拉格朗日定理。(4) 代數(shù)系統(tǒng)中的格的定義是集合論中的偏序集, 設(shè)是偏序集, 如果?x, y∈S, x, y都有最小上界和最大下界, 則稱S關(guān)于偏序?作成一個(gè)格。3 圖論與集合論(1) 圖是以集合的形式定義的, 包括頂點(diǎn)集V和邊集E, G=。(2) 有向圖與二元關(guān)系相關(guān), 都有三種表示法:集合、矩陣、圖形。設(shè)有向圖D=, V=v1, v2, v3, E=, , , , 其圖形表示如圖1所

13、示, 根據(jù)點(diǎn)與點(diǎn)之間的鄰接關(guān)系得到鄰接矩陣另外也可以從二元關(guān)系的角度來(lái)看, 設(shè)集合S=v1, v2, v3, 集合S上的二元關(guān)系R=, , , , 則圖1即為二元關(guān)系R的關(guān)系圖GR, A (D) 就是關(guān)系R的關(guān)系矩陣MR。圖1 有向圖D此外, 可達(dá)關(guān)系反映的是有向圖中兩點(diǎn)間是否存在通路的情況, 可以用可達(dá)矩陣P (D) 來(lái)表示, 當(dāng)假定圖中每個(gè)點(diǎn)到自身是可達(dá)的, 可達(dá)關(guān)系具有傳遞性?？蛇_(dá)矩陣P (D) 反映在二元關(guān)系中就是關(guān)系R的傳遞閉包t (R) 。(3) 無(wú)向圖的連通性與等價(jià)關(guān)系的概念相關(guān)聯(lián)。在無(wú)向圖中討論頂點(diǎn)之間的連通關(guān)系, 設(shè)G=為無(wú)向圖若u、v∈V之間存在通路, 則稱u?v

14、。規(guī)定, ?v∈V, v?v。由連通的定義可知, ?是V上的等價(jià)關(guān)系, R=|u, v∈V且u?v, 滿足自反性, ?v∈V?v?v?∈R, 滿足對(duì)稱性, ?∈R?u?v?vu?∈R, 滿足傳遞性, ?∈R∧∈R?u?v∧vw?uw?∈R。根據(jù)等價(jià)關(guān)系, 頂點(diǎn)集V中的每個(gè)點(diǎn)都有等價(jià)類, v=u|vu且u∈V。假設(shè)Vi是V關(guān)于頂點(diǎn)之間的連通關(guān)系的一個(gè)等價(jià)類, 稱其導(dǎo)出子圖GVi為G的一個(gè)連通分支。G的連通分支數(shù)記作P (G) 。例如, 無(wú)向圖G如圖2所示, 頂點(diǎn)集關(guān)于連通關(guān)系分為兩

15、個(gè)等價(jià)類, v1=v2=v3=v1, v2, v3, v4=v5=v4, v5, 等價(jià)類v1, v2, v3的導(dǎo)出子圖為一個(gè)連通分支如圖2左邊, 等價(jià)類v4, v5的導(dǎo)出子圖為另一個(gè)連通分支如圖2右邊, 連通分支數(shù)P (G) =2, 即為不同等價(jià)類的個(gè)數(shù)。圖2 無(wú)向圖G(4) 在二元關(guān)系部分, 求二元關(guān)系R的傳遞閉包t (R) 有三種方法:集合表達(dá)式、關(guān)系矩陣、關(guān)系圖。在通過(guò)R的關(guān)系圖GR求傳遞閉包t (R) 的關(guān)系圖Gt時(shí), 考察G的每個(gè)頂點(diǎn)xi, 找從xi出發(fā)的所有1步、2步、3步、…、n步長(zhǎng)的路徑 (n為GR的頂點(diǎn)數(shù)) 。如果有從xi到xj的步長(zhǎng)為1或2或…或

16、n的路徑, 就在Gt中加上一條從xi到xj的邊, 在檢查完所有的頂點(diǎn)后就得到傳遞閉包的關(guān)系圖Gt。在此過(guò)程中, 為什么找到步長(zhǎng)為n以內(nèi)的路徑, 而再長(zhǎng)的路徑不需要找了;, 這一點(diǎn)可以在圖論中找到依據(jù)。圖論中關(guān)于通路的性質(zhì), 在n階圖G中, 若從頂點(diǎn)vi到vj (vi和vj可能相同也可能不同) 存在通路, 則從vi到vj存在長(zhǎng)度小于或等于n的路徑。也就是說(shuō), 如果從vi到vj沒(méi)有長(zhǎng)度小于或等于n的路徑, 那么從vi到vj就沒(méi)有任何長(zhǎng)度的通路。所以判斷從vi到vj有沒(méi)有通路, 只需要找長(zhǎng)度為n以內(nèi)的路徑就可以了。4 圖論與代數(shù)結(jié)構(gòu)圖論與代數(shù)結(jié)構(gòu)中都有同構(gòu)的概念, 都指的是保持結(jié)構(gòu)的雙射函數(shù)。在代數(shù)

17、結(jié)構(gòu)中, 設(shè)V1=和V2=是同類型的代數(shù)系統(tǒng), f:A→B是雙射函數(shù), 且對(duì)于?x, y∈A有f (xy) =f (x) *f (y) , 則稱f是V1到V2的同構(gòu)映射, 記作V1?V2。在圖論中, 可以類比討論上面的同構(gòu)的概念。設(shè)G1=和G2=是兩個(gè)圖, 有向圖中的邊可以表示為點(diǎn)的有序?qū)? 如=e1, 這種對(duì)應(yīng)關(guān)系可以用函數(shù)來(lái)表示, 用函數(shù)g1:AxA→E1和g2:BxB→E2分別表示圖G1和圖G2中的有向邊, 它們分別對(duì)應(yīng)二元運(yùn)算和*, 則關(guān)于雙射函數(shù)f:A→B, 對(duì)于?x, y∈A, ∈E1當(dāng)且僅當(dāng)∈E2,

18、則稱G1與G2是同構(gòu)的, 記G1?G2。5 函數(shù)與二元關(guān)系函數(shù)與二元關(guān)系都是集合論中的內(nèi)容, 函數(shù)是一種特殊的二元關(guān)系。在學(xué)習(xí)過(guò)程中, 先學(xué)習(xí)二元關(guān)系, 再學(xué)習(xí)函數(shù)。在函數(shù)中有幾個(gè)常用函數(shù), 與二元關(guān)系相關(guān), 可以在學(xué)習(xí)函數(shù)的過(guò)程中, 對(duì)二元關(guān)系的內(nèi)容進(jìn)一步復(fù)習(xí)鞏固。(1) 單調(diào)函數(shù)。設(shè), 為偏序集, f:A→B, 如果對(duì)任意的x1, x2∈A, x1?x2, 就有f (x1) ?f (x2) , 則稱f為單調(diào)遞增的;如果對(duì)任意的x1, x2∈A, x1?x2, 就有f (x1) ?f (x2) , 則稱f為嚴(yán)格單調(diào)遞增的3。例如, 偏序集, , R?為包含關(guān)系, ≤為一般的小于等于關(guān)系, 令f:P (a,