Subtopic Notes
15.2 Boolean Algebra and Logic Circuits
15. Hardware and Virtual Machines
NOT Gate
| Name | Symbol | Boolean Symbol |
|---|---|---|
| NOT |  |  |
Truth Table
| A | Out |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND Gate
| Name | Symbol | Boolean Symbol |
|---|---|---|
| AND |  |  |
Truth Table
| A | B | Out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR Gate
| Name | Symbol | Boolean Symbol |
|---|---|---|
| OR |  |  |
Truth Table
| A | B | Out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NAND Gate
| Name | Symbol | Boolean Symbol |
|---|---|---|
| NAND |  |  |
Truth Table
| A | B | Out |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR Gate
| Name | Symbol | Boolean Symbol |
|---|---|---|
| NOR |  |  |
Truth Table
| A | B | Out |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XOR / EOR Gate
| Name | Symbol | Boolean Symbol |
|---|---|---|
| XOR / EOR |  |  |
Truth Table
| A | B | Out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Half Adder
- Logic Circuit that adds two single binary digits
- Outputs the result along with carry
- Typically represented using XOR gate (sum) and AND gate (carry)
| A | B | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Full Adder
- Logic Circuit that adds three binary digits
- Three inputs including the previous carry bit.
- Typically represented with two half adder circuits and an OR gate
Flip Flop
- Basic data storage element in digital electronics
- Can store 1 bit of data (either 0 or 1) until it is told to change
SR Flip Flop/Latch
- May use NAND gates or NOR Gates
- A two-state device controlled by Set (S) and Reset (R) inputs.
- The flip-flop is a two-state device:
- Q set to 1 and Q’ set to 0
- Q set to 0 and Q’ set to 1
- Invalid State: Q and Q’ having the same value
- Limitations:
- One combination of SR Flip flop is invalid
- Inputs may not arrive at the same time
Using NAND Gate
| S | R | Q | Q’ | State |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | Invalid |
| 0 | 1 | 1 | 0 | Sets Q to 1 |
| 1 | 0 | 0 | 1 | Resets Q to 0 |
| 1 | 1 | No Change |
Using NOR Gate
| S | R | Q | Q’ | State |
|---|---|---|---|---|
| 0 | 0 | No Change | ||
| 0 | 1 | 0 | 1 | Sets Q’ to 1 |
| 1 | 0 | 1 | 0 | Resets Q’ to 0 |
| 1 | 1 | 0 | 0 | Invalid |
JK Flip Flop
| J | K | Qn | Qn+1 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
- Has no invalid state, more stable
- Uses a clock pulse to synchronize and ensure proper function
- Only active when clock is high
Boolean Algebra
You don't need to remember the name, just use the formulas to simplify expression
| Name | AND form | OR form |
|---|---|---|
| Identity law | 1A = A | 0 + A = A |
| Null law | 0A = 0 | 1 + A = 1 |
| Idempotent law | AA = A | A + A = A |
| Inverse law | AA̅ = 0 | A + A̅ = 1 |
| Commutative law | AB = BA | A + B = B + A |
| Associative law | (AB)C = A(BC) | (A + B) + C = A + (B + C) |
| Distributive law | A + BC = (A + B)(A + C) | A(B + C) = AB + AC |
| Absorption law | A(A + B) = A | A + AB = A |
| De Morgan's law |  |  |
| Misc (Derived) | A + A̅B = A + B | A(A̅ + B) = AB |
Example of Simplification
| Step | Working | Law / Reason |
|---|---|---|
| 1 | (A + A̅.B)(A + C) + (A̅ + B)(A + B̅) + A.B.C̅ | Given expression |
| 2 | (A + B)(A + C) + (A̅ + B)(A + B̅) + A.B.C̅ | Misc |
| 3 | A + B.C + (A̅ + B)(A + B̅) + A.B.C̅ | Distributive law |
| 4 | A + B.C + A̅.A + A̅.B̅ + B.A + B.B̅ + A.B.C̅ | Expanding 3rd term |
| 5 | A + B.C + 0 + A̅.B̅ + A.B + 0 + A.B.C̅ | Inverse law |
| 6 | A + B.C + A̅.B̅ + A.B + A.B.C̅ | Identity law |
| 7 | A + B.C + A̅.B̅ + A.B(1 + C̅) | Factorising |
| 8 | A + B.C + A̅.B̅ + A.B | Null law |
| 9 | A + A.B + A̅.B̅ + B.C | Rearranging |
| 10 | A + A̅.B̅ + B.C | Absorption law |
| 11 | A + B̅ + B.C | Misc |
| 12 | A + B̅ + C | Misc |
Karnaugh Map (K-map)
- A visual method to simplify Boolean expressions
- Groups adjacent 1s in the truth table
- Minimises logic expressions without heavy algebra.
- Reduces number of gates
- Sum of product: OR Gate between all the combinations that lead to 1 in the output
- Method
- Fill in the map diagram by keeping AB on one side and C or CD on the other side
- Mark a 1 for each combination of inputs where the output is 1.
- Form groups:
- Only group sizes of 1, 2, 4, 8… (powers of 2)
- Groups must be rectangular & wrap around edges
- Larger groups = simpler expression
- Each 1 must be in at least one group
- Take the common values from the groups and use or gates between them
