Является ли `1 XOR 1 OR 1` неоднозначным в булевой алгебре?

Question

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

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

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

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

Answer 1

Мы можем использовать правила булевой алгебры , чтобы попытаться оценить выражение 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].

Answer 2

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

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

Answer 3

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

1. AND
2. XOR
3. ИЛИ

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

Answer 4

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