布尔代数

布尔代数,也就是关于 0/1 的代数。如果将 0 视作假,1 视作真,也是逻辑代数。如果将 0 视为空集,1 视为全集的话,布尔代数就变成了集合代数。

在 0/1 的基础上定义三种运算:与 & 、或 | 以及取反 ~ ,具体如下:

  1. 与 & : 0 & 0 == 0, 0 & 1 == 0, 1 & 0 == 0, 1 & 1 == 1 ,简言之就是当且仅当 & 的两个操作数都为 1 的时候结果才为 1,否则为 0;
  2. 或 | : 0 | 0 == 0, 0 | 1 == 1, 1 | 0 == 1, 1 | 1 == 1 ,简言之就是当且仅当 | 的两个操作数均为 0 的时候结果才为 0,否则为1;
  3. 取反 ~: ~0 == 1, ~1 == 0 ,也就是 0 取反为 1, 1 取反为 0。

如果将 0 视作假 F,1 视作真 T 的话,上面就是逻辑的三个连接词 —— 与(∧)、或(∧)、非(¬)。如果将 0 视作空集,1 视作全集的话,上面就是集合的 —— 交(∩)、并(∪)、补(~)。同时也和编程语言的且(&& and)、或(|| or)、非(! not)对应。

布尔运算律

下面的运算律几乎是显而易见的(a、b、c 是变量,可以取值 0 或是 1):

  • 零一律:0 & a == 0, 1 | a == 1
  • 同一律:1 & a == a, 0 | a == a
  • 求补律:a & ~a == 0, a | ~a == 1
  • 幂等律:a & a == a, a | a == a
  • 交换律:a & b == b & a, a | b == b | a
  • 结合律:(a & b) & c == a & (b & c), (a | b) | c == a | (b | c)
  • 分配律:a & (b | c) == (a & b) | (a & c), a | (b & c) == (a | b) & (a | c)
  • 吸收率:a & (a | b) == a, a | (a & b) == a
  • 对合律:~(~a) == a
  • 德·摩根律:~(a & b) == ~a | ~b, ~(a | b) == ~a & ~b

异或(exclusive-or 不可兼取或)运算

除了最常见的 & | ~ 之外,还有一种常见的异或(^) 运算,其定义为:0 ^ 0 == 0, 0 ^ 1 == 1, 1 ^ 0 == 1, 1 ^ 1 == 0,简言之就是两个操作数相同为 0,相异为 1。 异或运算用 & | 进行定义是:

a ^ b == (a & ~b ) | (~a & b)

异或运算的运算律:

  • 0 ^ a == a, 1 | a == ~a
  • 交换律:a ^ b == b ^ a
  • 结合律:(a ^ b) ^ c == a ^ (b ^ c)

蕴含和全等运算

除了常见的 & | ~ ^ 四种运算外,在逻辑中还有两种常见运算 → (蕴含) 和 ≡ (全等)。其定义是:

a → b == ~a | b

a ≡ b == (a → b) & (b → a) == ~(a ^ b) == (a & b) | (~a & ~b)

对偶原理

对偶原理:交换相对的运算符 (& 与 |) 和常量值 (0 与 1),那么原来的等式/运算律依然相等/成立。

其他概念

文氏图:集合中描述集合关系的图;

真值表:逻辑中描述真值关系的表格,类似于文氏图的作用;

合取范式/析取范式:逻辑中逻辑表达式的规范化表示,和真值表具有对应关系;

应用栗子

1. [按位操作] 交换两个数 a, b

除了常见的:c = a; a = b; b = c 或是 a += b; b = a - b; a = a - b; 之外还有一种经典的交换法: a ^= b ^= a ^= b;

2. [按位操作] 如何判断一个整数 n 是否是 2 的次幂?

x & (x - 1) == 0 即可;

3. [按位操作] 如何判断一个整数 n 的是偶数?

除了 n % 2 == 0 之外可以 n & 1 == 0 ;

4. [按位操作] 位图操作:如何表示多种情况的组合?譬如文件 owner/group/other 帐号的读、写、执行的各种情况以及组合?

熟悉 unix/linux 系统的人都知道,针对这种情况的处理是用 1bit 表示一种情况。譬如 1 2 4 表示 owner 的读、写、执行权限,8 16 32 表示 group 的,64 128 256 表示 other 的。1+8+64 = 73 表示 owner/group/other 都具有读权限。

set bit 位:flag |= bit (bit: 1 << n)

clear bit 位:flag &= ~bit (bit: 1 << n)

5. [逻辑运算] 我曾经遇到过一个问题:判断两个时间段 A: [s1, e1] 与 B: [s2, e2] 是否相交?眨眼一想:~(s1 > e2 | e1 < s2) 这几乎是显而易见的,不相交的条件是:A 在 B 的前面(s1 > e2),或是 A 在 B 的后面(e1 < s2)。

但我遇到一个问题,就是写 sql 的时候不允许有 () 出现,卧槽!于是 ~(s1 > e2 | e1 < s2) == ~(s1 > e2) & ~(e1 < s2) == s1 ≤ e2 & e1 ≥ s2 ,转换成后面的表达式才解决。

Tags: 

Article type: