A-Level Computer Science
Fundamentals of Computer Systems
Boolean Logic
NOT gate
A NOT gate inverses the input.
Gate Symbol |
|
A | Q |
1 | 0 |
0 | 1 |
Boolean Algebra Symbol |
|
_
A
AND gate
An AND gate produces an output only if both inputs are true.
Gate Symbol |
|
A | B | Q |
0 | 0 | 0 |
1 | 0 | 0 |
0 | 1 | 0 |
1 | 1 | 1 |
Boolean Algebra Symbol |
A . B |
OR gate
An OR gate produces an output if one or both inputs are true.
Gate Symbol |
|
A | B | Q |
0 | 0 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 1 |
Boolean Algebra Symbol |
A + B |
XOR gate
An XOR gate produces an output if either input is true but not both.
Gate Symbol |
|
A | B | Q |
0 | 0 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 0 |
Boolean Algebra Symbol |
A B |
NAND gate
An NAND gate produces an output if any of the inputs are false (inverse of AND)
Gate Symbol |
|
A | B | Q |
0 | 0 | 1 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 0 |
Boolean Algebra Symbol |
A . B |
_
NOR gate
An NOR gate produces an output only if both inputs are false (inverse of OR gate)
Gate Symbol |
|
A | B | Q |
0 | 0 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
1 | 1 | 0 |
Boolean Algebra Symbol |
A + B |
_
Circuit diagrams
You also need to be comfortable with creating a circuit diagram from a boolean algebra equation.
Boolean Algebra Equation |
A + (B . C) |
Example 1
_
Circuit Diagram |
|
A -
B -
C -
- Q
Circuit diagrams
Now let's try a slightly more complicated one.
Boolean Algebra Equation |
(A + (B + C)) |
Example 2
_
Circuit Diagram |
|
A -
B -
C -
- Q
Truth tables
Truth tables are a way of proving how a logic circuit will work. You need to be able to create one from either a circuit diagram or algebraic equation.
Boolean Algebra Equation |
A + (B . C) |
A | B | C | | | Q |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
Example 1
_
Truth tables
Step 1 - Fill in all the possible combinations for the variables in the equation. My advice would be to count up in binary to ensure none are missed.
Boolean Algebra Equation |
A + (B . C) |
A | B | C | | | Q |
0 | 0 | 0 | | | |
0 | 0 | 1 | | | |
0 | 1 | 0 | | | |
0 | 1 | 1 | | | |
1 | 0 | 0 | | | |
1 | 0 | 1 | | | |
1 | 1 | 0 | | | |
1 | 1 | 1 | | | |
Example 1
_
Truth tables
Boolean Algebra Equation |
A + (B . C) |
A | B | C | A’ | B.C | Q |
0 | 0 | 0 | 1 | 0 | |
0 | 0 | 1 | 1 | 0 | |
0 | 1 | 0 | 1 | 0 | |
0 | 1 | 1 | 1 | 1 | |
1 | 0 | 0 | 0 | 0 | |
1 | 0 | 1 | 0 | 0 | |
1 | 1 | 0 | 0 | 0 | |
1 | 1 | 1 | 0 | 1 | |
Example 1
_
Step 2 - I would then suggest completing a column for all but one of the operators. This will help ensure you get the correct answer every time.
Truth tables
Boolean Algebra Equation |
A + (B . C) |
A | B | C | A’ | B.C | Q |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 1 | 1 |
Example 1
_
Step 3 - Now you can fill in the Q column by simply doing an OR comparison on your other two new columns.
Truth tables
Logic Circuit |
|
A | B | C | A.B | C’ | (A.B)+C’ | Y |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
Example 2
You will also need to potentially make a truth table from a logic circuit. Lets do one of those as an example.
Truth tables
Logic Circuit |
|
A | B | C | A.B | C’ | (A.B)+C’ | Y |
0 | 0 | 0 | | | | |
0 | 0 | 1 | | | | |
0 | 1 | 0 | | | | |
0 | 1 | 1 | | | | |
1 | 0 | 0 | | | | |
1 | 0 | 1 | | | | |
1 | 1 | 0 | | | | |
1 | 1 | 1 | | | | |
Example 2
Step 1 - Fill in all the possible combinations for the variables in the equation. My advice would be to count up in binary to ensure none are missed.
Truth tables
Logic Circuit |
|
A | B | C | A.B | C’ | (A.B)+C’ | Y |
0 | 0 | 0 | 0 | 1 | 1 | |
0 | 0 | 1 | 0 | 0 | 0 | |
0 | 1 | 0 | 0 | 1 | 1 | |
0 | 1 | 1 | 0 | 0 | 0 | |
1 | 0 | 0 | 0 | 1 | 1 | |
1 | 0 | 1 | 0 | 0 | 0 | |
1 | 1 | 0 | 1 | 1 | 1 | |
1 | 1 | 1 | 1 | 0 | 1 | |
Example 2
Step 2 - I would then suggest completing a column for all but one of the logic gates in the circuit. This will help ensure you get the correct answer every time.
Truth tables
Logic Circuit |
|
A | B | C | A.B | C’ | (A.B)+C’ | Y |
0 | 0 | 0 | 0 | 1 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 1 | 1 | 0 |
0 | 1 | 1 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 | 0 | 1 | 0 |
Example 2
Step 3 - Now you can fill in the Y column by simply doing a NOT on the previous column.
Boolean expressions
Given either a truth table or a circuit diagram you will need to be able to represent the algebraic form.
Circuit Diagram |
|
Boolean Algebra Expression |
|
Q
Boolean expressions
Given either a truth table or a circuit diagram you will need to be able to represent the algebraic form.
Circuit Diagram |
|
Boolean Algebra Expression |
|
Q
Boolean simplification
Although you will be learning De Morgan’s law, that on his own is often not enough! You need to be able to simplify expressions and understand why.
For example
A.1 → A
Boolean simplification
Although you will be learning De Mrogan’s law, that on his own is often not enough! You need to be able to simplify expressions and understand why.
For example
A.1 → A
If we visualise this as a logic gate it can help understand the simplification. There is no way to obtain a 1 output without A being 1. Therefore the output is always A.
A
1
A
Boolean simplification
Other simplification rules:
A . B = B . A A + B = B + A A . 0 = 0 A + 1 = 1 A + 0 = A A . 1 = A A . A = A | A + A = A A . A’ = 0
A + A = 1
A = A
( A . B ) . C = A . ( B . C )
( A + B ) + C = A + ( B + C )
A . ( B + C ) = A . B + A . C |
De Morgan's Laws
This is Augustus De Morgan!
I determined that any Boolean Function can be created only using NOR and NAND gates.
NOR
NAND
We call these the Universal Gates
De Morgan's Laws
By following the three rules to De Morgan’s Law you can
(in theory)
simplify any Boolean Expression.
De Morgan's Laws
Let's see this in action!
We’re going to apply De Morgan’s Law to this expression
A.B
De Morgan's Laws
Step 1.
The logical connective must be changed.
A.B | A+B |
Here AND becomes OR
De Morgan's Laws
Step 2.
The logical state of each variable must be changed.
A.B | A+B | A+B | |
NOT is added to each variable.
De Morgan's Laws
Step 3.
The logical state of the complete expression must be changed.
A.B | A+B | A+B | A+B |
NOT is added to the whole thing
De Morgan's Laws
We could therefore say that:
A | B | A.B |
0 | 0 | 0 |
1 | 0 | 0 |
0 | 1 | 0 |
1 | 1 | 1 |
A.B | A+B |
A | A | B | B | A+B | A+B |
0 | 1 | 1 | 0 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 1 |
De Morgan's Laws
Worked Exam Question
(3)
De Morgan's Laws
Worked Exam Question
A . B
(3)
We use De Morgan’s Law to simplify part of the whole expression
A + B
Becomes
A . B
The double NOTs cancel each other
De Morgan's Laws
Worked Exam Question
(3)
A . B + B . A
We’re now left with..
De Morgan's Laws
Worked Exam Question
(3)
A . B + B . A
We’re now left with..
A . B . A
B + B simplifies to just B
De Morgan's Laws
Worked Exam Question
(3)
A . B + B . A
We’re now left with..
B . (A + A)
If we put the brackets back in
A . A simplifies to 1 which means we are left with
Which simplifies down to
B
B.1
De Morgan's Laws
Don’t believe it? Let’s prove our working.
A | B | A | B | B . A | A + B | Q |
1 | 1 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 1 |
Remember the order of operations is NOT then AND then OR.
De Morgan's Laws
Don’t believe it? Let’s prove our working.
A | B | A | B | B . A | A + B | Q |
1 | 1 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 1 |
Remember the order of operations is NOT then AND then OR.
Notice how the output is the same as B.
We can therefore simplify this expression down to just the same as B
De Morgan's Laws
Now try this more difficult exam question
De Morgan's Laws
Now try this more difficult exam question
or
You must demonstrate this method.
Order of operations
95% of the time the order in which you would simplify operators is made explicit with the use of brackets e.g.
A . (A + A) = A
However sometimes you may get a questions like this:
A . A + B . 1
From a simplification point of view its difficult to see where to start. The order to evaluate operations makes this clearer.
Order of operations
A . A + B . 1
ORDER OF OPERATIONS
A + B . 1
In this case as there are no ‘NOTs’ or parenthesis we would focus on the ANDs
A . A simplifies to A
B.1 Simplifies to B
Which leaves us with
A + B
Recognise half and full-adder circuits
Logic circuits are made up of sometimes thousands of logic gates where the output from one becomes the input to another. These are most commonly found in the ALU to perform binary addition.
Two of the more commonly known circuits are:
Half Adder
Full Adder
A2
Construct a half-adder circuit
You need to be able to construct a half-adder which is a fairly simple circuit. It is really important that you have a good understanding of what this circuit is doing.
Half Adder
A2
Edge-triggered D-type flip-flop
Before I explain this I need to explain a more basic flip-flop circuit:
This is a really basic circuit which is used in memory as it is capable of storing and retaining one bit of data. This would be an example of volatile memory as it requires power.
A2
Edge-triggered D-type flip-flop
An edge-triggered d-type flip-flop is a more complex version of a flip-flop. It has a very similar relationship to the half adder has to the full adder.
This circuit takes a normal input and a second input (clock). This means that on each pulse of the clock ths flip-flop will change state. This means that the data input coming in will be stored in the flip-flop and continue to be output until the next trigger pulse is received.
A2