离散数学(1) 证明

命题#

可判断真假的陈述.

比如1+2=3,2+3=6.

“你叫什么名字?”和”你好.”不是命题.

“这句话是假的.”也不是命题.

命题的复合#

可以使用与,或,非

非(not)#

$\neg p$ 为真当且仅当 $p$ 为真

与(and)#

$p\land q$ 为真当且仅当 $p,q$ 均为真.

或(or)#

$p\lor q$ 为真当且仅当 $p,q$ 中至少一个为真.

也可以说, $q\lor q$ 为假当且仅当 $p,q$ 均为假.

蕴含(implies)#

$p\implies q$ 为真当且仅当:

$p$ 为假,或 $q$ 为真.

等价于 $\lnot p \lor q$ .

“ $p$ 蕴含 $q$ ”和”如果 $p$ ,那么 $q$ ”陈述等价.

等价(iff)#

$p\iff q$ 当且仅当p与q同真假.

“p等价于q”也可说,“p当且仅当q”.

异或(xor)#

$p\oplus q$ 当且仅当p与q真假值不同.

显然 $p\oplus q$

等价于 $\lnot (p\iff q)$

等价于 $(\lnot p \land q)\lor (p\land \lnot q)$

运算律#

最重要的是德摩根律和分配律.

德摩根律:
- $\lnot (p\land q)$ 等价于 $\lnot p \lor \lnot q$
- $\lnot (p\lor q)$ 等价于 $\lnot p \land \lnot q$
分配律:
- $a\land (p\lor q)$ 等价于 $(a\land p) \lor (a\land q)$ .
- $a\lor (p\land q)$ 等价于 $(a\lor p) \land (a\lor q)$ .

谓词(predicate)#

相当于从某集合到布尔变量的函数 $p(n)或者p(x)$ 真假取决于给出的自变量取值.

比如" $p(n):n^2+n+41是质数$ "是一个谓词.真假取决于n的取值.当 $n\leq 39$ 时 $p(n)$ 为真.

量词(quantifier)#

全称量词(universal quantifier)#

$\forall$ (forall),表示”对所有的”,“对于任意”.

特称量词/存在量词(existential quantifier)#

$\exist$ (exist),表示”存在""至少一个""存在某个”.

量词作为对谓词的限制,可以与谓词组成命题.

一个命题可以有多个量词,而往往只有一个谓词(当然,这个谓词可以是由多个谓词通过逻辑运算复合而成的).

举个例子,

\forall (k\in Z) \land (2k \ge 4),\exist 质数p,\exist质数q, 2k=p+q.

即为一个命题(哥德巴赫猜想),这个命题有3个量词一个谓词,其中一个量词由两个命题复合而成.

量词的顺序很重要.上面这个命题和

\exist 质数p,\exist质数q, \forall (k\in Z) \land (2k \ge 4), 2k=p+q.

不等价.前者说的是所有的偶数都由某组质数(可能不同)p,q相加得到. 后者说的是所有的偶数都由相同的一组质数p,q相加得到,显然为假.

论域(domain of discourse)#

研究某领域的问题时默认的讨论范围,可以省略. 比如说在讨论数论问题时往往可以默认讨论范围为自然数或整数. $\exist p\in Z$ 可以省略成 $\exist p$ .

复杂命题的否定#

改变量词,否定谓词.

\forall (k\in Z) \land (2k \ge 4),\exist 质数p,\exist质数q, 2k=p+q.

的否定为

\exist (k\in Z) \land (2k \ge 4),\forall 质数p,\forall 质数q, 2k\neq p+q.

有效性(validity)#

若一个命题始终为真,则称其为有效的. 比如

p\lor \lnot p

无论p为真或假,该命题都为真. 上述命题也叫做重言式. 有效性的概念也可推广至谓词.若一个谓词p(n)在n的任何可能取值下都为真,则称谓词p(n)有效(valid).

可满足性(satisfiability)#

若一个命题在某取值下为真,则称其为可满足的.

p \land \lnot q

在p为真,q为假时命题为真,故该命题是可满足的(satisfiable). 可满足性的概念也可推广至谓词.若一个谓词p(n)在n的某一取值下为真,则称谓词p(n)是可满足的.

判断一个命题/谓词的可满足性的过程称为SAT. SAT是一个重要课题,当变量数增大时,往往需要指数级别的复杂度.虽然对于部分特殊的SAT问题有多项式复杂度的解,但目前尚不清楚是否对于所有SAT问题都能或不能得到多项式复杂度的解(P/NP问题).

证明方法#

公理#

在某个科学理论中,我们会假定某些命题为真,称为公理,然后再通过公理来证明其他定理. 比如说在现代数学中很重要的ZFC公理,平面集合中的欧几里得公理体系等.没有公理,科学理论本身将没有意义.

一个良好的公理体系的性质:

相容性(一致性):在同一个公理体系中推导出来的所有命题必须同真或同假(比如说有 $p_1, p_2,...$ 这些公理,如果由 $p_1,p_2$ 可以证明某个命题q为真,由 $p_3, p_4$ 可以证明q为假,那么这个公理体系就是不满足一致性的)
独立性:公理系统中的每一条公理都不能通过其他公理推导出来,确保公理之间没有冗余
完备性:公理体系能够判定论域内的所有命题

其中相容性是必要的(否则该公理体系将没有意义),独立性是重要的(但不是必须的),而完备性对于很多论域来说甚至是无法做到的(见哥德尔不完备定理)

逻辑证明#

\\p, \\p\implies q. \\------- \\q

也叫三段论推理. $p$ 为大前提, $p\implies q$ 为小前提.

NOTE
一些等价形式
$\\p\implies q, \\q\implies r. \\------- \\p\implies r.$ $\\p\implies q, \\\lnot q \\------- \\\lnot p.$ $\\\lnot p\implies \lnot q, \\------- \\q\implies p.$
(即原命题等价于其逆否命题)

分类讨论(proof by cases)#

这个很简单.

例
一个6人的团体中,要么包含一个3人均互相认识的团体,要么包含一个3人互相均不认识的团体.

证明
先研究6人中的某人x,与剩下5个人的认识情况只能是下列两者中的一个:

另外5人中至少3人认识x

另外5人中至少3人不认识x

研究第一种情况,即另外5人中至少3人认识x,研究其中3人:

3人间至少有一对a,b互相认识,这时a,b,x构成均互相认识的团体.

3人a, b, c间均不互相认识,这时a, b, c构成互相均不认识的团体

研究第二种情况,即另外5人中至少3人不认识x,考虑其中3人:

3人间至少有一对a,b互相不认识,这时a,b,x构成互相均不认识的团体.

3人a, b, c间均互相认识,这时a, b, c构成互相均认识的团体.

讨论完所有情况发现所有情况都要么包含一个3人均互相认识的团体,要么包含一个3人互相均不认识的团体.原命题成立.Q.E.D.

假定p为真#

这个没什么好说的,假定p为真,推出q则证明完毕.

证明逆否命题#

假定q为假,推出p为假则其逆否命题为真.

证明等价#

互相推导#

屋檐了

建立等价推导链#

从p推出q的过程中如果每一句均可逆(均为等价过程),则p与最后的结论也等价.

反证法#

本质:观察 $\lnot q \implies r$ 的真值表时发现 $r$ 为假时 $\lnot q$ 也一定为假,所以说只要能从 $\lnot q$ 推出任何假命题(自我矛盾的命题),即可证明q为真.

集合(set)#

将一些元素放在一起组成的群体.满足:

无序性
确定性:任何东西,要么在这个集合里,要么不在这个集合里.
互异性:集合里的元素不重复. 高中都学过,这里不赘述

集合的基数\势(Cardinality)#

集合的元素个数,通常用 $\operatorname{card}(A)$ 或者 $|A|$ 表示.

幂集(the power set)#

集合的所有子集组成的集合. 集合 $A$ 的幂集记作 $2^{A}$ 或 $P(A)$ ,容易注意到 $|P(A)|=|2^{A}|=2^{|A|}$

序列(sequence)#

某些元素有序排列组成的群体,可重复,有序. $a,b,c$ 组成的序列记作 $(a, b, c)$ 用 $\lambda$ 表示空序列.

笛卡尔积/叉积(cross product)#

假如 $A=\set{a,b},B=\set{c,d}$ 那么 $A\times B=\set{(a,c),(a,d),(b,c),(b,d)}$ .

集合的描述#

如 $\set{n \in N | n \space is \space a\space prime\space and\space n = 4k +1\space for\space some\space integer\space k}$

罗素悖论#

对于任意一个集合A，A要么是自身的元素，即A∈A；A要么不是自身的元素，即A∉A。根据康托尔集合论的概括原则，可将所有不是自身元素的集合构成一个集合S1，即S1={x∉x}

ZFC公理体系
以下为ZF公理,分别是ZF1到ZF9,注意ZF公理中唯一的对象是集合,集合的元素也是集合.

外延公理:一个集合完全由元素决定,若两个集合含有相同的元素,则两个集合相等.

空集合存在公理: 存在空集,即没有元素的集合.

无序对公理:对于集合 $A$ , $B$ ,存在某个集合 $W$ 使得 $W$ 仅有 $A,B$ 作为其元素.

并集公理:任给一集合W，我们可以把W的元素的元素汇集到一起，组成一个新集合.

幂集公理:对于任意集合 $W$ , $P(W)$ 存在,且也是一个集合.

无穷公理:存在一个集合 $W$ ,它有无穷多元素.

分离公理:对于任意集合 $W$ 和对 $W$ 元素有定义的谓词 $p(x)$ , 存在集合 $\set {x|p(x)}$ .

替换公理:对于函数 $F(x)$ ,若其定义域被限定在集合 $T$ 中,则存在某集合 $S$ ,使得 $F(x)$ 的值域可被限定在 $S$ 中.

正则公理:任何集合的元素都具有最小性质.其传递闭包上不存在无穷降链.比如,不允许出现X属于X的情况.

以下为选择公理(AC).ZF公理加上选择公理就成为ZFC公理.

选择公理:集合族上的任意笛卡尔积非空.

(一般认为ZF公理中可以不包含ZF2,ZF2可由其他公理导出)

归纳法(induction)#

良序原理(the well order principle)#

自然数集 $N$ 的任一非空子集中必然有最小元素. 这可以推导出:任何有理数的分数形式 $\frac {p}{q}$ 必有最简形式.

数学归纳法证明#

比如说,要证明 $\forall n\in N, p(n)$ ,有如下步骤:

证明 $p(0)$
证明 $\forall n\in N, p(n) \implies p(n+1)$

错误的数学归纳法证明#

此处证明”世界上的所有马拥有同一颜色”.

证明

定义 $p(n)::=$ ”任意n只马拥有同一颜色”

显然 $n=1$ 时,1只马本身拥有同一颜色,即 $p(1)$ 成立.

对于任意n,若 $p(n)$ 成立,那么马 $H_1, H_2, ... , H_n$ 这n只马拥有同一颜色, 即 $H_1, H_2, ... , H_n$ 的颜色= $H_2, ... , H_n$ 的颜色.

考虑 $H_2, ... , H_n, H_{n+1}$ 这n只马也拥有同一颜色, 则 $H_1, H_2, ... , H_n, H_{n+1}$ 的颜色= $H_2, ... , H_n$ 的颜色.

即H_1, H_2, … , H_n, H_{n+1}拥有同一颜色.

综上我们证明了任意多只马拥有同一颜色.

这个证明的问题在于 $p(1)$ 不能推出 $p(2)$ ,因为此时 $H_2, ... , H_n$ 为空.

不变量#

见视频6.042J(3),从14:23到56:15.

强归纳法#

比如说,要证明 $\forall n\in N, p(n)$ ,有如下步骤:

证明 $p(0)$
证明 $\forall n\in N, p(1)\land p(2)\land ...\land p(n) \implies p(n+1)$

示例见视频6.042J(3),从1:02:44到最后

猜出S(n)的通项是很关键的.

归纳结构(structural induction)#

递归数据类型#

一个递归数据类型应当包含:

一个不由递归定义的基本情况.
递归定义的其他情况.

例
比如,我们可以定义一个类型”括号字符串”,仅由]和[组成:

空串 $\lambda$ 是一个”括号字符串”

如果s和t是”括号字符串”,那么[s]t是一个”括号字符串”

同样地,可以定义一个”算术表达式”:

变量x是一个表达式; 对于任何自然数a,其阿拉伯数字表示是一个表达式.

若e,f是表达式,则(e+f)是表达式;(e*f)是表达式;-(e)是表达式.

递归数据类型上的归纳证明#

比如要证明对于某个递归数据类型 $A$ , $\forall a\in A$ , $p(x)$ 为真:

证明基础情况下p(x)为真
$x$ 的组成元素为 $a, b, ...$ ,假定 $p(a), p(b), ...$ 为真,证明 $p(x)$ 为真.

递归函数#

一个递归函数应当包含:

基础情况
能够最终归结于基础情况的递归式这里不再赘述.

这门课中的数论内容比较简单,我会单独开一章来学习初等数论的相关知识.