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

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

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

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

No

Мы получили правильное решение. Рассмотрим еще несколько задач.

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

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

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

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

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

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

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

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

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

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

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

No

   Мы определяем, что A – лжец, C – рыцарь, но определить кто такой B мы не в состоянии.

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

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

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

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

X = [b-лжец, a-лжец] ;

No

   Хотя произносит реплику B, но о нем ничего нельзя узнать, зато A  автоматически становится     лжецом.

   Парадоксы

   Все рассмотренные задачи подобраны так, чтобы решение всегда существовало, но в общем случае этого может не быть. Когда решения нет – возникает парадокс.

   Наиболее известный парадокс – это парадокс лжеца. Классической формой парадокса лжеца является высказывание  Евбулида (4 век до н. э.): «Я лгу». Рассмотрим вопрос об истинности высказывания «я лгу». Если сказав «я лгу», я сказал истину, то значит я при этом солгал (т. е. сказал неправду), что противоречиво, следовательно, произнося это высказывание, я сказал неправду, т. е. солгал. Итак, доказано, что произнося это высказывание, я солгал, а так как именно это я и утверждал, произнося это высказывание, то я, тем самым, сказал при этом истину, т. е. доказано и то, что я  (в том же случае) сказал истину. В этом противоречии и состоит парадокс.

   Чтобы отмести выражение, что высказывание Евбулида «слишком неясно» (не ясно, относится ли оно к себе или к другим высказываниям Евбулида, сделанным в течение его жизни), французский логик 13 в. Иоанн Буридан предложил следующую форму парадокса: обозначим через P высказывание, содержащее в рамке:

 

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

задача(парадокс_лжеца,[утверждение(a,лжец(a))]).

?- решение(парадокс_лжеца,X).

No

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

а) истинные высказывания,

б) ложные высказывания,

в) высказывания, не имеющие значения истинности.

Сделав это, возьмем теперь высказывание P:

 

   Если P истинно, то P не ложно и P имеет значение истинности. Это значит, что высказывание, содержащее в рамке, является ложным …, но это и есть P! Аналогично, если P ложно, то P истинно. Наконец, если P не имеет значения истинности, то P  истинно! Наша классификация высказываний опять не является исчерпывающей. (Последний парадокс принято называть «Усиленным лжецом».)

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

   q1: «q2 ложно»;

   q2: «q3 ложно»;

   q3: «q1 ложно».

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

задача(6, [утверждение(q1, лжец(q2)), утверждение(q2, лжец(q3)),

                 утверждение(q3, лжец(q1))]).

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

No

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

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

   q1: «q2 ложно»;

   q2: «q3 ложно»;

   q3: «q4 ложно»;

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

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

задача(7, [утверждение(q1, лжец(q2)), утверждение(q2, лжец(q3)),

                 утверждение(q3, лжец(q4)), утверждение(q4, рыцарь(q1))]).

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

No

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

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

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

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

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

задача(8, [утверждение(a,рыцарь(a) v рыцарь(b)),

           утверждение(b,лжец(a) v лжец(b))]).

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

Nо

   Задачи о рыцарях и лжецах выглядят несколько искусственно, особенно в части того, что жители говорят всегда только правду или только ложь. Но во всех предложенных задачах каждый персонаж высказывается только один раз, поэтому требование «всегда» не учитывается. Кроме того, термины «рыцарь» и «лжец» полезны для формального описания задач и могут использоваться в разных ситуациях. В качестве примера, рассмотрим следующую задачу, решение которой весьма поучительно.

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

   A: B – рыцарь.

   B: A – лжец.

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

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

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

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

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

X = [a-нормальный, b-нормальный] ;

No

Как мы видим, рыцарей  среди них нет.

   Включение в постановку задачи высказывания о высказывании (назовем его метавысказыванием) несколько усложняет положение дел. Можно ли модифицировать программу так, чтобы она могла решать, например, следующую задачу?

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

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

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

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

   Да, это возможно. Самое существенное, что нужно сделать, это изменить термы, представляющие утверждения персонажей. Изменения небольшие: если T – терм, который представляет утверждение, то метаутверждение, высказанное персонажем X, представляем в виде утверждение(X,T). Получаем решение:

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

            утверждение(b, утверждение(a, лжец(a)))]).

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

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

No

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

   Пролог позволяет в рамках одной программы моделировать решения как прямых, так и обратных задач. Для этого достаточно модифицировать программу «Рыцари и лжецы». Более того, обобщенная программа будет работать для произвольной конкретизации множества высказываний и мира персонажей. В том числе и для случая, когда и множество высказываний и мир содержат переменные («неизвестные сущности»).

   Предпринятая модификация программы содержит главный предикат:

задача(S,I,Xs,L):-

      генерация_утверждений(S,Xs,L),

      мир(Xs,I),

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

   Здесь переменные имеют следующие значения: S – список утверждений (может содержать неизвестные реплики); I - (возможно неизвестный) мир; Xs - список персонажей; L - список известных утверждений (этот список получается из S путем конкретизации переменных входящих в S при допущении мира I).

 

 

 

 

 

 

 

Список использованной литературы

1. Зюзьков В. М. Моделирование автореферентных рассуждений с помощью логического программирования // Доклады ТУСУР. Том 7. Автоматизированные системы обработки информации, управления и проектирования. Сборник научных трудов. Томск, Изд-во ТУСУР, 2002, с. 113-122.

2.Смаллиан Р. Как же называется эта книга? – М.: Мир, 1981.– 238с.

3. http://www.swi.psy.uva.nl/projects/SWI-Prolog/

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение А

Листинг программы.

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

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

:- 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]).

переменные(нормальный(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,P),[X]).

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

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

мир([],[]).

мир([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-T]).

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

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

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

истинность(нормальный, истина).

истинность(нормальный, ложь).

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

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

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

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

      A \= B,

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

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

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

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

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

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

       Y=лжец, V=ложь;

       Y=нормальный, V=ложь).

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

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

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

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

       Y=нормальный, V=ложь).

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

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

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

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

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

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

      нет(V1,V).

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

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

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

      или(V1,V2,V).

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

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

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

      и(V1,V2,V).

оценка_формулы(утверждение(X,P),I,V,[_-рыцарь]):-

      оценка_формулы(~P,I,V,Z),!.

оценка_формулы(утверждение(X,P),I,V,[_-лжец]):-

      оценка_формулы(P,I,V,Z),!.

оценка_формулы(утверждение(X,P),I,V,[_-нормальный]):-

      оценка_формулы(P,I,V,Z),!.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

задача(4,[утверждение(a,лжец(a) & лжец(b) & лжец(c)),утверждение(b,рыцарь(a) & рыцарь(b) & лжец(c) v лжец(a) & рыцарь(b) & рыцарь(c) v рыцарь(a) & лжец(b) & рыцарь(c))]).

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

задача(6,[утверждение(q1, лжец(q2)), утверждение(q2, лжец(q3)),утверждение(q3, лжец(q1))]).

задача(7,[утверждение(q1, лжец(q2)), утверждение(q2, лжец(q3)),утверждение(q3, лжец(q4)), утверждение(q4, рыцарь(q1))]).

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

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

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