PowerPoint Presentation
TU856-1 & TU858-1 Computer Architecture and Technology
Module Code: CMPU 1006
FROM BOOLEAN ALGEBRA TO LOGIC GATES
Presenter: Dr Art Sloan
Semester 1, Week 5
1
Presentation Outline
This presentation links the ideas of binary representation with the functionality of logic gates through the mathematical view of Boolean algebra and truth tables .
It describes the structure of logic gates and mentions their use in digital circuits and CMOS.
There are some example variations on the basic AND and OR gates, showing how they can be engineered for various numerical outcomes.
2
Presentation Content including
The Algebra of Logic
George Boole
Using Boolean Algebra with Binary
Boolean Arithmetic
The Principle of Logic Gates
Gate Representation (AND, OR, NOT)
Inside Logic Gates
3
Logic Gates for Data Movement
Truth Tables
De Morgans Theorem
Logic Gates on CMOS
NOR Gates as Universal
Lecture Summary
Where to Next?
The Algebra of Logic
Boolean algebra, sometimes referred to as the algebra of logic, is a two-valued system of algebra that represents logical relationships and operations.
Historically, the principle of two-value algebra began with the Greek philosopher Aristotles bivalent (two-mode) definition of truth with four foundational laws of logic.
4
The Algebra of Logic (2)
Aristotles laws of two-value logic:
The Law of Identity (A is A),
The Law of Non-Contradiction (A is not non-A),
The Law of the Excluded Middle (either A or non-A)
The Law of Rational Inference.
These so-called Laws function within the scope of logic where a proposition is limited to one of two possible values.
5
George Boole
George Boole was a teacher and mathematician who lived between 1815 and 1864 mostly in Lincoln, England. (He lectured in Cork for a few years when the university was called Queens College.)
Boole applied algebraic techniques to the logic processes for two-value systems.
He contended that any logical statement could be assigned a binary value, such as true/false or yes/no.
6
George Boole (2)
Boole discussed ways of reducing logical relationships to simple statements of equality, inequality, inclusion, and exclusion.
He then showed ways to express these statements symbolically using a binary (two-valued) code.
7
George Boole 2 November 1815 8 December 1864
George Boole (3)
He stated the algebraic rules that governed these logical relationships. This system of mathematical logic came to be known as Boolean algebra.
The algebra is based on one or two variables with logic of AND, OR and NOT applied to them as combinations of inputs.
8
George Boole (4)
AND
A (False) AND B (False) -> False
A (True) AND B (False) -> False
A (False) AND B (True) -> False
A (True) AND B (True) -> True
9
George Boole (5)
OR
A (False) OR B (False) -> False
A (True) OR B (False) -> True
A (False) OR B (True) -> True
A (True) OR B (True) -> True
10
George Boole (6)
NOT
A (False) ->NOT A = True
A (True) ->NOT A = False
11
Claude Shannon Takes Booles Algebra
In the 1930s, a graduate student of Massachusetts Institute of Technology called Claude Shannon described the Boolean type of algebra as matching the effects of switch and relay-switching circuits, therefore effecting bi-state or bipolar machinery. 1s and 0s. Digital things!
(John Von Neumann used these principles in his architecture more on that soon.)
12
Claude Shannon (2)
13
A (False) AND B (False) -> False
A (True) AND B (False) -> False
A (False) AND B (True) -> False
A (True) AND B (True) -> True
A (False) OR B (False) -> False
A (True) OR B (False) -> True
A (False) OR B (True) -> True
A (True) OR B (True) -> True
A (False) -> True (NOT A)
A (True) -> False (NOT A)
0 0 = 0
1 0 = 0
0 1 = 0
1 1 = 1
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 1
0 = 1
1 = 0
Using Boolean Algebra with Binary
The basic principle of Boolean algebra is that a logic variable X can have only one of two possible values or states:
X = TRUE orX = FALSE
In binary notation, we can say:
X = TRUE = 1
X = FALSE = 0
This is called positive logic or high-true logic.
14
Using Boolean Algebra with Binary (2)
We might also say:
X = TRUE = 0
X = FALSE = 1
This is called negative logic or low-true logic.
Usually the positive logic convention is used.
15
Using Boolean Algebra with Binary (3)
Electrically, 1 is represented by a more positive voltage than zero and 0 is represented by zero volts.
Very often, on a microprocessor;
X = TRUE = 1 = 0.5 volts (variable up to 0.8)
X = FALSE = 0 = 0 volts (or a small bit over 0)
16
Boolean Arithmetic
With two states for input and output, it turns out that:
Addition WILL work,
Subtraction WILL NOT work,
Multiplication WILL work,
Division WILL NOT work.
N.B. See Twos Complement from Week 4s notes
17
Boolean Arithmetic (2)
Addition works as OR:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
1 + 1 can not be 0 nor can it be 2, so Boolean logic means it has to be 1.
18
Boolean Arithmetic (3)
Multiplication works as AND:
0 x 0 = 0
0 x 1 = 0
1 x 0 = 0
1 x 1 = 1
19
Boolean Arithmetic (4)
A + B reads, A OR B
A x B reads A AND B but since, in mathematics, generally, a dot () is used to show multiplication or nothing at all the notation of AB or AB might appear for A AND B.
20
Boolean Arithmetic (5)
NOT:
The outputs in Boolean algebra can be affected by using NOT in the logic i.e. you can invert inputs, A or B or the output, X by placing a NOT with the input before applying OR or AND, or just after the operation (OR or AND), thereby inverting the output.
21
Boolean Arithmetic (6)
The notation for NOT is a bar, a bubble or a complement apostrophe.
So, for example, if A = 0 then NOT A = 1 and it might appear as either:
= 1
= 1
A = 1
22
Boolean Arithmetic (7) Truth Tables
23
ABX
000
011
101
111
ABX
000
010
100
111
The OR Truth Table
The NOT Truth Table
The AND Truth Table
AX
01
10
The Principles of Logic Gates
The binary language used in todays computers reflects Booles binary logic.
Modern computers operate solely on the binary numbers 1 and 0.
All the instructions that direct a computers operation exist as a sequence of such binary digits or bits (0s and 1s).
24
The Principles of Logic Gates (2)
Binary digits (or logical variables) are processed in the machine as distinct voltage states in tiny electronic circuits known as logic gates.
A logic gate only recognizes two varieties of input, high-voltage (value of 1 or TRUE) and low-voltage (value of 0 or FALSE).
25
The Principles of Logic Gates (3)
The truth variables of Boolean algebra use the functionality of the logical concepts of AND, OR and NOT.
It will come as no surprise, therefore, that the logic gates (as electronic mechanisms) are AND, OR, and NOT.
These gates, used in differing combinations, allow the computer to execute all its operations and/or store its data.
26
The Principles of Logic Gates (4)
Each logic gate of the types AND and OR takes in two or more bits in the form of such voltages, combines them according to a built-in rule, and produces a single high-voltage or low-voltage logical conclusion (output).
Note, though, that NOT gates usually have one input and one output.
27
Diagram of the Main Gates
28
Please note that an inverting buffer is referred to and used to represent a NOT gate.
Digital Logic
Let A and B denote two propositions. (Here, propositions = declarative sentences that are either true or false but not both true and false at the same time).
If each proposition A and B is associated with a switch that will be closed if the proposition is true and open if the proposition is false then:
the combined proposition AB (A AND B) may be instantiated by connecting the switches in series.
Thus the output of one switch is the input of the other. Current can flow through the combined circuit if and only if both switches are closed, that is, if both A and B are true.
29
Gate Representations AND
30
Digital Logic (2)
The combined proposition A + B (A OR B) may be instantiated by connecting the switches in parallel.
Thus, with the switches side by side so that both contribute to the output simultaneously they can be used to represent the statement, A + B (A OR B).
In this case current will flow if either switch is closed or if both switches are closed. That is, if A or B or both are true.
31
Gate Representations OR
32
Gate Representations OR (2)
33
Gate Representations NOT
34
Inside an AND Gate with Truth Table
35
ABX
000
010
100
111
Inside an OR Gate with Truth Table
36
ABX
000
011
101
111
Inside an NOT Gate with Truth Table
37
AX
01
10
Logic Gates for Data Movement
Logic gates are the fundamental building blocks of all digital logic circuits they are switching circuits that perform certain simple operations on binary signals.
These operations are chosen to facilitate the implementation of functions such as changing 1s to 0s or 0s to 1, filtering 1s only or 0s only, checking for combinations of 1s and/or 0s.
38
Logic Gates for Data Movement (2)
Why? Why are these filterings and conversions important to computer circuits?
Thats the question I asked myself when I first saw logic gates. The reason: these allow for bits and bytes to be shifted through circuits and/or converted in the CPU.
Those shifts and conversions are the fundamental elements of computation. All action associated with components like the BIOS and the CPU need to use logic and algebra.
39
NAND and NOR Gates
On (in) a silicone chip it is simpler to manufacture the combination NOT AND and NOT OR than it is to deal with AND, OR and NOT.
NOT AND becomes NAND.
NOT OR becomes NOR.
40
NAND
41
The NAND gate looks like an AND gate with a NOT bubble right on its output.
The NAND Truth Table
42
The NAND Gate notation:
A NAND B = X
or
_____
A B = X
This reads as,
A and B Bar equals X.
ABX
001
011
101
110
NOR
43
The NOR gate looks like an OR gate with a NOT bubble on its output.
The NOR Truth Table
44
The NOR Gate notation:
A NOR B = X
or
_____
A + B = X
This reads as,
A or B Bar equals X.
ABX
001
010
100
110
The EXCLUSIVE OR Truth Table
45
ABX
000
011
101
110
The Exclusive OR Gate notation:
A XOR B = X
or
A B = X
This reads as,
A x-or B equals X.
De Morgans Theorem
The mathematician, De Morgan had a theorem of logic that, when applied to switching circuits years later, showed that one gate could be made to work like another by inverting inputs and outputs.
There are two parts to the theorem:
46
Augustus De Morgan 27 June 1806 18 March 1871
De Morgans Theorem First Part
The complement of two or more variables ANDed is equivalent to the OR of the complements of the individual variables.
____ _
(A B) = A + B
(NOT A AND B = NOT A OR NOT B)
47
De Morgans Theorem Second Part
The complement of two or more variables ORed together is equivalent to the AND of the complements of the individual variables.
___ __
(A + B) = A B
(NOT A OR B = NOT A AND NOT B)
48
De Morgans Theorem (2)
De Morgans rules are about what is known as group complementation in Boolean algebra.
The rules can be expressed as:
the negation of a disjunction is the conjunction of the negations
the negation of a conjunction is the disjunction of the negations
49
50
50
More on DeMorgans Theorem
0001
0101
1001
1110
00111
01101
10011
11000
Proof
The truth-tables are equal; therefore, the Boolean equations must be equal.
51
Overview & proof of DeMorgans Theorem #1
DeMorgans Theorems
Digital Electronics
2,1 Introduction to AOI Logic
Project Lead The Way, Inc.
Copyright 2009
51
More on DeMorgans Theorem (2)
0001
0110
1010
1110
00111
01100
10010
11000
Proof
The truth-tables are equal; therefore, the Boolean equations must be equal.
52
Overview & proof of DeMorgans Theorem #2
DeMorgans Theorems
Digital Electronics
2,1 Introduction to AOI Logic
Project Lead The Way, Inc.
Copyright 2009
52
A Comparison Between Boolean and DeMorgans Theorems
Commutative Law
Associative Law
Distributive Law
Consensus Theorem
DeMorgans
53
Updates of the Boolean Theorems with the addition of DeMorgans
DeMorgans Theorems
Digital Electronics
2,1 Introduction to AOI Logic
Project Lead The Way, Inc.
Copyright 2009
53
The Theorem in Gates
54
NAND and NOR Gates on CMOS
NAND and NOR gates are most commonly etched on the die of a CMOS chip.
(CMOS Complementary Metal-Oxide Semiconductor, the architecture of most computer CPUs and memory modules.)
Why?
55
(Intel)
A
B
A
B
NAND and NOR Gates on CMOS (2)
It is easier to implement groups of NAND and NOR gates on a chip than the AND, OR and NOT gates individually. (Overall, using NAND and NOR causes fewer inputs (a lower gate input count).
Also, they give a convenient conceptual representation.
56
(Intel)
A
B
A
B
NAND and NOR Gates on CMOS (3)
The NAND gate is the natural implementation for CMOS technology in terms of chip area and speed.
The NAND gate is a universal gate: a gate type that can implement any Boolean function:
NOT can be implemented with NAND
AND implemented with the NAND gate
OR using NAND (as in De Morgans Theorem)
57
NAND and NOR Gates on CMOS (4)
Similar to the NAND gate, the NOR gate is a universal gate.
With a NOR gate you can implement:
a NOT
an AND
an OR
58
NOR Gates as a Universal
59
NAND and NOR gates implementing NOT
NOR Gates as a Universal (2)
60
NAND and NOR gates implementing AND
NOR Gates as a Universal (3)
61
A NOR gate implementing OR
Gates in Circuits
In conclusion;
most of computer functionality is dependent upon (and contained as) electrical circuits. Specifically, electronic circuits.
The mathematical and logical functionality is dependent upon the circuits that are gates.
That functionality accounts for the execution of instructions and the movement/storage of data.
62
End of Boolean Algebra and Logic Gates
That describes the functionality of Boolean algebra representation and the introduction of logic gates. There is more to come on logic gates, but the structure of these circuits have been described in this first part.
Are there
ANY QUESTIONS?
63
Where to Next?
NEXT WEEK:
The theme of the next lecture:
Sequential Logic (Logic Gates)
Next time we can take a look at sequential logic an extension of the topics of Boolean algebra and logic gates. More examples of gate arrangements will give more clarity to the subject.
64
Thanks for your attentiveness.
See you here next time. Be safe and well in the meantime.
65
B
A
B
A
+
B
B
A
B
A
B
A
+
=
B
A
A
B
A
B
B
A
+
B
A
B
B
A
+
B
A
B
A
=
+
B
A
B
A
+
B
A
+
B
A
+
B
A
+
B
A
X
X
9)
1
X
X
8)
X
X
X
7)
1
1
X
6)
X
0
X
5)
0
X
X
4)
X
X
X
3)
X
1
X
2)
0
0
X
1)
=
=
+
=
+
=
+
=
+
=
=
=
=
(
)
(
)
(
)
(
)
(
)
(
)
(
)
Y
X
Y
X
14B)
Y
X
Y
X
14A)
Y
X
Y
X
X
13D)
Y
X
Y
X
X
13C)
Y
X
XY
X
13B)
Y
X
Y
X
X
13A)
YZ
YW
XZ
XW
Z
W
Y
X
12B)
XZ
XY
Z
Y
X
12A)
Z
Y
X
Z
Y
X
11B)
Z
XY
YZ
X
11A)
X
Y
Y
X
10B)
X
Y
Y
X
10A)
=
+
+
=
+
=
+
+
=
+
+
=
+
+
=
+
+
+
+
=
+
+
+
=
+
+
+
=
+
+
=
+
=
+
=
(IBM)
/docProps/thumbnail.jpeg
Reviews
There are no reviews yet.