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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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.प्रस्ताविक तर्क और उपपत्तियाँमध्यम

कौन-सा सूत्र b ∨ (a ∧ c) के तार्किक रूप से तुल्य है? उस पर क्लिक करें।

b ∨ (a ∧ c)

1(b ∧ a) ∨ (b ∧ c)
2(b ∨ a) ∧ (b ∨ c)
3(b ∨ a) ∧ c
4b ∧ (a ∨ c)

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

आधार-वाक्य c → b; b → a दिए गए हैं। इनसे कौन-सा निष्कर्ष निकलता है? उस पर क्लिक करें।

c → bb → a

1a → c
2¬c → ¬a
3c ∧ a
4c → a

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

62 विद्यार्थियों के समूह में 45 फ्रेंच (F) बोलते हैं, 22 जर्मन (G) बोलते हैं और 15 दोनों बोलते हैं। कितने किसी भी समुच्चय में नहीं हैं?

|U| = 62|F| = 45|G| = 22|F ∩ G| = 15

|(F ∪ G)′| =

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

X = {1, 2, …, 7} पर संबंध R तब सत्य है जब x ≡ y (mod 2)। R में कितने क्रमित युग्म हैं? संख्या को |R| कहें।

X = {1, …, 7}x R y ⟺ 2 | (x − y)

|R| =

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

एक संबद्ध ग्राफ़ में 16 शीर्ष और 18 कोरें हैं। स्पैनिंग ट्री बचाने के लिए कितनी कोरें k हटानी होंगी?

|V| = 16|E| = 18

k =

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

भारित ग्राफ़ में A से F तक के सबसे छोटे पथ की लंबाई d(F) डाइक्स्ट्रा के एल्गोरिथ्म से ज्ञात करें।

प्रारंभ: Aअंत: F

d(F) =

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

यूलर का टोशेंट φ(76) ज्ञात करें, यानी 1 से 76 तक के वे पूर्णांक जो 76 से सहअभाज्य हैं।

n = 76 = 2²·19

φ(76) =

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

{0, 1, …, 81} में 64x ≡ 2 (mod 82) के कितने हल N हैं?

64x ≡ 2 (mod 82)

N =

3विलयन

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

उत्तर: (b ∨ a) ∧ (b ∨ c)

तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 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 ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)।

b ∨ (a ∧ c) ≡ (b ∨ a) ∧ (b ∨ c)

सत्यमान सारणी से जाँच

a = 1, b = 1, c = 1: 1 | 1 1 1 1

a = 1, b = 1, c = 0: 1 | 1 1 0 1

a = 1, b = 0, c = 1: 1 | 0 1 1 0

a = 1, b = 0, c = 0: 0 | 0 0 0 0

a = 0, b = 1, c = 1: 1 | 1 1 1 1

a = 0, b = 1, c = 0: 1 | 0 1 0 0

a = 0, b = 0, c = 1: 0 | 0 0 0 0

a = 0, b = 0, c = 0: 0 | 0 0 0 0

उत्तर

(b ∨ a) ∧ (b ∨ c)

पट्टी के बाद के स्तंभ विकल्प हैं, दिखाए गए क्रम में।

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

उत्तर: c → a

परिमाणक और तर्क: ¬∀x P(x) ≡ ∃x ¬P(x) और ¬∃x P(x) ≡ ∀x ¬P(x)। निषेध को भीतर ले जाएँ, उसके रास्ते में आने वाले हर परिमाणक को बदलें, और भीतरी सूत्र का निषेध प्रस्ताविक नियमों से करें, जैसे ¬(a → b) ≡ a ∧ ¬b। तर्क वैध होता है जब उन सभी पंक्तियों में निष्कर्ष 1 हो जिनमें सभी आधार-वाक्य 1 हों। सत्य आधार-वाक्यों और असत्य निष्कर्ष वाली एक भी पंक्ति प्रति-उदाहरण है और दिखाती है कि तर्क अवैध है।

वे पंक्तियाँ जिनमें सभी आधार-वाक्य सत्य हैं

a = 1, b = 1, c = 1: a → c = 1, ¬c → ¬a = 1, c ∧ a = 1, c → a = 1

a = 1, b = 1, c = 0: a → c = 0, ¬c → ¬a = 0, c ∧ a = 0, c → a = 1

a = 1, b = 0, c = 0: a → c = 0, ¬c → ¬a = 0, c ∧ a = 0, c → a = 1

a = 0, b = 0, c = 0: a → c = 1, ¬c → ¬a = 1, c ∧ a = 0, c → a = 1

निष्कर्ष

c → a (काल्पनिक न्यायवाक्य)

उत्तर

c → a

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

उत्तर: |(F ∪ G)′| = 10

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

F − G: 45 − 15 = 30

G − F: 22 − 15 = 7

(F ∪ G)′: 62 − (30 + 7 + 15) = 10

उत्तर

|(F ∪ G)′| = 10

उत्तर

|(F ∪ G)′| = 10

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

उत्तर: |R| = 25

संबंध: समुच्चय 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 को असंयुक्त वर्गों में बाँटता है।

वर्ग

शेषफल 0: 3

शेषफल 1: 4

युग्म

|R| = 3² + 4² = 25

उत्तर

|R| = 25

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

उत्तर: k = 3

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

स्पैनिंग ट्री की कोरें

16 − 1 = 15

हटाई जाने वाली कोरें

k = 18 − 15 = 3

उत्तर

k = 3

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

उत्तर: d(F) = 23

सबसे छोटे पथ और स्पैनिंग ट्री: डाइक्स्ट्रा का एल्गोरिथ्म हर चक्र में एक शीर्ष निर्धारित करता है: सबसे छोटी अस्थायी दूरी वाला अनिर्धारित शीर्ष। तब उसकी दूरी अंतिम होती है, और हर पड़ोसी v को d(v) = min(d(v), d(u) + w(u, v)) मिलता है। क्रुस्कल का एल्गोरिथ्म कोरों को हल्की से भारी की ओर लेकर और चक्र बनाने वाली हर कोर छोड़कर न्यूनतम स्पैनिंग ट्री बनाता है; प्रिम का एल्गोरिथ्म प्रारंभिक शीर्ष से एक वृक्ष बढ़ाता है और हमेशा उससे बाहर जाने वाली सबसे हल्की कोर जोड़ता है। n शीर्षों के स्पैनिंग ट्री में n − 1 कोरें होती हैं।

डाइक्स्ट्रा चक्र-दर-चक्र

हर पंक्ति: निर्धारित शीर्ष, उसकी अंतिम दूरी, और वे पड़ोसी जिनकी दूरी सुधरती है।

A (0): B: 1

B (1): C: 13, D: 14, E: 9

E (9): D: 10, F: 23

D (10)

C (13)

F (23)

सबसे छोटा पथ

A → B → E → F

d(F) = 23

उत्तर

d(F) = 23

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

उत्तर: φ(76) = 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)।

अभाज्य गुणनखंड

76 = 2²·19

टोशेंट

φ(76) = φ(4)·φ(19) = 2·18 = 36

उत्तर

φ(76) = 36

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

उत्तर: N = 2

gcd से भाग दें

gcd(64, 82) = 2

32x ≡ 1 (mod 41)

घटी हुई सर्वांगसमता हल करें

32⁻¹ ≡ 9 (mod 41) → x ≡ 9 (mod 41)

82 के मापांक में हल

x ∈ {9, 50}

N = 2

उत्तर

N = 2

ExamProblems · examproblems.com/courses/discrete-mathematics