प्रस्तावित निर्देशित अचक्रीय आलेख: Difference between revisions
From Vigyanwiki
(Work done) |
No edit summary |
||
| Line 1: | Line 1: | ||
'''प्रोपोज़िशनल डायरेक्टेड एसाइक्लिक ग्राफ़''' ('''पीडीएजी''') एक प्रकार का [[डेटा संरचना|डेटा स्ट्रक्चर]] है जो [[बूलियन समारोह|बूलियन | '''प्रोपोज़िशनल डायरेक्टेड एसाइक्लिक ग्राफ़''' ('''पीडीएजी''') एक प्रकार का [[डेटा संरचना|डेटा स्ट्रक्चर]] है जो [[बूलियन समारोह|बूलियन फलन]] को प्रतिष्ठित करने के लिए उपयोग की जाती है। बूलियन फलन निम्नलिखित रूप में मूलभूत, [[निर्देशित अचक्रीय ग्राफ|डायरेक्टेड एसाइक्लिक ग्राफ़]] के रूप में दर्शाया जा सकता है: | ||
* लीव्स को <math>\top</math> (सत्य), <math>\bot</math> (असत्य), या बूलियन चर (वेरिएबल) के साथ लेबल किया जाता है। | * लीव्स को <math>\top</math> (सत्य), <math>\bot</math> (असत्य), या बूलियन चर (वेरिएबल) के साथ लेबल किया जाता है। | ||
* नॉन-लीव्स <math>\bigtriangleup</math> (लॉजिकल और), <math>\bigtriangledown</math> (लॉजिकल या) और <math>\Diamond</math> (लॉजिकल नहीं) हैं। | * नॉन-लीव्स <math>\bigtriangleup</math> (लॉजिकल और), <math>\bigtriangledown</math> (लॉजिकल या) और <math>\Diamond</math> (लॉजिकल नहीं) हैं। | ||
| Line 5: | Line 5: | ||
* <math>\Diamond</math>-नोड में यथार्थ रूप से एक ही शाखा होती है। | * <math>\Diamond</math>-नोड में यथार्थ रूप से एक ही शाखा होती है। | ||
<math>\top</math> (<math>\bot</math>) के साथ लेबल की गई लीव्स नियत बूलियन | <math>\top</math> (<math>\bot</math>) के साथ लेबल की गई लीव्स नियत बूलियन फलन को निरूपित करती हैं, जो हमेशा 1 (0) पर मान्य होती है। बूलियन चर <math>x</math> के साथ लबले की गई लीव को असाइनमेंट <math>x=1</math> के रूप में इंटरप्रिट किया जाता है, अर्थात यह बूलियन फलन को निरूपित करता है जो यदि और केवल यदि <math>x=1</math> हो तो 1 पर मूल्यांकन करता है। <math>\bigtriangleup</math>-नोड द्वारा दर्शाया गया बूलियन फलन वह है जो 1 का मूल्यांकन करता है, यदि और केवल यदि इसकी सभी शाखाओं के बूलियन फलन 1 पर मूल्यांकन करती है। उसी तरह, <math>\bigtriangledown</math>-नोड एक बूलियन फलन को निरूपित करता है जो 1 का मूल्यांकन करता है, यदि और केवल यदि इसकी कम से कम एक शाखा का बूलियन फलन 1 का मूल्यांकन करती है। अंत में, <math>\Diamond</math>-नोड उसकी शाखा के विपरीत बूलियन फलन को निरूपित करता है, अर्थात इस फलन को निरूपित करता है जो 1 का मूल्यांकन करता है, यदि और केवल यदि उसकी शाखा का बूलियन फलन 0 का मूल्यांकन करता है। | ||
== पीडीएजी, बीडीडी, और एनएनएफ == | == पीडीएजी, बीडीडी, और एनएनएफ == | ||
प्रत्येक [[ द्विआधारी निर्णय आरेख |बाइनरी डिसिज़न डायग्राम]] (बीडीडी) और प्रत्येक [[ निषेध सामान्य रूप |नेगशन नार्मल फॉर्म]] (एनएनएफ) भी कुछ विशेष गुणों के साथ एक प्रकार का पीडीएजी हैं। निम्नलिखित चित्र बूलियन | प्रत्येक [[ द्विआधारी निर्णय आरेख |बाइनरी डिसिज़न डायग्राम]] (बीडीडी) और प्रत्येक [[ निषेध सामान्य रूप |नेगशन नार्मल फॉर्म]] (एनएनएफ) भी कुछ विशेष गुणों के साथ एक प्रकार का पीडीएजी हैं। निम्नलिखित चित्र बूलियन फलन <math>f(x1, x2, x3) = -x1 * -x2 * -x3 + x1 * x2 + x2 * x3</math> को दर्शाते हैं: | ||
{| align="center" | {| align="center" | ||
|- | |- | ||
| [[File:BDD simple.svg|thumb|189px| | | [[File:BDD simple.svg|thumb|189px|फलन f के लिए बीडीडी]] | ||
| [[File:BDD2pdag.png|thumb|189px| | | [[File:BDD2pdag.png|thumb|189px|फलन f के लिए पीडीएजी, बीडीडी से प्राप्त किया गया]] | ||
| [[File:BDD2pdag simple.svg|thumb|189px| | | [[File:BDD2pdag simple.svg|thumb|189px|फलन f के लिए पीडीएजी]] | ||
|} | |} | ||
Revision as of 12:03, 30 June 2023
प्रोपोज़िशनल डायरेक्टेड एसाइक्लिक ग्राफ़ (पीडीएजी) एक प्रकार का डेटा स्ट्रक्चर है जो बूलियन फलन को प्रतिष्ठित करने के लिए उपयोग की जाती है। बूलियन फलन निम्नलिखित रूप में मूलभूत, डायरेक्टेड एसाइक्लिक ग्राफ़ के रूप में दर्शाया जा सकता है:
- लीव्स को (सत्य), (असत्य), या बूलियन चर (वेरिएबल) के साथ लेबल किया जाता है।
- नॉन-लीव्स (लॉजिकल और), (लॉजिकल या) और (लॉजिकल नहीं) हैं।
- - और -नोड्स में कम से कम एक शाखा होती है।
- -नोड में यथार्थ रूप से एक ही शाखा होती है।
() के साथ लेबल की गई लीव्स नियत बूलियन फलन को निरूपित करती हैं, जो हमेशा 1 (0) पर मान्य होती है। बूलियन चर के साथ लबले की गई लीव को असाइनमेंट के रूप में इंटरप्रिट किया जाता है, अर्थात यह बूलियन फलन को निरूपित करता है जो यदि और केवल यदि हो तो 1 पर मूल्यांकन करता है। -नोड द्वारा दर्शाया गया बूलियन फलन वह है जो 1 का मूल्यांकन करता है, यदि और केवल यदि इसकी सभी शाखाओं के बूलियन फलन 1 पर मूल्यांकन करती है। उसी तरह, -नोड एक बूलियन फलन को निरूपित करता है जो 1 का मूल्यांकन करता है, यदि और केवल यदि इसकी कम से कम एक शाखा का बूलियन फलन 1 का मूल्यांकन करती है। अंत में, -नोड उसकी शाखा के विपरीत बूलियन फलन को निरूपित करता है, अर्थात इस फलन को निरूपित करता है जो 1 का मूल्यांकन करता है, यदि और केवल यदि उसकी शाखा का बूलियन फलन 0 का मूल्यांकन करता है।
पीडीएजी, बीडीडी, और एनएनएफ
प्रत्येक बाइनरी डिसिज़न डायग्राम (बीडीडी) और प्रत्येक नेगशन नार्मल फॉर्म (एनएनएफ) भी कुछ विशेष गुणों के साथ एक प्रकार का पीडीएजी हैं। निम्नलिखित चित्र बूलियन फलन को दर्शाते हैं:
यह भी देखें
- डेटा स्ट्रक्चर
- बूलियन संतुष्टि समस्या
- प्रोपोज़िशन
संदर्भ
- M. Wachter & R. Haenni, "Propositional DAGs: a New Graph-Based Language for Representing Boolean Functions", KR'06, 10th International Conference on Principles of Knowledge Representation and Reasoning, Lake District, UK, 2006.
- M. Wachter & R. Haenni, "Probabilistic Equivalence Checking with Propositional DAGs", Technical Report iam-2006-001, Institute of Computer Science and Applied Mathematics, University of Bern, Switzerland, 2006.
- M. Wachter, R. Haenni & J. Jonczy, "Reliability and Diagnostics of Modular Systems: a New Probabilistic Approach", DX'06, 18th International Workshop on Principles of Diagnosis, Peñaranda de Duero, Burgos, Spain, 2006.
