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