Discrete Structures

a) Show that if (A, ≤) and (B, ≤) are posets. Prove that (A × B) is a poset, where (a, b) ≤ (c, d) if a ≤ c in A and b ≤ d in B.

दिखाइए कि यदि (A, ≤) और (B, ≤) पोसेट हैं। सिद्ध कीजिए कि (A × B) एक पोसेट है, जहाँ (a, b) ≤ (c, d) है। यदि a ≤ c और B में b ≤ d है।

b) Let N = {1, 2, 3,...} and a relation is defined in N × N as follows (x, y)R(u, v) if, and only if xv = yu then show whether R is a equivalence relation or not.

मान लीजिए N = {1, 2, 3,...} और एक संबंध N × N में इस प्रकार परिभाषित क��या गया है (x, y)R(u, v) यदि और केवल यदि xv = yu तो दिखाइए कि R एक तुल्यता संबंध है या नहीं।

a) If R and S are equivalence relation on the set A. Show that the following are equivalence relation (R ∪ S) and (R ∩ S).

यदि R और S समुच्चय A पर तुल्यता संबंध है। दर्शाइए कि निम्नलिखित तुल्यता संबंध (R ∪ S) और (R ∩ S) हैं।

b) Define the pendent vertices of a tree. Prove that every tree T = (V, e) with v vertices and e edges, |V|≥ 2 has at least two pendent vertices.

एक tree के pendent शीर्षों को परिभाषित करें। सिद्ध कीजिए कि प्रत्येक वृक्ष T = T (V, e) में शीर्षों और e किनारों के साथ, |V|≥ 2 में कम से कम दो pendent हुए शीर्ष हैं।

a) Define and explain any four of the following with suitable example.

निम्नलिखित को परिभाषित कर उपयुक्त उदाहरण सहित समझाइए।

i) Bipartite graph

i) द्विदलीय ग्राफ

ii) Hamiltonian paths and circuit

ii) हैमिल्टोनियन पथ और सर्किट

iii) Chromatic number and graph coloring of a graph

iii) एक ग्राफ की रंगीन संख्या और ग्राफ रंग

iv) Adjacency matrix of graph

iv) ग्राफ की निकटता मैट्रिक्स

v) Binary search tree

v) बाइनरी सर्च ट्री

a) Solve the recurrence relation a_r+2–2a_r+1+a_r=2r by the method of generating function with initial condition a₀=2 and a₁=1.

पुनरावृत्ति संबंध हल करें a_r+2–2a_r+1+a_r=2r प्रारंभिक स्थिति a₀=2 और a₁=1 के साथ फंक्शन उत्पन्न करने की विधि द्वारा।

b) What is the recursion and recurrence relation? Solve the following recurrence relation using initial condition as S(0) = S(1) = 1

S(K) – 9S(K-1) + 8S(K-2) = 9K+1

पुनरावर्तन और पुनरावृत्ति संबंध क्या है? S(0) = S(1) = 1 के रूप में प्रारंभिक स्थिति का उपयोग करके निम्नलिखित पुनरावृत्ति संबंध को हल करें।

S(K) – 9S(K-1) + 8S(K-2) = 9K+1

a) Prove that in a distributive lattice, if an element has a complement then this complement is unique.

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

b) Prove that the set G = {1, –1, i, –i} where i=(-1)^1/2 is a finite a abelian group with respect to multiplication of complex number. If G is cyclic group then determine the generator of G.

सिद्ध कीजिए कि समुच्चय G = {1, –1, i, –i} जहाँ i=(-1)^1/2 सम्मिश्र संख्या के गुणन के संबंध में एक परिमित आबेलीयन समूह है। यदि G चक्रीय समूह है तो G का जनक ज्ञात कीजिए।

a) Let G is the group of real number under addition, and let G' be the group of positive real number under multiplication. Let G → G' be defined by f(x) = e^x. Determine whether f is an isomorphic or not.

मान लीजिए G योग के अंतर्गत वास्तविक संख्या का समूह है, और G' गुणन के अंतर्गत धनात्मक वास्तविक संख्या का समूह है। मान लीजिए G → G' को f(x) = e^x द्वारा परिभाषित किया जाता है। निर्धारित करें कि f एक समरूपी है या नहीं।

b) Define and explain the following with suitable example.

निम्नलिखित को परिभाषित कर उपयुक्त उदाहरण सहित समझाइए।

i) Cyclic group

i) चक्रीय समूह

ii) Zero divisor of a ring

ii) वलय का शून्य भाजक

iii) Order of an element of a group

iii) एक समूह के एक तत्व का क्रम

iv) Field

iv) क्षेत्र

v) DFS and BFS

v) DFS और BFS

a) Explain various Rules of Inference for Propositional Logic.

प्रस्तावित तर्क के लिए अनुमान के विभिन्न नियमों की व्याख्या करें।

b) A collection of 10 electric bulbs contains 3 defective ones.

10 बिजली के बल्बों के संग्रह में 3 दोषपूर्ण हैं।

i) In how many ways can a sample of 4 bulbs be selected which contain 2 good bulbs and 2 defective ones?

i) चार ���ल्बों के नमूने को कितने तरीकों से चुना जा सकता है?

ii) In how many ways can a sample of 4 bulbs be selected so that either the sample contains 3 good bulbs and 1 defectives ones or 1 good and 3 defectives ones?

ii) कितने तरीकों से 4 बल्बों का एक नमूना चुना जा सकता है ताकि या तो नमूने में 3 अच्छे और 1 दोषपूर्ण या 1 अच्छे और 3 दोषपूर्ण हों?

iii) In how many ways can a sample of 4 bulbs be selected so that the sample contains at most 3 good bulbs?

iii) कितने तरीकों से 4 बल्बों का एक नमूना चुना जा सकता है ताकि नमूने में अधिकतम 3 अच्छे बल्ब हों?

c) Show that ((P ∨ Q) ∧ (¬Q ∨ ¬R)) ∨ (¬P ∨ ¬Q) ∨ (¬P ∨ R) is a tautology by using equivalences.

दिखाएँ कि ((P ∨ Q) ∧ (¬Q ∨ ¬R)) ∨ (¬P ∨ ¬Q) ∨ (¬P ∨ R) तुल्यता का उपयोग करके एक tautology है।

a) Draw a binary tree which following traversal:

एक बाइनरी ट्री ड्रा करें जो निम्नलिखित ट्रैवर्सल है:

In order: D B H E A I F J C G

Preorder: A B D E H C F I J G

b) A total of 1240 students have taken a course in Spanish, 887 have taken a course in French, and 122 have taken a course in Russian. Further, 111 have taken courses in both Spanish and French, 31 have taken courses in both Spanish and Russian, and 22 have taken courses in both French and Russian. If 2100 students have taken at least one of Spanish, French, and Russian, how many students have taken a course in all three languages?

कुल 1240 छात्रों ने स्पेनिश में एक कोर्स किया है, 887 ने फ्रेंच में एक कोर्स किया है, और 122 ने रूसी में एक कोर्स किया है। इसके अलावा, 111 ने स्पेनिश और फ्रेंच दोनों में पाठ्यक्रम लिया है, 31 ने स्पेनिश और रूसी दोनों में प���ठ्यक्रम लिया है, और 22 ने फ्रेंच और रूसी दोनों में पाठ्यक्रम लिया है। यदि 2100 छात्रों ने स्पेनिश, फ्रेंच और रूसी में से कम से कम एक कोर्स किया है, तो कितने छात्रों ने तीनों भाषाओं में एक कोर्स किया है?