離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中的應(yīng)用

1、離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中的應(yīng)用院系：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院姓名：XXX學(xué)號(hào)：XXXXXX指導(dǎo)老師：XXXXXXX年XX月XX日摘要本文主要內(nèi)容 目錄命題邏輯與程序優(yōu)化謂詞邏輯與程序驗(yàn)證遞歸函數(shù)論參考文獻(xiàn)本來(lái)想選取其他的一些課題作為報(bào)告的主要內(nèi)容，但是發(fā)現(xiàn)缺少一定的數(shù)學(xué)基礎(chǔ)，很多概念都難以理解，所以就查閱了一點(diǎn)關(guān)于離散數(shù)學(xué)的內(nèi)容，這也是我這份報(bào)告的主要內(nèi)容。根據(jù)書(shū)本給出的定義，離散數(shù)學(xué)的研究對(duì)象是各種各樣的離散量及它們之間的關(guān)系，而計(jì)算機(jī)科學(xué)中出現(xiàn)的基本量也大多是離散型的，所以離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)之一，在程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、算法分析、操作系統(tǒng)、編譯技術(shù)乃至人工智能等方面均有應(yīng)用。離散數(shù)

2、學(xué)主要有數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論、組合數(shù)學(xué)這幾個(gè)部分，以下僅列出了三個(gè)離散數(shù)學(xué)（更準(zhǔn)確地說(shuō)僅僅是數(shù)理邏輯）在計(jì)算機(jī)科學(xué)中的應(yīng)用。命題邏輯與程序優(yōu)化數(shù)理邏輯，顧名思義，是用數(shù)學(xué)的方法來(lái)研究邏輯學(xué)。這個(gè)方法就是引進(jìn)一套符號(hào)體系。當(dāng)我閱讀這一部分內(nèi)容的時(shí)候，感覺(jué)到一種很“妙”的感覺(jué)，比如，如果明天是星期六，我就睡懶覺(jué)，這件與數(shù)值毫無(wú)關(guān)系的事情，就可以用PQ（P:明天是星期六，Q：我睡懶覺(jué)）這些符號(hào)很簡(jiǎn)潔地表示出來(lái)。還有命題變?cè)?、謂詞變?cè)雀拍?，儼然就是我們傳統(tǒng)的數(shù)學(xué)的變量x。這些設(shè)定使得我們能夠用一種類似于傳統(tǒng)意義上的數(shù)學(xué)但又與之不同的數(shù)學(xué)方法來(lái)研究邏輯學(xué)。（不得不對(duì)萊布尼茨、布爾、弗雷格這

3、些先驅(qū)表示一下欽佩。）命題邏輯是數(shù)理邏輯的一個(gè)重要組成部分，主要研究命題的演算推證。當(dāng)我們把一個(gè)實(shí)際問(wèn)題符號(hào)化，借助一些基本的命題定律和推理定律，就可以達(dá)到證明或化簡(jiǎn)的目的，而不用糾結(jié)于命題的具體內(nèi)容。例如，這是某本離散數(shù)學(xué)教材中的例子：化簡(jiǎn)下列程序語(yǔ)言：IF A THEN IF B THEN X ELSE Y ELSE IF B THEN X ELSE Y，用C語(yǔ)言表述就是： if(A)if(B)X;else Y;else if(B)X;else Y;執(zhí)行X的條件為，執(zhí)行Y的條件為，所以，這段程序可以簡(jiǎn)化為：IF B THEN X ELSE Y,用C語(yǔ)言表述就是：if(B)X;else Y;

4、化簡(jiǎn)以后的代碼與之前相比，不僅簡(jiǎn)潔易讀，而且能夠減少計(jì)算機(jī)判斷的次數(shù)，加快程序的運(yùn)行速度。命題邏輯與電路設(shè)計(jì)也有密切的關(guān)系，如對(duì)于組合邏輯電路，可以利用命題公式和邏輯元件共有的二值特性，進(jìn)行邏輯演算，得到復(fù)雜度最小的電路。謂詞邏輯與程序驗(yàn)證據(jù)說(shuō)，謂詞邏輯的提出是為了解決一些命題邏輯所不能揭示的問(wèn)題，如：蘇格拉底的三段論、命題之間的共同屬性。這是因?yàn)槊}邏輯不關(guān)心命題的具體內(nèi)容，其研究的基本單位是原子命題，考慮的是邏輯連接詞的邏輯特性，而謂詞邏輯則不一樣，它還要深入到命題內(nèi)部，研究謂詞（刻畫(huà)個(gè)體域中個(gè)體性質(zhì)或個(gè)體之間相互關(guān)系的模式）和量詞（刻畫(huà)個(gè)體常元或變?cè)獢?shù)量關(guān)系的詞）的邏輯特性。因此，有人說(shuō)

5、，命題邏輯是謂詞邏輯的子集。與命題邏輯類似，謂詞邏輯也存在邏輯演算，也就是謂詞演算。由于我了解甚淺，自然沒(méi)有意識(shí)到這一點(diǎn)，但書(shū)本告訴我，謂詞邏輯可以應(yīng)用于程序驗(yàn)證、自動(dòng)程序設(shè)計(jì)以至人工智能等等。下面以程序驗(yàn)證為例。現(xiàn)代計(jì)算機(jī)程序的規(guī)模越來(lái)越龐大，僅靠調(diào)試是不能保證程序無(wú)錯(cuò)的，因?yàn)檎{(diào)試只能選取有限個(gè)初值作有限次的試驗(yàn)。因此有人提出了歸納斷言法。所謂斷言，實(shí)際上就是一種刻畫(huà)程序中的變?cè)诓煌碾A段應(yīng)該滿足的特性和關(guān)系?？梢猿绦虻拈_(kāi)始和結(jié)束以及中間的一些位置設(shè)置斷言，如果斷言的要求均能被滿足直到程序結(jié)束，那么就認(rèn)為這個(gè)程序是正確的。以一個(gè)簡(jiǎn)單的程序?yàn)槔?，這也是老師上課時(shí)給出的例子:求x=mn，其中n

6、0。void mult(int m, int n) int x,y;x = 0 ;y = 0 ;while (y n) x = x + m ;y = y + 1 ; 如下設(shè)置斷言：void mult(int m, int n) A1:n0 int x,y;x = 0 ;A2:(n0)(x=0)y = 0 ;A3:(n0)(x=0)(y=0)A4:(x=ym)(yn)while (y n)A5:(x=ym)(yn) x = x + m ;A6:x=y+1myny = y + 1 ;A4:(x=ym)(yn)A7:x=mn 可以按下面證明此程序的正確性：（1）A1x=0A2是正確的，因?yàn)閷?duì)x賦值不

7、會(huì)影響n的值；（2）A2y=0A3是正確的，同樣，因?yàn)閷?duì)y賦值不會(huì)影響n和x的值；（3）A1x=0,y=0A3是正確的，這可由合成規(guī)則（程序證明中的一條規(guī)則，將一個(gè)程序分成若干段，只要每一段都是正確的，那么它們組合而成的程序也是正確的，似乎有點(diǎn)類似于傳遞性）得到；(4）A1x=0,y=0A4是正確的。很容易由數(shù)學(xué)知識(shí)推出A3A4，再由推論規(guī)則（不嚴(yán)謹(jǐn)?shù)卣f(shuō)，前斷言可以用更強(qiáng)的斷言代替，后斷言可以用更弱的斷言代替，這里被替換的是后斷言）得到A1x=0,y=0A4是正確的。（其實(shí)我感覺(jué)A4的設(shè)置并不是很必要，A3也可以作為下一段的程序的初始斷言，這應(yīng)該是為了證明下面的while語(yǔ)句考慮。）（5）A4

8、ynx=x+m;y=y+1A4是正確的。要證明這一點(diǎn)，可以看出A4(yn)A5是正確的，所以只要證明A5x=x+m;y=y+1A4是正確的(這用到了推論規(guī)則)。設(shè)置中間斷言A6，先證明A5x=x+mA6，很容易就看出來(lái)執(zhí)行賦值語(yǔ)句x=x+m后，x的值為(y+1)m，由此得到A5x=x+mA6，類似也可得到A6y=y+1A4。在根據(jù)合成規(guī)則，即可得到A4ynx=x+m;y=y+1A4。（6）根據(jù)迭代規(guī)則（刻畫(huà)while語(yǔ)句的規(guī)則，簡(jiǎn)單地表示就是:如果QCSQ是正確的，則Qwhile(C)SQC）是正確的），A4whileynx=x+m;y=y+1A4yn是正確的。（7）由于A4(yn)A7是正確

9、的，所以根據(jù)推論規(guī)則，A4whileynx=x+m;y=y+1A7是正確的。最后，由合成規(guī)則及（4）（7）可得，整個(gè)程序是正確的。當(dāng)然，這只是個(gè)非常簡(jiǎn)單的例子。實(shí)際的程序驗(yàn)證除了需要一些推理規(guī)則以外，還需要用到一些公理：賦值公理和賦值預(yù)備公理，它們分別刻畫(huà)了賦值語(yǔ)句之后和之前的斷言的最強(qiáng)斷言和最弱斷言。實(shí)際的程序驗(yàn)證也不會(huì)像這樣一步步人工推導(dǎo)，而是利用自動(dòng)定理證明器。那涉及到更復(fù)雜的內(nèi)容，我不了解。遞歸函數(shù)論數(shù)理邏輯大致可分為邏輯演算、模型論、證明論、遞歸論和公理化集合論這幾個(gè)部分。以上只是非常粗淺地觸及了一些邏輯演算（包括命題邏輯和謂詞邏輯）的內(nèi)容，下面將談?wù)撘稽c(diǎn)點(diǎn)關(guān)于遞歸函數(shù)的知識(shí)。根據(jù)書(shū)

10、本的定義，遞歸函數(shù)以自然數(shù)為研究對(duì)象（一開(kāi)始我頗感詫異，因?yàn)樵贑語(yǔ)言學(xué)習(xí)中，遞歸函數(shù)明顯不是局限于自然數(shù)的），書(shū)本給出的解釋是，其他類型的數(shù)可以由自然數(shù)推廣得到，如整數(shù)可看成自然數(shù)偶（如-2=（1，2），有理數(shù)可以看成自然數(shù)的三階矢量（如-1/2=（1，1，2），等等。遞歸函數(shù)主要研究一個(gè)問(wèn)題的解法的具體構(gòu)造過(guò)程，對(duì)于計(jì)算機(jī)科學(xué)而言，就是算法。用專業(yè)術(shù)語(yǔ)來(lái)說(shuō)，遞歸函數(shù)論屬于一種能行性理論，通俗一點(diǎn)說(shuō)，研究哪些問(wèn)題可以給出一個(gè)算法來(lái)解決。老師上課的時(shí)候主要介紹了遞歸定義的解與相應(yīng)高階函數(shù)的不動(dòng)點(diǎn)的聯(lián)系，（說(shuō)實(shí)話，我從來(lái)沒(méi)想過(guò)遞歸函數(shù)會(huì)與函數(shù)的不動(dòng)點(diǎn)有關(guān)系。）接下來(lái)我就粗略地談一下遞歸函數(shù)與能行可

11、計(jì)算性的關(guān)系(僅僅是觸及表面的敘述)。一個(gè)函數(shù)，如果任給一組初值，一定能在有限步內(nèi)計(jì)算出它的值，則認(rèn)為這個(gè)函數(shù)是能行可計(jì)算的。書(shū)上給出了一個(gè)定理：一般遞歸函數(shù)（比原始遞歸函數(shù)稍微“一般”一點(diǎn)的函數(shù)）是可計(jì)算的，同時(shí)，一切可計(jì)算函數(shù)也都是一般遞歸函數(shù)。書(shū)上對(duì)這個(gè)定理給出了長(zhǎng)達(dá)七八頁(yè)的證明，在此不再贅述。這表明，計(jì)算機(jī)只能解決能表示成一般遞歸函數(shù)的問(wèn)題。因而，對(duì)于一個(gè)謂詞，要判斷其真假，只有當(dāng)其為一般遞歸謂詞時(shí)，它才是可完全判定的。對(duì)能行可計(jì)算性的研究，或者說(shuō)，對(duì)判定問(wèn)題的研究，能夠告訴我們哪些問(wèn)題是一定能夠用計(jì)算機(jī)解決的（如判斷兩個(gè)數(shù)是否互素等等），而哪些則是不可能用計(jì)算機(jī)解決的（如圖靈停機(jī)問(wèn)題

12、、編寫一個(gè)程序證明所有初等數(shù)學(xué)定理等等）。這就避免人們?cè)谝恍┎豢山鉀Q的問(wèn)題的上做無(wú)用功，就像熱力學(xué)定律否定了人們對(duì)永動(dòng)機(jī)的幻想。實(shí)際上在這篇文章中，我只涉及了數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用，而非整個(gè)離散數(shù)學(xué)（那實(shí)在是太龐大了），而且很多概念理解不深，為求準(zhǔn)確，只得照搬書(shū)上的定義。在我看來(lái)，離散數(shù)學(xué)的意義在于，它將生活中的很多問(wèn)題都變得可以用數(shù)學(xué)來(lái)處理，使得數(shù)學(xué)不僅僅再局限于“數(shù)”，比如離散數(shù)學(xué)中對(duì)函數(shù)概念的推廣，任意兩個(gè)集合（無(wú)論是數(shù)值集合還是非數(shù)值集合）都可構(gòu)成函數(shù)關(guān)系，因?yàn)樵陔x散數(shù)學(xué)看來(lái)，函數(shù)本質(zhì)上就是一種特殊的二元關(guān)系?？偠灾?，是離散數(shù)學(xué)奠定了計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)。最后，雖然這是一篇計(jì)算機(jī)導(dǎo)論課程的報(bào)告，但我還是不得不感嘆