§ 40. Знакомимся с логическим программированием

Определения и обозначения

Логическое программирование — способ составления программ через описание фактов, правил и вопросов к ним, а не через пошаговое указание действий. Программист задаёт, что известно и какие выводы допустимы. Система сама ищет доказательство нужного результата.

Факт — утверждение о конкретном объекте или отношении, которое программа считает истинным. Например, любит(Анна, информатика) сообщает о связи Анны с информатикой. Факты образуют исходные сведения, от которых начинается вывод.

Правило — условное утверждение, показывающее, когда из одних фактов можно вывести другой факт. Его можно прочитать так: если выполнены условия справа, верно утверждение слева. Правила позволяют не перечислять все знания по отдельности, а получать новые связи.

Запрос — вопрос к базе знаний, на который система ищет доказанный ответ. В нём можно спрашивать как о конкретном утверждении, так и о неизвестном объекте. Результатом будет подтверждение, значения переменных или отсутствие решений.

Как это устроено

База знаний строится из фактов и правил, потому что предметную область удобнее описывать её объектами и связями. Например, сведения о семье можно представить отношениями родитель, а не длинной последовательностью команд. Такое описание отделяет знания от способа их обработки: одну и ту же базу можно использовать для разных запросов.

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

При проверке запроса система сопоставляет его с фактами и правилами. Если вместо конкретного имени стоит переменная, она подбирает значение, при котором выражение совпадает с известным утверждением. Например, запрос любит(X, информатика) найдёт такое X, для которого в базе есть соответствующий факт.

Одного сопоставления бывает недостаточно, потому что нужное утверждение может выводиться через несколько правил. Система сначала проверяет цель, затем пытается доказать условия выбранного правила и повторяет этот процесс для каждой подцели. Так образуется цепочка: исходные факты становятся основаниями для новых выводов.

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

Основные элементы логической программы

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

Разбор задач

Задача 1. Нужно записать факт о том, что Анна любит информатику, и проверить соответствующий запрос. Здесь не требуется правило, потому что искомое утверждение дано непосредственно.

1. Записываем факт: любит(Анна, информатика).
2. Формулируем запрос: любит(Анна, информатика)?
3. Сравниваем запрос с фактом. Все имя и аргументы совпадают, поэтому утверждение доказано.

Ответ: запрос получает подтверждение, потому что такой факт есть в базе знаний.

Задача 2. Известно: родитель(Иван, Ольга) и родитель(Ольга, Пётр). Нужно применить правило «родитель родителя — предок» и выяснить связь Ивана с Петром.

1. Записываем правило: предок(X, Z) :- родитель(X, Y), родитель(Y, Z).
2. Подставляем X = Иван, Y = Ольга и Z = Пётр. Оба условия правила совпадают с имеющимися фактами.
3. Делаем вывод: предок(Иван, Пётр). Иван является предком Петра, поскольку он родитель его родителя.

Задача 3. Пусть дороги заданы фактами: дорога(А, Б), дорога(А, В), дорога(Б, Г), дорога(В, Г), дорога(Г, Д). Используем правила достижимости: достижим(X, Y) :- дорога(X, Y) и достижим(X, Y) :- дорога(X, Z), достижим(Z, Y).

1. Запрашиваем все значения Y в достижим(А, Y).
2. По непосредственным дорогам получаем Б и В. Через Б или В можно попасть в Г, а через Г — в Д.
3. Система перебирает обе ветви и собирает все найденные значения, не останавливаясь после первого ответа.

Ответ: из А достижимы Б, В, Г и Д. Если для некоторого города цепочка не найдена, он в ответ не включается.

Типичные ошибки

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

Записывать запрос как команду действий. Запрос не говорит системе, что делать по шагам, а задаёт требование к результату. Чтобы проверить себя, сформулируйте его как вопрос: какое утверждение нужно доказать или какое значение найти?

Смешивать имена объектов и переменные. Конкретное имя обозначает один объект, а переменная может получить разные значения. Проверьте написание: если вместо переменной случайно указано имя, система не сможет подобрать другой объект.

Ожидать только один ответ. Несколько фактов или маршрутов могут давать разные решения. После первого результата нужно позволить системе выполнить возврат и проверить остальные варианты.

Связь с другими темами

До темы нужны высказывания, логические связки, отношения между объектами и понятие переменной. Логическое программирование связано с алгоритмами, но задаёт не порядок команд, а условия поиска решения. Позже такой подход используется в искусственном интеллекте, экспертных системах, обработке знаний и задачах с ограничениями.

Что запомнить

• Логическая программа описывает знания и условия вывода.
• Факты задают исходные истинные утверждения.
• Правила позволяют получать новые утверждения из известных.
• Запрос формулирует вопрос к базе знаний.
• Переменные могут принимать значения, найденные при сопоставлении.
• Система перебирает возможные способы доказательства запроса.
• Один запрос может иметь несколько ответов или не иметь ни одного.