Following are the Discrete Structure notes: The Introduction
The notes on the Discrete Structure are based on UGC NET Computer Science and Application syllabus.
Sets
a set is a collection of objects, which are called the ‘elements’ of the set
 a ∈ A means that ‘a’ is an element of A (A is the set)
 sets are equal if and only if they have the same elements
 order and repetition don’t matter for sets
 note that a set doesn’t equal its elements, i.e. {a} ≠ a
Cardinality
the cardinality of a set is the number of elements in the set
 cardinality is denoted by A
Empty set
 the empty set is denoted by {} or ∅
Universal set
the universal set is the set containing all elements of all sets needed to discuss a topic
 denoted by U
 e.g. U might be ℝ in Calculus, or ℂ in algebra
Basic notation
The following format is used to indicate a set
S = { x ∈ A … }
which is read as “x is an element of A (x ∈ A
) such that (
) some property is true (…
).
For example, S = { x ∈ ℤ  –2 < x < 5 }
which is equal to { –1, 0, 1, 2, 3, 4 }
.
Venn diagrams
 when solving a problem using Venn diagrams, you must state what each of the subsets means before you draw the diagram
 note that often you can use inclusionexclusion principle (covered later) rather than Venn Diagrams
Subset
A is a subset of B if and only if every element of A is also an element of B
 A ⊆ B indicates that A is a subset of the set B
 A is the proper subset of B, A ⊂ B, if A ⊆ B but A ≠ B
The following properties are useful:
 if A = B then A ⊆ B and B ⊆ A
 if A ⊂ B then A ⊆ B
 if A ⊆ B and B ⊆ A then A = B (this is used to prove that two sets are equal)
 A is a proper subset of B if it is a subset of B and B has at least one element that is not also in A
Power set
The power set of a set is the set of all subsets of the set.
 given a set A, then power set of A is the set of all of the subsets of the set S
 the power set of S is denoted by P(S)
For example,
P({ 0, 1, 2 }) = {
∅,
{ 0 }, { 1 }, { 2 },
{ 0, 1 }, { 1, 2 },
{ 0, 1, 2 },
}
Note: For a set X, X ∈ P(S) and X ⊆ S mean the same thing
Cardinality of a power set
If  A  = n then  P(A)  = 2^{n}
Or, in English, the size of the power set is equal to 2^{n} where n is the number of elements in the set.
Set algebra
Union
The union of the sets A and B is the set that contains the elements that are either in A or in B, or in both.
 denoted by A ∪ B

A ∪ B = { x x ∈ A or x ∈ B }
Intersection
the set containing elements that in both A and B
 A ∩ B
Disjoint sets
two sets are disjoint if their intersection is the empty set (i.e. they have no elements in common)
Set difference
The difference of A and B, A – B, is the set containing elements in A but not in B.
 Note that A – B ≠ B – A
 Note that A ∩ B^{c} = A – B
Complement
The complement of A is A^{c}. A^{c} = U – A is the set of elements in U but not in A.
Laws of set algebra
 Commutative laws: A ∪ B = B ∪ A and A ∩ B = B ∩ A
 Associative laws: A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C
 Distribute laws: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
 Idempotent laws: A ∪ A = A and A ∩ A = A
 Double complement laws: (A^{c})^{c} = A
 De Morgan’s laws: (A ∪ B)^{c} = A^{c} ∩ B^{c} and (A ∩ B )^{c} = A^{c} ∪ B^{c}
 Identity laws: A ∪ ∅ = A and A ∩ U = A
 Domination laws: A ∪ U = U and A ∩ ∅ = ∅
 Intersection and union with complement: A ∩ A^{c} = ∅ and A ∪ A^{c} = U
 Alternative representation for set difference: A – B = A ∩ B^{c}
Keep in mind: the property of duality (‘dual’) means that you can swap ∩ and ∪, and swap ∅ and U. This helps you to remember less, which is good.
Generalised union and intersection
See your textbook or course notes for this stuff; it’s hard to write in HTML.
Disjoint
As above,
two sets are disjoint if their intersection is the empty set (i.e. they have no elements in common)
Pairwise disjoint
Sets A_{1}, A_{2}, …, A_{n} are pairwise disjoint if and only if A_{i} ∩ A_{j} = ∅ whenever i ≠ j
(i.e. any 2 sets have no overlapping elements)
Partition
A set of nonempty sets { A_{1}, A_{2}, …, A_{n} } is a partition of a set A if and only if
 A = A_{1} ∪ A_{2} ∪ … ∪ A_{n}
 A_{1}, A_{2}, …, A_{n} are pairwise disjoint
(i.e. all of the sets combine to produce the whole, but none of the sets have the same elements)
Cartesian product
A × B is the cartesian product is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
 Note that A^{2} = A × A
For example,
let A = { 1, 2 }
let B = { 2, 3 }
then
A × B = { (1, 2), (1, 3), (2, 2), (2, 3) }
We can also think of these as xy coordinate pairs, and they can be sketched on a number plane as such.
Relations
A binary relation R from set x to y (written as xRyxRy or R(x,y)R(x,y)) is a subset of the Cartesian product x×yx×y. If the ordered pair of G is reversed, the relation also changes.
Generally an nary relation R between sets A1,…, and AnA1,…, and An is a subset of the nary product A1×⋯×AnA1×⋯×An. The minimum cardinality of a relation R is Zero and maximum is n2n2 in this case.
A binary relation R on a single set A is a subset of A×AA×A.
For two distinct sets, A and B, having cardinalities m and n respectively, the maximum cardinality of a relation R from A to B is mn.
Domain and Range
If there are two sets A and B, and relation R have order pair (x, y), then −
 The domain of R, Dom(R), is the set {x(x,y)∈R for some y in B}{x(x,y)∈R for some y in B}
 The range of R, Ran(R), is the set {y(x,y)∈R for some x in A}{y(x,y)∈R for some x in A}
Examples
Let, A={1,2,9}A={1,2,9} and B={1,3,7}B={1,3,7}
 Case 1 − If relation R is ‘equal to’ then R={(1,1),(3,3)}R={(1,1),(3,3)}Dom(R) = {1,3},Ran(R)={1,3}{1,3},Ran(R)={1,3}
 Case 2 − If relation R is ‘less than’ then R={(1,3),(1,7),(2,3),(2,7)}R={(1,3),(1,7),(2,3),(2,7)}Dom(R) = {1,2},Ran(R)={3,7}{1,2},Ran(R)={3,7}
 Case 3 − If relation R is ‘greater than’ then R={(2,1),(9,1),(9,3),(9,7)}R={(2,1),(9,1),(9,3),(9,7)}Dom(R) = {2,9},Ran(R)={1,3,7}{2,9},Ran(R)={1,3,7}
Representation of Relations using Graph
A relation can be represented using a directed graph.
The number of vertices in the graph is equal to the number of elements in the set from which the relation has been defined. For each ordered pair (x, y) in the relation R, there will be a directed edge from the vertex ‘x’ to vertex ‘y’. If there is an ordered pair (x, x), there will be self loop on vertex ‘x’.
Suppose, there is a relation R={(1,1),(1,2),(3,2)}R={(1,1),(1,2),(3,2)} on set S={1,2,3}S={1,2,3}, it can be represented by the following graph −
Types of Relations
 The Empty Relation between sets X and Y, or on E, is the empty set ∅∅
 The Full Relation between sets X and Y is the set X×YX×Y
 The Identity Relation on set X is the set {(x,x)x∈X}{(x,x)x∈X}
 The Inverse Relation R’ of a relation R is defined as − R′={(b,a)(a,b)∈R}R′={(b,a)(a,b)∈R}Example − If R={(1,2),(2,3)}R={(1,2),(2,3)} then R′R′ will be {(2,1),(3,2)}{(2,1),(3,2)}
 A relation R on set A is called Reflexive if ∀a∈A∀a∈A is related to a (aRa holds)Example − The relation R={(a,a),(b,b)}R={(a,a),(b,b)} on set X={a,b}X={a,b} is reflexive.
 A relation R on set A is called Irreflexive if no a∈Aa∈A is related to a (aRa does not hold).Example − The relation R={(a,b),(b,a)}R={(a,b),(b,a)} on set X={a,b}X={a,b} is irreflexive.
 A relation R on set A is called Symmetric if xRyxRy implies yRxyRx, ∀x∈A∀x∈Aand ∀y∈A∀y∈A.Example − The relation R={(1,2),(2,1),(3,2),(2,3)}R={(1,2),(2,1),(3,2),(2,3)} on set A={1,2,3}A={1,2,3} is symmetric.
 A relation R on set A is called AntiSymmetric if xRyxRy and yRxyRximplies x=y∀x∈Ax=y∀x∈A and ∀y∈A∀y∈A.Example − The relation R={(x,y)→Nx≤y}R={(x,y)→Nx≤y} is antisymmetric since x≤yx≤y and y≤xy≤x implies x=yx=y.
 A relation R on set A is called Transitive if xRyxRy and yRzyRz implies xRz,∀x,y,z∈AxRz,∀x,y,z∈A.Example − The relation R={(1,2),(2,3),(1,3)}R={(1,2),(2,3),(1,3)} on set A={1,2,3}A={1,2,3} is transitive.
 A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive.Example − The relation R={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)}R={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)} on set A={1,2,3}A={1,2,3} is an equivalence relation since it is reflexive, symmetric, and transitive.
Functions
A function ƒ from a set X to a set Y is a subset of X × Y with the property that for each x ∈ X, there is exactly one ordered pair (x, y) ∈ ƒ.
Takeaways from that definition’s mess:
 a function is a set.
 each x value can only be paired with one y value.
The function
ƒ : X → Y
has X as the domain and Y as the codomain (the codomain is the set containing all of the y values that could occur).
Floor and ceiling
For any x ∈ ℝ,
Floor: the largest integer that is less than or equal to x. Written as ⌊x⌋.
Ceiling: the smallest integer that is greater than or equal to x. Written as ⌈x⌉.
For example, ⌊π⌋ = 3, ⌈π⌉ = 4
Range
The range of a function ƒ : X → Y is the set of all y ∈ Y such that there is an ordered pair (x, y) in ƒ. That is, { y ∈ Y  (x, y) ∈ ƒ for some x ∈ X }
More or less, the set of all the y values that actually occur.
Onetoone
A function ƒ is onetoone (or injective) if and only if for each y in the codomain there is only one (i.e. one or none at all) ordered pair (x, y) in ƒ.
i.e., ƒ is onetoone means that if ƒ(x_{1}) = ƒ(x_{2}), then x_{1} = x_{2}.
 recall from Calculus that increasing functions (ƒ′(x) > 0) are onetoone and that the horizontal line test can be used
Onto
A function ƒ : X → Y is onto (or surjective) if and only if for every element y ∈ Y there is an element x ∈ X with y = ƒ(x).
i.e., a function is onto if its range equals its codomain.
Bijection
A function is a bijection if it is both onetoone and onto.
Composition of functions
Let g : X → Y and ƒ : Y → Z. Then the composition of ƒ and g, ƒ ∘ g, is the function from X to Z defined by (ƒ ∘ g)(x) = ƒ(g(x)).
 for proofs involving composition you will possibly need to “take f (or g) of both sides”
Inverse functions
Let ƒ : X → Y. If ƒ is a bijection, then there is a function g : Y → X which, given any y ∈ Y, g(y) is the element x ∈ X such that y = ƒ(x). i.e., g(y) = x and y = ƒ(x)
 g is called the inverse function of ƒ, written as ƒ^{–1}
Composition of a function and its inverse
If ƒ “does something” to a variable, then ƒ^{1} “undoes” it.
 ƒ^{1} ∘ ƒ is the function i—called the identity function. It does nothing.
Pigeonhole Principle
If ‘n’ number of pigeons or objects are to placed in ‘k’ number of pigeonholes or boxes; where k<n then there must be at least one pigeonhole or box which has more than ceil(n/k) object.
Applications
Pigeonhole principle is widely applicable to many fields. It is fairly applied in computer science. It is quite useful in computer programming and in various algorithms. Pigeonhole principle plays a vital role in mathematical analysis also. It is used in different problems related to arithmetic, geometry, economics, finance etc. This principle is very commonly used in practical problems related to probability theory and statistics.
Not only in subjects related to mathematics and science, pigeonhole principle is applied to many other fields, such as: in sports in order to choose the team members.
The extensions of pigeonhole principle are applied to many areas related to arts, like: geology, mining, geography etc.
Examples
There are many examples which use pigeonhole principle. Few of the examples are given below:
1) Golf: Let us suppose that there are 8 balls and 7 holes. If balls are to be put in different holes, then at least one hole must have more than one ball.
2) Handshake: If a number of people does handshake with one another, then according to pigeonhole principle, there must exist two people who shake hanks with same people.
3) Birthday: Let us consider that n people are chosen at random from a group of people. Then, in order to find the probability of having same birthday, pigeonhole principle is applied. It says that at least two people will have same birthday.
4) Marble picking: Consider that we have a mixture of different color marbles in a jar. In order to find at least how many marbles will be picked before two same color marbles are guaranteed. It can be calculated using pigeonhole principle assuming one pigeonhole per color will be assumed.
InclusionExclusion Principle
In combinatorics (combinatorial mathematics), the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
AUB=A+BA∩B
where A and B are two finite sets and S indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The doublecounted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection.
The principle is more clearly seen in the case of three sets, which for the sets A, B and C is given by
AUBUC=A+B+CA∩BA∩CB∩C+A∩B∩C
This formula can be verified by counting how many times each region in the Venn diagramfigure is included in the righthand side of the formula. In this case, when removing the contributions of overcounted elements, the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be added back in to get the correct total.
For more details Read This.
Equivalence and Partial Orderings
Equivalence relations
Definition:
A relation R is an equivalence relation if and only if it is reflexive, symmetric and transitive.
Examples:
Let m and n be integers and let d be a positive integer. The notation
The meaning is: the integer division of d into m gives the same remainder
as the integer division of d into n.
Consider the relation R = {(x,y) x mod 3 = y mod 3}
For example, 4 mod 3 = 1, 7 mod 3 = 1, hence hence (4,7) Î R.
The relation is
symmetric: if x mod 3 = y mod 3, then y mod 3 = x mod 3
transitive: if x mod 3 = y mod 3, and y mod 3 = z mod 3, then x mod 3 = z mod 3
[1] = {1,4,7,10,13,….}
[2] = {2,5,8,11,14,…}
[1] = [4] =…
[2] = [5] = …
Each number is exactly in one of these sets.
The set {[0], [1], [2]} is a partition of the set of nonnegative integers.
Theorem: Each equivalence relation on a set induces a partition of that set,
and each partition of a set induces an equivalent relation on the set.
The sets in the partition are called classes of equivalence.
Partial orders
Definition:
R is a partial order relation iff R is transitive and antisymmetric.

 : R is reflexive.
Strict partial order

 : R is not reflexive (irreflexive or neither reflexive nor irreflexive).
Examples:


 Let A be a set, and P(A) be the power set of A.
The relation ‘subset of’ on P (A) is a partial order relation  Let N be the set of positive integers, and R be a relation defined as follows:
 Let A be a set, and P(A) be the power set of A.

(x, y) Î R iff y is a multiple of x, e.g. (3,12) Î R, while (3, 4) Ï R
R is a partial order relation. It is reflexive, antisymmetric, and transitive
Elementary Counting Techniques
The Rule of Sum and Rule of Product are used to decompose difficult counting problems into simple problems.
 The Rule of Sum − If a sequence of T1,T2,…,Tm can be done in w1,w2,…wm ways respectively (the condition is that no tasks can be performed simultaneously), then the number of ways to do one of these tasks is w1+w2+⋯+wm. If we consider two tasks A and B which are disjoint (i.e. A∩B=∅), then mathematically A∪B=A+B
 The Rule of Product − If a sequence of tasks T1,T2,…,Tm can be done in w1,w2,…wm ways respectively and every task arrives after the occurrence of the previous task, then there are w1×w2×⋯×wm ways to perform the tasks. Mathematically, if a task B arrives after a task A, then A×B=A×B
A permutation is an arrangement of some elements in which order matters. In other words a Permutation is an ordered Combination of elements.
A combination is selection of some given elements in which order does not matter.
Probability
Probability theory was invented in the 17th century by two French mathematicians, Blaise Pascal and Pierre de Fermat, who were dealing with mathematical problems regarding of chance.
Before proceeding to details of probability, let us get the concept of some definitions.
Random Experiment − An experiment in which all possible outcomes are known and the exact output cannot be predicted in advance is called a random experiment. Tossing a fair coin is an example of random experiment.
Sample Space − When we perform an experiment, then the set S of all possible outcomes is called the sample space. If we toss a coin, the sample space S={H,T}S={H,T}
Event − Any subset of a sample space is called an event. After tossing a coin, getting Head on the top is an event.
The word “probability” means the chance of occurrence of a particular event. The best we can say is how likely they are to happen, using the idea of probability.
Conditional Probability
The conditional probability of an event B is the probability that the event will occur given an event A has already occurred. This is written as P(BA).
Mathematically − P(BA)=P(A∩B)/P(A)
If event A and B are mutually exclusive, then the conditional probability of event B after the event A will be the probability of event B that is P(B).
Measure ( s ) for information and Mutual information.
In probability theory and information theory, the mutual information (MI) of two random variables is a measure of the mutual dependence between the two variables. More specifically, it quantifies the “amount of information” (in units such as shannons, more commonly called bits) obtained about one random variable, through the other random variable. The concept of mutual information is intricately linked to that of entropy of a random variable, a fundamental notion in information theory, that defines the “amount of information” held in a random variable.
Not limited to realvalued random variables like the correlation coefficient, MI is more general and determines how similar the joint distribution p(X,Y) is to the products of factored marginal distribution p(X)p(Y). MI is the expected value of the pointwise mutual information (PMI).
For more information Read this.
No Responses