ЛМвИИ (1086253), страница 14
Текст из файла (страница 14)
Важное понятие, используемое в нахождении ответов на вопросыэтого типа, - это так называемый метод состояний и их преобразований. Считается, что каждыйиз рассматриваемых объектов находится в данный момент в определенном состоянии. Длядостижения цели мы должны изменить текущее состояние объекта в желаемое. Рассмотримвозможность автоматического доказательства теорем для нахождения таких действий.Сформулируем задачу. Пусть начальное состояние объекта d является s1 и d вначаленаходится в точке а. Обозначим Р(х, у, z) - “х находится в точке у в состоянии z”. Перемещениеобъекта в другую точку под действием /i приводит к изменению исходного состояния.Пример.Аксиомы:1.
Объект d находится в точке а в состоянии s1.2. Объект перемещается из исходной точки в точку b под воздействием f13. Объект перемещается из точки b в точку с под воздействием f2 .Вопрос:4. Как передвинуть d из а в с, если прямого пути из а в с нет (см. рис. 2.6)?Рис. 2.6. перемещение объекта из точки а в точку сbФормальная запись будет следующей:A1: P(d, a, s1).А2 , A3: (∀x, yi , z, ∃yj )(P(x, yi , z)→P(x, yj , fi (x, yi , yj , z))).В4: ∃x, y, zP(x, y, z).Преобразуем аксиомы в дизъюнкты (взяв отрицание вопроса):Д1. P(d, a, s1 ).Д2. ¬P(d, a, z)vP(d, b, f1 (d, a, b, z)).Д3.
¬P(d, b, z)vP(d, c, f2 (d, a, c, z)).Д4. ¬P(d, c, a)vOTB(z).Решение:Д1 - Д2: Д5. P(d, b, f1 (d, a, b, s1 ))Д3 - Д5: Д6. P(d, c, f2(d, b, c, f1 (d, a, b, s1 )))Д6 - Д4: Д7. vOTB(f2 (d, b, c, f1 (d, a, b, s1 )))(z←s1 )(z←f1 (d, a, b, s1 )).(z←f2 (d, b, c, f1 (d, a, b, s1 )))Дизъюнкт OTB(f2 (d, b, c, f1 (d, a, b, s1 ))) можно интерпретировать как выполнение двухдействий - f1 и f2 . Иными словами, сначала применяется действие f1 для перемещения объекта dиз а в b, а затем применяется действие f2 для перемещения d из b в с.1.2.Вопросы класса Д.Аксиомы:Если Пете меньше пяти лет, то он должен принимать лекарство а.Если Пете не меньше пяти лет, то он должен принимать лекарство b.3.Вопрос:Какое лекарство должен принимать Петя?Пусть Р(х) - "человеку x меньше пяти лет", R(x, y) - "х должен принимать лекарство у".Перейдем сразу к дизъюнктивной форме:Д1.
¬Р(Петя)vR(Петя, а).Д2. Р(Петя)vR(Петя, b).Д3. ¬R(Петя, х)vОТВ(х).Решение:Д1 - Д3: Д4. ¬Р(Петя)vОТВ(а).Д2 - Д3: Д5. P(Петя)vOTB(b).Д4 - Д5: Д6. OTB(a)vOTB(b).Мы можем задать вопрос: "При каком условии будет истинен ОТВ(а)?" или "При какомусловии ОТВ(а) будет логическим следствием дизъюнктов Д1, Д2 , Д3". Аналогичный вопросможно задать для дизъюнкта ОТВ(b). Покажем, как можно получить информацию, анализируявывод дизъюнкта-ответа.Алгоритм извлечения информации.Обозначим T0 - дерево вывода, соответствующее полученному решению.Шаг 1.
Припишем ребрам резольвирующих узлов дерева T0 отброшенные предикаты ссоответствующей подстановкой переменных и обозначим это дерево Т1 (рис.2.7).Шаг 2. Перевернем дерево, добавим стрелки к ребрам и выбросим все дизъюнкты,приписанные узлам. Получим дерево (рис.2.8), где прописными буквами помечены листья(аргумент П — Петя).Шаг 3. В дереве Т2 удалим все узлы (и связанные с ними ребра), соответствующиедизъюнктам, не содержащим предиката ОТВ (листья В, С и связанные с ними ребра).Результирующее дерево T3 изображено на рис.2.9.Шаг 4.
Пусть N1, N2, …, Nm - листья дерева T3. Для каждого Ni , i=1..m пусть I(Ni )обозначает конъюнкцию литералов, приписанных пути (ребрам) от самого верхнего узла к NiПусть C(Ni ) - дизъюнкт, соответствующий узлу Ni . Находим в дизъюнкте-ответе литерал L(Ni )такой, что L(Ni ) - логическое следствие конъюнкции I(Ni )^C(Ni ). Припишем L(Ni ) узлу NiВ нашем примере C(A)=¬R(П, x)vOTB(x) и L(А)=ОТВ(а), так как I(А)=Р(П)^R(П, а).Аналогично L(В)=ОТВ(b). Полученное таким образом дерево T4 изображено на рис.2.10.Шаг 5. Запишем в виде N1, N2, …, Nq список всех узлов Ni дерева T4 таких, что из 1≤i≤qведет только одно ребро ri .
Удалим из дерева литералы L(ri ), где L(ri ) - литерал приписанныйребру ri Обозначим результирующее дерево T5. Для нашего примера Т5:Заметим, что рис. 2.11 удобно рассматривать как дерево решений. Если истинно Р(П),то истинно ОТВ(а). В противном случае истинно ОТВ(b). Таким образом, наш ответ таков: 'ЕслиПете меньше пяти лет, то он должен принимать лекарство а.
В противном случае - приниматьлекарство b'.На шаге 4 мы приписали ОТВ(а) узлу А после того, как было обнаружено, что ОТВ(а) логическое следствие из P(Петя)^R(Петя, а)^(¬R(Петя, х)vОТВ(х)). Так как дизъюнкт(¬R(Петя, х)vОТВ(х)) входит в число исходных дизъюнктов, он предполагается всегдаистинным. Поэтому ОТВ(а) истинен всегда, когда истинна конъюнкция Р(Петя)^R(Петя, а).Рассмотрим дерево T2 . Узел В соответствует дизъюнкту (Д1 ). Так как он не содержит предикатаОТВ, все входящие в него литеры будут отброшены при получении дизъюнкта-ответа.Поскольку отрицания всех этих дизъюнктов содержится в I(B), где I(B)={Р(Петя), R(Петя, а)},нетрудно показать, что R(Петя, а) является логическим следствием Р(Петя) и дизъюнкта (Д1 ).Так как дизъюнкт (Д1 ) предполагается истинным, R(Петя, а) должно быть истинно, еслиистинно Р(Петя).Поэтому из того, что истинность Р(Петя) и R(Петя, а) влечет истинность ОТВ(а) мыполучаем, что истинность Р(Петя) влечет истинность ОТВ(а).Аналогично можно показать, что истинность ¬Р(Петя) влечет истинность ОТВ(b).
Этодоказывает, что дерево T5 правильное.В заключение отметим, что для некоторого упрощения резолюции в ручном вариантемы не выполняли обязательную при машинной реализации процедуру переименованияпеременных. Переименование переменных обусловлено тем, что одноименные переменныемогут и должны быть связаны только в пределах одного дизъюнкта. Каждый дизъюнкт - это"строительный кирпич" модели для метода резолюции. Если в результате резолюцийодноименные переменные из разных дизъюнктов попадают в один, то возникает связь междупеременными из разных дизъюнктов. Например, для дизъюнктов Д1: P(x)vR(x, y) и Д2:¬P(x)vP(y) дизъюнкт R(x, y)vP(y) нельзя считать резольвентой, поскольку переменные у изразных дизъюнктов оказалась связанными в новом дизъюнкте.
Следует переименоватьпеременные в одном из дизъюнктов, например в Д1 , тогда получим Д1': P(z)vR(z,v).В результате унификации {z | x} (или {x | z}) и последующей резолюции получимрезольвенту Д3': R(z, v)vP(z). Разумеется, переменная v должна быть определена на том жемножестве, что и переменная у.2.7. Формы представления логических формул.2.7.1. Клаузальные формы.В целях формализации доказательства выводимости в предыдущих разделах былирассмотрены преобразования правильно построенных формул в предваренную нормальнуюформу (кванторы находятся в передней части формулы). Предваренная нормальная формапреобразовывалась в нормальную сколемовскую форму исключением кванторов существованияи введением специальным образом сколемовских функций и констант.В искусственном интеллекте часто бывает полезно представлять формулы вклаузальной форме.
Сколемовская нормальная форма может быть преобразована в клаузальнуюформу, т. е. в виде множества дизъюнктов. Это позволяет иногда упростить доказательствотеорем. Дизъюнкт - это дизъюнкция литер, в которых переменные неявным образомуниверсально квантифицировны.Общий вид дизъюнкта таков:¬P1v...v¬PmvQ1v...vQn .Здесь Рi и Qj - позитивные литералы (атомарные формулы, в которых все переменныепредполагаются универсально квантифицированными). Дизъюнкт без переменных называетсяконкретизированным дизъюнктом. Приведенный выше дизъюнкт можно записать вэквивалентной форме:P1^...^Pm→Q1v...vQn .В зависимости от числа литер в антецеденте (посылке) и в консеквенте (заключении)этой импликации имеем различные по выразительности подмножества языка: логическийэквивалент языка реляционных баз данных, логический язык, используемый в Прологе и др.Когда n позитивных литералов в дизъюнкте строго больше 1, то имеем дело сдизъюнктивной информацией (возможно, условной).
В частности, при m=0 и n>1 дизъюнктсодержит только позитивные литеры: Q1v...vQn . С помощью таких дизъюнктов можнопредставлять неполные сведения. Например, дизъюнкт Рисует(Миша)vРисует(Петя) можноинтерпретировать так: "хотя бы один из мальчиков Миша или Петя рисует", но не уточняетсярисует только Миша, рисует ли только Петя или оба мальчика рисуют.Если m≥1 и n≥1, дизъюнкт имеет самый общий вид и представляет условнуюдизъюнктивную информацию. Наличие такой дизъюнктивной информации позволяет выражатьнеполные знания о мире. Однако, формализовать рассуждения на основе таких знаний оченьтрудно. Поэтому в языках логического программирования, простых дедуктивных базах данныхне используют такие дизъюнкты.2.7.2. Хорновские дизъюнкты.В языках логического программирования, подобных Прологу, ограничиваютсяхорновскими дизъюнктами, т.
е. дизъюнктами, содержащими не более одного позитивноголитерала. При m≥1 и n=1 дизъюнкт называется точным хорновским дизъюнктом, которыйимеет вид:P1^...^Pm→Q.Такой дизъюнкт осуществляет представление условной информации и может выступатьв качестве правила в Пролог-программе. Точный дизъюнкт выражает некоторое правило:негативные литеры соответствуют гипотезам, а позитивная литера - заключению.Если антецедент приведенной импликации не содержит литералов (m=0), то, очевидно,имеем дело с безусловной информацией. Такой дизъюнкт называется унитарным позитивныйдизъюнктом. Возможны два случая.• Литерал Q не содержит переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
