Подколзин А.С.

Компьютерное
моделирование

логических
процессов.

Архитектура и
язы ки реш ателя

задач

МОСКВА

ФИЗМАТЛИТ ®

УДК 519.95; 007:159.955
ББК 32.81
П 44

Издание осуществлено при поддержке
Российского фонда фундаментальных
исследований по проекту 08-01-07074

Под к о л з и н А. С. Компьютерное моделирование логических процессов. Архитекту-
ра и язык решателя задач. — М.: ФИЗМАТЛИТ, 2008. — 1024 с. — ISBN 978-5-9221-1045-7.

В книге представлено описание разработанного автором пакета прикладных программ «Ло-
гическая система “Искра”», обобщающего многолетний опыт компьютерного моделирования
логических процессов, в результате которого возникла развитая технология обучения «решате-
ля». В основном моделировались процессы решения математических задач. Было проработано
около 9000 задач из разных разделов математики. Создана база приемов решателя задач,
насчитывающая в настоящее время около 25 тыс. приемов. Фактически возникла мощная
система символьной компьютерной математики нового типа, позволяющая не только получать
ответы, но и прослеживать ход решения по шагам. Для обучения «решателя» был развит
новый язык, объединяющий в себе два логических уровня — предметной области и принятия
решений, что позволило существенно ускорить обучение решателя и создало предпосылки
для исследований по автоматическому синтезу приемов. Прилагается адрес в сети программы
«решателя».
Студентам, аспирантам и специалистам по искусственному интеллекту, программированию
и компьютерной математике.

ISBN 978-5-9221-1045-7

c⃝ ФИЗМАТЛИТ, 2008

c⃝ А. С. Подколзин, 2008

ОГЛАВЛЕНИЕ

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11

Г л а в а 1. Общие замечания о логических процессах и их моделировании . . . . . .
14

Г л а в а 2. Логический язык решателя задач . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.1. Общелогические понятия . .. . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . .
31
2.2. Алгебра множеств . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.3. Элементарная алгебра. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .
34
2.4. Математический анализ . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.5. Элементарная геометрия . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2.6. Аналитическая геометрия . .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
41
2.7. Элементы линейной алгебры . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
2.8. Комплексные числа . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
2.9. Теория вероятностей. .. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
2.10. Элементарная физика . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48

Г л а в а 3. Представление задач в решателе . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
3.1. Структуры данных, используемые для представления задачи. .. . . . . . . . . . . . . .
59
3.2. Целевые установки задач . .. . . . . . . . .. . . . . . . . .. . . . . . . . . . . . . . . . . . . . .
61
3.3. Примеры формулировки задач для решателя. .. . . . . . . . . . . . . . . . . . . . .. . . . .
64
3.3.1. Алгебра множеств (64).
3.3.2. Элементарная алгебра (65).
3.3.3. Ком-
бинаторика (68).
3.3.4. Элементарная геометрия (69).
3.3.5. Математический
анализ (71).
3.3.6. Дифференциальные уравнения (78).
3.3.7. Аналитическая
геометрия и линейная алгебра (80). 3.3.8. Комплексные числа (82). 3.3.9. Теория
вероятностей (84).
3.3.10. Элементарная физика (85).
3.3.11. Вычислительные
задачи (88).
3.4. Интерфейс ввода задач . .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
89
3.4.1. Оглавление задачника (89). 3.4.2. Просмотр задач и основные операции над
задачами (90). 3.4.3. Ввод новой задачи (92). 3.4.4. Формульный редактор (99).
3.4.5. Текстовый редактор (117). 3.4.6. Геометрический редактор (119).

Г л а в а 4. Общая схема функционирования решателя . . . . . . . . . . . . . . . . . . . .
123
4.1. Сканирование задачи . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
123
4.2. Запуск решения задачи и его пошаговый просмотр . .. . . . . . . . . . . . . . . . . .. . .
125

Оглавление

4.3. Диалоговые задачи. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
130
4.4. Упражнения по вводу и решению задач . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
131
4.4.1. Элементарная алгебра (132).
4.4.2. Планиметрия (134).
4.4.3. Математи-
ческий анализ (137). 4.4.4. Аналитическая геометрия и линейная алгебра (139).
4.4.5. Дифференциальные уравнения (142).
4.5. Анализ траекторий решения задач при обучении решателя . .. . . . . . . . . . . . . . .
143
4.6. Сравнение логической системы с системами компьютерной математики . .. . . . . .
165
4.6.1. Упрощение выражений и уравнения с одной неизвестной (166).
4.6.2. Си-
стемы уравнений и неравенств (171).
4.6.3. Элементарная геометрия (173).
4.6.4. Аналитическая геометрия (175).
4.6.5. Алгебра логики, алгебра множеств
и комбинаторика (175).
4.6.6. Математический анализ (177).
4.6.7. Диффе-
ренциальные уравнения (179).
4.6.8. Теория вероятностей (179).
4.6.9. Ли-
нейная алгебра (180).
4.6.10. Комплексный анализ (181).
4.6.11. Элементар-
ная физика (181).
4.6.12. Вычисления (182).
4.6.13. Понимание текстов (184).
4.6.14. Анализ изображений (184). 4.6.15. Игровые ситуации (186). 4.6.16. Про-
чие возможности (186).

Г л а в а 5. Алгоритмический язык ЛОС . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
188

5.1. Структуры данных и общая схема организации программы на языке ЛОС . . . . . .
188
5.2. Основные операторы языка ЛОС. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
193
5.2.1. Общие операторы (193). 5.2.2. Операторы просмотра и преобразования зада-
чи (196). 5.2.3. Операторы логического представления данных (198). 5.2.4. Опе-
раторы сетевого представления данных (200).
5.2.5. Арифметические операто-
ры (202). 5.2.6. Операторы интерфейса (205).

Г л а в а 6. Библиотека вспомогательных операторов ЛОСа . . . . . . . . . . . . . . . . .
221

6.1. Операторы для работы с наборами и вхождениями в наборы . .. . . . . . . . . . . . . .
221
6.2. Операторы для работы с логическими структурами данных. .. . . . . . . . . . . . . . .
222
6.2.1. Перечисляющие операторы (223). 6.2.2. Вхождения в терм (226). 6.2.3. По-
строение нового терма (228).
6.2.4. Свойства терма и отношения между терма-
ми (230). 6.2.5. Списки термов (232).
6.3. Операторы для работы с задачами . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
233
6.3.1. Элементы задачи и связи ее с другими задачами (233). 6.3.2. Преобразова-
ния задачи (234). 6.3.3. Создание и решение вспомогательных задач (237).
6.4. Арифметические операторы . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
240
6.4.1. Десятичные числа (240). 6.4.2. Термы, представляющие числовые констан-
ты (241). 6.4.3. Вычисления с плавающей запятой (243).
6.5. Общие процедуры интерфейса . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
243
6.5.1. Клавиатура,
мышь
и
меню (243).
6.5.2. Текстовый
редактор (245).
6.5.3. Формульный
редактор (246).
6.5.4. Геометрический
редактор (248).
6.5.5. Просмотр термов и списков (249). 6.5.6. Текст-формульный редактор (252).
6.5.7. Оглавления (256). 6.5.8. Информационные блоки (260). 6.5.9. Диалоговые
блоки (261). 6.5.10. Разное (264).

Г л а в а 7. Редактор программ ЛОСа . . . . .. . . . . . . . .. . . . . . . . . . . . . . . . . . . . .
266

7.1. Названия логических символов . .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .
266
7.1.1. Просмотр названий логических символов (266).
7.1.2. Изменение словаря
и получение дополнительной информации о символе (266). 7.1.3. Перечень назва-
ний операторов ЛОСа (267).

Оглавление
5

7.2. Интерфейс редактора программ . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
268
7.2.1. Вход в редактор программ ЛОСа (268).
7.2.2. Просмотр фрагментов про-
граммы (269).
7.2.3. Редактирование текущего фрагмента программы (273).
7.2.4. Сдвиг номеров программных переменных (275). 7.2.5. Операции с ветвями
программы (275).
7.2.6. Обнаружение ошибок в программе (276).
7.2.7. Сопро-
вождение справочной информацией избранных точек в программе (277). 7.2.8. До-
полнительные возможности интерфейса редактора программ (278).

Г л а в а 8. Отладчик ЛОСа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
279

8.1. Семантическая трассировка решения задачи. .. . . . . . . . . . . . . . . . . .. . . . . . . .
279
8.2. Установка режимов технической трассировки перед запуском решения . .. . . . . . .
280
8.3. Просмотр информации о моменте прерывания. .. . . . . . . . . . . . . . . . . . . . . . . .
281
8.3.1. Просмотр программы (282). 8.3.2. Просмотр цепи задач (283). 8.3.3. Про-
смотр значений программных переменных (283).
8.3.4. Сообщение об ошибке
в программе (285).
8.3.5. Выход в базу приемов, реализованных на ГЕНО-
ЛОГе (286). 8.3.6. Техническая трассировка (286).
8.4. Тестирование программы оператора, операторного выражения либо справочника
290

Г л а в а 9. Примеры и упражнения по программированию на ЛОСе . . . . . . . . . .
291

9.1. Примеры программ приемов, применяемых при сканировании задачи . .. . . . . . . .
291
9.2. Примеры программ вспомогательных операторов и операторных выражений . .. . .
300
9.3. Упражнения по программированию на ЛОСе. . . . . . . . . . . . . . . . . . . . . . . . . .
304
9.3.1. Просмотр программ (304). 9.3.2. Логические символы (306). 9.3.3. Редак-
тирование программы (308). 9.3.4. Запуск программы и ее отладочная трассиров-
ка (311).

Г л а в а 10. Язык для записи приемов ГЕНОЛ´OГ . .. . . . . . . . . . . . . . . . . . . . . . .
318

10.1. Основные компоненты описания приема на языке ГЕНОЛ´ОГ . .. . . . . . . . . . . . .
319
10.2. Типы заголовков приемов . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
321
10.2.1. Приемы,
осуществляющие
тождественную
либо
эквивалентную
заме-
ну (321).
10.2.2. Приемы для вывода следствий (323).
10.2.3. Обратный вывод
для условий задачи (323).
10.2.4. Приемы для усмотрения ответа задачи (324).
10.2.5. Перенесение во внешнюю задачу на описание утверждений из блока
анализа (326).
10.2.6. Ввод и удаление комментариев (326).
10.2.7. Пакетные
операторы и их приемы (326). 10.2.8. Вычислительные пакеты (331). 10.2.9. Про-
стейшие приемы непосредственного усмотрения истинности либо ложности (332).
10.2.10. Приемы справочников (332). 10.2.11. Приемы вывода теорем (336).
10.3. Типы фильтров приемов . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .
336
10.3.1. Логические связки и квантор существования (337).
10.3.2. Равенство
объектов (338).
10.3.3. Сравнение
числовых
характеристик
термов (338).
10.3.4. Ограничения на задачу (338). 10.3.5. Ограничения на термы, переменные
и
логические
символы
(339).
10.3.6. Ограничения
на
вхождения
(341).
10.3.7. Ограничения на наборы (341).
10.3.8. Ограничения на новые термы,
вводимые приемом (342).
10.3.9. Ограничение на способ идентификации (342).
10.3.10. Числовые предикаты (342).
10.3.11. Учет комментариев задачи либо
пакетного оператора (342).
10.3.12. Ограничения на точку привязки (343).
10.3.13. Обращение к проверочному оператору из фильтра (344). 10.3.14. Иденти-
фицирующие термы (344). 10.3.15. Операторные выражения (350). 10.3.16. Оче-
редность проверки фильтров и дополнительные действия при проверке (357).

Оглавление

10.4. Типы указателей приемов . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
357
10.4.1. Указатели идентификации (357).
10.4.2. Указатели обработки антецеден-
тов теоремы (375).
10.4.3. Указатели, уточняющие тип основного преобразова-
ния (387).
10.4.4. Указатели, играющие роль дополнительных фильтров либо
отменяющие ограничения на применение приема (389).
10.4.5. Указатели, уточ-
няющие способ формирования новых термов (389).
10.4.6. Указатели, опреде-
ляющие дополнительные преобразования (391).
10.4.7. Указатели, уточняющие
точку привязки приема (396).
10.4.8. Указатели, определяющие преобразова-
ния комментариев (397).
10.4.9. Указатели, определяющие переключение вни-
мания (401).
10.4.10. Ограничитель трудоемкости (402).
10.4.11. Отложенная
фильтрация (403).
10.4.12. Специальные указатели пакетных операторов (403).
10.4.13. Указатели, определяющие отбор и сохранение ссылок на задачи, рассмот-
рение которых представляет интерес для развития приема (406).
10.4.14. Указа-
тели, определяющие формирование информации для трассировки (406).
10.5. Нормализаторы приема . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .
408
10.5.1. Обращения к пакетным нормализаторам (409). 10.5.2. Обращения к вспо-
могательным задачам (410). 10.5.3. Указатели коррекции посылок (411).

Г л а в а 11. Редактор приемов ГЕНОЛ´ОГа. .. . . . . . . . .. . . . . . . . . . . . . . . . . . . .
412

11.1. Просмотр описаний приемов . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
412
11.1.1. Вход
в
редактор
приемов (412).
11.1.2. Отображение
приема
на
экране (412). 11.1.3. Просмотр компонент описания приема (413). 11.1.4. Полу-
чение справочной информации при просмотре приема (415). 11.1.5. Указатели на
степень готовности приема (416). 11.1.6. Переход от просмотра описания приема
к просмотру других разделов системы (416).
11.2. Редактирование приемов . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .
417
11.2.1. Ввод нового приема (417).
11.2.2. Сохранение описания приема и ком-
пиляция (419).
11.2.3. Изменение приема (420).
11.2.4. Буфер базы прие-
мов (421). 11.2.5. Перенесение приема в другой концевой пункт оглавления (421).
11.2.6. Удаление приема (422). 11.2.7. Автоматическое пополнение описания при-
ема (422).
11.3. Дополнительные возможности редактора приемов . .. . . . . . . . . . . . . . . . . . . . .
423
11.3.1. Разрезание окна на несколько частей либо склейка частей окна (423).
11.3.2. Копирование приема либо его фрагментов (423).
11.3.3. Изменение ло-
гического символа, за которым закреплен прием (424).
11.3.4. Поиск приемов
заданного вида в базе приемов (424).
11.3.5. Перенесение приемов из версии
системы, находящейся в директории ALTSOL (425).
11.4. Анализ применений приема на обучающем материале . .. . . . . . . . . . . . . . . . . .
425
11.5. Расширение списка символов, прорисовываемых формульным редактором . .. . . . .
427
11.6. Инициализация пакетных операторов . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
428
11.6.1. Инициализация оператора вручную (428).
11.6.2. Интерфейс ускоренной
инициализации оператора (429).

Г л а в а 12. Примеры записи приемов на ГЕНОЛОГе и упражнения . . . . . . . . . .
431

12.1. Примеры записи приемов . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .
431
12.1.1. Приемы тождественной замены (431).
12.1.2. Приемы эквивалентной за-
мены (434).
12.1.3. Приемы вывода в посылках задачи (438).
12.1.4. Прие-
мы вывода в условиях задачи на описание (445).
12.1.5. Приемы нормализато-
ров (447).
12.1.6. Приемы проверочных операторов (465).
12.1.7. Приемы син-
тезаторов (468).
12.1.8. Приемы анализаторов (471).
12.1.9. Операторы филь-
тра (474).

Оглавление
7

12.2. Упражнения по работе с редактором приемов . .. . . . . . . . . . . . . . . . . . . . . . . .
475
12.2.1. Поиск приемов (475). 12.2.2. Просмотр описания приема (479). 12.2.3. Ре-
дактирование приема (484). 12.2.4. Анализ приема (492). 12.2.5. Создание нового
приема (505).

Г л а в а 13. Программы общего интерфейса системы . . . . . . . . . . . . . . . . . . . . .
515

13.1. Главное меню . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
515
13.1.1. Начало программы общего интерфейса (515).
13.1.2. Обращение к оглав-
лению приемов (517).
13.1.3. Обращение к редактору ЛОСа (518).
13.1.4. Об-
ращение к оглавлению задачника (520).
13.1.5. Операции со словарем (521).
13.1.6. Уплотнение и сохранение файлов (522).
13.1.7. Обращение к оглавлению
программ (523).
13.1.8. Редакция шрифта (524).
13.1.9. Вход в просмотр и ре-
дактирование информационных блоков (525).
13.1.10. Вход в просмотр и редак-
тирование вспомогательных меню (528).
13.1.11. Операции со словарем тексто-
вого анализатора (528).
13.1.12. Обращение к оглавлению базы теорем (531).
13.1.13. Прочие функции главного меню (532).
13.2. Программа интерфейса оглавлений . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
532
13.2.1. Типы оглавлений (532).
13.2.2. Инициализация обращения к оглавле-
нию (534). 13.2.3. Обработка команд интерфейса оглавления (537).
13.3. Программа формульного редактора . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
549
13.3.1. Структура данных, используемая для прорисовки формул в стандартной
математической записи (549).
13.3.2. Начало программы формульного редакто-
ра (551). 13.3.3. Обработчик команд формульного редактора (553). 13.3.4. Обра-
ботка очередного символа набираемой формулы (556). 13.3.5. Прорисовка очеред-
ного символа и коррекция ранее введенной части изображения (560). 13.3.6. Блок
вспомогательных процедур формульного редактора (565).
13.3.7. Блок эмуляции
набора формулы с клавиатуры (567).
13.4. Программа текстового редактора . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .
569
13.5. Программы геометрического и текст-формульного редакторов . .. . . . . . . . . . . . .
573

Г л а в а 14. Программа редактора программ . . . . . . . . . . . . . . . . . . . . . . . . . . .
576

Г л а в а 15. Программа отладчика ЛОСа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
591

15.1. Предварительные сведения об интерпретаторе ЛОСа . .. . . . . . . . . . .. . . . . . . . .
591
15.2. Серия операторов ”трассировка”
. .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .
595
15.3. Начало программы ”прерывание” . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .
600
15.4. Цикл обработки команд отладчика . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
606

Г л а в а 16. Интерпретатор ЛОСа . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .
618

16.1. Основные структуры данных интерпретатора . .. . . . . . . . . . . . . . . . . . . . . . . .
618
16.1.1. Хранение основных данных в оперативной памяти (618).
16.1.2. Хране-
ние программ (620).
16.1.3. Хранение вспомогательной информации в файлах
логической системы (623).
16.1.4. Вспомогательные файлы (626).
16.1.5. Вспо-
могательные массивы (627). 16.1.6. Обозначения массивов интерпретатора (629).
16.1.7. Основные регистры интерпретатора (629).
16.2. Преобразование программы ЛОСа в формат, используемый интерпретатором . .. . .
631
16.2.1. Переменные
и
логические
символы (631).
16.2.2. Непосредственно
реализуемые неперечисляющий оператор либо операторное выражение (631).
16.2.3. Отрицание
оператора (631).
16.2.4. Дизъюнкция
операторов (631).

Оглавление

16.2.5. Конъюнкция операторов (632).
16.2.6. Оператор ”альтернатива” (632).
16.2.7. Оператор
”длялюбого” (632).
16.2.8. Оператор
”существует” (632).
16.2.9. Операторное выражение ”вариант” (633). 16.2.10. Операторные выражения
”выписка”,
”перечисление”,
”суммавсех”
(633).
16.2.11. Программируемые
оператор
либо
операторное
выражение
(633).
16.2.12. Непосредственно
реализуемый
перечисляющий
оператор (633).
16.2.13. Операторы
перехода
”ветвь”, ”иначе” (634).
16.3. Общая схема функционирования интерпретатора . .. . . . . . . . . . . . . . . . . . . . .
634
16.3.1. Сканирование задачи (634).
16.3.2. Обработка текущего фрагмента про-
граммы (635).
16.3.3. Функции вызова фрагментов в зону программ (636).
16.3.4. Поиск свободного места и расчистка мусора в зоне задач (636).
16.4. Добавление нового оператора либо операторного выражения . .. . . . . . . . . . . . . .
637
16.5. Вспомогательные функции интерпретатора. .. . . . . . . . . . . . . . . . . .. . . . . . . . .
638
16.5.1. Функции, используемые для организации общих действий интерпретато-
ра (638). 16.5.2. Функции, используемые при реализации операторов ЛОСа (639).
16.5.3. Функции, используемые для перевода программы из формата зоны задач
в формат зоны программ и обратно (645). 16.5.4. Отладочные функции (646).
16.6. Отладка логической системы на уровне интерпретатора ЛОСа. .. . . . . . . . . . . . .
646

Г л а в а 17. Программы просмотра списков задач . . . . . . . . . . . . .. . . . . . . . . . . .
648

17.1. Просмотр списка задач из задачника. .. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .
648
17.2. Пошаговый просмотр решения . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .
682
17.2.1. Структура
данных
для
описания
текущего
шага
решения
(682).
17.2.2. Определение цепи обобщенных задач отладчиком ЛОСа (685). 17.2.3. Про-
смотр и редактирование цепи обобщенных задач (697).

Г л а в а 18. Программа редактора приемов . . . . . . . . . . . . . . . . . . . . . .. . . . . . .
714

18.1. Структуры данных, используемые для хранения приемов . .. . . . . . . .. . . . . . . . .
714
18.2. Обращение к редактору приемов . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
718
18.3. Прорисовка текущего приема . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
719
18.4. Обработчик команд редактора приемов . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . .
723
18.4.1. Переходы (723).
18.4.2. Просмотр окон приема (729).
18.4.3. Редактиро-
вание приема (734).
18.5. Программы редактора приемов, запускаемые из интерфейса оглавлений . .. . . . . .
754

Г л а в а 19. Компилятор ГЕНОЛОГа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
756

19.1. Общая архитектура компилятора . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .
756
19.1.1. Входной блок компилятора (756).
19.1.2. Компиляция приемов, приме-
няемых при сканировании задачи (757).
19.1.3. Компиляция приемов пакетных
операторов (759). 19.1.4. Компиляция приемов вывода теорем (759). 19.1.5. Ком-
пиляция приемов справочников (759).
19.2. Схема компиляции приема сканирования задачи . .. . . . . . . .. . . . . . . . . . . . . . .
760
19.2.1. Предварительное преобразование теоремы приема (760).
19.2.2. Выбор
точки привязки приема (763).
19.2.3. Создание программного блока и системы
установок на идентификацию (766).
19.3. Схема компиляции приема пакетного нормализатора . .. . . . . . . . . . .. . . . . . . . .
776
19.3.1. Предварительное преобразование теоремы приема (777). 19.3.2. Создание
начального отрезка программы (777). 19.3.3. Анализ заголовка приема (779).

Оглавление
9

19.4. Схема компиляции приема проверочного оператора . .. . . . . . . . . . . .. . . . . . . . .
786
19.4.1. Предварительное преобразование теоремы приема (786). 19.4.2. Создание
начального отрезка программы (787).
19.4.3. Ввод программного блока (790).
19.4.4. Компиляция идентифицирующей части приема и его фильтров (790).

19.5. Схема компиляции приема синтезатора . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
791
19.5.1. Предварительный анализ приема (792). 19.5.2. Создание начального отрез-
ка программы (792). 19.5.3. Ввод программного блока (793). 19.5.4. Компиляция
основной части программы приема (794).

19.6. Схема компиляции приема анализатора . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
794
19.6.1. Создание начального отрезка программы (795). 19.6.2. Ввод программного
блока (796). 19.6.3. Компиляция основной части программы приема (796).

19.7. Схема компиляции приема оператора фильтра . .. . . . . . . . . . . . . . . . . .. . . . . .
798
19.7.1. Предварительный анализ приема (798).
19.7.2. Ввод программного блока
и завершение компиляции (799).

19.8. Компиляция приемов вычислительных пакетов . .. . . . . . . . . . . . . . . . . . . . . . .
800

19.9. Информационные элементы программного блока . .. . . . . . . . . . . . . . . . . . . . . .
800
19.9.1. Идентификация теоремных переменных (800).
19.9.2. Идентификация
вхождений
(801).
19.9.3. Учет
посылок,
используемых
приемом
(802).
19.9.4. Списки переменных (803).
19.9.5. Антецеденты и указатели дополни-
тельной идентификации (803).
19.9.6. Идентификация функциональных пере-
менных (805).
19.9.7. Идентификация наборов (806).
19.9.8. Вычисления (807).
19.9.9. Особенности идентификации (807). 19.9.10. Нормализаторы приема (810).
19.9.11. Комментарии, изменяемые приемом (810). 19.9.12. Дополнительные пре-
образования (811). 19.9.13. Информация о задачах (811). 19.9.14. Разное (811).

19.10. Создание идентифицирующей части программы . .. . . . . . . . . . . . . . . . . . . . . .
812
19.10.1. Предварительные
преобразования (813).
19.10.2. Начало
основного
цикла идентификации (814).
19.10.3. Цикл просмотра установок
на иден-
тификацию (816).
19.10.4. Установка
на
идентификацию
”операнд” (816).
19.10.5. Установка на идентификацию ”корень” (857).
19.10.6. Установка на
идентификацию
”извлекается” (863).
19.10.7. Установка
на
идентификацию
”значения” (866).
19.10.8. Установка на идентификацию ”программа” (869).
19.10.9. Установка на идентификацию ”идентификатор” (875). 19.10.10. Установка
на идентификацию ”контекст” (883). 19.10.11. Проверка истинности антецедента
с помощью вспомогательной задачи либо общей проверочной процедуры (883).
19.10.12. Установка на идентификацию ”новаргумент” (885).
19.10.13. Установка
на идентификацию ”развертка” (886).
19.10.14. Установка на идентификацию
”транзитпереход” (892).
19.10.15. Установка на идентификацию ”группиров-
ка” (892).
19.10.16. Установка на идентификацию ”усм” (895).
19.10.17. Уста-
новка на идентификацию ”свертка” (898). 19.10.18. Установка на идентификацию
”теквхожд” (898).
19.10.19. Установка на идентификацию ”унификация” (899).
19.10.20. Установка на идентификацию ”тип” (900).
19.10.21. Установка на
идентификацию ”типзначения” (900).
19.10.22. Установка на идентификацию
”чертеж” (900).
19.10.23. Установка на идентификацию ”числоценка” (900).
19.10.24. Установка на идентификацию ”выч” (900).
19.10.25. Установка на
идентификацию ”вычисл” (901).
19.10.26. Установка на идентификацию ”рекур-
сия” (901). 19.10.27. Компиляция обращения к техническому анализатору (902).
19.10.28. Установка на идентификацию ”пересечподст” (904).
19.10.29. Действия
процедуры ”идентификатор” по исчерпании установок на идентификацию (904).
19.10.30. Процедура ”учетоперанда” (906).

19.11. Компиляция операторных выражений . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
914
19.11.1. Вычислительные форматы данных (915). 19.11.2. Особые случаи компи-
ляции (923). 19.11.3. Общий случай компиляции (924).

Оглавление

19.12. Компиляция теоремных термов. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
925
19.12.1. Развертка в дизъюнкцию квантора существования (926).
19.12.2. Учет
нормализаторов (926). 19.12.3. Случай однобуквенного терма (931). 19.12.4. Спе-
циальные случаи неоднобуквенного терма (933). 19.12.5. Общий случай компиля-
ции неоднобуквенного терма (941).
19.13. Предварительная обработка установок на нормализацию . .. . . . . . . . . . . . . . . .
943
19.13.1. Компиляция приема пакетного нормализатора (944). 19.13.2. Компиляция
приема, не относящегося к пакетному нормализатору (945).
19.14. Компиляция фильтров для приема сканирования задачи. .. . . . . . . . . . . . . . . . .
946
19.14.1. Учет уровней срабатывания приема (946). 19.14.2. Компиляция префикс-
ных фильтров приема (946). 19.14.3. Определение результирующего терма (947).
19.14.4. Основной цикл обработки фильтров (947).
19.14.5. Дополнительные
фильтры для приема ”связка” (948).
19.15. Процедура ”фильтр” . .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
948
19.16. Процедура ”вставкафильтра” . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
949
19.17. Компиляция фильтров и операторных выражений со связанными переменными . .
951
19.18. Компиляция преобразующей части приема сканирования задачи . .. . . . . . . . . . .
956
19.18.1. Предварительный учет указателей приема (956).
19.18.2. Компиляция
основного действия приема (962).
19.19. Завершающая обработка программы . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
973
19.19.1. Процедура ”вставкафрагментов” (973).
19.19.2. Процедура ”завершение-
программы” (973). 19.19.3. Процедура ”редакцияпрограммы” (974).
19.20. Запись программы приема в блок программ . .. . . .. . . . . . . . . . . . . . . . . . . . . .
981
19.20.1. Ввод ограничителя склейки программ (981).
19.20.2. Разрезание боль-
ших фрагментов (982).
19.20.3. Инициализация программы логического симво-
ла (982).
19.20.4. Случай приема сканирования задачи (983).
19.20.5. Слу-
чай приема проверочного оператора, синтезатора, либо пакета продукций (989).
19.20.6. Случай приема нормализатора либо анализатора (992).
19.21. Развитие компилятора ГЕНОЛОГа . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
994
19.21.1. Поиск в программе компилятора (994).
19.21.2. Трассировка процесса
компиляции (1005). 19.21.3. Пополнение языка новыми элементами (1016).

С п и с о к л и т е р а т у р ы . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1021

Введение

Прогресс в развитии вычислительной техники неоднократно приводил к активи-
зации исследований по искусственному интеллекту. Наиболее важными рубежами
здесь являются период первого появления электронных вычислительных машин и пе-
риод распространения персональных компьютеров. Вычислительная техника стала
широко доступной, а программирование приобрело массовый характер. Несмотря
на это, искусственный интеллект так и не появился, а первоначальный оптимизм
в отношении перспектив его создания стал постепенно вытесняться пессимизмом.
Успехи и неудачи в программировании определяются на сегодняшний день границей,
отделяющей те области, в которых имеются эффективные алгоритмы для решения
задач, от областей, для которых эти алгоритмы не созданы. К числу последних отно-
сятся, к сожалению, не только творческая деятельность, но даже такие «простейшие»
способности человека, как понимание естественного языка и изображений. Успехи
здесь пока достаточно скромны.
Вместе с тем, отсутствие простого общего алгоритма решения задач в какой-либо
из трудных для программирования областей, например, школьной геометрии, не
является препятствием для решения таких задач человеком. Хотя общего алгоритма
в учебниках и нет, но в каждом отдельном случае логика принятия решения вполне
поддается анализу и объяснению. Обучаясь на сотнях и тысячах примеров, постоянно
пополняя и корректируя свои умения, человек постепенно аккумулирует в себе
необходимый ему алгоритм, нигде не изложенный в явном виде. Чтобы получить
аналогичный алгоритм в компьютере, остается только следовать этому примеру.
Видимо, это и есть реальный способ создавать программы «там, где нет алгоритмов».
Если не овладеть таким искусством, то никакое, даже самое впечатляющее, развитие
вычислительной техники сколь-нибудь существенным образом положения дел с ис-
кусственным интеллектом не улучшит.
Алгоритмы, извлекаемые человеком из процесса обучения на примерах, сильно
отличаются от алгоритмов обычного программирования. Прежде всего, они почти
лишены циклов — на каждом шаге для решения задачи привлекаются какие-то новые
знания и приемы, зачастую из совершенно различных областей. Алгоритмы эти плохо
декомпозируются на блоки. Скорее, они представляют собой что-то типа векторного
поля приемов, в котором перемещается решаемая задача и которое создается путем
длительной трудоемкой дрессировки. Срабатывание каждого приема продвигает за-
дачу на один шаг вперед по ее траектории. До тех пор, пока не получено достаточно
полной коллекции приемов, обеспечивающей с большой вероятностью «цепную ре-
акцию» процесса решения задачи, эти алгоритмы практически бесполезны. А так
как обычно критический минимум достаточно велик и насчитывает многие тысячи
элементов, то возникает серьезный психологический барьер — у программиста после
проработки первых сотен задач может возникнуть впечатление, что проект безнаде-
жен и его следует бросить.
Еще одно отличие алгоритмов рассуждений от алгоритмов вычислений связано со
способом кодирования информации. Вычислительная программа обычно использует
технические структуры данных, семантика которых остается за кадром, так как
непосредственно при вычислениях не нужна. Приемы интеллектуальной системы
анализируют задачу независимо друг от друга, и чтобы они могли понимать текущий

Введение

контекст, необходимо сохранить всю его семантику, используя для представления
данных универсальный логический язык. Решение трудных для алгоритмизации
задач — это почти всегда процесс преобразования логических структур данных или,
иными словами, логический процесс.
История развития математики тесно связана с изучением процессов различных
типов. Многие разделы классической «непрерывной» математики, и в первую очередь
теория дифференциальных уравнений, возникли для изучения физических процес-
сов. Изучение процессов обработки дискретной информации в электронике привело
к появлению теории автоматов и других разделов математической кибернетики. К со-
жалению, логические процессы оказались настолько сложны, что попытки изучения
их математическими методами так и не привели к созданию эффективных РЕША-
ТЕЛЕЙ в сколь-нибудь нетривиальных областях. Поэтому единственным подходом
к созданию науки о логических процессах на сегодняшний день остается компьютер-
ное моделирование, т. е. указанная выше дрессировка «логических векторных полей»
на потоках обучающих примеров.
Создание больших РЕШАТЕЛЕЙ вручную чрезвычайно трудоемко, так как тре-
бует постоянной регулировки взаимодействий в многотысячной системе активных
элементов. Такие РЕШАТЕЛИ, как правило, изначально не очень качественные
и требуют последующей, еще более трудоемкой оптимизации. Однако они дают
материал, позволяющий начать исследования по автоматизации синтеза приемов
и саморазвитию «логических векторных полей», без которого невозможно было бы
создание подлинно интеллектуальной системы. Объектом изучения здесь являются
процессы синтеза алгоритмов по теоремам и процессы автоматического развития
теорий, ориентированного на синтез алгоритмов. Это — еще одна разновидность
логических процессов.
Данная монография описывает многолетний опыт компьютерного моделирования
логических процессов, в результате которого возникла развитая технология обучения
РЕШАТЕЛЕЙ, разработанных автором и собранных в пакет прикладных программ
«Логическая система “Искра”». Обучение компьютерной системы предпринималось
в различных областях математики и в элементарной физике. Моделировались также
логические процессы, возникающие при анализе текстов естественного языка, анали-
зе изображений и принятии решений в игровых ситуациях. Всего было проработано
около 9 тыс. задач и создано около 25 тыс. приемов. Поведение системы в тех
областях, где был накоплен необходимый критический минимум приемов, выглядит
вполне целесообразным и доказывает правильность предлагаемого подхода. Ход рас-
суждений демонстрируется по шагам, причем во многих разделах уровень сложности
решаемых задач достаточно серьезен.
Материал монографии разбит на три книги. Данная, первая книга посвящена
общему описанию архитектуры компьютерной системы и языкам программирования,
созданным для ускорения процесса обучения. Эти языки, ЛОС (Логический Описа-
тель Ситуаций) и ГЕНОЛ ´ОГ (ГЕНетический язык ЛОГического программирования),
подняли обучение РЕШАТЕЛЕЙ практически до уровня формулировки математиче-
ских теорем. Первый из них — чуть выше уровня ПРОЛОГа, второй — относится
к первому примерно так же, как ПРОЛОГ к ассемблеру. Планируется выпуск второй
и третьей книг. Вторая книга будет посвящена описанию собственно РЕШАТЕЛЕЙ;
одновременно она может рассматриваться как курс программирования на ГЕНОЛОГе.
Наконец, третья книга включит в себя материал, связанный с вопросами автомати-
ческого развития РЕШАТЕЛЕЙ и автоматизации теоретических исследований.

Введение
13

К книге прилагается диск, на котором находится текущая версия системы.
Содержимое первой книги позволяет научиться пользоваться РЕШАТЕЛЕМ в тех
разделах, где он достаточно «укомплектован» приемами.
Однако система никоим образом не претендует на роль коммерческой программы.
Скорее, она представляет собой попытку создания среды программирования для
обучения интеллектуальной системы, интегрирующей в себе знания из множества
различных областей, способной к проведению самостоятельных исследований и са-
моразвитию. Архитектура системы допускает увеличение ее сегодняшних размеров
(около 60 Мб) в тысячи раз без сколь-нибудь значимого замедления для уже
освоенных разделов. Совместная работа над развитием универсального интеллекту-
ального комплекса представляется единственно возможным способом объединения
усилий многих исследователей в создании науки о логических процессах. Только
таким образом можно обеспечить появление единой логической формализации по-
нятий и добиться разумного взаимодействия приемов в рамках общего «логического
векторного поля». Получение широкого спектра основанных на единой технологии
РЕШАТЕЛЕЙ является необходимой предпосылкой для проведения исследований по
автоматическому их синтезу.
Обучение логической системы требует постоянного развития программ интер-
фейсов и компилятора. Вторая половина книги (начиная с гл. 13) содержит доста-
точно подробное описание этих программ. Она будет необходима тем, кто захочет
проводить самостоятельные исследования по моделированию логических процессов.
При чтении этой части книги нужно иметь перед собой соответствующий раздел
программы, отображаемый на экране компьютера. Представленный здесь материал
имеет чисто справочный характер, и для начала работы вполне достаточно извлечь
из него лишь общее представление об архитектуре программ.
Проработав сравнительно полно ряд разделов элементарной математики, автор
взялся за развитие РЕШАТЕЛЕЙ в целом ряде новых разделов, не собираясь своими
силами доводить их до конца, а лишь с целью преодолеть стартовые трудности
и предоставить тем, кто захотел бы продолжить исследование логических процессов,
возможно более благоприятные исходные позиции.
Как и всякая большая программа, к тому же созданная единственным программи-
стом, РЕШАТЕЛЬ, вероятно, имеет множество недостатков и ошибок. Автор заранее
приносит за них свои извинения. Однако, будучи первой попыткой в развитии новых
технологий, этот РЕШАТЕЛЬ все же заслуживает определенного снисхождения.
В заключение автор выражает искреннюю благодарность Валерию Борисовичу
Кудрявцеву, поддержка которого сделала возможным проведение данного исследова-
ния. Автор благодарен также П. А. Пантелееву, оказавшему помощь при подготовке
рукописи.
Книга печатается при финансовой поддержке Российского фонда фундаменталь-
ных исследований (грант № 08-01-07074).

Г л а в а 1

ОБЩИЕ ЗАМЕЧАНИЯ О ЛОГИЧЕСКИХ ПРОЦЕССАХ

И ИХ МОДЕЛИРОВАНИИ

1. Логические процессы играют исключительно важную роль в поведении любой
интеллектуальной системы. Они необходимы для распознавания зрительных либо
звуковых образов, для управления динамикой системы, для понимания языка, пла-
нирования действий, анализа потока событий, решения технических и теоретических
задач. Хотя основной объем обработки информации во многих случаях берут на
себя средства автоматики, использующие не логические, а «технические» структуры
данных, логика играет роль диспетчера, организующего и контролирующего рабо-
ту этой автоматики, а в необходимых случаях обеспечивает ее развитие. В тех
случаях, когда для решения задачи имеется заранее выработанный план действий,
обычно логический вывод не требуется — вместо него создается специализирован-
ный вычислительный алгоритм. Это обычный и хорошо известный путь развития
программирования, на котором создаются различные системы численного модели-
рования, компиляции и оптимизации технических проектов, управления сложными
системами и т. п. Потребность в логических процессах появляется лишь при отсут-
ствии известного заранее плана действий. Тогда планирование действий происходит
непосредственно во время решения задачи, причем для обеспечения возможности
нахождения приемлемых вариантов система должна располагать достаточно обшир-
ным и разнообразным запасом знаний. Использование того или иного элемента
этого запаса знаний заранее непредсказуемо — задача из одной предметной области
может потребовать для своего решения весьма удаленных от этой области идей.
По этой причине вряд ли возможно создавать подлинно интеллектуальные системы
для ограниченных классов задач — например, только для распознавания изобра-
жений, или только для понимания естественного языка или только для написания
программ, синтеза «чипов» и т. д. Чтобы достаточно эффективно действовать хотя
бы в одной из таких областей, необходимо заложить в интеллектуальную систему
универсальное «фундаментальное» образование, как это и происходит обычно при
обучении человека. Уже один только количественный аспект этой нерешенной на
сегодняшний день задачи далеко выводит ее за рамки трудностей традиционного
программирования. Заметим, что даже в случае обучения человека, с отлаженной
и оптимизированной веками системой образования, процесс подготовки полноценного
специалиста (с учетом весьма существенного дошкольного периода) занимает более
20 лет.
Попытки исследования логических процессов математическими методами привели
к появлению и развитию такой науки, как математическая логика. В ее рамках
удалось дать точные определения фундаментальным понятиям логического языка,
аксиоматической теории, формального доказательства, алгоритма решения задачи,
сложности вычислительной процедуры. Был накоплен значительный запас математи-
ческих результатов, характеризующих общие свойства этих понятий. Возникли новые
представления о математической строгости и формализации теорий, которые привели
к переизложению многих разделов математики в виде формальных дедуктивных
систем. Изучение общих свойств этих формальных теорий методами математиче-
ской логики позволило решить ряд важных общематематических проблем: доказать

Гл. 1. Общие замечания о логических процессах и их моделировании
15

независимость континуум-гипотезы; установить алгоритмическую неразрешимость
диофантовых уравнений и др. Однако основные продвижения математической логики
оказались связаны не столько с логической «динамикой», сколько с логической «ста-
тикой». Несмотря на интенсивные исследования в области процедур автоматического
доказательства теорем, не удалось не только предложить эффективно работающие
общие процедуры решения задач, но даже найти общие принципы, на основе которых
такие процедуры могли бы быть созданы. Основной проблемой, с которой здесь
пришлось столкнуться, явилась проблема трудоемкости поиска решения задачи по
деревьям прямого либо обратного логического вывода, экспоненциально возраста-
ющей с ростом глубины поиска. Всевозможные результаты по отсечению ветвей
рассматриваемого дерева для уменьшения объема перебора и различные эвристиче-
ские общие принципы упорядочения перебора не изменили ситуации сколь-нибудь
ощутимым образом.
2. В сложившейся ситуации, когда поиски математических методов, позволяющих
создавать эффективные решатели задач, фактически зашли в тупик, единственной
возможностью создания таких решателей становится компьютерное моделирование
логики рассуждений человека. Компьютерная модель здесь должна сыграть роль
«микроскопа» для изучения процессов поиска решения и самообучения, с помощью
которого были бы выявлены фундаментальные принципы их организации. Возможно,
что по мере развития такой «экспериментальной» теории логических процессов вновь
окажутся востребованы и математические методы исследования.
Компьютерное моделирование логических процессов естественно начинать с мо-
делирования автоматики, управляющей ходом рассуждений, оставляя пока в сто-
роне значительно более сложные процессы саморазвития этой автоматики. Чтобы
разрабатывать механизмы самообучения и самопроектирования, необходимо прежде
всего получить определенный запас созданных вручную «эталонных» алгоритмиче-
ских конструкций, моделирующих процессы решения задач. По-видимому, без та-
ких «образцов для подражания» трудно определить необходимый для эффективного
функционирования запас архитектурных стандартов, который могла бы использовать
процедура самопрограммирования системы. Многократно предпринимавшиеся ранее
попытки создания саморазвивающихся интеллектуальных систем, основанных на тех
или иных простых общих принципах, без анализа реальной логической автоматики
во всей ее сложности и разнообразии, оказывались вполне бесплодными.
В самых общих чертах, процесс расшифровки логической автоматики, обес-
печивающей решение задач в некоторой предметной области, можно представить
происходящим по следующей схеме. Рассматривается некоторая обучающая последо-
вательность задач в этой области, решение которых известно эксперту, осуществляю-
щему развитие компьютерной модели. Предпринимается анализ траектории решения
очередной задачи из выбранной последовательности. Если эта задача не представляет
собой простейший тест, для которого имеется заранее известный стандартный план
действий, то процесс ее решения складывается из отдельных этапов, состоящих
из локального планирования и реализации выработанного плана действий. Каждый
такой этап локального планирования анализируется, и для него предлагается некото-
рый гипотетический алгоритм, приводящий в рассматриваемой ситуации к тому же
результату. Эти алгоритмы накапливаются в компьютерной модели, так что в новой
задаче некоторые из них могут сработать и предложить свою версию развития
решения. Каждое такое срабатывание анализируется на предмет целесообразности,
и в решающие правила алгоритма локального планирования вводятся необходимые
коррективы. Эта процедура повторяется для многих сотен задач предметной обла-
сти — до тех пор, пока сложившаяся мозаика алгоритмов локального планирования
действий не обнаружит достаточно устойчивого и эффективного поведения. В целом,

Гл. 1. Общие замечания о логических процессах и их моделировании

процесс напоминает обучение нейросистемы методом «поощрений и наказаний»;
отличие состоит лишь в более сложной процедуре коррекции, которая не сводится
к изменению каких-либо числовых параметров, как у нейрокомпьютера, а требует
привлечения логики для очередного перепроектирования алгоритмов планирования.
Многообразие алгоритмов локального планирования создает своего рода «логи-
ческое векторное поле», в котором перемещается решаемая задача — от исходной
формулировки к ответу. Разумеется, это лишь упрощенная аналогия; отдельные шаги
в таком перемещении могут представлять собой целые иерархии вложенных логиче-
ских процессов с различными циклами ограниченного поиска и отбора. Однако она
отражает главное обстоятельство: по завершении реализации каждого локального
плана предпринимается независимое рассмотрение всей текущей ситуации заново
для выработки следующего плана. К сожалению, на сегодняшний день не известно
другого способа создания эффективных «логических векторных полей» автоматиче-
ского решения задач, кроме весьма трудоемкого процесса их дрессировки на тысячах
обучающих примеров.
Так как алгоритмы локального планирования (для краткости далее условимся
называть такие алгоритмы приемами решения задач) берут всю инициативу на себя,
не имея какого-либо стоящего над ними управляющего центра (ведь никто, кроме
конкретного приема, и не располагает достаточной для принятия решения в области
его компетенции информацией), то особо важную роль приобретает точный учет вза-
имодействий различных приемов в цепи решения задачи. Трудоемкость этого учета,
в среднем, должна быть пропорциональна квадрату числа приемов, по крайней мере,
в той предметной области, где проводится обучение. Разумеется, адекватно большим
должен быть и обучающий материал — иначе качество работы решателя будет весь-
ма посредственным. По-видимому, единственной возможностью преодоления этого
недостатка логической автоматики (как и вообще любой автоматики, ограниченной
определенными разумными рамками) является развитие средств ее автоматическо-
го пополнения и оптимизации, которые подключались бы при решении задачи по
мере надобности. Анализ многих и многих математических задач так называемого
«нестандартного характера» показывает, что выход за рамки накопленных запасов
приемов (обычно связанный с попыткой скомбинировать несколько известных теорем
и извлечь из них новую идею) является, в общем, обыденным явлением и даже по
своей трудоемкости иногда вполне сопоставим с работой автоматики стандартных
приемов. Впрочем, автоматика мышления в поведении любых интеллектуальных
систем играет огромную роль, и лишь в ситуациях «аварийного» типа включаются
дополняющие ее средства более высоких уровней.
3. Описанная выше общая схема моделирования логической автоматики была
реализована на примере процессов решения математических задач. Причины, по
которым на первом этапе была рассмотрена математика, вполне понятны: именно
в ней при решении задач возникают наиболее сложные и разнообразные логические
процессы, причем имеются огромные запасы обучающего материала. В последнее
время начато моделирование логических процессов и в ряде нематематических об-
ластей. Было проработано свыше 9 тыс. задач из таких разделов, как элементарные
алгебра и геометрия, математический анализ, аналитическая геометрия, линейная
алгебра, дифференциальные уравнения, теория вероятностей, комплексный анализ,
элементарная физика, школьные текстовые задачи (с синтаксическим и семантиче-
ским анализом текста). На основе этого обучающего материала сформирована база
приемов решателя задач, насчитывающая в настоящее время более 25 тыс. приемов.
Фактически, возникла мощная система символьной компьютерной математики нового
типа, позволяющая не только получать ответы, но и прослеживать ход решения по
шагам, а при необходимости вмешиваться в процесс решения.

Гл. 1. Общие замечания о логических процессах и их моделировании
17

В отличие от традиционных систем компьютерной математики, где накаплива-
лись тысячи функций для пользователя, который должен был вручную находить
их в каталоге системы и применять к текущей задаче, новая система накапливает
тысячи приемов, которые самостоятельно анализируют задачу и принимают решение
о выполнении преобразований. Пользователь здесь может вообще не интересоваться
содержимым базы приемов. Разумеется, это более высокая степень автоматизации,
и, как следствие нового подхода, системе становятся доступны значительно более
сложные задачи. Преимущества нового подхода становятся особенно заметны в тех
разделах, где велика роль логического вывода. В элементарной алгебре — это
решение уравнений и неравенств с параметрами; в математическом анализе — каче-
ственное исследование функций с помощью пределов и производных, исследование
сходимости рядов, вычисление кратных интегралов и применение их для нахождения
площадей и объемов. Разумеется, наиболее интересными с точки зрения модели-
рования логических процессов оказались элементарная и аналитическая геометрии.
В распространенных системах компьютерной математики эти разделы представлены
совсем слабо, причем элементарная геометрия по существу отсутствует, а анали-
тическая связана лишь с выполнением стандартных операций явно одношагового
характера.
Работа над моделированием процессов решения математических задач потре-
бовала создания целого технологического комплекса, позволившего существенно
приблизить язык для программирования приемов к языку для формулировки теорем
предметной области. Фактически, прием задается как теорема, снабженная системой
указателей для компилятора, генерирующего на основе этой теоремы программу при-
ема. Задачей компилятора является синтез такой программы, которая была бы спо-
собна усматривать возможность применения теоремы даже в неявных, «замаскиро-
ванных» ситуациях, оценивать целесообразность такого применения и осуществлять
его. Программирование приемов имеет рекурсивный характер: в описании приема
допускаются обращения к всевозможным вспомогательным процедурам и задачам,
применяемым к фрагментам теоремы. Это означает, что при реализации приема
может быть использована не только та теорема, на которой он основан, но и сотни
других теорем, востребованных его вспомогательными операторами. Использование
стандартной математической записи для изображения теоремы приема, а также со-
провождение геометрических теорем чертежами позволили приблизить наглядность
описания приема к наглядности текста решаемой задачи. Сочетание этой наглядности
с развитием системы семантической трассировки процесса решения, выдающей на
экран подробные объяснения выполняемых преобразований, значительно уменьшило
трудоемкость процесса анализа решений и коррекции приемов. Вместе с тем, новый
язык для записи приемов не просто создает определенные преимущества для процес-
са обучения решателя. В действительности его приближенность к логическому языку
предметной области ориентирована в первую очередь на последующие исследования
в области автоматического синтеза приемов; на весь круг проблем, относящихся
к пограничному слою между логикой и алгоритмами.
Фактически, развитие техники обучения сделало доступным продолжение обуче-
ния системы ее пользователям — так же, как и в случае обычных систем компью-
терной математики, которые предоставляют пользователю средства для программи-
рования новых функций. Отличие здесь заключается в том, что вместо мало при-
способленных для логических процессов традиционных средств процедурного про-
граммирования развит мощный комплекс программирования продукционного. Чтобы
сравнить уровень используемого языка с уровнем известного языка логического
программирования ПРОЛОГ, заметим лишь, что программы на промежуточном языке
уровня ПРОЛОГ возникают как результат компиляции описания приема; естественно,

Гл. 1. Общие замечания о логических процессах и их моделировании

они значительно больше и, в сравнении с первоначальным описанием, совершенно
«нечитабельны».
4. Собственно работе по моделированию логических процессов в математике
предшествовало решение ряда важных технических проблем, определившее общую
архитектуру компьютерной системы. Прежде всего, необходимо было выбрать логи-
ческий язык для представления задач. Разумеется, для адекватного моделирования
процессов решения такой язык должен быть возможно более приближен к «есте-
ственному» математическому языку. Языки математической логики, создававшиеся
для теоретического исследования свойств аксиоматических теорий, обычно вводи-
лись как можно менее избыточным образом — для упрощения связанных с ними
формулировок теорем и доказательств этих теорем. Использование таких языков
в решателе привело бы к неоправданному усложнению формулировок и повлекло бы
существенные расхождения между моделью и моделируемым процессом. Фактически
оказалось, что несмотря на огромное количество работ в математической логике,
посвященных формализации различных разделов математики, никакой практически
пригодной формализации «сквозного» характера, сохраняющей все введенные для
удобства логических вычислений в обычной математической практике условности,
создано не было. Поэтому для решателя пришлось создавать свой собственный
логический язык, пополняемый по мере проработки новых предметных областей.
Одним из важных наблюдений, которые здесь были сделаны, оказался определенный
конфликт между требованиями к языку, предъявляемыми к нему традиционными
для формальной логики соображениями логической аккуратности, с одной стороны,
и соображениями вычислительной целесообразности — с другой. Аккуратная логиче-
ская запись иногда становится избыточно громоздкой, и в определенных контекстах
ее можно заменить упрощенными суррогатами, достаточными для корректных вы-
числений. Возникло, таким образом, явление «контекстной семантики» языка, когда
смысл того или иного утверждения задачи определяется лишь в контексте всей
задачи в целом. Простейшим примером такого рода является обычное использование
в математическом анализе утверждений вида f(x) = O(g(x)), для понимания смысла
которых в контексте должно содержаться что-нибудь вроде x → 0.
Учет контекста при обработке логических структур данных позволяет вводить
в язык различного рода нечеткие понятия, что часто бывает необходимо в нема-
тематических областях. Для уточнения их смысла в конкретной ситуации можно
обращаться к сопровождающей информации — как логической, так и технической
(например, анализировать изображения, протоколы и т. п.). Разумеется, какие-либо
формальные аксиоматические теории для таких понятий будут отсутствовать, од-
нако в процессе «дрессировки» системы на обучающем материале можно вырабо-
тать достаточно хорошие алгоритмические правила правдоподобных рассуждений,
аппроксимирующие действия эксперта. Таким образом, созданный аппарат обуче-
ния баз приемов никоим образом не ограничен рамками хорошо формализованных
предметных областей. Начатый при рассмотрении математических задач процесс
создания некоторого всеобъемлющего логического языка, используемого решателем,
предполагает продолжение и на нематематические области, включающие нечеткие
понятия и нечеткие рассуждения. Для работы с нечеткой логикой, по-видимому,
потребуются адаптивные алгоритмические конструкции, компенсирующие нечеткость
понятий аккуратным учетом контекста и накапливающие «четкие» аппроксимации
нечетких понятий в виде сложных логических описаний образов, стоящих за такими
понятиями. Заметим, наконец, что работа над указанной выше широкой логической
формализацией с развитием многообразия сопутствующих приемов совершенно необ-
ходима для создания системы, способной адекватно понимать естественные языки.