算法索引

离散数学、计算数学、组合数学

0. 命题逻辑

本部分除特别标注，否则不注意加斜体

0.0 命题的分类

原子命题：不可分解为更简单的命题的命题；

复合命题：由若干原子命题通过命题连接词和标点符号组成的命题。

悖(bei4)论：命题为1时，永远为假的命题。

0.1 命题的规定

命题标识符：表示一个命题的符号，比如(P, Q, p, q, p₁)

命题常量：可以确定真假的命题

命题变量：暂不可确定真假的命题

命题的指派（赋值）：给定一个命题变量一个值。

0.2 命题的连接词运算

感谢boole的贡献，为了纪念他，很多语言中都有bool类型。

连接命题的词语叫做命题连接词。常见的有：

否、析取、合取、蕴含、等价、异或。

定义一命题p，那么：

使用T(正体)或者1表示其为真命题，使用F(正体)或者0表示假命题

解析失败 (语法错误): {\displaystyle ┐p} （程序中使用!p）表示p的反命题，读作非p。

$p\wedge q$ （程序中使用p && q）表示p且q 或者说p与q。命题 $p\wedge q$ 称为p, q的合取。

幂等率： $p\wedge p=p$

交换律： $p\wedge q=q\wedge p$

结合律： $\left(p\wedge q\right)\wedge r=p\wedge \left(q\wedge r\right)=p\wedge q\wedge r$

同一律： $p\wedge 1=p$

零一率： $p\wedge 0=0$

否定率： $p\wedge \neg p=0$

$p\vee q$ （程序中使用p || q）表示p或q或者说p同或q。命题 $p\vee q$ 称为p, q的析取。

幂等率

交换律

结合律

同一律： $p\vee 0=p$

零一率： $p\vee 1=1$

否定率： $p\vee \neg p=0$

吸收律： $p\wedge \left(p\vee q\right)=p\vee \left(p\wedge q\right)=p$

德摩根率： $\neg \left(p\wedge q\right)=\neg p\vee \neg q$

析取和合取的分配率： $p\vee \left(q\wedge r\right)=\left(p\vee q\right)\wedge \left(p\vee r\right)$

$p\wedge \left(q\vee r\right)=\left(p\wedge q\right)\vee \left(p\wedge r\right)$

$p\oplus q$ 或者 $p{\overline {\vee }}q$ （程序中使用p | q表示按位异或）表示p或q或者说p异或q。命题 $p\oplus q$ 称为p, q的不可兼析取。

交换律

结合律

合取对不可兼析取的分配率： $p\wedge \left(q\oplus r\right)=\left(p\wedge q\right)\oplus \left(q\wedge r\right)$

注意：涉及不可兼析取的分配率仅此一个

另有： $p\oplus q=\neg \left(p<->q\right)$

归化：p⊕q == (p && !q) || (!p && q) == (p || q) && (!p || !q)

其中其真值表为，即只有两个题设中有且只有一个为1，结果才是1：

A	B	结果
1	1	0
1	0	1
0	1	1
0	0	0

例0.2.0 判断以下命题：

“如果今日晴，那么我们去打酱油

这就是今日晴蕴我们去打酱油，如果今日不晴，那么无论打不打酱油，这个命题都是真的，但是如果今天晴却没有打酱油，那么这个命题就是假的。

$p\rightarrow q$ 表示以下命题：其中p叫做蕴含式前件（假设，前提），q叫做蕴含式后件（结论，后果）（蕴含关系）.

其真值表如下，即只有前提为0，但是结论为1时才是0或者说可以满足命题p和命题q同时满足条件时，结果可以成立便为1：

A	B	结果
1	1	1
1	0	0
0	1	1
0	0	1

表示p蕴含q的语句很多，比如：

p是q的充分条件；

若p则q；

p仅当q（时成立）；

q时p的必要条件；

q当p（时成立）；

例0.2.1 证明 $p\rightarrow q=\neg p\vee q$ ——归化公式

p	q	p → q	!p	!p	q
0	0	1	1	q
0	1	1	1	q
1	0	0	0	0
1	1	1	0	1

例0.2.2 证明 p → q == !q → !p

p → q == !p || q == !(!q) || !p == !q → !p

例0.2.3 证明 !(p → q) == p && !q

!(p → q) == !(!p || q) == p && !q

$p<->q$ 表示当p, q同为真或假时为真，反之为假.

p等价于q

交换律

结合律

另有： $p<->q=\left(p\rightarrow q\right)\wedge \left(q\rightarrow p\right)$

规化：p ↔ q == (!p || q) && (!q || p)

== (p && q) || (!q && !p)

0.3 命题公式

由命题变项(p, q, a, b等)、逻辑联结词、圆括号按照一定规律组成的合式叫命题公式，简称公式；以下是公式在本阶段的规定，[#1.0.1“每一个”和“有一个”|outline #3.1. 谓词逻辑|outline]：

(1) 单个命题是合式公式

(2) 若A为合式公式，则 $\neg A$ 是合式公式

(3) 若A, B为合式公式，则 $A\wedge B,A\vee B,A\rightarrow B,A<-B$ 是合式公式

(4) 当且仅当有限地使用前三条原则得到的符号串叫做合式公式

0.3.1 逻辑联结词的优先级

逻辑联结词的优先级依次为：

!, && , || , → , ↔

例0.3.0 证明!(p || q) == !p && !q

p	q	p	q	!(p	q)	!p	!q	!p && !q
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

德摩根率：p || q == !(!p && !q)

p && q == !(!p || !q)

0.3.2 公式的等值

给定两个公式A, B，如果对于给定A, B任一不同的指派时它们的值均分别相等，那么就说A与B等值，记作“ $A\Leftrightarrow B$ ”，在本册中简记为“A = B”或“A == B”。

0.3.3 全动能联结词组

我们知道任意除 “!”, “&&” ,“||”以外的连接词都可用这三个进行替换。

如果任何一个公式均可以用一个一个连接词集合中的元素进行替换，那么这个集合叫做全功能联结词组或者联结功能完备集。

如果一个全功能连接词组中去掉任意一个连接词就不再是全功能连接词组，那么就叫这个全功能连接词组为最小全功能联结词组或者最小功能完备集。

以下列出两个全功能联结词组：

{!, ||}, {!, &&}

0.3.3 公式分类

永真式（重言式）：取指一定为1的公式。

永假式（矛盾式）：取值一定为0的公式。

可满足式：非矛盾式的公式。

仅可满足式：非永真式的可满足式。

证明永真、永假除了可以使用真值表，还可以使用否定律和零一率。

0.3.4 其他公式

等价否定等值律：A ←→ B == !A ←→ !B

假言移位：A → B == !B → !A——反证法的依据

归谬律：(A → B) && (A → !B) == !A

A	B	A → B	A → !B	(A → B) && (A → !B)
1	1	1	0	0
1	0	0	1	0
0	1	1	1	1
0	0	1	1	1

0.4 范式

0.4.0 对偶式和对偶原理

在仅含有联结词 $\neg ,\wedge ,\vee$ 的公式A中，将∨换成∧，将∧换成∨，同时0和1互相替代，所得公式A^*称为A的对偶式。

显然，A也是A^*的对偶式。

定理2 公式的否定等于其变元否定的对偶式。

若A和B互为对偶式，设P[0] – P[n]为其变元，那么：

!A(P[0], … , P[N]) == A(!P[0], … , !P[N])

A(!P[0], … , !P[N]) == !A(P[0], … , P[N])

定理3 对偶原理若两个公式等值，则它们的对偶式等值。

0.4.1 简单析取式和简单合取式

简单析取式：仅有有限个命题变项或其否定构成的析取式

如：p || !q ||r,p但 p || (!q ||r)不是

简单合取式：仅有有限个命题变项或其否定构成的合取式

如：!p && q && !r,q

0.4.2 范式的定义合存在性

仅由有限个简单合取式的析取构成的析取式称为析取范式；

仅由有限个简单析取式的合取构成的合取式称为合取范式；

注意：p || r || q 是三个简单合取式的析取，也是一个简单析取式的合取。

定理4 任何一个公式均存在一个与之等价的析取范式和合取范式。

经简单的构造性证明可以得到；

理论证明：

第一步化为基本三个符号组成的公式

第二步德摩根律等将否定移到命题变项之间

第三步使用分配率合结合律化去二重括号

例0.4.0 将(p → q) ↔ r化成两种范式

原式=(!(!p || q) || r) && ( !r || (!p || q) )

=(p && !q || r) && ( !r || !p || q )

=( (p || r) && (!q || r) ) && ( !r || (!p || q) )

=(p || r) && (!q || r) && ( !r || !p || q )

原式=((!p || q) && r) || ( !r && !(!p || q) )

=!p&&r|| q&&r || !r && p && !q

0.4.3 主析取范式

1. 极小项（布尔合取）：对于公式中有n个命题变项p[0], p[1], … , p[n-1]中，每个命题变项p[i]或者其否定!p[i]出现且仅出现一个的简单合取式，并且按照下标和字典排序。

规定：矛盾式主析取范式为0，重言式为其所有极小项析取

2. 极小项和赋值一一对应，每个极小项有且只有1个赋值使其为真，其它赋值均为假。

3. 极小项的记法：对于公示中2ⁿ个赋值，每个赋值对应一个极小项。对于任意一个极小项，将其记作解析失败 (未知函数“\textasciimacron”): {\displaystyle {m}_{\stackrel{\textasciimacron }{{a}_{1}{a}_{2}{a}_{3}}}} 或者将解析失败 (未知函数“\textasciimacron”): {\displaystyle \stackrel{\textasciimacron }{{a}_{1}{a}_{2}{a}_{3}}} 换成所对应十进制数k，即记作 ${m}_{k}$ ，其中 ${a}_{\mathrm {1,} }{a}_{\mathrm {2,} }{a}_{3}$ 分别是使其为真的赋值。

例0.4.1 将以下极小项化为命题公式的形式：

${m}_{01001}=\neg {p}_{0}\wedge {p}_{1}\wedge \neg {p}_{2}\wedge \neg {p}_{3}\wedge {p}_{4}$

${\begin{array}{c}{m}_{7}\Rightarrow {m}_{111}=p\wedge q\wedge r\\\Rightarrow {m}_{0111}=\neg o\wedge p\wedge q\wedge r\end{array}}$ 结论：表示为 ${m}_{k}$ 形式的极小项只能确定哪些变项不加“┐”，而不能确定那个应加

4. 主析取范式：若干个不同极小项的析取

5. 定理5 任何一个公式存在且仅存在一个与之等值的主析取范式。

例0.4.2 将!p&&r|| q&&r || !r && p && q 化成主析取范式

分析：每个极小项取真的取指分别为01_, _11, 100，我们知道析取式中只要一个简单合取式为真，那么结果就为真，所以，!p&&r可以改写成!p&&q&&r || !p&&!q&&r同理。。。

例0.4.3 使用真值表法将!(p&&q)化为主析取范式

!(p&&q) == !p || !q

p	q	!p	!q
1	1	0
1	0	1
0	1	1
0	0	1

!(p&&q) == m₀₁ || m₁₀ || m₀₀ == (!p && q) || (p && !q) || (!p ||!q) = $\sum \left(\mathrm {0,} \mathrm {1,} 2\right)$

0.4.4 主合取范式

1. 极大项（布尔析取）：对于公式中有n个命题变项p[0], p[1], … , p[n-1]中，每个命题变项p[i]或者其否定!p[i]出现且仅出现一个的简单析取式，并且按照下标和字典排序。

2. 极大项和赋值一一对应，每个极小项有且只有1个赋值使其为假，其它赋值均为真。

3. 极小项的记法：对于公示中2ⁿ个赋值，每个赋值对应一个极小项。对于任意一个极小项，将其记作解析失败 (未知函数“\textasciimacron”): {\displaystyle {M}_{\stackrel{\textasciimacron }{{a}_{1}{a}_{2}{a}_{3}}}} 或者将解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle \stackrel{\textasciimacron }{{a}_{1}{a}_{2}{a}_{3}}} 换成所对应十进制数k，即记作 ${M}_{k}$ ，其中 ${a}_{\mathrm {1,} }{a}_{\mathrm {2,} }{a}_{3}$ 分别是使其为假的赋值。

4. 主合取范式：若干个不同极大项的合取

5. 定理6 任何一个公式存在且仅存在一个与之等值的主合取范式。

结论： $\sum \left(\mathrm {0,} \mathrm {1,} 2\right)=\prod \left(3\right)$

0.5 逻辑推理

从已知条件、假设、前提或公理出发,根据推理规则推出结论、定理的过程,称为推理,这是逻辑学最基本的任务,在命题逻辑中也不例外。这个过程称为演绎或者形式证明。

设A与C是两个命题公式,若A→C为永真式、重言式,则称C是A的有效结论,或称 A 可以逻辑推出C，A重言蕴含C，记为A⇒C。

由上述定义可知,当A为假时,A→C 肯定为真,因此在考虑 A⇒C 时,只要考虑A为真时,C 是否为真就可以了,因此上述定义可写成：

设 A 与 C 是两个命题公式,若当 A 为真时 C 也为真,则称 C 是 A 的有效结论,或称 A 可以逻辑推出 C,记为 A⇒C。

从上可知，当A⇒C正确时，若A为真，C为真；若C为假，A为假。

设a[0], a[1], … , a[n]是命题公式，如果(a[0], a[1], … , a[n]) → c 是重言式，那么就称c是集合{a[0], a[1], … , a[n]}的有效结论，或者说{a[0], a[1], … , a[n]}可以逻辑推论c。

或者写作a[0] && a[1]&& … && a[n] ⇒ c

0.5.1 直接证法

根据已知的重言蕴涵式和基本等值式利用推理规则，推演出有效结论，这个过程成为形式演绎或抽象演绎。

P规则：任何推导的过程中，前提均可以引入

T规则：推导过程中，如果前面有一个或多个公式可以逻辑推导出命题公式S（或这些公式重演蕴含S），那么S可以引入到推导过程中去。

推倒诀窍：假设重演蕴含号左侧为真，看看是否能否推得右侧——几何推理。

基本重言蕴含式：

化简I₁, I₂： $a\wedge b\Rightarrow a$

附加I₃, I₄： $a\Rightarrow a\vee b$

I₅：解析失败 (未知函数“\rule”): {\displaystyle \neg a\phantom{\rule{0.5em}{0ex}}=\phantom{\rule{0.5em}{0ex}}a\rightarrow b} （请用真值表证明）

I₆： $b\Rightarrow \neg b\rightarrow a\Rightarrow a\rightarrow b\vee \neg a\Rightarrow a\rightarrow b$

I₇：解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle \neg \left(a\rightarrow b\right)\phantom{\rule{0.5em}{0ex}}=\phantom{\rule{0.5em}{0ex}}\neg \left(\neg a\vee b\right)=a\wedge \neg b\Rightarrow a} （最后一步请用真值表证明）

I₈：解析失败 (未知函数“\rule”): {\displaystyle \neg \left(a\rightarrow b\right)\phantom{\rule{0.5em}{0ex}}=\phantom{\rule{0.5em}{0ex}}\neg \left(\neg a\vee b\right)=a\wedge \neg b\Rightarrow \neg b}

合取引入I₉： $a,b\Rightarrow a\wedge b$

析取三段论I₁₀：解析失败 (未知函数“\rule”): {\displaystyle \neg a,\phantom{\rule{0.5em}{0ex}}a\vee b\Rightarrow b}

假言推理I₁₁：解析失败 (未知函数“\rule”): {\displaystyle a,\phantom{\rule{0.5em}{0ex}}a\rightarrow b\Rightarrow b}

拒取式I₁₂：解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle \neg b,\phantom{\rule{0.5em}{0ex}}a\rightarrow b\Rightarrow \neg a}

假言三段论I₁₃：解析失败 (未知函数“\rule”): {\displaystyle a\rightarrow b,\phantom{\rule{0.5em}{0ex}}b\rightarrow c\Rightarrow a\rightarrow c}

构造性二论I₁₄：解析失败 (未知函数“\rule”): {\displaystyle a\vee b,\phantom{\rule{0.5em}{0ex}}a\rightarrow c,\phantom{\rule{0.5em}{0ex}}b\rightarrow d\Rightarrow c\vee d}

推论：解析失败 (未知函数“\rule”): {\displaystyle a\vee b,\phantom{\rule{0.5em}{0ex}}a\rightarrow c,\phantom{\rule{0.5em}{0ex}}b\rightarrow c\Rightarrow c}

等值式：若a ⇔ b，则a ⇒ b，b ⇒ a成立。

故，等值式亦可在形式推导中使用。

0.5.2间接证法

CP规则（附加前提证明法）：对于A ⇒ b → c，如果证明A && b ⇒ c，那么原命题就被证明。

证明：A → (b → c) == !A || (!b || c) == !A || !b || c == !(A && b) || c == (A && b) → c

即，如果A → (b → c) == 1，那么(A && b) → c == 1

对于公式中有n个命题变项p[0], p[1], … , p[n-1]，如果p[0] ∧ p[1] ∧ … ∧ p[n-1]可满足，那么我们称p[0], p[1], … , p[n-1]是相容的。反之，如果p[0] ∧ p[1] ∧ … ∧ p[n-1]是矛盾式，那么他们是不相容的。

归谬法（反证法）：重言蕴涵式A ⇒ b中，若可得到A, ┐b不相容，那么b是A的有效结论。

欲证A ⇒ c，仅需证A ∧ ┐c == 0。

证明略去。

1. 谓词逻辑

1.0 基本定义

表示谓语部分的大写字母,称为“谓词”。

如M表示需要喝水，N表示喜欢吃肉

谓词需要主语，或者说个体。

比如用a表示“张三”，b表示“李四”；用x, y, z表示未知个体。

令P(x)为包含x的语句，D为一个集合；若对于集合D中的任一x，P(x)都是一个命题函数，其中D是P的论域或定义域。

1.0.1“每一个”和“有一个”

我们分别用旋转了180º的“Any”和“Exist”的首字母的倒置形式“”和“”表示“所有”和“存在”。（为了省事，此处使用Any( x, P(x) )和Exist代替( x, P(x) )）

我们可以将一个命题表示为量词语句： $\forall x\mathrm {P} \left(x\right)$ 、 $\exists x\mathrm {P} \left(x\right)$

当存在x使为P(x)为假时，我们知道 $\forall x\mathrm {P} \left(x\right)$ 为假，x称为反例。

没有使用“”和“”限定的变量叫做自由变量，否则成为约束变量。有自由变量的语句一般不是命题，无自由变量的语句是命题。

1.0.2 广义的德摩根律

!( P(x₀) && P(x₁) && … && P(x_n-1) ) == !P(x₀) || !P(x₁) || … || !P(x_n-1)

!Any( x, P(x) ) == Exist( x, !P(x) )

!( P(x₀) || P(x₁) || … || P(x_n-1) ) == !P(x₀) && !P(x₁) && … && !P(x_n-1)

!Exist( x, P(x) )== Any( x, !P(x) )

所以我们得到两个公式，它们称为广义的德摩根律。

[[Image:]]

1.0.3 其他的量词运算律

分配率：

[[Image:]]量词的收缩率和扩张率：

[[Image:]]置换规则：若B是A的子公式，且B ⇔ C，将B在A中的每次出现替换成C得到的公式D ⇔ A。（这其实是进行等值演算的一句，不需指明）

约束变元改名规则：将公式A中某量词的指导变元和辖域中约束变元每次约束出现,全部换成公式中未出现的字母,所得到的公式记为B，则A ⇔ B。

1.1 合法公式

定义0，非逻辑符号：个体常元(如 a,b,c)、函数常元(如表示x +y 的 f(x,y))、谓词常元(如表示人类的 H(x))。

定义1，逻辑符号：个体变元、量词(“”和“”)、联结词、逗号、括号。

定义2，项：个体常元、变元及其函数式的表达式称为项(item)。

(0)个体常元和个体变元是项,如 x,a,c

(1)若 f(x1,x2,..., xn)是 n 元函数,t1,t2,...tn 是 n 个项,则 f(t1,t2,..., tn)是项。如 f(x,y)是

项,x 2 +y 2 也是项,只要运算以后的结果仍是个体域中的对象就是项。

(2)有限次使用(1)得到的表达式是项，其他式子不是项。

定义3，原子公式：设 R(x₁ ,x₂, … ,x_n)是n元谓词t₁, t₂, … ,t_n 是项,则 R(t₁, t₂, … ,t_n)是原子公式。

定义4，合式公式

(0)原子公式是合式公式;

(1)若 A 是合式公式,则(┐A)也是合式公式;

(2)若 A,B 合式,则 $A\wedge B,A\vee B,A\rightarrow B,A<->B$ 合式

(3)若 A 合式,则"“A”和“A”是合式

(4)有限次使用(1)~(3)得到的式子是合式。

1.2 嵌套量词

定义命题函数P(x, y)为x驾驶过y。其中解析失败 (语法错误): {\displaystyle x\in \text{{飞行员}},\phantom{\rule{0.5em}{0ex}}y\in \text{{飞机型号}}}

我们设Q(x) = yP(x, y),

那么xQ(x) == xyP(x, y)

从上面的结论并结合实例，我们很容易的知道：

xyP(x, y) == yxP(x, y)

xyP(x, y) == yxP(x, y)

但是以下式子可能不成立：

xyP(x, y) == yxP(x, y)

xyP(x, y) == yxP(x, y)

1.3 证明

公理

定义

未定义项

定理、引理、推论、公理

证明一个定理为真的过程称为证明。

逻辑学中，一般的有且只有一个公理，任意命题重演蕴涵它本身。

1.3.1数学归纳法

本节整理自wikipedia。

数学归纳法（Mathematical Induction, MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：

骨牌一个接一个倒下，就如同一个值到下一个值的过程。

设有一个命题函数P，

证明当n = 1时命题P(n)成立。

证明如果在n = m时命题P(n)成立，那么可以推导出在n = m+1时命题P(n)也成立。（m代表任意自然数）

这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。

[[Image:]]例1.3.0 证明 ( $n\in \mathrm {N}$ )

我们易证这个公式在n == 0和1时成立，

然后我们计算[[Image:]]

下一步，将等式两边分别加上m + 1，得到

[[Image:]][[Image:]]

1.3.2 强数学归纳法

强数学归纳法(Strong Form of Mathematical Induction)。

证明对于命题函数P(n)，论域为D，由P(k) == 1推出对于任意n > k ≥ n₀时，P(n) == 1从而证明对于任意的n > k ≥ n₀，P(n) == 1过程。

例1.3.1 证明只要用2分和5分的邮票可以表示4分或4分以上的邮资。（方法不唯一，此处证明略去。）

1.4 逻辑谓词的推理公理

[[Image:]]

全称量词的指定（US或-）： $\forall \mathrm {P} \left(x\right)\Rightarrow \mathrm {P} \left({x}_{0}\right)$ ，其中x可以为论域中任意个体。

全称量词的推广（UG或+）： $\forall \mathrm {P} \left({x}_{0}\right)\Rightarrow \mathrm {P} \left(x\right)$ ，其中对P(x)为论域中任意个体成立方成立。

存在量词的指定（ES或-）： $\exists \mathrm {P} \left(x\right)\Rightarrow \mathrm {P} \left({x}_{0}\right)$ ，其中x为某个特定的个体,不是任意的个体。

存在量词的推广（EG或+）： $\exists \mathrm {P} \left({x}_{0}\right)\Rightarrow \mathrm {P} \left(x\right)$ ，其中x可以为任意的个体。

2. 集合论

以下介绍集合论的内容摘自wikipedia：

集合是现代数学中一个重要的基本概念，而集合论的基本理论是在十九世纪末被创立的。这里对被数学家们称为“直观的”或“朴素的”集合论进行一个简短而基本的介绍，另外可参见朴素集合论；关于对集合作公理化的理论，可见公理化集合论。

在纯数学中，朴素集合论是由德国数学家康托尔最早创立的第一个集合论，它后来被更加精确地构建为公理化集合论。

朴素集合论和公理化集合论的区别在于，前者依赖于把集合作为叫做这个集合的“元素”或 “成员”的搜集（collection），未有形式化的理解。

而公理化集合论只使用明确定义的公理列表，还有从中证明的关于集合和成员关系的种种事实（公理起源自我们对对象的搜集和它们的成员的理解，但为了各种目的而被谨慎地构建，例如是避免已知的各种悖论）。

在1908年，恩斯特·策梅洛提议了第一个公理化集合论，策梅洛集合论。这个公理化理论不允许构造序数；而多数“普通数学”不使用序数就不能被开发，序数在多数集合论研究中是根本工具。此外，Zermelo的一个公理涉及“明确性”性质的概念，它的操作性意义是有歧义的。在1922年，亚伯拉罕·弗兰克尔和陶拉尔夫·斯科伦独立的提议了定义“明确性”性质为可以在一阶逻辑中公式化的任何性质，从他们的工作促成了替代公理。Zermelo集合论接受替代公理和正规公理，产生了被称呼为ZF的这个集合论。

2.0 集合论初步

集合（或简称集）是基本的数学概念，它是集合论的研究对象，指具有某种特定性质的事物的总体，（在最原始的集合论─朴素集合论─中的定义，集合就是“一堆东西”。）集合里的事物（“东西”），叫作元素。

我们可以在wikibook上看集合论的教程，我们这里不做高一阶段的讨论。

我们用|A|表示集合A中元素的个数。

2.0.1 幂集

幂集：以一个集合的所有子集为与元素的集合，计为

例2.0.0 写出A == {1, 2}的幂集：

它的子集：{}, {1}, {2}, {1, 2}

它的幂集：{ {}, {1}, {2}, {1, 2} }

我们可以看到，幂集的元素个数是2^|A|个，所以对于集合A，我们也可以记它的中、幂集为2^A。

我们也可以利用和命题逻辑中研究范式的形式来表示其子集，我们按照例题中的来做定义，解析失败 (未知函数“\textasciimacron”): {\displaystyle {A}_{\stackrel{\textasciimacron }{{a}_{\mathrm{0,}}{a}_{\mathrm{1,}}{a}_{2}\mathrm{...},{a}_{n}}}} 中的a_n表示命题“其子集中在原集中的第n个元素出现”的值。

也就是：

A₀₀ == Ø

A₀₁ == {1}

A₁₀ == {2}

A₁₁ == {1, 2}

2.1 集合的运算

设A，B为集合，

定义集合的减运算（集合的差）：

A - B = { x | $x\in \mathrm {A} ,x\notin \mathrm {B}$ }

定义集合的对称差为：

[[Image:]]A △ B = { x | $x\in \mathrm {A} \wedge x\notin \mathrm {B}$ ∨ $x\in \mathrm {B} \wedge x\notin \mathrm {A}$ }

== { x | $x\in \mathrm {A}$ △ $x\in \mathrm {B}$ }

== (A - B) ∪ (B – A)

A ⊕ B== A ∪ B – A ∩ B

或记为A ⊕ B。

对于集合A，全集U，定义：┐A = { x | $x\in \mathrm {U} ,x\notin \mathrm {A}$ }

根据以上定义，我们得出集合的运算率：

幂等律：A∪A == A, A∩A == A;

结合律：(A∪B)∪C == A∪(B∪C), (A∩B)∩C == A∩(B∩C);

交换律：A∪B == B∪A, A∩B == B∩A;

分配率：A∪(B∩C) == (A∪B) ∩ (A∪C),

A∩(B∪C) == (A∩B) ∪ (A∩C)

同一律：A∪Ø == A

零一律：A∩Ø == Ø

排中律：A∪┐A == U

矛盾律：A∩┐A == Ø

吸收律（可通过前几个运算率得出）：[[Image:]]

德摩根律：┐(A∪B) == ┐A ∩ ┐B

┐(A∩B) == ┐A ∪ ┐B

双重否定：┐┐A == A

2.2 有穷集的计数

例2.2.0 某农民闲的蛋疼买了20匹马，公母各一半，长毛5匹，短耳10匹，短毛长耳的母马和公马各3匹，长毛短耳的母马和公马各1匹。

我们假设长毛长耳母马x匹，短毛短耳母马y匹，如图，得出方程组（图中集合A表示母马，B表示公马）：

${\begin{array}{c}\left(5-x\right)+\left(10-y\right)+1+3=10\\x+y+1+3=10\end{array}}$

解得：

${\begin{array}{c}x=1\\y=5\end{array}}$

设P(A_n)为A_n的元素数。

二个集合的包含排斥原理：

P(A₀∪A₁) = P(A₀) + P(A₁) – P(A₀∩A₁)

因为 2 个集合的交集被重复算了一次,故要减去公共部分。

多个集合的包含排斥原理：

[[Image:]]加上奇数个集合相交，减去偶数集合相交。

2.3 有序n元组

将两个具有固定次序的对象x, y写成(x, y)或者<x, y>的形式，则我们称(x, y)或者<x, y>为有序二元组或序偶。

若x == a, y == b，那么(x, y) == (a, b)

下面我们定义有序n元组（简称n元组，其中 $n\in \left(\mathrm {0,} +\mathrm {\infty } \right)$ ）：

(0) 将两个具有固定次序的对象x, y写成(x, y)或者<x, y>的形式，则我们称(x, y)或<x, y>为有序2元组或称序偶，

(1) 若A == (a₀, a₁, … ,a_n-2)是有序n-1元组，那么B == (a₀, a₁, … ,a_n-2, a_n-1)是有序n元组，简称n元组。

我们定义笛卡尔积（或称直积）：

解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikibooks.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle \mathrm{A}\times \mathrm{B}=\text{{}\left(a,b\right)\text{|}a\in \mathrm{A}\wedge b\in \mathrm{B}\text{}}}

其中，解析失败 (语法错误): {\displaystyle \text{|}\mathrm{A}\times \mathrm{B}\text{|}=\text{|}\mathrm{A}\text{|}\times \text{|}\mathrm{B}\text{|}}

注意： $\mathrm {A} \times \mathrm {B} \neq \mathrm {B} \times \mathrm {A}$

2.4 关系

例2.4 列出集合A == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}自乘的笛卡尔积：

太长了，编者懒得列了。

反正上述积中那一大堆的元素未必都有用，于是我们就引入关系的概念，对于A×B，其直积中满足一定条件条件的元素所组成的集合称为关系，计为R。

根据定义，R_A×B ⊆ A×B。

若(x, y) ∈ R_x，那么我们称(x, y)满足关系R_x。

算法