5.7.5 布尔函数、布尔表达式

1. 布尔函数

用 $B$ 表示有两个元素的布尔代数 (如第 529 页 5.7.3),那么 $n$ 重布尔函数 $f$ 是一个从 $B^n$ 到 $B$ 的映射. 有 $2^n$ 个 $n$ 重布尔函数. 所有具有运算

$$\begin{array}{}\text{(5.304)}& \left(f\sqcap g\right)\left(b\right)=f\left(b\right)\sqcap g\left(b\right),\end{array}$$$$\begin{array}{}\text{(5.305)}& \left(f\bigsqcup g\right)\left(b\right)=f\left(b\right)\bigsqcup g\left(b\right)\end{array}$$$$\begin{array}{}\text{(5.306)}& \overline{f}\left(b\right)=\overline{f\left(b\right)}\end{array}$$

的 $n$ 重布尔函数的集合是一个布尔代数. 这里 $b$ 总是表示 $B=\{0,1\}$ 的元素的 $n$ 组,并且方程右边的运算是在 $B$ 中实施的. 互异元素 0 和 1 对应于函数 $f_0$ 和 $f_1$ , 并且对于所有 $b\in B^n$ ,

$$\begin{array}{}\text{(5.307)}& f_0\left(b\right)=0,f_1\left(b\right)=1.\end{array}$$

$◼\mathbf{A}$ : 在 $n=1$ 的情形,即对于仅有一个布尔变量的情形,存在 4 个布尔函数:

恒等 $f\left(b\right)=b$ ,否定 $f\left(b\right)=\overline{b}$ ,重言 $f\left(b\right)=b$ ,矛盾 $f\left(b\right)=b$ .(5.308)

$◼\mathbf{B}$: 在 $n=2$ 的情形,即对于两个布尔变量 $a$ 和 $b$ 的情形,存在 16 个布尔函数, 这里最重要的是它们的名称和记号. 它们列在表 5.6 中.

函数名称	不同的记号	不同的符号	$\left(\begin{array}{l}a\\ b\end{array}\right)=\left(\begin{array}{l}0\\ 0\end{array}\right),\left(\begin{array}{l}0\\ 1\end{array}\right),\left(\begin{array}{l}1\\ 0\end{array}\right),\left(\begin{array}{l}1\\ 1\end{array}\right)$ 的值表
Sheffer 或 NAND	$\overline{a\cdot b}$ $a\mid b$ $\mathrm{NAND}\left(a,b\right)$		1,1,1,0
Peirce 或 NOR	$\overline{a+b}$ $a\downarrow b$ $\mathrm{NOR}\left(a,b\right)$		1,0,0,0
反等价 或 XOR	$\overline{a}b+a\overline{b}$ $a$ XOR $b$ $a\not\equiv b,a\oplus b$		0,1,1,0
等价	$\overline{a}\overline{b}+ab$ $a\equiv b$ $a\leftrightarrow b$		1,0,0,1
蕴涵	$\overline{a}+b,a\to b$		1,1,0,1

2. 布尔表达式

布尔表达式是用归纳的方式定义的: 设 $X=\{x,y,\cdots \}$ 是一个布尔变量(它们只能够在 $\{0,1\}$ 中取值) 的 (可数) 集:

(1)常数 0 和 1 作为 $X$ 中的布尔变量恰为布尔表达式.(5.309)

(2) 如果 $S$ 和 $T$ 是布尔表达式,那么 $\overline{T},\left(S\sqcap T\right)$ 和 $\left(S\bigsqcup T\right)$ 也是布尔表达式.(5.310)

如果一个布尔表达式含变量 $x_1,\cdots ,x_n$ ,那么它表示一个 $n$ 重布尔表达式 $f_T$ : 设 $b$ 是布尔变量 $x_1,\cdots ,x_n$ 的一个 “赋值”,即 $b=\left(b_1,\cdots ,b_n\right)\in B^n$ .

对表达式 $T$ 用下列方式指派一个布尔函数:

(1) 如果 $T=0$ ,那么 $f_T=f_0$ ; 如果 $T=1$ ,那么 $f_T=f_1$ .(5.311a)

(2) 如果 $T=x_i$ ,那么 $f_T\left(b\right)=b_i$ ; 如果 $T=\overline{S}$ ,那么 $f_T\left(b\right)=\overline{f_S\left(b\right)}$ .(5.311b)

(3) 如果 $T=R\sqcap S$ ,那么 $f_T\left(b\right)=f_R\left(b\right)\sqcap f_S\left(b\right)$ .(5.311c)

(4) 如果 $T=R\bigsqcup S$ ,那么 $f_T\left(b\right)=f_R\left(b\right)\bigsqcup f_S\left(b\right)$ .(5.311d)

另一方面,每个布尔函数 $f$ 可以用一个布尔表达式 $T$ 表示 (参见第 532 页5.7.6).

3. 共点或语义等价的布尔表达式

布尔表达式 $S$ 和 $T$ 称为共点或语义等价,如果它们表示相同的布尔函数. 布尔表达式相等, 当且仅当它们可以依据布尔代数的公理互相变换.

在此对于布尔表达式的变换要特别考虑两个方面:

• 形式尽可能 “简单” 的变换 (参见第 533 页 5.7.7).

• “正规形式” 的变换.