असतत गणित: क्रैम पैक

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 8 अभ्यास प्रश्न, पूरे हल पीछे दिए गए हैं।

नए प्रश्न कोर्स पर वापस जाएँ

प्रिंट विंडो में “PDF के रूप में सहेजें” चुनें, ताकि एक प्रति आपके डिवाइस पर रहे।

1सूत्र और विधियाँ

प्रस्ताविक तर्क और उपपत्तियाँ

सत्यमान सारणी की पंक्तियाँ: 2ⁿ
निहितार्थ: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
निषिद्ध निहितार्थ: ¬(p → q) ≡ p ∧ ¬q
द्विनिहितार्थ: p ↔ q ≡ (p → q) ∧ (q → p)
डी मॉर्गन: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
वितरण नियम: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
निषिद्ध परिमाणक: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
मोडस पोनेंस, मोडस टोलेंस: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

विधि

अलग-अलग चरों को गिनें: सत्यमान सारणी में 2ⁿ पंक्तियाँ होती हैं, जो सभी के 1 होने से शुरू होती हैं।
हर उप-सूत्र को अपना अलग स्तंभ दें और स्तंभों को भीतर से बाहर की ओर भरें।
हर संयोजक का नियम लगाएँ: → केवल 1 → 0 के लिए 0 होता है, ↔ तब 1 होता है जब दोनों पक्ष समान हों।
तुल्यता के लिए अंतिम स्तंभों की पंक्ति-दर-पंक्ति तुलना करें; किसी तर्क के लिए केवल उन्हीं पंक्तियों को देखें जिनमें हर आधार-वाक्य 1 हो।
परिमाणक वाले कथन का निषेध करने के लिए ¬ को भीतर ले जाएँ, ∀ और ∃ आपस में बदलें, और भीतरी सूत्र का निषेध करें।

समुच्चय, संबंध और फलन

दो समुच्चय: |A ∪ B| = |A| + |B| − |A ∩ B|
तीन समुच्चय: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
अंतर और पूरक: A − B = A ∩ B′, |A′| = |U| − |A|
घात समुच्चय और गुणनफल: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
आकार k के उपसमुच्चय: C(n, k) = n!/(k!(n − k)!)
फलन A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
n अवयवों पर संबंध: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
संयोजन: (g ∘ f)(x) = g(f(x))

विधि

वेन आरेख बनाएँ और क्षेत्र-दर-क्षेत्र तय करें कि समुच्चय व्यंजक में कौन-सा भाग आता है।
गिनती के प्रश्नों में क्षेत्रों को केंद्र से बाहर की ओर भरें: पहले सभी समुच्चय, फिर जोड़े, फिर अकेले समुच्चय, फिर बाहरी भाग।
जाँच के लिए समावेश–अपवर्जन का उपयोग करें: |A ∪ B| = |A| + |B| − |A ∩ B|।
किसी संबंध के लिए हर गुण को हर जोड़े पर जाँचें और गुण विफल होने पर एक प्रति-उदाहरण दें।
किसी फलन के लिए B के हर अवयव पर पहुँचने वाले तीरों को गिनें: अधिकतम एक हो तो एकैकी, कम से कम एक हो तो आच्छादक।

ग्राफ़ सिद्धांत

हैंडशेक लेमा: Σ deg(v) = 2|E|
पूर्ण ग्राफ़: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
नियमित ग्राफ़: |E| = n·k/2
वृक्ष और वन: |E| = n − 1, |E| = n − c
वृक्ष के पत्ते: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
यूलर: परिपथ: सभी घात सम; पथ: ठीक 2 घात विषम
K_n में हैमिल्टन परिपथ: (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.प्रस्ताविक तर्क और उपपत्तियाँमध्यम

इसकी सत्यमान सारणी की 8 पंक्तियों में से कितनी में ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) सत्य है? इस संख्या को N कहें।

¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q))

N =

2.प्रस्ताविक तर्क और उपपत्तियाँकठिन

सत्यमान सारणी की 16 पंक्तियों में से कितनी ((¬a ∧ ¬d) ∨ b) ∨ ((d → a) ∧ (b ∧ c)) को सत्य बनाती हैं? इस संख्या को N कहें।

((¬a ∧ ¬d) ∨ b) ∨ ((d → a) ∧ (b ∧ c))

N =

3.समुच्चय, संबंध और फलनमध्यम

62 प्रथम वर्ष के विद्यार्थियों में से 22 गणित (M) में, 31 भौतिकी (P) में और 27 रसायन (C) में उत्तीर्ण हुए। 12 M और P में, 6 M और C में, 16 P और C में, तथा 4 तीनों में उत्तीर्ण हुए। कितने तीनों समुच्चयों में से ठीक एक में हैं? संख्या को n कहें।

|U| = 62

n =

4.समुच्चय, संबंध और फलनकठिन

तीर आरेख फलन f: A → B दिखाता है, जहाँ A = {1, 2, 3} और B = {a, b}। f के अनुरूप विवरण पर क्लिक करें।

f = {(1, b), (2, a), (3, b)}

1एकैकी, आच्छादक नहीं
2आच्छादक, एकैकी नहीं
3एकैकी आच्छादक
4दोनों में से कुछ नहीं

5.ग्राफ़ सिद्धांतमध्यम

क्या संबद्ध ग्राफ़ में यूलर परिपथ है, परिपथ न होने वाला यूलर पथ है, या दोनों में से कुछ नहीं? अपना उत्तर क्लिक करें।

|V| = 7|E| = 8

1यूलर परिपथ
2यूलर पथ, परिपथ नहीं
3दोनों में से कुछ नहीं

6.ग्राफ़ सिद्धांतकठिन

लंबाई 2 की कितनी बंद वॉक D से शुरू और समाप्त होती हैं? वॉक में शीर्ष और कोरें दोहराई जा सकती हैं। संख्या को N कहें।

M = संलग्नता आव्यूहL = 2

N =

7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

67 के मापांक में 5 का प्रतिलोम ज्ञात करें: वह संख्या x जिसके लिए 0 < x < 67 और 5·x ≡ 1 (mod 67)।

a = 5n = 67

5⁻¹ mod 67 =

8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन

एक RSA कुंजी अभाज्य p = 13 और q = 23 तथा सार्वजनिक घातांक e = 5 का उपयोग करती है। निजी घातांक d ज्ञात करें (0 < d < φ(n))।

p = 13q = 23e = 5

d =

3विलयन

1.प्रस्ताविक तर्क और उपपत्तियाँ

उत्तर: N = 7

सत्यमान सारणियाँ: n अलग-अलग चरों वाले सूत्र की 2ⁿ पंक्तियाँ होती हैं, सत्यमानों के हर संयोजन के लिए एक (1 = सत्य, 0 = असत्य)। भीतर से बाहर की ओर काम करें और हर उप-सूत्र को अपना स्तंभ दें। ¬a मान उलट देता है; a ∧ b केवल तब 1 होता है जब दोनों 1 हों; a ∨ b केवल तब 0 होता है जब दोनों 0 हों; a → b केवल तब 0 होता है जब a = 1 और b = 0; a ↔ b तब 1 होता है जब दोनों पक्ष बराबर हों।

सत्यमान सारणी पंक्ति-दर-पंक्ति

p = 1, q = 1, r = 1: ¬q = 0, ¬q → p = 1, (¬q → p) ↔ r = 1, ¬((¬q → p) ↔ r) = 0, r ∨ q = 1, ¬(r ∨ q) = 0, ¬((¬q → p) ↔ r) ∧ ¬(r ∨ q) = 0, ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) = 1

p = 1, q = 1, r = 0: ¬q = 0, ¬q → p = 1, (¬q → p) ↔ r = 0, ¬((¬q → p) ↔ r) = 1, r ∨ q = 1, ¬(r ∨ q) = 0, ¬((¬q → p) ↔ r) ∧ ¬(r ∨ q) = 0, ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) = 1

p = 1, q = 0, r = 1: ¬q = 1, ¬q → p = 1, (¬q → p) ↔ r = 1, ¬((¬q → p) ↔ r) = 0, r ∨ q = 1, ¬(r ∨ q) = 0, ¬((¬q → p) ↔ r) ∧ ¬(r ∨ q) = 0, ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) = 1

p = 1, q = 0, r = 0: ¬q = 1, ¬q → p = 1, (¬q → p) ↔ r = 0, ¬((¬q → p) ↔ r) = 1, r ∨ q = 0, ¬(r ∨ q) = 1, ¬((¬q → p) ↔ r) ∧ ¬(r ∨ q) = 1, ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) = 0

p = 0, q = 1, r = 1: ¬q = 0, ¬q → p = 1, (¬q → p) ↔ r = 1, ¬((¬q → p) ↔ r) = 0, r ∨ q = 1, ¬(r ∨ q) = 0, ¬((¬q → p) ↔ r) ∧ ¬(r ∨ q) = 0, ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) = 1

p = 0, q = 1, r = 0: ¬q = 0, ¬q → p = 1, (¬q → p) ↔ r = 0, ¬((¬q → p) ↔ r) = 1, r ∨ q = 1, ¬(r ∨ q) = 0, ¬((¬q → p) ↔ r) ∧ ¬(r ∨ q) = 0, ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) = 1

p = 0, q = 0, r = 1: ¬q = 1, ¬q → p = 0, (¬q → p) ↔ r = 0, ¬((¬q → p) ↔ r) = 1, r ∨ q = 1, ¬(r ∨ q) = 0, ¬((¬q → p) ↔ r) ∧ ¬(r ∨ q) = 0, ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) = 1

p = 0, q = 0, r = 0: ¬q = 1, ¬q → p = 0, (¬q → p) ↔ r = 1, ¬((¬q → p) ↔ r) = 0, r ∨ q = 0, ¬(r ∨ q) = 1, ¬((¬q → p) ↔ r) ∧ ¬(r ∨ q) = 0, ¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)) = 1

मान 1 वाली पंक्तियाँ गिनें

¬(¬((¬q → p) ↔ r) ∧ ¬(r ∨ q)): 1, 1, 1, 0, 1, 1, 1, 1

N = 7

उत्तर

N = 7

2.प्रस्ताविक तर्क और उपपत्तियाँ

उत्तर: N = 10

स्तंभ

¬a; ¬d; ¬a ∧ ¬d; (¬a ∧ ¬d) ∨ b; d → a; b ∧ c; (d → a) ∧ (b ∧ c); ((¬a ∧ ¬d) ∨ b) ∨ ((d → a) ∧ (b ∧ c))

a पर बाँटें

a = 1: 4

a = 0: 6

N = 4 + 6 = 10

उत्तर

N = 10

3.समुच्चय, संबंध और फलन

उत्तर: n = 24

समुच्चय और वेन आरेख: 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|।

केंद्र और जोड़ियाँ

M ∩ P ∩ C: 4

M ∩ P केवल: 12 − 4 = 8

M ∩ C केवल: 6 − 4 = 2

P ∩ C केवल: 16 − 4 = 12

अकेले समुच्चय

M केवल: 22 − 8 − 2 − 4 = 8

P केवल: 31 − 8 − 12 − 4 = 7

C केवल: 27 − 2 − 12 − 4 = 9

उत्तर

8 + 7 + 9 = 24

उत्तर

n = 24

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(3) = b → एकैकी नहीं

आच्छादक?

B का हर अवयव पहुँचा जाता है → आच्छादक

उत्तर

आच्छादक, एकैकी नहीं

उत्तर

आच्छादक, एकैकी नहीं

5.ग्राफ़ सिद्धांत

उत्तर: दोनों में से कुछ नहीं

यूलर, हैमिल्टन और वृक्ष: संबद्ध ग्राफ़ में यूलर परिपथ (हर कोर एक बार, शुरुआत पर वापसी) तब होता है जब हर शीर्ष की घात सम हो, और परिपथ न होने वाला यूलर पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक विषम शीर्ष से दूसरे तक चलता है। हैमिल्टन परिपथ हर शीर्ष पर एक बार जाता है; K_n में ऐसे (n − 1)!/2 होते हैं। n शीर्षों वाले वृक्ष में n − 1 कोरें होती हैं, और m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद स्पैनिंग ट्री रखता है।

घात

deg(A) = 1, deg(B) = 4, deg(C) = 3, deg(D) = 1, deg(E) = 3, deg(F) = 1, deg(G) = 3

विषम शीर्ष

A, C, D, E, F, G → 6

दोनों में से कुछ नहीं

उत्तर

दोनों में से कुछ नहीं

6.ग्राफ़ सिद्धांत

उत्तर: N = 2

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। K_n में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।

संलग्नता आव्यूह

A: 0 1 1 0 0

B: 1 0 1 1 1

C: 1 1 0 0 1

D: 0 1 0 0 1

E: 0 1 1 1 0

उभयनिष्ठ पड़ोसी

(M²)_DD = 0·0 + 1·1 + 0·0 + 0·0 + 1·1 = 2

उत्तर

N = 2

7.संख्या सिद्धांत और मॉड्यूलर अंकगणित

उत्तर: 5⁻¹ mod 67 = 27

प्रतिलोम और सर्वांगसमताएँ: 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·5 (mod 67) के रूप में लिखा जाता है।

r = 67, t = 0

r = 5, q = 13, t = 1

r = 2, q = 2, t = −13

r = 1, q = 2, t = 27

व्युत्क्रम

1 ≡ 27·5 (mod 67)

x = 27

जाँच: 5·27 = 135 = 2·67 + 1

उत्तर

5⁻¹ mod 67 = 27

8.संख्या सिद्धांत और मॉड्यूलर अंकगणित

उत्तर: d = 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 से डिक्रिप्ट करें।

मापांक और टोशेंट

n = 13·23 = 299

φ(n) = 12·22 = 264

विस्तारित यूक्लिडीय एल्गोरिथ्म

r = 264, t = 0

r = 5, q = 52, t = 1

r = 4, q = 1, t = −52

r = 1, q = 4, t = 53

निजी घातांक

d = 53

जाँच: 5·53 = 265 = 1·264 + 1

उत्तर

d = 53

ExamProblems · examproblems.com/courses/discrete-mathematics