# Discrete Structures Notes: An Introduction

## 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 inclusion-exclusion 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 XX ∈ P(S) and X ⊆ S mean the same thing

##### Cardinality of a power set

If | A | = n then | P(A) | = 2n

Or, in English, the size of the power set is equal to 2n 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 BA – B, is the set containing elements in A but not in B.

• Note that A – B ≠ B – A
• Note that A ∩ Bc = A – B

#### Complement

The complement of A is Ac. Ac = U – A is the set of elements in U but not in A.

### Laws of set algebra

1. Commutative laws: A ∪ B = B ∪ A and A ∩ B = B ∩ A
2. Associative laws: A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C
3. Distribute laws: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
4. Idempotent laws: A ∪ A = A and A ∩ A = A
5. Double complement laws: (Ac)c = A
6. De Morgan’s laws: (A ∪ B)c = Ac ∩ Bc and (A ∩ B )c = Ac ∪ Bc
7. Identity laws: A ∪ ∅ = A and A ∩ U = A
8. Domination laws: A ∪ U = U and A ∩ ∅ = ∅
9. Intersection and union with complement: A ∩ Ac = ∅ and A ∪ Ac = U
10. Alternative representation for set difference: A – B = A ∩ Bc

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 A1, A2, …, An are pairwise disjoint if and only if Ai ∩ Aj = ∅ whenever i ≠ j

(i.e. any 2 sets have no overlapping elements)

### Partition

A set of non-empty sets { A1, A2, …, An } is a partition of a set A if and only if

1. A = A1 ∪ A2 ∪ … ∪ An
2. A1, A2, …, An 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 A2 = 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 co-ordinate 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 n-ary relation R between sets A1,, and AnA1,…, and An is a subset of the n-ary 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)fosomiB}{x|(x,y)∈R for some y in B}
• The range of R, Ran(R), is the set {y|(x,y)fosomiA}{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)|xX}{(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 RR′ will be {(2,1),(3,2)}{(2,1),(3,2)}
• A relation R on set A is called Reflexive if aA∀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 aAa∈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 yRxyRxxA∀x∈Aand yA∀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 Anti-Symmetric if xRyxRy and yRxyRximplies x=yxAx=y∀x∈A and yA∀y∈A.Example − The relation R={(x,y)N|xy}R={(x,y)→N|x≤y} is anti-symmetric since xyx≤y and yxy≤x implies x=yx=y.
• A relation R on set A is called Transitive if xRyxRy and yRzyRz implies xRz,x,y,zAxRz,∀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 (xy) ∈ ƒ.

Takeaways from that definition’s mess:

1. a function is a set.
2. 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 (xy) in ƒ. That is, { y ∈ Y | (xy) ∈ ƒ for some x ∈ X }

More or less, the set of all the y values that actually occur.

### One-to-one

A function ƒ is one-to-one (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 (xy) in ƒ.

i.e., ƒ is one-to-one means that if ƒ(x1) = ƒ(x2), then x1 = x2.

• recall from Calculus that increasing functions (ƒ′(x) > 0) are one-to-one 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 one-to-one 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.

## Inclusion-Exclusion 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|+|B|-|A∩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 double-counted 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|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

This formula can be verified by counting how many times each region in the Venn diagramfigure is included in the right-hand side of the formula. In this case, when removing the contributions of over-counted 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.

## 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

º n (mod d)is read “m is congruent to n modulo d“.
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

reflexive: x mod 3 = x mod 3
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
Consider the sets [x]= {y | yRx}, where x is an integer, and R is the relation above.

[0] = {0,3,6,9,12,….}
[1] = {1,4,7,10,13,….}
[2] = {2,5,8,11,14,…}
From the definition of [x] it follows that

[0] = [3] = [6] …
[1] = [4] =…
[2] = [5] = …
Thus the relation R produces three different sets [0], [1] and [2].

Each number is exactly in one of these sets.
The set {[0], [1], [2]} is a partition of the set of non-negative 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:

Let R be a binary relation defined on a set A.
R is a partial order relation iff R is transitive and anti-symmetric.
Weak partial order

1. : R is reflexive.

Strict partial order

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

Examples:

1. 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
2. Let N be the set of positive integers, and R be a relation defined as follows:

(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, anti-symmetric, 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. AB=), then mathematically |AB|=|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|

permutation is an arrangement of some elements in which order matters. In other words a Permutation is an ordered Combination of elements.

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(B|A).

Mathematically − P(B|A)=P(AB)/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 real-valued 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).