离散数学 - 01 数理逻辑

本文主要是介绍离散数学 - 01 数理逻辑，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数理逻辑

简介
命题逻辑
- 命题与联结词
- 命题公式及其赋值
- 等值演算
- 析取范式与合取范式
谓词逻辑（一阶逻辑）

简介

离散数学：数理逻辑，集合论，代数系统，图论
数理逻辑： $\color{red}{命题逻辑，谓词逻辑}$
命题逻辑
（1）命题逻辑的基本概念、命题逻辑联结词与真值表，重言式
（2）简单命题的形式化（简单自然语句的形式化）
（3）等值定理、基本等值公式以及等值演算
（4）命题公式与真值表的关系、联结词的完备集
（5）析取范式、合取范式、主析取范式和主合取范式
（6）命题逻辑的推理规则与推理演算，归结推理证明方法
（7）命题逻辑公理系统的概念，公理系统的基本结构
谓词逻辑
（1）谓词、量词的基本概念及表示法
（2）复杂自然语句的形式化
（3）否定型等值式、量词分配等值式
（4）范式、前束范式，Skolem 标准形
（5）基本推理公式及其证明方法 
（6）谓词逻辑的推理规则与推理演算，归结推理法
谓词逻辑与命题逻辑区别
(1) 命题逻辑把简单命题作为最基本的单元，在命题逻辑的范畴内是找不到什么联系的。如命题：“A是字母”。
(2) 谓词逻辑继续拆分命题，把命题拆为“A”、“…是字母”、这些结构，可以得出命题 “π是实数”这种命题。其中 “…是字母” 称为谓词。谓词逻辑可以描述更丰富的推理形式。

命题逻辑

命题与联结词

$\color{red}{命题}$ ：能判断真假的陈述句
（1）简单(原子) / 复合命题，真 / 假命题
（2）特别注意：变量，悖论，非陈述句
$\color{red}{复合命题联结词}$ ：否定¬、合取∧（且）、析取∨（或）、蕴涵→、等价↔
（1）不兼容或（排斥或）：今晚小李玩游戏p或打球q：(p∧¬q)∨(¬p∧q)
（2）蕴涵：如果 p 则 q; 只要 p 则 q；p 仅当 q；除非 q 否则p；只有q我才p
（3）等价：p 当且仅当 q
（4）优先顺序：¬，∧，∨，→，↔，括号优先

命题公式及其赋值

$\color{red}{合式公式(命题公式)}$ ：将命题用联结词和圆括号按一定逻辑关系联结的符号串
（1）性质
[1] 单个命题变项（或常项）是合式公式
[2] 若 A 是合式公式，则（┐A）也是合式公式
[3] 若 A,B 是合式公式，则(A∧B),(A∨B),(A→B),(A↔B)也是合式公式
[4] 有限次应用(1)～(3)形成的符号串是合式公式
$\color{red}{可满足式命题}$
（1）设 A 为一个命题公式
[1] 若 A 在各种赋值下取值均为真，则A为重言式或永真式；
[2] 若 A 在各种赋值下取值均为假，则A为矛盾式或永假式；
[3] 若 A 不是矛盾式，则称 A 是可满足式。
$\color{red}{真值表}$
（1）含 n(n≥1)个命题变项的公式 A 共有 2ⁿ 个赋值
（2）注：蕴涵为假：当且仅当 p 为真 q 为假。

等值演算

$\color{red}{命题的等值性}$ ：若 A↔B 为重言式，则称 A 与 B 是等值的，记为 A⇔B
（1）A↔B 定义为： A→B，B→A
（2）重要等值式
[1] 双重否定律：A⇔ ¬(¬A)
[2] 等幂律： A⇔A∨A； A⇔A∧A
[3] 交换律： A∨B ⇔ B∨A； A∧B ⇔ B∧A
[4] 结合律： (A∨B)∨C ⇔ A∨(B∨C)；(A∧B)∧C ⇔ A∧(B∧C)
[5] 分配律： A∨(B∧C))⇔ (A∨B)∧(A∨C)；A∧(B∨C) ⇔ (A∧B)∨(A∧C)
[6] 德摩根律： ¬(A∨B) ⇔ (¬A)∧(¬B)；¬(A∧B) ⇔ (¬A)∨(¬B)
[7] 吸收律： A∨(A∧B) ⇔ A；A∧(A∨B) ⇔A
[8] 零律： A∨1 ⇔1；A∧0 ⇔ 0
[9] 同一律： A∨ 0 ⇔A；A∧1 ⇔ A
[10] 排中律： A∨(¬A) ⇔ 1
[11] 矛盾律： A∧(¬A) ⇔ 0
[12] 蕴涵等值式： A→B ⇔ (¬A)∨B
[13] 等价等值式： A↔B ⇔ (A→B∧B→A)
[14] 假言易位： A→B ⇔ (¬B)→(¬A)
[15] 等价否定等值式： A↔B ⇔ (¬A)↔(¬B)
[16] 归谬论： (A→B)∧(A→(¬B)) ⇔ (¬A)
（3）置换定理：如果 A⇔B，则 f（A）⇔ f（B）
[1] 功能：验证两个命题公式等值；判别命题公式的类型（重言式，矛盾式，可满足式）；

析取范式与合取范式

$\color{red}{简单合取式 / 简单析取式}$ ：
（1）组成 : 命题变元 ( p) 或命题变元否定式 (¬ p) ;
（2）概念：有限个命题变元或其否定式组成的合取式/析取式
（3）文字：命题符号(代表命题变量或命题常量)或命题符号的否定的统称
（4）示例 :
[1] 三个命题变元或其否定式构成的合取式( p ∧ ¬q ∧ r ) / 析取式(p ∨ ¬q ∨ r)

$\color{red}{命题公式的范式}$ ：析取(∨)范式和合取(∧)范式统称为范式
（1）析取范式：由有限个简单合取式构成的析取式, 形如 A1∨A2∨…∨An; (Ai为简单合取式)
（2）合取范式：由有限个简单析取式构成的合取式, 形如 A1∧A2∧…∧An; (Ai为简单析取式)
$\color{red}{范式的定理}$
（1）定理1
[1] 一个简单析取式是永真式，当且仅当它同时含一个命题符号及其否定
[2] 一个简单合取式是矛盾式，当且仅当它同时含一个命题符号及其否定。
（2）定理2：
[1] 一个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式。
[2] 一个合取范式是永真式，当且仅当它的每个简单析取式都是永真式。
（3）定理3：（范式存在定理）任意命题公式都存在与之等值的析取范式与合取范式。
$\color{red}{范式的案例}$
（1）求一个公式的范式的步骤如下：
[1] 消除联结词→和↔，使得公式中只含有联结词¬、∧和∨：利用蕴涵等值式 $\color{red}{(A→B)⇔(¬A∨B)}$ 和等价等值式 $\color{red}{(A↔B)⇔(¬A∨B)∧(A∨¬B)}$ 。
[2] 利用双重否定律¬¬A⇔A消去双重否定词，德摩根律內移否定词。
[3] 利用分配律，求析取范式利用∧对∨的分配律，求合取范式则利用∨对∧的分配律。
（2）求(¬p→q)∧(p→r)的析取范式和合取范式
[1] 析取范式: (¬p→q)∧(p→r)⇔(¬¬p∨q)∧(¬p∨r) ⇔(p∨q)∧(¬p∨r)⇔(p∧¬p)∨(p∧r)∨(q∧¬p)∨(q∧r)⇔(p∧r)∨(q∧¬p)∨(q∧r)
[2] 合取范式:(¬p→q)∧(p→r)⇔(p∨q)∧(¬p∨r)

$\color{red}{极小项}$ : 是一种简单合取式，成真赋值
（1）概念：满足以下三点为极小项，第 i 个极小项 , 称为 m _i 。
[1] 含有 n 个文字的简单合取式
[2] 若每个命题符号和其否定不同时存在，而二者之一必须出现且只出现一次
[3] 第 i 个命题变元或者否定出现在左起第 i 个位置（若命题变元无下标，则按字典顺序排列)
（2）极小项个数：n 个命题变元会产生 2ⁿ 个极小项
（3）互不等值： 2ⁿ 个极小项均互不等值
（4）极小项表格

$\color{red}{极大项}$ : 是一种简单析取式，成假赋值
（1）概念：满足以下三点为极大项，第 i 个极大项 , 称为 M _i 。
[1] 含有 n 个文字的简单析取式
[2] 若每个命题符号和其否定不同时存在，而二者之一必须出现且只出现一次
[3] 第 i 个命题变元或者否定出现在左起第 i 个位置（若命题变元无下标，则按字典顺序排列)
（2）极大项个数：n 个命题变元会产生 2ⁿ 个极小项
（3）互不等值： 2ⁿ 个极大项均互不等值
（4）极大项表格

（5）极大项M _i和极小项 m _i 之间的关系 :
[1] ¬ m _i ⟺ M _i
[2] ¬ M _i ⟺ m _i

13. $\color{red}{主析取范式}$ : 所有简单合取式都是极小项的析取范式
(1) 定理：任何命题公式都存在唯一的与之等值的主析取范式
(2) 求命题公式 A 的主析取范式步骤
[1] 求A的一个析取范式
[2] 如该析取式的某个简单合取式 B 既不含某个命题变元 $p$ , 也不含 $\neg p$ ，则该简单合取式变为：（B ∧ $p$ ）∨ （B ∧ $\neg p$ ）
[3] 消除重复命题变元或否定，矛盾式及重复出现的极小项，并将每个极小项的命题变元或其否定按下标顺序或字典顺序排列。
(3) 案例：(¬p→q)∧(p→r)
[1] 通过10得 (¬p→q)∧(p→r)的一个析取范式是(p∧r)∨(q∧¬p)∨(q∧r)
[2] 将其中的每个简单合取式展开为含有所有命题变元的极小项的析取:
(p∧r)：(p∧q∧r)∨(p∧¬q∧r)，(q∧¬p)：(¬p∧q∧r)∨(¬p∧q∧¬r)，(q∧r)：(p∧q∧r)∨(¬p∧q∧r)
[3] 消除重复：(p∧q∧r)∨(p∧¬q∧r)∨(¬p∧q∧r)∨(¬p∧q∧¬r)
[4] 按极小项所对应的二进制数的大小重新排列：(¬p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧r)

14. $\color{red}{主合取范式}$ : 所有简单析取式都是极大项的合取范式
(1) 定理：任何命题公式都存在唯一的与之等值的主合取范式
(2) 求命题公式 A 的主析取范式步骤
[1] 求A的合取范式 A ’
[2] 如A ’ 的某个简单析取式 B 既不含某个命题变元 $p$ , 也不含 $\neg p$ ，则该简单合取式变为：B⇔B∨0⇔B∨(p∧┐p)⇔(B∨p)∧(B∨p)
[3] 消除重复命题变元或否定，矛盾式及重复出现的极小项，并将每个极小项的命题变元或其否定按下标顺序或字典顺序排列。
(3) 案例：(p→¬q)→r
[1] 求合取范式：(p∨r)∧(q∨r)
[2] 将(p∨r)转为主合取范式:
(p∨r) ⟺ (p∨0∨r) ⟺ (p∨(q∧¬q)∨r) ⟺ ((p∨r)∨(q∧¬q)) ⟺ (p∨r∨q)∧(p∨r∨¬q) ⟺ (p∨q∨r)∧(p∨¬q∨r)
[3] 根据极大项公式写出对应序号: (p∨q∨r):成假赋值000, 极大项M₀; (p∨¬q∨r):成假赋值010,是极大项 M₂ ;
[4] (p∨r)对应的主合取范式是:(p∨q∨r)∧(p∨¬q∨r) ⟺ M₀ ∧ M₂
[5] 将(q∨r)转为主合取范式: ( p∨q∨r)∧(¬p∨q∨r) ⟺ M₀ ∧ M₄
[6] (p∨r)∧(q∨r) ⟺ M₀ ∧ M₂ ∧ M₄

$\color{red}{真值表求主析取范式和主合取范式}$
（1）条件 : A = ( p → ¬ q ) → r

$\color{red}{命题逻辑的推理理论}$
(1) 推理: 指从前提推出结论的思维过程
[1] 前提：已知的命题公式
[2] 结论：从前提出发应用推理规则推出的命题公式
（2）前提和结论取值情况有以下4种：
[1] A₁ ∧ … ∧ A_k 为 0，B 为 0；
[2] A₁ ∧ … ∧ A_k 为 0，B 为 1；
[3] A₁ ∧ … ∧ A_k 为 1，B 为 0；
[4] A₁ ∧ … ∧ A_k 为 1，B 为 1；
只要不出现 [3], 推理就是正确的。
（3）A ⇒ B 表示 “A → B”是重言式。B为逻辑结论/有效结论。
（4）案例：
[1] {p, p → q}
[2] {p, q → p}
[3] 推理[1] 没有出现现象【3】，推理正确
[4] 推理[2] 出现现象【3】，推理错误

$\color{red}{重要的推理定律}$
(1) 定律
[1] 附加律：A⇒(A∨B)
[2] 化简律：(A∧B)⇒A,(A∧B)⇒B
[3] 假言推理：(A→B)∧A⇒B
[4] 拒取式：(A→B)∧¬B⇒¬A
[5] 析取三段论：(A∨B)∧¬B⇒A
[6] 假言三段论：(A→B)∧(B→C)⇒(A→C)
[7] 等价三段论：(A↔B)∧(B↔C)⇒(A↔C)
[8] 构造性二难：(A→B)∧(C→D)∧(A∨C)⇒(B∨D)
(2) 案例：((p∨q)∧¬p)→q
[1] 等值演算法来判断上式是否为重言式((p∨q)∧¬p)→q⇔((p∧¬p)∨(q∧¬p))→q⇔(q∧¬p)→q
⇔¬(q∧¬p)∨q⇔¬q∨p∨q⇔1
[2] 上式为重言式，所以推理正确
$\color{red}{推理规则}$
（1）A₁ ， … ， A_k |- B，表示B是A₁ , … ， A_k的逻辑结论。
（2）在证明的序列中，若有A₁ , … ， A_k，则可以引入B。

谓词逻辑（一阶逻辑）

$\color{red}{简单命题}$ ：可以分解为个体词和谓词两部分。
（1）个体词：可以独立存在的个体，可以是具体的事物，可表示抽象的概念
（2）谓词：刻画个体词的性质及个体词之间的关系
（3）谓词元数：谓词联系的个体数目
（4）个体常项：表示具体或特定的个体的个体词，一般小写字母 a，b，… 表示
（5）个体变项：表示抽象或泛指的个体词，一般x，y，… 表示
（6）个体域（论域）：个体变项的取值范围，可以又穷集合，也可无穷集合，常用 D 表示
（7）全总个体域：一切事物组成的个体域
（8）函数/函项：谓词逻辑可引入将个体映射为个体的函数/函项，如 F(x): x 是奇数
$\color{red}{量词}$ ：命题中表示数量的词，全称量词，存在量词
（1）全称量词: “一切”、“所有”、“任意”等，用“∀”表示，∀xF(x)表示个体域里所有个体都有性质 F。
[1] ∀xP(x)为真，当且仅当对论域中的所有个体 x 都有 P(x) 为真
[2] 翻译为 →
（2）存在量词: “存在”、“有一个”、“至少有一个”等，用“∃”表示，∃xF(x)表示存在个体域里的个体具有性质 F。
[1] ∃xP(x)为真，当且仅当论域中至少存在一个个体 x₀使 F(x₀)为真
[2] 翻译为 ∧

$\color{red}{一阶逻辑等值式}$
（1）设 A、B为一阶逻辑公式，若 A↔B 是永真式，则称 A 与 B 是等值的，记作 A⇔B ，称 A⇔B为等值式. 例如：∃xF(x)⇔∃xF(x)∧∃xF(x)，∀xF(x)∧¬∀xF(x)⇔0，∃xF(x)∨¬∃xF(x) ⇔1；
（2）等值演算方法1：消去量词等值式
[1] ∀x A(x)⇔ A(a₁) ∧ A(a₂) ∧…∧ A(a_n)
[2] ∃x A(x)⇔ A(a₁) ∨ A(a₂) ∨…∨ A(a_n)
（3）等值演算方法2：量词否定等值式
[1] ¬∀ x A(x)⇔∃x ¬A(x)
[2] ¬∃x A(x)⇔ ∀x ¬A(x)
（4）等值演算方法3：量词分配等值式
[1] ∀x (A(x)∧B(x))⇔∀ xA(x)∧∀x B(x)
[2] ∃x (A(x)∨B(x))⇔∃ xA(x)∨∃x B(x)
(5) 案例
[1] ¬∀x (F(x)→G(x))⇔¬∀x (¬F( x )∨G(x))
⇔∃x ¬(¬F(x)∨G(x)) ⇔∃x(F(x)∧¬G(x))
[2] ¬∀x∀y (F(x)∧G(y)→H(x,y)) ⇔ ∃x∃y ¬(F(x)∧G(y)→H(x,y))⇔∃x∃y ¬(¬(F(x)∧G(y))∨H(x,y))⇔∃x∃y (F(x)∧G(y)∧¬H(x,y))

$\color{red}{前束范式}$
（1）设 A 为一阶逻辑公式，若 A 具有如下形式 Q₁ x₁ … Q_nx_n B，则称 A 为前束范式。
[1] 其中 Q i 是 ∀ / ∃，i =1, …, n, B 是不含量词的公式, 例∀x∀y∃z (P(x,y)→H(x,z)) 和 ∃x∃y∃zP(x,y,z)
（2）定理：对任意一阶逻辑公式都存在与其等值的前束范式（但形式不唯一）
（3）案例
[1] ∀xF(x)∧¬∃xG(x)⇔∀xF(x)∧∀x¬G(x)量词否定等值式
⇔∀x(F(x) ∧¬G(x)) 量词分配等值式
[2] ∀xF(x) ∨¬∃xG(x)⇔∀xF(x)∨∀x¬G(x) 量词否定等值式
⇔∀yF(y)∨∀x¬G(x) 约束变项换名规则
⇔∀y∀x (F(y) ∨¬G(x)) 量词收缩扩张等值式
⇔∀y∀x (G(x)→F(y))
. $\color{red}{一阶逻辑的推理}$
(1) 推理苏格拉底三段论
解：取全总个体域，设 F(x):x是人, G(x):x是要死的, a:苏格拉底.
前提: ∀x (F(x)→G(x)), F(a);
结论: G(a)
证明: 引入前提∀x (F(x)→G(x)), 消去全程量词 F(a)→G(a),
引入前提 F(a), 得出结论: G(a), 即表示为: ( ∀x (F(x)→G(x)) )∧F(a) → G(a)