正文 第一章 計算機科學及數理邏輯與計算機科學間的相互關係(2 / 3)

數理邏輯計算機技木是有本質聯係的。這由這兩門學科的研究對象之間的關係就可以看出。邏輯是研究推理規則的,而近年來已經發現,推理(演繹推理)是和計算有本質聯係的。

計算機受控的推理這裏所說的“受控的推理”是指在通常的推理過程中,一組推理規則之中先用哪一條後用哪一條不是機械的;而當這些推理規則的應用順序是機械的,是事先確定了的時候,這種推理規則就構成了計算。

推理與計算是相通的,因之邏輯中的不少研究成果是可以用於計算技術的。但由於邏輯與計算機科學是兩門不同的學科,前者基本上是數學的一支(曆史上是哲學的一支)而後者是一門工程科學,二者的著眼點是不一樣的。前者可以考慮物理性質。邏輯中的結果隻有少數可以直接移用到計算機科學中,大部分的結果須經過變換,才能應用。例如邏輯中研究的可計算性是指理論的可計算性,而計算機科學中的可計算性則是指實際可計算性。

還有,數理邏輯工作者一百年來在應用形式方法時,有豐富的成功經驗,但也有失敗的經驗。例如19世紀末邏輯學者和集合論學者曾誤認為,對應於任意定義的謂詞都存在有集合,結果導致了“悖論”(也就是邏輯上自相矛盾這說明在計算機科學中應用形式方法時也需要注意這一類問題。

程序邏輯是60年代創立的。這種邏輯與古典邏輯的不同在於引進了“程序算子”。試看下列的例子。則在程序段執行以後,下麵是一個具體的這種引進了程序計算機邏輯更適合應用到關於程序的推理過程中。

古典的謂詞邏輯中沒有時間概念或者說沒有過程概念而程序的推理涉及過程的。因為在原來的謂詞邏輯中加人程序或別種過含有時間概念的計算機將使得邏輯更便於應用到計算機科學中。

邏輯型程序設計語言

這用所說的邏輯墦程序設計語,既包括通常所說的“邏輯程序設計語言”,也包括“泛函嗤程序設計語”。這兩種語言是分別以邏輯中的-階謂詞邏輯和“遞歸函數論”為理論的語言,因之都可以稱之為“邏輯銦的”。

邏輯語言最早的一種是表格處理語言是在1961年提出的,這種語言的理論基礎是在1960年的“符號表達式的遞歸函數論”後來1972年柯爾摩等人提出的,以及1977年提出的,然而這這種語言是不同的兩類,語言則是基於“遞歸函數論”的。

語言五年來得到較廣泛的應用,特別是在“人丁智能”方法。近年由於發展智能機課題的提出,人們對語言產生了新的興趣。現在有的地方已經製造出能直接執行用118語言寫成的程序的機器。

計算機語言在70年代初期由柯爾摩等人提出以後,當時並未引起廣泛的注意。80年代初日本人宣布了他們的研製第五代計算機的計劃。在日本人的計劃中,推理機以及智能接口占了重要地位。從此這種語言在國際上引起了很大的注意。

計算機語言如它的名字所指出的是基於“一階邏輯”的程序設計語言。所說的“一階邏輯”即“一階謂詞邏輯”。謂詞邏輯有一階與高階之分,如果謂詞的變元隻能取個體(如自然數)為值,這種謂詞邏輯稱作一階的;如果謂詞的變元可以取個體的集合(如自然數的集合,甚至集合的集合)為值,則這種謂詞邏輯稱作高階的。通常用到的謂詞邏輯是一階的。

最近幾年出現了計算機語言的幾種變種。語言是基於“一階邏輯”的,而它沒有利用“一階邏輯”的全部表達能力;語言中包含有“一階邏輯”中原來沒有的一些成分,而這些成分的邏輯意義是不清楚的。簡稱為近年還有些人發展了其他變種。