布尔代数与卡诺图化简

概念

布尔代数是只有两个值（0 / 1）的代数系统。它和普通代数最大的不同在于：

$$1+1=1,A\cdot A=A,A+A=A$$

这里的"+"是或（OR），"·"是与（AND），"$\overline{A}$"是非（NOT）。没有减法、没有除法、没有系数。

为什么要学它：因为 MOS 管只能导通/截止，所以硬件实现的"逻辑"天然就是这三种运算的组合。而同一逻辑功能有无数种表达式，对应无数种电路——管数、层数、延迟、功耗全都不同。

$$\boxed{{\displaystyle \text{化简的目的：用更少的门、更少的层级，实现同一个真值表}}}$$

一句话：卡诺图是"看图求最小表达式"的工具；它一步到位，比反复套公式快得多，而且不容易漏掉最优解。

原理

一、三种基本运算与真值表

$A$	$B$	$A\cdot B$ (AND)	$A+B$ (OR)	$\overline{A}$ (NOT)	$A\oplus B$ (XOR)
0	0	0	0	1	0
0	1	0	1	1	1
1	0	0	1	0	1
1	1	1	1	0	0

异或的等价定义（两种都常用）：

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

异或的性质：$A\oplus 0=A$（当作"可控反相器"）、$A\oplus 1=\overline{A}$、$A\oplus A=0$。这几条在加法器和奇偶校验里反复用。

二、布尔代数的定律（必背）

单变量定律

名称	或形式	与形式
同一律	$A+0=A$	$A\cdot 1=A$
零一律	$A+1=1$	$A\cdot 0=0$
幂等律	$A+A=A$	$A\cdot A=A$
对合律	$\bar{\overline{A}}=A$	—
互补律	$A+\overline{A}=1$	$A\cdot \overline{A}=0$

双变量及以上

名称	或形式	与形式
交换律	$A+B=B+A$	$AB=BA$
结合律	$(A+B)+C=A+(B+C)$	$(AB)C=A(BC)$
分配律	$A(B+C)=AB+AC$	$A+BC=(A+B)(A+C)$ ← 独有的！
吸收律	$A+AB=A$	$A(A+B)=A$
冗余律（共识）	$AB+\overline{A}C+BC=AB+\overline{A}C$	$(A+B)(\overline{A}+C)(B+C)=(A+B)(\overline{A}+C)$
德摩根	$\overline{A+B}=\overline{A}\cdot \overline{B}$	$\overline{A\cdot B}=\overline{A}+\overline{B}$

两个反直觉的坑：

1. 分配律的第二式 $A+BC=(A+B)(A+C)$ 在普通代数里不成立（这是布尔代数独有的）。验证：取 $A=1$，左边 $=1$，右边 $=(1)(1)=1$ ✓；取 $A=0$，左边 $=BC$，右边 $=BC$ ✓。
2. 德摩根要"拆横线、换符号"同时做：$\overline{A+B}=\overline{A}\overline{B}$（长横线断成两条短的、+ 变 ·）。只做一半就错。

德摩根的真值表验证

$A$	$B$	$\overline{AB}$	$\overline{A}+\overline{B}$	$\overline{A+B}$	$\overline{A}\overline{B}$
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

两两一致 ✓

记忆口诀："横线断开、符号翻转、0↔1、变量不变"。

硬件含义（这就是"NAND 能搭一切"的原因）：

$$\text{NAND}(A,B)=\overline{AB}=\overline{A}+\overline{B}$$

即"与非 = 输入取反后做或"，一个 NAND 门内部就完成了"与 + 非"两步。

三、标准形式：最小项与最大项

最小项（minterm）

$n$ 个变量可组成 $2^n$ 个最小项，每个最小项是所有变量各出现一次的乘积项（每个变量以原变量或反变量出现一次）。

例如 $A,B,C$ 的 $m_5$：二进制 $101$ → $A=1,B=0,C=1$ → $m_5=A\overline{B}C$。

最小项的关键性质：

1. 任一最小项，只有一组输入使它为 1
2. 任意两个不同最小项之积为 0（互斥）
3. 全部最小项之和为 1（完备）

标准与或式（SOP, Sum of Products）

$$F=\sum m(\text{使 }F=1\text{ 的那些最小项编号})$$

例：$F(A,B,C)$ 在 $m_1,m_3,m_5,m_7$ 处为 1，则 $F=\sum m(1,3,5,7)=\overline{A}\overline{B}C+\overline{A}BC+A\overline{B}C+ABC$。

标准或与式（POS, Product of Sums）

$$F=\prod M(\text{使 }F=0\text{ 的那些最大项编号})$$

关键对照：$M_i=\overline{m_i}$，所以 $\sum m(S)=\prod M(\text{全集}-S)$。

考试技巧：给最小项和给最大项是同一件事的两种说法。$F=\sum m(1,3,5,7)$ 等价于 $F=\prod M(0,2,4,6)$。别把编号搞反。

四、卡诺图：把化简变成"圈圈"

为什么能用"圈"化简

一个乘积项若少一个变量，就对应两个相邻的最小项。例如：

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

"相邻"的含义：两个最小项只有一个变量不同（其余相同）。

于是化简 = 把相邻的 1 圈起来，圈越大消掉的变量越多：

圈的大小	消掉的变量数
2 个格	1 个
4 个格	2 个
8 个格	3 个
$2^k$ 个格	$k$ 个

排列规则：必须用格雷码

卡诺图的行、列编号必须按格雷码（相邻只差一位），否则"相邻"就失去意义。

2 变量              3 变量（列用 00,01,11,10）
        B                        BC
        0   1                 00  01  11  10
   A 0 │   │   │         A 0 │   │   │   │   │
     1 │   │   │           1 │   │   │   │   │

4 变量（行 AB 用 00,01,11,10；列 CD 用 00,01,11,10）
              CD
              00  01  11  10
        AB 00│   │   │   │   │
           01│   │   │   │   │
           11│   │   │   │   │
           10│   │   │   │   │

注意 4 变量图的顺序是 00, 01, 11, 10——不是 00,01,10,11。这是最容易画错的地方。

圈的规则（六条）

① 只能圈 2^k 个格（1,2,4,8,16...），不能圈 3 个、5 个
② 圈必须是矩形（含正方形、长条），不能是 L 形、对角线
③ 每个 1 至少被圈一次（0 可以不圈）
④ 圈可以重叠（同一个 1 被多个圈覆盖）
⑤ 圈可以跨越边界：左右边缘相邻、上下边缘相邻
⑥ 4 变量图的四个角互相相邻（可圈在一格里）

目标：用尽量少的圈、每个圈尽量大。

一个实用的优先级：先找"只有一个 1 没被覆盖"的格 → 它的圈是本质蕴含项，必须圈；然后再用大圈覆盖剩下的。

四角相邻的原理

4 变量的四个角是 $m_0(0000)$、$m_2(0010)$、$m_8(1000)$、$m_{10}(1010)$——把它们写出来：

$$\overline{A}\overline{B}\overline{C}\overline{D}+\overline{A}\overline{B}C\overline{D}+A\overline{B}\overline{C}\overline{D}+A\overline{B}C\overline{D}=\overline{B}\overline{D}$$

确实能合成一项，所以四角要当"相邻"看。

五、无关项（don't care）

某些输入组合永远不会出现（例如 BCD 码中 1010~1111），或出现时输出随便。这些格在卡诺图上标 X。

处理规则：X 可以当 1 圈，也可以当 0 不管——怎么对你有利怎么来。

注意：X 不能单独圈（必须和至少一个真 1 一起圈，否则多出一个无用项）；X 也不能强制当 1（那样可能覆盖了本该为 0 的格导致功能错误——但在"永不会出现"的前提下无所谓）。

六、从化简结果到电路：NAND / NOR 的对应

表达式形式	直接实现	说明
SOP（与或式）	NAND–NAND	$\overline{\stackrel{―}{AB}\cdot \stackrel{―}{CD}}=AB+CD$
POS（或与式）	NOR–NOR	对偶关系

推导 SOP → NAND-NAND 的过程：

$$F=AB+CD=\overline{\stackrel{―}{AB+CD}}=\overline{(\stackrel{―}{AB})\cdot (\stackrel{―}{CD})}$$

右边正好是"两个 NAND 驱动一个 NAND" ✓

为什么重要：CMOS 里 NAND/NOR 是最便宜的门（4 管）。能全用 NAND 实现，就比用 AND+OR（6+6 管）省一大截。 这就是综合工具默认往 NAND 走的理由。

七、竞争冒险：化简之后可能更"脆"

化简会消掉冗余项，但冗余项有时是"救命的"。

考虑 $F=AB+\overline{A}C$。当 $B=C=1$ 时：

$$F=A\cdot 1+\overline{A}\cdot 1=A+\overline{A}=1$$

理论上 $F$ 恒为 1，与 $A$ 无关。但实际上：$A$ 变化时，"$AB$ 这条路"和"$\overline{A}C$ 这条路"的延迟不同——可能出现瞬间两条路都为 0，输出冒出一个负脉冲（毛刺）。

理想：  A  ──┐  ┌────       F  ─────────────  恒 1
            └──┘

实际：  A  ──┐  ┌────       F  ─────┐ ┌──────  出现负毛刺
            └──┘                   └─┘
                                  ↑ 两条路径延迟差造成的

消除方法：

1. 加冗余项（卡诺图上多圈一个重叠圈）：$F=AB+\overline{A}C+BC$。当 $B=C=1$ 时 $BC=1$ 顶住输出。
2. 加小滤波电容（模拟法，牺牲速度）。
3. 用时钟同步——在时钟沿采样，毛刺早已消失（同步设计的最大好处）。

记忆点：$BC$ 就是 $AB$ 和 $\overline{A}C$ 的共识项（consensus term）。"竞争冒险来自'两条路径抢'，冗余项的作用是'第三条路顶上'"。

示例

例 1：三变量卡诺图化简（完整过程）

化简 $F(A,B,C)=\sum m(1,2,3,5,7)$。

第一步：列真值表 / 定最小项。

$ABC$	编号	$F$
000	0	0
001	1	1
010	2	1
011	3	1
100	4	0
101	5	1
110	6	0
111	7	1

第二步：填卡诺图。

              BC
              00    01    11    10
        A 0 │  0  │  1  │  1  │  1  │    ← m0  m1  m3  m2
          1 │  0  │  1  │  1  │  0  │    ← m4  m5  m7  m6

第三步：圈。

              圈①（4 格，竖着两列 01 与 11，两行都要）
                     ↓    ↓
              00    01    11    10
        A 0 │  0  │[ 1 ]│[ 1 ]│  1  │
          1 │  0  │[ 1 ]│[ 1 ]│  0  │
                     ↑    ↑
              圈②（2 格，A=0 行的 11 与 10）
                          └────┘

• 圈①：$BC=01$ 与 $11$ 两列、$A$ 的两行 → 覆盖 $m_1,m_3,m_5,m_7$，共 4 格。$B$ 在 01 和 11 中都为 1（不变），$A$、$C$ 都变过（消掉）→ 得 $C$
• 圈②：$A=0$ 行的 $BC=11$ 和 $10$ → 覆盖 $m_3,m_2$，共 2 格。$A=0$ 不变、$B=1$ 不变、$C$ 变过 → 得 $\overline{A}B$

第四步：写结果。

$$\boxed{{\displaystyle F=C+\overline{A}B}}$$

第五步：真值表验证。

$ABC$	$C$	$\overline{A}B$	$F$	原值	一致
000	0	0	0	0	✓
001	1	0	1	1	✓
010	0	1	1	1	✓
011	1	1	1	1	✓
100	0	0	0	0	✓
101	1	0	1	1	✓
110	0	0	0	0	✓
111	1	0	1	1	✓

结论：$F=C+\overline{A}B$。从 5 个乘积项、15 个文字压到 2 项、3 个文字。

对照代数法（感受一下差距）：

$$\begin{array}{rl}F& =\overline{A}\overline{B}C+\overline{A}BC+A\overline{B}C+ABC\\ & =\underset{=\overline{A}C}{\underbrace{\overline{A}C(\overline{B}+B)}}+\underset{=AC}{\underbrace{AC(\overline{B}+B)}}\\ & =C(\overline{A}+A)=C\text{← 只得到 }C\text{，漏了 }\overline{A}B\text{ 覆盖的 }{m}_2\end{array}$$

还要再补 $m_2$ 那一项。代数法容易漏，卡诺图不会漏。

例 2：四变量卡诺图与四角相邻（完整过程）

化简 $F(A,B,C,D)=\sum m(0,2,5,7,8,10,13,15)$。

第一步：填图。 行按 $AB$ = 00, 01, 11, 10；列按 $CD$ = 00, 01, 11, 10。

编号	$ABCD$	位置	$F$
0	0000	行00×列00	1
2	0010	行00×列10	1
5	0101	行01×列01	1
7	0111	行01×列11	1
8	1000	行10×列00	1
10	1010	行10×列10	1
13	1101	行11×列01	1
15	1111	行11×列11	1

                    CD
                    00    01    11    10
              AB 00│  1  │  0  │  0  │  1  │  ← 四角的上两角
                 01│  0  │  1  │  1  │  0  │
                 11│  0  │  1  │  1  │  0  │  ← 中间 2×2
                 10│  1  │  0  │  0  │  1  │  ← 四角的下两角
                    ↑                 ↑
                    四角（可圈成一圈）

第二步：圈。

• 圈①（4 格）：四个角 $m_0,m_2,m_8,m_{10}$。它们共同点：$B=0$ 且 $D=0$，$A$、$C$ 都变过 → $B\overline{D}$，即 $\overline{B}\overline{D}$
• 圈②（4 格）：中间 2×2 块 $m_5,m_7,m_{13},m_{15}$。共同点：$B=1$ 且 $D=1$ → $BD$

第三步：结果。

$$\boxed{{\displaystyle F=\overline{B}\overline{D}+BD}}$$

第四步：验证。 这是 $B$ 和 $D$ 的同或（XNOR）：

$$B\odot D=\overline{B\oplus D}=\overline{B}\overline{D}+BD✓$$

逐项检查：$m_0(B=0,D=0)$ → $\overline{B}\overline{D}=1$ ✓；$m_5(B=1,D=1)$ → $BD=1$ ✓；$m_5$ 的补 $m_4(B=1,D=0)$ 是否被误覆盖？$\overline{B}\overline{D}=0$、$BD=0$ → $F=0$ ✓（$m_4$ 确实不在集合里）。

结论：$F=\overline{B}\overline{D}+BD$，8 个最小项压成 2 个 2 文字项。

这道题的价值在于：它必须用"四角相邻"才能圈出来。不掌握这条规则的人会在四角各圈一个小圈，得到 4 项 12 文字。"四角相邻"是卡诺图最关键的非直觉规则。

例 3：含无关项的化简（完整过程）

化简 $F(A,B,C,D)=\sum m(0,1,2,5,8,9,10)+\sum d(3,11,14,15)$。

第一步：填图（X 表示无关项）。

                    CD
                    00    01    11    10
              AB 00│  1  │  1  │  X  │  1  │
                 01│  0  │  1  │  0  │  0  │
                 11│  0  │  0  │  X  │  X  │
                 10│  1  │  1  │  X  │  1  │

第二步：圈。

• 圈①（8 格）：$AB$ = 00 行与 10 行（即 $B=0$）的所有 4 列。这 8 格里 6 个是真 1、2 个是 X → 全部可用 → $\overline{B}$
• 圈②（2 格）：$A=0$ 行（AB = 00 或 01）与 $CD=01$ 列 → $m_1,m_5$。共同点 $A=0,C=0,D=1$ → $\overline{A}\overline{C}D$

第三步：结果。

$$\boxed{{\displaystyle F=\overline{B}+\overline{A}\overline{C}D}}(\text{2 项，4 个文字})$$

第四步：不用无关项的对照。

只用真 1 圈：

• $\overline{B}\overline{D}$：覆盖 $m_0,m_2,m_8,m_{10}$
• $\overline{B}\overline{C}$：覆盖 $m_0,m_1,m_8,m_9$
• $\overline{A}\overline{C}D$：覆盖 $m_1,m_5$

$$F=\overline{B}\overline{D}+\overline{B}\overline{C}+\overline{A}\overline{C}D(\text{3 项，7 个文字})$$

第五步：结论对比。

方案	表达式	项数	文字数
利用无关项	$\overline{B}+\overline{A}\overline{C}D$	2	4
不用无关项	$\overline{B}\overline{D}+\overline{B}\overline{C}+\overline{A}\overline{C}D$	3	7

文字数从 7 降到 4，省了一个门。 这就是无关项的价值——它把原本"必须分开圈"的格子粘在一起，让圈能长得更大。

验证正确性：只需检查真 1 的格是否都被覆盖（X 格取什么值无所谓）。

• $m_0,m_2,m_8,m_{10}$（$B=0$）→ $\overline{B}=1$ ✓
• $m_1,m_9$（$B=0$）→ $\overline{B}=1$ ✓
• $m_5$（$B=1$）→ $\overline{A}\overline{C}D=1$ ✓ 全部覆盖，且没有真 0 的格子被误覆盖（$m_4,m_6,m_7,m_{12},m_{13}$ 代入都为 0）✓

例 4：竞争冒险与冗余项（完整过程）

电路实现 $F=AB+\overline{A}C$。判断是否存在静态冒险，若有则给出消除方案。

第一步：找"理论恒 1"的条件。

令 $B=C=1$：

$$F=A\cdot 1+\overline{A}\cdot 1=A+\overline{A}=1$$

与 $A$ 无关。

第二步：分析实际路径。 两条路径：

      A ──┬── AND ──┐
          │         ├── OR ── F
          └── NOT ──→ AND ──┘
                    ↑
                    C ──

$A$ 到 $F$ 有两条路：一条经 AND（1 级），一条经 NOT 再 AND（2 级）。延迟差 ≈ 一个 NOT 门的 $t_{pd}$。

第三步：毛刺的机理。 当 $A$ 从 1 → 0：

• 路径①的 $AB$ 先掉（快）
• 路径②的 $\overline{A}C$ 后起（慢，要等 NOT 翻转）

中间有一个"两条都为 0"的窗口 → $F$ 冒出一个负毛刺。

第四步：消除——加共识项。 卡诺图上把 $AB$ 和 $\overline{A}C$ 的圈额外用一个圈连起来：

$$\boxed{{\displaystyle F=AB+\overline{A}C+BC}}$$

验证冗余项确实冗余：用冗余律 $AB+\overline{A}C+BC=AB+\overline{A}C$ ✓

第五步：验证毛刺被消除。 当 $B=C=1$ 时，$BC=1$ 恒定，不论 $A$ 怎么变，$F=BC+\cdots =1$ 都顶住。✓

结论：$BC$ 是共识项，加它不改逻辑功能，但消除了竞争冒险。代价是多一个 AND 门和 OR 门的一个输入。

工程上的取舍：异步电路必须处理冒险；同步电路一般不管——因为毛刺在时钟沿到来前早就消失了。这就是"同步设计更安全"的一个具体理由。

用程序复算

#include <stdio.h>

/* 三个例子：真值表直接写出来验证 */
static int ex1(int A, int B, int C) { return C + (!A && B); }
static int ex1_ref(int A, int B, int C) {
    int m = A*4 + B*2 + C;
    return (m==1||m==2||m==3||m==5||m==7);
}
static int ex2(int A, int B, int C, int D) { return (!B && !D) || (B && D); }
static int ex2_ref(int A, int B, int C, int D) {
    int m = A*8 + B*4 + C*2 + D;
    return (m==0||m==2||m==5||m==7||m==8||m==10||m==13||m==15);
}
static int ex3(int A, int B, int C, int D) { return (!B) || (!A && !C && D); }
static int ex3_ref(int A, int B, int C, int D) {
    int m = A*8 + B*4 + C*2 + D;
    return (m==0||m==1||m==2||m==5||m==8||m==9||m==10);
}

int main(void) {
    printf("--- 例1 F=C+A'B vs Sm(1,2,3,5,7) ---\n");
    int bad = 0;
    for (int i = 0; i < 8; i++) {
        int A = i>>2 & 1, B = i>>1 & 1, C = i & 1;
        int a = ex1(A,B,C), b = ex1_ref(A,B,C);
        if (a != b) { bad++; printf("  MISMATCH %d%d%d: %d vs %d\n", A,B,C,a,b); }
    }
    printf("  %s\n", bad ? "FAIL" : "PASS");

    printf("--- 例2 F=B'D'+BD vs Sm(0,2,5,7,8,10,13,15) ---\n");
    bad = 0;
    for (int i = 0; i < 16; i++) {
        int A = i>>3 & 1, B = i>>2 & 1, C = i>>1 & 1, D = i & 1;
        if (ex2(A,B,C,D) != ex2_ref(A,B,C,D)) {
            bad++; printf("  MISMATCH %d%d%d%d\n", A,B,C,D);
        }
    }
    printf("  %s\n", bad ? "FAIL" : "PASS");

    printf("--- 例3 F=B'+A'C'D vs Sm(0,1,2,5,8,9,10) + d(3,11,14,15) ---\n");
    bad = 0;
    int dc[16] = {0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1};
    for (int i = 0; i < 16; i++) {
        int A = i>>3 & 1, B = i>>2 & 1, C = i>>1 & 1, D = i & 1;
        int a = ex3(A,B,C,D), b = ex3_ref(A,B,C,D);
        if (dc[i]) {                       /* 无关项：任意值都合法 */
            printf("  m%-2d 无关项 -> %d\n", i, a);
        } else if (a != b) {
            bad++; printf("  MISMATCH m%d: %d vs %d\n", i, a, b);
        }
    }
    printf("  %s\n", bad ? "FAIL" : "PASS");

    printf("--- 例4 冒险冗余项 BC 不改功能 ---\n");
    bad = 0;
    for (int i = 0; i < 8; i++) {
        int A = i>>2 & 1, B = i>>1 & 1, C = i & 1;
        int f1 = (A && B) || (!A && C);
        int f2 = (A && B) || (!A && C) || (B && C);
        if (f1 != f2) { bad++; printf("  MISMATCH %d%d%d\n", A,B,C); }
    }
    printf("  F=AB+A'C 与 F=AB+A'C+BC 等价: %s\n", bad ? "FAIL" : "PASS");

    printf("--- 德摩根验证 ---\n");
    bad = 0;
    for (int i = 0; i < 4; i++) {
        int A = i>>1 & 1, B = i & 1;
        if (!(A && B) != (!A || !B)) bad++;
        if (!(A || B) != (!A && !B)) bad++;
    }
    printf("  %s\n", bad ? "FAIL" : "PASS");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

from itertools import product

def check(name, fn, ref, n):
    bad = []
    for bits in product((0, 1), repeat=n):
        if fn(*bits) != ref(*bits):
            bad.append(bits)
    print(f"  {name}: {'PASS' if not bad else 'FAIL ' + str(bad)}")

print("--- 例1 F = C + A'B ---")
check("F(A,B,C)=C+A'B", lambda A,B,C: int(C or (not A and B)),
      lambda A,B,C: int(A*4+B*2+C in (1,2,3,5,7)), 3)

print("--- 例2 F = B'D' + BD ---")
check("F(A,B,C,D)", lambda A,B,C,D: int((not B and not D) or (B and D)),
      lambda A,B,C,D: int(A*8+B*4+C*2+D in (0,2,5,7,8,10,13,15)), 4)

print("--- 例3 F = B' + A'C'D ---")
ms = {0,1,2,5,8,9,10}
dc = {3,11,14,15}
bad = []
for bits in product((0,1), repeat=4):
    A,B,C,D = bits
    val = int((not B) or (not A and not C and D))
    m = A*8+B*4+C*2+D
    if m in ms and val != 1: bad.append(("ms", m))
    if m not in ms and m not in dc and val != 0: bad.append(("zero", m))
print(f"  F=B'+A'C'D (无关项自由): {'PASS' if not bad else 'FAIL ' + str(bad)}")
print(f"  覆盖的真 1: {sorted(ms)}，全部命中")
print(f"  未用无关项的表达式 B'D'+B'C'+A'C'D 文字数 7 vs 用无关项 4")

print("--- 例4 冗余项 BC 不改功能 ---")
check("F=AB+A'C  vs  AB+A'C+BC",
      lambda A,B,C: int((A and B) or (not A and C)),
      lambda A,B,C: int((A and B) or (not A and C) or (B and C)), 3)

print("--- 德摩根 ---")
check("(AB)' = A'+B'", lambda A,B: int(not (A and B)),
      lambda A,B: int((not A) or (not B)), 2)
check("(A+B)' = A'B'", lambda A,B: int(not (A or B)),
      lambda A,B: int((not A) and (not B)), 2)

print("--- 分工项与最大项编号对应 ---")
S = (1,2,3,5,7)
print(f"  Sm{S} 等价于 PiM{tuple(sorted(set(range(8)) - set(S)))}")
print(f"  因为 M_i = m_i', 全集减 {(0,4,6)} 即补集")

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出（节选）：

--- 例1 F = C + A'B ---
  F(A,B,C)=C+A'B: PASS
--- 例2 F = B'D' + BD ---
  F(A,B,C,D): PASS
--- 例3 F = B' + A'C'D ---
  F=B'+A'C'D (无关项自由): PASS
  覆盖的真 1: [0, 1, 2, 5, 8, 9, 10]，全部命中
--- 例4 冗余项 BC 不改功能 ---
  F=AB+A'C  vs  AB+A'C+BC: PASS
--- 德摩根 ---
  (AB)' = A'+B': PASS
  (A+B)' = A'B': PASS
  Sm(1, 2, 3, 5, 7) 等价于 PiM(0, 4, 6)

考点

考点

1. 定律里最常考的三条

$$\text{分配律（布尔独有）: }A+BC=(A+B)(A+C)$$$$\text{吸收律: }A+AB=A,A(A+B)=A$$$$\text{冗余律（共识）: }AB+\overline{A}C+BC=AB+\overline{A}C$$

冗余律的双重身份：化简时用它去掉 $BC$；消冒险时用它加回 $BC$。同一个公式，两个方向都用。

2. 德摩根：硬件含义与最易错处

$$\overline{A\cdot B}=\overline{A}+\overline{B},\overline{A+B}=\overline{A}\cdot \overline{B}$$

• 易错：只把横线断一半，忘了同时换运算符（+ ↔ ·）
• 硬件意义：NAND = 输入取反的 OR，NOR = 输入取反的 AND
• 推论：任何 SOP 都能用 NAND–NAND 实现，任何 POS 都能用 NOR–NOR 实现

3. 最小项与最大项（编号方向别搞反）

$$M_i=\overline{m_i},\sum m(S)=\prod M(\overline{S}),\overline{S}=\text{全集}-S$$

验证：$\sum m(1,3,5,7)$ 对应 $\prod M(0,2,4,6)$。

易错：写最小项时忘了某个变量要取反。$m_5$ 在 $A,B,C$ 下是 $A\overline{B}C$（不是 $\overline{A}BC$）。判据：把表达式里的原变量当 1、反变量当 0，拼出的二进制等于编号。

4. 卡诺图的圈法规则（判分点）

规则	说明
只能圈 $2^k$ 格	不能圈 3、5、6、7 格
必须矩形	不能 L 形、不能对角
4 变量四角相邻	可圈成一圈
上下/左右边界相邻	可跨边界圈
圈可重叠	同一个 1 可被多个圈覆盖
圈越大越好	$2^k$ 格消掉 $k$ 个变量

必背的等价关系：

• 圈 2 格 → 消 1 个变量
• 圈 4 格 → 消 2 个变量
• 圈 8 格 → 消 3 个变量

5. 格雷码顺序（最高频的作图错误）

$\boxed{{\displaystyle \text{4 变量卡诺图的行列顺序是 }00,01,11,10}}$

不是 00, 01, 10, 11。写成二进制递增会让整个图失去意义。

自检：写下 $m_3=0011$ 时，行取 $AB=00$、列取 $CD=11$，列的第三列（不是第二列）。

6. 无关项的处理（常考）

• X 可与 1 一起圈，把圈扩大
• X 不能单独圈（必须有真 1 在圈内）
• X 不影响正确性验证：验证时只需检查"真 1 全被覆盖、真 0 全不被覆盖"
• 典型场景：BCD 码（1010–1111 是无关项）、多路复用器的未用通道、状态机的非法状态

7. 竞争冒险（★ 概念题高频）

产生条件：同一个输出有两条及以上路径，且它们的延迟不等。

典型形式：$F=A+\overline{A}$ 型（一个变量原反同时出现，且系数相同）→ 静态负冒险。

消除：

1. 卡诺图上加冗余圈（共识项）——最标准的答案
2. 加滤波电容（模拟法，慢）
3. 时钟同步采样（同步设计的天然免疫）

易错：化简后的最简式反而可能有冒险，而不化简的完整 SOP 一定没有（因为每个最小项都单独有一条路径顶住）。"最简"与"无冒险"是两个不同的优化目标。

8. 易错点清单

• 布尔代数套用普通代数：$A+A=A$（不是 $2A$），$A\cdot A=A$（不是 $A^2$），$1+1=1$
• 德摩根只改一半（断线不换符，或换符不断线）
• 以为 $A+BC=(A+B)(A+C)$ 是错的。它是对的，布尔代数独有的分配律
• 卡诺图列顺序写成 00,01,10,11
• 忘了"四角相邻"和"跨边界相邻"
• 圈里混入 0。只能圈 1（和 X）
• 无关项当强制 1。只能在"对你有利"时当 1
• 把"最简 SOP"当唯一答案。同一个函数的最简式可能不唯一（有几个同样大小的解）
• POS 写成 SOP 的编号。$\prod M(0,2,4,6)$ 里的编号是输出为 0 的编号，不是为 1 的

小结

• 布尔代数只有三种运算，但有一套和普通代数不同的定律；最容易踩的是 $A+A=A$ 和布尔独有的分配律 $A+BC=(A+B)(A+C)$。
• 德摩根是硬件实现的桥梁：$\overline{AB}=\overline{A}+\overline{B}$ 意味着 NAND 能搭一切。
• 最小项 $m_i$ 对应唯一一组输入；$M_i=\overline{m_i}$，$\sum m(S)=\prod M(\overline{S})$。
• 卡诺图把化简变成"圈"：行列表头必须按格雷码，只能圈 $2^k$ 格矩形，四角与边界相邻，圈越消变量越多。
• 无关项用来把圈做大，可当 1 也可当 0；验证时只看真 1 和真 0。
• SOP → NAND-NAND，POS → NOR-NOR，这是最省管的实现形式。
• 竞争冒险来自"多条路径延迟不等"；用共识项（卡诺图加冗余圈）消除；最简 ≠ 无冒险。

回到主线：L1 的硬前置第一关过了——我们已经会"把逻辑需求写成最小表达式"。

但表达式还不是电路。接下来要问：一个中文的"38 译码器"或者"8 选 1"，怎么变成具体的门级连线？多个这样的模块怎么拼成 ALU？ 这就是下一篇——组合逻辑电路：编码器、译码器、数据选择器，以及"任意函数都能用译码器或数据选择器实现"这条重磅结论。

下一篇：组合逻辑电路：编码器、译码器、数据选择器