离散数学(5) 证明

大家不要看逻辑学这个名字很高大上,我们通过前面几节课已经讲完了离散数学中需要的逻辑知识。逻辑学对计算机科学来说太重要了:下到机器的电路逻辑上到程序语言里面的逻辑,学习计算机你总是不能饶过逻辑这一知识点。我建议同学们完成我课程中的练习的同时也可以在课本中找课后练习查漏补缺,为学习后面的知识打下基础。

这节课我们进入另一个单元–证明。

先上定义

A proof is a valid argument that establishes the truth of a theorem.(Textbook)

英语实在不行可以手动维基百科找中文定义,但是可能解释有出入。我手动翻译一下

证明是一段检验定理真假的有效论证

理解这段话,我们先区分一下一些术语

定理(Theorem):可以被证明为真的命题

公理(Axioms):被公认为真的命题

论证(argument):证明的过程

著名的哲学家亚里士多德说过:一个命题必然从另外两个命题中推导出。

比如说:

如果所有人(M)都是必死的(P),(大前提)

并且所有希腊人(S)都是人(M),(小前提)

那么所有希腊人(S)都是必死的(P)。(结论)

这样一个三段的陈述叫三段论。这三段话就组成了一个证明的过程。

如果我们用逻辑符号来表达上面三个命题的话,我们可以说

  1. M \rightarrow P
  1. S \rightarrow M
  1. S \rightarrow P

像这样的结论我们称之为“valid argument"有效论证。不理解的话我们可以看一种无效论证来体会一下

  1. 草(P)会死(M).
  1. 人(S)会死(M).
  1. 人(S)是草(P).

证明的方法有很多种,但是我们今天只讲三种

  1. 直接证明(direct proof)

  2. 反证法(contradiction)

  3. 否定证明(contrapositive)

直接证明

如果我们知道一个命题p为真,而且$p \rightarrow q$为真,那么我们就可以直接得到p。举个例子:

  1. 小明刚吃过饭
  1. 小明吃完饭一定会睡半小时

这两个命题都为真的时候我们可以推导出小明正在睡觉。

反证法

反证法中,我们通过将命题假设为真结果为假来反推出命题的错误。

比如说 证明:“如果3n+2是一个奇数的话,那么n就是一个奇数”

首先假设“3n+2是奇数”为真,”n是奇数“为假

我们知道任何偶数都可以被2整除,那么n就可以写成2k的形式(k为任意整数)

那么3(2k)+2就是一个奇数。

然后是

3(2k)+2 = 6k+2 = 2(3k+1)

从算式中我们得出(3k+1)是一个整数,2乘以任何证书都是偶数,这也间接说明3n+2是偶数,这个和我们的假设“n是奇数”不一致。于是我们可得“如果3n+2是一个奇数的话,那么n就是一个奇数”

否定证明

否定证明是利用 p \rightarrow q 意味着 \neg q \rightarrow \neg q 的特性(注意后面这一个是q在前。

利用上面那个例子,我们假设“n为偶数”

我们设n=2,代入算是3n+2中。

发现3n+2不为奇数,但是命题中说它应该是奇数。所以可得“如果3n+2是一个奇数的话,那么n就是一个奇数”

课后练习

我们在初高中(可能小学)学过有理数,我们复习一下

一个实数如果可以被写成 \frac{a}{b} 的形式,其中ab为整数,我们就说他是有理数

请证明: \sqrt{2} 是无理数

1 个赞