1. 1

(a)    no
(b)    X = пат   
(c)    X = боб
(d)    X = боб,    Y = пат

1. 2

(a)    ?-  родитель( X, пат).
(b)    ?-  родитель( лиз, X).
(c)    ?-  родитель( Y, пат),     родитель( X, Y).

1. 3

(a)    счастлив( X) :-
                родитель( X, Y).

(b)    имеетдвухдетей( X) :-
                родитель( X, Y),
                сестра( Z, Y).

1. 4

внук( X, Z) :-
        родитель( Y, X),
        родитель( Z, Y).

1. 5

тетя( X, Y) :-
        родитель( Z, Y),
        сестра( X, Z).

1. 6

Да.    (Определение верно)

1. 7

(a)    возвратов не будет
(b)    возвратов не будет
(c)    возвратов не будет
(d)    возвраты будут

2. 1

(a)    переменная
(b)    атом
(c)    атом
(d)    переменная
(e)    атом
(f)    структура
(g)    число
(h)    синтаксически неправильное выражение
(i)    структура
(j)    структура

2. 3

(a)    успех
(b)    неуспех
(c)    неуспех
(d)    D = 2,    Е = 2
(e)    Р1 = точка(-1, 0)
        Р2 = точка( 1, 0)
        Р3 = точка( 0, Y)

Такая конкретизация определяет семейство треугольников, у которых две вершины располагаются на оси х в точках 1 и -1, а третья - в произвольной точке оси у.

2. 4

отр( точка( 5, Y1),    точка( 5, Y2) )

2. 5

регулярный( прямоугольник( точка( X1, Y1),
                                    точка( Х2, Y1), точкa( X2, Y3),
                                    точка( X1, Y3) ) ).

Здесь предполагается, что первая точка соответствует нижней левой вершине прямоугольника.

2. 6

(a)    А = два
(b)    no
(c)    С = один
(d)    D = s(s(1));
        D = s(s(s(s(s(1)))))

2. 7

родственники( X, Y) :-
    предок( X, Y);
    предок( Y, X);
    предок( Z, X),
    предок( Z, Y);
    предок( X, Z),
    предок( Y, Z).

2. 8

преобразовать( 1, один).
преобразовать( 2, два).
преобразовать( 3, три).

2. 9

В случае, изображенном на рис. 2.10, пролог-система выполняет несколько больший объем работы.

2. 10

В соответствии с определением сопоставления, приведенном в разд. 2.2, данное сопоставление будет успешным. X приобретает вид циклической структуры, в которой сам X присутствует в качестве одного из аргументов.

3. 1

(a)    конк( L1, [ _, _, _ ], L)

(b)    конк( [ _, _, _ ], L1, L),
                        % Удалить 3 первые элемента L
        конк( L2, [ _, _, _ ], L1)
                        % Удалить 3 последние элемента L1

Вот более короткий вариант, предложенный I. Tvrdy:       

        конк( [ _, _, _ | L2], [ _, _, _ ], L)

3. 2

(а)    последний( Элемент, Список) :-
        конк( _, [Элемент], Список).

(b)    последний( Элемент, [Элемент]).

        последиий( Элемент, [Первый | Остальные]):-
        последний( Элемент, Остальные).

3. 3

четнаядлина( [ ] ).

четнаядлина( [Первый | Остальные] ) :-
    нечетнаядлина( Остальные).

нечетнаядлина( [ _ ] ).

нечетнаядлина( [Первый | Остальные] ) :-
    четнаядлина( Остальные).

3. 4

обращение( [ ], [ ]).

обращение( [Первый | Остальные], ОбращСпис): -
    обращение( Остальные, ОбращСписОстальных),
конк( О6ращСписОстальных, [Первый], ОбращСпис).

3. 5

% Такой предикат легко определить при помощи отношения обратить

палиндром( Список) :-
    обратить( Список, Список).

% Вот другое решение, не использующее обратить

палиндром1( [ ] ).

палиндром1( [ _ ] ).

палиндром1 [Первый | Остальные] ) :-
    конк( Середина, [Первый], Остальные),
    палиндром1( Середина).

3. 6

сдвиг( [Первый | Остальные], Сдвинут) :-
    конк( Остальные, [Первый], Сдвинут).

3. 7

перевод( [ ], [ ]).

перевод( [Голова | Хвост], [Голова1 | Хвост1]) :-
    означает( Голова, Голова1),
    перевод( Хвост, Хвост1).

3. 8

подмножество( [ ], [ ] ).

подмножество( [Первый | Остальные], [Первый | Подмн]):-
                                % Оставить первый элемент в подмножестве
    подмножество( Остальные, Подмн).

подмножество( [Первый | Остальные], Подмн) :-
                                % Убрать первый элемент из подмножества
    подмножество( Остальные, Подмн).

3. 9

разбиениесписка( [ ], [ ], [ ]).                           % Разбивать нечего

разбиениесписка( [X], [X], [ ]).
                            % Разбиение одноэлементного списка

разбиениесписка( [X, Y | Список], [Х | Список1],
                                [Y | Список2]) :-
    разбиениесписка( Список, Список1, Список2).

3. 10

можетзавладеть( состояние( _, _, _, имеет), [ ] ).
                                % Ничего не надо делать

можетзавладеть( Состояние, [Действие | Действия]):-
    ход( Состояние, Действие, НовоеСостояние),
                                % Первое действие
    можетзавладеть( НовоеСостояние, Действия).
                                % Оставшиеся действия

3. 11

линеаризация( [Голова | Хвост], ЛинейныйСписок ) :-
                                % Линеаризация непустого списка
    линеаризация( Голова, ЛинейнаяГолова ),
    линеаризация( Хвост, ЛинейныйХвост ),
    конк( ЛинейнаяГолова, ЛинейныйХвост,
        ЛинейныйСписок ).

линеаризация( [ ], [ ] ).                  % Линеаризация пустого списка

линеаризация( X, [X] ).
                            % Линеаризация объекта, не являющегося списком

% Замечание: при попытке получить от этой программы более
% одного варианта решения выдается бессмыслица

3. 12

Терм1 = играет_в( джимми, и( футбол, сквош) )
Терм2 = играет_в( сьюзан, и( теннис,
                                    и( баскетбол, волейбол) ) )

3. 13

:- ор( 300, xfx, работает)
:- ор( 200, xfx, в)
:- ор( 100, xfx, нашем)

3. 14

(a)    А = 1 + 0
(b)    В = 1 + 1 + 0
(c)    С = 1 + 1 + 1 + 1 + 0
(d)    D = 1 + 1 + 0 + 1

3. 15

:- ор( 100, xfx, входит_в)
:- ор( 300, fx, конкатенация_списков)
:- ор( 200, xfx, дает)
:- ор( 100, xfx, и)
:- ор( 300, fx, удаление_элемента)
:- ор( 100, xfx, из_списка)                         % Принадлежность к списку

Элемент входит_в [Элемент | Список].
Элемент входит_в [Первый | СписокОстальных] :-
Элемент входит_в СписокОстальных.

% Конкатенация списков

конкатенация_списков [ ] и Список дает Список.

конкатенация_списков [X | L1] и L2 дает [X | L3] :-
    конкатенация_списков L1 и L2 дает L3.

% Удаление элемента из списка

удаление_элемента Элемент иэ_списка
            [Элемент | ОстальныеЭлементы]
            дает ОстальныеЭлементы.

удаление_элемента Элемент из_списка
        [Первый | ОстальныеЭлементы]
        дает [Первый | НовСписОстЭлементов] :-
    удаление_элемента Элемент из_списка
            ОстальныеЭлементы дает НовСписОстЭлементов.

3. 16

max( X, Y, X) :-
    X >= Y.

max( X, Y, Y) :-
    X <Y.

3. 17

максспис( [X], X).
                            % Максимум в одноэлементном списке
максспис( [X, Y | Остальные], Мах) :-
                            % В списке есть по крайней мере два элемента?
    максспис( [Y | Остальные], МаксОстальные),
    mах( X, МаксОстальные, Мах).
                            % Мах наибольшее из чисел X и МаксОстальные

3. 18

сумспис( [ ], 0).

сумспис( [Первый | Остальные], Сумма) :-
    сумспис( Остальные, СуммаОстальных),
    Сумма is Первый + СуммаОстальных.

3. 19

упорядоченный ([ ]).
                        % Одноэлементный список является упорядоченным

упорядоченный( [X, Y | Остальные] :-
    X =< Y,
    упорядоченный( [Y | Остальные] ).

3. 20

подсумма( [ ], 0, [ ]).

подсумма( [N | Список], Сумма, [N | Подмн]) :-
                    % N принадлежит подмножеству
    Сумма1 is Сумма - N,
    подсумма( Список, Сумма1, Подмн).

подсумма( [N | Список], Сумма, Подмн) :-
                    % N не принадлежит подмножеству
    подсумма( Список, Сумма, Подмн).

3. 21

между( N1, N2, N1) :-
    N1 =< N2.

между( N1, N2, X) :-
    N1 < N2,
    HoвoeNl is N1 + 1,
    между( HoвoeNl, N2, X).

3. 22

:- ор( 900, fx, если).
:- ор( 800, xfx, то).
:- ор( 700, xfx, иначе).
:- ор( 600, xfx, :=).
если Вел1 > Вел2 то Перем := Вел3
                                иначе ЧтоУгодно :-
    Вел1 > Вел2,
    Перем = Вел3.

если Вел1 > Вел2 то ЧтоУгодно
                                иначе Перем := Вел4 :-
    Вел1 =< Вел2,
    Перем = Вел4.

4. 1

(a)    ?-  семья(членсемьи( _, Фамилия, _, _ ), _, [ ]).

(b)    ?-  ребенок( членсемьи( Имя, Фамилия, _,
                                работает( _, _ ) )).

(c)    семья(членсемьи( _, Фамилия, _, неработает),
                    членсемьи( _, _, _, работает( _, _ ) ),_ ).

(d)    ?-  семья( Муж, Жена, Дети),
            датарождения( Муж, дата( _, _, Год1) ),
            датарождения( Жена, дата( _, _, Год2) ),
            ( Год1 - Год2 >= 15;
              Год2 - Год1 >= 15 ),
            принадлежит( Ребенок, Дети).

4. 2

близнецы( Ребенок1, Ребенок2) :-
    семья( _, _, Дети),
    удалить( Ребенок1, Дети, ДругиеДети),
                            % Выделить первого ребенка
    принадлежит( Ребенок2, ДругиеДети),
    принадлежит( Ребенок1, Дата),
    принадлежит( Ребенок2, Дата).

4. 3

n_элемент( 1, [X | L], X).
                            % X - первый элемент списка [X | L]

n_элемент( N, [Y | L], X) :-
                            % X - n-й элемент [Y | L]

N1 is N - 1,
n_элемент( N1, L, X).

4. 4

Входная цепочка укорачивается на каждом неспонтанном цикле, а укорачиваться бесконечно она не может.

4. 5

допускается( S, [ ], _ ) :-
    конечное( S).

допускается( S, [X | Остальные], Макс_переходов) :-
    Макс_переходов > 0,
    переход( S, X, S1),
    НовыйМакс is Макс_переходов - 1,
    допускается( S1, Остальные, НовыйМакс).

допускается( S, Цепочка, Макс_переходов) :-
    Макс_переходов > 0,
    спонтанный( S, S1),
    НовыйМакс is Макс_переходов - 1,
    допускается( S1, Цепочка, НовыйМакс).

4. 7

(а)    ходконя( X/Y, X1/Y1) :-
                        % Ход коня с поля X/Y на поле X1/Y1
            ( dxy( DX, DY);
                        % Расстояния по направлениям X и Y
              dxy( DY, DX) ),
                        % Или расстояния по направлениям Y и X
            X1 is X + DX,
                        % X1 расположен в пределах шахматной доски
            надоске( X1),
            Y1 is Y + DY,
                        % Y1 расположен в пределах шахматной доски
            надоске( Y1).

        dxy( 2, 1).             % 2 поля вправо, 1 поле вперед
        dxy( 2, -1).            % 2 поля вправо, 1 поле назад
        dxy( -2, 1).            % 2 поля влево, 1 поле вперед
        dxy( -2, -1).           % 2 поля влево, 1 поле назад

        надоске( Коорд) :-
                            % Координаты в пределах доски
            0 < Коорд,
            Коорд < 9.

(b)    путьконя( [ Поле]).         % Конь стоит на поле Поле
            путьконя( [S1, S2 | Остальные] ) :-
            ходконя( S1, S2),
            путьконя( [S2 | Остальные]).

(c)    ?-  путьконя( [2/1, R, 5/4, S, Х/8] ).

5. 1

(a)    X = 1;
        X = 2

(b)    X = 1;
        Y = 1;

        X = 1;
        Y = 2;

        X = 2;
        Y = 1;

        X = 2
        Y = 2;

(c)    X = 1;
        Y = 1;

        X = 1;
        Y = 2;

5. 2

класс( Число, положительное) :-
    Число > 0,  !.

класс( 0, нуль) :-  !.

класс( Число, отрицательное).

5. 3

разбить( [ ], [ ], [ ]).

разбить( [X | L], [X | L1], L2) :-
    X >= 0,  !,
    разбить( L, L1, L2).

разбить( [X | L], L1, [X | L2]) .
    разбить( L, L1, L2).

5. 4

принадлежит( Некто, Кандидаты),
        not принадлежит( Некто, Исключенные)

5. 5

разность( [ ], _, [ ]).

разность( [X | L1], L2, L):-
    принадлежит( X, L2),  !,
    разность( L1, L2, L).

разность( [X | L1], L2, [X | L]) :-
    разность( L1, L2, L).

5. 6

унифицируемые( [ ], _, [ ]).

унифицируемые( [Первый | Остальные], Терм, Список) : -
    not( Первый = Терм),  !,
    унифицируемые( Остальные, Терм, Список).

унифицируемые( [Первый | Остальные], Терм,
                                [Первый | Список] ) :-
    унифицируемые( Остальные, Терм, Список).

6. 1

найтитерм( Терм) :-
                            % Пусть текущий входной поток - это файл f
    read( Терм),  !,
                            % Текущий терм из f сопоставим с Терм'ом?
    write( Терм);                  % Если да - вывести его на терминал
    найтитерм( Терм).       % В противном случае - обработать

6. 2

найтитермы( Терм) :-
    read( ТекущийТерм),
    обработать( ТекущийТерм, Терм).

обработать( end_of_file, _ ) :-  !.

обработать( ТекущийТерм, Терм) :-
    ( not( ТекущийТерм = Терм),  !;
                        % Термы несопоставимы
      write( ТекущийТерм), nl),
                        % В противном случае вывести текущий терм
    найтивсетермы( Терм).
                        % Обработать оставшуюся часть файла

6. 4

начинается( Атом, Символ) :-
    name( Символ, [ Код]),
    name( Атом, [Код | _ ]).

6. 5

plural( Существительное, Существительные) :-
    name( Существительное, СписокКодов),
    name( s, КодS),
    конк( СписокКодов, КодS, НовыйСписокКодов),
    name( Существительные, НовыйСписокКодов).

7. 2

добавить( Элемент, Список) :-
    var( Список),  !,
                        % Переменная Список представляет пустой список
Список = [Элемент | Хвост].

добавить( Элемент, [ _ | Хвост]) :-
    добавить( Элемент, Хвост).

принадлежит( X, Список) :-
    var( Список),  !,
                    % Переменная Список представляет пустой список,
                           % поэтому X не может ему принадлежать
fail.

принадлежит( X, [X | Хвост]).

принадлежит( X, [ _ | Хвост] ) :-
    принадлежит( X, Хвост).

8. 2

добавить_в_конец( L1-[Элемент | Z2], Элемент, L1 - Z2).

8. 3

обратить( А - Z, L - L) :-
                        % Результатом является пустой список,
                                % если A-Z представляет пустой список
    А == Z,  !.

обратить( [X | L] - Z, RL - RZ ) :-
                        % Непустой список
    обратить( L - Z, RL - [X | RZ].

9. 1

список( [ ]).

список( [ _ | Хвост]) :-
    список( Хвост).

9. 2

принадлежит( X, X затем ЧтоУгодно).

принадлежит( X, Y затем Спис) :-
    принадлежит( X, Спис).

9. 3

преобр( [ ], ничего_не_делать).

преобр( [Первый | Хвост], Первый затем Остальные):-
    преобр( Хвост, Остальные).

9. 4

преобр( [ ], ПустСпис, _, ПустСпис).
                                % Случай пустого списка

преобр( [Первый | Хвост], НовСпис, Функтор, Пустой) :-
    НовСпис =.. [Функтор, Первый, НовХвост],
    преобр( Хвост, НовХвост, Функтор, Пустой).

9. 8

сорт1( [ ], [ ]).

сорт1( [X], [X]).

сорт1( Спис, УпорСпис) :-
    разбить( Спис, Спис1, Спис2),
                            % Разбить на 2 прибл. равных списка
    сорт1( Спис1, Упор1),
    сорт1( Спис2, Упор2),
    слить( Упор1, Упор2, УпорСпис).
                            % Слить отсортированные списки
разбить( [ ], [ ], [ ]).

разбить( [X], [X], [ ]).

разбить( [X, Y | L], [X | L1], [Y | L2]) :-
                            % X и Y помещаются в разные списки
    разбить( L, L1, L2).

9. 9

(а)    двдерево( nil).

        двдерево( д( Лев, Кор, Прав) ) :-
            двдерево( Лев),
            двдерево( Прав).

9. 10

глубина( пусто, 0).

глубина( д( Лев, Кор, Прав), Г) :-
    глубина( Лев, ГЛ),
    глубина( Прав, ГП),
    макс( ГЛ, ГП, МГ),
    Г is МГ + 1.

макс( А, В, А) :-
    А >= В,  !.

макс( А, В, В).

9. 11

линеаризация( nil, [ ]).

линеаризация( д( Лев, Кор, Прав), Спис) :-
    линеаризация( Лев, Спис1),
    линеаризация( Прав, Спис2),
    конк( Спис1, [Кор | Спис2], Спис).

9. 12

максэлемент( д( _, Кор, nil), Кор) :-  !.
                            % Корень - самый правый элемент

максэлемент( д( _, _, Прав,), Макс) :-
                            % Правое поддерево непустое
    максэлемент( Прав, Макс).

9. 13

внутри( Элем, д( _, Элем, _ ), [ Элем]).

внутри( Элем, д( Лев, Кор, _ ), [Кор | Путь]) :-
    больше( Кор, Элем),
    внутри( Элем, Лев, Путь).

внутри( Элем,д( _, Кор, Прав), [Кор | Путь]) :-
    больше( Элем, Кор),
    внутри( Элем, Прав, Путь).

9. 14

% Отображение двоичного дерева, растущего сверху вниз
% Предполагается, что каждая вершина занимает при печати
% один символ

отобр( Дер) :-
    уровни( Дер, 0, да).
                            % Обработать все уровни
уровни( Дер, Уров, нет) :-  !.
                            % Ниже уровня Уров больше нет вершин
уровни( Дер, Уров, да) :-
                            % Обработать все уровни, начиная с Уров
    вывод( Дер, Уров, 0, Дальше), nl,
                            % Вывести вершины уровня Уров
    Уров1 is Уров + 1,
    уровни( Дер, Уров1, Дальше).
                            % Обработать следующие уровни
вывод( nil, _, _, _, _ ).

вывод( д( Лев, X, Прав), Уров, ГлубХ, Дальше) :-
    Глуб1 is ГлубХ + 1,
    вывод( Лев, Уров, Глуб1, Дальше),
                            % Вывод левого поддерева
( Уров = ГлубХ,  !,
                            % X на нашем уровне?
        write( X), Дальше = да;
                            % Вывести вершину, продолжить
        write(' ') ),
                            % Иначе - оставить место
        вывод( Прав, Уров, Глуб1, Дальше).
                            % Вывод левого поддерева

10. 1

внутри( Элем, л( Элем)).             % Элемент найден в листе

внутри( Элем, в2( Д1, М, Д2) ):-
                                                    % Вершина имеет два поддерева
    больше( М, Элем),  !,           % Вершина не во втором поддереве
    внутри( Элем, Д1);               % Поиск в первом поддереве
    внутри( Элем, Д2).               % Иначе - во втором поддереве

внутри( Элем, в3( Д1, М2, Д2, М3, Д3) ):-
                                                    % Вершина имеет три поддерева
    больше( М2, Элем),  !,
                % Элемент не во втором и не в третьем поддереве
    внутри( Элем, Д1);               % Поиск в первом поддереве
    больше( М3, Элем),  !,         % Элемент не в третьем поддереве
    внутри( Элем, Д2);               % Поиск во втором поддереве
    внутри( Элем, Д3).               % Поиск в третьем поддереве

10. 3

avl( Дер) :-
    аvl( Дер, Глуб).         % Дер является AVL-деревом глубины Глуб

avl( nil, 0).                     % Пустое дерево  -   AVL -дерево глубины 0

avl( д( Лев, Кор, Прав), Г) :-
    avl( Лев, ГЛ),
    avl( Прав, ГП),
    ( ГЛ is ГП; ГЛ is ГП + 1; ГЛ is ГП - 1),
                                    % Глубины поддеревьев примерно совпадают
        макс( ГЛ, ГП, Г).

макс1( U, V, М) :-                                     % М = 1 + макс( U, V)
    U > V,  !, М is U + 1;
    М is V + 1.

11. 1

вглубину1( [Верш | Путь], [Верш | Путь]) :-
    цель( Верш).

вглубину1( [Верш | Путь], Решение) :-
    после( Верш, Верш1),
    not принадлежит( Верш1, Путь),
    вглубину1( [ Верш1, Верш | Путь], Решение).

11. 6

решить( СтартМнож, Решение) :-
                            % СтартМнож - множество стартовых вершин
    bagof( [Верш], принадлежит( Верш, СтартМнож),
                                                        Пути),
    вширину( Пути, Решение).