布尔代数与布尔函数

本篇把布尔表达式作为函数来研究：怎样表示、证明恒等式，以及化简实现。二元布尔代数连接了命题真值表与数字逻辑。命题和量词的基础用法见数学基础，形式推导和推理算法则在后续独立章节中展开。

这里主要研究二元布尔代数，不试图完整分类抽象布尔代数。基本运算是与、或、补，异或属于派生运算。本篇回顾真值表，是为了建立代数等价与函数表示，不再重复基础篇的证明方法训练。

布尔表达式与真值表

布尔代数之所以叫“代数”，是因为它和普通代数一样，有一套对任意取值都成立的运算律。先回顾数的运算律，再把同样的思路搬到真值上。列全输入组合后得到的表，就是真值表。

代数运算的性质

对普通的数 $x$、$y$、$z$，加减乘除服从下表中的定律。

定律	加法形式	乘法形式
单位元	$x + 0 = x$	$x \cdot 1 = x$
零元		$x \cdot 0 = 0$
逆元	$x + (-x) = 0$	$x \cdot x^{-1} = 1$（$x \neq 0$）
交换律	$x + y = y + x$	$x \cdot y = y \cdot x$
结合律	$(x + y) + z = x + (y + z)$	$(x \cdot y) \cdot z = x \cdot (y \cdot z)$
分配律		$x \cdot (y + z) = x \cdot y + x \cdot z$

普通代数定律

这里的 $x$、$y$、$z$ 和程序里的变量一样，定律对它们的一切允许取值都成立。代数等式之所以能证，正是因为这些定律可以反复使用。以 $(-1)\times(-1)$ 为例：很多人脱口而出答案是 $1$，但为什么？下面只用表中的定律来证。

例证明 $(-1)(-1)=1$

证明 $(-1)\times (-1) = 1$。

证明

$$\begin{aligned} (-1)\times(-1) &= ((-1)\times(-1))+0 \\ &= ((-1)\times(-1))+((-1)+1) \\ &= (((-1)\times(-1)+(-1))+1) \\ &= (((-1)\times(-1)+((-1)\times 1))+1) \\ &= ((-1)\times((-1)+1))+1 \\ &= ((-1)\times 0)+1 \\ &= 0+1 \\ &= 1+0 \\ &= 1. \end{aligned}$$

表里加法单位元只写成 $x+0=x$，所以要把 $0+1$ 换成 $1+0$，再用一次加法交换律，才能套上已知结论。

当然，平时算 $(-1)\times(-1)$ 不必每次都写这么长。真正要记住的是：数学结论不能停留在“负负得正”这类口诀上，必须能给出可核对、可重复的证明。

布尔表达式与真值表

为什么布尔代数还要先翻一遍小学算术？因为后面证明布尔等式的方法完全一样。先引入布尔值及其运算。

定义布尔值

在数学和计算机科学里，布尔值是布尔域 $B$ 中的元素，可写成

$$\mathbb{B} = \{0, 1\}$$

其中 $0$ 表示假，$1$ 表示真。

这和第一章里命题的真假是同一件事：在给定条件下成立就取真，不成立就取假。布尔值是布尔表达式的取值基础，为变量给定取值后，布尔表达式才能求得一个布尔值；赋值之前，它通常表示一个函数，而不是常量。

定义布尔代数

布尔代数在布尔值上定义与、或、非、异或等运算，规定如下。

• 与（$\land$）：两个运算元都为真时结果为真，否则为假。
• 或（$\lor$）：至少一个运算元为真时结果为真，否则为假。
• 非（$\lnot$）：一元运算，真变假、假变真。
• 异或（$\oplus$）：两个运算元不同时结果为真，相同时为假。

后面还会引入更多派生运算。

在程序里，布尔值决定条件语句和循环是否执行；在硬件里，它们对应门电路的电平。下面用真值表列出这些基本运算：左列是输入组合，右列是输出。

A	$\neg \textbf{A}$
F	T
T	F

基本布尔运算的真值表

A	B	$\textbf{A} \land \textbf{B}$
F	F	F
F	T	F
T	F	F
T	T	T

基本布尔运算的真值表

A	B	$\textbf{A} \lor \textbf{B}$
F	F	F
F	T	T
T	F	T
T	T	T

基本布尔运算的真值表

A	B	$\textbf{A} \oplus \textbf{B}$
F	F	F
F	T	T
T	F	T
T	T	F

基本布尔运算的真值表

不同运算的元数不必相同。$\lnot$ 只吃一个输入，其余三个都是二元运算。

布尔空间取 $B=\{0,1\}$，对应两个真值。四则运算里只有加法和乘法会在 $\{0,1\}$ 上封闭成一张小表；布尔表达式则通常由 $\lnot$、$\land$、$\lor$ 生成，其余运算都能用这三者写出来。例如

$$A\oplus B=(A\land\lnot B)\lor(\lnot A\land B).$$

$0$ 与 $1$ 的乘法表、加法表如下。

$A$	$B$	$A \times B$
0	0	0
0	1	0
1	0	0
1	1	1

$0$ 与 $1$ 的乘法与加法

$A$	$B$	$A + B$
0	0	0
0	1	1
1	0	1
1	1	1

$0$ 与 $1$ 的乘法与加法

对照前面的真值表就会发现：这两张表正是 $\land$ 和 $\lor$ 的真值表。布尔加法在这里取的是 $1+1=1$，不是普通算术里的 $2$。

布尔恒等式

刚才写过 $A \oplus B= (A \land \lnot B) \lor(\lnot A \land B)$。右端不能直接套 $\lor$ 的两行真值表读出答案，必须按子表达式逐步填表。

$A$	$B$	$\neg B$	$A \land \neg B$	$\neg A$	$\neg A \land B$	$(A \land \neg B) \lor (\neg A \land B)$
F	F	T	F	T	F	F
F	T	F	F	T	T	T
T	F	T	T	F	F	T
T	T	F	F	F	F	F

$(A \land \neg B) \lor (\neg A \land B)$ 的真值表

用同样的办法可以给更复杂的表达式造表。左右两端各自列表、逐行相同，就证明了一条恒等式。下面这些是最常用的基本布尔恒等式。

恒等式	与形式	或形式
幂等律	$x \cdot x = x$	$x + x = x$
单位律	$x \cdot 1 = x$	$x + 0 = x$
支配律	$x \cdot 0 = 0$	$x + 1 = 1$
补元律	$x \cdot \lnot x = 0$	$x + \lnot x = 1$
双重否定律	$\lnot(\lnot x) = x$	$\lnot(\lnot x) = x$
交换律	$x \cdot y = y \cdot x$	$x + y = y + x$
结合律	$x \cdot (y \cdot z) = (x \cdot y) \cdot z$	$x + (y + z) = (x + y) + z$
分配律	$x \cdot (y + z) = (x \cdot y) + (x \cdot z)$	$x + (y \cdot z) = (x + y) \cdot (x + z)$
德摩根律	$\lnot(x + y) = \lnot x \cdot \lnot y$	$\lnot(x \cdot y) = \lnot x + \lnot y$
吸收律	$x \cdot (x + y) = x$	$x + (x \cdot y) = x$

基本布尔恒等式

注怎样读这些恒等式

如果代数写法看着别扭，就把 $x$、$y$、$z$ 换成 $A$、$B$、$C$，把 $0/1$ 换成假/真，把 $+$ 读成 $\lor$，把 $\times$ 读成 $\land$。

这些定律和普通代数定律地位相当：化简复杂表达式时几乎步步都要用。本节习题会要求用真值表核对其中几条。对某一条有疑问，就把左右两端分别列表，行行对照即可。

表还没列全。两条与派生运算有关的定律暂时留到下一小节，其中一条已经出现过，就是 $\oplus$。

有了基本定律，可以推出更有用的定理。化简时常用的一条是合意定理，也叫冗余定理。

定理合意定理

合意定理删掉布尔表达式里的冗余项。它和前面的恒等式一样，有或形式与与形式。对布尔变量 $x$、$y$、$z$，

$$xy\lor\bar{x}z\lor yz=xy\lor\bar{x}z,$$

这等价于

$$(x\lor y)(\bar{x}\lor z)(y\lor z)=(x\lor y)(\bar{x}\lor z).$$

证明

或形式可以由下面的计算得到：

$$\begin{aligned} xy\lor\bar{x}z\lor yz &=xy\lor\bar{x}z\lor(x\lor\bar{x})yz \\ &=xy\lor\bar{x}z\lor xyz\lor\bar{x}yz \\ &=(xy\lor xyz)\lor(\bar{x}z\lor\bar{x}yz) \\ &=xy(1\lor z)\lor\bar{x}z(1\lor y) \\ &=xy\lor\bar{x}z. \end{aligned}$$

改成加法记号，同一条恒等式是

$$\begin{aligned} xy + \overline{x}z + yz &= xy + \overline{x}z + (x + \overline{x})yz \\ &= xy + \overline{x}z + xyz + \overline{x}yz \\ &= (xy + xyz) + (\overline{x}z + \overline{x}yz) \\ &= xy(1 + z) + \overline{x}z(1 + y) \\ &= xy + \overline{x}z. \end{aligned}$$

派生布尔运算

定义派生布尔运算

由基本运算可以定义下列派生运算。

• 实质蕴涵：$x \rightarrow y = \lnot x \lor y$
• 实质双条件：$x \leftrightarrow y = (x \land y) \lor (\lnot x \land \lnot y)$
• 异或：

$$x \oplus y = \lnot(x \leftrightarrow y) = (x \lor y) \land (\lnot x \lor \lnot y) = (x \land \lnot y) \lor (\lnot x \land y)$$

它们的真值表如下。

$x$	$y$	$x \rightarrow y$	$x \leftrightarrow y$	$x \oplus y$
0	0	1	1	0
1	0	0	0	1
0	1	1	0	1
1	1	1	1	0

实质蕴涵、双条件与异或在全部输入上的真值

$\rightarrow$ 满足 $x \rightarrow x = 1$：只要 $x=y$，蕴涵就为真。派生运算以及蕴涵相关的恒等式，是本章要补上的最后一批布尔恒等式。

1. 实质蕴涵（$\rightarrow$）。读作“若 $x$ 则 $y$”，或“$x$ 蕴涵 $y$”。只有 $x$ 真且 $y$ 假时，$x \rightarrow y$ 为假；其余情形都为真。$x$ 为假时，无论 $y$ 取什么，蕴涵都为真，这一点常常反直觉。用基本运算写就是 $\lnot x \lor y$。

2. 实质双条件（$\leftrightarrow$）。也叫逻辑等价：当且仅当 $x$ 与 $y$ 同真或同假时为真。读作“$x$ 当且仅当 $y$”。写成基本运算是 $(x \land y) \lor (\lnot x \land \lnot y)$。

3. 异或（$\oplus$）。$x$ 与 $y$ 一真一假时为真。它和普通或的差别在于：两者都真时异或为假。写成 $(x \land \lnot y) \lor (\lnot x \land y)$。

有了这些运算和恒等式，不必每次都画真值表，可以直接用代数变形证明更多定理。下面几条就用这个办法。

例用前面的恒等式表证明下列等式

用前面给出的恒等式表证明下列等式。

表达式	名称
$(x \rightarrow \text{False}) = (\lnot x)$	把 $\lnot$ 写成 $\rightarrow$
$(x \rightarrow y) = (\lnot y \rightarrow \lnot x)$	逆否
$((x \rightarrow y) \land (x \rightarrow z)) = (x \rightarrow (y \land z))$	蕴涵对合取的分配
$((x \rightarrow y) \land (\lnot x \rightarrow y)) = y$	归谬
$(x \rightarrow (\lnot x)) = (\lnot x)$	矛盾

证明

把 $\lnot$ 写成 $\rightarrow$，只需用 $\rightarrow$ 的定义：

$$x\rightarrow\text{ False}= \lnot x \lor \text{False} = \lnot x + 0 = \lnot x,$$

最后一步是或的单位律。

逆否命题说 $(x \rightarrow y)$ 与 $(\lnot y \rightarrow \lnot x)$ 逻辑等价：

$$\begin{aligned} x \rightarrow y &\equiv \lnot x \lor y \\ &\equiv y \lor \lnot x \\ &\equiv \lnot y \rightarrow \lnot x. \end{aligned}$$

中间用了或的交换律。这正说明第一章里“逆否证明”为什么合法。

蕴涵对合取的分配，要证明 $(x \rightarrow y) \land (x \rightarrow z)$ 等价于 $x \rightarrow (y \land z)$：

$$\begin{aligned} (x \rightarrow y) \land (x \rightarrow z) &\equiv (\lnot x \lor y) \land (\lnot x \lor z) \\ &\equiv \lnot x \lor (y \land z) \\ &\equiv x \rightarrow (y \land z). \end{aligned}$$

归谬恒等式说 $(x \rightarrow y) \land (\lnot x \rightarrow y)$ 等价于 $y$：

$$\begin{aligned} (x \rightarrow y) \land (\lnot x \rightarrow y) &\equiv (\lnot x \lor y) \land (x \lor y) \\ &\equiv y \lor (x \land \lnot x) \\ &\equiv y \lor \text{False} \\ &\equiv y. \end{aligned}$$

矛盾恒等式说 $x \rightarrow (\lnot x)$ 等价于 $\lnot x$：

$$\begin{aligned} x \rightarrow (\lnot x) &\equiv \lnot x \lor (\lnot x) \\ &\equiv \lnot x. \end{aligned}$$

注布尔表达式的两种记法

本章有时用逻辑记号，有时用代数加减乘。两种都合法，按习惯选用即可。

回头看整段推导，其实就是在化简布尔表达式：定律用熟了，就不必反复列表。

习题

练习用表 1 证明 $(x+x)=(2\times x)$

利用前面的普通代数定律表，以及 $1+1=2$，证明 $(x+x)=(2\times x)$。

证明

$$\begin{aligned} ( 2\times x) & =( 1+1) \times x \\ & = 1\times x+1\times x \\ & =x+x. \end{aligned}$$

第一步用 $1+1=2$，第二步用分配律，第三步用乘法单位元。

练习证明 $((-1)\times x)+x=0$

用定律表证明 $((-1)\times x)+x=0$。

证明

$$\begin{aligned} (( -1) \times x) +x & =x( -1+1) \\ & = x\times 0 \\ & =0. \end{aligned}$$

依次用分配律、加法逆元、乘法零元。

练习证明 $(x+(((-1)\times (x+y))+z)) + y =z$

证明

$$(x+(((-1)\times (x+y))+z)) + y =z,$$

可以用上一题的结论。

证明

为了看清层次，用方括号和花括号区分括号层。

$$\begin{aligned} & \{x+[((-1) \times ( x+y)) +z]\} +y \\ & =\{x+[(( -1) \times x) +(( -1) \times y)] +z\} +y \\ & =\{x+(( -1) \times x) +[(( -1) \times y) +z]\} +y \\ & =\{(( -1) \times x) +x+\ [(( -1) \times y) +z]\} +y \\ & =0+\{[(( -1) \times y) +z] +y\} \\ & =\{[(( -1) \times y) +z] +y\} +0 \\ & =\{[(( -1) \times y) +z] +y\} \\ & =(( -1) \times y) +( z+y) \\ & =( z+y) +(( -1) \times y) \\ & =z+[ y+(( -1) \times y)] \\ & =z+[(( -1) \times y) +y] \\ & =z+0 \\ & =z. \end{aligned}$$

用到的依次是分配律、加法结合律、加法交换律、上一题结论、加法单位元，以及再次使用结合律和交换律。

练习用真值表验证德摩根律

用真值表说明德摩根律成立。

证明

德摩根第一定律：$\lnot (A \land B) = \lnot A \lor \lnot B$。

$A$	$B$	$A \land B$	$\lnot (A \land B)$	$\lnot A \lor \lnot B$
0	0	0	1	1
0	1	0	1	1
1	0	0	1	1
1	1	1	0	0

德摩根第二定律：$\lnot (A \lor B) = \lnot A \land \lnot B$。

$A$	$B$	$A \lor B$	$\lnot (A \lor B)$	$\lnot A \land \lnot B$
0	0	0	1	1
0	1	1	0	0
1	0	1	0	0
1	1	1	0	0

练习用真值表验证吸收律

用真值表说明吸收律成立。

证明

$x$	$y$	$x \lor y$	$x \land (x \lor y)$
T	T	T	T
T	F	T	T
F	T	F	F
F	F	F	F

$x$	$y$	$x \land y$	$x \lor (x \land y)$
T	T	T	T
T	F	F	T
F	T	F	F
F	F	F	F

练习写出 $x\lor ((\lnot y)\land (\lnot z))$ 的真值表

写出 $\displaystyle x\lor (( \lnot y) \land ( \lnot z))$ 的真值表。

三个变量时，输入组合有 $2^3=8$ 种。

$x$	$y$	$z$	$\lnot y$	$\lnot z$	$(\lnot y) \land (\lnot z)$	$x \lor ((\lnot y) \land (\lnot z))$
0	0	0	1	1	1	1
0	0	1	1	0	0	0
0	1	0	0	1	0	0
0	1	1	0	0	0	0
1	0	0	1	1	1	1
1	0	1	1	0	0	1
1	1	0	0	1	0	1
1	1	1	0	0	0	1

$x \lor ((\lnot y) \land (\lnot z))$ 的真值表

练习证明四个表达式等价并化简

给定

$$\begin{aligned} 1. &\quad (x \rightarrow y) \land (\lnot x \rightarrow \lnot y) \\ 2. &\quad ((\lnot x) \lor y) \land (x \lor (\lnot y)) \\ 3. &\quad \lnot((x \land (\lnot y)) \lor ((\lnot x) \land y)) \\ 4. &\quad \lnot((x \lor y) \land (\lnot x \lor \lnot y)), \end{aligned}$$

证明它们彼此等价，并求出共同的化简形式。

证明

$$\begin{aligned} (x \rightarrow y) \land (\neg x \rightarrow \neg y) & \equiv (\neg x \lor y) \land (x \lor \neg y) \\ & \equiv (x \lor \neg y) \land (\neg x \lor y) \\ & \equiv (x \lor \neg y) \land (y \lor \neg x). \end{aligned}$$

第一步用蕴涵的定义，后面两步分别用或、与的交换律。

$$\begin{aligned} ((\neg x) \lor y) \land (x \lor (\neg y)) & \equiv (y \lor \neg x) \land (x \lor \neg y) \\ & \equiv (x \lor \neg y) \land (y \lor \neg x). \end{aligned}$$$$\begin{aligned} \neg((x \land (\neg y)) \lor ((\neg x) \land y)) & \equiv \neg(x \land (\neg y)) \land \neg((\neg x) \land y) \\ & \equiv (\neg x \lor y) \land (x \lor \neg y) \\ & \equiv (x \lor \neg y) \land (y \lor \neg x). \end{aligned}$$

前两步都是德摩根律。

$$\begin{aligned} \neg((x \lor y) \land (\neg x \lor \neg y)) & \equiv \neg(x \lor y) \lor \neg(\neg x \lor \neg y) \\ & \equiv (\neg x \land \neg y) \lor (x \land y) \\ & \equiv (x \land y) \lor (\neg x \land \neg y) \\ & \equiv (x \lor \neg y) \land (y \lor \neg x). \end{aligned}$$

最后一步用分配律，把合取的析取写成析取的合取。四个表达式都可以化成 $(\lnot y \lor x)\land(\lnot x\lor y)$，也就是 $(y\rightarrow x)\land(x\rightarrow y)$，即 $x\leftrightarrow y$：$x$ 与 $y$ 同真或同假。

练习证明合意定理的两种形式等价

证明合意定理的两种形式等价：

$$xy\lor\bar{x}z\lor yz=xy\lor\bar{x}z$$

与

$$(x\lor y)(\bar{x}\lor z)(y\lor z)=(x\lor y)(\bar{x}\lor z).$$

把积形式展开，化成和形式：

$$\begin{aligned} (x \lor y)(\overline{x} \lor z)(y \lor z) &= x\overline{x} \lor xz \lor y\overline{x} \lor yz \lor xy \lor xz \lor y^2 \lor yz \\ &= 0 \lor xz \lor y\overline{x} \lor yz \lor xy \lor xz \lor y \lor yz \\ &= xz \lor y\overline{x} \lor yz \lor xy \\ &= xy \lor xz \lor y\overline{x}. \end{aligned}$$

右端与或形式在吸收 $yz$ 之前的展开一致，再对或形式用合意定理去掉 $yz$，两种写法表示同一个函数。

布尔函数

普通代数里可以把 $2x+3$ 看成函数 $f(x)=2x+3$。布尔运算同样可以定义布尔函数。

定义布尔函数

布尔函数对每一种布尔输入组合返回一个布尔值。写成 $f: B^n \rightarrow B$，即从 $n$ 元布尔组到布尔值的映射，其中 $B = \{0, 1\}$。

基本运算都可以写成函数。

1. 代数记号：

   • 与：$f(x, y) = x \cdot y$ 或 $f(x, y) = xy$
   • 或：$f(x, y) = x + y$
   • 非：$f(x) = x'$ 或 $f(x) = \overline{x}$

2. 逻辑记号：

   • 与：$f(x, y) = x \wedge y$
   • 或：$f(x, y) = x \vee y$
   • 非：$f(x) = \neg x$

真值表其实就是函数表：每个输入对应一个输出。实函数 $f:\mathbb{R}\rightarrow\mathbb{R}$ 的表列不完，因为实数无穷多。布尔函数好办得多：每个输出只有一个比特，而 $|B|=2$，于是 $n$ 个输入只有 $2^n$ 种情形。$2^n$ 看起来不小，但实际电路里变量个数多半不超过五个，表仍然画得下。

布尔函数的表示

多数时候，函数是从一张真值表造出来的。任意布尔函数都可以写成析取范式（积之和，SOP）或合取范式（和之积，POS）。

定义积之和形式

积之和（SOP），也叫析取范式（DNF），把布尔函数写成若干积项的和（逻辑或）。每个积项由文字（变量或其补）组成，对应函数值为 $1$ 的那些输入，也就是小项。一般形状是

$$f(x_1, x_2, \ldots, x_n) = \sum_{i=1}^{m} \prod_{j=1}^{n} x_j^{(i)},$$

其中 $m$ 是小项个数，$n$ 是变量个数，$x_j^{(i)}$ 在第 $i$ 个小项里取 $x_j$ 或 $x_j'$，由该小项中 $x_j$ 的取值决定。

定义和之积形式

和之积（POS），也叫合取范式（CNF），把布尔函数写成若干和项的积（逻辑与）。每个和项由文字组成，对应函数值为 $0$ 的那些输入，也就是大项。一般形状是

$$f(x_1, x_2, \ldots, x_n) = \prod_{i=1}^{M} \sum_{j=1}^{n} x_j^{(i)},$$

其中 $M$ 是大项个数，$n$ 是变量个数，$x_j^{(i)}$ 在第 $i$ 个大项里取 $x_j$ 或 $x_j'$，由该大项中 $x_j$ 的取值决定。

注小项与大项

小项对应输出为 $1$ 的输入组合，大项对应输出为 $0$ 的输入组合。它们是写标准型时的基本砖块。

为什么只盯着某一行输出是 $1$ 还是 $0$？因为构造布尔函数就是在做 $B^n$ 到 $B$ 的映射，而 $B=\{0,1\}$，输出只有两种可能。因此只需掌握全部出 $1$ 的情形，或全部出 $0$ 的情形，另一种就自动确定。这正是标准型定理的内容。

定理布尔函数的标准型

任意布尔函数都可以写成下面两种标准型之一。

1. 积之和（SOP / DNF）：函数等于若干小项的析取。小项是文字的合取，对应真值表中函数值为 $1$ 的行。
2. 和之积（POS / CNF）：函数等于若干大项的合取。大项是文字的析取，对应真值表中函数值为 $0$ 的行。

证明

任取布尔函数 $f(x_1, x_2, \ldots, x_n)$，分别构造 SOP 与 POS。

SOP（DNF）。

1. 对真值表中函数值为 $1$ 的每一行，把该行的输入写成一个小项：变量取 $1$ 时用原变量，取 $0$ 时用补。
2. 把这些小项全部析取，得到 SOP。

每个出 $1$ 的输入都对应一个小项，这些小项的析取恰好在这些输入上为 $1$，所以 SOP 与原函数相同。

POS（CNF）。

1. 对函数值为 $0$ 的每一行，把该行的输入写成一个大项：变量取 $0$ 时用原变量，取 $1$ 时用补。
2. 把这些大项全部合取，得到 POS。

每个出 $0$ 的输入都对应一个大项，这些大项的合取恰好在这些输入上为 $0$，所以 POS 与原函数相同。

因此任意布尔函数都可以写成 SOP 或 POS。

例由真值表写 XNOR 的 SOP 与 POS

考虑

$x$	$y$	$f(x, y)$
0	0	1
0	1	0
1	0	0
1	1	1

熟悉运算的话会看出这就是 XNOR，也就是异或的否定。下面分别写出代数表达式的 POS 与 SOP。

解SOP 与 POS

SOP 方面：

• 函数值为 $1$ 的输入组合对应小项 $m_0 = x'y'$，$m_3 = xy$。
• SOP：$f(x, y) = m_0 + m_3 = x'y' + xy$。

POS 方面：

• 函数值为 $0$ 的输入组合对应大项 $M_1 = x + y'$，$M_2 = x' + y$。
• POS：$f(x, y) = M_1 \cdot M_2 = (x + y')(x' + y)$。

同一张真值表可以在两种标准型之间转换。

变量再多，手续不变，只是行数变多。更多例子见本节习题。

布尔函数的性质

下面讨论完备性与对偶，然后给出布尔代数基本定理，也就是 Boole 展开（Shannon 展开）。它是组合逻辑设计和实现的基础。

定理函数完备性

一组布尔运算称为函数完备，如果只用这组运算就能写出每一个布尔函数。下面几组是函数完备的。

1. $\{\text{AND},\ \text{OR},\ \text{NOT}\}$，标准基底。
2. $\{\text{NAND}\}$，只用与非门。
3. $\{\text{NOR}\}$，只用或非门。

数字电路设计依赖这条性质：门的种类可以很少，但仍然能实现任意布尔函数。

证明与、或、非为什么足够

对每个使 $f=1$ 的输入行构造一个合取：该行第 $i$ 位为一就用 $x_i$，为零就用 $\neg x_i$。这个合取恰好只在该行成立。把所有这样的合取析取起来，就在每一行都与 $f$ 相同。若没有真行，取常量零；有输入变量时也可写成 $x\land\neg x$。因此任意有限元布尔函数都能由这组算子表示。下面再把这组算子分别用 NAND 或 NOR 实现；零输入函数则需要明确提供常量。

注逻辑门这个词

逻辑门就是工程师对布尔运算电路实现的叫法。本书只谈数学侧面，不展开电路细节。需要硬件背景时可以参考 逻辑门。

换句话说，任意布尔函数都可以只用 $\{\text{AND},\ \text{OR},\ \text{NOT}\}$ 来写，也可以只用 NAND，或只用 NOR。第一点已经清楚：派生运算都能改写成这三者。NAND 与 NOR 能生成全部基本门，证明如下。

证明

所有布尔运算都能用 $\lnot,\land,\lor$ 写出。因此只需证明 $\{\text{AND},\ \text{OR},\ \text{NOT}\}$ 都能用 NAND 实现，也都能用 NOR 实现。

1. 只用 NAND：

   • 非门：把 NAND 的两个输入短接，就得到非。
   • 与门：NAND 的输出再接一个非（仍用 NAND）就是与。
   • 或门：用德摩根律，$x + y = (x' \cdot y')'$。

2. 只用 NOR：

   • 非门：把 NOR 的两个输入短接，就得到非。
   • 或门：NOR 的输出再接一个非就是或。
   • 与门：用德摩根律，$x \cdot y = (x' + y')'$。

三种基本门都能只用 NAND 或只用 NOR 实现，完备性得证。

注逻辑门的工程用法

更细的门电路说明见 逻辑门。这件事在工程里更常用，数学上记住“一组运算何时够用”即可。

定理对偶原理

对由与、或、非及常量构成的表达式，交换与和或、零和一，同时保留变量及非运算，就得到对偶表达式。对应函数满足

$$f^D(x_1,\ldots,x_n)=\neg f(\neg x_1,\ldots,\neg x_n).$$

因此对偶不依赖同一函数选用哪种表达式，且 $(f^D)^D=f$；任意恒等式两边同时取对偶，仍为恒等式。

证明

按表达式结构归纳。单个变量时，右边为 $\neg\neg x=x$，所以 $x^D=x$，不是 $\neg x$；常量零和一则互换。假设公式对 $g,h$ 成立，由德摩根律，

$$\neg(g(\neg\mathbf x)\land h(\neg\mathbf x)) =g^D(\mathbf x)\lor h^D(\mathbf x).$$

交换与和或，得到另一个二元构造的情形。对于非运算，$\neg(\neg g(\neg\mathbf x))=g(\neg\mathbf x)=\neg g^D(\mathbf x)$，也满足所需公式。所有构造均已覆盖。公式只取决于函数值，故与表达式的选择无关；连续应用两次，输入和输出的两次否定各自抵消，便得双重对偶。相等函数同时替换输入再否定输出仍相等，因此恒等式也保留。

例如 $(x\lor\neg y)^D=x\land\neg y$，$((a\lor b)\land\neg c)^D=(a\land b)\lor\neg c$。NAND 与 NOR 互为对偶；蕴涵 $\neg x\lor y$ 的对偶是 $\neg x\land y$，不是逆蕴涵。对偶改变的是连接词结构，不能额外把每个文字都取反。

下面的定理按某个变量的取值分解函数。

定理Boole 展开定理

Boole 展开（Shannon 展开）是恒等式

$$F=x\cdot F_x+x^{\prime}\cdot F_{x^{\prime}},$$

其中 $F$ 是任意布尔函数，$x$ 是一个变量，$x^{\prime}$ 是它的补，$F_x$ 与 $F_{x^{\prime}}$ 分别是把 $F$ 中的 $x$ 固定为 $1$ 和固定为 $0$ 得到的函数。这两个子函数也叫 $F$ 关于 $x$ 的正、负 Shannon 余因子，可由限制运算 $\operatorname{restrict}(F,x,1)$ 与 $\operatorname{restrict}(F,x,0)$ 算出。写得更显式一些：

$$f(X_1,X_2,\ldots,X_n)=X_1\cdot f(1,X_2,\ldots,X_n)+X_1^{\prime}\cdot f(0,X_2,\ldots,X_n).$$

证明

设 $f(x_1, x_2, \ldots, x_n)$ 是 $n$ 元布尔函数，选定变量 $x_i$。定义两个子函数：

$$\begin{aligned} f_{x_i} &= f(x_1, x_2, \ldots, x_i=1, \ldots, x_n) \\ f_{\overline{x_i}} &= f(x_1, x_2, \ldots, x_i=0, \ldots, x_n). \end{aligned}$$

考虑表达式

$$\begin{aligned} f &= x_i \cdot f_{x_i} + \overline{x_i} \cdot f_{\overline{x_i}} \\ &= (x_i \cdot 1 + \overline{x_i} \cdot 0) \cdot f_{x_i} + (x_i \cdot 0 + \overline{x_i} \cdot 1) \cdot f_{\overline{x_i}} \\ &= x_i \cdot f_{x_i} + \overline{x_i} \cdot f_{\overline{x_i}}. \end{aligned}$$

对任意输入 $(x_1, x_2, \ldots, x_n)$，$x_i$ 与 $\overline{x_i}$ 恰好一个为真。因此两个积项里恰有一项为 $0$，另一项等于 $f$ 在该输入上的值。

若 $x_i$ 为真，则 $x_i \cdot f_{x_i} = f_{x_i}$ 且 $\overline{x_i} \cdot f_{\overline{x_i}} = 0$，表达式等于 $f_{x_i}$，这正是 $x_i$ 为真时 $f$ 的值。

若 $x_i$ 为假，则 $x_i \cdot f_{x_i} = 0$ 且 $\overline{x_i} \cdot f_{\overline{x_i}} = f_{\overline{x_i}}$，表达式等于 $f_{\overline{x_i}}$，这正是 $x_i$ 为假时 $f$ 的值。

因此 $x_i \cdot f_{x_i} + \overline{x_i} \cdot f_{\overline{x_i}}$ 在全部输入上都等于 $f$，Shannon 展开成立。

记 $f_1,f_0$ 为分别固定 $x=1,0$ 后的余因子，其对偶只针对剩余变量。对 Shannon 表达式取对偶，得到

$$f^D=(x\lor f_1^D)\land(\neg x\lor f_0^D).$$

当 $x=0$，该式为 $f_1^D$；当 $x=1$，为 $f_0^D$。因此也可写成积之和：

$$f^D=(\neg x\land f_1^D)\lor(x\land f_0^D).$$

分支值交换，是因为对偶的语义公式先对输入取反，再计算 $f$。

布尔函数的化简

化简布尔函数是数字逻辑设计的关键步骤：在不改变真值表的前提下减少表达式的复杂度。办法很多，下面只写最常用的几种。

用布尔定律化简

上一节的恒等式已经能化简表达式。变量一多，真值表就变得笨重：四个输入已有 $2^4=16$ 行，SOP 或 POS 也可能含很多项。更大规模时，通常改用卡诺图或算法化的最小化方法。

用卡诺图化简

卡诺图（K-map）是最多六个变量时的可视化化简工具。它把计算负担转成人眼对相邻格子的识别。

卡诺图本质上是排成网格的真值表。每个格子对应一种输入，相邻格子只差一个变量。因此相邻的 $1$ 可以圈在一起，对应布尔代数里“只差一个文字的两项可以合并、消掉那个文字”。合并规则于是变成圈格子。

例四变量真值表的卡诺图化简

考虑下面的真值表。

$X_1$	$X_2$	$X_3$	$X_4$	$Z_1$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	0

找出小项，得到四变量 SOP：

$$\begin{aligned} F_1(X1,X2,X3,X4) = & \overline{X1}\ \overline{X2}\ \overline{X3}\ \overline{X4}+\overline{X1}\ \overline{X2}\ \overline{X3}{X4}\\ &+\overline{X1}\ \overline{X2}{X3}{X4}+{X1}\overline{X2}{X3}{X4}\\ &+ \overline{X1}{X2}{X3} \overline{X4}+\overline{X1}{X2}{X3}{X4}\\ &+{X1}\ \overline{X2}\ \overline{X3}{X4}+{X1} \overline{X2}{X3} \overline{X4}\\ &+{X1}{X2}\overline{X3}\ \overline{X4}+{X1}{X2}\overline{X3}{X4}. \end{aligned}$$

用定律硬化简会很慢。改画卡诺图。变量组合的顺序必须按 格雷码：相邻编码只翻一比特。两个变量时顺序是 $00,01,11,10$。要写 SOP，就把所有 $1$ 按下面的规则圈起来。

卡诺图圈组的规则来自布尔代数，目的是尽量少留文字。

1. 二的幂。 每组格子数必须是 $1,2,4,8,\ldots$，这样才能对应一个化简后的积项。
2. 尽量大。 组越大，积项里剩下的变量越少。
3. 允许重叠。 为了得到更大的组，格子可以属于多个组。
4. 可以卷边。 卡诺图在拓扑上是环面：上下边相邻，左右边相邻。
5. 罩住全部 $1$。 每个 $1$ 至少进一个组。
6. $0$ 一般不进组。 除非为了凑更大的 $1$ 的组（通常不这么做；无关项另说）。
7. 本质质蕴涵。 若某组罩住了一个别的组都罩不到的小项，这个组必须进入最终表达式。

按这些规则得到右图的分组。逐组消去组内不一致的变量。

1. 绿组含 $\overline{X1}\ \overline{X2}\ \overline{X3}\ \overline{X4}$ 与 $\overline{X1}{X2}\overline{X3}\ \overline{X4}$，消掉 $X2$，留下 $\overline{X1}\ \overline{X3}\ \overline{X4}$。
2. 红组含 $\overline{X1}\ \overline{X2}\ \overline{X3}{X4}$ 与 ${X1}\overline{X2}\ \overline{X3}{X4}$，消掉 $X1$，留下 $\overline{X2}\ \overline{X3}{X4}$。
3. 蓝组含 $\overline{X1}\ \overline{X2}{X3}{X4}$ 与 $\overline{X1}{X2}{X3}{X4}$，消掉 $X2$，留下 $\overline{X1}{X3}{X4}$。
4. 紫组含 $\overline{X1}{X2}{X3}{X4}$ 与 $\overline{X1}{X2}{X3}\overline{X4}$，消掉 $X4$，留下 $\overline{X1}{X2}{X3}$。
5. 黄组含 ${X1}{X2}\overline{X3}\ \overline{X4}$ 与 ${X1}{X2}\overline{X3}{X4}$，消掉 $X4$，留下 ${X1}{X2}\overline{X3}$。
6. 粉组只有一格，必须保留 ${X1}\overline{X2}{X3}\overline{X4}$。

各项用 $+$ 连接，得到化简后的 SOP：

$$F_1=\overline{X1}\ \overline{X3}\ \overline{X4}+\overline{X2}\ \overline{X3}{X4}+ \overline{X1}{X3}{X4}+\overline{X1}{X2}{X3}+{X1}{X2}\overline{X3}+{X1}\overline{X2}{X3}\overline{X4}.$$

十项收成六项，看起来像变魔术。可它并不能包办一切：变量到七个及以上，图就画不住了。

SOP 会了，POS 也可以：对图中的 $0$ 重复同一套圈组规则，再把每组不一致的变量消掉，写成和之积。

卡诺图通常只用到四到六个变量，原因是实际限制，不是理论上不能画更大的图。

1. 视觉复杂度。 卡诺图靠空间排列让人眼发现模式。超过六个变量后，格子排布很难一眼读懂。
2. 认知负担。 人脑同时处理的视觉信息有限，每多一个变量，出错机会都明显上升。
3. 格子数目。 每加一个变量，格子数翻倍。六变量已有 $64$ 格，七变量 $128$ 格，手工圈组不再现实。
4. 效率与错误。 变量一多，圈组更容易漏或重。这时更适合程序化方法，例如后面的奎因-麦克拉斯基算法，或 二叉决策图（BDD）。

因此，六个变量以上虽然理论上还能画卡诺图，实际上会改用别的最小化方法。

从集合角度看，每个格子对应变量取值域幂集里的一个元素，也就是一种取值组合。相邻格子只差一个坐标，对应集合论里“相差最少条件”的相邻。圈组相当于把共享同一特征的子集并起来，从而在表达式里只留下必要变量。化简后的函数就是这些组的并。目标是：用尽可能少、尽可能大的相邻组罩住全部 $1$（函数的真值集），再把各组译回布尔表达式。

用奎因-麦克拉斯基方法化简

奎因-麦克拉斯基方法由 W. V. Quine 与 E. J. McCluskey, Jr. 在二十世纪五十年代给出。它提供机械化的化简手续，适用面比卡诺图更广。

该方法也叫质蕴涵法：先找出函数的全部质蕴涵，再从中抽出本质质蕴涵，得到最简表达式。与卡诺图不同，它不依赖视觉模式，因此适合编程，也能处理变量很多的函数。

步骤如下。

1. 把函数的小项写成二进制。
2. 按二进制表示里 $1$ 的个数分组。
3. 在相邻组中比较每一对小项，找出恰好差一比特的对，合并成新项，并给被合并的小项做标记。
4. 重复直到不能再合并。留下未标记的项，就是质蕴涵。
5. 用质蕴涵表找出本质质蕴涵，并选出函数的最小覆盖。

写成伪代码如下。

算法 1 奎因-麦克拉斯基化简

Require: 布尔函数 $f$

Ensure: 化简后的布尔表达式

1:把 $f$ 的每一项写成二进制，得到小项。

2:按二进制表示中 $1$ 的个数把小项分组。

3:while 还能继续合并 do

4:把相邻组中恰好差一比特的对合并。

5:给被合并的小项做标记。

6:end while

7:收集未标记的项，作为质蕴涵。

8:构造质蕴涵表并选出最小覆盖。

9:return 化简后的函数

例布尔函数表示的一个实例

逐步表格计算的一个完整例子见 奎因-麦克拉斯基表方法。

习题

练习把异或和蕴涵写成布尔函数

把异或和蕴涵写成布尔函数。

解异或与蕴涵

$$\begin{aligned} F(x,y)= x \oplus y &= (x \land \lnot y) \lor (\lnot x \land y)\\ &= xy' + x'y. \end{aligned}$$$$\begin{aligned} F(x,y)= x \rightarrow y &= \lnot x \lor y\\ &= x' + y. \end{aligned}$$

练习用表列出下列布尔函数的取值

用表列出下列布尔函数在全部输入上的值。

1. $F(x, y, z) = xy$
2. $F(x, y, z) = x + yz$
3. $F(x, y, z) = xy + (xyz)$
4. $F(x, y, z) = x(yz + \overline{y}z)$

第三个函数由吸收律化为 $xy$；第四个利用 $y+\overline y=1$ 化为 $xz$。

$x$	$y$	$z$	$xy$	$x+yz$	$xy+xyz$	$x(yz+\overline y z)$
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	0	1	0	0
1	0	0	0	1	0	0
1	0	1	0	1	0	1
1	1	0	1	1	1	0
1	1	1	1	1	1	1

练习用代数方法证明布尔函数的对偶

用代数方法证明布尔函数的对偶原理。

证明

前面的结构归纳证明已经覆盖变量、常量、两个二元连接词及非运算。特别地，对 $f=x\lor\neg y$，直接取对偶与计算 $\neg f(\neg x,\neg y)=\neg(\neg x\lor y)$，都会得到 $x\land\neg y$。

练习用卡诺图化简下列真值表给出的函数

用卡诺图化简下列真值表给出的布尔函数。

$X_1$	$X_2$	$X_3$	$X_4$	$Z_1$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	0

解$F_2$ 的卡诺图化简

函数的 SOP 为

$$\begin{aligned} F_2(X1,X2,X3,X4) = &\overline{X1}\ \overline{X2}\ \overline{X3}{X4}+\overline{X1}\ \overline{X2}{X3}\overline{X4}\\ &+\overline{X1}\ \overline{X2}{X3}{X4}+\overline{X1}{X2}\overline{X3}\ \overline{X4}\\ &+\overline{X1}{X2}{X3}\overline{X4}+{X1}\overline{X2}\ \overline{X3}\ \overline{X4}\\ &+{X1}\overline{X2}\ \overline{X3}{X4}+{X1}\overline{X2}{X3}{X4}\\ &+{X1}{X2}\overline{X3}\ \overline{X4}+{X1}{X2}\overline{X3}{X4}. \end{aligned}$$

卡诺图如下。

1. 蓝组含 $\overline{X1}\ \overline{X2}{X3}\overline{X4}$ 与 $\overline{X1}{X2}{X3}\overline{X4}$，消掉 $X2$，留下 $\overline{X1}{X3}\overline{X4}$。
2. 黄组含 $\overline{X1}{X2}\overline{X3}\ \overline{X4}$ 与 ${X1}{X2}\overline{X3}\ \overline{X4}$，消掉 $X1$，留下 ${X2}\overline{X3}\ \overline{X4}$。
3. 红组有四格，可以消掉两个变量；此处 $X3$ 与 $X1$ 在组内不固定，留下 $\overline{X2}\,X4$。
4. 绿组也是四格，消掉 $X2$ 与 $X4$，留下 $X1\overline{X3}$。

因此化简后的 SOP 为

$$F_2=\overline{X1}{X3}\ \overline{X4}+{X2}\overline{X3}\ \overline{X4}+\overline{X2}{X4}+{X1}\overline{X3}.$$

练习只用与和非表示下列函数

只用运算 $\cdot$（与）和补（非）表示下列布尔函数。

1. $x + y + z$
2. $x + \overline{y}(x + z)$
3. $x + \overline{y}$
4. $x(\overline{x} + y + z)$

解用德摩根律消去或

每次出现 $s + t$，都换成 $\overline{\overline{s} \cdot \overline{t}}$，必要时再用双重否定化简。

1. $x + y + z = \overline{\overline{x}\cdot\overline{y}\cdot\overline{z}}$。
2. 先写 $x+z=\overline{\overline{x}\cdot\overline{z}}$，于是

$$x + \overline{y}(x + z) = \overline{\overline{x}\cdot\overline{\overline{y}\cdot\overline{\overline{x}\cdot\overline{z}}}}.$$

3. $x + \overline{y} = \overline{\overline{x}\cdot y}$。
4. $\overline{x}+y+z=\overline{x\cdot\overline{y}\cdot\overline{z}}$，因此

$$x(\overline{x}+y+z)=x\cdot\overline{x\cdot\overline{y}\cdot\overline{z}}.$$

练习至少三个变量为 $1$ 的五元 SOP

求布尔函数 $F(x_1, x_2, x_3, x_4, x_5)$ 的积之和展开，使得该函数取 $1$ 当且仅当 $x_1, x_2, x_3, x_4, x_5$ 中至少三个取值为 $1$。

解列出全部至少三个原变量的小项

需要列入所有至少三个变量以原变量（不取补）出现的项。五个变量里取三个、四个、五个的组合数是 $10+5+1=16$，所以共 $16$ 项：

$$\begin{aligned} F(x_1, x_2, x_3, x_4, x_5) = \ & x_1 x_2 x_3 x_4 x_5+ x_1 x_2 \overline{x_3} x_4 x_5\\ + \ & x_1 x_2 x_3 x_4 \overline{x_5} + x_1 x_2 x_3 \overline{x_4} x_5 \\ + \ & x_1 \overline{x_2} x_3 x_4 x_5 + \overline{x_1} x_2 x_3 x_4 x_5 \\ + \ & x_1 x_2 x_3 \overline{x_4} \overline{x_5} + x_1 x_2 \overline{x_3} x_4 \overline{x_5} \\ + \ & x_1 \overline{x_2} x_3 x_4 \overline{x_5} + \overline{x_1} x_2 x_3 x_4 \overline{x_5} \\ + \ & x_1 x_2 \overline{x_3} \overline{x_4} x_5 + x_1 \overline{x_2} x_3 \overline{x_4} x_5 \\ + \ & \overline{x_1} x_2 x_3 \overline{x_4} x_5 + x_1 \overline{x_2} \overline{x_3} x_4 x_5 \\ + \ & \overline{x_1} x_2 \overline{x_3} x_4 x_5 + \overline{x_1} \overline{x_2} x_3 x_4 x_5. \end{aligned}$$

练习满足对称翻转条件的三元函数个数

有多少个不同的布尔函数 $F(x, y, z)$ 满足：对布尔变量 $x,y,z$ 的一切取值，都有

$$F(\overline{x}, y, z) = F(x, \overline{y}, z) = F(x, y, \overline{z})?$$

解由两个自由值决定其余取值

先指定 $F(0,0,0)$。条件迫使 $F(0,0,0)=F(1,1,0)$ 以及 $F(0,0,0)=F(1,0,1)$，从而也有 $F(1,1,0)=F(0,1,1)$，到此仍未限制其余点。再指定 $F(1,1,1)$（此前对它没有限制），同样的关系就决定了 $F(0,0,1)$、$F(0,1,0)$、$F(1,0,0)$。函数至此完全确定。$F(0,0,0)$ 有两种选法，$F(1,1,1)$ 也有两种，因此一共 $2\times 2=4$ 个这样的函数。

练习布尔域 $\mathbb{B}^n$ 的几何图像

第一部分讨论过欧氏空间的可视化。现在说明怎样想象 $\mathbb{B}^n$。

• $\mathbb{B}$、$\mathbb{B}^2$、$\mathbb{B}^3$ 各是什么几何对象？
• 怎样借助 $\mathbb{B}^3$ 来理解 $\mathbb{B}^4$？

解超立方体

集合 $\mathbb{B}$ 是布尔域，只有两个元素 $0$ 和 $1$。更高维时：

• $\mathbb{B}^2$ 可以看成二维网格上的正方形，四个顶点对应 $(00,01,10,11)$。
• $\mathbb{B}^3$ 把这件事抬成三维立方体，八个顶点对应 $(000,001,010,011,100,101,110,111)$。

$\mathbb{B}^4$ 无法直接用三维空间看完。可以把它想成超立方体（镶嵌体）：每个顶点对应一个四元布尔组，从 $0000$ 到 $1111$。虽然不能在空间里“看见”四维，但仍可以用四维二进制网格来标记每个点。

下面把布尔域画成欧氏空间中的点集。

谓词与量词

布尔函数以真值为输入，谓词则描述指定论域中的对象，量词在这个论域中取值。基本定义和否定律见命题与公理系统；形式语法、变量作用域、替换和量词推理规则则集中在形式逻辑与自然演绎。

推理与演绎

代数化简保持函数不变，推理则研究哪些结论能从前提得到。建议依次阅读形式逻辑与自然演绎、命题逻辑的自动推理，以及一阶逻辑的归结与定理证明。这里学到的 CNF 会成为归结和 SAT 的输入，卡诺图与布尔化简则继续保留在代数主线上。