规范形式 (布尔代数)
维基百科，自由的百科全书
布尔代数中，由标准逻辑运算符组成的布尔函数可以按利用了对偶性极小项和极大项的概念的规范形式来表达。
目录 |
[编辑] 极小项
我们首先开始于定义极小项为只由逻辑与和补运算符组成的 n 个变量的逻辑表达式。
例如，下列是极小项的例子:
- a b'c
- a' b c
n 个变量有 2n 个极小项 - 这是因为在极小项表达式中一个变量要么是自身要么是它的补的形式 - n 个变量每个都有两种选择。
[编辑] 索引极小项
一般的，你可以指派给每个极小项(确保以同样的次序写变量，通常按字母序)，基于极小项的二进制值的一个索引。一个补项a' 被当作二进制的 0，而一个非补项如 a 被当作二进制 1。例如，你可以对 a b c'(1102) 关联上数字 6，并把极小项表达式写为 m6。所以三个变量的 m0 是 a'b'c'(0002)，而 m7 是 a b c(1112)。
[编辑] 函数等价
明显的，极小项 n 对这个逻辑函数的第 n+1 个唯一的函数输入给出真值。例如，极小项 5，a b' c，只在 a 和 c 都为真而 b 为假的时候是真的 - 输入为 a = 1, b = 0, c = 1 得到 1。
如果你给出一个逻辑函数的真值表，就可以把这个函数写为"积之和"(由极小项OR起来的序列)。这是析取范式的特殊形式。例如，如果给出真值表
a b f(a, b) 0 0 1 0 1 0 1 0 1 1 1 0
观察到输出为 1 的行是第一行和第三行，所以我们可以把 f 写为极小项 m0 和 m2 的和。
如果我们要验证它:
- f(a,b) = m0 + m2 = (a'b')+(ab')
通过直接计算，结果和这个函数的真值表是一样的。
[编辑] 极大项
极大项是极小项想法的对偶。不再使用 AND 和补运算，我们转而使用 OR 和补运算，处理是类似的。
例如，下面是极大项的例子:
- a+b'+c
- a'+b+c
n 个变量也有 2n 个极大项 - 这是因为在极大项表达式中一个变量要么是自身要么是它的补的形式 - n 个变量每个都有两种选择。
[编辑] 索引极大项
索引极大项是同极小项相反的方式完成的。你可以指派给每个最大项(确保以同样的次序写变量，通常按字母序)，基于项的补的次序的一个索引，例如，对 a'+b'+c 关联上数字 6，而写为 M6。所以三个变量的 M0 现在是 a+b+c 而 M7 是 a'+b'+c'.
[编辑] 对偶化
可以轻易的使用de Morgan 定律验证，极小项的补是各自的极大项。例如
- m2' = M2
- (a+b')'= a'b
[编辑] 函数等价
明显的，极大项 n 现在对这个逻辑函数的第 n+1 个唯一的函数输入给出假值。例如，极大项 5，a'+b+c'，只在 a 和 c 都为真而 b 为假的时候是假的 - 输入为 a = 1, b = 0, c = 1 得到 0。
如果你给出一个逻辑函数的真值表，就可以把这个函数写为"和之积" (由极大项AND起来的序列)。它是合取范式的特殊形式。例如，如果给出真值表
a b f(a, b) 0 0 1 0 1 0 1 0 1 1 1 0
观察到输出为 0 的行是第二行和第四行，所以我们可以把 f 写为极大项 M1 和 M3 的积。
如果我们要验证它:
- f(a,b) = M1 M3 = (a+b')(a'+b')
通过直接计算，结果和这个函数的真值表是一样的。
[编辑] 结果总结
所以逻辑函数都可以用规范形式表达，要么是"极小项之和"要么是"极大项之积"的形式。除了可以用直接和简单的代数形式表达复杂的逻辑函数之外，它还允把这些函数强力分析成最简化的形式，这对于数字电路的最小化是非常重要的。
