ЛМвИИ (1086253), страница 8

Файл №1086253 ЛМвИИ (Учебник - Логические методы в искусственном интеллекте (2,3 и 5 глава)) 8 страницаЛМвИИ (1086253) страница 82018-01-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Хотя в логике слово "предикат"употребляется в более общем смысле, чем в грамматике, где оно выражает только то, чтоговорится о субъекте.Пусть задано множество V={v1, v2, …, vK , ...}, в котором v1, v2 и т.д. - какие-то объектыиз этого множества. Обозначим любой предмет из этого множества через х и назовем xпредметной переменной. Тогда высказывания об этих предметах обозначим через Р(v1), Q(v1, v2)и т.д., причем такие высказывания могут быть как истинными, так и ложными. Например, еслиV={1, 2, 3, ...}, то высказывание "4 есть четное число" является истинным, а "7 есть четноечисло" - ложным.

Если вместо конкретных чисел 4, 7 подставим предметную переменную х, тополучим предикат их есть четное число", обозначаемый Р(х). Таким образом, предикат намножестве V есть логическая функция, определенная на V, при фиксировании аргументовкоторой она превращается в высказывание со значениями {И, Л}.В приведенном примере имеемлогическую функцию Р(x), определенную на множестве V и принимающую значения: И, Л. Вобщем случае через Р(x1, x2, …, xn) обозначим n-местный предикат. Приписав значенияпеременным x1, x2, …, xn из соответствующих областей определения, получим высказывание созначениями {И, Л}.Определим синтаксис логики предикатов первого порядка.• Алфавит1. Предметные переменные x, y, z, ...

и предметные константы a, b, c, ...2. Функциональные константы или имена функций f1, f2, ...3. Предикатные константы или имена предикатов Pn, QK, Rj, ...4. Логические операторы (логические связки) ¬, ^(&), v, →, ↔, ⊃.5. Символы кванторов ∀, ∃.• Термы1. Всякая переменная или константа есть терм.2. Если t1, t2, …, tn - термы и fin - функциональная n-местная константа, тоfin(t1, t2, …, tn) - терм.

Здесь верхний индекс определяет количество аргументов.Если переменные терма t содержатся среди переменных списка x1, …, xs. То пишемt(x1, …, xS).3. Никакие другие выражения не являются термами.•••Атомы1. Если t1, …, tm - термы и Рm -m-местная предикатная константа, то Рm(t1, …, tm) - атом.При m=0 предикат Р() обращается в высказывание Р. Атомом является такжеравенство, т.е. выражение типа (s=t), где s и t - термы.2. Никаких других атомов нет.•Формулы:Формулы (или правильно построенные формулы ППФ) определяются следующимобразом:1. Если t1, …, tK - термы, {x1, …, xm} - множество всех переменных, входящих в термы;Р - предикатная переменная, то Р(t1, …, tK) - элементарная формула (атом), а{x1, …, xm} — все её свободные переменные.2. Всякий атом есть формула.3.

Если А и В - формулы, а x - свободная переменная, то ¬A, AvB, A^B, A→B, A↔B,∀xA, ∃xA - формулы.4. Никаких других формул нет.В пределах формализма логики предикатов первого порядка запрещено использованиепредикатов в качестве термов, навешивания кванторов на предикатный символ.Предикат P(t1, t2 , …, tn ) служит для выражения свойства объекта (при n=1) и отношениймежду объектами (при n≥2). Атомарная формула Р(a1, a2 , …, an ) истинна в некотором "мире"(M), если между объектами в М имеется отношение, соответствующее P.Связывание свободной переменной происходит либо квантификацией (взятиемквантора по этой переменной) либо присвоением значения.Например:n∑ 2i: n - свободная переменная, i-связанная;t =1∀xP(x, y) : х - связанная переменная, у — свободная;(х=а)Р(х) : х - связанная переменная.Если предметные переменные определены на конечной области, то операциюнавешивания кванторов можно выразить через операции конъюнкции и дизъюнкциисоответственно.Пусть x 1 ∈{a 1 , a 2 , ...

, a m }, тогда ∀x1P(x1, …, xn ) =Р(a1, x1, …, xn )^Р(a2, x1, …, xn )^...^Р(am , x1, …, xn ),∃x1P(x1, x2, …, xn ) = Р(a1, x1, …, xn )vР(a2, x1, …, xn )v...vР(am , x1, …, xn ); в частном случае∀хР(х) = P(a1)^P(a2)^...^P(am ),∃хР(х) = P(a1)vP(a2)v...vP(am).Говорят, что квантор связывает соответствующую переменную. Предикат (формула)называется замкнутым, если связаны все переменные (если нет свободных, т.е. несвязанныхпеременных).1.2.3.4.Примеры.Термами являются:a) переменные: х, фамилия, число, буква;b) константы: С, Дейкстра, 94, ъ;c) функции max(x, y, z), ∑(x, y) или более традиционное представление - (х+у).Термами не являются выражения:a) Р(х) - так как Р - символ, зарезервированный для предиката;b) (х>0) - так как это отношение ( т.е. с точки зрения логики -одноместный предикат);c) х:=а - специфическая операция в программировании.Формулами являются:a) Р(х)=(х>0), выше(x, y) или в более традиционном представлении (х выше у);b) формулы, полученные из атомарных ¬Р(х), ∀хР(х), P(x)→Q(x, y),∀x∃yQ(x, y)v¬zR(x, z), (х выше y)^(y выше z)→(х выше z).4.

Формулами не являются:a) (а+b) - поскольку это терм;b) (а+b)^(с-d) - здесь два терма, соединенные логическими символами;∀P∃xP(x) - поскольку здесь квантор ∀ навешен на символ предиката ( этовыражение могло бы служить примером формулы в языке второго порядка).Из интуитивного понимания квантификации вытекает, что имеется связь междувхождениями переменной, содержащейся в квантификации. Так, в формуле ∀x(P(x)→Q(x))переменная x связана. Связь вводится первым вхождением, которое следует за кванторомобщности.Область действия некоторой квантификации есть формула, к которой применяется этаквантификация.

Переменная x в кванторах ∀x и ∃x называется квантифицированной. Каждоевхождение переменной х в область действия этой квантификации является связанным.Вхождение переменной х свободное, если оно не является ни квантифицированным, нисвязанным.В формулах ∃хА и ∀хА область действия х есть А. Если х и y - переменные, то областидействия x и y либо не пересекаются, либо одна включает другую. Рассмотрим примеры:∀x[P(x, a)→∃xQ(x)],∀xP(x, a)→∃xQ(x),∀xP(x, a)→Q(x).В первом случае две квантификации по одной переменной перекрываются. Такой типформул исключим из рассмотрения, придерживаясь правила введения кванторов: ∃xA и ∀хA формулы только в том случае, если х - переменная и А - формула, не содержащая связанныхвхождений х.Во втором случае две связанные переменные случайно получили одинаковое имя.В третьем случае и связанная переменная и свободная получили одно имя. Следовалобы сразу переименовать, например, связанную переменную: ∀yP(y, a)→Q(x).c)Пример.2.2.

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

Интуитивнотерм означает объект. Тогда интерпретация должна указывать множество объектов, называемоеобластью интерпретации.Интерпретация /есть тройка (S, Ic, Iv ), где:• S - непустое множество (область интерпретации);• Ic - функция, сопоставляющая каждой n-местной функциональной константе f функциюIc(f) из Sn в S. Она также каждой m-местной предикатной константе Р ставит всоответствие функцию Ic(P) из Sm в {И, Л}.• Iv - функция, сопоставляющая каждой переменной какой-то элемент из S.Необходимо ввести еще обозначение, которое послужит для интерпретации двух видовквантифицированных формул.

Если I - некоторая интерпретация с областью SI , x - переменная иd - элемент из SI то Ix/d означает такую интерпретацию J, что Sj=SI , Jc=Ic, Jv(x)=d, Jv(y)=Iv(y) длявсех переменных у, отличных от х. Теперь для каждой интерпретации I=(S, Ic, Iv) можно задатьтакие правила интерпретации, которые каждой формуле А сопоставляют значение истинностиI(A) и каждому терму t сопоставляют элемент I(t) из S. Эти правила интерпретации образуютсемантику языка логики предикатов первого порядка.Семантика.•••••••Если х - переменная, то I(х)=Iv(х) (по определению).Если f - n-местная функциональная константа и t1, …, tn -термы, то I(f(t1, …, tn )) =Ic(f)(I(t 1), ..., I(tn)) (по определению).Если Р - m-местная предикатная константа и t1, …, tn - термы, то I(P(t1, …, tn ) =Ic(P)(I(t 1), …, I(tn)) (no определению).Если s и t - термы, то I(s=t) есть И, если I(s)=I(t), в противном случае — Л.Если А и В - формулы, то ¬A, (А^В), (AvB), (A→B) и (А↔В) интерпретируются так же,как и в исчислении высказываний.Если А - формула и x - переменная, то I(∀xA) есть И, если Ix/d(A) есть И для всехэлементов d из S.Если А - формула и x - переменная, то I(∃хА) есть И, если Ix/d(A) есть И хотя бы дляодного d из S.Формула А исчисления предикатов первого порядка называется истинной приинтерпретации f, если I(А)=И.Говорят, что терм t свободен для переменной х в формуле Р, если ни х, ни произвольнаяпеременная из t не квантифицированы в Р.

При этом через Px/t обозначается формула,полученная из Р путем одновременной замены всех вхождений х на t. Формула называетсязамкнутой, если в ней нет несвязанных (свободных) переменных.Замкнутая формула, истинная в любой интерпретации называется общезначимой.Замкнутая формула, ложная при всех интерпретациях, называется невыполнимой, а истиннаяпри некоторых интерпретациях - выполнимой.Мы определили семантику формул логики предикатов первого порядка, основанную напонятии интерпретации. Теперь определим семантику, опираясь на понятии модели. Этипонятия отличаются лишь видами используемых словарей и обозначениями.Моделью М логики предикатов первого порядка называется пара (S,V), где S - областьинтерпретации и V - функция, совпадающая с функцией интерпретации I.

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

Тип файла
PDF-файл
Размер
2,12 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Учебник - Логические методы в искусственном интеллекте (2,3 и 5 глава)
opens___.ttf
ЛМвИИ.chm
Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6390
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее