数理逻辑简介

在美国的研究生入学考试（GRE）中，有一节全是逻辑题。给你一种安排、或是分类、或是成分判定、或是决定等等，再给出一系列规则，要你找出合乎所有规则的各种答案来。半个小时5、6道题，每道题5、6小问，怎么才能按时做完呢？

学校老师总是强调要 ” Thinking, Thinking， Thinking “，可怎么去Think呢？有人说，Thinking就是你没有被教过，仍然能够Figure Out（想出来？），这听起来怎么陷入逻辑循环了？思考得有个由量变到质变的过程吧？试试这个问题：

一位女士到一家五金店为她父亲买了一个电钻。回家后才发现买错了；父亲要的那种电钻的价钱是她买的这把的两倍。她回到店里，还回去刚买的那把，拿起更贵的那把就要往家走。店主叫住了她，说她还欠店主钱。女士说，没有啊！她原来付过的钱，加上刚刚还回去的那把电钻的价值，不正是等于手里这个电钻的价钱吗？店主一时无言以对。你能帮他解围吗？

数理逻辑研究如何推理，是关于思考的学问，也可以说是一台测谎仪。数理逻辑的主要分支包括：模型论、证明论、递归论和公理化集合论。数理逻辑和计算机科学有许多重合之处，程序语言学、语义学的研究从模型论衍生而来，而程序验证中的模型检测则从模型论衍生而来。Curry-Howard correspondence给出了“证明”和“程序”的等价性。

数理逻辑的研究对象是命题和谓词；命题就是一句断言或者提议，谓词就是联系两个客观物件的关系词，像是A物“是，属于”B者。为了表述的方便，我们把一切对象都符号化：一个句子是一个符号，一个谓词则用一个函数记号来表示，所以又称其为符号逻辑或形式逻辑。将自然语言符号化是人类的必经之路，这是让无法量化的东西进入到可计量世界的一种途径。

人类进行演绎推理的格式是三段论：给定一个断言：如果P，那么Q；现有P，所以必有Q。这里的P和Q都是原子命题—某种更基本的论断或假设。P称为前题，或者充分条件；Q是结论，或者必要条件。怎么判定断言 “P蕴含Q” 为真呢？一种办法是把它作为公理，即不言自明、不容置疑的真理。

另一种办法是，规定：只有当P为真而Q为假时，整个断言为假，推理无效。这也同时意味着，如果前题P为假，那么任何结论Q，无论真假，你都不能说推理不对。比如说，“如果太阳从西边出来，那么，水就从高处往低处流”；这里的结论是对的，前题是错的，我们没有理由说，推理有错。如果有另外一个人说，“如果太阳从西边出来，那么，水从低处往高处流”；我们也不能说他错，因为太阳是从东边出来的，那是人类对东、西两个方向的定义。这个规定不太合常理，但数学上也只能一刀切了。

数理逻辑中还有逆命题，正如任何运算都有逆运算一样；逆就是相反，把条件与结论颠倒过来：如果Q，那么P。逆命题与原命题，意思上可能存在差异。例如，如果今天气温零下十度以下，那么我就不出门了：这是常理。它的逆命题是，如果我今天没有出门，那么气温一定零下十度以下；这显然不对，我可能是由于别的原因没有出门。如果逆命题Q → P与原命题 P → Q同为真或者同为假，我们就说P与Q互为充分必要条件，或者逻辑等价。

我们还要把句子的连接词符号化，也就是逻辑运算符。有“且、和、与（and）”记为  ，等同于集合的交集（）；”或（）”等同于集合的并；“非、否（~、）”等同于集合的补。这三个算符就可以表出所有的连接词了。’如果P，则Q“， 或者”因为P，所以Q“，即 “P → Q” 等价于 ”~P   Q”；“P除非(unless)Q”等价于“ ~Q → P”或者“Q  P”。还有一个二元运算符“|”（Nor），就构成了一个完备集：P|Q =  (p  q).

三个算符满足一系列的运算规律，如De Morgan定律，分配律，交换律，结合律，同一律等。这其实都与集合的 “并、交、补” 运算规则一致，可以用文氏图来直观地加以证明。命题的蕴含关系等同于集合的包含关系：A ⊆ B 就是从 x  A推出 x  B。说“中国人都是惹不得的”， 可以表示为 C ⊆ Y，C 是所有中国人的集合，Y是所有惹不得之人的集合。如果说“有些中国人是惹不得的”，则可以表示为 C ∩ Y ≠ Φ （空集）。全称量词（）和特称量词（）都可以集合化。

一个命题必须要能断得了真假；含有自由变量的断言，如x + 1 = 2 算不得一个命题。命令句、疑问句、感叹句都算不得命题。给定一个段落，一旦所有句子都符号化成为由逻辑算符连结起来的原子命题的等式了，就得出了N个变量（命题）的方程组：Ei（p1, p2, …, pN） = 1，这里1表示“真”，Ei是以三个逻辑算符把各原子命题连接起来的式子。如果能够得出无矛盾的（0，1）解，那么此段落就是合理的。为了简化求解，我们可以把式子逻辑等价地转化为析取范式（用或（）连接起来的一些原子命题的且（）），或者合取范式（用且（）连接起来的一些原子命题的或（）），蕴含关系就等价于下标集的包含关系。

自然语言符号化的困难在于人类动作太多，谓语关系复杂；而命题逻辑的表达能力有限。举个例子，“每个实数都有一个加法逆元”可以表示为“∀xR ∃yR (x + y = 0)”。怎么表示“实数的所有有界的、非空集合都有上确界”呢？写出来就是：

这里需要对谓词进行量化；也就是要有二阶逻辑甚至更高阶的逻辑。在一阶逻辑中，不能对谓词或者个体变量的性质进行量化。在二阶逻辑中的 “句子” 也是没有（任何种类的）自由变量的合式公式。

接下来，要讨论表达式的有效性、可计算性，推理系统的完备性、紧致性。我们还有《模糊逻辑》，某个关系是否成立是随机的，有一个机率！这还怎么用一个确定的式子去表达？逻辑学家、数学家们是不是走偏了？公理化集合论套不上分析学（连续变量），句子的连贯意义无法表达。怎么捏出句子的几个意思来呢？且听下回分解。