Unit 3 : Discrete Structures & Optimization

DISCRETE STRUCTURES & OPTIMIZATION

UGC NET / JRF — Computer Science & Applications

High-Yield Study Notes & PYQ-Pattern Workbook (Unit 3)

Contents

Ch.1 — Mathematical & Propositional Logic

Ch.2 — Permutation, Combination, Probability

Ch.3 — Group Theory

Ch.4 — Set and Relation

Ch.5 — Boolean Algebra

Ch.6 — Linear Programming

One-Shot Revision

Mini Mock Test (Answer Key)

Beginner → Concept → NET-level → JRF-level. Compact by design — exam value over page count.

Chapter 1 — Mathematical & Propositional Logic

1.1 Propositions & Logical Connectives

SimpleA proposition is a statement that is either TRUE or FALSE, never both (e.g., "5 is prime" is a proposition; "Is it raining?" is NOT — it's a question, not a truth-bearing statement).

Connective	Symbol	Meaning
Negation	¬p	NOT p
Conjunction	p∧q	p AND q (true only if both true)
Disjunction	p∨q	p OR q (true if at least one true)
Implication	p→q	IF p THEN q
Biconditional	p↔q	p IF AND ONLY IF q

JRF trap — implication is FALSE only in one casep→q is FALSE only when p is TRUE and q is FALSE. In every other case (T,T), (F,T), (F,F) it is TRUE — including when p is false ("vacuously true"). Students often wrongly think p→q is false whenever p is false; it's actually the opposite.

1.2 Truth Tables, Tautology, Contradiction

IdeaA tautology is a compound proposition that is TRUE for every possible truth value of its components (e.g., p∨¬p). A contradiction is always FALSE (e.g., p∧¬p). A contingency is sometimes true, sometimes false.

Worked exampleShow p→q ≡ ¬p∨q using a truth table: for (p,q)=(T,T): p→q=T, ¬p∨q=F∨T=T ✓. (T,F): p→q=F, ¬p∨q=F∨F=F ✓. (F,T): p→q=T, ¬p∨q=T∨T=T ✓. (F,F): p→q=T, ¬p∨q=T∨F=T ✓. All rows match → the two expressions are logically equivalent.

1.3 Logical Equivalences

Law	Equivalence
De Morgan's	¬(p∧q) ≡ ¬p∨¬q; ¬(p∨q) ≡ ¬p∧¬q
Implication	p→q ≡ ¬p∨q
Contrapositive	p→q ≡ ¬q→¬p
Distributive	p∧(q∨r) ≡ (p∧q)∨(p∧r)

JRF trap — contrapositive vs converse vs inverseFor p→q: the Contrapositive ¬q→¬p is LOGICALLY EQUIVALENT to the original. The Converse q→p and the Inverse ¬p→¬q are NOT equivalent to the original (and not to each other, though converse and inverse ARE equivalent to each other). Mixing up which one is actually equivalent to p→q is one of the most common NET/JRF traps in logic.

1.4 Predicates & Quantifiers

Quantifier	Symbol	Meaning
Universal	∀x P(x)	P(x) is true for ALL x
Existential	∃x P(x)	P(x) is true for AT LEAST ONE x

JRF trap — negating quantifiers¬(∀x P(x)) ≡ ∃x ¬P(x) (NOT "for all x, P(x) is false") ¬(∃x P(x)) ≡ ∀x ¬P(x) The quantifier FLIPS when you push the negation inside — a classic JRF numerical/symbolic trap, especially with nested quantifiers (∀x∃y vs ∃y∀x, which are NOT interchangeable in general).

1.5 Rules of Inference

Rule	Form
Modus Ponens	p, p→q ⊢ q
Modus Tollens	¬q, p→q ⊢ ¬p
Hypothetical Syllogism	p→q, q→r ⊢ p→r
Disjunctive Syllogism	p∨q, ¬p ⊢ q

Trap — a classic invalid argument"p→q, q ⊢ p" is the fallacy of affirming the consequent — NOT a valid rule of inference, even though it superficially resembles Modus Ponens. Similarly "p→q, ¬p ⊢ ¬q" is the fallacy of denying the antecedent. NET frequently tests whether an argument form is valid or one of these two fallacies.

1.6 Normal Forms — CNF & DNF

IdeaDNF (Disjunctive Normal Form) = OR of AND-terms, e.g., (p∧q)∨(¬p∧r). CNF (Conjunctive Normal Form) = AND of OR-terms, e.g., (p∨q)∧(¬p∨r). Every propositional formula can be converted into an equivalent CNF and DNF.

MUST REMEMBER — Chapter 1

• p→q is FALSE only when p=T and q=F; true in every other case.
• Contrapositive (¬q→¬p) IS equivalent to p→q; Converse (q→p) and Inverse (¬p→¬q) are NOT.
• De Morgan's: ¬(p∧q)≡¬p∨¬q and ¬(p∨q)≡¬p∧¬q.
• Negating a quantifier flips it: ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x).
• Modus Ponens (p,p→q⊢q) and Modus Tollens (¬q,p→q⊢¬p) are VALID; affirming the consequent and denying the antecedent are FALLACIES.
• DNF = OR of ANDs; CNF = AND of ORs.

DON'T CONFUSE

• Contrapositive (equivalent) vs Converse/Inverse (not equivalent).
• Modus Tollens (valid) vs denying the antecedent (fallacy, looks similar).
• Tautology (always true) vs Contingency (sometimes true) vs Contradiction (always false).

JRF CHALLENGE ZONE — Chapter 1

1. Which is logically equivalent to p→q? (a) q→p (b) ¬p→¬q (c) ¬q→¬p (d) ¬p→q
Answer: (c) — the contrapositive.

2. ¬(∀x P(x)) is equivalent to: (a) ∀x ¬P(x) (b) ∃x ¬P(x) (c) ∃x P(x) (d) ¬∃x P(x)
Answer: (b)

3. The argument "p→q, q ⊢ p" is: (a) Modus Ponens, valid (b) Modus Tollens, valid (c) Affirming the consequent, invalid (d) Denying the antecedent, invalid
Answer: (c)

Practice Questions — Chapter 1 (8)

1. When is p→q FALSE?
   Ans: Only when p is true and q is false
2. State De Morgan's laws for ¬(p∧q) and ¬(p∨q).
   Ans: ¬(p∧q)≡¬p∨¬q; ¬(p∨q)≡¬p∧¬q
3. Is the converse of p→q logically equivalent to p→q?
   Ans: No — only the contrapositive is equivalent
4. Write the negation of ∃x P(x).
   Ans: ∀x ¬P(x)
5. State Modus Ponens in symbolic form.
   Ans: p, p→q ⊢ q
6. What is the fallacy of "denying the antecedent"?
   Ans: Concluding ¬q from p→q and ¬p — an invalid argument form
7. Differentiate a tautology and a contradiction.
   Ans: Tautology is always true; contradiction is always false, for every truth assignment
8. What is DNF, and give a simple example form.
   Ans: Disjunctive Normal Form — an OR of AND-terms, e.g., (p∧q)∨(¬p∧r)

---

Chapter 2 — Permutation, Combination, Probability

2.1 Fundamental Counting Principle

SimpleIf one task can be done in m ways and a second independent task in n ways, both together can be done in m×n ways.

2.2 Permutations (Order Matters)

nPr = n! / (n−r)!

Worked exampleNumber of ways to arrange 3 books out of 5 on a shelf: 5P3 = 5!/(5−3)! = 5!/2! = 120/2 = 60.

JRF-level numerical — permutations with repetitionNumber of distinct arrangements of the letters in "MISSISSIPPI" (11 letters: M=1, I=4, S=4, P=2): 11! / (4!×4!×2!) = 39916800 / (24×24×2) = 39916800/1152 = 34650. This "repeated-letter arrangement" formula (n! divided by the factorial of each repeat count) is a classic JRF numerical.

2.3 Combinations (Order Doesn't Matter)

nCr = n! / (r!(n−r)!) = nPr / r!

Worked exampleWays to choose a 3-person committee from 6 people: 6C3 = 6!/(3!3!) = 720/(6×6) = 20.

JRF-level numerical — combined constraintFrom 5 men and 4 women, select a committee of 4 with EXACTLY 2 men and 2 women: (5C2)×(4C2) = 10×6 = 60. The multiplication rule combines independent selections — a very common JRF pattern (select subgroup A ways, subgroup B ways, multiply).

TrapnCr counts unordered selections (a committee); nPr counts ordered arrangements (a committee with distinct roles like President/Secretary). Using the wrong formula for the scenario is the most common error.

2.4 Circular Permutations

Circular permutations of n distinct objects = (n−1)! If clockwise and counter-clockwise arrangements are considered the SAME (e.g., a necklace that can be flipped): (n−1)!/2

JRF trapSeating n people around a round table gives (n−1)! arrangements, NOT n! — because rotating everyone by one seat is considered the SAME arrangement. Forgetting to divide by n (to remove rotational duplicates) is a common mistake.

2.5 Probability Basics

P(Event) = (favourable outcomes) / (total outcomes) P(A∪B) = P(A) + P(B) − P(A∩B) [Addition rule] P(A∩B) = P(A) × P(B) [Multiplication rule, ONLY if A,B independent]

Worked exampleA fair die is rolled once. P(even OR >4) = P(even) + P(>4) − P(even AND >4). Even={2,4,6}→3/6; >4={5,6}→2/6; even AND >4={6}→1/6. Result = 3/6+2/6−1/6 = 4/6 = 2/3.

2.6 Conditional Probability & Bayes' Theorem

P(A|B) = P(A∩B) / P(B) [conditional probability] Bayes' Theorem: P(A|B) = [P(B|A) × P(A)] / P(B)

JRF-level numerical — Bayes' theoremA factory has two machines: Machine A makes 60% of products with a 2% defect rate; Machine B makes 40% with a 5% defect rate. Given a random product is DEFECTIVE, find P(it came from Machine A). P(Defective) = 0.6×0.02 + 0.4×0.05 = 0.012+0.020 = 0.032. P(A|Defective) = P(Defective|A)×P(A) / P(Defective) = (0.02×0.6)/0.032 = 0.012/0.032 = 0.375 (37.5%). This "reverse conditional probability given evidence" structure is exactly how Bayes' theorem is tested at JRF level.

MUST REMEMBER — Chapter 2

• nPr = n!/(n−r)! (order matters); nCr = n!/(r!(n−r)!) (order doesn't matter).
• Repeated-item arrangements: n! / (product of factorials of each repeat count).
• Circular permutation of n distinct items = (n−1)!; divide by 2 more if flip-symmetric.
• P(A∪B) = P(A)+P(B)−P(A∩B); P(A∩B)=P(A)×P(B) only if independent.
• Bayes' theorem: P(A|B) = P(B|A)P(A) / P(B).

DON'T CONFUSE

• Permutation (ordered, e.g. President/Secretary) vs Combination (unordered, e.g. committee).
• P(A∩B)=P(A)P(B) — valid ONLY for independent events, not in general.

JRF CHALLENGE ZONE — Chapter 2

1. Number of distinct arrangements of letters in "BALLOON" (7 letters, L=2, O=2)? (a) 5040 (b) 2520 (c) 1260 (d) 630
Answer: (c) — 7!/(2!×2!) = 5040/4 = 1260.

2. 8 people are seated around a circular table. Number of distinct seating arrangements? (a) 8! (b) 7! (c) 8!/2 (d) 7!/2
Answer: (b) — (n−1)! = 7!.

3. A bag has 4 red and 6 blue balls. Two balls drawn without replacement. Find P(both red).
Answer: (4/10)×(3/9) = 12/90 = 2/15 — multiplication rule for dependent events (without replacement).

Practice Questions — Chapter 2 (8)

1. Write the formula for nPr and nCr.
   Ans: nPr = n!/(n−r)!; nCr = n!/(r!(n−r)!)
2. Find 6P2.
   Ans: 6!/4! = 30
3. Find 7C3.
   Ans: 7!/(3!4!) = 35
4. How many distinct arrangements of the letters in "STATISTICS" (10 letters: S=3, T=3, I=2, A=1, C=1)?
   Ans: 10!/(3!×3!×2!) = 3628800/72 = 50400
5. How many ways can 5 people be seated around a circular table?
   Ans: (5−1)! = 24
6. State the addition rule of probability for two events A and B.
   Ans: P(A∪B) = P(A) + P(B) − P(A∩B)
7. When is P(A∩B) = P(A)×P(B) valid?
   Ans: Only when A and B are independent events
8. Write Bayes' theorem formula for P(A|B).
   Ans: P(A|B) = P(B|A)×P(A) / P(B)

---

Chapter 3 — Group Theory

3.1 Algebraic Structures — Semigroup, Monoid, Group

Structure	Required properties (on set S with operation *)
Semigroup	Closure + Associativity
Monoid	Semigroup + Identity element
Group	Monoid + every element has an Inverse
Abelian Group	Group + Commutativity (a*b = b*a)

JRF trap — building up the hierarchyEach structure ADDS exactly one property to the previous: Semigroup(closure+associative) → Monoid(+identity) → Group(+inverse) → Abelian Group(+commutative). A very common JRF question gives a set+operation and asks "what is the highest structure it forms" — check the properties IN THIS ORDER and stop at the first one that fails.

3.2 Group Axioms — Worked Check

Worked exampleIs (Z, +) [integers under addition] a group? Closure: sum of two integers is an integer ✓. Associativity: (a+b)+c=a+(b+c) ✓. Identity: 0 (a+0=a) ✓. Inverse: for each a, −a exists (a+(−a)=0) ✓. All four hold, AND it's commutative → (Z,+) is an Abelian group.

JRF trapIs (Z, ×) [integers under multiplication] a group? Closure ✓, Associativity ✓, Identity=1 ✓, but INVERSE fails — e.g., 2 has no integer x with 2×x=1. So (Z,×) is only a Monoid, NOT a group. This exact "which axiom fails" question is extremely common.

3.3 Order of a Group / Element, Cyclic Groups

IdeaOrder of a group = number of elements in it. Order of an element a = smallest positive integer n such that aⁿ = identity. A group is CYCLIC if some single element (a "generator") can produce every element of the group via repeated operation.

Worked exampleIn (Z₆, +) [integers mod 6], the element 1 generates the whole group: 1,1+1=2,3,4,5,6mod6=0 — all 6 elements reached. So Z₆ is cyclic with generator 1, and order of Z₆ = 6.

3.4 Subgroups & Lagrange's Theorem

IdeaA subgroup is a subset of a group that is itself a group under the same operation. Lagrange's Theorem: the ORDER OF ANY SUBGROUP must DIVIDE the order of the group.

JRF-level numericalA group has order 12. Which of these CANNOT be the order of a subgroup? (a) 2 (b) 3 (c) 5 (d) 6 — Answer: 5, since 5 does not divide 12 (divisors of 12 are 1,2,3,4,6,12). This "must divide the group order" check is a very high-yield Lagrange's theorem application.

3.5 Cosets

IdeaFor a subgroup H of G and element a∈G, the left coset aH = {a*h : h∈H}. All cosets of H have the SAME SIZE as H, and they partition G into disjoint pieces — this is exactly why Lagrange's theorem works (|G| = number of cosets × |H|).

3.6 Homomorphism & Isomorphism

	Homomorphism	Isomorphism
Definition	A structure-preserving map f: f(a*b)=f(a)*f(b)	A homomorphism that is ALSO bijective (one-to-one and onto)
Implies	Similar structure, but sizes/elements can differ	The two groups are essentially "the same" (identical structure)

3.7 Ring & Field (Brief Overview)

IdeaA Ring has TWO operations (usually + and ×): an Abelian group under +, and × is associative and distributes over +. A Field is a ring where the nonzero elements ALSO form an Abelian group under × (every nonzero element has a multiplicative inverse) — e.g., rational numbers Q, real numbers R.

JRF trap(Z, +, ×) [integers with both operations] is a Ring but NOT a Field — because most integers (e.g., 2) have no multiplicative inverse that is also an integer. (Q, +, ×) [rationals] IS a Field.

MUST REMEMBER — Chapter 3

• Semigroup(closure+assoc) → Monoid(+identity) → Group(+inverse) → Abelian(+commutative) — each adds one property.
• (Z,+) is an Abelian group; (Z,×) is only a Monoid (no inverses).
• Lagrange's theorem: order of a subgroup must divide order of the group.
• Cosets all have the same size as the subgroup and partition the group.
• Homomorphism = structure-preserving map; Isomorphism = bijective homomorphism (same structure).
• Ring = abelian group under + with distributive ×; Field = ring where nonzero elements also form an abelian group under ×.

DON'T CONFUSE

• Monoid (has identity, no guaranteed inverse) vs Group (has both identity and inverse).
• Homomorphism (structure-preserving) vs Isomorphism (also bijective — "same" structure).
• Ring (× need not have inverses) vs Field (nonzero elements have × inverses).

JRF CHALLENGE ZONE — Chapter 3

1. Which axiom does (Z, ×) fail to be a group (it remains only a Monoid)? (a) Closure (b) Associativity (c) Identity (d) Inverse
Answer: (d)

2. A group has order 15. Which CANNOT be a subgroup's order? (a) 1 (b) 3 (c) 4 (d) 5
Answer: (c) — divisors of 15 are 1,3,5,15; 4 does not divide 15.

3. Which is TRUE? (a) Every homomorphism is an isomorphism (b) Every isomorphism is a homomorphism (c) Rings always have multiplicative inverses (d) (Z,+,×) is a field
Answer: (b)

Practice Questions — Chapter 3 (7)

1. List the properties needed for a set with an operation to be a Group.
   Ans: Closure, Associativity, Identity element, and Inverse for every element
2. What additional property turns a Group into an Abelian Group?
   Ans: Commutativity (a*b = b*a for all elements)
3. Is (Z, ×) a group? Why or why not?
   Ans: No — most integers lack a multiplicative inverse within the integers (e.g., 2 has none)
4. State Lagrange's theorem.
   Ans: The order of any subgroup of a finite group divides the order of the group
5. What is a cyclic group?
   Ans: A group in which every element can be generated by repeatedly applying the operation to a single generator element
6. Differentiate a homomorphism and an isomorphism.
   Ans: A homomorphism preserves structure; an isomorphism is a homomorphism that is also bijective (a perfect structural match)
7. Differentiate a Ring and a Field.
   Ans: A ring's multiplication need not have inverses; in a field, every nonzero element has a multiplicative inverse

---

Chapter 4 — Set and Relation

4.1 Set Operations

Operation	Meaning
A∪B	Union — elements in A OR B (or both)
A∩B	Intersection — elements in BOTH A and B
A−B	Difference — elements in A but NOT in B
A' (or Aᶜ)	Complement — elements NOT in A (within the universal set)
A×B	Cartesian product — all ordered pairs (a,b), a∈A, b∈B

JRF-level numerical|A|=5, |B|=7, |A∩B|=3. Find |A∪B|. |A∪B| = |A|+|B|−|A∩B| = 5+7−3 = 9. For 3 sets: |A∪B∪C| = |A|+|B|+|C|−|A∩B|−|B∩C|−|A∩C|+|A∩B∩C| (inclusion-exclusion) — a very common JRF numerical, especially with a concrete word problem (survey-style questions).

4.2 Relations — Properties

Property	Definition
Reflexive	(a,a)∈R for every a in the set
Symmetric	If (a,b)∈R then (b,a)∈R
Antisymmetric	If (a,b)∈R and (b,a)∈R, then a=b
Transitive	If (a,b)∈R and (b,c)∈R, then (a,c)∈R

JRF trap — symmetric vs antisymmetricThese are NOT opposites! A relation can be BOTH symmetric and antisymmetric at once (e.g., R={(a,a)} — the identity relation only, trivially satisfies both). It can also be NEITHER. Assuming "not symmetric" automatically means "antisymmetric" is a very common JRF logic error.

4.3 Equivalence Relations & Partial Orders

IdeaAn Equivalence Relation = Reflexive + Symmetric + Transitive (groups elements into "equivalence classes" of mutually related items, e.g., "same remainder mod 5"). A Partial Order = Reflexive + Antisymmetric + Transitive (defines a "≤"-like ranking, but not all pairs need be comparable, e.g., divisibility "a divides b").

Worked exampleIs "≡ (mod 3)" [same remainder when divided by 3] an equivalence relation on integers? Reflexive: a≡a(mod3) ✓. Symmetric: if a≡b then b≡a ✓. Transitive: if a≡b and b≡c then a≡c ✓. All three hold → yes, it's an equivalence relation, partitioning integers into 3 classes: {...,−3,0,3,6,...}, {...,−2,1,4,7,...}, {...,−1,2,5,8,...}.

4.4 Functions — Injective, Surjective, Bijective

Type	Meaning
Injective (one-to-one)	Different inputs always give different outputs (no two inputs share an output)
Surjective (onto)	Every element of the codomain is hit by at least one input
Bijective	Both injective AND surjective — a perfect one-to-one correspondence, invertible

JRF-level numerical — counting functionsNumber of functions from a set of size m to a set of size n = nᵐ (each of the m inputs independently picks one of n outputs). Number of one-to-one (injective) functions from size m to size n (m≤n) = nPm = n!/(n−m)!. These exact counting-function formulas are frequently tested.

4.5 Hasse Diagrams & Lattices (POSET)

IdeaA Hasse diagram is a simplified visual of a partial order — it removes reflexive loops and "implied" (transitive) edges, showing only the direct "covers" relationships, with higher elements drawn above lower ones. A Lattice is a POSET (partially ordered set) where every pair of elements has both a unique Least Upper Bound (join, ∨) and a unique Greatest Lower Bound (meet, ∧).

MUST REMEMBER — Chapter 4

• |A∪B| = |A|+|B|−|A∩B| (inclusion-exclusion, extends to 3+ sets).
• Symmetric and Antisymmetric are NOT opposites — a relation can be both, or neither.
• Equivalence relation = Reflexive+Symmetric+Transitive; Partial order = Reflexive+Antisymmetric+Transitive.
• Injective = no shared outputs; Surjective = every output hit; Bijective = both (invertible).
• Functions from size-m set to size-n set: total = nᵐ; injective (m≤n) = nPm.
• Lattice = POSET where every pair has a unique join (LUB) and meet (GLB).

DON'T CONFUSE

• Symmetric vs Antisymmetric — not opposites, can overlap or both fail.
• Equivalence relation (partitions into classes) vs Partial order (defines a ranking/hierarchy).
• Injective (one-to-one) vs Surjective (onto) — independent properties; bijective needs both.

JRF CHALLENGE ZONE — Chapter 4

1. |A|=10, |B|=8, |A∩B|=4. Find |A∪B|.
Answer: 10+8−4 = 14

2. A relation R = {(1,1),(2,2)} on set {1,2,3}. Is R symmetric, antisymmetric, both, or neither? (a) Symmetric only (b) Antisymmetric only (c) Both (d) Neither
Answer: (c) — trivially satisfies both since there are no pairs with a≠b.

3. Number of one-to-one functions from a 3-element set to a 5-element set? (a) 5³ (b) 3⁵ (c) 5P3 (d) 5C3
Answer: (c) — 5P3 = 60.

Practice Questions — Chapter 4 (7)

1. State the inclusion-exclusion formula for |A∪B|.
   Ans: |A∪B| = |A| + |B| − |A∩B|
2. Define a reflexive relation.
   Ans: A relation where (a,a) belongs to R for every element a in the set
3. Can a relation be both symmetric and antisymmetric? Give an example.
   Ans: Yes — e.g., the identity relation {(a,a) : a in the set}
4. What three properties define an equivalence relation?
   Ans: Reflexive, Symmetric, and Transitive
5. What three properties define a partial order?
   Ans: Reflexive, Antisymmetric, and Transitive
6. Differentiate injective and surjective functions.
   Ans: Injective means no two inputs share an output; surjective means every element of the codomain is hit by some input
7. How many total functions exist from a set of size 4 to a set of size 3?
   Ans: 3⁴ = 81

---

Chapter 5 — Boolean Algebra

5.1 Boolean Postulates & Basic Identities

Law	Identity
Identity	A+0=A; A·1=A
Null	A+1=1; A·0=0
Idempotent	A+A=A; A·A=A
Complement	A+A'=1; A·A'=0
De Morgan's	(A+B)'=A'·B'; (A·B)'=A'+B'

JRF trapA+1=1 (NOT A) and A·0=0 (NOT A) — these "absorbing element" identities are commonly mixed up with the Identity laws (A+0=A, A·1=A). Notice: 0 is the identity for OR(+), while 1 is the identity for AND(·) — opposite of what intuition might suggest.

5.2 Duality Principle

IdeaAny valid Boolean identity remains valid if you swap + ↔ · AND swap 0 ↔ 1 throughout — this is the Duality Principle. E.g., the dual of A+0=A is A·1=A.

5.3 SOP and POS Forms

IdeaSOP (Sum of Products) = OR of AND terms, e.g., AB+A'C. POS (Product of Sums) = AND of OR terms, e.g., (A+B)(A'+C). Every Boolean function can be expressed in either canonical form using minterms (SOP) or maxterms (POS).

5.4 Karnaugh Map (K-Map) Minimization

SimpleA K-map is a grid-based tool for simplifying Boolean expressions by grouping adjacent 1s (in powers of 2: 1, 2, 4, 8...) to eliminate variables that change within the group.

JRF-level numericalFor a 3-variable function F(A,B,C) with minterms Σ(0,1,2,3,5,7): plotting on a K-map, the four cells for m0,m1,m2,m3 (where A=0 for all) form a full group → simplifies to A'. Remaining cells m5, m7 (B=1,C=1 for both) form a pair → simplifies to BC. Final simplified SOP: F = A' + BC. Reading off K-map groupings correctly (identifying which variable stays CONSTANT across a group — that's the variable that survives) is exactly what JRF numericals test.

Common mistakeK-map groups must have a size that is a power of 2 (1,2,4,8,16...) and must be rectangular/wraparound-adjacent — a group of 3 cells is NOT valid. Also, larger groups give SIMPLER (fewer-literal) terms — always prefer the largest valid group.

5.5 Logic Gates

Gate	Output is 1 when...
AND	ALL inputs are 1
OR	AT LEAST ONE input is 1
NAND	NOT all inputs are 1 (complement of AND)
NOR	ALL inputs are 0 (complement of OR)
XOR	Inputs DIFFER (odd number of 1s)
XNOR	Inputs are THE SAME (even number of 1s, incl. zero)

NET pointNAND and NOR are each "universal gates" — either one alone can be used to construct ALL other basic gates (AND, OR, NOT). This universality property is frequently tested.

MUST REMEMBER — Chapter 5

• 0 is the identity for OR (A+0=A); 1 is the identity for AND (A·1=A).
• A+1=1 and A·0=0 (absorbing/null elements) — don't confuse with identity laws.
• Duality: swap +↔· and 0↔1 to get the dual of any valid identity.
• SOP = OR of ANDs (uses minterms); POS = AND of ORs (uses maxterms).
• K-map groups must be powers of 2 in size; the variable that stays CONSTANT across the group survives in the simplified term.
• NAND and NOR are each universal gates (can build AND/OR/NOT alone).

DON'T CONFUSE

• Identity laws (A+0=A, A·1=A) vs Null laws (A+1=1, A·0=0).
• SOP (sum of products, minterms) vs POS (product of sums, maxterms).
• XOR (differ) vs XNOR (same) — easy to swap by mistake.

JRF CHALLENGE ZONE — Chapter 5

1. Which identity is CORRECT? (a) A+1=A (b) A·0=A (c) A+1=1 (d) A·1=0
Answer: (c)

2. Which gate(s) are universal (can build all other basic gates alone)? (a) AND only (b) OR only (c) NAND and NOR (d) XOR only
Answer: (c)

3. A K-map grouping combines 4 cells where variable B stays 0 throughout, while A and C both vary. The simplified term is: (a) B (b) B' (c) AC (d) A'C'
Answer: (b) — only the constant variable (B, staying 0) survives, as B'.

Practice Questions — Chapter 5 (7)

1. What is the identity element for OR, and for AND?
   Ans: 0 is the identity for OR; 1 is the identity for AND
2. State the Null law for OR and for AND.
   Ans: A+1=1 (OR); A·0=0 (AND)
3. What is the Duality Principle in Boolean algebra?
   Ans: Swapping + with · and 0 with 1 throughout a valid identity gives another valid identity
4. Differentiate SOP and POS forms.
   Ans: SOP is an OR of AND-terms (minterms); POS is an AND of OR-terms (maxterms)
5. What sizes are valid for a K-map grouping?
   Ans: Powers of 2 — 1, 2, 4, 8, 16, etc.
6. Which two gates are each individually "universal"?
   Ans: NAND and NOR
7. When does an XOR gate output 1?
   Ans: When the inputs differ (an odd number of 1s among the inputs)

---

Chapter 6 — Linear Programming

6.1 LP Formulation

SimpleLinear Programming finds the BEST value (max or min) of a linear objective function, subject to linear constraints (inequalities/equations) and non-negativity of variables.

Standard components Objective function: e.g., Maximize Z = 3x + 5y Constraints: e.g., x+2y ≤ 10, 3x+y ≤ 15 Non-negativity: x≥0, y≥0

6.2 Graphical Method

Worked exampleMaximize Z=3x+2y subject to x+y≤4, x≤2, x,y≥0. Plotting constraints, the feasible region is a polygon with corner points (0,0), (2,0), (2,2), (0,4). Evaluate Z at each CORNER POINT (this is the key insight — the optimum ALWAYS occurs at a corner/vertex of the feasible region): Z(0,0)=0; Z(2,0)=6; Z(2,2)=6+4=10; Z(0,4)=8. Maximum Z=10 at (2,2).

JRF insightThe graphical method only works for 2 variables (can be extended to 3 with more difficulty) — this is exactly WHY the Simplex method exists, to handle problems with many variables where graphing is impossible.

6.3 Simplex Method (Concept)

IdeaThe Simplex method is an algebraic, iterative procedure that starts at a feasible corner point (vertex) of the feasible region and moves to an ADJACENT corner point that improves the objective function value, repeating until no further improvement is possible (optimal reached).

NET pointSlack variables are added to convert ≤ inequality constraints into equations (for ≤, add a slack variable; for ≥, subtract a surplus variable) — this conversion is the essential first step before applying the Simplex algorithm.

6.4 Special Cases in LP

Case	Meaning
Unbounded solution	The feasible region extends infinitely in the direction that improves Z — no finite optimum exists
Infeasible solution	No point satisfies ALL constraints simultaneously — the feasible region is empty
Multiple optimal solutions	The objective function line is PARALLEL to a constraint boundary — an entire edge (not just one point) gives the same optimal Z

JRF trap"Unbounded FEASIBLE REGION" does NOT automatically mean "unbounded SOLUTION" — the region can be infinite while Z still has a finite maximum/minimum, if the objective function's direction of improvement doesn't align with the region's unbounded direction. Confusing "unbounded region" with "unbounded solution" is a common JRF trap.

6.5 Duality in Linear Programming

IdeaEvery LP problem (the "Primal") has a corresponding "Dual" LP problem. If the Primal is a MAXIMIZATION problem with ≤ constraints, the Dual is a MINIMIZATION problem with ≥ constraints (roughly: rows become columns, objective coefficients and constraint RHS values swap roles).

NET pointAt the optimal solution, the objective values of the Primal and Dual problems are EQUAL (Strong Duality) — a key theoretical result sometimes directly tested.

MUST REMEMBER — Chapter 6

• LP = optimize a linear objective subject to linear constraints + non-negativity.
• The optimal solution ALWAYS occurs at a corner/vertex point of the feasible region (graphical method: evaluate Z at each corner).
• Simplex method: adds slack/surplus variables, moves vertex-to-vertex improving Z, for problems with many variables.
• Unbounded solution = Z can improve infinitely; Infeasible = no point satisfies all constraints; Multiple optima = objective line parallel to a constraint edge.
• An unbounded FEASIBLE REGION does not automatically mean an unbounded SOLUTION.
• At optimality, Primal and Dual objective values are equal (Strong Duality).

DON'T CONFUSE

• Unbounded feasible region (the region itself is infinite) vs Unbounded solution (Z itself has no finite optimum).
• Infeasible (no solution satisfies constraints) vs Unbounded (solution exists but Z can grow forever).

JRF CHALLENGE ZONE — Chapter 6

1. Maximize Z=4x+3y subject to x+y≤5, x≤3, x,y≥0. Corner points are (0,0),(3,0),(3,2),(0,5). Find max Z.
Answer: Z(3,2)=12+6=18 is the maximum (compare: Z(0,0)=0, Z(3,0)=12, Z(0,5)=15).

2. A feasible region is unbounded. Which is TRUE? (a) The solution must be unbounded too (b) The solution may still be finite, depending on the objective function's direction (c) The problem is automatically infeasible (d) Simplex cannot be applied
Answer: (b)

3. In LP, slack variables are added to: (a) ≥ constraints, subtracted (b) ≤ constraints, to convert them into equations (c) The objective function only (d) Remove non-negativity
Answer: (b)

Practice Questions — Chapter 6 (7)

1. What are the three main components of an LP formulation?
   Ans: Objective function, constraints, and non-negativity restrictions
2. Where does the optimal solution of an LP problem always occur, graphically?
   Ans: At a corner (vertex) point of the feasible region
3. Why is the Simplex method needed, given the graphical method exists?
   Ans: The graphical method only works for 2 (or with difficulty, 3) variables; Simplex handles problems with many variables
4. What is a slack variable, and when is it added?
   Ans: A variable added to convert a ≤ inequality constraint into an equation
5. Differentiate an infeasible LP problem and an unbounded LP problem.
   Ans: Infeasible means no point satisfies all constraints; unbounded means the objective function can improve without limit
6. When does an LP problem have multiple optimal solutions?
   Ans: When the objective function line is parallel to a constraint boundary, so an entire edge achieves the same optimal value
7. What does Strong Duality state about the Primal and Dual LP problems?
   Ans: At the optimal solution, the Primal and Dual objective function values are equal

---

One-Shot Revision — Unit 3

Key facts across all chapters

• Logic: p→q false ONLY when p=T,q=F. Contrapositive (¬q→¬p) is equivalent; converse/inverse are not.
• Logic: ¬∀xP(x) ≡ ∃x¬P(x); ¬∃xP(x) ≡ ∀x¬P(x). Modus Ponens/Tollens valid; affirming consequent/denying antecedent are fallacies.
• Counting: nPr=n!/(n−r)! (ordered); nCr=n!/(r!(n−r)!) (unordered). Repeated letters: n!/(product of repeat factorials).
• Circular permutation of n items = (n−1)!. P(A∪B)=P(A)+P(B)−P(A∩B). Bayes: P(A|B)=P(B|A)P(A)/P(B).
• Group theory: Semigroup→Monoid→Group→Abelian (each adds one property). (Z,+) is abelian group; (Z,×) is only a monoid.
• Lagrange's theorem: subgroup order divides group order. Homomorphism=structure-preserving; Isomorphism=+bijective.
• Sets: |A∪B|=|A|+|B|−|A∩B|. Symmetric ≠ opposite of Antisymmetric (can be both/neither).
• Equivalence relation = Reflexive+Symmetric+Transitive; Partial order = Reflexive+Antisymmetric+Transitive.
• Functions: total = nᵐ; injective (m≤n) = nPm. Bijective = injective+surjective.
• Boolean: 0=identity for OR, 1=identity for AND. A+1=1, A·0=0 (null laws). NAND/NOR are universal gates.
• K-map: groups must be powers of 2; the CONSTANT variable across a group survives in the term.
• LP: optimum always at a feasible-region corner point. Unbounded region ≠ unbounded solution necessarily.
• LP: Simplex uses slack/surplus variables; Strong Duality — Primal and Dual optimal values are equal.

Potential future exam areasPotential high-value exam area based on syllabus importance and historical question patterns: combined logic-and-quantifier symbolic questions; Bayes'-theorem word problems with 2–3 combined conditional steps; Lagrange's-theorem "which subgroup order is impossible" questions; symmetric-vs-antisymmetric relation identification from an explicit set of ordered pairs; K-map numericals requiring the largest valid grouping; and LP corner-point evaluation combined with an unbounded-vs-infeasible distinction.

---

Unit 3 — UGC NET/JRF Mini Mock Test

45 questions across all 6 chapters. NTA/UGC NET-style question patterns — mixed NET/JRF difficulty, numerical, statement-based, matching and scenario-based. Answer key with brief explanations follows each question.

Q1. p→q is FALSE exactly when: (a) p=F, q=T (b) p=T, q=T (c) p=T, q=F (d) p=F, q=F
Ans: (c) [Ch1 | NET]

Q2. Which is logically equivalent to p→q? (a) Converse (b) Inverse (c) Contrapositive (d) None
Ans: (c) [Ch1 | NET]

Q3. ¬(∃x P(x)) is equivalent to: (a) ∃x ¬P(x) (b) ∀x ¬P(x) (c) ∀x P(x) (d) ¬∀x P(x)
Ans: (b) [Ch1 | NET]

Q4. "p→q, q ⊢ p" is: (a) Modus Ponens (b) Modus Tollens (c) Affirming the consequent — a fallacy (d) A valid syllogism
Ans: (c) [Ch1 | JRF]

Q5. DNF is best described as: (a) AND of ORs (b) OR of ANDs (c) Only negations (d) A truth table
Ans: (b) [Ch1 | NET]

Q6. Number of distinct arrangements of "LEVEL" (5 letters, L=2, E=2)?
Ans: 5!/(2!×2!) = 120/4 = 30 [Ch2 | NET numerical]

Q7. 6 people seated around a circular table — number of arrangements?
Ans: (6−1)! = 120 [Ch2 | NET numerical]

Q8. From 6 men and 5 women, select a committee of 4 with exactly 2 men and 2 women.
Ans: 6C2×5C2 = 15×10 = 150 [Ch2 | JRF numerical]

Q9. A die is rolled once. P(odd OR >4)?
Ans: Odd={1,3,5}=3/6; >4={5,6}=2/6; both={5}=1/6; P=3/6+2/6−1/6=4/6=2/3 [Ch2 | NET numerical]

Q10. Two events A, B are independent. Which is TRUE? (a) P(A∩B)=P(A)+P(B) (b) P(A∩B)=P(A)×P(B) (c) P(A∪B)=P(A)×P(B) (d) P(A|B)=P(B)
Ans: (b) [Ch2 | NET]

Q11. Which axiom fails for (Z, ×) to be a group? (a) Closure (b) Associativity (c) Identity (d) Inverse
Ans: (d) [Ch3 | NET]

Q12. A group has order 20. Which CANNOT be a subgroup's order? (a) 4 (b) 5 (c) 7 (d) 10
Ans: (c) — divisors of 20 are 1,2,4,5,10,20; 7 doesn't divide 20. [Ch3 | JRF]

Q13. An Abelian group is a Group that additionally satisfies: (a) Closure (b) Associativity (c) Commutativity (d) Identity
Ans: (c) [Ch3 | NET]

Q14. Which is TRUE about homomorphism vs isomorphism? (a) Every homomorphism is bijective (b) Isomorphism = homomorphism + bijective (c) They are identical concepts (d) Isomorphism is weaker than homomorphism
Ans: (b) [Ch3 | NET]

Q15. (Q, +, ×) [rationals] forms: (a) A Ring only (b) A Field (c) A Group only (d) Neither
Ans: (b) [Ch3 | NET]

Q16. |A|=12, |B|=9, |A∩B|=5. Find |A∪B|.
Ans: 12+9−5 = 16 [Ch4 | NET numerical]

Q17. A relation on {1,2,3} contains only (1,1),(2,2),(3,3). It is: (a) Symmetric only (b) Antisymmetric only (c) Both symmetric and antisymmetric (d) Neither
Ans: (c) [Ch4 | JRF]

Q18. An equivalence relation requires: (a) Reflexive, Antisymmetric, Transitive (b) Reflexive, Symmetric, Transitive (c) Symmetric only (d) Antisymmetric, Transitive
Ans: (b) [Ch4 | NET]

Q19. Number of total functions from a 3-element set to a 4-element set?
Ans: 4³ = 64 [Ch4 | NET numerical]

Q20. Number of one-to-one functions from a 2-element set to a 5-element set?
Ans: 5P2 = 20 [Ch4 | JRF numerical]

Q21. A partial order requires: (a) Reflexive, Symmetric, Transitive (b) Reflexive, Antisymmetric, Transitive (c) Only Antisymmetric (d) Symmetric, Transitive
Ans: (b) [Ch4 | NET]

Q22. Which is the identity element for the OR operation in Boolean algebra?
Ans: 0 [Ch5 | NET]

Q23. A+1 = ? (a) A (b) 1 (c) 0 (d) A'
Ans: (b) [Ch5 | NET]

Q24. The dual of A·1=A is: (a) A+0=A (b) A·0=A (c) A+A=A (d) A'=A
Ans: (a) [Ch5 | JRF]

Q25. Which gate(s) are universal? (a) AND, OR (b) NAND, NOR (c) XOR only (d) NOT only
Ans: (b) [Ch5 | NET]

Q26. On a K-map, a group of 4 cells has variable C constant at 1, while A,B vary. The simplified term is: (a) C (b) C' (c) AB (d) A'B'
Ans: (a) [Ch5 | JRF]

Q27. XOR gate output is 1 when: (a) All inputs are 1 (b) All inputs are 0 (c) Inputs differ (d) Inputs are the same
Ans: (c) [Ch5 | NET]

Q28. The graphical LP method's optimal solution always occurs at: (a) The centre of the feasible region (b) A corner/vertex of the feasible region (c) Any random feasible point (d) The origin only
Ans: (b) [Ch6 | NET]

Q29. Maximize Z=2x+3y; corner points (0,0),(4,0),(4,2),(0,6). Find max Z.
Ans: Z(0,6)=18 is max — compare Z(0,0)=0, Z(4,0)=8, Z(4,2)=8+6=14, Z(0,6)=18. [Ch6 | NET numerical]

Q30. A slack variable is added to: (a) A ≥ constraint (b) A ≤ constraint, converting it into an equation (c) The objective function (d) A non-negativity condition
Ans: (b) [Ch6 | NET]

Q31. An LP problem has an unbounded feasible region. Which is TRUE? (a) The solution is definitely unbounded (b) The solution may still be finite depending on the objective's direction (c) The problem is infeasible (d) Simplex cannot start
Ans: (b) [Ch6 | JRF]

Q32. When does an LP problem have multiple optimal solutions? (a) When constraints are inconsistent (b) When the objective line is parallel to a constraint edge (c) When there are no constraints (d) Never, LP always has one solution
Ans: (b) [Ch6 | JRF]

Q33. Strong Duality states that at optimum: (a) Primal > Dual always (b) Primal and Dual objective values are equal (c) Dual has no solution (d) Primal is always infeasible
Ans: (b) [Ch6 | NET]

Q34. Which statement is FALSE about (Z,+)? (a) It has closure (b) It has an identity (0) (c) Every element has an inverse (d) It is not commutative
Ans: (d) — (Z,+) IS commutative (abelian). [Ch3 | JRF]

Q35. Given events A,B with P(A)=0.4, P(B)=0.5, P(A∩B)=0.2. Find P(A∪B).
Ans: 0.4+0.5−0.2 = 0.7 [Ch2 | NET numerical]

Q36. Which statement about Lagrange's theorem is TRUE? (a) Group order divides subgroup order (b) Subgroup order divides group order (c) They must be equal (d) No relationship exists
Ans: (b) [Ch3 | NET]

Q37. A relation R on integers is defined as aRb iff a≤b. Is R a partial order?
Ans: Yes — it is reflexive, antisymmetric, and transitive. [Ch4 | NET]

Q38. Which K-map grouping size is INVALID? (a) 1 (b) 2 (c) 3 (d) 4
Ans: (c) — must be a power of 2. [Ch5 | NET]

Q39. A machine has a 3% defect rate and makes 70% of total output; a second machine has a 6% defect rate and makes 30%. Given a defective item, find P(it's from machine 1) [round to 3 decimals].
Ans: P(D)=0.7×0.03+0.3×0.06=0.021+0.018=0.039; P(M1|D)=0.021/0.039≈0.538 [Ch2 | JRF numerical]

Q40. ¬(p∧q) is equivalent to: (a) ¬p∧¬q (b) ¬p∨¬q (c) p∨q (d) p∧q
Ans: (b) [Ch1 | NET]

Q41. A function f:A→B where |A|=|B| and f is injective. Is f necessarily surjective (hence bijective)?
Ans: Yes — for finite sets of equal size, injective implies surjective. [Ch4 | JRF]

Q42. Which is the correct De Morgan's law in Boolean algebra? (a) (A+B)'=A'+B' (b) (A+B)'=A'·B' (c) (A·B)'=A·B (d) (A+B)'=A·B
Ans: (b) [Ch5 | NET]

Q43. 8C3 equals?
Ans: 8!/(3!5!) = 56 [Ch2 | NET numerical]

Q44. Which structure requires ONLY closure and associativity (no identity/inverse needed)? (a) Group (b) Monoid (c) Semigroup (d) Abelian group
Ans: (c) [Ch3 | NET]

Q45. An LP problem has no point satisfying all constraints simultaneously. This is: (a) Unbounded (b) Infeasible (c) Multiple optima (d) Degenerate
Ans: (b) [Ch6 | NET]

— End of Mock Test — Cross-check your score, revisit the "Don't Confuse" and "JRF Challenge Zone" boxes for any topic you missed, then re-attempt after 48 hours. —

Share: