# 集合与逻辑

[[MCS/day2/00 学习指南|day2 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day2/阅读核验与疑问|阅读核验与疑问]]

> 来源：[[MCS/day2集合与逻辑|day2集合与逻辑]]。用途：主线。原有推导、追问与解答保留；阅读时请结合本日核验说明。

## 为什么学习集合与逻辑

集合

数据库的 查询

AND:∩ 交集 
OR：∪ 并集
NOT: $\complement$ 补集 取相反

python 列表元素是字典的查询

逻辑电路 布尔逻辑 与或非

AI 推理、知识图谱、规则引擎

## 集合论与布尔代数的背景

康托尔

发明集合论，用集合研究无穷
有些无穷比另一些无穷更大
即，实数的无穷比自然数的无穷更大

康托尔三分集

布尔：把逻辑变成了代数，用 0 和 1 表示真假，创造了布尔代数

四则运算表示 AND、OR、NOT?

AND-乘法
OR—加法

香农发现布尔正好可以用来设计数字电路

## 德摩根定律

不是（A 且 B）等于（不是 A）或（不是 B）：$\overline{A \cap B} = \overline{A} \cup \overline{B}$
不是（A 或 B）等于（不是 A）且（不是 B）：$\overline{A \cup B} = \overline{A} \cap \overline{B}$

## 集合的源头：分类


1. **集合的建立**：把一些对象看成一个整体。
    - **列举法**：{1, 2, 3}
    
	- **描述法**：{x | x 满足条件 P}
2. **元素与属于关系**：对象要么属于集合，要么不属于。
    
3. **集合的生成**：由元素组成集合，或由已有集合通过运算生成新集合。

    
	- **由已有集合生成新集合**：
    
    - 并集：A ∪ B
        
    - 交集：A ∩ B
        
    - 补集：Aᶜ
        
    - 幂集：P(A)
        
    - 子集：A ⊆ B



 集合论的核心：分类 、属于、运算

## 逻辑的源头：判断真假
命题：

条件判断

蕴含、或、且

| P   | Q   | P 且 Q | P 或 Q | 并非(P 且 Q) | 非 P | 非 Q | (非 P)或(非 Q) | P → Q | P  $\Leftrightarrow$ Q |
| --- | --- | ----- | ----- | --------- | --- | --- | ----------- | ----- | ---------------------- |
| 真   | 真   | 真     | 真     | 假         | 假   | 假   | 假           | 真     | 真                      |
| 真   | 假   | 假     | 真     | 真         | 假   | 真   | 真           | 假     | 假                      |
| 假   | 真   | 假     | 真     | 真         | 真   | 假   | 真           | 真     | 假                      |
| 假   | 假   | 假     | 假     | 真         | 真   | 真   | 真           | 真     | 真                      |


## 罗素悖论

罗素悖论：所有不包含自身的集合组成的集合，是否包含自身？
理发师只给“不自己刮胡子的人”刮胡子。
问：理发师给不给自己刮胡子？
定义集合 R：
R = { x | x 是不包含自身的集合 }
也就是：
R = { x | x ∉ x }
然后问：
R ∈ R 是否成立？


 集合经过公理化，仍然是现代数学的基础


ZF:zermelo；Fraenkel
加个选择公理
ZFC 公理理论

逻辑语言
布尔代数
哥德尔证明了希尔伯特 ，哥德尔不完备性
图灵利用逻辑设计了图灵机

属于
不属于
子集
真子集
空集
幂集

并集、交集、补集、差集、对称差

真值表与韦恩图