Discrete Structures 2074

Attempt all questions:(2 x10 = 20)

Group A

1. Define the term converse, contropositive and inverse.

2. Is the following argument valid? If Socrates is human, then Socrates is mortal Socrates is human.

 ∴ Socrates is mortal.

3. State the rule for the strong form of mathematical induction with prepositions.

4. State and prove " the extended pigeonhole principle".

5. Define the terms a language over a regular grammer and regular expression. 

6. Define linear homogeneous recurrence relation.

7. Explain the state transition function of the finite state machine with a suitable table.

8. Distinguish between multigraph and pseudograph with suitable examples. 

9. Define regular expression over a non empty set A.

10. What is regular graph ?

 Group B (5 x 4 = 20)

11. Express the statement " Everyone has exactly one best friend " as a logical expression involving predicates, quantifiers with a domain consisiting of all people and logical connectives.

12. Let A = {p, q, r} . Give the regular set corresponding to the regular expression give:

(a) (pvq)rq*   (b) p(q q) r.

13. Explain the finite-state with output with suitable examples.

OR

Explain the deterministic finite state automata. When are two finite state automata equivalent?Give an example.

14. When does the two simple graphs G₁ = m(V₁, E₁) and G₂(V₂, E₂) are isomorphic. Show that the graph G = (V, E) and H = (W, F) displayed in the following figure are isomorphic.

15. Define rooted tree. Show that a full m-ary tree with i internal vertices contains n = mi + 1 vertices.

Group C (8 x 5 = 40)

16. Construct truth tables to determine whether the given statement is a tautology a contingency or an absurdity.

a) p ⇒ (q ⇒p)

b) q ⇒ (q ⇒p)

c) p ∧ ~ p

OR

Explain the method of proving theorems by direct indirect, controdiction and by cases.

17. Define linear homogenous recurssion relation of degree k with constant coefficient with suitable examples. What is the solution of recurrence relation a_n = 6 a_n-1 - 9 a_n-2 with a₀ = 1 and a₁ = 6?

18. Find the maximum flow in the network shown in the figure.

19. What do you mean by spanning tree? Find a spanning tree of the simple graph G shown in figure.

A graph is connected if and only if it has a spanning tree.

OR

Prove that an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

20. Explain the concept of network flows and max-flow min-cut theorem with suitable examples.