布尔函数的表示与化简

与初等代数变量的取值是数字不同，布尔代数中，变量的值只能是真值 真 或 假 。这些值是由 位 表示，写作 1 和 0。它们和整数 1 和 0 并不一样，1 和 0 在这里仅仅是符号，而不是数字。

布尔代数的基本运算包括

• AND，写作 x ∧ y，当且仅当 x = y = 1 时 x ∧ y = 1，否则为 0。
• OR，写作 x ∨ y，当且仅当 x = y = 0 时 x ∨ y = 0，否则为 1。

• NOT，写作 ¬，当 x = 0 时 ¬x = 1，当 x = 1 时 ¬x = 0。

  它们的运算规则也可以用真值表来表示：

  x	y	x ∧ y	x ∨ y
  0	0	0	0
  1	0	0	1
  0	1	0	1
  1	1	1	1

  x	¬x
  0	1
  1	0

如果真值 0 和 1 被当作整数的话，这些运算也可以表示为普通的运算：

\(x ∧ y = xy = min(x, y)\)

\(x ∨ y = x + y - xy = max(x, y)\)

\(¬x = 1 - x\)

你可能会认为只有非运算和与或两者之一才是基础的，因为可以通过非运算和与运算导出或运算，也可以通过非运算和或运算导出与运算：

\(x ∧ y = ¬(¬x ∨ ¬y )\)

\(x ∨ y = ¬(¬x ∧ ¬y )\)

这三个运算被称作基础运算，”基础“意味着其他的布尔运算可以通过它们的组合而得到。例如：异或，同或

\(x ⊕ y = (x ∨ y) ∧ ¬(x ∧ y) = (x ∧ ¬y) ∨ (¬x ∧ y)\)

\(x ≡ y = ¬(x ⊕ y) = (x ∧ y) ∨ (¬x ∧ ¬y)\)

若将 ∨ 与加匹配，∧ 与乘匹配，布尔运算满足许多普通的代数运算规律：

结合律：\(x ∨ (y ∨ z) = (x ∨ y) ∨ z, x ∧ (y ∧ z) = (x ∧ y) ∧ z\)

交换律：\(x ∧ y = y ∧ x, x ∨ y = y ∨ x\)

分配律：\(x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)\)

诸如 x + 0 = x，x × 1 = x，x × 0 = 0 也有相似的规律

\(x ∨ 0 = x, x ∧ 1 = x, x ∧ 0 = 0\)

除了普通代数中的运算律外，布尔代数也有它独有的运算律：

∨ 的吸收律： \(x ∨ 1 = 1\)

∨ 和 ∧ 的幂等律： \(x ∨ x = x,x ∧ x = x\)

组合吸收律：\(x ∧ (x ∨ y) = x, x ∨ (x ∧ y) = x\)

另一种分配律：\(x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)\)

互补律： \(x ∧ ¬x = 0,x ∨ ¬x = 1\)

De Morgan：\(¬x ∧ ¬y = ¬(x ∨ y), ¬x ∨ ¬y = ¬(x ∧ y)\)

逻辑表达式由逻辑变量和逻辑运算符号组成，用于表示变量之间逻辑关系。常用的逻辑表达式有与或表达式，或与表达式与非与非表达式，或非或非表达式，与或非表达式。

与或表达式指两个或多个与项通过或连接在一起，例如：

\(F = AB + A\overline{C}D\)

或表达式指两个或多个或项通过与连接在一起，比如：

\(F = (A + B)(A + C + \overline{D})\)

与非与非指对两个或多个与项分别进行非运算并通过与运算连接，再对整个项进行非运算，例如：

\(F = \overline{(\overline{AB})(\overline{CD})}\)

或非或非指对两个或多个或项分别进行非运算并通过或运算连接，再对整个项进行非运算，例如：

\(F = \overline{\overline{A + B} + \overline{C + D}}\)

与或非表达式指两个或多个与项通过或运算连接，并对整个式子进行非运算，例如：

\(F = \overline{AB + CD}\)

除了上面提到的几种表达式，还需要注意两种标准表达式：标准与或表达式和标准或与表达式。

真值表是用来反映变量所有取值集合及对应函数值得表格。

例如， 布尔函数 \(F = AB + AC\) 对应的真值表是：

卡诺图 （Karnaugh map）是一种简化布尔代数表达式的方法。它是对 Edward Veith 的 Veitch chart 的改进。Veitch chart 因此以 Marquand-Veitch diagrams 这个名字而为人所知，卡诺图也叫 Karnaugh-Veitch 图（KV maps）。

卡诺图利用了人类的模式识别能力（humans' pattern-recognition capability）来消除多余的计算。它也可以快速消除潜在的 竞争冒险 （Race hazards） 。

卡诺图是一个二维表格，在卡诺图中，由行和列两组变量对应的每一个小方块都代表了逻辑函数的一个最小项，变量取值为 1 表示原变量，变量取值为 0 表示反变量。卡诺图的变量排布顺序是格雷码顺序而不是自然数顺序，这样就保证了相邻变量组合的邻接性。例如变量组合 AB 在卡诺图中对应的顺序应该是 00 01 11 10，而不是 00 01 10 11。直观上看，格雷码的每一个数的后一位都与后一个数的前一位相等，这就好像是最简单的贪吃蛇游戏，从屏幕的上面钻出去了，又从屏幕的下面进来。

还是以 \(F = AB + AC\) 为例，它的卡诺图表示：

这张图片能够很好的说明卡诺图中变量组合的邻接性质：（图片来源：维基百科）

图中的四个黑点尽管在卡诺图的四个角上，但是它们是邻接的。

这张图演示了动态变化的效果（图片来源：维基百科）

由逻辑门电路符号构成的，用来表示逻辑变量之间关系的图形称为逻辑电路图，简称逻辑图。

常见的逻辑门电路符号有 是门 （Yes gate）， 非门 ， 与门 ， 或门 ， 与非门 ， 或非门 ， 同或门 ， 异或门 。

buffer	not	and	or
NAND	NOR	XOR	XNOR

\(F=AB+AC\) 的逻辑图表示为：（没有现成的图片）

       +----+
B -----| OR |          +-----+
C -----|    |----------| AND |------- F
       +----+     +----|     |
                  |    +-----+
A ----------------+

波形图绘制了输入输出之间不同时刻的电平变化，也可以表示输入端在不同逻辑信号作用下所对应的输出信号之间的逻辑关系。

还是以 \(F = AB + AC\) 为例，其波形图可表示为：

                  --- --- --- ---          1
A --- --- --- ---                          0
          --- ---         --- ---          1
B --- ---         --- ---                  0
      ---     ---     ---     ---          1
C ---     ---     ---     ---              0
                      --- --- ---          1
F --- --- --- --- ---                      0

公式法就是反复利用布尔代数中的基本公式和常用公式，消去与或逻辑函数式中多余的乘积项和每个乘积项中多余的变量，以求得到逻辑函数表达式的最简形式。布尔运算的优先级为：非 > 与 > 或。公式法没有固定的步骤。

常用的公式有：

\(AB + A\overline{B} = A\)

\(A + AB = A\)

\(A + \overline{A}B = A+B\)

\(AB + \overline{A}C + BC = AB + \overline{A}C\)

\(\overline{A\overline{B} + \overline{A}B} = \overline{A}·\overline{B} +AB\)

在卡诺图中，凡邻接的两个小方格具有逻辑相邻性，即它们只有一个变量的取值不同，其他变量取值相同。逻辑相邻的最小项相或时，可以使用 \(AB + A\overline{B}=A\) 进行合并。

• 两个相邻小方格可以合并为一个乘积项，且消去一个变量。
• 四个相邻的小方格可以合并为一个乘积项，并消去两个变量。
• \(2^k, (k \in N)\) 个相邻的小方格可合并为一个乘积项，且消去 k 个变量。

具体步骤：

1. 将相邻的 N (\(N = 2^k\)) 个为 1 的小方格圈在一起，画图时要将尽可能多的小方块圈在一起。一般先画大圈，最后圈孤立的小方格。
2. 所画的圈内必须包含一个只属于该圈的 1，否则会得到冗余项。
3. 所画的圈必须是矩形。

例子：（图片来源：维基百科）

逻辑函数 \(F = \sum m(6, 8, 9, 10, 11, 12, 13, 14)\) 的卡诺图如图所示，红色圈和绿色圈分别圈了四个 1，故可分别消去两个变量，蓝紫色圈内有两个 1，可消去一个变量。

红色部分消去 BD 得到 \(A\overline{C}\) ，绿色部分消去 CD 得到 \(A\overline{B}\) ，蓝色部分消去 A 得到 \(BC\overline{D}\) 。

最后得到最简表达式：\(F = A\overline{C}+A\overline{B}+BC\overline{D}\) 。

如果要求反函数，圈 0 而不是 1，并消去相应的项即可。

3.2.1. 具有无关项时的情况

卡诺图可以轻易化简带有无关项的逻辑函数。

无关项大致分为两种情况，它们分别是：

• 输入变量的某些取值组合现实中根本不存在，或者某些取值存在，但对函数的输出没有任何影响。这类取值组合称为任意项。
• 输入变量的某些取值集合是存在的，但是逻辑函数不允许它的出现，如果出现，它可能会导致逻辑函数输出混乱。这类取值组合称为约束项。

无关项在卡诺图中用 \(X\) 或 \(\varnothing\) 表示。由于无关项取值对函数输出没有影响，故进行化简时，可以根据具体情况将无关项的取值看作 0 或 1 来进行进一步的化简。

例子如下：（图片来源：维基百科）

图中的 \(AB\overline{C}D\) 是一个无关项，它的出现使得红色矩形得以完整的形成。

当逻辑函数中的项过多时，公式法化简显得有些力不从心，卡诺图仅对于变量个数小于 4 的情况比较有效，随着变量个数的增多，卡诺图的直观性越来越差。计算机化简是最好的选择。