Building a Modern Computer 1.1 - 1.4

Logical Values (1.1)

The course begins with the discussion of logical boolean values. In case you missed the my review of the introduction to the course, it would be a good idea to begin there first. Boolean values are true/false, on/off, or 1/0 respectively. We will use basic variables, such as (x, y) for the inputs, or (a, b c) if using three. The inputs will be boolean values and the output will be a boolean value as well. The following are basic ways to play with boolean logic.

AND

An AND operation takes two inputs and outputs a single value. If both inputs are true, the output is true. Otherwise, the output is false.

Eg: (true AND true) = true; (true AND false) = false;

OR

An OR operation takes two inputs and outputs a single value. If either input is true, the output is true. Otherwise, the output is false.

Eg: (true OR false) = true; (false OR false) = false;

NOT

A NOT operation takes one input and returns a single value that is the opposite of the input value.

Eg: NOT(true) = false; NOT(false) = true;

Combining Operations into Boolean Functions

A boolean function looks like this: f(x, y) = NOT(x AND y) And has a truth table that looks like this:

x	y	f
0	0	1
1	0	1
0	1	1
1	1	0

This means we take the NOT value of (x AND y). We could use different basic laws of boolean algebra, such as the commutative law, like this:

Commutative Law

f(x, y) = NOT(x AND y) = NOT(y AND x);

Associative Law

f(x, y, z) = (x AND (y AND z)) = ((x AND y) AND z);

x	y	z	f
0	0	0	0
1	0	0	0
0	1	0	0
0	0	1	0
1	0	1	0
0	1	1	0
1	1	0	0
1	1	1	1

Distributive Law

f(x, y, z) = (x AND (y OR z)) = (x AND y) OR (y AND z);

x	y	z	f
0	0	0	0
1	0	0	0
0	1	0	0
0	0	1	0
1	0	1	1
0	1	1	0
1	1	0	1
1	1	1	1

De Morgan’s Law

NOT(x AND y) = NOT(x) OR NOT(y);

Boolean Expressions to Boolean Functions (1.2)

If we are given a truth table, such as this,

x	y	f
0	0	1
1	0	1
0	1	1
1	1	0

We can get the boolean expression that matches it by taking all of the rows that output 1 and making an expression from it. Then combine the lines with a 1 output with an OR statement. Like the following:

x	y	f
0	0	1	(NOT(x) AND NOT(y)) OR
1	0	1	(x AND NOT(y)) OR
0	1	1	(NOT(x) AND y)
1	1	0

Any function can be combined using AND, NOT and OR. But we do not even need OR, because we have De Morgan’s law. For example, if we took the previous expression and applied De Morgan’s Law, it would begin something like this:

(NOT(x) AND NOT(y)) OR (x AND NOT(y)) OR (NOT(x) AND y) = NOT(NOT(x) AND NOT(y)) AND NOT(x AND NOT(y)) AND NOT(NOT(x) AND y) = (x AND y) AND (NOT(x) AND y) AND (x AND NOT(y));

NAND

NAND outputs are true unless both inputs are true. So, actually, we can express any boolean function using only NAND.

(x AND y) = NOT(x NAND y);

Logic Gates (1.3)

A logic gate is a standalone chip that is designed to deliver specific functionality.

AND

Two inputs and a single output. If (x === 1 AND y === 1) then out = 1 else out = 0

OR

Two inputs and a single output. If (x === 0 AND y === 0) then out = 0 else out = 1

NOT

One input and a single output. If (x === 0) then out = 1 else out = 0;

NAND

Two inputs and a single output. If (x === 1 AND y === 1) then out = 0 else out = 1

Composite Logic Gates

Composite logic gates are made up of elementary logic gates combined. For instance, two AND gates are combined to form a larger AND gate with 3 inputs and one output.

(x AND y AND z) = (x AND (y AND z)) = ((x AND y) AND z);

But in this course, we will not deal with physical implementations because that is electrical engineering rather than computer science.

Hardware Description Language (1.4)

In this course we will use a Hardware Description Language, or HDL, to build our logic gates. Some common HDLs are VHDL, or Verilog. The HDL used in this course is similar to others in use. HDL is a functional/declarative language that is a textual description of the gate diagram. I could show some examples, but at this time in the course we have yet to write one (which will be coming in the near future). Until then, here is a great summary of an HDL file example.

Summary

So, in this introduction we learned about basic boolean operations and about building boolean expressions and functions. We also covered logic gates and their elementary constructions as well as a quick introduction to using HDL. There was a lot to cover, so if you would like to dig deeper, please refer to the course itself. I look forward to what tasks lie ahead in our quest to build a modern computer. Click here to go to the next part of the course summary.