UGC NET Computer Science

Discrete Structure

Introduction of Set theory

Set is a unordered collection of objects, known as elements or members of the set.
An element ‘a’ belong to a set A can be written as ‘a ∈ A’,  ‘a ∉ A’ denotes that a does not belong to the set A. Set is always denoted by the capital letter.


An element ‘a’ belong to a set A can be written as ‘a ∈ A’,  ‘a ∉ A’ denotes that a does not belong to the set A.

Representation of a Set 

A set can be represented by various methods. 3 common methods used for representing set:
1. Statement form.
2. Roaster form or tabular form method.
3. Set Builder method.

Statement form

In this representation, well defined description of the elements of the set is given. Below are some examples of same.
1. The set of all odd number less than 20.
2. The set of number less than 100 and more than 20.

Roster form

In this representation, elements are listed within the pair of brackets {} and are separated by commas. Below are two examples.
1. Let N is the set of natural numbers less than 10.
N = { 1 , 2 , 3, 4, 5, 6, 7, 8, 9}

Set builder form

In set builder set is describe by a property that its member must satisfy.
1. {x : x is odd number divisible by 60 and less than 150}.
2. {x : x is natural number less than 20}.

Equal sets

Two sets are said to be equal if both have same elements. and the order of elements can be changed For example A = {1, 3, 9, 7} and B = {3, 1, 7, 9} are equal sets.

Subset

A set A is said to be subset of another set B if and only if every element of set A is also a part of other set B.
Denoted by ‘‘.
‘A ⊆ B ‘ denotes A is a subset of B.

Finite set

When the number of elements in the set are bounded by the upper limit or there is countable number of elements then the set is called finite set. For example
A = {1, 3, 9, 7}

Infinite set

When the number of elements in the set are not bounded by the upper limit or there is uncountable number of elements then the set is called Infinite set. For example
A = {1, 3, 5, 7, 9……..}

Cardinality of set

Number of elements present in the given set is called the cardinality of set. For example The cardinality of A = {1, 3, 9, 7} is |A| = 4 The cardinality of null set is ZERO 0.

Null set

The set which contain no element then it is said to be Null set. Denoted by Phi Φ

Power Sets

Power set is the set all possible subset of the set S. Denoted by P(S).
Example : What is the power set of {0,1,2}?
Solution: All possible subsets
{∅}, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}.

Cardinality of power set is

2^n

, where n is number of element in a set.

Cartesian Products

Let A and B be two sets. Cartesian product of A and B is denoted by A × B, is the set of all ordered pairs (a,b), where a belong to A and B belong to B.

A × B = {(a, b) | a ∈ A ∧ b ∈ B}.

Example 1. What is Cartesian product of A = {1,2} and B = {a,b,c}.
Solution : A × B ={(1,a), (1,b), (1,c), (2,a), (2,b), (2,c) };


Cardinality of A × B
  is N*M, where N is the Cardinality of A and M is the cardinality of B. A × B is not same as B × A.

Set Operations (Set theory)

Union

Union of the sets A and B, denoted by A ∪ B, is the set of distinct element belongs to set A or set B, or both. For example A ={1,2,3} B = {3,4,5} Then
A ∪ B = {1, 2, 3. 4. 5}. In this example all elements of set A and all elements of set B come together and the common element come only once.

Intersection

Intersection of the sets A and B, denoted by A ∩ B, is the set of elements belongs to both A and B i.e. set of common element in A and B.
For example A ={1,2,3} B = {3,4,5} Then
A ∩ B = {3}. In this example only the common element come in intersection.

Disjoint

Two sets are said to be disjoint if their intersection is the empty set .i.e sets have no common elements. i.e Φ


Intersection of the sets A and B, denoted by A ∩ B, is the set of elements belongs to both A and B i.e. set of common element in A and B.

Relation

Relation R from set A to B is a subset of AxB which can be defined as
aRb <=> (a,b) € R <=> R(a,b).

Domain and Range:
If there are two sets A and B and Relation from A to B is R(a,b), then domain is defined as the set { a | (a,b) € R for some b in B} and Range is defined as the set {b | (a,b) € R for some a in A}.

Types of Relation:

  1. Empty Relation: A relation R on a set A is called Empty if the set A is empty set.
  2. Full Relation: A binary relation R on a set A and B is called full if AxB.
  3. Reflexive Relation: A relation R on a set A is called reflexive if (a,a) € R holds for every element a € A .i.e. if set A = {a,b} then R = {(a,a), (b,b)} is reflexive relation.
  4. Irreflexive relation : A relation R on a set A is called reflexive if no (a,a) € R holds for every element a € A.i.e. if set A = {a,b} then R = {(a,b), (b,a)} is irreflexive relation.
  5. Symmetric Relation: A relation R on a set A is called symmetric if (b,a) € R holds when (a,b) € R.i.e. The relation R={(4,5),(5,4),(6,5),(5,6)} on set A={4,5,6} is symmetric.
  6. AntiSymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.i.e. The relation R = {(a,b)→R|a ≤ b} is anti-symmetric since a ≤ b and b ≤ a implies a = b.
  7. Transiitive Relation: A relation R on a set A is called transitive if (a,b) € R and (b,c) € R then (a,c) € R for all a,b,c € A.i.e. Relation R={(1,2),(2,3),(1,3)} on set A={1,2,3} is transitive.
  8. Equivalence Relation: A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive. i.e. relation 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} is equivalence relation as it is reflexive, symmetric, and transitive.
  9. Asymmetric relation: Asymmetric relation is opposite of symmetric relation. A relation R on a set A is called asymmetric if no (b,a) € R when (a,b) € R.

Function

A function f from A to B is an assignment of exactly one element of B to each element of A (A and B are non-empty sets). A is called Domain of f and B is called co-domain of f. If b is the unique element of B assigned by the function f to the element a of A, it is written as f(a) = b. f maps A to B. means f is a function from A to B, it is written as f: A -.> B

  • Domain and co-domain – if f is a function from set A to set B, then A is called Domain and B is called co-domain.
  • Range – Range of f is the set of all images of elements of A. Basically Range is subset of co- domain.
  • Image and Pre-Image – b is the image of a and a is the pre-image of b if f(a) = b.

Properties of Function:

  1. Addition and multiplication: let F and f are two functions from A to B, then F + f and F.f are defined as-:
    (F+f)x = F(x) + f(x). (addition)
    (Ff)x = F(x) f(x). (multiplication)
  2. Equality: Two functions are equal only when they have same domain, same co-domain and same mapping elements from domain to co-domain.

Types of functions:

  1. One to one function(Injective): A function is called one to one if for all elements a and b in A, if f(a) = f(b),then it must be the case that a = b. It never maps distinct elements of its domain to the same element of its co-domain.
  2. Onto Function (surjective): If every element b in B has a corresponding element a in A such that f(a) = b. It is not required that a is unique; The function f may map one or more elements of A to the same element of B.
  3. One to one correspondence function(Bijective/Invertible): A function is Bijective function if it is both one to one and onto function.
  4. Inverse Functions:Bijection function are also known as invertible function because they have inverse function property. The inverse of bijection f is denoted as f-1. It is a function which assigns to b, a unique element a such that f(a) = b. hence f-1 (b) = a.

Pigeonhole Principle

The pigeonhole principle is one of the simplest but most useful ideas in mathematics, and can rescue us here. A basic version says that if (N+1) pigeons occupy N holes, then some hole must have at least 2 pigeons. Thus if 5 pigeons occupy 4 holes, then there must be some hole with at least 2 pigeons. It is easy to see why: otherwise, each hole as at most 1 pigeon and the total number of pigeons couldn’t be more than 4. (This proof shows that it does not even matter if the holes overlap so that a single pigeon occupies 2 holes.)

We can say as, if n + 1 objects are put into n boxes, then at least one box contains two or more objects.
The abstract formulation of the principle: Let X and Y be finite sets and let f: X –> Y be a function.

  • If X has more elements than Y, then f is not one-to-one.
  • If X and Y have the same number of elements and f is onto, then f is one-to-one.
  • If X and Y have the same number of elements and f is one-to-one, then f is onto.

Inclusion-Exclusion

In the field of Combinatorics, it is a counting method used to compute the cardinality of the union set. According to basic Inclusion-Exclusion principle:

  • For 2 finite sets  and , which are subsets of Universal set, then  and  are disjoint sets.Hence it can be said that,
    .
  • Similarily for 3 finite sets ,  and ,

Principle :

Inclusion-Exclusion principle says that for any number of finite sets A1,A2,A3…..Ai, Union of the sets is given by = Sum of sizes of all single sets – Sum of all 2-set intersections + Sum of all the 3-set intersections – Sum of all 4-set intersections .. + (-1)^i+1 Sum of all the i-set intersections.

In general it can be said that,

Properties :

  1. Computes the total number of elements that satisfy at least one of several properties.
  2. It prevents the problem of double counting.