Discrete Math Review (1)

1 命题逻辑

Definition(命题(Proposition))

命题是可以判定真假的陈述句(不可既真又假)。

Definition(命题逻辑的语言)

命题逻辑包括以下三个部分:

  1. 任意多个命题符号A0A_0, A1A_1, PP, QQ, …;
  2. 5个逻辑连词¬\lnot, \land, \lor, \to, \leftrightarrow
  3. 左括号,右括号

Definition(公式(Formula))

  1. 每个命题符号都是公式;
  2. 如果 α\alphaβ\beta 都是公式,则 (¬α\lnot \alpha), (αβ\alpha \land \beta), (αβ\alpha \lor \beta), (αβ\alpha \to \beta) 和 (αβ\alpha \leftrightarrow \beta) 都是公式
  3. 除此之外别无其他

Lemma (公式的括号匹配性质)

​ 每个公式中左右括号的数目相同。

Theorem(归纳原理)

P(α)P(\alpha) 为一个关于公式的性质。假设
(1) 对所有的命题符号 AiA_i, 性质 P(Ai)P(A_i) 成立; 并且
(2) 对所有的公式 α\alphaβ\beta , 如果 P(α)P(\alpha)P(β)P(\beta) 成立, 则 P((¬α))P((\lnot \alpha))P((αβ))P((\alpha * \beta)) 也成立,
那么 P(α)P(\alpha) 对所有的公式 α\alpha 都成立。

Definition(公式的长度)

公式 α\alpha 的长度 α\| \alpha \| 定义如下:

  1. 如果 α\alpha 是命题符号,那么α\| \alpha \| == 1;
  2. 如果 α\alpha == (¬β\lnot \beta), 则 α\| \alpha\| == 1 + β\|\beta \|
  3. 如果 α=(βγ)\alpha = (\beta * \gamma), 则 α=1+β+γ\| \alpha \| = 1 + \| \beta \| + \| \gamma \|

Theorem

  1. 交换律:…
  2. 结合律:…
  3. 分配率:…
  4. 德摩根律¬(AB)(¬A¬B)\lnot(A \land B) \leftrightarrow (\lnot A \lor \lnot B)
  5. 双重否定律¬¬AA\lnot \lnot A \leftrightarrow A
  6. 排中律A(¬A)A \lor (\lnot A)
  7. 矛盾律¬(A¬A)\lnot (A \land \lnot A)
  8. 逆否命题(AB)(¬B¬A)(A \to B) \leftrightarrow (\lnot B \to \lnot A)

Theorem

  1. α(βα)\alpha \to (\beta \to \alpha)
  2. (αβ)(¬αβ)(\alpha \to \beta) \leftrightarrow (\lnot \alpha \lor \beta)
  3. (α(βγ))((αβ)γ)(\alpha \to (\beta \to \gamma)) \leftrightarrow ((\alpha \land \beta) \to \gamma)
  4. (α(βγ))((αβ)(αγ))(\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to (\alpha \to \gamma))

Theorem(\land 推理规则)

  1. PQPQ\frac{P\quad Q}{P \land Q}
  2. PQP\frac{P \land Q}{P}
  3. PQQ\frac{P \land Q}{Q}

Theorem(¬\lnot ¬\lnot 推理规则)

  1. ᬬα\frac{\alpha}{\lnot \lnot \alpha}
  2. ¬¬αα\frac{\lnot \lnot \alpha}{\alpha}

Theorem(\to 推理规则)

  • pp\vdash p \to p
  • {¬q¬p}p¬¬q\{\lnot q \to \lnot p\} \vdash p \to \lnot \lnot q
  • {pqr}p(qr)\{p \land q \to r \} \vdash p \to (q \to r)

Theorem(\lor 推理规则)

  1. ααβ\frac{\alpha}{\alpha \lor \beta}
  2. βαβ\frac{\beta}{\alpha \lor \beta}
  3. αβαγβγγ\frac{\alpha \lor \beta \quad \alpha \to \gamma \quad \beta \to \gamma}{\gamma}

Theorem(\perp 推理规则)

  1. α¬α\frac{\alpha \quad \lnot \alpha}{\perp}

2 一阶谓词逻辑

Definition(一阶谓词逻辑的语言(Language))

​ 一阶谓词逻辑的语言包括了:

  1. 逻辑连词
  2. 量词符号: \forall \quad \exists
  3. 变元符号
  4. 左右括号

一些变换

  1. \exists x.\alpha \lor \exists x.\beta \leftrightarrow \exists x.(\alpha \lor \beta)

    \forall x.\alpha \rightarrow \exists x.\alpha

    \exists x.\forall y.\alpha \rightarrow \forall y.\exists x.\alpha

    \forall y.\exists x.\alpha \nrightarrow \exists x.\forall y.\alpha

    \forall x.\alpha \lor \forall x.\beta \rightarrow \forall x.(\alpha \lor \beta)

    \exists x.(\alpha \lor \beta) \rightarrow \exists x.\alpha \lor \exists x.\beta

    1. \forall x.(\alpha \land \beta) \leftrightarrow (\forall x.\alpha) \land \beta

      \exists x.(\alpha \lor \beta) \leftrightarrow (\exists x.\alpha) \lor \beta

      \exists x.(\alpha \land \beta) \leftrightarrow (\exists x.\alpha) \land \beta

  2. elim\forall - elim

    x.αα[t/x]\frac{\forall x. \alpha}{\alpha [t/x]} 即:可以用确定的t来代替任意的x,来消去任意符号

  3. intro\forall - intro

    [t] ..α[t/x]x.α\quad [t] \\ \ \quad. \\ \quad. \\ \frac{\alpha[t/x]}{\forall x. \alpha} 即: 任取t,如果能证明alpha对t成立,则alpha对所有x成立

  4. intro\exists - intro

    α[t/x]x.α\frac{\alpha[t/x]}{\exists x. \alpha} 即:用原本不在公式中的x来取代t,则可得到存在某个x使alpha成立,即可以获得存在符号

    for example:for\ example: P(c)x.P(x)P(c) \vdash \exists x.P(x)

  5. elim\exists - elim

    x.αα[x0/x]\frac{\exists x. \alpha}{\alpha[x_0/x]} 即:可用原本不在公式中的 x0x_0 来消去存在符号

    for example: x.αx.αfor\ example:\ \forall x. \alpha \to \exists x. \alpha


3 数学归纳法

Theorem(第一数学归纳法)

P(n)P(n) 是关于自然数的一个性质。如果

  1. P(0)P(0) 成立;
  2. 对任意自然数 nn,如果 P(n)P(n) 成立,则 P(n+1)P(n+1) 成立。

那么, P(n)P(n) 对所有自然数 nn 都成立。

Theorem(第二数学归纳法)

Q(n)Q(n) 是关于自然数的一个性质。如果

  1. Q(0)Q(0) 成立;
  2. 对任意自然数 nn, 如果 Q(0),Q(1),,Q(n)Q(0), Q(1), \dots, Q(n) 都成立,那么 Q(n+1)Q(n+1) 成立。

那么,Q(n)Q(n) 对所有自然数 nn 都成立。

Theorem(数学归纳法)

​ 第一数学归纳法与第二数学归纳法等价。

Definition(良序原理)

​ 自然数集的任意非空子集都有一个最小元

Theorem

​ 良序原理与(第一)数学归纳法等价

Theorem(费马小定理)

对于任意自然数 aa 与任意素数 ppapa (mod p)a^p \equiv a\ (mod\ p)

Theorem(做题步骤)

  1. Basis Step(基础步骤):
  2. Induction Hypothesis(归纳假设):
  3. Induction Step:(归纳步骤)

4 集合:基本概念与运算

集合的基本概念

Definition(集合)

集合就是任何一个有明确定义的对象的整体

Theorem(概括原则)

对于任意性质/谓词 P(x)P(x), 都存在一个集合 XX: X={xP(x)}X = \{x \| P(x) \}

Definition(外延性原理)

两个集合相等 (A=B)(A = B) 当且仅当它们包含相同的元素

Theorem(两个集合相等)

两个集合相等当且仅当它们互为子集(证明两个集合相等的基本方法).

A=bABBAA = b \Longleftrightarrow A \subseteq B \land B \subseteq A

集合的运算(一)

Definition(集合的并、交、相对补,绝对补)

  1. AB={xxAxB}A \cup B = \{x\|x \in A \lor x \in B \}
  2. AB={xxAxB}A \cap B = \{x\|x \in A \land x \in B \}
  3. AB={xxAxB}A \setminus B = \{x\| x \in A \land x \notin B \}
  4. A=UA={xUxA}\overline{A} = U \setminus A = \{x \in U \| x \notin A\}

Remark: 不存在包罗万象的全集

Theorem(分配律)

  1. A(BC)=(AB)(AC)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
  2. A(BC)=(AB)(AC)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

Theorem(吸收律)

  1. A(AB)=AA \cup (A \cap B) = A
  2. A(AB)=AA \cap (A \cup B) = A

Theorem

ABAB=BAB=AA \subseteq B \Longleftrightarrow A \cup B = B \Longleftrightarrow A \cap B = A

Theorem(相对补与绝对补的关系)

设全集为 UUAB=ABA \setminus B = A \cap \overline{B}

Theorem(德摩根律(绝对补))

设全集为 UU

  1. AB=AB\overline{A \cup B} = \overline{A} \cap \overline{B}
  2. AB=AB\overline{A \cap B} = \overline{A} \cup \overline{B}

Theorem

  1. A(BC)=(AB)C=(AB)(AC)A \cap (B \setminus C) = (A \cap B) \setminus C = (A \cap B) \setminus (A \cap C)

  2. A(BC)=(AC)(AB)A \setminus (B \setminus C) = (A \cap C) \cup (A \setminus B)

  3. ABBAA \subseteq B \Longrightarrow \overline{B} \subseteq \overline{A}

  4. AB(BA)A=BA \subseteq B \Longrightarrow (B \setminus A) \cup A = B

Theorem(对称差)

AB=(AB)(BA)=(AB)(BA)A \oplus B = (A \setminus B) \cup (B \setminus A) = (A \cap \overline{B}) \cup (B \cap \overline{A})

  1. (AB)C=A(BC)(A \oplus B) \oplus C = A \oplus (B \oplus C)
  2. AB=ABA \oplus B = \overline{A} \oplus \overline{B}
  3. AB=ACB=CA \oplus B = A \oplus C \Longrightarrow B = C

集合的运算(二)

Definition(广义并)

M\mathbb{M} 是一组集合 (a collection of sets)(a\ collection\ of\ sets)

M={xAM.xA}\bigcup M = \{x |\exists A \in M.x \in A \}

Definition(广义交)

M\mathbb{M} 是一组集合(a collection of sets)(a\ collection\ of\ sets)

M={xAM.xA}\bigcap M = \{x |\forall A \in M.x \in A \}

Theorem(德摩根律)

  1. XαIAα=αI(XAα)X \setminus \bigcup_{\alpha \in I}A_{\alpha} = \bigcap_{\alpha \in I}(X \setminus A_{\alpha})
  2. XαIAα=αI(XAα)X \setminus \bigcap_{\alpha \in I}A_{\alpha} = \bigcup_{\alpha \in I}(X \setminus A_{\alpha})

集合的运算(三)

Definition(幂集)

P(A)={XXA}\mathbb{P}(A) = \{X | X \subseteq A\}

Theorem

SP(X)SX{\color{Red} S \in \mathbb{P}(X) \Longleftrightarrow S \subseteq X}


5 集合:关系(Relation)

Definition(有序对公理(Ordered Pairs))

(a,b)=(c,d)a=cb=d(a, b) = (c, d) \Longleftrightarrow a = c \land b = d

Definition(Ordered Pairs)

(a,b)={{a},{a,b}}(a, b) {\color{Red} =} \{\{a\}, \{a, b\}\}

Definition(笛卡尔积)

The Cartesian product A×B{\color{Red} Cartesian\ product} \ A \times B of A and B{\color{Blue} A\ and\ B} is defined as

A×B={(a,b)aAbB}A \times B = \{(a, b)|a \in A \land b \in B \}

Remark:

  1. X×YY×XX \times Y \ne Y \times X
  2. (X×Y)×ZX×(Y×Z)(X \times Y) \times Z \neq X \times (Y \times Z)

Theorem(分配率)

A×(BC)=(A×B)(A×C)A×(BC)=(A×B)(A×C)A×(BC)=(A×B)(A×C)A \times (B \cap C) = (A \times B) \cap (A \times C) \\ A \times (B \cup C) = (A \times B) \cup (A \times C) \\ A \times (B \setminus C) = (A \times B) \setminus (A \times C)

Definition(关系(Relations))

A relation{\color{Red} relation} R from AA to BB is a subset of A×BA \times B:

RA×BR \subseteq A \times B

**Remark: ** 如果 A=BA = B 那么 RR 叫做 AA 上的关系

Definition

(a,b)RaRb(a,b)RaRb(a, b) \in R \qquad aRb \\ (a, b) \notin R \qquad a \overline{R} b

3 Definitions

  1. Definition(定义域)

dom(R)={ab.(a,b)R}dom(R) = \{a | \exists b.(a,b) \in R\}

  1. Definition(值域)

ran(R)={ba.(a,b)R}ran(R) = \{b |\exists a.(a,b) \in R\}

  1. Definition(域)

fld(R)=dom(R)ran(R)fld(R) = dom(R) \cup ran(R)

Theorem

dom(R)Rran(R)Rdom(R) \subseteq \bigcup \bigcup R \qquad ran(R) \subseteq \bigcup \bigcup R

5 Operations

Definition(逆(Inverse))

R1={(a,b)(b,a)R}R^{-1} = \{(a,b) | (b,a) \in R\}

Theorem

(R1)1=R(R^{-1})^{-1} = R

Theorem(关系的逆)

R,S均为关系(RS)1=R1S1R, S \text{均为关系} \\ (R \cup S)^{-1} = R^{-1} \cup S^{-1} \\ \cap \qquad \setminus \qquad 同理

Definition(左限制)

如果 RX×YR \subseteq X \times YSXS \subseteq X,那么从 RRSSXXYY 上的左限制:

RS={(x,y)RxS}R|_{S} = \{(x,y) \in R|{\color{Red} x\in S}\}

Definition(右限制)

如果 RX×YR \subseteq X \times YSYS \subseteq Y,那么从 RRSSXXYY 上的右限制:

RS={(x,y)RyS}R|^{S} = \{(x,y) \in R|{\color{Red} y \in S}\}

Definition(限制)

如果 RX×XR \subseteq X \times XSXS \subseteq X,那么从 RRSSXXYY 上的右限制:

RS={(x,y)RxSyS}R|_{S} = \{(x,y) \in R|{\color{Red} x \in S \land y \in S}\}

Definition(像(Image))

XX 在关系 RR 下的像是集合:

R[x]={bran(R)aX.(a,b)R}R[x] = \{b \in ran(R)|\exists a \in X.(a,b) \in R\}

Definition(逆像)

YY 在关系 RR 下的逆像是集合:

R1[Y]={adom(R)bY.(a,b)R}R^{-1}[Y] = \{a \in dom(R)|\exists b \in Y.(a, b) \in R\}

Theorem

R[X1X2]=R[X1]R[X2]R[X1X2]R[X1]R[X2]R[X1X2]R[X1]R[X2]R[X_1 \cup X_2] = R[X_1] \cup R[X_2] \\ R[X_1 \cap X_2] \subseteq R[X_1] \cap R[X_2] \\ R[X_1 \setminus X_2] \supseteq R[X_1] \setminus R[X_2]

Definition(复合(Composition))

RX×YR \subseteq X \times YSY×ZS \subseteq Y \times Z 的复合是关系:

RS={(a,c)b.(a,b)S(b,c)R}R \circ S = \{(a, c)|\exists b.(a,b) \in S \land (b,c) \in R\}

Theorem

(RS)1=S1R1(RS)T=R(ST)(XY)Z=(XZ)(YZ)(XY)Z(XZ)(YZ)(R \circ S)^{-1} = S^{-1} \circ R^{-1} \\ (R \circ S) \circ T = R \circ (S \circ T) \\ (X \cup Y) \circ Z = (X \circ Z) \cup (Y \circ Z) \\ (X \cap Y) \circ Z \subseteq (X \circ Z) \cap (Y \circ Z)

7 Properties

Definition

  1. 关系 RX×XR \subseteq X \times X自反ifif:

aX.(a,a)R\forall a \in X.(a, a) \in R

  1. 关系 RX×XR \subseteq X \times X反自反ifif:

aX.(a,a)R\forall a \in X.(a, a) \notin R

  1. 关系 RX×XR \subseteq X \times X对称ifif:

a,bX.aRbbRa\forall a, b \in X.aRb \to bRa

  1. 关系 RX×XR \subseteq X \times X反对称ifif:

a,bX.(aRbbRa)a=b\forall a, b \in X.(aRb \land bRa) \to a = b

  1. 关系 RX×XR \subseteq X \times X传递ifif:

a,b,cX.(aRbbRcaRc)\forall a, b, c \in X.(aRb \land bRc \to aRc)

  1. 关系 RX×XR \subseteq X \times X连接ifif:

a,bX.(aRbbRa)\forall a, b \in X.(aRb \lor bRa)

  1. 关系 RX×XR \subseteq X \times X三分ifif:

a,bX.(aRb,bRa,a=b只有一种存在)\forall a, b \in X.(aRb, bRa, a = b \text{只有一种存在})

Theorem

  1. RR 是对称的且传递的 R=R1R\Longleftrightarrow R = R^{-1} \circ R
  2. RR 是对称的 R1=R\Longleftrightarrow R^{-1} = R
  3. RR 是传递的 RRR\Longleftrightarrow R \circ R \subseteq R

Definition(等价关系)

RX×XR \subseteq X \times X 是一种 XX 上的等价关系 当且仅当 XX 上的关系 RR 是:

  • 自反的:aX.aRa\forall a \in X.aRa
  • 对称的:a,bX.(aRbbRa)\forall a, b \in X.(aRb \leftrightarrow bRa)
  • 传递的:a,b,cX.(aRbbRcaRc)\forall a, b, c \in X.(aRb \land bRc \rightarrow aRc)

Definition(划分(Partition))

一组集合 Π={AααI}\Pi = \{A_{\alpha} | \alpha \in I\} 是一种 XX 的划分当且仅当:

  1. (不空)

αI.Aα(αI.xX.xAα)\forall \alpha \in I.A_{\alpha} \neq \emptyset \\ (\forall \alpha \in I.\exists x \in X.x \in A_{\alpha})

  1. (不漏)

αIAα=X(xX.αI.xAα)\bigcup_{\alpha \in I} A_{\alpha} = X \\ (\forall x \in X. \exists \alpha \in I. x \in A_{\alpha})

  1. (不重)

α,βI.AαAβ=Aα=Aβ(α,βI.AαAβAα=Aβ)\forall \alpha, \beta \in I.A_{\alpha} \cap A_{\beta} = \emptyset \lor A_{\alpha} = A_{\beta} \\ (\forall \alpha, \beta \in I.A_{\alpha} \cap A_{\beta} \neq \emptyset \Longrightarrow A_{\alpha} = A_{\beta})

Definition(等价类)

RR 的等价类 aa 是一个集合:

[a]R={bX.(aRb)}[a]_{R} = \{b \in X.(aRb)\}

Definition(商集)

关系 RRXX 上的商集是一个集合:

X/R={[a]RaX}X / R = \{[a]_{R} | a \in X\}

Theorem

  1. X/R={[a]RaX}X / R = \{[a]_{R} | a \in X\}XX 的一个划分
  2. aX,bX.[a]R[b]R=[a]R=[b]R\forall a \in X, b \in X.[a]_{R} \cap [b]_{R} = \emptyset \lor [a]_{R} = [b]_{R}
  3. a,bX.([a]R=[b]RaRb)\forall a, b \in X.([a]_{R} = [b]_{R} \leftrightarrow aRb)

6 函数

Definition of Functions

Definition(Function)

fA×Bf \subseteq A \times B 是一个从 AABB 的函数 ifif:

aA.!bB.(a,b)f.{\color{Red} \forall} a \in A. {\color{Red} \exists!} b \in B.(a, b) \in f.

For Proof:

!bB.b,bB.(a,b)f(a,b)fb=b{\color{Red} \exists !b \in B}. \\ \forall b, b' \in B.(a, b) \in f \land (a, b') \in f \Longrightarrow b = b'

Special Funcition

Ix:XXX上的恒等函数xX.Ix(x)=xI_x : X \rightarrow X \\ X \text{上的恒等函数} \\ \forall x \in X.I_x(x) = x

Definition

XXYY 的所有函数的集合:

YX={f f:XY}Y^X = \{f\ | f : X \rightarrow Y\}

Theorem

没有一个集合可以包含所有的函数

Functions as Sets

Theorem(函数的外延性原理)

f,gf, g 都是函数:

f=gdom(f)=dom(g)(xdom(f).f(x)=g(x))f = g \Longleftrightarrow dom(f) = dom(g) \land (\forall x \in dom(f).f(x) = g(x))

Theorem

f:ABf : A \rightarrow B g:CDg: C \rightarrow D

fg:(AC)(BD)f \cap g: (A \cap C) \rightarrow (B \cap D)

fg:(AC)(BD)xdom(f)dom(g).f(x)=g(x)f \cup g : (A \cup C) \rightarrow (B \cup D) \Longleftrightarrow \forall x \in dom(f) \cap dom(g).f(x) = g(x)

Special Funtion

Definiton(单射函数 1-1)

f:ABf:ABa1,a2A.a1a2f(a1)f(a2)f : A \rightarrow B \qquad f : A {\color{Red} \rightarrowtail} B\\ \forall a_1, a_2 \in A. a_1 \ne a_2 \rightarrow f(a_1) \ne f(a_2)

For Proof

To prove that ff is 1-1:

a1,a2A.f(a1)=f(a2)a1=a2\forall a_1, a_2 \in A.f(a_1) = f(a_2) \rightarrow a_1 = a_2

To show that ff is not 1-1:

a1,a2A.a1a2f(a1)=f(a2){\color{Red} \exists} a_1, a_2 \in A. a_1 \ne a_2 \land f(a_1) = f(a_2)

Definition(满射函数 onto)

f:ABf:ABran(f)=Bf : A \rightarrow B \qquad f: A {\color{Red}\twoheadrightarrow} B \\ ran(f) = B

For Proof:

To prove that ff is onto:

bB.(aA.f(a)=b)\forall b \in B.({\color{Red} \exists} a\in A.f(a) = b)

To show that ff is not onto:

bB.(aA.f(a)b){\color{Red} \exists} b \in B.({\color{Red} \forall} a \in A.f(a) \ne b)

Definition(双射函数)

f:ABf:Aonto11B11 & ontof : A \rightarrow B \qquad f : A \xleftarrow[onto]{1 - 1} \xrightarrow[]{} B \\ 1 - 1\ \&\ onto

Definition(定义域与值域都一样的函数)

IX:XXI_X :X \to X

Theorem(Cantor Theorem)

如果 f:A2Af: A \to 2^A,那么 ff 不是双射函数。

  1. Not Onto:B2A.(aA.f(a)B)Not\ Onto: {\color{Red} \exists} B \in 2^A.({\color{Red} \forall}a \in A.f(a) \neq B)

  2. 如何构造这个 BB

    1. af(a),aBa \in f(a), a \notin B
    2. af(a),aBa \notin f(a), a \in B
  3. 反证法 Proof:aA.f(a)=BProof: \exists a \in A.f(a) = B

Functions as Relations

Definition(限制)

函数 ffXX 的限制是函数:

fX={(x,y)f  xX}f|_{X} = \{(x, y) \in f\ |\ x \in X\}

Definition(像和逆像)

  1. XXff 下的像是集合

  2. ff 只有在 and \subseteq and\ \cup 相等

    1. A1A2f(A1)f(A2)A_1 \subseteq A_2 \Longrightarrow f(A_1) \subseteq f(A_2)
    2. f(A1A2)=f(A1)f(A2)f(A_1 \cup A_2) = f(A_1) \cup f(A_2)
    3. f(A1A2) f(A1)f(A2)f(A_1 \cap A_2) \ f(A_1) \cap f(A_2)ff 是单射函数时取等号。
    4. f(A1A2)f(A1)f(A2)f(A_1 \setminus A_2) \supseteq f(A_1) \setminus f(A_2)
  3. f1f^{-1},,,\subseteq,\cap,\cup,\setminus 相等

    1. B1B2f1(B1)f1(B2)B_1 \subseteq B_2 \Longrightarrow f^{-1}(B_1) \subseteq f^{-1}(B_2)
    2. f1(B1B2)=f1(B1)f1(B2)f^{-1}(B_1 \cup B_2) = f^{-1}(B_1) \cup f^{-1}(B_2)
    3. f1(B1B2)=f1(B1)f1(B2)f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)
    4. f1(B1B2)=f1(B1)f1(B2)f^{-1}(B_1 \setminus B_2) = f^{-1}(B_1) \setminus f^{-1}(B_2)
  4. $f\ and\ f^{-1} $

    1. A0AA0f1(f(A0))A_0 \subseteq A \Longrightarrow A_0 \subseteq f^{-1}(f(A_0))
    2. B0f(f1(B0))B_0 \supseteq f(f^{-1}(B_0))ff 是满射函数且 B0ran(f)B_0 \subseteq ran(f) 时等号成立

Definition(函数的复合)

f:ABg:CDran(f)Cf: A \to B \qquad g: C \to D \\ ran(f) \subseteq C

那么复合函数 gf:ADg \circ f : A \to D 被定义为:

(gf)(x)=g(f(x))(g \circ f)(x) = g(f(x))

Theorem

f:ABg:BCh:CDh(gf)=(hg)ff: A \to B \qquad g:B \to C \qquad h:C \to D \\ h \circ (g \circ f) = (h \circ g) \circ f

Theorem

f:ABg:BCf: A \to B \qquad g : B \to C

  1. 如果 f,gf, g 是单射函数,那么 gfg \circ f 是单射函数
  2. 如果 f,gf, g 是满射函数,那么 gfg \circ f 是满射函数
  3. 如果 f,gf, g 是双射函数,那么 gfg \circ f 是双射函数
  4. 如果 gfg \circ f 是满射函数,那么 gg 是满射函数
  5. 如果 gfg \circ f 是单射函数,那么 ff 是单射函数

Definition(函数的逆)

函数 f:ABf: A\to B 是双射函数,那么函数 ff 的逆 f1BAf^{-1}:B \to A 被定义为

f1(b)=a    f(a)=bf^{-1}(b) = a \iff f(a) = b

Theorem

f:AB is bijectivef : A \to B\ is\ bijective

  1. ff1=IBf \circ f^{-1} = I_B
  2. f1f=IAf^{-1} \circ f = I_A
  3. f1 is bijectivef^{-1}\ is\ bijective
  4. g:BAfg=IBg=f1g: B \to A \land f \circ g = I_B \Longrightarrow g= f^{-1}
  5. g:BAgf=IAg=f1g: B \to A \land g \circ f = I_{A} \Longrightarrow g = f^{-1}

Theorem(复合的逆)

f:ABg:BC are bijectivef: A\to B \quad g: B \to C\ are\ bijective

  1. gf is bijectiveg \circ f\ is\ bijective
  2. (gf)1=f1g1(g \circ f)^{-1} = f^{-1} \circ g^{-1}

Theorem

f:ABg:BAf: A \to B \quad g:B \to A

  1. fg=IBgf=IAg=f1f \circ g = I_B \land g \circ f = I_A \Longrightarrow g = f^{-1}

7 集合:序关系

Definition(等价关系)

关系 RX×XR \subseteq X \times XXX 上的等价关系具有以下三个条件:

  1. 自反性

Definition(偏序关系)

X×X\preceq \subseteq X \times XXX 上的二元关系

如果 \preceq 满足以下条件,则称 \preceqXX 上的偏序关系

  1. \preceq 是自反的

Definition

(X,)(X, \preceq) 是偏序集。对任意 a,bXa, b \in X,

严格小于:

ab=ababa \prec b = a \preceq b \land a \neq b

被覆盖

ab=ab(cinX.(cacb)¬(acb))ab = a \prec b \land(\forall c in X.(c \neq a \land c \neq b) \rightarrow \lnot(a \preceq c \preceq b))

可比的

abbaa \preceq b \lor b \preceq a

不可比的

¬(abba)\lnot (a \preceq b \lor b \preceq a)

Definition(链与反链)

(X,)(X, \preceq) 是偏序集。

  • SXS \subseteq XSS 中的元素两两可比,则称 SS 是链。
  • SXS \subseteq XSS 中的元素两两不可比,则称 SS 是反链。

Theorem(Dilworth’s Theorem)

最大反链的大小 = 最小链分解中链的条数

Definition(严格偏序关系)

X×X\prec \subseteq X \times XXX 上的二元关系

如果 \prec 满足以下条件,则称 \precXX 上的严格偏序关系

  1. \prec反自反

Theorem

X×X\prec \subseteq X \times XXX 上的严格偏序关系。

对于任意 x,y,zXx, y, z \in X :

  1. xy,x=y,yxx \prec y, x = y, y \prec x 三者中至多有一个成立
  2. xyxx=yx \preceq y \preceq x \rightarrow x = y

Definition(全序关系)

X×X\preceq \subseteq X \times XXX 上的偏序,如果 \preceq 满足以下连接性,则称 \preceqXX 上的全序关系

a,bX.abba\forall a, b \in X.a \preceq b \lor b \preceq a

Definition(严格全序关系)

X×X\prec \subseteq X \times XXX 上的二元关系

如果 \prec 满足以下条件,则称 \precXX 上的严格全序关系

  1. 反自反

X×X\preceq \subseteq X \times XXX 上的偏序。设 aXa \in X。如果

xX.¬(ax)\forall x \in X. \lnot(a \prec x)

则称 aaXX极大元,如果

xX.¬(xa)\forall x \in X. \lnot (x \prec a)

则称 aaXX极小元

Definition(最大元与最小元)

X×X\preceq \subseteq X \times XXX 上的偏序。设 aXa \in X。如果

xX.xa\forall x \in X. x \preceq a

则称 aaXX最大元,如果

xX.ax\forall x \in X. a \preceq x

则称 aaXX最小元

Theorem

偏序集 (X,)(X, \preceq) 如果有最大元或最小元,则它们是唯一的。

Definition(线性拓展)

(X,)(X, \preceq) 是偏序集,(X,)(X, \preceq') 是全序集。如果

x,yX.xyxy\forall x, y \in X.x \preceq y \rightarrow x \preceq' y

则称 \preceq'\preceq线性拓展

Theorem

  1. 偏序集且 XX 为有限集,则 \preceq的线性拓展一定存在。
  2. 偏序集且 XX 为有限集,则极小元一定存在。

Definition(良序(Well-Ordering))

(X,)(X, \preceq) 是全序集。如果 XX 的任意非空子集都有最小元,则称 (X,)(X, \preceq) 为良序集。


8 集合:无穷

Definition(等势,A=B(AB)|A| = |B|(A \approx B))

AABB 是等势的 \Longleftrightarrow AABB 之间存在双射函数

Definition(Finite)

XX is finite ifif:

nN.X=n={0,1,,n1}\exists n \in \mathbb{N}.|X| = |n| = |\{0, 1, \dots, n - 1\}|

集合 XX 是有穷的当且仅当它与某个自然数等势

Definition(Infinite)

XX is infinite if it is note finite:

nN.Xn\forall n \in \mathbb{N}.|X| \neq n

  1. 可数无穷:X=N=0|X| = |\mathbb{N}| = \aleph_0
  2. 可数:有穷 \lor 可数无穷
  3. 不可数:无穷 \land 非可数无穷

Theorem

N\mathbb{N} 是无穷集合(Z,Q,R\mathbb{Z}, \mathbb{Q}, \mathbb{R} 也都是无穷集合)。

Theorem

  1. Z=N|\mathbb{Z}| = |\mathbb{N}|
  2. Q=N|\mathbb{Q}| = |\mathbb{N}|
  3. N×N=N|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|
  4. RN|\mathbb{R}| \neq |\mathbb{N}|R|\mathbb{R}| 是不可数的,且 R|\mathbb{R}| 是一个连续统
  5. 有穷多个可数集并在一起也是可数的
  6. (0,1)=R=R×R=Rn|(0, 1)| = |\mathbb{R}| = |\mathbb{R} \times \mathbb{R}| = |\mathbb{R}^n|

Theorem(康托-伯恩斯坦-施罗德定理)

若有 AB|A| \le |B|BA|B| \le |A| , 则有 A=B|A| = |B|

Theorem(康托定理)

AP(A)|A| \neq |P(A)|

A<P(A)|A| {\color{Red} <} |P(A)|

Definition(AB|A| \le |B|)

AB|A| \le |B| 当存在从 AA 映射到 BB 的单射函数

A<B    ABAB|A| < |B| \iff |A| \le |B| \land |A| \neq |B|

Theorem(可数)

XX 是可数的:

(nN:X=n)X=N(\exists n \in \mathbb{N} : |X| = n) \lor |X| = |\mathbb{N}|

Theorem(可数的证明方法)

XX 是可数的     \iff

XN|X| \le |\mathbb{N}|

存在单射函数 f:XNf: X \to N

Theorem

$

文章作者: ZY
文章链接: https://zyinnju.com/2022/02/16/Discrete-Math-Review-1/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ZY in NJU