是否有任何算法来确定 NAND 或 NOR 门的最小数量
实现布尔表达式需要？我们可以通过最小的卡诺图得到一个 AND-OR 形式作为质蕴涵项（据我所知，Quine-McCluskey算法确定性地获得它们）。NAND 或 NOR 实现是否也存在类似的技术？至少，即使没有找到实际图表，这种技术也应该确定所需的最小 NAND/NOR 门数量？
将德摩根定律应用于质蕴涵项似乎不是确定性的，
A ⊕ B = A'B + AB' = ((A'B)'(AB')')' [5 NAND gates]
A ⊕ B = (AB + A'B')' = ((ABAB+ABB') + (A'AB+A'B'))' = (AB(AB+B') + A'(AB+B'))' = ((AB+A')(AB+B'))' = (((AB)'A)'((AB)'B)')' [4 NAND gates by reusing (AB)']
您只能通过解决整数规划问题[或等价物，见下文]来找到多级网络中的最小门数。这个问题是 NP 完全的，所以只能解决十几个门左右的问题。
存在不会给你最小数量但在所需时间方面更容易处理的近似方法......这些本身就是一个巨大的话题，基本上是多级优化的整个领域。您可以在此处阅读 [免费] 概述。
对于NAND的小型网络（最多4个变量），通过穷举[或等效方法]已经完全解决了这个问题。Elizabeth Ann Ernst有一篇相当近期的 [2009]博士论文总结了古老的结果并对其进行了扩展。Ernst 使用分支定界，它在实践中改进了穷举法，但不是渐近的。她还指出，其他隐式枚举方法，如整数规划或 CSP（约束满足，通过 SAT 解决）在实践中表现更差。
她显然为她的方法编写了一些软件（称为 BESS），但我不确定它是否在某个地方公开可用。她的论文全文可在umich免费获得。实际上，您找到了 2-input xor 的最小表达式（显然是您的第二个），下面突出显示的那个：
她还将准确的结果（对于 NAND）与ABC的启发式优化器产生的结果进行了比较。
ABC 能够为已知最优网络的 4,043 个函数中的 340 个生成最优网络。对于 ABC 没有产生最优网络的那些函数，它平均比最优网络大 36%[.]
（显然）有一些 [更大的] BESS 没有完成的网络，但允许找到一个上限（在放弃搜索的点）。对于那些 ABC 做得很好[就找到的界限而言很好]，正如您从下面的第二张图中看到的那样。
那里可能有更好的技术，但早在黑暗时代，我发现卡诺图工作得很好
NAND 后跟 NAND 等价于 AND 后跟 OR。
NOR 后跟 NOR 等价于 OR 后跟 AND。
NAND 后跟 NOR 将等同于 AND 后跟 AND，这并没有多大意义。NOR 后跟 NAND 类似地等同于 OR 后跟 OR。
我不相信在一般情况下有任何可行的方法来找到解决大量输入问题的最小解决方案（显然对于小输入计数，你可以蛮力）。Quine-McClusky 只关注两级解决方案（最小的两级解决方案通常不是整体的最小解决方案），并且在复杂的真值表和大量输入的情况下可能在计算上不可行。
最好的算法是Espresso算法。在某种程度上，这是在 FPGA 综合中实现的
Logic friday是一款您可以使用的软件。注意：这将 XOR 减少到 5 个 NAND 门。