基本介紹
介紹,定義,例子,共軛,
介紹
在數學中，剩餘布爾代數是其格結構是布爾代數的剩餘格。例子包括么半群乘法選取為合取的布爾代數，在串接運算之下的給定字母表 Σ 的所有形式語言的集合，在關係複合運算之下的給定集合X上所有二元關係的集合，和更一般的在關係複合之下的任何等價類的冪集。最初的套用是作為關係代數中二元關係例子的有限公理化推廣，但是存在不是關係代數的有趣的剩餘布爾代數的例子，比如語言例子。
定義
剩餘布爾代數是代數結構 (L, ∧, ∨, ¬, 0, 1, ·,I, \, /) 使得
- (i) (L, ∧, ∨, ·,I, \, /) 是剩餘格，
- (ii) (L, ∧, ∨, ¬, 0, 1) 是布爾代數。
- 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. 冪集{\displaystyle 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.
使用這個表示保持了這個公理化可以表達為有限多等式的情況。
