15. Hardware
1. Boolean Algebra
Multi-input logic gates - logic gates can have more than two inputs e.g.
is the same as
Boolean algebra notation:
● AND (•) e.g. P = A • B
● OR (+) e.g. P = A + B
● NOT ( ) e.g. P = A
● XOR (⊕) e.g. P = A ⊕ B
De Morgan’s laws:
● His laws state any Boolean function can be converted to one using only NAND/NOR functions -
using one type of gate reduces manufacturing costs, so has huge commercial significance
● A + B = A • B
● A • B = A + B
More general rules: ● Commutative rule
● X • 0 = 0 Null law ○ X • Y = Y • X
● X • 1 = X Identity law ○ X + Y = Y + X
● X • X = X Idempotent law ● Associative rule
● X • X = 0 Inverse law ○ X • (Y • Z) = (X • Y) • Z
● X + 0 = X Identity law ○ X + (Y + Z) = (X + Y) + Z
● X + 1 = 1 Null law ● Distributive rule
● X + X = X Idempotent law ○ X • (Y + Z) = X • Y + X • Z
● X + X = 1 Inverse law ○ (X+ Y) (W + Z) = X • W + X • Z +
● X = X Double negative law Y • W + Y • Z
● XY + X = X+Y Redundancy law ● Absorption rule
○ X + (X • Y) = X
○ X • (X + Y) = X
Order of precedence:
1. Brackets
2. NOT
3. XOR
4. AND
5. OR
Cancelling NOTs - two NOTs only cancel each other out if they are over exactly the same part of an
expression e.g.𝐴 + 𝐵= 𝐴 + 𝐵but𝐴 + 𝐵. 𝐶≠ 𝐴 + 𝐵. 𝐶because the NOTs cannot be cancelled out
, 2. Karnaugh Maps
arnaugh maps (K-maps) are a method of simplifying Boolean expressions - it is important to simplify
K
so they use the least expressions/gates/electronic components to:
● reduce the physical size of the circuit
● reduce the cost of manufacturing the circuit
● reduce the power consumption of the circuit
● execute instructions as quickly as possible
Modelling the expression in the map:
● Start by putting the variables and all their possible values along the top and side of the table
○ Note: for the headings Gray codes must be used (only one digit is allowed to change), not
just counting up in binary
● Then split the expression up by the ORs, and fill 1s and 0s in for each set of inputs
Simplifying the expression:
● Draw boxes around the 1s, using the following rules:
○ Boxes must be rectangles or squares
○ Boxes cannot go diagonally
○ Boxes can only contain 1s (no 0s)
○ Boxes must be as big as possible
○ Boxes must be 2n cells big
○ Boxes can overlap
○ Aim to have the least number of boxes across the table
○ Boxes can wrap around the table
● Take each box in any order
● Take each variable in any order
● If the value (1 or 0) of the variable in the heading remains the same
throughout the box, keep the variable - if it changes, discard the
variable - this will create the simplified expression for that box
○ Note: if the variable remains the same as a 0, take NOT the variable e.g. if A remains a 0 in
all the headings in the box, take NOT A for the expression
● Repeat this for each of the boxes
● Combine the expressions of each of the boxes using OR statements
Helpful to understand -https://www.youtube.com/watch?v=4q6Zwf4tK34
1. Boolean Algebra
Multi-input logic gates - logic gates can have more than two inputs e.g.
is the same as
Boolean algebra notation:
● AND (•) e.g. P = A • B
● OR (+) e.g. P = A + B
● NOT ( ) e.g. P = A
● XOR (⊕) e.g. P = A ⊕ B
De Morgan’s laws:
● His laws state any Boolean function can be converted to one using only NAND/NOR functions -
using one type of gate reduces manufacturing costs, so has huge commercial significance
● A + B = A • B
● A • B = A + B
More general rules: ● Commutative rule
● X • 0 = 0 Null law ○ X • Y = Y • X
● X • 1 = X Identity law ○ X + Y = Y + X
● X • X = X Idempotent law ● Associative rule
● X • X = 0 Inverse law ○ X • (Y • Z) = (X • Y) • Z
● X + 0 = X Identity law ○ X + (Y + Z) = (X + Y) + Z
● X + 1 = 1 Null law ● Distributive rule
● X + X = X Idempotent law ○ X • (Y + Z) = X • Y + X • Z
● X + X = 1 Inverse law ○ (X+ Y) (W + Z) = X • W + X • Z +
● X = X Double negative law Y • W + Y • Z
● XY + X = X+Y Redundancy law ● Absorption rule
○ X + (X • Y) = X
○ X • (X + Y) = X
Order of precedence:
1. Brackets
2. NOT
3. XOR
4. AND
5. OR
Cancelling NOTs - two NOTs only cancel each other out if they are over exactly the same part of an
expression e.g.𝐴 + 𝐵= 𝐴 + 𝐵but𝐴 + 𝐵. 𝐶≠ 𝐴 + 𝐵. 𝐶because the NOTs cannot be cancelled out
, 2. Karnaugh Maps
arnaugh maps (K-maps) are a method of simplifying Boolean expressions - it is important to simplify
K
so they use the least expressions/gates/electronic components to:
● reduce the physical size of the circuit
● reduce the cost of manufacturing the circuit
● reduce the power consumption of the circuit
● execute instructions as quickly as possible
Modelling the expression in the map:
● Start by putting the variables and all their possible values along the top and side of the table
○ Note: for the headings Gray codes must be used (only one digit is allowed to change), not
just counting up in binary
● Then split the expression up by the ORs, and fill 1s and 0s in for each set of inputs
Simplifying the expression:
● Draw boxes around the 1s, using the following rules:
○ Boxes must be rectangles or squares
○ Boxes cannot go diagonally
○ Boxes can only contain 1s (no 0s)
○ Boxes must be as big as possible
○ Boxes must be 2n cells big
○ Boxes can overlap
○ Aim to have the least number of boxes across the table
○ Boxes can wrap around the table
● Take each box in any order
● Take each variable in any order
● If the value (1 or 0) of the variable in the heading remains the same
throughout the box, keep the variable - if it changes, discard the
variable - this will create the simplified expression for that box
○ Note: if the variable remains the same as a 0, take NOT the variable e.g. if A remains a 0 in
all the headings in the box, take NOT A for the expression
● Repeat this for each of the boxes
● Combine the expressions of each of the boxes using OR statements
Helpful to understand -https://www.youtube.com/watch?v=4q6Zwf4tK34
