23664

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

Лекция

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

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

Русский

2013-08-05

337.5 KB

30 чел.

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


 

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

53365. Ігри на матеріалі економічної термінології, спрямовані на збагачення активного словника та вдосконалення культури мовлення учнів 179 KB
  Методична порада. Для проведення ігор діти класу ділиться на гомогенні або гетерогенні групи. Обирається в кожній групі лідер. Завдання ігрової вправи виконують усі разом, доповідають про виконання тільки лідери. Вимпелом переможця нагороджується та група, яка першою за відведений час виконає правильно завдання.
53367. Ігрові хвилинки на уроках музики 48.5 KB
  Мета даної публікації не заглиблюючись у наукові аспекти теорії гри надати педагогові реальну допомогу на шляху впровадження ігрових форм у навчальновиховний процес. Дуже подобаються школярам варіанти психологічних ігрових вправ після проведення яких бажано аналізувати та обговорювати результати отримані під час гри.Кожній дитині надати можливість для виходу її емоцій після чого бажано алізувати та обговорювати результати отримані...
53368. Ігрові технології на уроках 39.5 KB
  Шіллер наприклад стверджував що античні ігри божественні і можуть служити ідеалом будьяких інших видів дозвілля людини. У Древньому Китаї святкові ігри відкривав імператор і сам у них брав участь. Складність визначається різноманіттям форм гри способів участі в ній партнером та алгоритмами проведення гри.
53369. Объемное моделирование и конструирование из бумаги. Игрушки из бумажных полосок 172.5 KB
  Игрушки из бумажных полосок Вид урока Урок беседа Тип урока Урок изучения нового материала Студенты преподаватели Айрапетова Мария Сергеевна Гусева Анна Павловна Ершова Дарья Дмитриевна Максимова Марина Вадимовна Государственный социальный заказ Во исполнение Закона Российской Федерации Об образовании. Добиваться: применения различных форм методов средств технологий при проведении образовательного урока; установления взаимодействия с различными субъектами образовательного процесса. Технологическая карта урока Триединые...
53370. Розвиток слухової уваги, слухової пам’яті та фонематичного сприймання у дітей дошкільного віку 68 KB
  Діти стають у коло непомітно для ведучого вони передають за спиною один одному дзвіночок. Логопед розрає дітям ведмедиків з зображенням цих предметів потім за ширмою озвучує ці предмети а діти повинні відгадати який ведмедик шумить. Дидактична гра Хто кличе Діти по черзі називають ім’я ведучого який стоїть до них спиною. Потім гра ускладнюється і діти кличуть ведучого: Ау то голосно то тихо в залежності від того що скаже логопед: Далеко пішли у ліс Близько пішли у ліс.
53371. Учет косвенных расходов в составе себестоимости продукции. Синтетический учёт движения нематериальных активов 22.77 KB
  Косвенные затраты — затраты, которые, в отличие от прямых затрат, не могут быть непосредственно отнесены на себестоимость одного конкретного вида продукции. Косвенные затраты относятся одновременно ко всем видам продукции и распределяются между ними условно: общепроизводственные и общехозяйственные расходы, часть расходов на продажу и др
53372. Дидактические игры как средство активизации учащихся при изучении таблицы умножения 52.5 KB
  Хочу рассказать о некоторых дидактических математических играх, которые я использую на уроках с целью активизации учащихся при формировании вычислительных навыков. Навык, как известно, приобретается в результате многократных повторений одних и тех же операций. Чтобы избежать однообразия в шлифовке табличных случаев умножения и деления, провожу упражнения в игровой, занимательной форме.
53373. Роль ігор-драматизацій в навчанні дошкільників англійської мови 97 KB
  Всі етапи роботи з казкою здійснюються разом з дітьми. Ініціативу розподілу ролей я надаю малечі (за бажанням), разом з тим, тактовно корегую їх вибір, адже дітям з низьким або середнім рівнем розвитку бажано надати роль, яка є невеличкою за обсягом, не дуже складною та не містить у собі тих мовних структур, які викликають труднощі у дитини (зокрема це стосується звуковимови), щоб не зникло бажання приймати участь у виставі.