वेन आरेख बनाएँ और क्षेत्र-दर-क्षेत्र तय करें कि समुच्चय व्यंजक में कौन-सा भाग आता है।
गिनती के प्रश्नों में क्षेत्रों को केंद्र से बाहर की ओर भरें: पहले सभी समुच्चय, फिर जोड़े, फिर अकेले समुच्चय, फिर बाहरी भाग।
जाँच के लिए समावेश–अपवर्जन का उपयोग करें: |A ∪ B| = |A| + |B| − |A ∩ B|।
किसी संबंध के लिए हर गुण को हर जोड़े पर जाँचें और गुण विफल होने पर एक प्रति-उदाहरण दें।
किसी फलन के लिए B के हर अवयव पर पहुँचने वाले तीरों को गिनें: अधिकतम एक हो तो एकैकी, कम से कम एक हो तो आच्छादक।
ग्राफ़ सिद्धांत
हैंडशेक लेमा
Σ deg(v) = 2|E|
पूर्ण ग्राफ़
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
नियमित ग्राफ़
|E| = n·k/2
वृक्ष और वन
|E| = n − 1, |E| = n − c
वृक्ष के पत्ते
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
यूलर
परिपथ: सभी घात सम; पथ: ठीक 2 घात विषम
Kn में हैमिल्टन परिपथ
(n − 1)!/2
डाइक्स्ट्रा अद्यतन
d(v) = min(d(v), d(u) + w(u, v))
लंबाई L की वॉक
(Mᴸ)ij
विधि
हर शीर्ष की घात लिखें; घातों का योग कोरों की संख्या का दोगुना होता है।
यूलर के प्रश्नों में जाँचें कि ग्राफ़ संबद्ध है और विषम घात वाले शीर्षों को गिनें।
वृक्षों के लिए n − 1 कोरों और हैंडशेक लेमा का उपयोग करें।
डाइक्स्ट्रा के लिए अस्थायी दूरियों की सारणी रखें और हर चक्र में सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें।
न्यूनतम स्पैनिंग ट्री के लिए कोरों को भार के अनुसार क्रमबद्ध करें और चक्र बनाने वाली हर कोर छोड़ दें (क्रुस्कल), या किसी प्रारंभिक शीर्ष से एक वृक्ष बढ़ाएँ (प्रिम)।
संख्या सिद्धांत और मॉड्यूलर अंकगणित
शेषफल सहित विभाजन
a = q·n + r, 0 ≤ r < n
यूक्लिड
gcd(a, b) = gcd(b, a mod b)
लघुत्तम समापवर्त्य
lcm(a, b) = a·b/gcd(a, b)
व्युत्क्रम
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
रैखिक सर्वांगसमता
a·x ≡ b → x ≡ a⁻¹·b (mod n)
यूलर का टोशेंट
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
फर्मा
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
विधि
पहले हर संख्या को n के मापांक में घटाएँ; शेषफल 0 से n − 1 के बीच होते हैं।
gcd के लिए यूक्लिड एल्गोरिथ्म से बार-बार भाग दें; अंतिम अशून्य शेषफल ही gcd है।
प्रतिलोम के लिए विस्तारित एल्गोरिथ्म चलाएँ और a का गुणांक रखें; ऋणात्मक हो तो n जोड़ें।
a·x ≡ b को हल करने के लिए a⁻¹ से गुणा करें; दो सर्वांगसमताओं को x = r₁ + m₁k लिखकर मिलाएँ।
घातों के लिए घातांक को द्विआधारी में लिखें और बार-बार वर्ग करें; RSA में d = e⁻¹ mod φ(n) होता है, जहाँ φ(n) = (p − 1)(q − 1)।
2अभ्यास प्रश्न
1.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
आप b → (a ∧ c) को प्रतिधनात्मक द्वारा सिद्ध करना चाहते हैं। इसके बजाय कौन-सा निहितार्थ सिद्ध करेंगे? उस पर क्लिक करें।
b → (a ∧ c)
1b ∧ ¬(a ∧ c)
2(a ∧ c) → b
3¬(a ∧ c) → ¬b
4¬b → ¬(a ∧ c)
2.प्रस्ताविक तर्क और उपपत्तियाँकठिन
निषेध को पूरी तरह भीतर ले जाने पर कौन-सा कथन ¬∀x ∀y (R(x, y) → R(y, x)) के तुल्य है? उस पर क्लिक करें।
¬∀x ∀y (R(x, y) → R(y, x))
1∃x ∃y (R(x, y) ∧ ¬R(y, x))
2∃x ∃y (R(x, y) → ¬R(y, x))
3∀x ∀y (R(x, y) ∧ ¬R(y, x))
4∃x ∃y (¬R(x, y) ∧ ¬R(y, x))
3.समुच्चय, संबंध और फलनमध्यम
53 लोगों के सर्वेक्षण में पाया गया कि 12 के पास लैपटॉप (L), 24 के पास टैबलेट (T) और 33 के पास स्मार्टवॉच (W) है। 9 के पास L और T, 8 के पास L और W, 17 के पास T और W, और 6 के पास तीनों हैं। कितने तीनों समुच्चयों में से ठीक दो में हैं? संख्या को n कहें।
|U| = 53
n =
4.समुच्चय, संबंध और फलनकठिन
{1, 2, 3, 4, 5} पर फलन f और g अपनी सारणियों से दिए गए हैं। (f ∘ f)(1) ज्ञात करें।
एक संबद्ध ग्राफ़ में 14 शीर्ष और 14 कोरें हैं। स्पैनिंग ट्री बचाने के लिए कितनी कोरें k हटानी होंगी?
|V| = 14|E| = 14
k =
6.ग्राफ़ सिद्धांतकठिन
भारित ग्राफ़ में A से D तक के सबसे छोटे पथ की लंबाई d(D) डाइक्स्ट्रा के एल्गोरिथ्म से ज्ञात करें।
प्रारंभ: Aअंत: D
d(D) =
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम
सबसे छोटा धनात्मक पूर्णांक x ज्ञात करें जिसके लिए x ≡ 1 (mod 5) और x ≡ 3 (mod 9)।
x ≡ 1 (mod 5)x ≡ 3 (mod 9)
x =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
2299 mod 71 ज्ञात करने के लिए बार-बार वर्ग करने की विधि का उपयोग करें।
a = 22k = 99n = 71
2299 mod 71 =
3विलयन
1.प्रस्ताविक तर्क और उपपत्तियाँ
उत्तर: ¬(a ∧ c) → ¬b
तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 1 होती है, विरोधोक्ति हर पंक्ति में 0, और आपातिक कथन इनमें से कुछ नहीं होता। उपयोगी नियम: डी मॉर्गन, ¬(a ∧ b) ≡ ¬a ∨ ¬b और ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (प्रतिधनात्मक); ¬(a → b) ≡ a ∧ ¬b; और वितरण नियम, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)।
निहितार्थ के भाग
a = b, b = a ∧ c
प्रतिधनात्मक
¬b → ¬a = ¬(a ∧ c) → ¬b
उत्तर
¬(a ∧ c) → ¬b
प्रतिधनात्मक मूल कथन के तुल्य है, इसलिए उसे सिद्ध करने से कथन सिद्ध हो जाता है।
2.प्रस्ताविक तर्क और उपपत्तियाँ
उत्तर: ∃x ∃y (R(x, y) ∧ ¬R(y, x))
परिमाणक और तर्क: ¬∀x P(x) ≡ ∃x ¬P(x) और ¬∃x P(x) ≡ ∀x ¬P(x)। निषेध को भीतर ले जाएँ, उसके रास्ते में आने वाले हर परिमाणक को बदलें, और भीतरी सूत्र का निषेध प्रस्ताविक नियमों से करें, जैसे ¬(a → b) ≡ a ∧ ¬b। तर्क वैध होता है जब उन सभी पंक्तियों में निष्कर्ष 1 हो जिनमें सभी आधार-वाक्य 1 हों। सत्य आधार-वाक्यों और असत्य निष्कर्ष वाली एक भी पंक्ति प्रति-उदाहरण है और दिखाती है कि तर्क अवैध है।
बाकी विकल्प या तो किसी परिमाणक को अपरिवर्तित रखते हैं, या परिमाणकों का क्रम बदल देते हैं, या भीतरी सूत्र का निषेध गलत करते हैं।
3.समुच्चय, संबंध और फलन
उत्तर: n = 16
समुच्चय और वेन आरेख: A ∪ B में A या B (या दोनों) के अवयव होते हैं, A ∩ B में दोनों के अवयव, A − B में A के वे अवयव जो B में नहीं हैं, और पूरक A′ में U का वह सब कुछ जो A में नहीं है। वेन आरेख में हर समुच्चय व्यंजक क्षेत्रों का संघ होता है, इसलिए उसे क्षेत्र-दर-क्षेत्र गिनें। समावेश–अपवर्जन: |A ∪ B| = |A| + |B| − |A ∩ B|, और |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|।
केंद्र और जोड़ियाँ
L ∩ T ∩ W: 6
L ∩ T केवल: 9 − 6 = 3
L ∩ W केवल: 8 − 6 = 2
T ∩ W केवल: 17 − 6 = 11
अकेले समुच्चय
L केवल: 12 − 3 − 2 − 6 = 1
T केवल: 24 − 3 − 11 − 6 = 4
W केवल: 33 − 2 − 11 − 6 = 14
उत्तर
3 + 2 + 11 = 16
उत्तर
n = 16
4.समुच्चय, संबंध और फलन
उत्तर: (f ∘ f)(1) = 4
फलन और गिनती: फलन f: A → B, A के हर अवयव को B में ठीक एक प्रतिबिंब देता है। f एकैकी (इंजेक्टिव) होता है जब भिन्न अवयवों के प्रतिबिंब भिन्न हों, आच्छादक (सरजेक्टिव) जब B का हर अवयव किसी का प्रतिबिंब हो, और एकैकी आच्छादक (बाइजेक्टिव) जब दोनों हों। |A| = m और |B| = n के साथ nᵐ फलन होते हैं, n!/(n − m)! एकैकी फलन (m ≤ n), और समावेश–अपवर्जन से Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ आच्छादक फलन। |𝒫(A)| = 2ᵐ और |A × B| = m·n।
भीतरी फलन
f(1) = 2
बाहरी फलन
f(2) = 4
(f ∘ f)(1) = 4
उत्तर
(f ∘ f)(1) = 4
5.ग्राफ़ सिद्धांत
उत्तर: k = 1
यूलर, हैमिल्टन और वृक्ष: संबद्ध ग्राफ़ में यूलर परिपथ (हर कोर एक बार, शुरुआत पर वापसी) तब होता है जब हर शीर्ष की घात सम हो, और परिपथ न होने वाला यूलर पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक विषम शीर्ष से दूसरे तक चलता है। हैमिल्टन परिपथ हर शीर्ष पर एक बार जाता है; Kn में ऐसे (n − 1)!/2 होते हैं। n शीर्षों वाले वृक्ष में n − 1 कोरें होती हैं, और m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद स्पैनिंग ट्री रखता है।
स्पैनिंग ट्री की कोरें
14 − 1 = 13
हटाई जाने वाली कोरें
k = 14 − 13 = 1
उत्तर
k = 1
6.ग्राफ़ सिद्धांत
उत्तर: d(D) = 13
सबसे छोटे पथ और स्पैनिंग ट्री: डाइक्स्ट्रा का एल्गोरिथ्म हर चक्र में एक शीर्ष निर्धारित करता है: सबसे छोटी अस्थायी दूरी वाला अनिर्धारित शीर्ष। तब उसकी दूरी अंतिम होती है, और हर पड़ोसी v को d(v) = min(d(v), d(u) + w(u, v)) मिलता है। क्रुस्कल का एल्गोरिथ्म कोरों को हल्की से भारी की ओर लेकर और चक्र बनाने वाली हर कोर छोड़कर न्यूनतम स्पैनिंग ट्री बनाता है; प्रिम का एल्गोरिथ्म प्रारंभिक शीर्ष से एक वृक्ष बढ़ाता है और हमेशा उससे बाहर जाने वाली सबसे हल्की कोर जोड़ता है। n शीर्षों के स्पैनिंग ट्री में n − 1 कोरें होती हैं।
डाइक्स्ट्रा चक्र-दर-चक्र
हर पंक्ति: निर्धारित शीर्ष, उसकी अंतिम दूरी, और वे पड़ोसी जिनकी दूरी सुधरती है।
A (0): B: 5, C: 12
B (5): D: 13, E: 18
C (12)
D (13): F: 27
E (18): F: 19
F (19)
सबसे छोटा पथ
A → B → D
d(D) = 13
उत्तर
d(D) = 13
7.संख्या सिद्धांत और मॉड्यूलर अंकगणित
उत्तर: x = 21
प्रतिलोम और सर्वांगसमताएँ: a का n के मापांक में प्रतिलोम ठीक तब होता है जब gcd(a, n) = 1। विस्तारित यूक्लिडीय एल्गोरिथ्म 1 = s·n + t·a लिखता है, और तब a⁻¹ ≡ t (mod n)। gcd(a, n) = 1 वाली सर्वांगसमता a·x ≡ b (mod n) का हल x ≡ a⁻¹·b है। सहअभाज्य मापांकों वाली दो सर्वांगसमताओं x ≡ r₁ (mod m₁) और x ≡ r₂ (mod m₂) का m₁·m₂ के मापांक में एक हल होता है (चीनी शेषफल प्रमेय)। यूलर का φ(n) 1 से n तक की उन संख्याओं को गिनता है जो n से सहअभाज्य हैं: φ(n) = n·∏(1 − 1/p)।
पहली सर्वांगसमता
x = 1 + 5k
दूसरी सर्वांगसमता
1 + 5k ≡ 3 (mod 9) → 5k ≡ 2 (mod 9)
k ≡ 2·2 ≡ 4 (mod 9)
परिणाम
x = 1 + 5·4 = 21
x = 21
जाँच: 21 mod 5 = 1, 21 mod 9 = 3
उत्तर
x = 21
8.संख्या सिद्धांत और मॉड्यूलर अंकगणित
उत्तर: 2299 mod 71 = 53
मॉड्यूलर घात और RSA: aᵏ mod n बार-बार वर्ग करके निकालें: k को द्विआधारी में लिखें, वर्ग करें, हर चरण के बाद घटाएँ और जिन घातों का बिट 1 है उन्हें गुणा करें। फर्मा: अभाज्य p के लिए, जो a को विभाजित नहीं करता, aᵖ⁻¹ ≡ 1 (mod p), इसलिए घातांक को p − 1 के मापांक में घटाया जा सकता है। RSA: अभाज्य p और q चुनें, n = p·q और φ(n) = (p − 1)(q − 1); सार्वजनिक घातांक e, φ(n) से सहअभाज्य है, और निजी घातांक d = e⁻¹ mod φ(n) है। c = mᵉ mod n से एन्क्रिप्ट करें और m = cᵈ mod n से डिक्रिप्ट करें।