布爾方程

布爾方程(Boolean equation)是一類特殊方程，指布爾代數B上含有未知元的等式f(X)=g(X)，其中f(X)與g(X)均為B上之布爾函式。當X=(x₁,x₂,…,x_e)時，稱此方程為e元布爾方程，而稱x₁,x₂,…,x_e為未知元。若有a₁,a₂,…,a_e∈B使之f(a₁,a₂,…,a_e)=g(a₁,a₂,…,a_e)，則稱(a1,a2,…,a_e)為e元布爾方程的一個解。對於具有形狀h(X)=0或h(X)=1的布爾方程，稱為0-1布爾方程，可以證明：形如f(X)=g(X)的布爾方程均可化為等價的0-1布爾方程。解0-1布爾方程的一個可行方法是逐次消元法，對於布爾函式中僅含0與1為其常量的0-1布爾方程有三種解法：即分項求解法、分支解法及卡諾圖解法，求解布爾方程不僅具有理論意義，而且在計算機科學及電路設計中均有重要套用，對於布爾方程x+y=a+b顯然有一解： x=a,y=b。

基本介紹

• 中文名：布爾方程
• 外文名：Boolean equation
• 所屬學科：數學
• 特例：0-1布爾方程

定義

設 是一個布爾代數，所謂 上的n元布爾方程是指如下的含有n個待定元的布爾函式f(X)及g(X)所組成的等式

類似的，我們可用

及

分別定義布爾不等方程及(廣義)布爾方程組，其中“ ”既可以是“=”，也可以是“≤”，布爾方程的（特）解是指滿足 的一個向量X∈ ；布爾不等方程及(廣義)布爾方程組的(特)解的定義類似。

0-1布爾方程

定義 若 是布爾函式， ，則

及

分別稱為（布爾）0方程與（布爾）1方程，它們又合稱為（布爾）0-1方程或0-1布爾方程。

1元布爾方程

僅含1個特定元的(廣義)布爾方程，簡稱為1元(廣義)布爾方程

由下文定理1知，每一個1元廣義布爾方程都可以寫成如下的0方程

這個0方程必定可寫成如下的標準形

其中a，b為布爾常量。

在每一個方程中都要區分哪些是待定元(未知元)，哪些是係數(已經給定的元)，例如，在1元標準形布爾方程

中，x(及x’)是未知元，而a與b是係數，但是在通常的定理中則沒有此種區別。

重要定理

定理1

每一個形如

的廣義布爾方程(m=1的情況)或廣義布爾方程組(m>1的情況)都等價於一個0-1布爾方程。

定理2

若B是布爾集；a，b∈B，則下列語句等價：

①

②

③

④1元布爾方程

是否有解(即：是否存在一個x∈B)使上式成立與係數a與b有關，方程有解的充要條件是有：

此外，x是1元布爾方程的解的充要條件是

定理3

若ab=0，則

及