discrete-mathematics

离散数学笔记

非常重要的结论叫定理
普通的结论叫性质

名词解释用需要定义来回答

命题逻辑

中文转折只能用合取来近似地表示

1. 命题: 能判断真假的陈述句(陈述句是命题的必要但不充分条件, 比如"我正在说谎")

2. 分类: 原子命题和复合命题
   原子命题: 不能再分解为更简单的陈述句
   复合命题: 由原子命题、联结词和标点符号构成的命题

3. 真值: 命题的判断结果, 真(True, T 或 1), 假(False, F, 或 0)
   真值表: 列出命题所有结果的表

4. 联结词:

   1. 否定 ┐P "非"运算

      P	┐P
      T	F
      F	T

   2. 合取 P∧Q "与"运算

      P	Q	P∧Q
      T	T	T
      T	F	F
      F	T	F
      F	F	F

   3. 析取 P∨Q "或"运算

      P	Q	P∨Q
      T	T	T
      T	F	T
      F	T	T
      F	F	F

   4. 条件 P→Q (如果前提P为真但此时Q为假说明此条件命题无效, 值为假)

      P	Q	P→Q
      T	T	T
      T	F	F
      F	T	T
      F	F	T

   5. 双条件 P↔Q “当且仅当” 符号iff
      可理解为P↔Q=(P→Q)∧(Q→P)

      P	Q	P↔Q
      T	T	T
      T	F	F
      F	T	F
      F	F	T

5. 联结词的运算优先级: ┐, ∧, ∨, →, ↔

6. 命题公式(也叫合成公式)

   1. 单个命题变元是命题公式
   2. 如果 A 是命题公式, 则 ┐A 也是
   3. 如果 A, B 是命题公式, 则 A∧B, A∨B, A→B, A↔B 也是
   4. 有限次使用上面 1~3 得到的符号串都是命题公式

7. 翻译: 汉语陈述 \(\rightleftharpoons\) 命题公式
   方法1: 直接根据逻辑含义
   方法2: 真值表法

8. 永真式(重言式):
   给定一个命题, 无论对变元做怎样的指派, 其真值总为真

9. 永假式(矛盾式):
   给定一个命题, 无论对变元做怎样的指派, 其真值总为假

10. 可满足:
    给定一个命题, 其真值有为真的情况

11. 等价:
    \(A\iff B\) , 当且仅当 \(A\harr B\) 是重言式(其中 A 和 B 可以是多个命题的结合)
    A, B 给变元任意一组真值指派, A 和 B 真值都相同

12. 十一大等价式:
    对合律 \(\neg\neg P\iff P\)
    幂等律 \(P\lor P\iff P\) , \(P\land P\iff P\)
    分配律 \((P\lor Q)\land R\iff (P\land R)\lor(Q\land R)\)
    \(\mskip{2.5em} (P\land Q)\lor R\iff(P\lor R)\land(Q\lor R)\)
    结合律 \((P\lor Q)\lor R\iff P\lor(Q\lor R)\)
    \(\mskip{2.5em} (P\land Q)\land R\iff P\land(Q\land R)\)
    交换律 \(P\lor Q\iff Q\lor P\) , \(P\land Q\iff Q\land P\)
    吸收律 \(P\lor(P\land Q)\iff P\)
    \(\mskip{2.5em} P\land(P\lor Q)\iff P\)
    德摩根律 \(\neg(P\lor Q)\iff \neg P\land\neg Q\)
    \(\mskip{3em} \neg(P\land Q)\iff \neg P \lor \neg Q\)
    同一律 \(P\lor \text{F}\iff P\) , \(P\land \text{T}\iff P\)
    零律 \(P\lor \text{T}\iff \text{T}\) , \(P\land \text{F}\iff \text{F}\)
    否定律 \(P\lor\neg P\iff \text{T}\) , \(P\land\neg P\iff \text{F}\)
    条件命题等价式 \(A\to B \iff \neg A\lor B\)
    \(\mskip{6em} A\harr B \iff (A\to B)\land(B\to A)\)

13. 置换:
    \(x\) 是 \(A\) 的子公式, 存在 \(x\iff Y\) , 将 \(A\) 中所有的 \(x\) 置换为 \(Y\) 得到公式 \(B\) , 则 \(B\iff A\)

14. 蕴含
    当且仅当 \(P\to Q\) 是重言式, 称 \(P\) 蕴含 \(Q\), 符号 \(P\implies Q\)
    蕴含其实就是充分关系, 即左边成立则右边一定成立
    反映在真值表就是 \(P\) 的真值表中为真的结果 \(Q\) 都为真, 但 \(Q\) 的真值表中为真的结果 \(P\) 不一定都为真

15. 十四大蕴含式
    化简律: \(P\land Q\implies P\)
    \(\mskip{3em}P\land Q\implies Q\)
    附加律: \(P\implies P\lor Q\)
    变形附加律: \(\neg P\implies P\to Q\)
    \(\mskip{5em}Q\implies P\to Q\)
    变形简化律: \(\neg(P\to Q)\implies P\)
    \(\mskip{5em}\neg(P\to Q)\implies\neg Q\)
    假言推理: \(P\land(P\to Q)\implies Q\)
    拒取式: \(\neg Q\land(P\to Q)\implies\neg P\)
    析取三段论: \(\neg P\land(P\lor Q)\implies Q\)
    条件三段论: \((P\to Q)\land(Q\to R)\implies P\to R\)
    等价三段论: \((P\harr Q)\land(Q\harr R)\implies P\harr R\)
    合取构造二难: \((P\land R)\land(P\to Q)\land(R\to S)\implies Q\land S\)
    析取构造二难: \((P\lor Q)\land(P\to R)\land(Q\to R)\implies R\)

16. 其他联结词

    1. 不可兼析取(逻辑异或) \(P\triangledown Q\iff \neg(P\harr Q)\)
    2. 条件否定 \(P\underrightarrow{c} Q\iff\neg(P\to Q)\)
    3. 与非 \(P\uarr Q\iff\neg(P\land Q)\)
    4. 或非 \(P\darr Q\iff\neg(P\lor Q)\)

17. 最小联结词化
    结合德摩根律和条件命题等价式, 可以将任何公式化成只含有最小联接词组的形式
    最小联接词组 \(\{\neg, \land\}\) , \(\{\neg, \lor\}\) , \(\{\darr\}\) , \(\{\uarr\}\)

18. 对偶式:
    一个命题公式 \(A\),
    将 \(\lor\) 换成 \(\land\) , \(\land\) 换成 \(\lor\),
    若 \(A\) 有 F 和 T, 将 F 换成 T, T 换成 F,
    得到的 \(A*\) 称为 \(A\) 的对偶式
    例:
    \((P\lor Q)\land R\) 的对偶式为 \((P\land Q)\lor R\)

    性质: \(A\iff B\) , \(A^* \iff B^*\)

19. 范式

    1. 合取范式
       形式为 \(A_1\land A_2\land\dots A_n\) , 其中 \(A_1\dots A_n\) 都是由变元及其否定组成的析取式
    2. 析取范式
       形式为 \(A_1\lor A_2\lor\dots A_n\) , 其中 \(A_1\dots A_n\) 都是由变元及其否定组成的合取式
    3. 主合/析取范式: 前面的合取范式和析取范式有个缺点, 他是不唯一的
       1. 小项(布尔合取): n 个变元的各种合取变换式, 其中每个变元及其否定仅出现一次. (n 个变元的小项有 \(2^n\) 个)
          小项的编码:
          设命题公式有两个变元 P 和 Q, 他有四个小项

          P	Q	P∧Q	P∧┐Q	┐P∧Q	┐P∧┐Q
          T	T	T	F	F	F
          T	F	F	T	F	F
          F	T	F	F	T	F
          F	F	F	F	F	T
          将以上各个小项为真时 P 和 Q 的指派状态用二进制表示可得 11, 10, 01, 00
          从而可用 \(m_{11} , m_{10} , m_{01} , m_{00}\) 表示以上各个小项

       2. 主析取范式
          主析取范式由若干小项的析取组成, 见下面定理
          定理: 任何一个命题公式, 其真值表中真值为真的指派所对应的小项们的析取就是该公式的主析取范式
       3. 大项(布尔析取): n 个变元的各种析取变换式, 其中每个变元及其否定仅出现一次. (n 个变元的小项有 \(2^n\) 个)
          大项的编码:
          设命题公式有两个变元 P 和 Q, 他有四个大项

          P	Q	P∨Q	P∨┐Q	┐P∨Q	┐P∨┐Q
          T	T	T	T	T	F
          T	F	T	T	F	T
          F	T	T	F	T	T
          F	F	F	T	T	T
          将以上各个大项为假时 P 和 Q 的指派状态用二进制表示可得 00, 01, 10, 11
          从而可用 \(M_{00} , M_{01} , M_{10} , M_{11}\) 表示以上各个大项

       4. 主合取范式
          主合取范式由若干大项的合取组成, 见下面定理
          定理: 任何一个命题公式, 其真值表中真值为假的指派所对应的大项们的合取就是该公式的主合取范式

20. 有效结论: 当且仅当 \(A\to C\) 为重言式, 即 \(A\implies C\) , 就说 \(C\) 是 \(A\) 的有效结论

21. 推理(也称论证): 若 \(H_1, H_2,\dots, H_n\) 为真, 利用一些公认的规则, 得到一个有效结论的过程.
    三种推理方法:

    1. 真值表法(万能, 但也是最笨的)
    2. 直接证法(重点)
       P 规则: 引入前提
       T 规则: 使用等价式 E, 蕴含式 I
       例: 证明 \((P\lor Q)\land(P\to R)\land(Q\to S)\implies S\lor R\)

       证明:   结论        理由
       (1)    P∨Q          P
       (2)    ┐P→Q      T(1), E     (E代表等价式)
       (3)    Q→S          P
       (4)    ┐P→S      T(2)(3), I  (I代表蕴含式) (使用了条件三段论)
       (5)    ┐S→P      T(4), E
       (6)    P→R          P
       (7)    ┐S→R      T(5)(6), I
       (8)    S∨R        T(7), E

    3. 间接证明(不要求)
       1. 反证法 \(H_1\land H_2\dots H_n\land\neg C \implies \dots \implies \text{F}\)
       2. CP 规则: \(H_1\land H_2\dots H_n\implies(R\to C) \iff H_1\land H_2\dots H_n\land R\implies C\)

习题

1. 指出下列语句中哪个不是命题 (C)
   A. 3+2=5
   B. 北京是中国的首都
   C. 请勿吸烟
   D. 李白是唐朝的诗人

2. 指出下列语句哪个是命题 (D)
   A. 这本书真好看啊!
   B. 上课不要迟到!
   C. 你吃午饭了吗?
   D. 李白是唐朝诗人

3. 以下语句不是命题的是 (B)
   A. 明天我要上门去谢你
   B. 谢谢你给了我的机会
   C. 如果不说我就不谢你
   D. 除非你做了我才谢你

4. 下列句子哪些是命题?

   1. 她能歌善舞
   2. 如果我有时间, 我就来看你
   3. 你喜欢看电影吗?
   4. 小王今年20岁或21岁
   5. 别讲话了!
   6. 小王和小李是同学

   (解: 1,2,4,6 是命题)

5. 复合命题 由原子命题、联结词和标点符号构成的命题

6. P、Q 为两个命题, 当且仅当 P和Q都为真时 P∧Q 为真.

7. 命题"如果 1+1=0, 那么太阳从东边落下"的真值为真

8. 设 P、Q 的真值为 0, R、S 的真值为 1, 则下列命题中真值为 1 的是. (D)
   A. R→P
   B. Q∧S
   C. P↔S
   D. Q∨R

9. 设 P: 天下雨, q: 我去新华书店, 命题"除非天不下雨, 我去新华书店"符号化形式为 (D)
   A. P→q
   B. q→P
   C. ┐q→P
   D. ┐P→q

10. 若 P: 今天下雪了, Q: 路滑, 则"虽然今天下雪了, 但是路不滑", 则符号化为 (D)
    A. (P∧Q)
    B. P∨┐Q
    C. (P→┐Q)
    D. P∧┐Q
    (中文里转折的意思只能用合取+否定的形式来表示)

11. 设 P, Q, R 的意义如下:
    P: 李华坐火车, Q: 李华在看书, R: 李华在思考问题
    试用日常语言复述下列命题公式.

    1. (P∧Q)∧┐R
    2. ┐(PVQ)∧R

    答:
    李华在坐火车和看书, 但是没有思考问题
    李华没有做火车也不在看书, 但是在思考问题
    (不能写成: 李华没有做火车或看书, 要把 ┐(PVQ) 化为 ┐P∧┐Q)

12. 命题公式 A 与 B 等价是指 (D)
    A. A 与 B 有相同的原子变元
    B. A 与 B 是可满足的
    C. 当 A 的真值为真时, B 也为真
    D. A 与 B 有相同的真值

13. \((P\to\neg P)\to\neg P\) 是 永真 式 (填永真, 永假, 可满足)

14. \((P\land \neg P)\to((Q\land \neg Q)\land\neg R)\) 是 永真 式 (填永真, 永假, 可满足)

15. 一个命题公式如果 变元各种指派下, 其真值总为假 , 则称矛盾式

16. \((P\lor\neg P)\land\neg Q\) 是 可满足 式 (填永真, 永假, 可满足)

17. 重言式: 给定一个命题公式, 它的变元在各种指派下, 其真值总为真

18. 下列集合哪个是最小联结词集? (D)
    A. \(\{\neg, \to\}\)
    B. \(\{\neg, \harr\}\)
    C. \(\{\neg, \implies\}\)
    D. \(\{\neg, \land\}\)

19. 证明 \((P\to R)\lor(Q\to R)\iff(P\land Q)\to R\)
    (证明思路是将左右两边最终化为由相同的最小联接词组组成的命题)
    证明:
    \(P\to R\lor(Q\to R)\)
    \(\iff (\neg P\lor R)\lor(\neg Q\lor R)\)
    \(\iff (\neg P\lor\neg Q)\lor R\) (使用了幂等律)
    \(\iff \neg(P\land Q)\lor R\) (使用了德摩根律)
    \(\iff (P\land Q)\to R\) (使用了条件命题等价式)
    证毕

20. 求 \((P\lor Q)\to (P\harr Q)\) 的主析取范式
    解:

    P	Q	P∨Q	P↔Q	原式
    T	T	T	T	T
    T	F	T	F	F
    F	T	T	F	F
    F	F	F	T	T
    所以主析取范式:
    \(m_0\lor m_3 \iff \sum_{0,3}\) (小项的编码表示)
    \(\iff (P\land Q)\lor(\neg P\land\neg Q)\)
    主合取范式:
    \(M_2\lor M_1 \iff \pi_{2,1}\) (大项的编码表示)
    \(\iff (\neg P\lor Q)\land(P\land\neg Q)\)

21. 命题公式的对偶式: 一个命题公式 A, 将 ∨ 换成 ∧ , ∧ 换成 ∨, 若 A 有 F 和 T, 将 F 换成 T, T 换成 F, 得到的 A* 称为 A 的对偶式

22. 任意两个大项的析取是 永真式

23. 全体大项的合取是 永假式

24. 求 \(((A\lor B)\to C)\to A\) 的主析取范式和主合取范式
    解:
    列真值表

    A	B	C	A∨B	(A∨B)→C	原式
    T	T	T	T	T	T
    T	T	F	T	F	T
    T	F	T	T	T	T
    T	F	F	T	F	T
    F	T	T	T	T	F
    F	T	F	T	F	T
    F	F	T	F	T	F
    F	F	F	F	T	F
    主析取范式: \(\sum_{2,4,5,6,7}\)
    主合取范式: \(\pi_{0,1,3}\)

谓词逻辑

苏格拉底三段论:
A. 所有人都是要死的
B. 苏格拉底是人
C. 苏格拉底是要死的
\(A\land B\implies C\)
以上命题无法用命题逻辑推理, 由此引出了谓词逻辑

1. 谓词: 描述实体的性质或关系
   例子:
   H() : 是人
   x : 苏格拉底
   H(x) : 苏格拉底是人
   5大于3: L(5, 3)
   L() : 大于
   x 称为客体变元
2. 命题函数: 使用谓词和一些客体变元组成的表达式
3. 个体域(论域): 变元的取值范围
4. 全称量词: \(\forall\) “所有的” “每一个”
5. 存在量词: \(\exist\) “存在一些” “至少有一个”
6. 谓词公式:
   1. 原子谓词公式是谓词公式
   2. 如果 \(A\) 是谓词公式, 则 \(\neg A\) 的否定也是谓词公式
   3. \(A\land B\) , \(A\lor B\) , \(A\to B\) , \(A\harr B\) 是谓词公式
   4. \(\forall x A\) 、\(\exist x A\) 是谓词公式
   5. 有限次使用以上 1~4 条得到的式子是谓词公式
7. 翻译: 自然语言 \(\rightleftharpoons\) 谓词公式
8. 指导变元(作用变元): 紧跟量词 \(\forall\) 、\(\exist\) 后面的变元
9. 作用域(辖域): 受指导变元作用的区域, 如无括号即为指导变元后至下一个联结词前的区域(如 ∀xP(x,y,z) 中的 P(x,y,z))
10. 约束变元: 作用域内出现的该变元叫作该指导变元的约束变元 (如 ∀xP(x,y,z) 中的 x 就是约束变元)
11. 自由变元: 除了约束变元以外的其他变元 (如 ∀xP(x,y,z) 中的 y, z 就是自由变元)
12. 约束变元换名: 对谓词公式中某个指导变元及其作用域内的约束变元替换为一个没有出现过的变元字母
    (如 ∀xP(x,y,z) ∨ ∃xP(x) 合取前边的 x 可换名为 ∀aP(a,y,z) ∨ ∃xP(x))
13. 自由变元代入: 同约束变元换名一样
14. 谓词公式的等价: A, B 对任意一组变元赋值时, 所得的命题真值相同(TLDR: 这两个命题真值表一样), 则 \(A\iff B\)
15. 谓词公式的永真式: 真值总为真
    谓词公式的永假式: 真值总为假
    谓词公式的可满足: 真值可为真或假
16. 常用的谓词公式等价式:
    以下内容利用这两条公式可证明
    \(\forall x F(x)\iff F(a_1)\land F(a_2)\land\dots\land F(a_n)\)
    \(\exist x F(x)\iff F(a_1)\lor F(a_2)\lor\dots\lor F(a_n)\)
    1. 从命题公式中推广而来
       注意: 仅有部分可以推广
       例: \(P\to Q\iff\neg P\lor Q\) 可变为 \(\forall x(P(x)\to Q(x))\iff\forall x(\neg P(x)\lor Q(x))\)
       例外 \(\exist x(A(x)\land B(x))\implies\exist x A(x)\land\exist x B(x)\)
    2. 量词与 \(\neg\) (量词的德摩根律)
       \(\neg\forall x P(x)\iff\exist x\neg P(x)\)
       \(\neg\exist x P(x)\iff\forall x\neg P(x)\)
    3. 量词与 \(\land\) , \(\lor\) , \(\to\) , \(\harr\)
       \(\forall x(A(x)\land B(x))\iff\forall x A(x)\land\forall x B(x)\)
       \(\exist x(A(x)\lor B(x))\iff\exist x A(x)\lor\exist x B(x)\)
       (对于全称量词的析取, 存在量词的合取, 全称量词和存在量词的条件, 双条件不等价, 而是蕴含)
       \(\forall x(A(x)\lor B(x))\implies\forall x A(x)\lor\forall x B(x)\)
       \(\exist x(A(x)\land B(x))\implies\exist x A(x)\land\exist x B(x)\)
       \(\forall x (A(x)\to B(x))\implies\forall x A(x)\to\forall x B(x)\)
       \(\forall x (A(x)\harr B(x))\implies\forall x A(x)\harr\forall x B(x)\)
    4. 量词作用域的扩张与收缩
       \(\forall x(A(x)\lor B)\iff\forall x A(x)\lor B\)
       \(\forall x(A(x)\land B)\iff\forall x A(x)\land B\)
       \(\exist x(A(x)\lor B)\iff\exist x A(x)\lor B\)
       \(\exist x(A(x)\land B)\iff\exist x A(x)\land B\)
       注意:
       \(\forall x A(x)\to B\iff\exist x(A(x)\to B)\)
       \(\exist x A(x)\to B\iff\forall x(A(x)\to B)\)
       \(B\to \forall x A(x)\iff\forall x(B\to A(x))\)
       \(B\to \exist x A(x)\iff\exist x(B\to A(x))\)
    5. 量词的嵌套
       对于所有x对于存在y, 和存在y对于所有x不同
       (最强) \(\forall x\forall y P(x,y)\iff\forall y\forall x P(x,y)\)
       (最弱) \(\exist x\exist y P(x,y)\iff\exist y\exist x P(x,y)\)
       (弱) \(\forall x\exist y P(x,y)\) , \(\forall y\exist x P(x,y)\)
       (次强) \(\exist x\forall y P(x,y)\) , \(\exist y\forall x P(x,y)\)
       \(\forall x\forall y\implies\exist y\forall x\)
       \(\exist y\forall x\implies\forall x\exist y\)
       \(\forall x\exist y\implies\exist y\exist x\)
17. 谓词公式的推理
    1. US 全称指定规则 \(\forall-\)
       (比如将 \(\forall x P(x)\) 指定为 \(P(c)\) , 其中 c 指任意的数)
    2. ES 存在指定规则 \(\exist-\)
       (比如将 \(\exist x P(x)\) 指定为 \(P(c)\) , 其中 c 指能使式子成立的那些数)
    3. UG 全称推广规则 \(\forall+\)
       (比如将 \(P(c)\) 推广为 \(\forall x P(x)\))
    4. EG 存在推广规则 \(\exist+\)
       (比如将 \(P(c)\) 推广为 \(\exist x P(x)\)

习题

1. 设 P(x) 为 “x 是大学生”, Q(x) 为 “x 不满 30 岁”, 命题"所有大学生都不满 30 岁"写成谓词公式为 (C)
   A. \(\forall x (P(x)\land Q(x))\)
   B. \(\exist x (P(x)\land Q(x))\)
   C. \(\forall x P(x)\to Q(x)\)
   D. \(\exist x P(x)\to Q(x)\)
2. 设 L(x): x 是演员, J(x): x 是老师. A(x,y): x 钦佩 y , 命题 "所有演员都钦佩某些老师"符号化为 (B)
   A. \(\forall x(L(x)\to A(x,y))\)
   B. \(\forall x(L(x)\to \exist y(J(y)\land A(x,y)))\)
   C. \(\forall x\exist y(L(x)\land(J(y)\land A(x,y)))\)
   D. \(\forall x\exist y(L(x)\land(J(y)\to A(x,y)))\)
   D 为什么是错的, D 可化为\(\forall x(L(x)\land\exist y(J(y)\to A(x,y)))\) , 若 \(x\) 不是演员结果竟然也为假, 显然不符合命题
   翻译时全称量词应和条件搭配(反之, 存在量词应和合取搭配)
3. 已知 \(\forall y(R(y)\lor B(y))\) , 其中 \(R(3)=B(4)=T\) , \(R(4)=B(3)=F\) , 且论域是 \(\{3,4\}\) , 求该式的值
   思路:
   \(\forall x F(x)\iff F(a_1)\land F(a_2)\land\dots\land F(a_n)\)
   \(\exist x F(x)\iff F(a_1)\lor F(a_2)\lor\dots\lor F(a_n)\)
   解:
   \(\mskip{2.7em}\forall y(R(y)\lor B(y))\)
   \(\iff (R(3)\lor B(3))\land(R(4)\lor B(4))\)
   \(\iff (T\lor F)\land (F\lor T)\)
   \(\iff T\land T\)
   \(\iff T\)
4. 谓词公式 \(\forall x(P(x)\lor\exist y R(y))\to Q(x)\) 中变元 \(x\) 是 (C)
   A. 自由变元
   B. 约束变元
   C. 既是自由变元又是约束变元
   D. 既不是自由变元也不是约束变元
5. 公式 \(\exist x\forall y(P(x,y)\land Q(z))\) 中 \(\forall y\) 的辖域是 (C)
   A. \(P(x,y)\)
   B. \(\exist x(P(x,y)\land Q(z))\)
   C. \((P(x,y)\land Q(z))\)
   D. \(Q(z)\)
6. 公式 \(\forall x\forall y(P(x,y)\land Q(x,y))\land\exist x P(x,y)\) 中 \(\forall x\) 的辖域是 (B)
   A. \(P(x,y)\)
   B. \(P(x,y)\land Q(x,y)\)
   C. \(Q(x,y)\)
   D. \(P(x,y)\land Q(x,y))\land\exist x P(x,y)\)
7. 公式 \(\forall x F(x)\land G(x,y)\) 中变元 \(y\) 是 自由 变元. (填自由或约束)
8. 约束变元的换名: 对谓词公式中某个指导变元及其作用域内的约束变元替换为一个没有出现过的变元字母
9. 下列等价式不正确的是 (D)
   A. \(\neg\forall x A\iff \exist x\neg A\)
   B. \(\forall x(B\to A(x))\iff B\to\forall x A(x)\)
   C. \(\exist x(A(x)\lor B(x))\iff \exist x A(x)\lor\exist x B(x)\)
   D. \(\forall x\forall y(A(x)\to B(y))\iff\forall x A(x)\to\forall y B(y)\)
10. 与 \(\neg\exist x M(x)\) 等价的是 (D)
    A. \(\forall x M(x)\)
    B. \(\exist x\neg M(x)\)
    C. \(\forall x M(x)\)
    D. \(\forall x\neg M(x)\)
11. 量词与否定之间有以下关系: \(\neg\forall x Q(x)\iff\) ___\(\exist x\neg Q(x)\)___
12. 证明题
    符号化并证明: 人总是要死的, 苏格拉底是人, 所以苏格拉底要死的.
    翻译: H(x): x 是人; D(x): x 是要死的; s: 苏格拉底
    \(\mskip{2em}\forall x(H(x)\to D(x))\) , \(H(s)\implies D(s)\)
    证明:
    \(\mskip{5em}\) 结论 \(\mskip{5em}\) 理由
    (1) \(\forall x(H(x)\to D(x))\mskip{3.25em}\) P
    (2) \(H(s)\mskip{9em}\) P
    (3) \(H(s)\to D(s)\mskip{5em}\) T(1), US
    (4) \(D(s)\mskip{8.7em}\) T(2)(3), I
13. 形式化并证明
    每一个自然数是不是奇数就是偶数,
    自然数是偶数当且仅当它被 2 整除,
    并不是所有自然数都能被 2 整除,
    因此, 有的自然数是奇数
    翻译: O(x): x 是奇数; E(x): x 是偶数; D(x): x 能被 2 整除
    \(\forall x(\neg O(x)\to E(x))\) ,
    \(\forall x(E(x)\harr D(x))\) ,
    \(\neg\forall x D(x)\harr\exist x O(x)\)
    证明:
    \(\mskip{5em}\) 结论 \(\mskip{5em}\) 理由
    (1) \(\forall x(\neg O(x)\to E(x))\mskip{3em}\) P
    (2) \(\forall x(E(x)\harr D(x))\mskip{3.5em}\) P
    (3) \(\neg\forall x D(x)\mskip{7.3em}\) P
    (4) \(\exist x\neg D(x)\mskip{6.5em}\) T(3), E
    (5) \(\neg D(a)\mskip{7.6em}\) T(4), ES
    (6) \(E(a)\harr D(a)\mskip{4.6em}\) T(2), US
    (7) \(\neg E(a)\mskip{7.2em}\) T(5)(6), I
    (8) \(\neg O(a)\to E(a)\mskip{4em}\) T(1), US
    (9) \(O(a)\mskip{8.3em}\) T(7)(8), I
    (10) \(\exist x O(x)\mskip{6.6em}\) T(9), EG
    注意: 第5步和第6步不能互换, 存在指定和全称指定的变量 a 需要先经存在指定限定范围

集合论

1. 集合: 把一些元素汇集成一个整体
   集合 A, B, C. 元素 a, b, c
   \(a\in A\) , 读作"属于", \(b\notin\) 读作"不属于"
   分类 \(\begin{cases} \text{有限集} \\ \text{无限集} \end{cases}\)

2. 表示:

   1. 列举法 \(A=\{1,2,3,4,5\}\)

   2. 描述法 \(A=\{x|x\text{是自然数}\}\)

   3. 文氏图(venn)

3. 相等: 当且仅当它们有相同的元素
   比如:
   \(\{1,3,5,7,\dots\}=\{x|x\text{是正奇数}\}\)
   \(\{1,2,4\}=\{1,4,2\}\)
   \(\{1,2,4\}=\{1,2,2,4\}\)

4. 包含于: 若 A 的每一个元素都是 B 的成员, 则称 A 是 B 的子集
   记为 \(A\subseteq B\) , 读作"包含于", 等价于 \(B\supseteq A\) (注意朝向)
   \(A\subseteq B\iff\forall x(x\in A\to x\in B)\)
   性质:

   • (自反性) \(A\subseteq A\)
   • (传递性) \((A\subseteq B)\land(B\subseteq C)\implies A\subseteq C\)
   • (但不满足下式对称性) \(A\subseteq B\nRightarrow B\subseteq A\)
   • 互为子集定理: \(A=B\iff(A\subseteq B)\land(B\subseteq A)\)

5. 真包含于: A 中每一个元素都是 B 的成员, 但 B 中至少有一个元素不属于 A, 则称 A 是 B 的真子集, 记作 \(A\subset B\) , 读作"真包含于"

6. 空集 \(\varnothing\)
   \(\varnothing\neq\{\varnothing\}\) (前者是空集, 但后者不是. 因为它有一个元素-空集本身)
   \(\varnothing\in\{\varnothing\}\) (正确)
   \(\varnothing\subseteq A\) (正确)
   \(\varnothing\subset A\) (不对, 因为有 \(A=\{\varnothing\}\) 的情况)

7. 全集: 在一定范围内, 包含所有元素的集合
   \(E=\{x|P(x)\lor\neg P(x)\}\)
   \(\varnothing=\{x|P(x)\land\neg P(x)\}\)

8. 幂集: 由 A 的所有子集为元素组成的集合叫 A 的幂集, 记作 P(A)
   \(P(A)=\{B|B\subseteq A\}\) (B 代表 A 的所有子集)
   如: \(A=\{a,b,c\}\) , \(P(A)=\{\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\},\varnothing\}\)

   • 若 \(A\) 有 \(n\) 个元素, \(P(A)\) 有 \(2^n\) 个元素 (推导思路, 将所有元素想象成拥有取或不取两种状态, 则能有 \(2^n\) 种不同的序列)

9. 交: \(A\cap B=\{x|(x\in A)\land(x\in B)\}\)

   • \(A\cap A=A\)
   • \(A\cap\varnothing=\varnothing\)
   • \(A\cap E=A\)
   • (对称性/交换律) \(A\cap B=B\cap A\)
   • (结合律) \((A\cap B)\cap C=A\cap(B\cap C)\)

10. 并: \(A\cup B=\{x|(x\in A)\lor(x\in B)\}\)

    • \(A\cup A=A\)
    • \(A\cup\varnothing=A\)
    • \(A\cup E=E\)
    • \(A\cup B=B\cup A\)
    • \((A\cup B)\cup C=A\cup(B\cup C)\)
    • 分配律
      \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\)
      \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\)
    • 吸收律
      \(A\cup(A\cap B)=A\)
      \(A\cap(A\cup B)=A\)

11. 差: \(A-B=\{x|(x\in A)\land(x\notin B)\}\)

    \(A-B=A\cup\sim B\)

12. 补: \(\sim A=E-A=\{x|(x\in E)\land(x\notin A)\}\)

    • \(\sim(\sim A)=A\)
    • \(\sim E=\varnothing\)
    • \(\sim\varnothing=E\)
    • \(A\cup\sim A=E\)
    • \(A\cap\sim A=\varnothing\)
    • \(A\cap\sim B=A-B\)
    • 定理(集合的德摩根律):
      \(\sim(A\cup B)=\sim A\cap\sim B\)
      \(\sim(A\cap B)=\sim A\cup\sim B\)

13. 对称差 \(A\oplus B=(A-B)\cup(B-A)=\{x|(x\in A)\triangledown(x\in B)\}\)

14. 序偶: 有固定次序的两个元素

    • \(<a,b>\neq<b,a>\)
    • \(<a,b>=<u,v>\iff(a=u)\land(b=v)\)

    推广: 三元组, 四元组, …

15. 笛卡尔积(直积):
    有序列 A、B,
    若序偶的第一个成员属于 A, 序偶的第二个属于 B,
    由所有这样的序偶组成的集合称为 A 与 B 的笛卡尔积
    符号 \(A\times B=\{<x,y>|(x\in A)\land(y\in B)\}\)

    例:
    \(A=\{\alpha,\beta\}\) , \(B=\{1,2\}\)
    \(A\times B=\{<\alpha,1>,<\alpha,2>,<\beta,1>,<\beta,2>\}\)

    性质: (笛卡尔积 对 并或交运算的分配律)

    • \(A\times(B\cup C)=(A\times B)\cup(A\times C)\)
    • \(A\times(B\cap C)=(A\times B)\cap(A\times C)\)
    • \((A\cup B)\times C=(A\times C)\cup(B\times C)\)
    • \((A\cap B)\times C=(A\times C)\cap(B\times C)\)
    • \(A\times A\times\dots\times A=A^n\)

    但注意, 并或交 对 笛卡尔积 不服从分配律
    如 \(A\cup(B\times C)\neq(A\cup B)\times(A\cup C)\) (显而易见, 因为左边的 \(A\) 不是序偶)

16. 关系\(^1\):
    任意一个关于序偶的集合, 都是一个二元关系 \(R\) , 记作 \(<x,y>\in R\)

    例:
    \(A=\{1,2,3,5\}\) , \(B=\{a,b,c\}\)
    \(R=\{<1,b><2,c><3,c>\}\)

17. 域
    由 \(<x,y>\in R\) 中所有 x 组成的集合叫作前域, 记作 \(\text{dom R}\)
    由 \(<x,y>\in R\) 中所有 y 组成的集合叫作值域, 记作 \(\text{ran R}\)
    前域和值域一起称作域 FLD
    \(\text{FLD}R=\text{dom R}\cup\text{ran R}\)

    例:
    \(A=\{1,2,3,5\}\) , \(B=\{1,2,4\}\) , \(R=\{<1,2>,<1,4>,<2,4>,<3,4>\}\)
    求 \(\text{dom R}\), \(\text{ran R}\), \(\text{FLD}R\)
    \(\text{dom R}=\{1,2,3\}\)
    \(\text{ran R}=\{2,4\}\)
    \(\text{FLD}R=\{1,2,3,4\}\)

18. 关系\(^2\) :
    \(A\times B\) 的子集称作 \(A\) 到 \(B\) 的关系
    恒等关系: \(I_A=\{<a,a>|a\in A\}\)
    全域关系: \(A\times B\)
    空关系: \(\varnothing\)

19. 关系的表示

    1. 列举序偶

    2. 关系矩阵
       \(R\) 对应 \(M_R=[r_{ij}]_{n\times n}\)
       其中, \(r_{ij}=\begin{cases} 1 &\text{当}<x_i,y_j>\in R \\ 0 &\text{当}<x_i,y_j>\notin R \end{cases}\)

       例: \(X=\{x_1,x_2,x_3,x_4\}\) , \(Y=\{y_1,y_2,y_3\}\) , \(R=\{<x_1,y_1>,<x_2,y_3>,<x_3,y_2>,<x_2,y_1>\}\)
       \(M_R=\begin{bmatrix} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}_{4\times 3}\)

    3. 关系图

20. 自反性: 设关于集合 \(X\) 的关系 \(R:X\) , 如果对于每一个 \(x\in X\) , 都有 \(xRx\) (即 \(<x,x>\in R\)) , 则称关系 \(R\) 是自反的
    例: \(A=\{1,2,3\}\) , 关系 \(R=\{<1,1>,<2,2>,<3,3>,<1,2>\}\) 是自反的
    关系矩阵主对角线上元素均为 1， 则关系 \(R\) 是自反的;
    关系图中每个结点都有环, 则关系 \(R\) 是自反的.

21. 反自反性: 设关于集合 \(X\) 的关系 \(R:X\) , 如果对于每一个 \(x\in X\) , 都有 \(x\not Rx\) (即 \(<x,x>\notin R\)), 则称关系 \(R\) 是反自反的
    例: \(A=\{1,2,3\}\) , 关系 \(R=\{<1,2>,<2,1>,<,3,2>\}\) 是反自反的
    关系矩阵主对角线上元素均为 0， 则关系 \(R\) 是反自反的;
    关系图中每个结点都没有环, 则关系 \(R\) 是反自反的.

22. 对称性: 设关于集合 \(X\) 的关系 \(R:X\) , \(x,y\in X\) , 对于每一个 \(xRy\) , 都有 \(yRx\) , 则称关系 \(R\) 是对称的
    例: \(A=\{1,2,3\}\) , 关系 \(R=\{<1,2>,<2,1>,<3,3>\}\) 是对称的
    关系矩阵沿主对角线对称, 则关系 \(R\) 是对称的
    关系图中若弧是成对出现的, 则关系 \(R\) 是对称的

23. 反对称性: 设关于集合 \(X\) 的关系 \(R:X\) , \(x,y\in X\) , 对于每一个 \(xRy\) , 都有 \(y\not Rx\) , 称关系 \(R\) 是反对称的
    另一个条件: 每当 \(xRy\land yRx\) , 都有 \(x=y\) , 也认为是反对称的
    例: \(A=\{1,2,3\}\) , 关系 \(R=\{<1,2>,<1,3>,<2,3>\}\) 是反对称的
    关系矩阵沿主对角线不对称, 则关系 \(R\) 是反对称的
    关系图中若弧不成对出现, 则关系 \(R\) 是反对称的

    • \(I_A\) 是对称的, 又是反对称的
    • 空关系 \(\varnothing\) 是对称的, 又是反对称的

24. 传递性: 设关于集合 \(X\) 的关系 \(R:X\) , \(x,y\in X\) , 每当 \(xRy\) , \(yRx\) , 都有 \(xRz\) , 则称关系 \(R\) 是传递的
    例: \(X=\{1,2,3\}\) , 关系 \(R=\{<1,2>,<2,3>,<1,3>,<2,1>\}\) 不是传递的 (少了\(<2,2>\) 和 \(<1,1>\))
    关系图中, 若从 a 到 b 的有向路径(路径是间接的), 存在 a 到 b 的弧(弧是直接的). 则 R 是传递的

25. 关系的运算: 交, 并, 差, 对称差, 补(用 \(\tilde{R}\) , 即 \(\text{全域关系}-R\) 中的序偶)

26. 关系的复合: 设 \(R: X\to Y\) , \(S: Y\to Z\) , 则复合 \(R\circ S=\{<x,z>|x\in X\land z\in Z\land\exist y(y\in Y\land<x,y>\in R\land<y,z>\in S)\}\)
    例:
    \(R=\{<1,2>,<3,4>,<2,2>\}\)
    \(S=\{<4,2>,<2,5>,<3,1>,<1,3>\}\)
    实际计算方法就是将 \(R\) 中每个序偶的终端 \(y\) 去找 \(S\) 的序偶中相同的始端 \(y\) , 然后跟这个相同始端的序偶结合成 \(<x,z>\)
    \(R\circ S=<1,5>,<3,2>,<2,5>\)
    \(S\circ R=<4,2>,<3,2>,<1,4>\)

    注意: 由上面例子可知复合不满足交换律. 但是复合满足:
    结合律 \(R\circ(S\circ P)=(R\circ S)\circ P\)
    \(R\circ I=R\)
    \(R\circ\varnothing=\varnothing\)
    \(R\circ R=R^{(2)}\)
    \(R\circ R\circ R\circ\dots\circ R=R^{(n)}\) (关系的幂运算)

27. 关系的逆运算: 设 \(R:X\to Y\) , 则 \(R^c (\text{或记}R^{-1})=\{<y,x>|<x,y>\in R\}\)
    (即把 R 的每一个序偶中元素顺序换一下)
    \((R^{-1})^{-1}=R\)

28. 闭包: 设 \(R:X\) , 如果另一个关系 \(R’\) 满足:

    1. \(R’\) 是自反的(对称的, 传递的)
    2. \(R’\supseteq R\)
    3. 对于任何自反的(对称的, 传递的)关系 \(R’‘\) , 如果 \(R’‘\supseteq R\) , 就有 \(R’‘\supseteq R’\) (即 \(R’\) 是最小的、包含 \(R\) 的自反关系)

    则称 \(R’\) 为 \(R\) 的自反(对称, 传递)闭包

29. 自反闭包表示为 \(r(R)=R\cup I_A\)

30. 对称闭包表示为 \(s(R)=R\cup R^{-1}\)

31. 传递闭包表示为 \(t(R)=\underset{i=1}{\overset{\infty}{\cup}}R^{(i)}=\underset{i=1}{\overset{|A|}{\cup}}R^{(i)}\) (\(|A|\) 表示集合 \(A\) 的基数)

32. 覆盖: 设 \(A\) , \(S=\{S_1,S_2,\dots,S_n\}\) , 若 \(S_i\subseteq A\) , \(S_i\neq\varnothing\) , 且 \(\underset{i=1}{\overset{n}{\cup}}S_i=A\) . 则称 \(S\) 是 \(A\) 的覆盖

33. 划分: 在满足覆盖条件的基础上, 另有 \(\forall i\forall j(S_i\cap S_j)=\varnothing\quad(i\neq j)\) , 则称 \(S\) 是 \(A\) 的划分.
    例:
    \(A=\{1,2,3,4,5\}\)
    \(X=\{\{1,2,3\},\{3,4,5\}\}\) 是覆盖
    \(Y=\{\{1,2,3\},\{4\},\{5\}\}\) 是划分
    \(Z=\{\{1,2,3,4,5\}\}\) 是最小划分(划分数最小)
    \(U=\{\{1\},\{2\},\{3\},\{4\},\{5\}\}\) 是最大划分(划分数最大)

34. 等价关系: 设 \(R:A\) , 若 \(R\) 是自反的, 对称的, 传递的, 则称 \(R\) 是等价关系

35. 等价类: 设 \(R\) 是 \(A\) 的等价关系, 则对于 \(\forall a\in A\) , 有元素 \(a\) 关于关系 \(R\) 的等价类 \([a]_R=\{x|xRa,x\in A\}\)
    (即从等价关系中挑出所有与元素 \(a\) 有关系的元素组成的集合就是这个元素 \(a\) 的等价类)
    例:
    \(A=\{1,2,3,4\}\)
    \(R=\{<1,1>,<2,2>,<1,2>,<2,1>,<3,3>,<4,4>,<3,4>,<4,3>\}\)
    则有
    \([1]_R=\{1,2\}=[2]_R\)
    \([3]_R=\{3,4\}=[4]_R\)

    • 定理: 在等价关系中, \(\forall a,b\in A\) , 有 \(aRb\Harr[a]_R=[b]_R\)

36. 商集: 设 \(R\) 是 \(A\) 的等价关系, 其等价类的集合 \(\{[a]_R|a\in A\}\) 称作 \(A\) 关于 R 的商集, 记作 \(A/R\)
    定理:

    • \(R\) 是 \(A\) 上的等价关系, 则商集 \(A/R\) 是 \(A\) 的一种划分(有关系的元素之间等价类完全相同, 所以是划分)
    • 反之, 集合 \(A\) 上的任意一种划分 \(S\) , 也能确定 \(A\) 上的一种等价关系

37. 相容关系: 设 \(R:A\) , 若 R 是自反的, 对称的, 则 R 是相容关系
    等价关系 \(\subset\) 相容关系
    等价类的商集为划分, 相容类的商集为覆盖

38. 偏序关系: \(R:A\), 若 R 是自反的, 反对称的, 传递的,
    则 R 是偏序关系, 换成用 “\(\preccurlyeq\)” 表示
    (或 “\(\leqslant\)” , 因为"小于等于"是一种典型的偏序关系)
    (\(a\preccurlyeq b=\{<a,a>,<b,b>,<a,b>\}\))
    偏序集: 记作 \(<A,\preccurlyeq>\) (用来表示定义在集合 A 上的一种偏序关系)
    例:
    \(A=\{2,3,6,8\}\) ,
    设 D 表示整除关系(即每个序偶中后者能整除前者)
    \(D=\{<2,6>,<2,8>,<3,6>,<2,2>,<3,3>,<6,6>,<8,8>\}\)
    D 是偏序关系;

    设 M 表示整倍数关系
    \(M=\{<6,2>,<6,3>,<8,2>,<2,2>,<3,3>,<6,6>,<8,8>\}\)
    M 是偏序关系

39. 盖住: 设偏序集 \(<A,\preccurlyeq>\) , 如果 \(x,y\in A\quad(x\neq y)\) , 有 \(x\preccurlyeq y\) , 且不存在 \(z\in A\) , 使得 \(x\preccurlyeq z\) 和 \(z\preccurlyeq y\) , 则称 y 盖住 x
    盖住关系: \(\text{COV}A=\{<x,y>|\text{y盖住x}\}\)
    例: (接着上面的例题)
    \(\text{COV}A=\{<2,6>,<3,6>,<2,8>\}\)

40. 哈斯图(Hasse Diagrams)
    作图顺序:

    1. 用小圆圈表示元素
    2. 若 \(x\preccurlyeq y\) , 将 y 画在 x 上方
    3. 若 \(<x,y>\in\text{COV}A\) , 则 x 和 y 之间用直线连接

    例: \(A=\{2,3,6,12,24,36\}\) , 求 \(<A,\text{整除}>\) 的哈斯图?
    解:
    \(\preccurlyeq=\{<2,2>,<3,3>,<6,6>,<6,2>,<6,3>,<12,12>,<12,6>,<12,3>, \\ <12,2>,<24,24>,<24,12>,<24,6>,<24,3>,<24,2>,<36,36>, \\ <36,12>,<36,6>,<36,3>,<36,2>\}\)
    \(\text{COV}A=\{<6,2>,<6,3>,<12,6>,<24,12>,<36,12>\}\)
    哈斯图如下:

41. 链: 设偏序集 \(<A,\preccurlyeq>\) , 若集合 \(A\) 中任何两个元素都有关系, 称 A 为链, A 的子集也是链
    (若任何元素都有关系, 则前者盖住后者, 哈斯图就是链状的)

42. 全序(线序): 设偏序集, \(<A,\preccurlyeq>\) , 如果 \(A\) 是链, 则称偏序关系 \(\preccurlyeq\) 为全序

43. 极大元和极小元
    设偏序集 \(<A,\preccurlyeq>\) , \(a\in A\)
    如果 \(A\) 中没有元素 \(x\) 能够 \(a\preccurlyeq x\) 且 \(x\neq a\) (即没有元素能再盖住 \(a\)), 称 \(a\) 为 \(A\) 的极大元;
    如果 \(A\) 中没有元素 \(x\) 能够 \(x\preccurlyeq a\) 且 \(x\neq a\) (即 \(a\) 不能盖住任何元素), 称 \(a\) 为 \(A\) 的极小元
    (极大元/极小元可以有多个)

44. 最大元和最小元
    设偏序集 \(<A,\preccurlyeq>\) ,
    如果\(\forall a\in A\) , 都有 \(x\preccurlyeq a\) , 则称 a 为 \(<A,\preccurlyeq>\) 的最大元;
    如果 \(\forall a\in A\) , 都有 \(a\preccurlyeq x\) , 则称 a 为 \(<A,\preccurlyeq>\) 的最小元.
    (即最大元只在极大元数量为1的时候存在)
    (即最小元只在极小元数量为1的时候存在)

45. 上界和下界
    设偏序集 \(<A,\preccurlyeq>\), 子集 \(B\subseteq A\) ,
    如果 \(\exist a\in A\) 且 \(\forall x\in B\) , 都有 \(x\preccurlyeq a\) , 则 \(a\) 为 \(B\) 的上界
    如果 \(\exist a\in A\) 且 \(\forall x\in B\) , 都有 \(a\preccurlyeq x\) , 则 \(a\) 为 \(B\) 的下界

46. 最小上界(上确界)和最大下界(下确界)
    设偏序集 \(<A, \preccurlyeq>\) , \(B\subseteq A\) ,
    若 \(a\) 为 \(B\) 的一个上界, 对于 \(B\) 的所有上界 \(x\), 都有 \(a\preccurlyeq x\) , 称 \(a\) 为最小上界(上确界)
    若 \(b\) 是 \(B\) 的一个下界, 对于 \(B\) 的所有下界 \(y\), 都有 \(y\preccurlyeq b\) , 称 \(b\) 为最大下界(下确界)

47. 良序: 设偏序集 \(<A,\preccurlyeq>\) , 若对于所有 \(B\subseteq A\) , \((B\neq\varnothing)\) , \(B\) 都存在最小元, 称此偏序为良序

48. 拟序: 反自反且传递的关系是拟序关系

49. 函数: 设集合 X, Y, f 是 X 到 Y 的一个关系, 如果对于 \(\forall x\in X\) , 都有唯一的 \(y\in Y\) , 使得 \(<x,y>\in f\) , 称关系 \(f\) 为函数
    记作 \(f:x\to y\) , \(x\in X\) 称作自变元, \(y\in Y\) 称作象
    象集 \(f(x)=\{f(x)|x\in X\}\subseteq Y\)
    函数=多对一映射

50. \(|x|=m\) , \(|Y|=n\)
    则从 X 到 Y 的关系有 \(2^{mn}\) 种 (可以理解由 \(nm\) 个序偶组成的集合, 它的幂集的元素就有 \(2^{mn}\) 个)
    从 X 到 Y 的函数有 \(n^m\) 种 (可以理解为 \(x\) 组成的序列, 每个 \(x\) 有 \(n\) 种可能, 共有 \(m\) 个 \(x\), 序列就有 \(n^m\) 种)

51. 满射(到上映射): 设 \(f:x\to y\) , 如果 \(Y\) 中每一个元素都是象, 则称 \(f\) 为满射. (即每个 \(y\) 都被利用)

52. 入射(单射;一对一映射): 设 \(f:x\to y\) , 如果 \(X\) 中没有两个元素有相同的象, 则称 \(f\) 为入射. (一个 \(x\) 对应一个 \(y\))

53. 双射(对应映射): 既是满射又是入射

54. 逆函数: 设双射函数 \(f:x\to y\) , 则 \(f\) 存在逆函数, 记作 \(f^{-1}\)

55. 复合函数: 设 \(f:x\to y\) , \(g:w\to z\) , 若 \(f(x)\subseteq w\) , 称 g 在 y 的左边可复合
    \(g\circ f=g(f(x))=\{<x,z>|\exist y, y=f(x)\land z=g(y)\}\)

    • 定理:
      设 \(g\circ f\) 是复合函数,
      若 \(g\) , \(f\) 是满射, 则 \(g\circ f\) 是满射
      若 \(g\) , \(f\) 是入射, 则 \(g\circ f\) 是入射
      若 \(g\) , \(f\) 是双射, 则 \(g\circ f\) 是双射

习题

1. 在自然数集上, 下列那种运算是不可交换的? (D) (这里 * 代表任意一种集合的运算)
   A. \(a\text{*}b=\text{min}(a,b)\)
   B. \(a\text{*}b=a+b\)
   C. \(a\text{*}b=\text{max}(a,b)\)
   D. \(a\text{*}b=a-b\)

2. 若集合 A 有 101 个元素, 则 A 的幂集有___ \(2^{101}\) ___个元素

3. 下列各项错误的是 (A)
   A. \(\{x\}\in\{x\}\)
   B. \(\{x\}\subseteq\{x\}\)
   C. \(\{x\}\in\{x,\{x\}\}\)
   D. \(\{x\}\subseteq\{x,\{x\}\}\)

4. 设
   \(M=\{x|(x\text{是整数})\land(1\leqslant x\leqslant 12)\land(x\text{被2整除})\}\)
   \(N=\{x|(x\text{是整数})\land(1\leqslant x\leqslant 12)\land(x\text{被3整除})\}\)
   则 \(M\cap N=\) ___ \(\{6,12\}\) ___

5. 证明 \(A\cap(B\oplus C)=(A\cap B)\oplus(A\cap C)\)
   证明:
   \(\begin{aligned} \text{左边} &=A\cap((B-C)\cup(C-B)) \\ &=(A\cap(B-C))\cup(A\cap(C-B)) \end{aligned}\)
   \(\begin{aligned} \text{右边} &=((A\cap B)-(A\cap C))\cup((A\cap C)-(A\cap B)) \\ &=((A\cap B)\cap\sim(A\cap C))\cup((A\cap C)\cap\sim(A\cap B)) \\ &=((A\cap B)\cap(\sim A\cup\sim C))\cup((A\cap C)\cap(\sim A\cup\sim B)) \enspace(\text{分配律拆右边}) \\ &=(A\cap B\cap\sim C)\cup(A\cap\sim B\cap C) \end{aligned}\)
   所以左边=右边
   证毕

6. 下列等式不成立的是 (A)
   A. \(A\cup(B\times C)=(A\cup B)\times(A\cup C)\)
   B. \(A\times(B\cup C)=(A\times B)\cup(A\times C)\)
   C. \((A\cup B)\times C=(A\times C)\cup(B\times C)\)
   D. \((A\cap B)\times C=(A\times C)\cap(B\times C)\)

7. 简答: 设 A 和 B 是两个非空集合, \(A\times B=B\times A\) 吗?
   答:
   不相等, 除非 A=B, 则成立.
   例如 \(A=\{1,2\}\) , \(B=\{3,4\}\)
   \(A\times B=\{<1,3>,<1,4>,<2,3>,<2,4>\}\)
   \(B\times A=\{<3,1>,<3,2>,<4,1>,<4,2>\}\)
   显然 \(A\times B\neq B\times A\)

8. 解释二元关系: 任意集合A、B, A×B 的子集称作 A 到 B 的关系

9. 在一个有 4 个元素的集合上, 可以定义不同的关系个数为 (D)
   A. \(2^4\)
   B. \(4^4\)
   C. \(2^{4^4}\)
   D. \(2^{4^2}\)
   (序偶有 \(4^2\) 种, 把这些序偶视作元素, 能组成 \(2^{4^2}\) 种集合)

10. 设 \(X=\{0,1,2,3,4,5,6\}\) , 其上关系 \(R=\{<x,y>|(x<y)\land (x是质数)\}\) , 写出关系 \(R\) 中的元素并求出 \(\text{dom R}\) , \(\text{ran R}\) 以及 \(\text{FLDR}\)
    解:
    \(R=\{<2,3>,<2,4>,<2,5>,<2,6>,<3,4>,<3,5>,<3,6>,<5,6>\}\)
    \(\text{dom R}=\{2,3,5\}\)
    \(\text{ran R}=\{3,4,5,6\}\)
    \(\text{FLDR}=\{2,3,4,5,6\}\)

11. 设 \(A=\{1,3,5,7\}\) , 定义 A 上的二元关系 \(R\) , \(<a,b>\in R\Harr a<b\) , 称 \(R\) 为小于关系, 记为 \(<\) , 试求出 \(R\) , \(\text{dom R}\) , \(\text{ran R}\) 以及 \(\text{FLDR}\)
    解:
    \(R=\{<1,3><1,5>,<1,7>,<3,5>,<3,7>,<5,7>\}\)
    \(\text{dom R}=\{1,3,5\}\)
    \(\text{ran R}=\{3,5,7\}\)
    \(\text{FLDR}=\{1,3,5,7\}\)

12. 设 \(A=\{1,2,3\}\) , \(A\) 的二元关系 \(R=\{<2,1>,<2,3>,<1,2>,<3,2>\}\) , 则 R 共有的性质是 (B)
    A. 自反性
    B. 对称性
    C. 传递性
    D. 反对称性

13. 给定 \(A=\{1,2,3,4\}\) , \(A\) 上的二元关系 \(R=\{<1,3>,<1,4>,<2,3>,<2,4>,<3,4>\}\) , 则 \(R\) 满足的性质是 (C)
    (思路, 一个一个按顺序找, 比如<1,3>, 接下来就找以3开头的序偶看是否满足传递性条件)
    A. 自反性
    B. 对称性
    C. 传递性
    D. 不可传递性

14. 若关系 \(R\) 是反对称的, 当且仅当关系矩阵中主对角线为对称的元素不能同时为1

15. 名词解释: 对称关系
    答: 设关于集合 \(X\) 的关系 \(R:X\) , \(x,y\in X\) , 对于每一个 \(xRy\) , 都有 \(yRx\) , 则称关系 \(R\) 是对称的.

16. 已知集合 \(A=\{a,b,c\}\) , \(A\) 上的二元关系 \(R_1=\{<a,b>,<c,b>\}\) , \(R_2=\{<a,c>,<b,c>\}\) , 则 \(R_1\circ R_2\) (A)
    A. \(\{<a,c>,<c,c>\}\)
    B. \(\{<a,b>,<b,c>\}\)
    C. \(\{<a,c>,<c,a>\}\)
    D. \(\{<a,a>,<c,b>\}\)

17. 设 \(A=\{0,1,2\}\) , \(B=\{0,2,4\}\) , 关系 \(R=\{<a,b>|a,b\in A\cap B\}\)
    求 \(R^{-1}\) 以及 \(M_{R^{-1}}\)
    答: (解答题关键步骤要写在答题纸上)
    \(A\cap B=\{0,2\}\)
    \(R=\{<0,0>,<0,2>,<2,0>,<2,2>\}\)
    \(R^{-1}=\{<0,0>,<2,0>,<0,2>,<2,2>\}\)
    \(M_{R^{-1}}=\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}\)

18. 设 \(A=\{a,b,c\}\) , \(A\) 上的二元关系 \(R=\{<a,a><b,b><a,c>\}\) , 则 \(s(R)\) 等于 (B)
    A. \(R\cup I_A\)
    B. \(R\cup\{<c,a>\}\)
    C. \(R\cap I_A\)
    D. \(R\)

19. 已知集合 \(A=\{a,b,c\}\) 上关系 \(R=\{<a,a>,<a,b>\}\) 则 \(s(R)\) 等于 (B)
    A. \(<a,a>,<b,a>\)
    B. \(<a,a>,<a,b>,<b,a>\)
    C. \(<a,a>,<b,b>,<c,c>\)
    D. \(<a,a>,<a,b>,<b,a>,<b,b>\)

20. 自反闭包: 设 R:X , 如果另一个关系 R’ 满足: 1. R’ 是自反的; 2. R’⊇R; 3. 对于任何自反的关系 R’‘, 如果 R’‘⊇R , 就有 R’‘⊇R’. 则称 R’ 为 R 的自反闭包.

21. 设 \(A=\{1,2,3,4\}\) , \(A\) 上等价关系 \(R=\{<1,2>,<2,1>,<3,4>,<4,3>\}\cup I_A\)
    则对应于 \(R\) 的 \(A\) 的划分是 (D)
    A. \(\{\{1\},\{2,3\},\{4\}\}\)
    B. \(\{\{1,2\},\{3\},\{4\}\}\)
    C. \(\{\{1\},\{2\},\{3\},\{4\}\}\)
    D. \(\{\{1,2\},\{3,4\}\}\)

22. 集合 \(A\) 上的等价关系 \(R\) , 其等价类的集合称为 (C)
    A. \(A\) 与 \(R\) 的并集, 记作 \(A\cup R\)
    B. \(A\) 与 \(R\) 的交集, 记作 \(A\cap R\)
    C. \(A\) 与 \(R\) 的商集, 记作 \(A/R\)
    D. \(A\) 与 \(R\) 的差集, 记作 \(A-R\)

23. 设集合 \(X=\{1,2,3,4\}\)
    \(A_1=\{\{1,2,3\},\{3,4\}\}\)
    \(A_2=\{\{1,2\},\{3\}\}\)
    \(A_3=\{\{1\},\{2\},\{3,4\}\}\)

    1. 判断 \(A_1\) , \(A_2\) , \(A_3\) 分别是否是 \(A\) 的覆盖? 划分呢?
    2. 写出 \(X\) 的划分所确立的等价关系

    解:

    1. \(A_1\) , \(A_3\) 是覆盖, \(A_2\) 既不是覆盖也不是划分, \(A_3\) 也是划分
    2. \(R=\{<1,1>,<2,2>,<3,3>,<3,4>,<4,3>,<4,4>\}\)

24. 给定集合 \(A\) 上的关系 \(R\) , 若 \(R\) 是自反, 对称的, 则称 \(R\) 是 \(A\) 上的相容关系.

25. 相容关系: 设 R:A , 若 R 是自反的、对称的, 则 R 是相容关系

26. 设 \(Z\) 为整数集, 下面哪个序偶不构成偏序集 (A)
    A. \(<Z,<>\)
    B. \(<Z,\leqslant>\)
    C. \(<Z,\geqslant>\)
    D. \(<Z,/>\)

27. 已知集合 \(A=\{1,2,3,4,5,6\}\) , R 是 A 上的整除关系, 则 A 的极小元是 (A)
    A. 1 B. 2 C. 3 D. 4

28. 设 A 是 18 的 除 1 以外的正因数组成的集合, “/” 为整除关系.
    画出 <A, /> (整除), 的哈斯图; 若存在的话, 分别求其最小元, 最大元, 极小元, 极大元, 上界, 下界, 上确界, 下确界
    解:
    \(A=\{2,3,6,9,18\}\) , \(\text{COV}A=\{<3,2>,<6,3>,<9,6>,<18,9>\}\)
    哈斯图:

    最大元: 18
    最小元: 没有
    极大元: 18
    极小元: 2, 3
    上界: 18
    下界: 没有
    上确界: 18
    下确界: 没有

29. 设 \(X=\{1,3,4,12,24\}\) , R 是 X 的整除关系

    1. 求出关系 R
    2. 画哈斯图
    3. 求子集 \(\{3,4,12\}\) 的极大元, 最大元, 上界, 上确界

    解:
    \(R=\{<1,1>,<1,3>,<1,4>,<1,12>,<1,24>,<3,3>,<3,12>, \\ <3,24>,<4,4>,<4,12>,<4,24>,<12,12>,<12,24>,<24,24>\}\)
    哈斯图:

    极大元: 12
    最大元: 12
    上界: 12, 24
    上确界: 12

30. 集合 A 上的拟序关系: 反自反且传递的关系是拟序关系

31. 设 \(X=\{1,2,3,4\}\) , \(Y=\{a,b,c,d\}\) (C) (因为 B 中没有 4 的映射)
    则下列哪个集合是 \(X\to Y\) 的函数
    A. \(\{<1,b>,<2,c>,<3,d>,<3,a>\}\)
    B. \(\{<1,b>,<2,b>,<3,d>\}\)
    C. \(\{<1,b>,<2,d>,<3,a>,<4,d>\}\)
    D. \(\{<1,b>,<1,d>,<3,d>,<4,d>,<2,b>\}\)

32. 求出从 \(A=\{1,2\}\) 到 \(B=\{x,y\}\) 的所有函数, 并列出哪些双射, 哪些满射?
    解:
    \(f_1=\{<1,x>,<2,x>\}\)
    \(f_2=\{<1,x>,<2,y>\}\)
    \(f_3=\{<1,y>,<2,x>\}\)
    \(f_4=\{<1,y>,<2,y>\}\)
    双射: \(f_2\) , \(f_3\)
    满射: \(f_2\) , \(f_3\)

33. 设 \(f:\{1,2\}\to\{1\}\) , 则 f 是 (B)
    A. 入射
    B. 满射
    C. 双射
    D. 非入非满

34. 设 \(A=\{0,1\}\) , \(N\) 是自然数集合, \(f(x) \begin{cases} 0 & x\text{是奇数} \\ 1 & x\text{是偶数} \end{cases}\)
    若 \(f:A\to A\) . 则 \(f\) 是 双射 (填"入",“满”,“双”)

35. 设 \(A=\{1,2,3,4\}\) , \(A\) 上的关系 \(R_1=\{<1,2>,<3,4>,<2,3>,<4,1>\}\) , \(R_2=\{<1,2><2,3>,<3,2>\}\)
    则 \(R_1\) , \(R_2\) 中是映射的是 (B)
    A. \(R_1\) , \(R_2\)
    B. \(R_1\)
    C. \(R_2\)
    D. 没有

36. 一个映射 \(f:x\to y\) , 如果对于任意 \(x_i,x_j\in X\) . 都有 ___ \(f(x_i)\neq f(x_j)\) ___, 则 \(f\) 是入射

37. 设 R 是 A 的等价关系, 在什么条件下, 自然映射 \(g:A\to A/R\) 是双射?
    解: 因为 \(A/R\) 是等价关系 R 的等价类构成的集合, 即商集
    要使映射 \(g:A\to A/R\) 是双射, 则 \(A/R\) 与 A 的元素个数必须相等, 因此 R 必须是恒等关系 \(I_A\)

38. 若 \(g\) , \(f\) 是满射, 则 \(g\circ f\) 是满射

代数系统

1. 代数系统: 一个非空集合 A 和定义在该集合上的若干种运算所组成的系统, 记作 \(<A,f_1,f_2,…,f_k>\)
   例:
   \(<N^+,+>\) 在正整数集合上的加法运算
   \(<P(s),\cap,\cup,\sim>\)

2. 封闭性:
   (对于任意的集合中的两个元素, 如果这两元素作某种运算, 运算结果仍在该集合内, 则该运算在这个集合上是封闭的)
   设集合 \(A\) , 一个从 \(A^n\) 到 \(B\) 的映射, 称为 \(A\) 上的 \(n\) 元运算,
   如果 \(B\subseteq A\) , 称该 \(n\) 元运算是封闭的

   另一种定义:
   设 * 是集合 A 上的二元运算, 对于 \(\forall x,y\in A\) , 都有 \(x*y\in A\) , 则称 * 在 A 是封闭的
   例:
   \(A=\{2^n|n\in N\}\)
   \(2^a\times2^b\in A\) A 是封闭的
   \(2^a+2^b\notin A\) A 不是封闭的

3. 交换律: 设 * , \(\forall x,y\in A\) , 都有 \(x*y=y*x\) , 则称 * 是可交换的

4. 结合律: 设 * , \(\forall x,y,z\in A\) , 都有 \((x*y)*z=x*(y*z)\) , 则称 * 是可结合的

5. 分配律: 设 \(*\)、\(\Delta\) , \(\forall x,y,z\in A\) , 都有
   \(x*(y\Delta z)=(x*y)\Delta(x*z)\) ,
   \((y\Delta z)*x=(y*x)\Delta(z*x)\)
   则称 \(*\) 对 \(\Delta\) 是可分配的

6. 吸收律: 设 \(*\) , \(\Delta\) 是可交换的, 如果 \(\forall x,y\in A\) , 都有
   \(x*(x\Delta y)=x\)
   \(x\Delta(x*y)=x\)
   则称 \(*\) , \(\Delta\) 满足吸收律

7. 幺元(单位元): 设 \(*\) , \(\exist e_l\) , 对于 \(\forall x\in A\) ,
   都有 \(e_l*x=x\) , 则称 \(e_l\) 为左幺元
   都有 \(x*e_l=x\) , 则称 \(e_l\) 为右幺元

8. 零元: 设 \(*\) , 如果他 \(\theta_l\in A\) , \(\forall x\in A\) ,
   都有 \(\theta_l*x=\theta_l\) 则称 \(\theta_l\) 为左零元
   都有 \(x*\theta_l=\theta_l\) 则称 \(\theta_l\) 为右零元

9. 逆元: 设 \(*\) , \(e\) 是幺元, 若 \(b*a=e\) , 则称 b 是 a 的左逆元, a 是 b 的右逆元
   (\(a\) 的逆元记作 \(a^{-1}\))
   若 b 既是左逆元又是右逆元, 则称 b 是逆元
   设 \(<A,*>\) , 若 \(*\) 是可结合的, 则左逆元等于右逆元且唯一

10. 广群: 设代数系统 \(<S,*>\) , 如果 \(*\) 是封闭的, 则称 \(<S,*>\) 为广群.

11. 半群: 设代数系统 \(<S,*>\) , 如果:

    1. \(*\) 是封闭的
    2. \(*\) 是结合的, 即 \(\forall a,b,c\in S\) , \((a*b)*c=a*(b*c)\)

    则称 \(<S,*>\) 为半群.
    (半群是一种特殊的广群)

12. 子半群: 设 \(<S,*>\) 是半群, \(B\subseteq S\), 若 \(<B,*>\) 也是半群, 则 \(<B,*>\) 为 \(<S,*>\) 的子半群

13. 独异点: 含有幺元的半群

14. 群: 设代数系统 \(<S,*>\), 如果:

    1. \(*\) 是封闭的
    2. \(*\) 是结合的
    3. 存在幺元 \(e\)
    4. \(\forall x\in S\) , 都存在逆元 \(x^{-1}\)

    则 \(<S,*>\) 为群.

15. 群的特性:
    设群 \(<G,*>\) ,

    • 若 \(G\) 为有限集, 则有有限解,
    • 若 \(G\) 为无限集, 则有无限解.
    • 集合中元素的个数称为基数, 记作 \(|G|\)
      则 \(|G|\) 称为有限群 \(<G,*>\) 的阶数
    • 群中不可能有零元. (因为群中每个元素都要有逆元, 但是零元没有逆元)
    • 概念的关系: \(\text{广群}\supset\text{半群}\supset\text{独异点}\supset\text{群}\)

16. 子群: 设群 \(<G,*>\) , \(B\subseteq G\) , 如果 \(<B,*>\) 也是群, 则 \(<B,*>\) 为 \(<G,*>\) 的子群

17. 格: 设偏序集 \(<A,\preccurlyeq>\) , 如果 \(A\) 中每两个元素组成的子集都有最小上界和最大上界, 则称 \(<A,\preccurlyeq>\) 为格.
    例:
    \(<I_+,/>\) 是格, 正整数的整除关系是格
    (\(\forall a,b\in I_+\) , 则 \(a,b\) 的最小上界是最小公倍数; 最大下界是最大公约数)
    \(<P(S),\subseteq>\) (幂集上的包含于关系)也是格

18. 格诱导的代数系统:
    例: 设 \(<A,\preccurlyeq>\) 是格, 定义运算 \(a\lor b\) 为 \(a\) 与 \(b\) 的最小上界, \(a\land b\) 为 \(a\) 与 \(b\) 的最大下界.
    则称 \(<A,\land,\lor>\) 为格 \(<A,\preccurlyeq>\) 诱导的代数系统.

19. 分配格:
    设 \(<A,\lor,\land>\) 是由 \(<A,\preccurlyeq>\) 格诱导的代数系统. \(\forall a,b,c\in A\).
    若
    \(a\land(b\lor c)=(a\land b)\lor(a\land c)\)
    \(a\lor(b\land c)=(a\lor b)\land(a\lor c)\)
    则称 \(<A,\preccurlyeq>\) 为分配格
    例:
    \(A=P(S)\) , \(S=\{a,b,c\}\)
    \(<A,\cap,\cup>\) 是由格 \(<A,\subseteq>\) 诱导的代数系统, 且 \(<A,\subseteq>\) 是分配的

    • 定理: 小于五个元素的格一定是分配格
    • 定理: 每个链都是分配格
    • 定理: 一个格是分配格当且仅当该格不包含和钻石格或五角格同构的子格

    例:

    1. 钻石格不是分配格!

       图中 \(a\land(b\lor c)\neq(a\land b)\lor(a\land c)\)

    2. 五角格不是分配格!

习题

1. 在实数域 \(R\) 上定义运算 \(*\)
   \(a*b=a+b+2ab\) , 则 \(<R,*>\) 是代数系统

   1. \(*\) 满足结合律?
   2. \(<R,*>\) 有单位元, 求 \(e\)
   3. \(<R,*>\) 每一个元素都有逆元?
      任一个元素 a 的逆元是什么?

   解:

   1. \(\forall a,b,c\in R\) , 由于
      \((a*b)*c=(a+b+2ab)+c+2c(a+b+2ab)=a+b+2ab+c+2ac+2bc+4abc\)
      \(a*(b*c)=a+(b+c+2bc)+2a(b+c+2bc)=a+b+c+2bc+2ab+2ac+4abc\)
      上面两式结果相等, 所以 \(*\) 满足结合律
   2. 设单位元为 \(e\)
      \(\forall x\in R\) , 都有 \(x*e=x\) , 即 \(x+e+2xe=x\) , \(e(1+2x)=0\) , 则 \(e=0\)
   3. \(\forall a\in R\) , 设逆元为 \(b\) , 则 \(a*b=e=0\) , \(a+b+2ab=0\) , \(b=\frac{-a}{1+2a}\)
      若 \(a=-\frac{1}{2}\) , 则 a 无逆元, 否则 \(b=a^{-1}=\frac{-a}{1+2a}\)
      (因为这里涉及到分母为 0 的情况, 所以"若 \(*\) 是可结合的, 则左逆元等于右逆元且唯一"不适用)

2. 如果一个独异点 \(<A,*>\) 满足 A中每个元素都有逆元. 则 \(<A,*>\) 为群.

3. 群 \(<G,*>\) , 其中 \(G\) 为有限集. 则称 \(<G,*>\) 为有限群. \(G\) 的阶是 G 中元素的个数

4. 设 \(<G,*>\) 是群, \(H\) 是 \(G\) 的非空子集, \(H\) 是 \(G\) 的子群当且仅当 ___ \(<H,*>\) 也是群 ___

5. 设 \(G\) 为无限群, 则 (C)
   A. \(G\) 是交换群
   B. \(G\) 是循环群
   C. \(G\) 中每个元素都有逆元
   D. \(G\) 中每个元素的阶都是无限的
   (交换群: 满足交换律的群; 循环群: 群中任何元素可用某一个元素来表示)

6. 设 \(<H,*>\) 是群 \(<G,*>\) 的子群,
   \(<K,*>\) 是群 \(<H,*>\) 的子群.
   求证: \(<K,*>\) 是 \(<G,*>\) 的子群
   证明:
   \(\because <H,*>\) 是群 \(<G,*>\) 的子群
   \(\therefore H\subseteq G\)
   \(\because <K,*>\) 是群 \(<H,*>\) 的子群
   \(\therefore K\subseteq H\)
   \(\therefore K\subseteq G\)
   \(\because <K,*>\) , \(<G,*>\) 都是群
   \(\therefore <K,*>\) 是 \(<G,*>\) 的子群

7. 设 \(Z_4\) 为模 4 剩余类的集合
   \(Z_4=\{[0],[1],[2],[3]\}\)
   \(+_4\) 为模 4 加法, 写出 \(<Z_4,+_4>\) 的运算表并证明 \(<Z_4,+_4>\) 为群
   (模 4 剩余类即取模 4 后结果为 0、1、2、3 的那些数)
   (如结果为 0 的数集用 \([0]=\{\dots, 0,4,8,\dots\}\) 表示)
   运算表:

   \(+_4\)	\([0]\)	\([1]\)	\([2]\)	\([3]\)
   \([0]\)	\([0]\)	\([1]\)	\([2]\)	\([3]\)
   \([1]\)	\([1]\)	\([2]\)	\([3]\)	\([0]\)
   \([2]\)	\([2]\)	\([3]\)	\([0]\)	\([1]\)
   \([3]\)	\([3]\)	\([0]\)	\([1]\)	\([2]\)
   证明:
   \(<Z_4,+_4>\) 是代数系统

   1. \(+_4\) 是封闭的
   2. \(+_4\) 是可结合的
   3. 存在幺元 \([0]\)
   4. \([0]^{-1}=[0]\)
      \([1]^{-1}=[3]\)
      \([2]^{-1}=[2]\)
      \([3]^{-1}=[1]\)

   \(\therefore <Z_4,+_4>\) 是群

8. 设 \(<G,*>\) 为群, 定义关系 \(R\) 为 \(G\times G\) 的子集.
   其中 \(R=\{<a,b>|\exist c\in G, \text{使} b=c*a*c^{-1}\}\)
   试证 \(R\) 是 \(G\) 上的等价关系.
   证明: 只需证得 \(R\) 具有自反性、对称性、传递性即可

   1. \(\forall a\in G\), 有 \(a=a*e=a*a*a^{-1}\)
      则有 \(<a,a>\in R\) , \(R\) 具有自反性
   2. 对于 \(\forall <a,b>\in R\) , \(\exist c\in G\) , 使 \(b=c*a*c^{-1}\)
      \(b*c=c*a*c^{-1}*c=c*a*e=c*a \Harr c^{-1}*b*c=c^{-1}*c*a=a\)
      即 \(a=c^{-1}*b*c\) , 运用换元法设 \(d=c^{-1}\) , 则 \(a=d*b*d^{-1}\) , 因此 \(<b,a>\in R\) , \(R\) 具有对称性
   3. \(\forall a,b,c\in G\) , \(<a,b>\in R\) , \(<b,c>\in R\)
      则 \(\exist e,f\in G\) , 使得
      \(b=e*a*e^{-1}\)
      \(c=f*b*f^{-1}\)
      则 \(c=f*e*a*e^{-1}*f^{-1}=(f*e)*a*(f*e)^{-1}\)
      则 \(<a,c>\in R\)
      \(R\) 具有传递性

   综上, \(R\) 是等价关系.

9. 若 \(<A,\preccurlyeq>\) 是 偏序集, 且 A 中每两个元素都有最小上界和最大下界, 则称 \(<A,\preccurlyeq>\) 为格.

10. 格: 若 <A,≼> 是偏序集, 且 A 中每两个元素都有最小上界和最大下界, 则称 <A,≼> 为格.

11. 以下格是分配格的 (C)
    A. 钻石格
    B. 五角格
    C. 少于 5 个元素的格
    D. 含有与钻石格同构的格

图论

1. 图: \(G=(V,E)\) , 图 \(G\) 是由顶点集 \(V\) 和边集 \(E\) 构成的. 其中 \(E\) 的每一条边连接顶点集 \(V\) 中的一个或两个顶点.
   例如: \(e_2\) 与 \(V_2\) , \(V_4\) 关联的.
   环(loop): 关联的边只有一个顶点
   度数(deg(V)): 与顶点 V 关联的边数, \(\displaystyle\sum_{v\in V}deg(v)=2|E|\) . 用 \(\Delta(G)\) 表示图 \(G\) 的最大结点度数

   • 入度(\(deg_-(V)\))
   • 出度(\(deg_+(V)\))
   • 性质 \(\displaystyle\sum_{v\in V}deg_+(v)=\displaystyle\sum_{v\in V}deg_-(v)=|E|\)

   零图: \(|E|=0\)
   平凡图: \(|E|=0\) , \(|V|=1\)
   有向图(directed G/digraph): 所有的边有方向
   无向图(undirected G): 所有的边没有方向
   复杂图: 有的边有方向有的边无方向
   简单图(无平行边/无环的图)
   多重图(有平行边/有环的图)
   完全图(\(C_n^2=\frac{n(n-1)}{2}\) 条边 \(K_n\)): 所有顶点两两相连
   补图(\(G=k_n-G\) 只对边作差): 完全图-原图
   同构: 设图 G=(V,E) 和 G’=(V’,E’) 如果存在一一对应的映射 \(g:v_i\to v_i’\) , 而且 \(e=(v_i,v_j)\) 是 G 的一条边, 当且仅当 \(e’=(g(v_i),g(v_j))\) 也是 \(G’\) 的一条边, 则称 \(G\) 与 \(G’\) 同构, 记 \(G\cong G’\)

2. 子图: 设 \(G=(V,E)\) , \(G’=(V’,E’)\) , \(V’\subseteq V\) , \(E’\subseteq E\) , 则 \(G’\) 为 \(G\) 的子图
   例: \(G:k_3\) , 求子图

   需要分类讨论:

   1. 1 个顶点: 3 个子图
   2. 2 个顶点:
      1. 0 条边: 3 个子图
      2. 1 条边: 3 给子图
   3. 3 个顶点:
      1. 0 条边: 1 个子图
      2. 1 条边: 3 个子图
      3. 2 条边: 3 个子图
      4. 3 条边: 1 个子图

   共计 17 个子图

3. 路: 设图 \(G=(V,E)\), 顶点 \(v_0,v_1,\dots,v_n\in V\) , 边 \(e_1,e_2,\dots,e_n\in E\)
   从 \(v_0\) 出发, 沿着 \(v_0e_1v_1e_2v_2\dots e_iv_i\dots e_nv_n\) 的交替序列称为路(walk)
   若 \(v_0=v_n\) 称为回路(closed walk)
   若 \(\forall i\forall jE_i\neq E_j\) 称为迹(trail)
   若 \(\forall i\forall jV_i\neq V_j\) 称为通路(path)
   既是通路又是回路称为圈(cycle)

4. 顶点连通性: 若顶点 \(u\) 和 \(v\) 至今存在一条路, 则称 \(u\) 和 \(v\) 是连通的
   图的连通性: 给定图 \(G=(V,E)\) , 若 \(\forall u,v\in V\) , \(u\) 和 \(v\) 都是连通的, 则称图 \(G\) 是连通的
   连通分支(connected component): 最大连通子图

5. 顶点之间的距离(distance): 两个顶点之间的最短路的长度

6. 图的直径(diameter): 图中顶点间最大距离 \(D=\text{max}d(u,v)\) , \(u,v\in V\)

7. 有向图中:
   可达: 从 \(u\) 到 \(v\) 存在一条路, 则称 \(u\) 可达 \(v\)
   强连通图: 若简单有向图中, 任何一对顶点之间都是相互可达(能去能回)的, 则称该图为强连通图.
   弱连通图: 若简单有向图不是强连通的, 但是省略边的方向得到的无向图是连通的, 称该简单有向图是弱连通的.

8. 图的表示:

   • 列举法
   • 画图
   • 矩阵
     • 邻接矩阵
     • 关联矩阵(不考)
     • 可达性矩阵(不考)

9. 邻接矩阵: 设简单图 \(G=(V,E)\) , \(|V|=n\) , 则构造 \(A(G)=(a_{ij})_{n\times m}\) 为 \(G\) 的邻接矩阵,
   其中 \(\begin{cases} 1 & \text{当} v_i \text{邻接} v_j \\ 0 & \text{当} v_i \text{不邻接} v_j \end{cases}\)

   • 计算 \(v_i\) 到 \(v_j\) 长度为 2 的路有几条?
     路的数目 \(=a_{i0}\cdot a_{0j}+a_{i1}\cdot a_{1j}+\cdots+a_{in}a_{nj}=\displaystyle\sum_{k=0}^{n-1} a_{ik}\cdot a_{kj}\)
     正好可以利用矩阵乘法来算
     (矩阵乘法: \(a_{ij}=\displaystyle\sum_{k=0}^{n-1} a_{ik}\cdot a_{kj}\) ， 即矩阵中 \(a_{ij}\) 元素的值为前者第 i 行的每项分别乘后者第 j 列的对应项再相加)
     则 \(v_i\) 到 \(v_j\) 长度为 \(n\) 条边的路有几条可通过 \(A^n(G)\) (矩阵的 n 次幂)得到

10. 欧拉路(欧拉通路): 给定一个无向图, 经过图中每条边一次且仅一次的路称为欧拉路.

11. 欧拉回路: 经过每条边一次且仅一次的回路称为欧拉回路.

12. 欧拉路充要条件: 无向图 \(G\) 具有欧拉路当且仅当 \(G\) 是连通的且有零个或两个奇数度数的顶点(若存在则必须从奇数度数顶点出发).

13. 欧拉回路充要条件: 无向图 \(G\) 具有欧拉回路当且仅当 \(G\) 是连通的且所有顶点度数都是偶数. (可从任意顶点出发)

14. 欧拉图: 具有欧拉回路的图

15. 平面图(Plane Graph): 设无向图 \(G=(V,E)\) , 如果能够把图中所有边画在一个平面上, 使任意两条边都不相交, 则称 \(G\) 为平面图.
    例子: \(k_{3,3}\) (二分图)和 \(k_5\) 都不是平面图

    • 库拉托夫斯基定理: 是平面图当且仅当图不包含 \(k_{3,3}\) 和 \(k_5\)

16. 面: 设连通平面图 \(G\) , 若由边包围的区域不包含任何顶点和边, 则该区域称为面.
    注意别忘了最外面的面包围的是外面所有区域(不是向里包围), 称为无限面
    面的次数 \(deg(r)\) : 组成面的边数
    定理: 设连通平面图 \(G\) , \(|E|=e\) , \(\sum deg(r)=2e\) (所有面的次数之和等于边数的 2 倍)

17. 欧拉定理
    设 \(G\) 是连通平面图， 有 \(v\) 个顶点 , \(e\) 条边, \(r\) 个面. 则 \(v-e+r=2\)

18. 定理: 设 \(G\) 是一个连通平面图, 有 \(v\) 个顶点, \(e\) 条边, 若 \(v\geqslant 3\) , 则 \(e\leqslant 3v-6\)

19. 树: 一个连通且无回路的无向图
    树叶: \(deg(v)=1\) 的结点
    内点: \(deg(v)>1\) 的结点
    森林: 由多棵树组成的图

20. 树的性质:

    1. \(v=e+1\)
    2. 无回路的树增加一条新边, 则得一个且仅一个回路
    3. 连通的树删除一条边则不连通
    4. 任何两个结点之间仅有一条路
    5. 至少有两片树叶

21. 生成树(spanning tree): 包含图 \(G\) 全部结点的子图如果是树, 则称该子图为生成树.
    在有权重的图中, 若它在所有的生成树中总权重最小, 则称为最小生成树.

22. 有向树: 给树的每一条边加个方向

23. 根树: 如果一颗有向树只有一个顶点入度为 0 其余结点入度均为 1
    根: \(deg_-(v)=0\) 的结点
    叶子: \(deg_+(v)=0\) 的结点
    内点: \(deg_+(v)>0\) 且 \(deg_-(v)\neq 0\) 的结点

24. \(n\) 叉树(\(m\) 叉树): 若根树中每个结点的出度小于等于 \(n\), 称这颗树为 \(n\) 叉树.
    若所有结点出度等于 \(n\) 或 0, 则称为完全 \(n\) 叉树.

习题

1. 图: 图由顶点集 V 和边集 E 构成, 其中 E 中的边连接 V 中的一个或两个顶点

2. 给定下列序列, 哪一个不能构成无向简单图的结点度数序列 (D) (无向简单图度数之和必为偶数)
   A. (1,1,2,2,4)
   B. (1,1,2,2,2)
   C. (2,1,3,3,3)
   D. (1,3,4,4,5)

3. 设简单图的最大结点度数为 \(\Delta(G)\) , 图中结点数为 \(n\) , 则 \(\Delta(G)\) 与 \(n\) 的关系 (B)
   A. \(\Delta(G)>n\)
   B. \(\Delta(G)<n\)
   C. \(\Delta(G)=n\)
   D. \(\Delta(G)\) 与 \(n\) 没关系

4. 由 \(n\) 个点 0 条边组成的图为 (A)
   A. 零图
   B. 完全图
   C. 平凡图
   D. 多重图

5. \(n\) 个结点的完全无向图 \(k_n\) 的边数为 ___ \(C_n^2=\frac{n(n-1)}{2}\) ___

6. 在有 3 个结点的图中, 度数是奇数的结点个数为 (D) (度数是奇数的结点个数必为偶数)
   A. 1
   B. 3
   C. 1 或 3
   D. 0 或 2

7. 不含多重边和环的图, 称为简单图

8. \(n\) 个结点的无向完全图的边数为 (D)
   A. \(n(n+1)\)
   B. \(\frac{n(n+1)}{2}\)
   C. \(n(n-1)\)
   D. \(\frac{n(n-1)}{2}\)

9. 含 5 个结点, 4 条边的无向简单图(不同构)的个数为 (B)
   A. 1
   B. 3
   C. 6
   D. 7
   (建议画图)

10. 在 5 阶图 G 中, 若从结点 \(v_1\) 到 \(v_4\) 存在路, 则从 \(v_1\) 到 \(v_4\) 必存在通路, 且长度小于等于 (D) (5 阶图就是顶点个数为 5)
    A. 1
    B. 2
    C. 3
    D. 4

11. 名词解释: 强连通性
    有向图中任意两个顶点相互可达

12. 给定有向图 \(G=(V,E)\) 如下

    试求:

    1. 各顶点的出入度
    2. 写出 \(G\) 的邻接矩阵
    3. 利用矩阵计算从点 1 到 4 长度分别是 1,2,3 的路各有几条.

    解:

    1. 顶点	1	2	3	4
       出度	2	2	2	1
       入度	0	3	1	3

    2. \(A(G)=\begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix}\)
    3. \(A^2(G)=\begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix}\times\begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix}=\begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 2 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}\)
       \(A^3(G)=A^2(G)\times A(G)=\begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 2 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}\times\begin{bmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix}=\begin{bmatrix} 0 & 2 & 1 & 2 \\ 0 & 1 & 2 & 2 \\ 0 & 2 & 1 & 2 \\ 0 & 2 & 0 & 1 \end{bmatrix}\)
       \(\therefore\) 从顶点 1 到 4 长度是 1, 2, 3 的路分别有 1, 1, 2 条.

13. 无向简单图的邻接矩阵: ___ \(G=(V,E)\) , \(|V|=n\), \(A(G)=(a_{ij})_{n\times n}\) 其中 \(a_{ij}=\begin{cases} 1 & v_i \text{邻接} v_j \\ 0 & v_i \text{不邻接} v_j \end{cases}\) ___

14. 设 \(M=(a_{ij})\) 是无向图 \(G=(V,E)\) 的邻接矩阵, \(M^k\) 中第 \(i\) 行 第 \(j\) 列的元素值表示, 从 \(v_i\) 到 \(v_j\) 长度是 \(k\) 的路的数目

15. 设无向图 \(G=(V,E)\) , 其中 \(V=\{1,2,3,4,5\}\) , \(E=\{(1,2),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)\}\)

    1. 画出 \(G\) 对应的图
    2. 求各顶点的度
    3. \(G\) 是否具有欧拉回路, 是否具有欧拉通路, 为什么? 如有请写出.

    解:

    2. 顶点	1	2	3	4	5
       度	2	4	3	3	4

    3. 没有欧拉回路, 因为有两个奇数度数的顶点.
       有欧拉通路. 如 3-4-2-3-5-2-1-5-4 (这里随便举一条欧拉回路即可)

16. 存在欧拉回路的图称为欧拉图

17. 设 \(G\) 是连通平面图, \(G\) 有 6 个顶点 8 条边, 则 \(G\) 的面数 (C)
    A. 2
    B. 3
    C. 4
    D. 5

18. 连通平面图 \(G\) 中, 所有面的次数之和 (C)
    A. 边数
    B. 边数的一半
    C. 边数的两倍
    D. 边数的已被

19. 若某连通平面图有 4 个顶点, 3 个区域, 则有5条边.

20. 设 \(G\) 为一个至少三个结点的连通平面图, 试证:
    \(G\) 中至少有一个结点的度数小于等于 5
    证明: (反证法)
    设 \(G=(V,E)\) , \(|V|=v\) , \(|E|=e\)
    假设 \(G\) 中所有结点度数大于等于 6
    则 \(\displaystyle\sum_{i=1}^v deg(v_i)=2e\) (度数之和等于边数两倍)
    则 \(2e\geqslant 6v\)
    则 \(e\geqslant 3v\)
    则 \(e\geqslant 3v-6\)
    这与连通平面图应该具有的性质 \(e\leqslant 3v-6\) 矛盾.
    所以假设错误

21. 在根树中, 若每个结点的出度小于等于 m, 则称为 \(m\) 叉树.

22. 设 \(T\) 为根树, 若每个结点的出度都小于等于 m, 则称 T 为 m 叉树.

23. 在根树中, 如果每个结点的出度恰好等于m或零, 则称这棵树为完全 m 叉树.