模块 04: 数学基础

命题具有真值。否定翻转真值，合取要求双方成立，析取要求至少一方成立。蕴含 p→q 等价于非 p 或 q，仅在 p 真而 q 假时为假。它表达前置条件成立时后置条件必须成立，并不表示因果。每条记录都有 ID 与某条记录有 ID 不同。∀x P(x) 的否定是 ∃x 非 P(x)，一个反例即可推翻全称断言。

集合包含不同元素，不具有位置顺序。并集包含任一集合中的元素，交集保留共同元素，差集 A−B 保留仅在 A 中的元素。关系是有序对的集合，例如借阅关系连接书 ID 与会员 ID。自反表示元素关联自身，对称表示关系可反向，传递表示 xRy 且 yRz 推出 xRz。相等满足三者，有向依赖未必对称。

函数把定义域每个元素映射到值域中的唯一元素。单射要求不同输入对应不同输出，满射要求覆盖陪域，双射兼具两者。两个独立选择分别有 a、b 种可能时，共有 a×b 种组合；只有等可能时才能直接用于概率。超过 k 个对象放入 k 个桶，至少一个桶重复占用，这是鸽巢原理，也说明哈希碰撞无法总被避免。

直接证明从假设推出结论，反例否定全称陈述。归纳法先证明基础情况，再证明 k 成立推出 k+1 成立。对 1+…+n=n(n+1)/2，n=0 时为零；在 k(k+1)/2 上加 k+1 得 (k+1)(k+2)/2。检查十个值有助调试，却不能覆盖无限多个 n。循环不变式也采用初始化与保持结构。

有限样本空间列出结果。等可能时 P(A)=|A|/|Ω|。条件概率把范围限制为 B：P(A|B)=P(A∩B)/P(B)，要求 P(B)>0。独立要求 P(A∩B)=P(A)P(B)，与互斥不同。期望按概率加权，公平骰子的期望为 3.5，但实际不会掷出 3.5。E[X+Y]=E[X]+E[Y] 无需独立，期望相乘等其他恒等式则需附加条件。

下载脚本，在终端中使用 Python 3.11 或更新版本运行：python m04_logic.py. Windows 也可使用 py -3；部分系统使用 python3。实验仅用标准库。先预测结果，再运行并完成变体。不要使用 -O，以保留断言。下方输出由构建器实际运行捕获，两种语言使用相同代码与输出。

枚举四种布尔输入，检查蕴含与逆否命题等价，并验证德摩根律。

下载 m04_logic.py

"""Enumerate finite cases to check logical equivalence and set operations."""
from itertools import product
for p, q in product([False, True], repeat=2):
    implication = (not p) or q
    contrapositive = q or (not p)  # (not q) implies (not p)
    assert implication == contrapositive
    assert (not (p and q)) == ((not p) or (not q))
    print(int(p), int(q), "implies:", int(implication))
available = {1, 2, 3}
requested = {2, 3, 4}
print("intersection:", sorted(available & requested))
print("union:", sorted(available | requested))
print("missing:", sorted(requested - available))

0 0 implies: 1
0 1 implies: 1
1 0 implies: 0
1 1 implies: 1
intersection: [2, 3]
union: [1, 2, 3, 4]
missing: [4]

1. 改成 q→p 并找反例。
2. 加入集合对称差。

两枚有标记的骰子有 36 个等可能有序结果，Fractions 避免浮点近似。

下载 m04_probability.py

"""Exact finite probability, conditional probability and a summation identity."""
from fractions import Fraction
outcomes = [(a, b) for a in range(1, 7) for b in range(1, 7)]
event = [(a, b) for a, b in outcomes if a + b == 7]
condition = [(a, b) for a, b in outcomes if a == 1]
joint = [x for x in condition if sum(x) == 7]
print("P(sum=7):", Fraction(len(event), len(outcomes)))
print("P(sum=7 | first=1):", Fraction(len(joint), len(condition)))
for n in [0, 1, 5, 10]:
    total = sum(range(1, n + 1))
    assert total == n * (n + 1) // 2
    print("n:", n, "sum:", total)

P(sum=7): 1/6
P(sum=7 | first=1): 1/6
n: 0 sum: 0
n: 1 sum: 1
n: 5 sum: 15
n: 10 sum: 55

1. 计算和为 8 的概率，以及第一枚为 1 时的条件概率。
2. 累加时排除 n，找失败案例。

先尝试，再展开解答。★ 应用概念；★★ 结合概念；★★★ 进行设计或证明。

选择答案查看反馈，重置后可重做。无需 JavaScript 也可阅读答案表。

• MIT 计算机科学数学 — 阅读开头的证明与归纳章节，指出一个证明的假设。

解释测试与证明提供的不同证据，为目录计数写一个不变式。模块 05 将分析搜索与排序。