如何将嵌套Prolog规则展平为普通Horn子句适配Clingo规则库？

问题背景 #

需要把包含嵌套析取、合取、否定的Prolog规则，拆解成无嵌套的Horn子句风格规则，适配Answer Set Programming工具Clingo。比如这条Prolog规则：

answer(X) :- cond1(X),
             \+ (cond2(X), cond3(X)),
             (cond4(X)
              ; cond5(X), cond6(X)).

要转换成下面4条独立规则：

answer(X) :- cond1(X), not cond2(X), cond4(X).
answer(X) :- cond1(X), not cond2(X), cond5(X), cond6(X).
answer(X) :- cond1(X), not cond3(X), cond4(X).
answer(X) :- cond1(X), not cond3(X), cond5(X), cond6(X).

核心转换逻辑 #

转换的关键是利用逻辑等价律展开嵌套结构，再拆分出所有可能的规则分支：

1. 处理嵌套否定合取：Prolog里的\+(A, B)遵循德摩根定律，等价于not A ; not B，转换时要把这个嵌套否定拆成两个析取分支
2. 拆分析取分支：规则体里的任何析取(C ; D)，都需要把原规则拆成多条规则，每条规则对应一个析取分支
3. 组合所有分支：把否定展开的分支和原有的析取分支做笛卡尔积，生成所有可能的合法规则组合

对应上面的例子：

• 先把\+(cond2(X), cond3(X))展开成not cond2(X) ; not cond3(X)
• 原规则体变成cond1(X), (not cond2(X) ; not cond3(X)), (cond4(X) ; cond5(X), cond6(X))
• 两个析取部分的笛卡尔积刚好是4种组合，每个组合对应一条新规则

通用转换步骤 #

1. 展开否定嵌套：对规则体中所有\+(A1, A2, ..., An)形式的嵌套否定，用德摩根定律替换成not A1 ; not A2 ; ... ; not An
2. 识别所有析取分支：把规则体里的所有析取结构（包括刚展开的）都拆分为独立分支选项
3. 生成规则组合：将所有分支选项做笛卡尔积，每个组合作为一条新规则的体，原规则头保持不变
4. 替换否定符号：把Prolog的\+换成ASP的not

批量转换思路 #

如果要处理大量规则，可以写个脚本或者用Prolog实现自动转换：

• 先解析Prolog规则的结构，拆分出规则头和规则体的各个逻辑项
• 递归展开所有嵌套的逻辑表达式：合取保留为项列表，析拆分为分支，否定合取按德摩根展开
• 对所有分支做笛卡尔积，生成每条新规则的体
• 最后输出成Clingo能识别的规则格式

内容的提问来源于stack exchange，提问作者이진우