证明
- 定理：是一个能够表明为真的语句，有时把不太重要的定理称为命题。
- 引理：在其他结果证明中很有帮助的不大重要的定理
- 推论：从定理直接建立被证明的定理
- 猜想：被提出为真的命题，通常是在一些依据的基础上，启发式论证，未被证实。
##证明定理的方法
直接证明
直接证明用于$p\rightarrow q$类型语句的方法。
第一步假设$p$为真，然后用定理、定义和前面的证明过的定理以及推理规则，来证明出$q$也肯定为真。
反证法
反证法基于$p\rightarrow q\equiv \lnot q\rightarrow \lnot p$，也就是说$p\rightarrow q$可以用它的倒置$\lnot q\rightarrow \lnot p$来证明。
在反证法中，将$\lnot q$作为假设，用公理、定义和前面证明过的定理以及推理规则，证明$\lnot p$。
例子
前提定义： 整数$n$是偶数，如果存在一个整数$k$使得$n=2k$；整数$n$是奇数，如果存在一个整数$k$使得$n=2k+1$。
证明”若$\3n+2$是奇数，则$n$也是奇数”。
假设$n$为偶数，则有$n=2k$，将其带入，得到$3n+2=3(2k)+2=6k+2=2(3k+1)$，由偶数定义得知$3n+2$是偶数，这与定理前提矛盾，因此$n$是奇数。
空证明
在条件语句$p\rightarrow q$中，如果能够证明$p$为假，那么$p\rightarrow q$一定为真，这就得到证明$p\rightarrow q$的证明方法。
平凡证明
在条件语句$p\rightarrow q$中，如果能够证明$q$为假，那么$p\rightarrow q$一定为真，这就得到证明$p\rightarrow q$的证明方法。
归谬证明
假设我们要证明$p$是真的，我们可以假定$\lnot p$为真，然后推导出一个矛盾式$q$，使得$\lnot p\rightarrow q$为真，因为$\lnot p\rightarrow q$为真，$\lnot p$必然为假，从而得出$p$为真。
也可用矛盾式证明$p\rightarrow q$是真的，通过假设$p$和$\lnot q$都为真，来证明$q$也一定为真。这意味着$q$和$\lnot q$都为真，矛盾。
归谬证明实例
前提定义：若存在整数$p$和$q(q\neq 0)$使得$r=p/q$。实数$r$是有理数。
证明：$\sqrt 2$是无理数
假定$\sqrt 2$是有理数，则存在整数$a$和$b$满足$\sqrt 2=a/b$，其中$a$和$b$没有公因子。
将等式两边平方，得$2=a^2/b^2$ $2b^2=a^2$。
根据偶数定义，$a^2$是偶数，若$a^2$是偶数，则$a$也是偶数，那么存在一个整数$c$，由$a=2c$。因此$2b^2=4c^2$。
等式两边除以$2$，得到$b^2=2c^2$。
由偶数定义，$b^2$是偶数，$b$也是偶数。
我们已经由$\lnot p$得出等式$\sqrt 2=a/b$，其中$a$和$b$没有公因子，这与$a$和$b$都是偶数矛盾，因此$\lnot p$为假，从而得出$p$为真。
等价性证明
为了证明一个定理是双条件的，即形如$p↔︎q$的语句，我们来证明$p\rightarrow q$和$q\rightarrow p$都是真的。这个方法的有效性基于:
$$ (p↔︎q)↔︎[(p\rightarrow q)\land (q\rightarrow p)]$$
有时候定理说几个命题都是等价的。这样的定理说命题$p_1,p_2,p_3,…,p_n$都是等价的。这个定理可以写成: $$p_1↔︎p_2↔︎…↔︎p_n$$
反例
证明形如$\forall xP(x)$的语句为假，只要能找到一个反例，即存在一个例子使$P(x)$为假。
穷举证明
有些定理能够通过有关的小数量例子测试来证明。这些证明通过穷举所有可能进行。穷举是分情形证明的特殊类型。
分情形证明
为了证明形如$(p_1 ∨ p_2 ∨ \dots ∨ p_n)→q$的条件语句，可以用永真式$[(p_1 ∨ p_2 ∨ \dots ∨ p_n)→q]↔︎[(p_1 →q)∧(p_2 →q)∧\dots ∧(p_n →q)]$作为推理规则。这个推理规则说明，可以通过分别证明每个条件语句$p_i→q$来证明命题$p_1,p_2,\dots p_n$的析取式组成前提的原条件语句。
存在性证明
对于形如$∃P(x)$的命题的证明。
- 构造性的存在性证明：找出一个使得$P(x)$为真的元素$a$。
- 非构造性的存在性证明：一个普通方法是，使用归缪证明，证明该存在量词化的否定式蕴含着矛盾。
唯一性证明
断言具有特定性质的元素惟一存在。证明分为两部分：
- 存在性：证明存在某个元素$x$具有期望的性质
- 唯一性：证明若$y≠x$，则$y$不具有期望的性质。或者我们可以证明如果$x$和$y$都具有期望的性质，则$x=y$。