Logic and Proofs - 逻辑与证明

更新中 · 笔记范围：持续补充

Propositional Logic

命题（Proposition）的定义：

  • 陈述性（Declarative）
  • 真值（Either true or false）

逻辑连接符（Logic Connectives）：

  • Negation \neg
  • Conjunction/and \land
  • Disjunction/or \lor
  • Exclusive or \oplus
  • Implication \to
  • Biconditional \leftrightarrow

真值表（Truth table）：表示不同的命题之间，所有真值（T/F）之间的关系。

  • 行数：若涉及 n 个命题，则有 2^{n} 行。
    例如异或的真值表：
    Logic - 逻辑
  • p\oplus q\equiv \neg(p\leftrightarrow q)
  • p\to q \equiv \neg p\lor q (Useful Law)

关于 Implication，有一些对应的概念：

  • Converse of p\to q ： q\to p（反/逆命题）
  • Contrapositive of p\to q： \neg q\to \neg p（逆否命题）
  • Inverse of p\to q ：\neg p\to \neg q（否命题）

从 truth table 得到逻辑表达式：把那些 True 的行用 disjunction 连接，例如异或可以写成 (p\land \neg q)\lor(\neg p\land q)。

一个 bit 就可以表示 0 和 1。
计算机中布尔变量（Boolean Variable）表示 0 和 1。
Bit string 就是一些 bit 组成的序列。
按位操作（bitwise operation）：把 T 和 F 替换为 1 和 0 进行运算。

George Boole：布尔代数（Boolean algebra）的发明者。

Tautology：永真式。（逻辑等价于 T）
Contradiction：永假式。(逻辑等价于 F）
Contingency：可真可假。

逻辑等价（Logical Equivalent）：

  • 一种定义：p 与 q 具有相同的真值表。
  • 另一种定义：p\leftrightarrow q 是永真式。
  • 记作 p\equiv q 或 p \iff q。

De Morgan’s Law：

  • \neg(p\lor q)\equiv \neg p\land \neg q
  • \neg(p\land q)\equiv \neg p\lor \neg q

Identity Law：

  • p\land T\equiv p
  • p\lor F\equiv p

Domination Law：

  • p\lor T\equiv T
  • p\land F\equiv F

Idempotent Law：

  • p\lor p\equiv p
  • p\land p\equiv p

Double negation Laws:

  • \neg(\neg p)\equiv p

Commutative Laws:

  • p\lor q\equiv q\lor p
  • p\land q\equiv q\land p

Associative Laws:

  • (p\lor q)\lor r\equiv p\lor(q\lor r)
  • (p\land q)\land r\equiv p\land(q\land r)

Distributive Laws:

  • p\lor(q\land r)\equiv(p\lor q)\land(p\lor r)
  • p\land(q\lor r)\equiv(p\land q)\lor(p\land r)

Absorption Laws

  • p\lor(p\land q)\equiv p
  • p\land(p\lor q)\equiv p

Negation Laws

  • p\lor \neg p\equiv T
  • p\land \neg p\equiv F

证明逻辑等价的方法：

  • Truth table
  • Logical Equivalence inference
  • By discussion

Predicate Logic / First Order Logic

有量词的逻辑。

  • Existential Quantifier：\exists
  • Universal Quantifier：\forall

谓词逻辑包含

  • Constant
  • Variable
  • Predicate：P(x) 给每个 x 赋一个 T / F 值。

Predicate P(x_{1},\dots,x_{n}) 只能称为Statement；只有当每个 x_{i} 换成具体的值，或用量词约束全部自由变量，它才成为一个 proposition（具有真值）。

  • Universe/Domain：所有可能取值 (x_{1},x_{2}\dots x_{n}) 的集合。
  • Truth set：让 P(x_{1},\dots ,x_{n}) 成立的取值 (x_{1},x_{2}\dots x_{n}) 的集合。

\forall 和 \exists 的优先级比其他逻辑运算符更高。

通常 \forall, \to 搭配，\exists, \land 搭配。

  • \neg \exists x P(x)\equiv \forall x\neg P(x) (De Morgan Law) 否定之后改变量词类型，把否定放到谓词上。这对嵌套也成立： \neg(\forall x\exists yP(x,y))\equiv \exists x\forall y\neg P(x,y)。
  • \neg \forall x(P(x)\to Q(x))\equiv \exists x(P(x)\land \neg Q(x))

嵌套的量词若种类不同不可交换。

翻译：There is EXACTLY one person whom everybody loves.
\exists y(\forall xL(x,y) \land \forall z(\forall xL(x,z)\to z=y))

Inference

对于命题逻辑有如下的 Inference Rules:
Logic - 逻辑-1
Logic - 逻辑-2
Logic - 逻辑-3
Logic - 逻辑-4

对于一阶逻辑：
Logic - 逻辑-5

数学证明（Mathematical Proof）

Axiom（公理）： 在一个理论中选定、不经证明而作为推理起点的命题。
Theorem（定理）： 可以证明的命题。
Lemma（引理）： 可以证明的命题，用于证明其他命题。
Corollary（推论）： 从定理可以推出来的结论。

Formal Proof： 每一步都遵循逻辑，从前提/公理/引理/定理中获得。
Informal Proof： 更常用，使用自然语言。

证明定理（形如 p\to q）的基本方法（可以通过 p\to q 的真值表理解）：

  • Direct proof
  • Proof by contrapositive （逆否命题）
  • Proof by contradiction（说明 p\land \neg q 不可能发生以说明 p\to q）
  • Proof by cases （(p_{1}\lor\dots \lor p_{n})\to q \equiv(p_{1}\to q)\land(p_{2}\to q)\land\dots \land(p_{n}\to q)）
  • Proof of equivalence （p\leftrightarrow q\equiv(p\to q)\land(q\to p)）

Vacuous Proof：证明 p 永远是假的，那么 p\to q 就是真的。
Trivial Proof：证明 q 永远是真的，那么 p\to q 就是真的。
证明含量词的命题

  • Proof by cases
  • Counterexample
  • Constructive proof
  • Non constructive - proof by contradiction

数学归纳法

数学归纳法（Mathematical Induction），其实是把反证法（非直接证明）转换成一个直接的证明的结果。

Proof by Smallest Counterexample. 要证明 P(n) 成立 \forall n=0,1,2, \dots：

  • 假设有反例。首先验证 P(0) 成立。那么就可以令 m>0 是 最小的 使得 P(n) 为假的反例。
  • 那么 P(m') 成立 \forall0\leq m'<m。用这件事去说明 P(m) 是真的，那就导致了矛盾。
  • 于是没有反例，也就是说 P(n) 成立 \forall n=0,1,2, \dots。

要使用这种“找最小反例”的证明，需要证明的集合需要是 良序集（Well-Ordered Set）。自然数/正整数的集合自然就是良序集。

Proof by Smallest Counterexample 的证明过程，其实就相当于数学归纳法。因此有：
The Weak Principle of Mathematical Induction.

  • （Base Step）：若 P(b) 成立。
  • （Inductive Step）：P(n-1)\to P(n) 对所有 n> b 成立，那么 P(n) 对所有 n\geq b 成立。

另外还有：
The Strong Principle of Mathematical Induction.

  • （Base Step）：若 P(b) 成立。
  • （Inductive Step）：P(b)\land P(b+1)\land\dots \land P(n-1)\to P(n) 对所有 n> b 成立，那么 P(n) 对所有 n\geq b 成立。

格式：
Logic and Proofs - 逻辑与证明-1

递归

一个函数的 递归式（Recurrence Equation / Recurrence） 告诉我们如何从前 n-1 个函数值计算出 n 处的函数值：
f(n)=F(f(1),f(2), \dots,f(n-1))
例如解汉诺塔的递归算法。

  • 正确性。用 implicit 的归纳法，说明能解 1 层的，并且能解 n-1 层的汉诺塔就能解 n 层的即可。([n,0,0]\to[1,n-1,0]\to[0,n-1,1]\to[0,0,n])。
  • 复杂度。M(n)=2M(n-1)+1,M(1)=1。 可以用 explicit 的归纳法证明 M(n)=2^{n}-1。

一阶线性递归式（First-Order Linear Recurrence）： T(n) 只和 T(n-1) 有关，且 T(n-1) 只有一次。可以写成：
T(n)=f(n) T(n-1) +g(n)

定理： 对递归式
T(n)=rT(n-1)+g(n)
有
T(n)=r^{n}T(0)+ \sum _{i=1}^{n} r^{n-i}g(i)
显然可以通过数学归纳法证明。

主定理（The Master Theorem）。 对递归式
T(n)= aT(n / b) + c n^{d}
其中 a 为正整数，b>1,c>0,d\geq0，T(1)\geq0。那么：

  • 若 a<b^{d}，则 T(n)=\Theta(n^{d})。
  • 若 a=b^{d}，则 T(n) =\Theta(n^{d}\log n)
  • 若 a>b^{d}，则 T(n)=\Theta(n^{\log _{b}a})