Tseytin transformation
ત્સાઇટિન પરિવર્તન, વૈકલ્પિક રીતે ત્સાઇટિન પરિવર્તન લખવામાં આવે છે, જે મનસ્વી સંયોજન તર્ક સર્કિટને ઇનપુટ તરીકે લે છે અને સંયુગ્મ સામાન્ય સ્વરૂપ (સી. એન. એફ.) માં સમાન સંતોષકારક બુલિયન સૂત્ર ઉત્પન્ન કરે છે. સૂત્રની લંબાઈ સર્કિટના કદમાં રેખીય હોય છે. ઇનપુટ વેક્ટર કે જે સર્કિટ આઉટપુટને "સાચું" બનાવે છે તે સોંપણીઓ સાથે 1 થી 1 અનુરૂપ હોય છે જે સૂત્રને સંતોષે છે. આ કોઈપણ સર્કિટ (કોઈપણ સૂત્ર સહિત) પર સર્કિટ સંતોષકારકતાની સમસ્યાને 3-સી. એન. એફ. સૂત્રો પર સંતોષકારક સમસ્યામાં ઘટાડે છે. તેની શોધ રશિયન વૈજ્ઞાનિક ગ્રિગોરી ત્સાઇટિન દ્વારા કરવામાં આવી હતી. નિષ્કપટ અભિગમ એ છે કે સર્કિટને બુલિયન અભિવ્યક્તિ તરીકે લખવી, અને તેને CNF માં રૂપાંતરિત કરવા માટે ડી મોર્ગનના નિયમ અને વિતરણ ગુણધર્મનો ઉપયોગ કરવો. જો કે, આના પરિણામે સમીકરણના કદમાં ઘાતાંકીય વધારો થઈ શકે છે. ત્સેટીન પરિવર્તન એક સૂત્રનું ઉત્પાદન કરે છે જેનું કદ ઇનપુટ સર્કિટની તુલનામાં રેખીય રીતે વધે છે. અભિગમ આઉટપુટ સમીકરણ એ એક અભિવ્યક્તિની બરાબર અચળાંક 1 સમૂહ છે. આ અભિવ્યક્તિ પેટા-અભિવ્યક્તિઓનું સંયોજન છે, જ્યાં દરેક પેટા-અભિવ્યક્તિનો સંતોષ ઇનપુટ સર્કિટમાં એક જ દરવાજાની યોગ્ય કામગીરીને લાગુ કરે છે. સમગ્ર આઉટપુટ અભિવ્યક્તિનો સંતોષ આમ લાગુ કરે છે કે સમગ્ર ઇનપુટ સર્કિટ યોગ્ય રીતે કાર્યરત છે. દરેક દ્વાર માટે, તેના ઉત્પાદનનું પ્રતિનિધિત્વ કરતો નવો ચલ રજૂ કરવામાં આવે છે. એક નાની પૂર્વ-ગણતરી કરેલ CNF અભિવ્યક્તિ જે ઇનપુટ્સ અને આઉટપુટને સંબંધિત કરે છે તે આઉટપુટ અભિવ્યક્તિમાં ("અને" કામગીરી દ્વારા) જોડવામાં આવે છે. નોંધ લો કે આ દરવાજાના ઇનપુટ્સ કાં તો મૂળ શાબ્દિક હોઈ શકે છે અથવા પેટા દરવાજાના આઉટપુટનું પ્રતિનિધિત્વ કરતા રજૂ કરાયેલા ચલ હોઈ શકે છે. જો કે આઉટપુટ અભિવ્યક્તિમાં ઇનપુટ કરતાં વધુ ચલ હોય છે, તે સમાન સંતોષકારક રહે છે, એટલે કે તે સંતોષકારક છે જો, અને માત્ર ત્યારે જ જો મૂળ ઇનપુટ સમીકરણ સંતોષકારક હોય. જ્યારે ચલોનું સંતોષકારક સોંપણી મળે છે, ત્યારે રજૂ કરાયેલા ચલ માટેના તે સોંપણીઓને સરળતાથી કાઢી શકાય છે. અંતિમ કલમ એક જ શાબ્દિક સાથે જોડવામાં આવે છેઃ અંતિમ ગેટનું આઉટપુટ ચલ. જો આ શાબ્દિક પૂરક હોય, તો આ કલમનો સંતોષ આઉટપુટ અભિવ્યક્તિને ખોટી કરવા માટે લાગુ કરે છે; અન્યથા અભિવ્યક્તિને ફરજ પાડવામાં આવે છે. ઉદાહરણો નીચે આપેલા સૂત્રનો વિચાર કરો. તમામ પેટા સૂત્રોનો વિચાર કરો (સરળ ચલને બાદ કરતાં): દરેક પેટા સૂત્ર માટે એક નવું ચલ રજૂ કરો. તમામ અવેજીઓને સંયોજિત કરો અને અવેજી માટેઃ તમામ અવેજીઓને CNFમાં રૂપાંતરિત કરી શકાય છે, દા. ત. ગેટ સબ-એક્સપ્રેશન લિસ્ટેડ એ કેટલીક સંભવિત સબ-એક્સપ્રેશન છે જે વિવિધ લોજિક ગેટ્સ માટે બનાવી શકાય છે. ઓપરેશન અભિવ્યક્તિમાં, સી આઉટપુટ તરીકે કાર્ય કરે છે; સી. એન. એફ. પેટા અભિવ્યક્તિમાં, સી નવા બુલિયન ચલ તરીકે કાર્ય કરે છે. દરેક કામગીરી માટે, સી. એન. એફ. ની પેટા અભિવ્યક્તિ ત્યારે જ સાચી હોય છે જ્યારે સી તમામ સંભવિત ઇનપુટ મૂલ્યો માટે બુલિયન કામગીરીના કરારનું પાલન કરે. સરળ સંયોજન તર્ક નીચેની સર્કિટ ત્યારે સાચું આપે છે જ્યારે તેના ઓછામાં ઓછા કેટલાક ઇનપુટ્સ સાચા હોય, પરંતુ એક સમયે બેથી વધુ નહીં. તે સમીકરણનો અમલ કરે છે. દરેક ગેટના આઉટપુટ માટે ચલ રજૂ કરવામાં આવે છે; અહીં દરેક લાલ રંગમાં ચિહ્નિત થયેલ છેઃ નોંધ લો કે ઇનપુટ તરીકે x સાથે ઇન્વર્ટરના આઉટપુટમાં બે ચલ રજૂ કરવામાં આવ્યા છે. જ્યારે આ બિનજરૂરી છે, તે પરિણામી સમીકરણની સમપ્રમાણતાને અસર કરતું નથી. હવે દરેક ગેટને તેના યોગ્ય CNF પેટા-અભિવ્યક્તિ સાથે બદલોઃ અંતિમ આઉટપુટ ચલ ગેટ 8 છે જેથી આ સર્કિટનું આઉટપુટ સાચું હોય તે લાગુ કરવા માટે, એક અંતિમ સરળ કલમ ઉમેરવામાં આવે છેઃ (ગેટ 8). આ સમીકરણોને જોડીને SAT ના અંતિમ ઉદાહરણમાં પરિણમે છેઃ (ગેટ 1 ′ x 1) ′ (′ x 2) ′ (′ ગેટ 2 ′) ′ (ગેટ 3 ′ x 2) ′ (′ ગેટ 3) ′ (′ ગેટ 4 ′) ′ (ગેટ 5 ′ x 2) ′ (′) ′ (′ ગેટ 5) ′ (′ x 3) ′ (′ ગેટ 6 ′) ′ (ગેટ 7 ′) ′ (ગેટ 7 ′) ′ (ગેટ 7 ′) ′ (ગેટ 7 ′) ′ (ગેટ અહીં, ખરેખર આઉટપુટ સાચા થવા માટે મૂળ સર્કિટ માટેના માપદંડને પૂર્ણ કરે છે. એક અલગ જવાબ શોધવા માટે, કલમ (x1 * x2 *) ને જોડી શકાય છે અને SAT સોલ્વર ફરીથી ચલાવવામાં આવે છે. પ્રસ્તુત વ્યુત્પત્તિ એ કેટલાક પસંદ કરેલા દરવાજાઓ માટે CNF પેટા-અભિવ્યક્તિનું એક સંભવિત વ્યુત્પત્તિ છેઃ અથવા બે ઇનપુટ્સ A અને B અને એક આઉટપુટ C સાથે ગેટ A OR ગેટ નીચેની શરતોને સંતોષે છેઃ જો આઉટપુટ C સાચું હોય, તો તેના ઓછામાં ઓછા એક ઇનપુટ્સ A અથવા B સાચું હોય, જો આઉટપુટ C ખોટું હોય, તો તેના બંને ઇનપુટ્સ A અને B ખોટા હોય છે. આપણે આ બે શરતોને બે અસરોના સંયોજન તરીકે વ્યક્ત કરી શકીએ છીએઃ અસરોને માત્ર સંયોજનો, વિચ્છેદ અને નકારાત્મકતાઓને સમાવતી સમકક્ષ અભિવ્યક્તિઓ સાથે બદલવાથી ઉપજ મળે છે જે લગભગ પહેલાથી જ સામાન્ય સંયોજન સ્વરૂપમાં છે. જમણી બાજુના કલમને બે વાર વિતરણ કરવાથી અને જોડાણની સહયોગીતા લાગુ કરવાથી સી. એન. એફ. સૂત્ર 'નોટ ગેટ' મળે છે જ્યારે તેનું ઇનપુટ અને આઉટપુટ એકબીજાની વિરુદ્ધ હોય ત્યારે 'નોટ ગેટ' યોગ્ય રીતે કાર્ય કરે છે. એટલે કેઃ જો આઉટપુટ C સાચું હોય, તો ઇનપુટ A ખોટો હોય જો આઉટપુટ C ખોટો હોય, તો ઇનપુટ A સાચું હોય તો આ શરતોને અભિવ્યક્તિ તરીકે વ્યક્ત કરો જેને સંતોષવી આવશ્યક છેઃ NOR ગેટ NOR ગેટ યોગ્ય રીતે કાર્યરત છે જ્યારે નીચેની શરતો હોયઃ જો આઉટપુટ C સાચું હોય, તો પછી A અથવા B બંનેમાંથી કોઈ સાચું નથી જો આઉટપુટ C ખોટું હોય, તો પછી A અને B માંથી ઓછામાં ઓછું એક સાચું હોય તો આ શરતોને અભિવ્યક્તિ તરીકે વ્યક્ત કરો જેને સંતોષવી આવશ્યક છેઃ સંદર્ભો G. S. ત્સેટિનઃ પ્રોપોઝિશનલ કેલ્ક્યુલસમાં વ્યુત્પત્તિની જટિલતા પર. માંઃ સ્લિસેન્કો, એઓ. (એડ.) સ્ટડીઝ ઇન કન્સ્ટ્રક્ટિવ મેથેમેટિક્સ એન્ડ મેથેમેટિકલ લોજિક, ભાગ II, ગણિતમાં પરિસંવાદો, pp. 115-125. સ્ટેક્લોવ મેથેમેટિકલ ઇન્સ્ટિટ્યૂટ (1970). રશિયનમાંથી અનુવાદિતઃ ઝાપિસ્કી નૌચનીખ સેમિનારોવ લોમી 8 (1968), પૃષ્ઠ. 234-259. જી. એસ. ત્સેટિનઃ પ્રોપોઝિશનલ કેલ્ક્યુલસમાં વ્યુત્પત્તિની જટિલતા પર. સપ્ટેમ્બર 1966માં આયોજિત મેથેમેટિકલ લોજિક પર લેનિનગ્રાડ સેમિનારમાં રજૂ કરવામાં આવ્યું હતું. કોમ્પ્યુટર વિજ્ઞાનમાં લોજિક ગેટ્સ લોજિક