规范形式 (布尔代数)
布尔代数中,所有由标准逻辑运算符组成的布尔函数,都可以表示为布尔规范形式。规范形式分为“极小项”形式,及其对偶,“极大项”形式。
极小项
[编辑]我们首先定义极小项(minterm)。对于一个有 n 个变量的布尔函数,极小项是由逻辑与运算符将这 n 个变量(或其逻辑否定)不重复地组合而成的逻辑表达式。
例如:
这两项中每个变量都出现,且仅只出现一次。三个变量间都仅使用逻辑与相连,因此这两项都符合极小项的定义。
个变量有个可能的极小项—这是因为在极小项表达式中,一个变量要么是其自身,要么是其逻辑否定形式—个变量中的每个都有两种选择。
索引极小项
[编辑]为了方便书写极小项,我们按照其中的每个变量是否含有逻辑非,为每一个可能的极小项指派一个索引值。
首先确保每个极小项中的变量都按照同样的次序排列(通常按拉丁字母序),从左到右,每个变量对应一个二进制位。一个带逻辑非的项,如,对应的二进制位为 0,而一个不带逻辑非的项,如,对应的二进制位为 1。例如, 对应的二进制序列是(),因此,其索引是数字 6,这个极小项表达式写作 。与之相似,三个变量的是(),而则是()。
函数等价
[编辑]因为极小项由各变量的逻辑与组合而成,所以只有当所有含有逻辑非的变量取值都为0,且所有不含逻辑非的变量取值都为 1,该极小项才会输出 1。例如,极小项,只在 a 和 c 都为 1 而 b 为 0 时输出 1。
如果你给出一个逻辑函数的真值表,就可以把这个函数写为"积之和"(由极小项OR起来的序列)。像这样组合出来的布尔表达式,其中任何一个极小项输出 1 时也输出 1,对其余输入其输出都是 0。由于每个极小项都只对一个输入输出 1,所以这个组合可以唯一地表示任何布尔函数。这是析取范式的特殊形式。例如,如果给出真值表
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
观察到的输出仅在第一行和第三行为 1,所以我们可以把写为极小项和之和。
验证:
通过直接计算,结果和这个函数的真值表是一样的。
布尔函数表示为极小项之和的形式,叫做其主析取范式或极小项规范形式。
极大项
[编辑]极大项是极小项的对偶。其中各变量(或其逻辑否定)由逻辑或运算符不重复地组合而成。 例如:
个变量同样也有个可能的极大项。
索引极大项
[编辑]极大项的索引与极小项的相反:含逻辑非的变量对应的二进制位为 1,不含的对应二进制位为 0。例如,极大项的索引为 6(),记作。同样,三个变量的为,为。
对偶化
[编辑]可以轻易的使用德·摩根定律验证,极小项的补是同索引的极大项。例如
函数等价
[编辑]明显的,极大项 n 现在对这个逻辑函数的第 n+1 个唯一的函数输入给出假值。例如,极大项 5,a'+b+c',只在 a 和 c 都为真而 b 为假的时候是假的 - 输入为 a = 1, b = 0, c = 1 得到 0。
如果你给出一个逻辑函数的真值表,就可以把这个函数写为“和之积”(由极大项AND起来的序列)。它是合取范式的特殊形式。例如,如果给出真值表
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
观察到的输出仅在第二行和第四行为 0,所以我们可以把写为极大项和之积。
验证:
通过直接计算,结果和这个函数的真值表是一样的。
布尔函数表示为极大项之积的形式,叫做其主合取范式或极大项规范形式。
结果总结
[编辑]所有逻辑函数都可以用“极小项之和”或“极大项之积”的规范形式表达。除了可以用直接和简单的代数形式表达复杂的逻辑函数之外,规范形式还允许把这些函数强力分析成最简化的形式,这对于数字电路的最小化是非常重要的。
参见
[编辑]Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.