Chap 1 The Foundations: Logic and Proofs⚓︎

Propositional Logic⚓︎

Propositions⚓︎

• 命题 (proposition)：一个陈述句，要么真要么假，但不同时为真为假
• 命题变量 (proposition variables)一般用字母 (e.g. \(p, q, r, s \dots\)) 表示

分类：

• 原子命题 (atomic proposition)不能被表示成更简单的形式的命题
• 复合命题 (compound proposition)由一些命题通过逻辑运算符 (logic operators)连接而成的命题

Truth Tables⚓︎

（略）

Logic Operator⚓︎

假设 \(p, q\) 为两个不同的命题

• 否定 (negation)：\(\neg p\) ( 读作not p)

• 合取 (conjunction)：\(p \land q\) ( 读作p and q)

  注：有时候but也表示 \(\land\)

• 析取 (disjunction)：\(p \lor q\)​ ( 读作p or q)

• 异或 (exclusive or, XOR)：\(p \oplus q\)​ ( 读作p XOR q)

Conditional Statements⚓︎

• 条件语句 (conditional statements, or implication)：\(p \rightarrow q\) ( 读作 if p, then q)

相关知识

• \(p\) 被称为前提 (hypothesis), \(q\) 被​称为结论 (conclusion)
• 条件语句的多种表述：

❗重点记住这两个，很容易混淆： \(p\) only if \(q\)， \(q\) unless \(\neg p\)​

• 从真值表可以看出，前提和结论之间不必有任何关联，\(p \rightarrow q\) 只取决于 \(p\) 和 \(q\)​的真值
• Implication Law: \(p \rightarrow q \equiv \neg p \lor q\) ( 等价命题那一讲会讲到的 )

双条件句 (bioconditional, or bi-implication)：\(p \leftrightarrow q\)​ ( 读作 p if and only if q)

Precedence⚓︎

Logic and Bit Operations⚓︎

位 (Bit)：一种表示两种可能值的记号，即0和1。计算机用位表示信息，位也能用来表示真值

布尔变量 (Boolean variable)：值为true或false的变量

上面所有表格中的T可用1代替，F可用0代替

位串 (Bit strings)：由 0 个或多个位构成的序列，它的长度即位的个数

按位运算 (Bitwise operations)：

• 按位或 (bitwise OR)
• 按位与 (bitwise AND)
• 按位异或 (bitwise XOR)

Supplements(from Exercises)⚓︎

模糊逻辑 (Fuzzy Logic)：一个命题的真值是 \([0,1]\) 间的数。真值为 0 的命题被认为是false，真值为 1 则被认为为true，0-1 之间的数表明不同的真实程度。常用于人工智能中。

Application of Propositional Logic⚓︎

Translating English Sentences⚓︎

方法 : 找原子命题，找逻辑运算符，然后组合起来

System Specifications⚓︎

上一部分 + 一致 (consistent)的概念：存在一组命题变量的可能赋值 ( 真值 )，对于一组命题中的每一条命题均成立。

Boolean Search⚓︎

一些搜索引擎的高级搜索会用到这种方式，这里就不作叙述

Logic Puzzles⚓︎

看看课本例题

Logic Circuits⚓︎

详见：数逻第 2 章

Propositional Equivalences⚓︎

Logical Equivalence⚓︎

• 永真 (Tautology)：真值总是为真的命题
• 永假 (Contradiction)：真值总是为假的命题
• Contingency：既非永真亦非永假的命题

逻辑等价 (Logically equivalent)：两个复合命题在不同的赋值情况下的真值始终相等，即 \(p \leftrightarrow q\)​为永真，记作 \(p \equiv q\)

🌟重要逻辑等价表

Using De Morgan's Laws⚓︎

🌟德 · 摩根定律 (De Morgan's Laws)

• \(\neg (p \land q) \equiv \neg p \lor \neg q\)
• \(\neg(p \lor q) \equiv \neg p \land \neg q\)

拓展版：

• \(\neg(\bigvee ^ n _{j = 1}p_j) \equiv \bigwedge ^ n _{j = 1} \neg p_j\)​

  即 \(\neg(p_1 \lor p_2 \lor \dots \lor p_n) \equiv (\neg p_1 \land \neg p_2 \land \dots \land \neg p_n)\)

• \(\neg (\bigwedge ^ n _{j = 1}p_j) \equiv \bigvee ^ n _{j = 1} \neg p_j\)

  即 \(\neg (p_1 \land p_2 \land \dots \land p_n) \equiv (\neg p_1 \lor \neg p_2 \lor \dots \lor \neg p_n)\)

注：使用时注意改变连接符​

Constructing New Logical Equivalence⚓︎

题型：

• 证明两个逻辑命题等价
• 证明某个逻辑命题永真
• ……

这需要我们灵活使用上表的规律

Propositional Satisfiablilty⚓︎

若存在一种赋值，使得某个复合命题的值为真，则称该命题是satisfiable( 可满足的 )（类似上面一致的概念），这样的一种赋值被称为可满足性问题的一个解；否则称该命题是unsatisfiable( 不可满足的 )

Applications⚓︎

The n-Queens Problem

问题

在 \(n \times n\) 的棋盘上放置 \(n\) 个皇后。皇后可以攻击同行、同列、同一对角线（两条）上的棋子。请找到能使 \(n\) 个皇后不会互相攻击的摆法。

分析

• 先保证每行至少有一个皇后：\(Q_1 = \bigwedge\limits^n_{i = 1} \bigvee\limits^n_{j = 1}p(i, j)\)
• 然后保证每行至多有一个皇后：\(Q_2 = \bigwedge\limits^n_{i = 1} \bigwedge\limits^{n-1}_{j = 1} \bigwedge\limits^n_{k = j + 1}(\neg p(i, j) \vee \neg p(i, k))\)
• 再确保每列至多有一个皇后：\(Q_3 = \bigwedge\limits^n_{j = 1} \bigwedge\limits^{n-1}_{i = 1} \bigwedge\limits^n_{k = i + 1}(\neg p(i, j) \vee \neg p(k, j))\)​

这三个条件的成立能使“每列至少有一个皇后”的条件自动成立

• 接着确定两条对角线：

  • \(Q_4 = \bigwedge\limits^n_{i = 2} \bigwedge\limits^{n - 1}_{j = 1} \bigwedge\limits^{min(i - 1, n - j)}_{k = 1}(\neg p (i, j) \vee \neg p (i - k, k + j))\)
  • \(Q_5 = \bigwedge\limits^n_{i = 1} \bigwedge\limits^{n - 1}_{j = 1} \bigwedge\limits^{min(n - i, n - j)}_{k = 1}(\neg p (i, j) \vee \neg p (i + k, j + k))\)

这里其实还有点问题，目前我还没仔细研究😝

• 最后并在一起便得到最终的解（命题） $$ Q = Q_1 \wedge Q_2 \wedge Q_3 \wedge Q_4 \wedge Q_5 $$

注：Chap 11 还会讲到该问题

Sudoku Puzzle

看书，这里略过🐶

Supplements(from Exercises, but important❗)⚓︎

注：这里的补充部分与 dld 高度重合，可以参考数逻的部分，那里讲得更加详细

Other Logical Operators⚓︎

• Sheffer stroke：与非 (NAND)，符号“\(|\)”，\(p | q \equiv \neg (p \wedge q)\)
• Peirce arrow：或非 (NOR)，符号“\(\downarrow\)”，\(p \downarrow q \equiv \neg(p \vee q)\)

The Dual of a Compound Proposition⚓︎

复合命题 \(S\) 的对偶 ( 命题 )\(S^*\)仅包含逻辑运算符 \(\vee\)，\(\wedge\) 和 \(\neg\)，且满足以下要求：

• 保持 \(\neg\) 不变
• 将 \(\vee\) 替换为 \(\wedge\)，\(\wedge\) 替换为 \(\vee\)
• 将T替换为F，F替换为T。

Functionally Complete Collection of Logical Operators⚓︎

当每个复合命题逻辑等价于一个与它使用相同逻辑运算符集的复合命题，则称这个逻辑运算符集是功能完备的 (functionally complete)

e.g. \(\{ \neg, \wedge, \vee, \rightarrow, \leftrightarrow\}, \{ \neg, \wedge, \vee\}, \{ \neg, \wedge\}, \{ \neg, \vee\}, \{ | \}, \{ \downarrow\}\) 均可为全功能集

拓展——极小全功能集：没有冗余（指从来没用过的）逻辑运算符的全功能集

🌟 Normal Forms⚓︎

注：该概念类似数逻的 " 标准形式 "

• 析取范式 (disjunctive normal form, DNF)= 字面量与合取从句的析取

  • literal( 字面量 )：命题变量及其否定
  • conjunctive clauses( 合取从句 )：单个命题变量 ( 或取补后 ) 的合取，比如：\(p \wedge q, p \wedge \neg q, \neg p \wedge q, \neg p \wedge \neg q\)

• 合取范式 (conjunctive normal form, CNF)= 字面量与析取从句的合取

注：具体参照数逻SOP和POS的概念

🌰

定理：所有的逻辑命题都有与之对应的等价的 DNF 或 CNF

如何得到范式？

1. 先消去 \(\rightarrow , \leftrightarrow\)( 公式见上图 )
2. 令 \(\neg\) 的使用范围缩小至单个原子命题（命题变量），这里常用到德 · 摩根定律和双重否定律
3. 再使用交换律、分配律和结合律得到范式

🌰（计算量有点大…）

主析取范式 (full disjunctive normal form)= 最小项的析取

• Minterm( 最小项 )：所有变量 ( 或取补后 ) 的合取，且每个变量都仅出现一次
• Maxterm( 最大项 )：所有变量 ( 或取补后 ) 的析取，...

注：具体参照数逻SOM和POM

如何获得？

• 计算法

  • 先将命题转化至 DNF 的形式
  • 如果某个析取从句的变量小于 \(n\) 个，则利用否定律和分配律补上缺少的变量，再计算整理

🌰

• 真值表法

  • 列真值表
  • 找到所有复合命题为T的赋值情况
  • 对于每种赋值情况，如果变量为T保持不变，F则取 \(\neg\)，然后进行合取
  • 对所有得到的合取再析取，便得到了 Full DNF

注：可以用类似的方法求 Full CNF，看下面的例子更好理解，或者看数逻相应部分

Predicates and Quantifiers⚓︎

Predicates⚓︎

命题函数 (propositional function)：\(P(x_1, x_2, \dots , x_n)\)，是一种对命题的泛化 (generalization)。当它的所有变量被替换为域(domain) 里的具体值，或受量词 (quantifier)约束时，命题函数就成为一个命题（有真值）

当命题函数有 \(n\) 个变量时，\(P\) 被称为\(n\) 位谓词 (\(n\)​-ary predicate)

连接符( 就是条件和双条件语句 ) 也可以用于谓词逻辑中。如果整个表达式中的变量都是命题（这里特指赋有具体值的命题函数），那么该表达式就是一个命题，否则就不是命题。

temp := c
x := y
y := temp

Quantifiers⚓︎

• 全称量词 (universal quantifiers)：符号 \(\forall\)

  \(\forall xP(x)\) 意思是“for all/ every/ arbitrary/… \(x\), \(P(x)\)”

  \(\forall xP(x) \equiv P(x_1) \wedge P(x_2) \wedge \dots \wedge P(x_n)\)

  这里假定 \(x\) 定义域非空，否则 \(\forall x P(x) \equiv T\)​

• 存在量词 (existential quantifiers)：符号 \(\exists\)

  \(\exists x P(x)\) 意思是“there exists/ for some/ for at least one/ there is/… an \(x\), \(P(x)\)​”

  \(\exists xP(x) \equiv P(x_1) \vee P(x_2) \vee \dots \vee P(x_n)\)

  这里假定 \(x\) 定义域非空，否则 \(\exists x P(x) \equiv F\)​

• 唯一量词 (uniqueness quantifiers)：符号 \(\exists !\)

  \(\exists !xP(x)\) 意思是“\(P(x) \text{ is true for one and only one }x \text{ in the universe of discourse}\)​”

  \(\exists !P(x) \equiv \exists x (P(x) \wedge \forall y (P(y) \rightarrow y = x))\)​

  这个量词可由前两种量词表示出来，因此不常用

注：量词的优先级高于所有逻辑运算符

Quantifiers over Finite Domains⚓︎

考虑在有限域(finite domain) 的情况——可以通过循环 (loop) 逐一判断定义域内每个变量

• 对于 \(\forall x P(x)\)，如果每个 \(P(x)\) 均为真，则为真；只要有一个是错的则为假，循环结束
• 对于 \(\exists xP(x)\)，如果有一个 \(P(x)\) 为真，则为真，循环结束；当循环结束后仍找不到值为真的 \(P(x)\)，则为假

Binding Variables⚓︎

• 如果一个量词用于变量 \(x\)，我们说这个变量是被绑定 (bound)的
• 如果一个变量没有被绑定或者被赋予具体值，我们说这个变量时自由 (free)的

Logical Equivalence Involving Quantifiers⚓︎

谓词命题中的逻辑等价 (Logical equivalence)：充要条件为两个命题有相同的真值，不论它们谓词和变量域是什么。

Negating Quantified Expressions⚓︎

🌟量词的德 · 摩根定律

Translating from English into Logical Expressions⚓︎

🌟Tips:

• \(\text{All } P(x) \text{ are } Q(x) \text{: } \forall x(P(x) \rightarrow Q(x))\)
• \(\text{No } P(x) \text{ are } Q(x) \text{: } \forall x(P(x) \rightarrow \neg Q(x)) \equiv \neg \exists x(P(x) \wedge Q(x))\)
• \(\text{Some } P(x) \text{'s are } Q(x) \text{: } \exists x(P(x) \wedge Q(x))\)
• \(\text{Some } P(x) \text{'s are not } Q(x) \text{: } \exists x(P(x) \wedge \neg Q(x))\)

Logic Programming⚓︎

见书本 \(P_{55-56}\)

Nested Quantifiers⚓︎

嵌套量词 (Nested Quatifiers)：一个包含在另一个量词的量词

循环 (loop) 思想：对于命题 \(P(x, y)\)，就有两重循环，遍历 \(x\) 和 \(y\)。以下例子均外层循环 \(x\)，内层循环 \(y\)

• 对于 \(\forall x\forall y P(x, y)\)，当所有情况均为真时，结果为真；否则为假
• 对于 \(\forall x \exists yP(x, y)\)，对于每一趟外层循环，只要有一种子情况为真，结果为真；否则为假
• 对于 \(\exists x \forall y P(x, y)\)，如果存在一趟外层循环，其所有子情况均为真，结果为真；否则为假
• 对于 \(\exists x \exists y P(x, y)\)，只要有一种情况为真，结果为真；否则为假

Order of Quantifiers⚓︎

量词的顺序不得随意更改，除非所有量词都是同一种量词

Translations⚓︎

下面都是一些例题

The Conversion between Nested Quantifiers and English⚓︎

Nested Quantifiers \(\rightarrow\) English

例题

例 1 例 2

English \(\rightarrow\) Nested quantified logical expressions

例题

例 1 例 2

Translating Mathematical Statements into Statements involving Nested Quantifiers⚓︎

例题

例 1 例 2

题目答案

\[ \begin{align} & \text{solution1: }\forall x \forall y ((x > 0) \wedge (y > 0) \rightarrow (x + y > 0)) \notag \\ & \text{solution2: }\forall x > 0 \forall y > 0 (x + y >0) \notag \end{align} \]

Negating Nested Quantifiers⚓︎

理论部分见前束范式一节

例题

例 1 例 2

Supplements(from Exercises)⚓︎

Prenex Normal Form⚓︎

前束范式 (prenex normal form, PNF)：它的形式如下： $$ Q_1x_1Q_2x_2\dots Q_kx_kP(x_1, x_2,\dots, x_k) $$ 其中\(Q_i, i = 1, 2, \dots, k\)仅代表全称量词\(\forall\) 或存在量词\(\exists\)，\(P(x_1, x_2, \dots, x_n)\) 是没有量词修饰的谓词。

怎么得到 PNF:

1. 消除所有 \(\rightarrow\) 和 \(\leftrightarrow\)
2. 将所有否定号 \(\neg\) 移到最内层，即 \(\neg\) 直接修饰单个谓词或命题 ( 使用德摩根定理)
3. ⭐如果对于同一个变量有不同的量词修饰（见下面 eg 中打红圈的部分），则只保留其中一个，剩下的替换为不同的变量，这样方便最后一步的进行
4. 将所有量词提到最前面

Rules of Inference⚓︎

Valid Arguments in Propositional Logic⚓︎

两种形式：

• \((p_1 \wedge p_2 \wedge \dots \wedge p_n) \rightarrow q\)​
• \[ \begin{align} & p_1 \notag \\ & p_2 \notag \\ & \dots \notag \\ & \underline{p_n} \notag \\ & q \notag \end{align} \]

合法 (valid)：

• 当所有前提为真时结论为真，称一个论证是合法的
• 当所有前提均为真时结论为真，不论前提中某些特定命题是否被命题变量取代，称一个论证形式是合法的，即 \((p_1 \wedge p_2 \wedge \dots \wedge p_n) \rightarrow q\)永真

Rules of Inference for Propositional Logic⚓︎

🌟

Resolution⚓︎

考虑下面两种情况：

• 令 \(r = q\)，则 \((p \vee q) \wedge (\neg p \vee q) \rightarrow q\)
• 令 \(r = F\)，则 \((p \vee q) \wedge \neg p \rightarrow q\)（析取三段论）

由于上述特性，归结 (resolutions)常用于自动推理或构建自动定理证明系统

使用归结作为唯一的推理方法来构建命题逻辑中的证明，前提和假设必须被表达为析取从句 ( 仅通过析取将单个变量或其否定连接起来 )

Using Rules of Inference to Build Arguments⚓︎

解题方法：

1. 选择命题变量
2. 将问题翻译成命题逻辑，得到前提和结论
3. 利用逻辑等价和推理规则构造合法的论证

例题

例 1 例 2

下面这个方法在某些情况 ( 比如下面的例子 ) 下很有用：

Fallacies⚓︎

谬误 (Fallacy) 分类 2 类：

• 肯定结论 (affirming the conclusion)：\(((p \rightarrow q) \wedge q) \rightarrow p\)
• 否定假设 (denying the hypothesis)：\(((p \rightarrow q) \wedge \neg p) \rightarrow \neg q\)

注：这些是错误示例，了解即可，不要当成正确的结论用！

Rules of Inference for Quantified Statements⚓︎

🌰：

Combining Rules of Inference for Propostions and Quantified Statements⚓︎

• 全称假言推理 (universal modus ponens)

• 全称拒取式 (universal modus tollens)

Introduction to Proofs⚓︎

Some Terminology⚓︎

• 定理 (theorem)：( 已知 ) 值为真的语句

  在数学的传统中，定理中的全称量词往往会省略

• 命题 (proposition)：不那么重要的定理，有时也被称为facts或result
• 证明 (proof)：通过合法的论证来证明定理的正确性
• 公理 (axiom)：关于数学的潜在的假设（值为真），或已被证明的定理的假设，或先前证明过的定理
• 引理 (lemma)：有助于证明其他结果的不那么重要的定理
• 推论 (corollary)：可直接从已证的定理中得到的结果
• 猜想 (conjecture)：不清楚真假的语句，通常基于部分证据、启发式的论证或专家的直觉，有待证明

Methods of Proving Theorems⚓︎

Direct Proofs⚓︎

就是用前面介绍过的方法证明

为了证明 \(p \rightarrow q\) 是正确的 (\(p\) 是指所有前提的合取)，我们需要

• 假设所有前提均为真
• 使用推理规则 (rules of inference)、公理、定义、先前证明过的定理和任何逻辑等价关系来证明结论的正确性

Indirect Proofs⚓︎

反证法 (proofs by contraposition) 利用\(p \rightarrow q \equiv \neg q \rightarrow \neg p\)

• 假设结论错误（即 \(\neg q\) 为真）
• 使用推理规则 (rules of inference)、公理、定义、先前证明过的定理和任何逻辑等价关系来证明前提也是错误的（即 \(\neg p\) 为真）

  注：如果有多个前提，我们只需要证出一个前提为假即可

特殊情况：

• 空证明 (vacuous proof)：只要证出 \(p\) 为假，\(p \rightarrow q\) 即为真
• 平凡证明 (trivial proof)：只要证出 \(q\) 为真，\(p \rightarrow q\) 即为真（数学归纳法常用到）

归谬法 (proofs by contradiction)

• 证明单个定理\(p\) 为真

  • 假设 \(p\) 为假，即 \(\neg p\) 为真
  • 得到一组矛盾关系 \(q \wedge \neg q (\equiv F)\)，使得 \(\neg p \rightarrow (q \wedge \neg q)\) 为假，这样就能说明 \(p\) 为真

：证明有无穷多个质数

• 证明条件语句\(p \rightarrow q\) 为真

  • 假设 \(p\) 为真，\(q\) 为假
  • 证明 \(\neg p\) 也为真，得到矛盾（\(p \wedge \neg p\) 一直为假），因此 \(q\) 为真

等价证明 (proof of equivalence)：

• 证明 \(p \leftrightarrow q\) 为真，利用 \(p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)\)
• 证明多个命题 \(p_1 \leftrightarrow p_2 \leftrightarrow \dots \leftrightarrow p_n\) 等价，利用其等价于 \((p_1 \rightarrow p_2) \wedge (p_2 \rightarrow p_3) \wedge \dots \wedge (p_n \rightarrow p_1)\)

Mistakes in Proofs⚓︎

很多错误结果来自于一些没有按逻辑遵循先前步骤的步骤

循环论证 (circular reasoning(begging the question)：某些步骤的正确性建立在自身支持的基础上

很简单的🌰：小明有罪，因为他有罪

更多的例子见 wiki

Proof Methods and Strategy⚓︎

Exhaustive Proof and Proof by Cases⚓︎

前提 \(p\) 可能由一系列情况的析取 (\(p_1 \vee p_2 \vee \dots \vee p_n\)) 构成，这时可以采用分类证明 (proof by cases)的方法，利用 \((p_1 \vee p_2 \vee \dots \vee p_n) \rightarrow q \equiv (p_1 \rightarrow q) \wedge (p_2 \rightarrow q) \wedge \dots \wedge (p_n \rightarrow q)\)

因此，对于规模相对较小的情况，我们可以采用穷举法证明 (exhaustive proof)

有时，直接证明可能不知从何开始，这时可以采用分类证明的方法——每种情况可能会提供额外的信息，有助于推动证明的进行

不失一般性 (without loss of generality, WLOG)

Existence Proofs⚓︎

证明 \(\exists xP(x)\) 为真

• 构造存在证明 (constructive existence proof)：

  • 证明对于定义域内的某些 \(c\)，\(P(c)\) 为真
  • 通过存在推广 (existence generalization)得到 \(\exists xP(x)\) 为真

• 非构造存在证明 (nonconstructive existence proof)：假设定义域内不存在任何一个 \(c\)，使得 \(P(c)\) 为真，推出矛盾

Uniqueness Proofs⚓︎

唯一性证明利用 \(\exists x(P(x) \wedge \forall y(y \ne x \rightarrow \neg P(y)))\)

Disproof by Counterexample⚓︎

要证明 \(\neg \forall xP(x)\)（即 \(\exists x \neg P(x)\)）为真，只要找到一个 \(c\)，使得 \(P(c)\) 为假

Noexistence Proofs⚓︎

要证明 \(\neg \exists xP(x)\)（即 \(\forall x \neg P(x)\)）为真，利用归谬法：假设一个 \(c\)，使得 \(P(c)\) 为真，若存在矛盾就能证明该命题为真

Universally Quantified Assertions⚓︎

要证明 \(\forall xP(x)\) 为真，需要找到对于任意 \(x\)，\(P(x)\) 为真，然后使用UG( 全称推广 )即可

Proof Strategies⚓︎

• 正向推理 (forward reasoning)：通过前提、公理和已知定理得到结论
• 反向推理 (backward reasoning)：要证语句 \(q\) 为真，找到另外一个语句 \(p\)，使得 \(p \rightarrow q\)（也就是所谓要证 \(\dots\)，即证 \(\dots\)）

评论区