भाग 4. अतुल्यकालिक समानांतर प्रक्रियाओं के लिए तार्किक कार्यों की गणना के लिए एक ग्राफ मॉडल

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

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

परिभाषा 1. वह घटना जिसमें चाप प्रवेश करता है, उस घटना का परिणाम है जिसमें से यह चाप बाहर निकलता है। इसके विपरीत, जिस घटना से चाप निकलता है वह उस घटना का कारण है जिसमें यह चाप प्रवेश करता है।

परिभाषा 2. एक पथ - घटनाओं का एक अंतहीन अनुक्रम - एक ग्राफ के लेबलिंग में परिवर्तन का परिणाम, एक विशिष्ट के साथ शुरू करना। प्रत्येक घटना क्रम में अनंत बार प्रवेश करती है। ऐसी प्रत्येक प्रविष्टि अद्वितीय है।

परिभाषा 3. ईवेंट A का ट्रेस वह पथ है जिसमें सभी ईवेंट्स इवेंट A के प्रत्यक्ष परिणाम हैं, या ईवेंट के संबंध में ईवेंट के परिणाम के संबंध के सकर्मक समापन का परिणाम है। घटना A के ट्रेस के लिए प्रारंभिक अंकन निम्नानुसार स्थापित किया गया है। यदि अंकन को मनमाने ढंग से बदल दिया जाता है, तो घटना A के ट्रिगर होने के बाद, घटना A के आउटपुट आर्क्स में मार्कर ठीक हो जाते हैं। तब बाकी मार्कर तब तक चले जाते हैं जब तक मार्करों की गति घटना ए के आउटपुट आर्क में मार्कर को जारी किए बिना असंभव हो जाती है। परिणामस्वरूप अंकन घटना ए के निशान के लिए प्रारंभिक अंकन है।

परिभाषा 4. हम तीन घटनाओं (ए, बी, सी) के लिए ऑर्डरिंग रिलेशन को पेश करते हैं। तीन घटनाओं का आदेश दिया जाता है (लिखित ए> बी> सी) यदि और केवल यदि, घटना ए के किसी भी निशान के लिए, अनुक्रम बी में घटना बी की पहली घटना हमेशा घटना सी की पहली घटना से पहले घटित होगी।

नोट। ईवेंट A, B और C (या केवल C) दोनों घटनाओं के समानांतर हो सकता है, या A और B दोनों घटनाएँ C के समानांतर हो सकती हैं।

आदेश दिए गए इवेंट A, B, और C के लिए स्थान विकल्प (A> B> C)।



परिभाषा 5. सिग्नल बी (स्विचिंग बी 1 और बी 2) घटनाओं एक्स और वाई (घटनाओं एक्स और वाई समानांतर या संयोग हैं) के संबंध में संकेत ए (स्विचिंग ए 1 और ए 2) उठाता है यदि निम्न स्थितियां संतुष्ट हैं:

1) एक्स> ए 1> ए 2;
2) यदि घटना A2, घटना X के समानांतर है और घटना Y के समानांतर नहीं है, तो X> A2> Y;
3) वाई> बी 1> बी 2;
4) अगर ईवेंट बी, इवेंट वाई के समानांतर है और ईवेंट एक्स के समानांतर नहीं है, तो वाई> बी 2> एक्स;
5) वाई> बी 1> ए 2;
6) यदि घटना A2, घटना Y के समानांतर है और घटना X के समानांतर नहीं है, तो Y> A2> X है।



टिप्पणी 1. शर्तें 1, 2, और 3, 4 क्रमशः संकेतों ए और बी के स्विचिंग के क्रम को निर्धारित करती हैं। शर्तें 5, 6 कैच ईवेंट B1 और कैच ईवेंट A2 का क्रम निर्दिष्ट करें।

टिप्पणी 2. इवेंट X इवेंट A1 हो सकता है। इस स्थिति में, स्थिति 1 और 2 पतित हो जाती है।

टिप्पणी 3. इवेंट Y इवेंट B1 हो सकता है। इस स्थिति में, स्थिति 3, 4 और 5 पतित होते हैं।

रिमार्क 4. इवेंट X इवेंट A1 हो सकता है, और इवेंट B1 भी इवेंट Y हो सकता है। इस स्थिति में, स्थिति 1, 2, 3, 4 और 5 पतित होते हैं।

अब हम विचार करना शुरू करते हैं कि प्रत्यारोपण क्या है। इम्प्लिकेंट को घटनाओं की विशेषता है, जिसके परिणामस्वरूप इम्प्लिकेंट इसका अर्थ बदल देता है।

परिभाषा 6. एक घटना, जिसके परिणामस्वरूप इम्प्लिकेंट (OR) 1 (0) से 0 (1) में अपना मान बदलता है, हम इम्प्लिकेंट की सही सीमा कहेंगे। इस घटना के अनुरूप सिग्नल को स्विचिंग कहा जाएगा। अन्तर्ग्रही चालू हो जाता है।

परिभाषा 7. एक घटना, जिसके परिणामस्वरूप इम्प्लिकेंट (OR) 0 (1) से 1 (0) में अपना मान बदलता है, हम इम्प्लिकेंट की लेफ्ट बॉर्डर कहेंगे। इस घटना के अनुरूप सिग्नल को बंद कर दिया जाएगा। अन्तर्ग्रही बंद हो जाता है।

परिभाषा 8. एक ऐसी अव्यवस्था जिसमें कोई दो दाएं (या कोई भी दो बाएं) की सीमाएं एक दूसरे के समानांतर नहीं होती हैं उन्हें बंद कहा जाएगा।

अभी के लिए, हम बाधित प्रत्यारोपण पर विचार नहीं करेंगे। हम नीचे उनके विचार पर लौटेंगे।

तो, हमारे पास: निहितार्थों की सभी दाहिनी सीमाएं एक दूसरे के समानांतर जोड़ीदार हैं, साथ ही प्रत्यारोपण की बाईं सीमाएं एक दूसरे के समानांतर जोड़ीदार हैं।

एक महत्वपूर्ण संपत्ति। कम से कम एक घटना होने पर, जो कि इम्प्लिकेंट की सही सीमा है, पर इम्प्लिकेंट चालू होता है। इम्प्लिकेंट तभी बंद होता है जब सभी ईवेंट्स जो इम्प्लिकेंट की लेफ्ट बाउंड्रीज हैं

अब यह प्रत्यारोपण बनाने वाले संकेतों के गुणों की पहचान करने के लिए बनी हुई है।

परिभाषा 9. प्रत्यारोपण में शामिल संकेत को एक चर कहा जाएगा।

चरों की पहली संपत्ति। संकेतों को चालू और बंद करना परिवर्तनशील है।

चरों की दूसरी संपत्ति। किसी भी स्विचिंग वैरिएबल के लिए (जिसका एक स्विच इम्प्लिकेंट L की बाईं बॉर्डर है, दूसरा कुछ ईवेंट X है), एक ईवेंट होना चाहिए - उसी इम्प्लिकेंट का कुछ राईट बॉर्डर R ऐसा है कि X और R एक ही ईवेंट हैं, या R > एक्स> एल।

चर की तीसरी संपत्ति। किसी भी समावेशी चर के लिए (जिनके स्विच इपीसिएंट R की दाहिनी सीमा है, दूसरा कुछ ईवेंट X है), एक ईवेंट होना चाहिए - उसी इम्प्लिकेंट की कुछ लेफ्ट बॉर्डर L ऐसी है, जिसमें X और L एक ही ईवेंट हैं, या R > एक्स> एल।

चरों की चौथी संपत्ति। किसी भी वैरिएबल (X1 और X2 को स्विच करने पर) जो चालू या बंद नहीं हो रहा है, दो इवेंट होने चाहिए: इम्प्लिकेंट L की कुछ लेफ्ट बॉर्डर और कुछ इम्प्लिकेंट R की राइट बॉर्डर जैसे कि R> X1> L और R> X2) L । अन्यथा, प्रत्यारोपण बंद स्थिति में एक निरंतर मूल्य को बनाए नहीं रख सकता है।

चरों की पाँचवी संपत्ति। किसी भी जोड़ी के लिए: कुछ स्विचिंग वैरिएबल और कुछ स्विचिंग वैरिएबल, वैरिएबल के कुछ सही बॉर्डर्स के लिए एक-दूसरे को लेने वाले वेरिएबल का एक क्रम होना चाहिए (अलग-अलग पिकअप के लिए, सही बॉर्डर्स अलग-अलग हो सकते हैं), इस स्विचिंग वेरिएबल के साथ शुरू होता है और इस स्विचिंग वेरिएबल के साथ समाप्त होता है । अन्यथा, इम्प्लिकेंट ऑन पोजीशन में निरंतर मान नहीं रख पाता।

चर की छठी संपत्ति। किसी भी समावेशी चर a के लिए, यदि आवेषण की सही सीमा घटना a ((a)) है, तो इस तरह के चर को उलट के साथ implicant AND (OR) के रिकॉर्ड में शामिल किया जाता है, और बिना व्युत्क्रम के (या) के रिकॉर्ड में। किसी भी स्विचिंग वैरिएबल a के लिए, यदि इम्प्लिकेंट की बाईं बॉर्डर एक- (+ ए) घटना है, तो इस तरह के वेरिएबल को आवेषण के साथ (या) उलटा के साथ और इंप्लिकेंट के रिकॉर्ड में (और) को उलटा किए बिना शामिल किया जाता है।

चरों की सातवीं संपत्ति। चर की चौथी संपत्ति के आधार पर, प्रत्येक चर के लिए जो चालू या बंद नहीं होता है, गर्भनिरोधक आर के लिए एक सही सीमा होती है और प्रत्यारोपण के लिए बाईं ओर सीमा होती है जैसे कि आर> ए +> एल और आर> ए-> एल। यदि R> a +> a- है, तो इस तरह का एक वैरिएबल, और उलटा के साथ, और उलटा के बिना या का प्रत्यारोपण करता है। यदि R> a-> a + है, तो ऐसा वैरिएबल इम्प्लिकेंट और बिना इनवर्जन के प्रवेश करता है, और इम्प्लिकेंट या उलटा।

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

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

अब हम विचार करेंगे कि कैसे एक तार्किक कार्य का सामान्य रूप इम्प्लिकेंट से बनाया गया है।

परिभाषा 10. अगर किसी राज्य के लिए इम्प्लिकेंट ऑफ पोजीशन में है (इम्प्लांट और (OR) का मान 1 (0)) है, तो हम कहते हैं कि इम्प्लिकेंट इस अवस्था को कवर करता है।

एक निश्चित सिग्नल x पर विचार करें, जिसके लिए हमें तार्किक फ़ंक्शन की गणना करने की आवश्यकता है। DNF (CNF) के निर्माण के लिए, AND (OR) -implicants उन सभी राज्यों को कवर करना आवश्यक है जिन पर फ़ंक्शन x 1 (0) है। इस मामले में, यह आवश्यक है कि इनमें से कोई भी (या) -implicants यह नहीं बताता है कि फ़ंक्शन x 0 (1) है। साथ ही, तार्किक कार्यों की गणना करते समय, सर्किटरी की बारीकियों को ध्यान में रखना आवश्यक है: प्रत्यारोपण को "ओवरलैप" करना चाहिए। यही है, अगर किसी राज्य में इम्प्लिकेंट चालू हो सकता है (यानी ऐसी घटना जो इस इम्प्लिकेंट की सही सीमा को ट्रिगर कर सकती है) और सिग्नल फंक्शन x का मान इस स्विचिंग के दौरान नहीं बदलता है, तो इस स्टेट को कवर करने वाला एक और इम्प्लिकेंट होना चाहिए। जब यह घटना चालू हो जाती है तो चालू नहीं होता है।

अब हमें तीन प्रश्नों को स्पष्ट करने की आवश्यकता है। ग्राफ के मामले में क्या है? उन राज्यों को कैसे निर्धारित किया जाए जिन पर सिग्नल फ़ंक्शन x 1 (0) है? इम्प्लांट को शामिल करने वाली स्थितियों का निर्धारण कैसे करें?

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

परिभाषा 11. एक चिह्नित चाप को दर्शाती घटनाओं की एक जोड़ी को {P, S} लिखा जाएगा, जहां P कारण घटना है, और S परिणाम घटना है।

परिभाषा 12. MM को ऑर्डर किए गए जोड़े {P, S} का सेट कहा जाएगा, जो कुछ प्राप्य स्थिति का वर्णन करता है।

अब हम यह निर्धारित करते हैं कि फ़ंक्शन x का मान 1 है, और जिसके लिए यह 0. है। इवेंट x + को n इवेंट A1, A2, ..., An, और इवेंट x- के कारण m इवेंट B1, B2, ..., के कारण दें। BM।

फ़ंक्शन x का मान 1 है यदि:

या 1) प्रत्येक के लिए 1 से n तक, जोड़ी {ऐ, एक्स +} सेट MM से संबंधित है;
या 2) एक जोड़ी {x +, S} ऐसी कि x +> S> x- सेट MM से संबंधित है;
या 3) एक जोड़ी {P, S} ऐसी कि x +> P> x- और x +> S> x- सेट MM से संबंधित है;
या 4) एक जोड़ी {P, x-} ऐसी कि x +> P> x- सेट MM से संबंधित है और वहाँ मैं 1 से m ऐसी मौजूद हूं कि जोड़ी {Bi, x-} सेट MM से संबंधित नहीं है।

फ़ंक्शन x का मान 0 है यदि:

या 1) प्रत्येक के लिए 1 से मी तक, जोड़ी {द्वि, x-} सेट MM से संबंधित है;
या 2) एक जोड़ी {x-, S} ऐसी कि x-> S> x + सेट MM से संबंधित है;
या 3) एक जोड़ी {P, S} ऐसी कि x-> P> x + और x-> S> x + सेट MM से संबंधित है;
या 4) एक जोड़ी {P, x +} ऐसी है कि x-> P> x + सेट MM से संबंधित है और वहाँ 1 से n तक मौजूद है, जो कि जोड़ी {Ai, x +} सेट MM से संबंधित नहीं है।

अब हमें पता चलता है कि इम्प्लांट किन परिस्थितियों में शामिल है। बता दें कि इम्प्लिकेंट की n लेफ्ट बाउंड्री L1, L2, ..., Ln और m राइट बाउंड्रीज R1, R2, ..., Rm है।

यदि एमएम सेट द्वारा वर्णित राज्य को कवर नहीं करता है, तो यदि एमएम सेट से संबंधित कम से कम एक जोड़ी {पी, एस} निम्न स्थिति को संतुष्ट करता है: तो 1 से n तक मौजूद है और 1 से एम तक j ऐसा है कि

या तो 1) Li और S एक ही घटना है और Rj> P> Li,
या 2) Rj और P एक ही घटना है और Rj> S> Li,
या 3) आरजे> पी> ली और आरजे> एस> ली।

यह कथन चर की पांचवीं संपत्ति के आधार पर सच है।

समसामयिक सेट एमएम द्वारा वर्णित राज्य को कवर करता है यदि कोई भी जोड़े के लिए {P, S} सेट MM से संबंधित है तो निम्न स्थिति संतुष्ट है: वहाँ 1 से n और j से 1 से m तक मौजूद है

या तो 1) Li और S एक ही घटना है और Rj> P> Li,
या 2) Rj और P एक ही घटना है और Rj> S> Li,
या 3) आरजे> पी> ली और आरजे> एस> ली।

यह कथन चर के दूसरे, तीसरे और चौथे गुण के आधार पर सही है।

आंकिक रूप से कहा जाए तो, एक इम्प्लिकेंट राज्य को कवर करता है यदि सभी मार्कर इम्प्लांटिक की बाईं और दाईं सीमाओं के बीच होते हैं। यदि कम से कम एक मार्कर इन सीमाओं के बाहर स्थित है, तो प्रत्यारोपण इस राज्य को कवर नहीं करता है।

अब हमारे पास सामान्य रूपों की गणना के लिए एक उपकरण है (यह अभी भी स्पष्ट नहीं है, हालांकि, आंतरायिक प्रत्यारोपण के साथ एक सवाल अभी भी है)। लेकिन हम न्यूनतम सामान्य रूपों (सर्किट्री की बारीकियों को ध्यान में रखते हुए) में रुचि रखते हैं। आगे बढ़ने से पहले, आइए हम रुक-रुक कर होने वाले प्रभाव पर विचार करें। DNF सिग्नल x के लिए I-इम्प्लिकेंट पर विचार करें (CNF के लिए OR-इम्प्लिकेंट के साथ मामला समान है)। मान लीजिए कि समान प्रत्यारोपण L1 और L2 की दो बाईं सीमाएं एक-दूसरे के समानांतर नहीं हैं और L1> L2> x- (दो दाईं सीमाओं के मामले को समान माना जाता है)। तब निहितार्थ R1 और R2 की दो सही सीमाएँ होनी चाहिए जैसे कि L1 और R2 दोनों की जोड़ी के लिए, और L2 और R1, चर की दूसरी, तीसरी, चौथी और पाँचवीं संपत्तियों को संतुष्ट करना होगा। यदि L1 के समानांतर एक बाएं सीमा L3 है, तो L3 और R2 जोड़ी के लिए उपरोक्त गुणों को भी पूरा करना होगा (इसी तरह, संबंधित सीमाओं के अस्तित्व के मामले में, प्रत्यारोपण जो सीमाओं L2, R1 और R2 के समानांतर हैं)। लेकिन, चूंकि कई संकेतों का उपयोग नहीं किया जाता है, इसलिए सीमाओं L1 और R2 (और समानांतर संगत सीमाओं के साथ, अगर किसी भी बाधित प्रत्यारोपण के पास था) के साथ एक गैर-विच्छेदन अव्यवस्थित होना चाहिए। इसके अलावा, गैर-डिसकंटेंट इम्पिकेंट में कम वैरिएबल होते हैं और डिसकंटेंट इम्प्लिकेंट द्वारा कवर किए गए सभी स्टेट्स को कवर करते हैं, जिस पर सिग्नल फंक्शन x का वैल्यू 1. होता है। इसलिए निष्कर्ष: डिसकंटेंट इम्प्लिकेंट एक्सट्रीम नहीं होते हैं और इनका इस्तेमाल न्यूनतम फंक्शन्स को कैलकुलेट करने के लिए नहीं किया जा सकता है।

अगले भाग में न्यूनतम कार्यों की गणना पर अधिक।