「Mathematics for Computer Science」学习笔记 - 证明

概述

第一部分: 证明

定义 一个 命题 的 数学证明 是从一个 公理 的基础集合推导出这个命题的逻辑推导链。

所以，命题、逻辑推导和公理是证明的定义中三个关键。

第一章: 命题

定义 一个 命题 是一个或是真或是假的陈述。

为了避开英语表述的模糊，数学家设计了一种针对表述逻辑关系的特殊的小巧语言，并且数学家赋予一些他们选中的英文单词(例如 “or”, “for all”)更精确的含义。搞懂这些词的含义是很重要的。

命题复合

如下的每个词都有对应的符号，我将提前把它们列在这里。

英语	表示符号
NOT(P)	$\neg$ P (或 $\bar{P}$)
P AND Q	P $\land$ Q
P OR Q	P $\vee$ Q
P IMPLIES Q (If P ,then Q)	P $\to$ Q
P IFF Q	P $\leftrightarrow$ Q

1. NOT, AND, 和 OR

   如果 P 表示任意一个命题，那么：

   P	NOT(P)
   T	F
   F	T

   如果 P 和 Q 表示任意一个命题，那么：

   P	Q	P AND Q
   T	T	T
   T	F	F
   F	T	F
   F	F	F

   P	Q	P OR Q
   T	T	T
   T	F	T
   F	T	T
   F	F	F

   P	Q	P XOR Q
   T	T	F
   T	F	T
   F	T	T
   F	F	F

   XOR 分开了 P 和 Q 是否相等的情况。

2. IMPLIES

   P IMPLIES Q, If P, then Q. 和 P $\rightarrow$ Q 这三个命题（表述方法）等价。

   如果 P 和 Q 表示任意一个命题，那么：

   P	Q	P IMPLIES Q
   T	T	T
   T	F	F
   F	T	T
   F	F	T

   这个真值表等价于 NOT(P) OR Q 。

   IMPLIES 遵从 If true, then true. 。并且，因为否命题可以推一切，所以所有 P 为假命题的 IMPLIES 命题均为真命题。

3. IFF

   P IFF Q, P if and only if Q. 和 P $\leftrightarrow$ Q 这三个命题（表述方法）等价，并且表示 P 和 Q 在逻辑上是等价的。

   如果 P 和 Q 表示任意一个命题，那么：

   P	Q	P IFF Q
   T	T	T
   T	F	F
   F	T	F
   F	F	T

   相当于 P IMPLIES Q 和 Q IMPLIES P 二者都为真命题。

4. 逻辑等价的Implication

   P	Q	P IMPLIES Q	NOT(Q) IMPLIES NOT(P)
   T	T	T	T
   T	F	F	F
   F	T	T	T
   F	F	T	T

   从真值表中不难看出，一个Implication和它的逆否命题(contrapositive)是等价的。

   P	Q	P IMPLIES Q	Q IMPLIES P
   T	T	T	T
   T	F	F	T
   F	T	T	F
   F	F	T	T

   而Implication与其逆命题(converse)并不等价。

   一个Implication如果与其逆命题同时成立，则可以得到这个Implication的左右两侧等价，正如IFF那点的结尾所言。

计算机程序中的命题逻辑