Является ли `1 XOR 1 OR 1` неоднозначным в булевой алгебре? - PullRequest
3 голосов
/ 12 декабря 2011

Используя булеву алгебру (не конкретную языковую реализацию), можем ли мы оценить 1 ^ 1 + 1 (или 1 XOR 1 OR 1) однозначно?

Я могу получить две оценки:

 [I]:  (1 ^ 1) + 1 = 0 + 1 = 1
[II]:  1 ^ (1 + 1) = 1 ^ 1 = 0

Возможноесть какой-то определенный порядок операций или оценки слева направо?Или это не определено в булевой алгебре?

Ответы [ 4 ]

3 голосов
/ 12 декабря 2011

Мы можем использовать правила булевой алгебры , чтобы попытаться оценить выражение 1 XOR 1 OR 1.

Сейчас:

  • XOR получено из OR так, что A XOR B = (¬A AND B) OR (¬B AND A);
  • Ассоциативность говорит нам, что A OR (B OR C) = (A OR B) OR C;
  • Ассоциативность также говорит нам, что A AND (B AND C) = (A AND B) AND C

Итак, берём любую из возможных интерпретаций порядка оценки:

  (1 XOR 1) OR 1                       1 XOR (1 OR 1)

Несмотря на то, что у нас не определен «порядок оценки» слева направо, эти правила - все, что нам нужно, чтобы показать, что две возможные интерпретации не эквивалентны:

= (¬1 AND 1) OR (¬1 AND 1) OR 1      = (¬1 AND (1 OR 1)) OR (¬(1 OR 1) AND 1)
= (0 AND 1) OR (0 AND 1) OR 1        = (0 AND 1) OR (0 AND 1)
= 0 OR 0 OR 1                        = 0 OR 0
= 1                                  = 0

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

(И, конечно, изучение выражения A XOR B OR C & forall; A, B, C, конечно, значительно сложнее! Но если выражение неоднозначно только для одного значения из всех три входа, тогда зачем проверять другие?)

Этот контекст обычно предоставляется в правилах порядка оценки для конкретного языка. Языки типа C дают XOR низкий приоритет (что-то, что Ричи не понравилось); напротив, математическое соглашение диктует ассоциативность слева направо , где никакая другая аксиома не может быть применена, и двусмысленность присутствует в противном случае.

Итак, в основном, поскольку мы игнорируем языковые правила, вы, вероятно, согласитесь с [I].

1 голос
/ 12 декабря 2011

Большинство языков делают XOR, а затем OR; опытные программисты в любом случае поставят скобки, чтобы прояснить намерение.

Многие современные языки выполняют так называемую быструю или короткую оценку, поэтому 0 & ? всегда 0, поэтому ? не будет оцениваться; то же самое с 1 + ?.

0 голосов
/ 12 декабря 2011

В c #, например, приоритет оператора для побитовых операторов:

  1. AND
  2. XOR
  3. ИЛИ

Но это может отличаться для другого языка.Если приоритет одинаков, то операции выполняются слева направо.Логического оператора XOR нет, но вы можете использовать NOT EQUAL (! =).

0 голосов
/ 12 декабря 2011

Я не думаю, что существует общепринятый порядок приоритета с логическими операторами.Оценка будет полностью специфической для языка.

...