离散数学（2024）
Chapter1 命题逻辑
推理过程正确性的保障需要 数学(具体而言是数理逻辑)的支持,数理逻辑基础包括： 命题逻辑和谓词逻辑
符号逻辑的语义
命题
一个陈述事实的能够判断出真假的语句
例题：判断句子是否为命题？
命题变元
常用小写字母表示（p q r …）,取值范围为:{T,F} ({1,0})
命题可以表示为命题变元的形式，可以理解为该变元“已经赋值”。命题逻辑只关注命题真假，即语义只有 0or1,与自然语言表达的内容没有关系。
符号逻辑的语法
命题符号化
命题的唯一真假值称为 “真值”, 最小的命题单位称作 “原子命题”, 原子命题通过基本的逻辑运算符(联结词) 组合称为 “复合命题”。
命题表达式
合式公式
命题符号化的结果是合式公式*(每个命题都可以化作一个公式)*，是命题“语言”中的“句子”。
递归定义:
使用非、或、且、蕴含和等价生成的在有限步中生成的公式。
公式的表示：
含$n$个原子$P1, P2, . . . , Pn$的公式$G$记为$G(P1, P2, . . . , Pn)$
指派
对公式$G(P1, P2, . . . , Pn)$中的所有原子$P1, P2, . . . , Pn$的一次取值$⟨x1, x2, . . . , xn⟩, xi ∈ {0, 1}$称为一个指派。
对一个指派$I$可将其记做$I = x1x2 …xn$。
命题变元
命题变元 (用大写字母表示) 就是命题表达式
联结词
$n$个原子的公式共有$2^{2^n}$个不同的运算。
$2^{n}$原子及其取反的排列。
基础联结词
| 名称 | Note | 符号 | 解释 |
|---|---|---|---|
| 否定词 | 单纯的取反 | $\neg p$ | 非 $p$ ，否定 $p$ |
| 析取词 | “或”,需要注意与自然语言中"或者"的区别,我中午吃饭"或者"吃面中的"或者"是异或 xor。 | $p \vee q$ | $p$ 或者 $q$ (兼或) |
| 合取词 | 并且 | $p \wedge q$ | $p$ 并且 $q$ |
| 蕴含词 | $P$ 蕴含$Q$中 $P$是前提,$Q$是结论(后件)可以看作"契约"(ex:总统竞选的承诺)$p$仅当$q$ $q$当$p$ $q$每当$q$ $p$蕴含$q$ | $p \rightarrow q$ | 如果 $p$ ，则 $q$ $p$ 是 $q$ 的充分条件 $q$ 是 $p$ 的必要条件 $p$ 是前提， $q$ 是结论当 $p$, 则 $q$ (仅当 $q$, 有 $p$ ) |
| 等值词 | 你吃完饭就可以吃甜点…是蕴含还是等值？iff | $p \leftrightarrow q$ | $p$ 等值于 $q$ $p$ 是 $q$ 的充分必要条件 $p$ 当且仅当 $q$ |
运算的优先级: $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$
拓展联结词
与非、或非、异或等
| 与非(NAND) | 或非(NOR) | 异或(XOR) | ||
|---|---|---|---|---|
| $P$ | $Q$ | $P \uparrow Q$$\neg(P \wedge Q)$ | $P \downarrow Q$$\neg(P \vee Q)$ | $P \oplus Q$$(P \wedge \neg Q) \vee(\neg P \wedge Q)$ |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 |
上与下或圈异或
各种位运算
全功能集
所有的运算均能用该集合中的联结词表示的一个联结词的集合,${ ¬, ∧, ∨ }$是全功能的,${ ¬, → }$是极小全功能的。
如何判断一个联结词集合是否是全功能的？
- ${ ¬, ↔ }$不是全功能的，因为$↔ + ¬$永远只能有 8 个公式：通过 CCNF 的数量判断
- ${ ∧, ∨ }$不是全功能的，因为$∧ + ∨$的组合中对每个原子都取真值的指派只能取真：通过取值方法判断
如何证明一个联结词集合是全功能的？
- $P ↓ Q ⇔ ¬P ∨ Q;$
- $¬P ⇔ P ↓ P$
- $P→Q ⇔ ¬P ∨ Q⇔ ¬¬((P ↓ P)∨Q) ⇔ ¬((P ↓ P) ↓ Q) ⇔ ((P ↓ P) ↓ Q) ↓ ((P ↓ P) ↓ Q)$
只要证明出$↓$能够表示出${ ¬, → }$,那么它就是全功能的。
逻辑等价
逻辑等价的定义
若公式$(F) ↔ (G)$是重言式,则称公式$F$和$G$逻辑等价。
逻辑等价记为$F ⇔ G$。
如果对$G$的任意一个指派 I$, 都有$I(G) = 1$, 称$G$为重言式。
如果存在$G$的一个指派$I$, 有$I(G) = 1$, 称 G 为可满足式。
如果对$G$的任意一个指派$I$, 都有$I(G) = 0$, 称$G$为矛盾式。
永真蕴含关系
若公式$(F) → (G)$是重言式,则称公式$F$永真蕴含公式$G$（ $F ⇒ G$）
常见的逻辑等价
| 名称 | 等价关系 |
|---|---|
| 交换律 | $p \vee q \equiv q \vee p，p \wedge q \equiv q \wedge p$ |
| 结合律 | $(p \vee q) \vee r \equiv p \vee(q \vee r)，(p \wedge q) \wedge r \equiv p \wedge(q \wedge r)$ |
| 分配律 | $p \vee(q \wedge r) \equiv(p \vee q) \wedge(p \vee r)，p \wedge(q \vee r) \equiv(p \wedge q) \vee(p \wedge r)$ |
| 德摩根律 | $\neg(p \vee q) \equiv \neg p \wedge \neg q，\neg(p \wedge q) \equiv \neg p \vee \neg q$ |
| 吸收律 | $p \vee(p \wedge q) \equiv p ，p \wedge(p \vee q) \equiv p$ |
| 排中律 | ${A} \vee \neg {A} \equiv {1}$ |
| 假言易位 | ${A} \rightarrow {B} \equiv \neg {B} \rightarrow \neg {A}，{A \leftrightarrow B} \equiv \neg {B} \leftrightarrow \neg {A}$ |
| 归缪论 | $( A \rightarrow { B } ) \wedge ( { A } \rightarrow \neg { B } ) \equiv \neg { A }$ |
| 蕴含 | $ {A} \rightarrow {B} \equiv \neg {A} \vee {B}， {A \leftrightarrow { B } \equiv ( { A } \rightarrow { B } ) \wedge ( { B } \rightarrow { A } )}$ |
证明中常用到的: $p \wedge q \rightarrow r \equiv p \rightarrow(q \rightarrow r)$
范式
公式的标准化表达
析取范式(DNF)
一个形为基本积(变元或变元的否定的且)的析取的公式, 若与命题公式 A 等价, 则称其为公式 A 的析取范式。
思想:只要不碰到为假的取值,那么这个公式就是真的。
**如何判断一个公式 trueorfalse？**变成 DNF 再判断？——理论上可行,但实际上没有这么大计算能力。
析取范式的求解:
- 消去联结词
- 利用德摩根律消去多元否定和双重否定
- 利用分配结合律等，将公式化为多个基本积相或的析取范式
合取范式(CNF)
一个形为基本和(变元或变元的否定的或)的合取的公式, 若与命题公式 A 等价, 则称其为公式 A 的合取范式。
注意:公式的析取范式和合取范式均不唯一。
可满足性问题(SAT 问题):
什么是 NP 问题? P 问题指的是多项式的计算过程(非指数问题),耗费时间增长较慢的问题——例如一个数学问题,你把它解出来的时间。
**NP:**Nondeter-P 不确定的 P 问题——例如一个数学问题的答案,你把这个答案理解的时间。
图灵机的计算可以 model 为一个 SAT 问题——NP-complete 存在
Example:八皇后 👑
主析取范式(CDNF)
由极小项之和组成与公式 A 逻辑等价的公式称之为公式 A 的主析取范式
极小项:
对于每个极小项, 有且仅有一个指派使之真值为真,下标为用使极小项为真的指派对应的数字。
主析取范式的求解:
先化为析取范式
去掉析取范式中永假的基本积
合并相同变元和基本积
补入未出现的变元
主析取范式的个数:
$2^{2^n}$个（极小项的某一原子是否为真+主析取范式是否含有极小项）
主合取范式(CCNF)
由极大项之积组成与公式 A 逻辑等价的公式称之为公式 A 的主合取范式
极小项:
对于每个极大项, 有且仅有一个指派使之真值为假,下标为用使极大项为假的指派对应的数字。
极大项的否定是极小项
前束范式(PNF)
推理 证明方法
如何推理？
等值演算
$$ \begin{aligned} & {p} \rightarrow({q} \rightarrow {r}) \ & \Leftrightarrow {p} \rightarrow(\neg {q} \vee {r}) \text { (蕴涵等值式,置换规则) } \ & \Leftrightarrow \neg {p} \vee(\neg q \vee v) \ & \Leftrightarrow(\neg \mathrm{p} \vee \neg \mathrm{q}) \vee \mathrm{r} \quad \text { (结合律) } \ & \Leftrightarrow \neg({p} \wedge {q}) \vee {r} \quad \text { (德•摩根律) } \ & \Leftrightarrow({p} \wedge {q}) \rightarrow {r} \quad \text { (蕴涵等值式) } \end{aligned} $$
蕴含运算没有结合律
AI:命题符号化再推演,但公式数量特别多,存在指数爆炸的问题,理论上计算机可以通过这个方法推演,但实际上很慢。
推理的形式结构
- 前提: $A1，A2，…，Ak$
- 结论: $B$
- 推理的形式结构: $(A1\wedge A2 \wedge A3 \wedge … \wedge Ak)\rightarrow B$
常用的定律和公式
常用的逻辑等价式
常用的永真蕴含式(重要的推理定律)
| $P \Rightarrow P \vee Q$ | 加法式 |
|---|---|
| $P \wedge Q \Rightarrow P$ | 简化式 |
| $(P \rightarrow Q) \wedge P \Rightarrow Q$ | 假言推理 |
| $(P \rightarrow Q) \wedge \neg Q \Rightarrow \neg p$ | 拒取式 |
| $(P \vee Q) \wedge \neg P \Rightarrow Q$ | 析取三段论 |
| $(P \rightarrow Q) \wedge(Q \rightarrow R) \Rightarrow(P \rightarrow R)$ | 前提三段论 |
| $(P \rightarrow Q) \Rightarrow(Q \rightarrow R) \rightarrow(P \rightarrow R)$ | |
| $(P \rightarrow Q) \wedge(R \rightarrow S) \Rightarrow(P \wedge R) \rightarrow(Q \wedge S)$ | |
| $(P → Q)∧(R → S)∧(P∨R) ⇒Q∨S$ | 构造性二难 |
| $(P → Q)∧(R → S)∧(¬Q∨¬S) ⇒ ¬P ∨ ¬R$ | 破坏性二难 |
左边的每个元为前提,右边的是结论
二难:发展经济导致污染,不发展经济导致贫困,要么污染要么贫困,陷入了两难的境地
常用的推理规则
替换规则
设$G$是一公式，$A$是在$G$的某个位置出现的子公式，将该子公式$A$用公式$B$置换，称为替换
设$G′$是公式$G$中的某个子公式$A$用$B$替换后得到的公式，如果$A ⇔ B$，则$G ⇔ G′$
Important!!!: 替换规则只能对恒等式$A ⇔ B$成立，对不等式不成立
$A ⇒ B, G ⇏ G′$
代入规则
$G(P1 , P2 , . . . , Pn )$是一公式，$F$是另一公式，设$Pi$ 是公式$G$中的某一原子，将 公式$G$中的每个$Pi$ 的用$F$替换，称为代入，代入后所得的公式 $G(P1, . . . , F, . . . , Pn)$称为原公式的代入实例
$G(P1 , P2 , . . . , Pn )$是重言式，则其代入实例$G(P1, . . . , Pi−1,F, Pi+1, . . . , Pn)$也是重言式
更名规则
量词的处理
辖域的扩展与收缩
对偶原理
证明方法
等值演算(形式结构是永真式)
$$ \begin{aligned} & (p \rightarrow(q \rightarrow r)) \wedge p \wedge q \rightarrow {r} \ \Leftrightarrow & (\neg {p} \vee(\neg q \vee {r}) \wedge {p} \wedge {q} \rightarrow {r} \ \Leftrightarrow & ((\neg {p} \wedge {p}) \vee((\neg {q} \vee {r}) \wedge p)) \wedge q \rightarrow {r} \ \Leftrightarrow & ((\neg {q} \vee {r}) \wedge {q}) \wedge {p} \rightarrow {r} \ \Leftrightarrow & ((\neg {q} \wedge {q}) \vee( {r} \wedge {q})) \wedge {p} \rightarrow {r} \ \Leftrightarrow & ( {r} \wedge {q} \wedge {p}) \rightarrow {r} \ \Leftrightarrow & \neg( {r} \wedge {q} \wedge {p}) \vee {r} \ \Leftrightarrow & \neg {r} \vee \neg q \vee \neg {p} \vee {r} \ \Leftrightarrow & (\neg r \vee r) \vee \neg q \vee \neg {p} \Leftrightarrow {1} \end{aligned} $$
推演(证明序列)
设$C1, C2, . . . , Cm$是关于条件$H1, H2, . . . , Hn$的证明序列
则对每个$Ci$都有:$ (H1 ∧H2 ∧…∧Hn ⇒Ci)$记作$(H1,H2,…,Hn ⊢ Ci)$反之亦然
$$ \begin{aligned} & ( {p} \rightarrow( {q} \rightarrow {r})) \wedge {p} \wedge {q} \ \Leftrightarrow & (( {p} \rightarrow( {q} \rightarrow {r})) \wedge {p}) \wedge {q} \ \Rightarrow & ( {q} \rightarrow {r}) \wedge {q} \ \Rightarrow & {r} \end{aligned} $$
直接证明法
$Example:A→B∨C, B→¬A, D→¬C⊢A→¬D$
-
$A→B∨C \quad(P)$
-
$B→¬A \quad(P)$
-
$A → ¬B \quad(2+T)$
-
$A → (B∨C)∧¬B \quad(1.2+复合式)$
-
$A→C∧¬B \quad(4+T)$
-
$(A → C)∧(A → ¬B) \quad(5+T)$
-
$A → C\quad (6+简化式)$
-
$D→¬C \quad(P)$
-
$C → ¬D\quad (8+T)$
-
$A → ¬D\quad (7.9+前提三段论)$
间接证明法
- CP 规则
- $A \quad(附加前提)$
- $A→B∨C\quad (P)$
- $B ∨ C\quad (1.2+MP)$
- $B→¬A \quad(P)$
- $ A → ¬B\quad (4+T)$
- $¬B \quad(1.5+MP)$
- $ C \quad(3.6+析取三段论) $
- $D→¬C\quad (P) $
- $C → ¬D\quad(8+T)$
- $¬D \quad(7.9+前提三段论)$
更多用于蕴含式的证明
- 反证法
中心思想为$H1, H2, H3, ¬(A → ¬D) ⊢ F.$
- $¬(A → ¬D) \quad(否定前提)$
- $A∧D \quad(1+T)$
- $A\quad (2+简化式)$
- $D \quad(2+简化式)$
- $D→¬C\quad (P)$
- $¬C \quad(4.5+MP)$
- $A→B∨C\quad (P)$
- $B∨C \quad(3.7+MP)$
- $B\quad (6.8+析取三段论)$
- $B→¬A \quad(P)$
- $¬A\quad (9.10+MP)$
- $F\quad(3.11+合取式)$
Chapter2 一阶谓词逻辑
谓词与量词
谓词
定义
如果 x 是整数，“x 大于 2” 不是命题，它的真值依赖于 x 的取值——不确定但唯一
一元谓词 P: 陈述 P(x)看作命题函数 P 在 x 的一个值
P 的定义域是整数集;P(3)是一个取值为 T 的命题;P(1)是一个取值为 F 的命题
谓词的递归定义: $If\ P\ is\ an\ n-ary\ predicate\ symbol, and\ t_1,t_2, . . . ,t_n\ are\ terms, then\ P(t_1,t_2, . . . ,t_n)是原子$
$LOVE(father(MARY), MARY);$
- 和命题一样，谓词原子是有唯一的真假值的
- 如果把命题公式中的原子换成谓词原子,那么这个公式就叫做谓词公式
语义
解释一个谓词公式需要解释对象和谓词原子两个部分
$F$是一谓词公式，$F$的一个$解释I$包含一个$集合D$(称为全总个体域(论域))
-
每个常量符号对应于 $D$ 中的一个元素
-
每个 $n$ 元函数对应于一个 $D^n⟶D$ 的函数
$(D^n$$≜{⟨x1,x2,. . . ,xn⟩∣xi∈D,i=1,2,3,…,n})$
-
每个 $n元谓词$对应于$1$个 $Dn⟶{0,1}$ 的函数.
量词
- 若 P(x) 是谓词, $\forall xP(x)$表示 “对所有的 x, P(x)" 称为全称量词
- 若 P(x) 是谓词, $\exists xP(x)$表示 “存在某个 x, P(x)” 称为存在量词
量词的优先级高于其它逻辑运算符
合式公式(WFF)的谓词拓展
递归定义:
使用非、或、且、蕴含和等价的在有限步中生成的公式。
- 如果 F 是 WFF,x 是变元,那么 $\forall xF$ , $\exists xF$ 都是 WFF
辖域
形如$\forall xF(x)$ , $\exists xF(x)$ 的子公式, $F$称为**全称(特称)**量词$\forall x$ （ $\exists x$）的辖域
这里的$x$即为约束变量(约束出现)。
推理方法补充
所有的命题公式有关恒等式和不等式的结论在谓词公式中均成立
常用的推理规则补充
更名规则
$F(x)$ 表示含自由变量 $x$ 的公式，若变量$ y $不出现在公式 $F(x)$ 中，则：
$∀xF(x)⇔∀yF(y)$
$∃xF(x)⇔∃yF(y)$
不能改变原式约束关系
量词的处理
量词解销
- $∀xF⇔∀F$ , $∃xF⇔∃F$：$F$与$x$无关
- $∀xF(x)\Rightarrow F(x)$ , $∃F(a)⇔∃xF(x)$
量词否定
- $¬(∃xF(x))⇔∀x¬F(x)$
- $¬(∀xF(x))⇔\exists x¬F(x)$
量词分配
设 $F(x)$ 和 $G(x)$ 是两谓词公式，则：
$$ \begin{aligned} & \forall x(F(x) \wedge G(x)) \Leftrightarrow \forall x F(x) \wedge \forall x G(x) \ & \exists x(F(x) \vee G(x)) \Leftrightarrow \exists x F(x) \vee \exists x G(x) \ & \forall x F(x) \vee \forall x G(x) \Rightarrow \forall x(F(x) \vee G(x)) \ & \exists x(F(x) \wedge G(x)) \Rightarrow \exists x F(x) \wedge \exists x G(x) \end{aligned} $$
- 任意配合取,存在配析取。
- 如$F(x)$ : $x$ 是偶数, $G(x): x$ 是奇数, 则, 在自然数集合的解释下: $\forall x(F(x) \vee G(x))$ 为真，但是， $\forall x F(x) \vee \forall x G(x)$ 为假; 同样, $\exists x F(x) \wedge \exists x G(x)$ 为真, 但是, $\exists x(F(x) \wedge G(x))$ 为假
多量词处理
$$ \begin{aligned} & \forall x \forall y F(x, y) \Leftrightarrow \forall y \forall x F(x, y) \ & \exists x \exists y F(x, y) \Leftrightarrow \exists y \exists x F(x, y) \ & \forall x \forall y F(x, y) \Rightarrow \exists y \forall x F(x, y) \ & \exists y \forall x F(x, y) \Rightarrow \forall x \exists y F(x, y) \ & \forall x \exists y F(x, y) \Rightarrow \exists y \exists x F(x, y) \end{aligned} $$
类型相同无所谓,类型不同后换前
全称指定规则(US)
$\forall xF(x) \Rightarrow F(y)$,y 不是在公式 A 中出现的约束变量。
$\forall xF(x) \Rightarrow F(c)$,c 是常量。
US 规则中的量词的辖域是整个公式(要把整个左边的公式全部包起来),而不是局部的子公式(不可局部替换),故:
$\forall x P(x) \rightarrow Q \nvdash P(x) \rightarrow Q$
另外有：
$\forall x \forall y P(x, y) \vdash \forall y P(x, y) ，其中 : F(x) \triangleq \forall y P(x, y) ；$ > $\forall x \exists y P(x, y) \nvdash \exists y P(y, y), y 在 \forall y P(x, y) 中约束出现；$
特称指定规则(ES)
$\exists xF(x) \Rightarrow F(c)$,c 是新引入的常量。
ES 规则中的量词的辖域是整个公式，而不是局部的子公式,故:
$\exists x P(x) \rightarrow Q(x) \nvdash P(a) \rightarrow Q(x)$
另外有:
$\exists x P(x, a) \vdash \exists y\exists x P(x, y) ,其中:F(y)=\exists x P(x,y)$
特称推广规则(EG)
$F(c) \Rightarrow \exists xF(x)$,y 是新引入的变量。
全称推广规则(UG)
$ F(x)\Rightarrow \forall yF(y)$
辖域的扩展与收缩
设 $x$ 不在公式 $G$ 中出现, 则:
$$ \begin{aligned} & (\forall x F(x)) \wedge G \Leftrightarrow \forall x(F(x) \wedge G) \ & (\forall x F(x)) \vee G \Leftrightarrow \forall x(F(x) \vee G) \ & (\exists x F(x)) \wedge G \Leftrightarrow \exists x(F(x) \wedge G) \ & (\exists x F(x)) \vee G \Leftrightarrow \exists x(F(x) \vee G) \end{aligned} $$
只要无关随便取
对偶原理
对偶式:将$\forall$,$\exists$,$\vee$,$\wedge$,$T$,$F$分别替换为$\exists$,$\forall$,$\wedge$,$\vee$,$F$,$T$,并且保持原有的运算关系(运算顺序)不变所得到的公式
设 F 和 G 是仅含有$\forall$,$\exists$,$\vee$,$¬$,$\wedge$运算符号的公式,则有$F\Leftrightarrow G$ 当且仅当 $F^\Leftrightarrow G^$
前束范式
形如：$\begin{aligned} & \forall x \forall y(P(x, y) \wedge Q(x)) \ & \forall x \forall y \exists z(P(x, y) \rightarrow Q(x, z))\end{aligned}$的公式为前束范式。
求解方法:
- 消除 $\rightarrow,\leftrightarrow$;
- 用德摩根律消除对非原子子公式的否定
- 重新命名约束变量
- 外提量词(吸收，扩张和分配)
前束范式不唯一
证明方法补充
- 命题公式的推理规则和证明方法对谓词公式全都可用
- 谓词公式特有的对处理量词的4 规则: 两个量词的分离和引入
- 约束与非约束的关系不能改变
$\forall yP(y)\vee Q(x)\vee R(z)=F(x,z)$
$\forall yP(x,y)\vee Q(x,y) \Leftrightarrow \forall zP(x , z) \vee Q(x , y) = G(x , y)$
-
先特殊,后一般(ES 在前,US 在后)
-
加量词:UG/EG
-
去量词:ES/US(先后关系,避免 US+ES 再用 UG)
Chapter3 集合论
集合概念
集合及其描述
定义
-
集合是数学最原始的概念，因此没有定义，只有一组公理来刻画。
-
由于集合论是用精确的语言来表达二义的自然语言的，逻辑中的相关规律，在集合论中自然成立
描述
外延法
罗列/枚举: $V ={ {a}, {e}, {i}, {o}, {u}}$
概括法
${x | P(x)}$
$a \in {x | P(x)} ↔ P(a)$
集合的基数
集合中所有元素的个数称为该集合的基数, 记为 $|S |$
若$|S |=n$ 则称其为有限集合
集合子集
外延原则
集合相等当且仅当它们有同样的元素即 $A=B \Leftrightarrow \forall x(x \in A \Leftrightarrow x \in B)$
子集
$\forall x(x \in A \rightarrow x \in B)$集合 A 称为集合 B 的子集， 记作$A\subseteq B$
- 子集具有传递性
- 集合相等当且仅当是互相的子集
空集
关于空集的一些性质：
- 空集是任何集合的子集
- 空集是唯一的，可以用 $Ø$表示
- 空集本身可以是一个对象，可以是某个集合的元素$Ø\in{Ø}, Ø\subseteq{Ø}$
事实上，我们从空集开始构造整个集合世界!：自然数、有理数、实数……
幂集合 笛卡尔积
幂集
$S$是一个集合,$S$的幂集是$S$的所有子集的集合$\rho (S)={x|x \subseteq S}$
$\rho({a, b}) = {Ø,{a},{b},{a, b}}$
$If \ \rho (A) \subseteq \rho (B), then\ A \subseteq B$
有限集合的所有子集
如果 $|A|=n$, 则 $|\rho (A)|=2^n$ 幂集的另一种记法: $2^A$
集合运算
运算定义的基本方式: 将结果定义为一个新的集合
Notion: 集合上的运算没有定义优先级别
集合上的运算本质上和逻辑运算相同，因此逻辑上的恒等式和不 等式可以完全平移到集合上来
交并补
$\begin{aligned} & A \cup B \triangleq{x \mid x \in A \vee x \in B} ; \ & A \cap B \triangleq{x \mid x \in A \wedge x \in B} ; \ & A-B \triangleq{x \mid x \in A \wedge x \notin B} .\end{aligned}$
广义交 广义并
设 𝐴 为非空集合， 𝐴 的所有元素的并，记为$⋃ 𝐴$; 定义为
$⋃𝐴={𝑥|∃𝑦(𝑦∈𝐴∧ 𝑥∈𝑦)}$
why"非空"?–集合悖论
设 𝐴 为非空集合， 𝐴 的所有元素的交，记为$⋂ 𝐴$, 定
义为
$⋂ 𝐴 = {𝑥|∀𝑦(𝑦 ∈ 𝐴 → 𝑥 ∈ 𝑦)}$
集合等式
最小上界和最大下界
最小上界：
$A \subseteq A \cup B, B \subseteq A \cup B$ (A 与 B 的上界)
$\text { 对任意 } X, \text { 若 } A \subseteq X, B \subseteq X \text {, 则 } A \cup B \subseteq X \$ (最小上界)
X 在右
最大下界:
$A \cap B \subseteq A, A \cap B \subseteq B $ (A 与 B 的下界)
$\text { 对任意 } X, \text { 若 } X \subseteq A, X \subseteq B \text {, 则 } X \subseteq A \cap B$ (最大下界)
X 在左
集合证明
在量化逻辑表达式中使用集合符号$\begin{aligned} & \forall x \in \mathrm{~S}(\mathrm{P}(x)) \text { 代表 } \forall x(x \in \mathrm{~S} \rightarrow \mathrm{P}(x)) \ & \exists x \in \mathrm{~S}(\mathrm{P}(x)) \text { 代表 } \exists x(x \in \mathrm{~S} \wedge \mathrm{P}(x))\end{aligned}$
集合构造
皮亚诺公理
-
零是个自然数
-
每个自然数都有一个后继(也是个自然数)
-
零不是任何自然数的后继
-
不同的自然数有不同的后继
-
设由自然数组成的某个集合含有零， 且每当该集合含有某个自然数时便也同时含有这个数的后继，那么该集合定含有全部自然数(归纳公理)
用集合定义自然数
设 $a$ 为集合，称 $a \cup{a}$ 为 $a$ 的后继，记为 $s(a)$ ，或 $a^{+}$。设 $A$ 是集合，若 $A$ 满足下列条件，称 $A$ 为归纳集：
- Ø $\in \boldsymbol{A}$
- $\forall a(a \in A \rightarrow s(a) \in A}$
自然数集合 $N(\mathbb{N})$ 是所有归纳集的交集
- 因此：$N={\varnothing,{\varnothing},{\varnothing,{\varnothing}},{\varnothing,{\varnothing},{\varnothing,{\varnothing}}}, \ldots}$
- $N$ 的每一个元素称为一个自然数。
- Ø 记为 $\mathbf{0}, s(0)$ 记为 $1, s(1)$ 记为 $2, s(2)$ 记为 $\mathbf{3}$ ，以此类推
集合悖论
$A={x | P(x)}$, 实际上不能保证:对任意的性质 P，这样的定义都有意义。
理发师悖论:“我给所有不给自己理发的人理发”->公理集合论
集合的归纳定义
字符串集合
设 A 是一个集合, 则，A 上的有限序列集合 A 归纳定义:
- ［inductive base］：$\varepsilon \in A^*$（空串）
- ［inductive rule］：if $s \in A^* \wedge a \in A$ ，then $\langle a, s\rangle \in A^*$（记为 as）
- ［极小性条款］：$A^*$ 的所有元素都由并仅由以上步骤在有限步生成．
计算机处理的对象一定是有归纳结构的集合
归纳证明
设 $S$ 是一个具有归纳结构的集合，$\forall x(x \in S \rightarrow P(x))$ ，当且仅当，下述两条件同时成立：
- Base：对 S 递归定义中的基础集合 $B$ 有：$\forall x(x \in B \rightarrow P(x))$
- Inductive rule：对每个归纳条款 $r(x, y)$（表示由 $x$ 和 $y$ 按照规则 $r$ 生成的新元素），有：$P(x) \wedge P(y) \rightarrow P(r(x, y))$ ．
if $S=\mathbb{N}$ ，then $r(n)=n+1$ ；此时称为数学归纳法（Mathematical Induction）；但是在计算机中使用更多的是针对一般归纳结构的结构归纳法；
两个条件必须同时成立，反例：$P(n)=n>3$则 $\forall n(n \in \mathbb{N} \rightarrow P(n))$ 为假，而 $\forall n(P(n) \rightarrow P(n+1))$ 为真．
笛卡尔积
序偶
序偶是一个包含两个元素的 collection, 其中一个(称之为第一分量)和另一个元素(称之为第二分量)是可区别的;如果第一分量是 a, 第二分量是 b，记该序偶为:$<a, b>$
n 重组
- 二重组即序偶
- 任 $n(n \geqslant 3)$ 个元素 $a_1, a_2, \ldots, a_n$ ，设前 $n-1$ 个元素的 $n-1$ 重组已经定义，并记为：$\left\langle a_1, a_2, \ldots, a_{n-1}\right\rangle$ ，则，$n$ 重组定义为：$\left\langle a_1, a_2, \ldots a_n\right\rangle \triangleq\left\langle\left\langle a_1, a_2, \ldots a_{n-1}\right\rangle, a_n\right\rangle$
笛卡尔积
无交换律、结合律、有分配律,但交换、结合的集合是等价的(存在一个映射将两个集合的元素一一对应起来)