本系列是在coursera的Build a Modern Computer from First Principles: From Nand to Tetris学习笔记。

Constructing a Disjunctive Normal Form

Boolean Functions Synthesis的问题是给定一个boolean function的描述,譬如真值表,如何求得这个boolean function的表达式(expression)?

例,已知真值表1

x y z f
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

求相应的boolean function表达式f?

一个方法是先考虑f值为1的表达式,例如第一行:

x y z f
0 0 0 1

其对应的表达式为:

当且仅当x,y,z的值都为0的时候,(1)式的值才为1。

第三行:

x y z f
0 1 0 1

对应的表达式:

当且仅当x,z值为0,y值为1的时候,(2)式的值为1。

第五行:

x y z f
1 0 0 1

对应的表达式:

当且仅当x值为1,y,z值为0的时候,(3)式的值为1。

由于只有1,3,5行的f值为1,所以最后整个boolean function的表达式为,即

(4)式可以化简为:

这种方法被称为constructing a disjunctive normal form

Theorem

Theorem 1:

Any boolean function can be represented using an expression containing AND, OR and NOT operations.

并由德摩根律,有:

即OR gate可以由AND和NOT gate表达,所以有

Theorem 2:

Any boolean function can be represented using an expression containing AND and NOT operations.

NAND gate

NAND gate即AND gate求反,其真值表:

x y nand
0 0 1
0 1 1
1 0 1
1 1 0

NAND可以表达NOT:

NAND可以表达AND:

由(6)式和(7)式,得到:

Any boolean function can be represented using an expression containing NAND operations.

PS1. Instructor提到化简DNF得到其shortest expression是一个NP-hard问题。