Формалные системы (индивидуальное, дополнительное задание)

  1. Реализовать правила для целых чисел, представленных в виде термов s(s(...0...)). Определить предикаты:

    • number(N), определяющий, является ли его параметр числом,
    • equal(N1, N2), определяющий равенство двух чисел,
    • more(N1, N2), определяющий, является ли первое число больше второго,
    • next(N1, N), вычисляющий следующее число для заданного,
    • prev(N1, N), вычисляющий предыдущее число для заданного, если это возможно, иначе возвращающий ложь,
    • sum(N1, N2, N), вычисляющий сумму двух чисел,
    • dif(N1, N2, N), вычисляющий разность двух чисел, если это возможно, иначе возвращающий ложь.
  2. Реализовать правила для множеств, представленных в виде термов set(a1, set(a2, ...nil...)). Определить предикаты:

    • is_set(S), определяющий, является ли его параметр множеством,
    • in(X, S), определяющий принадлежность элемента множеству,
    • equal(S1, S2), определяющий равенство двух множеств (в частности, запрос equal(set(a, set(b, nil)), set(b, set(a, nil))) должен возвращать истину),
    • subset(S1, S2), определяющий, является ли первое множество подмножеством второго,
    • add(X, S1, S), добавляющий элемент ко множеству,
    • remove(X, S1, S), удаляющий элемент из множества,
    • intersect(S1, S2, S), вычисляющий пересечение двух множеств,
    • union(S1, S2, S), вычисляющий объединение двух множеств.
  3. Реализовать правила для списков, представленных в виде термов list(a1, list(a2, ...nil...)). Определить предикаты:

    • is_list(L), определяющий, является ли его параметр списком,
    • in(X, L), определяющий принадлежность элемента списку,
    • equal(L1, L2), определяющий равенство двух списков,
    • sublist(L1, L2), определяющий, является ли первый список подсписком второго,
    • add_head(X, L1, L), добавляющий элемент в начало списка,
    • head(L, X), вычисляющий голову списка, если это возможно, иначе возвращающий ложь,
    • tail(L, L1), вычисляющий хвост списка, если это возможно, иначе возвращающий ложь,
    • concat(L1, L2, L), вычисляющий конкатенацию двух списков.
  4. Реализовать правила для двоичных деревьев, представленных в виде термов tree(a1, tree(a11, ...nil..., ...nil...), tree(a12, ...nil..., ...nil...)). Определить предикаты:

    • is_tree(T), определяющий, является ли его параметр деревом,
    • equal(T1, T2), определяющий равенство двух деревьев,
    • nodes(T, N), определяющий количество вершин в дереве,
    • leaves(T, N), определяющий количество листовых вершин в дереве,
    • depth(T, N), определяющий глубину дерева,
    • width(T, N), определяющий ширину дерева (максимальное количество вершин, одинаково удалённых от корня),
    • make_tree(X, T1, T2), создающий новое дерево с заданным корнем и двумя поддеревьями.
  5. Реализовать правила для деревьев поиска (двоичное дерево, в левом поддереве которого все элементы меньше корня, а в правом - не меньше), представленных в виде термов tree(10, tree(5, ...nil..., ...nil...), tree(12, ...nil..., ...nil...)). Определить предикаты:

    • is_tree(T), определяющий, является ли его параметр корректным деревом поиска,
    • in(N, T), определяющий принадлежность элемента дереву поиска,
    • add(N, T1, T), добавляющий новый элемент в дерево поиска,
    • min(T, N), возвращающий минимальный элемент в дереве поиска (находящийся в самом левом поддереве),
    • max(T, N), возвращающий максимальный элемент в дереве поиска.
  6. Реализовать правила для недетерминированного конечного автомата, представленного в лекции. Определить факты и предикаты:

    • final(S), набор фактов, определяющий допустимые состояния,
    • trans(S1, S2, C), набор фактов, определяющий переход из одного состояния в другое при заданном символе,
    • trans(S1, S2, nil), набор фактов, определяющих ε-переходы,
    • accepts(L, S0, NMax), правило, определяющее, примет ли автомат строку, содержащуюся в списке, начиная с заданного начального состояния и использующее заданное ограничение на количество проверок во избежание зацикливания.
  7. Реализовать часть базы знаний мира Вампуса при помощи следующих фактов и правил:

    • percept(X, Y, B, S, G), набор фактов, определяющих, какие из ощущений (ветерок, запах, блеск) ощущаются в квадрате [X, Y] (неизвестно агенту).
    • breezy(X, Y), правило, определяющее, чувствуется ли в заданном квадрате ветерок,
    • stinky(X, Y), правило, определяющее, чувствуется ли в заданном квадрате запах,
    • glittery(X, Y), правило, определяющее, чувствуется ли в заданном квадрате блеск,
    • adjacent(X1, Y1, X2, Y2), правило, возвращающее все квадраты, соседние по отношению к заданному.