# Boolean subalgebra

## Boolean Subalgebras

Let $A$ be a Boolean algebra  and $B$ a non-empty subset of $A$. Consider the following conditions:

1. 1.

if $a\in B$, then $a^{\prime}\in B$,

2. 2.

if $a,b\in B$, then $a\vee b\in B$,

3. 3.

if $a,b\in B$, then $a\wedge b\in B$,

It is easy to see that, by de Morgan’s laws, conditions 1 and 2 imply conditions 1 and 3, and vice versa. Also, If $B$ satisfies 1 and 2, then $1=a\vee a^{\prime}\in B$ by picking an element $a\in B$. As a result, $0=1^{\prime}\in B$ as well.

A non-empty subset $B$ of a Boolean algebra $A$ satisfying conditions 1 and 2 (or equivalently 1 and 3) is called a Boolean subalgebra of $A$.

Examples.

Remarks. Let $A$ be a Boolean algebra.

## Subalgebras Generated by a Set

Let $A$ be a Boolean algebra and $X$ a subset of $A$. The intersection of all Boolean subalgebras (of $A$) containing $X$ is called the Boolean subalgebra generated by $X$, and is denoted by $\langle X\rangle$. As indicated by the remark above, $\langle X\rangle$ is a Boolean subalgebra of $A$, the smallest subalgebra containing $X$. If $\langle X\rangle=A$, then we say that the Boolean algebra $A$ itself is generated by $X$.

###### Proposition 1.

Every element of $\langle X\rangle\subseteq A$ has a disjunctive normal form  (DNF). In other words, if $a\in\langle X\rangle$, then

 $a=\bigvee_{i=1}^{n}\bigwedge_{j=1}^{\phi(i)}a_{ij}=(a_{11}\wedge\cdots\wedge a% _{1\phi(1)})\vee(a_{21}\wedge\cdots\wedge a_{2\phi(2)})\vee\cdots\vee(a_{n1}% \wedge\cdots\wedge a_{n\phi(n)}),$

where either $a_{ij}$ or $a_{ij}^{\prime}$ belongs to $X$.

###### Proof.

Let $B$ be the set of all elements written in DNF using elements $X$. Clearly $B\subseteq\langle X\rangle$. What we want to show is that $\langle X\rangle\subseteq B$. First, notice that the join of two elements in $B$ is in $B$. Second, the complement  of an element in $B$ is also in $B$. We prove this in three steps:

1. 1.

If $a\in B$ and either $b$ or $b^{\prime}$ is in $X$, then $b\wedge a\in B$.

If $a=(a_{11}\wedge\cdots\wedge a_{1\phi(1)})\vee(a_{21}\wedge\cdots\wedge a_{2% \phi(2)})\vee\cdots\vee(a_{n1}\wedge\cdots\wedge a_{n\phi(n)})$, then

 $\displaystyle b\wedge a$ $\displaystyle=$ $\displaystyle b\wedge((a_{11}\wedge\cdots\wedge a_{1\phi(1)})\vee(a_{21}\wedge% \cdots\wedge a_{2\phi(2)})\vee\cdots\vee(a_{n1}\wedge\cdots\wedge a_{n\phi(n)}))$ $\displaystyle=$ $\displaystyle(b\wedge a_{11}\wedge\cdots\wedge a_{1\phi(1)})\vee(b\wedge a_{21% }\wedge\cdots\wedge a_{2\phi(2)})\vee\cdots\vee(b\wedge a_{n1}\wedge\cdots% \wedge a_{n\phi(n)})$

which is in DNF using elements of $X$.

2. 2.

If $a,b\in B$, then $a\wedge b\in B$.

In the last expression of the previous step, notice that each term $b\wedge a_{i1}\wedge\cdots\wedge a_{i\phi(i)}$ can be written in DNF by iteratively using the result of the previous step. Hence, the join of all these terms is again in DNF (using elements of $X$).

3. 3.

If $a\in B$, then $a^{\prime}\in B$.

If $a=(a_{11}\wedge\cdots\wedge a_{1\phi(1)})\vee(a_{21}\wedge\cdots\wedge a_{2% \phi(2)})\vee\cdots\vee(a_{n1}\wedge\cdots\wedge a_{n\phi(n)})$, then

 $a^{\prime}=(a_{11}^{\prime}\vee\cdots\vee a_{1\phi(1)}^{\prime})\wedge(a_{21}^% {\prime}\vee\cdots\vee a_{2\phi(2)}^{\prime})\wedge\cdots\wedge(a_{n1}^{\prime% }\vee\cdots\vee a_{n\phi(n)}^{\prime}),$

which is the meet of $n$ elements in $B$. Consequently, by step 2, $a^{\prime}\in B$.

Since $B$ is closed under  join and complementation, $B$ is a Boolean subalgebra of $A$. Since $B$ contains $X$, $\langle X\rangle\subseteq B$. ∎

Similarly, one can show that $\langle X\rangle$ is the set of all elements in $A$ that can be written in conjunctive normal form  (CNF) using elements of $X$.

###### Corollary 1.

Let $\langle B,x\rangle$ be the Boolean subalgebra (of $A$) generated by a Boolean subalgebra $B$ and an element $x\in A$. Then every element of $\langle B,x\rangle$ has the form

 $(b_{1}\wedge x)\vee(b_{2}\wedge x^{\prime})$

for some $b_{1},b_{2}\in B$.

###### Proof.

Let $X$ be a generating set for $B$ (pick $X=B$ if necessary). By the proposition  above, every element in $\langle B,x\rangle$ is the join of elements of the form $a_{1}\wedge a_{2}\wedge\cdots\wedge a_{n}$, where each $a_{i}$ or $a_{i}^{\prime}$ is in $X$ or is $x$. By the absorption laws, the form is reduced to one of the three forms $a$, $a\wedge x$, or $a\wedge x^{\prime}$, where $a\in B$. Joins of elements in the form of the first kind is an element of $B$, since $B$ is a subalgebra. Joins of elements in the form of the second kind is again an element in the form of the second kind (for $(a_{1}\wedge x)\vee(a_{2}\wedge x)=(a_{1}\vee a_{2})\wedge x$), and similarly for the last case. Therefore, any element of $\langle B,x\rangle$ has the form $a\vee(a_{1}\wedge x)\vee(a_{2}\wedge x^{\prime})$. Since $a=(a\wedge x)\vee(a\wedge x^{\prime})$, by setting $b_{1}=a_{1}\vee a$ and $b_{2}=a_{2}\vee a$, we have the desired form. ∎

Remarks.

• If $a=(b_{1}\wedge x)\vee(b_{2}\wedge x^{\prime})$, then $a^{\prime}=(b_{2}^{\prime}\wedge x)\vee(b_{1}^{\prime}\wedge x^{\prime})$.

• Representing $a$ in terms of $(b_{1}\wedge x)\vee(b_{2}\wedge x^{\prime})$ is not unique. Actually, we have the following fact: $(b_{1}\wedge x)\vee(b_{2}\wedge x^{\prime})=(c_{1}\wedge x)\vee(c_{2}\wedge x^% {\prime})$ iff $b_{2}\Delta c_{2}\leq x\leq b_{1}\leftrightarrow c_{1}$, where $\Delta$ and $\leftrightarrow$ are the symmetric difference   and biconditional  operators.

###### Proof.

$(\Rightarrow)$. The LHS can be rewritten as $(b_{1}\vee b_{2})\wedge(b_{2}\vee x)\wedge(b_{1}\vee x^{\prime})$. As a result, $c_{2}\wedge x^{\prime}\leq b_{2}\vee x$ so that $c_{2}\vee x=(c_{2}\wedge x^{\prime})\vee x\leq(b_{2}\vee x)\vee x=b_{2}\vee x$. Therefore, $c_{2}-b_{2}=c_{2}\wedge b_{2}^{\prime}\leq(c_{2}\vee x)\wedge b_{2}^{\prime}% \leq(b_{2}\vee x)\wedge b_{2}^{\prime}=b_{2}^{\prime}\wedge x\leq x$. Similarly, $b_{2}-c_{2}\leq x$. Taking the join and we get $b_{2}\Delta c_{2}\leq x$. Dually, $b_{1}\Delta c_{1}\leq x^{\prime}$, and complementing this to get $x\leq(b_{1}\Delta c_{1})^{\prime}=b_{1}\leftrightarrow c_{1}$.

$(\Leftarrow)$. If $b_{2}-c_{2}\leq x$, then $b_{2}\vee c_{2}=(b_{2}-c_{2})\vee c_{2}\leq x\vee c_{2}$, so that $(b_{2}\vee c_{2})-x\leq c_{2}-x$, or $(b_{2}-x)\vee(c_{2}-x)\leq c_{2}-x$, which implies that $b_{2}-x\leq c_{2}-x$. Similarly, $c_{2}-x\leq b_{2}-x$. Putting the two inequalities  together and we have $b_{2}-x=c_{2}-x$. Since $x\leq b_{1}\leftrightarrow c_{1}$ is equivalent to $b_{1}\Delta c_{1}\leq x^{\prime}$ (dual statements), we also have $b_{1}-x^{\prime}=c_{1}-x^{\prime}$ or $b_{1}\wedge x=c_{1}\wedge x$. Combining (via meet) this equality with the last one, we get $(b_{1}\wedge x)\wedge(b_{2}\wedge x^{\prime})=(c_{1}\wedge x)\wedge(c_{2}% \wedge x^{\prime})$. ∎

Title Boolean subalgebra BooleanSubalgebra 2013-03-22 17:57:55 2013-03-22 17:57:55 CWoo (3771) CWoo (3771) 9 CWoo (3771) Definition msc 06E05 msc 03G05 msc 06B20 msc 03G10 dense subalgebra dense Boolean subalgebra