Discrete Structure

Course: B.Tech Code: 302 Branch: CS,CT,CO,IT,CI Date: June 2025

Save as PDF

Opens your browser print dialog — select "Save as PDF" to download.

Total No of Questions : 8 Total No of Printed Pages : 4 [2]
Roll No. ____________________

CS/CT/CO/IT/CI (CSIT)-302

B.Tech./B.Tech. (Working Professional) III Semester

Examination, June 2025

Grading System (GS)/Working Professional

Discrete Structure

Time : Three Hours Maximum Marks : 70

Note:

i) Attempt any five questions.

किन्हीं पाँच प्रश्नों को हल कीजिए।

ii) All questions carry equal marks.

सभी प्रश्नों के समान अंक हैं।

iii) In case of any doubt or dispute the English version question should be treated as final.

किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।

1.
(a) Consider three sets A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6} and C = {1, 5, 7}. Using Venn diagrams, determine and shade the regions corresponding to (AUB)∩(B∩C) and A∩(BUC). Verify if these expressions are equivalent by listing the elements.7

तीन सेट A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6} और C = {1, 5, 7} दिए गए हैं। वेन आरेखों का उपयोग करके (AUB)∩(B∩C) और A∩(BUC) से संबंधित क्षेत्र को निर्धारित करें और छायांकित करें। तत्वों को सूचीबद्ध करके सत्यापित करें कि क्या ये अभिव्यक्तियाँ समतुल्य हैं।

(b) Define and illustrate an equivalence relation by constructing an equivalence relation on the set S = {1, 2, 3, 4, 5, 6} where two elements are related if they have the same remainder when divided by 3.7

एक तुल्यता संबंध को परिभाषित और चित्रित करें जिसमें सेट S = {1, 2, 3, 4, 5, 6} पर एक तुल्यता संबंध का निर्माण करके एक तुल्यता संबंध को परिभाषित और चित्रित करें जिसमें दो तत्व भी संबंधित हों जब उन्हें 3 से विभाजित करने पर समान शेषफल मिले।

2.
(a) What is pigeonhole principle. Prove it by using mathematical induction and use it to show that in a group of 15 people, at least two share the same birth month.7

कबूतरखाना सिद्धांत (पिजनहोल सिद्धांत) क्या है? इसे गणितीय प्रेरण का उपयोग कर सिद्ध करें। इसका उपयोग करते हुए यह दिखाएँ कि 15 लोगों के समूह में कम से कम दो का जन्म एक ही महीने में हुआ होगा।

(b) Explain a recursively defined function. Solve the recurrence relation f(n) = f(n – 1) + 3 with initial condition f(0) = 2.7

���ुनरावर्ती रूप से परिभाषित फंक्शन की व्याख्या करें। प्रारंभिक शर्त f(0) = 2 के साथ पुनरावृत्ति संबंध f(n) = f(n-1) + 3 को हल करें।

3.
(a) Prove that the set G = {0, 1, 2, 3} under addition modulo 4 is an abelian group. Identify the identity and inverse elements.7

सिद्ध करें कि योग मॉड्यूलो 4 के अंतर्गत सेट G = {0, 1, 2, 3} एक एबेलियन समूह है। पहचान और व्युत्क्रम तत्वों की पहचान करें।

(b) Define a homomorphism between two groups. Verify whether the mapping f : R → R defined by f(x) = 2x is a homomorphism under addition.7

दो समूहों के बीच होमोमॉर्फिज्म (एक समरूपता) को परिभाषित करें। सत्यापित करें कि f(x) = 2x द्वारा परिभाषित मैपिंग f : R → R योग के अंतर्गत होमोमॉर्फिज्म (एक समरूपता) है या नहीं?

[4]
4.
(a) Consider the propositions p, q and r, where :
  • p: "it is raining."
  • q: "i am carrying an umbrella."
  • r: "I stay dry."
Assume the implication (p → q) → r. Construct a truth table for the expression (p → q) → r and determine if it is a tautology or contradiction.

p, q और r पर विचार करें, जहाँ :

  • p: "बारिश हो रही है।"
  • q: "मैं छाता लेकर जा रहा हूँ।"
  • r: "मैं सूखा रहता हूँ।"
यह मानते हुए कि निहितार्थ (p → q) → r नहीं है। (p → q) → r अभिव्यक्ति के लिए एक सत्य तालिका बनाएँ और निर्धारित करें कि यह एक सर्वसम्य (टोटोलॉजी) है या विरोधाभास।

7
(b) What are predicates in propositional logic? Define universal and existential quantifiers with examples.7

प्रस्तावना तर्क में विधेय क्या हैं? उदाहरणों के साथ सार्वभौमिक और अस्तित्वगत परिमाणकों को परिभाषित करें।

5.
(a) Define graph theory and explain the basic terminology of graphs such as vertices, edges, degree and adjacency.7

ग्राफ सिद्धांत को परिभाषित करें और ग्���ाफ की मूल शब्दावली जैसे शीर्ष बिंदु, किनारे, डिग्री और आसन्नता को समझाएँ।

(b) Define and give an example of an isomorphic graph pair. Verify isomorphism between two adjacency matrices.7

समरूपी ग्राफ की परिभाषा दें और एक उदाहरण प्रस्तुत करें। दो आसन्न मैट्रिक्स के बीच समरूपता सत्यापित करें।

6.
(a) For the graph G with vertices V = {A, B, C, D} and edges E = {{A, B}, {B, C}, {C, D}, {D, A}, {A, C}}, determine :
  1. Whether the graph contains a Eulerian path or circuit or not.
  2. All Hamiltonian circuits in the graph G.
7
(b) Describe the properties of a binary relation such as reflexivity, symmetry, transitivity and antisymmetry with examples.7

आदर्श संबंध क्या है? द्विआधारी संबंध की विभिन्न गुणधर्मों जैसे परावर्तनशीलता, समरूपता, सकर्मकता और प्रतिसमरूपता को उदाहरणों के साथ समझाएँ।

7.
(a) What is a Hasse diagram? Draw the Hasse diagram for the set {1, 2, 3, 6, 9, 18} with the divisibility relation.7

हैस आरेख क्या है? विभाज्यता संबंध के साथ सेट {1, 2, 3, 6, 9, 18} के लिए हैस आरेख बनाएँ।

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

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

8.
Write short notes on (any four)14
  1. Finite state machines as language recognizers

    2. i) फाइनाइट स्टेट मशीनें

  2. Binomial theorem

    3. ii) द्विपद प्रमेय

  3. Permutation group

    4. iii) क्रमचय समूह

  4. Partial Ordering Relation

    5. iv) आंशिक क्रमबद्ध संबंध

  5. Countable and uncountable sets

    6. v) गणनीय और अगणनीय सेट

CS/CT/CO/IT/CI (CSIT)-302 PTO Contd...