MSCP 52011
Introduction to Computer Systems
Boolean Algebra
algebra (n)
the study of mathematical symbols and the rules for manipulating these symbols
Boolean algebra
the branch of algebra in which the values of the variables are the values true and false
Boolean Operators
And
The statementA • B is true ifA and B are both true; otherwise, it is false.
The And operator can be written as:
AB
A•B
A∧B -logic
A⋂B -settheory
A && B – c-style programming
A
B
A . B
F0
F0
F0
F0
T1
F0
T1
F0
F0
T1
T1
T1
Boolean Operators
Or
The statementA + B is true ifA or B (or both) are true; if both are false, the statement is false.
The Or operator can be written as: A+B
A∨B -logic
A⋃B -settheory
A || B – c-style programming
A
B
A+B
0
0
0
0
1
1
1
0
1
1
1
1
Boolean Operators Not
The statement A’ is true if and only if is false.
The Not operator can be written as: A’
Ā
¬A – logic
A’ – set theory
!A – c-style programming
A
not A
0
1
1
0
Boolean Axioms
And, Or, & Not can be stated in the form of axioms:
Identity 0 and X = 0 Idempotence 1andX=X Negation: 0’ = 1
1 or 0 = 1 0orX=X 1’ = 0
Boolean Properties
Derived from the axioms: Commutative XY=YX
X+Y=Y+X X+(Y+Z) = (X+Y)+Z
X+(YZ) = (X+Y)(X+Z) X+X = X
X+ XY = X
(X+Y)(X+Y’) = X (X+Y)’ = X’Y’
Associative Distributive Idempotive Absorption Combining DeMorgan’s
X(YZ) = (XY)Z X(Y+Z)=XY+XZ
XX=X X(X+Y) = X
(XY) + XY’) = X (XY)’ = X’+Y’
Boolean Operators Visualized as Circuits
And
Boolean Operators Visualized as Circuits
Or
Boolean Operators as Logic Gates
Summary
Minimizing Circuits with Karnaugh Maps
Demo of Nand2Tetris software, HDL, testing chips
Multiplexer
A Multiplexor is a data selector, a device that selects between several input signals and forwards it to a single output line.
Multiplexer
A
B
A mux B
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
4-Way Multiplexer
8-Way Multiplexer
DeMultiplexer
A Demultiplexor takes a single input line and routes it to one of several output lines.
4-Way Demultiplexer
8-Way Demultiplexer
Project 1 Design the chips in this order:
Not Mux
And DeMux
Or Mux16
Xor Mux4Way16 Not16 Mux8Way16 And16 DMux4Way Or16 DMux8Way Or8Way
Read: Chapters 1-2 in the text
In 2 weeks: upload completed Project 0
(zipped) to canvas.
A week from today (well, Friday 6am): upload hdl files for Project 1 chips (zipped) to canvas.