逻辑代数基础

基本的逻辑门有3种: 与 (AND) , 或 (OR) , 非 (NOT) 三种. 常见的逻辑门即其符号如下:













若不考虑对信号的复制, 也即忽略复制门 (FANOUT) 这种门. AND, OR, NOT中的两者可以构成一个通用门集合, 其他的逻辑运算门都可以用这个集合构造出来. 比如异或 (XOR) , 其真值表为:

A B XOR
0 0 0
1 0 1
0 1 1
1 1 0

我们可以得出 XOR=(A'B')'(AB)', 用 AND 和 NOT 实现的电路如下:

XOR, for iCircuit

  • 0 · A = 0 ( · 表示 AND )
  • 1 · A = A
  • A · A = A
  • A · A' = 0
  • A · B = B · A ( AND 的交换律 )
  • A · ( B · C ) = ( A · B ) · C ( AND 的结合律 )
  • A · ( B + C ) = (A · B) + (A · C)
  • ( A · B )' = A' + B' ( 摩根定理 )
  • (A')' = A
  • 1' = 0; 0' = 1
  • 1 + A = 1 ( + 表示 OR )
  • 0 + A = A
  • A + A = A
  • A + A' = 1
  • A + B = B + A ( OR 的交换律 )
  • A + ( B + C ) = ( A + B ) + C ( OR 的结合律 )
  • A + B · C = ( A + B )( A + C )
  • ( A + B )' = A' · B' ( 摩根定理 )
  • A + A · B = A · ( 1 + B ) = A
  • A · B' + A · B = A · ( B + B' ) = A
  • A + A' · B = A · ( B + B' ) + A' · B = A · B + A · B' + A' · B = A · B + A · B + A · B' + A' · B = A · ( B + B' ) + B ( A + A' ) = A + B
  • A · ( A + B ) = A + A · B = A · ( B + B' ) + A · B = A · B + A · B' = A

代入定理

在任何一个包含变量A的逻辑等式中, 若以另外一个逻辑式代入式中所有A的位置, 则等式仍然成立.
比如: A + A' · B = A + B, 如果用 B + C 作为一个整体代替 所有的A, 等式是仍然成立的.

反演定理

对于任意一个逻辑式Y, 若将其中所有的 “·” 换成 “+”, “+“换成”·”, 0换成1, 1换成0, 原变量换成反变量, 反变量换成原变量, 则得到的结果称为对欧式, 实际上就是Y'. 比如前面的摩根定理就是反演定理的一个很好的例子. 反演定理反映的是与和或两个基本逻辑运算的对称性.

对偶定理

若两逻辑式相等, 则它们的对偶式也相等, 这就是对偶定理. 对偶式实际上就是原式的非. 比如: A = B, 则 A' = B'.这是很显然的.

逻辑函数有两种标准表示方法, 分别为“最小项之和”和“最大项之积”.

最小项和最大项

  • 最小项: 在n变量逻辑函数中, 若m为包含n个因子的乘积项, 且这n个变量均以原变量A或反变量A'的形式在m中出现一次, 则称m为该组变量的最小项. 比如: 由A和B两个逻辑变量构成的逻辑函数的所有最小项为AB, AB', A'B, A'B'.
  • 最大项: 在n变量逻辑函数中, 若M为n个变量之和, 而且这n个变量均以原变量或反变量的形式在M中出现一次, 则称M为该组变量的最大项. 比如: 由A和B两个逻辑变量构成的逻辑函数的所有最大项为A+B, A+B',A'+B,A'+B'.
  • 可以证明, n变量的最小项集合和n变量的最大项集合分别构成两个完备集, 可以描述所有n变量逻辑函数.

最小项之和

一个最小项中, 如果有一个变量 (可能是原变量也可能是反变量) 为逻辑0, 则整个项就是逻辑0. 这意味着对于一个最小项来说, 使其取逻辑1的变量取值组合只有唯一一种. 如果我们把所有使得逻辑函数f为逻辑1的自变量取值组合找出来, 然后找出这些组合对应的值为逻辑1的最小项, 将它们相加, 即进行或运算, 即构成了这个逻辑函数f. 因为所有使得逻辑函数f为逻辑1的情况都囊括进来了, 其他的自变量组合将使得逻辑函数f输出逻辑0. 这也是为什么所有n变量最小项构成的集合是描述n变量逻辑函数的完备集.

最大项之积

类似地, 一个最大项对应取值为逻辑0的变量取值组合是唯一的. 这样, 我们只要把逻辑函数f为逻辑0的所有自变量取值组合找出来, 再找出它们对应的最大项, 然后将这些最大项相乘, 即进行与运算, 就构造出了逻辑函数f. 同样地, 这种描述方式也是完备的.

逻辑函数的变换

逻辑函数的变换基本上依赖一下几条公式:

  • 摩根定理的两个公式: ( A · B )' = A' + B' 和 ( A + B )' = A' · B'
  • A = A · ( B + B' )

方法一: 公式化简法

顾名思义, 利用前面提及的公式进行化简, 需要一定的技巧. 很多书讲的五花八门的方法, 如吸收法, 配项法, 消项法等, 本质上都是公式化简法, 没什么区别. 比如: 对于一个n变量的逻辑函数, 其中一些最小项可能不包含某些自变量, 这时我们要利用 A = A · ( B + B' ) 将其拓展至包含所有自变量, 然后使用公式A · ( B + B' ) = A 和 A + A · B = A, 将一些可以合并的项进行合并.

方法二: 卡诺图化简法

可以画图来化简, 这种方法最为直观. 关键是操作简单, 比较无脑, 一旦学会, 屡试不爽8-)

第一步: 构造卡诺图

如下图是二到五变量最小项的卡诺图.

有几个关键点:

  1. 逻辑函数改写为最小项之和的形式
  2. 将变量分配到两个轴向上: 比如3变量ABC, 将A分配到列方向上, 将BC分配到行方向上
  3. 每个方向上, 相邻最小项之间只有一位是不同的, 比如000和001只有第一位是不同的, 其他位都是0. 这样你会发现, 最后一个最小项和第一个最小项也满足这个条件, 也即构成了一个循环, 这对后面的化简是非常有用的. 我们最好把这个看成一个被我们摊开了的圆柱侧面, 也即最后一个最小项和第一个最小项本来也是连在一起的.
  4. 现在一个表格已经构造好了, 每个格子对应一个完整的最小项, 填入这个最小项对应的取值, 包含在逻辑函数中的为1, 不包含的为0

第二步: 化简

如下图所示:

  1. 找出相邻的1, 无论是列方向还是行方向上的, 圈成一个圈
  2. 圈内的项都是可以用 A · ( B + B' ) 化简的
  3. 利用这个图, 找出所有的可以合并化简的项, 就完成了化简的工作啦!

例子

  • basic_logic_algebra.txt
  • Last modified: 4 months ago
  • by daizhirui