第02课 · 布尔代数

基础Verilog卡诺图

📌 学习目标：掌握布尔代数基本定律、代数化简方法、卡诺图（Karnaugh Map）化简，并通过 Verilator 验证化简前后的逻辑等价性。

一、布尔代数基本定律

布尔代数是数字电路的数学基础。George Boole 于 1854 年创立，Claude Shannon 于 1938 年将其应用于开关电路。

1.1 基本公理

A · 0 = 0   (与0)
A · 1 = A   (与1)
A + 0 = A   (或0)
A + 1 = 1   (或1)

1.2 互补律

A · Ā = 0 (互斥)
A + Ā = 1 (完备)

1.3 幂等律

A · A = A
A + A = A

1.4 交换律 & 结合律 & 分配律

A · B = B · A   (交换)
A + B = B + A
(A·B)·C = A·(B·C)   (结合)
A·(B+C) = A·B + A·C   (分配)
A + B·C = (A+B)·(A+C)   (对偶分配!)

1.5 德摩根定律（De Morgan's Law）

¬(A · B) = Ā + B̄
¬(A + B) = Ā · B̄

德摩根定律是数字电路设计中最常用的化简工具，它建立了 AND 和 OR 之间的对偶关系。

1.6 吸收律 & 消除律

A + A·B = A (吸收)
A·(A + B) = A
A + Ā·B = A + B (消除)
A·(Ā + B) = A·B

二、代数化简实例

例1：化简 F = A·B + A·B̄

F = A·B + A·B̄
= A·(B + B̄) — 提取公因子 A
= A·1 — 互补律
= A

例2：化简 F = A·B̄·C + A·B·C + Ā·B·C

F = A·C·(B̄ + B) + Ā·B·C
= A·C + Ā·B·C
= C·(A + Ā·B)
= C·(A + B) — 消除律

三、卡诺图化简

卡诺图（K-Map）是一种图形化化简方法，通过相邻最小项的合并来简化布尔函数。

3.1 两变量卡诺图

化简 F(A,B) = Σm(1,3) = Ā·B + A·B

AB	00	01	11	10
F	0	1	1	0

合并 m1,m3 → F = B

3.2 三变量卡诺图

化简 F(A,B,C) = Σm(0,2,4,6)

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

合并四角 → F = C̄

3.3 四变量卡诺图

化简 F(A,B,C,D) = Σm(0,1,2,5,8,9,10)

CD\AB	00	01	10
00	1	0	1
01	1	1	1
11	0	0	0
10	1	0	1

合并组 → F = C̄·D̄ + B̄·D̄ + Ā·C̄·D（需要进一步检查覆盖）

四、Verilog 验证

我们验证：化简前后的布尔函数在所有输入组合下输出一致。

// boolean_simplify.v — 布尔代数化简验证
module boolean_simplify (
    input  a, b, c,
    output f_original,
    output f_simplified
);

    // 例2的原始函数: F = A·B̄·C + A·B·C + Ā·B·C
    assign f_original = (a & ~b & c) | (a & b & c) | (~a & b & c);

    // 化简后: F = C·(A + B)
    assign f_simplified = c & (a | b);

endmodule

// tb_boolean.v — 布尔代数测试台
module tb_boolean;

    reg  a, b, c;
    wire f_orig, f_simp;

    boolean_simplify uut (
        .a(a), .b(b), .c(c),
        .f_original(f_orig), .f_simplified(f_simp)
    );

    integer pass = 0, fail = 0;

    initial begin
        for (integer i = 0; i < 8; i = i + 1) begin
            {a, b, c} = i[2:0];
            #10;
            if (f_orig !== f_simp) begin
                $display("FAIL: a=%b b=%b c=%b | orig=%b simp=%b",
                    a, b, c, f_orig, f_simp);
                fail = fail + 1;
            end else
                pass = pass + 1;
        end
        $display("========================================");
        $display("布尔化简验证: PASS=%0d FAIL=%0d", pass, fail);
        if (fail == 0) $display("✅ 化简前后逻辑等价，卡诺图化简正确！");
        else $display("❌ 化简结果不一致！");
        $display("========================================");
        $finish;
    end

endmodule

五、德摩根定律验证

用 Verilog 验证德摩根定律：¬(A·B) = Ā + B̄

// demorgan.v — 德摩根定律验证
module demorgan (
    input  a, b,
    output lhs,   // ~(a & b)
    output rhs    // ~a | ~b
);
    assign lhs = ~(a & b);
    assign rhs = ~a | ~b;
endmodule

module tb_demorgan;
    reg a, b;
    wire lhs, rhs;
    demorgan uut (.a(a), .b(b), .lhs(lhs), .rhs(rhs));
    integer pass=0, fail=0;
    initial begin
        for (integer i=0; i<4; i=i+1) begin
            {a,b} = i[1:0]; #10;
            if (lhs !== rhs) begin
                $display("FAIL: a=%b b=%b lhs=%b rhs=%b", a, b, lhs, rhs);
                fail=fail+1;
            end else pass=pass+1;
        end
        $display("德摩根定律: PASS=%0d FAIL=%0d", pass, fail);
        if (fail==0) $display("✅ 德摩根定律验证通过！");
        $finish;
    end
endmodule

六、Verilator 编译命令

# 编译布尔化简验证
verilator --cc boolean_simplify.v --exe tb_boolean.v \
  --build --top-module tb_boolean
./obj_dir/Vtb_boolean

# 编译德摩根定律验证
verilator --cc demorgan.v --exe tb_demorgan.v \
  --build --top-module tb_demorgan
./obj_dir/Vtb_demorgan

📊 预期输出：

========================================
布尔化简验证: PASS=8 FAIL=0
✅ 化简前后逻辑等价，卡诺图化简正确！
========================================
德摩根定律: PASS=4 FAIL=0
✅ 德摩根定律验证通过！

七、卡诺图化简规则总结

圈必须是 2ⁿ 个相邻的 1（1,2,4,8...）
相邻包括上下左右和首尾环绕
每个圈必须包含至少一个未被其他圈覆盖的 1
圈越大越好（项越少），圈数越少越好（项数越少）
Don't care（X）可以当作 1 来帮助合并

🤔 思考题：用卡诺图化简 F(A,B,C,D) = Σm(0,2,8,10,12,14) + Σd(4,6)

💡 提示：Don't care 项可以灵活利用来获得最大圈

🏆 成就解锁：布尔化简大师

✅ Verilator 仿真验证通过

✅ 布尔代数化简前后逻辑等价验证正确

✅ 德摩根定律验证通过

✅ 掌握卡诺图化简方法

🎯 下一目标：组合逻辑电路设计 → 第03课：组合逻辑

⬅️ 第01课：逻辑门第03课：组合逻辑 ➡️