Tag: Unit – 1 : Discrete Structures and Optimization notes

UGC NET Computer Science Unit 1 – Optimization

Go back to UGC NET COMUPTER SCIENCE

UGC NET Computer Science Application – OPTIMIZATION

(Linear Programming · Simplex · Dual Simplex · Sensitivity · Integer Programming · Transportation · Assignment · PERT · CPM · Resource Levelling · Cost Considerations)

1. LINEAR PROGRAMMING (LP)

Definition: Linear Programming

Linear programming is a mathematical technique for optimizing (maximizing or minimizing) a linear objective function, subject to a set of linear constraints.

General structure:

Objective function

$Z = c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n}$
Subject to constraints:

$a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{i n} x_{n} \leq, =, \geq b_{i}$
with non-negativity constraints:

$x_{j} \geq 0$

Explanation

LP is used where resources (labor, materials, machines) are limited and must be allocated optimally.

Simple Example

Maximize

$Z = 3 x + 2 y$

Subject to:

$x + y \leq 4, x, y \geq 0$

2. MATHEMATICAL MODEL (FORMULATION)

Definition

Formulation is the process of expressing a real-world optimization problem as an LPP using:

Decision variables
Objective function
Constraints

Explanation

This converts a word problem into equations.

Example

A factory makes chairs (x) and tables (y).
Profit = 50x + 80y
Wood constraint → 3x + 5y ≤ 30
Labor constraint → 2x + y ≤ 10

3. GRAPHICAL SOLUTION METHOD

Definition

A method to solve LPPs with two variables by drawing constraints on a 2D graph and identifying the feasible region.

Explanation

Convert inequalities into lines.
Shade feasible region.
Compute objective value at each vertex.
Best value gives the optimum.

Example

Line x + y = 4 divides the plane; feasible region lies below it.

4. SIMPLEX METHOD

Definition

The Simplex Method is an iterative algebraic method to solve LPPs with two or more variables.

Explanation

Converts inequalities to equalities by adding slack, surplus, artificial variables
Builds a tableau
Performs pivoting to improve the solution
Stops when no negative indicators remain in the objective row

Key Terms

Basic variables: variables with non-zero values
Non-basic variables: set to zero
Pivot element: used for row operations

5. DUAL SIMPLEX METHOD

Definition

A modification of simplex used when:

The objective row is feasible
The basic solution is infeasible (negative RHS)

Explanation

Dual Simplex works by making the RHS feasible through pivoting until all RHS ≥ 0.

6. SENSITIVITY ANALYSIS

Definition

Sensitivity analysis studies how changes in:

Coefficients of objective function
RHS of constraints
Constraint coefficients
affect the optimal solution.

Key Terms

Shadow price: change in optimal Z when RHS of a constraint increases by 1 unit.
Reduced cost: amount by which objective coefficient must improve before variable enters basis.
Allowable range: how much parameters can vary without altering the optimal solution.

7. INTEGER PROGRAMMING (IP)

Definition

An optimization model where some or all decision variables must be integers.

Types

Pure Integer Programming – all variables integer
Mixed Integer Programming – some integer
0–1 (Binary) Programming – variables can be 0 or 1

Explanation

Used where fractional decisions are impossible (e.g., number of machines can’t be 2.5).

Methods

Branch & Bound
Cutting Plane
Dynamic Programming

8. TRANSPORTATION PROBLEM

Definition

A special LPP that deals with transporting commodities from multiple sources to multiple destinations at minimum cost.

Explanation

Rows: sources
Columns: destinations
Each cell: cost of transporting one unit

Balance condition:
Total supply = Total demand

Initial Solution Methods

North-West Corner
Least Cost Method
Vogel’s Approximation Method (VAM)

Optimal Solution Methods

MODI (u – v method)
Stepping-Stone Method

9. ASSIGNMENT PROBLEM

Definition

A special case of transportation where:

Supply = demand = 1
One person does one task only

Goal: Minimize cost or maximize efficiency.

Explanation

Square cost matrix (NxN).
Solved by Hungarian Method.

Steps

Row reduction
Column reduction
Covering zeros
Optimal assignment

10. PERT (PROGRAM EVALUATION REVIEW TECHNIQUE)

Definition

PERT is a project management tool using probabilistic time estimates to compute expected project duration.

Explanation

Each activity has three time estimates:

$a$ = optimistic time
$m$ = most likely time
$b$ = pessimistic time

Expected Time

$t_{e} = \frac{a + 4 m + b}{6}$

Variance

$σ^{2} = {(\frac{b - a}{6})}^{2}$

Used when time is uncertain.

11. CPM (CRITICAL PATH METHOD)

Definition

A deterministic technique to determine the longest duration path (critical path) through a project network.

Explanation

Activities have certain times
Critical Path = longest path
Activities on this path have zero float

Float Types

Total Float (TF)
Free Float (FF)
Independent Float (IF)

Critical Path Formula

Critical path = sequence of activities with

$Slack = 0$

12. CRITICAL PATH CALCULATIONS

Steps

1. Forward Pass (Earliest Times)

Compute Earliest Start (ES)
Compute Earliest Finish (EF = ES + duration)

2. Backward Pass (Latest Times)

Compute Latest Finish (LF)
Compute Latest Start (LS = LF – duration)

3. Slack Calculation

$Slack = L S - E S$

Activities with Slack = 0 → critical.

13. RESOURCE LEVELLING

Definition

Resource levelling adjusts activity start times to smooth out resource usage over time.

Explanation

Prevents:

sudden peaks in manpower
idle resources
overburdening specific days

Used for optimizing:

labor
machines
budgets

14. COST CONSIDERATION IN PROJECT SCHEDULING

Definition

Scheduling must consider both direct and indirect costs to obtain the lowest total project cost.

Direct Costs

Cost of performing activity itself.

Indirect Costs

Administrative, supervision, overhead.

Crash Cost

Additional cost for reducing activity duration.

Explanation

Project duration vs cost curve is U-shaped.
Goal → Find minimum total cost.

COMPLETE CHAPTER SUMMARY (Exam Sheet)

Concept	Definition	Keyword
LP	Optimize linear objective under linear constraints	linear + feasible
Simplex	Table-based root-finding	pivot
Dual Simplex	Fix infeasible RHS	RHS negative
Sensitivity	Post-optimal impact study	shadow price
Integer Programming	Variables restricted to integers	branch & bound
Transportation	Min cost supply–demand problem	VAM, MODI
Assignment	One-to-one allocation	Hungarian
PERT	Probabilistic time	expected time
CPM	Deterministic time	critical path
Resource Levelling	Smooth resource usage	no peaks
Cost Scheduling	Total = Direct + Indirect	crashing

December 4, 2025

UGC NET Computer Science Unit 1 – Boolean Algebra

Go back to UGC NET COMUPTER SCIENCE

UGC NET Computer Science Application – Unit 1 – Boolean Algebra

(Boolean Functions, Representations, Simplification)

1. BOOLEAN ALGEBRA

Definition

A Boolean Algebra is an algebraic structure

$(B, +, \cdot,^{'})$

with elements 0 and 1, and three operations:

OR → $+$
AND → $\cdot$
NOT → $x^{'}$

It satisfies the following axioms for all $x, y, z \in B$ :

Commutative laws
- $x + y = y + x$
- $x \cdot y = y \cdot x$
Associative laws
- $(x + y) + z = x + (y + z)$
- $(x \cdot y) \cdot z = x \cdot (y \cdot z)$
Distributive laws
- $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$
- $x + (y \cdot z) = (x + y) (x + z)$
Identity elements
- $x + 0 = x$
- $x \cdot 1 = x$
Complement
- $x + x^{'} = 1$
- $x \cdot x^{'} = 0$

2. BOOLEAN FUNCTIONS

Definition

A Boolean function of n variables is a mapping:

$f : {0, 1}^{n} \to {0, 1}$

Example:

$f (x, y) = x y^{'} + x^{'} y$

(This is XOR.)

Truth Tables

A Boolean function can be represented by a truth table listing all input combinations and outputs.

Example

Function $f (x, y) = x + y^{'}$ :

x	y	y′	f
0	0	1	1
0	1	0	0
1	0	1	1
1	1	0	1

3. REPRESENTATION OF BOOLEAN FUNCTIONS

Boolean functions can be represented in canonical forms:

A. Sum of Products (SOP)

A function written as OR of AND terms.

Definition

SOP form consists of minterms (product terms in which every variable appears in complemented or uncomplemented form).

Example

$f (x, y, z) = x^{'} y z + x y^{'} + x z$

Canonical SOP (Minterm Form)

$f = \sum m (i)$

where $m (i)$ are minterms where output = 1.

Example

Given truth table output = 1 for minterms 1, 3, 4 →

$f = \sum m (1, 3, 4)$

B. Product of Sums (POS)

Function written as AND of OR terms.

Definition

POS form consists of maxterms (sum terms where each variable appears).

Canonical POS

$f = \prod M (i)$

Where $M (i)$ are maxterms for output = 0.

Example

Output is 0 for rows 2 and 5 →

$f = \prod M (2, 5)$

⭐ C. Other Representations

Boolean Expression (normal algebraic form)
K-map Representation
Logic Circuit representation (using AND/OR/NOT gates)

4. MINTERMS & MAXTERMS

Minterm

A minterm is a product term containing all variables exactly once (either complemented or not).

Example (3 variables):

$m_{3} = x^{'} y z$

Maxterm

A maxterm is a sum term containing all variables.

Example:

$M_{5} = (x + y^{'} + z)$

5. SIMPLIFICATION OF BOOLEAN FUNCTIONS

Simplification reduces Boolean expressions to minimum number of literals and gates.

Methods:

Boolean Algebra Laws
Karnaugh Maps (K-Maps)
Quine–McCluskey method (tabular, for large expressions)

6. SIMPLIFICATION USING BOOLEAN LAWS

Example

Simplify

$f = x y + x^{'} y$

Solution:

$f = y (x + x^{'}) = y (1) = y$

Example

$f = x + x y$

Solution (Absorption law):

$x + x y = x$

Example

$f = (x + y) (x + y^{'})$

Solution (Using algebra):

$= x + y y^{'} = x + 0 = x$

7. KARNAUGH MAP (K-MAP) SIMPLIFICATION

K-maps group adjacent 1s to simplify expressions.

Rules

Groups must be of size 1, 2, 4, 8, …
Groups must be powers of 2
Wrap-around grouping is allowed
Larger groups → simpler answer

Example (2-variable K-map)

AB	0	1
00	1	0
01	1	1

Minterms: $m_{0}, m_{1}, m_{3}$

Group m0 & m1 → gives A′
Group m1 & m3 → gives B

So simplified form:

$f = A^{'} + B$

8. QUINE–McCLUSKEY METHOD

Used for systematic algebraic simplification when variables > 4.

Steps:

List minterms in binary.
Group by number of 1s.
Combine terms that differ in only one bit.
Find prime implicants.
Identify essential prime implicants.
Construct minimal expression.

9. PRIME IMPLICANTS

Definition

A prime implicant is a product term obtained by grouping 1s that cannot be combined further.

10. ESSENTIAL PRIME IMPLICANTS

Definition

A prime implicant that contains at least one minterm not covered by any other implicant.

These must appear in the simplified expression.

11. LOGIC GATE REPRESENTATION

Boolean expressions can be drawn using:

AND gates
OR gates
NOT gates
NAND / NOR universal gates

Example

Expression:

$f = x y + z$

Circuit:

AND gate for $x y$
OR gate to add $z$

Quick Summary for Exam

Topic	Key Idea
Boolean Algebra	Deals with 0/1 logic
Representations	SOP, POS, minterms, maxterms
Simplification	Laws, K-maps, QM method
Canonical Forms	Unique representations
Prime Implicants	Largest groups of 1s
Essential	Must be included in final expression

December 4, 2025

UGC NET Computer Science Unit 1 – Graph Theory
Go back to UGC NET COMUPTER SCIENCE

GRAPH THEORY

(Groups, Subgroups, Semi Groups, Product and Quotients of Algebraic, Structures, Isomorphism, Homomorphism, Automorphism, Rings, Integral Domains, Fields, Applications of Group Theory)

1. SIMPLE GRAPH

Definition

A simple graph is a graph in which:
1. There is at most one edge between any pair of vertices.
2. There are no loops (no edge from a vertex to itself).
A simple graph $G = (V, E)$ consists of:
- $V$ : Set of vertices
- $E$ : Set of unordered pairs of distinct vertices
Example

Vertices: {A, B, C}
Edges: {AB, BC}
No loops, no parallel edges → simple graph.

2. MULTIGRAPH

Definition

A multigraph is a graph where:
- Multiple (parallel) edges between the same pair of vertices are allowed.
- Loops may or may not be allowed (depending on the author).
Example

Two edges between A and B → multigraph.

3. WEIGHTED GRAPH

Definition

A weighted graph assigns a numerical value (weight) to each edge.

Weights represent:
- distance
- cost
- time
- capacity
Example

A triangle graph with edges weighted 1, 3, 4.

4. PATHS AND CIRCUITS

Definition: Path

A path in a graph is a sequence of distinct vertices where every consecutive pair is connected by an edge.

Example:
A → B → D → E

Definition: Circuit (Cycle)

A circuit is a path that begins and ends at the same vertex, with no repeated edges.

Example:
A → B → C → A

5. SHORTEST PATHS IN WEIGHTED GRAPHS

Definition

A shortest path between two vertices is the path with minimum total weight.

Algorithm (important for NET)
- Dijkstra’s Algorithm: For non-negative weights
- Bellman–Ford: For negative weights
Example

If A→B=3 and A→C→B=1+1=2,
shortest path from A to B is A → C → B.

6. EULERIAN PATHS AND CIRCUITS

Definition: Euler Path

A path that uses every edge exactly once.

Definition: Euler Circuit

A circuit that uses every edge exactly once and returns to the starting vertex.

Theorems (Very important)

Euler Circuit Theorem

A connected graph has an Euler circuit iff every vertex has even degree.

Euler Path Theorem

A connected graph has an Euler path iff exactly 0 or 2 vertices have odd degree.

7. HAMILTONIAN PATHS AND CIRCUITS

Definition: Hamiltonian Path

A path that visits every vertex exactly once.

Definition: Hamiltonian Circuit

A Hamiltonian path that returns to the starting vertex.

Key Notes
- No simple degree condition like Euler.
- Hamiltonian problems are NP-complete.
Example

Cycle graph $C_{n}$ is Hamiltonian (n ≥ 3).

8. PLANAR GRAPH

Definition

A graph is planar if it can be drawn on a plane without edge crossings.

Euler’s Formula (Very important)

For a connected planar graph:

$V - E + F = 2$

Where
- V = vertices
- E = edges
- F = faces (regions)
9. GRAPH COLORING

Definition

Graph coloring assigns colors to vertices so that adjacent vertices have different colors.

Chromatic Number (χ(G))

Minimum number of colors needed.

Example

A triangle (3-cycle) needs 3 colors:

$χ (C_{3}) = 3$

10. BIPARTITE GRAPHS

Definition

A graph is bipartite if its vertices can be divided into two sets U and V such that:
- Every edge connects a vertex in U to a vertex in V
- No edge connects two vertices within the same set.
Theorem

A graph is bipartite iff it has no odd cycle.

Example

A square (4-cycle) is bipartite.

11. TREES

Definition

A tree is a connected graph with no cycles.

Equivalent statements:
- A tree with n vertices has n−1 edges.
- Exactly one path exists between every pair of vertices.
- Removing any edge disconnects the tree.
12. ROOTED TREES

Definition

A rooted tree is a tree with one vertex chosen as root.

Terms used:
- Parent
- Child
- Sibling
- Ancestor
- Descendant
- Level / Depth
- Height
13. PREFIX CODES

Definition

A prefix code is a set of binary strings where no code word is a prefix of another.

Used in data compression (Huffman coding).

Example

Valid: {0, 10, 110, 111}
Not valid: {0, 01} (0 is a prefix of 01)

14. TREE TRAVERSALS

Definition

Tree traversal means visiting nodes of a tree in a specified order.

1. Preorder Traversal

Root → Left → Right

2. Inorder Traversal

Left → Root → Right

3. Postorder Traversal

Left → Right → Root

15. SPANNING TREES

Definition

A spanning tree of a connected graph G is a subgraph that:
- includes all vertices,
- is a tree (no cycles),
- has minimum possible edges (n−1).
Minimum Spanning Tree (MST)

Spanning tree with minimum total weight.

Algorithms
- Prim’s Algorithm
- Kruskal’s Algorithm
16. CUT-SETS

Definition

A cut-set is a set of edges whose removal disconnects the graph.

Example

In a triangle graph, removing any two edges forms a cut-set.
December 4, 2025
UGC NET Computer Science Unit 1 – Group Theory
Go back to UGC NET COMUPTER SCIENCE

UNIT-1 — Group Theory (UGC NET: Computer Science & Applications)

(Groups • Subgroups • Semigroups • Product & Quotients • Isomorphism • Homomorphism • Automorphism • Rings • Integral Domains • Fields • Applications)

1. SEMIGROUPS

Definition: Semigroup

A semigroup is a set $S$ with a binary operation $*$ such that:
1. Closure:
  For all $a, b \in S$ ,
  
  $a * b \in S .$
2. Associativity:
  For all $a, b, c \in S$ ,
  
  $(a * b) * c = a * (b * c) .$
No requirement of identity or inverse.

Example:

$(N, +)$ is a semigroup.

2. MONOID

Definition: Monoid

A monoid is a semigroup with an identity element $e$ such that:

$e * a = a * e = a \forall a \in S .$

Example:

$(N_{0}, +)$ with identity 0.

3. GROUPS

Definition: Group

A group is a set $G$ with a binary operation $*$ satisfying:
1. Closure: $a * b \in G$ .
2. Associativity: $(a * b) * c = a * (b * c)$ .
3. Identity: There exists $e \in G$ such that $e * a = a * e = a$
4. Inverse: For each $a \in G$ , there exists $a^{- 1} \in G$ such that
  
  $a * a^{- 1} = a^{- 1} * a = e .$
Definition: Abelian Group

A group is Abelian (or commutative) if:

$a * b = b * a \forall a, b \in G .$

4. SUBGROUPS

Definition: Subgroup

A non-empty subset $H$ of a group $G$ is a subgroup if:
1. $a, b \in H \Rightarrow a * b^{- 1} \in H$
  (one-step subgroup test)
– OR –

Equivalent conditions:
- Closed under operation
- Closed under inverse
- Contains identity
Cyclic Subgroup

Generated by an element $g \in G$ :

$⟨ g ⟩ = {g^{n} : n \in Z} .$

5. PRODUCT OF ALGEBRAIC STRUCTURES

Definition: Direct Product of Groups

For groups $G$ and $H$ ,

$G \times H = {(g, h) : g \in G, h \in H}$

with operation

$(g_{1}, h_{1}) * (g_{2}, h_{2}) = (g_{1} * g_{2}, h_{1} * h_{2}) .$

This forms a group.

6. QUOTIENT GROUPS (FACTOR GROUPS)

Normal Subgroup (Important)

A subgroup $N$ of group $G$ is normal if:

$g N = N g \forall g \in G$

or equivalently

$g n g^{- 1} \in N \forall g \in G, n \in N .$

Definition: Quotient Group

If $N$ is a normal subgroup of $G$ :

$G / N = {g N : g \in G}$

with operation

$(g N) (h N) = (g h) N .$

7. HOMOMORPHISM, ISOMORPHISM, AUTOMORPHISM

Definition: Homomorphism

A function $f : G \to H$ between groups is a homomorphism if:

$f (a * b) = f (a) * f (b) \forall a, b \in G .$

Kernel:

$\ker (f) = {x \in G : f (x) = e_{H}}$

Image:

$Im (f) = {f (x) : x \in G}$

Definition: Isomorphism

A homomorphism that is bijective.
Isomorphic groups have:
- same structure
- same properties
- different elements but identical algebraic behavior
Notation:

$G ≅ H$

Definition: Automorphism

An isomorphism from a group to itself:

$f : G \to G .$

The set of all automorphisms forms a group under composition.

8. RINGS

Definition: Ring

A ring $(R, +, \cdot)$ is a set with two operations satisfying:

Under Addition:
- Associative
- Commutative
- Identity (0)
- Inverses exist (each element has an additive inverse)
Under Multiplication:
- Associative
- Closed
Distributive Laws:

$a (b + c) = a b + a c, (a + b) c = a c + b c .$

Definition: Commutative Ring

If multiplication is commutative:

$a b = b a .$

Definition: Ring with Unity

A ring with multiplicative identity $1$ such that

$1 \cdot a = a \cdot 1 = a .$

9. INTEGRAL DOMAINS

Definition: Integral Domain

A commutative ring with unity and no zero divisors.

Zero divisor definition:

Non-zero $a, b \in R$ such that

$a b = 0.$

Thus, in an integral domain:

$a b = 0 \Rightarrow a = 0 or b = 0.$

Examples:
- $Z$
- Polynomial rings over fields
10. FIELDS

Definition: Field

A set $F$ with two operations (+,·) such that:

Under addition:

Forms an Abelian group.

Under multiplication:

Non-zero elements $F - {0}$ form an Abelian group.

Distributivity holds.

Examples:
- Rational numbers $Q$
- Real numbers $R$
- Complex numbers $C$
- Finite field $G F (p)$ where p is prime
11. APPLICATIONS OF GROUP THEORY (in Computer Science)

✔ Cryptography
– Uses groups, rings, finite fields
– Example: RSA, ECC use modular arithmetic groups

✔ Coding Theory
– Error-correcting codes use group and field structures
– Linear codes over finite fields

✔ Automata Theory
– Symmetry groups help in minimizing finite automata

✔ Graph Theory
– Automorphism groups classify graphs by symmetry

✔ Computer Graphics
– Rotations & transformations form groups

✔ Network Theory
– Cayley graphs build interconnection networks

✔ Algorithms
– Group operations used in hashing, randomization
December 4, 2025
UGC NETComputer Science Unit 1 – Counting, Mathematical Induction and Discrete Probability
Go back to UGC NET COMUPTER SCIENCE

UNIT 1 — Counting, Mathematical Induction and Discrete Probability

(UGC NET)

(Counting • Pigeonhole Principle • Permutations • Combinations • Inclusion–Exclusion • Mathematical Induction • Probability • Bayes’ Theorem)

1. BASICS OF COUNTING — DEFINITIONS

Definition 1: Counting Principle (Product Rule)

If an action consists of k independent stages, and the stages can be performed in

$n_{1}, n_{2}, \dots, n_{k} ways respectively,$

then the total number of ways of performing the action is

$n_{1} \times n_{2} \times \dots \times n_{k} .$

Definition 2: Sum Rule (Addition Principle)

If an action can be performed in m ways or n ways, and the two sets of possibilities are mutually exclusive,

$Total ways = m + n .$

Definition 3: Factorial (n!)

For any positive integer n:

$n! = n (n - 1) (n - 2) \dots 1$

and by definition

$0! = 1.$

2. PERMUTATIONS — DEFINITIONS

Definition 4: Permutation

A permutation is an arrangement of objects in a specific order.

Definition 5: r-Permutation of n Objects

The number of ways to arrange r objects out of n:

$^{n} P_{r} = \frac{n!}{(n - r)!}$

Definition 6: Permutation with Repetition

If among n objects,
- $n_{1}$ are alike,
- $n_{2}$ are alike, etc.,
then number of distinct permutations:

$\frac{n!}{n_{1}! n_{2}! \dots}$

3. COMBINATIONS — DEFINITIONS

Definition 7: Combination

A combination is a selection of r objects from n objects where order does not matter.

Definition 8: r-Combination of n Objects

$^{n} C_{r} = \frac{n!}{r! (n - r)!}$

Key Relation

$^{n} P_{r} =^{n} C_{r} \cdot r!$

4. PIGEONHOLE PRINCIPLE — DEFINITIONS & STATEMENTS

Definition 9: Pigeonhole Principle (Basic)

If more than n objects are placed into n boxes, then at least one box contains more than one object.

Formal Statement:
If $n + 1$ objects are placed into $n$ boxes, at least one box contains ≥ 2 objects.

Definition 10: Generalized Pigeonhole Principle

If N objects are placed into k boxes, then at least one box contains

$⌈ \frac{N}{k} ⌉$

objects.

5. INCLUSION–EXCLUSION PRINCIPLE — STATEMENTS

Definition 11: Inclusion–Exclusion Principle (Two Sets)

For any two sets A and B,

$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣ .$

Definition 12: Inclusion–Exclusion (Three Sets)

$∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣ .$

6. MATHEMATICAL INDUCTION — DEFINITIONS & STEPS

Definition 13: Principle of Mathematical Induction

Let $P (n)$ be a statement depending on a natural number n.
If:
1. Base Step: $P (1)$ is true.
2. Induction Step: $P (k) \Rightarrow P (k + 1)$ for all natural numbers k,
Then $P (n)$ is true for all natural numbers.

Definition 14: Strong Induction

A statement $P (n)$ is true for all natural numbers n if:
1. $P (1)$ is true.
2. Assuming all of $P (1), P (2), \dots, P (k)$ are true implies $P (k + 1)$ .
7. PROBABILITY — DEFINITIONS

Definition 15: Sample Space (S)

The set of all possible outcomes of an experiment.

Definition 16: Event (E)

Any subset of the sample space.

Definition 17: Probability of an Event

If all outcomes are equally likely:

$P (E) = \frac{∣ E ∣}{∣ S ∣}$

Definition 18: Complement of an Event

$P (E^{'}) = 1 - P (E)$

Definition 19: Conditional Probability

$P (A ∣ B) = \frac{P (A \cap B)}{P (B)}, P (B) > 0$

Definition 20: Independent Events

Two events A and B are independent if:

$P (A \cap B) = P (A) P (B)$

8. BAYES’ THEOREM — STATEMENT

Definition 21: Bayes’ Theorem

If $A_{1}, A_{2}, \dots, A_{n}$ form a partition of the sample space and B is any event with $P (B) > 0$ , then:

$P (A_{i} ∣ B) = \frac{P (B ∣ A_{i}) P (A_{i})}{\sum_{j = 1}^{n} P (B ∣ A_{j}) P (A_{j})}$

This theorem is used to reverse conditional probability.
December 4, 2025
UGC NET Computer Science Unit 1 – Sets & Relations
UNIT–1 (SETS & RELATIONS)

(Set Operations, Representation of Relations, Properties of Relations, Equivalence & Partial Order Relations)

PART A — SETS

1. What is a Set? (Definition)

A set is a well-defined collection of objects (called elements) such that it is possible to clearly decide whether an element belongs to the set or not.

Key idea:
✔ “Well-defined” means no ambiguity.
✔ Sets are written using curly braces.

Examples:
- A = {1,2,3,4}
- B = {a, e, i, o, u}
- C = {x | x is an even natural number}
Non-example:
- “All beautiful flowers” → not well-defined (beauty is subjective)
2. Important Types of Sets

2.1 Empty set (Null set)

A set with no elements.
Symbol: Ø or { }
Example: Set of even prime numbers > 2.

2.2 Finite and Infinite sets
- Finite: elements can be counted
- Infinite: unending, e.g., natural numbers ℕ
2.3 Equal sets

Two sets A and B are equal if every element of A is in B and vice-versa.

2.4 Subset

A ⊆ B means every element of A is also in B.

Example:
A = {1,2}
B = {1,2,3,4}
→ A ⊆ B

Proper subset:
A ⊂ B if A ⊆ B and A ≠ B.

2.5 Power Set

P(A) = set of all subsets of A.
If |A| = n → |P(A)| = 2ⁿ.

Example:
A = {1,2}
P(A) = { Ø, {1}, {2}, {1,2} }

3. SET OPERATIONS

Operations on sets are exactly parallel to logical operations.

Let A and B be sets in a universal set U.

3.1 Union (A ∪ B)

Statement: Set of all elements that belong to A, or to B, or to both.

Example:
A={1,2}, B={2,3}
A∪B = {1,2,3}

3.2 Intersection (A ∩ B)

Statement: Elements common to both A and B.

A={1,2}, B={2,3}
A∩B = {2}

3.3 Difference (A – B)

Statement: Elements belonging to A but not in B.

A − B = {elements in A that are not in B}

Example:
A={1,2,3}, B={2,4}
A−B={1,3}

3.4 Symmetric Difference (A Δ B)

Statement: Elements that are in A or in B but NOT in both.
AΔB = (A−B) ∪ (B−A)

Example:
A={1,2,3}, B={3,4,5}
AΔB = {1,2,4,5}

3.5 Complement (A′)

Everything in the universal set U that is NOT in A.

A′ = U − A

4. IMPORTANT SET IDENTITIES

These laws are vital for proofs and simplifications.

Identity Laws
- A ∪ Ø = A
  → “Adding nothing changes the set.”
- A ∩ U = A
  → “Intersecting with everything gives the set.”
Domination Laws
- A ∪ U = U
- A ∩ Ø = Ø
Statement:
“Union with universal set gives universal set; intersection with empty set gives empty set.”

Idempotent Laws
- A ∪ A = A
- A ∩ A = A
Commutative Laws
- A ∪ B = B ∪ A
- A ∩ B = B ∩ A
Associative Laws
- (A ∪ B) ∪ C = A ∪ (B ∪ C)
- (A ∩ B) ∩ C = A ∩ (B ∩ C)
Distributive Laws
- A ∩ (B ∪ C) = (A∩B) ∪ (A∩C)
- A ∪ (B ∩ C) = (A∪B) ∪ (A∪C)
Absorption Laws
- A ∪ (A ∩ B) = A
- A ∩ (A ∪ B) = A
De Morgan’s Laws
- (A ∪ B)′ = A′ ∩ B′
- (A ∩ B)′ = A′ ∪ B′
These correspond to logical laws for (∨, ∧, ¬).

PART B — RELATIONS

Relations form the mathematical structure for describing connections between objects.
They generalize functions, orders, equivalence, graph relations, database relations, etc.

5. RELATION — DEFINITION

A relation R from set A to set B is a subset of the Cartesian product A × B.

That is:
R ⊆ A × B

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

5.1 Binary Relation on a Set

A relation R on A is a subset of A × A.

Example:
A={1,2,3}
R = {(1,1),(2,2),(1,3)} is a relation on A.

6. REPRESENTATION OF RELATIONS

A relation can be represented in three ways:

6.1 (a) Set of Ordered Pairs

Direct listing of (a,b).

Example:
R = {(1,2),(2,3),(3,1)}

6.1 (b) Matrix Representation

If A = {a₁,a₂,…,aₙ}, R is represented by an n×n matrix M:

$m_{i j} = {\begin{cases} 1 & if (a_{i}, a_{j}) \in R \\ 0 & otherwise \end{cases}$

Used heavily in computing and adjacency matrices.

6.1 (c) Directed Graph (Digraph)
- Each element of A is a node.
- Each pair (a,b) ∈ R is a directed edge from a→b.
Graphical representation helps visualize transitivity, symmetry, closure, etc.

7. PROPERTIES OF RELATIONS

These properties define the nature of the relationship.

Let R be a relation on set A.

7.1 Reflexive Relation

Definition (Statement):

A relation R on A is reflexive if every element relates to itself.

$(a, a) \in R for every a \in A$

Example:
A = {1,2,3}
R = {(1,1),(2,2),(3,3),(1,2)} → reflexive

Non-example:
Missing even one (a,a) → not reflexive.

7.2 Symmetric Relation

Definition (Statement):

A relation R is symmetric if:

If (a,b) ∈ R then (b,a) ∈ R.

Example (symmetric):
R = {(1,2),(2,1),(2,3),(3,2)}

Non-example:
If (1,2) ∈ R but (2,1) ∉ R → not symmetric.

7.3 Antisymmetric Relation

Definition (Statement):

A relation R is antisymmetric if:

If (a,b) ∈ R and (b,a) ∈ R, then a = b.

Example (antisymmetric):
Set A = {1,2,3}
Relation: “≤”
Because if a ≤ b and b ≤ a → a = b.

Non-example:
(1,2) and (2,1) in R with 1≠2 → violates antisymmetry.

7.4 Transitive Relation

Definition (Statement):

A relation R is transitive if:

If (a,b) and (b,c) ∈ R → (a,c) must also be in R.

Example:
If a divides b and b divides c → a divides c.

Non-example:
If (a,b),(b,c) ∈ R but (a,c) ∉ R.

8. COMBINED RELATIONS — IMPORTANT TYPES

8.1 Equivalence Relation (VERY IMPORTANT)

Definition (Statement):

A relation R on A is an equivalence relation if it is:
1. Reflexive
2. Symmetric
3. Transitive
Meaning:
An equivalence relation groups elements into “categories” or “classes” of items that are considered equivalent.

Equivalence Class

For element a ∈ A, the equivalence class is:

$[a] = {x \in A ∣ (a, x) \in R}$

Meaning:
“All elements related to a.”

Example: Congruence modulo n

Define relation:
a ≡ b (mod n)
Meaning: “a and b leave same remainder when divided by n.”

Properties:
✔ reflexive: a≡a
✔ symmetric: if a≡b then b≡a
✔ transitive: if a≡b and b≡c then a≡c

→ So it’s an equivalence relation.

Each equivalence class contains all numbers with same remainder.

8.2 Partition of a Set

Equivalence relations partition a set into disjoint subsets (equivalence classes).

Properties of partition:
1. Classes are nonempty
2. Classes are disjoint
3. Union of all classes = A
Equivalence relations ↔ partitions.

These two concepts are dual to each other.

9. PARTIAL ORDER RELATIONS (POSets)

These describe ordered or hierarchical structure.

9.1 Partial Order Relation

Definition (Statement):

A relation R on A is a partial order if it is:
1. Reflexive
2. Antisymmetric
3. Transitive
Symbol: (A, ≤) is a poset (partially ordered set).

Example:
- “Divides” relation on {1,2,4,8}
- “Subset (⊆)” relation on P(S)
9.2 Total (Linear) Order

A partial order is total if every pair of elements is comparable.

That is, for any a and b:
Either a ≤ b or b ≤ a.

Example (total order):
- Natural numbers with ≤
- Alphabet with alphabetical order
Non-example:
Subset relation is not total.

9.3 Hasse Diagrams (Poset Representation)

Used to represent partial orders graphically:

Rules:
- Draw elements as nodes
- Draw edge upward if a < b and there is no c such that a < c < b
- Omit loops and transitive edges
10. Reflexive–Symmetric–Transitive Closures (Advanced but important)

Sometimes a relation R does not have a property, and we want the smallest relation that includes R and satisfies the property.

Reflexive closure:

Add (a,a) for all a ∈ A missing from R.

Symmetric closure:

Add (b,a) if (a,b) is in R but (b,a) missing.

Transitive closure:

Add (a,c) whenever (a,b) and (b,c) exist.

Used in database theory (Warshall’s algorithm), graph theory, and automata.
December 3, 2025