Intro to Computer Systems

Chapter 3: Digital Logic & Boolean Algebra

Digital Logic

Boolean Algebra

Boolean algebra is appropriate for computing, since it is based on the notion of true or false, which a computer can easily handle as 0 and 1. It consists of operands that are either true or false, and operations to combine those operands. Usually, true is represented as 1, and false as 0. The following shows the most common operators:

OR operator: returns true when either operand is true. In algebra it is denoted as + (plus), while in computer programming it is a || (double pipe). A table of results with this operator is as follows:

OR + or ||
0 + 0
= 0
0 + 1
= 1
1 + 0

= 1

1 + 1
= 1

AND operator: returns true when both operands are true. Its algebraic symbol is . (period), and in programming it is a && (double ampersand).

AND . or &&
0 . 0
= 0
0 . 1
= 0
1 . 0

= 0

1 . 1
= 1

NOT operator: this is a unary operator (it only takes in one term) that returns the opposite value; that is, it returns true if the operand is false, and false if the operand is true. Its algebraic symbol is - (minus), and in programming it is a ! (exclamation point).

NOT - or ~ or !
0
1
1
0
A NOT operation may also be shown with a slash (e.g. /a), or a bar (a).

Operator Precedence

Similarly to normal arithmetic, to make sure that operations are performed in the right order, these operators are given a precedence. For example, we know that in normal arithmetic 2 + 3 * 4 is interpreted as 2 + (3 * 4) = 14, rather than (2 + 3) * 4 = 20, since the multiplication ‘binds stronger’ than the sum. If we need to change the precedence of the evaluation, we use brackets.

When a Boolean operator has a higher precedence than another, it also means that it binds stronger, with similar consequences. As it may be seen in Table 8.4, the highest precedence is the (), followed by NOT, AND and OR.

( ) highest precedence
NOT  
AND  
OR lowest precedence

Therefore:

-a + b . c + d = (-a) + (b . c) + d

Note that since the () have higher precedence that any other operator, you can use () to change the precedence of evaluation to whatever is required. For example the expression above may be changed to:

(-a) + b . (c + d)

if so desired; the brackets forcing the evaluation the new way.

These Boolean operations have particular characteristics that are different to the ones we are used to. Table 8.5 shows a few:

0 + X = X
0 . X = 0
X = -(-X)
1 + X = 1
1 . X = X
X + X = X
X . X = X
X + -X = 1
X . -X = 0

Since these operators work on binary data, it is often possible to prove an identity such as the ones above by going through all the possible situations that may occur, verifying that the equality holds true at all times. This is called a truth table and they are used very often. As an example, let us prove the identity X + X = 1 using a truth table:

Truth table for X + -X = 1
X -X X + -X
0
1
1
1
0
1

Digital Logic Gates

Computer hardware is comprised of binary logic systems, which are made using logic gates. There are three basic logic gates: AND, OR, NOT and the derived negated gates: NAND, NOR, XOR, XNOR. All logic systems may be built out of the first three, or out of NAND and NOR gates. These gates are implemented in standard configurations, and later on these in turn are combined to produce complete circuits.

AND Gate

There are two inputs and one output. The output is true only when both inputs are true: when all inputs are 1, the output is also a 1. The AND Boolean expression is: A . B. In a logic diagram, it is represented by this symbol:

AND gate
An AND gate symbol.

The behaviour of a gate may be expressed using a truth table. This defines the output for all possible combinations of inputs.

Inputs Output
A B X
0
0
0
0
1
0
1
0
0
1
1
1

OR Gate

There are two inputs and one output. The output of the gate is true when either of the inputs is true. The equivalent boolean expression is A + B. The corresponding symbol and truth table are:

OR gate
An OR gate symbol.
Inputs Output
A B X
0
0
0
0
1
1
1
0
1
1
1
1
Logic design software (e.g. DigitalWorks) gives you the option of gates with more than two inputs (e.g. 3 or 4 inputs to an AND or OR gate). This often simplifies logic diagrams.

NOT Gate

There is a single input and a single output. The output is the opposite state to the input, i.e. the output is the input inverted. The symbol and truth table for a NOT gate are as follows:

NOT gate
A NOT gate symbol.
Input Output
A X
0
1
1
0

Universal Logic Gates

The universal logic gates, NAND and NOR are used to build logic systems instead of the basic AND, OR, NOT as they are more flexible in that only one type of gate is needed to build a logic system, and this results in cheaper costs.

You may hear of flash memory chips being referred to in the tech press as being called "NAND Flash". This means they are talking about flash memory chips that have an internal transistor structure that looks similar to a NAND gate.

NAND flash is the typical type, as how it can be accessed is more appropriate to general data storage, and with economies of scale, is much cheaper to build.

NAND Gate

This is equivalent to the Boolean Expression: X = -(A . B) (i.e. NOT (A AND B)).

The symbol and truth table for the NAND gate is:

NAND gate
A NAND gate symbol (left), along with its equvalent (right).
Inputs Output
A B X
0
0
1
0
1
1
1
0
1
1
1
0

NOR Gate

This is equivalent to the Boolean expression X = -(A + B) (i.e. NOT (A OR B)).

The symbol and truth table for the NOR gate is:

NOR gate
A NOR gate symbol (left), along with its equvalent (right).
Inputs Output
A B X
0
0
1
0
1
0
1
0
0
1
1
0

XOR Gate

This is a slightly different gate, very commonly used in digital logic. It is called the Exclusive OR, written with the expression A ⊕ B. For this gate the output is true when the inputs are different, and it is false when the inputs are the same.

XOR gate
An XOR gate symbol.
Inputs Output
A B X
0
0
0
0
1
1
1
0
1
1
1
0

 

XNOR Gate

This gate is the negation of the XOR gate, and so it corresponds to the Boolean expression -(A ⊕ B). Naturally, the output of the XNOR gate is 1 when both inputs are the same, as this is opposite of the XOR gate.

XNOR gate
An XNOR gate symbol.
Inputs Output
A B X
0
0
1
0
1
0
1
0
0
1
1
1

Advantages of Universal Logic Gates

The advantage of using the NOT versions of the gates is that we don’t need a special gate to implement the NOT logic. The following circuit implements a NOT gate out of a NAND gate:

A NOT gate using a NAND gate
A NOT gate built from a NAND gate.

Combinatorial Logic

Combinational logic consists of a logic circuit built with logic gates, to implement an output determined by the logic gates and the current set of inputs. There is no memory in the system, that is, the output depends exclusively of the inputs. An example combining and AND gate with an OR gate is as follows:

Sample combinatorial logic
Sample combinatorial logic

In practice, these gates are not provided individually but in integrated circuits, such as:

A 7400 logic chip: four 2-input NAND gates
A 7400 logic chip: four 2-input NAND gates

The most common situation is to build a circuit from a given Boolean expression. Re­call that this is the reason why we try to simplify expressions, so circuits are easier to build. For example, the SOP expression A . B + C . D is built very simply with two AND gates joined together with an OR gate:

A . B + C . D as combinatorial logic
A . B + C . D as combinatorial logic

Draw logic circuits for the following Boolean expressions:

  1. A . B + -C + D
  2. A + B . C . D
  3. A . B + -C . -D

Binary Adders

Half Adders

To be able to add binary numbers, we need to add individual bits properly, that is, we should be able to calculate their sum with the corresponding carry. The Truth Table for a 1-bit adder - a half-adder - is as follows:

Inputs Outputs
A B Sum Carry
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1

This is the logic for a half-adder, as implemented with standard gates:

A half adder, implemented with standard logic gates.
A half adder, implemented with standard logic gates.

The formulas corresponding to a half-adder are as follows:

Sum = /A.B + A./B
Carry = A.B

Note that the circuit reflects exactly the truth table and the formulas. Note also that this output is the output from an XOR gate so that a half adder can be represented by:

A half adder, implemented with standard logic gates.
A half adder, implemented with an XOR gate.

The downfall of half adders is that while they can generate a carry out output, they cannot deal with a carry in signal. This means that they can only ever be stand-alone units, and cannot be concatenated to add multiple bit numbers.

Full Adder

In a more complex operation, to add two bits properly we have to make sure not only that we add the two bits, but also that we add the carry properly. The design could be carried out again via a truth table, but a better method is to use two half-adders, since this approach is based on existing components. A full-adder is able to add in the carry from the previous column in a two-digit binary number, like this:

The logic for a full adder
The logic for a full adder

A full adder thus solves this problem by adding three numbers together - the two addends as in the half adder, and a carry in input.

A full adder can be constructed from two half adders by connecting A and B to the input of one half adder, connecting the sum from that to an input to the second adder, connecting the carry in, Cin, to the other input and ORing the two half adder carry outputs to give the final carry output, Cout.

This can be summarised in the following diagram:

Constructing a full adder from two half adders.
Constructing a full adder from two half adders.

Parallel Adder

A multi-digit adder may be implemented by cascading full-adders, as shown in Figure 8.14. The .gure shows 4 full-adders, in which the carry out of each full-adder is fed into the next one. The scheme is initialised with 0 as the .rst carry in, and the last carry out is the carry out of the whole adder.

The logic for a parallel adder
The logic for a parallel adder