शब्द बीजगणित

सार्वभौमिक बीजगणित और गणितीय लॉजिक में, शब्द बीजगणित दिए गए संकेत चिन्ह (लॉजिक) पर एक स्वतंत्र रूप से निर्मित बीजगणितीय संरचना है। उदाहरण के लिए, किसी संकेत चिन्ह (गणितीय लॉजिक) में एक एकल बाइनरी संक्रिया संचरण सम्मिलित है, चर के एक वर्ग समूह x पर बीजगणित शब्द निश्चित x द्वारा निर्मित मुक्त मैग्मा है। धारणा के लिए अन्य समानार्थक शब्द 'निश्चित मुक्त बीजगणित' और 'अराजक बीजगणित' सम्मिलित हैं। श्रेणी सिद्धांत परिप्रेक्ष्य से, एक शब्द बीजगणित एक ही संकेत चिन्ह के सभी x-निर्मित किए गए बीजगणितों की एफ-बीजगणित श्रेणी के लिए प्रारंभिक वस्तु है, और यह वस्तु, समरूपता तक अद्वितीय है, प्रारंभिक बीजगणित कहा जाता है; यह होमोमोर्फिक प्रोजेक्शन द्वारा श्रेणी में सभी बीजगणित निर्मित करता है। इसी तरह की धारणा लॉजिक में हेरब्रांड ब्रह्मांड की है, सामान्यतः इस नाम के तहत लॉजिक प्रोग्रामिंग में प्रयोग किया जाता है, जो (निश्चित स्वतंत्र रूप से) खंड (लॉजिक) के एक वर्ग समूह में स्थिरांक और फलन प्रतीकों के वर्ग समूह से प्रारम्भ होता है अर्थात्, हरब्रांड ब्रह्मांड में सभी मूलभूत शब्द सम्मिलित हैं: ऐसे शब्द जिनमें कोई चर नहीं है।

एक परमाणु सूत्र या परमाणु को सामान्यतः शब्दों के एक समूह पर लागू एक तार्किक नियम (गणितीय लॉजिक) के रूप में परिभाषित किया जाता है; मूलभूत परमाणु एक तार्किक नियम है जिसमें केवल मूलभूत शब्द दिखाई देते हैं। हेरब्रांड आधार सभी ग्राउंड परमाणुओं का वर्ग समूह है जो अपने हेरब्रांड ब्रह्मांड में खंडों और शर्तों के मूल वर्ग समूह में तार्किक नियम प्रतीकों से बनाया जा सकता है। इन दो अवधारणाओं का नाम जैक्स हर्ब्रांड के नाम पर रखा गया है।

शब्द बीजगणित भी संक्षिप्त डेटा प्रकार के शब्दार्थ में एक भूमिका निभाते हैं, जहां एक संक्षिप्त डेटा प्रकार की घोषणा एक बहु-क्रमबद्ध बीजगणितीय संरचना का संकेत चिन्ह प्रदान करती है और बीजगणित शब्द अमूर्त घोषणा का एक ठोस मॉडल है। बीजगणित का वह भेद जिसमें अक्षरों को संख्याओं का द्योतक मानकर कुछ सांकेतिक चिह्नों और निश्चित युक्तियों के द्वारा गणना की जाती है और विशेषतः निश्चित संख्याएँ आदि जानी जाती है ।

सार्वभौमिक बीजगणित

प्रकार $\tau$ फलन प्रतीकों का एक वर्ग समूह है, जिनमें से प्रत्येक में एक संबद्धता (अर्थात इनपुट की संख्या) है। किसी भी गैर-ऋणात्मक पूर्णांक के लिए $n$, माना कि $\tau _{n}$ में फलन प्रतीकों को निरूपित करें $\tau$ प्रदाता की $n$. एक स्थिरांक एरिटी 0 का एक फलन प्रतीक है।

माना कि $\tau$ एक प्रकार, और माना कि $X$ चर प्रतीकों का प्रतिनिधित्व करने वाले प्रतीकों का एक गैर-खाली वर्ग समूह बनें। (सरलता के लिए, मान लीजिए $X$ और $\tau$ असंयुक्त हैं।) फिर टर्म (लॉजिक) का वर्ग समूह $T(X)$ प्रकार का $\tau$ ऊपर $X$ सभी अच्छी तरह से निर्मित स्ट्रिंग (कंप्यूटर विज्ञान) का वर्ग समूह है जिसे चर प्रतीकों का उपयोग करके बनाया जा सकता है $X$ और $\tau$ के स्थिरांक और संचालन औपचारिक रूप से, $T(X)$ सबसे छोटा समुच्चय है कि:

• $X\cup \tau _{0}\subseteq T(X)$ - प्रत्येक चर प्रतीक से $X$ में एक पद है $T(X)$, और इसलिए प्रत्येक स्थिर प्रतीक $\tau _{0}$ से है.
• सभी के लिए $n\geq 1$ और सभी फलन प्रतीकों के लिए $f\in \tau _{n}$ और शर्तें $t_{1},...,t_{n}\in T(X)$, हमारे पास स्ट्रिंग है $f(t_{1},...,t_{n})\in T(X)$ - दिया गया $n$ शर्तें $t_{1},...,t_{n}$, एक का आवेदन $n$-समूह फलन प्रतीक $f$ उनके लिए फिर से एक शब्द का प्रतिनिधित्व करता है।

बीजगणित शब्द ${\mathcal {T}}(X)$ प्रकार का $\tau$ ऊपर $X$ संक्षेप में, प्रकार का बीजगणित है $\tau$ जो प्रत्येक अभिव्यक्ति को उसके स्ट्रिंग प्रतिनिधित्व में मैप करता है। औपचारिक रूप से, ${\mathcal {T}}(X)$ निम्नानुसंक्षिप्त परिभाषित किया गया है:

• ${\mathcal {T}}(X)$ का डोमेन $T(X)$ है.
• प्रत्येक अशक्त कार्य के लिए $f$ में $\tau _{0}$, $f^{{\mathcal {T}}(X)}()$ स्ट्रिंग के रूप में $f$ परिभाषित किया गया है.
• सभी के लिए $n\geq 1$ और प्रत्येक एन-आरी फलन के लिए $f$ में $\tau$ और तत्व $t_{1},...,t_{n}$ डोमेन में, $f^{{\mathcal {T}}(X)}(t_{1},...,t_{n})$ स्ट्रिंग के रूप में परिभाषित किया गया है $f(t_{1},...,t_{n})$.

एक शब्द बीजगणित को निश्चित मुक्त कहा जाता है क्योंकि किसी भी बीजगणित के लिए ${\mathcal {A}}$ प्रकार का $\tau$, और किसी भी फलन के लिए $g:X\to {\mathcal {A}}$, $g$ एक अद्वितीय समरूपता तक फैली हुई है $g^{\ast }:{\mathcal {T}}(X)\to {\mathcal {A}}$, जो केवल प्रत्येक शब्द का मूल्यांकन करता है $t\in {\mathcal {T}}(X)$ इसके संगत मूल्य के लिए $g^{\ast }(t)\in {\mathcal {A}}$. औपचारिक रूप से, प्रत्येक के लिए $t\in {\mathcal {T}}(X)$:

• अगर $t\in X$, तब $g^{\ast }(t)=g(t)$.
• अगर $t=f\in \tau _{0}$, तब $g^{\ast }(t)=f^{\mathcal {A}}()$.
• अगर $t=f(t_{1},...,t_{n})$ कहाँ $f\in \tau _{n}$ और $n\geq 1$, तब $g^{\ast }(t)=f^{\mathcal {A}}(g^{\ast }(t_{1}),...,g^{\ast }(t_{n}))$.

उदाहरण

एक उदाहरण के रूप में पूर्णांक अंकगणित से प्रेरित प्रकार द्वारा परिभाषित किया जा सकता है $\tau _{0}=\{0,1\}$, $\tau _{1}=\{\}$, $\tau _{2}=\{+,*\}$, और $\tau _{i}=\{\}$ प्रत्येक के लिए $i>2$.

प्रकार का सबसे प्रसिद्ध बीजगणित $\tau$ इसके डोमेन के रूप में प्राकृतिक संख्याएं हैं और इसकी व्याख्या करता है $0$, $1$, $+$, और $*$ सामान्य तरीके से; हम इसका उल्लेख करते हैं ${\mathcal {A}}_{nat}$.

उदाहरण चर वर्ग समूह के लिए $X=\{x,y\}$, हम बीजगणित शब्द की जांच करने जा रहे हैं ${\mathcal {T}}(X)$ प्रकार का $\tau$ ऊपर $X$.

सबसे पहले, वर्ग समूह $T(X)$ प्रकार की शर्तों का $\tau$ ऊपर $X$ माना जाता है। हम लाल रंग उपयोग करते हैं, अपने सदस्यों को फ़्लैग करने के लिए, जिन्हें अन्यथा उनके असामान्य वाक्यात्मक रूप के कारण पहचानना कठिन हो सकता है। हमारे पास उदा.

• ${\color {red}x}\in T(X)$, तब से $x\in X$ एक चर प्रतीक है;
• ${\color {red}1}\in T(X)$, तब से $1\in \tau _{0}$ एक स्थिर प्रतीक है; इस तरह
• ${\color {red}+x1}\in T(X)$, तब से $+$ एक 2-समूह फलन प्रतीक है; इसलिए, बदले में,
• ${\color {red}*+x1x}\in T(X)$ तब से $*$ एक 2-समूह फलन प्रतीक है।

अधिक सामान्यतः, प्रत्येक स्ट्रिंग में $T(X)$ स्वीकृत प्रतीकों से निर्मित और पोलिश उपसर्ग संकेतन में लिखे गए गणितीय अभिव्यक्ति से समानता रखता है; उदाहरण के लिए, शब्द ${\color {red}*+x1x}$ अभिव्यक्ति से समानता रखता है $(x+1)*x$ सामान्य इंफिक्स नोटेशन में। पोलिश संकेतन में अस्पष्टता से बचने के लिए किसी कोष्ठक की आवश्यकता नहीं है; उदा. इन्फिक्स अभिव्यक्ति $x+(1*x)$ पद से ${\color {red}+x*1x}$ इसी प्रकार समानता रखता है।

कुछ प्रति-उदाहरण देने के लिए, हमारे पास उदा,

• ${\color {red}z}\not \in T(X)$, तब से $z$ न तो एक स्वीकृत चर प्रतीक है और न ही एक स्वीकृत स्थिर प्रतीक;
• ${\color {red}3}\not \in T(X)$, इसी कारण से,
• ${\color {red}+1}\not \in T(X)$, तब से $+$ एक 2-समूह फलन प्रतीक है, लेकिन यहां केवल एक लॉजिक शब्द के साथ प्रयोग किया जाता है (अर्थात ${\color {red}1}$).

अब यह शब्द निर्धारित है $T(X)$ स्थापित हो गया है, तो हम बीजगणित शब्द पर विचार करते हैं ${\mathcal {T}}(X)$ प्रकार का $\tau$ ऊपर $X$. यह बीजगणित $T(X)$ उपयोग करता है, इसके डोमेन के रूप में, जिस पर जोड़ और गुणा को परिभाषित करने की आवश्यकता है। अतिरिक्त फलन $+^{{\mathcal {T}}(X)}$ दो शब्द लेता है, $p$ और $q$ और ${\color {red}+}pq$ अवधि लौटाता है; इसी प्रकार, गुणन फलन $*^{{\mathcal {T}}(X)}$ दिए गए नक्शे $p$ और $q$ अवधि के लिए ${\color {red}*}pq$. उदाहरण के लिए, $*^{{\mathcal {T}}(X)}({\color {red}+x1},{\color {red}x})$ अवधि का मूल्यांकन ${\color {red}*+x1x}$ इसी प्रकार करता है।

एक समरूपता के अद्वितीय विस्तार के लिए एक उदाहरण के रूप में विचार करें $g:X\to {\mathcal {A}}_{nat}$ द्वारा परिभाषित $g(x)=7$ और $g(y)=3$.अनौपचारिक रूप से, $g$ वेरिएबल सिंबल के लिए मानों के असाइनमेंट को परिभाषित करता है, और एक बार यह पूरा हो जाने के बाद, प्रत्येक शब्द से $T(X)$ में अनोखे तरीके से मूल्यांकन किया जा सकता है ${\mathcal {A}}_{nat}$. उदाहरण के लिए,

${\begin{array}{lll}&g^{*}({\color {red}+x1})\\=&g^{*}({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&g({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ coincides on }}X{\text{ with }}g\\=&7+g^{*}({\color {red}1})&{\text{ by definition of }}g\\=&7+1&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&8&{\text{ according to the well-known arithmetical rules in }}{\mathcal {A}}_{nat}\\\end{array}}$

इसी प्रकार व्यक्ति को प्राप्त होता है $g^{*}({\color {red}*+x1x})=...=8*g({\color {red}x})=...=56$.

हेरब्रांड बेस

Main articles: हरब्रांड व्याख्या and हरब्रांड संरचना

एक भाषा का संकेत चिन्ह σ एक ट्रिपल <O, F, P> है जिसमें स्थिरांक O, फलन प्रतीक F' की वर्णमाला सम्मिलित है ', और 'p' की भविष्यवाणी करता है। हरब्रांड बेस एक संकेत चिन्ह के σ में σ के सभी मूलभूत परमाणु होते हैं: R(t₁, ..., tn), जहां t₁, ..., tn ऐसे शब्द हैं जिनमें कोई चर नहीं है (अर्थात हरब्रांड ब्रह्मांड के तत्व) और R एक n-आरी संबंध प्रतीक है (अर्थात तार्किक नियम (गणितीय लॉजिक))। समानता के साथ लॉजिक के मामले में, इसमें फॉर्म t₁ के सभी समीकरण भी सम्मिलित हैं= t₂, जहां t₁ और t₂ कोई चर नहीं है।

निर्णायकता

शब्द बीजगणित को क्वांटिफायर उन्मूलन का उपयोग करके निर्णायक दिखाया जा सकता है। निर्णय समस्या की जटिलता गैर-प्रारम्भिक में है क्योंकि बाइनरी कंस्ट्रक्टर इंजेक्शन हैं और इस प्रकार युग्मन कार्य करते हैं।

यह भी देखें

• उत्तर-वर्ग समूह प्रोग्रामिंग
• क्लोन (बीजगणित)
• लेख / ब्रह्मांड (गणित) का डोमेन
• राबिन के ट्री प्रमेय (अनंत पूर्ण द्विआधारी ट्री का मठ सिद्धांत निर्णायक है)
• प्रारंभिक बीजगणित
• संक्षिप्त डेटा प्रकार
• टर्म पुनर्लेखन प्रणाली

अग्रिम पठन

• Joel Berman (2005). "The structure of free algebras". In Structural Theory of Automata, Semigroups, and Universal Algebra. Springer. pp. 47–76. MR2210125.

बाहरी संबंध

• Weisstein, Eric W. "Herbrand Universe". MathWorld.