Василенко Н.В., Никитин К.Д., Пономарёв В.П., Смолин А.Ю. - Основы робототехники (1071028), страница 67
Текст из файла (страница 67)
Такие выражения, построенные на основе символов предметных переменных и констант с помощью символов функций, называются термами. Содержательно терму соответствует имя некоторого объекта или вещи. Константы, например, являются простейшими видами термов для представления объектов или вещей при рассуждениях. Рассмотреннью компоненты языка логики предикатов (словарь его символов) соединяются между собой и интерпретируются в соотвествии с определенными правилами, изложенными ниже.
Предложения, высказывания и предикаты. В обычных языках простейшим выражением является предложение, являющееся соединением слов, имеющим самостоятельный смысл, Каждому предложению соответствует заключенное в нем высказывание, причем полагается, что каждое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным. Таким образом, высказывание может рассматриваться как величина, принимающая лишь два значения - "истинно" (И) или "ложно" (Л). Высказывание о каком-либо объекте х можно считать функцией ' Г (х), принимающей только два значения — И или Л, причем определенным высказыванием Г (х) становится только тогда, когда переменная х принимает конкретное значение. Например, предложение "х есть машина*' становится определенным высказыванием, если переменной х придать предметное значение.
Например, если положить, что х = = *'робот", то получим истинное высказывание и, напротив, положив х = "слон", получим высказывание ложное. Аналогично неопределенное высказывание о двух, трех и более объектах представляет собой функцию со значениями И и Л от двух, трех и более переменных. Именно такие неопределенные высказывания — функции вида Г (х,, х„ ..., хл), аргументы которых (х„ х„ ..., х„) принимают значения из рассматриваемой области, а сами функции только два значения — И и Л, называются логическими функциями или предикатами. Предикат, аргументы которого являются и преметных переменных„ называется и-местным.
Если и = 1, то предикат определяет некоторое свойство объекта; если и > 2, то предикат выражает и-арное отношение между объектами. Элементарные и правильно построенные формулы и логические операции. Элементарными формулами (или формулами-атомами, атомарными формулами) принято называть предикаты независимо от их смысла, количества и содержания термов. Значит, формулы-атомы можно рассматривать как элементарные величины, принимающие значения И или Л, над которыми возможно производить логические операции-действия, приводящие к получению новых, более сложных формул. Для этого используют определенные логические операции, каждая из которых имеет собственный смысл и символику: 1) конъюнкция, обозначаемая Л, или В и означающая '*и"; 2) дизъюнкция, обозначаемая У и означающая "или"; "...
или, ... или*', "и/или"; 3) импликация, обозначаемая и означающая "влечет за собой", "если ..., то ...", "если ..., тогда ...", "только если"; 337 4) эквивалентность, обозначаемая и означающая "равносильно", "эквивалентно", "тогда и только тогда"; 5) отрицание, обозначаемое 1, ипи -, и означающее "не", "неверно, что ... " . Если А и В какие-либо (элементарные или сложные) формулы, то над ними теперь можно производить действия-операции: пользуясь введенной символикой, например, ААВ; АЧВ; А . В; А В; 1А; 18, получая более сложные формулы. Для однозначного прочтения и восприятия сложных формул применяют скобки, указывающие, в каком порядке связывать их между собой.
Поэтому следует писать, например, (А - 8)- С или А (8 С), но не А- В ' С. Для уменьшения же числа скобок, как и в арифметических действиях, устанавливается "старшинство" символов операций в порядке убывания: ',-, Ч, Л, 1. Так, например, можно записать без скобок А — ВАС, что означает А- (ВЛС). Символ отрицания 1, или -, имеет наименьший ранг, поэтому, например, 1АЧ В означает (1 А) Ч В, но не 1 (А Ч В). для правильного определения значений сложных формул по значениям составляющих их простых формул следует пользоваться таблицей истинности (табл. 8.1). Таблица 8.1 Определение истинности сложных формул Кроме рассмотренных в логике предикатов используют еще два символа-связи, выражающих операции утверждения всеобщности и существования: 1) квантор всеобщности, обозначаемый Ух и означающий "для всех х...
истинно"; 2) квантор существования, обозначаемый Зх и означающий "существует такое х, что... истинно". Например, формула Ухг(х) истинна, когда Г(х) истинно для любого х из области определения функции, а читается как "для всех х Г(х) истинно"; формула Зх Е(х) истинна, если в области определения функции найдется хотя бы одно значение х, при котором Е (х) истинно, а читается как "'существует такое х, что Г(х) истинно". Из таблицы истинности выводится ряд эквивалентных соотношений, весьма полезных для использования в процессе логического вывода: 1(1А) АЧВ -1А -В; 1(З х) А(х) ' (Чх) [1 А(х)1; 1 ( У х ) А (х) ( 3 х ) [ 1 А (х) 1. Законы Де Моргана: 1(Ачв) 1А Л1 в; 1(АЛВ) - 1Ач1в.
Дистрибутивные законьс АЛ( ВЧС) (АЛВ ) Ч (АЛС); АЧ(ВЛС) (АЧВ)Л(АЧС). Коммутативные законы: АЛВ ' ВЛА; АЧВ ' ВЧА. Ассоциативные законы: ( Алв)лс ' Ал( влс); (АЧВ )ЧС АЧ ( ВЧС) . Контропозитивный закон А В 1В 1А. Теперь можно дать еще одно определение правильно построенной формулы на языке робота ППФ есть выражение в виде конечной последовательности символов, которое строится на основе элементарных формул-атомов путем перехода от формулы А к формулам ЧхА и ЗхА и от формул А и В к формулам АЛВ, АЧВ, А В, А В, 1А, 1 В. При этом элементарная формула или ее отрицание, входящие в ППФ, называются литерами (или литералами), а дизьюнкция литеров называется простым дизьюнктом.
Если дизъюнкт не содержит никаких питер, то он называется пустым дизъюнктом. Интерпретации и методы решения логических задач Правильно построенные формулы имеют практическими смысл, становятся осмысленными лишь тогда, когда входящие в них формальные символы получают какую-либо интерпретацию. Интерпретация - это предписание, устанавливающее соответствие языковым символам формулы некоторых объектов предметной области: константам и переменным — элементов этой области; функциональным символам— конкретных функций, определяющих связи между реальными объектами и вещами; предикатным символам - конкретных предикатов. Таким образом, интерпретация, осуществляя связь между языком робота и описываемой им предметной областью реального мира, позволяет придать ППФ содержательный смысл, т.е.
играет роль семантики языка При заданной интерпретации всякая формула (не содержащая свободных переменных) представляет собой истинное или ложное высказывание. Если при интерпретации » каждая из формул А , 1 А,,„Ам принимает значение И, то говорят, что интерпретация удов- летворяет системе формул (А,.», Процесс решения логических задач в исчислении предикатов сводится к преобразованию формул по определенным правилам, образующим в совокупности систему логического вывода или дедук- ции. В ее основе лежит так называемая концепция выводи- м ост и, которая гласит, что если ППФ А выводима из системы формул м ( А; »; 1, то объединение ( А; » Ч1А не удовлетворяется ни при какой физической интерпретации и назвается противоречивым.
И наоборот, если ( А; » Ч»А неудовлетворимо, то ППФ А должна логи- чески следовать из системы (А;»; Следует заметить, что противоречивость (неудовлетворимость) в ходе логического вывода выражается в получении из системы ППФ в качестве истинных какой-либо формулы и ее отрицания одновременно, так называемой н у л ь -ф о р м у л ы (пй). Один из наиболее эффективных и универсальных методов поиска логического вывода является предложенный в 1995 г. Дж. Робинсоном так называемый метод резолюций, в основу которого заложена идея доказательства от противного.
Вместо заданной формулы В, которая предполагается тождественной истинной, рассматривается ее отрицание »В и доказывается противоречивость последней формулы. Полученное противоречие доказывает неудовлетворимость формулы »В и, следовательно, тождественную истинность исходной формулы В. Метод замечателен тем,что сложный процесс логического вывода он сводит к последовательности очень простых операций, каждая из которых может быть легко запрограммирована. В основе использования метода резолюций лежат три простых правила вывода, или резольвенции: 1) если истинны ППФ А и»АЧВ, то истинна ППФ В (правило пюбцз ропепз); 2) если истинна ППФ АЧА, то истинна ППФ А (правило факторизации); 3) если истинна ППФ А ((Ч), то истинна ППФ Чхд (х) (правило уни- версальной специализации), где 1Ч - константа Эти правила применимы к простым дизьюнктам, на которые м предварительно и "раскладывается" система ППФ ( А; »1 1 Ч»А, из противоречивости которой следует, что А выводимо из ( А; »м 1.
Новые дизьюнкты, получаемые в результате применения указанных правил, назваются резольвентами. При образовании резольвент существенную роль играет процедура унификации, которая дпя двух данных предикатов 340 осуществляется подстановкой термов вместо переменных, делающих предикаты одинаковыми. Например, дпя неудовлетворимой системы ППФ вида ( А (х) ЧВ (х), »В (( (з)), »А Яз))», используя первое правило резольвенции после подстановки терма ((з) вместо переменной х, получим иэ первых двух ППФ резольвенту А (( (г)), которая в сочетании с третьей ППФ системы дает нулевую формулу (одновременное утверждение и отрицание истинности ППФ). Таким образом, если выбрано два простых дизьюнкта и по одной литере в каждом из них, то применение правил унификации, а затем резольвенции дает резольвенту; при этом при доказательстве выводимости ППФ процесс образования резольвент продожается пока не будет получена нуль-формула, означающая неудовлетворимость исходной системы ( А; »;-1 Ч»А, а значит, и успех доказательства от противного.
В целом процесс доказательства сводится к следующему. К системе( А;» присоединяется ППФ »А, а получившаяся формула ( А;» Ч»А Раскладывается на простые дизьюнкты, к которым применяют процедуру унификации, а также правила птобоз ропепз, факторизации и универсальной специализации. Конечной целью является получение нуль. формулы (пй), доказывающей неудовлетворимость объединения ( А; » Ч»А, а значит, выводимость А из ( А, »; 1. Важным качеством системы логического вывода является возможность установления не только истинности того или иного высказывания, но и значения переменной, при которой утверждение истинно.
В качестве иллюстрации рассмотрим очень простой с точки зрения поп~о вар~еле пример решения логической задачи, но совершенно неразрешимой для машины, не обладающей хотя бы зачатками искусственного интеллекта. Пусть робот Я может обслуживать (т.е. снимать и устанавливать детали) станок В. Деталь Д установлена на станке В. Роботу следует самостоятельно решить, может ли он снять со станка именно конкретную деталь Д ? В данном примере В и Д являются константами. Введем общие двухместные предикаты Р (у, г) и Я (р, О), которым придана очевидная интерпретация: Р(у, г)- "деталь унаходится на станке г'; Я (Р, о)— "робот может снять деталь р со станка О ".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
