Ch1. 朴素命题逻辑
命题
命题是可以明确判断真假的句子，由简单命题、连接词和括号组成
命题可以递归定义：
- 一个简单命题是一个命题，简单命题通常是一个主语+谓语
- 如果 \(P\) 和 \(Q\) 是命题，则通过有穷次的逻辑连接词 \((\neg P)\)（否定）、\((P \land p)\)（合取）、\((P \lor p)\)（析取）、\((P \to p)\)（蕴含）、\((P \leftrightarrow p)\)（双向蕴含）连接的也都是命题
连接词的优先级由高到低依次为 \((\neg P)\)（否定）、\((P \land p)\)（合取）、\((P \lor p)\)（析取）、\((P \to p)\)（蕴含）、\((P \leftrightarrow p)\)（双向蕴含）
真值函数
真值函数用于形式化定义命题逻辑的语义，每个命题都可以解释为一个真值函数，从而确定它在所有可能赋值下的真值
定义函数 \(\sigma:\{p_1, \cdots, p_{n}\} \to \mathbb{T}\) 是对于简单命题 \(\{p_1, \cdots, p_{n}\}\) 的一个赋值，\(\sigma{p_{i}}\) 表示 \(\sigma\) 下变量 \(p_{i}\) 的值
设 \(P\) 是一个命题（简单命题，或由简单命题通过连接词构成的命题），\(P\) 中的简单命题为 \(\{p_1, \cdots, p_{n}\}\) 的一个子集，我们归纳定义 \(P\) 的真值函数 \([P]：\mathbb{T}^{n} \to \mathbb{T}\)（\(\mathbb{T} = \{0, 1\}\)）：
- 对于简单命题 \(P = p_{i}\)，则 \([P](\sigma(p_1), \cdots, \sigma(p_{n})) =\sigma(p_{i})\)
- 定义 \([P_1], [P_2]\)，则任意选定一种连接符 \(\ast\)： $$ ⟦P_{1} \ast P_2⟧(\sigma) = H^{\ast}(⟦P_1⟧, ⟦P_2⟧)(\sigma) = ⟦P_1⟧(\sigma) \ast_{\text{bool}} ⟦P_2⟧(\sigma) $$
如果 \(\exists \sigma, [P](\sigma) = T\)，则 \(P\) 是可满足的
如果 \(\forall \sigma, [P](\sigma) = T\)，则 \(P\) 是重言式
如果 \(\forall \sigma, [P](\sigma) = F\)，则 \(P\) 是矛盾式
命题关系
已知命题 \(P,Q\)
如果 \((P \leftrightarrow Q)\) 为重言式，则 \(P,Q\) 逻辑等价，记为 \(P \Leftrightarrow Q\) 或 \(P \equiv Q\)。逻辑等价是 \((F, ¬,∧, ∨,→, \leftrightarrow)\) 上的一个同余关系：对于任意运算 \(f\)（如 \(\land, \lor, \to\) 等），如果 \(a_1 \equiv b_1, a_2 \equiv b_2\)，则： $$ f(a_1, a_2) \equiv f(b_1, b_2) $$ 如果 \((P \to Q)\) 为重言式，则称 \(P\) 逻辑蕴涵于 \(Q\)，记为 \(P \Rightarrow Q\)
\(P[Q/p]\) 表示把命题 \(P\) 中简单命题 \(p\) 的所有出现统一替换为 命题 \(Q\) 得到的命题，\(P[P_{1}/p_{1},…,P_{n}/p_{n}]\) 表示将简单命题 \(p_1,\cdots, p_{n}\)的所有出现同时分别替换为命题 \(P_{1}, \cdots, P_{n}\) 得到的命题
一些定理
- 重言式替换定理：如果 \(P\) 是重言式，则 \(P[P_{1}/p_{1},…,P_{n}/p_{n}]\) 也是重言式
- 德摩根定律：\((¬(P ∧ Q)) \equiv ((¬P) ∨ (¬Q))\)、\((¬(P ∨ Q)) \equiv ((¬P) ∧ (¬Q))\)
- 等价替换定理：假设命题 \(P_{1}\) 中包含了命题 \(P\)。将 \(P_{1}\) 中 \(P\) 的一个或多个出现用命题 \(Q\) 替换而得到 \(Q_{1}\)。如果 \(P\) 和 \(Q\) 逻辑等价，则 \(P_{1}\) 和 \(Q_{1}\) 逻辑等价
结构归纳法
分为三部分：
- 归纳基础：证明命题对每一种原子结构成立
- 归纳假设：假设命题对结构 \(P,Q\) 等成立
- 归纳证明：根据归纳假设证明命题对由 \(P,Q\) 等出发，通过使用一次构造规则（连接词连接）而得到的新的结构 \(P_{1}\) 成立
抽象布尔代数
如果把逻辑等价的公式视为同一个对象，那么我们可以说 \(((F, ⪯), ¬, ∧, ∨)\) 是一个抽象布尔代数，其中 \(F\) 表示命题集合，\(\preceq\) 表示逻辑蕴含关系
在这个布尔代数结构中：
- 极小元是矛盾式 \(\bot\)，极大元是重言式 \(\top\)
- \(P, Q\) 的上确界是 \(P \lor Q\)，下确界是 \(P \land Q\)
- \(P\) 的补元是 \(\neg P\)