规范形式规范形式|离散数学

本文概述

析取范式或产品总和或（SOP）
求和或（POS）的合取范式或乘积
获取析取范式
获得合取范式
对偶原理

有两种形式的规范形式：

析取范式或产品总和或（SOP）。
求和或（POS）的合取范式或乘积。

析取范式或产品总和或（SOP）如果布尔表达式（{0, 1}, ∨, ∧, ‘ ）是minterm的连接, 则表示为析取范式。
示例：（x1’ ∧x2’ ∧x3’ ）∨（x1’ ∧x2∧x3’ ）∨（x1∧x2∧x3）是析取范式的布尔表达式。
由于存在三个最小项x1’ ∧x2’ ∧x3′ , x1’ ∧x2∧x3和x1∧x2∧x3。
最大项：n个变量x1, x2, … . xnis的布尔表达式, 如果形式为x1∨x2∨… … … .∨xn, 则表示为最大项
其中xi用于表示xi或xi’ 。
求和或（POS）的合取范式或乘积（{0, 1}, ∨, ∧, ‘ ）上的布尔表达式如果满足max-terms, 则被认为是析取范式。
例：
【规范形式】（x1∨x2∨x3）∧（x1∨x2∨x3）∧（x1∨x2∨x3）∧（x1’ ∨x2∨x3’ ）∧（x1’ ∧x2’ x3）
是一个合取范式的布尔表达式, 由五个max-term组成。
获取析取范式考虑一个从{0, 1} n到{0, 1}的函数。通过使最小项对应于0和1的每个有序n元组（函数的值为1）, 可以以与该函数相对应的析取范式形式获得布尔表达式。
获得合取范式考虑一个从{0, 1} n到{0, 1}的函数。通过使max-term对应于0和1的每个有序n元组（函数的值为0）, 可以以与该函数对应的联合范式获得布尔表达式。
示例：在

析取范式
合取范式

	f		f
(0, 0, 0)	1	(1, 0, 0)	0
(0, 0, 1)	0	(1, 0, 1)	1
(0, 1, 0)	1	(1, 1, 0)	0
(0, 1, 1)	0	(1, 1, 1)	1

解：

（x1’ ∧x2’ ∧x3’ ）∨（x1’ ∧x2∧x3’ ）∨（x1∧x2’ ∧x3）∨（x1∧x2∧x3）
（x1’ ∨x2’ ∨x3’ ）∧（x1’ ∨x2∨x3）∧（x1∨x2’ ∨x3’ ）∧（x1∨x2∨x3’ ）

对偶原理通过交换运算符+和*以及交换原始表达式E中的对应标识元素0和1, 可以获得任何表达式E的对偶。
示例：编写以下布尔表达式的对偶：
1.（x1 * x2）+（x1 * x3’ ）2.（1 + x2）*（x1 + 1）3.（a∧（b∧c））
解：
1.（x1 + x2）*（x1 + x3’ ）2.（0 * x2）+（x1 * 0）3.（a∨（b∧c））
注意：布尔代数中任何定理的对偶也是一个定理。