Introduction to digital logic

Robert P. Webber, Don Blaheta, Longwood University
Why are we working on this? Now that we know how to represent everything as bits, we want to think about how the computer can process data when that data is all 1s and 0s. When the inputs and outputs are 1s and 0s, all computation—all algorithms—can be built from just a handful of operations. Skills in this section: Give truth table for each standard gate, and vice versa Concepts: Algorithm representation

Digital logic is at the "bottom" of the computer. It models what happens when we strip away all the programming languages and prewritten packages, and try to understand how the computer actually performs operations. For example, how does a computer actually add two binary numbers? To understand that, we have to understand digital logic.

Digital logic is based on the fundamental operations from symbolic logic: and, or, and not. These are called logical operations or Boolean operations, after George Boole, who was the first person to analyze them.

Boolean variables have precisely two values, true and false (often represented by 1 and 0). A Boolean value can be represented by a bit, or a binary digit.

We can represent Boolean operations by tables of 0s and 1s, showing what happens in every combination of bits. These tables are like the truth tables that are used in symbolic logic.

Here are the definitions of the basic functions.

Not This function just reverses the value of the variable: not true = false, and not false = true . Let A be the variable. Possible values of A are 1 and 0 (true and false).

A not A
0 1
1 0

Or The or function takes two operands. It is true if at least one operand is true and false if both are false . Let A and B be the operands. Each can be true or false . This means there are four possible combinations.

A B A or B
0 0 0
0 1 1
1 0 1
1 1 1

The order of the rows doesn't matter. This table:

A B A or B
1 1 1
1 0 1
0 1 1
0 0 0
defines the same operation.

And This function takes two operands. It is true if both operands are true and false otherwise.

A B A and B
0 0 0
0 1 0
1 0 0
1 1 1

These functions have special graphical symbols.

not or and

Electrical engineers can physically construct these basic functions from wire, silicon, and transistors. They are called gates, and they are the basis for modern computers. A computer is, at its most basic level, a bunch of connected gates. Agreeing a standard symbol for each kind of gate lets us represent entire computation systems in diagram form, and to build them virtually in simulators such as Logisim.

The idea of a truth table is also a very powerful one: Once we have enough rows to represent all possible combinations of inputs (for two inputs, there's 00, 01, 10, and 11—have we seen that pattern before?), by putting different combinations of 1s and 0s in the output column we can represent every possible different computable function with that many inputs.

Exercises

  1. Here is a truth table for a logical function F.

    X Y F
    0 0 0
    0 1 0
    1 0 0
    1 1 1

    Which standard gate does F correspond to?

  2. Here is the diagram for a circuit.

    A B F
    0 0 0
    0 1
    1 0
    1 1

    Complete the truth table. The first line has been done for you as an example.

  3. Here is a truth table for a logical function F.

    I2 I1 F
    0 0 1
    0 1 0
    1 0 1
    1 1 1
    What is the value of F for inputs
    1. I2 = 1, I1 = 0?
    2. I2 = 0, I1 = 1?
    3. I2 = 1, I1 = 1?
  4. Here is a truth table for a logical function F.
    I2 I1 F
    0 0 1
    0 1 1
    1 0 0
    1 1 1

    What is the value of F for inputs

    1. I2 = 0, I1 = 1?
    2. I2 = 1, I1 = 0?
    3. I2 = 0, I1 = 0?

Credits and licensing

This article is by Robert P. Webber and Don Blaheta, licensed under a Creative Commons BY-SA 3.0 license.

Version 2016-Mar-23 02:50