Discrete Mathematics Farkaleet Series
Discrete Mathematics Farkaleet Series
Discrete
Mathematics
AUTHORS:
Prof. (R) Muhammad Urs Shaikh
Prof. Dr. Asif Ali Shaikh
Dr. Sania Nizamani
CO-AUTHORS:
Muhammad Tahir Wahocho (M.Sc)
Edited by:
Prof. Dr. Feroz Shah
C H A P T E R
1 SET THEORY
1.1 A HISTORY OF SET THEORY
The history of set theory is rather different from the history of most other areas of
mathematics. For most areas a long process can usually be traced in which ideas evolve
until an ultimate flash of inspiration, often by a number of mathematicians almost
simultaneously, produces a discovery of major importance.
1
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
An event of major importance occurred in 1872 when Cantor made a trip to Switzerland.
There Cantor met Richard Dedekind (Born: 6 October 1831 in Braunschweig,, died on 12
Feb 1916 Germany) and a friendship grew up that was to last for many
years. Numerous letters between the two in the years 1873-1879 are
preserved and although these discuss relatively little mathematics it is
clear that Dedekind's deep abstract logical way of thinking was a
major influence on Cantor as his ideas developed.
Cantor moved from number theory to papers on trigonometric series.
These papers contain Cantor's first ideas on set theory and also
Richard Dedekind
important results on irrational numbers. Dedekind was working
independently on irrational numbers and Dedekind published Continuity and irrational
numbers.
In 1874 Cantor published an article in Crelle's Journal which marks the birth of set
theory. A follow-up paper was submitted by Cantor to Crelle's Journal in 1878 but already
set theory was becoming the centre of controversy. Kronecker, who was on the editorial
staff of Crelle's Journal, was unhappy about the revolutionary new ideas contained in
Cantor's paper. Cantor was tempted to withdraw the paper but Dedekind persuaded Cantor
not to withdraw it and Weierstrass supported publication. The paper was published but
Cantor never submitted any further work to Crelle's Journal.
In one of his papers Cantor shows that the real numbers cannot be put
into one-one correspondence with the natural numbers using an
argument with nested intervals which is more complex than that used
today (which is in fact due to Cantor in a later paper of 1891). Cantor
now remarks that this proves a theorem due to Liouville, namely that
Leopold Kronecker
there are infinitely many transcendental (i.e. not algebraic) numbers in
each interval.
In his next paper, the one that Cantor had problems publishing in
Crelle's Journal, Cantor introduces the idea of equivalence of sets and
says two sets are equivalent or have the same power if they can be put in
1-1 correspondence. The word 'power' Cantor took from Steiner. He
proves that the rational numbers have the smallest infinite power and
also shows that Rn has the same power as R. He shows further that coun-
tably many subsets of R still have the same power as R. At this stage
Karl Weierstrass Contor does not use the word countable, but he was to introduce
the word in a paper of 1883.
Cantor published a six part treatise on set theory from the years 1879 to 1884. This work
appears in Mathematische Annalen and it was a brave move by the editor to publish the
work despite a growing opposition to Cantor's ideas. The leading figure in the opposition
was Kronecker who was an extremely influential figure in the world of mathematics.
Kronecker's criticism was built on the fact that he believed only in constructive
mathematics. He only accepted mathematical objects that could be constructed finitely
from the intuitively given set of natural numbers. When Lindemann proved that π is
transcendental in 1882 Kronecker said: Of what use is your beautiful investigation of π.
Why study such problems when irrational numbers do not exist. Certainly Cantor's arrays
of different infinities were impossible under this way of thinking.
2
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
Cantor however continued with his work. His fifth work in the six part treatise was
published in 1883 and discusses well-ordered sets. Ordinal numbers are introduced as the
order types of well-ordered sets. Multiplication and addition of transfinite numbers are also
defined in this work although Cantor was to give a fuller account of transfinite arithmetic
in later work. Cantor takes quite a portion of this article justifying his work. Cantor claimed
that mathematics is quite free and any concepts may be introduced subject
only to the condition that they are free of contradiction and defined in
terms of previously accepted concepts. He also cites many previous
authors who had given opinions on the concept of infinity including
Aristotle, Descartes, Berkeley, Leibniz and Bolzano. The year 1884 was
one of crisis for Cantor. He was unhappy with his position at Halle and
would have liked to move to Berlin. However this move was blocked by
Giuseppe Peano Schwarz and Kronecker. In 1884 Cantor wrote 52 letters to
Mittag-Leffler each one of which attacked Kronecker. In this year of
mental crisis Cantor seemed to lose confidence in his own work and applied to lecture on
philosophy rather than on mathematics. The crisis did not last too long and by early 1885
Cantor was recovered and his faith in his own work had returned. However, despite a
wealth of important work in the years after 1884, there is some indication that he never
quite reached the heights of genius that his remarkable papers showed over the 10 year
period from 1874 to 1884. Although not of major importance in the development of set
theory it is worth noting that Peano (1858 - 1932) introduced the symbol` ` for 'is an
element of ' in 1889. It comes from the first letter of the Greek word meaning 'is'.
In 1885 Cantor continued to extend his theory of cardinal numbers and of order types. He
extended his theory of order types so that now his previously defined ordinal numbers
became a special case. In 1895 and 1897 Cantor published his final double treatise on sets
theory. It contains an introduction that looks like a modern book on set theory, defining
set, subset, etc. Cantor proves that if A and B are sets with A equivalent to a subset of B and
B equivalent to a subset of A then A and B are equivalent. This theorem was also proved by
Felix Bernstein and independently by E. Schröder.
The dates 1895 and 1897 are important for set theory in another way. In 1897 the first
published paradox appeared, published by Cesare Burali-Forti. Some of the impact of this
paradox was lost since Burali-Forti got the definition of a well-ordered set wrong!
However, even if the definition was corrected, the paradox remained. It basically revolves
round the set of all ordinal numbers. The ordinal number of the set of all ordinals must be
an ordinal and this leads to a contradiction. It is believed that Cantor discovered this
paradox himself in 1885 and wrote to Hilbert about it in 1886. This is slightly surprising
since Cantor was highly critical of the Burali-Forti paper when it appeared. The year 1897
was important for Cantor in another way, for in that year the first International Congress of
Mathematicians was held in Zurich and at that conference Cantor's work was held in the
highest esteem being praised by many including Hurwitz and Hadamard.
In 1899 Cantor discovered another paradox which arises from the set of all sets. What is
the cardinal number of the set of all sets? Clearly it must be the greatest possible cardinal
yet the cardinal of the set of all subsets of a set always has a greater cardinal than the set
itself. It began to look as if the criticism of Kronecker might be at least partially right
since extension of the set concept too far seemed to be producing the paradoxes. The
'ultimate' paradox was found by Bertrand Arthur William Russell (1872 - 1970) in 1902
(and found independently by Zermelo). It simplify defined a set A = { X | X is not a
member of X }.
3
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
For instance, the set of students in this room; the English alphabet may be viewed as the set
of letters of the English language; the set of natural numbers; etc. So sets can consist of
elements of various natures: people, physical objects, numbers, signs, other sets, etc. (We
will use the words object or entity in a very broad way to include all these different kinds of
things.) A set is an ABSTRACT object; its members do not have to be physically collected
together for them to constitute a set. The membership criteria for a set must in principle be
well-defined, and not vague. If we have a set and an object, it is possible that we do not
know whether this object belongs to the set or not, because of our lack of information or
knowledge. (e.g. “The set of students in this room over the age of 21”: a well-defined set
but we may not know who is in it.) But the answer should exist, at any rate in principle. It
could be unknown, but it should not be vague. If the answer is vague for some collection,
we cannot consider that collection as a set. Another thing: If we have a set, then for any
two elements of it, x and y, it should not be vague whether x = y, or they are different. (If
they are identical, then they are not actually “two” elements of it; the issue really arises
when we have two descriptions of elements, and we want to know whether those
descriptions describe the same element, or two different elements.) For example: is the
letter q the same thing as the letter Q? Well, it depends on what set we are considering. If
we take the set of the 26 letters of the English alphabet, then q and Q are the same element.
If we take the set of 52 upper-cases and lower-case letters of the English alphabet then, q
and Q are two distinct elements. Either is possible, but we have to make it clear what set
we are talking about, so that we know whether or not q = Q. Sometimes we simply assume
for the sake of examples that a description is not vague when perhaps for other purposes it
would be vague – e.g., the set of all red objects. Sets can be finite or infinite. There is
exactly one set, the empty set, or null set, which has no members at all. A set with only one
member is called a singleton or a singleton set. (“Singleton of a”).
Notation: A, B, C … for sets; a, b, c … or x, y, z … for members. b A if b belongs to A
(B A if both A and B are sets and B is a member of A) and c A, if c doesn’t belong to A.
is used for the empty set.
Specification of sets
There are three main ways to specify a set:
(i) By listing all its members (list notation);
(ii) By stating a property of its elements (predicate notation);
(iii) By defining a set of rules which generates (defines) its members (recursive rules).
List notation: The first way is suitable only for finite sets. In this case we list names of
elements of a set, separate them by commas and enclose them in braces.
For instance, {1, 12, 45}, {Bilal, Mustafa, Juweria, Saireen, Aisha, Areej}, {a, b, d, m} are
examples of list notation to represent a set. Three-dot abbreviation”: {1, 2 … 100}, {1, 2, 3, 4,…}
is not a real list notation, it is not a finite list, but it’s common practice as long as the
continuation is clear. Note that we do not care about the order of elements of the list, and
elements can be listed several times. {1, 12, 45}, {12, 1, 45,1} and {45,12, 45,1} are
different representations of the same set (see below the notion of identity of sets).
Predicate or Set Builder notation: This part of notation is a property which, the members
of the set share (a condition or a predicate which holds for members of this set).
For example, {x| x is a natural number and x < 8} can be read as “The set of all x such that
x is a natural number and is less than 8”. Other examples are: {x| x is a letter of English
alphabet}, {y | y is a student of MUET and y is older than 21}
General form: The general form of predicate notation also known as “Set builder”
notation is as: {x | P(x)}, where P is some predicate (condition, property).
5
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
Recursive rules: (Always safe) Recursive rules are used to describe the membership of an
element of a set in different ways. For example, let us consider the set A that contains an
even numbers greater than 3. Then we can say that:
(i) 4 A (ii) If x A, then x + 2 A (iii) Nothing else belongs to A other than the even
number greater than 3
The first rule is the basis of recursion, the second one generates new elements from the
elements defined before and the third rule restricts the defined set to the elements generated
by rules (i) and (ii).
Identity
Two sets are identical if and only if they have exactly the same members. So A = B iff for
every x, x A implies that x B. For example, {0, 2, 4} = {x| x is an even natural number
less than 5}.
From the definition of identity follows that there exists only one empty set; its identity is
fully determined by its absence of members. Note that empty list notation {} is not usually
used for the empty set, we have a special symbol for it.
Subsets
A set A is a subset of a set B iff every element of A is also an element of B. Such a relation
between sets is denoted by A B. If A B and A ≠ B we call A “a proper subset” of B and
write A B.
(Caution: sometimes is used the way we are using .) Both signs can be negated using
the slash `/` through the sign.
For example, {a, b} {d, a, b, e} and {a, b} {d, a, b, e}, {a, b} {a, b}, but
{a, b} {a, b}.
REMARK: An empty set is a subset of every set, that is: A for every set A.
There are probably many ways of convincing that this is the case.
1. The set A is a subset of the set B if and only if every element of A is also an element
of B. If A is the empty set then A has no elements and so all of its elements (there
are none) belong to B no matter what set B we are dealing with. That is, the empty
set is a subset of every set.
2. Another way of understanding it is to look at intersections. The intersection of two
sets is a subset of each of the original sets. So if {} is the empty set and A is any set
then {} intersect A is {} which means {} is a subset of A and {} is a subset of {}.
3. You can prove it by contradiction. Let's say that you have the empty set {} and a set
A. Based on the definition, {} is a subset of A unless there is some element in {}
that is not in A. So if {} is not a subset of A then there is an element in {}. But {}
has no elements and hence this is a contradiction, so the set {} must be a subset of A.
An example with an empty set and a non-empty set might be the set of all women who
have walked on the moon or a set of all engineering students who have read Pathology or a
set of alphabets before the letter `a`.
Power sets
The set of all subsets of a set A is called the power set of A and denoted as P(A).
For example, if A = {a, b}, then P(A) = { , {a}, {b}, {a, b}}.
Also notice that: a A; {a} A; {a} P(A); A; P(A); P(A)
Be careful and pay close attention to the definitions and it should come out all right. But if
you don’t pay close attention to the definitions, it’s easy to make mistakes. Make sure you
understand these examples before you try it to solve exercises.
6
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
7
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
Set
Pronunciation Meaning Venn diagram Answer
notation
everything
AUB "A union B" that is in {1, 2, 3}
either of the sets
Ac everything
"A complement",
or in the universe {3, 4}
or "not A"
~A outside of A
everything in A
"A minus B", or
A–B except for anything {1}
"A complement B"
in its overlap with B
everything
~(A U B) "not (A union B)" outside {4}
A and B
everything outside
~(A ^ B) "not (A intersect
of the overlap {1, 3, 4}
or B)"
of A and B
~( )
It is natural to ask, where do these objects come from which do not belong to A? In this
case it is presupposed that there exists a universe of discourse and all other sets are subsets
of this set. The universe of discourse is conventionally denoted by the symbol U. Then we
have: Ac = U – A.
Ordered Pairs
We begin by introducing the notion of the ordered pair. If a and b are some elements, then
8
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
the unordered pair {a, b} is a set whose elements are exactly a and b. The “order” in which
a and b are put together plays no role; {a, b} = {b, a}. For many applications, we need to
pair a and b in a way making possible to “read off” which element comes “first” and which
comes “second.” We denote this ordered pair of a and b by (a, b); a is the first coordinate
of the pair (a, b), b is the second coordinate.
As any object of our study, the ordered pair has to be a set. It should be defined in such a
way that two ordered pairs are equal if and only if their first coordinates are equal and their
second coordinates are equal. This guarantees in particular that (a, b) ≠ (b, a) if a ≠ b.
Definition: An ordered pair (a, b) may be defined as: (a, b) = {{a}, {a, b}}.
If a ≠ b, (a, b) has two elements, a singleton {a} and an unordered pair {a, b}. We find the
first coordinate by looking at the element of {a}. The second coordinate is then the other
element of {a, b}. If a = b, then (a, a) = {{a}, {a, a}} = {{a}} has only one element. In
any case, it seems obvious that both coordinates can be uniquely “read off” from the set
(a, b). We make this statement precise in the following theorem.
Theorem: (a, b) = (a′, b′) if and only if a = a′ and b = b′.
Proof: If a = a′ and b = b′, then, of course,
(a, b) = {{a}, {a, b}} = {{a′}, {a′, b′}} = (a′, b′).
The other implication is more intricate. Let us assume that
{{a}, {a, b}} = {{a ′}, {a′, b ′}}.
If a ≠ b, {a} = {a′} and {a, b} = {a ′, b′}. So, first, a = a′ and then {a, b} = {a, b′} implies
b = b′. If a = b, {{a}, {a, a}} = {{a}}. Thus{a} = {a′}, {a} = {a′, b ′}, and we get a = a′ =
b′, so a = a ′ and b = b′ holds in this case, too.
With ordered pairs at our disposal, we can define:
Ordered one-tuples: (a) = a.
Ordered triples: (a, b, c) = ((a, b), c),
Ordered quadruples: (a, b, c, d) = ((a, b, c), d), and so on.
Cardinality of Sets
From the point of view of pure set theory, the most basic question about a set is: How
many elements does it have? It is a fundamental observation that we can define the
statement “sets A and B have the same number of elements” without knowing anything
about numbers.
Definition: Sets A and B have the same cardinality if there is a one-to-one function f with
domain A and range B. We denote this by |A| = |B|.
Definition: The cardinality of A is less than or equal to the cardinality of B (notation:
|A| ≤ |B|) if there is a one-to-one mapping of A into B.
Notice that |A| ≤ |B| means that |A| = |C| for some subset C of B. We also write |A| < |B| to
mean that |A| ≤ |B| and not |A| = |B|, i.e., that there is a one-to-one mapping of A onto a
subset of B, but there is no one-to-one mapping of A onto B.
Lemma:
(i) If |A| ≤ |B| and |A| = |C|, then |C| ≤ |B| (ii) If |A| ≤ |B| and |B| = |C|, then |A| ≤ |C|
(iii) |A| ≤ |A|.
Cantor-Bernstein Theorem. If | X| ≤ |Y| and |Y| ≤ |X|, then |X| = |Y|.
Finite Sets
Finite sets can be defined as those sets whose size is a natural number.
Definition: A set S is finite if it has the same cardinality as some natural number n . We
then define: |S| = n and say that S has n elements. A set is infinite if it is not finite.
9
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
11
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
12
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
are invalid sentences as for as English grammar is concerned. Thus we say that a word is
valid if it can be found in any complete English dictionary and that a sentence is
grammatical if it satisfies the standard rules of English grammar book.
Computer languages are similar to English in the sense that certain strings of characters are
legitimate (valid) words of the language and certain strings of words can be put together
according to certain rules to form syntactically correct programs. A compiler for a
computer language analyses the stream of characters in a program. It first recognize
individual word and sentence units (this part of compiler is called a lexical scanner), then to
analyses the syntax, or grammar of the sentence (this part is called a syntactic analyzer),
and finally to translate the sentences into machine code (this part is called a code
generator).
In computer science it has proved useful to look at languages from a very abstract point of
view as strings of certain fundamental units. One may use any finite set of symbols as an
alphabet. It is common to denote an alphabet by a Greek letter sigma Σ.
A string of characters of an alphabet Σ (or string over Σ) is either (a) an ordered n-tuple of
elements of Σ written without parentheses or commas or (b) the null string ε , which has no
characters. For example, if the alphabet Σ consists of two characters a and b, then aab, a,
bb, aabbbab, and ε are all strings over Σ.
The length of a string of characters of an alphabet is the number of characters that make up
the string. Thus if a and b are in the alphabet, the length of the string aaab is 4. The length
of null string is zero.
The above definitions are summarized as under:
Alphabet Σ: a finite set of characters
String over Σ: an ordered n-tuple of characters of Σ , written without
parentheses or commas, or the null string ε.
Formal language over Σ: a set of strings over Σ
Example: Let Σ = {a, b}. (i) Define a language L1 over Σ to be the set of all strings that
begin with the character b and have length of at most three characters. Find L1 (ii) A
palindrome is a string that looks the same if the order of its characters is reversed.
For instance, abba is a palindrome. Define a language L2 over Σ to be the set of
palindrome obtained using the characters of Σ. Write ten elements of L2.
Solution: L1 = {b, bb, ba, bbb, bba, bab, baa}
L2 ={ ε, a, b, aa, bb, aaa, bab, abba, baab, baabbbbbaab}
NOTATION: Let Σ be an alphabet. For each non-negative integer n, let (a) Σn denote the
set of all strings that have length n (b) Σ* denote the set of all strings of finite length over Σ.
It in fact is an infinite set.
Example: Let Σ = {a, b}. (i) Find Σ0, Σ1, Σ2, and Σ3. (ii) Let A = Σ0 Σ1 and B = Σ2
Σ3. Describe A, B and A B. (iii) Describe a systematic way of writing elements of Σ*.
Solution: (i) Σ0 = {ε}, Σ1 = {a, b}, Σ2 ={aa, ab, ba, bb}, Σ3 ={aaa, aab, aba, abb, baa, bba,
bab, , bbb}.
(ii) A is a set of all strings of length 1 at most. B is the set of all strings of length 2 or 3.
Thus A B is the set of all strings of length at most 3.
(iii) Elements of Σ* can be written systematically by starting with the null string ε, then
writing all strings of length 1, then string of length 2 etc. Thus
Σ* = { ε. a, b, aa, ab, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, ….}
13
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
EXERCISES 01
1. Is 6 = {6}? Explain.
2. Let A = {n Z| n =(-1)k, for some integer k}.
Describe A. Let B = {m Z| m = 1 + (-1)k, for some integer k}. Describe B.
3. (i) Is 3 {1, 2, 3}? (ii) Is 1 {1}? (iii) Is {2} {1, 2}? (iv) Is {3} {1, {2}, {3}}?
(v) Is 1 {1}? (vi) Is {2} {1, {2}, {3}}? (vii) Is {1} {1, {2}}? (viii) Is 1 {{1}, 2}?
(ix) Is {1} {1}? (x) Is {1} {1, {2}}?
4. Let A ={m Z| m = 2k – 1, for some integer k}, B ={m Z| m = 3k + 2, for some integer
k}, C ={m Z| m = 2k + 1, for some integer k}, and D ={m Z| m = 3k – 1, for some
integer k}.
(i) Is A = B? (ii) Is A = C? (iii) Is A = D? (iv) Is D = B?
Explain your answer in each case.
5. Let C ={m Z| m is divisible by 2}, B ={n Z| n is divisible by 3}, and C ={k Z| k is
divisible by 6}.
(i) Is A C? (ii) Is C A? (iii) Is C B? (iv) Find A B?
6. For the Venn diagram shown here, copy it and shade the
region corresponding to the following indicated sets.
(i) A B (ii) C B (iii) Ac
(iv) (A B)c (v) Ac Bc
7. By taking a counter example show whether or not the following statements are true.
Then prove the same by taking element argument.
(i) (A –B) (A B) = A (ii) A – (B – C) = (A – B) – C
(iii) (A – B) (C – B) = (A C) – B (iv) (A – B) (C – B) = A - (B C)
(v) If A B then (A C) (B C) (vi) If A B then (A C) (B C)
8. Prove by mathematical induction that for any natural number n > 1:
(A1 – B) (A2 – B) (A3 – B) … (An – B)= (A1 A2 A3 … An) – B.
9. (i) Is the number 0 in ? Why? (ii) Is = { }? Why?(iii) Is { }? Why?
10. Draw Venn diagram to describe sets A, B, and C that satisfy the given conditions:
(i) A B = , A C, C B = (ii) A B, C B, A C ≠
(iii) A B ≠ , B C ≠ , A C =
11. Prove whether the following statement are true or not. Also give a counter example in
each case. Illustrate each of these by drawing c Venn diagram assuming that each set is
subset of a universal set U.
(i) (A – B) (A B) = (ii) (A – B) ((b – C) (A – B) =
(iii) If A B then A (B C)c = (iv) If A B then A B c =
14
CHAPTER ONE DISCRETE MATHEMATICS SET THEORY
15
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
C H A P T E R
2 INTRODUCTION TO LOGIC
2.1 INTRODUCTION
The first man who wrote treatise on logic was Greek philosopher Aristotle (384 BC – 322
BC), a student of Plato and teacher of Alexander the Great. They were
a collection of rules for deductive reasoning that were intended to
serve as a basis for the study of almost every branch of knowledge.
In the 17th century, the German mathematician Gottfried Leibniz
formed an idea of using symbols to preset the process of deductive
reasoning in much the same way that algebraic notations has
mechanized the process of reasoning about numbers and their
relationships. In 19th century, the idea of Leibniz was realized by two
English mathematicians George Boole and De Morgan, who founded
Aristotle the modern subject of symbolic logic. With continuous research work
(384 –322 BC) to present day, symbolic logic has provided the theoretical basis
for many areas of computer science, digital circuit design, relational
database theory, automata theory, computability and artificial
intelligence.
Logic
Logic means methods of reasoning. Logic is a science of necessary
laws of thought, without which no employment of the understanding
and the reason takes place (Immanuel Kant, 1785). The rules of logic
Boole specify the meaning of mathematical statements. These rules help to
(1815-1864) understand and reason with statements such as:
“ square of a prime number is also a prime” or “sum of first
n natural numbers is equal to n(n + 1)/2”
Logic is the basis of all mathematical reasoning. The rules of
logic give precise meaning to mathematical statements. These
rules are used to distinguish between valid and invalid mathematical
argument.
Statement
Most of the definitions of formal logic have been developed so that
they agree with the natural or fundamental logic used by people who
DeMorgan have been learned to think clearly and use language carefully.
(1806-1871)
The difference between formal and intuitive (normal) logic are necessary to avoid
uncertainty and obtain consistency. In any mathematical theory, new terms are defined by
16
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
using those that have been previously defined. However, this process has to start
somewhere. A few initial terms necessarily remain undefined. In logic, the words sentence,
true, and false are the initial undefined terms.
Definition: A statement is a declarative sentence which is either true or false but not both.
The statement is also known as proposition.
For example, “2 + 2 = 4” and “2 + 2 = 7 “are statements where the first one is true and the
second is false. On the other hand, the truth or falsity of “She is an officer” depends on the
reference for the pronoun she. For some value of she the sentence may be true; for the
others it may be false. If the sentence were preceded by the other sentences that made the
pronoun’s reference clear, then the sentence would be a statement. Considered on its own,
however, the sentence is neither true nor false, and so it is not a statement.
Similarly, “x + y < 0” is not a statement because for some values of x and y this may be
true and for other values it may be false. For instances, if x = 2 and y = -4 then this
inequality is true whereas if x = 2 and y = 3 the same is false.
Compound Statements
In this section we introduce three symbols that are used to build more complicated logical
expressions out of simple ones. These symbols are:
: denotes “not “ : denotes “and “ : denotes “or “
REMARK: Statements will be denoted by p, q, r, s, t etc.
Given a statement p, the statement p is read as ‘not p’ or ‘It is not the case that p’ and is
called the negation of p. For example, let p be the statement “x = 3”. Then p means
“x ≠ 3” or “It is not the case that x = 3”.
Conjunction and Disjunction
If p and q are two statements then sentence “ p q “is read “p and q “and is called conjunction of
p and q. The sentence “ p q “is read “p or q “and is called disjunction of p and q.
In expressions that contain along with or , the order of operation is that is evaluated first.
For instance, p q (p) q . Similarly, ( p q) represents the negation of disjunction of p
and q. Here negation is evaluated after the evaluation of disjunction as it lies under the parentheses.
The symbols and are considered co-equal in order of operations. The expression such as
p q r is considered ambiguous. It must be written as ( p q ) r or p ( q r ) to have
proper meaning.
Truth Tables
Truth tables display the relationships between the truth values of propositions. They are particularly
valuable in the determination of the truth values of propositions constructed from simpler
propositions. The following tables display the possible truth values for “negation”, “disjunction”
and “conjunction”.
By definition
i. Disjunction ( p q ) is true only when p or q is true otherwise it is false.
ii. Conjunction ( p q ) is true when both p and q are true otherwise it is false.
Truth values for Truth values for Truth values for
Negation of Disjunction Conjunction
proposition
P p P q p q p q pq
T F T T T T T T
F T T F T T F F
- - F T T F T F
- - F F F F F F
17
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
19
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
For Example:
i). The sentence “if 2 + 2 = 4” then “5 + 3 = 8” is true because both statements are
true.
ii). The sentence “if 2 + 2 = 4” then “5 + 3 = 9” is false because 1st statement is true
but 2nd is false.
iii). The sentence “if 2 + 2 = 5” then “5 + 3 = 8” is true because 1st statement is false
but 2nd is true.
iv). The sentence “if π is a rational number” then “e is rational number” is true
because both statements are false.
To understand implication let us consider the following example. Let p and q be the
propositions where:
p ≡ “Ali’s salary is over Rs. 2 lacs” and q ≡ “Ali pays income tax”. Now,
If Ali’s salary is over 2 lacs and he pays income tax, he will not be penalized.
If Ali’s salary is over 2 lacs and does not pay the tax, he will be penalized.
If Ali’s salary is not over 2 lacs but pays the tax, he will not be penalized.
If Ali’s salary is not over 2 lacs and does not pay the tax, he will not be penalized.
In this example,
p is true means “Ali’s salary is over 2 lacs”.
q is false means “Ali does not pay the tax”
p → q means he is penalized.
Because implications play an important role in mathematical reasoning, a variety of
terminologies is used to express p → q. Some of these are:
“if p then q” “p implies q” “p only if q” ”q if p”
“q when p” “q whenever p” “q follows from p” “q is necessary for p”
“p is sufficient condition for q” “a necessary condition for p is q”
Converse, Contra-positive and Inverse
There are some related implications that are derived from the implication p → q. They are:
i. Converse ii. Contra-positive iii. Inverse
Converse: If p → q is an implication then its converse is q → p.
Contra-positive: If p → q is an implication then its contra-positive is q → p.
Inverse: If p → q is an implication then its inverse is p → q.
Truth table for Converse
P Q p→q q→p
T T T T
T F F T
F T T F
F F T T
Truth table for Contra-positive
p Q p→q q p q → p
T T T F F T
T F F T F F
F T T F T T
F F T T T T
Truth table for Inverse
p Q p→q p q p → q
T T T F F T
T F F F T T
F T T T F F
F F T T T T
20
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
You may observe that truth values of implication (p → q) and its contra-positive
( q → p) are same and truth values for converse (q → p) and inverse ( p → q) are
same. It may be noted that when two compound propositions have the same truth values
they are called equivalent. Thus “implication” and “contra-positive” are equivalent
compound propositions and converse and inverse are equivalent compound statements.
Example 1: What are the contra-positive, the converse, and the inverse of the
implication “If it snows today then I will go to hill station tomorrow”.
Solution: Let p be the proposition that “It snows today” and q be the proposition that “I
shall go to hill station tomorrow”.
The contra-positive q → p means “If I will not go to hill station tomorrow then it is not
snowing today”. The converse q → p means “If I will go to hill station tomorrow then it is
snowing today”. The inverse p → q means “If it doesn’t snow today then I will not go
to hill station tomorrow”.
Bi-conditional or Double Conditional Proposition
Let p and q be propositions. The bi-conditional proposition, denoted by p ↔ q is a
proposition that is true when both p and q have the same truth values and is false otherwise.
The terminology “p if and only if q” is used for bi-conditional. Other ways to express the
bi-conditional proposition are:
“p is necessary and sufficient for q” “If p then q and vice versa” “p iff q”.
The truth table for bi-conditional proposition is shown below:
Truth table for Bi-conditional proposition
p q p↔q
T T T
T F F
F T F
F F T
For Example: (i) The sentence “2 + 2 = 4” if and only if π is irrational” is true. (ii) The
sentence “2 + 2 = 5” if and only if π is irrational” is false.
Let us take another example. Let p be the proposition “vectors a and b are perpendicular”
and q be the proposition “Their dot product is zero”. Then p ↔ q is the proposition
“vectors a and b are perpendicular if and only if their dot product is zero”. This means that
if vectors a and b are perpendicular then their dot product is zero and if the dot product
between two vectors is zero then they are perpendicular.
REMARK: It may be noted that: p ↔ q ≡ (p →q) (q →p)
Precedence of Logical Operators
In arithmetic, the hierarchy of operators is as under:
Brackets ( ), Multiplication (×), Division (÷), Addition (+), and Subtraction (-)
Similarly, the hierarchy of logical operators is as under:
Negation ( ), Conjunction ( ), Disjunction ( ), Implication (→) and Bi-conditional (↔)
Thus p q is the conjunction of p and q where as (p q) is the negation of
conjunction of p and q. Hence p q and (p q) are not same propositions.
Similarly, conjunction operator has hierarchy over disjunction operator. For example, when
we write p q r , p q is evaluated first and then its disjunction is taken with r. In other
words,
p q r =( p q) r
Similarly, implication (→) has less hierarchy over conjunction or disjunction operators. For
example, when we write p q → r we mean (p q) → r. This means p q is executed first
and then implication r is executed.
21
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
22
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
The puzzle that we present here is originally posed by Raymond Smullyan, a master of
logic puzzles when he published more that a dozen books containing challenging puzzles
that involve logical reasoning.
Example 5: In a small town two kinds of people “Rich” and “Poor” are living. Riches
always tell the truth, and poor always lie. You meet with two people A and B. What
are A and B if A says “B is rich” and B says “The two of us are opposite types”?
Solution: Let us define two statements
p: A is a rich p: A is a poor
q: B is a poor q: B is a rich.
We first consider that A is a rich. This means that p is true. Now if A says that B is rich then
q is also true. Now if B is rich and he never lies and B says that “two of us are opposite
types”. Thus what A and B say is expressed in logical form as (p q) ( p q). This is
not possible because A and B are both rich. Consequently, A is not a rich, so p is not true.
If A is poor and he says that B is rich, it is not true. Thus q is false and B is also poor. Now
if B is poor its statement that “Two of us are opposite type” is not true. This is consistent
with A and B being poor. Thus we conclude that both A and B are poor.
Logic and Bit operations
We are aware of the fact that computers represent information using bits. A bit has two
possible vales, 0 or 1. Since there are two truth values “T” and “F”, it is customary to use 1
to represent true and 0 to represent false.
Computer bit operations correspond to the logical connectives. Using the 1 and 0 to
represent “T” and “F” the disjunction ( ), conjunction ( ) and exclusive or ( ) may be
expressed as “AND” “OR”, and “XOR” respectively. Thus
T T = T → 1 AND 1 = 1 T T = T → 1 OR 1 = 1 T T = F → 1 XOR 1 = 0
T F = F → 1 AND 0 = 0 T F = T → 1 OR 0 = 1 T F = T → 1 XOR 0 = 1
F T = F → 0 AND 1 = 0 F T = T → 0 OR 1 = 1 F T = T → 0 XOR 1 = 1
F F = F → 0 AND 0 = 0 F F = F → 0 OR 0 = 0 F F = F → 0 XOR 0 = 0
Example 6: Find the bitwise OR, bitwise AND, bitwise XOR when the bit strings are
1110001000 and 1010101010.
Solution: Writing the bit string in block of “four” bits, we have:
11 1000 1000
10 1010 1010
11 1010 1010 bitwise OR
10 1000 1000 bitwise AND
01 0010 0010 bitwise XOR
23
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
p q pq (p q) p q p q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
Example 2: Show that propositions (p p) and (p p) are tautology and contradiction
respectively.
Solution: The truth table below shows that truth value of proposition (p p) is true and that of
proposition (p p) is false. Hence first proposition is tautology and the second one is
contradiction.
p p p p p p
T F T F
F T T F
Laws of Logical Equivalence
The following laws are logically equivalent and may be used to show that given two propositions
are logically equivalent, tautology or contradiction without using truth tables.
Logical Equivalences Logical Equivalences
Logical Equivalences
Involving Implications Involving bi-conditionals
Equivalence Name
p T ≡ p p→ q ≡ p q p↔ q ≡ ( p→ q) ( q→ p)
Identity laws
p F≡ p p→ q ≡ q → p p↔ q ≡ p↔ q
p T ≡ T Domination p q ≡ p → q p↔ q≡( p q) ( p q)
p F ≡ F laws p q ≡ ( p → q) ( p↔ q) ≡ p↔ q
p p ≡ p
p p ≡ p
Idempotent
laws
( p→q)≡p q
(p→ q) (q→ r)
( p) ≡ p
Double
negation law ≡ p→ ( q r)
p q ≡ q p Commutative (p→ q) (p→ r)
p p ≡ q p laws ≡ p→ (q r)
(p q) r ≡ p (q r) Associative (p→ r) (q→ r)
(p q) r ≡ p (q r) laws ≡ ( p q) → r
p (q r) ≡ (p q)
Distributive (p→ r) (q→ r)
(p r) p ( q r)
laws ≡ ( p q) → r
≡( p q) (p r)
(p q) ≡ p q De Morgan’s
(p q) ≡ p q laws
(p q) p ≡ p Absorption
(p q) p ≡ p laws
p p ≡ T
Negation laws
p p ≡ F
24
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
By using above laws we can prove the equivalence of two compound propositions without
using the truth table. The following example depicts this idea.
Example 3: Use laws of equivalence show that (p q) ( p q) and p are logically
equivalent.
Solution: (p q) ( p q) ≡ (p q) ( ( p) ( q)) from the De Morgan’s
law
≡ (p q) (p q )
≡ p (q q) from the distributive law
≡ p F from the negation law
≡p from the identity law
REMARK: Use truth table to prove above proposition.
Example 4: Use laws of equivalence show that the proposition ( p q) → ( p q) is
tautology.
Solution: ( p q) → ( p q) ≡ (p q) (p q) [by using the law p→ q ≡ p q]
≡ ( p q) (p q) [by using De Morgan’s law]
≡ ( q p) (p q) [by using commutative law]
≡ q ( p p) q [by using associative law]
≡ q T q [by using negation law]
≡ ( q q) T [by using associative law]
≡ T T [by using negation law]
≡T [by using identity law]
REMARK: Use truth table to prove that above proposition is “Tautology”.
2.4 LOGIC of QUANTIFIED PROPOSITIONS
In the above sections we discussed the logical analysis of compound statements obtained
from simple statements joined by connectives namely disjunction, conjunction, negation,
implication and bi-conditional operators. Such analysis throws light on many aspects of
human reasoning, but it cannot be used to decide validity in mathematical and everyday
situations. For example, consider the following argument:
“All human beings are mortal. Ali is a human being. Therefore, Ali is mortal.”
This argument looks very correct. Yet its validity cannot be resulting using methods
outlined in the above sections. To determine validity for such problems, it is necessary to
separate the statements into parts in the same way as we separate declarative sentences in
English into subjects and predicates. Two special words “for all” and “for some” which are
known as “Quantifiers” are used to determine the validity of such arguments. The symbolic
analysis of predicates and quantified statements is called the predicate calculus. The
symbolic analysis of ordinary statements as discussed in the previous sections is called the
propositional calculus or statement calculus.
Predicates and Quantified Statements
We know that the sentence “He is a university student” is not a statement because it may be
either true or false depending on the pronoun he. Similarly, the sentence “x + y > 0” is not
a statement because its truth value depends on the values of x and y.
In grammar, the word predicate refers to the part of a sentence that gives information about
the subject. In the sentence “Ali is a student at Mehran University”, ‘Ali’ is the subject and
the phrase ‘is a student at Mehran University’ is the predicate. The predicate is the part of
sentence from which the subject has been removed.
In logic, predicates can be obtained by removing any noun from the statement. For
example, let P stands for “is a student at Mehran University” and Q stands for “is a student
at”. Then both P and Q are predicate symbols. The sentence “x is a student at Mehran
25
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
University” and “x is a student at y” are symbolized as P(x) and Q(x, y) respectively. Here x
and y are predicate variables that take values in suitable sets. When real values are placed
in place of predicate variables, we get a statement.
When an element in the domain of the variable is substituted, the resulting statement may
be true or false. The set of all such elements that make the predicate true is called the truth
set of predicate or universe of discourse.
REMARK: If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all
elements of D that makes P(x) true when substituted for x. The truth set for P(x) is denoted
by {x D| P(x)}. This is read as “the set of all x in D such that P(x). The domain D is
known as “Universe of Discourse”.
For instance, let P(x) be “x is a factor of 12” and suppose the domain of x is the set of all
positive integers. Then truth set P(x) is {1, 2, 3, 4, 6, 12} because these are the only
positive integers that divide 12.
Notations and Used in Truth Sets
Let P(x) and Q(x) be predicates and suppose that common domain of x is D. The notation
P(x) Q(x) means that every element in the truth set P(x) is in Q(x). The notation
P(x) Q(x) means that P(x) and Q(x) have identical truth sets.
For example, let us assume that domain of x is a set of whole numbers W and P(x), Q(x)
and, R(x) are truth sets defined as under:
P(x) be “x is a factor of 12”. This means: P(x) = {1, 2, 3, 4, 6, 12}
Q(x) be “x is a factor of 8”. This means: Q(x) = {1, 2, 4, 8}
R(x) be “0 < x < 9 and x is an even number ≠ 6”. This means: R(x) = {1, 2, 4, 8}
i. We see that every element of truth set Q(x) is in the truth set P(x), hence, Q(x) P(x).
ii. The truth sets of Q(x) and R(x) are identical hence, R(x) Q(x).
Quantifiers: (for all) and (there exists/for some)
As discussed in the previous section that to change predicate into statement one has to
assign specific value to all its variables. For example, if x represents a number 55, the
sentence “x is divisible by 11” is a true proposition. The phrase “x is divisible by 11” is
known as quantifier. Thus to make a proposition from predicates one has to add
quantifiers with them. Quantifiers are the words that refer to quantifies such as “some” or
“all” and tell for how many elements a given predicate is true. The concept of quantifier
was introduced by the American philosopher, logician, and engineer Charles Sanders
Peirce (1839 – 1914) and German logician Gottlob Frege.
The symbol denotes “for all” and is called universal quantifier is used when every x of
truth set satisfies some specific property. For example, “All human beings are mortal” may
be expressed in formal way as: x D, x is mortal
where D is the set of all human beings. We may also use the words “for any”, “for each”,
“given any” in place of “for all”. As another example,
x, y R, x + y = y + x.
Here domain R is a set of real numbers.
For instances, “Every natural number is the sum of the squares of four integers” This is a
theorem due to Lagrange. It can be written as:
n N , a , b, c , d Z , such that n a 2 b 2 c 2 d 2
REMARK: Let P(x) be a predicate and D the domain of x. A universal statement is a
proposition of the form “ x D, P(x)”. It is defined to be true if, and only if, P(x) is true
26
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
for every x in D. It is defined to be false if at least one x does not belong to D. The value of
x for which P(x) is false is called a counter-example to the universal statement.
Example 1: Consider the statement: “ x D, x2 ≥ x”. Show that this statement is
(i) True when D = {1, 2, 3}.
(ii) False when D = R, by finding a counter-example, R being the set of
real numbers.
Solution: (i) Check that “x2 ≥ x for all x in D.
12 ≥ 1 (true), 22 ≥ 2 (true) and 32 ≥ 3 (true)
Hence, “ x D, x2 ≥ x” is true.
(ii) Counter-example: Take x = 1/2. Then, (1/2)2 is not ≥ (1/2). Hence, “ x D,
x2 ≥ x” is false.
The symbol denotes “there exists” and is called existential quantifier is used when
some x of truth set satisfies a specific property. For example, university offers some special
course in discrete mathematics and few students get registered in this course. Now we say
“there is a student registered in discrete mathematics”. More formally, it is described
as: s S such that s is a student in Discrete Mathematics
Here, S is a set of all students of that particular university.
As another example: 1 + 1 ≠ 1. 1, 2 + 2 = 2. 2, 3 + 3 ≠ 3.3
Thus we see that there is only one natural number 2 that satisfies the property that m + m =
m . m. Formally, this can be expressed as: m N such that m + m = m . m.
Example 2: Consider the statement: “ x D, x2 = x”. Show that this statement is
(i) True when D = {1, 2, 3}.
(ii) False when D = {2, 3, 4}.
Solution: (i) Check that “x2 = x for all x in D:
12 = 1 (true), 22 = 2 (false) and 32 = 3 (false)
Since there is at least one element in the set D for which the statement “x2 = x is true.
Hence, “ x D, x2 = x” is true.
(ii) Check that “x2 = x for all x in D: 22 = 2 (false), 32 = 3 (false) and 42 = 4 (false)
Since there is not a single element in the set D for which the statement “x2 = x is true.
Hence, “ x D, x2 = x” is false.
We are now producing some important formal propositions with their general forms with
example(s) from each.
Example 3: Every natural number is the sum of the squares of four integers. This is a
theorem due to Lagrange. It can be written as:
n N , a , b, c , d Z , such that n a 2 b 2 c 2 d 2 .
Solution: Let n = 10. Then 10 = 12 + 22 + (-1)2 + (-2)2.
Similarly, take n = 15. Then 15 = 12 + 22 + 32 + (-1)2.
Proof. We will use the following Euler’s identity:
(x21 + x22 + x23 + x24) (y21 + y22 + y23 + y24)
= (x1y1 + x2y2 + x3y3 + x4y4)2 + (x1y2−x2y1 +x3y4 −x4y3)2 + (x1y3−x3y1+x4y2−x2y4)2 +
(x1y4−x4y1+x2y3−x3y2)2
This is very easy to verify.
The conclusion is that the product of two numbers that are sum of four squares is also sum
of four squares. Hence, since the case of 1 is trivial, and since every natural number > 1 can
be decomposed as a product of prime numbers, it is enough to prove the result for prime
numbers. The first case is p = 2, but that follows from 2 = 12 + 12 + 02 + 02.
27
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
Example 4: Every even natural number greater than 2 is the sum of two primes. This
is known as GOLDBATCH Conjecture/Guess. It can be expressed as:
n N { 1 }, p , q prime , such that 2n p q .
Solution: It may be noted that 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 57,
59, 67, 71, 73, 79… are prime numbers. Now, let us take few even numbers and see the
truth ness of the conjecture.
4 = 2 + 2, 6=3+3 8=3+5 10 = 3 + 7 12 = 5 + 7, etc.
REMARK: It is not yet known whether this is true or not. This is one of the greatest
unsolved problems in mathematics.
Further Examples of and
1. Translating From Informal to Formal Language
i. Square of every real number is greater than or equal to zero means “ x R, x2 ≥ 0”.
ii. Every triangle has three angles means “ t T, t has three angles” (T is the set of all Δs)
iii. Some programs are structured mean “ p P, p is structured” (P is a set of structured
programs).
2. Writing Universal Conditional Statements Informally
General form: ________, if __________ then__________.
For example: All bytes have eight bits may be expressed with conditional statement as:
b, if b is a byte then x has eight bits.
28
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
29
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
B, and C. The set {B,C} is a subset of {A, B, C}. There is a special set with no elements,
the empty set {} or ø, as the set of humans bigger than the earth, or the set of odd numbers
divisible by two. Some sets contain infinitely many elements, as the set of all even
numbers.
A set can contain sets. The set {{A, B, C}, {x, y}} contains two sets {A, B, C} and {x, y}.
It also contains the empty set, by the way. All sets contain the empty set. We can define the
set of all sets. This set contains {A, B, C} and {{A, B, C}, {x, y}} and every other possible
set. Some sets contain themselves. The set of all red marbles does not contain itself,
because it contains no sets at all, only marbles. Let's say that S is a set which contains S
and {A, B}. Then this is S: {S, {A, B}}. It contains two sets, itself and {A, B}. The set of
all sets obviously contains itself. Well, let's construct a very interesting set, the set of all
sets which do not contain themselves.
There is something wrong here. Does "the set of all sets which do not contain themselves"
sound like "the barber who shaves all men who do not shave themselves?" The story of the
barber was inconsistent. The set of all sets which do not contain themselves is inconsistent
for the same reason. Does the set of all sets which do not contain themselves actually
contain itself, or not? If it contains itself, then it cannot contain itself. If it does not contain
itself, then it must contain itself. It is inconsistent.
But where did we go wrong? Let's make some lists. A list is a special kind of set. But we
know what a list is. A list may be clearer in our minds than a set. We cannot actually
physically make infinite lists. But we can certainly define some of them, like the list of all
even numbers. So we can deal with infinite lists. We can also make lists of lists. Here is
such a list:
1. My shopping list
2. My email address list
3. David Letterman's list of Top Ten Whatever’s
This list of lists is real. Now, if we allow infinite lists, then it is no stretch at all to produce
the list of all lists, and even the list of all lists which do not contain themselves. And that
list is inconsistent.
Well, maybe there are no infinite lists. There are infinite sets, for example, the set of all
even numbers. And that is a list: the list of all even numbers. The concept of an infinite list
is actually fairly simple.
So we have an inconsistent set. That is not all. We made no mistakes when we constructed
the set of all sets which do not contain themselves. And that means that set theory is
inconsistent. And that means that logic is inconsistent. And that means that all of
mathematics, including algebra and geometry, is inconsistent.
It doesn't invalidate mathematics or logic or set theory. The Pythagorean Theorem is still
true. But there is some doubt. Kurt Gödel (Gödel) proved that Number Theory (and by
identical arguments, every branch of mathematics) is inconsistent. He converted Russell's
Paradox, the set version, into a statement in Number Theory, and showed that Number
Theory is inconsistent. This had huge repercussions in the world of mathematics. All of this
leads to the following problem:
1. There are things that are true in mathematics (based on basic assumptions).
2. There are things that are false.
3. There are things that are true that can never be proved.
4. There are things that are false that can never be disproved.
And that is a problem, because we cannot ever tell if something is true unless we can prove
it.
30
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
31
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
EXERCISES 02
1. Which of the following sentences are propositions? What are their truth values if the
sentence is proposition?
i. Karachi is capital of Pakistan ii. 3 + 4 = 7 iii. 4 + 11 = 16
iv. Answer this question v. x + y = 3
vi. a + b = b + a where a and b are real numbers vii. What is your name?
viii. There are no black flies in Makka
xi. a + 1 = 4 if a = 2 x. a + b = b + u if u = a
2. Let p and q be the propositions
p: I appeared in the examination q: I passed the examination
Express each of the following propositions:
i. q ii. p iii. p q iv. p q v. p → q vi. q → p
vii. p ↔ q viii. p → q
ix. q → p x. p
q
xi. p q xii. p ( q p)
3. Let p and q be the propositions
p: You have malaria fever q: You miss the interview r: You qualify the interview
Express each of the following propositions:
i. q ii. p iii. p q iv. p q v. p → q vi. q → p
4. Let p and q be the propositions
p: You drive over 120 km/h q: You are penalizes
Express each of the following propositions using the above propositions and logical
connectives.
i. You do not drive over 120 km/h
ii. ii.You drive over 120 km/h but you are not penalized
iii. You will be penalized if you drive over 120 km/h
iv. iv. If you do not drive over 120 km/h you will not be penalized
v. v. Driving over 120 km/h is sufficient to be penalized
vi. You are penalized but you do not drive over 120 km/h
5. Let p, q and r be the propositions
p: You get grade A on the final examination q: You solved each exercise of all courses
r: You secure top position in the university
Express each of the following propositions using p, q and r with logical connectives.
i. You get grade A on the final examination but you do not solve each exercise of
all courses.
ii. You get grade A on the final examination, you do not solve each exercise of all
courses and you secure top position in the university
iii. To secure top position in the university it is necessary to solve each exercise of
all courses.
iv. Getting grade A on the final examination and solving each exercise of all
courses is sufficient to secure top position in the university.
v. You will secure top position in the university if and only if you get grade A on
the final examination or you solve each exercise of all courses.
6. Determine whether the following bi-conditional propositions are true or false.
i. 3 + 3 = 6 if and only if 5 + 9 = 14 ii. 4 + 6 = 10 if and only if 7 + 4 = 10
iii. 2 + 5 = 7 if and only if fishes can fly iv. 1 > 2 if and only if 3 > 2
7. Determine which of the following implication is true and which one is false.
i. 3 + 3 = 6 if 5 + 9 = 14 ii. 4 + 6 = 10 if 7 + 4 = 10 iii. 2 + 5 = 7 if fishes can fly
32
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
iv. 1 > 2 if 3 > 2 iii. 2 + 5 = 8 if fishes can fly iv. 2 + 5 = 7 if pigeon flies
8. For each of the following propositions, state whether an inclusive or an exclusive or is
intended. Explain each one of these briefly.
i. For the computing skill job requirement of WINDOW or UNIX operating system is
required.
ii. You can have coffee or cold drink at the dinner.
iii. You may publish your text book or destroy it.
iv. To enter in Pakistan you must be citizen of Pakistan or visa entry.
9. For the following implication state whether inclusive/exclusive or is indicated.
i. If you intend to take discrete mathematics you must have taken mathematics or computer
science course.
ii. If you book a new house in the housing society you may get a discount of Rs. One lac or
3% of the total value of house.
iii. Dinner includes two items from mutton or three items from chicken.
iv. School remains closed if more than 3 feet of snow falls or the temperature is below -10
o
C.
10. State the converse, contra-positive, and inverse of the following implications.
i. If it snows today, I will ski tomorrow.
ii. I will come to the university when the examination date is announced.
iii. A positive integer is a prime if it is divisible by 1 or itself.
iv. If it is sunny tomorrow, then I shall come to university.
v. I go to beach whenever it is raining.
11. Construct the truth tables for the following compound propositions.
i. p p ii. p p iii. (p q) → p iv. p q → p q
v. p ↔ p vi. (p→q) ↔ ( p → q) vii. (p→q) → (q → p)
viii. q (p q) ix. p p x. (p q) → (p q) xi. (p ↔ q ) ( p ↔ q )
xii. (p q) r xiii. p→(q→r) ivx. ( p ↔ q) ↔ (p ↔ r) xv. (p q) r
12. Find the bitwise OR, bitwise AND, and bitwise XOR for each of the following pairs of
bit string.
i. 111 1111, 001 1011 ii. 1111 1100, 1100 0001 iii. 11 1111 1111, 00 1100
1010
13. Evaluate each of the following.
i. 1 1000 (0 1011 1 1011) ii. 11 1101 (01 1011 10 1111)
iii. 11 1101 (01 1011 10 1111)
14. Use truth tables to verify the Laws of Logical Equivalence.
15. Show that following compound propositions are tautology. (Use truth table and “Laws
of Equivalence) where necessary.
i. (p q) →p ii. p →(p q) iii. p → (p →q )
iv. (p →q ) → p v.(p q)→(p →q) vi. (p →q ) → q
16. A menagerie (a collection of wild animals) consists of 7 brown dogs, 2 black dogs, 6 gray cats,
10 black cats, five blue birds, 6 yellow birds, and 2 black birds. Determine which of the following
statements are true and which are false.
i. There is an animal in the menagerie that is red.
ii. Every animal in the menagerie is a bird or mammal.
iii. Every animal in the menagerie is brown or gray.
iv. There is an animal in the menagerie that is neither a cat nor a dog.
v. No animal in the menagerie is blue.
vi. There are a dog, a cat, and a bird in the menagerie that all have the same color.
17. Find the truth set of each of the following predicate:
33
CHAPTER TWO DISCRETE MATHEMATICS INTRODUCTION TO LOGIC
34
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
C H A P T E R
35
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
37
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
Example 13: Refer to Example 1 (vi), which of the relations are transitive?
Solution: The relations R 1 , R2, and R4 and R5 re transitive.
R1 is transitive because if a ≤ b and b ≤ c then a ≤ c.
R2 is transitive because if a > b and b > c then a > c.
R4 is transitive because if a = ± b and b = ± c then a = ± c.
R5 is transitive by definition.
The relations R3, and R6 are not transitive.
R3 is not transitive because by definition if (2, 1), (1, 0) are in R5 then (2, 0) doesn't.
R6 is not transitive because by definition if (2, 1), (1, 2) are in R6 then (2, 2) doesn't.
Example 14: Is the "divides" relation on the set of natural numbers transitive?
Solution: Relation "divide" is transitive on the set of natural numbers because if a | b and b | c
then certainly a | c.
Modular Arithmetic
In various situations we care only about the remainder of the integer when it is divided by
some positive integers. For instance, when we ask what will be the time on 24-hour clock after
100 hours from now, we care about the remainder obtained after adding the current time to
100 and dividing the result by 24. For example, let us suppose that it is 1 p.m. This means on 24-
hour clock, the time is 13.00 O' clock. Now, 13 + 100 = 113 when divided by 24 the
remainder is 19. This means, it will be 7 p.m. after 100 hours when we are asked the time at 1
p.m.
This phenomenon is written as : 113 | 24 = 19 or equivalently, we say that 113 is congruence to
19 modulo 24. Symbolically, we write as: 113 = 19 mod 24.
Definition: If a and b are integers and m is a positive integer, then a is congruence to b modulo m
if m divides (a - b) and is denoted by: a = b mod m.
The great German mathematician Karl Friedrich Gauss developed the concept of
congruence’s at the end of 18th century.
REMARK: (i) a = b mod m iff a mod m = b mod m.
(ii) a = b mod m (a – b) | m a = b + km
For instance, 19 mod 24 = 19 and 113 mod 24 = 19. Hence, 113 mod 24 = 19 mod 24.
Similarly, 17 ≡ 5 mod 6 →(17 -5) | 6 = 0 and 24 ≡ 14 mod 6, since (24- 14) | 6 = 10 | 6 ≠ 0.
Example 15: What are 113 mod 11 and -113 mod 11? Also evaluate -226 mod 3.
Solution: When 113 is divided by 11 the quotient will be 10 and remainder 3, that is, we
can express 113 = 11 (10) + 3. Thus, l 13 mod 11=3.
To find -113 mod 11, you just forget about negative sign and repeat the above process, that
is, when 113 is divided by 11 the quotient is 10 and remainder is 3. Now add 1 to the quotient
and subtract remainder 3 from the divisor 11, we get
-113 = l l ( - l l ) + (11 -3) = l l (- l l ) + 8.
Thus, -113 mod 11= 8. This means when -113 is divided by 1 l, the remainder is 8.
Finally to find -226 mod 3, divide 226 by 3, the quotient is 75 and remainder is 1.
Now add 1 to the quotient and subtract remainder 1 from the divisor 3, we get:
-226 = 3(-76) + (3 - 1) = 3(-76) + 2.
Thus, -226 mod 3 = 2. This means when -226 is divided by 3 the remainder is 2.
Theorem: Let m be a positive integer. The integers a and b are congruent modulo m if and only if
there is an integer k such that a = b + km.
Proof: If a = b(mod m), then m | (a – b). This means that there is an integer k such that a – b = km
(that is a – b is multiple of m). Above equation implies that a = b + km. Conversely, if there is an
integer k such that a = b + k m then k m = a – b or k = (a – b)/m. This implies that m divides
(a – b).
38
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
39
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
40
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
this to show how 1’s and 0’s are placed in the matrix MR. Now at the cross section of elements
(2, 1), (3, 1) and (3, 2) place 1 and place 0 otherwise. This is how we write the matrix MR
which is representation of the relation defined above.
Example 9: Suppose that A = {a1, a2, a3, a4} and B = {b1, b2, b3, b4, b5}. The matrix
representation of binary relation is given as under. What is R?
B
b1 b2 b3 b4 b5
a1 0 1 0 0 0
a2 1 0 1 1 0
A MR
a3 1 0 1 0 1
a4
1 1 0 1 0
Solution: The binary relation formed from the above matrix is under:
R = {(a1 b2), (a2, b1), (a2, b3), (a2, b4), (a3, b 1 ), (a3, b3), (a3, b5), (a4, b1), (a4, b2), (a4, b4)}
An Important Note: It may be noted that if matrix M R is square matrix, we can easily find out
whether the given relation is reflexive, symmetric or anti-symmetric.
If MR is such the all its main diagonal elements mii = 1, then R is reflexive since, (a, a) R.
If mii = mji that is if MR = (MR)T then R is symmetric since if (a, b) R → (b, a) R.
If mij = 1 for i≠ j, then mji = 0, that is if mij = 0 or mji = 0 when i≠ j, then R is anti-symmetric.
Example 10: Suppose that relation R on a set is represented by the matrix
1 1 0 1
1 1 1 0
MR
0 1 1 1
1 0 1 1
Is R reflexive, symmetric or anti-symmetric?
Solution: We see that all diagonal elements of matrix MR are equal to unity and moreover,
MR = (MR)T . Hence, relation R is reflexive as well as symmetric.
Representing Relations Using Digraphs
In the last section we have shown that a relation can be represented by a matrix consisting of 1’s
and 0’s. There is another important way of representation of binary relation using a pictorial
form. Here each element of a set is represented by a point, and each ordered pair is represented
by a directed line or arc. Such a visual representation of binary relation is known as digraph or
directed graph.
Definition: A directed graph or digraph, consists of a set of vertices (V) also called the nodes and a
set of ordered pairs called the edges or arcs (E). The vertex ‘a’ is called an initial vertex of the
edge (a, b), and the vertex b is called the terminal vertex of this edge. An edge (a, a) is
represented by using an arc from the vertex a to a. Such an edge is called a loop.
Example 11: The directed graph with edges a, b, c and d and edges (a, b), (b, b),
(b, c), (c, a), (c, b), (d, a), and (d, b) is shown in the following figure.
Here the set on which this relation is defined is A = {a, b, c, d}. The a b
relation R on a set A is represented by the digraph which, has the
elements of A as vertices and the ordered pairs (a, b) R as edges.
The digraphs are often used to study binary relations and their properties
such as reflexive, symmetric, anti-symmetric and transitive.
c d
41
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
a b
a
Fig. 1 Fig. 2
b c c d
Relation R1 Relation R2
Solution: In Fig. I, we see that there is a loop at every vertex hence, R1 is reflexive. R1 is
neither symmetric nor anti-symmetric since there is an edge from a to b but not from b to a.
Moreover, it contains (b, c) and (c, b) hence it is not anti-symmetric. R1 is not transitive because there
are edges (a, b) and (b, c) but not (a, c).
In Fig. II, there is no loop at vertex a hence, R2 is not reflexive. We also observe that there are
parallel edges (a, b) and (b, a), (a, c) and(c, a), (a, d) and (d, d). This means R2 is symmetric. R2 is not
transitive because (c, a) and (a, b) are in R2 but (c, b).
Equivalence Classes
Let A be the set of students in your class. Some of your class fellows must have passed
Higher Secondary School Certificate (HSSC) from the same college. Consider the equivalence
relation R on A that contains all pairs (a, b), where a and b are from the same college. Given a
student a, we can form the subset of A usually denoted by [a] which contains those students of your
class who were your class fellows in the college during HSSC. The set of all such elements is known
as "Equivalence Class" of binary relation of R.
Definition: Let R be an equivalence relation on a set A. For each element a A, the equivalence class
of a denoted by [a] is the set of all elements x A such that x is related to a by R.
Example 13: Let R be a binary relation on the set A = {0, 1, 2, 3, 4} as
R={(0, 0), (0, 4), (1,1 ), (1, 3), (2, 2), (3, 1), (3, 3), (4, 0), (4, 4)}. Find distinct equivalence
classes of R on the set A.
Solution: One may easily observe that R is reflexive, symmetric and transitive. Hence R is
an equivalence relation. The directed graph shown below also depicts this fact.
0 4 1 3
42
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
X f Y g
P A P A
(i) Q B (ii) Q B
R C R C
S D S D
h k
P A P A
(iii) Q B (iv) Q B
R C R C
S D S D
P A
(v) Q B
R C
S D
Definition: A relation between two sets X and Y is such that each element of set X has a unique image in
set Y is called a function and is usually denoted by f.
Thus if f is a function from set X to set Y we write this as: f : X Y . In particular, if x
and y are the elements of sets X and Y respectively, then we say that f is a function from the set
X to set Y and write y = f(x). The set X is called the domain of function f and the set Y is
called its co- domain. The set of those elements of Y which form the images of elements of
X is called range of function f. For example, range of functions f is{A, B, D}and that of g is
the set Y. The range of h is {B}.
Types of Functions
i. A function f from set X to set Y is called onto (or surjective) if Range (f) = Y.
ii. A function f from set X to set Y is called one-one (or injective) if
f x1 f x2 x1 x2 , x1 x2 in X.
iii. A function f from set X to set Y is called one-one and onto (or bijective) if f is both 1-1
and onto.
For example function g as shown above is 1-1 and onto. The function shown below is 1-1
but not onto. Here set X contains only three students and set Y contains four grades.
P A
Q B
R C
D
44
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
2 2
1 1
-2 -1 0 1 2 3 -3 -2 -1 0 1 2
-1 -1
-2 -2
officers? If it is allowed to send the officers partially, how many minimum buses are required for
this trip?
Solution: For the first case we use floor function given by 4327 45 96.15 96
Thus 96 buses are required to take all the officers on a trip where it is assumed that each bus
must take 45 officers.
If officers are allowed partially to use a bus, minimum number of buses required is:
4327 45 96.15 97 .
Example 4: By taking a counter example, show that: x y x y
Solution: Let x y 1 . Then x y 1
2
L.H.S.= x y 1 1 0.5 0.5 0 0 0
2 2
Now, R.H.S. x y 1 1 0.5 0.5 1 1
2 2
Hence, L.H.S. R.H.S.
46
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
The problem with this approach is that function H is onto but not one-to-one. It is onto function
because record of each employee has to be stored. It is not 1-1 because H might assign the
same position in the table with different employee ID No. For example,
H(223799068) = 223799068 mod 7 = 3
This means that the record of an employee with ID No 223799068 is to be stored in the
memory location 3 which is already filled. Such an assignment is called a collision. When
collisions occur, various collision resolution methods are used. One of the simplest methods
th
is to find the first memory location which is empty starting from the k position where this
record is to be placed in the memory. If there are not too many collisions, this is very efficient
way to store and locate the records.
Second Application: Pseudo-Random Numbers
Randomly chosen numbers are often needed for computer simulations. Different methods
have been devised for generating numbers that have properties of randomly chosen numbers.
Because numbers generated by systematic methods are not truly random, they are called Pseudo-
Random Numbers.
The most commonly used procedure for generating pseudorandom numbers is the linear
congruential method. Here we choose four integers: the modulus m, multiplier a, increment
c, and seed x0, with 2 a m, 0 c m, and 0 x0 m .
We generate a sequence of pseudorandom numbers {xn} with 0 x0 m for all n, by successively
using the equation:
xn1 axn c mod m
For instances, the sequence of pseudorandom numbers generated by choosing m = 9, a = 7,
c = 4, and x0 = 3, can be found as follows:
x1 = (7 x0 + 4) mod 9 = (7.3 + 4) mod 9 = 25 mod 9 = 7
x2 = (7 x1 + 4) mod 9 = (7.7 + 4) mod 9 = 53 mod 9 = 8
x3 = (7 x2 + 4) mod 9 = (7.8 + 4) mod 9 = 60 mod 9 = 6
x4 = (7 x3 + 4) mod 9 = (7.6 + 4) mod 9 = 46 mod 9 = 1
xs = (7 x4 + 4) mod 9 = (7.1 + 4) mod 9 = 11 mod 9 = 2
x6 = (7 xs + 4) mod 9 = (7.2 + 4) mod 9 = 1 8 mod 9 = 0
x7 = (7 x6 + 4) mod 9 = (7.0 + 4) mod 9 = 4 mod 9 = 4
x8 = (7 x7 + 4) mod 9 = (7.4 + 4) mod 9 = 32 mod 9 = 5
x9 = (7 x8 + 4) mod 9 = (7.5 + 4) mod 9 = 39 mod 9 = 3
x10 = (7 x9 + 4) mod 9 = (7.3 + 4) mod 9 = 25 mod 9 = 7
We observe that x0 = x9 = 3 and each new term of the above sequence depends on its previous
term, the sequence so generated will be:
3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7...
This sequence contains nine different numbers before repetition.
An Important Note: It may be misleading thought that the sequence repeats after nine terms
just because m = 9.
Let us see what happens if we take m = 8.
xl = (7 x0 + 4) mod 8 = (7.3 + 4) mod 8 = 25 mod 8 = 1
x2 = (7 x1 + 4) mod 8 = (7.1 + 4) mod 8 = 11 mod 8 = 3
x3 = (7 x2 + 4) mod 8 = (7.3 + 4) mod 8 = 25 mod 8 = 1
Since x0 = x2, we see that sequence repeats itself after two terms, that is: 3, 1, 3, 1, 3, 1...
47
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25
Example 1: What is the secret message produced from the message "ALI WILL MEET YOU IN
HYDERABAD".
Solution: We replace the letters in the message with numbers.
A L I W I L L M E E T Y O U
0 11 8 22 8 11 11 12 4 4 19 24 14 20
I N H Y D E R A B A D
8 13 7 24 3 4 17 0 1 0 3
3 14 11 25 11 14 14 15 7 7 22 1 17 23
11 16 10 1 6 7 20 3 4 3 6
Translating now each number according to the table given above we get the encrypted message:
"DOL ZLOO PHHW BRX LQ KBGHUDEDH".
If we wish to decrypt the above message, we use: F-1= (n - 3) mod 26
The above formula use by Julius Caesar was based on the formulae defined as above.
However, the general formula for encrypting and decrypting the secret messages are:
F(n) = (an + k) mod 26 for Encrypt
and F -1(n) = (an - k) mod 26 for Decrypt
Here a and k are any integers provided F is bijection function.
48
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
EXERCISES 03
1. Let S denote the set of students of the university and B denote the set of books in this
university library. Interpret the Cartesian product S B . Give a sensible example of
this binary relation.
2. Let S denote the names of street in Hyderabad and R denotes the set of residents of
Hyderabad. Interpret the Cartesian product S R . Give a sensible example of this
binary relation.
3. Determine which of the properties reflexive, symmetric, transitive apply to the
following relations on the set of people:
i. R= {(a, b) | a is the father of b} ii. R={(a ,b) a is the friend of b}
iii. R = {(a, b) a is the descendent of b} iv. R = {(a, b) \ a and b have the same parent}
v. R = {(a, b) a is_an uncle of b}
4. Let Abe the set of books for sale and assume that among these are books with
following properties.
Book Price Length
A Rs. 800 100 pages
B Rs. 2000 125 pages
C Rs. 1600 150 pages
D Rs. 800 200 pages
E Rs. 400 100 pages
i. Suppose (a, b) e R provided the price of book 'a' is greater than or equal to the
price of the book 'V AND length of 'a' is greater than or equal to length of 'b'. Is R
"Reflexive", "Symmetric", "Anti-symmetric", and "Transitive"?
ii. Suppose (a, b) e R provided the price of book 'a' is greater than or equal to the price
of the book 'b' OR length of 'a' is greater than or equal to length of 'b'. Is R
"Reflexive", "Symmetric", "Anti-symmetric", and "Transitive"?
5. Determine whether the relation R on the set of all Web pages is reflexive,
symmetric, anti-symmetric and/or transitive, where (a, b) e R if and only if:
i. Everyone who has visited Web page 'a' has also visited Web page 'b'.
ii. There are no common links found on both Web page 'a' and Web page 'b'.
iii. There is at least one common link on Web page 'a' and Web page 'b'.
iv. There is Web page that includes links to both Web page 'a' and Web page 'b'.
6. Represent each of the following binary relations on the set A = {1, 2, 3, 4} by
matrix.
i. {(1,1), (I, 2), (2, 2), (2, 4), (3,4), (4,1), (4, 3), (4, 4)}
ii. {(1,1), (1, 2), (1, 3)(2, 2), (2, 3), (3,3), (4, 2)}
iii. (1, 2), (1, 4), (2, 3), (2, 4), (3,1), (4, 3), (4, 4)}
7. List the ordered pairs in the relations on {1,2,3} represented by the following
matrices;
1 1 0 1 1 1 1 1 0
i. 1 0 1 ii. 0 0 0 iii. 1 1 1
1 0 0 1 0 1 0 1 1
Also draw the digraphs for these relations.
49
CHAPTER THREE DISCRETE MATHEMATICS RELATIONS & FUNCTIONS
b c c d
b c
a b
a b
c d
9. Determine which of the following congruence relations are true and which are false,
i. 17 = 2 mod 5 ii. 4 = -5 mod 7 iii. -2 = -8 mod 3 iv. -6 = 22 mod 2
10. Let R be the relation of congruence modulo 3. Which of the following equivalence
classes are equal?
i. [7] ii. [-4] iii. [-6] iv. [17] v. [4] vi. [27] vii. [19]
11. Let R be the relation of congruence modulo 7. Which of the following equivalence
classes are equal?
i. [35] ii. [3] iii. [-7] iv. [12] v. [0] vi. [-2] vii. [17]
12. Prove that for all integers m and n, m mod 3 = n mod 3 i f f m = n mod 3.
13. Each of the following relations is an equivalence relation. Describe the distinct
equivalence classes of each relation:
i. R is the relation defined on Z as: for all m, n ϵ Z, mRn iff 2 | (m - n).
ii. ii. R is the relation defined on Z as: for all m, n ϵ Z, mRn iff 4 | (m - n).
14. Prove or disprove by taking counter example(s) each of the following:
i. x x ii. 2x 2 x iii. x y x y 0 or 1
x 1
iv. xy x y v. x
2 2
15. Compute the following:
i. 19 mod 7 ii.-Ill mod 13 iii. 789 mod 23 iv. 0 mod 19
v. 3 mod 5 vi. -1 mod 3 vii. 4 mpd 1 viii. -123 mod 19
ix. -2002 mod 87 x. -100 mod 101
16. Encrypt the message "KNIGHTS ARE BRUTAL" using the following formulae:
i. F(n) = (n + 5) mod 26 ii. F(n) = (n - 4) mod 26 iii. F(n) = (n + 8) mod 26
17. Decrypt the following by using Caesar cipher:
i. EOXH MHDQV ii. WHVW WRGDB iii. HDW GLP VXP
50
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
C H A P T E R
4 THE INTEGERS
4.1 INTRODUCTION
A component of discrete mathematics relating to integers and their properties belongs to
the branch of mathematics called number theory (Number Theory in fact is called The
Queen of Mathematics). In this section we shall study some basic concepts of number
theory. This includes divisibility, great common divisors, and modular arithmetic.
Although we have discussed a little on modular arithmetic in previous chapters however,
we shall take care of this topic in more detail now. We shall also discuss some algorithms
to show their importance in computer based subjects.
The ideas that we shall develop in this chapter are based on the notation of divisibility. One
important concept based on divisibility is that of prime number. A prime number is an
integer greater than 1 that is divisible by 1 or the number itself. We shall also discuss
“Fundamental Theorem of Arithmetic” which asserts that every positive integer can be
expressed as the product of primes. Division of an integer by a positive integer produces
a quotient and a remainder. These remainders lead to modular arithmetic which is
extensively used in computer science applications.
Division
When an integer is divided by another non-zero integer, the quotient may or may not be
integer. For example, 16 ÷ 2 = 8 is an integer but 17 ÷ 2 = 8.5 is not an integer. This leads
to the following definition.
Definition: If a and b are integers with a ≠ 0, we say that a divides b if there is an integer c
such that b = ac. When a divides b we say that a is a factor of b and that b is a multiple of
a. The notation a | b is used when a divides b. The notation a b is used when a does not
divide b.
REMARK: a | b can be expressed by using quantifier as:
If a divides b then c such that ac = b, a, b, c Z .
For instance, 8 ÷ 2 = 4 → 2 | 8 which means that 2 divides 8 and 8 = 2(4).
Example 1: Let n and d be positive integers. How many positive integers not greater
than n exist that divide n.
Solution: If d | n then by definition there exists a positive number k such that n = k d. This
implies that k = n/d. Now k is a positive integer thus 0 < k ≤ n/d. Now if d = 1 then k = n
and if d ≠ 1 then k/n < n. Thus maximum positive integer numbers that divide n are
k = n/d . For instance 2 | 8 8/2 = 4. Thus maximum positive integers that divide 8 are 4.
They are 1, 2, 4, and 8.
51
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
Example 1: To find all the prime numbers less than or equal to 30.
Solution: We proceed as follows:
First generate a list of integers from 2 to 30:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
22 23 24 25 26 27 28 29 30
Strike out the multiples of 2 resulting in:
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
The first number in the list after 2 is 3; strike the multiples of 3 from the list to get:
2 3 5 7 11 13 17 19 23 25 29
The first number in the list after 3 is 5; strike the remaining multiples of 5 from the list:
2 3 5 7 11 13 17 19 23 29
The first number in the list after 5 is 7, but 7 squared is 49 which is greater than 30 so the
process is finished. First prime numbers from 2 to 30 are:
2 3 5 7 11 13 17 19 23 29
Theorem: If n is a positive composite integer, then n has a prime divisor less than or
equal to n .
Proof: Since n is composite hence it can be expressed as n = ma where both m and a are
positive integers with 1 < a < n. This implies that a n or m n , since
otherwise ma n . n ma n . Hence every positive composite number n has a
positive divisor not exceeding n . This divisor is either prime of composite. In either case,
n has a prime divisors less than or equal to n .
REMARK: If none of the prime factors divides n then n is a prime.
Example 2: How many prime divisors are possible for the positive integers 36 and
101.
Solution: Since 36 6 hence prime divisors of 36 that are less than 6 are 2 and 3.
Now, 101 10 and the prime factors less than 10 are 2, 3, 5, and 7. Since none of these
prime factors divide 101 hence, 101 is a prime number.
Algorithm to Compute Prime Factors of an Integer
Following steps may help to compute the prime factors of any integer n.
i. If n itself is a prime no further step is required.
ii. If n is not a prime then divide n by the prime factor p and compute n/p. The prime
factor might be one of prime numbers 2, 3, 5, 7, etc.
iii. If n/p is not a prime then find out the next prime factor say q and compute (n/p)/q.
iv. Continue with the above process till we reach the factor that is a prime.
Example 3: Fine the prime factorization of 7007.
Solution: 7007 is not divisible by 2, 3, or 5. However, 7 divides 7007 giving
7007/7 = 1001. Now we see that 1001 is also divisible by 7 giving 1001/7 = 143. Further
143 is divisible by 11 which is the next prime after 7. Now 143/11 = 13. Finally 13 is a
prime hence, no further division is required. Thus 7007 = 7 × 7 × 11 × 13 = 72 × 11 × 13
The Infinitude of Prime Numbers
It has long been known that there are infinitely many primes. We shall produce this fact
using a proof given by Euclid in his famous mathematics text the “Elements”. We will give
two other proofs due to Kummer and Filip Saidak.
54
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069
1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223
1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373
55
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511
1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657
1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811
1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987
1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129
2131 2137 2141 2143 2153 2161 2179 2203 2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287
2293 2297 2309 2311 2333 2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423
2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 2539 2543 2549 2551 2557 2579 2591 2593 2609 2617
2621 2633 2647 2657 2659 2663 2671 2677 2683 2687 2689 2693 2699 2707 2711 2713 2719 2729 2731 2741
2749 2753 2767 2777 2789 2791 2797 2801 2803 2819 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903
2909 2917 2927 2939 2953 2957 2963 2969 2971 2999 3001 3011 3019 3023 3037 3041 3049 3061 3067 3079
3083 3089 3109 3119 3121 3137 3163 3167 3169 3181 3187 3191 3203 3209 3217 3221 3229 3251 3253 3257
3259 3271 3299 3301 3307 3313 3319 3323 3329 3331 3343 3347 3359 3361 3371 3373 3389 3391 3407 3413
3433 3449 3457 3461 3463 3467 3469 3491 3499 3511 3517 3527 3529 3533 3539 3541 3547 3557 3559 3571
The following table shows different values of n, the ratio n/ln n and exact number of primes
less than n.
Exact No. of Primes
n n/ln n
<n
10 ~4 4
50 ~13 15
100 ~ 16 25
500 ~ 79 95
… … …
3571 ~ 436 500
Mersenne Primes
Many early writers felt that the numbers of the form 2n-1 were primes for all primes n, but
in 1536 Hudalricus Regius showed that 211-1 = 2047 was not prime since 2047 = 23 × 89.
By 1603 Pietro Cataldi had correctly verified that 217-1 and 219-1 were
both prime, but then incorrectly stated 2n-1 was also prime for 23, 29, 31
and 37. In 1640 Fermat showed Cataldi was wrong about 23 and 37;
then Euler in 1738 showed Cataldi was also wrong about 29. Sometime
later Euler showed Cataldi's assertion about 31 was correct. French
monk Marin Mersenne (1588-1648) stated in the preface to his
Cogitata Physica-Mathematica (1644) that the numbers 2n-1 were prime
Marin Mersenne
for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 and were composite for all other positive
integers n < 257. Mersenne's (incorrect) conjecture fared only slightly better than Regius',
but still got his name attached to these numbers.
Definition: The number of the form 2n-1 where n is also a prime is said to be a Mersenne
prime.
It was obvious to Mersenne's peers that he could not have tested all of these numbers (in
fact he admitted as much), but they could not test them either. It was not until over 100
years later, in 1750, that Euler verified the next number on Mersenne's and Regius' lists,
56
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
231-1, was a prime. After another century, in 1876, Lucas verified 2127-1 was also a prime.
Seven years later Pervouchine showed 261-1 was a prime, so Mersenne had missed this
one. In the early 1900's Powers showed that Mersenne had also missed the primes 289-1
and 2107 -1. Finally, by 1947 Mersenne's range, n < 258, had been completely checked and
it was determined that the correct list is: n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.
See the table of known Mersenne primes below.
Perfect Numbers
Many ancient cultures were concerned with the relationship of a number with the sum of its
divisors, often giving mystic interpretations. Here we are concerned only with one such
relationship:
Definition: A positive integer n is called a perfect number if it is equal to the sum of all
of its positive divisors, excluding n itself.
For example, 6 is the first perfect number because 6 = 1 + 2 + 3. The next perfect number
is 28 because its divisors are 1, 2, 4, 7, and 14 and their sum 1+ 2 + 4 + 7+ 14 = 28. The
next two prime numbers are 496 and 8128. These four were all known before the time of
Christ.
REMARK: (i) Readers are advised to find the divisors of 496 and 8128 excluding the
numbers by writing a computer program or otherwise and check that the sum of their
divisors is equal to these numbers respectively. (ii) All perfect number are even.
Now look at the numbers 2 (3), 4 (7), 16 (31), 64 (127) which are in partially factored
form. Do you notice they all have the same form 2n-1(2n-1) (for n = 2, 3, 5, and 7
respectively)? And that in each case the 2nd number 2n-1 was a Mersenne prime? Over
2300 years ago Euclid proved that if 2n-1 is a prime number it would be a Mersenne prime,
then 2n-1(2n-1) is a perfect number. A few hundred years ago Euler proved the converse that
every even perfect number has this form. It is still unknown if there are any odd perfect
numbers but if there are; they are large and have many prime factors. This is probably the
oldest unsolved problem in all of mathematics. So the search for Mersennes is also the
search for even perfect numbers!
You may have also noticed that the perfect numbers listed above (6, 28, 496, 8128) all end
with either the digit 6 or the digit 8 but they do may not continue to alternate 6, 8, 6, 8...
However, it is easy to prove the following theorems.
Theorem: If 2n-1 is a prime number, then 2n-1(2n-1) is a perfect number and every
even perfect number has this form.
Theorem: If for some positive integer n, 2n-1 is a prime, then so is n.
The proofs are beyond the scope of this book. Interested readers may see the proofs in any
e-book.
Table of Known Mersenne Primes
Let M(p) = 2p -1 and P(p) = 2p-1(2p - 1). The list of all known primes p for which M(p) is a
Mersenne prime (therefore P(p) is a perfect number) follows:
P Digits digits
## year Discoverer
(exponent) in Mp in Pp
1 2 1 1 ---- ----
2 3 1 2 ---- ----
3 5 2 3 ---- ----
57
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
4 7 3 4 ---- ----
5 13 4 8 1456 Anonymous
6 17 6 10 1588 Cataldi
7 19 6 12 1588 Cataldi
8 31 10 19 1772 Euler
9 61 19 37 1883 Pervushin
10 89 27 54 1911 Powers
11 107 33 65 1914 Powers
12 127 39 77 1876 Lucas
13 521 157 314 1952 Robinson
14 607 183 366 1952 Robinson
15 1279 386 770 1952 Robinson
16 2203 664 1327 1952 Robinson
17 2281 687 1373 1952 Robinson
18 3217 969 1937 1957 Riesel
19 4253 1281 2561 1961 Hurwitz
20 4423 1332 2663 1961 Hurwitz
21 9689 2917 5834 1963 Gillies
22 9941 2993 5985 1963 Gillies
23 11213 3376 6751 1963 Gillies
24 19937 6002 12003 1971 Tuckerman
25 21701 6533 13066 1978 Noll & Nickel
26 23209 6987 13973 1979 Noll
27 44497 13395 26790 1979 Nelson & Slowinski
28 86243 25962 51924 1982 Slowinski
29 110503 33265 66530 1988 Colquitt & Welsh
30 132049 39751 79502 1983 Slowinski
31 216091 65050 130100 1985 Slowinski
32 756839 227832 455663 1992 Slowinski & Gage et al.
p digits digits
## year discoverer
(exponent) in Mp in Pp
33 859433 258716 517430 1994 Slowinski & Gage
34 1257787 378632 757263 1996 Slowinski & Gage
Armengaud, Woltman,
35 1398269 420921 841842 1996
et al. (GIMPS)
Spence, Woltman,
36 2976221 895932 1791864 1997
et al. (GIMPS)
58
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
Clarkson, Woltman,
37 3021377 909526 1819050 1998 Kurowski
et al. (GIMPS, PrimeNet)
Hajratwala, Woltman,
38 6972593 2098960 4197919 1999 Kurowski
et al. (GIMPS, PrimeNet)
Cameron, Woltman,
39 13466917 4053946 8107892 2001 Kurowski
et al. (GIMPS, PrimeNet)
Shafer, Woltman, Kurowski
?? 20996011 6320430 12640858 2003
et al. (GIMPS, PrimeNet)
Findley, Woltman,
?? 24036583 7235733 14471465 2004 Kurowski
et al. (GIMPS, PrimeNet)
Nowak, Woltman,
?? 25964951 7816230 15632458 2005 Kurowski
et al. (GIMPS, PrimeNet)
Cooper, Boone, Woltman,
?? 30402457 9152052 18304103 2005 Kurowski
et al. (GIMPS, PrimeNet)
Cooper, Boone, Woltman,
?? 32582657 9808358 19616714 2006 Kurowski
et al. (GIMPS, PrimeNet)
Elvenich, Woltman,
?? 37156667 11185272 22370543 2008 Kurowski
et al. (GIMPS, PrimeNet)
Strindmo, Woltman,
?? 42643801 12837064 25674127 2009 Kurowski
et al. (GIMPS, PrimeNet)
Smith, Woltman, Kurowski
?? 43112609 12978189 25956377 2008
et al. (GIMPS, PrimeNet)
We have put question marks instead of a number for the the last of the Mersenne primes
because it will not be known if there are other Mersenne's in between these until a check
and double check has been completed by GIMPS. See the GIMPS Status Page for more
information. Not all smaller exponents have been tested.
4.3 THE GREATEST COMMON DIVISOR and THE LEAST COMMON MULTIPLE
In this section we shall study two important topics. They are:
(i) The Greatest Common Divisor
(ii) The Least Common Multiple
The Greatest Common Divisor
Let a and b be two non-zero integers. An integer g is said to be the greatest common
divisor (gcd) of a and b if and only if (i) g | a, g | b and (ii) if c is any other integer such
that c | a, c | b then c ≤ g. We write g = gcd (a, b) to signify that g is greatest common
divisor of a and b.
59
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
For instance:
i. gcd (15, 6) = 3 ii. gcd (-24, 18) = 6 iii. gcd (756, 210) = 42
iv. gcd (-756, 210) = 42 v. gcd (-756, -210) = 42
REMARK: If a and b are integers and a | b then gcd (a, b) = a. If a is non- zero integer
then gcd (a, 0) = |a|.
Euclidean Algorithm for Computing gcd
Let a and b be natural numbers with b < a. To find gcd of a and b, write:
a = q1 b + r1 with 0 ≤ r1 < b,
If r1 ≠ 0, write b = q2 r1 + r2 with 0 ≤ r2 < r1,
If r2 ≠ 0, write r1 = q3 r2 + r3 with 0 ≤ r3 < r2,
If r3 ≠ 0, write r2 = q4 r3 + r4 with 0 ≤ r4 < r3.
Continue this process until some remainder rk + 1 = 0. Then the gcd of a and b is rk, the last
non-zero remainder.
Example 1: Use Euclidean Algorithm to find the gcd of 630 and 196.
Solution: 630 = 3(196) + 42
196 = 4(42) + 28
42 = 1(28) + 14
28 = 2(14) + 0
The last non-zero remainder is 14 hence gcd (630, 196) = 14
REMARK: The gcd g of integers a and b can be expressed as linear combination of a and
b, that is, g = m a + n b.
As shown in the above example that gcd (630, 196) = 14. Thus we can express 14 as:
14 = m (630) + n (196)
To find m and n we see that n = (14 – 630 m)/196. Now we have to find integral value of m
for which n is also integer. By hit and trial method:
If m = -10 → n = 32.21 and if m = -9 → n = 29.
Thus for m = -9, n = 29. Both values are integers. Hence gcd 14 can be expressed as:
14 = -9 (630) + 29 (196) = -5670 + 5684 = 14
Prime Factorization Method of Finding gcd
Consider a and b with following prime factorization:
a p11 p2 2 p33 ... pnn and b p11 p22 p33 ... pnn
Here each exponent is a zero or positive integer, and all primes p1, p2, p3, … pn are included
in both factorization.
Then, gcd (a, b) = p1min( 1,1 ) p2 min( 2 ,2 ) p3min( 3,3 ) ... pn min( n ,n )
Example 2: Find the gcd of 140 and 400 using prime factorizing method.
Solution: 140 = 2× 2 × 5 × 7 = 22. 51. 71 and 400 = 2 × 2 × 2 × 2 × 5 × 5 = 24. 52. 70
Therefore, gcd (140, 400) = 2min(2, 4) . 5min(1, 2) . 7min(1, 0) = 22 . 51 . 70 = 4 × 5 × 1 = 20
Least Common Multiple
The least common multiple of the positive integers a and b is the smallest integer that is
divisible by a and b and is denoted by lcm(a, b).
Prime factorization method is also used to find the lcm of two positive integers. This is
given by: lcm (a, b) = p1max( 1,1 ) p2 max( 2 ,2 ) p3max( 3,3 ) ... pn max( n ,n )
Example 3: Find the lcm of 140 and 400 using prime factorizing method.
Solution: 140 = 2× 2 × 5 × 7 = 22. 51. 71 and 400 = 2 × 2 × 2 × 2 × 5 × 5 = 24. 52. 70
Therefore, lcm (140, 400) = 2max(2, 4) . 5max(1, 2) . 7max(1, 0) = 24 . 52 . 71 = 16 × 25 × 7 = 2800
60
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
REMARK: The relation between gcd and lcm of two positive integers a and b is given by
a b = gcd(a, b) lcm(a, b)
From the examples 2 and 3 above, 140 × 400 = 20 × 2800 → 56000 = 56000.
Relatively Prime Numbers
In mathematics, two integers a and b are said to be coprime or relatively prime if they
have no common positive factor other than 1 or, equivalently, if their greatest common
divisor is 1. The notation a b is sometimes used to indicate that a and b are relatively
prime. For example, 6 and 35 are coprime, but 6 and 27 are not coprime because they are
both divisible by 3. The number 1 is coprime to every integer.
A fast way to determine whether two numbers are coprime is given by the Euclidean
algorithm that uses the prime factorization method to get gcd of two positive integers. If
gcd of two positive integers is 1 then the numbers are co-prime.
In many problems we are interested to know that how many coprimes are available in
between 1 and n. The Euler totient or Euler phi function as discussed above help to find
such numbers. Here we reproduce it.
“Euler's totient function (or Euler's phi function) φ(n) for a positive integer n outputs
the number of integers between 1 and n which are coprime to n. We reproduce this
function here: If p is prime, then for integer k ≥ 1, φ(pk) = (p -1) pk – 1.
For instance, as mentioned above φ(9) = φ(32 ) = (3 – 1) . 32 – 1 = 2(3) = 6 (Here p = 3 and
k = 2). This means that there are 6 positive integers that are less than 9 and are relatively
prime or coprime to 9. They are: 1, 2, 4, 5, 7, and 8.
Similarly, φ(8) = φ(23 ) = (2 – 1) . 23 – 1 = 1(4) = 4. This means there are 4 positive integers
that are less than 8 and are relative prime or coprime to 8. They are 1, 3, 5, and 7.
REMARK: Relatively prime is a term that is seemingly misleading. The number 15 is
relatively prime to 16, but neither 15 nor 16 is a prime.
Euler’s phi function can be extended to compute the number of coprimes related to n that
have two or more prime factorization. The following examples show the process of finding
coprimes for such positive integers.
Example 4: How many positive numbers less than or equal to 15 are relatively prime
to 15?
Solution: First, factorize 15 into its primes: 15 = 3 1 · 5 1
Then, use the above formula:
For 3 1 , we get 3 - 1 = 2 and 3 1 - 1 = 3 0 = 1.
Also from 5 1 , we get 5 - 1 = 4 and 5 1 - 1 = 5 0 = 1.
Multiply all the new numbers together to get the answer. 2 × 1 × 4 × 1 = 8.
This means there are 8 coprimes that are less than 15. They are: 1, 2, 4, 7, 8, 11, 13, and 14.
Example 5: How many positive numbers less than or equal to 16 are relatively prime
to 16?
Solution: First, factorize 16 into its primes: 16 = 2 4
Then, use the formula:
For 2 4 , we get 2 - 1 = 1 and 2 4 - 1 = 2 3 = 8.
Multiply these two numbers together to get the answer. 1 × 8 = 8.
Thus there are 8 positive integers that are less than 16 and are coprime to it. They are: 1, 3,
5, 7, 9, 11, 13, and 15.
Example 6: How many positive numbers less than or equal to 144 are relatively prime
to 144?
Solution: Factorize 144 = 2 4 × 3 2.
61
CHAPTER FOUR DISCRETE MATHEMATICS THE INTEGERS
EXERCISES 04
1. Does 19 divide the following integers:
i. 114 ii 266 iii. 476 iv. 28158
2. Show that if b is a nonzero positive integer then
i. b divides 0 ii. 1 divides b.
3. Show that if a divides b and b divides a then either a = b or a = - b.
4. Prove that a | b and c | d if and only if ac |bd.
5. What are the quotient and remainder when:
i. 29 is divided by 8 ii. -111 is divided by 11 iii. 788 id divided by 27
iv. 0 is divided by 3 v. 7 is divided by 8 vi. -2 is divided by 5
6. Find the prime factorization of each of the following integers:
i. 78 ii. 136 iii. 825 iv. 100011 v. 111111 vi. 909090
7. Show that 28 and 496 are perfect integers.
8. Let N = 2n-1(2n – 1). Find n for which 2n – 1 is a prime. Use this value of n to show that N
is perfect. Is n prime?
9. Determine whether each of these integers is prime, verify some of Mersenne’s claims.
i. 27 -1 ii. 29 – 1 iii. 211 -1 iv. 213 -1
10. Evaluate φ(34), φ(56), φ(78), φ(95), and φ(134). In each case list the coprimes.
11. What are the gcds and lcms of the following pairs of integers?
i. 22. 33. 55 and 25. 33. 52 ii. 2.3.5.7.11.13 and 211.39.11.1714
2 3
iii. 2 .7 and 5 .13 iv. 0 and 7
v. 2.3.5.9 and 2.3.5.9 vi. 313.517 and 212.721
12. How many positive integers less than or equal to:
15 that are relatively prime to 15
46 that are relatively prime to 46
78 that are relatively prime to 78
92 that are relatively prime to 92
62
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
C H A P T E R
5 RECURRENCE RELATIONS
5.1 INTRODUCTION
A sequence can be defined in a variety of different ways. One way to define a sequence is
to write the few terms with the belief that the general model will be evident. For example,
consider the sequence “3, 5, 7… “. We ask a person about this sequence and his replay may
be that “this is a sequence of odd numbers starting from 3”. A second person may say that
“this is a sequence of odd prime numbers”. Thus a misunderstanding can occur when this
approach is used. The next term of the sequence could be 9 if we mean the sequence of odd
integers and it could be 11 if we mean the sequence of odd prime numbers.
A second way to define a sequence is to give an explicit formula for its nth term. For
example, a sequence a1, a2, a3 … may be specifies by
n
an for all n ≥ 0
2
n 1
Then, a1 = 1/2, a2 = 2/5, a3 = 3/ 10 and so forth.
A third way to define a sequence is to use recursion. This method of defining a sequence is
to write an equation, called recurrence equation that relates later terms in the sequence to
previous terms and a specification, called initial conditions which define the values of first
few terms. The initial conditions are also called the base or bottom of the recursion.
Definition: A recurrence relation for a sequence a0, a1, a2… is a formula that relates each
term an to its preceding terms along with the initial conditions.
Example 1: Consider the recurrence relation an = an-1 + an-2 where n ≥ 2 and with
initial conditions a0 = 2 and a1 = 3. Find the sequence represented by the above
recurrence relation.
Solution: Put n = 2, 3, 4 we get:
a2 = a1 + a0 = 3 + 2 = 5, a3 = a2 + a1 = 5 + 3 = 8, a4 = a3 + a2 = 8 + 5 = 13
Thus required sequence is: 2, 3, 5, 8, 13…
Example 2: Consider the recurrence relation an = an-1 + n an-2 + 2 where n ≥ 2 with
initial conditions a0 = 1 and a1 = 2. Find the sequence represented by this recurrence
relation.
Solution: Put n = 2, 3, 4 we get:
a2 = a1 + 2 a0 = 2 + 2.1 = 4, a3 = a2 + 3 a1 = 4 + 3.2 = 10, a4 = a3 + 4 a2 = 10 + 4.4 = 26
Thus required sequence is: 1, 2, 4, 10, 26…
REMARK: It may be noted that a sequence can be expressed in more than one way. For
instance, the following two sequences are same.
63
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
64
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
Solution: Let us assume that number of rabbit pairs after n months be fn. The rabbit’s
population can be modeled using the recurrence relation. The initial pair f0 = 1. At the end
of first month f1 = 1 since this pair does not breed. To find the number of pairs after n
months, add the number of pairs in previous month, fn, and the number of newborn pairs,
which is equals fn, since each newborn pair comes from a pair at least two months old. The
recurrence relation governing the above rabbit problem is given by:
fn = fn-1 + fn -2 where, f0 = 1 and f1 = 1 for n ≥ 2
For n = 2, f2 = f1 + f0 = 1 + 1 = 2
For n = 3, f3 = f2 + f1 = 2 + 1 = 3
For n = 4, f4 = f3 + f2 = 3 + 2 = 5
For n = 5, f5 = f4 + f3 = 5 + 3 = 8
The sequence f0, f1, f2, f3, f4… is known as Fibonacci sequence.
Let us assume that we wish to find f50. Clearly, we need to compute f49, f48, f47, f46 ... In the
coming sections we shall develop methods where the recurrence relations are solved
explicitly.
Example 3: (Tower of Hanoi) The “Tower of Hanoi, is a puzzle invented by E. Lucas
in 1883. Given a stack of n disks arranged from largest on the bottom to smallest on
top placed on a peg, together with two empty pegs, the towers of
Hanoi puzzle asks for the minimum number of moves required to
move the stack from one peg to another, where moves are allowed
only if they place smaller disks on top of larger disks. Design
recurrence relation that allows to find the number of moves to shift
all n disks from peg “A” to peg “B”.
Solution: (Recursive solution)
Eduardo Lucas
Let us call the three pegs A, B and C. To better understand and appreciate the following
solution you should try solving the puzzle for small number of disks, say, 2,3, and,
perhaps, 4. To solve the problem, by shifting all disks from A to C the disks will have to
be stacked in decreasing size order on peg B. After moving the bottom disk from A to C
these disks will have to be moved from B to C. Therefore, for a given number n of disks,
the problem appears to be solved if we know how to accomplish the following tasks:
1. Move the top n-1 disks from A to B (using C as an intermediary peg)
2. Move the bottom disk from A to C
3. Move n-1 disks from B to C (using A as an intermediary peg).
Let us assume that we have to shift three disks from peg A to peg C. The following steps
could solve the problem.
1. Move from A to C 2. Move from A to B 3. Move from C to B
4. Move from A to C 5. Move from B to A 6. Move from B to C
7. Move from B to C
This shows that if we have to move three disks from peg A to peg C the number of
required moves required is 23 -1 = 7.
Of course "Move" means moving the topmost disk from one peg to another. For n = 4 we
get the following sequence:
65
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
66
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
STORY OF TOWER OF HANOI: In the great temple at Benares beneath the dome
that marks the centre of the world, rests a brass plate in which are fixed three diamond
needles, each a cubit high and as thick as the body of a bee. On one of these needles,
at the creation, God placed sixty-four discs of pure gold, the largest disk resting on the
brass plate, and the others getting smaller and smaller up to the top one. This is the
tower of Brahma. Day and night constantly the priest transfer the discs from one
diamond needle to another according to the fixed and immutable laws of Brahma,
which require that the priest on duty must not move more than one disc at a time and
that he must place this disc on a needle so that there is no smaller disc below it. When
the sixty-four discs shall have been thus transferred from the needle which at creation
God placed them, to one of the other needles, tower, temple, and Brahmins alike will
crumble into dust and with a thunderclap the world will vanish. From the explicit
formula as shown above the priests require
264 – 1 = 18, 446, 744, 073, 709, 551, 615
moves to transfer all 64 disks. If we assume that one disk requires a second to be
shifted from one golden needle to another, it would take priests 500 billion years to
solve the puzzle. Thus the world should survive a while longer than it already has.
[Students are advised to see JAVA Applets on Tower of Hanoi by searching
“Tower of Hanoi” on Google].
67
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
Example 6: Consider the equation an = A (-1)n + B (-2)n+ C.3n, where A, B, and C are
an arbitrary constants. By eliminating the arbitrary constants, find the RR.
Solution: Given that: an = A(-1)n + B (-2)n + C.3n (i)
Replacing n by n + 1, n + 2 and n + 3 we obtain respectively,
an+1 = A(-1)n+1 + B(-2)n+1 + C.3n+1 = - A(-1)n -2 B(-2)n + 3C.3n (ii)
n+2 n+2 n+2 n n n
an+2 = A(-1) + B(-2) + C.3 = A(-1) +4 B(-2) + 9C.3 (iii)
n+3 n+3 n+3 n n n
an+3 = A(-1) + B(-2) + C.3 = - A(-1) -8 B (-2) + 27C.3 (iv)
Eliminating A, B, and C from (i) to (iv), we get
an+3 -7 an+1 - 6 an = 0
Note that in Examples 4, 5, and 6 the expressions of an as a function of n contains one, two
and three arbitrary constants respectively. Once these arbitrary constants are eliminated, we
get the general solution of “Recurrence Relations”.
Order of Recurrence Relation: The difference between largest and smallest sub-scripts in
a recurrence relation is called its order. For example, RR of example 4 is of order 1, RR of
example 5 is of order 2, RR of example 6 is of order 3.
In many situations, the solution of a RR has to satisfy certain conditions. These are called
initial conditions which are used to determine the arbitrary constants and to get an
“Explicit Solution” of recurrence relation.
Example 7: RR an+2 -6 an+1 + 9 an = 0 has general solution an = (A + B n).3n. If a0 = 1
and a1 = 15 then find the particular solution. Hence find a5.
Solution: Put n = 0 and n = 1 in the general solution, we get:
a0 = A = 1, a1 = 3(A + B) = 3(1 + B) = 15 B = 4
Thus particular solution of given RR an+2 -6 an+1 + 9 an = 0 is an = (1 + 4n).3n.
Now a5 = 21.35 = 5103.
5.3 SECOND ORDER LINEAR HOMOGENEOUS RECURRENCE RELATIONS
WITH CONSTANT COEFFICIENTS
In the above sections we discussed two important topics regarding the recurrence relations.
First was on the modeling where a recurrence relation occurs whose solution cannot be
found directly because it depends on the previous terms. For example in the sequence of
Fibonacci numbers if we ask what will be the number of rabbits after 50 months we may
not be able to give a quick answer until we calculate the values f49, f48, f47….
In the second part, we determined a recurrence relation by eliminating arbitrary constants.
For example, when the arbitrary constants A and B were eliminated from the equation
an = (A + B n).3n, the recurrence relation an+2 -6 an+1 + 9 an = 0 was obtained. The equation
an = (A + B n).3n forms a general solution of given recurrence relation an+2 -6 an+1 + 9 an =
0. Now if we are given a recurrence relation how can we find its solution. In this section we
are addressing this problem. For the sake of simplicity, we shall consider second order
homogeneous recurrence relation and extend the idea for the solution of higher order
recurrence relations.
Definition: A second order linear homogeneous recurrence relation with constant
coefficients is a recurrence relation of the form: A an+2 + B an+1 + C an = 0
for all integers n ≥ 0. Here A, B and C are fixed constants with A ≠ 0.
“Second order” refers to the fact that the expression for an contains two previous terms ak-1
and ak-2, “linear” to the fact that ak-1 and ak-2 appear in separate terms and to the first power,
68
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
“homogeneous” to the fact that there is no term other than ak-1 and ak-2 and “constant
coefficients” to the fact that A and B are fixed constants and do not depend on n.
Example 1: State which of the following is a second order linear homogeneous
recurrence relation with constant coefficients.
a. an+2 - 3 an+1 - 2 an = 0 b. an+3- an+2 + an+1 = 0
2
c. an+2 - 4 a n+1 + an=0 d. an+2 - 6 an = 0
e. an+2 - ani-1 + n an = 0 f. an+2 - an+1 + 2 = 0
g. an+2 - an+1 . an = 0 h. an+2 - n an = 0
Solution:
a. Yes.
b. No; it is linear, homogeneous RR with constant coefficients but of order 3.
c. No; it is of order two and is homogeneous but non-linear since an+1 appears with power
2.
d. Yes.
e. No; it is of order two but non constant coefficients.
f. No; it is non-homogeneous as it contains 2, a term other than an+2 and an+1.
g. No; it is non-linear since contains a term which is product of an+1 and an.
h. No; it is RR of second order but with variable coefficients.
Solution of 2nd Order Homogeneous Linear Recurrence Relation with Constant
Coefficients
Consider a second order linear homogeneous recurrence relation with constant coefficients:
A an+2 + B an-1 + C an-2 = 0 for all n ≥ 0 (i)
Here A, B and C are some fixed real constants. If we suppose that for any m ≠ 0, the
solution of this equation is of the form mn then an = mn, an+1 = mn+1 and an+2 = mn+2.
Substituting these in equation (i), we get:
A mn+ 2 + B mn+1 + C mn = 0
Dividing both sides by mn, we obtain:
A m2 + B m + C = 0 A m2 + B m + C = 0 (ii)
Equation (ii) is called “Characteristic Equation” of recurrence relation (i).
Since characteristic equation is a polynomial (here quadratic equation) so its root may be:
(a) real and distinct (b) real and equal (c) Complex and conjugates.
We produce here some examples to see how the solutions of RRs are obtained under these
cases. The theoretical proofs may be found in any book on Discrete Mathematics.
Example 2: Solve the following recurrence relation:
a. an+2 + 4 an+1 + 3 an = 0 b. an+2 - 6 an+1 + 9 an = 0
c. an+2 + 4 an = 0 d. an+2 - 2 an+1 + 2 an = 0
Solution:
(a) For given RR an+2 + 4 an+1 + 3 an = 0, the characteristic equation is m2 + 4m + 3 = 0.
Solving, we get: m = -1 and m = -3. We see that roots of characteristic equation are real and
distinct. Hence the sequences 1, -1, 1, -1 … and 3, -3, 3, -3, 3 … both satisfy given RR. To
see this, take an = 1, an+1 = -1 and an+2 = 1 and substitute these in given RR, we see that:
1 - 4 + 3 = 0. Similarly, if we take an = 3, an+1 = -3 and an+2 = 3 and substitute these in
given RR, we get: 3 -12 + 9 = 0. Now we see that general forms of these sequences are
69
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
{(-1)n} and {(-3)n}. Thus both sequences satisfy given RR. Thus, general solution of given
RR is: an = A (-1)n + B (-3)n .
(b) For given RR an+2 - 6 an+1 + 9 an = 0 the characteristic equation is m2 - 6m + 9 = 0.
Solving, we get: m = 3, 3. Since the roots of characteristic equation are real and same, the
general solution of given RR is: an = A (3)n + B n (3)n = [A + B n].(3)n.
Readers may note the solution carefully in case the roots of repeated or same.
Suppose that the roots of characteristic equation are 3, 3, 3. In this case the solution of
RR would be: an = A (3)n + B n (3)n + C n2 (3)n = [A + B n + C n2].(3)n.
REMARK: Readers are advised to check that the sequences: (i) 3, 32, 33 and (ii) 1. 3, 2. 32,
3. 33 satisfy given RR.
(c) For given RR an+2 + 4 an = 0 the characteristic equation is m2 + 4 = 0. Solving, we get:
m = ±i2. The roots of characteristic equation are complex and conjugate. Hence general
solution of given RR is:
n n
an= A (i2)n + B (-i2)n = 2 n Ai n B( i ) n 2 n A cos i sin B cos i sin
2 2 2 2
n n n n
2 n A cos i sin B cos i sin [Using De Mover’s Theorem]
2 2 2 2
n n n n
a n 2 n A B cos i( A B ) sin 2 n C cos D sin
2 2 2 2
is a solution of given RR.
(d) For given RR an+2 - 2 an+1 + 2 an = 0 the characteristic equation is m2 - 2m + 2 = 0.
Solving, we get: m = 1 ± i. The roots of characteristic equation are complex and conjugate.
Hence general solution of given RR is:
an = A (1 + i)n + B (1 -i)n [Note: (1 ± i) = √2(cosπ/4 ± i sin π/4)
n n n n
= A1 i n B1 i n 2 n / 2 A cos i sin B cos i sin
4 4 4 4
[Using De Mover’s Theorem]
n n n n
a n 2 n / 2 A B cos i( A B ) sin 2 n / 2 C cos D sin
4 4 4 4
is a solution of given RR.
Finding the Particular Solution of Recurrence Relation
In example 2(a) we observed that the sequences 1, -1, 1... and 3, -3, 3… satisfy RR
an+2 + 4 an+1 + 3 an = 0. The general solution of this RR is an = A (-1)n + B (-3)n . Putting n
= 0 in given RR, we get a2 + 4a1 + a0 = 0. Now if we take a0 = 1 and a1 = 3 and substituting
these in given RR, we obtain: a2 + 4(3) + 1= 0 a2 = -13 and we see that -13 is not a
term of any of the above sequences, that is 1, -1, 1… or 3, -3, 3…. The numbers a1, a0 are
known as initial values. Now if we are asked to find a solution of RR an+2 + 4 an+1 + 3 an =
0 that satisfies given initial conditions a0 = 1 and a1 = 3, we proceed as under:
Put n = 0 and 1 respectively in the general solution an = A (-1)n + B (-3)n of given RR, we
obtain: a0 = A + B = 1 and a1 = -A -3B = 3
Solving we get: A = 3 and B = -2. Placing these values in the general solution of RR we
70
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
b. The numbers 1 5 / 2 and 1 5 / 2 are related to golden ratio of Greek
mathematicians. Why these numbers are given this name by Greeks? To answer this
question, consider a square of length “L” and height 1 where L > 1. 1
This is shown in the figure.
As we see that square is 1 unit on each side and the rectangle has
sides of length 1 and L – 1. The ancient Greeks considered the
outer rectangle to be perfectly proportioned (saying that the lengths 1
of the sides were in golden ratio to each other) if the ratio of the
length to the width of the outer rectangle equals the ratio of the L-1
length to the width of the inner rectangle. L
This means, L/1 = 1/(L – 1). Simplifying, we: L2 – L -1 = 0
This is nothing but the characteristic equation of Fibonacci RR. If we call its solutions L1
n 1
n 1
and L2 then solution of Fibonacci sequence is also expressed as: f n L1 L2 / 5 .
Here, L1 1 5 / 2 and L2 1 5 / 2
Non-Homogeneous Linear Recurrence Relations with Constant Coefficients
In this section we shall discuss the solutions of second order non-homogeneous linear
recurrence relation with constant coefficients. Its general form is:
71
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
RR (i).
The complementary function an(c) is found by the same method as define in the section of
“Solution of homogeneous linear recurrence relation” and particular integral an(p) is found
by the method of “Undetermined Coefficients”. This method is based on assuming a trial
which depends on the form of f(n) and which contains number of arbitrary constants. This
trial function is then substituted into the RR (i) and these undetermined constants are to be
found by comparing the similar terms.
The basic trial forms are given in the following table below.(c denotes a constant in the
expression f(n) and A denotes a constant to be determined.
It may be noted that we shall solve only limited problems where f(n) is of the form cnk. The
solutions when f(n) takes other forms can be dealt in the same manner.
72
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
73
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
74
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
75
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
C C++
#include <stdio.h> #include <iostream>
#include <sys/types.h> using namespace std;
u_int ackermann(u_int m, u_int n) long ackermann(long,long);
{ int main()
if ( m == 0 ) return n+1; {
if ( n == 0 ) cout << ackermann(3,2) << endl;
{ }
return ackermann(m-1, 1); {
} long ackermann(long m, long n)
return ackermann(m-1, ackermann(m, n- {
1)); if (n == 0) if (m == 0)
} return n+1;
if (n == 0)
int main() return ackermann(m-1, 1);
{
int m, n; NOTE: Ackermann proved that A is a
recursive function, a function that a
for(n=0; n < 7; n++) computer with unbounded memory can
{ calculate, but it is not a primitive recursive
for(m=0; m < 4; m++) function, a class of functions including
{ almost all familiar functions such as
printf("A(%d,%d) = %d\n", m, n, addition and factorial. Thus it is not
ackermann(m,n)); difficult to show that the Ackermann
} function is well defined.
printf("\n"); The following is an example of a recursive
} definition that does not define a function.
}
Output excerpt:
A(0,4) = 5
A(1,4) = 6
A(2,4) = 11
A(3,4) = 125
Example 1: Show that the “Recursive Function” defined below is not well defined.
1 if n 1
n
B( n ) 1 B if n is even
2
B( 3n 1 ) if n is odd and n 1
Solution: Suppose B is a function. Then by definition of B,
B(1) = 1, B(2) = 1 + B(1) = 1 + 1 = 2,
B(3) = B(8) = 1 + B(4) = 1 + [1 + B(2)] = 1 + (1 + 2) = 4,
B(4) = 1 + B(2) = (1 + 2) = 3.
Now B(5) = B(14) = 1 + B(7) = 1 + B(20) = 1 + (1 + B(10)) = 1 + (1 + (1 + B(5)))
84
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
EXERCISES 05
1. Find the terms indicated in the following recursively defined sequences.
i. an = an-1 + n an-2 + 1 with a0 = 1 and a1 = 2, n = 2, 3, 4, 5.
ii. an = 2 an-1 + n with a0 = 1, n = 1, 2, 3, 4.
iii. an = n (an-1 )2 + 2.k with a0 = 1, n = 1, 2, 3, 4.
2. Show that:
i. an = 3n + 1 satisfies the RR an = an-1 + 3, n > 0.
ii. an = 5n satisfies the RR an = 5an-1, n > 0.
iii. an = 2n -1 satisfies the RR an = 2.an-1 + 1, n > 0.
3. Use the recurrence relation defined in the “Tower of Hanoi” compute H7 and H10.
4. Use the formula for Fibonacci sequence fn = fn-1 + fn-2 , f0 =1 and f1 = 1, compute f13 and
n 1 n 1
1 1 5 1 5
.
f14. Compare the results by using the formula f n
5 2 2
5. Prove the following for the Fibonacci sequence:
i. f 2n - f 2n-1 = f n. fn+1 - fn+1 fn-1, n > 0.
ii. f 2n+1 - f 2n – f 2n-1 = 2 fn fn-1, n > 0.
iii. f 2n+1 - f 2n = fn-1 fn+2, n > 0.
iv. fn+2 – f 2n+1 = (-1)n, n > 0. [Hint: Use Mathematical Induction]
6. Solve the following RR:
i. an+2 – 6 an+1 - 7 an = 0 ii an+2 + 10 an+1 + 25 an = 0
iii. an+3 – 6 an+2 + 9 an+1 – 4 an = 0 iv. an+2 - 4 a+1 + 8 an = 0
v. an+3 + 5 an+2 + 12 an+1 – 18 an = 0
7. For each of the general solution of the following RRs.
i. an+2 + 4 an+1 - 5 an = 4 ii. an+2 - 9 an = 3n
iii. an+2 + 4 an+1 - 5 an = n2 + n + 1 iv. an+2 - 6 an + 9 an = 3n + 7n
85
CHAPTER FIVE DISCRETE MATHEMATICS RECRRENCE RELATIONS
86
CHAPTER SIX DISCRETE MATHEMATICS MATHEMATICAL INDUCTION
C H A P T E R
6 MATHEMATICAL INDUCTION
6.1 INTRODUCTION
In mathematics there are many statements that depend upon the natural numbers.
Mathematical Induction is a tool that provides the proof of the truth ness of such
statements. For example, if one claims that number P defined as P = n2 - n + 41 always
provides a prime number greater than or equal to 41 by taking few values of n say:
n = 1 P = 1 – 1 + 41 = 41 (a prime number)
n = 2 P = 4 – 2 + 41 = 43 (a prime number)
n = 3 P = 9 – 3 + 41 = 47 (a prime number)
n = 4 P = 16 – 4 + 41 = 53 (a prime number)
Then as soon as we take n = 41, we obtain P = 412 – 41 + 41 = 412 = 1681 which is not a
prime as it is divisible by 1, 41 and 1681. Thus we must have a way that helps to determine
whether or not the given proposition is valid for all natural number n. Mathematical
induction is a right tool to use to see the validity of such propositions.
Before we establish the principle of mathematical induction (M.I) let us address another
example that will help readers the importance of M.I.
PROBLEM 1: A certain store sells envelopes in packages of five and packages of twelve
and you want to buy n envelopes. Prove that for every n ≥ 45, the store can fill an order for
exactly n envelopes (assuming an unlimited supply of each type of envelope package).
Proof: If you want to purchase 45 envelopes, you can buy nine packages of five. If you
want to buy 46 envelopes, you can buy three packages of twelve and two packages of five.
If you want to buy 47 envelopes, you buy one package of twelve and seven packages of
five and if you want 48 envelopes, you would purchase four packages of twelve.
The obvious difficulty with this way of attacking the problem is that it never ends. For
supposing that we obtain with difficulty to answer the question for n as big as 250, say,
could we be sure of a solution for n = 251? What is needed is a general, not an ad hoc way
to continue. This means that is it possible to fill an order for exactly k envelops at this store,
we would like to be able to deduce that the store can also fill an order for k + 1 envelopes.
Then, knowing that we can purchase exactly 45 envelopes and knowing that we can always
continue, we could deduce that we can purchase exactly 46 envelopes. Knowing this, and
knowing that we can always continue, we could know that we can purchase exactly 47
envelopes, and so on.
PROBLEM 2: Some people claim that Rp. 1 coin in Pakistan should now be abolished.
They point out that frequently a person who drops this coin on the ground does not bother
to pick it up. Other people argue that abolishing Rp. 1 coin would not give enough
flexibility for pricing merchandise. What prices could still be paid with exact change if
87
CHAPTER SIX DISCRETE MATHEMATICS MATHEMATICAL INDUCTION
Rp. 1 coin were abolished and another coin worth Rs. 2 were used instead? The answer is
that the only prices that could not be paid with exact change would be Rs. 1 and Rs. 3. In
other words: Any whole number of rupees at least 4 can be obtained using Rs. 2 and Rs. 5
coins. More formally, for all natural numbers n ≥ 4, P(n) is true where P(n) is the statement
or proposition “n rupees can be obtained using Rs. 2 and Rs. 5 coins”
This is depicted in the following table.
Number of How to obtain it Number of How to obtain it
Rs. Rs.
Rs. 4 Rs. 2 + Rs. 2 Rs. 9 Rs. 2 + Rs. 2 + Rs. 5
Rs. 5 Rs. 5 Rs. 10 Rs. 5 + Rs. 5
Rs. 2 + Rs. 2 + Rs. 2 +
Rs. 6 Rs. 2 + Rs. 2 + Rs. 2 Rs. 11
Rs. 5
Rs. 7 Rs. 2 + Rs. 5 Rs. 12 Rs. 2 + Rs. 5 + Rs. 5
Rs. 2 + Rs. 2 + Rs. 2 + Rs. 2 + Rs. 2 + Rs. 2 +
Rs. 8 Rs. 16
Rs. 2 Rs. 5 + Rs. 5
These examples demonstrate the key ingredients of a proof by mathematical induction.
Principle of Mathematical Induction
Let P(n) be a proposition that is defined for integers n, and let `a` be a fixed integer.
Suppose the following two statements are true:
(i) P(a) is true.
(ii) For all integer k ≥ a, if P(k) is true then P(k + 1) is true.
Then the statement: for all n ≥ a, P(n) is true.
NOTE: The first step is known as BASIC STEP and the second one is known as
INDUCTIVE STEP.
In our first example, we had to prove that any order of n envelopes, n ≥ 45, could be filled
with packages of five and twelve: a was 45 and the induction hypothesis was the
assumption that there was a way to purchase k envelopes of five and twelve.
In the second example, let us assume that P((n) be the proposition “Rs. n coin can be
obtained using coins of Rs. 2 and Rs. 5”. Then P(n) is true for all integers n ≥ k. The proof
is as follows:
Proof: The proposition is true for n = 4 because Rs. 4 = Rs. 2 + Rs. 2.
If the proposition is true for n = k, then it is true for n = k + 1, for suppose that Rs. k can be
obtained using Rs. 2 and Rs. 5 coins for some k ≥ 4. (This is inductive hypothesis). We
must show that Rs. (k + 1) can also be obtained using Rs. 2 and Rs. 5 coins. If suppose
there is a Rs. 5 coin in Rs. k, then replace Rs. 5 coin by three coins of Rs. 2; the result will
be Rs. (k + 1). In case Rs. 5 coin is not used to make up the Rs. k then, at least two coins of
Rs. 2 are used as k ≥ 4. Thus replacing these two coins with Rs. 5 coin; the result will be
Rs. (k + 1). Thus in either case Rs. (k + 1) can be obtained using Rs. 2 and Rs. 5 coins.
Our next example is suggested by the following pattern. Notice that:
1 = 1 = 12
1+3 = 4 = 22
1+3+5 = 9 = 32
1+3+5+7 = 16 = 42
1+3+5+7+9 = 25 = 52
88
CHAPTER SIX DISCRETE MATHEMATICS MATHEMATICAL INDUCTION
From the above pattern it seems that sum of the first odd integers is equal to n2. The figure
below adds force to this possibility.
1
3
5
7
9
Example 1: Prove that for any integer n ≥ 1, the sum of first odd integers from 1 to
(2n -1) is equal to n2.
Proof: The given proposition is
P(n) = 1 + 3 + 5 + … + (2n – 1) = n2.
i. Basic Step:
Put n = 1, we get P(1) = 1. Put n = 2, we get P(2) = 1+ 3 = 4 = 22. Put n = 3, we get
P(3) = 1 + 3 + 5 = 9 = 32.
ii. Inductive Step:
Let given proposition be true for n = k, that is, P(k) = 1 + 3 + 5 + … + (2k – 1) = k2. Now
adding (2k – 1+ 2) on both sides we get,
1 + 3 + 5 + … + (2k – 1) (2k – 1 + 2) = k2 + (2k – 1 + 2)
1 + 3 + 5 + … + (2k – 1) [2(k + 1) - 1) = k2 + 2k + 1 = (k + 1)2.
Now replacing (k + 1) by n we get: 1 + 3 + 5 + … + (2n – 1) = n2, which is the required
proposition P(n). Hence by mathematical induction P(n) is true for all integral values of
n ≥ 1.
Example 2: Prove that for any integer
n ≥ 1, 12 + 22 + 32 + … + n2 = [n (n + 1) (2n + 1)]/6.
Proof: Given proposition is 12 + 22 + 32 + … + n2 = [n (n + 1) (2n + 1)]/6.
Basic Step:
Put n = 1, we get 12 = [1(1 + 1)(2+ 1)]/6 = 6/6 = 1 1 = 1 (This is true).
Put n = 2, we get 12 + 22 = [2(2+1)(2.2 + 1)]/6 = [2.3.5]/6 5 = 5 (This is true).
Put n = 3, we get 12 + 22 + 32 = [3(3+1)(2.3 + 1)]/6 = [3.4.7]/6 14 = 14 (This is true).
ii. Inductive Step:
Let given proposition be true for n = k,
that is, P(k) = 12 + 22 + 32 + … + k2 = [k (k + 1) (2k + 1)]/6
Now adding (k + 1)2 on both sides we get
k k 12k 1 k 2k 1
12 2 2 3 2 ... k 2 k 12 k 1 k 1
2
k 1
6 6
k 1
2k 2 k 6k 6 k 1 2k 2 7k 6
6 6
k 1 2k 2 4k 3k 6 k 1 2k k 2 3 k 2
6 6
k 1k 22k 3 k 1k 22k 2 1
6 6
k 1k 1 1 2k 1
6
Replacing (k + 1) by n we obtain: P(n) = 1 + 22 + 32 + … + n2 = [n (n + 1) (2n + 1)]/6.
2
89
CHAPTER SIX DISCRETE MATHEMATICS MATHEMATICAL INDUCTION
Which is the required proposition P(n). Hence by mathematical induction P(n) is true for
all integral values of n ≥ 1.
Example 3: Prove that for any integer n ≥ 1, 22n – 1is divisible by 3.
Basic Step:
When n = 1, we get 22 – 1 = 4 – 1 = 3 which, is divisible by 3.
When n = 2, we get 22.2 – 1 = 24 – 1 = 16 – 1 = 15 which, is divisible by 3.
When n = 3, we get 22.3 – 1 = 26 – 1 = 64 – 1 = 63 which, is divisible by 3.
Thus basic step is true.
ii. Inductive Step:
Let given proposition be true for n = k, that is, P(k) = 22k -1 is divisible by 3. This implies
that we can assume that 22k – 1 = 3p where p is any positive integer. Then 22k = 3p + 1.
Now,
P(k + 1) = 22(k + 1) – 1 = 22k + 2 – 1 = 22k . 22 – 1 = 4.(3p+ 1) - 1 = 12 p + 4 – 1 = 12p – 3
= 3(4p -1). This number is multiple of 3 hence is divisible by 3 so P(k + 1) is also true.
Hence by mathematical induction P(n) is true for all integral values of n ≥ 1.
Example 4: Prove that for any integer n ≥ 4, n! > 2n.
Basic Step:
When n = 4, we get 4! > 24 24 >16. This is true.
When n = 5, we get 5! > 25 120 >32. This is true.
When n = 6, we get 6! > 26 720 >64. This is true. This proves the basic step.
ii. Inductive Step:
Let given proposition be true for n = k, that is, P(k) = k! > 2k. Multiplying both sides by
(k + 1), we have:
(k + 1) k! > (k + 1) 2k. But k ≥ 4 hence (k + 1) ≥ 4 > 2. Now, (k + 1) k! = (k + 1)! and (k +
1) 2k ≥ 2. 2k = 2k+1 Thus, (k + 1)! ≥ 2k+1 for all k ≥ 4. This is P(k + 1). By mathematical
induction therefore, P(n) is true for all integral values of n ≥ 1.
Example 5: Prove that for any positive integer n ≥ 0, 1 + 2 + 22 + 23 + … + 2n = 2n+1 - 1.
Basic Step:
When n = 0, we get 1 = 20+1 – 1 = 2 – 1 = 1. This is true.
When n = 1, we get 1 + 2 = 22 – 1 3 = 3. This is true.
When n = 2, we get 1 + 2 + 22 = 23 – 1 7 = 7. This is true.
ii. Inductive Step:
Let given proposition be true for n = k, that is, P(k) = 1 + 2 + 22 + 23 + … + 2k = 2k+1 - 1.
Adding 2k + 1 on each side, we obtain,
1 + 2 + 22 + 23 + … + 2k + 2k+1 = 2k+1 – 1 + 2k+1 = 2.2k+1 -1 = 2(k+1) + 1 – 1.
Now replacing k + 1 by n we get:
1 + 2 + 22 + 23 + … + 2n = 2n+1 – 1.
Thus P(k + 1) is also true. Hence by mathematical induction P(n) is true for all n ≥ 0.
Strong Mathematical Induction
Let P(n) be a proposition/predicate that is defined for integer n, and let a and b be fixed
integers with a ≤ b. Suppose the following statements are true:
i. Basic Step: P(a), P(a + 1), …, and P(b) are all true.
ii. Inductive Step: For some element k > b, if P(m), is true for all integer m where
a ≤ m ≤ k, then P(k) is true. Then P(n) is true for all n ≥ a.
90
CHAPTER SIX DISCRETE MATHEMATICS MATHEMATICAL INDUCTION
Example 6: Prove that any integer greater than 1 is divisible by a prime number.
Proof (Basic Step): Let P(n) be the proposition that “n is divisible by a prime number”.
Using strong mathematical induction, the proposition holds for 2 because 2 is a prime an 2
divides 2, that is, 2|2.
(Inductive Step): Let k be an integer with k > 2. Suppose that for all integer m with 2 ≤ m
< k, k is divisible by a prime number. Now if k is a prime then k is divisible by itself. If k
not a prime then k = a . b where a and b are integers with 2 ≤ a < k and 2 ≤ b < k. By the
inductive hypothesis, a is divisible by a prime number p, and so by transitivity of
divisibility, k is also divisible by prime number p. Hence, regardless of whether k is a prime
or not, k is divisible by a prime number. This completes the proof.
6.2 WELL-ORDERING PRINCIPLE
Let U be a set containing one or more integers all of which are greater than some fixed
number. Then U has a least element.
Example 1: For the following set, state whether or not well-ordering principle is valid
or not.
i. The set of all positive real numbers
ii. The set of all non-negative integers n such that n2 < n
iii. The set of all non-negative integers of the form 46 – 7n, where n is an
integer.
Also state violation of well-ordering property occurs in each case.
Solution: (i) The set of all real positive numbers does not satisfy well-ordering property
because if we assume that x is a least positive element of it then x/2 is less than x and is also
positive and real. The violation does not occur because this set contains many elements.
(ii) This set does not satisfy the well-ordering property because there is no non-negative
integer that satisfies this property. For example 12 < 1, 22 < 2, … are all non-true. The
violation of well-ordering property does not occur because this set contains no element.
(iii) Let us first consider the following table showing the values of n and 46 – 7n.
N … -3 -2 -1 0 1 2 3 4 5 6 7 …
46 – 7n … 67 60 53 46 39 32 25 18 11 4 -3 …
For n ≥ 7, 46 – 7n turns out to be negative. From the table we see that 4 is the first non-
negative value of the form 46 – 7n which occurs when n = 6. Hence this set satisfies well
ordering property with least value of n = 6.
91
CHAPTER SIX DISCRETE MATHEMATICS MATHEMATICAL INDUCTION
EXERCISES 06
1. Use principle of mathematical induction to prove the following propositions:
n( n 1 )( 2n 1 )
(i) 12 22 32 ...n2
6
n( n 1 )( n 2 )
(i) (ii) 1.2 2.3 3.4 ... n( n 1 )
3
2
n( n 1 )
(ii) (iii) 13 2 3 33 ...n 3
2
1 1 1 1 n
(iv) ...
1.2 2.3 3.4 n.( n 1 ) n 1
(iv) 1.21 2.22 3.23 ... n.2n 2 n.n2
(v) 1( 1! ) 2( 2! ) 3( 3! ) ... n( n! ) ( n 1 )!1
1 1 1 1 n 1
(vi) 1 .1 .1 ...1 , n2
22 32 42 n2 2n
92
CHAPTER SIX DISCRETE MATHEMATICS MATHEMATICAL INDUCTION
9. Suppose that f(x) = x ex. Use M. I to prove that that f n(x) = (x + n) ex.
10. Is the following proof by M. I for the proposition produced as under where n is a
positive integer true?
1 1 1 1 3 1
P( n ) ...
1.2 2.3 3.4 ( n 1 ).n 2 n
1 3 1 1 1
Basic step: The result is true for n = 1 because P( n )
1.2 2 1 2 2
Inductive step: Assume that result is true for n = k. Then
1 1 1 1 3 1
P( k ) ...
1.2 2.3 3.4 ( k 1 ).k 2 k
1
Adding on both sides the term , we obtain
( k 1)
1 1 1 1 1 3 1 1
...
1 .2 2 . 3 3 . 4 ( k 1 ).k k ( k 1 ) 2 k k ( k 1 )
3 1 1 1 3 1
2 k k ( k 1) 2 ( k 1)
Replacing (k + 1) by n, we get the required proposition.
93
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
C H A P T E R
7 COUNTING TECHNIQUES
7.1 INTRODUCTION
Combinatorics which is the study of arrangements of objects has remained an important
part of discrete mathematics. This subject was studied as long ago as 17th century, when
combinatorial questions arose in the study of gambling games. Counting of an objects with
certain properties is an important part of combinatorics. For instance, suppose we wish to
find out whether or not the telephone lines at a switch board are enough to meet the
requirement of the users, or to see how many passwords are possible to be created from the
given digits and alphabet, or to see that in how many ways a salesman can complete his
tour visiting given number of areas of a city. Combinatorics (counting techniques) is the
right choice to study such problems.
The Basics of Counting
Before we define the basic counting rules consider the following problems:
i. Suppose we are asked to find out the number of passwords comprising of ten
digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 and twenty six small case alphabets ‘a’
through ‘z’ where the condition is that the first character must be from alphabet.
How many such passwords can be design?
ii. Suppose you invite your friend at dinner. You tell him that you can prepare only
four items from out of ten available items. In how many ways you prepare the
dinner for your friend?
iii. Suppose you wish to appoint three people out of five for three posts which are
of same grades. In how many ways you can appoint these persons?
Counting problems such as above arise in mathematics, computer science and many other
fields of engineering, social and natural sciences. We shall introduce the basic rules of
counting, the product or multiplicative rule and sum or additive rule and then show that
how these rules are applied to solve different types of counting problems.
REMARK: It may be noted that multiplicative rule is used when a complete task or
procedure is based on separate tasks where as the sum rule is based on the principle where
we are asked to find the number of tasks which can be performed in either way.
The Rule of Product
Suppose a complete task or a process is broken down into different tasks T1, T2, …, Tn,
where task T1 is achieved in m1 ways, task T2 is achieved in m2 ways given that task T1 has
already been performed. The task T3 is performed in m3 ways given that both tasks T1 and
T2 have been completed, and finally the task Tn is performed into mn ways given that all
tasks T1, T2, …,Tn-1 have been performed. Then the complete procedure can be performed
into m1 . m2 . m3 .… mn ways.
94
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
For instance, assume that a license plate contains two letters followed by three digits. In
how many different ways the license plates can be printed? The simple reply is that each
letter can be printed in 26 ways, and each digit can be printed in 10 ways, so 26 · 26 · 10 ·
10 · 10 = 676000 different plates can be printed.
Some other simple examples are listed below. Readers are advised to use product law and
convince themselves the results are given.
3 shirts, 4 pairs of pants, and 2 pairs of shoes give 3.4.2 = 24 possible outfits to
wear.
10
10 coin flips result in 2 possible outcomes.
3
3 rolls of a six-sided die gives 6 possible outcomes.
6 5
10 possible strings of six decimal digits, but only 9(10) six-digit decimal
numbers since the first digit cannot be zero. (See the difference between two
problems)
3 3
10 . 26 possible license plates can be formed with three letters followed by
three digits.
5
26 sequences of five letters can be formed from the complete alphabet.
There are 12.11.10.9 = 11,880 ways that four books out of a bag of 12 books
can be placed on a shelf.
5.4.3.2.1 = 5! = 120 strings from the letters A, B, C, D, and E can be formed.
26.25.24.23.22 = 7,893,600 five-letter words with distinct letters are possible.
9.9.8.7.6 = 27,216 five-digit numbers with distinct digits are possible to be
framed (note the first digit can’t be zero).
n
26.25 words of length n that don’t contain a double letter – the first letter can
be any letter, the second can’t equal the first, the third can’t equal the second,
etc…
The Rule of Sum
If a task can be performed in m ways, while another task can be performed in n ways, and
the two tasks cannot be performed simultaneously, then performing either task can be
accomplished in m + n ways.
For instance, if a class has 30 male students and 25 female students and a student is to be
chosen to attend a conference on discrete mathematics then, we have 30 + 25 = 45 choices
to choose a student.
Let us consider another example where a student is asked to choose a project out of three
lists and each list contains 20, 30 and 10 projects. Then the student has 20 + 30 + 10 = 60
choices to take any project.
Product and sum rules can always be phrased in terms of sets in the following way:
i. Let A1, A2, …, An be the finite sets, then number of elements in the cartesian
product of these sets is the product of the numbers of elements in each set. Notice
that the cartesian product A1 × A2 × ... × An is done by choosing an element in A1,
an element in A2, …, and an element in An. By the product law it follows that:
|A1 × A2 × … × An | = | A1| | A2| … | An |
ii. Let A1, A2, …, An be the finite disjoint sets, then number of elements in the union
of these sets is the sum of the numbers of elements in each set. Notice that the
union A1 A2 ... An is done by choosing an element from each Ai which is
95
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
done in |Ai| ways. By the sum rule it follows that: |A1 A2 ... An | = | A1| + |
A2| + … + | An |.
Computer programmers are effectively using the nested loops. The following two programs
depict the outputs for the product and sum rules. Students are advised to run these
programs using any high level language. We produce the algorithms only.
What is the output when the following programs are executed?
The first program uses multiplication rule due to nested loops. The second program uses
the sum rule where instead of nested loop an individual loop is used where value of m is
carried over to the next loop.
The Inclusion-Exclusion Principle
The inclusion-exclusion principle generalizes the rule of sum to non-disjoint sets. In
general, for arbitrary (but finite) sets A, B: |A B| = |A| + |B| − |A B|.
Example 1: Assume that in a university with 1000 students, 200 students are taking a
course in mathematics, 300 are taking a course in physics, and 50 students are taking both.
How many students are taking at least one of those courses?
Solution: If U = total set of students in the university, M = set of students taking
Mathematics, P = set of students taking Physics, then:
|M P| = |M| + |P| − |M P| = 300 + 200 − 50 = 450
This shows that 450 students are taking Mathematics or Physics.
For three sets the following formula applies:
|A B C| = |A| + |B| + |C| − |A B| − |A C| − |B C| + |A B C|.
7.2 COMBINAORICS
As mentioned earlier that combinatorics is the study of arrangements of objects. This
arrangement is performed in two ways namely by permutation and by combination. We
shall now discuss them separately.
Permutations
Assume that we have n objects. Any arrangement of these elements taking any k of these in
a given order is called a permutation of size k. If k = n then we call it just a permutation of
the n objects. For instance, the permutations of the letters a, b, c are the following: abc,
acb, bac, bca, cab, cba. The permutations of size 2 of the letters a, b, c, d are: ab, ac, ad,
ba, bc, bd, ca, cb, cd, da, db, dc. Note that the order is important. Given two permutations,
they are considered equal if they have the same elements arranged in the same order.
96
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
We define the number P(n, k) of permutations of size k of n given objects in the following
way: The first object in an arrangement can be chosen in n ways, the second one in (n − 1)
ways, the third one in (n − 2) ways, and so on, hence:
P(n, k) = n × (n − 1) × · · · × (n − k + 1) = n! / (n − k)!, where n! = 1 × 2 × 3 × · · · × n is
called “n-factorial”.
The number P(n, n) of permutations of n objects is P(n, n) = n!. By convention 0! = 1.
For instance, there are 3! = 6 permutations of the 3 letter a, b, c. The number of
permutations of size 2 of the 4 letters a, b, c, d is P(4, 2) = 4 × 3 = 12.
Combinations
Assume that we have a set A with n objects. Any subset of A of size r is called a
combination of n elements taken r at a time. For instance, the combinations of the letters a,
b, c, d, e taken 3 at a time are: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde, where two
combinations are considered identical if they have the same elements regardless of their
order. The number of subsets of size r in a set A with n elements is:
C(n, r) =n!/[r! (n − r)!].
n n
The symbol or
r C (read “n choose r”) is often used instead of C(n, r).
r
One way to derive the formula for C(n, r) is the following: Let A be a set with n objects. In
order to generate all possible permutations of size r of the elements of A (i) take all possible
subsets of size r in the set A, and (ii) permute the k elements in each subset in all possible
ways. Task (i) can be performed in C(n, r) ways, and task (ii) can be performed in P(r, r)
ways. By the product rule we have P(n, r) = C(n, r) × P(r, r), hence
C(n, r) = P(n, r)/ P(r, r) = n!/[r! (n − r)!]
Example 1: Six flights are scheduled from city A to B and then back from B to A. In
how many ways a person can go to A from B and then return to A if he doesn’t take
the same flight for his return journey.
Solution: The person can go from A to B in six ways. For the return journey he cannot take
the same flight thus he can return in five ways. Therefore, the total numbers of ways are
6 × 5 = 30.
Example 2: How many three digit numbers can be made out of the digita from 1 to 9
without repeating any number?
Solution: There are total 9 numbers, i.e., n = 9. One is supposed to select 3 numbers and
form a three digit number, i.e., r = 3. Therefore, the total numbers which can be formed are
P(9, 3) = 9! / 6! = 504.
Alternatively, 3 numbers can be selected out of 9 in C(9, 3) ways. Now the selected three
numbers can be arranged in 3! ways. Therefore, total ways = 3! × C(9, 3) = 504.
Example 3: In how many ways can the letters of the word “COMPUTER” be
arranged (i) without any restriction (ii) ‘M’ must always occur at the third place
(iii) all the vowels are together (iv) all the vowels are never together (v) vowels occupy
the even positions.
Solution: There are total 8 letters with 3 vowels and 5 consonants.
(i) The word “COMPUTER” can be arranged in P(8, 8) = 8! Ways without any
restriction, that is; any letter can be placed any where without repetition.
(ii) If M occurs at the third place then this position is fixed and the remaining seven
letters are to be arranged. This can be done in P(7, 7) = 7! ways.
(iii) Let us treat all the vowels as a single entity. Now there are 5 consonants plus 1
group of vowels which can be arranged in 6! ways among themselves. Now,
97
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
98
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
8!
That is, C (8, 4) 70 ways
4!.4!
Example 8: There are six questions in a question paper. In how many ways can a
student solve one or more questions?
Solution: The student can solve the question or he may not. Thus there are two ways
associated with each question. Hence for 6 questions there are 26 ways to deal with. But the
boy has to solve at least one question. So he cannot leave all the questions. Thus the total
number of ways = 26 – 1 = 63.
Example 9: There are 4 copies of 5 different books. In how many ways can they be
arranged on a shelf?
Solution: Since there are 4 copies alike in each set of 5, hence the numbers of
20!
20 4!
5
arrangements are:
4!4! 4! 4! 4!
Example 10: In how many ways a committee of 2 boys and 3 girls can be made out of
5 boys and6 girls.
Solution: Selecting 2 boys out of 5 can be done in C5,2 10 ways . Selecting 3 girls out
of 6 can be done in C6,3 20 ways
Therefore, total number of ways = 10 20 200 ways
Example 11: Find the number of ways a baseball team consisting of nine people can
arrange themselves in a line for a group picture.
Solution: The standing order is part of what makes one picture different from another. We
are dealing with a permutation. We are choosing from a group of 9 objects, choosing all 9.
There are P(9, 9) or 9! = 362,880 ways the nine people can arrange for the picture.
Example 12: Find the number of ways a representative group of 3 from the nine-man
baseball team can be chosen and arranged in a row for a picture.
Solution: The arrangement matters, so we will use permutations. From a group of 9, we are
choosing 3. There are P(9, 3) = 504 ways to select a subgroup of 3 people from the team
and arrange them for a picture.
Example 13: A representative group of three from a nine-man baseball team will be
chosen for a picture. Find the number of different representative groups of 3 that can
be chosen.
Solution: The arrangement doesn’t matter, we are counting different groups. This is a
combination, NOT a permutation. From a group of 9, we are choosing 3. The answer is
C(9, 3) = 84. There are 84 different groups of 3 that could be created.
Example 14: Find the number of ways the twelve men in a garden club can choose a
President, Vice-President, and Secretary-Treasurer.
Solution: The arrangement matters, so we will use permutations. From a group of 12, we
are choosing 3. There are P(12,3) = 1,320 different ways to choose a President, Vice-
President, and Secretary-Treasurer.
Example 15: A Senate investigations committee of four members is to be selected from
a larger group of ten members. Determine the number of ways this can be done.
Solution: This calls for application of the combination principle. A committee of four is
the same committee no matter how many times they rearrange in their chairs. From a group
of 10, we are choosing 4. The answer is C(10,4) = 210. There are 210 different committees
of four that could be chosen from the 10 members.
99
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
Example 16: How many 5-card hands can be dealt from a standard deck of 52 cards?
Solution: With card hands, like committee members, you can rearrange them all day long
and it is the same group (the same card hand). Re-arrangements of a particular group don’t
present a different option, so the order is not significant. We use combinations. From a
group of 52, we are choosing 5. The answer is C(52, 5) = 2,598,960. There are 2,598,960
possible 5-card hands that could be dealt from a standard deck.
Example 17: Ali has 4 history books, 5 grammar books, and 7 math books. If she is
going to place the books on a shelf where only three of each type can be displayed, and
all the books of each type are together, how many arrangements are possible?
Solution: This problem uses both the concept of permutations and the concept of the
multiplication principle.
Task 1: Select and arrange the history books. P(4, 3) = 24.
Task 2: Select and arrange the grammar books. P(5, 3) = 60.
Task 3: Select and arrange the math books. P(7, 3) = 210.
Task 4: Arrange the groups. P(3, 3) = 6.
Total number of arrangements: 24 x 60 x 210 x 6 = 1,814,400
Example 18: John goes fishing and catches 5 catfish, 3 perch, 4 bass, and 7 flounder.
He decides to choose 2 catfish, 1 perch, 2 bass, and 3 flounder for a fish fry for his
friends. In how many ways can those selections be made?
Solution: This is a combination application, with multiple tasks that call for the application
of the multiplication principle. There is also an assumption here that the fish are unique.
For example, each bass is different from the other 3 basses (in size, etc).
Task 1: Choose 2 catfish from the group of 5. C(5, 2) = 10.
Task 2: Choose 1 perch from the group of 3. C(3, 1) = 3.
Task 3: Choose 2 bass from the group of 4. C(4, 2) = 6.
Task 4: Choose 3 flounder from the group of 7. C(7, 3) = 35.
Total number of ways to make the selections: 10 x 3 x 6 x 35 = 6,300.
Example 19: The members of an octet, composed of three clarinet players, three trumpet
players, and two trombone players are to be selected from a group of six clarinet players,
five trumpet players, and four trombone players. In how many ways can the octet be
formed if the music requires the trumpet players to have designated positions?
Solution: This problem involves permutations and combinations, as well as the multiplication
principle.
Task 1: Choose the 3 clarinets from the choice of 6. C(6, 3) = 20.
Task 2: Choose the 3 trumpets from the group of 5 P(5, 3) = 60
Task 3: Choose the 2 trombones from the group of 4. C(4, 2) = 6
Total number of ways to make the selections: 20 x 60 x 6 = 7,200
Example 20: From the twenty members of the Spunky Spellers club, five members will be
chosen to represent the club at a national contest. Two alternates will also be chosen. In
how many ways could the contestants and alternates be selected? (Note: A strong
argument can be given for why the two alternates should be “ordered”. However, some
texts have been known to have similar problems where the alternates were not ordered
(using a combination rather than a permutation).
Solution: Task 1: Choose the 5 contestants. C(20, 5) = 15,504.
Task 2: Choose the 2 alternates (now there are only 15 spellers to choose from)
P(15, 2) = 210.
Total number of ways to make the selections: 15,504 × 210 = 3,255,840.
100
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
Example 21: A Mortgage company has 10 new mortgages to process. In how many
ways can these new mortgages be distributed to five of the company’s processors, if
each processor is to handle two mortgages?
Solution: 10 mortgage packets must be placed on 5 desks (2 per desk).
Task 1: Choose the 2 mortgages to be put on processor #1’s desk. C(10, 2) = 45.
Task 2: Choose the 2 mortgages to be put on processor #2’s desk. C(8, 2) = 28.
Task 3: Choose the 2 mortgages to be put on processor #3’s desk. C(6, 2) = 15.
Task 4: Choose the 2 mortgages to be put on processor #4’s desk. C(4, 2) = 6.
Task 5: Choose the 2 mortgages to be put on processor #5’s desk. C(2, 2) = 1.
Total number of ways to distribute the mortgages: 45 × 28 × 15 × 6 × 1 = 113,400.
Example 22: (The quorum concept) The local math club has 18 members. When
official club business is conducted, they must have a quorum of 12 members present.
How many different ways can the math club have a quorum of members?
Solution: If 12 members constitute a quorum, then in order to conduct business at least 12
members must be present. That means that either 12, 13, 14, 15, 16, 17, or 18 members can
be in attendance to have a quorum.
Computation 1: the # of ways to have exactly 12 people present C(18, 12) = 18,564.
Computation 2: the # of ways to have exactly 13 people present C(18, 13) = 8,568.
Computation 3: the # of ways to have exactly 14 people present C(18, 14) = 3,060.
Computation 4: the # of ways to have exactly 15 people present C(18, 15) = 816.
Computation 5: the # of ways to have exactly 16 people present C(18, 16) = 153.
Computation 6: the # of ways to have exactly 17 people present C(18, 17) = 18.
Computation 7: the # of ways to have exactly 18 people present C(18, 18) = 1.
Note that these are NOT separate Tasks to be completed in succession as separate pieces in
the completion of one overall task. The multiplication principle does NOT apply.
We ADD: 18,564 + 8,568 + 3,060 + 816 + 153 + 18 + 1 = 31,180 possible quorums.
Note: A problem stating that a majority of members need to be present would involve the
same concept. The difference is that you have to compute the number that makes a majority
(more than half).
Cautions: As you practice a variety of mixed problems that involve one or more of the
multiplication principle, permutations, and combinations – you might feel as if a dense fog
has settled. The only way out of the fog is to keep working problems until the air clears
again. You have to practice enough to lift the fog!
A point to remember: Neither the permutation formula nor the combination formula
handles repetitions. If you are allowing repetitions of letters, digits, etc. (such as creating
passwords, phone numbers, social security numbers, serial numbers, etc), you will be using
the multiplication principle (see the format for those type of examples in earlier notes)
Example 23: Find the number of permutations that can be formed from all the letters
in the word CABINET.
Solution: All the letters in the word CABINET are different. From 7 letters, we are
choosing all 7 to make an arrangement. The number of permutations is P(7,7) = 5,040.
Note: It is important to realize that the letters in the word are all different. If they were not,
the solution would be slightly more complicated.
Distinguishable Permutations involving Indistinguishable Objects
Example 24: Find the number of (visibly) different arrangements (distinguishable
permutations) that can be formed from all the letters in the word ATLANTA.
101
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
Solution: The idea here is that for a given permutation such as ATATLAN, rearranging the
two T’s or any of the three A’s doesn’t give another visibly unique arrangement. If your
back was turned when the T’s were switched, you wouldn’t know the difference. The
number generated by P(7,7) would include ATATLAN and ATATLAN (I switched the
T’s, can you tell?). Since we don’t want those types of switches counted as different
arrangements, we have to divide out the duplicates.
The computation 7!/(2!3!) or P(7, 7)/(2!3!) will divide out the duplication in the 2 T’s and
the 3 A’s. There are 420 distinct permutations.
Example 25: There are 6 black dogs, 3 brown dogs, and 2 white dogs to be lined up
for a dog show. How many different color sequences are possible?
Solution: We would generally assume dogs to be unique, so if it was a question of simply
ordering the dogs for the show, the answer would be P(11, 11). However, if only the color
sequences are under consideration, then the 6 black dogs are all identical in that respect.
We need to divide out the duplicate sequences that would be formed by switching, for
example, any 2 black dogs.
The computation 11!/(6!3!2!) or P(11,11)/(6!3!2!) will divide out the duplication in the
color sequences. There are 4,620 ways different color sequences.
Example 26: Jim is organizing his closet. He will hang his slacks together in groups by
color. He has 6 black slacks, 3 of which are identical. He has 4 pair of grey slacks, 2 of
which are identical. He has 5 pair of khaki slacks, all of which are identical. In how
many distinguishable ways can he order the slacks in his closet? [Finish the work
below, for a final count. Can you explain the parts in the solutions?]
Solution: P(3,3) × P(6, 6)/3! × P(4, 4)/2! × P(5, 5)/5! = 720 × 12 × 1 = 8460.
7.3 PIGEOHOLE PROBLEM
The pigeonhole principle is used for proving that a certain situation must actually occur. It
says the following: If n pigeonholes are occupied by m pigeons and m > n, then at least one
pigeonhole is occupied by more than one pigeon. For example, in any
given set of 13 people at least two of them have their birthday during the
same month.
The Pigeonhole Principle was first used by Dirichlet in Number Theory.
The term pigeonhole actually refers to one of those old-fashioned
writing desks with thin vertical wooden partitions in which to file
letters. Johann Peter Gustav Lejeune Dirichlet (13 February 1805 – 5
May 1859) was a German mathematician credited with the modern
Gustav Dirichlet
formal definition of a function.
Example 1: Let S be a set of eleven 2-digit numbers. Prove that S must have two
elements whose digits have the same difference (for instance in S = {10, 14, 19, 22, 26,
28, 49, 53, 70, 90, 93}, the digits of the numbers 28 and 93 have the same difference:
8 − 2 = 6, 9 − 3 = 6.)
Solution: The digits of a two-digit number can have 10 possible differences (from 0 to 9).
So, in a list of 11 numbers there must be two with the same difference.
Example 2: Assume that we choose three different digits from 1 to 9 and write all
permutations of those digits. Prove that among the 3-digit numbers written that way
there are two numbers whose difference is a multiple of 500.
Solution: There are 9 · 8 · 7 = 504 three-digit numbers. Now if we divide these 504 three-
digit numbers by 500 we can get only 500 possible remainders, so at least two numbers
give the same remainder, and their difference must be a multiple of 500.
102
CHAPTER SEVEN DISCRETE MATHEMATICS COUNTING TECHNIQUES
EXERCISE 07
1. Prove that if we select n + 1 numbers from the set S = {1, 2, 3, . . . , 2n}, among the
numbers selected there are two such that one is a multiple of the other one.
2. Use any appropriate technique that has been presented.
A bag contains five zucchini squash and four yellow squash. In how many ways can a
shopper select a sample of four squash if
a) There are no restrictions?
b) All must be zucchini?
c) Half are zucchini, and half are yellow?
d) At least two are zucchini?
3. Four girls and six boys form a Physics club. How many different ways can a President, a
Vice-President, a Secretary-Treasurer, and a committee of three be chosen, if no person can
serve two roles, and
a) there are no other restrictions?
b) only boys serve as officers, and only girls serve on the committee?
c) girls must be President and Vice-President and boys must fill the other roles?
4. How many different five-card hands have:
a) exactly one diamond?
b) exactly two aces and one king?
c) at least three spades?
5. There are 6 math classes into which 18 students will be placed. In how many ways can
these students be assigned into these classes if an equal number of students is placed in
each class?
6. Solve the following problems:
a) Using the digits 4, 5, 6, and 7, how many two-digit numbers can be formed (i)
without repetition? (ii) with repetition?
b) Using the digits 4, 5, 6, 7, 8, and 9, how many five-digit numbers can be formed
(i) without repetition? (ii) with repetition?
c) Using the digits of problem 7, how many four-digit odd numbers can be formed
without repetition?
10. In how many ways can the 18 members of a boy scout troop elect a president, a vice-
president, and a secretary, assuming that no member can hold more than one office?
11. How many different ways can 4 red, 3 blue, 4 yellow, and 2 green bulbs be arranged on a
string of Christmas tree lights with 13 sockets?
12. How many car tags can be made if the first three positions are letters and the last three
positions are numbers (Hint: Twenty-six letters and ten distinct single-digit numbers are
possible) (i) with repetition? (ii) without repetition?
13. A lady wants to select one cotton shirt and one polyester shirt from a collection of 8 cotton
shirts and 11 polyester shirts. In how many ways can the lady choose the two shirts?
14. In how many ways can 6 men and 5 women be seated in a line so that no two women sit
together?
15. In how many ways can 10 examination papers be arranged so that best and the worst are
never together?
16. In how many ways can three prizes be distributed among 4 boys when (i) No one gets more
than one prize. (ii) A boy can get any number of prizes.
17. How many three digit numbers are there, with distinct digits, with each digits odd?
18. Given 6 flags of different colors, how many different signals can be generated, if a signal
requires the use of two flags one below the other?
103
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
C H A P T E R
8 GRAPH THEORY
8.1 INTRODUCTION
Graph theory is an old subject with numerous modern applications. Its basic ideas were
introduced in the 18th century by Euler. He used graphs to solve the famous Königsberg
Bridge Problem, which we shall discuss in coming sections. Beginning his scientific
career shortly after the death of Sir Isaac Newton, Euler spent the last 17 years of his life
blind, but still very active. Besides his tremendous work in mathematics, perhaps less
known is that Euler was a superb designer of algorithms; he had the supernatural ability
of making order of chaos (disorder), of seeing simple routes through the most
complicated situations. It is because of his imaginative solution to Königsberg Bridge
Problem that Euler is generally considered as the father of modern Graph Theory.
(Königsberg was destroyed in World War II and renamed Kaliningrad and is a
westernmost city in Russia). The Pregel River flowed through town and split into two
branches around Kneiphof Island, which is labeled 1 in figure below. Seven bridges
crossed the river providing links among the four lands masses labeled 1, 2, 3 and 4 in the
figure. People wondered if it were possible to start on one of the land masses, walk over
each of the seven bridges exactly once and return to the starting point without getting
wet.
Euler’s idea was to realize that the physical layout of land, water, and bridges could be
modeled by the graphs shown in the 3rd figure. The land masses are represented by small
circles (or vertices) and the bridges by lines (or edges) which can be straight or curved.
By means of this graph, the physical problem is transferred into mathematical one: Given
the graph in figure 3 above, is it possible to choose a vertex, then to proceed along the
edges one after the other and return to the chosen vertex covering every edge exactly
once? We shall return to this problem and discuss its solution in coming sections.
The Three Houses – Three Utilities Problem
This is another physical situation which can be modeled by means of graph. There are
three houses; each one is to be connected to each of three utilities – water, electricity and
telephone by means of underground pipes. The problem is to see whether or not it is
104
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
possible to make these connections without any crossovers. The houses and utilities are
represented by vertices and the pipes are the lines (edges) drawn between the vertices.
When we discuss planner graphs in the coming sections, we shall see that answer to this
question is “no”.
Let us consider another example. Suppose that an organization that has six computers
wishes to upgrade computer services by connecting them to form an integrated network
within the organization. It is not necessary that every computer be linked with the other
one. The organizations requirement is as under:
Connect computer A with B, C, D and E; Connect computer B with A, and C;
Connect computer C with A, B, D and E; Connect computer D with A, and C;
Connect computer E with A, C, and F Connect computer F with E.
This information can be conveniently displayed in the diagram shown below called the
graph. B
Having used the term graph, it is time now to define the
word properly and to introduce some related A C
terminologies of graph theory.
DEFINITION: A simple graph G = (V, E) consists V, a F
D
non empty set of vertices, and E, a set of unordered
pairs of distinct elements of V called edges. E
Another definition of graph is: A Graph is a mathematical abstraction that is useful for
solving many kinds of problems. A graph consists of a set of vertices, and a set of edges,
where an edge is something that connects two vertices in the graph.
More formally, a graph G = (V, E) consists of a nonempty set V (the vertices of G) and a
set E of two element subsets of V (the set of edges of V).
Example 1: The G with V = {a, b, c, d} and E = {{a, b}, {a, d},{b, d},{c, d}} is a graph
with four vertices and four edges. We can obtain a diagram of a graph G by using dots as
the vertices and lines or curves as the edges connecting the appropriate dots. The diagram
in the figure 1 is one representation of the graph G shown below.
a d a b
b c
c d
Fig. 1 Fig. 2
Figure 2 is the graph with vertex set V = {a, b, c, d, e} and edge set E = {{a, b}, {b, c},
{b, d}, {c, d}, {c, e}}.
105
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
In high class of integrated intranet or internet one computer is connected with the other
via two or more lines in order to control a heavy data flow between the two. This is
illustrated below. Simple graphs are not sufficient to model such network. Instead, we use
multi-graphs which consist of vertices and undirected edges between these vertices, with
multiple edges between pairs of these vertices. b
DEFINITION: A multi- graph G = (V, E) consists
a
V, a non empty set of vertices, a set E of edges, c
and a function f from E to {(u, v) | u, v є V, u ≠ v}.
The edges e1 and e2 are called parallel edges if d
f
f(e1) = f(e2)
REMARK: e
(i) If e is an edge between two vertices u and v, Computer Network with multiple lines
we write f(e) = (u, v).
(ii) The parallel edges in a multi-graph are associated to same pair of vertices, that is,
if e1 and e2 are parallel edges then f(e1) = {u, v} = f(e2). b
Pseudo graph: A computer network may contain a a
system of lines from a computer to itself (perhaps for c
diagnostic purpose), as illustrated below. For such f d
network, we use loops which are edges from a vertex
to itself. Such a graph is known as pseudo graph.
e
Pseudo graphs are more general than simple graphs
and multi graphs. Pseudo graph
Graph Models e
As we mentioned earlier that graphs have diverse applications and many problems of real
life can be modeled through the graphs. In this section we shall try to present some of the
applications by modeling the practical problem using graphs of various kinds.
First Model: Niche Overlap Graph in Ecology
Ecology (from Greek: οἶκος, "house" ; -λογία, "study of") is the interdisciplinary
scientific study of the interactions between organisms and their environment. Ecology is
also the study of ecosystems. Ecosystems describe the web or network of relations among
organisms at different scales of organization. Since ecology refers to any form of bio-
diversity, ecologists can conduct research on the smallest bacteria to the global flux of
atmospheric gases that are regulated by photosynthesis and respiration as organisms
breath in and out of the biosphere. Ecology is a recent discipline that emerged from the
106
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
natural sciences in the late 19th century. Ecology is not synonymous with environment,
environmentalism, or environmental science.
Graphs are used in models involving the interaction of different species of animals. Niche
overlap graphs are used to model the relationship between different species having
different as well as common ecological behaviors.
Here each species is represented by a vertex and an undirected edge connects two vertices
if the two species have common ecological property (for instance some of the food
resources they use are same). The following graph shows the ecological relation between
different species.
REMARK: The common thing between these species considered here is food
resources they use.
Raccoon (R) Hawk (H) Owl (Ow) Opossum (Op)
H
Ow
R
Sq
Op
C
Squirrel (Sq) Crow (C) Shrew (Sh) Mouse (M) Woodpecker (W)
Sh
M W
This type of graph is used when we have to show whether or not there exits a relationship
between people. For example, let us consider the case of students in a class who have just
admitted in a college.
We wish to see that which group of students knows the other one before entering in the
college. Such a graph is known as Acquaintanceship Graph. Here vertex represents a
particular student and the edge showing that students know each other before entering in
the college. a
b c d e a b
f g h
i j k
l m
n c d e
o p
Graph of 2nd Model Graph of 3rd Model
Third Model: Influence Graph
There are situations where one person has influence on the others but he is not influence
by any one of them. It is also possible that a group of people influence one and other. The
graph that shows such relationship between different people is always a directed graph
and is known as “Influence graph”.
Here vertices are the people and the directed edge represents the fact that which person is
influenced by the other one. From the graph we see that c has influence over a, and b and
is influence by d. b and e influence each other and e has influence on d as well.
107
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
b c
d e
Graph of 4th Model
108
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
Proof: We begin by drawing a graph with a given number of vertices and no edges. Note
that every vertex has degree 0 and so the number of odd vertices is 0 (an even number).
We will see that if we start adding edges to the graph, the number of odd vertices will
either go up by 2 or down by 2, thus keeping the number of odd vertices an even number.
In Figure below, we start with all vertices having degree 0, and so there are no vertices
having odd degree.
109
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
REMARK: Let G be a directed graph and (u, v) be its directed edge. Then vertex u is
said to be adjacent to vertex v and v is said to be adjacent from u. The vertex u is called
initial vertex and v is called the terminal vertex of edge (u, v). The initial and terminal
vertex of the loop is same. In such case the definition of number of degrees of vertex is
redefined to reproduce the number of degrees with this vertex as the initial vertex and as
the terminal vertex.
Definition: In a directed graph the in-degree of a vertex v, denoted by δ-(v), is the
number of edges which terminate at v. Similarly the out-degree of a vertex v, denoted by
δ+(v), is the number of edges which depart from v. The loop at any vertex contributes 1 to
both in-degree and out-degree.
Example 3: For the following directed graph find out the number of in-degrees and
out-degrees.
Solution: here directed graph contains five vertices.
Now let us see the in-degree and out-degree. b c
a
δ-(a) = 1, δ-(b) = 3, δ-(c) = 3, δ-(d) = 1, δ-(e) = 3.
δ+(a) = 3, δ+(b) = 1, δ+(c) = 3, δ+(d) = 2, δ+(e) = 2.
It may be noted that each edge has an initial and
terminal vertex. Thus sum of in-degree is equal to
sum of out-degree for all vertices for every directed
graph. Both of these sums are the number of edges d e
in the directed graph. This shows that:
( v ) ( v ) | E | where | E |
Indicates cardinality of set E of edges in a graph. For the above directed graph, we
observe that:
i. Sum of in-degree = Sum of out-degree = 11. ii. Total number of edges is 11.
Some Important Simple Graphs and Their Applications
In this section we introduce some simple graphs which are used in many networks. They
are:
Complete Graphs: The complete graph is a simple graph usually denoted by Kn. Here n
indicates the number of vertices it contains with the property that each edge of this
graph connects only two vertices. The following are the complete graphs with n = 1, 3,
4, 5, and 6.
K1 K3 K4 K5 K6
Cycles: The cycle graph is a simple graph usually denoted by Cn, n ≥ 3 with the property
that its n vertices v1, v2, v3 … vn form the edges {v1, v2}, {v2, v3}, {v3, v4} … {vn-1, vn}.
The following are the cycles with n = 3, 4, 5, and 6.
C3 C4 C5 C6
110
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
Wheels: The wheels graph is a simple graph usually denoted by Wn, n ≥ 3 with the
property that its each vertex connects the other vertices. The following are the wheels
with n = 3, 4, 5, and 6.
W3 W4 W5 W6
You may observe that Wn is obtained from Cn by adding an extra vertex in Cn and joining
every vertex of Cn to this new vertex.
Bipartite Graph
A simple graph G is called bipartite graph (or
bigraph) whose vertices can be divided into two
disjoint sets U and V such that every edge connects a
vertex in U to one in V; that is, U and V are
independent sets. The two sets U and V may be
thought
of as a coloring of the graph with two colors: if we
color all nodes in U blue, and all nodes in V green,
each edge has endpoints of differing colors. In contrast, such a coloring is impossible in
the case of a non-bipartite graph, such as a triangle: after one node is colored blue and
another green, the third vertex of the triangle is connected to vertices of both colors,
preventing it from being assigned either color.
One often writes G = (U, V, E) to denote a bipartite graph whose partition has the parts U
and V. If |U| =|V|, that is, if two subsets have equal cardinality, then G is called a
balanced bipartite graph.
Bipartite graphs are useful for modeling matching problems. An example of bipartite
graph is a job matching problem. Suppose we have a set P of people and a set J of jobs,
with not all people suitable for all jobs. We can model this as a bipartite graph (P, J, E).
If a person px is suitable for a certain job jy there is an edge between px and jy in the graph.
The marriage theorem provides another example that characterizes bipartite graphs which
allow perfect matching. For instance, consider the graph representing marriages between
people in a town, where each person is represented by a vertex and a marriage is
represented by an edge. In this graph, each edge connects a vertex in the subset of
vertices representing males and a vertex in the subset of vertices representing females.
v1 v2
The cycle C6 is another example of bipartite graph. v1 v2
If we decompose the set of vertices {v1, v2, v3, v3 v4
v4, v5, v6} into subset say: v3 v v4
U = { v1, v3, v5} and V = {v2, v4, v6}, v5 v6 v5 v6
then we see that every edge of C6 connects vertex in U and V.
Complete Bipartite Graph
A complete bipartite graph or biclique is a special kind of bipartite graph where every
vertex of the first set is connected to every vertex of the second set. Complete bipartite
graph usually denoted by Km, n is the graph that has vertex set partitioned into two subsets
of m and n vertices, respectively.
111
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
Complete bipartite graph K2, 3 Utility graph K3,3 The star graphs S3, S4, S5 and S6.
For any n, K1, n is called a star. All complete bipartite graphs which are trees are stars and
are denoted by Sn. (Tree will be defined in next chapter). The graph K1, 3 is called a claw
(Pointed nail of a bird or animal, e.g. claw of lion or claw of hawk). K3,3 is called the
utility graph. This usage comes from a standard mathematical puzzle in which three
utilities must each be connected to three buildings; it is impossible to solve without
crossings due to the non-planarity of K3, 3.
Applications to Computer Networks
The physical configuration that determines how the network's computers are connected is
known as “Topology”. Common configurations include the bus topology, mesh topology,
ring topology, star topology, tree topology and hybrid topology. In this section we shall
discuss few of these important topologies that are related to graphs.
Star Network or Star Topology
Star networks are one of the most common computer network topologies. In its simplest
form, a star network consists of one central switch, hub or computer, which acts as a
conduit (link) to transmit messages. Thus, the hub and leaf nodes, and the transmission
lines between them, form a graph
with the topology of a star. If the
central node is passive, the
originating node must be able to
tolerate the reception of an echo
of its own transmission, delayed
by the two-way transmission time (i.e. to and from the central node) plus any delay
generated in the central node. An active star network has an active central node that
usually has the means to prevent echo-related problems.
The star topology reduces the chance of network failure by connecting all of the systems
to a central node. When applied to a bus-based network, this central hub rebroadcasts all
transmissions received from any peripheral node to all peripheral nodes on the network,
sometimes including the originating node. All peripheral nodes may thus communicate
with all others by transmitting to, and receiving from, the central node only. The failure
of a transmission line linking any peripheral node to the central node will result in the
isolation of that peripheral node from all others, but the rest of the systems will be
unaffected.
Advantages
Better performance: The star topology prevents the passing of data packets
through an excessive number of nodes. At most, 3 devices and 2 links are
involved in any communication between any two devices. Although this topology
places a huge overhead on the central hub, with adequate capacity, the hub can
handle very high utilization by one device without affecting others.
Isolation of devices: Each device is inherently isolated by the link that connects it
to the hub. This makes the isolation of individual devices straightforward and
112
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
amounts to disconnecting each device from the others. This isolation also prevents
any non-centralized failure from affecting the network.
Benefits from centralization: As the central hub is the bottleneck, increasing its
capacity, or connecting additional devices to it, increases the size of the network
very easily. Centralization also allows the inspection of traffic through the
network. This facilitates analysis of the traffic and detection of suspicious
behavior.
Simplicity: This topology is easy to understand, establish, and navigate. Its
simplicity obviates the need for complex routing or message passing protocols.
Also, as noted earlier, the isolation and centralization it allows simplify fault
detection, as each link or device can be probed individually.
Disadvantages
The primary disadvantage of a star topology is the high dependence of the system on the
functioning of the central hub. While the failure of an individual link only results in the
isolation of a single node, the failure of the central hub renders the network inoperable,
immediately isolating all nodes. The performance and scalability of the network also
depend on the capabilities of the hub. Network size is limited by the number of
connections that can be made to the hub, and performance for the entire network is
capped by its throughput. While in theory traffic between the hub and a node is isolated
from other nodes on the network, other nodes may see a performance drop if traffic to
another node occupies a significant portion of the central node's processing capability or
throughput. Furthermore, wiring up of the system can be very complex.
Ring Network or Ring Topology
A ring network is a network topology in which each node connects to exactly two other
nodes, forming a single continuous pathway for signals through each node - a ring. Data
travels from node to node, with each node along the way handling every packet. Because
a ring topology provides only one
pathway between any two nodes,
ring networks may be disrupted by
the failure of a single link. A node
failure or cable break might isolate
every node attached to the ring.
FDDI (Fiber Distributed Data Interface) networks overcome this vulnerability by sending
data on a clockwise and a counterclockwise ring: in the event of a break data is wrapped
back onto the complementary ring before it reaches the end of the cable, maintaining a
path to every node along the resulting "C-Ring". 802.5 networks -- also known as IBM
Token Ring networks avoid the weakness of a ring topology altogether: they actually use
a star topology at the physical layer and a Multi-station Access Unit to imitate a ring at
the data-link layer.
Many ring networks add a "counter-rotating ring" to form a redundant topology. Such
"dual ring" networks include Spatial Reuse Protocol, Fiber Distributed Data Interface
(FDDI), and Resilient Packet Ring.
Advantages
Very orderly network where every device has access to the token and the
opportunity to transmit
Performs better than a star topology under heavy network load
Can create much larger network using Token Ring
113
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
Does not require network server to manage the connectivity between the
computers
Disadvantages
One malfunctioning workstation or bad port in the MAU (Multi-station Access
Unit) can create problems for the entire network
Moves, adds and changes of devices can affect the network
Network adapter cards and MAU's are much more expensive than Ethernet cards
and hubs
Much slower than an Ethernet network under normal load
Hybrids Topology
Hybrid network is the combination of different topologies such as star,
Ring, etc. For example, if a department uses a ring network, second
department uses the star network, then both networks can be connected
together through a central hub (in the form of star network) as shown
in the two figures.
Advantages and Disadvantages of Hybrid Topology
Hybrid topology allows coexistence and cohabitation by integrating different network
technology to work together. Disadvantage is the cost and the support requires
maintaining them. Thus today network topology is commonly a cluster of Ethernets. Very
few if any exist like Token ring, Serial loop.
114
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
i. ii. iii.
Regular Graph
In graph theory, a regular graph is a graph where each vertex has the same number of
neighbors, i.e. every vertex has the same degree or valency. A regular graph with vertices
of degree k is called a k-regular graph or regular graph of degree k. Regular graphs of
degree at most 2 are easy to classify: A 0-regular graph consists of disconnected vertices
(Isolated vertices are zero degree regular graphs). A 1-regular graph consists of
disconnected edges, and a 2-regular graph consists of disconnected cycles. A 3-regular
graph is known as a cubic graph.
G1 G2 G1 G2
115
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
is that this form of representation takes away from the visual aspect of graphs. It would
be difficult to illustrate in a matrix, properties that are easily illustrated graphically.
Specifically, the adjacency matrix of a finite graph G on n vertices is the n × n matrix
where the non-diagonal entry aij is the number of edges from vertex i to vertex j, and the
diagonal entry aii, depending on the convention, is either once or twice the number of
edges (loops) from vertex i to itself. Undirected graphs often use the former convention
of counting loops twice, whereas directed graphs typically use the latter convention.
There exists a unique adjacency matrix for each graph, and it is not the adjacency matrix
of any other graph. In the special case of a finite simple graph, the adjacency matrix is a
(0, 1)-matrix with zeros on its diagonal. If the graph is undirected, the adjacency matrix is
symmetric. In other words, adjacency matrix is defined as: Let G be a graph with "n"
vertices that are assumed to be ordered from v1 to vn.
The n × n matrix A, in which
aij = 1 if there exists a path from vi to vj
aij = 0 otherwise
is called an adjacency matrix.
116
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
Matrix representation of
directed graph
Original Graph G:
v1 v2 v3 v4 v5
v1 0 1 0 1 1
v2 0 0 0 1 0
v3 0 0 0 0 1
v4 0 0 0 0 0
v5 0 1 0 0 0
Incidence Matrix
An incidence matrix is a matrix that shows the relationship between two classes of
objects where first class is X, the set of vertices and the second is Y, the set of edges. The
matrix has one row for each element of X and one column for each element of Y. The
entry in row x and column y is 1 if x and y are related (called incident in this context) and
0 if they are not where x is the vertex and y is the edge. In other words, the incidence
matrix of graph G is a m × n matrix (bij), where m and n are the numbers of vertices and
edges respectively, such that bij = 1 if the vertex vi and edge xj are incident and 0
otherwise.
For example the incidence matrix of the undirected graph shown on the right is a matrix
consisting of 4 rows (corresponding to the four vertices) and 4 columns (corresponding to
the four edges):
e1 e2 e3 e4
v1
v2
v3
v4
isomorphism is to say that one graph can be rearranged to look like the other one. The
two graphs shown below are isomorphic, despite their different looking drawings.
An isomorphism
Graph G Graph H
between G and H
ƒ(a) = 1
ƒ(b) = 6
ƒ(c) = 8
ƒ(d) = 3
ƒ(g) = 5
ƒ(h) = 2
ƒ(i) = 4
ƒ(j) = 7
It has been observed that if a graph contains n vertices then there exists n! possible 1-1
correspondences between the set of vertices of two graphs. Thus it is difficult to
determine whether two graphs are isomorphic or not. We may use adjacency matrix
method to determine that two graphs are isomorphic but again it becomes difficult if n is
too big. However, we can often show that two graphs are not isomorphic by showing that
they do not share a property that isomorphic graphs must both have. Such property is
known as graph invariant. There are four such invariants by which one can determine
the isomorphic property between two graphs. These are:
(i) Number of vertices (ii) Number of edges (iii) Number of faces and (iv) Number of
degrees of each vertex in both graphs.
Example 1: Are the following graphs isomorphic. If no then what are the graph
invariants?
Solution: a a'
Number of vertices in G = 5 = Number of vertices in H.
b c b' c'
Number of edges in G = 6 = Number of edges in H.
Number of faces in G = 3 = Number of faces in H.
Now let us see the number of degrees of each vertex d e d' e'
in each graph:
G H
deg(a) = 2, deg(b) = 2, deg(c) = 3, deg(d) = 3, deg(e) = 2.
deg(a’) = 2, deg(b’) = 4, deg(c’) = 3, deg(d’) = 2, deg(e’) = 2.
Since there is no vertex in graph G which has degree 1 or 4 as in graph H. Hence given
graphs are not isomorphic and the graph invariant is “number of degrees”.
Example 2: Are the following graphs isomorphic. If no then what are the graph
invariants? a b
Solution: c d
Number of vertices in G = 8 = Number of vertices in H. e f
Number of edges in G = 10 = Number of edges in H. g h
Number of faces in G = 4 = Number of faces in H. G
118
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
r s
Solution: e f
t u
Number of vertices in G = 6 = Number of vertices in H.
Number of edges in G = 7 = Number of edges in H.
Number of faces in G = 3 = Number of faces in H.
Now let us see the number of degrees of each vertex in each graph:
deg(a) = 2, deg(b) = 3, deg(c) = 2, deg(d) = 2, deg(e) = 3, deg(f) = 2.
deg(p) = 2, deg(q) = 3, deg(r) = 2, deg(s) = 2, deg(t) = 3, deg(u) = 2.
Since number of vertices of degree 3 are two and those of degree 2 are four in both
graphs G and H in graph G, the deg(a) = 2 and adjacent vertices of a are b and e with
degree 3 each. Similarly, in graph H degree of p is 2 and its adjacent vertices are r and t
whose degree is 2 and 3 respectively. This is true for all vertices of graph G as well as
graph H. Hence, two graphs are isomorphic.
REMARK: Sometimes number of faces may not be considered as graph invariant.
8. 5 PATHS
Many problems can be modeled with paths and circuits. A path is a sequence of edges
that begins at a vertex of a graph and travels along edges of the graph connecting the
pairs of adjacent vertices. For example, a files can be shared by two computer users using
intermediate links or one can plane a route for mail delivery, garbage pickup, diagnostics
in computer networks, and so on, can be solved using models that involve paths in a
graph.
Some Important Definitions
Connected Graph: A graph G is called connected if there is a path between any two
distinct vertices of G. Otherwise, the graph is called disconnected. Symbolically,
Graph G is connected if and only if u, v G, a walk from u to v.
For example, the graph (a) shown below is connected where as the graph (b) and (c) are
not connected.
119
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
A directed graph is strongly connected if for every pair of distinct vertices u, v there is a
path from u to v and there is a path from v to u.
Walk: A walk in a graph is a sequence of vertices and edges, which starts and ends with
a vertex, and in which each edge is incident with vertex immediately preceding it and the
vertex immediately following it.
Trail: A trail is a walk in which all edges are distinct.
Path: A path is a walk which does not contain repeated edge.
Simple Path: A simple path is a walk that does not contain repeated vertex.
If the first and the last vertex in a walk or trail is same, then we say that walk or trail is
closed. A walk or trail that is not closed is open.
Circuit: A closed trail is called a circuit. Thus a circuit is a closed walk that does not
contain repeated edge.
Simple Circuit: A simple circuit is a circuit that does not contain repeated vertex except
the first and last. Cycle: A circuit in which no vertex except first and last appears more
than once is called a cycle. An n-cycle is a cycle with n vertices and n edges. An even
cycle is one with even number of edges and an odd cycle is one which contains odd
number of edges. Consider the following figure:
a
abcefcbd is a walk which is neither a trail nor a path because edge (b,
c) and vertices b and c are repeated twice.
abcefcd is a trail but not path because the vertex c is repeated twice. b d
abcefcdba is a closed walk but not a circuit because the edge (a, b) is c
repeated twice.
bcefcdb is a circuit but not a cycle because the vertex c is repeated e f
which is not the first or last vertex.
bcdb is a 3-cycle and hence is an odd cycle.
For case of reference, these definitions are summarized in the following table:
Repeated edge Repeated vertex Can starts and ends
allowed or not allowed or not at the same point
Walk Y Y Y
Path N Y Y
Simple Path N N N
Closed Walk Y Y Y
Circuit N Y Y
Simple Circuit N Only first & last Y
REMARK: Often a walk can be specified unambiguously by giving either a sequence of
edges or a sequence of vertices. The following two examples show how this is done.
Example 1: In the graph shown here, the notation e1 e2 e4 e3 e2
refers unambiguously to the walk v1 e1 v2 e2 v3 e4 v3 e3 v2. On the e4
e1
other hand the notation e1 is ambiguous if used to refer to a walk. v1 v2
It could mean either v1 e1 v2 or v2 e1 v1. Also, the notation v2 v3 is v3
ambiguous if used to refer to a walk. It could mean v2 e2 v3 or e2
v2 e3 v3.
e1 e4
Example 2: In the graph show here, the notation v1 v2 v2
v3 refers unambiguously to the walk v1 e1 v2 e2 v2 e3 v3. v1 v2 v3
REMARK: If a graph G does not have any parallel edges, then any walk in G is uniquely
determined by its sequence of vertices.
120
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
Euler Paths
As mentioned earlier that subject of graph theory began in the year 1736 when the great
mathematician Leonhard Euler published a paper that contained the solution to the
following puzzle.
[Leonhard Paul Euler (15 April 1707 – 18 September 1783) was a
pioneering Swiss mathematician and physicist who spent most of
his life in Russia and Germany]. The town of Königsberg Prussia
(now Kaliningrad in Russia) was built at a point where two branches
of the Pregel River came together. It consisted of an island and some
land along the river banks. These were connected by seven bridges as
EULER shown in figure 1 below.
The question is: Is it possible for a person to take a walk around town starting and ending
at the same location and crossing each of the seven bridges exactly once?
To solve this puzzle, Euler translated it into a graph theory problem. He noticed that all
points of Königsberg can be identifies with the graph shown in figure 2 in which the
vertices 1, 2, 3, and 4 represent land masses and the seven edges represent the seven
bridges. In terms of graph, the question becomes the following:
Is it possible to find a route through the graph that starts and ends at same vertex, and
traverse each edge exactly once? Equivalently, we may say that is it possible to trace this
graph, starting and ending the same vertex, without lifting your pen from the paper?
u1 e1 u2e3 u3 e4 u2 e3 u3 e5 u4 e6 u4 e7 u2 e3 u3 e5 u4.
Certain types of sequences of adjacent vertices and edges are of special importance in
graph theory. u2 e3
u3
i). Those that do not have a repeated edge. e1 e4
ii). Those that do not have a repeated vertex. u1 e2 e2 e7 u4 e5
iii). Those that start and end at the same vertex. u5 e6
Euler Paths and Circuit
Let G(V, E) be a graph with no isolated vertices. An Euler Path in G is a simple path that
traverses every edge of the graph exactly once. Analogously, an Euler Circuit in G is a
simple circuit that traverses every edge of the graph exactly once.
We return now to consider general problems similar to the puzzle of the Königsberg
bridges. The following definition is made in honour of Euler.
Definition: Let G be a graph. An Euler circuit for G is a sequence of adjacent vertices
and edges in G that stars and ends at the same circuit that contains every vertex and every
edge of G.
The analysis used earlier to solve the puzzle of the Königsberg bridges generalizes to
prove the following theorem.
Theorem: If a graph is Euler circuit, then every vertex of the graph has even edges.
Proof: Suppose G is a graph that has an Euler circuit. Let u be any arbitrary vertex of G.
Since the Euler circuit contains every edge of G, it contains all edges incident on u. Each
time u is entered by traveling along one edge, it is immediately existed by traveling along
another edge. Because Euler circuit uses every edge of G exactly once, every edge
incident on u exactly traversed once in this process. Hence the edges incident on u in
every entry/exit pairs, and consequently the degree of the u must be a multiple of 2. This
means that the degree of u is even as was to be shown.
REMARK: The contra-positive of the above proposition/theorem is that if some vertex
of a graph is of odd degree, then graph does not have an Euler circuit.
Example 3: Show that the graph shown here does not have an Euler circuit.
Solution: Here vertices u1 and u3 have degree 3, which is
odd.
Hence by contra-positive form of Euler circuit, this graph u2 e1 u3
does not have an Euler circuit. e6
e4 e5
Converse of Euler Circuit e2
Now consider the converse of above theorem. If every vertex u1 e 3
u4
of a graph has even degree, then the graph has an Euler e7
circuit. Is it true?
The answer is no. There are many graphs with every vertex
of even degree but it has not an Euler circuit. The adjacent
figure shows this. u1 u3
e1 e3
The reason that above graph has not an Euler circuit is that it
is not connected. However, the modified converse of the e4
e2
above theorem is always true. It states that if a graph is u2 u4
connected and every vertex is of even degree, then the graph
has an Euler circuit.
Corollary (Euler Path)Let G be a graph and let u and v be two vertices of G. There is an
Euler path from u to v if, and only if, G is connected, u and v have an odd degree, and all
other vertices of G have even degree.
122
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
G
Open
I
H
F
A
E
K
B
J
D
C
Example 4: (Finding an Euler Path) The floor plan shown below is for a house that
is open for public viewing. Is it possible to find a path that starts in room A, ends in
room B, and passes through every interior doorway of the house exactly once? If so,
find such a path.
Solution: The graph of the house plan is shown below. Each vertex of this graph has
even degree except for A and B, which have degree 1. It may be noted that room/door is
considered as vertex and the path from one room/door to another is an edge. The open
and ending rooms/doors are vertices of degree 1. You may visualize that once people are
entered in room A they are asked to have a tour starting from A and ending at B without
utilizing the same edges. Hence by above corollary, there is an Euler path from A to B.
One such path is “AGHFEIHEKJDCG”.
REMARK: It may be noted that there is no bar if one visit any room more than once but
he must not reuse the same path to move from one room to another.
G
A I
H
B
F K
E
C D
J
Hamiltonian Circuit
In 1859 the Irish mathematician Sir William Rowan Hamilton introduced a puzzle in the
shape of a dodecahedron (DOH-DEKA-HEE-DRON) shown below
which is a solid figure with twelve identical pentagonal faces. Each
vertex was labeled with the name of city-London, Paris, New York,,
and so on. The problem Hamilton posed was to start at one city and
tour the world by visiting each other city exactly once and retuning to
the starting city. The puzzle was quite easy to solve by imagining the
surface of the dodecahedron stretched out and laid flat in the plane as
Sir W. R. Hamilton
shown in the following figure. It may be noted that in Hamiltonian
123
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
circuit we have to visit each vertex but not necessarily that each edge has also to be
utilized. This means that some edges may be omitted.
A Hamilton path in G is a path that contains each vertex of G once. Note that by deleting
an edge in a Hamilton circuit, we get a Hamilton path, so if a graph has a Hamilton
circuit, then it also has a Hamilton path. The converse is not true.
Note that H has the same number of edges as it has the vertices since all its n edges are
distinct and so are its n vertices C: u1 u2 … un. Also by definition of Hamiltonian circuit,
every vertex of G is a vertex of H, and hence H is connected since any two of its vertices
lie on a circuit. In addition, every vertex of H has degree 2. The reason for this is that
there are exactly two edges incident on any vertex, namely ei and ei+1 for any vertex ui
except u0 = un and e1 and en for u0. These observations have established the truth of
following proposition:
Proposition: If a graph G has a Hamiltonian circuit then G has a sub graph H with the
following properties:
(i) H contains every vertex of G.
(ii) H is connected.
(iii) H has the same number of edges and vertices.
(iv) Every vertex of H has degree 2.
124
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
The contra-positive of the above proposition says that if a graph G does not have a
subgraph H with properties (i) to (iv), then G does not have a Hamiltonian circuit.
Example 5: Prove that the graph G shown below does not have Hamiltonian circuit.
Solution: If G has a Hamiltonian circuit then by above proposition G has a sub graph H
that contains
i). H contains every vertex of G. a b
c
ii). H is connected.
iii). H has the same number of edges and vertices.
d e
iv). Every vertex of H has degree 2.
We observe that vertex ci has degree 4. To find sub graph H we must remove one of the
edges that is connecting c. But in this case other vertices will not retain degree 2. Hence
G is not Hamiltonian circuit.
The traveling salesperson problem, discussed in the next example, is a variation of the
problem of finding a Hamiltonian circuit for a graph.
Example 6: (Traveling Salesperson Problem) Imagine that the drawing shown in the
following graph is a map showing four cities and the distances in kilometers between
them. Suppose a salesperson must travel to each city exactly once, starting and
ending in city A. Which route from city to city will minimize the total distance that
must be traveled?
Solution: The problem can be solved by writing all possible Hamiltonian circuits starting
and ending at A and calculating the total distance traveled for each.
Route Total Distance (in Km)
B
ABCDA 30 + 30 + 25 + 40 = 125 30
ABDCA 30 + 35 + 25 + 50 = 140 C
ACBDA 50 + 30 + 35 + 40 = 155 35
30
ACDBA backward ACDBA = 140 50 25
ABCDA backward ADBCA = 155
ADCBA backward ADCBA = 125
A 40 D
Thus either route ABCDA or ADCBA gives a minimum distance of 125 kilometers.
The general traveling salesperson problem involves finding a Hamiltonian circuit to
minimize the total distance traveled for an arbitrary graph with n vertices in which each
edge is marked with a distance. One way to solve the general problem is to use the
method of above example, that is to write down all Hamiltonian circuits starting and
ending at a particular vertex, compute the total distance for each, and pick one for which
this total is minimum. However, even for small value of n say 30 vertices, there would be
29! ≈ 8.84 × 1030 different Hamiltonian circuits starting and ending at the same vertex.
Even if each circuit could be found and its total distance computed in just one
microsecond, it would require approximately 2.8 × 1017 years finishing the computation.
At present, there is no known method for solving the general traveling salesperson
problem that is more efficient. However, there are some efficient algorithms that find
better solutions if not necessarily having the least possible total distance but have smaller
total distances than most other Hamiltonian circuits.
REMARK: Few other glossary terms are:
i. a path in a graph is a sequence of vertices, such that from each vertex there is an
edge to the next vertex.
ii. a graph is complete if every vertex is connected to every other vertex.
125
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
126
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
b 1 c
2 3
2
a 1 z
3 d
4 4
e f
2
In the each iteration the algorithm would label the vertices in the following way. The
boxed vertices are the ones removed from T.
Iteration a b C d e f z
0 0 ∞ ∞ ∞ ∞ ∞ ∞
1 0 2 ∞ 3 4 ∞ ∞
2 0 2 3 3 4 ∞ ∞
3 0 2 3 3 4 ∞ 6
4 0 2 3 3 4 ∞ 4
5 0 2 3 3 3 6 4
6 0 2 3 3 3 6 3
At this point the algorithm returns the value 4. It may be noted that for n-vertex, simple,
connected weighted graph, Dijkstra’s algorithm has a worst case run time of order n2.
Planar Graphs
A graph G is planar if it can be drawn in the plane with its edges intersecting at their
vertices only. In other words, a graph is called planar if it can be drawn in the plane
without any edge crossing. One such drawing is called an embedding of the graph in the
plane. For example, K4 is a planar graph. This is shown below.
Graph Homeomorphism
If a graph G has a vertex v of degree 2 and edges (v, v1), (v, v2) with v1 ≠ v2, we say that
the edges (v, v1) and (v, v2) are in series. Deleting such vertex v and replacing (v, v1) and
(v, v2) with (v1, v2) is called a series reduction. For example the edges (h, b) and (h, d) in
the graph 3 shown below are in series. By removing vertex h we get the graph 1.
Three homeomorphic Graphs
c c
c f
b d b d b d
a e a e
a e
127
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
K5 K3, 3
Graph Coloring
Consider a problem of coloring a map M in such a way that no adjacent region sharing a
border has the same color.
In general, a coloring of a graph is an assignment of a color to each vertex of a graph.
The color is called proper if there are no adjacent vertices with the same color. If a region
can be properly colored with n colors we say that it is n-colorable. The minimum number
of colors needed to properly color a given graph G(V, E) is called chromatic number of
G, and is represented by (G ) . Obviously, (G ) ≤ |V|.
Some Results about Graph Coloring
1. ( K n ) n .
2. Let G be a simple graph. Then (i) (G ) = 2, (ii) G is bi-partite (iii) Every circuit
in G has even length.
3. Every simple planar graph is 5-colorable (This is due to Kempe, Heawood).
4. Every simple planar graph is 4-colorable (This is due to Appel and Haken 1976).
128
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
129
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
EXERCISES 08
1. Diagram the graph given by V = {a; b; c; d} and E = {{a, b}, {a; d}, {c; d}.
2. Diagram the graph given by V = {; b; c; d; e; f} and E = {{a, f}, {a, e}, {b, c},{b, f},
{c, f}, {d, e}, {e, f}}
3. In the graphs shown below name each vertex and find the degree of each of it. Also
indicate an isolate vertex. Also verify that 2 e ( u )
uV
i. ii. iii.
4. Refer to graphs of problem 3, give directions to each edge at your choice then verify
that:
( v ) ( v ) | E |
5. Draw the graphs:
i. K7 ii. K1, 7 iii. K4, 4 iv. C7 v. W7 vi. C8
6. Name each vertex in the following graphs and determine whether or not they are
bipartite.
i. ii. iii.
iv. v.
7. Find a general formula for the number of edges to each of the graph:
i. Kn ii. Km, n iii. Cn v. Wn
8. Does there exits a simple graph with five vertices and of following degree? If so,
draw such a graph and if it is not possible then give a reason for it.
i. 1, 1, 1, 1, 1 ii. 0, 1, 2, 2, 3 iii. 3, 4, 3, 4, 3
iv. 1, 2, 3, 4, 4 v. 1, 2, 3, 4, 5 v. 3, 3, 3, 3, 2.
9. How many sub graphs with at least one vertex do K2, K3, and W3 have? Also draw
these graphs.
10. Draw all possible sub graphs of the graph shown
here:
130
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
11. For what value of n are the following graphs are regular.
i. Kn ii. Cn iii. Wn
Also find m and n for which Km, n is regular graph.
12. How many vertices does a regular graph of degree 4 with 10 edges have?
13. Find the union of the following simple graphs. Draw the union in at least two
different ways.
i. ii. iii.
14. Represent the following graph with an adjacency matrix. Name the vertices as well.
i. ii. iii.
iv v. vi.
15. Draw an undirected graph with each of the adjacency matrix given below:
0 0 2 1 1 1 1 0
1 3 2 0 0 1 0 1 0 1 0
i . 3 0 3 ii . iii .
2 1 0 2 1 1 0 1
2 3 1
1 0 2 0 0 0 1 1
1 0 2 3
1 1 3 0
16. Draw a directed graph with adjacency matrix: .
1 2 1 1
2 1 2 0
17. Use an incidence matrix to represent the graphs given in 16. Name the vertices and
edges as well.
18. Find an adjacency matrix for each of the following graphs.
i. K5 ii. C5 iii. W5
19. Find an incidence matrix for each of the following graphs.
i. K5 ii. C5 iii. W5
20. In each of the following show whether or not the given pair of graphs is isomorphic.
Name each vertex.
131
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
i. ii. iii.
iv. v. vi.
21. After giving names to every vertex and edge of the following graph, start at any
vertex trace out the complete graph without picking up the pencil show that it has an
Euler circuit. Write down the edge sequence as well.
22.In the graph below, determine whether the following walk are paths, simple paths,
closed walks, circuits, simple circuits, or just walks.
i. v0 e1 v1 e10 v5 v9 v2 e2 v1 v1
ii. v4 e7 v2 e9 v5 e10 v1 e3 v2 e9 v5 e1 e2 v3
iii. v2 v0 e3 v2 e4
iv. v5 v2 v3 v4 v4 v5 e10 e5
v. v2 v3 v4 v5 v2 v4 v3 v2 e9 e7
vi. e5 e8 e10 v1 e3 e8 v4 e6
22. Determine which of the following graphs have Euler circuit. Find Euler circuit as
well. v2
a b
(i) e1 e2 e3 e4 (ii) e d f
v1 v3
v5 g h i j
e7 e6
v4
a a b
c
(iii) b c (iv)
d e
i
d e
f g h
132
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
23. Is it possible to take a walk around the city whose map is shown below, starting and
ending at the same point and crossing each bridge exactly once? If so, how can this be
B
done?
Bridge Island
C
A
Island Island
D
River
E
24. In the following graph, determine whether there is an Euler path from u to v. If there
is, find such a path. Name the other paths yourselves.
(i)
(ii) u (iii)
u u
v
v v
25. Find Hamiltonian circuits (if any) for each of the following graphs. Name the vertices
yourselves.
(i) (ii)
(vi) (vii)
26. Show that the graph shown below possesses Euler circuit but not the Hamiltonian
circuit.
27. Show that graph show below has Hamiltonian circuit but not the Euler circuit.
28. Show that the graph shown below has both Euler and Hamiltonian circuits.
133
CHAPTER EIGHT DISCRETE MATHEMATICS GRAPHS
29. Show that the graph shown below has both Euler as well as Hamiltonian circuits but
the two circuits are not same.
REMARK: Name the vertices.
31. For the following graphs determine whether the given graph has an Hamiltonian tour
and if so find one.
134
CHAPTER NINE DISCRETE MATHEMATICS TREES
C H A P T E R
9 TREES
9.1 INTRODUCTION
A tree is a connected undirected graph with no simple circuit. Trees were used as long
ago as 1857, when the British mathematician Arthur Cayley used them to count certain
types of chemical compounds. Since that time, trees have been employed to solve
problems in many disciplines such as in computer science to develop a wide range of
algorithms to locate an item from a big list. Huffman coding that constructs efficient
codes saving cost in transmission and storing the huge data make use of trees.
Trees can be used in chess game to develop strategies for winning
such games. They can also be used in modeling various procedures
to carry out a sequence of decisions and to develop algorithms such
as sorting. Trees are also used to develop organizational charts.
Family trees are graphs that represent parent-child relationships. The
following tree diagram shows the family tree of Bernoulli family a
Swiss mathematician.
Arthur Cayley The Bernoulli Family of Mathematicians
Nikolaus
(1623-1708)
Nikolaus-I
Nikolaus-II Daniel
(1687-1759) Johann-II
(1695-1726) (1700-1782)
(1710-1790)
Johann-II Jocob-II
(1746-1807) (1759-1789)
135
CHAPTER NINE DISCRETE MATHEMATICS TREES
Pro-Vice Chancellor
To qualify as a tree, a connected graph must fulfill path and edge requirements. We
present the path requirement first.
Theorem: A connected graph is a tree if and only if there is a unique, simple path
between any two vertices.
Proof: Let G be a tree and let v and w be any two of its vertices. Since G is connected, a
simple path must run between them. If there are two distinct simple paths between them,
then one path followed by the other in reverse order would form a cycle which is
impossible since G is a tree. Thus G contains a unique, simple path between v and w.
Conversely, let G be a graph with a unique, simple path between any two vertices.
Clearly, G is connected. Suppose G contains a cycle, and v and w are two vertices in it.
Then the cycle can be split into two distinct simple paths between v and w. This gives
contradiction to our assumption. So G is acyclic. Since G is connected and acyclic, hence
G is a tree.
REMARK: A graph with one vertex without loop is considered as simple graph and
tree as well.
REMARK: You may verify that the graphs in the above figures are connected and
contain unique and simple paths between any two vertices. Thus they all represent
trees.
REMARK: Since a tree cannot have a simple circuit, a tree cannot contain multiple
edges or loops. Therefore any tree must be a simple graph.
Now we establish the edge requirement for a connected graph to be a tree.
Theorem: Prove that a connected graph with n vertices is a tree if it has exactly
n – 1 edges.
Proof: We prove this theorem by mathematical induction.
Basic step: Let us consider a proposition P(n) that a tree with n vertices has n – 1 edges.
Suppose T contains one vertex. Since T is acyclic, it is loop free. Hence T contains no
edge and P(1) is true.
Inductive step: Suppose the result is true for n = k. Let T be a tree with k + 1 vertices
and e an edge in T. Deleting e from T yields two connected disjoint graphs, T1 and T2.
136
CHAPTER NINE DISCRETE MATHEMATICS TREES
Rooted Tree
Take a good look at the following tree that is designed to dial any number from any city
of the world. For sack of simplicity we are producing the country codes of only three
cities. 011 (root)
France
UK Japan
33
44 81
a Level 0
b c
Level 1
d g
e f h i
Level 2
j k l m n o p Level 3
137
CHAPTER NINE DISCRETE MATHEMATICS TREES
Fundamental Terminologies
A tree has the following fundamental terminologies:
Node
Node is the main component of a tree. This stores the actual data and links to the other
node. Node is also known as vertex of a tree. Refer to above figure, a, b, c, .., p are all
nodes
Child
Child of node is the immediate successor of a node. Child may be left or right child
depending on whether it lies on left or right of the node. Refer to above figure, a, b, c are
children of R, d, e are children of a.
Parent
Parent of a node is the immediate predecessor of a node. Refer to above figure, a is
parent of d and e. Similarly, g is I.
Root
A node that has no parent is called root. Refer to above figure is a root.
Leaf
The node which is at the end and which does not have any child is called leaf node. Leaf
is also called terminal node or external node. Refer to above figure, j, k, l, m, n, o, and p
are leaves.
Level
The level of a vertex v is the length of the simple path from the root to v. Root is always
at level zero. If a node is at level n then its parent is at level (n – 1) and child is at level
(n + 1). Refer to above figure, level of nodes a, b, c is 1 etc.
Height
The height of a rooted tree is the maximum level of its nodes or vertices. The height of a
tree is also termed as depth of tree. Refer to above figure, the height of tree is 4.
Mathematically, height of tree is level of tree plus one.
Siblings
The nodes, which have the same parent, are called siblings. Refer to above figure, h, i are
sibling. Similarly, l, and m are also siblings.
Generalizing, if T be a tree with root v0 and suppose that x, y and z are vertices in T and
that (v0, v1, v2, … vn) is a simple path. Then:
i. vn-1 is the parent of vn.
ii. (v0, v1, v2, … vn) are ancestors of vn.
iii. vn is child of vn-1.
iv. If x is an ancestor of y , y is the descendent of x.
v. If x has no children, it is called terminal vertex or leaf.
vi. If x is not a terminal vertex, it is an internal or branch vertex.
vii. The subtree of T rooted at x is the graph (V, E), where V is x together with its
descendants and E is number of edges of simple paths from x to some vertex
in E.
138
CHAPTER NINE DISCRETE MATHEMATICS TREES
Binary Trees
A binary tree is a rooted tree in which each vertex has at most two children, designated as
left child and right child. If a vertex has one child, that child is designated as either a left
child or a right child, but not both. A full binary tree is a binary tree in which each vertex
has exactly two children or none. The following are few results about binary trees:
1. If T is a full binary tree with i internal vertices, then T has i+1terminal vertices and
2i + 1 total vertex.
2. If a binary tree of height h has t terminal vertices, then t ≤ 2h.
More generally we can define a m-array tree as a rooted tree in which every internal
vertex has no more than m children. The tree is called a full m-array tree if every internal
vertex has exactly m children. An ordered rooted tree is a rooted tree where the children
of each internal vertex are ordered. A binary tree is just a particular case of m-array
ordered tree (with m = 2).
A binary tree is said to be full binary tree if it contains maximum possible number of
nodes in all level. A binary tree is said to be complete binary tree if it contains
maximum possible number of nodes in all level except the last level.
139
CHAPTER NINE DISCRETE MATHEMATICS TREES
Bridge
An edge of a graph G(V, E) is said to be a bridge if an edge is removed from the graph G
results in two or more connected components.
Consider the following graph.
On removing edge e from the graph G, the graph has two connected components shown
below.
Hence e is a bridge. It may be noted that graph G after removing bridge is called a forest.
Theorem: A tree of order n has size (n – 1).
Proof: By induction if n = 1 then there is only one vertex in the tree and its level is
1 – 1 = 0. If n = 2, then tree contains two vertices and therefore its level is 2 – 1 = 1.
Let us suppose that proposition is true for n = k. We also suppose that its size be q and e
be the edge of T. If e is the bridge of T then (T – e) is a forest. Let the two components of
(T – e) are T1 and T2, where T1 is of order n1 with size q1 and T2 is of order n2 with size q2.
Now q1 = n1 – 1 and q2 = n2 – 1. Since n = n1 + n2 and q = q1 + q2 + 1
we get q = (n1 – 1) +( n2 – 1) + 1= (n1 + n2 ) – 1 = (n -1)
Thus by induction the size of tree is (n – 1) that is, one less than its order.
Distance and Eccentricity
Let u and v be two vertices of the graph G. The distance between u and v is denoted by
D(u, v) and is defined as the length of a shortest path from u to v . If there is no path
between u and v, then D(u, v) = ∞.
Let V be the set of all vertices of G. Let v V . The eccentricity of v is denoted by E(v)
and is defined as:
Ev max Du, v | u V and u v
Radius and Diameter
Let G be a graph. Then the radius and diameter of G are denoted by Rad(G) and Diam(G)
respectively defined as:
Rad G min Ev | v V and DiamG max Ev | v V
Central Point and Centre
Let V be the set of all vertices of graph G. Then v ϵ V is said to be a central point if E(v) =
Rad(G). The set of all central points of G is known as centre of G. To understand the idea
let us consider the following graph where each edge is of length 1.
140
CHAPTER NINE DISCRETE MATHEMATICS TREES
v4 v9
v1 v6 v11 v13
v2 v16
v7 v12 v14
v3 v8
v15
v5 v10
Here V = {v1, v2, v3, …, v12}. Now,
D(v1, v2) = 1; D(v1, v3) = 2; D(v1, v4) = 4; D(v1, v5) = 4; D(v1, v6) = 3;
D(v1, v7) = 2; D(v1, v8) = 3; D(v1, v9) = 4; D(v1, v10) = 4; D(v1, v11) = 4;
D(v1, v12) = 3; D(v1, v13) = 5; D(v1, v14) = 4; D(v1, v15) = 5; D(v1, v16) = 5.
Therefore, E(v1) = max{1, 2, 3, 4, 5} = 5
D(v2, v1) = 1; D(v2, v3) = 1; D(v2, v4) = 3; D(v2, v5) = 3; D(v2, v6) = 2;
D(v2, v7) = 1; D(v2, v8) = 2; D(v2, v9) = 3; D(v2, v10) = 3; D(v2, v11) = 3;
D(v2, v12) = 2; D(v2, v13) = 4; D(v2, v14) = 3; D(v2, v15) = 4; D(v2, v16) = 4.
Therefore, E(v2) = max{1, 2, 3, 4} = 4.
Proceeding this way we get:
E(v3) = 5; E(v4) = 5; E(v5) = 5; E(v6) = 4; E(v7) = 3; E(v8) = 4; E(v9) = 5; E(v10) = 5;
E(v11) = 4; E(v12) = 3; E(v13) = 5; E(v14) = 4; E(v15) = 5; E(v16) = 5.
Now, Rad G min Ev | v V min 3,4,5 3 and
DiamG max Ev | v V max 3,4,5 5 .
Therefore, the central points are v7 and v12 and centre is (v7, v12)
Binary Search Trees
Assume S is a set in which elements (which we will call “data”) are ordered; e.g., the
elements of S can be numbers in their natural order, or strings of alphabetic characters in
lexicographic order. A binary search tree associated to S is a binary tree T in which data
from S are associate with the vertices of T so that, for each vertex v in T, each data item in
the left subtree of v is less than the data item in v, and each data item in the right subtree
of v is greater than the data item in v.
Example 2: The following figure contains a binary search tree for the set S = {1, 2, 3, 4,
5, 6, 7, 8, 9, 10}. In order to find a element we start at the root and compare it to the data
in the current vertex (initially the root). If the element is greater we continue through the
right child, if it is smaller we continue through the left child, if it is equal we have found
it. If we reach a terminal vertex without founding the element, then that element is not
present in S.
Making a Binary Search Tree
We can store data in a binary search tree by randomly choosing data from S and placing it
in the tree in the following way: The first data chosen will be the root of the tree. Then
for each subsequent data item, starting at the root we compare it to the data in the current
vertex v.
141
CHAPTER NINE DISCRETE MATHEMATICS TREES
2
9
1 10
3 7
8
4 6
If the new data item is greater than the data in the current vertex then we move to the
right child, if it is less we move to the left child. If there is no such child then we create
one and put the new data in it. For instance, the tree in figure 8.3 has been made from the
following list of words choosing them in the order they occur: “IN A PLACE OF LA
MANCHA WHOSE NAME I DO NOT WANT TO REMEMBER”.
IN
A PLACE
I OF WHOSE
DO LA WANT
MANCHA TO
NAME REMEMBER
NOT
Decision Trees
A decision tree is a tree in which each vertex represents a question and each descending
edge from that vertex represents a possible answer to that question.
Example 3: The Five-Coin Puzzle. In this puzzle we have five coins C1,C2,C3,C4,C5 that
are identical in appearance, but one is either heavier or lighter than the others. The
problem is to identify the bad coin and determine whether it is lighter or heavier using
only a pan balance and comparing the weights of two piles of coins. The problem can be
solved in the following way. First we compare the weights of C1 and C2. If C1 is heavier
than C2 then we know that either C1 is the bad coin and is heavier, or C2 is the bad coin
and it is lighter. Then by comparing say C1 with any of the other coins, say C5, we can
determine whether the bad coin is C1 and is heavier (if C1 it is heavier than C5) or it is C2
and is lighter (if C1 has the same weight as C5). If C1 is lighter than C2 we proceed as
before with “heavier” and “lighter” reversed. If C1 and C2 have the same weight we can
try comparing C3 and C4 in a similar manner. If their weights are the same then we know
that the bad coin is C5, and we can determine whether it is heavier or lighter by
142
CHAPTER NINE DISCRETE MATHEMATICS TREES
comparing it to say C1. The corresponding decision tree is shown below. In each vertex
“Ci : Cj” means that we compare coins Ci and Cj by placing Ci on the left pan and Cj on
the right pan of the balance, and each edge is labeled depending on what side of the
balance is heavier. The terminal vertices are labeled with the bad coin and whether it is
heavier (H) or lighter (L). The decision tree is optimal in the sense that in the worst case
it uses three weighing, and there is no way to solve the problem with less than that—with
two weighing we can get at most nine possible outcomes, which are insufficient to
distinguish among ten combinations of 5 possible bad coins and the bad coin being
heavier or lighter.
C1 : C 2
Left Right
Balanced
C3 : C 4
C1 C5 C1 C5
Right
Left Right
Left Bal Bal
C1 H C3 C5 C1 C5 C3 C5
C2L C2H C1L
Right
Left Left Right
Bal
Bal
C3 H C4L C5L C5 H C4H C3L
Complexity of Sorting
Sorting algorithms work by comparing elements and rearranging them as needed. For
instance we can sort three elements a1, a2, a3 with the decision tree shown in the
following figure.
a1 < a2
Y N
a2 < a3 a1 < a3
Y N Y N
Y N Y N
Since there are 3! = 6 possible arrangements of 3 elements, we need a decision tree with
at least 6 possible outcomes or terminal vertices. Recall that in a binary tree of height h
143
CHAPTER NINE DISCRETE MATHEMATICS TREES
with t terminal vertices the inequality t ≤ 2h holds. Hence in our case 6 < 2h which implies
that h ≥ 3, so the algorithm represented by the decision tree in the above figure is optimal
in the sense that it uses the minimum possible number of comparisons in the worst-case.
Isomorphism of Trees
Assume that T1 is a tree with vertex set V1 and T2 is another tree with vertex set V2. If
they are rooted trees then we call their roots r1 and r2 respectively. We will study three
different kinds of tree-isomorphism between T1 and T2.
1. Usual graph-isomorphism between trees: T1 and T2 are isomorphic if there is a
bijection f: V1 → V2 that preserves adjacency, i.e., f(v) is adjacent to f(w) if and only
if v is adjacent to w.
2. Rooted-tree-isomorphism: T1 and T2 are isomorphic if there is a bijection f: V1 → V2
that preserves adjacency and the root vertex, i.e.:
(a) f(v) is adjacent to f(w) if and only if v is adjacent to w. (b) f(r1) = r2.
3. Binary-tree-isomorphism: Two binary trees T1 and T2 are isomorphic if there is a
bijection f: V1→V2 that preserves adjacency, and the root vertex, and left/right
children, i.e.:
(a) f(v) is adjacent to f(w) if and only if v is adjacent to w.
(b) f(r1) = r2.
(c) f(v) is a left child of f(w) if and only if v is a left child of w.
(d) f(v) is a right child of f(w) if and only if v is a right child of w.
Example 4: The following figure shows three trees which are graph-isomorphic. On the
other hand as rooted trees T2 and T3 are isomorphic, but they are not isomorphic to T1
because the root of T1 has degree 3, while the roots of T2 and T3 have degree 2. Finally T2
and T3 are not isomorphic as binary trees because the left child of the root in T2 is a
terminal vertex while the left child of the root of T3 has two children.
T1 T2 T3
Trees with different kinds of isomorphism
Huffman Codes
Usually characters are represented in a computer with fix length bit strings. Huffman
codes provide an alternative representation with variable length bit strings, so that shorter
strings are used for the most frequently used characters. As an example assume that we
have an alphabet with four symbols: A = {a, b, c, d}. Two bits are enough for
representing them, for instance a = 11, b = 10, c = 01, d = 00 would be one such
representation. With this encoding n-character words will have 2n bits. However assume
that they do not appear with the same frequency, instead some are more frequent than
others, say a appears with a frequency of 50%, b 30%, c 15% and d 5%. Then the
following encoding would be more efficient than the fix length encoding: a = 1, b = 01, c
= 001, d = 000. Now in average an n-character word will have 0.5n a’s, 0.3n b’s, 0.15n
c’s and 0.05n d’s, hence its length will be 0.5n·1+0.3n·2+0.15n·3+0.05n·3 = 1.7n, which
144
CHAPTER NINE DISCRETE MATHEMATICS TREES
is shorter than 2n. In general the length per character of a given encoding with characters
1 n
a1, a2, . . . , an whose frequencies are f1, f2, . . . , fn is f k l( a k ) , where l(ak) = length
F k 1
n
of ak and F f k . The problem now is, given an alphabet and the frequencies of its
k 1
characters; find an optimal encoding that provides minimum average length for words.
Fix length and Huffman codes can be represented by trees like in figure shown below.
The code of each symbol consists of the sequence of labels of the edges in the path from
the root to the leaf with the desired symbol.
1 0 1 0
a
1 0 1 0 1 0
b
a b c d 1 0
c d
Fix length code Huffman code
Frequency 2 3 7 8 12
Here we have a choice, we can choose to add the first 12 and 8, or 8 and the second 12.
Let’s choose the former:
8 , 12 → 20,
12,
12 → 32
145
CHAPTER NINE DISCRETE MATHEMATICS TREES
32
1 0
20
1 0 12
12 e
1 0 8
5 d
7
1 0 c
2 3
A b
Optimal Huffman code-I
to encode rarely occurring letters. When letters are encoded using varying numbers of
bits some method must be used to determine where the bits for each character starts and
end. For instance, if ‘e’ were encoded with 0, ‘a’ with 1, and ‘t’ with 01, then the bit
string 0101 could correspond to ‘ eat’, ‘ tea’, ‘ eaea’ or ‘tt’.
One way to ensure that no bit strings corresponds to more than one sequence of letters is
to encode letters so that the bit string for a letter never occurs as the first part of the bit
string, for another letter. Codes with this property are called prefix codes. For instance,
the encoding of e as 0, a as 10 and t as 11 is prefix code. A word can be recovered from
the unique bit string that encodes its letters. For example, the string 10110 is the encoding
of ate. To see this, note that the initial 1 does not represent a character, but 10 does
represent ‘a’. Then, the next 1 does not represent a character, but 11 does represent‘t’.
The final bit, 0, represents ‘e’.
A prefix code can be represented using a binary tree, where the characters are the labels
of the leaves in the tree. The edges of the tree are labeled so that an edge leading to a left
child is assigned a 0 and an edge leading to a right child is assigned a 1. The bit string
used to encode a character is the sequence of labels of the edges in the unique path from
the root to the leaf that has this character as its label. For example, the tree in the figure
below represents the encoding of e by 0, a by 10, t by 110, n by 1110, and s by 1111.
0 1
e
0 1
a 0 1
t
0 1
n s
The tree representing a code can be used to decode a bit string. For example, consider the
word encoded by 11111011100 using the code in the figure above. This bit string can be
decoded by starting at the root, using the sequence of bits to form a path that stops when
a leaf is reached. Each 0 bit takes the path down the edge leading to the left child of the
last vertex in the path, and each 1 bit corresponds to the right child of this vertex.
Consequently, the initial 1111 corresponds to the path starting at the root, going right four
times leading to a leaf labeled s. Continuing with the 5th bit, we reach a leaf next after
going right then left, when the vertex labeled with a which is encoded by 10. Starting
with the 7th bit, we reach a leaf next after going right three times and then left, when the
vertex labeled with n is visited and is encoded by 1110. Finally, the last bit, 0, leads to the
leaf labeled with e. Thus the string bit 11111011100 can be decoded by the word ’same’.
This way we can construct a prefix code from any binary tree where the left edge at each
internal vertex is labeled by 0 and the right edge by a 1 and where the leaves are labeled
by characters. Characters are encoded with the bit string constructed using the labels of
the edges in the unique path from the root to the leaves.
Tree Transversal
In order to motivate this subject, we introduce the concept of Polish notation. Given a
(not necessarily commutative) binary operation, it is customary to represent the result of
147
CHAPTER NINE DISCRETE MATHEMATICS TREES
applying the operation to two elements a, b by placing the operation symbol in the middle
such as: a * b
This is called infix notation. The Polish notation consists of placing the symbol to the left
such as: * a b.
The reverse Polish notation consists of placing the symbol to the right such as: a b*.
The advantage of Polish notation is that it allows us to write expressions without need for
parenthesis. For instance, the expression a* (b + c) in Polish notation would be * a + b c,
while a * b + c is + * a b c.
Also, Polish notation is easier to evaluate in a computer. In order to evaluate an
expression in Polish notation, we scan the expression from right to left, placing the
elements in a stack (A stack or last-in first-out (LIFO) system, is a linear list of elements
in which insertions and deletions take place only at one end, called top of the list). Each
time we find an operator, we replace the two top symbols of the stack by the result of
applying the operator to those elements. For instance, the expression + 2 3 4 which in
infix notation is “(2 + 3) 4” would be evaluated as under:
Expression Stack
+234
+ 2 3 4
+ 2 34
+ 234
54
20
TL TR
Tree of SL * SR
For instance, consider the following algebraic expression: a + b c + d " e ↑ (f + h),
where ↑ denotes exponentiation. The binary tree for this expression is given in the
following figure. +
+ ×
a
× ×
b c d e f h
Tree for a + b × c +d ↑ e × (f + h)
148
CHAPTER NINE DISCRETE MATHEMATICS TREES
Given the binary tree of an algebraic expression, its Polish, reverse Polish and infix
representation are different ways of ordering the vertices of the tree, namely in preorder,
post-order and in-order respectively.
The following are recursive definitions of several orderings of the vertices of a rooted
tree T = (V, E) with root r. If T has only one vertex r, then r by itself constitutes the
preorder, post-order and in-order transversal of T. Otherwise, let T1, . . . , Tn the sub-trees
of T from left to right (see figure below). Then:
1. Preorder Transversal: Pre(T) = r, Pre(T1), . . . , Pre(Tn).
2. Post-order Transversal: Post(T) = Post(T1), . . . ,Post(Tn), r.
3. In-order Transversal. If T is a binary tree with root r, left sub-tree TL and right
sub-tree TR, then: In(T) = In(TL), r, In(TR).
r
T1 T2 T3 … Tn
Ordering of trees
Spanning Trees
All connected graphs have trees that span them. A tree T is called a spanning tree of a
graph G if T is a sub-graph of G that contains all the vertices of G.
Let us consider an example of five towns A through E connected by roads. Due to heavy
snowfall some of the roads are closed for traffic. Management wishes to plow as few as
possible roads so as to travel between the towns. The following graphs show how five
towns are connected (graph G) and how the roads are plowed to overcome the difficulty
on traffic flow (Graph H).
C C
B B
D D
A E A E
Graph G Graph H
Notice that graph H is sub-graph of graph G. It is a tree that contains every vertex of
graph G. Two additional spanning trees are given in the following figure, indicating that
the spanning tree of a graph need not be unique.
C C
B B
D D
A E A E
Two other spanning trees for graph G
149
CHAPTER NINE DISCRETE MATHEMATICS TREES
150
CHAPTER NINE DISCRETE MATHEMATICS TREES
b d
a c e
g f
151
CHAPTER NINE DISCRETE MATHEMATICS TREES
a 4 b
2 5
3 1 d
C
6 6
E 2 f
Minimum Spanning Tree
The minimum weight is 4 + 3 + 2 + 1 + 2 = 12.
Let us consider an example where a company would like to lay pipelines for natural gas
between five towns A through E as shown in the figure below. The weights (in millions)
of edges represent the cost of building the various pipelines. They must be laid in such a
way that the natural gas can be sent from any town to any other town holding
construction cost to a minimum. In other words, the company needs to find a spanning
tree for a weighted graph with the sum of the weights of the tree’s edges at a minimum.
Such a tree is minimal spanning tree.
C
13 13
16 12
B 10 D
11 10
7 15 Fig. 3
A 12 E
A number of algorithms are available which find the minimal spanning tree of a
connected weighted graph G. We produce below two algorithms.
Kruskal’s Algorithms
The following steps are involved to find the minimal spanning tree using this
algorithm.
Arrange the degrees in G in non-decreasing order of their weights.
Choose an edge in G with the minimum weight.
Add an edge of least weight to T if it does not a cycle with the edges already
selected.
Repeat step 3 until the number of edges selected is n – 1, where n denotes the
number of vertices in G.
Example 7: Find the minimal spanning tree using Kruskal’s algorithm for graph of
figure 3.
Solution: The steps of Kruskal’s algorithm are as under:
Step 1: Arrange the edges in non-decreasing order of their weights as shown in the
following table.
152
CHAPTER NINE DISCRETE MATHEMATICS TREES
Weight: 7 10 10 11 12 12 13 13 15 16
Edge: (A, B) (A, D) (B, D) (B, E) (A, E) (C, E) (B, C) (C, D) (D, E) (A, C)
7 10
A E
Prim’s Algorithm
Prim’s algorithm is an other way to find minimal spanning tree. This algorithm was
discovered by the American Engineer Robert Clay Prim in 1957. The following steps
summarize this algorithm.
Choose the edge with minimum weight and include it in T.
Select an edge of least weight that is incident with the vertex of an edge in T.
If it does not create a cycle with the edges in T, then include it; otherwise discard it.
Repeat steps 3 and 4 until T contains (n – 1) edges.
The following example illustrates the application of Prim’s algorithm.
Example 8: Use Prim’s algorithm and construct the minimal spanning tree for the
graph of figure 3.
Solution:
Step 1: Arrange the edges in non-decreasing order of their weights as shown in the
following table.
Weight: 7 10 10 11 12 12 13 13 15 16
Edge: (A, B) (A, D) (B, D) (B, E) (A, E) (C, E) (B, C) (C, D) (D, E) (A, C)
153
CHAPTER NINE DISCRETE MATHEMATICS TREES
Step 2: Choose edge (A, B) since it has the smallest weight so include it in T. Draw this
edge now.
B
7
A
Step 3: An edges with the next smallest weight are (A, D) and (B, D). They do not form a
cycle. Hence select one of them say (B, D) and include it in T.
B 10 D
7
A
7 11
A E
Step 6: Edge (A, E) forms a cycle hence discard it.
Step 7: Select edge (C, E) as it does not form cycle so include it in T.
C
B 10 D
12
7 11
A E
Having selected all vertices we are done and found the minimal spanning tree with
minimum weights equal to 7 + 10 + 11 + 12 = 40.
154
CHAPTER NINE DISCRETE MATHEMATICS TREES
EXERCISES 09
1. Determine whether or not the following graphs represent trees.
i. ii. iii. iv. v. vi.
If n is number of vertices and e the number of edges verify that e = n – 1 for the graph
which represent trees. Also show that sum of degrees of all vertices is equal to 2n -2
fro a graph that represents tree.
2. For what values of n is Kn a tree? Which of the graphs K1, 2, K1, 3, K2, 2 and, K2, 3 a
tree? For what values of m and n is Km, n a tree?
3. The eccentricity of a vertex v in a tree is the length of the longest simple path from v
and centre of a tree is a vertex with the least eccentricity. Find the eccentricity of
each vertex of the tree and centre of the following tree. (Give name to each vertex)
4. Rewrite each of the following in prefix form. Also construct binary tree for each of
these expressions.
i. a + b × c/(d – e) ↑ f ii. a↑ (b ↑ c) + d/e – f
iii. (a + b × c)/(d – e/f) ↑ g iv. a – (b × c + d)/e × f – g ↑ f
5. Rewrite the following prefix expressions in infix form, supplying enough parentheses
where necessary.
i. + × ↑ abc × de ii. +a ↑ /b – cde
iii. - ↑ + a × bcd × ef iv. × × -a + bcd ↑ e – fg
6. Convert each postfix expressions into infix form, supplying parentheses where
necessary.
i. ab – cd - /ef ↑ × ii. abc + d × / e × f –
iii. ab – cd - / e ↑ iv. ab/cd/efg - + × +
7. Evaluate each binary expression, where each operand is a single-digit number.
i. - ↑ 2 ↑ 23 × + 857 ii. 37 × 4 + 5/2 ↑
iii. 63/921 + / + 73 - × iv. 86 + 34 + / 5↑
8. Evaluate each binary expression tree.
- ↑
+ × × /
6 26
9 ↑ - + -
9 3 8
5 2 5 4 5
155
Chief
Project
Director
CHAPTER NINE DISCRETE MATHEMATICS TREES
10. How many leaves does a full binary tree with n vertices have?
11. Prove that the number of vertices in a full binary tree is odd.
12. How many leaves does a full binary tree with i internal vertices have?
13. How many vertices does a full binary tree with l leaves have?
14. Use Kruskal’s algorithm, construct a spanning tree for each graph, starting at vertex a.
i. ii. b iii. b iv. a b
a b c d
a c a c f g
v. b e vi. a b vii. d
f g b f h
a c f h
e h a
d g d g ci c
e
15. Use DFS and DFS methods construct a spanning tree for each graph in problem 14.
16. Find spanning tree for each complete graph: K2, K3, K4, and K5.
17. Find spanning tree for each complete bipartite graph: K1, 1, K2, 2, K2,3, and K3,3.
18. Use Kruskal’s algorithm, construct a minimal spanning tree for each of the following
weighted graph. Name each vertex.
5 3 11
3 8 2 1
i. 2 4 ii. 2 8
5 2 12
1 2
3 8
4 6 1 6 1
iii. 4 iv. 5 3 7 6
3 3 3 8
2 7 1 7 1
8
v. 2 7 6 4
3
5 10 7 5
19. Use Prim’s algorithm, construct a minimal spanning tree for each of the weighted
graph of question 18.
156
OTHER BOOKS OF FARKALEET SERIES
Applied Calculus
Linear Algebra and Analytical Geometry
Differential Equations and Fourier Series
Complex Variable and Transforms
Complex Analysis, Probability and Statistical Methods
Statistical Methods and Estimations
Numerical Analysis and Computational Applications
Laplace, Fourier and Z-Transforms
Linear Algebra & Numerical Methods
MCQs in Mathematics for F. Sc.-I
MCQs in Mathematics for F. Sc-II
Textbook with Key (Mathematics) for F. Sc-I
Textbook with Key (Mathematics) for F. Sc-II
Partial Differential Equations with Applications