Discrete Structure (CS-302) - Important Questions

Define the pigeonhole principle and write the contrapositive of the implication "if it is Sunday then it is a holiday".

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

Prove by mathematical induction that 1+2+...+n = n(n+1)/2.

Define relation. Explain equivalence relation and partial ordering relation with suitable examples.

Let Z be the group of integers with operation a * b = a+b-2. Find the identity element of the group <Z, *>.

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

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

Construct the truth table for (p -> q) <-> (~p v q) and show it is a tautology.

Define finite state machine and explain FSM as a language recognizer.

What are predicates in propositional logic? Define universal and existential quantifiers with examples.

Define 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.

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

Draw the Hasse diagram of the set {1,2,3,6,9,18} under the divisibility relation.

In a distributive lattice, if a^b = a^c and a v b = a v c then prove that b = c.

In how many ways can a sample of 4 bulbs be selected from 10 bulbs containing 3 defective ones? In how many ways can the sample contain 2 good and 2 defective bulbs?