Boolean Algebra
tommymio
·
·
个人记录
是数电的前导内容。最近在看一些杂七杂八的东西，可能也会更新 \text{Operating System} 及 \text{Machine Learning} 相关。
简单来说 \text{Boolean Algebra} 是建立在 \{0,1\} 上的一类代数，一种应用是通过将数字电路抽象为代数式，并对代数式加以运算从而化简、设计电路。
在 \text{Boolean Algebra} 中只有三类运算：
-
-
\times$，类比 $\text{Elementary algebra}$，定义为 $a\times b=[a\times b=1]
-
-$，类比 $\text{Elementary algebra}$，对于 $-a$，定义为 $a+(-a)=1
当然不得不提到真值表，它是 \text{Boolean Algebra} 中各种结论的基础，但我们根据以上定义能推导出一些二级结论，方便运算。本质上来说，这是对于底层逻辑的抽象。
交换律
a+b = b+a
a\times b=b\times a
结合律
(a+b)+c=a+(b+c)
(a\times b)\times c=a\times(b\times c)
似乎和 \text{Elementary algebra} 一样。因为在这两条运算律中，并未体现出 \text{Boolean Algebra} 的特性。
在讲分配律之前，让我们来看看 \text{Boolean Algebra} 的特性。
a+0=a \dots (1) \ \ \ \ a\times 1=a\dots(1')
\\
a+1=1 \dots (2) \ \ \ \ a\times 0=0\dots(2')
\\
a\times a= a \dots (3) \ \ \ \ a + a =a\dots (3')
\\
a+(-a)=1 \ \ \ \ a\times(-a)=0
根据真值表易证。我们同时注意到左右的式子似乎存在某种对称性，事实上它确实存在。
一般地，定义一个表达式为
F(x_1,x_2,\dots,x_n,+,\times)
那么其对偶为
F^D(x_1,x_2,\dots,x_n,+,\times)=F(x_1,x_2,\dots,x_n,\times,+)
即在 不改变原有运算顺序 的情况下交换 + 与 \times。
自然地，有 F^D = G^D 是 F=G 的充要条件。运用好这一性质可简化很多证明。
分配律
a(b+c)=ab+ac
(x+y)(x+z)=x+yz\dots (4)
对于 (4) 来说，它展现了一部分特性。并且 (4) 其实是一般分配律的对偶。
证明
\begin{aligned}
LHS
&=x\times x+x\times z+x\times y+y\times z
\\
&=x\times(1+y+z)+yz
\\
&=x+yz
\end{aligned}
对于 (4) 而言，它还存在更一般的形式，读者可以尝试证明
(x+y_1)(x+y_2)\dots(x+y_n)=x+y_1y_2\dots y_n
DeMorgan's Law
F(x_1,x_2,\dots,x_n,+,\times)=F(-x_1,-x_2,\dots,-x_n,\times,+)
这与对偶的形式十分类似。联想到了什么？是不是有点像数学中的逆命题与反命题？\text{Boolean Algebra} 的初衷本就是用来抽象化逻辑问题。