Tag: Unit – 1 : Discrete Structures and Optimization – UGC NET Exam

UGC NET Computer Science Unit 1 SET-1
Go back to UGC NET COMUPTER SCIENCE

Expected Questions with Solutions

Unit – 1 : Discrete Structures and Optimization

A. Mathematical Logic (Propositional & Predicate Logic, Inference)
1. ¬∃x Q(x) is equivalent to:
  (1) ∃x ¬Q(x)
  (2) ∀x ¬Q(x)
  (3) ¬∀x ¬Q(x)
  (4) ∀x Q(x)
  Answer: (2)
  Explanation: Negation of an existential becomes universal negation: ¬∃x Q(x) ≡ ∀x ¬Q(x).
2. From (P → Q) ∧ (R → S) and P ∨ R, what follows (Y)?
  (1) P ∨ R
  (2) P ∨ S
  (3) Q ∨ R
  (4) Q ∨ S
  Answer: (4)
  Explanation: If P then Q; if R then S. From P∨R we derive Q∨S.
3. “Agra and Gwalior are both in India.” Student wrote: In(Agra,India) ∨ In(Gwalior,India). This is:
  (1) Syntactically valid but wrong meaning
  (2) Syntactically valid and correct meaning
  (3) Syntactically invalid but correct meaning
  (4) Invalid and wrong meaning
  Answer: (1)
  Explanation: Sentence requires AND; OR changes meaning. Syntax is valid but semantics wrong.
4. Knowledge base: ∃x AsHighAs(x, Everest). After existential instantiation we get
  (a) AsHighAs(Everest, Everest)
  (b) AsHighAs(Kilimanjaro, Everest)
  Options:
  (1) Both (a) and (b) are sound conclusions.
  (2) Both (a) and (b) are unsound conclusions.
  (3) (a) is sound but (b) is unsound.
  (4) (a) is unsound but (b) is sound.
  Answer: (2) — (In some papers the key differs; see explanation below.)
  Short explanation: Existential instantiation must introduce a new arbitrary constant; substituting existing named constants (Everest, Kilimanjaro) is unsound.
5. Given FOL: ((R ∨ Q) ∧ (P ∨ Q)). Which is equivalent?
  Options show same expression repeated in the paper; all choices are identical.
  Answer: Any option (they are identical)
  Explanation: The options are identical textually; the expression stands as given.
B. Sets & Relations (Set operations, Equivalence, Partial Orders)
1. If Aᵢ = {−i, …, −1, 0, 1, …, i} for i ≥ 1, then ⋃_{i=1}^{∞} Aᵢ =
  (1) Z
  (2) Q
  (3) R
  (4) C
  Answer: (1) Z
  Explanation: As i → ∞ the union includes all integers.
2. Which of the following relations on {0,1,2,3} is an equivalence relation?
  (1) {(0,0),(0,2),(2,0),(2,2),(2,3),(3,2),(3,3)}
  (2) {(0,0),(1,1),(2,2),(3,3)}
  (3) {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0)}
  (4) {(0,0),(0,2),(2,3),(1,1),(2,2)}
  Answer: (2)
  Explanation: Identity relation has reflexivity, symmetry, transitivity.
3. Which relation on functions f,g: Z→Z is an equivalence relation?
  (1) f(x) − g(x) = 1
  (2) f(0)=g(0) OR f(1)=g(1)
  (3) f(0)=g(1) AND f(1)=g(0)
  (4) f(x) − g(x) = k (for some integer k)
  Answer: (4)
  Explanation: Difference-by-constant is reflexive (k=0), symmetric (negate), transitive (sum).
4. Which is true?
  (1) (Z, ≤) is not totally ordered
  (2) ⊆ is a partial order on P(S)
  (3) (Z, ≠) is a poset
  (4) Directed graph is not a partial order
  Answer: (2)
  Explanation: Subset relation is reflexive, antisymmetric and transitive.
5. Match:
  (a) ∀x∀y (f(x)=f(y) → x=y)
  (b) ∀y ∃x (f(x)=y)
  (c) ∀x f(x)=k
  (i) Constant (ii) Injective (iii) Surjective
  Codes: (1) (i)(ii)(iii) (2) (iii)(ii)(i) (3) (ii)(i)(iii) (4) (ii)(iii)(i)
  Answer: (4)
  Explanation: (a) injective, (b) surjective, (c) constant.
C. Counting, Pigeonhole, Permutations & Combinations, Induction
1. Consider A = {1,2,…,1000}. How many members are divisible by 3 or 5 or both?
  (A) 533 (B) 599 (C) 467 (D) 66
  Answer: (paper keys vary — mathematically = C) (C) 467; several uploaded keys show (A) 533 (answer-key discrepancy).
  Explanation: Using inclusion–exclusion: ⌊1000/3⌋+⌊1000/5⌋−⌊1000/15⌋ = 333+200−66 = 467.
2. How many multiples of 6 between 0 and 100, and between −6 and 34?
  (1) 16 and 6
  (2) 17 and 6
  (3) 17 and 7
  (4) 16 and 7
  Answer: (3)
  Explanation: Multiples of 6 from 0 to 100: 0,6,…,96 → 17 numbers (including 0). From −6 to 34: −6,0,6,…,30 → 7 numbers.
3. Number of atomic events (five-card poker hands)?
  (1) 2,598,960 (2) 3,468,960 (3) 3,958,590 (4) 2,645,590
  Answer: (1)
  Explanation: C(52,5) = 2,598,960.
4. Number of ways to arrange letters of “DISCRETE”:
  (1) 8! (2) 8!/2! (3) 8!/3! (4) 7!
  Answer: (2)
  Explanation: 8 letters with E repeated twice → 8!/2!.
5. Number of permutations of 5 distinct objects taken 3 at a time:
  (A) 60 (B) 10 (C) 125 (D) 5
  Answer: (A) 60
  Explanation: P(5,3)=5×4×3=60.
6. Pigeonhole: 13 pigeons into 12 holes ⇒ some hole has at least how many pigeons?
  (A)1 (B)2 (C)13 (D)12
  Answer: (B) 2
  Explanation: Ceiling(13/12)=2.
7. Probability: rolling two dice, P(sum=7):
  (1) 1/6 (2) 1/9 (3) 1/12 (4) 1/36
  Answer: (1) 1/6
  Explanation: 6 favourable / 36 total.
8. Flipping coin 10 times: number of atomic events:
  (1) 2⁵ (2) 2¹⁰ (3) 10! (4) 100
  Answer: (2) 2¹⁰
  Explanation: 2 outcomes per flip → 2¹⁰ sequences.
D. Probability & Bayes
1. Selecting k uniformly from {1..1,000,000} a million times: P(k=1 appears at least once):
  (A) 0.5 (B) 0.704 (C) 0.632121 (D) 0.68
  Answer: (C) ≈ 0.632121
  Explanation: P(not 1 each trial) = 1 − 1/1e6; (1 − 1/1e6)^{1e6} ≈ e^{−1}; 1 − e^{−1} ≈ 0.632121.
2. If A and B independent with P(A)=0.3, P(B)=0.4, then P(A∪B)=
  (A) 0.12 (B) 0.58 (C) 0.7 (D) 0.3
  Answer: (B) 0.58
  Explanation: P(A)+P(B)−P(A)P(B)=0.3+0.4−0.12=0.58.
3. Bayes formula: P(H|E)= ?
  (A) P(E|H)P(E)/P(H)
  (B) P(E|H)P(H)/P(E)
  (C) P(H)P(E)
  (D) P(E)/P(H)
  Answer: (B)
  Explanation: Standard Bayes’ rule.
4. If A,B,C are events, which is true?
  (1) P(A∪B) = P(A)+P(B)−P(AB)
  (2) P(A∪B∪C) = P(A)+P(B)+P(C)
  (3) P(A∪B) ≥ P(A)
  (4) P(A∪B) ≤ P(A)
  Answer: (3)
  Explanation: Union never decreases probability.
E. Graph Theory & Trees
1. A tree with two vertices degree 4, one vertex degree 3, one vertex degree 2, rest degree 1 → total vertices?
  (A)5 (B)n−3 (C)20 (D)11
  Answer: (D) 11
  Explanation: Let number of leaves = x, n = x+4; sum degrees = 13 + x = 2(n−1)=2x+6 → x=7 → n=11.
2. This graph is a:
  (A) Complete Graph (B) Bipartite Graph (C) Hamiltonian Graph (D) All of the above
  Answer: (D)
  Explanation: Given graph (in paper) satisfies all three properties.
3. Hamiltonian graph G (|V|=n≥3). Which is true?
  (1) deg(v) ≥ n/2 for each v
  (2) |E| ≥ ½ (n−1)(n−2) + 2
  (3) deg(v)+deg(w) ≥ n whenever v and w not adjacent
  (4) All of the above
  Answer: (4)
  Explanation: These are sufficient conditions referenced in the paper.
4. Strict (full) binary tree with 19 leaves has how many nodes?
  (1) cannot have more than 37 nodes
  (2) has exactly 37 nodes
  (3) has exactly 35 nodes
  (4) cannot have more than 35 nodes
  Answer: (2) 37
  Explanation: In full binary tree: number nodes = 2L − 1.
5. Shortest path algorithm allowing negative edges (no negative cycles):
  (1) Dijkstra (2) Bellman–Ford (3) Prim (4) Floyd only
  Answer: (2) Bellman–Ford
  Explanation: Bellman–Ford handles negative edge weights.
6. Chromatic number of a cycle C_n is:
  (1) 2 (if n even), 3 (if n odd)
  (2) 3 (if n even), 2 (if n odd)
  (3) Always 2
  (4) Always 3
  Answer: (1)
  Explanation: Even cycles are 2-colorable, odd cycles need 3 colors.
F. Boolean Algebra & Automata
1. Consensus theorem identity:
  (A) XY + X′Z + YZ = XY + X′Z
  (B) X + X′Y = X + Y
  (C) XX′ = 0
  (D) X + X′ = 1
  Answer: (A)
  Explanation: Consensus term YZ redundant and can be removed.
2. Simplify (A + B)(A + B′):
  (1) A (2) B (3) AB (4) A′
  Answer: (1) A
  Explanation: Use absorption law: (A+B)(A+B′)=A.
3. Order of algorithm determining whether a Boolean function of n variables outputs 1 (brute force):
  (1) Logarithmic (2) Linear (3) Quadratic (4) Exponential
  Answer: (4) Exponential
  Explanation: Exhaustive checking needs O(2^n) evaluations.
G. Group Theory & Coding (selected Unit-1 items present)
1. Which structure is always commutative?
  (A) Any group (B) Abelian group (C) Semigroup (D) Non-abelian group
  Answer: (B) Abelian group
  Explanation: Abelian = group where operation commutes.
2. Order of a permutation expressed as disjoint cycles equals:
  (A) sum of cycle lengths (B) product of cycle lengths (C) LCM of cycle lengths (D) minimum cycle length
  Answer: (C) LCM
  Explanation: The permutation repeats after LCM of cycle lengths.
3. Hamming bound uses which RHS term for q-ary n-length code:
  Options: (1) q^n (2) q^t (3) q^{−n} (4) q^{−t}
  Answer: (1) q^n
  Explanation: Sphere-packing bound compares sum of spheres to q^n.
H. Optimization (LPP, Transportation, Assignment, PERT/CPM)
1. Given LPP with constraints (in paper) — which is true?
  (1) Solution x₁=100, x₂=0, x₃=0
  (2) Unbounded solution
  (3) No solution
  (4) Solution x₁=50, x₂=70, x₃=60
  Answer: (3) No solution (as per paper key)
  Explanation: The constraints as given are inconsistent → infeasible.
2. Transportation degeneracy occurs when number of basic variables <
  (A) m + n (B) m + n − 1 (C) mn (D) m − n
  Answer: (B) m + n − 1
  Explanation: Basic feasible solution should have m+n−1 basics; fewer indicates degeneracy.
3. A basic feasible solution of LP corresponds to:
  (A) any interior point (B) a vertex of polytope (C) centroid (D) none
  Answer: (B) a vertex (extreme point)
  Explanation: Basic feasible solutions map to vertices of feasible region.
4. PERT uses which distribution for activity times?
  (1) Exponential (2) Normal (3) Beta (4) Poisson
  Answer: (3) Beta
  Explanation: PERT models activity time with Beta distribution (approx. using optimistic, pessimistic, most likely).
5. In PERT/CPM the critical path is:
  (1) minimum duration path (2) maximum duration path (3) any path with slack (4) both (2) and (3)
  Answer: (2) maximum duration path (equivalently zero slack)
  Explanation: Critical path has longest duration; activities on it have zero total float.
6. Which of the following is FALSE about convex minimization?
  (1) Local minimum ⇒ global minimum
  (2) Global minima set is convex
  (3) Global minima set is concave
  (4) Strictly convex function has unique minimum
  Answer: (3) (false)
  Explanation: Global minima set of convex functions is convex (not concave).
MORE PRACTICE CUM EXPECTED QUESTIONS

Q41.

If $A, B, C$ are events in a probability space, then which of the following is TRUE?
(1) $P (A \cup B) = P (A) + P (B) - P (A B)$
(2) $P (A \cup B \cup C) = P (A) + P (B) + P (C)$
(3) $P (A \cup B) \geq P (A)$
(4) $P (A \cup B) \leq P (A)$

Answer: (3)
Explanation: A union can never reduce probability: $P (A \cup B) \geq P (A)$

Q42.

The number of atomic events in the sample space when a fair coin is flipped 10 times is:
(1) $2^{5}$
(2) $2^{10}$
(3) $10!$
(4) 100

Answer: (2)
Explanation: Each flip has 2 outcomes → $2^{10}$ sequences.

Q43.

A strictly binary tree with L leaves has
(1) $2 L + 1$ nodes
(2) $2 L - 1$ nodes
(3) $L - 1$ nodes
(4) $2 L$ nodes

Answer: (2)
Explanation: Full binary tree nodes = $2 L - 1$ .

Q44.

If a function $f$ is injective, then
(1) $f (x) = f (y) \Rightarrow x = y$
(2) $f (x) = k$ for all $x$
(3) $f$ is onto
(4) $f (x)$ never repeats

Answer: (1)
Explanation: Injective means one-to-one.

Q45.

If a relation R is reflexive and symmetric but not transitive, then R is
(1) Equivalence relation
(2) Partial order
(3) Not an equivalence relation
(4) Total order

Answer: (3)
Explanation: Equivalence requires all 3; missing transitivity → not equivalence.

Q46.

For a universal set $U$ and subset $A \subseteq U$ :
(1) $A^{'} \cup A = U$
(2) $A^{'} \cap A = U$
(3) $(A^{'})^{'} = \emptyset$
(4) $A^{'} \subseteq A$

Answer: (1)
Explanation: A set union its complement gives the universal set.

Q47.

Number of arrangements of the letters of “DISCRETE”:
(1) 8!
(2) 8!/2!
(3) 8!/3!
(4) 7!

Answer: (2)
Explanation: “E” is repeated twice → divide by 2!.

Q48.

If a fair die is rolled twice, the probability that the sum is 7 is
(1) 1/6
(2) 1/9
(3) 1/12
(4) 1/36

Answer: (1)
Explanation: 6 favourable outcomes → 6/36 = 1/6.

Q49.

The chromatic number of the cycle graph $C_{n}$ is:
(1) 2 if n even; 3 if n odd
(2) 3 if n even; 2 if n odd
(3) Always 2
(4) Always 3

Answer: (1)
Explanation: Even cycle: bipartite (2 colors). Odd cycle: needs 3.

Q50.

A relation R on A is antisymmetric if
(1) $a R b and b R a \Rightarrow a = b$
(2) $a R b \Rightarrow b R a$
(3) R is neither symmetric nor reflexive
(4) $a R b and b R a \Rightarrow a \neq b$

Answer: (1)
Explanation: This is the definition of antisymmetry.

Q51.

Simplify the Boolean expression:
$(A + B) (A + B^{'})$
(1) A
(2) B
(3) AB
(4) A’

Answer: (1)
Explanation: Use absorption: (A + B)(A + B′) = A.

Q52.

Shortest-path algorithm that works with negative edge weights (but no negative cycles):
(1) Dijkstra
(2) Bellman–Ford
(3) Prim
(4) Floyd–Warshall only

Answer: (2)
Explanation: Bellman–Ford is designed for graphs with negative edges.

Q53.

PERT uses which probability distribution for activity times?
(1) Exponential
(2) Normal
(3) Beta
(4) Poisson

Answer: (3)
Explanation: PERT uses 3-point Beta distribution.

Q54.

The number of atomic events when flipping a fair coin n times is
(1) n
(2) n!
(3) $2^{n}$
(4) $n^{2}$

Answer: (3)
Explanation: Each flip has 2 outcomes → $2^{n}$ .

Q55.

In a graph, the degree sum formula says:
(1) Sum of degrees = E
(2) Sum of degrees = 2E
(3) Sum of degrees = V
(4) Sum of degrees = V + E

Answer: (2)
Explanation: Handshaking lemma: ∑deg(v) = 2|E|.

Q56.

If a full binary tree has 15 internal nodes, the number of leaves is:
(1) 14
(2) 15
(3) 16
(4) 30

Answer: (3)
Explanation: In full binary tree: L = I + 1 = 16.

Q57.

A relation R on A is transitive if
(1) $a R b and b R c \Rightarrow a R c$
(2) $a R b = b R a$
(3) $a R a$ for all a
(4) None

Answer: (1)
Explanation: Direct definition of transitivity.

Q58.

Probability of getting exactly 2 heads in 4 fair coin tosses:
(1) 1/4
(2) 3/8
(3) 6/16
(4) 1/2

Answer: (3)
Explanation: C(4,2)=6; total outcomes=16 → 6/16.

Q59.

A graph is bipartite if and only if
(1) It has no odd cycle
(2) It is planar
(3) It is complete
(4) It has Euler path

Answer: (1)
Explanation: Characterization of bipartite graphs: no odd-length cycle.

Q60.

The value of C(10, 3) is
(1) 120
(2) 720
(3) 10
(4) 3

Answer: (1)
Explanation: 10C3 = 120.

Q61.

If events A and B are independent, then
(1) $P (A ∣ B) = P (A)$
(2) $P (A ∣ B) = 0$
(3) $P (A ∣ B) > P (A)$
(4) None of these

Answer: (1)
Explanation: Independence implies P(A|B)=P(A).

Q62.

The number of spanning trees in a tree with 10 vertices is
(1) 1
(2) 9
(3) 10
(4) 0

Answer: (1)
Explanation: A tree already IS a spanning tree → exactly one.

Q63.

In Boolean algebra, the identity element for AND is
(1) 0
(2) 1
(3) X
(4) X’

Answer: (2)
Explanation: A·1 = A.

Q64.

The number of subsets of a 5-element set is
(1) 10
(2) 25
(3) 32
(4) 64

Answer: (3)
Explanation: 2⁵ = 32.

Q65.

For a simple graph with 7 vertices, maximum possible number of edges is
(1) 21
(2) 7
(3) 14
(4) 35

Answer: (1)
Explanation: Maximum edges = n(n−1)/2 = 7×6/2 = 21.

Q66.

Which is a valid probability value?
(1) −0.2
(2) 1.4
(3) 0.5
(4) 2

Answer: (3)
Explanation: Probability must be in [0,1].

Q67.

A function f: A → B is surjective if
(1) every element of A is mapped
(2) f repeats values
(3) every element of B has a pre-image
(4) f is injective

Answer: (3)
Explanation: Surjection means onto.

Q68.

The chromatic number of a tree is
(1) 1
(2) 2
(3) 3
(4) n

Answer: (2)
Explanation: Any tree is bipartite.

Q69.

The probability of an impossible event is
(1) 1
(2) 1/2
(3) 0
(4) Undefined

Answer: (3)
Explanation: Impossible event = probability 0.

Q70.

In LP, the optimal solution always occurs at
(1) any point
(2) interior point
(3) a corner point
(4) outside feasible region

Answer: (3)
Explanation: Fundamental theorem of linear programming.

Q71.

In adjacency-matrix representation of a graph with n vertices, the matrix size is
(1) n
(2) n²
(3) n×n
(4) n−1

Answer: (3)
Explanation: Adjacency matrix is n×n.

Q72.

If P(A)=0.4, P(B)=0.5, and A,B mutually exclusive, then P(A∪B)=
(1) 0.9
(2) 0.2
(3) 1
(4) 0.1

Answer: (1)
Explanation: No overlap → sum of probabilities.

Q73.

If a∈A, then in set-builder form A =
(1) {x : x ≠ a}
(2) {x : x = a}
(3) {x : x has property of A}
(4) All

Answer: (3)
Explanation: Set-builder describes all elements satisfying the defining property.

Q74.

A graph with all even degrees is
(1) Hamiltonian
(2) Eulerian
(3) Tree
(4) Complete

Answer: (2)
Explanation: Eulerian graph ↔ connected + all vertices have even degree.

Q75.

If P(A)=0.6 and P(A′)=0.4, then
(1) Correct
(2) Incorrect
(3) Cannot say
(4) None

Answer: (1)
Explanation: A + A′ = 1.

Q76.

Number of edges in a tree with 30 vertices:
(1) 29
(2) 30
(3) 28
(4) None

Answer: (1)
Explanation: Tree with n vertices has n−1 edges.

Q77.

If a graph has an odd cycle, it is
(1) Bipartite
(2) Not bipartite
(3) Complete
(4) Tree

Answer: (2)
Explanation: Odd cycle → not bipartite.

Q78.

For a set of size n, number of proper subsets is
(1) $2^{n}$
(2) $2^{n} - 1$
(3) n
(4) n!

Answer: (2)
Explanation: Exclude the set itself.

Q79.

Which operation is associative?
(1) Union
(2) Intersection
(3) Both
(4) None

Answer: (3)
Explanation: Both ∪ and ∩ are associative.

Q80.

In a simple graph, maximum degree of any vertex is
(1) n
(2) n−1
(3) n²
(4) n/2

Answer: (2)
Explanation: A vertex can be connected to at most n−1 others.
December 4, 2025

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
UGC NET Computer Science UNIT 1 – Mathematical Logic
Go back to UGC NET COMUPTER SCIENCE

UNIT – 1 : DISCRETE STRUCTURES & LOGIC

Mathematical Logic
(Complete Conceptual Notes)

PART A — MATHEMATICAL LOGIC

1. PROPOSITIONAL LOGIC

1.1 What is a Proposition?

A proposition is a declarative sentence that expresses a fact and has a definite truth value:
either True (T) or False (F), but never both at the same time.

✔ Examples of Propositions (Meaningful Facts)
- “7 is a prime number.” → True
- “The Earth has two moons.” → False
✘ Not Propositions (No truth value / not a statement of fact)
- “Shut the door.” (command)
- “Where are you?” (question)
- “x is greater than 10.” (truth depends on x → open sentence)
Why important?
Because logic operates only on propositions with fixed truth values.

1.2 Propositional Variables

We use letters like p, q, r to represent propositions.

Example:
- Let p = “It is raining.”
- Let q = “The ground is wet.”
2. LOGICAL CONNECTIVES WITH STATEMENTS

Connectives combine propositions to form compound statements.

2.1 Negation (¬p)

Statement Form:

“NOT p” means that whatever p asserts, the negation asserts the opposite.

Example:
- p = “The sky is blue.”
- ¬p = “The sky is not blue.”
Truth rule:
- If p is true → ¬p is false
- If p is false → ¬p is true
2.2 Conjunction (p ∧ q)

Statement Form:

“p AND q” means both statements must be true simultaneously.

Example:
- p: “The power is on.”
- q: “The fan is running.”
- p ∧ q: “The power is on and the fan is running.”
2.3 Disjunction (p ∨ q)

Statement Form:

“p OR q” means at least one of the two statements must be true.

Example:
- p: “I will study.”
- q: “I will watch a movie.”
- p ∨ q: “I will study or watch a movie (or both).”
2.4 Implication (p → q)

Statement Form:

“If p is true, then q must also be true.”

Example:
- p: “It rains.”
- q: “The ground gets wet.”
- p → q: “If it rains, then the ground gets wet.”
Exception:
If it does NOT rain, the statement is considered true regardless of the ground’s condition.

2.5 Biconditional (p ↔ q)

Statement Form:

“p is true if and only if q is true.”

Example:
- p: “You pass the course.”
- q: “You score ≥ 40.”
- p ↔ q: “You pass the course if and only if you score ≥ 40.”
True when both p and q have the same truth value.

3. TRUTH TABLES (Purpose + Use)

Truth tables allow us to compute the truth value of compound propositions under all possible combinations.

4. PROPOSITIONAL EQUIVALENCES

Logical equivalences indicate when two compound statements always have the same truth value.

4.1 Double Negation

Statement:

“Saying ‘NOT NOT p’ means the same as saying p.”

Symbolically:
¬(¬p) ≡ p

4.2 De Morgan’s Laws

These describe how negation interacts with AND/OR.

Statements:
- “The negation of ‘p AND q’ is the same as ‘NOT p OR NOT q’.”
- “The negation of ‘p OR q’ is the same as ‘NOT p AND NOT q’.”
4.3 Implication Law

Statement:

“‘If p then q’ is equivalent to saying ‘Either p is false OR q is true.’”

p → q ≡ ¬p ∨ q

This is core to CNF/DNF.

4.4 Contrapositive (Key Logical Principle)

Statement:

“‘If p then q’ is logically equivalent to ‘If NOT q then NOT p’.”

4.5 Biconditional Law

Statement:

“‘p if and only if q’ means both ‘if p then q’ AND ‘if q then p’ must be true.”

5. NORMAL FORMS (CNF, DNF)

5.1 Disjunctive Normal Form (DNF)

Statement:

A formula is in DNF when it is expressed as an OR of AND terms.

Example Statement:
“p AND q is true OR p is false AND r is true.”

Symbolic:
(p ∧ q) ∨ (¬p ∧ r)

5.2 Conjunctive Normal Form (CNF)

Statement:

A formula is in CNF when it is expressed as an AND of OR terms.

Example Statement:
“Either p or q is true AND either p or r is true.”

Symbolic:
(p ∨ q) ∧ (p ∨ r)

PART B — PREDICATE LOGIC

6. PREDICATES

A predicate is an expression involving variables that becomes a proposition when specific values are substituted.

Example:
P(x): “x is divisible by 3.”
— P(6) is True
— P(7) is False

7. QUANTIFIERS

7.1 Universal Quantifier (∀)

Statement Meaning:

“∀x P(x)” means “For every x, P(x) is true.”

Example Statement:
“Every natural number is greater than or equal to 0.”

7.2 Existential Quantifier (∃)

Statement Meaning:

“∃x P(x)” means “There exists at least one x such that P(x) is true.”

Example Statement:
“There exists a number divisible by 6.”

8. NESTED QUANTIFIERS

Example 1

∀x ∃y P(x,y)

Statement Meaning:

“For every x, there exists a y such that P(x,y) holds.”

Example in math:
“For every number x, there is a number y greater than x.”

Example 2

∃y ∀x P(x,y)

Statement Meaning:

“There exists a single y such that for every x, P(x,y) holds.”

Example:
“There is one number y greater than all numbers x.”
→ False (no largest integer)

9. NEGATION OF QUANTIFIERS (WITH EXPLANATORY STATEMENTS)

Universal to Existential

¬∀x P(x)

Statement:

“It is NOT true that P(x) holds for all x”
⟹ “There exists at least one x for which P(x) does not hold.”

Existential to Universal

¬∃x P(x)

Statement:

“It is NOT true that there exists an x with P(x)”
⟹ “For every x, P(x) is false.”

10. RULES OF INFERENCE (WITH NATURAL LANGUAGE MEANINGS)

10.1 Modus Ponens

p, and p → q

Statement Meaning:

“If p is true, and p implies q, then q must be true.”

10.2 Modus Tollens

¬q, and p → q

Statement Meaning:

“If q is false, and p implies q, then p must be false.”

10.3 Hypothetical Syllogism

p → q, q → r

Statement Meaning:

“If p implies q, and q implies r, then p implies r.”

10.4 Simplification

p ∧ q
→ p

Statement:

“If both p and q are true, then p is true.”

10.5 Addition

p
→ p ∨ q

Statement:

“If p is true, then ‘p OR q’ is automatically true.”

10.6 Conjunction

p, q
→ p ∧ q

Statement:

“If p is true and q is true, then ‘p AND q’ is true.”
December 3, 2025

Tag: Unit – 1 : Discrete Structures and Optimization – UGC NET Exam

UGC NET Computer Science Unit 1 SET-1

Go back to UGC NET COMUPTER SCIENCE

Expected Questions with Solutions

Unit – 1 : Discrete Structures and Optimization

A. Mathematical Logic (Propositional & Predicate Logic, Inference)

B. Sets & Relations (Set operations, Equivalence, Partial Orders)

C. Counting, Pigeonhole, Permutations & Combinations, Induction

D. Probability & Bayes

E. Graph Theory & Trees

F. Boolean Algebra & Automata

G. Group Theory & Coding (selected Unit-1 items present)

H. Optimization (LPP, Transportation, Assignment, PERT/CPM)

MORE PRACTICE CUM EXPECTED QUESTIONS

Q41.

Q42.

Q43.

Q44.

Q45.

Q46.

Q47.

Q48.

Q49.

Q50.

Q51.

Q52.

Q53.

Q54.

Q55.

Q56.

Q57.

Q58.

Q59.

Q60.

Q61.

Q62.

Q63.

Q64.

Q65.

Q66.

Q67.

Q68.

Q69.

Q70.

Q71.

Q72.

Q73.

Q74.

Q75.

Q76.

Q77.

Q78.

Q79.

Q80.

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

Explanation

Simple Example

2. MATHEMATICAL MODEL (FORMULATION)

Definition

Explanation

Example

3. GRAPHICAL SOLUTION METHOD

Definition

Explanation

Example

4. SIMPLEX METHOD

Definition

Explanation

Key Terms

5. DUAL SIMPLEX METHOD

Definition

Explanation

6. SENSITIVITY ANALYSIS

Definition

Key Terms