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