浅谈逻辑在计算机科学中的应用精选.docVIP

浅谈逻辑在计算机科学中的应用 awwr57367 　　摘 要：本文阐述了逻辑与计算、计算机的起源、程序设计之间的相互关系，并在一阶逻辑的基础上，以LISP、PROLOG等为例，给出了逻辑在程序设计语言和逻辑程序设计中的应用，以此说明计算机科学是逻辑的超大规模应用。 　　关键词：逻辑；计算；计算机 　　 　　1 引言（Introduction） 　　20世纪30年代，Godel、Church、Turing等逻辑学家给出了“可计算”概念的严格定义。Turing于1936年发明了一种抽象机器――第一台通用数字计算机。该机器可用来辅助求解数学基础问题。1940年，Turing的逻辑抽象机付诸实践。Turing设计了ACE计算机。von Neumann主持研制了EDVAC和IAS计算机。50年代，计算机科学成为一门独立的学科。从那时起，逻辑与计算机科学间的联系越来越紧密，主要表现在计算机理论、复杂性理论、类型论、程序设计语言的形式语法和语义、编译技术、程序规范和验证、并发理论、知识工程、归纳学习[1]、数据库理论、专家系统、定理证明、逻辑程序设计和函数程序设计等方面。 　　2 逻辑与计算（Logic and computing） 　　计算机是逻辑和技术的共同产物20世纪30年代，逻辑学家Godel、Church、Turing提出了计算的抽象概念。40年代中期，Turing和von Neumann主持设计、制造了第一台计算机。此外，他们的工作为理解计算过程和计算形式化的发展打下了广泛的逻辑基础。 　　如今逻辑仍是新颖计算机体系结构抽象思想的重要来源，这些新结构包括推理机、数据流机、数据库机、重写机。逻辑为程序设计提供了一整套的思想，同时为程序的推理提供了系统的框架。逻辑在程序设计语言的理论和设计方面发挥着重要作用，数理逻辑可视为两类主要逻辑程序设计语言的直接模型。一类是基于Church的λ一演算[2]的函数程序设计语言，如LISP、ML、LUCID、MIRANDA。另一类是基于Horn子句归结的关系程序设计语言，如PROLOG、PARLOG、GHC。Peter Landin早在20世纪70年代就指出，像ALGOL这样的语言也不过是对Church的λ一演算稍加扩充后的“语法变形”。后来，Martin-Lof直觉主义类型论被用来研究更高层的程序设计语言。其突出特征是程序正确性证明自动伴随着程序书写过程。 　　为设计、理解、讲解计算机及程序设计语言，为编写、分析程序以及进行有关性质的正确推导，逻辑在发挥着重要作用。逻辑学家本身亦可称为抽象工程师。 　　为分析知识表达和推理的过程以及综合用于表达和推理的机器，逻辑为我们提供了语言及技术。 　　在人工智能研究中，逻辑在下述诸方面得到成功应用。 　　（1）知识表示的模型。 　　（2）机器归纳推理和学习的组织。 　　（3）自动演绎系统的理论基础。 　　然而，与逻辑在计算的理论和实践中的作用相比，逻辑在人工智能中的作用更多的是引发人们的争论。要结束这种争论，必须更好地理解自然智能与人工智能的差别。与此同时，逻辑的倡导者和批评者均应做出更多的工作来阐述各自的观点。 　　3 逻辑与计算机的起源（The origin of logic and 　　computing） 　　在现代计算机的发明过程中，逻辑起决定性的作用。这一点并未被人们广为接受。抽象计算机发明于1936年，该发明由1930年Godel的重要逻辑发现所引发。1936年Godel有关计算的理论鼓舞Turing来寻求一种既严格又抽象的逻辑模型。这种模型不仅是关于计算过程的，而且是关于计算机本身的。以此为辅助的理论概念。Turing证明数学的形式系统是不可判定的，从而解决了Hilbert第三问题。尽管Turing的最初计算机仅是抽象逻辑概念，但在这之后的10年（1937―1946）中，Turing成为了实用计算机的设计、制造、使用的领头人。 　　Turing机似乎是真正计算机的抽象。然而，它却创立于20世纪30年代。抽象Turing机是人们可以执行的可能计算模式的理想模型。Turing本人的最大成就是证明了一些Turing机是“通用的”――它们可模仿任何Turing机的行为，他所给出的通用机是如今的存储程序通用计算机的抽象原型。每个特殊机器的编码描述是一程序，它可使通用机当专用机使用。 　　Turing的工作有一明显的技术解释，不需要对每个计算任务都建造一个独立的机器，而只需建造一台机器――通用机器。人们可以通过编写适当的程序来做所需的计算，事实上，Turing本人动手建造了一台通用机。 　　von Neumann在阐述EDVAC、IAS机的设计和操作时，侧重用抽象的逻辑描述语言来说明，很少涉及详细的工