Digital Logic: Boolean Algebra and Gates
CSE12 Winter 2021
2
CSE12 Winter 2021
1
0 0 0
3
CSE12 Winter 2021
4
A general CM
CSE12 Winter 2021
OS circuit
Pull Up Network (PUN)
Q. How to determine Out without solving for entire truth table???
A. Follow Output path through either the PUN (towards Vdd) or the PDN (towards gnd)
PDN approach: Under what conditions does Out have a direct path to gnd??
Out = 0, (when AAND B ON) OR (whenCANDDON)
Pull Down Network (PDN)
5
CSE12 Winter 2021
6
Axioms of Boolean Algebra (CMPE 100!)
Algebra : study of mathematical symbols and the rules for manipulating these symbols
Different types of algebra exists depending on what mathematical space you are working with ; e.g. real algebra, vector algebra, linear algebra, Boolean algebra
The three important tenets of algebra: symbols, rules/operators, constants
We are already pretty familiar with the rules of real algebra, i.e. working with real numbers e.g. x ,y,z,k are real numbers: x(y+z-k) = xy +xz – xk
Above example used distributive law and “plus”, “subtract”, “multiply” operators.
Boolean algebra is the only algebra understood by a computer. The computer physically solves problems in Boolean algebra which are based on high level problems (in various types of algebra)
Two constants: 1,0; Three fundamental operators: AND (&), OR(+), NOT
CSE12 Winter 2021
7
Axioms of Boolean Algebra (CMPE 100!)
0·0=0 1+1=1 1·1=1 0+0=0 0·1=1·0=0 1+0=0+1=1 ifx=0thenx’=1 ifx=1thenx’=0
Let’s have a closer look at what exactly those transistors were computing in the previous slides!
CSE12 Winter 2021
8
Single-Variable Theorems (CMPE 100!)
x·0=0 x+ 1 = 1 x·1=x x+ 0 = x x·x=x x+ x = x x · x’ = 0 x + x’ = 1 (x’)’ = x
CSE12 Winter 2021
9
Properties of Boolean Algebra (CMPE 100!)
Commutative x · y = y · x x + y = y + x
Associative
x · (y · z) = (x · y) · z x + (y + z) = (x + y) + z
Distributive
x · (y + z ) = x · y + x · z x + y · z = (x + y) · (x + z)
CSE12 Winter 2021
10
Properties of Boolean Algebra (CMPE 100!)
Absorption
x + x · y = x x · (x + y) = x
x
Combining
x · y + x · y’ = x (x + y) · (x + y’) = x
Y(gulp!)
CSE12 Winter 2021
11
Properties of Boolean Algebra (CMPE 100!)
De Morgan’s Laws (x · y)’ = x’ + y’ (x + y)’ = x’y’
Other
x + x’·y = x + y x · (x’ + y) = x · y
CSE12 Winter 2021
12
Basic Logic Gates
CSE12 Winter 2021
XOR
13
XOR gate
CSE12 Winter 2021
14
XOR
Output is
a(XOR)b=a’b+ab’ (for 2 operands)
In general, we say output is
1 if odd number of inputs are 1 0 if even number of inputs are 1
Output is
a(XOR)b=a’b+ab’ (for 2 operands)
In general, we say output is
1 if odd number of inputs are 1 0 if even number of inputs are 1
XOR gate as a “programmable “inverter (NOT gate)
Thus, we can “program” Z to either be inverse of B, or simply be equal to B, depending on the value of A
Above is an alternative symbol for XOR gate as a programmable inverter. But in general, we will stick to the normal XOR gate symbol
CSE12 Winter 2021 15