🧮 CSC3001 LEC3-5 集合论、FOL和 基础证明法

(涵盖第 2 和第 3 个讲义)

LN2 Sets and FOL 集合论与谓词逻辑


II.1 集合论


集合的基本定义

  • 集合(set)：无序(unordered) 且元素互不重复(distinct) 的元素群。元素本身可以是集合
  • 幂集(power set)： 对于集合 A，其幂集 P(A) = { S｜S ⊆ A }，即其所有子集的集合。比如 P({a, b}) = {ø, {a}, {b}, {a, b}}
  • 基数(size / cardinality)： |A| = “A 的元素数”
  • 幂集的基数： |P(A)| = “A 的子集个数”(含空集与本身)。如果集合 A 含有 n 个元素，那么它的幂集有 2n 个元素。A 的幂集基数是 A 的子集个数，同时也是 A 的幂集的元素个数：|P(A)| =2|A|


集合运算

  • Union 并集 A ∪ B：属于 A 或 B（或二者）的所有元素。$$\bigcup_{i=0}^{n} A_i = {, x \in U \mid \exists\ i=0,1,2,\dots,n\ ;so\ x \in A_i \ }$$
  • Intersection 交集 A ∩ B：同时属于 A 与 B 的元素。$$\bigcap_{i=0}^{n} A_i = {, x \in U \mid\ \forall\ i=0,1,2…n\ ;x \in A_i \ always\ hold\ } $$
  • Difference 差集 A \ B：属于 A 但不在 B 的元素。( 课本记作 A - B)
  • Complement 补集 Aᶜ：相对于全集 U，不在 A 的元素。
  • Subset 子集 A ⊆ B：A 的每个元素都在 B；真子集用 ⊊。

partition of sets(集合的划分)

将一个集合 A 变成一个包含一些“两两不相交”且并集恰为 A 的子集的集合 a set of subsets of A which are pairwise/mutual disjoint, and their union is A

cartesian product(笛卡尔积)

  • 定义：A × B x C = { (a, b, c) | a ∈ A, b ∈ B, c ∈ C }
  • ordered(有序性)：(1,2) ≠ (2,1), A x B ≠ B x A if A ≠ B
  • |A x B x C| = |A| x |B| x |C|


集合恒等式(Identities)

Commutative 交换, Associative结合, Distributive分配, Identity 恒等, Complement 补集, De Morgan：(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ；(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ, Difference law(差集)：A - B = A ∩ Bᶜ。




II.2 谓词逻辑(First Order Logic)


Predicates(谓词)

带变量的命题，例如：

  • P(x, y): x+2=y。

  • P(1,3) 为真；¬P(1,4) 为真。 Domain(论域)：变量可取的值的范围


Quantifiers(量词)

Universal Quantifier(全称量词 ∀)

  • ∀ x ∈ D, P(x) 表示“对 D 中所有 x，命题 P(x) 成立”。
  • 代表了 Proposition Logic 的“交集(∩) / AND(∧)”： $$\forall x \in \mathbb{Z}^+,\ \ P(x) = P(1)\land P(2)\land P(3)\dots$$

Existential Quantifier(存在量词 ∃)

  • ∃ x ∈ D, P(x) 表示“在 domain D 中至少有一个 x，使得 P(x) 成立”。
  • 代表了 Proposition Logic 的“并集(∪) / OR(∨)"：
  • 展开成无限析取：\exists x \in \mathbb{Z}^+ P(x) = P(1)\lor P(2)\lor P(3)\dots


翻译

费马大定理

自然语言： 如果一个整数 n 大于 2， an+ bn= cn对任意正整数 a, b, c 都不成立 谓词逻辑： 对于任意正整数 a, b, c，要么 n ≤ 2，要么 n 不是整数，要么 an+ bn= cn 不成立 谓词逻辑语言:$$\forall\ a, b, c\in Z^+,\ (n≤2)\lor(n\notin Z)\lor(a^n+b^n≠c^n)$$


哥德巴赫猜想

自然语言： “每个正偶数都是两个质数之和”。 谓词逻辑： ”对于任意正整数，要么它不是偶数；要么存在两个整数质数，两者和为这个数“ 谓词逻辑语言：$$\forall x \in Z^+, (odd(x))\lor(\exists\ m,n \in Z, prime(m)\land prime(n)\land (m+n=x))$$


素数的定义

自然语言： 素数是所有大于 1 且没有除了 1 和自己以外的正因子的正数 谓词逻辑： 对于整数 p >1，对于任意整数 a 和 b，要么 a 是 1，要么 a 是 p，要么 a x b ≠ p 谓词逻辑语言：$$prime(p) \equiv (p>1)\land(p\in Z)\land(\forall\ a, b\in Z^+, (a=1)\lor(a=p)\lor(a\times b≠p)$$



量词语句的否定

不任意 ≡ 存在不： ¬(∀x), P(x) ≡ (∃x), ¬P(x) 不存在 ≡ 任意不： ¬(∃x), P(x) ≡ (∀x), ¬P(x) 证明(利用德摩根定律)：$$“不是对任意 x，都有 P(x)”\ ::=\ (¬(∀x),\ P(x))\ ≡\ ¬(\bigcap_{i=0}^{n} P_i)\ ≡\ \bigcup_{i=0}^{n}(¬P_i)\ ≡\ ((∃x),\ ¬P(x)) $$



多重量词与其否定

  • ∀, ∃ ¬≡ ∃, ∀ (对于任意人，都存在一个最爱的人 ≠ 存在一个人，爱所有人)
  • ∃, ∃ 以及 ∀, ∀ 都可以交换顺序
  • ¬(∀x, ∃y, P(x, y)) ≡ ∃x, ∀y, ¬P(x, y)


更多翻译

  • 不存在最大的正整数： → 对于任意正整数 x，都存在一个正整数 y 不比 x 小 $$∀x ∈ Z^+,\ ∃y ∈ Z^+,\ y ≥ x$$

  • 所有有理数都可以用分数表示： → 对于任意有理数 x，存在整数 p 和 q，使得 x = p/q $$∀x ∈ R,\ ∃ p,\ q ∈ Z,\ (q ≠ 0) ∧ ({p\over{q}} = x)$$

  • 每一个大于 1 的整数，都能表示为一组素数的乘积 → 对于任意整数 x 且 x 大于 1，存在一些素数之积为这个整数 x $$∀x \in \mathbb{Z}, \ x > 1,\ (∃p_1, p_2, \dots, p_n \in \mathbb{Z}^+, ; (\bigwedge_{i=1}^n prime(p_i)) \land (x = \prod_{i=1}^n p_i)))$$




LN3 Basic Prove Methods 基本证明法


  • 论证方法分为：direct proof(直接数学证明)、~ by contrapositive(逆否法)、~ by contradiction(反证法)、proof by cases(反例法) 以及 proof by induction(数学归纳法)。我们现在讨论前四种。

  • 在论证开始前，除了直接证明，需要声明 “We shall prove by ~"。

  • 对于逆否，写出逆否命题；对于反证，写出否定假设。

  • 论证结束写“Q.E.D."。


Proof by Contrapositive

  • 逆否命题：P → Q ≡ ¬Q → ¬P (“偶数能被 2 整除” 等价于 “不能被 2 整除就不是偶数”)
  • 对于需要声明双向蕴含关系(”当且仅当“)时，可以直接证明 P → Q 和 ¬P → ¬Q

Proof by Contradiction

  • 反证法：P → Q ≡ ¬P → FALSE (”偶数能被 2 整除“ 等价于 ”不是偶数也能被 2 整除“是荒谬的)
  • 或者 P NOT→ Q ≡ ¬P → TRUE

Proof by Cases

  • 只能用于探讨存在性的含变量命题的证伪
comments powered by Disqus