Изложены основы так называемой клаузальной логики, являющейся средством логического программирования. Последнее лежит в основе проектирования ЭВМ пятого поколения, над которыми в настоящее время работают специалисты ряда стран.
Для научных работников и инженеров, занимающихся проблемами искусственного интеллекта. Полезна аспирантам и студентам втузов.
Табл. 2. Ил. 146. Библиогр. 107 назв.
Рецензент академик Г. С. Поспелов
ОГЛАВЛЕНИЕ
Предисловие ДА. Поспелова........................................ 7
Предисловие автора к русскому изданию......................
Предисловие...................................
17-
1. Введение.....................................
Пример "Родственные связи" и клаузальная форма............... **
Более строгое определение клаузальной формы.................. **
Нисходящий и восходящий варианты определений................ II
Семантика клаузальной формы............................ j*
Пример "Грекам свойственно ошибаться"..................... ^
Пример "Факториал числа"...............................
Универсум дискурса и интерпретации........................ *°
Более строгое определение несовместности..................... *"
Семантика альтернативных заключений....................... f *
Клаузы Хорна....................................... ,2
Пример "Простые грибы и поганки"......................... ^
Упражнения........................................
37
2. Представления в форме клауз.............................
Инфиксная нотация................................... 38
Переменные и типы................................... 40
Существование...................................... 42
Отрицание......................................... 43
Отрицания заключений, являющихся импликациями............... ^
Условия, являющиеся импликациями........................ 45
Определения и словосочетания если-и-только-если................ 46
Семантические сети................................... 47
Расширенные семантические сети........................... 48
Представление информации при помощи бинарных предикатных символов ^
Преимущества бинарного представления . ..................... 52
Базы данных........................................ 53
Языки запросов...................................... 54
Описание данных..................................... 55
Ограничения целостности................................ 55
Пример "База данных кафедры"........................... 57
Равенство.......................................... go
Упражнения........................................
3. Нисходящие и восходящие процедуры доказательств, основанные на ^
использовании клауз Хорна..............................
Предварительные замечания.............................. ^
Задача грамматического разбора........................... «
Описание задачи грамматического разбора на языке логики предикатов
Восходящий вывод.................................... 67
Нисходящий вывод................................... 68
. Пример "Родственные связи"............................. 70
Правила вывода и стратегии поиска......................... 74
Бесконечные поисковые пространства: натуральные числа........... 77
Определения........................................ 79
Подстановка и согласование.............................. 82
Корректность и полнота систем логического вывода............... 83
Упражнения........................................ 84
4. Основы поиска решений на языке клауз Хорна.................. 87
Поиск пути......................................... 87
Задача о сосудах с водой............................., 87
Упрощенная задача поиска пути............................ 89
Представление поисковых пространств в виде графов.............. 90
Пространство поиска для задачи о сосудах с водой................ 92
Поисковые стратегии для задачи поиска пути................... 95
* Процесс редукции поиска решений и его представление в виде И-ИЛИ
дерева......................................... 97
Интерпретация клауз Хорна в терминах поиска решений............ 99
Расщепление и независимые подцели......................... 101
Зависимые подцели................................... 102
Поиск versus доказательство.............................. 104
Леммы, повторяющиеся подцели и циклы..................... 106
Стратегии поиска для пространств редукции задач................ 107
Двунаправленный поиск решений........................... 111
Обозначения для описаний двунаправленного поиска решений......... П2
Другая формулировка задачи поиска пути..................... 114
Иные аспекты поиска решений............................ 115
Упражнения........................................ 116
5. Процедурная интерпретация клауз Хорна...................... 118
s Термы как структуры данных............................. 119
Вычисление методом последовательного приближения к выходному
значению....................................... 121
Изменение назначений параметрам ролей входов и ролей выходов...... 122
Недетерминизм первого рода: несколько процедур согласуются с одним
процедурным вызовом............................... 122
Последовательный поиск как итерация....................... 124
"Не знаю" versus "не забочусь" в условиях недетерминизма первого рода 125
Недетерминизм второго рода: планирование процедурных вызовов..... 127
Выполнение программ способом снизу вверх.................. 130
Прагматическая сторона логических программ.................. 132
Отделение структур данных.............................. 134
Структуры данных: термы versus отношения.................... 135
Формальные средства описания баз данных и языки программирования 138
Алгоритм = Логика + Управление.......................... 138
Спецификация управляющего компонента..................... 140
Естественный язык = Логика + Управление..................... 143
• Упражнения......................................... 143
6. Построение планов и проблема остова........................ 147
Построение плана и мир блоков............................ 147
Описание задачи блочного мира на языке клауз.................. 149
Восходящее применение аксиомы пространства состояний (12)........ 153
Восходящее применение аксиомы остова (15)................... 154
Смешанное нисходящее и восходящее выполнение аксиомы остова (15) 154
Нисходящее выполнение в пространстве состояний и применение аксиомы остова....................................... 157
Приложения методов построения планов...................... 159
Ограничения^........................................ 160
Упражнения........................................ 161
7. Резолюция......................................... 162
Негативные цели и утверждения............................ 162
Резолюция......................................... 164
Расходящиеся от центра рассуждения, использующие клаузы Хорна..... 165
Пример "Пропозициональная логика"........................ 166
Стрелочная нотация для нехорновских клауз................... 170
Дизъюнктные решения задач, сформулированных в терминах нехорновских клауз...................................... .L
Факторизация .......................................
Упражнения..........................•.............
8. Процедура доказательства методом графа соединений.............. *•''
Начальный граф соединений.............................. 177
Резолюция связей в графе соединений....................."• - • 179
Смешанный нисходяще-восходящий поиск в задаче грамматического
разбора........................................ }81
Макропроцессирование и рассуждения, расходящиеся от центра........ 1ал
Использование стрелочных обозначений для управления выбором связей 184
Авторезольвентные клаузы.............................. 186
Удаление связей, резольвентами которых являются тавтологии........ 188
Процедура доказательства методом графа соединений.............. 189
Упражнения........................................ 191
9. Глобальные стратегии поиска решений....................... 193
Удаление избыточных подцелей............................ 194
Добавление замещающих подцелей.......................... 195
Устранение несовместных целевых предложений................. 196
Обобщение использования диаграмм в геометрических доказательствах 197
Цели как обобщенные решения............................ 198
Преобразование целей и информационный взрыв................. 199
Распознавание зацикливаний путем анализа различий.............. 199
Пример "Факториал числа"............................... 201
Инвариантные свойства процедур........................... 202
Упражнения........................................ 204
10. Соотношение между клаузльной формой и стандартной формой логики 207
Введение в стандартную форму логики....................... 207
Перевод в клаузальную форму............................ 211
Сравнение клаузальной и стандартной форм.................... 215
Конъюнктивные заключения и дизъюнктивные посылки............ 216
Дизъюнктивные заключения.............................. 217
Только-если части определений............................ 217
Импликации как посылки импликаций..................... 218
Вывод (извлечение) программ из спецификаций................. 219
Упражнения....................' . '................... 221
11 • Если-и-только-если.................................... 225
Необходимость только-если частей определений.................. 226
Термы versus отношения при использовании в качестве структур данных 227
Неформулируемые только-если посылки...................... 228
Двусмысленность только-если частей........................ 230
, Решения в объектном языке и в мета-языке.................... 231
Объектноязыковые и метаязыковые интерпретации отрицания....... 232
Клаузы Хорна, дополненные отрицанием, интерпретируемым как неудача 234
Доказательство свойств программ.......................... 236
Критика свойства монотонности логического следования............ 237
Упражнения........................................ 238
12. Формализация доказуемости.............................. 240
Корректная представимость.............................. 241
Простое определение отношения доказуемости.................. 242
Непосредственное исполнение versus имитация................... 243
Добавление и подавление посылок .......................... 245
Раскрутка......................................... 246
Комбинация объектного языка и мета-языка................... 247 .
Неполнота комбинации объектного языка и мета-языка............ 248 >
Более полная форма отношения Продемонстрировать.............. 249
Упражнения........................................ 250
13. Логика, изменчивость и противоречие........................
Информационные системы............................... 253
Динамика изменения информационных систем.................. 255
Восстановление совместности............................. 256
Логическая программа для естественного языка................. 259
Заключение . ....................................... 262
Список литературы..................................... 263
Именной указатель.................................... 272
Предметный указатель................................. 273 :
ПРЕДИСЛОВИЕ Д.А,ПОСПЕЛОВА
В мире существуют тысячи различных языков программирования. Подавляющее большинство известны лишь их создателям и никогда не применялись широкой армией пользователей. Законы выживаемости языков программирования пока известны не до конца, хотя многое в этом вопросе уже ясно. Например, никакой язык программирования не сможет выжить и распространиться (особенно сейчас), если он не обладает весьма большим набором вспомогательных средств, составляющих для него дружественную программную среду, куда входят сервисные программы, редакторы, трансляторы и многое другое. Язык без среды обречен на вымирание, как только исчезнет энтузиазм его создателей.
Поэтому появление в наше время нового жизнеспособного'языка программирования — событие редкое. Нужен какой-то мощный стимул, чтобы новичек вошел в ряды "джентльменского набора" языков, признанных мировым сообществом программистов.
Среди пионерских исследований, связанных с решением нечисловых задач на вычислительных машинах, появившихся вскоре после появления самих вычислительных машин, были исследования по машинному переводу. К чести лингвистов надо сказать, что из всех весьма далеких от точных наук специалистов они первыми сумели оценить те возможности, которые несли в себе новые технические устройства. Попытки использовать алгоритмический подход к созданию программ для перевода предложений с одного языка на другой, .а позже для автоматического реферирования текстов, фактографического поиска информации и синтеза естественно-языковых текстов выдвинули перед специалистами по программированию ряд новых задач. Обработка текстов во многом оказалась не такой, как работа с числовыми данными. Например, вся система базовых операций, из которых строятся процедуры работы с текстом, не совпадала с традиционным набором базовых операторов, оказавшимся удобным (и универсальным) для программирования вычислений. Поэтому программы обработки текстов, которые, в принципе, можно было свести к последовательности традиционных для вычислений базовых операторов, получались все же неуклюжими, плохо интерпретируемыми и неэффективными.
И поэтому с самого начала проникновения лингвистов, а вслед за ними логиков и других специалистов, которые видели в вычислительных машинах средство для автоматизации символьных преобразований, характер-
Цена: 300руб.
