वेन आरेख बनाएँ और क्षेत्र-दर-क्षेत्र तय करें कि समुच्चय व्यंजक में कौन-सा भाग आता है।
गिनती के प्रश्नों में क्षेत्रों को केंद्र से बाहर की ओर भरें: पहले सभी समुच्चय, फिर जोड़े, फिर अकेले समुच्चय, फिर बाहरी भाग।
जाँच के लिए समावेश–अपवर्जन का उपयोग करें: |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.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
क्या ¬((p ∧ q) → p) पुनरुक्ति, विरोधोक्ति या आपातिक कथन है? अपना उत्तर क्लिक करें।
¬((p ∧ q) → p)
1पुनरुक्ति
2विरोधोक्ति
3आपातिक कथन
2.प्रस्ताविक तर्क और उपपत्तियाँकठिन
निषेध को पूरी तरह भीतर ले जाने पर कौन-सा कथन ¬∀x (A(x) → B(x)) के तुल्य है? उस पर क्लिक करें।
¬∀x (A(x) → B(x))
1∃x (¬A(x) ∧ B(x))
2∀x (A(x) → ¬B(x))
3∃x (A(x) → ¬B(x))
4∃x (A(x) ∧ ¬B(x))
3.समुच्चय, संबंध और फलनमध्यम
61 विद्यार्थियों के समूह में 30 फ्रेंच (F) बोलते हैं, 27 जर्मन (G) बोलते हैं और 29 स्पैनिश (S) बोलते हैं। 13 फ्रेंच और जर्मन, 16 फ्रेंच और स्पैनिश, 5 जर्मन और स्पैनिश, और 2 तीनों बोलते हैं। कितने तीनों समुच्चयों में से किसी में नहीं हैं?
|U| = 61
|(F ∪ G ∪ S)′| =
4.समुच्चय, संबंध और फलनकठिन
4 अवयवों वाले समुच्चय पर कितने प्रति-सममित संबंध हैं? संख्या को N कहें।
|X| = 4
N =
5.ग्राफ़ सिद्धांतमध्यम
एक वृक्ष में घात 3 वाले 2 शीर्ष, घात 4 वाले 4 शीर्ष, घात 5 वाले 3 शीर्ष, घात 2 वाले 4 शीर्ष है, और उसके बाकी सभी शीर्ष पत्ते (घात 1) हैं। उसमें कितने पत्ते L हैं?
2 × deg 34 × deg 43 × deg 54 × deg 2
L =
6.ग्राफ़ सिद्धांतकठिन
लंबाई 2 की कितनी बंद वॉक B से शुरू और समाप्त होती हैं? वॉक में शीर्ष और कोरें दोहराई जा सकती हैं। संख्या को N कहें।
M = संलग्नता आव्यूहL = 2
N =
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम
55x ≡ 20 (mod 79) हल करें। हल x दें, जहाँ 0 < x < 79।
55x ≡ 20 (mod 79)
x =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
22x ≡ 52 (mod 74) हल करें। सबसे छोटा धनात्मक हल x दें।
22x ≡ 52 (mod 74)
x =
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)।
सत्यमान सारणी पंक्ति-दर-पंक्ति
p = 1, q = 1: p ∧ q = 1, (p ∧ q) → p = 1, ¬((p ∧ q) → p) = 0
p = 1, q = 0: p ∧ q = 0, (p ∧ q) → p = 1, ¬((p ∧ q) → p) = 0
p = 0, q = 1: p ∧ q = 0, (p ∧ q) → p = 1, ¬((p ∧ q) → p) = 0
p = 0, q = 0: p ∧ q = 0, (p ∧ q) → p = 1, ¬((p ∧ q) → p) = 0
वर्गीकृत करें
¬((p ∧ q) → p): 0, 0, 0, 0
हर पंक्ति में 0: विरोधोक्ति।
उत्तर
विरोधोक्ति
2.प्रस्ताविक तर्क और उपपत्तियाँ
उत्तर: ∃x (A(x) ∧ ¬B(x))
परिमाणक और तर्क: ¬∀x P(x) ≡ ∃x ¬P(x) और ¬∃x P(x) ≡ ∀x ¬P(x)। निषेध को भीतर ले जाएँ, उसके रास्ते में आने वाले हर परिमाणक को बदलें, और भीतरी सूत्र का निषेध प्रस्ताविक नियमों से करें, जैसे ¬(a → b) ≡ a ∧ ¬b। तर्क वैध होता है जब उन सभी पंक्तियों में निष्कर्ष 1 हो जिनमें सभी आधार-वाक्य 1 हों। सत्य आधार-वाक्यों और असत्य निष्कर्ष वाली एक भी पंक्ति प्रति-उदाहरण है और दिखाती है कि तर्क अवैध है।
निषेध को भीतर ले जाएँ
¬∀x (A(x) → B(x)) ≡ ∃x (A(x) ∧ ¬B(x))
उत्तर
∃x (A(x) ∧ ¬B(x))
बाकी विकल्प या तो किसी परिमाणक को अपरिवर्तित रखते हैं, या परिमाणकों का क्रम बदल देते हैं, या भीतरी सूत्र का निषेध गलत करते हैं।
3.समुच्चय, संबंध और फलन
उत्तर: |(F ∪ G ∪ S)′| = 7
समुच्चय और वेन आरेख: 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|।
केंद्र और जोड़ियाँ
F ∩ G ∩ S: 2
F ∩ G केवल: 13 − 2 = 11
F ∩ S केवल: 16 − 2 = 14
G ∩ S केवल: 5 − 2 = 3
अकेले समुच्चय
F केवल: 30 − 11 − 14 − 2 = 3
G केवल: 27 − 11 − 3 − 2 = 11
S केवल: 29 − 14 − 3 − 2 = 10
उत्तर
|F ∪ G ∪ S| = 54
|(F ∪ G ∪ S)′| = 61 − 54 = 7
उत्तर
|(F ∪ G ∪ S)′| = 7
4.समुच्चय, संबंध और फलन
उत्तर: N = 11664
संबंध: समुच्चय 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 को असंयुक्त वर्गों में बाँटता है।
स्वतंत्र विकल्प गिनें
N = 24·36 = 11664
उत्तर
N = 11664
5.ग्राफ़ सिद्धांत
उत्तर: L = 21
यूलर, हैमिल्टन और वृक्ष: संबद्ध ग्राफ़ में यूलर परिपथ (हर कोर एक बार, शुरुआत पर वापसी) तब होता है जब हर शीर्ष की घात सम हो, और परिपथ न होने वाला यूलर पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक विषम शीर्ष से दूसरे तक चलता है। हैमिल्टन परिपथ हर शीर्ष पर एक बार जाता है; Kn में ऐसे (n − 1)!/2 होते हैं। n शीर्षों वाले वृक्ष में n − 1 कोरें होती हैं, और m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद स्पैनिंग ट्री रखता है।
वृक्ष के लिए हैंडशेक लेमा
L + 45 = 2(L + 13) − 2
L = 21
उत्तर
L = 21
शॉर्टकट: L = 2 + Σ (d − 2), घात d ≥ 3 वाले शीर्षों पर।
6.ग्राफ़ सिद्धांत
उत्तर: N = 3
घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। Kn में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।
संलग्नता आव्यूह
A: 0 1 1 0 0
B: 1 0 1 0 1
C: 1 1 0 0 1
D: 0 0 0 0 1
E: 0 1 1 1 0
उभयनिष्ठ पड़ोसी
(M²)BB = 1·1 + 0·0 + 1·1 + 0·0 + 1·1 = 3
उत्तर
N = 3
7.संख्या सिद्धांत और मॉड्यूलर अंकगणित
उत्तर: x = 65
प्रतिलोम और सर्वांगसमताएँ: 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)।
55 का प्रतिलोम
r = 79, t = 0
r = 55, q = 1, t = 1
r = 24, q = 2, t = −1
r = 7, q = 3, t = 3
r = 3, q = 2, t = −10
r = 1, q = 3, t = 23
55−1 ≡ 23 (mod 79)
हल करें
x ≡ 23·20 = 460 ≡ 65 (mod 79)
जाँच: 55·65 = 3575 ≡ 20 (mod 79)
उत्तर
x = 65
8.संख्या सिद्धांत और मॉड्यूलर अंकगणित
उत्तर: x = 36
प्रतिलोम और सर्वांगसमताएँ: 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)।