Tseytin transformation
சைட்டின் உருமாற்றம், மாற்றாக எழுதப்பட்ட சைட்டின் உருமாற்றம், ஒரு தன்னிச்சையான ஒருங்கிணைந்த தர்க்க சுற்று உள்ளீடாக எடுத்து, இணை இயல்பான வடிவத்தில் (சிஎன்எஃப்) சமமான திருப்திகரமான பூலியன் சூத்திரத்தை உருவாக்குகிறது. சூத்திரத்தின் நீளம் சுற்றுவட்டத்தின் அளவில் நேரியல் ஆகும். சுற்று வெளியீட்டை "உண்மை" ஆக்கும் உள்ளீட்டு திசையன்கள் சூத்திரத்தை திருப்திப்படுத்தும் பணிகளுடன் 1 முதல் 1 வரை தொடர்புடையவை. இது எந்தவொரு சுற்றிலும் (எந்தவொரு சூத்திரமும் உட்பட) சுற்று திருப்தியளிப்பதில் உள்ள சிக்கலை 3-சிஎன்எஃப் சூத்திரங்களில் திருப்தியளிப்பதில் உள்ள சிக்கலாக குறைக்கிறது. இதை ரஷ்ய விஞ்ஞானி கிரிகோரி சைடின் கண்டுபிடித்தார். உந்துதல் அப்பாவித்தனமான அணுகுமுறை என்பது சுற்றுவட்டத்தை ஒரு பூலியன் வெளிப்பாடாக எழுதுவதும், டி மோர்கனின் சட்டத்தையும் விநியோகச் சொத்தையும் பயன்படுத்தி அதை சிஎன்எஃப் ஆக மாற்றுவதும் ஆகும். இருப்பினும், இது சமன்பாட்டின் அளவில் அதிவேக அதிகரிப்புக்கு வழிவகுக்கும். சைட்டின் உருமாற்றம் ஒரு சூத்திரத்தை வெளியிடுகிறது, அதன் அளவு உள்ளீட்டு சுற்றுகளுடன் ஒப்பிடுகையில் நேரியல் ரீதியாக வளரும். அணுகுமுறை வெளியீட்டு சமன்பாடு என்பது ஒரு வெளிப்பாட்டிற்கு சமமான மாறிலி 1 தொகுப்பாகும். இந்த வெளிப்பாடு துணை வெளிப்பாடுகளின் இணைப்பாகும், அங்கு ஒவ்வொரு துணை வெளிப்பாட்டின் திருப்தியும் உள்ளீட்டு சுற்றுவட்டத்தில் ஒரு வாயிலின் சரியான செயல்பாட்டை செயல்படுத்துகிறது. முழு வெளியீட்டு வெளிப்பாட்டின் திருப்தி இதனால் முழு உள்ளீட்டு சுற்றும் சரியாக இயங்குகிறது என்பதை செயல்படுத்துகிறது. ஒவ்வொரு வாயிலுக்கும், அதன் வெளியீட்டைக் குறிக்கும் ஒரு புதிய மாறி அறிமுகப்படுத்தப்படுகிறது. உள்ளீடுகள் மற்றும் வெளியீடுகளை தொடர்புபடுத்தும் ஒரு சிறிய முன் கணக்கிடப்பட்ட சிஎன்எஃப் வெளிப்பாடு வெளியீட்டு வெளிப்பாட்டுடன் ("மற்றும்" செயல்பாடு வழியாக) இணைக்கப்படுகிறது. இந்த வாயில்களுக்கான உள்ளீடுகள் அசல் எழுத்துக்களாகவோ அல்லது துணை வாயில்களின் வெளியீடுகளைக் குறிக்கும் அறிமுகப்படுத்தப்பட்ட மாறிகளாகவோ இருக்கலாம் என்பதை நினைவில் கொள்க. வெளியீட்டு வெளிப்பாடு உள்ளீட்டை விட அதிக மாறிகளைக் கொண்டிருந்தாலும், அது சமமான திருப்திகரமாக உள்ளது, அதாவது அசல் உள்ளீட்டு சமன்பாடு திருப்திகரமாக இருந்தால் மட்டுமே அது திருப்திகரமாக இருக்கும். மாறிகளின் திருப்திகரமான வேலையைக் கண்டறியும்போது, அறிமுகப்படுத்தப்பட்ட மாறிகளுக்கான வேலைகளை வெறுமனே நிராகரிக்க முடியும். ஒரு இறுதி உட்பிரிவு ஒற்றை எழுத்துடன் இணைக்கப்பட்டுள்ளதுஃ இறுதி வாயிலின் வெளியீட்டு மாறி. இந்த இலக்கியம் பூர்த்தி செய்யப்பட்டால், இந்த பிரிவின் திருப்தி வெளியீட்டு வெளிப்பாட்டை பொய்யாக்குகிறது; இல்லையெனில் வெளிப்பாடு கட்டாயமாக உண்மை. எடுத்துக்காட்டுகள் பின்வரும் சூத்திரத்தைக் கவனியுங்கள். அனைத்து துணைச் சூத்திரங்களையும் கருத்தில் கொள்ளுங்கள் (எளிய மாறிகள் தவிர்த்து): ஒவ்வொரு துணைச் சூத்திரத்திற்கும் ஒரு புதிய மாறியை அறிமுகப்படுத்துங்கள்ஃ அனைத்து மாற்றீடுகளையும் இணைக்கவும் மற்றும் அதற்கு மாற்றாகஃ அனைத்து மாற்றீடுகளையும் சிஎன்எஃப் ஆக மாற்றலாம், எ. கா. கேட் துணை வெளிப்பாடுகள் பட்டியலிடப்பட்டுள்ளன, அவை பல்வேறு லாஜிக் வாயில்களுக்கு உருவாக்கக்கூடிய சில சாத்தியமான துணை வெளிப்பாடுகளாகும். செயல்பாட்டு வெளிப்பாட்டில், சி ஒரு வெளியீடாக செயல்படுகிறது; சிஎன்எஃப் துணை வெளிப்பாட்டில், சி ஒரு புதிய பூலியன் மாறியாக செயல்படுகிறது. சாத்தியமான அனைத்து உள்ளீட்டு மதிப்புகளுக்கும் பூலியன் செயல்பாட்டின் ஒப்பந்தத்தை சி பின்பற்றினால் மட்டுமே ஒவ்வொரு செயல்பாட்டிற்கும் சிஎன்எஃப் துணை வெளிப்பாடு உண்மை. எளிய ஒருங்கிணைந்த தர்க்கம் பின்வரும் சுற்று குறைந்தபட்சம் அதன் சில உள்ளீடுகள் உண்மையாக இருக்கும்போது, ஆனால் ஒரு நேரத்தில் இரண்டுக்கு மேல் இல்லை. இது சமன்பாட்டை செயல்படுத்துகிறது. ஒவ்வொரு கேட்டின் வெளியீட்டிற்கும் ஒரு மாறி அறிமுகப்படுத்தப்படுகிறது; இங்கே ஒவ்வொன்றும் சிவப்பு நிறத்தில் குறிக்கப்படுகின்றனஃ x உள்ளீடாக உள்ள இன்வெர்ட்டரின் வெளியீட்டில் இரண்டு மாறிகள் அறிமுகப்படுத்தப்பட்டுள்ளன என்பதைக் கவனியுங்கள். இது தேவையற்றது என்றாலும், இதன் விளைவாக வரும் சமன்பாட்டின் சமச்சீர் திருப்தியை இது பாதிக்காது. இப்போது ஒவ்வொரு கேட்டையும் அதன் பொருத்தமான சிஎன்எஃப் துணை வெளிப்பாட்டுடன் மாற்றவும்ஃ இறுதி வெளியீட்டு மாறி கேட் 8 ஆகும், இதனால் இந்த சுற்றுவட்டத்தின் வெளியீடு உண்மையாக இருக்க வேண்டும், ஒரு இறுதி எளிய பிரிவு இணைக்கப்பட்டுள்ளதுஃ (கேட் 8). இந்த சமன்பாடுகளை இணைப்பது SAT இன் இறுதி நிகழ்வை விளைவிக்கிறதுஃ (கேட்1′x1′x1′x1′x1′x1′x1′x1′x1′x1′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′x2′ இங்கே, உண்மையில் உண்மையான வெளியீட்டிற்கான அசல் சுற்றுக்கான அளவுகோல்களைப் பூர்த்தி செய்கிறது. வேறொரு பதிலைக் கண்டுபிடிக்க, உட்பிரிவு (x1 * x2 *) சேர்க்கப்படலாம் மற்றும் SAT தீர்வு மீண்டும் செயல்படுத்தப்படலாம். வழங்கப்பட்ட வழித்தோன்றல் என்பது சில தேர்ந்தெடுக்கப்பட்ட வாயில்களுக்கு சிஎன்எஃப் துணை வெளிப்பாட்டின் ஒரு சாத்தியமான வழித்தோன்றலாகும்ஃ அல்லது இரண்டு உள்ளீடுகள் ஏ மற்றும் பி மற்றும் ஒரு வெளியீடு சி கொண்ட கேட் ஏ ஓஆர் கேட் பின்வரும் நிபந்தனைகளை பூர்த்தி செய்கிறதுஃ வெளியீடு சி உண்மை என்றால், அதன் உள்ளீடுகளில் குறைந்தபட்சம் ஒன்று ஏ அல்லது பி உண்மை, வெளியீடு சி தவறானது என்றால், அதன் உள்ளீடுகள் ஏ மற்றும் பி இரண்டும் தவறானவை. இந்த இரண்டு நிபந்தனைகளையும் இரண்டு தாக்கங்களின் இணைப்பாக நாம் வெளிப்படுத்தலாம்ஃ இணைப்புகள், விலகல்கள் மற்றும் எதிர்மறைகளை மட்டுமே உள்ளடக்கிய சமமான வெளிப்பாடுகளுடன் தாக்கங்களை மாற்றுவது ஏற்கனவே கிட்டத்தட்ட இணைந்த இயல்பான வடிவத்தில் உள்ளது. வலதுபுற உட்பிரிவை இரண்டு முறை விநியோகிப்பது மற்றும் இணைப்பின் கூட்டுறவைப் பயன்படுத்துவது சிஎன்எஃப் சூத்திரத்தை அளிக்கிறது கேட் அல்ல கேட் அதன் உள்ளீடு மற்றும் வெளியீடு ஒருவருக்கொருவர் எதிர்க்கும்போது சரியாக இயங்குகிறது. அதாவதுஃ வெளியீடு C உண்மை என்றால், உள்ளீடு A தவறானது என்றால் வெளியீடு C தவறானது என்றால், உள்ளீடு A உண்மை என்றால் இந்த நிபந்தனைகளை பூர்த்தி செய்ய வேண்டிய ஒரு வெளிப்பாடாக வெளிப்படுத்தவும்ஃ NOR கேட் பின்வரும் நிபந்தனைகள் இருக்கும்போது NOR கேட் சரியாக இயங்குகிறதுஃ வெளியீடு C உண்மை என்றால், வெளியீடு C தவறானது என்றால் A அல்லது B இரண்டும் உண்மை இல்லை, பின்னர் A மற்றும் B இல் குறைந்தபட்சம் ஒன்று உண்மையாக இருந்தால் இந்த நிபந்தனைகளை பூர்த்தி செய்ய வேண்டிய வெளிப்பாடாக வெளிப்படுத்தவும்ஃ குறிப்புகள் G. S. ட்சேடின்ஃ முன்மொழிவு கால்குலஸில் வழித்தோன்றலின் சிக்கலானது குறித்து. இல்ஃ ஸ்லிஸென்கோ, ஏ. ஓ. (ed.) ஆக்கபூர்வமான கணிதம் மற்றும் கணித தர்க்கத்தில் ஆய்வுகள், பகுதி II, கணிதத்தில் கருத்தரங்குகள், pp. 115-125. ஸ்டெக்லோவ் கணித நிறுவனம் (1970). ரஷ்ய மொழியிலிருந்து மொழிபெயர்க்கப்பட்டதுஃ ஜாபிஸ்கி நௌச்னிக் செமினாரோவ் லோமி 8 (1968), pp. 234-259. ஜி. எஸ். ட்சேடின்ஃ முன்மொழிவு கால்குலஸில் வழித்தோன்றலின் சிக்கலானது குறித்து. செப்டம்பர் 1966 இல் நடைபெற்ற கணித தர்க்கம் குறித்த லெனின்கிராட் கருத்தரங்கில் வழங்கப்பட்டது. கணினி அறிவியலில் லாஜிக் கேட்ஸ் லாஜிக்