Transcript Computer Science 101

Computer Science 101
Logic Gates and Simple Circuits
Transistor - Electronic Switch

Collector


Base
Switch
Emitter


Base High (+5v or 1)
Makes connection
Base Low (0v or 0)
Disconnects
Say, 500 million
transistors on a chip 1
cm2
Change states in
billionth of sec
Solid state
Moore’s Law
In 1965, Intel co-founder Gordon
Moore saw the future. His prediction,
now popularly known as Moore's
Law, states that the number of
transistors on a chip doubles about
every two years.
Gates

A gate is an electronic device that takes
0/1 inputs and produces a 0/1 result.
NOT Gate
+5v
Output
Input

Input High (+5v or 1)
Output Low (0v or 0)

Input Low (0v or 0)
Output High (+5v or 1)

Output is opposite of
Input
NOT Gate
Ground
A
_
A
AND Gate
+5v

Output is 1 only if
• Input-1 is 1 and
• Input-2 is 1

Output
= Input1 AND Input2
Input-1
AND Gate
A
Input-2
B
Output
AB
OR Gate

• A is 1 or if
• B is 1
+5v

A
Output is 1 if
Output
= A OR B
B
OR Gate
A
Output
B
A+B
Boolean Expression  Python

Logical operators
• AND  and (Python)
• OR  or (Python)
• NOT  not (Python)

NOT ((x>y) AND ((x=5) OR (y=3))

not((x>y) and ((x==5)or(y==3)))

while (not((x>y) and ((x==5)or(y==3)))) :
…
Abstraction

In computer science, the term abstraction refers to
the practice of defining and using objects or
systems based on the high level functions they
provide.

We suppress the fine details of how these functions
are carried out or implemented.

In this way, we are able to focus on the big picture.

If the implementation changes, our high level work
is not affected.
Abstraction Examples

Boolean algebra - we can work with the
Boolean expressions knowing only the
properties or laws - we do not need to
know the details of what the variables
represent.

Gates - we can work with the logic gates
knowing only their function (output is 1
only if inputs are …). Don’t have to know
how gate is constructed from transistors.
Boolean Exp  Logic Circuit

To draw a circuit from a Boolean expression:
• From the left, make an input line for each variable.
• Next, put a NOT gate in for each variable that appears
negated in the expression.
• Still working from left to right, build up circuits for the
subexpressions, from simple to complex.
Logic Circuit: _ ____
AB+(A+B)B
Input Lines for Variables
A
B
Logic Circuit: _ ____
AB+(A+B)B
NOT Gate for B
A
B
_
B
Logic Circuit: _ ____
AB+(A+B)B
_
Subexpression AB
_
AB
A
B
_
B
Logic Circuit: _ ____
AB+(A+B)B
Subexpression A+B
_
AB
A
A+B
B
_
B
Logic Circuit: _ ____
AB+(A+B)B
___
Subexpression A+B
_
AB
A
A+B
B
_
B
____
A+B
Logic Circuit: _ ____
AB+(A+B)B
___
Subexpression (A+B)B
_
AB
A
A+B
B
_
B
____
A+B
____
(A+B)B
Logic Circuit: _ ____
AB+(A+B)B
Entire Expression
_
AB
A
A+B
B
_
B
____
A+B
____
(A+B)B
Logic Circuit  Boolean Exp

In the opposite direction, given a logic circuit, we
can write a Boolean expression for the circuit.

First we label each input line as a variable.

Then we move from the inputs labeling the
outputs from the gates.

As soon as the input lines to a gate are labeled,
we can label the output line.

The label on the circuit output is the result.
Logic Circuit  Boolean Exp
_
_ _
AB AB+AB
A
_
A
B
_
B
_
AB
A+B
Entire Expression
______
_ _
(AB+AB)(A+B)
______
_ _
AB+AB
Simplification Revisited

Once we have the BE for the circuit,
perhaps we can simplify.
AB  ABA  B  AB AB A  B
  
 A  BA  BB
 A  BA
 A  B A  B A  B
 AA  BA
 AB
Logic Circuit  Boolean Exp
Reduces to:
The Boolean Triangle
Boolean
Expression
Logic
Circuit
Truth
Table
The Boolean Triangle
Boolean
Expression
Logic
Circuit
Truth
Table