LectLog3 (1157998)
Текст из файла
Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А. ЗахаровЛекция 3.Выполнимые и общезначимыеформулы.Модели. Логическое следование.Проблема общезначимости.Семантические таблицы.ВЫПОЛНИМЫЕ И ОБЩЕЗНАЧИМЫЕФОРМУЛЫФормула ϕ(x1 , . . . , xn ) называется выполнимой в интерпретацииI , если существует такой набор элементов d1 , . .
. , dn ∈ DI , длякоторого имеет место I |= ϕ(x1 , . . . , xn )[d1 , . . . , dn ].Формула ϕ(x1 , . . . , xn ) называется истинной в интерпретации I ,если для любого набора элементов d1 , . . . , dn ∈ DI имеет местоI |= ϕ(x1 , . . . , xn )[d1 , . . . , dn ].Формула ϕ(x1 , . . . , xn ) называется выполнимой , если естьинтерпретация I , в которой эта формула выполнима.Формула ϕ(x1 , . . .
, xn ) называется общезначимой (илитождественно истинной ), если эта формула истинна в любойинтерпретации.Формула ϕ(x1 , . . . , xn ) называется противоречивой (илиневыполнимой ), если она не является выполнимой.ВЫПОЛНИМЫЕ И ОБЩЕЗНАЧИМЫЕФОРМУЛЫПримерыP(x1 )&¬P(x2 ),∀xP(x) → ∃xP(x),∃xP(x) → ∀xP(x)— выполнимые формулы.I1 : DI = {d1 , d2 }, P̄(d1 ) = true, P̄(d2 ) = falseI1 |= P(x1 )&¬P(x2 )[d1 , d2 ],I1 |= ∀xP(x) → ∃xP(x).I2 : DI = {d}, P̄(d) = trueI2 |= ∃xP(x) → ∀xP(x)Формулы P(x1 )&¬P(x2 ), ∃xP(x) → ∀xP(x) необщезначимые.I2 6|= P(x1 )&¬P(x2 )[d, d],I1 6|= ∃xP(x) → ∀xP(x).Формула ∀xP(x) → ∃xP(x) является общезначимой.Но почему? И как в этом убедиться?ВЫПОЛНИМЫЕ И ОБЩЕЗНАЧИМЫЕФОРМУЛЫВыполнимые формулы — это логические формы, которыеслужат для представления знаний. Каждая выполнимаяформула несет определенную информацию.Общезначимые формулы — это трюизмы, банальности,тавтологии, не несущие никакой информации.Какую же роль играют общезначимые формулы?МОДЕЛИ.
ЛОГИЧЕСКОЕ СЛЕДСТВИЕПусть Γ — некоторое множество замкнутых формул, Γ ⊆ CForm.Тогда каждая интерпретация I , в которой выполняются всеформулы множества Γ, называется моделью для множества Γ.Модель для множества формул Γ — это интерпретация(реальный или виртуальный мир), устройство которогоадекватно всем предложениям из множества Γ.ПримерI : DI = {d1 , d2 }, P̄(d1 ) = true, P̄(d2 ) = falseI — модель для множества формул Γ = {∃xP(x), ∃x¬P(x)}.ЗамечаниеА какая интерпретация является моделью пустого множестваформул Γ = ∅?Правильный ответ: любая интерпретация . Почему ?МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕПримерC (x) — «x — квадрат»;S(x) — «x — шар»;B(x) — «x — черный предмет»;W (x) — «x — белый предмет»;U(x, y ) — «предмет x лежит под предметом y ».МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКаждый белый куб лежит под каким-то черным шаром.∀x (W (x) & C (x) → ∃y (B(y ) & S(y ) & U(x, y )))~~~Модель I∀x (W (x) & C (x) & ∃y (B(y ) & S(y ) & U(x, y )))Каждый предмет является белым кубоми лежит под каким-то черным шаром.МОДЕЛИ.
ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))~Модель IМОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))~Модель I∃x (W (x) & C (x) → ∀y (B(y ) & S(y ) → U(x, y )))МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))~Модель I∃x (W (x) & C (x) → ∀y (B(y ) & S(y ) → U(x, y )))Какой-то предмет либо не является белым кубом,либо лежит под каждым черным шаром.МОДЕЛИ.
ЛОГИЧЕСКОЕ СЛЕДСТВИЕКакой-то белый куб лежит под всеми черными шарами.∃x (W (x) & C (x) & ∀y (B(y ) & S(y ) → U(x, y )))~Модель J∃x (W (x) & C (x) → ∀y (B(y ) & S(y ) → U(x, y )))Какой-то предмет либо не является белым кубом,либо лежит под каждым черным шаром.МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕОбщий принцип правильного построения формул.Каждый предмет, наделенный атрибутом A, обладаетсвойством B:∀x (A(x) → B(x))Некоторый предмет, наделенный атрибутом A, обладаетсвойством B:∃x (A(x) & B(x))МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕОпределениеПусть Γ — некоторое множество замкнутых формул, и ϕ —замкнутая формула.
Формула ϕ называется логическимследствием множества предложений (базы знаний) Γ, есликаждая модель для множества формул Γ является модельюдля формулы ϕ, т. е.для любой интерпретации I : I |= Γ =⇒ I |= ϕЛогические следствия — это «производные» знания, которыенеизбежно сопутствуют «базовым» знаниям Γ, находятся впричинно-следственной зависимости от предложений Γ. Однаиз главных задач (и одновременно наиболее характерноепроявление) интеллектуальной деятельности — это извлечениелогических следствий из баз знаний.МОДЕЛИ.
ЛОГИЧЕСКОЕ СЛЕДСТВИЕОбозначенияЗапись Γ |= ϕ обозначает, что ϕ — логическое следствие Γ .А какие формулы являются логическими следствиями пустойбазы знаний Γ = ∅? Правильный ответ: общезначимые .Поэтому для обозначения общезначимости формулы ϕ будемиспользовать запись|= ϕ .МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕТеорема о логическом следствииПусть Γ = {ψ1 , . . . , ψn } ⊆ CForm, ϕ ∈ CForm. ТогдаΓ |= ϕ ⇐⇒ |= ψ1 & . .
. &ψn → ϕ.Доказательство. ⇒ Пусть I — произвольная интерпретация.Если I 6|= ψ1 & . . . &ψn , то I |= ψ1 & . . . &ψn → ϕ.Если I |= ψ1 & . . . &ψn , то I |= ψi , 1 ≤ i ≤ n, т. е. I — модельдля Γ.Поскольку Γ |= ϕ, получаем I |= ϕ. Значит,I |= ψ1 & . . . &ψn → ϕ.Таким образом, для любой интерпретации I имеет местоI |= ψ1 & . . .
&ψn → ϕ.Значит, ψ1 & . . . &ψn → ϕ — общезначимая формула.МОДЕЛИ. ЛОГИЧЕСКОЕ СЛЕДСТВИЕТеорема о логическом следствииПусть Γ = {ψ1 , . . . , ψn } ⊆ CForm, ϕ ∈ CForm. ТогдаΓ |= ϕ ⇐⇒ |= ψ1 & . . . &ψn → ϕ.Доказательство. ⇐ Пусть I — модель для множествапредложений Γ, т. е. I |= ψi , 1 ≤ i ≤ n.Тогда I |= ψ1 & . . .
&ψn .Так как |= ψ1 & . . . &ψn → ϕ, верно I |= ψ1 & . . . &ψn → ϕ.Значит, I |= ϕ.Так как I — произвольная модель для Γ, приходим кзаключению Γ |= ϕ.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛОбщезначимые формулы — это каналы причинно-следственнойсвязи, по которым передаются знания, представленные в виделогических формул, преобразуясь при этом из одной формы вдругую.Практически важно уметь определять эти каналы инастраивать их на извлечение нужных знаний.IБаза знаний — множество предложений Γ;IЗапрос к базе знаний — предложение ϕ;IПолучение ответа на запрос — проверка логическогоследствия Γ |= ϕ.Если Γ — конечное множество, то проверка логическогоследствия сводится к проверке общезначимости формулыψ1 & . .
. &ψn → ϕПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛТаким образом, возникает проблемаобщезначимости формул:Для заданной формулы ϕпроверить ее общезначимость:|= ϕ?ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛУтверждение.Для любой формулы ϕ(x1 , . . . , xn ) верно, что1. |= ϕ(x1 , . . . , xn )⇐⇒|= ∀x1 . . . ∀xn ϕ(x1 , . .
. , xn );2.ϕ(x1 , . . . , xn ) — выполнимая⇐⇒∃x1 . . . ∃xn ϕ(x1 , . . . , xn ) — выполнимая;3.ϕ(x1 , . . . , xn ) — выполнима в любой интерпретации⇐⇒|= ∃x1 . . . ∃xn ϕ(x1 , . . . , xn ).ДоказательствоСамостоятельно. Это просто.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛКак же решать проблемуобщезначимости|= ϕ ?Может быть проверять всеинтерпретации по очереди ?ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛНет, такой подход заведомо обречен на неудачу. Почему?Потому, что верноУтверждение.Существует такая замкнутая формула ϕ, которая истиннав любой интерпретации I с конечной предметнойобластью DI , но не является общезначимой .∀x¬R(x, x) &∀x∀y ∀z(R(x, y )&R(y , z) → R(x, z)) →∃x∀y ¬R(x, y ).ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛДоказательство.R(x, y ): «субъект y — начальник субъекта x»;1).
∀x¬R(x, x): «никто не командует самим собой»;2). ∀x∀y ∀z (R(x, y )&R(y , z) → R(x, z)): «начальник моегоначальника — мой начальник»;3). ∃x∀y ¬R(x, y ): «кто-то никому не подчиняется».В каждой компании с конечным множеством сотрудников, вкоторой действуют законы 1) и 2), выполняется и закон 3).Значит, наша формула истинна во всех интерпретациях сконечной предметной областью.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛДоказательство.Но наша формула не является общезначимой.R(x, y ): «натуральное число y больше натурального числа x»1).
∀x¬R(x, x);2). ∀x∀y ∀z (R(x, y )&R(y , z) → R(x, z));выполняются на множестве натуральных чисел.3). ∃x∀y ¬R(x, y ) на множестве натуральных чисел невыполняется: неверно, что существует максимальноенатуральное число.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛНе только перебор всех интерпретаций, но даже проверкуистинности формулы в интерпретации с бесконечнойпредметной областью осуществить затруднительно.Значит, необходимо придумать более изощренный способпроверки.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима.
Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ. Изучим эту контрмодель.ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ. Изучим эту контрмодель.I 6|= ϕПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ.
Изучим эту контрмодель.I 6|= ϕI |= ∀x (P(x) → R(x)) I 6|= ∀x P(x) → ∀x R(x)ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ. Изучим эту контрмодель.I 6|= ϕI |= ∀x (P(x) → R(x)) I 6|= ∀x P(x) → ∀x R(x)I |= ∀x P(x)I 6|= ∀x R(x)ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима. Тогда должнасуществовать интерпретация I (контрмодель), опровергающаяϕ. Изучим эту контрмодель.I 6|= ϕI |= ∀x (P(x) → R(x)) I 6|= ∀x P(x) → ∀x R(x)I |= ∀x P(x)I 6|= ∀x R(x)I 6|= R(x)[d]ПРОБЛЕМА ОБЩЕЗНАЧИМОСТИ ФОРМУЛПример.Проверить общезначимость формулыϕ = ∀x (P(x) → R(x)) → (∀x P(x) → ∀x R(x)) .Предположим, что ϕ необщезначима.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
