數(shù)理邏輯及其在計(jì)算機(jī)中的應(yīng)用

靳艷芳，趙彥玲

（鄭州工業(yè)應(yīng)用技術(shù)學(xué)院，河南 鄭州 451100）

1 數(shù)理邏輯概念及其發(fā)展

作為離散數(shù)學(xué)中專門研究推理邏輯的課程，數(shù)理邏輯是一門以數(shù)學(xué)方法為基礎(chǔ)，用符號(hào)系統(tǒng)的形式來研究思維結(jié)構(gòu)及規(guī)律的學(xué)科.古希臘著名學(xué)者亞里士多德最早提出用計(jì)算的形式對(duì)人類的思維進(jìn)行描述和演示的表達(dá)形式.后17世紀(jì)德國著名數(shù)學(xué)家、哲學(xué)家萊布尼茲也曾努力發(fā)明一種通用的科學(xué)語言，可以像數(shù)學(xué)公式一樣對(duì)所有思維的推理過程進(jìn)行計(jì)算，并最終得出準(zhǔn)確無誤的結(jié)論，他的這想法正是現(xiàn)代數(shù)理邏輯的重要啟蒙.

1847年，英國數(shù)學(xué)家布爾在大量試驗(yàn)和實(shí)踐的基礎(chǔ)上發(fā)表了《邏輯的數(shù)學(xué)分析》一文.在布爾看來，邏輯關(guān)系和一些數(shù)學(xué)運(yùn)算之間存在著相似之處，數(shù)學(xué)中的代數(shù)系統(tǒng)具備存在差異性的解釋.通過將代數(shù)系統(tǒng)的解釋引申到邏輯領(lǐng)域，可以實(shí)現(xiàn)對(duì)思維的準(zhǔn)確計(jì)算和演變.因此，貝爾根據(jù)這一理論創(chuàng)建了布爾代數(shù)，在他的代數(shù)系統(tǒng)中由兩個(gè)不同代數(shù)組成一套符號(hào)系統(tǒng)，不同的符號(hào)用來表達(dá)邏輯中的不同概念.布爾在此基礎(chǔ)上又建立了一系列的運(yùn)算法則，這種在以代數(shù)方法為基礎(chǔ)對(duì)思維邏輯進(jìn)行研究的形式，為數(shù)理邏輯的產(chǎn)生奠定了一定的基礎(chǔ).而在現(xiàn)代計(jì)算機(jī)的編程中所使用的二進(jìn)制，則正是由布爾代數(shù)中0和1這兩個(gè)始終處于相互對(duì)立位置的代數(shù)構(gòu)成.從本質(zhì)上來說，現(xiàn)代計(jì)算機(jī)中的二進(jìn)制就是對(duì)0和1一對(duì)矛盾概念進(jìn)行邏輯的推理和判斷.在這種形式的邏輯推理和判斷的進(jìn)程中，我們只需使用“是”或“非”就可以對(duì)邏輯進(jìn)行運(yùn)算.后來，一些數(shù)學(xué)研究者在布爾邏輯思想的基礎(chǔ)上創(chuàng)造了代數(shù)f,即邏輯代數(shù)，并在此基礎(chǔ)上于1946年第一臺(tái)電子計(jì)算機(jī)誕生.最終，隨著先進(jìn)技術(shù)和數(shù)學(xué)科學(xué)的不斷進(jìn)步和發(fā)展，萊布尼茲所幻想的“對(duì)人類思維進(jìn)行機(jī)器模擬”的愿望也成為了現(xiàn)實(shí).

2 數(shù)理邏輯對(duì)計(jì)算機(jī)科學(xué)的重要性

數(shù)理邏輯能力是計(jì)算機(jī)工作者所要具備的基本素質(zhì)，計(jì)算機(jī)技術(shù)的進(jìn)步和發(fā)展與數(shù)學(xué)是密不可分的.可以說，如果沒有一定的數(shù)學(xué)功底一個(gè)計(jì)算機(jī)科學(xué)工作者是很難在計(jì)算機(jī)這個(gè)行業(yè)中嶄露頭角的.對(duì)于單純地應(yīng)用計(jì)算機(jī)進(jìn)行簡單應(yīng)用開發(fā)，如開發(fā)小系統(tǒng)、對(duì)圖片進(jìn)行處理等，可以不用較深的數(shù)學(xué)理論.然而，要想對(duì)計(jì)算機(jī)應(yīng)用進(jìn)行深入開發(fā)，如制作游戲、系統(tǒng)集成等，沒有扎實(shí)的數(shù)學(xué)理論基礎(chǔ)是很難能勝任這些工作的.數(shù)理邏輯等離散數(shù)學(xué)理論知識(shí)已經(jīng)成為計(jì)算機(jī)專業(yè)學(xué)生所必須完成的專業(yè)課程.可見，數(shù)學(xué)思維和推理邏輯與計(jì)算機(jī)有著緊密相連的關(guān)系，在三者關(guān)系中，如果將計(jì)算機(jī)比喻成一座大廈，那么數(shù)學(xué)思維和推理邏輯就是建成這座大廈所必不可少的基礎(chǔ)材料和重要支柱.在數(shù)學(xué)思維與計(jì)算機(jī)的結(jié)合應(yīng)用中，離散數(shù)學(xué)中的數(shù)理邏輯是與計(jì)算機(jī)科學(xué)和發(fā)展關(guān)聯(lián)性最強(qiáng)、發(fā)揮作用最大的一門學(xué)科，它是用來對(duì)學(xué)科的重要理論、技術(shù)及方法行描繪的重要工具.基于離散數(shù)學(xué)的數(shù)理邏輯與計(jì)算機(jī)的密切關(guān)系，在一些場合下數(shù)理邏輯和計(jì)算機(jī)甚至可以被當(dāng)成同義詞使用.一個(gè)計(jì)算機(jī)程序員如果具備扎實(shí)的數(shù)學(xué)功底和較高的數(shù)學(xué)修養(yǎng)，那么他在編寫程序代碼時(shí)就可以在縝密的邏輯思維指導(dǎo)下，編寫出既簡潔又高質(zhì)量的代碼，而促進(jìn)計(jì)算機(jī)軟件質(zhì)量和水平的提高.比如，微軟公司在面試員工時(shí)，經(jīng)常會(huì)出很多需要具備發(fā)散思維、邏輯推理等能力還能解答出來的題目，這就說明微軟公司對(duì)于員工的邏輯思維是非?？粗氐?，只有員工具備了較強(qiáng)的數(shù)學(xué)思維才能真正地促進(jìn)計(jì)算機(jī)科學(xué)及計(jì)算機(jī)行業(yè)的進(jìn)步和發(fā)展.因此，數(shù)理邏輯是計(jì)算機(jī)科學(xué)的進(jìn)步和發(fā)展所不可或缺的思維基礎(chǔ)和持續(xù)動(dòng)力，在計(jì)算機(jī)科學(xué)的發(fā)展進(jìn)程中起著不可忽視的重要作用.

3 數(shù)理邏輯在計(jì)算機(jī)中的應(yīng)用

3.1 數(shù)理邏輯為計(jì)算機(jī)程序語言提供思想和方法

隨著知識(shí)工程和專家系統(tǒng)的不斷出現(xiàn)和快速發(fā)展，人們逐漸意識(shí)到古典邏輯推理方法已經(jīng)無法滿足計(jì)算機(jī)程序設(shè)計(jì)的需要和現(xiàn)代科技的迅猛發(fā)展.特別是隨著信息變化及傳播速度的不斷提高，一定程度上也提高了人類生活環(huán)境中信息的不確定性，要想實(shí)現(xiàn)對(duì)人類思維的模糊推理、復(fù)雜推理到深入研究，建立一個(gè)真正智能的系統(tǒng)來的越來越具有必要性.在這種時(shí)代背景下，非經(jīng)典邏輯逐漸產(chǎn)生并快速發(fā)展.所謂非經(jīng)典邏輯是指以計(jì)算機(jī)語言進(jìn)行程序設(shè)計(jì)為媒介而實(shí)現(xiàn)的模糊邏輯、直覺邏輯、多值邏輯等數(shù)理邏輯.數(shù)理邏輯的相關(guān)推理理論主要是通過為其提供方法和思想來發(fā)揮計(jì)算機(jī)程序設(shè)計(jì)語言中重要的工具作用.可以說，人工智能系統(tǒng)的工作離不開推理，而邏輯思想則是已知前提到推理出未知結(jié)論的重要橋梁.

例1 數(shù)學(xué)中著名的n皇后問題：是否能夠?qū)檎麛?shù)n個(gè)皇后分別放到棋盤上，要求棋盤上的每一行一列以及每一條對(duì)角線上都有且只有一個(gè)皇后，如何放置才能實(shí)現(xiàn)？針對(duì)這一類題目時(shí)，可以運(yùn)用數(shù)理邏輯中的命題邏輯來進(jìn)行解答.首先設(shè)定n2個(gè)命題變項(xiàng)pij(1≤i≤n,1≤j≤n)，其中變項(xiàng)pij即為第i行、第j列中有且僅有的皇后，則要滿足題目中的要求需要滿足以下命題公式：每行最多能有一個(gè)皇后：對(duì)任何 i,j和 k(1≤i≤n,1≤j≤k≤n)，則有 -pij∨-pik=1成立；每行至少有一個(gè)皇后：則對(duì)任意的i（1≤i≤n），都有pi1∨pj2∨.......pin=1成立；對(duì)于每列至少有一個(gè)皇后：則對(duì)任意的j（1≤j≤n），都有 p1j∨p2j∨.......pnj=1成立;對(duì)于每列最多能有一個(gè)皇后：對(duì)任何 i,j和 k,(1≤j≤n,1≤i≤k≤n),-pij∨-pkj=1成立;對(duì)于每條對(duì)角線上最多有一個(gè)皇后：對(duì)任意i,j和k（1≤i，j,k≤n,k≠i）.則如果 1≤j+i-k≤n,那么 pij∨-pk1j+i-k=1成立.依據(jù)上述論述，3皇后問題模型的符號(hào)可以用模型概述為：{p12,p21,p33}，即第1行第2列、第2行第1列以及第3行第3列分別可以放置皇后；4皇后問題模型的符號(hào)可以用模型概述為：{p12,p24,p31}，即第1行第2列、第2行第4列以及第3行第1列分別可以放置皇后；5皇后問題模型的符號(hào)可以用模型概述為：{p12,p24,p31，p43,p55}，即第1行第2列、第2行第4列、第3行第1列、第4行第3列、第5行第5列分別可以放置皇后.以此類推，就可以推理出n皇后問題的排列規(guī)則.

例2 會(huì)跳舞的很有氣質(zhì)，麗麗會(huì)跳舞.因此，麗麗有氣質(zhì).針對(duì)這一推理，可以這 F（x）:x會(huì)跳舞.G(x)有氣質(zhì).a:麗麗.會(huì)跳舞的人有氣質(zhì)：坌x(F（x）→G(x))；麗麗會(huì)跳舞，則 F（a）;麗麗有氣質(zhì)：G（a）.對(duì)于上述邏輯命題可以符號(hào)為坌x(F（x）→G(x))∧F（a）→G（a）.因此，此個(gè)體域?yàn)?D={a}，經(jīng)過量詞消去等式可以簡化為（F（a）→G（a））∧F（a）→G（a），根據(jù)假言推理定律，其結(jié)果必然為真.因此，可以證明麗麗是有氣質(zhì)的.

3.2 數(shù)理邏輯在計(jì)算機(jī)硬件設(shè)計(jì)中的應(yīng)用

作為計(jì)算機(jī)科學(xué)進(jìn)步和發(fā)展的重要理論基礎(chǔ)，一般而言，數(shù)字邏輯在計(jì)算機(jī)科學(xué)中發(fā)揮的重要作用可以追溯到著名數(shù)學(xué)家布爾的布爾代數(shù).布爾運(yùn)算雖然在形式上運(yùn)用了代數(shù)的演算方法，但究其本質(zhì)而言其實(shí)質(zhì)內(nèi)容仍然是邏輯.因此，在計(jì)算機(jī)硬件的設(shè)計(jì)過程中，特別是面對(duì)解決選擇的問題，通常用數(shù)理邏輯進(jìn)行推理.

3.3 數(shù)理邏輯有利于擴(kuò)大計(jì)算機(jī)的應(yīng)用范圍

基于數(shù)理邏輯可以通過推理邏輯的方式進(jìn)一步揭露事物本質(zhì)，因此，數(shù)理邏輯在計(jì)算機(jī)中的應(yīng)用，有利于促進(jìn)語言學(xué)、機(jī)械、心理學(xué)、哲學(xué)、法學(xué)等學(xué)科在計(jì)算機(jī)領(lǐng)域的廣泛應(yīng)用.一個(gè)計(jì)算機(jī)科學(xué)工作者的軟件編程水平在很大程度上要取決于其編程的思維定式，而清晰的數(shù)學(xué)思維、高超人的推理邏輯則有利于編程者具備超強(qiáng)的編程思維，進(jìn)而能夠編寫出讓人耳目一新、標(biāo)新立異的程序.目前，大部分科班出身的計(jì)算機(jī)科學(xué)工作者都是在語法編寫程序的指導(dǎo)下來完成程序編寫的，而僅有少部分具備了軟件編程的思維.脫離了軟件編程思維而編寫程序的方式，很容易導(dǎo)致他們編寫出來的程序毫無邏輯和創(chuàng)新可言.因此，為了培養(yǎng)計(jì)算機(jī)科學(xué)工作者的思維、促進(jìn)計(jì)算機(jī)科學(xué)的進(jìn)步和發(fā)展，加強(qiáng)他們數(shù)學(xué)思維的培養(yǎng)和鍛煉是至關(guān)重要的.

總而言之，數(shù)理邏輯在推動(dòng)人類社會(huì)及近現(xiàn)代科學(xué)的進(jìn)步和發(fā)展的進(jìn)程中發(fā)揮著不可替代的關(guān)鍵作用.在計(jì)算機(jī)科學(xué)中，數(shù)理邏輯通符號(hào)化的方式在計(jì)算機(jī)語言程序設(shè)計(jì)、計(jì)算機(jī)模型、計(jì)算機(jī)硬件系統(tǒng)等應(yīng)用方面發(fā)揮著不可忽視的重要作用.因此，計(jì)算機(jī)科學(xué)工作者要想在軟件編程工作中有所作為，必須注重自身數(shù)學(xué)思維的培養(yǎng)和鍛煉，通過不斷地加強(qiáng)數(shù)學(xué)思維，來充分發(fā)揮數(shù)理邏輯在計(jì)算機(jī)科學(xué)發(fā)展中的重要作用.

〔1〕徐潔磐，朱懷宏，宋方敏.離散數(shù)學(xué)及其在計(jì)算機(jī)中的應(yīng)用[J].北京：人民郵電出版社，2008.1-323.

〔2〕許蔓苓.離散數(shù)學(xué)的方法和挑戰(zhàn)[J].計(jì)算科學(xué)與發(fā)展，2002（06）：1771-1772.

〔3〕何新軍.引進(jìn)數(shù)理邏輯的知識(shí)要符合傳統(tǒng)邏輯的特點(diǎn)[J].中山大學(xué)學(xué)報(bào)論叢，2002（05）.

〔4〕龔靜，王青川.數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用淺析[J].青?？萍迹?004（06）.

〔5〕胡一之，劉恩久，唐南迪.計(jì)算機(jī)數(shù)理邏輯命題演算軟件的研究[J].鞍山鋼鐵學(xué)院學(xué)報(bào)，1996（02）.