Достоверный и правдоподобный вывод в интеллектуальных системах

Вагин В.Н.

Головина Е.Ю.

Загорянская А.А.

Фомина М.В.

Достоверный и

правдоподобный

вывод в

интеллектуальных

систем ах

МОСКВА

ФИЗМАТЛИТ ®

УДК 519.816
ББК 32.81
Д 70

А в т о р с к и й к о л л е к т и в :
В а г и н В. Н., Го л о в и н а Е. Ю., З а г о р я н с к а я А. А., Ф о м и н а М. В.

Достоверный и правдоподобный вывод в интеллектуальных системах / Под ред. В.Н. Вагина, Д.А. Поспелова. — 2-е изд., испр. и доп. —
М.: ФИЗМАТЛИТ, 2008. — 712 с. — ISBN 978-5-9221-0962-8.

Рассматриваются методы достоверного (дедуктивного) и правдоподобного
(абдуктивного, индуктивного) выводов в интеллектуальных системах различного назначения. Приводятся методы дедуктивного вывода на графовых структурах. Описываются как классические, так и немонотонные модальные логики:
логики убеждения и знания, немонотонные логики Мак-Дермотта и Дойла,
автоэпистемические логики Мура, логики умолчания Рейтера. Приводятся
основы теории аргументации и методы абдуктивного вывода. Рассматриваются
базовые принципы построения систем обучения и принятия решений и даются
задачи обучения «без учителя» и «с учителем». Излагаются индуктивные
методы для случая с неполной информацией и методы теории приближенных
множеств. Во 2-е издание добавлены главы об исчислении высказываний и об
исчислении предикатов первого порядка, а также о работе с реальными «зашумленными» базами данных в задаче индуктивного формирования понятий.
Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов вузов, обучающихся по направлениям
«Прикладная математика и информатика», «Информатика и вычислительная
техника» и специальностям «Прикладная информатика» (по направлениям)
и «Прикладная математика и информатика».

Рецензенты: Э. В. Попов, д.т.н., профессор, зам. директора по науке РосНИИ ИТ и АП, Г. С. Плесневич, к.ф.-м.н., профессор МАТИ — Российского
государственного технологического университета им. К. Э. Циолковского.

ISBN 978-5-9221-0962-8

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

c⃝ Коллектив авторов, 2008

ОГЛАВЛЕНИЕ

Предисловие ко второму изданию . .. . . . . . . . . . . . . . . . . . . . . . . . . .
10
Предисловие . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .
13

I.
ДОСТОВЕРНЫЙ ВЫВОД

Г л а в а 1.
Формальные системы. . . . . . . . . . . . . . . . . . . . . . . . . .
24
1.1. Понятие формальной системы . .. . . . . . . . . . . . . . . . . . . . . . . .
24
1.2. Исчисление высказываний как формальная система. .. . . . . . . . . .
28
1.3. Исчисление предикатов первого порядка как формальная система
31
1.4. Проблема разрешимости . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
37

Г л а в а 2.
Автоматическое доказательство теорем . . . . . . . . . .. . . .
42
2.1. Нормальные и стандартные формы . .. . . . . . . . . . . . . . . . . . . . .
43
2.2. Логические следствия. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
2.3. Процедура вывода Эрбрана . .. . . . . . . . . . . . . . . . . . . . . . . . . .
55
2.4. Принцип резолюции . .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
58
2.5. Линейная резолюция . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
2.6. Вывод в языке Пролог . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
2.6.1. SLD-резолюция (70).
2.6.2. Стратегии
поиска в языке
Пролог (74).
2.6.3. Предположение о замкнутости мира (77).
2.6.4. Синтаксис и семантика языка Пролог (78).
2.6.5. Реализация на языке Пролог моделей представления знаний и механизмов
вывода на них (84).

Г л а в а 3.
Вывод на графе связей. . . . . . . . . . . . . . . . . . . . . . . . .
96
3.1. Последовательная процедура доказательства методом графа связей
97
3.2. Стратегии поиска в графе связей . .. .. . . . . . . . . . . . . . . . . . . . .
100
3.3. Достоинства процедуры дедуктивного вывода на графе связей. .. . .
102
3.4. Параллельный вывод на графе связей . .. . . . . . . . . . . . . . . . . . .
103
3.4.1. Метод OR-параллельной резолюции (104).
3.4.2. DCDPпараллельный вывод (105).
3.4.3. AND-параллельная резолюция (108).
3.5. Модификация процедур параллельного вывода . .. . . . . . . . . . . . .
111

Оглавление

3.5.1.
Принципы
создания
эвристической
функции
(111).
3.5.2. Эвристическая функция H1 (112).
3.5.3. Применение эвристической функции H1 при решении задачи «Стимроллер» (115).
3.6. Сравнение эффективности . .. . . . . . . . . . . . . . . . . . . . . . . . . . .
118
3.7. Система параллельного вывода PIS (Parallel Inference System) на
графе связей . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
121
3.7.1. Автоматический выбор параллельных методов вывода (122).
3.7.2. Математический препроцессор (122).
3.7.3. Методы ускорения и анализ результатов для задачи о N ферзях (125). 3.7.4. Полученные результаты (128).

Г л а в а 4.
Вывод на графе дизъюнктов. . . . . . . . . . . . . . . . . . . . .
129
4.1. Типы параллелизма в дедуктивном выводе . .. . . . . . . .. . . . . . . . .
129
4.2. Последовательный алгоритм вывода на раскрашенных графах дизъюнктов. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
132
4.3. Параллелизм в дедуктивном выводе на C-графах. .. . . . . . . . . . . .
137
4.4. Сравнение эффективности процедур дедуктивного вывода . .. . . . .
146

Г л а в а 5.
Вывод на аналитических таблицах . . . . . . . . . . . . . . . .
149
5.1. Метод аналитических таблиц для логики высказываний. .. . . . . . .
149
5.2. Метод аналитических таблиц для логики предикатов первого порядка. .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
156
5.3. Метод аналитических таблиц в логическом программировании . .. .
165
5.3.1. Реализация метода аналитических таблиц для логики высказываний на языке Пролог (165).
5.3.2. Реализация метода аналитических таблиц для логики предикатов 1-го порядка (171).

Г л а в а 6.
Вывод на иерархических структурах . . . . . . . . . . . . . . .
195
6.1. Многоуровневая упорядоченно-сортная алгебра. .. . . . . . . . . . . . .
195
6.1.1. Необходимость разработки механизмов вывода на иерархических структурах (195).
6.1.2. Введение в многоуровневую алгебру (197).
6.1.3. Моделирование подтипов и наследования (198).
6.1.4. Описание параметрического полиморфизма аппаратом двухуровневой алгебры (199).
6.2. Многоуровневая логика как язык представления знаний в интеллектуальных системах . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
202
6.2.1. Способы задания иерархических структур в многоуровневой логике (202).
6.2.2. Синтаксис многоуровневой логики (206).
6.2.3. Описание двух видов иерархической абстракции и иерархической структуры множеством правильно построенных формул
многоуровневой логики (207).
6.2.4. Логический вывод в многоуровневой логике (211).
6.3. Система моделирования проблемной области «Инфолог». .. . . . . . .
223
6.3.1. Назначение
и
структура
системы
«Инфолог»
(223).
6.3.2. Концептуальный язык описания сложноструктурированной
проблемной области (226).
6.3.3. Реализация системы «Инфолог» (229).

Оглавление
5

II.
АРГУМЕНТАЦИЯ И АБДУКЦИЯ

Г л а в а 7.
Данные и знания в интеллектуальных системах . . . . . . .
231
7.1. Характерные особенности знания . .. . . . . . . . . . . . . . . . . . . . . .
231
7.2. Знание как обоснованное истинное убеждение . .. . . . . . . . . . . . .
240
7.3. Не-факторы знания . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
247
7.4. Зачем нужны нетрадиционные логики? . .. . . . . . . . . . . . . . . . . .
254

Г л а в а 8.
Монотонные классические модальные логики . . . . . . . .
260
8.1. Исчисление предикатов первого порядка как основа построения
модальной логики . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
260
8.2. Вспомогательная логика как основа перехода к модальному исчислению высказываний . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
262
8.3. Постулаты, основные теоремы и правила модального исчисления
высказываний . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
264
8.4. Система S1 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
266
8.5. Система S4 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
276
8.6. Система S5 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .
280
8.7. Семантика возможных миров Крипке . .. . . . . . . . . . . . . . . . . . .
280

Г л а в а 9.
Немонотонные модальные логики . . . . . . . . . . . . . . . . .
286
9.1. Логики убеждения и знания . .. . . . . . . . . . . . . . . . . . . . . . . . .
286
9.2. Немонотонные логики Мак-Дермотта и Дойла . .. . . . . . . . . . . . .
291
9.3. Автоэпистемические логики. .. . . . . . . . . . . . . . . . .. . . . . . . . . .
297
9.4. Логики умолчаний . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
305
9.5. Системы поддержки истинности . .. . . . . . . . . . . . . . . . . . . . . . .
316
9.5.1. Системы поддержки истинности, основанные на обоснованиях (318). 9.5.2. Системы поддержки истинности, основанные на
предположениях (320).

Г л а в а 10.
Немонотонные логики в логическом программировании
324
10.1. Семантика логических программ: краткий обзор . .. . . . . . . . . . . .
326
10.1.1. Нормальные логические программы (326).
10.1.2. Расширенные логические программы (333).
10.1.3. Зачем нужна новая
семантика для расширенных программ? (339).
10.2. WFSX — фундированная семантика для расширенных логических
программ . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .
340
10.2.1. Интерпретации
и
модели
(340).
10.2.2. Определение
WFSX
(342).
10.2.3. Существование
семантики
(346).
10.2.4. Нисходящие процедуры вывода для WFSX (347).
10.3. Работа с противоречиями . .. . . . . . . . . . . . . . . . . . . . . . . . . . .
357
10.3.1. Удаление
противоречий (360).
10.3.2. Паранепротиворечивая
WFSX (361).
10.3.3. Декларативные
ревизии (364).
10.3.4. Поддержка и устранение противоречий (371).

Оглавление

10.4. WFSX, семантика логических программ с двумя отрицаниями и
автоэпистемическая логика . .. . . . . . . . . . . . . . . . . . . . . . . . . .
376
10.4.1. Общая семантика для программ с отрицаниями двух видов (376). 10.4.2. Автоэпистемические логики для WFSX (389).
10.5. WFSX и логика умолчаний . .. . . . . . . . . . . . . . . . . . . . . . . . . .
400
10.5.1. Язык умолчаний (401).
10.5.2. Некоторые необходимые
принципы для теорий умолчаний (404).
10.5.3. Ω-теория умолчаний (407).
10.5.4. Сравнение с семантикой Рейтера (411).
10.5.5. Сравнение со стационарной семантикой умолчаний (412).
10.5.6. Связь семантики теории умолчаний и логических программ
с явным отрицанием (413).
10.5.7. Определение WFSX с помощью Γ (414).

Г л а в а 11.
Системы аргументации и абдуктивный вывод. . . . . . . .
417
11.1. Системы пересматриваемой аргументации . .. . . . . . . . . . . . . . . .
418
11.1.1. Основы теории аргументации (418).
11.1.2. Обзор систем
аргументации (433).
11.2. Организация абдуктивного вывода . .. . . . . . . . . .. . . . . . . . . . . .
440
11.2.1. Понятие абдуктивного вывода (440).
11.2.2. Подходы к
характеризации абдукции (443).
11.2.3. Подходы к вычислению
абдуктивных объяснений (451).
11.2.4. Метод вероятностных абдуктивных рассуждений в сложноструктурированных проблемных
областях (460).
11.3. Абдукция и аргументация в логическом программировании. .. . . . .
475
11.3.1. Аргументационная семантика логических программ и ее вычисление (475).
11.3.2. Роль аргументации в организации абдуктивного вывода (488).

III.
ИНДУКЦИЯ И ОБОБЩЕНИЕ

Г л а в а 12.
Базовые принципы построения систем обучения и принятия решений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
495
12.1. Системы поддержки принятия решений . .. . . . . . . . . . . . . . . . . .
497
12.2. Задачи извлечения знаний из баз данных . .. . . . . . . . . . . . . . . .
502
12.3. Способы представления исходной информации в интеллектуальных
системах . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
509
12.4. Структурно-логические методы обобщения. .. . . . . . . . . . . . . . . .
514

Г л а в а 13.
Задача обучения «без учителя» . . . . . . . . . . . . . . . . . .
524
13.1. Алгоритм, основанный на понятии порогового расстояния . .. . . . .
525
13.2. Алгоритм MAXMIN. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
527
13.3. Алгоритм «K средних» . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . .
531
13.4. Распознавание с использованием решающих функций . .. . . . . . . .
534
13.4.1. Построение решающих функций по критерию минимального
расстояния (535). 13.4.2. Разделяющие решающие функции (536).

Оглавление
7

13.4.3. Линейные решающие функции (538).
13.4.4. Построение
решающих функций методом потенциалов (540).
13.5. Распознавание на основе приближенных признаков . .. . . . . . . . . .
545

Г л а в а 14.
Обучение с учителем . . . . . . . . . . . . . . . . . . . . . . . . .
547
14.1. Постановка задачи . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
547
14.2. Алгоритм ДРЕВ . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .
552
14.3. Построение решающего дерева с использованием метрики Хемминга. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
554
14.4. Индукция решающих деревьев . .. . . . . . . . . . . . . . . . . . . . . . . .
557
14.5. Модификация алгоритма Куинлана — ID5R . .. . . . . . . . . . . . . . .
562
14.6. Алгоритм Reduce . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .
567
14.7. Фокусирование . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
570
14.8. Алгоритм EG2. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
575

Г л а в а 15.
Индуктивные методы для случая неполной информации
582
15.1. Проблемы извлечения знаний из баз данных . .. . . . . . . . . . . . . .
582
15.1.1. Ограниченная
информация (583).
15.1.2. Искаженная
информация (583).
15.1.3. Большой размер баз данных (584).
15.1.4. Изменение баз данных со временем (585).
15.2. Алгоритм извлечения продукционных правил из большой базы данных . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
586
15.3. Подход с использованием приближенных множеств . .. . . . . . . . . .
589
15.3.1. Основные понятия теории приближенных множеств (589).
15.3.2. Алгоритм
RS1,
использующий
приближенные
множества (593).
15.3.3. Информационные системы с неопределенностью (597).
15.4. Алгоритм распознавания объектов в условиях неполноты информации . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .
606

Г л а в а 16.
Индуктивное формирование понятий в «зашумленных»
базах данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
617
16.1. Общая классификация недостаточной информации . .. . . . . . . . . .
618
16.2. Моделирование неточной и неполной информации в задаче индуктивного формирования понятий . .. . . . . . . . . . . . . . . . . . . . . . .
620
16.2.1. Внесение шума в поле атрибута, содержащего дискретные значения (621).
16.2.2. Внесение шума в поле атрибута, содержащего непрерывные значения (622).
16.2.3. Моделирование
шума в обучающей выборке (622).
16.3. Методы построения деревьев решений при наличии шума в обучающей выборке
. .. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
628
16.3.1. Постановка задачи индуктивного построения понятий при
наличии шума (628). 16.3.2. Алгоритм предсказания неизвестных
значений по методу «ближайших соседей» (630).
16.3.3. Использование алгоритма ВОССТАНОВЛЕНИЕ при построении дерева
решений (635).

Оглавление

16.4. Программная реализация алгоритма IDTUV. .. . . . . . . . . . . . . . .
637
16.5. Эксперименты на тестовых наборах данных . .. . . . . . . . . . . . . . .
639
16.5.1. Эксперименты
на
данных
«задач
монахов»
(640).
16.5.2. Медицинские
данные (641).
16.5.3. Данные
проекта
StatLog (641). 16.5.4. Другие наборы данных (642).
16.6. Методы проверки. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
643
16.6.1. Перекрестная проверка (643).
16.6.2. Проверка исключением одного примера (643).
16.6.3. Метод бутстрепа (644).
16.6.4. Методика проведения эксперимента по внесению шума в
обучающие выборки (644).
Литература и комментарии . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
648
К введению . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
648
К части I . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
649
К главе 1 . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .
649
К главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
649
К главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
652
К главе 4 . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
654
К главе 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
655
К главе 6 . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
655
К части II. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
658
К главе 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
658
К главе 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
659
К главе 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
660
К главе 10 . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .
662
К главе 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
665
К части III . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
669
К главе 12 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
669
К главе 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
672
К главе 14 . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
673
К главе 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
675
К главе 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
677
Предметный указатель . .. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
679

Низкий поклон тебе, Учитель.

Предисловие ко второму изданию

Второе издание книги вызвано непрекращающимся ростом интереса к трем основным механизмам рассуждений человека: дедукции,
абдукции и индукции, ибо без глубокого изучения и понимания этих
механизмов навряд ли возможно создание действительно интеллектуальных систем управления и принятия решений. В книгу добавлены две главы: формальные системы и индуктивное формирование
понятий в «зашумленных» базах данных. Так как значительную часть
читателей составляют студенты и аспиранты, то как с педагогической,
так и с научной точек зрения разумно начинать книгу не с методов
автоматического доказательства теорем, а с основ математической логики, изложить основные сведения по логике, нашедшие применение
в последующих главах. Поэтому книга начинается с главы, посвященной двум классам формальных систем: исчислению высказываний и
исчислению предикатов первого порядка. Особое внимание уделено
проблеме разрешимости формальных систем, так как после прочтения
этого параграфа и понимания теоремы А. Чёрча о неразрешимости
исчисления предикатов первого порядка в дальнейшем более прозрачными становятся ограничения, положенные в основу автоматического
доказательства теорем.
Последняя глава книги посвящена проблеме работы с реальными,
«зашумленными» базами данных в задаче индуктивного формирования
понятий. Умение работать с неточными и неопределенными данными
очень важно как для дедуктивных баз данных, так и для систем
принятия решений, в частности, экспертных систем. Наряду с методами построения деревьев решений при наличии шума в обучающей
выборке в главе приводятся результаты экспериментов, выполненных
на множествах данных из известной коллекции тестовых наборов данных Калифорнийского университета информатики и вычислительной
техники UCI Machine Learning Repository.
Глава 1 написана Вагиным В. Н., а глава 16 — Фоминой М. В.
В книге были исправлены найденные описки и опечатки, допущенные
в первом издании, которые были указаны читателями, за что авторы
приносят им искреннюю благодарность и признательность.

Предисловие

Идея написания книги возникла у авторов в ходе обсуждения научных результатов на различных конференциях и семинарах по проблемам искусственного интеллекта. Большое влияние на выбор тематики
оказала книга Д. А. Поспелова «Моделирование рассуждений. Опыт
анализа мыслительных актов» 1), в которой описываются дедуктивные
и правдоподобные модели, учитывающие особенности человеческих
рассуждений. Блестяще написанная, совмещающая доступность чтения со строгим изложением сложных логических проблем, эта книга
явилась своеобразным стимулом для продолжения исследований по достоверным и правдоподобным рассуждениям, итог которых воплотился
в данном издании.
Авторы, конечно, осознают, что дать полную картину исследований по достоверным и правдоподобным рассуждениям в одной книге
невозможно, поэтому в ней отражены личные пристрастия авторов в
освещении тех или иных проблем. При этом авторы все-таки надеются, что излагаемый материал привлечет внимание не только узкого
круга специалистов по математической логике, но и многочисленных
профессионалов, занимающихся разработкой интеллектуальных систем
принятия решений, в частности, экспертных систем и систем управления сложными технологическими объектами.
Для того чтобы читатель смог получить цельное представление о
рассматриваемых проблемах, в книге, наряду с оригинальными работами авторов, составляющих единую научную группу, изложен ряд
результатов других российских и зарубежных ученых, тем более, что
некоторые проблемы и методы, такие, как метод аналитических таблиц
или проблема аргументации и абдукции, почти не освещались в отечественной литературе.
Чтобы не затруднять чтение книги, в тексте нет библиографических
ссылок. Вся использованная литература указана в конце книги, где дан
также краткий обзор работ, на которые ссылаются авторы и которые
помогут читателю углубить свои знания об обсуждаемых проблемах.
Выбор материала книги определялся следующими соображениями:
во-первых, желанием охватить достаточно широкий круг проблем, связанных с использованием математической логики в разного рода интеллектуальных системах различного назначения, во-вторых, стремлением
сделать изложение весьма разнородного материала единым и связным,
в-третьих, как уже говорилось, собственными научными интересами
авторов. Насколько удачно это удалось сделать, судить читателям, и
мы заранее благодарны тем, которые укажут на замеченные недостатки
и недоработки.

1) М.: Радио и связь, 1989. 184 с.

Предисловие

Для чтения книги требуются знания в объеме стандартных курсов вузов по дискретной математике, математической логике, теории
принятия решений и языкам программирования. По мнению одного из
авторов, а именно В. Н. Вагина, желательно, чтобы читатели ознакомились с его монографией «Дедукция и обобщение в системах принятия
решений» 1), в которой изложены основные понятия математической
логики и модели представления знаний, а также описаны алгоритмы
дедукции и обобщения понятий по признакам и структурам. Как бы
то ни было, все основные понятия вводятся в данную книгу. Каждый
читатель может избрать свой порядок чтения глав в зависимости от
своих интересов. Читателю, не знакомому или мало знакомому с предметом, рекомендуется изучение материала в той последовательности, в
какой он приведен в книге. Читатели, интересующиеся выборочно какой-либо одной проблемой, например, только абдукцией, могут ограничиться чтением соответствующих глав, опустив или бегло просмотрев
остальные.
Материал книги распределен между авторами следующим образом.
В. Н. Вагин подготовил предисловие, введение, главу 2 (за исключением § 2.6), главы 3, 4, 7, 8, 9; глава 5 написана совместно В. Н. Вагиным
и Е. Ю. Головиной, которая изложила также § 2.6 главы 2, главу 6,
§11.2.4 главы 11. А. А. Загорянская написала главы 10, 11 (кроме
§11.2.4), а М. В. Фомина — главы 12, 13, 14, 15. Естественно, за все
опечатки, описки и ошибки все авторы несут равную ответственность.
Авторы приносят свою искреннюю благодарность редактору этой
книги Д. А. Поспелову и рецензентам Э. В. Попову и Г. С. Плесневичу.
Редактор книги Д. А. Поспелов пытался сделать все возможное, чтобы
книга стала четко структурированной и единой по стилю и замыслу,
но, к сожалению, в силу ряда обстоятельств он так и не сумел добиться
конечного результата.

1) М.: Наука, 1988. 384 с.

Введение

Однажды Лебедь, Рак да Щука
Везти с поклажей воз взялись
И вместе трое все в него впряглись.
И. А. Крылов

С возникновением интеллектуальных систем различного назначения и перенесением центра тяжести на модели и методы представления
и обработки знаний существенно изменяется аппарат формальных рассуждений, комбинирующий средства достоверного и правдоподобного
выводов. На наш взгляд, логика есть наука о рассуждениях, и от разработки формальных моделей различных форм рассуждений зависит
успех создания действительно интеллектуальных систем.
Не вдаваясь в детали определения интеллектуальной системы
(ИнтС), отметим ее основные компоненты:

ИнтС = РИС + ПИС + ИнИн + АП,

где РИС — рассуждатель интеллектуальной системы, состоящий из генератора гипотез, доказателя теорем и вычислителя; ПИС — поисковая
информационная система, которая доставляет информацию, релевантную цели рассуждения; ИнИн — интеллектуальный интерфейс (диалог,
графика, обучение пользователя работе с системой); АП — подсистема
автоматического пополнения базы данных (БД) и базы знаний (БЗ)
из текстов, образующих информационную среду для интеллектуальных
систем.
Под рассуждением понимается построение последовательности аргументов, вынуждающих принятие некоторого утверждения, которое и
является целью рассуждения. Особенностями рассуждения, отличающими его от логического вывода, и в частности, от доказательства, в
стандартном понимании являются
• открытость множества возможных аргументов;
• использование метатеоретических, и в частности, металогических
средств, с помощью которых осуществляется управление логическими выводами, применяемыми в процессе рассуждения;
• использование правил не только достоверного вывода, но и правдоподобного вывода.
Очевидно, что логический вывод в стандартном понимании математической логики — частный случай рассуждений, когда множество
аргументов фиксировано, нетривиальные металогические средства (например, проверка на непротиворечивость) не используются и применяются только правила достоверного вывода, по которым из истинных
аргументов (посылок) можно получить лишь истинные заключения.

Введение

В широком смысле к достоверному выводу и относится дедуктивный вывод, который в настоящее время хорошо изучен и исследован.
В классической логике дедуктивный вывод рассматривается как вывод
от общего к частному. Дедукция — в высшей степени идеализированная и ограниченная форма рассуждений, и если мы хотим моделировать
некоторые аспекты человеческих рассуждений (здравый смысл, неопределенность, противоречивость информации и т. п.), то дедукции будет
совершенно недостаточно, и нужно привлекать недедуктивные или
правдоподобные формы рассуждений, такие как абдукция и индукция.
Термин «правдоподобное рассуждение» принадлежит Д. Пойа; примерами правдоподобных рассуждений в смысле Д. Пойа являются индукция через простое перечисление, аналогия и различные схемы недостоверных (в двузначной логике высказываний) выводов.
Д. Пойа
сформулировал
два
возможных
принципа
вывода
по
аналогии:
• «предположение становится более правдоподобным, когда оказывается истинным аналогичное предположение»;
• «предположение становится несколько более правдоподобным,
когда становится более правдоподобным аналогичное предположение».
Пусть ϕ и Ψ — упомянутые выше предположения, тогда принципам Пойа отвечают, соответственно, следующие схемы правдоподобных
выводов:
ϕ
аналогично Ψ,
Ψ
истинно,

ϕ
более правдоподобно;

ϕ
аналогично Ψ,
Ψ
более правдоподобно,

ϕ
несколько более правдоподобно.

Здесь «ϕ несколько более правдоподобно» понимается в том смысле,
что без информации о правдоподобности Ψ ϕ было бы менее правдоподобным.
Формальные уточнения схем таких правдоподобных выводов связаны, во-первых, с формализацией средства описания структуры данных
предметной области, и, во-вторых, с формализацией «степени правдоподобия ϕ». Существенность сходства структур в выводах по аналогии
была отмечена еще Г. В. Лейбницем.
Индукция обеспечивает возможность перехода от единичных фактов к общим положениям, законам. Говоря об истории исследования
индуктивных рассуждений, следует отметить Ф. Бэкона, который впервые попытался формализовать индуктивные выводы посредством таблиц причин. Ф. Бэкон явился родоначальником исследований «эмпирической структурной индукции», целью которой является обнаружение
эмпирических зависимостей в виде индуктивных обобщений, получен

Введение
15

ных на основе сравнения объектов, имеющих структуру и входящих
в явления, которые представляются примерами и контрпримерами.
Учение Ф. Бэкона об индукции было развито Д. С. Миллем, который
предложил свои известные методы сходства, различия, остатков и
сопутствующих изменений.
Рассматривая индукцию как недедуктивное рассуждение, можно
выделить аргументы, обеспечивающие некоторую (частичную) поддержку заключения, т. е. если посылки истинны, они дали бы некоторое основание, хотя и неполностью убедительное, принять данное
заключение истинным; при этом остается некоторая возможность получить ложное заключение. Аргументы такого типа Салмон называл
«индуктивными аргументами». Далее он классифицирует их следующим образом:

• аргументы, основанные на выборках;
• аргументы, полученные по аналогии;
• статистические силлогизмы.

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

X% наблюдаемых явлений F есть G;
поэтому (приблизительно) X% всех F есть G.

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

объекты типа X имеют свойства F1, F2, ... , Fk;
объекты типа Y
имеют свойства F1, F2, ... , Fk, а также свойство G;
поэтому объекты типа X имеют также свойство G.

Наконец, статистические силлогизмы имеют следующую форму:

X% всех явлений F есть G;
α есть F;
поэтому α есть G.
Здесь процент всех явлений понимается как значительный («большой»), ибо в противном случае заключение будет: α не есть G.

Введение

Можно разделить индуктивные аргументы на статистические и
категорные, понимая последние как имеющие некоторую форму рассуждений. Так, например, категорное индуктивное обобщение имеет
следующий вид:
все наблюдаемые явления F есть G;
поэтому все F есть G.
Независимо от того, являются ли индуктивные аргументы статистическими или категорными, главная проблема заключается в способе
их оценивания. Чтобы узнать степень убеждения некоторой гипотезы
(гипотетического заключения) H при некотором основании (доводе)
E, можно прибегнуть к вероятностной формализации индуктивной
поддержки этой гипотезы и вычислить условную вероятность P(H | E),
что реализуется в теории подтверждения (confirmation theory). Сторонник этой теории Карнап прямо указывал на возможность рассмотрения степени подтверждения гипотезы H путем основания E как на
степень общезначимости индуктивного аргумента типа «E, поэтому H»
и подчеркивал возможность обрабатывать эту «индуктивную общезначимость» как аналог дедуктивной общезначимости. Он писал, что,
называя теорию индуктивного вывода недедуктивной, термин «вывод»
в индуктивной логике мы не понимаем в том же самом смысле, как в
дедуктивной. Обе логики, как дедуктивная, так и индуктивная, едины
в одном: они исследуют логические отношения между утверждениями,
но если первая изучает отношение выводимости одних утверждений из
других, то вторая — степень подтверждения утверждений, которая рассматривается как некоторая числовая мера. Другими словами, теория
подтверждений сама по себе не устанавливает отношение логического
следствия, поскольку любое основание только подтверждает любую
гипотезу в определенной степени. Индуктивная логика, основанная
на теории подтверждений, является логикой оценки гипотезы, а не
ее образования. Поскольку меры убеждения выражают субъективные
оценки агента об истинности гипотез, то процедуры оценки истинности
гипотез являются тем средством, который отвечает на вопрос: «Насколько правдоподобна эта гипотеза при данном основании?»
Возвращаясь к категорным индуктивным аргументам, можно продолжить разделение недедуктивных рассуждений на индуктивные и
абдуктивные. Если в индуктивных выводах некоторые факты, устанавливаемые для отдельных явлений, переносятся на весь класс таких
явлений, то в абдуктивных выводах имеет место вывод от частного к
частному.
Абдуктивные выводы были предложены одним из создателей математической логики Ч. Пирсом. В своей попытке классифицировать
аргументы он следовал силлогистике Аристотеля. Гениальный мыслитель древности выбрал для формализации именно дедуктивные рассуждения, в которых истинные посылки порождают только истинные
заключения. Пирс разработал свою теорию силлогистики. Рассмотрим
в качестве примера аристотелевский силлогизм «Barbara».