Тема Языки ии

жүктеу 258 Kb.

бет	11/18
Дата	21.01.2022
өлшемі	258 Kb.
	#34485
түрі	Лекция

1 ... 7 8 9 10 11 12 13 14 ... 18

МУ-консп-лек-СИИ-рус

Содержание лекций.
P(f(y))VQ(f(y)) Q(f(y) .
Резольвенции

Лекция 9. Метод исчисления предикатов

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

Содержание лекций. В источниках литературы имеются два важных приложения ИИ: понимание естественного языка и автоматическое рассуждения. Система автоматического доказательства применяет однозначные описания для представления информации. В такой системе применяются точные правила вывода, внимательно сформулированные стратегии для управления этими выводами. Для построения систем автоматических рассуждений используются представления основанные на теории предикатов первого порядка, теория хорновских выражений, теория операторов разрешения. На данной лекций рассматривается теория предикатов первого порядка. Основные понятия. Для автоматического логического рассуждения необходим некоторый формальный язык, на котором можно сформулировать посылки и делать верные логические выводы. Исчисление предикатов первого порядка – это такая система в логике, в которой можно выразить большую часть того, что относится к математике, а также многое из разговорного языка. Эта система содержит правила логического вывода, позволяющие делать верные логические построения новых утверждений, исходя из некоторого заданного множества утверждений. В любом языке имеется его синтаксис и семантика. Синтаксис. Он включает в себе задание алфавита символов и определение различных выражений, которые можно построить из этих символов. Основной алфавит состоит из таких множества символов: 1. Знаки пунктуации : , . ( ); 2. Логикические символы: ~, => (~- символ “не” –; а => читается как – “влечет за собой”; 3. n – местные функциональные буквы: ( ) ( -константая буква, они обозначаются как а,в,с, а как - f, g, h. ; 4. n – местные предикатные буквы: ( ) ( - пропорциональные буквы). Их предлагают обозначать как - P, Q, R – для простоты. С помощью этих символов можно построить различные выражения. В классе выражений можно определить следующие термины: Термы, Атомные формулы, ППФ – Правильно Посроенные Формулы. Теперь добавим нашему алвафиту следующие логические символы: ٨ – “и” , V –“или” . Например: если х₁ и х₂ любой ППФ, тогда x₁ ٨x₂, x₁V x₂, - тоже ППФ, т.е. x₁ ٨x₂=~ (x₁ =>~x₂), x₁V x₂=(~ x₁ )=>x₂). Семантика Для того чтобы придать ППФ- “содержание”, ее надо интерпретировать как некоторое утверждение, касающееся рассматриваемой области. Например областью может служить некоторое непустое мнжество.(возможно бесконечное). Им может быть множество целых чисел,или множество конфигураций игры в “8” или множество всех математиков и.т.д. Интересующее нас утверждения будут связаны отношениями между элементами этой обдасти. Нарпимер мы выскажем следующее утверждения: “Ержан - отец Айдара”. Тогда областью будет множество людей, а отношением между людьми – бинарное отношение –“отцовство”. Нарпимер, функция плюс отображает пары целых чисел в целые числа в соответствии с хорошо известной операцией сложения. Для ППФ сделать утверждения определенного смысла, мы связываем с этой ППФ – некоторую непустую область D. Затем связываем: с каждым констнатным символом в ППФ – некоторый конкретный элемент из D, с каждой функциональной буквой в ППФ –некоторую конкретную функцию на D, с каждой предикатной буквой в ППФ –некоторое конкретное отношение между элементами из D. Конкретизация области и указанных соответствий дает интрепретацию нашей ППФ, или модельнашей ППФ. При заданной ППФ и некоторой интерпретации каждой атомной формуле в этой ППФ припсвается значение T (истина) или F(ложь). Правило приписывания значения атомной формулы очень простое: если термы предикатной буквы соответствуют элементам из D, удовлетворяющим соответствующему соотношению, то значениям атомной формулы будет T. В противном случае будет F. Например: Пусть P(a,f(в,c)) – атомная формула, и имеет она следующую интерпретацию: D- множество целых чисел, а – число 2, b – число 4, c – число 6, f - функция сложения, P – > отношение “больше”. При такой интерпретации наша атомная формула утверждает, что: “число2 больше суммы чисел 4 и 6”. Это утверждение неверно, поэтому , P(a,f(в,c)) – имеет значение F. Если интерпретацию изменить так, что а=11, тогда P(a,f(в,c)) – будет имеет значение Т. Очевидно, что существует много других интерпретаций, для которых эта атомная формула имеет значение Т, и много таких интерпретаций, для которых эта атомная формула имеет значение F. Но для любой интерпретаций будет либо Т, либо F и никогда то и другое одновременно. Общезначимость и выполнимость. Если некоторая ППФ имеет значение Т (true) при всех интерпретациях, то ее называют общезначимой. Так по таблице истинности следующая ППФ P(a)=>(P(a)|P(b)) при любой интерпретации имеет значение Т и следовательно, она общезначима. С помощью таблиц истинности всегда можно определить, общезначима ли данная ППФ, не содержащая кванторов. Нужно просто проверить , имеет ли эта ППФ значение Т при всех возможных значениях (Т или F) содержащихся в ней атомных формул. Если при данной интерпретации каждая ППФ из некоторого множества имеет значение Т, то говорят, что данная интерпретация удовлетворяет данному множеству. ППФ W логически следует из некоторого множества S - ППФ, если каждая интерпретация удовлетворяющая S удовлетворяет и W. Доказательствам того, что некоторая ППФ W логически вытекает из заданного множества S ППФ . показывает тот факт, что W логически следует из S. Факт «неразрешимости» исчиления предикатов означает также, что при заданных ППФ W и произвольном множества S ППФ не существует эффективной процедуры, позволяющей всегда решить, следует ли логически W из S. Именно эту концепция, логического следования положена в основу понятия доказательства. Если некоторе мнжество ППФ не удовлетворяется ни при какой интерпретации. То она называется неудовлетворимым (или невыполнимым). Так если W логически следует из S, то объединение S U {~W} неудовлетворимо. Обратно, если S U {~W} неудовлетворимо, то W должна логически следовать из S. Этот результат используется для того, чтобы придать одинаковую форму всем задачам доказательства: для доказательства логического следования W из S мы будем показывать, что объединение S U {~W} неудовлетворимо. Для того ,чтобы показать , что некоторое множество ППФ неудовлетворимо, надо доказать , что нет никакой интерпретации, при которой каждая ППФ в этом множестве имеет значение Т. Хотя эта задача и кажется трудоемкой, существуют довольно эффективные процедуры ее решения. Для выполнения этих процедур требуется сначала ППФ данного множества в специально удобном виде – в виде предложений (clouse). Любую ППФ в исчилении предикатов можно представить в виде предложения, применяя к ней последовательность простых операций. Предложения состоят из ППФ, обиъеденненых символами дизъюнкции (символ V) и отрицания (символ ~). Если это множество предложении неудовлетворимо, то считается, что ППФ получена как логически следуемая из этого множества. Резольвентой называется предложение которая появляется из двух родительских предложений. В то же время эти два предложения должны находиться в одной интерпретации определенного множества. Например, рассмотрим два следующих предложений ~P(f(y))VQ(f(y)) ~Q(f(y) . Из двух этих предложений можно вывести следующее одно предложение ~P(f(y)). Это выведенное предложение является резольвентой двух предыдущих предложений. Принципом Резольвенции называется процесс образования резольвенты из двух родительскеких предложений. Процессы отрицания исползующие резольвенты проходят в графоподобных структурах. В каждой вершине таких структур записываются по одному предложению. Если в последних вершинах два предложения являются взаимно разрешимыми, то их резольвента записвается в последующей вершине. Связь вновь появившихся вершин с предыдущими осуществляется через ветви дерева. Таким образом в процессе появления графа опровержения должен появится корень. Который будет пустым предложением. Он обозначается через знак nil. В корне этого преобразованного графа находиться ответ-предложение. Ткаим образом применяя принцип резольвенции компьютер может выдать ответ, который получает человек. Обратимся теперь к известной классической задаче об обезьяне и банане, простейшую формулировку которой мы и рассмотрим [13,15]. В комнате находятся обезьяна, ящик и связка бананов, которая подвешена к потолку настолько высоко, что обезьяна может до нее дотянуться, только встав на ящик. Нужно найти последовательность действий, позволяющие обезьяне достать бананы. Предполагается, что обезьяна может ходить по комнате, двигать по полу ящик, взбираться на него и хватать бананы. Рассмотренный пример показывает, сколь важен для успешного и эффективного решения задачи выбор определенного представления. Такое небольшое по размерам пространство состояний получено, в частности, вследствие того, что игнорировались все точки пола, кроме трех, соответствующих первоначальному расположению обезьяны, ящика и бананов. Мощным приемом сужения пространств состояний является применение так называемых схем состояний и схем операторов, в которых для описаний состояний и операторов используются переменные. Тем самым схема состояния описывает целое множество состояний, а не только одно, а схема оператора определяет все множество действий некоторого типа. В рассмотренном нами представлении задачи об обезьяне использовались схемы операторов, но не схемы состояний. Другое представление этой задачи с использованием как схем состояний, так и схем операторов приведено в [13].

жүктеу 258 Kb.

Достарыңызбен бөлісу:

1 ... 7 8 9 10 11 12 13 14 ... 18