CS 2204: Digital Circuits
Lecture 2
Operation of a Boolean logic network
What happens if the inputs change?
Operation of a
Boolean network
0 0 1
0 1 1
1 0 0
1 1 1
Timing diagram
Boolean Algebra
Boolean algebra allows us to manipulate equations and
formulas of Boolean variables. To do so, we will leverage
several “theorems”
See truth tables of . and + ops
Try
plugging in
both values
of x and
verifying
that these
theorems
hold…
Boolean Algebra = “regular” Algebra??
NOT !
Boolean algebra doesn’t follow the rules of algebra
over reals…
Boolean Algebra DUALITY
Dual of a statement:
1. Replace + with . (and vice-versa)
2. Replace 0 with 1 (and vice versa)
If a Boolean statement is true, it’s dual is true!
Two variable theorems
These look like
standard algebra
This one doesn’t. Hmmm…Duality
Two variable theorems
Now on to slightly more complex theorems
Proof: x.1 + x.y =x.(1+y)
= x.1 = x
Proof: x . (y + !y)
= x . 1 = x
Using Venn Diagrams to prove theorems
● Logic “0” is the empty set
● Logic “1” is the universal set
● x.y is interpreted as the intersection of sets x and y
● x+y is interpreted as the union of sets x and y
Proving theorems
x y x y
Proving theorems
x y x y
Proving theorems
x y x y
“COnsensus” Theorema
Now on to slightly more complex theorems
Worked out
proofs in class
Proving theorems
x y
z
x
y
z
Precedence of operations
Brackets, NOT, AND, OR
=
Implementing boolean logic functions
Given a Boolean function (as a truth table) how do we
implement (“synthesize”) it using NOT, AND and OR gates?
For what combination of
inputs is function f
equal to 1?
Implementing boolean logic functions
Given a Boolean function (as a truth table) how do we
implement (“synthesize”) it using NOT, AND and OR gates?
Let’s say it in words:
F is 1 if x1=0 AND x2=0
OR x1=0 AND x2=1
OR x1=1 AND x1=1
IMplementation
Can we simplify this further?
Chip Design
Verilog basics
What function does
f implement?
Like a
function
Module
name
Input
/output
ports
Gates can be
specified in
any order
(out,in1, in2)
wire k, g, h; Internal wires
Exercise
Draw a gate-level netlist corresponding to the following
Verilog code.