The Foundations: Logic and Proofs
基本结构: 集合, 函数,
序列, 求和, 矩阵
Copyright By PowCoder代写 加微信 powcoder
大连东软信息学院/大数据科学系
Section 2.4
序列是元素的有序列表
1, 2, 3, 5, 8
1, 3, 9, 27, 81, …….
序列贯穿于整个数学，计算机科学，以及许多其他学科，如从植物学到音乐。
我们将介绍序列及其求和中使用的一些术语。
序列 Sequence
定义: 序列是从一个整数集的子集 (通常是集合 {0, 1, 2, 3, 4, …..} 或者 {1, 2, 3, 4, ….} ) 到一个集合S的函数。
用记号 an 表示整数 n 的像。我们认为相当于f(n) ，其中 f 是从{0,1,2,…..} 到 S 的函数。 称 an 是序列的一个项。
例: 考虑序列 ，其中
定义: 几何级数是如下形式的序列:
其中初始项 a 和公比 r 都是实数。
令 a = 1 ， r = −1 。那么：
令a = 2 ， r = 5 。那么:
令 a = 6 ， r = 1/3 。那么:
定义: 算术级数是如下形式的序列:
其中初始项a 和公差 d 都是实数。
令a = −1 ， d = 4:
令a = 7 ， d = −3:
令a = 1 ， d = 2:
定义:字符串是有限集合中的有限字符序列。
字符或比特序列在计算机科学中很重要。
空字符串 用 λ 表示。
字符串 abcde 长度为 5 。
定义: 关于序列{an}的一个递推关系是一个等式，对所有满足 n ≥ n0 的整数n ， an 用序列中前面项, 即 a0, a1, …, an-1,中的一项或多项表示, 这里 n0是一个非负整数。
如果一个序列的项满足递推关系，则该序列就称为是递推关系的一个解。
递推关系生效，序列的初始条件定义了首项前的那些项。
例 1: 令 {an} 是满足递推关系的一个序列，an = an-1 + 3 , n = 1,2,3,4,…. ,并假定a0 = 2 。 a1 , a2 和 a3 是多少?
[a0 = 2是初始条件]
解: 从递推关系可以看出
a1 = a0 + 3 = 2 + 3 = 5
a2 = 5 + 3 = 8
a3 = 8 + 3 = 11
例 2: 令 {an}是满足递推关系的一个序列 an = an-1 – an-2 for n = 2,3,4,…. 并假定a0 = 3 ， a1 = 5 。 a2 和 a3是多少?
[这里初始条件是a0 = 3 ， a1 = 5 ]
解: 从递推关系可以看出
a2 = a1 – a0 = 5 – 3 = 2
a3 = a2 – a1 = 2 – 5 = –3
Fibonacci 序列
定义: Fibonacci 序列, f0 ,f1 ,f2,…, :
初始条件: f0 = 0, f1 = 1
递推关系: fn = fn-1 + fn-2
例: 找出斐波那契数 f2 ,f3 ,f4 , f5 和 f6 。
f2 = f1 + f0 = 1 + 0 = 1
f3 = f2 + f1 = 1 + 1 = 2
f4 = f3 + f2 = 2 + 1 = 3
f5 = f4 + f3 = 3 + 2 = 5
f6 = f5 + f4 = 5 + 3 = 8
找出满足递推关系的序列中第n 项的公式，称为求解递推关系。
这个公式被称为 闭公式。
已有很多方法可以求解递推关系，在 Chapter 8会深入的研究递推关系，将证明递推关系如何用于求解计数问题。
这里我们将以一种迭代法的例子说明如何求解递推关系。用归纳法可以证明猜想是正确的(Chapter 5)。
方法 1: 正向替换，从初始条件出发一直找到an
令 {an} 是满足递推关系的序列 an = an-1 + 3 ， n = 2,3,4,…. 并假定a1 = 2 。
a2 = 2 + 3
a3 = (2 + 3) + 3 = 2 + 3 ∙ 2
a4 = (2 + 2 ∙ 3) + 3 = 2 + 3 ∙ 3
an = an-1 + 3 = (2 + 3 ∙ (n – 2)) + 3 = 2 + 3(n – 1)
方法 2: 反向替换
令 {an} 是满足递推关系的序列 an = an-1 + 3 ， n = 2,3,4,….并假定 a1 = 2 。
an = an-1 + 3
= (an-2 + 3) + 3 = an-2 + 3 ∙ 2
= (an-3 + 3 )+ 3 ∙ 2 = an-3 + 3 ∙ 3
= a2 + 3(n – 2) = (a1 + 3) + 3(n – 2) = 2 + 3(n – 1)
例: 假设一个人在银行存了$10,000.00 ，年利率是11% 按年计复利。那么在30年后该账户上将有多少钱?
令 Pn 表示n 年后账户上的金额。 Pn 满足下列递推关系:
Pn = Pn-1 + 0.11Pn-1 = (1.11) Pn-1
初始条件 P0 = 10,000
Pn = Pn-1 + 0.11Pn-1 = (1.11) Pn-1 初始条件P0 = 10,000
P1 = (1.11)P0
P2 = (1.11)P1 = (1.11)2P0
P3 = (1.11)P2 = (1.11)3P0
Pn = (1.11)Pn-1 = (1.11)nP0 = (1.11)n 10,000
Pn = (1.11)n 10,000 (归纳证明)
P30 = (1.11)30 10,000 = $228,992.97
特殊的整数序列(opt)
给定序列的几个项，尝试确定序列。 猜想一个可能的公式、 递推关系或序列的某种规则。
是否有相同的值重复出现?
是否给前项加上某个常量或乘以特定量就能得出后项?
是否按某种方式组合前面若干项就可以得出后项?
是否在各项之间存在循环?
这些项与已知序列相符吗?
特殊的整数序列(opt)
例 1: 求具有下列前5项的序列公式: 1, ½, ¼, 1/8, 1/16
解: 可以看出分母都是2的幂次。 序列an = 1/2n 是一个可能的解。 几何级数a = 1 ， r = ½。
例 2: 考虑 1,3,5,7,9
解: 每一项可通过前一项加2 得到。 可能的公式an = 2n + 1，算术级数a =1 ， d = 2。
特殊的整数序列(opt)
例 3: 1, -1, 1, -1,1
解: 各项交替出现1 和 -1。一个可能的序列an = (−1)n 。几何计数 a = 1 ， r = −1。
序列猜想(optional)
例: 如果序列 {an}的前10 项是 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047，猜想序列的项an 。
解: 相邻项的比接近于 3. 所有猜想序列的各项是由一个与3n 有关的公式产生。 注意第 n 项比对应的3的幂次小 2 。故猜想 an = 3n − 2。
序列 的一些项
变量 j 称为求和下标，遍历所有整数，开始其下限m和结束其上限n。
序列 的一些项
求积符号(optional)
要计算Sn , 等式两边首先乘以r，然后得出求和公式进行如下变换：
变换求和下标 k = j + 1。
去除 k = n + 1 项，添加 k = 0 项。
用 S 代替求和公式
Later we will prove some of these by induction.
Proof in text
(requires calculus)
Geometric Series: We just proved this.
例子: 几何级数, 算术级数
例子: Fibonacci 序列
Section 2.5
定义: 集合A 和集合B 有相同的基数, 表示为
|A| = |B|,
当且仅当存在从集合A到集合B的一个一一对应 (i.e., 双射) 。
如果存在一个从A到B的一对一函数(i.e., 单射), 集合A 的基数小于或等于集合B 的基数，写作|A| ≤ |B|。
当 |A| ≤ |B| 且 A 和 B 有不同的基数, 我们就说集合 A 的基数小于集合 B 的基数，并写成 |A| < |B|。
定义: 一个集合或者是有限集，或者是与正整数集(Z+)具有相同的基数，就称这个集合是可数的。否则是不可数的。
实数集 R 是不可数的
如果一个无线集S是可数的，它的基是ℵ0 (这里ℵ 是 aleph, 希伯来语字母表的第一个字母). 写作|S| = ℵ0 ， S 得基“阿里夫零.”
证明一个集合是可数的
一个无限集是可数的，当且仅当 可以把集合中的元素排成序列(下标是正整数)。
原因是从正整数集合到集合S 的一一对应关系 f 可以用序列 a1,a2,…, an ,… 表示，其中 a1 = f(1), a2 = f(2),…, an = f(n),…
Hilbert’s 大饭店
大饭店( ) 有可数无限多个房间,每个房间都有客人。我们可以随时在这家旅馆接待一位新客人。这怎么可能?
解: 因为大饭店的房间是可数的, 我们可以列出 Room 1, Room 2, Room 3, ……. 当来了一位新的客人, 我们把 Room 1 的客人安排到 Room 2, Room 2 的客人安排到 Room 3, 更一般地， Room n 的客人安排到 Room n + 1, n 是正整数。 这样就把Room 1 腾出来可以安排新的客人 ，并且所有原先的客人也都有房间。
证明一个集合是可数的
例 1: 证明正整偶数 E 是可数集
解: 令 f(x) = 2x.
1 2 3 4 5 6 …..
2 4 6 8 10 12 ……
那么 f 是从N 到 E 的双射，因为 f 是一对一且映上的。 要证明一对一, 假设f(n) = f(m)， 那么 2n = 2m, 并且 n = m。要证明映上, 假设t 正的偶数，那么 t = 2k ，k 是正整数，且 f(k) = t。
证明一个集合是可数的
例 2: 证明整数集合Z 是可数的
0, 1, − 1, 2, − 2, 3, − 3 ,………..
或者定义一个双射 从N 到 Z:
当 n 是偶数: f(n) = n/2
当 n 是奇数: f(n) = −(n−1)/2
定义: 一个有理数可以表示为两个整数p 和 q 的比， q ≠ 0。
例 3: 证明正有理数是可数的
解: 正有理数是可数的，因为它们能以序列排列:
r1 , r2 , r3 ,…
先列出 p/q 满足 p + q = 2.
再列出 p/q 满足 p + q = 3
第一行列出分母q = 1.
1, ½, 2, 3, 1/3,1/4, 2/3, ….
例 3: 证明以有限的字符表 A生成的字符串是可数的无限集。
假定A中字符按字母顺序排列
解:证明字符串可以按某种顺序列出。首先列出
以字母顺序所有长度为0的字符串；
然后以字典顺序列出所有长度为1的字符串（如字典）；
以字典顺序列出所有长度为2的字符串；
意味着从 N 到 S 是双射，于是字符串是可数的无限集。
证明实数集合是不可数的。
解: 采用反证法证明
假设 R 是可数的，那么0 和 1 之间的实数所构成的子集也是可数的 (可数集合的任意子集都是可数的)。
0 和 1 之间的实数按某种顺序列出 r1 , r2 , r3 ,… .
设这些实数的十进制表示为
构造新的实数具有十进制展开式 其中
(1845-1918)
实数 r 不等于r1 , r2 , r3 ,... 中的任意一个。因为对于每个i， r 的十进制展开式与ri 的十进制展开式在小数点右边第i 位是不同的。由于存在不在0 和 1 之间的实数，所以, 假设可以列出所有介于0 和 1 之间的所有实数必定为假。所以0 和 1 之间的实数不能一一列出，因此0 和 1 之间的实数集合是不可数的。
任何含有不可数子集合的集合都是不可数的。
(1845-1918)
可计算的 (Optional)
定义: 一个函数称为是可计算的，如果存在某种编程语言写的计算机程序能计算该函数的值。否则是不可计算的。
Section 2.6
矩阵是有用的离散结构，可以在许多方面使用。 例如:
描述某些类型的函数称为线性变换。
表示图的顶点由边连接。
在后面的章节，我们可以使用矩阵用于建模:
基于矩阵模型的算法在后面章节将被提供。
在这里，我们涵盖了矩阵运算方面，为后面打好基础。
定义: 矩阵是矩形状的数组。m 行n 列的矩阵称为m n 矩阵。
行数和列数相等的矩阵叫方阵。
两个矩阵相等，如果它们有相同的行数和列数，并且对应位置上的对应项都相等。
令 m 和 n 是正整数，
矩阵A 的第i行是1 n， [ai1, ai2,…,ain]，第 j 列示 m 1:
A的第(i,j) 是元素 aij. 用A = [aij ] 表示矩阵。
定义: 令 A = [aij] ， B = [bij] 是m n 矩阵。 A 与 B的和写作A + B, 是m n 矩阵，且aij + bij 是第(i,j)元素。 换句话说, A + B = [aij + bij].
注意不同尺寸的矩阵不能做加法。
定义: 令 A 是 m k 矩阵，B 是 k n 矩阵。 A 和 B的乘积, 记作AB, 是m n 矩阵，其第(i,j )元素是A的第i 行与B的第 j 列对应元素的乘积之和。也就是, 如果 AB = [cij] ，那么 cij = ai1b1j + ai2b2j + … + akjb2j
两个矩阵相乘是没有定义的，当第一个矩阵的列数不等于第二个矩阵的恶行数时。
A = [aij] ， B = [bij]
定义: n 阶单位阵是 n n 矩阵， In = [ij], 其中如果 i = j， ij = 1 ； 如果 i≠j ，ij = 0 。
AIn = ImA = A
当 A 是 m n 矩阵
方阵的幂次，令 A 是 n n 矩阵, 有:
A0 = In Ar = AAA∙∙∙A
定义: 令 A = [aij] 是 m n 矩阵。A的转置，记作 AT ,是n m 矩阵，是通过交换 A的行和列所得。
如果 AT = [bij], 那么 bij = aji ， i =1,2,…,n ，j = 1,2, ...,m.
矩阵 的转置是
定义: 方阵 A 是对称的，如果 A = AT。A = [aij] 是对称的，如果aij = aji ， i 和 j 满足 1≤ i≤ n ， 1≤ j≤ n 。
方阵的行和列互换时，不改变。
定义: 所有元素非0 即 1 的矩阵叫0-1矩阵。
由0-1矩阵表示的离散结构上的算法是基于布尔运算定义的布尔运算，如 :
定义: 令 A = [aij] 和 B = [bij] 是m n 的0-1矩阵。
A 和 B 的并是0-1矩阵，满足第 (i,j )元素为 aij ∨ bij。A 和 B 并写作A ∨ B。
例: 写出下列0-1矩阵的并和交
定义: 令 A = [aij] 和 B = [bij] 是m n 的0-1矩阵。
A 和 B 的并是0-1矩阵，满足第 (i,j )元素为 aij ∨ bij。A 和 B 并写作A ∨ B。
A 和 B的交是0-1矩阵，满足第 (i,j)元素为 aij ∧ bij。 A和B的交写作A ∧ B。
例: 写出下列0-1矩阵的并和交
定义：令 A = [aij] 是 m k 的0-1 矩阵，B = [bij] 是 k n的0-1 矩阵。 A 和 B的布尔积, 写作A ⊙ B, 是mn 的0-1矩阵，满足第(i,j) 元素为
cij = (ai1 ∧ b1j)∨ (ai2 ∧ b2j) ∨ … ∨ (aik ∧ bkj).
定义: 令 A 是0-1方阵，r 是正整数。A 的r 次布尔幂是 r 个 A的布尔积, 写作 A[r] . 于是,
定义A[r] 是 In.
(这是良定义，因为矩阵的布尔积是可结合的。)
良定义(well defined)就是指无歧义的、不会导致矛盾的、符合其应满足的所有要求的定义。
An 是多少？n是整数。
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com