c - 简化逻辑表达式

Question

注意:这不是作业。

我想提出正确的方法来设计正确的算法来处理这个简单的问题。

我有一个随时间变化的状态(用正整数表示)。我有另一个值，它是一个恒定的特定状态(用特定的正整数表示)，第一个状态可能等于。

最好这样说明:

// this is C pseudocode

int things_happen(int *value) {
  ... // value possibly gets changed!
}

const int y = VALUE_Y_CONST; 
int x = y; // to simplify things we assume x starts out equal to y

while (things_happen(&x)) {
  // I am now interested in changes to x with respect to y. 
  if (/* expression of interest */) { 
    x_is_changed(); // I want to know whenever x is no longer y
  }
  if (/* another expression of interest */) {
    x_is_back(); // and I want to know whenever x becomes equal to y again
  }
}

如何确定何时应该调用 x_is_changed() 和 x_is_back()？

到目前为止，在尝试编程时，我已经多次遇到这种情况。每次，我想出的解决方案看起来都异常复杂，而且经常有错误。

到目前为止，我的解决方案要求我创建第三个变量，我用它来缓存 while 循环底部的 x 值。它让我知道我的 x 从哪个值改变。有了这些知识，我然后使用看起来完全太多的条件语句:

int x_cache = y;
while(things_happen(&x)) {
  if (x_cache != x) {
    if (x == y && x_cache != y)
      x_is_back();
    else if (x != y && x_cache == y)
      x_is_changed();
    x_cache = x;
  }
}

这是迄今为止我完成的最简洁的方法。代码很难遵循。我想知道的是，有没有更好的算法来解决这个问题？我应该采取什么样的方法？我以为我可以画一个真值表，但我只能根据真值来做。我用 3 个变量之间的相等性完成了它并得到了这张表:

x_cache == x | x_cache == y | x == y  ||  x_is_changed | x_is_back
                                      || 
    T                T          T     ||       F            F 
    T                T          F     ||       F            F
    T                F          T     ||       F            F
    T                F          F     ||       F            F
    F                T          T     ||       F            F
    F                T          F     ||       T            F
    F                F          T     ||       F            T
    F                F          F     ||       F            F

这似乎是我在逻辑课上记得的唯一一件事。我注意到由于传递性，第 2、3 和 5 行是不可能的。所以如果我只考虑值之间的相等性检查，我肯定会限制自己。

我是否应该继续提出命题变量，并寻找能够减少我的操作总数的特定组合？一定有更简单的方法吗？针对任意条件提出最有效算法的一般问题显然是 NP 完全问题(关于变量的数量)。

进一步查看该表，划掉第 2、3 和 5 行，我看到条件 x_cache != x 将消除前 4 行，这很好，那么我是剩下 3 种可能性。我可以看到此时 x_cache == y 等于 x_is_changed，而且 x == y 等于 x_is_back 。

所以这意味着我可以从上面简化为:

...
  if (x_cache != x) {
    if (x == y)
      x_is_back();
    else if (x_cache == y)
      x_is_changed();
    x_cache = x;
  }
...

我仍然觉得这不是最优的。我认为没有其他关系运算符可以帮助解决这个问题。它可能实际上是最佳的，现在我想到了。

我凭直觉认为第 2、3 和 5 行是不可能的。没有这些知识，我无法将问题减少到如此少的操作。是否有一些数学/逻辑概念可以让我系统地执行这种“修剪”？

Answer 1

我认为最简单的形式是:

int x_cache = 1;
while(things_happen(&x)) {
  if (x_cache != (x==y)) {
    if (x == y)
      x_is_back();
    else
      x_is_changed();
    x_cache = (x==y);
  }
}

另一种选择是

for (;;) {
  while (things_happen(&x) && x==y) { }
  if (x==y) break;
  x_is_changed();
  while (things_happen(&x) && x!=y) { }
  if (x!=y) break;
  x_is_back();
}