• “x>y” 并非命题
  • 简单命题/原子命题：不含联结词的命题
  • P→Q 中，P 为前件/前项/条件，Q 为后件/后项/结论
  • 代入规则：从简单到复杂
  • ⊽ 异或 ↑与非 ↓或非
  • 除非：¬P→Q
  • 悖论并非命题
  • 推理形式：由前提和结论经蕴涵词联结而成的；正确的：重言的
  • 等值：AB共同的命题变项任一解释，且不同的命题变项任意解释，真值相同
  • 等值定理：A=B ⇔ A↔B
  • 置换规则：等值可任意替换
  • 等值公式：
    • 分配律：
      • P∨(Q∧R) = (P∨Q)∧(P∨R)
      • P∧(Q∨R) = (P∧Q)∨(P∧R)
      • P→(Q→R) = (P→Q)→(P→R)
    • 吸收律
      • P∨(P∧Q) = P
      • P∧(P∨Q) = P
    • 前提合并 P→(Q→R) = (P∧Q)→R = Q→(P→R)
    • (P→R)∧(Q→R) = (P∨Q)→R
    • 归谬论 (P→Q)∧(P→¬Q) = ¬P
  • n 元联结词个数：2^2^n
  • 基底：完备，联结词不能相互表示；元素不超过3个
  • ¬A = A*⁻；A〜A⁻，¬A〜A* （证明尽量避免星号）
  • 推理演算：前提引入，结论引用，代入规则，置换规则，分离规则，条件证明规则/附加前提
  • 归结证明：子句集，归结
  • 形式化
    • 有的 A 是 B：(∃x)(A(x)∧B(x))
    • A 都是 B 的：(∀x)(A(x)→B(x))
    • 仅当 A 才 B: B→A

集合论

  • 外延表示法：0,1,2 或 0,1,2,… 或 0,1,2,…,7,8,9

  • ZFC 集合论：

    • 外延公理：两个集合相等，当且仅当它们具有相同的元素
    • 空集公理：空集存在
    • 配对公理：集合的集合存在
    • 并集公理：并集存在
    • 幂集公理：幂集存在
    • 分离公理：集合通过内涵谓词构造的（子）集合存在
    • 无穷公理：存在 A ∅∈A∧∀x(x∈A→{x}∈A) （即自然数集存在）
    • 替换公理：∅ 对 A 的映射存在
    • 正则公理：每个非空集合 A 都包含一个与 A 不相交的元素（蕴含 不存在以自身为元素的集合）
    • 选择公理：集合组可选出元素组

  • 有序对的 Kuratowski 定义：<x,y> = if x≠y {{x},{x,y}} else {{x}}

  • n 元组

  • 优先级：（同优先级从左到右）

    • 括号
    • 一元运算符 (−A, ∩A, ∪A)
    • 二元运算符 (◦, −, ∩, ∪, ⊕, ×)
    • 集合关系符 (=, ⊆, ⊂, ∈)
    • 一元联结词 (¬)
    • 二元联结词 (∧, ∨, →, ↔)
    • 逻辑关系符 (⇔, ⇒)

  • 幂集

    • 幂集的哈斯图
    • 幂集对与原集对 同子集，同相等
    • P(A − B) ⊆ (P(A) − P(B)) ∪ {∅}.

  • 传递集合：(∀x)((x ∈ A) → x ⊆ A). (⇔ A ⊆ P(A)); ∩A = ∅

  • 笛卡尔积对交并有分配律

  • 基数 #(A) = |A| = card(A) = n

  • P(A) 上的包含关系 R1 和真包含关系 R2

  • 恒等关系 IA，全域关系（全关系）EA，空关系∅

  • fld(R) = dom(R) ∪ ran(R)

  • fld(R) = ∪∪R

  • 象

    • R[A ∩ B] ⊆ R[A] ∩ R[B] （注意子集关系）
    • R[A] − R[B] ⊆ R[A − B]

  • 关系：

    • 自反 r：IA 的超集
    • 反自反 ρ：-IA 的超集
    • 对称 s：(∀x)(∀y)(xRy ↔ yRx) 或 R = R⁻¹
    • 反对称 σ：除了 IA 外 (∀x)(∀y)¬(xRy ∧ yRx) 或 R ∩ R⁻¹ ⊆ IA；并集未必反对称
    • 注意反对称和对称并非互补；其定义都是任意
    • 传递 t：(xRy ∧ yRz) → xRz 或 R◦R⊆R；并集未必传递

  • 闭包：

    • 自反 r：R∪I
    • 对称 s：R∪R⁻¹
    • 传递 t：Warshall 算法

  • 闭包关系

    • r => s t 也 r
    • s => r t 也 s
    • t => r 也 t
    • rt, rs 可交换，s 可破 t
    • 以下从右往左 （rs 即 r(s(R))）
    • rs = sr
    • rt = tr
    • st ⊆ ts
    • st 是不好的，它未必 t

  • 关系类

    • 等价：r,s,t；[x]_R 或 [x] 或 \bar x 为 x 关于 R 的等价类；商集；划分 π_R
    • 相容：r,s；覆盖 Ω；完全覆盖 C_R(A)
    • 偏序：r,σ,t；通常记作 ⩽
    • 拟序：ρ,(σ,)t
    • 偏序结构 ⟨A, R⟩

  • 偏序关系的哈斯图：关系图删去自圈、有向、传递

    • y 盖住 x：x⩽y ∧ ¬(∃z)(x⩽z∧z⩽y)
    • A 上的盖住关系 covA：{⟨x,y⟩ | y盖住x}

  • 界

    • 最大：B 内大于所有B；极大：B 内大于所有B可比较的
    • 上（确）界：A 内大于所有B

  • 链

    • 可比，全序/线序，链，反链
    • 对偏序集 ⟨A, ⩽⟩，若 A 中元素为 mn + 1 个，则 A 中或者存在一条长度为 m + 1 的反链，或者存在一条长度为 n + 1 的链

  • 良序集：A 的任何非空子集都有最小元；一个有限的全序集一定是良序集；任意的集合都是可以良序化的/任何集合都存在一个偏序关系使它良序

  • 函数：单值性 + A 为定义域；f⁻¹ 表示逆关系而非函数

    • 特征函数 χA (A⊆E)：E → {0, 1}, χA(a) = if a∈A 1 else 0
    • g(a) = [a]R：g 为从 A 到商集A/R 的典型映射/自然映射
    • 若 f ◦ g 是双射的，则 f 是满射的，g 是单射的。
    • f 存在左逆，当且仅当 f 是单射的；f 存在右逆，当且仅当 f 是满射的

note

  • 给定论域判断命题真值 尤其“存在”时，且有“→”时，要注意判断 F→? 的情形
  • 注意“对”“错”
  • 函数判断题 单射 满射 各举例子
  • 所有背不清楚的公式举例/列析取范式