卡诺图

对于一个逻辑函数的化简，卡诺图的方法非常巧妙的把问题转化成了最小集合覆盖问题

在卡诺图中，相邻的两个格子仅只有一个 bit 的变化，我们记其为 $x$ 则有

$$Rx+R\overline{x}=R$$

其中 $R$ 表示公共部分，这就是相邻的两个格子可以“合并”以消去一个自由变量的原因 —— 若对于 $2^k$ 个相邻的格子，也可以简单的时候归纳法进行证明合并之后可以消去 $k$ 个自由变量

接着对于一个最简的 SOP 可以使用若干质项表示 —— 用反证法，如果其中有非质项，则必然还不是最简形式

而每个质项在卡诺图中的表示即为“极大占 $2^k$ 格子仅含 1 的圈”，也非常好说，如果这个圈组还能继续扩，则说明还有没有消去的自由变量，所以是蕴含项而不是质项，那么综上，我们在考虑最简表示的时候仅需要考虑质项即可

我们已经可以得到一个比较粗略的等价描述

$$G=P_1+P_2+\cdots +P_m$$

其中 $P_i$ 为质项，并且保证满足 $F⟺G$，在卡诺图中，即要求对于每一个 1 都覆盖，同时所有覆盖的圈都是极大

回到目标继续说明 —— 找到一个 $F⟺G$，即对于所有的输入 $x,s.t.F(x)=1$，都可以有 $G(x)=1$，这就非常好的说明了我们在卡诺图中需要覆盖全部的 1；反过来，又因为 $G$ 是由 $F$ 的质项组成，所以必有 $P_i(x)=1⟹F(x)=1$

最后关于”最简“的描述 —— 我们需要在 $\{P_1,P_2,\dots ,P_m\}$ 中挑选 $k$ 个，使得依旧可以保证所有的 1 都被覆盖，变转化成了最小集合覆盖问题（这样在保证了每一项都是最简，并且拥有最少的项，所以是最简形式）