- •Лекция №1 Логическая программа: основные конструкции
- •Лекция №2 Программирование баз данных
- •Структурированные и абстрактные данные
- •Логические программы и модель реляционной базы данных
- •Лекция №3 Рекурсивное программирование
- •Построение рекурсивных программ
- •Бинарные деревья
- •Работа с символьными выражениями
- •Лекция №4 Вычислительная модель логических программ
- •Абстрактный интерпретатор логических программ
- •Лекция №5 Теория логических программ Операционная и декларативная семантика. Интерпретация
- •Корректность программы
- •Лекция №6 Анализ структуры термов
- •Типовые предикаты
- •Составные термы
- •Лекция №7 Металогические предикаты
- •Типовые металогические предикаты
- •Сравнение неосновных термов
- •Использование переменных в качестве объектов
- •Доступность метапеременных
- •Лекция №8 Внелогические предикаты
- •Лекция №9 Недетерминированное программирование
- •Недетерминизм с произвольным выбором альтернативы и недетерминизм с неизвестным выбором альтернативы
- •Лекция №10 Неполные структуры данных
- •Лекция №11 Программирование второго порядка
- •Лекция №12 Методы поиска
- •Лекция №13 Нечеткая логика. Обработка нечетких данных
- •Лекция №14 Constraint-пролог: операционная семантика Программирование в ограничениях
- •Лекция №15 Применение логического программирования в задачах искусственного интеллекта. Тест Тьюринга.
- •Лекция №16 Введение в функциональное программирование
- •Лекция №17 Рекурсивные функции и лямбда-исчисление а.Черча
- •Лекция №18 Функциональные языки программирования Свойства функциональных языков
- •Лекция №19 Программирование в функциональных обозначениях Структуры данных и базисные операции
- •Типы в функциональных языках
- •Лекция №20 Представление и интерпретация функциональных программ Программная реализация
Лекция №2 Программирование баз данных
Имеются два основных применения логических программ: построение логической базы данных и работа со структурами данных. Логическая база данных строится из множества фактов и правил. Покажем, как множество фактов может определять отношения, так же как в реляционных базах данных. Мы покажем, как правила могут определять сложные реляционные вопросы, также как в реляционной алгебре. Таким образом, функциональные зависимости, связанные с реляционными базами данных, могут выражаться логическими программами, составленными из фактов и правил весьма ограниченного вида.
Простые базы данных
Начнем с повторного рассмотрения программы 1.1, библейской базы данных и ее расширения правилами, задающими семейные отношения. В самой базе данных имеются четыре основных предиката: отец/2, мать/2, мужчина/1 и женщина/1. Мы примем соглашение из теории баз данных и снабдим каждое отношение реляционной схемой, которая указывает роль каждой позиции в отношении (каждого аргумента в цели). Реляционными схемами для этих четырех предикатов будут соответственно отец(Отец, Ребенок), мать(Мать, Ребенок), мужчина(Человек) и женщина(Человек). Принятые мнемонические имена говорят сами за себя.
Будем придерживаться типографского соглашения о курсивном выделении реляционных схем. В правилах переменным даются содержательные имена, в то время как в вопросах – имена Х или Y. Многословные имена используются по-разному для переменных и предикатов. В случае переменной каждое слово начинается с прописной буквы, например: ПлемянницаИлиПлемянник; в случае имен функций и предикатов слова соединяются нижней чертой, например: конфликт_расписания.
Новые отношения строятся из этих основных отношений с помощью определения подходящих правил. Соответствующими реляционными схемами для отношений, введенных в предыдущей главе, являются сын(Сын, Родитель), дочь(Дочь, Родитель), родитель(Родитель, Ребенок) и внук(Внук, ДедИлиБабушка). С точки зрения логики несущественно, какие отношения определяются с помощью фактов, а какие – с помощью правил. Например, если соответствующая база данных содержит факты родитель, мужчина и женщина, то правила, определяющие отношения сын и дочь, остаются в силе. Для отношений, более не определяемых фактами, например отец и мать, следует ввести новые правила. Подходящими правилами будут
отец(Папа, Ребенок) родитель(Папа, Ребенок), мужчина(Папа).
мать(Мама, Ребенок) родитель(Мама, Ребенок), женщина(Мама).
Интересные правила могут появиться при превращении отношений, неявно присутствующих в базе данных, в явные. Например, поскольку нам известны отец и мать ребенка, то нам известно, у каких пар был потомок, или известны, в терминах Библии, прародители. Это отношение не задано явно в базе данных, однако простое правило может выявить эту информацию. Реляционная схема – прародители(Мужчина, Женщина).
прародители(Мужчина, Женщина)
отец(Мужчина, Ребенок), мать(Женщина, Ребенок).
Правило означает: «Мужчина и Женщина являются прародителями, если есть ребенок, отцом которого является Мужчина, а матерью – Женщина».
Другим примером извлечения информации из более простых сведений является отношение «быть детьми одних родителей» – братья и сестры. Дадим правило для брат(Брат, ДетиОднихРодителей).
брат(Брат, ДетиОднихРодителей)
родитель(Родитель, Брат),
родитель(Родитель, ДетиОднихРодителей),
мужчина(Брат).
Однако такое правило означает: «Брат является братом ДетейОднихРодителей, если Родитель является родителем Брата и ДетейОднихРодителей и Брат является мужчиной».
Определение отношения брат приводит к некоторой проблеме. Вопрос брат(Х, Х)? выполняется для любого ребенка Х мужского пола, что не согласуется с нашим пониманием отношения брат.
Для того чтобы исключить подобные утверждения из значения программы, введем предикат (Терм1, Терм2). Удобнее записывать этот предикат в обычном (инфиксном) виде. Таким образом. Терм1 Терм2 истинно, если Терм1 и Терм2 различны. Ограничимся пока примером термов, являющихся константами. В принципе этот предикат может быть определен с помощью таблицы Х Y для каждой пары различных индивидов X и Y из интересующей области. Рис. 2.1 представляет собой такую таблицу для программы 1.1.
авраам исаак. авраам аран. авраам лот.
авраам милка. авраам иска. исаак аран.
исаак лот. исаак милка. исаак иска.
аран лот. аран милка. аран иска.
лот милка. лот иска. милка иска.
Рис 2.1 Определение неравенства.
Новое правило для отношения брат:
брат(Брат, ДетиОднихРодителей)
родитель(Родитель, Брат),
родитель(Родитель, ДетиОдних Родителей),
мужчина(Брат),
Брат ДетиОднихРодителей.
Чем больше отношений уже введено, тем проще определять новые сложные понятия. Программа 2.1 определяет отношения дядя(Дядя, ПлемянницаИлиПлемянник), дети_одних_родителей(ДетиОднихРодителей1, ДетиОднихРодителей2) и родственник(Родственник1, Родственник2).
Другое отношение, неявно содержащееся в семейной базе данных, – является ли женщина матерью. Это отношение определяется с помощью отношений мать/2. Новой реляционной схемой является мать(Женщина), которая определяется правилом
мать(Женщина) мать(Женщина, Ребенок)
Это означает: «Женщина является матерью, если у нее есть Ребенок». Заметим, что одно и то же предикатное имя мать используется для описания двух разных отношений мать. Предикат мать имеет в этих двух случаях различное число аргументов, т. е. различную арность. В общем случае одно и то же предикатное имя с различными арностями описывает различные отношения.
дядя(Дядя, Субъект)
брат(Дядя, Родитель), родитель(Родитель, Субъект).
дети_одних_родителей(ДетиОднихРодителей1, ДетиОднихРодителей2)
родитель(Родитель, ДетиОднихРодителей1),
родитель(Родитель, ДетиОднихРодителей2), ДетиОднихРодителей1 ДетиОднихРодителей2.
родственник(Родственник1, Родственник2)
родитель(Родитель1, Родственник1),
родитель(Родитель2, Родственник2),
дети_одних_родителей(Родитель1, Родитель2).
Программа 2.1.Определение семейных отношений.
Чтобы не доводить семейные отношения до кровосмешения, сменим примеры и обратимся к описанию простых логических схем. Схему можно рассматривать с двух точек зрения: как топологический слой физических элементов, обычно описываемый диаграммой, и в виде взаимодействия функциональных элементов. Оба подхода легко отобразить в логической программе. Совокупность фактов представлена в диаграмме схемы, а правила описывают функциональные элементы.
База данных, приведенная в программе 2.2, представляет собой упрощенное описание логического вентиля «И», изображенного на рис. 2.2. Факты изображают связи между отдельными резисторами и транзисторами, входящими в схему. Реляционная схема резистора – resistor(Вывод1, Вывод2), Канального транзистора – transistor(Затвор, Исток, Сток).
Программа демонстрирует стиль толкования логических программ, который будет поддерживаться на протяжении всей книги. Перед каждой содержательной процедурой приводятся реляционная схема процедуры и словесное описание отношения. Советуем следовать этому способу комментирования, так как он заостряет внимание на декларативном понимании любых программ, в том числе и программ на Прологе.
Рис. 2.2-Логическая схема.
Правила, относящиеся к функциональным компонентам схемы, описывают работу отдельных групп резисторов и транзисторов Схема описывает вентиль «И», в котором выходной сигнал является логическим «и» двух входных сигналов. Один из способов построения такого вентиля состоит в последовательном соединении вентиля «И-НЕ» и инвертора. Такой способ и использован в данной схеме. Реляционные схемы для этих трех компонентов – and_gate(Input1, Input2, Output), nand_gate(Input1, Input2, Output) и inverter(Input, Output).
Чтобы понять программу 2.2, давайте разберем правило для инвертора. Оно утверждает, что инвертор строится из транзистора с заземленным истоком и резистора, один вывод которого присоединен к источнику питания. Затвор транзистора является входом инвертора, а свободный вывод резистора следует соединить со стоком транзистора, – это соединение образует выход инвертора. Общие переменные используются для описания общих соединений.
Рассмотрим вопрос and_gate(In1, In2, Out)? относительно программы 2.2. Имеется решение {In1 = n3, In2 = n5, 0ut = п1}. Это решение подтверждает, что факты действительно описывают вентиль «И», и указывает входы и выход вентиля.
resistor(power, n1).
resistor(power, n2).
transistor(n2, ground, nl).
transistor(n3, n4, n2).
transistor(n5, ground, n4).
inverter (Input,Output)
Output является инверсией Input.
inverter(Input, Output)
transistor(Input,ground,Output), resistor(power,Output).
nand-gate(Input1,Input2,Output)
Output является логическим «И-НЕ» Input1 и Input2.
nand_gate(Inputl,Input2,Output)
transistor(Input1,X,Output),
transistor(Input2, ground,X),
resistor(power, Output).
and_gate(Input1,Input2,Output)
Output является логическим «И» Input1 и Input2.
and_gate(Inputl,Input2,Output)
nand_gate(Input1, Input2,X),
inverter(X,Output).
Программа 2.2. Схема логического вентиля «И».
Рис 2.3 Вентиль ИЛИ