Canonical Forms

Difficulties in Manipulating Boolean Functions

• a Boolean function has multiple expressions.

• Problem 1: too many identities and theorems of Boolean algebra to apply

• Problem 2: requires skills for simplification

1. 中每一项使用或来连接，3.中每一项使用and来进行连接

• Minterms are AND terms with every variable present in either trueor complemented form 

• 每一项使用or来连接

• 包含所有的元素

• 各个字母元素出现的位置保持一致

• 每个元素均会出现一次

• 写成maxterm和minterm的标准形式

• 最后化简成所需要的形式即可

• 使用德摩根定律：
• 找到`F，然后使用德摩根定律进行求逆的操作就可以

• 两种格式的转换：

• 举个例子：
• 像下面的算式：
• 关键是画出真值表，使用德摩根定律

Circuit Optimization

• 线路优化的目标：
• 减少线路的成本，成本最小化
• Optimization requires a cost criterion to measure the simplicity of a circuit
• 成本设计的方式：
• Literal Cost（L）
• Gate input Cost（G）
• Gate input Cost with NOTs（GN）
• 下面是以一个例子

• 卡诺图Karnaugh Maps (K-map)
• Step 1: Identify minterms or maxterms
• Step 2: Fill the K-map with minterms or maxterms
• For SOM, put 1's in squares respective to the minterms
• For POM, put 0's in squares respective to the maxterms
• Step 3: Form the rectangular groups containing maximum number of terms in power of two
• Step 4: Obtain the simplified expression for groups
• For SOM, find the product terms and sum them up
• For POM, find the sum terms and take product of them

Four Variable Maps



Example 1: Four Variable Map Simplification

𝐹(𝑊,𝑋,𝑌,𝑍)=Σ(0,2,4,5,6,7,8,10,13,15)



出现Don’t Cares:
• 实现更大的矩形



SOM转换为POM：



主蕴含项和基本主蕴含项：
• A Prime Implicant is a product term obtained by combining the maximum possible number of adjacent squares in the map into a rectangle with the number of squares a power of 2.
出现四个基本主蕴含项，需要包含所有基本主蕴含项
• An Essential Prime Implicant is a prime implicant that covers one or more minterms that no combination of other prime implicants are able to include.