|
Известен ряд задач об узнике, который в силу определенных условий должен определить, в какой комнате находится тигр, а в какой принцесса. Но все решения такого рода задач сводились к объяснению "на пальцах". Подскажите, пожалуйста, как можно решать такого рода задачи с использованием характеристических уравнений? Знаю что оно в итоге сводится к ДНФ, откуда и следует нужный выбор. К примеру задача такая:
======================================== задан 7 Май '12 1:27 
carapuz |
|
А что такое характеристическое уравнение в мат. логике? Можно просто составить формализацию условий. Например, так. Пусть $%T_i$%= "В комнате номер i сидит тигр". Тогда первая надпись переписывается в виде $%T_1\ne T_2$%, вторая - видимо, так: $%\overline T_1T_2 $%. Хотя тут возможны варианты, например, $%\overline T_1$% или $%T_2 $%. Если считать, что король не соврал, получаем такую конструкцию: $$\big(\overline T_1 =(T_1\ne T_2)\big)\cdot \big(T_2=\overline T_1T_2\big),$$
которую можно дальше преобразовать к ДНФ. Конкретно это выражение, вроде, сводится к виду
$%\overline T_1T_2\vee T_1\overline T_2 $%. Т.е. $%T_1\ne T_2$%. Дополнение. Предыдущее выражение не верно. Аккуратное преобразование дает решение этой задачи: Первая большая скобка после преобразования принимает вид $$\Big(\overline T_1 =(T_1\ne T_2)\Big)=\Big(\overline T_1\cdot(T_1\ne T_2)\vee T_1\cdot\overline{(T_1\ne T_2)} \Big)=$$ $$=\Big(\overline T_1\cdot(T_1\cdot\overline T_2\vee \overline T_1\cdot T_2 )\vee T_1\cdot(T_1\cdot T_2\vee\overline T_1\cdot\overline T_2) \Big)=\big(\overline T_1\cdot T_2\vee T_1\cdot T_2\big)=T_2,$$ т.е. во второй комнате сидит тигр. Второе выражение преобразуется к виду $$T_2\cdot \overline T_1T_2\vee \overline T_2\cdot(T_1\vee\overline T_2) =\overline T_1T_2\vee \overline T_2\cdot T_1\vee\overline T_2=\overline T_1T_2\vee \overline T_2,$$ Произведение двух скобок равно $%\overline T_1T_2$%, т.е. открывать надо первую комнату. отвечен 8 Май '12 2:34 
DocentI Собственно это оно самое и есть. Быть может я неправильно только сформулировал это понятие. Спасибо большое, Вы мне очень помогли.
(8 Май '12 16:46)
carapuz
|
И где же @Галактион? Задача прямо для него!
Хотел написать то же самое. Вы меня опередили!
Совпадение! А ведь задача задана давно... Кстати, у Вас время не Московское? У нас - да. Так что спать давно пора...