तर्क प्रोग्रामिंग का सिंटैक्स और शब्दार्थ: Difference between revisions

From Vigyanwiki
(Created page with "{{more footnotes|date=March 2023}} {{Short description|Formal semantics of logic programming languages}} तर्क प्रोग्रामिंग एक प...")
 
No edit summary
 
(15 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{more footnotes|date=March 2023}}
{{Short description|Formal semantics of logic programming languages}}
{{Short description|Formal semantics of logic programming languages}}


[[ तर्क प्रोग्रामिंग ]] एक [[प्रोग्रामिंग प्रतिमान]] है जिसमें [[संगणक वैज्ञानिक]] और [[प्रोलॉग]] सहित औपचारिक तर्क पर आधारित भाषाएं शामिल हैं। यह आलेख इन भाषाओं के विशुद्ध रूप से [[घोषणात्मक प्रोग्रामिंग]] उपसमुच्चय के वाक्यविन्यास और शब्दार्थ का वर्णन करता है। भ्रमित करने वाली बात यह है कि लॉजिक प्रोग्रामिंग नाम भी एक को संदर्भित करता है {{em|specific}} प्रोग्रामिंग भाषा जो मोटे तौर पर प्रोलॉग के घोषणात्मक उपसमुच्चय से मेल खाती है। दुर्भाग्य से, इस लेख में इस शब्द का प्रयोग दोनों अर्थों में किया जाना चाहिए।
[[ तर्क प्रोग्रामिंग ]]एक [[प्रोग्रामिंग प्रतिमान]] है जिसमें [[Index.php?title=डाटालॉग|डाटालॉग]] और [[प्रोलॉग]] सहित औपचारिक तर्क पर आधारित लैंग्वेजेज सम्मलित हैं। यह आलेख इन लैंग्वेजेज के विशुद्ध रूप से [[Index.php?title=घोषणात्मक|घोषणात्मक]] उपसमुच्चय के वाक्यविन्यास और शब्दार्थ का वर्णन करता है। भ्रामक रूप से, लॉजिक प्रोग्रामिंग नाम एक विशिष्ट प्रोग्रामिंग लैंग्वेज को भी संदर्भित करता है जो लगभग प्रोलॉग के घोषणात्मक उपसमुच्चय से मेल खाती है। दुर्भाग्य से, इस लेख में इस शब्द का प्रयोग दोनों अर्थों में किया जाना चाहिए।


घोषणात्मक तर्क कार्यक्रम पूरी तरह से प्रपत्र के नियमों से युक्त होते हैं
घोषणात्मक तर्क कार्यक्रम पूरी तरह से प्रपत्र के नियमों से युक्त होते हैं
Line 10: Line 8:
H :- B1, ..., BN.
H :- B1, ..., BN.
</syntaxhighlight>
</syntaxhighlight>
ऐसे प्रत्येक नियम को [[सामग्री सशर्त]] के रूप में पढ़ा जा सकता है:
ऐसे प्रत्येक नियम को एक [[Index.php?title=निहितार्थ|निहितार्थ]] के रूप में पढ़ा जा सकता है:


:<math>B_1\land\ldots\land B_n\rightarrow H</math>
:<math>B_1\land\ldots\land B_n\rightarrow H</math>
मतलब यदि प्रत्येक <math>B_i</math> तो फिर सच है <math>H</math> क्या सच है । लॉजिक प्रोग्राम उन तथ्यों के समूह की गणना करते हैं जो उनके नियमों द्वारा निहित हैं।
जिसका अर्थ है यदि प्रत्येक <math>B_i</math>, <math>H</math> ट्रूथ है । फिर लॉजिक प्रोग्राम उन तथ्यों के समूह की गणना करते हैं जो उनके नियमों द्वारा निहित हैं।


डेटालॉग, प्रोलॉग और संबंधित भाषाओं के कई कार्यान्वयन प्रोलॉग [[ कट (तर्क प्रोग्रामिंग) ]] या [[विदेशी फ़ंक्शन इंटरफ़ेस]] जैसी अतिरिक्त-तार्किक सुविधाओं जैसी प्रक्रियात्मक विशेषताएं जोड़ते हैं। ऐसे एक्सटेंशन का औपचारिक शब्दार्थ इस लेख के दायरे से बाहर है।
डेटालॉग, प्रोलॉग और संबंधित लैंग्वेजेज के कई कार्यान्वयन प्रोलॉग के [[Index.php?title=कट ऑपरेटर|कट ऑपरेटर]] या [[Index.php?title= फोरेइग्नर फ़ंक्शन इंटरफ़ेस|फोरेइग्नर फ़ंक्शन इंटरफ़ेस]] जैसी अतिरिक्त-तार्किक सुविधाओं जैसी प्रक्रियात्मक विशेषताएं जोड़ते हैं। ऐसे एक्सटेंशन का औपचारिक शब्दार्थ इस लेख के दायरे से बाहर है।


== डेटालॉग ==
== डेटालॉग ==
{{main|Datalog}}
{{main|
डेटालॉग}}


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


=== सिंटेक्स ===
=== सिंटेक्स ===


डेटालॉग प्रोग्राम में नियमों ([[ हॉर्न उपवाक्य ]]) की एक सूची होती है।{{sfn|Ceri|Gottlob|Tanca|1989|p=146}} यदि स्थिरांक और चर क्रमशः स्थिरांक और चर के दो गणनीय सेट हैं और संबंध [[विधेय चर]] का एक गणनीय सेट है, तो निम्नलिखित [[बीएनएफ व्याकरण]] डेटालॉग प्रोग्राम की संरचना को व्यक्त करता है:
डेटालॉग प्रोग्राम में नियमों की एक सूची होती है।{{sfn|Ceri|Gottlob|Tanca|1989|p=146}} यदि स्थिरांक और चर क्रमशः स्थिरांक और चर के दो गणनीय सेट हैं और संबंध [[विधेय चर]] का एक गणनीय सेट है, तो निम्नलिखित [[Index.php?title=BNF ग्रामर|BNF ग्रामर]] डेटालॉग प्रोग्राम की संरचना को व्यक्त करता है:


<syntaxhighlight lang="bnf">
<syntaxhighlight lang="bnf">
Line 34: Line 33:
<term-list> ::= <term> | <term> "," <term-list> | ""
<term-list> ::= <term> | <term> "," <term-list> | ""
</syntaxhighlight>
</syntaxhighlight>
परमाणुओं को भी कहा जाता है {{dfni|literals}}. के बाईं ओर परमाणु <code>:-</code> प्रतीक को कहा जाता है {{dfni|head}}नियम का; दाहिनी ओर के परमाणु हैं {{dfni|body}}. प्रत्येक डेटालॉग प्रोग्राम को इस शर्त को पूरा करना होगा कि नियम के शीर्ष में दिखाई देने वाला प्रत्येक चर बॉडी में भी दिखाई देता है (इस स्थिति को कभी-कभी कहा जाता है) {{dfni|range restriction}}).{{sfn|Ceri|Gottlob|Tanca|1989|p=146}}<ref>{{Cite journal |last1=Eisner |first1=Jason |last2=Filardo |first2=Nathaniel W. |date=2011 |editor-last=de Moor |editor-first=Oege |editor2-last=Gottlob |editor2-first=Georg |editor3-last=Furche |editor3-first=Tim |editor4-last=Sellers |editor4-first=Andrew |title=Dyna: Extending Datalog for Modern AI |url=https://link.springer.com/chapter/10.1007/978-3-642-24206-9_11 |journal=Datalog Reloaded |series=Lecture Notes in Computer Science |volume=6702 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=181–220 |doi=10.1007/978-3-642-24206-9_11 |isbn=978-3-642-24206-9}}</ref>
एटमों को शाब्दिक भी कहा जाता है। लिट्रल. के बाईं ओर एटम को नियम का <code>:-</code> हेड  कहा जाता है; दाहिनी ओर के एटम {{dfni| समूह}} हैं। प्रत्येक डेटालॉग प्रोग्राम को इस शर्त को पूरा करना होगा कि नियम के शीर्ष में दिखाई देने वाला प्रत्येक चर मुख्य भाग में भी दिखाई देता है।<ref>{{Cite journal |last1=Eisner |first1=Jason |last2=Filardo |first2=Nathaniel W. |date=2011 |editor-last=de Moor |editor-first=Oege |editor2-last=Gottlob |editor2-first=Georg |editor3-last=Furche |editor3-first=Tim |editor4-last=Sellers |editor4-first=Andrew |title=Dyna: Extending Datalog for Modern AI |url=https://link.springer.com/chapter/10.1007/978-3-642-24206-9_11 |journal=Datalog Reloaded |series=Lecture Notes in Computer Science |volume=6702 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=181–220 |doi=10.1007/978-3-642-24206-9_11 |isbn=978-3-642-24206-9}}</ref>
खाली शरीर वाले नियम कहलाते हैं {{dfni|facts}}. उदाहरण के लिए, निम्नलिखित नियम एक तथ्य है:
 
खाली निकाय वाले नियमों को तथ्य कहा जाता है। उदाहरण के लिए, निम्नलिखित नियम एक तथ्य है:
<syntaxhighlight lang="prolog">
<syntaxhighlight lang="prolog">
r(x) :- .
r(x) :- .
Line 43: Line 43:
==== सिंटैक्टिक शुगर ====
==== सिंटैक्टिक शुगर ====


तर्क प्रोग्रामिंग के कई कार्यान्वयन बिना तथ्यों को लिखने की अनुमति देने के लिए उपरोक्त व्याकरण का विस्तार करते हैं <code>:-</code>, जैसे इतना:
तर्क प्रोग्रामिंग के कई कार्यान्वयन बिना तथ्यों को लिखने की अनुमति देने के लिए उपरोक्त व्याकरण का विस्तार करते हैं <code>:-</code>, जैसे:


<syntaxhighlight lang="prolog">
<syntaxhighlight lang="prolog">
Line 71: Line 71:
=== शब्दार्थ ===
=== शब्दार्थ ===


डेटालॉग कार्यक्रमों के शब्दार्थ के लिए तीन व्यापक रूप से उपयोग किए जाने वाले दृष्टिकोण हैं: [[मॉडल सिद्धांत]]|मॉडल-सैद्धांतिक, [[निश्चित बिंदु (गणित)]]|निश्चित-बिंदु, और [[प्रमाण-सिद्धांत संबंधी शब्दार्थ]]|प्रमाण-सिद्धांत। ये तीन दृष्टिकोण समतुल्य सिद्ध हो सकते हैं।<ref>{{Cite journal |last1=van Emden |first1=M. H. |last2=Kowalski |first2=R. A. |date=1976-10-01 |title=एक प्रोग्रामिंग भाषा के रूप में विधेय तर्क का शब्दार्थ|url=https://doi.org/10.1145/321978.321991 |journal=Journal of the ACM |volume=23 |issue=4 |pages=733–742 |doi=10.1145/321978.321991 |s2cid=11048276 |issn=0004-5411}}</ref>
डेटालॉग कार्यक्रमों के शब्दार्थ के लिए तीन व्यापक रूप से उपयोग किए जाने वाले दृष्टिकोण हैं: [[Index.php?title=मॉडल-सैद्धांतिक|मॉडल-सैद्धांतिक]], [[Index.php?title=निश्चित बिंदु|निश्चित बिंदु]] , और [[Index.php?title=प्रमाण-सिद्धांत संबंधी|प्रमाण-सिद्धांत संबंधी]] है। ये तीन दृष्टिकोण समतुल्य प्रमाणित हो सकते हैं।<ref>{{Cite journal |last1=van Emden |first1=M. H. |last2=Kowalski |first2=R. A. |date=1976-10-01 |title=एक प्रोग्रामिंग भाषा के रूप में विधेय तर्क का शब्दार्थ|url=https://doi.org/10.1145/321978.321991 |journal=Journal of the ACM |volume=23 |issue=4 |pages=733–742 |doi=10.1145/321978.321991 |s2cid=11048276 |issn=0004-5411}}</ref>
परमाणु कहा जाता है {{dfni|[[Ground atom|ground]]}} यदि इसका कोई भी उपपद चर नहीं है। सहज रूप से, प्रत्येक शब्दार्थ एक कार्यक्रम के अर्थ को उन सभी जमीनी परमाणुओं के सेट के रूप में परिभाषित करता है जिन्हें तथ्यों से शुरू करके कार्यक्रम के नियमों से निकाला जा सकता है।
 
एक एटम को {{dfni|[[Ground atom|ग्राउंड]]}} कहा जाता है यदि इसका कोई भी उपपद परिवर्तनशील न हो। सहज रूप से, प्रत्येक शब्दार्थ एक कार्यक्रम के अर्थ को उन सभी ग्राउंड एटमों के सेट के रूप में परिभाषित करता है जिन्हें तथ्यों से प्रारंभ करके कार्यक्रम के नियमों से निकाला जा सकता है।


==== मॉडल सैद्धांतिक ====
==== मॉडल सैद्धांतिक ====
Line 87: Line 88:
   e(B, C).
   e(B, C).
</syntaxhighlight>
</syntaxhighlight>
व्याख्या <math>M</math> न्यूनतम हेरब्रांड मॉडल है। इसके ऊपर की सभी व्याख्याएँ भी मॉडल हैं, इसके नीचे की सभी व्याख्याएँ मॉडल नहीं हैं।]]एक नियम को ग्राउंड कहा जाता है यदि उसके सभी परमाणु (सिर और शरीर) ग्राउंड हैं। एक जमीनी नियम आर<sub>1</sub> एक अन्य नियम R का जमीनी उदाहरण है<sub>2</sub> यदि आर<sub>1</sub> R में सभी चरों के लिए स्थिरांकों के [[प्रतिस्थापन (तर्क)]] का परिणाम है<sub>2</sub>.
व्याख्या <math>M</math> न्यूनतम हेरब्रांड मॉडल है। इसके ऊपर की सभी व्याख्याएँ भी मॉडल हैं, इसके नीचे की सभी व्याख्याएँ मॉडल नहीं हैं।]]एक नियम को ग्राउंड कहा जाता है यदि उसके सभी एटम ग्राउंड हैं। यदि R1, R2 में सभी चरों के लिए स्थिरांकों के [[प्रतिस्थापन]] का परिणाम है तो एक ग्राउंड नियम R1 दूसरे नियम R2 का एक ग्राउंड उदाहरण है।


डेटालॉग प्रोग्राम का हेरब्रांड बेस सभी ग्राउंड परमाणुओं का सेट है जिसे प्रोग्राम में दिखाई देने वाले स्थिरांक के साथ बनाया जा सकता है। एक व्याख्या (डेटाबेस उदाहरण के रूप में भी जाना जाता है) [[हेरब्रांड आधार]] का एक सबसेट है। एक व्याख्या में एक जमीनी परमाणु सत्य है {{mvar|I}} यदि यह का एक तत्व है {{mvar|I}}. एक व्याख्या में एक नियम सत्य है {{mvar|I}} यदि उस नियम के प्रत्येक बुनियादी उदाहरण के लिए, यदि मुख्य भाग में सभी खंड सत्य हैं {{mvar|I}}, तो नियम का शीर्ष भी सत्य है {{mvar|I}}.
डेटालॉग प्रोग्राम का हेरब्रांड बेस सभी ग्राउंड एटमों का सेट है जिसे प्रोग्राम में दिखाई देने वाले स्थिरांक के साथ बनाया जा सकता है। एक व्याख्या [[हेरब्रांड आधार]] का एक सबसेट है। एक ग्राउंड एटम एक व्याख्या {{mvar|I}} में ट्रुथ है यदि यह {{mvar|I}} का एक तत्व है। यदि उस नियम के प्रत्येक ग्राउंड खंड {{mvar|I}} में ट्रुथ हैं, तो यह प्रमुख नियम है।


डेटालॉग प्रोग्राम पी का एक मॉडल एक व्याख्या है {{mvar|I}} का P जिसमें P के सभी जमीनी तथ्य शामिल हैं, और P के सभी नियमों को सत्य बनाता है {{mvar|I}}. [[मॉडल-सैद्धांतिक]] शब्दार्थ बताता है कि डेटालॉग प्रोग्राम का अर्थ इसका न्यूनतम मॉडल (समान रूप से, इसके सभी मॉडलों का प्रतिच्छेदन) है।{{sfn|Ceri|Gottlob|Tanca|1989|p=149}}
डेटालॉग प्रोग्राम P का एक मॉडल, {{mvar|I}} की एक व्याख्या  है जिसमें P के सभी ग्राउंड तथ्य सम्मलित हैं, और {{mvar|I}} में P के सभी नियमों को ट्रुथ बनाता है। [[मॉडल-सैद्धांतिक]] शब्दार्थ बताता है कि डेटालॉग प्रोग्राम का अर्थ इसका न्यूनतम मॉडल है।{{sfn|Ceri|Gottlob|Tanca|1989|p=149}}


उदाहरण के लिए, यह प्रोग्राम:
उदाहरण के लिए, यह प्रोग्राम:
Line 104: Line 105:
   edge(B, C).
   edge(B, C).
</syntaxhighlight>
</syntaxhighlight>
यह हेरब्रांड ब्रह्मांड है: <code>x</code>, <code>y</code>, <code>z</code>
यह हेरब्रांड यूनिवर्स है: <code>x</code>, <code>y</code>, <code>z</code>
और यह हेरब्रांड आधार: <code>edge(x, x)</code>, <code>edge(x, y)</code>, ..., <code>edge(z, z)</code>, <code>path(x, x)</code>, ..., <code>path(z, z)</code>
 
और यह न्यूनतम हर्ब्रांड मॉडल: <code>edge(x, y)</code>, <code>edge(y, z)</code>, <code>path(x, y)</code>, <code>path(y, z)</code>, <code>path(x, z)</code>
और यह हेरब्रांड आधार है: <code>edge(x, x)</code>, <code>edge(x, y)</code>, ..., <code>edge(z, z)</code>, <code>path(x, x)</code>, ..., <code>path(z, z)</code>
 
और यह न्यूनतम हर्ब्रांड मॉडल है: <code>edge(x, y)</code>, <code>edge(y, z)</code>, <code>path(x, y)</code>, <code>path(y, z)</code>, <code>path(x, z)</code>
 




==== निश्चित-बिंदु ====
==== निश्चित-बिंदु ====


होने देना {{mvar|I}} डेटालॉग प्रोग्राम पी की व्याख्याओं का सेट बनें, यानी, {{math|''I'' {{=}} '''P'''(''H'')}}, जहां H, P का हेरब्रांड आधार है और 'P' [[ सत्ता स्थापित ]] ऑपरेटर है। वह {{dfni|immediate consequence operator}} P के लिए निम्नलिखित मानचित्र है {{mvar|T}} से {{mvar|I}} को {{mvar|I}}: पी में प्रत्येक नियम के प्रत्येक ग्राउंड इंस्टेंस के लिए, यदि बॉडी में प्रत्येक क्लॉज इनपुट व्याख्या में है, तो ग्राउंड इंस्टेंस के प्रमुख को आउटपुट व्याख्या में जोड़ें। यह मानचित्र {{mvar|T}} उपसमुच्चय समावेशन द्वारा दिए गए आंशिक रूप से आदेशित सेट के संबंध में [[मोनोटोनिक फ़ंक्शन]] है {{mvar|T}}. नैस्टर-टार्स्की प्रमेय के अनुसार, इस मानचित्र में सबसे कम निश्चित बिंदु है; [[क्लेन निश्चित-बिंदु प्रमेय]] द्वारा निश्चित बिंदु श्रृंखला का सर्वोच्च है <math>T(\emptyset), T(T(\emptyset)), \ldots, T^n(\emptyset), \ldots </math>. का सबसे कम निश्चित बिंदु {{mvar|M}} कार्यक्रम के न्यूनतम हेरब्रांड मॉडल से मेल खाता है।{{sfn|Ceri|Gottlob|Tanca|1989|p=150}}
{{mvar|I}} डेटालॉग प्रोग्राम P की व्याख्याओं का सेट है, अर्थात्  {{math|''I'' {{=}} '''P'''(''H'')}}, जहां H, P का हेरब्रांड आधार है और 'P' [[Index.php?title=पॉवरसेट|पॉवरसेट]] ऑपरेटर है। P के लिए तत्काल परिणाम ऑपरेटर {{mvar|I}} से {{mvar|I}} तक निम्नलिखित मानचित्र {{mvar|T}} है: P में प्रत्येक नियम के प्रत्येक ग्राउंड इंस्टेंस के लिए, यदि समूह में प्रत्येक क्लॉज इनपुट व्याख्या में है, तो ग्राउंड इंस्टेंस के प्रमुख को आउटपुट में करते है। यह मानचित्र {{mvar|T}}, पर उपसमुच्चय समावेशन द्वारा दिए गए आंशिक क्रम के संबंध में [[Index.php?title=मोनोटोनिक फलन|मोनोटोनिक फलन]] है नैस्टर-टार्स्की प्रमेय के अनुसार, इस मानचित्र में न्यूनतम निश्चित बिंदु है; [[क्लेन निश्चित-बिंदु प्रमेय]] द्वारा निश्चित बिंदु श्रृंखला का सर्वोच्च है <math>T(\emptyset), T(T(\emptyset)), \ldots, T^n(\emptyset), \ldots </math>. {{mvar|M}} का सबसे कम निश्चित बिंदु कार्यक्रम के न्यूनतम हेरब्रांड मॉडल के साथ मेल खाता है।{{sfn|Ceri|Gottlob|Tanca|1989|p=150}}


[[ फिक्सप्वाइंट ]] सिमेंटिक्स न्यूनतम हेरब्रांड मॉडल की गणना के लिए एक एल्गोरिदम का सुझाव देता है: प्रोग्राम में जमीनी तथ्यों के सेट से शुरू करें, फिर फिक्सपॉइंट तक पहुंचने तक नियमों के परिणामों को बार-बार जोड़ें। इस एल्गोरिदम को Datalog#Naive मूल्यांकन|naive मूल्यांकन कहा जाता है।
[[ फिक्सप्वाइंट ]]सिमेंटिक्स न्यूनतम हेरब्रांड मॉडल की गणना के लिए एक एल्गोरिदम का सुझाव देता है: प्रोग्राम में ग्राउंड तथ्यों के सेट से प्रारंभ करें, फिर फिक्सपॉइंट तक पहुंचने तक नियमों के परिणामों को बार-बार जोड़ें। इस एल्गोरिदम को अनुभवहीन मूल्यांकन कहा जाता है।


==== प्रमाण-सैद्धांतिक ====
==== प्रमाण-सैद्धांतिक ====


[[Image:Proof tree for Datalog transitive closure computation.svg|thumb|ज़मीनी परमाणु की व्युत्पत्ति दर्शाने वाला प्रमाण वृक्ष <code>path(x, z)</code> कार्यक्रम से
[[Image:Proof tree for Datalog transitive closure computation.svg|thumb|प्रोग्राम से ग्राउंड एटम<code>path(x, z)</code> की व्युत्पत्ति दर्शाने वाला प्रमाण ट्री है।


<syntaxhighlight lang="prolog">
<syntaxhighlight lang="prolog">
Line 128: Line 132:
   edge(B, C).
   edge(B, C).
</syntaxhighlight>
</syntaxhighlight>
]]एक कार्यक्रम दिया {{mvar|P}}, ए {{dfni|proof tree}} एक जमीनी परमाणु का {{mvar|A}} एक [[वृक्ष (डेटा संरचना)]] है जिसके मूल को लेबल किया गया है {{mvar|A}}, तथ्यों के शीर्ष से जमीन के परमाणुओं द्वारा लेबल की गई पत्तियां {{mvar|P}}, और बच्चों के साथ शाखाएँ <math>A_1, \ldots, A_n</math> जमीनी परमाणुओं द्वारा लेबल किया गया {{mvar|G}} जैसे कि एक जमीनी उदाहरण मौजूद है
]]एक प्रोग्राम {{mvar|P}}, को देखते हुए, ग्राउंड एटम {{mvar|A}} का एक प्रमाण [[Index.php?title=Index.php?title=ट्री|ट्री]] है जिसकी जड़ को {{mvar|A}} द्वारा लेबल किया गया है, पत्तियों को {{mvar|P}} में तथ्यों के प्रमुखों से ग्राउंड एटमों द्वारा लेबल किया गया है, और <math>A_1, \ldots, A_n</math> को ग्राउंड एटम {{mvar|G}} द्वारा लेबल किया गया है।


:<code>G :- A<sub>1</sub>, …, A<sub>n</sub>.</code>
:<code>G :- A<sub>1</sub>, …, A<sub>n</sub>.</code>
में एक नियम का {{mvar|P}}. प्रूफ़-सैद्धांतिक शब्दार्थ डेटालॉग प्रोग्राम के अर्थ को ऐसे ज़मीनी परमाणुओं के समूह के रूप में परिभाषित करता है जिन्हें ऐसे पेड़ों से अलग किया जा सकता है। यह सेट न्यूनतम हेरब्रांड मॉडल से मेल खाता है।<ref>{{Cite book |first=Serge |last=Abiteboul |url=http://worldcat.org/oclc/247979782 |title=डेटाबेस की नींव|date=1996 |publisher=Addison-Wesley |isbn=0-201-53771-0 |oclc=247979782}}</ref>
{{mvar|P}} में एक नियम का प्रमाण-सैद्धांतिक शब्दार्थ डेटालॉग प्रोग्राम के अर्थ को ग्राउंड एटमों के सेट के रूप में परिभाषित करता है जिन्हें ऐसे ट्रीस से परिभाषित किया जा सकता है। यह सेट न्यूनतम हेरब्रांड मॉडल से मेल खाता है।<ref>{{Cite book |first=Serge |last=Abiteboul |url=http://worldcat.org/oclc/247979782 |title=डेटाबेस की नींव|date=1996 |publisher=Addison-Wesley |isbn=0-201-53771-0 |oclc=247979782}}</ref>
किसी को यह जानने में रुचि हो सकती है कि डेटालॉग प्रोग्राम के न्यूनतम हर्ब्रांड मॉडल में एक विशेष ग्राउंड परमाणु दिखाई देता है या नहीं, शायद बाकी मॉडल के बारे में ज्यादा परवाह किए बिना। ऊपर वर्णित प्रूफ ट्री की ऊपर से नीचे की रीडिंग ऐसे प्रश्नों के परिणामों की गणना के लिए एक एल्गोरिदम का सुझाव देती है, ऐसी रीडिंग [[एसएलडी संकल्प]] एल्गोरिदम को सूचित करती है, जो प्रोलॉग के मूल्यांकन का आधार बनती है।
 
किसी को यह जानने में रुचि हो सकती है कि डेटालॉग प्रोग्राम के न्यूनतम हर्ब्रांड मॉडल में एक विशेष ग्राउंड एटम दिखाई देता है या नहीं, शायद बाकी मॉडल के बारे में ज्यादा परवाह किए बिना। ऊपर वर्णित प्रूफ ट्री की ऊपर से नीचे की रीडिंग ऐसे प्रश्नों के परिणामों की गणना के लिए एक एल्गोरिदम का सुझाव देती है, ऐसी रीडिंग [[SLD रिज़ॉल्यूशन]] एल्गोरिदम को सूचित करती है, जो प्रोलॉग के मूल्यांकन का आधार बनती है।


==== अन्य दृष्टिकोण ====
==== अन्य दृष्टिकोण ====


डेटालॉग के शब्दार्थ का अध्ययन अधिक सामान्य [[मोटी हो जाओ]] पर फिक्सप्वाइंट के संदर्भ में भी किया गया है।<ref>{{Cite arXiv |last1=Khamis |first1=Mahmoud Abo |last2=Ngo |first2=Hung Q. |last3=Pichler |first3=Reinhard |last4=Suciu |first4=Dan |last5=Wang |first5=Yisu Remy |date=2023-02-01 |title=डेटालॉग का अभिसरण (पूर्व) सेमीरिंग्स पर|class=cs.DB |eprint=2105.14435 }}</ref>
डेटालॉग के शब्दार्थ का अध्ययन अधिक सामान्य [[सेमीरिंग्स]] पर फिक्सप्वाइंट के संदर्भ में भी किया गया है।<ref>{{Cite arXiv |last1=Khamis |first1=Mahmoud Abo |last2=Ngo |first2=Hung Q. |last3=Pichler |first3=Reinhard |last4=Suciu |first4=Dan |last5=Wang |first5=Yisu Remy |date=2023-02-01 |title=डेटालॉग का अभिसरण (पूर्व) सेमीरिंग्स पर|class=cs.DB |eprint=2105.14435 }}</ref>




== तर्क प्रोग्रामिंग ==
== तर्क प्रोग्रामिंग ==


जबकि लॉजिक प्रोग्रामिंग नाम का उपयोग डेटालॉग और प्रोलॉग सहित प्रोग्रामिंग भाषाओं के संपूर्ण प्रतिमान को संदर्भित करने के लिए किया जाता है, औपचारिक शब्दार्थ पर चर्चा करते समय, यह आम तौर पर [[फ़ंक्शन प्रतीक]]ों के साथ डेटालॉग के विस्तार को संदर्भित करता है। लॉजिक प्रोग्राम भी कहलाते हैं {{dfni|[[Horn clause]] programs}}. इस आलेख में चर्चा की गई तर्क प्रोग्रामिंग प्रोलॉग के शुद्ध या घोषणात्मक प्रोग्रामिंग उपसमुच्चय से निकटता से संबंधित है।
जबकि लॉजिक प्रोग्रामिंग नाम का उपयोग डेटालॉग और प्रोलॉग सहित प्रोग्रामिंग लैंग्वेजेज के संपूर्ण प्रतिमान को संदर्भित करने के लिए किया जाता है, औपचारिक शब्दार्थ पर चर्चा करते समय, यह सामान्यतः [[Index.php?title=फलन प्रतीकों|फलन प्रतीकों]] के साथ डेटालॉग के विस्तार को संदर्भित करता है। लॉजिक प्रोग्राम को [[हॉर्न क्लॉज]] प्रोग्राम भी कहा जाता है। इस आलेख में चर्चा की गई तर्क प्रोग्रामिंग प्रोलॉग के शुद्ध या वर्णनात्मक उपसमुच्चय से निकटता से संबंधित है।


=== सिंटेक्स ===
=== सिंटेक्स ===


लॉजिक प्रोग्रामिंग का सिंटैक्स फ़ंक्शन प्रतीकों के साथ डेटालॉग के सिंटैक्स का विस्तार करता है। लॉजिक प्रोग्रामिंग सीमा प्रतिबंध को हटा देती है, जिससे वेरिएबल्स को नियमों के प्रमुखों में प्रकट होने की अनुमति मिलती है जो उनके शरीर में प्रकट नहीं होते हैं।{{sfn|Abiteboul|p=299}}
लॉजिक प्रोग्रामिंग का सिंटैक्स फलन प्रतीकों के साथ डेटालॉग के सिंटैक्स का विस्तार करता है। लॉजिक प्रोग्रामिंग सीमा प्रतिबंध को हटा देती है, जिससे वेरिएबल्स को नियमों के प्रमुखों में प्रदर्शित होने की अनुमति मिलती है जो उनके निकाय में प्रकट नहीं होते हैं।{{sfn|Abiteboul|p=299}}


=== शब्दार्थ ===
=== शब्दार्थ ===


फ़ंक्शन प्रतीकों की उपस्थिति के कारण, तर्क कार्यक्रमों के हेरब्रांड मॉडल अनंत हो सकते हैं। हालाँकि, एक तर्क कार्यक्रम के शब्दार्थ को अभी भी इसके न्यूनतम हेरब्रांड मॉडल के रूप में परिभाषित किया गया है। संबंधित रूप से, तत्काल परिणाम ऑपरेटर का फिक्सपॉइंट चरणों की एक सीमित संख्या (या एक सीमित सेट) में परिवर्तित नहीं हो सकता है। हालाँकि, न्यूनतम हेरब्रांड मॉडल में किसी भी जमीनी परमाणु में एक सीमित प्रूफ पेड़ होगा। यही कारण है कि प्रोलॉग का मूल्यांकन ऊपर से नीचे तक किया जाता है।{{sfn|Abiteboul|p=299}} डेटालॉग की तरह ही, तीन शब्दार्थों को समतुल्य सिद्ध किया जा सकता है।
फलन प्रतीकों की उपस्थिति के कारण, तर्क कार्यक्रमों के हेरब्रांड मॉडल अनंत हो सकते हैं। हालाँकि, एक तर्क कार्यक्रम के शब्दार्थ को अभी भी इसके न्यूनतम हेरब्रांड मॉडल के रूप में परिभाषित किया गया है। संबंधित रूप से, तत्काल परिणाम ऑपरेटर का फिक्सपॉइंट चरणों की एक सीमित संख्या में परिवर्तित नहीं हो सकता है। हालाँकि, न्यूनतम हेरब्रांड मॉडल में किसी भी ग्राउंड एटम में एक सीमित प्रूफ होगा। यही कारण है कि प्रोलॉग का मूल्यांकन ऊपर से नीचे किया जाता है।{{sfn|Abiteboul|p=299}} डेटालॉग की तरह ही, तीन शब्दार्थों को समतुल्य सिद्ध किया जा सकता है।


== निषेध ==
== निषेध ==


लॉजिक प्रोग्रामिंग में वांछनीय गुण है जिससे लॉजिक प्रोग्राम के शब्दार्थ की सभी तीन प्रमुख परिभाषाएँ सहमत हैं। इसके विपरीत, तर्क कार्यक्रमों के शब्दार्थ के लिए निषेध के साथ कई परस्पर विरोधी प्रस्ताव हैं। असहमति का स्रोत यह है कि तर्क कार्यक्रमों में एक अद्वितीय न्यूनतम हेरब्रांड मॉडल होता है, लेकिन सामान्य तौर पर, तर्क प्रोग्रामिंग (या यहां तक ​​कि डेटालॉग) कार्यक्रमों में निषेध नहीं होता है।
लॉजिक प्रोग्रामिंग में वांछनीय गुण है जिससे लॉजिक प्रोग्राम के शब्दार्थ की सभी तीन प्रमुख परिभाषाएँ सहमत हैं। इसके विपरीत, तर्क कार्यक्रमों के शब्दार्थ के लिए निषेध के साथ कई परस्पर विरोधी प्रस्ताव हैं। असहमति का स्रोत यह है कि तर्क कार्यक्रमों में एक अद्वितीय न्यूनतम हेरब्रांड मॉडल होता है, लेकिन सामान्य तौर पर, तर्क प्रोग्रामिंग कार्यक्रमों में निषेध नहीं होता है।


=== सिंटेक्स ===
=== सिंटेक्स ===


निषेध लिखा है <code>not</code>, और किसी नियम के शरीर में किसी भी परमाणु के सामने प्रकट हो सकता है।
नेगेटिव नहीं है, और किसी नियम के समूह में किसी भी एटम के सामने प्रकट हो सकता है।


<syntaxhighlight lang="bnf">
<syntaxhighlight lang="bnf">
Line 168: Line 173:
==== स्तरीकृत निषेध ====
==== स्तरीकृत निषेध ====


{{expand section|date=March 2023|with=a formal definition of stratification}}
निषेध के साथ एक तर्क कार्यक्रम को तब स्तरीकृत किया जाता है जब प्रत्येक संबंध को कुछ स्तर पर निर्दिष्ट करना संभव होता है, जैसे कि यदि कोई संबंध {{mvar|R}} संबंध {{mvar|S}} के समूह में नकारा हुआ प्रतीत होता है, तो {{mvar|R}}, {{mvar|S}} की तुलना में निचले स्तर में है।<ref>{{Cite journal |last1=Halevy |first1=Alon Y. |last2=Mumick |first2=Inderpal Singh |last3=Sagiv |first3=Yehoshua |last4=Shmueli |first4=Oded |date=2001-09-01 |title=डेटालॉग एक्सटेंशन में स्थैतिक विश्लेषण|url=https://doi.org/10.1145/502102.502104 |journal=Journal of the ACM |volume=48 |issue=5 |pages=971–1012 |doi=10.1145/502102.502104 |s2cid=18868009 |issn=0004-5411}}</ref> डेटालॉग के मॉडल-सैद्धांतिक और निश्चित-बिंदु शब्दार्थ को स्तरीकृत निषेध को संभालने के लिए बढ़ाया जा सकता है, और ऐसे विस्तारों को समकक्ष साबित किया जा सकता है।
 
निषेध के साथ एक तर्क कार्यक्रम को तब स्तरीकृत किया जाता है जब प्रत्येक संबंध को किसी स्तर पर निर्दिष्ट करना संभव हो, जैसे कि यदि कोई संबंध {{mvar|R}} किसी संबंध के मुख्य भाग में नकारा हुआ प्रतीत होता है {{mvar|S}}, तब {{mvar|R}}से निचले तबके में है {{mvar|S}}.<ref>{{Cite journal |last1=Halevy |first1=Alon Y. |last2=Mumick |first2=Inderpal Singh |last3=Sagiv |first3=Yehoshua |last4=Shmueli |first4=Oded |date=2001-09-01 |title=डेटालॉग एक्सटेंशन में स्थैतिक विश्लेषण|url=https://doi.org/10.1145/502102.502104 |journal=Journal of the ACM |volume=48 |issue=5 |pages=971–1012 |doi=10.1145/502102.502104 |s2cid=18868009 |issn=0004-5411}}</ref> डेटालॉग के मॉडल-सैद्धांतिक और निश्चित-बिंदु शब्दार्थ को स्तरीकृत निषेध को संभालने के लिए बढ़ाया जा सकता है, और ऐसे विस्तारों को समकक्ष साबित किया जा सकता है।


डेटालॉग के कई कार्यान्वयन निश्चित बिंदु शब्दार्थ से प्रेरित बॉटम-अप मूल्यांकन मॉडल का उपयोग करते हैं। चूँकि यह शब्दार्थ स्तरीकृत निषेध को संभाल सकता है, डेटालॉग के कई कार्यान्वयन स्तरीकृत निषेध को लागू करते हैं।
डेटालॉग के कई कार्यान्वयन निश्चित बिंदु शब्दार्थ से प्रेरित बॉटम-अप मूल्यांकन मॉडल का उपयोग करते हैं। चूँकि यह शब्दार्थ स्तरीकृत निषेध को संभाल सकता है, डेटालॉग के कई कार्यान्वयन स्तरीकृत निषेध को लागू करते हैं।
Line 180: Line 183:
win(X) :- move(X, Y), not win(Y).
win(X) :- move(X, Y), not win(Y).
</syntaxhighlight>
</syntaxhighlight>
यह कार्यक्रम स्तरीकृत नहीं है, लेकिन ऐसा सोचना उचित लगता है <code>a</code> खेल जीतना चाहिए.
यह कार्यक्रम स्तरीकृत नहीं है, लेकिन यह सोचना उचित लगता है <code>a</code> कि गेम जीतना चाहिए।


==== समापन शब्दार्थ ====
==== समापन शब्दार्थ ====


{{main|Negation as failure#Completion semantics}}
{{main|विफलता के रूप में नकार#समापन शब्दार्थ}}


{{empty section|date=March 2023}}
{{empty section|date=March 2023}}
Line 194: Line 197:
==== स्थिर मॉडल शब्दार्थ ====
==== स्थिर मॉडल शब्दार्थ ====


{{main|Stable model semantics}}
{{main|
स्थिर मॉडल शब्दार्थ}}
 
स्थिर मॉडल शब्दार्थ किसी प्रोग्राम के कुछ हर्ब्रांड मॉडल को स्थिर कहने के लिए एक शर्त को परिभाषित करता है। सहज रूप से, स्थिर मॉडल "विश्वासों के संभावित सेट हैं जो एक तर्कसंगत एजेंट धारण कर सकते हैं, जिसे परिसर के रूप में दिया गया है।<ref>{{Cite journal |last=Lifschitz |first=Michael Gelfond and Vladimir |date=1988 |title=तर्क प्रोग्रामिंग के लिए स्थिर मॉडल शब्दार्थ|url=https://www.cs.utexas.edu/users/ai-lab/?gel88}}</ref>


स्थिर मॉडल शब्दार्थ किसी प्रोग्राम के कुछ हर्ब्रांड मॉडल को स्थिर कहने के लिए एक शर्त को परिभाषित करता है। सहज रूप से, स्थिर मॉडल विश्वासों के संभावित सेट हैं जो एक तर्कसंगत एजेंट धारण कर सकता है, जिसे [कार्यक्रम] परिसर के रूप में दिया गया है।<ref>{{Cite journal |last=Lifschitz |first=Michael Gelfond and Vladimir |date=1988 |title=तर्क प्रोग्रामिंग के लिए स्थिर मॉडल शब्दार्थ|url=https://www.cs.utexas.edu/users/ai-lab/?gel88}}</ref>
नकार वाले एक प्रोग्राम में कई स्थिर मॉडल या कोई स्थिर मॉडल नहीं हो सकते हैं। उदाहरण के लिए, प्रोग्राम
नकार वाले एक प्रोग्राम में कई स्थिर मॉडल या कोई स्थिर मॉडल नहीं हो सकते हैं। उदाहरण के लिए, प्रोग्राम


Line 203: Line 208:
q :- not p.
q :- not p.
</syntaxhighlight>
</syntaxhighlight>
इसके दो स्थिर मॉडल हैं <math>\{p\}</math>, <math>\{q\}</math>. एक-नियम कार्यक्रम
इसके दो स्थिर मॉडल हैं <math>\{p\}</math>, <math>\{q\}</math>. एक-नियम कार्यक्रम  


<syntaxhighlight lang="prolog">
<syntaxhighlight lang="prolog">
p :- not p.
p :- not p.
</syntaxhighlight>
</syntaxhighlight>
कोई स्थिर मॉडल नहीं है.
कोई स्थिर मॉडल नहीं है।


प्रत्येक स्थिर मॉडल एक न्यूनतम हेरब्रांड मॉडल है। बिना किसी निषेध के डेटालॉग प्रोग्राम में एक स्थिर मॉडल होता है, जो बिल्कुल इसका न्यूनतम हेरब्रांड मॉडल है।
प्रत्येक स्थिर मॉडल एक न्यूनतम हेरब्रांड मॉडल है। बिना किसी निषेध के डेटालॉग प्रोग्राम में एक स्थिर मॉडल होता है, जो बिल्कुल इसका न्यूनतम हेरब्रांड मॉडल है। स्थिर मॉडल शब्दार्थ एक तर्क कार्यक्रम के अर्थ को उसके स्थिर मॉडल होने से नकारते हुए परिभाषित करता है, यदि वास्तव में कोई एक है। हालाँकि, किसी प्रोग्राम के सभी स्थिर मॉडलों की जांच करना उपयोगी हो सकता है; यह [[आंसर सेट प्रोग्रामिंग]] का लक्ष्य है।
स्थिर मॉडल शब्दार्थ एक तर्क कार्यक्रम के अर्थ को उसके स्थिर मॉडल होने से नकारते हुए परिभाषित करता है, यदि वास्तव में कोई एक है। हालाँकि, इसकी जाँच करना उपयोगी हो सकता है {{em|all}} (या कम से कम, कई) किसी प्रोग्राम के स्थिर मॉडल; यह [[उत्तर सेट प्रोग्रामिंग]] का लक्ष्य है।


==== अच्छी तरह से स्थापित शब्दार्थ ====
==== अच्छी तरह से स्थापित शब्दार्थ ====


{{main|Well-founded semantics}}
{{main|
अच्छी तरह से स्थापित शब्दार्थ}}


{{empty section|date=March 2023}}
{{empty section|date=March 2023}}
Line 221: Line 226:
== आगे विस्तार ==
== आगे विस्तार ==


डेटालॉग के कई अन्य एक्सटेंशन प्रस्तावित और अध्ययन किए गए हैं, जिनमें [[पूर्णांक]] स्थिरांक और फ़ंक्शंस के समर्थन वाले वेरिएंट शामिल हैं (डेटालॉगजेड|डेटालॉग सहित)<sub>ℤ</sub>),<ref>{{Cite arXiv |last1=Kaminski |first1=Mark |last2=Grau |first2=Bernardo Cuenca |last3=Kostylev |first3=Egor V. |last4=Motik |first4=Boris |last5=Horrocks |first5=Ian |date=2017-11-12 |title=लिमिट डेटालॉग प्रोग्राम का उपयोग करके घोषणात्मक डेटा विश्लेषण की नींव|class=cs.AI |eprint=1705.06927 }}</ref><ref>{{Cite journal |last1=Grau |first1=Bernardo Cuenca |last2=Horrocks |first2=Ian |last3=Kaminski |first3=Mark |last4=Kostylev |first4=Egor V. |last5=Motik |first5=Boris |date=2020-02-25 |title=Limit Datalog: A Declarative Query Language for Data Analysis |url=https://doi.org/10.1145/3385658.3385660 |journal=ACM SIGMOD Record |volume=48 |issue=4 |pages=6–17 |doi=10.1145/3385658.3385660 |s2cid=211520719 |issn=0163-5808}}</ref> नियमों और [[समग्र कार्य]]ों के निकायों में [[असमानता (गणित)]] बाधाएँ।
डेटालॉग के कई अन्य विस्तार प्रस्तावित और अध्ययन किए गए हैं, जिनमें [[पूर्णांक]] स्थिरांक और फलनों के (डेटालॉग सहित)<sub>ℤ</sub>),<ref>{{Cite arXiv |last1=Kaminski |first1=Mark |last2=Grau |first2=Bernardo Cuenca |last3=Kostylev |first3=Egor V. |last4=Motik |first4=Boris |last5=Horrocks |first5=Ian |date=2017-11-12 |title=लिमिट डेटालॉग प्रोग्राम का उपयोग करके घोषणात्मक डेटा विश्लेषण की नींव|class=cs.AI |eprint=1705.06927 }}</ref><ref>{{Cite journal |last1=Grau |first1=Bernardo Cuenca |last2=Horrocks |first2=Ian |last3=Kaminski |first3=Mark |last4=Kostylev |first4=Egor V. |last5=Motik |first5=Boris |date=2020-02-25 |title=Limit Datalog: A Declarative Query Language for Data Analysis |url=https://doi.org/10.1145/3385658.3385660 |journal=ACM SIGMOD Record |volume=48 |issue=4 |pages=6–17 |doi=10.1145/3385658.3385660 |s2cid=211520719 |issn=0163-5808}}</ref> नियमों के निकायों में असमानता बाधाएं और [[Index.php?title=समग्र कार्यों|समग्र कार्यों]] के समर्थन वाले वेरिएंट सम्मलित हैं।


[[बाधा तर्क प्रोग्रामिंग]] [[वास्तविक संख्या]] या पूर्णांक जैसे डोमेन पर बाधाओं को नियमों के मुख्य भाग में प्रदर्शित करने की अनुमति देती है।
[[Index.php?title=कॉन्सट्रेंट लॉजिक प्रोग्रामिंग|कॉन्सट्रेंट लॉजिक प्रोग्रामिंग]] [[वास्तविक]] या [[पूर्णांक]] जैसे डोमेन पर बाधाओं को नियमों के मुख्य भाग में प्रदर्शित करने की अनुमति देती है।


== यह भी देखें ==
== यह भी देखें ==


* हरब्रांड संरचना
* हरब्रांड संरचना
* तर्क प्रोग्रामिंग
* लॉजिक प्रोग्रामिंग
* असफलता के रूप में नकार
* असफलता के रूप में नकार
* [[प्रोलॉग सिंटैक्स और शब्दार्थ]]
* [[प्रोलॉग सिंटैक्स और शब्दार्थ]]
Line 248: Line 253:
श्रेणी:तर्क प्रोग्रामिंग
श्रेणी:तर्क प्रोग्रामिंग


 
[[Category:Articles using small message boxes]]
[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 English-language sources (en)]]
[[Category:CS1 errors]]
[[Category:Created On 24/07/2023]]
[[Category:Created On 24/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]

Latest revision as of 10:20, 12 August 2023

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

घोषणात्मक तर्क कार्यक्रम पूरी तरह से प्रपत्र के नियमों से युक्त होते हैं

H :- B1, ..., BN.

ऐसे प्रत्येक नियम को एक निहितार्थ के रूप में पढ़ा जा सकता है:

जिसका अर्थ है यदि प्रत्येक , ट्रूथ है । फिर लॉजिक प्रोग्राम उन तथ्यों के समूह की गणना करते हैं जो उनके नियमों द्वारा निहित हैं।

डेटालॉग, प्रोलॉग और संबंधित लैंग्वेजेज के कई कार्यान्वयन प्रोलॉग के कट ऑपरेटर या फोरेइग्नर फ़ंक्शन इंटरफ़ेस जैसी अतिरिक्त-तार्किक सुविधाओं जैसी प्रक्रियात्मक विशेषताएं जोड़ते हैं। ऐसे एक्सटेंशन का औपचारिक शब्दार्थ इस लेख के दायरे से बाहर है।

डेटालॉग

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

सिंटेक्स

डेटालॉग प्रोग्राम में नियमों की एक सूची होती है।[1] यदि स्थिरांक और चर क्रमशः स्थिरांक और चर के दो गणनीय सेट हैं और संबंध विधेय चर का एक गणनीय सेट है, तो निम्नलिखित BNF ग्रामर डेटालॉग प्रोग्राम की संरचना को व्यक्त करता है:

<program> ::= <rule> <program> | ""
<rule> ::= <atom> ":-" <atom-list> "."
<atom> ::= <relation> "(" <term-list> ")"
<atom-list> ::= <atom> | <atom> "," <atom-list> | ""
<term> ::= <constant> | <variable>
<term-list> ::= <term> | <term> "," <term-list> | ""

एटमों को शाब्दिक भी कहा जाता है। लिट्रल. के बाईं ओर एटम को नियम का :- हेड कहा जाता है; दाहिनी ओर के एटम समूह हैं। प्रत्येक डेटालॉग प्रोग्राम को इस शर्त को पूरा करना होगा कि नियम के शीर्ष में दिखाई देने वाला प्रत्येक चर मुख्य भाग में भी दिखाई देता है।[2]

खाली निकाय वाले नियमों को तथ्य कहा जाता है। उदाहरण के लिए, निम्नलिखित नियम एक तथ्य है:

r(x) :- .


सिंटैक्टिक शुगर

तर्क प्रोग्रामिंग के कई कार्यान्वयन बिना तथ्यों को लिखने की अनुमति देने के लिए उपरोक्त व्याकरण का विस्तार करते हैं :-, जैसे:

r(x).

कई लोग बिना कोष्ठक के 0-एरी संबंध लिखने की भी अनुमति देते हैं, जैसे:

p :- q.

ये केवल संक्षिप्त रूप (वाक्यात्मक शर्करा) हैं; उनका कार्यक्रम के शब्दार्थ पर कोई प्रभाव नहीं पड़ता है।

उदाहरण

निम्नलिखित प्रोग्राम संबंध की गणना करता है path, जो संबंध का सकर्मक समापन है edge.

edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).


शब्दार्थ

डेटालॉग कार्यक्रमों के शब्दार्थ के लिए तीन व्यापक रूप से उपयोग किए जाने वाले दृष्टिकोण हैं: मॉडल-सैद्धांतिक, निश्चित बिंदु , और प्रमाण-सिद्धांत संबंधी है। ये तीन दृष्टिकोण समतुल्य प्रमाणित हो सकते हैं।[3]

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

मॉडल सैद्धांतिक

डेटालॉग कार्यक्रम की हेरब्रांड व्याख्याओं का हस्से आरेख
e(x, y).
e(y, z).
p(A, B) :-
  e(A, B).
p(A, C) :- 
  p(A, B),
  e(B, C).
व्याख्या न्यूनतम हेरब्रांड मॉडल है। इसके ऊपर की सभी व्याख्याएँ भी मॉडल हैं, इसके नीचे की सभी व्याख्याएँ मॉडल नहीं हैं।

एक नियम को ग्राउंड कहा जाता है यदि उसके सभी एटम ग्राउंड हैं। यदि R1, R2 में सभी चरों के लिए स्थिरांकों के प्रतिस्थापन का परिणाम है तो एक ग्राउंड नियम R1 दूसरे नियम R2 का एक ग्राउंड उदाहरण है।

डेटालॉग प्रोग्राम का हेरब्रांड बेस सभी ग्राउंड एटमों का सेट है जिसे प्रोग्राम में दिखाई देने वाले स्थिरांक के साथ बनाया जा सकता है। एक व्याख्या हेरब्रांड आधार का एक सबसेट है। एक ग्राउंड एटम एक व्याख्या I में ट्रुथ है यदि यह I का एक तत्व है। यदि उस नियम के प्रत्येक ग्राउंड खंड I में ट्रुथ हैं, तो यह प्रमुख नियम है।

डेटालॉग प्रोग्राम P का एक मॉडल, I की एक व्याख्या है जिसमें P के सभी ग्राउंड तथ्य सम्मलित हैं, और I में P के सभी नियमों को ट्रुथ बनाता है। मॉडल-सैद्धांतिक शब्दार्थ बताता है कि डेटालॉग प्रोग्राम का अर्थ इसका न्यूनतम मॉडल है।[4]

उदाहरण के लिए, यह प्रोग्राम:

edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

यह हेरब्रांड यूनिवर्स है: x, y, z

और यह हेरब्रांड आधार है: edge(x, x), edge(x, y), ..., edge(z, z), path(x, x), ..., path(z, z)

और यह न्यूनतम हर्ब्रांड मॉडल है: edge(x, y), edge(y, z), path(x, y), path(y, z), path(x, z)


निश्चित-बिंदु

I डेटालॉग प्रोग्राम P की व्याख्याओं का सेट है, अर्थात् I = P(H), जहां H, P का हेरब्रांड आधार है और 'P' पॉवरसेट ऑपरेटर है। P के लिए तत्काल परिणाम ऑपरेटर I से I तक निम्नलिखित मानचित्र T है: P में प्रत्येक नियम के प्रत्येक ग्राउंड इंस्टेंस के लिए, यदि समूह में प्रत्येक क्लॉज इनपुट व्याख्या में है, तो ग्राउंड इंस्टेंस के प्रमुख को आउटपुट में करते है। यह मानचित्र T, पर उपसमुच्चय समावेशन द्वारा दिए गए आंशिक क्रम के संबंध में मोनोटोनिक फलन है नैस्टर-टार्स्की प्रमेय के अनुसार, इस मानचित्र में न्यूनतम निश्चित बिंदु है; क्लेन निश्चित-बिंदु प्रमेय द्वारा निश्चित बिंदु श्रृंखला का सर्वोच्च है . M का सबसे कम निश्चित बिंदु कार्यक्रम के न्यूनतम हेरब्रांड मॉडल के साथ मेल खाता है।[5]

फिक्सप्वाइंट सिमेंटिक्स न्यूनतम हेरब्रांड मॉडल की गणना के लिए एक एल्गोरिदम का सुझाव देता है: प्रोग्राम में ग्राउंड तथ्यों के सेट से प्रारंभ करें, फिर फिक्सपॉइंट तक पहुंचने तक नियमों के परिणामों को बार-बार जोड़ें। इस एल्गोरिदम को अनुभवहीन मूल्यांकन कहा जाता है।

प्रमाण-सैद्धांतिक

प्रोग्राम से ग्राउंड एटमpath(x, z) की व्युत्पत्ति दर्शाने वाला प्रमाण ट्री है।
edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

एक प्रोग्राम P, को देखते हुए, ग्राउंड एटम A का एक प्रमाण ट्री है जिसकी जड़ को A द्वारा लेबल किया गया है, पत्तियों को P में तथ्यों के प्रमुखों से ग्राउंड एटमों द्वारा लेबल किया गया है, और को ग्राउंड एटम G द्वारा लेबल किया गया है।

G :- A1, …, An.

P में एक नियम का प्रमाण-सैद्धांतिक शब्दार्थ डेटालॉग प्रोग्राम के अर्थ को ग्राउंड एटमों के सेट के रूप में परिभाषित करता है जिन्हें ऐसे ट्रीस से परिभाषित किया जा सकता है। यह सेट न्यूनतम हेरब्रांड मॉडल से मेल खाता है।[6]

किसी को यह जानने में रुचि हो सकती है कि डेटालॉग प्रोग्राम के न्यूनतम हर्ब्रांड मॉडल में एक विशेष ग्राउंड एटम दिखाई देता है या नहीं, शायद बाकी मॉडल के बारे में ज्यादा परवाह किए बिना। ऊपर वर्णित प्रूफ ट्री की ऊपर से नीचे की रीडिंग ऐसे प्रश्नों के परिणामों की गणना के लिए एक एल्गोरिदम का सुझाव देती है, ऐसी रीडिंग SLD रिज़ॉल्यूशन एल्गोरिदम को सूचित करती है, जो प्रोलॉग के मूल्यांकन का आधार बनती है।

अन्य दृष्टिकोण

डेटालॉग के शब्दार्थ का अध्ययन अधिक सामान्य सेमीरिंग्स पर फिक्सप्वाइंट के संदर्भ में भी किया गया है।[7]


तर्क प्रोग्रामिंग

जबकि लॉजिक प्रोग्रामिंग नाम का उपयोग डेटालॉग और प्रोलॉग सहित प्रोग्रामिंग लैंग्वेजेज के संपूर्ण प्रतिमान को संदर्भित करने के लिए किया जाता है, औपचारिक शब्दार्थ पर चर्चा करते समय, यह सामान्यतः फलन प्रतीकों के साथ डेटालॉग के विस्तार को संदर्भित करता है। लॉजिक प्रोग्राम को हॉर्न क्लॉज प्रोग्राम भी कहा जाता है। इस आलेख में चर्चा की गई तर्क प्रोग्रामिंग प्रोलॉग के शुद्ध या वर्णनात्मक उपसमुच्चय से निकटता से संबंधित है।

सिंटेक्स

लॉजिक प्रोग्रामिंग का सिंटैक्स फलन प्रतीकों के साथ डेटालॉग के सिंटैक्स का विस्तार करता है। लॉजिक प्रोग्रामिंग सीमा प्रतिबंध को हटा देती है, जिससे वेरिएबल्स को नियमों के प्रमुखों में प्रदर्शित होने की अनुमति मिलती है जो उनके निकाय में प्रकट नहीं होते हैं।[8]

शब्दार्थ

फलन प्रतीकों की उपस्थिति के कारण, तर्क कार्यक्रमों के हेरब्रांड मॉडल अनंत हो सकते हैं। हालाँकि, एक तर्क कार्यक्रम के शब्दार्थ को अभी भी इसके न्यूनतम हेरब्रांड मॉडल के रूप में परिभाषित किया गया है। संबंधित रूप से, तत्काल परिणाम ऑपरेटर का फिक्सपॉइंट चरणों की एक सीमित संख्या में परिवर्तित नहीं हो सकता है। हालाँकि, न्यूनतम हेरब्रांड मॉडल में किसी भी ग्राउंड एटम में एक सीमित प्रूफ होगा। यही कारण है कि प्रोलॉग का मूल्यांकन ऊपर से नीचे किया जाता है।[8] डेटालॉग की तरह ही, तीन शब्दार्थों को समतुल्य सिद्ध किया जा सकता है।

निषेध

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

सिंटेक्स

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

<atom-list> ::= <atom> | "not" <atom> | <atom> "," <atom-list> | ""


शब्दार्थ

स्तरीकृत निषेध

निषेध के साथ एक तर्क कार्यक्रम को तब स्तरीकृत किया जाता है जब प्रत्येक संबंध को कुछ स्तर पर निर्दिष्ट करना संभव होता है, जैसे कि यदि कोई संबंध R संबंध S के समूह में नकारा हुआ प्रतीत होता है, तो R, S की तुलना में निचले स्तर में है।[9] डेटालॉग के मॉडल-सैद्धांतिक और निश्चित-बिंदु शब्दार्थ को स्तरीकृत निषेध को संभालने के लिए बढ़ाया जा सकता है, और ऐसे विस्तारों को समकक्ष साबित किया जा सकता है।

डेटालॉग के कई कार्यान्वयन निश्चित बिंदु शब्दार्थ से प्रेरित बॉटम-अप मूल्यांकन मॉडल का उपयोग करते हैं। चूँकि यह शब्दार्थ स्तरीकृत निषेध को संभाल सकता है, डेटालॉग के कई कार्यान्वयन स्तरीकृत निषेध को लागू करते हैं।

जबकि स्तरीकृत निषेध डेटालॉग का एक सामान्य विस्तार है, ऐसे उचित कार्यक्रम हैं जिन्हें स्तरीकृत नहीं किया जा सकता है। निम्नलिखित कार्यक्रम दो-खिलाड़ियों के खेल का वर्णन करता है जहां एक खिलाड़ी जीतता है यदि उनके प्रतिद्वंद्वी के पास कोई चाल नहीं है:[10]

move(a, b).
win(X) :- move(X, Y), not win(Y).

यह कार्यक्रम स्तरीकृत नहीं है, लेकिन यह सोचना उचित लगता है a कि गेम जीतना चाहिए।

समापन शब्दार्थ

उत्तम मॉडल शब्दार्थ

स्थिर मॉडल शब्दार्थ

स्थिर मॉडल शब्दार्थ किसी प्रोग्राम के कुछ हर्ब्रांड मॉडल को स्थिर कहने के लिए एक शर्त को परिभाषित करता है। सहज रूप से, स्थिर मॉडल "विश्वासों के संभावित सेट हैं जो एक तर्कसंगत एजेंट धारण कर सकते हैं, जिसे परिसर के रूप में दिया गया है।[11]

नकार वाले एक प्रोग्राम में कई स्थिर मॉडल या कोई स्थिर मॉडल नहीं हो सकते हैं। उदाहरण के लिए, प्रोग्राम

p :- not q.
q :- not p.

इसके दो स्थिर मॉडल हैं , . एक-नियम कार्यक्रम

p :- not p.

कोई स्थिर मॉडल नहीं है।

प्रत्येक स्थिर मॉडल एक न्यूनतम हेरब्रांड मॉडल है। बिना किसी निषेध के डेटालॉग प्रोग्राम में एक स्थिर मॉडल होता है, जो बिल्कुल इसका न्यूनतम हेरब्रांड मॉडल है। स्थिर मॉडल शब्दार्थ एक तर्क कार्यक्रम के अर्थ को उसके स्थिर मॉडल होने से नकारते हुए परिभाषित करता है, यदि वास्तव में कोई एक है। हालाँकि, किसी प्रोग्राम के सभी स्थिर मॉडलों की जांच करना उपयोगी हो सकता है; यह आंसर सेट प्रोग्रामिंग का लक्ष्य है।

अच्छी तरह से स्थापित शब्दार्थ

आगे विस्तार

डेटालॉग के कई अन्य विस्तार प्रस्तावित और अध्ययन किए गए हैं, जिनमें पूर्णांक स्थिरांक और फलनों के (डेटालॉग सहित)),[12][13] नियमों के निकायों में असमानता बाधाएं और समग्र कार्यों के समर्थन वाले वेरिएंट सम्मलित हैं।

कॉन्सट्रेंट लॉजिक प्रोग्रामिंग वास्तविक या पूर्णांक जैसे डोमेन पर बाधाओं को नियमों के मुख्य भाग में प्रदर्शित करने की अनुमति देती है।

यह भी देखें

संदर्भ

टिप्पणियाँ

  1. Ceri, Gottlob & Tanca 1989, p. 146.
  2. Eisner, Jason; Filardo, Nathaniel W. (2011). de Moor, Oege; Gottlob, Georg; Furche, Tim; Sellers, Andrew (eds.). "Dyna: Extending Datalog for Modern AI". Datalog Reloaded. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 6702: 181–220. doi:10.1007/978-3-642-24206-9_11. ISBN 978-3-642-24206-9.
  3. van Emden, M. H.; Kowalski, R. A. (1976-10-01). "एक प्रोग्रामिंग भाषा के रूप में विधेय तर्क का शब्दार्थ". Journal of the ACM. 23 (4): 733–742. doi:10.1145/321978.321991. ISSN 0004-5411. S2CID 11048276.
  4. Ceri, Gottlob & Tanca 1989, p. 149.
  5. Ceri, Gottlob & Tanca 1989, p. 150.
  6. Abiteboul, Serge (1996). डेटाबेस की नींव. Addison-Wesley. ISBN 0-201-53771-0. OCLC 247979782.
  7. Khamis, Mahmoud Abo; Ngo, Hung Q.; Pichler, Reinhard; Suciu, Dan; Wang, Yisu Remy (2023-02-01). "डेटालॉग का अभिसरण (पूर्व) सेमीरिंग्स पर". arXiv:2105.14435 [cs.DB].
  8. 8.0 8.1 Abiteboul, p. 299.
  9. Halevy, Alon Y.; Mumick, Inderpal Singh; Sagiv, Yehoshua; Shmueli, Oded (2001-09-01). "डेटालॉग एक्सटेंशन में स्थैतिक विश्लेषण". Journal of the ACM. 48 (5): 971–1012. doi:10.1145/502102.502104. ISSN 0004-5411. S2CID 18868009.
  10. Leone, N; Rullo, P (1992-01-01). "डेटालॉग क्वेरीज़ के सुस्थापित शब्दार्थ की सुरक्षित गणना". Information Systems (in English). 17 (1): 17–31. doi:10.1016/0306-4379(92)90003-6. ISSN 0306-4379.
  11. Lifschitz, Michael Gelfond and Vladimir (1988). "तर्क प्रोग्रामिंग के लिए स्थिर मॉडल शब्दार्थ". {{cite journal}}: Cite journal requires |journal= (help)
  12. Kaminski, Mark; Grau, Bernardo Cuenca; Kostylev, Egor V.; Motik, Boris; Horrocks, Ian (2017-11-12). "लिमिट डेटालॉग प्रोग्राम का उपयोग करके घोषणात्मक डेटा विश्लेषण की नींव". arXiv:1705.06927 [cs.AI].
  13. Grau, Bernardo Cuenca; Horrocks, Ian; Kaminski, Mark; Kostylev, Egor V.; Motik, Boris (2020-02-25). "Limit Datalog: A Declarative Query Language for Data Analysis". ACM SIGMOD Record. 48 (4): 6–17. doi:10.1145/3385658.3385660. ISSN 0163-5808. S2CID 211520719.


स्रोत

श्रेणी:प्रोग्रामिंग भाषा सिंटैक्स श्रेणी:तर्क प्रोग्रामिंग