author: o-jules

Description:

這是關於離散數學的相關筆記，本篇介紹命題和複合命題

基本概念

集合與元素

集合與元素：集合是元素的全體。

標記法

集合通常使用大寫字母表示，元素通常使用小寫字母表示。

因此術語“$p$是$A$的元素”或等價於“$p$屬於$A$”記作：\(p \in A\)

外延公理

兩個集合$A$和$B$相等當且僅當其元素相同。

如果集合$A$​​與$B$​​相等，則記作 $A = B$​​，否則 $A \neq B$​​。

集合的表示

集合有兩種基本素方法，一是枚舉元素，二是描述元素特征性質。

如：

• $V = {a, e, i, o, u}$, 或

• $V = {x: x是英文字母，x是元音字母}$

• $E = {x: x > 0, x mod 2 = 0}$​​​ 或$E = {2, 4, 6, 8, 10, …}$​​

常用的集合及其表示

抽象原則

給定集合$U$和性質$P$，則存在集合$A$恰好包含$U$中具有性質$P$的那些元素。

全集與空集

全集

記號為$U$。

空集

沒有元素的集合；又稱“零集”，記號為 $\emptyset$，或者 ${}$。

空集的特性：

• $∀A: A ⊆ ∅ ⇒ A = ∅$
• $P(∅) = {∅}$
• $card(∅) = 0$
• $∀A: ∅ ⊆ A$
• $∀A: A ∪ ∅ = ∅$
• $∀A: A ∩ ∅ = ∅$
• $∀A: A × ∅ = ∅$

子集

如果集合$A$的每個元素都是集合$B$的元素，則稱$A$為$B$的一個子集。也稱$A$包含於$B$或者$B$包含$A$。記作：

$A ⊆ B$ 或 $B ⊇ A$

或者A不是B的子集，即A至少有一個元素不屬於B，則記作 \(A \nsubseteq B\) 或者 \(B \nsupseteq A\)。

定理1.1

• 對於任意集合$A$, $∅ <= A <= U$
• 對於任意集合$A$，$A <= A$
• 如果$A <= B$，且 $B<= C$，則 $A<= C$
• $A = B$ 當且僅當 $A <= B$ 且 $B <= A$