Discrete Structure (IT-302) - Important Questions

Define the pigeonhole principle.

Prove by mathematical induction that $5^{2n}-1$ is divisible by 24 for any positive integer $n$.

Prove that congruence modulo $m$ (in particular divisibility of $x-y$ by $3$) on integers is an equivalence relation.

Prove that the relation $(a,b) R (c,d)$ iff $a+d = b+c$ is an equivalence relation.

State and prove the pigeonhole principle by mathematical induction with an illustrative example, e.g. two of 15 people share a birth month.

Using Venn diagrams for given finite sets, determine and shade specified set operations and verify equivalence by listing elements.

Define an equivalence relation and illustrate it by the same-remainder-mod-3 relation on $S=\{1,2,3,4,5,6\}$.

What is a mapping? Explain types of mappings.

Explain a recursively defined function. Solve the recurrence relation $f(n) = f(n - 1) + 3$ with initial condition $f(0) = 2$.

Define a relation with example and explain the various types of representation of a relation.

Discuss in brief any two of the following:

Define various types of functions (mappings) and find the number of symmetric and reflexive relations on a set with $n$ elements.

Prove that the set $\{0,1,\dots,n-1\}$ under addition modulo $n$ is an abelian group and identify identity and inverses.

What is a ring? Define elementary properties of a ring with example.

Let $Z$ be the group of integers with binary operation $*$ defined by $a * b = a + b - 2$, for all $a, b \in Z$. Find the identity element of the group $\langle Z, * \rangle$.

Show that every cyclic group is Abelian and prove that a lattice with 5 elements is not a Boolean algebra.

Prove or disprove that intersection of two normal subgroups is normal, and define subgroup, normal subgroup and quotient group with an example for each.

Prove that $F = \{a + b\sqrt{2} : a, b \text{ rational}\}$ is a field.

Prove or disprove that the intersection of two normal subgroups of a group $G$ is again a normal subgroup of $G$.

Define a group homomorphism and verify whether $f(x)=2x$ on $\mathbb{R}$ under addition is a homomorphism.

Show that $f(a,b)=a/b$ from $(N\times N,*)$ to $(Q,\times)$ is a homomorphism and find the congruence relation $x\sim y$ iff $f(x)=f(y)$.

Define a group and explain the properties of groups.

Define symmetric group, normal subgroup and homomorphism.

Prove that the set $\{0,1,2,3,4,5,6\}$ is a finite abelian group of order 7 under multiplication modulo 7.

Construct truth table(s) for the given propositional formula(s) in $p,q,r$ and determine whether they are tautologies, contradictions, or neither.

Explain the various Rules of Inference for Propositional Logic.

Prove the validity of the argument: if the races are fixed then tourist trade will decline, if tourist trade declines police will be happy, police are never happy, therefore races are not fixed.

Define predicates and explain universal and existential quantifiers with examples.

Write short notes on (any four) i) Finite state machines as language recognizers ii) Binomial theorem iii) Permutation group iv) Partial Ordering Relation v) Countable and uncountable sets

Prove that $p \land q \implies q \lor p$ is a tautology and that $(p \lor q) \land (\sim p) \land (\sim q)$ is a contradiction.

Show that $((p \lor q) \land \neg p) \to q$ is a tautology.

Express the statement "No one has more than three grandmothers" using universal and existential quantifiers with $G(x, y)$ meaning $x$ is the grandmother of $y$.

Discuss the 6 tuple notation of finite state machine $M$ with an example.

Write the negation of the following.

Show that the proposition $\neg(p \wedge q)$ and $\neg p \vee q$ are logically equivalent.

Obtain the conjunctive normal form of i) $p \land (p \Rightarrow q)$; ii) $\sim p \Rightarrow [r \land (p \Rightarrow q)]$.

Define a planar graph and prove Euler's formula $v - e + r = 2$ for any connected planar graph.

Explain complete digraph and Euler graph with suitable examples.

Explain Euler graph, isomorphic graphs, minimal spanning tree, and height of a tree.

Prove that no graph exists with degree sequence 1, 3, 4, 2, 3 on 5 vertices.

Define and explain graph concepts such as bipartite graph, Hamiltonian path and circuit, chromatic number and graph coloring, adjacency matrix, and binary search tree with suitable examples.

Define graph theory and explain basic terminology such as vertices, edges, degree and adjacency.

Define an isomorphic graph pair with example and verify isomorphism between two adjacency matrices.

For a given graph, determine whether it contains a Eulerian path or circuit and find all Hamiltonian circuits.

Determine whether two given graphs $G_1$ and $G_2$ (or $G$ and $H$, $F_1$ and $F_2$) are isomorphic.

State Euler's formula for a planar graph and give an example with 5 vertices and 5 regions verifying the formula.

Find a Hamiltonian circuit of minimal weight in a given complete weighted graph.

Discuss the various applications of graph colouring.

Solve the second-order recurrence $G(K)-7G(K-1)+10G(K-2)=8K+6$ using generating function.

Draw the Hasse diagram for a divisibility poset (e.g., a given finite set under divides, positive divisors of 36).

Define a lattice and prove monotonicity: if $a \le b$ and $c \le d$ then $a \vee c \le b \vee d$ and $a \wedge c \le b \wedge d$.

Using inclusion-exclusion with 2, 3, 5 and 7, find the count of integers divisible by at least one of them versus divisible by none of them.

Obtain the generating function for the constant finite sequence $4,4,\dots,4$.

In how many ways can a sample of 4 bulbs be selected from 10 bulbs with 3 defective, including cases with specified numbers of good and defective bulbs?

Prove the cancellation law in a distributive lattice: if $a \wedge b = a \wedge c$ and $a \vee b = a \vee c$ then $b=c$.

Using inclusion-exclusion, find the count of integers from 1 to $N$ not divisible by any of three given primes.

How many permutations can be formed from the letters of the word MATHEMATICS such that all vowels are together?

Solve the following recurrence relation : $$a_r- 7a_{r-1}+10a_{r-2}=3^r \text{ Given that } a_0=0,a_1=1.$$

Define a lattice and prove that every finite lattice has a unique least upper bound and greatest lower bound.

Draw the Hasse diagram of $(P(A), \subseteq)$ for finite $A$.

Discuss in brief any two of the following:

i) Partial ordering relation ii) Cosets iii) Disjunctive normal form iv) Pigeonhole principle