algorithm - 将多个交集重构为相交并集组

Question

给定一组规则，这些规则是一些已知值(组、类型、属性)的逻辑交集，这些规则组合起来给出一些值，如下所示:

group1 AND type1 AND property1 = value1
group1 AND type1 AND property2 = value2
group1 AND type1 AND property3 = value3
group1 AND type2 AND property1 = value1
group1 AND type2 AND property4 = value1
group2 AND type1 AND property2 = value2

并且以下内容成立:

• 组/类型/属性的集合是有限且已知的
• 组/类型/属性组合的唯一给定规则
• 许多规则可以引用一个值

我如何找到最佳解决方案以将这些规则“折叠”成一种格式，在该格式中组契约(Contract)一组的多个值(如下)，同时保持对原始查找的相同逻辑解释？

(group1) AND (type1 OR type2) AND (property1) = value1
(group1 OR group2) AND (type1) AND (property2) = value2
(group1) AND (type1) AND (property3) = value3
(group1) AND (type2) AND (property4) = value1

目标:包含与原始查找相同的逻辑信息的规则数量最少。

一种方法可以是采用原始查找“键”，按第一个值分组，然后按两个键分组，并折叠剩余键的不同实例，可以为键的每个组合重复。结果朝着正确的方向前进，但不能保证多步方法是最佳的。

如果这实际上是一个普遍的问题，我们将不胜感激任何关于更好方法的想法，或阅读指南。

如果需要，很乐意提供任何说明。

*为笨拙的标题道歉 - 希望描述了一般问题

编辑: 我认为这个问题(没有具体答案)表达了寻找 Union of all intersecting sets 的问题。 .

编辑 2: 我应该说，目标形式实际上是一个要求，而不是来自@timrau 的逻辑最佳解决方案。形式是 (groups) AND (types) A​​ND (properties) => value，其中 groups/types/properties 仅用 OR 表示。

Answer 1

对于每个可能的值，以积和形式形成一个 bool 公式。 (为了简单起见，我用g1代表group1，t1代表type1，p1 代表property1 和v1 代表value1)

v1 = g1 t1 p1 + g1 t2 p1 + g1 t2 p4
v2 = g1 t1 p2 + g2 t1 p2
v3 = g1 t1 p3

然后，您可以应用任何逻辑最小化算法/系统，例如 Quine-McCluskey , Espresso , ABC , Logic Friday甚至 Karnaugh map如果您真的打算手动最小化它们。

最小化后，我们得到

v1 = g1 (t1+t2) p1 + g1 t2 p4
v2 = (g1+g2) t1 p2
v3 = g1 t1 p3

然后可以将它们转换回您的原始逻辑公式。