Boolean Algebra and Logic Gates

Basic Engineering

Boolean Algebra and Logic Gates
F Hamer, M Lavelle & D McMullan
The aim of this document is to provide a short, self assessment programme for students who wish to understand the basic techniques of logic gates.

c 2005 Email: chamer, mlavelle, [email protected]

Last Revision Date: August 31, 2006

Version 1.0

Table of Contents
1. Logic Gates (Introduction) 2. Truth Tables 3. Basic Rules of Boolean Algebra 4. Boolean Algebra 5. Final Quiz
Solutions to Exercises Solutions to Quizzes
The full range of these packages and some instructions, should they be required, can be obtained from our web page Mathematics Support Materials.

Section 1: Logic Gates (Introduction)

3

1. Logic Gates (Introduction)

The package Truth Tables and Boolean Algebra set out the basic principles of logic. Any Boolean algebra operation can be associated with an electronic circuit in which the inputs and outputs represent the statements of Boolean algebra. Although these circuits may be complex, they may all be constructed from three basic devices. These are the AND gate, the OR gate and the NOT gate.

x

x·y x

y

y

AND gate

OR gate

x+y x

x

NOT gate

In the case of logic gates, a different notation is used:
x ∧ y, the logical AND operation, is replaced by x · y, or xy. x ∨ y, the logical OR operation, is replaced by x + y. ¬x, the logical NEGATION operation, is replaced by x or x. The truth value TRUE is written as 1 (and corresponds to a high voltage), and FALSE is written as 0 (low voltage).

Section 2: Truth Tables
2. Truth Tables
x x·y y

x y x+y
00 0 01 1 10 1 11 1
Summary of OR gate

x

x

4
x y x·y 00 0 01 0 10 0 11 1 Summary of AND gate
x y x+y
xx 01 10 Summary of NOT gate

Section 3: Basic Rules of Boolean Algebra

5

3. Basic Rules of Boolean Algebra

The basic rules for simplifying and combining logic gates are called

Boolean algebra in honour of George Boole (1815 – 1864) who was a

self-educated English mathematician who developed many of the key

ideas. The following set of exercises will allow you to rediscover the

basic rules:

Example 1

x

1

Consider the AND gate where one of the inputs is 1. By using the truth table, investigate the possible outputs and hence simplify the expression x · 1.
Solution From the truth table for AND, we see that if x is 1 then 1 · 1 = 1, while if x is 0 then 0 · 1 = 0. This can be summarised in the rule that x · 1 = x, i.e.,
x x
1

Section 3: Basic Rules of Boolean Algebra

6

Example 2
x 0

Consider the AND gate where one of the inputs is 0. By using the truth table, investigate the possible outputs and hence simplify the expression x · 0.
Solution From the truth table for AND, we see that if x is 1 then 1 · 0 = 0, while if x is 0 then 0 · 0 = 0. This can be summarised in the rule that x · 0 = 0
x 0
0

Section 3: Basic Rules of Boolean Algebra

7

Exercise 1. (Click on the green letters for the solutions.) the rules for simplifying the logical expressions
x (a) x + 0 which corresponds to the logic gate
0

Obtain

x (b) x + 1 which corresponds to the logic gate
1

Exercise 2. (Click on the green letters for the solutions.) the rules for simplifying the logical expressions:
x (a) x + x which corresponds to the logic gate

Obtain

x (b) x · x which corresponds to the logic gate

Section 3: Basic Rules of Boolean Algebra

8

Exercise 3. (Click on the green letters for the solutions.) the rules for simplifying the logical expressions:
x (a) x + x which corresponds to the logic gate

Obtain

x (b) x · x which corresponds to the logic gate

Quiz Simplify the logical expression (x ) represented by the following circuit diagram.
x

(a) x (b) x

(c) 1 (d) 0

Section 3: Basic Rules of Boolean Algebra

9

Exercise 4. (Click on the green letters for the solutions.) Investigate the relationship between the following circuits. Summarise your conclusions using Boolean expressions for the circuits.

x

x

(a) y y

x

x

(b) y y

The important relations developed in the above exercise are called De Morgan’s theorems and are widely used in simplifying circuits. These correspond to rules (8a) and (8b) in the table of Boolean identities on the next page.

Section 4: Boolean Algebra

10

4. Boolean Algebra

(1a)

x·y = y·x

(1b)

x+y = y+x

(2a) x · (y · z) = (x · y) · z

(2b) x + (y + z) = (x + y) + z

(3a) x · (y + z) = (x · y) + (x · z)

(3b) x + (y · z) = (x + y) · (x + z)

(4a)

x·x = x

(4b)

x+x = x

(5a) x · (x + y) = x

(5b) x + (x · y) = x

(6a)

x·x = 0

(6b)

x+x = 1

(7)

(x ) = x

(8a)

(x · y) = x + y

(8b) (x + y) = x · y