离散数学笔记

第二篇 集合论

第三章 集合与关系

集合的概念与表示法

外延性原理

两个集合是相等的，当且仅当他们有相同的成员。

定义3-1.1

设 $A$ , $B$ 是任意两个集合，假如 $A$ 的每一个元素是 $B$ 的成员, 则称 $A$ 为 $B$ 的子集, 或 $A$ 包含在 $B$ 内, 或 $B$ 包含 $A$. 记作 $A\subseteq B$, 或 $B \supseteq A$, 即有

$$A\subseteq B \Leftrightarrow \forall x(x\in A \rightarrow x\in B)$$

联结词的全功能集

定义：设S是一个联结词集合，如果任何 $n(n\geq 1)$

蕴含关系的证明

这里的蕴含是：$\Rightarrow$

• 前真证明后真
• 后假证明前假

基本蕴含关系

1. $A\land B\Rightarrow A$
2. $A\Rightarrow A\lor B$
3. $\neg A \Rightarrow A \to B$
4. $B \Rightarrow A \to B$
5. $\neg (A \to B)\Rightarrow A$
6. $\neg (A \to B)\Rightarrow \neg B$
7. $A\land (A\to B)\Rightarrow B$
8. $(A\to B)\land (B\to C)\Rightarrow A\to C$
9. $(A\lor B)\land (A\to C)\land (B\to C)\Rightarrow C$
10. $(A\to B)\land (D\to C)\Rightarrow (A\land D)\to (B\land C)$
11. $(A\leftrightarrow B)\land (B\leftrightarrow C)\Rightarrow A\leftrightarrow C$

1.自由变元不改名字