二叉判定图这种数据结构主要用来表示逻辑表达式,而现在人们已经研制了一些表示方法:比如二叉判定树、真值表、卡诺图等等,但是对于这些表达方式而言,存储空间的需要比较大,还存在着大量的冗余数据。二叉判定图则是在二叉判定树的基础上,消除了其中的冗余结点,减少了对存储空间的需求,从而提高了求解问题的速度。文中比较全面地介绍了二叉判定图的基本理论。首先由二叉判定树表示的布尔函数,引出了布尔函数的二叉判定图表示方法。之后详细的介绍了二叉判定图的构造算法。通过对二叉判定图理论的学习和研究,我提出了利用二叉判定图对极小碰集和约束满足问题求解的算法。极小碰集问题是在基于模型的诊断中遇到的问题。这种方法不会因剪枝而丢失解;而且不用求出全部的碰集,但是所求得的解却包含全部的极小碰集。约束满足问题作为人工智能领域的研究方向,在经过几十年的研究后,目前已经拥有了数量丰富的各种求解算法。本文给出了利用二叉判定图求约束满足问题的算法,并编程实现了对N皇后问题的求解。