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

[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

[psilogic.livejournal.com]

подставьте A=B=C=true :)

[ex-kpblca248.livejournal.com]

в этом случае остаётся С

[psilogic.livejournal.com]

что не есть правильно, т.к. фраза не сводится к "я пойду в боулинг"

[ex-kpblca248.livejournal.com]

Не сводится, но выбор осуществлён.
Вы подумайте просто.

[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, что неверно. Похоже, ДНФ самое универсальное, никуда не спрячешься, кругом ахтунг.

[psilogic.livejournal.com]

ага, для четырех громоздко получается

[ex-kpblca248.livejournal.com]

(A xor B xor C) and not (A and B and C) не работает, потому что в случае трёх истин выбора не происходит и решение зависает.

[psilogic.livejournal.com]

выбор тут ни при чем, не несите ерунду, если не понимаете, о чем идет речь

[ex-kpblca248.livejournal.com]

Я не несу.
Какое у Вас решение будет при трёх истинах? Вы никуда не пойдёте получается?
У Вас условие задачи не соответствует решению.

[psilogic.livejournal.com]

Я не несу.

несете :)

Какое у Вас решение будет при трёх истинах? Вы никуда не пойдёте получается?

При трех истинах я пойду во все три места.

[ex-kpblca248.livejournal.com]

>При трех истинах я пойду во все три места

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

Алгоритм такой
Я иду в А
Иначе иду в В
Иначе иду в С

Но в условии задачи нет того, что я никуда не иду, то есть
Иначе никуда.

[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"
Надеюсь, объяснила :)
Если нет, не ругайтесь, просто мысль.

[phantomer.livejournal.com]

"Выбора не происходит" это реально новое слово в науке. :-))

[ex-kpblca248.livejournal.com]

Оперировать небулевыми значениями булевыми операциями - тоже весьма оригинально.

[nomatrix.livejournal.com]

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

[psilogic.livejournal.com]

если все три операнда true, то по этой формуле получится true

[nomatrix.livejournal.com]

я-то думал, то, что правее AND, не выполняется при A=B=C=true:
A OR B XOR C = true OR true XOR true = (true OR true) XOR true = true XOR true = false

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

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

блин

[tbapb-xl.livejournal.com]

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

Re: блин

[psilogic.livejournal.com]

:))))

[q-styler.livejournal.com]

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

[aimant-la-vie.livejournal.com]

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

[psilogic.livejournal.com]

А ДНФ можно попробовать преобразовать по правилам мат.логики до наиболее короткого результата.

В ЭТОМ случае ДНФ для любого числа аргументов сократить не получится. Т.е. ДНФ тут единственная (с точностью до перестановки операндов) и сокращению не поддается.

[mamakarlo.livejournal.com]

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

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

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

[2macy.livejournal.com]

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

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

[psilogic.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

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