Practical Electronics/Logic/Boolean Arithmetic

From Wikibooks, open books for an open world
< Practical Electronics‎ | Logic
Jump to: navigation, search

Boolean algebra (named after the mathematician George Boole) is a form of aritmetic that deals solely in ones and zeroes. It has only three operators: addition, multiplication and negation. As we shall see these correspond to OR, AND and NOT repectively.

XOR is sometimes included for convenience, and we shall see how in the XOR section.

Variables are written as capital letters, unlike "real" algebra, where lowercase ones can be used.

This page is not concerned with the identities and properties of boolean operators beyond that of the equivalence to the logic functions. These properties are discussed on the Boolean Identities page.

Negative Numbers, Subtraction and Division[edit]

As 1 and 0 are the only permissible numbers in Boolean algebra, there can be no negative numbers.

This means that there is no subtraction, as 0-1 is the same as 0+(-1). -1 is not an allowed number, so the concept of subtraction is meaningless in Boolean algebra.

As division is just a variation on subtraction, just as multiplication is a variation on addition, division is also meaningless in Boolean algebra.

Addition[edit]

Consider the following sums:

0+0=0\,
0+1=1\,
1+0=1\,
1+1=1\,

The first three make sense, as the same holds true for real algebra. The fourth statement, however, is different as it goes against real arithmetic. 2 is not allowed in Boolean algebra so it cannot be the answer, and 1+1 is definitely not equal to 0, so the answer must be 1.

A B Q
A+B
0 0 0
0 1 1
1 0 1
1 1 1

If we display the above equations in a table as on the left, it is clear that the Boolean addition operator is equivalent to the logical OR. This is why the logic OR operator has a plus sign as its symbol:

A\mbox{ OR }B = A + B\,


Multiplication[edit]

Consider the following equations:

0 \times 0=0\,
0 \times 1=0\,
1 \times 0=0\,
1 \times 1=1\,

As you can see, multiplication behaves in exactly the same way with Boolean algebra as it does in real arithmetic: anything multiplied by zero becomes zero, and anything multiplied by one stays the same.

You should be able to see that the multiplication operator has exactly the same effect as the logical AND operator, and this is why the AND function is represented by multiplication:

A\mbox{ AND }B = A \cdot B =AB\,

Complementation[edit]

Because there are only two numbers in Boolean algebra, if we know the value of a variable, then we automatically know the value of the number that it isn't. This number is the complement of the variable. Thus 0 is the complement of 1 and 1 is the complement of zero. A complement of a variable is written as the variable with a line over it:

\mbox{Complement of A}=\overline A

If a line cannot be drawn over the variable, as in text like this, then a "¬" symbol is used before the variable. This should not be used if a line can be drawn over the variable. Sometimes, a "prime" symbol (') is placed after it, but this should never be used.

Complementation is equivalent to a logical NOT.

NOR and NAND[edit]

These two logic fuctions are made up of the complement of their respective underlying functions:

A\mbox{ NAND }B = \overline{A \cdot B}\,
A\mbox{ NOR }B = \overline {A + B}\,

XOR and XNOR[edit]

XOR cannot be represented as a simple Boolean function such as addition or multiplication, and as such, it is not directly supported by Boolean algebra. Nevertheless, it does have a symbol - a plus sign in a circle.

A\mbox{ XOR }B =A \oplus B\,

The XNOR function is given as:

A\mbox{ XNOR }B =\overline{A \oplus B}\,

As the rules and identities of Boolean algebra do not apply to this invented function, when writing and simplifying logical statements, the following equivalent substitution is used:

A \oplus B=\bar A B + A \bar B.

It is easy to see how this substitution works. The XOR function gives a high output if one and only one of the inputs is high. In this case, the complement of one input is equal to the other input. When the inputs are the same (i.e. the XOR function returns a low), one input and the complement of the other will be different. Therefore, by ANDing the first input and the second's complement, and ANDing the first's complement and the second input, we will always have a high at the output of one of the AND gates when only one input is high. BY ORing these two together, we get a high at the final output if either one is high and the other one is low.

This uses one of the alternative gate arrangements shown here.

XNOR can be substituted as:

\overline{A \oplus B}=\overline{\bar A B + A \bar B}.

Summary[edit]

  • Boolean addition is equivalent to a logical OR.
  • Boolean multiplication is equivalent to a logical AND.
  • Boolean complementation is equivalent to a logical NOT.
  • XOR has its own special symbol as it is not directly included in the framework of Boolean algebra.