我该如何将一个自解释的全字母句表示为布尔函数？

Question

自枚举的句子维基文章指出，它们是使用二叉决策图计算的。我一直在阅读有关BDD的内容，据我理解，您需要将某些问题表示为布尔函数，然后才能为其构建BDD。

我该如何做？

我已经思考了几天，我相当确定您可以使用简单的编码来表示布尔函数的输入：

10000 01010 01011 10101 ...
16A's 10B's 11C's 21D's ...

因此，对于以“十六个A，十个B，十一个C，二十一个D”开头的完美句子（pangram），您可以将其表示为10000010100101110101...。

这意味着布尔函数中有26 * 5 = 130个变量，假设您将字符的最大频率限制为32次出现。

输出应该是表示是否为自计数完美句子，即句子是否描述了其自己的频率集。

要做到这一点，肯定需要使用散列表（或几个）。

因此，对于字母E，散列表可能如下开始：

one   -> 1
two   -> 0
three -> 2
four  -> 0
five  -> 1
...

在二进制中，它可能看起来像：

1   -> 1
10  -> 0
11  -> 10
100 -> 0
101 -> 1

如果从E哈希表中查找的所有值的总和等于与E相对应的五个输入位，则自枚举排列的该部分是正确的。如果所有部分都正确，则布尔函数应该产生1，否则为0。

我相当确定我可以想出如何使用布尔函数进行加法运算以及如何检查两个数字是否相等。然而，我不知道如何将哈希表表示为布尔函数。此外，连接所有部分在我看来可能会使我困惑。

有什么想法？创意？合作？我想看看这个项目的发展。

提前致谢。

- Chris

---

有一些线索：http://www.fatrazie.com/EWpangram.html - Tom Sirgedas

这是一个非常有趣的问题，我已经享受思考了几个小时。个人而言，我会尝试使用搜索来解决问题，而不是尝试使用布尔函数进行数学求解。我查看了一些关于此问题的文献[链接]（http://scholar.google.com/scholar?q=pangram+search），这些论文比我更优雅地提出了解决方法。希望这可以帮到你，非常感谢让我度过了几个非常有趣的思考时光。Dave - stormCloud

确实非常有趣。也许你会发现这份关于二进制决策图的文档很有用：http://www.voronkov.com/lics_doc.cgi?what=chapter&n=10 - cprogcr

嗨，迈克。我没有构建这个，但我更深入地探索了这个领域。如果你从二进制电路设计的角度考虑问题，我觉得它更易于理解。通过组合加法器、或门、与门等，您可以构建一个复杂的门电路，该电路接受某些编码形式的测试用例，并输出一个单独的引脚，指示它是否是自枚举的完美句子。我认为最好使用硬件描述语言来实现，然后将其折叠成二进制函数。然后，您可以将其馈送到许多BDD程序之一。 - Chris

对于任何偶然发现这个问题的人，我确实在这方面有所进展。最终，我将自枚举回文句的问题简化为布尔可满足性问题，并围绕这个想法构建了一种编程语言，它在这里：https://sentient-lang.org/。 - Chris

Answer 1

以我个人看来，BDD的使用，如在此上下文中所用，只是一种表达和帮助操纵用于评估的表达式的方式，例如，如果您的句子满足成为自枚举全字母句的要求。有一些规则可以用更容易理解的方式来操纵它们，而不是用布尔代数中语句操作的方式，因为它们在这种符号表示法中比在布尔代数中更容易表示，类似于8000个变量的多项式在其一般形式下处理比在其他一些代数符号下处理更困难。计算机算法可以用于操纵其中任何一个，因此您最好的选择可能是查找并调整适合您需求的算法。您可能会发现此文档很有帮助。

谷歌也可能有助于寻找其他资源。

- AJMansfield