Transcript Introduction to Database Systems

Applications : Digital Logic Circuits 2.4 and
Number Systems
2.5
Instructor: Hayk Melikya
Introduction to Abstract Mathematics
[email protected]
1
Simple electrical switching device
Here are more complicated circuits
Introduction to Abstract Mathematics
2
Serial and Parallel switches
Introduction to Abstract Mathematics
3
Block Boxes and Gates
Black Box is specified by the signal
input/output table.
An effective way to build more complicated
circuits is connecting less complicated
block box circuits
Three such a gates: NOT-gate, AND-gate,
OR-gate can be combined
Introduction to Abstract Mathematics
4
Combinatorial circuits
1.
2.
3.
4.
Never combine two input wires
An input line can be split and used as input for two separate
gates
Any output can be used as input
No output can be feed back to gate
Example:
Deterring input/output table for given circuit
Introduction to Abstract Mathematics
5
Circuits and Boolean expressions
Combinational circuit always correspond to some Boolean expression,
such that input/output table of a table and a truth table of the
expression are identical
Construct equivalent boolean expression using disjunctive
normal form as follows
1.
for all outputs of 1 construct a conjunctive form based
on the truth table row.
2.
All conjunctive forms are united using disjunction
Introduction to Abstract Mathematics
6
Example:
Input/output table
The circuit corresponding to given table
is the disjunctions of obtained below three
conjunctive terms
 P  Q  R
 P  Q  ~R
 P  ~ Q  ~ R
(P  Q  R)  (P  Q  ~R)  (P  ~ Q  ~ R)
Introduction to Abstract Mathematics
7
Example:
Here is the combinatorial circuit corresponding to the
( P  Q  R)  (P  Q  ~R)  (P  ~ Q  ~ R)
Introduction to Abstract Mathematics
8
Example: Construct circuit which corresponds to
Exclusive or of P and Q
Introduction to Abstract Mathematics
9
Number Systems

Decimal number system
There are only 10 digits: 0, 1, 2, 3, ,4, 5, 6, 7, 8, 9
Decimal numbers are finite sequences of digits
example:
376 = 3x 102 + 7x 101 + 6x100

base
= 300 + 70 + 6
Binary number system
there are only two digits: 0 and 1
Binary numbers are finite sequences of 0’s and 1’s
example:
1101 = 1x23 + 1x 22 + 0x21 + 1x20 = 1x8 + 1x4 + 1x1 = 13


base
Conversion between decimal and binary numbers
Binary addition and subtraction
Introduction to Abstract Mathematics
10
Binary addition and subtraction
Adding numbers in base two
1 1 1 0 12
+ 1 0 1 02
1 0 0 1 1 12
Circuits for computer addition
Introduction to Abstract Mathematics
Adding digits in base 2
1 + 1 = 102
1 + 0 = 012
0 + 1 = 012
0 + 0 = 002
11
Digital Circuits for Addition: Full Adder – addition of
two bits and a carry
To construct a circuit to add multidigit binary numbers it is necessary to have
circuit which computes sum of three binary digits. Such a circuit is called Full
Adder

Parallel Adder – addition of multi-bit numbers
Introduction to Abstract Mathematics
12
Digital Circuits for Addition: Parallel Adder – addition
of two 3 binary digit numbers.
Two full-adders and one half adder can be used to buld a circuit to add
2 binary 3 digit numbers PQR and STU to obtain WXYZ
Introduction to Abstract Mathematics
13
Try:


Represent 43 in binary notation
Represent 110110 in decimal notation
Add
11101 01
+ 1011 11
Introduction to Abstract Mathematics
14
Practice problems
1.
2.
3.
Study the Sections 1.4 and 1.5 from your textbook.
Be sure that you understand all the examples discussed in
class and in textbook.
Do the following problems from the textbook:
Exercise 2.4, # 2, 4, 15, 19, 23.
Exercise 2.5, # 3, 5, 8, 10, 14, 18.
Introduction to Abstract Mathematics
15