Размещено на http://www.allbest.ru/

Московский Авиационный Институт

КУРСОВАЯ РАБОТА

по дисциплине «Интеллектуальные Информационные Системы»

Решение логической задачи на языке Prolog

Выполнил: студент группы 03-432

Виноградов А.А.

Москва 2012г

Введение

Пролог -- язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.

Основными понятиями в языке Пролог являются факты, правила логического вывода и запросы, позволяющие описывать базы знаний, процедуры логического вывода и принятия решений.

Факты в языке Пролог описываются логическими предикатами с конкретными значениями. Правила в Прологе записываются в форме правил логического вывода с логическими заключениями и списком логических условий.

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

Факты в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщёнными сведениями.

Начало истории языка относится к 1970-м годам. Будучи декларативным языком программирования, Пролог воспринимает в качестве программы некоторое описание задачи или баз знаний и сам производит логический вывод, а также поиск решения задач, пользуясь механизмом поиска с возвратом и унификацией.

Почему Prolog?

Пролог самый популярный язык логического программирования с многолетней историей развития, огромным сообществом и достаточным количеством качественной литературы, в отличие, к примеру от языка Lisp. Решение на Прологе задач, требующие логических выводов, наиболее лаконично, по сравнению с любым из структурированных языков. Чем решение короче и понятнее, тем легче разобраться в его нюансах, что немало важно при работе программистов в команде.

История головоломок

Некоторые головоломки известны с глубокой древности. Оригинальные логические задачи находят на стенах египетских пирамид, в древнегреческих манускриптах и в других исторических памятниках. Эпохой расцвета в средневековой истории головоломок можно считать конец IX века. Рост уровня образования и снижение религиозной нетерпимости к наукам привели к расширению круга любителей логических задач. В это время появилась и первая книга головоломок в Европе -- сборник ирландского просветителя Алкуина «Задачи для развития молодого ума».

Наиболее широкое распространение головоломки получили на рубеже XIX и XX веков. Благодаря деятельности американца Сэма Лойда и англичанина Генри Дьюдени головоломки проникли во многие периодические издания, стали популярны среди широких слоев населения. Лойд считается автором популярнейшей во всем мире головоломки «Пятнашки». Игра была настолько популярной, что некоторые работодатели вынуждены были издать приказ о запрете приносить её на работу.

Следующим толчком в развитии головоломок стало изобретение в 1974 году венгром Эрнё Рубиком знаменитого кубика. Кубик Рубика стал не только игрушкой, но и объектом исследований математиков и инженеров. С тех пор по всему миру регулярно проводятся соревнования по скоростной сборке кубика. Современная индустрия головоломок стремительно развивается. Постоянно на рынке появляются новые игры, конструкции и издания, призванные держать интеллект человека в тонусе, развивать логику, тренировать нестандартное мышление и повышать интеллектуальный уровень в целом.

С 1992 года проводятся чемпионаты мира по пазлспорту -- интеллектуальному виду состязаний, в котором участники соревнуются в скоростном решении головоломок на бумаге.

Задача

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

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

Подсудимого А судья спросил: Вы шпион? А ответил односложно ("да" или "нет"). Затем судья спросил подсудимого В: Правду ли сказал А? В дал односложный ответ ("да" или "нет"), после чего судья, указав на одного из подсудимых, заявил: Вы не шпион, освобождаетесь из-под стражи и можете быть свободны! Тот с радостью покинул зал заседаний. Затем судья спросил у одного из двух оставшихся на скамье подсудимых, шпион ли его сосед. Тот ответил односложно ("да" или "нет"), после чего судья с уверенностью установил, кто шпион.

Пока ты еще не можешь определить, кто шпион, сказал Король Алисе, необходимы дополнительные данные.

Слушай, что было дальше.

Мистер Энтони рассказал о процессе своему другу, по профессии адвокату. Разобравшись в деле, друг сказал: Я считаю, что данных недостаточно. Не мог бы ты сообщить мне по крайней мере, одинаковые ли ответы получил судья на все три вопроса? Мистер Энтони ответил. Смог ли адвокат решить после этого задачу, неизвестно.

При случае мистер Энтони задал ту же логическую задачу другому своему приятелю, по профессии также адвокату. Выслушав обстоятельства дела, этот приятель спросил: Получил ли судья по крайней мере два отрицательных ответа на свои вопросы? Мистер Энтони удовлетворил любознательность своего приятеля, но смог ли тот после этого решить задачу, неизвестно. Зато известно, продолжал Король, что эту логическую задачу либо решили, либо не решили оба приятеля мистера Энтони.

А теперь, сказал в заключение Король, я хочу спросить тебя, кто же был шпионом? Разве такую задачу можно решить? - вскричала в изумлении Алиса. Да, вполне, ответил Король. Торжественно заверяю тебя в этом.

prolog язык программирование логический

Листинг

DOMAINS

персонаж = персонаж(имя,тип)

ответ,имя,тип = symbol

список_ответов = ответ*

список_типов = тип*

список_персонажей = персонаж*

процесс = процесс(список_персонажей,ответ,ответ,имя,ответ)

вердикт = вердикт(персонаж,процесс)

список_процессов = процесс*

список_вердиктов = вердикт*

номер = integer

количество = integer

PREDICATES

nondeterm один_из(персонаж,список_персонажей)

nondeterm один_из(тип,список_типов)

nondeterm один_из(процесс,список_процессов)

nondeterm один_из(вердикт,список_вердиктов)

nondeterm количество_вхождений(ответ,список_ответов,количество)

nondeterm количество_элементов(список_вердиктов,количество)

nondeterm выбрать_уникальные(список_вердиктов,список_вердиктов);

nondeterm выбрать_уникальные(список_персонажей,список_персонажей);

nondeterm пересечение(список_вердиктов,список_вердиктов,список_вердиктов)

nondeterm один_из_ответов(ответ)

nondeterm один_из_участников(имя)

nondeterm сказал(персонаж,номер,процесс)

nondeterm проверка(персонаж,номер,процесс)

nondeterm шпион(имя,список_процессов,список_процессов)

nondeterm не_шпион(имя,список_процессов,список_процессов)

nondeterm исключить_невозможные_ответы(список_процессов,список_процессов,список_процессов)

nondeterm не_возможен(процесс,список_процессов)

nondeterm исключить_подозреваемого(имя,список_персонажей,список_персонажей)

nondeterm гипотеза(процесс)

nondeterm суд1(процесс)

nondeterm суд2(процесс)

nondeterm конец_суда(вердикт)

nondeterm подсказка1(вердикт,ответ)

nondeterm подсказка2(вердикт,ответ)

nondeterm решение1(список_вердиктов)

nondeterm решение2(список_вердиктов)

nondeterm решили_вместе(список_вердиктов,список_вердиктов,ответ)

nondeterm итог(персонаж)

nondeterm уникальный_итог(персонаж)

CLAUSES

один_из(Что,[Что|_]).

один_из(Что,[_|Хвост]):-один_из(Что,Хвост).

%Количество

количество_вхождений(_,[],0).

количество_вхождений(Что,[Что|Хвост],Число) :-

количество_вхождений(Что,Хвост,Число_в_хвосте),

Число = Число_в_хвосте+1.

количество_вхождений(Что,[Нечто|Хвост],Число) :-

not(Что = Нечто),

количество_вхождений(Что,Хвост,Число).

количество_элементов([],0).

количество_элементов([_|Хвост_Списка],Количество):-

количество_элементов(Хвост_Списка,Количество_в_хвосте),

Количество=Количество_в_хвосте+1.

%Поиск пересечения множеств

пересечение([],_,[]).

пересечение([Head1|Tail1],List2,[Head1|TailOut]) :-

один_из(Head1,List2),пересечение(Tail1,List2,TailOut).

пересечение([Head1|Tail1],List2,ListOut) :-

not(один_из(Head1,List2)),пересечение(Tail1,List2,ListOut).

один_из_ответов(да).

один_из_ответов(нет).

один_из_участников(а).

один_из_участников(б).

один_из_участников(в).

выбрать_уникальные([],[]).

выбрать_уникальные([Голова|Хвост],[Голова|ХвостУ]) :-

not(один_из(Голова,Хвост)),выбрать_уникальные (Хвост,ХвостУ).

выбрать_уникальные([Голова|Хвост],СписокУ) :-

один_из(Голова,Хвост),выбрать_уникальные(Хвост,СписокУ).

сказал(персонаж(а,Тип),1,процесс(_,Ответ,_,_,_)) :-

Ответ = "да", Тип = "шпион";

Ответ = "нет", not(Тип = "шпион").

сказал(персонаж(б,_),1,Процесс) :-

Процесс = процесс(Персонажи,_,Ответ,_,_),

Ответ = "да", А = персонаж(а,_), один_из(А,Персонажи), сказал (А,1,Процесс);

Процесс = процесс(Персонажи,_,Ответ,_,_),

Ответ = "нет", А = персонаж(а,_), один_из(А,Персонажи), not(сказал (А,1,Процесс)).

сказал(Персонаж,2,Процесс) :-

Процесс = процесс(Персонажи,_,_,_,Ответ),

Ответ="да", один_из(Сосед,Персонажи), not(Сосед = Персонаж), Сосед = персонаж(_,шпион);

Процесс = процесс(Персонажи,_,_,_,Ответ),

Ответ="нет", один_из(Сосед,Персонажи), not(Сосед = Персонаж), Сосед = персонаж(_,Тип), not(Тип = "шпион").

проверка(Персонаж,Номер,Процесс) :- Персонаж = персонаж(_,рыцарь),сказал(Персонаж,Номер,Процесс).

проверка(Персонаж,Номер,Процесс) :- Персонаж = персонаж(_,лжец),not(сказал(Персонаж,Номер,Процесс)).

проверка(Персонаж,_,_) :- Персонаж = персонаж(_,шпион).

исключить_подозреваемого(_,[],[]).

исключить_подозреваемого(Имя,[персонаж(Имя,_)|InT],OutList) :- исключить_подозреваемого(Имя,InT,OutList).

исключить_подозреваемого(Имя,[InH|InT],[InH|OutT]) :- not(InH = персонаж(Имя,_)),исключить_подозреваемого

(Имя,InT,OutT).

гипотеза(Процесс) :-

ПерсонажА = персонаж(а, ТипА),

один_из(ТипА,[рыцарь,лжец,шпион]),

ПерсонажБ = персонаж(б,ТипБ),

один_из(ТипБ,[рыцарь,лжец,шпион]), not(ТипБ = ТипА),

ПерсонажВ = персонаж(в,ТипВ),

один_из(ТипВ,[рыцарь,лжец,шпион]), not(ТипВ = ТипА),not(ТипВ = ТипБ),

один_из_ответов(Ответ1),один_из_ответов(Ответ2),

один_из_участников(ДалОтвет3),один_из_ответов(Ответ3),

Персонажи = [ПерсонажА,ПерсонажБ,ПерсонажВ],

Процесс = процесс(Персонажи,Ответ1,Ответ2,ДалОтвет3,Ответ3).

суд1(Процесс) :-

гипотеза(Процесс), Процесс = процесс(Персонажи,_,_,_,_),

% из процесса выбираются персонажи

ПерсонажА = персонаж(а,_),один_из(ПерсонажА,Персонажи),

% выбока персонажа

проверка(ПерсонажА,1,Процесс),

% проверка что сказал перонаж А

ПерсонажБ = персонаж(б,_),один_из(ПерсонажБ,Персонажи),

% выборка персонажа

проверка(ПерсонажБ,1,Процесс).

% проверка что сказал перонаж Б

суд2(Процесс2) :-

findall(Процесс1,суд1(Процесс1),Результаты),

%получаем в результате список всех гипотез удовлетворяющих первым двум высказываниям

один_из_участников(Предполагаем_Не_Шпион),

шпион(Предполагаем_Не_Шпион,Результаты,Невозможные_Результаты),

исключить_невозможные_ответы(Результаты,Невозможные_Результаты,Возможные_Результаты),

один_из(процесс(Персонажи1,Ответ1,Ответ2,ДалОтвет3,Ответ3),Возможные_Результаты),

исключить_подозреваемого(Предполагаем_Не_Шпион,Персонажи1,Персонажи2),

Процесс2 = процесс(Персонажи2,Ответ1,Ответ2,ДалОтвет3,Ответ3),

Подозреваемый = персонаж(ДалОтвет3,_),один_из(Подозреваемый,Персонажи2),

проверка(Подозреваемый,2,Процесс2).

конец_суда(вердикт(Шпион,Итоговый_Результат)) :-

findall(Процесс,суд2(Процесс),Результаты),

один_из_участников(Предполагаем_Шпион),

не_шпион(Предполагаем_Шпион,Результаты,Невозможные_Результаты),

исключить_невозможные_ответы(Результаты,Невозможные_Результаты,Возможные_Результаты),

один_из(Итоговый_Результат,Возможные_Результаты),

Итоговый_Результат = процесс(Персонажи,_,_,_,_),

Шпион = персонаж(_,шпион),один_из(Шпион,Персонажи).

подсказка1(Вердикт,Ответ4) :-

Ответ4 = "да", Вердикт = вердикт(_,процесс(_,Ответ1,Ответ2,_,Ответ3)),

конец_суда(Вердикт),

Ответ1 = Ответ2, Ответ1 = Ответ3;

Ответ4 = "нет", Вердикт = вердикт(_,процесс(_,Ответ1,Ответ2,_,_)),

конец_суда(Вердикт),

not(Ответ1 = Ответ2);

Ответ4 = "нет",Вердикт = вердикт(_,процесс(_,Ответ1,_,_,Ответ3)),

конец_суда(Вердикт),

not(Ответ1 = Ответ3);

Ответ4 = "нет",Вердикт = вердикт(_,процесс(_,_,Ответ2,_,Ответ3)),

конец_суда(Вердикт),

not(Ответ2 = Ответ3).

подсказка2(Вердикт,Ответ5) :-

Ответ5 = "да", Вердикт = вердикт(_,процесс(_,Ответ1,Ответ2,_,Ответ3)),

конец_суда(Вердикт),

количество_вхождений("нет",[Ответ1,Ответ2,Ответ3],ОтветовНет),

ОтветовНет >= 2;

Ответ5 = "нет", Вердикт = вердикт(_,процесс(_,Ответ1,Ответ2,_,Ответ3)),

конец_суда(Вердикт),

количество_вхождений("нет",[Ответ1,Ответ2,Ответ3],ОтветовНет),

ОтветовНет < 2.

%Формируем список гипотез в которых человек с именем Имя является шпионом

шпион(_,[],[]).

%Проверка если человек с именем Имя не является шпионом, то не добавляем в исходящий список

шпион(Имя,[процесс(Персонажи,_,_,_,_)|InT],Out):-not(один_из(персонаж(Имя,шпион),Персонажи)),шпион(Имя,InT,Out).

%Проверка если человек с именем Имя является шпионом, то добавляем его в список Out

шпион(Имя,[InH|InT],[InH|OutT]):-InH = процесс(Персонажи,_,_,_,_),один_из(персонаж(Имя,шпион),Персонажи),шпион

(Имя,InT,OutT).

%Формируем список гипотез в которых человек с именем Имя не является шпионом

не_шпион(_,[],[]).

%Проверка если человек с именем Имя является шпионом, то не добавляем в исходящий список

не_шпион(Имя,[процесс(Персонажи,_,_,_,_)|InT],Out):-один_из(персонаж(Имя,шпион),Персонажи),не_шпион(Имя,InT,Out).

%Проверка если человек с именем Имя не является шпионом, то добавляем его в список Out

не_шпион(Имя,[InH|InT],[InH|OutT]):-InH = процесс(Персонажи,_,_,_,_),not(один_из(персонаж

(Имя,шпион),Персонажи)),не_шпион(Имя,InT,OutT).

%Исключение невозможных гипотез

исключить_невозможные_ответы([],_,[]):-!.

исключить_невозможные_ответы([InH|InT],Ans,Out) :- не_возможен(InH,Ans),исключить_невозможные_ответы

(InT,Ans,Out).

исключить_невозможные_ответы([InH|InT],Ans,[InH|OutT]) :- not(не_возможен(InH,Ans)),исключить_невозможные_ответы

(InT,Ans,OutT).

не_возможен(процесс(_,Ответ11,Ответ21,Имя,Ответ31),[процесс(_,Ответ11,Ответ21,Имя,Ответ31)|_]).

не_возможен(Процесс,[_|AnsT]) :- не_возможен(Процесс,AnsT).

решение1(Список_Уникальных_Решений) :-

один_из_ответов(Ответ4),findall(Решение,подсказка1(Решение,Ответ4),Список_Решений),выбрать_уникальные

(Список_Решений,Список_Уникальных_Решений).

решение2(Список_Уникальных_Решений) :-

один_из_ответов(Ответ5),findall(Решение,подсказка2(Решение,Ответ5),Список_Решений),выбрать_уникальные

(Список_Решений,Список_Уникальных_Решений).

решили_вместе(Решения1,Решения2,"да") :- решение1(Решения1),количество_элементов(Решения1,1),

решение2(Решения2),количество_элементов(Решения2,1).

решили_вместе(Решения1,Решения2,"нет") :- решение1(Решения1),количество_элементов(Решения1,К1),not(К1=1),

решение2(Решения2),количество_элементов(Решения2,К2),not(К2=1).

итог(Шпион) :- один_из_ответов(Решили),решили_вместе(Решения1,Решения2,Решили),

пересечение(Решения1,Решения2,ИтоговыеРешения),

один_из(Решение,ИтоговыеРешения),Решение = вердикт(Шпион,_).

уникальный_итог(Шпион) :- findall(Персонаж, итог(Персонаж), Список_Решений), выбрать_уникальные

(Список_Решений,Список_Уникальных_Решений), один_из(Шпион,Список_Уникальных_Решений).

GOAL

уникальный_итог(Шпион).

Вывод

С помощью языка логического программирования Пролог возможно реализовать любые экспертные системы, решить любые головоломки и шарады. Он прекрасно подходит для программирования логических игр и многого другого, в том числе предпринимались попытки создания искусственного интеллекта на базе языка Пролог, потому что он прекрасно работает с базой знаний и наиболее схож с работой логики человека.

Размещено на Allbest.ru