1 基本概念
1.1 定义与表示
布尔电路是一种由逻辑门通过导线连接而成的有向无环图结构，其输入输出均为二进制值（0或1）。每个逻辑门实现一个基本的布尔运算，整个电路则计算一个复合布尔函数。
1.1.1 输入与输出变量
输入变量是电路接收的外部二进制信号，通常用x₁、x₂、...、xₙ表示；输出变量是电路计算产生的结果，用y₁、y₂、...、yₘ表示。每个变量取值0或1，对应电路中的低电平或高电平。
1.1.2 电路图与布尔表达式
电路图通过图形符号表示逻辑门及其连接关系，直观展示信号流向。布尔表达式则用代数符号描述电路功能，例如输出y = (x₁ ∧ x₂) ∨ (¬x₃) 表示先对x₁和x₂做与运算，再与x₃的非做或运算。两者可互相转换。
1.2 逻辑门基础
逻辑门是布尔电路的基本构建单元，每个门实现一个简单的逻辑运算。
1.2.1 基本门：与门、或门、非门
与门（AND门）输出为1当且仅当所有输入均为1；或门（OR门）输出为1当至少一个输入为1；非门（NOT门）输出为输入的取反。这三个门构成逻辑运算的完备集。
1.2.2 复合门：与非门、或非门、异或门、同或门
与非门（NAND门）是与门加非门，或非门（NOR门）是或门加非门，两者均可单独构造任意布尔函数。异或门（XOR门）输出为1当输入不同，同或门（XNOR门）输出为1当输入相同。复合门在VLSI设计中更为常用。
1.2.3 门延迟与扇入扇出
门延迟是信号通过逻辑门所需的时间，决定了电路的最高工作频率。扇入指一个门允许的最大输入端口数，扇出指一个门可驱动的最大负载门数。过高的扇入或扇出会导致信号衰减和延迟增加。
1.3 布尔函数与真值表
布尔函数描述从输入向量到输出值（0或1）的映射关系。真值表以表格形式列出所有输入组合对应的输出，是理解布尔函数的直观工具。
1.3.1 最小项与最大项
最小项是与所有输入变量（或其非）的乘积项，使真值表中唯一一行输出为1；最大项是或所有输入变量（或其非）的和项，使真值表中唯一一行输出为0。两者互相补充。
1.3.2 标准形式：SOP与POS
积之和（SOP）形式将若干最小项相或，用于直接实现真值表；和之积（POS）形式将若干最大项相与，功能等效。SOP更适合与或门电路实现，POS更适合或与门电路实现。
2 电路结构与分类
2.1 组合逻辑电路
组合逻辑电路的输出仅由当前输入决定，不涉及存储状态。
2.1.1 全加器与半加器
半加器对两个二进制位求和，产生和与进位输出；全加器增加第三个输入（低位进位），实现完整一位加法。多个全加器级联构成多位加法器。
2.1.2 编码器与译码器
编码器将m个输入信号转换为n位二进制码（m≤2ⁿ），如8-3编码器；译码器将n位码转换为m个输出信号，如3-8译码器，常用于地址解码。
2.1.3 多路选择器与多路分配器
多路选择器（MUX）从多个数据输入中选一路到输出，由选择线控制；多路分配器（DEMUX）将单路输入分配到多个输出之一。两者实现数据路由功能。
2.2 时序逻辑电路
时序逻辑电路包含存储元件，输出由当前输入和历史状态共同决定。
2.2.1 锁存器与触发器
锁存器是电平触发的基本存储单元，如SR锁存器、D锁存器；触发器是边沿触发的存储单元，如D触发器、JK触发器，常用于同步电路中。
2.2.2 寄存器与移位寄存器
寄存器由一组触发器构成，用于存储多位数据；移位寄存器在时钟驱动下将数据逐位移动，可用于串行到并行转换、延迟等。
2.2.3 有限状态机（FSM）的电路实现
FSM由状态寄存器、下一状态逻辑和输出逻辑三部分组成。根据输出类型分为米利机（输出与当前状态和输入相关）和摩尔机（输出仅与当前状态相关）。
2.3 同步与异步电路
2.3.1 时钟信号与同步设计
同步电路使用全局时钟信号同步所有触发器的动作，确保状态变化同时发生。时钟频率受最差路径延迟限制，设计方法成熟可靠。
2.3.2 异步电路的风险与竞争
异步电路无全局时钟，状态变化由事件驱动。易发生竞争（多个信号变化顺序不确定）和冒险（毛刺信号传播），设计复杂但功耗低、速度快。
3 分析与优化
3.1 布尔代数化简
通过数学变换减少逻辑门的数量和电路复杂度。
3.1.1 基本定律（交换律、结合律、分配律、德摩根律）
交换律使门输入可交换，结合律改变运算分组，分配律展开或合并项，德摩根律将与或运算互转取反。这些定律是化简的基础。
3.1.2 卡诺图（Karnaugh Map）化简
卡诺图将真值表转化为二维网格，相邻格子代表只变一个输入变量的项。通过圈选最大矩形组（大小为2的幂）得到最简SOP或POS形式，适用于输入变量数小于等于6的情况。
3.1.3 奎因-麦克拉斯基（Quine-McCluskey）算法
一种系统化化简算法，逐级合并相邻项，找出所有质蕴含项，再选择覆盖所有最小项的最小集合。适合计算机实现且可处理更多变量。
3.2 电路复杂度度量
3.2.1 电路大小（门数量）与深度（最长路径）
电路大小指逻辑门总数，影响芯片面积与功耗。电路深度是从输入到输出的最长门级数，决定最差路径延迟，约束最高工作频率。
3.2.2 时间复杂度与空间复杂度
电路问题的时间复杂度通常用深度衡量，空间复杂度用大小衡量。在电路复杂度理论中，一个函数族的电路大小决定了其属于哪类复杂度（如P/poly）。
3.3 优化策略
3.3.1 逻辑综合与工艺映射
逻辑综合将行为级描述转换为与工艺无关的逻辑网表，应用化简算法减少门数。工艺映射将网表映射到特定工艺库的单元，考虑时序和面积约束。
3.3.2 功耗优化与静态时序分析
功耗优化通过降低电源电压、减少翻转活动（门控时钟、数据编码）实现。静态时序分析在不仿真的情况下计算所有路径的延迟，确认是否满足时钟约束。
4 理论扩展与应用
4.1 布尔电路与图灵机
4.1.1 电路复杂度理论（P/poly类）
P/poly类指可由多项式规模电路族计算的判定问题，包含所有P类问题，且包含某些非P问题。电路族是研究问题非均匀计算能力的基本模型。
4.1.2 电路族与均匀性
均匀电路族要求存在图灵机在多项式时间内生成第n个电路的描述，与非均匀电路族（无限定）相比更接近实际可计算性。均匀性保证了电路与算法的等价性。
4.2 计算模型中的布尔电路
4.2.1 非确定性布尔电路
允许电路有“猜测”输入，类似于非确定性图灵机。该模型用于研究NP问题与电路复杂度的关系，如能否用多项式电路解决NP问题。
4.2.2 博罗梅安电路与单调电路
博罗梅安电路是特殊拓扑结构，三个门相互缠绕却可独立移去。单调电路不使用非门（仅用与门和或门），研究此类电路的复杂度有助于理解运算的单调性。
4.3 实际应用
4.3.1 数字集成电路（VLSI）设计
布尔电路是VLSI设计的理论基础，从加法器、乘法器到GPU中的整数运算单元均基于此。现代EDA工具自动完成从RTL到版图的综合。
4.3.2 密码学中的安全多方计算（混淆电路）
混淆电路将布尔电路加密，使计算方在不知道输入的情况下仍能正确计算结果。这是安全多方计算的核心技术之一，应用于数字拍卖、隐私保护机器学习等领域。
4.3.3 人工智能中的可满足性（SAT）求解器
SAT求解器将布尔电路转化为CNF（合取范式）问题进行求解，是现代形式化验证和AI推理的基础。冲突驱动子句学习（CDCL）算法极大提升了求解效率。
5 设计与实现工具
5.1 硬件描述语言（HDL）
HDL用文本描述数字电路的结构和行为，支持层次化设计。
5.1.1 Verilog 与 VHDL 基础
Verilog语法类似C语言，广泛用于ASIC验证；VHDL更强调强类型和并发性，常用于FPGA设计。两者均为IEEE标准，功能等效。
5.1.2 行为级、数据流级与门级建模
行为级用过程语句（always/process）描述功能，数据流级用连续赋值（assign）描述逻辑方程，门级实例化标准逻辑门单元。高抽象级便于验证，低抽象级控制实现细节。
5.2 逻辑综合工具
5.2.1 综合流程：RTL到门级网表
工具首先解析RTL代码，进行文法与语义检查，然后通过优化（恒值传播、资源共享）和工艺映射生成门级网表。最终输出带时序约束的物理网表。
5.2.2 典型软件（如Synopsys Design Compiler）
Synopsys Design Compiler是业界主流综合工具，支持多目标优化（面积、速度、功耗）。其他工具包括Cadence Genus、Yosys（开源）等。
5.3 仿真与验证
5.3.1 功能仿真与时序仿真
功能仿真验证逻辑行为正确，不包含门延迟信息。时序仿真将门延迟反标到网表，检查是否满足建立时间、保持时间约束。
5.3.2 形式化验证与等价性检查
形式化验证基于数学证明检查电路属性（如安全性、活性）。等价性检查对比两个网表是否功能一致，常用于综合前后验证和工程变更。
6 常见问题与趣谈
6.1 布尔电路中的“冒烟测试”
“冒烟测试”一词源于硬件测试的“真·冒烟”——当电路接线有误或电源短路时，芯片可能过热冒烟。如今在数字设计中，冒烟测试指简单通断检查，例如确认电源和地之间无短路。
6.2 计算机硬件中的“魔法”：从晶体管到微处理器
一个现代CPU包含数十亿个晶体管，它们并非独立的魔法粒子，而是由大量布尔电路（如加法器、寄存器、有限状态机）有机组合而成。每个晶体管实现的开关逻辑，最终呈现出能运行操作系统、玩“推箱子”游戏的神奇能力。
6.3 布尔电路与推箱子游戏的不解之缘
推箱子游戏（Sokoban）的每一步操作都可编码为布尔可满足性问题（SAT实例）。玩家从起点到目标的通路，在布尔电路的世界里就是一组变量的赋值，求解器通过搜索所有可能的“箱子移动序列”来找出解。这也说明，即便是电子游戏里的“推箱子”路径规划，其背后的数学本质与布尔电路竟如此亲近。