Boolean Logic

Binary / Boolean Logic
This document was primarily made from the first couple “slides” from this website – http://computer.howstuffworks.com/boolean.htm

Have you ever wondered how a computer can do something like balance a cheque book, or play chess, or spell-check a document? These are things that, just a few decades ago, only humans could do. Now computers do them with apparent ease. How can a “chip” made up of silicon and wires do something that seems like it requires human thought?

If you want to understand the answer to this question down at the very core, the first thing you need to understand is something called Boolean logic. Boolean logic, originally developed by George Boole in the mid 1800s, allows quite a few unexpected things to be mapped into bits and bytes. The great thing about Boolean logic is that, once you get the hang of things, Boolean logic (or at least the parts you need in order to understand the operations of computers) is outrageously simple. In this article, we will first discuss simple logic “gates,” and then see how to combine them into something useful.

Background
When we write a number, each position represents a value. Think of the 1’s place, the 10’s place, the 100’s place and so on.

In base 10 a number like 5042 is:
(5*1000) + (0*100) + (4*10) + (2*1)
or
5000 + 0 + 40 + 2

In base 2 each position also represents a value. The first place is the 1’s place, then the 2’s place, then 4’s place, then 8’s place, then 16’s place.

In base 2 a number like 11011 is:
(1*16) + (1*8) + (0*4) + (1*2) + (1+1)
or
16 + 8 + 0 + 2 + 1 = 27

Go to this website and play the binary game – http://forums.cisco.com/CertCom/game/binary_game_page.htm

 

Question: What is the difference between a bit and a byte?
In computers you hear the terms “bit” and “byte”.  A bit is two states: on or off.  A byte is 8 bits.  A bit is uses a small “b” and a byte uses an uppercase “B”. 

Don’t get confused …How long would it take to download at 200 MB file on an internet connect promising downloads at 100 Mbps (mega bits per second)?  The answer is NOT 2s.  The connection is 100 divided by 8 … or 12.5 MBps.  So it will take at least 16 seconds to download.  Watch this crazy video if you want a video answer – https://www.youtube.com/watch?t=260&v=Dnd28lQHquU

Three Fundamental Gates
There are three, five or seven simple gates that you need to learn about, depending on how you want to count them (you will see why in a moment). With these simple gates you can build combinations that will implement any digital ­component you can imagine. These gates are going to seem a little dry here, and incredibly simple, but we will see some interesting combinations in the following sections that will make them a lot more inspiring.

NOT Gate
The simplest possible gate is called an “inverter,” or a NOT gate. It takes one bit as input and produces as output its opposite.

The NOT gate has one input called A and one output called Q (“Q” is used for the output because if you used “O,” you would easily confuse it with zero). The table shows how the gate behaves. When you apply a 0 to A, Q produces a 1. When you apply a 1 to A, Q produces a 0.

The logic (truth) table is:

A Q
0 1
1 0

Make sure you understand this table!  They get more complicated.
Question: Consider a light bulb and a switch that controls it.  If a NOT gate is use and the switch is put to ‘on’ will the light be on or off?

AND Gate
The AND gate performs a logical “and” operation on two inputs, A and B:
The idea behind an AND gate is, “If A AND B are both 1, then Q should be 1.

A B Q
0 0 0
0 1 0
1 0 0
1 1 1

Question: If two switches are used to control a light bulb and they go through an AND gate. Will the light be on or off if only one switch is flipped on?

 

OR Gate
The next gate is an OR gate. Its basic idea is, “If A is 1 OR B is 1 (or both are 1), then Q is 1.”

Fill in column Q for this truth table:

A B Q
0 0  
0 1  
1 0  
1 1  

For column Q your answer should be 0111. Did you get it right?

Question: If two switches are used to control a light bulb and they go through an OR gate. Will the light be on or off if only one switch is flipped on?

“Hybrid” Gates
We just look at three basic gates (that’s one way to count them). It is quite common to recognize two others as well: the NAND and the NOR gate. These two gates are simply combinations of an AND or an OR gate with a NOT gate. If you include these two gates, then the count rises to five. Here’s the basic operation of NAND and NOR gates — you can see they are simply inversions of AND and OR gates:

Finish filling in the truth tables for the NOR gate and the NAND gate.

NOR Gate                                                                  

A B Q
0 0  
0 1  
1 0  
1 1  

NAND Gate

A B Q
0    
0    
1    
1    

Google the truth table for NOR gate and truth table for NAND gate and check that you got the write answers.

The final two gates that are sometimes added to the list are the XOR and XNOR gates, also known as “exclusive or” and “exclusive nor” gates, respectively. Here are their tables:

XOR Gate

A B Q
0 0 0
0 1 1
1 0 1
1 1 0

 XNOR Gate

A B Q
0 0 1
0 1 0
1 0 0
1 1 1

The idea behind an XOR gate is, “If either A OR B is 1, but NOT both, Q is 1.” The reason why XOR might not be included in a list of gates is because you can implement it easily using the original three gates listed.

If you try all four different patterns for A and B and trace them through the circuit, you will find that Q behaves like an XOR gate. Since there is a well-understood symbol for XOR gates, it is generally easier to think of XOR as a “standard gate” and use it in the same way as AND and OR in circuit diagrams.

If you want to become the next Steve Wozniak keep reading the article on Adders, Flip Flops (memory), …. Keep reading through the slides:  http://computer.howstuffworks.com/boolean.htm