एक तार्किक फ़ंक्शन को संयोजक सामान्य रूप कहा जाता है। तार्किक कार्यों का प्रतिनिधित्व करने के संयोजक रूप

तार्किक कार्यों के सामान्य रूप इकाई Ki 2.7 के घटकों के संयोजी शब्दों के विच्छेदन के रूप में एक बूलियन फ़ंक्शन के प्रतिनिधित्व को इस फ़ंक्शन के DNF का विच्छेदन सामान्य रूप कहा जाता है। इसमें नकार के साथ या उसके बिना लिए गए सभी तार्किक चरों में से एक होता है, तो किसी फ़ंक्शन के प्रतिनिधित्व के इस रूप को इस फ़ंक्शन का पूर्ण विघटनकारी सामान्य रूप एसडीएनएफ कहा जाता है। जैसा कि आप देख सकते हैं, एसडीएनएफ फ़ंक्शन बनाते समय, आपको सभी न्यूनतम शब्दों का एक विच्छेदन बनाने की आवश्यकता होती है जिसके लिए फ़ंक्शन मान 1 लेता है।

यदि यह कार्य आपको पसंद नहीं आता है, तो पृष्ठ के नीचे समान कार्यों की एक सूची है। आप खोज बटन का भी उपयोग कर सकते हैं

व्याख्यान 1.xx

तार्किक कार्यों के सामान्य रूप

संयोजक पदों (इकाई घटक) के विच्छेदन के रूप में एक बूलियन फ़ंक्शन का प्रतिनिधित्वके मैं

, (2.7)

बुलाया विच्छेदात्मक सामान्य रूप(डीएनएफ) इस फ़ंक्शन का।

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

उपरोक्त को ध्यान में रखते हुए, निम्नलिखित प्रमेय प्रमेय 2.1 से अनुसरण करता है।

प्रमेय 2. कोई बूलियन फ़ंक्शन(समान रूप से नहीं 0) एसडीएनएफ में प्रस्तुत किया जा सकता है, .

उदाहरण 3. आइए हमारे पास एक तालिका दी गई फ़ंक्शन हैएफ (एक्स 1 , एक्स 2 , एक्स 3 ) (तालिका 10)।

तालिका 10

सूत्र (2.6) के आधार पर हम प्राप्त करते हैं:

जैसा कि आप देख सकते हैं, एसडीएनएफ फ़ंक्शन बनाते समय, आपको सभी न्यूनतम शब्दों का एक विच्छेदन बनाने की आवश्यकता होती है जिसके लिए फ़ंक्शन मान 1 लेता है।

वियोजक पदों (शून्य घटक) के संयोजन के रूप में एक बूलियन फ़ंक्शन का प्रतिनिधित्वडी मैं

, (2.8)

बुलाया संयोजक सामान्य रूप(CNF) इस फ़ंक्शन का।

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

प्रमेय 3. कोई बूलियन फ़ंक्शन(1 के समान नहीं है) एसकेएनएफ को प्रस्तुत किया जा सकता है, और ऐसा प्रतिनिधित्व ही एकमात्र है.

प्रमेय का प्रमाण संयोजनात्मक अपघटन पर निम्नलिखित शैनन लेम्मा के आधार पर प्रमेय 2.1 के प्रमाण के समान ही किया जा सकता है।

शैनन की लेम्मा . कोई भी बूलियन फ़ंक्शन f (x 1, x 2, …, x m) m से चरों को इस प्रकार दर्शाया जा सकता है:

. (2.9)

यह ध्यान दिया जाना चाहिए कि तार्किक फ़ंक्शन (डीएनएफ और सीएनएफ) के प्रतिनिधित्व के दोनों रूप सैद्धांतिक रूप से उनकी क्षमताओं में समान हैं: किसी भी तार्किक सूत्र को डीएनएफ (समान शून्य को छोड़कर) और सीएनएफ (समान शून्य को छोड़कर) दोनों में दर्शाया जा सकता है ). स्थिति के आधार पर, किसी फ़ंक्शन का किसी न किसी रूप में प्रतिनिधित्व छोटा हो सकता है।

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

उदाहरण 4. फ़ंक्शन f (x 1 , x 2 , x 3) के लिए ), तालिका द्वारा दिया गया है। 10, इसे SKNF को लिखें।

एसडीएनएफ के विपरीत, किसी तार्किक फ़ंक्शन की सत्यता तालिका में एससीएनएफ को संकलित करते समय, आपको वेरिएबल्स के संयोजनों को देखने की आवश्यकता होती है, जिस पर फ़ंक्शन मान 0 लेता है, और संबंधित अधिकतम शब्दों का संयोजन बनाता है,लेकिन चर को विपरीत व्युत्क्रम के साथ लिया जाना चाहिए:

यह ध्यान दिया जाना चाहिए कि किसी फ़ंक्शन के एसडीएनएफ से सीधे उसके एससीएनएफ या इसके विपरीत में जाना असंभव है। ऐसे परिवर्तनों का प्रयास करते समय, परिणाम ऐसे कार्य होते हैं जो वांछित कार्यों के विपरीत होते हैं। एसडीएनएफ और एससीएनएफ कार्यों के लिए अभिव्यक्ति सीधे इसकी सत्य तालिका से ही प्राप्त की जा सकती है।

उदाहरण 5. फ़ंक्शन f (x 1 , x 2 , x 3) के लिए ), तालिका द्वारा दिया गया है। 10, एसडीएनएफ से एसकेएनएफ पर स्विच करने का प्रयास करें।

उदाहरण 2.3 के परिणाम का उपयोग करने पर हमें मिलता है:

जैसा कि आप देख सकते हैं, सामान्य व्युत्क्रम के तहत हमने एक तार्किक फ़ंक्शन का SCNF प्राप्त किया, जो उदाहरण 2.4 में प्राप्त फ़ंक्शन का व्युत्क्रम है:

क्योंकि इसमें वे सभी अधिकतम शब्द शामिल हैं जो विचाराधीन फ़ंक्शन के एससीएनएफ के लिए अभिव्यक्ति में नहीं हैं।

1. संचालन के गुणों का उपयोग करते हुए (तालिका 9 देखें) पहचान (), योग मॉड्यूलो 2 (), निहितार्थ (), हम संचालन और, या, नहीं (बूलियन आधार पर) पर आगे बढ़ते हैं।

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

3. तार्किक संचालन AND और OR (तालिका 9 देखें) के गुणों का उपयोग करके, हम सामान्य रूप (DNF या CNF) प्राप्त करते हैं।

4. यदि आवश्यक हो, तो हम पूर्ण रूपों (एसडीएनएफ या एसकेएनएफ) की ओर बढ़ते हैं। उदाहरण के लिए, एससीएनएफ प्राप्त करने के लिए आपको अक्सर संपत्ति का उपयोग करने की आवश्यकता होती है:।

उदाहरण 6. एक तार्किक फ़ंक्शन को SKNF में कनवर्ट करें

उपरोक्त एल्गोरिथम के चरणों को क्रम से आगे बढ़ाने पर, हमें मिलता है:

अवशोषण गुण का उपयोग करके, हम प्राप्त करते हैं:

इस प्रकार, हमने CNF फ़ंक्शन प्राप्त किया हैएफ (एक्स 1 , एक्स 2 , एक्स 3 ). इसका एससीएनएफ प्राप्त करने के लिए, आपको प्रत्येक वियोजन को दोहराना होगा जिसमें कोई भी चर गायब है, इस चर के साथ दो बार और इसके निषेध के साथ:

2.2.6. तर्क कार्यों को न्यूनतम करना

चूँकि समान तार्किक फ़ंक्शन को इस प्रकार दर्शाया जा सकता हैएच व्यक्तिगत सूत्र, फिर सबसे सरल रूप खोजनाआर बूलियन फ़ंक्शन को परिभाषित करने वाला म्यूल, बूलियन फ़ंक्शन को लागू करने वाले लॉजिक सर्किट को सरल बनाता है tion करने के लिए. न्यूनतम प्रपत्र एलहे तार्किक कार्यकुछ आधारों पर हम उस पर विचार कर सकते हैं जिसमें मनोरंजन के सुपरपोजिशन की न्यूनतम संख्या शामिल हैको कोष्ठकों की अनुमति देते हुए, आधार का उल्लेख करें। हालाँकि, एक प्रभावी निर्माण करना कठिन हैएल न्यूनतम कोष्ठक प्राप्त करने के लिए ऐसे न्यूनतमकरण के लिए एल्गोरिदमआर हम.

आइए संयोजन सर्किट के संश्लेषण में एक सरल न्यूनतमकरण समस्या पर विचार करें, जिसमें हम किसी फ़ंक्शन के न्यूनतम कोष्ठक रूप की तलाश नहीं कर रहे हैं, बल्कि इसके न्यूनतम डीएनएफ की तलाश कर रहे हैं। इस कार्य के लिए सरल, कुशल एल्गोरिदम हैं।

क्विन की विधि

न्यूनतम किए जाने वाले फ़ंक्शन को एसडीएनएफ में दर्शाया गया है, और सभी संभावित अपूर्ण ग्लूइंग ऑपरेशन इस पर लागू किए जाते हैं

, (2.10)

और फिर अवशोषण

, (2.11)

और चरणों की यह जोड़ी बार-बार लागू की जाती है। इस प्रकार, पदों की श्रेणी को कम करना संभव है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि एक भी पद ऐसा न बचे जिसे किसी अन्य पद से जोड़ा जा सके।

ध्यान दें कि समीकरण (2.10) के बाईं ओर को तुरंत सरल और अधिक स्पष्ट तरीके से छोटा किया जा सकता है:

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

यह ध्यान दिया जाना चाहिए कि क्विन की विधि काफी श्रम-गहन है, इसलिए परिवर्तनों के दौरान गलतियाँ होने की संभावना काफी अधिक है। लेकिन इसका लाभ यह है कि सैद्धांतिक रूप से इसका उपयोग किसी भी संख्या में तर्कों के लिए किया जा सकता है और जैसे-जैसे चर की संख्या बढ़ती है, परिवर्तन कम जटिल हो जाते हैं।

कर्णघ मानचित्र विधि

कार्नोट मैप्स (तालिकाओं) की विधि तार्किक कार्यों को कम करने के लिए अधिक दृश्य, कम श्रम-गहन और विश्वसनीय तरीका है, लेकिन इसका उपयोग व्यावहारिक रूप से 3-4 चर, अधिकतम 5-6 चर के कार्यों तक सीमित है।

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

दो लेन के AND और OR कार्यों के लिए सत्य सारणी और कार्नॉघ मानचित्रइ चर चित्र में प्रस्तुत किए गए हैं। 8. कार्ड के प्रत्येक सेल में एक मान लिखा होता हैए इस सेल के अनुरूप तर्क मानों के सेट पर किसी फ़ंक्शन का मानएन कॉमरेड

ए) और बी) या

चावल। 8. दो चरों के कार्यों के लिए कर्णघ मानचित्र का उदाहरण

कर्नाघ मानचित्र में And फ़ंक्शन के लिए केवल एक 1 है, इसलिए इसे किसी भी चीज़ से चिपकाया नहीं जा सकता है। न्यूनतम फ़ंक्शन की अभिव्यक्ति में केवल इस 1 के अनुरूप पद शामिल होगा:

एफ = एक्स वाई .

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

एफ = एक्स + वाई.

चित्र में. 9 तीन चर वाले दो कार्यों की सत्य सारणी दिखाता है (ए ) और उनके कार्नोट मानचित्र (बी और सी). फ़ंक्शन एफ 2 पहले से इस मायने में भिन्न है कि इसे चर के तीन सेटों पर परिभाषित नहीं किया गया है (तालिका में इसे डैश द्वारा दर्शाया गया है)।

न्यूनतम डीएनएफ फ़ंक्शन का निर्धारण करते समय, निम्नलिखित नियमों का उपयोग किया जाता है। 1 युक्त सभी कोशिकाओं को बंद आयताकार क्षेत्रों में संयोजित किया जाता है जिन्हें कहा जाता है k-घन, जहाँ k = लघुगणक 2 K, K एक आयताकार क्षेत्र में मात्रा 1. इस मामले में, प्रत्येक क्षेत्र 2 कोशिकाओं की संख्या के साथ एक आयत होना चाहिए k, जहाँ k = 0, 1, 2, 3,…। के = के लिए 1 आयत कहलाता हैएक एक घन है और इसमें 2 1 = 2 इकाइयाँ हैं; के = के लिए 2 आयत में 2 शामिल हैं 2 = 4 इकाई और कहा जाता हैदो-घन; k = 2 3 के 3 क्षेत्र के लिए = 8 इकाई कहलाती हैतीन घन ; आदि ऐसी इकाइयाँ जिन्हें आयतों में नहीं जोड़ा जा सकता कहा जा सकता हैशून्य-घन , जिसमें केवल एक इकाई है (2 0 = 1). जैसा कि देखा जा सकता है, यहां तक ​​किक क्षेत्रों का आकार चौकोर हो सकता है (लेकिन जरूरी नहीं), और यदि विषम भी होक केवल आयतें.

चावल। 9. तीन चर वाले कार्यों के लिए कर्णघ मानचित्र का उदाहरण

ये क्षेत्र ओवरलैप हो सकते हैं, यानी एक ही कोशिकाएं विभिन्न क्षेत्रों में प्रवेश कर सकती हैं। फिर न्यूनतम डीएनएफ फ़ंक्शन को संबंधित सभी संयोजक शब्दों के विच्छेदन के रूप में लिखा जाता हैके - क्यूब्स।

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

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

चित्र में कर्णघ मानचित्र के अनुसार फ़ंक्शन के लिए। 9,बी हम पाते हैं

चूंकि ऊपरी बंद क्षेत्र के लिए चरएक्स 1 और एक्स 2 निम्न के लिए व्युत्क्रम के बिना मान हैंएक्स 1 व्युत्क्रम के साथ मायने रखता है, और x 3 बिना व्युत्क्रमण के।

चित्र में मानचित्र में अपरिभाषित मान। 9,वी इसे शून्य या एक से प्रतिस्थापित करके और अधिक परिभाषित किया जा सकता है। इस फ़ंक्शन के लिए, यह स्पष्ट है कि दोनों अपरिभाषित मानों को 1 से प्रतिस्थापित करना अधिक लाभदायक है। इस स्थिति में, दो क्षेत्र बनते हैं, जो विभिन्न प्रकार के 2-क्यूब हैं। फिर न्यूनतम DNF फ़ंक्शन के लिए अभिव्यक्ति इस प्रकार होगी:

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

कार्नॉघ मानचित्र विभिन्न तरीकों से बनाए जा सकते हैं (चित्र 10)।

ए बी

चावल। 10. कार्नॉघ मानचित्रों को चित्रित करने के विभिन्न तरीके
3 वेरिएबल के एक फ़ंक्शन के लिए

लेकिन 2-4 चर के कार्यों के लिए कर्णघ मानचित्रों के लिए सबसे सुविधाजनक विकल्प चित्र में दिखाए गए हैं। 11 तालिकाएँ, क्योंकि वे प्रत्येक कोशिका के लिए दिखाती हैंए हमारे पास सभी चर प्रत्यक्ष या व्युत्क्रम रूप में हैं।

ए बी

चावल। ग्यारह। कार्नॉघ मानचित्रों की सबसे सुविधाजनक छवि
फ़ंक्शन 3 के लिए (ए) और 4 (बी) चर

5 और 6 चर वाले कार्यों के लिए, चित्र में दिखाई गई विधि। 10,वी.

चावल। 12. 5 चर वाले फ़ंक्शन के लिए कर्णघ मानचित्र की छवि

चावल। 13. 6 चरों के एक फ़ंक्शन के लिए कर्णघ मानचित्र की छवि

मानक आधार. प्राथमिक सूत्र शाब्दिक हैं. प्राथमिक संयोजन (विघटन)। विभक्ति (संयोजक) सामान्य रूप और उत्तम रूप। प्रमेय: 0 (1 से) से भिन्न किसी भी बूलियन फ़ंक्शन को SDNF (SCNF) के रूप में दर्शाया जा सकता है। मानक आधार की पूर्णता. पूर्ण आधारों के उदाहरण: ज़ेगल्किन आधार, शेफ़र स्ट्रोक, पीयर्स तीर।

मानक आधार बूलियन बीजगणित की तीन बुनियादी संक्रियाओं का एक सेट है: जोड़ (संघ), गुणा (प्रतिच्छेदन) और निषेध।

यहां हम कॉल करेंगे शाब्दिक चर x या उसका निषेधन x और निरूपित xˆ। विभिन्न चरों द्वारा परिभाषित कई शाब्दिकों का बूलियन प्रतिच्छेदन, अर्थात। X = xˆ 1 xˆ 2 के रूप की अभिव्यक्ति। . . xˆl, कहा जाता है प्राथमिक संयोजन . सभी चरों के अलग-अलग होने की आवश्यकता निम्नलिखित द्वारा निर्धारित की जाती है। यदि किसी संयोजन में कई समान अक्षर शामिल हैं, तो संयोजन की क्रमविनिमेयता, साहचर्यता और निष्क्रियता के कारण, समतुल्य सूत्र में जाने पर, केवल एक अक्षर छोड़ना संभव है (उदाहरण के लिए, x 1 x 1 = x 1)। यदि संयोजन में एक चर और उसका निषेध शामिल है, तो सूत्र स्थिरांक 0 के बराबर है, क्योंकि x x = 0 और किसी भी सूत्र Y के लिए हमारे पास Y x x = 0 है।

अनेक प्रारंभिक समुच्चयबोधकों का विच्छेद कहलाता है विच्छेदात्मक सामान्य रूप , या डीएनएफ . उदाहरण के लिए,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5।

यदि किसी दिए गए DNF के प्रत्येक प्रारंभिक संयोजन में चर की संरचना समान है, तो DNF कहा जाता है उत्तम . दिया गया उदाहरण एक डीएनएफ है जो सही नहीं है। इसके विपरीत, सूत्र

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

एक आदर्श रूप है.

चूंकि बूलियन बीजगणित में जोड़ और गुणा सममित संक्रियाएं हैं और आप हमेशा जोड़ को गुणा के रूप में और गुणा को जोड़ के रूप में व्याख्या कर सकते हैं, एक दोहरी अवधारणा है - संयोजक सामान्य रूप (केएनएफ ), जो प्रारंभिक विच्छेदन का एक संयोजन है, और उत्तम संयोजक रूप (एसकेएनएफ ). सममित सेमीरिंग्स के लिए द्वंद्व के सिद्धांत से यह पता चलता है कि डीएनएफ के संबंध में किसी भी कथन का उत्तर सीएनएफ के संबंध में दोहरे कथन द्वारा दिया जाता है, जो जोड़ (वियोजन) को गुणन के साथ, गुणन (संयोजन) को जोड़ के साथ, स्थिरांक 0 को स्थिरांक 1 के साथ प्रतिस्थापित करके प्राप्त किया जाता है। 1 स्थिरांक 0 के साथ, क्रम में दोहरे (व्युत्क्रम) के साथ संबंध। इसलिए आगे हम सिर्फ DNF के अध्ययन पर ही फोकस करेंगे.

प्रमेय 1.4.स्थिरांक 0 के अलावा किसी भी बूलियन फ़ंक्शन को SDNF के रूप में दर्शाया जा सकता है।

◀आइए हम सहमत हैं कि x σ से हमारा तात्पर्य सूत्र x से है यदि σ = 1 है, और सूत्र x यदि σ = 0 है। मान लें कि फ़ंक्शन f(y 1 , . . . . , y n) वेक्टर (t) पर मान 1 लेता है 1 , . . . , t n ) (ऐसे वेक्टर को कहा जाता है घटक इकाई ). फिर प्रारंभिक संयोजन भी इस सेट पर मान 1 लेता है, लेकिन अन्य सभी एन-आयामी बूलियन वैक्टर पर गायब हो जाता है। सूत्र पर विचार करें

जिसमें योग (संघ) तर्क मानों के उन सभी सेटों (t 1, ..., t n) तक विस्तारित होता है, जिस पर दिया गया फ़ंक्शन मान 1 लेता है। ध्यान दें कि ऐसे सेट का सेट खाली नहीं है, इसलिए योग में कम से कम एक पद होता है।

यह देखना आसान है कि सूत्र Φ उन लोगों के लिए 1 बन जाता है और केवल चर के उन मानों के लिए जिनके लिए प्रश्न में फ़ंक्शन 1 हो जाता है। इसका मतलब यह है कि सूत्र Ψ फ़ंक्शन f का प्रतिनिधित्व करता है।

परिणाम 1.1.मानक आधार पूरा हो गया है.

◀ दरअसल, यदि कोई फ़ंक्शन स्थिर 0 नहीं है, तो इसे एसडीएनएफ के रूप में दर्शाया जा सकता है, जो मानक आधार पर एक सूत्र है। उदाहरण के लिए, स्थिरांक 0 को सूत्र f(x 1, x 2,..., x n) = x 1 x 1 द्वारा दर्शाया जा सकता है।

उदाहरण 1.2.तीन चर m(x 1, x 2, x 3) (तालिका 1.4) के एक फ़ंक्शन पर विचार करें, जिसे कहा जाता है बहुसंख्यकवादी कार्य ̆. यदि इसके आधे से अधिक तर्कों का मान 1 है तो यह फ़ंक्शन 1 का मूल्यांकन करता है। इसलिए, इसे अक्सर वोटिंग फ़ंक्शन कहा जाता है। आइए इसके लिए एक एसडीएनएफ बनाएं।

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

उदाहरण 1.3.संचालन मोडुलो 2 जोड़, गुणा और स्थिरांक 1 के सेट को कहा जाता है ज़ेगलकिन आधार . जोड़ मॉड्यूलो 2 और गुणन Z2 रिंग के मूल संचालन हैं; उनकी मदद से बनाए गए भाव Z2 रिंग पर बहुपद हैं। इस स्थिति में स्थिरांक 1 मुक्त पद लिखने के लिए आवश्यक है। चूँकि xx = x, तो बहुपद के सभी कारकों की घात 1 होती है। इसलिए, बहुपद लिखते समय, आप घात की अवधारणा के बिना भी काम कर सकते हैं। ज़ेगलकिन आधार पर सूत्रों के उदाहरण:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

ऐसे किसी भी सूत्र को ज़ेगलकिन बहुपद कहा जाता है। वास्तव में, ज़ेगल्किन बहुपद वलय Z2 पर एक बहुपद है।

ज़ेगाल्किन आधार पर सूत्रों का निर्माण करना मुश्किल नहीं है, जो मानक आधार के जोड़ और नकार के संचालन का प्रतिनिधित्व करते हैं (दो आधारों का गुणन सामान्य है):

x+y=x⊕y⊕xy, x =x⊕1.

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

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

उदाहरण 1.4.आइए एकल फ़ंक्शन के एक सेट पर विचार करें - शेफ़र स्ट्रोक*। यह सेट निम्नलिखित आसानी से सत्यापन योग्य पहचानों के अनुसार पूरा हो गया है:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

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

*शेफ़र का स्ट्रोक एक द्विआधारी है, लेकिन सहयोगी नहीं, ऑपरेशन। इसलिए, इन्फिक्स फॉर्म का उपयोग करते समय, आपको सावधान रहना चाहिए: परिणाम संचालन के क्रम पर निर्भर करता है। इस मामले में, कोष्ठक का उपयोग करके संचालन के क्रम को स्पष्ट रूप से इंगित करने की अनुशंसा की जाती है, उदाहरण के लिए, लिखें (x | y) | z, x नहीं | य | z, हालाँकि दोनों रूप समतुल्य हैं।

परिभाषा 1.संयोजक एकपदी (प्रारंभिक संयोजन)चरों का इन चरों या उनके निषेधों का संयोजन है।

उदाहरण के लिए, एक प्रारंभिक संयोजन है।

परिभाषा 2.विभक्ति एकपदी (प्रारंभिक वियोजन)चरों से इन चरों का विच्छेद या उनका निषेधन होता है।

उदाहरण के लिए, एक प्राथमिक विच्छेद है।

परिभाषा 3.एक सूत्र जो किसी दिए गए प्रस्तावित बीजगणित सूत्र के समतुल्य है और प्राथमिक संयोजक एकपदी का विच्छेदन है, कहलाता है विच्छेदात्मक सामान्य रूप(डीएनएफ) इस सूत्र का।

उदाहरण के लिए,- डीएनएफ.

परिभाषा 4.एक सूत्र जो किसी दिए गए प्रस्तावित बीजगणित सूत्र के समतुल्य है और प्रारंभिक विच्छेदनात्मक एकपदी का संयोजन है, कहलाता है संयोजक सामान्य रूप(CNF) इस सूत्र का.

उदाहरण के लिए, - केएनएफ।

प्रत्येक प्रस्तावात्मक बीजगणित सूत्र के लिए वियोजक और संयोजक सामान्य रूपों का एक सेट पाया जा सकता है।

सामान्य प्रपत्रों के निर्माण के लिए एल्गोरिदम

तार्किक बीजगणित की तुल्यताओं का उपयोग करते हुए, सूत्र में सभी बुनियादी संक्रियाओं को बदलें: संयोजन, वियोजन, निषेध:

दोहरी नकारात्मकताओं से छुटकारा पाएं.

यदि आवश्यक हो, तो संयोजन और विच्छेदन के संचालन के लिए वितरण और अवशोषण सूत्रों के गुणों को लागू करें।

2.6. उत्तम विभक्ति और उत्तम समुच्चय सामान्य रूप

किसी भी बूलियन फ़ंक्शन में DNF और CNF के रूप में कई प्रतिनिधित्व हो सकते हैं। इन अभ्यावेदनों के बीच एक विशेष स्थान पर परफेक्ट डीएनएफ (एसडीएनएफ) और परफेक्ट सीएनएफ (एससीएनएफ) का कब्जा है।

परिभाषा 1. उत्तम विभक्ति सामान्य रूप(एसडीएनएफ) एक डीएनएफ है जिसमें प्रत्येक संयुग्मक एकपदी में सेट से प्रत्येक चर बिल्कुल एक बार होता है, या तो स्वयं या उसके निषेधन में।

संरचनात्मक रूप से, डीएनएफ में घटाए गए प्रत्येक प्रस्तावित बीजगणित सूत्र के लिए एसडीएनएफ को निम्नानुसार परिभाषित किया जा सकता है:

परिभाषा 2. उत्तम विभक्ति सामान्य रूपएक प्रस्तावित बीजगणित सूत्र के (एसडीएनएफ) को इसका डीएनएफ कहा जाता है, जिसमें निम्नलिखित गुण होते हैं:

परिभाषा 3. उत्तम संयोजक सामान्य रूप(एससीएनएफ) एक सीएनएफ है जिसमें प्रत्येक डिसजंक्टिव मोनोमियल में सेट से प्रत्येक चर बिल्कुल एक बार होता है, और या तो स्वयं या उसका निषेधन प्रकट होता है।

संरचनात्मक रूप से, सीएनएफ में घटाए गए प्रत्येक प्रस्तावित बीजगणित सूत्र के लिए एससीएनएफ को निम्नानुसार परिभाषित किया जा सकता है।

परिभाषा 4. उत्तम संयोजक सामान्य रूपकिसी दिए गए प्रस्तावित बीजगणित सूत्र के (एससीएनएफ) को सीएनएफ कहा जाता है जो निम्नलिखित गुणों को संतुष्ट करता है।

प्रमेय 1.वेरिएबल्स का प्रत्येक बूलियन फ़ंक्शन जो समान रूप से गलत नहीं है, उसे एसडीएनएफ में और एक अनूठे तरीके से दर्शाया जा सकता है।

एसडीएनएफ खोजने के तरीके

पहली विधि

दूसरी विधि

उन पंक्तियों का चयन करें जहां सूत्र मान 1 लेता है;

हम इस शर्त के तहत संयोजनों का विच्छेदन बनाते हैं कि यदि एक चर को 1 के मान के साथ संयोजन में शामिल किया जाता है, तो हम इस चर को लिखते हैं; यदि 0 के मान के साथ, तो इसका निषेधन। हमें एसडीएनएफ मिलता है।

प्रमेय 2.वेरिएबल्स का प्रत्येक बूलियन फ़ंक्शन जो समान रूप से सत्य नहीं है, उसे एससीएनएफ में और एक अनूठे तरीके से दर्शाया जा सकता है।

एससीएनएफ खोजने के तरीके

पहली विधि- समतुल्य परिवर्तनों का उपयोग करना:

दूसरी विधि- सत्य तालिकाओं का उपयोग करना:

उन पंक्तियों का चयन करें जहां सूत्र मान 0 लेता है;

हम इस शर्त के तहत वियोजनों का संयोजन बनाते हैं कि यदि 0 के मान के साथ एक चर को वियोजन में शामिल किया जाता है, तो हम इस चर को लिखते हैं; यदि 1 के मान के साथ, तो इसका निषेधन। हमें एसकेएनएफ मिलता है।

उदाहरण 1।सीएनएफ फ़ंक्शन का निर्माण करें।

समाधान

आइए चरों के परिवर्तन के नियमों का उपयोग करके संयोजक "" को हटा दें:

= /डी मॉर्गन के नियम और दोहरा निषेध/ =

/वितरणात्मक कानून/=

उदाहरण 2. DNF का सूत्र बताइये।

समाधान

आइए और का उपयोग करके तार्किक संक्रियाओं को व्यक्त करें:

= /आइए निषेध को चर के रूप में वर्गीकृत करें और दोहरे नकारात्मक को कम करें/ =

= /वितरण का नियम/ .

उदाहरण 3.डीएनएफ और एसडीएनएफ में सूत्र लिखें।

समाधान

तर्क के नियमों का उपयोग करते हुए, हम इस सूत्र को एक ऐसे रूप में बदल देते हैं जिसमें केवल प्रारंभिक संयोजनों का विच्छेदन होता है। परिणामी सूत्र वांछित DNF होगा:

एसडीएनएफ के निर्माण के लिए, आइए इस सूत्र के लिए एक सत्य तालिका बनाएं:

हम तालिका की उन पंक्तियों को चिह्नित करते हैं जिनमें सूत्र (अंतिम कॉलम) मान 1 लेता है। ऐसी प्रत्येक पंक्ति के लिए, हम एक सूत्र लिखते हैं जो इस पंक्ति के चर के सेट पर सत्य है:

लाइन 1: ;

पंक्ति 3: ;

पंक्ति 5: .

इन तीन सूत्रों का विच्छेदन केवल पंक्ति 1, 3, 5 में चर के सेट पर मान 1 लेगा, और इसलिए वांछित पूर्ण विच्छेदन सामान्य रूप (पीडीएनएफ) होगा:

उदाहरण 4.सूत्र को SKNF में दो तरीकों से लाएँ:

क) समतुल्य परिवर्तनों का उपयोग करना;

बी) सत्य तालिका का उपयोग करना।

समाधान:

आइए हम दूसरे प्राथमिक विच्छेदन को रूपांतरित करें:

सूत्र इस प्रकार दिखता है:

बी) इस सूत्र के लिए एक सत्य तालिका बनाएं:

हम तालिका की उन पंक्तियों को चिह्नित करते हैं जिनमें सूत्र (अंतिम कॉलम) मान 0 लेता है। ऐसी प्रत्येक पंक्ति के लिए, हम एक सूत्र लिखते हैं जो इस पंक्ति के चर के सेट पर सत्य है:

लाइन 2: ;

पंक्ति 6: .

इन दो सूत्रों का संयोजन केवल पंक्ति 2 और 6 में चर के सेट पर मान 0 लेगा, और इसलिए वांछित पूर्ण संयोजक सामान्य रूप (पीसीएनएफ) होगा:

स्वतंत्र समाधान के लिए प्रश्न और कार्य

1. समतुल्य परिवर्तनों का उपयोग करते हुए, सूत्रों को DNF तक कम करें:

2. समतुल्य परिवर्तनों का उपयोग करते हुए, सूत्रों को CNF में लाएँ:

3. दूसरे वितरण नियम का उपयोग करके, DNF को CNF में बदलें:

ए) ;

4. दिए गए DNF को SDNF में बदलें:

5. दिए गए CNF को SCNF में बदलें:

6. दिए गए तार्किक सूत्रों के लिए, एसडीएनएफ और एससीएनएफ का निर्माण दो तरीकों से करें: समकक्ष परिवर्तनों का उपयोग करना और सत्य तालिका का उपयोग करना।

बी) ;

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

प्राथमिक संयोजन (संयुक्त)चरों के समुच्चय या उनके निषेध कहलाते हैं जिनमें प्रत्येक चर अधिकतम होता है

एक बार।

विच्छेदनात्मक सामान्य रूप(डीएनएफ) एक सूत्र है जिसमें प्रारंभिक संयोजनों के विच्छेदन का रूप होता है।

प्राथमिक विच्छेद (विच्छेद)निषेध के साथ या निषेध के बिना चरों के वियोजन कहलाते हैं।

संयोजक सामान्य रूप(सीएनएफ) एक सूत्र है जो प्रारंभिक विच्छेदन के संयोजन का रूप रखता है।

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

डीएनएफ के निर्माण के लिए एल्गोरिदम:

1. समतुल्य परिवर्तन सूत्रों का उपयोग करके बूलियन संचालन पर जाएं।

2. करीबी निषेधों वाले सूत्रों पर जाएं, यानी, एक ऐसे सूत्र पर जिसमें निषेध चर के ऊपर से अधिक नहीं स्थित हैं - डी मॉर्गन के नियमों को लागू करें।

3. कोष्ठक खोलें - वितरण के नियम लागू करें।

4. एक समय में एक बार दोहराए जाने वाले शब्दों को लें - निष्क्रियता का नियम।

5. अवशोषण और अर्ध-अवशोषण के नियम लागू करें।

उदाहरण 6.डीएनएफ सूत्र खोजें: .

बूलियन बीजगणित में यह सत्य है द्वैत का सिद्धांत. यह इस प्रकार है.

फ़ंक्शन को कॉल किया जाता है दोहरीफ़ंक्शन के लिए यदि . वे। किसी दिए गए फ़ंक्शन के दोहरे फ़ंक्शन को खोजने के लिए, तर्कों के निषेधों से फ़ंक्शन के निषेधन का निर्माण करना आवश्यक है।

उदाहरण 7.फ़ंक्शन डुएल को खोजें।

तर्क के बीजगणित के प्रारंभिक कार्यों में, 1 से 0 द्वैत है और इसके विपरीत, x से द्वैत है, x से द्वैत है, द्वैत से 0 है और इसके विपरीत।

यदि सूत्र F 1 में फ़ंक्शन का प्रतिनिधित्व करते हुए हम सभी संयोजनों को प्रतिस्थापित करते हैं

वियोजन पर, वियोजन पर वियोजन, 1 पर 0, 0 पर 1, तब हमें सूत्र F* प्राप्त होता है जो फलन * दोहरे को दर्शाता है।

संयोजक सामान्य रूप (सीएनएफ) डीएनएफ के लिए एक दोहरी अवधारणा है, इसलिए इसे निम्नलिखित योजना के अनुसार आसानी से बनाया जा सकता है:

उदाहरण 8. CNF सूत्र खोजें: .

उदाहरण 6 के परिणाम का उपयोग करते हुए, हमारे पास है

उत्तम विभक्ति और उत्तम समुच्चय सामान्य रूप।प्रत्येक प्रकार के सामान्य रूपों (डिजंक्टिव और कंजंक्टिव) में, कोई भी पूर्ण रूपों एसडीएनएफ और एससीएनएफ के एक वर्ग को अलग कर सकता है।

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

किसी भी डीएनएफ को उन संयोजनों को विभाजित करके एसडीएनएफ में घटाया जा सकता है जिनमें सभी चर शामिल नहीं हैं, यानी। लुप्त चर x i को जोड़कर वितरण नियम का उपयोग करके गुणा किया जाता है

उदाहरण 9.उदाहरण 6 के डीएनएफ के लिए एसडीएनएफ खोजें

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

किसी भी सीएनएफ को एक संयोजन शब्द जोड़कर एससीएनएफ में कम किया जा सकता है जिसमें संयोजन द्वारा कोई चर एक्स नहीं होता है और वितरण कानून लागू होता है

उदाहरण 10. KNF को SKNF में लाएँ:

SCNF के निर्माण के लिए, आप आरेख का उपयोग कर सकते हैं

उदाहरण 11.उदाहरण 6 के सूत्र के लिए एससीएनएफ खोजें।

प्रत्येक फ़ंक्शन में एक SDNF और, इसके अलावा, एक अद्वितीय होता है। प्रत्येक फ़ंक्शन में एक SCNF और, इसके अलावा, एक अद्वितीय होता है।

क्योंकि एसडीएनएफ और एसकेएनएफ को सूत्रों द्वारा विशिष्ट रूप से परिभाषित किया गया है; इन्हें सूत्र की सत्य तालिका का उपयोग करके बनाया जा सकता है।

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

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

उदाहरण 12.उदाहरण 6 के सूत्र के लिए सत्य तालिका का उपयोग करके एसडीएनएफ और एससीएनएफ खोजें।

तालिका 14 केवल अंतिम मान F=10101101 दिखाती है। आपको एक विस्तृत सत्य तालिका बनाकर इस कथन की वैधता को स्वयं सत्यापित करना चाहिए।

तालिका 14

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

यदि किसी तार्किक फलन को चरों के विच्छेदन, संयोजन तथा निषेध के माध्यम से व्यक्त किया जाता है, तो निरूपण के इस रूप को सामान्य कहा जाता है।

सामान्य रूपों के बीच, पूर्ण सामान्य रूपों को प्रतिष्ठित किया जाता है (वे रूप जिनमें कार्यों को एक अनोखे तरीके से लिखा जाता है)।

परफेक्ट डिसजंक्टिव नॉर्मल फॉर्म (पीडीएनएफ)

परिभाषा। एक सूत्र को प्रारंभिक संयोजन कहा जाता है यदि यह एक निश्चित संख्या में चरों या उनके निषेधों के संयोजन से बनता है।

उदाहरण: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

परिभाषा। एक सूत्र को डिसजंक्टिव नॉर्मल फॉर्म (डीएनएफ) कहा जाता है यदि यह गैर-दोहराए जाने वाले प्राथमिक संयोजनों का एक डिसजंक्शन है।

DNF निम्नलिखित रूप में लिखा गया है: F 1 ∨ F 2 ∨ ... ∨ F n , जहां F i प्रारंभिक संयोजन है

उदाहरण: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3 , ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

परिभाषा। K वेरिएबल्स में एक तार्किक सूत्र को पूर्ण विघटनकारी सामान्य रूप (PDNF) कहा जाता है यदि:
1) सूत्र एक डीएनएफ है, जिसमें प्रत्येक प्रारंभिक संयोजन k चर x 1, x 2, ..., x k का एक संयोजन है, और इस संयोजन के i-वें स्थान पर या तो एक चर x i है या इसका निषेध है ;
2) ऐसे डीएनएफ में सभी प्रारंभिक संयोजन जोड़ीवार अलग-अलग होते हैं।

उदाहरण: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

परफेक्ट कंजंक्टिव नॉर्मल फॉर्म (पीसीएनएफ)

परिभाषा। एक सूत्र को प्रारंभिक वियोजन कहा जाता है यदि यह एक निश्चित संख्या में चरों के वियोजन या उनके निषेधन से बनता है।

उदाहरण: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

परिभाषा। एक सूत्र को संयोजक सामान्य रूप (सीएनएफ) कहा जाता है यदि यह गैर-दोहराए जाने वाले प्राथमिक विच्छेदन का संयोजन है।

सीएनएफ को निम्नलिखित रूप में लिखा गया है: एफ 1 ∧ एफ 2 ∧ ... ∧ एफ एन, जहां एफ आई एक प्रारंभिक विच्छेदन है

उदाहरण: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

परिभाषा। K वेरिएबल्स में एक तार्किक सूत्र को एक पूर्ण संयोजक सामान्य रूप (सीपीएनएफ) कहा जाता है यदि:
1) सूत्र सीएनएफ है, जिसमें प्रत्येक प्रारंभिक वियोजन k चर x 1, x 2, ..., x k का एक वियोजन है, और इस वियोजन के i-वें स्थान पर या तो एक चर x i या इसका निषेध है;
2) ऐसे सीएनएफ में सभी प्राथमिक विच्छेदन जोड़ीवार अलग-अलग होते हैं।

उदाहरण: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

नोटिस जो कोई भी तार्किक फ़ंक्शन जो 0 या 1 के बराबर नहीं है, उसे एसडीएनएफ या एसकेएनएफ के रूप में दर्शाया जा सकता है.

सत्य तालिका का उपयोग करके एसडीएनएफ के निर्माण के लिए एल्गोरिदम

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

सत्य तालिका का उपयोग करके एससीएनएफ के निर्माण के लिए एल्गोरिदम

1. उन सभी तालिका पंक्तियों का चयन करें जिनमें फ़ंक्शन मान शून्य है।
2. ऐसी प्रत्येक पंक्ति के लिए, सभी चरों का विच्छेद इस प्रकार लिखें: यदि इस समुच्चय में किसी चर का मान 0 के बराबर है, तो हम चर को ही संयोजन में शामिल करते हैं, अन्यथा, इसका निषेधन।
3. हम सभी परिणामी वियोजनों को संयोजन संक्रियाओं से जोड़ते हैं।

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

उदाहरण: तीन चरों के तार्किक फलन की एक सत्य तालिका दी गई है। एक तार्किक सूत्र का निर्माण करें जो इस फ़ंक्शन को लागू करता है।

क्योंकि सत्य तालिका की अधिकांश पंक्तियों पर फ़ंक्शन का मान 1 है, तो हम SCNF का निर्माण करेंगे। परिणामस्वरूप, हमें निम्नलिखित तार्किक सूत्र प्राप्त होता है:
एफ = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

आइए परिणामी सूत्र की जाँच करें। ऐसा करने के लिए, हम फ़ंक्शन के लिए एक सत्य तालिका का निर्माण करेंगे।

मूल सत्य तालिका और तार्किक सूत्र के लिए निर्मित तालिका की तुलना करते हुए, हम ध्यान देते हैं कि फ़ंक्शन मानों के कॉलम मेल खाते हैं। इसका मतलब है कि तार्किक फ़ंक्शन का निर्माण सही ढंग से किया गया है।