人工智能教程 - 数学基础课程1.5 - 离散数学-1 证明

证明(proof)

是一种确定事实的方法

(A proof is a method for ascertaining the truth)

物理上和平时：

• 实验和观察(Experimentation & oberservation)
• 抽样和找反例(Sampling & counterexamples)
• 裁判(judge & jury)
• Boss
• inner conviction
  例如在计算机科学里很流行的一句话:“信不信由你，我的程序里没有bug！”
  (It is very popular in computer science.believe it or not,with the mantra.there are no bugs in my program)

数学证明

证明是通过一系列公理的逻辑推理来验证一个命题

(A methematical proof is a verigication of a proposition by a chain of logical deductions from a set of axioms)

命题是真或假的陈述：
(A proposition is a statement that is either true or false)

Ex:\forall n \in \mathbb{N} n^2+n+41 is a prime number

\forall for all 【量词】(quantifier)
\mathbb{N} {0,1,2,3,…}【论域】(universe of discourse)
n^2+n+41 is a prime number :谓词(predicate)

谓词是一个命题，它的真值依赖于变量的值
(a predicate is a propostion whose truth depends on the value of a variable )

在实际的物理学和统计学中，你经常会通过检验前40个值
但即便前40个都正确，可能41就会是命题为假。

Ex:
Ex:\forall n \in \mathbb{Z} , n\geq z\Rightarrow n^2\geq 4
“\Rightarrow” means implies
Def： An inplication p\Rightarrow q is true if p is False or q is True

真值表(Truth Table)

p	q	p\Rightarrowq	q\Rightarrowp	p\Leftrightarrowq
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

公理

定义：是一个假定为真的命题
def: An axiom is a proposition that is assumed to be true

公理应该具备：

• 一致性(consistent)
  定义：如果一组公理是一致的，那么一个命题不能同时为真，同时为假
  (Def: A set of axioms is consistent if no proposition can be proved to be both true and false.)

• 完整性(complete)
  定义：如果一组公理是完整的，那么所有命题必须或者为真或为假。
  (Def: A set of axioms is complete if it can be used to prove every proposition is .)