剩餘布林代數

在數學中，**剩餘布林代數**是其格結構是布林代數的剩餘格。例子包括么半群乘法選取為合取的布林代數，在串接運算之下的給定字母表 Σ 的所有形式語言的集合，在關係複合運算之下的給定集合 _X_ 上所有二元關係的集合，和更一般的在關係複合之下的任何等價類的冪集。最初的應用是作為關係代數中二元關係例子的有限公理化推廣，但是存在不是關係代數的有趣的剩餘布林代數的例子，比如語言例子。

## 定義

**剩餘布林代數**是代數結構 (_L_, ∧, ∨, ¬, 0, 1, ·, **I**, \, /) 使得

　
: (i) (_L_, ∧, ∨, ·, **I**, \, /) 是剩餘格，而

　
: (ii) (_L_, ∧, ∨, ¬, 0, 1) 是布林代數。

更適合關係代數應用的一個等價標識 (signature) 是 (_L_, ∧, ∨, ¬, 0, 1, ·, **I**, ▷, ◁)，這裡的一元運算 _x_\ 和 _x_▷ 是可用如下德・摩根定律的方式相互轉換的：

　
: _x_\_y_ = ¬(_x_▷¬_y_),   _x_▷_y_ = ¬(_x_\¬_y_)，

和對偶的為 /_y_ 和 ◁_y_ 使用：

　
: _x_/_y_ = ¬(¬_x_◁_y_),   _x_◁_y_ = ¬(¬_x_/_y_),

而在剩餘格中的剩餘公理因而 (替代 _z_ 為 ¬_z_) 改寫為

　
: (_x_▷_z_)∧_y_ = 0 ⇔ (_x_·_y_)∧_z_ = 0 ⇔ (_z_◁_y_)∧_x_ = 0

這個德・摩根對偶重公式化在下面關於共軛的段落中詳細討論。

因為剩餘格和布林代數都可以用有限多等式定義，剩餘布林代數也是如此，因此它們形成了可有限公理化的一個簇。

## 例子

1. 任何布林代數帶有么半群乘法・選取為合取而兩個剩餘選取為實質蘊涵 _x_→_y_。在也有可能替代合取作為么半群乘法的餘下 15 個二元布林運算中，只有五個滿足單調性要求，它們是 _x_·_y_ = 0, _x_·_y_ = 1, _x_·_y_ = _x_, _x_·_y_ = _y_, 和 _x_·_y_ = _x_∨_y_。設置 _y_ = _z_ = 0 於剩餘公理 _y_ ≤ _x_\_z_ ⇔ _x_·_y_ ≤ _z_ 中，得到 0 ≤ _x_\0 ⇔ _x_・0 ≤ 0，通過選取 _x_ = 1 它在 _x_·_y_ = 1、_x_·_y_ = _x_ 或 _x_·_y_ = _x_∨_y_ 的時候失敗。_z_/_y_ 的對偶自變數排除了 _x_·_y_ = _y_。這就只留下了 _x_·_y_ = 0 (與 _x_ 和 _y_ 無關的常數二元運算)，它在剩餘都被選取為常數運算 _x_/_y_ = _x_\_y_ = 1 的時候滿足幾乎所有公理。它不能滿足的公理是 _x_·**I** = _x_ = **I**·_x_，因為 **I** 缺乏一個合適的值。所以合取是作為剩餘布林代數的么半群乘法的唯一二元布林運算。

2. 冪集 $2^{X^{2}}$ 如平常那樣通過 ∩、∪ 和相對於 _X_2 的補集運算成為布林代數，並通過關係複合運算成為么半群。么半群單位元素 **I** 是恆等關係 {(_x_,_x_)|_x_ ∈ _X_}。右剩餘 _R_\_S_ 定義為 _x_(_R_\_S_)_y_ 若且唯若對於所有 _X_ 中的 _z_，_zRx_ 蘊涵 _zSy_。對偶的左剩餘 _S_/_R_ 定義為 _y_(_S_/_R_)_x_ 若且唯若對於所有 _X_ 中 _z_ ，_xRz_ 蘊涵 _ySz_。

3. 冪集 2Σ\* 如例子 2 那樣成為布林代數，但是么半群選取為語言串接。這裡的集合 Σ 被用做字母表而 Σ\* 指示在字母表上的所有有限 (包括空串) 的字的集合。語言 _L_ 和 _M_ 的串接 _LM_ 構成自所有字 _uv_ 使得 _u_ ∈ _L_ 並且 _v_ ∈ _M_。么半群單位元素是只由空字 ε 構成的語言 {ε}。右剩餘 _M_\_L_ 構成自所有在 Σ 上的字 _w_ 使得 _Mw_ ⊆ _L_。左剩餘 _L_/_M_ 除了 _wM_ 替代了 _Mw_ 之外同右剩餘一樣。

## 共軛

剩餘的德・摩根對偶 ▷ 和 ◁ 如下這樣引出。在剩餘格之中，布林代數是有補運算 ¬ 的特殊情況。這允許了如下三個不等式的可供替代的表達式

　
: _y_ ≤ _x_\_z_ ⇔ _x_·_y_ ≤ _z_ ⇔ _x_ ≤ _z_/_y_

在使用不相交的兩個剩餘的公理化中，使用了等價的 _x_ ≤ _y_ ⇔ _x_∧¬_y_ = 0。 簡寫 _x_∧_y_ = 0 為 _x_ # _y_ 來表達它們的不相交，並把在公理中的 _z_ 代換為 ¬_z_ ，通過一點布林運算處理它們變成了

　
: ¬(_x_\¬_z_) # _y_ ⇔ _x_·_y_ # _z_ ⇔ ¬(¬_z_/_y_) # _x_

現在 ¬(_x_\¬_z_) 讓我們想起了德・摩根對偶性，假設 _x_\ 被認為是一元運算 _f_，定義為 _f_(y) = _x_\_y_，它有一個德・摩根對偶 ¬_f_(¬_y_)，這類似於 ∀_x_φ(_x_) = ¬∃_x_¬φ(_x_)。這個對偶就指示為 _x_▷，我們定義 _x_▷_z_ 為 ¬(_x_\¬_z_)。類似的我們定義另一個運算 _z_◁_y_ 為 ¬(¬_z_/_y_)。通過類比 _x_\ 作為關聯於運算 _x_・的剩餘運算，我們稱呼 _x_▷ 為 _x_・的**共軛**運算或簡稱共軛。類似的，◁_y_ 是・_y_ 的共軛。不同於剩餘的是，共軛是在兩個運算之間的等價關係：如果 _f_ 是 _g_ 的共軛則 _g_ 也是 _f_ 的共軛，就是說，_f_ 的共軛的共軛是 _f_。共軛的另一個好處是沒有必要談論右和左共軛，這個區別現在繼承自 _x_・和・_x_ 之間的不同，它們有各自的共軛 _x_▷ 和 ◁_x_。(但是在 _x_\ 被選取為對 _x_・的剩餘運算的時候這個優點同樣出現在剩餘上。)

所有這些 (與布林代數和么半群公理一起) 生成了下列剩餘布林代數的等價公理化。

　
: _x_▷_z_ # _y_ ⇔ _x_·_y_ # _z_ ⇔ _z_◁_y_ # _x_

使用這個表示保持了這個公理化可以表達為有限多等式的情況。

## 逆反

在例子 2 和 3 中可以證明 _x_▷**I** = **I**◁_x_。在例子 2 中兩側都等於 _x_ 的逆反 _x_ ${\breve {}}$ ，而在例子 3 中兩側在 _x_ 包含空字的時候都是 **I** 否則都是 0。在例子 2 情況中 _x_ ${\breve {\ }}{\breve {\ }}$ = _x_。對於例子 3 是不可能的因為 _x_▷**I** 幾乎沒有保留關於 _x_ 的任何訊息。所以在例子 2 中我們用 _x_ ${\breve {}}$ 代換 _x_▷**I** = _x_ ${\breve {}}$ = **I**◁_x_ 中的 _x_ 並消去得到

　
: _x_ ${\breve {}}$ ▷**I** = _x_ = **I**◁_x_ ${\breve {}}$ 。

_x_ ${\breve {\ }}{\breve {\ }}$ = _x_ 可以從這兩個方程式證明。塔斯基的**關係代數**概念可以定義有滿足這兩個等式的一個運算 _x_ ${\breve {}}$ 的剩餘布林代數。

上面的消去步驟對於例子 3 是不可能的，因此它不是關係代數，_x_ ${\breve {}}$ 唯一確定為 _x_▷**I**。

逆反的這個公理化的推論包括 _x_ ${\breve {\ }}{\breve {\ }}$ = _x_、 ¬(_x_ ${\breve {\ }}$ ) = (¬_x_) ${\breve {\ }}$ 、(_x_∨_y_) ${\breve {}}$ = _x_ ${\breve {}}$ ∨_y_ ${\breve {}}$ 和 (_x_·_y_) ${\breve {}}$ = _y_ ${\breve {}}$ ·_x_ ${\breve {}}$ 。

## 引用

* Bjarni Jónsson and Constantine Tsinakis, Relation algebras as residuated Boolean algebras, Algebra Universalis, 30 (1993) 469-478.
* Peter Jipsen, _Computer aided investigations of relation algebras_, Ph.D. Thesis, Vanderbilt University, May 1992.