CSEE 3827: Fundamentals of Computer

Systems, Spring 2021

Lecture
Prof. Dan Rubenstein (danr@cs.columbia.edu
2

Agenda (M&K 2.1-2.2)

• Terminology

• Boolean algebra (incl. DeMorgan’s Law)

• Logic gates

• Circuit fabrication

• NAND, NOR

• DUAL

• XOR

2
Boolean Terminology
Terminology

• Recall: Digital / Binary / Boolean: 0 = False, 1 = True

• Binary or Boolean Variable: a symbolic representation of a value that might be

0 or 1, e.g., X, Y, A, B

• Complement (e.g., of a variable X): written X : the opposite value of X

X X
I sometimes say “negate”: , e.g.,
0 1 if boolean X=1, negating X makes X=0.
Negating X again changes it back to 1

1 0

• Literal: a boolean variable or its complement (e.g., X, X, Y)

 Boolean Logic

• All logical functions can be implemented in terms of three logical operations:

NOT AND OR Not

addition
can omit the “⋅” anymore!
x x x y x.y x y x+y

0 1 0 0 0 0 0 0
1 0 0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1

• Whether “+” represents addition or logical OR can often be gotten from

context

• When not from context, we will specify

5
Boolean Logic 2

• Boolean logic precedence rules just like addition / multiplication

• Implied precedence: NOT before AND before OR

• Use parentheses as necessary

A+BC same as A+ (BC)

(A + B)C same as ((A) + B)C

 Terminology cont’d

• Expression: a set of literals (possibly with repeats) combined with logic

operations (and possibly ordered by parentheses)

• e.g., 4 expressions:
AB + C, (AB) + C, (A + B)C, ((A) + B)C

• Equation: expression1 = expression2

• e.g.,
(A + B)C = ((A) + B)C

• Function of (possibly several) variables: an equation where the lefthand side is

de ned by the righthand side

F(A,B,C) = ((A) + B)C

7
fi
XOR: the parity operation
X Y X⊕Y
• X ⊕ Y = XY + XY

0 0 0
0 1 1
1 0 1
1 1 0

• In general, represents parity, i.e.,

• X1 ⊕ X2 ⊕ X3 ⊕ ... ⊕ Xk = 1 when an odd number of Xi = 1

8
XOR as a “control”

• Y ⊕ 0 = Y

• Y ⊕ 1 = Y

• As we XOR bits, the result “ ips” when XOR’ing a 1, and stays the same
when XOR’ing a 0

• 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 1

0 1 0 1 0 1

9
fl
Boolean Logic: Truth Table

Truth Table: Function output for all

D X A L=DX + A combinations of input variables
0 0 0 k variables ➜ 2k input combinations
0 0 1
0 1 0 e.g., L = DX + A
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

10

Boolean Logic: Example

Intermediate computations to compute function:

D X A X DX L=DX + A

0 0 0 1 0 0
0 0 1 1 0 1
0 1 0 0 0 0
0 1 1 0 0 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 0 1

(M&K Table 2-2) 11

Boolean Logic: Example 2

Truth table for XY + XY

X Y XY + XY

0 0

0 1

1 0

1 1

12
Boolean Logic: Example 2

Truth table for XY + XY: intermediate computations

X Y X Y XY XY XY + XY

0 0 1 1 0 1 1
0 1 1 0 0 0 0
1 0 0 1 0 0 0
1 1 0 0 1 0 1

13
Boolean Theorems
Boolean Algebra: Identities and Theorems
For any boolean X (X ∈ {0,1}):
OR AND NOT

X+0 = X X1 = X (identity)

X+1 = 1 X0 = 0 (null)

X+X = X XX = X (idempotent)

X+X = 1 XX = 0 (complementarity)

X=X (involution)

X+Y = Y+X XY = YX (commutativity)

X+(Y+Z) = (X+Y)+Z X(YZ) = (XY)Z (associativity)

X(Y+Z) = XY + XZ X+YZ = (X+Y)(X+Z) (distributive)

X+Y = X Y XY = X + Y (DeMorgan’s theorem)

15
Other important simpli cations:

• X + XY = X :

• If X is false, both sides clearly false

• If X is true, LHS is true no matter what Y is

e.g.
X = “You are male
• X (X+Y) = X :
Y = “You are taller than 5’5”

• If 1st term is false, doesn’t matter what second term is

• If 1st term true, so is 2nd term

•
16
,

fi
Boolean Algebra: Example

Simplify (reduce # of literals) this equation using algebraic manipulation.

F = XYZ + XYZ + XZ

17
Boolean Algebra: Example
Simplify this equation using algebraic manipulation.

F = XYZ + XYZ + XZ

XY(Z + Z) + XZ (by reverse distribution)

XY(1) + XZ (by complementarity)

XY + XZ (by identity)

18
Complementing (parts of) expressions (“the big bar”)

• Complement operations can be applied to expressions (big bars)

• Precedence: the complement is performed after all other boolean ops that lie
beneath it

• e.g., A+B : First, OR A with B, then complement (negate)

A B A+B A+B

0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
19
Complementing (parts of) expressions (“the big bar”)
• Order of precedence example:

(A + BD)C

1. Complement A. (In parallel) AND B with D

2. OR A with BD

3. Complement (A + BD)

4. AND (A + BD) with C

5. Complement (A + BD) C

20
DeMorgan’s Theorem
Important!!!!!
DeMorgan’s Theorem

• Procedure for simplifying complemented expressions (i.e.,

removal of “big bar"

• Remove the “big bar” over AND or OR of 2 (or more) functions

(e.g., F & G) and replace...

• AND with OR, OR with AND

• 1 with 0, 0 with 1

FG = F + G
• function F with F, F with F

F + G = FG

Understanding DeMorgan

• Example:

• F = Donald Trump won the 2020 Election

• G = Donald Trump was a good president

It’s not the case that [Trump won 2020 AND

FG: was a good president]
FG = F + G
Either Trump didn’t win OR wasn’t a good
F+G: president (or both)

It’s not the case that [Trump won 2020 OR

F+G: was a good president (or both)]
Trump didn’t win 2020 AND Trump wasn’t a
F + G = FG
FG: good president!

DeMorgan’s Theorem extended

• Can do for 3 functions (or variables), i.e.,

FGH = F + G + H

F + G + H = FGH

• Can apply to complementing the AND of any N functions (or variables), or

complementing the OR of any N functions (or variables)

24

Boolean Algebra: Example 2

Find the complement of Z.

Z = AB + AB

Z=

25
Boolean Algebra: Example 2
Find the complement of Z.
F G

Z = AB + AB

Z = AB + AB

(AB) (AB) (by DeMorgan’s)

(A + B) (A + B) (by DeMorgan’s)

(A + B) (A + B) (by involution)

AA + AB + BA + BB (by commutativity)
(by complementarity and
AB + BA
identity) 26
DeMorgan’s Practice

ABC + ACD + BC F1 = ABC, G1 = ACD, H1 = BC, F1+G1+H1 = F1 G1 H1

= (ABC)(ACD)(BC) (ABC) (ACD) = ABCD, F2 = B, G2 = C, F2G2 = F2+G2

= (ABCD)(B+C)
= ABCD + ABCD
= ABCD
 Consensus Theorem

• XY + XZ + YZ = XY + XZ (The YZ term is redundant)

• Proof:

• If YZ=0, it’s obviously not needed (just have XY+XZ+0 on LHS)

• If YZ = 1

• both Y and Z are 1. XY + XZ + 1 = 1 so , LHS equation = 1

• Either X or X = 1. Since Y=Z=1, either XY=1 or XZ = 1,

• so RHS equation either 1 + 0 or 0 + 1 = 1

28
Circuit Perspective
Circuit Representation of Boolean Ops

• Information ows from left to right

• Input(s) all the way on the left, output(s) on the right

These circuits consume area, power, and time

Goal: minimize the amount of circuitry to compute the desired function 30

fl

more-than-2 input shorthand

A
• A+B+C+D can be written in shorthand as the gate:
B
C
D

• This is really a series of 2-input gates:

A
B

C
D

• i.e., a k-input gate is really a sequence of gates

with depth log2k

31
We simplify to reduce required circuitry...

F = XYZ + XYZ + XZ

XY(Z + Z) + XZ (by reverse distribution)

XY1 + XZ (by complementarity)

XY + XZ (by identity)

32
Circuit view

wire connector: black dot signi es wires are connected

33
fi
 Circuit view: why reduce?

• Cost:
wire connector: black dot signi es wires are connected

• pay per gate:

higher cost

• more gates = more

space on chip

• Wires are fast, gates

are slow: speed of a
circuit (time from
setting inputs to
getting output) roughly
proportional to circuit
depth: longest-gated
path
Top circuit more costly (more gates), and faster when considering 3-input gates each have depth 2

34
fi
 Circuit view: why reduce?

• Cost:
wire connector: black dot signi es wires are connected 3-input gate
(Actually represent depth-2
+1 +2 composition of 2-iput gates)
• pay per gate:
higher cost

+2
• more gates = more
space on chip

• Wires are fast, gates

are slow: speed of a
circuit (time from +1 +1
setting inputs to
+1
getting output) roughly
proportional to circuit
depth: longest-gated
path
Top circuit more costly (more gates), and faster when considering 3-input gates each have depth 2
Top circuit depth 5 along top path, bottom circuit depth 3 along top path (longest paths)
35
s

fi
Alternate shorthand for multiple inputs to Gate
A
• Given inputs A,B,C,D,E,F,
C
D
F

• Another representation for A+C+D+F This is really

a series of 2-input gates:

A
B
C black dot signi es connection:
no dot means no connection
D
E
F

36
fi
Bitwise parallel
operations
Bit-wise (in parallel) Logic Ops

• Up to now, we looked at single-bit logic ops, e.g., X + Y = Z where X,Y,Z are

each one bit

• Will often need to perform logic op on set of bits in parallel, e.g.,

• X = Xk-1Xk-2…X1X0, Y=Yk-1Yk-2…Y1Y0

• Want to compute Z=Zk-1Zk-2…Z1Z0 where for each i, Zi = Xi + Yi

• Can just write Z = X+Y as a shorthand (here + is logical OR)

• e.g., X = 0110, Y = 0011, Z = X+Y = 0110 + 0011 = 0111

• e.g., X=1010, Y = 1100, Z = XY = 1000 (here, we are talking about logical

AND)

38
Bitwise logical ops with circuitry
k
}k

…
= k wires running in parallel, same as
• extends to circuits as well, e.g., k=3

• X = 101, Y=110, X+Y = 111

3
3
X 3 Z
Y

• Note the di erence between above and

which ORs 3 bits together
39
ff
Bitwise logical ops with circuitry
k
}k

…
= k wires running in parallel, same as
• extends to circuits as well, e.g., k=3

• X = 101, Y=110, X+Y = 111

X2
X1 Z2
3 X0
3
X 3 Z Z1
Y2
Y Y1
Y0 Z0

• Note the di erence between above and

which ORs 3 bits together
40
ff
NAND and NOR:
Universal gates
Universal gates: NAND, NOR

x y z = xy
0 0 1
0 1 1 XY
1 0 1
Note: the “o” in a circuit
1 1 0
represents a NOT (inverter)

Different from “ ” which

x y z = x+y represents wire connector
0 0 1
0 1 0 X+Y
1 0 0
1 1 0

42

NAND and NOR universal because...

• NOT, AND, OR can each be implemented using only NAND gates

• NOT, AND, OR can each be implemented using only NOR gates

A = A NAND A A = A NOR A

AB = A NAND B A+B = A NOR B

A+B = A NAND B AB = A NOR B

Any circuit can be entirely implemented with just NAND or just NOR gates!!!

43
Duals
Duals

• All boolean expressions have duals

• Any theorem you can prove, you can also prove for its dual

• To form a dual...

• replace AND with OR, OR with AND

• replace 1 with 0, 0 with 1

What is the dual of this expression?

X + Y = XY
What is the dual of this expression?

X + Y = XY
dual

XY = X + Y
What are the complements of these expressions?

X + Y = XY complement
dual

XY = X + Y complement
What are the complements of these expressions?

X + Y = XY complement XY = X + Y
dual

XY = X + Y complement X + Y = XY
These are also the duals of one another.

X + Y = XY complement XY = X + Y
dual

dual
XY = X + Y complement X + Y = XY

Note: to complement a function, compute its dual,

then complement literals
“Complement using Dual” example

• F = X + A (Z + X (Y + W) + Y (Z + W))

• Dual: Fdual = X (A + Z (X + YW)(Y + ZW)) (swapped ANDs and ORs)

• F = X (A + Z (X + YW)(Y + ZW)) (“Flipped” literals)

51
Revisiting XOR
XOR: the parity operation
X Y X⊕Y
• X ⊕ Y = XY + XY

0 0 0 X

1
Y
0 1
1 0 1
1 1 0

• In general, represents parity, i.e.,

• X1 ⊕ X2 ⊕ X3 ⊕ ... ⊕ Xk = 1 when an odd number of Xi = 1

53
Summary

• Subtle things that are very important to remember from this lecture:

• Boolean order of precedence (slide 6)

• XOR (slide 8)

• Truth Tables (slide 10)

• Boolean (basic) theorems (slide 15)

• DeMorgan’s Law (slide 21) & using to simplify complemented expressions

(slide 50)

54