Одна из известных задач про принцессу и тигра имеет формулировку:
Хотелось бы понять, как можно решить эту задачу не просто логически, а математически. Скорее всего, надо взять переменные:
и с их помощью формализовать выражения, а затем преобразовать. Помогите разобраться, как будут выглядеть надписи на табличках, представленные через эти переменные? Будет ли верным такое рассуждение? Если - f1 - надпись на первой двери - f2 - на второй, то общее уравнение имеет вид:
(частично использовал советы Limit-Sun) задан 19 Май '12 13:58 carapuz |
Ну, если пользоваться вашей терминологией, то получим следующее: "Что выбрать - большая разница (в одной комнате принцесса, в другой тигр или наоборот)" $% (X_1\wedge\overline{Y_1}\wedge\overline{X_2}\wedge Y_2)\vee(Y_1\wedge\overline{X_1}\wedge\overline{Y_2}\wedge X_2) $% Соответственно отрицание к этому утверждению (принцесса и принцесса или тигр и тигр) $% (X_1\wedge\overline{Y_1}\wedge X_2\wedge\overline{Y_2})\vee(Y_1\wedge\overline{X_1}\wedge Y_2\wedge\overline{X_2}) $% "Лучше выбрать первую комнату" - ну это понятно $% X_1 $% Далле аккрутно всё это записываем: $% (((X_1\wedge\overline{Y_1}\wedge\overline{X_2}\wedge Y_2)\vee(Y_1\wedge\overline{X_1}\wedge\overline{Y_2}\wedge X_2))\wedge X_1\wedge\overline{Y_1}\vee ((X_1\wedge\overline{Y_1}\wedge X_2\wedge\overline{Y_2})\vee\\(Y_1\wedge\overline{X_1}\wedge Y_2\wedge\overline{X_2}))\wedge\overline{X_1}\wedge Y_1)\wedge((\overline{X_1}\wedge Y_1\wedge X_2\wedge\overline{Y_2})\vee(X_1\wedge\overline{Y_1}\wedge\overline{X_2}\wedge Y_2))$% Потом, собственно, раскладываем это выражение: $% ((X_1\wedge\overline{Y_1}\wedge\overline{X_2}\wedge Y_2)\vee(Y_1\wedge\overline{X_1}\wedge Y_2\wedge\overline{X_2}))\wedge((\overline{X_1}\wedge Y_1\wedge X_2\wedge\overline{Y_2}))\vee\\\vee(X_1\wedge\overline{Y_1}\wedge\overline{X_2}\wedge Y_2))=X_1\wedge\overline{Y_1}\wedge\overline{X_2}\wedge Y_2$% Получаем ответ: в первой комнате находится принцесса, во второй - тигра. отвечен 19 Май '12 16:20 Limit-Sun Это и есть логическое решение. Мы уже обсуждали эту задачу здесь
(19 Май '12 22:01)
DocentI
Да, решение разумеется логическое, но для дисмата самое то :) Теперь, по поводу второго утверждения - для более чёткой формализации лучше считать, что под понятием "лучше выбрать первую комнату" не подразумевается, что принцесса за первой дверью лучше, той, что за второй (ну или тигр добрее). А именно, то, что во второй комнате всё-таки тигра, а в первой принцесса. Хотя в целом согласен, тут можно и поразмышлять Сейчас немного подкорректирую своё решение и доведу до конца, чтобы было понаглядней
(20 Май '12 1:49)
Limit-Sun
Вообще не понимаю, зачем автор снова поднимает тот же вопрос. В прошлый раз я ему все написала, через переменные, разве что к ДНФ не привела. И переменных было меньше (учитывались только тигры, так как отсутствие тигра = принцессе). И ответ я там получила (открыть первую комнату).
(20 Май '12 1:59)
DocentI
В целом согласен, без логики при решении задачи никак не обойтись и это решение во многом похоже на предложенное вами. Перегруз по переменным (четыре вместо двух) - излишний, правда мы можем посадить в одну комнату принцессу и тигру, однако это состояние быстро переходит в тигру без принцессы (как вы и заметили). Случай, когда две тигры или две принцессы в одной комнате по своему интересен, но в данной задаче до этого не доходит
(20 Май '12 2:14)
Limit-Sun
|
Что значит "не логически, а математически". А какие значения принимают ваши переменные - "ложь, истина" или "0, 1"? Второе, по сути - только кодировка первого. Все равно к ним придется применять некоторые логические действия. В принципе, можно ввести переменные $%P_i$% и $%T_i$%, задающие число принцесс (соотв. тигров) в i-ой комнате. Но в таких переменных трудно будет описать логическое следствие. отвечен 19 Май '12 21:59 DocentI |
А зачем Вам две переменные? Ведь по двое они не сидят? От принцессы мало что останется... Значит, придется добавлять условие $%X_i \ne Y_i$%
А как тогда предусмотреть все возможные варианты? ведь может быть ситуация, когда в обоих комнатах сидит по тигру или по принцессе
И что? В ваших обозначениях $%Y_i = не X_i$%, так что от переменных Y можно избавиться. Мне казалось, что мы уже решили эту проблему в предыдущем обсуждении.