布尔表达式

考虑一个布尔代数 (B, ∨,∧,',0,1)。布尔代数 B 上的布尔表达式定义为

1. B 的每个元素都是一个布尔表达式。
2. 每个变量名都是一个布尔表达式。
3. 如果 a₁ 和 a₂ 是布尔表达式，那么 a₁,'∨ a₂ 和 a₁∧ a₂ 都是布尔表达式。

示例: 考虑一个布尔代数 ({0, 1, 2, 3},∨,∧,',0,1)。

1. 0∨x
2. (2∧3)
3. (x₁∨ x₂)∧ (x₁∧x₃)

是布尔代数上的布尔表达式。

    包含 n 个不同变量的布尔表达式通常被称为 n 个变量的布尔表达式。

布尔表达式的求值

令 E (x₁,x₂,....x_n) 是一个布尔代数 B 上 n 个变量的布尔表达式。对变量 x₁,x₂,....x_n 赋值意味着将 A 的元素赋值给变量的值。

    我们可以通过将表达式中的变量替换为它们的值来评估表达式 E ( x₁,x₂,....x_n)。

示例: 考虑布尔表达式

            E( x₁,x₂,x₃)=(x₁∨ x₂ )∧(x₁∨ x₂ )∧(x₂∨ x₃)

在布尔代数 ({0,1}, ∨,∧,') 上

通过赋值 x₁=0,x₂=1,x₃=0 得到

            E (0, 1, 0) = (0∨1)∧(0∨1)∧(1∨0)=1∧1∧0=0。

等价的布尔表达式

如果两个 n 个变量的布尔表达式对于变量的每次赋值都具有相同的值，则称它们相等。

示例: 以下两个布尔代数 (x₁∧x₂)∨(x₁∧ x₃ ) 和 x₁∧ (x₂∨ x₃) 是等价的。

我们可以写 E₁( x₁,x₂,....x_n)=E₂( x₁,x₂,....x_n) 来表示两个表达式 E₁( x₁,x₂,....x_n) 和 E₂( x₁,x₂,....x_n) 是等价的。

示例: 布尔表达式 (x₁∧x₂∧x₃)∨(x₁∧x₂ )∨(x₁∧x₃) 在布尔代数 ({0, 1}, ∨,∧,') 上定义了图中的函数 f。

最小项: 如果 n 个变量 x₁,x₂,....x_n 的布尔表达式的形式为 x₁∧x₂∧x₃∧....∧x_n，则称其为最小项

其中 x_i 用于表示 x_i 或 x_i'。