प्रस्तावित निर्देशित अचक्रीय आलेख: Difference between revisions
From Vigyanwiki
(Created page with "एक प्रस्तावित निर्देशित अचक्रीय ग्राफ (पीडीएजी) एक डेटा संरचना...") |
(Work done) |
||
| Line 1: | Line 1: | ||
'''प्रोपोज़िशनल डायरेक्टेड एसाइक्लिक ग्राफ़''' ('''पीडीएजी''') एक प्रकार का [[डेटा संरचना|डेटा स्ट्रक्चर]] है जो [[बूलियन समारोह|बूलियन फ़ंक्शन]] को प्रतिष्ठित करने के लिए उपयोग की जाती है। बूलियन फ़ंक्शन निम्नलिखित रूप में मूलभूत, [[निर्देशित अचक्रीय ग्राफ|डायरेक्टेड एसाइक्लिक ग्राफ़]] के रूप में दर्शाया जा सकता है: | |||
* | * लीव्स को <math>\top</math> (सत्य), <math>\bot</math> (असत्य), या बूलियन चर (वेरिएबल) के साथ लेबल किया जाता है। | ||
* | * नॉन-लीव्स <math>\bigtriangleup</math> (लॉजिकल और), <math>\bigtriangledown</math> (लॉजिकल या) और <math>\Diamond</math> (लॉजिकल नहीं) हैं। | ||
* <math>\bigtriangleup</math>- और <math>\bigtriangledown</math>-नोड्स में कम से कम एक | *<math>\bigtriangleup</math>- और <math>\bigtriangledown</math>-नोड्स में कम से कम एक शाखा होती है। | ||
* <math>\Diamond</math>- | * <math>\Diamond</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 09:38, 29 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.
