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

[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]

Избыточное "not (A and B and C)" в этом случае даёт false, и "and" превращает всё решение тоже в false

Так и должно быть. По условию я не иду во все три места одновременно, я иду только в одно из трех. Три "true" соответствуют утверждению, что я иду во все три места одновременно. То есть, ложному высказыванию. Результат формулы соответствует ложности высказывания.

Другими словами, формула должна давать на выходе true, когда только одно из высказываний A, B, C true, а два других - false. Во всех остальных случаях формула должна давать false. В том числе и когда все три высказывания true, на выходе должно быть false. Понятно?

[ex-kpblca248.livejournal.com]

Вы не учитываете, что человек не может пойти и в два места одновременно (как и в три).

Мне кажется нужно добавить в условие, что выбирающий не может пойти в два и в три места одновременно (что очевидно) и есть возможность никуда не пойти, тогда
(A xor B xor C) and not (A xor B xor C)

[ex-kpblca248.livejournal.com]

А ещё вернее получается совсем не красиво
(A xor B xor C) and ((A + B + C) <= 1)

[psilogic.livejournal.com]

Операция "+" по условию не предусматривалась :) Да и нет в природе такой операции "+", как вы нарисовали. Интуитивно понятно, что вы имели в виду, но тогда можно проще: A + B + C = 1.

[ex-kpblca248.livejournal.com]

Да-да, простите.

[psilogic.livejournal.com]

Вы не учитываете, что человек не может пойти и в два места одновременно (как и в три).

Учитываю. Может. Перечитайте условие. По условию человек утверждает, что пойдет только в одно. Надо выразить истинность его слов формулой.

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

Эта формула даст false при любых знгачениях переменных.

[ex-kpblca248.livejournal.com]

Всё, поняла. Вы правы.
Я не с той стороны зашла и все мои примеры действительно дурацкие.

[psilogic.livejournal.com]

А я думал, вы надо мной прикалываетесь :) Не расстраивайтесь :)

[ex-kpblca248.livejournal.com]

Я не расстраиваюсь. Я поняла, что Вы смотрите с точки зрения машины. Я же как простая выбирающая - нелинейно.

[psilogic.livejournal.com]

машины тут ни при чем, это логика еще времен Аристотеля :)

[ex-kpblca248.livejournal.com]

Я думаю, что логика существовала и раньше Аристотеля, как и Америка до её открывателей.

"Машинная" - в смысле с целью выразить формулой, годной для машинных вычислений. (Вы это сразу сказали в условии, можете не напоминать)
Можно и дальше придираться к этому слову, но, думаю, Вы не станете.

[ex-kpblca248.livejournal.com]

Знаете, я что подумала ещё - это не относится к задаче, а скорее к тому, что меня сбило с толку.
Например, есть два условия:
А = "пойти в кино"
В = "пойти в гости"
возникает вопрос, что тогда значит "true"? Сам процесс "идти", т.е. "да, пойду"?
Например, (A xor B) даёт:
1. "true", т.е. "пойду", а куда не известно.
2. А или В, т.е. "пойду в кино" или "пойду в гости", но эти два значения не равны и не могут быть одновременно "true"
Надеюсь, объяснила :)
Если нет, не ругайтесь, просто мысль.