3-逻辑函数及其化简

做题总结

• 常用的公式：
  $消因子：A+\overline{A}B=A+B$
  $消冗余项：AB+\overline{A}C+BC(D)=AB+\overline{A}C$
  $(A+B)(A+C)=A+BC$
  $A+AB=A$
  $(A+B)(A+\overline{B})=A$
• 德摩根定理
• 对偶、反演的变换规则；代换（逻辑变量可以用逻辑函数代替）
• 卡诺图找矩形注意临界相邻，要求尽可能少、矩形尽可能大

逻辑运算

基本运算

• 逻辑变量：只取 $0$、$1$，表示假、真。
  

• 优先级：非 $\to$ 与 $\to$ 或。

• 完备集：能实现任意逻辑函数的一组运算

  • $\{\text{与、或、非}\}$、$\{\text{与、非}\}$、$\{\text{或、非}\}$ 均完备
  • $\{\text{与、或}\}$ 不完备，不能实现非
• • 补充：反相线、小圆圈表示取反。

复合运算

运算	表达式	输出为 $1$ 的条件
与非（NAND）	$Y=\overline{AB}$	不全为 $1$；有 $0$
或非（NOR）	$Y=\overline{A+B}$	全为 $0$
异或（XOR）	$Y=A\oplus B=\overline{A}B+A\overline{B}$	两输入不同
同或（XNOR）	$Y=A\odot B=\overline{A}\overline{B}+AB$	两输入相同
![[ch3-复合逻辑运算-与非或非-014.png	451]]
![[ch3-复合逻辑运算-异或同或-015.png	532]]

异或性质：

$$\begin{array}{rlrl}A\oplus 0& =A,& A\oplus 1& =\overline{A}\\ A\oplus A& =0,& A\oplus \overline{A}& =1\\ A\oplus B& =B\oplus A& & \end{array}$$

通用门：与非门、或非门各自都能实现任意逻辑函数(与或非)。

---

逻辑代数的基本定律和规则

基本定律

基本定律略，不需要背诵

逻辑代数基本规则

规则	变换	注意
代换	对于一个逻辑等式，把同一变量的所有位置，同时换成同一逻辑函数	同步替换，等式仍成立
对偶	所有 $+\leftrightarrow \cdot$、$0\leftrightarrow 1$，原变量、反变量不变。逻辑等式成立，其对偶等式也成立	运算顺序不能改变
反演	所有 $+\leftrightarrow \cdot$、$0\leftrightarrow 1$，$X_i\leftrightarrow \overline{X_i}$，注意保持运算顺序不变	得到反函数 $\overline{F}$，输出与 $F$ 相反

• 对偶与反演的区别：对偶保持变量的原、反形式不变，所得 $F^{\ast }$ 与 $F$ 仅形式对偶；反演还须互换原变量与反变量，所得 $\overline{F}$ 与 $F$ 输出相异
• 真值表法（完全归纳法）：列出全部 $2^n$ 组输入，核对等式两边输出

二变量和三变量定理

定律	定律公式及对偶式	理解与用途
交换律	$A+B=B+A$ $AB=BA$	可交换变量次序
结合律	$(A+B)+C=A+(B+C)$ $(AB)C=A(BC)$	可改变结合顺序
分配律	$AB+AC=A(B+C)$ $(A+B)(A+C)=A+BC$	可提取公因式；注意对偶式的应用
吸收律	$A+AB=A(1+B)=A$ $A(A+B)=A$	化简常用
并项公式	$AB+A\overline{B}=A(B+\overline{B})=A$ $(A+B)(A+\overline{B})=A$	合并 $B$ 的两种状态，消去 $B$
消冗余项公式	$AB+\overline{A}C+BC=AB+\overline{A}C$ $(A+B)(\overline{A}+C)(B+C)=(A+B)(\overline{A}+C)$	$BC$ 称为一致项（冗余项）
消因子公式	$A+\overline{A}B=(A+\overline{A})(A+B)=A+B$ $A(\overline{A}+B)=AB$	$A=1$ 时输出为 $1$，$A=0$ 时输出为 $B$，故 $\overline{A}$ 可消去。

• 补充：$AB(A+B)=AB,AB=AB(A+B)$

消冗余项的推导：补上 $A+\overline{A}=1$，再吸收。

$$\begin{array}{rl}AB+\overline{A}C+BC& =AB+\overline{A}C+BC(A+\overline{A})\\ & =AB(1+C)+\overline{A}C(1+B)\\ & =AB+\overline{A}C\end{array}$$

消冗余项的推广：$AB+\overline{A}C+BCD=AB+\overline{A}C$。

德摩根定理

$$\overline{X_1{X}_2\dots X_n}=\overline{X_1}+\overline{X_2}+\dots \overline{X_n}$$

$\overline{X_1+X_2+\dots X_n}=\overline{X_1}\overline{X_2}\dots \overline{X_n}$

整体取反：逐项取反，并交换与、或运算

• 与取反：至少一个条件不成立
• 或取反：所有条件都不成立

广义德摩根定理

$$\overline{F(X_1,\dots ,X_n,+,\cdot )}=F(\overline{X_1},\dots ,\overline{X_n},\cdot ,+)$$

对一个逻辑表达式取反的结果：可以通过对每一项取反，并交换与和或运算（适用于任意表达式）

---

逻辑函数的表示

逻辑函数：每组输入唯一对应一个输出；$n$ 个变量有 $2^n$ 组输入。

$$F=f(X_1,\dots ,X_n),X_i,F\in \{0,1\}$$

表示方法	要点
逻辑表达式	用与、或、非等运算描述输入、输出关系
逻辑图	用门电路和连线表示运算
真值表	列出全部输入组合及输出
波形图	用波形表示输入输出
标准表达式	最小项之和或最大项之积
卡诺图	按循环邻接关系排列真值表，便于化简

转换方法总结：

• 真值表 $\leftrightarrow$ 卡诺图：按输入编号填值，只改变排列
• 真值表 $\to$ 标准式：取 $1$ 写最小项之和，取 $0$ 写最大项之积
• 表达式 $\to$ 真值表：代入全部输入组合
• 逻辑图 $\leftrightarrow$ 表达式：逐级写式，或按运算顺序连接门

给定变量顺序后，真值表、标准项列表唯一
普通表达式可以有多种写法。

真值表：

波形图：

---

逻辑表达式

与或式、或与式

形式	组成	表达式
与或式（SOP）	多个乘积项的或运算	$AB+\overline{A}C$
或与式（POS）	多个求和项的与运算	$(A+B)(\overline{A}+C)$

标准表达式

标准项：每项含全部变量，每个变量恰好出现一次。

对比	最小项 $m_i$	最大项 $M_i$
结构	与项	或项
对应输入	仅在编号 $i$ 的输入下为 $1$	仅在编号 $i$ 的输入下为 $0$
变量写法	$1$ 写原变量，$0$ 写反变量	$0$ 写原变量，$1$ 写反变量
由真值表求标准式	所有 $F=1$ 的最小项相或	所有 $F=0$ 的最大项相与
标准式名称	标准与或式	标准或与式

若第 $i$ 行输出为 $f_i$，则标准表达式为

$$F=\sum _{f_i=1}m(i_1,i_2,\dots )=\prod _{f_i=0}M(i_1,i_2,\dots )$$

或$F=\Sigma m+\Sigma d$，其中 $d$ 表示无关项。
标准形式的反函数直接替换补集序号即可，无关项无需更换。

(真值表按二进制数值大小排序）
标准项性质

• $M_i=\overline{m_i}$
• 最小项性质：$m_i{m}_j=0(i\ne j)$
• 最大项性质：$M_i+M_j=1(i\ne j)$
• 相邻的两个最小项之和，可以合并成一项，并消去一个因子
• 真值表的表示是唯一的，因此标准项列表的表示也是唯一的
• 最大项编号集合和最小项编号集合互补（两种列表之间可方便转换）

---

逻辑函数的化简

• 最简与或式：保持功能不变，先使与项最少，再使总变量数最少；结果可能不唯一
• 最简式便于减少用门，标准式便于编号

代数法

五种代数化简方法：

方法	公式	做法
并项法	$AB+A\overline{B}=A$	合并消去互补变量
吸收法	$A+AB=A$	删去被其他项包含的项
消因子法	$A+\overline{A}B=A+B$	消去项中的多余因子
消项法	$AB+\overline{A}C+BC(D)=AB+\overline{A}C$	删去被其他项共同覆盖的项
配项法	$A+A=A$ $A+\overline{A}=1$	用 $A=A+A=A(B+\overline{B})$ 复制、拆分已有项

例题：

卡诺图法

卡诺图

卡诺图（K-map）：把真值表按循环邻接规则重新排列成方格图，相邻输入组合只相差一个变量 (便于找出能合并的最小项)

• 格子位置表示输入：$n$ 个变量有 $2^n$ 格，每格对应一组输入，即一个最小项。

• 格内数字表示输出：在对应位置填入 $F$ 的值。和真值表对应，具有唯一性
  

• 单变量按 $0,1$ 排列；两变量按格雷码 $00,01,11,10$ 排列

• 四变量常用行 $AB$、列 $CD$，组成 $4\times 4=16$ 格

• 若给出 $F=\sum m(\cdots )$，所列最小项填 $1$，其余填 $0$

化简原理：去异留同

• 相邻两格的最小项有一个变量互补，利用并项公式消去该变量：

$$PX+P\overline{X}=P(X+\overline{X})=P$$

• 矩形内的 $2^k$ 格，包含 $k$ 个变化变量的全部组合，因此可消去这 $k$ 个变量，留下 $n-k$ 个不变变量
• 循环邻接：左右边界相邻，上下边界相邻；四变量图的四角也能合成一组。斜对角不相邻
  

方法总结

卡诺图化简法

• 填图：填卡诺图
• 找矩形：圈尽量大、圈数尽量少、覆盖所有的 1（优先找好零散的以及临界的 1）
  • 允许重叠，但每个矩形至少有一个不重叠的1
  • 矩形格数必须为 $2^n$(1,2,4,8…)。
  • 注意临界相邻
• 读式相或：把每个矩形写成与项，然后或运算得到最简与或式

补充：若卡诺图中多数为 $0$，则可以圈 $0$ 矩形得到 $\overline{F}$ 的最大项，变换成最小项即可

• 全图为 $1$ 时 $F=1$；全图为 $0$ 时 $F=0$。

示例

$$F=BCD+AD+A\overline{B}\overline{C}$$

$$\overline{F}=ABD\Rightarrow F=\overline{ABD}=\overline{A}+\overline{B}+\overline{D}$$

---

非完全描述的逻辑函数

• 非完全描述：部分输入组合未规定输出，用其他符号代替
• 无关项：输入不会出现（约束项），或不关心其输出（任意项），记为 $\times$、$d$ 或 $\Phi$
  • 可任意取 $0$ 或 $1$，以方便矩形的选择，不必全部使用
  • 合法矩形不能只包含无关项。

例：