MA3354 Discrete Mathematics Previous Year Question Papers - Anna University

UNIT I: LOGIC AND PROOFS

Part A (2 Marks)

• State De-Morgan's Law for propositional logic.
• Find the contrapositive of a conditional statement.
• Define tautology and contradiction.
• Negation of quantified statements (Universal and Existential).

Part B (13/15 Marks)

• Show logical equivalence without using a truth table.
• Derive conclusions using rules of inference.
• Obtain DNF and CNF for a given logical expression.
• Translate English statements into logical expressions using predicates and quantifiers.

UNIT II: COMBINATORICS

Part A (2 Marks)

• State the Pigeonhole Principle and Generalized form.
• Find permutations of words with repeating letters.
• Define generating functions.
• State the Principle of Inclusion and Exclusion.

Part B (13/15 Marks)

• Solve recurrence relations using generating functions.
• Prove results using Mathematical Induction / Strong Induction.
• Solve counting problems using inclusion-exclusion.
• Solve permutation and combination problems with constraints.

UNIT III: GRAPHS

Part A (2 Marks)

• Define complete graph and bipartite graph.
• State Handshaking Lemma.
• Define strongly connected graph.
• Define graph isomorphism.

Part B (13/15 Marks)

• Test graph isomorphism and form adjacency matrices.
• Determine Euler and Hamiltonian paths/circuits.
• Prove number of odd degree vertices is even.
• Explain graph connectivity and models.

UNIT IV: ALGEBRAIC STRUCTURES

Part A (2 Marks)

• Define Group, Subgroup, Semigroup.
• State Lagrange's Theorem.
• Define homomorphism and isomorphism.
• Define commutative ring.

Part B (13/15 Marks)

• State and prove Lagrange's Theorem.
• Prove properties of homomorphisms.
• Verify whether a set forms a group/abelian group.
• Find left and right cosets of a subgroup.

UNIT V: LATTICES AND BOOLEAN ALGEBRA

Part A (2 Marks)

• Define Poset and Lattice.
• Explain maximal and minimal elements.
• State absorption law and isotonicity.
• Define distributive and complemented lattice.

Part B (13/15 Marks)

• Draw Hasse Diagram for a given Poset.
• Prove every chain is a distributive lattice.
• Prove uniqueness of complement in distributive lattice.
• Simplify Boolean expressions using algebraic laws.

Most Repeated / High-Weight Questions

DNF and CNF conversion, graph isomorphism and Euler/Hamiltonian paths, Lagrange's theorem with proof, Boolean algebra simplification, generating functions for recurrence relations.