CS计算机代考程序代写 computer architecture PowerPoint Presentation

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 Morgan’s 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 Aristotle’s bivalent (two-mode) definition of truth with four foundational laws of logic.
4

The Algebra of Logic (2)
Aristotle’s 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.

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 Queen’s 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.

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

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

Claude Shannon Takes Boole’s 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 or X = 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.

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 Two’s Complement from Week 4’s 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

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 A•B 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.

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

Boolean Arithmetic (7) Truth Tables
23
A B X
0 0 0
0 1 1
1 0 1

1 1 1

A B X
0 0 0
0 1 0
1 0 0
1 1 1

The OR Truth Table
The NOT Truth Table
The AND Truth Table
A X
0 1
1 0

The Principles of Logic Gates
The binary language used in today’s computers reflects Boole’s binary logic.

Modern computers operate solely on the binary numbers “1” and “0.”

All the instructions that direct a computer’s 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.

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

A B X
0 0 0
0 1 0
1 0 0
1 1 1

Inside an OR Gate with Truth Table
36
A B X
0 0 0
0 1 1
1 0 1
1 1 1

Inside an NOT Gate with Truth Table
37

A X
0 1
1 0

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.

Logic Gates for Data Movement (2)
Why? Why are these filterings and conversions important to computer circuits?
That’s 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.

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.”
A B X
0 0 1
0 1 1
1 0 1
1 1 0

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.”
A B X
0 0 1
0 1 0
1 0 0
1 1 0

The EXCLUSIVE OR Truth Table
45
A B X
0 0 0
0 1 1
1 0 1
1 1 0

The Exclusive OR Gate notation:
A XOR B = X
or
A  B = X

This reads as,
“A x-or B equals X.”

De Morgan’s 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 Morgan’s 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 Morgan’s 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)

De Morgan’s Theorem (2)
De Morgan’s 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

Related Posts