剩餘布爾代數

在數學中，剩餘布爾代數是其格結構是布爾代數的剩餘格。例子包括幺半群乘法選取為合取的布爾代數，在串接運算之下的給定字母表 Σ 的所有形式語言的集合，在關係複合運算之下的給定集合 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² 的補集運算成為布爾代數，並通過關係複合運算成為幺半群。幺半群單位元 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.