Home 计算机 数字电路

# 逻辑函数

设有 nn 个 Boolean 变量 x1,x2,…,xnx_1, x_2, \ldots, x_n，则一个 逻辑函数 是一个映射

f:Bn→Bf: B^n \to B

即，对于 nn 个二值输入，其返回一个二值输出

逻辑函数可以用多种方式等价表达，将在接下来讲解

  • Boolean 代数表达式
  • 真值表
  • 极大项与极小项组合
  • Karnaugh 图

显然，对于 nn 个变量的逻辑函数，其可能的输入组合数为 2n2^n，这意味着其真值表有 2n2^n 行
但是实际上，大部分逻辑函数并不需要穷举所有输入组合来表达，对于不关注的结果，可以在真值表中使用 * 或 - (don't care) 来表示
通过这种方式，可以实现逻辑函数的简化

示例
对于真值表

xyz = f(x, y)
001
01*
100
110

如果 ∗* 的值对计算毫无影响，可以任意选取，那么

  • 令 f(0,1)=0f(0, 1) = 0，则逻辑函数为 f(x,y)=x‾y‾f(x, y) = \overline x \overline y
  • 令 f(0,1)=1f(0, 1) = 1，则逻辑函数为 f(x,y)=x‾f(x, y) = \overline x

# 包含关系

对于两个逻辑函数 F,GF, G，令

  • AA 为 F=1F=1 的逆像
  • BB 为 G=1G=1 的逆像

则

F包含G⟺F≥G⟺B⊂AF \text{ 包含 } G \iff F \geq G \iff B \subset A

当 FF 包含 GG 时

  • F‾G=0\overline F G = 0
  • F+G‾=1F + \overline G = 1

通过真值表可以简单判断包含关系
如果说 FF 包含了 GG，也就是 F≥GF \geq G，那么意味着

  • F=0F=0 时，G=0G=0
  • G=1G=1 时，F=1F=1

可以直观里面为点集拓扑中连续映射的逆像性质

显然，包含关系作为一种偏序关系，满足自反性、反对称性和传递性
自然地，根据偏序关系可以定义极大极小关系 minimal element 和 maximal element

  • F≠1F \neq 1 为极大 ⟺\iff 对任意 GG，若 G≥FG \geq F 则 G=FG = F
  • F≠0F \neq 0 为极小 ⟺\iff 对任意 GG，若 G≤FG \leq F 则 G=FG = F

在布尔函数的偏序中，这些 minimal element 就是最小项（minterm）

# 极小项

称去掉 01 后的 SS 中，仅针对特定输入为 1 的逻辑函数为 极小项 (Minterm) 「最小項」，记为 mim_i，其中 ii 为该输入的十进制表示

对于三变量函数，由于输入组合共有 23=82^3 = 8 种，因此共有 8 个极小项

极小项不依赖于具体的逻辑函数，其定义与任意 nn 维 Boolean 空间，成为类似 原子 的存在
所以，任意逻辑函数均可以表示为极小项的组合

对于任意逻辑函数，取其取值为 1 的所有输入组合所对应的极小项，将这些极小项进行逻辑或运算，即可得到该逻辑函数的表达式，这称为该逻辑函数的 和项标准式 (Sum of Minterms)

并且，极小项可以仅靠 AND 和 NOT 实现，因此添加 OR 运算后，和项标准式也称为 NOT-AND-OR 形式

示例
设有逻辑函数 f(x,y,z)f(x, y, z)，其真值表如下，给出对应输入的极小项

xxyyzzf(x,y,z)f(x, y, z)极小项
00000000x‾y‾z‾=m0\overline x \overline y \overline z = m_0
00001111x‾y‾z=m1\overline x \overline y z = m_1
00110011x‾yz‾=m2\overline x y \overline z = m_2
00111100x‾yz=m3\overline x y z = m_3
11000000xy‾z‾=m4x \overline y \overline z = m_4
11001111xy‾z=m5x \overline y z = m_5
11110011xyz‾=m6x y \overline z = m_6
11111100xyz=m7x y z = m_7

将 FF 进行和项标准式表达

解

取值为 1 的输入组合对应的极小项 m1,m2,m5,m6m_1, m_2, m_5, m_6，则

f(x,y,z)=m1+m2+m5+m6=x‾y‾z+x‾yz‾+xy‾z+xyz‾\begin{aligned} f(x, y, z) &= m_1 + m_2 + m_5 + m_6 \\ &= \overline x \overline y z + \overline x y \overline z + x \overline y z + x y \overline z \end{aligned}

# 极大项

同理
称去掉 10 后的 SS 中，仅针对特定输入为 0 的逻辑函数为 极大项 (Maxterm) 「最大項」，记为 MiM_i，其中 ii 为该输入的十进制表示

对于任意逻辑函数，取其取值为 0 的所有输入组合所对应的极大项，将这些极大项进行逻辑与运算，即可得到该逻辑函数的表达式，这称为该逻辑函数的 积项标准式 (Product of Maxterms)

与极小项 不同 的是，极大项仅靠 OR 和 NOT 实现，因此添加 AND 运算后，积项标准式也称为 NOT-OR-AND 形式

以下给出重要示例（异或）的表达式
异或函数 x⊕y:=x‾y+xy‾x \oplus y := \overline x y + x \overline y 会非常常见

示例
设有逻辑函数 f(x,y)f(x, y)，其真值表如下，给出对应输入的极小项与极大项

xxyyf(x,y)f(x, y)极小项极大项
000000x‾y‾=m0\overline x \overline y = m_0x+y=M0x + y = M_0
001111x‾y=m1\overline x y = m_1x+y‾=M1x + \overline y = M_1
110011xy‾=m2x \overline y = m_2x‾+y=M2\overline x + y = M_2
111100xy=m3x y = m_3x‾+y‾=M3\overline x + \overline y = M_3

将 FF 分别进行和项标准式与积项标准式表达

解

取值为 1 的输入组合对应的极小项 m1,m2m_1, m_2，则

f(x,y)=m1+m2=x‾y+xy‾\begin{aligned} f(x, y) &= m_1 + m_2 \\ &= \overline x y + x \overline y \end{aligned}

取值为 0 的输入组合对应的极大项 M0,M3M_0, M_3，则

f(x,y)=M0M3=(x+y)(x‾+y‾)\begin{aligned} f(x, y) &= M_0 M_3 \\ &= (x + y)(\overline x + \overline y) \end{aligned}

# 与非门

与非门是泛用逻辑门，可以实现任意逻辑函数
定义

NAND(x,y):=x∧y‾\text{NAND}(x, y) := \overline{ x \land y }

真值表

xxyyx∧yx \land yNAND(x,y)\text{NAND}(x, y)
00000011
00110011
11000011
11111100

通过与非门

  • NOT 门：x‾=NAND(x,x)\overline x = \text{NAND}(x, x)
  • AND 门：x∧y=NAND(x,y)‾x \land y = \overline{\text{NAND}(x, y)}
  • OR 门：x∨y=NAND(x‾,y‾)x \lor y = \text{NAND}(\overline x, \overline y)

# Shannon 展开

设有逻辑函数 F(x1,x2,…,xn)F(x_1, x_2, \ldots, x_n)，则对于任意变量 xix_i，都有

F=xiFxi+x‾iFxi‾F = x_i F_{x_i} + \overline x_i F_{\overline{x_i}}

其中

  • Fxi:=F(x1,…,xi−1,1,xi+1,…,xn)F_{x_i} := F(x_1, \ldots, x_{i-1}, 1, x_{i+1}, \ldots, x_n)
  • Fxi‾:=F(x1,…,xi−1,0,xi+1,…,xn)F_{\overline{x_i}} := F(x_1, \ldots, x_{i-1}, 0, x_{i+1}, \ldots, x_n)

称为 Shannon 展开式

实际上，Shannnon 展开可以理解为在点 xi=1x_i = 1 和 xi=0x_i = 0 处对函数进行 分段，然后通过逻辑或将两段连接起来

F(x1,…,xi⏟choice,…,xn)=xi⏟trueF(x1,…,1⏟true,…,xn)+x‾i⏟falseF(x1,…,0⏟false,…,xn)F(x_1, \ldots, \underbrace{x_i}_{\text{choice}}, \ldots, x_n) = \underbrace{x_i}_{\text{true}} F(x_1, \ldots, \underbrace{1}_{\text{true}}, \ldots, x_n) + \underbrace{\overline x_i}_{\text{false}} F(x_1, \ldots, \underbrace{0}_{\text{false}}, \ldots, x_n)

# 单极与单调

令逻辑函数 F(x1,x2,…,xn)F(x_1, x_2, \ldots, x_n)
若对某变量 xix_i，有

xi≤yi⟹F(x1,…,xi,…,xn)≤F(x1,…,yi,…,xn)x_i \leq y_i \implies F(x_1, \ldots, x_i, \ldots, x_n) \leq F(x_1, \ldots, y_i, \ldots, x_n)

则称 FF 对变量 xix_i 是正的
也就是说，把 xix_i 从 0 变为 1，函数值不会下降
若 FF 对所有变量均为正的，则称 FF 是单调函数 (Monotone Function)

另外，若

  • F(x1,…,0i,…,xn)≤F(x1,…,1i,…,xn)F(x_1, \ldots, 0_i, \ldots, x_n) \leq F(x_1, \ldots, 1_i, \ldots, x_n) 对 xix_i 正
  • F(x1,…,1i,…,xn)≤F(x1,…,0i,…,xn)F(x_1, \ldots, 1_i, \ldots, x_n) \leq F(x_1, \ldots, 0_i, \ldots, x_n) 对 xix_i 负

则称 FF 对变量 xix_i 是单极 (Unate) 的
若 FF 对所有变量均为单极的，则称 FF 是单极函数

单调⟹单极\text{单调} \implies \text{单极}

# 对偶函数

对于逻辑函数 F(x1,x2,…,xn)F(x_1, x_2, \ldots, x_n)，定义其对偶函数为

Fd(x1,x2,…,xn):=F(x1‾,x2‾,…,xn‾)‾F^d(x_1, x_2, \ldots, x_n) := \overline{F(\overline{x_1}, \overline{x_2}, \ldots, \overline{x_n})}

即，将所有变量取反后计算函数值，再对结果取反

# 邻域关系

对于逻辑式 AA
若 xAxA 与 x‾A\overline x A 被 AA 包含，那么意味着其可以被合并为 AA

对于两个长度相同的二进制串 x=(x1,x2,…,xn)x = (x_1, x_2, \ldots, x_n) 与 y=(y1,y2,…,yn)y = (y_1, y_2, \ldots, y_n)
定义其 Hamming 距离为

d(x,y):=∣{i∣xi≠yi,1≤i≤n}∣d(x, y) := |\{ i \mid x_i \neq y_i, 1 \leq i \leq n \}|

也就是逐位比较，不同的位数的个数
其满足度量公理，称为真正的距离