# 集合论

# 集合的基本概念

# 集合的定义

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

# 集合的元素

  • 组成一个集合的那些对象或单元称为这个集合的元素,通常,用小写的英文字母aa,bb,cc,…,或者a1a_1,a2a_2,b1b_1,b2b_2… 表示集合中的元素

# 属于

  • 设 A 是一个集合,a 是集合 A 中的元素,记以aAa \in A,读作aa 属于AA;若aa 不是集合AA 中的元素,则记以aAa \notin A,读作aa 不属于AA

# 有限集

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

# 无限集

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

# 空集

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

# 全集

  • 约定,所讨论的对象的全体称为全集 (universal set),记作EEUU,我们所讨论的集合都是全集的子集

  • 全集是相对的

# 集合的元素数

  • AA 是有穷集合,AA 中元素的个数称为集合AA 的元素数,记为A|A|特别,=0|\varnothing|=0

# 集合的表示法

# 列举法

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

# 描述法

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

# 文氏图

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

# 集合的特征

# 确定性

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

# 互异性

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

# 无序性

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

# 多样性

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

# 集合间的关系

# 集合相等

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

# 集合包含

# 子集

  • AABB 是两个集合,若AA 的元素都是BB 的元素,则称AABB 的子集 (subset) ,也称BB 包含AA,或AA 包含于BB,记以ABA \subseteq B,或BAB \supseteq A

# 真子集

  • ABA \subseteq B,且ABA \neq B,则称AABB 的真子集 (proper subset),也称BB 真包含AA,或AA 真包含于BB,记以ABA \subset B,或BAB \supset A

# 重要结论

  • 对任意集合AA, 有AAA ⊆ A
  • \varnothing 是任意集合的子集,且空集是唯一的
  • 对于任意两个集合AABBA=BA=B 当且仅当ABA⊆BBAB⊆ A

# 幂集

# 定义

  • AA 是集合,AA 的所有子集为元素组成的集合称为AA 的幂集,记以ρ(A)ρ(A)2A2^Aρ(A)={SSA}ρ(A)=\{S|S ⊆ A\}

# 性质

  • 若 A 为有穷集,A=n|A|=n,则2A=ρ(A)=Cn0+Cn1++Cnn=2n|2^A | = |ρ(A)|= C_n^0 + C_n^1 + … + C_n^n =2^n
  • xρ(A)x∈ρ(A) 当且仅当xAx⊆A
  • AABB 是两个集合,ABA⊆B 当且仅当ρ(A)ρ(B)ρ(A)⊆ρ(B)

# 集合运算

# 集合的并集

  • AABB 是两个集合。所有属于AA 或者属于BB 的元素组成的集合,称为AABB 的并集,记以ABA∪B。即AB={xxAxB}A∪B=\{x|x∈A或x∈B\}

# 集合的交集

  • AABB 是两个集合。由属于AA 又属于BB 的元素组成的集合,称为AABB 的交集,记以ABA∩B。即AB={xxAxB}A∩B=\{x|x∈A且x∈B\}

# 并集和交集的推广

  • A1A_1A2A_2,…,AnA_nnn 个集合,则:A1A2AnA_1∪A_2∪…∪A_n,简记为i=1nAi\bigcup\limits_{i=1}^nA_i

  • A1A2AnA_1∩A_2∩…∩A_n,简记为i=1nAi\bigcap\limits_{i=1}^n A_i

# 集合的补集

  • AA 是一个集合,全集EEAA 的差集称为AA 的补集,记以A\sim A,即A=EA\sim A=E-A

  • 特别, =E\sim \varnothing=EE=\sim E= \varnothing

# 集合的差集

  • AABB 是两个集合。由属于集合AA 而不属于集合BB 的所有元素组成的集合,称为AABB 的差集,记以ABA-B。即AB={xxAxB}A-B=\{x|x∈A且x ∉B\}

# 集合的对称差

  • AABB 是两个集合。则AABB 的和 (对称差), 记以ABA⊕B, 定义为AB=(AB)(BA)A⊕B=(A-B)∪(B-A),即AB={x(xA)(xB)(xB)(xA)}A \oplus B=\{x|(x \in A)且(x \notin B)或(x \in B)且(x \notin A)\}
  • AABB 的对称差还有一个等价的定义,即AB=(AB)(AB)A⊕B=(A∪B)-(A∩B)

# 集合的运算律

# 等幂律

  • AA=AA∩A=A
  • AA=AA∪A=A

# 交换律

  • AB=BAA∩B=B∩A
  • AB=BAA∪B=B∪A

# 结合律

  • (AB)C=A(BC)(A∩B)∩C=A∩(B∩C)
  • (AB)C=A(BC)(A∪B)∪C=A∪(B∪C)

# 分配律

  • A(BC)=(AB)(AC)A∩(B∪C)=(A∩B)∪(A∩C)
  • A(BC)=(AB)(AC)A∪(B∩C)=(A∪B)∩(A∪C)

# 吸收律

  • A(AB)=AA∩(A∪B)=A
  • A(AB)=AA∪(A∩B)=A

# 互补律

  • AA=\sim A∩A= \varnothing
  • AA=E\sim A∪A=E

# 德摩根律

  • (AB)=AB\sim (A∩B)=\sim A ∪ \sim B
  • (AB)=AB\sim(A∪B)=\sim A ∩ \sim B

# 同一律

  • EA=AE∩A=A
  • A=A\varnothing ∪A=A

# 零一律

  • A=\varnothing∩A=\varnothing

  • EA=EE∪A=E

# 双重否定律

  • (A)=A\sim (\sim A)=A

# 其他算律

  • AB=ABA-B=A∩ \sim B
  • AB=(AB)(BA)=(AB)(AB)A⊕B=(A-B)∪(B-A)=(A∪B)-(A∩B)
  • AA=A⊕A=\varnothing
  • =E\sim\varnothing=E
  • E=\sim E=\varnothing

# 有限集合的计数

# 容斥原理

  • AB=A+BAB|A∪B|=|A|+|B|-|A∩B|
  • ABC=A+B+CABACBC+ABC|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
  • A1A2AnA_1,A_2,…,A_nnn 个集合,则:i=1nAi=i=1nAii<jnAiAj+i<j<knAiAjAk+...+(1)n1A1A2A3...An|\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 中间式;
  • 根据基本运算符号的定义和运算定律转换。

# 集合成员表法

# 关系

# 序偶和笛卡尔积

# 序偶

# 定义

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

# 特点

  • aba≠b, 则(a,b)(b,a)(a,b)≠(b,a)
  • 两个有序对(a,b)(a,b)(c,d)(c,d) 相等当且仅当a=ca=cb=db=d

# 特征

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

# 笛卡尔积

# 定义

  • AABB 是两个集合,所有有序对(x,y)(x, y) 做成的集合(其中xAyB)(其中x∈A,y∈B),称为AABB 的笛卡儿积,记为A×BA×BA×B={(xy)xAyB}A×B=\{(x,y)|x∈A且y∈B\}
  • A1,A2,...,AnA_1,A_2 , ...,A_nnn 个集合,由所有有序nn 元组 (a1,a2,,ana_1,a_2,…,a_n) 组成的集合(其中aiAii=1,2,,n)(其中ai∈A_i,i=1,2, … ,n),称为A1,A2,...,AnA_1,A_2,...,A_n 的笛卡儿积,记以A1×A2×...×AnA_1×A_2 ×...×A_nA1×A2×...×An={(a1,a2,,an)aiAii=1,2,,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×B|=|A|× |B|

  • 对任意集合AA,有A×=A×\varnothing=\varnothing×A=\varnothing \times A=\varnothing

  • 笛卡儿积运算不满足交换律,即A×BB×AA×B≠B×A

  • 笛卡儿积运算不满足结合律,即(A×B)×CA×(B×C)(A×B)×C≠A×(B×C)

  • 笛卡儿积运算对并和交运算满足分配律, 即

    • A×(BC)=(A×B)(A×C)A×(B∪C)=(A×B)∪(A×C)
    • (BC)×A=(B×A)(C×A)(B∪C)×A=(B×A)∪(C×A)
    • A×(BC)=(A×B)(A×C)A×(B∩C)=(A×B)∩(A×C)
    • (BC)×A=(B×A)(C×A)(B∩C)×A=(B×A)∩(C×A)
  • AABBCCDD 是集合,若ACA⊆CBDB⊆D,则A×BC×DA×B ⊆ C×D

# 二元关系

# 定义

  • 给定任意集合AABB,若RA×BR⊆A×B,则称RR 为从AABB 的二元关系,特别在A=BA=B 时,称RRAA 上的二元关系

# 补充

  • 关系是一个集合,是序偶的集合
  • RR 是有序对的集合。若(x,y)R(x,y)∈R,则也表示为xRyx R y,即(x,y)R    xRy(x,y)∈ R \iff x R y
    • R=R =\varnothing,则称RRAABB空关系
    • R=A×BR =A×B,称RRAABB全域关系
    • R={(x,x)xA}R=\{(x,x)|x∈A\}AA 上的恒等关系,记为IAI_A
  • 当集合A,BA,B 都是有限集时,A×BA×B 共有2AB2^{|A|\cdot|B|} 个不同的子集,
    即从AABB 的不同关系共有2AB2^{|A|\cdot|B|}

# 定义域、值域和域

# 定义

  • RA×BR \subseteq A \times B,且
    {D(R)={x(y)(xRy)}R(R)={y(x)(xRy)}F(R)=D(R)R(R)\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)D(R)R(R)R(R)F(R)F(R) 分别是二元关系RR 的定义域、值域和域,显然D(R)AD(R) ⊆ AR(R)BR(R) ⊆ B

# 关系矩阵与关系图

# 关系矩阵

  • 给定集合A={a1,a2,,am}A=\{a_1,a_2,···,a_m \}B={b1,b2,,bn}B=\{b_1,b_2,···,b_n \},且RA×BR⊆A×B,若rij={1,aiRbj0,否则r_{ij}=\begin{cases} 1 ,& {a_i R b_j}\\0 ,& 否则 \end{cases}
    则称矩阵MR=(rij)M_R=(r _{i j})RR 的关系矩阵

# 关系图

  • 给定集合A={a1,a2,,am}A=\{a_1,a_2,···,a_m \}AA 上的关系RR,且RA×AR⊆A×A,若:以AA 中的元素为结点;对RR 中的元素(ai,aj)(a_i ,a_j ), 以aia_i 为起点,以aja_j 为终点,作有向边所构成的图,则称该图为RR 的关系图

# 关系运算

# 关系的并、交、补、差

  • 关系是序偶 (有序对) 的集合,因此可以对关系进行运算。
    R,SA×BR, S⊆A×B,则RSR∪SRSR ∩SR\sim RRSA×BR-S⊆A×B

# 关系的复合

# 定义

  • RR 是从集合XXYY 的关系,SS 是从YYZZ 的关系,把XXZZ 的关系定义为RSR\circ S。称RSR\circ S 是关系RRSS 的合成关系或复合关系,RS={(x,z)xX,zZ,至少存在一个yY(x,y)R(y,z)S}R\circ S=\{(x,z)|∃x∈X, ∃z∈Z, 至少存在一个y∈Y有(x , y)∈R且(y , z)∈S\}

# 定理

  • 已知集合X,Y,Z,WX,Y,Z,W,关系R1,R2,R3,R4R_1,R_2,R_3,R_4 如下XR1YR2R3ZR4WX\stackrel {R_1}\longrightarrow Y \stackrel {R_2R_3}\longrightarrow Z \stackrel {R_4}\longrightarrow W,则有:

    • 𝑅1(𝑅2𝑅3)=(𝑅1𝑅2)(𝑅1𝑅3)𝑅_1∘(𝑅_2∪𝑅_3)=(𝑅_1∘𝑅_2)∪(𝑅_ 1∘𝑅_3)
    • R1(R2R3)(R1R2)(R1R3)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)
    • (𝑅2𝑅3)𝑅4(𝑅2𝑅4)(𝑅3𝑅4)(𝑅_2∩𝑅_3)∘𝑅_4⊆(𝑅_2∘𝑅_4)∩(𝑅_3∘𝑅_4)
  • 已知集合X,Y,Z,WX, Y, Z, W,关系R1,R2,R3R_1, R_2, R_3 如下XR1YR2ZR3WX\stackrel {R_1}\longrightarrow Y \stackrel {R_2}\longrightarrow Z \stackrel {R_3}\longrightarrow W,则有:(R1R2)R3=R1(R2R3)(R_1 \circ R_2)\circ R_3=R_1\circ (R_2 \circ R_3) 结合律

  • RRRR=R(n)R\circ R\circ R \circ\dots\circ R=R^{(n)}

  • R(0)=IX={(x,x)xX}R^{(0)}=I_X=\{(x,x)|x\in X\}

# 逆关系

# 定义

  • RA×BR⊆A×B,则关系R={(y,x)(x,y)R}\overline R =\{(y,x)|(x,y)∈ R\}
    是集合BBAA 的关系,R\overline R 称为关系RR 的逆关系

# 定理

  • R1,R2,RR_1, R_2, RXXYY 的二元关系,则

    • R1R2=R1R2\overline{R_1∪ R_2} =\overline{R_1} ∪\overline{R_2}

    • R1R2=R1R2\overline{R_1 \cap R_2}=\overline {R_1} \cap \overline {R_2}

    • X×Y=Y×X\overline{X \times Y} = Y \times X

    • R=R\overline{\sim R}=\sim \overline{R}

    • R1R2=R1R2\overline{R_1-R_2}=\overline{R_1}-\overline{R_2}

    • SR    SRS \subseteq R \iff \overline{S}\subseteq\overline{R}

  • 已知集合X,Y,ZX, Y, Z,关系R,SR, S 如下,XRYSZX \stackrel {R}\longrightarrow Y \stackrel {S}\longrightarrow Z,则有:RS=SR\overline{R\circ S}=\overline{S}\circ\overline{R}

# 注意

  • RR 的关系矩阵转置即得R\overline R 的关系矩阵,即RRR\overline R 的关系矩阵互为转置矩阵
  • R\overline R 的前域与后域正好是RR 的后域和前域,即domR=ranRdomR=ran\overline RdomR=ranRdom\overline R=ranR
  • R=R|R|=|\overline R|

# 关系性质

# 自反性

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

# 反自反性

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

# 对称性

  • RA×AR⊆A×A,对于AA 中每个xxyy,若xRyxRy,则yRxyRx,称RR 是对称的,即A上关系R是对称的    (x)(y)(x,yAxRyyRx)在A上关系R是对称的\iff(∀x)(∀y)(x,y∈A且xRy→yRx)
  • 该定义表明了,在表示对称的关系RR 的有序对集合中,若有有序对(x,y)(x, y),则必定还会有有序对(y,x)(y, x)

# 反对称性

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

# 传递性

  • RA×AR⊆A×A,对于AA 中每个x,y,zx, y, z,若xRyyRzxRy且yRz,则xRzxRz,称RR 是传递的,即A上关系R是传递的    (x)(y)(z)(x,y,zAxRyyRzxRz)A上关系R是传递的 \iff (∀x)(∀y)(∀z)(x,y,z∈A且xRy且yRz→xRz)
  • 该定义表明了,在表示可传递关系RR 的有序对集合中,若有有序对(x,y)(x, y)(y,z)(y, z),则必有有序对(x,z)(x, z)

# 结论

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

# 闭包运算

# 自反闭包

  • RRAA 上的二元关系,若RR'RR 的自反闭包,记作r(R)r(R),则:
    • RR' 是自反的
    • RRR⊆R'
    • 对任意的自反关系RR''RRR⊆R'',则必有RRR'⊆R''

# 对称闭包

  • RRAA 上的二元关系,若RR'RR 的对称闭包,记作s(R)s(R),则:
    • RR' 是对称的
    • RRR⊆R'
    • 对任意的对称关系RR''RRR⊆R'',则必有RRR'⊆R''

# 传递闭包

  • RRAA 上的二元关系,若RR'RR 的传递闭包,记作t(R)t(R),则:

    • RR' 是传递的
    • RRR⊆R'
    • 对任意的传递关系RR''RRR⊆R'',则必有RRR'⊆R''

# 定理

  • R 是 X 上的二元关系,则:
    • r(R)=R{(x,x)xX}=RIxr(R)=R∪\{(x,x)|x∈X\}=R∪I_x
    • s(R)=RRs(R) = R∪ \overline{R}
    • t(R)=RR(2)R(3)...R(n)t(R)=R∪ R^{(2)}∪ R^{(3)}...∪ R^{(n)}nn 为集合XX 的元素的个数
    • RR 是自反的    \iff r(R)r(R)
    • RR 是对称的    \iff s(R)=Rs(R)=R
    • RR 是传递的    \iff t(R)t(R)

# 等价关系

# 定义

  • RR 是集合XX 上的二元关系,如果RR 是自反的、对称的、传递的,那么称RR 是等价关系

# 划分

  • 设集合A={S1,S2,,Sm}A=\{S_1, S_2 , …, S_m\},SiS_iSS 的非空子集,如果称AASS 的一个划分,称SiS_i 为划分的块,则:
    • SiS_i 之间是不相交的
    • S1S2Sm=SS_1∪S_2∪…∪S_m = S

# 等价类

# 定义

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

# 性质

  • x[x]x\in[x]
  • y[x]y\in[x], 则[y]=[x][y]=[x]
  • y[x]y\in[x], 则[y][x]=[y]∩[x]=\varnothing

# 定理

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

# 偏序关系

# 定义

  • RR 是集合AA 中的二元关系,如果RR 是自反的、反对称的和可传递的,则称RRAA 中的偏序关系。
  • 通常用符号 “” 来标记偏序关系RR

# 偏序集

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

# 哈斯图

  • 用小圆圈表示AA 中的元素
  • xyx≼yxyx≠y, 则xxyy 的下方
  • xyx≼yxyx≠y, 并且AA 中不存在另外的元素zz, 满足xzx≼z,zyz≼y, 则在xxyy 之间画一直线

# 拟序关系

  • RR 是集合AA 中的反自反和传递的二元关系,则称RRAA 中的拟序关系 (“”)

# 全序和全序集

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

# 最大(小)元素

  • (X,)( X, ≼ ) 是偏序集,YYXX 的子集。若存在元素yYy∈ Y, 对于每一个yYy' ∈ Y
    • 若有yyy' ≼ y,则称yy 是集合YY 的最大元素
    • 若有yyy ≼y',则称yy 是集合YY 的最小元素

# 性质

  • (X,)( X, ≼ ) 是偏序集,YYXX 的子集,如果YY 有最大(最小)元素,则必定是唯一的

# 极大(小)元素

  • (X,)( X, ≼) 是偏序集,YYXX 的子集,若yYy ∈ Y,且不存在yYy' ∈ Yyyy≠ y'
    • 若有yyy ≼ y',则称yyYY 的极大元素
    • 若有yyy' ≼ y,则称yyYY 的极小元素

# 上(下)界

  • (X,)( X, ≼ ) 是偏序集,YXY\subseteq X,若xXx ∈ X,使得对任意yYy' ∈ Y,
    • 若有yxy'≼x,则称xxYY 的上界
    • 若有xyx ≼ y',则称xxYY 的下界

# 上(下)确界

  • (X,)( X, ≼ ) 是偏序集,YYXX 的子集。
    • xxYY 的上界,若对YY 的任一上界xx',都有xxx ≼x',则称xxYY 的上确界,记作LUBLUB YY
    • xxYY 的下界,若对于YY 的任一下界xx',均有xxx' ≼x,则称xxYY 的下确界,记作GLBGLB YY

# 函数

# 函数及其分类

# 函数的定义

  • ff 是集合AABB 的关系
    若称ff 是集合AABB 的函数或映射,记作f:ABf: A→BABA → B
    (a,b)f(a,b)∈f 时,通常记为b=f(a)b=f(a)bb 称为aaff 下的像,称aabb 的原像。则ff 满足下列两个条件:
    • 对每个aAa∈A,必存在bBb∈B,使得(a,b)f(a,b)∈f—— 存在性条件
    • 对每个aAa∈A,只存在一个bBb∈B,使得(a,b)f(a,b)∈f—— 唯一性条件
  • 即:值域为函数的像集合

# 函数相等

  • f:XYf:X→Yg:ZWg:Z→W,如果ffgg 具有相同的定义域和值域,即X=ZX=ZY=WY=W,并且对于所有的xXx∈XxZx∈Z,都有f(x)=g(x)f(x)=g(x),则称函数ffgg 相等,并记作f=gf=g

# 函数个数

  • AABB 是非空有限集合,则从AABB 共有BA|B|^{|A|} 个不同的函数
  • 因为函数是一种特殊的关系,所以一个函数确定一个关系;但一个关系不一定确定一个函数

# 函数的分类

  • f:ABf: A→B 是一个函数:
    • 对任意的a1a_1a2Aa_2∈A,若a1a2a_1≠a_2,均有f(a1)f(a2)f(a_1)≠f(a_2),则称ffAABB单射函数一对一函数;否则,称ffAABB多对一函数
    • 如果对任意的bBb∈B,均有aAa∈A,使b=f(a)b=f(a),即Cf=BC_f=B,则ffAABB满射函数;否则,称ffAABB内射函数
    • 如果ff 既是AABB单射,又是AABB满射,则称ffAABB双射函数一一对应函数。特殊地,在一一对应函数f:ABf: A→B 中,若A=BA=B,则此函数叫做AA 的变换。

# 函数分类结论

  • 设 A,B 为有限集合,f 是从 A 到 B 的函数,则:
    • ff 是单射的必要条件为AB|A|≤|B|
    • ff 是满射的必要条件为BA|B|≤|A|
    • ff 是双射的必要条件为AB|A|=|B|

# 特殊函数

  • ff 是一个函数,若对任意的aAa∈A,均有f(a)=bf(a)=bbBb∈B,则称ff 是从AABB常值函数常函数
  • ff 是一个函数,若对任意的aAa∈A,均有f(a)=af(a)=a,则称ffAA 上的恒等函数
  • f:RRf:R→R 是一个函数,其中RR 为实数集,
    • 对任意a,bRa,b∈R,若a<ba<b,必有f(a)f(b)f(a)≤f(b),则称ff 为单调递增函数
    • 对任意a,bRa,b∈R,若a<ba<b,必有f(a)<f(b)f(a)<f(b),则称ff 为严格单调递增函数
  • UU 是全集,且AUA⊆U,函数ΨA:U{0,1}\Psi _A:U\to \{0,1\} 定义为: ΨA={1,aA0,aA\Psi_A=\begin{cases} 1,& a \in A\\ 0,& a \notin A \end{cases} 则称ΨA\Psi_A 是集合AA 的特征函数

# 复合函数与逆函数

# 复合函数

# 复合函数定义

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

# 复合函数定理

  • 函数的合成运算是可结合的
  • ffgg 是函数,并且有合成函数gfg\circ f, 则
    • 如果ffgg 都是满射函数,则gfg \circ f 也是满射函数
    • 如果ffgg 都是单射函数,则gfg\circ f 也是单射函数
    • 如果ffgg 都是双射函数,则gfg\circ f 也是双射函数

# 逆函数

# 逆函数定义

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

# 逆函数的定理

  • 函数f:ABf : A→B,若存在逆函数f1:BAf^{-1} : B→A,则必须满足:
    • 对任意的aAa∈A,必有唯一的bBb∈B 与之对应;
    • 对任意的bBb∈B,必有唯一的aAa∈A 与之对应;

# 代数系统

# 代数系统的基本概念

# 二元运算

# 定义

  • A,B,CA, B, C 是非空集合,从A×BA×BCC 的一个函数fA×BCf :A×B→C 称为一个A×BA×BCC 的二元代数运算,简称二元运算
  • 一个二元运算就是一个特殊的函数 ,该函数能够对aAa\in AbBb\in B 进行运算,得到CC 中的一个元素cc , 即 (a,b)c\circ (a, b)=c
    中缀方法表示为:abca \circ b=c

# 特点

# 封闭性

  • 如果 “ \ast” 是A×AA×AAA 的二元运算,则称运算 “ \ast” 对集合AA 是封闭的,或者称 “ \ast” 是AA 上的二元运算
  • 设 “ \ast” 是一个A1×A2××AnA_1×A_2×…×A_nAAnn 元代数运算,如果A1A2AnAA_1=A_2=…=A_n=A,则称代数运算 “ \ast” 对集合AA 是封闭的,或者称 “ \ast” 是AA 上的nn 元代数运算

# 代数系统的定义

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

# 同类型代数系统

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

# 运算规律

# 结合律

  • (A,)(A, \ast ) 是二元代数系统,若对任意a,b,cAa, b, c∈A,都有
    (ab)ca(bc)(a \ast b) \ast c=a \ast (b \ast c)
    则称 “ \ast” 在AA 上是可结合的,或称满足结合律

# 交换律

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

# 消去律

  • (A,)(A, \ast ) 是二元代数系统,元素aAa∈A
    • 对任意x,yAx, y∈A,都有如果ax=aya \ast x = a \ast y,那x=yx = y,则称aaAA 中关于 “ \ast” 是左可消去元
    • 对任意x,yAx, y∈A,都有如果xa=yax \ast a = y \ast a,那么x=yx = y,则称aaAA 中关于 “ \ast” 是右可消去元
    • 如果aa 既是AA 左可消去元又是右可消去元,则称aaAA 的可消去元
    • AA 中所有元素都是可消去元,则称 “ \ast” 在AA 上可消去,或称 “ \ast” 满足消去律

# 幂等律

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

#

  • 设 “ \ast” 是集合AA 上可结合的二元运算,aAa∈A,则aaAaaaAa \ast a∈A,a \ast a \ast a∈A,…,由此,可以归纳定义aa 的正整数幂方:
    a1=aa2=aaa3=a2aan=an1aa^1 = a,a^2 = a \ast a,a^3 = a^2 \ast a,… , a^n = a^{n-1} \ast a,…
  • 对任意正整数nnmm,有以下等式:anam=an+m(an)m=anma^n \ast a^m = a^{n+m}, (a^n)^m = a^{nm}

# 分配律

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

# 吸收律

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

# 特殊元

# 特殊元的定义

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

# 单位元

  • (A,)(A, \ast ) 是二元代数系统,
    • 若存在eAe∈A,对任意aAa∈A,都有 ae=ea=aa \ast e = e \ast a = a,则称eeAA 中关于运算 “ \ast” 的一个单位元
    • 若存在elAe_l∈A,使得对任意aAa∈A,都有 ela=ae_l \ast a = a,则称ele_lAA 中关于运算 “ \ast” 的一个左单位元
    • 若存在erAe_r∈A,使得对任意aAa∈A,都有 aer=aa \ast e_r = a,则称ere_rAA 中关于运算 “ \ast” 的一个右单位元

# 零元

  • (A,)(A, \ast ) 是一个二元代数系统,
    • 若存在θAθ∈A,使得对任意aAa∈A,都有aθ=θa=θa \ast θ = θ \ast a =θ,则称θθAA 中关于运算 “ \ast” 的一个零元
    • 若存在θlAθ_l∈A,使得对任意aAa∈A,都有θla=θlθ_l \ast a = θ_l,则称θlθ_lAA 中关于运算 “ \ast” 的一个左零元
    • 若存在θrAθ_r∈A,使得对任意aAa∈A,都有aθr=θra \ast θ_r = θ_r,则称θrθ_rAA 中关于运算 “ \ast” 的一个右零元。

# 逆元

  • (A,)(A, \ast ) 是二元代数系统,ee 是幺元,aAa∈A,若存在一个元素bAb∈A
    • 使得:ab=ba=ea \ast b = b \ast a = e,则称aa 可逆,并称bbaa 的一个逆元,记为a1a^{-1}
    • 使得:ba=eb \ast a = e,则称aa 左可逆,并称bbaa 的一个左逆元,记为al1a_l^{-1}
    • 使得:ab=ea \ast b = e,则称aa 右可逆,并称bbaa 的一个右逆元,记为ar1a_r^{-1}

# 定理

  • (A,)(A, \ast ) 是一个代数系统,“ \ast” 满足结合律,aAa∈Aaa 可逆,则aa 是可消去元
  • (A,)(A, \ast ) 是二元代数系统,
    • 如果(A,)(A, \ast ) 存在单位元,则单位元唯一
    • 如果(A,)(A, \ast ) 存在单位元,则该单位元一定是左、右单位元
    • 如果(A,)(A, \ast ) 存在左、右单位元,则该左、右单位元相等,且是单位元。
  • (A,)(A, \ast ) 是二元代数系统,
    • 如果(A,)(A, \ast ) 存在零元,则零元唯一
    • 如果(A,)(A, \ast ) 存在零元,则该零元一定是左、右零元
    • 如果(A,)(A, \ast ) 存在左、右零元,则该左、右零元相等,且是零元。
  • (A,)(A, \ast ) 是二元代数系统,“ \ast” 满足结合律且设ee 是单位元,则对任意aAa∈A
    • 如果aa 存在逆元,则逆元唯一
    • 如果aa 存在逆元,则该逆元一定是左、右逆元
    • 如果aa 存在左、右逆元,则该左、右逆元相等,且是逆元。
  • (A,)(A, \ast ) 是二元代数系统,“ \ast” 满足结合律,a,bAa, b∈A
    • 如果a,ba, b 分别有逆元a1,b1a^{-1}, b^{-1},则(ab)1=b1a1(a \ast b)^{-1} = b^{-1} \ast a^{-1}
    • 如果aa 是左(或右)可逆的元素,则aa 是左(或右)可消去的元素
    • 如果aa 是可逆的元素,则aa 是可消去的元素

# 同构

# 同构的定义

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

# 同构的条件

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

# 同态

# 同态的定义

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

# 命题逻辑

# 命题与命题联结词

# 命题

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

# 命题的分类

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

# 命题联结词

# 否定¬\neg

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

# 合取\wedge

  • PPQQ 是任两个命题,复合命题 “P并且QP并且Q”(或 “PQP和Q”) 称为PPQQ 的合取式 (Conjunction),记作PQP∧Q,“” 为合取联结词

# 析取\vee

  • PPQQ 是任两个命题,复合命题 “P或者QP或者Q” 称为PPQQ 的析取式 (Disjunction),记作PQP∨Q,“” 为析取联结词

# 蕴涵

  • PPQQ 是任两个命题,复合命题 “如果P,则Q如果P,则Q” 称为PPQQ 的蕴涵式 (Implication),记作PQP→Q,“” 称为蕴涵联结词,PP 称为蕴涵式的前件,QQ 称为后件

# 等价\leftrightarrow

  • PQP、Q 是任两个命题,复合命题 “P当且仅当QP当且仅当Q” 称为PPQQ 的等价式 (Equivalence),记作PQP\leftrightarrow Q,“\leftrightarrow” 称为等价联结词

# 说明

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

# 命题公式与符号化

# 命题公式的定义

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

# 公式的解释

# 定义

  • P1P2PnP_1、P_2、…、P_n 是出现在公式GG 中的所有命题变元,指定P1P2PnP_1、P_2、…、P_n 一组真值,则这组真值称为GG 的一个解释,常记为II

# 性质

  • 一般来说,若有个命题变元,则应有2n2^n 个不同的解释
  • 如果公式GG 在解释II 下是真的,则称II 满足GG;如果GG 在解释II 下是假的,则称II 弄假GG

# 真值表

# 定义

  • 将公式GG 在其所有可能解释下的真值情况列成的表,称为GG 的真值表

# 公式的等价性

# 基本等价式

# 交换律

  • PQ    QPP∧Q\iff Q∧P
  • PQ    QPP∨Q\iff Q∨P
  • PQ    QPP\leftrightarrow Q\iff Q\leftrightarrow P

# 结合律

  • (PQ)R    P(QR)(P∧Q)∧R\iff P∧(Q∧R)
  • (PQ)R    P(QR)(P∨Q)∨R\iff P∨(Q∨R)
  • (PQ)R    P(QR)(P\leftrightarrow Q)\leftrightarrow R\iff P\leftrightarrow (Q\leftrightarrow R)

# 分配律

  • P(QR)    (PQ)(PR)P∧(Q∨R)\iff (P∧Q)∨(P∧R)
  • P(QR)    (PR)(PR)P∨(Q∧R)\iff(P∨R)∧(P∨R)

# 否定深入

  • ¬¬P    P\neg \neg P \iff P
  • ¬(PQ)    ¬P¬Q\neg (P∧Q) \iff \neg P∨ \neg Q
  • ¬(PQ)    ¬P¬Q\neg (P\vee Q) \iff \neg P\wedge \neg Q
  • ¬(PQ)    P¬Q\neg (P → Q)\iff P ∧ \neg Q
  • ¬(PQ)    ¬PQ    P¬Q\neg(P \leftrightarrow Q) \iff \neg P \leftrightarrow Q \iff P \leftrightarrow \neg Q

# 联结词化归

  • PQ    ¬¬P¬QP∧Q\iff \neg(\neg P∨\neg Q)
  • PQ    ¬¬P¬QP∨Q\iff \neg (\neg P∧\neg Q)
  • PQ    ¬PQP→Q\iff \neg P∨Q
  • PQ    (PQ)(QP)    (¬PQ)(¬QP)    (PQ)(¬P¬Q)P \leftrightarrow Q \iff (P→Q)∧(Q→P) \iff (\neg P∨Q) ∧(\neg Q∨P) \iff (P ∧ Q) ∨(\neg P ∧ \neg Q)

# 命题与集合的关系

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

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

# 定义

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

# 公式等价

# 定义

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

# 定理

  • G    HG\iff H 等价的充分必要条件为G    HG\implies HH    GH\implies G
  • 公式 G、H 等价的充分必要条件是公式G    HG\iff H 是永真公式

# 性质

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

# 命题逻辑推理

# 基本蕴含式

  • (PQ)(QR)    PR(P \to Q) \land (Q \to R) \implies P \to R (假言三段论)

# 定理

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

# 推理规则

  • PQ,QRPRP \to Q, Q \to R \vdash P \to R

# 公式蕴涵的证明方法

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

# 三个基本推理规则

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

# 范式

# 定义

# 合取式

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

# 析取式

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

# 析取范式

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

# 合取范式

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

# 定理

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

# 范式的应用

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

# 公式的主范式

# 最小项

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

# 最大项

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

# 主析取范式

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

# 主合取范式

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

# 求法

  • 公式化归法
  • 真值表法

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

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

# 主范式的应用

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

# 推理规则

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

  • ” 仅是一般的蕴涵联结词,GHG→H 的结果仍是一个公式,而 “