基础知识

官官方信息技术老师·23 页·深入（追求细节与边界）·0 次浏览·2 天前
✦ 基础知识信息技术基础知识图
数学基础大模型图解原理

软件理论基础：基础知识

看完一组图，能说清大语言模型为什么必须靠矩阵、概率与注意力这三件套

按 空格/→ 演示下一步

1 / 23 页

全部页面点击任意一页，跳回舞台从这页播放

数学基础大模型图解原理

软件理论基础：基础知识

看完一组图，能说清大语言模型为什么必须靠矩阵、概率与注意力这三件套

1第 1 页 · 软件理论基础：基础知识

集合与元素

代码里写枚举类型、把状态列成一组常量——这些动作背后都在用「集合」的思想。集合论是软件理论最底层的语言，先把它讲清楚。

集合
把确定对象的全体视为一个整体，记作大写字母，如 A、B
元素
集合中的每个对象，用 x ∈ A 表示「x 属于 A」
子集
A 的每个元素都属于 B，记作 A ⊆ B；空集 ⊆ 任意集合
三大特性
确定性、互异性、无序性；任一不满足就不是合法集合
数据库表的查询结果对应 →集合与子集

一张表是一个集合，每行是元素；SELECT WHERE 的返回结果就是原表的子集

A⊆B  ⟺  ∀x (x∈A⇒x∈B)A \subseteq B \iff \forall x \, (x \in A \Rightarrow x \in B)
2第 2 页 · 集合与元素

集合运算

上一页我们认识了集合——把元素装进一个袋子里。如果有两个袋子，它们里的元素可以怎么组合？这就需要四种基本运算：并、交、补、差。

并集 A∪B
属于 A 或属于 B 的全部元素；A∪A=A，集合与自身并集不变
交集 A∩B
既属于 A 又属于 B 的元素；A∩∅=∅，与空集交集恒为空
补集 Ā
在全集 U 中不属于 A 的元素；A∪Ā=U，A∩Ā=∅
差集 A−B
属于 A 但不属于 B 的元素；A−B≠B−A，不满足交换律
选课名单对应 →集合运算

至少选一门=并集；两门都选=交集；全班没选=补集；只选A不选B=差集

A∪B={x∣x∈A 或 x∈B},A∩B={x∣x∈A 且 x∈B},A‾={x∈U∣x∉A},A−B={x∈A∣x∉B}A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}, \quad A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}, \quad \overline{A} = \{x \in U \mid x \notin A\}, \quad A - B = \{x \in A \mid x \notin B\}
3第 3 页 · 集合运算

关系

集合运算回答了「如何合并/筛选元素」，但实际中我们更关心元素之间的联系——比如「A 是 B 的朋友」「x ≤ y」。这种「谁和谁有这层联系」的描述，就是关系。

二元关系
从集合 A×B 中挑出的子集，每个 (a,b) 代表一对联系
自反性
每个元素都和自己有这层关系：∀a, (a,a) ∈ R
对称性
关系是双向的：(a,b) ∈ R ⇒ (b,a) ∈ R
传递性
能「接力」：(a,b),(b,c) ∈ R ⇒ (a,c) ∈ R
微信好友圈对应 →二元关系三性质

加自己=自反、互加=对称、A→B→C 推出 A→C=传递

R⊆A×B自反:∀a, (a,a)∈R对称:(a,b)∈R⇒(b,a)∈R传递:(a,b),(b,c)∈R⇒(a,c)∈R\begin{aligned} R &\subseteq A \times B \\ \text{自反} &: \forall a,\ (a,a)\in R \\ \text{对称} &: (a,b)\in R \Rightarrow (b,a)\in R \\ \text{传递} &: (a,b),(b,c)\in R \Rightarrow (a,c)\in R \end{aligned}
4第 4 页 · 关系

函数

映射、单射、满射、双射

函数
映射、单射、满射、双射
5第 5 页 · 函数

图的基本概念

上一页讲过，关系是有序对的集合。当这种有序对多起来、结构交织，单纯列举就让人眼花。于是数学家换了一种画法：把元素画成点，把配对画成连线，让结构一眼可读。这就是「图」。

顶点
图中的基本单元，对应集合里的一个元素
边
连接两个顶点，对应关系中的一个有序对或无序对
无向图
边不带方向，两个顶点间的关系是双向的
有向图
边带方向，用箭头表示，关系不对称
边界情况
自环是连回自身的边；重边是同一对顶点间的多条边
城市路网地图对应 →图的基本结构

路口是顶点，道路是边；双向路对应无向边，单行道对应有向边

$G = (V, E)$，其中 $V$ 为顶点集合，$E$ 为边集合
6第 6 页 · 图的基本概念

图的表示方法

同一张示例图，左矩阵右表，对比空间与查询复杂度。

图解渲染中…
G：示例图：5 个顶点、6 条无向边M1：V=顶点数，O(·) 描述规模增长L2：查某点所有邻居 = 该点的度数CH：汇总两类结构的权衡，给出取舍
7第 7 页 · 图的表示方法

路径与环

上页我们把图存进了电脑。现在想象你站在某个路口，沿街道走到朋友家——这一路的路口与路段，就是图论里最基本的「通路」。

通路 (Walk)
顶点与边均可重复出现，是最宽松的「走过」
迹 (Trail)
边不可重复，但顶点仍可重复访问
简单路径 (Path)
顶点互不重复（边也随之不重复）
回路 (Cycle)
起点与终点重合的简单路径；简单图中长度 ≥ 3
走街串巷对应 →通路与回路

通路可回头走、简单路径每条街只走一次；回路是起点终点重合的环线

$W = v_0 \to v_1 \to \cdots \to v_k$，$(v_i, v_{i+1}) \in E$；简单路径：$v_i \neq v_j$；回路：$v_0 = v_k$
8第 8 页 · 路径与环

图的连通性

上一节我们认识了路径和环。一个自然的问题是：图里任意两个顶点之间，是不是都能找到一条路走到？这个「能不能互相到达」的问题，就是图的连通性。

连通图
无向图中任意两顶点之间都存在路径
连通分量
无向图中的极大连通子图
强连通
有向图中两顶点可互相到达
强连通分量
有向图中的极大强连通子图
弱连通
忽略方向后是连通的，但并非强连通
现实中的公路网对应 →图的连通性

双向公路像无向图，单行道像有向图；省级之间各通各的，对应连通分量

$$\forall u,v \in V:\ u \rightsquigarrow v \land v \rightsquigarrow u$$
9第 9 页 · 图的连通性

直接证明法

调试时一行行追代码：从入口（前提）出发，每条语句执行一次，看到中间状态，直到输出（结论）。直接证明正是这种「正向走法」——承认前提，按规则一步步推到底。

前提
推理起点，被假定为真的命题
推理规则
保证「从 A 可得 B」的合法规则
中间命题
逐步推导产生的过渡语句，串成推导链
目标结论
推导链末端必须落到的命题 Q
程序从入口跑到出口对应 →直接证明的推导

输入对应前提，每条语句是一次推理，最终输出对应结论

P1,P2,…,Pn⊢QP_1, P_2, \ldots, P_n \vdash Q
10第 10 页 · 直接证明法

反证法

上页的直接证明,是顺着前提一步步推结论。可有些命题这条路走不通——比如证明'√2是无理数'。今天换一种思路:把要证的话反过来假设,看能不能推出矛盾。

设立反假设
假设原结论不成立,即取其否定作为推理起点
演绎推导
从反假设和已知条件出发,按逻辑规则一直推
撞上矛盾
推出的结果与公理、已知或反假设自身冲突
否定反假设
矛盾说明反假设错,原命题反而得以成立
假设今天不下雨对应 →反证法的反假设

查天气预报说有暴雨,与假设直接冲突,反假设被推翻,推出今天会下雨

¬P⇒Q∧¬Q⊢P\neg P \Rightarrow Q \land \neg Q \vdash P
11第 11 页 · 反证法

数学归纳法

数学归纳法分三步：先打地基，再做假设，最后完成递推，让结论从最小值传到所有自然数。

1
基础步
验证命题在最小值 n₀（常取 1）时成立
2
归纳假设
假设命题对某个任意大的 k 成立
3
归纳步
由 k 成立推出 k+1 也成立
12第 12 页 · 数学归纳法

证明方法对比

直接证和反证都能证一般性命题，但推理方向相反。看到题目该选哪个？这页给出判断标准。

直接证明法
  • 起点：已知条件；方向：顺向推导
  • 结构：P → 中间结论 → Q，逐层推进
  • 适合：因果链路清晰、可直接构造
  • 信号词：「因为……所以……」
反证法
  • 起点：假设结论不成立；方向：推出矛盾
  • 结构：¬Q → 推出矛盾 → ¬Q 不成立
  • 适合：正面难推进、或命题含否定词
  • 信号词：「假设……不成立，……矛盾」
因果清晰、正面可达→直接证；含「不存在/不可能」或正面卡壳→反证。归纳法留给「自然数序列」，别凑数。
13第 13 页 · 证明方法对比

字母表

前面用集合描述元素、用图刻画关系。现在要搭形式语言的第一块砖：所有合法字符串由哪些「原料」拼出来？这个原料库就叫做字母表——而它必须是有穷的，把这条限制拿掉，自动机理论就站不住脚。

字母表：有穷非空符号集
互不相同、不可再分的符号构成的有限集合，记为 Σ；空集不算字母表
符号的原子性
符号是构造字符串的最底层单位，不允许再拆分
字符串由符号拼接
Σ 上的字符串是 0 个或多个符号的有序拼接
有限性是理论基石
若字母表无穷（如 ℕ），自动机无法枚举，理论根本性变化
拼音声母韵母表对应 →字母表 Σ

23 声母 + 39 韵母 = 有限集合；一个汉字的拼音 = Σ 上的一个字符串

Σ∗=⋃n=0∞Σn, Σ0={ε}\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n,\ \Sigma^0 = \{\varepsilon\}
14第 14 页 · 字母表

字符串

上一页认识了字母表 Σ——所有可用符号的集合。但光有符号还不够，得把它们按顺序排成队，才有「内容」。字符串，就是这样一队排好的符号。

字符串
字母表 Σ 上符号的有序有限序列，记作 w 或 s
长度 |w|
字符串 w 中符号的个数，例如 |abc|=3
空串 ε
长度为 0 的唯一字符串，任何字母表上都存在
Kleene 闭包 Σ*
Σ 上所有字符串（含 ε）的集合，自动机的舞台
一列玩具火车对应 →字符串

车厢=符号，按顺序挂好，节数=长度；空串就是没有车厢的空轨道

Σ∗=⋃n=0∞Σn\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n
15第 15 页 · 字符串

语言

上一页我们看了字符串——字母表上单个的串。这一页把视角拉远：把「所有合法的字符串」聚成一个集合，这个集合就是语言。所有标识符、所有合法 C 程序、所有英文单词，统统都是语言。

形式定义
语言 L 是字母表 Σ 上的字符串集合，即 L ⊆ Σ*
两个边界
∅（空语言，不含任何串）≠ {ε}（只含空串的语言），初学者常混
基数性质
Σ* 可数无穷，但其子集有 2^ℵ₀ 个——字母表上语言有不可数个
直观例子
偶数长度的串、C 合法标识符、合法的 C 程序，都是语言
一本英汉词典对应 →语言 L

词条是字符串，整本词典收录的词条集合就是语言；词典是数学对象，不只是纸书

L⊆Σ∗L \subseteq \Sigma^{*}
16第 16 页 · 语言

字符串运算

从输入串出发，按"缩短"或"合并"两类运算得到新串——箭头表示数据流向。

图解渲染中…
p：形式定义：prefix(s,k) = s[0..k-1]suf：形式定义：suffix(s,k) = s[|s|-k..|s|-1]sub：形式定义：sub(s,i,j) = s[i..j-1]c：形式定义：concatenate(s,t) = s·t
17第 17 页 · 字符串运算

语言的并与交

上一节我们认识了字符串的拼接和幂，而语言本身就是字符串的集合。两个语言之间能不能也做并和交？答案是自然的——集合运算直接延伸到语言上。

语言即集合
语言 L 是 Σ* 的子集，所有集合运算天然适用
并集 L₁∪L₂
{w | w∈L₁ 或 w∈L₂}，属于任一语言就算
交集 L₁∩L₂
{w | w∈L₁ 且 w∈L₂}，必须两语言都收
边界：先约定字母表
Σ 未定时'全集'与'补集'无定义，De Morgan 等定律需谨慎使用
两份歌单 A 与 B对应 →语言的并与交

歌单就是字符串集合；并=合并去重，交=两边都收藏的那几首

L1∪L2={w∣w∈L1∨w∈L2},L1∩L2={w∣w∈L1∧w∈L2}L_1 \cup L_2 = \{ w \mid w \in L_1 \lor w \in L_2 \},\quad L_1 \cap L_2 = \{ w \mid w \in L_1 \land w \in L_2 \}
18第 18 页 · 语言的并与交

语言的连接

上一页用并和交把两个语言合在一起——但那些操作只触及单个串本身。若想把一个语言的串和另一个语言的串首尾相接，就需要「语言的连接」。

定义
L1L2 = {xy : x∈L1, y∈L2}，两语言中所有串首尾拼接的结果
不满足交换律
一般 L1L2 ≠ L2L1，串的先后顺序决定结果语言
单位元是 {ε}
L·{ε} = {ε}·L = L，空串语言充当连接的单位元
形容词集 + 名词集对应 →语言的连接

把形容集与名词集里的词两两首尾拼接，所有「形+名」组合就构成新集合

L1L2={xy∣x∈L1,  y∈L2}L_1 L_2 = \{ xy \mid x \in L_1,\; y \in L_2 \}
19第 19 页 · 语言的连接

语言的幂运算

上次学了语言连接：把两个语言里的串首尾相接。那如果把一个语言 L 和自己拼接呢？接一次是 L·L，接两次是 L·L·L，连续接 n 次——这叫语言的幂，记作 L^n。

核心定义
L^n = L·L·...·L，n 个 L 首尾相连得到的语言
零次幂 L^0 = {ε}
约定空次自连接为只含空串，与乘法 2^0 = 1 平行
递归递推
L^(n+1) = L^n · L，每次右端再连一个 L
计算示例
L = {a, bc} 时 L^2 = {aa, abc, bca, bcbc}
易混：字符串幂 vs 语言幂
s^n 把一个串重复；L^n 从 L 取 n 个串拼接
数学里的 2³ = 2×2×2对应 →语言里的 L³ = L·L·L

数字换成集合，「乘法」换成「连接」，主体始终是同一个 L

L0={ε},Ln+1=Ln⋅LL^0 = \{\varepsilon\}, \quad L^{n+1} = L^n \cdot L
20第 20 页 · 语言的幂运算

语言的闭包

上一页我们让 L 与自身连接 n 次得到 L^n。现在把 n 放开：若 n 可以是 0、1、2、…，结果叫 L*；若 n 至少是 1，结果叫 L+。两者只差一点点。

L*（Kleene 闭包）
L 与自身连接 0 次或多次，结果必含空串 ε
L+（正闭包）
L 与自身连接 1 次或多次，结果不含空串
核心关系
L+ = L* − {ε}，等价于 L* = L⁰ ∪ L+
边界情形
若 ε ∈ L，则 L⁰ ⊆ L¹，从而 L* = L+
串糖葫芦对应 →L* 与 L+

L* 允许一根光秃秃的竹签（连接 0 次），L+ 至少串上一颗山楂

L∗=⋃i≥0Li,L+=⋃i≥1Li,L+=L∗∖{ε}L^* = \bigcup_{i \geq 0} L^i,\quad L^+ = \bigcup_{i \geq 1} L^i,\quad L^+ = L^* \setminus \{\varepsilon\}
21第 21 页 · 语言的闭包

基础概念自测

点击作答

设字母表 Σ={a,b}，下列关于"语言"的描述，哪一项一定正确？

22第 22 页 · 基础概念自测

课后思考

先独立思考每个问题，再对照参考答案的思路。每个问题都值得多琢磨几分钟。

1为什么我们要把'关系'从'集合'中单独抽出来？仅用集合在什么场景下不足以描述问题？

参考答案集合只回答'有什么'，关系回答'之间怎么连'。描述一个班级，集合列出所有学生，但谁和谁是朋友、成绩谁高谁低，必须用关系刻画。函数也是关系的一种特殊形式。

2若用图描述一个校园导航系统，顶点集和边集分别如何定义？路径与连通性各对应什么？

参考答案顶点集可以是每栋楼或每个路口，边集是道路（带权即距离）。路径对应'从A到B怎么走'，连通性对应'任意两点是否可达'。图不连通意味着存在孤立的建筑群。

3数学归纳法在离散问题中很强，但遇到无穷结构（如无穷集合上的关系）时还能直接套用吗？边界在哪？

参考答案标准归纳法依赖自然数的良序性。遇到无穷集合或关系，要么改用超限归纳法，要么先把问题归约到有限可枚举结构。归纳根基必须可枚举、归纳步必须对所有元素成立，两者缺一不可。

23第 23 页 · 课后思考