(1) 阅读 (1082)

组合逻辑 编辑

词条创建者 匿名用户

组合逻辑

编辑

组合逻辑是一种符号,用于消除数理逻辑中对量化变量的需求。它是由摩西-舍芬克尔和哈斯克-库里提出的,最近在计算机科学中被用作计算的理论模型,也被用作函数式编程语言设计的基础。它以组合器为基础,组合器是由Schönfinkel在1920年引入的,其想法是提供一种类似的方式来建立函数,并消除对变量的任何提及,特别是在谓词逻辑中。组合器是一个高阶函数,它只使用函数应用和早期定义的组合器,从其参数中定义一个结果。在数学中,组合逻辑最初是作为一种"前逻辑",它将澄清量化变量在逻辑中的作用,基本上是通过消除它们。消除量化变量的另一种方式是奎因的谓词漏斗逻辑。虽然组合逻辑的表达能力通常超过一阶逻辑,但谓词漏斗逻辑的表达能力与一阶逻辑的表达能力相同(Quine1960,1966,1976)。组合逻辑的最初发明者摩西-舍芬克尔在他最初的1924年论文之后没有发表任何关于组合逻辑的文章。

组合逻辑

哈斯克尔-库里在1927年底在普林斯顿大学担任讲师时重新发现了组合逻辑。在20世纪30年代末,AlonzoChurch和他在普林斯顿的学生发明了一种功能抽象的对手形式主义,即lambda微积分,它被证明比组合逻辑更受欢迎。这些历史偶然事件的结果是,直到理论计算机科学在20世纪60年代和70年xxx始对组合逻辑感兴趣,几乎所有关于这个主题的工作都是由哈斯克尔-库里和他的学生,或者由比利时的罗伯特-费斯完成的。Curry和Feys(1958)以及Curry等人(1972)调查了组合逻辑的早期历史。关于组合逻辑和lambda微积分的更现代的处理,见Barendregt的书,其中回顾了DanaScott在1960年代和1970年代为组合逻辑设计的模型。

在计算中

编辑

在计算机科学中,组合逻辑被用作计算的简化模型,用于可计算性理论和证明理论。尽管它很简单,但组合逻辑抓住了计算的许多基本特征。组合逻辑可以被看作是λ微积分的一个变体,其中λ表达式(代表函数抽象)被一组有限的组合器所取代,即没有自由变量的原始函数。将lambda表达式转化为组合器表达式很容易,而且组合器还原比lambda还原要简单得多。因此,组合逻辑已经被用来为一些非严格的函数式编程语言和硬件建模。这种观点最纯粹的形式是编程语言Unlambda,其xxx的基元是用字符输入/输出增强的S和K组合器。虽然不是一种实用的编程语言,但乌兰巴达具有一定的理论意义。组合逻辑可以被赋予各种解释。Curry的许多早期论文展示了如何将传统逻辑的公理集转化为组合逻辑方程(HindleyandMeredith1990)。DanaScott在20世纪60年代和70年代展示了如何将模型理论和组合逻辑结合起来。

兰姆达微积分的总结

编辑

兰姆达微积分关注的是被称为兰姆达术语的对象,它可以用以下三种形式的字符串表示。{displaystylelambdav.E_{1}}代表函数,它应用于一个参数,将形式参数v绑定到参数上,然后计算出结果值。表示这样一个函数,它应用于一个参数,将形式参数v与该参数绑定,然后计算出结果为{displaystyleE_{1}}是一个抽象,则该术语可被还原为:{displaystyleE_{2}}。(有时被称为applicand)是一个抽象概念,该术语可以被还原。{displaystyleE_{2}},参数,可以被替换到句子中。参数,可以被替换到E2的主体中。


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/167684/

发表评论

登录后才能评论

词条目录
  1. 组合逻辑
  2. 在计算中
  3. 兰姆达微积分的总结

轻触这里

关闭目录

目录