Bitstring algebra, monoid with concatenation and bitwise boolean operations

88 Views Asked by At

Given the free monoid on $\{0,1\}$ that is the set of all finite, possibly empty binary strings.

$$\langle \rangle, \langle 0\rangle, \langle 1\rangle, \langle 01\rangle \in \{0,1\}^*$$

with the concatenation operation $.$

$$\langle 0\rangle . \langle 1\rangle = \langle 01\rangle $$

Lets define subsets $\{0,1\}^n\quad \forall n \in ℕ $ with $n$ determining the string lenght. Then the operation $.$ applied to two non-empty elements produces elements from other subsets.

$$ \forall a, b \in \{0,1\}^2 :\quad a . b \in \{0,1\}^4 $$

In general:

$$ \forall m,n \in ℕ: \forall a \in \{0,1\}^m : \forall b \in \{0,1\}^n : \quad a . b \in \{0,1\}^{m+n} $$

I want to add to every subset the boolean bitwise operations ∧, ∨ applying only in strings of the subset.

Then every subset $\{0,1\}^n\quad \forall n \in ℕ $ is a Boolean ring.

  • Is what I proposed correct?
  • How I can further formalize this kind of algebraic structure?
  • Is there any kind of algebraic structure similar to what I proposed?