Transcript Mathematical Ideas

Chapter 4
Numeration
and
Mathematical
Systems
© 2008 Pearson Addison-Wesley.
All rights reserved
Chapter 4: Numeration and
Mathematical Systems
4.1
4.2
4.3
4.4
4.5
4.6
Historical Numeration Systems
Arithmetic in the Hindu-Arabic System
Conversion Between Number Bases
Clock Arithmetic and Modular Systems
Properties of Mathematical Systems
Groups
4-1-2
© 2008 Pearson Addison-Wesley. All rights reserved
Chapter 1
Section 4-1
Historical Numeration Systems
4-1-3
© 2008 Pearson Addison-Wesley. All rights reserved
Historical Numeration Systems
• Mathematical and Numeration Systems
• Ancient Egyptian Numeration – Simple
Grouping
• Traditional Chinese Numeration –
Multiplicative Grouping
• Hindu-Arabic Numeration - Positional
4-1-4
© 2008 Pearson Addison-Wesley. All rights reserved
Mathematical and Numeration Systems
A mathematical system is made up of
three components:
1. a set of elements;
2. one or more operations for combining
the elements;
3. one or more relations for comparing the
elements.
4-1-5
© 2008 Pearson Addison-Wesley. All rights reserved
Mathematical and Numeration Systems
The various ways of symbolizing and working
with the counting numbers are called
numeration systems. The symbols of a
numeration system are called numerals.
4-1-6
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Counting by Tallying
Tally sticks and tally marks have been
used for a long time. Each mark
represents one item. For example, eight
items are tallied by writing
4-1-7
© 2008 Pearson Addison-Wesley. All rights reserved
Counting by Grouping
Counting by grouping allows for less
repetition of symbols and makes numerals
easier to interpret. The size of the group is
called the base (usually ten) of the number
system.
4-1-8
© 2008 Pearson Addison-Wesley. All rights reserved
Ancient Egyptian Numeration –
Simple Grouping
The ancient Egyptian system is an example
of a simple grouping system. It used ten as
its base and the various symbols are shown
on the next slide.
4-1-9
© 2008 Pearson Addison-Wesley. All rights reserved
Ancient Egyptian Numeration
4-1-10
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Egyptian Numeral
Write the number below in our system.
4-1-11
© 2008 Pearson Addison-Wesley. All rights reserved
Traditional Chinese Numeration –
Multiplicative Grouping
A multiplicative grouping system involves
pairs of symbols, each pair containing a
multiplier and then a power of the base. The
symbols for a Chinese version are shown on
the next slide.
4-1-12
© 2008 Pearson Addison-Wesley. All rights reserved
Chinese Numeration
4-1-13
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Chinese Numeral
Interpret each Chinese numeral.
a)
b)
4-1-14
© 2008 Pearson Addison-Wesley. All rights reserved
Positional Numeration
A positional system is one where the various
powers of the base require no separate symbols.
The power associated with each multiplier can
be understood by the position that the
multiplier occupies in the numeral.
4-1-15
© 2008 Pearson Addison-Wesley. All rights reserved
Positional Numeration
In a positional numeral, each symbol (called a
digit) conveys two things:
1. Face value – the inherent value of the
symbol.
2. Place value – the power of the base which
is associated with the position that the digit
occupies in the numeral.
4-1-16
© 2008 Pearson Addison-Wesley. All rights reserved
Positional Numeration
To work successfully, a positional system
must have a symbol for zero to serve as a
placeholder in case one or more powers of
the base are not needed.
4-1-17
© 2008 Pearson Addison-Wesley. All rights reserved
Hindu-Arabic Numeration –
Positional
One such system that uses positional form is
our system, the Hindu-Arabic system.
The place values in a Hindu-Arabic numeral,
from right to left, are 1, 10, 100, 1000, and so
on. The three 4s in the number 45,414 all
have the same face value but different place
values.
4-1-18
© 2008 Pearson Addison-Wesley. All rights reserved
Hindu-Arabic Numeration
7,
5
4
1,
7
2
5
.
4-1-19
© 2008 Pearson Addison-Wesley. All rights reserved
Section 4.1: Historical Numerical
Systems
1. A mathematical system has
a) Elements
b) Operations
c) Relations
d) All of the above
Section 4.1: Historical Numerical
Systems
2. Our numeration system is an example of a
a) simple grouping system
b) multiplicative grouping system
c) positional system
d) complex grouping
Chapter 1
Section 4-2
Arithmetic in the Hindu-Arabic System
Arithmetic in the Hindu-Arabic
System
• Expanded Form
• Historical Calculation Devices
Expanded Form
By using exponents, numbers can be written
in expanded form in which the value of the
digit in each position is made clear.
Example: Expanded Form
Write the number 23,671 in expanded form.
Distributive Property
For all real numbers a, b, and c,
b  a    c  a   b  c   a.
For example,

 

3 104  2 104   3  2  104
 5 10 .
4
Example: Expanded Form
Use expanded notation to add 34 and 45.
Decimal System
Because our numeration system is based on
powers of ten, it is called the decimal
system, from the Latin word decem, meaning
ten.
Historical Calculation Devices
One of the oldest devices used in calculations
is the abacus. It has a series of rods with
sliding beads and a dividing bar. The abacus
is pictured on the next slide.
Abacus
Reading from right to left, the rods have values of 1,
10, 100, 1000, and so on. The bead above the bar has
five times the value of those below. Beads moved
towards the bar are in “active” position.
Example: Abacus
Which number is shown below?
Lattice Method
The Lattice Method was an early form of a
paper-and-pencil method of calculation. This
method arranged products of single digits into
a diagonalized lattice.
The method is shown in the next example.
Example: Lattice Method
Find the product 38  794 by the lattice
method.
7
9
4
3
8
Napier’s Rods (Napier’s Bones)
John Napier’s invention, based on the
lattice method of multiplication, is often
acknowledged as an early forerunner to
modern computers.
The rods are pictured on the next slide.
Napier’s Rods
See figure 2 on page 174
Russian Peasant Method
Method of multiplication which works by
expanding one of the numbers to be multiplied
in base two.
Nines Complement Method
Step 1
Align the digits as in the standard
subtraction algorithm.
Step 2
Add leading zeros, if necessary, in the
subtrahend so that both numbers have the
same number of digits.
Step 3
Replace each digit in the subtrahend
with its nines complement, and then add.
Step 4
Delete the leading (1) and add 1 to the
remaining part of the sum.
Example: Nines Complement Method
Use the nines complement method to subtract
2803 – 647.
Solution
Step 1
2803
Step 2 Step 3 Step 4
2803 2803 2155
 647  0647
+9352
1
12,155 2156
Section 4.2: Arithmetic in the HinduArabic System
1. Which of the following is an example of
expanded form?
a) 205
b) 2 10  0 10  5 10
2
c) 5(40 + 1)
1
0
Section 4.2: Arithmetic in the HinduArabic System
2. Which of the following is an example of the
distributive property?
a) 3  5  4  5  (3  4)  5
b) 3  (4  5)  (4  5)  3
c) 5(3 + 4) = 5(7)
Chapter 1
Section 4-3
Conversion Between Number Bases
Conversion Between Number Bases
• General Base Conversions
• Computer Mathematics
General Base Conversions
We consider bases other than ten. Bases
other than ten will have a spelled-out
subscript as in the numeral 54eight. When a
number appears without a subscript assume it
is base ten. Note that 54eight is read “five four
base eight.” Do not read it as “fifty-four.”
Powers of Alternative Bases
Base two
Base five
Fourth
Third Second First
Zero
Power
power Power Power Power
16
8
4
2
1
625
125
25
5
1
Base seven
2401
343
49
7
1
Base eight
4096
512
64
8
1
65,536
4096
256
16
1
Base
sixteen
Example: Converting Bases
Convert 2134five to decimal form.
Calculator Shortcut for Base
Conversion
To convert from another base to decimal
form: Start with the first digit on the left and
multiply by the base. Then add the next digit,
multiply again by the base, and so on. The
last step is to add the last digit on the right.
Do not multiply it by the base.
Example:
Use the calculator shortcut to convert
432134five to decimal form.
Example: Converting Bases
Convert 7508 to base seven.
Converting Between Two Bases
Other Than Ten
Many people feel the most comfortable
handling conversions between arbitrary bases
(where neither is ten) by going from the
given base to base ten and then to the desired
base.
Computer Mathematics
There are three alternative base systems that
are most useful in computer applications.
These are binary (base two), octal (base
eight), and hexadecimal (base sixteen)
systems.
Computers and handheld calculators use the
binary system.
Example: Convert Binary to Decimal
Convert 111001two to decimal form.
Solution
111001two

1 2  1  2  1  2  0  2  0  2  1
 57
Example: Convert Hexadecimal to
Binary
Convert 8B4Fsixteen to binary form.
Section 4.3: Conversion Between
Number Bases
1. Which of the following is not a valid base 8
number?
a) 456
b) 781
c) 0
Section 4.3: Conversion Between
Number Bases
2. The following is a way to convert what
base to base 10?
  3  7  2   7  5  7  2
a) 7
b) 5
c) 2
Chapter 1
Section 4-4
Clock Arithmetic and Modular
Systems
4-4-55
© 2008 Pearson Addison-Wesley. All rights reserved
Clock Arithmetic and Modular
Systems
• Finite Systems and Clock Arithmetic
• Modular Systems
4-4-56
© 2008 Pearson Addison-Wesley. All rights reserved
Finite Systems
Because the whole numbers are infinite,
numeration systems based on them are
infinite mathematical systems. Finite
mathematical systems are based on finite
sets.
4-4-57
© 2008 Pearson Addison-Wesley. All rights reserved
12-Hour Clock System
The 12-hour clock system is based on an
ordinary clock face, except that 12 is
replaced by 0 so that the finite set of the
system is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.
4-4-58
© 2008 Pearson Addison-Wesley. All rights reserved
Clock Arithmetic
As an operation for this clock system, addition
is defined as follows: add by moving the hour
hand in the clockwise direction.
11 0 1
10
2
9
8
3
4
7 6
5
5+3=8
4-4-59
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Finding Clock Sums by
Hand Rotation
Find the sum: 8 + 7 in 12-hour clock
arithmetic
Solution
Start at 8 and move
the hand clockwise
through 7 more hours.
Answer: 3
11 0 1
10
2
9
8
3
4
7 6
5
4-4-60
© 2008 Pearson Addison-Wesley. All rights reserved
12-Hour Clock Addition Table
4-4-61
© 2008 Pearson Addison-Wesley. All rights reserved
12-Hour Clock Addition Properties
Closure The set is closed under addition.
Commutative For elements a and b, a + b = b + a.
Associative For elements a, b, and c,
a + (b + c) = (a + b) + c.
Identity The number 0 is the identity element.
Inverse Every element has an additive inverse.
4-4-62
© 2008 Pearson Addison-Wesley. All rights reserved
Inverses for 12-Hour Clock Addition
Clock
value a
0
Additive
Inverse -a
0 11 10 9 8 7 6 5 4 3
1
2
3 4 5 6 7 8 9 10 11
2
1
4-4-63
© 2008 Pearson Addison-Wesley. All rights reserved
Subtraction on a Clock
If a and b are elements in clock arithmetic,
then the difference, a – b, is defined as
a – b = a + (–b)
4-4-64
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Finding Clock Differences
Find the difference 5 – 9.
4-4-65
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Finding Clock Products
Find the product 4  5.
4-4-66
© 2008 Pearson Addison-Wesley. All rights reserved
Modular Systems
In this area the ideas of clock arithmetic are
expanded to modular systems in general.
4-4-67
© 2008 Pearson Addison-Wesley. All rights reserved
Congruent Modulo m
The integers a and b are congruent modulo
m (where m is a natural number greater than
1 called the modulus) if and only if the
difference a – b is divisible by m.
Symbolically, this congruence is written
a  b (mod m).
4-4-68
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Truth of Modular Equations
Decide whether each statement is true or false.
a) 12  4 (mod 2)
b) 35  4 (mod 7)
c) 11  44 (mod 3)
4-4-69
© 2008 Pearson Addison-Wesley. All rights reserved
Criterion for Congruence
a  b (mod m) if and only if the same
remainder is obtained when a and b are
divided by m.
4-4-70
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Solving Modular Equations
Solve the modular equation below for the whole
number solutions.
2  x  5(mod 8)
4-4-71
© 2008 Pearson Addison-Wesley. All rights reserved
Section 4.4: Clock Arithmetic and
Modular Systems
1. In 12-hour clock addition, find the additive
inverse of 3.
a) 8
b) 9
c) –3
Section 4.4: Clock Arithmetic and
Modular Systems
2. Is it true that 7  3(mod 2) ?
a) Yes
b) No
Chapter 1
Section 4-5
Properties of Mathematical Systems
Properties of Mathematical Systems
•
•
•
•
•
•
•
An Abstract System
Closure Property
Commutative Property
Associative Property
Identity Property
Inverse Property
Distributive Property
An Abstract System
The focus will be on elements and operations that
have no implied mathematical significance. We can
investigate the properties of the system without
notions of what they might be.
Operation Table
Consider the mathematical system with elements
{a, b, c, d} and an operation denoted by ☺.
The operation table on the next slide shows how
operation ☺ combines any two elements. To use
the table to find c ☺ d, locate c on the left and d
on the top. The row and column intersect at b, so
c ☺ d = b.
Operation Table for ☺
☺
a
b
c
d
a
a
b
c
d
b
b
d
a
c
c
c
a
d
b
d
d
c
b
a
Closure Property
For a system to be closed under an operation, the
answer to any possible combination of elements
from the system must in the set of elements.
This system is
closed.
☺ a
b
c
d
a
a
b
c
d
b
b
d
a
c
c
c
a
d
b
d
d
c
b
a
Commutative Property
For a system to have the commutative property, it
must be true that for any elements X and Y from the
set, X ☺ Y = Y ☺ X.
This system has the
commutative property.
The symmetry with
respect to the diagonal
line shows this
property
☺
a
b
c
d
a
a
b
c
d
b
b
d
a
c
c
c
a
d
b
d
d
c
b
a
Associative Property
For a system to have the associative property, it must
be true that for any elements X, Y, and Z from the set,
X ☺ (Y ☺ Z) = (X ☺ Y) ☺ Z.
This system has the
associative property.
There is no quick
check – just work
through cases.
☺
a
b
c
d
a
a
b
c
d
b
b
d
a
c
c
c
a
d
b
d
d
c
b
a
Identity Property
For the identity property to hold, there must be an
element E in the set such that any element X in the set,
X ☺ E = X and E ☺ X = X.
a is the identity
element of the set.
☺
a
b
c
d
a
a
b
c
d
b
b
d
a
c
c
c
a
d
b
d
d
c
b
a
Inverse Property
If there is an inverse in the system then for any
element X in the system there is an element Y (the
inverse of X) in the system such that
X ☺ Y = E and Y ☺ X = E, where E is the identity
element of the set.
☺ a b c d
You can inspect the
table to see that every
element has an
inverse.
a
a
b
c
d
b
b
d
a
c
c
c
a
d
b
d
d
c
b
a
Potential Properties of a Single
Operation Symbol
Let a, b, and c be elements from the set of any
system, and ◘ represent the operation of the system.
Closure
a ◘ b is in the set
Commutative
a ◘ b = a ◘ b.
Associative
a ◘ (b ◘ c) = (a ◘ b) ◘ c
Identity The system has an element e such that
a ◘ e = a and e ◘ a = a.
Inverse there exists an element x in the set such
that
a ◘ x = e and x ◘ a = e.
Example: Identifying Properties
Consider the system
shown with elements
{0, 1, 2, 3, 4} and
operation . Which
properties are
satisfied by this
system?

0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
0
2
3
0
3
0
3
0
4
0
4
2
0
4
Distributive Property
Let ☺ and ◘ be two operations defined for
elements in the same set. Then ☺ is
distributive over ◘ if
a ☺ (b ◘ c) = (a ☺ b) ◘ (a ☺ c)
for every choice of elements a, b, and c from
the set.
Example: Testing for the Distributive
Property
Is addition distributive over multiplication on
the set of whole numbers?
Section 4.5: Properties of Mathematical
Systems
1. For elements a and e and the operation ,
a e  e a  a represents which property?
a) Commutative
b) Inverse
c) Identity
Section 4.5: Properties of Mathematical
Systems
2. When a system has two operations, which
property would we look for?
a) Commutative
b) Distributive
c) Associative
Chapter 1
Section 4-6
Groups
Groups
• Groups
• Symmetry Groups
• Permutation Groups
Group
A mathematical system is called a group if,
under its operation, it satisfies the closure,
associative, identity, and inverse properties.
Example: Checking Group Properties
Does the set {–1, 1} under the operation of
multiplication form a group?
Example: Checking Group Properties
Does the set {–1, 1} under the operation of
addition form a group?
Symmetry Groups
A group can be built on sets of objects other than
numbers. Consider the group of symmetries of a
square. Start with a square labeled below.
Front
Back
4
1
1'
4'
3
2
2'
3'
Symmetries - Rotational
M rotate 90°
N rotate 180°
3
4
2
3
2
1
1
4
P rotate 270°
Q original
1
2
4
1
4
3
3
2
Symmetries - Flip
Flip about horizontal line through middle.
4
1
3
2
R
3'
2'
4'
1'
Flip about vertical line through middle.
4
1
3
2
S
1'
4'
2'
3'
Symmetries - Flip
Flip about diagonal line upper left to lower right.
4
1
3
2
T
4'
3'
1'
2'
Flip about diagonal line upper right to lower left.
4
1
3
2
V
2'
1'
3'
4'
Symmetries of the Square
□
M
N
P
Q
R
S
T
V
M
N
P
Q
M
T
V
S
R
N
P
Q
M
N
S
R
V
T
P
Q
M
N
P
V
T
R
S
Q
M
N
P
Q
R
S
T
V
R
V
S
T
R
Q
N
P
M
S
T
R
V
S
N
Q
M
P
T
R
V
S
T
M
P
Q
N
V
S
T
R
V
P
M
N
Q
Example: Verifying a Subgroup
Form a mathematical system by using only the
set {M, N, P, Q} from the group of symmetries
of a square. Is this new system a subgroup?
Solution
The operational table is
given and the system is
a group. The new
group is a subgroup of
the original group.
□
M
N
P
Q
M
N
P
Q
M
N
P
Q
M
N
P
Q
M
N
P
Q
M
N
P
Q
Permutation Groups
A group comes from studying the arrangements,
or permutations, of a list of numbers.
The next slide shows the possible permutations
of the numbers 1-2-3.
Arrangements of 1-2-3
A*: 1-2-3
2-3-1
B*: 1-2-3
2-1-3
C*: 1-2-3
1-2-3
D*: 1-2-3
1-3-2
E*: 1-2-3
3-1-2
F*: 1-2-3
3-2-1
Example: Combining Arrangements
Find D*E*.
Solution
1-2-3
1-3-2 Rearrange according to D*.
3
E* replaces 1 with 3.
3 1 E* replaces 2 with 1.
3-2-1 E* replaces 3 with 2.
Section 4.6: Groups
1. A mathematical group does not have to
satisfy which property?
a) Commutative
b) Closure
c) Associative
Section 4.6: Groups
2. Does {a, b} satisfy a group under the
operation shown below?
a) Yes
b) No
¤
a
b
a
a
b
b
b
a