Content

Boolean Algebra 2

It's algebra, Jim, but not as we know it

Although we appear to be going off in a completely new direction, we will get back to switching circuits . When we do we will have powerful, algorithmic, tools for producing the simplest switching circuits for any specified problem. We have already cheated by using these tools in some of the answers to the problems of the last section.

As we know, one rather odd thing happens with the zeros and ones that we used in the switching circuits . Everything looks normal when you multiply. You would expect and get

\[0 \times 0 = 0; \quad 0 \times 1 = 0 =1 \times 0;\quad \mbox{ and } 1 \times 1 = 1.\]

But addition throws up something new. Sure

\[0 + 0 = 0;\quad 0 + 1 = 1 = 1 + 0; \]

But 1 + 1 = 1! This is not what you might have guessed ahead of time. After all we normally get 1 + 1 = 2 and in arithmetic base 2, 1 + 1 = 0. However, 1 + 1 = 1 is quite different.

On the other hand, there are other places where sort of 1 + 1 is 1, but you might not have thought of it that way. Think about set theory. If you have the set of all sets contained in some set $I$, the power set of $I$, then the union of $I$ with itself is $I$. So$ I \cup I = I$. If we think of union as being addition does it give us the arithmetic above that we got for zeros and ones?

Ah, but $I \cap I = I$ too. Would we be better off using intersection for addition if we want to find another example of 1 + 1 = 1?

It turns out that we have stumbled into a whole new ballgame. The zeros and ones we started with and the sets we looked at next, are all examples of a useful axiomatic system that contains lots of examples other than the two we have been playing with. This axiomatic system is called Boolean algebra (see https://en.wikipedia.org/wiki/Boolean_algebra).

A Boolean algebra, $B$, is a set $B$ on which operations $+, \times$ and complementation are defined along with a zero and a one, which satisfy the following axioms.

• Axiom 1

  $B$ contains at least two elements.

• Axiom 2

  $B$ is closed under $+$ and $\times$. That is for all $x$ and $y$ in $B$, $x + y$ and $x \times y$ are in $B$.

• Axiom 3

  $+$ and $\times$ are commutative. That is for all $x$ and $y$ in $B$, $x + y = y + x$ and $x \times y = y \times x$.

• Axiom 4

  + and $\times$ are associative. That is, for all $x, y$ and $z$ in $B$, $(x + y) + z = x + (y + z)$ and $(x \times y) \times z = x \times (y \times z)$.

• Axiom 5

  $\times$ is distributive over + and + is distributive over $\times$. That is, for all $x, y$ and $z$ in $B$, $x \times (y + z) = (x \times y) + (x \times z)$, while $x + (y \times z) = (x + y) \times (x + z)$.

• Axiom 6

  + and $\times$ have identities in $B$ which are denoted, respectively, by 0 and 1. That is for all $x$ in $B$, $x + 0 = x$ and $ x \times 1 = x$.

• Axiom 7

  + and $\times$ obey two absorption laws. That is, for all $x$ and $ y$ in $B$, $x + (x \times y) = x$ and $x \times (x + y) = x$.

• Axiom 8

  + and $\times$ both have a common complement. That is, for all $x$ in $B$, there is an $x'$ in $B$ such that $x + x' = 1$ and $x \times x' = 0$.

Before you think that we are still right off track, we should say that this is actually going to be very useful for switching circuits. But there is more to deal with before we can get to that point. In fact, for a time, we are going to delve in the life of a pure mathematician. There may have been quite a lot of things that you have been assuming about Boolean algebras that are true but which need to be supported by the axioms. If they aren't, they are not true and you shouldn't have been using them. So what would a pure mathematician say? What would one of these rare creatures worry about?

First worry: $ x + x = x$. It's clearly true in our switching circuits that two of the same switches in parallel are the same as just one on its own. It also works for the power set (see the answer to Q7) of a set. Does it work for all of the other Boolean algebras that you now know? Alright, BUT it's not an axiom! So how do we know it's true for all Boolean algebras? Well, is it supported by the axioms? Let's look.

\begin{alignat*}{3} x + x &= (x + x) \times 1 && \qquad \mbox{(this is OK by axiom 6)}\\ &= (x + x) \times (x + x') && \qquad\mbox{(axiom 8)}\\ &= x + (x \times x') && \qquad \mbox{(axiom 5)}\\ &= x + 0 &&\qquad\mbox{(axiom 8)}\\ &= x &&\qquad\mbox{(axiom 6)} \end{alignat*}

The problem here is how do you choose the right path to go down? What axioms do you need and in what order? There's no really good answer to this. You just have to play around for a start until you have a better intuition of the axioms. Then you have to play around till you get the right ones. It looks as if there isn't an algorithm that might help you.

Second worry: $x \times x = x$. Does it seem to be true? Try it.

\begin{alignat*}{2} x \times x & = x \times x + 0 &\qquad \mbox{(axiom 6)}\\ &= x \times x + x \times x' &\qquad \mbox{(axiom 8)}\\ &= x \times (x + x') &\qquad \mbox{(axiom 5)}\\ &= x \times 1 &\qquad \mbox{(axiom 8)}\\ &= x &\qquad \mbox{(axiom 6)} \end{alignat*}

There are more worries in the next set of questions.

A mathematical note

In your role as pure mathematician you may have noticed some symmetry in what has been going on. It looks as if we have a result in Boolean algebra and we interchange + and $\times $, and 0 and 1, then we get a new result that it also true. This is called the principle of duality and it is sometimes useful as it reduces the number of things that you need to prove for any conjecture in Boolean algebra. Check that the axioms show this principle. So now worry on.

In Boolean algebra you may have met an abstract quantity defined by axioms for the first time. It turns out that there are a whole host of them in what is known as Abstract Algebra. Things such as groups, rings and fields are also defined by sets of axioms. All of these objects arose in attempts to generalise something that occurred naturally. For example, groups (see https://en.wikipedia.org/wiki/Group_(mathematics)) have only one operation and could be thought of as generalisations of the integers with addition being the only operation; rings (see https://en.wikipedia.org/wiki/Ring_(mathematics)) have two operations and are generalisations of the integers with two operations, addition and multiplication; and fields (see https://en.wikipedia.org/wiki/Field_(mathematics)) again have two operations and have developed from the rational numbers with addition and multiplication. Like Boolean algebra, generalisations have been studied by pure mathematicians and have applications outside mathematics.

Using `$\times$' for multiplication is beginning to get tedious. In normal arithmetic we avoid this tedium by replacing $x \times y$ by $xy$. Let's do this from here on.

Next page - Content - Switches again