De Bruijn index
ગાણિતિક તર્કશાસ્ત્રમાં, ડી બ્રુઇજન અનુક્રમણિકા એ ડચ ગણિતશાસ્ત્રી નિકોલાસ ગોવર્ટ ડી બ્રુઇજન દ્વારા શોધાયેલું એક સાધન છે, જે બંધાયેલા ચલોનું નામ આપ્યા વિના લેમ્બડા કલનની શરતોને રજૂ કરે છે. આ સૂચકાંકોનો ઉપયોગ કરીને લખાયેલા શબ્દો α-રૂપાંતરના સંદર્ભમાં અપરિવર્તનશીલ છે, તેથી α-સમાનતા માટેની તપાસ વાક્યરચના સમાનતા માટે સમાન છે. દરેક ડી બ્રુઇજન અનુક્રમણિકા એ એક કુદરતી સંખ્યા છે જે λ-પદમાં ચલની ઘટનાને રજૂ કરે છે, અને તે ઘટના અને તેના અનુરૂપ બંધનકર્તા વચ્ચેના અવકાશમાં રહેલા બંધનકર્તાઓની સંખ્યાને સૂચવે છે. નીચેના કેટલાક ઉદાહરણો છેઃ λx શબ્દ. λy. x, જેને કેટલીકવાર K સંયોજક કહેવામાં આવે છે, તેને ડી બ્રુઇજન સૂચકાંકો સાથે λλ2 તરીકે લખવામાં આવે છે. ઘટના x માટેનું બંધનકર્તા અવકાશમાં બીજું λ છે. શબ્દ λx. λy. λz. ડી બ્રુઇજન સૂચકાંકો સાથે xz (yz) (S સંયોજક) એ λλλ31 (211) છે. શબ્દ λz. (λy. y (λx. x)) (λx. z x) એ λ (λ1 (λ1)) (λ21) છે. નીચેનું ચિત્ર જુઓ, જ્યાં બંધકો રંગીન છે અને સંદર્ભો તીર સાથે દર્શાવવામાં આવ્યા છે. ડી બ્રુઇજન સૂચકાંકોનો ઉપયોગ સામાન્ય રીતે ઓટોમેટેડ થીયરમ પ્રોવર્સ અને લોજિક પ્રોગ્રામિંગ સિસ્ટમ્સ જેવી ઉચ્ચ ક્રમની તર્ક પ્રણાલીઓમાં થાય છે. ઔપચારિક વ્યાખ્યા ઔપચારિક રીતે, ડી બ્રુઇજન સૂચકાંકોનો ઉપયોગ કરીને લખાયેલા λ-શબ્દો (M, N,.) માં નીચેની વાક્યરચના હોય છે (કૌંસને મુક્તપણે મંજૂરી આપવામાં આવે છે): M, N,:: = n | M N | λ M જ્યાં n-0 કરતા મોટી પ્રાકૃતિક સંખ્યાઓ-ચલ છે. એક ચલ n બંધાયેલ છે જો તે ઓછામાં ઓછા n બાઈન્ડર (λ) ના અવકાશમાં હોય; અન્યથા તે મુક્ત છે. ચલ n માટે બંધનકર્તા સ્થળ એ n મો બંધનકર્તા છે જે તેના અવકાશમાં છે, જે સૌથી અંદરના બંધનકર્તાથી શરૂ થાય છે. λ-શરતો પરની સૌથી પ્રાચીન કામગીરી અવેજી છેઃ મુક્ત ચલને અન્ય શરતો સાથે બદલીને. ઉદાહરણ તરીકે, β-ઘટાડો (λM) N માં, આપણે ચલ n1, n2,., nk M માં એવા ઉદાહરણો શોધવા જોઈએ કે જે λM માં λ દ્વારા બંધાયેલા હોય, બાહ્ય λ-બંધનકર્તાને દૂર કરવા સાથે મેળ કરવા માટે M ના મુક્ત ચલને ઘટાડે છે, અને n1, n2,., nk ને N સાથે બદલે છે, દરેક વખતે N માં આવતા મુક્ત ચલને યોગ્ય રીતે વધારીને, λ-બંધનકર્તાઓની સંખ્યા સાથે મેળ ખાય છે, જે હેઠળ અનુરૂપ ચલ ત્યારે થાય છે જ્યારે N એક ni માટે અવેજી કરે છે. સમજાવવા માટે, એપ્લિકેશન (λλ42 (λ13)) (λ51) ને ધ્યાનમાં લો જે સામાન્ય સંકેત (λx) માં લખાયેલા નીચેના શબ્દને અનુરૂપ હોઈ શકે છે. λy. z x (λu. u x)) (λx. ડબલ્યુ એક્સ). પગલું 1 પછી, આપણે λ4· (λ1·) શબ્દ મેળવીએ છીએ, જ્યાં અવેજી માટે નિર્ધારિત ચલોને બોક્સ સાથે બદલવામાં આવે છે. પગલું 2 મુક્ત ચલને ઘટાડે છે, જે λ3⁄2 (λ1⁄2) આપે છે. છેવટે, પગલું 3 માં, આપણે બોક્સને દલીલ સાથે બદલીએ છીએ, એટલે કે λ51; પ્રથમ બોક્સ એક બાઈન્ડર હેઠળ છે, તેથી આપણે તેને λ61 સાથે બદલીએ છીએ (જે λ51 છે અને ફ્રી વેરિયેબલ્સમાં 1 નો વધારો થાય છે); બીજું બે બાઈન્ડર હેઠળ છે, તેથી આપણે તેને λ71 સાથે બદલીએ છીએ. અંતિમ પરિણામ λ3 (λ61) (λ1 (λ71)) છે. ઔપચારિક રીતે, અવેજી એ શબ્દોની અમર્યાદિત સૂચિ છે, જે M1.M2. લખવામાં આવે છે, જ્યાં Mi એ ith મુક્ત ચલ માટે અવેજી છે. પગલું 3 માં વધતી જતી કામગીરીને કેટલીકવાર શિફ્ટ અને લેખિત k કહેવામાં આવે છે જ્યાં k એ એક કુદરતી સંખ્યા છે જે ચલને વધારવા માટેની રકમ સૂચવે છે, અને તેના દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. M1.M2.Mn શબ્દોની મર્યાદિત સૂચિ અવેજી M1.M2.Mn. (n + 1). (n + 2) ને સંક્ષિપ્ત કરે છે. n કરતા મોટા તમામ ચલને અપરિવર્તિત રાખીને. M શબ્દ માટે અવેજી s નો ઉપયોગ M [s] લખવામાં આવે છે. બે અવેજીઓ s1 અને s2 ની રચના s1s2 લખવામાં આવે છે અને તેને (M1.M2.) s = M1 [s]. M2 [s] દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. ગુણધર્મ M [s1s2] = (M [s1]) [s2] ને સંતોષ આપે છે, અને અવેજીને નીચેની શરતો પર વ્યાખ્યાયિત કરવામાં આવે છેઃ ઉપરના β-ઘટાડા માટે દર્શાવેલ પગલાંઓ આમ વધુ સંક્ષિપ્તમાં આ રીતે વ્યક્ત કરવામાં આવે છેઃ (λM) N → βM [N]. ડી બ્રુઇજન સૂચકાંકોના વિકલ્પો જ્યારે λ-શબ્દોની પ્રમાણભૂત "નામવાળી" રજૂઆતનો ઉપયોગ કરવામાં આવે છે, જ્યાં ચલને લેબલ અથવા શબ્દમાળા તરીકે ગણવામાં આવે છે, ત્યારે શરતો પર કોઈપણ કામગીરીને વ્યાખ્યાયિત કરતી વખતે સ્પષ્ટપણે α-રૂપાંતરને નિયંત્રિત કરવું આવશ્યક છે. વ્યવહારમાં આ બોજારૂપ, બિનકાર્યક્ષમ અને ઘણીવાર ભૂલગ્રસ્ત હોય છે. તેથી તે આવા શબ્દોની વિવિધ રજૂઆતોની શોધ તરફ દોરી ગયું છે. બીજી બાજુ, λ-શબ્દોની નામાંકિત રજૂઆત વધુ વ્યાપક છે અને અન્ય લોકો દ્વારા વધુ તરત સમજી શકાય છે કારણ કે ચલને વર્ણનાત્મક નામો આપી શકાય છે. આમ, જો કોઈ સિસ્ટમ આંતરિક રીતે ડી બ્રુઇજન સૂચકાંકોનો ઉપયોગ કરે તો પણ, તે નામો સાથે વપરાશકર્તા ઇન્ટરફેસ રજૂ કરશે. ડી બ્રુઇજન સૂચકાંકોને જોવાની વૈકલ્પિક રીત ડી બ્રુઇજન સ્તરો તરીકે છે, જે ટોચથી બદલે સ્ટેકના તળિયેથી ચલ સૂચિબદ્ધ કરે છે. આ રીઇન્ડેક્સ ફ્રી વેરિયેબલ્સની જરૂરિયાતને દૂર કરે છે, ઉદાહરણ તરીકે જ્યારે સંદર્ભ નબળો પડે છે, જ્યારે ડી બ્રુઇજન સૂચકાંકો રીઇન્ડેક્સ બાઉન્ડ વેરિયેબલ્સની જરૂરિયાતને દૂર કરે છે, ઉદાહરણ તરીકે જ્યારે અન્ય સંદર્ભમાં ક્લોઝ્ડ એક્સપ્રેશનને બદલવામાં આવે છે. ડી બ્રુઇજન સૂચકાંકો એ λ-શરતોની એકમાત્ર રજૂઆત નથી જે α-રૂપાંતરની સમસ્યાને દૂર કરે છે. નામાંકિત રજૂઆતોમાં, પિટ્સ અને ગબ્બેની નજીવી તકનીકો એક અભિગમ છે, જ્યાં λ-પદની રજૂઆતને ચલ ક્રમચયો ઉપયોગ કરીને તેને ફરીથી લખી શકાય તેવા તમામ શબ્દોના સમકક્ષ વર્ગ તરીકે ગણવામાં આવે છે. આ અભિગમ ઇસાબેલ/એચઓએલના નોમિનલ ડેટાટાઇપ પેકેજ દ્વારા લેવામાં આવે છે. બીજો સામાન્ય વિકલ્પ ઉચ્ચ-ક્રમની રજૂઆત માટે અપીલ છે જ્યાં λ-બંધનકર્તાને સાચા કાર્ય તરીકે ગણવામાં આવે છે. આવી રજૂઆતોમાં, α-સમાનતા, અવેજી, વગેરેના મુદ્દાઓ. મેટા-લોજિકમાં સમાન કામગીરીઓ સાથે ઓળખવામાં આવે છે. પ્રૂફ આસિસ્ટન્ટમાં ડિડક્ટિવ સિસ્ટમના મેટા-થિયોરેટિક ગુણધર્મો વિશે તર્ક કરતી વખતે, કેટલીકવાર પોતાને ફર્સ્ટ-ઓર્ડર રજૂઆતો સુધી મર્યાદિત રાખવા અને ધારણાઓને નામ આપવાની અથવા તેનું નામ બદલવાની ક્ષમતા હોવી ઇચ્છનીય છે. સ્થાનિક રીતે નામહીન અભિગમ ચલની મિશ્ર રજૂઆતનો ઉપયોગ કરે છે-બંધાયેલા ચલ માટે ડી બ્રુઇજન સૂચકાંકો અને મુક્ત ચલ માટેના નામો-જે યોગ્ય હોય ત્યારે ડી બ્રુઇજન અનુક્રમિત શબ્દોના α-કેનોનિકલ સ્વરૂપથી લાભ મેળવવા માટે સક્ષમ હોય છે. બેરેન્ડ્રેગ્ટનું ચલ સંમેલન બેરેન્ડ્રેગ્ટનું ચલ સંમેલન એ સામાન્ય રીતે પુરાવાઓ અને વ્યાખ્યાઓમાં ઉપયોગમાં લેવાતું એક સંમેલન છે જ્યાં એવું માનવામાં આવે છે કેઃ બંધાયેલા ચલ મુક્ત ચલથી અલગ છે, અને તમામ બંધનકર્તાઓ એવા ચલને બાંધે છે જે પહેલેથી જ અવકાશમાં નથી. પ્રેરક વ્યાખ્યાના સામાન્ય સંદર્ભમાં, જ્યાં પરંપરાનો ઉપયોગ થતો નથી ત્યાં પરંપરાનો ઉપયોગ કરીને પ્રેરક વ્યાખ્યાને રૂપાંતરિત કરવા માટે જરૂરી α-રૂપાંતર લાગુ કરવું શક્ય નથી, કારણ કે ચલ બંધનકર્તા સ્થિતિ અને બિન-બંધનકર્તા સ્થિતિ બંનેમાં દેખાઈ શકે છે. જો દરેક નિયમ નીચેની બે શરતોને સંતોષે તો ઇન્ડક્શન સિદ્ધાંત લાગુ પડે છેઃ નોમિનલ લોજિકના અર્થમાં નિયમ સમાન છે, એટલે કે નિયમના પરિસરને ધારીને ચલોનું નામ બદલીને તેની માન્યતા બદલાતી નથી, નિયમમાં બંધનકર્તા સ્થિતિઓમાં ચલ અલગ છે અને નિષ્કર્ષમાં મુક્ત છે. સંયોજી તર્ક, ચલ નામોને દૂર કરવાની વધુ આવશ્યક રીત છે. સંદર્ભો લામ્બડા કલન