[科普中国]-布尔方程组

布尔方程组(system of Boolean equations)是布尔方程构成的方程组，在布尔代数B中，由2m个n元布尔函数(可分为两组)fi(x1，x2，…，xn)，gi(x1，x2，…，xn)，(i=1，2…，m)可组成m个布尔方程，fi(x1，x2，…，xn)=gi(x1，x2，…，xn)，(i=1，2，…，m)，这m个方程所构成的方程组称为B上的布尔方程组1。

基本概念在布尔代数B中，由2m个n元布尔函数(可分为两组)fi(x1，x2，…，xn)，gi(x1，x2，…，xn)，(i=1，2…，m)可组成m个布尔方程，fi(x1，x2，…，xn)=gi(x1，x2，…，xn)，(i=1，2，…，m)，这m个方程所构成的方程组

称为B上的布尔方程组1。

布尔方程组的解布尔方程组的解是布尔方程组的基本概念之一。在布尔代数B中，如果存在一个n元列a1，a2，…，an∈B满足布尔方程组fi(x1，x2，…，xn)=gi(x1，x2，…，xn)，(i=1，2，…，m)的每个方程，则称n元列a1，a2，…，an为布尔方程组在B中的一个特解，简称布尔方程组的解，而所有解的一般形式称为通解，如布尔方程组

有通解

其中u，v，w为布尔代数中的任意元素1。

相关概念定义1 含有待定元的等式叫（相等）方程；含有待定元的不等式叫不等方程；能概括这二者的则叫广义方程，某些（广义）方程组成的组叫**（广义）方程组2**。

定义2 设是一个布尔代数，所谓上的n元布尔方程是指如下的含有n个待定元的布尔函数f(X)及g(X)所组成的等式

类似的，我们可用

及

分别定义布尔不等方程及**（广义）布尔方程组**，其中“”既可以是“=”，也可以是“≤”。

布尔方程(1)的（特）解，是指满足(1)的一个向量X∈；布尔不等方程(2)及（广义）布尔方程组(3)的（特）解的定义类似2。

定义3 若h(X)是布尔函数，k(X)=h'(X)，则

及

分别称为（布尔）0方程与（布尔）1方程；它们又合称为（布尔）0-1方程或0-1布尔方程2。

相关定理引理1 每一个形如(1)的布尔方程都可等价于一个0-1布尔方程2。

引理2 每一个形如(2)的布尔不等方程也等价于一个0-1布尔方程。

引理3 每一个布尔0方程组

或布尔1方程组

也等价于一个0-1布尔方程。

注意，引理1，2，3都已给出了化成等价0 -1布尔方程的方法。

定理1 每一个形如(3)的广义布尔方程（m=1的情况）或广义布尔方程组（m>1的情况）都等价于一个0-1布尔方程。

证 (1)m=1的情况已由引理1及引理2证得2；

(2)仅证m>1的情况：由于通过求补对偶变换可将0方程变成1方程，也可将1方程变成0方程，所以每一个广义布尔方程组都可以变成0方程组或1方程组，于是再由引理53即得证。

【例1】将布尔方程组

变成与之等价的0方程。

解 (6)等价于 (xy')(ab')∪(xy')(ab')=0 ， (8)

(7)等价于 (x'y)(a’b)∪(x'y)(a'b)=0 ， (9)

(8)与(9)等价于:

[(xy')(ab')∪(xy')'(ab’)]∪[(x'y)(a'b)∪(x’y)(a'b)]=0

即

(a’b∪ab')xy∪(a'∪b)xy'∪(a∪b')x'y∪(ab'∪a'b)x'y'=0， (10)

(10)即为所求的0方程2。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学