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

[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

[batva.livejournal.com]

до первой скобочки я додумался, а дальше... правда я не учил логику

[ex-kpblca248.livejournal.com]

(A xor B) xor C

[phantomer.livejournal.com]

(A xor B xor C) and not (A and B and C)

Это работает, но только для трёх аргументов, а масштабирования не получается. Для четырёх аргументов формула

(A xor B xor C xor D) and not (A and B and C and D)

не пашет, ибо для t,t,t,f она даст t, что неверно. Похоже, ДНФ самое универсальное, никуда не спрячешься, кругом ахтунг.

[nomatrix.livejournal.com]

я так понял, требуется формула, равная истине тогда, когда истине равна только одна из переменных.
Может, это подойдет?
(A XOR B XOR C) AND (A OR B XOR C)
Сэкономил одну операцию.

блин

[tbapb-xl.livejournal.com]

благодаря вам узнал, что забыл что такое xor :))

[q-styler.livejournal.com]

если упростить первую фразу, то получается третья

[aimant-la-vie.livejournal.com]

почитал все эти комменты и осознал, что я, видимо, простак, так как составил ДНФ и не парился.
Уж даже не знаю, что длиннее - ДНФ или попытки сделать вариант с XOR правильным для любого числа аргументов. Кстати, если речь идет о программировании, грош цена такому неуниверсальному, частному решению.
А ДНФ можно попробовать преобразовать по правилам мат.логики до наиболее короткого результата. Только вот начинать-то все равно с ДНФ надо, я думаю.

[mamakarlo.livejournal.com]

Вы знаете, я ни черта не понимаю в логике. Точнее, скажем так, я от формул устаю быстро =) Только при большой необходимости стану вникать во все эти операнты и расписанные Вами уравнения.
Но я вижу одну большую ошибку, которая почему-то никак не повлияла на ход Ваших рассуждений. Честно говоря, сначала я была уверена, что в ней и состоит прикол, мешающий логике.

"Я либо пойду сегодня в кино, либо в гости к родителям, либо в боулинг"

Нельзя сопоставлять "пойду" и "в гости". Надеюсь, подробно объяснять нет необходимости =)

[2macy.livejournal.com]

А мне в четверг сдавать логику .. у меня есть несколько дней чтобы научится решать подобные задачи ..рисовать круги Эйлера .. и еще что-то там …

Тяжко будет мне .. :) хотя и не так сложно как тут ..

[mr-ri.livejournal.com]

Ладно пробую, пусть есть N условий либо-либо.

f(n) = (!(g(n-1) && n)) && (n xor f(n-1))

g(k) = 1 || 2 || .. || k

f(1) = 1

Вроде как-то так..