Booleovy okruhy
Definice. Okruh (R, +, ·) se nazývá Booleův okruh, je-li
idempotentní, tj. pro každé x ∈ R platí x · x = x.
Příklad. Pro libovolnou množinu X tvoří (P(X), ÷, ∩), kde ÷ značí
symetrický rozdíl množin, tj. A ÷ B = (A − B) ∪ (B − A), Booleův
okruh. Důkaz zanedlouho uvidíme, je to speciální příklad věty 9.2.
Věta 9.1. Netriviální Booleův okruh je komutativní okruh
charakteristiky 2.
Důkaz. Z idempotentnosti plyne
1 + 1 = (1 + 1) · (1 + 1) = 1 · 1 + 1 · 1 + 1 · 1 + 1 · 1 = 1 + 1 + 1 + 1.
Přičtením −(1 + 1) dostaneme 1 + 1 = 0. Protože okruh není
triviální, platí 1 = 0, a tedy má charakteristiku 2.
Opět z idempotentnosti pro libovolné x, y ∈ R dostáváme
x +y = (x +y)·(x +y) = x ·x +x ·y +y ·x +y ·y = x +x ·y +y ·x +y,
odkud x · y = −y · x = y · x, což jsme měli dokázat.
Booleův okruh vzniká z Booleovy algebry
Věta 9.2. Nechť (G, ∨, ∧) je Booleova algebra. Definujme na
množině G operace + a · takto: pro libovolné x, y ∈ G klademe
x + y = (x ∧ y ) ∨ (x ∧ y), x · y = x ∧ y.
Pak (G, +, ·) je Booleův okruh.
Důkaz. Obě operace jsou komutativní, násobení je i asociativní a
idempotentní. Pro každé x ∈ G platí x + 0 = x, x + x = 0,
x · 1 = x. Je tedy (G, ·) je pologrupa s neutrálním prvkem 1.
Dokažme distributivní zákon, nechť x, y, z ∈ G jsou libovolné.
Z definic a De Morganových zákonů plyne
x · y + x · z = (x ∧ y) ∧ (x ∧ z) ∨ (x ∧ y) ∧ (x ∧ z) =
= x ∧ y ∧ (x ∨ z ) ∨ (x ∨ y ) ∧ x ∧ z =
= (x ∧ y ∧ x ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ x ∧ z) ∨ (y ∧ x ∧ z) =
= (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z) =
= x ∧ (y ∧ z ) ∨ (y ∧ z) = x · (y + z),
což jsme chtěli dokázat.
Zbývá ověřit asociativitu sčítání, nechť x, y, z ∈ G jsou libovolné.
Z definice a De Morganových zákonů plyne
(x + y) + z = (x ∧ y ) ∨ (x ∧ y) ∧ z ∨ (x ∧ y ) ∨ (x ∧ y) ∧ z =
= (x ∧ y ) ∨ (x ∧ y) ∧ z ∨ (x ∨ y) ∧ (x ∨ y ) ∧ z =
= (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨
∨ (x ∧ x) ∨ (x ∧ y ) ∨ (y ∧ x) ∨ (y ∧ y ) ∧ z =
= (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ) ∨ (y ∧ x) ∧ z =
= (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z).
Poslední výraz se nezmění, provedeme-li s x, y, z jakoukoli
permutaci. Proto
(x + y) + z = (y + z) + x = x + (y + z),
a tedy sčítání je asociativní, tudíž (G, +) je komutativní grupa.
Ukázali jsme, že (G, +, ·) je Booleův okruh.
Booleova algebra vzniká z Booleova okruhu
Věta 9.3. Nechť (R, +, ·) je Booleův okruh. Definujme na množině
R operace ∨ a ∧ takto: pro libovolné x, y ∈ R klademe
x ∨ y = x · y + x + y, x ∧ y = x · y.
Pak (R, ∨, ∧) je Booleova algebra, kde pro každé x ∈ R platí
x = x + 1.
Důkaz. Operace ∧ je komutativní, asociativní a idempotentní a
operace ∨ komutativní a idempotentní. Pro libovolné x, y, z ∈ R
platí
(x ∨ y) ∨ z = (x · y + x + y) · z + (x · y + x + y) + z =
= x · y · z + x · z + y · z + x · y + x + y + z =
= x · (y · z + y + z) + x + y · z + y + z =
= x ∨ (y ∨ z),
a tedy je ∨ asociativní operace.
Protože
(x∨y)∧x = (x·y+x+y)·x = x·y·x+x·x+y·x = x·y+x·y+x = x,
a také
(x ∧ y) ∨ x = (x · y) · x + (x · y) + x = x · y + x · y + x = x,
je (R, ∨, ∧) svaz. Protože pro každé x ∈ R je x ∧ 0 = x · 0 = 0,
platí 0 ≤ x, podobně x ∧ 1 = x · 1 = x, a tedy x ≤ 1. Proto je 0
nejmenší a 1 největší prvek tohoto svazu.
Ověřme, že skutečně je x + 1 komplementem prvku x:
x ∧ (x + 1) = x · (x + 1) = x · x + x = x + x = 0,
x ∨ (x + 1) = x · (x + 1) + x + (x + 1) = 0 + x + x + 1 = 1.
Je tedy (R, ∨, ∧) komplementární svaz, zbývá ukázat, že je to též
svaz distributivní. Platí
(x ∧ z) ∨ (y ∧ z) = (x · z) · (y · z) + (x · z) + (y · z) =
= x · y · z + x · z + y · z = (x · y + x + y) · z =
= (x ∨ y) ∧ z.
Věta je dokázána.
Korespondence Booleových algeber a Booleových okruhů
Věta 9.4. Předchozí dvě věty nám dávají jednoznačnou
korespondenci mezi Booleovými okruhy a Booleovými algebrami.
Důkaz. Ukážeme, že v předchozí konstrukci si Booleovy okruhy a
Booleovy algebry navzájem odpovídají. Součiny a infima na sebe
přecházely. Vyjděme z Booleova okruhu:
B. okruh (R, +, ·) → B. algebra (R, ∨, ∧) → B. okruh (R, ⊕, ·).
Pro libovolné x, y ∈ R tedy platí
x ⊕ y = (x ∧ y ) ∨ (x ∧ y) =
= (x · y ) · (x · y) + (x · y ) + (x · y) =
= x · (x + 1) · y · (y + 1) + x · (y + 1) + (x + 1) · y =
= 0 + x · y + x + x · y + y = x + y.
Nyní vyjděme z Booleovy algebry:
B. algebra (R, ∨, ∧) → B. okruh (R, +, ·) → B. algebra (R, , ∧).
Pro libovolné x, y ∈ R tedy platí
x y = x · y + x + y = x + y + (x ∧ y) =
= x + y ∧ (x ∧ y) ∨ y ∧ (x ∧ y) =
= x + y ∧ (x ∨ y ) ∨ 0 =
= x + (y ∧ x ) ∨ (y ∧ y ) = x + (y ∧ x ) ∨ 0 =
= x + (y ∧ x ) = x ∧ (y ∧ x ) ∨ x ∧ (y ∧ x ) =
= x ∧ (y ∨ x) ∨ (x ∧ y) =
= x ∨ (x ∧ y) = (x ∨ x ) ∧ (x ∨ y) = 1 ∧ (x ∨ y) = x ∨ y,
což bylo třeba ověřit.
Poznámka. Podobné dvojí pohledy na jeden objekt bývají v
matematice velmi cenné, neboť mnohdy ukáží nečekané souvislosti.
Příkladem může být dualita, která je pro Booleovy algebry
naprosto zřejmá. Výše uvedenou korespondencí se převádí též na
Booleovy okruhy, kde už však není tak snadné si jí všimnout.