Аналогия в задачах принятия решений

      Определение 2.7 (Харагути). Если для парного соответствия отношение является взаимно однозначным, то назовем частичным тождеством.

      Для того чтобы  являлось частичным тождеством, необходимо в дополнение к ввести следующие новые аксиомы:

      

      

      Здесь обозначение предиката структурной эквивалентности термов (в смысле возможности унификации). Более строго в соответствии со следующей логикой первого порядка (теории эквивалентности), введенной Кларком, можно определить так, как указано ниже.

      Логика  первого порядка  :

      1)  для различных констант  ,

      2)  для различных функций 

          ,

      3)  для константы  и функции

       ,

      4)  для терма  с переменной , отличного от ,

           ,

      5) для функции 

      

      6)   ,

      7)  

      8)    ,

              

      При этих условиях для термов в , не содержащих переменных, утверждения « |— » и « и структурно равны » равнозначны. С помощью , можно следующим образом определить логику первого порядка , которая дает условия того, что является частичным тождеством.

      

      Здесь означает сумму множеств логических формул.

      Теорема 2.2. Для парного соответствия следующие два условия равнозначны:

      1) -  частичное тождество,

      2) - непротиворечивая логика.

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

      В общем случае оценка непротиворечивости логики — алгоритмически нерешаемая проблема. Однако, к счастью, если частичное тождество определено, то сразу же можно рассмотреть процедуру вывода из . В следующем разделе мы изучим свойства частичного тождества и приведем процедуру выводов из суммы аналогии. 

      2.3. Реализация  механизма  аналогии 

      Выше  было введено понятие частичного тождества (определение 2.7) и показано, что проблема обнаружения частичного тождества равнозначна обнаружению непротиворечивости логики . В данном разделе дадим условия обеспечения частичного тождества  заданных  парных  соответствий.   Кроме того, рассмотрим метод реализации механизма аналогии, выполняющего выводы на основе , если с помощью этих условий обнаружено частичное тождество .  Oсновные этапы реализации состоят в следующем.

       . Предварительно получим парное соответствие между моделями множеств определенных предложений, затем будем не только преобразовывать правила, но и одновременно с преобразованием проверять согласование частичных тождеств, частично определив тем самым .

       .  Объекты аналогии описываются в виде множества определенных предложений, поэтому для преобразования правил воспользуемся конкретизацией и правилом «модус поненс» в системе обработки логических программ (в данном случае интерпретатором Пролога).

      В процессе преобразования правил для  выводов по аналогии на основе подобия как «структурного частичного тождества» (Харагути) накладывались условия согласования правил на основе некоторого частичного тождества. Кроме того, в системе выводов по аналогии Уинстона, использующей фреймовые «структуры как внутреннее представление объектов, априори вводились условия, соответствующие максимальному частичному тождеству , а уже затем делалась аналогия. В рассматриваемом ниже методе определяется так, как указано в , поэтому нет необходимости заранее знать . Отметим также, что Уинстон, используя входной интерфейс, предварительно обрабатывал структуры с целью получения дедуктивных выводов, а в данном методе дедукция сделается только при необходимости. В этом состоят наиболее явные отличия этих методов. 

      2.3.1. Подобие, как частичное   тождество

      Частичное тождество  , введенное выше, — это отношение термов, задающее частичную тождественность областей Эрбрана . В общем случае парное соответствие задает отношение атомов в (определение 2.3), а частичное тождество — взаимно  однозначное отношение атомов.

      Лемма 2.2. Для частичного тождества :

       - является взаимно однозначным отношением атомов в и   .

      Из  этой леммы следует, что частичное  тождество  задает частичную тождественность и   . Если использовать обобщенное графическое представление (Плоткин), то этот факт можно иллюстрировать так, как на рис. 2.8.

                                                                   

      

      

        а     

        

                                 

      Рис. 2.8. Частичное тождество 

и    

        На этом рисунке переменные    введены для представления пар из .  Кроме того, с помощью запись   представляется в виде логической формулы .

      Для реализации аналогии на основе такого частичного тождества рассмотрим условие, гарантирующее, что заданное парное соответствие является частичным тождеством.

      Определение 2.8. Следующее условие для парного соответствия назовем расширенным условием частичного тождества и обозначим его как .

      Условие: пусть  ,   , а — терм, не содержащий констант. Тогда не существует , , таких, что

      

      

      Теорема 2.3. Необходимым и достаточным условием для того, чтобы было частичным тождеством, является .

        по существу обеспечивает  возможность унификации и играет важную роль при реализации системы выводов, но об этом мы узнаем в следующем разделе. 

      2.3.2. Реализация  системы   аналогии

      В данном разделе приведем процедуру  вывода от цели к фактам факта  для некоторого частичного тождества . По определению включает минимальную модель множества и является минимальным множеством, замкнутым относительно применения правил, полученных при их преобразовании. Следовательно, искомая процедура вывода состоит из двух процедур[7]:

       ) интерпретатора, который считает логической программой и выполняет ее процедурную интерпретацию;

       ) процедуры, выполняющей преобразование правил от цели к фактам.

      В качестве интерпретатора рассмотрим интерпретатор чистого Пролога. Тогда указанную выше процедуру вывода можно считать логической программой, расширяющей этот интерпретатор. Для преобразования правил в процедуре необходимо определить, на основе какого частичного тождества выполнять это преобразование. С этой целью сначала априори зададимся некоторым частичным тождеством и рассмотрим метод выводов с фиксированным . Однако это не эффективно в следующих случаях:

      1) для заданных  и может существовать несколько , поэтому для определения подходящего , следуя некоторому порядку действий, потребуется большой объем вычислений;

      2)  подходящих для аналогии  также может быть несколько, поэтому выбор только одного из них суживает возможности выводов.

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

        

                    

                           ,

                           ,

      

      Зададимся для  и , и некоторого частичного тождества начальной целью

       .

      В этот момент никакой информации о  не задано. Процедура вывода, прежде всего, проверяет безотносительно , является ли логическим следствием , то есть атомом в . В случае неудачи процедура пытается преобразовать правила . , поэтому конкретизируем правило :

                                      

и преобразуем  его. Для конкретизации сгенерируем  подцель:

       ,

получим решение   , с помощью некоторого выполним преобразование   

      

      

      По  определению преобразования правила  для

      

      должно  быть справедливо

            (2.7)

      Благодаря определению достаточности формулы (2.7) частично получаем . С этой целью используем следующую лемму.

      Лемма 2.3. Пусть — ограниченное множество пар термов, не содержащих переменных. Тогда необходимым и достаточным условием существования некоторого частичного тождества, такого, что является условие для .

      По  этой леммe формулу (2.7) можно привести к виду

          (2.8)

      Процедура вывода, определив  для которых  удовлетворяет , частично получает , используемое для преобразования правил. Поставив в соответствие и для терма  в  ,  задает (частичную) эквивалентность областей Эрбрана  и , поэтому в должно быть справедливо . Аналогично для термов и в должны быть справедливы и . В конце концов утверждения «существует некоторое частичное тождество, которое делает возможным преобразование исходных правил» и «множество равенств 

                                            (2.9)

имеет решение» равнозначны. Здесь знак « = » означает отношение структурного равенства термов, поэтому через возможность унификации можно проверить существовавания решения. В данном случае решение дает замена

      

а формулу (2.8) можно привести к виду

      

      Таким образом, получаем преобразование правила 

                                       (2.10)

      Далее, для получения  генерируем подцель