组合逻辑(Combinational_Logic)电路没有状态和记忆，某些输入集的输出总是相同。

真值表(Truth Tables/TT)

image-20240730212102555

TT Example #1: 1 iff one (not both) a,b=1

image-20240730212141287

这个也是后面会说到的XOR，trick xor treat!

使用a和b的关系简化真值表：

  • 当a为0时，输出y等于b。
  • 当a为1时，输出y等于not b。

TT Example #2: 2-bit adder

image-20240730212241135

输入A和B分别有两位，输出C有三位（包括进位）。

总共需要16行（4位输入）。

TT Example #3: 32-bit unsigned adder

image-20240730212250551

输入A和B分别有32位，输出C需要33位（包括进位）。

真值表的方法在这种情况下可能不适用，需考虑其他构建方法。

TT Example #4: 3-input majority circuit

image-20240730212302805

逻辑门

image-20240730213128404

image-20240730213117887

如何记忆：image-20240730213100760

2-input gates extend to n-inputs

image-20240730213307305

对于XOR的N-input数abc中有多少个1，奇数个1最终结果就是1

Truth Table -> Gates (e.g., majority circ.)

image-20240730213406554

Truth Table -> Gates (e.g., FSM circuit)

image-20240730213449047

布尔代数

image-20240730213504382

  • + = OR
  • · = AND
  • $\bar{x}$ = NOT

Boolean Algebra (e.g., for majority fun.)

image-20240730213934732

Boolean Algebra (e.g., for FSM)

image-20240730213951120

电路&代数简化

image-20240730214021676

布尔代数的规则

image-20240730214032704

标准型(Canonical forms)

image-20240730214050410

image-20240730214056207

总结

image-20240730214125385

我们可以互相转化，除了TT转成GD