Discreate Mathmatics

期末才想起来要学离散

布尔代数

image-20250517223806266

image-20250517223828265

好的，我们从最基础的概念说起，逐步推导出为什么由 nn 个生成元生成的布尔子代数最多有 22n2^{2n} 个元素。

---

1. 布尔代数与生成子代数

• 布尔代数 (B,∨,∧, ¬,0,1)(B,\lor,\land,,\lnot,0,1) 是一组满足一定公理的集合，其中有“或”“与”“非”、两端元 0,10,1。
• 给定子集 A={a1,…,an}⊆BA={a_1,\dots,a_n}\subseteq B，我们记由它们“生成”的最小子代数为 A∗A^*。
• 直观地说，A∗A^* 中的元素就是所有可以用有限次 ∨,∧,¬\lor,\land,\lnot 操作，从 a1,…,ana_1,\dots,a_n（以及代数中的 0,10,1）“拼”出来的结果。

---

2. 布尔表达式对应布尔函数

3. 布尔表达式：比如

   (a1∧¬a2)∨(a3∧a2∧¬a4) (a_1\land \lnot a_2)\lor (a_3\land a_2\land\lnot a_4)

   这样的公式，里面只出现了 a1,…,ana_1,\dots,a_n 和逻辑运算符。

4. 布尔函数：每当你给这 nn 个变量赋一组真值 (0/1)(0/1)，公式就有一个计算结果（0 或 1）。
   —— 换句话说，每个布尔表达式都定义了一个从 {0,1}n{0,1}^n 到 {0,1}{0,1} 的映射，也就是一个 布尔函数。

---

3. 等价与计数

• 等价：如果两个不同的布尔表达式对所有 (x1,…,xn)∈{0,1}n(x_1,\dots,x_n)\in{0,1}^n 的输出都一样，那么在任何布尔代数中，它们表示的是同一个元素。
• 布尔函数的总数：
  • 域是 {0,1}n{0,1}^n，共有 2n2^n 个输入。
  • 对每个输入，你可以选输 0 或 1，因此一共 22n2^{2n} 种不同的映射。

---

4. 把它们对应起来

5. 映射

   Φ:A∗  ⟶  {所有从 {0,1}n→{0,1}}, \Phi: A^* ;\longrightarrow; {\text{所有从 } {0,1}^n\to{0,1}},

   令 Φ(f)\Phi(f) = “把代数里的元 ff 看作一个布尔表达式，记录它在每组 (a1,…,an)(a_1,\dots,a_n) 取 0/1 时的输出真值表”。

6. 注入性

   • 若 f≠gf\neq g 在 A∗A^* 中是两个不同元素，则作为布尔表达式它们必有某组输入时输出不同，故对应的布尔函数也不同。
   • 因此 Φ\Phi 是单射。

7. 结论
   因为目标集合（所有布尔函数）大小为 22n2^{2n}，而 A∗A^* 至多和它等大，所以

   ∣A∗∣  ≤  22n. |A^*|;\le;2.

---

5. 小结

• 每个子代数元素 ↔ 一个布尔函数
• 布尔函数数目 = 22n2^{2n}
• 子代数元素数 ≤ 布尔函数数
• 故 ∣A∗∣≤22n\bigl|A^*\bigr|\le 2^{2n}

如果还有哪里不清楚，或想看具体的真值表示例，请告诉我！