Исчисление предикатов. Пропозициональная функция



Скачать 245.53 Kb.
Дата15.01.2013
Размер245.53 Kb.
ТипДокументы

  • Исчисление предикатов. Пропозициональная функция - это выражение, содержащее переменные и превращающиеся в высказывание при подстановке вместо этих переменных соответствующих аргументов. Примерами пропозициональных функций могут служить: “ Если p, то q ”. Это выражение превращается в высказывание, если вместо p и q подставить, например, высказывания: “ Телу придать скорость более 7,9 км/сек”, “ Тело становится спутником Земли”. Пропозициональная функция, аргументами, которой являются имена (предметные переменные), называется предикатом. Предикат - это функция от любого числа аргументов, принимающая истинностные значения: истина или ложь (И или Л; 1 или 0). Аргументы принимают значения из произвольного конечного или бесконечного множества M, называемого предметной областью. Если Р есть n - местная предикатная переменная, а Хi ,…, Хn предметные переменные (аргументы предиката), то выражение Р(Х­12 ,…,Хn) есть атомарная (элементарная) формула. Эта формула трактуется как высказывание, гласящее, что объекты Х12 ,,…,Хn связаны отношением Р. Например, высказывание “Сидоров работает преподавателем” может быть представлено предикатом(формулой):РАБОТАЕТ ( СИДОРОВ,ПРЕПОДАВАТЕЛЬ).


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

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

В логике исчисления предикатов объекты представляются с помощью термов:

1.Переменные представлены прописными буквами: x, y, z, u, v, w или этими же буквами с индексами.

2.Константы - представлены строчными буквами a, b, c, d, e или этими же буквами с индексами.

3.Функциональные символы – представлены буквами f, g, h или этими же буквами с индексами.

4.Предикатные символы представлены буквами p, q, r, s, t или этими же буквами с индексами.

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

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

6.Вспомогательные символы – круглые скобки.

7.Терм определяется индуктивно с помощью пунктов1 – 3.

  1. Переменные и константы являются термами.

  2. Если f – функция m аргументов и t1,…,tm являются термами, то f(t1,…,tm) - терм.

  3. Термами являются понятия определенные в пунктах 1,2.

В любой предметной области определив константы, функциональные и предикатные символы, можно построить логические формулы, описывающие знания конкретной предметной области. Если А и логические формулы, а Х –переменная то (А) (В), (А) ( В), (А) ( В), x (А), y ( В) - являются логическими формулами.

Например, логической формулой является выражение


(( y ( x (p(x ,y)))) (( q ( f (a))))) ( r(u ,b).

Уменьшив количество скобок логическая формула будет иметь вид:

( yx p(x ,y) q ( f (a))) r(u ,b ).

Атомарным предикатом называется последовательность из термов ( константа, переменная или функция), заключенная в круглые скобки, следущими за предикатным символом, имя которого выражено некоторой конечной последовательностью букв. Например, атомарным предикатом является предикат ОТЕЦ( x,y), ЛЮБИТ(x,y).

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

xy ЛЮБИТ(x,y): для всех x существует человек y ,которого любит x .

y x ЛЮБИТ(x,y): существует такой человек y ,что его любят все x .

xy ЛЮБИТ(x,y): все люди любят всех людей.

xy ЛЮБИТ(x,y): существует человек, который любит всех людей.

xx ЛЮБИТ(x,y): для каждого человека существует человек,который его любит.

xy ЛЮБИТ(x,y): существует человек, который кого-нибудь любит.

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

Приведение формул к стандартной (нормальной) форме.

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

  1. Исключение импликаций и эквивалентностей.

Из логики высказываний известно, что α β α β. Поэтому на этом этапе с помощью этой формулыисключаем все импликации.

Формула вида: (х, мужчина (х) человек (х)) будет преобразована в формулу такого вида:

( х, мужчина (х) человек (х))

  1. Перенос отрицания внутрь формулы. Непосредственно к атомам.

Формула вида: (человек (цезарь) существует (цезарь)) преобразуется в формулу такого вида:

человек (цезарь) существует (цезарь), а формула ( х, человек (х)) преобразуется в формулу

( х, человек (х))

Здесь преобразование основывается на формулах:

( ) значит то же самое, что и ( ) ( )

( v, p) значит то же самое, что и (v, p)

(v, p) значит то же самое, что и (v, p)

3 Переименование переменных.

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

4.Вынесение кванторов общности в начало формулы.

Формула (Х, мужчина(Х) (У, женщина(У) нравиться(Х,У))) преобразуется в формулу (Х, (У, мужчина(Х) ( женщина(У) нравиться(Х,У)))).
Так как теперь каждая переменная в этой формуле вводится посредством квантора общности, находящегося в начале формулы, то кванторы сами по себе не несут больше какой либо дополнительной информации. Поэтому можно сократить формулу, опустив кванторы. Необходимо лишь помнить, что каждая переменная вводится посредством не указанного явно квантора, который опущен при записи формулы. Так формулу

(Х, живет (Х) мертвый (Х) ( нравиться (мэри, У) грязный (У)) можно представить так:

(Х, живет (Х) мертвый (Х) ( нравиться (мэри, У) грязный (У)). Эта формула значит ,что какие бы Х и У ни были выбраны, либо Х живет, либо Х мертвый, и либо Мэри нравиться У, либо У – грязный.

5.Сколемизация.

На этом этапе удаляются кванторы существования, путем введения новых констант – сколемовских констант, вместо переменных связанных квантором существования. Например, формула y(y) заменится на формулу (A). Формула (х, женщина (х) мать (х, ирина) в результате сколемизации преобразуется в формулу женщина (q1) мать (q1, ирина) , где А и q1 – новые константы не использованные ранее.

В общем случае , если переменная , связанная квантором существования, встречается в каком либо литерале вместе с переменными, связанными квантором общности, приходится, чтобы избавиться от квантора общности, вводить специальную функцию( функция Сколема) F(x), зависящую от переменных, связанных квантором общности, вместо переменной связанной квантором существования.

Формула x α(x) y((y) y(x,y))будет заменена на формулу x α(x) ( F(x) y(x,F(x)). Формула xy ЛЮБИТ(x,y) будет заменена на формулу x ЛЮБИТ(x, f(x)).

Если в предикатной формуле все кванторы выведены за скобки и стоят непосредственно перед формулой, то такая форма представления носит названия префиксной нормальной формы. Приоритетность действия кванторов,имеющихся в префиксной форме представления определяется в порядке следования слева направо. Например, формула x yz F(x, y, z) имеет смысл, что “для всех x существует некоторый y, такой что F(x, y, z) истина при всех z. Из этой формулы следует, что переменной, которая влияет на связанную квантором переменную y, является только x, значит формулу можно переписать в следующем виде: x z F(x, f(x), z).

Если исходная логическая формула есть x z y F(x, y, z) , переменными влияющими напеременную с квантором существования, являются x и z ,то получим x z F(x, f(x, z), z). Если переменная, связанная квантором существования, является крайней слева, то такую формулу можно заменить функцией без аргументов, т.е. константой xy ЛЮБИТ(x, y)= ЛЮБИТ(x, y). В случае в одной логической формуле имеется более двух связанных квантором существования переменных, то сколемовская функция также будет распадаться на различные функции. Например, x yzu F(x, y, z, u) = x z F(x, f(x), z, q(x,z)).

6.Использование дистрибутивных законов для символов и .
На этом этапе исходная формула исчисления предикатов претерпела довольно много изменений. Формула больше не содержит в явном виде кванторов, а из логических связок в ней остались лишь и ( помимо отрицания, входящего в состав литералов). Теперь формула преобразуется к специальному виду и конъюнктивной нормальной форме, характерной тем, что дизъюнктивные члены формулы не содержат внутри себя конъюнкцию. таким образом. формулу можно преобразовать к такому виду, когда она будет представлять последовательность элементов, соединенных друг с другом конъюнкциями, а каждый элемент является либо литералом, либо состоит из нескольких литералов, соединенных дизъюнкцией. Чтобы привести формулу к такому виду, необходимо использовать следующие два тождества:
( А В) С эквивалентно (А С) (В С)

А(ВС) эквивалентно (А В) (А С)
Так, например, формула
выходной (Х) ( работает (крис, Х) (сердитый ( крис) унылый (крис)))
(Для каждого Х либо Х – выходной день, либо Крис работает в день Х и при этом он либо сердитый, либо унылый) эквивалентно следующей формуле:

выходной (Х) ( работает (крис, Х))

(выходной (Х) (сердитый ( крис) унылый (крис))).

( Для каждого Х, во-первых ,Х является выходным днем или Крис работает в день Х; во-вторых, либо Х – выходной, либо Крис сердитый или унылый)

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

( А В) ( С ( D E))

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

( А В) ( С ( D E))

( А (В С) ( D E))

( А В) (( С D) E)

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

А В С D E

и порядок записи этих формул не имеет значения.  Поэтому формулу можно выразить короче, опустив знак и записав ее в виде совокупности {А, В, С, D, E}. Формулы, являющиеся элементами совокупности, полученной в результате преобразования некоторой формулы исчисления предикатов, называются дизъюнктами. Теперь исходная формула представлена в стандартной форме. Стандартная форма состоит из совокупности дизъюнктов, каждый из которых представляет совокупность литералов. Литерал – это либо атамарная формула, либо отрицание атомарной формулы.
Основным лексическим категориям (высказываниям, именам, функторам) выделяются важнейшие разделы логик - логическая теория высказываний (логика высказываний, логика имен, классов, отношений ). (смотри читаемые специальные курсы).
Рассмотрим все этапы приведения формы к стандартному виду.

(X, (Y,человек(Y) почитает (X,Y)король(X)))

Формула трактуется так:

Для каждого X, если каждый Y является человеком, почитающим X, то X – это король.

Проведем устранение (исключение) импликации, согласно этапу (1), тогда получим:

(X, ( (Y, человек (Y) почитает (Y,X))) король(X))

Произведем перенос отрицания внутрь формулы согласно этапу (2) и получим:

(X, (Y, человек (Y) почитает (Y,X)) король(X))

Далее проведем сколемизацию по этапу (5) и будем иметь:

(X, (человек (f1(X)) почитает (f1(X),X)) король(X))

где f1 – сколемовская функция

Теперь производится удаление кванторов всеобщности (этап (4)) и будем иметь формулу:

(человек (f1(X)) почитает (f1(X),X)) король(X)

Теперь полученную формулу преобразуем к конъюктивной нормальной форме, этап (6)

(человек (f1(X)) король(X)) ( почитает (f1(X)) король (X))

Переход к дизъюнктивной форме, этап (7).

Последняя формула содержит два дизъюнкта. Первый дизъюнкт содержит два литерала: человек (f1(X)) и король(X), второй дизъюнкт имеет литералы: почитает (f1(X)) и король (X).

Получим множество дизъюнктов:

{ человек (f1(X)), король(X), почитает (f1(X),X)}


Механизм резолюций Робинсона.

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

Задача Р может быть представлена в виде (форме) следующего кортежа:
Р=< Модель, Исходное_состояние, [Критерий], Решение, Решающая_процедура, [Доказательство]> (1)
Доказательство может потребоваться как свидетельство того, что отыскиваемое решение действительно удовлетворяет критерию задачи или служит допустимой интерпретацией для заданной модели.

При решении задачи (1) один из эффективных подходов базируется на доказательстве теоремы о существовании решения. Эта идея доказательства принадлежит Р. Ковальскому. Теорема существования решения формируется следующим образом:

S (модель (s) Sol (решение (s, sol))), (2)

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

Доказательство демонстрирует, что некоторая ППФ является теоремой на заданном множестве аксиом , т.е. результатом, логически выводимом из аксиом. Положим, что есть множество, состоящее из W ППФ, а именно: A1, A2, …, An, и пусть ППФ, для которой требуется выяснить, является ли она теоремой, есть B. В таком случае можно сказать, что доказательство показывает справедливость (истинность ППФ вида (2))

A1 A2 … An (3)

При любой её интерпретации или можно сказать по иному: такое определение эквивалентно тому, что отрицание формулы (3), т.е. (A1 A2 An B) (4) не выполняется (является ложью) при любой интерпретации. Формула (4) это ППФ, то её можно преобразовать к форме клаузального множества. Пусть это преобразование ППФ есть S. Метод резолюции является одним из методов доказательства возможности преобразования, однако его основная идея состоит: первое в проверке того, содержит или не содержит S пустое предложение, второе – в проверке того, выводится или не выводится пустое предложение из S, если пустое предложение в S отсутствует. Любое предложение Ci из которого образуется S, является совокупностью атомарных предикатов или их отрицаний (предикат и его отрицание вместе называются литералом), соединенных символом дизъюнкции вида C1=Pi1Pi2Pim , (5)

а само S – это конъюнктивная форма, т.е. имеет вид S= С1 С2 … Cn, где условием истинности S является условие истинности всех Ci в совокупности или наоборот условием ложности S является ложность по крайней мере одного из Ci. Из (5) видно, что Ci будет ложным при какой-нибудь интерпретации, если множество {Pi1, …, Pim} будет пустым. Следовательно, если S содержит пустое предложение, формула (4) является ложью, поэтому является ложью и исходная формула (3), а это показывает, что B выводится из группы предикатов A1, A2, …, An, т.е. из E. Второй шаг – наличие пустого предложения в S – означает проверку результата после того, как будут выполнения преобразования с помощью правил вывода в S.
Подстановка

Так как в логике предикатов содержатся переменные, то алгоритм доказательства несколько усложняется. Перед тем, как применить механизм вывода, будет проведена некоторая подстановка в переменные (унификация). Имеются два предиката L(x) и L(a). Положим, что x - переменная, a –константа. В этих предикатах предикатные символы L одинаковы, что нельзя сказать о самих предикатах. Подстановка a в x делает эти предикаты одинаковыми. Целью унификации является обеспечение применение описанного алгоритма доказательства для предикатов. Подстановку t в x принято записывать как {t /x}. Поскольку в одну ППФ может входить более одной переменной, то подстановки записываются в виде множества упорядоченных пар: {t1/x1, t2/x2, …, tn/xn}, где ti – это терма, xi – переменная.
Унификация.

Обозначим группу подстановки {t1/x1, t2/x2, …, tn/xn} через . Тогда для некоторого представления L с переменными {x1, x2, …, xn} производится подстановка термов {t1, t2, …, tm} вместо xi , то результат подстановки обозначается как L.

Если имеется группа различных выражений предиката L, т.е. {L1, L2, …, Lm}, то подстановка (если она существует), такая что все эти выражения становятся одинаковыми L1= L2=…= Lm, называется унификатором для {L1, L2, …, Lm}, а само множество {L1, L2, …, Lm} унифицируемо. Иными словами, то, что подставляем, т.е. (a/x)- запись называется унификатором, а множество {L(x), L(a)} – унифицируемо. Если подстановка вида a/x разбивается на две подстановки u/x и a/w. Результат последовательного выполнения двух подстановок и также является подстановкой. Такая подстановка называется сложной и обозначается в виде ◦. В результате подстановки все переменные будут замещены константами и описательная мощность ППФ будет ограничена. Подстановка является унификатором с самыми минимальными ограничениями, поэтому её принято называть “наиболее общим унификатором” - НОУ. Метод отыскания НОУ из заданной группы предикатных выражений называется алгоритмом унификации.
Пример.

P1=L(a, x, f (q(y)))

P2=L(z, f(z), f (u))

1. Самые первые члены несовпадения слева направо: (a, z)

Подстановка a/z имеем.

P1=L(a, x, f (q(y)))

P2=L(a, f(a), f (u))

2. Несовпадения первых членов слева направо x и f(a)

Подстановка {f(a)/x}

P1=L(a, f(a), f (q(y)))

P2=L(a, f(a), f (u))

Подстановка f(q(u))/f(u)

Оба представления совпадают и НОУ: {a/z, f(a)/x q(y)/y} и подстановки выполняются рекуррентно. Рассмотрим метод резолюции на примере.

Пусть имеется легенда: “Полиция разыскивает всех въехавших в страну, за исключением дипломатов. Шпион въехал в страну, однако распознать личность шпиона может только шпион. Шпион не является дипломатом”. При этих посылках оценить правильным или неправильным является вывод: “Среди полицейских является (имеется, есть) шпион”.

Для доказательства используются следующие предикаты:

Въехал (x): x въехал в страну

Дипломат (x): x является дипломатом

Поиск (x, y): x разыскивает y

Полиция (x): x является полицейским.

Через эти предикаты выразим приведенную в посылках легенду и вывод в форме ППФ.
А1: x [въехал (x) ~дипломат (x) y (поиск (x, y) полиция (y)))]

Читается: (для всех x)если x, не являющийся дипломатом, въехал в страну, то некоторый полицейский y разыскивает этого x.
А2: x [шпион (x) въехал (x) (y) (поиск (y, x) шпион (y))]

Читается: если существует шпион x, который въехал в страну, и некоторый y разыскивает шпиона, то он сам является шпионом.
А3: x [шпион (x) ~дипломат (x)]

Для всех x справедливо, что если x является шпионом, то он не дипломат.
Заключение.

B: (x) [шпион (x) полиция (x)]

Читается: существует такой x, что он является шпионом и полицейским.
А1, А2, А3 B
Эти формулы преобразуем в клаузальную форму
(1) въехал (x) дипломат (x) поиск (f(x), x)

А1 2. въехал (x) дипломат (x) полиция (f(x))
3. шпион (a)

А2 4. въехал (a)

5. поиск
6. шпион (x) дипломат (x)

А3 7. шпион (x) полиция (x)
Алгоритм раздельного доказательства.
8. дипломат (a) [a/x] из (3) и (6)

9. дипломат (a) полиция (f(a)) [a/x] из (2) и (4)

10. полиция [f(a)] из (8) и (9)

  1. дипломат (a) поиск (f(a),a) [a/x] из (1) и (4)

  2. поиск (f(a),a) [a/x] из (8) и (11)

  3. шпион (f(a)) [a/x] из (12) и (5)

  4. полиция (f(a)) [f(a)/y] из (13) и (7)

  5. нуль [ из (10) и (14).


Так используется метод резолюции.

Похожие:

Исчисление предикатов. Пропозициональная функция iconОсновы логического программирования Исчисление высказываний пропозициональная логика
Исчисление высказываний (пропозициональная логика) — это формальная теория, основным объектом которой служит понятие логического...
Исчисление предикатов. Пропозициональная функция iconЛекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка
Исчисление предикатов. Пропозициональная функция iconНормальные формы формул логики предикатов
При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной...
Исчисление предикатов. Пропозициональная функция iconИсчисление предикатов с равенством
Замечание. В формулах подформула называется областью действия квантора соответственно
Исчисление предикатов. Пропозициональная функция iconЛогические подходы к спецификации агентных систем
Если рассматривать логики как средства описания состояния систем, пропозициональная логика и логика предикатов первого порядка позволяют...
Исчисление предикатов. Пропозициональная функция iconІіі. Дифференциальное исчисление главаvi: Производные и дифференциалы
Пусть функция определена на промежутке (возможно бесконечном). Возьмем произвольную точку и придадим ей произвольный прирост такой,...
Исчисление предикатов. Пропозициональная функция iconС. 38. Модель согласования выводов из теорий, используемых для объяснения особых состояний сознания (осс)
Предлагается использовать алгебраические модели конструктивной логики (амкл), отображающие интуиционистское исчисление предикатов...
Исчисление предикатов. Пропозициональная функция iconЛабораторная работа №1 по дисциплине "Системы искусственного интелекта"
Исчисление предикатов первого порядка является теоретической основной множества формализмов методов искусственного интеллекта. Задачи...
Исчисление предикатов. Пропозициональная функция iconЯзык Пролог Пролог (Prolog)
Пролог декларативный язык, который основывается на исчисление предикатов и при работе с которым необходимо описать ситуацию (правила...
Исчисление предикатов. Пропозициональная функция iconИнтегральные преобразования. Операционное исчисление и некоторые его приложения
Пусть задана функция действительного переменного t, которая удовлетворяет условиям
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org