Логические рассуждения

Размещено на http://www.allbest.ru//

Лекция 3. Логические рассуждения

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

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

Рассуждения в пространстве состояний среды

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

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

Таблица 3.1

Состояние b1 означает, что кот находится около левой комнаты и около обеих комнат лежит по кусочку сыра, состояние b2 -- кот находится около правой комнаты и около обеих комнат снова лежит по кусочку сыра и т.д.

Кот может совершать в один и тот же момент времени только одно из следующих действий: переходить к дверям левой комнаты, переходить к дверям правой комнаты и съедать кусочек сыра около той комнаты, где он находится.

Эти действия обозначим с1 = Идти налево, с2 = Идти направо и с3 = Съесть, соответственно. Если среда находится в одном из состояний, перечисленных в табл. 3.1, и кот совершает какое-либо из действий, то нетрудно определить в какое состояние после выполнения действия перейдет среда.

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

Пусть, например это будет состояние b1. Будем изображать состояния

кружочками с обозначением состояния внутри кружочка.

Рис. 3.1. Допустимые переходы из начального состояния b1

Рис. 3.2. Дерево переходов

Переход из одного состояния в другое, происходящий в результате действия, будем изображать стрелкой, ведущей в это другое состояние и помеченной соответствующим действием. Так, на рис.3.1 изображены все переходы из состояния b1 в результате действий с1,с2 , с3 .

На рис. 3.2 показано дерево всех дальнейших переходов, являющееся продолжением элементарного дерева на рис. 3.1. Построение каждой ветви дерева прекращено на том состоянии, которое встречается повторно на пути, ведущем в него из начального состояния.

Постановка задачи

Цель кота -- не оставить ни одного кусочка сыра, где бы он изначально ни находился. В терминах состояний среды целью кота является перевод ее с помощью своих действий (реакций) в одно из состояний b7 или b8 . Состояния, в которые с помощью набора допустимых действий необходимо перевести среду, называются целевыми. Процесс определения этих состояний называют формулировкой цели. Будем полагать в рамках нашего примера, что каждое восприятие совпадает с одним из состояний. Задачей агента является нахождение последовательности действий или пар восприятие--действие, ведущих на дереве переходов из начального состояния в целевые. Процесс нахождения этих последовательностей называют поиском, выводом или рассуждением. Постановкой задачи называют задание всех состояний и действий, которые можно использовать для решения задачи, начального состояния и целевых состояний, а также всех допустимых переходов между состояниями при выполнении действий. Для среды кота постановка задачи уже осуществлена. Все состояния, которые могут использоваться при решении задачи, перечислены в табл. 3.1. Целевыми состояниями являются состояния b7, b8. Все допустимые переходы между состояниями показаны на рис. 3.2. Из рисунка ясно, что решениями задачи является последовательность b1/c2, b2/c3,b4/c1,b3/c3, в результате выполнения которой агент (кот) переведет среду в состояние b7, и последовательность b1/c3, b5/c2, b6/c3, в результате выполнения которой среда окажется в состоянии b8.

Формализация вывода средствами логики высказываний

Для записи задачи на языке исчисления высказываний введем три логические переменные хк, хл, хп .

Истинное значение первой из них означает, что кот находится у левой комнаты, а ложное, что он находится у правой комнаты;

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

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

В результате таких обозначений табл. 3.1 можно заменить на табл. 3.2. Каждое состояние среды можно рассматривать как комбинацию (отношение) простейших свойств объектов, задаваемых значениями отдельных логических переменных. Так, состояние b1 соответствует комбинации свойств кота и кусочков сыра, состоящей в том, что кот находится в левой комнате, и в это же самое время около левой и правой комнат находится по кусочку сыра. На русском языке эту комбинацию можно выразить предложением: «Кот находится около левой комнаты, кусочек сыра лежит около левой комнаты и кусочек сыра лежит у правой комнаты». В соответствии с уже приведенной выше интерпретацией логических переменных хк, хл, хп это предложение можно представить формулой , которая истинна в единственном случае - все логические переменные, входящие в нее, истинны, т.е. среда находится в состоянии b1. Формулы такого типа, являющиеся конъюнкцией переменных с отрицанием или без него, называют элементарными конъюнкциями. Если среда находится в состоянии b2, то истинна формула и т.д.

Элементарную конъюнкцию, в которую входит по одному разу каждая переменная, определяющую состояние среды, с отрицанием или без отрицания, называют полной конъюнкцией, или конституентой.

Аналогично тому, как были введены логические переменные хк, хл, хп, введем логические переменные z 1, z2, z3 для действий кота “Идти налево”, “Идти направо”, “Съесть “,соответственно. Переменная принимает истинное значение, если выполняется соответствующее ей действие. В противном случае она принимает ложное значение.

Таблица 3.2

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

Таблица 3.3

Рассмотрим теперь, как могут быть выражены в виде формул переходы среды из одного состояния в другое при совершении котом того или иного действия. Так, если кот находился в состоянии b1, и выполнил действие “Идти направо”, то среда перейдет в состояние b2 . Факт нахождения кота в состоянии b1, и выполнение им в это время действия “Идти направо” означает истинность формулы , а факт перехода состояния b1 при выполнении действия «идти направо» в состояние b2 будем интерпретировать как истинность формулы , что позволяет при истинности сделать заключение об истинности . Точно так же можно выразить в виде аналогичных формул все остальные переходы, показанные на рис. 3.2. Представим их в виде табл. 3.3. В первых трех столбцах этой таблицы указаны переходы, имеющиеся на рис. 3.2, а в последнем -формулы, соответствующие переходам.

Поиск решения

Решения задачи для среды кота практически очевидны, когда построено дерево переходов состояний среды, по которому легко проследить пути, ведущие в целевые состояния из начального. В реальных задачах это дерево может быть очень большим, вследствие чего нецелесообразно использовать стратегию поиска, согласно которой необходимо сначала получать дерево целиком. Вместо этого используются другие более эффективные стратегии поиска, речь о которых пойдет в главе 4. Однако, какая бы из этих стратегий не применялась, элементарным шагом поиска является переход из одного состояния среды в другое и анализ состояния, в которое переход был осуществлен, на принадлежность к числу целевых. Каждый допустимый переход из состояния bi. после совершения действия сj в состояние bk можно задавать с помощью правила перехода: « Если среда находится в состоянии bi. и совершается действие сj, то она должна перейти в состояние bk».

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

1.Образовать множество В = {b1}, состоящее из одного начального состояния b1.

2. Для каждого состояния множества В и каждого действия с найти, согласно соответствующим правилам перехода, все состояния bk, в которые переходит среда. Совокупность всех таких состояний, за исключением тех, которые уже встречались в ранее образованных множествах В, принять за новое множество В.

3. Проверить, нет ли среди элементов этого множества целевых состояний. Если целевых состояний нет, то перейти к п. 2. Если целевые состояния есть, то выписать в порядке использования правил все последовательности действий, которые привели к целевым состояниям, удалить эти состояния из множества В и перейти к выполнению следующего пункта.

4. Проверить, все ли целевые состояния найдены. Если найдены все, то прекратить поиск. Если найдены не все, то перейти к п. 2.

Проиллюстрируем на примере среды кота применение этой стратегии. Правила перехода выписывать не будем, поскольку в нашем распоряжении уже есть дерево переходов (см. рис. 2.2).

Итак, вначале В = {b1}. После выполнения п. 2 имеем совокупность состояний b1 ,b2, b5 . В этой совокупности нет ни одного целевого состояния, а состояние b1 уже встречалось. Поэтому, согласно п. 3, принимаем В = {b2,b5} и переходим к выполнению п. 2. В результате получаем совокупность состояний b1,b2, b4, b5, b6 , среди которых опять нет целевых, а b1, b2 , b6 уже встречались. Поэтому В = {b4, b6 } и снова возвращаемся к п. 2. После очередного выполнения этого пункта имеем совокупность состояний b3, b4, b5, b6, b8 . Среди этих состояний b4, b5, b6 уже встречались, а состояние b8, является целевым. В это состояние ведет единственная последовательность действий с3, c2 , c3. Однако еще не все целевые состояния найдены, а именно не найдено состояние b7 . Поэтому в соответствии с п. 4 продолжим поиск, вновь переходя к п. 2 с множеством В = {b3}. В результате получим совокупность состояний b3, b4, b7, среди которых b3, b4 уже встречались, а b7 - целевое. Последовательностью действий, ведущих в состояние b7, является c2 c3 c1 c3. И так, все целевые состояния найдены, решение задачи в виде последовательности действий, ведущих в эти состояния, получено. Поиск на этом прекращается.

Нечеткий логический вывод

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

Люди не всегда могут ответить на вопросы точно. Можно ли узнать, какая у человека температура, если он говорит, что слегка заболел? Скорее всего, нет. Такие слова, как высокий, горячий и легкий, представляют собой лингвистические переменные, которые нельзя определить одним значением.

Лингвистическая переменная состоит из названия переменной, например, ПРОЦЕНТНАЯ СТАВКА и ее значений, например, РАСТЕТ, ПАДАЕТ.

Использование этих понятий при формулировании правил называется нечеткой логикой.

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

В качестве примера рассмотрим влияние квартирной платы и цен на продукты питания на уровень жизни семьи. Это влияние описывается следующими утверждениями.

1. ЕСЛИ К_П незначительно растет, ТО У_Ж_1 незначительно падает. ( = 0.9)

2. ЕСЛИ К_П незначительно растет, ТО У_Ж_1 не падает. ( = 0.1)(Если перестают платить)

3. ЕСЛИ К_П значительно растет, ТО У_Ж_1 значительно падает. ( = 0.5)

4. ЕСЛИ К_П значительно растет, ТО У_Ж_1 не падает. ( = 0.5)

5. ЕСЛИ Ц_П незначительно растут, ТО У_Ж_2 незначительно падает. ( = 1)

6. ЕСЛИ Ц_П значительно растут, ТО У_Ж_2 значительно падает. ( = 1)

7. ЕСЛИ У_Ж_1 незначительно падает И У_Ж_2 незначительно падает, ТО У_Ж незначительно падает. ( = 1)

8. ЕСЛИ У_Ж_1 незначительно падает И У_Ж_2 значительно падает ИЛИ У_Ж_1 значительно падает И У_Ж_2 значительно падает, ТО У_Ж значительно падает. ( = 1)

9. ЕСЛИ У_Ж_1 значительно падает И У_Ж_2 значительно падает, ТО У_Ж очень значительно падает. ( = 1)

Условия К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ и К_П ЗНАЧИТЕЛЬНО РАСТЕТ являются размытыми и выражаются в зависимости от количества процентов роста p следущими формулами.

При 0 < p < 2 (К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ) = p / 2.

При 2 < p < 4 (К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ) = 1.

При 4 < p < 10 (К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ) = (10 - p) / 6.

При p > 10 (К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ) = 1.

При p < 5 (К_П ЗНАЧИТЕЛЬНО РАСТЕТ) = 0.

При 5 < p < 15 (К_П ЗНАЧИТЕЛЬНО РАСТЕТ) = (p - 5) / 10.

При p > 15 (К_П ЗНАЧИТЕЛЬНО РАСТЕТ) = 1.

Условия Ц_П НЕЗНАЧИТЕЛЬНО РАСТУТ и Ц_П ЗНАЧИТЕЛЬНО РАСТУТ также являются размытыми и выражаются формулами

При 0 < p < 1 (Ц_П НЕЗНАЧИТЕЛЬНО РАСТУТ) = p.

При 1 < p < 5 (Ц_П НЕЗНАЧИТЕЛЬНО РАСТУТ) = (5 - p) / 4.

При 0 < p < 10 (Ц_П ЗНАЧИТЕЛЬНО РАСТУТ) = p / 10.

При p > 10 (Ц_П ЗНАЧИТЕЛЬНО РАСТУТ) = 1.

При использовании нечеткой логики для каждой формулы вводятся целый спектр возможных значений, лежащих между 0 (ЛОЖНО) и 1 (ИСТИННО), и правила вычисления этих значений. Вычисленные таким образом значения определяют степень истинности формул. Рассмотрим основополагающие понятия нечеткого множества и функции принадлежности.

Рассмотрим такие понятия, как « растет» и «падает». Отнесем эти понятия к переменным ПРОЦЕНТНАЯ СТАВКА и РУБЛЬ. Применительно к переменной ПРОЦЕНТНАЯ СТАВКА понятие роста может означать повышение уровня цен на бирже на 10 -- 30 пунктов по индексу Доу- Джонса, а применительно к переменной РУБЛЬ означает повышение курса рубля по сравнению с какой - либо другой валютой в 20 --30 раз. В таком контексте слово «растет» называется значением лингвистической переменной. Лингвистическая переменная может принимать различные значения из некоторого интервала, границы которого могут меняться в зависимости от обстоятельств. Например, границы интервала для лингвистической переменной «холодный» могут меняться в зависимости от того, идет ли речь о зиме или весне.

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

Рассмотрим правило:

ЕСЛИ ПРОЦЕНТНЫЕ СТАВКИ - ПАДАЮТ И НАЛОГИ УМЕНЬШАЮТСЯ,

ТО УРОВЕНЬ ЦЕН НА БИРЖЕ - РАСТЕТ.

Это правило верно не всегда, поэтому можно ему приписать значение некоторого числа m, изменяющегося от 0 до 1. Такое число называют функцией принадлежности м.

Пусть функция принадлежности данного правила равна 0,9, т.е. вероятность того, что при падении процентных ставок и уменьшении налогов уровень цен на бирже будет падать равна 0.9.

Но выполнение правила зависит от выполнения условий ПРОЦЕНТНЫЕ СТАВКИ ПАДАЮТ и НАЛОГИ УМЕНЬШАЮТСЯ, что происходит не всегда.

Пусть функция принадлежности лингвистической переменной ПРОЦЕНТНЫЕ СТАВКИ ПАДАЮТ равна 0.6, а функция принадлежности лингвистической переменной НАЛОГИ УМЕНЬШАЮТСЯ равна 0.8.

Тогда правило можно записать так:

ЕСЛИ ПРОЦЕНТНЫЕ СТАВКИ - ПАДАЮТ (м - 0.6) И

НАЛОГИ УМЕНЬШАЮТСЯ (м - 0.8), ТО УРОВЕНЬ ЦЕН НА БИРЖЕ - РАСТЕТ ( м правила - 0.9)

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

(minimum (0.6, 0.8))*0.9 = 0.54

Следовательно, при м - 0,54 можно сказать, что уровень цен на бирже будет падать.

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

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

2.Если в правиле есть оператор ИЛИ, выбрать максимальное значение из м для всех условий правила, разделенных оператором И для всех условий, связанных оператором ИЛИ.

3.Умножить выбранный м на м правила.

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

Рассмотрим два правила с одним и тем же логическим выводом С:

ЕСЛИ А (м =0,3) И В (м =0.6), ТО С (м =0.5)

ЕСЛИ D (м =0.4) И Е (м =0,7), ТО С (м =0.9)

В приведенных правилах м для логического вывода С подсчитывается следующим образом:

maximum ((minimum(0.3,0.6)*0.5), (minimum (0.4,0.7) *0.9)) =

=maximum (03*0.5),(0.4*0.9)) = maximum (0.15,0.36) = 0.36

Возьмем пример с использованием логического оператора ИЛИ:

ЕСЛИ А (м =0.3) И В (м =0.6) ИЛИ D (м =0.5), ТО С (м =0.4)

В этом примере м для логического вывода С считается так:

maximum (minimum (0.3,0.6), 0.5)*0.4) = maximum (0.3,0.5)*0.4 =

0.5*0.4=0.2.

Во многих случаях изначально заданы граничные значения функции принадлежности. Логический вывод считается верным только в том случае, если его м превышает заранее заданные граничные значения. Работа с базой знаний продолжается до тех пор, пока значение функции принадлежности логического вывода больше граничного значения. В процессе работы выполняются определенные вычисления. Предположим, для частного логического вывода м равно 0,4. Это значение запоминается. Затем оно сравнивается с граничным значением м (допустим, что оно равно 0,8). Запомненное значение оказалось меньше граничного, и, значит, работа с базой знаний продолжается. Если при работе с базой знаний встретился тот же самый логический вывод, м для новой м и результат прибавляется к запомненному ранее м . Значение м , равное 1, свидетельствует об абсолютной уверенности в правильности вывода. Затем вновь запомненное значение м сравнивается с граничным, и если оно больше, выполняется логический вывод, в противном случае, работа с базой знаний продолжается. Вышесказанное можно записать с помощью равенства:

Запомненный м = Ранее запомненный м + (1-Ранее запомненный м ) * м нового правила.

Например:

Граничное значение м = 0,8

Правило: ЕСЛИ А, ТО В (м =0,6)

Запомненный м : 0,6

Новое правило: ЕСЛИ С, ТО В (м =0,7)

Запомненный м =0.6+ (1 -0,6) *0,7= 0,88 (граничные значения превышены, и выполняется вывод).

Размещено на Allbest.ru