Какие предикаты обычно используются для представления свойств объектов

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

При проектировании модели представления знаний следует учесть два требования: однородность представления; простоту понимания.

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

Классификация методов моделирования знаний с точки зрения подхода к их представлению в ЭВМ показана на рис. 13.1.

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

Модели на основе эвристического подхода.Представление знаний тройкой «объект — атрибут — значение». Один из первых методов моделирования знаний. Как правило, используется для представления фактических знаний в простейших системах.

Примеры.

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

Продукционная модель. Модель правил; модель продукций — от англ. production — изготовление, выработка. В настоящее время наиболее проработанная и распространенная модель представления знаний, в частности в ЭС.

Модель предусматривает разработку системы продукционных правил (правил продукций), имеющих вид:

ЕСЛИ А1И А2 И … И Аn, ТО B1ИЛИ В2ИЛИ … ИЛИ Вт,

где Аiи Bj — некоторые высказывания, к которым применены логические операции И и ИЛИ. Если высказывания в левой части правила (ее часто называют антецедент — условие, причина) истинно, истинно и высказывание в правой части (консеквент — следствие).

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

Пусть в некоторой области памяти (базе знаний) хранятся следующие правила (суждения):

· правило 1: ЕСЛИ в стране происходит падение курса национальной валюты, ТО материальное положение населения ухудшается;

· правило 2: ЕСЛИ объемы производства в стране падают, ТО курс национальной валюты снижается;

· правило 3: ЕСЛИ материальное положение населения ухудшается, ТО уровень смертности в стране возрастает.

Если на вход системы поступит новый факт (факт 1) «В стране высокий уровень падения объемов производства», то из правил можно построить цепочку рассуждений и сформулировать два заключения:

где заключение 1 (промежуточный вывод) — «Материальное положение населения ухудшается»; заключение 2 (окончательный вывод) — «В стране возрастает уровень смертности».

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

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

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

Фреймовая модель. Сравнительно новая модель представления знаний. Само понятие «фрейм» (англ. frame — рама, рамка, скелет, сгусток, сруб и т.д.) было введено в 1975 г. М.Минским (M.Minsky, США).

Фрейм — это минимальная структура информации, необходимая для представления знаний о стереотипных классах объектов, явлений, ситуаций, процессов и др. С помощью фреймов можно моделировать знания о самых разнообразных объектах интересующей исследователя предметной области — важно лишь, чтобы эти объекты составляли класс концептуальных (повторяющихся: стереотипных) объектов, процессов и т. п. Примерами стереотипных жизненных ситуаций могут служить собрание, совещание; сдача экзамена или зачета; защита курсовой работы и др. Примеры стереотипных бытовых ситуаций: отъезд в отпуск, встреча гостей, выбор телевизора, ремонт и др. Примеры стереотипных понятий: алгоритм; действие; методика и др. На рис. 13.2 представлен фрейм технологической операции «соединять» [21].

Данный фрейм описывает ситуацию «Субъект X соединяет объект Y с объектом Z способом W».

Наполняя слоты конкретным содержанием, можно получить фрейм конкретной ситуации, например: «Радиомонтажник соединяет микросхему с конденсатором способом пайки». Заполнение слотов шанциями называют активизацией фрейма.

С помощью фреймов можно моделировать как процедурные, так и декларативные знания. На рис. 13.2 представлен пример представления процедурных знаний.

На рис. 13.3 приведен пример фрейма «технологическая операция», иллюстрирующий представление декларативных знаний для решения задачи проектирования технологического процесса.

По содержательному смыслу фрейма выделяют [21]:

· фреймы-понятия;

· фреймы-меню;

· фреймы с иерархически вложенной структурой.

Фрейм-понятие — это фрейм типа И. Например, фрейм «операция» содержит объединенные связкой И имена слотов «что делать», «что это дает», «как делать», «кто делает», «где делать» и т.д., а фрейм «предмет» — слоты с именами «назначение», «форма», «вес», «цвет» и т.д.

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

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

Значения слотов могут содержать ссылки на так называемые присоединенные процедуры. Различают два вида присоединенных процедур: процедуры-демоны; процедуры-слуги.

Процедуры-демоны присоединяются к слоту и активизируются при изменении информации в этом слоте (выполняют вспомогательные операции — например, автоматически корректируют информацию во всех других структурах, где используется значение данного слота).

1. Процедура «Если — добавлено» (IF —ADDED) выполняется, когда новая информация помещается в слот.

2. Процедура «Если — удалено» (IF —REMOVED) выполняется, когда информация удаляется из слота.

3. Процедура «Если —нужно» (IF —NEEDED) выполняется, когда запрашивается информация из пустого слота.

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

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

Модель семантической сети (модель Куилиана). Семантическая сеть — это направленный граф с поименованными вершинами и дугами, причем узлы обозначают конкретные объекты, а дуги — отношения между ними [21]. Как следует из определения, данная модель представления знаний является более общей по отношению к фреймовой модели (иными словами, фреймовая модель — частный случай семантической сети). Семантическую сеть можно построить для любой предметной области и для самых разнообразных объектов и отношений.

В семантических сетях используют три типа вершин:

· вершины-понятия (обычно это существительные);

· вершины-события (обычно это глаголы);

· вершины-свойства (прилагательные, наречия, определения).

Дуги сети (семантические отношения) делят на четыре класса:

· лингвистические (падежные, глагольные, атрибутивные);

· логические (И, ИЛИ, НЕ);

· теоретико-множественные (множество — подмножество, отношения целого и части, родовидовые отношения);

· квантифицированные (определяемые кванторами общности и существования ).

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

Приведем два примера.

На рис. 13.4 представлена семантическая сеть для предложения (ситуации) «студент Табуреткин добросовестно изучает новый план счетов на 2002 г. перед сдачей экзамена по дисциплине «Бухгалтерский учет».

Рис. 13.5 содержит фрагмент семантической сети для понятия «автомобиль».

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

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

· громоздкость, сложность построения и изменения;

· потребность в разнообразных процедурах обработки, связанная с разнообразием типов дуг и вершин.

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

Очень коротко остановимся на ставшей классической предикатной модели представления знаний. Первые попытки использовать такую модель относятся к 50-м гг. прошлого века. Дадим несколько определений.

Пусть имеется некоторое множество объектов, называемое предметной областью. Выражение P(x1, x2, …, хn), где х1…xn — предметные переменные, а Р принимает значения 0 или 1, и называется логической функцией, или предикатом.

Предикат Р(х1, х2, …, хn) задает отношение между элементами х1 х2, …, хnи обозначает высказывание, что «х1, х2, …, хnнаходятся между собой в отношении Р». Например, если А — множество целых чисел, а Р(а) — высказывание «а — положительное число», то Р(а) = 1 при а > 0 и Р(а) = 0 при а £0.

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

Предикат от п переменных называют n-местным.

Одноместные (унарные) предикаты отражают свойства определенного объекта или класса объектов. Многоместные предикаты позволяют записывать отношения, которые существуют между группой элементов.

Если а — тоже предикат, то Р(а) — предикат 2-го порядка и далее до n-го порядка.

Приведем примеры различных предикатов.

1. Унарный предикат (высказывание) «река впадает в Каспийское море» имеет значение 1, если «река» = «Волга», и значение 0, если «Река» = «Днепр».

2. Двухместный предикат «x1не меньше х2» может иметь значение 1 или 0 в зависимости от значений х1и х2. Если значение предиката тождественно равно 1 при любых значениях предметных переменных, он называется тавтологией.

В аппарат исчисления предикатов входят также символы функций (обычно обозначаемые латинскими буквами f, g, h и т.д.), задаваемых на множестве предметных переменных, и кванторы общности и существования .

3. Представление с помощью предиката знаний, заключенных в теореме Пифагора: P{g[f(x),f(y)],f(z)}, где предикат Р— «быть равным», функция g(x, у) = х + у; функция f(х) = х2.

Иногда используется такая форма записи:

РАВНЫ [СУММА (КВАДРАТ(х), КВАДРАТ(y)), КВАДРАТ (z)].

Предикат Р равен 1, если х, у, z — соответственно длины катетов и гипотенузы прямоугольного треугольника.

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

Источник

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 14 мая 2019;
проверки требует 1 правка.

Предика́т (лат. praedicatum «заявленное, упомянутое, сказанное») — это утверждение, высказанное о субъекте. Субъектом высказывания называется то, о чём делается утверждение.

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

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

Определение[править | править код]

Предика́т (-местный, или -арный) — это функция с множеством значений (или {ложь, истина}), определённая на множестве . Таким образом, каждый набор элементов множества характеризуется либо как «истинный», либо как «ложный».

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

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

Предикат называют тождественно-истинным и пишут:

если на любом наборе аргументов он принимает значение .

Предикат называют тождественно-ложным и пишут:

если на любом наборе аргументов он принимает значение .

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

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

Примеры[править | править код]

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

Более житейским примером может служить предикат ПРОЖИВАЕТ для отношения « проживает в городе на улице » или ЛЮБИТ для « любит » для и принадлежащих , где множество — это множество всех людей.

Предикат — это то, что утверждается или отрицается о субъекте суждения.

Операции над предикатами[править | править код]

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

Логические операции[править | править код]

Конъюнкцией двух предикатов A(x) и B(x) называется новый предикат , который принимает значение «истина» при тех и только тех значениях х из Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.
Множеством истинности Т предиката является пересечение множеств истинности предикатов A(x) — T1 и B(x) — T2, то есть T = T1 ∩ T2.
Например: A(x): «x — чётное число», B(x): «x кратно 3».
A(x) B(x) — «x — чётное число и x кратно 3».
То есть предикат «x делится на 6».

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

Отрицанием предиката A(x) называется новый предикат, который принимает значение «истина» при всех значениях x из T, при которых предикат A(x) принимает значение «ложь», если A(x) принимает значение «истина».

Множеством истинности предиката x X является дополнение T’ к множеству T в множестве X.

Импликацией предикатов A(x) и B(x) называется новый предикат , который является ложным при тех и только тех значениях x из T, при которых A(x) принимает значение «истина», а B(x) — значение «ложь», и принимает значение «истина» во всех остальных случаях.
Читают: «Если A(x), то B(x)».

Например. A(x): «Натуральное число x делится на 3». B(x): «Натуральное число x делится на 4», можно составить предикат: «Если натуральное число x делится на 3, то оно делится и на 4».
Множеством истинности предиката является объединение множества T2 — истинности предиката B(x) и дополнения к множеству T1 истинности предиката A(x).

Кванторные операции[править | править код]

См. также[править | править код]

Исчисление предикатов
Предикатив
Определяющий предикат

Литература[править | править код]

Гуц А.К. Математическая логика и теория алгоритмов. — Наследие, Диалог-Сибирь, 2003.
Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука, Физматлит, 1987.
Игошин В.И. Математическая логика и теория алгоритмов. — Academia, 2008.
Клини С.К. Математическая логика. — М.:Мир, 1973.
Мендельсон Э. Введение в математическую логику. — М. Наука, 1971.
Новиков П.С. Элементы математической логики. — М.:Наука, 1973.

Источник

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

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

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

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

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

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

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

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

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

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

Константа применяется для обозначения конкретных объектов реального мира. Пример: ласточка, птица, один, 2 и т.д.
Переменные используются для обозначения одного из возможных объектов реального мира или совокупности этих объектов. В Прологе идентификаторы переменных начинаются с заглавной буквы. Пример: Некто, X, Who, Вещь.
Функции (структуры) – последовательность из нескольких констант или переменных, заключенных в круглые скобки, которые следуют за функциональным символом (функтором).
Пример:
сумма (1,2);
+(1,2);
удвоить (X).
Функторы обозначают операторы, которые после воздействия на какой-либо объект или группу объектов возвращают некоторое значение.

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

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

Пример:
является (ласточка, птица).
отец (X, Джон).

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

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

Таблица 4.1

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

, (или &)	∨	¬	←	↔
“и”	“или”	“не”	“если”	“тогда и только”

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

¬
& , ∨
← , ↔

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

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

где является( _ , _ ), имеет( _ , _ ) и владеет( _ , _ ) – это двуместные атомарные предикаты, которые обычно записывают в виде: является/2, имеет/2, владеет/2, а сиволы “,” и “←” представляют собой логические связки.

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

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

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

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

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

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

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

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

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

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

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

любит (Х, У),

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

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

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

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

Термом является либо константа, либо переменная, либо кортеж из n термов, перед которым стоит функтор.
Предикат — это кортеж из n термов, перед которым стоит предикатный символ.
Атомарный предикат является логической формулой.
Если F и G — логические формулы, то (F), F&G, F∨G, ¬F, F←G; F↔G — также являются логическими формулами.
Если F(X) — логическая формула, то оба выражения (∀Х)F(X) и (∃X)F(X) — также является логическими формулами.
Все результаты, получаемые повторением конечного числа n1 – n6, являются логическими формулами.

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

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

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

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

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

факт: А
отрицание: ¬(А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, A ← B
———– (*)
¬B

и соответствует следующему умозаключению:
допуская, что: НЕ А и А ЕСЛИ В,
выводим: НЕ В
В еще более простом случае, когда S1 – отрицание, а S2 – факт, т.е.:
S1: ¬А
S2: А
применение правила резолюции даст резольвенту – пустое отрицание
s: ∅
и означает противоречие.

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

¬A, A
——- (**)
∅

и резолюцией является рассуждения типа
допуская, что: НЕ А и А
выводим противоречие.

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

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 – представляет собой факт:

S1: ¬(A1, … , Ak, … , An)
S2: Ak
При этом факт Аk является одним из предикатов отрицания S1. В этом случае шаг вывода будет заключаться только в вычеркивание предиката Аk из S1. При этом получаем резольвенту вида

s: ¬(A1, … , Ak-1, Ak+1, … , An)

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

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

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

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

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

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

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

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

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

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

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

ШАГ 1

Система на первом шаге применит правило (*) к родительским предложениям S1 и S2 и получит резольвенту:
s: ¬сдает (успешно, сессию, студент)
ШАГ 2

Используя правило (**) к двум родительским предложениям s и S3, система выводит противоречие:
s’: ∅

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предикат

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

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

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

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

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

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

Θ = {X1:= t1, … , Xn:= tn}

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

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

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

Таблица 4.2

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

Родительские предложения	Унификатор	Общий пример
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(5)

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

На первом этапе необходимо сформулировать наши знания и допущения о предметной области в виде множества ППФ.
На втором этапе нужно выразить конкретную задачу, поставленную на предметной области, как запрос об одном или нескольких отношениях. Обычно запрос ставится как исходное отрицание.
Составлением допущений и исходного запроса завершается работа программиста, цель которой — формулировка задачи.
Третий шаг выполняется компьютером, который пытается решить задачу, строя доказательство от противного. Он строит вывод сверху вниз, начиная с исходного отрицания, и порождает последовательность отрицаний
D1, D2, … , Dn
Если может быть построен вывод, заканчивающийся отрицанием
Dn = ∅ (противоречие) ,
то этот вывод, называемый успешным выводом, сразу дает решение поставленной задачи.

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

S1 : факториал (0,1)
S2 : факториал (X,Y) ← X>0, факториал (X-1, Y1), Y = Y1 * X.

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

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

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

Таблица 4.3

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

Шаг вывода	Родительские предложения	Унификатор	Отрицание (резольвента)
1	D1, S2	Θ = {X:=3, Y:=Z, Y1:=Y/X}= = {X:=3 , Y1:= Z/3}	D2: ¬ факториал (2, Z/3)
2	D2, S2	Θ = {X:=2, Y:=Z/3, Y1:=Y/X}= = {X:=2 , Y1:= Z/6}	D3: ¬ факториал (1, Z/6)
3	D3, S2	Θ = {X:=1, Y:=Z/6, Y1:=Y/X}= = {X:=1 , Y1:= Z/6}	D4: ¬ факториал (0, Z/6)
4	D4, S1	Θ = {Z/6:=1} = {Z:=6}	∅

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

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

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

Рассмотрим пример построения рекурсивной процедуры для вычисления факториала любого целого числа. Из определения факториала известно, что 0!=1, а факториал любого числа N может быть вычислен как факториал N-1, умноженный на N. Это определение является рекурсивным, поскольку сводит задачу нахождения N! к более простой задаче нахождения (N-1)!, а затем умножения полученного значения на N.

Для обозначения факта, что факториал числа N равен R, используем предикат f(N, R), рекурсивное определение которого будет иметь вид, приведенный на