# 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.

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 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.

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 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.

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 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

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 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.

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

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.

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

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.

38

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.

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.”

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)

48

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

49

50

50

More on DeMorgan’s Theorem

0 0 0 1

0 1 0 1

1 0 0 1

1 1 1 0

0 0 1 1 1

0 1 1 0 1

1 0 0 1 1

1 1 0 0 0

Proof

The truth-tables are equal; therefore, the Boolean equations must be equal.

51

Overview & proof of DeMorgan’s Theorem #1

DeMorgan’s Theorems

Digital Electronics

2,1 Introduction to AOI Logic

Project Lead The Way, Inc.

Copyright 2009

51

More on DeMorgan’s Theorem (2)

0 0 0 1

0 1 1 0

1 0 1 0

1 1 1 0

0 0 1 1 1

0 1 1 0 0

1 0 0 1 0

1 1 0 0 0

Proof

The truth-tables are equal; therefore, the Boolean equations must be equal.

52

Overview & proof of DeMorgan’s Theorem #2

DeMorgan’s Theorems

Digital Electronics

2,1 Introduction to AOI Logic

Project Lead The Way, Inc.

Copyright 2009

52

A Comparison Between Boolean and DeMorgan’s Theorems

Commutative Law

Associative Law

Distributive Law

Consensus Theorem

DeMorgan’s

53

Updates of the Boolean Theorems with the addition of DeMorgan’s

DeMorgan’s 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 Morgan’s 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