• 布尔代数提供的是布尔值集合 ${\mathbb B} =\{ 0, 1 \}$ 上的运算和规则。
• $0, 1$ 被称为布尔值，因为它们的值是确定的，也被称为布尔常量。
• 记 ${\mathbb B}$ 上的变量为布尔变量，比如 $x \in \mathbb B$ 表明要么 $x = 0$，要么 $x = 1$。

一、布尔代数

1. 布尔值的补、和与积

• 一个布尔值的补 (complement) 也称为取反 (NOT)，记为 ${\rm NOT} \, x$，或者 $\overline x$，或者 $\neg x$。

  $x$	${\rm NOT} \, x$
  $0$	$1$
  $1$	$0$

• 两个布尔值之和 (sum) 也称为或 (OR)，记为 $x \, {\rm OR} \, y$，或者 $x + y$，或者 $x \vee y$。

  $x$	$y$	$x \, {\rm OR} \, y$
  $0$	$0$	$0$
  $0$	$1$	$1$
  $1$	$0$	$1$
  $1$	$1$	$1$

• 两个布尔值之积 (sum) 也称为且 (AND)，记为 $x \, {\rm AND} \, y$，或者 $x \cdot y$，或者 $x \wedge y$。

  $x$	$y$	$x \, {\rm AND} \, y$
  $0$	$0$	$0$
  $0$	$1$	$0$
  $1$	$0$	$0$
  $1$	$1$	$1$

2. 布尔表达式

• 定义布尔表达式的递归定义：

  • 布尔常量 $0, 1$，布尔变量 $x, y, \cdots$ 本身是布尔表达式。
  • 如果 $E$ 是布尔表达式，那么 ${\rm NOT} \, E$ 是布尔表达式。
  • 如果 $E_1, E_2$ 是布尔表达式，那么 $E_1 \, {\rm OR} \, E_2$ 和 $E_1 \, {\rm AND} \, E_2$ 都是布尔表达式。

• 布尔表达式的值表

  $x$	$y$	${\rm NOT} \, y$	$x \, {\rm AND} \, ({\rm NOT} \, y)$
  $0$	$0$	$1$	$0$
  $0$	$1$	$0$	$0$
  $1$	$0$	$1$	$1$
  $1$	$1$	$0$	$0$

  • 根据计数原理可以发现，$n$ 个变量有 $2^n$ 种不同的取值（值表里面的行），$n$ 元表达式有 $2^{2^n}$ 种不同的取值（值表里面互不相同的列的种类数目）。

• 布尔代数的恒等式