02 - Lec2 Boolean Algebra 布尔代数

布尔代数 0 & 1

普通的数学代数计算无非就是 数字集合加上一套运算规则, 相似的, 布尔代数也一样, 只不过: 数字集合变成了 {0, 1}, 运算规则也只有三个加法 +, 乘法 ⋅, 补  ˉ

规则如下:

x y x + y x • y
0 0 0 0
0 1 1 0
1 0 1 0
1 1 1 1

补运算：

加法

布尔加法和普通加法的区别是 1 + 1 = 1

乘法

布尔乘法和普通乘法运算结果一样

补

取反

翻译

优先级是: 补 > 乘 > 加，括号可以强制改变顺序

+ ∨ 或
• ∧ 与
ˉ ¬ 非

布尔函数

变量就是”一个不知道是 0 还是 1 的值”, 通常写成 x, y, z

含变量的表达式叫布尔函数，比如:

真值表 - 把所有情况列出来

变量的值不知道，函数值就算不出来。解决办法是把每一种取值都试一遍，列成表格，这就是真值表。 每个变量有 2 种取值，所以 n 个变量共有 2^n 种组合，真值表就有 2^n 行

以上面这个函数为例：
0 1 0 1
1 0 1 1

中间两列只是辅助计算 结果显示: 不管 x 取什么值, f(x) 都是 1

大法则

identical - 恒等

两个函数写法不同, 但在所有取值下结果都一样, 就叫恒等

比如: 和 列出真值表会发现, 两者的结果都和 x 完全一样 y 取什么都不影响

化简

既然结果相同, 做电路时当然选运算最少的写法, 这便是化简

定律 公式 直觉
Identity ， 和 1 做”与”, 和 0 做”或”, 都不改变 x
Idempotent ， 自己和自己做运算, 还是自己
Domination ， 或上一个真，结果必真; 与上一个假，结果必假
Double Complement 否定两次等于没否定
Commutative ， 和普通算术一样
Associative ， 和普通算术一样
De Morgan ， 对整体取补时, 每个变量取补, 同时加和乘互换
Distributive ， 第二条在普通算术里不成立, 是布尔代数特有的
Absorption ， 结果只由 x 决定, y 被吸收了
Unit Property “要么真要么假”一定真
Zero Property “又真又假”一定假

例子

化简:

流程

Step 4: 用电路实现

开关就是布尔运算

开关闭合 close 通电 1
开关断开 open 不通电 0

当两个开关:

  • 两个开关串联时: 都闭合 close 灯才亮, 对应 x • y
  • 两个开关并联时: 一个闭合 close 灯就亮, 对应 x + y