Discrete Structures

(a) Define countable and uncountable sets. Prove that the set of rational numbers is countable.

गणनीय एवं अगणनीय समुच्चय की परिभाषा दीजिए। सिद्ध कीजिए कि परिमेय संख्याओं का समुच्चय गणनीय है।

(b) Using Venn diagram, prove:

वेन आरेख की सहायता से ��िद्ध कीजिए:

A∩(B∪C)=(A∩B)∪(A∩C)

(a) Define relation and partial ordering relation with suitable examples. उपयुक्त उदाहरण सहित समुच्चय संबंध एवं आंशिक क्रम संबंध समझाइए।

(b) Let

A = {1, 2, 3}

R = {(1,1), (2,2), (3,3), (1,2), (2,1)}

Check whether R is an equivalence relation and find equivalence classes.

दिए गए संबंध के लिए जाँ��� कीजिए कि यह समतुल्य संबंध है या नहीं। इसके समतुल्य वर्ग ज्ञात कीजिए।

(a) Define one-one, onto and bijective functions. Prove that inverse of a function exists if and only if the function is bijective.

एक-एक, सर्जक-एक ब्लैक फलन की परिभाषा दीजिए। सिद्ध कीजिए कि किसी फलन का व्युत्क्रम तभी अस्तित्व में होता है जब वह ब्लैक हो।

(b) State and prove Pigeonhole Principle.

कबूतराखाना सिद्धांत को कथन सहित सिद्ध कीजिए।

(a) Construct truth table for the proposition.

(p→q)↔(~p∨q) and show that it is a tautology.

निम्न कथन की सत्य सारणी बनाइए तथा सिद्ध कीजिए कि यह सर्वतः सत्य है! (p→q)↔(~p∨q)

(b) Convert the following statement into predicate logic and write its negation: "Every student studies Discrete Mathematics."

वाक्य को प्रेडिकेट लॉजिक में बदलिए तथा उसका निषेध लिखिए। “प्रत्येक छात्र असतत गणित का अध्ययन करता है।"

(a) Prove by mathematical induction that:

गणितीय आगमन विधि से सिद्ध कीजिए:

1 + 2 + 3 + ..... + n = ⁿ⁽ⁿ⁺¹⁾2

(b) Prove by contradiction that √2 is irrational.

विरोधाभास विधि से सिद्ध कीजिए कि √2 अपरिमेय है।

(a) Define group and Abelian group. Prove that identity element of a group is unique.

समूह एवं एबेलियन समूह की परिभाषा दीजिए। ���िद्ध कीजिए कि समूह का पहचान तत्व अद्वितीय होता है।

(b) Find all subgroups of the group Z₆.

समूह Z₆ के सभी उपसमूह ज्ञात कीजिए।

(a) Define Finite State Machine. Explain FSM as a language recognizer.

सीमित अवस्था मशीन की परिभाषा दीजिए तथा इसे भाषा पहचानकर्ता के रूप में समझाइए।

(b) Design a finite state machine that accepts all binary strings ending with 01.

ऐसी सीमित अवस्था मशीन डिजाइन कीजिए जो 01 पर समाप्त होने वाली सभी बाइनरी स्ट्रिंग स्वीकार करे।

(a) Define Euler path and Euler circuit. State necessary and sufficient conditions for their existence.

आयलर पथ एवं आयलर परिपथ की परिभाषा दीजिए। इनके अस्तित्व की आवश्यक एवं पर्याप्त शर्तें लिखिए।

(b) Explain Dijkstra's Algorithm and find the shortest path from a given source vertex in a weighted graph.

डायक्स्ट्रा एल्गोरिथम समझाइए तथा भारित ग्राफ में दिए गए स्रोत शिखर से लघुत्तम पथ ज्ञात कीजिए।