命题逻辑

逻辑联结词

析取与合取

析取符号: ∨
合取符号: ∧

  • 想象合取就是两个条件都要满足,析取符号就像漏斗一样析取东西,因此朝上

蕴含与等价

p->q =¬p∨q

  • 不要读作如果p,那么q,而是读作p蕴含q,表示p是q的充分条件,q是p的必要条件
  • 我的理解:当p为真自然可以推出q为真,故p真q假真值为F,当p为假时无法得知q的情况,故只能默认为T

真值表
来自知乎大佬

p ↔ q=(¬p∨q)∧(¬q∨p)

  • 由于p,q互为充要条件,故p与q真值相同时等价式为真

命题

设A为一个命题公式

  • 若A在所有赋值下都为真,则为重言式
  • 若A在所有赋值下都为假,则为矛盾式
  • 若至少有一组成真赋值,则为可满足式

不能被分解,真值确定的简单陈述句称为简单命题(原子命题,命题常项)

  • (真值未知但确定也是命题)
  • 真值可以变化的简单陈述句称为命题变项(不是命题!!!)
    使用联结词联结简单命题形成的命题称为复合命题

逻辑等值式汇总

双重否定律

  • ¬¬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

对称差等值式

  • A ⊕ B ⇔ (A ∨ B) ∧ ¬(A ∧ B)
  • A ⊕ B ⇔ (A ∧ ¬B) ∨ (¬A ∧ B)

联结词完备集

定义

设 S 是一个联结词集合。若任意真值函数都可以由仅含 S 中联结词构成的命题公式来表示，则称 S 为联结词完备集

  • 这里的真值函数可以看作是命题对应的函数,不同形式但等价的命题有相同的真值函数

与非和或非

  • 与非:p ↑ q = ¬(p ∧ q)

  • 或非:p ↓ q = ¬(p ∨ q)

可以把箭头想象成水流,自然要从开口进入,这样就好记忆了

联结词完备集整理

编号 联结词集合 是否完备 证明思路 / 说明
S1 {¬, ∧, ∨, →, ↔} 完备 包含 ¬（非）、∧（与）、∨（或）三种基本联结词，可表示所有 n 元真值函数（经典教材定理）。→ 和 ↔ 可由 ¬、∧、∨ 表示。
S2 {¬, ∧, ∨, →} 完备 包含 ¬、∧、∨，能表示任意 n 元真值函数；→ 可由 ¬、∨ 表示（p → q ≡ ¬p ∨ q）。
S3 {¬, ∧, ∨} 完备 经典完备集，¬、∧、∨ 可表示任意 n 元真值函数。
S4 {¬, ∧} 完备 通过与非公式可表示 ∨：p ∨ q ≡ ¬(¬p ∧ ¬q)。因此可表示 ¬、∧、∨ → 完备。
S5 {¬, ∨} 完备 通过或非公式可表示 ∧：p ∧ q ≡ ¬(¬p ∨ ¬q)。因此可表示 ¬、∧、∨ → 完备。
S6 {¬, →} 完备 通过 ¬ 与 → 可以表示 ∧ 和 ∨：

观察可以知道,只要有¬和基础联结词中三个中的一个就是完备集

同时↑和↓可以单独作为完备集

与非（↑）单独作为完备集

  • ¬p ≡ p ↑ p
  • p ∧ q ≡ (p ↑ q) ↑ (p ↑ q)

证明提示

  • ¬¬(p ∧ q)=¬(p↑q)

或非（↓）单独作为完备集

  • ¬p ≡ p ↓ p
  • p ∨ q ≡ (p ↓ q) ↓ (p ↓ q)

范式

合取范式和析取范式

析取范式:由有限个简单合取式构成的析取式
合取范式:由有限个简单析取式构成的合取式

极小项:简单合取式中每个命题变项及其否定有且只有一个出现过一次
极大项:简单析取式中每个命题变项及其否定有且只有一个出现过一次

为什么说是极小项,因为所有命题的交集覆盖范围是最小的,效力最弱;而极大则是因为所有命题的并集覆盖范围是最大的,效力最强

  • 若命题A的析取范式中所有合取式都是极小项,则称为A的主析取范式
  • 若命题A的合取范式中所有析取式都是极大项,则称为A的主合取范式

这时可以对每个极小项进行编码成m(001),每个极大项为M(001)这样的形式,用角标来表示主析取范式和主合取范式

计算方法

求A的主析取范式的方法

若合取式B中不含命题变项p及其否定,则将B展开为合取形式B ∧ (p ∨ ¬p),消去重复出现的命题和极小项,将极小项按照角标由小到大的形式排列

  • 至于为什么用合取形式而不是用析取形式B ∨(p ∧ ¬p),是因为要保证每个字式仍然是简单合取式

求出主析取范式后就可以求主合取范式了,主析取范式中没出现的极小项的角标作为极大项的角标,这些极大项构成的合取式为A的主合取范式.

  • 当然反过来也是可以的

一阶逻辑

个体与谓词

  • 个体常项:表示具体或特定个体的词,用a,b,c…表示
  • 个体变项:表示抽象或泛指个体的词,用x,y,z…表示
  • 个体变项的取值范围称为个体域
    当无特殊声明时,个体域可以表示所有事物,称为全总个体域
  • 谓词常项与谓词变项和上述概念对应,用F,G,H…表示
    谓词中包含的个体数称为元数,n元谓词含有n个个体词,0元谓词就是简单命题

合式公式

合式公式:也叫谓词公式,简称公式,看做是命题A加上量词或者个体变项后的形态例如"∀x(A∧B)"就行了

在"∀xA","∃xA"中的x称为指导变项,A为相应量词的辖域,在辖域x的所有出现称为约束出现,不受辖域约束的出现称为自由出现

  • 若公式A中无自由出现的个体变项,则称A为封闭的合式公式,简称闭式

换名规则: 将一个指导变项及其在辖域中所有的约束出现替换成没出现过的个体变项符号

  • 换句话说换名就是让公式中不存在既是自由出现又是约束出现的个体变项

解释: 对公式A中出现的每个个体常项和谓词变项进行赋值,由以下四部分构成

  1. 非空个体域D
  2. 给个体常项指定一个D中的元素
  3. 给函数变项指定一个D上的函数
  4. 给谓词变项指定一个D上的谓词

这个时候∀可以看作是∧,∃就看作是∨,这个通过下面的例题就很好理解了

例子
alt text

  • (1)中直接把x=2和x=3的情况用∧连接了

等值式和前束范式

等值式:若A ↔ B为永真式,则称A与B是等值的,记作A⇔B
前束范式:A=QB,其中Q为∀x或者∃x这样的形式,B为不含量词的谓词公式

一、量词否定等值式

  • ¬∀xA(x) ⇔ ∃x¬A(x)
  • ¬∃xA(x) ⇔ ∀x¬A(x)

二、量词辖域收缩与扩张等值式（B 中不含 x）

  • ∀x(A(x) ∨ B) ⇔ ∀xA(x) ∨ B

  • ∀x(A(x) ∧ B) ⇔ ∀xA(x) ∧ B

  • ∀x(A(x) → B) ⇔ ∃xA(x) → B

  • ∀x(B → A(x)) ⇔ B → ∀xA(x)

  • ∃x(A(x) ∨ B) ⇔ ∃xA(x) ∨ B

  • ∃x(A(x) ∧ B) ⇔ ∃xA(x) ∧ B

  • ∃x(A(x) → B) ⇔ ∀xA(x) → B

  • ∃x(B → A(x)) ⇔ B → ∃xA(x)

三、量词分配等值式

  • ∀x(A(x) ∧ B(x)) ⇔ ∀xA(x) ∧ ∀xB(x)
  • ∃x(A(x) ∨ B(x)) ⇔ ∃xA(x) ∨ ∃xB(x)

注意到∀对∨是不可分配的,∃对∧是不可分配的,这也很好理解.

因为含有B的公式中的约束变元x都本应该写成y(防止与A中的x相同),但在∀xA(x) ∧ ∀yB(y)中由于∧需要满足两边式子都成立,因此x=y时也要成立,所以可以写成∀x(A(x) ∧ B(x)),而若 是∀xA(x) ∨ ∀yB(y)只需要有一边式子成立,故当x=y时可能有一边不满足.

同时,∃xA(x) ∨ ∃yB(y)由于只要找到一个数z满足一边条件就能让式子成立,无论是x=z还是y=z都可以,因此可以写成∃x(A(x) ∨ B(x)) ,而∃xA(x) ∧ ∃yB(y)中由于需要找到两个数z1,z2使得这个式子满足,而这两个数不一定相等,故不能合并.

集合与关系

集合概念

真包含

  • A ⊂ B 当且仅当

    • 对任意 x，若 x ∈ A，则 x ∈ B
    • 且 A ≠ B

幂集

P(A)：A 的所有子集组成的集合

公式：
P(A) = { B | B ⊆ A }
|p(A)|=2^|A|

集合运算

相对补

  • A - B = A ∩ ~B

对称差

  • A ⊕ B = (A − B) ∪ (B − A)
  • A ⊕ B = (A ∪ B) − (A ∩ B)

对称差运算满足结合律,交换律,分配律,消去律
其中分配律最难理解

证明：A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C)

1
2
3
4
5
A ∩ (B ⊕ C)
= A ∩ [(B − C) ∪ (C − B)]
= [A ∩ (B − C)] ∪ [A ∩ (C − B)]
= [(A ∩ B) − (A ∩ C)] ∪ [(A ∩ C) − (A ∩ B)]
= (A ∩ B) ⊕ (A ∩ C)

例题

关系的定义

定义

  • A到A的关系R称为A上的关系

全域关系与恒等关系

  • 全域关系（EA）：集合 A 上的全体可能的有序对，即 EA = A × A。
  • 恒等关系（IA）：集合 A 上所有元素与自身配对的关系，即 IA = {<x, x> | x ∈ A}

关系的几种性质

这里都是对于A上的关系R进行展开的

性质名称 定义 关系矩阵特点 关系图特点
自反性 ∀x∈A，(x,x)∈R 主对角线元素全为 1 每个结点都有自环
反自反性 ∀x∈A，(x,x)∉R 主对角线元素全为 0 所有结点均无自环
对称性 ∀x,y∈A，(x,y)∈R ⇒ (y,x)∈R 矩阵关于主对角线对称 任一有向边必有反向边
反对称性 ∀x,y∈A，(x,y)∈R 且 (y,x)∈R ⇒ x=y 主对角线外不出现对称的 1 不同结点间不能出现双向边
传递性 ∀x,y,z∈A，(x,y)∈R 且 (y,z)∈R ⇒ (x,z)∈R 若 m_xy=1 且 m_yz=1，则 m_xz=1 存在长度为 2 的路径则必须有直接边

注意到反对称和对称可以是在单位矩阵中同时存在,因为两个对称位置都为0也可以认为是反对称的

关系的运算

关系的逆

设关系 ® 是集合 (A) 到集合 (B) 的一个二元关系，即 R ⊆ A × B，则关系 R 的逆关系记作 R⁻¹，定义为：

  • R⁻¹ = {(b, a) | (a, b) ∈ R}
    即将 R 中每一对元素的顺序交换。

性质：

  • (R⁻¹)⁻¹ = R
  • 如果 R 是 A 上的关系，则 R⁻¹ 仍是 A 上的关系

关系合成

设 R 是集合 A 到 B 的关系，S 是集合 B 到 C 的关系，则关系 S 与 R 的合成（或复合）记作 S ∘ R，定义为：

  • S ∘ R = {(a, c) | 存在 b ∈ B，使得 (a, b) ∈ R 且 (b, c) ∈ S}

性质：

(F ∘ G) ∘ H = F ∘ (G ∘ H)
(F ∘ G)⁻¹ = G⁻¹ ∘ F⁻¹

关系合成结合律的证明

要证：(F ∘ G) ∘ H = F ∘ (G ∘ H)

证明思路：通过任意元素对 <x, y> 来判断两边是否相等。

  1. 任取一对 <x, y>，假设 <x, y> ∈ (F ∘ G) ∘ H。
    根据关系合成的定义，存在 t 使得：

    • <x, t> ∈ F ∘ G
    • <t, y> ∈ H

  2. 进一步展开 <x, t> ∈ F ∘ G 的定义，存在 s 使得：

    • <x, s> ∈ F
    • <s, t> ∈ G

  3. 现在我们有：

    • <x, s> ∈ F
    • <s, t> ∈ G
    • <t, y> ∈ H

    也就是存在 s 和 t，使得上述三条都成立。

  4. 可以先固定 s，再看 t 是否存在：

    • 对于固定的 s，存在 t 使得 <s, t> ∈ G 且 <t, y> ∈ H
    • 根据合成定义，这说明 <s, y> ∈ G ∘ H

  5. 因此我们得到：

    • <x, s> ∈ F
    • <s, y> ∈ G ∘ H
    • 所以 <x, y> ∈ F ∘ (G ∘ H)

  6. 反向也类似（从 F ∘ (G ∘ H) → (F ∘ G) ∘ H），所以两边相等。

关系的幂

设 R 是集合 A 上的关系，n 为自然数，则定义 R 的 n 次幂如下：

  1. 零次幂
    R⁰ = {<x, x> | x ∈ A} = IA（恒等关系）

  2. 递推定义
    Rⁿ⁺¹ = Rⁿ ∘ R（与矩阵乘法类似，用关系合成定义）

集合 A 上关系的个数

设集合 A 有 n 个元素，即 |A| = n。

  1. 关系的定义
    A 上的一个关系 R 是 A × A 的任意子集。

    • 因为 A × A 有 n² 个有序对
    • 每个有序对可以选择“在关系中”或“不在关系中”

  2. 关系数计算

    • 对每个有序对有 2 种选择
    • 总共有 n² 个有序对
    • 因此关系的总数为 2^(n²)

结论：
集合 A 上关系的总数 = 2^(n²)

关系闭包

自反闭包(reverse)

  • r(R) = R ∪ {(x,x) | x ∈ A}
    相当于加上单位矩阵I

对称闭包(symmetry)

  • s(R) = R ∪ R⁻¹
    补全另一半即可

传递闭包(transfer)

  • t(R) = R ∪ R² ∪ R³ ∪ ···
    这个只好一个个推了,不出错就行’

等价类, 商集与划分

等价类

定义

设 R 是集合 A 上的等价关系，对任意 a ∈ A，
a 的等价类定义为
[a] = { x ∈ A | (a, x) ∈ R }

四条性质及其证明

性质一：a ∈ [a]

即每个元素属于自己的等价类

证明

因为 R 是等价关系，满足自反性，
所以 (a, a) ∈ R，
由等价类定义可知 a ∈ [a]。

性质二：若 b ∈ [a]，则 [b] = [a]

证明

b ∈ [a] 等价于 (a, b) ∈ R。

先证 [b] ⊆ [a]：
任取 x ∈ [b]，则 (b, x) ∈ R。
又因 (a, b) ∈ R，R 具有传递性，
得 (a, x) ∈ R，故 x ∈ [a]。

再证 [a] ⊆ [b]：
由 (a, b) ∈ R 且 R 具有对称性，
得 (b, a) ∈ R，
同理可证任意 x ∈ [a] 有 x ∈ [b]。

因此 [a] = [b]。

性质三：若 [a] ∩ [b] ≠ ∅，则 [a] = [b] (即aRy)

证明

设存在 c ∈ [a] ∩ [b]，
则 (a, c) ∈ R 且 (b, c) ∈ R。

由 (b, c) ∈ R 和对称性得 (c, b) ∈ R，
再由 (a, c) ∈ R 和传递性得 (a, b) ∈ R。

于是 b ∈ [a]，由性质二可得 [a] = [b]。

性质四：所有等价类的并集等于原集合 A

证明

任取 x ∈ A，
由于 R 是等价关系，满足自反性，
有 (x, x) ∈ R，
因而 x ∈ [x]。

又因为 [x] 是 A 上的一个等价类，
所以 x 属于所有等价类的并集中。

由 x 的任意性可得
⋃{ [a] | a ∈ A } = A。

商集

定义

设 R 是集合 A 上的等价关系,
A 关于 R 的商集定义为
A / R = { [a] | a ∈ A }

  • 也就是说把A划分成多个等价类

划分

定义

设 A 为非空集合, 若 A 的一个子集族 P 满足

  1. 任意 B ∈ P, B ≠ ∅
  2. 任意 B1, B2 ∈ P, 若 B1 ≠ B2, 则 B1 ∩ B2 = ∅
  3. ⋃P = A

则称 P 是 A 的一个划分

由集合 A 的一个划分得到 A 上的等价关系

设 A 为非空集合，
π = { A₁, A₂, … } 是 A 的一个划分。

定义关系 R：

R = { <x, y> | x, y ∈ A，且 x 与 y 属于 π 中的同一划分块 }

说明：

  • 对任意 x ∈ A，x 与自身属于同一划分块，故 <x, x> ∈ R
  • 若 <x, y> ∈ R，则 x、y 在同一划分块中，对称性显然成立
  • 若 <x, y> ∈ R 且 <y, z> ∈ R，则 x、y、z 属于同一划分块，传递性成立

因此，R 是集合 A 上的等价关系。

例题

给出 A = {1, 2, 3} 上所有的等价关系

  • 求解思路
    先写出 A 的所有划分，再由每个划分得到对应的等价关系。

第一步：列出 A 的所有划分

A = {1, 2, 3} 的所有划分共有 5 种：

  1. π₁ = { {1}, {2}, {3} }
  2. π₂ = { {1, 2}, {3} }
  3. π₃ = { {1, 3}, {2} }
  4. π₄ = { {2, 3}, {1} }
  5. π₅ = { {1, 2, 3} }

第二步：由划分写出对应的等价关系

π₁ = { {1}, {2}, {3} }

R₁ = { <1,1>, <2,2>, < 3,3> }

π₂ = { {1,2}, {3} }

R₂ = {
<1,1>, <2,2>, < 3,3>,
<1,2>, <2,1>
}

π₃ = { {1,3}, {2} }

R₃ = {
<1,1>, < 3,3>, <2,2>,
<1,3>, < 3,1>
}

π₄ = { {2,3}, {1} }

R₄ = {
<2,2>, < 3,3>, <1,1>,
<2,3>, < 3,2>
}

π₅ = { {1,2,3} }

R₅ = {
<1,1>, <2,2>, < 3,3>,
<1,2>, <2,1>,
<1,3>, < 3,1>,
<2,3>, < 3,2>
}

结论

集合 A = {1,2,3} 上一共有 5 个等价关系，
与 A 的 5 种划分一一对应。

等价关系与偏序关系

等价关系:要求集合A上的R关系是自反,对称,传递的.
偏序关系:要求集合A上的R关系是自反,反对称,传递的.

  • 从定义可以知道偏序关系图中不存在双向箭头.
  • 注意下面的小于等于只是表示偏序关系中的上下级关系

偏序集:A与A上的偏序关系R一起称做偏序集,记为<A,R>,对于任意的x,y∈A,若x<=y或者y<=x成立,则称x与y是可比的,若x<y,且x与y之间不存在z∈A使得x<z<y,则称y盖住x.

  • 简略一点说,y盖住x表示y是x的直属上司,y与x可比表示二者在同一条分支上,具有亲缘关系

全序集:若偏序集中∀x,y∈A,x与y都可比,则称(A,<=)是全序集

设 (A, ≤) 为偏序集，B ⊆ A。

  • 最小元：若存在 m ∈ B，使得 ∀x ∈ B，都有 m ≤ x，则称 m 为 B 的最小元。
  • 最大元：若存在 M ∈ B，使得 ∀x ∈ B，都有 x ≤ M，则称 M 为 B 的最大元。
  • 极小元：若 m ∈ B，且不存在 x ∈ B 使得 x < m，则称 m 为 B 的极小元。
  • 极大元：若 M ∈ B，且不存在 x ∈ B 使得 M < x，则称 M 为 B 的极大元。
  • 上界：若 u ∈ A，使得 ∀x ∈ B，都有 x ≤ u，则称 u 为 B 的一个上界。
  • 下界：若 l ∈ A，使得 ∀x ∈ B，都有 l ≤ x，则称 l 为 B 的一个下界。
  • 最小上界：u是B的上界集合中的最小元，则称 u 为 B 的最小上界。
  • 最大下界：l是B的下界集合中的最大元，则称 l 为 B 的最大下界。
  • 简单一点说,最大元就是跟所有元素都可比,故需要位于哈斯图的上顶点,约束所有分支,故只能有一个,同理,最小元位于哈斯图的下顶点,只能有一个
  • 极小元和极大元可以有多个,只要位于某一条分支的上顶点或者下顶点就可以了,因此最大元也是极小元,最小元也是极大元.
  • 如果有多个极大元,就一定没有最大元,有多个极小元,就一定没有最小元,因为分支没有收束.
  • 上界可以看成是偏序集中所有元素的上司,可以有多个,但最小上界只能有一个

我想到的问题:如果一个偏序子集B上方连接的两个直属上司构成了一个三角形时还会有最小上界吗

  • 经过思考后我发现偏序关系图中不存在三角形,因为反对称性决定了如果a<=b,b<=a则a=b,故不会有两个分支在同级连接的情况,否则两个元素就相互可比了.

函数

函数定义

设 f 是集合 A 与 B 之间的二元关系，
若满足：
对任意 x ∈ dom(f)，存在唯一的 y ∈ ran(f) 使得 x f y 成立，
则称 f 为 函数（从 A 到 B 的函数）。

对于函数 f，如果 x f y，则通常记作
y = f(x)

单射 / 满射 / 双射

设 f : A → B 为函数。

  • 单射

    若对任意 x₁, x₂ ∈ A，
    f(x₁) = f(x₂) ⟹ x₁ = x₂，
    则称 f 为从 A 到 B 的单射。

  • 满射

    若对任意 y ∈ B，
    存在 x ∈ A，使得 f(x) = y，
    则称 f 为从 A 到 B 的满射。

  • 双射

    若 f 既是单射又是满射，
    则称 f 为从 A 到 B 的双射。

特征函数

设 A 为集合，B ⊆ A，
定义函数 χ_B : A → {0, 1} 为

χ_B(x) = 1，当 x ∈ B
χ_B(x) = 0，当 x ∉ B

χ_B 称为集合 B 在 A 上的特征函数。

B 上 A

定义

所有从集合 A 到集合 B 的函数所组成的集合，记作 B 上 A，
读作“B 上 A”。

符号化表示

B^A = { f | f : A → B }

计数性质

  • 设 |A| = m，|B| = n，且 m，n > 0，
    则

    |B^A| = n^m

特殊情况

  • 若 A = ∅，则

    B^∅ = { ∅ }

  • 若 A ≠ ∅ 且 B = ∅，则

    ∅^A = ∅