剩餘布林代數
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在數學中,剩餘布林代數是其格結構是布林代數的剩餘格。例子包括么半群乘法選取為合取的布林代數,在串接運算之下的給定字母表 Σ 的所有形式語言的集合,在關係複合運算之下的給定集合 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. 冪集 如平常那樣通過 ∩、∪ 和相對於 X2 的補集運算成為布林代數,並通過關係複合運算成為么半群。么半群單位元素 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,而在例子 3 中兩側在 x 包含空字的時候都是 I 否則都是 0。在例子 2 情況中 x = x。對於例子 3 是不可能的因為 x▷I 幾乎沒有保留關於 x 的任何資訊。所以在例子 2 中我們用 x 代換 x▷I = x = I◁x 中的 x 並消去得到
- x▷I = x = I◁x。
x = x 可以從這兩個方程證明。塔斯基的關係代數概念可以定義有滿足這兩個等式的一個運算 x 的剩餘布林代數。
上面的消去步驟對於例子 3 是不可能的,因此它不是關係代數,x 唯一確定為 x▷I。
逆反的這個公理化的推論包括 x = x、 ¬(x) = (¬x)、(x∨y) = x∨y 和 (x·y) = y·x。
引用
[編輯]- 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.