逻辑与计算介绍
It is reasonable to hope that the relationship between computation and mathematical logic will be as fruitful in the next century as that between analysis and physics in the last. The development of this relationship demands a concern for both applications and mathematical elegance.
—— J. McCarthy
(希望下个世纪计算与数理逻辑的关系将会像上个世纪分析与物理的关系一样结出丰硕的果实是非常合理的。对这二者之间关系的研究成果即需要有各种应用也需要有数学的优雅。
"The theory of types brings in a new idea for the solution of paradoxes, especially suited to their intentional form. It consists in blaming the paradoxes not on the axioms that every propositional function defines a concept or class, but on the assumption that every concept gives a meaningful proposition, if asserted for any arbitrary object or objects as arguments"
—— K. Gödel
"In general the position as regards all such new calculi is this. – That one cannot accomplish by them anything that could not be accomplished without them. However, the advantage is, that, provided that such a calculus corresponds to the inmost nature of frequent needs, anyone who masters it thoroughly is able – without the unconscious inspiration which no one can command – to solve the associated problems, even to solve them mechanically in complicated cases in which, without such aid, even genius becomes powerless. . . . Such conceptions unite, as it were, into an organic whole, countless problems which otherwise would remain isolated and require for their separate solution more or less of inventive genius."
—— C. F. Gauss
We think we are creating the system for our own purposes. We believe we are making it in our own image... But the computer is not really like us. It is a projection of a very slim of ourselves: that portion devoted to logic, rule, and clarity.
—— Ellen Ullman
用一组基本的指令来编制一个计算机程序,非常类似于从一组公理来构造一个数学证明。
—— D.E.Knuth
【逻辑与计算】包括以下内容:
1. 数理逻辑中证明论和计算的关系,重点探讨集合论、类型论、范畴论和证明论之间的关系
2. 组合逻辑和λ-演算以及相关的函数式编程
3. 可计算函数问题,包括可计算性理论和计算复杂性理论
4. 和逻辑有关的程序设计语言的理论问题
本栏内容面向程序员等对逻辑和计算接口感兴趣的朋友,因此尽量避免涉及理论问题而以初级知识为主。对一些理论问题的探讨和论文的研究则放在姊妹小站【形式语法理论】的【计算基础】内。
—— J. McCarthy
(希望下个世纪计算与数理逻辑的关系将会像上个世纪分析与物理的关系一样结出丰硕的果实是非常合理的。对这二者之间关系的研究成果即需要有各种应用也需要有数学的优雅。
"The theory of types brings in a new idea for the solution of paradoxes, especially suited to their intentional form. It consists in blaming the paradoxes not on the axioms that every propositional function defines a concept or class, but on the assumption that every concept gives a meaningful proposition, if asserted for any arbitrary object or objects as arguments"
—— K. Gödel
"In general the position as regards all such new calculi is this. – That one cannot accomplish by them anything that could not be accomplished without them. However, the advantage is, that, provided that such a calculus corresponds to the inmost nature of frequent needs, anyone who masters it thoroughly is able – without the unconscious inspiration which no one can command – to solve the associated problems, even to solve them mechanically in complicated cases in which, without such aid, even genius becomes powerless. . . . Such conceptions unite, as it were, into an organic whole, countless problems which otherwise would remain isolated and require for their separate solution more or less of inventive genius."
—— C. F. Gauss
We think we are creating the system for our own purposes. We believe we are making it in our own image... But the computer is not really like us. It is a projection of a very slim of ourselves: that portion devoted to logic, rule, and clarity.
—— Ellen Ullman
用一组基本的指令来编制一个计算机程序,非常类似于从一组公理来构造一个数学证明。
—— D.E.Knuth
【逻辑与计算】包括以下内容:
1. 数理逻辑中证明论和计算的关系,重点探讨集合论、类型论、范畴论和证明论之间的关系
2. 组合逻辑和λ-演算以及相关的函数式编程
3. 可计算函数问题,包括可计算性理论和计算复杂性理论
4. 和逻辑有关的程序设计语言的理论问题
本栏内容面向程序员等对逻辑和计算接口感兴趣的朋友,因此尽量避免涉及理论问题而以初级知识为主。对一些理论问题的探讨和论文的研究则放在姊妹小站【形式语法理论】的【计算基础】内。
百家讲坛 ( 全部 )
2018-11-21 11:05:32
我们上篇笔记的目的是熟悉五大逻辑连接符如何用Haskell定义和表示,下面再简单总结一下(假定你已经进入GHCi的repl环境,并成功:load TAMO.hs): 否定(非): not : : Bool -> Bool not True = False not False = True 合取(与): (&&) : : Bool -> Bool -> Bool False && x = False True &am......
(1回应)
2018-10-04 15:20:02
在开始本章之前,我们需要下载官网上的源码TAMO.hs。下载完毕,如果你有本地运行环境,例如GHCi,可将下载文件存放到一个文件夹中,然后运行 $ ghci TAMO.hs 如果没有则可以利用在线GHCi环境,创建一个新文件TAMO.hs,然后将下载文件的内容复制粘贴到这个新文件中。 具体步骤如下: 1. 登录网站:  2. 如果你是第一次登......
(6回应)
2017-12-15 01:24:05
本篇的内容是关于书中第二章的内容,从计算的角度理解逻辑中的一些基本概念,例如,逻辑连接符的概念和意义,论证的有效性,逻辑学中的陈述性概念如何表示为计算中的算法概念,特别是对量词概念在计算中的再定义。 在前面的笔记中,曾经多次强调函数的重要性,这里再一次简明归纳一下: 函数的过程/映射二象性:一个函数,......
(1回应)
2017-04-23 18:09:46
谈谈【闭包】概念——从《Let over Lambda》说开去 《Let over Lambda》第二章的话题是【闭包】,但作者的解说完全是技术性的,只有训练有素的、有经验的职业程序员才能理解。但是我对【闭包】理解则超出了计算机编程的细节,换句话说超出了原书作者的意图和所设定的边界。我认为【闭包】是一个超越具体学科和技术的基础概......
(8回应)
2017-04-22 17:14:20
2017-03-07 20:26:02
在开始之前,先把学习材料交代一下: 本书的电子版下载地址是,这里; 本书的官网链接地址是这里,其中包含了每一章作为例子的Haskell原码。如果有可能,请务必访问官网,除了书中例示源码之外还有许多附加的学习资源,不懂英语的,可用翻译工具大致浏览一下。特别是【读者反馈】部分对于其他初学者很有参考意义。 源码下载......
2017-03-02 15:39:17
《通往逻辑、数学和编程的Haskell之路》—— 从逻辑走向计算(1) 逻辑和计算,对许多置身其外的人来说,似乎是两门不相干的学问,学逻辑的,大部分在哲学系,少部分在数学系,对他们来讲,逻辑就是关于“思维”的,是形而上的;从数学角度来说,就是数学的一个分支;而学计算机的,因为程序语言和离散数学的关系,了解多一......
2017-02-19 19:46:42
2017-02-17 15:09:40
篇外篇:熟悉Haskell编程环境 如果你对Haskell比较熟悉、或者有本地Haskell系统,下面就不必看了。本文是为那些不熟悉编程、特别是对Haskell完全是门外汉准备的,对他们来说,在本地安装Haskell环境可能不是一件非常容易的事。 首先,进入这个网站,映入眼帘的就是这个画面: 这是一个命令行和文本编辑器的模拟环境。这......
(1回应)
2017-02-15 18:41:21
《通往逻辑、数学和编程的Haskell之路》—— 函数 先说说我们这个系列笔记的大方向。第一,这里不是Lisp或Haskell语言教程,也就是说,不会专门去说明某个语言的某个特定功能或语法。第二,内容的重心仍然是在逻辑,例如命题逻辑、谓词逻辑,只是我们的语言换成了编程语言,重点是将逻辑的内容换写成另一种语言,使我们更能......
(4回应)
组合子与λ-演算 ( 全部 )
2018-11-15 07:35:33
4. 组合子的推导 上文介绍了五个组合子,I、C、T、Z、S的基本概念和定义。从这些概念定义中我们可以组合子的基本精神就是:对于任意给定的函数N,都可以以这个函数为参数,创建一个新函数M: MN 不过,这种解释还不能一般化,如果φ不是函数而是一般的变量,上述的命题仍然成立。因此对φ的定义就一定要宽泛,可以容纳任何......
2018-11-14 18:15:06
3. 具有一般性质的特殊函数 (particular functions of very general nature) 这是Schönfinkel对【组合子】的描述。在第三小节中,作者提出了下列组合子: 1) 恒等函数 (identity function),用 I 表示 2) 常项函数 (constancy function),用C表示 3) 交换函数 (interchange function),用T表示 4) 组合函数 (composition......
2018-11-13 04:54:01
2. 柯里化 (Currying) Schönfinkel的论文,分为六个小节,上一篇介绍了第一小节的内容。在这个小节中,作者简单介绍了五个逻辑连接符的表示法,详细阐述Sheffer竖线连接符的概念、操作、真值表以及如何从竖线连接符所表示的“与非”运算派生出其它五个逻辑运算。这就像我们可以从加法运算派生乘法运算,加法运算和负数概......
2018-11-12 18:48:16
2018-11-08 02:57:49
在前一篇笔记我们引入了函数组合的概念,并简单介绍了组合子的基本原理。从日常生活的角度,函数组合就是一个行为链,通过一个或多个因素完成一个动作,这个动作的结果又触发了下一个动作,形成一个链。上餐馆吃饭,包括了一系列动作:点菜——吃——付款。那么“点菜”的参数就是你点的那些菜肴的名称,结果是服务生给你端......
2018-10-21 00:32:41
1. Church和他的计算理论 逻辑源于亚里士多德和古希腊的斯多噶学派,经中世纪的奥卡姆和经院哲学家到莱布尼茨的“calculus ratiocinator”(推理演算器)。而我们的兴趣在于形式逻辑,它源自19世纪的布尔、德摩根、弗雷格、皮尔斯、皮亚诺和其他学者。 20世纪初,怀特海和罗素出版了“Principia Mathematica”(数学原理......
2018-10-19 18:46:50
Propositions as Types by Philip Wadler University of Edinburgh 命题=类型、程序=证明 开场白 一直想写这样一篇文章,但不知道如何下笔。因为逻辑与计算的关系太复杂了,牵涉的学科、话题、术语太多太多,而且十分之九在我们的小站里从未提及过,我没有能力将这些千头万绪而且对大多数人来说背景知识都是陌生的话题......
(7回应)
2017-03-18 08:53:32
组合子(combinator)是一个听上去很陌生但实际上很熟悉的概念:一种特殊的函数。我们在中学学过许多函数,有一般的代数函数,如多项式函数,有理函数、实函数,也有许多特殊函数,如三角函数中的sin、cos,对数函数ln等。这些函数之所以是特殊函数,是因为它们是超越函数,无法用有限次步骤的代数方法求得函数值。 组合子,......
(4回应)
程序员园地 ( 全部 )
2018-11-01 18:18:58
初看到这个标题,有些朋友可能认为:怎么会?函数概念我们在初中课程中就有了。是的,函数作为一个重要的数学概念,我们多多少少都知道一点。再说,这里可能有许多朋友从事和计算机程序设计有关的工作,那么对函数的概念就有了更深更广的认识。那么这里的“初识函数”到底是什么意思? 现在就让我们深究、或者说考据一下函......
2018-10-30 00:59:50
Haskell语言介绍:再谈类型 上次我们初步介绍了类型的概念,具体地说涉及到下列一些问题: 数据的划分:我们分别讨论了数值类型和字符类型; 数据的单复数:单数的数据,指的是个体的数据,例如一个整数,一个字符等;复数的数据,指的是由0或多个同类个体数据构成的集合,例如多个字符组成字符串,多个实数组成一个实数列......
2018-10-27 06:54:54
Beginning in my early years of software development, I was interested in the way formal math shared similarities with writing code. In math, we learned about the concept of proofs, and how, starting from a set of axioms and definitions, one could logically construct true statements to prove a conjec......
(5回应)
2018-10-26 01:38:04
我们上回讨论了Haskell中的数据,有两大类:数值类和字符类。 数值类,就是我们熟悉的自然数、整数、有理数和实数(我们真那么“熟悉”吗?)以及和这类数据相关的运算,包括加减乘除、乘方、开方,以及对数、三角函数等。 字符类,可能不如数值类那么熟悉,但也是我们日常生活中经常接触的数据类别之一。例如写文章、改稿......
2018-10-10 12:40:38
Haskell语言介绍 由于在《通往逻辑、数学和编程的Haskell之路》笔记的主要目的是介绍逻辑,无暇顾及所使用的编程语言,因此这里同时开个系列简单介绍一下Haskell。参考资料有两个: 一个是在线Haskell教程:《Real World Haskell 中文版》 另一个是《Learn you Haskell for great good! A Beginner’s Guide》 二者都属于......
(2回应)
2017-07-14 05:31:51
本书的全称是:《Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp》,这是一本学习Lisp编程的优秀教科书,如果你已经学完了《Common.Lisp:A Gentle Introduction to Symbolic Computation》或者有同等的水平,这一本应当是最值得学习的。在这本书里,你所学习的不再是以语言为中心的语言......
(1回应)
2017-07-05 10:21:45
逻辑是许多形式科学的基础理论,包括数学、形式语法理论、理论计算机科学、人工智能、哲学等。其中在计算机科学及其分支程序设计语言理论中更是基础中的基础。为了使逻辑的学习更加实用、特别是对在IT第一线的战士——程序员来说,逻辑素养的提高更是修炼内功的基本功之一。抽象地讲逻辑,很容易让人觉得是天上的彩虹,赏心......
(1回应)
书评
话题 | 作者 | 回应 | 更新时间 |
逻辑与计算的一本经典 | 来自 赛义甫 | 2018-10-21 00:57 | |
难得一见:用编程语言Haskell学习数理逻辑 | 来自 赛义甫 | 2015-10-07 05:52 |