Monadyczna algebra Boole’a

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

Definicja

Monadyczna algebra Boole’a to struktura algebraiczna $\mathbb {B} =(B,\lor ,\land ,0,1,',\exists )$ taka, że:

• $(B,\lor ,\land ,0,1,')$ jest algebrą Boole’a,
• funkcja $\exists \colon B\to B$ spełnia następujące warunki dla wszystkich $p,q\in B{:}$
  1. $\exists 0=0$
  2. $p\leqslant \exists p$
  3. $\exists (p\land \exists q)=(\exists p)\land (\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 $\exists$ jest idempotentna: dla każdego $p\in B$ zachodzi $\exists \exists p=\exists p,$ ponieważ $\exists \exists p=\exists (\exists p\land \exists p)=\exists \exists p\land \exists p=\exists p.$

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

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

Przykłady

∃p = 1

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

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

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

∃p = p

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

$\exists p=p$ dla każdego $p\in B$

tworzy wraz z $\mathbb {B}$ monadyczną algebrę Boole’a $(\mathbb {B} ,\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\colon 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 \left\{p(i)\colon i\in I\right\}.$ Niech $\exists p$ oznacza funkcję stałą o wartości $p^{*}.$ Wtedy $C^{I}$ z powyższym działaniem $\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 $\left\{p(i)\colon i\in I\right\};$
  • jeśli $p\in C$ i $p^{*}=\sup \left\{p(i)\colon i\in I\right\},$ to również funkcja stała o wartości $p^{*}$ należy do zbioru $C.$ Funkcję tę oznacza się $\exists p.$

Wówczas $(C,\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.