离散数学·数理逻辑深度学习笔记

离散数学·数理逻辑深度学习笔记涵盖章节第15章 命题逻辑基本概念 | 第16章 等值演算 | 第17章 推理理论 | 第18章 一阶逻辑基本 | 第19章 一阶逻辑推理 第15章 命题逻辑基本概念一、命题与联结词核心基础1. 命题的判定标准能判断真假且非真即假的陈述句才是命题。判断标准例子✅ 命题“2是素数”、“√5是无理数”❌ 不是命题“你去图书馆吗”疑问句、“这朵花多美呀”感叹句、“2x35”含变量变量取值不定2. 五种基本联结词★必须牢记记 S {┐, ∧, ∨, →, ↔} 称为常用联结词集联结词符号自然语言何时为真何时为假否定┐“非”p为假时p为真时合取∧“与”、“虽然…但是…”p和q同时为真至少一个为假析取相容或∨“或”至少一个为真p和q同时为假蕴涵→“若…则…”除前真后假外均为真前真后假时才为假等价↔“当且仅当”p和q真值相同p和q真值不同3. 蕴涵式 p→q 的深层理解★易错点记忆技巧前件是充分条件后件是必要条件“若 p则 q” → p→q前真后假才为假“只有 p才 q” → q→p后件是充分条件“除非 p否则 q” → ┐p→q蕴涵式的9种日常说法全部符号化为 p→q若 p则 q只要 p就 qp 仅当 q假如 p那么 q一旦 p就 q假使 p则 q要是 pq在 p 的条件下有 qp 蕴含 q排除法记忆蕴涵式只有一种情况为假 →前件真 AND 后件假二、命题公式及其层次★理解层次计算1. 合式公式WFF的递归定义(1) 单个命题变项/常项是合式公式原子公式 (2) 若 A 是合式公式则 (┐A) 是合式公式 (3) 若 A,B 是合式公式则 (A∧B),(A∨B),(A→B),(A↔B) 是合式公式 (4) 有限次使用(1)(2)(3)生成的符号串2. 公式层次计算规则情况层数单个命题变项0层A ┐Bn1层B是n层A B∧C 或 B∨C 或 B→C 或 B↔Cn max(i, j)B是i层C是j层3. 赋值与真值表赋值 给每个命题变项指定真值0或1 成真赋值使公式取值为1的赋值 成假赋值使公式取值为0的赋值4. 公式的三种类型★必考类型别名定义真值表最后一列重言式永真式所有赋值下均为真全1矛盾式永假式所有赋值下均为假全0可满足式—至少有一个成真赋值有1有0重要性质可满足式 ≠ 重言式只要不是全0就是可满足式矛盾式的否定是重言式三、命题符号化方法总结★题型一解题步骤识别句子中的简单命题并符号化识别句子中的联结词类型组合成复合命题符号化典型联结词对应关系自然语言符号“但是”、“而且”、“并且”、“既…又…”、“虽然…但…”∧“或者…或者…”可同时为真∨“要么…要么…”不能同时为真如选学英语或法语(p∧┐q)∨(┐p∧q)排斥或 第16章 命题逻辑等值演算一、基本等值式24个必须熟练双重否定与幂等① A ⟺ ┐┐A 双重否定律 ② A ∨ A ⟺ A 幂等律 ③ A ∧ A ⟺ A交换、结合、分配④ A ∨ B ⟺ B ∨ A 交换律 ⑤ A ∧ B ⟺ B ∧ A ⑥ (A ∨ B) ∨ C ⟺ A ∨ (B ∨ C) 结合律 ⑦ (A ∧ B) ∧ C ⟺ A ∧ (B ∧ C) ⑧ A ∨ (B ∧ C) ⟺ (A ∨ B) ∧ (A ∨ C) 析取对合取分配 ⑨ A ∧ (B ∨ C) ⟺ (A ∧ B) ∨ (A ∧ C) 合取对析取分配德摩根律★考频最高⑩ ┐(A ∨ B) ⟺ ┐A ∧ ┐B ⑪ ┐(A ∧ B) ⟺ ┐A ∨ ┐B吸收、零律、同一⑫ A ∨ (A ∧ B) ⟺ A 吸收律 ⑬ A ∧ (A ∨ B) ⟺ A ⑭ A ∨ 1 ⟺ 1 零律 ⑮ A ∧ 0 ⟺ 0 ⑯ A ∨ 0 ⟺ A 同一律 ⑰ A ∧ 1 ⟺ A排中与矛盾⑱ A ∨ ┐A ⟺ 1 排中律非此即彼必有一真 ⑲ A ∧ ┐A ⟺ 0 矛盾律不能同时为真蕴涵与等价变换★重要变换公式⑳ A → B ⟺ ┐A ∨ B 蕴涵等值式→转∨ ㉑ A ↔ B ⟺ (A→B) ∧ (B→A) ㉒ A → B ⟺ ┐B → ┐A 假言易位 ㉓ A ↔ B ⟺ (A∧B) ∨ (┐A∧┐B) ㉔ (A→B) ∧ (A→┐B) ⟺ ┐A 归谬论二、范式理论★重难点1. 核心概念简单合取式有限个文字的合取如 p ∧ ┐q ∧ r 简单析取式有限个文字的析取如 p ∨ ┐q ∨ r 析取范式简单合取式的析取 合取范式简单析取式的合取2. 极小项与极大项极小项合取式用于主析取范式n个变元产生2 n 2^n2n个极小项每个极小项的成真赋值唯一例m₀₀ ┐p∧┐q成真赋值00m₀₁ ┐p∧q成真赋值01极大项析取式用于主合取范式n个变元产生2 n 2^n2n个极大项每个极大项的成假赋值唯一例M₀₀ p∨q成假赋值00M₀₁ p∨┐q成假赋值013. 主析取范式求法★方法一等值演算法步骤消去→和↔用蕴涵/等价等值式否定号内移德摩根律或双重否定消去分配律化成析取范式不是极小项的简单合取式用排中律等化成极小项主析取范式的三大用途✅ 求成真赋值✅ 判断公式类型看包含多少极小项✅ 判断两公式是否等值主析取范式唯一主析取范式与公式类型的关系含n个命题变项类型主析取范式主合取范式重言式含全部2 n 2^n2n个极小项1不含极大项矛盾式0含全部2 n 2^n2n个极大项可满足式非重言含s个极小项1≤s2^n含2 n − s 2^n-s2n−s个极大项三、联结词完备集核心定理所有真值函数都可以由以下完备集表示{┐, ∧, ∨}、{┐, →}、{↑}与非、{↓}或非关键变换p → q ⟺ ┐p ∨ q 用{┐, ∨}表示 p ∧ q ⟺ ┐(p ↑ q) 用{↑}表示 p ∧ q ⟺ ┐(p ↓ q) 用{↓}表示 第17章 命题逻辑的推理理论一、推理的基本概念推理从前提推出结论的思维过程有效推理若前提全部为真则结论必然为真形式前提₁, 前提₂, …, 前提ₙ ⊨ 结论记作 Γ ⊨ B二、自然推理系统 P★核心常用推理规则规则名称说明前提引入—结论引入—置换规则A⟺B可相互替换肯定前提CP规则若Γ, A ⊨ B则Γ ⊨ A→B否定结论反证法若Γ, ┐B ⊨ C∧┐C则Γ ⊨ B重要推理规则内置规则内容假言三段论HS(A→B)∧(B→C) ⊨ A→C析取三段论DS(A∨B)∧┐B ⊨ A假言推理MP(A→B)∧A ⊨ B拒取式MT(A→B)∧┐B ⊨ ┐A合取引入∧IA, B ⊨ A∧B合取消去∧EA∧B ⊨ A或B析取消去∨E(A∨B)∧(A→C)∧(B→C) ⊨ C三、消解法归结原理消解规则C₁ C ∨ L, C₂ C ∨ ┐L → Res(C₁, C₂) C ∨ C 消去互补文字 L 和 ┐L消解法判断可满足性步骤操作1输入公式 A2求 A 的合取范式 S3反复对 S 中简单析取式做消解4若消出空子句 □ → 不可满足矛盾式5若无法消出 □ → 可满足 第18-19章 一阶逻辑一、一阶逻辑基本概念个体词研究对象个体常量a, b, c…具体对象个体变量x, y, z…变化对象谓词描述个体性质或关系命题常量人都会死。 一阶谓词苏格拉底是人。→ M(苏格拉底) 所有人都是会死的。→ ∀x(M(x)→D(x)) 存在一个数大于0。→ ∃x(G(x,0))二、一阶公式的结构原子公式谓词(个体₁,...,个体ₙ) ├─ 否定┐A ├─ 量词∀x A 或 ∃x A └─ 复合联结词连接原子公式自由变量 vs 约束变量量词后面的x被该量词约束不被任何量词约束的变量是自由变量无自由变量的公式是闭公式命题形式三、等值演算与推理基本等值式量词相关㊀ ┐∀x A ⟺ ∃x ┐A 量词否定 ㊁ ┐∃x A ⟺ ∀x ┐A ㊂ ∀x A ∨ B ⟺ ∀x(A ∨ B) x不是B的自由变元时 ㊃ ∃x A ∨ B ⟺ ∃x(A ∨ B) x不是B的自由变元时 ㊄ ∀x(A ∧ B) ⟺ ∀x A ∧ ∀x B ㊅ ∃x(A ∧ B) ⟺ ∃x A ∧ ∃x B 注意∧无分配律 ㊆ ∀x A → B ⟺ ∃x(A → B) x不是B的自由变元时 ㊇ ∃x A → B ⟺ ∀x(A → B) x不是B的自由变元时自然推理系统 Nc 量词规则规则符号说明全称量词消去∀⁻从 ∀x A(x) 可推出 A©c为任意个体全称量词引入∀⁺从 A© 可推出 ∀x A(x)c不在前提中自由出现存在量词消去∃⁻从 ∃x A(x) 可推出 A©c为新常量存在量词引入∃⁺从 A© 可推出 ∃x A(x)c为任意个体 典型例题精讲例题1蕴涵式符号化“只有天下大雨他才乘班车上班”分析p天下大雨q他乘班车上班“只有p才q” → q的前件是p →q→p答案q → p例题2判断公式类型判断公式 (p→q) ∧ (┐p ∨ r) ∧ q 的类型方法写真值表或用等值演算pqrp→q┐p∨r(p→q)∧(┐p∨r)∧q000110001110010111011111100000101010110100111111→ 成真赋值为001, 011, 111不全为1有0有1→可满足式非重言式例题3推理有效性判断若天下雨则地湿。地湿了。所以天下雨了。符号化前提A→B, BA天下雨B地湿结论A判断这是肯定后件谬误推理无效A → B B ────── A ✗ 错误正确推理假言推理 MPA → B A ────── B ✓ 正确例题4等值演算化简用等值演算法证明 p→(p∨┐q∨r) 为重言式解答p → (p ∨ ┐q ∨ r) ⟺ ┐p ∨ (p ∨ ┐q ∨ r) 蕴涵等值式 ⟺ (┐p ∨ p) ∨ (┐q ∨ r) 结合律 ⟺ 1 ∨ (┐q ∨ r) 排中律 ⟺ 1 零律→ 结果为1故为重言式✅例题5求主析取范式求公式 (p→q)→r 的主析取范式解答(p→q)→r ⟺ ┐(┐p ∨ q) ∨ r 蕴涵等值式 ⟺ (p ∧ ┐q) ∨ r 德摩根律 ⟺ (p ∧ ┐q ∧ r) ∨ (p ∧ ┐q ∧ ┐r) ∨ (┐p ∧ r) ∨ (q ∧ r) 分配律r (p∧┐q)∧r ∨ (┐p∧q∧r) ∨ (p∧┐q∧┐r)…… 化简后 ⟺ m₁₀₁ ∨ m₁₀₀ ∨ m₀₁₁ ∨ m₁₁₁成真赋值为101, 100, 011, 111 学习建议层次内容建议基础5种联结词、命题符号化、真值表多做自然语言→符号语言练习进阶等值式、范式、推理规则背熟24个基本等值式做等值演算题综合综合推理题、消解法做习题册应用题理解消解原理 附录常用公式速查表蕴涵式的5种等价变形p → q ⟺ ┐p ∨ q 最基本 p → q ⟺ ┐q → ┐p 假言易位 p → q ⟺ ┐(p ∧ ┐q) 德摩根 p → q ⟺ ┐p → (q ∨ r) 加项常见谬误谬误名称形式错误原因肯定后件(A→B)∧B → AB为真时A不一定为真否定前件(A→B)∧┐A → ┐B┐A为真时B不一定为假肯定析取项(A∨B)∧A → ┐BA∨B为真时A、B均可为真本笔记基于《离散数学学习指导与习题解析第3版》第15-19章内容整理