有限多值变量真值表转AND/OR/=谓词的算法与工具咨询

布尔场景下从真值表构造DNF的方法完全可以泛化到有限离散取值变量的场景，本质是多值逻辑下的析取范式构造与化简，全程只需要用到AND、OR、=三类运算符，不需要额外算子。

具体算法流程 #

• 第一步先做初始规则构造，逻辑和布尔DNF的最小项生成完全一致：把所有输出结果为1的输入组合全部筛出来，每一组输入对应一个合取子句。比如某组正例的取值是a=A3、b=B2、c=C1，对应的子句就是(a = A3) AND (b = B2) AND (c = C1)。所有这类子句用OR连接，就得到了能覆盖全部正例的初始表达式，最后补一条“所有子句都不满足则输出0”的兜底规则即可。
• 第二步做规则化简，用泛化版的奎因-麦克拉斯基算法就行，核心合并规则非常简单：如果两个合取子句除了某一个变量的取值约束不一样，剩下所有变量的取值约束完全相同，且两个子句都对应正例输出，就可以直接消去这个变量的约束，合并成一个更短的子句。举个例子，(a=A3) AND (b=B2) AND (c=C1)和(a=A3) AND (b=B2) AND (c=C2)两个子句，只有c的取值不同，就可以直接合并成(a = A3) AND (b = B2)，和你给出的参考规则形式完全一致。
• 反复执行上面的合并操作，直到没有新的子句可以生成为止，再删掉所有被更短子句完全覆盖的冗余子句：比如如果已经有(a = A2) -> 1这条规则，那么所有a取A2、不管b和c是什么取值的长子句全是多余的，直接删掉就行。

适配当前场景的实操提示 #

提到的实际场景只有3个变量，单变量最多30个取值，总输入空间最大也就27000种组合，规模非常小：

• 不需要找复杂的专用工具，写个几十行的简单脚本就能跑完全流程：先枚举所有正例生成初始最小项，循环做合并、去重、删冗余操作直到收敛，算力消耗极低，根本不会有性能问题。
• 最终输出规则的时候，把约束变量更少的短规则排在前面，判断时命中任意一条就返回1，所有规则都没命中就返回0，和参考输出格式完全匹配。

内容的提问来源于stack exchange，提问作者Aidar