简化逻辑表达式

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;
  }
}

这是我目前为止做到的最简洁的方法。代码难以跟踪。我想知道的是，难道没有更好的算法来解决这个问题吗？我应该采取什么样的方法？我想画一个真值表，但我只能在真值上这样做。我用三个变量之间的等式做了一下，得到了这个表格:

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将消除前四行，这很好，然后我只剩下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行是不可能的。如果没有这个知识，我就无法将问题简化到如此少的操作。是否有一些数学/逻辑概念可以让我系统地执行这种“修剪”？

- Steven Lu

---

如果你最初将x_cache设置为y（而不是-1），那么这是否会删除第一个if语句？ - Vaughn Cato

我想是这样的。我之前加上了if语句是因为我不想做任何假设，但现在看来我已经做出了一个假设（x初始值等于y）...我已经更新了问题。 - Steven Lu

你想说的是，当x从等于y变为不等于y时，你想调用x_is_changed函数，而当x从不等于y变为等于y时，你想调用x_is_back函数，这样说是否合适？ - Vaughn Cato

@VaughnCato 是的，那正是我的意思。我之所以没有用你刚才那样的方式用语言表达它，是因为以那种方式呈现时极难理解。---- 我也希望新的 c 标签能给我带来更多的观众。 - Steven Lu

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();
}

- Vaughn Cato

---

这个不起作用。x = y = 2。x从2变为0。x从0变为1。我不想在从0到1的更改时调用x_is_changed，因为它最初不是2。 - Steven Lu

哦，我喜欢那个。我刚开始考虑在（x == y）上预测。 - Steven Lu

有没有办法避免缓存x的值？ - Steven Lu

好的，我认为我理解了你的第二种方法是如何工作的。但是，如果我试图在不干扰“things_happen”部分（“things_happen”是整个程序的其余部分）的情况下实现它。我认为你所能做的就是将先前状态的存储转移到程序执行位置，这非常聪明，但遗憾的是这个解决方案并不通用。无论如何，你已经赢得了我的认可。 - Steven Lu

我认为当你希望它退出时，things_happen()返回false。 - Vaughn Cato