完美模型的充要条件及其结构分析

纯ｄａｔａｌｏｇ的唯一模型定理在ｄａｔａｌｏｇ－ｎｏｔ程序中不成立，因此，在ｄａｔａｌｏｇ－ｎｏｔ程序的所有ｈｅｒｂｒａｎｄ模型中，必须有一种模型的选择标准来确定程序的语义．完美模型关系是一种合理的选择标准．然而，由于完美模型的复杂性阻止了它的发展．本文分析了完美模型，通过有向图，给出了有完美模型的充要条件，并且给出构造算法及其正确性证明．本文得到的结果是：对任一自反有向图ｇ，都能构造一个ｄａｔａｌｏｇ－ｎｏｔ程序ｐ，使得ｐ的完美模型图与ｇ同构.