Logic Expression Simplification

逻辑运算定律

名称	公式1(基于·运算)	公式2(基于+运算)
0·1 律	$A\cdot 1=A$	$A+0=A$
	$A\cdot 0=0$	$A+1=1$
互补律	$A\overline{A}=0$	$A+\overline{A}=1$
重叠律	$AA=A$	$A+A=A$
交换律	$AB=BA$	$A+B=B+A$
结合律	$A(BC)=(AB)C$	$A+(B+C)=(A+B)+C$
分配律	$(A+B)C=AC+BC$	$AB+C=(A+C)(B+C)$
反演律	$\overline{AB}=\overline{A}+\overline{B}$	$\overline{A+B}=\overline{A}\overline{B}$
吸收律	$A(A+B)=A$	$A+AB=A$
	$A(\overline{A}+B)=AB$	$A+\overline{A}B=A+B$
	$(A+B)(\overline{A}+C)(B+C)=(A+B)(\overline{A}+C)$	$AB+\overline{A}C+BC=AB+\overline{A}C$
对合律	$\overline{\overline{A}}=A$	-

卡诺图

假设我们有如下逻辑表达式

$$F(A,B,C)=\overline{A}\overline{B}C+\overline{A}BC+A\overline{B}\overline{C}+A\overline{B}C+ABC$$

现在, 我们将这个真值表转换为卡诺图. 1. 构建卡诺图 对于三个变量, 我们需要一个$2\times 4$的卡诺图. 列表示$B$和$C$, 行表示$A$, 使用格雷码排列.

	BC=00	BC=01	BC=11	BC=10
A=0
A=1

2. 填充卡诺图

根据真值表, 将$F$的值填入卡诺图中对应的单元格.

	BC=00	BC=01	BC=11	BC=10
A=0	0	1	1	0
A=1	1	1	1	0

3. 圈选

在卡诺图上, 我们圈选相邻的1. 圈选的规则是: 圈选的区域必须是矩形或正方形, 且大小必须是2的幂次方.

• 我们可以圈选左边两列下方的两个1（A=1, BC=00 和 A=1, BC=01）。
• 我们可以圈选上方中间的两个1（A=0, BC=01 和 A=0, BC=11）。
• 我们可以圈选下方中间的两个1（A=1, BC=01 和 A=1, BC=11）。

现在卡诺图如下, 用括号表示圈选的部分, 实际使用中用圆圈或者其他方式标记即可。

	BC=00	BC=01	BC=11	BC=10
A=0	0	(1)	(1)	0
A=1	(1)	(1)	(1)	0

4. 提取简化后的表达式

• 第一个圈选 (A=1, BC=00 和 A=1, BC=01): A=1没有变化, BC从00变化到01, 表明C变化了, B没变, 等于0. 这个圈选对应的项是 $A\overline{B}$
• 第二个圈选 (A=0, BC=01 和 A=0, BC=11): A=0没有变化, 等于$\overline{A}$。BC从01变化到11, 表明B变化了, C没变, 等于1. 这个圈选对应的项是$\overline{A}C$
• 第三个圈选 (A=1, BC=01 和 A=1, BC=11): A=1没有变化, 等于$A$. BC从01变化到11, 表明B变化了, C没变, 等于1. 这个圈选对应的项是$AC$。

所以最终简化后的逻辑表达式为：

$$F(A,B,C)=A\overline{B}+\overline{A}C+AC=A\overline{B}+C$$

Tip

在卡诺图上圈选的注意事项

• 只能圈 $2$ 的幂次个元素, $2^0=1$ 也算
• 尽可能圈大一点, 不用管重叠, 只要不把 $0$ 包括进去就可以
• 上下左右边界是联通的
• $4\times 4$ 的卡诺图的左上, 右上, 左下, 右下的四个格子也可以放一起
• 检查最后得到的表达式还能不能化简

See Also

Karnaugh Map - Wikipedia