वेन आरेख बनाएँ और क्षेत्र-दर-क्षेत्र तय करें कि समुच्चय व्यंजक में कौन-सा भाग आता है।
गिनती के प्रश्नों में क्षेत्रों को केंद्र से बाहर की ओर भरें: पहले सभी समुच्चय, फिर जोड़े, फिर अकेले समुच्चय, फिर बाहरी भाग।
जाँच के लिए समावेश–अपवर्जन का उपयोग करें: |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.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
क्या ¬(r ∨ ¬r) पुनरुक्ति, विरोधोक्ति या आपातिक कथन है? अपना उत्तर क्लिक करें।
¬(r ∨ ¬r)
1पुनरुक्ति
2विरोधोक्ति
3आपातिक कथन
2.प्रस्ताविक तर्क और उपपत्तियाँकठिन
सत्यमान सारणी की 16 पंक्तियों में से कितनी (¬(p ∨ s) → ¬(p → r)) → (¬q ∨ (¬s ∨ r)) को सत्य बनाती हैं? इस संख्या को N कहें।
(¬(p ∨ s) → ¬(p → r)) → (¬q ∨ (¬s ∨ r))
N =
3.समुच्चय, संबंध और फलनमध्यम
{1, 2, 3, 4} पर संबंध R को दिशित ग्राफ़ के रूप में खींचा गया है (लूप का अर्थ (x, x) ∈ R है)। चारों गुणों में से ठीक एक सत्य है। उस पर क्लिक करें।
R = {(2, 4), (3, 1), (3, 2)}
1स्वतुल्य
2सममित
3प्रति-सममित
4संक्रामक
4.समुच्चय, संबंध और फलनकठिन
तीर आरेख फलन f: A → B दिखाता है, जहाँ A = {1, 2, 3} और B = {a, b, c, d}। f के अनुरूप विवरण पर क्लिक करें।
f = {(1, d), (2, d), (3, c)}
1एकैकी, आच्छादक नहीं
2आच्छादक, एकैकी नहीं
3एकैकी आच्छादक
4दोनों में से कुछ नहीं
5.ग्राफ़ सिद्धांतमध्यम
पूर्ण ग्राफ़ K5 में कितने भिन्न हैमिल्टन परिपथ H हैं? जो परिपथ केवल प्रारंभिक शीर्ष या दिशा में भिन्न हों, उन्हें एक ही गिना जाता है।
K5
H =
6.ग्राफ़ सिद्धांतकठिन
भारित ग्राफ़ के न्यूनतम स्पैनिंग ट्री का कुल भार W ज्ञात करें।
|V| = 7|E| = 9
W =
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम
46 के मापांक में 11 का प्रतिलोम ज्ञात करें: वह संख्या x जिसके लिए 0 < x < 46 और 11·x ≡ 1 (mod 46)।
a = 11n = 46
11−1 mod 46 =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
{0, 1, …, 33} में 16x ≡ 2 (mod 34) के कितने हल N हैं?
16x ≡ 2 (mod 34)
N =
3विलयन
1.प्रस्ताविक तर्क और उपपत्तियाँ
उत्तर: विरोधोक्ति
तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 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)।
सत्यमान सारणी पंक्ति-दर-पंक्ति
r = 1: ¬r = 0, r ∨ ¬r = 1, ¬(r ∨ ¬r) = 0
r = 0: ¬r = 1, r ∨ ¬r = 1, ¬(r ∨ ¬r) = 0
वर्गीकृत करें
¬(r ∨ ¬r): 0, 0
हर पंक्ति में 0: विरोधोक्ति।
उत्तर
विरोधोक्ति
2.प्रस्ताविक तर्क और उपपत्तियाँ
उत्तर: N = 14
सत्यमान सारणियाँ: n अलग-अलग चरों वाले सूत्र की 2ⁿ पंक्तियाँ होती हैं, सत्यमानों के हर संयोजन के लिए एक (1 = सत्य, 0 = असत्य)। भीतर से बाहर की ओर काम करें और हर उप-सूत्र को अपना स्तंभ दें। ¬a मान उलट देता है; a ∧ b केवल तब 1 होता है जब दोनों 1 हों; a ∨ b केवल तब 0 होता है जब दोनों 0 हों; a → b केवल तब 0 होता है जब a = 1 और b = 0; a ↔ b तब 1 होता है जब दोनों पक्ष बराबर हों।
संबंध: समुच्चय X पर संबंध R क्रमित युग्मों (x, y) का समुच्चय है। R स्वतुल्य होता है जब X के हर x के लिए (x, x) ∈ R हो; सममित जब (x, y) ∈ R के साथ हमेशा (y, x) ∈ R हो; प्रति-सममित जब (x, y) और (y, x) दोनों R में केवल तभी हों जब x = y; और संक्रामक जब R में (x, y) और (y, z) होने पर (x, z) ∈ R अनिवार्य हो। तुल्यता संबंध स्वतुल्य, सममित और संक्रामक होता है और X को असंयुक्त वर्गों में बाँटता है।
स्वतुल्य
विफल है: (1, 1) ∉ R
सममित
विफल है: (2, 4) ∈ R, (4, 2) ∉ R
प्रति-सममित
सत्य है
संक्रामक
विफल है: (3, 2), (2, 4) ∈ R, (3, 4) ∉ R
उत्तर
प्रति-सममित
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) = f(2) = d → एकैकी नहीं
आच्छादक?
a, b कोई तीर नहीं पहुँचता → आच्छादक नहीं
उत्तर
दोनों में से कुछ नहीं
उत्तर
दोनों में से कुछ नहीं
5.ग्राफ़ सिद्धांत
उत्तर: H = 12
यूलर, हैमिल्टन और वृक्ष: संबद्ध ग्राफ़ में यूलर परिपथ (हर कोर एक बार, शुरुआत पर वापसी) तब होता है जब हर शीर्ष की घात सम हो, और परिपथ न होने वाला यूलर पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक विषम शीर्ष से दूसरे तक चलता है। हैमिल्टन परिपथ हर शीर्ष पर एक बार जाता है; Kn में ऐसे (n − 1)!/2 होते हैं। n शीर्षों वाले वृक्ष में n − 1 कोरें होती हैं, और m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद स्पैनिंग ट्री रखता है।
गिनें
H = (5 − 1)!/2 = 24/2 = 12
उत्तर
H = 12
6.ग्राफ़ सिद्धांत
उत्तर: W = 47
सबसे छोटे पथ और स्पैनिंग ट्री: डाइक्स्ट्रा का एल्गोरिथ्म हर चक्र में एक शीर्ष निर्धारित करता है: सबसे छोटी अस्थायी दूरी वाला अनिर्धारित शीर्ष। तब उसकी दूरी अंतिम होती है, और हर पड़ोसी v को d(v) = min(d(v), d(u) + w(u, v)) मिलता है। क्रुस्कल का एल्गोरिथ्म कोरों को हल्की से भारी की ओर लेकर और चक्र बनाने वाली हर कोर छोड़कर न्यूनतम स्पैनिंग ट्री बनाता है; प्रिम का एल्गोरिथ्म प्रारंभिक शीर्ष से एक वृक्ष बढ़ाता है और हमेशा उससे बाहर जाने वाली सबसे हल्की कोर जोड़ता है। n शीर्षों के स्पैनिंग ट्री में n − 1 कोरें होती हैं।
क्रुस्कल का एल्गोरिथ्म
BD (1): लें
GE (2): लें
GB (5): लें
GC (8): लें
DF (12): लें
GD (13): छोड़ें, चक्र बनता है
EF (15): छोड़ें, चक्र बनता है
BC (18): छोड़ें, चक्र बनता है
AB (19): लें
कुल भार
W = 1 + 2 + 5 + 8 + 12 + 19 = 47
उत्तर
W = 47
7.संख्या सिद्धांत और मॉड्यूलर अंकगणित
उत्तर: 11−1 mod 46 = 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)।
विस्तारित यूक्लिडीय एल्गोरिथ्म
हर शेषफल r को r ≡ t·11 (mod 46) के रूप में लिखा जाता है।
r = 46, t = 0
r = 11, q = 4, t = 1
r = 2, q = 5, t = −4
r = 1, q = 2, t = 21
व्युत्क्रम
1 ≡ 21·11 (mod 46)
x = 21
जाँच: 11·21 = 231 = 5·46 + 1
उत्तर
11−1 mod 46 = 21
8.संख्या सिद्धांत और मॉड्यूलर अंकगणित
उत्तर: N = 2
प्रतिलोम और सर्वांगसमताएँ: 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)।