1

尽管这个问题听起来很奇怪，但我实际上有一组变量和一些它们产生有效状态的条件。我当然会根据我的理解写出测试它们的代码，但是是否有一个系统/代码生成器可以生成具有所有适当优化的有效代码？

  $a   $b   Output
 ---------------
  0     0    1
  0     1    0
  1     0    1
  1     1    0

所以这个系统应该生成php代码：

 if($b==0) {}

为了这：

  $a   $b   Output
 ---------------
  0     0    0
  0     1    1
  1     0    1
  1     1    0

它应该输出：

 if(($a!=1 && $b!=1) && ($a!=0 && $b!=0)) {}
 // any better way?

当然，这里的 0 和 1 只是为了说明 - 我需要比较实际的字符串/值，所以聪明的乘法技术不会起作用。

4

4 回答 4

2

你的系统是布尔逻辑的扩展，（除了值之间的 &&、|| 和 ! 围绕某些值，你也使用仅基于一个真值的结果，尽管有多个真值）。所以正常的方法是行不通的，我查看了 K-Map，我认为它在这里行不通。

您可以在所有可能的组合中组合所有 A、B、C、...，可能为所有可能的子集引入新值（以处理 (A || B) && C），然后尝试所有可能的运算符组合在所有这些子集上查看运算符组合中的一个是否适用于所有组合，然后最后推断出一条规则，也许使用动态编程你可以加快一点速度，但对于任何超过几个的情况来说，它都会很慢值，并且编程会很麻烦。（找到这些规则将远远超过 O(n^3)）

更快/更容易/更快但更多内存成本的解决方案只是将所有可能的组合存储为真（或所有为假，取决于哪个列表更短）在哈希表/字典/数组中。

于 2011-04-06T13:09:10.837 回答
1

您应该能够通过分析真值表的K-map然后编写表达式来生成优化的解决方案。

于 2011-04-06T13:03:02.353 回答
0

有很多关于手工操作的文献。见卡诺图。您可以自动化其中一种技术。

但本质上，您要做的是构建一个表示真值表的简单布尔方程，然后对该方程应用符号布尔简化器（或最小化器）（硬件语言合成器将其作为代码生成过程的一部分）。

构建朴素方程很容易：为真值表的每一行建立一个合取，并取所有合取的析取。你的第一个表会产生简单的等式：

 (~a & ~b)  |  (a & ~b)

如果您对此应用布尔简化：

  ((~a | a) & ~b)  // combine terms
  (TRUE & ~b )    // consequence of ~a | a
  ~b  // the answer

你的第二个表会产生天真的方程：

 (~a & b) | (a & ~b )

这并没有进一步简化。

您可以使用程序转换系统来完成此操作。这样的系统通常允许您为输入语言（在本例中为真值表）定义解析器，并定义从输入语言到输出语言的转换，以及对输出语言的更多转换。您的输入到输出转换会将真值表符号映射到布尔方程符号。然后，布尔方程的变换将进行简化。

一旦你有了一个简化的公式，你就想应用另一组转换来从纯布尔代数映射到你的最终计算机语言，在你的例子中是 PHP。

我们经常使用我们的DMS 软件再工程工具包来做这种事情。DMS 为问题带来了一些很好的帮助：它理解关联和交换代数重写，这使得在面对复杂公式时产生简化方程更容易和更健壮。

在许多情况下，我们已经将 DMS 应用于具有数十万字面量（A 或 ~A 形式的项）的代数布尔公式。一个例子是一个代码生成器，它接受关于如何根据传感器（读取工厂状态）和执行器（改变工厂状态的东西）来控制工厂（字面意思）的描述，生成方程，简化它们，然后翻译将它们转换为用于称为 PLC 的工业控制器的多种不同目标计算机语言。

您可以看到一个示例，不是布尔简化，而是使用 DMS进行实际代数简化。布尔简化更容易编写：-}

于 2011-04-07T16:08:07.617 回答
0

我认为 CKen ( http://cken.sourceforge.net/ ) (对你有好处)。

CKen 支持“大写”和“小写”，因此它支持 58 (= 2x29) 个单变量！

最重要的是，可以在其中使用多表达式（通过分隔符）：

例子：a,b,c,d,e;(a+b)*c;d*e#a;

另一方面，它非常快！

在表达式中使用它（变量）之前，您必须定义变量。

于 2015-04-06T09:49:48.547 回答