Yorkville High School Computer Science Department
Yorkville High School Computer Science Department on Facebook  Yorkville High School Computer Science Department Twitter Feed  Yorkville High School Computer Science Department on Instagram

Yorkville High School Computer Science

ASSIGNMENTS: Mobile App - May 10, 2019 :: UI Project - May 10, 2019 :: Web App - May 15, 2019 >>

Operating System Design :: Lessons :: Boolean Logic

Boolean Algebra

This lesson is a synopsis of Chapter 1 from the book Building a Modern Computer From First Principles. After reading this synopsis you should read that chapter as well as Appendix A that describes the Hardware Description Language. Boolean values, sometimes called binary values, are typically labeled true/false, 1/0, yes/no, on/off, and so forth. The simplest way to specify a boolean function is by using a truth table that specifies that function's outputs based on its inputs. Below is an example truth table for the Boolean function (x + y) • x̄ where x̄ means NOT x.

x y z f(x, y, z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0

Every Boolean function can be expressed using And, Or, and Not. Below are all the possible Boolean function using two variables.

x 0 0 1 1
Function y 0 1 0 1
Constant 0 0 0 0 0 0
And x • y 0 0 0 1
x And Not y x • ȳ 0 0 1 0
x x 0 0 1 1
Not x And y x̄ • y 0 1 0 0
y y 0 1 0 1
Xor x • ȳ + x̄ • y 0 1 1 0
Or x + y 0 1 1 1
Nor x + y 1 0 0 0
Equivalence x • y + x̄ • ȳ 1 0 0 1
Not y ȳ 1 0 1 0
If y then x x + ȳ 1 0 1 1
Not x 1 1 0 0
If x then y x̄ + y 1 1 0 1
Nand x • y 1 1 1 0
Constant 1 1 1 1 1 1

Gate Logic

A gate is a physical device that implements a Boolean function. Today's computers rely on electricity to implement gates with chips that are transistors etched in silicon. There are three primitive gates that can be used to construct composite gates. The three primitive gates are And, Or, and Not.

And Gate
Or Gate
Not Gate

Composite gates are gates made up of primitive gates. The example below represents the function if (a=b=c=1) then out = 1. The interface of a gate only shows its inputs and outputs while the implementation of a gate shows the primitive gates the composite gate is composed of.

3-Input And Gate Xor Gate Interface

An Xor gate takes two inputs and outputs 1 if exactly one of the inputs is 1. Below is the interface and implementation of an Xor gate. A gate's interface is unique, meaning that there is only one way to describe it using a truth table. However, different implementations can be used to realize an interface. Some implementation are better than others in terms of speed, cost, and simplicity. In general, it is best to use as few primitive gates as possible to implement a composite gate.

Xor Gate Implementation

Circuit Implementation

You can easily construct working gates yourself with some silicon, transistors, copper wire, and a soldering iron. You can see the structure of an And Gate in the electrical diagram below. Electricity can only flow through the wire if the transistors at inputs A and B are both "open" or at a high voltage level.

And Gate Electrical Diagram

An Or Gate has a different diagram that allows electrical flow if either of the input gates are "open."

Or Gate Electrical Diagram

Below is an electrical diagram of the 3-input And Gate we saw earlier.

3-Input And Gate Electrical Diagram

Hardware Description Language

A Hardware Description Language or HDL is language used for modeling hardware. A tool called a hardware simulator take an HDL program as input and builds an image of the working chip in memory. The outputs of that chip can then be inspected to determine if they produce the desired results. Hardware simulators are usually designed to run test scripts that are written in a scripting language. These test scripts act like unit tests to determine if the chip behaves as expected.

The hardware simulator that will be used in this course can be downloaded here. You can follow the steps on the website to run the software. You can see a tutorial of the hardware simulator here.

Yorkville High School Computer Science Department on Facebook Yorkville High School Computer Science Department Twitter Feed Yorkville High School Computer Science Department on Instagram