- 相關(guān)推薦
淺談數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用論文
摘 要:數(shù)理邏輯是離散數(shù)學(xué)課程中研究推理的邏輯學(xué)科,它為確定一個(gè)給出的論證是否有效提供各種法則和技巧,在計(jì)算機(jī)科學(xué)里用來(lái)檢驗(yàn)程序的正確性,也可以驗(yàn)證定理和推論,同時(shí)在計(jì)算機(jī)模型、計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言、計(jì)算機(jī)硬件系統(tǒng)等方面有著重要作用。研究數(shù)理邏輯在計(jì)算機(jī)科學(xué)領(lǐng)域中的應(yīng)用,必須從研究數(shù)理邏輯的符號(hào)化開始討論、加以分析、驗(yàn)證結(jié)論。
關(guān)鍵詞:數(shù)理邏輯;命題邏輯;一階邏輯;推理理論
離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的重要分支,是研究離散量的結(jié)構(gòu)及相互關(guān)系的學(xué)科,它在計(jì)算機(jī)理論研究及軟、硬件開發(fā)的各個(gè)領(lǐng)域都有著廣泛的應(yīng)用。其內(nèi)容大致包含數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、組合數(shù)學(xué)、圖論和初等數(shù)論6部分,這6部分從不同的角度出發(fā),研究各種離散量之間數(shù)與形的關(guān)系。本文主要研究數(shù)理邏輯部分在計(jì)算機(jī)科學(xué)領(lǐng)域中的應(yīng)用。
1.為計(jì)算機(jī)的可計(jì)算性研究提供依據(jù)
數(shù)理邏輯分為命題邏輯和一階邏輯兩部分,命題邏輯是一階邏輯的特例。在研究某些推理問(wèn)題時(shí),一階邏輯比命題邏輯更準(zhǔn)確。數(shù)理邏輯中的可計(jì)算謂詞和計(jì)算模型中的可計(jì)算函數(shù)是等價(jià)的,互相可以轉(zhuǎn)化,計(jì)算可以用函數(shù)演算來(lái)表達(dá),也可以用邏輯系統(tǒng)來(lái)表達(dá)。
某些自然語(yǔ)言的論證看上去很簡(jiǎn)單,直接就可以得出結(jié)論,但是通過(guò)數(shù)理邏輯中的兩種符號(hào)化表達(dá)的結(jié)果卻截然不同,讓人們很難理解,這就為計(jì)算機(jī)的可計(jì)算性研究埋下伏筆。下面舉一個(gè)簡(jiǎn)單例子加以說(shuō)明。
例1 凡是偶數(shù)都能被2整除。6是偶數(shù),所以6能被2整除。
可見,一個(gè)復(fù)雜的命題或者公式可以利用符號(hào)的形式來(lái)說(shuō)明含義,來(lái)判斷正確性,這使得計(jì)算機(jī)科學(xué)中的通過(guò)復(fù)雜文字驗(yàn)證的推理過(guò)程變得簡(jiǎn)單、明了了。
2.為計(jì)算機(jī)硬件系統(tǒng)的設(shè)計(jì)提供依據(jù)
數(shù)理邏輯部分在計(jì)算機(jī)硬件設(shè)計(jì)中的應(yīng)用尤為突出,數(shù)字邏輯作為計(jì)算機(jī)科學(xué)的一個(gè)重要理論,在很大程度上起源于數(shù)理邏輯中的布爾運(yùn)算。計(jì)算機(jī)的各種運(yùn)算是通過(guò)數(shù)字邏輯技術(shù)實(shí)現(xiàn)的,而代數(shù)和布爾代數(shù)是數(shù)字邏輯的理論基礎(chǔ),布爾代數(shù)在形式演算方面雖然使用了代數(shù)的方法,但其內(nèi)容的實(shí)質(zhì)仍然是邏輯。范式正是基于布爾運(yùn)算和真值表給出的一個(gè)典型公式。
下面以計(jì)算機(jī)科學(xué)中比較典型的開關(guān)電路的設(shè)計(jì)為實(shí)例說(shuō)明數(shù)理邏輯中布爾代數(shù)和范式的應(yīng)用。整個(gè)開關(guān)電路從功能上可以看做是一個(gè)開關(guān),把電路接通的狀態(tài)記為1(即結(jié)果為真),把電路斷開的狀態(tài)記為0(即結(jié)果為假),開關(guān)電路中的開關(guān)也要么處于接通狀態(tài),要么處于斷開狀態(tài),這兩種狀態(tài)也可以用二值布爾代數(shù)來(lái)描述,對(duì)應(yīng)的函數(shù)為布爾函數(shù),也叫線路的布爾表達(dá)式。接通條件相同的線路稱為等效線路,找等效線路的目的是化簡(jiǎn)線路,使線路中包含的節(jié)點(diǎn)盡可能地少。利用布爾代數(shù)可設(shè)計(jì)一些具有指定的節(jié)點(diǎn)線路,數(shù)學(xué)上既是按給定的真值表構(gòu)造相應(yīng)的布爾表達(dá)式,理論上涉及到的是范式理論,但形式上并不難構(gòu)造。
例2 關(guān)于選派參賽選手,趙,錢,孫三人的意見分別是:趙:如果不選派甲,那么不選派乙。錢:如果不選派乙,那么選派甲; 孫:要么選甲,要么選乙。以下諸項(xiàng)中,同時(shí)滿足趙,錢,孫三人意見的方案是什么?
解答:把趙,錢,孫三個(gè)人的意見看做三條不同的線路,對(duì)三條線路化簡(jiǎn)得到接通狀態(tài)(既使公式結(jié)果為1)。
可見,這類選擇問(wèn)題應(yīng)用數(shù)理邏輯來(lái)解決,不但思路清晰、運(yùn)算結(jié)果準(zhǔn)確,而且省時(shí)、省力。
3.為計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言提供主要思想
專家系統(tǒng)和知識(shí)工程的出現(xiàn)使人們認(rèn)識(shí)到僅僅研究那些從真前提得出真結(jié)果的那種古典邏輯推理方法是不夠的,因?yàn)槿祟惿钤谝粋(gè)充滿不確定信息的環(huán)境里,進(jìn)行著有效的推理。因此,為了建立真正的智能系統(tǒng),研究那些更接近人類思維方式的非單調(diào)推理、模糊推理等就變得越來(lái)越必要了,非經(jīng)典邏輯應(yīng)運(yùn)而生。非經(jīng)典邏輯一般指直覺(jué)邏輯、模糊邏輯、多值邏輯等。這些也可以用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)。計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的理論基礎(chǔ)是形式語(yǔ)言、自動(dòng)機(jī)與形式語(yǔ)義學(xué),數(shù)理邏輯的推理理論為二者提供了主要思想和方法,程序設(shè)計(jì)語(yǔ)言中的許多機(jī)制和方法,如子程序調(diào)用中的參數(shù)代換、賦值等都出自數(shù)理邏輯的方法。推理是人工智能研究的主要工作。邏輯的思想就是通過(guò)一些已知的前提推理出未知的結(jié)論。
例3 著名的n皇后問(wèn)題是:是否可以將n(n為正整數(shù))個(gè)皇后放在的棋盤上,使得每行每列都有且僅有一個(gè)皇后,并且每條對(duì)角線上如果有皇后且僅有一個(gè)。
通過(guò)上述幾個(gè)實(shí)例的驗(yàn)證,會(huì)發(fā)現(xiàn)數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用非常廣泛,可以把計(jì)算機(jī)科學(xué)中表面上看似不相干的內(nèi)容通過(guò)找出其內(nèi)在的聯(lián)系作為前提,利用數(shù)理邏輯中的推理理論得到結(jié)論。
參考文獻(xiàn):
[1] 郭遠(yuǎn)華.若干邏輯自動(dòng)推理方法研究[J].華東師范大學(xué)博士學(xué)位論文.2009.
[2] 屈婉玲、耿素云、張立昂.離散數(shù)學(xué)(第2版)[M].北京:清華大學(xué)出版社,2008.
【淺談數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用論文】相關(guān)文章:
淺談數(shù)學(xué)在生活中的應(yīng)用論文06-12
淺談茶文化在美術(shù)創(chuàng)作中的應(yīng)用論文09-14
離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中的作用和應(yīng)用論文06-18
淺談?dòng)?jì)算機(jī)在社會(huì)審計(jì)中的應(yīng)用08-28
淺談微課在中職計(jì)算機(jī)的應(yīng)用論文07-19
淺談電影在中職英語(yǔ)教學(xué)中的應(yīng)用論文09-11
淺談插畫藝術(shù)在平面設(shè)計(jì)中的應(yīng)用論文09-27
淺談?dòng)?jì)算機(jī)科學(xué)與技術(shù)專業(yè)應(yīng)用技術(shù)型人才的培養(yǎng)研究論文09-02