【学习笔记】离散数学（Discrete Math） - 证明 Proof 3

谁借莪１个温暖的怀抱￠ 2023-07-02 12:23 20阅读 0赞

# 离散数学（Discrete Math） #

# \- 证明proof #

**目录**

离散数学（Discrete Math）

\- 证明proof

Terminology 术语

How to prove conditional statements?

Direct proof直接证明法

Proof by contraposition对位证明法

Proof by contradiction 矛盾法/反证法

Vacaous and Trival proofs

Proof by cases 列举法

Uniqueness proofs 唯一性证明

名词补充

参考课程

--------------------

## Terminology 术语 ##

**Theorem 定理 ：**A theorem is a statement that can be shown to be true.

**Proposition 命题**：Less important theorems are called propositions.

**Proof 证明**：A proof is a valid argument that established the truth of a theorem.

**Axiom 公理**：Statements that we assume to be true.

**Lemma 引理**：A less important throrem that is helpful in the proof of other results.

**Corollary 推论**：A theorem that can be established directly from a theorem that has been proved.

**Conjecture 推测（猜想）**：A statement that is being proposed to be a true statement.

## How to prove conditional statements? ##

p->q

1.  Direct proof 直接证明法
2.  Proof by contraposition 对位证明法
3.  Proof by contradiction 矛盾法/反证法
4.  Vacaous and Trival proofs 空真和平凡证明

### Direct proof 直接证明法 ###

例：

P(n): n is odd.

Q(n): n^2 is odd.

∀n∈Z, P(n)-> Q(n)

证：

设n=2k+1，则有

n^2 = 2(2k^2+2k)+1

证毕

### Proof by contraposition 对位证明法 ###

p->q ≡┐q->┐p

Assume q is false by applying rule of inference, we conclude that p is false.

例：

Prove that if n is an integer and 3n+2 is odd, then n is odd.

证：

Assume n is not odd.

Then, n is even

There exists an integer k such that n=2k.

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

Since 3k+1 is an integer 3n+2 is even.

So, the premise is not true.

Therefore, the theorem is proved.

例2：

Definition

The real number r is rational if there exists integers p and q with q≠0 such that r=p/q. Areal number that is not rational is called irrational.

Example

Prove that the sum of two rational numbers is rational.

证：

∀x,y,R(x), R(y)-> R(x+y)

Assume R(x) and R(y) are true. (Premise前提)

R(x)-> ∃p,q≠0 such that x = p/q.(def)

R(y)-> ∃r,s≠0 such that y = r/s.(def)

x+y = p/q + r/s = (ps+rq)/qs

ps+rq and qs are integer and qs≠0, x+y is rational.(def)

证毕

例3：

If n is an integer and n^2 is odd, then n is odd. ∀n∈Z, odd(n^2)-> odd(n).

证：

We prove ┐odd(n)-> ┐odd(n^2).

Assume ┐odd(n) is true.

i.e. n is even.

There exists k such that n=2k.

n^2 = 2(2k^2)

Since 2k^2 is an integer, n^2 is even. Therefore ┐odd(n^2) is true.

### Proof by contradiction 矛盾法/反证法 ###

If we want to proof p is true, we first assume ┐p(i.e. p is false). Then , by applying rules of inference we get some contradiction.(i.e. ┐p->F). Since ┐p->F is true ,we can get p is T.

例：

Prove that ‘√2 is irrational’ by contradiction.

证：

Assume √2 is not irrational.

There exists integers p,q≠0, such that √2 = p/q( Beside, we can assume p and q are both composite.)

P^2 = 2q^2

Since p^2 is even ,q is even (E(p^2)->E(P))

Assume ,p = 2k, (2k)^2 = 2q^2.

We get

q^2 = 2k^2

since q^2 is even ,q is even .

2|p(代表2为p的一个因子) and 2|q , imply p,q are not composite.

This is a contradiction.

Therefore ‘√2 is rational’ is false

And we prove the theorem.

### Vacaous and Trival proofs 空真和平凡证明 ###

**虚假前件蕴含任何后件**

To prove p->q is true ,we can

show p is false (vacuous proof) or

show q is true (trivial proof).

例1

Let P(n) =”if n>1,then n^2>n”. Prove P(0) is true.

证：

P(0) =”if 0>1,then 0^2>0.” in the conditional statement.

The premise “0>1” is false , so P(0) is true.

例2

Let P(n) =”If a and b are positive integers with a ≥ b, then a^n ≥ b^n”. Show that P(0) is true.

证：

P(0) =”If a and b are positive integers with a ≥ b, then a^0 ≥ b^0.”

Since a^0=1 and b^0=1,

a^0 ≥ b^0 is true.

So, P(0) is true.

### Proof by cases 列举法 ###

(p1∪p2∪p3 ∪…∪pn)->q ó p ≡ p1∪p2∪p3 ∪…∪pn and p->q

例：

Show that there are no solutions in integers x and y of x^2+3y^2 = 8

证：

以y的定义域分段进行判断即可

### Uniqueness proofs 唯一性证明 ###

∃!xp(x) ≡ ∃x0(p(x0)) ∧ ∀x ≠x0 ┐p(x)

So, we need to

1.  Find an x0 such that P(x0) is true;
2.  Show that ∀ x≠x0 ┐p(x) is true.

## 名词补充 ##

WLOG 不失一般性原则 without loss of generality

Set 集合

Set builder 结构式式集合

Subsets 子集

## 参考课程 ##

易志伟老师 – 离散数学 Discrete Mathematics

【学习笔记】离散数学（Discrete Math） - 证明 Proof 3

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 NEFU离散数学实验3-递推方程

相关离散数学试题

相关学习Python数学math模块

相关 web3:区块链共识机制系列-POS(Proof of Stake)股权证明算法

相关【学习笔记】离散数学（Discrete Math） - 证明 Proof 3

相关【学习笔记】离散数学（Discrete Math） -命题逻辑1

相关 Math 数学函数

相关【离散数学】基础理论归纳

相关《离散数学》速成

相关离散数学