23664

Представление знаний с использованием логики предикатов

Лекция

Информатика, кибернетика и программирование

S2: получает студент стипендию  сдает успешно сессию студент S3: сдает успешно сессию студент Задача которую надо решить состоит в том чтобы ответить на запрос получает ли студент стипендию Когда используется обычная система логического вывода то такой вопрос представляется в виде отрицания S:  получает студент стипендию и система должна отвергнуть это отрицание при помощи других предложений демонстрируя что данное допущение ведет к противоречию. ШАГ 1 Система на первом шаге применит правило к родительским...

Русский

2013-08-05

337.5 KB

28 чел.

9

© SerP   С.Хабаров  - Лекция по курсу "Информационные технологии " (9 стр.)  стр. 9

4. Представление знаний с использованием логики предикатов

4.1. Логические модели и логическое программирование

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

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

Т.е. логика предикатов - это языковая система, которая оперирует с предложениями на естественном языке в пределах синтаксических правил этого языка.

Язык логики предикатов использует слова, которые описывают:

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

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

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

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

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

4.2. Простейшие конструкции языка предикатов

Терм - это знак (символ) или комбинация знаков (символов), являющаяся наименьшим значимым элементом языка.

К термам относятся константы, переменные и функции.

Константа применяется для обозначения конкретных объектов реального мира. Пример: ласточка, птица, один, 2  и т.д.

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

Функции (структуры) - последовательность из нескольких констант или переменных, заключенных в круглые скобки, следующие за функциональным символом (функтором). Пример: сумма (1,2); +(1,2); удвоить (X).

Функторы обозначают операторы, которые после воздействия на объект возвращают некоторое значение.

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

Заключенная в скобки последовательность из n термов, перед которой стоит предикатный символ, называется n-местным (или n-арным) предикатом, который принимает значения «истина» или «ложь» в соответствии со значением термов, являющимися его аргументами.

Пример:

является ( ласточка, птица )

отец (X, Джон )

Такого типа предикаты получили название атомарных предикатов и соответствуют наиболее простым предложениям нашего разговорного языка - нераспространенным предложениям.

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

4.3. Предикатные формулы

В логике предикатов сложными предложениями естественного языка соответствуют предикатные формулы. Предикатные формулы образуются из атомарных предикатов и логических связок, которые читаются как (таблица 4.1):

Таблица 4.1

Логические связки

,

«и»

«или»

«не»

«если»

«тогда и только»

Логические связки имеют следующий приоритет использования:

  1.    
  2.   ,
  3.   ,

Наиболее часто в логическом программировании используются связки «И», «НЕ» «ЕСЛИ».

Пример предикатной формулы, соответствующей сложному предложению:

является (ласточка, птица) ← имеет (ласточка, крылья),

владеет (ласточка, гнездо).

где является (_,_); имеет (_,_); владеет (_ _) - атомарные предикаты; «,» и «» - логические связки.

Однако приведенная конструкция предикатной формулы позволяет делать утверждение не только о конкретном индивидууме которым является ласточка, но и о всех индивидуумах из класса птиц, используя вместо констант переменные:

является (Х, птица) имеет (Х, крылья), владеет (Х, гнездо)

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

Однако предикат, который содержит переменные; например,

имеет (Х, крылья)

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

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

Тогда приведенная выше логическая формула будет записана в виде:

(X) [являться (Х, птица) имеет (Х, крылья), владеет (Х, гнездо)]

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

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

любит (Х, У),

который описывает отношение «Х любит Y»:

  •  (X) (Y) любит (Х, Y) - все люди любят всех людей;
  •  (Х) (Y) любит (Х, Y) - существует человек, который любит всех;
  •  (Х) (Y) любит (Х, Y) - для каждого человека существует тот, который его любит;
  •  (Х) (Y) любит (Х, Y) - существует человек, который кого-нибудь любит.

4.4. Определение правильно построенной формулы

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

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

  1.  Термом является либо константа, либо переменная, либо кортеж из n термов, перед которым стоит функтор.
  2.  Предикат - это кортеж из n термов, перед которым стоит предикатный символ.
  3.  Атомарный предикат является логической формулой.
  4.  Если F и G - логические формулы, то (F); F,G; FG; F; FG; FG - также являются логическими формулами.
  5.  Если F(X) - логическая формула, то оба выражения (Х) F(X),  (X) F(X) является логическими формулами.
  6.  Все результаты, получаемые повторением конечного числа n1 - n6, являются логическими формулами.

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

Воспользовавшись этими определениями, можно, например, предложение «все люди смертны» записать в виде:

(X) [человек (Х) смертен]

4.5. Логический вывод

Логический вывод - это процесс получения из множества правильно построенных формул (S) некоторой ППФ (s) путем применения одного или нескольких правил вывода.

4.5.1. Правило резолюции для простых предложений

Наиболее простой метод логического вывода использует только одно правило вывода, называемое резолюцией, которое применяют к логическим формулам вида:

факт: А

отрицание: 1, ... , Аn)

импликация: А В1, ... , Вm,

где Аi (i = 1, n) и Bj (j = 1, m) - произвольные предикаты.

Рассмотрим наиболее простую из форм резолюции для случая  всего лишь двух S = { S1 , S2 } ППФ вида:

S1 (отрицание):   А

S2 (импликация):  А В ,

в которых предикат А из S1 совпадает с предикатом А левой части S2.

В результате одного шага вывода из S1 и S2 будет получена новая ППФ вида:

S:  B

На этом шаге вывода ППФ S1 и S2 называются родительскими предложениями, а S - резольвентой, которая получается в результате применения резолюции к S1 и S2.

Резолюция в этом простейшем случае соответствует правилу вывода modus tollens, которое записывается в виде:

A AB

  B

и соответствует следующему умозаключению:

допуская, что: НЕ А и А ЕСЛИ В,

выводим:  НЕ В

В еще более простом случае, когда S1 - отрицание, а S2 - факт, т.е.:

S1:  А

S2: А

применение правила резолюции даст резольвенту - пустое отрицание

S:

и означает противоречие. Данный шаг вывода может быть записан в виде:

A, A

 

и резолюцией является рассуждения типа

допуская, что: НЕ А и А

выводим противоречие.

4.5.2. Правило резолюции для сложных предложений

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

S1: (A1,... ,Ak, ...,An)

S2: Ak  (B1, ...,Bm)  (где 1<k<n)

Здесь некоторый предикат Аk из отрицания S1 совпадает с предикатом из левой части S2. В этом случае шаг вывода заменяет Аk в S1 на правую часть S2 и в качестве резольвенты получают отрицание

S:  (A1, ..., Ak-1, B1,..., Bm, Ak+1, ..., An)

Данное правило проиллюстрируем содержательным примером.

допуская, что Не (темно и зима и холодно)

и что Зима если Январь

выводим, что НЕ (темно и январь и холодно)

В том случае, если S1 имеет тот же вид, а S2 - факт

S2: Ak

причем Аk является одним из предикатов из S1, шаг вывода только вычеркивает Аk из S1 и получается резольвента

S:  (A1, ..., Ak-1, Ak+1, ..., An)

Данный шаг вывода можно иллюстрировать следующим примером

допуская, что НЕ (темно и зима и холодно)

и что Зима

выводим, что:  НЕ (темно и холодно)

4.5.3. Простая резолюция сверху вниз

Рассмотренные выше правила применяются на каждом шаге вывода только к двум родительским предложениям. Вместе с тем описание любой области знания содержит множество ППФ.

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

S2: получает (студент, стипендию) сдает (успешно, сессию, студент)

S3: сдает (успешно, сессию, студент)

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

получает ли студент стипендию?

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

S: получает (студент, стипендию)

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

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

Теперь представим себе, что исходная логическая модель, составленная из трех предложений  S1, S2 ,S3 поступает на вход системы логического вывода ЭВМ.

ШАГ 1

Система на первом шаге применит правило (*) к родительским предложениям S1 и S2 и получит резольвенту:

S: сдает (успешно, сессию, студент)

ШАГ 2

Используя правило (**) к S и S3 система выводит противоречие:

S`: 

Таким образом, для доказательства противоречивости S1 S2 S3 оказалось достаточно двух шагов вывода.

Если считать, что S2 и S3 не противоречат друг другу, то они совместно противоречат S1, т. е.

подтверждают

отрицание S: S1: ( получает (студент, стипендию))

или другими словами подтверждают предложение:

получает (студент, стипендию)

и ответом на исходную задачу является «ДА».

Логический вывод, который порождает последовательность отрицаний, такую как (S1 , S , S`) в рассмотренном примере, называется резолюцией сверху вниз.

4.5.4. Общая резолюция сверху вниз

В общем случае предикаты и ППФ в качестве термов содержат не только константы, но и переменные  и функции. Рассмотрим два родительских предложения:

S1: получает (студент, У)

S2: получает (Х, стипендию) сдает (успешно, Z, X)

К ним непосредственно нельзя применить правило резолюции, т.к. они не содержат одинаковых предикатов в левой части импликации и в отрицании. Данные предложения содержат три переменных X, Y, Z,  которые неявно универсально квантированы.

Рассмотрим первое предложение, S1 , которое утверждает, что:

для всех У студент не получает У

Причем выражение «для всех» понимается как «для всех индивидуумов из какой либо области, выбранной для интерпретации предложений». При интерпретации S1 и S2 по крайней мере один индивидуум У будет связан с именем «стипендия» и поэтому непосредственным следствием S1 является более конкретное предложение:

S1`: получает (студент, стипендию)

Аналогично рассматривается S2 на области интерпретации S1 и S2 и, выбирая для Х, индивидуум с именем «студент», получаем более конкретное предложение:

S2`: получает (студент, стипендию) сдает (успешно, Z, студент)

Теперь имеем два предложения S1` и S2`, которые удовлетворяют условию применимости правила резолюции, а именно наличию одинаковых предикатов в левой части импликации и в отрицании. Поэтому резольвентой S1` и S2` будет:

S:  сдает (успешно, Z, студент)

Предикат

получает (студент, стипендию)

называется общим примером родительских предикатов

получает (Х, стипендию)

получает (студент, У)

и получен с помощью унификатора вида

= { Х:= студент, У:= стипендия}

4.5.5. Унификаторы и примеры унификации

Унификатором называется множество присваиваний вида

= {X1:= t1, ..., Xn:= tn}

где Хi - переменная, а ti – терм, применение которых к двум выражениям дает одинаково общие примеры.

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

Рассмотрим ряд примеров унификации (таблица 4.1):

Таблица 4.1

Примеры унификации

Родительские
предложения

Унификатор

Общий пример

p(5), p(5)

- пустое множество
(не заменяется ни одна переменная)

p(5)

p (x), p(5)

= {x:=5}

p(x) = p(5) = p(5)

p(x), p(y)

= {x:=y}

p(y)

p(x, y), p(5, x)

= {x:=5, y=x} =
   =
{x:=5, y:=5}

p(x,y) = p(5,x) = p(5,5)

 p(5, x)

p(x, y) ← q(x)

= {x:=5, y:=5}

p(5,5)

резольвента:

s: q(x) = q(s)

4.5.6. Решение задач и извлечение ответа.

Решение задачи с использованием логического программирования разбивается на 3 этапа:

На первом этапе необходимо сформулировать наши знания и допущения о предметной области в виде множества ППФ

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

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

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

D1, D2, ... , D

Если может быть построен вывод, заканчивающийся отрицанием

Dn  = (противоречие) ,

то этот вывод, называемый успешным выводом, сразу дает решение поставленной задачи.

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

На первом этапе необходимо в виде ППФ сформулировать наши знания о вычислении факториала, которые можно представить двумя предложениями:

S1 :  факториал (0,1)

S2 : факториал (х,у) х>0, факториал (х-1, у), у=у х

На втором этапе конкретную задачу, например, вычисление значение факториала трех (т.е. 3!), формулируем в виде запроса как исходного отрицания:

D1: факториал (3, z)

На третьем этапе система логического вывода выполнит следующую последовательность этапов вывода на основе резолюции (таблица 4.2)

Таблица 4.2

Вывод на основе резолюции

Шаг
вывода

Родительские
предложения

Унификатор

Отрицание
(резольвента)

1

D1, S2

= {x:=3, y:=z, y1:=y/x} =
   = {x:=3 , y
1:= z/3}

D2: факториал (2, z/3)

2

D2, S2

= {x:=2, y:=z/3, y1:=y/x} =
   = {x:=2 , y
1:= z/6}

D3: факториал (1, z/6)

3

D3, S2

= {x:=1, y:=z/6, y1:=y/x} =
   = {x:=1 , y
1:= z/6}

D4: факториал (0, z/6)

4

D4, S1

= {z/6:=1} = {z:=6}

Полученное на 4 шаге противоречие подтверждает отрицание D1, а стало быть вывод является успешным и дает решение:

факториал (3,z), с унификатором = {z:=6}

т.е.   факториал (3,6)

Откуда ответ, выдаваемый системой логического вывода: z:=6


 

А также другие работы, которые могут Вас заинтересовать

15681. Повесть о настоящем человеке 52.95 KB
  Повесть о настоящем человеке Великая Отечественная Война II Мировая Война Мы со слезами на глазах произносим эти слова но и с гордостью за то что выстояли это испытаниечто не сломалисьмы русский народ А как же создавалась победа А создавалась она героизмом и
15682. Причины и повод Второй мировой войны 73.68 KB
  А с чего все началось Прошло уже шесть с половиной десятилетий после окончания Великой Отечественной войны но до сих пор остаются нерешенными некоторые вопросы. До сих пор мы помним и с интересом рассуждаем о причинах Великой Отечественной Войны. Почему страна была
15683. УДОСКОНАЛЕННЯ СИСТЕМ РОЗПОДІЛУ ТА ЗРОСТАННЯ ДОХОДІВ НАСЕЛЕННЯ В УКРАЇНІ 339.5 KB
  Розподіл доходів - це стадія відтворення, яка займає проміжне місце між виробництвом і споживанням. Реалізована на ринку про-дукція перетворюється на грошову виручку. Після вилучення з неї вартості спожитих засобів виробництва залишається грошовий...
15684. Методы политического влияния и манипулирования 203 KB
  Методы политического влияния и манипулирования Методы политического влияния Усиление роли политического влияния в жизни общества являясь симптомом перехода от тоталитарных форм правления к демократическим предопределяет интерес к механизмам осуществления влиян
15685. Психология воздействия 41.5 KB
  В современную эпоху главным орудием воздействия на массы стало телевидение. Как заявил в 1972 году директор французского ведомства по радио и телевидению ...в умелых руках телевидение превращается в невиданное ранее оружие. Тот кто владеет им может направлять общественн
15686. Воздействие политической пропаганды 127 KB
  Воздействие политической пропаганды И зучение воздействия на аудиторию массмедийных сообщений или символов политических по своей природе или имеющих политические последствия представляет собой одно из направлений широкой области исследований воздействия пол
15687. МАНИПУЛИРОВАНИЕ ЛИЧНОСТЬЮ: Организация, способы и технологии информационно-психологического воздействия 1.19 MB
  Георгий Грачев Игорь Мельник МАНИПУЛИРОВАНИЕ ЛИЧНОСТЬЮ:Организация способы и технологии информационнопсихологического воздействия Комплексно рассматривается проблема манипулирования людьми с использованием различных средств способов и технологий информаци
15688. СОЦИАЛЬНО-КУЛЬТУРНОЕ ВОЗДЕЙСТВИЕ МАССОВОЙ КОММУНИКАЦИИ: ПОЛИТИЧЕСКИЕ АСПЕКТЫ 926 KB
  СОЦИАЛЬНОКУЛЬТУРНОЕ ВОЗДЕЙСТВИЕ МАССОВОЙ КОММУНИКАЦИИ: ПОЛИТИЧЕСКИЕ АСПЕКТЫ ИССЛЕДОВАНИЕ ОПЫТА ЗАПАДА АННОТАЦИЯ Книга представляет собой электронную версию книги В.П. Терина МАССОВАЯ КОММУНИКАЦИЯ. ИССЛЕДОВАНИЕ ОПЫТА ЗАПАДА М. 2000. Духовная жизнь стран Зап...
15689. Основы воздействия СМИ 3.74 MB
  Основы воздействия СМИ Книга посвящена воздействию которое оказывают средства массовой информации на зрителей и слушателей. Авторы дают краткий исторический обзор темы анализируют феномен воздействия СМИ на массовую аудиторию и научные исследования данного явлени