3、P1 W1 U1.2 布尔函数

如果本次课程对应的 Coursera 的视频打不开，可以点击下面链接
P1W1U1.2 - Boolean Functions Synthesis

上节主要介绍了 布尔表达式 和 真值表。两个是用来表示布尔函数的两种表示形式。而且我们也知道了通过 布尔运算 可以从 布尔表达式 转换成对应的 真值表。

真值表怎么转换？

那么这节课主要讲如何用最基本的原则，从 真值表 转换成 布尔表达式，因为这也是我们之后如何做出“Hack”计算机的基本方法。课程每节课都是下一节课的铺垫，并会在实践中一步一步完成。

老师用了一种 叫 disjunctive normal form(析取范式?)的方法，总之就是下图先找出哪些行 “ f ” 为 “ 1 ”的。比如第一行，然后猜出一个表达式？怎么猜？

简单点就是都用AND 连接xyz，0就用Not，然后组合出下图绿色表达式，同时确保了其它xyz的情况（其它行） f 都为 0

猜出一个（ not(x) and not(y）and not(z) ）

然后确保套用这个表达式后，只有这第一行是1，其它行的结果都是0。

口诀：xyz用and连，遇到0加not

再看第二个 “ f ” 为 “ 1 ” 的行，比如第三行。猜出一个表达式。

应用红色表达式的时候，要确保其它行也用这个表达式后 f 结果为 0

最后同理我们把最后一个f是1的行，第五行，用上面同样的方法，写出一个表达式。最后只需用Or 把这三行（f是1）的表达式 连起来，就完成了真值表到 布尔表达式的转换工作

三行用Or连接

当然表达式可以用各种布尔恒等法则，简化比如简化成如下图

最终有很多种简化后结果，表达式不一定和图中一致

于是到这里我们发现一个定理theorem，其实我们只需要用 AND、 NOT、OR 就能表示任何的真值表。

任何布尔函数都可以用AND、OR、NOT来表示。

而我们能不能用再少的操作呢，其实可以不需要OR的，证明如下图：

x or y = not(not(x)and not(y))

那and 和 not 能不能再简化呢，其实还能...，如下图AND和NOT的操作都能合并成NAND布尔函数（这里其实还有很多布尔函数，完成本周课程后，我们就要亲手去实现它们）

所以极端情况，我们是可以只用 NAND 就能表示任何布尔函数了

然后把上面定理改一下：任何布尔函数，如果只用NAND，也是能表示的。下图下部分还给出了证明。

这就是标题 NAND to Tetris 的来历。

这节完成了抽象的逻辑操作的基础讲解，下一节课程就来开始讲解真实的逻辑门，以及逻辑门如何组成计算机。