Monadyczna algebra Boole’a

Monadyczna algebra Boole’a – algebra Boole’a z dodatkowym działaniem jednoargumentowym $\mathrm{\exists },$ które spełnia pewne warunki naśladujące własności kwantyfikatora egzystencjalnego.

Definicja

Monadyczna algebra Boole’a to struktura algebraiczna $𝔹=(B,\vee ,\wedge ,0,1{,}^{\prime },\mathrm{\exists })$ taka, że:

• $(B,\vee ,\wedge ,0,1{,}^{\prime })$ jest algebrą Boole’a,
• funkcja $\mathrm{\exists }:B\to B$ spełnia następujące warunki dla wszystkich $p,q\in B:$
  1. $\mathrm{\exists }0=0$
  2. $p⩽\mathrm{\exists }p$
  3. $\mathrm{\exists }(p\wedge \mathrm{\exists }q)=(\mathrm{\exists }p)\wedge (\mathrm{\exists }q)$

Pojęcie monadycznych algebr Boole’a pierwszy wprowadził Paul Halmos. Według niego motywacją do badań tych algebr było pragnienie lepszego rozumienia pewnych aspektów logiki matematycznej.

Elementy domknięte

Operacja $\mathrm{\exists }$ jest idempotentna: dla każdego $p\in B$ zachodzi $\mathrm{\exists }\mathrm{\exists }p=\mathrm{\exists }p,$ ponieważ $\mathrm{\exists }\mathrm{\exists }p=\mathrm{\exists }(\mathrm{\exists }p\wedge \mathrm{\exists }p)=\mathrm{\exists }\mathrm{\exists }p\wedge \mathrm{\exists }p=\mathrm{\exists }p.$

Elementy $p$ spełniające $\mathrm{\exists }p=p$ (innymi słowy wartości funkcji $\mathrm{\exists }$) nazywa się elementami domkniętymi. Zbiór elementów domkniętych jest podalgebrą Boole’a algebry $𝔹.$

Zbiór elementów domkniętych zawiera pełną informację o funkcji $\mathrm{\exists },$ dlatego możliwe jest jej odtworzenie na podstawie tego zbioru: niech $Z=\{\mathrm{\exists }q:q\in B\},$ wtedy $\mathrm{\exists }p=\min \{q\in Z:p⩽q\}.$

Przykłady

∃p = 1

Niech $𝔹$ będzie algebrą Boole’a. Funkcja $\mathrm{\exists }:B\to B$ zdefiniowana wzorem

$\mathrm{\exists }p=1$ dla każdego $p\in B\setminus \{0\}$

umożliwia określenie monadycznej algebry Boole’a $(𝔹,\mathrm{\exists }).$

∃p = p

Niech $𝔹$ będzie algebrą Boole’a. Funkcja $\mathrm{\exists }:B\to B$ zdana wzorem

$\mathrm{\exists }p=p$ dla każdego $p\in B$

tworzy wraz z $𝔹$ monadyczną algebrę Boole’a $(𝔹,\mathrm{\exists }).$

Funkcyjne monadyczne algebry Boole’a

Niech $C$ będzie zupełną algebrą Boole’a i niech $I$ będzie dowolnym zbiorem niepustym. Rodzina $C^I$ wszystkich funkcji $p:I\to C$ z działaniami określonymi punktowo jest również zupełną algebrą Boole’a.

Dla każdego $p\in C^I$ istnieje $p^{*}=\sup \{p(i):i\in I\}.$ Niech $\mathrm{\exists }p$ oznacza funkcję stałą o wartości $p^{*}.$ Wtedy $C^I$ z powyższym działaniem $\mathrm{\exists }$ jest zupełną monadyczną algebrą Boole’a.

Uogólnienie

Niech $C$ będzie dowolną algebrą Boole’a, a $I$ dowolnym zbiorem niepustym. Niech $B$ będzie podzbiorem zbioru $C^I$ wszystkich funkcji $p$ takim, że spełnione są następujące warunki:

• • $B$ (z działaniami określonymi punktowo) jest algebrą Boole’a (w szczególności funkcje stałe $0$ i $1$ należą do $B$);
  • dla każdej funkcji $p\in B$ istnieje kres górny zbioru $\{p(i):i\in I\};$
  • jeśli $p\in C$ i $p^{*}=\sup \{p(i):i\in I\},$ to również funkcja stała o wartości $p^{*}$ należy do zbioru $C.$ Funkcję tę oznacza się $\mathrm{\exists }p.$

Wówczas $(C,\mathrm{\exists })$ jest monadyczną algebrą Boole’a. Takie monadyczne algebry Boole’a nazywa się funkcyjnymi monadycznymi algebrami Boole’a (określonymi na I o wartościach w zbiorze $C$).

Twierdzenie Halmosa o reprezentacji monadycznych algebr Boole’a

Paul Halmos udowodnił, że każda monadyczna algebra Boole’a jest izomorficzna z funkcyjną monadyczną algebrą Boole’a.

Bibliografia

• Paul Halmos, Algebraic Logic. Chelsea Publishing Co., New York 1962.