剩餘布爾代數

維基百科,自由的百科全書
前往: 導覽搜尋

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

定義[編輯]

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

(i) (L, ∧, ∨, ·, I, \, /) 是剩餘格,而
(ii) (L, ∧, ∨, ¬, 0, 1) 是布爾代數。

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

x\y = ¬(x▷¬y),   xy = ¬(xy),

和對偶的為 /y 和 ◁y 使用:

x/y = ¬(¬xy),   xy = ¬(¬x/y),

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

(xz)∧y = 0 ⇔ (x·y)∧z = 0 ⇔ (zy)∧x = 0

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

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

例子[編輯]

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

2. 冪集 如平常那樣通過 ∩、∪ 和相對於 X2 的補集運算成為布爾代數,並通過關係複合運算成為么半群。么半群單位元 I 是恆等關係 {(x,x)|xX}。右剩餘 R\S 定義為 x(R\S)y 若且唯若對於所有 X 中的 zzRx 蘊涵 zSy。對偶的左剩餘 S/R 定義為 y(S/R)x 若且唯若對於所有 XzxRz 蘊涵 ySz

3. 冪集 2Σ* 如例子 2 那樣成為布爾代數,但是么半群選取為語言串接。這裡的集合 Σ 被用做字母表而 Σ* 指示在字母表上的所有有限(包括空串)的字的集合。語言 LM 的串接 LM 構成自所有字 uv 使得 uL 並且 vM。么半群單位元是只由空字 ε 構成的語言 {ε}。右剩餘 M\L 構成自所有在 Σ 上的字 w 使得 MwL。左剩餘 L/M 除了 wM 替代了 Mw 之外同右剩餘一樣。

共軛[編輯]

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

yx\zx·yzxz/y

在使用不相交的兩個剩餘的公理化中,使用了等價的 xyx∧¬y = 0。 簡寫 xy = 0 為 x # y 來表達它們的不相交,並把在公理中的 z 代換為 ¬z ,通過一點布爾運算處理它們變成了

¬(xz) # yx·y # z ⇔ ¬(¬z/y) # x

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

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

xz # yx·y # zzy # x

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

逆反[編輯]

在例子 2 和 3 中可以證明 xI = Ix。在例子 2 中兩側都等於 x 的逆反 x,而在例子 3 中兩側在 x 包含空字的時候都是 I 否則都是 0。在例子 2 情況中 x = x。對於例子 3 是不可能的因為 xI 幾乎沒有保留關於 x 的任何信息。所以在例子 2 中我們用 x 代換 xI = x = Ix 中的 x 並消去得到

xI = x = Ix

x = x 可以從這兩個方程證明。塔斯基關係代數概念可以定義有滿足這兩個等式的一個運算 x 的剩餘布爾代數。

上面的消去步驟對於例子 3 是不可能的,因此它不是關係代數,x 唯一確定為 xI

逆反的這個公理化的推論包括 x = x、 ¬(x) = (¬x)、(xy) = xy 和 (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.