Home 计算机 数字电路

# 定义

布尔代数 (B,∧,∨,¬,0,1)(B, \land, \lor, \lnot, 0, 1) 是定义在集合 B={0,1}B = \{0, 1\} 上的代数结构
其带有一个一元运算 NOT 以及两个二元运算 AND 和 OR
通常记运算为

  • a∧ba \land b 表示 aa AND bb
  • a∨ba \lor b 表示 aa OR bb
  • a‾\overline a 表示 NOT aa

且运算满足以下条件

  • BB 对所有运算封闭
  • 结合律
    • a∧(b∧c)=(a∧b)∧ca \land (b \land c) = (a \land b) \land c
    • a∨(b∨c)=(a∨b)∨ca \lor (b \lor c) = (a \lor b) \lor c
  • 交换律
    • a∧b=b∧aa \land b = b \land a
    • a∨b=b∨aa \lor b = b \lor a
  • 分配律
    • a∧(b∨c)=(a∧b)∨(a∧c)a \land (b \lor c) = (a \land b) \lor (a \land c)
    • a∨(b∧c)=(a∨b)∧(a∨c)a \lor (b \land c) = (a \lor b) \land (a \lor c)
  • 恒等律
    • a∧1=aa \land 1 = a
    • a∨0=aa \lor 0 = a
  • 互补律
    • a∧a‾=0a \land \overline a = 0
    • a∨a‾=1a \lor \overline a = 1

基于上述定义，可以得到 Boolean 代数的一般性质

  • 吸收律
    • a∧(a∨b)=aa \land (a \lor b) = a
    • a∨(a∧b)=aa \lor (a \land b) = a
  • 幂等律
    • a∧a=aa \land a = a
    • a∨a=aa \lor a = a
  • 对偶原理
    • a∧b‾=a‾∨b‾\overline{a \land b} = \overline a \lor \overline b \quad
    • a∨b‾=a‾∧b‾\overline{a \lor b} = \overline a \land \overline b \quad

示例
对任意集合 UU，令幂集 P(U)\mathcal{P}(U) 上的运算定义为

  • A∧B=A∩BA \land B = A \cap B
  • A∨B=A∪BA \lor B = A \cup B
  • A‾=U−A\overline A = U - A

定义 0:=∅0 := \emptyset，1:=U1 := U
则可以得到最经典的 Boolean 代数结构 (P(U),∧,∨,⋅‾,0,1)(\mathcal{P}(U), \land, \lor, \overline{\cdot}, 0, 1)

由此，可以将 Boolean 代数在一般代数结构上分类

命题
任意有限 Boolean 代数同构于某个幂集 P(U)\mathcal{P}(U)

证明

设有限 Boolean 代数为 (B,∧,∨,⋅‾,0,1)(B, \land, \lor, \overline{\cdot}, 0, 1)
定义 UU 为 BB 中所有原子元的集合
则可以构造同构映射 f:B→P(U)f: B \to \mathcal{P}(U)，使得对任意 b∈Bb \in B，f(b)f(b) 为所有小于等于 bb 的原子元的集合
□\square

# 对偶

定义
给定一个 Boolean 表达式 PP，定义其 对偶 (Dual) 「双対」 表达式 PdP^d 为

  • 将所有的 ∧\land 与 ∨\lor 互换
  • 将所有的 00 与 11 互换

对于对偶，两次的对偶会回到原表达式，这是名字 Dual 的来源

示例

  • P=x∨0⟹Pd=x∧1P = x \lor 0 \implies P^d = x \land 1
  • P=(x∧y)‾∨z⟹Pd=(x∨y)‾∧zP = \overline{(x \land y)} \lor z \implies P^d = \overline{(x \lor y)} \land z \quad
  • P=xy‾∨x‾yz‾⟹Pd=x+y⋅(x+z)P = x \overline y \lor \overline x y \overline z \implies P^d = x + y \cdot (x + z)