命題有向非巡回グラフ（めいだいゆうこうひじゅんかいグラフ、）とは、ブール関数を表現するために用いられるデータ構造である。ブール関数は、根付きの以下の形式の有向非巡回グラフとして表現できる。
葉には （真）、（偽）、あるいはブール変数のいずれかのラベルが付けられる。 葉以外のノードは （論理積）、（論理和）、（否定）のいずれかである。 ノードとノードは少なくとも1つの子を持つ。 ノードはちょうど1つの子を持つ。
（）でラベル付けされた葉は、常に1（0）に評価される定数のブール関数を表す。ブール変数でラベル付けされた葉は、割り当てとして解釈される。すなわちそれは、の場合に限り1に評価されるブール関数を表す。ノードが表すブール関数は、そのすべての子のブール関数が1に評価される場合に限り1に評価されるものである。同様に、ノードは、少なくとも1つの子のブール関数が1に評価される場合に限り1に評価されるブール関数を表す。最後に、ノードは、その子の補ブール関数、すなわちその子のブール関数が0に評価される場合に限り1に評価される関数を表す。
PDAG、BDD、NNF すべての二分決定図（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.