The Foundations: Logic and Proofs
基本结构: 集合, 函数,
序列, 求和, 矩阵
Copyright By PowCoder代写 加微信 powcoder
大连东软信息学院/大数据科学系
Section 2.1
集合是基本的离散结构之一
集合论是一种要的数学分支
许多不同的公理系统已经被用来发展集合论。
在这里，我们不关心一组正式的公理集理论。这里，我们使用的是朴素集合论。
集合是对象的一个无序的聚集。
集合中的对象称为元素, 或成员。集合包含元素。
注意a ∈ A 表示 a 是集合A中的一个元素。
如果 a 不是集合A中的元素，写作 a ∉ A
通常用大写字母表示集合，小写字母表示集合中的元素
描述一个集合: 花名册方法
S = {a,b,c,d }
S = {a,b,c,d} = {b,c,a,d}
每个不同的对象是一个成员; 列出多次并不改变集合。
S = {a,b,c,d} = {a,b,c,b,c,d}
省略号 (…) 常用来描述没有列出所有的成员时。
S = {a,b,c,d, ……,z }
花名册方法(列举法)
英语字母表中所有元音的集合:
V = {a,e,i,o,u}
整数，小于10的正奇数的集合:
O = {1,3,5,7,9}
小于100的正整数的集合:
S = {1,2,3,……..,99}
S = {…., -3,-2,-1}
N = 自然数 = {0,1,2,3….}
Z = 整数 = {…,-3,-2,-1,0,1,2,3,…}
Z⁺ = 正整数 = {1,2,3,…..}
描述集合中的元素必须满足某种性质:
S = {x | x 是小于 100的正整数}
O = {x | x是小于10的正奇数}
T = {x ∈ Z⁺ | x 是奇数，且x < 10}
正有理数: Q+ = {x ∈ R | x = p/q, p和q为正整数}
使用谓词: S = {x | P(x)}
例: S = {x | Prime(x)}
[a,b] = {x | a ≤ x ≤ b}
[a,b) = {x | a ≤ x < b}
(a,b] = {x | a < x ≤ b}
(a,b) = {x | a < x < b}
全集 U 是包含当前正在考虑的一切的集合。
空集是不包含任何元素的集合。
用符号 ∅, 或者 { } 表示。
John Venn (1834-1923)
Cambridge, UK
设 S 是所有集合的集合它们不是自己的成员。一个悖论的结果，试图回答的问题“S是它自己的成员吗?”
亨利为所有不给自己刮胡子的人刮胡子。一个悖论的结果，试图回答“亨利为自己刮胡子吗？”
(1872-1970)
Cambridge, UK
Nobel Prize Winner
集合可以是一个集合的元素。
{{1,2,3},a, {b,c}}
空集与包含空集的集合不同
∅ ≠ { ∅ }
对下面的每个集合，判断2是否为它的元素。
{x∈R|x是大于1的整数}
{x∈R|x是一个整数的平方}
{{2},{{2}}}
{{2},{2,{2}}}
定义: 两个集合相等当且仅当它们有相同的元素。
如果A 和 B 是集合, 那么 A 和 B 相等当且仅当
{1,3,5} = {3, 5, 1}
{1,5,5,5,3,3,1} = {1,3,5}
定义: 集合A 是B的子集, 当且仅当A的每个元素也是B的元素。
A ⊆ B 当且仅当量化式 为真。
例1：A = {b,c,d}，B = {a,b,c,d}
例2：A = {a,b,c,d}，B = {a,b,c,d}
定义: 集合A 是B的子集, 当且仅当A的每个元素也是B的元素。
A ⊆ B 当且仅当量化式 为真。
对于任意集合S， ∅ ⊆ S，因为 a ∈ ∅ 永假。
对于任意集合S， S ⊆ S, 因为 a ∈ S → a ∈ S永真。
证明一个集合是否是另一个集合的子集
证明 A 是B的子集 ：要证明 A ⊆ B，需要证明 x 属于 A, 那么 x 也属于B。
证明A 不是B的子集: 要证明 A ⊈ B, 需要找到一个 x ∈ A 但 x ∉ B。
两个集合A 和 B 是相等的, 表示为 A = B， 当且仅当
也就是 A = B iff
相当于 A ⊆ B 并且 B ⊆ A
定义: 如果A ⊆ B, 但是 A ≠B，那么A 是 B的真子集，表示为 A ⊂ B，即
判断下列语句是真是假。
定义: 如果S中恰好有n个完全不同的元素，这里 n 是非负整数, 我们就说S 是有限集，否则是无限集。
定义: 有限集A 的基数, 记作 |A|, 是A 中不同元素的个数。
|{1,2,3}| = 3
下列各集合的基数是什么？
{a,{a},{a,{a}}}
{，{}，{，{}}}
定义: 集合A的所有子集构成的集合, 记作 , 称为A的幂集。
例: A = {a,b}
(A) = {ø, {a},{b},{a,b}}
如果集合有n 个元素, 那么它的幂集的基数为
求出下列各集合的幂集
下列集合各有多少个元素？
有序 n-元组 (a1,a2,…..,an) 是一个有序集合 ，a1 是第一个元素，a2 是第二个元素，……， an 是最后一个元素。
2-元组也叫有序对。
两个有序n-元组 是相等的，当且仅当它们对应的元素相等。
有序对(a,b) 和 (c,d) 相等，当且仅当 a = c ， b = d。
定义: 两个集合A 和 B 的笛卡尔积, 表示为 A × B，是 有序对 (a,b) 的集合，其中 a ∈ A 且b ∈ B 。
例: A = {a,b} B = {1,2,3}
A × B = {(a,1),(a,2),(a,3), (b,1),(b,2),(b,3)}
定义: 笛卡尔积A × B 的子集R 称为集合 A 到集合 B的一个关系。
René Descartes (1596-1650)
定义: 集合A1,A2,……,An, 的笛卡尔积表示为A1 × A2 × …… × An , 是有序对n-元组 (a1,a2,……,an) 的集合，其中ai 属于Ai ， i = 1, … n。
例: A × B × C ，其中 A = {0,1}, B = {1,2} 和 C = {0,1,2}
答: A × B × C = {(0,1,0), (0,1,1), (0,1,2),(0,2,0), (0,2,1), (0,2,2),(1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2)}
令A={a,b,c,d}, B={y,z}，求：
令A={a,b,c}, B={x,y}, C={0,1}。求：
笛卡尔积A×B×C是什么？其中A是所有航线的集合，B和C是所有城市的集合。
试着解释A×B×C和(A×B)×C为什么不同？
A={1,2,a,b}
如果A有m个元素，B有n个元素，则A×B有多少个不同的元素？
如果A有m个元素，B有n个元素，C有p个元素，则A×B×C有多少个不同的元素？
如果A有m个元素且n是一个正整数，则An有多少个不同的元素？
给定谓词 P 和论域 D, 定义 P 的真值集 为 D 中使P(x) 为真的元素x组成的集合。 P(x)的真值集记作
例: 论域是整数，P(x) 是“|x| = 1”，那么 P(x)的真值集是{-1,1}
数学中一些重要的集合
Section 2.2
定义： A 和 B 是集合。 集合A 和集合 B 的并集, 表示为 A ∪ B, 是一个集合:
例如: {1,2,3} ∪ {3, 4, 5} ?
答: {1,2,3,4,5}
A ∪ B 的文氏图
交集Intersection
定义: 集合A 和 B 的交集, 表示为 A ∩ B, 是
注意，如果交集是空集, 那么A 和 B 被称为是不相交。
例如: {1,2,3} ∩ {3,4,5} ?
例如： {1,2,3} ∩ {4,5,6} ?
差集Difference
定义: A 和 B是集合。A 和B 的差集, 表示为 A – B，它包含属于A 而不属于B 的元素。A 和 B 的差集也被称为B相对于A的补集。
A – B = {x | x ∈ A x ∉ B} = A ∩B
A − B 的文氏图
补集Complement
定义: 如果A 是集合, 那么A的 补集 (相对于U ), 表示为Ā ，是集合 U - A
Ā = {x ∈ U | x ∉ A}
(A的补集有时候表示为 Ac )
例: 如果 U 是小于100的正整数, {x | x > 70} 的补集是什么？
答: {x | x ≤ 70}
容斥原理 |A ∪ B| = |A| + | B| − |A ∩ B|
例: A 是打篮球的学生集合，B 打排球的学生集合。 计算打篮球或者打排球的学生人数？
A, B, A ∩ B, A ∪ B的文氏图
例: U = {0,1,2,3,4,5,6,7,8,9,10} A = {1,2,3,4,5}, B ={4,5,6,7,8}
答: {1,2,3,4,5,6,7,8}
答: {0,6,7,8,9,10}
答: {0,1,2,3,9,10}
答: {1,2,3}
答: {6,7,8}
对称差(optional)
定义: 集合A 和 B 的对称差，表示为
U = {0,1,2,3,4,5,6,7,8,9,10}
A = {1,2,3,4,5} B ={4,5,6,7,8} :
答: {1,2,3,6,7,8}
令A={0,2,4,6,8,10},B={0,1,2,3,4,5,6},C={4,5,6,7,8,9,10}
如果集合A与B具有下列性质，你能就A和B说些什么？
A ∩ B = B ∩ A
A – B = B – A
练习（Optional）
如果集合A、B、C满足下列条件，你能断定A=B吗？
A ∪ C = B ∪ C
A ∩ C = B ∩ C
A ∪ C = B ∪ C 并且 A ∩ C = B ∩ C
证明集合相等的方法:
每一个是另一个的子集。
使用集合构造器符号和命题逻辑。
1) 和
逻辑等价式的德摩根律
不属于符号的含义，交集的定义
逻辑等价式的德摩根律
集合构造器符号:第二德摩根律
逻辑等价式的德摩根律
证明集合相等的方法:
每一个是另一个的子集。
使用集合构造器符号和命题逻辑。
成员表: 验证在相同集合组合中元素同属于恒等式两边的集合。 用 1 表示元素属于一个是集合，否则为0。
A B C B∩C A∪(B∩C) A∪B A∪C (A∪B)∩(A∪C)
1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1
0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0
A1, A2 ,…, An 是集合。定义:
i = 1,2,…,n。
A∪(B-A)=A ∪ B
(B-A) ∪(C-A)=(B ∪ C)-A
(A-C)∩(C-B)=
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com