命题逻辑 - 减少操作的次数 [英] Propositional Logic - Reducing the Number of Operations

问题描述

总之，我如果给定两个命题公式，是否有发现，仍然有输出作为两个公式相同操作的最短序列的标准方法不知道。例如，如果我们有如下的公式：

In short, I'm wondering if, given two propositional formulas, whether there is a standard method for finding the shortest sequence of operations that still have the same output as the two formulas. For example if we have the following formulas:

和

我们可以通过引入一个新的命题减少操作次数：

we can reduce the number of operations by introducing a new proposition:

然后问：变成了：

这从 19 减少操作（一元和二元）的数量 14 。对于新的逻辑电路问：是：

This reduced the number of operations (unary and binary) from 19 to 14. The new logic circuit for Q is:

我非常希望那里只有否定和析取。是否有任何命题转化为我的理想简化的一种演算法？而且是有引入新的命题像上面的算法？

Ideally I would like there to be only negations and disjunctions. Is there an algorithm for converting any proposition into my ideal simplified one? And is there an algorithm for introducing new propositions like above?

推荐答案

有是 - 经过大约50年的研究 - 仍然是多层次的逻辑综合尚无标准方法。这两个级别的情况下，可以使用卡诺图或的奎因McCluskey的方法。这里，最小项数被最小化。但是，这并不直接对应于以测定该函数值所需要的逻辑运算的次数。

There is - after some 50 years of research - still no standard method for multi-level logic synthesis. The two-level case can be decently tackled using Karnaugh maps or the Quine McCluskey method. Here, the number of minterms is minimized. But this does not directly correspond to the number of logical operations required to determine the function value.

加州伯克利大学开发了多种工具来生成启发式的解决方案。其中的一些工具是很好的包装逻辑周五1 。

The University of California at Berkeley developed several tools to generate heuristic solutions. Some of these tools are nicely packaged in Logic Friday 1.

输入你的函数Q：

进入：
问：=（A和（（B和C）+（B'和C'）））+（A'及（（B和C）+（B'和C'））'）

Entered: Q:=(A & ((B & C) + (B' & C'))) + (A' & ((B & C) + (B' & C'))');

最小化：
问：= A B C + A'B'C + A'B C'+ A B'C';

Minimized: Q: = A B C + A' B' C + A' B C' + A B' C';

映射到门后的操作输出：

注意：结果
最近的一个综合套件是克利福德狼的 Yosys 。

这篇关于命题逻辑 - 减少操作的次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！