Fundamental Hardware Elements of Computers: Logic Gates

In 1854 a British mathematician, George Boole, developed Boolean Algebra. Instead of an algebra that uses numbers, boolean algebra uses truth values, true(1) and false(0). By defining sentences using truth values and performing operations on these truth values you can work out the overall conclusion of complex statements. Boolean Algebra has had a massive impact on Computer Science and the language that computers understand is a language of 1s and 0s, boolean.

Examples of Boolean Algebra shown in a truth table

$x$ $y$ $x.y$ $x+y$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

$x$ ${\overline {x}}$ 0 1 1 0

Logic gates are pieces of hardware that perform operations on boolean inputs, allowing us to create complex devices out of abstract boolean algebra. Logic gates are the fundamental building blocks of hardware and processors will be made out of billions of them. A logic gate will typically have one or two inputs, in the examples here defined by A and B, There are six types of gate that you need to know:

• 
  NOT
• 
  AND
• 
  OR
• 
  XOR
• 
  NAND
• 
  NOR

NOT

A NOT gate takes only one input and gives one output

A NOT gate will always give an output opposite to what the input is e.g. 1 (not gate) 0. A NOT gate takes one boolean input and flips it. It is possible to have a double NOT. This will reverse the original NOT. The symbol would have an extra bar over it.

In Boolean Algebra we write a NOT symbol by placing a bar on top of a letter(${\overline {A}}$) or letters (${\overline {C+B}}$).

Examples of a NOT gate at work are as follows: NOT(It is not raining) = It is raining ${\overline {TRUE}}=FALSE$ ${\overline {0}}=1$

To summarise here is a truth table showing the relationship between A and ${\overline {A}}$

A	${\overline {A}}$
0	1
1	0

AND (.)

An AND gate takes two inputs and combines them to form one output

An AND gate will combine the boolean values of two inputs (you can get more than two inputs but we don't need to know about that type of gate here). If and only if both inputs are true will it output true. If any of the inputs are false it will out put false.

In Boolean Algebra we write an AND symbol by placing a bullet point between two (${A}.{B}$) or more (${A}.{B}.C$) values.

Examples of an AND gate at work are as follows: Six is bigger than four AND Cats are bigger than gerbils = TRUE $TRUE.FALSE=FALSE$ $(7<8).(2>1)=TRUE$ $(8>0).{\overline {(20=19)}}=TRUE$

An easy way to remember how an AND gate works is thinking about a circuit to turn a light bulb on. If both switches are on then the bulb will light up, if any switch is off then the bulb won't light.

a circuit diagram equivalent to an AND gate

To summarise here is a truth table showing all the different values for two inputs A and B and the result of ANDing those values together

A	B	A.B
0	0	0
0	1	0
1	0	0
1	1	1

OR (+)

An OR gate takes two inputs and combines them to form one output

An OR gate will combine the boolean values of two inputs. If one or more inputs are true then the output will be true. If both the inputs are false then the output will be false.

In Boolean Algebra we write an OR symbol by placing a plus symbol between two (${A}+{B}$) or more (${A}+{B}+C$) values.

Examples of an OR gate at work are as follows: humans have two legs OR Elephants have 8 legs = TRUE $TRUE+FALSE=TRUE$ $(9>3)+(2>1)=TRUE$ ${\overline {(20=20)}}+(5>6)=FALSE$

An easy way to remember how an OR gate works is thinking about a circuit to turn a light bulb on. If one or more switches are on then the bulb will light up, if both switch are off then the bulb won't light.

a circuit diagram equivalent to an OR gate

To summarise here is a truth table showing all the different values for two inputs A and B and the result of ORing those values together

A	B	A+B
0	0	0
0	1	1
1	0	1
1	1	1

XOR ($\oplus$)

A XOR gate takes two inputs and combines them to form one output

An exclusive- OR, XOR, gate will combine the boolean values of two inputs. If exactly one input is true then the output will be true. If both the inputs are false or both the inputs are true then the output will be false.

In Boolean Algebra we write an XOR symbol by placing a plus symbol surrounded by a circle between two (${A}\oplus {B}$) or more (${A}\oplus {B}\oplus {C}$) values.

Examples of an XOR gate at work are as follows: it is raining XOR it is not raining = TRUE $TRUE\oplus TRUE=FALSE$ $(9<3)\oplus (2<1)=FALSE$ ${\overline {(20=20)}}\oplus (8>2)=TRUE$

To summarise here is a truth table showing all the different values for two inputs A and B and the result of XORing those values together

A	B	$~A\oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

NAND

A NAND gate takes two inputs and combines them to form one output

A NAND gate will combine the boolean values of two inputs, AND them together, and NOT the result. If one or less input is true then the output will be true. If both the inputs are true then the output will be false. To draw a NAND gate you draw an AND gate and add a circle to the front, as you can see above.

In Boolean Algebra we write an NAND symbol by taking an AND equation and NOTing the result (${\overline {{A}.{B}}}$).

Examples of an NAND gate at work are as follows: (A=A) NAND (A<>B) = TRUE ${\overline {TRUE.TRUE}}=FALSE$ ${\overline {(9<3).(2<1)}}=TRUE$ ${\overline {(20>20).(8>2)}}=TRUE$

To summarise here is a truth table showing all the different values for two inputs A and B and the result of NANDing those values together

A	B	$A.B$	${\overline {A.B}}$
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

NOR

A NOR gate takes two inputs and combines them to form one output

A NOR gate will combine the boolean values of two inputs, OR them together, and NOT the result. If no input is true then the output will be true. If either or both inputs are true then the result will be false. To draw a NOR gate you draw an OR gate and add a circle to the front, as you can see above.

In Boolean Algebra we write an NOR symbol by taking an OR equation and NOTing the result (${\overline {{A}+{B}}}$).

Examples of an NOR gate at work are as follows: (A=A) NOR (A<>B) = FALSE ${\overline {FALSE+TRUE}}=FALSE$ ${\overline {(9<3)+(2<1)}}=TRUE$ ${\overline {(20>20)+(8>2)}}=FALSE$

A	B	$A+B$	${\overline {A+B}}$
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

Exercise: Logic Gates Give the symbol and gate diagram for an OR statement Answer: + Give the symbol and gate diagram for an AND statement Answer: . Give the symbol and gate diagram for a XOR statement Answer: $\oplus$ Give answers to the following equations: TRUE AND TRUE Answer: TRUE TRUE + FALSE Answer: TRUE TRUE + TRUE Answer: TRUE TRUE $\oplus$ TRUE Answer: FALSE NOT(TRUE) . TRUE Answer: FALSE ${\overline {\overline {TRUE}}}+FALSE$ Answer: TRUE Draw a NAND gate and truth table Answer: A B $A.B$ ${\overline {A.B}}$ 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 Complete the following table: Name NAND NOR AND NOT OR XOR Gate Symbol Truth Table Answer: Name NAND NOR AND NOT OR XOR Gate Symbol ${\overline {A.B}}$ ${\overline {A+B}}$ $.$ ${\overline {A}}$ $+$ $\oplus$ Truth Table A B $A.B$ ${\overline {A.B}}$ 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 A B $A+B$ ${\overline {A+B}}$ 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 A B A.B 0 0 0 0 1 0 1 0 0 1 1 1 A ${\overline {A}}$ 0 1 1 0 A B A+B 0 0 0 0 1 1 1 0 1 1 1 1 A B $~A\oplus B$ 0 0 0 0 1 1 1 0 1 1 1 0