離散數(shù)學(xué)論文

1、離散數(shù)學(xué)在電子信息和計(jì)算機(jī)中的應(yīng)用離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的重要分支，是研究離散量的結(jié)構(gòu)及相互關(guān)系的學(xué)科，它在計(jì)算機(jī)理論研究及軟、硬件開發(fā)的各個(gè)領(lǐng)域都有著廣泛的應(yīng)用。作為一門重要的專業(yè)基礎(chǔ)課，對(duì)于我們電子專業(yè)的同學(xué)來(lái)說(shuō)，學(xué)習(xí)離散數(shù)學(xué)史有其重要現(xiàn)實(shí)意義：它不僅能為我們的專業(yè)課學(xué)習(xí)打下基礎(chǔ)，也為我們今后將要從事的軟、硬件開發(fā)和應(yīng)用研究打下堅(jiān)實(shí)的基礎(chǔ)，同時(shí)也有助于培養(yǎng)我們的抽象思維、嚴(yán)格的邏輯推理和創(chuàng)新能力。離散數(shù)學(xué)的應(yīng)用非常廣泛，本文主要研究其在我們所學(xué)的重要課程中的應(yīng)用：數(shù)字電路中的門電路設(shè)計(jì)、軟件技術(shù)基礎(chǔ)中的一些技術(shù)以及解決現(xiàn)實(shí)生活中的一些問(wèn)題的應(yīng)用。 離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)

2、科，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支。它在各學(xué)科領(lǐng)域，特別在計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，同時(shí)離散數(shù)學(xué)也是計(jì)算機(jī)專業(yè)的許多專業(yè)課程，如程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯技術(shù)、人工智能、數(shù)據(jù)庫(kù)、算法設(shè)計(jì)與分析、理論計(jì)算機(jī)科學(xué)基礎(chǔ)等必不可少的先行課程。離散數(shù)學(xué)是傳統(tǒng)的邏輯學(xué)，集合論（包括函數(shù)），數(shù)論基礎(chǔ)，算法設(shè)計(jì)，組合分析，離散概率，關(guān)系理論，圖論與樹，抽象代數(shù)（包括代數(shù)系統(tǒng)，群、環(huán)、域等），布爾代數(shù)，計(jì)算模型（語(yǔ)言與自動(dòng)機(jī)）等匯集起來(lái)的一門綜合學(xué)科。離散數(shù)學(xué)的應(yīng)用遍及現(xiàn)代科學(xué)技術(shù)的諸多領(lǐng)域，它通常研究的領(lǐng)域包括：數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、關(guān)系論、函數(shù)論、圖論、組合學(xué)、數(shù)論等。離散數(shù)學(xué)在門電路

3、設(shè)計(jì)中的應(yīng)用邏輯門是集成電路中的基本組件。簡(jiǎn)單的邏輯門可由晶體管組成。這些晶體管的組合可以使代表兩種信號(hào)的高低電平在通過(guò)它們之后產(chǎn)生高電平或者低電平的信號(hào)。高、低電平可以分別代表邏輯上的“真”與“假”或二進(jìn)制當(dāng)中的1和0，從而實(shí)現(xiàn)邏輯運(yùn)算。常見(jiàn)的邏輯門包括“與”門，“或”門，“非”門，“異或”門（也稱：互斥或）等等。邏輯門可以組合使用實(shí)現(xiàn)更為復(fù)雜的邏輯運(yùn)算。在數(shù)字電路中，離散數(shù)學(xué)的應(yīng)用主要體現(xiàn)在數(shù)理邏輯部分的使用。在數(shù)字電路中廣于使用的邏輯代數(shù)即為布爾代數(shù)。邏輯代數(shù)中的邏輯運(yùn)算與、或、非、異或與離散數(shù)學(xué)中的合取，析取、否定、異或（排斥或）相對(duì)應(yīng)。數(shù)字電路的學(xué)習(xí)重點(diǎn)在于掌握電路設(shè)計(jì)技術(shù)，在設(shè)計(jì)門

4、電路時(shí)，要求設(shè)計(jì)者根據(jù)給出的具體邏輯問(wèn)題，求出實(shí)現(xiàn)這一邏輯功能的邏輯電路。一般的設(shè)計(jì)過(guò)程為如下： 首先，進(jìn)行邏輯抽象.分析給定的邏輯問(wèn)題，確定輸入、輸出變量,一般把引起事件的原因作為輸入變量，把事件的結(jié)果作為輸出變量。再以二值邏輯的0、1兩種狀態(tài)分別代表變量的兩種不同狀態(tài)，并根據(jù)給定的因果關(guān)系列出邏輯真值表。于是，這個(gè)實(shí)際的邏輯問(wèn)題被抽象成一個(gè)邏輯函數(shù)了，而且這個(gè)邏輯函數(shù)是以真值表形式給出的。 然后根據(jù)真值表寫出邏輯函數(shù)式。在這一步的主要工作為對(duì)邏輯函數(shù)進(jìn)行化簡(jiǎn)和變換，此時(shí)采用的方法一般為使用邏輯代數(shù)公式，即離散數(shù)學(xué)中的命題演算公式將命題公式直接進(jìn)行化簡(jiǎn)；或者用卡諾圖法進(jìn)行化簡(jiǎn)；或者同時(shí)采用兩

5、種方法，互相驗(yàn)證結(jié)果是否最簡(jiǎn)。但在一般情況下，在真值表中變量較多，邏輯函數(shù)式較為復(fù)雜時(shí)，我們采用卡諾圖法更為方便快捷，且出錯(cuò)率更低。在得到最簡(jiǎn)邏輯函數(shù)式后，選定器件類型，開始構(gòu)建實(shí)際電路。在對(duì)所用器件種類有所限制或使用中規(guī)模集成電路構(gòu)建設(shè)計(jì)好的電路時(shí)，需要把函數(shù)式變換為適當(dāng)?shù)男问?。此時(shí)，我們將采用命題等值演算對(duì)函數(shù)式進(jìn)行變換，變換的結(jié)果通常為合取范式和析取范式，以便使用最少的器件和最簡(jiǎn)單的連線。離散數(shù)學(xué)在軟件技術(shù)中的應(yīng)用離散數(shù)學(xué)作為計(jì)算機(jī)科學(xué)技術(shù)的支撐學(xué)科之一，它在計(jì)算機(jī)程序中有著極其重要和廣泛的應(yīng)用。在軟件技術(shù)基礎(chǔ)中，我們所學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)極其運(yùn)算，查找與排序技術(shù)，數(shù)據(jù)庫(kù)技術(shù)，無(wú)一不是建立在離

6、散數(shù)學(xué)的基礎(chǔ)上的。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩大類，無(wú)論是哪種存儲(chǔ)結(jié)構(gòu)，我們都必須存儲(chǔ)數(shù)據(jù)元素和元素之間的前后件關(guān)系這兩方面的內(nèi)容。通過(guò)數(shù)據(jù)元素間的特定關(guān)系，我們可以得出數(shù)據(jù)結(jié)構(gòu)的集合，寫出關(guān)系矩陣，畫出關(guān)系圖。對(duì)于線性結(jié)構(gòu)的數(shù)據(jù)，我們構(gòu)造順序表或鏈表對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)處理和分析，對(duì)于非線性結(jié)構(gòu)的數(shù)據(jù)，我們則經(jīng)常使用樹和圖來(lái)表示。樹和圖的概念對(duì)于非線性結(jié)構(gòu)數(shù)據(jù)非常重要，例如一個(gè)學(xué)校的行政層次結(jié)構(gòu)，我們可以用樹來(lái)表示，一個(gè)城市中的交通路線可以用圖來(lái)描述。在查找和排序技術(shù)中，樹顯得尤為重要。在多種排序技術(shù)中，樹概念的使用在堆排序技術(shù)中直觀可見(jiàn)。堆排序的基本思想是，先將所需要排序的元素用完全二叉

7、樹表示成堆，堆定義為：具有n個(gè)元素的序列（h1,h2,hn）,當(dāng)且僅當(dāng)滿足hih2i,hih2i+1或hih2i,hih2i+1時(shí)稱為堆。然后在調(diào)整建堆的過(guò)程中，總是將根結(jié)點(diǎn)值與左右子樹的根結(jié)點(diǎn)值進(jìn)行比較，若不滿足堆的條件，則將左右子樹根結(jié)點(diǎn)值中的大者（或小者）與根結(jié)點(diǎn)值進(jìn)行交換。這個(gè)調(diào)整過(guò)程一直做到所有子樹均為堆為止。查找技術(shù)史建立在樹的基礎(chǔ)之上的，首先要構(gòu)建二叉排序樹，然后在其中進(jìn)行查找。為提高查找數(shù)據(jù)的效率，一般采用多層索引樹進(jìn)行查找。主要的查找方法建立在樹的遍歷基礎(chǔ)上。遍歷一棵樹有3種方法：前序遍歷、中序遍歷和后序遍歷。具體采用哪種遍歷方法由所選擇的查找方法所決定。數(shù)據(jù)庫(kù)技術(shù)主要是實(shí)現(xiàn)對(duì)數(shù)據(jù)的加工和管理。在關(guān)系模型數(shù)據(jù)庫(kù)中，對(duì)數(shù)據(jù)的操作歸結(jié)為各種集合運(yùn)算。在關(guān)系模型的數(shù)據(jù)語(yǔ)言中，我們除了要運(yùn)用常規(guī)的集合運(yùn)算（并、交、差、笛卡爾積等）外，還定義了一些專門的關(guān)系運(yùn)算，如投影、選擇、連接等運(yùn)算。前者是將關(guān)系（即二維表）看成元素組的集合，這些運(yùn)算主要是從二維表中行的方向來(lái)進(jìn)行的；后者主要是從二維表中列的方向來(lái)進(jìn)行運(yùn)算的。兩者統(tǒng)稱為關(guān)系代數(shù)。由于這方面的內(nèi)容在離散數(shù)學(xué)和軟件技術(shù)基礎(chǔ)兩門課程中都剛開始進(jìn)入學(xué)習(xí)，所以在此不做進(jìn)一步的研究。如果知道了學(xué)習(xí)離散數(shù)學(xué)能解