Ловушка для логиков ;)

[psilogic]

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

Есть фраза: "я либо пойду сегодня в кино, либо в гости к родителям, либо в боулинг".
Как логическими операциями связать три варианта действий:
A = "я пойду сегодня в кино"
B = "я пойду сегодня в гости к родителям"
C = "я пойду сегодня в боулинг"
?

Допускается применять операции or, xor, and, not. Формула должна быть по-короче.


Простаки, которые реально учили логику, начнут составлять дизъюнктивную нормальную форму. Примерно так:

[ A and (not B) and (not C) ] or [ (not A) and B and (not C) ] or [ (not A) and (not B) and C ]
Это правильно, но длинно.

Те, кто по-хитрее, заметят операцию "xor". И напишут:

A xor B xor C

И тут то вы их обломаете :) По смыслу фразы нельзя пойти сразу во все три места. Однако, если подставить три раза true, то получим:

A xor B xor C = true xor true xor true = false xor true = true

А должно быть false, т.к. не пойдет чел сразу в три места.

Вот правильная и сравнительно короткая запись:

(A xor B xor C) and not (A and B and C)
- т.е. три "xor"-a и исключаем "плохой" случай, когда все true.

Интересно, можно ли написать еще короче?
Кстати, получается, что для довольно обычной конструкции "... либо ... либо ..." - когда союз "либо" соединяет три и более условия, нет логической операции. Для двух работает A xor B, а для 3, 4 и более - ничего подходящего.

Comments

[psilogic.livejournal.com]

Нет, все выполняется. В C++ есть оптимизация, но она не влияет на булевский результат, а только н апобочные эффекты вызова функций и выглядит по-другому:
false and ... = false, правее не выполняется
true or ... = true, правее не выполняется

[nomatrix.livejournal.com]

Шаблону true or ... = true соответствовало бы такое выражение:
true OR (true XOR true)
Но поскольку Вы сами писали однажды, что
Операции одного приоритета выполняются слева направо,
скобки по умолчанию ставятся вокруг операндов самой левой операции OR, т.е.
(true OR true) XOR true.
Да, оптимизатор скажет, что выражение под скобками равно true. Но ведь потом этому true сделают XOR с еще одним true, и в результате получистя false?
Или я пропустил какой-то важный момент в Вашем учебнике?

[psilogic.livejournal.com]

Конечно, при необходимости то, что на месте многоточия, надо заключать в скобки, чтобы сохранить порядок действий.