प्रस्तावित निर्देशित अचक्रीय आलेख
एक प्रस्तावित निर्देशित अचक्रीय ग्राफ (पीडीएजी) एक डेटा संरचना है जिसका उपयोग बूलियन समारोह का प्रतिनिधित्व करने के लिए किया जाता है। एक बूलियन फ़ंक्शन को निम्नलिखित रूप के रूटेड, निर्देशित चक्रीय ग्राफ के रूप में दर्शाया जा सकता है:
- पत्तियों पर लेबल लगा होता है (सत्य), (झूठा), या एक बूलियन चर।
- बिना पत्ते वाले होते हैं (तार्किक और), (तार्किक या) और (तार्किक नहीं)।
- - और -नोड्स में कम से कम एक बच्चा है।
- -नोड्स का ठीक एक बच्चा है।
के साथ लेबल छोड़ देता है () निरंतर बूलियन फ़ंक्शन का प्रतिनिधित्व करता है जो हमेशा 1 (0) का मूल्यांकन करता है। बूलियन चर के साथ लेबल किया गया पत्ता कार्य के रूप में समझा जाता है , यानी यह बूलियन फ़ंक्शन का प्रतिनिधित्व करता है जो 1 का मूल्यांकन करता है अगर और केवल अगर . बूलियन फ़ंक्शन a द्वारा दर्शाया गया है -नोड वह है जो 1 का मूल्यांकन करता है, अगर और केवल अगर उसके सभी बच्चों का बूलियन फ़ंक्शन 1 का मूल्यांकन करता है। इसी तरह, एक -नोड बूलियन फ़ंक्शन का प्रतिनिधित्व करता है जो 1 का मूल्यांकन करता है, अगर और केवल अगर कम से कम एक बच्चे का बूलियन फ़ंक्शन 1 का मूल्यांकन करता है। अंत में, ए -नोड अपने बच्चे के पूरक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है, यानी वह जो 1 का मूल्यांकन करता है, अगर और केवल अगर उसके बच्चे का बूलियन फ़ंक्शन 0 का मूल्यांकन करता है।
पीडीएजी, बीडीडी, और एनएनएफ
प्रत्येक द्विआधारी निर्णय आरेख | बाइनरी डिसीजन डायग्राम (BDD) और प्रत्येक निषेध सामान्य रूप | नेगेशन नॉर्मल फॉर्म (NNF) भी कुछ विशेष गुणों के साथ एक PDAG हैं। निम्न चित्र बूलियन फ़ंक्शन का प्रतिनिधित्व करते हैं :
यह भी देखें
- डेटा संरचना
- बूलियन संतुष्टि समस्या
- प्रस्ताव (गणित)
संदर्भ
- 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.