Monadyczna algebra Boole’a

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

Definicja

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

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

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

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

Przykłady

∃p = 1

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

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

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

∃p = p

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

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

tworzy wraz z ${\displaystyle \mathbb {B} }$ monadyczną algebrę Boole’a ${\displaystyle (\mathbb {B} ,\exists ).}$

Funkcyjne monadyczne algebry Boole’a

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

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

Uogólnienie

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

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

Wówczas ${\displaystyle (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 ${\displaystyle 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.