Skip to main content

cdm-notes

离散数学

image-20250114005315816

(P↔Q)↔R=P↔(Q↔R)P→(Q→R)=(P→Q)→(P→R)(P\leftrightarrow Q)\leftrightarrow R=P\leftrightarrow(Q\leftrightarrow R)\\ P\to(Q\to R)=(P\to Q)\to(P\to R)

n个命题变项能组成具有不同真值的命题公式有22n2 ^ {2 ^ {n}}，与其任一命题公式等值而形式不同的命题公式有无穷个

术语

  • 文字

    P,¬PP,\neg P统称为文字，是合取范式也是析取范式

  • 合取式（短语）

    有限个文字的合取称为合取式

  • 析取式（子句）

    有限个文字的析取称为析取式

  • 互补对

    P与¬P称为互补对

  • 析取范式

    有限个合取式的析取式， 𝐴1 ∨ 𝐴2 ∨ ⋯ ∨ 𝐴𝑛, 其中𝐴𝑖(𝑖 = 1, … , 𝑛)为合取式

  • 合取范式

    有限个析取式的合取式， 𝐴1 ∧ 𝐴2 ∧ ⋯ ∧ 𝐴𝑛, 其中𝐴𝑖(𝑖 = 1, … , 𝑛)为合取式

永假式不能用主析取范式表达出来

极小项编码：

例：¬P1∧P2∧P3:m011=m3\neg P_1\land P_2\land P_3:m_{011}=m_3 形式：A=m1∨m3=∨1,3A=m_1\vee m_3=\vee_{1,3}

永真式不能用主合取范式表达出来

极大项编码：

例：¬P1∨P2∨P3:M011=M3\neg P_1\vee P_2\vee P_3:M_{011}=M_3 形式：A=M1∧M3=∧1;3A=M_1\land M_3=\land_{1;3}

主析取范式和主合取范式的转换

∨0;1;4;5;7=∧(2;3;6)补=∧5;4;1∨0;1;4;5;7=∧{0;1;2;3;4;5;6;7}−{7;6;3;2;0}=∧5;4;1\vee_{0;1;4;5;7}=\land_{(2;3;6)补}=\land_{5;4;1}\\ \vee_{0;1;4;5;7}=\land_{\{0;1;2;3;4;5;6;7\}-\{7;6;3;2;0\}}=\land_{5;4;1}

范式功能

  • 判断重言式

    合取范式中所有析取式都有互补对（P∨¬PP\vee\neg P）

  • 判断矛盾式

    析取范式中所有合取式都有互补对

  • 判断公式等值

    范式不唯一，引入唯一主范式，判断公式等值

重言蕴含

只要A取值为真， B就必取值为真，称A重言（永真）蕴涵B，或称B是A的逻辑推论，记作A⇒BA\Rightarrow B（⇒\Rightarrow表示两公式之间的真值关系，不是逻辑联结词，这个式子不是合式公式）

image-20250114011332552

image-20250114011421983

image-20250114011517004

image-20250114011537643

image-20250114011904145

有限域上，一个公式的可满足性和普遍有效性依赖于个体域个体的个数且仅依赖于个体域个体的数目，即在某个含𝑘个元素的𝑘个体域上普遍有效（或可满足），则在任一𝑘个体域上也普遍有效（或可满足）

判定问题

  • 如某公式在𝑘个体域上普遍有效，则在𝑘 − 1个体域上也普遍有效
  • 如某公式在𝑘个体域上可满足，则在𝑘 + 1个体域上也可满足

范式

谓词逻辑的公式也有范式，其前束范式与原公式是等值的，其他范式与原公式只有较弱的关系

前束范式

公式中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端

Skolem标准型：只保留全称量词的前束型

只保留全称量词而消去存在量词

任一公式都可化作Skolem标准型（只保留全称量词的前束型）

A是不可满足的，当且仅当其Skolem标准型是不可满足的

不可满足公式与Skolem标准型是等值的

image-20250114012509889

推理演算：推理规则

  • 全称量词消去规则 (∀x)P(x)⇒P(a)(\forall x)P(x)\Rightarrow P(a)
  • 全称量词引入规则 P(y)⇒(∀x)P(x)P(y)\Rightarrow (\forall x)P(x)
  • 存在量词消去规则 (∃x)P(x)⇒P(c)(\exist x)P(x)\Rightarrow P(c)
  • 存在量词引入规则 P(c)⇒(∃x)P(x)P(c)\Rightarrow (\exist x)P(x)

image-20250114013008717

谓词逻辑的归结推理法

  1. 反证法

    为证明𝐴 → 𝐵是定理（𝐴, 𝐵是谓词公式），等价的是证明𝐴 ∧ ¬𝐵 = 𝐺是矛盾式

  2. 建立子句集𝑺 关键点：消去𝐺中的量词，特别是存在量词； 方法：

    1. 将𝐺化作等值的前束范式
    2. 将前束范式化为Skolem标准形（消去存在量词），得到仅含全称量词的公式𝐺 ∗ ，𝐺和𝐺 ∗ 在不可满足时是等值的，而𝐺 的不可满足性可由𝐺 ∗ 的不可满足性求得
    3. 将𝐺 ∗中的全称量词省略，𝐺 ∗母式（已合取范式化）中的合取词∧以“，”表示，可得子句集𝑆

    说明：𝑆和𝐺是同不可满足，𝑆中的变元视作有全称量词作用着

  3. 对𝑺作归结, 重复 设𝐶1，𝐶2是两个无共同变元的子句，𝐿1, 𝐿2分别是𝐶1，𝐶2中的文字，如果𝐿1和¬𝐿2中有合一置换𝜎，则：(𝐶1𝜎 − {𝐿1𝜎}) ∪ (𝐶2𝜎 − {𝐿2𝜎}) 作为子句𝐶1，𝐶2的归结式。 如：𝐶1 = 𝑃(𝑥) ∨ 𝑄(𝑥) 𝐶2 = ¬𝑃(𝑎) ∨ 𝑅(𝑦) 𝑃(𝑥)与¬𝑃(𝑎)在合一置换{𝑥/𝑎}下将变元𝑥换成𝑎，互补对可做归结，有归结式𝑅（𝐶1, 𝐶2）= 𝑄(𝑎) ∨ 𝑅(𝑦)

  4. 直至归结出空子句□ ，证明结束

image-20250114013220298

常用等值公式

P→Q=¬P∨QP→Q=¬Q→¬PP↔Q=(P∧Q)∨(¬P∧¬Q)P↔Q=(P→Q)∧(Q→P)=(P∨¬Q)∧(¬P∨Q)P→(Q→R)=(P∧Q)→RP→(Q→R)=Q→(P→R)(P→R)∧(Q→R)=(P∨Q)→RP\to Q=\neg P\vee Q\\ P\to Q=\neg Q\to \neg P\\ P\leftrightarrow Q=(P\land Q)\vee(\neg P\land \neg Q)\\ P\leftrightarrow Q=(P\to Q)\land(Q\to P)=(P\vee\neg Q)\land (\neg P\vee Q)\\ P\to(Q\to R)=(P\land Q)\to R\\ P\to(Q\to R)=Q\to(P\to R)\\ (P\to R)\land (Q\to R)=(P\vee Q)\to R

真值表的T列写和F列写

T列写: 析取范式

F列写: 合取范式

异或对交分配律

幂集合性质

P(A)∩P(B)⇔P(A∩B)P(A)∪P(B)⊆P(A∪B)P(A)\cap P(B)\Leftrightarrow P(A\cap B)\\ P(A)\cup P(B)\sube P(A\cup B)

P(A)∈P(B)⇒A∈BP(A)\in P(B)\Rightarrow A\in B

P(A−B)⊆(P(A)−P(B))∪{∅}P(A-B)\sube (P(A)-P(B))\cup \{\varnothing\}, 空集不能漏

image-20250113233254768

量词对蕴涵的分配律

(∀x)(P(x)→q)=(∃x)P(x)→q(∃x)(P(x)→q)=(∀x)P(x)→q(∀x)(p→Q(x))=p→(∀x)Q(x)(∃x)(p→Q(x))=p→(∃x)Q(x)\begin{array}{l} (\forall x)(P(x) \rightarrow q)=(\exists x) P(x) \rightarrow q \\ (\exists x)(P(x) \rightarrow q)=(\forall x) P(x) \rightarrow q \\ (\forall x)(p \rightarrow Q(x))=p \rightarrow(\forall x) Q(x) \\ (\exists x)(p \rightarrow Q(x))=p \rightarrow(\exists x) Q(x) \end{array}

计算问题：有输入有输出，中间是computer

可计算：程序能不能输出一个结果

  • 良定义的输入
  • 不是无限时间（有限步骤完成）

不可计算的问题有无穷多个

广义交并, 回归定义

空集的广义并是空集, 广义交是anything(->的前半恒false, ->恒true) -> 未定义

A⊆B⇒∪A⊆∪BA⊆B⇒∩B⊆∩A(A,B非空)A\sube B\Rightarrow \cup A\sube \cup B\\ A\sube B\Rightarrow \cap B\sube \cap A(A,B非空)

∪(A∪B)=(∪A)∪(∪B)∩(A∪B)=(∩A)∩(∩B)(A,B非空)\cup (A\cup B)=(\cup A)\cup (\cup B)\\ \cap (A\cup B)=(\cap A)\cap(\cap B)(A,B非空)

∪(P(A))=A\cup (P(A))=A 广义并是幂集的逆运算

  • 定理十四：若集合A是传递集合，则∪A\cup A是传递集合
  • 定理十五：若集合AA的元素是传递集合，则∪A\cup A是传递集合
  • 定理十六：若非空集合AA是传递集合，则∩A\cap A是传递集合，且∩A≠∅\cap A\neq\varnothing
  • 定理十七：若集合AA的元素都是传递集合，则∩A\cap A是传递集合

对称差 A⊕BA \oplus B : (A−B)∪(B−A)(A-B)\cup(B-A)

集合关系证明

  1. 定义
  2. 逻辑恒等式
  3. 不断用定律展开式子

笛卡尔积的性质: 满足分配律(对交并都是), 不满足交换律和结合律

笛卡尔积是另一个笛卡尔积的子集等效于积的每一项都是对应项的子集

(A×B⊆C×D)⇔(A⊆C∧B⊆D)(A\times B\sube C \times D)\Leftrightarrow (A\sube C\land B\sube D)

(A⊆B)⇔(A×C⊆B×C)⇔(C×A⊆C×B)(A\sube B)\Leftrightarrow (A\times C\sube B\times C)\Leftrightarrow (C\times A\sube C\times B)

image-20250115194749529

不可以使用画图证明！

计算问题的类型：搜索问题, 计数问题, 优化问题, 判定问题 -> SAT问题

解决了判定问题, 其他问题就可以划归成判定问题

字母表->有限长度的字符集, string -> 子集, 合法的string, lauguage

decide: 输入w是否是语言L的元素

what problems computer can solve ? -> what lauguages can a computer recoginize?

朴素集合论:

  • 穷举表示
  • 内涵表示(用谓词定义)

朴素集合论会带来矛盾:

如果S∈SS \in S, 那么SS满足P(x)P(x), S∉SS \notin S

反之同理

发现不管S∈SS \in S成立与否都矛盾

公理系统

ZF公理系统

子集公理: 单纯的谓词定义不够, 需要指定谓词在哪个集合上作用, 在集合上作用的谓词才是新的合法集合

正则公理: 对任意的一个非空集合x, 存在一个元素和x不相交

A∉AA \notin A的证明

A0={A}A_0 = \{A\}, 由正则公理, A0∩A=∅A_{0} \cap A = \empty

如果A∈AA\in A 又有A∈{A}=A0A \in \{A\} = A_0 则得到A∩A0=A≠∅A \cap A_0 = A \not= \empty,矛盾！

集合的势(基数): 元素个数 ∣A∣|A|

A无限集合的势

阿列夫0(ℵ0\aleph_0): 自然数集合的势

比较两个集合的方法: 一一对应则等势

有理数Q和自然数N等势

可数集合的基数 <= ℵ0\aleph_0

幂集合公理, 一个集合的所有子集构成的集合存在(集合的幂集是集合)

∣P(A)∣=2∣A∣|P(A)| = 2^{|A|}

对于有限集合必有∣P(A)∣>A|P(A)| > A

但对于无限集合呢? 也成立

证明

首先P(A) >= A, 证P(A) != A即可

假设A和P(A)可以一一对应, 设 aia_i 对应 {ai1,ai2,...,aij}\{a_{i1}, a_{i2}, ..., a_{ij}\} 这样一行

构造一个子集为: 在每一行取一个aija_{ij}然后取反

假设这个子集与a对应, 那他应该是前面的一行, 但因为包含了取反的元素, 所以它不等于前面的一行, 矛盾!

所以∣P(A)∣>∣A∣|P(A)| > |A| 恒成立(康托尔定理),

  • 无限有无限多个
  • 没有最大的无限

定义 ℵ1=P(ℵ0)\aleph_1 = P(\aleph_0), 以此类推ℵ2\aleph_2, ...

实数集合

证明计算机不能解决所有的问题 |programs|<= |strings| < |sets of strings| <= |problems| (对任意一个string set,至少可以构造一个问题,例如set之中最短的string)

所以 |programs| < |problems|

一定有问题是没有对应的program的映射的, 即计算机不可解

|形式语言| = |sets of strings|

字符串是有限长的, 因而可以base 字母表 (例如26进制)得到和一个整数的双射

所以|strings| = ℵ0\aleph_0

一维数轴上的所有点的集合和二维平面的所有点的集合，它们的基数是一样的，都是 c (continuum)，也就是实数的基数。

这可能乍一看有些违反直觉，因为二维平面似乎比一维数轴包含“更多”点。然而，基数的概念在无限集上与有限集的计数方式有所不同。 我们用一一对应来定义基数：如果两个集合之间存在一一对应的映射，则它们具有相同的基数。

证明一维和二维实数集具有相同基数的方法有很多，其中一种常见的方法是利用实数的小数表示法。

证明思路：

我们可以将一个区间 (0, 1) 内的实数与整个实数集建立一一对应，然后将 (0, 1) 内的实数与二维平面上的点建立一一对应。

  1. (0, 1) 与实数集 R 的一一对应: 我们可以通过一些简单的函数变换，例如双曲正切函数 tanh(x)，将 (0, 1) 映射到整个实数集 R。

  2. (0, 1) 与 (0, 1) x (0, 1) 的一一对应: 这步是关键。我们可以将 (0, 1) 中的实数 x 表示成其十进制展开形式：x = 0.d₁d₂d₃d₄... 然后，我们可以构造一个映射，将 x 映射到 (0, 1) x (0, 1) 中的点 (y, z)，其中 y 和 z 的十进制展开分别由 x 的十进制展开的奇数位和偶数位组成：

    y = 0.d₁d₃d₅... z = 0.d₂d₄d₆...

    这个映射是 (0, 1) 到 (0, 1) x (0, 1) 的一一对应（需要处理一些特殊情况，例如 0.999... = 1 的情况，但这不影响整体的证明思路）。

  3. (0, 1) x (0, 1) 与二维平面: (0, 1) x (0, 1) 是单位正方形，我们可以通过一些几何变换将单位正方形映射到整个二维平面。

进一步的结论, ∣(a,b)∣=∣R∣=∣Rn∣|(a, b)| = |R| = |R^n|

连续统假设: ∣R∣=ℵ1|R| = \aleph_1 ,这在ZFC公理体系下不可证明或证伪

关系

A,B的一个关系,是A×BA \times B 的子集

A的关系是 A×AA \times A 的子集

关系的性质:

  • (R1∪R2)∘R3=R1∘R3∪R2∘R3\left(R_{1} \cup R_{2}\right) \circ R_{3}=R_{1} \circ R_{3} \cup R_{2} \circ R_{3} 并分配
  • (R1∩R2)∘R3⊆R1∘R3∩R2∘R3\left(R_{1} \cap R_{2}\right) \circ R_{3} \subseteq R_{1} \circ R_{3} \cap R_{2} \circ R_{3} 交子集

aRbaRb, aR̸ba\not R b : <a,b>∈R,<a,b>∉R<a, b> \in R, <a,b> \notin R

恒等关系 Ia:{<x,x>∣x∈A}I_a: \{<x,x>|x \in A\}

全域关系 Ea:R=A×BE_a: R = A \times B

空关系 Na=∅N_a = \empty

dom(R)dom(R) 定义域

ran(R)ran(R) 值域

fld(R)fld(R) = dom(R)∪ran(R)dom(R) \cup ran(R) = ∪∪R\cup \cup R

关系矩阵M(R)=(rij)m×n,rij=<xi,yi>∈RM(R) = (r_{ij})_{m \times n},r_{ij}=<x_i,y_i> \in R

关系图: X→YX \to Y的关系R, 图的顶点 X∪YX \cup Y 边 R

image-20250113200628191

图论算法->关系图

R在A上的限制R↾AR\upharpoonright A为A到Y的关系

A在R下的象 R[A] 实质是R↾AR\upharpoonright A的值域

关系的逆 R−1R^{-1}: {<x,y>∣<y,x>∈R}\{<x,y> |<y, x> \in R\}, M(R−1)=MT(R)M(R^{-1}) = M^T(R)

关系的合成 R与S的合成 记为 S∘RS\circ R , M(S∘R)=M(R)M(S)M(S \circ R) = M(R)M(S)

逻辑(矩阵)乘 ⊙\odot ：A⊙BA \odot B

R[A]−R[B]⊆R[A−B]R[A]-R[B]\sube R[A-B]

恒等式证明: 拆开有序对, 可以直接变成关系矩阵的关系吗?

partitions 划分

  • 空集不属于划分
  • 任意属于划分的属于原来的集合
  • 划分的广义并=原来的集合
  • 划分的任意两个元素交集为空

partition 关系R, partition π\pi of set A

def: R={<a,b>∣∃π0(π0∈π∧a∈π0∧b∈π0)}R = \{<a, b> | \exist \pi_0 (\pi_0 \in \pi \wedge a \in \pi_0 \wedge b \in \pi_0)\}

(a,b在同一个partition block里面)

则有

  • aRaaRa for any a∈Aa \in A 自反性
  • if aRbaRb, then bRabRa 对称性
  • if aRbaRb and bRcbRc, then aRcaRc 传递性

自反性

  • x = x for any x
  • A⊆AA \subseteq A
  • IA,EAI_A, E_A
  • =,≥,≤ on R=, \ge, \le \space on \space \R

...

等价于关系矩阵对角线是1

对称性

  • IA,EA,NAI_A, E_A, N_A (NAN_A空关系)
  • 四种状态：对称、反对称，既不是对称也不是反对称，既是对称也是反对称
  • 反对称: ((x∈A∧y∈A∧xRy∧x≠y)→yR̸x)((x \in A \wedge y \in A \wedge x R y \wedge x \neq y) \rightarrow y \not R x) 或者等价的 ((x∈A∧y∈A∧xRy∧yRx)→x=y)((x \in A \wedge y \in A \wedge x R y \wedge y R x) \rightarrow x=y)

关系矩阵 M=MTM = M^T, 即矩阵对称

反对称: 矩阵反对称

即是反对称也是对称: 只有对角线存在1

即

  • R对称 ⇔R=R−1\Leftrightarrow R=R^{-1}
  • R反对称 ⇔R∩R−1⊆IA\Leftrightarrow R \cap R^{-1} \subseteq I_{A}

传递性

  • IA,EA,NAI_A, E_A, N_A
  • ⊆\subseteq
  • 正整数集的整除关系

如果R1,R2R_1, R_2自反, 则R1−1,R1∩R2,R1∪R2,R1∘R2R_1^{-1}, R_1 \cap R_2, R_1 \cup R_2, R_1 \circ R_2都自反(要求R1,R2R_{1}, R_{2}都是同一个集合上的关系, 以下均有)

对称, 反自反也有R1−1,R1∩R2,R1∪R2R_1^{-1}, R_1 \cap R_2, R_1 \cup R_2 对R1∘R2R_1 \circ R_2不满足

传递对R1∪R2,R1∘R2R_1 \cup R_2, R_1 \circ R_2不满足, t(R1)∪t(R2)⊆t(R1∪R2)t(R_1) \cup t(R_2) \sube t(R_1 \cup R_2)

反对称同对称

image-20250113203528260

如果一个关系同时满足自反,对称,传递,则称为等价关系

正方形表示A×AA \times A, AA上的等价关系就相当于是对角线 + 对角线为对称轴的正方形

等价类: 等价关系R

[x]R={y∣y∈A∧xRy}[x]_R = \{y | y \in A \wedge xRy\}

一个等价类可以生成 partition block, 称为等价关系R诱导的划分 πR\pi_R

  • ∪{[x]R∣x∈A}=A\cup\left\{[x]_{R} \mid x \in A\right\}=A

划分: 四个条件: 子集族, 不空, 不漏, 不交

规定空集的划分是空集

对于一个划分π\pi,也可以生成一个等价关系R, 称为诱导的关系 RπR_{\pi}

集合A的划分和等价关系一一对应

集合划分问题（等价关系个数问题）

计算思路: 对于n个元素的全集，分成m个子集,设分法为f(n,m)

m == 1 || m == n时，f(n,1)==f(n,n)==1

又有递推式f(n,m)=m*f(n-1, m) + f(n-1,m-1)

（考虑最后一个元素,有两种情况,一种已经有m个集合,加入这m个之中, 为m*f(n-1,m), 另一种只有m-1个集合,最后一个元素是一个单独的新集合,为f(n-1,m-1)）

则划分个数F(n) = sum(f(n,1) .. f(n,n))

等价类的集合 商集 quotient set

A/R={y∣∃x(x∈A∧y=[x]R)}A/R = \{y|\exist x (x\in A \wedge y=[x]_R) \}

商集 等价于 partition

e.g

java equals

  • 自反性
  • 对称性
  • 传递性

covers 将一个集合分成若干个非空子集，子集的集合称为cover

和partition的区别

partition 一个元素只能属于一个子集

cover 一个元素可以属于多个子集

partition ⊆\subseteq cover, 划分中各元素不相交，覆盖中各元素可能相交

cover 关系满足自反和对称，不满足传递性

自反+对称: 相容关系 Compatible Relation

相容类: 给定相容关系R, 集合A

相容类C定义为

  • C⊆AC \subseteq A
  • C={x∣x∈A∧∀y((y∈C)→xRy)}C = \{x| x\in A \wedge \forall y ((y\in C) \to xRy)\}

即A的一个子集, 满足里面两两之间满足相容关系R

极大相容类: CRC_R不是任何其他相容类的真子集

找极大相容类

从随便一个开始, 遍历, 不断尝试加入新的元素O(n)O(n)

相容关系简化图中，最大完全多边形是每个顶点和其他所有顶点相连的多边形，这种最大完全多边形的顶点集合，才是最大相容类；一个孤立点的集合也是最大相容类；如果两点连线不是最大完全多边形的边，这两个顶点的集合也是最大相容类。

完全覆盖

极大相容类的集合->A的cover,称为完全覆盖CR(A)C_R(A)

对非空集合A，覆盖Ω={A1,A2,⋯ ,An}\Omega=\{A_1,A_2,\cdots,A_n\}，由Ω\Omega确定的关系

R=A1×A1∪A2×A2∪⋯∪An×AnR=A_1\times A_1\cup A_2\times A_2\cup \cdots \cup A_n\times A_n

是A上的相容关系

判断关系和集合的关系的时候不要忘记有序对的定义

def<a,b>={a,{a,b}}def <a, b> = \{{a}, \{a, b\}\}

关系的合成在并下满足分配律, 交下不满足, 且先交的是后交的子集

关系的象R[A]也有这个并分配, 交子集的特点

一个覆盖可以确定一个相容关系

一个相容关系也可以确定一个完全覆盖

覆盖Ω={A1,A2,...,An}\Omega = \{A_1,A_2,...,A_n\}确定相容关系 R=A1×A1∪A2×A2∪...∪An×AnR = A_1 \times A_1 \cup A_2 \times A_2 \cup ... \cup A_n \times A_n

但相容关系和覆盖是1对多的, 不同覆盖可能确定一个相容关系

偏序partial order

R反对称性 aRb∧bRa→a=baRb \wedge bRa \to a = b

  • IAI_A
  • NAN_A

partial order: 自反, 反对称, 传递

偏序集: 集合和在集合上定义的偏序关系的pair, <A,R><A, R>

anti-reflexvity 非自反性: 对角线全0

∀a,a∈A→aR̸a\forall a, a \in A \to a\not R a

自反是对角线全1, 所以易得同时不满足两种性质的关系，但除了空关系之外没有同时满足两种性质的关系

使用的例子：偏序关系一定有R2=RR^2 = R

  • R2⊆R:<a,b>∈R,<b,c>∈R→<a,c>∈R(传递)R^2 \subseteq R: <a,b>\in R, <b,c> \in R \to <a,c> \in R(传递)
  • R⊆R2:<a,a>∈R(自反)，<a,b>∈R→<a,b>∈R(传递)R \subseteq R^2: <a,a>\in R(自反)，<a,b>\in R \to <a,b> \in R(传递)

拟序(quasi-order): 非自反 + 传递(从而一定有反对称)

反证: 假设不满足反对称, 存在xRy∧yRx∧x≠yxRy \wedge yRx \wedge x \ne y, 由传递性xRxxRx，和反对称矛盾

关系的幂

  • R0=IAR^0 = I_A
  • Rn+1=Rn∘RR^{n+1} = R^{n} \circ R

partial order和quasi order

p -> q: R′=R−R0R' = R-R^0

q -> p: R′=R+R0R' = R+R^0

cover relation

for poset <A,≤><A,\le>, if x,y∈A,x≤y,x≠yx, y \in A, x \le y , x \ne y, 不存在z∈A∧x≤z∧z≤yz\in A \wedge x\le z \wedge z\le y

也就是y比x刚好大"1" ,中间无空隙

成为y covers x

可以定义 cover relation

cov(A)={<x,y>∣x∈A∧y∈A∧(y covers x)}cov(A) = \{<x,y>|x\in A \wedge y \in A \wedge {(y \space covers \space x)}\}

Hasse Diagram 哈斯图

  • 顶点是元素
  • if x≤y∧x≠yx \le y \wedge x \ne y, 则y在x上面
  • if <x,y>∈cov(A)<x, y> \in cov(A), x y之间有无向边

一个更简单的画法是先画出所有的关系, 都作为边, 再把自反边和通过其他边可以推出的边去掉

最大元(全大于), 极大元(全不小于)

chain and anti-chain 链和反链

chain: 任意两个元素可比的子集

anti-chain: 任意两个都不可比

单个元素构成的集合: 同时为chain 和 anti-chain

将集合拆成不相交的反链:

最长链如果为n, 则最少要拆成n条反链

well order relation 良序关系

偏序集A的任意一个子集都有最小元素, 称A是良序集

例如自然数在小于等于上的偏序集是良序集, 实数的不是

全序关系: 任意两个元素均可比较

良序集都是全序集 total order set

因为可以取子集{x, y}, 一定有最小元推出x <= y or y <= x，则可比

有限的全序集都是良序集: 反之如实数，整数，都能轻松构造没有最小的子集

良序化：对于一个非良序的集合，可以定义集合上的一个全序关系，使该集合成为良序集

良序定理：任何的集合都是可以良序化的

极大极小和最大最小:

整除关系R上 B1={2,3,4,6}，极大元：4，6；极小元：2，3，没有最大元和最小元B_1=\{2,3,4,6\}，极大元：4，6；极小元：2，3，没有最大元和最小元

画图理解

上界：（集合中的元素）与子集中的都有关系且大于等于子集中的元素（哈斯图中，最大元及最大元以上的元素）

上确界: 上界里面最小的

B的上下界/上下确界可能不在B中: 整除关系, {2,3}\{2, 3\}的上确界是6

闭包:

(自反，对称，传递)闭包:

  • R 是 A上的非空集合
  • R⊆R′R \subseteq R', R'是(自反的，对称的，传递的)
  • ∀R′′,R⊆R′′→R′⊆R′′\forall R'', R \subseteq R'' \to R' \subseteq R'' (最小的代价)

自反闭包r(R)=R∪R0r(R) = R \cup R^0

对称闭包s(R)=R∪R−1s(R) = R \cup R^{-1}

传递闭包t(R)=R∪R2∪...∪Rn,n=∣A∣t(R) = R \cup R^{2} \cup ... \cup R^{n}, n=|A|

  • r(R1)∪r(R2)=r(R1∪R2)r(R_1) \cup r(R_2) = r(R_1 \cup R_2)
  • s(R1)∪s(R2)=s(R1∪R2)s(R_1) \cup s(R_2) = s(R_1 \cup R_2)
  • t(R1)∪t(R2)⊆t(R1∪R2)t(R_1) \cup t(R_2) \subseteq t(R_1 \cup R_2)

引理: 存在从a到b的长为n的path 当且仅当<a,b>∈Rn<a,b> \in R^{n}

证明, 数归

连接闭包

R+=R∪R2∪...=t(R)R^{+} = R\cup R^{2} \cup ... = t(R)

Warshall 算法

B = M(R)
for i in 1..n
	for j in 1..n
		if B[j,i]:
        	for k in 1..n
                B[j, k] = B[j, k] && B[i, k]
return B # B == M(R+)

闭包可能会破坏性质吗?

如果R是传递的, s(R)不一定是传递的

其他情况下的三种闭包都不破坏R的原始性质（即自反/对称的R的自反/对称/传递闭包+传递的R的自反闭包不影响R的自反/对称/传递性）

因此, 如果要求R的自反对称传递闭包, 需要最后做传递, 在有传递操作下闭包不是可以任意换序的

  • rs(R) = sr(R)
  • rt(R) = tr(R)
  • st(R) ⊆\subseteq ts(R)

函数：

单值性+定义域内每个都有对应

A->B的函数的个数 ∣AB∣=∣B∣∣A∣,AB:A到B的所有函数的集合|A_B| = |B|^{|A|}, A_B: A到B的所有函数的集合

泛函(functional):

F:A→BcF: A\to B_c

n元运算: An→AA_n \to A

如果一个关系是函数，则它的关系矩阵中每行恰好有一个 1，其余为 0，它的关系图中每个 A 中的顶点恰好发出一条有向边

从∅\varnothing到∅\varnothing的函数只有f=∅f=\varnothing 从∅\varnothing到B的函数只有f=∅f=\varnothing从A到∅A到\varnothing的函数不存在

image-20250114004002823

函数的合成compose 单射的合成还是单射, 满射的合成还是满射

空集到A单射, 空集到空集双射

  • 若 f∘g 是满射的，则 f 是满射的
  • 若 f∘g 是单射的，则 g 是单射的
  • 若 f∘g 是双射的，则 f 是满射的，g 是单射的
  • 理解: (f∘g)(x)=f(g(x))(f \circ g)(x) = f(g(x))

选择公理

对任意一个关系R，存在R的子集作为函数F，且定义域相同

函数的逆

f∘g=IAf \circ g = I_A g是f的右逆，f是g的左逆

有左逆 等价于 单射

有右逆 等价于 满射

都有，则f双射, 且左右逆相同（证明 g (f h) = (g f) h, g=h(关系的合成有结合律)），称为f的逆函数。所以可逆等价于双射

函数的逆不一定是函数, 需要把f−1f^{-1}认为是关系

一个关系的逆不一定是关系，一个函数的逆也不一定是函数

存在双射h等价于 |X| = |Y|

存在单射f: X->Y等价于 |X| <= |Y|

存在单射g: Y->X等价于 |X| >= |Y|

图灵机

自动机

图形表示：终止状态双圈

  • 停在终止状态=接受输入=合法

image-20241222173355989

DFA一定是停机的, 因为输入有限

或者是表格的形式

ab
q0q0q1
*q1q2q1
q2q2q2

第一行a,b是input

第一列q0,q1,q2是状态, *q1指q1是终止状态

中间的矩阵是转移方程

接受一个输入符号+一个状态, 得到下一个状态

拓展转移方程f': 初始状态q0, 转移方程f, 空输入e, 输入a1a2a3...

f'(q0, e) = q0

f'(q0, a1...ai+1) = f'(f(q0, a1...ai), ai+1)

这样就可以递归定义f', 将输入从单个符号变成一串序列

定义L(A)={w∣f′(w)∈F}L(A) = \{w | f'(w) \in F\}, 则称L是这个DFA的语言, 即所有能被DFA接受的输入序列的集合

能被DFA接受的语言: 正则语言

不是正则语言的?

eg 0n1n∣n∈N0^{n}1^{n} | n\in N

图灵机: 输入有磁带

可以修改, 可以回溯

一旦进入accept state就停住

转移函数再加一个左右的方向

图灵机定义的语言: 递归可枚举语言RE

表达能力: P(T) t是dfa, tm, ...

P(DFA)={L∣L∈R}P(DFA)=\{L | L \in R\}

P(TM)={L∣L∈RE}P(TM)=\{L | L \in RE\}

P(DFA)⊆P(TM)P(DFA) \subseteq P(TM)

church-turing thesis: 没有比图灵机更强的计算模型

output of TM

  • reject
  • accept
  • loop

不接受：r/l, 不拒绝：a/l, 停机: r/a

能被TM不停机识别的: 可识别的, RE的子集

Recursive Lauguage: 存在一个TM m使得任意属于L的输入w, 都能在有限步给一个输出(不停机)

又叫图灵可判定的

Regular, R, RE, all language范围逐步增大

特殊的情况

属于R不属于RE: 通用图灵机

bool simulateTM(TM M, string w)

这样的图灵机是不可判定停机的, 否则将自己取反后输入自己, 就推出矛盾了

encoding TM: 可以做到的, 将所有能排序的排序之后, 就可以用1做分隔符, 两个1之间0的个数用于表达符号的编码,这样就可以表达单个状态的转换方程, 再用两个1作为方程的分隔符... => 图灵机可以encode成一个string

所以simulateTM里面TM作为输入是可以的

自指的代码: quine

# Quine
A:
  >>> x='y="x="+repr(x)+"\\n"\nprint (y+x)'
B:
  >>> y="x="+repr(x)+"\n"
  >>> print (y+x)
  x='y="x="+repr(x)+"\\n"\nprint (y+x)'
  y="x="+repr(x)+"\n"
  print (y+x)

所有通用程序本身的非平凡特性都是图灵不可判定的

RE: 正确的输入, 能在有限步骤判定确实正确

不属于RE: 对角线语言, 且无限多个

numbering TMs

将所有图灵机encoding后编号 -> 不是所有数字都有对应的图灵机

没有对应的图灵机的数字可以视为拒绝任何输入的图灵机

所有的string也编号

将所有的图灵机和所有的string构成一张二维表, 每一个格子表示某个图灵机是否能接受这个string

然后取这张表的对角线, 再取反, 这样的语言不能被任意的图灵机接受, 即为非RE的

由于对角线的任意性(只要每个选的行列都不同就行), 所以非RE的语言有无穷多个

对角线语言不是图灵可识别的