6

我有一个表情，假设，

a = 1 && (b = 1 || b != 0 ) && (c >= 35 || d != 5) && (c >= 38 || d = 6)

我希望它减少到，

a = 1 && b != 0 && (c >= 38 || d = 6)

有没有人有什么建议？指向任何算法的指针？

Nota Bene：我相信，卡诺图或 Quine-McCluskey 不是这里的选择。因为这些方法不处理灰色情况。我的意思是，表达只能减少到像 A 或 A' 或什么都没有，或者说是黑色或白色或无色的情况。但是在这里我有灰色阴影，正如你们所看到的。

解决方案：我已经在 Clojure 中为此编写了程序。我使用包含函数作为值的地图的地图。这很方便，只需几个组合的一些规则，你就很好。感谢您提供有用的答案。

4

2 回答 2

2

我认为您应该能够通过使用约束处理规则来实现您想要的。您需要编写简化 OR 和 AND 表达式的规则。

主要困难是约束蕴涵检查，它告诉您可以丢弃哪些部分。例如， (c >= 35 || d != 5) && (c >= 38 || d = 6) 简化为 (c >= 38 || d = 6) 因为前者由后者蕴涵，即后者更具体。不过，对于 OR 表达式，您需要选择更通用的部分。

谷歌发现了一篇关于 CHR 扩展的论文，其中包含对用户定义约束的蕴涵检查。我不知道足够多的 CHR 能够告诉您是否需要这样的扩展。

于 2012-02-28T16:13:40.900 回答
1

我相信这类事情在约束逻辑编程中经常发生。不幸的是，我没有足够的经验来提供更准确的细节，但这应该是一个很好的起点。

一般原则很简单：一个未绑定的变量可以有任何值；当您针对不等式对其进行测试时，它的一组可能值受到一个或多个间隔的限制。当/如果这些间隔收敛到一个点时，该变量将绑定到该值。如果，OTOH，对于间隔中的每个值，这些不等式中的任何一个都被认为是无法解决的，那么就会发生[编程]逻辑故障。

另请参阅this，了解如何在实践中使用 swi-prolog 完成此操作的示例。希望你能找到底层算法的链接或参考，这样你就可以在你选择的平台上重现它们（甚至可以找到现成的库）。

更新：我尝试使用 swi-prolog 和 clpfd 重现您的示例，但没有得到我预期的结果，只有接近的结果。这是我的代码：

?- [library(clpfd)].
simplify(A,B,C,D) :-
    A #= 1 ,
    (B #= 1 ; B #\= 0 ) ,
    (C #>= 35 ; D #\= 5) ,
    (C #>= 38 ; D #= 6).

我的结果是回溯（为了便于阅读而插入换行符）：

10 ?- simplify(A,B,C,D).

A = 1,
B = 1,
C in 38..sup ;

A = 1,
B = 1,
D = 6,
C in 35..sup ;

A = 1,
B = 1,
C in 38..sup,
D in inf..4\/6..sup ;

A = 1,
B = 1,
D = 6 ;

A = 1,
B in inf.. -1\/1..sup,
C in 38..sup ;

A = 1,
D = 6,
B in inf.. -1\/1..sup,
C in 35..sup ;

A = 1,
B in inf.. -1\/1..sup,
C in 38..sup,
D in inf..4\/6..sup ;

A = 1,
D = 6,
B in inf.. -1\/1..sup.

11 ?-

因此，该程序产生了 8 个结果，其中 2 个是您感兴趣的（第 5 个和第 8 个）：

A = 1,
B in inf.. -1\/1..sup,
C in 38..sup ;

A = 1,
D = 6,
B in inf.. -1\/1..sup.

另一个是多余的，也许可以使用简单、可自动化的逻辑规则来消除：

1st or 5th ==> 5th          [B == 1  or B != 0 --> B != 0]
2nd or 4th ==> 4th          [C >= 35 or True   --> True  ]
3rd or 1st ==> 1st ==> 5th  [D != 5  or True   --> True  ]
4th or 8th ==> 8th          [B == 1  or B != 0 --> B != 0]
6th or 8th ==> 8th          [C >= 35 or True   --> True  ]
7th or 3rd ==> 3rd ==> 5th  [B == 1  or B != 0 --> B != 0]

我知道这是一个通用解决方案还有很长的路要走，但正如我所说，希望这是一个开始......

PS我使用“常规” AND 和 OR ( ,and ;) 因为 clpfd 的 ( #/\and #\/) 给出了一个非常奇怪的结果，我自己无法理解......也许更有经验的人可以对此有所了解......

于 2012-02-28T07:30:12.067 回答