CS110: Introduction to Computing Study Notes

Building a Computer: Logic Circuits

Outline

• Overview of topics covered

• Deep dive into:

  • Boolean Functions

  • Logic Circuits

Boolean Functions

• Definition of Variable:

  • A variable (e.g., age) associates a name with a value.

• Boolean Variables:

  • A boolean variable (e.g., isRed) can take the value of 1 (True) or 0 (False).

• Boolean Function:

  • A boolean function is an algebraic expression consisting of boolean variables and logical operations.

Basic Boolean Functions

• The three basic boolean functions are:

  • not(x) = x' (where x' is the negation of x)

  • or(x, y) = x + y (logical OR)

  • and(x, y) = x · y (logical AND)

Truth Tables

• Definition:

  • The truth table for a boolean function describes its input(s) and output(s).

• Example Truth Tables:

  • For the not function, not(0) = 1, not(1) = 0.

  • For the or function:

  • Inputs: (0,0), (0,1), (1,0), (1,1)

  • Outputs: 0, 1, 1, 1 respectively.

  • For the and function:

  • Inputs: (0,0), (0,1), (1,0), (1,1)

  • Outputs: 0, 0, 0, 1 respectively.

• Combined Truth Table Data:

  • A summarized table combining the outputs:
    | x | y | not(x) | or(x, y) | and(x, y) |
    |---|---|---------|----------|------------|
    | 0 | 0 | 1 | 0 | 0 |
    | 0 | 1 | 1 | 1 | 0 |
    | 1 | 0 | 0 | 1 | 0 |
    | 1 | 1 | 0 | 1 | 1 |

Minterm Expansion Algorithm

• Any boolean function can be expressed in terms of the basic boolean functions through the Minterm expansion algorithm which involves the following steps:

  1. Write down the truth table for the boolean function.

  2. Delete all rows from the truth table where the value of the function is 0.

  3. For each remaining row, create a "minterm" as follows:

  • For each variable x: if its value is 1, write x; otherwise, write x'.

  • Combine the variables using · (logical AND).

  1. Combine the minterms using + (logical OR).

Example Problem

• Proposition: "If you score over 93% in this course, then you will get an A."

• This proposition can be described using the implication function:

  • imp(x, y) = x ⇒ y or in minterm form:

  • The final expression is imp(x, y) = x · y' + x' · y + x · y.

Logic Circuits

• Definition:

  • Circuits (called gates) that implement the not, or, and and functions.

• Logic Gates:

  • NOT Gate: Implements the not function.

  • OR Gate: Implements the or function.

  • AND Gate: Implements the and function.

Circuit Representation

• Circuits implementing various logical functions:

  • NOT Circuit:

  • Input: 0 gives output 1 and input: 1 gives output 0.

  • AND Circuit:

  • Logic representation of and(x, y):

  • Outputs based on combinations of x and y.

  • OR Circuit:

  • Displays how outputs change with different inputs.

Full Adder (FA) Circuit

• A full adder circuit adds two 1-bit numbers along with a carry input:

  • Produces a 2-bit result represented as:

  • Inputs: x, y, Cin (carry-in)

  • Outputs: Z (sum), Cout (carry-out).

• Truth Table of Full Adder:

  • The output depends on various combinations of inputs:
    | x | y | Cin | Z | Cout |
    |---|---|-----|---|------|
    | 0 | 0 | 0 | 0 | 0 |
    | 0 | 0 | 1 | 1 | 0 |
    | 0 | 1 | 0 | 1 | 0 |
    |…|…| … |…| … |

n-bit Ripple-Carry Adder

• An n-bit ripple-carry adder for adding two n-bit numbers is formed by chaining together n full adder circuits.

Additional Logic Gates and Memory Circuits

• An n-bit memory circuit called a latch, built using two NOR gates:

  • Reset and Set functions are defined:

  • Example of a 1-bit latch:

  • Implementations of latch functions involve combinations of states (S, R) to yield outputs (Q, Q').

• A billion latches can be combined to produce a 1GB Random Access Memory (RAM) module.