Name: Password: Sign in

[Lecture 6] 证明

在上一节中我们已经讨论了构建有效证明的推理规则,因而理论上根据假定为真的前提我们运用推理规则就可以推导出结论的真实性,即完成 形式化证明 。然而现实中这样做会导致我们的证明非常冗长,就像上节第 4 部分所讨论的那样;另一些时候有些步骤很难用形式化的方式给出。因而这一节我们使用的是 非形式化证明 ,许多步骤将会被省略,以此来突出证明的关键部分。

1 一些术语

  • 公理 :假设为真的命题;公理 用不要求定义的语句表述;它们不需要被证明
  • 定理 : 一个能表示为真的命题,可由 公理 与其他 定理 证明;但一般而言我们只把较为关键的真命题叫做定理
  • 引理 : 在证明中经常把不大重要的定理称作 引理,复杂证明可能需要一系列 引理 ,它们需要被一一单独证明
  • 推论 : 从定理直接建立的被证明的 定理
  • 猜想 : 被提出待被证明为真的 命题,通常建立在一些依据之上;得到证明后 猜想 变为 定理;当然 很多猜想 被证明是错误的
  • 显然(清楚的) : 这些词经常意味着证明步骤被省略并希望读者能够补上;这当然是出于避免证明冗长的考虑,然而很多时候我们无法保证读者能够补上缺失的部分,因而什么地方该省略是一个需要斟酌的问题= =

2 证明定理的方法

2.1 直接证明

从前提开始经过一连串推演最终终止于结论即 直接证明

例如要证明 pq ,首先假设 p 为真,接下来运用定义、公理、定理或推理规则推出 q 为真,因而 pq 被证明为真。

2.2 间接证明

很多时候考虑从前提出发终止于结论的做法行不通,例如要证明下面这个命题:

如果 n=ab,其中 ab 为正整数,那么 an 或者 bn

直接从 n=ab 这样的前提很难经过一连串推演得到 「an 或者 bn」的结论。这需要我们通过其他的方式来构造证明。

2.2.1 反证法

由于 pq¬q¬p 等价,因而我们可以构造 ¬q¬p 两个命题,假设 ¬q 为真,经过推演得到 ¬p 为真,那么 ¬q¬p 为真,pq 被证明为真,这种方法即为 反证法

还是考虑上面这个例子,假设

(an)(bn)

为假,即

(a>n)(b>n)

为真,进而有 ab>n,即 abn 为真,所以

¬[(an)(bn)]¬(ab=n)

为真,因而

(ab=n)(an)(bn)

为真,原命题得证

又如要证明

n2 为偶数,那么 n 为偶数

假设 「n 为偶数」为假,即 n 为奇数,存在整数 kn=2k+1,则

n2=2(2k2+2k)+1

即 「n2 为偶数」为假,由反证法原命题得证

2.2.2 空证明与平凡证明

  • 空证明p 为假时 pq 为真总是成立,因而 pq 自动得到证明
  • 平凡证明q 为真时 pq 为真总是成立,因而 pq 自动得到证明

2.2.3 归谬法

假设我们想证明 p 为真,可以利用矛盾式 q 使得 ¬pq 为真,从而 ¬qp 为真,由于矛盾式本身恒为假的性质所以 p 为真得证。

所以接下来的事情就是想办法构造矛盾式,注意到 r¬r 是一个矛盾式,当我们得到

¬p(r¬r)

为真时,p 自动为真,这种方法即为 归谬法 ,归谬法也是间接证明的一种。

例如要证明命题 p

2 是无理数

  • 由归谬法,假定 p 为假,即 2 不是无理数,存在整数 aba/b 不可约,使得 2=a/b,那么 2b2=a2
  • 由 2.2.1 中已证明 「n2 为偶数,那么 n 为偶数」,所以 a 为偶数,假设 a=2k,那么 b2=2k2,所以 b 为偶数,也即 a/b 可约
  • 所以有 ¬2 是无理数 ((a/b 可约 )(a/b 不可约 ))

所以 2 是无理数 得证

归谬法可用于条件语句中,方法与上面关于归谬法的说明类似,只需将 p 替换为 pq (等价于 ¬pq),那么只要证明

(p¬q)F

即可。换句话说先否定结果 q,然后推出矛盾式,则 pq 得证。

3 等价性证明

要证明 pq 等价,即

pq

为真,利用:

(pq)[(pq)(qp)]

即要证明 pqqp 同时为真。

当我们说一系列命题 p1p2pn 等价,即

p1p2...pn

为真,利用

[p1p2...pn][(p1p2)(p2p3)...(pnp1)]

即要证明 p1p2p2p3pnp1 同时为真。

Copyright (c) 2014-2016 Kyles Light.
Powered by Tornado.
鄂 ICP 备 15003296 号