数理逻辑-离散基础概念简介

离散数学中包含的模块有: 逻辑与证明、集合论、函数与关系、图论、组合数学、代数结构、数论初步、离散概率

离散数学的特点

下面将对本文中会用到的离散数学中的概念进行介绍,
方便读者在阅读到后续自己用这些概念处理生活中的事情时能够理解

下面仅介绍逻辑与证明、集合论、图、树
这些概念基本足以满足对日常生活中的事情进行解释时思考更系统,表达更清晰
如果阅读本文后激发了你对离散数学的兴趣, 那么可以自己寻找专业书籍系统学习

为了更清晰地解释“命题、集合、图、树”这些概念，并加入命题运算的说明，我们可以采用字符画的方式进行直观展示。下面将分别对每个概念进行简要介绍和图示。

1. 数理逻辑

命题 (Proposition)

在离散数学中，命题是命题逻辑 (Propositional Logic) 的基本构建单元。

定义

一个命题是一个具有真值（True 或 False）的陈述句。命题通常用大写字母表示，如 P,Q,R

• 若命题为真，其真值记为 True（或 1）。
• 若命题为假，其真值记为 False（或 0）。

注意：只有能判断真假的陈述句才是命题。疑问句、命令句、感叹句、含未定变量的开语句（如 x>5）不是命题。

原子命题与复合命题

• 原子命题 (Atomic Proposition)：不能再分解的简单命题，如 “今天下雨。”
• 复合命题 (Compound Proposition)：由原子命题通过逻辑联结词组合而成。

常见逻辑联结词（Logical Connectives）：

示例

设 P: “今天下雨”，Q: “我带伞”。

则 P→Q表示“如果今天下雨，那么我带伞”。这是一个复合命题，其真值依赖于 P和 Q的真值。

在离散数学中，命题逻辑用于形式化推理、证明定理、验证程序正确性等。
蕴含 P→Q只在 P=True,Q=False时为假。

逻辑等值

• 定义：两个命题公式 A 和 B，如果在所有可能的真值赋值下，它们的真值都相同，则称 A 和 B 是逻辑等值的，记作 A ⇔ B。
• 意义：A 和 B 可以在任何上下文中互换，而不改变整体真值。

重要等值式

等值定律 是 命题逻辑中的基本运算规则
这些规则是进行逻辑推理、公式化简和证明的基础。所有规则均以逻辑等价（⇔）形式给出。

等值演算

• 目标：利用上述等值式，将一个复杂的命题公式化简或转换为另一个逻辑等值但形式更简单（或更便于分析）的公式。
• 方法：在一个公式中，将某个子公式替换为与之等值的公式。
• 示例：化简 (P → Q) ∧ (P → ¬Q)
  • (P → Q) ∧ (P → ¬Q) ⇔ (¬P ∨ Q) ∧ (¬P ∨ ¬Q) （应用蕴含等值式）
  • ⇔ ¬P ∨ (Q ∧ ¬Q) （应用分配律）
  • ⇔ ¬P ∨ F （Q ∧ ¬Q 是矛盾式，恒为假 F）
  • ⇔ ¬P （P ∨ F ≡ P）

命题逻辑的推理理论

基本概念

• 论证 (Argument)：一组前提 (Premises) 推出一个结论 (Conclusion)。记作：P₁, P₂, ..., Pₙ ⊨ C
• 有效性 (Validity)：一个论证是有效的，当且仅当在所有使所有前提为真的真值赋值下，结论也必然为真。
• 可靠性 (Soundness)：如果一个论证有效且所有前提为真，则结论为真。

推理规则

这些是构造有效论证的“合法步骤”。

特别留意以下证明的形式结构, 它利用的正是前文命题中的 重要等值式
规则名称与利用的等值式名称是对应的

证明

从前提出发，应用推理规则，一步步推导出结论。

示例：证明 P → Q, Q → R, P ⊨ R

• P → Q (前提) -①
• Q → R (前提) -②
• P (前提) -③
• Q (①,③, 等值式名称: 假言三段论,规则名称: 假言推理 ) -④
• R (②,④, 等值式名称: 假言三段论,规则名称: 假言推理 ) -⑤

证明补充-归谬法

归谬法是一种经典的逻辑证明方法。其核心思想是：为了证明一个命题P为真，我们先假设它的反面（即¬P）为真，然后通过严密的逻辑推理，从这个假设中推导出一个荒谬、矛盾或不可能成立的结论。既然我们的推理过程是正确的，那么导致矛盾的根源只能是我们最初的假设（¬P）是错误的。因此，原命题P必须为真。

简单来说，就是“欲证其真，先证其假会导致荒谬”。

基本步骤：

1. 提出待证命题： 设要证明的命题为 P。
2. 进行反设： 假设命题 P 不成立，即假设 ¬P 为真。
3. 进行推理： 在假设 ¬P 为真的前提下，结合已知的公理、定义、定理或其他已被证明的事实，进行一系列逻辑推理。
4. 导出矛盾： 推理的结果最终会得到一个矛盾。这个矛盾可以是：
   • 与已知的公理或定理相矛盾。
   • 与题目给定的条件相矛盾。
   • 与我们刚刚在推理过程中得出的某个中间结论相矛盾（例如，推出 Q 和 ¬Q 同时成立）。
   • 得出一个明显不符合事实或逻辑的荒谬结论（例如，0=1）。
5. 得出结论： 由于从 ¬P 出发导致了矛盾，而我们的推理过程无误，因此假设 ¬P 必然不成立。所以，原命题 P 成立。

关键点：

• 逻辑基础： 归谬法依赖于排中律（Law of Excluded Middle）和非矛盾律（Law of Non-contradiction）。排中律指出，对于任何命题P，要么P为真，要么¬P为真，二者必居其一。非矛盾律指出，P和¬P不能同时为真。
• 目标明确： 目标不是去接受那个反设，而是利用它作为工具来制造矛盾。
• 普遍适用： 归谬法在证明存在性命题、否定性命题以及一些难以直接证明的肯定性命题时非常有效。

经典例子：证明 √2 是无理数

注: gcb表示最大公约数

这是归谬法最著名的应用之一。

1. 待证命题 P： √2 是无理数。
2. 反设： 假设 √2 不是无理数，即 √2 是有理数 (¬P)。
   • 根据有理数的定义，可以将 √2 写成两个互质整数（没有大于1的公约数）的比值：√2 = a/b，其中 a, b 是整数，b ≠ 0，且 gcd(a, b) = 1。
3. 进行推理：
   • 两边平方得：2 = a² / b²
   • 即：a² = 2b²
   • 这说明 a² 是偶数（因为它是2的倍数）。
   • 如果 a² 是偶数，那么 a 本身也必须是偶数（奇数的平方仍是奇数）。
   • 所以，我们可以令 a = 2k （k 是某个整数）。
   • 代入上式：(2k)² = 2b² => 4k² = 2b² => b² = 2k²
   • 这说明 b² 也是偶数，因此 b 本身也必须是偶数。
4. 导出矛盾：
   • 我们推出了 a 是偶数，b 也是偶数。
   • 这意味着 a 和 b 都有公约数 2。
   • 但这与我们最初的设定 gcd(a, b) = 1（即a和b互质）相矛盾！
5. 得出结论：
   • 因为我们从“√2是有理数”的假设出发，得出了一个矛盾。
   • 所以，这个假设是错误的。
   • 因此，“√2是无理数”这个命题成立。

补充一点题外话,数学归纳法与归谬法是不同的

注意上述例子证明 √2 是无理数, 并非数学归纳法,而是归谬法

归谬法和数学归纳法的区别在于是否涉及自然数的递推、基础步骤或归纳步骤

证明√2是无理数”是归谬法的典范，其逻辑结构如下：

• 假设：√2 是有理数。
• 推理：根据有理数定义和整数性质进行代数推导。
• 矛盾：得出两个数既互质又有公因数2，矛盾。
• 结论：假设错误，故√2是无理数。

这个过程完全没有涉及自然数的递推、基础步骤或归纳步骤，因此绝对不是数学归纳法。

数学归纳法 vs. 归谬法：根本区别

证明补充-消解法

消解法 是一种用于命题逻辑（和谓词逻辑）的形式化推理规则，通过不断合并子句来推导出新结论。如果最终能推出“空子句”，就说明原假设不成立 —— 这是一种机械化反证法。

它的核心思想是：
利用两个包含互补文字的子句，消去这对文字，生成一个新子句。

这部分可以了解一下即可, 他是提供给机器证明的一种方法, 但是需要了解其思想本质是归谬法,是证明一般性结论的重要方法

基本概念准备

1. 文字（Literal）

   • 一个原子命题或其否定。

   • 例如：p、¬q、r 都是文字。

2. 子句（Clause）

   • 若干文字的析取（OR），即形如：p∨¬q ∨ r

   • 在消解法中，所有公式必须转换为合取范式（CNF）

3. 合取范式（CNF, Conjunctive Normal Form）

   • 一系列子句的合取（AND）

   • 形如：(p∨¬q)∧(¬p∨r)∧(q∨¬r)

   • 消解法要求所有前提和结论的否定都写成 CNF 形式

4. 互补文字（Complementary Literals）

   • 一对互为否定的文字，如 p 和 ¬p

消解规则

设有两个子句：

• C1=A∨B
• C2=¬B∨D

其中 B 和 ¬B 是互补文字。

应用消解规则，可得新子句：Resolvent=A∨D

符号表示：

A∨B,¬B∨D
----------
  A∨D 

这表示：从前提出发，推出 A∨D
本质: 如果“A 或 B”为真，且“非 B 或 D”为真，那么至少 A 或 D 必有一个为真

消解法的完整证明流程

要证明：前提集合 S 蕴含结论 T，即 S⊨T

使用消解法的步骤如下：

1. 否定结论

   引入 ¬T，加入前提集合。

   目标：检查 S∪{¬T} 是否一致（可满足）。如果不一致（矛盾），则 T成立。

2. 将所有公式转为 CNF

   将每个前提和 ¬T 化为合取范式，并拆分为独立子句。

   常用技巧：

   • 消除蕴含：p→q≡¬p∨q

   • 德·摩根律、分配律等

3. 应用消解规则

   从已有子句出发，不断对含有互补文字的子句进行消解，生成新子句。

   注意：

   • 新子句加入子句集

   • 避免重复

   • 目标是推出空子句 □（表示“假”）

4. 判断是否推出空子句

   • 如果推出 空子句□ ⇒ 矛盾 ⇒ 原结论 T成立

   • 否则，无法证明（可能不成立，也可能需更多步骤）

示例

要证明: (p→q),(q→r),p⊨r

即：如果 p 则 q；如果 q 则 r；p 成立 ⇒ r 成立

1. 否定结论

   结论是 r，否定为 ¬r

   我们要检查：

   (p→q),  (q→r),  p,  ¬r

   是否导致矛盾。

2. 转为 CNF 并列出子句

   原式	转换过程	子句
   p→q	¬p∨q¬p∨q	C1:¬p∨q
   q→r	¬q∨r¬q∨r	C2:¬q∨r
   p	已是文字	C3:p
   ¬r	已是文字	C4:¬r

   当前子句集：{C1,C2,C3,C4}

3. 应用消解规则

   我们逐步推导：

   • C1:¬p∨q 和 C3:p

     互补文字：¬p 和 p

     消解得：q

     → 新子句 C5:q

   • C2:¬q∨r 和 C5:q

     互补文字：¬q 和 q

     消解得：r

     → 新子句 C6:r

   • C6:r 和 C4:¬r

     互补文字：r 和 ¬r

     消解得：空子句 □

4. 得出结论

   推出了 空子句□ ⇒ 矛盾！

   因此，假设 ¬r 错误 ⇒ r 为真。

   所以原推理有效：(p→q),(q→r),p⊨r

如何得到空子句

空子句 □ 表示“假”或“矛盾”，是消解法成功的标志。

另一个简单例子：直接推出空子句

前提：p∨q, ¬p, ¬q

能推出矛盾吗？

1. C1:p∨q
2. C2:¬p
3. C3:¬q

消解：

• C1 和 C2：(p∨q),¬p ⇒ q → C4:q
• C4:q 和 C3:¬q ⇒ □

矛盾！所以这三个命题不能同时为真。

总结：消解法的核心要点

一阶逻辑

为什么需要一阶逻辑？——命题逻辑的局限性

命题逻辑 (Propositional Logic) 只能处理完整的、不可分割的命题（如 “P: 苏格拉底是人”，“Q: 所有人都会死”），并用逻辑联结词（¬, ∧, ∨, →, ↔）组合它们。

问题：

命题逻辑可以证明:
①一个简单的电路，灯亮（L）当且仅当开关a（A）闭合并且开关b（B）闭合
用命题逻辑表示：

• A: 开关a是闭合的。
• B: 开关b是闭合的。
• L: 灯是亮的。
• 电路逻辑：L ↔ (A ∧ B) （灯亮当且仅当a和b都闭合）

命题逻辑无法证明:
②所有人类都会死” 和 “苏格拉底是人” 推出 “苏格拉底会死
命题逻辑中只能表示为：

• P: 苏格拉底是人
• Q: 所有人都会死
• R: 苏格拉底会死
• 推理形式：P ∧ Q → R 这个推理在命题逻辑中不是有效的，因为 P, Q, R 是独立的原子命题，逻辑上没有必然联系。

两者区别在于①中的有效性能完全拆解为逻辑联结词“↔”和“∧”的结构
而②中的有效性并不能拆解为逻辑联结词的形式

为了解决上诉问题,一阶逻辑通过引入个体、谓词、函数和量词。

基本概念回顾 (对比命题逻辑)

• 项 (Term): 表示个体的表达式。常量、变量、函数作用于项的结果。
• 原子公式: 谓词作用于项。如 Human(socrates), Loves(x, father_of(y))。
• 量词:
  • ∀x P(x): 对论域中所有 x，P(x) 为真。
  • ∃x P(x): 论域中存在至少一个 x，使得 P(x) 为真。

一阶逻辑的核心组成部分

语法与公式构成

• 项 (Term): 表示个体的表达式。
  • 常量、变量、函数作用于项的结果都是项。
  • 例如：socrates, x, father_of(socrates), add(2, x)
• 原子公式 (Atomic Formula): 谓词作用于项。
  • 例如：Human(socrates), Loves(x, father_of(y))
• 合式公式 (Well-Formed Formula, WFF):
  • 原子公式是合式公式。
  • 如果 φ 和 ψ 是合式公式，则 ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) 也是合式公式。
  • 如果 φ 是合式公式，x 是变量，则 ∀x φ 和 ∃x φ 也是合式公式。

语义 (含义)

• 解释 (Interpretation): 为逻辑符号赋予具体意义。
  • 指定一个论域 (Domain)：如 {苏格拉底, 柏拉图, 亚里士多德}。
  • 为每个常量指定论域中的一个具体个体。
  • 为每个谓词指定论域上的一个关系（即哪些元组使其为真）。
  • 为每个函数指定论域上的一个函数。
• 真值: 在一个给定的解释下，一个公式可以被判断为真或假。
• 有效性 (Validity): 一个公式如果在所有可能的解释下都为真，则称为有效（永真）。
• 可满足性 (Satisfiability): 一个公式如果在至少一个解释下为真，则称为可满足。

等值演算

在命题逻辑等值式的基础上，增加与量词相关的等值式。

示例：化简 ¬∀x (Human(x) → Mortal(x))

1. ⇔ ∃x ¬(Human(x) → Mortal(x)) （量词否定）
2. ⇔ ∃x ¬(¬Human(x) ∨ Mortal(x)) （蕴含等值式）
3. ⇔ ∃x (Human(x) ∧ ¬Mortal(x)) （德·摩根律）

结果：存在不是人或者不会死的人 → 即“存在不会死的人”。

一阶逻辑的推理理论

推理规则的扩展

在命题逻辑推理规则的基础上，增加与量词相关的规则。

证明示例

前提：∀x (Human(x) → Mortal(x)), Human(socrates) 结论：Mortal(socrates)

1. ∀x (Human(x) → Mortal(x)) (前提)
2. Human(socrates) (前提)
3. Human(socrates) → Mortal(socrates) (1, 全称实例化, 令 x=socrates)
4. Mortal(socrates) (2,3, 假言推理)

一阶与命题对比