Transcript Sample Unix Session

Boolean Algebra &
Logic Design
1
Boolean Algebra
• Developed by George Boole in the 1850s
• Mathematical theory of logic.
• Shannon was the first to use Boolean
Algebra to solve problems in electronic
circuit design. (1938)
2
Variables & Operations
• All variables have the values 1 or 0
– sometimes we call the values TRUE / FALSE
• Three operators:
– OR
written as , as in A  B
– AND written as , as in A  B
– NOT written as an overline, as in
A
3
Operators: OR
• The result of the OR operator is 1 if either
of the operands is a 1.
• The only time the result of an OR is 0 is
when both operands are 0s.
• OR is like our old pal addition, but operates
only on binary values.
4
Operators: AND
• The result of an AND is a 1 only when both
operands are 1s.
• If either operand is a 0, the result is 0.
• AND is like our old nemesis multiplication,
but operates on binary values.
5
Operators: NOT
• NOT is a unary operator – it operates on
only one operand.
• NOT negates it’s operand.
• If the operand is a 1, the result of the NOT
is a 0.
• If the operand is a 0, the result of the NOT
is a 1.
6
Equations
Boolean algebra uses equations to express
relationships. For example:
X  A  ( B  C)
This equation expresses a relationship
between the value of X and the values of A,
B and C.
7
Quiz (already?)
What is the value of each X:
X 1  1  (0  1)
X2  A A
X3  A A
X 4  X 4 1
huh?
8
Laws of Boolean Algebra
Just like in good old algebra, Boolean
Algebra has postulates and identities.
We can often use these laws to reduce
expressions or put expressions in to a
more desirable form.
9
Basic Postulates of Boolean
Algebra
• Using just the basic postulates – everything
else can be derived.
Commutative laws
Distributive laws
Identity
Inverse
10
Identity Laws
A0  A
A 1  A
11
Inverse Laws
A A 1
A A  0
12
Commutative Laws
A B  B  A
A B  B  A
13
Distributive Laws
A  ( B  C )  ( A  B)  ( A  C )
A  ( B  C )  ( A  B)  ( A  C )
14
Other Identities
Can be derived from the basic postulates.
Laws of Ones and Zeros
Associative Laws
DeMorgan’s Theorems
15
Zero and One Laws
A 1  1
Law of Ones
A0  0
Law of Zeros
16
Associative Laws
A  ( B  C )  ( A  B)  C
A  ( B  C )  ( A  B)  C
17
DeMorgan’s Theorems
A  B  A B
A B  A  B
18
Other Operators
• Boolean Algebra is defined over the 3 operators
AND, OR and NOT.
– this is a functionally complete set.
• There are other useful operators:
– NOR: is a 0 if either operand is a 1
– NAND: is a 0 only if both operands are 1
– XOR: is a 1 if the operands are different.
• NOTE: NOR is (by itself) a functionally complete
set!
19
Boolean Functions
• Boolean functions are functions that operate
on a number of Boolean variables.
• The result of a Boolean function is itself
either a 0 or a 1.
• Example:
f(a,b) = a+b
20
Question
• How many Boolean functions of 1 variable
are there?
• We can answer this by listing them all!
f1 ( x)  x
f 2 ( x)  x
f 3 ( x)  0
f 4 ( x)  1
21
Tougher Question
• How many Boolean functions of 2 variables
are there?
• It’s much harder to list them all, but it is
still possible…
22
Alternative Representation
• We can define a Boolean function by
describing it with algebraic operations.
• We can also define a Boolean function by
listing the value of the function for all
possible inputs.
23
OR as a Boolean Function
for(a,b)=a+b
a
b
for(a,b)
0
0
0
0
1
1
1
0
1
1
1
1
24
Truth Tables
NOR NAND XOR
OR
AND
0 0
0
0
1
1
0
0 1
1
0
0
1
1
1 0
1
0
0
1
1
1 1
1
1
0
0
0
a
b
25
Truth Table for (X+Y)·Z
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
(X+Y)·Z
0
0
0
1
0
1
0
1
26
Gates
• Digital logic circuits are electronic circuits that are
implementations of some Boolean function(s).
• A circuit is built up of gates, each gate
implements some simple logic function.
• The term gates is named for Bill Gates, in much
the same way as the term gore is named for Al
Gore – the inventor of the Internet.
27
A Gate
Output
A
Inputs
B
???
f(A,B)
28
Gates compute something!
• The output depends on the inputs.
• If the input changes, the output might
change.
• If the inputs don’t change – the output does
not change.
29
An OR gate
A
A+B
B
30
An AND gate
A
A•B
B
31
A NOT gate
A
A
32
NAND and NOR gates
A
A•B
B
A
A+B
B
33
Combinational Circuits
• We can put gates together into circuits
– output from some gates are inputs to others.
• We can design a circuit that represents any
Boolean function!
34
A Simple Circuit
A
?
B
35
Truth Table for our circuit
b
a
b
a•b
a•b
0 0
1
1
1
0
0 1
1
0
0
1
1 0
0
1
0
1
1 1
0
0
0
1
a
36
Alternative Representations
• Any of these can express a Boolean
function. :
Boolean Equation
Circuit (Logic Diagram)
Truth Table
37
Implementation
• A logic diagram is used to design an
implementation of a function.
• The implementation is the specific gates
and the way they are connected.
• We can buy a bunch of gates, put them
together (along with a power source) and
build a machine.
38
Integrated Circuits
• You can buy an AND gate chip:
39
Function Implementation
• Given a Boolean function expressed as a
truth table or Boolean Equation, there are
many possible implementations.
• The actual implementation depends on what
kind of gates are available.
• In general we want to minimize the number
of gates.
40
Example:
A
0
0
1
1
f  A B  A B
B A B
0
0
1
0
0
1
1
0
A B
0
1
0
0
f
0
1
1
0
41
One Implementation
f  A B  A B
A
f
B
42
Another Implementation
A
f
B

f  A  B  A  B   A  B  A  B

43
Proof it’s the same function
A B  A B 
DeMorgan's Law
A  B   A  B  
DeMorgan's Laws
A  B   A  B  
Distributive
A  B  A A  B  B  
A  A  B  A A  B  B  B   Distributive
Inverse, Identity
 B  A   A  B  
DeMorgan's Law
 B  A   A  B  
DeMorgan's Laws
B  A  A  B 
44
Better proof!
A B  A B 
Distributive
A  B A A  B B 
A  A B  A  A  B B  B Distributive (twice)
B  A  A  B
Inverse, Identity
45
Possible Questions
• Prove that NOR is a functionally complete set.
– Show how you can express the functions AND, OR and
NOT in terms of NOR.
• Prove that two expressions are (or are not) really
the same boolean function.
– Use identities/postulates to transform one expression in
to another
– Compare truth tables.
• Know DeMorgan's Theorems (prove them!).
46