How to use this guide
Discrete mathematics studies objects that can be separated and counted, along with the precise rules connecting them. It supports reasoning used in computer science: conditions, data groups, mappings, networks and systems of equations.
This guide follows the supplied Mahatma Gandhi University syllabus for MG1DSCBCA103. It preserves the module order and stated scope. The ESE carries 70 marks and CCA carries 30 marks. Practice questions here are syllabus-based, not claimed to be actual or guaranteed MGU questions.
Course outcomes in plain language
- Understand and solve problems involving sets.
- Understand propositional logic, apply operators, truth tables and inference rules.
- Analyse relations, functions and equivalence relations.
- Understand matrices and operations; find inverses and solve non-homogeneous linear systems using matrix methods and Cramer’s rule.
Course map, priorities and exam pattern
→ SETS → SET OPERATIONS → FUNCTIONS
→ RELATIONS → REPRESENTATIONS → EQUIVALENCE RELATIONS
→ MATRICES → OPERATIONS / DETERMINANTS / INVERSE
→ SOLVE A SYSTEM OF LINEAR EQUATIONS
Logic teaches how statements combine and how conclusions follow. Sets collect objects; functions map inputs to outputs; relations describe connections. Matrices provide a compact way to calculate and solve systems.
MUST MASTER: truth tables and equivalences; set operations; relation properties and equivalence classes; matrix operations, determinants and inverses; solving systems. These match explicit course outcomes and calculation/application requirements.
IMPORTANT: inference rules, function properties, relation representations, symmetric and skew-symmetric matrices.
QUICK-SCORE: definitions, notation, operator meaning, property names and short distinctions.
Priorities are based on the syllabus outcomes and ESE pattern, not invented topic marks.
Official ESE pattern from the supplied syllabus
| Part | Available questions | Answer | Marks |
|---|---|---|---|
| A · 2 marks | 8 | Any 5 | 10 |
| B · 6 marks | 8 | Any 5 | 30 |
| C · 10 marks | 6 | Any 3 | 30 |
| Total | 22 | 13 answered | 70 |
The document also gives module-wise question counts: Module I (2, 2, 2), Module II (2, 2, 1), Module III (2, 2, 1), Module IV (2, 2, 2), listed for Parts A, B and C respectively. Maximum time is 2 hours.
Propositional logic, equivalences and inference
You will learn: propositions, logical connectives, propositional equivalences and rules of inference.
Why it matters: computers and mathematical arguments depend on precise statements and reliable ways of combining or deriving them.
1.1 Propositional logic
A proposition is a declarative statement that is either true or false. Let p and q be propositions. The main connectives are:
| Symbol | Name | Simple meaning |
|---|---|---|
| ¬p | Negation | Not p |
| p ∧ q | Conjunction | p and q; true only when both are true |
| p ∨ q | Disjunction | p or q (inclusive); true when at least one is true |
| p → q | Conditional | If p, then q; false only when p is true and q false |
| p ↔ q | Biconditional | p if and only if q; true when they have the same truth value |
| p | q | p→q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
A conditional is considered true when its premise p is false because it makes no false promise about the case “if p.” This truth-table rule is important even if it feels unfamiliar at first.
1.2 Propositional equivalences
Two propositions are logically equivalent if they have the same truth value for every assignment of truth values. Write p≡q. Truth tables can verify equivalence.
De Morgan: ¬(p∧q) ≡ (¬p∨¬q); ¬(p∨q) ≡ (¬p∧¬q)
Implication: p→q ≡ ¬p∨q
Contrapositive: p→q ≡ ¬q→¬p
Other useful laws include commutative, associative, distributive, identity and domination laws. Use the law names and forms taught in class; transform one expression at a time and keep brackets clear.
1.3 Rules of inference
A rule of inference is a valid pattern for deriving a conclusion from premises. An argument is valid if whenever its premises are true, its conclusion must be true.
| Rule | Pattern | Plain-language cue |
|---|---|---|
| Modus ponens | p, p→q ∴ q | p holds; p guarantees q; therefore q |
| Modus tollens | ¬q, p→q ∴ ¬p | q did not happen; so the sufficient condition p did not hold |
| Hypothetical syllogism | p→q, q→r ∴ p→r | Chain implications |
| Disjunctive syllogism | p∨q, ¬p ∴ q | One of p or q; rule out p |
Module 1 recap
Key terms: proposition, connective, truth table, tautology, contradiction, equivalence, premise, conclusion, valid argument, inference rule.
Expected / Exam-Focused Questions: construct a truth table; identify a proposition’s truth value; prove a propositional equivalence; apply an inference rule; distinguish a valid argument from an invalid converse.
Self-test: (1) When is p→q false? (2) Write De Morgan’s law for ¬(p∨q). (3) Is p→q equivalent to its converse q→p? (4) Name the rule in p, p→q ∴ q.
Sets, set operations and functions
You will learn: sets and their operations, plus functions as mappings between sets.
Why it matters: sets organise collections of data; functions describe how an input is assigned an output, a central idea in computing.
2.1 Sets
A set is a well-defined collection of distinct objects. The objects are its elements. If a is an element of A, write a∈A; if not, a∉A. Example: V={a,e,i,o,u} is the set of English vowels.
Set-builder notation describes a rule: {x∈ℤ : x is even and 0<x<8}={2,4,6}. The empty set ∅ has no elements. A is a subset of B (A⊆B) if every element of A is also in B. The power set P(A) is the set of all subsets of A.
2.2 Set operations
| Operation | Definition | Example for A={1,2,3}, B={3,4} |
|---|---|---|
| Union A∪B | In A or B or both | {1,2,3,4} |
| Intersection A∩B | In both A and B | {3} |
| Difference A\B | In A but not B | {1,2} |
| Complement Aᶜ | In universal set U but not A | Depends on U |
| Cartesian product A×B | Ordered pairs (a,b), a∈A,b∈B | {(1,3),(1,4),…} |
Subtract the intersection once because adding |A| and |B| counted shared elements twice.
2.3 Functions
A function f:A→B assigns each element of domain A exactly one element of codomain B. The assigned value is f(x). The range is the set of outputs actually attained; it is a subset of the codomain.
| Type | Meaning |
|---|---|
| Injective (one-to-one) | Different inputs have different outputs: f(a)=f(b) implies a=b |
| Surjective (onto) | Every element of the codomain is reached by some input |
| Bijective | Both injective and surjective; has an inverse function |
Module 2 recap
Key terms: element, subset, empty set, universal set, power set, union, intersection, complement, domain, codomain, range, injective, surjective, bijective.
Expected / Exam-Focused Questions: simplify set expressions; calculate union/intersection/complement; solve a counting problem using inclusion-exclusion; determine whether a mapping is injective, onto or bijective.
Self-test: (1) If A⊆B, what can be said about elements of A? (2) Compute {1,2}∩{2,3}. (3) Why subtract the intersection in the union formula? (4) Is x↦x² from ℤ to ℤ injective? onto?
Relations, representations and equivalence
You will learn: relation properties, ways to represent relations, and equivalence relations.
Why it matters: relations model connections such as “has the same remainder,” “is connected to,” or “is at least as large as.”
3.1 Relations and their properties
A relation R from A to B is a subset of A×B. If (a,b)∈R, write aRb. A relation on A is a subset of A×A.
| Property | Test | Example idea |
|---|---|---|
| Reflexive | aRa for every a | “is equal to” |
| Symmetric | aRb implies bRa | “has the same age as” |
| Antisymmetric | aRb and bRa imply a=b | “≤” |
| Transitive | aRb and bRc imply aRc | “≤” |
Symmetric and antisymmetric are different ideas: symmetric requires the reverse pair; antisymmetric allows both directions only when the two elements are equal.
3.2 Representing relations
For finite sets, represent a relation as a set of ordered pairs, a zero-one matrix, or a directed graph (digraph). In a digraph, elements are vertices and a directed edge a→b represents aRb; a loop at a represents aRa.
3.3 Equivalence relations
An equivalence relation is reflexive, symmetric and transitive. It groups elements into equivalence classes: elements related to a are treated as equivalent under the chosen rule.
Equivalence classes form non-overlapping groups that together cover the set. To verify a proposed equivalence relation, check all three properties separately.
Module 3 recap
Key terms: ordered pair, Cartesian product, relation, reflexive, symmetric, antisymmetric, transitive, matrix representation, digraph, equivalence class.
Expected / Exam-Focused Questions: test properties of a relation; represent a finite relation by a matrix or digraph; show whether a relation is an equivalence relation; find equivalence classes.
Self-test: (1) Is ≤ symmetric on integers? (2) Is equality antisymmetric? (3) Which properties define equivalence? (4) For same parity, name the equivalence classes.
Matrix types, operations and linear systems
You will learn: matrix definitions and types, symmetric/skew-symmetric matrices, operations, determinants and inverse, and solving non-homogeneous systems by matrix method and Cramer’s rule.
Why it matters: a matrix stores coefficients compactly and provides systematic methods to solve several linear equations together.
4.1 Definitions and types of matrices
A matrix is a rectangular array of numbers. Its order is rows × columns. A square matrix has the same number of rows and columns; a diagonal matrix has zero entries off the main diagonal; an identity matrix I has 1s on the diagonal and 0s elsewhere; a zero matrix has all entries 0.
For a square matrix A, transpose Aᵀ swaps rows and columns. A is symmetric if Aᵀ=A and skew-symmetric if Aᵀ=−A. In a real skew-symmetric matrix diagonal entries must be zero, since aᵢᵢ=−aᵢᵢ.
4.2 Matrix operations, determinant and inverse
Addition/subtraction require matrices of the same order and operate entry by entry. Scalar multiplication multiplies every entry. Matrix multiplication AB is defined when columns of A equal rows of B; it is generally not commutative (AB may differ from BA).
A square matrix is invertible when its determinant is non-zero. Its inverse satisfies AA⁻¹=A⁻¹A=I.
4.3 Solve a non-homogeneous system: matrix method and Cramer’s rule
A non-homogeneous linear system has form AX=B with at least one non-zero constant in B. If A is invertible, X=A⁻¹B gives the solution.
Cramer’s rule solves a square system when D=det(A)≠0. Replace column i of A with the constants column B to obtain Dᵢ; then xᵢ=Dᵢ/D.
Module 4 recap
Key terms: order, square matrix, transpose, identity, determinant, inverse, singular, non-singular, coefficient matrix, non-homogeneous system.
Expected / Exam-Focused Questions: identify matrix types; test symmetric/skew-symmetric; compute products/determinants/inverse; solve a system by inverse matrix and Cramer’s rule.
Self-test: (1) What must be true for AB to exist? (2) Is matrix multiplication commutative? (3) When does a 2×2 inverse exist? (4) What is the diagonal of a real skew-symmetric matrix? (5) Check x=2,y=1 in the example system.
Formula and rule sheet
Logic and sets
p→q ≡ ¬p∨q · ¬(p∧q)≡¬p∨¬q · ¬(p∨q)≡¬p∧¬q
|A∪B|=|A|+|B|−|A∩B|
Inference patterns: 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.
Matrices
det([[a,b],[c,d]])=ad−bc; A⁻¹=(1/det A)[[d,−b],[−c,a]]
AX=B ⇒ X=A⁻¹B (when A⁻¹ exists); Cramer: xᵢ=Dᵢ/D, D≠0
Use the main guide sections for symbol meanings, conditions and complete worked steps.