|
Задача Энштейна и новый подход к решению задач этого типа в математической логике.
Существует довольно ограниченный набор методов решения задач математической логики. А именно:
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 раз.
|
