Миры Р. Смаллиана: обобщения задач с рыцарями и лжецами

Федеральное агентство по образованию

 

 

Томский Государственный Университет  Систем Управления и Радиоэлектроники

(ТУСУР)

 

Кафедра компьютерных систем в управлении и проектировании

(КСУП)

 

 

Миры Р. Смаллиана: обобщения задач  с рыцарями и лжецами

Пояснительная записка к курсовой работе по дисциплине «Интеллектуальные подсистемы САПР».

 

 

 

 

 

Выполнил:

Студент гр. 584–1

_________Павлова М.С.

“___”________2008 г.

 

Принял:

доцент каф. КСУП

_________Зюзьков В.М.

“___”_______ 2008 г.

 

 

 

 

2008

Реферат

 

     Курсовая работа содержит: страниц – 27, источников – 3, приложение – 1.

     Цель данной работы – создание программы в среде программирования Prolog, решающую логические задачи, представленные в виде высказываний рыцарей и лжецов. Пояснительная записка выполнена в текстовом редакторе Microsoft Office 2007.

 

Федеральное агентство по образованию

 

Томский государственный  университет систем управления и  радиоэлектроники

(ТУСУР)

 

Кафедра компьютерных систем в управлении и проектировании

(КСУП)

 

Утверждаю

Зав. каф. КСУП

д.т.н., проф.

__________Шурыгин Ю.А.

«__»__________ 2008 г.

ЗАДАНИЕ

по курсовому  проектированию по дисциплине

"Интеллектуальные подсистемы  САПР"

студенту Павловой Мелитине Сергеевне      

группа 584-1 факультет ВС

1. Тема проекта: «Миры Р. Смаллиана: обобщения задач с рыцарями и лжецами»

2. Срок сдачи студентом законченной работы «30» ноября 2008 г.

3. Дата выдачи задания «10» сентября 2008 г.

    РУКОВОДИТЕЛЬ: доцент каф.  КСУП

    _____________ Зюзьков Валентин  Михайлович

     Задание приняла к исполнению:

     ______________Павлова М.С.

 

Содержание

 

                                              

     Введение

     Автореферентными рассуждениями называются те рассуждения, в которых используются понятия, самоотносимые или самоприменимые к самим себе. Некоторые из таких высказываний приводят к так называемым семантическим парадоксам (например, «парадокс лжеца»), другие вполне безобидны.

     В книге Р. Смаллиана [1] приводится много логических задач, в которых персонажи высказывают некоторые автореферентные утверждения, прямо или косвенно говорящие об истинности этих утверждений. Персонажи этих задач населяют некоторый остров и относятся к одной из двух категорий: «рыцари»,  которые говорят только правду, и «лжецы», изрекающие только ложь. Предполагается, что каждый обитатель острова либо рыцарь, либо лжец, либо нормальный человек. Начнем с классической задачи этого сорта.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

    2. Постановка задачи

    Реализовать программу  на языке Пролог, реализующую  предложенные обобщения (остров  населен рыцарями, лжецами и нормальными  людьми и возможны метавысказывания) и решающую задачи 1-10 из указанной статьи [2].

 

 

     3. Условия задач

     Задача формулируется следующим образом. Существует остров, населённы рыцарями и лжецами. Любое высказывание рыцаря – истина и наоборот, любое высказывание лжеца – ложь. Необходимо по высказываниям двух персонажей определить к какой категории относятся: рыцарь или лжец.

   Задача 1.Перед нами три жителя острова A, B и C. Двое из них (A и B) высказывают следующие утверждения:

   A: Мы все лжецы.

   B: Один из нас рыцарь.

Кто из трех островитян A, B и C рыцарь и кто лжец?

   Задача 2. Персонаж A утверждает: «Я говорю правду». Кто он рыцарь или лжец?

   Задача 3. Персонаж A утверждает: «Мы оба вместе с B лжецы». Кто есть A и кто есть B?

   Задача 4. Предположим, что A и B высказывают следующие утверждения:

   A: Мы все (A,B и C) лжецы.

   B: Только один из нас лжец.

Можно ли определить, кто  такие  A и C? Можно ли определить, кто такой B?

   Задача 5. Из двух жителей острова A и B житель B утверждает: «Только один из нас двоих рыцарь». Кто эти жители?

   Задача 6. Имеются три высказывания:

   q1: «q2 ложно»;

   q2: «q3 ложно»;

   q3: «q1 ложно».

Какие у них  значения истинности?

   Задача 7. Имеются четыре высказывания:

   q1: «q2 ложно»;

   q2: «q3 ложно»;

   q3: «q4 ложно»;

   q4: «q1 истинно».

Какие у них значения истинности?

   Задача 8. Имеется два жителя острова, на котором живут только рыцари и лжецы. Они произносят следующие реплики:

   A: «Хотя бы один из нас говорит правду»;

   B: «Хотя бы один из нас лжец».

Кто из них рыцарь, а кто лжец?

   Задача 9. Двое людей A и B, о которых известно, что каждый из них либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения:

   A: B – рыцарь.

   B: A – лжец.

Есть ли среди  них рыцари?

Включение в  постановку задачи высказывания о высказывании (назовем его метавысказыванием) несколько усложняет положение дел.

   Задача 10. Встретились два человека A и B, которые заявляют следующее:

   A: B утверждает, что он рыцарь.

   B: A утверждает, что он лжец.

К какой категории  следует отнести каждый персонаж?

 

 

 

 

 

 

   3. Анализ задач и их реализация

   Задача 1. Перед нами три жителя острова A, B и C. Двое из них (A и B) высказывают следующие утверждения:

   A: Мы все лжецы.

   B: Один из нас рыцарь.

Кто из трех островитян A, B и C рыцарь и кто лжец?

   Приведем решение этой задачи [5, стр. 34-35]. Прежде всего, заметим, что A должен быть лжецом. Действительно, если бы A был рыцарем, то из его высказывания следовало бы, что все трое лжецы. Но тогда A (по предположению, рыцарь) оказался бы лжецом, что невозможно. Следовательно, A – лжец. Но тогда его высказывание ложно и по крайней мере один из трех островитян A, B и C – рыцарь.

   Предположим теперь, что B – лжец. Тогда A и B – оба лжецы, поэтому C должен быть рыцарем (так как, по крайней мере, один из трех островитян рыцарь). Это означает, что ровно один из трех островитян рыцарь, и, следовательно, высказывание B истинно, но это невозможно, так как любое высказывание лжеца не истинно. Отсюда мы заключаем, что B должен быть рыцарем.

   Итак, мы установили, что A – лжец, а B – рыцарь. Так как B – рыцарь, то его высказывание истинно, поэтому ровно один из трех островитян – рыцарь. Им должен быть B, следовательно, C должен быть лжецом. Итак, A – лжец, B – рыцарь, C – лжец.

   Как можно формализовать решение задачи?

   Проведем онтологический анализ задач данного класса. По-видимому, для решения таких задач нам придется иметь дело со следующими объектами:

• Персонажи, произносящие утверждения. Произносимое утверждение характеризует либо самого персонажа, либо прочих персонажей, либо и тех и других. Персонаж может быть либо рыцарем, либо лжецом.
• Утверждение, содержащее в реплике. Это утверждение может быть лживым или истинным.
• Существует среда (мир), которая характеризуется совокупностью наших предположений. Например, существует мир, в котором мы предположили, что B  – рыцарь и, следовательно, высказанное им утверждение (или утверждения) истинно. Это предположение влечет за собой разные следствия, которые образуют контекст данного гипотетического мира.

    Таким образом, рассматриваемая проблема относится к типу таких, решение которых находится в результате анализа выводов, следующих из определенных предположений, и поиска в них противоречий (или отсутствия таковых). Мы предполагаем, что определенный персонаж говорит правду, а затем смотрим, можно ли в этом случае так распределить «роли» остальных персонажей, что не будут нарушены условия, сформулированные в утверждениях. Если в задаче участвуют n персонажей, то всего существуют 2ⁿ различных гипотетических миров, в котором каждому персонажу выбрана конкретная роль рыцаря или лжеца. Вопрос состоит в том, существует ли мир и кем он должен быть «заселен», чтобы множество утверждений (с учетом их истинности) было непротиворечивым? В терминах математической логики искомый мир должен быть моделью множества высказанных утверждений.

  

   Задачи с рыцарями и лжецами

   Рассмотрим как формулировку и решение таких задач можно описать на языке Пролог. Будем использовать SWI-Prolog [3], поддерживающий эдинбургский стандарт языка.

   Выберем сначала структуры данных. Персонажи задачи будем обозначать атомами a, b, c и т. д. Атомарные утверждения любого персонажа можно представить в виде термов рыцарь(<кто-то>) или лжец(<кто-то>), где <кто-то> – имя персонажа, о котором сообщается, что он рыцарь или лжец, соответственно. Более сложные реплики можно представить в виде комбинации атомарных высказываний, соединенных логическими связками: & – конъюнкция, v – дизъюнкция, ~ – отрицание. Тот факт, что персонаж X высказал утверждение Y, будем представлять в виде сложного терма утверждение(X, Y). Множество утверждений, высказанное персонажами задачи, представим списком термов вида утверждение(X, Y). Это множество, по сути дела, является единственным входным данным задачи, поскольку имена персонажей задачи можно извлечь из этого списка. Мир будем представлять в виде списка термов <персонаж>–<категория>, где <категория> имеет одно из атомарных значений рыцарь или лжец, классифицирующего персонажа. Алгоритм решения задачи сводится к генерации возможных миров и проверки, являются ли они моделями.

Приведем полный текст программы  с комментариями.

/* Программа  «Рыцари и лжецы»

Персонажами задач  могут быть только рыцари и лжецы */

:- op( 100, fy, ~).  % определяем операторы для логических связок

:- op( 110, xfy, &).

:- op( 120, xfy, v).

/* Главный предикат: S – имя или номер задачи, переменная I в результате

   решения  получает значение конкретного  мира в виде списка пар, 

   например, I = [a-лжец, b-рыцарь] */

решение(S,I):-

      задача(S,L),      % L – условие задачи в виде списка утверждений

      персонажи(L,Xs),  % Xs – список персонажей, определяется из L

      мир(Xs,I),        % I – один из возможных миров для персонажей Xs

      модель(L,I).      % является  ли этот мир моделью для L?

% определение  персонажей логической задачи

% персонажи(+Список  утверждений, -Персонажи)

персонажи([],[]).

персонажи([утверждение(X,P)|Vs],A):-

      переменные(P,Xs),

      персонажи(Vs,Y),

      append([X|Xs],Y,Z),

      list_to_set(Z,A).

переменные(рыцарь(X),[X]).

переменные(лжец(X),[X]).

переменные(~P,L):-

      переменные(P,L).

переменные(P1 & P2,L):-

      переменные(P1,L1),

      переменные(P2,L2),

      append(L1,L2,L).

переменные(P1 v P2,L):-

      переменные(P1,L1),

      переменные(P2,L2),

      append(L1,L2,L).

% мир  определяет возможные категории  персонажей

% мир(+Персонажи, -Мир)

мир([],[]).

мир([X|Xs],[X-Y|R]):-

      категория(Y),

      мир(Xs,R).

% возможные  категории персонажей: только рыцари  и лжецы

категория(рыцарь).

категория(лжец).

% является ли возможный мир моделью для утверждений?

% модель(+Утверждения, +Мир)

модель([],_).

модель([V|Vs],I):-

      модель(V,I),

      модель(Vs,I).

модель(утверждение(X,F),I):-

      тип_персонажа(X,I,T),

      истинность(T,M),

      оценка_формулы(F,I,M).

% каждой категории  соответствует свое значение  истинности

истинность(рыцарь, истина).

истинность(лжец, ложь).

% определение  типа персонажа в данном мире

% тип_персонажа(+Персонаж, +Мир, -Тип_персонажа)

тип_персонажа(X, [X-Y|_],Y).

тип_персонажа(A, [B-_|L],Y):-

      A \= B,

      тип_персонажа(A,L,Y).

% оценка  формулы при заданной интерпретации

% оценка_формулы(+Формула, +Мир, -Значение)

оценка_формулы(рыцарь(X),I,V):-

      тип_персонажа(X,I,Y),

      (Y=рыцарь, V=истина;

       Y=лжец, V=ложь).

оценка_формулы(лжец(X),I,V):-

      тип_персонажа(X,I,Y),

      (Y=рыцарь, V=ложь;

       Y=лжец, V=истина).

оценка_формулы(~F,I,V):-

      оценка_формулы(F,I,V1),

      нет(V1,V).

оценка_формулы(F1 v F2,I,V):-

      оценка_формулы(F1,I,V1),

      оценка_формулы(F2,I,V2),

      или(V1,V2,V).

оценка_формулы(F1 & F2,I,V):-

      оценка_формулы(F1,I,V1),

      оценка_формулы(F2,I,V2),

      и(V1,V2,V).

% булевские  операции со значениями "истина" и "ложь"

      нет(истина,ложь).

      нет(ложь,истина).

      или(истина,ложь,истина).

      или(истина,истина,истина).

      или(ложь,ложь,ложь).

      или(ложь,истина,истина).

      и(истина,ложь,ложь).

      и(истина,истина,истина).

      и(ложь,ложь,ложь).

      и(ложь,истина,ложь).

   Рассмотрим теперь некоторые задачи с рыцарями и лжецами и их решения с помощью программы. Начнем с простых задач.

   Задача 2. Персонаж A утверждает: «Я говорю правду». Кто он рыцарь или лжец? Эта задача описывается в виде факта:

задача(2,[утверждение(a,рыцарь(a))]).

   Очевидно, из условия задачи нельзя однозначно определить категорию персонажа:

?- решение(2,X).

X = [a-рыцарь] ;

X = [a-лжец] ;

No

   Задача 3. Персонаж A утверждает: «Мы оба вместе с B лжецы». Кто есть A и кто есть B? Эта задача описывается в виде факта:

задача(3,[утверждение(a,лжец(a) & лжец(b))]).

   В данном случае решение однозначно: A  – лжец и B  – рыцарь.

?- решение(3,X).

X = [a-лжец, b-рыцарь] ;

No

   Решим теперь задачу 1. Запись задачи немного сложнее:

задача(1, [утверждение(a,лжец(a) & лжец(b) & лжец(c)),

            утверждение(b,рыцарь(a) & лжец(b) & лжец(c) v

                          лжец(a) & рыцарь(b) & лжец(c) v