प्रस्तावित निर्देशित अचक्रीय आलेख

प्रोपोज़िशनल डायरेक्टेड एसाइक्लिक ग्राफ़ (पीडीएजी) एक प्रकार का डेटा स्ट्रक्चर है जो बूलियन फलन को प्रतिष्ठित करने के लिए उपयोग की जाती है। बूलियन फलन निम्नलिखित रूप में मूलभूत, डायरेक्टेड एसाइक्लिक ग्राफ़ के रूप में दर्शाया जा सकता है:

• लीव्स को $\top$ (सत्य), $\bot$ (असत्य), या बूलियन चर (वेरिएबल) के साथ लेबल किया जाता है।
• नॉन-लीव्स $\bigtriangleup$ (लॉजिकल और), $\bigtriangledown$ (लॉजिकल या) और $\Diamond$ (लॉजिकल नहीं) हैं।
• $\bigtriangleup$- और $\bigtriangledown$-नोड्स में कम से कम एक शाखा होती है।
• $\Diamond$-नोड में यथार्थ रूप से एक ही शाखा होती है।

$\top$ ($\bot$) के साथ लेबल की गई लीव्स नियत बूलियन फलन को निरूपित करती हैं, जो हमेशा 1 (0) पर मान्य होती है। बूलियन चर $x$ के साथ लबले की गई लीव को असाइनमेंट $x=1$ के रूप में इंटरप्रिट किया जाता है, अर्थात यह बूलियन फलन को निरूपित करता है जो यदि और केवल यदि $x=1$ हो तो 1 पर मूल्यांकन करता है। $\bigtriangleup$-नोड द्वारा दर्शाया गया बूलियन फलन वह है जो 1 का मूल्यांकन करता है, यदि और केवल यदि इसकी सभी शाखाओं के बूलियन फलन 1 पर मूल्यांकन करती है। उसी तरह, $\bigtriangledown$-नोड एक बूलियन फलन को निरूपित करता है जो 1 का मूल्यांकन करता है, यदि और केवल यदि इसकी कम से कम एक शाखा का बूलियन फलन 1 का मूल्यांकन करती है। अंत में, $\Diamond$-नोड उसकी शाखा के विपरीत बूलियन फलन को निरूपित करता है, अर्थात इस फलन को निरूपित करता है जो 1 का मूल्यांकन करता है, यदि और केवल यदि उसकी शाखा का बूलियन फलन 0 का मूल्यांकन करता है।

पीडीएजी, बीडीडी, और एनएनएफ

प्रत्येक बाइनरी डिसिज़न डायग्राम (बीडीडी) और प्रत्येक नेगशन नार्मल फॉर्म (एनएनएफ) भी कुछ विशेष गुणों के साथ एक प्रकार का पीडीएजी हैं। निम्नलिखित चित्र बूलियन फलन $f(x1,x2,x3)=-x1*-x2*-x3+x1*x2+x2*x3$ को दर्शाते हैं:

फलन f के लिए बीडीडी

फलन f के लिए पीडीएजी, बीडीडी से प्राप्त किया गया

फलन f के लिए पीडीएजी

यह भी देखें

• डेटा स्ट्रक्चर
• बूलियन संतुष्टि समस्या
• प्रोपोज़िशन

संदर्भ

• 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.