Методы искусственного интеллекта в робототехнике (2 варианта) (1088971), страница 2

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

Текст из файла (страница 2)

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

Знания отображаются совокупностью таких формул, а получение новых знанийсводится к реализации процедур логического вывода. В основе логических моделейпредставления знаний лежит понятие формальной теории, задаваемое кортежем: S = <B,F,A,R > , где: B — счетное множество базовых символов (алфавит); F — множество, называемое формулами; A — выделенное подмножество априори истинных формул (аксиом); R — конечное множество отношений между формулами, называемое правиламивывода.Логика высказываний (или пропозициональная логика) — это формальная теория,основным объектом которой служит понятие логического высказывания. С точки зрениявыразительности, её можно охарактеризовать как классическую логику нулевого порядка.Логика высказываний является простейшей логикой, максимально близкой кчеловеческой логике неформальных рассуждений и известна ещё со времён античности.Базовыми понятиями логики высказываний являются пропозициональная переменная— переменная, значением которой может быть логическое высказывание, — и(пропозициональная) формула, определяемая индуктивно следующим образом:1.

Если P — пропозициональная переменная, то P — формула.2. Если A — формула, то— формула.3. Если A и B — формулы, то,и— формулы.4. Других соглашений нет.Знакии(отрицание, конъюнкция,дизъюнкция и импликация) называютсяпропозициональными связками. Подформулой называется часть формулы, самаявляющаяся формулой. Собственной подформулой называется подформула, несовпадающая со всей формулой.Правила построения формул логики высказываний:1. Элементарное высказывание (буква) является формулой нулевого уровня.

Еслиэлементарное высказывание всегда верно, мы будем его обозначать буквой И, аесли оно всегда неверно, — буквой Л. Тогда формулы первого уровня — этоэлементарные высказывания, к которым применена только одна логическая связка.2. 2.Пусть Ф1 и Ф2 — формулы ненулевого уровня.

Тогда записи (¬(Ф1)), ((Ф1)(Ф2)), ((Ф1) (Ф2)), ((Ф1)→(Ф2)) также являются формулами. Если же одна изформул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевойуровень, то она в скобки не заключается.Теперь, зная буквы-элементарные высказывания, мы никогда не ошибёмся, определяя,является ли формулой запись, содержащая эти буквы, скобки и символы связок, то естьправильно ли построено сложное высказывание. В процессе подобного опознавания мывыделяем части формулы, то есть более короткие формулы, из которых на каждом этапестроится более длинная формула с применением одной связки.

Самыми простымичастями формулы являются, разумеется, элементарные высказывания. Значит, логическийанализ формулы сводится к выделению всех её частей.оскольку в построенных по определению формулах оказывается слишком много скобок,иногда и не обязательных для однозначного понимания формулы, математики принялисоглашения о скобках, по которым некоторые из скобок можно опускать. Записи сопущенными скобками восстанавливаются так: Если опущены внешние скобки, то они восстанавливаются.Если рядом стоят две конъюнкции или дизъюнкции (например,), тов скобки заключается сначала самая левая часть (т.е.

две подформулы со связкоймежду ними). (Говорят также, что эти связки левоассоциативны.) Если рядом стоят разные связки, то скобки расставляются согласно приоритетам:и(от высшего к низшему).Когда говорят о длине формулы, имеют в виду длину подразумеваемой(восстанавливаемой) формулы, а не сокращённой записи.Например: записьозначает формулу, а её длинаравна 12.Истинностное значение:Оценкой пропозициональных переменных называется функция из множества всехпропозициональных переменных в множество {0, 1} (т.е. множество истинностныхзначений). Основной задачей логики высказываний является установлениеистинностного значения формулы, если дана оценка (т.е.

определены истинностныезначения входящих в неё переменных). Истинностное значение формулы в таком случаеопределяется индуктивно (с шагами, которые использовались при построении формулы) сиспользованием таблиц истинности связок.Оценка отрицаниязадаётся таблицей:Значение двуместных логических связок(конъюнкция) определются так:(импликация),(дизъюнкция) и0 0 1000 1 1011 0 0011 1 111Тождественно истинные формулы (тавтологии):Формула является тождественно истинной, если она истинна при любых значенияхвходящих в неё переменных.

Вот несколько широко известных примеров тождественноистинных формул логики высказываний:Законы де Моргана:1);2);Закон контрапозиции:;Законы поглощения:1);2);Законы дистрибутивности:1);2).Исчисление высказываний:Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказыванийявляется следующая система аксиом:;;;;;;;;;;.вместе с единственным правилом:Теорема корректности исчисления высказываний утверждает, что все перечисленныевыше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинныхвысказываний можно получить только истинные.

Доказательство этой теоремытривиально и сводится к непосредственной проверке. Куда более интересен тот факт, чтовсе остальные тавтологии можно получить из аксиом с помощью правила вывода — этотак называемая теорема полноты логики высказываний.из юнктивная нормальная форма ( НФ) в булевой логике — нормальная форма, вкоторой булева формула имеет вид дизъюнкции нескольких конъюнкций.Например, следующие формулы записаны в ДНФ:он юнктивная нормальная форма ( НФ) в булевой логике — нормальная форма, вкоторой булева формула имеет вид конъюнкции нескольких дизъюнктов.Например, следующие формулы записаны в КНФ:Эти формы удобны для автоматического доказательства теорем.Логические следствияВысказывание В есть логическое следствие высказыванийвысказываний), что символически записывается в виде:(в исчисленииесли для всякого распределения истинностных значений, приписываемых каждой изпростых формул, входящих в одну или несколько из формулв В, формула В получает значение Т всякий раз, как каждоеЕсли пользоваться истинностными таблицами, то «просто, что при построении истинностных таблиц дляиполучает значение Т.» означаети В по перечнюпростых формул, входящих в одну или в несколько из этих формул, Вполучает истинностное значение Т по меньшей мере для каждого приписыванияотдельным P истинностных значений, которое одновременно дает всемПример.значение Т.8.

Основные теоремы о логических следствиях в исчислении высказываний.Метод доказательства от противного. ПротиворечияМножествовысказываний непротиворечиво, если существует по меньшеймере одно такое распределение истинностных значений простым компонентам, что все Аодновременно получают значение Т. Противоречивость множества высказываний естьотрицание его непротиворечивости. Так,есть противоречивое множество,если при всяком распределении истинностных значений простым компонентам поменьшей мере одно из А получает значение F.

Короче говоря,непротиворечиво, есликомбинации приписываемыхпростымимеет значение Т по меньшей мере для однойкомпонентам истинностных значений, ипротиворечиво, еслиимеет значение F для всехкомбинаций истинностных значений, приписываемых простым компонентам.Противоречие есть формула, которая всегда принимает истинностное значение F(например,)Теоремы о противоречииТеорема 1. Множество высказыванийпротиворечиво, если в него в качествелогического следствия можно вывести противоречие.Теорема 2.|= B, если в качестве логического следствия изможно вывести противоречие.Общезначимость в исчислении предикатовиФормула общезначима в поле, если она принимает значение T при каждом приписываниизначений предикатным символам и свободным переменным в ней.

Формула общезначима,если она общезначима во всяком поле. Тот факт, что формула А общезначима, мы будемвыражать так:|=AОсновные теоремы общезначимости в исчислении предикатовТеорема 1. Пусть A(x) – формула, свободная для y. Тогда:I.II.|=|=Следствие. Если |=, то |=.Теорема 2. Пусть x – какая-либо переменная, B – какая-либо формула, не содержащаясвободных вхождений x, и A(x) – какая-либо формула. Тогда:I.II.Если |=, то |=Если |=, тоСледствие: Если |= A(x), то |=.Определение 10 (Интерпретация). Символы л,и (``ложь'', ``истина'') называютсяистиностными значениями.

Интерпретация пропозициональной сигнатуры s естьфункция из s в {л,и}.Если s конечна, тогда интерпретация может быть определена таблицей её значений,например:pq(3)л иСемантика логики высказываний, которую мы собираемся ввести, определяет какиеистиностные значения назначены формуле F интерпретацией I.Прежде всего нам надо связать функцию с каждой пропозициональной связкой –функцию из {л,и} в {л,и} с унарной связкой ¬ и функцию из {л,и}ґ {л,и} в {л,и} скаждой бинарной связкой. Функции определяются следующими таблицами:x ¬(x)л иилx y &(x, y) Ъ(x, y) Й(x, y)л л ллил илииил лилиииииДля любой формулы F и любой интерпретации I истиностное значение FI , назначенноеформуле F интерпретацией I, определяется как значение суперпозиции соответствующихбулевых функций, а именно, следующим образом:FI = I(F) если F – атом,(¬F )I = ¬(FI),(F Д G)I = Д(FI,GI) для каждой бинарной связки Д.Заметим, что это определение рекурсивно: (¬F)I определяется через FI и (F Д G)I – черезFI и GI.Если FI = и, мы говорим, что формула F истинна при интерпретации I (символически I|= F ).2.10 Найдите формулу F такую, что (3) – единственная интерпретация, при которой Fистинна.Если рассматриваемая сигнатура конечна, тогда множество интерпретаций тоже конечно,и значения FI для всех интерпретаций можно представить в виде конечной таблицы.

Характеристики

Список файлов учебной работы