“The study of mathematics,

like the Nile,

begins in minuteness
but ends in magnificence.”
Charles Caleb Colton
 THE
NATURE
OF MATHEMATICS
Daniel M. Abratique, Ph D
Mathematics is a useful way to think
about nature and our world
 MATHEMATICS
Mathematics is derived from the ancient word manthanein
meaning "to learn". The Greek root mathesis means
"knowledge" or its other form máthema meaning science,
knowledge, or learning, and mathematikós or mathemata
means "fond of learning".
• Mathematics relies on both logic and creativity, and
it is pursued both for a variety of practical purposes
and for its intrinsic interest.
• The essence of mathematics lies in its beauty and
its intellectual challenge.
• The chief value of mathematics is how it applies to
work.
• Because mathematics plays such a central role in
modern culture, some basic understanding of the
nature of mathematics is requisite for scientific
literacy.
• One needs to perceive mathematics as part of the
scientific endeavor, comprehend the nature of
mathematical thinking, and become familiar with
key mathematical ideas and skills.
Basically it is seen as a study of patterns and relations.
It is also a way of thinking. Mathematics is seen as an
art which is characterized by order and internal
consistency. It is a language that uses carefully defined
terms and symbols. Thus, mathematics is a tool (Reys,
Lindquist, Lambdin, Smith and Suydam, 2004). The
study of patterns which may be numerical, logical
or geometric.
Mathematics has five basic
characteristics’ namely:
precision, definition,
reasoning, coherence, and
purposefulness.
It is precise in the sense that mathematical statements are clear
and unambiguous. It is clear what is known and what is not
known. Definitions abound in mathematics. It is the bedrock of
mathematical structure and the platform that supports reasoning.
Reasoning is the lifeblood of mathematics. It is the engine that
drives proving and problem solving. Its absence is the root cause
of the learning by rote approach. Concepts and skills are
interwoven in mathematics. And lastly, mathematics is goal-
oriented, and for every concept or skill there is a purpose for it.
MATHEMATICS IN NATURE

Euclid said that "The laws of nature are

but the mathematical thoughts of God."
Galileo affirmed by stating that
“Mathematics is the language in which God
has written the Universe.”
To see the world in a grain of sand,
And a heaven in a wild flower;
Hold infinity in the palm of your hand,
And eternity in an hour.
- William Blake
PATTERNS
IN
NATURE
TYPES OF PATTERNS
• Though every living and non-living thing of the world may
seem to follow a pattern of its own, looking deeply into the
geometry and mechanism of the pattern formation can lead
you to broadly classify them into merely two categories:
 Self-organized patterns/ Inherent organization
 Invoked organization
Self-Organized patterns
• they are based on simple set of rules, and they use only local
information to determine how a particular sub-unit evolves
• One of the first cellular automata (a mechanism to study the pattern
formation) to be studied in any depth was the so-called ''Game of
Life'', devised by the mathematician Joan Horton Conway.
• Another example is the stripes of a zebra
• Self-organizing patterns extends to the non-living world as well. They
appear in the mineral deposits between layers of sedimentary rocks,
in the path of a lightening bolt as itcrashes to the ground, in the
undulating ripples of windblown sand on a desert dune.
Invoked Organization
• the building of structures does involve indeed a little architect that
oversees and imposes order and pattern. There are no 'subunits' that
interact with one another to generate a pattern; instead, each of the
animals acts like a stonemason, measuring, fitting, and moving pieces
into place
• weaver bird uses its own body as a template as it builds the
hemispherical egg chamber of the nest
• spider crates its sticky orb following a genetically determined recipe for
laying out the various radii and spirals of the web
• caddisfly larva builds an intricate hideaway from grains of sand or other
debris carefully fastened together with silk
• honeycomb made by bees
 MATHEMATICS: AS A SOLUTION TO THE
PATTERN FORMATION

• The geometry of most patterns in nature can be linked to

mathematical numbers either directly or indirectly.
• these relations seem to have been forced through, the high degree to
which natural patterns follow mathematical series and numbers is
amazing.
The Golden Ratio and the Fibonaccci Series
• Leonardo Fibonacci began the study of this sequence by posing the
following problem in his book, Liber Abaci

''How many pairs of rabbits will be produced in a year, beginning with

a single pair , if in every month each pair bears a new pair which
becomes productive from the second month on?'‘
this problem gives rise to the sequence 1, 1, 2, 3, 5, 8, 13, ... in which any
term after the first two can be found by summing the two previous terms
In functional notation we could write f(n) = f (n - 1) + f (n - 2) using f(0) = 1
and f(1) = 1.

The ratio between two consecutive terms of this series tends to the
number 1.61803399.
It is a number commonly encountered when taking ratios of distances in
simple geometric figures such as pentagons, decagons and dodecagons. It
is denoted by PHI, and is called the divine proportion, golden mean, or
golden section
Other forms of Phi
• One way to find Phi is to consider the solutions to the equation 𝑥2 − 𝑥 −
1=0
When solving this equation we find that the roots are
1± 5
𝑥=
2
We can also express Phi by the following two series
1
𝜑 =1+
1
1+ 1
1+1+⋯

𝜑= 1+ 1+ 1+ 1+⋯
Phi can also be found in many geometrical shapes, but instead of
representing it as an irrational number; we can express it in the
following way. Given a line segment, we can divide it into two
segments A and B, in such a way that the ratio of the length of the
entire segment is to the length of the segment A is same as that of the
length of segment A is to the length of segment B. If we calculate
these ratios, we see that we get an approximation of the Golden
Ratio.
• Another geometrical figure that is commonly associated with Phi is
the Golden Rectangle. This particular rectangle has sides A and B
that are in proportion to the Golden Ratio. It has been said that the
Golden Rectangle is the most pleasing rectangle to the eye.
• If we take the isosceles triangle that has the two base angles of 72
degrees and we bisect one of the base angles, we should see that we get
another Golden triangle that is similar to the first. If we continue in this
fashion we should get a set of Whirling Triangles.
Out of these Whirling Triangles, we are able to draw a logarithmic spiral
that will converge at the intersection of the two blue lines

A logarithmic spiral
– a commonly
observed pattern in
nature
Examples
 (a) A pine cone exhibits the pattern of spirals of both directions – 13
clockwise and 8
counterclockwise (13 and 8 are consecutive terms of the Fibonacci
Series)
(b) The seed of the cone flower following a logarithmic spiral pattern
(c) The shells of snails are also in the shape of spirals.
• Analogy of giraffe pattern and Dirichlet domains.(a) side of a giraffe
(b) Dirichlet polygon
Polygon structures: (a) the left posterior wing of the dragon fly. (b) Schematic of fly
veins. (c) Completion of a new boundary between the two domains (arrow)
• The world around us seems to make up of several distinct
patterns, evolving various complex steps of formation.
However, looking more deeply we see many similarities and
resemblances. The numerous models explained above have
no experimental proof and may not be correct, but they
definitely show linkages between patterns formed under
highly contrasting natural conditions e.g. (a zebra coat and
sand dunes) and also show that the mechanisms between
the formations of these patterns need not necessarily be
complex
For further readings (references)
• Adam, John A; Mathematics in Nature: Modeling Patterns in the
Natural World, published by New Jersey K: Princeton University Press,
2003
• http://www.scottcamazine.com/personal/DesignNature/
• http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html
• http://maven.smith.edu/~phyllo/
• http://www.apogeephoto.com/aug2004/along82004.shtml
• http://jwilson.coe.uga.edu/emt669/Student.Folders/Frietag.Mark/Ho
mepage/Goldenratio/goldenratio.html
• http://goldennumber.net/
What distinguishes a mathematical model from, say, a
poem, a song, a portrait or any other kind of “model”,
is that the mathematical model is an image or picture
of reality painted with logical symbols instead of with
words, sounds or watercolors.
- John Casti, from Reality Rules: 1.
 MATHEMATICAL
LANGUAGE
AND
Day 2 SYMBOLS
January 5, 2018
AM

33
Imagine the following scenario?

You are in a math class, and the instructor

passes a piece of paper to each student. It is
announced that the paper contains Strategies in
Solving Math Problems. You are to read it and
make comments. Upon glancing the paper, you
are surprised that it is written in a foreign
language that you do not understand!

IS THE INSTRUCTOR BEING FAIR?

34
Responses:
Of course not. Indeed , the instructor is probably trying to make a
point. Although the ideas in the paragraph may be simple, there is no
access to the ideas without a knowledge of the language in which the
ideas are expressed.
This situation has a very strong analogy in mathematics. People
frequently have trouble understanding mathematical ideas; not
necessarily because the ideas are difficult, but because they are being
presented in a foreign language – THE LANGUAGE OF MATHEMATICS!

35
 Mathematical Language
& Symbols

Language of Mathematics
Like any language, mathematics has its own symbols,
syntax and rules.

• to understand the expressed ideas

• to communicate ideas to others

36
 Mathematical Language
& Symbols

Characteristics
• Precise
- be able to make very fine distinctions
• Concise
- use symbols to be able to express more
• Powerful
- be able to express complex thoughts with relative
ease

37
 Mathematical Language
& Symbols

Noun versus Sentences

ENGLISH

Noun Sentence
(name given to object of (must state a complete
interest thought)

• Person • TRUE: The word “math” has four

letters.
• Place
• FALSE: The word “math” has 5
• Thing letters
• Sometimes True/Sometimes False:
Math is a difficult subject.

38
 Mathematical Language
& Symbols

Expression versus Sentences

MATHEMATICS

Expression Sentence
(name given to (must state a complete
mathematical object of thought)
interest
• Number • TRUE : 1+ 2 = 3
• Set • FALSE: 1 + 2 = 4
• Matrix • ST/SF : x =1
• Ordered pair
• Average
39
 Mathematical Language
& Symbols

Ideas Regarding Expressions

• Expressions have different names

Example:
5 2 + 3 10÷2 (6 - 2) + 1 1 + 1+ 1 +1+ 1
• Common in solving expressions is to SIMPLIFY
•

40
 Mathematical Language
& Symbols

What does SIMPLER mean?

• Fewer symbols
• Fewer operations
• Better suited to current use
• Preferred/ style/format

41
 Mathematical Language
& Symbols

Mathematical Sentence
A mathematical sentence is the analogue of an English sentence;
it is a correct assignment of mathematical symbols that states a
complete thought.

• Truth of a Sentence
The notion of truth (the property of being true or false) is of
fundamental importance in the mathematical language.

42
 Mathematical Language
& Symbols

Ideas regarding Mathematical sentence

• Mathematical Sentences have verbs and connectives
• Truth of Sentences

43
How to decide whether something is a
Sentence?
• Read it aloud, and ask yourself the question: Does it state a complete
thought? If YES, then it is a sentence.
• You may also ask yourself the question: Does it make sense to ask
about the truth of it?

44
 Mathematical Language
& Symbols

• Activity 2.1.docx

45
 Mathematical Language
& Symbols
The Grammar of Mathematics

It is the structural rules governing the use of

symbols representing mathematical objects
Express the following using mathematical
symbols
a. 5 is the square root of 25
b. 5 is less than 10
c. 5 is a prime number

46
 Mathematical Language
& Symbols

Some difficulties in math language

• The word "is" could mean equality, inequality or

membership in a set
• Different uses of a number; to express quantity
(cardinal), to indicate the order (ordinal), and as a
label (nominal)
• Mathematical objects may be represented in many
ways, such as sets and functions
• The words "and' & "or" means different from its
English use

47
 Mathematical Language
& Symbols

Objects that we use in Math

• Numbers (4 operations and properties)

• Variables (free and bound)
• Operations (unary & binary)
FOUR BASIC CONCEPTS:
• Sets (relationships, operations, properties)
• Relations (Equivalence relations)
• Functions ( injective, Surjective , Bijective)
• Binary Operations
48
 Mathematical Language
& Symbols
Numbers and 4 operations

Can you think of any more terms that you can add to
the mind map?
49
 Mathematical Language
& Symbols

Variable

A variable is any letter used to stand

for a mathematical object.

50
 Mathematical Language
& Symbols

Operations (Unary or Binary)

A Unary operation is an operation on a single

element.
Example: negative of 5
multiplicative inverse of 7
• A binary operation is an operation that
combines two elements of a set to give a
single element.
e.g. multiplication 3 x 4 = 12

51
 Mathematical Language
& Symbols
Sets

• Definition of a Set
• Methods of naming a set
• Properties
• Relationships between two sets
• Operation on Sets
• Venn Diagram

52
 Mathematical Language
& Symbols
Relations
• A relation is a correspondence between two things or
quantities. It is a set of ordered pairs such that the set
of all first coordinates of the ordered pairs is called
Domain and the set of all the second coordinates of
the ordered pairs is called Range.
• A relation maybe expressed a statement, arrow
diagram, table, equation, set-builder notation and
graph.
• Example: R= {(1, 2), (2, 4), (3, 6), (4, 8), (5, 10)}

53
 Mathematical Language
& Symbols

Types of Relations
1. one - to – one relation
2. one – to – many relation
3. many – to – one relation
An Equivalence Relation has the following properties:
i. Reflexive : 𝑥~𝑥
ii. Symmetric : If 𝑥~𝑦 , then y~𝑥.
iii. Transitive : If 𝑥~𝑦 & y~𝑧 , then 𝑥~𝑧.

Show that R = {(1,1), (1,3), (2,2), (3,1, (1,3)) is an

equivalence relation from a set A = {1, 2, 3}.

54
 Mathematical Language
& Symbols

Relations in Language of Math

Grammatical rules for the use of symbols
• To use < in a sentence, one should precede it by a noun and follow it
by a noun.
• Other examples of relations are “equals” and “ is an element of”
• It is important when specifying a relation to be careful about which
objects are to be related.

55
 Mathematical Language
& Symbols
Functions
A function is a relation such that each
element of the domain is paired with exactly one
element of the range. To denote this relationship,
we use the functional notation:
y = f(x)
where f indicates that a function exists between
variables x and y.

56
 Mathematical Language
& Symbols

The notation f : A → B is used to denote

a function which means that f is a function
with domain A and range B; f(x) = y means
that f transform x (which must be an element
of A) into y ( which must be an element of B)

57
 Mathematical Language
& Symbols

Evaluating Functions
The functional notation y = f(x) allows us to
denote specific values of a function. To evaluate
a function is to substitute the specified values of
the independent variable in the formula and
simplify.
Example:
When f(x) = 2x – 3, find f(2)
Solution:
f(2) = 2(2) – 3 = 4 – 3
f(2) = 1

58
 Mathematical Language
& Symbols

Inverse of a Function
The inverse of a function is another
function that that undoes it, and that it undoes.
For example, the function that takes a
number n to n – 5 is the inverse of the function
that takes n to n + 5.

What is the inverse of y = 2x?

59
 Mathematical Language
& Symbols

Binary Operations
A binary operation on a set A is a function
that takes pairs of elements of A and produces
elements of A from them.
We use the symbol * to denote arbitrary
binary operation on a set A.
Four Properties:
1. Commutative x* y = y *x
2. Associative x* (y*z) = (x*y)* z
3. Identity e*x = x *e
4. Inverse x*y = y*x = e

60
 Mathematical Language
& Symbols

EXERCISE
A. Describe the error
1. 5 is a subset of N
2. x > 2 or x <1 is equivalent to 2<x<1
3. Given the function x +10, find the value of f(4)
4. ‫ 𝑥 𝑒(׬‬+ 𝑥)
5. 22/7 = 3.14

61
 Mathematical Language
& Symbols

B. Translate each sentence using math symbols

1. 1/2 is a rational number.
2. x is a multiple of 7. (clarification, multiple does not
only include the positive multiples of 7)
3. x belongs to both sets A and B.
4. The values of n range from -3 to 8.
5. The square root of y is not more than 20.
6. The square root of a number x is non-negative.
7. The binary operation in x and y which is equal to 1
more than the product of x and y.

62
 Mathematical Language
& Symbols

Thought!
On the level of students being taught, don’t confine them only with
what they can.
As early, let them aware of the possibilities in the higher level.

63
Possible activity:
Video Watching
• Math isn't hard_ it's a language _ Randy Palisoc _
TEDxManhattanBeach.mp4

64
SOME ELEMENTARY LOGIC

65
Mathematical Logic
• It is a tool for working with complicated
compound statements. It includes:
• A language for expressing them.
• A concise notation for writing them.
• A methodology for objectively reasoning
about their truth or falsity.
•It is the foundation for expressing formal
proofs in all branches of mathematics

66
Statement or proposition
• Must express a complete thought
• A declarative statement with a definite meaning,
having a truth value that is true or false but not both
• A proposition (statement) may be denoted by a
variable like P, Q, R,…, called a proposition
(statement).
• Example:
R : University of Northern Philippines is in Vigan City.

Possible Exercise:
Determine whether a given sentence is a
67
proposition or not.
Logical Connectives
Logical Connective is a word or symbol
that joins two sentences to produce a new
one.
1. Conjunction
2. Disjunction
3. Implication
4. Bi-conditional
5. Negation
68
Logical Connectives

Name Connective Symbol

(key word)
⋀
Conjunction and
⋁
Disjunction or

Implication If... then… →

Biconditional …if and only if… ↔

69
TRUTH VALUES
Summary of truth values of compound statements
using logical connectives
P Q P ⋀Q P ⋁Q P → 𝑸 P ↔ 𝐐

T T T T T T
T F F T F F
F T F T T F
70
F F F F T T
IMPLICATION
• P is the antecedent or hypothesis
• Q is the consequent or conclusion
CONDITIONAL : P → Q
CONVERSE : Q → P
INVERSE : ¬P → ¬Q
CONTRAPOSITIVE : ¬Q → ¬P

71
Exercise 1
Symbolize the statement, using capital letters to abbreviate
the simple statements or propositions ( stated positively)
1. If Neil is not a big eater or Len has a big voice, then Jerry
likes violet.
State the premises first:
• N: Neil is a big eater
• L: Lena has a big voice
• J = Jerry likes violet
Answer (¬𝐍 ⋁ L) → 𝐉
2. A man should look for what he is, and not for what he
thinks should be (Albert Einstein).
• P: a man should look for what he is
• Q: a man should look for he thinks should be
Answer: P ^ ¬𝑸 72
Exercise 2:
Write the following in If-Then form
1. The product of two odd integers is an even integer.
Answer: If two odd integers are multiplied, then their
product is an even integer. (Take note that it is false.)
2. Every integer that is not odd is divisible by 2.
Answer: If an integer is not odd, then it is divisible by 2.
3. A function has an inverse if it is one-to-one.
Answer: If a function is one-to-one then it has an
inverse)

73
Exercise3:
Give the converse, inverse, and contrapositive of the
following conditional statements.
1. If you are more than 60 years old, then you are entitled
to a Senior Citizen's Card
Converse: If you are entitled to a SCC, then you are more
than 60 yrs old.
Inverse: If you are not more than 60 yrs old, then you are
not entitled to a SCC
Contrapositive: If you are not entitled to a SCC, then you
are not more than 60 yrs old.
74
Quantifiers

A constructs that specifies the

quantity of specimens in the domain of
discourse that satisfy a formula
KINDS:
• Universal Quantifier
• Existential Quantifier

75
UNIVERSALLY QUANTIFIED STATEMENT
Definition:
Let P be a propositional function with domain of discourse
D. The statement for all x, P(x) is said to be a UNIVERSALLY
QUANTIFIED STATEMENT .
The statement for all x, P(x) may be written as:
“∀𝒙, 𝑷(𝒙)".
The symbol ∀ means “for all” and is called the
universal quantifier.

∀𝒙, 𝑷(𝒙)" 𝐢𝐬 𝐓𝐫𝐮𝐞 𝐢𝐟 𝐏(𝐱) 𝐢𝐬 𝐭𝐫𝐮𝐞 𝐟𝐨𝐫 𝐞𝐯𝐞𝐫𝐲 𝐱 𝐢𝐧 𝐃.

𝐈𝐭 𝐢𝐬 𝐟𝐚𝐥𝐬𝐞 𝐢𝐟 𝐏 𝐱 𝐢𝐬 𝐅𝐚𝐥𝐬𝐞 𝐟𝐨𝐫 𝐚𝐭 𝐥𝐞𝐚𝐬𝐭 𝐨𝐧𝐞 𝐱 𝐢𝐧 𝐃. 76
EXAMPLE
1. ∀𝒙, 𝒙𝟐 ≥ 𝟎 , 𝒙 ∈ 𝑹

2. ∀𝒙, 𝒙𝟐 − 𝟏 ≥ 𝟎 , 𝒙 ∈ 𝒁+

3. ∀𝒙, 𝒙𝟐 − 𝟏 ≥ 𝟎 , 𝒙 ∈ 𝑹

4. All birds can fly.

5. Every student in the class wear

socks.

77
existentiaLLY QUANTIFIED STATEMENT
Definition:
Let P be a propositional function with domain of
discourse D. The statement there exists x, P(x) is said to
be EXISTENTIALLY QUANTIFIED STATEMENT .
The statement there exists x, P(x) may be written
as:
“∃𝒙, 𝑷(𝒙)".
The symbol ∃ means “there exists” and is called
the existential quantifier.

∃𝒙, 𝑷(𝒙)" 𝐢𝐬 𝐓𝐫𝐮𝐞 𝐢𝐟 𝐏(𝐱) 𝐢𝐬 𝐭𝐫𝐮𝐞 𝐟𝐨𝐫 𝐚𝐭 𝐥𝐞𝐚𝐬𝐭

𝐨𝐧𝐞 𝐱 𝐢𝐧 𝐃. 𝐈𝐭 𝐢𝐬 𝐟𝐚𝐥𝐬𝐞 𝐢𝐟 𝐏 𝐱 𝐢𝐬 𝐅𝐚𝐥𝐬𝐞 𝐟𝐨𝐫
𝐞𝐯𝐞𝐫𝐲 𝐱 𝐢𝐧 𝐃. 78
EXAMPLE
1. ∃𝒙, 𝟐𝒙 + 𝟏 = 𝟎 , 𝒙 ∈ 𝒁

𝒙
2. ∃𝒙, >𝟎 𝒙∈𝒁
𝒙𝟐 +𝟏

3. ∃𝒙, 𝒙𝟐 > 𝒙 , 𝒙 ∈ 𝒁−

4. ∃𝒙, 𝒙 > 𝟏 → 𝒙𝟐 = 𝒙 , 𝒙 ∈ 𝑹

5. There exists an elementary student who

can vote for the national election.
79
Multiple Quantifiers such as
∀𝒙∀𝒚 , ∃𝒙∃𝒚, ∀𝒙∃𝒚, etc … are said to be NESTED
QUANTIFIERS. These are propositional functions with
multiple quantifiers involving more than one variable.

Example:
• ∀𝑥 ∈ 𝑍 + , ∃𝑦 ∈ 𝑅, 𝑦 2 = 𝑥
For every positive integer x, there exists a real
number y such that y squared is equal to x. TRUE
• ∃𝑥, 𝑦 ∈ 𝑁, 𝑥 − 𝑦 = 𝑦 − 𝑥
There exist Natural numbers x and y such that x
- y = y - x. TRUE 80
NEGATION
Negation of mathematical statement P is
denoted by ¬P, read as “not P”.
If P is true, then ¬P is not true.

Example 1:
P: The trainees are sleepy.
¬P: The trainees are not sleepy.

Example 2:
Q: I have a new phone. 81

¬Q: I do not have a new phone.

TRY THESE!
Negate the following:
1. R: John will spend his Christmas
vacation in Singapore

2. Let A = {1, 3, 5, 7, 9, …}
S: Every number in the set A is odd.

3. T: Some math teachers knows how to

play tong –its. 82
NEGATION
Consider P: All math majors are male.
In symbolic notation:

∀𝑥, 𝑃(𝑥),
predicate: x is male
D: math majors
TRY TO NEGATE .
a. -P: It is false that all math majors are male.
b. -P: There is at least one math major who
is female.
Write in symbol 83

-P: ∃𝒙, −𝑷 𝒙
NEGATION OF QUANTIFIED STATEMENT
Consider P: Some teachers in CCIT know how to
run a computer program.
In symbolic notation:
∃𝑥, 𝑃(𝑥),
predicate: x know how to run a computer program
D: teachers in CCIT
TRY TO NEGATE
a. -P: It is false that some teachers in CCIT know how
to run a computer program.
b. -P: All teachers in CCIT do not know how to run
a computer program. 84
Write in symbol
-P: ∀𝒙, −𝑷 𝒙
Generalized De Morgan’s Laws for
Logic
If P is a propositional function, each
pair of propositions in (a) and (b) has the
same truth values (i.e.) either both are true
or both are false).

(a). ¬ ∀𝑥, 𝑃 𝑥 ≡ ∃𝑥, ¬𝑃 𝑥

(b). ¬ ∃𝑥, 𝑃 𝑥 ≡ ∀𝑥, ¬𝑃(𝑥)
85
Exercise
Let P(x) denote the statement “x is
attending new GE Course Training”. The domain
of discourse is the set of all math teachers in
SUCs & LUCs.
Write each proposition in words :
a. ∀𝑥, 𝑃 𝑥
b. ∀𝑥, ¬𝑃 𝑥
c. ∃𝑥, 𝑃 𝑥
d. ∃𝑥, ¬𝑃(𝑥)
Write the negation of a - d.
86
 GEOMETRIC PATTERNS
 depicts abstract shapes, like lines, polygons,
and circles
 are observed in nature and in arts
 nice to look at because of symmetry.
A pattern has symmetry if there is an
isometry of the plane that preserves
the pattern.

An isometry of the plane is a linear

transformation which preserves length.
Recognizing and Analyzing Geometric Shapes
• A geometric shape is defined as a geometric information that
still remains there even if scale, orientation, location and
reflection are displaced from a particular geometrical object.
We can say that if we move the shape, enlarge it , reflect it
or rotate it, then also the shape remains the same, i.e. it
does not change into another.
Two types of Geometric Shape
The geometric shapes (generally seen in everyday life) are of two types
two dimensional
 three dimensional.
Generally the two-dimensional geometric shapes are
represented by the lines joining the set of points called vertices in a
bounded form.
These are known as polygons including triangles,
quadrilaterals etc.
Some two-dimensional shapes formed by bounded curves, for
example - circle and ellipse.
Most of the three-dimensional geometric shapes are
represented by the lines joining a set of points as
well as two dimensional surfaces containing those
lines. For example - cubes, cuboids, pyramids etc.
Few three-dimensional shapes are formed by
bounded curved surfaces, such as sphere
and ellipsoid.
Transformations
Transformation maps an initial image, called
preimage, onto a final image, called an image.
Isometry
• It is a transformation in which the resulting image is congruent to the
pre-image. It is also called as RIGID TRANSFORMATION
• Which of the these transformations are isometries?
Four types of Rigid Transformation

• Translation  Rotation

Reflection

 Glide Reflection
Transformations using Coordinate Geometry
TRANSLATION
The example shows how
each vertex moves
the same distance in
the same direction.
Transformations using Coordinate Geometry

ROTATION
Observe the
transformation that turns
every point of a preimage
through a specified angle
and direction about a fixed
point
Transformations using Coordinate Geometry

REFLECTION
The example shows that
reflection along the x-axis
change the sign of the y-
coordinate.
Transformations using Coordinate Geometry

DILATION
Notice how EVERY
coordinate of the
original triangle has
been multiplied by
the scale factor
(x2).
Patterns and Diagrams
A pattern is said to be a design having a certain
discriminant regularity. A pattern that is drawn using
geometric shapes which are typically repeating.
A wallpaper is an ideal example of geometrical
pattern. These patterns are commonly seen in art as well
as in nature. Natural geometrical patterns may include
waves, cracks, spirals, foams etc. Actually, there is a
mathematical structure underlying in each geometrical
pattern.
SYMMETRIC PATTERNS
• Note: A plane figure has symmetry if there is a non-trivial
transformation that maps the figure onto itself. A trivial
transformation refers to the identity transformation
• Types of Symmetry:
1. Line symmetry/mirror symmetry/reflection symmetry
2. Rotational Symmetry.
1. Line symmetry/mirror
symmetry/reflection symmetry

 An object is reflected
across a line, like
looking in a mirror.
 A square has four line
symmetries.

101
2. Rotational symmetry

 Occurs when a figure is rotated less than

360o about a point so that the image
and the pre-image are indistinguishable

 A square has 4 rotational symmetries:

0o, 90o, 180o, 270o

102
Exercise:
List all symmetries present
in the following:

a. Isosceles triangle
b. Equilateral triangle
c. Rectangle
d. Regular hexagon
e. Regular pentagon
103
Answers:

Isosceles triangle Line symmetry

equilateral Line and rotational
rectangle Line and rotational
Regular hexagon Line and rotational
Regular pentagon Line and rotational

104
FRIEZE PATTERNS
 It is an infinitely long strip imprinted with a
design given by a repeating motif.

Note: Each frieze pattern is symmetric under a

translation in the direction of the strip.
A frieze pattern may also be symmetric:
a) About a horizontal reflection (H)
b) About a vertical reflection (V)
c) A rotation ( R ) of 180o about some point
d) A glide reflection (G)
e) Or a combination of the above
transformations.
105
Example: Can you identify the
transformation/s present in the following?

106
7 Frieze Symmetry Types

Symmetry Figure IUC

Type
T p111
TV pm11
TG p1a1
TR p112
THG p1m1
TVRG pma2
TVHRG pmm2 107
 IUC – INTERNATIONAL UNION OF CRYSTALLOGRAPHY

Observe that all the seven types begin with

p. P represents translation. As we have noted
before, each frieze pattern consists of
translation.
The remaining 3 characters are as follows:

 m if there is a vertical reflection, 1 if none

 m if there is a horizontal reflection; a if there
is a glide reflection, 1 if none
 2 if there is a 180o rotation, 1 if none 108
 Example: Can you name the frieze
pattern/s below?

1.

2.

109
3. TESSELLATION
• Basically, a tessellation is a way to tile a floor (that
goes on forever) with shapes so that there is no
overlapping and no gaps.

• A tessellation is possible only when the sum of

the interior angles of the polygons that are
tessellated is 360o .

• It can be created with translation, rotation and

reflection.

• It could be either regular or semi-regular

110
Regular tessellation is made from congruent
regular polygons joined side-to-side.

Can you guess which

of the polygons can be
used for regular
tessellation?

AMONG THE REGULAR

POLYGONS, only equilateral
triangle, square and regular
hexagon can be used for Regular
tessellation.
111
 A semi- regular
tessellation uses two or
more different regular
polygons with sides of the
same length in such a way
that all vertices are an example of semi-regular tessellation
identical. The numerical (4,8,8)
notation shown for these There are eight semi-
semi-regular tessellations regular tessellations in all.
Challenge:
represents the regular
a. Draw tessellation (3, 4, 6, 4)
polygon arrangement b. Find out the other 6 semi-
about each vertex. regular tessellations 112
8 Semi- regular tessellations
4, 8, 8

3, 4, 6, 4

Name or give the numerical notation of each…

113
Non-regular tessellation
 does not use regular polygons.
 Also called demiregular or polymorph

114
Dutch graphic artist M. C. Escher (1898-1972) is known for his creative use
of tessellations in his work. What transformations can you see in this
picture?

The birds and

fish have been
translated here.

115
What
transformations
can you see in this
Escher print?

Some birds have

been translated
and some have
been rotated.
116
More….

117
More….

118
More….

119
 WALLPAPER PATTERNS
These are patterns that cover the plane
and can be mapped onto itself by
translations in more than one direction.

120
Activity:
1. Using the first letter of your first
name, represent the 7 frieze
patterns.
2. On a ¼ sheet of illustration
board, create your own
tessellation of any type you
want.

121
A Sample for tessellation
Make a tessellation using a rotation
a. draw an equilateral triangle on a blank piece of paper and cut it out
b. draw trapezoid inside the right side of the triangle
c. rotate the trapezoid so you can copy the change on the side as indicated
d. repeat this pattern on a tessellation of equilateral triangles.

122
• SOFTWARE FOR CREATING DESIGNS USING ROTATION, REFLECTION
Examples:
KALEIDOMANIA
GEOGEBRA

123
DESIGNS, ARTS AND CULTURE
• Different patterns can be used to create different
geometric designs. When these designs are used
correctly, the designs can be visually effective and
functional.
• Patterns can be used to enhance artistic skills and
enrich one’s culture

124
Designs, arts, and culture
Geometric designs can be seen in the following:
Weaving
Lukay Art
Tile designs
Wallpaper designs
etc

125
Suggested activities for students
•Photo exhibit of geometric designs seen in
Philippine culture
•Portfolio of geometric designs
•Explore the campus, look for geometric designs,
prepare a report with photos, and present to
class

126
 THE MATHEMATICS
OF GRAPHS

Though this deals with graphs, it would not be a

course on discrete math so only the basic definitions
and algorithms are covered.
WHY STUDY GRAPH?

Graphs are excellent modeling tools.

It leads to applications to networking, scheduling, map

coloring and other fields.
THE KONIGSBERG BRIDGE PROBLEM
• Is it possible to start a walk at any point and cross each bridge
exactly once, without retracing your steps?
Many citizens of the time attempted to take a stroll
that would lead them across each bridge and return
them to the starting point without traversing the same
bridge twice. None of them could do it, no matter
where they chose to start.

Try it for yourself with pencil and paper. You will see
that it is not easy!
In solving the puzzle, we look for entry
points and exit points. Once we moved in
then there must be an exit point if not
then we say we cannot traverse the path
that we have selected.
See if you can find a way to trace the shape without
lifting your pen and without tracing over the same
segment.
• Euler proved that networks can be traced if one of the
following conditions is met:
a. There are only even vertices in the figure.
b. There are exactly two odd vertices in the figure.
Think of all the various connections we experience in our
lives—friends are connected on Facebook, cities are
connected by roads, computers are connected across the
Internet. We usually say that we have networks and draw
diagrams.

A branch of mathematics called graph theory illustrates and

analyzes connections such as these.
Preliminaries
• GRAPHS is a set of points called vertices and line
segments or curves called edges.
• Edges connect two vertices.
• Edges only intersect at vertices.
• Edges joining a vertex to itself are called loops.
• The degree of a vertex is the number of edges that intersect
that vertex.
• An odd vertex is defined as one that has an odd number of
arcs (line segments) that come to that point.
• An even vertex has an even number of arcs.
• Adjacent vertices have at least one edge connecting them.
• A path on a graph is a sequence of adjacent vertices and the
edges connecting them that uses no edge more than once.
Graphs can be presented in many scenarios.
Constructing a graph
The following table lists five students at a college. An “X” indicates that
the two students participate in the same study group this semester.
a. Draw a graph that represents this information where each
vertex represents a student and an edge connects two vertices
if the corresponding students study together.
b. Use your graph to answer the following questions: Which
student is involved in the most study groups with the others?
Which student has only one study group in common with the
others? How many study groups does Laura have in common
with the others?
Solution:
a. We draw five vertices (in any configuration we wish) to represent
the five students, and connect vertices with edges according to the
table.
 Answer to b
 The vertex corresponding to Amber is connected to more
edges than the others so she is involved with more study
groups (three) than the others.
Kayla is the only student with one study group in common,
as her vertex is the only one connected to just one edge.
Laura’s vertex is connected to two edges, so she shares two
study groups with others.
We could represent the graph in different ways by
having the positions of the individuals vary.

Show one on the board.

One graph may be drawn in (infinitely) many
ways, but it always provides us with the same
information.

Graphs are structures for describing relationships

between objects of interest.
Some Applications
• Transactions
• Routes
• Work distribution
• Networks
• Maps
• Floor plans
• Offices and functions
Graphs can represent many different scenarios such as:
Computer network of a small business
Flights available on a particular airline between
selected cities
Game match in a particular sports
Etc.
 Terminologies
 A loop is an edge connecting a vertex to
itself.
 If two edges are connected by more than
one edge, the edges are called multiple
edges. The graph is called a multigraph.
A graph with no loops and no multiple
edges is called a simple graph.
Graph with vertices but no edges is called
a Null Graph.
Identify the nature of the following graphs.
Equivalent Graphs

The edges form the same connections of vertices in each graph.

Determine whether the following two graphs
are equivalent.
SOLUTION
• Despite the fact that the two graphs have different
arrangements of vertices and edges, they are
equivalent. To illustrate, we examine the edges of
each graph. The first graph contains six edges; we can
list them by indicating which two vertices they
connect. The edges are AC, AE, BD, BE, CE, and DE. If
we do the same for the second graph, we get the
same six edges. Because the two graphs represent the
same connections among the vertices, they are
equivalent.
Determine whether the following two graphs
are equivalent.
 Euler Circuits
Terminologies
A path in a graph can be thought of as a movement from
one vertex to another by traversing edges.
If a path ends at the same vertex at which it started, it is
considered a closed path, or circuit.
A graph is said to be connected if for any two vertices,
there is at least one path that connects them.
If a graph is not connected ‘ then it is disconnected.
A bridge on a connected graph is an edge that, if removed,
makes the graph disconnected.
Definition
• A circuit that uses every edge, but never uses the same edge
twice, is called an Euler circuit.

The path B–D–F–G–H–E–C–B–A–D–G–E–B in Figure shown

above is an Euler circuit.
 Eulerian Graph Theorem

A connected graph is Eulerian if and only if every

vertex of the graph is of even degree.
Which of the following graph has an
Euler Circuit?
Exercise
• Determine whether the graph shown below is Eulerian. If it is, find an
Euler circuit. If it is not, explain how you know. The number beside
each vertex indicates the degree of the vertex.
Application

A subway map shows the tracks that subway trains

traverse as well as the junctions where one can switch
trains. Suppose an inspector needs to travel the full
length of each track. Is it possible to plan a journey that
traverses the tracks and returns to the starting point
without traveling through any portion of a track more
than once?
EULER PATHS
Euler Path Theorem
• For any connected graph:
1. If all vertices are even, the graph has at least one Euler circuit (which
is by definition also an Euler path). An Euler circuit can start at any
vertex.
2. If exactly two vertices are odd, the graph has no Euler circuits but at
least one Euler path. The path must begin at one odd vertex and end
at the other odd vertex.
3. If there are more than two odd vertices, the graph has no Euler paths
and no Euler circuits.
Application of Euler Path
A photographer would like to travel across all of the roads shown on
the following map. The photographer will rent a car that need not be
returned to the same city, so the trip can begin in any city.

Is it possible for the photographer to design a trip that traverses all of

the roads exactly once?
The floor plan of an art gallery is pictured below. Draw a graph that
represents the floor plan, where vertices correspond to rooms and
edges correspond to doorways. Is it possible to take a stroll that passes
through every doorway without going through the same doorway
twice? If so, does it matter whether we return to the starting point?
HAMILTONIAN CIRCUITS
• A path on a connected graph that passes through
every vertex exactly once is called a Hamiltonian
path. A Hamiltonian path that begins and ends at the
same vertex, but passes through all vertices exactly
once is called a Hamiltonian circuit
Complete Graphs and Hamiltonian Circuits
Complete Graphs are graphs in which every possible
edge is drawn between vertices.

Every complete graph (without any multiple edges)

with more than two vertices has a Hamiltonian
circuit. Furthermore, the number of Hamiltonian
circuits in a complete graph with n vertices is (n – 1)!
 DIRAC’S THEOREM
Consider a connected graph with at
least three vertices and no multiple
edges. Let n be the number of
vertices in the graph. If every vertex
has degree of at least n/2, then the
graph must be Hamiltonian.
Example
The graph below shows the available flights of a popular airline. Apply
Dirac’s theorem to verify that the following graph is Hamiltonian. Then
find a Hamiltonian circuit. What does the Hamiltonian circuit represent
in terms of flights?
 A large firm has offices in seven major cities. The firm has
overnight document deliveries scheduled every day between certain
offices. In the graph below, an edge between vertices indicates that
there is delivery service between the corresponding offices.
Use Dirac’s theorem to answer the following question: Using the
law firm’s existing delivery service, is it possible to route a document to
all the offices and return the document to its originating office without
sending it through the same office twice?
WEIGHTED GRAPHS
A weighted graph is a graph in which each edge is
associated with a value, called a weight. The value can
represent any quantity we desire.
Find Hamiltonian Circuits in a Weighted Graph
• The various options will be simpler to analyze if we fi rst organize the
information in a graph. Begin by letting each city be represented by a
vertex. Draw an edge between two vertices if there is a flight between
the corresponding cities, and label each edge with a weight that
represents the number of miles between the two cities.
Solution
• A route that visits each city just once corresponds to a Hamiltonian
circuit. Beginning at Chicago, one such circuit is Chicago–New York–
Dallas–Philadelphia–Atlanta–Washington, D.C.–Chicago. By adding
the weights of each edge in the circuit, we see that the total number
of miles traveled is 713 + 1374 + 1299 + 670 + 544 + 597 = 5197
• By trial and error, we can identify two additional routes. One is
Chicago–Philadelphia–Dallas–Washington, D.C.–Atlanta–New York–
Chicago. The total weight of the circuit is
665 + 1299 + 1185 + 544 + 748 + 713 = 5154
• A third route is Chicago–Washington, D.C.–Dallas–New York–Atlanta–
Philadelphia–Chicago. The total mileage is
597 + 1185 + 1374 + 748 + 670 + 665 = 5239
Is there a way we can find the very best
route to take?

Unfortunately, there is no known shortcut

for finding the optimal Hamiltonian circuit in
a weighted graph.
Algorithms in Complete Graph

Complete Graphs are graphs in which every possible edge is drawn between
vertices (without any multiple edges).

ALGORITHMS
1. The nearest neighbor algorithm
2. The edge-picking algorithm

The circuits found by the algorithms are not guaranteed to have the
smallest total weight possible, but they are often better than using the trial
and error method.
1.The Nearest Neighbor Algorithm
The Nearest Neighbor Algorithm
Choose a vertex to start at, then travel along the connected edge
that is nearest to it. (If two or more edges have the same weight, pick
any one.)
After arriving at the next vertex, travel along the edge which is
nearest that connects to a vertex not yet visited. Continue this
process until you have visited all vertices.
 Return to the starting vertex.
Example:
• Use the nearest neighbor algorithm to find a Hamiltonian circuit in
the weighted graph shown. Start at vertex A.
Solution
• Begin at A. The weights of the edges from A are 13, 5, 4, 15, and 8,
The smallest is 4. Connect A to D.
• At D, the edge with the smallest weight is DB. Connect D to B.
• At B, the edge with the smallest weight is BF. Connect B to F.
• At F, the edge with the smallest weight, 7, is FD. However, D has
already been visited. Choose the next smallest weight, edge FE.
Connect F to E.
• At E, the edge with the smallest weight whose vertex has not been
visited is C. Connect E to C.
• All vertices have been visited, so we are at step 3 of the algorithm.
We return to the starting vertex by connecting C to A.
Example
Use the greedy algorithm to find a Hamiltonian circuit starting at vertex
A in the weighted graph shown.
2. The Edge-Picking Algorithm
1. Mark the edge of smallest weight in the graph. (If two or
more edges have the same weight, pick any one.)
2. Mark the edge of next smallest weight in the graph, as long
as it does not complete a circuit and does not add a third
marked edge to a single vertex.
3. Continue this process until you can no longer mark any
edges. Then mark the final edge that completes the
Hamiltonian circuit.
Example
Use the edge-picking algorithm to find a Hamiltonian circuit of the
previous graph.
Solution
• We first highlight the edge of smallest weight, namely BD with weight 2.
• The edge of next smallest weight is AD with weight 4.
• The next smallest weight is 5, which appears twice, with edges AE and
FB. We can mark both of them.
• There are two edges of weight 6 (the next smallest weight), BC and EC.
We cannot use BC because it would add a third marked edge to vertex
B. We mark edge EC.
• We are now at step 3 of the algorithm; any edge we mark will either
complete a circuit or add a third edge to a vertex. So we mark the final
edge to complete the Hamiltonian circuit, edge FC.
• Beginning at vertex A, the Hamiltonian circuit is A–D–B–F–C–E–A. (In
the reverse direction, an equivalent circuit is A–E–C–F–B–D–A.) The
total weight of the circuit is
4 + 2 + 5 + 14 + 6 + 5 = 36
EXERCISE
Susan needs to mail a package at the post office, pick up several items
at the grocery store, return a rented video, and make a deposit at her
bank. The estimated driving time, in minutes, between each of these
locations is given in the table below. Use both of the algorithms to
design routes for Susan to follow that will help minimize her total
driving time. Assume she must start from home and return home when
her errands are done.
Planarity and the Euler’s Formula
Planar Graph

A planar graph is a graph that can be drawn so that no

edges intersect each other (except at vertices).
Is this a planar drawing of a graph?
Is the graph planar?
Show that the graphs below are planar or not
planar
Subgraph Theorem
• If a graph G has a subgraph that is not planar, then G is also
not planar. In particular, if G contains the Utilities Graph or
K5 as a subgraph, G is not planar.

Nonplanar Graph Theorem

A graph is nonplanar if and only if it has the Utilities
Graph or K5 as a subgraph, or
it has a subgraph that can be contracted to the Utilities
Graph or K5.
Utilities Graph
EULER’s FORMULA
• In a connected planar graph drawn with no intersecting edges, let v
be the number of vertices, e the number of edges, and f the number
of faces. Then v + f = e + 2.
Verify the Euler’s Formula
The Five Regular Convex Polyhedra
• A regular polyhedron is a three-dimensional object in
which all faces are identical. Specifically, each face is a
regular polygon (meaning that each edge has the same
length and each angle has the same measure). In
addition, the same number of faces must meet at each
vertex, or corner, of the object. Here we will discuss
convex polyhedra, which means that any line joining
one vertex to another is entirely contained within the
object. (In other words, there are no indentations.)
• It was proved long ago that only five objects fi t this
description—the tetrahedron, the cube, the
octahedron, the dodecahedron, and the icosahedron.
One way mathematicians determined that there were
only five such polyhedral was to visualize these three-
dimensional objects in a two-dimensional way.
• The tetrahedron consists of four faces,
each of which is an equilateral
triangle.

• Draw the graph that results from a

projection of the tetrahedron.
Possible Exercises
1. Show the planar graphs for each platonic solid.
2. Verify the Euler’s formula for each of these.
GRAPH COLORING
In the mid-1800s, Francis Guthrie was trying to color a map of
the counties of England. So that it would be easy to
distinguish the counties, he wanted counties sharing a
common border to have different colors. After several
attempts, he noticed that four colors were required to color
the map, but not more. This observation became known as
the four-color problem.
•There is a connection between
coloring maps and graph theory.
This connection has many
practical applications, from
scheduling tasks, to designing
computers, to playing Sudoku.
Our map-coloring question then becomes:
1. Can we give each vertex of the graph a color such
that no two vertices connected by an edge share the
same color?
2. How many different colors will be required?
Color the fictitious map.
The graph is actually 3-colorable; only three colors are necessary.
Four-Color Theorem
Every planar graph is 4-colorable.

• The graph shown at the right

requires five colors if we wish to
color it such that no edge joins
two vertices of the same color.
Does this contradict the four-color
theorem?
Using a Graph to Color a Map
The fictional map below shows the boundaries of countries on a
rectangular continent. Represent the map as a graph, and find a
coloring of the graph using the fewest possible number of colors. Then
color the map according to the graph coloring.
Exercise
Represent the fictional map of countries below as a graph, and
determine whether the graph is 2-colorable, 3-colorable, or 4-colorable
by finding a suitable coloring of the graph. Then color the map
according to the graph coloring.
The Chromatic Number of a Graph
The minimum number of colors needed
to color a graph so that no edge
connects vertices of the same color is
called the chromatic number of the
graph.
2-Colorable Graph Theorem

A graph is 2-colorable if
and only if it has no circuits
that consist of an odd
number of vertices.
Find the chromatic number

Thus the Utilities Graph has a chromatic number of 2.

Determine whether the given graph below is
2-colorable.
A Scheduling Application of Graph Coloring
• Eight different school clubs want to schedule meetings on the last day
of the semester. Some club members, however, belong to more than
one of these clubs, so clubs that share members cannot meet at the
same time. How many different time slots are required so that all
members can attend all meetings? Clubs that have a member in
common are indicated with an “X” in the table .
Solution
We can represent the given information by a graph. Each club is
represented by a vertex, and an edge connects two vertices if the
corresponding clubs have at least one common member.
• Each color corresponds to a time slot, so one
scheduling is
First time slot: ski club, debate club, student newspaper
Second time slot: student government, community
outreach
Third time slot: honor society, campus Democrats,
campus Republicans
 TREES
A tree is a graph in which any two vertices are connected by exactly
one path.
PROPERTIES OF TREES
1. A tree has no circuits.
2. Trees are connected graphs.
3. Every edge of a tree is a bridge.
4. A tree with n vertices has exactly n-1 edges.
SPANNING TREES
A spanning tree for a graph is a tree that results from
the removal of as many edges as possible from the
original graph without making it disconnected.

A minimum spanning tree for a weighted graph is the

spanning tree for that graph that has the smallest
possible sum of the weights.
KRUSKAL’S ALGORITHM
To construct a minimum spanning tree for a weighted graph:
Step 1. Choose the edge with the lowest weight and highlight
it in color.
Step 2. Choose the unmarked edge with the next lowest
weight that does not form a circuit with the edges already
highlighted, and highlight it.
Step 3. Repeat until all vertices have been connected.
Note: 1. If more than one edge could be chosen at any stage pic one
randomly.
2. The number of steps in any given problem depends on how
many edges need to be removed.
A flower farm has five greenhouses that need an irrigation system.
The distances in meters between each of the greenhouses are shown
below. Use a minimum spanning tree to connect the greenhouses and
find the minimum amount of pipe needed.
CAUTION
In any application problem involving a weighted graph,
make sure you think carefully about what solves the
problem: a minimal spanning tree or a Hamiltonian
circuit. In many cases, spanning tree problems are
about connecting locations, while Hamiltonian circuit
problems are about traveling between locations and
returning to a starting point.
MATHEMATICAL SYSTEMS
Contents

• Modulo Arithmetic

• Application

• Cryptography
A. Modulo Arithmetic

In mathematics, modular arithmetic (sometimes called clock

arithmetic) is a system of arithmetic for integers, where numbers wrap
around after they reach a certain value – the modulus.

There are 24 Hours in a Day,

however, time is divided to
two twelve hour periods.
Example:
22 Hours is 12 + 10, So it is Ten O'clock!
Modulo Arithmetic
The Swiss mathematician Leonhard Euler
pioneered the modern approach to
congruence in 1750, when he explicitly
introduced the idea of congruence modulo
of a number N.

Modular arithmetic was further

advanced by Carl Friedrich Gauss in his
book published in 1801.
• Modulo n
Two integers a and b are said to be congruent modulo n, where n is a
natural number,
𝑎 −𝑏
if 𝑛

is an integer. In this case, we write 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛. The number n is

called the modulus. The statement 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛 is called a
congruence.
Now suppose today is Friday. To determine the day of the week 16 days
from now, we observe that 14 days from now the day will be Friday, so
16 days from now the day will be Sunday. Note that the remainder
when 16 is divided by 7 is 2, or, using modular notation, 16 ≡ 2𝑚𝑜𝑑7.
The 2 signifies 2 days after Friday, which is Sunday.

July 4, 2010, was a Sunday. What day of the week is July 4, 2018?
Modulo Operations
The notion of modular arithmetic is related to that of the remainder in
division. The operation of finding the remainder is sometimes referred
to as the modulo operation.

We define Zn as the set of integers from 0,1,2,…,n-1 modulo n, i.e.

Zn = {0, 1, 2, …, n-1}
Note that Zn has exactly n nonnegative integers. In particular, we define
Zn with the following set of positive integers:

Z3 = {0, 1, 2}, modulo 3

Z5 = {0, 1, 2, 3, 4}, modulo 5
Z8 = {0, 1, 2, 3, 4, 5, 6, 7}, modulo 8

Zn contains the remainder r when an integer 𝑎∈ ℤ is divided by n;

where r < n and r ≥ 0.
Arithmetic modulo n
Arithmetic modulo n, where n is a natural number, uses a
variation of the standard rules of arithmetic we have used
before. Perform the arithmetic operation and then divide by
the modulus. The answer is the remainder. Thus the result of
an arithmetic operation mod n is always a whole number less
than n.
Addition Modulo n

Evaluate: (23 + 38) mod 12

Solution
Add 23 and 38 to produce 61. Then divide by the modulus, 12. The
answer is the remainder.

61
= 5 𝑟𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟 1
12

The answer is 1.
Subtraction Modulo n

• Evaluate each of the following.

a. (33 – 16) mod 6 b. (14 – 27) mod 5
Solution
a. Subtract: 33 - 16 = 17. The result is positive. Divide the difference by
the modulus, 6. The answer is the remainder. Five is the remainder.
Therefore: 33 − 16 𝑚𝑜𝑑6 ≡ 5
Subtract: 14 - 27 = -13. Because the answer is negative, we must find x
so that −13 ≡ 𝑥𝑚𝑜𝑑5. Thus we must find x so that the value of
−13 − 𝑥 −(13 + 𝑥)
=
5 5
is an integer. Trying the whole number values of x less than 5, the
modulus, we find
−(13+2) 15
that when x = 2, = −5 = −3. And 5 – 3 = 2
5
Thus, 14 − 27 𝑚𝑜𝑑 5 ≡ 2
Multiplication Modulo n

Evaluate: 15 ∙ 23 𝑚𝑜𝑑11

Solution
Find the product of 15 and 23 and then divide by the modulus, 11. The
answer is the remainder.
15 ∙ 23 345
= = 31 𝑟𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟 4.
11 11

Thus 15 ∙ 23 𝑚𝑜𝑑11 ≡ 4
Solving Congruence Equations
• Solving a congruence equation means finding all whole number
values of the variable for which the congruence is true.
• For example, to solve (3𝑥 − 5) ≡ 3𝑚𝑜𝑑4, we search for whole
number values of x for which the congruence is true.
Thus: If we continued trying values,
we would find that 10 and 14
are also solutions. Note that
the solutions 6, 10, and 14 are
all congruent to 2 modulo 4. In
general, once a solution is
determined, additional
solutions can be found by
repeatedly adding the modulus
to the original solution.
Modular division can be performed by considering the related
multiplication problem.
For instance, if 5 ÷ 7 = 𝑥, then 𝑥 ∙ 7 = 5
Similarly, the quotient: 5 ÷ 7 𝑚𝑜𝑑8 is the solution to the congruence
equation 𝑥 ∙ 7 ≡ 5𝑚𝑜𝑑8, which is 3.
Exercise
Perform the modular arithmetic.
a) (9 + 15) mod 7 b) (12 + 8) mod 5 c) (5 + 22) mod 8
d) (19 – 6) mod 5 e) (25 – 10) mod 4 f) (48 – 21) mod 6
g) (6 ∙ 8) mod 9 h) (5 ∙ 12) mod 4 i) (9 ∙ 15) mod 8
j) (4 ÷ 5) mod 8 k) (6 ÷ 4) mod 9 l) (2 ÷ 3) mod 5
 Applications of Modular Arithmetic
• ISBN and UPC
• Every book that is cataloged in the Library of Congress must have an
ISBN (International Standard Book Number). This 13-digit number
was created to help ensure that orders for books are filled accurately
and that books are catalogued correctly.
• The first three digits of an ISBN are 978, the next digit indicates the
country in which the publisher is incorporated (0, and sometimes 1,
for books written in English), the next two to seven digits indicate the
publisher, the next group of digits indicates the title of thebook, and
the last digit (the 13th one) is called a check digit.
• If we label the first digit of an ISBN d1, the second digit d2, and so on
to the 13th digit d13, then the check digit is chosen to satisfy the
following congruence.

• Formula for the ISBN Check Digit

d13 ≡ 10 – (d1 + 3d2 + d3 + 3d4 + d5 + 3d6 + d7 + 3d8 + d9 + 3d10 + d11 + 3d12) mod 10

If d13 = 10, then the check digit is 0.

• It is this check digit that is used to ensure accuracy. For instance, the
ISBN for the fourth edition of the American Heritage Dictionary is
978-0-395-82517-4. Suppose, however, that a bookstore clerk sends
an order for the American Heritage Dictionary and inadvertently
enters the number 978-0-395-28517-4, where the clerk transposed
the 8 and 2 in the five numbers that identify the book.
Correct ISBN: 978-0-395-82517-4
Incorrect ISBN: 978-0-395-28517-4
The receiving clerk calculates the check digit.
(Determine the check digit for the book)
• Another coding scheme that is closely related to the ISBN is the UPC
(Universal Product Code). This number is placed on many items and is
particularly useful in grocery stores.
Credit Card Numbers
• Companies that issue credit cards also use modular arithmetic to
determine whether a credit card number is valid. This is especially
important in e-commerce, where credit card information is
frequently sent over the Internet. The primary coding method is
based on the Luhn algorithm, which uses mod 10 arithmetic.
• Credit card numbers are normally 13 to 16 digits long. The first
one to four digits are used to identify the card issuer. The table
below shows the identification prefixes used by four popular card
issuers.
• The Luhn algorithm, used to determine whether a credit card
number is valid, is calculated as follows: Beginning with the
next-to-last digit (the last digit is the check digit) and reading
from right to left, double every other digit. If a digit becomes
a two-digit number after being doubled, treat the number as
two individual digits. Now find the sum of the new list of
digits; the final sum must equal 0 mod 10. The Luhn
algorithm is demonstrated in the next example.
Cryptology
• Related to codes on books and grocery items are secret
codes. These codes are used to send messages between
people, companies, or nations. It is hoped that by devising a
code that is difficult to break, the sender can prevent the
communication from being read if it is intercepted by an
unauthorized person. Cryptology is the study of making and
breaking secret codes.
Use the cyclical alphabetic encrypting code
that shifts each letter 11 positions to

a. code CATHERINE THE GREAT.

b. decode TGLY ESP EPCCTMWP.
Apportionment
• A method 0f dividing a whole into various parts

• Has its roots in the US Constitution

• Main question: How many voters must be represented by each member of the House of Representatives?

• Equivalently, how representatives must each state send to the House based on its population?
• Since 1790, when the House of Representatives
first attempted to apportion itself, various
methods have been used to decide how many
voters would be represented by each member of
the House. The two competing plans in 1790 were
put forward by Alexander Hamilton and Thomas
Jefferson.
 History
• 1790 – 1830: The Jefferson Plan (Thomas Jefferson)
• 1840 : Webster’s Method (Daniel Webster)
• 1850 – 1900: The Hamilton Plan (Alexander Hamilton)
• 1910 : Webster’s Method
• 1920 : No apportionment
• 1930 : Webster’s Method
• 1940 – present Huntington-Hill Method (Joseph Hill/Edward
Huntington)
• To illustrate how the
Hamilton and Jefferson
plans were used to
calculate the number of
representatives each state
should have, we will
consider the fictitious
country of Andromeda,
with a population of
20,000 and five states. The
population of each state is
given in the table at the
right. Andromeda’s
constitution calls for 25
representatives to be
chosen from these states.
 The Hamiltonian plan
• Under the Hamilton plan, the total population of
the country (20,000) is divided by the number of
representatives (25). This gives the number of
citizens represented by each representative. This
number is called the standard divisor.
The standard divisor and
standard quota
apportionment
 The total number of representatives
is 22, not 25 as required by
Andromeda’s constitution.
When this happens, the Hamilton plan calls for
revisiting the calculation of the quotients and
assigning an additional representative to the
state with the largest decimal remainder. This
process is continued until the number of
representatives equals the number required by
the constitution.
 JEFFERSON PLAN
The Jefferson plan attempts to
overcome this difficulty by using a
modified standard divisor. This number
is chosen, by trial and error,
so that the sum of the standard quotas is
equal to the total number of
representatives. In a specific
apportionment calculation, there may be
more than one number that can serve as
the modified standard divisor.
Suppose the 18 members on the
board of the Ruben County
Environmental Agency are
selected according to the
populations of the five cities in
the county, as shown in the table
at the right.
a. Use the Hamilton method to
determine the number of board
members each city
should have.
b. Use the Jefferson method to
determine the number of board
members each city
should have.
Solution
a. First find the total population of the cities.
7020 + 2430 + 1540 + 3720 + 5290 = 20,000

Now calculate the standard divisor.

𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝑐𝑖𝑡𝑖𝑒𝑠
𝑆𝑡𝑎𝑛𝑑𝑎𝑟𝑑 𝑑𝑖𝑣𝑖𝑠𝑜𝑟 =
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑏𝑜𝑎𝑟𝑑 𝑚𝑒𝑚𝑏𝑒𝑟𝑠
20,000
= ≈ 1111.11
18
Use the standard divisor to find the standard quota for
each city.
To use the Jefferson method, we must
find a modified standard divisor that is
less than the standard divisor we
calculated in part a. We must do this by
trial and error.
For instance, if we choose 925 as the
modified standard divisor, we have the
following result.
This result yields too many board members. Thus we must increase the modified
standard divisor. By experimenting with different divisors, we find that 950 gives
the correct number of board members.
TRY THIS!
Suppose the 20 members of a
committee from five European
countries are selected
according to the populations of
the five countries, as shown in
the table at the left.
a. Use the Hamilton method to
determine the number of
representatives each country
should have.
b. Use the Jefferson method to
determine the number of
representatives each country
should have.
 Fairness in Apportionment
The choice of apportionment method affects the number of
representatives a state will have. Given that fact,
mathematicians and others have tried to work out an
apportionment method that is fair. The difficulty lies in trying to
define what is fair.
One criterion of fairness for an apportionment plan
is that it should satisfy the quota rule.

Quota Rule
The number of representatives apportioned to a
state is the standard quota or one
more than the standard quota.
We can show that the Jefferson plan, for instance, does
not always satisfy the quota rule by calculating the
standard quota of Apus.
11123
𝑆𝑡𝑎𝑛𝑑𝑎𝑟𝑑 𝑞𝑢𝑜𝑡𝑎 = ≈ 13
800

The standard quota of Apus is 13. However, the

Jefferson plan assigns 15 representatives to that state ,
two more than its standard quota. Therefore, the
Jefferson method violates the quota rule.
Another measure of fairness is average
constituency. This is the population of a state
divided by the number of representatives from
the state and then rounded to the nearest
whole number.

𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝑎 𝑠𝑡𝑎𝑡𝑒
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑐𝑜𝑛𝑠𝑡𝑖𝑡𝑢𝑒𝑛𝑐𝑦 =
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑟𝑒𝑝𝑟𝑒𝑠𝑒𝑛𝑡𝑎𝑡𝑖𝑣𝑒𝑠 𝑓𝑟𝑜𝑚 𝑡ℎ𝑒 𝑠𝑡𝑎𝑡𝑒
Absolute Unfairness of an Apportionment
The absolute unfairness of an apportionment is
the absolute value of the difference between the
average constituency of state A and the average
constituency of state B.

|Average constituency of A| - |Average constituency of B|

 Consider the two states Hampton and Shasta in
the table below.

Because the average constituencies are approximately

equal, it seems natural to say that both states are
equally represented.
Now suppose that one representative will be added
to one of the states. Which state is more deserving
of the new representative? In other words, to be fair,
which state should receive the new representative?

The changes in the average constituency are shown

below.
From the table, there are two possibilities for
adding one representative. If Hampton receives the
representative, its average constituency will be
1455 and Shasta’s will remain at 1668. The
difference in the average constituencies is 1668 -
1455 = 213. This difference is called the absolute
unfairness of the apportionment.

If Shasta receives the representative, its average

constituency will be 1390 and Hampton’s will
remain at 1600. The absolute unfairness of
apportionment is 1600 - 1390 = 210.
Because the smaller absolute unfairness of
apportionment occurs if Shasta receives the new
representative, it might seem that Shasta should receive
the representative. However, this is not necessarily true.
A similar process is used when deciding which state should
receive another representative. Rather than look at the
difference in the absolute unfairness of apportionment, we
determine the relative unfairness of adding the representative.

The relative unfairness of an apportionment is the quotient of

the absolute unfairness of the apportionment and the average
constituency of the state receiving the new representative.
Absolute unfairness of the apportionment
Average constituency of the state receiving the new representative
Compare the relative unfairness
between Hampton and Shasta.
OTHER METHODS OF
APPORTIONMENT
• Adam’s Method of Apportionment
• Webster’s Method of Apportionment
• Huntington-Hill Apportionment Method
Basic Terminology

• Standard Divisor (D) – the number of voters

represented by each representative
total population
D=
number of representatives
• Standard Quota (Q) – the quotient when the
population of a sub-group is divided by the
standard divisor
sub−group population
Q= D
It is customary to round the standard quota
two decimal places.
Adam’s Method of
Apportionment
• If the sum of the UPPER QUOTAS does not equal the
correct number of representatives Use a modified
standard divisor 𝑫𝒎 that yields the correct number of
representatives by trial and error.
• Note that Dm > D
• Choose 𝐷𝑚 such that the sum of the UPPER QUOTAS
equals the number of representatives
Webster’s Method of Apportionment
• A variation of the Jefferson plan and Adam’s method
• Instead of using the LOWER QUOTA or the UPPER QUOTA, use
the regular rules of rounding to determine the REGULAR
QUOTA (R).
• Use a modified standard divisor 𝑫𝒎 that yields the correct
number of representatives by trial and error.
• Note that Dm > D or Dm < D
• Choose 𝐷𝑚 such that the sum of the REGULAR QUOTAS equals
the number of representatives
Huntington-Hill Apportionment Method
• Calculate the standard quota, lower quotas and upper
quotas of each sub-group.
• Calculate the geometric mean (rounded to 2 decimal
places) of each sub-group’s lower quota and upper quota.
• If the standard quota is less than the geometric mean, round
the quota down.
• If the standard quota is greater than or equal to the geometric
mean, round the quota up.
• If the sum of the rounded standard quotas equals the
number of representatives, you are done. Otherwise,
choose a modified standard divisor and calculate the
modified quotas and rounded modified quotas. Repeat
this process until the required number is achieved.
Ex.
A total of 25 teacher aides are to be apportioned
among 7 classes at a new elem. School. The enrollment in
each of the 7 classes is shown in the following table. Find the
std. divisor and the std. quota of each class. Give the lower
quota and the upper quota of each class.
 Class No. of Q L U
Students
Kindergarte 38/8.96 4.24 4 5
n
First Grade 39 4.35 4 5
2nd Grade 35 3.91 3 4
3rd Grade 27 3.01 3 4
4th Grade 21 2.34 2 3
5th Grade 31 3.46 3 4
6th Grade 33 3.68 3 4
Total 224 22 29
Solution
224
D= = 8.96
25
Where D¬ standard divisor
Adam’s Plan
Class No. Ham Dm = 7.8 Dm = 9.8 Dm = 10 10.3 10.5
K 38 4 4 4 4 4 4
1st 39 4 5 5 4 4 4
2nd 35 4 4 4 4 4 4
3rd 27 3 3 3 3 3 3
4th 21 2 2 3 3 3 2
5th 31 4 3 4 4 4 3
6th 33 4 4 4 4 4 4
Total 25 25 27 26 26 24
Hamilton Jefferson
Dm = Q R Dm = 8.8 Q GM HH
10.4
4 3.24 4 4 4.24 < 4.47 4
4 4.35 4 4 4.35 < 4.47 4
4 3.91 4 4 3.91 > 3.46 4
3 3.01 3 3 3.01 < 3.46 3
3 2.34 2 2 2.34 < 2.45 2
3 3.46 3 4 3.46 = 3.46 4
4 3.68 4 4 3.68 > 3.46 4
25 24 25 25
Adam’s Webster’s Huntington-
Plan Plan Hill Plan
Huntington-Hill Apportionment Principle
When there is a choice of adding one representative to
a number of sub-groups, the representative should be
added to the sub-group with the greatest Huntington-
Hill number.
𝑃𝐴 2
H=
𝑎(𝑎 + 1)

Where: 𝑃𝐴 is the population of sub-group A,

a is the current number of representatives of sub-group
A
Example 3
• The table below shown the number of computers
that are assigned to four number of students in
those schools. Use the Huntington-Hill
apportionment principle to determine to which
school a new computer should be assigned.

School Number of Number of

computers students
Rose 26 625
Lincoln 22 532
Midway 26 620
Valley 31 754
 𝑷𝑨 a a+1 H
Rose 625 26 27 556.45
Lincoln 532 22 23 559.34
Midway 620 26 27 547.58
Valley 754 31 32 573.10

𝑃𝐴 2
H= 𝑎(𝑎+1)
Now that we have looked at various
apportionment methods, it seems reasonable to
ask which is the best method. Unfortunately, all
apportionment methods have some flaws.
This was proved by Michael Balinski and H.
Peyton Young in 1982.
Apportionment
paradoxes
The Alabama paradox, although it was not given
that name until later, was first noticed after the
1870 census. At the time, the House of
Representatives had 270 seats.
However, when the number of representatives in
the House was increased to 280 seats, Rhode Island
lost a representative.
After the 1880 census, C. W. Seaton, the chief clerk
of the U.S. Census Office,
calculated the number of representatives each state
would have if the number were set at some number
between 275 and 300. He noticed that when the
number of representatives was increased from 299
to 300, Alabama lost a representative.
There are other paradoxes that involve
apportionment methods. Two of them are the
population paradox and the new states paradox. It is
possible for the population of one state to be
increasing faster than that of another state and for
the state still to lose a representative. This is an
example of the population paradox.
In 1907, when Oklahoma was added to the Union,
the size of the House was increased by five
representatives to accommodate Oklahoma’s
population. However, when the complete
apportionment of the Congress was recalculated,
New York lost a seat and Maine gained a seat. This is
an example of the new states paradox.
Summary of Apportionment Methods
and Possible Flaws
 Which is the best apportionment
•

•
Balinski-Young Impossibility Theorem

method?
Any apportionment method will either violate the quota rule of will produce paradoxes.

Quota Rule: The number of representatives apportioned to a sub-group should be equal to the lower quota or the upper quota of the group.
voting
The Plurality Method of Voting

Each voter votes for one candidate, and the

candidate with the most votes wins.
The winning candidate does not have to have a
majority of the votes.
Fifty people were asked to rank their preferences of
five varieties of chocolate candy, using 1 for their
favorite and 5 for their least favorite. This type of
ranking of choices is called a preference schedule.
The results are shown in the table below.
According to this table, which variety
of candy would win the taste test
using the plurality voting system?
To answer the question, we will make a table
showing the number of first-place votes for
each candy.
• B. Plurality with Elimination Method (Without Rank)
• If a candidate receives a majority of votes, that candidate is
declared the winner.
• If no candidate receives a majority, then the candidate with
the fewest vote is eliminated and a new election is
held until a candidate receives a majority of votes
Suppose that 30 members of a regional planning board must decide
where to build a new airport. The airport consultants to the regional
board have recommended four different sites. The preference schedule
for the board members is shown in the following table.
Using the plurality with elimination method,
the board members first eliminate the site with
the fewest number of first-place votes. If two
or more of these alternatives have the same
number of first-place votes, all are eliminated
unless that would eliminate all alternatives. In
that case, a different method of voting must be
used.
Bremerton is eliminated because it received only
two first-place votes. Now a vote is retaken using
the following important assumption: Voters do not
change their preferences from round to round. This
means that after Bremerton is deleted, the 12
people in the first column would adjust their
preferences so that Apple Valley becomes their
second choice, Cochella remains their first choice,
and Del Mar becomes their third choice. For the 11
voters in the second column, Apple Valley remains
their first choice, Cochella remains their second
choice, and Del Mar becomes their third choice.
Simi lar adjustments are made by the remaining
voters. The new preference schedule is
The board members now repeat the process and
eliminate the site with the fewest first-place votes. In
this case it is Del Mar. The new adjusted preference
schedule is
From this table, Apple Valley has 16 first-place votes
and Cochella has 14 first-place votes. Therefore,
Apple Valley is the selected site for the new airport.
The problem with plurality voting is
that alternative choices are not
considered.
If voters had been asked, “Choose the
candidate you prefer, but if that
candidate does not receive a majority
of the votes, which candidate would be
your second choice?”
The Borda Count Method of Voting
If there are n candidates or issues in an
election, each voter ranks the candidates or
issues by giving n points to the voter’s first
choice, n - 1 points to the voter’s second
choice, and so on, with the voter’s least
favorite choice receiving 1 point. The
candidate or issue that receives the most
total points is the winner.
Thirty-six senators are considering an educational
funding measure. Because the senate leadership
wants an educational funding measure to pass, the
leadership first determines that the senators prefer
measure A for $50 million over measure B for $30
million. However, because of an unexpected dip in
state revenues, measure A is removed from
consideration and a new measure, C, for $15 million,
is proposed. The senate leadership determines that
senators favor measure B over measure C.
In summary, we have
A majority of senators favor measure A over measure B.
A majority of senators favor measure B over measure C.
From these results, it seems reasonable to think
that a majority of senators would prefer measure A
over measure C. However, when the senators are
asked about their preferences between the two
measures, measure C is preferred over measure A.
To understand how this could happen, consider the
preference schedule for the senators shown in the
following table.
Notice that 15 senators prefer measure A
over measure C, but 12 + 9 = 21 senators, a
majority of the 36 senators, prefer measure C
over measure A. According to the preference
schedule, if all three measures were on the
ballot, A would come in first, B would come
in second, and C would come in third.
However, if just A and C were on the ballot, C
would win over A.
Applying the Borda count method to the
education measures, a measure receiving a first-
place vote receives 3 points. (There are three
different measures.) Each measure receiving a
second-place vote receives 2 points, and each
measure receiving a third-place vote receives 1
point.
 Pairwise Comparison Voting Method
The pairwise comparison method of voting is
sometimes referred to as the “head-to-head”
method. In this method, each candidate is
compared one-on-one with each of the other
candidates. A candidate receives 1 point for a win,
0.5 points for a tie, and 0 points for a loss. The
candidate with the greatest number of points wins
the election.

A voting method that elects the candidate who

wins all head-to-head matchups is said to satisfy
the Condorcet criterion.
Condorcet Criterion
A candidate who wins all possible head-to-head
matchups should win an election when all
candidates appear on the ballot.
There are four proposals for the name of a new football
stadium at a college: Panther Stadium, after the team mascot;
Sanchez Stadium, after a large university contributor; Mosher
Stadium, after a famous alumnus known for humanitarian
work; and Fritz Stadium, after the college’s most winning
football coach. The preference schedule cast by alumni and
students is shown below.

Use the pairwise comparison voting method to determine the

name of the stadium.
We will create a table to keep track of each of the head-
to-head comparisons. Before we begin, note that a
matchup between, say, Panther and Sanchez is the same
as the matchup between Sanchez and Panther. Therefore,
we will shade the duplicate cells and the cells between
the same candidates. This is shown below.
To complete the table, we will place the name of
the winner in the cell of each head-to-head match.

For instance, for the Panther–Sanchez matchup,

Panther was favored over Sanchez on
678 + 599 + 512 = 1789 ballots.
Sanchez was favored over Panther on
752 + 487 = 1239 ballots.

The winner of this matchup is Panther, so that

name is placed in the Panther versus Sanchez cell.
From the above table, Fritz has three wins,
Panther has two wins, and Mosher has one win.
Using pairwise comparison, Fritz Stadium is the
winning name.
Fairness Criteria
1. Majority criterion: The candidate who receives a majority
of the first-place votes is the winner.
2. Monotonicity criterion: If candidate A wins an election,
then candidate A will also win the election if the only change
in the voters’ preferences is that supporters of a different
candidate change their votes to support candidate A.
3. Condorcet criterion: A candidate who wins all possible
head-to-head matchups should win an election when all
candidates appear on the ballot.
4. Independence of irrelevant alternatives: If a candidate
wins an election, the winner should remain the winner in
any recount in which losing candidates withdraw from the
race.