Transcript document

COS 111
Review Session 1
Friday, March 4, 2005
Outline
•
•
•
•
All About Numbers
Boolean/Logic Circuits
Assignment 4
Questions
Can you say five ?
Say five
Dutch – vijf
German – fünf
French – cinq
Spanish – cinco
Hindi – paanch
Slang -- Lincoln
Math -- 5
Say five
Dutch – vijf
German – fünf
French – cinq
Spanish – cinco
Hindi – paanch
Slang – Lincoln
Math -- 5
Spoken form
Say five
Dutch – vijf
German – fünf
French – cinq
Spanish – cinco
Hindi – paanch
Slang – Lincoln
Math -- 5
Visual form
When is five not five

When using different langauges


GM called one of their small cars "Nova". They didn't
sell too many in Spain where 'NoVa' means “doesn’t
go”
Math has many sub-dialects – binish, tertiarist,
octalish, hexadecimalish, AnyNish (I am making the names up
but that’s not the point :))
How much is 10 ?
• You need to know what language it is being
spoken in
– V in roman numerals refers to decimal 5 but refers to
decimal 31 in hexatridecimalish

How do we translate from one dialect to another ?

We need to understand the structure of math-dialects
Closer look at Roman Numerals
• Pick a few agreed upon quantities – I, V, X, L, C,
D, M
• Express all other numbers as sums and differences
of above – 7 is VII, 19 is XIX, 10000 is
MMMMMMMMMM
• Not very convenient as numbers become large
• Structure also cumbersome – 41 is XLI or IXL
Penta System
• Instead of sums and differences, can we use
multiplication to provide structure to number ?
• MMMMMMMMMM can be X-M
• But a odd collection I, V, X, L, C, D, M wont do
• Pick 5 symbols – 0, 1, 2, 3, 4. Why 5 ?
– Its arbitrary.
– It doesn’t matter what the base is as long as its fixed
Lets count…
0
1
2
3
4
What now ?
We need to combine our symbols to come up write
bigger numbers
Lets count…
0
1
2
3
4
What now ?
We have made one pass over all symbols. So lets
note down that fact. One pass and no more.
Lets count…
0
1
2
3
4
10 – lets call this a fif
We now use position of a symbol in a number to
hold its value.
Lets count…
0
1
2
3
4
10
10 – fif
11 – fif one
12 – fif two
13 – fif three
14 – fif four
20 -- twofif
Lets count…
0
1
2
3
4
10
10
11
12
13
14
20
20
21
22
23
24
30
30
31
32
33
34
40
40 – fourfif
41 – fourfif one
42 – fourfif two
43 – fourfif three
44 – fourfif four
100 – fiffif
We now use position of a symbol in a number to hold its
value
Penta System
• A number ABCDE is hence
–
–
–
–
–
–
A fif-fif-fif-fif +
B fif-fif-fif +
C fif-fif +
D fif +
E
A*fif^4 + B*fif^3 + C*fif^2 + D*fif + E
b System
• A number Xk-1….X0 in base b is
– Sum of Xi-1*b^i for i from 0 to k-1
• All rules of multiplication, addition, subtraction
are similar to what we normally do in base 10
numbers
Lets do some practice
• Conversion from one base to another
• Subtraction, addition, multiplication in any base
• Suggest numbers and operations and we work it
out together.
Before we move to next topic…
• Old number systems joke –
– Why is Christmas like Halloween ?
– Because 31 oct = 25 dec
Outline
•
•
•
•
All About Numbers
Boolean/Logic Circuits
Assignment 4
Questions
Boolean Algebra
• Shorthand for writing and thinking about logic
circuits
• Notation
–
–
–
–
–
' is a NOT
. is an AND
+ is an OR
1 represents TRUE
0 represents FALSE
Some simple rules
•
•
•
•
•
•
•
•
•
(A ') ' = A
(A ' + A) = 1
A+ 0 =A
A+1=1
(A '.A) = 0
A.0 = 0
A.1 = A
A+A=A
A.A = A
Distributive Laws
• E +(E1.E2...En) = (E+E1).(E+E2)...(E+En)
• E.(E1+E2+...En) = (E.E1) + (E.E2)... + (E.En)
DeMorgan’s Laws
• (E1 + E2 + ... + En)' = E1'.E2'....En'
• (E1.E2...En)' = E1' + E2' + ... + En'
Lets try some examples
• x'.y + x.y + x
• x.y.z + x'.y.z + x'.y'.z + x'.y'.z + x.y'.z' + x.y'.z
• x'.y + x'.y' + x.y' + x.y
Outline
•
•
•
•
All About Numbers
Boolean/Logic Circuits
Assignment 4
Questions