माना R समुच्चय X पर एक द्विआधारी संबंध है। संबंध को R कहा जाता है चिंतनशील , यदि (x, x) О R सभी x О X के लिए; सममित - यदि (x, y) О R से यह (y, x) О R का अनुसरण करता है; संक्रमणीय संख्या 23 विकल्प 24 से मेल खाती है यदि (x, y) О R और (y, z) О R का तात्पर्य (x, z) О R है।

उदाहरण 1

हम कहेंगे कि x О X आम बात है तत्व y О X के साथ, यदि सेट है
x Ç y खाली नहीं है. समान होने का संबंध प्रतिवर्ती और सममित होगा, लेकिन संक्रमणीय नहीं।

तुल्यता संबंधएक्स पर एक प्रतिवर्ती, सकर्मक और सममित संबंध है। यह देखना आसान है कि R Í X ´

आईडी एक्स Í आर (रिफ्लेक्सिविटी),

आर -1 Í आर (समरूपता),

आर ° आर Í आर (परिवर्तनशीलता)।

वास्तव में, ये तीन स्थितियाँ निम्नलिखित के बराबर हैं:

आईडी एक्स Í आर, आर -1 = आर, आर ° आर = आर।

बँटवारा करकेएक समुच्चय .

X पर प्रत्येक समतुल्य संबंध ~ एक विभाजन A से मेल खाता है, जिसके तत्व उपसमुच्चय हैं, जिनमें से प्रत्येक में संबंध ~ के तत्व शामिल हैं। ये उपसमुच्चय कहलाते हैं समतुल्य वर्ग . इस विभाजन A को ~ के संबंध में समुच्चय X का कारक समुच्चय कहा जाता है और इसे X/~ से दर्शाया जाता है।

आइए हम प्राकृतिक संख्याओं के समुच्चय w पर संबंध परिभाषित करें, यदि x और y को 3 से विभाजित करने पर शेषफल बराबर हो तो x ~ y लगाएं। फिर w/~ में शेषफल 0, 1 और 2 के अनुरूप तीन तुल्यता वर्ग होते हैं।

आदेश संबंध

समुच्चय X पर एक द्विआधारी संबंध R कहलाता है antisymmetric , यदि x R y और y R x से यह इस प्रकार है: x = y. समुच्चय X पर एक द्विआधारी संबंध R कहलाता है आदेश संबंध , यदि यह रिफ्लेक्टिव, एंटीसिमेट्रिक और सकर्मक है। यह देखना आसान है कि यह निम्नलिखित स्थितियों के बराबर है:

1) आईडी एक्स आई आर (रिफ्लेक्सिविटी),

2) आर Ç आर -1 (एंटीसिममेट्री),

3) आर ° आर Í आर (परिवर्तनशीलता)।

एक क्रमित युग्म (X, R) जिसमें एक समुच्चय X और X पर एक क्रम संबंध R होता है, कहलाता है आंशिक रूप से ऑर्डर किया गया सेट .

उदाहरण 1

माना X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2 ), (1, 3), (2, 2), (3, 3)).

चूँकि R शर्तें 1 - 3 को संतुष्ट करता है, तो (X, R) आंशिक रूप से ऑर्डर किया गया सेट है। तत्वों x = 2, y = 3 के लिए, न तो x R y और न ही y R x सत्य है। ऐसे तत्वों को कहा जाता है बेमिसाल . आमतौर पर ऑर्डर संबंध को £ द्वारा दर्शाया जाता है। दिए गए उदाहरण में, 0 £ 1 और 2 £ 2, लेकिन यह सत्य नहीं है कि 2 £ 3 है।

उदाहरण 2

होने देना< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

आंशिक रूप से क्रमित समुच्चय (X, £) के तत्व x, y О X कहलाते हैं तुलनीय , यदि x £ y या y £ x।

आंशिक रूप से ऑर्डर किया गया सेट (X, £) कहलाता है रैखिक रूप से क्रमबद्ध या जंजीर , यदि इसके कोई दो तत्व तुलनीय हैं। उदाहरण 2 से सेट को रैखिक रूप से क्रमबद्ध किया जाएगा, लेकिन उदाहरण 1 से सेट को नहीं।

आंशिक रूप से ऑर्डर किए गए सेट (X, £) का एक उपसमुच्चय A Í X कहलाता है ऊपर से घिरा हुआ , यदि कोई तत्व x О X ऐसा है कि सभी О A के लिए £ x है। तत्व x О सबसे वृहद X में यदि y £ x सभी y О X के लिए है। एक तत्व x О उदाहरण 1 में, तत्व 2 और 3 अधिकतम होंगे, लेकिन सबसे बड़े नहीं। इसी प्रकार परिभाषित किया गया है निचली सीमा उपसमुच्चय, सबसे छोटे और न्यूनतम तत्व। उदाहरण 1 में, तत्व 0 सबसे छोटा और न्यूनतम दोनों होगा। उदाहरण 2 में, 0 में भी ये गुण हैं, लेकिन (w, £) में न तो सबसे बड़ा और न ही अधिकतम तत्व है।

मान लीजिए (X, £) एक आंशिक रूप से ऑर्डर किया गया सेट है, A Í X एक उपसमुच्चय है। ए पर एक संबंध, जिसमें तत्वों ए, बी ओ ए के जोड़े (ए, बी) शामिल हैं, जिसके लिए £ बी, ए पर एक ऑर्डर संबंध होगा। यह संबंध उसी प्रतीक द्वारा दर्शाया गया है: £। इस प्रकार, (ए, £) आंशिक रूप से ऑर्डर किया गया सेट है। यदि इसे रैखिक रूप से क्रमबद्ध किया जाए, तो हम कहेंगे कि A है जंजीर (एक्स, £) में।

अधिकतम सिद्धांत

कुछ गणितीय कथनों को पसंद के सिद्धांत के बिना सिद्ध नहीं किया जा सकता है। ये बयान कहा जा रहा है पसंद के सिद्धांत पर निर्भर करें या ZFC सिद्धांत में मान्य व्यवहार में, पसंद के स्वयंसिद्ध के बजाय, या तो ज़र्मेलो स्वयंसिद्ध, या कुराटोस्की-ज़ोर्न लेम्मा, या पसंद के स्वयंसिद्ध के समतुल्य कोई अन्य कथन आमतौर पर प्रमाण के लिए उपयोग किया जाता है।

कुराटोव्स्की-ज़ोर्न लेम्मा. यदि प्रत्येक श्रृंखला आंशिक रूप से क्रमबद्ध सेट में है(एक्स, £) ऊपर से सीमित है, फिर अंदर तकएक्स कम से कम एक अधिकतम तत्व है.

यह प्रमेयिका पसंद के स्वयंसिद्ध के समतुल्य है, और इसलिए इसे एक स्वयंसिद्ध के रूप में स्वीकार किया जा सकता है।

प्रमेय.किसी आंशिक रूप से ऑर्डर किए गए सेट के लिए(एक्स, £) एक रिश्ता है जिसमें रिश्ता है£ और परिवर्तनएक्स एक रैखिक क्रमबद्ध सेट में।

सबूत. संबंध £ वाले सभी ऑर्डर संबंधों के सेट को समावेशन संबंध यू द्वारा आदेश दिया गया है। चूंकि ऑर्डर संबंधों की एक श्रृंखला का मिलन एक ऑर्डर संबंध होगा, तो कुराटोस्की-ज़ोर्न लेम्मा द्वारा एक अधिकतम संबंध आर मौजूद है जैसे कि x £ y का तात्पर्य x R y है। आइए हम सिद्ध करें कि R, X को रैखिक रूप से व्यवस्थित करने वाला एक संबंध है। आइए इसके विपरीत मान लें: मान लीजिए कि a, b О X का अस्तित्व इस प्रकार है कि न तो (a, b) और न ही (b, a) R से संबंधित हैं। संबंध पर विचार करें:

आर¢ = आर È ((एक्स, वाई): एक्स आर ए और बी आर वाई)।

यह जोड़ी (ए, बी) को आर और जोड़े (एक्स, वाई) को जोड़कर प्राप्त किया जाता है, जिसे आर¢ में इस शर्त से जोड़ा जाना चाहिए कि आर¢ एक ऑर्डर संबंध है। यह देखना आसान है कि R¢ रिफ्लेक्सिव, एंटीसिमेट्रिक और ट्रांजिटिव है। हम R Ì R¢ प्राप्त करते हैं, जो R की अधिकतमता का खंडन करता है, इसलिए, R वांछित रैखिक क्रम संबंध है।

एक रैखिक रूप से क्रमित समुच्चय X को सुव्यवस्थित कहा जाता है यदि इसके प्रत्येक गैर-रिक्त उपसमुच्चय A Í

ज़र्मेलो का स्वयंसिद्ध. प्रत्येक सेट के लिए एक ऑर्डर संबंध होता है जो इसे पूरी तरह से ऑर्डर किए गए सेट में बदल देता है।

उदाहरण के लिए, प्राकृतिक संख्याओं का समुच्चय w पूरी तरह से क्रमबद्ध है। प्रेरण के सिद्धांत को संक्षेप में इस प्रकार प्रस्तुत किया गया है:

ट्रांसफिनिट इंडक्शन. अगर(एक्स, £) एक पूर्णतः व्यवस्थित समुच्चय है और F(x) इसके तत्वों का एक गुण है,सबसे छोटे तत्व x 0 О X के लिए सत्य और ऐसा कि सभी y के लिए F(y) के सत्य से < z следует истинность F(z), то एफ(एक्स) हर किसी के लिए सच हैएक्स ओ एक्स .

सुनो तो< z означает, что у £ z, но y ¹ z. Действительно, в противном случае среди x Î X, не обладающих свойством F(x), можно выбрать наименьший элемент x 1 , и выполнение F(y) для всех y < x 1 приводит к выполнению F(x 1), противоречащему предположению.

शक्ति अवधारणा

मान लीजिए f: X à Y और g: Y à Z सेट के मानचित्र हैं। चूँकि f और g संबंध हैं, उनकी संरचना g ° f(x) = g(f(x)) परिभाषित है। यदि h: Z à T सेट का मानचित्र है, तो h ° (g ° f) = (h ° g) ° f। संबंध Id X और Id Y फ़ंक्शन हैं, इसलिए, रचनाएँ Id Y ° f = f ° Id x = f परिभाषित हैं। X = Y के लिए, हम f 2 = f ° f, f 3 = f 2 ° f, ..., f n+1 = f n ° f को परिभाषित करते हैं।

मैपिंग f: X àY कहलाती है इंजेक्शन द्वारा , यदि समुच्चय X के किसी तत्व x 1 ¹ x 2 के लिए, f(x 1) ¹ f(x 2) सत्य है। मैपिंग f को कहा जाता है आपत्ति , यदि प्रत्येक y ОY के लिए एक x О X है जैसे कि f(x) = y. यदि f एक प्रक्षेपण और एक इंजेक्शन दोनों है, तो f कहा जाता है द्विभाजन . यह देखना आसान है कि f एक आक्षेप है यदि और केवल यदि व्युत्क्रम संबंध f -1 Í Y ´ X एक फलन है।

हम कहेंगे कि समानता |X| = |Y|, यदि X और Y के बीच कोई आपत्ति है। मान लीजिए |X| £ |Y|, यदि कोई इंजेक्शन है f: X à Y.

कैंटर-श्रोएडर-बर्नस्टीन प्रमेय. अगर|एक्स| £ |Y| और|वाई| £ |एक्स| , वह|एक्स| = |वाई|.

सबूत. शर्त के अनुसार, इंजेक्शन f: X à Y और g: Y à X हैं। मान लीजिए A = g¢¢Y = Img मैपिंग g के संबंध में सेट Y की छवि है। तब

(X \ A) Ç (gf)¢¢(X \ A) = Æ,

(gf)¢¢(X \ A) Ç (gf) 2 ¢¢(X \ A) = Æ, …,

(gf) n ¢¢(X \ A) Ç (gf) n+1 ¢¢(X \ A) = Æ, ...

मैपिंग j: X à A पर विचार करें, जिसे j(x) = gf(x) के रूप में दिया गया है

x Î (X \ A) È (gf)¢¢(X \ A) È (gf) 2 ¢¢(X \ A) È …, और अन्य मामलों में j(x) = x। यह देखना आसान है कि j एक आपत्ति है। X और Y के बीच आवश्यक आक्षेप g -1°j के बराबर होगा।

कैंटर का एंटीनॉमी

चलो |एक्स|< |Y|, если |X| £ |Y| и не существует биекции между X и Y.

कैंटर का प्रमेय. किसी भी सेट X, |X| के लिए< |P(X)|, где P(X) – множество всех подмножеств множества X.

(अर्थात, जिसमें निम्नलिखित गुण हैं: सेट का प्रत्येक तत्व स्वयं के बराबर है; यदि एक्ससमकक्ष य, वह यसमकक्ष एक्स; अगर एक्ससमकक्ष य, ए यसमकक्ष जेड, वह एक्ससमकक्ष जेड ).

फिर सभी समतुल्य वर्गों का सेट कहा जाता है कारक सेटऔर नामित किया गया है. किसी समुच्चय को समतुल्य तत्वों के वर्गों में विभाजित करना उसका कहलाता है गुणन.

से प्रदर्शित करें एक्सतुल्यता वर्गों के समुच्चय को कहा जाता है कारक मानचित्रण.

उदाहरण

अर्ध-मानक वाले स्थानों से मानक स्थान, लगभग आंतरिक उत्पाद वाले स्थानों से आंतरिक उत्पाद वाले स्थान आदि प्राप्त करने के लिए सेट फ़ैक्टराइज़ेशन का उपयोग करना उचित है। ऐसा करने के लिए, हम क्रमशः, एक वर्ग के मानदंड का परिचय देते हैं, जो कि के बराबर है। एक मनमाने तत्व का मानदंड, और वर्गों के मनमाने तत्वों के एक आंतरिक उत्पाद के रूप में वर्गों का आंतरिक उत्पाद। बदले में, तुल्यता संबंध को निम्नानुसार पेश किया जाता है (उदाहरण के लिए, एक सामान्यीकृत भागफल स्थान बनाने के लिए): मूल सेमीनॉर्म्ड स्पेस का एक उपसमुच्चय पेश किया जाता है, जिसमें शून्य सेमीनॉर्म वाले तत्व शामिल होते हैं (वैसे, यह रैखिक है, यानी, यह एक उपसमष्टि है) और यह माना जाता है कि दो तत्व समतुल्य हैं यदि उनका अंतर इसी उपसमष्टि से संबंधित है।

यदि, एक रैखिक स्थान को गुणनखंडित करने के लिए, एक निश्चित उपस्थान पेश किया जाता है और यह माना जाता है कि यदि मूल स्थान के दो तत्वों का अंतर इस उपस्थान से संबंधित है, तो ये तत्व समतुल्य हैं, तो कारक सेट एक रैखिक स्थान है और इसे कहा जाता है एक कारक स्थान.

उदाहरण

यह सभी देखें

विकिमीडिया फ़ाउंडेशन. 2010.

देखें अन्य शब्दकोशों में "फैक्टरसेट" क्या है:

अमूर्तता के माध्यम से परिभाषाओं में अंतर्निहित तार्किक सिद्धांत (अमूर्तता के माध्यम से परिभाषा देखें): समानता के प्रकार का कोई भी संबंध, तत्वों के कुछ प्रारंभिक सेट पर परिभाषित, मूल को विभाजित (विभाजित, वर्गीकृत) करता है... ...

सोच का एक रूप जो वस्तुओं और घटनाओं के आवश्यक गुणों, कनेक्शन और संबंधों को उनके विरोधाभास और विकास में दर्शाता है; एक विचार या विचारों की प्रणाली जो सामान्यीकरण करती है, एक निश्चित वर्ग की वस्तुओं को कुछ सामान्य के अनुसार और समग्र रूप से अलग करती है... ... महान सोवियत विश्वकोश

गैलोइस ग्रुप कोहोमोलॉजी। यदि एम एक एबेलियन समूह है और एम पर कार्य करने वाले विस्तार का एक गैलोइस समूह है, तो गैलोइस कोहोमोलॉजी समूह सभी मानचित्रों से युक्त एक कॉम्प्लेक्स द्वारा परिभाषित कोहोमोलॉजी समूह हैं, और डी एक कोबाउंड्री ऑपरेटर है (समूहों की कोहोमोलॉजी देखें)...। .. गणितीय विश्वकोश

स्वर्ग का निर्माण, सबसे पहले सेट सिद्धांत में दिखाई दिया, और फिर बीजगणित, टोपोलॉजी और गणित के अन्य क्षेत्रों में व्यापक रूप से उपयोग किया जाने लगा। आई.पी. का एक महत्वपूर्ण विशेष मामला एक ही प्रकार की गणितीय संरचनाओं के निर्देशित परिवार का आई.पी. है। रहने दो … गणितीय विश्वकोश

अंक हालांकि समूह जी के सापेक्ष सेट एक्स (बाईं ओर) पर कार्य कर रहे हैं, सेट सेट जी का एक उपसमूह है और कहा जाता है। जी के संबंध में एक बिंदु का स्टेबलाइजर, या स्थिर उपसमूह। मैपिंग जी/जीएक्स और कक्षा जी(एक्स) के बीच एक आक्षेप उत्पन्न करती है। के बारे में।… … गणितीय विश्वकोश

इस लेख का परिचय बहुत छोटा है. कृपया एक परिचयात्मक अनुभाग जोड़ें जो लेख के विषय का संक्षेप में परिचय देता है और इसकी सामग्री का सारांश देता है... विकिपीडिया

यह लेख बीजगणितीय प्रणाली के बारे में है। गणितीय तर्क की उस शाखा के लिए जो कथनों और उन पर संक्रियाओं का अध्ययन करती है, तर्क का बीजगणित देखें। बूलियन बीजगणित एक गैर-रिक्त सेट ए है जिसमें दो बाइनरी ऑपरेशन (एक संयोजन के अनुरूप) हैं, ... विकिपीडिया

मान लीजिए कि एक समुच्चय पर एक तुल्यता संबंध दिया गया है। तब सभी समतुल्य वर्गों के समुच्चय को कारक समुच्चय कहा जाता है और निरूपित किया जाता है। किसी समुच्चय को समतुल्य तत्वों के वर्गों में विभाजित करना उसका गुणनखंडन कहलाता है। से मैपिंग ... ...विकिपीडिया

ज्यामिति में, एक निर्देशित खंड को बिंदुओं की एक क्रमबद्ध जोड़ी के रूप में समझा जाता है, जिनमें से पहला, बिंदु ए, इसकी शुरुआत कहा जाता है, और दूसरा, बी, इसका अंत कहा जाता है। सामग्री 1 परिभाषा...विकिपीडिया

गणित की विभिन्न शाखाओं में, मैपिंग का कर्नेल एक निश्चित सेट केर्फ़ होता है, जो एक अर्थ में एफ और इंजेक्शन मैपिंग के बीच अंतर को दर्शाता है। विशिष्ट परिभाषा भिन्न हो सकती है, लेकिन इंजेक्टिव मैपिंग के लिए... विकिपीडिया

नौकरी का स्रोत: कार्य 10_20. एकीकृत राज्य परीक्षा 2018 सामाजिक अध्ययन। समाधान

कार्य 20.नीचे दिए गए पाठ को पढ़ें, जिसमें कई शब्द (वाक्यांश) लुप्त हैं। उन शब्दों (वाक्यांशों) की सूची से चयन करें जिन्हें अंतराल के स्थान पर डालने की आवश्यकता है।

“जीवन की गुणवत्ता कई कारकों पर निर्भर करती है, जिसमें व्यक्ति के निवास स्थान से लेकर सामान्य सामाजिक-आर्थिक और (ए) स्थिति के साथ-साथ देश में राजनीतिक मामलों की स्थिति भी शामिल है। जीवन की गुणवत्ता, एक डिग्री या किसी अन्य तक, जनसांख्यिकीय स्थिति, आवास और उत्पादन की स्थिति, _____(बी) की मात्रा और गुणवत्ता आदि से प्रभावित हो सकती है। अर्थव्यवस्था में जरूरतों की संतुष्टि की डिग्री के आधार पर, यह है जनसंख्या के जीवन स्तर के विभिन्न स्तरों को अलग करने की प्रथा: धन - उपयोग (बी) व्यापक मानव विकास सुनिश्चित करना; वैज्ञानिक रूप से आधारित मानकों के अनुसार _____(जी) का सामान्य स्तर, एक व्यक्ति को उसकी शारीरिक और बौद्धिक शक्ति की बहाली प्रदान करता है; गरीबी - प्रजनन की न्यूनतम सीमा के रूप में कार्य क्षमता बनाए रखने के स्तर पर वस्तुओं की खपत _____(डी); गरीबी जैविक मानदंडों के अनुसार वस्तुओं और सेवाओं के न्यूनतम स्वीकार्य सेट की खपत है, जो केवल मानव व्यवहार्यता को बनाए रखने की अनुमति देती है।

जनसंख्या, बाजार की स्थितियों के अनुकूल, आय के विभिन्न अतिरिक्त स्रोतों का उपयोग करती है, जिसमें व्यक्तिगत भूखंडों से आय, _____(ई) से लाभ शामिल है।"

सूची में शब्द (वाक्यांश) नामवाचक मामले में दिए गए हैं। प्रत्येक शब्द (वाक्यांश) का प्रयोग केवल एक बार ही किया जा सकता है।

प्रत्येक अंतराल को मानसिक रूप से भरते हुए, एक के बाद एक शब्द (वाक्यांश) चुनें। कृपया ध्यान दें कि सूची में रिक्त स्थानों को भरने के लिए आवश्यकता से अधिक शब्द (वाक्यांश) हैं।

शर्तों की सूची:

1) पूंजी

2) पर्यावरण

3) तर्कसंगत उपभोग

4) उपभोक्ता वस्तुएँ

5) उत्पादन के साधन

7) परिश्रम

8) उद्यमशीलता गतिविधि

9) सामाजिक गतिशीलता

समाधान।

आइए शब्दों को पाठ में सम्मिलित करें।

“जीवन की गुणवत्ता कई कारकों पर निर्भर करती है, जिसमें व्यक्ति के निवास स्थान से लेकर सामान्य सामाजिक-आर्थिक और पर्यावरणीय (2) (ए) स्थिति, साथ ही देश में राजनीतिक मामलों की स्थिति भी शामिल है। जीवन की गुणवत्ता, एक डिग्री या किसी अन्य तक, जनसांख्यिकीय स्थिति, आवास और उत्पादन की स्थिति, उपभोक्ता वस्तुओं की मात्रा और गुणवत्ता (4) (बी), आदि से प्रभावित हो सकती है। यह आवश्यकताओं की संतुष्टि की डिग्री पर निर्भर करता है अर्थव्यवस्था, जनसंख्या के जीवन स्तर के विभिन्न स्तरों को अलग करने की प्रथा है: धन - लाभों का उपयोग (6) (बी) जो किसी व्यक्ति के व्यापक विकास को सुनिश्चित करता है; तर्कसंगत उपभोग का सामान्य स्तर (3) (डी) वैज्ञानिक रूप से आधारित मानकों के अनुसार, एक व्यक्ति को उसकी शारीरिक और बौद्धिक शक्ति की बहाली प्रदान करता है; गरीबी - श्रम शक्ति प्रजनन की न्यूनतम सीमा के रूप में कार्य क्षमता बनाए रखने के स्तर पर वस्तुओं की खपत (7) (डी); गरीबी जैविक मानदंडों के अनुसार वस्तुओं और सेवाओं के न्यूनतम स्वीकार्य सेट की खपत है, जो केवल मानव व्यवहार्यता को बनाए रखने की अनुमति देती है।

अगर रवैया आर निम्नलिखित गुण हैं: प्रतिवर्ती सममितीय सकर्मक, अर्थात्। सेट पर एक तुल्यता संबंध (~ या ≡ या ई) है एम , तो तुल्यता वर्गों के समुच्चय को समुच्चय का कारक समुच्चय कहा जाता है एम समतुल्यता के संबंध में आर और नामित किया गया है श्री

समुच्चय के तत्वों का एक उपसमुच्चय है एम समकक्ष एक्स , बुलाया तुल्यता वर्ग.

कारक समुच्चय की परिभाषा से यह निष्कर्ष निकलता है कि यह बूलियन का उपसमुच्चय है: .

फ़ंक्शन को कॉल किया जाता है पहचानऔर इसे इस प्रकार परिभाषित किया गया है:

प्रमेय.गुणनखंड बीजगणित एफ n /~ बूलियन फ़ंक्शंस के बीजगणित के लिए समरूपी है बीएन

सबूत.

आवश्यक समरूपता ξ : एफ एन / ~ → बी n निम्नलिखित नियम द्वारा निर्धारित किया जाता है: तुल्यता वर्ग ~(φ) फ़ंक्शन का मिलान किया गया है च φ , सेट से एक मनमाना सूत्र के लिए एक सत्य तालिका होना ~(φ) . चूंकि अलग-अलग तुल्यता वर्ग अलग-अलग सत्य तालिकाओं से मेल खाते हैं, इसलिए मैपिंग ξ इंजेक्शन, और चूँकि किसी भी बूलियन फ़ंक्शन के लिए एफ से पी में फ़ंक्शन का प्रतिनिधित्व करने वाला एक सूत्र है एफ, फिर मैपिंग ξ विशेषण. स्टोर संचालन, प्रदर्शित होने पर 0, 1 ξ सीधे जांच की जाती है. सीटीडी.

प्रत्येक फ़ंक्शन की कार्यात्मक पूर्णता पर प्रमेय के अनुसार जो स्थिर नहीं है 0 , कुछ SDNF से मेल खाता है ψ , वर्ग से संबंधित ~(φ) = ξ -1 (एफ) किसी फ़ंक्शन का प्रतिनिधित्व करने वाले सूत्र एफ . कक्षा में रहने की समस्या उत्पन्न होती है ~(φ) विघटनकारी सामान्य रूप, जिसकी संरचना सबसे सरल है।

काम का अंत -

यह विषय अनुभाग से संबंधित है:

अनुशासन पृथक गणित पर व्याख्यान का कोर्स

मॉस्को स्टेट यूनिवर्सिटी ऑफ सिविल इंजीनियरिंग.. इंस्टीट्यूट ऑफ मैनेजमेंट इकोनॉमिक्स एंड इंफॉर्मेशन सिस्टम्स इन कंस्ट्रक्शन.. आईईईई..

यदि आपको इस विषय पर अतिरिक्त सामग्री की आवश्यकता है, या आपको वह नहीं मिला जो आप खोज रहे थे, तो हम अपने कार्यों के डेटाबेस में खोज का उपयोग करने की सलाह देते हैं:

हम प्राप्त सामग्री का क्या करेंगे:

यदि यह सामग्री आपके लिए उपयोगी थी, तो आप इसे सोशल नेटवर्क पर अपने पेज पर सहेज सकते हैं:

करें

इस अनुभाग के सभी विषय:

असतत गणित का विषय
असतत (परिमित, परिमित) गणित का विषय गणित की एक शाखा है जो असतत संरचनाओं के गुणों का अध्ययन करती है, जबकि शास्त्रीय (निरंतर) गणित वस्तुओं के गुणों का अध्ययन करती है

समाकृतिकता
बीजगणितीय संक्रियाओं का अध्ययन करने वाले विज्ञान को बीजगणित कहा जाता है। जैसे-जैसे आप पाठ्यक्रम का अध्ययन करेंगे यह अवधारणा अधिक विशिष्ट और गहरी होती जाएगी। बीजगणित की रुचि केवल इस प्रश्न में है कि कैसे कार्य किया जाए

अभ्यास
1. साबित करें कि एक आइसोमोर्फिक मैपिंग हमेशा आइसोटोन होती है, और इसका विपरीत सत्य नहीं है। 2. अपने समूह को समुच्चय की भाषा में लिखें। 3. जो वस्तुएँ हैं उन्हें समुच्चय की भाषा में लिखिए

सेट और सेट के तत्व
वर्तमान में, मौजूदा सेट सिद्धांत वैचारिक आधार और तार्किक साधनों के प्रतिमान (विचारों की प्रणाली) में भिन्न हैं। इसलिए, उदाहरण के तौर पर, हम दो विपरीत बातों का हवाला दे सकते हैं

परिमित और अनंत समुच्चय
वह जिसमें सेट शामिल है, यानी। वे वस्तुएँ जो समुच्चय बनाती हैं, उसके तत्व कहलाती हैं। एक समुच्चय के तत्व एक दूसरे से भिन्न और विशिष्ट होते हैं। जैसा कि दिए गए उदाहरण से देखा जा सकता है

सेट की शक्ति
किसी परिमित समुच्चय की प्रमुखता उसके तत्वों की संख्या के बराबर होती है। उदाहरण के लिए, कार्डिनलिटी एन के सेट ए के ब्रह्मांड बी (ए) की कार्डिनैलिटी

A1A2A3| + … + |A1A2A3| + … + |A1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|
एक परिमित समुच्चय A में कार्डिनैलिटी k है यदि यह खंड 1.. k के बराबर है;:

उपसमुच्चय, उचित उपसमुच्चय
एक सेट की अवधारणा पेश किए जाने के बाद, मौजूदा सेटों से नए सेट बनाने का काम सामने आता है, यानी सेट पर संचालन को परिभाषित करना। एम का सेट",

सार्थक सेट सिद्धांतों की प्रतीकात्मक भाषा
पाठ्यक्रम का अध्ययन करने की प्रक्रिया में, हम सेट सिद्धांत की वस्तु भाषा और धातुभाषा के बीच अंतर करेंगे, जिसके माध्यम से वस्तु भाषा का अध्ययन किया जाता है। समुच्चय सिद्धांत की भाषा से हम रिलेशनल को समझते हैं

सबूत
समुच्चय B अनंत है, जिसका अर्थ है

तत्वों को जोड़ना और हटाना
यदि A एक समुच्चय है, और x एक तत्व है, और फिर तत्व

बंधे हुए सेट. सीमाओं का निर्धारण
मान लीजिए किसी समुच्चय X पर एक संख्यात्मक फलन f(x) दिया गया है। फलन f(x) की ऊपरी सीमा (सीमा) एक ऐसी संख्या है

सटीक ऊपरी (निचली) सीमा
सभी ऊपरी सीमाओं के समुच्चय E को Es द्वारा और सभी निचली सीमाओं को Ei द्वारा दर्शाया जाता है। यदि

सेट की सटीक ऊपरी (निचली) सीमा
यदि कोई तत्व z समुच्चय E और उसकी सभी ऊपरी सीमाओं के समुच्चय Es (क्रमशः निचला r) के प्रतिच्छेदन से संबंधित है

ऊपरी और निचली सीमाओं के मूल गुण
मान लीजिए कि X एक आंशिक रूप से ऑर्डर किया गया सेट है। 1. यदि, तो

गुणात्मक दृष्टिकोण से सेट करें
समग्र दृष्टिकोण, गुणात्मक दृष्टिकोण के विपरीत, इस अर्थ में तार्किक रूप से अस्थिर है कि यह रसेल और कैंटर के प्रकार के विरोधाभासों की ओर ले जाता है (नीचे देखें)। गुणात्मक टी के ढांचे के भीतर

संरचना
आंशिक रूप से क्रमित समुच्चय X को एक संरचना कहा जाता है यदि इसमें कोई दो-तत्व समुच्चय हो

कवरिंग और विभाजन सेट
समुच्चय A का विभाजन एक परिवार Ai है

द्विआधारी रिश्ते
लंबाई n का एक अनुक्रम, जिसके पद a1, .... an हैं, को (a1, .... a) द्वारा दर्शाया जाएगा

द्विआधारी संबंधों के गुण
समुच्चय Ho पर एक द्विआधारी संबंध R में निम्नलिखित गुण हैं: (ए) प्रतिवर्ती यदि xRx

त्रिगुट संबंध
कार्तीय उत्पाद XY

एन-एरी संबंध
दो सेट एक्स, वाई के कार्टेशियन उत्पाद के अनुरूप, हम कार्टेशियन उत्पाद एक्स का निर्माण कर सकते हैं

प्रदर्शित करता है
मैपिंग सेट के तत्वों के बीच कुछ कनेक्शन हैं। संबंधों का सबसे सरल उदाहरण सदस्यता x के संबंध हैं

पत्र-व्यवहार
कार्टेशियन उत्पाद के उपसमुच्चय S को समुच्चय Mi के तत्वों का n-ary पत्राचार कहा जाता है। औपचारिक रूप से

समारोह
असतत गणित की सभी शाखाएँ फ़ंक्शन की अवधारणा पर आधारित हैं। चलो एक्स -

संबंधों के संदर्भ में किसी फ़ंक्शन का प्रतिनिधित्व करना
एक द्विआधारी संबंध f को एक फ़ंक्शन कहा जाता है यदि से और

इंजेक्शन, प्रक्षेपण, आक्षेप
"मैपिंग" शब्द का उपयोग करते समय, मैपिंग XbY और मैपिंग X से Y के बीच एक अंतर किया जाता है

उलटा काम करना
मनमाने लोगों के लिए, हम परिभाषित करते हैं

आंशिक रूप से ऑर्डर किए गए सेट
एक सेट S को आंशिक रूप से ऑर्डर किया गया (PUM) कहा जाता है यदि इसे एक रिफ्लेक्टिव, ट्रांजिटिव और एंटीसिमेट्रिक बाइनरी आंशिक ऑर्डर संबंध दिया जाता है

प्रतिनिधित्व न्यूनीकरण सेट करें
इन कानूनों का उपयोग करते हुए, हम संचालन का उपयोग करके सेट एम के प्रतिनिधित्व को कम करने की समस्या पर विचार करते हैं

पुनर्व्यवस्था
एक समुच्चय A दिया गया है। माना A एक परिमित समुच्चय है जिसमें n तत्व A = (a1, a2, …, a) शामिल हैं।

दोहराव के साथ क्रमपरिवर्तन
मान लीजिए कि सेट A में समान (दोहराए जाने वाले) तत्व हैं। रचना की पुनरावृत्ति के साथ क्रमपरिवर्तन (n1, n2, … ,nk

प्लेसमेंट
लंबाई k (1≤k≤n) के टुपल्स, जिसमें एन-तत्व सेट ए के विभिन्न तत्व शामिल हैं (ट्यूपल्स अलग-अलग हैं)

दोहराव के साथ प्लेसमेंट
मान लीजिए कि सेट A में समान (दोहराए जाने वाले) तत्व हैं। K नामों के n तत्वों की पुनरावृत्ति के साथ प्लेसमेंट

व्यवस्थित प्लेसमेंट
आइए हम n वस्तुओं को m बक्सों में रखें ताकि प्रत्येक बक्से में एक अनुक्रम हो, न कि, पहले की तरह, उसमें रखी गई वस्तुओं का एक सेट हो। दो

युग्म
एम-तत्व सेट ए से हम लंबाई एन का एक क्रमबद्ध सेट बनाते हैं, जिसके तत्व समान विषयों के साथ व्यवस्था करते हैं

दोहराव के साथ संयोजन
परिणामी सूत्र केवल तभी मान्य होते हैं जब सेट ए में कोई समान तत्व नहीं होते हैं। मान लीजिए कि n प्रकार के तत्व हैं और उनमें से एक टुपल है

फ़ंक्शन उत्पन्न करने की विधि
इस पद्धति का उपयोग संयोजन संख्याओं की गणना करने और संयोजन पहचान स्थापित करने के लिए किया जाता है। प्रारंभिक बिंदु अनुक्रम (एआई) कॉम्बिनेटर है

बीजगणितीय प्रणाली
एक बीजगणितीय प्रणाली A एक संग्रह ‹M,O,R› है, जिसका पहला घटक M एक गैर-रिक्त सेट है, दूसरा घटक O एक सेट है

समापन और उपबीजगणित
कहा जाता है कि एक उपसमुच्चय को ऑपरेशन φ यदि के तहत बंद किया जाता है

एक बाइनरी ऑपरेशन के साथ बीजगणित
मान लीजिए समुच्चय M पर एक द्विआधारी संक्रिया दी गई है। आइए इसके द्वारा उत्पन्न बीजगणित पर विचार करें, लेकिन पहले हम बाइनरी ऑपरेशन के कुछ गुणों पर विचार करेंगे। बाइनरी ओ

समूहबद्ध
प्रपत्र का बीजगणित<М, f2>ग्रुपॉइड कहा जाता है। यदि f2 गुणन जैसा एक संक्रिया है (

पूर्णांक मॉड्यूलो एम
पूर्णांकों की एक अंगूठी दी गई है . आइए हम आपको याद दिला दें. बीजगणित<М,

सर्वांगसमताएँ
बीजगणित पर सर्वांगसमता A = (Σ - बीजगणित हस्ताक्षर में केवल फ़ंक्शन प्रतीक होते हैं) ऐसे तुल्यता संबंध को कहा जाता है

ग्राफ़ सिद्धांत के तत्व
ग्राफ़ गणितीय वस्तुएं हैं। ग्राफ सिद्धांत का उपयोग भौतिकी, रसायन विज्ञान, संचार सिद्धांत, कंप्यूटर डिजाइन, इलेक्ट्रिकल इंजीनियरिंग, मैकेनिकल इंजीनियरिंग, वास्तुकला, अनुसंधान जैसे क्षेत्रों में किया जाता है

ग्राफ़, शीर्ष, किनारा
एक अप्रत्यक्ष ग्राफ़ (या, संक्षेप में, एक ग्राफ़) से हमारा तात्पर्य ऐसी मनमानी जोड़ी G = से है , क्या

पत्र-व्यवहार
निर्देशित ग्राफ G का एक और, अधिक बार उपयोग किया जाने वाला विवरण, शीर्ष X के एक सेट और एक पत्राचार Г को निर्दिष्ट करना शामिल है, जिससे

अप्रत्यक्ष ग्राफ
यदि किनारों में कोई ओरिएंटेशन नहीं है, तो ग्राफ़ को अनडायरेक्टेड (अप्रत्यक्ष डुप्लिकेट या अनओरिएंटेड) कहा जाता है

घटना, मिश्रित ग्राफ
यदि किनारे e का रूप (u, v) या है<и, v>, तो हम कहेंगे कि किनारा ई घटना क्रिया है

उलटा मिलान
चूँकि यह ऐसे शीर्षों के एक समूह का प्रतिनिधित्व करता है

ग्राफ समरूपता
दो ग्राफ G1 = और G2 = समरूपी हैं (जी

पथ उन्मुख मार्ग
एक निर्देशित ग्राफ का पथ (या निर्देशित मार्ग) चापों का एक क्रम है जिसमें

आसन्न चाप, आसन्न शीर्ष, शीर्ष डिग्री
चाप a = (xi, xj), xi ≠ xj, उभयनिष्ठ अंत शीर्ष वाले, n

कनेक्टिविटी
किसी ग्राफ़ में दो शीर्षों को जुड़ा हुआ कहा जाता है यदि उन्हें जोड़ने वाला कोई सरल पथ हो। एक ग्राफ़ को जुड़ा हुआ कहा जाता है यदि उसके सभी शीर्ष जुड़े हुए हों। प्रमेय.

भारित चाप ग्राफ
एक ग्राफ G = (N, A) को भारित कहा जाता है यदि कुछ फ़ंक्शन l: A → R को चाप A के सेट पर इस प्रकार परिभाषित किया गया है कि

मजबूत कनेक्टिविटी मैट्रिक्स
मजबूत कनेक्टिविटी मैट्रिक्स: विकर्ण के साथ 1 रखें; पंक्ति X1 भरें - यदि शीर्ष X1 और X1 d से पहुंच योग्य है

पेड़
पेड़ न केवल इसलिए महत्वपूर्ण हैं क्योंकि उनका ज्ञान के विभिन्न क्षेत्रों में उपयोग होता है, बल्कि इसलिए भी कि ग्राफ सिद्धांत में उनका एक विशेष स्थान है। उत्तरार्द्ध पेड़ की संरचना की अत्यधिक सादगी के कारण होता है

किसी भी गैर-तुच्छ पेड़ में कम से कम दो लटकते हुए शिखर होते हैं
प्रमाण पेड़ G(V, E) पर विचार करें। इसलिए, पेड़ एक जुड़ा हुआ ग्राफ़ है

प्रमेय
एक स्वतंत्र पेड़ के केंद्र में एक शीर्ष या दो आसन्न शीर्ष होते हैं: Z(G) = 0&k(G) = 1 → C(G) = K1

निर्देशित, आदेशित और बाइनरी पेड़
निर्देशित (आदेशित) पेड़ पदानुक्रमित संबंधों का एक अमूर्त रूप हैं जो व्यावहारिक जीवन और गणित और प्रोग्रामिंग दोनों में अक्सर सामने आते हैं। वृक्ष (अभिविन्यास)

सबूत
1. प्रत्येक चाप किसी न किसी नोड में प्रवेश करता है। परिभाषा 9.2.1 के खंड 2 से हमारे पास है: v

पेड़ों का ऑर्डर दिया
ऑर्डरेव की समतुल्य परिभाषा में सेट T1,..., Tk उपवृक्ष हैं। यदि उपवृक्षों का सापेक्ष क्रम T1,...,

बाइनरी पेड़
एक बाइनरी (या बाइनरी) ट्री नोड्स का एक सीमित सेट है जो या तो खाली होता है या इसमें एक जड़ और दो असंयुक्त बाइनरी पेड़ होते हैं - बाएँ और दाएँ। बाइनरी ट्री जावा में नहीं है

निःशुल्क वृक्ष प्रतिनिधित्व
पेड़ों का प्रतिनिधित्व करने के लिए, आप सामान्य ग्राफ़ का प्रतिनिधित्व करने के लिए उन्हीं तकनीकों का उपयोग कर सकते हैं - आसन्नता और घटना मैट्रिक्स, आसन्नता सूचियाँ, और अन्य। लेकिन के विशेष गुणों का उपयोग करना

के लिए समाप्त करें
तर्क प्रुफ़र कोड वास्तव में एक निःशुल्क वृक्ष प्रतिनिधित्व है। इसे देखने के लिए, आइए हम दिखाते हैं कि यदि T" एक पेड़ है

बाइनरी पेड़ों का प्रतिनिधित्व
किसी भी मुक्त पेड़ को उसके किसी एक नोड को जड़ के रूप में नामित करके उन्मुख किया जा सकता है। कोई भी आदेश मनमाने ढंग से दिया जा सकता है। एक आदेशित क्रम के एक नोड (भाइयों) के वंशजों के लिए, इसे सापेक्ष परिभाषित किया गया है

बुनियादी तर्क कार्य
आइए हम दो संख्याओं से युक्त एक समुच्चय को E2 = (0, 1) से निरूपित करें। असतत मैट में संख्याएँ 0 और 1 मूल हैं

बूलियन फ़ंक्शन
n तर्क x1, x2,…,xn का एक बूलियन फ़ंक्शन सेट की nवीं शक्ति से एक फ़ंक्शन f है

दो-तत्व बूलियन बीजगणित
आइए सेट Во = (0,1) पर विचार करें और स्रोतों की तालिकाओं के अनुसार उस पर संचालन को परिभाषित करें

बूलियन फ़ंक्शन टेबल्स
n वेरिएबल्स का एक बूलियन फ़ंक्शन दो कॉलम और 2n पंक्तियों वाली तालिका द्वारा निर्दिष्ट किया जा सकता है। पहला कॉलम बी से सभी सेटों को सूचीबद्ध करता है

F5 - y में दोहराएँ
एफ6 - योग मॉड्यूलो 2 एफ7

कार्रवाई के आदेश
यदि किसी जटिल अभिव्यक्ति में कोई कोष्ठक नहीं हैं, तो संचालन निम्नलिखित क्रम में किया जाना चाहिए: संयोजन, विच्छेदन, निहितार्थ, तुल्यता, निषेध। शैनन के प्रथम प्रमेय की व्यवस्था के संबंध में कन्वेंशन
मूल सूत्र φ के समतुल्य SDNF और SCNF को खोजने की समस्या को हल करने के लिए, हम पहले बूलियन फ़ंक्शन f(x1, x2) के विस्तार पर विचार करते हैं

शैनन का दूसरा प्रमेय
द्वैत के सिद्धांत के आधार पर, प्रमेय 6.4.3 (शैनन का दूसरा प्रमेय) बूलियन बीजगणित के लिए लागू होता है। कोई भी बूलियन फ़ंक्शन f(x1, x2,...

कार्यात्मक पूर्णता
प्रमेय (कार्यात्मक पूर्णता के बारे में)। किसी भी बूलियन फ़ंक्शन f के लिए फ़ंक्शन f का प्रतिनिधित्व करने वाला एक सूत्र φ है

एसडीएनएफ खोजने के लिए एल्गोरिदम
एसडीएनएफ को खोजने के लिए, इस सूत्र को पहले डीएनएफ में घटाया जाना चाहिए, और फिर निम्नलिखित क्रियाओं का उपयोग करके इसके संयोजनों को इकाई के घटकों में बदलना होगा: ए) यदि संयोजन में कुछ शामिल हैं

क्विन की विधि
किसी दिए गए बूलियन फ़ंक्शन का प्रतिनिधित्व करने वाले एमडीएनएफ को खोजने के लिए क्विन की विधि पर विचार करें। आइए हम निम्नलिखित तीन ऑपरेशनों को परिभाषित करें: - संपूर्ण ग्लूइंग ऑपरेशन -

तार्किक कार्यों का विहित प्रतिनिधित्व
तार्किक (सूत्र) फ़ंक्शंस के विहित रूप वे अभिव्यक्तियाँ हैं जिनमें बूलियन सूत्र का मानक रूप होता है जैसे कि यह विशिष्ट रूप से एक तार्किक फ़ंक्शन का प्रतिनिधित्व करता है। बीजगणित में

बूलियन फ़ंक्शन सिस्टम
मान लीजिए बूलियन फलन f(g1, g2, …, gm) और g1(x1, x2, …, xn), g2(x1)

ज़ेगलकिन आधार
आइए इसे आज़माएं। आइए सिस्टम को देखें। यह पूर्ण है, क्योंकि मानक आधार से कोई भी फ़ंक्शन शब्दों में व्यक्त किया जाता है

पोस्ट का प्रमेय
पोस्ट का प्रमेय बूलियन कार्यों की एक प्रणाली की पूर्णता के लिए आवश्यक और पर्याप्त शर्तें स्थापित करता है। (पोस्ट ई.एल. गणितीय तर्क की दो-मूल्यवान इंटरैक्टिव प्रणालियाँ। - एनल्स ऑफ मैथ। स्टु

सबूत
आवश्यकता. विपरीत से. जाने भी दो

ज़ेगलकिन बीजगणित
योग मॉड्यूलो 2, संयोजन और स्थिरांक 0 और 1 एक कार्यात्मक रूप से पूर्ण प्रणाली बनाते हैं, अर्थात। एक बीजगणित बनाएं - ज़ेगल्किन बीजगणित। ए=

मक तर्क
गणितीय तर्क प्राकृतिक भाषा के वाक्यविन्यास (रूप) और शब्दार्थ (सामग्री) की बुनियादी अवधारणाओं का अध्ययन करता है। आइए गणितीय तर्क में अनुसंधान के तीन प्रमुख क्षेत्रों पर विचार करें - तर्क

विधेय की परिभाषा
मान लीजिए कि X1, X2, ..., Xn मनमाना चर हैं। इन चरों को हम विषय चर कहेंगे। वेरिएबल को आपको सेट करने दें

बीजगणित में विधेय का अनुप्रयोग
आइए उन विधेय पर विचार करें जिनमें केवल एक चर मुक्त है, जिसे हम x द्वारा निरूपित करते हैं, और बीजगणित में विधेय के उपयोग पर चर्चा करते हैं। एक विशिष्ट उदाहरण

बूलियन विधेय बीजगणित
चूँकि तार्किक संक्रियाओं को विधेय पर लागू किया जा सकता है, बूलियन बीजगणित के बुनियादी नियम उनके लिए मान्य हैं। प्रमेय. (विधेय के लिए तार्किक संचालन के गुण)। एम.एन.

F↔G=(F→G)(G→F), F→G=नहीं FG
2. कानून का प्रयोग करें न कि एफ=एफ, डी मॉर्गन के कानून: नहीं (एफ)।

विधेय कलन
विधेय कलन को प्रथम-क्रम सिद्धांत भी कहा जाता है। विधेय कलन में, साथ ही प्रस्तावित कलन में, पहला सबसे महत्वपूर्ण स्थान सॉल्वैबिलिटी की समस्या है।

अनुसरण एवं समतुल्यता
यदि निहितार्थ Q1→Q2 सत्य हो जाता है तो प्रस्तावात्मक प्रपत्र Q2, प्रस्तावात्मक प्रपत्र Q1 से अनुसरण करता है

स्वीकृत नोटेशन
"अब और ऑर्डर न करें" के प्रतीक। दो फ़ंक्शन f(n) और g(n) (गैर-नकारात्मक मानों के साथ) की वृद्धि दर की तुलना करते समय, निम्नलिखित बहुत सुविधाजनक हैं

मेटा पदनाम
प्रतीक सामग्री उदाहरण या

निम्नलिखित प्रमेय सिद्ध किये जा सकते हैं।

प्रमेय 1.4. एक फलन f का व्युत्क्रम फलन f -1 है यदि और केवल यदि f विशेषण है।

प्रमेय 1.5. विशेषण फलनों की संरचना एक विशेषण फलन है।

चावल। 1.12 विभिन्न संबंधों को दर्शाता है, पहले वाले को छोड़कर सभी, कार्य हैं।

रवैया, लेकिन

इंजेक्शन, लेकिन

आपत्ति, लेकिन

कोई फ़ंक्शन नहीं

कोई अनुमान नहीं

कोई इंजेक्शन नहीं

मान लीजिए कि f : A→B एक फलन है, और समुच्चय A और B परिमित समुच्चय हैं, आइए हम A = n, B = m रखें। डिरिचलेट का सिद्धांत कहता है कि यदि n > m, तो f का कम से कम एक मान एक से अधिक बार आता है। दूसरे शब्दों में, तत्वों की एक जोड़ी है a i ≠ a j , a i , a j A जिसके लिए f(a i )= f(a j ) है।

डिरिचलेट के सिद्धांत को सिद्ध करना आसान है, इसलिए हम इसे एक तुच्छ अभ्यास के रूप में पाठक पर छोड़ देते हैं। आइए एक उदाहरण देखें. मान लीजिए कि एक समूह में 12 से अधिक छात्र हैं। तो यह स्पष्ट है कि उनमें से कम से कम दो का जन्मदिन एक ही महीने में है।

§ 7. तुल्यता संबंध. कारक - समुच्चय

समुच्चय A पर एक द्विआधारी संबंध R को तुल्यता संबंध कहा जाता है यदि R प्रतिवर्ती, सममित और सकर्मक है।

संख्याओं के समूह पर एक समानता संबंध में संकेतित गुण होते हैं, और इसलिए यह एक तुल्यता संबंध है।

त्रिभुज समानता संबंध स्पष्ट रूप से एक तुल्यता संबंध है।

वास्तविक संख्याओं के सेट पर गैर-सख्त असमानता संबंध (≤) एक तुल्यता संबंध नहीं होगा, क्योंकि यह सममित नहीं है: 3≤ 5 से यह 5≤ 3 का पालन नहीं करता है।

किसी दिए गए समतुल्य संबंध आर के लिए तत्व ए द्वारा उत्पन्न समतुल्य वर्ग (कोसेट) उन एक्स ए का उपसमुच्चय है जो ए के साथ संबंध आर में हैं। संकेतित तुल्यता वर्ग को [a]R द्वारा निरूपित किया जाता है, इसलिए, हमारे पास है:

[ए] आर = (एक्स ए: ए, एक्स आर)।

आइए एक उदाहरण देखें. त्रिभुजों के सेट पर एक समानता संबंध प्रस्तुत किया गया है। यह स्पष्ट है कि सभी समबाहु त्रिभुज एक कोसेट में आते हैं, क्योंकि उनमें से प्रत्येक समान है, उदाहरण के लिए, एक त्रिभुज के, जिसकी सभी भुजाओं की लंबाई इकाई है।

प्रमेय 1.6. मान लीजिए R समुच्चय A और [a] R एक सहसमुच्चय पर एक तुल्यता संबंध है, अर्थात। [ए] आर = (एक्स ए: ए, एक्स आर), फिर:

1) किसी भी ए ए के लिए: [ए] आर ≠, विशेष रूप से, ए [ए] आर;

2) विभिन्न सहसमुच्चय प्रतिच्छेद नहीं करते;

3) सभी सहसमुच्चय का मिलन संपूर्ण समुच्चय A से मेल खाता है;

4) विभिन्न सहसमुच्चय का एक समुच्चय समुच्चय A का एक विभाजन बनाता है।

सबूत। 1) R की प्रतिवर्तीता के कारण, हम पाते हैं कि किसी भी a, a A के लिए, हमारे पास a,a R है, इसलिए a [ a] R और [ a] R ≠ ;

2) आइए मान लें कि [ ए] आर ∩ [बी] आर ≠ , यानी। A और c का एक तत्व c है [a]R ∩ [b]R। फिर (cRa)&(cRb) से R की समरूपता के कारण हमें वह (aR c)&(cRb) प्राप्त होता है, और R की परिवर्तनशीलता से हमें aRb मिलता है।

किसी भी x [a] R के लिए हमारे पास है: (xRa)&(aRb), तो R की परिवर्तनशीलता के कारण हमें xRb प्राप्त होता है, अर्थात। एक्स [बी] आर, इसलिए [ए] आर [बी] आर। इसी प्रकार, किसी भी y, y [b] R के लिए, हमारे पास है: (yRb)&(aRb), और R की समरूपता के कारण हम प्राप्त करते हैं कि (yRb)&(bR a), फिर, R की परिवर्तनशीलता के कारण , हमें वह प्राप्त होता है yR a , अर्थात। वाई [ए]आर और

इसलिए [बी] आर [ए] आर। [ a ] ​​​​R [ b ] R और [ b ] R [ a ] ​​​​R से हम प्राप्त करते हैं [ a ] ​​​​ R = [ b ] R , अर्थात, यदि सहसमुच्चय प्रतिच्छेद करते हैं, तो वे संपाती होते हैं;

3) किसी भी ए, ए ए के लिए, जैसा कि सिद्ध है, हमारे पास एक [ए] आर है, तो, जाहिर है, सभी कोसेट का मिलन सेट ए के साथ मेल खाता है।

प्रमेय 1.6 का कथन 4) 1)-3) से अनुसरण करता है। प्रमेय सिद्ध हो चुका है। निम्नलिखित प्रमेय को सिद्ध किया जा सकता है।

प्रमेय 1.7. सेट ए पर विभिन्न तुल्यता संबंध ए के विभिन्न विभाजन उत्पन्न करते हैं।

प्रमेय 1.8. सेट ए का प्रत्येक विभाजन सेट ए पर एक समतुल्य संबंध उत्पन्न करता है, और विभिन्न विभाजन अलग-अलग समतुल्य संबंध उत्पन्न करते हैं।

सबूत। मान लीजिए कि समुच्चय A का एक विभाजन B = (B i ) दिया गया है। आइए संबंध R को परिभाषित करें: a,b R यदि और केवल यदि कोई B i मौजूद है जैसे कि a और b दोनों इस B i से संबंधित हैं। यह स्पष्ट है कि प्रस्तुत संबंध प्रतिवर्ती, सममित और सकर्मक है, इसलिए, आर एक तुल्यता संबंध है। यह दिखाया जा सकता है कि यदि विभाजन अलग-अलग हैं, तो उनके द्वारा उत्पन्न तुल्यता संबंध भी अलग-अलग हैं।

किसी दिए गए तुल्यता संबंध R के संबंध में समुच्चय A के सभी सहसमुच्चयों के समुच्चय को कारक समुच्चय कहा जाता है और इसे A/R द्वारा निरूपित किया जाता है। कारक समुच्चय के तत्व सहसमुच्चय होते हैं। कोसेट वर्ग [ए]आर, जैसा कि ज्ञात है, इसमें तत्व ए शामिल हैं जो एक दूसरे आर के संबंध में हैं।

आइए पूर्णांक Z = (..., -3, -2, -1, 0, 1, 2, 3, ...) के सेट पर एक तुल्यता संबंध के उदाहरण पर विचार करें।

दो पूर्णांक a और b को तुलनीय (सर्वांगसम) मॉड्यूलो m कहा जाता है यदि m संख्या a-b का विभाजक है, अर्थात यदि हमारे पास है:

a=b+km , k=…, -3, -2, -1, 0, 1, 2, 3, ….

इस स्थिति में, a≡ b(mod m) लिखें।

प्रमेय 1.9. किसी भी संख्या a, b, c और m>0 के लिए हमारे पास है:

1) ए ≡ ए(मॉड एम) ;

2) यदि a ≡ b(mod m), तो b ≡ a(mod m);

3) यदि a ≡ b(mod m) और b ≡ c(mod m), तो a ≡ c(mod m)।

सबूत। कथन 1) और 2) स्पष्ट हैं। आइए सिद्ध करें 3). मान लीजिए a=b+k 1 m, b=c+k 2 m, फिर a=c+(k 1 +k 2)m, यानी। ए ≡ सी(मॉड एम) . प्रमेय सिद्ध हो चुका है।

इस प्रकार, तुलनीयता संबंध मॉड्यूलो एम एक तुल्यता संबंध है और पूर्णांकों के सेट को संख्याओं के असंयुक्त वर्गों में विभाजित करता है।

आइए एक अंतहीन खुलने वाला सर्पिल बनाएं, जिसे चित्र में दिखाया गया है। 1.13 को एक ठोस रेखा के रूप में दिखाया गया है, और एक अंतहीन घुमाव वाले सर्पिल को धराशायी रेखा के रूप में दिखाया गया है। मान लीजिए कि एक गैर-ऋणात्मक पूर्णांक m दिया गया है। हम सभी पूर्णांकों (सेट Z से तत्वों) को m किरणों के साथ इन सर्पिलों के प्रतिच्छेदन बिंदुओं पर रखेंगे, जैसा कि चित्र में दिखाया गया है। 1.13.

तुलनीयता संबंध मॉड्यूलो एम (विशेष रूप से, एम = 8 के लिए) के लिए, समतुल्यता वर्ग किरण पर पड़ी संख्याएं हैं। जाहिर है, प्रत्येक संख्या एक और केवल एक ही वर्ग में आती है। यह प्राप्त किया जा सकता है कि m= 8 के लिए हमारे पास है:

[ 0] ={…, -8, 0, 8, 16, …};
[ 1] ={…, -7, 1, 9, 17, …};
[ 2] ={…, -6, 2, 10, 18, …};
[ 7] ={…, -9, -1, 7, 15, …}.

तुलना संबंध मॉड्यूलो m के संबंध में सेट Z का कारक सेट Z/m या Z m के रूप में दर्शाया गया है। विचाराधीन मामले के लिए एम =8

हम पाते हैं कि Z/8 = Z8 = ( , , , …, ) .

प्रमेय 1.10. किसी भी पूर्णांक a, b, a*, b*, k और m के लिए:

1) यदि a ≡ b(mod m), तो ka ≡ kb(mod m);

2) यदि a ≡ b(mod m) और a* ≡ b* (mod m), तो:

ए) ए+ए * ≡ बी+बी* (मॉड एम); बी) आ * ≡ बीबी* (मॉड एम)।

हम केस 2बी के लिए प्रमाण प्रस्तुत करते हैं)। मान लीजिए a ≡ b(mod m) और a * ≡ b * (mod m), फिर a=b+sm और a * =b * +tm कुछ पूर्णांक s और t के लिए। गुणा

हमें मिलता है: aa* =bb* + btm+ b* sm+ stm2 =bb* +(bt+ b* s+ stm)m। इस तरह,

आ* ≡ बीबी* (मॉड एम)।

इस प्रकार, मॉड्यूलो तुलनाओं को जोड़ा जा सकता है और पद दर पद गुणा किया जा सकता है, अर्थात। समानता के समान ही कार्य करें। उदाहरण के लिए,