DISCRETE MATHEMATICS

14 TOPICS
1 Set
2 Relation
3 Function
4 Sequence and Strings
5 Propositional Logic
6 Predicate Logic
7 Integer
8 Counting
9 Matrices
10 Introduction to Graphs
11 Path and Cycle
12 Graph Representation and Isomorphism
13 Planar Graph
14 Tree

CHAPTER 1 : SET

CONTENT SUMMARY
1.1 Concept of Set
1.1.1 Listing the -A set is any well-defined collection of objects, called elements or members of the
Elements of Sets set.
1.1.2 Specifying  A set is completely known when its members are all known. Thus, we say
Properties of Sets two sets of A and B are equal if they have the same elements, and we write
1.1.3 Set Membership A = B.
1.1.4 Empty Set  A Venn diagram illustrates the universal set E as a rectangle, while sets
1.1.5 Set of Numbers within E will be denoted by circles.
1.2 Set Equality  Set A is a subset of set B if every element of A is also an element of B,
1.3 Venn Diagram
1.4 Subset  If A is a set, then the set of all subsets of A including the empty set and
1.5 Power Set itself
1.6 Set Operation  The operations of sets include union, intersection and difference.
1.6.1 Union  The generalised union of an arbitrary family, S, of sets are those elements x
1.6.2 Intersection
 belonging to at least one set X in S. Formally, U S = {x
1.6.3 Disjoint Sets
1.6.4 Set Difference
 The generalised intersection of an arbitrary family, S, of sets are those
1.6.5 Set
Complementary
1.6.6 Characteristics
of Set
1.7 Generalised Union
and Intersection
1.8 Partition
1.9 Cartesian Product
1.1 Concept of Set

1.1.1 Listing the Elements of Sets

- A set that has a finite number of elements is by
listing the elements of the set between
curly brackets.

Notation A = {elements of set A}

- Where A is the name of the set. It could be

any other variable name.
- Other examples are C, D, E and so on.
- Normally the name of the set is denoted by
capital letters while elements of a set are
with small letters, for example P = {x,
y,z}.

1.1.4 Empty Set

1.1.2 Specifying Properties of Sets

- To define a set is by specifying a property that
the elements of the set have in common. 1.1.5 Set of Numbers

-If a set is a large finite set or an infinite set, we

can describe it by listing a property necessary for
membership.

1.10 Set Equality

-A set is completely known when its members are
all known.
- Two sets of A and B are equal if they have the
same elements and we write A = B.
1.1.3 Set Membership
Example 1.2a 1.6.3 Disjoint Sets
If A = {1, 2, 3} and B = {x|x is a positive integer
and x2 < 12}, then A = B.
Example 1.2b
If A = {BASIC, PASCAL, ADA}, B = {ADA,
BASIC, PASCAL} and C = { ADA,
ADA, BASIC, PASCAL, BASIC} then A = B = 1.6.4 Set Difference
C.
Example 1.2c
If A = {x | x2 + x – 6 = 0},
B = {2, –3}
A = B since x2 + x – 6 = 0 can be factorised into
(x – 2) (x + 3) = 0, giving x = 2 and
x = – 3.

1.11 Venn Diagram

1.6.5 Set Complementary
The purpose of Venn diagrams is to provide
pictorial views of a set.

1.4 Subset

1.6.6 Characteristics of Set

1.12 Power Set

1.6 Set Operation

1.6.1 Union

1.6.2 Intersection
1.7 Generalised Union and Intersection 1.9 Cartesian Product

1.8 Partition
 CHAPTER 2 : RELATION
2.1 Concept of Relation • The relation R between set X and Y is said „x is related to y‰, and
2.2 Inverse Relation denoted by x R y when (x, y) R.
2.3 Composition of Relations • The relation can be presented pictorially by using an arrow diagram.
2.4 Relations on a Set • Let R be a relation from X to Y. The inverse of R, denoted by R-1, is
2.4.1 Reflexive the relation from Y to X defined by R-1 = {(y, x) | (x, y) R}
2.4.2 Symmetric • Let R1 be a relation from X to Y and R2 be a relation from Y to Z.
2.4.3 Antisymmetric -The composition of R1 and R2, denoted by R2 o R1, is the relation
2.4.4 Transitive from X to Z, defined by R2 o R1 = {(x, z) | (x, y) R1 and (y,
2.5 Digraph z) R2 for some y Y}
2.6 Partial Order • A (binary) relation R on a set X is a relation from X to X.
2.7 Equivalence Relation • There are four properties of relations on a set namely reflexive,
symmetric, antisymmetric and transitive.
• The relation R between two sets is reflexive when (x, x ) R for all x
X.
• The relation R between two sets is symmetric when (x, y ) R then
(y, x) R , for all x, y X.
• The relation R between two sets is antisymmetric when (x, y ) R but
(y, x) , R for all x, y X.
• The relation R between two sets is transitive when (x, y ) R and (y,
z) R , then (x, z) R for all x, y, z X.
• The partial order is a relation R with properties of reflexive,
antisymmetric and transitive.
• The equivalence relation is a relation R with properties of reflexive,
symmetric and transitive.

2.1 Concept of Relation

2.4 Relations on a Set

2.2 Inverse Relation

2.3 Composition of Relations

2.4.1 Reflexive

2.4.2 Symmetric

2.6 Partial Order

2.4.3 Antisymmetric

2.4.4 Transitive

2.5 Digraph 2.7 Equivalence Relation

A digraph consists of vertices to represent the
elements of X and edges to represent the relation
between the elements. Let us check out some
examples of digraphs.
 CHAPTER 3 : FUNCTION
3.1 Concept of Function • The function f from X to Y is a relation from X to Y, if for each
3.2 Graph of a Function element in X,there is exactly one element in Y.
3.3 Types of Function • A function can be drawn into a graphical representation.
3.3.1 Injective • Three types of functions are injective, surjective and bijective.
3.3.2 Surjective • The function f from X to Y is said to be one to one (or injective), if
3.3.3 Bijective each element in Y in its arrow diagram will have at most one arrow
3.4 Inverse of a Function pointing to it.
3.5 Functions Composition • The function f from X to Y is said to be onto (or surjective), if each
3.6 Binary and Unary Operators element in Y in its arrow diagram will have at least one arrow pointing
to it.
• The function f from X to Y is said to be bijective function, if it has
both oneto-one and onto function.
• Suppose that f is one to one, onto function from X to Y. It can be
shown that the inverse relation{(y, x)|(x, y) ∈ f } is a function from Y
to X.
-This new function, denoted f–1 is called f inverse.
• The operation on function composition happens when g is a function
from X to Y and f is a function from Y to Z. Then the resulting
function from X to Z is the composition of f with g and is denoted by
f o g.
• A function from X X into X is called a binary operator on X.
• A function X into X is called a unary operator on X.
3.1 Concept of Function 3.4 Inverse of a Function

3.5 Functions Composition

- We can form the compositionof two functions.
3.2 Graph of a Function Specifically, suppose that g is a function from X
to Y and f is a function from Y to Z.
3.3 Types of Function -The resulting function from X to Z is called the
composition of f with g and is denoted by f o g.

3.3.1 Injective
3.6 Binary and Unary Operators

- A unary operator of a set X associates each

element of X with one element in X.
3.3.2 Surjective

3.3.3 Bijective
 CHAPTER 4 : SEQUENCE & STRINGS
4.1 Sequence • A sequence is a list in which order is taken into account, such as, if s is a
4.1.1 Types of sequence, we denote the first element as s1, the second element as s2 and nth
Sequence element denotes as sn . The sequence is increasing when sn sn+1 for all n.
4.1.2 Subsequence -The sequence is decreasing when sn+1 sn for all n. The certain terms of the
4.2 Sequence original sequence is called a subsequence. For example, sequence A contains s1,
Operation s2, s3, s4 and s5 while s2, s3 and s4 is a subsequence of A.
4.3 String • The operation on sequence involves the sum and product of terms in the
sequence.
• A string is a finite sequence of elements which are not necessarily distinct
elements. For example, abaa is the string with four elements and baaa is also the
string with four elements but they are two different strings.
• The operations on strings includes length of a string and concatenation.
4.1 Sequence

4.1.1 Types of Sequence

4.1.2 Subsequence

4.2 Sequence Operation

4.3 String

The string with no elements is called the null string and is denoted as Pai.
 CHAPTER 5 : PROPOSITIONAL LOGIC
CONTENTS SUMMARY
5.1 Proposition • Proposition is a statement that is either true or false.
5.1.1 Conjunction and Disjunction • The propositions in statements can be formulated
5.1.2 Negation into symbolic expressions.
5.2 Conditional Proposition • The compound propositions can be proved by using
5.3 Biconditional Proposition truth tables and laws of logic.
5.4 Tautologies, Contradictions and • The operations on compound propostions are
Logical Equivalence tautologies, contradiction, logical equivalence,
5.5 Contrapositive and Converse contrapositive and converse.
5.1 Proposition

5.1.1 Conjunction and Disjunction

5.3 Biconditional Proposition

5.4 Tautologies, Contradictions and Logical

Equivalence

5.1.2 Negation

5.2 Conditional Proposition

5.5 Contrapositive and Converse
 CHAPTER 6: PREDICATE LOGIC
CONTENTS SUMMARY
6.1 Predicate Logic • A predicate p, by itself, is neither true nor false. However, for each
6.2 Quantifiers x in its domain of discourse, p(x) is a proposition and is, therefore,
6.2.1 Universal Quantifier either true or false.
6.2.2 Existential Quantifier • There are two types of quantifiers: Universal quantifier ( ) and
6.2.3 Combining existential quantifier ( ).Universal quantifier of a predicate p(x) is a
Quantifiers proposition for all values of x; meanwhile existential quantifier of a
6.3 Generalised De Morgan predicate p(x) is the proposition for some value of x in the domain of
Laws discourse for which p(x) is true.
6.4 Translating Sentences • The given predicate can be shown equivalence by using generalised
into Logical Expressions De Morgan laws.
• The natural language sentences can be translated into logical
expressions.
6.1 Predicate Logic

6.2 Quantifiers

6.2.3 Combining Quantifiers

- Two or more quantifiers may be used in a
statement.
6.3 Generalised De Morgan Laws

6.2.1 Universal Quantifier

6.4 Translating Sentences into Logical

Expressions

6.2.2 Existential Quantifier

 CHAPTER 7 : INTEGER
7.1 Integer • An integer is a set of numbers from - ⁄-2, -1, 0, 1, 2⁄ to + .
7.1.1 Basic Operations • The basic operations on integers include addition, subtraction,
7.1.2 Order multiplication and division.
7.1.3 Absolute Value • Mod is a balance from division operations.
7.2 Mod • The greatest common divisors between two numbers can be
7.3 Divisor and Greatest computed using the Euclidean algorithm.
Common Divisor • Prime number is an integer number if its divisors are only 1 and itself.
7.3.1 Divisors • The steps involve in solving cryptography problems are encryption
7.3.2 Common Divisors and decryption.
7.3.3 Greatest Common -Steps in encryption are as follows:
Divisors – Choose two large primes, p and q (typically more than 100).
7.3.4 Euclidean Algorithm – Compute n = pq and z = (p – 1)(q – 1).
7.4 Prime Numbers – Choose a number relatively prime to z and call it d.
7.5 Cryptography • Then, to encrypt a message P, compute C = Pd (mod n). C is called
7.5.1 Private Key the cipher text.
7.5.2 Public Key • Steps in decryption are follows: Steps 1 to 3 in encryption, and
compute e such that ed mod z = 1. Then, to decrypt a cipher text C,
compute P = Ce (mod n).
7.1 Integer
An integer is a set of numbers Z = {⁄., –2, –1, 0, 1,
2,⁄.}

7.1.1 Basic Operations

7.2 Mod

7.3 Divisor and Greatest Common Divisor

7.3.1 Divisors

7.1.2 Order

7.3.2 Common Divisors

7.1.3 Absolute Value

7.3.3 Greatest Common Divisors

7.3.4 Euclidean Algorithm

7.5.1 Private Key

- The sender and receiver each have a key that
7.4 Prime Numbers defines a substitute character for each potential
character to be sent.

7.5.2 Public Key

- In the RSA system, each participant makes
public an encryption key and hides a decryption
key.

7.5 Cryptography

The sender is said to encrypt the message, and the

recipient is said to decrypt the message.
 CHAPTER 8: COUNTING
8.1 Basic Principle of  Counting is the action of finding the number of elements of a finite
Counting set of objects.
8.1.1 Multiplication  Two basic counting principles are multiplication principle and
Principle addition principle.
8.1.2 Addition  Multiplication principle is the idea that if there are a ways of doing
Principle something and b ways of doing another thing, then there are ab
8.1.3 Combining ways of performing both actions.
Principles  Addition principle is the idea that if we have a ways of doing
8.2 Permutation something and b ways of doing another thing and we can’t do both
8.3 Combination at the same time, then there are a + b ways to choose one of the
8.4 Pigeonhole actions.
Principle  Permutation relates to the act of rearranging or permuting, all the
8.4.1 First Form members of a set into some sequence or order.
8.4.2 Second Form  Combination is a way of selecting members from a grouping, such
that (unlike permutations) the order of selection does not matter.
• Pigeonhole principle states that if n items are put into m
containers, with n > m, then at least one container must
contain more than one item.
8.1 Basic Principle of Counting
8.1.1 Multiplication Principle

8.1.2 Addition Principle

8.1.3 Combining Principles

8.2 Permutation
 8.4 Pigeonhole Principle
Is there an item having a given property?

8.4.1 First Form

8.3 Combination

8.4.2 Second Form

 CHAPTER 9: MATRICES
9.1 Matrices • A matrix is a rectangular array of numbers with m rows and n
9.1.1 Equal Matrices columns. The matrix with the same number of rows and columns
9.1.2 Matrix Addition is called a square matrix.
9.1.3 Matrix Multiplication  The matrix with 1 as the values of its diagonal is called an
9.1.4 Identity Matrix identity matrix.
9.1.5 Power of Square Matrices  The matrix with entries either 0 or 1 is called a zero-one
9.1.6 Matrix Transpose matrix.
109.1.7 Zero-One Matrices • The basic operations in matrices are addition, multiplication and
9.2 Matrices of Relation transpose.
9.2.1 Representing Relations as • A few matrix types are square matrix, equal matrix, identity
Matrices matrix and zeroone matrix.
9.2.2 Using Matrices for Analysis • The relation can be represented as a matrix by labelling the rows
of Relations with the elements of X and labelling the columns with the
9.2.3 Checking for Transitivity element of Y for the relation R from X to Y. Then set the entry in
rows x and column y to 1 if and to 0 otherwise.
• The relation R on a set X can be analysed if it is reflexive,
symmetric and antisymmetric by examining the matrix A of R.
• The relation R is transitive if and only if whenever entries i, j in
A2 are nonzero and entry ij in A is also non-zero.
9.1 Matrices

9.1.4 Identity Matrix

9.1.5 Power of Square Matrices

9.1.1 Equal Matrices
-Two matrices are equal if they have the same
number of rows and the same number of columns
and the
corresponding entries in every position are equal.

9.1.2 Matrix Addition

9.1.3 Matrix Multiplication

9.1.6 Matrix Transpose

9.1.7 Zero-One Matrices

A matrix with entries that are either 0 or 1 is
called a zero-one matrix.

9.2 Matrices of Relation

9.2.2 Using Matrices for Analysis of Relations
9.2.1 Representing Relations as Matrices
Determine whether a relation R on a set X is reflexive,
symmetric and anti-symmetric by examining the matrix A of
R (relative to some ordering) by following this guideline:

(a) The relation R is reflexive, if and only if, A has 1s on

the main diagonal (the main diagonal to the right).
(b) The relation R is symmetric, if and only if, for all i
and j, the ij th entry of A is equal to the ji th entry of A.
(c) We can also quickly determine whether a relation R
is anti-symmetric by examining the matrix of R (relative
to some ordering).
9.2.3 Checking for Transitivity
 CHAPTER 10: INTRODUCTION TO GRAPHS
10.1 The Concept of Graphs • A graph G consists of a set V of vertices and a set E of
10.2 Types of Graphs edges, such that, each edge is associated with an unordered
10.2.1 Directed Graphs pair of vertices.
10.2.2 Simple Graphs • Some terminologies of graphs are vertex, edge, incident,
10.2.3 Weighted Graphs adjacent and degree of vertex.
10.2.4 Complete Graphs • Eight types of graphs are directed graph (digraph), simple
10.2.5 Cycles graph, weighted graph, complete graph, cycle, n-cube,
10.2.6 n-cube bipartite graph and complete bipartite graph.
10.2.7 Bipartite Graphs • Subgraph G is a part of a graph G = (V, E ) which is G_ =
10.2.8 Complete Bipartite (V, E_) such that V_ u_and E_ E._______
Graphs
10.3 Subgraphs

10.1 The Concept of Graphs

10.2 Types of Graphs

10.2.1 Directed Graphs
 10.2.3 Weighted Graphs

10.2.4 Complete Graphs

10.2.5 Cycles

10.2.2 Simple Graphs

10.2.6 n-cube

10.2.8 Complete Bipartite Graphs

10.2.7 Bipartite Graphs

10.3 Subgraphs
 CHAPTER 11 : PATH & CYCLE
11.1 Path • A path is a sequence of edges which connects a sequence of vertices. A
11.2 simple path is a path that does not contain the same edge more than once.
Connected • A cycle is a path that begins and ends at the same vertex. A simple cycle is a
Graph cycle that does not contain the same edge more than once.
11.3 • A graph G is connected if given any vertices v and w in G, there is a path from
Components v to w.
11.4 Euler Path • Let G be a graph and let v be a vertex in G. The subgraph GÊ of G consisting of
and Cycle all edges and vertices in G that are contained in some path beginning at v, is
11.5 Hamilton called the component of G containing v.
Path and Cycle • An Euler path is a path in a graph which visits every edge exactly once.
Similarly, an Euler cycle is an Euler path which starts and ends on the same
vertex. For the existence of Euler path, it is necessary that two vertices have an
odd degree. If there are no vertices of odd degree, then it is an Euler cycle.
• A Hamilton path is a path that visits each vertex exactly once. A
Hamilton cycle is a Hamilton path that starts and ends on the same vertex.

11.1 Path
11.2 Connected Graph

11.3 Components
11.4 Euler Path and Cycle 11.5 Hamilton Path and Cycle
 CHAPTER 12 : GRAPH REPRESENTATION & ISOMORPHISM
12.1 Graph • Graphs can be represented by using matrices that are adjacency matrices
Representation and incidence matrices.
12.1.1 Adjacency • We can obtain the degree of a vertex by using the graph representation of
Matrix an adjacency matrix. For simple graphs, the power of the adjacency matrix
12.1.2 Incidence counts the number of paths with various lengths.
Matrix • As for an incidence matrix, it gives the incidents of the graph, looping
12.2 Isomorphism and the degree of vertex.
• Two graphs G1 and G2 are isomorphic if there exists one to one and onto
function f from vertices of G1 to the vertices of G2, and one to one and
onto function g from the edges of G1 to the edges of G2.
• Two graphs, G1 and G2 are isomorphic if G1 and G2 have the same
adjacency matrix.
12.1 Graph Representation

12.1.1 Adjacency Matrix

12.1.2 Incidence Matrix

12.2 Isomorphism
 CHAPTER 13 : PLANAR GRAPH
13.1 Planar • A planar graph is a graph that can be drawn in such a way that no edges
Graph cross one another.
13.2 Graph • The concept of planar graphs can be used in solving a problem, such as, in deciding
Colouring whether it is possible to directly connect cities with other cities by expressways to
each of three other cities, so that the expressways do not cross one another, or to
design printed circuits in order to have as few lines crossing as possible, and so on.
• Graph colouring is a way of colouring the vertices of a graph such that no two
adjacent vertices share the same colour. The chromatic number of a graph is the least
number of colours needed to make a colouring.
• The graph colouring problem can be solved by following these steps:
– Step 1: Choose a vertex with the highest degree and colour it. Use the
same colour to colour as many vertices as you can, without colouring
vertices joined by an edge of the same colour.
– Step 2: Choose a new colour and repeat what you did in Step 1 for
vertices not already coloured.
– Step 3: Repeat Step 1 until all vertices are coloured.
13.1 Planar Graph 13.2 Graph Colouring
 CHAPTER 14 : TREE
14.1 Concept of Trees • A tree is a simple graph in which exists a unique simple path from vertex
14.2 Important v to vertex w.
Terminology • Different types of trees are trees, rooted trees and binary trees.
14.3 Binary Tree • Important terminologies of trees are root, parent, ancestors, children,
14.4 Tree Isomorphism descendats, siblings, terminal vertices and internal vertices.
14.4.1 Basic Concept of • A binary tree is a rooted tree in which each vertex has no children, one
Isomorphism child or two children. If a vertex has one child, that child is designated as
14.4.2 Rooted either a left child or a right child (but not both). If a vertex has two
Isomorphism children, one child is designated a left child and the other child is
14.4.3 Binary designated a right child.
Isomorphism of Trees • Tree isomorphisms are two trees with isomorphic properties.
• The difference between tree isomorphism and binary isomorphism is,
binary isomorphism contains two trees with binary tree properties.

14.1 Concept of Trees

14.2 Important Terminology

14.3 Binary Tree
 14.4.2 Rooted Isomorphism

14.4 Tree Isomorphism

14.4.1 Basic Concept of Isomorphism
14.4.3 Binary Isomorphism of Trees