# A-level Computing 2009/AQA/Computer Components, The Stored Program Concept and the Internet/Fundamental Hardware Elements of Computers/Logic Gates

In 1854, British mathematician George Boole developed Boolean algebra. Instead of using 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 substantial impact on computer science, with low-level hardware heavily relying on it. Boolean algebra equations are often expressed using truth tables, which are tables that show every possible output of an equation.
| $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 small pieces of hardware that perform operations on boolean inputs. They are one of the fundamental building blocks of computers, with computers typically requiring billions of them. A logic gate will usually have only one or two inputs, which will be referred to as A and B in the passages below. There are six main types of logic gates:
* NOT
* AND
* OR
* XOR
* NAND
* NOR

## NOT

The NOT gate, also known as the disjunction operation, will output the opposite of its input. (i.e. if the input is 1, the NOT gate will output 0; if the input is 0, the NOT gate will output 1)
In Boolean algebra, the NOT operation is expressed by placing a bar on top of a truth value(${\overline {A}}$) or multiple truth values (${\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 summarize, here is the truth table showing the relationship between A and ${\overline {A}}$.
| A | ${\overline {A}}$ |
| 0 | 1 |
| 1 | 0 |

## AND (.)

The AND gate, also known as the conjunction operation, will output true if all of its inputs are true; otherwise, it will output false.
In Boolean algebra, the AND operation is expressed by placing a bullet point between two (${A}.{B}$) or more (${A}.{B}.C$) truth 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.
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 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.
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$)

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 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 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:
NameNANDNORANDNOTORXOR
Gate
Symbol
Truth Table
Answer:
NameNANDNORANDNOTORXOR
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 :