Transcript 1 - Computer Science

CPSC 171 Introduction to
Computer Science
Boolean Logic, Gates, & Circuits
Announcements
Read Chapter 4
Exam, Oct 2nd in class
Boolean Logic
A Boolean variable, A, is either true or
false
A Boolean expression, (A AND B),
evaluates to either true or false
Boolean operators include:



AND (&  • )
OR ( + )
NOT (a bar ' ¬ ~)
Boolean Operators
a AND b
true only when A and B are both true
a OR b
true when A is true, B is true, or both are true
NOT a
true when A is false
Truth Tables
Truth tables can be
used to capture
when an expression
is true, given its
inputs
a
b
a AND b
0
0
1
0
1
1
1
1
0
1
1
1
You make truth tables for AND and NOT
Example Boolean Expressions
(a AND b) OR (NOT a AND c)
a·b + ~a·c
ab+āc
Truth tables can be made for complex
expressions as well
Boolean Logic (continued)
Example:
(a AND b) OR ((NOT b) and (NOT a))
a
b
Value
0
0
1
1
0
1
0
1
1
0
0
1
Gates
Gates


Hardware devices built from transistors to
mimic Boolean logic
An electronic device that operates on a
collection of binary inputs to produce a
single binary output
AND gate (page 161 in text)


Two input lines, one output line
Outputs a 1 when both inputs are 1
Gates (continued)
OR gate (page 163 in text)


Two input lines, one output line
Outputs a 1 when either input is 1
NOT gate (page 161 in text


One input line, one output line
Outputs a 1 when input is 0 and vice versa
Figure 4.15
The Three Basic Gates and Their Symbols
Circuits
A collection of logic gates that
transforms a set of binary inputs into a
set of binary outputs
Wire gates together keeping constraints
for the number of inputs to any gate
Example Circuit
a 1
b
1
0
1
output
0
c 1
d
1
1
If a, b, c, and d are all true the output
can be determined by tracing through
the circuit
Designing Circuits
A circuit construction algorithm
1. Truth Table Construction
Determine outputs for every possible input
2. Sub-expression Construction (using AND and NOT
gates)
For each output find the rows that are 1 and build a subexpression that is true for the exact input
3. Sub-expression combination (using OR gates)
Take each subexpression and combine them, 2 at a time, using
OR gates
4. Circuit Diagram Production
Construct final circuit by converting Boolean operators into
gates
Example Circuit Design
Design a 3-input circuit that is true if
exactly two inputs are true, and false
otherwise
You Try it: Design a 2-input circuit that is
true if the inputs are the same, and
false otherwise
Examples of Circuit Design
and Construction
Compare-for-equality circuit
Addition circuit
Both circuits can be built using the circuit
design algorithm
A Compare-for-Equality Circuit
CE compares two unsigned binary
integers for equality
Built by combining together 1-bit
comparison circuits (1-CE)
Integers are equal if corresponding bits
are equal (AND together 1-CD circuits
for each pair of bits)
A Compare-for-Equality Circuit
(continued)
1-CE circuit truth table
a
b
Output
0
0
1
0
1
0
1
0
0
1
1
1
A Compare-for-Equality Circuit
(continued)
1-CE Boolean expression

First case: (NOT a) AND (NOT b)

Second case: a AND b

Combined:
((NOT a) AND (NOT b)) OR (a AND b)
Figure 4.22
One-Bit Compare-for-Equality Circuit
N-Bit Compare for Equality Circuit
AND together the 1-CE circuits, two at a
time
An Addition Circuit
Adds two unsigned binary integers,
setting output bits and an overflow
Built from 1-bit adders (1-ADD)
Starting with rightmost bits, each pair
produces

A value for that order

A carry bit for next place to the left
An Addition Circuit (continued)
1-ADD truth table

Input
 One bit from each input integer
 One carry bit (always zero for rightmost bit)

Output
 One bit for output place value
 One carry bit
Figure 4.24
The 1-ADD Circuit and Truth Table
An Addition Circuit (continued)
Building the full adder




Put rightmost bits into 1-ADD, with zero for
the input carry
Send 1-ADD’s output value to output, and
put its carry value as input to 1-ADD for
next bits to left
Repeat process for all bits
See pg 174, 175, 176