Глава третья
Исчисление высказываний. Эта формальная система описана во всех руководствах по математической логике, например в [45]. Цитаты из Д. Самойлова заимствованы из сборника [46].
«Логик-теоретик». Существует весьма много программ, с помощью которых демонстрировались возможности ЭВМ при доказательстве выводимости формул в исчислении высказываний. Например, одна из первых работ в данной области [47] и первая отечественная система такого рода [48]. Программа «Логик-теоретик» была первым шагом на пути создания А. Ньюэллом и Г. Саймоном общей концепции решения творческих задач на ЭВМ на основе организованного эвристически перебора по лабиринту возможных альтернатив. Эта идея была воплощена ими в виде программы, названной «Общий решатель задач». Работы по этому кругу вопросов печатались неоднократно, например [49, 50]. Как позже выяснилось, подход к решению задач, реализованный в «Общем решателе задач», оказался не столь плодотворным, как думали авторы. Но для организации вывода в исчислении высказываний он удобен, хотя программа не всегда без большого перебора могла находить нужные пути по множеству альтернатив. В работах [49, 50] по этому поводу имеется немало экспериментальных наблюдений как над людьми, ищущими вывод, так и над работой программы «Логик-теоретик»
Исчисление предикатов. Исчисление предикатов описано во всех учебниках. Сошлемся на [45]. Проблема соответствия логики предикатов и силлогистики Аристотеля до сих нор вызывает некоторую полемику [31, 51]. Еще во второй половине 40-х годов известный логик Я. Лукасевич построил специальную формальную систему для силлогистики [52]. Он оставил два квантора A и I, положив по определению, что Esp=
Я. Лукасевич ввел три правила вывода: 1) в выводимую формулу вместо любой переменной типа s, p или m можно одновременно по всей формуле подставить любую формулу исчисления; 2) в выводимой формуле вместо любой переменной можно по всей формуле поставить другую переменную; 3) модус поненс.
Изложение вопросов, связанных с процедурами автоматизации доказательств, можно найти в монографии [53].
Первым универсальным методом доказательства был предложенный в 1965 году американским логиком Дж. Робинсоном метод резолюций. Его появление совершило переворот в использовании ЭВМ для доказательства теорем в исчислении предикатов. Начиная с работы самого Робинсона [54], возник огромный поток исследований в этом направлении. В монографии [53] на зафиксированном в ней временном срезе дан аналитический обзор всего сделанного в этой области. Но и до сегодняшнего дня всевозможные модификации метода Робинсона продолжают оставаться предметом публикаций.
Появление языка программирования ПРОЛОГ вновь стимулировало интерес к методу резолюций. Язык ПРОЛОГ, считающийся весьма перспективным для ЭВМ новых поколений, позволяет эффективно описывать выполняемые в нем процедуры в виде вывода в исчислении предикатов (точнее, в некоторой части этого исчисления, связанной с дизъюнктами Хориовского типа, исключающими некоторые типы выражений). А так как метод резолюций есть универсальная процедура для Хорновских дизъюнктов, то понятен тот интерес, который специалисты по программированию, созданию ЭВМ новых поколений и пользователи, оперирующие ПРОЛОГом, проявляют к методам типа метода резолюций.
Общая схема вывода. Описанное в этом разделе представление имеет куда большее значение, чем то, о котором в нашей книге идет речь. В теории искусственного интеллекта И-ИЛИ деревья и И-ИЛИ сети встречаются не только при моделировании рассуждений. Они широко используются при представлении знаний о проблемных областях разного типа. Находят они применение и в лингвистических процессорах, предназначенных для анализа текстов на естественном языке. В монографиях [55–57] заинтересованные читатели могут найти описание областей применения таких моделей. Идея метода обратного вывода принадлежит С.Ю. Маслову. Впервые она сформулирована в работе [58]. В настоящее время в СССР имеются версии программной реализации этого метода, во многом не уступающего по своей эффективности методу резолюций Робинсона. Рассказ Э. По, из которого приведена цитата, помещен в [59].