数理逻辑基础 | 命题逻辑 / 谓词逻辑 / 命题符号化

注：本文为 “数理逻辑” 相关文章合集。

略作重排，未整理去重。
如有内容异常，请看原文。

---

数理逻辑、命题逻辑与谓词逻辑之概念梳理

发芽 ing 的小啊呜 于 2020-07-31 12:34:47 首次发布

一、前言

在《离散数学》的学习中，数理逻辑部分涉及的命题逻辑与谓词逻辑等概念，对于初学者而言，容易在学习后逐渐变得模糊。本文旨在对这些基本概念进行详细梳理，以便读者更好地理解和掌握。

二、概念梳理

1. 数理逻辑

数理逻辑是运用数学方法研究逻辑或形式逻辑的学科，属于形式逻辑在符号化、数学化方面的表现形式，本质上仍属于知性逻辑范畴。数理逻辑也称为符号逻辑或理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。其研究对象是对证明和计算这两个直观概念进行符号化后的形式系统。数理逻辑是基础数学的重要组成部分。尽管名称中包含“逻辑”二字，但它并不完全属于单纯逻辑学的范畴。

数理逻辑可以简洁地理解为精确化、数学化的形式逻辑。用数学方法研究关于推理、证明等问题的学科即为数理逻辑，也称为符号逻辑。

（1）数理逻辑包含哪些内容

广义上，数理逻辑 包括集合论、模型论、证明论、递归论等。本文主要介绍其两个最基本且最重要的组成部分：命题演算和谓词演算。

命题演算 主要研究命题如何通过逻辑连接词构成更复杂的命题，以及逻辑推理的方法。命题 是指具有明确意义且能够判断其真假的句子。

谓词演算 也称为命题涵项演算。在谓词演算中，命题的内部结构被分析为具有主词和谓词的逻辑形式，由命题涵项、逻辑连接词和量词构成命题，并研究这些命题之间的逻辑推理关系。

（2）数理逻辑体系

数理逻辑的主要分支包括：逻辑演算（涵盖命题演算和谓词演算）、模型论、证明论、递归论和公理化集合论。

数理逻辑与计算机科学存在诸多重合之处，二者均属于模拟人类认知机理的科学。许多计算机科学的先驱者既是数学家，也是逻辑学家，例如阿兰・图灵、邱奇等。

程序语言学、语义学的研究源于模型论，而程序验证则源自模型论的模型检测。

柯里 —— 霍华德同构揭示了“证明”与“程序”的等价性，这一成果与证明论密切相关，其中直觉逻辑和线性逻辑发挥了重要作用。λ 演算和组合子逻辑等演算现已成为理想的程序语言。

计算机科学在自动验证和自动寻找证明等技术方面的成果，对逻辑研究做出了重要贡献，例如自动定理证明和逻辑编程。

2. 命题逻辑

命题逻辑是指通过逻辑运算符结合原子命题来构成代表“命题”的公式，并允许某些公式构建为“定理”的一套形式化“证明规则”。与谓词逻辑相比，命题逻辑是量化的，其原子公式为谓词函数；与模态逻辑相比，命题逻辑可以是非真值泛函的。

在命题演算中，语言由命题变量（也可称为占位符）和句子 / 判决算子（也可称为连结词）组成。wff 是任何原子公式或在句子操作符之上构建的公式。

存在许多不同的公式系统，它们在以下方面存在差异，尽管它们在一定程度上是等价的：

⑴ 语言（即哪些操作符和变量属于该语言）；

⑵ 公理（如果有的话）；

⑶ 推理规则。

3. 谓词逻辑

在谓词逻辑中，原子命题被分解为个体词和谓词。

个体词 是可以独立存在的事物，包括现实物、精神物和精神事三种。

谓词 是用来刻画个体词性质的词，即刻画事物之间某种关系的词。

例如，“苹果” 是一个现实物个体词，“苹果可以吃” 是一个原子命题。“可以吃” 是谓词，刻画了“苹果” 的一个性质，即与动物或人的某种关系。

三、命题逻辑与谓词逻辑之间的关系

1. 解释一

命题逻辑：

可以理解为事实表示（fact representation）：$A$ 为事实，$B$ 为事实，$A$ 可以推出 $B$ 或 $C$ 等。

谓语逻辑：

增加了函数操作，例如 $\text{function}(A)$ 可以推出 $B$，$C$ 可以推出 $\text{function}(B)$ 等。

例子：

命题逻辑：“4 的倍数” 是 “2 的倍数”。

$$\forall x(x\text{ 是 4 的倍数}\to x\text{ 是 2 的倍数})$$

谓语逻辑：“一个偶数” 的下一个的下一个是 “2 的倍数”。

这里的“下一个”是一个函数，用 $\text{next}$ 表示。

$$\forall x(x\text{ 是偶数}\to \text{next}(\text{next}(x))\text{ 是 2 的倍数})$$

2. 解释二

谓词逻辑可以视为在命题逻辑基础上增加了“量词运用规则”的逻辑体系。

3. 解释三

命题逻辑是一种较为简单、较为宽泛的逻辑形式。

例如，令命题 $A$ 表示 “小明喜欢数学”。

谓词逻辑则是对命题逻辑无法表达的逻辑关系进行进一步细化。

例如，$A(x,y)$ 表示 $x$ 喜欢 $y$，则 “小明喜欢数学” 可以表示为 $A(\text{小明},\text{数学})$。

4. 解释四

通过细分命题，可以得到谓词逻辑命题。

注：

命题逻辑与谓词逻辑之间的关系，可参考知乎：

• 命题逻辑和谓词逻辑之间有什么关系？ - 知乎

---

【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )

韩曙亮 于 2019 - 06 - 28 11:15:21发布

一. 命题概念

1. 命题概念

(1) 命题逻辑的主要内容 ( 逻辑 推理 命题 | 最小单位 | 最简单最基本部分 )

命题逻辑的主要内容：

• 逻辑、推理与命题的关系：逻辑主要研究推理过程，推理过程必须依靠命题来表达。
• 最小单位：命题逻辑中，命题是最小单位。
• 最简单部分：命题是数理逻辑中最基本、最简单的部分。

(2) 什么是命题 ( 陈述句 | 真假必居且只居其一 )

什么是命题：

• 命题概念：命题是陈述客观外界发生事情的陈述句。
• 真假其一：命题是或为真或为假的陈述句。
• 命题特征：
  • 陈述句。
  • 真假必居其一，只居其一。
• 命题判定的说明：
  • 针对将来发生的事：只要是非真即假，并且是陈述句，那么这就是命题。虽然现在不知道是真是假，但必定是非真即假。
  • 未证明的定理：如哥德巴赫猜想，我们不知道其真假，但其如果证明出来必定是非真即假的陈述句，因此也是命题。

2. 命题举例

(1) 命题举例 ( 非真即假 | 将来会知道必是真假 | 将来会证明必是真或假 )

下面句子都是命题：

1. $8$ 小于 $10$：陈述 $8$ 和 $10$ 之间的关系，是真命题；这件事已经发生了。
2. $8$ 大于 $10$：陈述 $8$ 和 $10$ 之间的关系，陈述错了，是个假命题；这件事是不可能发生的；但其是陈述句并且非真即假。
3. 二十一世纪末，人类将住在太空：是陈述句，还没有发生，但肯定是非真即假，将来是否发生不确定，但将来会知道。
4. 任一个 $>5$ 的偶数可表成两个素数的和 - 哥德巴赫猜想：皇冠上的明珠，是一个命题，是陈述句，但现在不知道真假；但终究会证明这个猜想。
5. $2\sqrt{2}$ 的小数展开式中 $12345$ 出现偶数多次：有真假，但真假不知道什么时候知道。

(2) 不是命题举例 ( 不是陈述句 | 没有做出判断 | 真假不确定 | 悖论 )

不是命题：

1. $8$ 大于 $10$ 吗？：不是陈述句，是疑问句。
2. 请勿吸烟！：不是陈述句，是祈使句，没有做出判断，真假不确定。
3. $X$ 大于 $Y$：是陈述句，但真假不确定。
4. 我正在撒谎 - 悖论：
   • 是陈述句，但属于悖论。
     • 外层含义：如果我在撒谎，这个命题为假；如果我没撒谎，这个命题为真。
     • 如果命题为真：说明我在撒谎，含义是这个命题是假，出现了矛盾。
     • 如果命题为假：说明我没有撒谎，含义是这个命题是真的，出现了矛盾。

二. 复合命题与命题符号化

1. 联结词和复合命题

(1) 复杂命题引入 ( 复合命题真假由其组成的小命题的真假进行判断 )

复杂命题：由简单命题能构造更加复杂的命题。

• 期中考试，张三没有考及格。
• 其中考试，张三和李四都考及格了。
• 其中考试，张三和李四中有人考了 $90$ 分。
• 如果张三能考 $90$ 分，那么李四也能考 $90$ 分。
• 张三能考 $90$ 分当且仅当李四也能考 $90$ 分。

(2) 联结词和复合命题

• 联结词：上述“如果……那么……”等连词成为联结词。
• 复合命题：由联结词和命题连接而成的更加复杂命题成为复合命题。
• 简单命题：相对地，不能分解成更简单的命题成为简单命题。
• 复合命题真假：复合命题的真假完全由构成它的简单命题的真假决定。
• 简单命题和复合命题的划分是相对的。

2. 命题符号化

(1) 命题符号化

• 命题符号化：将命题符号化，记为 $p,q,r,\cdots$，类似于代数中使用 $a$ 代表 $1$ 数字一样。
• 符号是变量：
  • 代表数字：在代数中，使用字母 $a$ 代替数字，具体代表哪个数字并不确定，只知道这是个数字即可。
  • 代表命题：同理，命题符号 $p,q,r$ 代替命题，具体代表哪些命题也不确定，只知道这是个命题即可。
• 常元和变元：
  • 常元：代数中字母 $a$ 确定的表示某个数字时，称为常元。
  • 变元：代数中字母 $a$ 表示不确定的数字时，称为变元。
• 命题常元和命题变元：
  • 命题常元：命题 $p$ 代表确定的命题时，称为命题常元。
  • 命题变元：命题 $p$ 代表不确定的命题时，称为命题变元。

(2) 命题符取值号化

• 真 (True)：记为 $1$ 或 $T$。
• 假 (False)：记为 $0$ 或 $F$。
• 命题取值：命题变元 $p$ 取值 $0$ 或 $1$，取值 $0$ 表示 $p$ 是真命题，取值 $1$ 表示 $p$ 是假命题。

三. 联结词

(1) 否定联结词

• 定义：设 $p$ 为一个命题，复合命题“非 $p$”称为 $p$ 的否定式，记为 $\neg p$；$\neg$ 称为否定联结词。

• 真值表：

  $p$	$\neg p$
  $0$	$1$
  $1$	$0$

(2) 合取联结词

• 定义：设 $p,q$ 为两个命题，复合命题“$p$ 而且 $q$”称为 $p,q$ 的合取式，记为 $p\wedge q$，$\wedge$ 称为合取联结词。

• 真值表：

  $p$	$q$	$p\wedge q$
  $0$	$0$	$0$
  $0$	$1$	$0$
  $1$	$0$	$0$
  $1$	$1$	$1$

(3) 析取联结词

• 定义：设 $p,q$ 为两个命题，复合命题“$p$ 或者 $q$”称为 $p,q$ 的析取式，记为 $p\vee q$；$\vee$ 称作析取联结词。

• 真值表：$p\vee q$ 为真，当且仅当 $p$ 与 $q$ 至少有一个为真。

  $p$	$q$	$p\vee q$
  $0$	$0$	$0$
  $0$	$1$	$1$
  $1$	$0$	$1$
  $1$	$1$	$1$

• 举例：

  • 其中考试，张三和李四中有人考了 $90$ 分：
    • $p$ 代表张三考了 $90$ 分。
    • $q$ 代表李四考了 $90$ 分。
    • $p\vee q$ 代表：张三和李四中有人考了 $90$ 分。

(4) 蕴含联结词

• 定义：设 $p,q$ 为命题，复合命题“如果 $p$，则 $q$”称为 $p$ 对 $q$ 的蕴涵式，记做 $p\to q$，其中又称 $p$ 为此蕴涵式的前件，$q$ 为此蕴涵式的后件；$\to$ 为蕴涵联结词。
• 真值表：$p\to q$ 假当且仅当 $p$ 真而 $q$ 假。

$p$	$q$	$p\to q$
$0$	$0$	$1$
$0$	$1$	$1$
$1$	$0$	$0$
$1$	$1$	$1$

• 举例：如果张三能考 $90$ 分，那么李四也能考 $90$ 分。

(5) 等价联结词

• 定义：设 $p,q$ 为命题，复合命题“$p$ 当且仅当 $q$”称作 $p,q$ 的等价式，记做 $p\leftrightarrow q$，$\leftrightarrow$ 记做等价联结词。
• 真值表：$p\leftrightarrow q$ 真当且仅当 $p,q$ 同时为真或同时为假。

$p$	$q$	$p\leftrightarrow q$
$0$	$0$	$1$
$0$	$1$	$0$
$1$	$0$	$0$
$1$	$1$	$1$

• 举例：张三能考 $90$ 分当且仅当李四也能考 $90$ 分。

三. 命题符号化示例

(1) 命题符号化 ( 仔细看三个例子 )

• 铁和氧化合，但铁和氮不化合：
  • 命题 $p$：铁和氧化合。
  • 命题 $q$：铁和氮化合。
  • 复合命题：$p\wedge (\neg q)$。
• 如果我下班早，就去商店看看，除非我很累：
  • 命题 $p$：我下班早。
  • 命题 $q$：去商店看看。
  • 命题 $r$：我很累。
  • 复合命题：$((\neg r)\wedge p)\to q$：去商店的前提是不累并且下班早。
• 李四是计算机系的学生，他住在 $312$ 室或 $313$ 室：
  • 命题 $p$：李四是计算机系学生。
  • 命题 $q$：李四住在 $312$ 室。
  • 命题 $r$：李四住在 $313$ 室。
  • 复合命题：$p\wedge ((q\vee r)\wedge (\neg (q\wedge r)))$；注意这里李四只能住在 $312$ 或者 $313$ 之间的一个，不能都住进入，因此需要将 $q\wedge r$ 的情况排除，$\neg (q\wedge r)$。
  • 复合命题：$p\wedge ((q\wedge (\neg r))\vee ((\neg q)\wedge r))$；这里李四住在 $312$ 不住在 $313$，李四住在 $313$ 不住在 $312$，只能取其中一种情况。

(2) 命题符号化注意点

• 联结词与日常词汇不完全一致：上述五个联结词非、析取、合取、蕴含、等价，来源于日常使用的相应词汇，但不完全一致。
• 命题真假根据定义理解：联结词组成的复合命题的真假值要根据它们的定义去理解，不能根据日常语言的含义去理解。
• 不能对号入座：不要见到“或”就表示成 $\vee$ 析取，如上面的住在 $312$ 或 $313$ 的情况，要考虑只住在 $312$，只住在 $313$，同时住在 $312$ 和 $313$ 的情况。
• 有些词也可以表示为这五个联结词：如“但是”可以表示成“$\wedge$”。

【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表 可满足式 矛盾式 重言式 )

韩曙亮于 2020 - 09 - 25 21:30:37发布

一、命题与联结词

• 原子命题：$p,q,r$ 表示原子命题，又称为简单命题。
• 真值：
  • $1$ 表示命题真值为真。
  • $0$ 表示命题真值为假。
• 联结词：
  • 否定联结词：$\neg$
  • 合取联结词：$\wedge$，$p\wedge q$，$p,q$ 同真，结果才为真，其余情况为假。
  • 析取联结词：$\vee$，$p\vee q$，$p,q$ 同假，结果才为假，其余情况为真。
  • 蕴含联结词：$\to$，$p\to q$，$p$ 真 $q$ 假，结果才为假，其余情况为真。
  • 等价联结词：$\leftrightarrow$，$p\leftrightarrow q$，$p,q$ 真值相同时为真，表示等价成立，$p,q$ 真值相反时为假，等价不成立。

二、命题公式

命题公式组成：

1. 单个命题变元 / 命题常元是命题公式。
2. 如果 $A$ 是命题公式，则 $(\neg A)$ 也是命题公式。
3. 如果 $A,B$ 是命题公式，则 $(A\wedge B),(A\vee B),(A\to B),(A\leftrightarrow B)$ 也是命题公式。
4. 有限次应用 1、2、3 形成的符号串是命题公式。（无限次不行）

三、命题公式示例

• 简单命题：$p$
• 复合命题：使用联结词的命题称为复合命题。
  • $\neg p$
  • $(p\to q)$，最外层的括号可以省略，$p\to q$
  • $(p\to (q\to r))$，最外层括号可以省略，内层的括号不可以，$p\to (q\to r)$。

四、联结词优先级

• “$\neg$” 大于 “$\wedge ,\vee$” 大于 “$\to ,\leftrightarrow$”
• $\wedge ,\vee$ 优先级相同。
• $\to ,\leftrightarrow$ 优先级相同。

五、真值表

$p$	$q$	$p\to q$	$p\wedge \neg q$	$p\wedge (p\vee q)\leftrightarrow p$
$0$	$0$	$1$	$0$	$1$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$0$	$1$

• $p\to q$ 是可满足式。
• $p\wedge \neg q$ 是矛盾式，又称为永假式。
• $p\wedge (p\vee q)\leftrightarrow p$ 是重言式，又称为永真式。
• 可满足式：真值表中，至少有一个结果为真，可以都为真。
• 矛盾式 ( 永假式 )：所有的真值都为假。
• 可满足式与矛盾式，是二选一的，复合命题要么是可满足式，要么是矛盾式。
• 重言式 ( 永真式 ) 是可满足式的一种。

---

【数理逻辑】命题逻辑（等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定律 | 蕴涵等值式…）

韩曙亮 于 2020 - 09 - 27 11:44:33发布

一、等值演算

• 等值式
• 基本等值式
• 等值演算置换规则

二、等值式

• 等值式概念：$A,B$ 是两个命题公式，如果 $A\leftrightarrow B$ 是永真式，那么 $A,B$ 两个命题公式是等值的，记做 $A\iff B$。
• 等值式特点：$A$ 和 $B$ 两个命题公式，可以互相代替，凡是出现 $A$ 的地方都可以替换成 $B$，凡是出现 $B$ 的地方都可以替换成 $A$。
• 证明 $p\to q$ 与 $\neg p\vee q$ 是等值式：

$p$	$q$	$p\to q$	$\neg p\vee q$	$(p\to q)\leftrightarrow (\neg p\vee q)$
$0$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

写出两个命题公式的真值表，从而计算 $(p\to q)\leftrightarrow (\neg p\vee q)$ 的真值表，计算完成后发现其是永真式，根据定义，这两个命题公式是等价的，$(p\to q)\iff (\neg p\vee q)$。

三、基本等值式

基本运算规律：

1. 幂等律：
   • $A\iff A\vee A$
   • $A\iff A\wedge A$
2. 交换律：
   • $A\vee B\iff B\vee A$
   • $A\wedge B\iff B\wedge A$
3. 结合律：
   • $(A\vee B)\vee C\iff A\vee (B\vee C)$
   • $(A\wedge B)\wedge C\iff A\wedge (B\wedge C)$
4. 分配律：
   • $A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$
   • $A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)$

新运算规律：

5. 德摩根律：
   • $\neg (A\vee B)\iff \neg A\wedge \neg B$
   • $\neg (A\wedge B)\iff \neg A\vee \neg B$
   • 有了与 ($\wedge$) 非 ($\neg$)，就可以表示或 ($\vee$)。
   • 有了或 ($\vee$) 非 ($\neg$)，就可以表示与 ($\wedge$)。
6. 吸收率：
   • 前者将后者吸收了：$A\vee (A\wedge B)\iff A$
   • 后者将前者吸收了：$A\wedge (A\vee B)\iff A$

$0,1$ 相关的运算律：

7. 零律：
   • $A\vee 1\iff 1$
   • $A\wedge 0\iff 0$
   • $1$ 是或运算的零元，$0$ 是与运算的零元。
   • 与零元进行运算结果是零元。
8. 同一律：
   • $A\vee 0\iff A$
   • $A\wedge 1\iff A$
   • $0$ 是或运算的单位元，$1$ 是与运算的单位元。
   • 与单位元进行运算结果是其本身。
9. 排中律：$A\vee \neg A\iff 1$
10. 矛盾律：$A\wedge \neg A\iff 0$

对偶原理适用于上述运算律，将两边的 $\wedge ,\vee$ 互换，同时 $0,1$ 互换，等价仍然成立。

等价蕴含运算规律：

11. 双重否定率：$\neg \neg A\iff A$
12. 蕴涵等值式：
    • $A\to B\iff \neg A\vee B$
    • 替换蕴含联结词：蕴含联结词 $\to$ 不是必要的，使用 $\neg ,\vee$ 两个联结词可以替换蕴含联结词。
13. 等价等值式：
    • $A\leftrightarrow B\iff (A\to B)\wedge (B\to A)$
    • 双箭头 ( 等价联结词 ) 可以理解成充分必要条件。
    • $A\to B$ ( 蕴含联结词 ) 理解成 $A$ 是 $B$ 的充分条件，$B$ 是 $A$ 的必要条件。
    • $B\to A$ ( 蕴含联结词 ) 理解成 $B$ 是 $A$ 的充分条件，$A$ 是 $B$ 的必要条件。
    • 替换等价联结词：等价联结词 $\leftrightarrow$ 不是必要的，使用 $\to ,\wedge$ 两个联结词可以替换等价联结词。
14. 等价否定等值式：$A\leftrightarrow B\iff \neg A\leftrightarrow \neg B$
15. 假言易位 ( 逆否命题 )：
    • $A\to B\iff \neg B\to \neg A$
    • $A$ 称为前件，$B$ 称为后件 ( 结论 )。
16. 归谬论 ( 反证法 )：
    • $(A\to B)\wedge (A\to \neg B)\iff \neg A$
    • 这是反证法的原理，由 $A$ 推导出 $B$ 和 $\neg B$，$B$ 和 $\neg B$ 是矛盾的，则 $A$ 是错的，$\neg A$ 是对的。

四、基本运算

• 等价等值式：等价联结词 $\leftrightarrow$ 不是必要的，使用 $\to ,\vee$ 两个联结词可以替换等价联结词。
• 蕴涵等值式：蕴含联结词 $\to$ 不是必要的，使用 $\neg ,\vee$ 两个联结词可以替换蕴含联结词。
• 德摩根律：
  • 有了与 ($\wedge$) 非 ($\neg$)，就可以表示或 ($\vee$)。
  • 有了或 ($\vee$) 非 ($\neg$)，就可以表示与 ($\wedge$)。
• 因此得出结论，与非或者或非 ( 二选一 )，可以表示所有的命题。

五、等值演算

证明 $p\to (q\to r)$ 与 $(p\wedge q)\to r$ 是等价的。

证明上述两个命题是等价的，有两种方法：

1. 列出真值表。
2. 进行等值演算。

$p\to (q\to r)$

1. 使用蕴涵等值式，进行置换：将 $q\to r$ 置换为 $\neg q\vee r$
   • $\iff p\to (\neg q\vee r)$
2. 继续使用蕴涵等值式，将外层的蕴含符号置换：
   • $\iff \neg p\vee (\neg q\vee r)$
3. 使用结合律，将 $p,q$ 结合在一起：
   • $\iff (\neg p\vee \neg q)\vee r$
4. 使用德摩根律，将 $\neg$ 提取到外面：
   • $\iff \neg (p\wedge q)\vee r$
5. 使用蕴涵等值式，进行置换：
   • $\iff (p\wedge q)\to r$

---

数理逻辑初步：命题逻辑、一阶逻辑和二阶逻辑

音程 已于 2024-11-27 19:31:46 修改

本文介绍命题逻辑（很少部分人称其为零阶逻辑）、一阶逻辑和二阶逻辑。这些形式推理的逻辑系统，其表达与推理能力依次增强。

命题逻辑

命题逻辑：propositional logic

命题

命题具有真假值，因此能称得上是命题的句子具有特定特点，例如它不是一个问句，而是一个陈述句。进一步而言，即使是陈述句，也未必是命题。命题是具有真假值的陈述句。

一般来说，判断一个陈述句是否为命题，只需考虑该陈述句是否具有判断的意味。例如，“5<2”是一个命题，且为假命题；“北京是中国的首都”是命题，且为真命题。然而，有时判断一个陈述句是否为命题较为困难，如著名的“说谎者悖论”——“我在说谎”是命题吗？答案是：这是一个悖论，不是命题。

悖论是指同一命题中存在两个对立结论，而这两个结论都能自圆其说。即：事件 P 可以推导出事件非 P；事件非 P 可以推导出事件 P。

“我在说谎”：

• 若为真，则“我在说谎”本身是一个谎话，与“真”矛盾。
• 若为假，则“我在说谎”是一个谎言，与“假”又矛盾。

命题逻辑

确定一个命题后，为了形式化，我们用小写字母 $p,q,r$ 表示这些命题。接着，使用命题连接词将 $p,q,r$ 组合成更复杂的命题，称为命题公式，此时 $p,q,r$ 称为命题变元或原子命题（即不可再分）。这一过程也可形式化为 $\alpha =f(p,q,r)$。

命题连接词常用的有以下五个：非、且（合取）、或（析取）、蕴含（推出）、等价（当且仅当）。

名称	符号	含义
非	$\neg$	对命题的否定
且（合取）	$\wedge$	当两个命题都为真时，整个合取命题才为真
或（析取）	$\vee$	两个命题中只要有一个为真，整个析取命题就为真
蕴含（推出）	$\to$	若前一个命题成立能推出后一个命题成立，则该蕴含关系成立
等价（当且仅当）	$\leftrightarrow$	两个命题的真假性完全相同，即同真同假时，等价关系成立

例子：

设 $\alpha =f(p,q,r)=p\wedge q\wedge r$，则若 $(p,q,r)=(1,1,0)$，命题公式 $\alpha$ 为假。

对于一个命题公式，可以构造一个真值表。例如，对于 $\alpha =f(p,q)=p\wedge q$：

$p$	$q$	$\alpha$
0	0	0
0	1	0
1	0	0
1	1	1

指派（assignment）和解释（interpretation）的概念：设 $\alpha =f(p_1,\cdots ,p_n)$，可绘制其真值表（同样，最后一列是因变量 $\alpha$ 的值）。那么指派和解释为：

一阶逻辑

作为命题逻辑向一阶逻辑的过渡，考虑如下经典三段论：

所有人都会死
苏格拉底是人
所以苏格拉底会死

该逻辑关系能否用命题逻辑表达？先定义命题 $p,q,r$：

$p$: 所有人都会死
$q$: 苏格拉底是人
$r$: 苏格拉底会死

用上述定义的命题表达三段论中的因果关系，有：$(p\wedge q)\to r$。此逻辑表达式虽能表达三段论的表层意思，但背后的深层次逻辑未表达出来。

若命题 $s$ 为：

$s$: 小明是人

从语言上推导，可得出 $t$: 小明会死 的结论。但若之前将三段论表述为 $(p\wedge q)\to r$，那么给定条件 $s$，通过逻辑符号的推理，无法推出 $t$。所谓逻辑符号的推理，例如 $(\neg (\neg p))=p$，只能通过与、或、非等运算以及 $p$ 等符号去推理，会发现推不出 $t$。总结就是：语言上推得过去，用逻辑符号和运算推不过去，根本原因是命题逻辑表达力太弱。

现在考虑使用一阶逻辑（First-order Logic）。它也是一种形式符号推理系统，也称一阶谓词演算、低阶谓词演算（Predicate Calculus）、限量词（Quantifier）理论，有人称其为“谓词逻辑”，但这种说法不够精确。总之，一阶逻辑是一种形式推理的逻辑系统，是一种抽象推理的符号工具。

一阶逻辑不同于单纯的“命题逻辑”，因为它使用了“任意”和“存在”。举一个一阶逻辑表达式的例子：

$\exists x(Math(x)\to Prof(x))$

其表示：存在一个 $x$，如果 $x$ 是数学老师，那么 $x$ 是教授。

再举一个例子：

$\forall x(Math(x)\to Prof(x))$

其表示：任意一个 $x$，如果 $x$ 是数学老师，那么 $x$ 是教授。

看完上述两个例子后，不难发现其特点在于：将命题逻辑中命题的一些名词变量化。为了区别，再举例如下：

命题逻辑中的表示：

小明是一位数学家
$p$: 小明是一位数学家

一阶逻辑中的表示：

小明是一位数学家
$math(小明)$。
其中 $math(x)$ 表示：$x$ 是一位数学家。

此时，可逐渐发现一阶逻辑的强大。为了证明这一点，可将前面的三段论使用一阶逻辑进行完美表示：

所有人都会死
苏格拉底是人
所以苏格拉底会死

定义：

• $die(x)$: $x$ 会死
• $people(x)$: $x$ 是人

那么上述三段论可表示为：

$\forall x(people(x)\to die(x))$

$people(“苏格拉底”)\to die(“苏格拉底”)$

这一次，若小明是人，即 $people(“小明”)$，根据 $\forall x(people(x)\to die(x))$，可推导出 $die(“小明”)$，即小明会死。这次总算完美解决了。

相关概念：

• 谓词：一个含有变量的命题，例如上述 $math(x)$。
• 谓词符号：如上述的 $math,die$ 等。通常习惯用大写表示，如 $F,G,H$，但也可随意使用。
• 函数符号：早已熟悉，通常用小写表示 $f,g,h$，但也可随意使用，如构造函数时也用过 $F$。

谓词符号和函数符号非常相似，只是在映射上，函数更加宽泛 $f:A\to B$，而谓词更加狭窄 F : D → E = { 0 , 1 } F: D \rightarrow E = \{0, 1\} F:D→E={0,1}，例如 $people(“桌子”)$ 是假的，所以为 0。

个体域：即谓词中变量的取值范围。例如 $math(x)$ 中，$x$ 的取值范围是人这种类型的个体。个体域可以是有限的，也可以是无限的。

二阶逻辑

有了上述一阶逻辑的概念后，二阶逻辑便水到渠成。假设要将如下语句翻译成逻辑：

Leibniz Law: “对于任意个体 $x$ 和 $y$，只要 $x$ 和 $y$ 相等，那么 $x,y$ 具有相同的性质”

那么显然，可翻译如下：

• $P(z)$: $z$ 具有性质 $P$。
• $E(u,v)$: $u$ 和 $v$ 相等。

从而翻译为：

$$\forall x,y[E(x,y)\to \forall P(P(x)\leftrightarrow P(y))]$$

看到上述表示后，细心的人应该能够发现，这次量词符号竟然作用在谓词符号上 $\forall P$，而之前在一阶谓词中只允许量词作用在个体上，例如 $\forall xP(x)$。这就是一阶逻辑和二阶逻辑的区别。

上述表示非常完美，读者应当细细品味。

其他逻辑系统

模糊逻辑

对于命题逻辑，一个命题要么为真，要么为假，不存在模糊地带，即是一个二值逻辑。如今，为了增强表达能力，当值域大小不止为 2 时，称为多值逻辑，或模糊逻辑。

参考资料：

• 一阶逻辑与二阶逻辑的区别 一元谓词多元谓词-CSDN博客

---

via：

• 数理逻辑、命题逻辑、谓词逻辑之概念详细梳理_命题逻辑和谓词逻辑的区别-CSDN博客
  https://blog.csdn.net/qq_43543789/article/details/107710256

• 【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 )_析取,合取,蕴含,等价 - CSDN博客 韩曙亮 于 2019 - 06 - 28 11:15:21发布
  https://blog.csdn.net/shulianghan/article/details/93914663

• 【数理逻辑】命题逻辑 ( 命题与联结词回顾 | 命题公式 | 联结词优先级 | 真值表 可满足式 矛盾式 重言式 )命题联结词总结 - CSDN博客 韩曙亮于 2020 - 09 - 25 21:30:37发布
  https://blog.csdn.net/shulianghan/article/details/108803629

• 【数理逻辑】命题逻辑 ( 等值演算 | 幂等律 | 交换律 | 结合律 | 分配律 | 德摩根律 | 吸收率 | 零律 | 同一律 | 排中律 | 矛盾律 | 双重否定率律 | 蕴涵等值式… )等值演算法 - CSDN博客 韩曙亮 于 2020 - 09 - 27 11:44:33发布
  https://blog.csdn.net/shulianghan/article/details/108804672

• 数理逻辑初步：命题逻辑、一阶逻辑和二阶逻辑_一阶逻辑和二阶逻辑的区别-CSDN博客
  https://liubingqing.blog.csdn.net/article/details/117397388