Tseytin transformation
त्साइटिन परिवर्तन, जिसे वैकल्पिक रूप से त्साइटिन परिवर्तन लिखा जाता है, एक मनमाना संयोजन तर्क परिपथ को इनपुट के रूप में लेता है और संयुग्म सामान्य रूप (सी. एन. एफ.) में एक सम-संतोषजनक बूलियन सूत्र का उत्पादन करता है। सूत्र की लंबाई परिपथ के आकार में रैखिक होती है। इनपुट वैक्टर जो सर्किट आउटपुट को "सही" बनाते हैं, वे असाइनमेंट के साथ 1-से-1 पत्राचार में होते हैं जो सूत्र को संतुष्ट करते हैं। यह किसी भी परिपथ (किसी भी सूत्र सहित) पर परिपथ संतुष्टि की समस्या को 3-सी. एन. एफ. सूत्रों पर संतुष्टि की समस्या तक कम कर देता है। इसकी खोज रूसी वैज्ञानिक ग्रिगोरी त्साइटिन ने की थी। अभिप्रेरणा सरल दृष्टिकोण परिपथ को बूलियन अभिव्यक्ति के रूप में लिखना है, और इसे सी. एन. एफ. में बदलने के लिए डी मॉर्गन के नियम और वितरण गुण का उपयोग करना है। हालाँकि, इसके परिणामस्वरूप समीकरण के आकार में घातीय वृद्धि हो सकती है। सेयटिन परिवर्तन एक सूत्र का उत्पादन करता है जिसका आकार इनपुट परिपथ के सापेक्ष रैखिक रूप से बढ़ता है। दृष्टिकोण आउटपुट समीकरण एक अभिव्यक्ति के बराबर स्थिरांक 1 सेट है। यह अभिव्यक्ति उप-अभिव्यक्तियों का एक संयोजन है, जहां प्रत्येक उप-अभिव्यक्ति की संतुष्टि इनपुट सर्किट में एकल गेट के उचित संचालन को लागू करती है। संपूर्ण उत्पादन अभिव्यक्ति की संतुष्टि इस प्रकार लागू करती है कि संपूर्ण इनपुट परिपथ ठीक से काम कर रहा है। प्रत्येक गेट के लिए, इसके आउटपुट का प्रतिनिधित्व करने वाला एक नया चर पेश किया जाता है। एक छोटी पूर्व-गणना की गई सी. एन. एफ. अभिव्यक्ति जो इनपुट और आउटपुट से संबंधित है, आउटपुट अभिव्यक्ति में ("और" ऑपरेशन के माध्यम से) जोड़ी जाती है। ध्यान दें कि इन द्वारों के लिए इनपुट या तो मूल अक्षर हो सकते हैं या उप-द्वारों के आउटपुट का प्रतिनिधित्व करने वाले शुरू किए गए चर हो सकते हैं। यद्यपि आउटपुट अभिव्यक्ति में इनपुट की तुलना में अधिक चर होते हैं, लेकिन यह समान रूप से संतोषजनक रहता है, जिसका अर्थ है कि यह तभी संतोषजनक है जब मूल इनपुट समीकरण संतोषजनक हो। जब चरों का एक संतोषजनक कार्य पाया जाता है, तो शुरू किए गए चरों के लिए उन कार्यों को आसानी से त्याग दिया जा सकता है। एक अंतिम खंड को एकल शाब्दिक के साथ जोड़ा जाता हैः अंतिम गेट का आउटपुट चर। यदि यह शाब्दिक पूरक है, तो इस खंड की संतुष्टि आउटपुट अभिव्यक्ति को गलत करने के लिए लागू करती है; अन्यथा अभिव्यक्ति को सही करने के लिए मजबूर किया जाता है। उदाहरण निम्नलिखित सूत्र पर विचार करें। सभी उप-सूत्रों पर विचार करें (सरल चर को छोड़कर): प्रत्येक उप-सूत्र के लिए एक नए चर का परिचय देंः सभी प्रतिस्थापनों को संयोजित करें और प्रतिस्थापन के लिएः सभी प्रतिस्थापनों को सी. एन. एफ. में बदला जा सकता है, जैसे। गेट उप-अभिव्यक्तियाँ कुछ संभावित उप-अभिव्यक्तियाँ हैं जिन्हें विभिन्न तर्क द्वारों के लिए बनाया जा सकता है। एक ऑपरेशन अभिव्यक्ति में, सी एक आउटपुट के रूप में कार्य करता है; एक सी. एन. एफ. उप-अभिव्यक्ति में, सी एक नए बूलियन चर के रूप में कार्य करता है। प्रत्येक ऑपरेशन के लिए, सी. एन. एफ. उप-अभिव्यक्ति तभी सही होती है जब सी सभी संभावित इनपुट मूल्यों के लिए बूलियन ऑपरेशन के अनुबंध का पालन करता है। सरल संयोजन तर्क निम्नलिखित परिपथ तब सही लौटता है जब इसके कम से कम कुछ इनपुट सही होते हैं, लेकिन एक बार में दो से अधिक नहीं। यह समीकरण को लागू करता है। प्रत्येक गेट के आउटपुट के लिए एक चर पेश किया जाता है; यहाँ प्रत्येक को लाल रंग में चिह्नित किया गया हैः ध्यान दें कि एक इनपुट के रूप में x के साथ इन्वर्टर के आउटपुट में दो चर पेश किए गए हैं। जबकि यह अनावश्यक है, यह परिणामी समीकरण की समता को प्रभावित नहीं करता है। अब प्रत्येक गेट को उसके उपयुक्त सी. एन. एफ. उप-अभिव्यक्ति के साथ प्रतिस्थापित करेंः अंतिम आउटपुट चर गेट8 है ताकि यह लागू किया जा सके कि इस परिपथ का आउटपुट सही हो, एक अंतिम सरल खंड जोड़ा गया हैः (गेट8)। इन समीकरणों के संयोजन से SAT के अंतिम उदाहरण में परिणाम प्राप्त होते हैंः (गेट1′x1) ′ (′x2) ′ (′ गेट2′) ′ (गेट3′x2) ′ (′) ′ (′x1) ′ (′ गेट3) ′ (′ गेट5′x2) ′ (′) ′ (′ गेट5′x5) ′ (′x3) ′ (′ गेट6′) ′ (गेट7′) ′ (गेट7′) ′ (गेट7′) ′ (गेट7′) ′ (गेट यहाँ, वास्तव में आउटपुट सही होने के लिए मूल परिपथ के मानदंडों को पूरा करता है। एक अलग उत्तर खोजने के लिए, खंड (x1 * x2 *) को जोड़ा जा सकता है और SAT समाधानक को फिर से निष्पादित किया जा सकता है। प्रस्तुत व्युत्पत्ति कुछ चुने हुए द्वारों के लिए सी. एन. एफ. उप-अभिव्यक्ति की एक संभावित व्युत्पत्ति हैः या दो इनपुट ए और बी और एक आउटपुट सी के साथ गेट एन ओ. आर. गेट निम्नलिखित शर्तों को पूरा करता हैः यदि आउटपुट सी सही है, तो कम से कम इसका एक इनपुट ए या बी सही है, यदि आउटपुट सी गलत है, तो इसके दोनों इनपुट ए और बी गलत हैं। हम इन दो स्थितियों को दो निहितार्थों के संयोजन के रूप में व्यक्त कर सकते हैंः निहितार्थों को समकक्ष अभिव्यक्तियों के साथ बदलना जिसमें केवल संयोजन, विच्छेदन और निषेध शामिल हैं जो पहले से ही लगभग सामान्य रूप में है। सबसे दाहिने खंड को दो बार वितरित करने और संयोजन की सहयोगीता को लागू करने से सी. एन. एफ. सूत्र 'नॉट गेट' मिलता है जब इसका इनपुट और आउटपुट एक दूसरे का विरोध करते हैं तो 'नॉट गेट' ठीक से काम कर रहा होता है। अर्थात्ः यदि आउटपुट सी सही है, तो इनपुट ए गलत है यदि आउटपुट सी गलत है, तो इनपुट ए सही है इन शर्तों को एक अभिव्यक्ति के रूप में व्यक्त करें जिन्हें संतुष्ट किया जाना चाहिएः एनओआर गेट एनओआर गेट ठीक से काम कर रहा है जब निम्नलिखित शर्तें हैंः यदि आउटपुट सी सही है, तो न तो ए या बी सही हैं यदि आउटपुट सी गलत है, तो ए और बी में से कम से कम एक सही था इन शर्तों को एक अभिव्यक्ति के रूप में व्यक्त करें जिन्हें संतुष्ट किया जाना चाहिएः संदर्भ जी. एस. त्सेटिनः प्रस्तावक कलन में व्युत्पत्ति की जटिलता पर। मेंः स्लिसेन्को, ए. ओ. (एड।) रचनात्मक गणित और गणितीय तर्क में अध्ययन, भाग II, गणित में सेमिनार, पीपी। स्टेक्लोव गणितीय संस्थान (1970)। रूसी से अनुवादितः ज़ापिस्की नौचनीख सेमिनारोव लोमी 8 (1968), पृ. 234-259। जीएस. त्सेटिनः प्रस्तावक कलन में व्युत्पत्ति की जटिलता पर। सितंबर 1966 में आयोजित गणितीय तर्क पर लेनिनग्राद सेमिनार में प्रस्तुत किया गया। कंप्यूटर विज्ञान में लॉजिक गेट्स लॉजिक