Questions
3 questions per paper
Difficulty
Medium
Importance
High yield for HPCL/NTPC/ONGC technical sections
Overview
Discrete Mathematics serves as the foundation for computer science and logical reasoning, focusing on non-continuous mathematical structures. Mastering logic, sets, and algebraic structures is critical for clearing technical exams like HPCL and NTPC as these concepts underpin database query optimization, algorithm analysis, and digital circuit design.
Propositional & First-Order Logic
This subtopic deals with the formalization of arguments and the evaluation of truth values using connectives and quantifiers. PSU exams frequently test your ability to convert natural language statements into formal expressions and evaluate logical equivalence.
- Tautology: Formula that is always true
- Contradiction: Formula that is always false
- De Morgan's Laws: ~(p ∧ q) ≡ ¬p ∨ ¬q
- Universal Quantifier (∀): 'For all'
- Existential Quantifier (∃): 'There exists'
- Implication (p → q): Equivalent to ¬p ∨ q
Sets, Relations & Functions
Sets and Relations provide the framework for understanding database structures and data dependencies. Focus specifically on mapping properties such as injective, surjective, and bijective functions, as well as the classification of relations.
- Reflexive: (a,a) ∈ R for all a ∈ A
- Symmetric: (a,b) ∈ R implies (b,a) ∈ R
- Transitive: (a,b) ∈ R and (b,c) ∈ R implies (a,c) ∈ R
- Equivalence Relation: Must be reflexive, symmetric, and transitive
- Power Set size: 2^n for a set with n elements
- Cartesian Product: A × B = {(a,b) | a ∈ A, b ∈ B}
Partial Orders & Lattices
A Partially Ordered Set (Poset) defines order relations that do not necessarily compare every pair of elements. Lattices are special posets where every pair of elements has a Least Upper Bound (LUB) and a Greatest Lower Bound (GLB).
- Hasse Diagram: Visual representation of a Poset
- GLB: Also known as the meet (∧)
- LUB: Also known as the join (∨)
- Total Order: Every pair of elements is comparable
- Distributive Lattice: Satisfies the distributive law of meet and join
- Complemented Lattice: Every element has a complement
Groups & Algebraic Structures
This section covers sets equipped with binary operations that satisfy axioms like closure, associativity, and identity. Exam questions often ask about the order of groups or checking if a structure forms a group, monoid, or semi-group.
- Closure Property: Operation result remains in the set
- Identity Element: a * e = a
- Inverse Element: a * a^-1 = e
- Abelian Group: Commutative group (a * b = b * a)
- Lagrange's Theorem: Order of subgroup divides order of group
- Monoid: Semi-group with identity element
Formula Sheet
p → q ≡ ¬p ∨ q
p ↔ q ≡ (p → q) ∧ (q → p)
n(A ∪ B) = n(A) + n(B) - n(A ∩ B)
Order of Power Set = 2^|A|
Lagrange's Theorem: |H| divides |G|
Exam Tip
When evaluating logical expressions, always convert complex implications (p → q) into (¬p ∨ q) before applying equivalence laws to simplify the problem rapidly.
Common Mistakes
- Confusing the Transitive property with Symmetric property in relations.
- Misapplying De Morgan's Law by forgetting to negate both the proposition and the operator.
- Ignoring the specific requirements for an abelian group versus a general group structure.
More Revision Notes
Ready to test yourself?
Play topic-wise Discrete Mathematics — Logic & Sets questions in Aspirant Arcade — gamified MCQ practice.
Download Free