1. Опишите синтаксис и семантику языка предикатов.

Основой логических моделей является понятие формальной системы, задаваемой четвёркой:

M=(T, P, A, F),

где T – множество базовых элементов (например, буквы некоторого алфавита);

P – множество синтаксических правил, на основе которых из T строятся формулы;

A – множество априорно истинных выражений (аксиомы);

F – семантические правила вывода, которые из множества А позволяют получить новые, правильно построенные формулы – теоремы.

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

Алфавит исчисления предикатов состоит из следующего набора символов:

• знаки пунктуации { ( , ) . };

• логические связи {, , ,  };

• знаки кванторов {,  };

• символы переменных {a, b, x, v, …};

• функциональные буквы {f, g, s, …};

• предикатные буквы {P, Q, N, …}.

Логика предикатов, называемая также логикой первого порядка, допускает четыре типа обозначений (имен):

- Константы. Они служат именами индивидуумов (в отличие от имен совокупностей), объектов, людей, событий. Константы обозначаются прописными буквами вроде: К, Слон, G.

- Переменные. Обозначают имена совокупностей, таких как человек, книга, посылка, событие, i, k. Для переменных имен используются строчные буквы.

- Предикатные имена (Предикатные константы). Они задают правила соединения констант и переменных, например правила грамматики, процедуры, математические операции. Для предикатных имен используются прописные буквы: Соединить, Посылка, А, P.

- Функциональные имена представляют такие же правила, как и предикаты. Функциональные имена пишут одними строчными буквами: фраза, сложить, разделить, g, f. Их называют также функциональными константами.

2. Опишите процедуру поиска методом редукции.

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

Поиск планирования в пространстве задач заключается в последовательном сведении исходной задачи к все более простым до тех пор, пока не будут получены только элементарные задачи. Частично упорядоченная совокупность таких задач составит решение исходной задачи. Расчленение задачи на альтернативные множества подзадач удобно представлять в виде И/ИЛИ-графа. В таком графе всякая вершина, кроме концевой, имеет либо конъюнктивно связанные дочерние вершины (И-вершина), либо дизъюнктивно связанные (ИЛИ-вершина). В частном случае, при отсутствии И-вершин, имеет место граф пространства состояний. Концевые вершины являются либо заключительными (им соответствуют элементарные задачи), либо тупиковыми. Начальная вершина (корень И/ИЛИ-графа) представляет исходную задачу. Цель поиска на И/ИЛИ-графе-показать, что начальная вершина разрешима. Разрешимыми являются заключительные вершины (И-вершины), у которых разрешимы все дочерние вершины, и ИЛИ-вершины, у которых разрешима хотя бы одна дочерняя вершина. Разрешающий граф состоит из разрешимых вершин и указывает способ разрешимости начальной вершины. Наличие тупиковых вершин приводит к неразрешимым вершинам. Неразрешимыми являются тупиковые вершины, И-вершины, у которых неразрешима хотя бы одна дочерняя вершина, и ИЛИ-вершины, у которых неразрешима каждая дочерняя вершина.

Билет №5