2.1.1 命题演算

逻辑演算是数理逻辑的基础，命题演算是逻辑演算最基本的组成部分。命题演算研究命题之间的关系，比如简单命题和复杂命题之间的关系，简单命题如何构成复杂命题，由简单命题的真假如何推出复杂命题的真假等等。对于具体命题，我们不难通过机械运算来达到我们的目的，这就是命题的算术。 、

对于命题演算最早是由美国逻辑学家波斯特在1921年给出证明的，他的证明方法是把命题化为标准形式—合取范式。教科书中常见的证明是匈牙利数学家卡尔马给出的。除了这些构造性证明之外，还有用布尔代数的非构造性证明。

2.1.2 一阶谓词演算

在命题演算中，形式化的对象及演算的对象都是语句。但是，在数学乃至一般推理过程中，许多常见的逻辑推理并不能建立在命题演算的基础上。例如：1．张三的每位朋友都是李四的朋友，王五不是李四的朋友，所以王五不是张三的朋友。因此，我们必须深入到语句的内部，也就是要把语句分解为主语和谓语。

谓词演算要比命题演算范围宽广得多，这由变元也可以反映出来。命题演算的变元只是语句或命题，而谓词演算的变元有三类：个体变元、命题变元、谓词变元。由于谓词演算中有全称量词和存在量词，在这些量词后面的变化称为约束变元，其他变元称为自由变元。最简单的谓词演算是狭义谓词演算，现在通称一阶谓词演算。

谓词演算中的普遍有效公式与命题演算中的重言式还是有差别的。我们有行之有效的具体方法来判定一个公式是不是重言式。这种方法每一步都有明确的规定，并且可以在有限步内完成，这种方法我们称为能行的。但是在谓词演算中，并没有一种能行的方法来判定任何一个公式是否普遍有效的。这就需要寻找一种能行的方法来判定某个具体公式或一类公式是否普遍有效，这就是所谓判定问题。它是数理逻辑中最主要的问题之一。

一阶谓词演算的普遍有效公式也有一个公理系统。另外，同样也有代入规则及推理规则。另外，还有约束变元改字规则等变形规则。在谓词演算中也可以将每一个公式通过变形规则化为标准形式。其中最常用的是所谓前束范式，也就是公式中所有的量词都放在最前面，而且还可以把前束范式进一步化成斯科兰路范式，它不但具有前束范式的形状，而且每一个存在量词都在所有全称量词之前。

利用范式可以解决许多问题，最重要的是哥德尔证明的一阶谓词演算的公理系统的完全性定理，即可以证明：公式A在公理系统中可以证明的当且仅当A是普遍有效的。同样，一阶谓词演算的公理系统也是协调(无矛盾)的、相独立的。1936年丘奇和图林独立的证明一阶谓词演算公式的一般判定问题不可解问题，可以变为去解决具有特殊形式的范式公式的判定问题。