# 集合论

# 集合的基本概念

# 集合的定义

具有某种特定性质事物的全体，通常，用大写的英文字母 $A, B, C,……$ 表示集合

# 集合的元素

组成一个集合的那些对象或单元称为这个集合的元素，通常，用小写的英文字母 $a$ , $b$ , $c$ ,…，或者 $a_1$ , $a_2$ , $b_1$ , $b_2$ … 表示集合中的元素

# 属于

设 A 是一个集合，a 是集合 A 中的元素，记以 $a \in A$ ，读作 $a$ 属于 $A$ ；若 $a$ 不是集合 $A$ 中的元素，则记以 $a \notin A$ ，读作 $a$ 不属于 $A$

# 有限集

包含有限个元素的集合，称为有限集或有穷集 (finite set)

# 无限集

包含无限个元素的集合，称为无限集或无穷集 (infinite set)

# 空集

约定，存在一个没有任何元素的集合，称为空集 (empty set) ，记为 $\varnothing$ ，有时也用 $\{\}$ 来表示

# 全集

约定，所讨论的对象的全体称为全集 (universal set)，记作 $E$ 或 $U$ ，我们所讨论的集合都是全集的子集
全集是相对的

# 集合的元素数

设 $A$ 是有穷集合， $A$ 中元素的个数称为集合 $A$ 的元素数，记为 $|A|$ ，特别， $|\varnothing|=0$

# 集合的表示法

# 列举法

将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征

# 描述法

通过描述集合中元素的共同特征来表示集合

# 文氏图

用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素

# 集合的特征

# 确定性

任何一个对象，或者是这个集合的元素，或者不是，二者必居其一

# 互异性

集合中任何两个元素都是不同的，即集合中不允许出现重复的元素

# 无序性

集合与其中的元素的顺序无关

# 多样性

集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征

# 集合间的关系

# 集合相等

当两个集合 $A$ 和 $B$ 的元素完全一样，即 $A$ ， $B$ 实际上是同一个集合时，则称集合 $A$ ， $B$ 相等，记以 $A=B$

# 集合包含

# 子集

设 $A$ ， $B$ 是两个集合，若 $A$ 的元素都是 $B$ 的元素，则称 $A$ 是 $B$ 的子集 (subset) ，也称 $B$ 包含 $A$ ，或 $A$ 包含于 $B$ ，记以 $A \subseteq B$ ，或 $B \supseteq A$

# 真子集

若 $A \subseteq B$ ，且 $A \neq B$ ，则称 $A$ 是 $B$ 的真子集 (proper subset)，也称 $B$ 真包含 $A$ ，或 $A$ 真包含于 $B$ ，记以 $A \subset B$ ，或 $B \supset A$

# 重要结论

对任意集合 $A$ , 有 $A ⊆ A$
$\varnothing$ 是任意集合的子集，且空集是唯一的
对于任意两个集合 $A$ 、 $B$ ， $A=B$ 当且仅当 $A⊆B$ 且 $B⊆ A$ 。

# 幂集

# 定义

设 $A$ 是集合， $A$ 的所有子集为元素组成的集合称为 $A$ 的幂集，记以 $ρ(A)$ 或 $2^A$ ， $ρ(A)=\{S|S ⊆ A\}$

# 性质

若 A 为有穷集， $|A|=n$ ，则 $|2^A | = |ρ(A)|= C_n^0 + C_n^1 + … + C_n^n =2^n$
$x∈ρ(A)$ 当且仅当 $x⊆A$
设 $A$ 、 $B$ 是两个集合， $A⊆B$ 当且仅当 $ρ(A)⊆ρ(B)$

# 集合运算

# 集合的并集

设 $A$ ， $B$ 是两个集合。所有属于 $A$ 或者属于 $B$ 的元素组成的集合，称为 $A$ 和 $B$ 的并集，记以 $A∪B$ 。即 $A∪B=\{x|x∈A或x∈B\}$

# 集合的交集

设 $A$ ， $B$ 是两个集合。由属于 $A$ 又属于 $B$ 的元素组成的集合，称为 $A$ 和 $B$ 的交集，记以 $A∩B$ 。即 $A∩B=\{x|x∈A且x∈B\}$

# 并集和交集的推广

设 $A_1$ ， $A_2$ ，…， $A_n$ 是 $n$ 个集合，则： $A_1∪A_2∪…∪A_n$ ，简记为 $\bigcup\limits_{i=1}^nA_i$
$A_1∩A_2∩…∩A_n$ ，简记为 $\bigcap\limits_{i=1}^n A_i$

# 集合的补集

设 $A$ 是一个集合，全集 $E$ 与 $A$ 的差集称为 $A$ 的补集，记以 $\sim A$ ，即 $\sim A=E-A$
特别， $\sim \varnothing=E$ ， $\sim E= \varnothing$

# 集合的差集

设 $A$ ， $B$ 是两个集合。由属于集合 $A$ 而不属于集合 $B$ 的所有元素组成的集合，称为 $A$ 与 $B$ 的差集，记以 $A-B$ 。即 $A-B=\{x|x∈A且x ∉B\}$

# 集合的对称差

设 $A$ ， $B$ 是两个集合。则 $A$ 与 $B$ 的和 (对称差), 记以 $A⊕B$ , 定义为 $A⊕B=(A-B)∪(B-A)$ ，即 $A \oplus B=\{x|(x \in A)且(x \notin B)或(x \in B)且(x \notin A)\}$
$A$ 与 $B$ 的对称差还有一个等价的定义，即 $A⊕B=(A∪B)-(A∩B)$

# 集合的运算律

# 等幂律

$A∩A=A$
$A∪A=A$

# 交换律

$A∩B=B∩A$
$A∪B=B∪A$

# 结合律

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

# 分配律

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

# 吸收律

$A∩(A∪B)=A$
$A∪(A∩B)=A$

# 互补律

$\sim A∩A= \varnothing$
$\sim A∪A=E$

# 德摩根律

$\sim (A∩B)=\sim A ∪ \sim B$
$\sim(A∪B)=\sim A ∩ \sim B$

# 同一律

$E∩A=A$
$\varnothing ∪A=A$

# 零一律

$\varnothing∩A=\varnothing$
$E∪A=E$

# 双重否定律

$\sim (\sim A)=A$

# 其他算律

$A-B=A∩ \sim B$
$A⊕B=(A-B)∪(B-A)=(A∪B)-(A∩B)$
$A⊕A=\varnothing$
$\sim\varnothing=E$
$\sim E=\varnothing$

# 有限集合的计数

# 容斥原理

$|A∪B|=|A|+|B|-|A∩B|$
$|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|$
设 $A_1，A_2，…，A_n$ 是 $n$ 个集合，则： $|\bigcup\limits_{i=1}^n A_i|=\sum\limits_{i=1}^n|A_i|-\sum\limits_{i<j}^n|A_i\cap A_j|+\sum\limits_{i<j<k}^n|A_i\cap A_j \cap A_k|+...+(-1)^{n-1}|A_1 \cap A_2 \cap A_3 \cap ...\cap A_n|$ 称为包含排斥原理，简称容斥原理

# 集合恒等式的证明

# 基本定义法

# 公式等价法

# 基本原则

将集合运算表达式中其他运算符号转换为∩和∪；
将补运算作用到单一集合上；
左 $\implies$ 右，右 $\implies$ 左，左 $\implies$ 中间式，右 $\implies$ 中间式；
根据基本运算符号的定义和运算定律转换。

# 集合成员表法

# 关系

# 序偶和笛卡尔积

# 序偶

# 定义

对于有序 $n$ 元组，当 $n=2$ 时，我们将其称作有序二元组，也称作有序对，或序偶。

# 特点

若 $a≠b$ , 则 $(a,b)≠(b,a)$
两个有序对 $(a,b)$ 和 $(c,d)$ 相等当且仅当 $a=c$ ， $b=d$

# 特征

成对出现、具有一定的顺序

# 笛卡尔积

# 定义

设 $A$ ， $B$ 是两个集合，所有有序对 $(x, y)$ 做成的集合 $(其中x∈A，y∈B)$ ，称为 $A$ ， $B$ 的笛卡儿积，记为 $A×B$ ， $A×B=\{(x，y)|x∈A且y∈B\}$
设 $A_1,A_2 , ...,A_n$ 是 $n$ 个集合，由所有有序 $n$ 元组 ( $a_1,a_2,…,a_n$ ) 组成的集合 $(其中ai∈A_i，i=1,2, … ,n)$ ，称为 $A_1,A_2,...,A_n$ 的笛卡儿积，记以 $A_1×A_2 ×...×A_n$ ， $A_1×A_2 ×...×A_n=\{(a_1,a_2 ,… ,a_n) | a_i∈A_i，i=1,2, … ,n \}$

# 性质

$|A×B|=|A|× |B|$
对任意集合 $A$ ，有 $A×\varnothing=\varnothing$ ， $\varnothing \times A=\varnothing$
笛卡儿积运算不满足交换律，即 $A×B≠B×A$
笛卡儿积运算不满足结合律，即 $(A×B)×C≠A×(B×C)$
笛卡儿积运算对并和交运算满足分配律，即
- $A×(B∪C)=(A×B)∪(A×C)$
- $(B∪C)×A=(B×A)∪(C×A)$
- $A×(B∩C)=(A×B)∩(A×C)$
- $(B∩C)×A=(B×A)∩(C×A)$
设 $A$ ， $B$ ， $C$ ， $D$ 是集合，若 $A⊆C$ 且 $B⊆D$ ，则 $A×B ⊆ C×D$

# 二元关系

# 定义

给定任意集合 $A$ 和 $B$ ，若 $R⊆A×B$ ，则称 $R$ 为从 $A$ 到 $B$ 的二元关系，特别在 $A=B$ 时，称 $R$ 为 $A$ 上的二元关系

# 补充

关系是一个集合，是序偶的集合
$R$ $R$ 是有序对的集合。若 $(x,y)∈R$ $(x, y) \in R$ ，则也表示为 $x R y$ $x R y$ ，即 $(x,y)∈ R \iff x R y$ $(x, y) \in R ⟺ x R y$
- 若 $R =\varnothing$ ，则称 $R$ 为 $A$ 到 $B$ 上空关系
- 若 $R =A×B$ ，称 $R$ 为 $A$ 到 $B$ 上全域关系
- 称 $R=\{(x,x)|x∈A\}$ 为 $A$ 上的恒等关系，记为 $I_A$
当集合 $A,B$ 都是有限集时， $A×B$ 共有 $2^{|A|\cdot|B|}$ 个不同的子集，
即从 $A$ 到 $B$ 的不同关系共有 $2^{|A|\cdot|B|}$ 个

# 定义域、值域和域

# 定义

令 $R \subseteq A \times B$ ，且
$\begin{cases} D (R) = \{ x | (∃y) (x R y ) \}\\R (R) = \{ y | (∃x) (x R y ) \}\\F(R) = D(R)∪R(R)\end{cases}$ 则称 $D(R)$ 、 $R(R)$ 和 $F(R)$ 分别是二元关系 $R$ 的定义域、值域和域，显然 $D(R) ⊆ A$ ， $R(R) ⊆ B$

# 关系矩阵与关系图

# 关系矩阵

给定集合 $A=\{a_1,a_2,···,a_m \}$ 和 $B=\{b_1,b_2,···,b_n \}$ ，且 $R⊆A×B$ ，若 $r_{ij}=\begin{cases} 1 ,& {a_i R b_j}\\0 ,& 否则 \end{cases}$
则称矩阵 $M_R=(r _{i j})$ 为 $R$ 的关系矩阵

# 关系图

给定集合 $A=\{a_1,a_2,···,a_m \}$ 和 $A$ 上的关系 $R$ ，且 $R⊆A×A$ ，若：以 $A$ 中的元素为结点；对 $R$ 中的元素 $(a_i ,a_j )$ , 以 $a_i$ 为起点，以 $a_j$ 为终点，作有向边所构成的图，则称该图为 $R$ 的关系图

# 关系运算

# 关系的并、交、补、差

关系是序偶 (有序对) 的集合，因此可以对关系进行运算。
若 $R, S⊆A×B$ ，则 $R∪S$ ， $R ∩S$ ， $\sim R$ ， $R-S⊆A×B$

# 关系的复合

# 定义

设 $R$ 是从集合 $X$ 到 $Y$ 的关系， $S$ 是从 $Y$ 到 $Z$ 的关系，把 $X$ 到 $Z$ 的关系定义为 $R\circ S$ 。称 $R\circ S$ 是关系 $R$ 和 $S$ 的合成关系或复合关系， $R\circ S=\{(x,z)|∃x∈X, ∃z∈Z, 至少存在一个y∈Y有(x , y)∈R且(y , z)∈S\}$

# 定理

已知集合 $X,Y,Z,W$ ，关系 $R_1,R_2,R_3,R_4$ 如下 $X\stackrel {R_1}\longrightarrow Y \stackrel {R_2R_3}\longrightarrow Z \stackrel {R_4}\longrightarrow W$ ，则有：
- $𝑅_1∘(𝑅_2∪𝑅_3)=(𝑅_1∘𝑅_2)∪(𝑅_ 1∘𝑅_3)$
- $R_1∘(R_2∩R_3)⊆(R_1∘R_2)∩(R_1∘R_3)$
- $(𝑅_2∪𝑅_3)∘𝑅_4=(𝑅_2∘𝑅_4)∪(𝑅_3∘𝑅_4)$
- $(𝑅_2∩𝑅_3)∘𝑅_4⊆(𝑅_2∘𝑅_4)∩(𝑅_3∘𝑅_4)$
已知集合 $X, Y, Z, W$ ，关系 $R_1, R_2, R_3$ 如下 $X\stackrel {R_1}\longrightarrow Y \stackrel {R_2}\longrightarrow Z \stackrel {R_3}\longrightarrow W$ ，则有： $(R_1 \circ R_2)\circ R_3=R_1\circ (R_2 \circ R_3)$ 结合律
$R\circ R\circ R \circ\dots\circ R=R^{(n)}$
$R^{(0)}=I_X=\{(x,x)|x\in X\}$

# 逆关系

# 定义

若 $R⊆A×B$ ，则关系 $\overline R =\{(y,x)|(x,y)∈ R\}$
是集合 $B$ 到 $A$ 的关系， $\overline R$ 称为关系 $R$ 的逆关系

# 定理

$R_1, R_2, R$ 为 $X$ 到 $Y$ 的二元关系，则
- $\overline{R_1∪ R_2} =\overline{R_1} ∪\overline{R_2}$
- $\overline{R_1 \cap R_2}=\overline {R_1} \cap \overline {R_2}$
- $\overline{X \times Y} = Y \times X$
- $\overline{\sim R}=\sim \overline{R}$
- $\overline{R_1-R_2}=\overline{R_1}-\overline{R_2}$
- $S \subseteq R \iff \overline{S}\subseteq\overline{R}$
已知集合 $X, Y, Z$ ，关系 $R, S$ 如下， $X \stackrel {R}\longrightarrow Y \stackrel {S}\longrightarrow Z$ ，则有： $\overline{R\circ S}=\overline{S}\circ\overline{R}$

# 注意

将 $R$ 的关系矩阵转置即得 $\overline R$ 的关系矩阵，即 $R$ 和 $\overline R$ 的关系矩阵互为转置矩阵
$\overline R$ 的前域与后域正好是 $R$ 的后域和前域，即 $domR=ran\overline R$ ， $dom\overline R=ranR$
$|R|=|\overline R|$

# 关系性质

# 自反性

令 $R⊆A×A$ ，若对 $A$ 中每个 $x$ ，都有 $xRx$ ，则称 $R$ 是自反的，即 $A上关系R是自反的\iff∀x(x∈A→xRx)$
该定义表明了，在自反的关系 $R$ 中，除其他有序对外，必须包括由每个 $x∈A$ 所组成的元素相同的有序对

# 反自反性

令 $R⊆A×A$ ，若对于 $A$ 中每个 $x$ ，有 $(x,x) ∉R$ ，则称 $R$ 是反自反的，即 $A上关系R是反自反的\iff∀x (x∈A→(x,x) ∉R)$
该定义表明了，一个反自反的关系 $R$ 中，不应包括有任何相同元素的有序对
应该指出，任何一个不是自反的关系，未必是反自反的；反之，任何一个不是反自反的关系，未必是自反的。这就是说，存在既不是自反的也不是反自反的二元关系

# 对称性

令 $R⊆A×A$ ，对于 $A$ 中每个 $x$ 和 $y$ ，若 $xRy$ ，则 $yRx$ ，称 $R$ 是对称的，即 $在A上关系R是对称的\iff(∀x)(∀y)(x,y∈A且xRy→yRx)$
该定义表明了，在表示对称的关系 $R$ 的有序对集合中，若有有序对 $(x, y)$ ，则必定还会有有序对 $(y, x)$

# 反对称性

令 $R⊆A×A$ ，对于 $A$ 中每个 $x$ 和 $y$ ，若 $xRy$ 且 $yRx$ ，则 $x=y$ ，称 $R$ 是反对称的，即 $A上关系R是反对称的 \iff (∀x)(∀y)(x,y∈A且xRy且yRx→x=y)$
该定义表明了，在表示反对称关系 $R$ 的有序对集合中，若存在有序对 $(x, y)$ 和 $(y, x)$ ，则必定是 $x=y$ 。或者说，在 $R$ 中若有有序对 $(x, y)$ ，则除非 $x=y$ ，否则必定不会出现 $(y, x)$

# 传递性

令 $R⊆A×A$ ，对于 $A$ 中每个 $x, y, z$ ，若 $xRy且yRz$ ，则 $xRz$ ，称 $R$ 是传递的，即 $A上关系R是传递的 \iff (∀x)(∀y)(∀z)(x,y,z∈A且xRy且yRz→xRz)$
该定义表明了，在表示可传递关系 $R$ 的有序对集合中，若有有序对 $(x, y)$ 和 $(y, z)$ ，则必有有序对 $(x, z)$

# 结论

关系 $R$ 是自反的 $\implies$ $R$ 不是反自反的
关系 $R$ 是自反的 $\iff$ 关系图中每个结点都有环
关系 $R$ 是反自反的 $\iff$ 关系图中每个结点都无环
关系 $R$ 是自反的 $\iff$ 关系矩阵的主对角线上全为 1
关系 $R$ 是反自反的 $\iff$ 关系矩阵的主对角线上全为 0
关系 $R$ 是对称的 $\iff$ 关系图中任何一对结点之间，要么有方向相反的两条边，要么无任何边
关系 $R$ 是反对称的 $\iff$ 关系图中任何一对结点之间，至多有一条边
关系 $R$ 是对称的 $\iff$ $R$ 的关系矩阵为对称矩阵
关系 $R$ 是反对称的 $\iff$ $R$ 的关系系矩阵满足 $r_{ij}\cdot r_{ji}＝0，i,j=1,2,…,n，i≠j$
非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的
非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的
设 $R⊆A×A$ ，若 $R$ 是反自反的和传递的，则 $R$ 是反对称的

# 闭包运算

# 自反闭包

设 $R$ $R$ 是 $A$ $A$ 上的二元关系，若 $R'$ $R^{'}$ 是 $R$ $R$ 的自反闭包，记作 $r(R)$ $r (R)$ ，则：
- $R'$ 是自反的
- $R⊆R'$
- 对任意的自反关系 $R''$ ， $R⊆R''$ ，则必有 $R'⊆R''$

# 对称闭包

设 $R$ $R$ 是 $A$ $A$ 上的二元关系，若 $R'$ $R^{'}$ 是 $R$ $R$ 的对称闭包，记作 $s(R)$ $s (R)$ ，则：
- $R'$ 是对称的
- $R⊆R'$
- 对任意的对称关系 $R''$ ， $R⊆R''$ ，则必有 $R'⊆R''$

# 传递闭包

设 $R$ 是 $A$ 上的二元关系，若 $R'$ 是 $R$ 的传递闭包，记作 $t(R)$ ，则：
- $R'$ 是传递的
- $R⊆R'$
- 对任意的传递关系 $R''$ ， $R⊆R''$ ，则必有 $R'⊆R''$

# 定理

R 是 X 上的二元关系，则：
- $r(R)=R∪\{(x,x)|x∈X\}=R∪I_x$
- $s(R) = R∪ \overline{R}$
- $t(R)=R∪ R^{(2)}∪ R^{(3)}...∪ R^{(n)}$ ， $n$ 为集合 $X$ 的元素的个数
- $R$ 是自反的 $\iff$ $r(R)$
- $R$ 是对称的 $\iff$ $s(R)=R$
- $R$ 是传递的 $\iff$ $t(R)$

# 等价关系

# 定义

设 $R$ 是集合 $X$ 上的二元关系，如果 $R$ 是自反的、对称的、传递的，那么称 $R$ 是等价关系

# 划分

设集合 $A=\{S_1, S_2 , …, S_m\}$ $A = {S_{1}, S_{2}, \dots, S_{m}}$ , $S_i$ $S_{i}$ 是 $S$ $S$ 的非空子集，如果称 $A$ $A$ 是 $S$ $S$ 的一个划分，称 $S_i$ $S_{i}$ 为划分的块，则：
- $S_i$ 之间是不相交的
- $S_1∪S_2∪…∪S_m = S$

# 等价类

# 定义

$R$ 是集合 $S$ 上的等价关系，对任一 $x\in S$ ，均可构造一个 $S$ 的非空子集 $[x]_R= \{ y | y\in S 且 xRy \}$ ，也可记为 $[x]$ ，叫做 $x$ 关于 $R$ 的等价类:

# 性质

$x\in[x]$
若 $y\in[x]$ , 则 $[y]=[x]$
若 $y\in[x]$ , 则 $[y]∩[x]=\varnothing$

# 定理

集合 $S$ 上的一个等价关系 $R$ 生成的等价类集合对应 $S$ 的一个划分
集合 $S$ 上的一个等价关系 $R$ 生成的等价类集合对应 $S$ 的一个划分。此划分称为集合 $S$ 关于 $R$ 的商集，记为 $S/R$
集合 $S$ 上的一个划分可产生 $S$ 上的一个等价关系

# 偏序关系

# 定义

设 $R$ 是集合 $A$ 中的二元关系，如果 $R$ 是自反的、反对称的和可传递的，则称 $R$ 是 $A$ 中的偏序关系。
通常用符号 “ $≼$ ” 来标记偏序关系 $R$

# 偏序集

在偏序集合 $(A ,≼ )$ 中，如果有元素 $x,y∈A$ , 且 $x≼ y$ (或者写为 $(x,y)∈≼$ ) 和 $x≠y$ , 同时不存在其它任何元素 $z∈A$ ，能使 $x≼ z$ 和 $z≼ y$ , 则称元素 $y$ 盖住 $x$ ，若元素 $y$ 盖住 $x$ ，则可以将 $x,y$ 间的关系用图形表示，即：哈斯图

# 哈斯图

用小圆圈表示 $A$ 中的元素
若 $x≼y$ 且 $x≠y$ , 则 $x$ 在 $y$ 的下方
若 $x≼y$ 且 $x≠y$ , 并且 $A$ 中不存在另外的元素 $z$ , 满足 $x≼z$ , $z≼y$ , 则在 $x$ 与 $y$ 之间画一直线

# 拟序关系

设 $R$ 是集合 $A$ 中的反自反和传递的二元关系，则称 $R$ 是 $A$ 中的拟序关系 (“ $≺$ ”)

# 全序和全序集

设 $≼$ 是 $A$ 中的偏序关系，若对任意的 $x,y∈A$ ，必有 $x ≼ y$ 或 $y ≼ x$ ，即 $x$ 和 $y$ 可比较，则称 $≼$ 是 $A$ 中的线性次序关系或全序关系，又称全序或线性序。相应的偏序集 $(A,≼)$ 称为线性序集或全序集
显然，任一全序集也是偏序集，其哈斯图为一条链，
但是任一偏序集不一定是全序集合

# 最大（小）元素

设 $( X, ≼ )$ $(X, ≼)$ 是偏序集， $Y$ $Y$ 是 $X$ $X$ 的子集。若存在元素 $y∈ Y$ $y \in Y$ , 对于每一个 $y' ∈ Y$ $y^{'} \in Y$ ，
- 若有 $y' ≼ y$ ，则称 $y$ 是集合 $Y$ 的最大元素
- 若有 $y ≼y'$ ，则称 $y$ 是集合 $Y$ 的最小元素

# 性质

设 $( X, ≼ )$ 是偏序集， $Y$ 是 $X$ 的子集，如果 $Y$ 有最大（最小）元素，则必定是唯一的

# 极大（小）元素

设 $( X, ≼)$ $(X, ≼)$ 是偏序集， $Y$ $Y$ 是 $X$ $X$ 的子集，若 $y ∈ Y$ $y \in Y$ ，且不存在 $y' ∈ Y$ $y^{'} \in Y$ ， $y≠ y'$ $y \neq = y^{'}$ ，
- 若有 $y ≼ y'$ ，则称 $y$ 是 $Y$ 的极大元素
- 若有 $y' ≼ y$ ，则称 $y$ 是 $Y$ 的极小元素

# 上（下）界

设 $( X, ≼ )$ $(X, ≼)$ 是偏序集， $Y\subseteq X$ $Y \subseteq X$ ，若 $x ∈ X$ $x \in X$ ，使得对任意 $y' ∈ Y$ $y^{'} \in Y$ ,
- 若有 $y'≼x$ ，则称 $x$ 是 $Y$ 的上界
- 若有 $x ≼ y'$ ，则称 $x$ 是 $Y$ 的下界

# 上（下）确界

设 $( X, ≼ )$ $(X, ≼)$ 是偏序集， $Y$ $Y$ 是 $X$ $X$ 的子集。
- $x$ 是 $Y$ 的上界，若对 $Y$ 的任一上界 $x'$ ，都有 $x ≼x'$ ，则称 $x$ 是 $Y$ 的上确界，记作 $LUB$ $Y$
- $x$ 是 $Y$ 的下界，若对于 $Y$ 的任一下界 $x'$ ，均有 $x' ≼x$ ，则称 $x$ 是 $Y$ 的下确界，记作 $GLB$ $Y$

# 函数

# 函数及其分类

# 函数的定义

设 $f$ $f$ 是集合 $A$ $A$ 到 $B$ $B$ 的关系
若称 $f$ $f$ 是集合 $A$ $A$ 到 $B$ $B$ 的函数或映射，记作 $f: A→B$ $f : A \to B$ 或 $A → B$ $A \to B$ 。
当 $(a,b)∈f$ $(a, b) \in f$ 时，通常记为 $b=f(a)$ $b = f (a)$ ， $b$ $b$ 称为 $a$ $a$ 在 $f$ $f$ 下的像，称 $a$ $a$ 为 $b$ $b$ 的原像。则 $f$ $f$ 满足下列两个条件：
- 对每个 $a∈A$ ，必存在 $b∈B$ ，使得 $(a,b)∈f$ —— 存在性条件
- 对每个 $a∈A$ ，只存在一个 $b∈B$ ，使得 $(a,b)∈f$ —— 唯一性条件
即：值域为函数的像集合

# 函数相等

设 $f:X→Y$ ， $g:Z→W$ ，如果 $f$ 和 $g$ 具有相同的定义域和值域，即 $X=Z$ 和 $Y=W$ ，并且对于所有的 $x∈X$ 和 $x∈Z$ ，都有 $f(x)=g(x)$ ，则称函数 $f$ 和 $g$ 相等，并记作 $f=g$

# 函数个数

设 $A$ ， $B$ 是非空有限集合，则从 $A$ 到 $B$ 共有 $|B|^{|A|}$ 个不同的函数
因为函数是一种特殊的关系，所以一个函数确定一个关系；但一个关系不一定确定一个函数

# 函数的分类

设 $f: A→B$ $f : A \to B$ 是一个函数：
- 对任意的 $a_1$ 和 $a_2∈A$ ，若 $a_1≠a_2$ ，均有 $f(a_1)≠f(a_2)$ ，则称 $f$ 为 $A$ 到 $B$ 的单射函数或一对一函数；否则，称 $f$ 为 $A$ 到 $B$ 的多对一函数。
- 如果对任意的 $b∈B$ ，均有 $a∈A$ ，使 $b=f(a)$ ，即 $C_f=B$ ，则 $f$ 为 $A$ 到 $B$ 的满射函数；否则，称 $f$ 为 $A$ 到 $B$ 的内射函数。
- 如果 $f$ 既是 $A$ 到 $B$ 的单射，又是 $A$ 到 $B$ 的满射，则称 $f$ 为 $A$ 到 $B$ 的双射函数或一一对应函数。特殊地，在一一对应函数 $f: A→B$ 中，若 $A=B$ ，则此函数叫做 $A$ 的变换。

# 函数分类结论

设 A，B 为有限集合，f 是从 A 到 B 的函数，则：
- $f$ 是单射的必要条件为 $|A|≤|B|$
- $f$ 是满射的必要条件为 $|B|≤|A|$
- $f$ 是双射的必要条件为 $|A|＝|B|$

# 特殊函数

设 $f$ 是一个函数，若对任意的 $a∈A$ ，均有 $f(a)=b$ ， $b∈B$ ，则称 $f$ 是从 $A$ 到 $B$ 的常值函数或常函数
设 $f$ 是一个函数，若对任意的 $a∈A$ ，均有 $f(a)=a$ ，则称 $f$ 是 $A$ 上的恒等函数
设 $f:R→R$ $f : R \to R$ 是一个函数，其中 $R$ $R$ 为实数集，
- 对任意 $a,b∈R$ ，若 $a<b$ ，必有 $f(a)≤f(b)$ ，则称 $f$ 为单调递增函数
- 对任意 $a,b∈R$ ，若 $a<b$ ，必有 $f(a)<f(b)$ ，则称 $f$ 为严格单调递增函数
设 $U$ 是全集，且 $A⊆U$ ，函数 $\Psi _A:U\to \{0,1\}$ 定义为: $\Psi_A=\begin{cases} 1,& a \in A\\ 0,& a \notin A \end{cases}$ 则称 $\Psi_A$ 是集合 $A$ 的特征函数

# 复合函数与逆函数

# 复合函数

# 复合函数定义

函数的合成运算可定义如下：设 $f : X→Y$ , $g : Y→Z$ 是两个函数，于是合成函数记为 $g\circ f : X→Z$
$\\g\circ f=\{(x,z)|x∈X且z∈Z且存在y∈Y且y=f(x)且z=g(y)\}$ 通常称为函数 $f$ 和 $g$ 的合成，确切的说， $g\circ f$ 称为 $f$ 和 $g$ 左合成，从 $f$ 和 $g$ 求得 $g\circ f$ 的运算 “ $\circ$ ” 称为左合成运算
关系的合成运算为 $f\circ g$ ，函数的合成运算为 $g\circ f$

# 复合函数定理

函数的合成运算是可结合的
设 $f$ $f$ 和 $g$ $g$ 是函数，并且有合成函数 $g\circ f$ $g \circ f$ , 则
- 如果 $f$ 和 $g$ 都是满射函数，则 $g \circ f$ 也是满射函数
- 如果 $f$ 和 $g$ 都是单射函数，则 $g\circ f$ 也是单射函数
- 如果 $f$ 和 $g$ 都是双射函数，则 $g\circ f$ 也是双射函数

# 逆函数

# 逆函数定义

设 $f : A→B$ 是一个双射函数，称 $f^{-1} : B→A$ 是 $f$ 的逆函数
在关系部分，曾定义了从集合 $X$ 到 $Y$ 的关系 $R$ 的逆关系，但是对于函数来说，交换序偶中的成员次序并不一定能保证得到的仍然是个函数
设 $f:A→B$ 是一一对应的函数，则 $f$ 的逆关系称为它的逆函数，记成 $f^{-1}: B→A$ 。这时称函数 $f$ 是可逆的

# 逆函数的定理

函数 $f : A→B$ $f : A \to B$ ，若存在逆函数 $f^{-1} : B→A$ $f^{- 1} : B \to A$ ，则必须满足：
- 对任意的 $a∈A$ ，必有唯一的 $b∈B$ 与之对应；
- 对任意的 $b∈B$ ，必有唯一的 $a∈A$ 与之对应；

# 代数系统

# 代数系统的基本概念

# 二元运算

# 定义

设 $A, B, C$ 是非空集合，从 $A×B$ 到 $C$ 的一个函数 $f ：A×B→C$ 称为一个 $A×B$ 到 $C$ 的二元代数运算，简称二元运算
一个二元运算就是一个特殊的函数，该函数能够对 $a\in A$ 和 $b\in B$ 进行运算，得到 $C$ 中的一个元素 $c$ ，即 $\circ (a, b)＝c$ 。
中缀方法表示为： $a \circ b＝c$

# 特点

# 封闭性

如果 “ $\ast$ ” 是 $A×A$ 到 $A$ 的二元运算，则称运算 “ $\ast$ ” 对集合 $A$ 是封闭的，或者称 “ $\ast$ ” 是 $A$ 上的二元运算
设 “ $\ast$ ” 是一个 $A_1×A_2×…×A_n$ 到 $A$ 的 $n$ 元代数运算，如果 $A_1＝A_2＝…＝A_n＝A$ ，则称代数运算 “ $\ast$ ” 对集合 $A$ 是封闭的，或者称 “ $\ast$ ” 是 $A$ 上的 $n$ 元代数运算

# 代数系统的定义

设 $A$ 是非空集合， $\ast$ 是定义在 $A$ 上 $k$ 元封闭运算，称集合 $A$ 和 $\ast$ 所组成的系统称为代数系统，简称代数，记为 $(A, \ast )$
当 $A$ 是有限集合时，该代数系统称为有限代数系统，否则称为无限代数系统
注意：判断集合 $A$ $A$ 和其上的代数运算是否是代数系统，关键是判断两点：
- 集合 $A$ 非空
- 这些运算关于 $A$ 是否满足封闭性

# 同类型代数系统

设 $(A, \ast )$ 和 $(B, \circ )$ 是两个代数系统，若 “ $\circ$ ” 和 “ $\ast$ ” 都是 $k$ 元运算， $i = 1, 2, …, m$ ，则称这两个代数同类型

# 运算规律

# 结合律

设 $(A, \ast )$ 是二元代数系统，若对任意 $a, b, c∈A$ ，都有
$(a \ast b) \ast c＝a \ast (b \ast c)$
则称 “ $\ast$ ” 在 $A$ 上是可结合的，或称满足结合律

# 交换律

设 $(A, \ast )$ 是二元代数系统，若对任意 $a, b∈A$ ，都有
$a \ast b＝b \ast a$
则称 “ $\ast$ ” 在 $A$ 上是可交换的，或称 “ $\ast$ ” 满足交换律

# 消去律

设 $(A, \ast )$ $(A, *)$ 是二元代数系统，元素 $a∈A$ $a \in A$ ，
- 对任意 $x, y∈A$ ，都有如果 $a \ast x = a \ast y$ ，那 $x = y$ ，则称 $a$ 在 $A$ 中关于 “ $\ast$ ” 是左可消去元
- 对任意 $x, y∈A$ ，都有如果 $x \ast a = y \ast a$ ，那么 $x = y$ ，则称 $a$ 在 $A$ 中关于 “ $\ast$ ” 是右可消去元
- 如果 $a$ 既是 $A$ 左可消去元又是右可消去元，则称 $a$ 是 $A$ 的可消去元
- 若 $A$ 中所有元素都是可消去元，则称 “ $\ast$ ” 在 $A$ 上可消去，或称 “ $\ast$ ” 满足消去律

# 幂等律

设 $(A, \ast )$ 是二元代数系统，若元素 $a∈A$ ，满足 $a \ast a=a$ 则称 $a$ 是 $A$ 中关于 “ $\ast$ ” 的一个幂等元，简称 $a$ 为幂等元。若 $A$ 中的每一个元素都是幂等元，则称 “ $\ast$ ” 在 $A$ 中是幂等的，或称 “ $\ast$ ” 满足幂等律

# 幂

设 “ $\ast$ ” 是集合 $A$ 上可结合的二元运算， $a∈A$ ，则 $a \ast a∈A，a \ast a \ast a∈A，…，$ 由此，可以归纳定义 $a$ 的正整数幂方：
$a^1 = a，a^2 = a \ast a，a^3 = a^2 \ast a，… ， a^n = a^{n-1} \ast a，…$
对任意正整数 $n$ ， $m$ ，有以下等式： $a^n \ast a^m = a^{n+m}， (a^n)^m = a^{nm}$

# 分配律

设 “ $\ast$ $*$ ”、“ $\circ$ $\circ$ ” 是集合 A 上的二元运算， $(A, \ast , \circ)$ $(A, *, \circ)$ 是一个代数系统，对任意 $a,b,c\in A$ $a, b, c \in A$ ，
- $a\circ (b \ast c)=(a\circ b) \ast (a\circ c)$ ，
  则称运算 “ $\circ$ ” 对 “ $\ast$ ” 在 $A$ 上满足左分配律 (或第一分配律)
- $(b \ast c) \circ a=(b\circ a) \ast (c\circ a)$ ，
  则称运算 “ $\circ$ ” 对 “ $\ast$ ” 在 $A$ 上满足右分配律 (或第二分配律)
- 如果 “ $\circ$ ” 对 “ $\ast$ ” 既满足左分配律又满足右分配律，则称 “ $\circ$ ” 对 “ $\ast$ ” 在 $A$ 上满足分配律

# 吸收律

设 “ $\ast$ ”、“ $\circ$ ” 是集合 $A$ 上的二元运算， $(A, \ast , \circ )$ 是一个代数系统，如果对任意 $x, y∈A$ ，都有 $x \ast (x \circ y) = x，x \circ(x \ast y) = x$
则称 “ $\ast$ ” 和 “ $\circ$ ” 满足吸收律

# 特殊元

# 特殊元的定义

在代数系统中，有些元素有特殊性质，叫特殊元

# 单位元

设 $(A, \ast )$ $(A, *)$ 是二元代数系统，
- 若存在 $e∈A$ ，对任意 $a∈A$ ，都有 $a \ast e = e \ast a = a$ ，则称 $e$ 是 $A$ 中关于运算 “ $\ast$ ” 的一个单位元
- 若存在 $e_l∈A$ ，使得对任意 $a∈A$ ，都有 $e_l \ast a = a$ ，则称 $e_l$ 是 $A$ 中关于运算 “ $\ast$ ” 的一个左单位元
- 若存在 $e_r∈A$ ，使得对任意 $a∈A$ ，都有 $a \ast e_r = a$ ，则称 $e_r$ 是 $A$ 中关于运算 “ $\ast$ ” 的一个右单位元

# 零元

设 $(A, \ast )$ $(A, *)$ 是一个二元代数系统，
- 若存在 $θ∈A$ ，使得对任意 $a∈A$ ，都有 $a \ast θ = θ \ast a =θ$ ，则称 $θ$ 是 $A$ 中关于运算 “ $\ast$ ” 的一个零元
- 若存在 $θ_l∈A$ ，使得对任意 $a∈A$ ，都有 $θ_l \ast a = θ_l$ ，则称 $θ_l$ 是 $A$ 中关于运算 “ $\ast$ ” 的一个左零元
- 若存在 $θ_r∈A$ ，使得对任意 $a∈A$ ，都有 $a \ast θ_r = θ_r$ ，则称 $θ_r$ 是 $A$ 中关于运算 “ $\ast$ ” 的一个右零元。

# 逆元

设 $(A, \ast )$ $(A, *)$ 是二元代数系统， $e$ $e$ 是幺元， $a∈A$ $a \in A$ ，若存在一个元素 $b∈A$ $b \in A$ ，
- 使得： $a \ast b = b \ast a = e$ ，则称 $a$ 可逆，并称 $b$ 是 $a$ 的一个逆元，记为 $a^{-1}$
- 使得： $b \ast a = e$ ，则称 $a$ 左可逆，并称 $b$ 是 $a$ 的一个左逆元，记为 $a_l^{-1}$
- 使得： $a \ast b = e$ ，则称 $a$ 右可逆，并称 $b$ 是 $a$ 的一个右逆元，记为 $a_r^{-1}$

# 定理

设 $(A, \ast )$ 是一个代数系统，“ $\ast$ ” 满足结合律， $a∈A$ ， $a$ 可逆，则 $a$ 是可消去元
设 $(A, \ast )$ $(A, *)$ 是二元代数系统，
- 如果 $(A, \ast )$ 存在单位元，则单位元唯一
- 如果 $(A, \ast )$ 存在单位元，则该单位元一定是左、右单位元
- 如果 $(A, \ast )$ 存在左、右单位元，则该左、右单位元相等，且是单位元。
设 $(A, \ast )$ $(A, *)$ 是二元代数系统，
- 如果 $(A, \ast )$ 存在零元，则零元唯一
- 如果 $(A, \ast )$ 存在零元，则该零元一定是左、右零元
- 如果 $(A, \ast )$ 存在左、右零元，则该左、右零元相等，且是零元。
设 $(A, \ast )$ $(A, *)$ 是二元代数系统，“ $\ast$ $*$ ” 满足结合律且设 $e$ $e$ 是单位元，则对任意 $a∈A$ $a \in A$ ，
- 如果 $a$ 存在逆元，则逆元唯一
- 如果 $a$ 存在逆元，则该逆元一定是左、右逆元
- 如果 $a$ 存在左、右逆元，则该左、右逆元相等，且是逆元。
设 $(A, \ast )$ $(A, *)$ 是二元代数系统，“ $\ast$ $*$ ” 满足结合律， $a, b∈A$ $a, b \in A$ ，
- 如果 $a, b$ 分别有逆元 $a^{-1}, b^{-1}$ ，则 $(a \ast b)^{-1} = b^{-1} \ast a^{-1}$
- 如果 $a$ 是左（或右）可逆的元素，则 $a$ 是左（或右）可消去的元素
- 如果 $a$ 是可逆的元素，则 $a$ 是可消去的元素

# 同构

# 同构的定义

在现实社会中，存在着很多代数系统，但仔细分析这些众多的代数系统发现，有些代数系统，他们之间表面上似乎不相同，但他们本质上是 “相同” 的

# 同构的条件

必须是同型代数系统
两个集合的元素个数应相等
运算定义法则相同，即对应元素运算后的结果也对应

# 同态

# 同态的定义

设 $(A, \ast )$ 和 $(B, \circ)$ 为两个二元代数系统， $g$ 是 $A$ 到 $B$ 的函数。对任意 $x, y∈A$ ，都有 $g(x \ast y) = g(x) \circ g(y)$ ，则称 $g$ 是从 $(A, \ast )$ 到 $(B, \circ)$ 的同态映射，称 $g(A)$ 为同态像，其中 $g(A) = \{g(x) | x∈A\}$ 。如果存在一个从 $(A, \ast )$ 到 $(B, \circ )$ 的同态映射，则称 $(A, \ast )$ 与 $(B, \circ )$ 同态，记为 $(A, \ast )∽(B, \circ )$ 。当 $(A, \ast )= (B, \circ )$ 时，称其同态为自同态
当同态映射 $g$ 分别是单射、满射、双射时，分别称 $g$ 是单一同态映射、满同态映射、同构映射
如果存在一个从 $(A, \ast )$ 到 $(B, \circ )$ 的同构映射（单一同态映射、满同态映射），则称代数系统 $(A, \ast )$ 与 $(B, \circ )$ 同构（单一同态、满同态）。
用 $(A, \ast )≌(B, \circ )$ 表示 $(A, \ast )$ 与 $(B, \circ )$ 同构

# 命题逻辑

# 命题与命题联结词

# 命题

具有真假意义的陈述句称为命题
命题可以取一个 “值”，称为真值
真值只有 “真” 和 “假” 两种，分别用 “ $Ｔ$ ”(或 “ $１$ ”) 和 “ $Ｆ$ ”(或 “ $０$ ) 表示

# 命题的分类

原子命题 (简单命题)：不能再分解为更为简单命题的命题
复合命题：可以分解为原子命题的命题，这些原子命题之间通过如 “或者”、“并且”、“不”、“如果... 则...”、“当且仅当” 等这样的关联词和标点符号复合而构成一个复合命题。（优先级：否定→合取→析取→蕴涵→等价）

# 命题联结词

# 否定 $\neg$

设 $P$ 是任一命题，复合命题 “非 $P$ ”(或 “ $P$ 的否定”) 称为 $P$ 的否定式 (Negation)，记作 $\neg P$ ，“ $\neg$ ” 为否定联结词

# 合取 $\wedge$

设 $P$ 、 $Q$ 是任两个命题，复合命题 “ $P并且Q$ ”(或 “ $P和Q$ ”) 称为 $P$ 与 $Q$ 的合取式 (Conjunction)，记作 $P∧Q$ ，“ $∧$ ” 为合取联结词

# 析取 $\vee$

设 $P$ 、 $Q$ 是任两个命题，复合命题 “ $P或者Q$ ” 称为 $P$ 与 $Q$ 的析取式 (Disjunction)，记作 $P∨Q$ ，“ $∨$ ” 为析取联结词

# 蕴涵 $→$

设 $P$ 、 $Q$ 是任两个命题，复合命题 “ $如果P，则Q$ ” 称为 $P$ 与 $Q$ 的蕴涵式 (Implication)，记作 $P→Q$ ，“ $→$ ” 称为蕴涵联结词， $P$ 称为蕴涵式的前件， $Q$ 称为后件

# 等价 $\leftrightarrow$

设 $P、Q$ 是任两个命题，复合命题 “ $P当且仅当Q$ ” 称为 $P$ 与 $Q$ 的等价式 (Equivalence)，记作 $P\leftrightarrow Q$ ，“ $\leftrightarrow$ ” 称为等价联结词

# 说明

联结词与自然语言之间的对应并非一一对应：
- 合取联结词 “ $∧$ ” 对应自然语言的 “既… 又…”、“不仅… 而且…”、“虽然… 但是…”、“并且”、“和”、“与” 等
- 蕴涵联结词 “ $→$ ”,“ $P→Q$ ” 对应自然语言中的 “如 P 则 Q” , “只要 P 就 Q”,“P 仅当 Q”,“只有 Q 才 P”,“除非 Q 否则 $\neg$ P” 等
- 等价联结词 “ $↔$ ” 对应了自然语言中的 “等价”、“当且仅当”、“充分必要” 等
- 析取联结词 “ $\vee$ ” 对应的是相容（可兼）的或
- 否定联结词 “ $\neg$ ” 是自然语言中的 “非”、“不” 和 “没有” 等
当前件 $P$ 为假时，不管 $Q$ 的真假如何，则 $P→Q$ 都为真。此时称为 “善意推定”
复合命题的真值只取决于构成他们的各原子命题的真值，而与它们的内容、含义无关，与联结次所连接的两原子命题之间是否有关系无关

# 命题公式与符号化

# 命题公式的定义

一个特定的命题是一个常值命题，它不是具有值 “T”(“1”)，就是具有值 “F”(“0”)
一个任意的没有赋予具体内容的原子命题称为命题变量 (或命题变元)，该命题变量无具体的真值，它的变域是集合 $\{T，F\}$ (或 $\{0，1\}$ )
当原子命题是命题变元时，此复合命题也即为命题变元的 “函数”，且该 “函数” 的值仍为 “真” 或 “假” 值，这样的函数可形象地称为 “真值函数”, 或称为命题公式，此命题公式没有确切真值

# 公式的解释

# 定义

设 $P_1、P_2、…、P_n$ 是出现在公式 $G$ 中的所有命题变元，指定 $P_1、P_2、…、P_n$ 一组真值，则这组真值称为 $G$ 的一个解释，常记为 $I$

# 性质

一般来说，若有 $ｎ$ 个命题变元，则应有 $2^n$ 个不同的解释
如果公式 $G$ 在解释 $I$ 下是真的，则称 $I$ 满足 $G$ ；如果 $G$ 在解释 $I$ 下是假的，则称 $I$ 弄假 $G$

# 真值表

# 定义

将公式 $G$ 在其所有可能解释下的真值情况列成的表，称为 $G$ 的真值表

# 公式的等价性

# 基本等价式

# 交换律

$P∧Q\iff Q∧P$
$P∨Q\iff Q∨P$
$P\leftrightarrow Q\iff Q\leftrightarrow P$

# 结合律

$(P∧Q)∧R\iff P∧(Q∧R)$
$(P∨Q)∨R\iff P∨(Q∨R)$
$(P\leftrightarrow Q)\leftrightarrow R\iff P\leftrightarrow (Q\leftrightarrow R)$

# 分配律

$P∧(Q∨R)\iff (P∧Q)∨(P∧R)$
$P∨(Q∧R)\iff(P∨R)∧(P∨R)$

# 否定深入

$\neg \neg P \iff P$
$\neg (P∧Q) \iff \neg P∨ \neg Q$
$\neg (P\vee Q) \iff \neg P\wedge \neg Q$
$\neg (P → Q)\iff P ∧ \neg Q$
$\neg(P \leftrightarrow Q) \iff \neg P \leftrightarrow Q \iff P \leftrightarrow \neg Q$

# 联结词化归

$P∧Q\iff \neg（\neg P∨\neg Q）$
$P∨Q\iff \neg （\neg P∧\neg Q）$
$P→Q\iff \neg P∨Q$
$P \leftrightarrow Q \iff (P→Q)∧(Q→P) \iff (\neg P∨Q) ∧(\neg Q∨P) \iff (P ∧ Q) ∨(\neg P ∧ \neg Q)$

# 命题与集合的关系

将 $G，H$ 理解为某总体论域上的子集合，而规定 $G∧H$ 为两集合的公共部分（交集）， $G∨H$ 为两集合的全部（并集）， $\neg G$ 为总体论域（如矩形域）中 $G$ 的补集，将命题中的真值 “1” 理解为集合中的总体论域（全集），将命题中的真值 “0” 理解为集合中的空集

# 永真式、永假式与蕴含式

# 定义

公式 G 称为永真式，如果在它的所有解释之下都为 “真”
公式 G 称为永假式，如果在它的所有解释之下都为 “假”
公式 G 称为可满足的，如果它不是永假的

# 公式等价

# 定义

设 G、H 是公式，如果在任意解释 I 下，G 与 H 的真值相同，则称公式 G、H 是等价的，记作 $G\iff H$

# 定理

$G\iff H$ 等价的充分必要条件为 $G\implies H$ 且 $H\implies G$
公式 G、H 等价的充分必要条件是公式 $G\iff H$ 是永真公式

# 性质

由于 “ $\iff$ $⟺$ ” 不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：
- 自反性 G=G
- 对称性若 G=H，则 H=G
- 传递性若 G=H，H=S，则 G=S

# 命题逻辑推理

# 基本蕴含式

$(P \to Q) \land (Q \to R) \implies P \to R$ (假言三段论)

# 定理

若前提集合为 $\{ H_1，H_2，…，H_m \}$ , 结论为 $P→ Q$ ，则 $\{ H_1，H_2，…，H_m \}\implies P\to Q$ 等价于 $\{H_1，H_2，…，H_m，P\}\implies Q$ (CP 规则)

# 推理规则

$P \to Q, Q \to R \vdash P \to R$

# 公式蕴涵的证明方法

真值表法
证 $G \to H$ 是恒真公式
利用一些基本等价式及蕴涵式进行推导
任取真值 I，若 I 满足 G，往证 I 满足 H
反证法，设结论假，往证前提假

# 三个基本推理规则

P 规则 (前提引入规则)：前提总是可用
T 规则 (推理引入规则)：推理中允许使用推理规则，所得结果在后面的推理中可用
CP 规则 (附加前提引入规则) ：证明 $P\to Q$ 时可将 P 作为附加前提引入

# 范式

# 定义

# 合取式

在一公式中，仅由命题变元及其否定构成的合取，称该公式为合取式
其中每个命题变元或其否定，称为合取项

# 析取式

在一公式中，仅由命题变元及其否定构成的析取，称该公式为析取式
其中每个命题变元或其否定，称为析取项

# 析取范式

一个命题公式 A 称为析取范式可表示为：多个合取式的析取

# 合取范式

一个命题公式 A 称为合取范式可表示为：多个析取式的合取

# 定理

合取式为永假式的充要条件是：它同时含有某个命题变元及其否定
析取式为永真式的充要条件是：它同时含有某个命题变元及其否定
对于任何一命题公式，都存在与其等价的析取范式和合取范式

# 范式的应用

公式 A 为永假式的充要条件是其析取范式中每个简单合取式至少包含一个命题变元及其否定
公式 A 为永真式的充要条件是其合取范式中每个简单析取式至少包含一个命题变元及其否定

# 公式的主范式

# 最小项

在含有 n 个命题变元的合取式中，若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该合取式为最小项
n 个命题变元共形成 $2^n$ 个最小项
任意两个不同的最小项的合取式是永假的： $m_i∧m_j\iff F,i≠j$
所有最小项之析取为永真： $\bigvee\limits_{i=1}^n m_i \iff T$
每个最小项只有一个真值组合为真

# 最大项

在 n 个命题变元的析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该析取式为最大项
任何两个不同最大项之析取是永真的，即： $M_i∨M_j\iff T,i≠j$
所有最大项之合取为永假，即： $\bigwedge\limits_{i=1}^n M_i \iff F$
每个最大项只有一个真值组合为假，且其真值 0 位于主对角线上

# 主析取范式

在给定公式的析取范式中，若其合取式都是最小项，则称该范式为主析取范式
任意含 n 个命题变元的非永假命题公式 A，都存在与其等价的主析取范式
任意含 n 个命题变元的非永假命题公式，其主析取范式是惟一的

# 主合取范式

在给定公式的合取范式中，若其所有简单析取式都是最大项，称该范式为主合取范式
任意含有 n 个命题变元的非永真命题公式 A，都存在与其等价的主合取范式
任意含 n 个命题变元的非永真命题公式 A，其主合取范式是唯一的

# 求法

公式化归法
真值表法

# 主析取范式与主合取范式之间的关系

由于主范式是由最小项或最大项构成，由其定义，可知两者有下列关系： $\neg m_i\iff M_i, \neg M_i\iff m_i$
因此，主析取范式和主合取范式有着 “互补” 关系，即由公式的主析取范式可以求出其主合取范式

# 主范式的应用

根据主范式的定义和定理，可以判定含 n 个命题变元的公式，其关键是先求出给定公式的主范式Ａ；其次按下列条件判定之：
- 若 $A\iff Ｔ$ ，或 A 可化为与其等价的、含 $2^n$ 个最小项的主析取范式，则 A 为永真式
- 若 $A\iff Ｆ$ ，或 A 可化为与其等价的、含 $2^n$ 个最大项的主合取范式，则 A 为永假式
- 若 A 不与Ｔ或者Ｆ等价，且又不含 $2^n$ 个最小项或最大项，则 A 为可满足的
由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的

# 推理规则

# “ $\implies$ ” 与 “ $\to$ ” 的不同

“ $→$ ” 仅是一般的蕴涵联结词， $G→H$ 的结果仍是一个公式，而 “ $⟹$