查看“︁规范形式 (布尔代数)”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
{{Unreferenced|time=2024-01-19T18:07:54+00:00}}
[[布尔代数]]中，所有由标准[[逻辑运算符]]组成的[[布尔函数]]，都可以表示为'''布尔规范形式'''。规范形式分为“极小项”形式，及其[[对偶律|对偶]]，“极大项”形式。

== 极小项 ==
我们首先定义'''极小项(minterm)'''。对于一个有 ''n'' 个变量的布尔函数，极小项是由[[逻辑合取|逻辑与]]运算符将这 ''n'' 个变量（或其逻辑否定）不重复地组合而成的逻辑表达式。

例如：
: <math>a b' c</math>
: <math>a' b c</math>
这两项中每个变量都出现，且仅只出现一次。三个变量间都仅使用逻辑与相连，因此这两项都符合极小项的定义。

<math>n</math>个变量有<math>2^n</math>个可能的极小项—这是因为在极小项表达式中，一个变量要么是其自身，要么是其逻辑否定形式—<math>n</math>个变量中的每个都有两种选择。

=== 索引极小项 ===
为了方便书写极小项，我们按照其中的每个变量是否含有逻辑非，为每一个可能的极小项指派一个索引值。

首先确保每个极小项中的变量都按照同样的次序排列（通常按拉丁字母序），从左到右，每个变量对应一个二进制位。一个带逻辑非的项，如<math>a'</math>，对应的二进制位为 0，而一个不带逻辑非的项，如<math>a</math>，对应的二进制位为 1。例如，<math>a b c'</math> 对应的二进制序列是（<math>110_2</math>），因此，其索引是数字 6，这个极小项表达式写作 <math>m_6</math>。与之相似，三个变量的<math>m_0</math>是<math>a'b'c'</math>（<math>000_2</math>），而<math>m_7</math>则是<math>a b c</math>（<math>111_2</math>）。

===函数等价===
因为极小项由各变量的逻辑与组合而成，所以只有当所有含有逻辑非的变量取值都为0，且所有不含逻辑非的变量取值都为 1，该极小项才会输出 1。例如，极小项<math>m_5 = ab'c</math>，只在 ''a'' 和 ''c'' 都为 1 而 ''b'' 为 0 时输出 1。

如果你给出一个逻辑函数的[[真值表]]，就可以把这个函数写为"积之和"(由极小项[[逻辑析取|OR]]起来的序列)。像这样组合出来的布尔表达式，其中任何一个极小项输出 1 时也输出 1，对其余输入其输出都是 0。由于每个极小项都只对一个输入输出 1，所以这个组合可以唯一地表示任何布尔函数。这是[[析取范式]]的特殊形式。例如，如果给出真值表
{| class="wikitable"
|+ 例：布尔函数<math>f</math>的真值表
! <math>a</math> !! <math>b</math> !! <math>f(a,b)</math>
|-
| 0 || 0 || 1
|-
| 0 || 1 || 0
|-
| 1 || 0 || 1
|-
| 1 || 1 || 0
|}

观察到<math>f</math>的输出仅在第一行和第三行为 1，所以我们可以把<math>f</math>写为极小项<math>m_0</math>和<math>m_2</math>之和。

验证：
: <math>f(a,b) = m_0 + m_2 = (a'b') + (ab')</math>
通过直接计算，结果和这个函数的真值表是一样的。

布尔函数表示为极小项之和的形式，叫做其'''主析取范式'''或'''极小项规范形式'''。

== 极大项 ==
'''极大项'''是极小项的对偶。其中各变量（或其逻辑否定）由[[逻辑析取|逻辑或]]运算符不重复地组合而成。
例如：
: <math>a+b'+c</math>
: <math>a'+b+c</math>

<math>n</math>个变量同样也有<math>2^n</math>个可能的极大项。

=== 索引极大项 ===
极大项的索引与极小项的相反：含逻辑非的变量对应的二进制位为 1，不含的对应二进制位为 0。例如，极大项<math>a'+b'+c</math>的索引为 6（<math>110_2</math>），记作<math>M_6</math>。同样，三个变量的<math>M_0</math>为<math>a+b+c</math>，<math>M_0</math>为<math>a'+b'+c'</math>。

===对偶化===
可以轻易的使用[[德·摩根定律]]验证，极小项的补是同索引的极大项。例如
: <math>m_2'=M_2</math>
: <math>(a+b')'=a'b</math>

===函数等价===
明显的，极大项 ''n'' 现在对这个逻辑函数的第 ''n''+1 个唯一的函数输入给出''假''值。例如，极大项 5，''a''<nowiki>'</nowiki>+''b''+''c''<nowiki>'</nowiki>，只在 ''a'' 和 ''c'' 都为真而 b 为假的时候是假的 - 输入为 a = 1, b = 0, c = 1 得到 0。

如果你给出一个逻辑函数的[[真值表]]，就可以把这个函数写为“和之积”（由极大项[[逻辑合取|AND]]起来的序列）。它是[[合取范式]]的特殊形式。例如，如果给出真值表
{| class="wikitable"
|+ 例：布尔函数<math>f</math>的真值表
! <math>a</math> !! <math>b</math> !! <math>f(a,b)</math>
|-
| 0 || 0 || 1
|-
| 0 || 1 || 0
|-
| 1 || 0 || 1
|-
| 1 || 1 || 0
|}

观察到<math>f</math>的输出仅在第二行和第四行为 0，所以我们可以把<math>f</math>写为极大项<math>m_1</math>和<math>m_3</math>之积。

验证：
: <math>f(a,b) = M_1 M_3 = (a+b')(a'+b')</math>
通过直接计算，结果和这个函数的真值表是一样的。

布尔函数表示为极大项之积的形式，叫做其'''主合取范式'''或'''极大项规范形式'''。

== 结果总结 ==
所有逻辑函数都可以用“极小项之和”或“极大项之积”的规范形式表达。除了可以用直接和简单的代数形式表达复杂的逻辑函数之外，规范形式还允许把这些函数强力分析成最简化的形式，这对于数字电路的最小化是非常重要的。

==参见==

* [[布尔代数主题列表]]
* [[Quine-McCluskey算法]]
* [[合取范式]]
* [[析取范式]]

[[Category:布尔代数|G]]
[[Category:带有代码示例的条目]]