判定图

判定图（decision diagram），理学-计算机科学技术-计算机科学理论-概率统计-概率表示，用来表示一个布尔函数的有向无环图。又称二元判定图。判定图是表达布尔函数的一种数据结构。布尔函数的表示有许多种，最直接的表示方法就是对应表，但这种表示方法非常耗空间资源。二元判定图是一种更有效的表示方法，它将布尔函数用图的形式表示。二元判定图是一个二叉树，它包含终节点（叶子结点）和非终节点。每一个非终节点代表一个基本事件，它有两个状态，取值为1或者0。两个状态分别对应判定图在该非终节点处的两个分支。每一个终节点代表布尔函数的取值，只有一个状态是1或者0。二元判定图的构造有许多种，使用不同的变量顺序可以构造不同的二元判定图，它们可能具有不同数量的节点。在使用时，应选择节点最少的二元判定图，以节约计算资源。二元判定图广泛地用于电路的设计和测试过程。每一个二元判定图都可以在硬件中实现，计算非常高效。