10 Boolean Algebra

From binary logic to digital circuits

We’ve seen how computers represent information.

• In particular how they perform arithmetical operations upon numbers.
We’ve also seen how the CPU supports a small set of arithmetical and logical
operations in its machine language.
• Small, yet sufficient to allow universal computation.
A B Q
0 0 1
0 1 1
In these lectures we’ll see how binary logic works. 1 0 1
1 1 0
Later on we’ll see how it is used to design and implement digital circuits which
can perform such arithmetical and logical operations.
• Including how simple circuits combine to perform more complex operations.

2
10 Boolean Algebra
• History
• Operators and Truth Tables
• Identities
• Standardized Form
A potted history

1854: George Boole’s The Laws of Thought is published.

• Thus creating Symbolic Logic, or Boolean Algebra.

George Boole
1938: John Atanasoff determines 4 principles for his ABC digital computer: 1815−1864

1. It will use electricity instead of mechanical movements.

2. It will use base-2 (binary) because switches are either on or off.
3. It will use capacitors for memory because they store charge with a
regenerative process, avoiding power leakage.
4. Computations will be performed by direct logical action - which Claude
Shannon proved is essentially Boolean Algebra - rather than by John Atanasoff
1903-1995
enumeration (counting) as had been done before.

4
10 Boolean Algebra
• History
• Operators and Truth Tables
• Identities
• Standardized Form
Boolean algebra

A system for the manipulation of variables, where the variables can have
one of two values:
• True or False.
• Which correspond to on or off, 1 or 0.

Boolean Expressions are created by applying Boolean Operators to one

or more variables:
• Such as AND, OR and NOT.
• And also NAND, NOR and XOR.

6
Operators and their truth tables

Each operator can be described using its truth table.

A truth table is a systematic way to define a Boolean function:
• One row for each possible set of arguments.
• Each row gives the function value for the specified arguments.
• N inputs: 2N rows needed.

x y x.y x y x+y x x'

0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1 NOT
1 1 1 1 1 1
AND OR

7
Operators and their truth tables

Each operator can be described using its truth table.

x y (x.y)' x y (x+y)' x y x⊕y

0 0 1 0 0 1 0 0 0
0 1 1 0 1 0 0 1 1
1 0 1 1 0 0 1 0 1
1 1 0 1 1 0 1 1 0
NAND NOR XOR

8
Boolean functions

A Boolean Function involves:

• One or more input variables.
• One or more operators.
• A result from the set {0,1}.

Examples:
• F(x, y) = xy
• F(x, y) = x + y
• F(x, y, z) = y + x'.z

If x = 0, y =1 and z = 1 then we can easily evaluate the first two functions:

• x.y = (1 AND 0) = 0
• x + y = (1 OR 0) = 1

But in what order do we perform the operations to find the answer to the third function?
9
Operators: order of precedence

Priority highest to lowest:

• NOT then AND then OR

Example: Inputs Intermediate Output

• Suppose F(x,y,z) = y + x'.z x y z x' x'.z F=y+x'.z

• Evaluate F when x = 0, y = 1 and z = 1.

0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 1 0 1
Easiest to evaluate in stages: 0 1 1 1 1 1
• x' = NOT(0) = 1 1 0 0 0 0 0
• x'.z = (1 AND 1) = 1 1 0 1 0 0 0
• y + x'.z = (1 OR 1) = 1 1 1 0 0 0 1
1 1 1 0 0 1
(Can you spot the easy way to generate the
A truth table lets us do this for all possible values.
set of truth table input values for x, y and z?)
10
10 Boolean Algebra
• History
• Operators and Truth Tables
• Identities
• Standardized Form
Boolean identities

Boolean functions can quickly become complicated.

Yet the simpler we can make the function, the smaller circuit we’ll need to build for it.
• Cheaper, more economical and faster.

So there’s an incentive to reduce boolean functions to their simplest form.

Sometimes this can be tricky, so in practice automated techniques such as Karnaugh
Maps are used.

Here, we’ll use the basic boolean identities to perform the task.

12
Boolean identities

Name AND Form OR Form

Identity Law 1.x = x 0 + x = x
Null (or Dominance) Law 0.x = 0 1 + x = 1
Idempotent Law x.x = x x + x = x
Inverse Law x.x' = 0 x + x' = 1
Commutative Law x.y = y.x x + y = y + x
Associative Law (x.y).z = x.(y.z) (x+y)+z = x+(y+z)
Distributive Law x+y.z = (x+y).(x+z) x.(y+z) = x.y + x.z
Absorption Law x.(x+y) = x x + x.y = x
DeMorgan’s Law (x.y)' = x' + y' (x+y)' = x'.y'
Double Complement Law (x')' = x

13
Truth table proofs

Truth tables are convenient for establishing identities in Boolean logic.

• One row for each possibility.
• Identity established if columns match.

Proofs of DeMorgan's laws

NOR NOR
x y xy ( x y ) ' x y x' y' x' + y' x y x + y (x + y)' x y x' y' x'y'

0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 1 1
0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 0
1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 0
1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0

(xy)' = (x' + y' ) (x + y)' = x'y'

Important: note that x'.y' ≠ (x.y)' This technique extends for 3 or more variables.
14
Using identities to simplify functions

Simplify F(x, y, z) = x'.y.z + x'.y.z' + x.z

= x'.y.z + x'.y.z' + x.z

= x'.y.(z + z') + x.z distributive
= x'.y.(1) + x.z inverse
= x'.y + x.z identity

15
Using identities to simplify functions

Simplify F(x, y) = y + (x.y)'

= y + (x.y)'
= y + x' + y' DeMorgan’s
= y + y' + x' commutative
= (y + y') + x' associative
= 1 + x' inverse
= 1 null

16
Using identities to simplify functions

Prove (x + y).(x' + y) = y

(x + y).(x' + y)
= x.x' + x.y + y.x' + y.y distributive
= 0 + x.y + y.x' + y.y inverse
= 0 + x.y + y.x' + y idempotent
= x.y + y.x' + y identity
= y.(x + x') + y distributive (& commutative)
= y.(1) + y inverse
= y + y identity
= y idempotent ✓

17
Universality of NAND and NOR

Recall DeMorgan's Law:

(x.y)' = x' + y'
(x+y)' = x'.y'

This is one of the most useful identities in practical terms.

Q. Why?
A. It tells us how to convert AND and OR operations into NAND and NOR operations.

Moreover we can determine that all other operations can be performed

using just NAND or just NOR.
• Which means that NAND and NOR are universal.
And that makes digital circuits much easier to produce.

18
NAND alone

Examples:
Show that OR, NOT and AND can be performed using NAND operations only: NAND(a,b) = (a.b)'

OR:
x+y = x.x + y.y idempotent
= ((x.x)')' + ((y.y)')' double complement
= ((x.x)'.(y.y)')' DeMorgan (a.b)' = a' + b'
= NAND(NAND(x,x),NAND(y,y))
✓

NOT:
x' = (x)' simple re-write
= (x.x)' idempotent
= NAND(x,x)
✓
19
NAND alone

Examples:
Show that OR, NOT and AND can be performed using NAND operations only: NAND(a,b) = (a.b)'

AND:
x.y = ((x.y)')' double complement
= ((x.y)'.(x.y)')' idempotent a = a.a
= NAND(NAND(x,y),NAND(x,y))
✓

20
10 Boolean Algebra
• History
• Operators and Truth Tables
• Identities
• Standardized Form
Standardized form

We've seen that the same boolean function can be written in many different ways.
To avoid confusion designers specify functions in a standardized (or canonical) form.
The two most common forms are:

Sum of Products:
• ANDed variables are ORed together.
• Such as F(x, y, z) = x.y + x.z + y.z

Product of Sums:
• ORed variables are ANDed together
• Such as F(x, y, z) = (x + y).(x + z).(y + z)

22
Universality of AND, OR and NOT

The easiest version to determine because we can just use a truth table:
• Find and list the values of x, y and z which make the function true.
• Then simply OR each expression in the list together.

Example: Majority Polling Function

x y z MAJ x'yz xy'z xyz' xyz

0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
So the function is:
0 1 1 1 1 0 0 0 x'yz
F = x'yz + xy'z + xyz' + xyz
1 0 0 0 0 0 0 0
1 0 1 1 0 1 0 0 xy'z
1 1 0 1 0 0 1 0 xyz'
1 1 1 1 0 0 0 1 xyz
23
To conclude

We’ve learned about Boolean variables, operators, expressions and functions.

We’ve seen how to form truth tables to help us to determine the outcome of functions.
• Don’t underestimate the value of using these!

We’ve seen how to apply the identities to help us to simplify some functions.

And to transform others so that they can be expressed just using NAND or NOR.
• Making good use of DeMorgan’s Law.

We’ve seen how to represent functions in a standardized form.

24
Reading and References

Required Reading
• Course textbook chapter 7.1, 7.2
Suggested learning activities:
• In these slides we simplified functions by hand.
• But the process can be automated using Karnaugh Maps.
• Which is helpful in circuit design,
• and you see an explanation of the process here.

25