第1章 逻辑与证明 (Logic and Proofs)

一、导读

1.1 本章学习目标

完成本章学习后，你将能够：

理解命题逻辑的基本概念，包括原子命题、复合命题和真值表

掌握谓词逻辑中的量词（全称量词∀和存在量词∃）及其使用方法

熟练运用常见的推理规则进行有效论证

掌握直接证明、反证法、数学归纳法等基本证明方法

理解逻辑等价和蕴含关系的判定方法

能够将自然语言陈述转化为形式化逻辑表达式

识别常见逻辑谬误并避免在推理中犯错

将逻辑思维应用于程序设计和算法正确性证明

1.2 为什么本章如此重要

逻辑是计算机科学的基石。从硬件电路设计到软件验证，从数据库查询优化到人工智能推理，逻辑无处不在。

在编程语言层面：条件语句（if-else）、循环条件、布尔表达式都是命题逻辑的直接应用。理解逻辑运算的优先级和结合性，能够帮助你编写更清晰、更少bug的代码。

在算法分析层面：证明算法的正确性需要严格的逻辑推理。无论是排序算法的终止性证明，还是图算法的最优性证明，都依赖于本章介绍的证明技巧。

在系统设计层面：形式化方法使用逻辑来描述系统规范，并通过自动化工具验证系统是否满足这些规范。这在安全关键系统（如航空航天、医疗设备）中尤为重要。

在数据库领域：SQL查询本质上是谓词逻辑的应用。理解量词和逻辑连接词有助于编写更高效、更准确的数据库查询。

在人工智能领域：知识表示、自动推理、专家系统都建立在逻辑基础之上。一阶逻辑是AI中最常用的知识表示语言之一。

对于程序员而言，良好的逻辑思维能力是区分优秀工程师与普通工程师的关键因素。它不仅能帮助你写出正确的代码，还能帮助你在调试时快速定位问题，在设计时预见潜在的边界情况。

1.3 核心问题引导

在学习本章之前，请思考以下问题：

为什么"如果今天下雨，那么地面湿"这个陈述在今天不下雨时仍然为真？

"所有鸟都会飞"和"有些鸟不会飞"这两个陈述能否同时为真？为什么？

如何证明一个存在性命题（如"存在无穷多个素数"）而不具体构造出实例？

为什么反证法在数学证明中如此有效？它的逻辑基础是什么？

程序中的断言（assertion）与逻辑中的命题有什么联系？

如何用逻辑表达"恰好有一个元素满足某性质"？

为什么在编程中我们常说"短路求值"？它与逻辑运算有什么关系？

数学归纳法为什么能保证对所有自然数成立？它与递归有什么内在联系？

二、核心概念详解

2.1 命题逻辑 (Propositional Logic)

定义与直觉解释

命题逻辑是研究命题之间逻辑关系的形式系统。命题（proposition）是一个有确定真值的陈述句，它要么为真（True，记作T或1），要么为假（False，记作F或0），不能既真又假，也不能非真非假。

例如：

• "2 + 2 = 4" 是一个命题，其真值为真
• "北京是中国的首都" 是一个命题，其真值为真
• "x > 5" 不是命题（因为x的值未确定，无法判断真假）
• "请关上门" 不是命题（这是祈使句，没有真值）

原子命题是最简单的命题，不能再分解为更小的命题。复合命题是由原子命题通过逻辑连接词组合而成的命题。

基本逻辑连接词

真值表是定义逻辑连接词语义的标准方法。以下是蕴含连接词的真值表：

蕴含的真值表常常让初学者困惑。关键在于理解：蕴含式 p → q 只在"前件为真而后件为假"时为假。当p为假时，无论q是什么，p → q 都为真。这被称为"空真"（vacuously true）。

直觉上，"如果今天下雨，那么我带伞"这个承诺只有在"下雨了但我没带伞"时才被违背。如果今天没下雨，无论我带不带伞，我都没有违背承诺。

逻辑等价

两个命题公式是逻辑等价的，如果它们在所有可能的真值赋值下都有相同的真值。记作 p ≡ q。

重要的逻辑等价律：

德摩根定律（De Morgan's Laws）：

• ¬(p ∧ q) ≡ ¬p ∨ ¬q
• ¬(p ∨ q) ≡ ¬p ∧ ¬q

德摩根定律在编程中非常有用。例如，条件 !(a && b) 等价于 !a || !b。理解这一点可以帮助你简化复杂的布尔表达式。

分配律：

• p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
• p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

吸收律：

• p ∧ (p ∨ q) ≡ p
• p ∨ (p ∧ q) ≡ p

范式（Normal Forms）

任何命题公式都可以转换为等价的合取范式（CNF）或析取范式（DNF）。

• 合取范式：若干子句的合取，每个子句是若干文字（原子命题或其否定）的析取

- 例如：(p ∨ q) ∧ (¬p ∨ r) ∧ (q ∨ ¬r)

• 析取范式：若干项的析取，每项是若干文字的合取

- 例如：(p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ ¬r)

范式在自动定理证明和SAT求解器中有重要应用。

2.2 谓词逻辑 (Predicate Logic)

从命题到谓词

命题逻辑的局限性在于它无法处理涉及变量的陈述。例如，"所有人类都会死"这个陈述包含了一个普遍性的断言，无法用单个命题来表示。

谓词逻辑（也称为一阶逻辑）扩展了命题逻辑，引入了：

• 变量：可以取不同值的符号
• 谓词：描述对象性质或对象间关系的函数，返回真值
• 量词：对变量进行量化

例如，设 H(x) 表示"x是人类"，M(x) 表示"x会死"，则"所有人类都会死"可以表示为：

$$\forall x (H(x) \rightarrow M(x))$$

量词

全称量词 ∀（读作"对于所有"）：

• $\forall x P(x)$ 表示"对于论域中的所有x，P(x)都为真"
• 要证明 $\forall x P(x)$ 为假，只需找到一个反例

存在量词 ∃（读作"存在"）：

• $\exists x P(x)$ 表示"论域中存在至少一个x，使得P(x)为真"
• 要证明 $\exists x P(x)$ 为真，只需找到一个实例

量词的否定（德摩根定律的量词版本）：

• $\neg \forall x P(x) \equiv \exists x \neg P(x)$
• $\neg \exists x P(x) \equiv \forall x \neg P(x)$

直觉上："并非所有人都喜欢咖啡"等价于"存在某人不喜欢咖啡"；"不存在永动机"等价于"所有机器都不是永动机"。

嵌套量词

当多个量词嵌套使用时，顺序非常重要：

• $\forall x \exists y (x < y)$：对于每个数x，都存在比它大的数y（在实数域中为真）
• $\exists y \forall x (x < y)$：存在一个数y，比所有数x都大（在实数域中为假）

这两个公式不等价！第一个说"没有最大数"，第二个说"存在最大数"。

在编程中，嵌套量词对应嵌套循环：

# ∀x ∃y P(x, y) 的计算
for x in domain:
    found = False
    for y in domain:
        if P(x, y):
            found = True
            break
    if not found:
        return False
return True

# ∃y ∀x P(x, y) 的计算
for y in domain:
    all_satisfied = True
    for x in domain:
        if not P(x, y):
            all_satisfied = False
            break
    if all_satisfied:
        return True
return False

2.3 推理规则 (Rules of Inference)

推理规则是从已知前提推导出结论的有效模式。一个推理规则是有效的，如果当前提都为真时，结论必然为真。

基本推理规则

假言推理（Modus Ponens）：

$$\frac{p \rightarrow q, \quad p}{\therefore q}$$

如果"如果p则q"为真，且p为真，那么q为真。这是最常用的推理规则。

假言三段论（Hypothetical Syllogism）：

$$\frac{p \rightarrow q, \quad q \rightarrow r}{\therefore p \rightarrow r}$$

析取三段论（Disjunctive Syllogism）：

$$\frac{p \vee q, \quad \neg p}{\therefore q}$$

全称例化（Universal Instantiation）：

$$\frac{\forall x P(x)}{\therefore P(c)}$$

如果某个性质对所有元素成立，那么它对特定元素c也成立。

存在推广（Existential Generalization）：

$$\frac{P(c)}{\therefore \exists x P(x)}$$

如果某个特定元素c具有性质P，那么存在元素具有性质P。

推理的有效性 vs 真实性

重要的是区分推理的有效性和结论的真实性：

• 有效推理：如果前提为真，则结论必为真（关注推理形式）
• 真实结论：结论实际上为真（关注事实内容）

一个推理可以是有效的，但结论却是假的——如果前提本身就是假的。

例如：

• 前提1：所有猫都会飞（假）
• 前提2：Tom是猫（真）
• 结论：Tom会飞（假）

这个推理是有效的（形式正确），但结论是假的（因为前提1是假的）。

2.4 证明方法 (Proof Methods)

直接证明（Direct Proof）

要证明 $p \rightarrow q$，假设p为真，然后通过逻辑推理得出q为真。

示例：证明"如果n是偶数，则n²是偶数"

证明：

假设n是偶数，则存在整数k使得 n = 2k。

那么 n² = (2k)² = 4k² = 2(2k²)。

令 m = 2k²，则m是整数，且 n² = 2m。

因此n²是偶数。∎

反证法（Proof by Contradiction）

要证明命题p，假设¬p为真，然后推导出矛盾（即推出一个显然为假的陈述，如 0 = 1）。

经典示例：证明 $\sqrt{2}$ 是无理数

证明：

假设 $\sqrt{2}$ 是有理数，则存在互质的正整数p和q使得 $\sqrt{2} = \frac{p}{q}$。

两边平方得：$2 = \frac{p^2}{q^2}$，即 $p^2 = 2q^2$。

因此p²是偶数，从而p也是偶数（因为奇数的平方是奇数）。

设 p = 2k，代入得：$(2k)^2 = 2q^2$，即 $4k^2 = 2q^2$，所以 $q^2 = 2k^2$。

因此q²也是偶数，从而q也是偶数。

但这与p和q互质矛盾（因为它们都是偶数，至少有公因子2）。

因此假设错误，$\sqrt{2}$ 是无理数。∎

逆否证明（Proof by Contrapositive）

要证明 $p \rightarrow q$，可以证明其逆否命题 $\neg q \rightarrow \neg p$，因为两者等价。

示例：证明"如果n²是偶数，则n是偶数"

直接证明较困难，我们证明逆否命题："如果n是奇数，则n²是奇数"。

证明：

假设n是奇数，则存在整数k使得 n = 2k + 1。

那么 n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1。

令 m = 2k² + 2k，则m是整数，且 n² = 2m + 1。

因此n²是奇数。∎

数学归纳法（Mathematical Induction）

数学归纳法用于证明关于自然数的命题。它包含两个步骤：

基础步骤：证明命题对最小值（通常是n=0或n=1）成立

归纳步骤：假设命题对n=k成立（归纳假设），证明它对n=k+1也成立

原理：如果基础步骤和归纳步骤都成立，那么命题对所有自然数成立。

直觉上，这就像多米诺骨牌：如果你能推倒第一块（基础步骤），且每一块倒下都会导致下一块倒下（归纳步骤），那么所有骨牌都会倒下。

示例：证明 $1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}$

证明：

基础步骤：当n=1时，左边=1，右边=$\frac{1 \times 2}{2} = 1$。成立。

归纳步骤：假设对n=k成立，即 $1 + 2 + ... + k = \frac{k(k+1)}{2}$。

考虑n=k+1：

$$1 + 2 + ... + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$

$$= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$$

这正是公式对n=k+1的形式。因此由归纳法，命题对所有正整数n成立。∎

强归纳法（Strong Induction）

强归纳法的归纳假设更强：假设命题对所有小于等于k的自然数都成立，而不仅仅是对k成立。

示例：证明每个大于1的整数都可以分解为素数的乘积。

证明：

基础步骤：n=2是素数，本身就是素数乘积（只有一个因子）。

归纳步骤：假设所有满足 $2 \leq m \leq k$ 的整数m都可以分解为素数乘积。

考虑n=k+1：

• 如果k+1是素数，则它本身就是素数乘积。
• 如果k+1是合数，则存在 $a, b$ 使得 $k+1 = a \times b$，其中 $2 \leq a, b \leq k$。

由归纳假设，a和b都可以分解为素数乘积，因此k+1也可以。

由强归纳法，命题成立。∎

构造性证明与非构造性证明

构造性证明：通过实际构造出满足条件的对象来证明存在性。

示例：证明存在无理数的无理数次幂是有理数。

我们知道 $\sqrt{2}$ 是无理数。考虑 $(\sqrt{2})^{\sqrt{2}}$：

• 如果 $(\sqrt{2})^{\sqrt{2}}$ 是有理数，则我们已经找到例子。
• 如果 $(\sqrt{2})^{\sqrt{2}}$ 是无理数，则考虑 $((\sqrt{2})^{\sqrt{2}})^{\sqrt{2}} = (\sqrt{2})^2 = 2$，这是有理数。

这个证明是非构造性的，因为我们没有明确指出哪个数满足条件（实际上 $(\sqrt{2})^{\sqrt{2}}$ 已被证明是超越数，因此是无理数）。

三、程序员的视角

3.1 在计算机科学中的应用

程序验证

逻辑是程序形式化验证的基础。前置条件（precondition）、后置条件（postcondition）和循环不变式（loop invariant）都是用谓词逻辑表达的。

例如，对于一个排序函数：

• 前置条件：输入是一个数组
• 后置条件：输出是一个排列，且对于所有 i < j，有 output[i] ≤ output[j]

霍尔逻辑（Hoare Logic）使用三元组 {P} C {Q} 来表示：如果程序C执行前P成立，且C终止，则执行后Q成立。

布尔表达式优化

编译器使用逻辑等价律来优化布尔表达式。例如：

# 原始代码
if not (a and b):
    do_something()

# 优化后（德摩根定律）
if not a or not b:
    do_something()

在某些情况下，后者可能更高效（短路求值）。

数据库查询

SQL中的WHERE子句本质上是谓词逻辑的应用：

-- 选择所有年龄大于25且部门为'工程'的员工
SELECT * FROM employees WHERE age > 25 AND department = 'Engineering';

这里的 age > 25 AND department = 'Engineering' 就是一个谓词。

类型系统

现代编程语言的类型系统基于逻辑。Curry-Howard同构揭示了类型系统与直觉主义逻辑之间的深刻联系：类型对应命题，程序对应证明。

3.2 常见陷阱与误区

混淆充分条件与必要条件

• p是q的充分条件：p → q（p成立足以保证q成立）
• p是q的必要条件：q → p（q成立要求p必须成立）

例如："是哺乳动物"是"是人类"的必要条件，但不是充分条件。

在编程中，这种混淆会导致错误的条件判断。

忽视边界情况

在证明涉及自然数的命题时，忘记检查基础情况（如n=0或n=1）是常见错误。同样，在编程中，空列表、零值、负数等边界情况经常被忽视。

错误地否定全称量词

$\neg \forall x P(x)$ 不等价于 $\forall x \neg P(x)$，而是等价于 $\exists x \neg P(x)$。

例如，"并非所有人都喜欢咖啡"不等于"所有人都不喜欢咖啡"，而是"有人不喜欢咖啡"。

无限递归与归纳失败

数学归纳法要求归纳步骤对所有k成立。如果归纳步骤只在某些条件下成立，证明就失败了。类似地，递归函数必须有正确的基础情况和递减参数，否则会导致无限递归。

3.3 与其他层级的联系

• 硬件层：逻辑门（AND、OR、NOT）直接实现命题逻辑运算
• 操作系统层：进程同步中的条件变量、信号量使用布尔逻辑
• 网络层：路由协议中的决策基于逻辑判断
• 应用层：业务规则引擎、权限系统都依赖逻辑表达

四、代码实战

4.1 真值表生成器

"""
真值表生成器：计算命题公式在所有可能赋值下的真值
"""

from itertools import product

def evaluate_and(a, b):
    """计算 a AND b"""
    return a and b

def evaluate_or(a, b):
    """计算 a OR b"""
    return a or b

def evaluate_not(a):
    """计算 NOT a"""
    return not a

def evaluate_implies(a, b):
    """计算 a IMPLIES b"""
    return (not a) or b

def generate_truth_table():
    """生成二元逻辑连接词的真值表"""
    values = [False, True]
    
    print("p | q | p∧q | p∨q | p→q | p↔q")
    print("-" * 40)
    
    for p, q in product(values, repeat=2):
        and_val = evaluate_and(p, q)
        or_val = evaluate_or(p, q)
        implies_val = evaluate_implies(p, q)
        iff_val = (p == q)
        
        p_str = "T" if p else "F"
        q_str = "T" if q else "F"
        and_str = "T" if and_val else "F"
        or_str = "T" if or_val else "F"
        implies_str = "T" if implies_val else "F"
        iff_str = "T" if iff_val else "F"
        
        print(f"{p_str} | {q_str} |  {and_str}  |  {or_str}  |  {implies_str}  |  {iff_str}")

if __name__ == "__main__":
    generate_truth_table()

4.2 数学归纳法验证

"""
验证求和公式：1 + 2 + ... + n = n(n+1)/2
通过计算验证前N个自然数
"""

def sum_formula_direct(n):
    """直接计算 1 + 2 + ... + n"""
    return sum(range(1, n + 1))

def sum_formula_closed(n):
    """使用闭合公式 n(n+1)/2"""
    return n * (n + 1) // 2

def verify_sum_formula(max_n=100):
    """验证公式对 1 到 max_n 的所有值成立"""
    for n in range(1, max_n + 1):
        direct = sum_formula_direct(n)
        closed = sum_formula_closed(n)
        
        if direct != closed:
            print(f"公式在 n={n} 时失败！")
            print(f"  直接计算: {direct}")
            print(f"  公式计算: {closed}")
            return False
    
    print(f"公式对 1 到 {max_n} 的所有值都成立！")
    return True

def prove_by_induction_step(k):
    """
    演示归纳步骤：
    假设 1+2+...+k = k(k+1)/2
    证明 1+2+...+k+(k+1) = (k+1)(k+2)/2
    """
    # 归纳假设
    hypothesis = k * (k + 1) // 2
    
    # 左边：加上 k+1
    left_side = hypothesis + (k + 1)
    
    # 右边：公式对 k+1
    right_side = (k + 1) * (k + 2) // 2
    
    print(f"归纳步骤验证 (k={k}):")
    print(f"  归纳假设: 1+...+{k} = {hypothesis}")
    print(f"  左边 (加{k+1}): {left_side}")
    print(f"  右边 (公式): {right_side}")
    print(f"  相等: {left_side == right_side}")
    
    return left_side == right_side

if __name__ == "__main__":
    verify_sum_formula(1000)
    print()
    prove_by_induction_step(5)

4.3 反证法：证明素数有无穷多个

"""
欧几里得证明：素数有无穷多个

证明思路：
假设只有有限个素数 p1, p2, ..., pn
考虑 N = p1*p2*...*pn + 1
N不能被任何pi整除（余数为1）
因此N要么是新的素数，要么有新的素因子
这与假设矛盾
"""

def is_prime(n):
    """判断n是否为素数"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def get_primes_up_to(n):
    """获取不超过n的所有素数"""
    return [i for i in range(2, n + 1) if is_prime(i)]

def euclid_contradiction(primes):
    """
    给定一组素数，构造N = 乘积 + 1
    返回N及其最小素因子
    """
    product = 1
    for p in primes:
        product *= p
    
    N = product + 1
    
    # 找到N的最小素因子
    smallest_factor = None
    for i in range(2, N + 1):
        if is_prime(i) and N % i == 0:
            smallest_factor = i
            break
    
    return N, smallest_factor

def demonstrate_euclid_proof(num_primes=5):
    """演示欧几里得证明的过程"""
    primes = get_primes_up_to(50)[:num_primes]
    
    print(f"假设只有这些素数: {primes}")
    
    N, factor = euclid_contradiction(primes)
    
    print(f"构造 N = {' * '.join(map(str, primes))} + 1 = {N}")
    print(f"N 的最小素因子: {factor}")
    
    if factor not in primes:
        print(f"{factor} 不在原素数列表中！")
        print("这与'只有这些素数'的假设矛盾。")
    else:
        print(f"{factor} 在原素数列表中（这种情况也可能发生）")
        print("需要进一步分析N的其他因子。")
    
    print("\n结论：素数有无穷多个。")

if __name__ == "__main__":
    demonstrate_euclid_proof(5)
    print()
    
    # 验证更多素数
    primes = get_primes_up_to(100)
    print(f"前25个素数: {primes[:25]}")
    print(f"100以内的素数个数: {len(primes)}")

五、深入思考

5.1 历史背景

逻辑学有着悠久的历史，可以追溯到亚里士多德（公元前384-322年）的三段论。然而，现代数理逻辑的发展始于19世纪末和20世纪初：

• 乔治·布尔（George Boole, 1815-1864）：创立布尔代数，为数字电路奠定理论基础
• 戈特洛布·弗雷格（Gottlob Frege, 1848-1925）：发展谓词逻辑，建立形式系统
• 伯特兰·罗素（Bertrand Russell, 1872-1970）和阿尔弗雷德·怀特海：试图将所有数学归约为逻辑
• 库尔特·哥德尔（Kurt Gödel, 1906-1978）：不完备性定理表明任何足够强大的形式系统都存在无法证明的真命题
• 艾伦·图灵（Alan Turing, 1912-1954）：图灵机模型为可计算性理论奠定基础

5.2 前沿方向

• 自动定理证明：使用计算机自动寻找数学证明，如Coq、Isabelle等证明助手
• 模型检测：自动验证有限状态系统是否满足给定的逻辑规范
• 可满足性模理论（SMT）：结合SAT求解器和特定理论的决策过程
• 形式化验证：在安全关键系统中使用逻辑方法验证软件正确性
• 线性逻辑：资源敏感逻辑，在并发编程和量子计算中有应用

5.3 延伸阅读

• 《Logic and Computer Design Fundamentals》by M. Morris Mano
• 《How to Prove It》by Daniel J. Velleman
• 《Concrete Mathematics》by Ronald L. Graham, Donald E. Knuth, Oren Patashnik
• MIT OpenCourseWare: Mathematics for Computer Science

六、实验笔记

实验1：构建命题逻辑计算器

目标：实现一个能够解析和计算简单命题公式的程序。

任务：

设计数据结构表示命题公式（原子命题、否定、合取、析取、蕴含）

实现公式求值函数，给定变量赋值后计算公式的真值

实现真值表生成器，列出公式在所有可能赋值下的真值

实现公式等价性检查：判断两个公式是否逻辑等价

（进阶）实现将任意公式转换为合取范式（CNF）的算法

测试用例：

• 验证德摩根定律：¬(p ∧ q) ≡ ¬p ∨ ¬q
• 验证分配律：p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
• 检查 p → q 与 ¬p ∨ q 是否等价

提交物：源代码、测试输出、简要报告说明设计思路。

实验2：证明辅助工具

目标：实现一个简单的交互式证明辅助工具，帮助用户练习数学归纳法。

任务：

定义数据结构表示数学命题（涉及自然数的等式或不等式）

实现基础步骤验证：检查命题对n=0或n=1是否成立

实现归纳步骤框架：用户输入归纳假设和推导过程，程序验证推导是否正确

提供预设的证明题目（如求和公式、不等式等）

记录用户的证明尝试，给出反馈

示例题目：

• 证明 $1 + 3 + 5 + ... + (2n-1) = n^2$
• 证明 $2^n > n$ 对所有 $n \geq 1$ 成立
• 证明 $n^3 - n$ 能被6整除

提交物：源代码、用户界面截图、使用说明。

七、本章小结

本章介绍了离散数学的逻辑基础，包括命题逻辑和谓词逻辑两个层次。命题逻辑研究简单命题通过逻辑连接词组合后的性质，核心概念包括真值表、逻辑等价和范式。谓词逻辑引入变量和量词，能够表达更丰富的陈述。

推理规则提供了从前提推导结论的有效模式，其中假言推理是最基本的规则。证明方法是数学和计算机科学中建立真理的手段，包括直接证明、反证法、逆否证明和数学归纳法等。

对于程序员而言，逻辑思维不仅帮助编写正确的代码，还在程序验证、查询优化、类型系统等方面有直接应用。理解逻辑的深层原理能够提升抽象思维能力，更好地处理复杂问题。

数学归纳法与递归编程有着深刻的联系：归纳的基础步骤对应递归的基础情况，归纳步骤对应递归调用。掌握归纳法不仅有助于数学证明，也有助于理解和设计递归算法。

八、习题

习题1（基础）：构造以下命题公式的真值表：

(a) $(p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p)$

(b) $(p \vee q) \wedge (\neg p \vee r) \rightarrow (q \vee r)$

习题2（基础）：使用逻辑等价律简化以下表达式：

(a) $\neg(\neg p \wedge q) \vee (p \wedge \neg q)$

(b) $(p \rightarrow q) \wedge (q \rightarrow p)$

习题3（中等）：将以下自然语言陈述翻译为谓词逻辑公式：

(a) 每个学生都喜欢至少一门课程

(b) 存在一个素数大于100

(c) 对于每个实数，都存在一个更大的有理数

(d) 恰好有两个学生获得了满分

习题4（中等）：使用推理规则证明以下论证的有效性：

• 前提1：如果今天下雨，那么道路湿
• 前提2：如果道路湿，那么交通拥堵
• 前提3：今天下雨
• 结论：交通拥堵

习题5（中等）：用直接证明法证明：如果n是奇数，则 $n^2 - 1$ 能被8整除。

习题6（中等）：用反证法证明：不存在最大的素数。

习题7（较难）：用数学归纳法证明：对于所有 $n \geq 1$，有 $1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$。

习题8（较难）：证明或反驳：对于所有整数n，$n^2 + n + 41$ 是素数。（提示：尝试不同的n值）

习题9（挑战）：证明鸽巢原理的推广形式：如果将 $kn + 1$ 个物体放入n个盒子中，则至少有一个盒子包含至少 $k + 1$ 个物体。

习题10（挑战）：设计一个算法，判断给定的命题公式是否是重言式（在所有赋值下都为真）。分析你的算法的时间复杂度。