2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача Энштейна и новый подход к решению задач этого типа в
Сообщение04.10.2009, 15:00 


04/10/09
2
Задача Энштейна и новый подход к решению задач этого типа в математической логике.

Существует довольно ограниченный набор методов решения задач математической логики. А именно:
1) Метод рассуждений
2) Табличный метод
a. Бинарный (значения в таблицы могут принимать только «Ложь» и «Истина»
b. Свободный (в таблице могут быть любые значения)
3) Метод граф
4) Метод составления логической формулы
Не смотря на свою условную универсальность, каждый метод наиболее подходит для решения задач только определенного типа. За исключением метода рассуждений и свободного табличного метода, которые есть суть одно и тоже. И все эти методы довольно затруднительно применить для решения задач сходных по типу и уровню сложности со знаменитой логической задачей Энштейна. Даже метод рассуждений применить довольно затруднительно за счет отсутствия четкой алгоритмизации требуемых для решения действий. Одной из наиболее затруднительных проблем для алгоритмизации, является наличие в условии задач позиционных условий, которые очень сложно формализовать в виде общей логической формулы Предлагаемый метод существенно упрощает процесс решения задач подобного типа и подобной сложности и позволяет алгоритмизировать действия по решению задач.

Суть метода заключается в записи условий задачи в виде набора символов: a1a2a3…an , где n – число наборов признаков по условиям задачи, а а1,a2,a3…an - признаки, стоящие соответственно на i месте (i=1…n). В случае если признак не определен используется символ X. В случае позиционной привязки условий, используется значение (Х+k), где k – смещение относительно Х. Причем эти наборы символов могут принимать значение «Истина» или «Ложь» и соответственно с ними возможны все логические операции.

Рассмотрим простой пример.

Задача: Есть три девушки: Айрин (А), Джоана (Д), Линда (Л). Они приобрели известность в пении (П), балете(Б) и кино(К), и живут в Париже(П), Риме(Р) и Чикаго (Ч).

Введем соответственно набор символов x1x2x3 , х1 – имя девушки (А,Д,Л), х2 –город (П,Р,Ч) , х3 – занятие (П,Б,К).

Условия:

1) Джоана живет не в Париже. Это можно записать в виде формулы: ДРх или ДЧх =1 (Истина)
2) Линда живет не в Риме. ЛПх или ЛЧх = 1
3) Парижанка не снимается в кино. хПБ или хПП = 1
4) Римлянка – певица. хРП = 1
5) Линда равнодушна к балету. ЛхП или ЛхК =1

Вопрос: Где живет Айрин и чем занимается?

Решение:
1. Используя 2 и 5 условие. (ЛПх или ЛЧх) и (ЛхП или ЛхК) = 1, получаем: ЛПП или ЛПК или ЛЧП или ЛЧК =1
2. Используем 4 условие хРП=1, следовательно ЛПП и ЛЧП = 0, тогда ЛПК или ЛЧК = 1
3. Используем условие 3 условие хПБ или хПП = 1, следовательно ЛПК = 0, тогда ЛЧК=1.
4. Используем 1 условие и вывод из 3 шага решения: ДРх или ДЧх =1 и ЛЧК=1, тогда ДЧх=0, а ДРх=1
5. Объеденим: хРП=1, ДРх=1 тогда ДРП = 1
6. Из ДРП=1 и ЛЧК=1 однозначно следует АПБ=1

Ответ: Айрин, Париж, Балет.

Рассмотрим теперь решение задачи Энштейна предложенным способом.

Условия:
Исходные данные:
1. Есть 5 домов, каждый разного цвета.
2. В каждом доме живёт один человек, отличающийся от соседнего по национальности:
немец, англичанин, швед, датчанин и норвежец.
3. Каждый пьёт только один определённый напиток, курит определённую марку сигарет
и держит определённое животное.
4. Никто из пяти человек не пьёт одинаковые с другими напитки, не курит одинаковые сигареты
и не держит одинаковое животное.

Вопрос: Кому принадлежит рыба?

Введем набор символов: х1х2х3х4х5х6, где х1 – номера домов по порядку (1,2,3,4,5), х2 – национальности (О, Д, А , Ш , Н), х3 – цвет дома (З,Ж,Г,К,Б), х4 – сигареты (П, Р, В, М, Д), х5 – напиток (П,В,К,Ч,М), х6 – домашнее животное (Л,С,К,П,Р). 1<=х1<=5, если значение х1 в паре наборов символов не определено, но фиксировано в обоих наборах, то х1=Х

Запишем подсказки и условия: в виде наборов символов
1. Англичанин живёт в красном доме. хАКххх=1
2. Швед держит собаку. хШхххС=1
3. Датчанин пьёт чай. хДххЧх=1
4. Зелёный дом стоит слева от белого, рядом. ХхЗххх и (Х+1)хБххх=1
5. Жилец зелёного дома пьёт кофе. ххЗхКх=1
6. Человек, который курит "Pall Mall", держит птицу. хххПхП=1
7. Жилец из среднего дома пьёт молоко. 3хххМх=1
8.Жилец из желтого дома курит "Dunhill". ххЖДхх=1
9. Норвежец (О) живёт в первом доме. 1Охххх=1
10. Курильщик "Marlboro" живет около того, кто держит кошку. (ХххМхх и (Х+1)ххххК) или (ХххМхх и (Х-1)ххххК) = 1
11. Человек, который содержит лошадь, живёт около того, (ХххххЛ и (Х+1)ххДхх) или
кто курит "Dunhill". (ХххххЛ и (Х-1)ххДхх) = 1
12. Курильщик сигарет "Winfield" пьёт пиво. хххВПх=1
13. Норвежец живёт около голубого дома. (ХОхххх и (Х+1)хГххх) или (ХОхххх и (Х-1)хГххх)=1
14. Немец (Н) курит "Rothmans" хНхРхх=1
15. Курильщик "Marlboro" живёт по соседству с человеком, (ХххМхх и (Х+1)хххВх) или
который пьёт воду. (ХххМхх и (Х-1)хххВх) =1

Решение:
1) Рассмотри 9 и 13 условие. 1Охххх=1 и (ХОхххх и (Х+1)хГххх) или (ХОхххх и (Х-1)хГххх)=1 т.к. (Х-1=0) – ложь по условиям задачи, то (1ХОхххх и (Х+1)хГххх)=1, получаем 1Охххх=1 и 2хГххх=1
2) 4 и 5 условие: ХхЗхКх и (Х+1)хБххх=1
3) Объединим 1) решение и 7 условие. В виде таблицы:
1 O х х х х
2 х Г х х х
3 х х х M х
х х х х х х
х х х х х х
Применим 2) шаг решения ХхЗхКх и (Х+1)хБххх=1. Х=1 – ложь, Х=2 – ложь, Х=3 – ложь, Х = 5 – ложь, Х=4 – истина
Объединим в таблицу:
1 O х х х х
2 х Г х х х
3 х х х M х
4 х З х К х
5 х Б х х х
4) Применим 1 условие хАКххх=1, 1Oхххх=1 следовательно 1АКххх=0, следовательно 3АКххх=1. по остаточному принципу 1ОЖххх=1, тогда применив 8 условие , получаем 1ОЖДхх=1. В Таблице:
1 O Ж Д х х
2 х Г х х х
3 А К х M х
4 х З х К х
5 х Б х х х
5) Применим 3 условие: хДххЧх=1. Т.к. 1ОЖДхх=1 то 1ДххЧх=0, тогда (2ДГхЧх или 5ДБхЧх) =1
6) Применим 12 условие хххВПх=1. т.к. . 1ОЖДхх=1 то 1ххВПх=0, следовательно (2хГВПх или 5хБВПх) =1
7) 5) и 6) шаг решения получаем 1ОЖДВх=1
8) Применяем 15 условие. Перепишем его (ХхххВх и (Х+1)ххМхх) или (ХхххВх и (Х-1)ххМхх)=1. т.к. 1ОЖДВх=1 то (Х-1=0) получаем ХхххВх и (Х+1)ххМхх=1. Следовательно 2хГМхх=1
1 O Ж Д В х
2 х Г М х х
3 А К х M х
4 х З х К х
5 х Б х х х
9) Применим 6) и 8) шаги решения. Получим 5хБВПх=1, тогда применим 5) шаг решения, получаем 2ДГхЧх=1.
1 O Ж Д В х
2 Д Г М Ч х
3 А К х M х
4 х З х К х
5 х Б В П х
10) Применим 14 условие хНхРхх=1. т.к. 5хБВПх=1 получаем 4НЗРКх. Тогда 2 условие: хШхххС=1, получаем 5ШБВПС=1.
1 O Ж Д В х
2 Д Г М Ч х
3 А К х M х
4 Н З Р К х
5 Ш Б В П С
11) Применим 6 условие хххПхП=1.
1 O Ж Д В х
2 Д Г М Ч х
3 А К П M П
4 Н З Р К х
5 Ш Б В П С
12) Применим 10 условие (ХххМхх и (Х+1)ххххК) или (ХххМхх и (Х-1)ххххК) = 1. т.к. Х=2, а 3АКПМП=1 тогда 1ОЖДВК=1
13) Применим 11 условие: (ХххххЛ и (Х+1)ххДхх) или (ХххххЛ и (Х-1)ххДхх) = 1 перепишем ( ХххДхх и (Х+1)ххххЛ) или (ХххДхх и (Х-1)ххххЛ) =1. т.к.х=1, то 2ДГМЧЛ=1
1 O Ж Д В К
2 Д Г М Ч Л
3 А К П M П
4 Н З Р К х
5 Ш Б В П С
14) Получаем 4НЗРКР (!!!) , т.е. Рыба у Немца. Что и требовалось найти.


Заключительные замечания.
1) Очевидно, что все наборы символов в таблицах связаны логическим «И» и представляют собой истинные логические утверждения.
2) На практике применять таблицы нет необходимости, достаточно писать наборы символов в столбик.
3) В ситуации, когда очевидные условия заканчиваются (как на 4 шаге решения). Необходимо выбрать признак по которому известно максимальное число позиций. В нашем случае это признаки: х2 – национальности и х4 – напитки. И одновременно наименьшее число условий (так как это повышает определенность). В нашем случае по напиткам оставалось 3 неиспользованных условия, а по национальностям – 4 неиспользованных условия. (гипотеза !!! объясняемая требованием лаконичности. Т.е. при формулировке задачи исходят из необходимости минимизации числа условий. Соответственно, чем меньше остается неотработанных условий по заданному признаку, тем выше определенность и меньше вариантов)
4) Каждое условие и каждый шаг решения используется в дальнейшем только 1 раз.

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение04.10.2009, 16:16 
Заслуженный участник
Аватара пользователя


13/08/08
14495
У меня вопрос. Вот эта задача она действительно была Эйнштейном сформулирована? Конечно, у многих великих учёных были невинные развлечения. Кто пасьянсы раскладывал, кто чемоданы делал. Может быть он эту задачу предлагал школьникам, ну типа задач Арнольда? Просто я её уже много раз встречал в инете, и обычно её преподносят как критерий гениальности. Что из тысячи человек только один может решить её меньше, чем за час. У Кэррола было много таких "силлогизмов".

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение04.10.2009, 16:39 
Модератор
Аватара пользователя


11/01/06
5710
gris в сообщении #248965 писал(а):
У меня вопрос. Вот эта задача она действительно была Эйнштейном сформулирована?

Точно неизвестно. В википедии пишут:
Цитата:
Считается, что эта головоломка была создана Альбертом Эйнштейном в годы его детства. Также бытует мнение, что она использовалась Эйнштейном для проверки кандидатов в ассистенты на способность к логическому мышлению.

Некоторые приписывают Эйнштейну рассуждение, в котором тот утверждает, что лишь два процента населения земного шара способны оперировать в уме закономерностями, связанными сразу с пятью признаками. Как частное следствие этого, приведённая головоломка может быть решена без использования бумаги лишь теми, кто принадлежит к этим двум процентам. Тем не менее, не существует никаких документальных свидетельств того, что Эйнштейн когда-либо утверждал подобное.

 Профиль  
                  
 
 Re: Задача Эйнштейна и новый подход к решению задач этого типа в
Сообщение05.10.2009, 13:18 


04/10/09
2
Переклинило меня... Эйнштейна "Энштейном" назвал (((( Поспешишь - людей насмешишь...

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение05.10.2009, 15:01 


17/10/08

1313
Этому "новому методу" лет 30, если не больше. См. например Лорьер "Системы искусственного интеллекта", гл. что-то вроде "система ALICE". См. также в интернете "Программирование в ограничениях" или Constraint Programming.

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение10.10.2009, 21:46 
Аватара пользователя


12/03/08
191
Москва
А какие есть методы решения судоку 9х9?
Я знаю такие (довольно очевидные):
1. по цифрам: берется цифра, закрашиваются занятые ею строки, столбцы и квадраты, откуда находится (если возможно) новая позиция данной цифры
2. по комплекту: берется квадрат 3х3, либо строка, либо столбец, и изучаются на предмет недостающих цифр. этот метод является подсказской к первому
3. по клетке: берется клетка (с большим числом соседей по строкам/столбцам и квадратам) и изучается вопрос о том, какие цифры могут на ней стоять. если возможна лишь одна цифра, то именно она и стоит там.
4. альтернативный: ищутся пары цифр на паре клеток, так что только эти цифры на этих клетках могут стоять, рассматриваются оба варианта до тех пор, пока не будет найдено противоречие, либо не будет решена задача.
Есть еще ситуативные методы, подсказываемые логикой, но нет универсального метода решения судоку.

Сори, если это будет здесь оффтоп.

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение10.10.2009, 22:37 
Заслуженный участник


31/12/05
1525
rishelie в сообщении #250766 писал(а):
А какие есть методы решения судоку 9х9?
http://www.scanraid.com/sudoku.htm
Там справа можно нажать на каждую эвристику и получить описание.

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение11.10.2009, 19:01 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Ekim в сообщении #248951 писал(а):
1) Метод рассуждений


Улыбнуло :)

Этот метод не только первый, но и единственный. И не только в математической логике, но и в математике вообще :D

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение12.10.2009, 10:31 
Заслуженный участник


08/04/08
8562
rishelie писал(а):
А какие есть методы решения судоку 9х9?

Тут несколько можно найти несколько ссылок и хороших задач:
topic5975.html

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение24.02.2010, 21:23 
Аватара пользователя


20/01/10
766
Нижний Новгород
Эта игрушка имеет некоторое отношение к теме.

 Профиль  
                  
 
 Re: Задача Энштейна и новый подход к решению задач этого типа в
Сообщение18.02.2012, 05:50 


28/10/11
12
Есть еще один метод – посредством самоорганизующихся нейросетей.

Он очень прост– на двумерной плоскости задаем условия.
Просто рисуем точки – причем очень приближенно.
Для разнообразия «дома» можно расположить по кругу.

Изображение

В хорошем качестве.
http://softvito.narod2.ru/E.JPG


Тут представлены все условия. Как видите они набросаны крайне небрежно(синие линии и красные точки – топология сети ).
Попробуйте решить ее сами. Не получится.
Тем не менее сеть сама производит анализ и разбивает на классы.

А вот и результат в привычном виде.

Изображение

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

Плюсы – очень простая формулировка правил да и решение. Огромные возможности "анализа на чувствительность".
Кстати – ее действительно никто еще не решил(введение дополнительных ограничений искажают суть).А задачка очень и очень нетривиальная.

Р.С. Если интересно- спрашивайте, расскажу подробнее.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group