{%hackmd @RintarouTW/About %}

# Boolean Algebra

A Boolean algebra is a lattice that contains a least element and a greatest element and that is both complemented and distributive. The notation [$B;\lor,\land,\bar{}$] is used to denote the boolean algebra with operations join, meet and complementation.

$$
[B;\lor,\land,\bar{}] = \cases{
0, 1\in B\\
\text{distributive}\\
\text{complemented}
}
$$

## Notations

$B_2 = \{0,1\}$

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->1
}

$\cases{
0\lor 1=1\\
1\lor 1=1
}\implies 1\text{ is the greatest element of } B_2$

$\cases{
0\land 0=0\\
1\land 0=0
}\implies 0\text{ is the least element of } B_2$

$\cases{
0\lor 1=1\\0\land 1=0
}\implies \bar{0} = 1$

$\cases{
1\lor 0=1\\1\land 0=0
}\implies \bar{1} = 0$

$B_2^k = \overbrace{B_2\times B_2\times\cdots B_2}^\text{k itmes} = \{(x_1,x_2,\cdots,x_n)\mid x_i\in B_2\}$

### Boolean Algebra of Sets

$A$ be any set, $B=\mathcal{P}(A)$, [$B;\cup,\cap,^c$] is a Boolean algebra.

$^c$ = the complement of an element of $B$ with respect to $A$, $A\setminus B$

ex:

$\cases{A = \{a,b,c\}\\
B=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}}$

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->"{a}","{b}","{c}";
"{a}"->"{a,b}","{a,c}";
"{b}"->"{a,b}","{b,c}";
"{c}"->"{a,c}","{b,c}";
"{a,b}","{b,c}","{a,c}"->"{a,b,c}";
}

$x\in B$, $x^c = A\setminus x$

Assume $x=\{a,c\}, x^c = \{a,b,c\}\setminus\{a,c\}=\{b\}$

## Isomorphic Boolean Algebras

[$D_6,\lor,\land,\bar{}$] under $\mid$ (divisor) $\cases{\lor:\text{least common multiple}\\
\land:\text{greatest common divisor}}$

$D_6=\{1,2,3,6\}$

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
1->2,3->6;
}

$\cases{A=\{a,b\} , B=\mathcal{P}(A)\\
[B;\cup,\cap,\bar{}]}$

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->"{a}","{b}"->"{a,b}";
}

$\cases{
A=\{0,1\}\\
B=A\times A=A^2=\{(x,y)\mid x,y\in A\}}$

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
"(0,0)"->"(0,1)","(1,0)"->"(1,1)";
}

## Always True for Boolean Algebra

For any Boolean algebra [$B;\lor,\land,\bar{}$] under $\preceq$ relation,

- $\forall x\in B\cases{x\lor 1= 1\\x\land 1=x\\x\lor 0=x\\x\land 0=0}$
:::success
Boolean Opeartions $\lor,\land$ becomes least upper bound and greatest lower bound operations which can be easily mapped by the graph.
:::
- $a,b\in B\cases{(a\lor b)=a\implies a\succeq b (\iff b\preceq a)\\(a\land b)=a\implies a\preceq b(\iff b\succeq a)}$
- In terms of set operations
$a,b\in B\cases{(a\cup b)=a\implies b\subseteq a\\(a\cap b)=a\implies a\subseteq b}$
- In terms of logic
$\cases{p\lor q\iff p\text{ if } q\implies p\\p\land q\iff p\text{ if } p\implies q}$

## Atoms of a Boolean Algebra

Every finite Boolean algebra has $2^n$ elements with $n$ generators, called **atoms**.

ex:

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->"{a}","{b}","{c}";
"{a}"->"{a,b}","{a,c}";
"{b}"->"{a,b}","{b,c}";
"{c}"->"{a,c}","{b,c}";
"{a,b}","{b,c}","{a,c}"->"{a,b,c}";
}

$\cases{
\{a,b\}=\{a\}\lor\{b\}\\
\{a,c\}=\{a\}\lor\{c\}\\
\{b,c\}=\{b\}\lor\{c\}\\
\{a,b,c\}=\{a\}\lor\{b\}\lor\{c\}}$

$\{a\},\{b\},\{c\}$ are the atoms. $n=3$, it has 3 generators(aka. atoms), $|B| = 2^3 = 8$ (this number is called **order**).

:::info
$\sum\limits_{k=0}^n\binom{n}{k}=2^n\cases{
C_0^3=1=\varnothing\\
C_1^3=3=\{a\},\{b\},\{c\}\\
C_2^3=3=\{a,b\},\{a,c\},\{b,c\}\\
C_3^3=1=\{a,b,c\}
}$
:::

A non-least element $a$ in a Boolean algebra [$B;\lor,\land,\bar{}$] is called an atom if $\forall x\in B \cases{x\land a = a\\
\text{ or}\\
x\land a = 0}$

1) $x\land a=a$,
$x$ is a successor of $a\implies a\preceq x$
2) $x\land a=0$, so $x$ is not connected to $a$,
$\cases{\text{x is another atom}\\
\text{x is a successor of other atoms}\\
x=0}$

### The Covering Relation

[$B;\lor,\land,\bar{}$], $x, y\in B$,

:::info
$x$ **covers** $y$ $\iff y\prec x$ and $\nexists y'\in B, y\prec y' \prec x$
:::

ex:
$\{a,b\}$ covers $\{a\}$

$\{a,b,c\}$ doest NOT cover $\{a\}$ since there exists $\{a,b\}$,

$\{a\}\prec\{a,b\}\prec\{a,b,c\}$

:::info
Every element(except 0) in a Boolean algebra can be expressed **uniquely** as the join of a subset of all atoms.
:::

**Theorem**
Let $\mathcal{B}=[B;\lor,\land,\bar{}]$ be any finite Boolean algebra, and let $A$ be the set of all atoms of $B$. Then $[\mathcal{P}(A);\cup,\cap,^c]$ is isomorphic to $[B;\lor,\land,\bar{}]$.

Proof:

$\cases{
T(\varnothing)=0\\
T(x\cup y)=T(x)\lor T(y)\\
T(x\cap y)=T(x)\land T(y)\\
T(x^c)=\overline{T(x)}
}$

T: $\mathcal{P}(A)\to B$ , is a bijection.

###### tags: `math` `boolean` `algebra`