第四课：排中律、逻辑联结词、命题公式、重言式¶
Page 2-4 — 命题的定义¶
- 命题：对确定的对象作出判断的陈述句
- 真值：真（true）或假（false）
- 三个识别要点： 1. 陈述句 2. 判断 3. 确定的对象
- 练习判断：
- ✅ 浙江大学建校的那天，杭州在下雨（命题，虽不知真值）
- ✅ 大于2的偶数均可以分解为两个素数之和（哥德巴赫猜想，命题）
- ❌ 请双击666！（祈使句）
- ❌ 谁动了我的奶酪？（疑问句）
- ✅ 2是偶数，而且3也是偶数（命题）
💡 人话：命题就是能判断对错的陈述句。"北京是首都"是命题，"你好吗"不是陈述句不是命题，"x>5"没有确定对象也不是命题。能不能知道真值不重要，关键是"有没有真值"。
Page 5 — 识别命题¶
- 真值是命题的固有属性（是否知道是另一回事）
- 悖论（自相矛盾）不能作为命题——"这句话是错的"
- 命题非真即假，不能兼有，也不能不真不假
- 非真即假，是一个基本假设？（排中律）
Page 6 — 排中律¶
- 排中律（Law of Excluded Middle）：是非之间，必居其一
- 墨子《经说下》："辩也者，或谓之是，或谓之非，当者胜也"
- 任一事物在同一时间里具有某属性或者不具有某种属性，而无其他可能
💡 人话：一个命题要么真要么假，没有中间状态。这是逻辑的基本假设。
Page 7-9 — 反证法与排中律¶
- 利用排中律：假设命题不为真→推出矛盾→此命题非假即真
- 经典例子1：素数有无穷多个
- 假设素数有限，构造N=P₁...Pₙ+1
- N要么有新的素因子，要么本身是素数
- 推出矛盾，故命题成立
- 经典例子2：√2是无理数
- 假设√2是有理数a/b（a,b互质）
- 2b²=a²→a是偶数→b是偶数→与a,b互质矛盾
Page 10 — 直觉主义对排中律的质疑¶
- 从有限事物中概括的排中律，不能贸然推广到无穷事物
- 涉及有穷事物全体的命题可逐个检验
- 涉及无穷事物一般无法检验
- "昨天太阳从东边升起→明天太阳还从东边升起"（归纳法不保证）
Page 11-13 — 原子命题和复合命题¶
- 原子命题（atom proposition）：不含逻辑联结词的命题
- 复合命题（compound proposition）：包含原子命题和逻辑联结词的命题
- 逻辑联结词（logical connectives）：连接命题，对真值进行运算
- 形式化三步： 1. 抽象：仅关注真值，抛弃内涵 2. 符号化：命题变元p,q，联结词符号 3. 建立规则：按规则组合成公式
💡 人话：最小的命题叫原子命题，用"且、或、非、如果...那么..."等联结词连起来就是复合命题。联结词本质就是怎么根据子命题的真假算母命题的真假。
Page 14-24 — 逻辑联结词的定义¶
| 联结词 | 名称 | 记号 | p=1,q=1 | p=1,q=0 | p=0,q=1 | p=0,q=0 |
|---|---|---|---|---|---|---|
| ¬ | 否定 | ¬p | 0 | — | 1 | — |
| ∧ | 合取 | p∧q | 1 | 0 | 0 | 0 |
| ∨ | 析取 | p∨q | 1 | 1 | 1 | 0 |
| → | 蕴涵 | p→q | 1 | 0 | 1 | 1 |
| ↔ | 等价 | p↔q | 1 | 0 | 0 | 1 |
💡 人话： - ¬就是取反，真的变假假的变真 - ∧只要有一个假就是假 - ∨只要有一个真就是真 - →关键：假的前提可以推出任何结论（p假时p→q恒真） - ↔两边相同为真，不同为假
Page 24 — 蕴涵的深入理解¶
- p→q为假仅当p真且q假
- 日常语言中"如果...那么..."还考虑因果关系，逻辑中只考虑真值关系
- 规定"假可以推出任意结论"是为了数学推理的方便（如反证法）
Page 26-30 — 命题公式的归纳定义¶
- 命题变元是命题公式（原子公式）
- 若A,B是命题公式，则(¬A)、(A∧B)、(A∨B)、(A→B)、(A↔B)也是命题公式
- 只有有限次使用上述两条组成的符号串是命题公式 - 公式常用大写A,B,C表示
Page 31 — 命题公式的例子¶
- ✅ 例：(¬(p→(q∧r))) 是命题公式
- ❌ (qp) 不是
- ❌ (p₁∧(p₂∧...) 不是（有限性）
- ❌ p→r∧s 不是（缺少括号）
- 约定：最外层括号可省略，按优先级减少括号
Page 32 — 逻辑联结词的优先级¶
最高：¬ → 第二：∧, ∨ → 第三：→ → 最低：↔
除非有括号，否则按优先级从高到低、从左到右结合： - ¬p∨q 等同于 (¬p)∨q - p→q∧r→s 是 (p→((q∧r)→s))，不是 (p→q)∧(r→s)
Page 33-36 — 真值函数与赋值¶
- 命题公式本质是真值函数：从变元的赋值映射到{0,1}
- n个变元 → 2ⁿ种赋值
- 赋值（指派/assignment）：变元的一种取值状况组合
- 真值表：列出所有赋值下公式的真值，2ⁿ行，k+n列
💡 人话：把公式看成黑盒，输入变元的真假，输出公式的真假。有多少种输入？n个变元就有2ⁿ种组合。
Page 36 — 成真赋值和成假赋值¶
- 成真赋值：使公式为真的赋值（α(A)=1）
- 成假赋值：使公式为假的赋值（α(A)=0）
Page 37-38 — 自然语言句子的形式化¶
步骤：确定原子命题→确定联结词→处理联结关系及顺序
例子： - "我和他既是兄弟又是同学" → p∧q - "狗急跳墙" → p→q - "如果他不来那么是生病了或者不在本地" → ¬p→(q∨¬r) - "无论是否下雨，我都去上学" → (p→q)∧(¬p→q) ≡ q
注意： - 善于确定原子命题（"兄弟"无需再拆分） - 否定词位置要准确 - 有时形式化结果不唯一，但逻辑等价
Page 39-40 — 命题公式的分类¶
| 类型 | 定义 | 例子 |
|---|---|---|
| 重言式（永真式）tautology | 所有赋值都为真 | A∨¬A |
| 矛盾式（永假式）contradiction | 所有赋值都为假 | A∧¬A |
| 可满足式 contingency | 至少有一个成真赋值 | 其他所有公式 |
- 永真式都是可满足式
- 矛盾式都不是可满足式
- 非永真式并不都是永假式
- 若A是永真式，则¬A是永假式，反之亦然
Page 41 — 重言式的例子和证明¶
- 排中律：A∨¬A
- 矛盾律：A∧¬A
- 真值表法证明重言式：(p∨q)∧¬p→q
| p | q | p∨q | ¬p | (p∨q)∧¬p | (p∨q)∧¬p→q |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 |
最后一列全为1 → 这是重言式 ✅