Упрощение логических выражений - PullRequest
Новая
       32

Упрощение логических выражений

3 голосов
/ 29 сентября 2011

ПРИМЕЧАНИЕ: это НЕ домашнее задание.

Я хочу предложить правильный подход к разработке правильного алгоритма для решения этой простой проблемы.

У меня есть состояние (представимое с положительным целым числом), которое меняется со временем.У меня есть другое значение, которое представляет собой постоянное определенное состояние (представляемое определенным положительным целым числом), которому первое состояние может стать равным.

Лучше всего проиллюстрировать это так: 

// 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()?

Я уже несколько раз сталкивался с этой ситуацией, когда пытался что-то программировать.Каждый раз, решение, которое я придумываю, выглядит неоправданно сложным, и часто возникают ошибки.

Пока мои решения требуют, чтобы я создал третью переменную, которую я использую для кэширования значения x в нижней части этого цикла while.Это позволяет мне узнать, какое значение у моего 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 невозможны.Без этого знания я не смог бы свести проблему к такому количеству операций.Есть ли какая-то математическая / логическая концепция, которая позволяет мне систематически выполнять эту «обрезку»?

1 Ответ

3 голосов
/ 29 сентября 2011

Я думаю, что самая простая форма: 

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