主打一个意识流。

2024.01.15 upd: 好像卷面分挺能看的，喜。

Lecture 1

命题

• 陈述句。
• 能判断真假（二值），任何命题的真值是唯一的。
• 悖论不是命题。

$x$ 比 $y$ 大：不是命题，因为 $x,y$ 是变量。
$2050$ 年元旦北京下雪：是命题，但真值待定。

Lecture 2

波兰表达式：画二叉树。

$\uparrow$：与非；$\downarrow$：或非。$\{\uparrow\},\{\downarrow\}$ 都是连接词的完备集。

$n$ 个变元的二值逻辑：$2^{2^n}$ 个 $n$ 元连接词。

Lecture 3

一个简单析取式是重言式 $\Leftrightarrow$ 他同时含有某个命题变项和他的否定式。
一个简单合取式是矛盾式 $\Leftrightarrow$ 他同时含有某个命题变项和他的否定式。

主范式——极小项和极大项

$(\neg P\wedge Q)=m_{1},(P\wedge \neg Q)=m_{2}$。
$(\neg P\vee Q)=M_1,(P\vee \neg Q)=M_2$。

$\bigvee_{S}=\bigwedge_{\{U-S\} 的补}$。

推理演算

• 前提引入规则：推理过程中可随时引入前提；
• 结论引入规则：中间结论可作为后续推理的前提；
• 带入规则：仅限于重言式中的命题变项。
• 置换规则：利用等值公式对部分公式进行置换；
• 分离规则：由 $A$ 与 $A\to B$ 成立，可将 $B$ 分离出来；
• 条件证明规则：$A_1\land A_2\Rightarrow B$ 与 $A_1\Rightarrow A_2\to B$ 等价（前提引入与附加前提引入）

Lecture 4

归结法

• 证 $A\Rightarrow B$ 等价于证 $A\wedge \neg B$ 是矛盾式。
• 将 $A\wedge \neg B$ 化为合取范式，建立子句集。
• 消除互补对，直到出现矛盾式（$\square$）

公理系统

从一些公理出发，根据演绎规则推导出一系列定理。

Russell 公理系统

王浩算法

$A_1,A_2,\cdots\Rightarrow B_1,B_2,\cdots$（$A_1\land A_2\cdots\Rightarrow B_1\lor B_2\cdots$）
反向使用变形规则。

自然演绎系统

附有前提的推理系统，公理集为空集。

• 肯定前提律
• 传递律
• 反证律
• 蕴含词消去律（分离规则）
• 蕴含词引入律

Lecture 5

把命题继续拆分。

谓词

刻画个体词的性质或多个个体词间的关系。

谓词常项：表示具体的性质 / 关系
谓词变项：表示抽象或泛指的性质 / 关系
两者都用 $P,Q,R,\cdots$ 来表示。

（只有 $0$ 个变元的谓词常项 $=$ 命题）

一阶谓词逻辑

量词仅用于个体变项，不允许量词作用于命题变项和谓词变项。

在未指明个体域的时候，应使用总论域，即需要另加一个谓词用于表示个体的性质。

Lecture 6

$(\forall x)(P(x)\to q)=(\exists x)P(x)\to q$
$(\exists x)(P(x)\to q)=(\forall x)P(x)\to q$

$(\forall x)(p\to Q(x))=p\to (\forall x)Q(x)$
$(\exists x)(p\to Q(x))=p\to (\exists x)Q(x)$

$\forall$ 对 $\lor$ 不满足分配律：$(\forall x)P(x)\lor (\forall x)Q(x)\Rightarrow (\forall x)(P(x)\lor Q(x))$
$\exists$ 对 $\land$ 不满足分配律：$(\exists x)(P(x)\land Q(x))\Rightarrow (\exists x)P(x)\land (\exists x)Q(x)$

等值演算规则

• 置换规则

• 换名规则

  • $(\forall x)P(x)\land Q(x)$ 中 $P(x)$ 的 $x$ 是约束的，$Q(x)$ 的 $x$ 是自由的。换为 $(\forall t)P(t)\land Q(x)$ 就可以进一步写为 $(\forall t)(P(t)\land Q(x))$。

• 代替规则

  • 将某个自由出现的个体变项的所有出现用从未出现过的个体变项符号代替。
  • $(\forall x)P(x,y,z)\land (\forall y)Q(y,z)$ 用 $t$ 替换 $y$ 得：$(\forall x)P(x,t,z)\land(\forall y) Q(y,z)$

前束范式

• 所有量词都在公式最左边
• 所有量词都不含否定词
• 量词的辖域延伸到整个公式的末尾

基本步骤：

• 消去蕴含 & 双蕴含
• 右移否定词 $\neg$
• 量词左移
• 变元易名

Skolem 标准型

或叫 “$\forall$ 前束范式”？

前束范式的所有存在量词都在全称量词的左边，且至少有一个存在量词（或仅保留全称量词而消去存在量词）

公式与其 Skolem 标准型 只能保持某种意义（不可满足的意义）下的等值关系

Lecture 7

谓词基本推理公式

• $(\forall x)(P(x)\to Q(x))\Rightarrow (\forall x)P(x)\to (\forall x)Q(x)$
• $(\forall x)(P(x)\to Q(x))\Rightarrow (\exists x)P(x)\to (\exists x)Q(x)$
• $(\exists x)(\forall y)P(x,y)\Rightarrow (\forall y)(\exists x)P(x,y)$ “万人迷”

谓词逻辑推理规则

• UI： $(\forall x)P(x)\Rightarrow P(c)$ 当 $c\in U$；
• UG："任意的 $c\in U$ 有 $P(c)$" $\Rightarrow (\forall x)P(x)$；
• EI：$(\exists x)P(x)\Rightarrow P(c)$，对某一个 $c$；
• EG：“对某些 $c\in U$ 有 $P(c)$“ $\Rightarrow (\exists x)P(x)$。

公式的普遍有效性和不可满足性

普遍有效：在任何解释下真值均为真；
不可满足：在任何解释下真值均为假。
“任何解释”：个体域给定：自由个体变项、谓词变项、函数（都任意）

Lecture 8

啥也没有。
哦，有个 $H=\{ x\mid x\notin x\}$。

Lecture 9

$P(A)\in P(B)\Rightarrow A\in B$（不是双向箭头）

$$ \begin{aligned} P(A)\in P(B)&\Leftrightarrow P(A)\subset B\\ &\Leftrightarrow P(A)\subset B \land A\in P(A)\\ &\Rightarrow A\in B\\ \end{aligned} $$

$P(A)\cap P(B)=P(A\cap B), P(A)\cup P(B)\subset P(A\cup B)$

传递集合

$A$ 是传递集合 $\Leftrightarrow$ $(\forall x)(\forall y)((x\in y \land y\in A)\to x\in A)$
故有：$x\in A\Rightarrow x\subset A$
$A$ 是传递集合 $\Leftrightarrow$ $P(A)$ 是传递集合
$\bigcup (P(A))=A$，但 $P(\bigcup A)\ne A$。

ZFC 集合论公理系统

• 外延公理：两个集合相等 $\Leftrightarrow$ 他们具有相同的元素（一个集合由其元素唯一确定）
• 空集存在公理：$(\exists x)(\forall y)(y\notin x)$。
• 无序对集合存在公理：对任意集合 $x,y$，存在一个集合 $z$ 的元素恰好是 $x$ 和 $y$。
• 并集合存在公理：对任意集合 $x$，存在一个集合 $y$ 的元素恰好是 $x$ 中元素的元素。
• 子集公理模式：对任意谓词公式 $P(z)$ 和任意集合 $x$，存在一个集合 $y$ 的所有元素 $z$ 既是 $x$ 的元素，又使 $P(z)$ 为真。
• 幂集合公理：对于任意集合 $x$，存在一个集合 $y$ 的元素恰好是 $x$ 的子集。
• 正则公理：对任意的非空集合 $x$，存在一个 $x$ 的元素和 $x$ 无交。$(\forall x)(x\ne \varnothing\to (\exists y)(y\in x\land y\cap x=\varnothing))$。称该元素为集合 $x$ 的极小元，每个非空集合都有极小元。“所有集都是良序集”
• 选择替换公理：对任意集合 $x$ 和定义在 $x$ 上的函数 $g$，存在集合 $y=g(x)$。
• (AC) 选择公理：对任意集合 $x$ ，存在以 $x$ 为定义域的函数 $g$，使得 $(\forall y)(y\in x\to g(y)\in y)$。

子集公理模式的细节

“不能直接用谓词来概括集合的组成，而是要经过分离”

Russell 悖论：$H=\{x\mid x\notin x\}$ 只能从万有集 $+P(x)=(x\notin x)$ 分离得到。ZFC 公理系统中的“万有集不存在定理”是通过构造 Russell 悖论的集合得出的，接着又反推出在 ZFC 公理系统中不会有 Russell 悖论。

注：$\bigcap \varnothing$ 不存在，因为这就相当于“万有集”。

Lecture 10

$\operatorname{dom}(R)$：关系 $R$ 的定义域；$\operatorname{ran}(R)$：关系 $R$ 的值域。
$\operatorname{fld}(R)=\text{dom}(R)\cup\text{ran}(R)$：关系 $R$ 的域。

关系图：$<x,y>\in R$，关系图中有有向边 $x\to y$。

“$R$ 和 $S$ 的复合”：先 $R$ 后 $S$，记作 $S\circ R$（记号中从右往左）
$R\uparrow A$：把 $R$ 的定义域限制在 $A$ 上
$R[A]$：$\text{ran}(R\uparrow A)$

Lecture 11

集合的“后继”：$A^+=A\cup \{A\}$。
$n+1=n^+=\{0,1,2,\cdots, n\}$，$\bigcup n=n-1$。

Lecture 12

关系的性质

• 自反、非自反（可以同时不是自反，也不是非自反）
• 对称；
• 反对称：$xRy\land yRx\to x=y$。
• 传递；

闭包

$R$ 是有限集合 $A$ 上的关系，$|A|=n$，则存在 $s\ne t$ 有 $R^s=R^t$（抽屉原理）

$r(R)$：自反闭包；
$s(R)$：对称闭包；
$t(R)$：传递闭包；

• $R$ 是自反的，$s(R),t(R)$ 也自反
• $R$ 是对称的，$r(R),t(R)$ 也对称
• $R$ 是传递的，$r(R)$ 也是传递的，但 $s(R)$ 不一定（$R=\{<1,3>,<2,3>\}$）
• $rs(R)=sr(R)$
• $rt(R)=tr(R)$
• $st(R)\subseteq ts(R)$！！

Lecture 13

相容关系

如果 $R$ 是自反的、对称的（无需传递），则 $R$ 是相容关系。

相容类：$\forall x, y\in C, xRy$，其中 $R$ 是相容关系。（团）
最大相容类：其实就是“极大”，极大团。

覆盖

一堆 $A$ 的非空子集，并起来是 $A$，就是 $A$ 的一组覆盖。
完全覆盖：所有最大相容类，记作 $C_R(A)$，显然唯一。

偏序关系

如果 $R$ 是自反的、反对称的、传递的，则 $R$ 是偏序关系。

集合 $A$ 和 $A$ 上的偏序关系 $R$ 称作偏序集 $<A,R>$。

拟序关系

如果 $R$ 是非自反的、传递的，则 $R$ 是拟序关系。

可以推出反对称。

盖住关系

偏序集 $<A,\le>$，如果 $x\le y$ 且没有 $z$ 使得 $x\le z\land z\le y$，则 $y$ 盖住 $x$。$<x,y>\in \operatorname{cov}A$。

哈斯图

$<x,y>\in\operatorname{cov} A$，$y$ 画上面，$x$ 画下面，忽略自环。

特殊元素

最大元、最小元（不一定存在，存在不一定唯一）
极大元、极小元（对有限集一定存在，但不一定唯一）
上界、下界（针对 $B\subseteq A$ 而言，但不一定在 $B$ 中）
上确界 $\sup(B)$、下确界 $\inf(B)$（不一定存在，存在一定唯一）

全序关系

任意 $x,y$ 都可比的偏序关系。

Lecture 14

列表法、图像法、解析法

$A\to B$ 的函数 $f$ 要求 $\operatorname{dom}(f)=A$，但 $\operatorname{ran}(f)\subseteq B$ 就行。
$A_B=\{f\mid f:A\to B\},|A_B|=|B|^{|A|}$。

象：$A_1\subseteq A, f[A_1]$。
完全原象：$B_1\subseteq B,f^{-1}[B_1]=\{x\mid x\in A\land f(x)\in B_1\}$。

满射：$\operatorname{ran}(f)=B$。
单射、双射：懂得都懂。

常函数、恒等函数、单调函数

$n$ 元运算：$f:A^n\to A$。
泛函：$A,B,C$ 是集合，$F:A\to B_C$ 称作一个泛函。
例如 $F:R\to R_R, F(a)=(f(x)=x+a)$，是一个泛函。
$A$ 到 $A/R$ 的典型映射 / 自然映射：$g(a)=[a]_R$。

选择公理：

对任意关系 $R$，存在函数 $f$ 使得 $\operatorname{dom}(f)=\operatorname{dom}(R)$。

如果 $g\circ f=I_A$（先 $f$ 后 $g$！！！），则 $g$ 是 $f$ 的左逆，同理有右逆。

相容性：$f:A\to B,g:C\to D$，$\forall x\in (A\cap C)$ 有 $f(x)=g(x)$，就称 $f,g$ 相容。
函数集的相容：函数两两相容。相容的函数集可以构造一个新函数。

关系和函数的相容性：$f:A\to A,R$ 是 $A$ 上的等价关系，$<x,y>\in R\to <f(x),f(y)>\in R$，就称关系 $R$ 和函数 $f$ 相容。

模糊子集

不会真有人看吧？不会真考吧（

Lecture 15

自然数集合 $\mathbb{N}$

$n+1=n^+=\{0,1,\cdots,n\}$

整数集合 $\mathbb{Z}$

$\mathbb{Z}_+=\mathbb{N}-\{0\},\mathbb{Z}_-=\{<0,n>\mid n\in \mathbb{Z}_+\},\mathbb{Z}=\mathbb{Z}_+\cup \{0\}\cup\mathbb{Z}_-$。

有理数集合 $\mathbb{Q}$

$\mathbb{Q}_1=\mathbb{Z}\times(\mathbb{Z}-\{0\})$。定义 $<a,b>\cong <c,d>$ 当且仅当 $ad=bc$。
然后 $\mathbb{Q}=\mathbb{Q}_1/\cong$。

实数集合 $\mathbb{R}$

若 $f:\mathbb{N}\to \mathbb{Q}$ 有界、单调非递减，称 $f$ 是一个基本函数。
对于基本函数的集合 $\mathbb{B}$，定义 $\mathbb{B}$ 上的关系 $\cong$，$f\cong g$ 当且仅当 $f,g$ 的极限相同。

$\mathbb{R}=\mathbb{B}/\cong$。

等势

$\neg \mathbb{N}\approx \mathbb{R}$：对角线方法。
$\neg A\approx P(A)$。

基数

对基数 $k,l$，$k\le l$ 且 $l$ 是无限基数，则：

$$ k+l=k\cdot l=l=\max(k,l) $$

$\aleph_0$ 是最小的无限基数。
一个例子：

$$ 2^{\aleph_0}\le \aleph_0\cdot 2^{\aleph_0}\le 2^{\aleph_0}\cdot 2^{\aleph_0}=2^{\aleph_0} $$

所以 $\aleph_0\cdot 2^{\aleph_0}=2^{\aleph_0}$。
对无限基数 $k$，有 $k^k=2^k$：

$$ 2^k\le k^k\le (2^k)^k=2^{k\cdot k}=2^k $$

连续统假设

懂得都懂。